JPH04213175A - 大域レンダリングで使用するための分散処理装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は一般に、三次元コンピュ
ータ・グラフィックスの分野に関している。より詳しく
は本発明は、ラジオシティー（ｒａｄｉｏｓｉｔｙ）ま
たはレイトレーシングなどの大域照射（ｇｌｏｂａｌ　
ｉｌｌｕｍｉｎａｔｉｏｎ）手法を用いる三次元グラフ
ィックス・レンダラーにおける光線交点計算（ｒａｙ　
ｉｎｔｅｒｓｅｃｔｉｏｎ　ｃａｌｃｕｌａｔｉｏｎｓ
）を速めるための方法及び装置に関している。

【０００２】

【従来の技術】三次元コンピュータ・グラフィックスを
作成するための多くの大域照射手法が知られているが、
そのうち最も一般的なものはレイトレーシング及びラジ
オシティーである。レイトレーシング及びラジオシティ
ーは何れも、（ｉ）　シーンに表現される対象から得た
表面要素（「多角形（ｐｏｌｙｇｏｎｓ）」）及び／ま
たはボックス（「境界ボリューム（ｂｏｕｎｄｉｎｇ　
ｖｏｌｕｍｅｓ）」）と、（ｉｉ）シーンの視点（レイ
トレーシング）またはシーンの光源（ラジオシティー）
から投じられる光線、との間の交差を検査することによ
り、そのシーンの大域照射を計算するものである。これ
らのステップは、多角形検査、ボックス検査及び／また
はシャドー検査と呼ばれることもある。以下の参照によ
ってその内容を本明細書に取り入れる以下の刊行物には
、シーンの大域照射を解決するためのレイトレーシング
及びラジオシティーの手法について記述してある。即ち
グラスナー（Ａｎｄｒｅｗ　Ｓ．　Ｇｌａｓｓｎｅｒ）
編集の「レイトレーシング入門」、Ａｃａｄｅｍｉｃ　
Ｐｒｅｓｓ、１９８９年（２章、３３−７７頁）、ケイ
（Ｋａｙ，Ｔ．Ｌ．）らの「レイトレーシング複合シー
ン」、ＳＩＧＧＲＡＰＨ　Ｐｒｏｃｅｅｄｉｎｇｓ、ｖ
ｏｌ．２０、ｎｏ．４、２６９−２７７　頁（１９８６
年８月）、グリーンバーグ（Ｇｒｅｅｎｂｅｒｇ　Ｄ．
Ｐ．）らの「ラジオシティー：大域照射の計算方法」、
Ｔｈｅ　Ｖｉｓｕａｌ　Ｃｏｍｐｕｔｅｒ、ｖｏｌ．２
、２９１−２９７頁（１９８６年）」、コーエン（Ｃｏ
ｈｅｎ　Ｍ．Ｆ．）らの「半立方体：複雑な環境でのラ
ジオシティー解法」、ＳＩＧＧＲＡＰＨ　Ｐｒｏｃｅｅ
ｄｉｎｇｓ、ｖｏｌ．１９、ｎｏ．３、３１−４０頁（
１９８５年）」がある。シーンの大域照射を解決するた
めの１つの現在推奨される方法であって、本発明が特別
の用途を持つものは、１９８９年４月３日に出願された
「ラジオシティーにおける形状因子の計算にレイトレー
シングを用いる三次元コンピュータ・グラフィックス」
と題する同時係属中の米国特許出願第３３２，７７７号
に記述されている。またワラス（Ｗａｌｌａｃｅ　Ｊ．
Ｒ．）らの「漸進ラジオシティーのためのレイトレーシ
ングアルゴリズム」、ＳＩＧＧＲＡＰＨ　Ｐｒｏｃｅｅ
ｄｉｎｇｓ、Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ、ｖ
ｏｌ．２３、ｎｏ．３、３１５−３２４頁（１９８９年
７月）も参照されたい。

【０００３】

【発明が解決しようとする課題】一般に、シーン内の対
象や光源の記述などを含む、表示すべきシーンを規定し
ているデータは、大域照射を計算するために大域レンダ
ラーの作動する（例えばレイトレーシング又はラジオシ
ティーにより）データベースに与えられ、また一般に光
線交点計算などのすべての計算は、ホスト・コンピュー
タで行われる。しかしながら従来技術の大域レンダラー
に関する問題の１つとして、光線交点計算に非常に時間
がかかることがある。大域照射の解決に要する大部分の
時間は、光線交点計算に費やされている。以下の刊行物
は一般に、大域照射の解決を速めるためのハードウェア
及びソフトウェア・システムについて記述してある。ポ
トメシル（Ｐｏｔｍｅｓｉｌ　Ｍ．）らの「ピクセル・
マシン：パラレル・イメージ・コンピュータ」、ＳＩＧ
ＧＲＡＰＨ　Ｐｒｏｃｅｅｄｉｎｇｓ、ｖｏｌ．２３、
ｎｏ．３、６９−７８頁（１９８９年７月）、アケレイ
（Ａｋｅｌｅｙ　Ｋ．）らの「高性能多角形レンダリン
グ」、ＳＩＧＧＲＡＰＨ　Ｐｒｏｃｅｅｄｉｎｇｓ、ｖ
ｏｌ．２２、ｎｏ．４、２３９−２４６頁（１９８８年
８月）等がこれである。しかしながらこれらのシステム
は、大域レンダリングにおける光線交点計算を速めるた
めの必要性に適切に応えてはいない。

【０００４】そこで光線交点計算を速めるため、レイト
レーシング又はラジオシティー（または光線交点に依存
する他の何らかの大域照射手法）と共に用いることがで
き、実施が簡単かつ効率的に、さらに比較的廉価に行う
ことのできる方法及び装置を提供することが望ましい。 本発明はこれらの課題を解決するものである。

【０００５】

【課題を解決するための手段】ホスト・コンピュータは
、シーンに表示される対象から得た境界ボリューム及び
多角形を示すデータなどの、ディスプレイ上に表示され
るシーンを規定するデータを記憶するためのデータベー
スを含んでいる。本発明によれば、ホストから与えられ
る選ばれた境界ボリューム及び多角形のデータについて
光線交点計算を行うよう各々がプログラムされたＰ個の
複数の変換プロセッサから成る変換エンジンが設けられ
る。ホストに記憶されたすべての境界ボリューム及び多
角形のデータについての光線交点計算は、Ｐ個の変換プ
ロセッサにわたって分散される。

【０００６】共用メモリが、変換エンジン及びホストと
通信して作動可能なように結合されており、変換プロセ
ッサの各々はその光線交点計算の結果を共用メモリに記
憶するようにプログラムされており、それがホストコン
ピュータによって検索可能である。本発明の一つの実施
例によれば、境界ボリューム及び多角形のデータをホス
トから変換エンジンに迅速に転送するために、ホストと
変換エンジンの間にはブロック・データ転送経路が与え
られている。このブロック・データ転送経路はＤＭＡ（
直接メモリ・アクセス）回路から構成することができる
。本発明の別の実施例によれば、変換エンジンは多数の
専用メモリを含み、変換プロセッサの各々に一つの専用
メモリが関連している。この実施例によれば、ホストか
らのデータはＤＭＡサイクルで専用メモリに直接記憶さ
れ、各々の変換プロセッサにより処理される。

【０００７】さらに別の実施例では、境界ボリューム及
び多角形のデータは各専用メモリのシーケンシャルメモ
リ位置にデータワードとして記憶され、各変換プロセッ
サは、それぞれに関連する専用メモリのＰ番目のデータ
ワード毎（Ｐは変換プロセッサの数）に光線交点計算を
行うようにプログラムされている。変換プロセッサが全
体としてデータワードのすべてについて光線交点計算を
行うように、各変換プロセッサは、他のすべての変換プ
ロセッサとは異なるデータワードで開始する。光線交点
計算の結果はその後、ホストにより検索するために共用
メモリに記憶される。

【０００８】本発明を実施する望ましい方法では、以下
のステップが行われる： （ａ）　ホストコンピュータに、境界ボリューム及び多
角形のデータを含むグラフィックス・データを記憶する
こと、 （ｂ）　境界ボリューム及び多角形のデータを、ブロッ
ク・データ転送によりホストから、Ｐ個の複数の変換プ
ロセッサ及び関連する専用メモリから成るタイプの変換
エンジンに伝送し、該データをデータワードとして専用
メモリのシーケンシャルメモリ位置に記憶すること、（
ｃ）　各々の変換プロセッサを他の変換プロセッサとは
異なるデータワードで開始させ、それぞれに関連する専
用メモリのＰ番目のデータワード毎に光線交点計算を行
うことにより、境界ボリューム及び多角形のデータにつ
いて行われる光線交点計算をＰ個の変換プロセッサにわ
たって分散させること、 （ｄ）　光線交点計算の結果を共用メモリに記憶するこ
と、及び （ｅ）　最後の変換プロセッサが光線交点計算を完了し
た後、大域レンダリングのために、共用メモリに記憶さ
れた光線交点計算の結果をホストコンピュータに伝送す
ること。

【０００９】本発明のさらなる詳細は、以下の詳細な説
明及び特許請求の範囲を読むことによって明らかとなる
ものである。

【００１０】

【実施例】添付図面を参照すると、そこでは同じ符号は
同じ構成要素を表している。図１には、本発明の装置及
び方法を用いることのできるコンピュータ・グラフィッ
クス・レンダラー１０のブロック図が示されている。し
かし本発明が図１に示すタイプのグラフィックス・レン
ダラーに限定されないことは理解すべきである。本発明
は、レイトレーシング又はラジオシティーなどの大域照
射手法を用いるどのようなグラフィックス・レンダラー
と関連しても用いることができる。

【００１１】グラフィックス・レンダラー１０の詳細は
、「グラフィックス・システムにおけるウィンドゥの加
速方法及び装置」と題する同時係属中の特許出願明細書
により詳しく記述してある。また、ローデン（Ｒｈｏｄ
ｅｎ　Ｄ．）らの「ウィンドゥ・システムのためのハー
ドウェア加速」、ＳＩＧＧＲＡＰＨ　Ｐｒｏｃｅｅｄｉ
ｎｇｓ，　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ，　ｖ
ｏｌ．２３，ｎｏ．３，６１−６７　頁（１９８９年７
月）も参照せよ。特許請求の範囲に記載の事項を除き、
グラフィックス・レンダラー１０の詳細は本発明の一部
を構成するものではなく、本明細書においては詳述する
ことはしない。これについては、上述した文献を参照さ
れたい。ここでは図１のグラフィックス・レンダラー１
０が、インタフェース１６を介して変換エンジン１４と
通信するホスト・コンピュータ１２を含んでいることを
述べるにとどめる。変換エンジン１４は、グラフィック
ス・データをレンダリングＶＬＳＩ（超大規模集積回路
）１８と交信し、ＶＬＳＩは次にウィンドゥ回路２０と
交信する。ウィンドゥ回路２０は、データをフレーム・
バッファ２２に送り、該バッファはビデオ発生器２４と
交信する。ビデオ発生器２４は、ラスター・ディスプレ
イ２６上の画像表示をコントロールする。データはまた
、ホスト・コンピュータ１２からインタフェース回路１
６及びパイプライン・バイパス２８を介して、ウィンド
ゥ回路２０、フレーム・バッファ２２、及びビデオ発生
器２４にも交信される。図１のタイプのグラフィックス
・レンダラーを用いる場合には、本明細書で詳細に述べ
るように、本発明の装置及び方法を、ホスト・コンピュ
ータ１２、インタフェース１６、及び変換エンジン１４
に組み込むことが望ましい。

【００１２】次に図２を参照すると、そこには本発明の
原理を具体化した装置のブロック図が示してある。図示
のように、ホスト・コンピュータ１２は図１と同様にし
て、インタフェース（ＩＦＵ）１６により変換エンジン
１４と交信する。しかしこの場合インタフェース１６に
はブロック・データ転送回路が設けられており、これは
望ましい実施例ではＤＭＡ回路３０である。さらに、図
１のブロック図とは異なり、変換エンジン１４はＰ個の
多数の変換プロセッサ３４とこれに関連する専用メモリ
３２から成る。 これについては後で詳細に述べる。

【００１３】シーンに表示される対象から得た境界ボリ
ューム及び多角形を示すデータを含むシーンを規定する
データ、並びに境界ボリュームや多角形と交わる光線を
規定するデータは、ホスト・コンピュータ１２のメモリ
に記憶される。境界ボリューム及び多角形データ、及び
光線記述データは、後でより詳細に説明するようにして
、ブロック・データ転送（ＤＭＡサイクルが望ましい）
でもって専用メモリ３２の各々に迅速に転送される。し
たがって、ホストがデータをダウンロードした後には、
専用メモリ３２の各々には、同じ境界ボリューム及び多
角形データ並びに光線記述データが含まれる。境界ボリ
ューム及び多角形データは、各専用メモリ３２のシーケ
ンシャルメモリ位置にデータワードとして記憶されるこ
とが望ましい。以下で明らかにされるように、各変換プ
ロセッサは、ホスト１２により与えられ関連する専用メ
モリ３２に記憶された、選ばれた境界ボリューム及び多
角形データだけについて光線交点計算を行うようにプロ
グラムされており、境界ボリューム及び多角形データに
ついての光線交点計算結果はすべて、変換プロセッサ３
４に送られる。 やはり後に詳細に説明するが、望ましい実施例において
は、変換プロセッサの各々はそれに関連する専用メモリ
におけるＰ番目のデータワード（Ｐは変換プロセッサ３
４の数に等しい）毎に光線交点計算を行うようにプログ
ラムされており、変換プロセッサが全体としてすべての
データワードについての光線交点計算を行うように、各
々の変換プロセッサは他の変換プロセッサとは異なるデ
ータワードで始動する。

【００１４】図２にも示してあるように、バス４２を介
して変換プロセッサ３４の各々と通信する共用メモリ３
６を設けることが望ましい。二重ポート通信レジスタ３
８も設けられているが、これは各変換プロセッサ３４と
通信し、バス４２、４６を介してマルチプレクサ４０と
も通信するものである。通信レジスタ３８の読み出し専
用出力４４も、以後に明らかになる理由によりマルチプ
レクサ４０への入力として与えられる。図示のように、
マルチプレクサ４０は、ホスト１２、共用メモリ３６及
び通信レジスタ３８の間に配置され、以下で明らかにさ
れる手法によって、これらの間の情報の流れを指図して
いる。

【００１５】各変換プロセッサ３４は、光線交点計算の
中間結果を関連する専用メモリ３２に記憶するようにプ
ログラムされていることが望ましく、また光線交点計算
が完了したときに、すべての光線交点計算結果を関連メ
モリ３２から共用メモリ３６に記憶させるようにプログ
ラムされている。以下で明らかになるように、共用メモ
リ３６には、変換プロセッサ３４の数に対応するＰ個の
ビット位置を有する完了レジスタが含まれる。各変換プ
ロセッサ３４は、ある変換プロセッサがその光線交点計
算結果を共用メモリ３６に記憶するときに、これに対応
する完了レジスタのビットをセットする。完了レジスタ
の最後のビットをセットする変換プロセッサ３４は、そ
の後に通信レジスタ３８のフラグをセットする。ホスト
コンピュータは、マルチプレクサ４０、バス４６及び読
み出し専用出力４４を介して通信レジスタを周期的にポ
ーリングし、出力４４において立っているフラグの存在
を検出すると、光線交点計算結果をマルチプレクサ４０
を介して共用メモリ３６から検索する。所望の場合には
、共用メモリ３６からのデータを、ＤＭＡ回路３０を通
してブロック・データ転送によりホスト・コンピュータ
１２に転送することができる。したがって、共用メモリ
のデータをホストにより検索する準備が整ったという通
知を、通信レジスタが提供するということが理解されよ
う。通信レジスタはハンドシェーキング手法によりポー
リングされることが望ましく、該手法では、通信レジス
タ３８がアドレス指定され、マルチプレクサ４０を介す
るホスト１２への出力４４にフラグの状態が与えられる
。

【００１６】以下の説明から明らかになるように、変換
プロセッサ３４の各々は、光線交点計算を完了するに際
して共用メモリ３６を要請し（すなわち、他のすべての
変換プロセッサ３４を除外する）、自己の光線交点計算
結果を記憶することが許可される。当該変換プロセッサ
からのすべての光線交点計算結果が共用メモリ３６に記
憶された後に共用メモリ３６は解放され、今度は別の変
換プロセッサ３４がその結果を同様にして記憶すること
ができるようになる。

【００１７】本発明の望ましい実施においては、各変換
プロセッサ３４には、他の変換プロセッサを除いてそれ
自体を固有に識別するコードを有する情報レジスタ８０
（図５）が含まれる。光線交点計算を計算するための開
始データワードは、当該変換プロセッサの情報レジスタ
８０に記憶されたコードに従って決められるのが望まし
い。図５に、情報レジスタの１つの実施例を示す。図示
のように、情報レジスタ８０にはＰ個の多数のビット位
置があり、そこにおいてＰは変換エンジン１４の変換プ
ロセッサ３４の数と等しい。情報レジスタ８０は各変換
プロセッサ３４に設けられ、各情報レジスタの１つのビ
ットだけがセットされている。セットされる特定ビット
は、当該変換プロセッサを固有に識別するだけでなく、
その特定の変換プロセッサが他の変換プロセッサに対し
てどこに置かれているのかをも示す。例えば、レジスタ
８０のビット位置３が特定の変換プロセッサ３４におい
てセットされている場合、それはその変換エンジンが行
内の３番目であることを示している。

【００１８】次に図３及び図４を参照すると、本発明の
方法が非常に詳細に記述されている。注記した点を除き
、図３及び図４のフローチャートは各変換プロセッサ３
４の動作を示す。したがって、各変換プロセッサ３４は
同様な方法で作動する。各変換エンジンは、マイクロコ
ンピュータなどのプログラム可能な装置であることが望
ましく、図３及び図４に示す機能を行うようにプログラ
ムされる。

【００１９】ブロック５０に示すように、各変換プロセ
ッサ３４はホストコンピュータ１２からの光線交差コマ
ンドを待っている。換言すれば、データベースが確立さ
れ、光線の記述が定義されて、境界ボリューム及び多角
形のデータがホストから得られた後に、周知の方法によ
って変換プロセッサ３４により光線交差を行うことがで
きる。変換プロセッサ３４が光線交差コマンドを受け取
ると、そのプロセッサは５２に示すようにして、そのコ
マンドが光線セットアップ・コマンドであるかどうかを
問い合わせる。言い換えると、その変換プロセッサ３４
は、そのコマンドが境界ボリューム及び多角形のデータ
と交差するための光線をセットアップするためのもので
あるかどうかを問い合わせるのである。そのコマンドが
光線セットアップ・コマンドであったならば、望ましく
はＤＭＡ３０を介してのブロック・データ転送により、
光線記述データがすべての専用メモリ３２にダウンロー
ドされる。光線記述データは、すべての専用メモリ３２
に与えられて記憶される。

【００２０】ステップ５２で、コマンドが光線セットア
ップ・コマンドではないことが確認されると、そのコマ
ンドは変換プロセッサが光線交点計算の実行を開始する
ためのものであると仮定される。光線交点計算を行うた
めには、すべての境界ボリューム（ＢＶ）または多角形
（ＰＧＯＮ）のデータを、すべての専用メモリ３２にも
供給して記憶しなければならない。ステップ５６に示さ
れているように、このデータは、ＤＭＡ回路３０を介し
てブロック・データ転送によりホスト１２から全ての専
用メモリ３２に迅速にダウンロードされる。すべての境
界ボリューム及び多角形のデータが専用メモリ３４にダ
ウンロードされたならば、ステップ５８以下に示す機能
を行うことができる。

【００２１】この時点では、各専用メモリ３２の情報内
容が同じであることが理解されよう。しかし光線交点計
算をすべての変換プロセッサ３４に分散して行わせるた
めには、各変換プロセッサに対し、光線交点計算を行う
について別々のデータを選択するように指令する方法を
用意せねばならない。このことについては一般的にステ
ップ５８に示してあるが、計算を行うためのデータを選
択する手順については、図６のフローチャートにより詳
しく示してある。

【００２２】図６のステップ９０に示されているように
、各変換プロセッサは、関連する専用メモリ３２にある
最初の境界ボリューム／多角形データワードを指示する
ように最初にセットしてあるソフトウェア・ポインタ（
「ＰＯＩＮＴＥＲ」）を用いる。変数ＢＶは最初は１に
セットされている。また、Ｐビット計数レジスタは最初
に、その最下位ビットだけが１でありその中の他のすべ
てのビットが０であるようにセットされている。簡単の
ために、この計数レジスタはフローチャートでは、「ｉ
」で示してある。ステップ９２では、レジスタｉの内容
が、その特定の変換プロセッサの情報レジスタ８０（図
５）と同じであるかどうかを確かめるための検査が行わ
れる。同じでなければ、変数ＢＶは１だけ増加され、ソ
フトウェア・ポインタは、関連する専用メモリ３２にあ
る次の境界ボリューム／多角形データワードを指示する
ように増加される。次に、計数レジスタ「ｉ」の内容は
１ビット位置分だけ左にシフトされ、それまで最下位ビ
ット位置にあったビットが、今度は最下位ビット位置の
隣にくる。 ステップ９２、９４は、計数レジスタ「ｉ」の内容と各
変換プロセッサ３４の情報レジスタ８０の内容の間に一
致が得られるまで、繰り返し行われる。特定の変換プロ
セッサ３４において一致が得られたならば、その変換プ
ロセッサは、図４に示すステップ６０以下を続けて行う
。こうして各変換プロセッサ３４について異なる開始デ
ータワードが選択され、各変換プロセッサ３４は異なる
データワードで光線交点計算を始めることが理解されよ
う。また、各変換プロセッサ３４の開始データワードが
、関連する情報レジスタ８０に記憶されたコードに従っ
て決まることも理解されるよう。

【００２３】今度は図４を参照するが、特定の変換プロ
セッサ３４についての開始データワードが突き止められ
ると、そのデータワードにより示される境界ボリューム
または多角形についての光線交点計算が行われうること
が看取されよう。光線交点計算を行う方法は技術的に周
知であり、本発明の一部をなすものではない。これにつ
いては例えば、レイトレーシング入門という表題の前述
の刊行物を参照されたい。その特定の境界ボリューム／
多角形についての光線交点計算が完了したならば、変換
プロセッサ３４は、この計算によって境界ボリュームま
たは多角形と光線との実際の交差がもたらされたかどう
かを問い合わせる。交差が生じた場合には、ステップ６
４に示すようにその計算結果はその変換プロセッサに関
連する専用メモリ３２に一時的に記憶され、ステップ６
６が次に行われる。計算結果から、境界ボリューム／多
角形と光線との交差がないことが分かったならば、その
特定の境界ボリューム／多角形に関連する専用メモリ３
２にはデータは記憶されず、ステップ６６が次に行われ
る。

【００２４】ステップ６６では、変換エンジンにある変
換プロセッサの数、すなわちＰだけループ・カウントが
増加される。ステップ６８では、境界ボリューム／多角
形ポインタ（最初は図６のステップ９０でセットされ、
ステップ９４で増加される）もまた、システムの変換プ
ロセッサ３４の数、すなわちＰだけ増加される。ステッ
プ７０では、その変換プロセッサに関連する専用メモリ
３２のすべての境界ボリューム／多角形のデータが処理
されたかどうかについて問い合わせられる。処理されて
いなければ、専用メモリ３２のすべてのデータが処理、
すなわち光線交差について検査されるまで、ステップ６
０−６８　が繰り返される。

【００２５】以上のことから、各変換プロセッサ３４が
関連する専用メモリ３２にあるＰ番目のデータワード毎
に光線交点計算を行い、また変換プロセッサ全体でホス
ト・コンピュータ１２から渡されたすべてのデータワー
ドについて光線交点計算を行うように、各変換プロセッ
サ３４がシステム中の他の変換プロセッサとは異なるデ
ータワードで開始することが理解されよう。こうして光
線交点計算は、すべての変換プロセッサ３４へと、実質
的に均一に分散される。さらに、各変換プロセッサがス
テップ６０−６８（図４）を行うに際して、光線交点計
算の中間結果が、関連する専用メモリ３２に記憶される
ことも理解されよう。各変換プロセッサ３４は光線交点
計算を完了すると、ブロック７２に示すようにして、（
関連する専用メモリ３２に記憶された）その結果を共用
メモリ３６に書き込む。図８に、それを行う方法を示す
。

【００２６】図８について述べる前に、共用メモリ３６
の望ましい構成について記述しておくことが有用である
。 図７に示すように、共用メモリ３６は以下のデータを含
むように構成されていることが望ましい。第一は「完了
レジスタ」である。前述したように、これは、Ｐ個の変
換プロセッサの各々に対応する１つのビット位置を有す
るＰビット・レジスタであることが望ましい。各変換プ
ロセッサ３４が光線交点計算を完了して結果を共用メモ
リに記憶すると、完了レジスタのこれに対応するビット
位置がセットされる。これは、情報レジスタ８０に記憶
されるのと同じビットである。既に述べたように、完了
レジスタの最後のビットをセットする変換プロセッサは
、光線交点計算の結果を共用メモリ３６から検索可能で
あるということをホストコンピュータ１２に知らせるた
めに、通信レジスタ３８のフラグもセットする。第二は
「実行交点の合計（ｒｕｎｎｉｎｇ　ｔｏｔａｌ　ｉｎ
ｔｅｒｓｅｃｔｉｏｎｓ）」を示すデータワードである
。これは、各変換プロセッサ３４から返される交点の数
の実行カウントである。第三は「ワードの合計」を示す
データワードである。「ワードの合計」は、ホストコン
ピュータ１２に転送するために共用メモリに記憶される
データワードの数を示す。これは、ＤＭＡサイクルを介
して共用メモリ３８から結果を検索することを望む場合
に、データのブロック・サイズの合計を利用できるよう
にするために提供される。第四は「光線交点の合計」を
示すデータワードである。これは、すべての変換プロセ
ッサ３４により検出される交点の合計数を示す。 「交点の合計」と「実行交点の合計」の相違は、各変換
プロセッサがその光線交点計算結果を共用メモリに記憶
するときに、「実行交点の合計」が連続的に更新される
ことである。「交点の合計」は、交点の最終的な合計数
を示す。第五は、各変換プロセッサ３４により与えられ
る実際の光線交点計算結果である。

【００２７】今度は図８を参照すると、光線交点計算結
果を、専用メモリ３２の各々から共用メモリ３６に転送
するためのルーチンが示されている。１００で示されて
いるように、各変換プロセッサ３４は光線交点計算を完
了すると、共用メモリ３６を要求してから待ちループに
進む。共用メモリがその変換プロセッサ３４（すなわち
他のすべての変換プロセッサを除く）に許可されると、
その変換プロセッサは１０２に示すようにして、すでに
述べた「完了レジスタ」の各ビットをセットする。ステ
ップ１０４では、その変換プロセッサが光線交点計算の
結果、交点がないことを検出したかどうかについて問い
合わせが行われる。実際に交点がある場合には、１０６
に示すステップが行われる。特に、光線交点結果はその
変換プロセッサに関連する専用メモリ３２から共用メモ
リ３６にコピーされ、実行交点の合計を示すデータワー
ドは更新されて、その変換プロセッサにより検出された
さらなる交点の数が反映される。ステップ１０４で交点
が一つも検出されないことが確認されると、その変換プ
ロセッサに関連する専用メモリ３２からはデータはコピ
ーされず、１０８に示す機能が行われる。

【００２８】ステップ１０８では、すべての変換プロセ
ッサが共用メモリ３６に光線交点計算結果を記憶したか
どうかについての問い合わせがされる。記憶されていな
い場合には、次の変換プロセッサが光線交点計算結果を
転送することができるように共用メモリが解放されてい
るステップ１１２へと、制御は直接に移動する。他方、
それが最後の変換プロセッサであることが、完了レジス
タのすべてのビットがセットされていることにより示さ
れるならば、１１０に示すように幾らかの共用メモリ・
ハウスキーピングを最初に行わねばならない。特に、す
べての変換プロセッサが共用メモリに光線交点計算結果
を記憶したならば、通信レジスタのフラグを立てねばな
らず、完了レジスタはゼロにされねばならない。さらに
「実行交点の合計」データワードは、共用メモリの「交
点の合計」メモリ位置にコピーされる。「ワードの合計
」（ホストコンピュータに転送されるデータワードの合
計数）が次に計算され、共用メモリの「ワードの合計」
位置に記憶される。最後に「実行交点の合計」データワ
ードがクリアされる。これで共用メモリ３６は変換エン
ジン１４から新しいデータを受信する準備ができたこと
になる。

【００２９】図９及び図１０は、光線交点計算の結果と
して共用メモリ３６に記憶されるデータの種類を示す。 図９は、光線Ｒ０と境界ボリューム１２０の交差を示す
。光線Ｒ０と境界ボリューム１２０との交点は、光線が
境界ボリューム１２０に進入しまた退出する光線Ｒ０に
沿うパラメータ距離をそれぞれ表す、２つの指標ｔｎｅ
ａｒ及びｔｆａｒをもたらす。図１０は、光線Ｒ０の多
角形１３０との交点を示す。多角形は平面であるから、
１つの値、即ち多角形１３０　と交差する光線Ｒ０に沿
うパラメータ距離を表す値ｔｄｉｓｔだけを返すことが
必要である。

【００３０】

【発明の効果】本発明は、三次元コンピュータ・グラフ
ィックス・レンダラーにおける光線交差プロセスを、非
常に大きく加速するものである。本発明は、その思想ま
たは本質的な属性から逸脱することなく、どのような特
定の形態でも実施することができ、従って本発明の範囲
を示すものとしては、以上の発明の詳細な説明ではなく
、添付の特許請求の範囲を参照すべきである。

【図面の簡単な説明】

【図１】本発明の装置及び方法を用いることのできるコ
ンピュータ・グラフィックス・レンダラーのブロック図
である。

【図２】本発明の原理を具体化した装置のブロック図で
ある。

【図３】本発明の方法を示すフローチャートである。

【図４】本発明の方法を示すフローチャートである。

【図５】本発明の好ましい実施例の具体化に基づき設け
られる情報レジスタの概念を例示する図である。

【図６】本発明のさらなる詳細を示すフローチャートで
ある。

【図７】本発明の実施による共用メモリの好ましい構成
を示す図である。

【図８】本発明の方法の別のさらなる詳細を示すフロー
チャートである。

【図９】光線交点計算の結果として与えられるデータの
タイプを概念的に示す図である。

【図１０】光線交点計算の結果として与えられるデータ
のタイプを概念的に示す図である。

【符号の説明】

１０　　コンピュータ・グラフィックス・レンダラー１
２　　ホスト・コンピュータ １４　　変換エンジン １６　　インタフェース １８　　レンダリングＶＬＳＩ ２０　　ウィンドゥ回路 ２２　　フレーム・バッファ ２４　　ビデオ発生器 ２６　　ラスター・ディスプレイ ２８　　パイプライン・バイパス ３０　　ＤＭＡ回路 ３２　　専用メモリ ３４　　変換プロセッサ ３６　　共用メモリ ３８　　二重ポート通信レジスタ ４０　　マルチプレクサ １２０　　境界ボリューム １３０　　多角形

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　ａ）　　シーンに表示される対象から
   得た境界ボリューム及び多角形（１２０，１３０）を示
   すデータを含めて、ディスプレイ装置（２６）上に表示
   されるシーンを規定するデータを記憶するホストコンピ
   ュータ（１２）と、ｂ）　　ホストコンピュータ（１２
   ）により供給された境界ボリューム及び多角形の選ばれ
   たデータについて光線交点計算を行うよう各々プログラ
   ムされているＰ個の複数の変換プロセッサ（３４）から
   なる変換エンジン（１４）とからなり、ホストコンピュ
   ータ（１２）に記憶された境界ボリューム及び多角形の
   全てのデータについての光線交点計算が、Ｐ個の変換プ
   ロセッサ（３４）にわたって分散される、大域レンダリ
   ングで使用するための分散処理装置。