(57)【特許請求の範囲】
【請求項１】
仮想の３次元オブジェクトが位置する仮想オブジェクト空間を複数のサブ空間に分割する単一の空間分割部と、
前記分割された各サブ空間に対応し、前記対応する各サブ空間に入射した光線の前記各サブ空間内における軌跡を算出する複数のプロセッサと、
を含み、
前記空間分割部は、前記光線が前記各サブ空間に入射される頻度がイコライズされるように前記仮想オブジェクト空間を前記複数のサブ空間に分割し、分割された複数のサブ空間を各プロセッサに割り当てることを特徴とする３次元映像プロセッサ。
【請求項２】
前記分割されたサブ空間のうち、第１サブ空間内の光線が前記第１サブ空間と異なる第２サブ空間に入射されれば、前記第１サブ空間に対応する第１プロセッサは前記光線の軌跡情報を格納し、
前記第２サブ空間に対応する第２プロセッサは、前記光線の前記第２サブ空間内における軌跡を算出することを特徴とする請求項１に記載の３次元映像プロセッサ。
【請求項３】
前記空間分割部は、前記サブ空間の間の境界を仮想平面に設定し、
前記第２プロセッサは、前記光線が前記第１サブ空間および前記第２サブ空間の間の前記仮想平面と前記光線が当る点を仮想ノードに設定し、前記設定された仮想ノードから前記光線が前記第２サブ空間に入射したものと仮定して前記光線の前記軌跡を算出することを特徴とする請求項２に記載の３次元映像プロセッサ。
【請求項４】
前記光線の軌跡情報は、前記光線が前記第２サブ空間に入射される時の角度および前記光線が前記第２サブ空間に入射される時の強度を含むことを特徴とする請求項２に記載の３次元映像プロセッサ。
【請求項５】
前記複数の各プロセッサは、前記対応する各サブ空間に対して並列的に前記軌跡を算出することを特徴とする請求項１に記載の３次元映像プロセッサ。
【請求項６】
前記複数の各プロセッサは、前記光線および前記対応する各サブ空間内の前記仮想の３次元オブジェクト間の衝突によって変化する前記光線の軌跡を算出することを特徴とする請求項１に記載の３次元映像プロセッサ。
【請求項７】
前記複数の各プロセッサは、前記対応する各サブ空間の前記仮想の３次元オブジェクトから生成されたサブ空間モデルデータを格納し、前記対応するサブ空間内で前記仮想の３次元オブジェクトが変化すれば、前記格納されたサブ空間モデルデータを更新することを特徴とする請求項１に記載の３次元映像プロセッサ。
【請求項８】
前記複数の各プロセッサは、前記光線および前記対応する各サブ空間内の前記仮想の３次元オブジェクト間の衝突回数が閾値以上であれば、前記光線の軌跡の算出を終了することを特徴とする請求項１に記載の３次元映像プロセッサ。
【請求項９】
前記複数の各プロセッサは、前記光線の各色の強度が閾値以下であれば、前記光線の軌跡の算出を終了することを特徴とする請求項１に記載の３次元映像プロセッサ。
【請求項１０】
前記空間分割部は、前記仮想オブジェクト空間の領域別の複雑度に基づいて前記仮想オブジェクト空間を前記複数のサブ空間に分割することを特徴とする請求項１に記載の３次元映像プロセッサ。
【請求項１１】
単一の空間分割部が、仮想の３次元オブジェクトが位置する仮想オブジェクト空間を複数のサブ空間に分割するステップと、
複数のプロセッサが、前記分割された各サブ空間に入射される光線の前記入射したサブ空間内における軌跡を算出するステップと、を含み、
前記光線の前記入射したサブ空間内における軌跡を算出するステップは、互いに異なる入射したサブ空間に対して並列的に行なわれ、
前記複数のサブ空間に分割するステップは、前記光線が前記各サブ空間に入射される頻度がイコライズされるように前記仮想オブジェクト空間が前記複数のサブ空間に分割され、分割された複数のサブ空間が前記複数のプロセッサの各々に割り当てられることを特徴とする３次元映像プロセッシング方法。
【請求項１２】
前記分割されたサブ空間のうち、第１サブ空間内の光線が前記第１サブ空間と異なる第２サブ空間に入射されれば、前記光線の軌跡情報を格納するステップと、
前記格納された軌跡情報から前記光線の前記第２サブ空間内における軌跡を算出するステップと、
をさらに含むことを特徴とする請求項１１に記載の３次元映像プロセッシング方法。
【請求項１３】
前記分割されたサブ空間の間の境界を仮想平面に設定するステップをさらに含み、
前記光線の軌跡情報は、前記第１サブ空間および前記第２サブ空間の間の前記仮想平面と前記光線が当る点における前記光線の方向、強度および以前の衝突回数を含むことを特徴とする請求項１２に記載の３次元映像プロセッシング方法。
【請求項１４】
請求項１１ないし１３のいずれか一項の方法を実行するためのプログラムが記録されていることを特徴とするコンピュータで読み出し可能な記録媒体。
【請求項１５】
仮想の３次元オブジェクトが位置する仮想オブジェクト空間を複数のサブ空間に分割する単一の空間分割部と、
前記複数のサブ空間にそれぞれ対応する複数のプロセッサであって、各プロセッサは対応されるサブ空間を通過する光線の軌跡を算出する前記複数のプロセッサと、
を含み、
前記空間分割部は、前記光線が前記各サブ空間に入射される頻度がイコライズされるように前記仮想オブジェクト空間を前記複数のサブ空間に分割し、分割された複数のサブ空間を各プロセッサに割り当てることを特徴とする３次元映像処理装置。
【請求項１６】
前記算出は、前記複数の各プロセッサが対応するサブ空間内における光線の軌跡の算出、前記光線が衝突するオブジェクト座標の算出、および前記オブジェクトに衝突した前記光線の補助成分係数の算出のうち、少なくとも１つを含むことを特徴とする請求項１５に記載の３次元映像処理装置。
【請求項１７】
前記光線の補助成分係数は、反射成分、透過成分およびシャドウ成分のうち、少なくとも１つを含むことを特徴とする請求項１６に記載の３次元映像処理装置。
【請求項１８】
前記複数のプロセッサは、それぞれ対応するサブ空間に対して並列的に算出を行うことを特徴とする請求項１５に記載の３次元映像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元映像プロセッサおよびプロセッシング方法に関し、特にレイトレーシング（ｒａｙ  ｔｒａｃｉｎｇ）技法を用いる３次元映像プロセッサおよびプロセッシング方法に関する。
【背景技術】
【０００２】
３次元映像プロセッシングは、ＴＶまたはモニタなどの平面ディスプレイ上に実際の映像と類似の画面を生成する技術である。３次元映像プロセッシングは、仮想（ｖｉｒｔｕａｌ）の立体オブジェクトが置かれる仮想の立体空間を設定し、仮想の光源と仮想の立体オブジェクトの関係に応じて観察者の視点で見ることのできる映像をシミュレートする。
【０００３】
３次元映像プロセッシングは、仮想の立体空間および仮想の立体オブジェクトをモデリングする過程と、モデリングされた仮想の立体オブジェクトが観察者の視点に投影される映像を抽出する過程とに区分されてもよい。仮想の立体オブジェクトから観察者の視点に投影される映像を抽出する過程を３次元レンダリングとも称する。
【０００４】
レイトレーシングは、３次元レンダリングの１つの技法である。
【０００５】
実際の世界では１つ以上の光源から出発した光線（ｒａｙ）がオブジェクトに当って反射および／または屈折することによって、方向および／または強度が変化し、変化した１つ以上の光線が合算されて観察者の視点を形成する。
【０００６】
レイトレーシングは実際の世界における光線の軌跡を逆に追跡する技法であって、観察者の視点から１つ以上の光線を生成し、生成された１つ以上の光線がオブジェクトに当って反射および／または屈折することによって変化する過程を追跡する。レイトレーシングは、平面ディスプレイを構成するピクセル（ｐｉｘｅｌ）それぞれを観察者の視点で設定し、ピクセルそれぞれから生成された１つ以上の光線の変化を追跡してピクセルそれぞれの色を決定する。
【０００７】
一般的に、レイトレーシングを用いて現実感あふれる３次元映像を提供するためには、光線およびオブジェクトの数が増加するため、レイトレーシング技法による３次元レンダリングは極めて多くの算出量を要求する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明における３次元映像プロセッサまたはプロセッシング方法の目的は、新しい演算アルゴリズムを用いることによって、レイトレーシング技法を用いる場合に算出量の軽減を提供することにある。
【０００９】
本発明における３次元映像プロセッサまたはプロセッシング方法の目的は、レイトレーシング技法を用いる場合の算出量を減らし、並列的に算出を行なうことによって３次元映像の提供に所要される時間の短縮を提供することにある。
【００１０】
本発明における３次元映像プロセッサまたはプロセッシング方法の目的は、レイトレーシング技法を用いる場合の算出量を減らすことによって、リアルタイムの３次元映像を提供することにある。
【００１１】
本発明における３次元映像プロセッサまたはプロセッシング方法の目的は、並列レイトレーシング技法を用いる場合にメモリ使用量の軽減を提供することにある。
【課題を解決するための手段】
【００１２】
本発明の一実施形態に係る３次元映像プロセッサは、仮想の３次元オブジェクトが位置する仮想オブジェクト空間を複数のサブ空間に分割する空間分割部と、前記分割された各サブ空間に対応する複数のプロセッサとを含んでもよい。複数のプロセッサは、前記対応する各サブ空間に入射した光線の前記各サブ空間内における軌跡を算出してもよい。
【００１３】
本発明の他の実施形態に係る３次元映像プロセッシング方法は、仮想の３次元オブジェクトが位置する仮想オブジェクト空間を複数のサブ空間に分割するステップと、前記分割された各サブ空間に入射される光線の前記入射したサブ空間内における軌跡を算出するステップとを含んでもよい。前記光線の前記入射したサブ空間内における軌跡を算出するステップは、互いに異なる入射されたサブ空間に対して並列的に行なわれてもよい。
【発明の効果】
【００１４】
本発明の一実施形態に係る３次元映像プロセッサまたはプロセッシング方法は、新しい演算アルゴリズムを用いることによってレイトレーシング技法を用いる場合の算出量を減らすことができる。
【００１５】
本発明の一実施形態に係る３次元映像プロセッサまたはプロセッシング方法は、レイトレーシング技法を用いる場合の算出量を減らし、並列的に算出を行なうことによって、３次元映像の提供に所要される時間を短縮することができる。
【００１６】
本発明の一実施形態に係る３次元映像プロセッサまたはプロセッシング方法は、レイトレーシング技法を用いる場合の算出量を減らすことによって、リアルタイムの３次元映像を提供することができる。
【００１７】
本発明の一実施形態に係る３次元映像プロセッサまたはプロセッシング方法は、並列レイトレーシング技法を用いる場合のメモリ使用量を減らすことができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施形態に係る３次元映像プロセッシング方法を示す図である。
【図２】本発明の他の実施形態に係る３次元映像プロセッシング方法を示す図である。
【図３】本発明の他の実施形態に係る３次元映像プロセッシング方法を示す図である。
【図４】図１における３次元映像プロセッシング方法が行なわれる３次元映像プロセッサを示す図である。
【図５】図３における実施形態において第１時間区間の間の算出過程を示す図である。
【図６】図３における実施形態において第２時間区間の間の算出過程を示す図である。
【図７】本発明の他の実施形態に係る３次元映像プロセッシング方法で仮想の３次元モデルデータを更新する過程を示す図である。
【図８】本発明の一実施形態に係る３次元映像プロセッシング方法を示す動作フローチャートである。
【発明を実施するための形態】
【００１９】
以下、本発明に係る好適な実施形態を添付の図面を参照して詳細に説明する。しかし、本発明が実施形態によって制限されたり限定されることはない。各図面に提示される同一の参照符号は同一の部材を示す。
【００２０】
図１は、本発明の一実施形態に係る３次元映像プロセッシング方法を示す図である。図１を参照すれば、仮想の３次元オブジェクトが位置する仮想オブジェクト空間は、４個のサブ空間１１０、１２０、１３０、１４０に分割される。
【００２１】
レイトレーシング（ｒａｙ  ｔｒａｃｉｎｇ）技法は、ディスプレイ画面上のピクセルそれぞれを目（ｅｙｅ）と仮定し、ピクセルそれぞれから仮想オブジェクト空間に入射される光線（ｒａｙ）の軌跡を算出することができる。
【００２２】
３次元映像プロセッシング方法は、分割された４個のサブ空間１１０、１２０、１３０、１４０それぞれに対して３次元オブジェクトに対する仮想モデルデータを維持し、分割された４個のサブ空間１１０、１２０、１３０、１４０それぞれに対して仮想モデルデータを用いて入射した光線の軌跡を算出することができる。
【００２３】
分割された４個のサブ空間１１０、１２０、１３０、１４０それぞれに対してプロセッサ（図示せず）が割り当てられてもよい。例えば、プロセッサ１はサブ空間１１０に割り当てられてもよい。
【００２４】
仮想オブジェクト１１１はサブ空間１１０内に位置する。仮想オブジェクト１１１を含むサブ空間１１０の３次元モデルデータは、バッファメモリ１（図示せず）に格納されてもよい。プロセッサ１は、バッファメモリ１に格納されたサブ空間１１０の３次元モデルデータを用いてサブ空間１１０に入射される光線の軌跡を算出することができる。
【００２５】
該当のピクセルから光線１１２はサブ空間１１０に入射される。プロセッサ１は、光線１１２のサブ空間１１０内における軌跡を算出することができる。バッファメモリ１に格納されたサブ空間１１０の３次元モデルデータは、仮想オブジェクト１１１の境界をなす点の座標を含んでもよい。プロセッサ１は、光線１１２の進行方向に沿って光線１１２が仮想オブジェクト１１１に当るか否かを追跡することができる。
【００２６】
光線１１２は、仮想オブジェクト１１１に当る点で反射されてもよく、仮想オブジェクト１１１に透過または屈折されてもよい。光線１１２は、仮想オブジェクト１１１に当る点で反射光線、透過光線、および影光線に分けられてもよい。影光線は、直接光線とも呼ばれてもよい。光源からの光が他のオブジェクトによって遮られなければ、影光線から光の強度が分かる。
【００２７】
プロセッサ１は、光線１１２が仮想オブジェクト１１１に当る点で反射光線の係数、透過光線の係数および影光線の係数を算出し、光線１１２が仮想オブジェクト１１１に当る点の座標とともに算出された各光線の係数をバッファメモリ１または他のメモリに格納してもよい。
【００２８】
本明細書では、説明の便宜上、反射光線の反射比率を反射係数、透過光線の透過比率を透過係数と称することにする。これらの名称は、簡単な説明のために導入されたものであって、これらの名称によって本発明の権利範囲が狭く解釈されてはならない。
【００２９】
プロセッサ１は、光線１１２が仮想オブジェクト１１１に当る点の座標、反射係数、透過係数および影係数を格納することができる。プロセッサ１は反射光線の進行方向に沿って反射光線の軌跡を引き続き追跡することができる。反射光線が他の３次元オブジェクトに当ると、プロセッサ１は反射光線が前記の他の３次元オブジェクトに当る点で反射係数、透過係数および影係数を算出することができる。反射光線がサブ空間１１０の境界に当ると、プロセッサ１は、反射光線がサブ空間１１０の境界に当る点の座標を格納して算出を終了してもよい。
【００３０】
以上でサブ空間１１０、仮想オブジェクト１１１および光線１１２について説明したが、残りのサブ空間、残りの仮想オブジェクトおよび残りの光線についても同一の内容が適用され得る。例えば、プロセッサ２はサブ空間１２０に割り当てられてもよく、プロセッサ３はサブ空間１３０に割り当てられてもよく、プロセッサ４はサブ空間１４０に割り当てられてもよい。
【００３１】
仮想オブジェクト１２１はサブ空間１２０内に位置する。仮想オブジェクト１２１を含むサブ空間１２０の３次元モデルデータは、バッファメモリ２（図示せず）に格納されてもよい。プロセッサ２はバッファメモリ２に格納されたサブ空間１２０の３次元モデルデータを用いて、サブ空間１２０に入射される光線の軌跡を算出することができる。該当のピクセルから光線１２２はサブ空間１２０に入射される。プロセッサ２は光線１２２のサブ空間１２０内における軌跡を算出することができる。
【００３２】
仮想オブジェクト１３１はサブ空間１３０内に位置する。仮想オブジェクト１３１を含むサブ空間１３０の３次元モデルデータはバッファメモリ３（図示せず）に格納されてもよい。プロセッサ３はバッファメモリ３に格納されたサブ空間１３０の３次元モデルデータを用いて、サブ空間１３０に入射される光線の軌跡を算出することができる。該当のピクセルから光線１３２はサブ空間１３０に入射される。プロセッサ３は光線１３２のサブ空間１３０内における軌跡を算出することができる。
【００３３】
仮想オブジェクト１４１はサブ空間１４０内に位置する。仮想オブジェクト１４１を含むサブ空間１４０の３次元モデルデータはバッファメモリ４（図示せず）に格納されてもよい。プロセッサ４は、バッファメモリ４に格納されたサブ空間１４０の３次元モデルデータを用いて、サブ空間１４０に入射される光線の軌跡を算出することができる。該当のピクセルから光線１４２はサブ空間１４０に入射される。プロセッサ４は光線１４２のサブ空間１４０内における軌跡を算出することができる。
【００３４】
図１において、４個のサブ空間１１０、１２０、１３０、１４０それぞれに対して１つの光線１１２、１２２、１３２、１４２が入射される場合を示したが、本発明の実施形態はこれに限定されることなく、サブ空間それぞれに複数の光線が入射される場合もあり得る。
【００３５】
実施形態によっては、同一の時間区間ではプロセッサは１つずつの光線の軌跡を算出することができる。すなわち、同一の時間区間にプロセッサ１は光線１１２の軌跡を算出し、プロセッサ２は光線１２２の軌跡を算出し、プロセッサ３は光線１３２の軌跡を算出し、プロセッサ４は光線１４２の軌跡を算出してもよい。
【００３６】
図２は、本発明の他の実施形態に係る３次元映像プロセッシング方法を示す図である。図２を参照すれば、３次元仮想オブジェクトが位置した３次元仮想空間は２つのサブ空間２１０、２２０に分割される。
【００３７】
３次元映像プロセッシング方法は、特定のピクセルを目と仮定し、ピクセルから２つのサブ空間２１０、２２０に入射される光線２１２、２２２の軌跡を算出する。
【００３８】
サブ空間２１０にはプロセッサ１（図示せず）が割り当てられてもよい。プロセッサ１は、サブ空間２１０に入射される光線２１２の軌跡を算出する。
【００３９】
仮想オブジェクト２１１はサブ空間２１０に位置する。プロセッサ１は仮想オブジェクト２１１を含むサブ空間２１０の３次元モデルデータを格納してもよく、またはバッファメモリ（図示せず）に格納された３次元モデルデータを読み出してもよい。
【００４０】
光線２１２が仮想オブジェクト２１１の境界面に当る点が探索されれば、プロセッサ１は、光線２１２が仮想オブジェクト２１１の境界面に当る点で反射された光線２１３の進行方向および反射された光線２１３の反射比率を算出することができる。プロセッサ１は、光線２１３の進行方向に沿って光線２１３が仮想平面２３０に当る点２３１が存在するか否かを探索することができる。仮想平面２３０は、サブ空間２１０およびサブ空間２２０の境界を示す平面である。
【００４１】
光線２１３が仮想平面２３０に当る点２３１が探索されれば、プロセッサ１は点２３１で光線２１３の進行方向および光線２１３の反射比率を格納して算出シーケンスを終了してもよい。また、プロセッサ１は、点２３１まで達する前の光線２１３の反射回数を格納してもよい。光線２１３は、光線２１２が仮想オブジェクト２１１に当る点で反射された光線であるため、光線２１３の反射回数は１回である。
【００４２】
サブ空間２２０にはプロセッサ２（図示せず）が割り当てられてもよい。プロセッサ２はサブ空間２２０に入射される光線２２２の軌跡を算出する。
【００４３】
仮想オブジェクト２２１はサブ空間２２０に位置する。プロセッサ２は、仮想オブジェクト２２１を含むサブ空間２２０の３次元モデルデータを格納してもよく、またはバッファメモリ（図示せず）に格納された３次元モデルデータを読み出してもよい。
【００４４】
サブ空間２２０の３次元モデルデータは、仮想オブジェクト２２１の境界面を形成する点の座標情報を含んでもよい。プロセッサ２は、光線２２２の進行方向に沿って光線２２２が仮想オブジェクト２２１の境界面に当る点が存在するか否かを探索することができる。
【００４５】
光線２２２が仮想オブジェクト２２１の境界面に当る点が探索されれば、プロセッサ２は、光線２２２が仮想オブジェクト２２１の境界面に当る点で反射された光線２２３の進行方向および反射された光線２２３の係数を算出することができる。プロセッサ２は、光線２２３の進行方向に沿って光線２２３が仮想平面２３０に当る点２３２が存在する否かを探索することができる。
【００４６】
光線２２３が仮想平面２３０に当る点２３２が探索されれば、プロセッサ２は、点２３２で光線２２３の進行方向および光線２２３の係数を格納して算出シーケンスを終了してもよい。また、プロセッサ２は、点２３２まで達する前の光線２２３の反射回数を格納してもよい。光線２２３は、光線２２２が仮想オブジェクト２２１に当る点で反射された光線であるため、光線２２３の反射回数は１回である。
【００４７】
図３は、本発明の他の実施形態に係る３次元映像プロセッシング方法を示す図である。図３を参照すれば、３次元仮想オブジェクトが位置した３次元仮想空間は２つのサブ空間３１０、３２０に分割される。
【００４８】
プロセッサ１（図示せず）はサブ空間３１０に割り当てられ、プロセッサ２（図示せず）はサブ空間３２０に割り当てられてもよい。第１時間区間の間にプロセッサ１は、サブ空間３１０内の光線３１２および光線３１３の軌跡を算出することができる。光線３１３が仮想平面３３０に当る点３３１が探索されれば、プロセッサ１は、点３３１で光線３１３の進行方向および係数を格納し、第１時間区間の算出過程を終了してもよい。
【００４９】
第１時間区間の間にプロセッサ２は、サブ空間３２０内の光線３２２および光線３２３の軌跡を算出することができる。光線３２３が仮想平面３３０に当る点３３２が探索されれば、プロセッサ２は点３３２で光線３２３の進行方向および係数を格納し、第１時間区間の算出過程を終了してもよい。
【００５０】
第１時間区間の間にプロセッサ１およびプロセッサ２はそれぞれサブ空間３１０およびサブ空間３２０内の光線の軌跡を算出することができる。プロセッサ１およびプロセッサ２の算出過程は並列的に行なわれてもよい。
【００５１】
第２時間区間の間にプロセッサ１は、点３３２からサブ空間３１０に入射した光線３１４、光線３１５および光線３１６のサブ空間３１０内における軌跡を算出することができる。点３３２で光線３１４の進行方向および係数は点３３２で光線３２３の進行方向および係数と同一であってもよい。プロセッサ１は、光線３１４の進行方向に沿って光線３１４が仮想オブジェクト３１１またはサブ空間３１０の境界面に当る点が存在するか否かを探索することができる。
【００５２】
光線３１４がサブ空間３１０の後方の境界面に当る点が探索されれば、プロセッサ１は反射した光線３１５の進行方向および係数を算出することができる。同様な方法によりプロセッサ１は、光線３１５がサブ空間３１０の左側の境界面に当る点で反射した光線３１６の進行方向および係数を算出することができる。
【００５３】
光線３１６が仮想平面３３０に当る点３３４が探索されれば、プロセッサ１は、点３３４で光線３１６の進行方向および係数を格納して第２時間区間の算出過程を終了してもよい。
【００５４】
第２時間区間の間にプロセッサ２は、点３３１からサブ空間３２０に入射した光線３２４、光線３２５、光線３２６および光線３２７のサブ空間３２０内における軌跡を算出することができる。点３３１において光線３２４の進行方向および係数は点３３１において光線３１３の進行方向および係数と同一であってもよい。プロセッサ２は、光線３２４の進行方向に沿って光線３２４が仮想オブジェクト３２１またはサブ空間３２０の境界面に当る点が存在するか否かを探索することができる。
【００５５】
光線３２４がサブ空間３２０の下側の境界面に当る点が探索されれば、プロセッサ２は、反射した光線３２５の進行方向および係数を算出することができる。光線３２５が仮想オブジェクト３２１の境界面に当る点が探索されれば、プロセッサ２は反射した光線３２６の進行方向および係数を算出することができる。光線３２６がサブ空間３２０の右側の境界面に当る点が探索されれば、プロセッサ２は反射した光線３２７の進行方向および係数を算出することができる。光線３２７が仮想平面３３０に当る点３３３が探索されれば、プロセッサ２は、点３３３で光線３２７の進行方向および係数を格納して第２時間区間の算出過程を終了してもよい。
【００５６】
プロセッサ１は、サブ空間３１０の３次元モデルデータに基づいてサブ空間３１０内の光線の軌跡を算出することができる。このとき、プロセッサ１は、他のサブ空間３２０の３次元モデルデータを考慮する必要がないことから、算出過程に必要なメモリの格納容量を減らすことができる。また、レイトレーシング技法では、光線の進行方向による位置座標と３次元モデルデータの座標とを比較し、仮想オブジェクトと光線とが当ることを探索するため、考慮される３次元モデルデータの量が少ないほど光線の軌跡を算出する時間を減らすことができる。プロセッサ１は、サブ空間３１０の３次元モデルデータから光線の軌跡を算出するため、サブ空間３１０およびサブ空間３２０の３次元モデルデータを全て考慮する場合よりも算出過程の時間も短縮できる。
【００５７】
プロセッサ２もサブ空間３２０の３次元モデルデータに基づいてサブ空間３２０内の光線の軌跡を算出することができる。このとき、プロセッサ２は、他のサブ空間３１０の３次元モデルデータを考慮する必要がないため、算出過程に必要なメモリの格納容量を減らすことができる。プロセッサ２は、サブ空間３２０の３次元モデルデータから光線の軌跡を算出するため、サブ空間３１０およびサブ空間３２０の３次元モデルデータを全て考慮する場合よりも算出過程の時間も短縮できる。
【００５８】
本発明の他の実施形態によれば、全体の仮想空間をＰ個のサブ空間に分割し、Ｐ個のサブ空間それぞれに１つずつのプロセッサが割り当てられて並列的に光線の軌跡を算出することができる。このとき、各プロセッサは従来のプロセッサが必要とするメモリ格納容量の１／Ｐだけのメモリ格納容量を必要とする。各プロセッサは、従来のプロセッサが行う算出の１／Ｐだけの算出を行なってもよい。各プロセッサは、従来のプロセッサの算出過程に所要される時間の１／Ｐだけの時間の間に算出過程を行なってもよい。
【００５９】
本実施形態では３次元映像のプロセッシング過程において処理されなければならない全ての光線をＰ個のプロセッサが分けて並列的に処理し、各プロセッサは従来のプロセッサよりもＰ倍早く算出過程を行なうことができるため、全体の３次元映像のプロセッシング過程において所要される時間は１／Ｐ２に減らすことができる。
【００６０】
再び図３を参照すれば、プロセッサ１は、第１時間区間の算出過程が終了した後、仮想平面３３０からサブ空間３１０に入射される光線が存在するか否かを探索することができる。図３に示すように、サブ空間３２０から点３３２を経由してサブ空間３１０に入射される光線３１４が探索されるので、プロセッサ１は、探索された光線３１４およびその反射された光線３１５、３１６のサブ空間３１０内における軌跡を算出することができる。
【００６１】
反射した光線が終了条件を満たせば、プロセッサは該当の光線の軌跡を算出する過程を終了してもよい。各時間区間が終了した後、プロセッサ１は、仮想平面３３０からサブ空間３１０に入射される光線が存在するか否かを探索することができる。プロセッサ１は、仮想平面３３０からサブ空間３１０に入射される光線が終了条件を満たすか否かを判定でき、仮想平面３３０からサブ空間３１０に入射される光線が終了条件を満たせば、プロセッサ１は、仮想平面３３０からサブ空間３１０に入射される光線に対する算出を行なわなくてもよい。
【００６２】
仮想平面３３０からサブ空間３１０に入射される光線が終了条件を満たせば、プロセッサ１は、ピクセルからサブ空間３１０に入射される他の光線が存在するか否かを探索することができる。図３においては詳細に示されてはいないが、レイトレーシング技法では１つのピクセルから多数の光線を３次元仮想空間に入射させ、その軌跡を探索することができる。プロセッサ１は、１つの入射した光線に対する算出過程が終了すれば、次の入射した光線を探索して新しく探索された光線のサブ空間３１０内における軌跡を算出することができる。
【００６３】
光線の算出を終了する終了条件の例として、次のようなものが挙げられる。光線それぞれは仮想オブジェクトに当る点で反射し、反射した光線の強度は減少する。終了条件は、反射した光線の強度が基準値よりも小さい条件であってもよい。または、終了条件は、光線が仮想オブジェクトに当る点で反射した累積回数が基準値よりも大きい条件であってもよい。終了条件が満たされたか否かが判定される時点は、光線が仮想オブジェクトに当る時点であってもよく、時間区間それぞれが終了する時点であってもよい。
【００６４】
図４は、図１の３次元映像プロセッシング方法が行なわれる３次元映像プロセッサ４００を示す図である。図４を参照すれば、３次元映像プロセッサ４００は、空間分割部４１０および４個のプロセッサ４２０、４３０、４４０、４５０を含む。
【００６５】
空間分割部４１０は、仮想の３次元オブジェクトが位置する仮想オブジェクト空間を４個のサブ空間４６０、４７０、４８０、４９０に分割する。空間分割部４１０は、分割されたサブ空間４６０、４７０、４８０、４９０に対する情報を各プロセッサ４２０、４３０、４４０、４５０に伝達する。
【００６６】
空間分割部４１０は、分割されたサブ空間４６０、４７０、４８０、４９０を１つずつプロセッサ４２０、４３０、４４０、４５０に割り当ててもよい。
【００６７】
プロセッサ１（４２０）はサブ空間４６０に対応する。プロセッサ１（４２０）は対応するサブ空間４６０に入射した光線のサブ空間４６０内における軌跡を算出する。
【００６８】
プロセッサ２（４３０）はサブ空間４７０に対応する。プロセッサ２（４３０）は、対応するサブ空間４７０に入射した光線のサブ空間４７０内における軌跡を算出する。
【００６９】
プロセッサ３（４４０）はサブ空間４８０に対応する。プロセッサ３（４４０）は、対応するサブ空間４８０に入射した光線のサブ空間４８０内における軌跡を算出する。
【００７０】
プロセッサ４（４５０）はサブ空間４９０に対応する。プロセッサ４（４５０）は、対応するサブ空間４９０に入射した光線のサブ空間４９０内における軌跡を算出する。
【００７１】
サブ空間４６０内の光線がサブ空間４８０に入射されれば、プロセッサ１（４２０）は光線の軌跡情報を格納し、算出過程を終了してもよい。光線が新しく入射したサブ空間４８０に対応するプロセッサ３（４４０）は、サブ空間４８０内における入射した光線の軌跡を算出することができる。
【００７２】
格納される軌跡情報は、光線がサブ空間４８０に入射される時の角度および光線がサブ空間４３０に入射される時の強度を含んでもよい。
【００７３】
１つの時間区間の間に各プロセッサ４２０、４３０、４４０、４５０は、対応するサブ空間４６０、４７０、４８０、４９０内の光線の軌跡を算出することができる。時間区間が終了した後に各プロセッサ４２０、４３０、４４０、４５０は、他のサブ空間４６０、４７０、４８０、４９０から対応するサブ空間４６０、４７０、４８０、４９０に入射される光線が存在するか否かを探索することができる。例えば、他のサブ空間４６０、４８０、４９０からサブ空間４７０に入射される光線が探索されれば、サブ空間４７０に対応するプロセッサ２（４３０）は入射した光線の軌跡を算出することができる。他のサブ空間４６０、４８０、４９０からサブ空間４７０に入射される光線が探索されなければ、サブ空間４７０に対応するプロセッサ２（４３０）は、ピクセルからサブ空間４７０に入射される他の光線を探索することができる。
【００７４】
各プロセッサ４２０、４３０、４４０、４５０は、対応する各サブ空間４６０、４７０、４８０、４９０に対して並列的に光線の軌跡を算出することができる。
【００７５】
空間分割部４１０は、分割されたサブ空間４６０、４７０、４８０、４９０の間の境界を仮想平面に設定してもよい。サブ空間４６０内の光線がサブ空間４８０に入射されれば、サブ空間４８０に対応するプロセッサ３（４４０）は、光線が仮想平面に当る点を仮想ノードとして設定してもよい。プロセッサ２４４０は、光線が仮想ノードからサブ空間４８０に入射されたものと仮定し、入射した光線の軌跡を算出することができる。
【００７６】
プロセッサ１（４２０）は、サブ空間４６０に入射した光線およびサブ空間４６０内の仮想の３次元オブジェクト間の衝突によって変化する光線の軌跡を算出することができる。このとき、光線は仮想の３次元オブジェクトとの衝突によって反射されるか、または屈折され得る。屈折は、仮想の３次元オブジェクト内に光線が進むことであるため、透過と呼んでもよい。
【００７７】
プロセッサ１（４２０）は、光線と仮想の３次元オブジェクトとの衝突回数が閾値以上であれば光線の軌跡の算出を終了してもよい。プロセッサ１（４２０）は、光線と仮想の３次元オブジェクトとの衝突回数を累積加算して格納し、累積加算された衝突回数が閾値以上であるか否かを判定することができる。
【００７８】
プロセッサ２（４３０）は、光線の各色の強度が閾値以下であれば、光線の軌跡の算出を終了してもよい。光線は、赤色（Ｒｅｄ）、緑色（Ｇｒｅｅｎ）、青色（Ｂｌｕｅ）の３つのコンポーネントからなる。プロセッサ２（４３０）は、光線が仮想の３次元オブジェクトと衝突するたびに透過光線、反射光線または影光線を算出することができる。
【００７９】
プロセッサ２（４３０）は、反射光線の進行方向に沿って反射光線が異なる仮想の３次元オブジェクトと衝突するか否かを判定することができる。プロセッサ２（４３０）は、反射光線が異なる仮想の３次元オブジェクトと衝突すれば、新しい衝突による新しい透過係数、影係数および反射係数を算出することができる。
【００８０】
このとき、プロセッサ２（４３０）は、以前の衝突によって生成された透過係数の積および以前の衝突によって生成された反射係数の積を格納してもよい。前記格納される以前の衝突によって生成された透過係数および以前の衝突によって生成された反射係数の積をアンセスター（ａｎｃｅｓｔｏｒ）と言える。
【００８１】
プロセッサ２（４３０）は、光線のアンセスターの係数の積を最終決定された基準色（これを葉節点（ｌｅａｆ  ｎｏｄｅ）の色とする）に乗算することによって、光線のピクセルに対する最終色を算出することができる。プロセッサ２（４３０）は、現在の反射光線の各色の強度（アンセスターの反射係数の積）が閾値以下であれば、光線の軌跡に対する算出を終了し、光線のアンセスターとして格納された係数を合算して光線のピクセルに対する最終強度（または明度）値を算出することができる。葉節点は、１つの光線によって１つのピクセルに形成される色を示す。１つのピクセルには多数の光線によって色が形成され得るので、複数の葉節点によって形成される色を全て合算すれば、前記ピクセルの色が最終決定されることができる。
【００８２】
空間分割部４１０は、仮想オブジェクト空間の領域別に複雑度に基づいて仮想オブジェクト空間を４個のサブ空間４６０、４７０、４８０、４９０に分割してもよい。空間分割部４１０は、分割された各サブ空間４６０、４７０、４８０、４９０の複雑度が互いに類似のレベルになるよう仮想オブジェクト空間を分割してもよい。
【００８３】
レイトレーシング技法では、１つのピクセルから多数の光線が仮想オブジェクト空間に入射されてもよい。空間分割部４１０は、光線が各サブ空間４６０、４７０、４８０、４９０に入射される頻度がイコライズ（ｅｑｕａｌｉｚｅ）されるように仮想オブジェクト空間を分割してもよい。光線が各サブ空間４６０、４７０、４８０、４９０に入射される頻度がイコライズされれば、各サブ空間４６０、４７０、４８０、４９０に対応するプロセッサ４２０、４３０、４４０、４５０の算出負荷が均衡的に割り当てられることから、算出過程の並列性を向上させることができる。
【００８４】
図５は、図３に示す実施形態において第１時間区間の間の算出過程を示す図である。
【００８５】
図３および図５を参照すれば、プロセッサ１はサブ空間３１０に割り当てられ、プロセッサ２はサブ空間３２０に割り当てられる。
【００８６】
矢印５１１はサブ空間３１０に入射した光線３１２に対応する。
【００８７】
ノード５１５は、光線３１２が仮想オブジェクト３１１と衝突する点に対応する。
【００８８】
プロセッサ１は、光線３１２の進行方向、光線３１２の強度、仮想オブジェクト３１１の境界面の情報および仮想オブジェクト３１１の透明度情報に基づいて、反射光線３１３の進行方向および係数を算出し、影光線の進行方向および係数を算出し、透過光線の進行方向および係数を算出することができる。
【００８９】
矢印５１２は影光線に対応し、ノード５１７は影係数に対応する。矢印５１３は透過光線に対応し、ノード５１８は透過係数に対応する。矢印５１４は反射光線３１３に対応する。光線３１３が仮想平面３３０に当ると、プロセッサ１は点３３１の座標とともに光線３１３の係数および進行方向を格納することができる。このとき、プロセッサ１は、点３３１の座標とともに光線３１３のアンセスターとしてノード５１７の影係数およびノード５１８の透過係数を格納してもよい。プロセッサ１は点３３１の座標とともに光線３１３の情報およびアンセスター情報を格納し、第１時間区間の算出過程を終了してもよい。ノード５１６は点３３１に対応する。
【００９０】
矢印５２１はサブ空間３２０に入射した光線３２２に対応する。
【００９１】
ノード５２５は光線３２２が仮想オブジェクト３２１と衝突する点に対応する。
【００９２】
プロセッサ２は、光線３２２の進行方向、光線３２２の強度、仮想オブジェクト３２１の境界面の情報および仮想オブジェクト３２１の透明度情報に基づいて反射光線３２３の進行方向および係数を算出し、影光線の進行方向および係数を算出し、透過光線の進行方向および係数を算出することができる。
【００９３】
矢印５２２は影光線に対応し、ノード５２７は影係数に対応する。矢印５２３は透過光線に対応し、ノード５２８は透過係数に対応する。矢印５２４は反射光線３２３に対応する。光線３２３が仮想平面３３０に当ると、プロセッサ２は点３３２の座標とともに光線３２３の係数および進行方向を格納することができる。このとき、プロセッサ２は、点３３２の座標とともに光線３２３のアンセスターとしてノード５２７の影係数およびノード５２８の透過係数を格納してもよい。プロセッサ２は、点３３２の座標とともに光線３２３の情報およびアンセスター情報を格納し、第１時間区間の算出過程を終了してもよい。ノード５２６は点３３２に対応する。
【００９４】
図６は、図３の実施形態において第２時間区間の間の算出過程を示す図である。
【００９５】
図３および図６を参照すれば、プロセッサ１はサブ空間３１０に割り当てられ、プロセッサ２はサブ空間３２０に割り当てられる。
【００９６】
プロセッサ１は、点３３２からサブ空間３１０に入射した光線３１４の軌跡を算出する。ノード６３１は点３３２に対応する。
【００９７】
矢印６１１はサブ空間３１０に入射した光線３１４に対応する。
【００９８】
ノード６３２は、光線３１４がサブ空間３１０の後方の境界面と衝突する点に対応する。
【００９９】
プロセッサ１は、光線３１４の進行方向、光線３１４の強度、サブ空間３１０の後方の境界面の情報に基づいて反射光線３１５の進行方向および係数を算出することができる。プロセッサ１は、光線３１４がサブ空間３１０の後方の境界面と衝突する点において影光線の進行方向および係数を算出し、透過光線の進行方向および係数を算出することができる。
【０１００】
矢印６１４は影光線に対応し、ノード６３５は影係数に対応する。矢印６１５は透過光線に対応し、ノード６３６は透過係数に対応する。矢印６１２は反射光線３１５に対応する。
【０１０１】
プロセッサ１は、光線３１５の進行方向に沿って光線３１５の衝突の有無を探索することができる。光線３１５がサブ空間３１０の左側の境界面と衝突すれば、プロセッサ１は反射した光線３１６の軌跡を算出することができる。ノード６３３は、光線３１５がサブ空間３１０の左側の境界面と衝突する点に対応する。
【０１０２】
プロセッサ１は、ノード６３３に対応する点で影光線および透過光線を求めることができる。矢印６１６は影光線に対応し、ノード６３７は影係数に対応する。矢印６１７は透過光線に対応し、ノード６３８は透過係数に対応する。
【０１０３】
矢印６１３は反射光線３１６に対応する。プロセッサ１は光線３１６の進行方向に沿って光線３１６の軌跡を算出する。
【０１０４】
光線３１６が仮想平面３３０に当ると、プロセッサ１は点３３４の座標とともに光線３１６の係数および進行方向を格納することができる。このとき、プロセッサ１は、点３３４の座標とともに光線３１６のアンセスターとしてノード６３５、ノード６３７の影係数およびノード６３６、ノード６３８の透過係数を格納してもよい。プロセッサ１は、点３３４の座標とともに光線３１６の情報およびアンセスター情報を格納し、第２時間区間の算出過程を終了してもよい。ノード６３４は点３３４に対応する。
【０１０５】
プロセッサ１は、光線３１６の強度が基準値以上であるか否かを判定することができる。光線３１６の強度が基準値よりも小さければ、プロセッサ１は光線３１６に対する算出過程を終了してもよい。このとき、プロセッサ２は、光線３１６のサブ空間３２０内における軌跡を算出しなくてもよい。
【０１０６】
プロセッサ１は、光線３１６の強度および格納されたアンセスター係数（または、係数の積）を合算して光線３１６がピクセルに及ぼす色値を算出することができる。光線３１６は光線３２２から始まったため、前記合算された値は光線３２２がピクセルに及ぼす色値として見ることができる。
【０１０７】
格納されたアンセスター情報（アンセスターの係数）は光線が進行方向を変えるたびに生成される付随的な明度（または色）値として見ることができる。
【０１０８】
プロセッサ１は、点３３４の座標とともに光線３１６の情報およびアンセスターの係数の積を格納することによって、光線３１６の軌跡のヒストリー情報を全て格納することができる。プロセッサ１は、アンセスター情報を光線３１６の強度（または係数）とともに格納することによって、光線３１６の経路または以前の衝突点の座標を全て記憶しなくても必要な情報を全て管理することができる。
【０１０９】
プロセッサ２は、点３３１からサブ空間３２０に入射した光線３２４の軌跡を算出する。ノード６５１は点３３１に対応する。
【０１１０】
矢印６２１はサブ空間３２０に入射した光線３２４に対応する。
【０１１１】
ノード６５２は光線３２４がサブ空間３２０の下側の境界面と衝突する点に対応する。
【０１１２】
プロセッサ２は、光線３２４の進行方向、光線３２４の強度、サブ空間３２０の下側の境界面の情報に基づいて反射光線３２５の進行方向および係数を算出することができる。プロセッサ２は、光線３２４がサブ空間３２０の下側の境界面と衝突する点で影光線の進行方向および係数を算出し、透過光線の進行方向および係数を算出することができる。プロセッサ２は、光線３２４、反射光線３２５、影光線および透過光線のベクトル演算を行なって各光線のベクトルを求め、前記求めた各光線のベクトルから各光線の係数および進行方向を求めることができる。
【０１１３】
矢印６４１は影光線に対応し、ノード６６１は影係数に対応する。矢印６４２は透過光線に対応し、ノード６６２は透過係数に対応する。矢印６２２は反射光線３２５に対応する。
【０１１４】
プロセッサ２は、光線３２５の進行方向に沿って光線３２５の衝突の有無を探索することができる。光線３２５が仮想オブジェクト３２１と衝突すれば、プロセッサ２は光線３２５の進行方向、光線３２５の強度、仮想オブジェクト３２１の境界面の情報および仮想オブジェクト３２１の透明度情報に基づいて反射光線３２６の進行方向および係数を算出することができる。ノード６５３は、光線３２５が仮想オブジェクト３２１と衝突する点に対応する。
【０１１５】
プロセッサ２は、ノード６５３に対応する点で影光線の進行方向および係数を算出し、透過光線の進行方向および係数を算出することができる。
【０１１６】
矢印６４３は影光線に対応し、ノード６６３は影係数に対応する。矢印６４４は透過光線に対応し、ノード６６４は透過係数に対応する。矢印６２３は反射光線３２５に対応する。
【０１１７】
光線３２６がサブ空間３２０の右側の境界面と衝突すれば、プロセッサ２は反射した光線３２７の軌跡を算出することができる。ノード６５４は、光線３２６がサブ空間３２０の右側の境界面と衝突する点に対応する。
【０１１８】
プロセッサ２は、ノード６５４に対応する点で影光線および透過光線を求めることができる。矢印６４５は影光線に対応し、ノード６６５は影係数に対応する。矢印６４６は透過光線に対応し、ノード６６６は透過係数に対応する。矢印６２４は反射光線３２７に対応する。
【０１１９】
プロセッサ２は、光線３２７の進行方向に沿って光線３２７の軌跡を算出する。
【０１２０】
光線３２７が仮想平面３３０に当ると、プロセッサ２は点３３３の座標とともに光線３２７の係数および進行方向を格納することができる。このとき、プロセッサ２は点３３３の座標とともに光線３２７のアンセスターとしてノード６６１、ノード６６３、ノード６６５の影係数およびノード６６２、ノード６６４、ノード６６６の透過係数を格納してもよい。プロセッサ２は、点３３３の座標とともに光線３２７の情報およびアンセスター情報を格納して第２時間区間の算出過程を終了してもよい。ノード６５５は点３３３に対応する。
【０１２１】
図７は、本発明のまた他の実施形態に係る３次元映像プロセッシング方法で仮想の３次元モデルデータを更新する過程を示す図である。図７を参照すれば、隣接した視覚に対応する２つのフレームが示される。
【０１２２】
フレーム１は、仮想オブジェクト空間は４個のサブ空間７１１、７１２、７１３、７１４に分割され、フレーム２は、仮想オブジェクト空間は４個のサブ空間７２１、７２２、７２３、７２４に分割される。
【０１２３】
フレーム１のサブ空間７１１およびフレーム２のサブ空間７２１は互いに対応する。プロセッサ１（図示せず）は、フレーム１ではサブ空間７１１に割り当てられ、フレーム２ではサブ空間７２１に割り当てられる。
【０１２４】
仮想オブジェクト７１５はサブ空間７１１内に位置し、仮想オブジェクト７２５はサブ空間７２１内に位置する。フレーム２の仮想オブジェクト７２５の位置は、フレーム１の仮想オブジェクト７１５の位置と同一である。このとき、プロセッサ１は、フレーム２に対するレイトレーシング算出過程でフレーム１におけるサブ空間７１１の３次元モデルデータをそのまま用いてもよい。
【０１２５】
時間が経過するにともなって、サブ空間７２１内の仮想オブジェクト７２５の位置が以前フレームのサブ空間７１１内の仮想オブジェクト７１５の位置と同一であれば、プロセッサ１はサブ空間７２１の３次元モデルデータを更新しなくてもよい。
【０１２６】
フレーム１のサブ空間７１２およびフレーム２のサブ空間７２２は互いに対応する。プロセッサ２（図示せず）は、フレーム１ではサブ空間７１２に割り当てられ、フレーム２ではサブ空間７２２に割り当てられる。
【０１２７】
仮想オブジェクト７１６はサブ空間７１２内に位置し、仮想オブジェクト７２６はサブ空間７２２内に位置する。フレーム２の仮想オブジェクト７２６の位置はフレーム１の仮想オブジェクト７１６の位置と同一であるが、フレーム２の仮想オブジェクト７２７の位置はフレーム１の仮想オブジェクト７１７の位置と異なる。
【０１２８】
プロセッサ２は、フレーム２に対するレイトレーシング算出過程のためにサブ空間７１２の３次元モデルデータを更新する。時間の経過とともなって、サブ空間７２２内の仮想オブジェクト７２７の位置が以前フレームのサブ空間７１２内の仮想オブジェクト７１７の位置と異なるため、プロセッサ２はサブ空間７２２の３次元モデルデータを更新する。
【０１２９】
フレーム１のサブ空間７１３およびフレーム２のサブ空間７２３は互いに対応する。プロセッサ３（図示せず）は、フレーム１ではサブ空間７１３に割り当てられ、フレーム２ではサブ空間７２３に割り当てられる。
【０１３０】
仮想オブジェクト７１８はサブ空間７１３内に位置し、仮想オブジェクト７２８はサブ空間７２３内に位置する。フレーム２の仮想オブジェクト７２８の位置は、フレーム１の仮想オブジェクト７１８の位置と同一であれば、プロセッサ３はサブ空間７２３の３次元モデルデータを更新しなくてもよい。
【０１３１】
フレーム１のサブ空間７１４およびフレーム２のサブ空間７２４は互いに対応する。プロセッサ４（図示せず）は、フレーム１ではサブ空間７１４に割り当てられ、フレーム２ではサブ空間７２４に割り当てられる。
【０１３２】
仮想オブジェクト７１９はサブ空間７１４内に位置し、仮想オブジェクト７２９はサブ空間７２４内に位置する。フレーム２の仮想オブジェクト７２９の位置は、フレーム１の仮想オブジェクト７１９の位置と同一であれば、プロセッサ４はサブ空間７２４の３次元モデルデータを更新しなくてもよい。
【０１３３】
３次元モデルデータを更新する過程は多くの算出量を必要とする。本発明のプロセッサは、分割されたサブ空間のうち、サブ空間内の仮想オブジェクトの位置または形態が変化したサブ空間に対しては３次元モデルデータを更新し、仮想オブジェクトの位置または形態が変化しなかったサブ空間に対しては３次元モデルデータを更新しなくてもよい。本発明のプロセッサは、サブ空間それぞれに対して３次元モデルデータを更新することによって算出量を減らすことができ、３次元モデルデータを生成する時間を減らすことができる。
【０１３４】
図８は、本発明の一実施形態に係る３次元映像プロセッシング方法を示す動作フローチャートである。図８を参照すれば、３次元映像プロセッシング方法は、仮想の３次元オブジェクトが位置する仮想オブジェクト空間を複数のサブ空間に分割する（Ｓ８１０）。
【０１３５】
３次元映像プロセッシング方法は、分割されたサブ空間それぞれに入射される光線の入射したサブ空間内における軌跡を算出する（Ｓ８２０）。
【０１３６】
ステップＳ８２０において、互いに異なる入射したサブ空間に対して並列的に行なわれる。
【０１３７】
３次元映像プロセッシング方法は、分割されたサブ空間のうち、第１サブ空間内の光線が第２サブ空間に入射されるか否かを判定する（Ｓ８３０）。
【０１３８】
３次元映像プロセッシング方法は、第１サブ空間内の光線が第２サブ空間に入射されれば、入射した光線の軌跡情報を格納する（Ｓ８４０）。
【０１３９】
３次元映像プロセッシング方法は、分割されたサブ空間の間の境界を仮想平面に設定することができる。軌跡情報は、第１サブ空間および第２サブ空間間の仮想平面と光線が当る点における光線の方向、強度（または係数）および以前の衝突回数を含んでもよい。
【０１４０】
３次元映像プロセッシング方法は、格納された軌跡情報が終了条件を満たすか否かを判定する（Ｓ８５０）。
【０１４１】
終了条件は、軌跡情報に含まれた光線の強度が基準値よりも小さい条件であってもよく、軌跡情報に含まれた光線の以前の衝突回数が基準値よりも大きい条件であってもよい。
【０１４２】
３次元映像プロセッシング方法は、格納された軌跡情報が終了条件を満たさなければ、格納された軌跡情報から光線の第２サブ空間内における軌跡を算出する（Ｓ８６０）。
【０１４３】
ステップＳ８６０において、第２サブ空間に割り当てられたプロセッサによって行なわれてもよい。
【０１４４】
３次元映像プロセッシング方法は、ステップＳ８６０が行なわれた後ステップＳ８３０を行なってもよい。このとき、ステップＳ８３０は、第２サブ空間内の光線が第１サブ空間または第３サブ空間に入射されるか否かを判定することができる。
【０１４５】
３次元映像プロセッシング方法は、ステップＳ８５０の判定結果、格納された軌跡情報が終了条件を満たせば、算出されなかった光線が残っているか否かを探索する（Ｓ８７０）。
【０１４６】
３次元映像プロセッシング方法は、ステップＳ８３０の判定結果、第１サブ空間内の光線が第２サブ空間に入射されなければ、算出されなかった光線が残っているか否かを探索する（Ｓ８７０）。
【０１４７】
３次元映像プロセッシング方法は、ステップＳ８７０の探索結果、算出されなかった光線が残っていなければ終了する。
【０１４８】
３次元映像プロセッシング方法は、ステップＳ８７０の探索結果、算出されなかった光線が残っていれば、残っている光線のうちの次の光線を選択する（Ｓ８８０）。
【０１４９】
３次元映像プロセッシング方法は、ステップＳ８８０において選択された光線に対してステップＳ８２０を行う。
【０１５０】
本発明に係る３次元映像プロセッシング方法は、様々なコンピュータ手段により実現されることができるプログラム命令形態に実現されてコンピュータ読取可能な記録媒体に記録されることができる。当該記録媒体は、プログラム命令、データファイル、データ構造などを単独または組み合わせて含むこともでき、記録媒体およびプログラム命令は、本発明の目的のために特別に設計されて構成されたものでもよく、コンピュータソフトウェア分野の技術を有する当業者にとって公知であり使用可能なものであってもよい。コンピュータ読取可能な記録媒体の例としては、ハードディスク、フロッピー（登録商標）ディスク及び磁気テープのような磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤのような光記録媒体、フロプティカルディスクのような磁気−光媒体、およびＲＯＭ、ＲＡＭ、フラッシュメモリなどのようなプログラム命令を保存して実行するように特別に構成されたハードウェア装置が含まれる。また、記録媒体は、プログラム命令、データ構造などを保存する信号を送信する搬送波を含む光または金属線、導波管などの送信媒体でもある。プログラム命令の例としては、コンパイラによって生成されるような機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行され得る高級言語コードを含む。上述のハードウェア装置は、本発明の動作を行うために１つ以上のソフトウェア階層で作動するように構成され、その逆も同様である。
【０１５１】
上述したように、本発明は、たとえ限定された実施形態と図面によって説明したが、本発明は、上記の実施形態に限定されることなく、本発明が属する分野における通常の知識を有する者であれば、このような基材から多様な修正および変形が可能である。
【０１５２】
したがって、本発明の範囲は説明された実施形態に限定されて決められてはならず、後述する特許請求の範囲だけでなく、この特許請求の範囲と均等なものなどによって定められなければならない。
【図１】
0005485180.tif 000002
【図２】
0005485180.tif 000003
【図３】
0005485180.tif 000004
【図４】
0005485180.tif 000005
【図５】
0005485180.tif 000006
【図６】
0005485180.tif 000007
【図７】
0005485180.tif 000008
【図８】
0005485180.tif 000009