(57)【特許請求の範囲】
【請求項１】
複数のボクセルを有するボリュームデータ集合をレンダリングする方法であって、
ａ)ボリュームデータ集合を複数のセクションに分割する工程と、
ｂ)ボクセル集合を外部メモリから順番に読み出しセクション内のボクセル集合をレンダリングして複数のセクションの最初の１つをレンダリングする工程と、
ｃ)複数のセクションの最初の１つのレンダリングで蓄積されたデータを一時記憶装置に記憶させる工程と、
ｄ)外部メモリから複数のセクションの次の１つのボクセル集合を順番に読み出しボクセル集合をレンダリングして複数のセクションの次の１つをレンダリングし、レンダリングが一時記憶装置からの蓄積データを合体させる工程と、
ｅ)複数のセクションの次の１つのレンダリングで蓄積されたデータを一時記憶装置に記憶させる工程と、
ｆ)ボリュームデータ集合の複数のセクションのそれぞれがレンダリングされるまで前記ｄ)工程とｅ)工程を繰り返す工程と、
を備え、
複数のセクションの境界からのボクセル集合を一時記憶装置中に記憶するステップと、複数のセクションの境界からのボクセル集合をフェッチしてセクションの境界を横切るボリュームデータ集合のレンダリングのためのレンダリング値を得るステップと、によりセクションの境界を横切ってボリュームデータ集合をレンダリングする工程をさらに備えたことを特徴とするボリュームデータ集合・レンダリング方法。
【請求項２】
複数のボクセルを有するボリュームデータ集合をレンダリングする方法であって、
ａ)ボリュームデータ集合を複数のセクションに分割する工程と、
ｂ)ボクセル集合を外部メモリから順番に読み出しセクション内のボクセル集合をレンダリングして複数のセクションの最初の１つをレンダリングする工程と、
ｃ)複数のセクションの最初の１つのレンダリングで蓄積されたデータを一時記憶装置に記憶させる工程と、
ｄ)外部メモリから複数のセクションの次の１つのボクセル集合を順番に読み出しボクセル集合をレンダリングして複数のセクションの次の１つをレンダリングし、レンダリングが一時記憶装置からの蓄積データを合体させる工程と、
ｅ)複数のセクションの次の１つのレンダリングで蓄積されたデータを一時記憶装置に記憶させる工程と、
ｆ)ボリュームデータ集合の複数のセクションのそれぞれがレンダリングされるまで前記ｄ)工程とｅ)工程を繰り返す工程と、
を備え、
セクションの境界付近のボクセルを再読み出しするステップと、複数のセクションの次の１つのレンダリングに使用するために再読み出しの結果を一時記憶装置に記憶するステップと、によりセクションの境界を横切ってボリュームデータ集合をレンダリングする工程をさらに備えたことを特徴とするボリュームデータ集合・レンダリング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はボリューム・グラフィックス、より詳細にはボクセル・ベースのデータを実時間処理してそのデータによって表すオブジェクトの視覚画像を生成するボリュームデータ集合・レンダリング方法およびボリューム・グラフィックス・システムに関する。
【０００２】
【従来の技術】
ボリューム・グラフィックスは、３次元以上のサンプルデータとして表現されるオブジェクトまたは事象のビジュアル化を扱うコンピュータ・グラフィックスの一分野である。これらのサンプルはボリューム・エレメントまたは「ボクセル」と呼ばれ、検討されるオブジェクトまたは事象の物理的特徴を表すデジタル情報を含む。例えば、ある特定のオブジェクトのボクセル・データは、密度、物質の種類、温度、速度、あるいはオブジェクトの内部や近くの空間での離散的なポイントにおける他の特性を表す。
【０００３】
オブジェクトのボクセル・ベースの表示は多くの状況および応用において起こる。例えば、人体または工業用組立品のトモグラフィック・スキャンおよび核磁気共鳴スキャンは、人体またはオブジェクトを構成する物質の密度および種類を表すデータの３次元アレイを生成する。同様に、地震および制御された爆発から収集した地震データが処理されて、地面下の土壌および岩石の種類を表すデータの３次元アレイを生成する。出生前のヘルスケアにおいて、子宮内の胎児の超音波スキャンによって、非浸襲性検査および診断のための３次元サンプル値が生成される。さらなる他の例は、航空機の翼の上またはジェットエンジンを通過する空気の流れのモデリングであり、それによってまた、航空機またはエンジンの設計および解析に使用できる３次元空間のポイントにおけるデータの離散的なサンプルが得られる。
【０００４】
ボクセルによって表されるオブジェクトの画像を見たいと思うのは当然である。過去に、二つの方法がこの目的のために利用できた。一つの方法は、一連の平行２次元画像スライス(断面)を構築することであり、各スライスは見ようとするオブジェクトの少しづつ異なる断面を表す。これは、人体のＣＴスキャンまたは核磁気共鳴スキャンを見る場合に、放射線医師が通常使用する方法である。放射線医師は、これら一連の２次元画像から人体の内臓の３次元メンタル・ピクチャーを構築するように訓練される。一般に、スライス群は人体の主要な次元または軸の一つに平行であり、そのためスライス群は放射線医師にとってあたりまえの「矢状縫合(サジタル)の」、「中軸の」および「冠状縫合(コロナ型)の」図を表す。ボクセル・ベースのデータを視覚化するこの方法は難しく、数年の訓練が必要であり、大抵の熟練開業医でさえも不確かになりがちである。
【０００５】
もう一つの方法は、ボクセル・データをコンピュータ・グラフィックス・システムが表示するのに適した表現に変換することである。現在、大抵のコンピュータ・グラフィックス・システムは、オブジェクトの表面を小さな三角形または多角形に細分することによってオブジェクトの表面を表示するように設計されている。これらの三角形には色および透明度または不透明度が割り当てられ、それからピクセル即ち画素に変換される、そしてコンピュータ画面に投影される。前景の表面に対応する三角形は、背景の表面に対応する三角形をぼんやりさせる。また、三角形を模様や他のパターンで彩色したり描いたりして、より写実的に見えるようにする。光の位置および効果をシミュレートすることによって現実感が可能となって、光輝部と影が結果として得られた画像に現れる。この種のグラフィックス・システムの技術は十分に発達しており、大部の文献、例えば、テキストブック「Computer Graphics:Principles and Practice」第二版(J. Foley, A. vanDam, S. Feiner, およびJ. Hughesによる共著、Addison-Wesley of Reading社刊、マサチュ−セッツ州、１９９０年)に記述されている。
【０００６】
この種の多角形ベースのグラフィックス・システムは、建築学的または機械的図面のようなオブジェクト表面のコンピュータモデルとして表現されるオブジェクトの画像を表示するのに特に適している。しかし、３次元サンプル値またはボクセルによって表現するオブジェクトを視覚化するのにはあまり適当ではない、何故なら、サンプルを三角形または多角形に変換するプロセスはコンピュータ費用が高くつくからである。ボクセルから多角形に変換するための多くのアルゴリズムが有る、例えば、W. E. Lorensen、H. E. Cline共著の有名なMarching Cubes algorithm、 題名「Marching Cubes:A high-resolution 3D surface construction algorithm」 Computer Graphics, the Proceedings of the 1987 SIGGRAPH Conference, pages 163-169 に発表。これらアルゴリズムのすべてが表面の細部を失うという問題を経験し、あるものは医療用画像などの応用が不可能となる。
【０００７】
ここ数年の間に、ボリューム・レンダリングと呼ばれる別の方法が登場した。この方法は、そこではボクセル・ベースの表現の個々のボクセルに色および透明度または不透明度が割り当てられるデジタル信号処理の形式である。そして、それらはコンピュータ画面のような２次元画面に投影されて、前景の不透明なボクセルが背景の他のボクセルをぼんやりさせる。この投影されたボクセルの蓄積によって、オブジェクトの視覚画像が生ずる。照明計算を個々のボクセルについて行って、従来のコンピュータ・グラフィックスと類似の方法で光輝部および影を表す。
【０００８】
色および透明度の特定のボクセル・データ値への割り当てを変更することによって、オブジェクトの外部および内部の異なる面を見ることができる。例えば、手術の準備において膝の靭帯、腱、および骨を検査する必要がある外科医が膝の断層撮影スキャンを利用することができて、血、皮膚、および筋肉に対応するボクセル・データ値を完全に透明に見えるようにできる。他の例では、整備士はジェットエンジン内のタービンブレードまたは溶接点の断層撮影スキャンを使用して、金属を表すボクセル・データ値を透明に、一方空気を表すボクセル・データ値を不透明にすることができる。これによって目に見えない金属内部の欠陥を見つけることがてきる。
【０００９】
コンピュータ・データから見える画像を生成するプロセスは「レンダリング」と称し、そしてボクセル・データから見える画像を生成するプロセスは「ボリューム・レンダリング」と称する。個々のボクセルのデータ値に色および透明度をマッピングするメカニズムは「伝達関数」と称する。
【００１０】
ａ)ボクセル・データの投影
オブジェクトを表すデータ・ポイントまたはボクセルを取って、それをコンピュータ画面のような平らな画面に投影する技術は沢山ある。これらの技術は各々、見ようとするオブジェクトを、そのオブジェクトを表す３次元サンプル・データを画面の正面または後ろの空間の空間座標に変換することによって画面を基準として配置する。これらの技術には、その画面上のディスクリートポイントまたは「ピクセル」における光の色および強度を計算するいろいろな方法がある。
【００１１】
一つの技術では、一連のボクセル・データの高速フーリエ変換を計算し、それらを結合し、そしてフーリエ逆変換を計算して結果として生ずる２次元画像を得る。それは、T. Malzbender による米国特許番号５，４１４，８０３「３次元オブジェクトの２次元面を生成するための周波数領域表現の利用方法」に著わされている。
【００１２】
「スプラッティング」と称する第二の技術は、L. A. Westoverの博士論文「スプラッティング：平行なフィード・フォワード・ボリューム・レンダリング・アルゴリズム」(ノースカロライナ大学コンピュータ科学部出版、１９９１年７月、技術報告番号ＴＲ９１−０２９)に著わされた。スプラッティング技術において、１セットの３次元サンプル・データの個々のボクセルを観察者の目の方向に投影する。投影されたボクセルの色および透明度を投影像がコンピュータ画面と交わるポイントを囲む当面の領域における画面のピクセルと数学的に結合する。このようにしてすべてのボクセルを蓄積した場合に、結果として生ずる画像は３次元オブジェクトの２次元画像であるように見える。
【００１３】
第三の技術では、３次元セットのデータをいわゆる「テクスチャ・マップ」に変換して、それを最近のコンピュータ・システムのあるタイプで見られるテクスチャ・マップ・メモリーに保管する。それから、このテクスチャ・マップを使用して、一連の平行プレーンを「描き」または「色付け」する。各々は見る方向に垂直である。したがって各々は当該オブジェクトの断面のように見える。それから、これらのプレーンをコンピュータ・システムのグラフィックス・サブシステムによって数学的に結合して、観察者には３次元オブジェクトであるように見える画像を形成する。この方法は、１９９１年「ボリューム視覚化に関するワークショップ」においてB. Cabral、 N. Camおよび J. Foranによって発表された論文「テクスチャ・マッピング・ハードウェアを使用する加速ボリューム・レンダリングおよび断層撮影再構成」に詳細に著わされている。さらにそれは、T. J. CullipおよびU. Neumannによって著わされた技術報告番号ＴＲ９３−０２７「３次元テクスチャ・マッピング・ハードウェアによる加速ボリューム再構成」(ノースカロライナ大学コンピュータ科学部出版)に述べられている。
【００１４】
第四の技術は「光線キャスティング」と称する。この技術では、仮想の光線が観察者の目から画面の各ピクセル真中を通過し、そして観察対象のオブジェクトを通過する。ボリュームを通過する各光線は、その経路に沿った各ポイントの視覚特性で「ロードアップ」される。光線がボリュームを通過するにつれて、その特性全体は光線に沿ったポイントのすべての特性の和集合すなわち数学的集積となる。そしてこの和集合すなわち集積を光線が通過するピクセルに割り当てる。それによって光の点が画面上に見える。そのような光線すべての蓄積によって、画面上に視覚画像を生ずる。
【００１５】
光線がボリュームを通過する場合に、いくつかは３次元サンプル・データによって表すポイントの間を通るが、それらと交差しない。評価したいのは、これらの「はずれた」データ・ポイントまたはボクセルは、どれかの光線に対応するピクセルの色または強度に反映されないということである。このはずれたデータ・ポイントの問題を解決するために、補間技術を使用して、はずれたポイントの直ぐ隣のボクセルからの値を合成する。ある例では、プレーン内の４つの最も近いボクセルの値の二本線補間の数学的方法によって、合成値を光線が横切るサンプルポイントまたはボクセルの各プレーンに対して生成する。他の例では、各ポイントを囲む８つの最も近いボクセルの三本線補間の数学的方法によって、合成値を光線に沿って均等な間隔で生成する。これらの方法において、光線がオブジェクトを通過するにつれて、経路に沿って蓄積された特性は最も近い隣のものの特性を考慮してはずれたポイントの値を合成する。評価したいのは、合成ポイントを生成する可能な方法が多くあるということ、そしてこれらは投影された画像の品質および現実感に大いに関係があるということである。
【００１６】
２次元画像が人間の目によって３次元のオブジェクトまたは場面の像として知覚されるためには、画像が光と影の効果を備えることが重要である。これは、前述のＪ．  Ｆｏｌｅｙ他著のテキストブックを含むコンピュータ・グラフィックスの広範な文献の主題である。たいていの技術は、表示されるオブジェクトの各表面の各ポイントに対して「法線ベクトル」または垂直方向を見つけ、それからそれらポイントを照らすためにこれらの法線ベクトルおよび観察者と光源の位置にもとづいた計算を行う、そして光輝部と影の効果を生ずる。
【００１７】
多角形と表面にもとづいた従来のコンピュータ・グラフィックスにおいては、これらの法線ベクトルを表面の数学モデルから直接計算できるのに対して、ボリューム・グラフィックスにおいては、法線ベクトルをサンプル・データ自体から抽出する必要がある。これを各ボクセルに対して、例えば、直ぐ隣の他のボクセルの値を検査することによって行う必要がある。異なる物質、例えば異なる組織の境界において、隣り合うボクセルの値に著しい差異または勾配がある。これらの差異から、法線ベクトルを計算できる。そして、一種の物質が透明であり隣接の物質が不透明である場合はいつも、投影によって異なる物質間の端と表面がはっきり区分できる。さらに、これらの法線ベクトルにもとづくライティング計算によって、これらの表面の不整が人間の目によって３次元として認識できるように強調される。例えば、脳を構成する灰色の物質中の隆起を、断層撮影スキャンからこの方法で、頭蓋の皮膚と骨を簡単に透明にすることによって、はっきりと表示することができる。
【００１８】
ｂ)計算の要求事項
評価したいのは、ボクセル・データを計算表面に投影する上記技術の四つすべてが膨大な量の計算を必要とし、パーソナルまたはデスクトップ・コンピュータのサイズおよびコストの装置には従来不適当であったということである。その上、それらは、ボリュームを有用な方法で、例えば医学診断において描画するために多くの異なる技術の呼び出しを含む。一般に、投影画像を形成するために、３次元データの各ボクセルを少なくとも一度調査する必要がある。サンプル・データ集合が一つのサイドに２５６ポイントを有するキューブである場合に、これは現行の医学用の断層撮影および核磁気共鳴スキャンの典型的サイズであり、そのとき合計２５６3または約１千６百万のボクセルを評価する必要がある。しかし、サンプル・データ集合が一つのサイドに４０９６ポイントを有するキューブである場合に、これは石油と天然ガスの採鉱に使用される地質データの典型であり、そのとき、単一の画像を描くために合計４０９６3または約６４０億のボクセルを評価する必要がある。
【００１９】
さらに評価したいのは、静的データの静的画像をレンダリングする計算費用が高いとしても、なにか他の方法で動き、回転し、または変化するオブジェクトをレンダリングするのに要する計算の力を考慮するとこれは重要ではなくなるということである。多くの応用は、実時間で動いているように見えるオブジェクトの視覚化を必要とし、それは１秒当たり３０フレームのオーダーのレンダリングを意味する。すなわち、各ボクセルを１秒当たり３０回再評価したり投影したりする必要がある。２５６3データ・ポイントのボリュームについて言えば、これは、データをサンプル・データ集合から１秒当たり２５６3×３０または約５億３百万回抽出する必要があることを意味する。注目すべきは、ボリューム・レンダリングをコンピュータ・プログラムによって行う場合に、フレーム当たりデータ・ポイント毎に１０から１００の計算機命令を必要とすることである。したがって、回転または変化するボリュームグラフィック画像を見る処理力は、１秒当たり５０億から５００億回の動作である。データセットの３乗の側におけるデータ・ポイント数の各倍増に注目すると、要求処理力は８倍増える。
【００２０】
通例の妥協は、フレームレート、視覚品質、コスト、またはサイズを犠牲にすることである。現在、コンピュータ・ソフトウェアにおいて２５６3ボリュームをレンダリングして得るベストは、現行の上位パソコンに見られる８組のプロセッサにおいて１秒当たり１から２フレームである。グラフィックスに特化し膨大な容量のテクスチャ・メモリを備える非常に高価なコンピュータを使用して、光輝部と影を犠牲にすることによって、１秒当たり１５フレームまでのフレームレートを遂行できる。画像品質を犠牲にせずに１秒当たり３０フレーム以上の実時間フレーム・レートを実際に行う他のアプローチは、パーソナルまたはデスクトップサイズ装置にとって大きすぎて高価である非常に特殊化されたシステムをもたらす。
【００２１】
ｃ)計算の要求事項の削減
光線キャスティング技術にもとづいて１秒当たり３０フレームで実時間ボリューム・レンダリングを得るようにこのやや暗い見通しを改善するために、ニューヨーク州立大学のAri KaufmanとHanspeter Pfisterによる開発が米国特許番号５，５９４，８４２「実時間ボリューム視覚化の装置および方法」に記述されている。この開発では、多数の光線を平行にボリュームを通過させ、そしてボリュームデータを一度に一スライス評価することによってそれらを処理することによって改善する。ソフトウェアとは対照的に、特殊化された電子ハードウェアにおいて速くスライス処理ができる場合、わずかなコストで１秒当たり２フレームから１秒当たり３０フレームに増やすことができることが実証された。
【００２２】
理論上、これは、非常に多数のメモリー・モジュールおよび特殊化された処理パイプラインを利用してハードウェアで達成される。多数のメモリー・モジュールおよびパイプラインを使用して、「Ｃｕｂｅ−４」と呼ばれるシステムにおいていろいろなメモリー・モジュールから並列にデータを選び出すことができる。Ｃｕｂｅ−４は、H. Pfister。 A. KaufmanおよびT. Wesselsによる論文「Towards a Scalable Architecture for Real-time Volume Rendering」(the 10th Eurographics Workshop on Graphics Hardware at Masstricht, The Netherlands で1995年8月28,29日に発表、)に述べられている。さらにHanspeter Pfisterによる博士論文(１９９６年１２月、ニューヨーク州立大学コンピュータ科学部へ提出)にも述べられている。
【００２３】
Ｃｕｂｅ−４システムの本質は、オブジェクトを表す３次元サンプル・データを、「スキューイング」と呼ばれる技術によってメモリー・モジュール中に配信し、そのため各次元内の隣接するボクセルを隣接のメモリー・モジュールに保存することである。各メモリー・モジュールはそれ自体の処理パイプラインに関連する。さらに、ボクセルはメモリー・モジュール内で編成されて、Ｐ個のパイプラインとＰ個のメモリー・モジュールが有る場合には、Ｐ個の隣接するボクセルを、並列に、コンピュータ・メモリー・システムの単一サイクル内で、見る方向に依って、同時にフェッチすることができる。これによってボクセルをメモリーからフェッチする合計時間がＰ分の１に減少する。例えば、データセットが２５６3個のボクセルを有し、Ｐの値が４の場合には、画像をレンダリングするためにデータをフェッチするのに必要なのはわずか２５６3÷４即ち約４百万メモリー・サイクルだけである。
【００２４】
Ｃｕｂｅ−４システムのその他の特徴は、ボリューム・レンダリングに必要な計算処理をこの目的のために特殊化された機能を有するパイプラインに編成することである。各パイプラインは、各サイクル内の新しいボクセルの処理を始めることができる。このように、第一のサイクルで、パイプラインはその関連メモリー・モジュールからボクセルをフェッチして処理の第一のステップを行う。そして第二のサイクルで、それはこの第一のボクセルの処理の第二のステップを行う、それと同時に第二のボクセルをフェッチしてこのボクセルを処理する第一のステップを行う。同様に、第三のサイクルで、パイプラインは第一のボクセルの第三の処理ステップ、第二のボクセルの第二の処理ステップ、および第三のボクセルの第一の処理ステップを行う。このようにして、各メモリー・モジュールからのボクセルは、その対応するパイプラインを通して決まりきったやり方で、次から次に、完全に処理されるまで進む。したがって、ボクセル当たり１０〜１００の計算機命令を必要とする代わりに、新しいボクセルをサイクル毎に処理できる。
【００２５】
Ｃｕｂｅ−４システムのさらなる革新的特徴は、各パイプラインはその至近隣接するものとだけ交信することである。例えば、そのような交信は、光輝部と影の効果を計算するために勾配または法線ベクトルを見積もる目的でボクセル値を一つのパイプラインから次のパイプラインへ送信するのに必要である。それはまた、光線が通過する領域の近辺のボクセルの視覚特性を蓄積するボリュームを通過するにつれて光線の値を伝えるのに使用される。
【００２６】
この至近隣接通信のアプローチによって、Ｃｕｂｅ−４の主要な利点である「スケーラブル」が提供される。つまり、大量の３次元サンプル・データを収容したり、このデータを高速に処理したりするために、より多くのモジュールおよびパイプラインを増設することが必要である。この拡張によって過負荷となる共通バスや他のシステム資源はない。
【００２７】
Ｃｕｂｅ−４システムでは、ボリューム・レンダリングは次のように進む。データを立方体または他の長方形の固体として編成する。見る方向にほぼ垂直なこの立方体または固体の面を第一に考慮して、上部の角のＰ個のボクセルの部分的な列をＰ個のメモリー・モジュールから、一つのメモリー・サイクルで同時にフェッチして、Ｐ個の処理パイプラインの第一のステップに挿入する。第二のサイクルで、これらのボクセルをそれらのパイプラインの第二段階へ動かしたり、隣接のパイプラインの第二段階へ送信したりする。同時に、次のＰ個のボクセルを同じ列からフェッチして、それらのパイプラインの第一段階に挿入する。続く各サイクルにおいて、Ｐ個より多いボクセルを上部の列からフェッチして、それらのパイプライン中に挿入する、一方、前にフェッチされたボクセルはそれらのパイプラインの後の段階に移動する。これは、ボクセルの列全体がフェッチされるまで続く。そして次の列を、一度にＰ個のボクセルをフェッチし、それから次々に、ボリューム・データ・セットの面の列すべてをフェッチしてそれらの処理パイプラインに挿入するまで行う。
【００２８】
この面は「スライス」と称する。そしてＣｕｂｅ−４システムは再び上部の角に移動するが、今度はこの面の直ぐ後ろの上部の列のＰ個のボクセルをフェッチし始める、即ち第二の「スライス」から、このように、それはデータセットの第二のスライスを通して進む、一度に一列そして各列内で一度にＰ個のボクセル。第二のスライスを完了後、それは第三のスライスへ進み、それから、すべてのスライスを処理するまで、同様にして続くスライスへ進む。このアプローチの目的は、ボリューム・データ・セット全体を処理して画像を形成するまで、一度にＰ個のボクセルづつ、順序立った方法ですべてのボクセルをフェッチし処理する。
【００２９】
Ｃｕｂｅ−４システムの用語で、ボクセルの列は「ビーム」と称し、ビーム内のＰ個のボクセルのグループは「部分ビーム」と称する。
【００３０】
Ｃｕｂｅ−４システムの処理段階は、サンプルの補間、勾配または法線ベクトルの推定、色および透明度または不透明度の割り当て、および２次元画面に最終画像を生成する光と影の効果の計算などの光線放射技術に必要な計算のすべてを行う。
【００３１】
Ｃｕｂｅ−４システムは、半導体技術で実現できるように設計された。しかし、二つの制限要因によって、パーソナルまたはデスクトップサイズ・コンピュータのために小さいサイズと低コストを達成するのが妨げられる。即ち、メモリー・モジュールからボクセル値にアクセスする速度、および各処理パイプラインで必要な内部記憶装置の容量である。メモリーにアクセスする速度については、ボリューム・データ・セットをＣｕｂｅ−４システム内に保管するのに適した現行の半導体メモリーデバイスは遅すぎるか高価格すぎるかまたはその両方である。もっと低価格のメモリーがパーソナルまたはデスクトップ・コンピュータで有用な実用的なシステムのために必要である。内部記憶装置については、Ｃｕｂｅ−４アルゴリズムは、各処理パイプラインが処理中に中間結果をそれ自体内に保管することを要求する。記憶装置の容量は、レンダリングされるボリューム・データ・セットの面の領域に比例する。２５６3個のデータセットでは、この量は単一チップ処理パイプラインのサイズをかなり増加するほど大きくて、パーソナル・コンピュータ・システムにとって過大なコストとなる。実用的なシステムでは、この中間記憶容量を減らすことが必要である。
【００３２】
ｄ)ブロック化およびＳＲＡＭ技術
Ｃｕｂｅ−４と同じ頃設計された他の実験システムにおいては、これらの制限が無視された。そのような一つのシステムは「ＤＩＶ2Ａ」(Distributed Volume Visualization Architecture)と称し、J. Lichtermannによる論文「並列ボリューム視覚化のための高速ボクセル・プロセッサの設計」(the 10th Eurographics Workshop on Graphics Hardware, August 28 and 29, 1995, at Maastricht, The Netherlandsで発表)に述べられている。そのような他のシステムはＶＩＲＩＭシステムと言い、M. deBoer, A. Gropl、 J. HesserおよびR. Mannerによる論文「ダイレクト・ボリューム・レンダリングのためのラテンシィおよびハザード・フリー・ボリューム・メモリー・アーキテクチャ」(the 11th Eurographics Workshop on Graphics Hardware on August 26-27, 1996, in Poitiers, Franceで発表)に述べられている。
【００３３】
ＤＩＶ2Ａシステムはリング内でともに接続された１６の処理パイプラインから成り、その結果、各パイプラインは各サイド上の至近隣接パイプラインと直接通信できる。各処理パイプラインは、ボリューム・データ・セットの一部を保管する関連メモリー・モジュールを有する。ボクセルは小さいサブキューブに編成される。そしてこれらのサブキューブをメモリー・モジュールに分配して、隣接のサブキューブを３次元の各々の隣接のメモリー・モジュールに保管する。しかし、２５６3個のデータセットを１秒当たり３０フレームでレンダリングするために必要なメモリー・アクセス速度を達成するために、ＤＩＶ2Ａシステムは各メモリー・モジュール内に８つの並列メモリーバンクを必要とする。さらに、各メモリーバンクはスタティック・ランダム・アクセス・メモリー即ちＳＲＡＭデバイスで実装される。
【００３４】
現在の半導体技術において、ＳＲＡＭデバイスは非常に高速なので、高速度のデータ・アクセスをサポートすることができる。しかし、それらはまた非常に高価で、消費電力が非常に大きく、容量が制限される。ＤＩＶ2Ａシステムは処理パイプライン当たり８つのＳＲＡＭデバイスを必要とし１６の処理パイプラインを備えるので、合計１２８のＳＲＡＭデバイスが必要で、２５６3個のボリューム・データ・セットのボクセルを保管する。これは、パーソナル・コンピュータの背後に組み込むボードの物理的サイズと電力の制限をはるかに越えているということが分かる。ＤＩＶ2ＡおよびＶＩＲＩＭはファイル・キャビネットの引出しのサイズであり、それらが接続するデスクトップ・コンピュータを含まない。
【００３５】
【発明が解決しようとする課題】
以上のようなことから従来、実時間ボリューム・レンダリングをパーソナルまたはデスクトップ・コンピュータにとって実用的なものとすることは難しいという課題があった。
【００３６】
この発明は、上記のような課題を解消するためになされたもので、実時間ボリューム・レンダリングをパーソナルまたはデスクトップ・コンピュータにとって実用的なものにすることを目的とする。
【００３７】
【課題を解決するための手段】
上記の目的に鑑み、この発明は、複数のボクセルを有するボリュームデータ集合をレンダリングする方法であって、ａ)ボリュームデータ集合を複数のセクションに分割する工程と、ｂ)ボクセル集合を外部メモリから順番に読み出しセクション内のボクセル集合をレンダリングして複数のセクションの最初の１つをレンダリングする工程と、ｃ)複数のセクションの最初の１つのレンダリングで蓄積されたデータを一時記憶装置に記憶させる工程と、ｄ)外部メモリから複数のセクションの次の１つのボクセル集合を順番に読み出しボクセル集合をレンダリングして複数のセクションの次の１つをレンダリングし、レンダリングが一時記憶装置からの蓄積データを合体させる工程と、ｅ)複数のセクションの次の１つのレンダリングで蓄積されたデータを一時記憶装置に記憶させる工程と、ｆ)ボリュームデータ集合の複数のセクションのそれぞれがレンダリングされるまで前記ｄ)工程とｅ)工程を繰り返す工程と、を備え、複数のセクションの境界からのボクセル集合を一時記憶装置中に記憶するステップと、複数のセクションの境界からのボクセル集合をフェッチしてセクションの境界を横切るボリュームデータ集合のレンダリングのためのレンダリング値を得るステップと、によりセクションの境界を横切ってボリュームデータ集合をレンダリングする工程をさらに備えたことを特徴とするボリュームデータ集合・レンダリング方法にある。
【００３８】
また、複数のボクセルを有するボリュームデータ集合をレンダリングする方法であって、ａ)ボリュームデータ集合を複数のセクションに分割する工程と、ｂ)ボクセル集合を外部メモリから順番に読み出しセクション内のボクセル集合をレンダリングして複数のセクションの最初の１つをレンダリングする工程と、ｃ)複数のセクションの最初の１つのレンダリングで蓄積されたデータを一時記憶装置に記憶させる工程と、ｄ)外部メモリから複数のセクションの次の１つのボクセル集合を順番に読み出しボクセル集合をレンダリングして複数のセクションの次の１つをレンダリングし、レンダリングが一時記憶装置からの蓄積データを合体させる工程と、ｅ)複数のセクションの次の１つのレンダリングで蓄積されたデータを一時記憶装置に記憶させる工程と、ｆ)ボリュームデータ集合の複数のセクションのそれぞれがレンダリングされるまで前記ｄ)工程とｅ)工程を繰り返す工程と、を備え、セクションの境界付近のボクセルを再読み出しするステップと、複数のセクションの次の１つのレンダリングに使用するために再読み出しの結果を一時記憶装置に記憶するステップと、によりセクションの境界を横切ってボリュームデータ集合をレンダリングする工程をさらに備えたことを特徴とするボリュームデータ集合・レンダリング方法にある。
【００４１】
実時間ボリューム・レンダリングをパーソナルまたはデスクトップ・コンピュータにとって実用的なものとするために、本発明は、メモリー・モジュールに高容量で低価格のダイナミック・ランダム・アクセス・メモリー即ちＤＲＡＭデバイスを使用するアーキテクチャの変更を含む技術を提供することによって、Ｃｕｂｅ−４システムをさらに改善する。ＤＲＡＭデバイス即ち「チップス」は、ＳＲＡＭデバイスよりチップ当たり５〜１０倍の情報を保管することができ、コストが保管される情報のビット当たりで５〜１０分の１、そして動作電力が非常に少ない。現在、ＤＲＡＭデバイスは、４、１６および６４メガビットのものが利用できる。４つの６４メガビットＤＲＡＭを用いれば、ボクセル当たり１６ビットを有する２５６3ボクセルのデータセットを格納するのに４個のチップしか必要としない。４個のＤＲＡＭモジュールをパイプラインを処理する４個のカスタム・デザインの半導体デバイスと結合することによって、本発明は、パーソナル・コンピュータの後部に差し込むことができるボード上で実時間ボリューム・レンダリング・システムを具体化することができる。
【００４２】
しかしながら、ＤＲＡＭデバイスやチップはＳＲＡＭデバイスよりずっと遅い。通常、ＳＲＡＭチップが１秒当たり５０〜２００百万回のアクセスをサポートするのに対して、ＤＲＡＭチップは１秒当たり８〜１２百万回のアクセスしかサポートできない。したがって、４個のＤＲＡＭデバイスは２５６3個のボクセルのボリューム・データ・セットを格納するのに十分な容量を有しているが、合わせてそれらは、１秒当たり３０フレームでデータセットを描画するのに必要な１秒当たり５０３百万回のアクセスのデータ速度よりずっと少ない、１秒当たりたった約３２〜４８百万回のアクセスしかサポートできない。
【００４３】
ＤＲＡＭの高容量と低コストという利点を実現するために、本発明は、「バースト・モード」アクセスをサポートするＤＲＡＭチップを利用する。現在、この特徴はいくつかのＤＲＡＭで見られ、ＳＲＡＭデバイスと同じ位速いアクセス速度を可能にする。しかしそれは速いシーケンスで連続したメモリー・ロケーションにアクセスした場合だけである。この条件を満足できるようにしてバースト・モードＤＲＡＭを利用できるようにするために、Ｃｕｂｅ−４システムのアーキテクチャを修正する必要がある。本発明は、この目的のために４つのテクニックを利用する。
【００４４】
「ブロック化」と称する第一のテクニックにおいて、データをブロックに編成して、一つのブロック内のすべてのボクセルを単一のメモリー・モジュール内の連続したメモリー・アドレスに格納する。これによって、一度に一つのボクセルではなく一気にブロック全体のデータをフェッチすることが可能となる。このようにして、単一の処理パイプラインは１秒当たり１２５百万以上のボクセルのデータ速度でメモリーにアクセスできて、このようにして４つの処理パイプラインと４つのＤＲＡＭモジュールが１秒当たり３０フレームで２５６3個のデータセットをレンダリングすることが可能となる。
【００４５】
Ｃｕｂｅ−４システムを改善する第二のテクニックは「セクション化」と称する。このテクニックでは、ボリューム・データ・セットをセクションにさらに分割して、一度に一つのセクションをレンダリングする。各セクションはより小さい面積を有する面をレンダリング・パイプラインに提供するので、内部記憶装置が小さくて済む。さらに、処理個別セクションからの中間結果を処理パイプラインの外側に格納することが可能で、それからお互いに結合編集してレンダリングされるオブジェクトの完全な画像を形成する。このテクニックの効果は、処理パイプライン内の中間格納量を半導体実装で可能なレベルまで減らすことである。
【００４６】
第三のテクニックは、ピンの数および隣接処理パイプラインをお互いに接続するピンを横切って伝送するデータの速度を減らす。これは、ブロック当たり伝送する必要があるデータ量を約１／Ｂに減らすブロック化の副次効果を利用して行う。ここで、Ｂはブロックのエッジにおけるボクセルの数である。
【００４７】
最後のテクニックは「ミニ・ブロック化」と称し、前述のセクション化テクニックをさらに改善する。このテクニックでは、一つのブロックのＢ3個のボクセルを各サイズ２×２×２のミニ・ブロックと称する小さいブロックまたはキューブにさらに編成する。これによって、一つのセクションと前に処理したセクションの間の境界付近のボクセルを処理する場合に、ブロック全体を読み取るのを回避してミニ・ブロックだけを読み取ることができる。これによって、セクション内の一つのボリュームを処理するに要する時間を約５〜７％節約することができる。
【００４８】
これらの４つのアーキテクチャの改善の全体的な効果は、ＤＲＡＭメモリー・モジュールを使用してＣｕｂｅ−４アーキテクチャにもとづく実用的な低コストのボリューム・レンダリング・システムを具体化できて、それによってそのサイズとコストを小形ファイル・キャビネットのものからパーソナル・コンピュータの後部に差し込むことができるプリント基板のそれに減らすことができることである。副次的効果は、パイプラインとそのメモリーを同一の半導体チップ内に実装できるようにＣｕｂｅ−４アーキテクチャをさらに小さくできることである。これによって、ボリューム・レンダリング・システムのサイズと電力要求がさらに減少する。
【００４９】
ブロック化についてさらに詳述すると、電流バースト・モードＤＲＡＭデバイスは１秒当たり１２５百万回以上のアクセス動作できるが、連続したメモリー・アドレスからデータをフェッチする間だけである。最小バースト・サイズは少なくとも８つの遂次アクセスであるが、しばしばそれ以上である。このデータ速度は、４つのパイプラインが１秒当たり３０フレームで２５６3個のデータセットまたは約５０３百万のボクセルをレンダリングするのに十分である。しかし、遂次アクセスが少なくとも最小バースト・サイズに対する遂次アドレスであるようにデータをメモリー内で編成できる場合にだけ、バースト・モードは動作する。
【００５０】
初めに示したようにＣｕｂｅ−４では、これは多くの見る方向にとって可能ではない。見る方向の少なくとも３分の１から、遂次ボクセルをＮアドレスずつ隔たったメモリー・ロケーションからアクセスする。ここでＮはキュービックデータセットのエッジにおけるボクセルの数である。見る方向の他の３分の１から、遂次ボクセルをＮ2ずつ隔たったアドレスからアクセスする。この結果、バースト・モードＤＲＡＭデバイスさえもその最も遅いモード、アドレスにランダムアクセスするそれに変化する。このモードでは、ＤＲＡＭデバイスは１秒当たりたった約８百〜１千２百万回のアクセスをサポートできるだけである。
【００５１】
どの方向からオブジェクトを見ようともボクセルのバーストを連続したメモリー・アドレスからフェッチできるようにボクセル・データを編成することによって、この問題を解決できる。これを行うために、ボクセル・データを一つのサイドにＢ個のボクセルを有する小さいキューブまたはブロックにグループ分けし、それでサイズＢ×Ｂ×Ｂのブロックのボクセルのすべてを単一のメモリー・モジュール内の連続アドレスに格納する。Ｂにどんな値でも使用できるが、４〜８のＢの値が最も実用的である。
【００５２】
レンダリングは見る方向とは独立であるというＣｕｂｅ−４の特徴を保持するために、データをメモリー・モジュールを横切ってスキューする必要がある。しかし、Ｃｕｂｅ−４におけるようにボクセルによってスキューイングする代わりに、本発明ではデータがブロックによってスキューされる。特に、ボリューム・データ・セットの３次元のいずれにおける隣接するブロックも隣接するメモリー・モジュールに格納する。これによって、Ｐ個の隣接する処理パイプラインがボクセルのＰ個の隣接するブロックをバースト・モードでＰ個の隣接するメモリー・モジュールから、すべて平行にそして同時にフェッチすることが可能となる。各パイプラインは一つのブロック内のボクセルのすべてをレンダリングする、そしてそれらすべてはそれらの各々の次のブロックへ進む、全く同様に、Ｃｕｂｅ−４処理パイプラインはそれらの個々の次のボクセルに進む。この体系では、個々のボクセルを処理する順序は、Ｃｕｂｅ−４システムにおける順序と本発明においては同じではない、そしてＣｕｂｅ−４アルゴリズムに対する重要な変更が必要である。
【００５３】
セクション化に関して言えば、これは処理パイプラインにおける中間結果に必要な記憶量の問題を扱う。Ｃｕｂｅ−４システムおよび本発明に導入する変更の両方において、中間記憶装置の要求量はＮ2／Ｐに大体比例する、ここでＮはキュービックデータセットの一つのサイドにおけるボクセルの数であり、Ｐはメモリー・モジュールおよびパイプラインの数である。この比の根拠は、Ｃｕｂｅ−４アルゴリズムにもとづいて勾配または法線ベクトルを計算するためには、現在処理しつつあるスライスのボクセル値を２つの前のスライスでフェッチされたボクセル値と数学的に結合することが必要であるということである。同様に、光線に沿った「欠けたデータ・ポイント」の値を得るために３つの線の補間を計算するために、処理されるスライスからのボクセル値を前に処理したスライスからのボクセル値と数学的に結合することが必要である。この正味の効果は、現行スライスの処理を完成するために、各パイプラインは一つまたは二つの前に読み取られたスライスからボクセルを記憶する必要があるということである。一つのサイドにＮ個のボクセルを有するキュービックデータセットでは、保存する必要があるボクセル数はスライス内のボクセル数、即ちＮ2に比例する。しかし、このデータをＰ個の処理パイプラインを横切って配信する、そのためにこの数はＮ2／Ｐに減少する。通常、比例係数は３以上である。
【００５４】
より一般的には、ボクセル・データセットが任意の割合の方形固体を表す場合に、スライスからスライスに格納する必要があるデータ量は見る方向にほとんど垂直な面の面積に比例する。
【００５５】
現在の半導体技術にとって、これは一つの処理チップに経済的に適合するにはあまりにもデータが多すぎることが分かる。特に、Ｎが２５６でＰが４である場合には、Ｃｕｂｅ−４システムで必要な記憶装置の容量は少なくとも３×２５６2÷４、または約５０，０００ボクセルであり、１６ビットのボクセル値に対して約８００，０００ビットである。この記憶容量はＳＲＡＭまたはＤＲＡＭの半導体技術で容易に実現できるが、それは処理ユニットに適する現在の技術ではかなり大きい半導体デバイスとなるので、それはパーソナルおよびデスクトップ計算環境にとって非常に高価なものとなる。
【００５６】
この問題を解決するために、ボリューム・データ・セットを、見る方向に最も近いボリュームの面に垂直にそれをさらに分けることによって、セクションに分割する、そのようなさらに分けられた各々は「セクション」と称する。セクションが独立のボリューム・データ・セットであるかのように、セクションを他のセクションから個別にレンダリングする。セクションをレンダリングする場合に、一部の光線はそのセクションを通過して後部へ出る。これらの光線の視覚特性、即ち、色、輝度、および透明度を見る面の対応するピクセルに直接割り当てる。しかし、他の光線はそのセクションの側面、上面、または底面の外を過ぎて、隣接するセクションの中に入る。隣接セクション内の同じ光線の連続をレンダリングする場合に、これらの光線の視覚特性を退避して利用する必要がある。これらの光線を退避するために、本発明の処理パイプラインがそれらを外部記憶モジュールモジュールに書き込む。後に、それが近隣セクションを処理し始めたとき、それはそれらを再読み込みして、それらの連続の視覚特性を初期化する。
【００５７】
この正味の効果は、処理パイプライン内に要する記憶装置容量を最も大きいセクションの面の表面積に比例する容量まで減らすことである。逆に、セクションのサイズを、利用できるメモリーの容量にもとづいて選択することができる。本発明では、一つのセクションは、ボリューム・データ・セット全体の約１／８〜１／４である。
【００５８】
セクション化の他の利点は、ボリューム・メモリー・モジュール内の全記憶容量より大きいボクセル・データセットをレンダリングすることにある。これは、一度に一つのセクションづつボクセル・データセットをレンダリングすることによって、行うことができる。より早いセクションをレンダリングして、それらのデータをもはや必要としなくなった後に、後のセクションをボリューム・メモリー・モジュール内にロードする、そしてより早いセクションを書き込み過ぎる。それから後のセクションを処理する、一方他のセクションをロードする。このように、大きいボリューム・データ・セット全体がレンダリングしている間により小さなボリュームメモリーを通って通過する、そして結果として生ずる画像を外部メモリー・モジュール内に蓄積することができる。このように処理できる最も大きなボリューム・データ・セットのサイズは、外部メモリー・モジュールの記憶容量によってのみ制限される。
【００５９】
隣接する処理パイプライン・チップを相互に接続するために要するピン数に関して、これらは半導体デバイスのコストの重要な成分を表す。Ｃｕｂｅ−４アルゴリズムは、隣接パイプライン間に情報を伝送するために数百のピンを必要とする。これらのピンは、ボクセル値、いくつかのボクセルから計算した値、および各光線の特性の部分蓄積を運ぶ。
【００６０】
Ｃｕｂｅ−４アルゴリズムにおいて、メモリーから読み込まれた各ボクセルに対してピンの各セットを横切って一つのデータ・エレメントを送信する必要がある。秒当たり１２５百万のボクセルである１２５ＭＨｚでＤＲＡＭメモリーからバースト・モードで読み込まれるボクセルでは、これは、処理パイプラインの各対間で１２５ＭＨｚで動作する数百のピンを有する回路を意味する。これは、ボリューム・レンダリング・システムを含む回路基板の設計者に対する重大な挑戦を示す。
【００６１】
本発明における解は、ブロック化アルゴリズムの副次効果、即ち隣接パイプライン間で送信するデータ量が約１／Ｂに減少することを利用することである。データは各ブロックの面上のボクセルから隣接処理パイプラインへ送信するだけに必要なので、この減少が起きる。ボクセルからブロック内部へのデータは、各ブロック内でのみ利用される。ブロック内のＢ3個のボクセルの各々に対して、そのブロックの各面上にはＢ2個のボクセルしかないことが分かる。したがって、隣のパイプラインに送信する必要がある情報の数はＢ2に比例する。この結果、パイプライン間の伝達は約Ｂ2／Ｂ3、即ち１／Ｂに減少する。この係数１／Ｂは、個々のピンに伝送されたデータの帯域幅を減らしたり、マルチプレキシングによってピン数を減らしたりするのに適用できる。注目すべきは、多数の広く知られたマルチプレキシング技術のどれもこの点に利用できることである。
【００６２】
分かることは、セクションを処理するために、前に処理されたセクションの真近に隣接するボクセルの値が利用されるということである。これらを処理されるセクションのボクセル値と数学的に結合して、セクションのエッジの近くに勾配または法線ベクトルを得、そして二つのセクション間の「欠けたポイント」の値を得る。これらの値を得る一つの方法は、前に処理したセクションのボクセル・データをボリューム・データ・セットを保持するメモリー・モジュールから直接再読み込むことである。しかし、前述のブロック化技術の結果として、ボクセル値を一度に一ブロックのバーストで読み込む。Ｂの値、ブロックのサイドのボクセル数が２より大きい場合に、セクション化機構は多過ぎるボクセルを再読み込みし、それによって時間および処理パワーをむだにする。
【００６３】
これは、Ｃｕｂｅ−４システムを改善する、即ちミニ・ブロックを利用する、およびいくつかのＤＲＡＭ製品において最小バースト・サイズは８アクセスであるという事実を利用する第四の技術へ通じる。本発明において、各ブロックをサイズ２×２×２のボクセルのミニ・ブロックにさらに分けて、またブロックの各ミニ・ブロックをボリューム・メモリー・モジュール内の連続したメモリー・ロケーションに格納する。それから、セクション化機構がボクセルを前に処理した隣接セクションから再読み込みするとき、それは、ブロック全体ではなく、それらの隣接セクションの正にその境界におけるミニ・ブロックのみを再読み込みする必要がある。この技術はボリューム・データ・セットの処理時間の約５〜７％を節約すると見積もられる、しかし実際の節約はセクションの境界の面積に依存する。
【００６４】
分かることは、本発明の明らかな簡略化はＢの値、ブロックのエッジにおけるボクセル数を２にセットするということである。このことは個々のミニ・ブロック化機構に対する必要性を不要にするように見える。しかし、この簡略化は錯覚である、なぜなら隣接処理パイプライン間のデータピン数の節約は係数１／Ｂによって決定されるからである。Ｂを２にセットした場合、この節約はたった半分、低コスト実現には不十分な値となる。したがって、半導体設計および生産の経済は、Ｂを８のようなより大きい値にセットすべきであり、そしてセクションの境界において不要なボクセルを再読み込みする時間の浪費を回避するために個々のミニ・ブロックスキームを実行すべきであることを示している。
【００６５】
要約すると、本発明による装置によってパソコンまたはデスクトップ・コンピュータにおいて実時間のボリューム・レンダリングが可能となる。ボクセル・データのブロック化を含む技術がデータを編成して、一つのブロック内のすべてのボクセルが単一のメモリー・モジュール内の連続メモリー・アドレスに保存され、それも一度に一つのボクセルというよりもブロック全体のデータを一気にフェッチする。メモリー・モジュールにＤＲＡＭを使用することによって、高容量、低コストとなり、そしてスペースが実質的に減少する。さらなる技術は、処理パイプラインにおける中間記憶の量を半導体実装にとって許容できる程度まで区分化し減少させることを含む。マルチプレクシング技術はブロック化の利点を利用して、ブロック当たりの送信必要データ量を減らし、これによってピンの数および隣接の処理モジュールを互いに接続するピンを横切ってデータを伝送する割合(速度)が減少する。ミニ・ブロック化技術は、一つのセクションと前に処理されたセクションの間の境界近くのボクセルに対してブロック全体を読み取るのを回避することによって、セクションを処理するのに要する時間を節約する。
【００６６】
【発明の実施の形態】
図１を参照すると、３次元ボリューム・データ・セット１０の２次元図が示されている。ボリューム・データ・セット１０の３次元は印刷ページに垂直なので、データセットの断面だけを図に見ることができる。ボクセルは、図中にドット１２によって示され、３次元空間において方形格子の固定ポイントで３次元オブジェクト１４のある特性を表すデータ値である。また図１には、オブジェクト１４の画像がその上に形成される２次元画像面１６の１次元図が示されている。この図では、また画像面１６の第二の次元は印刷ページに垂直である。
【００６７】
光線キャスティングの技術において、光線１８は、画像面１６のピクセル２２からボリューム・データ・セット１０を通って延びる。各光線は、その光線に沿ってサンプルポイント２０において色、明るさ、および透明度または不透明度を蓄積する。この光の蓄積は対応するピクセル２２の明るさおよび色を決定する。
【００６８】
分かることは、図１はボリューム・データ・セット１０の第三の次元と画像面１６の第二の次元は両方とも印刷ページに垂直であり、それゆえお互いに平行であることを示唆しているが、一般に、そうではないということである。画像面はボリューム・データ・セットに関していかなる方位も有することができる。そのため光線１８は３次元すべてにおいてどんな角度でもボリューム・データ・セット１０を通過する。
【００６９】
また、サンプルポイント２０はボクセル１２によって表す固定ポイントと必ずしも交差しないことが分かる。したがって、各サンプルポイントの値を隣接するボクセルの値から合成する。つまり、各サンプルポイント２０における光、色、透明、および不透明の強度を、隣接するボクセル１２の値の数学的関数によって計算する必要がある。そして各光線１８のサンプルポイント２０はもう一つの数学的関数によって蓄積されて、その光線に対応するピクセル２２の明るさおよび色が求まる。結果として生ずるピクセル２２のセットは、オブジェクト１４の視覚画像を画像面１６に形成する。
【００７０】
Ｃｕｂｅ−４システムと本発明の両方において、サンプルポイント２０の色、明るさまたは輝度、および透明度の計算を２つに分けて行う。第一に、３つの線の補間(trilinear interpolation)の数学的関数を利用して、サンプルポイント２０を隣接して囲むキュービック配置内の８つのボクセルの値の加重平均を計算する。そして得られた平均を使って、ある伝達関数によって色および不透明度または透明度をサンプルポイントに割り当てる。第二に、隣接のサンプルポイント間の差を測ることによって、各サンプルポイント２０におけるサンプル値の数学的勾配を概算する。そしてこの勾配を光計算において使用し、サンプルポイントの明るさを決定する。
【００７１】
図２は、個々の光線の処理を示す。光線１８は３次元のボリューム・データ・セット１０をある角度で通過し、ボクセル１２の近くを通る。各サンプルポイントは補間(内挿)ユニット２４によって計算され、そしてその勾配は勾配評価ユニット２６によって計算される。そしてこれらの出力を色、明るさまたは輝度、および透明度または不透明度を各サンプルに割り当てる伝達関数２８に適用する。最後に、光線のすべてに沿ったサンプルのすべてに割り当てられる色、明るさのレベル、および透明度が合成ユニット３０に適用される。合成ユニット３０はこれらの値を数学的に結合してピクセルと成し、ピクセルは結果として生ずる画像３２を画像面１６上に画く。
【００７２】
ａ)並行光線キャスティング
オブジェクトの図のいろいろなポイントを形成するために、画像面１６をボリューム・データ・セット１０に対して動かすか再配向する。あたかも映画のようにオブジェクトが動いて見えるように、ボリューム・データ・セットからの画像をいろいろな観点から十分速く再計算することは、対話式のボリューム・グラフィックスの分野の目標である。さらに、ボクセル１２をサンプル２０に変換してサンプルをピクセル２２に蓄積する数学的関数を変更して、ダイナミックに変化したり変形したりする３次元オブジェクトの様相を提供する。典型的要求は、１秒当たり３０回以上画像を再計算することができることである。
【００７３】
２５６3個のボクセルの小さなデータセットでさえも、再計算の規模が膨大となるということが分かる。したがって、光線キャスティングを行うたいていのシステムは、並行処理ユニットを利用し、多数の光線を同時にボリュームを通過させる。図３は、並行光線キャスティングを行ういくつかの可能な方法を示す。図３の(ａ)では、個々の光線１８がボリューム・データ・セット１０を通して独立に投ぜられて、前面から後部へデータセットを通ってステッピングし、進むにつれて、色、輝度、および不透明度を蓄積する。並行は、別々の光線を別々の処理ユニットに割り付けることによって達成される。例えば、「ａ」〜「ｇ」と表示された光線は、別々の処理ユニットに割り付けられて、並列に処理される。これを「光線・並行アプローチ」と称する。
【００７４】
光線・並行アプローチの問題は、異なる光線をしばしば同時に処理するのに、同じボクセル値が必要なことである。例えば、図３の(ａ)で３４と表示したボクセルは、光線「ｃ」および光線「ｄ」の両方を処理するために必要である。２つの独立な処理ユニットがそれら自身のペースで進む場合に、ボクセルを少なくとも二度ボリューム・データ・セット１０からフェッチする必要がある。一般に、個々のボクセル値はその近くを過ぎるいくつかの光線に寄与し、そしてボリューム・データ・セットの各値を、別々のプロセッサによって数回フェッチする必要がある。メモリー・モジュールからデータをフェッチすることは、データを処理するのに比較して時間がかかるので、このアプローチは遅くそして高価である。さらに、ボクセルが複数のメモリー・モジュールを横切って配信されたとしても、たいてい、いくつかのプロセッサは同じモジュールに同じ時間にアクセスしようと試みる。このように、メモリー・アクセスはボリューム・データ・セットを画像にレンダリングするのに傷害である。
【００７５】
図３の(ｂ)では、いくつかの光線をボリューム・データ・セット１０を通って並行に投ずることによって、この問題は多少とも解決され、各光線は一つの処理ユニットに割り当てられ、すべての処理ユニットはロックステップで動作する。「ビーム並行」アプローチと称するこの技術では、処理ユニットすべてが一列または「ビーム」３６のボクセルを同時にフェッチする。各処理ユニットはサンプルポイントを合成し、それがフェッチしたボクセルから、そしてその左右の隣りによってフェッチされた値から色、輝度、および透明度を計算する。そしてすべての処理ユニットは次のビームへステップを進め、各処理ユニットはそのビームの対応するボクセルを処理し、そしてその隣りと値を共有する。それから、それらは次のビームへステップを進め、そしてすべての光線がボリューム・データ・セットから現れるまで、次へ進む。ボリューム・データ・セットの前面から始まってボクセルのすべてを処理するまで、これを他のビームに対して繰り返す。
【００７６】
メモリーコンフリクトを回避するために、別々の光線のための処理ユニットは独立のメモリー・モジュールを持つ必要があり、そしてボリューム・データ・セットをメモリー・モジュールを横切って配信する必要がある。例えば、図３の(ｂ)のボクセルの垂直「スライス」３８は、各サイド上のスライスから別々のメモリー・モジュールへ割り当てられる。したがって、これのプロセッサはボクセルをそのメモリー・モジュールからフェッチでき、同時に、隣接の処理ユニットは隣接ボクセルを隣接メモリー・モジュールから同時に、メモリーコンフリクト無しにフェッチする。もちろん、処理ユニットは、「失われた」サンプルポイントを合成するためにボクセル値をお互いに共有し、法線ベクトルを計算し、そして光線をある角度でボリュームを通過させる。
【００７７】
光線が垂直スライスとだいたい平行ならば、このアプローチはよく動作する。しかし、図３の(ｃ)に示すように、ボリュームを他の方向から見た場合、ビーム並行処理は失敗する。この場合、ボクセル３６のビームと垂直スライス３８はお互いに平行である。その結果、そのビームのボクセルのすべては同じ垂直スライス中に有り、したがってそれらを同じメモリー・モジュールに格納する。このように、多数の並列プロセッサが、(そのメモリー・モジュールにクラッシング・オーバー・アクセスしないで)それらすべてに同時にアクセスするのは不可能である。
【００７８】
ある光線キャスティングは、ボリューム・データ・セットの３つのコピーを所定の時に、(各配向または主要な見る方向に対して一つのコピーを)格納することによってこの問題を解決する。一つのコピーは前面から後部へのスライス内のメモリー・モジュール間に分割され、第二のコピーは側面から側面へのメモリー・モジュール間に分割され、そして第三のコピーは上部から底部へのメモリー・モジュール間に分割される。これはボリューム・データ・セットを格納するのに要するメモリー量を３倍にするということであり、またそれはアプリケーションに負担をかけて、３つのコピーすべてをお互いに一致するようにするということが分かる。
【００７９】
ｂ)Ｃｕｂｅ−４におけるスライス・並行、光線キャスティング
図４を参照すると、ボリューム・データ・セットの３つのコピーを必要とする問題は、すべての３次元においてメモリー・モジュールを横切ってボリューム・データ・セットを同時に「スキューイング」することによって、Ｃｕｂｅ−４システムにおいて解決される。即ち、隣接ボクセルを隣接メモリー・モジュールに格納する、その結果、どの方向の光線がボリューム・データ・セットに入ろうとも、隣接光線は異なるメモリー・モジュールに割り当てられた隣接ボクセルの近くを通る。図４は、４つのメモリー・モジュールを有するシステムについて、一つの角の近くのボリューム・データ・セットの部分を詳細に示すことによって、このスキューイングを表す。図中の各ボクセルは小さなキューブ５４によって表される、そしてキューブ上のパターンは、ボクセルのメモリー・モジュールへの割り当てを示す。図から分かるように、ボリューム・データ・セットの３つの視覚面上の隣接ボクセルはことなる影をつけたパターンを有し、したがってことなるメモリー・モジュールへ割り当てられる。同じことが図４に示されないボリューム・データ・セットの３つ面、即ち３つの背面にも当てはまることが分かる。Ｃｕｂｅ−４システムの用語では、この配置は「スキューイング」と称し、それはＣｕｂｅ−４発明の本質である。
【００８０】
メモリー・モジュール間のボクセルの配置を数学的に表わすことができる。Ｐ個のメモリー・モジュールおよび処理ユニットが有る場合、ボリューム・データ・セット内の位置(Ｘ，Ｙ，Ｚ)に位置するボクセルを次の番号を付けたメモリー・モジュールに割り当てる。
【００８１】
【数１】
0004158007.tif 000002
【００８２】
ここで、ｘ、ｙとｚは３次元によってデータセット内のボクセルの位置を表わす整数であり、記号「ｍｏｄ」は左側の数量を右側の整数によって割って剰余のみを保持する数学的演算を表わす。即ち、ボクセルの３つの位置座標を積算し、メモリー・モジュール数Ｐによって割り、そして剰余を保持する式(１)によって、メモリー・モジュール番号を得ることができる、この剰余の値は０〜(Ｐ−１)である。通常、ボクセルのｘ、ｙとｚ座標はデータセットの指定された隅から計算されるが、ある指定されたポイントから計算することも、一般性を失うことなく可能であり、このポイントは「原点」と呼ばれる。
【００８３】
式(１)から分かることは、ボリューム・データ・セットの３次元の各々を通して各スライスのボクセルは、まったく同じようにメモリー・モジュールを横切ってスキューされ、しかし異なるメモリー・モジュールで始まるということである。したがって、スライスの一つが図４のボリューム・データ・セットのどれかの面から剥がれたとするなら、それはそのすぐ後の同じ色または影のついた、しかし一つのボクセルだけシフトされたパターンを有するスライスを表わす。さらに、分かることは、特定のメモリー・モジュールのボクセルは、同じ２つの他のモジュールのボクセルによっていつもくくられる、一つのサイドに一つのモジュール、そして他のサイドに一つのモジュール。このように、メモリー・モジュールに関連する特定の処理ユニットはきっちりと２つの隣りを有するということである。
【００８４】
この編成は光線のキャスティングを並行する能力に大きな影響を及ぼす。Ｐ本の光線のグループをボリューム・データ・セットのどの面を通してもどの方向にも投ずることができる、そしてそれらをいつもメモリーコンフリクト無しに並列に処理することができる。各処理ユニットはそれ自体のメモリー・モジュールからその光線近くのボクセルをフェッチし、その結果、Ｐ個の隣接ボクセルを同時にフェッチする。このように、スキューされたメモリー編成によって、ボリューム・データ・セットをどの見る方向からもレンダリングする完全な並行が可能となる。
【００８５】
図５と６を参照すると、Ｃｕｂｅ−４システムはボリューム・データ・セットを一度に一スライスづつレンダリングし、すべての光線をそのスライスを通して投じ、そして、つぎのスライスに進む前に、そのスライス内のすべてのサンプルポイントの視覚特性を蓄積する。この技術は「スライス並行」レンダリングと称する。図５は、ボリューム・データ・セットのスライス５５の面に入る多数の光線１８を示す。分かることは、実際には、この簡単な図で示したよりずっと多くの光線があるということである。
【００８６】
スライス並行技術では、スライス５５に入る各光線１８が部分的にレンダリングされる。つまり、各光線の色、明るさ、および透明度を含む視覚特性をスライス５５で利用できるデータから可能なかぎり割り当てる。光線のすべてがスライス５５から視覚特性を蓄積した後でだけ、Ｃｕｂｅ−４システムは剥がれ、スライスとステップが次のスライス５６に進む。メモリーを横切ってボクセルをスキューするので、スライス５６はスライス５５と同一であるが、そのメモリー・モジュールは一つのボクセルだけシフトして割り当てられる。
【００８７】
図６は、Ｃｕｂｅ−４システムでボクセルをフェッチする実際の順序を示す。この図で、Ｐは４と仮定する、そして４つのメモリー・モジュールと４つの処理パイプラインがある。ボクセル５４をＰ個のボクセルのグループ５８においてスライスの上部の列からフェッチする。それは上方左隅から始まる。一度これらのＰ個のボクセルが処理パイプラインに挿入されると、同じ列から次のＰ個のボクセルがフェッチされ、そしてその列が完了するまで次々とフェッチされる。それからシステムは次の列へステップダウンし、その列がまた完了するまでＰ個のボクセルのグループでフェッチする。この処理は、スライス５５のすべての列に対して、その列が完了するまで繰り返される。それから処理は次のスライス５６へ、またその上方左隅から始まるＰ個のボクセルのグループにおいて続く。
【００８８】
Ｃｕｂｅ−４アルゴリズムの変種は他の隅または他の指定ポイントで始まる処理で可能であるが、しかしそれは、スライスのビームを通して一度にＰ個のボクセルのグループ内を、そしてボリューム・データ・セットを通していつも進むことが分かる。
【００８９】
図７は、先行技術によるＣｕｂｅ−４システムの理想化したブロック図であり、処理要素とメモリー・モジュールの相互接続を示す。図７で、多数の処理パイプライン４０は、各々それら自体のボリューム・メモリー・モジュール４２に結合される。処理パイプライン４０は、多数の通信チャンネル４４を経由してお互いに結合されて、各通信チャンネルは、２つの処理パイプライン間のいずれの方向にもデータを伝送する手段を提供する。処理要素の出力４６は、レンダリングされた画像をコンピュータ画面のようなディスプレィ面５０に伝達する目的で、バスまたは他の機構４８に結合される。入力ボクセルを、各モジュールに結合される入力バス５２を経由してボリューム・メモリー・モジュール４２に書き込む。
【００９０】
図７から分かることは、いかなる「第一の」または「マスター」処理パイプラインもないということである。すべてのパイプラインは等しいステータスを有し、お互いにロックステップで動作する。
【００９１】
図８は、パイプライン間の通信チャンネルのより詳細な図とともに、Ｃｕｂｅ−４処理パイプラインの内部要素のブロック図を示す。図には、５つの処理パイプライン４０が、説明の目的のためだけに並んで配置される。即ち、図の最も右の処理ユニットは最も左の処理ユニットに接続されて、システム全体が図７のような処理ユニットのリングを形成する。図８で、各メモリー・モジュール４２は、それ自体のパイプラインのＦＩＦＯ記憶ユニット６０および３つの線の補間ユニット６２に結合される。メモリー・モジュール４２は、通信ライン４４を経由して、左方の２つの隣りのパイプラインの３つの線の補間ユニット６２に、そして右方の１つの隣りのパイプラインの３つの線の補間ユニット６２に結合される。ＦＩＦＯ記憶ユニット６０は、それ自体の処理パイプライン内の一つの３つの線の補間ユニット６２に、そして通信ライン４４を経由して、左方の隣りの処理パイプライン内の一つの３つの線の補間ユニット６２に、そして右方の２つの隣りのパイプラインの各々内の３つの線の補間ユニット６２に結合される。これらの接続によって、各処理パイプライン４０はサンプルポイント２０を８つの取り囲むボクセルから合成できる。ＦＩＦＯ記憶ユニット６０は、一つのビームから次のビームへ、そして一つのスライスから次のスライスへのボクセル値のコピーを保持するのに必要な内部記憶装置を与えるファーストイン、ファーストアウト記憶回路である。
【００９２】
３つの線の補間ユニット６２は、ＦＩＦＯ記憶ユニット６４とシェーダーユニット６６の両方に結合される。ＦＩＦＯ記憶ユニット６４はそれ自体のパイプラインのシェーダーユニット６６に、そして通信ライン４４を経由して右方の２つの隣りのパイプラインのシェーダーユニット６６に結合される。また、パイプラインのシェーダーユニット６６は、通信ライン４４を経由していずれかの側における最近隣のパイプラインのシェーダーユニット６６に、そしてまた右方の第二の隣りのパイプラインのシェーダーユニット６６に結合される。
【００９３】
シェーダーユニット６６の出力は合成ユニット６８に結合されて、また通信ライン４４を経由して左方の隣りのパイプラインの合成ユニット６８に、そして右方の３つの隣りのパイプラインのシェーダーユニット６６に結合される。
【００９４】
Ｃｕｂｅ−４システムの詳細な動作が、通信ライン４４を横切る信号の説明とともに、Hanspeter Pfisteｒによる前述の博士論文、そしてまたUrs KanusとMichael Meissnerによる修士論文「Cube-4, a Volume Rendering Architecture for Real-time Visualization of High-resolution Volumetric Datasets」(Eberhard- Karls大学、チューリンゲン、独、１９９６年９月３０日)に述べられている。一般に、Ｐ個のボクセルはメモリー・モジュール４２からフェッチされ、そして多数の３つの線の補間ユニット６２に送られ、サンプル２０を合成する。各サンプルはそれを囲む８つのボクセルから合成し、これらのボクセルは隣接する列と隣接するスライス内にあるので、いくつかのボクセル値を、他のものがフェッチされるのを待つために、「保留」または遅らせる必要があるということが分かる。この遅延はＦＩＦＯ記憶ユニット６０によって与えられる。一度サンプル２０が合成されると、それらは勾配が計算されるシェーダーユニット６６に送られる。
【００９５】
各勾配は、そのいずれかの側のサンプル値に、その上下のサンプルに、その前後のサンプルに依存する。いくつかのサンプルを他より前に計算し、そうしてより早いサンプル値を、ちょうどボクセル値のように、保留または遅らせる必要があることが分かる。ＦＩＦＯ記憶ユニット６４は、２つの遅延レベル、単一のスライスに対して一つのレベル、そして第二のスライスに対して一つのレベルを与える。
【００９６】
最後に、勾配が計算された後に、サンプルの色、明るさ、および透明性を計算できる。これらの視覚特性を合成ユニット６８に送り、そこでそれらは、前に処理したボクセルとサンプルに対して夫々の光線にすでに蓄積された色、明るさのレベル、および透明性と結合する。光線がある角度でボリューム・データ・セットを通過し、その結果、それがボクセルの近くでスライスから現れたときに、それは９つのボクセルのどれかの近くの次のスライスに入るということが分かる。これらの９つのボクセルは５つ位のメモリー・モジュールに渡ってスキューされる。したがって、一部蓄積された光線の値を５つの処理パイプライン４０と合成ユニット６８のどれかに、見る方向に依存して、追加のスライスの色、明るさ、および透明度の連続蓄積のために、送る必要がある。
【００９７】
一つの光線が完成すると、それをピクセルバス４８を経由して表示するために画面に送る。
【００９８】
ｃ)Ｃｕｂｅ−４におけるメモリー・アクセス速度の制限
ボクセルのメモリー・モジュールへの割り当てをより詳細に見ると、ボクセル値をスライス並列処理中にメモリーからフェッチする順序を見ることができる。ボリューム・データ・セットが合計Ｎ3個のボクセルを有するように、ボリューム・データ・セットを各エッジにＮ個のボクセルを有するキューブとして編成する場合に、そしてＮがＰで割り切れる場合に、Ｃｕｂｅ−４システムのそのメモリー・モジュール内の各ボクセルのアドレスは次の数式によって与えられる。
【００９９】
【数２】
0004158007.tif 000003
【０１００】
ここで、ｘ、ｙとｚはボリューム・データ・セットの隅またはなにか他の原点に対するボクセルの整数座標であり、記号［ｘ／Ｐ］は、整数ｘを数Ｐで割り剰余を切り捨てた結果である。
【０１０１】
図９は、４に等しいＰに対する各ボクセルのメモリー・アドレスとともに、図４のＸＹ面上のボクセルのシェーディングを示す。図から分かることは、どの列内でも、Ｐ個の隣接するボクセルのグループは個々のメモリー・モジュール内に同じメモリー・アドレスを有するということである。さらに、処理ユニットがＣｕｂｅ−４アルゴリズムにしたがって連続してボクセルをフェッチする場合に、それは同じ列から同じシェーディングの連続するボクセルをフェッチする。図９から分かることは、これらのボクセルはそれらのメモリー・モジュール内に連続するメモリー・アドレスを有するということである。より一般的に、式(２)から認識したいことは、ＸＹ面に平行なボリューム・データ・セットのどのスライスに対しても、連続するボクセルは連続するメモリー・アドレスを有するということである。理論上、見る方向は光線がボリュームのＸＹ面に入るようであるなら、これらのボクセルをより速くフェッチするためにバースト・モードのＤＲＡＭモジュールを使用することは可能である。
【０１０２】
しかし、図１０は、４に等しいＰを有する同じボリューム・データ・セットのＹＺ面上のボクセルへのメモリー・アドレスの割り当てを示す。この面上、図から分かることは、同じ列内に同じシェーディングを有する連続するボクセルは、それらのメモリー・アドレスで量Ｎだけ異なるということである。さらに、所定のシェーディングを有する列の最後のボクセルと同じシェーディングを有する次の列の最初のボクセルは、それらのメモリー・アドレスで量３×Ｎ＋４だけ異なる。したがって、ＹＺ面に入る光線に対して連続するボクセルをフェッチするためにバースト・モードのＤＲＡＭモジュールを使用することは可能ではない。Ｃｕｂｅ−４アルゴリズムにしたがってボクセルをフェッチする処理ユニットは、それらを通常モードでフェッチするのに限定される、即ち、バースト・モードではなく、そしてランダムにメモリー・ロケーションをフェッチしているかのごとく遅いデータ速度で限定される。
【０１０３】
式(２)から認識したいことは、ＺＸ面において、同じシェーディングを有するどの列の連続するボクセルもそれらのメモリー・アドレスでＮ2だけ異なるということである。したがって、バースト・モードはこの面に入る光線を処理するのに適用できない。
【０１０４】
より一般的に、ボリューム・データ・セットが寸法Ｌ、Ｍ、およびＮを有する方形の固体である場合に(ここで、Ｌ、Ｍ、およびＮは各々Ｐで割り切れる)、それは合計Ｌ×Ｍ×Ｎ個のボクセルを有する。Ｃｕｂｅ−４システムにおける各ボクセルのアドレスは次式によって与えられる。
【０１０５】
【数３】
0004158007.tif 000004
【０１０６】
式(１)および式(２)から分かることは、ＸＹ面上に同じシェーディングを有する列内の連続するボクセルは連続するメモリー・アドレスに格納されるが、ＹＺ面上に同じシェーディングを有する列内の連続するボクセルはＬだけ異なるアドレスに格納されるということであり、そしてＺＸ面上に同じシェーディングを有する列内の連続するボクセルはＬ×Ｍだけ異なるアドレスに格納されるということである。このように、光線がＸＹ面に入る場合にボクセルのフェッチングをスピードアップするのにバースト・モードを使用することができる、しかしそれらがＹＺまたはＺＸ面に入る場合にそれは使用できない。
【０１０７】
ｄ)ブロック化およびバースト・モードＤＲＡＭの利用
図１１を参照すると、ボクセルを連続するメモリー・アドレスからフェッチできる方法でボクセルをグループに分けるために、見る方向にかかわらず、本発明はブロック化と称する技術を利用する。そうすることによって、すべての見る方向に対してＤＲＡＭモジュールからボクセルにアクセスするためにバースト・モードを使用することが可能となる。この技術では、ボクセルをサブキューブまたはブロック７０に編成し、そして個々のボクセルをスキューするよりもむしろブロックをメモリー・モジュールを横切ってスキューする。図中のブロックのシェーディングはそれが格納されるメモリー・モジュールを示し、そのブロックのボクセルのすべてがその同じメモリー・モジュールに格納される。
【０１０８】
特に、各ブロックがそのエッジの各々に沿ってＢ個のボクセルを有する場合に、ボクセルの座標(ｘ，ｙ，ｚ)への割り当ては次式によって与えられる。
【０１０９】
【数４】
0004158007.tif 000005
【０１１０】
ここで、Ｐはメモリー・モジュールと処理ユニットの数であり、ｘ、ｙとｚは３次元の各々におけるボリューム・データ・セットの隅または他の原点に対するボクセルの整数座標である。つまり、ボクセル(ｘ，ｙ，ｚ)が割り当てられるメモリー・モジュールを、各座標をＢで割り、剰余を切り捨て、これら３つの割り算の和をとり、そしてその和をＰで割り、剰余をとることによって決定することができる。これは、ＤＩＶ2Ａシステムの前述の説明でLichtermanによって書かれたのと同じ式である。
【０１１１】
ブロックは、ボクセルがＣｕｂｅ−４システムにおいて番号をつけられたと同じように本発明でボリューム・データ・セット内で番号をつけられ、それは隅または他の原点から３次元の各々におけるブロックをカウントすることによって行う。式(４)から分かることは、位置(ｘ，ｙ，ｚ)におけるボクセルは、次式によって与えられるブロック座標(ＢX，ＢY，ＢZ)を有するブロックに格納されるということである。
【０１１２】
【数５】
0004158007.tif 000006
【０１１３】
ボリューム・データ・セットがＮ3個のボクセルを有するキューブを表わし、そしてＰ×ＢがＮ(キュービックデータセットの一つのサイドにおけるボクセル数)を割り切れる場合に、そのメモリー・モジュール内に座標(ＢX，ＢY，ＢZ)を有するブロックのスターティングアドレスは次式によって与えられる。
【０１１４】
【数６】
0004158007.tif 000007
【０１１５】
各ブロック内に、ボクセルは連続するメモリー・アドレスに格納される。ブロック内のボクセルの多くの実行可能な配置が可能であるということが分かる。ある実施の形態では、ブロックの頭の部分に関するボクセルメモリー・アドレスは次式によって与えられる。
【０１１６】
【数７】
0004158007.tif 000008
【０１１７】
即ち、そのブロック内のボクセル(ｘ，ｙ，ｚ)の位置を、Ｂで割った後にｘ，ｙ，およびｚからの剰余をとり、そしてｘからの剰余をｙからの剰余のＢ倍に加え、そしてそれをｚからの剰余のＢ2倍に加えることによって見つけることができる。認識したいことは、式(７)はＢ3個の範囲のメモリー・アドレスを有する連続するロケーションを表わすということであり、ここでＢ3はブロック内のボクセル数である。
【０１１８】
図１２に、本発明の一実施の形態による実時間ボリューム・レンダリング装置における処理モジュールであるパイプラインプロセッサ(処理パイプライン)４０をその関連メモリー・モジュール４２とともに示す。Ｃｕｂｅ−４と同様に、図７に示したように、本発明は、リングに接続された多数の処理パイプライン(処理モジュール)４０とメモリー・モジュール４２から成る。再び図１２を参照すると、メモリー・モジュール４２を二つのブロックバッファ７２に結合する、その各々はＢ3個のボクセルを格納する容量を有する。ここでＢはブロックのエッジ上のボクセル数である。各ブロックバッファ７２を、補間ユニット８２と二つのトライステートインタフェース７４の両方に結合する。各トライステートインタフェース７４をボクセル通信ライン７６に結合し、一つを、リングのまわりに時計方向の最近隣のパイプライン４０に結合し、そして他の一つを、リングのまわりに反時計方向の最近隣のパイプラインに結合する。
【０１１９】
電子設計では、トライステートインタフェースは入力または出力インタフェースのいずれとしても機能することが分かる。特に、この実施の形態の半導体実装において、トライステートインタフェース７４を通信ライン７６に接続するピンは、入力および出力ピンの両方である。したがって、各ボクセル通信ライン７６はいずれの方向にもデータを運ぶことができる。そのため処理パイプライン４０は、その至近隣のいずれからもデータを受け取ったり、伝送したりできる。この実施の形態では、両方のボクセル通信ライン７６はリングのまわりに同じ方向にデータを運ぶ、つまり、いずれも時計方向に信号を送るように構成され、または両方とも所定のときに反時計方向に信号を送るように構成される。
【０１２０】
また、トライステートインタフェース７４を、ビームＦＩＦＯ記憶ユニット７８、スライスＦＩＦＯ記憶ユニット８０、および随意遅延ユニット７３に結合する。ビームＦＩＦＯ記憶ユニット７８、スライスＦＩＦＯ記憶ユニット８０、および随意遅延ユニット７３すべてを、補間ユニット８２に結合する。幅がＬボクセル、高さがＭボクセル、そして奥行きがＮボクセルであるボリューム・データ・セットをレンダリングするために、ビームＦＩＦＯ記憶ユニット７８をＬ÷(Ｂ×Ｐ)要素を保持するように構成する、ここで各要素は(Ｂ＋１)2ボクセルのアレイである。同様に、ＦＩＦＯ記憶ユニット８０を(Ｌ×Ｍ)÷(Ｂ2×Ｐ)要素を保持するように構成する、ここで各要素はＢ×(Ｂ＋１)サンプルのアレイである。随意遅延ユニット７３を、Ｂ2ボクセルを保持して、パイプラインがその部分ビームの左端にあるかどうかに依って、それらをゼロファンダメンタルサイクルまたはＢ3ファンダメンタルサイクル遅延させるように構成する。以下に示すように、ビームおよびスライスＦＩＦＯ記憶ユニット７８と８０は、処理しつつあるブロックの直ぐ上と前から送られたボクセルを夫々保持する。随意遅延ユニット７３は、直ぐ左のパイプラインから送られたボクセルを保持する。
【０１２１】
補間ユニット８２は、囲んでいるボクセルにもとづいてサンプルポイントの値を計算する。一般に、Ｂ3サンプルポイントを計算するために、(Ｂ＋１)3ボクセル値が必要である。これらは、メモリー・モジュール(ボクセルメモリ)４２からブロックバッファ７２に読み込まれたＢ3ボクセル、随意遅延ユニット７３からのＢ2ボクセルのアレイ、ビームＦＩＦＯ記憶ユニット７８からの(Ｂ＋１)2ボクセルのアレイ、およびスライスＦＩＦＯ記憶ユニット８０からのＢ×(Ｂ＋１)ボクセルのアレイから得られる。
【０１２２】
補間ユニット８２を、勾配評価・シェーディングユニット９２とトライステートインタフェース８４に結合する。トライステートインタフェース８４をサンプル通信ライン８６に結合し、そして次にそれらを時計方向および反時計方向にある最近隣のパイプラインに夫々結合する。ボクセル通信ライン７６と同様に、サンプル通信ライン８６は双方向であり、そしてリングまわりのいずれの方向にもサンプル・データを運ぶ。また、トライステートインタフェース８４を、ビームＦＩＦＯ記憶ユニット８８、スライスＦＩＦＯ記憶ユニット９０、および随意遅延ユニット８３に結合する。随意遅延ユニット８３およびビームとスライスＦＩＦＯ記憶ユニット８８と９０すべてを、勾配評価・シェーディングユニット９２に結合する。
【０１２３】
幅がＬボクセル、高さがＭボクセル、そして奥行きがＮボクセルであるボリューム・データ・セットをレンダリングするために、ビームＦＩＦＯ記憶ユニット８８をＬ÷(Ｂ×Ｐ)要素を保持するように構成する。ここで各要素は２×(Ｂ＋２)2サンプルのアレイである。同様に、ＦＩＦＯ記憶ユニット９０を(Ｌ×Ｍ)÷(Ｂ2×Ｐ)要素を保持するように構成する。ここで各要素は２×Ｂ×(Ｂ＋２)サンプルのアレイである。随意遅延ユニット８３を、パイプラインがその部分ビームの左端にあるかどうかに依って、ゼロファンダメンタルサイクルまたはＢ3ファンダメンタルサイクルの遅延を行うためにＢ2サンプル値を保持するように構成する。以下に示すように、ビームおよびスライスＦＩＦＯ記憶ユニット８８と９０は、処理しつつあるブロックの直ぐ上と前から送られたサンプルを夫々保持する。随意遅延ユニット８３は、直ぐ左のパイプラインから送られたサンプルを保持する。
【０１２４】
勾配評価・シェーディングユニット９２を、合成ユニット１０２に直接結合する。合成ユニット１０２を、トライステートインタフェース９４に結合し、そして次にそれらを合成要素通信ライン９６に結合する。ボクセル通信ライン７６やサンプル通信ライン８６のように、合成要素通信ライン９６は、リングまわりの時計方向および反時計方向の各々における最近隣のパイプラインへの双方向通信ラインである。また、トライステートインタフェース９４はビームＦＩＦＯ記憶ユニット９８、スライスＦＩＦＯ記憶ユニット１００、および随意遅延ユニット９３に結合する。ビームＦＩＦＯ記憶ユニット９８、スライスＦＩＦＯ記憶ユニット１００、および随意遅延ユニット９３すべてを合成ユニット１０２に結合する。最後に、合成ユニット１０２をピクセル出力バス４８に結合し、そして次にそれをコンピュータ画面のような画面に結合する。
【０１２５】
幅がＬボクセル、高さがＭボクセル、そして奥行きがＮボクセルであるボリューム・データ・セットをレンダリングするために、ビームＦＩＦＯ記憶ユニット９８をＬ÷(Ｂ×Ｐ)要素を保持するように構成する。ここで各要素は部分的に蓄積された光線の(Ｂ＋１)2ピクセル値のアレイである、つまり、視覚特性は色、不透明度、および奥行情報を含む。同様に、スライスＦＩＦＯ記憶ユニット１００を(Ｌ×Ｍ)÷(Ｂ2×Ｐ)要素を保持するように構成する。ここで各要素は部分的に蓄積された光線のＢ×(Ｂ＋１)ピクセル値のアレイである。随意遅延ユニットを、ゼロファンダメンタルサイクルまたはＢ3ファンダメンタルサイクルの遅延を行うために部分的に蓄積された光線のＢ2ピクセル値を保持するように構成する。以下に示すように、ビームおよびスライスＦＩＦＯ記憶ユニット９８と１００は、処理しつつあるブロックの直ぐ上と前から前送りされた部分的に蓄積された光線のピクセル値を夫々保持する。随意遅延ユニット９３は、直ぐ左のパイプラインからの部分的に蓄積された光線のピクセル値を保持する。
【０１２６】
換言すれば、本発明のこの実施の形態において、処理ユニット４０は、パイプライン方式でともに接続される４つの主要機能段、即ち、ブロックバッファリング段、補間段、勾配評価・シェーディング段、および合成段から成る。各段を、一対の隣接するパイプラインへの双方向通信ラインによって、そして前のビームと前のスライスから送られた値を保持できるビームおよびスライスＦＩＦＯ記憶ユニットによって、次の段から分離する。
【０１２７】
ｅ)作動方法
次に、本発明のこの実施の形態の作動方法について説明をする。図１３を参照すると、観察方向が決定される。単一の光線１１０がボリュームデータ集合を通して観察方向から、即ちイメージ１６から、垂直に投射され、この光線は観察面(the view surface)に最も近くて該面に対して殆ど垂直な面１１２の中心に当たる。一般に、光線は面１１２の法線ベクトルから、即ち面１１２に対して垂直な直線から、４５度未満の角度１１６をなして観察面に当たる。角度１１６がもし４５度より大きければ、ボリュームデータ集合のうちの異なる面の方がもっと近くなり、光線１１０に対してもっと垂直に近くなる。法線ベクトル１１４に対する角度１１６がもし正確に４５度であれば、その２つの観察面のいずれを選んでもよい。更に、光線１１０がボリュームデータ集合のコーナーに当たったならば、角度１１６は３つの法線ベクトルのいずれからも４５度となり、その３つの面のいずれを選んでもよい。
【０１２８】
面１１２を選択した後、光線１１０をその面上に投射して該光線の”影”１１８を作る。一般に、この影はその面の４個の象限のうちの１つに着く。影１１８を含む象限１２０は選択された象限となる。もし影１１８が２つの象限の間の線上に着いたならば、いずれの象限を選択してもよい。影１１８が正確に面１１２の中心点であるならば、光線１１０は該面に対して垂直であり、どの象限を選択してもよい。
【０１２９】
面１１２の象限１２０を選択した後、面１１２が”前(front)”に位置して象限１２０が左上のコーナーに位置することとなるようにボリュームデータ集合を３次元で回転させることができる。ボリュームデータ集合を”回転”させるときには、どのデータも動かす必要はない。適当な変換マトリックスをボクセル及びブロック座標にかけて、それらの座標を、選択された象限が原点となっていて前面の左上コーナーに位置しているような座標系へ並進させることができる。変換マトリックスの理論は、Ｊ．フォーリー等の前述の参考文献を含むグラフィックスの教科書で説明されている。
【０１３０】
以下の解説では、ボリュームデータ集合自体に対する座標はｘ、ｙ、ｚで表され、選択された象限１２０に対する座標はｕ、ｖ、ｗで表される。これらは”レンダリング座標”と称される。”左”、”右”、”上”、”下”、”後”、及び”前”という用語はレンダリング座標に関して下記のように定義される：
【０１３１】
”左”                         ”ｕの値が減少してゆく方向”
”右”                         ”ｕの値が増大してゆく方向”
”上”及び”頂点(top)”        ”ｖの値が減少してゆく方向”
”下”及び”底(bottom)”       ”ｖの値が増大してゆく方向”
”前(front)”                  ”ｗの値が減少してゆく方向”
”後(back)”                   ”ｗの値が増大してゆく方向”
【０１３２】
更に、レンダリング座標におけるボリュームデータ集合の前の、左の、頂部のコーナーは、”原点”即ち(ｕ，ｖ，ｗ)＝(０，０，０)の座標を有するボクセル、と称される。レンダリング座標では、光線は、面に対して偶発的に垂直にならない限りは、常に前から後へ、下方右向きにボリュームを通る。
【０１３３】
式(４)におけるブロック・スキューイングの定義から分かるように、特定の隣接するパイプラインに付される”左”、”右”、”上”、”下”、”前”及び”後”という用語は、観察方向によって決まる。１つの観察方向について、前、左、及び上のパイプラインは全て図７において反時計回り方向のパイプラインであり、他の観察方向ではそれらのうちの一部又は全部が図７において時計回り方向のパイプラインである。
【０１３４】
本発明の本実施の形態では、処理順序は、それが個々のボクセルではなくてブロックを指していることを除いて、正確に図６のそれと同じである。即ち、処理はレンダリング座標の原点から始まって、ブロックの各ビームを横断してＰ個のブロックのグループ中を左から右へ進み、１ビームずつスライス・ブロックを下リ、次に該ボリュームの前から後へ１スライスずつ進む。処理パイプラインがＰ個のブロックのグループずつボリュームを横切ってゆくとき、光線は常になお処理されるべき方向に、即ち、後、下方、又は右の方向にブロックから出てゆく。全ての場合に、既に処理されたデータは、現在処理されているブロックの上、前、及び左から生じる。
【０１３５】
図１２をもう一度参照すると、本発明の本実施の形態における基本処理サイクルはＤＲＡＭメモリーから１ボクセルをバースト・モードで読み出すサイクルタイムである。これらの基本サイクルは、各々Ｂ3個の基本サイクルのブロック・サイクルにグループ分けされる。ブロック・サイクルの始めにメモリー・モジュール４２の連続するアドレスからＢ3個のボクセルが取り出され、これが、考察しているブロックの始めから始まってＢ3個の基本サイクルの間継続して行われる。ボクセルは２つのブロック・バッファー７２のうちの１つに取り込まれる。次のブロック・サイクルの間、これらのＢ3個のボクセルが処理されると同時にＢ3個のボクセルの新しいブロックが他方のブロック・バッファー７２に取り込まれる。次のブロック・サイクルの間、普通の”ダブル・バッファーリング”技術が適用されて、その２個のバッファーの役割は再び逆にされる。
【０１３６】
次に図１４を参照する。Ｃｕｂｅ−４及び本発明の両方において、光線１８同士の間隔は、結像面１６上のピクセル２２によって決定されるのではなくてベース・プレーン１３２上のベースピクセル１３０によって決定される。図１４は、図１と同様に３次元ボリュームデータ集合の２次元図解と結像面とを示している。図１４の”ベース・プレーン”は、ボリュームデータ集合の選択された面１１２に平行でレンダリング座標における原点(ｕ，ｖ，ｗ)＝(０，０，０)を通る数学的平面である。ベース・プレーン１３２の”ベースピクセル”１３０は、面１１２上のボクセルと完全に重なり合っていて、ボクセルと同じ間隔で全ての方向に延在している。光線１８は、結像面１６に垂直でベース・プレーン１３２のベースピクセル１３０のまさに中心を通る方向に投射される。得られたイメージは結像面にではなくてベース・プレーンで表現(レンダリング)される。一般に、ベースピクセルを通る光線は結像面１６のピクセル２２と正確には１列に並ばない。従って、ベース・プレーンのイメージを最終のイメージに”ゆがめる(warp)”後処理が必要である。
【０１３７】
互いに平行な光線１８については、標本点は、それらがベース・プレーンに平行な同一の平面内にあるときには常に、それらの隣接ボクセルから同じ距離だけずれる。そのためにＣｕｂｅ−４アルゴリズムが相当単純になる。具体的には、それは、隣り合う標本点が８個の隣接ボクセルの隣接するグループに囲まれることを意味し、その２個の標本点は、その８個のうちの４個を分け合う。
【０１３８】
次に、本実施の形態の動作中の、パイプライン間でのデータの流れについて説明する。始めに、ブロックのＢ3個のボクセルと、隣接するパイプラインから送られてきた他のボクセルとから、光線１８に沿うＢ3個の標本値のアレイが計算される。標本は、それに最も近いボクセルから補間されるので、Ｂ3個の標本を作るには(Ｂ＋１)3個のボクセルのアレイが必要である。第２に、Ｂ3個の勾配のアレイが計算されるとともに、色、輝度又は明暗のレベル、及び透明度を表すピクセル値が与えられる。１つの標本の勾配を見積もるにはその標本の全ての側の標本の値が必要なので、Ｂ3個の勾配とピクセル値とを作るには合計で(Ｂ＋２)3個の標本が必要である。最後に、そのＢ3個のピクセル値を前に蓄積されたピクセル値と合成して、部分的に表現(レンダリング)された光線を形成する。そのために、ブロックを通る光線の視覚的特性を蓄積するために(Ｂ＋１)3個のピクセル値のアレイも必要である。
【０１３９】
図１５は、パイプラインがＢ3の標本点のブロックを計算するために必要とする(Ｂ＋１)3個のボクセルの３次元アレイの３つの図を示している。図１５の(ａ)は、０より大きい値のｗ(ｗ＞０)についてのアレイ、即ちアレイの前面を除く全てのボクセル、の横断面を表している。図１５の(ｂ)は、該アレイの右面を表している。図１５の(ｃ)は、該アレイの下方、前方、右側から該３次元アレイを斜めに見た図である。
【０１４０】
図１５の立方体アレイのボクセルは４つの出所から生じる。Ｂ3個のボクセルのブロック１４０はボリューム・メモリーからブロック・バッファ７２に取り込まれる。Ｂ2個のボクセルのアレイ１４２は、現在のブロックの左側のパイプラインから通信ライン７６と随意遅延ユニット７３とを介して送られる。(Ｂ＋１)2個のボクセルのアレイ１４４はビームＦＩＦＯ記憶ユニット７８の出力側から取り出され、Ｂ×(Ｂ＋１)個のボクセルのアレイ１４６はスライスＦＩＦＯ記憶ユニット８０の出力側から取り出される。ボクセルのこれら４個のグループの合計は(Ｂ＋１)3個である。図において×印で表されているＢ3個の標本のアレイ１５０は、３線補間法又はその他の数学的関数によって計算される。一般に、このプロセスにより計算されたＢ3個の標本のアレイ１５０は、ブロック・バッファ７２を介してボリューム・メモリー・モジュール４２から最初に取り出されたＢ3個のボクセルのアレイ１４０から左、前、及び上にずれている。そのずれの量は、常にボクセル間の間隔よりは小さくて、観察方向がレンダリング座標の軸の１つに垂直である場合には、このずれの量は０になることがある。
【０１４１】
Ｐ個の処理パイプラインが並列に動作するので、ボクセル・アレイ(ブロック)１４２は、一般に、直ぐ左側で現在処理されているＢ3個のボクセルのブロックの右面である。従って、ブロックのボクセルがブロック・バッファー７２に取り込まれるとき、その最も右側のＢ2個のボクセルは直ちに右側の処理エレメントに送られて随意遅延ユニット７３に入れられ、その後に補間ユニット８２に送られなければならない。この送りは、ブロック１４０の左端の標本点１５０を計算するためにボクセルが必要になる前に完了しなければならない。例外は、ブロック１４０が部分ビームの一番左のブロックであるときである。この場合には、その左側のブロックがその前のブロック・サイクルで読まれているのでボクセルのアレイ(ブロック)１４２を１ブロック・サイクル即ちＢ3個の基本サイクルだけ遅延させる必要がある。この遅延は図１２において随意遅延ユニット７３で表されている。パイプラインがその部分ビームの左端にある場合には遅延値はＢ3サイクルにセットされるが、その他の場合には遅延値は遅延が全く無いことを意味する０にセットされる。
【０１４２】
右側の処理パイプラインによって直ぐに使用されるブロック１４０の一番右の面を送る他に、ブロック１４０の下及び背後の処理パイプラインのためにアレイも用意される。ここで図１６を参照すると、アレイ２４２はアレイ１４２によく似ている。これは次のビームを処理するときに、即ちＬ÷(Ｂ×Ｐ)ブロック・サイクル後に、必要になる。このアレイは、ブロック１４０の底面と、アレイ１４２の底の行と、アレイ(ブロック)１４６の底の行とから形成される。これは下のブロックの処理パイプラインに送られてそのビームＦＩＦＯ記憶ユニット７８に記憶される。同様に、アレイ１４６によく似ているアレイ２４６が背後のブロックの処理パイプラインのために用意されなければならない。これはブロック１４０の背面とアレイ１４２の背後の垂直な行とから形成される。それは背後のブロックの処理パイプラインのスライスＦＩＦＯ記憶ユニット８０に送られて、１スライス後に、即ちＬ×Ｍ÷(Ｂ2×Ｐ)ブロック・サイクル後に、使用される用意が整う。
【０１４３】
勾配の計算と光線の合成とは、ほぼ同一のパターンをたどって行われる。補間ユニット８２はＢ3個の標本のアレイを作る。一般に、図１５に示されているように、それらはブロック１４０のＢ3個のボクセルの僅かに上、左、前にずれている。これらの標本からＢ3個の勾配を計算するためには、(Ｂ＋２)3個の標本の立方体アレイが必要である。その理由は、３つの次元の各々で隣接する標本の中心差分又は他の何らかの数学的関数をとることによって各勾配を計算するからである。
【０１４４】
次に図１７を参照する。標本の(Ｂ＋２)3グループの境界に存在するものではない標本点で勾配１５８を計算することができる。最初のブロック１４０のボクセルは点で示されている。補間ユニット８２によって計算された標本は×印で示されている。処理ブロック１４０の一部分として計算された最初のグループは標本のＢ3アレイ１５０である。更に、２×Ｂ2個の標本のアレイが直ぐ左のブロックから必要とされ、２×(Ｂ＋２)2個の標本のアレイ１５４が上のブロックの処理から必要とされ、２×Ｂ×(Ｂ＋２)個の標本のアレイ１５６が直ぐ前のブロックから必要とされる。ブロック１４０が部分ビームの左に無ければ、ボクセルのアレイ１４２と同じく、アレイ１５２は同じパイプライン・サイクルの間に直ぐ左の処理パイプラインによって計算される。従って、標本アレイ１５２は随意遅延ユニット８３に送られる。パイプラインがその部分ビームの左端にあるときを除いて遅延値は０にセットされるが、左端にあるときには遅延値はＢ3基本サイクルに、即ち１ブロック・サイクルに、セットされる。対照的に、アレイ１５４及び１５６は、ビームＦＩＦＯ記憶ユニット８８及びスライスＦＩＦＯ記憶ユニット９０からそれぞれ得られる。
【０１４５】
同様に、標本の計算後に、補間ユニット８２は、次のビーム及びスライスでの処理のためにアレイ１５４及び１５６によく似ているアレイをビームＦＩＦＯ記憶ユニット８８及びスライスＦＩＦＯ記憶ユニット９０にそれぞれ送らなければならない。
【０１４６】
最初にボクセルのブロック１４０を取り出した処理パイプラインは、１ボクセルの間隔より大きく左、上、及び前にずれている標本での勾配を計算する。即ち、前のブロック・サイクルで合成された標本の一部についての勾配を計算する。その理由は、後に合成されるボクセル及び標本に依存する勾配を計算することのできる処理ユニットは無いからである。特に、部分ビームの右端にある処理ユニットは、そのブロックの右面に最も近いＢ2個の標本についての勾配を計算することはできない。更に、どの処理パイプラインも、そのブロックの底面の標本についての勾配を計算することはできない。従って、その勾配は後に計算されなければならず、それを補うために処理パイプラインはそのブロックの上、左、及び前にある標本について前に計算されなかった勾配を計算する。
【０１４７】
勾配の計算後に、標本の色、輝度、及び透明度又は不透明度を表すピクセル値を与えることができる。次にそれらは勾配評価・シェーデェイングユニット(gradient estimate and shader unit)９２によって合成のための最終段の集合に渡される。それは図１５のパターンに従うけれども、標本間隔は図１７の計算された勾配の位置へずれている。Ｂ3個のピクセル値は勾配評価・シェーディングユニット９２から合成ユニット１０２に直接送られる。ボクセル・アレイ１４２によく似ている部分的に累積された光線のピクセル値のアレイは右の処理パイプラインに送られ、ここで随意遅延ユニット９３に入れられる。同様に、ボクセル・アレイ１４４及び１４６によく似ている合成エレメントのアレイが後及び下の隣接パイプラインのビームおよびスライスＦＩＦＯ記憶ユニット９８及び１００にそれぞれ送られる。前と同様に、これらのアレイは、同じブロック・サイクルの間に勾配から計算されたＢ3個の合成エレメントの底及び後のスライスと、左隣及びスライスＦＩＦＯ記憶ユニット１００から得られたボクセルの底の行とから形成される。
【０１４８】
この様にして、Ｐ個のブロックのグループの全てのボクセルを一度に処理し、ブロックのビームを右へ横切り、ブロックのスライスを１ビームずつ下り、ボリュームデータ集合中を１スライスずつ進んでゆくことができる。
【０１４９】
或る実施の形態では、パイプライン内での各ブロックの処理はＢ3個の基本サイクルで逐次実行される。１２５メガヘルツ又は１３３．３メガヘルツのバースト・モード速度でボリューム・メモリーにアクセスするときには、基本サイクルの長さはそれぞれ８ナノ秒又は７．５ナノ秒である。これは、標本を計算し、勾配を見積もり、部分的に累積された光線のピクセル値を合成する回路の設計者にとっては過酷である。従って、好ましい実施の形態では、パイプラインでの処理は、もっと低い速度で動作する複数の処理ユニットによって並列に実行される。例えば、Ｂが８に等しければ、７．５ナノ秒から８ナノ秒のサイクルタイムで動作する１組の処理段によって、又は１５から１６ナノ秒のサイクルタイムで動作する２組の処理段によって、又は３０から３２ナノ秒のサイクルタイムで動作する４組の処理段によって、又は６０から６４ナノ秒の処理時間で動作する８組の処理段によって、又はもっと多数の処理段でも、処理を実行することができる。電子回路設計技術者は、この処理段の個数を選択することができる。
【０１５０】
ボクセルのアーキテクチャ及び処理順序に、ブロック化とそれに伴う変更とを導入することによって、Ｃｕｂｅ−４に基づくシステムでＤＲＡＭにアクセスするためにバースト・モードを利用できるようになるという効果が得られることが以上の記述から分かる。即ち、本発明において、安価で容易に入手できるＤＲＡＭデバイスを利用してボリュームデータ集合を保持するのに必要な大量のメモリーを実現できるようになる。そのために、以前に実現された実時間ボリューム・レンダリング・システムと比べてコスト、サイズ及び電力が相当節約されることとなり、パソコン及びデスクトップコンピュータ環境のための実用的で入手可能な実時間ボリューム・レンダリング・システムを実現することが可能となる。
【０１５１】
また、半導体技術が進歩し、処理論理とＤＲＡＭとを同じデバイス又はチップにおいて結合させることが可能になると、バースト・モードＤＲＡＭアクセスを可能にするために必要なのと同じアーキテクチャの変更が、処理パイプラインによるボリューム・メモリーへの効率の良い直接オンチップ・アクセスを可能にするために必要になることも分かる。
【０１５２】
ｆ)処理パイプライン間の通信
図１２及び以上の記述から、本実施の形態では１つのパイプラインからその隣のへ３種類のデータを送らなければならないことが分かる。それは、ボクセル、標本、及び部分的に累積されたピクセル値である。それらのデータはパイプライン間でそれぞれ通信ライン７６，８６，及び９６を介して伝送される。更に、それらのデータの各種類について２種類のＦＩＦＯ記憶ユニットがある、即ち、それぞれボクセル、標本、及びピクセルのためのビームＦＩＦＯ記憶ユニット７８，８８，９８とスライスＦＩＦＯ記憶ユニット８０，９０，１００とがある。
【０１５３】
各ブロック・サイクル中に、Ｂ3個のボクセルがボリューム・メモリー４２から取り出される。同時に、アレイ１４２のＢ2個のボクセルと、アレイ１４４の(Ｂ＋１)2個のボクセルと、アレイ１４６のＢ×(Ｂ＋１)個のボクセルとが２パイプライン間で伝送されなければならない。即ち、下記の個数
【０１５４】
【数８】
0004158007.tif 000009
【０１５５】
のボクセルが伝送されなければならない。
【０１５６】
同じく、各ブロック・サイクル中に、パイプラインの同じ計算段からＢ3個の標本が得られるが、アレイ１５２のＢ2個の標本と、アレイ１５４の２×(Ｂ＋２)2個の標本と、アレイ１５６の２×Ｂ×(Ｂ＋２)個の標本とがパイプライン間で伝送されなければならない。即ち、合計で下記の個数
【０１５７】
【数９】
0004158007.tif 000010
【０１５８】
の標本が伝送されなければならない。
【０１５９】
各ブロック・サイクル中に、パイプライン内でＢ3個のピクセル値が計算されるが、部分的に累積された光線を表すＢ2個のピクセル値が左から使用され、部分的に累積された光線を表す(Ｂ＋１)2個のピクセル値が上から使用され、部分的に累積された光線を表すＢ×(Ｂ＋１)個のピクセル値が前から使用される。従って、合計で下記の個数
【０１６０】
【数１０】
0004158007.tif 000011
【０１６１】
のピクセル値がパイプライン間で伝送されなければならない。式(８)，(９)及び(１０)から、ボクセルの各Ｂ3ブロックについてパイプライン間で伝送されなければならないデータ項目の総数はＢ2にほぼ比例するということが分かる。
【０１６２】
下記の表は、２から１６の範囲にわたるブロック・サイズについての式(８)，(９)及び(１０)の値を示している。
【０１６３】
0004158007.tif 000012
【０１６４】
この表から分かるように、Ｂが大きくなるに従って、Ｂ3は急速に大きくなるけれども、式(８)，(９)及び(１０)はそれより遙かにゆっくりと大きくなるということが分かる。メモリ又は前の段から取り出されたデータの各立方体アレイについて、二次の数のボクセルをパイプライン間で伝送するだけでよいからである。例えば、ブロックが各エッジに２個のボクセルを有するならば、ブロック・サイクル中に２３個即ち８個のボクセルを取り出さなければならないが、その同じブロック・サイクル中に隣り合うパイプライン間で１９個のボクセルと、５６個の標本と、１９個のピクセルとが伝送されなければならない。即ち伝えられる情報の量は取り出される情報の量の殆ど１２倍の多さである。
【０１６５】
一方、Ｂ＝８ならば、ブロック・サイクル中に５１２個のボクセルが取り出され、隣り合うパイプライン間で２１７個のボクセルと、４８８個の標本と、２１７個のピクセルとが伝送されなければならない。取り出される値に対する伝えられる値の比は、この場合には約１．８である。
【０１６６】
ブロック化の副作用は、パイプライン間で伝送されなければならない情報の量の減少である。これは、伝送量が減少するということはピンの本数が減少するということであるので、処理パイプラインの半導体インプリメンテーションを設計する上で付加的利点となる。また、ピンの本数ではなくてピンの帯域幅を減少させることも可能である。
【０１６７】
図８から、従来技術のＣｕｂｅ−４システムは、隣り合う処理パイプライン間に、互いに２の距離だけ離れているパイプライン間に、そして合成ユニット６８の場合には互いに３の距離だけ離れているパイプライン間に、通信ラインを必要とするということが分かる。必要なピンの総数は、８ビットのボクセルについては２００を僅かに下回り、１６ビットのボクセルについてはほぼ４００である。対照的に、本実施の形態では、Ｂ＝８であり、ボクセル及び標本は１６ビットでピクセルは４８ビットであるとすると、必要なピンの総数は１９２である、即ち、９６本のピンが各側でパイプラインへ延在する。
【０１６８】
レンダリング座標がいったん選択されたならば、特定のブロックを通る光線はそのブロックから出て他の７個のブロック(即ち、当該ブロックの右、下、又は背後の３個の隣接ブロック、当該ブロックの右底エッジ、右後エッジ、及び底後エッジにエッジが隣接している３個のブロック、又は頂部の左の前のコーナーが当該ブロックの底の右の後のコーナーに隣接しているブロック)のうちのいずれにも入ることができるということが本発明のブロック・スキューイングの方法から分かる。これら７個のブロックは、少なくとも３種類の処理モジュールによって、また場合によっては５種類の処理モジュールによって、処理される。
【０１６９】
Ｃｕｂｅ−４システムでは各処理パイプラインが５個の全てとの直接接続を必要とするのに対して、本発明ではそれは不要である。むしろ、ボクセルと標本値と部分的に累積された光線とを送るために必要な全ての通信は、それらの値のアレイを直ぐ隣へ送ることによって達成される。もっと遠くのパイプライン、即ち直ぐ隣には無いパイプライン、が必要とする値は、７段階で送られるが、常にちょうど良い時に目的のパイプラインに到達する。
【０１７０】
ｇ)セクショニング
本発明では、各処理パイプラインは、１パイプラインから次のパイプラインへ伝送されるデータ値を保持する内部記憶装置又はメモリーを含む。それらのデータ値は、ブロックの次のビーム又は次のスライスを処理するために必要になるまでこのメモリーにより保持される。本実施の形態では、この内部メモリーは、ビームＦＩＦＯ記憶ユニット７８，８８，９８とスライスＦＩＦＯ記憶ユニット８０，９０，１００との形を取っている。各ＦＩＦＯ記憶ユニットは、周知されている先入れ先出しメモリー管理技術を実行する内部メモリーユニットである。即ち、新しいデータは常に使用されていない記憶場所に書き込まれる。前に記憶されたデータが読み出されると、その記憶場所は再び使用されていない状態となって、新しいデータのためにその記憶場所を利用できるようになる。ＦＩＦＯ記憶ユニットの制御は、データ項目をそれらが書き込まれた順序でしか読み出せないことを保証する。
【０１７１】
本実施の形態では、各ビームＦＩＦＯ記憶ユニットは、後に処理されるＬ÷(Ｂ×Ｐ)個のブロックについてのデータを記憶する容量を含むが、このＬは表現されるボリュームデータ集合の幅であり、Ｂはブロックのエッジに存在するボクセルの個数であり、Ｐはボリュームレンダリング・システムの処理パイプラインの個数である。１ブロックあたりにＦＩＦＯ記憶ユニット７８及び９８に蓄積されるデータの量は(Ｂ＋１)2データ・エレメントのサイズのアレイであり、１ブロックあたりにＦＩＦＯ記憶ユニット８８に蓄積されるデータの量は２×(Ｂ＋２)2データ・エレメントのサイズのアレイである。従って、ビームＦＩＦＯ記憶ユニットの内部蓄積の総量は約Ｌ×Ｂ÷Ｐである。
【０１７２】
スライスＦＩＦＯ記憶ユニット８０，９０，１００の場合には、各々が、後に処理されるＬ×Ｍ÷(Ｂ2×Ｐ)個のブロックのための容量を含み、このＭはボリュームデータ集合の高さである。１ブロックあたりにＦＩＦＯ記憶ユニット８０及び１００に蓄積されるデータの量はＢ×(Ｂ＋１)データ・エレメントのサイズのアレイであり、１ブロックあたりにＦＩＦＯ記憶ユニット８８に蓄積されるデータの量は２×Ｂ×(Ｂ＋２)データ・エレメントのサイズのアレイである。従って、ビームＦＩＦＯ記憶ユニットの内部蓄積の総量はほぼＬ×Ｍ÷Ｐである。
【０１７３】
換言すると、ビームＦＩＦＯ記憶ユニットの記憶容量はボリュームデータ集合の幅に比例しなければならず、スライスＦＩＦＯ記憶ユニットの記憶容量はボリューム・データの面の面積に比例する。立方体ボリュームデータ集合の場合、即ち各エッジに同数のエレメントが存在するボリュームデータ集合の場合、その記憶要件は観察方向とは無関係である。しかし、任意の比率の矩形固体のような形状を持った一般のボリュームデータ集合の場合には、記憶要件は観察方向に応じて変化する。
【０１７４】
従来技術のＣｕｂｅ−４システムと本発明の他の実施の形態とでは、内部記憶要件はほぼ同じである。即ち、ビーム記憶はボリュームデータ集合の幅に比例し、スライス記憶はボリュームデータ集合の面の面積に比例する。また、スライスＦＩＦＯユニットについての記憶要件が他の全てを支配することも分かる。
【０１７５】
更に、記憶の総量は非常に大きくなる可能性がある。ボクセル及び標本が１６ビットの記憶を必要とし、部分的に累積されたピクセルが３２ビットの記憶を必要とする本実施の形態では、４個の処理パイプラインで２５６３データ集合を表現するためには１パイプラインあたりに１．５メガビット以上の内部記憶が必要になる。処理エレメントを実現するのに適する現在の半導体技術では、これは非常に大きくて従って非常に高価なチップをもたらす結果となる。
【０１７６】
この問題を緩和するために、本発明は、ボリュームデータ集合を別々の部分即ち”セクション”に分けて各セクションの面の面積をもっと処理しやすい値に減少させるようにして該ボリュームデータ集合を表現する。これにより、各セクションが独立のボリュームデータ集合として表現されることになるので、必要な内部記憶量が減少する。図１８〜２０は、各々観察方向１１０から表現される３つのボリュームデータ集合をレンダリング座標で示している。図１８は均等な水平セクション２００に分割されている。各セクションは、レンダリング座標において前から後へのデータの”厚板”である。スライスＦＩＦＯユニットに必要な内部記憶量は各セクションの面２０２の面積に比例する。
【０１７７】
図１９では、ボリュームデータ集合１０は、ｕ次元及びｖ次元の両方で前から後へと延在する矩形セクションに分割されている。この場合にも、各セクションを表現するために使用されるスライスＦＩＦＯ記憶の量は面の面積に比例する。図２０では、ボリュームデータ集合は、その長い側から表現される細長い矩形の固体である。この場合には、このデータ集合は、並んでいる正方形の面を持ったセクションに分割されている。この３つの場合の全てにおいて、表現に使用される内部記憶量はセクションの面２０２の面積に比例する量に減少している。
【０１７８】
観察方向１１０ａが各セクション面２０２に正確に垂直であるならば、各セクションを表現した結果としてのイメージを並べて或いは上に重ねていってボリュームデータ集合全体の正しく表現されたイメージを作ることができる。即ち、観察方向が垂直である場合には、セクションに分けて行う表現は、データ集合を一体として表現することと正確に同等である。
【０１７９】
しかし、観察方向が各面に対して垂直でなければ、一部の光線はセクション間の境界２０４を通ることになる。この場合には、セクションの側面又は底面から出て隣のセクションに入る部分的に合成又は累積された光線は、そのセクションの表現が完了するまで一時的に蓄積される。それらは、隣接するセクションでの光線の累積を続けるために使用される。
【０１８０】
本発明では、部分的に累積された光線は、レンダリング・パイプラインの外側の外部記憶モジュールに蓄積される。ここで図２１を参照すると、図１２の下側部分の修正が示されている。この修正では、合成ユニット１０２はトライステートインタフェース１０６を介して外部記憶モジュール１０４に結合されている。ピクセル通信ライン９６を結合させているトライステートインタフェース９４は、トライステートインタフェース１０６にも結合されている。外部記憶モジュール１０４はレンダリング出力４８に結合されている。
【０１８１】
レンダリング動作中、合成ユニット１０２が部分的に累積されたピクセル値をその下又は右の隣接パイプラインに送るとき、もしそのピクセル値が現在表現されているセクションの右側又は底側から出てゆく光線を表していて、その光線が隣のセクションの頂部側の左に入るならば、その隣接パイプラインはそのピクセル値をトライステートインターフェース１０６を介して外部記憶モジュール１０４に書き込む。次に、隣のセクションを表現するとき、そのセクションに左又は上から入る部分的に累積された光線のピクセル値は、随意遅延ユニット９３やビームＦＩＦＯ記憶ユニット９８からではなくて外部記憶モジュール１０４から読み出される。ボリュームデータ集合全体から出てゆく光線を表すピクセル値も外部記憶モジュール１０４に書き込まれ、次にピクセル出力ライン４８に送られる。
【０１８２】
本発明では、外部記憶モジュールはバースト・モードＤＲＡＭチップを利用して実現される。必要な記憶量はセクションの境界を形成する底面及び右面の面積に比例する。例えば、各エッジにＮ個のボクセルのある立方体データ集合が図１８のように水平セクションに分割されるならば、各境界２０４は高々Ｎ2個のピクセルを有する。セクション間の記憶される必要のあるピクセルの実際の個数は観察角に依存する。観察方向が垂直であればピクセルを外部に記憶させる必要はなく、セクションの境界に対して４５度の観察角はＮ2個のピクセルを記憶させることを必要とする。
【０１８３】
光線をセクションの境界２０４に正確に累積させるために、１セクションのボクセルの右又は底の平面とその隣のセクションの頂部又は左の平面との間で標本点が計算されなければならない。それらの標本を計算するために両方のセクションからのボクセル値が必要である。同様に、勾配は、両セクション間の標本値と、境界２０４に最も近い各セクションの中の標本値とについて見積もられなければならない。この見積もりのために両方のセクションからの標本値が必要である。
【０１８４】
本発明のある実施の形態では、セクションの境界付近での計算に必要なこれらのボクセル値及び標本値は、部分的に累積された光線のピクセル値と共に外部記憶モジュール１０４に記憶される。しかし、好ましい実施の形態では、これらのボクセル値及び標本値は、セクションの境界付近のボクセルを読み直して表現し直すことによって得られる。このことには、セクションの境界２０４の近くの標本及び勾配を計算するために必要な適切な中間値がビームＦＩＦＯ記憶ユニットに再び充填されることになるという効果がある。
【０１８５】
ボリューム・メモリーに全体を一度に収めるには大きすぎるボリュームデータ集合を表現するためにセクションに分ける手法を利用することができる。大きなデータ集合はセクションに分割され、その各々はボリューム・メモリーに収まるのに充分な程度に小さくて、且つその各々は内部記憶装置の範囲内で表現するために充分な程度に小さな面を持っている。そして各セクションは別々に表現され、その表現されたイメージは外部記憶モジュール１０４に蓄積される。セクションが表現された後、それは、ボリューム・メモリーにおいて、次に別に表現される隣のセクションと置き換えられる。部分的に累積された光線のピクセル値は、境界付近のボクセルの再読み出し及び再処理を含む上記のものと同じメカニズムを介して１セクションから次のセクションへ渡される。ボリュームデータ集合全体が表現されるまで、このプロセスが反復される。非常に大きなデータ集合の場合には毎秒３０フレームの全実時間表現速度を達成するのは実行不可能である。
【０１８６】
ｈ)ミニ・ブロック化
これまでに解説した本発明では、ボクセルはボクセル・メモリーから一度に１ブロックずつ読み出される。即ち、１ブロック・サイクルで１回の読み出し動作によりＢ3個のボクセルが取り出される。これは、セクションの境界付近のボクセルを再処理するために必要な量より多い。例えば、Ｂが８に等しければ、１ブロック・サイクルで５１２個のボクセルが読み出される。しかし、再処理のためには境界に沿ってボクセルの２又は３個の平面、即ち１２８又は１９２個のボクセル、しか必要ではない。わずか１２８又は１９２個のボクセルを処理するために５１２個のボクセルを読み出さなければならないというのは時間の浪費である。
【０１８７】
この無駄を少なくするために、本発明は”ミニ・ブロック化(mini-blocking)”と称される手法を利用する。この手法では、ブロックを各々２×２×２ボクセルのサイズの小さな”ミニ・ブロック”に分けて(即ち、ミニ・ブロックには合計で８個のボクセルがある)ボクセルを蓄積する。ブロック全体はミニ・ブロックの立方体状アレイである。各ミニ・ブロックは、バースト・モードで取り出すことができるようにボリューム・メモリーの連続する記憶場所に蓄積される。ミニ・ブロックのサイズは、バースト・モードＤＲＡＭ製品の最小バースト・サイズと少なくとも同じサイズとなるように選択される。従って、ブロックのミニ・ブロックをボリューム・メモリーからどんな順序で読み出すこともでき、適当な場合にはブロックの部分集合を読み出してもよい。
【０１８８】
セクションの境界付近のボクセルを読み直すときにこの手法が利用される。再処理のために必要な数のボクセルを含んでいるミニ・ブロックだけが取り出される。
【０１８９】
ブロック内でボクセルが処理される順序でミニ・ブロックを取り出すことによってブロック・バッファーのサイズを少し小さくすることができる。即ち、それらのボクセルが取り出されると直ちにブロックの表現が一方の側で始まる。取り出しが個々のボクセルの処理と同じ速さで進行する限りは、両者は密接に同時進行(ｐｒｏｃｅｅｄ  ｉｎ  ｌｏｃｋ  ｓｔｅｐ)することができる。処理が完了したバッファー領域に新しいボクセルを取り込むことができる。そのために、表現に必要なブロック・バッファ７２の総量が減少する。
【０１９０】
以上に、本発明の幾つかの実施の形態と、その修正形とを解説したが、以上の解説は限定をするものではなくて単なる例示に過ぎないことは当業者にとっては明らかなことである。多数の修正形や実施の形態が当業者の視野の中にあり、それらは添付の特許請求の範囲のみによって限定される発明及びその同等物の範囲に属すると考えられる。
【０１９１】
【発明の効果】
以上のようにこの発明では、複数のボクセルを有するボリュームデータ集合をレンダリングする方法であって、ａ)ボリュームデータ集合を複数のセクションに分割する工程と、ｂ)ボクセル集合を外部メモリから順番に読み出しセクション内のボクセル集合をレンダリングして複数のセクションの最初の１つをレンダリングする工程と、ｃ)複数のセクションの最初の１つのレンダリングで蓄積されたデータを一時記憶装置に記憶させる工程と、ｄ)外部メモリから複数のセクションの次の１つのボクセル集合を順番に読み出しボクセル集合をレンダリングして複数のセクションの次の１つをレンダリングし、レンダリングが一時記憶装置からの蓄積データを合体させる工程と、ｅ)複数のセクションの次の１つのレンダリングで蓄積されたデータを一時記憶装置に記憶させる工程と、ｆ)ボリュームデータ集合の複数のセクションのそれぞれがレンダリングされるまで前記ｄ)工程とｅ)工程を繰り返す工程と、を備えたことを特徴とするボリュームデータ集合・レンダリング方法およびこれに関連するボリューム・グラフィックス・システムとしたので、パソコン及びデスクトップコンピュータ環境のための実用的で入手可能な実時間ボリューム・レンダリングを実現することが可能になる等の効果が得られる。
【図面の簡単な説明】
【図１】  光線キャスティングによって画像面上に投影されるボリューム・データ・セットを示す図である。
【図２】  光線キャスティングによる個々の光線の処理を示す図である。
【図３】  光線キャスティングシステムにおいて光線の処理に対応するいくつかの方法を示す図である。
【図４】  先行技術によるＣｕｂｅ−４システムにおけるメモリー・モジュール間のボクセルのスキューイングを示す図である。
【図５】  Ｃｕｂｅ−４システムにおいて実行されるスライスパラレルレンダリングを示す図である。
【図６】  Ｃｕｂｅ−４システムにおいてボクセルを二つの遂次スライスからフェッチし処理する順序を示す図である。
【図７】  Ｃｕｂｅ−４システムのリング内の処理ユニットの接続を示すブロック図である。
【図８】  Ｃｕｂｅ−４システムの処理パイプラインのパイプラインの主要コンポーネントを示すブロック図である。
【図９】  Ｃｕｂｅ−４システムにおけるボリューム・データ・セットのＸＹ面上のボクセルのメモリー・アドレスを示す図である。
【図１０】  Ｃｕｂｅ−４システムにおけるボリューム・データ・セットのＸＺ面上のボクセルのメモリー・アドレスを示す図である。
【図１１】  本発明におけるメモリー・モジュール間のブロックによるボクセルの編成およびブロックのスキューイングを示す図である。
【図１２】  本発明の一実施の形態による実時間ボリューム・レンダリング装置における処理パイプラインおよびその関連メモリー・モジュールのブロック図を示す。
【図１３】  観察面からの光線の角度にもとづいてのレンダリングのためのレンダリング座標および選択「フロント」面の決定を示す図である。
【図１４】  ボリューム・データ・セットのベース面およびその画像面との関係を示す図である。
【図１５】  Ｂ3個のボクセルのブロックおよび前に処理したブロックから転送されたボクセルからのサンプルの計算を示す図である。
【図１６】右側、下側、および後の方向における隣接ブロックの処理をサポートするためのブロックからの情報の転送を示す図である。
【図１７】  Ｂ3個のサンプルのブロックおよび前に処理したブロックから転送されたサンプルの勾配の計算を示す図である。
【図１８】  セクションに分けられるボリューム・データ・セットを示す図である。
【図１９】  セクションに分けられる別のボリューム・データ・セットを示す図である。
【図２０】  セクションに分けられる別のボリューム・データ・セットを示す図である。
【図２１】  図１２の構成にセクション化の技術を実行するのに必要な変更を行ったもののブロック図を示す。
【符号の説明】
１０  ボリュームデータ集合、１２  ボクセル、１４  オブジェクト、１６  ２次元画像面、１８  光線、２０  サンプル・ポイント、２２  ピクセル、４０処理パイプライン(処理モジュール)、４２  ボリューム・メモリー・モジュール、４８  バス、７２  ブロックバッファ、７３，８３，９３  随意遅延ユニット、７４，８４，９４，１０６  トライステートインタフェース、７６  ボクセル通信ライン，７８，８８，９８  ビームＦＩＦＯ記憶ユニット、８０，９０，１００  スライスＦＩＦＯ記憶ユニット、８２  補間ユニット、８６  サンプル通信ライン、９２  勾配評価・シェーディングユニット、９６  合成要素通信ライン、１０２  合成ユニット、１０４  外部記憶モジュール、１３０  ベースピクセル、１３２  ベース・プレーン。
【図１】
0004158007.tif 000013
【図２】
0004158007.tif 000014
【図３】
0004158007.tif 000015
【図４】
0004158007.tif 000016
【図５】
0004158007.tif 000017
【図６】
0004158007.tif 000018
【図７】
0004158007.tif 000019
【図８】
0004158007.tif 000020
【図９】
0004158007.tif 000021
【図１０】
0004158007.tif 000022
【図１１】
0004158007.tif 000023
【図１２】
0004158007.tif 000024
【図１３】
0004158007.tif 000025
【図１４】
0004158007.tif 000026
【図１５】
0004158007.tif 000027
【図１６】
0004158007.tif 000028
【図１７】
0004158007.tif 000029
【図１８】
0004158007.tif 000030
【図１９】
0004158007.tif 000031
【図２０】
0004158007.tif 000032
【図２１】
0004158007.tif 000033