JPS63167986A - 物体画像合成装置 - Google Patents

Abstract

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

Description

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

〔従来の技術〕

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

このような光線探索法による画像生成を高速に行なうた
めに、物体の定義されている空間を複数の領域に分割し
て、各領域をそれぞれ１台のコンピュータに割り当てて
、各コンピュータが割り当てられた領域を通過する光線
の処理を行なう方法が提案されている。この方法の詳細
は、コンピュータ　グラフィックス（Ｃｏｒａｐｕｔｅ
ｒ　Ｇｒａｐｈｉｃｓ　＞、第１８巻、第３号、マーク
・デイッペ（Ｍａｒｋ　Ｄｉ−ｐｐｅ　）　、ジョン゛
スウエンセン（Ｊｏｈｎ　Ｓｗｅｎｓｅｎ　）著、論文
「アン　アダプティブ　サブデイヴイジョン　アルゴリ
ズム　アンド　パラレル　アーキテクチャ　フォア　リ
アリスティック　イメージシンセシス（Ａｎ　Ａｄａｐ
ｔｉｖｅ　５ｕｂｄｉｖｉｓｉｏｎ＾Ｉｇｏｒｉｔｂｍ
ａｎｄ　Ｐａｒａｌｌｅｌ＾ｒｃｈｉｔｅｃｔｕｒｅ　
ｆｏｒ　Ｒｅａｌｉｓｔｉｃ　Ｉｍ−ａｇ６５ｙｏＬｂ
ｅｓｉｓ）１に記載されている。

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

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

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

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

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

第一に、分割された領域から隣接する領域へ光線の情報
を伝達する場合、領域の境界面と光線との交差判定によ
り、転送すべき領域を決定する。

しかし、領域の各境界面の向きや形状が任意なので、こ
の交差判定処理の処理量が非常に多くなってしまう。こ
のため、全体の処理時間も遅くなってしまうという問題
点がある。

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

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

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

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

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

〔作用〕

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

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

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

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

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

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

〔実施例〕

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

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

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

この輝度計算部３で計算された輝度を、画像として記憶
する画（１記憶部４が設けられている。この画像記憶部
４は、画像の合成を行なう前に、総ての画素の輝度をＯ
に設定する。

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

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

第２図は、画素ｐ（ｉ、ｊ）の輝度Ｉの計算方法を示す
説明図であり、図のように光源し、物体０．０′および
視点Ｅが配置されている。第２図に示すように、光線探
索法においては、光源りから画素ｐ　（ｉ、ｊ＞を通っ
て視点Ｅに至る光線の経路を逆向きに辿って、画素ｐ（
ｉ、ｊ）の輝度の計算を行なう。ここで、画素ｐ（ｉ、
ｊ）の輝度Ｉを、視点Ｅから画素ｐ（ｉ、ｊ）を通って
逆向きに発生される光線Ｒの輝度と呼ぶことにする。第
２図および以下の説明でＲ、Ｒ’　、　Ｒｔ等は光線を
示し、Ｋ”、　ＴＥ’　、　Ｕ；７は方向を示し、方向
ｒは光線Ｒの方向を示すというように対応する。

この光線Ｒの輝度Ｉとは、画素ｐ（’ｉ、ｊ＞を通って
視点Ｅに入射する光の強度■である。光線Ｒの輝度Ｉは
、次式で計算される。（＊は掛は算を示す） Ｉ＝ｒｅｆ＊Ｉ’　十ｄｉｆ＊　（ｒ−Ｈ）＊ＩＬｒｅ
ｆ：物体０の反射係数 ｄｉｆ：物体Ｏの拡散係数 Ｉ’　　　：Ｒ’力方向らの入射光強度ＩＬ　：光源り
からの入射光強度 Ｎ９：物体Ｏの表面の単位法線ベクトルｆ、　　　、　
ｆ方向の正反射方向ベクトルれ゛　　：光源りの方向ベ
クトル これらの２つの入射光強度１’、Ｉｔを求めるために、
光線Ｒと物体Ｏとの交点ＣＰを始点として方向がＲ，Ｒ
Ｌとなる２つの光線Ｒ’、ＲＬを発生させる。また、輝
度■を求めるためのＩ’、Ｉ。

の係数を、光線Ｒ’、ＲＬの減衰率Ｇ’、ＧＬとして設
定する。すなわち、光線Ｒが物体Ｏに衝突することによ
り減衰されて、光線Ｒ’、ＲＬが発生されるのである。

これらの減衰率Ｇ’、ＧＬは、Ｇ’　＝Ｇ＊　ｒｅ　ｆ ＧＬ　　＝Ｇ＊　ｄ　ｉ　ｆ　＊　（Ｎ−ＲＬ）Ｇ　　
：光線Ｒの減衰率（＝１） となる。これらの減衰率Ｇ’、ＧＬを用いることにより
、光線Ｒの輝度■すなわち画素ｐ　（ｉ、ｊ＞の輝度Ｉ
は、次のように求められる。

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

さらに第２図に示すように、光線Ｒ′が物体Ｏ′と交差
した場合は、同様に光線Ｒ″、Ｒ，’とが発生される。

これらの減衰率Ｇ”、ＧＬ’は、やはり同様に次式で計
算される。

Ｑ”　　＝Ｇ’＊ｒｅｆ’ ＧＬ’　　＝Ｇ’　＊ｄｉ　ｆ’　＊　（Ｎ　　、　Ｒ
ｔ　　）ｒｅｆ’　：物体０′の反射係数 ｄｉｆ’　　：物体０′の拡散係数 Ｎ１′：物体０′の表面の単位法線ベクトルｒ′　　：
光源りの方向ベクトル このように、減衰率Ｇ″、ＧＬ　’には、減衰率Ｇ′が
積算される。

ただし、光線ＲＬの処理は、光線Ｒ，Ｒ’とは異なる。

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

この種類Ｃは、光線Ｒが物体に向かう場合には０、光源
に向かう場合には１という値が与えられる。

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

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

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

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

第３図は、光線Ｒを発生した際に設定すべき光線Ｒの情
報を示す説明図である。第３図に示すように光線Ｒを発
生した際には、光線Ｒの情報として、光線Ｒを示す半直
線の始点位置座標（ＳＸ。

Ｓｙ、Ｓ、）と方向（ｄ、、ｄ、、ｄ、）とが設定され
る。また、光線Ｒの輝度が影響を与える画素ｐ（ｉ、ｊ
＞の位置（ｉ、ｊ＞も、光線Ｒの情報として設定される
。さらに、光線Ｒの持つ減衰率Ｇと光線Ｒの回数Ｔと光
線Ｒの種類Ｃも光線Ｒの情報として設定される。

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

そのために、第１図（ａ＞の初期光線発生部１には、情
報入力部６により、視点Ｅの位置座標（Ｅ、、　Ｅ、、
Ｅ、）が入力される。また、合成される画像Ｐを定義す
る情報として、画像Ｐの平面と範囲を示すパラメータが
、情報入力部６がら入力される。初期光線発生部１では
、これらのパラメータに基づいて、光線Ｒの情報の発生
を行なう。この光線Ｒを示す半直線を求める方法の一例
は、ティー・ホイッテッド（Ｔ、Ｗｈｉ　ｔｔｅｄ）著
、コミュニケーション　オブ　ニーシーエム（Ｃｏｍ＋
＊ｕｎｉｃａｔｉｏｎ　ｏｆ　ＡＣＭ）　、第２３巻、
第６号、３４３頁から３４９頁、論文［アン　インブル
ーブト　イルミネーション　モデル　フォオ　シェープ
イツト　ディスプレイ（＾ｎ　Ｉｍｐｒｏｖｅｄ　ＩＩ
Ｉｕ＋５ｉｎａ−ｔｉｏｎ　Ｍｏｄｅｌ　ｆｏｒ　５ｂ
ａｄｅｄ　Ｄｉｓｐｌａｙ）」に記載されている。

次に、この半直線と物体定義空間との交点のうちで、最
も視点に近い交点の位置座標（ｓ’、、ｓ、。

Ｓ２）を求める。この位置座標（Ｓ、、Ｓ、、Ｓ、）が
、光線Ｒの始点位置塵＠　（ｓ　、、ｓ　、、ｓ　ｚ）
となる。すなわち、光線Ｒが最初に物体定義空間に入射
する位置が、光線Ｒの始点となる。また、視点Ｅがら画
素ｐに向かｊ方向が、光線Ｒの方向（ｄ　ＸＩ　ｄ　、
。

ｄ、）となる。さらに、画素ｐ（ｉ、ｊ）の位置（ｉ、
ｊ）が、光線Ｒの画素位置（ｉ、ｊ）として設定される
。

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

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

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

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

第６図は、物体としての球の外接領域を示す説明図であ
る。第６図に示すように、物体０＋の外接領域は、Ｘ方
向の範囲（Ｘ　ｉ　−＋　Ｘ　＋＋　）　＋　’ｐ’方
向の範囲（３’　Ｉ−＋　３’　＋＋）、　Ｚ方向の範
囲（Ｚ　ｌ−＋　Ｚ　＋＋）で示される直方体である。

これらの値は次式で求められる。

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

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

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

ｙ、ｚ方向のａ、ｂ、ｃ番めの輝度計算部３を（ａ、ｂ
、ｃ）輝度計算部３と呼ぶことにすると、（ａ、ｂ、ｃ
）！１度計算部３は、（ａ−１゜ｂ、ｃ）、（ａ＋１．
’ｂ、ｃ）、（ａ、ｂ−１゜ｃ）、（ａ、ｂ＋１．ａ−
）、（ａ、ｂ、ｃ−１）。

（ａ、ｂ、ｃ＋１＞輝度計算部３と接続されている。

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

第９図は、物体を定義する空間を、各輝度計算部３に割
り当てられる担当領域Ｓに分割する方法を示す説明図で
ある。第９図に示すように、Ｘ。

ｙ、ｚ座標軸のうちの１軸にそれぞれ垂直な平面により
、物体定義空間を複数の直方形状の領域に分割する。こ
の場合に、Ｘ方向の領域数がＡ個、ｙ方向の領域数がＢ
個、２方向の領域数がＣ個となるように、分割を行なう
。そして、（ａ、ｂ。

Ｃ）輝度計算部３に、Ｘ方向の８番め、ｙ方向の５番め
、２方向の０番めの領域を割り当てる。これにより、分
割されたすべての領域をそれぞれ１個の輝度計算部３に
割り当てることができる。

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

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

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

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

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

そこで、光線情報判定手段３７では、光線Ｒの始点位置
座標（Ｓ、、Ｓ、、Ｓ、）と担当領域Ｓの範囲（Ｘ−・
ｘ＋）・　（ｙ−、ｙ＋　＞、（ｚ−。

ｚ＋）とが、比較される。

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

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

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

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

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

第１４図に示すように、輝度計算部３に設けられた負荷
決定手段４３は、光線情報記憶手段３７に記憶された光
線Ｒの個数を、その輝度計算部３の負Ａ’Ｆとして求め
る。なお、ここでは説明を簡単にするためにこのような
負荷決定方法としたが、この池にも様々な負荷の決定方
法が可能である。

これ以外の方法を取った場合でも、はぼ同様に処理を行
うことができる。例えば、負荷決定手段４３において各
輝度計算部３が実際に処理を行っている時間と、光線Ｒ
の情報を待っている時間とを計測して、これらの値から
各輝度計算部３の負荷を決定しても良い。

こうして負荷決定手段４３で決定された負荷Ｆは、相互
通信手段３１を介して、輝度計算部３のＸ−、Ｘ＋、’
ｉ’−，３’＋　、Ｚ−、Ｚ子方向に接続された輝度計
算部３　（ｘ−＞、（ｘ＋　）。

（ｙ−）、（ｙや）、（ｚ−＞、（ｚ＋　）にそれぞれ
伝達される。（Ｘ一方向に接続された輝度計算部３を輝
度計算部３　（Ｘ−’）と記し、他の方向においても同
様に記す）。そして、方向決定手段４４は、輝度計算部
３　（ｘ−＞、（ｘ＋　＞。

（ｙ−＞、（ｙ＋　＞、（ｚ−）、（ｚ＋　）から相互
通信手段３１を介して伝達される負荷Ｆ（ｘ−）。

Ｆ　（ｘ＋　＞、　Ｆ　（ｙ−）、　Ｆ　（ｙ＋　＞、
　Ｆ　（ｚ−）。

Ｆ　（ｚ＋　）の内で（輝度計算部３　（ｘ−）の負荷
をＦ　（ｘ−）と記し、他の方向に接続する輝度計算部
３の負荷も同様に記す）、で最大となるものを１つだけ
選択する。そして、その方向を示す値りを出力する。こ
の値りは１から６までの整数であり、１から順にそれぞ
れＸ　−、Ｘ＋　、　３／　−。

３’＋　、Ｚ−、Ｚや方向を示している。こうして方向
決定手段４４で決定した方向を示す値りを、担当領域Ｓ
の拡大方向として領域拡大手段４６に出力する。同時に
、方向決定手段４４で求めた負荷の最大値Ｆ　ｗａｘを
、拡大決定手段４５に出力する。

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

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

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

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

このような担当領域Ｓの拡大処理を行なうことにより、
各担当領域Ｓに含まれている物体の数や通過する光線の
数を増加させることができ、各輝度計算部３の計算量を
増加させることができる。

同時に、値りで示される方向に隣接する領域を担当する
隣接輝度計算部３の負荷を減少させることができる。従
って、全体の計算量を平均化して適切な負荷の再配分を
図ることができる。

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

（ｂ）に示すような場合、担当領域Ｓａから担当領域ｓ
ｂに入射する光線Ｒの情報を、輝度計算部３ａから相互
通信手段３１を介して、直接に輝度計算部３ｂへ転送す
ることはできない。

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

このような転送処理を行うために、各輝度計算部３の光
線情報記憶手段３４に記憶された光線Ｒの情報は、まず
光線情報判定手段３７に読み出される。この光線情報判
定手段３７は、光線Ｒの始点位置座標（ｓＸ、Ｓ、、ｓ
−）と、領域情報記憶手段３３から読み出した担当領域
Ｓの範囲（ｘ−、ｘ＋）、（ｙ−、ｙ＋）、（Ｚ−、ｚ
＋）とを比較して、次のような処理を行う。

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

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

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

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

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

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

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

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

そのために物体情報判定手段３８は、領域情報記憶手段
３３から担当領域Ｓの範囲（ｘ−。

Ｘｌ　＞、（ｙ−、ｙ＋　＞、（ｚ−、Ｚｌ　）と各物
体Ｏ５の外接領域の範囲（Ｘし＋　Ｘ　１４）　＋　　
（３’　ｌ−＋ｙ＋＋）、（Ｚｌ−＋　ｚｔ＋）との比
較処理を行い、各物体Ｏ１が担当領域Ｓに含まれるかど
うかの判定処理を行う。

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

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

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

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

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

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

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

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

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

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

〔発明の効果〕

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

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

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

【図面の簡単な説明】

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

Claims (1)

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