JPH0632046B2

JPH0632046B2 - 物体画像合成装置

Info

Publication number: JPH0632046B2
Application number: JP31183286A
Authority: JP
Inventors: 啓次根本
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1986-12-29
Filing date: 1986-12-29
Publication date: 1994-04-27
Anticipated expiration: 2009-04-27
Also published as: JPS63167986A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、物体を表示するための画像を合成する物体画
像合成装置に関する。

〔従来の技術〕

物体を表示するためのディジタル画像を合成する方法と
して、光線探索法と呼ばれる方法がある。この方法で
は、光源から視点に至る光線の経路を逆向きに辿って、
光線と物体との交差判定処理を行ない、その結果に基づ
いて画像を構成する各画素の輝度を計算する。この光線
探索法の一例は、情報処理学会論文誌、第２５巻、第６
号、出口弘、西村仁志、吉村浩、河田亨、白川功、大村
皓一著、論文「コンピュータグラフィックスシステム
ＬＩＮＫＳ−１における画像生成の高速化手法」に記載
されている。

このような光線探索法による画像生成を高速に行なうた
めに、物体の定義されている空間を複数の領域に分割し
て、各領域をそれぞれ１台のコンピュータに割り当て
て、各コンピュータが割り当てられた領域を通過する光
線の処理を行なう方法が提案されている。この方法の詳
細は、コンピュータグラフィックス（Computer Graph
ics）、第１８巻、第３号、マーク・ディッペ（Mark Di
ppe）、ジョン・スウェンセン（John Swensen）著、論
文「アンアダプティブサブディヴィジョンアルゴ
リズムアンドパラレルアーキテクチャフォア
リアリスティックイメージシンセシス（An Adaptive
Subdivision Algorithm and Parallel Architecture fo
r Realistic Image Synthesis）」に記載されている。

上述の方法においては、空間はまず直方体形状の複数個
の領域に分割され、各領域がそれぞれ１台のコンピュー
タに割り当てられる。次に、各コンピュータには、割り
当てられた直方体形状の領域に含まれる物体のデータが
記憶される。そして、各コンピュータでは、割り当てら
れた領域を通過する光線と物体との交差判定処理が行な
われる。この交差判定処理により、物体と光線が交差し
た場合には、物体表面における反射，透過処理が行なわ
れる。その領域内で物体と交差しない光線の情報は、隣
接する領域に割り当てられたコンピュータへ転送され
る。

このような処理を行なう場合、各コンピュータの処理量
にかなりのばらつきが生じてしまう可能性がある。すな
わち、多くの物体を含む領域を割り当てられたコンピュ
ータの処理量は非常に多く、物体を全く含まない領域を
割り当てられたコンピュータでは、ほとんど処理が行な
われないといった場合がある。

このようなコンピュータ間の負荷のばらつきを減少させ
るために、直方体に分割された領域の頂点を任意に移動
して、領域の体積や形状を変化させる方法が提案されて
いる。すなわち、頂点を移動することにより体積が減少
した領域に割り当てられたコンピュータの処理量は減少
する。そして、その頂点の移動により体積が増加した領
域に割り当てられたコンピュータにその分の処理が分担
されるのである。こうして、各コンピュータ間の負荷の
再配分が行なわれる。

〔発明が解決しようとする問題点〕

このような従来の負荷の再配分方法では、領域の頂点を
移動して負荷の再配分を行なうために、領域の形状が様
々に変化してしまう。すなわち、頂点の移動による変形
なので、領域の形状は六面体に保たれるが、領域の各境
界面の向きや形状は任意となる。このため、次のような
問題点が生じる。

第一に分割された領域から隣接する領域へ光線の情報を
伝達する場合、領域の境界面と光線との交差判定によ
り、転送すべき領域を決定する。しかし、領域の各境界
面の向きや形状が任意なので、この交差判定処理の処理
量が非常に多くなってしまう。このため、全体の処理時
間も遅くなってしまうという問題点がある。

第二に、領域の形状が変化された場合、領域に含まれる
物体の情報も変化させなければならない。すなわち、体
積が減少した領域の場合、変化以前にその領域に含まれ
ていた物体のうちで、変化以後にはその領域に含まれな
いものが存在する可能性がある。また、体積が増加した
領域の場合は、新たな物体がその領域に含まれる可能性
がある。このような物体情報の変更を行なう場合も、領
域の形状が様々なので、その領域に含まれる物体を判定
する処理に要する処理量や処理時間が、非常に多くなっ
てしまうという問題点がある。

このように、領域の頂点を移動して負荷の再配分を行な
うという従来の方法では、再配分に要する処理が非常に
多く、再配分による効果が十分に得られないという問題
点がある。

本発明、負荷の再配分のための領域形状の変更情報を単
純にすることで、領域形状の変更に伴う情報を軽減する
ことができ、再配分の効果を十分に上げることのでき
る、物体画像合成装置を提供することを目的とする。

〔問題点を解決するための手段〕

本発明の物体画像合成装置は、視点から各画素を通る複
数の光線の情報を発生する初期光線発生部と、物体の情
報を設定する物体情報設定部と、それぞれが前記物体の
定義される空間を分割することにより生成される複数の
領域のうち１領域を担当してこの領域を通過する光線と
この担当領域に含まれる物体との交差判定処理を行なう
ことにより前記画素の輝度を計算する複数の輝度計算部
と、この輝度計算部で計算された輝度を画像として記憶
する画像記憶部とで構成されるとともに、前記輝度計算
部に前記物体定義空間を座標軸に垂直な平面で分割して
生成される複数の領域のうちの前記輝度計算部の担当領
域の範囲を記憶する領域情報記憶手段と、前記輝度計算
部の負荷を決定する負荷決定手段と、各座標軸に平行な
方向において前記担当領域と隣接する領域を担当する隣
接輝度計算部と前記輝度計算部との相互通信をそれぞれ
行なう相互通信手段と、前記相互通信手段を介して得ら
れる前記隣接輝度計算部の負荷が最大となる隣接輝度計
算部の担当領域の方向を前記輝度計算部の担当領域の拡
大方向として決定する方向決定手段と、前記負荷が最大
となる隣接輝度計算部の負荷と前記輝度計算部の負荷と
を比較して前記方向決定手段で決定された方向に前記輝
度計算部の担当領域を拡大するかどうかを決定する拡大
決定手段と、前記拡大決定手段の決定に基づき前記方向
決定手段で決定された方向に前記担当領域を拡大すべく
前記領域情報記憶手段に記憶された前記担当領域の範囲
を変更する領域拡大手段とが備えられている。〔作用〕本発明における輝度計算部の負荷の再配分方法について
述べる。各輝度計算部には、物体定義空間を座標軸に垂
直な平面で分割して生成される複数の領域のうちの１領
域が、その輝度計算部の担当領域として割り当てられ
る。この担当領域の範囲は、輝度計算部に備えられた領
域情報記憶手段に記憶される。

ここで、この輝度計算部の担当領域と隣接する領域のう
ちで、各座標軸（ｘ，ｙ，ｚ軸）に平行な方向の領域を
担当する６つの輝度計算部を、隣接輝度計算部とよぶ。

各輝度計算部の負荷は、負荷決定手段によって決定され
て、相互通信手段を介して６つの隣接輝度計算部に転送
される。そして方向決定手段では、相互通信手段を介し
て得られる６つの隣接輝度計算部の負荷のうちで最大の
負荷を選択し、この最大負荷となる隣接輝度計算部の接
続方向を、担当領域の拡大方向として決定する。そして
方向決定手段は、その最大負荷を拡大決定手段に出力
し、決定方向を領域拡大手段に出力する。

次に拡大決定手段は、負荷決定手段によて決定された負
荷と、方向決定手段から出力された隣接輝度計算部の最
大負荷との比較を行う。この比較結果に基づいて、負荷
が最大となる隣接輝度軽算部の担当領域の方向にこの輝
度計算部の担当領域を拡大するかどうかを決定する。

最後に領域拡大手段は、拡大決定手段の決定に従い領域
情報記憶手段に記憶された担当領域の範囲を変更して、
担当領域の拡大を実行する。

このように、担当領域を負荷の比較結果に基づいて拡大
することにより、輝度計算部とその隣接輝度計算部との
間で、負荷の再配分が実行される。

〔実施例〕

第１図（ａ）および（ｂ）は、本発明の一実施例として
の物体画像合成装置を示す構成図であり、第１図（ａ）
は、物体画像合成装置の全体を示す全体構成図、第１図
（ｂ）は、第１図（ａ）に示す輝度計算部の詳細な構成
を示す構成図である。第１図（ａ）に示すように、本実
施例には、予め設定された視点から合成される画像の各
画素を通る複数の光線の情報を発生する初期光線発生部
１が設けられている。

また、表示される物体の情報を設定するための物体情報
設定部２が設けられている。

さらに、物体の定義される空間を分割することにより生
成される複数の領域のうちの１領域を担当して、この領
域を通過する光線と担当領域（領域５と称す）に含まれ
る物体との交差判定処理を行なうことにより、各画素の
輝度を計算する複数の輝度計算部３が設けられている。
この輝度計算部３で計算された輝度を、画像として記憶
する画像記憶部４が設けられている。この画像記憶部４
は、画像の合成を行なう前に、総ての画素の輝度を０に
設定する。

そして、これらの初期光線発生部１と物体情報設定部２
と複数の輝度計算部３と画像記憶部４との間で情報を伝
達するための接続線５が設けられている。この接続線５
を介して、例えばキーボードから情報を入力するための
情報入力部６が設けられている。

第１図（ｂ）に示すように、輝度計算部３には、６方向
に隣接する領域を担当する他の輝度計算部３と、相互に
通信を行なう相互通信手段３１が設けられている。ま
た、接続線５を介して通信を行なう通信手段３２が設け
られている。さらに、輝度計算部３内での情報の伝達を
行なうための接続線１０１が設けられている。

第２図は、画素ｐ（ｉ，ｊ）の輝度Ｉの計算方法を示す
説明図であり、図のように光源Ｌ、物体Ｏ，Ｏ′および
点Ｅが配置されている。第２図に示すように、光線探索
法においては、光源Ｌから画素ｐ（ｉ，ｊ）を通って視
点Ｅに至る光線の経路を逆向きに辿って、画素ｐ（ｉ，
ｊ）の輝度の計算を行なう。ここで、画素ｐ（ｉ，ｊ）
の輝度Ｉを、視点Ｅから画素ｐ（ｉ，ｊ）を通って逆向
きに発生される光線Ｒの輝度と呼ぶことにする。第２図
および以下の説明でＲ，Ｒ′，Ｒ_Ｌ等は光線を示し、は方向を示し、方向は光線Ｒの方向を示すというよう
に対応する。この光線Ｒの輝度Ｉとは、画素ｐ（ｉ，
ｊ）を通って視点Ｅに入射する光の強度Ｉである。光線
Ｒの輝度Ｉは、次式で計算される。（＊は掛け算を示
す）ｒｅｆ：物体Ｏの反射係数ｄｉｆ：物体Ｏの拡散係数Ｉ′ ：′方向からの入射光強度Ｉ_Ｌ：光源Ｌからの入射光強度：物体Ｏの表面の単位法線ベクトル ′ ：方向の正反射方向ベクトルこれらの２つの入射光強度Ｉ′，Ｉ_Ｌを求めるために、
光線Ｒと物体Ｏとの交点ＣＰを始点として方向がとなる２つの光線Ｒ′，Ｒ_Ｌを発生させる。また、輝度
Ｉを求めるためのＩ′，Ｉ_Ｌの係数を、光線Ｒ′，Ｒ_Ｌ
の減衰率Ｇ′，Ｇ_Ｌとして設定する。すなわち、光線Ｒ
が物体Ｏに衝突することにより減衰されて、光線Ｒ′，
Ｒ_Ｌが発生されるのである。これらの減衰率Ｇ′，Ｇ_Ｌ
は、Ｇ：光線Ｒの減衰率（＝１）となる。これらの減衰率Ｇ′，Ｇ_Ｌを用いることによ
り、光線Ｒの輝度Ｉすなわち画素ｐ（ｉ，ｊ）の輝度Ｉ
は、次のように求められる。

Ｉ＝Ｇ′＊Ｉ′＋Ｇ_Ｌ＊Ｉ_Ｌこのように、新たな光線Ｒ′，Ｒ_Ｌが生成されると、光
線Ｒの情報は必要無くなる。

さらに第２図に示すように、光線Ｒ′が物体Ｏ′と交差
した場合は、同様に光線Ｒ″，Ｒ_Ｌ′とが発生される。
これらの減衰率Ｇ″，Ｇ_Ｌ′は、やはり同様に次式で計
算される。

ｒｅｆ′：物体Ｏ′の反射係数ｄｉｆ′：物体Ｏ′の拡散係数 ′：物体Ｏ′の表面の単位法線ベクトルこのように、減衰率Ｇ″，Ｇ_Ｌ′には、減衰率Ｇ′が積
算される。

ただし、光線Ｒ_Ｌの処理は、光線Ｒ，Ｒ′とは異なる。
光線Ｒ_Ｌが物体と交差した場合には、交点ＣＰはその物
体の影となり、光源Ｌの照明光を受けることができな
い。従って、光線Ｒ_Ｌの輝度Ｉ_Ｌは０となる。もし光線
Ｒ_Ｌがどの物体とも交差しない場合には、光線Ｒ_Ｌの輝
度Ｉ_Ｌは光源Ｌの輝度となる。このように、物体へ向か
う光線Ｒ，Ｒ′と光源Ｌへ向かう光線Ｒ_Ｌとは扱いが異
なるので、光線の種類を区別する必要がある。そこで、
光線Ｒに光線の種類を区別するための種類Ｃを設定す
る。この種類Ｃは、光線Ｒが物体に向かう場合には０、
光源に向かう場合には１という値が与えられる。

第２図に示すように、物体へ向かう光線は、物体に衝突
する毎に新たな物体へ向かう光線を発生する。このた
め、１画素ｐの輝度Ｉを計算するために、多くの光線の
処理を行なわなければならない場合が生じる。しかし、
物体と衝突する毎に光線は減衰を受けるので、衝突回数
が多くなると、その光線が輝度Ｉに与える影響はほとん
ど無視できるようになる。

そこで、光線Ｒの衝突回数を制限するために、光線Ｒに
回数Ｔを設定する。この回数Ｔは、光線Ｒの可能な衝突
回数を示すものである。回数Ｔを持つ光線Ｒが物体に衝
突して、物体に向かう光線Ｒ′が発生される場合、光線
Ｒ′の回数Ｔ′は（Ｔ−１）に設定される。もし、回数
Ｔが０の光線Ｒが物体と衝突した場合には、物体に向か
う光線Ｒ′は発生されずに、光源Ｌへ向かう光線Ｒ_Ｌの
みが発生される。

なお、第２図では光源Ｌが１個しか存在しないが、複数
個の光源Ｌ_ｉ（ｉ＝１，２，…）が存在する場合は、す
べての光源Ｌ_ｉへ向かう光線を発生しなければならな
い。ところで、光源へ向かう光線Ｒ_Ｌの場合には、前述
の通り物体と交差しても新たな光線の発生を行わないの
で、光源Ｒ_Ｌの情報としての回数Ｔは意味を持たない。
そこで、複数個の光源Ｌ_ｉが存在する場合には、光線Ｒ
_Ｌの回数Ｔとして、その光線Ｒ_Ｌが向かう光源の番号ｉ
を設定する（計算機の処理上、光線Ｒ，Ｒ′に対する回
数Ｔの設定に相当するように光線Ｒ_Ｌに対する光源の番
号ｉを設定する）。このように光線Ｒ_Ｌに対し回数Ｔの
代わりに光源Ｌ_ｉの番号ｉを設定することにより、複数
個の光源Ｌ_ｉが存在する場合でも、各光線Ｒ_Ｌが向かう
光源Ｌ_ｉの番号ｉが分かるので、正しく処理を行うこと
ができる。

また、ここでは簡単のため物体の表面における反射のみ
を考えた。もし物体の透過も考慮する場合には、物体と
光線Ｒとの交点において、透過方向への光線を発生すれ
ばよい。ただし、この光線の種類は、物体へ向かう光線
であり、上述の光線Ｒ′と同様に処理すれば、正しく物
体の透過を表現できる。

第３図は、光線Ｒを発生した際に設定すべき光線Ｒの情
報を示す説明図である。第３図に示すように光線Ｒを発
生した際には、光線Ｒの情報として、光線Ｒを示す半直
線の始点位置座標（Ｓ_ｘ，Ｓ_ｙ，Ｓ_ｚ）と方向（ｄ_ｘ，
ｄ_ｙ，ｄ_ｚ）とが設定される。また、光線Ｒの輝度が影
響を与える画素ｐ（ｉ，ｊ）の位置（ｉ，ｊ）も、光線
Ｒの情報として設定される。さらに、光線Ｒの持つ減衰
率Ｇと光線Ｒの回数Ｔと光線Ｒの種類Ｃも光線Ｒの情報
として設定される。

第４図は、初期光線発生部１の動作を説明するための説
明図である。第４図に示すように、初期光線発生部１に
おいて、視点Ｅを始点として、画像Ｐを構成する各画素
ｐ（ｉ，ｊ）を通る半直線の延長に、光線Ｒを発生す
る。

そのために、第１図（ａ）の初期光線発生部１には、情
報入力部６により、視点Ｅの位置座標（Ｅ_ｘ，Ｅ_ｙ，Ｅ
_ｚ）が入力される。また、合成される画像Ｐを定義する
情報として、画像Ｐの平面と範囲を示すパラメータが、
情報入力部６から入力される。初期光線発生部１では、
これらのパラメータに基づいて、光線Ｒの情報の発生を
行なう。この光線Ｒを示す半直線を求める方法の一例
は、ティー・ホィッテッド（T.Whitted）著、コミュニ
ケーションオブエーシーエム（Communication of A
CM）、第２３巻、第６号、３４３頁から３４９頁、論文
「アンインプルーブドイルミネーションモデル
フォオシェーディッドディスプレイ（An Improved
Illumination Model for Shaded Display）」に記載さ
れている。

次に、この半直線と物体定義空間との交点のうちで、最
も視点に近い交点の位置座標（Ｓ_ｘ，Ｓ_ｙ，Ｓ_ｚ）を求
める。この位置座標（Ｓ_ｘ，Ｓ_ｙ，Ｓ_ｚ）が、光線Ｒの
始点位置座標（Ｓ_ｘ，Ｓ_ｙ，Ｓ_ｚ）となる。すなわち、
光線Ｒが最初に物体定義空間に入射する位置が、光線Ｒ
の始点となる。また、視点Ｅから画素ｐに向かう方向
が、光線Ｒの方向（ｄ_ｘ，ｄ_ｙ，ｄ_ｚ）となる。さら
に、画素ｐ（ｉ，ｊ）の位置（ｉ，ｊ）が、光線Ｒの画
素位置（ｉ，ｊ）として設定される。

初期光線発生部１では、発生される光線Ｒの減衰率Ｇは
１、すなわちまったく減衰を受けていない状態に設定さ
れる。また、回数Ｔとしては、情報入力部６から初期光
線発生部１に予め設定された定数値が与えられる。さら
に、種類Ｃとしては、物体へ向かう光線を示す０の値が
与えられる。

初期光線発生部１では、このような情報を持つ光線Ｒ
が、画像Ｐのすべての画素ｐ（ｉ，ｊ）に対応して発生
されて、輝度計算部３へ転送される。

第５図は、物体情報設定部２に設定される物体の情報を
示す説明図である。説明を簡単にするために、表示され
る物体を球に限定して説明を行なうが、多面体や自由曲
面などの物体を表示する場合も、ほぼ同様に行なうこと
ができる。

第５図に示すように、情報入力部６から物体の情報が入
力されて、物体情報設定部２に設定される。設定される
物体Ｏ_ｉの情報は、物体Ｏ_ｉを区別するための物体番号
ｎ_ｉ，物体としての球の中心座標（ｘ_ｉ，ｙ_ｉ，ｚ_ｉ）
半径ｒ_ｉ，物体の材質を示す拡散係数ｄｉｆ_ｉ，反射係
数ｒｅｆ_ｉである。さらに、物体Ｏ_ｉの外接領域を示す
情報として、物体を含む最小の直方体の範囲が設定され
る。

第６図は、物体としての球の外接領域を示す説明図であ
る。第６図に示すように、物体Ｏ_ｉの外接領域は、ｘ方
向の範囲（ｘ_ｉ−，ｘ_ｉ＋），ｙ方向の範囲（ｙ_ｉ−，
ｙ_ｉ＋），ｚ方向の範囲（ｚ_ｉ−，ｚ_ｉ＋）で示される
直方体である。これらの値は次式で求められる。

ｘ_ｉ−＝ｘ_ｉ−ｒ_ｉｘ_i+＝ｘ_ｉ＋ｒ_ｉｙ_i-＝ｙ_ｉ−ｒ_ｉｙ_i+＝ｙ_ｉ＋ｒ_ｉｚ_i-＝ｚ_ｉ−ｒ_ｉｚ_i+＝ｚ_ｉ＋ｒ_ｉ第７図は、物体情報設定部２に設定される光源の情報を
示す説明図である。説明を簡単にするために、点光源の
みに限定して説明を行なうが、平行光線やスポットライ
トなどの各種照明光を扱う場合も、ほぼ同様に行なうこ
とができる。情報入力部６から物体の照明としての光源
の情報が入力されて、第７図に示すように物体情報設定
部２に設定される。設定される光源の情報は、点光源Ｌ
_ｉの位置座標（ｘ_ｉ，ｙ_ｉ，ｚ_ｉ），光源の輝度Ｉ_Liで
ある。この輝度Ｉ_Liは、０から１の実数値である。この
輝度Ｉ_Liの値は、光源の明るさを示すものであり、１の
ときが最も明るく、０のときが真っ暗な光源となる。

こうして設定された物体情報と光源情報とは、物体情報
設定部２から接続線５を介して輝度計算部３に伝達され
る。

第８図は、複数の輝度計算部３を３次元配列状に結合す
る方法を示す説明図である。第８図に示すように、輝度
計算部３は、輝度計算部３内に設けられた相互通信手段
３１を介して、３次元配列状に結合されている。すなわ
ち、各輝度計算部３はそれぞれｘ，ｙ，ｚ方向の両側の
輝度計算部３と接続されており、それらの輝度計算部３
と相互に情報を伝達することができる。ここで、ｘ，
ｙ，ｚ方向のａ，ｂ，ｃ番目の輝度計算部３を（ａ，
ｂ，ｃ）輝度計算部３と呼ぶことにすると、（ａ，ｂ，
ｃ）輝度計算部３は、（ａ−１，ｂ，ｃ），（ａ＋１，
ｂ，ｃ），（ａ，ｂ−１，ｃ），（ａ，ｂ＋１，ｃ），
（ａ，ｂ，ｃ−１），（ａ，ｂ，ｃ＋１）輝度計算部３
と接続されている。

また、輝度計算部３は図中のｘ，ｙ，ｚ方向にそれぞれ
Ａ，Ｂ，Ｃ個ずつ並んでおり、全部の輝度計算部３の個
数Ｄは、Ｄ＝Ａ＊Ｂ＊Ｃとなる。

第９図は、物体を定義する空間を、各輝度計算部３に割
り当てられる担当領域Ｓに分割する方法を示す説明図で
ある。第９図に示すように、ｘ，ｙ，ｚ座標軸のうちの
１軸にそれぞれ垂直な平面により、物体定義空間を複数
の直方形状の領域に分割する。この場合に、ｘ方向の領
域数がＡ個、ｙ方向の領域数がＢ個、ｚ方向の領域数が
Ｃ個となるように、分割を行なう。そして、（ａ，ｂ，
ｃ）輝度計算部３に、ｘ方向のａ番め、ｙ方向のｂ番
め、ｚ方向のｃ番の領域を割り当てる。これにより、分
割されたすべての領域をそれぞれ１個の輝度計算部３に
割り当てることができる。

また、このような割り当てを行なうことにより、相互通
信手段３１を介して接続された輝度計算部３は、それぞ
れ隣接する領域を担当することになる。

第１０図，１１図は、輝度計算部３の担当領域Ｓを示す
領域情報の内容を示す説明図である。第１０図に示すよ
うに、輝度計算部３に設けられた領域情報記憶手段３３
には、その輝度計算部３の担当領域Ｓを示す領域情報が
記憶される。この領域情報としては、ｘ，ｙ，ｚ方向の
何番めかを示す（ａ，ｂ，ｃ）の値と、第１１図に示す
ような担当領域Ｓのｘ，ｙ，ｚ方向の範囲（ｘ₋，
ｘ_＋），（ｙ₋，ｙ_＋），（ｚ₋，ｚ_＋）とが記憶され
る。

さらに、３次元配列の外周に存在する輝度計算部３にお
いては、相互通信手段３１により輝度計算部３が接続さ
れていない場合がある。そこで、相互通信手段３１によ
り接続されている各方向に、実際に輝度計算部３が接続
されているかいないかが、有無の情報として、領域情報
記憶手段３３に記憶される。

これらの領域情報は、情報入力手段６から入力されて、
各輝度計算部３に伝達される。

第１２図は、初期光線発生部１から輝度計算部３への光
線Ｒの情報の転送処理を示す説明図である。初期光線発
生部１で発生されたすべての光線Ｒの情報は、接続線５
を介してすべての輝度計算部３へ一斉に転送される。そ
して、第１２図に示すように、各輝度計算部３に設けら
れた光線情報判定手段３７には、初期光線発生部１から
転送された光線Ｒの情報が、通信手段３２を介して入力
される。同時に、領域情報記憶部３３に記憶された担当
領域Ｓの情報が、この光線情報判定手段３７によって読
み出される。入力された光線Ｒの始点位置座標（Ｓ_ｘ，
Ｓ_ｙ，Ｓ_ｚ）は、光線Ｒが最初に物体定義空間に入射す
る位置に設定されている。このため、もしこの始点位置
座標（Ｓ_ｘ，Ｓ_ｙ，Ｓ_ｚ）が担当領域Ｓに含まれていれ
ば、光線Ｒは担当領域Ｓを最初に通過することになる。

そこで、光線情報判定手段３７では、光線Ｒの始点位置
座標（Ｓ_ｘ，Ｓ_ｙ，Ｓ_ｚ）と担当領域Ｓの範囲（ｘ₋，
ｘ_＋），（ｙ₋，ｙ_＋），（ｚ₋），Ｚ_＋）とが、比較
される。

ｘ₋≦Ｓ_ｘ＜ｘ_＋ｙ₋≦Ｓ_ｙ＜ｙ_＋ｚ₋≦Ｓ_ｚ＜ｚ_＋という３条件式のすべてが満される場合、始点位置座標
（Ｓ_ｘ，Ｓ_ｙ，Ｓ_ｚ）は担当領域Ｓに含まれており、光
線Ｒは担当領域Ｓを最初に通過することになる。この場
合、光線情報判定手段３７から光線Ｒの情報が光線情報
記憶手段３４に転送されて、記憶される。

また、これらの条件式のうちのどれかが成り立たない場
合、光線Ｒは他の担当領域Ｓ′に最初に入射しているこ
とになる。従って、光線Ｒの情報はこの輝度計算部３に
は記憶されない。

以上の処理により、初期光線発生部１で発生された光線
Ｒの情報は、最初に入射する領域を担当する輝度計算部
３の、光線情報記憶手段３４に記憶される。

第１３図は、輝度計算部３に設けられた物体情報記憶手
段３５と光源情報記憶手段３６に、物体情報設定部２か
ら、物体情報と光源情報とを記憶させる情報を示す説明
図である。物体情報設定部２に記憶されたすべての物体
情報と光源情報は、接続線５を介してすべての輝度計算
部３へ一斉に転送される。そして、第１３図に示すよう
に、輝度計算部３に設けられた光源情報記憶手段３６
は、通信手段３２を介して転送された光源情報をすべて
記憶する。そして、輝度計算部３に設けられた物体情報
記憶手段３５は、通信手段３２を介して転送された物体
情報をすべて記憶する。

第１４図は、輝度計算部３の担当領域Ｓの拡大処理を示
す説明図である。この担当領域Ｓの拡大処理は、特定の
座標軸に垂直な担当領域Ｓの境界面を、座標軸に平行な
方向に移動することで行われる。

第１４図に示すように、輝度計算部３に設けられた負荷
決定手段４３は、光線情報記憶手段３７に記憶された光
線Ｒの個数を、その輝度計算部３の負荷Ｆとして求め
る。なお、ここでは説明を簡単にするためにこのような
負荷決定方法としたが、この他にも様々な負荷の決定方
法が可能である。これ以外の方法を取った場合でも、ほ
ぼ同様に処理を行うことができる。例えば、負荷決定手
段４３において各輝度計算部３が実際に処理を行ってい
る時間と、光線Ｒの情報を待っている時間とを計測し
て、これらの値から各輝度計算部３の負荷を決定しても
良い。

こうして負荷決定手段４３で決定された負荷Ｆは、相互
通信手段３１を介して、輝度計算部３のｘ₋，ｘ_＋，ｙ
₋，ｙ_＋，ｚ₋，ｚ_＋方向に接続された輝度計算部３
（ｘ₋），（ｘ_＋），（ｙ₋），（ｙ_＋），（ｚ₋），
（ｚ_＋）にそれぞれ伝達される。（ｘ₋方向に接続され
た輝度計算部３を輝度計算部３（ｘ₋）と記し、他の方
向においても同様に記す）。そして、方向決定手段４４
は、輝度計算部３（ｘ₋），（ｘ_＋），（ｙ₋），（ｙ
_＋），（ｚ₋），（ｚ_＋）から相互通信手段３１を介し
て伝達される負荷Ｆ（ｘ₋），Ｆ（ｘ_＋），Ｆ
（ｙ₋），Ｆ（ｙ_＋），Ｆ（ｚ₋），Ｆ（ｚ_＋）の内で
（輝度計算部３（ｘ₋）の負荷をＦ（ｘ₋）と記し、他
の方向に接続する輝度計算部３の負荷も同様に記す）、
で最大となるものを１つだけ選択する。そして、その方
向を示す値Ｄを出力する。この値Ｄは１から６までの整
数であり、１から順にそれぞれｘ₋，ｘ_＋，ｙ₋，
ｙ_＋，ｚ₋，ｚ_＋方向を示している。こうして方向決定
手段４４で決定した方向を示す値Ｄを、担当領域Ｓの拡
大方向として領域拡大手段４６に出力する。同時に、方
向決定手段４４で求めた負荷の最大値Ｆ_maxを、拡大決
定手段４５に出力する。

そして拡大決定手段４５は、各隣接輝度計算部３の負荷
の最大値Ｆ_maxと輝度計算部３の負荷Ｆとの比較によ
り、次に示す結果ｄＦを出力し、担当領域Ｓを拡大する
かどうかを次のように決定する。

Ｆ_max−Ｆ＞ＴＨのときｄＦ＝１それ以外のときｄＦ＝０ＴＨ：予め情報入力部６を通じて設定された正のしきい
値この結果ｄＦが１のときには、担当領域Ｓを値Ｄによっ
て示される方向に拡大する。また、この結果ｄＦが０の
ときには、担当領域Ｓの拡大は行わない。

こうして決定された担当領域Ｓの結果ｄＦを受けて、こ
の値が１の場合に領域拡大手段４６では担当領域Ｓの範
囲を拡大する。この領域拡大手段４６は、方向決定手段
４４で決定された拡大方向を示す値Ｄに従って、まず領
域情報記憶手段３３から、担当領域Ｓの値Ｄで示される
方向の範囲ａを読み出して記憶する。例えば、値Ｄが１
の場合には範囲ａとして第１０図に示す範囲ｘ₋を読み
出し、２の場合にはｘ_＋を読み出す。次に、以下に示す
ように新たな範囲ａを求める。

Ｄ＝１，３，５のときａ′＝ａ−ｄＳＤ＝２，４，６のときａ′＝ａ＋ｄＳｄＳ：予め情報入力部６を通じて設定された正の拡大量このように求められた範囲ａ′を領域情報記憶手段３３
の対応する方向の範囲を記憶する部分に書き込んで、担
当領域Ｓの範囲を拡大する。

このような担当領域Ｓの拡大処理を行なうことにより、
各担当領域Ｓに含まれている物体の数や通過する光線の
数を増加させることができ、各輝度計算部３の計算量を
増加させることができる。同時に、値Ｄで示される方向
に隣接する領域を担当する隣接輝度計算部３の負荷を減
少させることができる。従って、全体の計算量を平均化
して適切な負荷の再配分を図ることができる。

第１５図（ａ）、（ｂ）は、輝度計算部３間の光線Ｒの
情報の転送方向を示す説明図である。第１５図（ｂ）に
示す輝度計算部３ａ〜３ｅそれぞれの担当領域が第１５
図（ａ）に示す担当領域Ｓａ〜Ｓｅであり、担当領域Ｓ
ａ、Ｓｂ、Ｓｄは拡大処理がなされている。第１５図
（ａ）に示すように、担当領域Ｓの変更により、領域の
境界面の重なりが生じる。また、第１５図（ｂ）に示す
ように、相互通信手段を介した輝度計算部３間の接続は
固定されいる。従って、第１５図（ａ）、（ｂ）に示す
ような場合、担当領域Ｓａから担当領域Ｓｂに入射する
光線Ｒの情報を、輝度計算部３ａから相互通信手段３１
を介して、直接に輝度計算部３ｂへ転送することはでき
ない。

そこで、このような光線Ｒの情報は、ままず輝度計算部
３ａから、相互通信手段３１を介して、輝度計算部３ｅ
に転送される。この転送された光線Ｒの情報は、いった
ん輝度計算部３ｅの光線情報記憶手段３４に記憶され、
次に輝度計算部３ｃに転送される。

このような転送処理を行うために、各輝度計算部３の光
線情報記憶手段３４に記憶された光線Ｒの情報は、まず
光線情報判定手段３７に読み出される。この光線情報判
定手段３７は、光線Ｒの始点位置座標（Ｓ_ｘ，Ｓ_ｙ，Ｓ
_ｚ）と、領域情報記憶手段３３から読み出した担当領域
Ｓの範囲（ｘ₋，ｘ_＋），（ｙ₋，ｙ_＋），（ｚ₋，ｚ
_＋）とを比較して、次のような処理を行う。ただし、光
線Ｒの始点位置座標（Ｓ_ｘ，Ｓ_ｙ，Ｓ_ｚ）は後述する交
差判定処理により、光線Ｒと担当領域Ｓの境界面との交
点に更新されている。

Ｓ_ｘ＜ｘ₋のとき相互通信手段３１を介して、光線Ｒの情報をｘ₋方向に
接続された輝度計算部３へ転送しての終了へ。

Ｓ_ｘ≧ｘ_＋のとき相互通信手段３１を介して、光線Ｒの情報をｘ_＋方向に
接続された輝度計算部３へ転送してへ。

Ｓ_ｙ＜ｙ₋のとき相互通信手段３１を介して、光線Ｒの情報をｙ₋方向に
接続された輝度計算部３へ転送してへ。

Ｓ_ｙ≧ｙ_＋のとき相互通信手段３１を介して、光線Ｒの情報をｙ_＋方向に
接続された輝度計算部３へ転送してへ。

Ｓ_ｚ＜ｚ₋ 相互通信手段３１を介して、光線Ｒの情報をｚ₋方向に
接続された輝度計算部３へ転送してへ。

Ｓ_ｚ≧ｚ_＋のとき相互通信手段３１を介して、光線Ｒの情報をｚ_＋方向に
接続された輝度計算部３へ転送してへ。

終了このように光線Ｒの情報を輝度計算部３間で転送すれ
ば、正しい輝度計算部３で光線Ｒの情報を処理すること
ができる。

第１６図は、輝度計算部３における光線と物体との交差
判定処理による各画素の輝度計算方法を示す説明図であ
る。第１６図に示すように、光線情報記憶手段３４に記
憶された光線Ｒの情報は、まず光線情報判定手段３７に
読み出される。この光線情報判定手段３７における判定
処理の結果、隣接する輝度計算部３へ転送されなかった
光線Ｒの情報は、交差判定手段３９へ送られる。この交
差判定手段３９は、担当領域Ｓに含まれる物体と光線Ｒ
との交差判定処理を行なう。

そのために物体情報判定手段３８は、領域情報記憶手段
３３から担当領域Ｓの範囲（ｘ₋，ｘ_＋），（ｙ₋，ｙ
_＋），（ｚ₋，ｚ_＋）と各物体Ｏ_ｉの外接領域の範囲
（ｘ_i-，ｘ_i+），（ｙ_i-，ｙ_i+），（ｚ_i-，ｚ_i+）との
比較処理を行い、各物体Ｏ_ｉが担当領域Ｓに含まれるか
どうかの判定処理を行う。

第１７図（ａ），（ｂ）は、輝度計算部３の担当領域Ｓ
と、物体情報の外接領域との比較処理を示す説明図であ
る。第１７図（ａ），（ｂ）に示すように、担当領域Ｓ
と外接領域とが共通部分を持たない場合には、以下の条
件式のうちの少なくとも１つが成立する。

ｘ₋≧ｘ_i+ ｘ_＋≦ｘ_i- ｙ₋≧ｙ_i+ ｙ_＋≦ｙ_i- ｚ₋≧ｚ_i+ ｚ_＋≦ｚ_i- そこで、物体情報判定手段３８では、これらの条件式が
評価されて、担当領域Ｓと外接領域とが共通部分を持つ
かどうかが求められる。その結果、共通部分を持つ場合
には、担当領域Ｓ内に物体Ｏ_ｉが含まれていると判定さ
れて、交差判定手段３９に、物体Ｏ_ｉの情報が転送され
る。共通部分を持たない場合には、転送されない。

以上の処理により、物体情報記憶手段３５に記憶された
物体情報のうちで、担当領域Ｓ内に含まれる物体情報の
みが、物体情報判定手段３８から交差判定手段３９に転
送される。そして交差判定手段３９は、物体情報判定手
段３８から転送された物体Ｏ_ｉと光線Ｒとの交差判定処
理を行う。

その結果、物体と交差しない光線Ｒについては、まず担
当領域Ｓの境界面と光線Ｒとの交点が求められる。この
交点により、光線Ｒが次に入射する隣接する領域Ｓ′が
求められ、光線Ｒの情報を転送すべき方向が決定され
る。光線Ｒの情報は、相互通信手段３１を介して決定さ
れた方向の輝度計算部３へ転送される。

その際に、光線Ｒの始点位置座標は、求められた交点の
位置座標に変更される。これにより、光線Ｒの始点位置
座標は、次に入射すべき領域に含まれることになる。

こうして転送された光線Ｒの情報は、相互通信手段３１
から読み出されて、光線情報記憶手段３４に記憶され
る。

ままた、光線Ｒが物体と交差していて、光線Ｒから新た
な光線Ｒ′や光線RLが発生された場合には、これらの光
線Ｒ′と光線RLの情報が、光線情報記憶手段３４に記憶
される。

このような交差判定処理については、前述の各論文およ
び第２図に示されている。

この処理により、光線Ｒの輝度Ｉが決定された場合に
は、通信手段３２を介して、光線Ｒの情報が示す画像記
憶部４の画素ｐ（ｉ，ｊ）に、その輝度Ｉが加算され
る。

上述の交差判定処理によって、各輝度計算部３の光線情
報記憶手段３４に記憶された光線Ｒの情報を総て処理し
た時点で、画像Ｐの合成が完了する。

〔発明の効果〕

本発明の物体画像合成装置では、各輝度計算部の担当領
域の形状は直方体であり、その直方体の各面は、座標軸
に垂直である。このため、担当領域の境界面と光線との
交差判定が、非常に容易である。従って、光線が担当領
域を通過する場合に、従来と比べてはるかに少ない処理
量で、この光線の情報を転送すべべき領域を決定するこ
とができる。

また、担当領域の形状の変更は、各座標軸に垂直な境界
面を、その座標軸に平行な方向に移動することで実行さ
れる。このため、担当領域の形状が変更されても、担当
領域は直方体に保たれるので、上述の効果は損なわれな
い。

このように、担当領域の形状を変更する際の処理量が少
ないので、担当領域の形状の変更による、各輝度計算部
の負荷の再配分の効果を、十分に得ることができる。

【図面の簡単な説明】

第１図（ａ）および（ｂ）はそれぞれ本発明の一実施例
の物体画像合成装置の全体を示す構成ブロック図および
輝度計算部の詳細な構成を示す構成ブロック図、第２図
は画素ｐ（ｉ，ｊ）の輝度Ｉの計算方法を示す説明図、
第３図は光線Ｒを発生した際に設定すべき光線Ｒの情報
を示す図、第４図は初期光線発生部１の動作を説明する
ための説明図、第５図は物体情報設定部２に設定される
物体の情報を示す図、第６図は物体としての球の外接領
域を示す説明図、第７図は物体情報設定部２に設定され
る光源の情報を示す図、第８図は複数の輝度計算部３を
３次元配列状に結合する方法を示す説明図、第９図は物
体を定義する空間を各輝度計算部３に割り当てられる担
当領域Ｓに分割する方法を示す図、第１０図および第１
１図はそれぞれ輝度計算部３の担当領域Ｓを示す領域情
報の図および立体的に示す説明図、第１２図は初期光線
発生部１から輝度計算部３への光線Ｒの情報の転送処理
を示すブロック図、第１３図は輝度計算部３に設けられ
た物体情報記憶手段３５と光源情報記憶手段３６に物体
情報設定部２から物体情報と光源情報とを記憶させる処
理を示すブロック図、第１４図は輝度計算部３の担当領
域Ｓの拡大処理を示すブロック図、第１５図（ａ）およ
び（ｂ）は、輝度計算部３間の光線Ｒの情報の転送方法
を示す説明図、第１６は輝度計算部３における光線と物
体との交差判定処理による各画素の輝度計算方法を示す
ブロック図、第１７図（ａ）および（ｂ）は輝度計算部
３の担当領域Ｓと物体情報の外接領域との比較処理を示
す説明図で、それぞれ担当領域Ｓと外接領域とが共通部
分を持つ場合と持たない場合である。１……初期光線発生部、２……物体情報設定部、３，３
ａ，３ｂ，３ｃ，３ｄ……輝度計算部、４……画像記憶
部、５……接続線、６……情報入力部、３１……相互通
信手段、３２……通信手段、３３……領域情報記憶手
段、３４……光線情報記憶手段、３５……物体情報記憶
手段、３６……光源情報記憶手段、３７……光線情報判
定手段、３８……物体情報判定手段、３９……交差判定
手段、４３……負荷決定手段、４４……方向決定手段、
４５……拡大決定手段、４６……領域拡大手段。

Claims

【特許請求の範囲】

【請求項１】光源から視点に至る光線の経路を逆向きに
辿って、物体と光線との交差判定処理を行い、前記物体
を表示すべき画像を構成する各画素の輝度を計算する光
線追跡法に基づく物体画像合成装置において、前記視点から前記各画素を通る複数の光線の情報を発生
する初期光線発生部と、前記物体の情報を設定する物体情報設定部と、それぞれが前記物体の定義される空間を座標軸に垂直な
平面で分割して生成される複数の領域のうちの１領域を
担当し、その担当領域を通過する光線と前記担当領域に
含まれる前記物体との交差判定処理を行うことにより前
記画素の輝度を計算する複数の輝度計算部と、この輝度計算部で計算された輝度を前記画素として記憶
する画素記憶部とを含み、前記輝度計算部それぞれに、前記担当領域の範囲を記憶
する領域情報記憶手段と、それぞれの負荷を決定する負
荷決定手段と、前記座標軸それぞれに平行な方向におい
て前記担当領域と隣接する前記領域を担当する前記輝度
計算部である隣接輝度計算部との相互通信を行う相互通
信手段と、この相互通信手段を介して得られる前記隣接
輝度計算部のうち負荷が最大となるものが担当する前記
領域の方向を前記担当領域の拡大方向として決定する方
向決定手段と、前記負荷が最大となる隣接輝度計算部の
負荷から前記輝度計算部の負荷を減算した結果が予め定
められた閾値よりも大きい場合に前記方向決定手段で決
定された方向に前記担当領域を拡大すると決定する拡大
決定手段と、この拡大決定手段の決定に基づき前記方向
決定手段で決定された方向に前記担当領域を拡大すべく
前記領域情報記憶手段に記憶された前記担当領域の範囲
を変更する領域拡大手段とが備えられていることを特徴
とする物体画像合成装置。