JPH0632044B2

JPH0632044B2 - 物体画像合成装置

Info

Publication number: JPH0632044B2
Application number: JP22765786A
Authority: JP
Inventors: 啓次根本
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1986-09-25
Filing date: 1986-09-25
Publication date: 1994-04-27
Anticipated expiration: 2009-04-27
Also published as: JPS6381585A

Description

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

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

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

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

このように各光線は、その光線が通過する領域に含まれ
る物体とのみ交差が判定される。従って、各光線がすべ
ての物体と交差判定の処理をされるのに比べて、全体の
処理量ははるかに少なくなる。

また、このような交差判定処理は、各コンピュータで並
列に実行される。この並列処理効果も加わって、非常に
高速に画像を合成できる。

（発明が解決しようとする問題点）このような従来の画像の合成方法において、各コンピュ
ータは割り当てられた領域を通過する光線と、その領域
に含まれる物体との交差判定処理を行う。このために要
する処理量は、すべての物体と交差判定処理を行う場合
と比べればはるかに少ないが、やはり膨大な処理量であ
る。そこで、物体が存在する領域と光線との交差を判定
するという簡単な処理によって、あらかじめこの光線と
交差する可能性のある物体のみを選択して、これらの物
体とのみ従来の交差判定処理を行うという方法がある。
この方法の一例は、文献３：ピクセル（PIXEL）、第37
号、秋本彰著、「レイ・トレーシングの高速化技法につ
いて−これまでの手法とARTSの手法」に記載されてい
る。この方法では、光線が通過する単位立方体の列を３
次元デジタル直線として発生する。この３次元デジタル
直線を用いて、物体が存在する領域と光線との交差を高
速に判定している。

しかし、このような従来の方法では、各単位立方体毎に
その単位立方体が含んでいる物体を記憶することで、物
体が存在する領域を表現している。従って、物体が存在
する領域を表現するために必要なデータ量が膨大となっ
てしまうという問題点がある。

本発明は、このような問題点を解決するために、非常に
少ないデータ量で物体が存在する範囲を表現でき、これ
を利用して高速の交差判定処理を行うことのできる、物
体画像合成装置を提供することを目的とする。

（問題点を解決するための手段）本発明の物体画像合成装置は、視点から各画素を通る複
数の光線の情報を発生する初期光線発生部と、物体の情
報を設定する物体情報設定部と、上記物体の定義される
空間を分割することにより生成される複数の領域のうち
の１領域を担当してこの領域を通過する光線と上記担当
領域に含まれる物体との交差判定処理を行なうことによ
り上記画素の輝度を計算する複数の輝度計算部と、この
輝度計算部で計算された輝度を上記画像として記憶する
画像記憶部とで構成されるとともに、上記輝度計算に、
座標軸に垂直で等間隔な複数の平面で上記物体定義空間
を分割して生成される複数の単位立方体のうちで上記光
線が通過する単位立方体の列を３次元デジタル直線とし
て発生する直線発生手段と、上記複数の平面のうちの一
部または全部の平面で上記物体定義空間を分割して生成
される複数の領域のうちの１領域を上記輝度計算部の相
当領域としてこの担当領域の範囲を記憶する領域情報記
憶手段と、上記担当領域に含まれる物体の上記担当領域
における存在範囲を決定する存在範囲決定手段と、上記
存在範囲を記憶する存在範囲記憶手段と、上記直線発生
手段で発生される単位立方体の列と上記存在範囲記憶手
段に記憶された上記物体の存在範囲とを比較して上記担
当領域に含まれる物体の内で上記光線が交差する可能性
のある物体を選択する物体選択手段と、この物体選択手
段で選択された物体と上記光線との交差判定処理を行う
交差判定手段とが備えられている。

（作用）本発明の物体画像合成装置における、物体と光線との交
差判定方法について述べる。

物体定義空間を座標軸に垂直で等間隔な複数の平面で分
割して生成される複数の立方体を、単位立方体とよぶ。
また、これらの複数の平面のうちの一部または全部の平
面によって、物体定義空間を分割して複数の領域を生成
する。こうして生成される領域は、１個または複数の単
位立方体から成る直方体となり、この直方体の各境界面
は、各座標軸に垂直となる。これらの複数の領域のうち
の１領域が、１つの輝度計算部の担当領域として割り当
てられる。この担当領域の範囲は、輝度計算部に備えら
れた領域情報記憶手段に記憶される。

また、各輝度計算部に備えられた存在範囲決定手段は、
この担当領域に含まれる物体の、担当領域における存在
範囲を決定する。そして、決定された存在範囲は、存在
範囲記憶手段に記憶される。

さらに、各輝度計算部に備えられた直線発生手段は、光
線が通過する単位立方体の列を、３次元デジタル直線と
して順次発生する。そして物体選択手段は、担当領域に
含まれる物体の存在範囲を存在範囲記憶手段から読み出
して、物体の存在範囲と順次発生される単位立方体との
比較を行う。この比較により、発生された単位立方体が
この存在範囲に含まれる場合は、光線がその物体と交差
する可能性があると判定して、この物体を交差判定処理
の対象として選択する。

そして交差判定手段は、物体選択手段で選択された物体
と光線との交差判定処理を行う。

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

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

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

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

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

第２図は、画素p(i,j)の輝度Ｉの計算方法を示す、説明
図である。第２図に示すように、光線追跡法において
は、光源Ｌから画素p(i,j)を通って視点Ｅに至る光線の
経路を逆向きに辿って、画素p(i,j)の輝度の計算を行な
う。ここで、画素p(i,j)の輝度Ｉを、視点Ｅから画素p
(i,j)を通って逆向きに発生される光線Ｒの輝度と呼ぶ
ことにする。この光線Ｒの輝度Ｉとは、画素p(i,j)を通
って視点Ｅに入射する光の強度Ｉである。光線Ｒの輝度
Ｉは、次式で計算される。

これらの２つの入射光強度Ｉ′，R_Lを求めるために、交
点CPを始点として方向がとなる２つ光線Ｒ′，R_Lを発生させる。また、輝度Ｉを
求めるためのＩ′，I_Lの係数を、光線Ｒ′，R_Lの減衰率
Ｇ′，G_Lとして設定する。すなわち、光線Ｒが物体Ｏに
衝突することにより減衰されて、光線Ｒ′，R_Lが発生さ
れるのである。これらの減衰率Ｇ′，G_Lは、となる。これらの減衰率Ｇ′，G_Lを用いることにより、
光線Ｒの輝度Ｉすなわち画素p(i,j)の輝度Ｉは、次のよ
うに求められる。

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

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

このように、減衰率Ｇ″，G_L′には、減衰率Ｇ′が積算
される。

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

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

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

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

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

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

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

第４図は、光線Ｒが通過する単位立方体の列を、３次元
デジタル直線として発生するために、光線Ｒに設定され
る情報を示す、説明図である。ここで、ｘ，ｙ，ｚ座標
軸に垂直で等間隔な複数の平面で物体定義空間を分割し
て生成される複数の立方体を、単位立方体と呼ぶ。第４
図に示すように、３次元デジタル直線として順番に発生
された単位立方体のうちで、最後に発生された単位立方
体の位置（T_x,T_y,T_z）が、光線Ｒの情報として設定され
る。すなわちこの位置（T_x,T_y,T_z）は、光線Ｒの現在の
位置を示しており、光線Ｒが物体定義空間を通過するの
に従って更新されていく。また、３次元デジタル直線を
順次発生するための誤差情報ERも、光線Ｒの情報として
設定される。この誤差情報ERを加算して判定することに
より、３次元デジタル直線を高速に発生できる。この誤
差情報ERの意味や計算方法については、文献３に詳述さ
れている。

第５図は、初期光線発生部１の動作を説明するための、
説明図である。第５図に示すように、初期光線発生部１
において、視点Ｅを始点として、画像Ｐを構成する各画
素p(i,j)を通る半直線としての光線Ｒを発生する。

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

次に、この半直線の始点となる視点Ｅの位置座標（E_x,E
_y,E_z）を、光線Ｒの始点位置座標（S_x,S_y,S_z）として設
定し、視点Ｅから画素ｐに向かう方向を、光線Ｒの方向
（d_x,d_y,d_z）として設定する。また、画素p(i,j)の位置
(i,j)が、光線Ｒの画素位置(i,j)として設定される。

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

また、こうして発生される光線Ｒと物体定義空間との交
点のうちで、最も視点に近い交点の位置座標（t_x,t_y,
t_z）を求める。この位置座標（t_x,t_y,t_z）を整数化し
て、この交点を含む単位立方体を求めて、これを光線Ｒ
の情報としての位置（T_x,T_y,T_z）として設定する。この
位置（T_x,T_y,T_z）は、光線Ｒが最初に物体定義空間に入
射する位置の単位立方体を示している。そして、この単
位立方体を最初の単位立方体として、物体定義空間内に
おいて光線Ｒが通過する単位立方体の列が、各輝度計算
部３において３次元デジタル直線として発生される。

その後の処理において、光線Ｒが領域Ｓを通過して領域
Ｓ′に入射する場合には、光線Ｒの情報は輝度計算部３
間で転送される。その際に、光線Ｒの情報として３次元
デジタル直線の現在の位置（T_x,T_y,T_z）は、新たな領域
Ｓ′と光線Ｒとの交点を含む単位立方体の位置に更新さ
れる。

さらに初期光線発生部１では、３次元デジタル直線を順
次発生するための誤差情報ERの初期値が計算されて、光
線Ｒの誤差情報ERとして設定される。この初期値の計算
方法は、前述の通り文献３に詳述されている。

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

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

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

第７図は、物体としての球の外接領域を示す、説明図で
ある。第７図に示すように、物体ｉの外接領域は、ｘ方
向の範囲（x_i-，x_i+）、ｙ方向の範囲（y_i-，y_i+）、ｚ
方向の範囲（z_i-，z_i+）で示される、複数の単位立方体
から成る直方体である。これらの値は整数値であり、次
式で求められる。

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

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

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

また、輝度計算部３は図中のx,y,z方向にそれぞれA,B,C
個ずつ並んでおり、全部の輝度計算部３の個数Ｄは、Ｄ＝Ａ＊Ｂ＊Ｃとなる。

第10図は、物体を定義する空間を、各輝度計算部３に割
り当てられる担当領域Ｓに分割する方法を示す。説明図
である。第10図に示すように、単位立方体の境界面とな
る複数の平面のうちの一部または全部の平面により、物
体定義空間を複数の直方体形状の領域に分割する。この
ような分割を行うことにより、各領域を製造個個または
１個の単位立方体で構成することができる。

またこの場合に、ｘ方向の領域数がＡ個、ｙ方向の領域
数がＢ個、ｚ方向の領域数がＣ個となるように、分割を
行なう。そして、(a,b,c)輝度計算部３に、ｘ方向のａ
番め、ｙ方向のｂ番め、ｚ方向のｃ番めの領域を割り当
てる。これにより、分割されたすべての領域をそれぞれ
１個の輝度計算部３に割り当てることができる。

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

第11図および第12図は、輝度計算部３に担当領域Ｓを示
す領域情報の内容を示す説明図である。第11図に示すよ
うに、輝度計算部３に設けられた領域情報記憶手段33に
は、その輝度計算部３の担当領域Ｓを示す領域情報が記
憶される。この領域情報としては、ｘ，ｙ，ｚ方向の何
番めかを示す(a,b,c)の値値と、第12図に示すような担
当領域Ｓのｘ，ｙ，ｚ方向の範囲(x_-,x₊),(y_-,y₊),(z_-,
z₊)とが記憶される。各領域が複数個または１個の単位
立方体から構成されているので、これらの範囲を示す値
は整数値となる。

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

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

第13図は、初期光線発生部１から輝度計算部３への光線
Ｒの情報の転送処理を示す説明図である。第13図に示す
ように、初期光線発生部１で発生されたすべての光線Ｒ
の情報は、接続線５を介してすべての輝度計算部３へ一
斉に転送される。そして、各輝度計算部３に設けられた
初期情報判定手段38は、初期光線発生部１から転送され
た光線Ｒの情報が、通信手段32を介して入力される。同
時に、領域情報記憶部33に記憶された担当領域Ｓの情報
が、この初期情報判定手段38によって読み出される。

こうして入力された光線Ｒの位置（T_x,T_y,T_z）は、光線
Ｒが最初に物体定義空間に入射する位置に設定されてい
る。このため、もしこの位置（T_x,T_y,T_z）が担当領域Ｓ
に含まれていれば、光線Ｒは担当領域Ｓを最初に通過す
ることになる。

そこで、初期情報判定手段38は、光線Ｒの位置（T_x,T_y,
T_z）と担当領域Ｓの範囲(x_-,x₊),(y_-,y₊),(z_-,z₊)との
比較を行う。

x_-≦T_x＜x₊ y_-≦T_y＜y₊ z_-≦T_z＜z₊ という３条件式のすべてが満たされる場合、位置（T_x,T
_y,T_z）は担当領域Ｓに含まれており、光線Ｒは担当領域
Ｓを最初に通過することになる。この場合、初期情報判
定手段38から光線Ｒの情報が光線情報記憶手段34に転送
されて、記憶される。

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

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

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

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

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

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

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

第16図(a),(b)は、輝度計算部３に設けられた存在範囲
決定手段40における、物体の存在範囲の決定方法を示す
説明図である。第16図(a)に示すように、まず存在範囲
決定手段40は、物体情報記憶手段35に記憶された物体情
報と、領域情報記憶手段33に記憶された担当領域Ｓの範
囲とを読み出す。そして、物体情報としての物体ｉの外
接領域の範囲(x_-,x₊),(y_-,y₊),(z_-,z₊)と、担当領域Ｓ
の範囲(x_i-,x_i+),(y_i-,y_i+),(z_i-,z_i+)とを比較して、
担当領域Ｓにおける各物体の存在範囲（ｘ′_i-,
ｘ′_i+），（ｙ′_i-,ｙ′_i+），（ｚ′_i-,ｚ′_i+）を次
のように決定する。

x_-≧x_i-ならばｘ′_i-＝x_- x_-＜x_i-ならばｘ′_i-＝x_i- x₊≦x_i+ならばｘ′_i+＝x₊ x₊＞x_i+ならばｘ′_i+＝x_i+ y_-≧y_i-ならばｙ′_i-＝y_- y_-＜y_i-ならばｙ′_i-＝y_i- y₊≦y_i+ならばｙ′_i+＝y₊ y₊＞y_i+ならばｙ′_i+＝y_i+ z_-≧z_i-ならばｚ′_i-＝z_- z_-＜z_i-ならばｚ′_i-＝z_i- z₊≦z_i+ならばｚ′_i+＝z₊ z₊＞z_i+ならばｚ′_i+＝z_i+ なお、ここでは簡単のために物体ｉの外接領域と担当領
域Ｓとの共通部分を、物体ｉの存在領域として決定し
た。しかし、第16図(b)に示すように物体ｉの存在範囲
をより小さい直方体で表現できる場合には、これを存在
範囲として決定しても良い。

そして、存在範囲決定手段40はこのように決定した物体
ｉの存在範囲（ｘ′_i-,ｘ′_i+），（ｙ′_i-,ｙ′_i+），
（ｚ′_i-,ｚ′_i+）を、存在範囲記憶手段41に記憶させ
る。

第17図は、輝度計算部３における光線Ｒの情報の処理方
法を示す、説明図である。第17図に示すように、光線情
報記憶手段34に記憶された光線Ｒの情報は、まず交差判
定手段39に読み出されて記憶される。この交差判定手段
39は、光線Ｒの情報を物体選択手段42と直線発生手段43
へ伝達する。この伝達された光線Ｒの情報を受けて、物
体選択手段42は、まず存在範囲記憶手段41から各物体ｉ
の存在範囲（ｘ′_i-,ｘ′_i+），（ｙ′_i-,ｙ′_i+），
（ｚ′_i-,ｚ′_i+）を読み出して記憶する。そして、各
物体ｉに対応するフラグF_iを、０に設定する。このフラ
グF_iは、物体選択手段42の内部に設けられており、光線
Ｒの情報を受ける毎に０に設定される。

さらに物体選択手段42は、光線Ｒが交差する可能性のあ
る物体ｉを選択するために、光線Ｒの情報としての光線
Ｒの位置（T_x,T_y,T_z）と、各物体ｉの存在範囲
（ｘ′_i-,ｘ′_i+），（ｙ′_i-,ｙ′_i+），（ｚ′_i-,
ｚ′_i+）とを比較する。ただし、物体ｉに対応するフラ
グF_iの値が１の場合には、この物体ｉについての交差判
定処理は既に行われているので、比較を行わない。も
し、ｘ′_i-≦T_x＜ｘ′_i+ ｙ′_i-≦T_y＜ｙ′_i+ ｚ′_i-≦T_z＜ｚ′_i+ という３条件のすべてが成り立つ場合には、光線Ｒが通
過する単位立方体が物体ｉの存在範囲に含まれているこ
とになる。従って、この物体ｉは光線Ｒと交差する可能
性がある。そこで、物体ｉの番号ｉを交差判定手段39に
転送する。同時に、フラグF_iを１に設定する。このよう
にフラグF_iが１に設定された物体ｉの情報は、以後の処
理では比較を行わない。この操作により、同じ物体ｉの
番号ｉを１つの光線Ｒに関して何度も交差判定手段39に
転送してしまうことを防止している。

このような処理を各物体ｉについておこなった後に、物
体選択手段42は直線発生手段43に制御情報を送る。この
制御情報を受けた直線発生手段43は、光線Ｒが通過する
次の単位立方体を発生する。

第18図(a),(b)は、直線発生手段43における直線の発生
方法を示す説明図である。第18図(a),(b)に示すよう
に、まず直線発生手段43は光線Ｒの情報を交差判定手段
39から受けて、この情報を記憶する。そして、物体選択
手段42からの制御情報を受ける毎に、記憶している光線
Ｒの情報である誤差情報ERの加算判定処理により、光線
Ｒの通過する単位立方体を１つ発生する。

このような単位立方体を発生するために、直線発生手段
43はまず誤差情報ERの加算判定処理を行い、その結果に
基づいて誤差情報ERの更新処理を行う。次に、直線発生
手段43は、この加算判定処理結果に基づいて、単位立方
体を発生する座標軸を、ｘ，ｙ，ｚ座標軸の中から選択
して決定し、選択情報SELを決定する。この選択情報SEL
の値は０，１，２のうちのどれかであり、これらの値は
それぞれｘ，ｙ，ｚ座標軸を示している。同時に、直線
発生手段43は発生する単位立方体の方向DIRも決定す
る。この方向DIRの値は１または−１である。これらの
値の決定方法は、前述の通り文献３に示されている。

例えば、第18図(a)に示すように単位立方体（T_x,T_y,
T_z）の次の単位立方体を発生する場合に、直線発生手段
43における光線Ｒの誤差情報ERの加算判定処理によっ
て、選択情報SELを０、方向DIRを１に決定した場合に
は、直線発生手段43は、単位立方体（T_x＋１，T_y,T_z）
を発生する。また、選択情報SELを０に、方向DIRを−１
に決定した場合には、直線発生手段43は、単位立方体
（T_x−１，T_y,T_z）を発生する。

そして、直線発生手段43は、記憶している光線Ｒの情報
のうちの位置（T_x,T_y,T_z）を、新たに発生した単位立方
体（T_x′，T_y′，T_z′）に変更する。こうすることによ
り光線Ｒの位置（T_x,T_y,T_z）が更新されて、この位置
（T_x,T_y,T_z）が、３次元デジタル直線としての単位立方
体の列の最後の単位立方体を示すようになる。

また直線発生手段43は、決定した選択情報SELと方向DIR
とに基づいて、新たな光線Ｒの位置（T_x,T_y,T_z）が担当
領域Ｓの範囲内であるか範囲外であるかを判定する。そ
して、範囲外であると判定した場合には光線Ｒの通過方
向を決定して、光線Ｒの情報と通過方向とを光線情報転
送手段44へ送る。

例えば、第18図(b)に示すように、発生された単位立方
体が担当領域Ｓの範囲外の場合には、単位立方体が発生
された方向が、光線Ｒの通過方向となる。

このような判定を行うために、直線発生手段43は、選択
情報SELと方向DIRとで示される担当領域Ｓの範囲の値
を、領域情報記憶手段33から読み出す。そして、この値
と位置（T_x,T_y,T_z）のうちの選択情報SELで示される値
との比較により、発生された単位立方体が担当領域Ｓの
範囲内か範囲外かを判定する。

例えば、第18図(a)に示すように選択情報SELが０で方向
DIRが１の場合には、範囲のx₊の値を読み出す。この値x
₊と位置（T_x,T_y,T_z）のうちの選択情報SELで示される値
T_xとを比較して、次のように判定する。

T_x＞x₊のとき範囲外 T_x≦x₊のとき範囲内また、選択情報SELが０で方向DIRが−１の場合には、範
囲のx_-の値を読み出す。この値x_-と位置（T_x,T_y,T_z）の
うちの選択情報SELで示される値T_xとを比較して、次の
ように判定する。

T_x＜x_-のとき範囲外 T_x≧x_-のとき範囲内こうして、直線発生手段43が位置（T_x,T_y,T_z）を範囲内
と判定した場合には、更新された光線Ｒの位置（T_x,T_y,
T_z）を物体選択手段42に送る。これを受けた物体選択手
段42は、新たな位置（T_x,T_y,T_z）と各物体ｉの存在範囲
との比較処理を行い、光線Ｒと交差する可能性のある物
体ｉの番号ｉを交差判定手段39へ送る。

同様に、範囲外と判定した場合には、物体選択手段42に
範囲外であることを示す制御情報を送る。同時に、光線
Ｒの情報と選択情報SELおよび方向DIRとを光線情報転送
手段44へ送る。これを受けた物体選択手段42は、交差判
定手段39に終了を示す制御情報を送る。

以上の処理により、物体選択手段42は、担当領域Ｓに含
まれている各物体ｉのうちで、光線Ｒと交差する可能性
のあるすべての物体ｉの番号ｉを選択して、交差判定手
段39へ送ることができる。そして、交差判定手段39は物
体選択手段42で選択された物体ｉの情報を物体情報記憶
手段35から読み出して、光線Ｒとの交差判定処理を行
う。

この交差判定処理の結果、光線Ｒが物体と交差している
場合には、光線Ｒから新たな光線Ｒ′や光線R_Lが発生さ
れ、これらの光線Ｒ′と光線R_Lの情報が、光線情報記憶
手段34に記憶される。ただし、光線Ｒの情報としての回
数Ｔが０の場合には、前述の通り新たな光線Ｒ′を発生
しない。このような交差判定処理については、前述の各
文献および第２図に示されている。

このように、光線Ｒが担当領域Ｓ内で物体と交差してい
る場合には、光線Ｒの情報を隣接する輝度計算部３に転
送する必要は無い。そこで、交差判定手段39は、光線情
報転送手段44に光線Ｒが物体と交差することを示す制御
情報を送る。この制御情報を受けて、光線情報転送手段
44は、既に直線発生手段43から送られていた光線Ｒの情
報と選択情報SELおよび方向DIRとを消去する。

また、交差判定手段39における交差判定処理の結果、物
体と交差しない光線Ｒの情報は、隣接する輝度計算部３
に転送されなければならない。そこで交差判定手段39
は、光線情報転送手段44に光線Ｒが物体と交差しないこ
とを示す制御情報を送る。この制御情報を受けると、光
線情報転送手段44は、既に直線発生手段43から送られて
いた選択情報SELと方向DIRとに基づいて、やはり既に直
線発生手段43から送られていた光線Ｒの情報の転送処理
を行う。この転送処理を行うために、光線情報転送手段
44は、まず選択情報SELと方向DIRとで示される方向に輝
度計算部３が接続されているかどうかの有無の情報を、
領域情報記憶手段33から読み出す。

もし、この方向に輝度計算部３が接続されている場合に
は、選択情報SELと方向DIRとで示される方向に接続され
た輝度計算部３に、相互通信手段31を介して光線Ｒの情
報を転送する。

例えば、直線発生手段43から出力された選択情報SELが
０で方向DIRが１の場合には、x₊方向に接続された輝度
計算部３に光線Ｒの情報を転送する。同様に、直線発生
視手段43から出力された選択情報SELが０で方向DIRが−
１の場合には、x_-方向に接続された輝度計算部３に光線
Ｒの情報を転送する。こうして転送された光線Ｒの情報
は、隣接する輝度計算部３３において相互通信手段31か
ら読み出されて、光線情報記憶手段34に記憶される。

また、直線発生手段43から送られてきた選択情報SELと
方向DIRとで示される方向に輝度計算部３が接続されて
いない場合には、光線Ｒは物体定義空間の外に出ること
になる。従って、この光線Ｒはすべての物体定義空間に
おいて物体と交差していないことが分かる。

そこで光線情報転送手段44は、この光線Ｒを情報を輝度
決定手段37に出力する。この輝度決定手段37では、光線
Ｒの情報としての光線Ｒの種類Ｃを調べて、この光線Ｒ
が光源Ｌへ向う光線である場合には、光源情報記憶手段
36から光源の情報を読み出して、光線Ｒの輝度Ｉを決定
する。ただし、複数個の光源L_iが存在する場合には、光
源Ｒの回数Ｔで示される光源番号ｉを参照して、その番
号の光源L_iの情報を読み出して、輝度Ｉを決定する。こ
の決定処理は、前述の各文献および第２図で示した通り
である。そして、通信手段32を介して、光源Ｒの情報が
示す画像記憶部４の画素p(i,j)に、その輝度Ｉを加算す
る。

また、もしこの光線が物体へ向う光線である場合には、
光線Ｒの輝度Ｉは０になるので、輝度Ｉの加算処理は行
わずに光線Ｒの情報を消去する。

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

（発明の効果）本発明の物体画像合成装置では、光線と交差する可能性
のある物体を選択するために、３次元デジタル直線を利
用している。この３次元デジタル直線は非常に高速に発
生きるので、従来多くの処理量を必要としていた物体の
選択処理を、大幅に高速化することができる。

同時に、空間を分割する並列処理によって、光線追跡法
による画像の合成を行う場合に、担当領域に含まれる物
体の内で、光線と交差する可能性のあるものとのみ交差
判定処理を行えばよいので、交差判定処理の効果を十分
に高速化することができる。

また、物体の存在範囲というデータ量の少ない情報を基
に効果的な物体の選択を実行できるので、従来と比べて
必要なデータ量を大幅に削減できる。

【図面の簡単な説明】

第１図(a)は、物体画像合成装置の全体を示す全体構成
図、第１図(b)は、その輝度計算部の詳細な構成を示す
構成図、第２図は、画素p(i,j)の輝度Ｉの計算方法を示
す説明図、第３図は、光線Ｒを発生した際に設定すべき
光線Ｒの情報を示す説明図、第４図は、光線Ｒが通過す
る単位立方体の列を、３次元デジタル直線として発生す
るために、光線Ｒに設定される情報を示す説明図、第５
図は、初期光線発生部Ｉの動作を説明するための説明
図、第６図は、物体情報設定部２に設定される物体の情
報を示す説明図、第７図は、物体としての球の外接領域
を示す説明図、第８図は、物体情報設定部２に設定され
る光源の情報を示す説明図、第９図は、複数の輝度計算
部３を３次元配列状に結合する方法を示す説明図、第10
図は、物体を定義する空間を、各輝度計算部３に割り当
てられる担当領域Ｓに分割する方法を示す説明図、第11
図および第12図は、輝度計算部３の担当領域Ｓを示す領
域情報の内容を示す説明図、第13図は、初期光線発生部
１から輝度計算部３への光線Ｒの情報の転送処理を示す
説明図、第14図は、輝度計算部３に設けられた物体情報
記憶手段35と光源情報記憶手段36に物体情報設定部２か
ら物体情報と光源情報とを記憶させる処理を示す説明
図、第15図(a),(b)は、輝度計算部３の担当領域Ｓと、
物体情報の外接領域との比較処理を示す説明図、第16
図、輝度計算部３に設けられた存在範囲決定手段40にお
ける、物体の存在範囲の決定方法を示す説明図、第17図
は、輝度計算部３における光線Ｒの情報の処理方法を示
す説明図、第18図(a),(b)は、直線発生手段43における
直線の発生方法を示す説明図である。図において、１……初期光線発生部、２……物体情報設
定部、３……輝度計算部、４……画像記憶部、５……接
続線、６……情報入力部、31……相互通信手段、32……
通信手段、33……領域情報記憶手段、34……光線情報記
憶手段、35……物体情報記憶手段、36……光源情報記憶
手段、37……輝度決定手段、38……初期情報判定手段、
39……交差判定手段、40……存在範囲決定手段、41……
存在範囲記憶手段、42……物体選択手段、43……直線発
生手段、44……光線情報転送手段。

Claims

【特許請求の範囲】

【請求項１】光源から視点に至る光線の経路を逆向きに
辿って、物体と光線との交差判定処理を行ない、上記物
体を表示すべき画像を構成する各画素の輝度を計算する
光線追跡法による上記画像の合成を行なうために、上記
視点から上記の各画素を通る複数の光線の情報を発生す
る初期光線発生部と、上記物体の情報を設定する物体情
報設定部と、上記物体の定義される空間を分割すること
により生成される複数の領域のうちの１領域を担当して
この領域を通過する光線と上記複数の領域のうちの１領
域である担当領域に含まれる物体との交差判定処理を行
なうことにより上記画素の輝度を計算する複数の輝度計
算部と、この輝度計算部で計算された輝度を上記画像と
して記憶する画像記憶部とで構成される物体画像合成装
置において、上記輝度計算部に、座標軸に垂直で等間隔
な複数の平面で上記物体定義空間を分割して生成される
複数の単位立方体のうちで上記光線が通過する単位立方
体の列を３次元デジタル直線として発生する直線発生手
段と、上記複数の平面のうちの一部または全部の平面で
上記物体定義空間を分割して生成される複数の領域のう
ちの１領域を上記輝度計算部の担当領域としてこの担当
領域の範囲を記憶する領域情報記憶手段と、物体の外接
領域と上記担当領域との共通部分である存在範囲を決定
する存在範囲決定手段と、上記存在範囲を記憶する存在
範囲記憶手段と、上記直線発生手段で発生される単位立
方体の列と上記存在範囲記憶手段に記憶された上記物体
の存在範囲とを比較して上記担当領域に含まれる物体の
内で上記光線が交差する可能性のある物体を選択する物
体選択手段と、この物体選択手段で選択された物体と上
記光線との交差判定処理を行う交差判定手段とが備えら
れていることを特徴とする、物体画像合成装置。