(57)【特許請求の範囲】
【請求項１】
視点からスクリーン上の点を通って更に延びる光線と３次元物体との交点を求め、該交点の光の状態を算出して前記スクリーン上の点の色を決定する光線追跡法を用いて３次元物体の２次元画像を生成する際に、前記３次元物体を含む直方体からなるバウンディングボックスを構成する６面の何れかの面と前記光線とが交差するか否かを判定する面交差判定を実行して、前記光線と交差すると判定された面を持つ前記バウンディングボックスを選択し、該バウンディングボックスに含まれる前記３次元物体に対してのみ前記光線との交点を求める交点計算を実行する制御手段を備える画像生成装置において、
更に、前記視点が前記バウンディングボックスに内包されるか否かを判定する内包判定を前記制御手段の指令により実行する内包判定手段を備え、
前記制御手段は、まず前記内包判定手段に前記内包判定を実行させ、該内包判定によって前記視点が前記バウンディングボックスに内包されると判定された場合は前記面交差判定を実行せずに前記バウンディングボックスと前記光線とは交差すると判定し、前記内包判定によって前記視点が内包されないと判定された場合は前記面交差判定を実行して前記バウンディングボックスと前記視点とが交差するか否かを判定することを特徴とする画像生成装置。
【請求項２】
請求項１に記載の画像生成装置において、
前記制御手段は、前記内包判定手段に前記内包判定を実行させるに先立ち、前記バウンディングボックスが所定の大きさより大きいか否かを判定し、大きいと判定した場合は前記内包判定手段に前記内包判定を実行させ、小さいと判定した場合は前記内包判定手段に前記内包判定を実行させずに前記面交差判定を実行することを特徴とする画像生成装置。
【請求項３】
視点からスクリーン上の点を通って更に延びる光線と３次元物体との交点を求め、該交点の光の状態を算出して前記スクリーン上の点の色を決定する光線追跡法を用いて３次元物体の２次元画像を生成する際に、前記３次元物体を含む直方体からなるバウンディングボックスを構成する６面の何れかの面と前記光線とが交差するか否かを判定する面交差判定を実行して、前記光線と交差すると判定された面を持つ前記バウンディングボックスを選択し、該バウンディングボックスに含まれる前記３次元物体に対してのみ前記光線との交点を求める交点計算を実行する制御手段を備える画像生成装置において、
更に、対象としている前記バウンディングボックスの頂点のうち以下に示す正頂点を共有する３つの面をそれぞれ含む３つの無限平面について、各無限平面によって２つに分けられる領域のうち該無限平面自体を含まず且つ前記バウンディングボックス側でない領域の和集合で表される領域を不交差領域とし、前記視点が前記不交差領域に含まれるか否かを判定する不交差判定を前記制御手段の指令により実行する不交差判定手段を備え、
前記制御手段は、まず前記不交差判定手段に前記不交差判定を実行させ、該判定によって前記視点が前記不交差領域に含まれないと判定された場合のみ前記面交差判定を実行して前記バウンディングボックスと前記視点とが交差するか否かを判定し、前記不交差判定によって前記視点が前記不交差領域に含まれると判定された場合は前記面交差判定を実行せずに前記バウンディングボックスと前記光線とは交差しないと判定することを特徴とする画像生成装置。
前記光線を含む直線に関して、視点から見て前記光線のベクトル方向の無限遠を正無限、反対方向の無限遠を負無限とした場合、前記バウンディングボックスの各頂点から前記直線上に垂線を下ろした場合の交点位置が最も正無限方向に位置する頂点を正頂点、最も負無限方向に位置する頂点を負頂点とする。
【請求項４】
請求項３に記載の画像生成装置において、
更に、前記視点が前記バウンディングボックスに内包される否かを判定する内包判定を前記制御手段の指令により実行する内包判定手段を備え、
前記制御手段は、前記不交差判定手段に前記不交差判定を実行させることに先立って、前記内包判定手段に前記内包判定を実行させ、該判定によって前記視点が前記バウンディングボックスに内包されると判定された場合は他の交差判定を実行せずに前記バウンディングボックスと前記光線とが交差すると判定し、前記内包判定によって前記視点が前記バウンディングボックスに内包されないと判定された場合は続けて前記不交差判定手段に前記不交差判定を実行させ、該判定によって前記視点が前記不交差判定領域に含まれると判定された場合は前記光線と前記バウンディングボックスとは交差しないと判定し、前記不交差判定によって前記視点が前記不交差領域に含まれないと判定された場合は前記面交差判定を実行して前記バウンディングボックスと前記視点とが交差するか否かを判定することを特徴とする画像生成装置。
【請求項５】
請求項３に記載の画像生成装置において、
更に、前記視点が前記バウンディングボックスに内包されるか否かを判定する内包判定を前記制御手段の指令により実行する内包判定手段を備え、
前記制御手段は、まず前記不交差判定手段に前記不交差判定を実行させ、該判定によって前記視点が前記不交差領域に含まれると判定された場合は前記光線と前記バウンディングボックスとは交差しないと判定し、前記不交差判定によって前記視点が前記不交差領域に含まれないと判定された場合は続けて前記内包判定手段に前記内包判定を実行させ、該判定によって前記視点が前記バウンディングボックスに内包されると判定された場合は前記面交差判定を実行せずに前記バウンディングボックスと前記光線とは交差すると判定し、前記内包判定によって前記視点が前記バウンディングボックスに内包されないと判定された場合は前記面交差判定を実行することを特徴とする画像生成装置。
【請求項６】
請求項５に記載の画像生成装置において、
前記内包判定手段が実行する前記内包判定は、前記負頂点を共有する３面をそれぞれ含む３つの無限平面について、各無限平面によって２つに分けられる領域のうち前記バウンディングボックス側である領域を対象領域にし、該３つの対象領域の積集合で表される領域に前記視点が内包されていれば前記視点は前記バウンディングボックスに内包されていると判定し、前記３つの対象領域の積集合で表される領域に前記視点が内包されていなければ、前記視点は前記バウンディングボックスに内包されていないと判定することを特徴とする画像生成装置。
【請求項７】
請求項６に記載の画像生成装置において、
前記制御手段は、前記内包判定手段が前記内包判定で用いた前記３つの対象領域のうち前記視点を含まなかった対象領域を選択し、該対象領域を分けている無限平面に含まれる面に対してのみ、前記面交差判定を実行することを特徴とする画像生成装置。
【請求項８】
請求項１又は、請求項４から請求項６の何れかに記載の画像生成装置において、
前記光線を含む直線に関して、視点から見て前記光線のベクトル方向の無限遠を正無限、反対方向の無限遠を負無限とした場合、前記バウンディングボックスの各頂点から前記直線上に垂線を下ろした場合の交点位置が最も正無限方向に位置する頂点を正頂点、最も負無限方向に位置する頂点を負頂点とした時、
前記制御手段は、前記面交差判定において負頂点を共有する３面を選択して判定することを特徴とする画像生成装置。
【請求項９】
視点からスクリーン上の点を通って更に延びる光線と３次元物体との交点を求め、該交点の光の状態を算出して前記スクリーン上の点の色を決定する光線追跡法を用いて３次元物体の２次元画像を生成する際に、前記３次元物体を含む直方体からなるバウンディングボックスを構成する６面の何れかの面と前記光線とが交差するか否かを判定する面交差判定を実行して、前記光線と交差すると判定された面を持つ前記バウンディングボックスを選択し、該バウンディングボックスに含まれる前記３次元物体に対してのみ前記光線との交点を求める交点計算を実行する制御手段を備える画像生成装置において、
前記光線を含む直線に関して、視点から見て前記光線のベクトル方向の無限遠を正無限、反対方向の無限遠を負無限とした場合、前記バウンディングボックスの各頂点から前記直線上に垂線を下ろした場合の交点位置が最も正無限方向に位置する頂点を正頂点、最も負無限方向に位置する頂点を負頂点とし、
前記制御手段は、前記面交差判定において正頂点を共有する３面を選択して判定することを特徴とする画像生成装置。
【請求項１０】
請求項９に記載の画像生成装置において、
更に、対象としている前記バウンディングボックスの頂点のうち正頂点を共有する３つの面をそれぞれ含む３つの無限平面について、各無限平面によって２つに分けられる領域のうち該無限平面自体を含まず且つ前記バウンディングボックス側でない領域の和集合で表される領域を不交差領域とし、前記視点が前記不交差領域に含まれるか否かを判定する不交差判定を前記制御手段の指令により実行する不交差判定手段を備え、
前記制御手段は、まず前記不交差判定手段に前記不交差判定を実行させ、該判定によって前記視点が前記不交差領域に含まれないと判定された場合のみ前記面交差判定を実行して前記バウンディングボックスと前記視点とが交差するか否かを判定し、前記不交差判定によって前記視点が前記不交差領域に含まれると判定された場合は前記面交差判定を実行せずに前記バウンディングボックスと前記光線とは交差しないと判定することを特徴とする画像生成装置。
【請求項１１】
請求項１から請求項１０の何れかに記載の画像生成装置において、
前記制御手段は、前記面交差判定を実行する際に対象の面を含む無限平面との交点を求め、該交点が以下に示す非交差部分平面に存在するか否かを判定し、前記交点が前記非交差部分平面に存在した場合は前記バウンディングボックスに対して以降の前記面交差判定を実行せずに前記バウンディングボックスと前記光線とは交差しないと判定することを特徴とする画像生成装置。
前記光線を含む直線に関して、視点から見て前記光線のベクトル方向の無限遠を正無限、反対方向の無限遠を負無限とした場合、前記バウンディングボックスの各頂点から前記直線上に垂線を下ろした場合の交点位置が最も正無限方向に位置する頂点を正頂点、最も負無限方向に位置する頂点を負頂点とした時、前記バウンディングボックスの対象面において正頂点又は負頂点と対角に位置する頂点を含む２辺について、該頂点と反対側一端を延長し、対象面を含む無限平面を二つの部分平面に分け、該部分平面のうち対象の面を含まない方の部分平面を非交差部分平面とする。
【請求項１２】
請求項１から請求項１０の何れかに記載の画像生成装置において、
前記制御手段は、前記バウンディングボックスの各辺が座標軸と平行になるように前記バウンディングボックスを設定し、前記面交差判定を以下に示すように判定することを特徴とする画像生成装置。
（１）対象面を含む平面がｙｚ平面に平行である場合
対象面の各要素及び交点座標に、前記光線の方向ベクトルのｘ成分を乗じて判定。
（２）対象面を含む平面がｘｚ平面に平行である場合
対象面の各要素及び交点座標に、前記光線の方向ベクトルのｙ成分を乗じて判定。
（３）対象面を含む平面がｘｙ平面に平行である場合
対象面の各要素及び交点座標に、前記光線の方向ベクトルのｚ成分を乗じて判定。
【請求項１３】
視点からスクリーン上の点を通って更に延びる光線と３次元物体との交点を求め、該交点の光の状態を算出して前記スクリーン上の点の色を決定する光線追跡法を用いて３次元物体の２次元画像を生成する際に、前記３次元物体を含む直方体からなるバウンディングボックスを構成する６面の何れかの面と前記光線とが交差するか否かを判定する面交差判定を実行して、前記光線と交差すると判定された面を持つ前記バウンディングボックスを選択し、該バウンディングボックスに含まれる前記３次元物体に対してのみ前記光線との交点を求める交点計算を実行する制御手段を備える画像生成装置において、
前記制御手段は、前記バウンディングボックスの各辺が座標軸と平行になるように前記バウンディングボックスを設定し、前記面交差判定を以下に示すように判定することを特徴とする画像生成装置。
（１）対象面を含む平面がｙｚ平面に平行である場合
対象面の各要素及び交点座標に、前記光線の方向ベクトルのｘ成分を乗じて判定。
（２）対象面を含む平面がｘｚ平面に平行である場合
対象面の各要素及び交点座標に、前記光線の方向ベクトルのｙ成分を乗じて判定。
（３）対象面を含む平面がｘｙ平面に平行である場合
対象面の各要素及び交点座標に、前記光線の方向ベクトルのｚ成分を乗じて判定。
【請求項１４】
視点からスクリーン上の点を通って更に延びる光線と３次元物体との交点を求め、該交点の光の状態を算出して前記スクリーン上の点の色を決定する光線追跡法を用いて３次元物体の２次元画像を生成する際に、前記３次元物体を含む直方体からなるバウンディングボックスを構成する６面の何れかの面と前記光線とが交差するか否かを判定する面交差判定を実行して、前記光線と交差すると判定された面を持つ前記バウンディングボックスを選択し、該バウンディングボックスに含まれる前記３次元物体に対してのみ前記光線との交点を求める交点計算を実行する制御手段を備える画像生成装置において、
更に、前記制御手段から指定される１面を除く５面をそれぞれ含む５つの無限平面について、各無限平面によって２つに分けられる領域のうち該無限平面自体を含まず且つ前記バウンディングボックス側でない領域の和集合を不交差領域とし、前記視点が前記不交差領域に含まれるか否かを判定する不交差判定を前記制御手段の指令により実行する不交差判定手段を備え、
前記制御手段は、前記バウンディングボックスの各辺が座標軸と平行になるように前記バウンディングボックスを設定し、前記光線の方向ベクトルの成分のうち何れか２つの成分がゼロである場合に限り、以下に示す負無限方向に最も位置する１面を指定して前記不交差判定手段に前記不交差判定を実行させ、前記不交差判定によって前記視点が前記不交差領域に含まれると判定された場合は前記バウンディングボックスと前記光線とは交差しないと判定し、前記不交差判定によって前記視点が前記不交差領域に含まれないと判定された場合は前記バウンディングボックスと前記光線とは交差すると判定することを特徴とする画像生成装置。
前記光線を含む直線に関して、視点から見て前記光線のベクトル方向と反対方向の無限遠を負無限とする。
【請求項１５】
コンピュータを、請求項１から請求項１４の何れかに記載の画像生成装置を構成する各手段として機能させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、光線追跡法を用いた画像生成装置等に関する。
【０００２】
【従来の技術】
光線追跡法は、視点から物体の方向に向かって画像を追跡し、光線が物体と交差すればその交点における物体の光の状態を求めて画像面（スクリーン）に投影して、２次元の画像を生成する手法である。光線と物体との交点を求める必要があるがその交点計算に非常に時間がかかるため、様々な高速化手法が考え出されているが、その一つとしてバウンディングボリュームを用いる方法がある。
【０００３】
バウンディングボリュームは１又は複数の物体を内包し、球体や直方体（この場合を特に「バウンディングボックス」と言う）の形状を有している。光線と物体との交点を求める前にその物体を内包するバウンディングボリュームと光線とが交差するか否かを判定し、バウンディングボリュームと光線とが交差する場合のみ光線と物体との交点を求めることによって、不要な交点計算を減らしている。
【０００４】
【発明が解決しようとする課題】
しかし、このような手法を用いてもなお計算量が非常に多く、画像を得るまでに長い時間を要する。このため、特にバウンディングボリュームの一つであるバウンディングボックスを用いた場合、更に計算量を減らして２次元の画像を得るまでの時間を短縮できる画像生成装置及びプログラムを提供することを目的とする。
【０００５】
【課題を解決するための手段及び発明の効果】
上記目的を達成するために為された請求項１に記載の画像生成装置は、制御手段が、面交差判定（３次元物体を含む直方体からなるバウンディングボックスを構成する６面の何れかの面と光線とが交差するか否かの判定）を実行して光線と交差すると判定された面を持つバウンディングボックスを選択し、そのバウンディングボックスに含まれる３次元物体に対してのみ光線との交点を求める交点計算を実行する。また、内包判定手段が内包判定（視点がバウンディングボックスに内包されるか否かの判定）を制御手段の指令により実行する。そして、制御手段は、まず内包判定手段に内包判定を実行させ、その内包判定によって視点がバウンディングボックスに内包されると判定された場合は面交差判定を実行せずにバウンディングボックスと光線とは交差すると判定し、内包判定によって視点が内包されないと判定された場合は面交差判定を実行してバウンディングボックスと視点とが交差するか否かを判定する。
【０００６】
このように、内包判定手段を備えることによって、制御手段は面交差判定を実行せずにバウンディングボックスと光線とが交差することを判定できる場合が生まれる。従って、内包判定に比べ計算コストが大きい面交差判定を制御手段が実行する回数を減少させることができ、画像生成装置によって画像が生成されるまでの時間が短縮される。
【０００７】
尚、制御手段は常に内包判定手段に内包判定を実行させてもよいが、一般的にバウンディングボックスが小さければ小さいほど、視点がバウンディングボックスに内包される確率が減る。このため、ある程度の大きさのバウンディングボックスでないと内包判定を行う計算量に見合う効果が得られない。したがって、請求項２に記載のように、制御手段は、内包判定手段に内包判定を実行させるに先立ち、対象のバウンディングボックスが所定の大きさより大きいか否かを判定し、大きいと判定した場合は内包判定手段に内包判定を実行させ、小さいと判定した場合は内包判定手段に内包判定を実行させずに面交差判定を実行するようにしてもよい。
【０００８】
このようになっていると、内包判定によって計算量が削減される可能性が高い場合のみ内包判定が行われ、内包判定によって計算量が削減される可能性が低い場合は内包判定は行われない。したがって、より計算量の削減につながる。
尚、ここで言うところの所定の大きさは、視点がバウンディングボックスに内包される確率と、面交差判定及び内包判定の計算量とを鑑み、例えば実験によって定めることができる。
【０００９】
一方、請求項３に記載の画像生成装置は、請求項１及び請求項２と同様、制御手段が面交差判定を実行して光線と交差すると判定された面を持つバウンディングボックスを選択し、そのバウンディングボックスに含まれる３次元物体に対してのみ光線との交点を求める交点計算を実行する。また、不交差判定手段が制御手段の指令により次のような不交差判定を行う。それは、対象としているバウンディングボックスの頂点のうち正頂点を共有する３つの面をそれぞれ含む３つの無限平面について、各無限平面によって２つに分けられる領域のうちその無限平面自体を含まず且つ前記バウンディングボックス側でない領域の和集合で表される領域を不交差領域（図５（４）参照）とし、視点が不交差領域に含まれるか否かを判定することである。尚、光線を含む直線に関して、視点から見て光線のベクトル方向の無限遠を正無限、反対方向の無限遠を負無限とした場合、バウンディングボックスの各頂点から直線上に垂線を下ろした場合の交点位置が最も正無限方向に位置する頂点を正頂点、最も負無限方向に位置する頂点を負頂点とした。
【００１０】
そして、制御手段は、まず不交差判定手段に不交差判定を実行させ、その判定によって視点が不交差領域に含まれないと判定された場合のみ面交差判定を実行してバウンディングボックスと視点とが交差するか否かを判定し、不交差判定によって視点が不交差領域に含まれると判定された場合には面交差判定を実行せずにバウンディングボックスと光線とは交差しないと判定する。
【００１１】
このように、不交差判定手段を備えることによって、制御手段は面交差判定を実行せずにバウンディングボックスと光線とが交差しないことを判定できる場合が生まれる。従って、不交差判定に比べ計算コストが大きい面交差判定を制御手段が実行する回数を減少させることができ、画像生成装置によって画像が生成されるまでの時間が短縮される。
【００１２】
尚、正頂点及び負頂点の設定手順は、上述した手順に限定されることはなく、上述した手順によって設定された頂点と実質的に同じ頂点を指すのであれば、どのような手順であってもよい。
また、請求項４に記載の画像生成装置のように不交差判定手段に加えて内包判定手段を備えてもよい。その場合、制御手段は、まず内包判定手段に内包判定を実行させ、その判定によって視点がバウンディングボックスに内包されると判定された場合は他の判定を実行せずにバウンディングボックスと光線とが交差すると判定する。一方、内包判定によって視点がバウンディングボックスに内包されないと判定された場合は続けて不交差判定手段に不交差判定を実行させる。そして、その不交差判定によって視点が不交差判定領域に含まれると判定された場合は光線とバウンディングボックスとは交差しないと判定し、不交差判定によって視点が不交差領域に含まれないと判定された場合は面交差判定を実行してバウンディングボックスと視点とが交差するか否かを判定する。
【００１３】
このようにすれば、内包判定や不交差判定に比べ計算コストが大きい面交差判定を制御手段が実行する回数を更に減少させることができ、画像生成装置によって画像が生成されるまでの時間が短縮される。
尚、不交差判定と内包判定とを実行させる順序は逆であってもよい。すなわち、請求項５に記載の画像生成装置のように、制御手段は、まず不交差判定手段に不交差判定を実行させ、その判定によって視点が不交差領域に含まれると判定された場合は光線とバウンディングボックスとは交差しないと判定する。一方、不交差判定によって視点が不交差領域に含まれないと判定された場合は続けて内包判定手段に内包判定を実行させる。そして、その内包判定によって視点がバウンディングボックスに内包されると判定された場合は面交差判定を実行せずにバウンディングボックスと光線とは交差すると判定し、内包判定によって視点がバウンディングボックスに内包されないと判定された場合は面交差判定を実行してバウンディングボックスと視点とが交差するか否かを判定するようにしてもよい。
【００１４】
このようにしても、請求項４に記載の画像生成装置と同様の作用及び効果が得られる。
尚、請求項５に記載の画像生成装置における内包判定手段が実行する内包判定は、請求項６に記載のようにしてもよい。つまり、負頂点を共有する３面をそれぞれ含む３つの無限平面について、各無限平面によって２つに分けられる領域のうちバウンディングボックス側である領域を対象領域にし、その３つの対象領域の積集合で表される領域（図６（４）参照）に視点が内包されていれば視点はバウンディングボックスに内包されていると判定し、３つの対象領域の積集合で表される領域に視点が内包されていなければ、視点はバウンディングボックスに内包されていないと判定する。
【００１５】
なぜこのように判定してよいかと言うと、内包判定手段が内包判定を実行する段階で、不交差領域に視点が存在しないことが保証されているからである。したがって、上記の内包判定においては不交差領域に視点が存在しない前提で判定を行っている。その結果、画像生成装置によって画像が生成されるまでの時間が短縮される。
【００１６】
更に、請求項７に記載のように、請求項６に記載の画像生成装置において、制御手段は、内包判定手段が内包判定で用いた３つの対象領域のうち視点を含まなかった対象領域を選択し、その対象領域を分けている無限平面に含まれるバウンディングボックスの面に対してのみ、面交差判定を実行するようにしてもよい（図６（１）〜（３）及び図７参照）。
【００１７】
なぜなら、制御手段が面交差判定を実行する段階で、既に実行された不交差判定及び内包判定によって視点が存在し得る領域が推測されるからである。したがって、その領域において光線と交差する可能性のあるバウンディングボックスの面に対してだけ面交差判定が実行されればよい。
【００１８】
このため、面交差判定を実行する面の数を減らすことができて計算量が減少し、画像生成装置によって画像が生成されるまでの時間が短縮される。
尚、請求項１又は、請求項４から請求項６の何れかに記載の画像生成装置においては、制御手段が面交差判定で光線と交差するか否かを判定する面は、請求項８に記載のように、負頂点を共有する３面が選択されてもよい。
【００１９】
なぜなら、光線がバウンディングボックスと交差する時、光線は必ず２面を通過するため、その通過する２面のうちの片方を確認できれば光線とバウンディングボックスとは交差すると言えるからである。したがって上記のようにすることによって、面交差判定において光線と交差するか否かを判定する面が減少し、制御手段が実行する計算量が減る。その結果、画像生成装置によって画像が生成されるまでの時間が短縮される。尚、上記のように３面を選択しなかった場合は、少なくとも５面と面交差判定を行わないと、光線とバウンディングボックスとが交差しないことを判定できない場合があるため、このようにすることによって画像を生成する時間が大きく短縮することができる。
【００２０】
一方、請求項９に記載の画像生成装置のように、制御手段が、面交差判定（３次元物体を含む直方体からなるバウンディングボックスを構成する６面の何れかの面と光線とが交差するか否かの判定）を実行して光線と交差すると判定された面を持つバウンディングボックスを選択し、そのバウンディングボックスに含まれる３次元物体に対してのみ光線との交点を求める交点計算を実行する。そして、
制御手段は、面交差判定において正頂点を共有する３面を選択して判定する。尚、ここで言う正頂点とは、光線を含む直線に関して、視点から見て光線のベクトル方向の無限遠を正無限とした場合、バウンディングボックスの各頂点から直線上に垂線を下ろした場合の交点位置が最も正無限方向に位置する頂点である。
【００２１】
前述した理由により、面交差判定で光線と交差するか否かを判定する面を減らすことができるので、制御手段が実行する計算量が減少し、画像生成装置によって画像が生成されるまでの時間が短縮される。
また、請求項１０に記載のように、請求項９に記載の画像生成装置に、更に不交差判定手段を備え、制御手段は、まず不交差判定手段に不交差判定を実行させ、その判定によって視点が不交差領域に含まれないと判定された場合のみ面交差判定を実行してバウンディングボックスと視点とが交差するか否かを判定し、不交差判定によって視点が不交差領域に含まれると判定された場合は面交差判定を実行せずにバウンディングボックスと光線とは交差しないと判定するようにしてもよい。
【００２２】
このようにすることによって、制御手段は面交差判定を実行せずにバウンディングボックスと光線とが交差しないことを判定できる場合が生まれる。従って、不交差判定に比べ計算コストが大きい面交差判定を制御手段が実行する回数を減少させることができ、画像生成装置によって画像が生成されるまでの時間が短縮される。
【００２３】
また、請求項１１に記載のように、請求項１から請求項１０の何れかに記載の画像生成装置において、制御手段は面交差判定を実行する際に対象の面を含む無限平面との交点を求め、その交点が次に示す非交差部分平面に存在するか否かを判定する。非交差部分平面とは、バウンディングボックスの対象面において正頂点又は負頂点と対角に位置する頂点を含む２辺について、その頂点と反対側一端を延長し、対象面を含む無限平面を二つの部分平面に分け、二つの部分平面のうち対象の面を含まない方の部分平面のことである（図１１参照）。
【００２４】
そして、制御手段は、非交差部分平面に交点が存在すると判定すると、当該バウンディングボックスに対して以降の面交差判定を実行せずに、当該バウンディングボックスと光線とは交差しないと判定する。
なぜなら、非交差部分平面に交点が存在する場合は、光線とバウンディングボックスとが交差することはないからである。したがって、上記のようにすれば、面交差判定を行う面を減らすことができて計算量を減少させることができる。よって、画像生成装置によって画像が生成されるまでの時間が短縮される。
【００２５】
また、制御手段が実行する面交差判定において、対象の面を含む平面と光線との交点座標を求め、その交点座標が対象の面上に存在するか否かを判定するようにしてもよいが、面交差判定では光線と対象の面とが交差するか否かがわかればよく、交点座標を正確に求める必要はない、
このため、請求項１２に記載のように、請求項１から請求項１０の何れかに記載の画像生成装置において、制御手段は、バウンディングボックスの各辺が座標軸と平行になるようにバウンディングボックスを設定し、面交差判定を以下に示すように判定するとよい。
【００２６】
（１）対象面を含む平面がｙｚ平面に平行である場合
対象面の各要素及び交点座標に、前記光線の方向ベクトルのｘ成分を乗じて判定。
（２）対象面を含む平面がｘｚ平面に平行である場合
対象面の各要素及び交点座標に、前記光線の方向ベクトルのｙ成分を乗じて判定。
【００２７】
（３）対象面を含む平面がｘｙ平面に平行である場合
対象面の各要素及び交点座標に、前記光線の方向ベクトルのｚ成分を乗じて判定。
このようにすることにより、除算を行うことなく面交差判定を実行することができる。一般的にコンピュータを用いて計算を実行する場合、除算は他の四則演算に比べ、計算に時間がかかる。そのため、上述したようにすることによって除算を実行することを避けることができ、画像が生成されるまでの時間が短縮された画像生成装置を提供できる。尚、各成分を乗じる場合、その成分の定数倍であっても同様の作用及び効果が得られる。
【００２８】
また、請求項１３に記載の画像生成装置のように、従来の画像生成装置に上記の計算方法を適用させてもよい。
その場合も、同様の作用及び効果を得ることができる。
また、請求項１４に記載の画像生成装置は、これまでと同様、制御手段が面交差判定を実行して光線と交差すると判定された面を持つバウンディングボックスを選択し、そのバウンディングボックスに含まれる３次元物体に対してのみ光線との交点を求める交点計算を実行する。また、制御手段の指令により次のような不交差判定を行う不交差判定手段を備える。それは、制御手段から指定される１面を除く５面をそれぞれ含む５つの無限平面について、各無限平面によって２つに分けられる領域のうちその無限平面自体を含まず且つバウンディングボックス側でない領域の和集合を不交差領域とし、その不交差領域に視点が含まれるか否かを判定する判定である。
【００２９】
そして、制御手段は、バウンディングボックスの各辺が座標軸と平行になるようにバウンディングボックスを設定し、光線の方向ベクトルの成分のうち何れか２つの成分がゼロである場合に限り、負無限方向に最も位置する１面を指定して不交差判定手段に不交差判定を実行させる。その結果、視点が不交差領域に含まれると判定された場合はバウンディングボックスと光線とは交差しないと判定し、視点が不交差領域に含まれないと判定された場合はバウンディングボックスと光線とは交差すると判定する（図１３参照）。尚、光線を含む直線に関して、視点から見て光線のベクトル方向と反対方向の無限遠を負無限とする。
【００３０】
このようにすれば、光線の方向ベクトルの成分のうち何れか２つの成分がゼロである場合、制御手段が面交差判定を実行することなく、簡易な方法で光線とバウンディングボックスとが交差するか否かが判定できる。従って、計算量を減少させることができ、画像生成装置によって画像が生成されるまでの時間が短縮される。
【００３１】
また、請求項１から請求項１４の何れかに記載の画像生成装を構成する各手段は、ハードウェア上で実現されてもよいが、請求項１５に示すように、コンピュータで機能させるためのプログラムとして実現させてもよい。
このようにプログラムで実現させれば、磁気ディスク、光磁気ディスク、メモリカード等のコンピュータが読み取り可能な記録媒体に記録し、必要に応じてコンピュータにロードして起動することにより用いることができる。また、ネットワークを介してロードして起動することにより用いることもできる。
【００３２】
【発明の実施の形態】
以下、本発明の実施形態を図面と共に説明する。
［第１実施形態］
まず、これから使用する３次元モデルについて図１を用いて説明する。符号２で示される外側の立方体は３次元空間を表し、その中に置かれた符号４で示される直方体はバウンディングボックスを表す。そして、符号６で表される頂点が正頂点を表し、符号８で表される頂点が負頂点を表す。尚、符号４で示されるバウンディングボックス内部には図示しない物体要素が含まれる。
【００３３】
また、符号１０で表される点が視点を表し、符号１２で表される矢印が光線を表す。そして、符号１４で表される矢印が光線の方向ベクトルを表す。
尚、バウンディングボックス４、視点１０及び方向ベクトル１４を各々下記のように設定する。
【００３４】
【数１】
0003931691.tif 000002
次に図２のブロック図を用いて画像生成装置２２の構成を説明する。画像生成装置２２は主に、ＣＰＵ２４と、ＲＯＭ２６と、ＲＡＭ２８と、ＶＲＡＭ（ビデオＲＡＭ）３０と、ＩＦ（インタフェース）３２とを備え、これらはバス３４で相互に接続されている。
【００３５】
ＣＰＵ２４（制御手段、内包判定手段、不交差判定手段として機能する）は各種演算や制御を司り、ＲＯＭ２６には光線追跡法によって２次元画像を生成するためのプログラムが格納され、ＲＡＭ２８はプログラムを実行するための一時領域として利用され、ＶＲＡＭ３０には生成結果の２次元画像が格納される。また、ＶＲＡＭ３０に格納された２次元画像は、ＩＦ３２より接続ケーブル３８を介して表示装置３６に伝達され、表示装置３６で画像として表示される。
【００３６】
そして、図示しない操作部を利用者が操作すると、ＣＰＵ２４はＲＯＭ２６からプログラムを読み込み、画像生成処理を開始する。
図３は画像生成処理を表すフローチャートである。本処理が開始されると、まずＳ１００で光線１２を設定する。これは、視点１０を起点とし、２次元画像が投影されると仮定するスクリーン上の一点（ピクセル）を通って更に延びる半直線を設定することである。尚、本ステップでは毎回異なるスクリーン上のピクセルを選択し、全てのピクセルを選択し終えた場合は、光線の設定は行わない。
【００３７】
続いてＳ１１０では、Ｓ１００において光線１２の設定が行われたか否かによって分岐する。光線１２の設定が行われた場合はＳ１２０に進み、光線１２の設定が行われなかった場合は画像生成処理を終了する。
Ｓ１２０では、交差判定対象の設定及び選択を行う。これは、バウンディングボックス４を設定したり、その設定したバウンディングボックス４もしくは直接物体要素を選択することである。尚、バウンディングボックス４は各辺がｘｙｚ直行座標系における各座標軸に対して平行になるように設定する。
【００３８】
続いてＳ１３０で交差判定対象が存在するか否かを判定する。交差判定対象が存在する場合はＳ１４０に進み、交差判定対象が存在しない場合（例えばこの時点で全てのバウンディングボックス４との交差判定を終了してしまった場合等）は、Ｓ１００に戻って光線１２の設定を行う。
【００３９】
Ｓ１４０では、交差判定の対象がバウンディングボックス４か否かを判定する。交差判定の対象がバウンディングボックス４である場合はＳ１５０に進み、交差判定の対象がバウンディングボックス４でない場合、すなわち物体要素である場合はＳ１８０に進む。
【００４０】
Ｓ１５０では、後述するバウンディングボックス交差判定処理を実行する。続くＳ１６０では、Ｓ１５０の結果に基づいて光線１２とバウンディングボックス４とが交差するか否かによって分岐する。光線１２とバウンディングボックス４とが交差しない場合はＳ１７０に進み、光線１２とバウンディングボックス４とが交差する場合はＳ１２０に戻る。
【００４１】
Ｓ１７０では、当該バウンディングボックス４を交差判定対象から除外する。そしてＳ１２０に戻る。
一方、Ｓ１８０では、光線１２と物体要素とが交差するか否かの判定を行う。その結果に応じてＳ１９０で分岐し、交差する場合はＳ２００に進み、交差しない場合はＳ１００に戻る。
【００４２】
Ｓ２００では、光線１２と物体要素との交点を求め、その交点における光の状態を算出する。そして、射影されるスクリーン上のピクセルを設定しＶＲＡＭ３０に画像データを書き込む。書き込が終了するとＳ１００に戻る。尚、ＶＲＡＭ３０に書き込まれた画像データは、ＩＦ３２及び接続ケーブル３８を介して逐一表示装置３６に送られる。
【００４３】
ここで、Ｓ１５０のバウンディングボックス交差判定処理について詳しく説明する。図４はバウンディングボックス交差判定処理を表すフローチャートである。本処理もＣＰＵ２４で起動され実行される。
まず、Ｓ３００で不交差判定を行う。これは、図５（１）、（２）、（３）に各々示すＡｘ領域、Ａｙ領域、Ａｚ領域の和集合である不交差領域Ａ（図５（４））に視点１０が含まれるか否かを判定する。尚、Ａｘ領域は、ｘ＝Ｘｍａｘ平面によって分けられる領域のうち、バウンディングボックス４側ではない領域（ｘ＝Ｘｍａｘ平面を含まず）である。また、Ａｙ領域は、ｙ＝Ｙｍａｘ平面によって分けられる領域のうち、バウンディングボックス４側ではない領域（ｙ＝Ｙｍａｘ平面を含まず）である。また、Ａｚ領域は、ｚ＝Ｚｍｉｎ平面によって分けられる領域のうち、バウンディングボックス４側の領域（ｚ＝Ｚｍｉｎ平面を含まず）である。
【００４４】
続いて、図２のＳ３１０ではＳ３００の結果に応じて分岐する。不交差領域Ａに視点１０が存在する場合は、バウンディングボックス４と光線１２とは交差しないと判定して本処理を終了し、図３のＳ１６０へ移行する。一方、不交差領域Ａに視点１０が存在しない場合は、Ｓ３２０に進む。
【００４５】
Ｓ３２０では内包判定を行う。これは、図６（１）、（２）、（３）に示すＢｘ領域、Ｂｙ領域、Ｂｚ領域の積集合である領域Ｂ（図６（４））に視点１０が含まれるか否かを判定する。尚、Ｂｘ領域は、ｘ＝Ｘｍｉｎ平面によって分けられる領域のうち、バウンディングボックス４側の領域（ｘ＝Ｘｍｉｎ平面を含む）である。また、Ｂｙ領域は、ｙ＝Ｙｍｉｎ平面によって分けられる領域のうち、バウンディングボックス４側の領域（ｙ＝Ｙｍｉｎ平面を含む）である。また、Ｂｚ領域は、ｚ＝Ｚｍａｘ平面によって分けられる領域のうち、バウンディングボックス４側の領域（ｚ＝Ｚｍａｘ平面を含む）である。
【００４６】
前述の不交差判定によって、視点１０は不交差領域Ａに存在しない（すなわち視点は図６（５）の領域に存在する）ことがわかっているため、図６（４）に示す領域Ｂに視点１０が含まれるか否かを判定することによって、視点１０がバウンディングボックス４に内包されるか否かが判定できる（図６（６）参照）。
【００４７】
図４に戻り、Ｓ３３０ではＳ３２０の内包判定の結果によって分岐する。バウンディングボックス４に視点１０が内包されると判定された場合は、バウンディングボックス４と視点１０とは交差すると判定し、画像生成処理に戻る。一方、バウンディングボックス４に視点が内包されないと判定された場合は、Ｓ３４０に進む。
【００４８】
Ｓ３４０では面と光線１２とが交差するか否かを判定する面交差判定を行う。今までの経過から、視点１０の存在領域は不交差領域Ａでない領域からバウンディングボックス４を除いた領域（図７（１）参照）であることがわかる。更にその領域は、光線１２が、バウンディングボックス４の負頂点８を共有する３面のうちいくつの面と交差する可能性があるかによって、３つのグループに分けることができる。すなわち、光線１２が１つの面とのみ交差する可能性があるグループ（図７（２）参照）、光線１２が２つの面と交差する可能性があるグループ（図７（３）参照）、光線１２が３つの面と交差する可能性があるグループ（図７（４）参照）の３つのグループに分けられる。また、この３つのグループのうち何れに視点１０が存在するかは、Ｓ３２０の内包判定を実施した時点で判明している。このため、視点１０がどのグループに属するかに応じて、必要最低限の面とのみ面交差判定を実施する。
【００４９】
続いて、Ｓ３５０ではＳ３４０の結果に応じて分岐する。面と光線１２とが交差する場合はバウンディングボックス４と光線１２とは交差することになり、面と光線１２とが交差しない場合はバウンディングボックス４と光線１２とは交差しないことになる。そして、共にそれぞれの判定結果を保持しつつ画像生成処理に戻る。
【００５０】
尚、Ｓ３４０における面交差判定は以下に示す方法で行う。
例えば対象面がｙｚ平面に平行な面のうちＸ成分が大きい面（図８において符号４０で示す面）であった場合、交点は下記の式１で表される。
【００５１】
【数２】
0003931691.tif 000003
対象面に存在するか否かを判定する判定式は下記の式２で表される。
【００５２】
【数３】
0003931691.tif 000004
ここで、対象面の各要素及び交点座標に、光線を表すベクトルのＸ成分を乗じると下記の式３又は式４になる。
【００５３】
【数４】
0003931691.tif 000005
光線１２を表すベクトルのＸ成分が正の場合は式３のようになり、負の場合は式４のようになる。式３又は式４を用いて面交差判定を行うことにより、式２を用いた場合に比べ乗算回数は増加するが除算はなくなる。尚、図９に乗算及び除算の実行時間を比較した実験結果を示す。実験の概要は、コンピューター上で乱数を発生させてその中から任意の２つの数字を選択し、乗算（０回〜３２回）を行う処理を１０００万回実行。この処理のうち、乗算にかかった時間を測定した。また、同様の処理を乗算の替わりに除算についても行った。
【００５４】
この実験によると、除算の実行時間は乗算の実行時間のおよそ１８倍かかる。したがって、式３を用いて面交差判定を行えば、面交差判定の実行時間は減少すると言える。
このように、バウンディングボックス交差判定処理において、面交差判定に比べ少ない計算量である不交差判定及び内包判定を行うことによってバウンディングボックス４と光線１２とが交差するか否かが判別できる場合ができる。また、これら不交差判定及び内包判定によってバウンディングボックス４と光線１２とが交差するか否かが判別できない場合でも、最小限の面に対してのみ交差判定をおこなうことによって、バウンディングボックス４と光線１２とが交差するか否かが確定できる。
【００５５】
したがって、本画像生成装置２によればバウンディングボックス４と光線１２とが交差するか否かが少ない計算量で判別でき、画像生成処理にかかる時間を短縮できる。
［第２実施形態］
第２実施形態の画像生成装置は、第１実施形態のバウンディングボックス交差判定処理とは別の方法のバウンディングボックス交差判定処理を行う。尚、装置の構成及びその他の処理は第１実施形態と同様であるため説明を省略する。
【００５６】
図１０は、第２実施形態のバウンディングボックス交差判定処理である。まずＳ４００で不交差判定を行う。この不交差判定は、第１実施形態における不交差判定（図４のＳ３００）と同様である。続いて、Ｓ４１０においてＳ４００の結果に応じて分岐する。不交差領域に視点１０が存在する場合は、バウンディングボックス４と視点１０とは交差しないと判定し、画像生成処理に戻る。一方、不交差領域に視点１０が存在しない場合は、Ｓ４２０に進む。
【００５７】
Ｓ４２０では、バウンディングボックス４の面と光線１２とが交差するか否かを判定する面交差判定を行う。この面交差判定は正頂点６を共有する３面に対して行う。その際、対象面において正頂点６と対角に位置する頂点を含む２辺についてその頂点と反対側一端を延長し、対象面を含む平面を２つの部分平面に分ける。そして、２つの部分平面のうち対象面を含まない方の部分平面を非交差部分平面４２（図１１参照）とする。光線１２と対象面を含む平面との交点が、非交差部分平面４２に存在する場合は、以降の面交差判定を実行せずにバウンディングボックス４と光線１２とは交差しないと判定する。
【００５８】
続いて、Ｓ４３０ではＳ４２０の結果に応じて分岐する。面と光線１２とが交差する場合はバウンディングボックス４と光線１２とは交差することになり、面と光線１２とが交差しない場合はバウンディングボックス４と光線１２とは交差しないことになる。そして、共にそれぞれの判定結果を保持しつつ画像生成処理に戻る。
【００５９】
このように、バウンディングボックス交差判定処理において、面交差判定に比べ少ない計算量である不交差判定によってバウンディングボックス４と光線１２とが交差するか否かが判別できる場合ができる。また、これら不交差判定によってバウンディングボックス４と光線１２とが交差するか否かが判別できない場合でも、６面全ての面について面交差判定を行わずに３面について行うだけでよい。そして更に、その３面との面交差判定を実行する途中においても、光線１２と該当面を含む平面との交点を求め、その交点の存在場所によって後の面交差判定を省略できる場合がある。
【００６０】
したがって、本画像生成装置２によればバウンディングボックス４と光線１２とが交差するか否かが少ない計算量で判別でき、画像生成処理にかかる時間を短縮できる。
［第３実施形態］
第３実施形態の画像生成装置は、第１実施形態及び第２実施形態のバウンディングボックス交差判定処理とは別の方法のバウンディングボックス交差判定処理を実行する。尚、装置の構成及びその他の処理は第１実施形態及び第２実施形態と同様であるため説明を省略する。
【００６１】
図１２は、第３実施形態のバウンディングボックス交差判定処理である。まずＳ５００で方向ベクトル１４の成分のうちの何れか２成分がゼロであるか否かを判定する。何れか２成分が０であった場合はＳ５１０に進み、そうでなかった場合はＳ５３０に進む。
【００６２】
Ｓ５１０では不交差判定を実行する。バウンディングボックス４を構成する面のうち負無限方向に最も位置する１面を選択する。そして、選択した１面を除く５面をそれぞれ含む５つの平面について、各平面によって２つに分けられる領域のうちその平面自体を含まず且つバウンディングボックス４側でない領域の和集合を不交差領域Ｃ（図１３参照）とし、視点１０がその不交差領域Ｃに含まれるか否かを判定する。
【００６３】
続いて、Ｓ５２０ではＳ５１０の結果に応じて分岐する。視点１０が不交差領域Ｃに存在する場合はバウンディングボックス４と光線１２とは交差しないと判定し、視点１０が不交差領域Ｃに存在しない場合はバウンディングボックス４と光線１２とは交差すると判定する。そして、共にそれぞれの判定結果を保持しつつ画像生成処理に戻る。
【００６４】
一方Ｓ５３０では面交差判定を実行する。これは、バウンディングボックス４の各面と光線１２とが交差するか否かを判定する。そして、Ｓ５４０でＳ５３０の結果に応じて分岐する。光線１２がバウンディングボックス４の何れかの面と交点を持つ場合はバウンディングボックス４と光線１２とは交差するという判定結果を保持して画像生成処理に戻る。一方、光線１２がバウンディングボックス４の何れの面とも交点を持たない場合はバウンディングボックス４と光線１２とは交差しないという判定結果を保持して画像生成処理に戻る。
【００６５】
このように、方向ベクトル１４の成分のうちの何れか２成分がゼロである場合、バウンディングボックス４と光線１２とが交差するか否かの判定が不交差判定を実行するだけで判定できる。したがって、本画像生成装置２によれば、画像生成処理にかかる時間を短縮できる。
【００６６】
以上、本実施形態を説明したが、本発明は上記の実施形態に限定されるものではなく種々の態様を取ることができる。例えば第３実施形態において、座標軸の何れか１軸が方向ベクトル１４と平行になるように座標系を設定してもよい。このようにすれば、常に方向ベクトル１４の成分のうちの何れか２成分がゼロになり、常に不交差判定が実行できる。
【００６７】
また、第１実施形態においてバウンディングボックス交差判定処理は、不交差判定・内包判定・面交差判定の順に行ったが、内包判定・不交差判定・面交差判定の順に行うことも可能である。更に、内包判定と面交差判定のみを行うようにすることも可能である。このようにしても、従来の画像生成装置より画像生成処理にかかる時間を短縮できる。
【００６８】
また、バウンディングボックス４が所定の大きさより大きい場合だけ内包判定を実行するようにしてもよい。この所定の大きさについては、視点１０がバウンディングボックス４に内包される確率（バウンディングボックス４が占める領域の体積を視点１０が存在する可能性のある領域の体積で割ったもの）と、面交差判定及び内包判定の計算量とを算出し、最も効率的な内包判定の実行可否が判断できるように画像生成処理中に定める方法が考えられる。
【図面の簡単な説明】
【図１】  バウンディングボックスを用いた光線追跡法の３次元モデルの説明図である。
【図２】  画像生成装置のブロック図である。
【図３】  第１実施形態の画像生成処理を表すフローチャートである。
【図４】  第１実施形態のバウンディングボックス交差判定処理を表すフローチャートである。
【図５】  第１実施形態の不交差判定を説明するための３次元モデルである。
【図６】  第１実施形態の内包判定を説明するための３次元モデルである。
【図７】  第１実施形態の面交差判定を説明するための３次元モデルである。
【図８】  第１実施形態の面交差判定一例を説明するための３次元モデルである。
【図９】  乗算と除算の実行時間を比較した実験の概要及び結果である。
【図１０】  第２実施形態のバウンディングボックス交差判定処理を表すフローチャートである。
【図１１】  第２実施形態の面交差判定を説明するための３次元モデルである。
【図１２】  第３実施形態のバウンディングボックス交差判定処理を表すフローチャートである。
【図１３】  第３実施形態の不交差判定を説明するための３次元モデルである。
【符号の説明】
２…３次元空間、４…バウンディングボックス、６…正頂点、８…負頂点、１０…視点、１２…光線、１４…方向ベクトル、２２…画像生成装置、２４…ＣＰＵ、２６…ＲＯＭ、２８…ＲＡＭ、３０…ＶＲＡＭ、３２…ＩＦ、３４…バス、３６…表示装置、３８…接続ケーブル。
【図１】
0003931691.tif 000006
【図２】
0003931691.tif 000007
【図３】
0003931691.tif 000008
【図４】
0003931691.tif 000009
【図５】
0003931691.tif 000010
【図６】
0003931691.tif 000011
【図７】
0003931691.tif 000012
【図８】
0003931691.tif 000013
【図９】
0003931691.tif 000014
【図１０】
0003931691.tif 000015
【図１１】
0003931691.tif 000016
【図１２】
0003931691.tif 000017
【図１３】
0003931691.tif 000018