Comments
Description
Transcript
博士論文 - 横浜国立大学教育人間科学部紀要
㌦． Y 轟ク 矛︾ 博：士論文 実時間ボリュームグラフィックスの アーキテクチャに関する研究 指導教官： 土肥康孝教授 平成12年12月22日提出 横浜国立大学大学院工学研究科 電子情報工学専攻 緒方正人 98JDOO2 幽脚ll lO994800 要旨 科学技術上の諸問題を計算機で解き，結果を直感的に把握したいとの要求，あるい はMRI， CTおよび超音波診断装置などを用いた高度医療の普及などから3次元情報 を映像化する高速かつ安価なボリュームレンダリング装置が必要とされている。ボ リュームレンダリングの計算は，比較的単純な積和計算の繰り返しで構成されるが， データ量が膨大であるため，高速映像表示には高価なスーパコンピュータや専用ハー ドウエアが用いられている．本研究は，処理性能がスケーラブルであり価格性能比の 良いボリュームレンダリングシステムを提案した。 本論文は2部からなり，第1部でボリュームグラフィックにおける光線の経路に沿っ た透視投影を可能にする下和計算の高速エンジンを提案する．第2部では，高速エン ジンを持つパーソナルコンピュータ複数をネットワークで結合し，大規模なボリュー ムデータの高速表示を行う並列ボリュームレンダリング・システムを提案する． 透視投影が可能なPCクラスの高速エンジンは現存しない．透視投影においては， 光線の経路で近傍の格子点を用いたコンボリューションを行う必要があるが，このコ ンボリューション領域は光線が遠ざかるに従い増加するため，回路規模が大きくなり VLSIでの実現が難しい．この問題を解決するVLSI化に適したコンボリューション・ アーキテクチャを提案した．領域Wのコンボリューションを構成するには，通常W3 個の関和計算を必要とするが，提案法は3Wの積和計算器で構成できる．性能予測に よれば2563格子点数の実時間表示が4パイプラインで可能である．この実時間表示 における3Dコンボリューションの回路規模は，半導体プロセス0，18μmを用いた場 合，80K：ゲートおよび3MビットのSRAM程度である． 手術シミュレータなど大規模な科学技術計算の対話的野黒化では，大容量のボリュー ムデータ（10243格子点以上）を取り扱う必要があり単一のレンダリングエンジンの みでは処理性能が不足する．大規模ボリュームの実時間表示に対応する並列ボリュー ムレンダリング・システムを提案した．提案法はボリュームを部分空間に分け，各 部分空間の映像発生にPCを割り当て2次元部分映像を発生させ，これを合成するこ とにより全体映像を得る．部分映像のレンダリング時間は並列度の増加により減少 するが，部分映像の重畳時間は増加する．重畳をハードウエア化することによりこの 問題を解決する「実用的な並列ボリュームレンダリング・システム」を試作した．試 作システムは，高速エンジンおよび重畳ハードウエアを用いることにより，10243格 子点のボリュームを約15Hzで表示可能である． 本研究は，大規模科学技術計算の高速可視化あるいは医療分野での3次元可視化に 寄与するものである．特に，実用的な手術シュミュレータの実現に応用が期待される． 唇− ●ユ 目次 第1部 実時間ボリュームレンダリングにおいて透視投影を可能 とするパイプラインコンボリューション・アーキテクチャ ■ 1 1部あらまし 1 第1章はじめに 関連した研究の現状 2。1 サンプルオーダ．。。．．．．．．．。．。．．．◎尋．．．。．．．亀。．紛． 2．2 ボクセルオーダ法．、．．．．．．．．．．．．。．．．。．＿．．．．．．1， 第3章 ハードウエア構成の問題 3．1シアーワープ法を用いたH／W構成の問題点 4．1 サンプル並列＿．。．．．．．．．。。。．．．．。。。．。。．。．．．．． 4．2 4．3 1Dコンボリューションの直列化による3Dコンボリューション 。、．． 並列パイプライン・コンボリューション構成の導出。。。．．、．．．． 4．4 V＝飾特異条件下の並列パイプラインコンボリューションの構成．． 4．5 コンボリューション領域．．。．。．．．．．。．．。．。，。．．．．．．． 11⊥ 第4章 基本原理 006δ90 財05 ケ8ケ邑00Qり15 第2章 2 第5章 提案するアーキテクチャ 16 5．1 スキュードメモリ構成 ．。．．＿、．．。．．．．。。．．．．。．．。．． 16 5．2 一般条件下で動作する並列パイプライン3Dコンボリューションの構戒16 第6章 提案アーキテクチャの評価 20 6ユ レンダリング時問。。．。、。。．．．．。．。。．．。．。．．。。．、．。． 20 6．2 63 提案アーキテクチャのゲート数評価 21 スケーラビリティ＿．．．．．．．． 23 6。4 画質．．．。．．．．。．．、．．．。． 24 第7章 まとめ ■ 1部参考文献 26 27 iii 第II部 空間および光線分割による 並列ボリュームレンダリング・システム 29 ■ II部あらまし 30 第1章はじめに 31 第2章 並列ボリュームレンダリング技術の現状 32 第3章並列化の原理 33 3．1空間分割による並列化。．．．．．．．。1，．．． 33 3⊥1 光線分割による並列化．．．．．。．．． 34 3．2 Mul七iple−sheared重畳法＿＿．．．＿．＿．一一・．・・… 一 35 第4章 PCクラスタを用いたソフトウエアによる実装 38 4．1 システム構城 ＿．。．．．．。．．．．．．．．． 38 4．2 処理概要．．．、．．．．．．．．．．．．．．．．． 38 第5章 性能評価 41 5ユ 処理時間。．．．．．。．。。．．．。。．。．，．． 41 5．2 実験の考察 ．．．＿．，．．．。．．．．。．．． 42 5．2．1 並列度と処理性能の線形性．．．．．．． 42 52．2 ソフトウエアによる重畳時間と並列度 43 5．2．3 ビデオレ・一トでの映像発生．．．。．．． 44 第6章 試作ハードウエア 48 6．1 構成 ．．．．。．．．。．。、。．。．．．．。．．． 48 6．2 試作ハードウェア，．．。．．。．．．．．．．。． 49 6．3性能評価．．．＿．．．．．。．．．．．．．．．． 51 第7章 まとめ 53 ■ II部参考文献 54 付録A光線分割の原理 56 □ 57 公表論文 58 □ 謝辞 iv 図目次 1部 1 3．1透視投影におけるシアーおよび縮小．．．。．．．．．．．．。．．．．．． 5 で⊥り4 ピ0ρU 44 3 44ム 444 サンプル並列によるボリュームレンダリングの再構戒。．．．．．．、． 7 ボクセルデータの4パイプラインによる読み出し順序： データサイズ yはパイプライン数より大きい． ．．。．．．．．。。．．．．．．．．．。。。 9 i方向1Dコンボリューション構成の導出。．．．．．．．。．．．．．．． 10 ゴ方向1Dコンボリューション構成の導出．．．．．＿＿．＿．．．。 10 3×3×3領域の4並列パイプライン3Dコンボリューション：y＝師＝413 パイプラインが読み込むボクセルデータとその出力の関係。．．。．． 15 5。1折り返しにともなう「折り返し遅延」および「左折り返し遅延」の導 出： y＝8およびハ争＝4として説明 。．．．．．．．．。。．．．．． 18 5．23x3×3領域の並列パイプライン3Dコンボリューションの構成：一 般条件y》1Vpに対応，1協篇4の例 ＿＿＿＿＿＿＿＿＿ 19 6．1 各種表示速度（フレームレート）に対応する最大ボリューム次元yお よびパイプライン数陽の関係＿＿＿＿＿＿＿＿＿＿．． 21 62 ゲート数評価に用いる積憂計算α詔＋6のVHDLコード： 12ビット幅22 6．3 シミュレータを用いた映像による評価 ．。．．．。．。．．．．．．．．． 25 29 II部 1 9廟34 り0り0り0り0 444 BSPを用いた隠顕関係を示す優i先順位の計算．．．。．．．．．．．．．．34 並列処理のためのBSPを用いたボリュームのサブボリュームへの分割 35 並列処理のための光線分割。．。．．。．。．．．．．．。．．．．．．．。． 36 Mu1七iple−sheared重畳法：サブボリュームに対応する二次元ベースプ レーン間で透明度を用いた重畳を行なう ．．．．．．．．．。．．．．．． 37 −←り泊り0 ソフトウエアによる並列ボリュームレンダリングシステムの構成．．． 38 PCクラスタを用いた並列ボリュームレンダリングシステムの概観。．39 評価に用いたボリュームデータの表示映像＿．。．．．．．．。。．．。 5．2 本提案法およびRaycastiR9法の並列度による処理時間比較。． 本提案法とRaycasting法の並列度による重畳時間比較 ．．．． 5．3 ド◎ρ◎βU 5．1 444 プロトタイプシステムに実装したMu1七iple−Sheared重畳法の処理フロー40 V 5．4 並列度による高速化率の変化 ＿．．．．．．．．．．．。．．．．．．．． 47 5．5 並列度による処理時間の予測 47 6．3 試作重畳装置インターフェースボード部．．。．．。．．．．．．．．．． 6．4 試作重畳装置の重畳部 ．．．．。．．．．。。．、．．．．．。。．．．．．。 6．5 試作重畳装置の構成 。．．。。．．．．．．．．．．．．．。．．．．．．．． 6．6 試作ハードウエアの並列度による処理時間予測．．．．。．．．．．。．． 4←4ド0ドOpOFO 6．2 重畳部の構城 ．．．．．。．。。．．。．．．．．．。．．．．．．．。。．．． 8QりAUAU−⊥り白 6．1H／W重畳装置を持つ並列ボリュームレンダリングシステムの構成．． vi 表目次 1部 1 4．1￠方向1Dコンボリューションのデータフロー ．．．、．．．．．．．．． 12 42 ゼ方向1Dコンボリューションにおけるサンプル位置およびシアー位置 のデータフロー．．9．。。．。．．。．e．。．。．．。5。．．。．．．．． 14 5．1データの次元yおよびパイプライン数怖と遅延時間の関係 17 6．1 パイプライン当たりのメモリサイズ評価（ビット） 。。．。．．。．．． II部 4．1 構成したPCクラスタおよび要素PCの性能諸元 5．2Multiple−Sheared法による人体頭部のレンダリング時間計測． ． 5．3 M登1tiple−Sheared法によるニューロンのレンダリング時間計測 5．4 Raycasting法による人体頭部のレンダリング時間計測．．．．． 5。5Raycasting法によるニューロンのレンダリング時間計測 ＿． 29 39 −り白り4り0り0 4 4∴4ム4藷4 5．1時間計測の組み合わせ条件．．．．．．．．．．．．．．．．。．．．．．．． り○り0 り4り々 3Dコンボリューションのゲート数（1パイプラインあたり）： ビット 幅12ビット。．．＿。．＿．．．．．．．＿．．．＿．＿．、．．．．魯 AU−← イプライン数瑞の関係＿．＿＿．＿＿＿＿＿＿．＿．． 積和計算α3塗十6のASICでのゲート規模．．．．．．．．。．．．．．．． り4リム り詣9e 盆VρU 6．4 各表示速度（フレームレート）に対応する最大ボリューム次元Vとパ 第1部 実時間ボリュームレンダリングにおいて 透視投影を可能とするパイプラインコ ンボリューション・アーキテクチャ 1 1部あらまし 本論文は実時間ボリュームグラフィックスの高速表示アルゴリズムであるシアーワー プ法において透視投影映像を生成するために必要なコンボリューションのシストリッ クアレイ構成法に関して提案したものである．シアーワープ法ではサンプル点の計算 において，視点から遠いものほど，コンボリューションの対象となるボクセル数が増 加する．このボクセル数の増加は配線が固定しているハードウエアでの実現において 回路規模の増大をまねき，その実現を困難にしている． 重みがX，Y，Z方向に分離できることを用いることにより，1Dコンボリューション をX，YおよびZ方向にそれぞれに割り当て，これらを直列に接続することにより，領 域．Mの3Dコンボリューションに必要なM3個の積和計算を3．Mに削減した。 ボクセルのサイズをV3とすれば光線に対応するパイプライン数はy2である．1 パイプラインが単位時間あたりに処理する光線数をγとすれば，擬似的にγ本のパ イプラインが必要となるが，実用上，実パイプライン数五はゐ《yでなければなら ない．このため，提案法は擬似パイプラインに折り返しを用いて実用的なパイプラ イン数しまで削減する機構を持つ。 評価によれば，提案法は4実パイプラインを用いて2563サイズのデータをビデオ レート，即ち30Hz，で表示可能である．このとき，3Dコンボリューションの回路規模 は，半導体プロセス0．18μ鶏を用いた場合，80Kゲートおよび3MビットのSRAMを 必要とする程度である．また，提案するアーキテクチャは大規模データに対してパイプ ラインの増加により容易に対応できる処理のスケーラビリティを持つ．5123（y＝512） サイズのデータのビデオレート表示は32パイプライン，10243（V＝1024）データで は256パイプラインで可能である． 2 第1章 はじめに 科学技術上の諸問題を計算機を用いて解き，結果を直感的に把握したいとの要求，あ るいは高度医療におけるMRI， CT，超音波診断装置から得たデータの非専門家への 提示，などから大容量の3次元情報を可視化する高速かつ安価なボリュームレンダリ ングシステムが必要とされている。 ボリュームの可視化は，1）ボリュームが物質の光透過率などの情報を3次元空間内 の格子点上に持つため大量のデータ処理を必要とする，2）光の減衰を光線の経路に ．沿って一次元で計算するので比較的単純な積和計算の繰り返しである，などを特徴と する．しかし，データ量が膨大であることから，高速表示には，高価なスーパコン ピュータや専用ハードウエアが用いられている。 ボリューム映像の発生には多くの方法が提案されているが，基本的に全ての方法 は，ボリュームレンダリングの計算式（［5］）を用いて，光の減衰を計算している。式 中，1（α，6）は位置αから6間を通過した光線の輝度を示し，5（γ）は光路における発光， α（γ）は吸収をそれぞれ示す． 1（α，6）諜・（・）・耀・（オ）4オ酢 （L1） 式（1．1）の簡略形として各サンプル点の計算に周囲のボクセル値による線形補間を 用いている．各々のサンプル値の計算は比較的単純であるが，サンプル点の総数が膨 大であるため，映像発生時間に占めるサンプル値計算の割合は高い．本論文は，透視 投影と平行投影を統一して取り扱うシアーワープ甲州［61で必要なコンボリューショ ン計算：に関してVLSI化に適したアーキテクチャを提案した。 本論文は次の構成を持つ．2章では「現状」を示し，3章において「シアーワープ 法の問題点」，4章では「提案法の原理」，5章においては「アーキテクチャ」を示 す．また6章において「提案法の評価」，最後に「まとめ」を7章に示す． 3 第2章 関連した研究の現状 アーキテクチャ構成の観点に立てば，ボリュームレンダリングは次の二つの実現法 に分類できる．それらは，1）サンブルーオーダ（sample−order）法，2）ボクセルオーダ （voxe1−order）法である．言葉が示すように前者は，処理の起点としてサンプル点を用 いて，これからボクセルのメモリ位置を求める．これとは逆に，ボクセルオーダ法は 処理の起点にボクセル位置を用いるので，複雑なアドレス計算をすることなく直接 メモリアドレスが求まる．各々の実現法は実時間ボリュームレンダリングアーキテク チャを構成する上で，短所および長所を持つ． 2．1 サンプルオーダ サンプルオーダ法はボリュームレンダリング法の直接的な実現法である圖同。こ の方法では不透明になった光線の減衰計算を打ち切り，他の光線計算に計算資源を割 り当てる”アーリレイターミネーション”（early ray termin．ation），メモリアクセスの 局所性を利用した”アクセスコヒーレンスエンコーディング”（cohere耽e eRcoding） など［7］を用いた最適化による処理速度の向上が容易である． 本方式の欠点は，サンプル値の計算時，異なる複数の光線のサンプル値計算のため に，同一ボクセルの同時読み出しを生じ，メモリ読み出しに待ちを発生させ，メモリ 読み出しの実効速度が低下することにある． また，アクセスがメモリの格納順でな いため，視点の姿勢を考慮したメモリアドレスの計算が必要である．これらの，欠点 がVLSI化した実時間レンダリングアーキテクチャの実現を複雑にする．この方式で 643ボクセル以上の実用的なボリュームデータに対応した実システムは報告されてい ない圖． 2．2 ボクセルオーダ法 ボクセルオーダ法は，ボクセルのアドレスを直接処理の起点に用いるので，メモリ アドレスを前法のように計算する必要がなく，また，メモリのアクセスも規則性を持 つ．この特徴はアーキテクチャのVLSI化には有効である．このため，実時間化に適 して方法と考えられる．Cube−4［11］およびVLSIでこれを実現したEM−Cube［10］［12］ は，シストリック構成をとるボクセルオーダ方式の最も優れた実現例である．この方 式では，メモリ読み出しの規則性を活用して，読み出し内容の再利用により，メモリ 読み出し回数を削減して実時間表示を達成している．しかし，投影法が平行投影に限 られている。シアーワープ（Shear−warp）法［5］［6］はこの分類に属し，平行投影およ 2．2．ボクセルオーダ法 び透視投影を統一して取り扱い可能な優れた方法である。しかし，リサンプリングに 必要なコンボリューションの実現が多数の積和計算を必要とするため，ソフトウエア でのみ実現され，このため実時間化は行われていない． 4 5 第3章 ハードウエア構成の問題 3．1シアーワープ法を用いたH／W構成の問題点 シアーワープ法同［6］はベースプレーン1上にシアーマトリクスHにより歪ませた ボリュームの映像を発生させ，この映像をテクスチャマッピングにより歪み補正を行 いスクリーン上に正し映像を発生する，二段階による映像発生法である．図3．1（左） に光線が視点から遠ざかるに光線が広がっていく模式図を示す．このため，サンプリ ジグにおいては，視点から遠方になるに従い，コンボリューション領域を増加させる 必要がある．図3．1（右）に広がって行く光線がベースプレーン上で平行光線とされて いる模式図を示す。左図で示した光線が広がる替わりにボクセル位置の平行移動およ び間隔の縮小により，広がる光線が平行化されることを示す．両図は等価である．右 図では，最も手前のスライスから，視点から遠いスライスへ行くに従い，縮小および 平行移動量が増加している．平行化された光線上のサンプル点における推定したボ クセル値は，この縮小および平行移動されたボクセルの領域内におけるコンボリュー ションで求められる． 配 G「’ Parallelized ／ ン ？”惇．”噂の◎…◇口唖…嚇小？ ㌔鯉評 1：0：●：●iRayS l＝ i／メ ”’⋮⋮⋮ ⇔ ’ ．． Equiva− lent k． ○○ ● ’ Slice k ● ’ ● 焉Q．．＿＿．一一 y x ／Image on scree］a Eye MatriX H i ’ ：O⋮・・⋮■ ●●○ ⋮●⋮：●・孟● Z ● Trans我）rm with 点●○ 轤r Ray・ j ko Base］Plar糺e Eye（i◎・jo・ko） 図3．1：透視投影におけるシアーおよび縮小 シアーワープ法は前述のように透視投影と平行投影を統一処理する良い性質を持つ． しかし，実時間化に必要なパイプライン化（あるいはシストリック構成）したハード ウエアの実現には次の問題点がある：（1）コンボリューションに必要な積和計算器数 の削減および（2）並列パイプライン化したアーキテクチャの導出，である． 1ボリュームデータを構成する6面のうち視線に対して最も直角になる面 3．1．シアーワープ法を用いたH／W構成の問題点 6 コンボリューション対象となる最大ボクセル数M，即ち最悪の設計条件，は次式 となる． M＝1一一為η協記／為。ラ （3．1） ここで，編。．は2ベースプレーンから最も遠いスライス位置を示し，秘は視点と ベースプレーン間の距離を示す．図3．1参照．このMは，秘と編。．の比により大き な数となる． 領域Mを持つ単純な三次元コンボリューションではM3個の積和計 算器が必要である．ハードウエアでの実現を想定した場合，配線が固定されるため， 最初から十分な大きなコンボリューション領域を予め想定した設計が必要である．こ のため，ハードウエアの規模増大を招く． また，VLSI化に適した処理性能がスケーラブルな構造を持つコンボリューション の構成を導出することも大きな課題である．実時間での映像発生を行なうための高速 性を持つため，シストリック構成での実現を目指している． 以上述べた二つの課題が，ハードウエアでの実現を困難にしている． 2表記＠，シ，勾でデータベース座標におけるボクセル位置を示し，表記σ，ゴ，紛で図3．1に示す正規 化した処理座標系におけるボクセル位置を示す． 7 第4章 基本原理 4．1 サンプル並列 処理の起点をボクセルとする従来の考えからサンプルに転換し，ボリュームレンダ リング処理を「サンプル並列」（sample paralle1）として再構成した．これにより，サ ンプリングに必要なパイプライン問の複雑な通信がレンダリング部からサンプリング 部にまとまって分離可能である。図4ユに示すように，リサンプリング部はメモリ部 とレンダリング部との中間に位置しレンダリダ部と完全に分離している． Voxel Memory（Skewed memory） ザ ゆれぬののロコロの りのののコロココ ののサロロロ のののサココロ のりほロロ おののロゆコののののコロロのゆのほコロ のののの リコじ i囮口口…一…一画； 趨＿＿翻艦禰鼎瀞騨 一＿一鳳傭贈轄障一一＿柵曽脚”聯需一＿＿齢輔僻鱒，＿ 一榊需肺＿＿顧輔常鞘一＿＿齢鱒膳贈ρ一鼎鼎儲轄鱒 一＿一齢輔榊騨聯’ Resampling Module with Shealうng （3D corlvol縫tion） ↓R・・d・曝Pip・li勲1・ΣS（・）」a（「侭・↓ 一ローローL］一一「］一 ＿＿ユ ↓ ↓Pixe童M・m・・y↓ し コ …MM画國一一一國… 圏 1 輸9一《CRT MEM：Memory Modules 図4ユ：サンプル並列によるボリュームレンダリングの再構成 4．2。1Dコンボリユーションの直列化による3Dコンボリューション 8 42 1Dコンボリューションの直列化による3Dコンボリ も ユーンヨノ シアーされたボクセル位置（鵜メ，たりおよびリサンプル位置色ゴ，勧はボクセル位 置σ，ブ，紛を用いた次式で与えられる． （1，」，κ，レγ）T＝H・（ゴ，あん，1）7 ω，ゴ㌔ん†）＝（1／四」／確ラκ／W） （4．1） （ゼ，ゴ，ん）＝（Lゼ†1，！ゴ†」，！列） ここに添え字丁はマトリクスの転置を示し，マトリクス∬は次式で示されるシアー マトリクス圖である． 10一無O ll湖， （42） oo一意1 式中の（ゴ。，ゴ。，海。）は視点位置，砺。．はベースプレーンから最も遠いスライス位置をそ れぞれ示す．図3。1参照． 今，コンボリューション領域をルf×M×114と仮定したとき，並列化された光線上 のサンプル位置σ，ゴ，初におけるサンプル値は，次式の3Dコンボリューションで求 まる。 5ε錘＝Σ告1Σ編Σ論1 （4．3） ωZη襯●物ζ十∼，ゴ。十糀，ん。十π， 上式で用いた，2。，ゴ。，ん。は次式で与えられ， i。＝ ゼーL誓1，ゴ。＝ゴー1誓」， 海。ごしL誓」． η￠。私ゴ。橿，た。梅は（i。＋Z，ゴ。＋鵬，為。＋π）をアドレスとするボクセル値であり，勧職は 次式で示されるコンボリューションの正規化した重み関数である． ωz矯π驚 四篇πσ一（i。十z）†，ゴー（ブ。十m）重， りん一（海。十箆）†）， ご れ ΣΣΣω・＿一1・ 重みがωz肌mi．e．ωz搬π＝・砺’ωmωzと分離可能とすれば，式（4．3）は式（4．4）と変形 できる． 5雛＝Σ論1ωπΣ編妬Σ超♂ （4．4） ωごδη￠c一μ，ゴ。伽，紀。十倫り 4．3．並列パイプライン・コンボリューション構成の導出 9 ここに，吻，ω瓢および’砺は距離差を用いた重み関数であり次式である。 ωド 隅（ε一（盛。＋z）†）， ωべ鴨σ一（ゴ。擁）†）， （4。5） ・ω物瓢 肌（海一（海。＋箆）‡）． 重みが分離可能なものを対象とするとの仮定は，応用上有効である． 多くの実用 上重要な重み関数，例えば3Dラグランジェ補間あるいは3D3伽。関数などはこのク ラスに属している。重み関数が分離可能であることにより，3Dコンボリューション 計算が1Dコンボリューションの直列結合で実現できる．コンボリューション領域を Mとする通常の3Dコンボリューション計算は．M3個の積和計算器を必要とするが， 重み関数が分離可能なクラスを対象とすることにより3ルfに削減できる． 4．3 並列パイプライン・コンボリューション構成の導出 導出にあたり，初めにパイプライン内を通過するボクセルデータ間の遅れ時間乃 を定義する．図4．2はボリュームデータを構成するスライスデータ上のボクセルデー タを4パイプラインを用いて読み出す順序を示した模式図である．ボリューム内の全 データは図で示した順序により読み出される． k 1 ユ Ti搬e Vvoxe1 Time Time 2 V／4 轟一騨 Ti狙e V／4÷1 Time Time V／4牽2 2＊V／4 購輌騨霜〉 今 Ti】me 2＊V／4牽1 ﹂ 図4．2：ボクセルデータの4パイプラインによる読み出し順序： データサイズyはパ イプライン数より大きい． このとき，データ読み出し時間の相違による二つのボクセルデータ間の読み出し時 刻の相違乃は，ボリュームデータの次元y（一辺のサイズ）および用いるパイプラ イン数箇を用いて式（4．6）で定義できる． 乃（り輌鱗，≠H酬γ髭＋γ2観物 （4・6） 式（4．4）の3Dコンボリューション計算は，次式で示すように1Dコンボリュー ション計算を順次実行したものになる． α赫＝Σ麗♂町妙i。＋1，。，。， 6εドΣ溜ω犠・αε，蛙跳。， （4・7） 5奪3ドΣ誕モ01ωパ6ε，ラ，廓・ 4．3．並列パイプライン・コンボリューション構成の導出 10 以下の議論は，導出を明確にするためにコンボリューション領域を．M＝3および 用いるパイプライン数を脇＝4とするが，これは一般性を失うことなく，任意のM’ および瑞に対しても成立する． 図4。3は計算αε，。，，＝Σ覆δ1ωz・妙岬，＊，。を縦に記述した後，Zをずらしながら4並 列，横に並べたものである． 図中，同一のボクセルデータは矢印で示されている． これらの同一ボクセルデータはメモリから別’々に読み出す必要はなく，データの受 け渡しによる再利用による．再利用に伴なうデータ受け渡しの遅れ時間は，式（4．6） で規定される，この図の例では，乃1（η乞。＋1，・，・；η‘q・，・）＝0である． 従って，データ の再利用に必要な遅延器は，この例では必要ない． τ0，幣 む1，属，翼 η2糊 ”3，写，x 図43河方向1Dコンボリューション構成の導出 ︵．㊧ N β畢 α． 『轡 図4．4：ゴ方向1Dコンボリューション構成の導出 図4・4に計算甲声を前述と同様に縦に書き，横に並べた模式図を示す・ この場合 の遅延器の遅れ時間は，7鳳α姦÷1戸α娠ρ＝4／4となる・同様な議論をk方向に適用 可能である・この場合の遅延器の遅れ時間は，乃3（δε∂，た。＋1；軽3，た。）＝16／4となる・ 以上のような議論を通して，図4．3で示した2方向ユDコンボリューションと図4．4で 示したブ方向コンボリューションおよび同様なん方向コンボリューションを順番に直 列に接続すれば，3Dコンボリューションを実現する4並列パイプラインコンボリュー ションの構成が導ける． 4．4．V＝Np特異条件下の並列パイプラインコンボリューションの構i成 11 4．4 V＝N♪特異条件下の並列パイプラインコンボリュー ションの構成 図4．5に，前述の議論を元に構成した，3×3×3のコンボリューション領域を持つ 並列パイプラインコンボリューションを示す． 図は，ボリュームー辺のサイズとパイプライン数が等しい特異な条件下での構成を 示す．コンボリューションは図4．5（a）に示すように，二種類のデータパスを持つ．実 線はボクセルのデータパスを示し，破線はサンプリング位置およびシアー位置のデー タパスを示す． 構成は前述のように盛方向およびゴ方向為方向の3グループのlDコンボリュー ションから構成されている．ゴ方向のユDコンボリューションは，次のスキャンライ ンデータ上の対応ボクセルの遅れを補償する遅延時間7レ2を持つか遅延器を持つ．ん 方向のlDコンボリューションは，次のスライスデータ上の対応ボクセルの遅れを補 償する遅延時間乃3を持つん遅延器を持つ．この並列パイプラインを用いて，全ての ボクセルをどのように読み出すかの様子を図4．5（b）に示す．図4．5（c）に元のボクセ ル位置とシアー変換を受けた位置の空間的関係を示す．サンプリング位置とシアーさ れた位置との距離差δ2rδゴrδたは各方向の重み計算に用いる．図4．5（d）は，図4，5（a） で示した演算器の詳細を示す． 表4．1に，図4．5（a）に示したi方向！Dコンボリューションにおけるパイプライ ン内のデータフローを示す．華中のデータフローは，1スライスが4×4で構成した ボクセルを入力とする例を示した．（図4．5（b）参照．） 表中，時刻一5における位置 脇一。の出力が示すように！Dコンボリューションの結果が同時に4出力されている． 同様に表4．2に，サンプリングの位置②あ勧およびシアー位置（盛†，ゴ㌔ん†）のパイプ ライン内における流れを示す． 表4．1および4．2は2方向におけるにデータフローを示したが，ゴ脈は遅れ時間とし て，乃2および乃3を持つことが異なるのみであるので，示した表から図4．5における データフローが推測できる。 4．4．y＝1Vp特異条件下の並列パイプラインコンボリューションの構成 12 表4．1：i方向1Dコンボリューションのデータフロー Time Loca七ion 1 恥一D つ ， ， ， う （一 o） （国，η3・・ ，o） o，／） ＠2、。， （團，［亟i］，o） j 一） （一， ラ o） （り◎2。，o， o） （勿、2。， o，o） 0 （η1エ。，勿2・・， 0 ＠2・・， ”3・o，0） （一 ラ 一） ”。。。） （り3◎。 ， η20◎ラリ300 ， 妙3◎。） ”201 ＠230り0， o） o） ＠220， η32。，0） ＠32。，U。2。， ＠310， 勿・10，”、・・） ＠…，り・1・， り21◎） η00◎，妙、。◎） η301 ＠330，0， o） ＠・3・， ＠。2。，”、20， o） ＠、2◎， （P，9，7）＝P肌＋9恥＋7％ ，∼ り030 ”33◎ η320予 0り 一，一 η120 （η・1。，0 ”101 o，o） ∼） o，o） j 一う一 j （匝］， ︵ （一， ， η10◎ラ勿200 ， η100，妙200 り001 ＠・3・， ，o） （国，”… ＠010，”・1・， 妙010ラ 0 一） ︵ 砺一D 一一 o） @ ， （一ラー o） ， ラ （妙。。。 j 一，一 j 一，一 妙210 （［亟］・o， U230 o，o） （一 ”020 ︵ ︶ ＠3・◎， 一） @ ラ ”13◎ （”22◎， （一 一） ， ％一D j ，一 一） ＠010．0 り、。。，0） ， （一 o， ） 一） ， 一 妙320 （一 り110 o） （匝］・o・ （ ，一 囮 j 一ラ∼ 一） ， （圓， 囑一。 瑚一。 晩一。 o，o） j 一，一 j 一，一 Pipe 3 ラ 瑚一。 ％一。 一） ， ， ＠3・oう 一） 国 （一，一 （一，一 （一，一 勿010 妙220 yレb−c 一） ， ラ 一 耽一D ％一。 隅一。 ％一。 5 勿310 （［二二， ︵ 4 ， ％一D ％一。 瑚一。 ％一。 3 （一 国 （一り一 （一，一 （一ラー ， （一 j 一，一 j 一，一 j 一，一 Pipe 2 ， 隅一。 恥一。 Pipe 1 ラ （一 ， 凧）一。 ， 2 Pipe O （舳，妙2・・， η31◎） o，o） 妙22。，o） ＠2・・， ”3エ・，妙◎・・） 4．4．y＝1Vp特異条件下の並列パイプラインコンボリューションの構成 Rays Processing 卜、 P2 order k I V330 VO30 鎗δ鉱げvセ20 〆 ÷ ，／ To ，W玉 ．Wl （b）Se（蓬ueRもial a・ccess of voxe1s， skewed，も。 be窺sed ニろ ．W重 ．．WI From§き W珍／ 1 ／〆 ： 負）reach pipeli貧e． ゾ・クw1馨 」ド 1 ” ， ゐら w2 ， w2 ．Wゑ 廼 「lli ノ ぎ ち漏∼．L＿＿＿ i ／ 1／1 …津； 傘﹂ い！馬 ｝㌔！自 いてつ い ぶ ゆ エ 「’『⊃ ／1翫ll T。，．w3 O00vOOv多00vOO @ ： P0取一一一貿・一 O珈……）む一・ 宸P一⋮瓢 癒2⋮覗 旨 A…’…’‘ @一曽曹FF一一戸 ： ： 蔀6・鰭さ，iti一、． O酵22 ツ琶善．／ 甲・ ’” lD，／ lD’ノ5 鴨 ’擦じ「 W5 ↓♀、 燈＿ 鳶／留／ O￥1曽……栄冒一 …一一 … ?・… @1 螺a ＿串3 ◎Resampling posiもio盗 ρ’ 糊 ノ ⊥‘−・3 享 6、／1 W凱w（δ1） Wi凱 @ δ2 x …… 車4x：灘・窺島） … … 。．．⑩ ．衛 δ3 ，，，V、米，，恥米、、鴨陛 胆／曲／ T4 ．1嚢﹂ 逸レ1翌／／陣 T2 嬰3 I）ipelines ＼？、三； ／WO ，．W6 F。鱗 ／ 1 、／／ サ／／WO 奎 cceSS Time l ／＼＼l 」i，：瑠・i Pン i ・ ●l コ 馳oo V OO POPIP2P3 ●．・ P◎ 、 、 、㌔00 璽1；δvOO㌦ン 鼎欝 、、 _ 。 i． ；欝 ；1饗誉 δ，て｝，63㌧f，δV＄10 ＼ 鎗6鼠δV130 姿︸1 P1 Pi eline O 13 盾鱒ﾇ一一…一x一一 （c）One slice data of a volume fb∫もhe convoluも三〇R input・ ／ ％ To ↓↓↓4 b B →6 →d （d）Ariもhmetic昼葺it iR the pipelined co箆volution・ 図4．5：3×3×3領域の4並列パイプライン3Dコンボリューション：y＝Np瓢4 Cρ 十← 0ρ λ ﹁ ゑB君♂ ︵．Z︵φ4 く ω⋮ Dn ．嗣． む ハ （a）Paralel pipeli鼓e convolution． ω帖 匝］jor k−delay ：N unitもilae delay w ．4 →α り 0 Arithmetic un圭t 塊 陣／ W8 〆 ＾ん† ▼ 〆 ．W8 が ︶ 〆 。／箒贈 ／，d 薗ﾙ／ 擁撚 ／／ 111 D且BOP ．離． む ＝＝＝ 審D．ンW6 ，・てノ 藩、 ユ ⊆O酬一篇一〇﹀⊆OnΨ︵一帽 囹， ．W6 ’1炉 螢O聯⇔Φ﹄＝︶塾螺 W7／ 昌 y＝1Vp特異条件下の並列パイプラインコンボリューシ 1Dコンボ タフロー Location Time 、 ユーン 引 ノー 9Z 向 町 表 4．2： Pipe O 鴎一4，B A A A 嶋黹ｿ，b 2 ％一AB 嶋黹ｿ，ろ 一α，6 4 既一4，・B 嶋黹ｿ，ゐ 勛黹ｿ，6 嶋黹ｿ，ゐ （1†0†0†） i100）， @ 一 C （バ ノ ム320），（2†2†0†） i6i6），（・†・†・† A A A i100） @ ｝ （2†0†0†） 鯛，晒†が） A A A i200） @ 一 （1†o†o†） C 一 （ii6），（・†・†・†） A A A i200）， （2†0†0†） @ 一 C ｝ 0倉6），（3†2†0†） iii6），（・†・†・†） A 《 A i200） 『 C 一 （3†0†0†） A A A （2†0†0†） i300）， @ 一 C （ム ム210），（1†・†・†） A A A （3†0†0り i300）， @ ㎜ 一 C （0†0†0†） C C 一 ＾念6）， （2†3†0†） ＾36）， （3†3†0†） iム ム バ320），（3†2†0†） iム ム ム020），（0†2†0†） i バ ム120），（1†2†0†） i6i6）， （1†1†0† iii6），（2†1†0†） iバ ム パ210），（3†1†o†） i100）， （3†0†0†） A A A i200）， （0†0†0†） A A A i300）， （1†0†0†） （3†0†0り i000）， @ ∼ 一 （バ ム310），（2†1†0り A A A （0†0†0†） i000）， @ 一 26），（0†2†0りA A A （2†1†o†） （ム パ 230），（1†3†o†） A A A A A A 一 C 含6），（1†2†0†）A A A （3†1†0†） i A A A220︶， A A A︵310︶， A ︽ A︵000︶， 嶋黹ｿ，6 一α，6 ｨ一α，6 A A A Pipe 3 ︵310︶， A A A︵000︶， ％一・4，B （6i6）， （3†1†0† Pipe 2 Pipe 1 ︵210︶， A AA︵300︶， ︸ 3 （0†0†0†） ｩ 一 14 ンの構i成 ンにおけるサンプル位置およびシアー位置のデ口 咽，酬） 1 ヨ 4．4。 （1†0†0†） C A A 0）， （0†3†0†） @ （2†2†0†） @ （o†1†o†） （2†0†0†） 15 4．5。コンボリューション領域 4．5 コンボリューション領域 提案するアーキテクチャはメモリ部と並列パイプラインコンボリューション部を対 とする。このため，1パイプラインは1ボクセルデータをメモリモジュールから読み 出すのみで，隣…接するパイプラインと横方向の通信によりコンボリューションに必要 なボクセルデータを送受し，1出力を出す．メモリ部にパイプラインが固定して接続 しているため，ボクセルの読み出し順序は変えることができないが，各パイプライン に割り当てるサンプリング位置色ブ，初は自由に制御可能である． 図4．6は読み出すボクセルとその出力の関係を示した模式図である．図は並列度 瑞＝4および領域．M瓢3の場合を図示している．サンプリングに寄与しない出力は 図に示すようにENABLE／DIABLEフラッグによりピクセルメモリへの書き込みが禁 止される． Slice PoPIP2P3Po PIP2P3PoPIP2P3PoPI P2P3 PO Ti Pn：Proρes§ing Plpellne n P1 P2 P3 Convol登tion PO ⊥：Disable P1 P2 PO P2 PO @P3 ま ：Enable Base plaRe x：Sheared voxe1 ●：Resampled data 図4．6：パイプラインが読み込むボクセルデータとその出力の関係 16 第5章 提案するアーキテクチャ 5．1 スキュードメモリ構成 メモリに格納したボリュームデータを視点位置に係わらず同時読み出し可能にする ボクセルのメモリ格納方式がスキュードメモリ構成國である．メモリの同時読み出 しを可能にする際，簡易な方法として用いられる，視点方向に対応したメモリの重複 した保持が必要ない． 今，パイプライン数が罵本でボリュームのサイズがy3の処理を考える．このと き，論理アドレスσ，ゴ，紛で規定されるボクセルアドレスは，実メモリモジュールの モジュール番号％とモジュール内のメモリアドレスちへ，次の式により変換される。 πP ＝ mmodハ多， ②P驚 L呵1陽」＋ゴy／A㌃＋たy2／1％， （5ユ） （5．2） ここに， ？γ∼・＝（￠十ブ十ん）mod y． （5。3） 図4．5（b）右にボリュームデータを構成する1スライスをスキュードメモリ化して 保持するメモリ構成を示す． 5．2 一般条件下で動作する並列パイプライン3Dコンボ リューションの構成 通常ボクセルー辺のサイズyはパイプライン数！協より十分大きいが，前記した3 D並列パイプラインコンボリューションはy＝瑞の特異条件に対応した構成である． ここでは，特異条件下の構成を元に，一般の条件下で動作する構成を導く． 図4．2に示すように，スキャンライン状に並んだボクセル列をパイプライン数1％ を単位として折り返すことにより，全てのボリュームを読み出すことが可能である。 この「折り返し」を用いて，特異条件下の構成を一般条件の構成に拡張できる．この 「折り返し」は，前記アーキテクチャに，新たな遅延器と関連の仕組みを追加するこ とにより実現できる． これらは，「左折り返し遅延器」，「折り返し遅延器」，および 「セレクター」である．図5．1に，この仕組みの導出過程を示す． 図で示した導出は，y＝8およびハ争＝4の条件での導出であるが，導出は一般性 を失わない。図5ユ（a）は，「折り返し」を用いない実現法を示す．図5．1（b）は，（a） にダミースロットを設けて，入力データを遅らせた状況を示す． 図で示すように左 5．2．一般条件下で動作する並列パイプライン3Dコンボリューションの構成 17 側半分のボクセルデータの入力時刻は右半分のボクセルデータよりも1単位時間早 い． このデータ到着時刻の相違は遅延器で補償できる．図5．1（c）は，「折り返し」 により，ダミースロットが埋められることを示した模式図である。これにより，無駄 時間が解消されている．以上の説明から，「折り返し遅延器」の遅延時間はyおよび 瑞によらず常に1単位時間である．これと対照的に「左折り返し遅延器」の遅延時 間はγ／ハ争である。 図52にy≧1％に対応する汎用3Dコンボリューションの4並列での実現例を示 す．この構成は，4並列であるため図4．5で示した特異条件化の構成から「ゴ遅延器」 としてγ／4の遅延時間，防遅延器」としてγ2／4の遅延時間に変更している．また， 「折り返し遅延器」および「左折り返し遅延器」が追加されているのみで，基本的な 構成に変化はない．パイプライン数を飾とした，一般条件化での各遅延器の遅延時 間の一覧を表5ユにまとめる。 表5．1：データの次元yおよびパイプライン詩意と遅延時間の関係 Location of delay The nu：mber of unit−time 以下に図で示した並列パイプライン3Dコンボリューションの動作を説明する． ・4翻rε38（穿飢においてボクセル（0，0，0）を初期値として茗アドレスの増分鱗を用いて ボクセルアドレスσ，プ，紛を発生する．このとき盛方向のアドレスがyを超えた場合 は，ゴアドレスが1増加，同様にブ方向がyを超えた場合はんアドレスが！増加する ようにして（y−1，V−1，y−1）までアドレスの更新が行われる． 物理メモリアドレ スは論理アドレス＠ゴ，紛を用いて，式（5．2）により求められる． 同時に，シアー計算σ，ゴ，初→（ゼ†，ゴ†，ん†）がオンラインで3んeαr部において行われ る． また，同ブロックにおいてω，プ，ん†）を用いて（ゼ，ゴ，紛が計算される、 パイプライン列が直結されたメモリモジュールからアドレス＠あ紛を起点とし て，ボクセルデータ列鷲，蜘玲1瀞…砺鶴一1，帥を同時に読み出す。また，読み出さ れたボクセル値，サンプリング位置＠ゴ，為）…（σ十瑞一1），ゴ，紛，およびシアー位置 （盛†，ゴ†ラ為†）。・・（（野馬1＞≧｝一一1）†，プ，為りがコンボリューション部のパイプラインに入力され て，コンボリューション結果が出力される． コンボリューションからの出力はスキューがかかっているため，4e3舵ω部において σ，凶）を用いてマルチプレクスすることによりスキューの補正が行わる．この補正後の 出力がレンダリング部への入力となり平行化された光線として重畳処理（Composiもe） が行われれ，最終的なベースプレーン上の画素値となる。 5．2．一般条件下で動作する並列パイプライン3Dコンボリューションの構成 18 V710 VO10 V110 V210 V310 V410 Vち10 V召10 VOOO V100 V200 V300 V400 V500 V600 V700 0 0／1／0／0／0ノソ0／ W ㊥寺 壱 寺 壷 ◎ 壷 壷 （a）No振）粟diR9・ V310 V410 V510 V610 口 Unit V710 VO10 V110 V210 − time V400 V500 V600 V700 delay VOOO V100 V200 V300 隔 ．Oo m♀ノ 0ノ．0／0／0／0ノ W l ｝ 1 寺；◎ 重 ◎ † 引 （b）Ti狙ing s膿・f i叩礁もdぬwith delaエ 闘 I」e：既fblding delay 2 unit time delay V310 V410 V510 V610 V710 VO10 V110 V210 V400 V500 V600 V700 VOOO V100 V200 V300 ロ 0／0／0／0／ u，nit time W Folding delay delay ヤ ⑨ Selector 寺 毒 寺 寺 （c）F◎lding a string of vQxe玉s wiもh 4 pipelines． 図5ユ：折り返しにともなう「折り返し遅延」および「左折り返し遅延」の導出 y＝8およびA秘＝4として説明 52．一般条件下で動作する並列パイプライン3Dコンボリューションの構成 19 Address Pipehne−O Pipeline4 Pipeline−2 Pipeline−3 Gea。 ijk M M M M Shea；＝＝ゴ＝二 ＝」＝二‡ ＝；二＝‡一こ二r一いl Skewed Me憩ory lO／l lO／； 10／l lO．／1 蘭 恥 が’ 曲 〆プ 、く・ A， 』一 ，、W1 ガ／〆灘w1 〆ラ『 ％ }｝「 一∴柄一・ W2 、く． 《・ 一泌一十一一一」 ㎞｝一 嚠鼈鼈黹i ♪ 声 ／Ψ4． ／睾4〆／ V／4 ’一 ，：w4 ，W4 ノ ノ 自 V／4 W5 ／ To V／4 ／From． Y ↓〆（§ノyW3 鴨 …｝ ／ V2／4 ノ ／ ／ ／ Dク W8 ／ V2／4 梶／4 疑ンw6．農 鵠 ⊇③ダ 葛 8 ．Wブ 壱Q 、W7 聾 W8 V2／4 ／ ま臼 ／ 、W7 delay ゆ ↓ む 」膨” To delay き 覇窪 ／v2／4． r ÷ W7 Unit time nunit ti拠e ！ ／ 中 ／ ノ ／ 4’ P鳳麟 V2／4 delay jor k−delay W6： W6； ／ To ：Foldi難9 匝 撃aw一り 〆 β W7 ∫§タノw4 〆⑤ノ f ノ 寺 〆 専 ！ W6 職 ／ 』一㌧十一一一， 恥∼㌦†一一一， 声” delay ・て 響く／ ”卸臓 コ Lel既丑）1di丑9 delay V／4unit ti獄e V／4 ／：From W51 W51 W5 ・で 〆③ノ ，鴨 弊／ 」匡” ノ ／ 庸頃自 、wヨ 、鴨 ／ W4 ノ 戸 To ％ 袴 ”一 声” ．驚 ￠O圃ρづ一〇﹀煩◎Q︵HC繭 w2 ｭ．W2 W1 聾 W1 ，，，W1 コー 〒 む ゆ’ 頃 To メ 鴨 苑 ’＝御■ ・。 ㎎ V2／4 む 矯溢ノw7 篇③ン 塊 ← ← ← ← Deskew（Multiplexer） 〆⑤6 Selecto：r Resampled Data 図5．2：3×3×3領域の並列パイプライン3Dコンボリューションの構成 y》飾に対応，1協＝4の例 一般条件 20 第6章 提案アーキテクチャの評価 6．1 レンダリング時間 実用的なボリュームサイズに対する提案アーキテクチャの映像発生時間とパイプラ イン数の評価を以下に行う． サンプリング時間およびレンダリング時間は完全にパ イプライン化可能であるので，パイプラインの刻み喚問はメモリの読み出し時間監 まで短縮可能である．このため，映像発生時間のボトルネックはメモリからのデータ 読み出し時間と考えられる。 今，y3をボクセル数，1％を処理パイプライン数，1Vノを1秒間に発生するフレーム 数として議論を進める。1秒間に計算が必要なパイプライン当たりの総サンプル数 N，は次式である． N8＝y3Nノ／呪P． （6ユ） また， N8ク賑≦1． （6．2） であることを用いれば，最大のボリューム次元γはパラメータ賜，1V！および瑞を 用いた次式となる． τ／≦ 3ハ㌃，／（ノV∫窺）。 （63） 125MHzのSDRAMを用いるとして窺＝8nsと仮定して計算したボリュームの次 元yとパイプライン数罵およびフレーム表示速度1＞∫の関係を図6・1に示す．また， 表6．1にその数値を示す． 以上の試算によれば，提案法は実用的なボリュームサイズである2563ボクセルを ビデオレートで表示可能である． 表6．1：各表示速度（フレームレート）に対応する最大ボリューム次元yとパイプラ イン数鱗の関係 N∫ 1V》（ヲ≠pipelines） （丘ames／sec） 2 4 8 16 32 64 30 203 255 322 405 511 644 20 232 292 368 585 737 10 292 368 464 464 585 737 928 6．2．提案アーキテクチャのゲート数評価 1600 21 l l 1400 1200 Number of volume dimension 露〆． ＿！一……’〆が ！ジ／〈ll二〉二〉： 1000 800 600 ・ノぐ・’＿＿一一！ 60H・一一 400 ：1ク／ 2・H，一一 ・／・ ’〆！！ 30H，一一 ／ 200 10Hz … ” 咽 騨 0 2 1632 256 64 128 Number of pipelinesハ》 図6．1：各種表示速度（フレームレート）に対応する最大ボリューム次元yおよびパ イプライン数篤の関係 6．2 提案アーキテクチャのゲート数評価 図5．2に示した並列パイプラインアーキテクチャのゲート規模を見積る． この規 模見積もりのために，積和計算αω＋6をVHDLで記述し総ゲート数評価の基準にし た． 図6．2に，VHDL言語で記述した12ビット幅の積和計算を示す． 積和計算αz＋6をASICで実現する場合のゲート数を表6．2に示す。表で示したゲー ト数の評価は，論理合成ツールとしてシノプシス社のデザインコンパイラーを用い， 半導体プロセスは0．18μ鵬とした． 表6．2：積和計算傭＋6のASICでのゲート規模 ビット幅 必要ゲート数 250MHz 200Mhz 100Mh裟 10 2706 一 鴨 12 3715 3325 1928 16 8165 一 硝 Des三gn Compiler w誌h O。18μγ㍑process library 表6．2で示したゲート数を用いて見積もったコンボリューションに必要な1パイプ ライン当たりのゲート数を表6．3に示す．また，ルックアップテーブルおよびFIFO メモリに必要なメモリのビット数を表6．4に示す。 以上の見積もりから計算ビット幅を12ビット，動作周波数100MHzとして4並列パ 22 6．2．提案アーキテクチャのゲート数評価 LIBRARY ieee； USE ieee。s七d＿＝Logic＿1164．aユユ； USR ieee．s七d＿10gic＿ari七h．a：Ll； USE ieee。s七d＿logic＿uasigned．a1：L； ENT工TY 】【npy4 1 S PORT（（：1◎ckin ： ：【N STD＿LOGIC； da七aa ： 11Ψ STD＿：LOGIC＿V鷺CTOR（ 11 DOW麗TO O）； da七a：x： ： 工N STD＿LOGIC＿VECTOR（ 11 DOW聾TO 0）； da七ab ： 工麗 STD＿LOG工C＿VECTOR（ 11 DOWNTO O）； da七ao ： OUT STD＿LOG工C＿VECTOR（ 工1 DOWNTO O））； 副懸Dmpy4 ； ARCHITECTURE ：r七1 0F mpy4 工S SIGNAL dampy ： STD＿：LOGIC＿VECTOR（ 23 DOW麗丁O O）； SIG麗AL da七db ： STD＿LOG工C＿VECTOR（ 11 DOW麗丁O O）； BEGIN PROCESS（clockin） BHGIH IF （clockin，EV猛NT AND c］．ockin 畿 ，1，） TRHN da：mpy ＜讐 dat aa ＊ da七ax ； HND IF； HND PROCESS； PROCHSS（c：Locki：n） B鷺GIN IF （c：Lockin，EVENT AND c：Lockin 竃 ，ユ，） THEN da七db 〈識 da七ab ； END IF； E1懸D PROC￡SS； PROCESS（c：Lockin） BEG工N IF （clocki：n，EVE麗T AND clocki：【Σ 鶏 ，↓，） THEN O， da七ao 〈識 dampy（23 D OW麗丁0 12） 千 da七db 副ΨDIF； 副可D PROCESS； E1懸Dr七1； 図6．2：ゲート数評価に用いる積和計算α詔＋うのVHDLコード： 12ビット幅 23 6．3．スケーラビリティ 表6。3：3Dコンボリューションのゲート数（1パイプラインあたり） ビット幅12 ビット ブロック名 ゲート数 i方向 j方向 k方向 12x10＝120 5928 120 欄 5928 5928 （1928x3瓢5784） （5784） （5784） @ A→a：3units （12x4x3＝144） （144） （144） ：Latch：2uni七s 12x2x4x2＝192 24x2x4x2＝384 192 192 384 384 Shear（DDAによる） Ari七hme七ic u．簸i七s @ ax十b：3units Selector：2un．its 総ゲート数 19，752 表6．4：パイプライン当たりのメモリサイズ評価（ビット） メモリ数（ビット） ブロック名 ：FIFO：2uni七s i方向 j方向 k方向 欄 12x2x（256／4）x2 3072x256 P2bi七s wid七h @ ＝3072 Weigh七七able：3uni七s 256x8x3 @ 8bits width @＝6144 総メモリ数 6144 ≠V86432 6144 807，936 イプライン3Dコンボリューションを実現するには，約80K：のゲート規模および3．3M ビットのSRAMが必要である． 6．3 スケーラビリティ 次の理由から，提案するアーキテクチャはパイプライン数の増加に対応した処理性 能向上が可能である．（スケーラビリティを持つ，） 1）パイプラインとメモリモジュールが直結しているため，パイプライン数の増加は メモリからのデータ読み出し速度に影響しない． 2）サンプリングに必要なパイプライン問のデータ通信は隣i接するパイプライン問で あり規則的である．このため，パイプラインの追加がメモリ読み出し速度に影響を与 えない． 3）コンボリューションのパイプラインとレンダリングパイプラインは直結している． また，コンボリューション領域Mの増加は縦方向に積和計算を追加するのみで基 本的な構成の変化はなく容易に拡張可能である． 6．4．画質 24 6．4 画質 提案アーキテクチャをソフトウエアで模擬したシミュレータを作成し，データフ ローの確認などの方式評価をおこなった．また，画質を比較するために，従来法のレ イキャスティング法を実現した別のシミュレータを作成し，各種のテストデータを用 いて両者の映像を比較した． 図6．3（a）はボクセルサイズ643の不透明ボリュームを用いた透視投影法を確認す る映像である． 視点から近い部分が大きく，遠方が小さく表示されていることが確 認できる．この例では，コンボリューション領域2×2×2のラグランジュ補間式を 用いた。 図6．3（b）および（c）はボリュームサイズが1283の市松模様を持つ不透明のボリュー ムを用いた透視投影映像である．この不透明で空間周波数64施を持つデータはアン チアリアシングを比較するために用いた．図6．3（b）はコンボリューションを行わず 近傍のボクセルをサンプリングデータ（neares七neighbor）として表示した映像であ り，明らかにエリアシングの影響が現れている。 図6．3（c）は3×3×3のコンボ リューション領域を持つボックスフィルターを用いた映像表示であり，コンボリュー ションによりエリアシング除去が行われている。 図6．3（d），（e）および（f）は2563ボクセルを持つLacrou七eが実験に用いたエンジン ブロックデータ［6］を用いて表示した映像である．（但し，オパシティテーブルは一部 修正した．）図6．3（d）は透視投影による映像であり， 6．3（e）は並行投影による映像 である．両映像とも，3×3×3の領域を持つラグランジェ補間式を用いた． 図6．3（f）はサンプルオーダスキームに基づくレイキャスティング法による映像で ある．比較を容易にするため，256スライスを用いてサンプリング数を調整した映像 である． 図63（d）と（f）の映像比較によれば，両者の違いは見られない． 25 6．4．画質 雛 ’壁i ． ：邸 図6．3：シミュレータを用いた映像による評価 26 第7章 まとめ 実時間ボリュームグラフィックスの高速表示アルゴリズムであるシアーワープ法にお いて透視投影映像を生成するために必要なコンボリューションのシストリックアレイ 構域法に関して提案した。シアーワープ法ではサンプル点の計算において，視点から 遠いものほど，コンボリューションの対象となるボクセル数が増加する．このボクセ ル数の増加は配線が固定しているハードウエアでの実現において回路規模の増大をま ねき，その実現を困難にしている。 重みがX，Y，Z方向に分離できることを用いることにより，1Dコンボリューション をX，YおよびZ方向にそれぞれに割り当て，これらを直列に接続することにより，領 域Mの3Dコンボリューションに必要なM3個の積高計算を3．Mに削減した． ボクセルのサイズをy3とすれば光線に対応するパイプライン数はy2である．1 パイプラインが単位時間あたりに処理する光線数をyとすれば，擬似的にy本のパ イプラインが必要となるが，実用上，実パイプライン数ゐは五《yでなければなら ない．このため，提案法は擬似パイプラインに折り返しを用いて実用的なパイプラ イン数五まで削減する機構を持つ． 評価によれば，提案法は4実パイプラインを用いて2563サイズのデータをビデオ レート，即ち30Hz，で表示可能である．このとき，3Dコンボリューションの回路規 模は，半導体プロセス0．18μmを用いた場合，80：Kゲートおよび3MビットのSRAM を必要とする程度である． また，提案するアーキテクチャは大規模データに対してパイプラインの増加により 容易に対応できる処理のスケーラビリティを持つ．5123（γ＝512）サイズのデータの ビデオレート表示は32パイプライン，10243（y＝1024）データでは256パイプライ ンで可能である． 実現するビット幅が少ないことが，ハードウエア規模の縮小に有効である．一方， ビット数が減ることは誤差を増加させる． 今後，両者を考慮した最適性の解析的検 討を実施したい．また，提案法の不規則格子点を持つボリュームデータ，即ち格子点 位置が移動する，への発展的適応も研究課題である． 27 22K g ma [1] A. S. Glassner: "PrSnciples of Digital Image Synthesis", Morgan& Kauiman (1995) [2] T. Gimther, C. Poliwoda, C. Reinhart, J. Hesser, R. M5nner, H.--P. Meikze:, and H.-J. Baur: "Virim: A massively parallel processor fbr real-time velume visualization in medicine", Cemputers & Graphics, Vol.19, No.5, pp.705--71e (1995) [3] A. Kauiman and R. Bakalash: "Memory aRd precessing architecture focr 3d voxel-based imagery", IEEE Computer Graphics & Applications, Vel.8, No.6, pp. Ie-23 (Nov. 1988) [4] G. Knittel and W. Strasser: "A compact volume rendering accelerator", In Proceedings of the IEEE Symposium oR Volume Visualization, pp. 67-74 (Oct. 1994) [5] P. G. Lacroute: "Fast volume rendering using a shear-warp facrorizatiolt of the viewing traRsfbrmation", Technical Report CSL--TR--95-678 (Ph.D. Dissertation), Computer Systems Laboratory, Stanfbrd University (Sep. 1995) [6] P. G. Lacroute and M. Levoy: "Fast volume rendering using a shear-warp factor- izatioR ofthe viewing transformation", In Proceedings ofthe ACM SIGGRAPH '94 Conference, pp. 451--457 (July 1994) [7] M. Levoy: "Eflicient ray tracikg of velume data", ACM Transactions eR Graphics, Vbl.9, No.3, pp. 245-261 (July 1990) [8] M. Ogata, H. Ohkami, H.C. Latter and H. Pfister; "A Real-Time Volume Rendering Architecture with ResampliRg Scheme fbr Parallel and Perspective Projections", Proceedings ofthe ACM/IEEE Symposium on Volume Visualization, pp. 20-29 (Oct. I998) [9] R. Osborne, H. Pfister, H,. Lauer, N. McKenzie, S. Gibsell, W. ]ilatt and T. Ohkami: "Em-cube: AR architecture for low-cost real-time volume render- ing", IR Proceedings ofthe 1997 SIGGRAPH/EUROGRAPHICS Workshop on Graphics Hardware, pp. I31-138 (Aug. 1997) 28 pe] H. Pfister and A. KaufuLarc "Cube-4: A scalable architectrtre fbr real-time volume rendering", In Proceedings of the ACM/IEEE Sympesium on Volume Visualization , pp. 47-54, San Fransisce, CA (Oct. 1996) [11] H. Pfister, J. H. Hardenburg, H. Lauer and S. Sailor: "The VolumePro Real-Time Ray-Casting System", In Proceedings ofthe ACM SIGGRAPH '99 Cenference, pp. 131-138 (Aug. 1999) [12] L. Westover: "Footprint evaluation fbr volume rendering", In Proceedings ef the ACM SIGGRAPH '94, pp. 144-153 (Oct. 1994) [13] L. Williams; "Pyramidal parametrics", In Proceedings ofthe ACM SIGGRAPH '83 Conference, pp. 1-11 (July 1983) 第II部 空間および光線分割による 並列ボリュームレンダリング・システム 30 II部あらまし 大規模な科学技術計算の高速可視化では，大容量のボリュームデータ（10243以上）を 取り扱う必要があり単一のレンダリングエンジンでは処理性能が十分でない。大規 模データの実時間表示，15フレーム／秒程度，に対応する並列ボリュームレンダリン グシステムを提案した．提案法はボリュームを部分空間に分け，各部分空間にPCク ラスタを構成するノードを割り当て，ノード上のソフトウエアによるレンダリングま たはレンダリングエンジンで2次元部分映像を発生させ，これを合成することにより 全体映像を得る．ソフトウエアレンダリングに関しては光線の連続性を仮定しないの で各サブボリュームのレンダリング部を独立したシアーワープ法で実現でき，従来法 であるRaycasting法との性能比較では約4倍の高速化を達成している． 並列度を増せばレンダリング時間は並列度に応じてほぼリニアーに減少するが，部 分映像の重畳に伴なう通信により合成に要する時間は増加する．評価実験によれば， 並列度40ノード程度から，並列度の増加により全処理時間は逆に増加を始める．この ため，メッセージパッシング（MPI）のみを用いたソフトウエアによる部分映像重畳 では，ビデオレートでの映像発生はできない．この問題を解決するため，ハードウエ アで部分映像重畳を行う方法を提案し，試作卜した．試作システムは，高速エンジン および重畳ハードウエアを用いることにより，10243ボクセルのボリューームを約15H2 で表示可能である． シミュレーション対象を部分空間に分割し，各部分空間に計算能力の高いPCを割 り当てるPCクラスタによるボリュームレンダリングシステムの実現は，計算と映像 発生を密に融合するものであり，大規模科学技術計算の可視化あるいは，医療分野で の3次元可視化に寄与するものである。特に，人間の操作により対象物が変形するな どの計算過程を表示可能であるので，本格的な手術シュミュレ心月の実現に応用が期 待される． 31 第1章 はじめに 科学技術上の諸問題を計算機を用いて解き，結果を直感的に把握したいとの要求，あ るいは高度医療におけるMRI， CT，超音波診断装置などのデータの表示，などから 大容量の3次元情報を可視化する高速かつ安価なボリュームレンダリングシステムが 必要とされている．ボリュームの可視化は，1）ボリュームが物質の光透過率などの情 報を3次元空間内の格子点上に持つため大量のデータ処理を必要とする，2）光の減 衰を光線の経路に沿って一次元で計算するので，比較的単純な積和計算の繰り返しで ある，などを特徴とする．しかし，データ量が膨大であることから，高速表示には， 高価なスーパコンピュータや専用ハードウエアが用いられている． 本論文は，対象ボリュームをサブボリュームに分割し，各サブボリューム単位に独 立した局所映像を発生後，隠顕関係を考慮し重畳して映像を発生する「並列ボリュー ムレンダリング・システム」を提案する．また，市販のPCをクラスタ化して提案法 を実現したプロトタイプシステムの性能評価を示す．シアーワープ法同を分割した 各ボリュームに適用する，提案の「マルチプルシアーワープ法」を用いたため，提案 法はRaycas七ing法に比較して約4倍程度の高速化を達成した。一方，並列度の増加 は重畳時間を増加させる．この時間を並列度との関係から評価し，ビデオレートでの 映像発生を可能にする：重畳ハードウエア装置の試作を行った． 本論文の構成は，2章並列ボリュームレンダリング技術の現状，3章並列化の原 理，4章提案法のソフトウエアによる実装，5章性能評価，6章試作ハードウエア， 7章まとめからなる． 32 第2章 並列ボリュームレンダリング技 術の現状 ボリュームレンダリングは，ポリゴンによる映像表示と異なり，本来明確な形状を持 たないあるいは通常の状態では形状がない3次元的に分布した情報から，適正な戦略 により選択・抽出した情報に，異なる色あるいは輝度を与え可視化する技術である． ボリュームデータの対話的な速度での表示を可能にする方法としては，専用ハードウ エア（H／W）を用いる方法［3，4，5，8，9，10，12］，複数の演算装置を用いてソフトウエ ア（S／W）でレンダリダを実現する方法［6，15，16，7］などが提案されている． 専用H／Wでの実現は，高速であるが処理の柔軟性にかける．例えば，PCクラス で初めて商用化を実現したVolumePro500［10，12］では，平行投影のみが対象であり， また最適化の一つであるアーリー・レイターミネーション（Early ray termination）が 実現されていない． いっぽうS／Wでの実現では，一般的に処理の自由度は高いが計算量が膨大であるた め速度が遅い．このため，高速化を図る方法の一つとして並列処理が用いられる．こ の方法における代表的な提案である”Binary−Swap Co：mpositing”法［15］は， CM−5お よびワークステーションによる並列処理に関する提案で，サブボリューム映像の重畳 を並列処理するところに特徴があるが，光線の連続性を仮定するため投影法は並行投 影に限られている。”The U1七raVis Sys七em’ラ［16］はPentium IIIによるmu1七i−processor platform．sを対象にした方式で，キャッシュメモリの積極的活用および命令レベルでの 最適化を特徴とする．しかし，高速化のための各種チューニングがPen七iumlII固有 であるので，処理の汎用性にかけると予想される． ”WireGLG”［18］は，タイル状に配列した大画面のレンダリングを可能にする分散 グラフィックシステムであり，商用PCを高速ネットワーク（Myrine七）で結合したPC クラスタを用いて既存のアプリケーションをスケーラブルな解像度で対話的速度で実 行する．スケーラブルな解像度を実現するためにネットワークのトラフィックを最少 化するソートアルゴリズムを特徴とする。 表示はOpenGLを用いるためボリュー ムを対象とした処理では，3Dテクスチャによる擬似的なボリュームレンダリングと なる。 33 第3章 並列化の原理 本研究における提案法は，全対象空間（ボリューム）を部分空間（サブボリューム） に分け並列処理により各々の二次元映像を発生後，この映像間で重畳（Composite） を行ない最終映像を得る。 S．Mohar［17］らは，グラフィックにおける並列化法を，ジオメトリック処理および レンダリング処理に対するシステム内のSor七の位置により分類する方法を提案し1， その分類によるシステム構成の特徴を解析している．この分類によると，本提案のシ ステム構成はSort−1as七アーキテクチャに属す．最終段のPixe1の重畳形式はSL−sparse とSL−fu11の中間に属し，処理は透明度を用いた二次元画像の重畳であり単純で規則的 である．システムの特徴は，ノードプロセッサの処理はレンダリング全体を含みユニ プロセシングと同一であり，ロードバランスは比較的良く，線形のスケーラビリティ が得られやすい反面，最終段のpixe1転送のトラフィックが一般的に大きくなる． しかし，本提案法の重畳方式は前記のように単純かつ規則的であるので処理時間は大 きくないと予想される． 3．1 空間分割による並列化 全対象ボリュームをサブボリュームに分け，サブボリューム単位で二次元映像発生を 行ない，隠顕の優先順位を考慮して重畳した．この重畳における優先順位の判断には， 空間を分割し視点に近い順に優i先度を付する方法であるBinary Space Par七itioning （BSP）法をサブボリュームに適用した．全体をサブボリュームに分割して処理するた め，計算ノード内のメモリを一定とすれば計算ノード数の増加に伴ない，従来困難で あった大規模ボリュームデータの表示が可能となる． 図3．1（a）に視点と8分割したサブボリュームの隠顕関係を示す．分割は必ずしも2π の分割である必要はなく偶数であれば良いが，後述する理由により処理の負荷を均一 にする分割が好ましい．この隠顕関係（優i先度）を計算するのが，図3．1（b）に示し たBSPである．ツリーの根（ルート）から，各セパレート面を規定するパラメータ （α爲，6π，cπ，4π）と視点位置（￠，，ン，，之，）を用いて，枝選択のためにα罐，＋6紹，＋c罷，＋4η を計算する．（％，6π，cπ）は面の法線，鑑は原点から面までの距離をそれぞれ示す．こ の計算結果が正の場合は，正側の枝（スペース）に分岐することを再帰的に繰り返し， 全ての葉（リーフ）すなわちサブボリュームに優先順位を付番する．図3．1（b）は，図 3．1（a）に示す位置に視点があるとした優先番号の付番結果を示す．図中のちはサブボ リューム瑞から作られた二次元の部分画像を示す． 1SOftが，ジオメトリック処理の前のものをSOfも一貴rsも，ジオメトリック処理とレンダリング処理の 間のものをSorも一磁ddb，レンダリング処理の後のものをSorも4asもと分類している． 3．1．空間分割による並列化 34 Eye： （x，y，z） Sμ s3挽i彦 微 ％∠ ．B6 拓旺． E @ ’霧 纏 芳笏z 名 工 z 藤彫 霧笏z 聯髪身1笏 ル．笏捻5 託 ノ aiX＋bly＋∼コz＋d ＞0 zzz％z ／隼s韮 誘 ・B8 S ’「∠ 狽a4 Z影 Cノ27856 髄い2董41目3151716・8 P・1・・i重y34’ S Bn：Subvolume n ノ Sn：Plane n （a）Paぼtitioning a vdu瓶e into s篠bvd一 （b） P澱iority caJculatio鷺fk）r もhe eye 犠mes 茎）oiRt usi麓g Binary−Space−PaTtitio職ing もree 図3。1：BSPを用いた隠顕関係を示す優i先順位の計算 図32（a）は，二次元部分画像を重畳する重畳木（COmposi七ing Tree）を示す．図 3．2（b）は，重畳の式を示している．A側の色為とB側の色1βをA側の透明度・転に より重畳している．この場合A側の画像がB側の画像の手前（即ち優先度が高い）を 前提としている．図3．2（c）および32（d）は重畳木の階層毎にどのように重畳が行わ れるかの模式図を示す． 3．1．1 光線分割による並列化 図3。3（a）に，光線がボリュームを通過し，スクリーン上の該当画素位置（p，のに 入射される様子を示す．このとき，スクリーン上の（p，g）画素位置における輝度仙 は，式（3．1）［21により与えられる． ち，一鷹五（・）・…∬聯d・ （3・1） ここに，μ（オ）は光線上の位置オにおける減衰比，双3）は同様に位置5における輝度 を示す．また，50は光線の開始位置（パラメータ形式），51は終了位置をそれぞれ示 す．式（3．1）を離散化し，△3＝ムォと仮定すれば式（3．2）となる． 秘：罫二1雛萬一3△の （3．2） ここで，αゴは透過率を示す． 上式を展開し，図3．3（b）が示すように，為一1と為の間で光線を2分割したとすれ ば式（3．3）が得られる． ち9＝139＋139・孟1 、4 驚 。41η42 P9 （3．3） 3．2。Mul七iple−sheared重畳法 E 工．． ．笏 ｶ． ％多 笏 男zz ％B6z 笏擁 B穫 S％ 笏多笏笏B2z尾 鄭 笏吾5z’髪 35 Ic Ac Blending Equation ∠ 解 狽a8 S Ic＝AAII‘IB幸IA 笏B4笏 纏笏拶 S3娩3髪％ 笏 「 S Bn：Subvo蓋Bme R ノ Sn：Plane n ／＼ IA IB A♂Aざ1‘AB AA AB （a） Com．positi簸g t￡ee fbr sepa，raもed s曲vol縫mes （b）Compositing eq瞼tion fbyもw◎ pixels Il牽至3牽12一ト14＋至5一ト17や16＋夏8 ↑ …i恥曝酬翻 癖一一｛無 （c）Eight 1・cahm哉ges wiもh （d）Compositiag loacahm− regayd to occlusio職 ages 図3．2：並列処理のためのBSPを用いたボリュームのサブボリュームへの分割 ただし，．41＝αoα1…偽＿1，。42＝偽αた＋1…αN＿1である。 これは，光線の減衰計算をサブボリュームごと独立に行ない，それぞれの最終結果 弓，および13，を透過率を用いて重畳すれば良いことを示す・上式は，2分割である が任意の分割数に対しても成立する．導出の詳細を付録に示す． 3．2 Multiple−sheared重畳法 Raycas七ing法は，ボリューム全体に対して連続した一本の光線を仮定して処理を 行なう．発生映像が必要な精度を持ち，この精度が理論上保証されていれば，個々の 光線の連続性は問題にしない重畳法を提案した．メモリアクセスの規則性を利用して 高速化を図るボクセルオーダ・スキームでの並列処理においては，処理順序は光線に 沿ったサンプリング点の順序でなくボクセルの並びの順序になるため，連続な単一光 線を仮定し難い．本提案による方法では光線の連続性を仮定しない． 図3。4に本提案（Multiple−sheared重畳法）の原理を示す、図3．4（a）はRaycas七ing 法を示す．透視投影の場合，アンチエイリアスの観点からサンプル点が視線から遠く 3．2．Mu1七iple−sheared重畳法 S O 36 Ray S 玉pq A pq S玉 SAV O Ray SCreen Volume k−l k Ii Al pq ひq N−1 12 A2 pq pq （a） CasもiRg 翫 ray into vo1− （b）Split a ray intoもwo pices at p◎si− ume tionゐ一1 図3．3：並列処理のための光線分割 なるに従い，サンプル値の決定に広い範囲のボクセル情報を用いる必要がある、図 3．4（b）は，光線を常時，基軸（x，y，z軸のうち視線に最も並行に近い軸）に平行とした 場合の光線に対するボクセルの相対位置を示す．この性質を用いて，レンダリング する方法がシアーワープ法囹である．提案法は，図3．4（c）に示すように，各サブボ リュームを視点に応じてシアーし2，各々の2次元ベースプレーン映像を発生後，ベー スプレーン間で重畳を行ない最終ベースプレーンを作り，この最終ベースプレーン をOpenGLのテクスチャ・マッピング機能を用いて歪み補正を行ないスクリーン上に 正しい映像を得ている． 2リサンプル時にサンプル点とシアー後のボクセル位置の距離に応じた重みを求めるのに用いるの みであり，実際にボクセルの空間位置を変化させるものではない． 32。 Multiple−sheared重畳法 37 R ay S コ Rays ？↑ ÷÷（P，q，k） l l ， ?＊ｘ? ■ ●● ’嘗崩暑鱒掩鱒 ⋮⋮ ● ●o ：， ◎■ ● @⋮層＊xxxx ・ 怐@Oo x x ● ● ■ iBase iP玉ane 卿。：●⋮ 一 3 o o ●『■ ?；xxxxx 魯詫xxxx c 響 ● o oo● ● ・⋮◎o＝ 幽？⋮ 言 x…双xxx ＝o＝o ⋮ 督 撃 ロロのコロロコロサ サも ■ 曾 ・ ?ｘｘｘｘ? … … 畳 ＝＝： 準含TLOーユ●一血了一1▲TわーーX一 一﹂再一X一馨一寧輩虫 噛嫌●8曽噂”“6夢 ⋮﹂ l l 書⋮露 け ● ［ 噛O o 一 噂 ㌔ 鱒・ ゆ サ の ぼ ●● ● ● ● o ● xx；x 醤 x x x ● ● o ● ● 層蝿x堆xxx 竃 ； ● o o ● ● …x 埴x x x plane ● ● ● ○ ● o’ ＄ 其x x ● ● ● o ixxx ・1 ＝ 2 xx瓢 ● ● ● ●● x：x x x ：Base k ．屡﹂ コ ●● ● ● XX x xxx喩 コ 守 ●o●● ●XXx Xxxx難 鷺●O o ●・X Xxxx繁 コ ■● ●O X Xx xx鷲 O ● ● ● O■ m ひ o 。● xxxxx瞥 X コ X X X ◎O● ●OO■ X X 一 X X X 瓢 ◎●O● ●OOX X の ● XXXXXX ● σ ㍗駕xx x x x ● ■ ●榊 の 脚 ●o O・ 瞥 XXXXX ● の ㊤ 0 輔 聯 O● 瞥XXXXX の 暫 xxxx⑦● ● OO ロ ■● ● 榊 OO ㍗駕x鼠xxxx■ 潔一1峯一←轟閲一窯lI￥一X5窯牽零辱Og−O曝 ロ XXXXXX OO ●● O V o1 U m e _ ParaUelized x x x 一 ．／Image On screen Eye Eye （b）Mul七iple−shea∫ed （a）Raycasもi箆9 ▼ 朝、 @、 @ 、 @ 、 A 、 @、 、 @ 、、 、 轟 ド の の の の ザの ゆ の の ヘ へ 聾 、、 、 さ ヘ へ 婁 ＼、、 、、 1 、、 、 1 ’、、 ’、 、 ｛一薗、ヤP謄、 ＼毫 一 ﹁ーーー1奮 Base se Plane A 、 ＼、 @ 、 門ドL F1 ・ @ ， ■ 「 ■冨冒一 r一曽襯 踊 ヘ へ 、、 、 、、 、 、、 、 、、 、 、 、 、、 、 、 k一一＿一Σ・一一一＿∴ ∵僻’菰…’、 5 、、 、 撃 、、 、 、、 、 、、 、 @ 、、 、、、 へし へ 」 、、 、 奪 、、 、 蓼 、 、 い 願1一一一一上、 Base Plane ，㌔ ㌔㌧卜．∵，㌧， ㌔ 、 、 ．・『・．∵『・『・E・．・ ・：・ 、 、 ：’：・：：；：1：：：1：：：：：＝・、 、 1 ・：・：・：ζ・1・．，・：・：・、 、 c…………i…ヌ ・’ 堰Fi：i二 iiiiiiiii L ii⋮翼・：：：；：：﹃ ：：1：：：ll：：：：：ll：㌔、 、 ：…iiiiiiii鍵 T 奪 ：・：・：・：・：・：・：・：・ 、 、 驚 ∵ ．㌔∵【㌧∵． 、 r鱒鱒幣偽 Y 、 ⋮ 9・ マ．㌦曇り ．，． 、 Composite 胴廟 監鞘 一 “ 桐 備 一 ρ 齢 轟 ：；’；1：’：’；：：：：’ 、 て一隔麗璽卿 ︸ 、 塾 、 （C）Image COmpOSiもing 図3．4：Multiple−sheared重畳法：サブボリュームに対応する二次元ベースプレーン 間で透明度を用いた重畳を行なう 38 第4章PCクラスタを用いたソフトウ エアによる実装 4。1 システム構成 提案法をPCクラスタ上の並列処理により実現した．レンダリング処理および重畳 処理等の処理は全てソフトウエアで実現している．図4．1にPCクラスタの構成と各 ノードの受け持つ処理を示す．各PCはサブボリューム単位のレンダリングおよび重 畳処理を行なう．各PC間の通信はMPI（Message Passing In七erface）を用いた．物 理的通信の高速化を図るため，PC間接続はMyr三net（転送速度1Gビット／秒）を用 いている。図4．2に並列ボリュームレンダリングシステムとして構成したPCクラス タの概観を示す． Server ＊Camera CRT Ｕser imerface 魔sex瞳e @mappi籍9 OS： My崩et kinux÷SCore Hlgh speed Network switcher omp康lng mode＃1 Node井3 N（虹e井5 NG6e＃7 ＊Subvol縫凱e ＊Subvolほme qendereぎ qeBderer qendereぎ qendeぎer 魔bom籍osi毛e 魔bomposite 魔bom閃slξe 魔bomposi芝e ＊S組bv◎k…me 零Subvo1Ume N◎ごe存2 ∼》Gde拶 No耀e井6 NGde拶8 ＊S疑bVQI切me ＊S顯bvolume ＊SubVQlume qe轟defer qendeぎer qe脆derer qe鐵dere罫 魔bomposi芝e 魔bomposite ?Ｃo脚slte 魔bomposi｛e ‡Subvolume 図4．1：ソフトウエアによる並列ボリュームレンダリングシステムの構戒 構成したPCクラスタ（16ノード）および要素PCの性能諸元を表4．1に示す． 4．2 処理概要 図4。3にMu1七iple−sheaτed重畳法の処理フローを示す． 4．2．処理概要 39 図4．2：PCクラスタを用いた並列ボリュームレンダリングシステムの概観 表4．1：構成したPCクラスタおよび要素PCの性能諸元 CPU Pen七ium III 700 MHz（8PC x 2CPU） Memory 512MB Ne七wor：k Myrinet lGbits／sec OS SCore iReal World Compu七ing Partnership） ：Linux kernel 2．2．14 with XF863．3．6 Graphics API OpenGL and Gt：kGL，area 40 4．2。処理概要 ／／一一一＝＝＝謹謹謹＝＝醤鶉謹謹塗謹謹 サーバ処理 繍需器一＝＝謹讐蕊一一＝謹謹讐＝＝謹＝一＝謹醤＝＝／／ ︷ PτocessSe3vez（） Se駐dVoユ㎜eDa㌻aO； ルノードにサブボリュームを送る。 〃フレームの繰り返し． fo驚（；；）｛： Bmadcas七Ca臓eごa翫。（）； 〃視点情報などをノードに送る． Receiマ③BasoPla夏00； 〃藻麺冬ベースプレーンの受け取り 〃全体ベースプレーンをテクスヤマッピングのプレーンとして 〃ベースプレーンの内容をテクスチャパターンとしてテクスチャ 〃 マッピングする．（OPG纂GLを用いた） Tex七生τ6頚appi蕊90； ︸ ：｝／／無1製ループ 〃講一一一一篇一＝＝＝開雛鵠ノードの処理 一一一＝訟一一一一一一雛謹瓢一鵠＝〃 ︷ P驚ocoss翼。δ⑤（） 〃 サブボリュームデータを読む。 R③a（まS篭わvo1「鵬e（） 〃フレ∼ムの繰り返し． foご（ ；；） ｛： 〃サーバからカメラ情報などの受頭を待つ． 闘rai七Camo2｝aユヨ七c（）； 〃ベースプレーン（BP）の初期化 Cloar8asoPユa纂e（） ； 〃サブボリュームに下り当てられたボクセルを勾」，k順に全てたどる． 〃 （i，」，k）はBPに直角な基線をk・鮎， BPの辺をi，」軸とする右手座標系． 〃 変数も③gin？，ユa鵠？がサブボリュームの範闘を示す。 foτ （ k 繍 1》egi纂K ； k 〈篇 ＝Las㌻K ； k 乎÷ ） ｛ 〃変数upd縞eに更新に必要な起点および変化量などの情報を求める。 〃 （p，儀〉は点（ちあk）がシ∼アされた位置（BP」二〇）メモリ位置） upda七〇 蹴 GeのbUpda薗ヒePa潔a認L（ k ） ； 〃スライスkにおける左上ボクセル位置がシアーを受けて移動 〃 した点のJ座標を起点qとして加算によりアップデートする． 儀魏 up虚aもe・begi蕊S｝≧ea驚e｛ユJ ； fo驚 （ 3謹beginJ ； 」 く訟1as・b3 ； 3亭← ） ｛ 〃 」方向のシアー位趾を変化量の加算により更新する． q，一瓢 黛P〔玉a七〇。doユ七aJ ； P 謹「ユpda七③・もoginShoa訟e（1工 ； fo澱（ ／／工方向の起，【∴〔位置の設定 i 嵩わegin工 ； i ＜篇 ＝Lasも工 ； i÷＋ ） ｛ P・ト繍篭P（王a「ヒe・deユrヒa工； 〃ijkはボクセル位雌であり， 〃変化量により更新 sijkは点萄kがシア∼された位置 ； ijk 篇（ i，j，k） ； sijk蕊（ P，q，k） ／／ ／／ 〃ボクセル位置ijkを用いてボクセル情報を取り出し ，書き込み ︶ 二八 （整数化p，整数化儀）と（p．q）の距離を用いて書き込み情報 の寄与率を考慮してpixoエを求める． p加。ユは為g，b，aで構成。 shoa泌．Resa戯】plo麗i・ヒhCo＝製v◎コ．u㌻io＝t（ 土jk ， sijk ； ／ ／ −∼／ pi，xeユ． ＝ pixe1（τ，g，b，opac鎚y）を（p遜）位置で決まるべ∼ス プレーンにアルファブレンドで書き込む。 アドレスの計算． ） 寧 si箔e土jk．bP冒i（玉・bh ＋ iユ七（P））＊4 3 P皿e斑雛（i纂t（q Pπ匹e職， pix61 ） ； Co加些》osi七￠BaSGPlaぼしe（ ︸ ｝ 〃 i ループの終了 ｝ 〃 j ループの終了 〃kループ0）終了 〃．重畳ポイントがツリーの雨漏になるまで以下を実行する． 窟hilo （ハ〇七Rooも ）｛ RecieveBaseP1孤G O； 〃8Pを受信する． L。c磁eτg￠BaSGP1㎝o（）； ／／受信3Pと自ノードが持つBPで重畳処理を行なう。 s6滅BasePl蝕00； 〃次の重て霧：ポイントに対応するノードへBPを送る。 ｝ ︸ ｝〃フレームの繰り．返し． 図4．3：プロトタイプシステムに実装したMu1七iple−Sheared重畳法の処理フロー 41 第5章性能評価 本提案法およびRaycasもing法に関して，ボリュームデータサイズ，表示画像サイズ およびノード数を変化させたときのレンダリング時間（重畳を含む）および重畳時間 を計測した。表5．1に評価に用いたボリュームデータの諸元および評価条件を示す、 表5．1＝時間計測の組み合わせ条件 表示画素数 実験条件番号 ボリュームデータ 2562 （1） 人体頭部（128x128x120 @ ボクセル） 5122 ニューロン（386x258x197 @ ボクセル） 5122 7682 2562 （2） 7682 また，図5．1に評価対象データの出力映像を示す． 5．1 処理時間 表5。1に示す各条件において並列度を変化させ，本提案法とRaycasting法のレンダ リング時間の比較を実施した．表52から5．3に提案法によるレンダリング時間（重畳 時間も含む）を示す． 表5．4から5．5にRaycasting法によるレンダリング時間（重 畳時間も含む）を示す． いずれの場合もノード数を2，4，8，16と変化させて時間 を計測した。 図5．2（a）に実験条件（1）における両方式のレンダリング時間比較を示す．また，図 5．2（b）に実験条件（2）における両方式のレンダリング時間比較を示す．図から分かる ように，本提案法はRay㈱s七ing法に比較してレンダリング速度が速いとの実験：結果 が得られた． 図5．3（a）に実験条件（1）における両方式の部分映像重畳処理に要した時間の比較 を示す．また，図5．3（b）に実験条件（2）における両方式の同様な比較を示す．いずれ の場合もノード数を2，4，8，16と変化させて重畳時間を測定した。 5．2．実験の考察 42 表52：Multiple−Sheared法による人体頭部のレンダリング時間計測 表示ピクセル数 ノード数 2562 5122 鶉 臨 鶴 鳳 2ユ36 ◎．0206 2，265 0．0204 0．0335 1ユ72 0．0327 1ユ77 0．0329 0．0470 0，691 0．0468 0，657 0．0461 0．0588 0，421 0．0596 0，419 0．0593 ⑳ 窺 2 7682 2，136 0．0206 4 L170 8 0，679 16 0，416 恐はレンダリング時間賜は重畳時間（秒） 表5．3：Mul七iple−Sheared法によるニューロンのレンダリング時間計測 表示ピクセル数 ノード数 5122 7682 2562 2 鶉 臨 21．12 0213 恐 臨 鶏 ％ 21．67 0，213 21．07 0，213 4 10．61 0，317 10．85 0，316 10．84 0，317 8 5．38 0，418 5．39 0，414 5．50 0，416 16 2．79 0，518 2．85 0，518 2．84 0，517 鶉はレンダリング時間臨は重畳時間（秒） 5。2 実験の考察 5．2．1 並列度と処理性能の線形性 ボリュームの一辺のサイズをyとしたとき，レンダリングに要する計算量のオーダ は0（y3）である．いっぽうRaycasti丑g法はスクリーン上の画素からレイを出すため スクリーンサイズをP・Pピクセルとしたとき計算量のオーダは0（P3）1である．この ため，シアーワープ法の処理時間はボリュームデータのサイズにより，Raycasむing法 はスクリーンサイズによる。この傾向は測定結果，図5．2に現れている．もともとオ リジナルのボリュームデータが持つ分解能以上の分解能は表現できないのであるが， シアーワープ法は必要以上の分解能の映像発生を自然に抑えているといえる．並列化 の効果に関しては，図5．4（a），5．4（b）に示すように計測した範囲の並列度（16ノード まで）では，いずれも線形性を有している、本提案法ではサブボリューム分割を均等 におこなうので，計算ノード数を瑞としたとき，単純に対象サブボリュームサイズ が瑳となり，測定の範囲では処理の線形性を持つと予想される・ エ奥行き方向のサンプリング間隔をyと考えれば0（P2y）と考えられるが，議論を明確にするため 0（P3）とした． 43 5．2。実験の考察 表5．4：Raycasもing法による人体頭部のレンダリング時間計測 表示ピクセル数 ノード数 2562 5122 7682 2 6．28 0．0315 26．01 0，129 恐 臨 55．49 0288 4 327 0．0485 13．28 0，197 29ユ1 0，442 8 1．95 0．0611 7．92 0，246 16．98 0，553 16 0．97 0．0789 3．91 0，318 8．36 0，707 勾 塩 鱗 臨 鶉はレンダリング時間監は重畳時間（秒） 表5．5：Raycas七ing法によるニューロンのレンダリング時間計測 表示ピクセル数 ノード数 2562 5122 7682 鶉 ％ 鶏 窺 33．40 0，151 73．35 0，341 0．0541 16．95 0，216 36．35 0，484 0，278 20．14 0，622 0，337 10．63 0，759 鶉 窺 2 8．55 0．0370 4 4．31 8 2．40 0．0691 9．47 16 1．26 0．0840 4．90 鶉はレンダリング時間賑は重畳時間（秒） 5．2．2 ソフトウエアによる重畳時間と並列度 ビデオレートでの映像発生が全てソフトウエアで可能か否かを知るため，重畳時間 と並列度の関係を検討する． 部分映像の重畳時間に関しては図5．3に示すように計 算ノードの増加に伴ない増加している．これは次のように解釈できる．重畳処理を， 混合計算式（3．3）の実行時間塩（2枚のサブボリュームイメージを重畳する時間）と 他ノードへの転送時間男（1枚のサブボリュームイメージを転送する時間）に分ける とすれば，重畳に要する全時間丁は，重畳および通信の回数凡を用いた次式になる． T ＝＝ ！V≧（望賑十7吃） （5。1） 係数N。は重畳の並列度を鱗としたとき重畳および通信回数の下限であり， 〈墾＝罵》（2−1十2｝2十。．。十2｝Zo92 Np）＝罵，一1 である． 転送時間処はデータの転送時間乃と転送セットアップ時間偽。オ（転送時間以外の 時間）に分解されるので，上の式は 7＝A㌃（臨十鶉。重十％r （5．2） 44 52．実験の考察 これを瑞ノード数で並列処理するとすれば，監，鴎は並列化できるので， T一（〈レ1）（讐墜＋牲・の （5．3） 瑞を大きくとれば， 丁磐 臨十7諺r十ハらT。。重 （5．4） となり単一処理よりも並列処理の方が処理時間は増加する． ノード数2および16の 重畳時間計測データを用いれば，77。。舌が求まり，7翫蟹3㎜5程度となる． 5．2．3 ビデオレートでの映像発生 レンダリング処理を高速に行うためには，並列度を増やす必要があるが，前節の議 論から重畳処理のオーバヘッドはノード数を瑞としたとき3（錦一1）msと増加する。 ビデオレートの処理（30フレーム／秒）を想定すれば，1＞レ瓢12でオーバヘッド時 間が33msを越える．しかし，図5．2（b）によれば，本提案法のレンダリング時間は約 5秒程度であり，さらなる並列数の増加が必要である． 提案する処理方法の性能が高並列時にどのようになるかを実験で確かめることは 困難である、従って，ニューロンデータを用いて画素数7682を表示するとの条件下 で，提案法のレンダリング時間丁3およびRaycasting法による時間娠を，式（5．5） を用いて予測した． 乃 ＝ 0（τ／3）／ノ鷲）十〇。0031＞レ （5，5） 娠 ＝ 0（1）3）／1＞1）十〇・003凡 0（y3）および0（P3）に関して実測時間（表5．3および表5．5）を使用した． 性能予測を図5．5に示す． 図で示すように，並列度が低い範囲では，処理時間は 0（y3）／！％または，0（P3）／！％で削減し，並列度が高い範囲では，直線31％に漸近し ている． 図で示した331nsのラインがビデオレートでの表示に必要な性能であるが， ノード数40ないし200から並列化による性能向上は見られない． これは，並列度 が高くなるに従い，メッセージパッシング（MPI）での通信時問のオーバヘッドが無 視できなくなるからである。 この予想図からも分かるように，PCクラスタを用いたソフトウエアのみの実装で はビデオレートでの映像発生はできない． このため，ビデオレートでの映像表示の 場合はレンダリング部ノードプロセッサによる並列化の他に重畳を行う専用ハードウ エアが必要である． 45 5．2．実験の考察 （a）ニューロン （b）人体頭部（8サブボリューム分割 による並列処理を示す） （c）人体頭部（2サブボリューム分割に （d）人体頭部 よる並列処理を示す） 図5．1：評価に用いたボリュームデータの表示映像 5．2．実験の考察 46 80 60 、 Volume data size：壌28x128x120 Volume data size：386x258x197 、、 70＼ ＿50 ・ （ 、 ち 禽＼ 甚6・＼R・y・a・童購th・d l：：、＼際1物識一pll：＼＿曲、紅潮 12。＼、’＼＿ i麗li13・＼＼響 1 囑一 に ＼一鞭．lize：5蓬2x5鷹2＼一一一一 鉱20’・5興、、＼一一一一鴨 10 Sαee轟si・e・256・256鱒學隔脅騎麟一…一・．．．．．． 壌0 6，256 ．翰纈暫噸鰯”顧・・・・・…．．．．．齢 ・24 8 16 ・24 8 』壌6 The自umber d processing n◎des， The nu蒲ber◎f processlng自odes、 （a）頭部データを用いた処理時間比較 （b）ニューロンデータを用いた処理時間比較 図5．2：本提案法およびRaycasting法の並列度による処理時間比較 0．8 0．8 V。1、m， d、t、、i、e、128、窪28、120 Vdume data size：386x258x壌9ア，！一・！ α7 ！〆 ＿o．7 ．．〆！／ 1：1／繍∴〆 @｛：：：穿輝／；躍1 ◎2 4 8 総 ◎2 4 8 鷹6 The number o董 processiR9自odes． Tぬe nu飢ber◎f processing aodes． （a）頭部データを用いた重畳時間比較 （b）ニューロンデータを用いた重畳時間の比較 図5．3：本提案法とRaycas七ing法の並列度による重畳時間比較 5．2。実験の考察 47 8 ‘ 〆 ！ Volume size：128x128x120 ／ ！ Voぬ瀟e size： 386x258x19ア 7 Screen size：768x768 ／’ Screen size：768x768 ， ’ ・卿． ldeal ／ 瀦茜が ！’！ 曽鵬髄 ldeal ノ ’ O篇05﹂ΩコわΦΦαの o⋮董α召ΦΦαの 1 6 ←M・ltipl・・h・a・ ／ ノ 5 牽…OR・ycasti・g／ ．・／ ノ ’ ！ ， ！ ’ ノ ノ 4 ／ ，” ノノ’ −G」一 M田tiple sねear ，’ …←… Raycastiag ・ ， ！！ 3 ／ ！！ ／， 祓 4ρ’ 2 ，ノ 1 灌2 4 16 8 2 Nu類ber of processi自9獅odes 4 16 8 麗u蒲berof pr◎cessing nodes （＆）頭部データ （b）ニューロンデータ 図5．4： 並列度による高速化率の変化 100 、＼ Ra a＄しing Neuro嶽 、 ＼ 、 、 へ 、、＼＼ Rayca＄し烹漁9 C㌘一Head 、 ＼ 、 、 ＼ ㌔ 、 ＼ ら 、 、 ね 、 、 、＼、 燦0 、 、 、 、 、 ＼ 、 、 、 、 、 ＼ 、 、 ＼ 、 、 、 、 、 ＼ 、 、 、 飾 、 、 、 、 、 、 、〆 、 、 ＼ 、 、 ＼ 馬 、 ＼ 、 、 、 壌 Wの︶Φ琵9ωのΦ§α℃Φ︸§￡ （． ／ 瓢uよtip■e一＄heaτed cτ一］｝｛ead 選登二Ltip：Le一＄heared Ne1議τon 0．1 V烹d愈。 Rate 33π｝＄ 0．01 10 壌00 Number of nodes 図5．5：並列度による処理時間の予測 4000 48 第6章 試作ハードウエア 6．1 構成 前節の理由から，並列度を増加してもビデオレートでの映像発生は不可能である． 重畳処理を行う専用ハードウエアが必要である． ビデオレートでの映像発生を可 能とするレンダリングシステムの構成を図6．1，試作中の重畳装置のブロック図を図 6．2に示す． 図6．1に従ってデータの流れを説明する，各ノードPCでレンダリング された部分映像がPCIバス上のインタフェースボード（IFB）を経由して，重畳ハー ドウエアに送られ，隠顕関係を考慮した合成画像が出力される．この画像は，サーバ PCのPCIインタフェースボードを経由してグラフィックスボードのフレームメモリ に書き込みが行われ，1画面の映像が表示される． 部分映像の発生は，高速エンジ ン（VGB）あるいはソフトウエアによるレンダリングの何れでも発生可能であるが， ソフトウエア処理（例えば提案のMulti−shered法）を用いる場合は，ビデオレートに よる映像発生においては，高い並列度が必要である． Server PC IB：Inteface board CRτ CP M￡ σ歳 uGB：VG board @ VolumePro500 O GB＜一圃 fB：Graphics boafd ；i・iiL・cal Imagesl；iiiComposite Node PC 鯉撫 Node PC 聾夏幡 Node PC 嬰夏幡 N◎de PC 聾臣幡 Node PC 三等幡 輿臣驕 Node PC 勲臣幡 鯉輪 Node PC Node PC 図6．1：H／W重畳装置を持つ並列ボリュームレンダリングシステムの構成 49 6．2．試作ハードウェア 図6．2に重畳装置の処理ブロックを示す． この構成は，図3．1および3．2に示した サブボリューム分割とその2次元映像の優i先度を用いた合成法をパイプライン化した 処理で実現したものである． 入力は8チャンネルあり，この入力を通して，Priority，色情報（R，G，B，A）が送ら れる．Priori七yはフレームに固定であるので，フレームの開始に一度送られ，セレク タの制御に用いられる． これにより，A側およびB側のどちらが視点側かが決定さ れる．図中のBLENDERでは色混合が行われ，この計算は，各R，G，B毎に式（3．3） を用いて行われる。 重畳装置はバンド幅36（R，G，B，A各8ビット＋制御ビット） ビット，21段のパイプラインで構i成されており，動作周波数はPCI32との兼ね合い により33MHzである． 8以上の並列度に対応するには重畳装置を多段にすることに よる．仕様上は512並列まで構成が可能である． Local lmage COmposite A＞B 、 l一ゆ 診B CH．3−i CH．4一一レ； 聾 B田NDER CB＞く BLEM）駐R CBX P BLEND￡R → P A＞B PB 畢 P A＞B BLEND￡R CB× ﹀く CH．6一一→l 8L￡NDER → PA A＞B P8 C i導 PA CH．5＿i 蹴→ ↓ c田一一i CR，2＿i 里X↓ → 坤↓ P P l l A＞B A＞B P C i PA P 興 BL猛製DER 1ま調→ → P二Prioriεy CR，7＿； C嫉，8一一→i C：Co】or（r，9，b，a） CB峯 図6．2：重畳部の構成 6．2 試作ハードウエア 図6．3，6．4および6．5に試作した重畳装置の概観を示す．図63は各パーソナルコ ンピュータのPCIバスに挿入されるインタフェース部，図6．4は重畳部，図6．5は重 畳装置（1チャンネルの接続）をそれぞれ示す．インターフェースボードと重畳回路 のデータ受け渡しは，高速転送に伴なうフロックスキューを防ぐためにパラレルデー タをシリアルデータに変換しLDVS（Low Voltage Diffeτential Signaling）を用いて 転送する。 CMOS／TTLデータからLDVSデータへの変換はNatioRal Semiconductor社製VLSI チップDS90CR483／484を用いておこなっている．インターフェースボードと重畳装 50 6．2．試作ハードウエア 』轟＿畑鋤論三三訟野田… 図6．3：試作重畳装置インターフェースボード部 図6．4：試作重畳装置の重畳部 置間の接続ケーブルは，DS90CR483／484を用いることにより，最大48ビットのデー タを取り扱い可能であり，本試作では1配線に6ビットを割り当て8配線と，クロッ ク1配線の計9配線でケーブルを構成している。 このシリアル転送を行うには，PCIバス（PCI32）の基本クロック周数33MHzを PLL（Phase：Lock LooP）を用いて33MHz×6に逓倍し，この逓倍した周波数でシリア ル化したデータを送信している．受信側である重畳装置では，同様に33MHz×6のサ ンプリング周期でシリアルデータを取り込み，V丑SIチップDS90CR484を用いてシリ アルデータをパラレルデータに変換する．転送速度は，1配線当たり33x6Mビット／ 秒，8配線による実効速度は1．58Gビット／秒である． これは， PCIバス（PCI32） の転送速度1．064Gビット／秒より高速であり，システム的に十分置速度マージンを 持つ． インタフェースボードおよび重畳装置における論理回路の多くはアルテラ社製FPGA を用い，論理はVHDL言語で記述している． 6．3．性能評価 51 図6．5：試作重畳装置の構成 6．3 性能評価 ハードウエアで重畳装置を構成する場合は，入力端子を並列度数分構成可能であ るので，ソフトウエア重畳を行うときの予測式（5．5）と異なり，重畳時間は並列度 賜の関数ではない． 処理時間の予測を式（6．1）に示す．式中乃はシアー法を用 いたレンダリング時間，跣はRaycas七ing法によるレンダリング時間である．また， ろ。ゴ（P2）は，インターフェースボードから重畳装置への2次元部分映像の転送速度で あり，データ量P2に比例する． 鞠＝o（γ3）／瑞＋ろ。・（P2） （6．1） 塩＝o（P3）馬＋7』。‘（P2） ろ。ゴ（P2）をPCI32のの規格から推定すると以下の式となる． 勿』c‘（P2） ＝ 」配pc‘ ・」配e」F∫ecオ ・」P 2 瑞。ゴはPCI32の規格から33量10、秒であり，R。〃飢はPCI32を制御するマザーボード 上のチップセットによるDMA転送時の効率低下を表す係数である．この係数は，稼 動プログラムおよびチップセットの種類により異なるが0．8と想定している．以上の 数値を用いて計算するとR卿・R。〃εc亡は2，4×10−8となる． これを式（6．1）に代入 すれば，評価式（6．2）となる． 鞠 ＝ 0（y「3）／二十2r4×10−8・P2 （6。2） 図6．6に，重畳処理をハードウエアおよびソフトウエアで行った場合の評価式 （6．2）および（5．5）による処理性能予測を示す． このとき画素数は1M画素とした． ソフトウエアでのレンダリングは図5．5に示す4種の曲線中，Multiple Sheared法の みを選択して示している．図で示すように，並列度による処理の飽和はビデオレート 以下に押さえられる． 52 6．3．性能評価 100 謬 、 A／ ，〆 ．！ ＼ 、 ＼ 10 ／／ ／ ，ノβ ／ ^ p①QQ︶Φ惹蕊滋・。・。80嵐℃の︸・。8￡ （． ＼ 1 A ，4グ＼・＼．＿．ノー多穿’ @ ノ’ 、＼ @ ノ’ A＼ 、 ＼ @ ，／ 、、＿＿＿〃・rン @ ノ @ ノ @ ’ ノ @ ノ 0．1 ’ @ ノ @ ’ @’ ノ f 鎖階 f Video Rate s @ 、 ’ 鞠 一 0．0裏 SハV Compsite w冠h SハV Renderlng 一勝一冊一 SハV Comps魏e wi繕H〈V Renderlng 鳳 繍 扁 鷹 顯 繍 0．00蒙 0．0001 g／W bompsite wlth SハV Re職deri織g H／W Compsite wi山H／W Rendering 10 100 1000 Number of nodes 図6．6：試作ハードウエアの並列度による処理時間予測 10000 53 第7章 まとめ 大規模な科学技術計算の高速可視化では，大容量のボリュームデータ（10243以上）を 取り扱う必要があり単一のレンダリングエンジンでは処理性能が十分でない．大規 模データの実時間表示，15フレーム／秒程度，に対応する並列ボリュームレンダリン グシステムを提案した．提案法は対象ボリュームを部分空間であるサブボリュームに 分け，サブボリューム単位に並列してレンダリングをおこなうことにより高速化を達 成する．本提案法に基ずくプロトタイプシステムを用いた機能・性能評価によれば， 提案法は並列度に応じた処理のスケーラビリティを持つ．Raycas七ing法を用いた同 等のシステムとの性能比較では約4倍の高速化を達成した． いっぽう，レンダリング処理を高速で行うためにはノード数を増やす必要があるが， 重畳処理のオーバヘッドは並列度を脇とすれば3（1％一1）msと増加する．ビデオレー トの処理（30フレーム／秒）を想定すれば，1協＝12でオーバヘッド時間が33msを 越える．従って，PCクラスタを用いたソフトウエアのみの実装ではビデオレートで の映像発生はできない．ビデオレートでの映像表示の場合はレンダリング部ノードプ ロセッサによる並列化の他に重畳を行う専用ハードウエアが必要となる．この8入力 1出力を同時行う重畳ハードウエアの試作を実施した．提案システムは，高速エンジ ンおよび重畳ハードウエアを用いることにより，10243ボクセルサイズのボリューム データを約15翫で表示可能である． また，提案法は並列度に応じて各ノードに割り当てるサブボリューム容量が小さく なるため，全体として大規模なボリュームデータの可視化が可能である． シミュレーション対象を部分空間に分割し，各部分空間に計算能力の高いPCを割 り当てるPCクラスタによるボリュームレンダリングシステムの実現は，計算と映像 発生を密に融合するものであり，大規模科学技術計算の可視化あるいは，医療分野で の3次元可視化に寄与するものである．特に，人間の操作により対象物が変形するな どの計算過程を表示可能であるので，実用的な手術シュミュレータの実現に応用が期 待される． 54 x2 gr wt [1] S. Muraki, K. Shimokawa, M. Ogata, K. Kajihara, K. Ma and Y. Ishikawa: "VG CIuster: Large Scale Visual Computing System for Vblumetric Simulations, SC2000 Research Gems(Poster), Nevember 2000 [2] A. S. Glassner: "Principles of Digital Image Synthesis", Morgan& Kauiman (1995) [3] T. Gimther, C. Poliwoda, C. Reinhart, J. Hesser, R. Manner, H.-P. Meinzer, akd H.-J. Barir: "Virirn: A massively parallel processor fbr real-time volume visualization in medicine", Computers & Graphics, Vel.19, No.5, pp.705-710 (1995) [4] A. Kauiman and R. Bakalash: "Memery and processing architecture fbr 3d voxel-based imagery", IEEE Cemputer Graphics & Applications, Vel.8, No.6, pp. 10-23 (Nov. 1988) [5] G. Knittel aRd W. Strasser: "A compact voiume rendering accelerator", In Proceedings of the IEEE Symposium on Volume Visualization, pp. 67--74 (Oct. 1994) [6] P. G. Lacroute and M. Levoy: "Fast volume reRdering RsiRg a shear-warp factor-- ization ofthe viewing transformatiok", In Proceedings ofthe ACM SIGGRAPH '94 Conference, pp. 451-457 (July 1994) [7] M. Levoy: "EfficieRt ray tracikg of volume data", ACM Transactions oit Graphics, Vbl.9, No.3, pp. 245-261 (July 1990) l8] M. Ogata, H. Ohkami, H.C. Lauer and H. Pfister: "A Real-Time Volume ReRdering Architecture with Resampling Scheme fbr Parallel and Perspective Prejections", Proceedings ofthe ACM/IEEE Symposium on Velume VisualizatioR, pp. 20--29 (Oct. 1998) [9] M. Ogata,H. Pfister, H.C. Lauer, Y.Dohi: `A Parallel Pipeline Convolution for Perspective ProjectioR iR Real-Time Velume Rendering", The Jor!mal of the IRstitute of Image Infbrmatioll aRd TelevisioR Engineers, Vol.54, No.9, pp･ l339--1348 (Sept. 2000) 55 [10] R. Osbome, H, Pfister, H. Lauer, N. McKenzie, S. Gibson, W. Hiatt and T. Ohkami: "Em-cube: An architecture for low-cost real-time volume render- ikg", IR Proceedings of the 1997 SIGGRAPH/EUROGRAPHICS Workshep on Graphics Hardware, pp. 131-138 (Aug. 1997) [11] H. Pfister and A. Kauiman: "Cube-4: A scalable architecture fbr real-time volume rendering", In ProceediRgs efthe ACM/IEEE Symposium on Velume Visualization , pp. 47--54, San Fransisco, CA (Oct. 1996) [12] H. Pfister, J. H. Hardenburg, H. Lauer and S. Sailor: "The VolumePro Real-Time Ray-Casting SystenL", In Proceedings ofthe ACM SIGGRAPH '99 Conference, pp. 131-l38 (Aug. 1999) [13] L. Westever: "Footprint evaluation fbr volume rendering", Ill ProceediRgs of the ACM SIGGRAPH '94, pp. 144-153 (Oct. 1994) [14] L. Williams: "Pyramidal parametrics", In Proceedings ofthe ACM SIGGRAPH '83 CoRfereRce, pp. 1-11 (July 1983) [15] Kwan-Liu Ma: "Parallel Volume Rendering UsiRg Binary-Swap Compositing", In IEEE Computer Graphics and Applications,pp. 59-68 (July 1994) [16] G. Knittel: "The UltraVis System", In Hewlett-Packard Laberatories, Usual Computing Department, [email protected] [17] S. Molnar, D. Ellswoorth and H. Fuchs: "A Sorting Classification of Parallel Rendering", IEEE CG&A, vol.14, no.4, pp.23-32, July 1994 [18] Greg Humphreys, Ian Buck, Matthew Eldridge and Pat HaRrahan: "Distributed Rendering fbr Scalable Display", Proc. SC2000, November 2000 56 光線分割の原理 スクリーン上の該当位置（∫），9）での輝度ちgは，式（A．1）により求まる． ちげ傭五（・）・瀞（オ）d診d・ （A・1） ここに，μ（のは光線上の位置重における減衰率，双3）は同様に位置5における発光 を示す．また，30は光線の開始位置（パラメータ形式），51は終了位置をそれぞれ 示す． 式（A。1）を離散化すると式（A．2）となる． ち，瓢 Σ1：計1（ち△3¶舞『e間△3△8） 一Σ齢1（α・H欝1αゴ） （A．2） ここで，△5瓢ムォとした．また，α茗は透過率を示す． 式（A．2）を展開すれば式（A．3）となる． ち，＝0・＋01α・＋02α・α・＋03α・α・α2＋ （A．3） …＋0飴1αoα1…αN−2 上式を，図3。3に示すように2分具したとすれば式（A．4）となる． ち，＝Oo＋0エαo＋02αoα1＋03αoα1α2＋ …＋0た一1αoα1…α械 十 （A．4） α◎α1…αた一10た＋α0α1…α鳶．、0ん＋、αん＋ …＋α0α1…αレ10鮎1α鳶…αN−2 まとめれば， ち9驚残＋堵グ・41 （A．5） ．4 ＝ 、41・．42 P9 ただし，ガ＝α◎偽…α臥1，、42＝α海αた＋1…α酷1である． 従って，別々に対称な計算を行ないそれぞれの最終結果弓，およびぢ，を上式で重 畳すれば良い． 57 謝辞 本研究は，著者が1998年から2001年にかけて博：士課程学生として3年間在席した横 浜国立大学大学院工学研究科土肥研究室におけるコンピュータグラフィックス・アー キテクチャの研究および1997年から会社業務として行なったボリュームグラフィック スの研究成果をまとめたものであります． 1993年より著者を社会人学生として受け入れて頂き，長い間ご指導頂いた横浜国 立大学土肥康孝教授には，本論文をまとめる機会を頂き衷心より深謝いたしており ます．ご指導頂いた三章石井六哉教授にも感謝いたします．先生は信号理論がご専門 でありこの方面でのご指導は大変有意義でした． また，本論文をまとゆるにあたり 論文の質を落とさないようご指導いただいた同科有澤博教授，同河野隆二教授，同 長尾智晴助教授にも感謝いたします． また，著者が社会人学生として入学するにあたり許可を頂きました所属上長である 三菱プレシジョン（株）（現、常務取締役開発本部長）久良知國雄氏には，このような ご配慮を頂き感謝しています。さらに，著者がこのような方向に向かう多大な精神的 影響を受けた，三谷尚正氏（元，三菱プレシジョン，常務取締役），梶原景範氏（元、 ビジュアル技術担当部長），藤野勝氏に感謝します．今回，お名前は挙げませんでし たが，著者がお世話になった多くの先生および会社の方々に感謝します． 最後に，会社員と学生の二足の草鮭を履き，この6年間，家庭を顧みる暇がなく， 迷惑をかけた妻敬子，長女智子、次女満美子に深謝します． 58 公表論文リスト 1査読フルペーパ ［1］Oga七a，Pfister，：Lauer，Dohi：，，A Parallel Pipeline Convobもon fbr Perspective Projec七ion in Rea1−Time Volume Rendering”，映像情報メディア学会論文誌 VoL54 No．9ラppユ339−1348， Nov．2000 図緒方，梶原，村木，下川，Ma，土肥：「空間および光線分割による並列ボ リュームレンダリング・システム」，映像情報メディア学会論文誌，平成12 年12月14EI投稿 II査読研究速報 国中井，村木，加藤，杉尾，松尾，上田，緒方，劉，小西，富樫：「高分解能 三次元画像の立体可視化システムの開発」，日本医学放射線学会誌，VbL 61 No．3， PP39−41，2001年！月 III査読国際会議論文 ［1】：Fuji漁。 an．d Ogaもa：“Dy丑amic Tex七ure in Visual Sys七emララうProceedillgs of AIAA：Flight Simulaもion Technologies Confもrenceラ88ラAmerican Insもi加te of Aeで（）aauもics and Asrona鷺tics，88−4578−CP， Atlan七a， Geofgia， Aug。1988． ［2］Ogaもa a捻d Dohi：‘‘A Shadow Genera七ion in Rea1−Time Co：mpu七er Gτaph− ics∵ラPfoc￠edi難gs◎f IEEE ICONラ96ラPP。440−446ラ1996。 ［3］Ogaもa，Oh：kam・i・Phisも鱗Lauer：“A Rea1−Time Volume RenUering Architec一 綴￡ewi七h Resa皿Pli難g Schem，e for Parallel a：nd Perspec七ive Projec七io：ns，ヲ， Pf◎ceedi鍛gs ofもh￠ACM／IEEE Sy即osium o難Vohme VisulaizaもionラPP．20− 29ラ（）Ct．ラ1998・ 59 ［4］Muraki，Shimokawa，Oga七a，：KajiharaラMaラlshikawa：”VG Cluset：Large Scale Visual Computing Sys七em薮）r Volumetric Sim嚢1aもionsラララResearch Gems（Poster） of IEEE Super Compu七α2000。 Iv解説論文および雑誌記事 ［1］緒方，梶原，藤野：「実時間CG技術の現状」，電子情報通信学会誌 Vb1． 84No．3， pp．167−171，2001年3月 ［2］村木，下川，緒方，梶原，Ma：「神経システムのシミュレーションを目指 してし共立出版，Bi七誌 vb1．33 No．3， pp。58−65，2001年2月 v学術研究会 国緒方，梶原，藤野：“フライトシミュレータ用高性能ビジュアルシステムの畠 試作”，電子情報通信学会技術報告CPSY Vo1．93 No。436， pp．945，1994年 1月 ［2］緒方，土肥：ζ‘実時間コンピュータグラフィックスにおける影映像の実現法”， 電子情報通信学会技術報告CPSY Vol．94 No．481， pp。33−40，1995年2月 ［3］中井，村木，喜田，富樫，劉，緒方：”3D Rea1−Time Vohme Viewerの開 発“，第59回日本医学放射線学会誌会サイバーラド06，1999年4月