(57)【特許請求の範囲】
【請求項１】
第１の視点および該第１の視点とは異なる第２の視点から共通の物体を描画する画像処理装置であって、
仮想空間を構成する複数の仮想物体のデータを管理する管理手段と、
前記第１の視点から観察可能な仮想物体を前記複数の仮想物体から探索し、該探索により見つかった仮想物体の画像を含む、当該第１の視点から前記仮想空間を観察した第１画像を描画する第１の描画手段と、
前記第２の視点から観察可能な仮想物体を前記複数の仮想物体から探索し、該探索により見つかった仮想物体の画像を含む、当該第２の視点から前記仮想空間を観察した第２画像を描画する第２の描画手段とを備え、
前記第１の描画手段は、前記仮想物体を所定の順序で探索し、該探索により見つかった仮想物体が先の順序となるように前記所定の順序を更新し、
前記第２の描画手段は、前記第１の描画手段により更新された所定の順序で前記仮想物体を探索することを特徴とする画像処理装置。
【請求項２】
前記第１の描画手段は、
前記探索により見つかった仮想物体が先頭に位置するように、前記所定の順序を更新することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記第１画像及び前記第２画像の画像領域は、第１の領域と第２の領域とを含み、
前記第１の描画手段及び前記第２の描画手段はそれぞれ、前記第１画像の前記第１の領域及び前記第２画像の前記第２の領域を描画し、該描画後、前記第１画像の前記第２の領域及び前記第２画像の前記第１の領域を描画し、
前記第１の描画手段は、前記第１画像の前記第１の領域を描画する際に、前記仮想物体を第１の所定の順序で探索し、該探索により見つかった仮想物体が先の順序となるように前記第１の所定の順序を更新し、
前記第２の描画手段は、前記第２画像の前記第２の領域を描画する際に、前記仮想物体を第２の所定の順序で探索し、該探索により見つかった仮想物体が先の順序となるように前記第２の所定の順序を更新し、
前記第１の描画手段は、前記第１画像の前記第２の領域を描画する際に、前記仮想物体を前記第２の描画手段により更新された前記第２の所定の順序で探索し、
前記第２の描画手段は、前記第２画像の前記第１の領域を描画する際に、前記仮想物体を前記第１の描画手段により更新された前記第１の所定の順序で探索することを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記第１の描画手段及び前記第２の描画手段はそれぞれ、描画の過程で得られた奥行き値を他方の視点からの座標系に変換して描画することを特徴とする請求項１乃至３の何れか１項に記載の画像処理装置。
【請求項５】
前記第１の視点は観察者の一方の目に対応しており、前記第２の視点は当該観察者の他方の目に対応していることを特徴とする請求項１乃至４の何れか１項に記載の画像処理装置。
【請求項６】
前記第１の描画手段及び前記第２の描画手段はそれぞれ、前記第１の領域と前記第２の領域とが重ならないように前記画像領域の分割を行うことを特徴とする請求項３に記載の画像処理装置。
【請求項７】
第１の視点および該第１の視点とは異なる第２の視点から共通の物体を描画する画像処理装置が行う画像処理方法であって、
前記画像処理装置の管理手段が、仮想空間を構成する複数の仮想物体のデータを管理する管理工程と、
前記画像処理装置の第１の描画手段が、前記第１の視点から観察可能な仮想物体を前記複数の仮想物体から探索し、該探索により見つかった仮想物体の画像を含む、当該第１の視点から前記仮想空間を観察した第１画像を描画する第１の描画工程と、
前記画像処理装置の第２の描画手段が、前記第２の視点から観察可能な仮想物体を前記複数の仮想物体から探索し、該探索により見つかった仮想物体の画像を含む、当該第２の視点から前記仮想空間を観察した第２画像を描画する第２の描画工程とを有し、
前記第１の描画工程では、前記仮想物体を所定の順序で探索し、該探索により見つかった仮想物体が先の順序となるように前記所定の順序を更新し、
前記第２の描画工程では、前記第１の描画工程で更新された所定の順序で前記仮想物体を探索することを特徴とする画像処理方法。
【請求項８】
コンピュータを、請求項１乃至６の何れか１項に記載の画像処理装置が有する各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想空間画像の生成技術に関するものである。
【背景技術】
【０００２】
近年、計算機の処理能力の向上により、体験者にリアルな体験を提供するVirtual Reality（仮想現実感）の技術が研究されている（非特許文献１を参照）。係る技術は、コンピュータグラフィックスで仮想空間を表現し、ＨＭＤ（Head Mounted Display）や壁面型のディスプレイに表示することで成される。
【０００３】
この分野において高品質な体験を体験者に提示するために必要とされる要素が、画像生成の速度である。一般的に体験者の視点移動に追随して仮想空間を画像生成する際に求められる処理速度は、毎秒１０〜１５フレーム以上であると言われている。そのため、従来より高い表現力を維持したまま高速に画像生成するための技術が開発されてきた。
【０００４】
近年では、計算機の並列化技術と、仮想空間のハンドリング技術の進展により、今まで不可能とされてきた光線追跡（レイトレーシング）法のリアルタイム化が可能になってきている（非特許文献２を参照）。非特許文献２に開示されているレイトレーシング法は、特にリアルタイムレイトレーシングと呼ばれ、研究が盛んに行われている。この技術を利用すると、従来のラスタライゼーション法では困難であった反射や屈折表現、影の高速な生成、グローバルイルミネーションの表現が可能になり、高品質な画像を生成することができる。
【０００５】
このように画像生成処理の表現能力が高まる一方、高品質な画像を得るために費やす計算負荷は増加の一途を辿っている。また、仮想空間中に物体をリアルタイムに表示したいという欲求から、取り扱うデータ量も増加している。そのため、リアルタイムレイトレーシングが実現されても、表現能力を高く維持したまま高フレームレートで出力するためには計算負荷軽減技術が必要不可欠である。
【０００６】
時系列的な関連性を利用し、レイトレーシングによるアニメーション作成を効率化するための手法が特許文献１に開示されている。アニメーションは、少しずつ変化する画面（フレーム）を更新することで動きを表現している。したがって、少しずつ変化する画面には当然見えている物体の位置関係等の時系列的な相関関係（コヒーレンス）が存在している。
【０００７】
一般的に、レイトレーシングによる画像生成処理の中で最も時間がかかるのは、光線追跡の探索時間である。特許文献１では、時系列的な画像間のコヒーレンスを活用し、前フレームと現フレームで変化の無い部分は、前フレームの結果を再利用することで光線追跡法における探索時間の軽減を実現している。
【非特許文献１】ＶＲ世界の構築手法  監修者  舘すすむ、編者  廣瀬通孝、発行所  株式会社  培風館、2000年
【非特許文献２】Interactive Rendering with Coherent Ray-Tracing Ingo Wald, Carsten Benthin, Markus Wagner, and Philipp Slusallek in Computer Graphics Forum ／ Proceedings of the EUROGRAPHICS 2001, pp 153-164, 20(3), Manchster, United Kingdom, September 3-7, 2001
【特許文献１】特許第2532055号
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記の方法は、レイトレーシングによる画像生成処理の時系列的な効率化と高速化を実現している。しかし、一度に視点の異なる複数枚の画像を生成する処理については全く考慮されていない。例えば、仮想空間内を体験者がＨＭＤを装着して体験する場合、一度に右眼用と左眼用の２枚の画像を生成し、ステレオ画像として体験者に提示する必要がある。ここで、ステレオ画像生成では、右眼用画像と左眼用画像とでは視点位置姿勢が異なるため、光線の反射方向が異なる。そのため時系列的な関連性は利用することができない。したがって、体験者に提示するステレオ画像を生成するためには、左右眼それぞれで画像生成処理を行う必要が生じる。
【０００９】
本発明は以上の問題に鑑みてなされたものであり、複数枚の仮想空間画像を効率的に生成するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の目的を達成するために、例えば、本発明の画像処理装置は以下の構成を備える。
【００１１】
即ち、第１の視点および該第１の視点とは異なる第２の視点から共通の物体を描画する画像処理装置であって、
仮想空間を構成する複数の仮想物体のデータを管理する管理手段と、
前記第１の視点から観察可能な仮想物体を前記複数の仮想物体から探索し、該探索により見つかった仮想物体の画像を含む、当該第１の視点から前記仮想空間を観察した第１画像を描画する第１の描画手段と、
前記第２の視点から観察可能な仮想物体を前記複数の仮想物体から探索し、該探索により見つかった仮想物体の画像を含む、当該第２の視点から前記仮想空間を観察した第２画像を描画する第２の描画手段とを備え、
前記第１の描画手段は、前記仮想物体を所定の順序で探索し、該探索により見つかった仮想物体が先の順序となるように前記所定の順序を更新し、
前記第２の描画手段は、前記第１の描画手段により更新された所定の順序で前記仮想物体を探索することを特徴とする。
【発明の効果】
【００１４】
本発明の構成により、左右眼のように視点の位置姿勢が異なる複数枚の仮想空間画像であっても効率的に生成することができる。
【発明を実施するための最良の形態】
【００１５】
以下、添付図面を参照し、本発明の好適な実施形態について詳細に説明する。
【００１６】
［第１の実施形態］
本実施形態では、ユーザ（観察者）の右眼、左眼のそれぞれに対して提示する仮想空間画像をレイトレーシング法により生成する場合を想定している。より詳しくは、本実施形態では先ず一方の目に対して提示する仮想空間画像を生成し、係る生成処理の過程で得られる計算結果を記憶する。そして、係る計算結果を、他方の目に対して提示する仮想空間画像の生成処理に利用する。これにより、それぞれの目に対して提示する仮想空間画像の生成処理の効率化と高速化を可能にする。
【００１７】
図１は、本実施形態で行う画像処理の概要を説明する図である。本実施形態では、ユーザが仮想空間に没入して体験を行う際、左眼と右眼でそれぞれ異なる視点位置姿勢で仮想空間の画像をレイトレーシング法により生成する場合を想定している。したがって、ユーザの左眼に対して提示する画像を表示する画面１０１と、ユーザの右眼に対して提示する画像を表示する画面１０２のそれぞれには、それぞれ異なる視点位置姿勢に基づいた仮想空間画像が表示されることになる。
【００１８】
また、それぞれの画面１０１、１０２に表示される画像の視点位置姿勢は、人間の眼間距離と同様に、それほど大きく離れていないことを想定している。そのため、本実施形態では、画面１０１に映っている仮想物体は、画面１０２にも映っていると仮定することができる。このような仮定を用いることで、左眼用の仮想空間画像を生成するために計算した計算結果を、右眼用の仮想空間画像を生成する処理でも利用することが可能となる。
【００１９】
画像処理装置１０３は、画面１０１，１０２に表示する仮想空間画像を、レイトレーシング法により生成する画像処理装置である。
【００２０】
ただし、それぞれの画面１０１，１０２における領域１０４は、左眼と右眼とで視野が重ならない領域である。領域１０４については、一方の画面に表示した仮想空間画像の生成時における計算結果の再利用ができないため、それぞれの画像生成処理の中で毎回計算を行う必要がある。
【００２１】
レイトレーシング法による画像処理計算において最も処理時間のかかる処理は、光線と交差する仮想物体の探索処理である。
【００２２】
探索の難しさは仮想物体の多さ、つまりはシーンの複雑さに大きく依存する。例えば、シーン中に１万個の仮想物体が存在しているとする。この場合、仮想空間を構成する各要素をツリー構造で管理するシーンツリー中の１万番目のオブジェクトが描画対象であるとすると、仮想空間画像を毎フレーム生成する度に１万回の探索処理を行う必要がある（仮想物体の探索処理の詳細な説明は後述する）。
【００２３】
本実施形態では、一方の目に対して提示する仮想空間画像を生成すべく一方の目に映る仮想物体をシーンデータから検索した場合に、その検索の結果を、他方の目に対して提示する仮想空間画像を生成する処理に利用する。これにより、全体の計算負荷を軽減させ、画像生成処理の高速化を実現する。
【００２４】
図２は、本実施形態に係る画像処理装置に適用可能なコンピュータのハードウェア構成を示すブロック図である。なお、コンピュータのハードウェア構成については係る構成に限定するものではなく、処理を実行する実行部とプログラムやデータを記憶する記憶部とを主要な構成とする装置であれば、如何なる構成のコンピュータを用いても良い。
【００２５】
図２において、ＣＰＵ２０１は、ＲＡＭ２０２やＲＯＭ２０３に格納されているコンピュータプログラムやデータを用いて本コンピュータ全体の制御を行うと共に、本コンピュータが行うものとして後述する各処理を実行する。
【００２６】
ＲＡＭ２０２は、外部記憶装置２０４からロードされた処理プログラム２０５（コンピュータプログラム）やシーンデータ２０６を一時的に記憶するためのエリアを有すると共に、ＣＰＵ２０１が各種の処理を実行する際に用いるワークエリアも有する。即ち、ＲＡＭ２０２は、各種のエリアを適宜提供することができる。
【００２７】
ＲＯＭ２０３には、ブートプログラムや本コンピュータの設定データ等が格納されている。
【００２８】
外部記憶装置２０４は、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置２０４には、ＯＳ（オペレーティングシステム）に加え、処理プログラム２０５、シーンデータ２０６が格納されている。更に、外部記憶装置２０４には、後述の説明において既知の情報として説明するものや、後述の説明において、当業者であれば常識的に用いるであろう情報等もまた、保存されている。外部記憶装置２０４に保存されているコンピュータプログラムやデータは、ＣＰＵ２０１による制御に従って適宜ＲＡＭ２０２にロードされる。そしてＣＰＵ２０１は、このロードされたコンピュータプログラムやデータを用いて各種の処理を実行する。
【００２９】
ここで、外部記憶装置２０４に保存されている処理プログラム２０５は、本コンピュータが行うものとして後述する各種の処理をＣＰＵ２０１に実行させる為のコンピュータプログラムである。
【００３０】
シーンデータ２０６は、仮想空間を構成する各要素をツリー形式（木構造）で管理するためのデータである。例えば、仮想物体を周知のポリゴンで構成する場合、シーンデータ２０６には、ポリゴンの色データ、法線ベクトルデータ、ポリゴンを構成する各頂点の座標値データ（これらのデータを以下、幾何情報と呼称する）等が含まれる。また、仮想物体に対してテクスチャマッピングを施す場合には、シーンデータ２０６には、テクスチャマップデータも含まれる。さらに、仮想空間中を照射する仮想光源の種類や輝度情報も、このシーンデータ２０６に含まれる。
【００３１】
また、仮想空間画像をレイトレーシング法を用いて描画する場合、シーンデータ２０６には、光線と仮想物体との交差判定を容易にするための空間分割情報等も含まれている。本実施形態では上述の通り、仮想空間画像はレイトレーシング法で描画するものとして説明する。
【００３２】
入力装置２０７は、仮想空間画像を観察するユーザの右眼の位置姿勢情報、左眼の位置姿勢情報を入力するための装置である。従って入力装置２０７に適用可能な装置としては様々なものが考え得る。
【００３３】
例えば、キーボードやマウスを入力装置２０７として用いても良い。この場合、ユーザが入力装置２０７を用いて手動でそれぞれの眼の位置姿勢情報を入力することになる。
【００３４】
また、位置姿勢センサを入力装置２０７として用いても良い。この場合、係る位置姿勢センサはユーザの頭部に取り付けることになる。そして係る位置姿勢センサは、計測した結果をＲＡＭ２０２にデータとして入力することになる。ＣＰＵ２０１は、係る計測結果のデータと、位置姿勢センサと右眼との位置姿勢関係、位置姿勢センサと左眼との位置姿勢関係、を用いて、右眼、左眼の位置姿勢を求める。
【００３５】
このように、ユーザの右眼、左眼の位置姿勢情報の取得方法については様々なものがあり、何れかの方法に限定するものではない。またそれに従って、入力装置２０７に適用する装置は適宜決めればよい。
【００３６】
表示装置２０８は、ＣＰＵ２０１が生成した右目用の仮想空間画像、左目用の仮想空間画像を表示するためのものであり、ＣＲＴや液晶画面などにより構成されている。もちろん、表示装置２０８にはこれ以外の情報を表示させても良い。即ち、表示装置２０８は、ＣＰＵ２０１による処理結果を画像や文字等を用いて表示することができる。
【００３７】
２０９は上述の各部を繋ぐバスである。
【００３８】
次に、図２に示す構成を有するコンピュータが、ユーザの右眼、左眼のそれぞれに対して提示する仮想空間画像（それぞれ右目用仮想空間画像、左目用仮想空間画像）を生成するために行う処理について、同処理のフローチャートを示す図３を用いて説明する。
【００３９】
なお、図３に示したフローチャートに従った処理をＣＰＵ２０１に実行させる為のコンピュータプログラム（処理プログラム２０５を含む）やデータ（シーンデータ２０６を含む）は、外部記憶装置２０４に保存されている。上述の通り、係るコンピュータプログラムやデータは、ＣＰＵ２０１による制御に従って適宜ＲＡＭ２０２にロードされる。ＣＰＵ２０１は、このロードされたコンピュータプログラムやデータを用いて処理を実行するので、本コンピュータは、図３に示したフローチャートに従った処理を実行することになる。
【００４０】
先ずステップＳ３００では、以降の処理のための初期化処理を行う。係る初期化処理には、外部記憶装置２０４から処理プログラム２０５を読み出し、ＲＡＭ２０２にロードする処理が含まれている。また、係る初期化処理には、ＲＡＭ２０２内に、以降の処理で用いる為のエリアを確保する処理も含まれている。
【００４１】
次にステップＳ３０１では、外部記憶装置２０４からシーンデータ２０６を読み出し、ＲＡＭ２０２に順次展開する。この時、ＲＡＭ２０２へ展開されるデータは、シーン全体の木構造を記述したシーンツリーとノード情報である。ノード情報とは、シーンツリーの個々の要素となる仮想物体の幾何情報、材質情報、仮想光源等の情報である。
【００４２】
次にステップＳ３０２では、仮想空間中における視点（右眼、左眼）のそれぞれの位置姿勢情報をＲＡＭ２０２に取得する。係る取得は上述の通り様々な方法があるが、本実施形態では、入力装置２０７を用いて手動でユーザが入力したものとする。しかし、予め定められた固定値としての右眼の視点位置姿勢情報、左眼の視点位置姿勢情報を用いても良い。
【００４３】
次に、ステップＳ３０３では、ステップＳ３０１でＲＡＭ２０２に取得したデータ群、ステップＳ３０２でＲＡＭ２０２に取得した右眼、左眼の位置姿勢情報、を用いて、一方の眼（第１の視点）に対して提示する仮想空間画像（第１画像、第１画面）を生成する。そして生成した第１画面を表示装置２０８の表示画面上に表示する。本ステップにおける処理の詳細については後述する。
【００４４】
次に、ステップＳ３０４では、ステップＳ３０３における処理において更新されたシーンデータ２０６を用いて、他方の眼（第２の視点）に対して提示する仮想空間画像（第２画像、第２画面）を生成する。そして生成した第２画面を表示装置２０８の表示画面上に表示する。本ステップにおける処理の詳細についても後述する。
【００４５】
ステップＳ３０５では、本処理を終了するか否かを判断する。本処理を終了させるためには、例えば、ユーザが入力装置２０７を用いて終了指示を入力するようにしても良いし、処理の終了条件を予め設定しておいても良い。係る判断の結果、本処理を終了するのであれば、本処理を本処理を終了させる。一方、本処理を終了しないのであれば、次のフレームにおける右目用仮想空間画像、左目用仮想空間画像を生成すべく、処理をステップＳ３０２に進め、以降の処理を行う。
【００４６】
ここで、レイトレーシング法について、図４を用いて説明する。図４は、レイトレーシング法と仮想空間の分割とについて説明する図である。
【００４７】
レイトレーシング法では、仮想空間中に設定した視点４０１より仮想スクリーン４０２の各画素に対して光線（レイ）を飛ばす処理を行う。そして、仮想スクリーン４０２を通過した光線と、例えば、オクトリー分割した仮想空間４０３内の仮想物体との交差判定を行う。光線と仮想物体とが交差した場合は、係る仮想物体の情報をシーンデータ２０６から探索する。そして、探索した情報が示す仮想物体に対する仮想光源４０５からの光の反射を計算し、仮想スクリーン４０２上の画素値を決定する。以上の処理を仮想スクリーン４０２を構成する全ての画素について行う。
【００４８】
ここで、仮想空間４０３は光線と仮想物体との交差判定を容易にするためオクトリー分割している。レイトレーシング法では空間を分割することにより交差判定を容易にする手法が数多く提案されている。例えば、kd-tree分割やBVH（Boundary Volume Hierarchy）などが挙げられる。本実施形態は空間分割のアルゴリズムに依らないため、如何なる空間分割手法を用いても良い。
【００４９】
また、光線と交差した仮想物体の情報は、シーンデータ２０６中のシーンツリーの探索を行うことで得られる。
【００５０】
次に、シーンデータ２０６について説明する。図５は、シーンデータ２０６が示すツリーの構成例を示す図である。
【００５１】
World５０１はシーン（仮想空間）の根幹（ルート）ノードに相当するノードで、シーンの絶対座標を定義するノードである。
【００５２】
Camera５０２は、視点の位置姿勢や画角を格納しているノードである。
【００５３】
Object５０３は、仮想物体の各種情報を保持しているノードである。一般的に、シーンには複数の仮想物体が存在するため、Object５０３以下にはシーン内に登場する仮想物体をグループ化したSub-object５０５が用意される。
【００５４】
Transform５０６は、World５０１の絶対座標に対するObject５０３の位置姿勢を定義するパラメータである。
【００５５】
Sub-object５０５は、仮想物体を示す最小単位としてのobject１（５０７）、object２、…をグループ化したノードである。Sub-object５０５以下にはシーンに登場する仮想物体の数だけobjectノードが関連付けられている。
【００５６】
object１（５０７）は、shape５０８、material５０９、transform５１０の情報を有している。
【００５７】
Shape５０８は、object１（５０７）のポリゴンを構成する各頂点の座標値データや法線ベクトルデータ等の幾何形状の情報を有している。
【００５８】
Material５０９は、object１（５０７）のテクスチャ情報や、光源が当たった時の拡散反射情報、鏡面反射情報などが属性データとして格納されている。
【００５９】
transform５１０は、object１（５０７）の位置姿勢情報を示している。
【００６０】
最後に、Light５０４は、仮想空間シーンを照射する為の仮想光源の情報を有しており、仮想光源の位置（幾何情報）と光源の種類（直接光、点光源、スポットライト等）、輝度情報（色味情報も含む）のデータを格納している。
【００６１】
以上の構成から、光線と交差した仮想物体の情報を得るためには、光線と交差した数だけ図５に示したシーンツリーの探索処理（シーンデータ内の探索）が必要になる。すなわち、階層構造の深い場所にある仮想物体に光線が交差した場合や、仮想物体が非常に多いシーン等では、探索処理が膨大に増加してしまう。
【００６２】
次に、シーンデータ２０６中のシーンツリーの探索について説明する。図６は、シーンツリーの探索について示す図である。
【００６３】
シーンツリー６０１は、初期状態におけるシーンツリーである。シーンツリー６０１における子ノード６０２は、ある視点（着目視点）から見えている仮想物体を示している。そして、探索経路６０３は、光線が仮想物体（子ノード６０２）に交差した際に、この仮想物体のノードを探索する為の経路を示している。係る経路は予め設定されている。
【００６４】
ここで、着目視点から見える仮想空間画像を生成する処理では、従来では、子ノード６０２に対応する仮想物体の表示画面上における画素数分だけ探索経路６０３に沿って子ノード６０２の探索を行うことになる。シーンツリー６０１の場合、子ノード６０２の位置は探索経路６０３の末端部分にあるため、毎回の探索には時間がかかる。本実施形態では、係る時間を短縮すべく、子ノード６０２の位置を、探索経路６０３の先頭部分に移動させることで、シーンツリー６０１を更新する。
【００６５】
より詳しくは、子ノード６０２が探索された時点で、ＲＡＭ２０２内に新たなシーンツリーの作成を開始する。即ち、最初にシーンツリー６０１の複製をＲＡＭ２０２中に作成し、複製シーンツリーにおける子ノード６０２の位置を探索経路６０３の先頭部分に移動させることで、複製シーンツリーを更新する。即ち、シーンデータ中における仮想物体のデータの管理順を変更することで、シーンデータを更新する。図６において６０４は、子ノード６０２の位置を探索経路６０３の先頭位置に移動させたことで更新した複製シーンツリーを示す。６０５で示す如く、子ノード６０２を探索するまでの経路の長さは、探索経路６０３と比べても短くなっていることが分かる。なお、子ノード６０２内のそれぞれのノードの並び順（管理順）に関しては特に限定するものではない。
【００６６】
そして、着目視点から見える仮想空間画像を生成する処理が終了した時点で、シーンツリー６０１を複製シーンツリーに更新する。そして、更新後のシーンツリー６０１を、着目視点以外のもう一方の視点から見える仮想空間画像を生成する為に用いるシーンツリーとして設定する。
【００６７】
このように、ある視点についての仮想空間画像の生成処理の過程で更新したシーンツリーは、次の視点についての仮想空間画像を生成するために用いられる。従って、複数の視点についての仮想空間画像を生成する場合、生成処理順で後の視点ほど、探索距離が短くなる。
【００６８】
なお、仮想空間画像の生成過程で探索されなかったノードについては、新シーンツリーの（探索経路６０３の）最後尾に配置する。このように、探索されなかったノードに関しても、新シーンツリーにコピーしておくことで、第１画面、第２画面で異なる仮想物体を視野に入れていても問題が生じない。つまり、第２画面のみに映っている仮想物体が存在した場合、新シーンツリーにおける並べ替えの対象にはならないが、新シーンツリー内には仮想物体の情報が格納されているため、問題無く表示することが可能である。
【００６９】
このように、一方の視点に対する仮想空間画像の生成時に、探索される仮想物体のノードのシーンツリー中における位置を探索経路の先頭位置に再配置することで、効率的な探索処理を実現することができる。
【００７０】
また、新シーンツリー作成時のノード組み換え操作では、探索順序の代わりに探索を行った頻度をカウントしておき、探索頻度順でシーンツリーを組み替える事も可能である。即ち、ノード毎に探索された回数をカウントしておき、１枚の仮想空間画像の生成処理を完了させた時点でカウント値が大きいものから順に、探索経路の先頭から並べる。
【００７１】
更に、第１画面の画像生成過程で仮想物体が視野に入っていない場合は、第２画面においてシーンツリーの探索処理は不要となる。したがって、第１画面の画像処理過程で仮想物体が視野に入っていない情報を新シーンツリーの情報に付加しておくことで第２画面の画像生成を高速に処理することが可能となる。
【００７２】
第１画面の視野に仮想物体が入っていない場合の第２画面の画像生成処理としては、背景となる画像をテクスチャとして予め用意しておき、レイトレーシング処理を行う代わりにテクスチャレンダリングで画像生成処理を行う。
【００７３】
ただし、仮想物体が第２画面のみに映っている場合がある。この場合は仮想物体の有無情報は利用することができない。しかし、片眼のみに仮想物体が映る現象は、仮想物体と視点位置が極端に近い場合に視差が大きなり生じる現象である。したがって、仮想物体の有無情報を利用する場合は、視差が大きくならないように視点から一定の奥行き値以上に仮想物体が存在する場合に限るように制約を設ける。この制約により仮想物体の有無情報を利用することが可能になる。
【００７４】
第１画面の画像生成における視点位置姿勢が第２画面の画像生成における視点位置姿勢と同一、またはほぼ同一である場合、第１画面の探索結果と第２画面の探索結果は等しくなる。そのため、第１画面で探索した探索結果を第２画面の画像生成過程で再利用することが可能になる。
【００７５】
シーン探索の問題は、種々の画像生成処理（ラスタライゼーション手法、ボリュームレンダリング手法、パーティクルレンダリング法等）で必ず必要となる処理であるため、画像生成処理を変更してもシーン再構築による画像生成の効率化手法は有効である。したがって、本実施形態は種々の画像生成処理一般に応用可能である。
【００７６】
なお、本実施形態では、第１画面、第２画面を、コンピュータが有する表示装置２０８に表示させていたが、他の表示装置に第１画面、第２画面を表示させても良い。例えば、コンピュータにＨＭＤを接続した場合、ＨＭＤが有する右目用の表示画面には右目用仮想空間画像、左目用の表示画面には左目用仮想空間画像を表示させるようにしても良い。
【００７７】
［第２の実施形態］
第１の実施形態では、第１画面、第２画面を逐次処理で生成していた。本実施形態では、第１画面、第２画面を分割し、並列でそれぞれの画面を生成する。
【００７８】
図７は、本実施形態で行う画像処理の概要を説明する図である。
【００７９】
本実施形態では、第１画面、第２画面を上下で２分割し、それぞれの領域を１つのＣＰＵで処理することを想定している。
【００８０】
図７において７０１は第１画面の上部領域（部分領域）を示し、７０３は第１画面の下部領域を示している。上部領域７０１と下部領域７０３はそれぞれ、第１画面を上下で２分割して得られるものであるので、それぞれの領域で重なる部分はない。
【００８１】
図７において７０２は第２画面の上部領域を示し、７０４は第２画面の下部領域を示している。上部領域７０２と下部領域７０４はそれぞれ、第２画面を上下で２分割して得られるものであるので、それぞれの領域で重なる部分はない。
【００８２】
本実施形態では、一方の画面の上部領域と他方の画面の下部領域とを並行して生成する。一方の画面の上部領域の生成処理では、オリジナルのシーンデータを複製し、一方の画面の上部領域に登場する仮想物体のノードを、探索経路の先頭に移動させるべく複製シーンツリーを第１の実施形態と同様に更新する。他方の画面の下部領域の生成処理では、オリジナルのシーンデータを複製し、他方の画面の下部領域に登場する仮想物体のノードを、探索経路の先頭に移動させるべく複製シーンツリーを第１の実施形態と同様に更新する。即ち、本実施形態では、一方の画面用のシーンデータ（第１のシーンデータ）と他方の画面用のシーンデータ（第２のシーンデータ）とが生成されることになる。
【００８３】
次に、一方の画面の下部領域と他方の画面の上部領域とを並行して生成する。一方の画面の下部領域の生成処理では、他方の画面の下部領域の生成の過程で更新されたシーンデータを用いる。他方の画面の上部領域の生成処理では、一方の画面の上部領域の生成の過程で更新されたシーンデータを用いる。
【００８４】
このように、２つのプロセスが同時並行で実行されることにより、画像生成が１画面の半分まで終わった時点から、効率良くシーンツリーの探索処理を行うことが可能になる。
【００８５】
図８は、本実施形態で行う画像処理の概要を説明する図である。図８において図１と同じ部分には同じ参照番号を付けており、その説明は省略する。本実施形態では、第１画面１０１と第２画面１０２とを並列に生成するために、新たに画面領域分割制御部８０１が追加されている。これは、第１画面１０１と第２画面１０２の画像生成処理を同時平行で行う際に、各々の画面を領域分割した上で画像生成処理を前半と後半に分けている。
【００８６】
また、本実施形態では、画像生成の後半部分で情報交換を行うため、第２画面１０２の画像生成過程で取得した情報も画像処理装置１０３へ出力し、第１画面１０１の画像生成時に利用する点が異なっている。
【００８７】
次に、図２に示す構成を有するコンピュータが、ユーザの右眼、左眼のそれぞれに対して提示する仮想空間画像を生成するために行う、本実施形態に係る処理について、同処理のフローチャートを示す図９を用いて説明する。
【００８８】
なお、図９に示したフローチャートに従った処理をＣＰＵ２０１に実行させる為のコンピュータプログラム（処理プログラム２０５を含む）やデータ（シーンデータ２０６を含む）は、外部記憶装置２０４に保存されている。上述の通り、係るコンピュータプログラムやデータは、ＣＰＵ２０１による制御に従って適宜ＲＡＭ２０２にロードされる。ＣＰＵ２０１は、このロードされたコンピュータプログラムやデータを用いて処理を実行するので、本コンピュータは、図９に示したフローチャートに従った処理を実行することになる。
【００８９】
先ずステップＳ９００では、以降の処理のための初期化処理を行う。係る初期化処理には、外部記憶装置２０４から処理プログラム２０５を読み出し、ＲＡＭ２０２にロードする処理が含まれている。また、係る初期化処理には、ＲＡＭ２０２内に、以降の処理で用いる為のエリアを確保する処理も含まれている。
【００９０】
次にステップＳ９０１では、外部記憶装置２０４からシーンデータ２０６を読み出し、ＲＡＭ２０２に順次展開する。この時、ＲＡＭ２０２へ展開されるデータは、シーン全体の木構造を記述したシーンツリーとノード情報である。ノード情報とは、シーンツリーの個々の要素となる仮想物体の幾何情報、材質情報、仮想光源等の情報である。
【００９１】
次にステップＳ９０２では、右目用の画面、左目用の画面をそれぞれ上下２分割するので、それぞれの分割領域を示す領域情報を生成し、ＲＡＭ２０２に格納する。領域情報には、例えば、どちらの画面（右目用の画面、左目用の画面）における領域であるのかを示す情報、領域の左上隅の座標位置と右下隅の座標位置、が含まれている。
【００９２】
次にステップＳ９０３では、仮想空間中における視点（右眼、左眼）のそれぞれの位置姿勢情報をＲＡＭ２０２に取得する。係る取得は上述の通り様々な方法があるが、本実施形態では、入力装置２０７を用いて手動でユーザが入力したものとする。しかし、予め定められた固定値としての右眼の視点位置姿勢情報、左眼の視点位置姿勢情報を用いても良い。
【００９３】
次に、ステップＳ９０４では、ステップＳ９０１、Ｓ９０２でＲＡＭ２０２に取得したデータ群、ステップＳ９０３でＲＡＭ２０２に取得した右眼、左眼の位置姿勢情報、を用いて、一方の眼に対して提示する仮想空間画像（第１画面）の上部領域を生成する。そして生成した第１画面の上部領域を表示装置２０８の表示画面上に表示する。
【００９４】
また、ステップＳ９０４と並行してステップＳ９０５における処理を行う。ステップＳ９０５では、ステップＳ９０１、Ｓ９０２でＲＡＭ２０２に取得したデータ群、ステップＳ９０３でＲＡＭ２０２に取得した右眼、左眼の位置姿勢情報、を用いて、他方の眼に対して提示する仮想空間画像（第２画面）の下部領域を生成する。そして生成した第２画面の下部領域を表示装置２０８の表示画面上に表示する。
【００９５】
次に、ステップＳ９０７では、ステップＳ９０５で更新したシーンデータを用いて、第１画面の下部領域を生成する。そして生成した第１画面の下部領域を表示装置２０８の表示画面上に表示する。
【００９６】
また、ステップＳ９０７と並行してステップＳ９０８では、ステップＳ９０４で更新したシーンデータを用いて、第２画面の上部領域を生成する。そして生成した第２画面の上部領域を表示装置２０８の表示画面上に表示する。
【００９７】
ステップＳ９０９では、本処理を終了するか否かを判断する。本処理を終了させるためには、例えば、ユーザが入力装置２０７を用いて終了指示を入力するようにしても良いし、処理の終了条件を予め設定しておいても良い。係る判断の結果、本処理を終了するのであれば、本処理を本処理を終了させる。一方、本処理を終了しないのであれば、次のフレームにおける右目用仮想空間画像、左目用仮想空間画像を生成すべく、処理をステップＳ９０３に進め、以降の処理を行う。
【００９８】
ここで、本実施形態では、並列数を２として第１画面の画像生成と第２画面の画像生成処理を２つのプロセスで同時に処理することを想定しているが、必ずしも並列数は２である必要性はない。並列数は２以上でも対応が可能であり、その場合は、並列数に応じ画面領域を分割し、探索を効率化するためのシーンツリーをそれぞれのプロセスで生成すればよい。
【００９９】
また、本実施形態では、上下に画面を２分割して画像生成処理を実行することを想定したが、画面の分割方法は必ずしも上下に２分割する必要はない。左右で画面分割を行ってもよい。さらに並列数が上がれば、それに応じて画面領域の分割方法を変更してもよい。したがって、画面の分割方法は構築するシステムや体験を行うシーン毎に好適な手段を選択すればよい。何れにせよ、本実施形態では、一方の視点についての仮想空間画像と他方の視点についての仮想空間画像とを並行して複数回に分けて生成することになる。
【０１００】
＜変形例＞
ここでは、適応的に画面分割を行う例について説明する。
【０１０１】
図１０は、適応的に画面分割する処理を説明する図である。
【０１０２】
図１０（ａ）において第１画面１０１では左上隅の位置１００１から画像生成処理を行い、第２画面１０２では右下隅の位置１００４から画像生成処理を行う。そして図１０（ｂ）に示す如く、現在処理している画素の位置がそれぞれの画面で同じになった場合、残りの領域を処理すべく、第１画面については第２画面の生成で更新したシーンデータを用いる。そして、第２画面については第１画面の生成で更新したシーンデータを用いる。図１０（ｂ）において、１００２は、現在処理している画素の位置がそれぞれの画面で同じになった場合における、処理済みの領域を示している。
【０１０３】
このように、本実施形態によれば、画像生成処理の並列処理能力に応じて画面を分割し、画像生成処理を分担することにより、効果的でかつ高速に画像生成処理を実行することができる。
【０１０４】
［第３の実施形態］
第１，２の実施形態では、画像の生成を逐次的に１画素ずつおこなっていた。本実施形態では、画像生成処理の前半過程で一部のみ画像生成を行いシーンデータの更新を行い、再度詳細に画像生成処理を行う点が大きく異なる。
【０１０５】
図１１は、本実施形態に係る画像生成処理を説明する図である。１１０４は、視点からの視野内に収まっている仮想空間の画像（スクリーン）であり、上記第１画面や第２画面に相当する。１１０１は、係る画像１１０４内に設定されている特定領域で、図１１では、等間隔に離散的に設定されている。本実施形態では、特定領域１１０１は、画像１１０４の１画素に対応するものとするが、そのサイズについては特に限定するものではないし、特定領域の配置方法についてもこれに限定するものではない。
【０１０６】
本実施形態では、１つの仮想空間画像を２回に分けて生成する。１回目の生成（第１の生成）では、特定領域内の画像について生成する。そして２回目の生成（第２の生成）では、第１の画像生成で第１の実施形態と同様にして更新したシーンデータを用いて、残りの領域（特定領域１１０１を除く領域）の画像を生成する。
【０１０７】
本実施形態では、このように離散的に光線を飛ばす領域を設定することにより、スクリーン上の全画素を計算せずともシーン全体のシーンデータを高速に再構築することができる。
【０１０８】
そして、特定領域１１０１以外の領域は、シーン再構築後に再度詳細な画像生成処理を行うことで効率的に画像生成を行うことができる。本実施形態は主に画面上の画素値を決定する際に１画素ずつ計算するレイトレーシングなどの画像生成処理においてとても有用な方法である。
【０１０９】
特定領域によるシーンの再構築は、第１画面１０１および第２画面１０２に対して両方に適用しても良いし、片方だけに適用した結果を両方の画像生成処理に対して適用してもよい。
【０１１０】
［第４の実施形態］
第１の実施形態、第２の実施形態、第３の実施形態では、それぞれの画像生成過程で出力されるシーンデータを交換して利用することで効率良く画像を生成するための処理について説明した。本実施形態では、ラスタライゼーションによる画像生成処理において、左右の眼に対する画像生成過程で出力された奥行き値を視点座標変換して流用する点が異なる。
【０１１１】
本実施形態で行う画像処理の概要は、第２の実施形態で説明した概要と重複する点が多いので異なる点のみについて説明する。
【０１１２】
まず、本実施形態では、図７に示すように領域分割した上部領域７０１および下部領域７０４のそれぞれ重なり合わない部分領域の輝度値を通常の描画方法で計算する。このとき、輝度値を計算する過程で得られる奥行き値（Ｚバッファの値）、および対象物体の材質情報（マテリアル情報）をＲＡＭ２０２に格納する。
【０１１３】
ＲＡＭ２０２に格納した奥行き値を、他方の視点の座標系における奥行き値に変換する。係る変換によって求められた奥行き値と、対象物体のマテリアル情報があれば、輝度値は算出可能である。
【０１１４】
次に、図２に示す構成を有するコンピュータが、ユーザの右眼、左眼のそれぞれに対して提示する仮想空間画像を生成するために行う、本実施形態に係る処理について、同処理のフローチャートを示す図１２を用いて説明する。なお、図１２において、図９と同じ処理を行うステップについては同じステップ番号を付けている。
【０１１５】
ステップＳ９０４，Ｓ９０５では、第２の実施形態で説明した処理に加え、それぞれの分割領域を構成する各画素の輝度値を求める処理を行う。
【０１１６】
ステップＳ１２０１では、ステップＳ９０４，Ｓ９０５における処理の過程で得られる奥行き値（Ｚバッファの値）、対象物体の各頂点の法線情報、対象物体の材質情報をＲＡＭ２０２に格納する。
【０１１７】
ステップＳ１２０２では、ステップＳ１２０１でＲＡＭ２０２に格納した奥行き値に対して視点の座標変換を行う。係る座標変換は、左眼における奥行き値を右目における奥行き値に変換し、右眼における奥行き値を左眼における奥行き値に変換する処理である。
【０１１８】
最後に、ステップＳ９０７、Ｓ９０８では、第２の実施形態で説明した処理に加え、ステップＳ１２０２で変換したそれぞれの奥行き値に対して、ステップＳ１２０１で格納した材質情報から、それぞれの分割領域を構成する各画素の輝度値を計算する。
【０１１９】
次に、本実施形態に係る描画処理における、輝度値の決定方法について説明する。
【０１２０】
図１３は、一般的なラスタライゼーションによる画像生成処理の流れを説明する図である。
【０１２１】
モデリング変換１３０１では、外部記憶装置２０４内に保存されているシーンデータの情報（３次元座標）をＲＡＭ２０２にロードし、ワールド座標に変換する。つまり、モデリング変換１３０１では、３次元空間内での仮想物体の回転と変形を行っている。これは拡大縮小と回転のようなローカルなオブジェクト空間上での基本的な座標変換も含んでいる。ここで、モデリング変換１３０１の処理を行った時点のデータは、視点の位置姿勢に依存しないデータである。従って、右眼と左眼とでデータを共有することができる。
【０１２２】
視点変換１３０２では、ワールド座標上に定義した仮想物体の位置姿勢を、仮想カメラの位置と姿勢に基づいたローカル座標系における位置姿勢に変換する。具体的には、視点変換用の行列を予め求めておき、仮想物体の各頂点に対する行列演算を行いて行う。この結果、元の３次元シーンは仮想カメラから見た座標系におけるシーンに変換される。
【０１２３】
視点変換１３０２での処理を行った時点で、データはそれぞれの視点に依存したデータとなるため、右眼と左眼とでデータを共有することは出来なくなる。
【０１２４】
投影変換１３０３では、仮想カメラで定義した３次元座標系から２次元座標系への変換を行う。投影変換１３０３により、仮想空間は仮想カメラから見た平面（仮想スクリーン）上に２次元の情報としてマッピングされる。
【０１２５】
ラスタライゼーション１３０４では、クリッピング処理と陰面処理を施した後、仮想スクリーンに投影されるシーンの２次元画像を構成する各画素の輝度値を計算する処理を行う。
【０１２６】
クリッピング処理では、視界の外に存在する仮想物体のポリゴンを破棄し、視界の範囲内のポリゴンのみを切り取る処理を行う。隠面処理では、視点方向に向いていない、理論上は視点からは見えないポリゴンを破棄する処理を行う。このとき、視点から見えるはずのポリゴンは視点から最も遠い順にＺバッファに書き込まれる。そして順次上書きされていくことで、各画素値に対応する奥行き値が算出されると共に、視点から見えるポリゴンのみが選択される。
【０１２７】
さらに、ラスタライゼーション１３０４では、陰面処理の後、シェーディング（陰影）処理のために各頂点の法線情報および仮想物体の材質情報をシーンデータから抽出する。また、必要に応じてテクスチャ情報も抽出する。ここで、左右の眼で同一の物体を見ていた場合、物体の材質情報は共有することが可能である。抽出したデータと仮想視点の位置姿勢情報を元に反射光を計算し、仮想スクリーン上の各画素の輝度値を算出する。ただし、物体の材質情報から計算した陰影処理の結果は視点の位置姿勢によって異なるため、共有することができない。
【０１２８】
表示１３０５では、最終的に色がついた画素をモニタやその他の表示装置に表示する。
【０１２９】
以上、一般的なラスタライゼーションの処理において共通の仮想物体を異なる視点で観察する場合、変換処理をせずに共有できるデータはモデリング変換１３０１で得られるデータと物体の材質情報である。ただし、ラスタライゼーション１３０４の処理過程で得られる奥行き値は、視点の座標変換を行うことにより流用可能である。しかし、視点と物体との位置関係によってはオクルージョンが発生し、正しく奥行き値が算出できない場合がある。この場合は、前フレームの対応する画素値を参照することによって輝度値を決定する。
【０１３０】
次に、視点座標の変換を行った奥行き値から各画素の輝度値を算出する方法を説明する。
【０１３１】
図１４は、ステレオ視による３次元座標の推定手法を説明するための図である。
【０１３２】
図１４に示すように、３次元空間中にｘｙｚ絶対座標系１４０１を定義する。そして、左右のカメラレンズの中心の絶対座標がそれぞれ、OL＝（0、0、0）、OR＝（ｄ、0、0）となるように距離ｄだけ離間させて配置する。そして、レンズ焦点距離、即ちレンズ中心と左右の画像面までの距離をｆとする。このようにして設定した仮想視点から仮想物体１４０２を観察し、観察した像が投影される右眼用のスクリーン、左眼用のスクリーンをそれぞれ、仮想スクリーン１４０３Ｒ、１４０３Ｌとする。
【０１３３】
右眼から仮想物体１４０２上の点Ｐを観察した場合、点Ｐは仮想スクリーン１４０３Ｒ上の点PR（xR、yR）に投影される。また、左眼から仮想物体１４０２上の点Ｐを観察した場合、点Ｐは仮想スクリーン１４０３Ｌ上の点PL（xL、yL）に投影される。但し、点ＰＬ、点ＰＲの座標はそれぞれ、仮想スクリーン１４０３Ｌ、仮想スクリーン１４０３Ｒの中心を原点とする相対座標である。
【０１３４】
このとき、対象物体の表面上の点Ｐ（xp、yp、zp）を、２台のカメラの中心と計測点からなる三角形を利用した三角測量により、求めることができる。
【０１３５】
このようにして、点PLと点PR、各種パラメータ、が既知であれば、対象物の３次元座標が計算可能であるというのが、コンピュータビジョンにおけるステレオ視を利用した一般的な奥行き推定の方法である。
【０１３６】
本実施形態では、ステレオ視による奥行き推定方法の原理を応用して、左右どちらか一方の目に対する画面上の画素値とその画素に対応する対象物の3次元座標が既知であった場合に、他方の目に対する画面上の対応する画素の画素値を決定する。例えば、点PR（xR、yR）と、対象物体の表面上の点Ｐ（xp、yp、zp）が入力として与えられたとき、点PL（xL、yL）を求めるという問題となる。
【０１３７】
従って、視点の位置姿勢が既知で、かつ視点の座標変換を行った奥行き値によって対象物体の表面上の点Pが算出できていた場合、各仮想スクリーン上の対応点を計算することが可能になる。
【０１３８】
ステップＳ９０７，Ｓ９０８では、第２の実施形態で説明した処理に加え、計算によって求めた仮想スクリーン上の点に対して、ＲＡＭ２０２に格納されている物体の材質情報をロードする。そして、ラスタライゼーション１３０４の処理で、シェーディング処理およびテクスチャマッピング処理を行い、個々の輝度値を算出する。この処理は、未計算の画素が無くなるまで繰り返される。これらのラスタライゼーションによる画像生成手法は、一般的なグラフィックス処理を行うハードウェアで実現されており、公知の技術である。
【０１３９】
以上説明した処理により、一方の画面で領域分割した領域の輝度値を計算する過程で得られる情報を共有することで、他方の画面の該当する領域の輝度値を算出することができる。
【０１４０】
［第５の実施形態］
第１〜４の実施形態では、ステレオ画像を生成する際に画像生成過程で得られる情報を交換して利用することで効率良く画像を生成するための処理について説明した。本実施形態では、２眼以上のカメラシステムで画像生成を行う場合を想定しており、画面領域を２つ以上の領域に分割してそれぞれの画像生成処理を適用する点が異なる。
【０１４１】
図１５は、本実施形態で行う画像処理の概要を説明する図である。
【０１４２】
３つの視点のそれぞれについて描画した結果は第１画面１５０１、第２画面１５０２、および第３画面１５０３に表示される。本実施形態では、画面を３分割してそれぞれの描画を行う。
【０１４３】
領域１５０４〜１５０６は、各画面で最初に処理を開始する領域（描画領域）である。本実施形態では、領域１５０４〜１５０６は重ならないように設定されている。そして、各画面において領域１５０４〜１５０６の描画が完了した時点で、領域１５０４〜１５０６の計算結果を参照して未計算領域１５０７〜１５０９についての計算に移る。また、未計算領域１５０７〜１５０９についての計算が完了すれば、残りの領域を計算する。
【０１４４】
次に、図２に示す構成を有するコンピュータが、３眼のそれぞれに対して提示する仮想空間画像を生成するために行う、本実施形態に係る処理について、同処理のフローチャートを示す図１６を用いて説明する。なお、図１６において、図９と同じ処理を行うステップについては同じステップ番号を付けている。
【０１４５】
但し、ステップＳ９０２では、３つの画面（第１画面、第２画面、第３画面）をそれぞれ、上段、中段、下段の３段（カメラの台数に相当）に分割するものとする。なお、分割形態については特に限定するものではなく、縦に等分割しても良いし、シーンの複雑さに依存して分割領域を可変にしても良い。
【０１４６】
ステップＳ１６０１ａでは、第１画面の上段の描画処理を行う。ステップＳ１６０１ｂでは、第２画面の中段の描画処理を行う。ステップＳ１６０１ｃでは、第３画面の下段の描画処理を行う。ステップＳ１６０１ａ、１６０１ｂ、１６０１ｃのそれぞれにおける描画処理は、他の実施形態と同様にして行う。
【０１４７】
ステップＳ１６０２では、ステップＳ１６０１ａ、１６０１ｂ、１６０１ｃのそれぞれにおける描画結果を、ＲＡＭ２０２に格納する。
【０１４８】
ステップＳ１６０３ａでは、ＲＡＭ２０２に格納されている第１画面の上段の描画結果を参照して、第１画面の中段の領域内の輝度値を決定し、係る中段の描画処理を行う。ステップＳ１６０３ｂでは、ＲＡＭ２０２に格納されている第２画面の中段の描画結果を参照して、第２画面の下段の領域内の輝度値を決定し、係る下段の描画処理を行う。ステップＳ１６０３ｃでは、ＲＡＭ２０２に格納されている第３画面の下段の描画結果を参照して、第３画面の上段の領域内の輝度値を決定し、係る上段の描画処理を行う。但し、ステップＳ１６０３ａ、１６０３ｂ、１６０３ｃの段階で描画する領域は任意で良く、計算する時点で未計算領域であればよい。
【０１４９】
ステップＳ１６０４ａでは、第１画面の中段の描画結果を参照して、第１画面の下段の領域内の輝度値を決定し、係る下段の描画処理を行う。ステップＳ１６０４ｂでは、第２画面の下段の描画結果を参照して、第２画面の上段の領域内の輝度値を決定し、係る上段の描画処理を行う。ステップＳ１６０４ｃでは、第３画面の上段の描画結果を参照して、第３画面の中段の領域内の輝度値を決定し、係る中段の描画処理を行う。
【０１５０】
ここで、本実施形態では、ステップＳ１６０３ａ、１６０３ｂ、１６０３ｃで計算した結果をＲＡＭ２０２に格納していない。しかし、構築するシステムによっては、ステップＳ１６０２で格納した情報をステップＳ１６０３ａ、１６０３ｂ、１６０３ｃで計算した情報で上書きしてもよい。
【０１５１】
例えば、視点が横に並んでおり、それぞれの視点による画面を視点の並び順で並べた結果が第１の画面、第２の画面、第３の画面、であったとする。この場合、第１画面の画像を生成するにあたり第３画面の描画処理結果を利用するよりも、より視点が近い第２画面結果を利用した方が、効率が良い。従って、得られた情報の参照方法は構築するシステムによって好適な手段を選択すればよい。
【０１５２】
このようにして、共通の仮想物体を観察する２つ以上の仮想視点においても、任意の分割数で画面を分割し、各担当領域を計算した結果をそれぞれ共有することによって効率的かつ高速に描画を行うことが可能になる。
【０１５３】
［第６の実施形態］
領域分割の際、第１の画面および第２の画面で重なり合う領域が無い場合に最も効率が良くなる。しかし、全く重なり合う領域が無い場合には、境界部分のエッジが目立ってしまうという問題が発生する。そのため、境界エッジの周辺で数ピクセルに渡り重なり合う領域を設け、計算して得られた画像を合成してスムージングすることによりエッジを目立たなくすることが可能となる。領域分割の際に重なり合う領域をどの程度設定するかは、構築するシステムでそれぞれ好適な手段を採用すればよい。
【０１５４】
［その他の実施形態］
また、本発明の目的は、以下のようにすることによって達成されることはいうまでもない。即ち、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記録媒体（または記憶媒体）を、システムあるいは装置に供給する。係る記憶媒体は言うまでもなく、コンピュータ読み取り可能な記憶媒体である。そして、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に格納されたプログラムコードを読み出し実行する。この場合、記録媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記録した記録媒体は本発明を構成することになる。
【０１５５】
また、コンピュータが読み出したプログラムコードを実行することにより、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム（ＯＳ）などが実際の処理の一部または全部を行う。その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１５６】
さらに、記録媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれたとする。その後、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１５７】
本発明を上記記録媒体に適用する場合、その記録媒体には、先に説明したフローチャートに対応するプログラムコードが格納されることになる。
【図面の簡単な説明】
【０１５８】
【図１】本発明の第１の実施形態で行う画像処理の概要を説明する図である。
【図２】本発明の第１の実施形態に係る画像処理装置に適用可能なコンピュータのハードウェア構成を示すブロック図である。
【図３】図２に示す構成を有するコンピュータが、ユーザの右眼、左眼のそれぞれに対して提示する仮想空間画像を生成するために行う処理のフローチャートである。
【図４】レイトレーシング法と仮想空間の分割とについて説明する図である。
【図５】シーンデータ２０６が示すツリーの構成例を示す図である。
【図６】シーンツリーの探索について示す図である。
【図７】本発明の第２の実施形態で行う画像処理の概要を説明する図である。
【図８】本発明の第２の実施形態で行う画像処理の概要を説明する図である。
【図９】図２に示す構成を有するコンピュータが、ユーザの右眼、左眼のそれぞれに対して提示する仮想空間画像を生成するために行う、本発明の第２の実施形態に係る処理のフローチャートである。
【図１０】適応的に画面分割する処理を説明する図である。
【図１１】本発明の第３の実施形態に係る画像生成処理を説明する図である。
【図１２】図２に示す構成を有するコンピュータが、ユーザの右眼、左眼のそれぞれに対して提示する仮想空間画像を生成するために行う、本発明の第４の実施形態に係る処理のフローチャートである。
【図１３】一般的なラスタライゼーションによる画像生成処理の流れを説明する図である。
【図１４】ステレオ視による３次元座標の推定手法を説明するための図である。
【図１５】本発明の第５の実施形態で行う画像処理の概要を説明する図である。
【図１６】図２に示す構成を有するコンピュータが、ユーザの右眼、左眼のそれぞれに対して提示する仮想空間画像を生成するために行う、本発明の第５の実施形態に係る処理のフローチャートである。
【図１】
0005055214.tif 000002
【図２】
0005055214.tif 000003
【図３】
0005055214.tif 000004
【図４】
0005055214.tif 000005
【図５】
0005055214.tif 000006
【図６】
0005055214.tif 000007
【図７】
0005055214.tif 000008
【図８】
0005055214.tif 000009
【図９】
0005055214.tif 000010
【図１０】
0005055214.tif 000011
【図１１】
0005055214.tif 000012
【図１２】
0005055214.tif 000013
【図１３】
0005055214.tif 000014
【図１４】
0005055214.tif 000015
【図１５】
0005055214.tif 000016
【図１６】
0005055214.tif 000017