(57)【要約】【課題】データの転送の重複を避ける。【解決手段】ある平面で光線αβγを用いて交差判定を行う場合、従来における場合では、光線αと交差している３つのボクセル、光線βと交差している３つのボクセル、光線γと交差している３つのボクセルの９個のボクセルの情報が、記憶容量は大きいがデータ転送速度がローカルストレージと比較して劣る主記憶から転送される。すなわち、従来における場合では、図中Ａ，Ｂ，Ｃで示される３つのボクセルが重複して転送処理される。これに対して、高速にアクセス可能であるが記憶容量の少ないローカルストレージに、発生された所定数Ｍ本の光線と交差したボクセルはいずれのボクセルであるかを示す情報を記録し、３本の光線α、β、γのいずれかと交差している合計５つのボクセルの情報がデータ転送速度が劣る主記憶から転送されるので、データ転送回数を減少させることができる。本発明は、画像処理装置に適用できる。【選択図】図１２
2008262493.tif 000002
【特許請求の範囲】
【請求項１】
画像に対して空間分割法を利用した交差判定を実行する情報処理装置において、
前記画像を記憶する第１の記憶手段に記憶されている前記画像に対して空間分割を行い、所定の単位空間を生成する空間分割手段と、
交差判定を実行する対象物と前記空間分割手段により生成された前記単位空間とが交差していることを判定する第１の判定手段と、
前記第１の判定手段による判定結果に基づいて、前記対象物に関して、前記単位空間と交差している前記対象物はいずれであるかを示す交差情報を生成し、前記第１の記憶手段よりもデータ転送速度の速い第２の記憶手段に記憶させる生成手段と、
前記生成手段により生成され前記第２の記憶手段に記憶された前記交差情報に基づいて、前記対象物のうちのいずれかと交差している前記単位空間の空間情報を、前記第１の記憶手段から読み出す読み出し制御手段と、
前記読み出し制御手段により読み出された前記単位空間の前記空間情報を用いて交差判定を実行する第２の判定手段と
を備える情報処理装置。
【請求項２】
前記第１の記憶手段を更に備える
請求項１に記載の情報処理装置。
【請求項３】
前記第２の記憶手段は、前記第１の記憶手段よりも記憶容量が少ない
請求項１に記載の情報処理装置。
【請求項４】
前記第１の判定手段、前記生成手段、前記読み出し制御手段、および、前記第２の判定手段の処理は、複数の演算処理部により分担して実行可能である
請求項１に記載の情報処理装置。
【請求項５】
前記空間分割手段の処理は、複数の前記演算処理部とは異なる主演算処理部により実行され、
前記主演算処理部は、複数の前記演算処理部による前記第１の判定手段、前記生成手段、前記読み出し制御手段、および、前記第２の判定手段の処理の分担を制御する
請求項４に記載の情報処理装置。
【請求項６】
前記第２の記憶手段は、複数の前記演算処理部のそれぞれに設けられている
請求項４に記載の情報処理装置。
【請求項７】
前記対象物をそれぞれ区別する区別情報を付与する区別情報付与手段を更に備え、
前記生成手段は、前記単位空間のそれぞれが、前記区別情報付与手段により付与された前記区別情報により区別可能な前記対象物のそれぞれと交差するかを示すフラグ情報により構成される前記交差情報を生成する
請求項１に記載の情報処理装置。
【請求項８】
空間分割法を利用した交差判定を実行して画像を処理する情報処理装置の情報処理方法において、
前記画像を記憶する第１の記憶部に記憶されている前記画像に対して空間分割を行い、
交差判定を実行する対象物と、生成された前記単位空間とが交差していることを判定し、
判定結果に基づいて、前記対象物に関して、前記単位空間と交差している前記対象物はいずれであるかを示す情報を生成して、前記第１の記憶部よりもデータ転送速度の速い第２の記憶部に記録し、
前記第２の記憶部に記録された前記情報に基づいて、前記対象物のうちのいずれかと交差している前記単位空間の情報を、前記第１の記憶部から読み出し、
前記第１の記憶部から読み出された前記単位空間の情報を用いて交差判定を実行する
ステップを含む情報処理方法。
【請求項９】
空間分割法を利用した交差判定をコンピュータに実行させるためのプログラムであって、
前記画像を記憶する第１の記憶部に記憶されている前記画像に対して空間分割を行い、
交差判定を実行する対象物と、生成された前記単位空間とが交差していることを判定し、
判定結果に基づいて、前記対象物に関して、前記単位空間と交差している前記対象物はいずれであるかを示す情報を生成して、前記第１の記憶部よりもデータ転送速度の速い第２の記憶部への記録を制御し、
前記第２の記憶部に記録された前記情報に基づいて、前記対象物のうちのいずれかと交差している前記単位空間の情報を、前記第１の記憶部から読み出し、
前記第１の記憶部から読み出された前記単位空間の情報を用いて交差判定を実行する
ステップを含む処理をコンピュータに実行させるプログラム。
【請求項１０】
請求項９に記載のプログラムが記録されている記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置および情報処理方法、プログラム、並びに、記録媒体に関し、特に、空間分割法を利用した交差判定を行う場合に用いて好適な、情報処理装置および情報処理方法、プログラム、並びに、記録媒体に関する。
【背景技術】
【０００２】
光の反射や屈折、影などを考慮したリアルな三次元画像を生成するために、レイトレーシング法（光線追跡法または視線探索法とも称される）では、仮想的なスクリーンの各画素に光線を延ばし、一番手前で交差する物体表面の幾何学形状、物理特性により新たな光線を算出し、次々と光線経路を辿ることで前記スクリーンの各画素の色を決定するようになされている。
【０００３】
このとき３次元空間の物体(モデル)の形状はポリゴンと称される多角形面(例えば、三角形)の貼り合わせによって近似される。そして、仮想光線とモデルが交差するか否か、すなわち、仮想光線は、ポリゴンのうちのいずれかと交差するか否かが判定される。しかし、光線とポリゴンとの交差判定には時間がかかり、ポリゴンの数だけ交差判定を実行すると、この交差判定がレイトレーシング処理の大半を占める。そのため、物体の形状が複雑化したり、ポリゴンの数が多くなると処理速度が著しく低下する。
【０００４】
そこで、交差判定の処理速度を上げるため、無駄な交差判定を減少させる空間分割法が知られている。空間分割法は、ポリゴンによって近似された物体が存在する３次元空間を立体要素に分割する方法である。従来の空間分割法としては、例えば、ボクセル分割法、オクトリー分割法などが知られている。
【０００５】
ボクセル分割法は、３次元空間全体をボクセルと呼ばれる立体要素に等分割する方法である。ボクセル分割法では、３次元空間全体が等分割され、３ＤＤＤＡ（three-dimensional digital differential analyzer）法と呼ばれるアルゴリズムによって光線とポリゴンとの交差判定の処理速度を上げることが可能となる。
【０００６】
３ＤＤＤＡ法は、所定の光線が通過した、換言すれば、所定の光線と交差するボクセルを検出するためのアルゴリズムである。
【０００７】
ボクセル分割法を適用した場合の処理について、図１を参照して説明する。ここでは、平面的に図示して説明するが、ボクセル分割法は、３次元空間全体をボクセルと呼ばれる立体要素に等分割するものであり、図中では、３次元空間のうちのある平面を例として説明している。
【０００８】
ボクセル分割法では、まず、立体要素と光線との交差判定が実行される。例えば、図１に示されるように、光線Aと光線Bのそれぞれにおいて、光線が通過するボクセルが判定される。図中、太枠で示されるボクセルが、光線Aまたは光線Bと交差するボクセルである。次に、交差していると判定された立体要素内に含まれるポリゴンと光線との交差判定が行われる。図中、ハッチのかかっている部分が、ポリゴンを含むボクセルである。図１に示される光線Aと光線Bとでは、それぞれ異なるボクセルに関して交差判定が行われる。
【０００９】
図１を用いて説明したように、ボクセル分割法を用いることにより、ポリゴンとの交差判定の処理を最小限に止め、高速処理を実現することができる。
【００１０】
従来、例えば、一般的なパーソナルコンピュータなど、CPU等の内部メモリ(キャッシュメモリ等)を有する情報処理部と主記憶部とを有する装置において、ポリゴンにより構成される３次元空間中のモデルに影を付ける処理が実行される場合、モデル、すなわち、それぞれのポリゴンに関する情報は、主記憶装置に保存された状態において、情報処理部で、その３次元空間がボクセルに分割され、仮想的な光線が発生されて、発生された光線に対して３ＤＤＤＡが実行されて、光線と交差するボクセルが抽出される。そして、光線と交差するボクセルに含まれるポリゴンの情報が情報処理部から読み出されて、光線とポリゴンとの交差判定が行われるようになされていた。
【００１１】
図２のフローチャートを参照して、従来における影生成処理について説明する。
【００１２】
ステップＳ１において、処理を実行する装置は、ポリゴンにより構成された３次元画像データを取得し、主記憶部に記憶する。
【００１３】
ステップＳ２において、情報処理部は、処理を実行する３次元空間を分割し、ボクセルを生成する。
【００１４】
ステップＳ３において、情報処理部は、影を生成するために必要な仮想的な光線を１本(例えば、図１における光線Aまたは光線B)発生させる。
【００１５】
ステップＳ４において、情報処理部は、発生させた光線に対して３ＤＤＤＡを実行し、発生された光線と交差するボクセルを求める。
【００１６】
ステップＳ５において、情報処理部は、３ＤＤＤＡで得られたボクセルのうちの１つを抽出する。
【００１７】
ステップＳ６において、情報処理部は、抽出されたボクセルのデータ（ボクセルに含まれるポリゴンのデータ）を主記憶部から転送して取得する。
【００１８】
ステップＳ７において、情報処理部は、転送されたボクセルに含まれるポリゴンと光線との交差判定を実行する。
【００１９】
ステップＳ８において、情報処理部は、その光線が、転送されたボクセルに含まれるいずれかのポリゴンと交差しているか否かを判断する。
【００２０】
ステップＳ８において、その光線がいずれかのポリゴンと交差していると判断された場合、ステップＳ９において、情報処理部は、光線とポリゴンとの交差している点の輝度計算を実行する。
【００２１】
ステップＳ８において、その光線がいずれかのポリゴンと交差していないと判断された場合、または、ステップＳ９の処理の終了後、ステップＳ１０において、情報処理部は、３ＤＤＤＡで得られた全てのボクセルの処理が終了したか否かを判断する。ステップＳ１０において、全てのボクセルの処理が終了していないと判断された場合、処理は、ステップＳ５に戻り、それ以降の処理が繰り返される。
【００２２】
具体的には、例えば、ステップＳ３において発生された光線が図１の光線Aであるとき、ステップＳ３乃至ステップＳ１０の処理が、図１に示されたボクセルのうちの７ボクセル分繰り返されて、ステップＳ３において発生された光線が図１の光線Bであるとき、ステップＳ３乃至ステップＳ１０の処理が、図１に示されたボクセルのうちの１５ボクセル分繰り返される。
【００２３】
ステップＳ１１において、情報処理部は、交差判定処理が必要な全ての光線の処理が終了したか否かを判断する。ステップＳ１１において、全ての光線の処理が終了していないと判断された場合、処理は、ステップＳ３に戻り、それ以降の処理が繰り返される。
【００２４】
ステップＳ１１において、全ての光線の処理が終了したと判断された場合、ステップＳ１２において、情報処理部は、全ての光線に関する輝度計算結果に基づいて、影の濃度を算出して出力し、処理が終了される。
【００２５】
このような処理により、従来、ボクセル分割法、３ＤＤＤＡ法を用いて、交差判定が実行され、３次元立体画像内のモデルの影が描画されていた。
【００２６】
そして、アンビエントオクルージョン法とは、環境光による自然な影の効果を３次元画像に付与する技法で、影の濃さを求めたい物体表面のある点において、その点を始点とする大量の仮想光線を飛ばし、他の物体と交差した率をもって影の濃さとする技法である。物体と光線の交差判定が出来ればよいため、上述したボクセル分割法などの、レイトレーシング法における高速化技法が使える。
【００２７】
更に、従来、空間分割の方法を改良したり、必要な部分だけ空間分割するための技術が存在する（例えば、特許文献１および特許文献２参照）。
【００２８】
【特許文献１】特開平０６−２２３１９８号公報
【特許文献２】特開昭６３−１９６９８号公報
【００２９】
また、レイトレーシング法により直接画像を生成する分野では、周囲の４本の光線が辿った反射経路を履歴として記録しておき、中央の光線に関する計算を不要にすることができる技術(例えば、特許文献３参照）が存在する。
【００３０】
【特許文献３】特開平０６−１８７４６１号公報
【発明の開示】
【発明が解決しようとする課題】
【００３１】
近年の計算機システムは、メモリ転送速度に対してプロセッサの計算速度が相対的にどんどん速くなってきており、一連の処理を高速化するにあたって、演算速度ではなくメモリ転送にかかる時間がボトルネックになりがちである。
【００３２】
従来のように、光線１本について３ＤＤＤＡによりその光線が通るボクセルを求め、それらのボクセルに含まれるポリゴンのデータを主記憶部からプロセッサ（図２のフローチャートの説明における情報処理部の処理を実行するプロセッサ）に読み込み、ボクセルに含まれるポリゴンと光線の交差判定処理をすると、例えば、図３に示されるように、複数の光線が同一のボクセルを通過している状態では、複数の光線に対するそれぞれの処理において同一のボクセルを何回も転送することとなってしまい、非効率である。このような処理においては、主記憶部からボクセルデータを読み込む際の遅延が処理時間の大半を占めることさえありうる。
【００３３】
また、例えば、画像データ自体が大きかったり、物体の形状が複雑化したり、ポリゴンの数が多くなって、保持しておくべきポリゴンデータが巨大になると、装置内部の主記憶部には収まりきらず、外部記憶装置から必要なデータだけを主記憶部に読み込んで、さらに主記憶部からプロセッサへ転送して処理をするという方法を取らざるを得なくなる。このような処理が行われる場合、外部記憶装置から主記憶部へのデータ転送にかかってしまう時間は主記憶部からプロセッサへのデータ転送にかかる時間の比ではないため、複数の光線の処理において同じボクセルのデータを何回も転送するようになされていた場合、転送時間の遅延問題がより顕著に現れる。
【００３４】
上述した特許文献１および特許文献２においても、主記憶部や外部記憶装置からポリゴンデータを読み込む際の遅延問題を解決する技術は存在しなかった。
【００３５】
また、上述した特許文献３に記載された技術は、整然と等間隔で並んだ画素に対して有効であり、アンビエントオクルージョン法には用いることができなかった。
【００３６】
本発明はこのような状況に鑑みてなされたものであり、空間分割法を利用した交差判定を行う場合に、処理の精度を落とすことなく、分割された空間に関する情報の転送回数を減少させることができるようにするものである。
【課題を解決するための手段】
【００３７】
本発明の一側面の情報処理装置は、画像に対して空間分割法を利用した交差判定を実行する情報処理装置であって、前記画像を記憶する第１の記憶手段に記憶されている前記画像に対して空間分割を行い、所定の単位空間を生成する空間分割手段と、交差判定を実行する対象物と前記空間分割手段により生成された前記単位空間とが交差していることを判定する第１の判定手段と、前記第１の判定手段による判定結果に基づいて、前記対象物に関して、前記単位空間と交差している前記対象物はいずれであるかを示す交差情報を生成し、前記第１の記憶手段よりもデータ転送速度の速い第２の記憶手段に記憶させる生成手段と、前記生成手段により生成され前記第２の記憶手段に記憶された前記交差情報に基づいて、前記対象物のうちのいずれかと交差している前記単位空間の空間情報を、前記第１の記憶手段から読み出す読み出し制御手段と、前記読み出し制御手段により読み出された前記単位空間の前記空間情報を用いて交差判定を実行する第２の判定手段とを備える。
【００３８】
前記第１の記憶手段を更に備えることができる。
【００３９】
前記第２の記憶手段は、前記第１の記憶手段よりも記憶容量が少ないものとすることができる。
【００４０】
前記第１の判定手段、前記生成手段、前記読み出し制御手段、および、前記第２の判定手段の処理は、複数の演算処理部により分担して実行可能であるものとすることができる。
【００４１】
前記空間分割手段の処理は、複数の前記演算処理部とは異なる主演算処理部により実行されるものとすることができ、前記主演算処理部には、複数の前記演算処理部による前記第１の判定手段、前記生成手段、前記読み出し制御手段、および、前記第２の判定手段の処理の分担を制御させるようにすることができる。
【００４２】
前記第２の記憶手段は、複数の前記演算処理部のそれぞれに設けられているものとすることができる。
【００４３】
前記対象物をそれぞれ区別する区別情報を付与する区別情報付与手段を更に備えさせるようにすることができ、前記生成手段には、前記単位空間のそれぞれが、前記区別情報付与手段により付与された前記区別情報により区別可能な前記対象物のそれぞれと交差するかを示すフラグ情報により構成される前記交差情報を生成させるようにすることができる。
【００４４】
本発明の一側面の情報処理方法は、空間分割法を利用した交差判定を実行して画像を処理する情報処理装置の情報処理方法であって、前記画像を記憶する第１の記憶部に記憶されている前記画像に対して空間分割を行い、交差判定を実行する対象物と、生成された前記単位空間とが交差していることを判定し、判定結果に基づいて、前記対象物に関して、前記単位空間と交差している前記対象物はいずれであるかを示す交差情報を生成して、前記第１の記憶部よりもデータ転送速度の速い第２の記憶部に記録し、前記第２の記憶部に記録された前記交差情報に基づいて、前記対象物のうちのいずれかと交差している前記単位空間の空間情報を、前記第１の記憶部から読み出し、前記第１の記憶部から読み出された前記単位空間の前記空間情報を用いて交差判定を実行するステップを含む。
【００４５】
本発明の一側面のプログラムは、空間分割法を利用した交差判定をコンピュータに実行させるためのプログラムであって、前記画像を記憶する第１の記憶部に記憶されている前記画像に対して空間分割を行い、交差判定を実行する対象物と、生成された前記単位空間とが交差していることを判定し、判定結果に基づいて、前記対象物に関して、前記単位空間と交差している前記対象物はいずれであるかを示す交差情報を生成して、前記第１の記憶部よりもデータ転送速度の速い第２の記憶部への記録を制御し、前記第２の記憶部に記録された前記交差情報に基づいて、前記対象物のうちのいずれかと交差している前記単位空間の空間情報を、前記第１の記憶部から読み出し、前記第１の記憶部から読み出された前記単位空間の前記空間情報を用いて交差判定を実行するステップを含む処理をコンピュータに実行させる
【００４６】
本発明の一側面においては、第１の記憶部に記憶されている画像に対して空間分割が行われ、交差判定を実行する対象物と生成された単位空間とが交差していることが判定され、判定結果に基づいて、対象物に関して、単位空間と交差している対象物はいずれであるかを示す交差情報が生成されて、第１の記憶部よりもデータ転送速度の速い第２の記憶部へ記録され、第２の記憶部に記録された交差情報に基づいて、対象物のうちのいずれかと交差している単位空間の空間情報が、第１の記憶部から読み出され、第１の記憶部から読み出された単位空間の空間情報を用いて交差判定が実行される。
【００４７】
ネットワークとは、少なくとも２つの装置が接続され、ある装置から、他の装置に対して、情報の伝達をできるようにした仕組みをいう。ネットワークを介して通信する装置は、独立した装置どうしであっても良いし、１つの装置を構成している内部ブロックどうしであっても良い。
【００４８】
また、通信とは、無線通信および有線通信は勿論、無線通信と有線通信とが混在した通信、即ち、ある区間では無線通信が行われ、他の区間では有線通信が行われるようなものであっても良い。さらに、ある装置から他の装置への通信が有線通信で行われ、他の装置からある装置への通信が無線通信で行われるようなものであっても良い。
【００４９】
情報処理装置は、独立した装置であっても良いし、記録再生装置や画像処理装置の情報処理を行うブロックであっても良い。
【発明の効果】
【００５０】
以上のように、本発明の一側面によれば、交差判定を行うことができ、特に、対象物に関して、単位空間と交差している対象物はいずれであるかを示す交差情報を生成し、その情報を基に、単位空間の空間情報を読みだすようになされているので、対象物のいずれかと交差している単位空間の情報を重複して読み出すことを防ぐことができる。
【発明を実施するための最良の形態】
【００５１】
以下に本発明の実施の形態を説明するが、本発明の構成要件と、明細書または図面に記載の実施の形態との対応関係を例示すると、次のようになる。この記載は、本発明をサポートする実施の形態が、明細書または図面に記載されていることを確認するためのものである。従って、明細書または図面中には記載されているが、本発明の構成要件に対応する実施の形態として、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その構成要件に対応するものではないことを意味するものではない。逆に、実施の形態が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００５２】
本発明の一側面の情報処理装置は、画像に対して空間分割法を利用した交差判定を実行する情報処理装置（例えば、図４の画像処理装置１１または図８の画像処理装置１１１）であって、前記画像を記憶する第１の記憶手段（例えば、図４の記憶部３８、ドライブ４０に装着されているリムーバブルメディア５１、または、通信部３９を介して通信可能な他の装置、もしくは、図８のＸＤＲ−ＲＡＭ１４３、ＨＤＤ１４５、ドライブ１１３に装着されているリムーバブルメディア１１７、または、記憶装置１１２）に記憶されている前記画像に対して空間分割を行い、所定の単位空間（例えば、ボクセル）を生成する空間分割手段（例えば、図６または図９のボクセル生成処理部７５）と、交差判定を実行する対象物（例えば、光線）と前記空間分割手段により生成された前記単位空間とが交差していることを判定する第１の判定手段（例えば、図６または図９の３ＤＤＤＡ演算部７６）と、前記第１の判定手段による判定結果に基づいて、前記対象物に関して、前記単位空間と交差している前記対象物はいずれであるかを示す交差情報（例えば、図７を用いて説明した光線記録データ）を生成し、前記第１の記憶手段よりもデータ転送速度の速い第２の記憶手段（例えば、図４のローカルストレージ６１または図８のローカルストレージ１９１）に記憶させる生成手段（例えば、図６または図９のボクセル通過光線情報記録部７７）と、前記生成手段により生成され前記第２の記憶手段に記憶された前記交差情報に基づいて、前記対象物のうちのいずれかと交差している前記単位空間の空間情報（例えば、対応するボクセルに含まれるポリゴンの情報）を、前記第１の記憶手段から読み出す読み出し制御手段（例えば、図６または図９のボクセル取得制御部７８）と、前記読み出し制御手段により読み出された前記単位空間の前記空間情報を用いて交差判定を実行する第２の判定手段（例えば、図６または図９の交差判定処理部７９）とを備える。
【００５３】
前記第１の記憶手段を更に備えさせるようにすることができる。
【００５４】
前記第２の記憶手段は、前記第１の記憶手段よりも記憶容量が少ないものとすることができる。
【００５５】
前記第１の判定手段、前記生成手段、前記読み出し制御手段、および、前記第２の判定手段の処理は、複数の演算処理部（例えば、図８のサブＣＰＵコア１８２）により分担して実行可能であるものとすることができる。
【００５６】
前記空間分割手段の処理は、複数の前記演算処理部とは異なる主演算処理部（例えば、図８のメインＣＰＵコア１８１）により実行されるものとすることができ、前記主演算処理部は、複数の前記演算処理部による前記第１の判定手段、前記生成手段、前記読み出し制御手段、および、前記第２の判定手段の処理の分担を制御することができる。
【００５７】
前記第２の記憶手段は、複数の前記演算処理部のそれぞれに設けられているものとすることができる。
【００５８】
前記対象物をそれぞれ区別する区別情報（例えば、光線ＩＤ）を付与する区別情報付与手段（例えば、図６または図９の光線発生数係数および光線ＩＤ発行部７４）を更に備えることができ、前記生成手段は、前記単位空間のそれぞれが、前記区別情報付与手段により付与された前記区別情報により区別可能な前記対象物のそれぞれと交差するかを示すフラグ情報により構成される前記交差情報（例えば、図７を用いて説明した光線記録データ）を生成することができる。
【００５９】
本発明の一側面の情報処理方法は、空間分割法を利用した交差判定を実行して画像を処理する情報処理装置（例えば、図４の画像処理装置１１または図８の画像処理装置１１１）の情報処理方法であって、前記画像を記憶する第１の記憶部（例えば、図４の記憶部３８、ドライブ４０に装着されているリムーバブルメディア５１、または、通信部３９を介して通信可能な他の装置、もしくは、図８のＸＤＲ−ＲＡＭ１４３、ＨＤＤ１４５、ドライブ１１３に装着されているリムーバブルメディア１１７、または、記憶装置１１２）に記憶されている前記画像に対して空間分割を行い（例えば、図１０のステップＳ４２の処理）、交差判定を実行する対象物（例えば、光線）と、生成された前記単位空間とが交差していることを判定し（例えば、図１０のステップＳ４５の処理）、判定結果に基づいて、前記対象物に関して、前記単位空間と交差している前記対象物はいずれであるかを示す交差情報（例えば、図７を用いて説明した光線記録データ）を生成して、前記第１の記憶部よりもデータ転送速度の速い第２の記憶部（例えば、図４のローカルストレージ６１または図８のローカルストレージ１９１）に記録し（例えば、図１０のステップＳ４７の処理）、前記第２の記憶部に記録された前記交差情報に基づいて、前記対象物のうちのいずれかと交差している前記単位空間の空間情報（例えば、対応するボクセルに含まれるポリゴンの情報）を、前記第１の記憶部から読み出し（例えば、図１０のステップＳ５１の処理）、前記第１の記憶部から読み出された前記単位空間の前記空間情報を用いて交差判定を実行する（例えば、図１１のステップＳ５５の処理）ステップを含む。
【００６０】
本発明の一側面のプログラムは、空間分割法を利用した交差判定をコンピュータに実行させるためのプログラムであって、前記画像を記憶する第１の記憶部（例えば、図４の記憶部３８、ドライブ４０に装着されているリムーバブルメディア５１、または、通信部３９を介して通信可能な他の装置、もしくは、図８のＸＤＲ−ＲＡＭ１４３、ＨＤＤ１４５、ドライブ１１３に装着されているリムーバブルメディア１１７、または、記憶装置１１２）に記憶されている前記画像に対して空間分割を行い（例えば、図１０のステップＳ４２の処理）、交差判定を実行する対象物（例えば、光線）と、生成された前記単位空間とが交差していることを判定し（例えば、図１０のステップＳ４５の処理）、判定結果に基づいて、前記対象物に関して、前記単位空間と交差している前記対象物はいずれであるかを示す交差情報（例えば、図７を用いて説明した光線記録データ）を生成して、前記第１の記憶部よりもデータ転送速度の速い第２の記憶部（例えば、図４のローカルストレージ６１または図８のローカルストレージ１９１）への記録を制御し（例えば、図１０のステップＳ４７の処理）、前記第２の記憶部に記録された前記交差情報に基づいて、前記対象物のうちのいずれかと交差している前記単位空間の空間情報（例えば、対応するボクセルに含まれるポリゴンの情報）を、前記第１の記憶部から読み出し（例えば、図１０のステップＳ５１の処理）、前記第１の記憶部から読み出された前記単位空間の前記空間情報を用いて交差判定を実行する（例えば、図１１のステップＳ５５の処理）ステップを含む処理をコンピュータに実行させる。
【００６１】
以下、図を参照して、本発明の実施の形態について説明する。
【００６２】
図４は、画像処理装置１１の構成を示すブロック図である。
【００６３】
CPU（Central Processing Unit）３１は、ROM(Read Only Memory)３２に記憶されているプログラム、または、記憶部３８からRAM(Random Access Memory)３３にロードされたプログラムに従って各種の処理を実行する。RAM３３にはまた、CPU３１が各種の処理を実行する上において必要なデータなどが適宜記憶される。
【００６４】
CPU３１の内部には、ローカルストレージ６１が備えられている。ローカルストレージ６１は、後述する記録部３８と比較して、転送速度が高速であるが、記憶容量が比較的少ないメモリである(例えば、容量が256KB程度であり、データ転送速度が51.2GB/s程度であるものとする)。
【００６５】
CPU３１、ROM３２、およびRAM３３は、内部バス３４を介して相互に接続されている。この内部バス３４にはまた、入出力インターフェース３５も接続されている。
【００６６】
入出力インターフェース３５には、キーボード、マウスなどよりなる入力部３６、CRT，LCDなどよりなるディスプレイ、スピーカなどよりなる出力部３７、ハードディスクなどより構成される記憶部３８、並びに、モデム、ターミナルアダプタなどより構成される通信部３９が接続されている。
【００６７】
記憶部３８を構成するハードディスクなどの記録媒体は、上述したローカルストレージ６１と比較して、データ記憶容量は大きいが、通信速度が比較的遅い(例えば、容量が256MB程度であり、データ転送速度が25.6GB/s程度であるものとする)。
【００６８】
通信部３９は、電話回線やCATVを含む各種のネットワークを介しての通信処理を行う。また、通信部３９は、アンテナなどを有し、放送信号を受信することも可能であるものとしてもよい。
【００６９】
入出力インターフェース３５にはまた、必要に応じてドライブ４０が接続され、磁気ディスク、光ディスク、光磁気ディスク、あるいは半導体メモリなどによりなるリムーバブルメディア５１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部３８にインストールされる。また、リムーバブルメディア５１に記録されている情報がＣＰＵ３１の処理に用いられる場合もある。
【００７０】
次に、画像処理装置１１の動作について説明する。
【００７１】
記憶部３８を構成するハードディスクなどの記録媒体には、影の描画処理を施したい３次元画像データを構成するポリゴンデータが記録されている。
【００７２】
ＣＰＵ３１は、ユーザの操作入力、または、設定に基づいて、影の描画処理を施したい３次元画像データにおける３次元空間をボクセルに分割する。ＣＰＵ３１により、対応する３次元画像データがボクセルに分割された場合、ローカルストレージ６１には、空間の分割数、ボクセルの絶対座標、ボクセルの幅・高さ・奥行き(例えば、対応する空間がx y z 軸それぞれ5分割されたことを示す情報)などが保存される。記憶部３８を構成するハードディスクなどの記録媒体に記憶されているこれらのポリゴンデータは、分割されたいずれのボクセルに属するかによって分けることが可能である。
【００７３】
そして、ＣＰＵ３１は、３ＤＤＤＡを実行して、光線と交差するボクセルを抽出する処理を実行する。ＣＰＵ３１は、従来における場合のように、１本ずつの光線を発生させて、その光線と交差するボクセルを求めて、そのボクセルのデータをその都度転送させるのではなく、複数の光線を順次発生させ、それぞれの光線に対して３ＤＤＤＡを実行して、それらの光線と交差したボクセルはいずれのボクセルであるかをローカルストレージ６１に記録しておき、所定数の光線についての処理が終了した後、所定数の光線のうちのいずれかと交差したボクセルに含まれるポリゴンデータの転送処理を実行することにより、例えば、図５に示される、複数の光線が交差しているボクセル（図中太線で示されるボクセル）のデータの転送回数を、従来においてはボクセルに交差している光線の回数だけ転送されていたものを、重複を避けて１回だけ転送されるようにし、その回数を削減することができるようになされている。
【００７４】
また、順次発生される光線の数の上限は、ローカルストレージ６１の記録容量と、ローカルストレージ６１に記録される情報の形式により決められる。すなわち、ローカルストレージ６１の容量があまり大きくなく、発生された所定数の光線と交差したボクセルはいずれのボクセルであるかを示す情報を記録するための領域を多く取ることができない場合、１度に連続して発生可能な光線の上限数は小さくなる。しかしながら、この上限数は、描画される影の精度にはかかわらない。なぜなら、１陰影計算点につき発生される光線数を多くして、描画される影の精度を向上させたい場合は、処理を繰り返せばよいのである。例えば、１陰影計算点につき５００光線を仮想的に発生させて、交差判定を実施し、輝度計算を行うようになされている場合に、１度に連続して発生される光線の数の上限が５０本であり、５０本のそれぞれの光線に対して３ＤＤＤＡを実行して、それらの光線と交差したボクセルはいずれのボクセルであるかをローカルストレージ６１に記録するようになされている場合、この記録処理と、記録された情報に基づく複数のボクセルに関するデータの転送処理は、１陰影計算点につき１０回繰り返される。
【００７５】
したがって、例えば、５０光線など、影を描画するための仮想的な所定の数の光線データに関する情報も、ローカルストレージ６１に保存される。
【００７６】
そして、ＣＰＵ３１は、ローカルストレージ６１に記録された情報に基づいて、所定数、例えば、Ｍ本の光線のうちのいずれかが交差したボクセルについて、そのボクセルに含まれるポリゴンの情報を記憶部３８から読み出して、入出力インターフェース３５および内部バス３４を介して取得する。
【００７７】
そして、ＣＰＵ３１は、所定数Ｍ本の光線のうちのいずれかが交差したボクセルについて、そのボクセルに含まれるポリゴンのうちのいずれかが、そのボクセルと交差した光線のうちのいずれかと交差するかを交差判定し、交差すると判断された場合、その交点の輝度を計算する。
【００７８】
すなわち、複数の光線が同一ボクセルを通過するとき、従来の手法においては、そのボクセルに含まれるポリゴンデータの転送が複数回、すなわち、そのボクセルを通過する光線の数だけ実行されていたが、この方法を用いることにより、所定数の光線のうち重複して光線が通過しているボクセルに含まれるポリゴンデータの転送を１回だけにすることができる。
【００７９】
換言すれば、画像処理装置１１においては、高速にアクセス可能であるが記憶容量の少ないローカルストレージ６１に、発生された所定数Ｍ本の光線と交差したボクセルはいずれのボクセルであるかを示す情報を記録するようにすることにより、所定数Ｍ本の光線との３ＤＤＤＡ処理の結果得られるボクセルに関するデータの転送は重複することがなくなるので、記憶容量は大きいが、データ転送速度がローカルストレージ６１と比較して劣る記憶部３８(例えば、ハードディスクなど)、または、外部の装置からのデータ転送回数を減少させることができる。
【００８０】
このようにすることにより、ボクセル分割法などの空間分割法を用い、交差判定を行う画像処理（ここでは、レイトレーシング法をベースとした３次元画像生成）において、記憶部３８(例えば、ハードディスクなど)、または、外部の装置からの同一のボクセルに含まれるポリゴンデータの転送回数を減らすことができるため、演算処理全体にかかる時間の短縮化が図れる。
【００８１】
したがって、時間の短縮化により、同じ画像を同じ時間で生成するために必要な計算機の数も減り、消費電力も削減することができ、結果としてコスト削減につながる。
【００８２】
図６は、複数の光線をまとめて発生させ、複数光線のうちのいずれかと交差したボクセルのデータの転送処理を実行する場合のＣＰＵ３１が有する機能を示す機能ブロック図である。
【００８３】
ＣＰＵ３１は、影情報算出座標制御部７１、光線発生数管理部７２、光線発生処理部７３、光線発生数係数および光線ＩＤ発行部７４、ボクセル生成処理部７５、３ＤＤＤＡ演算部７６、ボクセル通過光線情報記録部７７、ボクセル取得制御部７８、交差判定処理部７９、輝度計算部８０、影濃度計算部８１、および、計算結果出力制御部８２の機能を有している。
【００８４】
影情報算出座標制御部７１は、入力部３６から入力されたユーザの操作入力や、３次元画像に影を描画する処理を実行させる上位のアプリケーション(例えば、画像処理ソフトウェアや動画像処理ソフトウェアなど)からの指令に基づいて、３次元画像の影情報を算出するために、３次元画像のいずれの位置から光線を発生するかを制御して、光線発生数管理部７２による光線の発生を制御するとともに、３次元画像のいずれの画素の影濃度を算出するかを制御し、計算結果出力制御部８２に供給された影濃度の計算結果をまとめ、１枚の３次元画像の影情報を算出する処理を制御する。
【００８５】
光線発生数管理部７２は、入力部３６から入力されたユーザの操作入力や、３次元画像に影を描画する処理を実行させる上位のアプリケーションからの指令に基づいて、光線発生処理部７３による光線の発生数を管理する。例えば、所定の座標から５００本の光線の発生が必要であるとき、光線発生数管理部７２は、光線発生処理部７３による所定の座標からの５００本の光線の発生を制御するのであるが、上述したように、ボクセルデータの転送を実行するにあたって一度に発生される光線数は、ローカルストレージ６１の記憶容量などによって決められる。そこで、光線発生数管理部７２は、１陰影計算点につき発生される合計の光線数と、一度に発生される光線数を管理し、光線発生処理部７３を制御する。
【００８６】
光線発生処理部７３は、光線発生数管理部７２の制御に基づいて、仮想的な３次元空間内の仮想的な光線の発生処理を行う。
【００８７】
光線発生数係数および光線ＩＤ発行部７４は、光線発生処理部７３により発生される光線の数を計数するとともに、それらの光線が通過したボクセルの情報を記録しておくために、それぞれの光線を区別する光線ＩＤを発行する。
【００８８】
ボクセル生成処理部７５は、処理する３次元画像を所定のボクセルに分割する処理を実行する。
【００８９】
３ＤＤＤＡ演算部７６は、光線発生処理部７３により発生された光線と交差するボクセルを検出し、検出結果をボクセル通過光線情報記録部７７に供給する。
【００９０】
ボクセル通過光線情報記録部７７は、３ＤＤＤＡ演算部７６から供給された、光線発生処理部７３により発生された光線と交差するボクセルの検出結果に基づいて、複数（Ｍ本）の光線のいずれかが通過したボクセルと、そのボクセルを通過した光線の光線ＩＤの情報を記録する。
【００９１】
ボクセル通過光線情報記録部７７は、複数（Ｍ本）の光線のいずれかが通過したボクセルと、そのボクセルを通過した光線の光線ＩＤの情報を記録することが可能であれば、いずれの形式で情報を記録しても良い。例えば、ボクセル通過光線情報記録部７７は、図７に示されるように、３次元画像のそれぞれのボクセルにおいて、複数（Ｍ本）の光線のうち、そのボクセルを通過した光線の光線ＩＤが分かるように、ボクセル数×一度に処理される光線数（Ｍ本）のフラグを用意しておき、それぞれのボクセルを通過した光線の光線ＩＤに対応するフラグを１にセットするものとすることができる。この情報を、以下、光線記録データと称するものとする。
【００９２】
すなわち、光線記録データの記録のために必要なデータ容量は、「ｘ軸方向のボクセル分割数×ｙ軸方向のボクセル分割数×ｚ軸方向のボクセル分割数×一度に処理する光線数」で表される。例えば、一度に処理する光線の本数が６４本であり、処理を実行する３次元画像空間が５×５×５のボクセルに分割されているとき、光線記録データに必要なデータ容量は、8000bit＝1000byteとなり、この値は通常物体を構成するポリゴンを表すのに必要な記憶容量に比べて十分小さく、ローカルストレージ６１が他の処理に用いられる情報を記録するために必要なデータ容量を鑑みても、十分小さい値である。
【００９３】
ボクセル通過光線情報記録部７７は、複数（Ｍ本）の光線の発生が終了した後、記録された光線記録データを、ボクセル取得制御部７８および交差判定処理部７９に供給する。
【００９４】
ボクセル取得制御部７８は、例えば、図７を用いて説明したような光線記録データに基づいて、複数（Ｍ本）の光線のいずれかが通過したボクセルの情報を取得する。画像処理装置１１において、ボクセルの情報が記憶部３８に記憶されている場合、ボクセル取得制御部７８は、光線記録データを参照して、内部バス３４および入出力インターフェース３５を介して、記憶部３８から複数（Ｍ本）の光線のいずれかが通過したボクセルの情報を取得する。また、例えば、ボクセルの情報がドライブ４０に装着されたリムーバブルメディア５１や、外部の他の装置に記録されている場合、ボクセル取得制御部７８は、内部バス３４、入出力インターフェース３５、および、ドライブ４０を介してリムーバブルメディア５１から、または、内部バス３４、入出力インターフェース３５、および、通信部３９を介して、図示しない他の装置から、複数（Ｍ本）の光線のいずれかが通過したボクセルの情報を取得する。
【００９５】
また、ボクセル取得制御部７８は、複数（Ｍ本）の光線のいずれかが通過し、かつ、ポリゴンのデータを含むボクセルの情報を取得するものとしてもよい。
【００９６】
交差判定処理部７９は、例えば、図７を用いて説明した光線記録データに基づいて、所定のボクセルを通過した光線のそれぞれが、そのボクセルに含まれるいずれかのポリゴンと交差しているか否かの交差判定を実行し、交差判定結果を輝度計算部８０に供給する。
【００９７】
輝度計算部８０は、交差判定処理部７９による交差判定結果に基づいて、光線とポリゴンとの交差している点の輝度計算を実行し、輝度計算結果を影濃度計算部８１に供給する。
【００９８】
影濃度計算部８１は、輝度計算部８０から供給された光線とポリゴンとの交差している点の輝度計算に基づいて、発生される光線全体による各座標の影濃度の計算を実行する。
【００９９】
計算結果出力制御部８２は、影情報算出座標制御部７１の制御にしたがって、３次元画像のそれぞれの画素の影濃度を算出する結果に基づいて、１枚の３次元画像の影情報を算出し、出力する。
【０１００】
更に、上述した一連の処理は、複数のサブＣＰＵコアを用いて並列に実行させることによっても実現可能である。この場合、例えば、図４を用いて説明した画像処理装置１１は、図８に示されるような画像処理装置１１１を含む画像処理システムにより構成される。
【０１０１】
図８に示すように、図４の画像処理装置１１に対応する画像処理システムは、画像処理装置１１１、画像処理装置１１１とＰＣＩバス１０１によって接続された、記憶装置１１２およびドライブ１１３、並びに、ユーザがこれらに対する操作入力を行うためのマウス１１４、キーボード１１５、および、操作コントローラ１１６から構成されている。
【０１０２】
この画像処理システムでは、記憶装置１１２に取り込まれた動画または静止画に影を施す処理などをはじめとした画像処理を行うことができ、その結果得られた処理済の動画または静止画を、ＲＡＩＤ（Redundant Arrays of Independent Disks）でなる大容量の記憶装置１１２に蓄積したり、ドライブ１１３の処理によりリムーバブルディスク１１７に記録し得るようになされている。また、ドライブ１１３に装着されたリムーバブルディスク１１７に記録された動画または静止画についても、記憶装置１１２に取り込んだり、画像処理装置１１１に読み込まれることが可能なようになされている。
【０１０３】
画像処理装置１１１は、マイクロプロセッサ１４１、ＧＰＵ（Graphics Processing Unit）１４２、ＸＤＲ（Extreme Data Rate）−ＲＡＭ１４３、サウスブリッジ１４４、ＨＤＤ１４５、ＵＳＢインターフェース１４６、および、サウンド入出力コーディック１４７を含んで構成されている。
【０１０４】
画像処理装置１１１においては、マイクロプロセッサ１４１に対してＧＰＵ１４２、ＸＤＲ−ＲＡＭは、ＨＤＤ１４５、ＵＳＢインターフェース１４６、および、サウンド入出力コーディック１４７が接続されている。このサウンド入出力コーディック１４７にはスピーカ１２１が接続されている。また、ＧＰＵ１４２にはディスプレイ１２２が接続されている。
【０１０５】
サウスブリッジ１４４には、ＰＣＩバス１０１を介して、マウス１１４、キーボード１１５、記憶装置１１２、ドライブ１１３、および、操作コントローラ１１６が接続されている。
【０１０６】
マウス１１４およびキーボード１１５、並びに、操作コントローラ１１６は、ユーザの操作入力を受け、ＰＣＩバス１０１およびサウスブリッジ１４４を介して、ユーザの操作入力の内容を示す信号を、マイクロプロセッサ１４１に供給する。記憶装置１１２は、所定のデータを記録または再生できるようになされている。
【０１０７】
マイクロプロセッサ１４１は、汎用のメインＣＰＵコア１８１と、メインＣＰＵコア１８１に内部バス１８５を介して接続された複数（この場合８個）のＲＩＳＣ（Reduced Instruction Set Computer）タイプの信号処理プロセッサ（以下、これをサブＣＰＵコアと称する）１８２−１乃至１８２−８と、例えば２５６[MByte]の容量を持つＸＤＲ−ＲＡＭ１４３に対するメモリコントロールを行うメモリコントローラ１８３と、サウスブリッジ１４４との間でデータの入出力を管理するＩ／Ｏ（In/Out）コントローラ１８４とが１チップに集積されたマルチコア構成を有しており、例えば、動作周波数４[GHz]を実現している。
【０１０８】
マイクロプロセッサ１４１は、起動時、ＨＤＤ１４５に格納された制御プログラムに基づき、ＨＤＤ１４５に格納されている必要なアプリケーションプログラムを読み出してＸＤＲ−ＲＡＭ１４３に展開し、この後このアプリケーションプログラムおよびオペレータ操作に基づいて必要な制御処理を実行する。
【０１０９】
メインＣＰＵコア１８１は、ＯＳ（Operating System）等の基本プログラムや、サブＣＰＵコア１８２−１乃至１８２−８を含むマイクロプロセッサ１４１の全体の制御、および、計算処理のうちの一部を実行する。
【０１１０】
サブＣＰＵコア１８２−１乃至１８２−８は、それぞれ、ローカルストレージ１９１−１乃至１９１−８を有しており、メインＣＰＵコア１８１の制御に基づいて、割り当てられた画像処理に関する計算処理を実行する。ローカルストレージ１９１−１乃至１９１−８は、後述するＸＤＲ−ＲＡＭ１４３やＨＤＤ１４５と比較して、転送速度が高速であるが、記憶容量が少ないメモリである(例えば、容量が256KB程度であり、データ転送速度が51.2GB/s程度であるものとする)。
【０１１１】
以下、サブＣＰＵコア１８２−１乃至１８２−８を個々に区別する必要のない場合、単にサブＣＰＵコア１８２と称し、ローカルストレージ１９１−１乃至１９１−８を個々に区別する必要のない場合、単にローカルストレージ１９１と称するものとする。
【０１１２】
この画像処理装置１１１のマイクロプロセッサ１４１は、例えば、上述したボクセル分割法、３ＤＤＤＡ、および、交差判定を実行して、３次元画像の各点の影の濃度を算出し、影を描画する処理を実行して、得られた画像(動画像または静止画)を、サウスブリッジ１４４を介して、ＨＤＤ１４５に供給して記憶させたり、処理中の画像、または、処理の結果得られた画像(動画像または静止画)を、ＧＰＵ１４２へデータ転送して、ディスプレイ１２２に表示させることができる。
【０１１３】
特に、マイクロプロセッサ１４１では、メインＣＰＵコア１８１が、サウスブリッジ１４４を介してマウス１１４、キーボード１１５、または、操作コントローラ１１６から供給された命令を受け付け、その命令に基づいた処理をサブＣＰＵコア１８２−１乃至１８２−８に割り当てたり、ボクセル分割処理やデータの転送処理の管理など、３次元画像全体にかかわる処理を主に分担するようになされており、８個のサブＣＰＵコア１８２−１乃至１８２−８のそれぞれが、３ＤＤＤＡ、および、交差判定、並びに、交差判定結果を用いた輝度計算処理などを実行する役割をそれぞれ担うようになされている。
【０１１４】
８個のサブＣＰＵコア１８２−１乃至１８２−８は、異なる陰影計算点におけるそれぞれの３ＤＤＤＡ、および、交差判定を同時並列的に実行することが可能であるとともに、例えば、１陰影計算点において陰影を計算するために発生される光線数の設定が、１度に演算処理される光線数Ｍ本よりも多い場合、同一の陰影計算点における異なる光線群に対する３ＤＤＤＡ、および、交差判定を同時並列的に実行することが可能である。また、同一の陰影計算点における同一の光線群に対する３ＤＤＤＡ、および、交差判定を、同一のサブＣＰＵコア１８２で実行するものとしても良いし、３ＤＤＤＡと交差判定とを異なるサブＣＰＵコア１８２で実行するものとしても良い。
【０１１５】
このように、マイクロプロセッサ１４１は、８個のサブＣＰＵコア１８２−１乃至１８２−８によって同時並列的に演算処理を実行することができるようになされている。
【０１１６】
ＸＤＲ−ＲＡＭ１４３は、３次元画像のポリゴンの情報を記録することができ、上述したローカルストレージ１９１と比較して、データ記憶容量は大きいが、通信速度が比較的遅い。ここでは、ＸＤＲ−ＲＡＭ１４３は、例えば、容量が256MB程度であり、データ転送速度が25.6GB/s程度であるものとする。ＸＤＲ−ＲＡＭ１４３は、８つのサブCPUコア１８２とメインCPUコア１８１で共有されるので、メインCPUコアの影響は無視できるほど小さいとして、８つのサブCPUコア１８２のそれぞれとの間におけるデータ転送速度は、3.2GB/sとなる。
【０１１７】
そして、ＧＰＵ１４２は、例えば、ディスプレイ１２２に表示する画像をディスプレイ１２２に表示するときの座標変換計算処理や、表示される画像に対する拡大・縮小処理等、画像の表示に関する機能を司り、マイクロプロセッサ１４１の処理負担を軽減させるようになされている。
【０１１８】
また、マイクロプロセッサ１４１は、処理される画像とともに再生される音声データが存在する場合、その音声データに対して音声ミキシング処理を施し、その結果得られた編集音声データを、サウスブリッジ１４４およびサウンド入出力コーディック１４７を介して、スピーカ１２１へ送出することにより、音声信号に基づく音声をスピーカ１２１から出力させることもできる。
【０１１９】
次に、画像処理装置１１１の動作について説明する。
【０１２０】
ＸＤＲ−ＲＡＭ１４３には、影の描画処理を施したい３次元画像データを構成するポリゴンデータが記録されている。例えば、３次元画像データのデータ量が非常に大きな場合など、３次元画像データのうちの一部または全部は、更にデータ容量が大きいがデータ転送速度が遅い、ＨＤＤ１４５や記憶装置１１２に記憶されている場合もあるし、ドライブ１１３に装着されたリムーバブルディスク１１７に記録されている場合もある。
【０１２１】
マイクロプロセッサ１４１のメインＣＰＵコア１８１は、サウスブリッジ１４４を介してマウス１１４、キーボード１１５、または、操作コントローラ１１６から供給された命令を受け付け、影の描画処理を施したい３次元画像データにおける３次元空間をボクセルに分割する。メインＣＰＵコア１８１により、対応する３次元画像データがボクセルに分割された場合、メインＣＰＵコア１８１の内部のキャッシュメモリには、空間の分割数、ボクセルの絶対座標、ボクセルの幅・高さ・奥行き(例えば、対応する空間がx y z 軸それぞれ5分割されたことを示す情報)などが保存される。
【０１２２】
メインＣＰＵコア１８１は、３次元画像データに陰の描画を行うために必要な３ＤＤＤＡ、および、交差判定を、サブＣＰＵコア１８２−１乃至１８２−８に割り当てるとともに、処理に必要な情報を、そのサブＣＰＵコア１８２が内部に有するローカルストレージ１９１に供給する。
【０１２３】
３ＤＤＤＡ処理を割り当てられたサブＣＰＵコア１８２は、複数の光線を順次発生させ、それぞれの光線に対して３ＤＤＤＡを実行して、それらの光線と交差したボクセルはいずれのボクセルであるかをローカルストレージ１９１に記録し、例えば、図７を用いて説明したような光線記録データを生成する。
【０１２４】
３ＤＤＤＡ処理を割り当てられたサブＣＰＵコア１８２が、同一の陰影計算点における同一の光線群に対する交差判定を行うようになされていた場合、そのサブＣＰＵコア１８２は、光線記録データを基に、Ｍ本の光線のうちのいずれかが交差したボクセルについて、そのボクセルに含まれるポリゴンの情報をＸＤＲ−ＲＡＭ１４３から読み出して、データバス１６２およびメモリコントローラ１８３を介して取得する。そして、そのサブＣＰＵコア１８２は、所定数Ｍ本の光線のうちのいずれかが交差したボクセルについて、そのボクセルに含まれるポリゴンのうちのいずれかが、そのボクセルと交差した光線のうちのいずれかと交差するかを交差判定し、交差すると判断された場合、その交点の輝度を計算する。
【０１２５】
３ＤＤＤＡ処理を割り当てられたサブＣＰＵコア１８２とは異なるサブＣＰＵコア１８２が、同一の陰影計算点における同一の光線群に対する交差判定を行うようになされていた場合、そのサブＣＰＵコア１８２は、光線記録データを、交差判定を実行するサブＣＰＵコア１８２に供給する。光線記録データの供給を受けたサブＣＰＵコア１８２は、供給された光線記録データを基に、Ｍ本の光線のうちのいずれかが交差したボクセルについて、そのボクセルに含まれるポリゴンの情報をＸＤＲ−ＲＡＭ１４３から読み出して、データバス１６２およびメモリコントローラ１８３を介して取得し、所定数Ｍ本の光線のうちのいずれかが交差したボクセルについて、そのボクセルに含まれるポリゴンのうちのいずれかが、そのボクセルと交差した光線のうちのいずれかと交差するかを交差判定し、交差すると判断された場合、その交点の輝度を計算する。
【０１２６】
また、サブＣＰＵコア１８２は、Ｍ本の光線のうちのいずれかが交差し、かつ、ポリゴンを有するボクセルについて、そのボクセルに含まれるポリゴンの情報をＸＤＲ−ＲＡＭ１４３から読み出して、データバス１６２およびメモリコントローラ１８３を介して取得し、交差判定を行うようにしても良い。
【０１２７】
なお、処理を施す３次元画像のポリゴンの情報が、ＨＤＤ１４５に記録されていた場合、必要な情報が、ＨＤＤ１４５から読み出されて、サウスブリッジ１４４、Ｉ/Ｏコントローラ１８４、および、内部バス１８５を介して、ＸＤＲ−ＲＡＭ１４３に供給されて記憶される。また、処理を施す３次元画像のポリゴンの情報が、外部の記憶装置１１２やドライブ１１３に装着されたリムーバブルディスク１１７に記憶されている場合、必要な情報が、外部の記憶装置１１２やドライブ１１３に装着されたリムーバブルディスク１１７から読み出されて、ＰＣＩバス１０１、サウスブリッジ１４４、Ｉ/Ｏコントローラ１８４、および、内部バス１８５を介して、ＸＤＲ−ＲＡＭ１４３に供給されて記憶される。
【０１２８】
このようにして、画像処理装置１１１においても、所定の数の光線のうち重複して光線が通過しているボクセルに関する情報の転送を１回だけにすることができる。
【０１２９】
換言すれば、画像処理装置１１１においても、高速にアクセス可能であるが記憶容量の少ないローカルストレージ１９１に、発生された所定数Ｍ本の光線と交差したボクセルはいずれのボクセルであるかを示す情報を記録するようにすることにより、所定数Ｍ本の光線との３ＤＤＤＡ処理の結果得られるボクセルに関する情報の転送は、それぞれ、重複することがなくなるので、記憶容量は大きいがデータ転送速度がローカルストレージ１９１と比較して劣るＸＤＲ−ＲＡＭ１４３、ＨＤＤ１４５、または、外部の記憶装置１１２やドライブ１１３に装着されたリムーバブルディスク１１７からのデータ転送回数を減少させることができる。
【０１３０】
このようにすることにより、ボクセル分割法などの空間分割法を用い、交差判定を行う画像処理（ここでは、レイトレーシング法をベースとした３次元画像生成）において、ＸＤＲ−ＲＡＭ１４３、ＨＤＤ１４５、または、外部の記憶装置１１２やドライブ１１３に装着されたリムーバブルディスク１１７からのポリゴンデータの転送回数を減らすことができるため、演算処理全体にかかる時間の短縮化が図れる。
【０１３１】
したがって、時間の短縮化により、同じ画像を同じ時間で生成するために必要な計算機の数も減り、消費電力も削減することができ、結果としてコスト削減につながる。
【０１３２】
図９は、複数の光線をまとめて発生させ、複数光線のうちのいずれかと交差したボクセルに関する情報の転送処理を実行する場合のＣＰＵ３１が有する機能を示す機能ブロック図である。
【０１３３】
なお、図６における場合と対応する部分には同一の符号を付してあり、その説明は適宜省略する。
【０１３４】
すなわち、メインＣＰＵコア１８１は、図６を用いて説明した、影情報算出座標制御部７１、光線発生数管理部７２、ボクセル生成処理部７５、および、計算結果出力制御部８２の機能を有している。
【０１３５】
そして、３ＤＤＤＡ処理を割り当てられたサブＣＰＵコア１８２とは異なるサブＣＰＵコア１８２が、同一の陰影計算点における同一の光線群に対する交差判定を行うようになされていた場合、３ＤＤＤＡ処理を割り当てられたサブＣＰＵコア１８２−ａは、図６を用いて説明した、光線発生処理部７３、光線発生数係数および光線ＩＤ発行部７４、３ＤＤＤＡ演算部７６、および、ボクセル通過光線情報記録部７７の機能を有しており、交差判定処理を割り当てられたサブＣＰＵコア１８２−ｂは、図６を用いて説明した、ボクセル取得制御部７８、交差判定処理部７９、輝度計算部８０、および、影濃度計算部８１の機能を有している。
【０１３６】
また、３ＤＤＤＡ処理を割り当てられたサブＣＰＵコア１８２が、同一の陰影計算点における同一の光線群に対する交差判定を行うようになされていた場合、そのサブＣＰＵコア１８２―ｃは、図６を用いて説明した、光線発生処理部７３、光線発生数係数および光線ＩＤ発行部７４、３ＤＤＤＡ演算部７６、ボクセル取得制御部７８、交差判定処理部７９、輝度計算部８０、および、影濃度計算部８１の機能を有している。
【０１３７】
上述した一連の処理を画像処理装置１１１の複数のサブＣＰＵコア１８２を用いて並列に実行させるようになされている場合、上述したように、ボクセル分割法などの空間分割法を用い、交差判定を行う画像処理（ここでは、レイトレーシング法をベースとした３次元画像生成）において、ＸＤＲ−ＲＡＭ１４３、ＨＤＤ１４５、または、外部の記憶装置１１２やドライブ１１３に装着されたリムーバブルディスク１１７からのポリゴンデータの転送回数を減らすことができるため、演算処理全体にかかる時間の短縮化が図れ、時間の短縮化により、同じ画像を同じ時間で生成するために必要な計算機の数も減り、消費電力も削減することができ、結果としてコスト削減につながるという効果を有することができ、更に、複数のサブＣＰＵコア１８２に適宜処理を分散させることができるので、演算処理全体にかかる時間の短縮化を更に促進することが可能となる。
【０１３８】
次に、図１０および図１１のフローチャートを参照して、画像処理装置１１または画像処理装置１１１が実行する影生成処理について説明する。
【０１３９】
ステップＳ４１において、画像処理装置１１または画像処理装置１１１は、ポリゴンにより構成された３次元画像データを取得し、主記憶部に記憶する。ここで、主記憶部とは、画像処理装置１１においては、記憶部３８であり、画像処理装置１１１においては、基本的には、ＸＤＲ−ＲＡＭ１４３であり、場合によっては、ＨＤＤ１４５であるものとする。
【０１４０】
ステップＳ４２において、ボクセル生成処理部７５は、ポリゴンにより構成された３次元画像データにおける３次元空間を分割し、ボクセルを生成する。
【０１４１】
ステップＳ４３において、光線発生数係数および光線ＩＤ発行部７４は、光線の発生数NをN＝１とする。
【０１４２】
ステップＳ４４において、光線発生処理部７３は、影を生成するために必要な仮想的な光線のうちのN番目の光線を発生させる。光線発生数係数および光線ＩＤ発行部７４は、Ｎ番目の光線に、所定の繰り返し回数Mだけ発生される光線の中で個別に区別可能なように、ＩＤを付与する。
【０１４３】
ステップＳ４５において、３ＤＤＤＡ演算部７６は、発生させた光線に対して３ＤＤＤＡを実行し、発生された光線と交差するボクセルを求める。
【０１４４】
ステップＳ４６において、ボクセル通過光線情報記録部７７は、３ＤＤＤＡで得られたボクセルのうちの１つを抽出する。
【０１４５】
ステップＳ４７において、ボクセル通過光線情報記録部７７は、ローカルストレージ６１またはローカルストレージ１９１に保持される、例えば、図７を用いて説明した光線記録データに、そのボクセルにN番目の光線が通過することを記録する。
【０１４６】
ステップＳ４８において、ボクセル通過光線情報記録部７７は、３ＤＤＤＡで得られた全てのボクセルの処理が終了したか否かを判断する。ステップＳ４８において、３ＤＤＤＡで得られた全てのボクセルの処理が終了していないと判断された場合、処理は、ステップＳ４６に戻り、それ以降の処理が繰り返される。
【０１４７】
ステップＳ４８において、３ＤＤＤＡで得られた全てのボクセルの処理が終了したと判断された場合、ステップＳ４９において、光線発生数係数および光線ＩＤ発行部７４は、光線の発生数NをN=N+1とする。
【０１４８】
ステップＳ５０において、光線発生数係数および光線ＩＤ発行部７４は、Nの値が所定の繰り返し回数Mを超えたか、または、全ての光線の処理が終了したか否かを判断する。ステップＳ５０において、Nの値が所定の繰り返し回数Mを超えておらず、かつ、全ての光線の処理が終了していないと判断された場合、処理は、ステップＳ４４に戻り、それ以降の処理が繰り返される。
【０１４９】
ステップＳ５０において、Nの値が所定の繰り返し回数Mを超えているか、または、全ての光線の処理が終了したと判断された場合、ステップＳ５１において、ボクセル通過光線情報記録部７７は、例えば、図７を用いて説明した光線記録データを、ボクセル取得制御部７８に供給する。ボクセル取得制御部７８は、光線記録データに基づいて、複数の光線のいずれかの光線が通過しているボクセルを検出する。
【０１５０】
ステップＳ５２において、ボクセル取得制御部７８は、いずれかの光線が通過しているボクセルのうち、ポリゴンを含むボクセルを１つ抽出する。
【０１５１】
ステップＳ５３において、ボクセル取得制御部７８は、抽出されたボクセルに含まれるポリゴンデータを主記憶から転送させて取得する。ここで、主記憶部とは、画像処理装置１１においては、記憶部３８であり、画像処理装置１１１においては、基本的には、ＸＤＲ−ＲＡＭ１４３であり、場合によっては、ＨＤＤ１４５であるものとする。
【０１５２】
ステップＳ５４において、交差判定処理部７９は、抽出されたボクセルを通過する光線のうちの未処理の一つを選択する。
【０１５３】
ステップＳ５５において、交差判定処理部７９は、抽出されたボクセルに含まれるポリゴンと選択された光線との交差判定を実行する。
【０１５４】
ステップＳ５６において、交差判定処理部７９は、その光線が、いずれかのポリゴンと交差しているか否かを判断する。
【０１５５】
ステップＳ５６において、その光線が、いずれかのポリゴンと交差していると判断された場合、ステップＳ５７において、交差判定処理部７９は、交差判定結果を輝度計算部８０に供給するので、輝度計算部８０は、その光線とポリゴンとの交点における輝度計算を実行する。
【０１５６】
ステップＳ５６において、その光線が、いずれかのポリゴンと交差していないと判断された場合、または、ステップＳ５７の処理の終了後、ステップＳ５８において、交差判定処理部７９は、そのボクセルを通る全ての光線に対する交差判定が終了したか否かを判断する。ステップＳ５８において、そのボクセルを通る全ての光線に対する交差判定が終了していないと判断された場合、処理は、ステップＳ５４に戻り、それ以降の処理が繰り返される。
【０１５７】
ステップＳ５８において、そのボクセルを通る全ての光線に対する交差判定が終了したと判断された場合、ステップＳ５９において、ボクセル取得制御部７８は、光線記録データに基づいて、いずれかの光線が通過している全てのボクセルの処理が終了したか否かを判断する。ステップＳ５９において、いずれかの光線が通過している全てのボクセルの処理が終了していないと判断された場合、処理は、ステップＳ５２に戻り、それ以降の処理が繰り返される。
【０１５８】
ステップＳ５９において、いずれかの光線が通過している全てのボクセルの処理が終了したと判断された場合、ステップＳ６０において、光線発生数管理部７２は、発生するべき全ての光線の処理が終了したか否かを判断する。ステップＳ６０において、発生するべき全ての光線の処理が終了していないと判断された場合、処理は、ステップＳ４３に戻り、それ以降の処理が繰り返される。
【０１５９】
ステップＳ６０において、発生するべき全ての光線の処理が終了したと判断された場合、ステップＳ６１において、影濃度計算部８１は、輝度計算部８０から供給された輝度計算結果に基づいて、３次元画像の各画素の影の濃度を算出し、計算結果出力制御部８２に供給する。
【０１６０】
ステップＳ６２において、計算結果出力制御部８２は、影濃度計算部８１から供給された影の濃度の算出結果を出力し、処理が終了される。
【０１６１】
このような処理により、ボクセル分割法やオクトリー分割法などの空間分割法を用い、交差判定を行う画像処理（例えば、レイトレーシング法やアンビエントオクルージョン法をベースとした３次元画像生成や）において、交差判定の処理回数自体は従来における場合と同一である（すなわち、交差判定の結果得られる画像処理の精度は従来における場合と同一である）が、転送速度の比較的遅い記憶部からのポリゴンデータの転送回数を減らすことができるため、演算処理全体にかかる時間の短縮化を図ることができる。
【０１６２】
具体的には、例えば、説明を分かりやすくするために、３次元画像のうちの図１２に示されるようなある平面において、３本の光線α、β、γを用いて交差判定を行う場合を例とすると、従来における場合においても、ポリゴンを含むボクセルの情報のみを転送するようになされていたとしても、それぞれの光線に交差するボクセルの情報を１つの光線ごとに転送していた場合、図中αとして示される光線と交差しているとして３つのボクセル、図中βとして示される光線と交差しているとして３つのボクセル、図中γとして示される光線と交差しているとして３つのボクセルの情報が、それぞれ転送されるので、合計９回ボクセルの情報が転送される。すなわち、従来における場合では、図中Ａ，Ｂ，Ｃで示される３つのボクセルに関する情報が重複して転送処理される。これに対して、画像処理装置１１または画像処理装置１１１においては、３本の光線α、β、γのいずれかと交差しているボクセルが選択されて、そのボクセルに関する情報が転送されるので、合計５つのボクセルの情報が転送される。
【０１６３】
このような処理を実行することにより、影の描画にかかる時間を短縮することができるので、同じ画像を同じ時間で生成するために必要な計算機の数も減り、消費電力も削減することができ、結果としてコスト削減につながる。
【０１６４】
図１２においては、説明を分かりやすくするため、簡略化したモデルを用いて説明したが、実際に処理されるのは、３次元画像であり、その３次元画像に含まれるポリゴンによって構成される物体が３次元空間を占める割合が大きい可能性がある。画像処理装置１１または画像処理装置１１１においては、３次元画像空間内のモデルが大きい場合、換言すれば、ポリゴンを含むボクセルの割合が多い場合や、発生される光線の数が多い場合などにおいて、ボクセルの情報の転送回数の従来における場合と比較した減少割合が顕著となる。また、画像処理装置１１または画像処理装置１１１においては、１度に発生される光線の数Ｍが多いほど、ボクセルの情報の転送回数の減少割合が顕著となる。
【０１６５】
例えば、映画に使われるCG（computer graphics）において、1枚の画像を生成するのに数十分乃至数時間かかってしまうことがある。例えば、2時間の映画には、17万枚もの画像が必要になるため、それぞれの画像を生成するための処理時間を抑えることは多大なるコスト削減につながる。画像処理のうちの、影の描画処理を、その品質を落とすことなく短時間で実行することが可能となることにより、画像生成全体のコスト削減を図ることができるのは言うまでもない。
【０１６６】
なお、本発明の構成要件と、明細書または図面に記載の実施の形態との対応関係の一部を例示すると、交差情報は、例えば、図７を用いて説明した光線記録データであり、空間情報は、例えば、対応するボクセルに含まれるポリゴンの情報である。なお、この記載は、本発明をサポートする実施の形態が、明細書または図面に記載されていることを確認するためのものであり、この実施の形態が、その構成要件以外の構成要件には対応しないものであることを意味するものではない。
【０１６７】
上述した一連の処理は、ソフトウェアにより実行することもできる。そのソフトウェアは、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【０１６８】
この記録媒体は、図４または図８に示すように、コンピュータとは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM（Compact Disk-Read Only Memory），DVD（Digital Versatile Disk）を含む）、光磁気ディスク（ＭＤ(Mini-Disk)（商標）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア５１またはリムーバブルメディア１１７などにより構成される。
【０１６９】
また、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１７０】
なお、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０１７１】
なお、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【０１７２】
【図１】従来の空間分割法について説明するための図である。
【図２】従来における影生成処理について説明するためのフローチャートである。
【図３】ボクセルに関する情報の転送の重複について説明するための図である。
【図４】画像処理装置の構成を説明するためのブロック図である。
【図５】ボクセルの転送について説明するための図である。
【図６】図４の画像処理装置が有する機能について説明するための機能ブロック図である。
【図７】光線記録データについて説明するための図である。
【図８】画像処理システムについて説明するためのブロック図である。
【図９】図８のマイクロプロセッサが有する機能について説明するための機能ブロック図である。
【図１０】影生成処理について説明するためのフローチャートである。
【図１１】影生成処理について説明するためのフローチャートである。
【図１２】ボクセルの転送回数の削減について説明するための図である。
【符号の説明】
【０１７３】
１１  画像処理装置，  ３１  CPU，  ３８  記憶部，  ６１  ローカルストレージ，  ７１  影情報算出座標制御部，  ７２  光線発生数管理部，  ７３  光線発生処理部７３，  ７４  光線発生数係数および光線ＩＤ発行部，  ７５  ボクセル生成処理部，  ７６  ３ＤＤＤＡ演算部，  ７７  ボクセル通過光線情報記録部，  ７８  ボクセル取得制御部，  ７９  交差判定処理部，  ８０  輝度計算部，  ８１  影濃度計算部，  ８２  計算結果出力制御部，  １１１  画像処理装置，  １１２  記憶装置，  １４１  マイクロプロセッサ，１４３  ＸＤＲ−ＲＡＭ，  １４５  ＨＤＤ，  １８１  メインＣＰＵコア，  １８２  サブＣＰＵコア，  １９１  ローカルストレージ
【図１】
2008262493.tif 000003
【図２】
2008262493.tif 000004
【図３】
2008262493.tif 000005
【図４】
2008262493.tif 000006
【図５】
2008262493.tif 000007
【図６】
2008262493.tif 000008
【図７】
2008262493.tif 000009
【図８】
2008262493.tif 000010
【図９】
2008262493.tif 000011
【図１０】
2008262493.tif 000012
【図１１】
2008262493.tif 000013
【図１２】
2008262493.tif 000014