JPH0575150B2 - - Google Patents

Description

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

〔従来の技術〕

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

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

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

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

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

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

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

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

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

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

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

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

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

〔作用〕

本発明における輝度計算部の負荷の再配分方法
について述べる。各輝度計算部には、物体定義空
間を座標軸に垂直な平面で分割して生成される複
数の領域のうちの１領域が、その輝度計算部の担
当領域として割り当てられる。この担当領域の範
囲は、輝度計算部に備えられた領域情報記憶手段
に記憶される。

ここで、この輝度計算部の担当領域と隣接する
領域を担当する輝度計算部を隣接輝度計算部と呼
ぶ。

各輝度計算部の負荷は、負荷決定手段によつて
決定されて、相互通信手段を介して、各隣接輝度
計算部に転送される。これらを受けた輝度計算部
に設けられている拡大決定手段では、負荷決定手
段で決定された負荷と、相互通信手段を介して得
られる各隣接輝度計算部の負荷とがそれぞれ比較
される。そして拡大決定手段は、これらの比較結
果に基づいて、各輝度計算部の負荷が平滑される
ように、各隣接輝度計算部の担当領域の方向にこ
の輝度計算部の領域を拡大するかどうかをそれぞ
れ決定する。

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

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

〔実施例〕

以下、図面により本発明の一実施例としての物
体画像合成装置について説明する。説明を簡単に
するために、特定の座標軸に平行な方向に隣接す
る輝度計算部間における負荷の再配分処理に限定
して説明を行うが、一般性を損なうものではな
い。

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

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

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

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

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

Ｉ＝G′〓I′＋G_L〓I_L このように、新たな光線R′，R_Lが生成される
と、光線Ｒの情報は必要無くなる。

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

G″＝G′〓ref′ G_L′＝G′〓dif′〓（Ｎ→′，R_L′） ref′：物体O′の反射係数 dif′：物体Ｏの拡散係数 Ｎ→′：物体Ｏの表面の単位法線ベクトル R_L′：光源Ｌの方向ベクトル このように、減衰率G″，G_L′には、減衰率G′が
積算される。

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

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

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

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

このように光線R_Lに対し回数Ｔの代わりに光
源L_iの番号ｉを設定することにより、複数個の光
源L_iが存在する場合でも、各光線R_Lが向かう光源
L_iの番号ｉが分かるので、正しく処理を行うこと
ができる。

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

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

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

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

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

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

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

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

第５図に示すように、情報入力部６から物体の
情報が入力されて、物体情報設定部２に設定され
る。設定される物体O_iの情報は、物体O_iを区別す
るための物体番号n_i、物体としての球の中心座標
（x_i，y_i，z_i）半径r_i、物体の材質を示す拡散係数
dif_i、反射係数ref_iである。さらに、物体O_iの外接
領域を示す情報として、物体を含む最小の直方体
の範囲が設定される。

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

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

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

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

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

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

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

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

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

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

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

そこで、光線情報判定手段３７では、光線Ｒの
始点位置座標（S_x，S_y，S_z）と担当領域Ｓの範囲
（x_-，x₊），（y_-，y₊），（z_-，z₊）とが、比較され
る。

x_-≦S_x＜x₊ y_-≦S_y＜y₊ z_-≦S_z＜z₊ という３条件式のすべてが満される場合、始点位
置座標（S_x，S_y，S_z）は担当領域Ｓに含まれてお
り、光線Ｒは担当領域Ｓを最初に通過することに
なる。この場合、光線情報判定手段３７から光線
Ｒの情報が光線情報記憶手段３４に転送されて、
記憶される。

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

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

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

また、輝度計算部３に設けられた物体情報設定
手段３８は、まず通信手段３２を介して転送され
る物体情報を受け取る。次に、領域情報記憶手段
３３から、輝度計算部３の担当領域Ｓの範囲を読
み出す。この担当領域Ｓの範囲（x_-，x₊），（y_-，
y₊），（z_-，z₊）と物体情報の外接領域の範囲
（x_i-，x_i+），（y_i-，y_i+），（z_i-，z_i+）とが、比較
さ
れる。

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

x_-≧x_i+ x₊≦x_i- y_-≧y_i+ y₊≦y_i- z_-≧z_i+ z₊≦z_i- そこで、物体情報判定手段３８では、これらの
条件式が評価されて、担当領域Ｓと外接領域とが
共通部分を持つかどうかが求められる。その結
果、共通部分を持つ場合には、担当領域Ｓ内に物
体O_iが含まれていると判定されて、物体情報記憶
手段３５に、物体O_iの情報がすべて記憶される。
共通部分を持たない場合には、記憶されない。

以上の処理により、物体情報設定部２に記憶さ
れた物体情報のうちで、担当領域Ｓ内に含まれる
物体情報のみが、輝度計算部３に設けられた物体
情報記憶手段３５に記憶される。

第１５図は、輝度計算部３の担当領域Ｓの拡大
処理を示す説明図である。この担当領域Ｓの拡大
領域処理は、特定の座標軸に垂直な担当領域Ｓの
境界面を、この特定の座標軸に平行な方向に移動
することで行われる。この特定の座標軸は、情報
入力部６から入力される情報で決定される。ここ
では、ｚ座標軸を特定の座標軸とした場合につい
て説明を行うが、一般性を損なうものではない。

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

こうして負荷決定手段４３で決定された負荷Ｆ
は、相互通信手段３１を介して、輝度計算部３の
z₊方向に接続された輝度計算部３（以下、これを
輝度計算部３（z₊）と称す）と、z_-方向に接続さ
れた輝度計算部３（以下、これを輝度計算部３
（z_-）と称す）とに伝達される。そして、拡大決
定手段４４は、輝度計算部３（z_-），（ｚ（₊）から
相互通信手段３１を介して伝達される負荷Ｆ
（z_-），Ｆ（ｚ（₊）（輝度計算部３（z_-）の負荷をＦ
（z_-）、輝度計算部３（z₊）の負荷をＦ（z₊と記す）
と、負荷決定手段４３で決定された負荷Ｆとの比
較をそれぞれ行なう。この拡大決定手段４４は、
負荷の比較により担当領域Ｓを拡大するかどうか
を次のように決定して、その結果dF_-，dF₊を出
力する。

Ｆ（z_-）−Ｆ＞THのとき dF_-＝ １ Ｆ−Ｆ（z_-）＞THのとき dF_-＝−１ それ以外のとき dF_-＝ ０ Ｆ（z₊）−Ｆ＞THのとき dF₊＝ １ Ｆ−Ｆ（z₊）＞THのとき dF₊＝−１ それ以外のとき dF₊＝ ０ TH：予め情報入力部６を通じて設定さ れた正のしきい値 この結果dF_-が１のときには、担当領域Ｓをz_-
方向に拡大する。また、この結果dF_-が−１のと
きには、担当領域Ｓの拡大は行わないが、z_-方向
に接続された輝度計算部３の担当領域が拡大され
ることを示している。

同様に、dF₊が１のときには、担当領域Ｓをz₊
方向に拡大する。また、この結果dF₊が−１のと
きには、担当領域Ｓの拡大は行わないが、z₊方向
に接続された輝度計算部３の担当領域が拡大され
ることを示している。

こうして決定された担当領域Ｓの拡大方向
dF_-，dF₊を受けて、これらの値が１の場合に、
領域拡大手段４５では担当領域Ｓの範囲が拡大さ
れる。この領域拡大手段４５は、まず領域情報記
憶手段３３から、担当領域Ｓのｚ方向の範囲
（z_-，z₊）を読み出して記憶する。次に、以下に
示すように新たな範囲（z′_-，z′₊）を求める。

dF_-＝１のとき、z′_-＝z_-−dS dF₊＝１のとき、z′₊＝z₊＋dS dS：予め情報入力部６を通じて設定 された正の拡大量 このように求められた範囲（z′_-，z′₊）を、領
域情報記憶手段３３に書き込んで、担当領域Ｓの
範囲を拡大する。

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

こうして担当領域Ｓが拡大された場合、拡大さ
れた領域に含まれる物体の情報を隣接する輝度計
算部３から受け取り、物体情報記録手段３５に付
け加えなければならない。

そのために、dF_-が−１の場合、領域拡大手段
４５はdF_-の値を制御情報として物体情報記憶手
段３５に出力する。これを受けた物体情報記憶手
段３５は、各物体O_iの情報を、相互通信３１を介
して、輝度計算部３（z_-）へ転送する。

また、dF_-が１の場合には、領域拡大手段４５
はdF_-の値を物体情報判定手段３８に出力する。
これを受けた物体情報判定手段３８は、拡大され
た担当領域Ｓの範囲を、領域情報記憶手段３３か
ら読み出す。さらに、相互通信手段３１を介し
て、輝度計算部３（z_-）から転送された物体O_j
の情報を読み出す。そして、この物体O_jの外接
領域と担当領域Ｓとが共通部分を持つかどうかの
判定処理を行う。この際の判定処理は、第１４図
で既に示した通りの方法で行なう。この判定処理
の結果、物体O_jの外接領域と担当領域Ｓとが共
通部分を持つ場合には、物体O_jが担当領域Ｓに
含まれると判断して、この物体O_jの情報を物体
情報記憶手段３５に記憶させる。

ただし、この物体O_jと同じ物体の情報が、既
に物体情報記憶手段３５に記憶されている場合が
ある。そこで、重複して物体O_jの情報を記憶さ
せることを避けるために、この物体O_jの物体番
号n_jと、物体情報記憶手段３５に記憶された物体
O_iの物体番号n_iとを比較する。この比較結果によ
り、もし物体O_jと同じ物体O_iが記憶されていない
場合に物体O_jの情報を物体情報記憶手段３５に
記憶させる。

さらにdF₊についても同様の処理を行つて、物
体情報の変更を行う。

以上の処理により、担当領域Ｓが拡大された場
合に、物体情報記憶手段３５に記憶された物体情
報の追加を行なう。

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

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

こうして光線情報記憶手段３４に記憶された光
線Ｒの情報は、まず光線情報判定手段３７に読み
出される。この光線情報判定手段３７は、光線Ｒ
の始点位置座標のｚ座標値S_zと、領域情報記憶手
段３３から読み出した担当領域Ｓのｚ方向の範囲
（z_-，z₊）とを比較する。もし、 S_z≧z₊ の場合は、相互通信手段３１を介して、光線Ｒの
情報を、z₊方向に接続された輝度計算部３ｄへ転
送する。また、 S_z＜z_- の場合は、相互通信手段３１を介して、光線Ｒの
情報を、z_-方向に接続された輝度計算部３ｂへ転
送する。

すなわち、担当領域Ｓのｚ方向の範囲（z_-，
z₊）のみが変更されるのであるから、光線Ｒの情
報をｚ方向に接続された輝度計算部３に転送すれ
ば、ただしい輝度計算部３で、光線Ｒの情報を処
理することができる。

第１７図は、輝度計算部３における光線と物体
との交差判定処理による各画素の輝度計算方法を
示す説明図である。第１７図に示すように、光線
情報記憶手段３４に記憶された光線Ｒの情報は、
まず光線情報判定手段３７に読み出される。この
光線情報判定手段３７における判定処理の結果、
輝度計算部３（z_-）または輝度計算部３（z₊）へ
転送されなかつた光線Ｒの情報は、交差判定手段
３９へ送られる。この交差判定手段３９は、光線
Ｒと物体情報記憶手段３５に記憶された物体との
交差判定処理を行なう。

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

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

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

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

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

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

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

なお、ここではｚ方向に隣接する輝度計算部３
間でのみ負荷の再配分処理を行うものとして説明
した。もし、ｘ，ｙ方向に隣接する輝度計算部３
間でも負荷の再配分処理を行う場合も、同様の処
理で負荷の再配分を実行できる。

また、各輝度計算部３の物体情報記憶手段３５
に全物体の情報を記憶しておいて、担当領域内に
含まれる物体のみを選択して交差判定処理を行つ
ても良い。こうすることにより、負荷の再配分処
理の際に輝度計算部３間で物体の情報を転送する
必要が無くなる。

〔発明の効果〕

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

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

さらに、担当領域の形状が変更された際に、こ
の担当領域に含まれる物体の情報を、変更しなけ
ればならない。この場合でも、担当領域が直方体
に保たれるので、容易に物体の情報を変更するこ
とができる。

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

【図面の簡単な説明】

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

Claims (1)

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