修士学位論文
題目 「部分更新光線追跡法による
動画生成に関する研究」
情報工学専攻
木村研究室 片平 昌幸
目次
第１章 緒論
§１．１ 本論文の背景及び目的
§１．２ 本論文の内容
第２章 光線追跡法による画像生成
§２．１ 緒言
§２．２ 光線追跡法による画像生成
§２．３ 光線追跡法の高速化
２．３．１ オブジェクト空間分割による高速化
２．３．２ 並列処理による高速化
§２．４ 結言
第３章 部分更新光線追跡法による動画生成
§３．１ 緒言
§３．２ 部分更新光線追跡法
３．２．１ 部分更新のアルゴリズム
３．２．２ 光線追跡木のデータ構造
§３．３ 部分更新光線追跡法の性能評価
３．３．１ 従来の手法との比較
３．３．２ 空間分割数とメモリ使用量の関係
３．３．３ 空間分割数と処理時間の関係
３．３．４ 画素分割型並列処理システムによる性能評価
§３．４ 改良型部分更新光線追跡法
§３．５ 結言
第４章 共有メモリ型並列計算機による部分更新光線追跡法の性能評価
§４．１ 緒言
§４．２ 共有メモリ型並列計算機
４．２．１ ハードウェア
４．２．２ ソフトウェア
§４．３ 並列部分更新光線追跡法
§４．４ 並列部分更新光線追跡法の性能評価
４．４．１ プロセス数と処理時間との関係
４．４．２ プロセス数とメモリ使用量の関係
４．４．３ アルゴリズム改良の効果
４．４．４ オブジェクトの配置位置と処理時間の関係
§４．５ 結言
第５章 結論
謝辞
参考文献
発表論文リスト
第１章 緒論
§１．１ 本論文の背景及び目的
１９５０年代の後半から１９６０年代の初めにかけて、ランダムスキャン形ディスプレイを用いたワイヤフレームモデルによるフライト・シミュレーションやＣＡＤ／ＣＡＭシステムがはじめて実用化されて以来、コンピュータ・グラフィックス（ＣＧ）はコンピュータ技術及びディスプレイ技術の急速な進歩とともに飛躍的な発展を遂げ、今日では各種のデータの視覚化をはじめとして、設計・製造のためのＣＡＤ／ＣＡＭシステム、フライトシュミレータなど各種のＣＧによるシミュレーション、各種のデザイン分野への応用などといった実用的な分野ばかりでなく、コマーシャルフィルムやアニメーション映画に至るまで幅広く用いられるようになってきている。特に、近年のコンピュータの性能の向上と各種の新しい画像生成アルゴリズムの開発によって、以前よりもはるかにリアリティに富んだＣＧ画像を生成することが可能となった。
現在、最も高品質な画像を生成できるアルゴリズムとして光線追跡法（ Ray Tracing）がある[1]。これは光源から発した光線が物体によって反射・屈折されて視点に届くまでの過程をシュミレーションすることによってスクリーン上の各画素の輝度を計算して画像を得る方法である。通常、光学現象はスネルの法則、フレネルの反射法則などを考慮にいれた簡単なモデルで近似される。光線追跡法は比較的単純なアルゴリズムにもかかわらず光の反射、屈折などを統一的に扱えるため非常にリアルな画像を生成できる反面、処理速度が非常に遅いという欠点を持つ。このため、現在この処理速度を改善しようという研究が盛んに行われている。１つはアルゴリズムの改良によるものであり、また並列処理を用いて高速化しようとする試みもある。
一方、近年のＶＬＳＩ技術の進歩にともない、マイクロプロセッサの処理性能はかなりの勢いで向上している。しかし、高速なプロセッサをもちいてシステムを構築するためには高速なメモリや周辺回路が必要となり、その実装技術も高度なものが要求される。そのため、シングルプロセッサによるシステムの性能の向上にはこれから先困難が予想される。そこで、複数個のマイクロプロセッサを並列動作させることによって、高性能なシステムを構成することが考えられている。現在、キャッシュメモリを持った４から８台程度のプロセッサを高速バスで接続し、主記憶を共有するといった構成の密結合マルチプロセッサシステムがいくつか開発・試作されている。このようなシステムでは、既存のシステムとのソフトウェア互換性をとりやすく、またシステムを構成するのにほぼ確立された既存技術を使えコストを低く抑えることができるなどの利点がある。
本論文では、光線追跡法による動画生成の際の高速化手法である部分更新光線追跡法について述べる。またその手法に並列処理を適用した場合について、シミュレーションによって性能評価を行う。更に、実際に共有メモリ型密結合マルチプロセッサシステム上に並列化した部分更新光線追跡法をインプリメントして実験を行った結果について検討する。
§１．２ 本論文の内容
本論文の内容は以下の構成となっている。
第２章では、光線追跡法の基本概念及び特徴について述べ、その高速化へのアプローチとして空間分割法と並列処理について述べる。
第３章では、光線追跡法による動画生成の高速化を目的とする部分更新光線追跡法について、それを実現するための光線追跡木のデータ構造及び部分更新のアルゴリズムについて述べ、従来の手法と比較検討を行う。また、シミュレーションによって、画素分割型の並列処理システム上で部分更新光線追跡法を実行する場合の性能評価を行った結果についても述べる。
第４章では、第３章で述べた部分更新光線追跡法を実際に共有メモリ型の並列計算機上にインプリメントし実行させた実験結果について示し、検討する。
第５章は結論である。
第２章 光線追跡法による画像生成
§２．１ 緒言
本章では、高品質な３次元図形の動画像生成アルゴリズムとして本論文で検討していく部分更新光線追跡法の基本となる光線追跡法の基本概念と特徴について述べる。次に、光線追跡法の高速化手法として、空間分割法、並列処理について述べる。
§２．２ 光線追跡法による画像生成
３次元図形を陰影をつけて表示するためには、視点から不可視な面を除去して表示する必要がある。このような処理は隠面消去と呼ばれており、代表的な隠面消去アルゴリズムとして次の３つがある。
（１）スキャンライン法
全ての図形をスクリーン座標に変換し、それらをスクリーンの上下方向にソートする。次に視点とスキャンラインを含む平面上で最も視点に近い図形の色を求める。これをスキャンライン分だけ繰り返し画像を得る。
この手法はスキャンライン間の相関関係を利用できるため高速であるが、表示図形がポリゴンのみと限定される。また、全図形をソートするため図形の数に限界があるといった欠点を持ち、反射や屈折といった光学現象を表現できない。
（２）Ｚバッファ法
全画素について奥行きデータ用のメモリを用意する。次に各物体の存在範囲から奥行きデータを更新し、隠面消去を行う。
この手法は高速であり、図形の形状に制限がないといった利点があるが、膨大なメモリが必要であり、反射や屈折といった光学現象を表現できない。
（３）光線追跡法
視点から各画素を通る光線（実際に視点に入射する光線とは逆方向）を光学現象に従って追跡して、各画素の色を決定し画像を生成するものである。
この手法の最大の利点は光の反射、屈折、付影といった現象を統一的に扱うことができる点である。光線追跡法で得られる画像はスキャンライン法、Ｚバッファ法で得られる画像に比べきわめて高品質である。
次に、光線追跡法の基本処理について述べる。
まず、コンピュータ内部に図２．１のように仮想的な３次元空間を設定し、視点、スクリーン、３次元形状の物体を定義する。次に視点からスクリーン上の各画素を通る光線を考え、この光線と物体が交差するか判定する。もし、交差しなければ、何も見えないことになる。交差すれば、その交点が可視交点になるが、交点が複数存在する場合、視点に最も近い交点が可視交点になる。さらに、可視交点から反射方向、透過方向に光線を発生し、同様に処理を続ける。また、この点から光源方向に物体が存在するか判定することにより付影処理が行われる。図２．２左のようなモデルについて次々と可視交点を求めて行くと、図２．２右に示す光線追跡木(binary shade tree)が得られる。この光線追跡木にしたがってボトムアップに可視交点の輝度をシェーディングモデルに従い求めて画素の輝度を決定する。この計算を全画素について行うことにより画像が生成される。
次に代表的なシェーディングモデルの例を示す。これはT.Whittedによって提案された透明体についてのシェーディングモデル（図２．３）である。
ｎ
Ｉ ＝ Ｉｄ＋Ｋｄ�堯�Ｎ・Ｌｉ）＋ＫｓＳ＋ＫｔＴ
ｉ＝１
Ｉｄ ： 環境光の輝度
Ｋｄ ： 拡散反射係数
n ： 光源の個数
Ｎ ： 対象点での面の法線ベクトル
Ｌｉ ： 第ｉ番目の光源の方向ベクトル
Ｋｓ ： 鏡面反射係数
Ｓ ： 反射による入射光の輝度
Ｋｔ ： 透過係数
Ｔ ： 透過による入射光の輝度
上の式で、第１項は環境光成分、第２項は光源から直接入射してきた光による拡散反射成分、第３項は鏡面反射成分、第４項は透過光成分である。
光線追跡法は球、円柱といった２次曲面、平面などを扱え物体の形状に制限がなく、反射、屈折といった光学現象も扱え非常にリアルな画像を生成できる手法であるが、他の手法に比べ膨大な計算時間を必要とする。その原因として、以下のことが考えられる。
１）グローバルな照明モデルで輝度計算を行う。
グローバルな照明モデルでは、光学モデルに従って光線の反射や屈折をシミュレートするため、各画素に関与する光線は複数である。各画素に対して光線追跡木を作成し、この木をボトムアップ的にトラバースしながら輝度を計算しなければならない。
２）各画素の輝度は、補間処理を行わずに独立に計算される。
スキャンラインなどの方法では、画像や物体の一貫性(coherency)を利用し、画面の大部分の画素の輝度計算を増分計算によって行う。光線追跡法では、それらの一貫性を利用することが困難なため、各画素の輝度計算を独立に行わなければならない。
３）物体と光線の交点の算出
可視交点を検出するために、光線追跡木の各光線について全ての物体との交差判定を行う必要がある。交差判定のための計算は、浮動小数点による複雑な計算を必要とし実行に時間を要する。
T.Whittedによると[1]、この処理が全計算時間の７５％以上になり、複雑な画像においては９５％を占めるということである。
§２．３ 光線追跡法の高速化
光線追跡法によって生成された画像は非常に高品質にもかかわらず、処理時間が膨大であるために広く実用化されていない。さらに、光線追跡法による動画像生成を普及させるにはその高速化は最も重要な課題である。現在、この高速化の研究が様々な角度から行われている。以下に代表的な高速化手法である空間分割法と並列処理の導入について述べる。前者はアルゴリズムの改良といったソフトウェアからのアプローチであるのに対して、後者はハードウェアからのアプローチである。
２．３．１ オブジェクト空間分割による高速化
光線追跡法アルゴリズムの改良による高速化手法を大きく分けると、光線追跡を適用させる画素数を減少させる画素補間法と交差判定回数を減少させるプリミティブ存在領域法に分けられる。前者にはスキャンライン法やＺバッファ法との併用、光束追跡法[2]などがあり画素数の増大に伴う処理時間の増加を抑えることができるが、一般に画質の劣化や表示できる物体の形状が限定されるといった欠点がある。後者には外接体包含法、空間分割法[3][4]がある。外接体包含法は物体を比較的単純な形状を有する外接体（直方体、球など）で囲み、さらにこれを階層的に適用することによって、木構造の物体データを構成するものである。この手法では、交差判定は木のルートより始まり、交差の生じたものに対してのみ、その下のレベルを追跡してゆく。これにより、交差判定回数はかなり低減されるが、最適な外接体とその階層構造の選択は自動化が困難であり人手によって行われるため、多くの時間を費やすという欠点を持つ。
空間分割法も物体と光線との交差判定回数を低減化する手法である（図２．４）。オブジェクト空間は互いに隣接するいくつかの部分空間に分割され、光線追跡は光線の貫く部分空間を順次決定しながら各部分空間に含まれる物体と交差判定して行く。この場合、各部分空間は空間的にソーティングされているので、交点が見つかればそれ以降の部分空間についての交差判定は必要なくなる。具体的な例を図２．５に示す。空間分割法により交差判定回数を減少させることができることが分かる。本研究で採用したオブジェクト空間分割法は立方体で定義されるオブジェクト空間を均一な小立方体の部分空間（cell）に３次元等分割する方法である。この手法は、単純ながら前処理であるcellに含まれる物体を求める作業も高速にできる。また、次に交差判定を行う部分空間の決定も３ＤＤＤＡ(3 Dimensional Digital Differential Analyser)[4][5]によって高速に実行できるなど利点が多い。欠点としては図形情報の他に、各cellの中にどの物体が含まれているかを示す補助的なデータベースが必要になり、データ量が増加することである。
２．３．２ 並列処理による高速化
光線追跡法による画像生成は汎用計算機によっても実用的な処理速度を得ることはできない。近年、ＶＬＳＩ技術の進歩にともない高速で安価なマイクロプロセッサが登場し、これを用いた並列計算機が様々な応用分野に対して研究開発されている。
光線追跡法による画像生成ではスクリーン上の各画素は独立に計算可能であるため、並列処理に適している。そのため、光線追跡法による画像生成を目的とした疎結合マルチプロセッサ型の並列処理システムが盛んに研究開発されており、実際に稼働しているシステムとしては、大阪大学のＬＩＮＫＳ[6]、富士通研究所のＣＡＰ[7][8][9]などがある。また、ＮＴＴのＳＩＧＨＴ[10]では、光線追跡における３次元ベクトル演算についても並列処理を行っている。これらのシステムでは、画面の分割を行い、分割された各画素の処理をプロセッサに割り当てて並列実行させる方法をとっている。このようなシステムは画素分割型と呼ばれる。画素分割型の並列処理方式は、各プロセッサのローカルメモリにオブジェクト空間内の全オブジェクト情報を持つ必要がある。そのためにデータメモリ量がプロセッサ台数に比例して増加するという欠点がある[6]。 しかし、並列度が高くプロセッサ数を増すとそれに応じた処理能力の向上を期待することができる。
本論文で検討する部分更新光線追跡法では、光線追跡木を保存するために多量のメモリを必要とする。一般に並列計算機では、通常の計算機よりも多量のメモリを持っているため、このような処理を行わせるのに適しているといえる。
§２．４ 結言
本章では、３次元図形の画像生成アルゴリズムである光線追跡法の基本概念とその特徴について述べた。光線追跡法の最大の欠点はその膨大な処理時間である。この処理時間を短縮する手法として、空間分割法と並列処理の導入について述べた。
第３章 部分更新光線追跡法による
動画生成
§３．１ 緒言
本章では、３次元空間等分割法[4]を用いて部分更新光線追跡法を高速に行う方法について述べ、その性能について評価検討する。さらに本手法に画素分割型の並列処理システムの導入を提案し、シミュレーションにより処理速度やメモリ使用量などの性能評価を行った結果についても述べる。
§３．２ 部分更新光線追跡法
３．２．１ 部分更新のアルゴリズム
光線追跡法を用いて動画を生成する場合、各フレームごとにすべての画素を生成する方法では、前章で述べた各種の高速化手法を用いても膨大な時間を要する。そこで、村上等[11][12]は、各フレーム間のコヒーレンスを用いた部分更新光線追跡法を提案し、高速な動画生成ができることを報告している。これは、動画の連続するフレーム間では画像の変化量が少ないことに着目して前フレームから変化した部分のみを再計算する手法である。しかし、全ての画素の計算結果、すなわち光線追跡情報の保存のためには、膨大な量のメモリを必要とする。
そこで、光線追跡木を保存する画素は動画の１シーンの間の各フレームで変化することが予想されるもののみとし、実際に画像生成をする際には各フレーム間で変化する部分だけを保存した光線追跡木を元に再計算するという手法を提案する。この手法は、視点を固定して、物体だけがオブジェクト空間内を移動するような動画を生成する場合に有効である。
この手法では、ある画素の光線追跡木を保存すべきか否かを判定することが必要である。これは、移動するオブジェクトの軌跡から判定することができるが、この判定を高速に処理するために、光線追跡法の高速化手法の一つであるオブジェクト空間の三次元等分割法[4] を応用した。
物体の存在する空間は、前処理において多数の小空間（cell）に分割され、それぞれのcellが含む物体のリストが生成される。このとき、移動するオブジェクトの軌跡にあるcellを記録しておく。この、オブジェクトの移動軌跡を含んでいるcellのことを、locus cellと呼ぶことにする。
各画素の光線追跡木を保存するか否かの判定は、その画素から追跡した光線がlocus cellを通過しているかどうかを調べることにより行われる。図３．１に、locus cellと光線追跡木を保存する光線の判定の様子を示す。 光線が１本でも locus cellを通過していれば、その画素は移動物体の影響を受ける可能性があるので光線追跡木を保存する。もし追跡したどの光線もlocus cellを通過しなかった場合は、その画素は動画の１シーンの中で移動物体の影響を受けないので、光線追跡木は保存せず最初のフレームでの計算結果が用いられることになる。また、光線追跡木の各ノードにおいて下位レベルで再計算の必要性が無ければ、下位の全てのノードを光線追跡木から削除する。これらの方法により、メモリ使用量を全画素の全ての光線追跡木を保存する場合に比較して大きく減少させることができる。以上に述べた最初のフレームにおける光線追跡木保存のためのアルゴリズムを図３．２（ａ）（ｂ）に示す。
２フレーム目からの画像生成は、次のようにして行われる。まず、光線追跡木を保存した全ての画素についてそれぞれの光線追跡木をルートから順にたどり、各光線が移動物体の影響を受けているかどうかをチェックする。そのためのアルゴリズムを図３．３に示す。このとき、光線がlocus cellを通過している部分のみチェックする。もし、移動物体の影響を受けていることが判明した場合、光線追跡ノードの下位レベルのtreeは削除され、新たに光線追跡を行う。移動物体の影響を受けない場合は、以前のフレームの計算結果がそのまま用いられる。以上に述べた２フレーム目以降における再計算のためのアルゴリズムを図３．４（ａ）（ｂ）に示す。
従来の部分更新光線追跡法の場合は、全画素についての情報を保存するため、物体のどのような変化にも対応することが可能である。たとえば意匠設計ＣＡＤシステムにおいて、自由に物体を移動あるいは質感の変更等の操作をするというような応用ができる[11][12]。一方、本手法の場合、動画の１シーン中の移動物体の軌跡を用いて、そのシーンの間で変化することが予想される画素の情報のみを選択して保存する。そのため、空間分割処理を行う以前に計画した物体の移動等の変更にしか対応できない。しかし、例えば移動しない背景の中を少数の移動物体が移動するようなアニメーションの画像生成をするような場合には全画素を保存するよりもメモリ使用量を少なくすることが可能である。
３．２．２ 光線追跡木のデータ構造
図３．５に保存する光線追跡木のデータ構造を示す。各画素は、ＲＧＢ３原色の輝度とルートノードを指すポインタを持っている。ルートノードをさすポインタがnullの場合、その画素は１シーン中で変化しない、つまり再計算の必要性が無いことを示す。ルートノードは、視点から発した光線の通過したlocus cellのリスト(traverse list) を指すポインタ、光線に関する情報、次のノードを指すポインタなどを持つ。
視点から発した光線が物体と交差すると、新しいノードが生成される。それぞれのノードは、付影、反射、透過の各光線に関するデータを指すポインタ、及び各光線に共通なパラメータを持っている。各光線に関するデータの中には、traverse list を指すポインタ、各光線に固有なパラメータ、それぞれの光線についての次のノードを指すポインタなどが含まれている。各ノードにおいて、それぞれの光線のデータを指すポインタがnullの場合は、シェーディングの結果その光線の成分が存在しない、あるいはそれ以下のレベルにおいて移動する物体の影響を受ける可能性がないということを示している。
ルートノード、または各ノードの光線データにおいて、traverse list を指すポインタがnullの場合、その光線は移動する物体の影響を受ける可能性が無いということを表す。
§３．３ 部分更新光線追跡法の性能評価
提案したアルゴリズムの有効性を評価するために、計算時間、使用メモリ量などについて検討する。
性能評価に用いた動画のサンプル画像について、表３．１に示す。また、略図及び画面ハードコピーを図３．６(a)〜(m)に示す。いずれの画像も、移動物体として乱反射体の球７個からなる物体を使用している。
３．３．１ 従来の方法との比較
まず、計算時間について全ての画素を再計算する通常の方法と比較した結果を表３．２に示す。なお、いずれの画像も、cell分割数は１軸当り２４、画素数は１００×１００で計算した。計算時間は、ＦＡＣＯＭ Ｍ３６０のＵｎｉｘ（ＵＴＳ）上のＣ言語の clock関数を用いて計測したｃｐｕ時間である。
１枚目のフレームの場合、保存する光線追跡木の作成のために、通常の光線追跡法よりも１．３〜１．４倍の時間を要している。２枚目以降のフレームでは、画像によって大きく異なるが、全ての画素を再計算する場合に比較して１／５〜１／１３の時間で計算可能であるという結果が得られた。
次に要求メモリ量について検討する。サンプル画像の場合、最も少ない場合（ｏｒｂｉｔ）でも約３８６Ｋｂｙｔｅを要し、最大の場合（ｒａｓｅｎ）では約１．８Ｍｂｙｔｅにも達した。これは通常の光線追跡法と比較して１１〜２００倍のメモリを必要とすることになる。本手法は、光線追跡木を保存するために莫大な量のメモリを必要とすることが分かる。しかし、全画素の光線追跡木を保存する方法と比較するとおよそ五分の一程度に抑えられている。
３．３．２ 空間分割数とメモリ使用量の関係
オブジェクト空間を分割する際、より細かく分割すればするほど、真の移動物体の移動軌跡とlocus cellとが一致してくるために、より正確に移動物体の影響を受ける光線の判定をすることが可能になる。そのため、再計算の可能性のない光線追跡木を保存することが少なくなり、メモリの使用量を減少させることができる。しかし、分割数を増すことによって、光線の通過するlocus cellのリスト（traverse list ）を保存するためにより多くのメモリが必要になる。
オブジェクト空間の分割数と光線追跡木を保存した画素数の関係を図３．７に示す。いずれの画像も画素数は１００×１００で計算した。一般に分割数を増加させるにつれて保存画素数が減少しているが、ｒａｓｅｎの場合は余り減少しない。これは移動物体の軌跡が画面のかなりの部分を占めているためと考えられる。
次に、分割数と最大メモリ使用量の関係について調べた結果を図３．８〜図３．１０に示す。いずれの画像も画素数は１００×１００で計算を行い、ルートノード（root）、光線追跡木本体（shade tree）、物体定義データ（object data）、全体（total）のそれぞれについてメモリ使用量の最大値を示している。
ｏｒｂｉｔ３やｇｌａｓｓのような比較的単純な画像では、保存画素数の減少によりtraverse list のメモリ使用量の増加分が補われ、全体として分割数の増加と共にメモリ使用量が減少している。
ｍｖｔｓｔやｍｉｒｒｏｒのようなやや複雑化した画像では、保存画素数の減少によるメモリ要求量の減少分とtraverse list のメモリ使用量の増加分とがほぼつりあった状態となる。分割数１０以上では光線追跡木のメモリ使用量は一定になる。分割数が２４を越えると、物体定義データ（空間の各cellと物体との対応リストも含む）のメモリ使用量の増加により、全メモリ使用量は増える。
ｒａｓｅｎの場合には、分割数を増加しても保存画素数が減少せず、それによるメモリ使用量の減少がほとんど見られない。そのうえ、画像が複雑なため光線追跡木のメモリ使用量（traverse list のメモリ使用量を含んでいる）、物体定義データのメモリ使用量ともに、分割数を増すと増加する。従って、全体のメモリ使用量は、分割数にほぼ比例して増加する。
これらのことより、オブジェクト空間の分割数を増すことによって使用メモリ量を減少させる効果があるのは、分割数の増加によって保存画素数が非常に小さくなるような場合に限られる。分割数を増しても保存画素数が小さくならない場合には、光線追跡木内のtraverse listのメモリ使用量が増加するため、全メモリ使用量が増加してしまう。
３．３．３ 空間分割数と処理時間の関係
オブジェクト空間の分割数を大きくすると、次部分空間決定のためのオーバーヘッドが増加する。さらに、オブジェクト空間をcellに分割するための前処理時間も増加する。
各サンプル画像についてオブジェクト空間の１軸あたりの分割数と、前処理時間と画像生成時間および両者の合計時間の関係を図３．１１〜図３．１３に示す。前処理時間は、空間分割数の増加により増える。それに対して、画像生成時間は１軸当りの分割数が１０くらいまでは減少し、それ以上ではほぼ一定になる。これは、空間分割数をある程度以上増すと、交差判定回数があまり減少しないためである。
以上のことより、空間分割数は前処理時間、画像生成時間、使用メモリ量の３つをそれぞれ考慮にいれて決定する必要がある。本サンプル画像では１軸当り１６くらいが適当である。
３．３．４ 画素分割型並列処理システムによる性能評価
光線追跡法では、各画素の輝度をそれぞれ独立に計算できるため、並列処理を行うことにより画像生成の高速化を図ることが容易である。ここでは、画面の分割を行いそれぞれの分割した画素を各プロセッサに割り当てる画素分割型並列処理システムについてシミュレーションによる性能評価を行う。
§３．２で述べた部分更新光線追跡法に、画素分割型並列処理方式を導入する場合、各画素の光線追跡木のデータはそれぞれ独立であるためプロセッサ間で重複して持つ必要はない。そのため、プロセッサ数の増加によって光線追跡木の保存のための使用メモリ量が増加することはあまりない。現実には、各プロセッサ間で保存する画素数に片寄りが生じるために、全プロセッサのトータルメモリ使用量は単一プロセッサの場合よりも若干多くなる。
一般に、光線追跡木の保存のために必要なメモリ量はオブジェクト情報のためのメモリ使用量に較べて数十から数百倍に達する。したがって、数十台程度の疎結合マルチプロセッサシステムを考えると、オブジェクト情報と光線追跡木のためのトータルなメモリ使用量は、単一プロセッサと比較して数倍程度以内であると考えられる。これは、フレーム間の相関を利用しない場合の画素分割型並列処理方式がプロセッサ台数に比例してメモリ使用量が増加するのと比較して大きな特徴である。
ここでは、図３．１４に示すような画素分割型並列処理システムを想定する。全体のシステムはホストコンピュータ、それとシステムバスにより結合された各処理ユニット、フレームバッファバス、フレームバッファから構成される。ホストコンピュータはシステム全体の管理、オブジェクト情報の管理、各処理ユニットへの画素の割付情報の管理などを行う。各処理ユニットは、ホストコンピュータより各フレーム毎に移動物体のオブジェクト情報を受け取り、割り当てられた画素に関してそれぞれ独立に計算を行う。全処理ユニットが計算を終了したときそのフレームに関する処理が終了したことになる。
各処理ユニットが計算した輝度はフレームバッファバスを通してフレームバッファに書き込まれる。なお処理ユニット間の通信は行われないものとした。
以上のようなシステムの性能を評価するために、ＦＡＣＯＭ Ｍ３６０のＵＴＳ上にシミュレータを構築し、それによって、画像生成時間、稼働率、最大メモリ使用量を調べた。
各処理ユニットに画素をどの様に割り当てるかによって、負荷の分散の度合が変化することが考えられる[8]。 できるだけ光線追跡木を保存する画素を各処理ユニットに分散して配置する方が、メモリ使用量、稼働率両方の改善をはかることができる。ここでは、図３．１５に示した３種の割当方法と、乱数によってランダムに処理ユニットに画素を割り当てた場合についてシミュレーションを実行した。シミュレーションは、すべて空間分割数を１軸当り１６、画素数を１６０×１６０として行った。
図３．１６に、サンプル画像”ｒａｓｅｎ”のプロセッサ数と速度向上比の関係について示した。シーケンシャル型割当と、ドット型割当ではほとんど差はなく、ほぼ台数の増加とともにリニアな速度の向上がみられる。ランダム型割当の場合は、台数の増加につれて速度向上比がわずかに低下している。ブロック型割当の場合、他の割当方法に比較してかなり悪い結果となった。このことより、負荷分散の効果はドット≒シーケンシャル＞ランダム＞＞ブロックの順であることがわかる。これは、負荷の大きい部分が局在しているために、画面のある部分をまとめて一つのプロセッサに割り当てるブロック型では、負荷に片寄りが生じるためである。それに対して画面のとびとびの部分を一つのプロセッサに割り当てる方法は、平均的に負荷が分散される。
次に、図３．１７にサンプル画像”ｒａｓｅｎ”のプロセッサ数と稼働率の関係について示した。最も負荷分散の効果が高いと思われるドット型と、最も低いブロック型の結果を示した。なお、稼働率は各プロセッサの稼働時間の総和を、画像生成時間とプロセッサ数の積で割った値である。ドット型の場合、プロセッサ数２５６個の場合で稼働率は９０％程度を維持している。ブロック型の場合では、プロセッサ数の増加により稼働率は低下する。また、ブロック型においては、１枚目と比較して２枚目以降の稼働率がかなり下がっている。これは、光線追跡木を保存した画素数がプロセッサによって大きくばらついているためであると考えられる。
図３．１８に、サンプル画像”ｒａｓｅｎ”のプロセッサ数とメモリ要求量の関係について示した。なお、メモリ要求量は全プロセッサの中で最大のメモリ要求量を示した値にプロセッサ数を掛けたものである。ドット型では、プロセッサ数の増加に伴うメモリ要求量の増加のほとんどの部分が、オブジェクト情報のためのメモリ要求量の増加に起因していることが分かる。一方、ブロック型では、オブジェクト情報のためのメモリ要求量の増加に加えて、保存画素数のばらつきによる光線追跡木のためのメモリ要求量の増加もかなり見られる。
図３．１９に、サンプル画像”ｒａｓｅｎ”のプロセッサ数と相対メモリ要求量の関係について示した。なお、相対メモリ要求量はそれぞれの値を単一プロセッサにおけるメモリ要求量で割って正規化した値である。
負荷分散の効果が高いドット型の場合、オブジェクト情報のためのメモリ要求量はプロセッサ台数に比例して増加している。しかし、光線追跡木のためのメモリ要求量は単一プロセッサの場合に比較してもほとんど変化していないことがわかる。全体の要求メモリ量についてみると、プロセッサ数２５６台の場合においても単一プロセッサと比較して４倍以内の値となっている。負荷分散の効果が低いブロック型の場合においても、全体のメモリ要求量は５〜６倍程度である。
§３．４ 改良型部分更新光線追跡法
§３．２で述べた部分更新光線追跡法の場合、２フレーム目以降における再計算実行時に移動物体の影響を受ける光線を判定するためには、保存されている光線追跡木をルートから順にたどりtraverse listに登録されているcellについて一つずつ調べていく必要がある。部分更新光線追跡法を更に高速化するためには、この処理を高速に実行できるようにする必要がある。ここでは、各部分空間がどのフレームで移動物体を含むかを表す移動物体フラグを用いることによって、移動物体の影響を受ける光線の判定を高速化する改良型部分更新光線追跡法について提案する。
まず、オブジェクト空間を分割する際の処理であるが、従来の場合には移動物体の軌跡が通過するlocus cellであるか否かについてのみ記録したのに対して、さらにどのフレームでそのcellを移動物体が通過するかについての情報も記録する。これをcellに関する移動物体フラグと呼ぶ。現在、移動物体フラグは４バイト＝３２ビットで表現され、１シーンのフレーム数が３２以下の場合には１フレームにつき１ビット、３３以上６４以下の場合には２フレームを１ビットで表すことにしている。
１フレーム目における処理はほとんど従来の手法と同様に行われるが、光線を追跡する際に、光線が通過した各cellの移動物体フラグのビット毎の論理和をとりながら進むようにして、追跡が終わったときにそれを光線の移動物体フラグとして保存する。もし光線が物体と交差した場合には、光線追跡木上に新たなノードが生成されることになるが、各ノードにおけるノードの移動物体フラグは図３．２０に示すように、そのノードに関する光線および自分より下位のノードにおける移動物体フラグ全てのビット毎の論理和を取ることにより定義される。また、光線追跡木を保存するか否かの判定は、この各ノードや光線についての移動物体フラグが０であるか否かによって判定される。
次に、２フレーム目以降の再計算時における処理について述べる。再計算の必要性の判定はまず、各ノードにおける移動物体フラグと、前フレームと現フレームを表すビットを立てた判定用フラグのビット毎の論理積を取ることにより行われる。その結果が０となれば、そのノードより下位のレベルでは移動物体の影響を受けないことが分かり、再計算は不要となる。０以外の結果となった場合についてのみ、従来のアルゴリズムを用いた判定を実行すればよいことになり、高速化が図られる。以上のアルゴリズムについて、簡単な例を図３．２１〜図３．２２及び表３．３に示す。１、２フレーム間で移動物体が図３．２１のように移動する場合、各cellにおける移動物体フラグは図３．３２のようになる。ここで各光線に対する移動物体フラグは表３．３に示された値となる。後は上記のアルゴリズムにしたがって各光線についての移動物体の影響の有無が判定され、表３．３最下段のような結果が得られる。
以上の処理において、従来に加えて新たに実行される演算は、ビット毎の論理演算が主であり、これは浮動小数点演算に比べればはるかに簡単な処理であるので実行速度に対する悪影響は低く抑えることができる。一方、各cellに関する移動物体フラグや、ノードや光線に関する移動物体フラグを保存するために従来の手法に比べてメモリをより多く必要とする。
次章における実験で、この改良型アルゴリズムと従来のものについて、実行速度及びメモリ使用量に関して比較検討を行うことにする。
§３．５ 結言
本章では、部分更新光線追跡法に三次元空間等分割法を用いた、視点を固定した動画生成について検討した。その結果、各フレームの計算は従来の５〜１３倍の速度で計算可能であることがわかった。また、提案した方法に画素分割型の並列処理を導入した場合について、シミュレーションによる性能評価を示した。その結果、単一プロセッサの場合と比較して、あまりメモリ要求量を増加させることなく高い稼働率で並列処理を行うことが可能であることがわかった。また、移動物体フラグを用いることによって移動物体の影響を受ける光線の判定を高速化する手法についても述べた。
第４章 共有メモリ型並列計算機による
部分更新光線追跡法の性能評価
§４．１ 緒言
本章では、前章で述べた部分更新光線追跡法を、画素分割型の並列処理方式に基づいて共有メモリ型並列計算機上にインプリメントして実行した実験結果を示し、その有効性と問題点を明らかにする。
§４．２ 共有メモリ型並列計算機
４．２．１ ハードウェア
実験に使用した並列計算機は共有メモリ型の密結合マルチプロセッサシステムである[13][14][15]。そのシステム構成図を図４．１に示す。システム構成はローカル・キャッシュ付きのプロセッサ（最大１２個）で主記憶を共有し、各プロセッサカード間を高速バス（６４ｂｉｔ幅×２本でインタリーブ、転送速度８５Ｍｂｙｔｅ／ｓｅｃ）で結んだものとなっている。なお、プロセッサカードのうち１枚はハードディスク入出力に使用される。ハードディスク以外のＩ／Ｏは、マイクロチャネルインタフェースを介して接続されたワークステーション経由で行われる。また、専用のグラフィックス表示用ハードウェアは持っていないため、生成した画像はネットワークを経由し他のワークステーション上でＸｗｉｎｄｏｗを用いて表示される。
１つのプロセッサカードは以下のような構成となっている。
・ＣＰＵ：８０３８６（クロック１６ＭＨｚ）
・ＦＰＵ：８０３８７
Ｗｅｉｔｅｋ１１６７（８０３８７の２．５〜４倍の性能）
・キャッシュメモリ：１２８ＫＢｙｔｅ
カード１枚当りの性能は４ＭＩＰＳ，３．３ＭＦＬＯＰＳである。
実際に使用したのは１０プロセッサ構成のものである。これで３０ＭＩＰＳ程度の処理能力がある。
４．２．２ ソフトウェア
実験に使用した並列計算機のＯＳにはマルチプロセッサ用に改造されたＵｎｉｘ（ＳｙｓｔｅｍＶ＋ＢＳＤの一部）が採用されており、通常に使用する分には全く普通のＵｎｉｘと変わりなく使用できる。本来、シングルプロセッサのためのＯＳであるＵｎｉｘのマルチプロセッサへの対応方法はマスタ・スレーブ型を採用しており、１つのプロセッサのみがカーネル・プロセスを実行し、それ以外のプロセッサでユーザ・プロセスが実行される。
実際にプログラムを作成する場合、自動的に並列化するようなコンパイラ等はないので、プログラムを並列化するには、プログラム中で例えばシステムコールｆｏｒｋを用いて子プロセスを生成して行う。生成したプロセスをプロセッサに割り当てるのはＯＳが行う。また、プロセス間の通信や同期は、Ｕｎｉｘ ＳｙｓｔｅｍＶに備わっている共有メモリ及びセマフォに関するシステムコールを利用して行うことになる。このため、Ｕｎｉｘ ＳｙｓｔｅｍＶをＯＳとする通常の計算機上でもプログラム開発及びある程度のデバッグが可能である。
なお、浮動小数点演算用コプロセッサとしてＷｅｉｔｅｋ１１６７を使用する場合には、Ｃコンパイラとしてｇｃｃを使用しなければならない。
§４．３ 並列部分更新光線追跡法
前章で述べた部分更新光線追跡法を並列化して並列計算機上にインプリメントするに当たって、３．３．４節でシミュレーションを行った場合と同様に画素分割型の並列処理化を採用した。但し、シュミレーションの際に仮定したシステムは疎結合型であり、全てのプロセッサはローカルメモリのみを持ち、共有メモリは持たないものとしていたが、実験に使用した並列計算機は共有メモリ型であり、共有メモリ上にオブジェクト等のプロセス間で共通なデータを共有できる点が異なる。また、専用のフレームバッファもないため、計算された各画素の輝度は共有メモリ上に配置された配列に一旦書き込まれ、計算終了後にファイルに書き出される。
並列化した部分更新光線追跡法の実行の様子を、オブジェクト情報を共有メモリ上に配置した場合を例として図４．２に示す。まずプログラムが起動されると、システムコールによる共有メモリ、セマフォの取得をおこない、背景及び１フレーム目のオブジェクトデータを共有メモリ上に読み込む。次にプロセスに対する画素の割当を行ったのち子プロセスをｆｏｒｋして並列動作を開始する。子プロセスがそれぞれ割り当てられた画素の処理を行っている間、親プロセスは子プロセスの終了を待っている。子プロセスの実行が終了すると、子プロセスは親プロセスに終了を知らせたのち、親プロセスから次のフレームの処理開始の指令が出るまで待ち状態になる。全ての子プロセスの処理が終了すると、親プロセスは共有メモリに書き込まれた計算結果をファイルに書き出し、次のフレームのオブジェクト情報を読み込んでから子プロセスに実行開始の指令を出してまた待ち状態になる。以下、最終フレームの処理が終了するまで同様に繰り返される。なお、このような実行の同期処理はセマフォを用いて行われる。最終フレームの処理が終了すると、親プロセスはｗａｉｔシステムコールにより子プロセスがｅｘｉｔシステムコールで終了するのを待つ。子プロセスの終了処理が終わった後、共有メモリ、セマフォを解放してプログラムの実行を終える。
実験に使用したプログラムは部分更新アルゴリズムの改良前後の２種類のバージョンに大別できる。また、それぞれ１プロセスのものと複数のプロセスで実行するもの、オブジェクトやcellの移動物体フラグの情報を共有メモリ上に配置するか、それとも各プロセスに持たせるかなどによっていくつかの種類が存在する。それらの関係を表４．１に示す。
実験は、６種のサンプル画像について画素数１６０×１６０、オブジェクト空間の分割数は１辺当り１６で行い、画素割当法はブロック、シーケンシャル、ドットの３種類を用いた。複数プロセスのプログラムは、それぞれプロセス数２、４、８の場合について実行した。一部の画像では、１６プロセスについても実行してみた。但し、１−Ａ，１−Ｂのプログラムでは、８プロセス以上にすると実行不可能（理由は不明）だったので、２、４プロセスのみ行った。各プロセッサにおけるプロセスの実行状況を表示するユーティリティープログラムを用いて調べた１、４、８、１６プロセスのプログラムの実行状況を図４．３から図４．６にそれぞれ示す。実際にユーザ・プロセスが利用できるプロセッサは最大８台であるので、８プロセスまでは並列動作が可能であるが、１６プロセスの場合にはあふれたプロセスがキューに入れられて実行待ちとなっていることが分かる。
§４．４ 並列部分更新光線追跡法の性能評価
４．４．１ プロセス数と処理時間の関係
図４．７〜図４．９に、サンプル画像ＭＶＴＳＴについてプロセス数を変えて実行した結果を示す。実験には２及び２−Ｃのプログラムを用い、各プロセスに対する画素割当法はシーケンシャル型を用いた。それぞれ、全フレーム、１フレーム目、２フレーム目以降の平均の実行時間である。また、比較のため、他のシステム（NEWS,SUN-4,UTS）上で実行した結果も示した。なお、＋Ｏが付いているものはプログラムのコンパイル時に最適化を行ったことを示す。
理想的には、プロセス１つの場合の実行時間と比較して並列動作させるプロセス数分の一になることが望ましいが、実際には負荷の偏りや並列動作のためのオーバーヘッドなどのためにそこまで達することはないのが普通である。１フレーム目の実行結果では、２プロセスで１．９倍、４プロセスで３．７倍とかなり理想値に近い結果が得られているが、８プロセスでは６．７５倍とやや低下する。また、１６プロセスでは、システムが持つプロセッサ数を越えているため、かえって遅くなっている。一方、２フレーム目以降の平均の実行結果には、プロセス数分の一よりも大きなスピードアップが２、４プロセスの時に得られているといった、奇妙な現象がみられる。これは、膨大なメモリを使用する部分更新光線追跡法が並列化されることにより、１プロセス当りの使用メモリ量が減少し、キャッシュメモリの効果が増したことによるものと考えられる。
次に、画素割当法による負荷分散の効果について示す。実験には２及び２−Ｃのプログラムを用い、ブロック型（Ｂ）、シーケンシャル型（Ｓ）、ドット形（Ｄ）の３種類の画素割当法について調べた。３種のサンプル画像（ＭＶＴＳＴ、ＯＲＢＩＴ３、ＲＡＳＥＮ）についての実験結果をそれぞれ、図４．１０〜図４．１２、図４．１３〜図４．１５、図４．１６〜図４．１８に示す。１フレーム目では全ての画素が計算されるため、２フレーム目以降の平均と比較して３種の割当法の間の差は小さくなっている。しかし、２フレーム目以降の計算においては、再計算の行われる画素が画面上に偏って存在するようになるため、負荷分散の効果の高いシーケンシャル形、ドット形とブロック形の差が大きく開くようになる。これは３．３．４節におけるシミュレーション結果と同様であることが分かる。また、実験の結果、一般にシーケンシャル形の方がわずかにドット形よりも速度向上度が上回っていることが判明した。さらに、２、４プロセスの場合に、３種のサンプル画像どれについても２フレーム目以降の実行結果においてプロセス数以上の速度向上が認められた。
４．４．２ プロセス数とメモリ使用量の関係
実験に使用した各種のプログラムについて、３種のサンプル画像におけるプロセス数とメモリ使用量の関係を図４．１９〜図４．２１に示す。図中のｔｏｔａｌは全メモリ使用量、ｔｒｅｅは光線追跡木のみのメモリ使用量を示す。なお画素割り当てはシーケンシャル形を用いた。全メモリ使用量は１６０×１６０といった比較的少ない画素数にもかかわらず３〜５Ｍｂｙｔｅを必要としている。また、改良後のアルゴリズムを用いた場合、移動物体フラグの記憶のために従来よりも約７％ほどメモリ使用量が増している。今回実験に使用した共有メモリ形並列計算機の場合、光線追跡木の保存のために使用される総メモリ量は、各プロセスにおけるそれの和となり、これはプロセス数によってほとんど変化しない。従って、プロセス数を増したときのメモリ使用量の増加は、共有されないオブジェクト情報に起因するもののみである。従って、オブジェクト情報をすべて共有するプログラムでは、プロセス数を増しても総メモリ量はほとんど変化しない。オブジェクト情報を全く共有しないプログラムでも、光線追跡木のためのメモリ使用量が全メモリ使用量の７５〜９５％を占めているため、８プロセスの場合でも１プロセスにくらべてせいぜい１０〜１８％程度しか増加していない。
４．４．３ アルゴリズム改良の効果
１−Ｂ、２−Ｂ、２−Ｃのプログラムを用いて、６種のサンプル画像におけるプロセス数と処理時間の関係を調べた結果を図４．２２〜図４．３９に示す。なお画素割り当てはシーケンシャル形を用いた。１フレーム目の処理では余り差は見られないが、２フレーム目以降の処理においては、ＲＡＳＥＮ以外の画像では改良形の方（２−Ｂ、２−Ｃ）が従来のもの（１−Ｂ）と比較して平均１７％、最大で３０％近い速度の向上がみられた。このことから、高速化を目的としたアルゴリズムの改良は効果があることが分かった。しかし、サンプル画像ＲＡＳＥＮの場合は、ほとんど速度の向上がなかった。これは、移動物体が多数でしかも画面上の多くの部分を占めているため、他の画像と比較して移動物体フラグによる第１の判定だけで再計算の必要性を判定できる画素が少なかったためと考えられる。
４．４．４ オブジェクトの配置位置と処理時間の関係
図４．２２〜図４．３９にはまた、プログラム２−Ｂと２−Ｃの間のオブジェクト情報を配置する位置による処理時間への影響についても示してある。オブジェクト情報を共有した場合のように共有メモリ上のアドレスが同一の領域を頻繁に複数のプロセッサがアクセスするような場合、処理時間に影響が生じることが考えられたが、実験結果によると明らかな影響は認められなかった。従って、全体のメモリ使用量を少しでも低く抑えるようにするためにオブジェクトを共有した方が有利であると考えられる。
§４．５ 結言
本章では、前章で述べた部分更新光線追跡法を並列化して共有メモリ型並列計算機上で実行させた実験結果を示し、検討を行った。その結果、負荷分散を考慮した画素割り当て法を用いることにより、プロセス数にほぼ比例した速度向上が得られることが分かった。また、２フレーム以降の再計算においては、２、４プロセスの場合プロセス数以上の速度向上が得られた。さらに、オブジェクト情報の配置位置と実行速度及びメモリ使用量の関係を調べた結果、オブジェクト情報を共有しても速度にほとんど影響がなく、総メモリ使用量の面から考えて共有した方がよいということが分かった。更に、§３．４で述べたアルゴリズムの改良によって、画像によっては再計算時に２割近くの速度向上を図れることが分かった。
第５章 結論
光線追跡法は非常に高品質な画像を生成できる手法として注目されている。しかし、計算時間が膨大であるため、光線追跡法で動画を生成することは実用的でなかった。本論文では、光線追跡法による動画生成の高速化を目的とする部分更新光線追跡法について検討し、さらに、並列化した部分更新光線追跡法を共有メモリ型並列計算機上で実行した結果についても検討した。以下に、本論文の内容を総轄する。
第２章では、３次元図形表示アルゴリズムの一つである光線追跡法の基本概念と特徴について述べた。さらに、光線追跡法の最大の欠点である膨大な計算時間の原因について述べ、その高速化手法として空間分割法と並列処理について述べた。
第３章では、光線追跡法による動画生成の高速化を目的とした部分更新光線追跡法について述べた。これは、最初のフレームにおける計算結果を利用し、動画のフレーム間で変化する画素のみを再計算することによって高速化する方法であるが、移動物体の軌跡を利用して再計算が必要な画素に関する光線追跡木のみを保存することによって、全画素についての情報を保存する従来の方法よりもメモリ使用量を低く抑えることが可能になった。次に、本手法を画素分割型の並列処理システム上で実行した場合における性能について、シュミレーションを行い検討した。また、移動物体の影響を受ける光線をより高速に判定するアルゴリズムについて提案した。
第４章では、第３章で述べた部分更新光線追跡法を並列化し、実際に共有メモリ型並列計算機上で実行させた実験結果について、評価検討を行った。第３章におけるシミュレーションで高い稼働率を示した画素分割法を用いて負荷分散を図ることにより、プロセス数にほぼ比例した速度向上を得られることが分かった。また、プロセス間でオブジェクト情報を共有すれば、プロセス数を増しても全データ量を増加させずに済ますことが可能であるが、そうした場合でも速度に対する影響はほとんどないことが分かった。
以上、本論文の内容を総轄したが、以下に今後の課題を示す。
・ＣＳＧ表現やパッチなど球以外の形状の物体を含む複雑な画像における性能評価
・移動物体の数、大きさ、種類、移動軌道などを変化させた、各種の動画像を用いた性能評価
・現在、各プロセスごとに持っている光線追跡木の情報をプロセス間で共有し、２フレーム以降の再計算において画素再割当を行うことによる負荷均等化
などの問題が残されている。
謝辞
本研究を進めるにあたり、終始懇切なる御指導、ご鞭撻を賜りました木村正行教授に、厚く感謝致します。
また、ご教示、ご検討を賜りました竹田 宏教授、斎藤伸自教授に、深く感謝致します。
本研究室の阿曽弘具助教授、堀口 進助教授、下平 博助手には、日頃から細部にわたり多大な御指導、御助言を頂き、心より感謝致します。
中田武男氏をはじめ、日本ＩＢＭ�蠹豕�基礎研究所の皆様には、並列計算機における実験の際に大変御世話になりました。ここに深く感謝致します。
最後に、日頃より多大なご援助、ご協力を頂きました木村研究室の皆様に、厚く御礼申し上げます。
参考文献
[1] T.Whitted, "An Improved Illumination Model for Shaded Display",
Comm.ACM, Vol.23, No.6, June 1980, pp.343-349
[2] P.S.Heckbert, P.Hanrahan, "BEAM TRACING POLYGONAL OBJECTS", SIGGRAPH'84 Conference Proceedings, Vol.18, No3, July 1984, pp.119-127
[3] A.S.Glassner, "Space Subdivision for Fast Ray tracing", IEEE CG&A,
Vol.4, No.10, Oct.1984, pp.15-22
[4] A.Fujimoto, T.Tanaka, and K.Iwata, "ARTS: Accelerated Ray-Tracing System", IEEE CG&A, April 1986, pp.16-26
[5] 藤本 彰：”レイトレーシングの高速化技法について”，PIXEL, No.37,
Oct. 1985, pp.16-26
[6] 西村 他：”コンピュータグラフィックスシステムＬＩＮＫＳ−１における並列処理の性能評価”，電子通信学会論文誌, Vol.J68-D, No.4, April 1985,pp.733-740
[7] 石畑 他：”セルラ・アレイ・プロセッサＣＡＰによるＣＧシステム（前）”, PIXEL, No.60, Sep.1987, pp.113-116
[8] 村上 他：”セルラ・アレイ・プロセッサＣＡＰによるＣＧシステム（中）”, PIXEL, No.61, Oct.1987, pp.140-144
[9] 村上 他：”セルラ・アレイ・プロセッサＣＡＰによるＣＧシステム（後）”, PIXEL, No.62, Nov.1987, pp.136-138
[10] 吉田 他：”グラフィックス計算機ＳＩＧＨＴの基本構成”，情報処理学会研究報告， Vol.85-CA-60, No.60-5, Dec.1985
[11] 村上 他：”レイトレーシングにおけるフレーム間コヒーレンス方式”, 情報処理学会第３３回（昭和６１年度後期）全国大会, 4Q-6
[12] 広田 他：”部分更新レイトレーシング”，情報処理学会研究報告，87-CAD-27-5,Vol.87,No.46,Jul.,1987
[13] 横田 他：”１００ＭＩＰＳ時代へ向け、胎動を始めたマルチプロセサ型ワークステーション”，日経エレクトロニクス，No.461, 1988.11.28, pp.101-121
[14] 星 暁雄：”最大１２個の８０３８６が密結合で並列動作するワークステーションを試作”，日経エレクトロニクス，No.450, 1988.6.27, pp.100-101
[15] 鈴木 他：”高速並列処理ワークステーション（ＴＯＰ−１）”，情報処理学会第３７回（昭和６３年度後期）全国大会講演論文集, pp.171-183
発表論文リスト
［電気関係学会東北支部連合大会講演論文］
片平昌幸，堀口進，木村正行：”並列光線追跡法による動画生成の高速化”，昭６３ 東北支部連大，1B12
片平昌幸，堀口進，木村正行：”光線追跡法における八進木適応空間分割法”，平１ 東北支部連大，2C16
［ＮＩＣＯＧＲＡＰＨ論文コンテスト発表論文］
片平昌幸，堀口進，木村正行：”動画生成のための高速並列光線追跡法”，第４回ＮＩＣＯＧＲＡＰＨ論文コンテスト論文集，１９８８年１１月