トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 ３Ｄコンピュータモデリング装置
【発明者】 【氏名】アダム マイケル ボームバーグ

【氏名】アレキサンダー ラルフ リオンズ

【氏名】アーロン ウィリアム クリストファー コッチェフ
【要約】 【課題】少ない計算量で正確に被写体オブジェクトの３Ｄコンピュータモデルを生成できるコンピュータ処理装置を提供する。

【解決手段】処理装置において、被写体オブジェクトのいくつかのデプスマップ３２１０を処理して被写体オブジェクトの３Ｄコンピュータモデルを生成する。各デプスマップ中の点を連結して２Ｄメッシュを与え、メッシュ中の点のデプスに従い、各２Ｄメッシュを３Ｄ空間に投影することで３Ｄメッシュ３６１０を与える。３Ｄメッシュの各稜線の側面をデプスマップから延長して追加することで、各デプスマップに対する多面体３６００を生成する。多面体３６００の交点を計算することで被写体オブジェクトの３Ｄコンピュータモデルを生成する。
【特許請求の範囲】
【請求項１】 被写体オブジェクトの複数のデプスマップを定義するデータを処理することで、被写体オブジェクトの面上の点を表す３次元空間の点で構成される被写体オブジェクトの３Ｄコンピュータモデルを生成する方法であって、各デプスマップを処理してその中の点を連結することで各デプスマップの連結された点の２次元メッシュを生成する工程と、メッシュを含むデプスマップの３次元空間の位置と向きと、デプスマップによって定義されたメッシュの中のそれぞれの点のデプスとに従って各２次元メッシュを３次元空間に投影することで、各々が３次元メッシュの各稜線に対する平面状の側面と共に２次元メッシュに対応する平面を定義する連結された頂点の３次元メッシュからなる多面体を各デプスマップから生成する工程と、生成された多面体からの所定数の平面が交差する点を計算することで被写体オブジェクトの表面上の点を表す３次元空間中の点を計算する工程とを備えることを特徴とする方法。
【請求項２】 各デプスマップは画素の配列で構成され、デプスマップを処理してその中の点を連結する工程では、画素を小画素に分割し、小画素を連結して２次元メッシュを生成することを特徴とする請求項１に記載の方法。
【請求項３】 更に、交点計算に先立ち、生成された各多面体を処理することで４つ以上の平面が接する多面体中の各頂点を３つ以下の平面が接する複数の頂点に置換する工程を備えることを特徴とする請求項１又は２に記載の方法。
【請求項４】 各置換頂点は、それが置換する頂点と同じ位置を３次元空間中で有するように定義されることを特徴とする請求項３に記載の方法。
【請求項５】 被写体オブジェクトの面上の点を表す３次元空間の点を計算する工程は、被写体オブジェクトの全ての点が存在すべき３次元空間のボリュームを定義する工程と、ボリュームを複数のボリューム部分に再分割する工程と、ボリューム部分をデプスマップから生成した多面体に対して検査する工程、及び、あるボリューム部分が少なくとも１つの多面体の完全に外側に存在する場合、そのボリューム部分を破棄し、あるボリューム部分が少なくとも部分的に全ての多面体の内側に存在する場合、そのボリューム部分と交差する平面を定義するデータをそのボリューム部分と交差する平面の数に従って処理し、更なる検査のためにボリューム部分を複数のより小さいボリューム部分に再分割し、所定数の平面が接するボリューム部分の３Ｄ点を計算するか、あるいはそのボリューム部分を破棄する工程とを備えることを特徴とする請求項１乃至４のいずれか１項に記載の方法。
【請求項６】 あるボリューム部分が少なくとも部分的に全ての多面体の内側に存在し、そのボリューム部分と交差する平面の数が所定数より多い場合、そのボリューム部分を再分割することを特徴とする請求項５に記載の方法。
【請求項７】 あるボリューム部分が少なくとも部分的に全ての多面体の内側に存在し、そのボリューム部分と交差する平面の数が所定数より少ない場合、そのボリューム部分を破棄することを特徴とする請求項５又は６に記載の方法。
【請求項８】 あるボリューム部分を検査した際、そのボリューム部分に交差する平面を定義するデータが記憶され、親ボリューム部分の再分割により生成された小さいボリューム部分を検査した際、親ボリューム部分に交差する平面のみを検査することでその平面が小さいボリューム部分に交差するか否かを判断することを特徴とする請求項５乃至７のいずれか１項に記載の方法。
【請求項９】 あるボリューム部分を検査した際、そのボリューム部分が完全に内側に存在すると判断された各多角形を定義するデータが記憶され、親ボリューム部分の再分割により生成された小さいボリューム部分を検査した際、検査を行って小さいボリューム部分が記憶されたデータに定義されていない多面体の各々の内側に存在するか否かを判断するが、記憶されたデータに定義された多面体についてはその内側に小さいボリューム部分が存在するか否かを判断する検査を行わないことを特徴とする請求項５乃至８のいずれか１項に記載の方法。
【請求項１０】 更に、被写体オブジェクトの面上の点を表す３次元空間の計算した点を連結することで被写体オブジェクトの面を表す多角形メッシュからなる３Ｄコンピュータモデルを生成する工程を備えることを特徴とする請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】 更に、３Ｄコンピュータモデルを搬送する信号を生成する工程を備えることを特徴とする請求項１乃至１０のいずれか１項に記載の方法。
【請求項１２】 更に、直接あるいは間接に信号の記録を作成する工程を備えることを特徴とする請求項１１に記載の方法。
【請求項１３】 被写体オブジェクトの複数のデプスマップを定義するデータを処理することで、被写体オブジェクトの面上の点を表す３次元空間の点からなる被写体オブジェクトの３Ｄコンピュータモデルを生成する装置であって、各デプスマップを処理してその中の点を連結することで各デプスマップの連結された点の２次元メッシュを生成する連結手段と、メッシュを含むデプスマップの３次元空間の位置と向きと、デプスマップによって定義されたメッシュの中のそれぞれの点のデプスとに従って前記連結手段によって生成された各２次元メッシュを３次元空間に投影することで、各々が３次元メッシュの各稜線に対する平面状の側面と共に２次元メッシュに対応する平面を定義する連結された頂点の３次元メッシュからなる多面体を各デプスマップから生成する投影手段と、投影手段により生成された多面体からの所定数の平面が交差する点を計算することで被写体オブジェクトの表面上の点を表す３次元空間中の点を計算する３Ｄ点計算手段とを備えることを特徴とする装置。
【請求項１４】 各デプスマップは画素の配列で構成され、連結手段は画素を小画素に分割し、小画素を連結して２次元メッシュを生成することを特徴とする請求項１３に記載の装置。
【請求項１５】 更に、３Ｄ点計算手段による処理に先立ち、生成された各多面体を処理することで４つ以上の平面が接する多面体中の各頂点を３つ以下の平面が接する複数の頂点に置換する頂点置換手段を備えることを特徴とする請求項１３又は１４記載の装置。
【請求項１６】 頂点置換手段は、各置換頂点がそれが置換する頂点と同じ位置を３次元空間中で有するように定義することを特徴とする請求項１５に記載の装置。
【請求項１７】 ３Ｄ点計算手段は、被写体オブジェクトの全ての点が存在すべき３次元空間のボリュームを定義するボリューム定義手段と、ボリュームを複数のボリューム部分に再分割するボリューム分割手段と、ボリューム部分を投影手段によって生成された多面体に対して検査するボリューム検査手段とを具備し、当該ボリューム検査手段はあるボリューム部分が少なくとも１つの多面体の完全に外側に存在する場合、そのボリューム部分を破棄し、あるボリューム部分が少なくとも部分的に全ての多面体の内側に存在する場合、そのボリューム部分と交差する平面を定義するデータをそのボリューム部分と交差する平面の数に従って処理し、更なる検査のためにボリューム部分を複数のより小さいボリューム部分に再分割する、所定数の平面が接するボリューム部分の３Ｄ点を計算するか、あるいはそのボリューム部分を破棄することを特徴とする請求項１３乃至１６のいずれか１項に記載の装置。
【請求項１８】 ボリューム検査手段は、あるボリューム部分が少なくとも部分的に全ての多面体の内側に存在し、そのボリューム部分と交差する平面の数が所定数より多い場合、そのボリューム部分を再分割するように構成されることを特徴とする請求項１７に記載の装置。
【請求項１９】 ボリューム検査手段は、あるボリューム部分が少なくとも部分的に全ての多面体の内側に存在し、そのボリューム部分と交差する平面の数が所定数より少ない場合、そのボリューム部分を破棄するように構成されることを特徴とする請求項１７又は１８に記載の装置。
【請求項２０】 ボリューム検査手段は、あるボリューム部分を検査した際、そのボリューム部分に交差する平面を定義するデータを記憶するように構成され、さらに、親ボリューム部分の再分割により生成された小さいボリューム部分を検査した際、親ボリューム部分に交差する平面のみを検査することでその平面が小さいボリューム部分に交差するか否かを判断するように動作するよう構成されることを特徴とする請求項１７乃至１９のいずれか１項に記載の装置。
【請求項２１】 ボリューム検査手段は、あるボリューム部分を検査した際、そのボリューム部分が完全に内側に存在すると判断された各多角形を定義するデータを記憶するように構成され、さらに、親ボリューム部分の再分割により生成された小さいボリューム部分を検査した際、検査を行って小さいボリューム部分が記憶されたデータに定義されていない多面体の各々の内側に存在するか否かを判断するが、記憶されたデータに定義された多面体についてはその内側に小さいボリューム部分が存在するか否かを判断する検査を行わないように動作するよう構成されることを特徴とする請求項１７乃至２０のいずれか１項に記載の装置。
【請求項２２】 更に、被写体オブジェクトの面上の点を表す３次元空間の計算した点を連結することで被写体オブジェクトの面を表す多角形メッシュからなる３Ｄコンピュータモデルを生成する手段を備えることを特徴とする請求項１３乃至２１のいずれか１項に記載の装置。
【請求項２３】 プログラム可能な処理装置が請求項１乃至１２のうちの少なくとも１項に記載された方法を実行するよう動作可能となる命令を記憶すうｒ記憶装置。
【請求項２４】 プログラム可能な処理装置が請求項１乃至１２のうちの少なくとも１項に記載された方法を実行するよう動作可能となる命令を搬送する信号。
【発明の詳細な説明】【０００１】本発明は、複数のデプスマップ（すなわち、オブジェクト上の点と基準点との間の距離を定義する１セット分の値）からオブジェクトの３次元（３Ｄ）コンピュータモデルを生成するコンピュータ処理に関する。
【０００２】従来、オブジェクトの３Ｄコンピュータモデルをそのオブジェクトの複数のデプスマップ（depth map）「範囲画像（range image）」ともいわれる）から生成する方法が数多く知られている。
【０００３】これらの既知の方法において、全てのデプスマップからのデータは同じ座標系に配置され、それぞれのデプスマップによって定義された３Ｄ点を連結することで各々が１つのデプスマップに対応する複数の３Ｄ面メッシュを形成する。次に、２種類の方法のいずれかを用いて、別々の面メッシュをオブジェクトの面を表す単一の面に合成する、すなわち、（１）例えばTurkとLevoyの“Zippered Polygon Meshes from Range Image” (SIGGRAPH 94 (ACM)、Addison-Wesley社刊、ISBN 0-201-60795-6)に記載されるように、個々の面メッシュが３Ｄ空間において実質的に近接しているならば、それらを「ジップ」する。
（２）「マーチンキューブス(marching-cubes)」ボリューム系の方法を用いる。この方法では、座標系の３Ｄ空間をボクセル（直平行六面体）に分割し、ボクセル内の少なくとも１点（各頂点あるいは中心）からデプスマップから最も近い３Ｄ点までの距離を定義するそれぞれのボクセルについて「符号付距離」を計算し、それがオブジェクト面の内側か（マイナス値）、外側か（プラス値）、オブジェクト面の上（ゼロ値）かを判定する。次に、前に計算した符号付距離に基づくボクセルをゼロ値表面が通過する経路を計算してボクセルの周囲を「マーチング」することで、連結された多角形の面メッシュを生成する。こうした技術は例えばWheelerなどの“Consensus Surfaces for Modelling 3D Objects from Multiple Range Images” (Proceedings of International Conference on Computer Vision 1998、917〜924ページ、Narosa社刊、ISBN 81-7319-221-9)に記載されている。
【０００４】しかしながら、これらの方法には数々の問題がある。
【０００５】特に、「メッシュジッピング(mesh zippering)」法の場合、かなりの処理資源と処理時間を要するうえ、生成した面は被写体オブジェクトの面を正確に表すものではないという問題がある。
【０００６】マーチンキューブスボクセル系の方法の場合、オブジェクトを表す得られた面の精度（解像度）は３Ｄ空間を分割したボクセルのサイズによって決まるという問題がある。しかしモデル解像度を上げるためにボクセルサイズを小さくすれば検査を要するボクセルの数が増大し、処理時間が長くなる。
【０００７】メッシュジッピング系の方法もマーチンキューブスボクセル系の方法も他の点（例えば、オブジェクトの背後の面あるいはオブジェクトが存在する面を表す）から識別されるべき被写体オブジェクトに関連するデプスマップにおける点を必要とする。しかし、モデリングされているオブジェクトを表す点とその他の点を区別する方法はしばしば点を誤分類することになり、最終的な３Ｄコンピュータモデルが不正確となる。例えば、ある方法ではオブジェクトの稜線が生じるデプスの急激な変化を識別するために「任意の」最大デプスを用いる。しかし、多くのオブジェクトはデプスが急激に変化する表面を有するため、多くの点を誤分類する可能性がある。
【０００８】本発明は上記の問題点に鑑みてなされたものであり、その１つ以上の問題に対処することを目的としている。
【０００９】本発明によれば、被写体オブジェクトのいくつかのデプスマップのそれぞれを多面体に変換し、それらの多面体の交点を計算することで、被写体オブジェクトの３Ｄコンピュータモデルを生成するコンピュータ処理装置及び方法が提供される。
【００１０】それぞれの多面体はデプスマップ内の点を連結して２Ｄ多角形メッシュを与え、２Ｄメッシュを３次元空間に投影してメッシュ内の点の既知のデプスに依存した３Ｄメッシュを与えることで生成するのが好ましい。３Ｄメッシュのそれぞれの稜線の側面をデプスマップから任意の長距離まで延長して加えても良い。
【００１１】こうして被写体オブジェクトの輪郭形状（シルエット）をデプスデータと合成してそれぞれの多面体を生成することができる。
【００１２】この方法ではボリュームを分割するため、被写体オブジェクトに関連する点やその他のオブジェクトに関連する点を識別するためにそれぞれのデプスマップを分割する必要がない。
【００１３】この方法によれば多面体の交点からなる３Ｄモデルを得ることができる。よってボクセルに基づく技術を用いる必要がない。
【００１４】また、本発明によれば、例えば記憶装置あるいは信号として実施され、プログラミング可能な処理装置が上記の方法を行うように動作可能となる命令を含み、又は上記の装置を構成するコンピュータプログラム製品が提供される。
【００１５】以下、添付の図面を参照して、単なる一例としての本発明の実施形態を説明する。
【００１６】第１実施形態図１を参照すると、本発明の第１実施形態は、従来通りに１つ以上のプロセッサと、複数のメモリと、グラフィックスカードなどを含むパーソナルコンピュータのような処理装置３００２と、従来のパーソナルコンピュータモニタなどの表示装置３００４と、キーボード、マウスなどのユーザ入力装置３００６とを具備する。
【００１７】処理装置３００２は、例えば、ディスク３０１２などのデータ記憶媒体に格納されたデータとして及び／又は例えば遠隔データベースからインターネットなどの通信ネットワーク（図示せず）を介する伝送、あるいは無線伝送により処理装置３００２に入力され且つ／又はキーボードなどのユーザ入力装置３００６を介してユーザにより入力される信号３０１４として入力されるプログラミング命令に従って動作するようにプログラムされている。
【００１８】以下にさらに詳細に説明するが、それらのプログラミング命令は、被写体オブジェクト(subject object)のデプスマップ(depth map)と各デプスマップの相対的な位置及び向きを定義するデータとを処理することで被写体オブジェクトの３次元コンピュータモデルを定義するデータを生成するように処理装置３００２を構成させるための命令である。被写体オブジェクトの３Ｄコンピュータモデルは新規且つ発明的な技術を用いて生成される。この技術においては、それぞれのデプスマップを処理することで複数の多角形からなる多面体を生成し、全てのデプスマップに対する多面体における多角形の交点を判断することで、被写体オブジェクトの頂点を表す３Ｄ点を計算する処理を行う。以下にさらに詳細に説明するが、本実施形態において、この処理は特に、被写体オブジェクトの表面上に３Ｄ点を生じることができない多角形の交点を計算しなくても良いので、非常に効率的な方法で実行される。
【００１９】処理装置３００２は、プログラミング命令によりプログラミングされたとき、処理動作を実行するための幾つかの機能ユニットとして構成されたと考えることができる。そのような機能ユニットの例及びそれらの相互接続関係を図１に示す。しかし、図１に示すユニット及び相互接続は概念上のものであり、理解を助けるという目的のために一例として示されているにすぎない。しかし、それらは、処理装置３００２のプロセッサ、メモリなどが構成されるユニットや接続を必ずしも表してはいない。
【００２０】図１に示す機能ユニットを説明すると、中央制御装置３０２０はユーザ入力装置３００６からの入力信号を処理すると共に、その他の機能ユニットの制御及び処理を実行する。
【００２１】メモリ３０３０は、中央制御装置３０２０及びその他の機能ユニットにより用いられるべく設けられている。
【００２２】入力データ記憶装置３０４０は処理装置３００２から入力された入力データを例えばディスク３０４２などの記憶装置に記憶されたデータ、又は処理装置３００２に送信された信号３０４４として、あるいはユーザ入力装置３００６を用いて記憶する。本実施形態において入力データは被写体オブジェクトの複数のデプスマップを定義する。各デプスマップは、従来と同様、複数の画素から構成される被写体オブジェクトの画像と、画素内で撮影された内容のカメラの焦点からの距離を定義するデプス値とで構成される。デプスマップを定義する入力データは従来の３Ｄ撮影装置、例えばレーザスキャナ、構造光システム、受動ステレオカメラ対などによって生成しても良い。
【００２３】本実施形態においては、入力されたそれぞれのデプスマップを装置３００２に入力する前に分割することで、各画素が被写体オブジェクトに関連するのか「背景」（すなわち、被写体オブジェクト以外のもの）に関連するのかを示すフラグを定義する。しかし、この分割を行う処理は処理装置３００２において従来技術を用いて選択的に行っても良い。
【００２４】入力データはさらにデプスマップ画像を記録した（１つあるいは複数の）カメラの固有のパラメータ、すなわち、縦横比(aspect ratio)、焦点距離、主点（光軸が撮影平面と交わる点）、１次半径方向歪み(first order radial distortion)係数及びスキュー角（画素格子の軸が厳密には直交していないことがありえるため、それらの軸が成す角度）を定義するデータも含む。固有カメラパラメータを定義する入力データはユーザの側からユーザ入力装置６を用いて入力されても良い。
【００２５】入力データはまた、入力されたデプスマップの相対的な位置と向き（すなわち、デプスマップの画像が記録された位置と向き）を定義する。
【００２６】カメラ計算器３０５０は入力データを処理して、それが入力されたデプスマップの相対的な位置と向きとをまだ定義していない場合、相対的な位置と向きとを計算するように構成される。以下に述べるように、カメラ計算機３０５０はデプスマップ画像の特徴を一致させ、異なるデプスマップにおいて一致した特徴の相対的な位置に基づいた位置と向きとを計算することでこの処理を行うように構成されている。
【００２７】デプスマップ点コネクタ３０６０は各入力デプスマップを定義するデータを処理しデプスマップの画素を連結することでデプスマップにおける被写体オブジェクトを表す２Ｄ三角面を生成するように構成される。
【００２８】多面体生成器(polyhedron generator)３０７０はデプスマップ点コネクタ３０６０によって生成されたそれぞれの２Ｄ三角面を、デプスマップの位置と向きとを定義するデータ及びデプスマップにおける画素のデプスを定義するデータとともに処理することで、被写体オブジェクトの画像を定義する複数の多角形で構成される各デプスマップに対する３Ｄ多面体を生成するように構成される。
【００２９】サーフェスモデラ３０８０は３Ｄ点計算器３０９０及び多角形生成器(polygongenerator)３１００を具備する。
【００３０】３Ｄ点計算器３０９０は多面体生成器３０７０によって生成された多面体を処理してそれらの多角形の交点を計算するように構成される。交点は被写体オブジェクトの面上に潜在的に存在する３Ｄ点を定義する。これらの交点は、被写体オブジェクトの表面に潜在的に存在する３Ｄ点を定義する。３Ｄ点計算器３０９０は、計算した３Ｄ点を検査して、どの点が被写体オブジェクト中の実際の３Ｄ点を表すのかを判断するように構成される。
【００３１】多角形生成器３１００は、３Ｄ点計算器３０９０により計算され、検査後保持された３Ｄ点を連結し、被写体オブジェクトの面を表す多角形メッシュを形成するように構成される。
【００３２】具体的には、デプスマップ多面体の多角形の交点が被写体オブジェクトの全体的な面画像上の３Ｄ点を定義する。従って、これらの３Ｄ点は、被写体オブジェクトの面を表す多角形メッシュの多角形の頂点を形成するように多角形生成器３１００により連結される。このため、これ以降、３Ｄ点計算器３０９０により計算され、多角形生成器３１００によって連結される３Ｄ点を３Ｄ頂点と呼ぶ。
【００３３】サーフェステクスチャラ３１１０は、サーフェスモデラ３０８０により生成されたサーフェスモデルにレンダリングするために、入力デプスマップの画像データからテクスチャデータを生成するように構成される。
【００３４】ディスプレイプロセッサ３１２０は、中央制御装置３０２０の制御の下に、３Ｄコンピュータモデルを生成する処理中に、表示装置３００４を介してユーザに対し画像及び命令を表示するように構成される。さらに、中央制御装置３０２０の制御の下に、ディスプレイプロセッサ３１２０は、サーフェスモデラ３０８０により生成されたサーフェスモデルデータを処理し且つサーフェステクスチャラ３１１０により生成されたテクスチャデータをサーフェスモデル上にレンダリングすることにより、ユーザが選択した視点から被写体オブジェクトの３Ｄコンピュータモデルの画像を表示するように構成される。
【００３５】出力データ記憶装置３１３０は、サーフェスモデラ３０８０により生成されたサーフェスモデルを定義するデータを格納するのに加え、オプションとしてサーフェステクスチャラ３１１０により生成されたテクスチャデータも格納するように構成される。中央制御装置３０２０は、出力データ記憶装置３１３０からの出力データを例えばディスク３１４０などの記憶装置へのデータ及び／又は信号３１５０として制御するように構成される。
【００３６】図２は、本実施形態において処理装置３００２によって行われる処理動作を示す。
【００３７】図２において、ステップＳ２−１で、中央制御装置３０２０はディスプレイプロセッサ３１２０によって表示装置３００４にメッセージを表示させユーザに処理のためのデータを入力するよう要求する。
【００３８】ステップＳ２−２で、ステップＳ２−１での要求に応じてユーザによって入力されたデータが入力データ記憶装置３０４０に記憶される。具体的に本実施形態では、入力データは異なる位置と向きで記録された被写体オブジェクトの複数のデプスマップを定義するデータで構成される（各デプスマップは被写体オブジェクトの画像と、カメラ焦点からの画素内に示される内容の距離を定義する画像の各画素のデプス値と、本実施形態では、各画素が表すものが被写体オブジェクトであるか背景であるかを特定するフラグを定義するデータで構成される）。入力データはさらにデプスマップの画像を記録したカメラに固有のパラメータ、すなわち、縦横比、焦点距離、主点、１次半径方向歪み係数及びスキュー角を定義するデータを含む。入力データはまた、入力されたデプスマップの相対的な位置と向き（すなわち、デプスマップが記録された、３Ｄ空間における相対的な位置と向き）とを定義するデータを含む。
【００３９】ステップＳ２−４で、中央制御装置３０２０はステップＳ２−２で記憶された入力データが入力デプスマップの相対的な位置と向きとを定義するか否かを判断する。
【００４０】ステップＳ２−４で入力データがデプスマップの相対的な位置と向きとを定義しないと判断した場合、ステップＳ２−６でカメラ計算機３０５０はこれらの相対的な位置と向きとを計算する処理を行う。本実施形態では、画像が、例えばＥＰ−Ａ−０８９８２４５に記載されるように、従来の方法で記録されたのであれば、カメラ計算機３０５０はデプスマップ画像を処理しその中の特徴をマッチさせカメラの相対的な位置と向きとを計算することでデプスマップの相対的な位置と向きとを計算する。
【００４１】これに対し、ステップＳ２−４でステップＳ２−２で記憶された入力データがすでにデプスマップの相対的な位置と向きとを定義していると判断した場合、ステップＳ２−６は省略される。
【００４２】図３において、処理のこの段階では。処理装置３００２は複数のデプスマップ３２００から３２７０を定義するデータと、デプスマップの３Ｄ空間の相対的な位置と向きとを定義するデータを記憶する（デプスマップの焦点位置３４００から３４７０を含む）。
【００４３】デプスマップ３２００から３２７０は各々、被写体オブジェクト３３００の画像と、カメラ焦点３４００から３４７０の３Ｄ位置からの画素内に示される被写体の距離を定義する画像の各画素のデータと、本実施形態では、各画素の内容が被写体オブジェクト３３００に関連するのかあるいは背景に関連するのかを定義するデータで構成される。
【００４４】図２に戻って、ステップＳ２−８で、デプスマップ点コネクタ３０６０はデプスマップ３２００から３２７０のそれぞれにおける被写体オブジェクト３３００を表す画素を連結しそれぞれのデプスマップの被写体オブジェクトの２Ｄ三角面を生成する。
【００４５】図４は、ステップＳ２−８でデプスマップ点コネクタ３０６０が行う処理動作を示す。
【００４６】図４において、ステップＳ４−２で、デプスマップ点コネクタ３０６０は次に処理すべきデプスマップ（ステップＳ４−２が初めて行われる場合は最初のデプスマップ）を検討する。
【００４７】ステップＳ４−４で、デプスマップ点コネクタ３０６０は各画素を４つの画素に分割する。各画素には親画素と同じデプス値、さらに親画素と同じ被写体オブジェクト・背景フラグを割り当てられる（画素が被写体オブジェクト３３００の一部かそれともそれ以外のもの、すなわち「背景」を示すかを表す）。
【００４８】この処理をさらに図５を参照して説明する。図５はデプスマップ画像の一部を一例として示す。具体的には、図５は図３において丸で示したデプスマップ画像３２４０の一部３４８０を示す。
【００４９】図５において、親画素は格子状の太線で定義される。ステップＳ４−４で親画素を４つに分割することで生成された画素は格子状の細線で表す。
【００５０】図５の線３５００は画像中の被写体オブジェクト３３００の輪郭を表す。従って、線３５００が通過する元の親画素はそれぞれ、元は入力データにおいて被写体オブジェクト３３００を示す画素として指定されていたものである。ステップＳ４−４で、被写体オブジェクト３３００を表すそれぞれの画素を４つの画素に分割する。４つの新しい画素もまた被写体オブジェクト３３００を示す画素として指定される（図５では被写体オブジェクト３３００を表す各画素の点によって表される）。尚、ステップＳ４−４で生成された新しい画素のいくつか（例えば画素３５０２）は被写体オブジェクト３３００を表すとして指定されるが線３５００の外側に位置する。こうした状況は、上記のように、親画素の位置とは無関係にステップＳ４−４で親画素から生成された４つの画素はそれぞれ親画素と同じ被写体オブジェクト・背景フラグを割り当てられるために生じる。
【００５１】これ以降、本実施形態では、デプスマップ中の「画素」といった場合、特に言及のない限りは元の画素ではなく、ステップＳ４−４で生成した小さな画素を意味する。
【００５２】図４に戻って、ステップＳ４−６で、デプスマップ点コネクタ３０６０は被写体オブジェクト３３００を示すデプスマップの画素の周囲にバウンディングボックス(bounding box)を定義する。本実施形態では、バウンディングボックスはデプスマップ画像の稜線に平行な稜線を有するように定義される。バウンディングボックスは少なくとも１つの背景画素の各稜線に沿った境界を含むように定義される。
【００５３】ステップＳ４−８で、デプスマップ点コネクタ３０６０はステップＳ４−６で定義されたバウンディングボックス内の画素を２×２画素窓（換言すると、ステップＳ４−４が実施される以前のデプスマップ中の元画素と同じサイズを有する窓）で走査する。
【００５４】画素窓の各位置について、デプスマップ点コネクタ３０６０は、図６ａ乃至６ｋを参照して以下に説明するように、被写体オブジェクト３３００を表す窓内の画素の位置及び所定の連結規則により画素窓内に現れたデプスマップ内の画素を連結する。
【００５５】具体的には、図６ａ乃至６ｄにおいて、画素窓に被写体オブジェクト３３００を表す画素が２つあるいは２つだけ出現した場合（こうした画素は図６ａから６ｋでは図５と同様点によって示される）、その２つの画素が垂直及び水平方向に隣接している場合、デプスマップ点コネクタ３０６０は被写体オブジェクト３３００を表す画素の中心を連結する。
【００５６】これに対し、図６ｅ及び６ｆにおいて、画素窓内に画素が２つあるいは２つだけ対角線上の対向する隅に出現した場合、ステップＳ４−８でデプスマップ点コネクタ３０６０は画素を連結しない。
【００５７】図６ｇ及び６ｊにおいて、被写体オブジェクト３３００を表す画素が３つあるいは３つだけ画素窓内に存在する場合、デプスマップ点コネクタ３０６０は、図示するように、垂直方向の連結と水平方向の連結（対角線方向の連結ではない）によって被写体オブジェクト３３００を表す画素の中心を連結する。
【００５８】図６ｋにおいて、画素窓内の４つの画素全てが被写体オブジェクト３３００を表す場合、デプスマップ点コネクタ３０６０は２つの垂直連結、２つの水平連結、及び１つの対角線連結によって画素の中心を連結する。
【００５９】被写体オブジェクト３３００を表す画素が１つあるいは１つだけ画素窓内に出現した場合には、デプスマップ点コネクタ３０６０は画素連結を行わない。
【００６０】図７は図５に示した例についてステップＳ４−８で行われた処理の結果を示す。
【００６１】図７において、被写体オブジェクト３３００を表すデプスマップ画像内に２Ｄ三角面が生成されているのがわかる（あるいは図５及び７の例の被写体オブジェクト３３００の一部）。
【００６２】図４に戻って、ステップＳ４−１０で、デプスマップ点コネクタ３０６０はステップＳ４−８で生成された三角面を間引く。これは面内の連結の数を削減するためである。本実施形態では、間引き処理は連結された画素のデプス値によって行われる。この処理は例えばHoppeなどの“Mesh Optimization”(ACM SIGGRAPH93、Addison-Wesley社刊、ISBN 0-201-58889-7)”に記載されるように、従来の方法で行われる。
【００６３】ステップＳ４−１２で、デプスマップ点コネクタ３０６０は他に処理する入力デプスマップがあるか否かを判断する。
【００６４】上記の方法で各入力デプスマップが処理されるまでステップＳ４−２からＳ４−１２を繰り返す。
【００６５】図２に戻って、ステップＳ２−１０で、多面体生成器３０７０は被写体オブジェクト３３００の画像を定義するそれぞれの入力デプスマップの多面体を生成する。
【００６６】図８は、ステップＳ２−１０で多面体生成器３０７０によって行われる処理動作を示す。
【００６７】図８において、ステップＳ８−２で多面体生成器３０７０はステップＳ２−８で生成された次の２Ｄ三角デプスマップ（ステップＳ８−２が初めて行われる場合は三角デプスマップ）を検討する。
【００６８】ステップＳ８−４で、多面体生成器３０７０は入力データ中に定義された頂点を含む画素のデプス値、デプスマップの位置と向き、及びカメラパラメータに従って三角形の各頂点を３Ｄ空間に投影する。これにより、各２Ｄ頂点から３Ｄ頂点が生成され、多面体生成器３０７０は生成された３Ｄ頂点の各々に固有のＩＤを割り当て、３Ｄ頂点によって定義された平面多角形面を定義するデータを記憶する。こうして、多面体生成器３０７０は被写体オブジェクト３３００を表す複数の平面多角形で構成される多面体を生成する。
【００６９】多面体生成器３０７０によって行われる処理について図９ａ、９ｂ、及び９ｃを参照してさらに説明する。
【００７０】図９ａは２Ｄ頂点がデプスマップ内の被写体オブジェクトの画像の内側に位置する点を表す場合の、２Ｄ三角形から３Ｄ空間への頂点の投影を示す（すなわち、２Ｄ頂点はステップＳ２−８で生成された三角形の境界上にない）。
【００７１】図９ａにおいて、１例としてデプスマップ３２１０の２つの２Ｄ頂点３５１０及び３５２０が示されている。
【００７２】入力データに定義されたデプスマップ３２１０の位置及び向きと固有のカメラパラメータとを用いて、２Ｄ頂点３５１０を３Ｄ空間に投影し、２Ｄ頂点３５１０を含む画素に定義されたデプス値に等しい焦点位置３４１０から離れた位置に３Ｄ点３５３０を定義する。同様に、デプスマップ３２１０の位置及び向きと固有のカメラパラメータとに基づいて、２Ｄ頂点３５２０を３Ｄ空間に投影し、２Ｄ頂点３５２０を含む画素のデプス値に等しい焦点位置３４１０から離れた位置に３Ｄ点３５４０を定義する。
【００７３】２Ｄ頂点３５１０及び３５２０は２Ｄ三角形において連結されているため、多面体生成器３０７０はこれらから生成された３Ｄ点３５３０及び３５４０が３Ｄ多面体において連結されていることを定義するデータを記憶する。
【００７４】図９ｂは、本実施形態のステップＳ２−８で、ステップＳ２０８で生成された２Ｄ三角面の境界上に位置する２Ｄ頂点を３Ｄ空間に投影する処理を示す。
【００７５】前述のように、ステップＳ２−１０で多面体生成器３０７０が行う処理の目的は、被写体オブジェクト３３００の３Ｄ多面体画像を処理されているデプスマップから生成することである。結果的に２Ｄ三角形の境界上に位置する各２Ｄ頂点は３Ｄ多面体の側面の終点である３Ｄ頂点を定義する。さらに、被写体オブジェクト３３００の背の位置を定義するために処理されているデプスマップについて情報が得られないため（デプスマップを生成したとき、これは３Ｄイメージャにとっては見えない）、本実施形態で多面体生成器３０７０が生成した３Ｄ多面体の各側面は「無限の」範囲（実際には任意の距離までの範囲）にあると定義される。
【００７６】具体的には、図９ｂにおいて、ステップＳ２−８で生成された２Ｄ三角形の境界上に位置する２つの２Ｄ頂点３５５０及び３５６０はデプスマップ３２１０に対する１例として示される。
【００７７】図９ａに示す例で、デプスマップ３２１０の位置及び向きとデプスマップ画像を生成するのに用いたカメラのパラメータとを用いて２Ｄ頂点３５５０及び３５６０はそれぞれ３次元に投影される。２Ｄ頂点３５５０は、２Ｄ頂点３５５０を含むデプスマップ３２１０の画素に定義されたデプス値に等しいカメラの焦点位置３４１０からの距離を有する３Ｄ頂点３５７０を生成する。同様に、２Ｄ頂点３５６０は、２Ｄ頂点３５６０を含む画素に定義されたデプス値に等しい焦点位置３４１０からの距離を有する３Ｄ頂点３５８０を生成する。
【００７８】２Ｄ頂点３５５０及び３５６０は２Ｄ三角形において連結されているため、多面体生成器３０７０はこれらから生成された３Ｄ点３５７０及び３５８０が３Ｄ多面体において連結されていることを定義するデータを記憶する。さらに、多面体生成器３０７０は焦点位置３４１０から無限の方向（実際には任意の距離）に投影された側面３５９０を定義する。これは３Ｄ頂点３５７０及び３５８０を焦点位置３４１０に向かう方向への終点として有している。
【００７９】図９ｃにおいて、ある２Ｄ三角形にステップＳ８−４の処理を行う全体的な効果は「前」端面３６１０、無限の側面、及び潜在的な「背」面を無限大に有する３Ｄ多面体３６００を生成することである。
【００８０】前端面３６１０は、２Ｄ頂点に対応する接続とステップＳ２−８で生成された２Ｄ三角形中の接続とを有する３Ｄ頂点から成る。
【００８１】多面体３６００は、デプスマップ３２１０から見た被写体オブジェクト３３００の面画像を定義する。多面体３６００は複数の平面多角形、つまり、端面３６１０の３Ｄ頂点によって定義された平面多角形（全ての３Ｄ頂点が同一平面上に存在するわけではないので、これらの平面多角形全てが同一平面上に存在するわけではない）及び多面体３６００の側面を定義する平面多角形を備える。
【００８２】多面体３６００の側面をデプスマップ３２１０の背後に向かって投影した場合、これらは焦点位置３４１０に収束する。そのため多面体３６００は頂点を焦点位置３４１０に有する円錐台とみなすことができる。
【００８３】以下に述べるように、処理装置３００２は各デプスマップについて３Ｄ多面体を生成し、全ての多面体を形成する多角形の交点を計算し被写体オブジェクト３３００の前面を表す多角形メッシュを生成する処理を行う。
【００８４】図８において、ステップＳ８−６からＳ８−１４で、多面体生成器３０７０はステップＳ８−４で生成した「複合」多面体を「単一」多面体、すなわち３つの平面多角形面のみが各頂点で接する多面体に変換する処理を行う。以下により詳細に説明するように、この処理は３つの多角形のみが各垂直頂点で接するように付加的な「垂直」頂点を多面体に加えることを含む。
【００８５】詳細には、ステップＳ８−６で、多面体生成器３０７０はステップＳ８−４で生成された多面体の次の３Ｄ頂点（ステップＳ８−６が初めて行われる場合は最初の３Ｄ頂点）を検討する。
【００８６】ステップＳ８−８で、多面体生成器３０７０は多面体のどの平面多角形が頂点で接するのかとその隣接する順番を判断する（平面多角形は前端面３６１０及び／又は無限平面側面における有限の平面である）。
【００８７】具体的には、図１０に示す例において、３Ｄ頂点３６２０がステップＳ５２−６で検討した頂点である場合、ステップＳ８−８で、多面体生成器３０７０はどの平面多角形が頂点３６２０で接するのか、さらにそれらの平面多角形が連結される順番を判断する処理を行う（図１０に示す例では平面多角形Ａ、Ｂ、Ｃ、Ｄ、Ｅ、及びＦが頂点３６２０で接し、その隣接する順番はＡ−Ｂ−Ｃ−Ｄ−Ｅ−Ｆ−Ａである）。
【００８８】図１１はステップＳ８−８で多面体生成器３０７０が行う処理を示す。これらの処理動作について図１０に示す例を参照しながら説明する。
【００８９】図１１において、ステップＳ１１−２で、多面体生成器３０７０はステップＳ８−６で選択した頂点を頂点として有する平面多角形面を識別し、その面を面の順番リストに加える。この処理は、平面多角形面を形成する頂点を読取り、検討した頂点に対応する頂点を有することが判明した最初の面を選択することで行われる。
【００９０】例えば、ステップＳ１１−２で図１０の例の多角形面Ａを識別したと仮定する。
【００９１】ステップＳ１１−４で、多面体生成器３０７０は最後に順番リストに加えられた平面多角形の稜線に突き当たる平面多角形面（ステップＳ１１−４が初めて行われる場合はステップＳ１１−２で加えられた面）を検討し、ステップＳ８−６で選択した頂点を共有する平面多角形面を識別する。
【００９２】詳細には、図１０に示す例においては、ステップＳ１１−２で順番リストに加えられた多角形面Ａのエッジに当接する多角形は多角形面Ｂ、Ｆ、及びＸである。この３つの多角形のうち、多角形Ｂ及びＦは多角形Ａと頂点３６２０を共有する。しかし多角形Ｘは頂点３６２０を含まない。
【００９３】ステップＳ１１−６で、多面体生成器３０７０はステップＳ１１−４で識別した面がすでに順番リストにあるか否かを判断する。ステップＳ１１−４が実行される前に順番リストが面を１つしか含んでいない場合、ステップＳ１１−４で識別した面はいずれもリストにはない。これに対し、ステップＳ１１−４が実行されたときに２つ以上の平面が順番リストに存在した場合、ステップＳ１１−４で識別した面の１つがリストに存在することになる。ステップＳ１１−４で識別したその他の面はリストにはない。また、ステップＳ１１−４が実行されたときにステップＳ８−６で選択した頂点を有する平面が全て順番リストに存在する場合、ステップＳ１１−４で識別した面はいずれもすでに順番リストに存在しており、頂点を共有する全ての平面の隣接順番が決定される。
【００９４】従って、ステップＳ１１−４で識別した少なくとも１つの平面が順番リストに存在しないとステップＳ１１−６で判断した場合、ステップＳ１１−８に進んでリストに存在しない平面をリストに追加する。すなわち、ステップＳ１１−４で識別した２つの平面のいずれもが順番リストになければ、ステップＳ１１−８の処理で、２つの面のいずれかを任意に選択しリストに追加する。ステップＳ１１−４で識別した２つの面の片方だけがリストにない場合には、ステップＳ１１−８でこの面をリストに追加する。
【００９５】ステップＳ１１−４で識別した平面が２つともすでにリストに存在するとステップＳ１１−６で判断した場合、処理を終了する。
【００９６】図８に戻って、ステップＳ８−１０で、多面体生成器３０７０はステップＳ８−８で識別され、ステップＳ８−６で選択した頂点を共有する平面を検討し、４つ以上の平面がその頂点で接するか否かを判断する。
【００９７】ステップＳ８−１０で４つ以上の平面が頂点で接すると判断した場合、ステップＳ８−１２で、多面体生成器３０７０はステップＳ８−６で選択した頂点を複数の新たな「仮想」頂点で置換する。ステップＳ８−８で識別した平面が３つ以上は新たな頂点のそれぞれで接しないようになっている。
【００９８】詳細には、本実施形態では、ｎ個の平面多角形面ｐ1、ｐ2、．．．、ｐnが頂点で接する場合、多面体生成器３０７０はその頂点をｎ−２個の新たな仮想頂点（ｐ1、ｐ2、ｐn）、（ｐ2、ｐ3、ｐn）、．．．、（ｐn-2、ｐn-1、ｐn）で置換する。頂点（ｐ1、ｐ2、ｐn）は平面ｐ1、ｐ2、及びｐnがその頂点で接することを定義する。
【００９９】本実施形態では、ステップＳ８−１２で生成された新たな仮想頂点はそれぞれ、それが置換するステップＳ８−６で選択した元の頂点と同じ３Ｄ位置を有する。
【０１００】ステップＳ８−１２で多面体生成器３０７０によって行われる処理について図１２を参照の上でより詳細に説明する。図１２は図１０に示す例に対応する。
【０１０１】最初に図１０において、６つの多角形面Ａ、Ｂ、Ｃ、Ｄ、Ｅ、及びＦが頂点３６２０で接している。従って、この例では「ｎ」は６であり、ステップＳ８−１２で多面体生成器３０７０は頂点３６２０を４つの新たな仮想頂点で置換する（本例ではｎ−２＝４）。
【０１０２】次に図１２において、多面体生成器３０７０によって追加された４つの新たな仮想頂点は頂点３６３０、３６４０、３６５０、及び３６６０である。図１２では見やすいよう、新たな頂点を異なる位置に示してある。しかし、上述したように、新たな仮想頂点はそれぞれ、実際には元の頂点３６２０の同じ位置を有するように定義されている。
【０１０３】仮想頂点３６３０は３つの多角形ｐ1、ｐ2、及びｐnがこの頂点で接するように定義される。図１２の例では多角形Ａ、Ｂ、及びＦが頂点３６３０で接する。
【０１０４】仮想頂点３６４０は３つの多角形ｐ2、ｐ3、及びｐnがこの頂点で接するように定義される。図１２の例では多角形Ｂ、Ｃ、及びＦが頂点３６４０で接する。
【０１０５】仮想頂点３６５０は３つの多角形ｐ3、ｐ4、及びｐnがこの頂点で接するように定義される。図１２の例では多角形Ｃ、Ｄ、及びＦが頂点３６５０で接する。
【０１０６】同様に、仮想頂点３６６０は３つの多角形ｐ4、ｐ5、及びｐ6がこの頂点で接するように定義される。図１２の例では多角形Ｄ、Ｅ、及びＦが頂点３６６０で接する。
【０１０７】図８に戻って、ステップＳ８−１２の処理を終えた後（あるいは、その頂点で４つ以上の平面が接することがないため、ステップＳ８−１２の処理が不必要であるとステップＳ８−１０で判断した場合）、ステップＳ８−１４に進む。
【０１０８】ステップＳ８−１４で、多面体生成器３０７０は現在検討中の多面体の中に未処理の頂点があるか否かを判断する。多面体の中のそれぞれの頂点が上記の方法で処理されるまでステップＳ８−６からＳ８−１４を繰り返す。
【０１０９】この処理を行った結果、多面体生成器３０７０はステップＳ８−４で生成した多面体を複合多面体から単一多面体へと変換する。
【０１１０】ステップＳ８−１６で、多面体生成器３０７０は処理すべき他の三角デプスマップが存在するか否かを判断する。
【０１１１】ステップＳ２−８で生成された三角デプスマップがそれぞれ上記の方法で処理されるまでステップＳ８−２からＳ８−１６を繰り返す。
【０１１２】このように、多面体生成器３０７０は、デプスマップ３２１０に対する図９ｃに示す多面体３６００のように、各デプスマップに対して多面体を生成する。
【０１１３】以下に説明するように、処理装置３００２はこれらの多面体を形成する平面多角形の交点を計算する。３つの多角形が接する３Ｄ点はいずれも（これらの多角形が同じデプスマップ多面体のものか、２つあるいは３つの異なるデプスマップの多面体かにかかわらず）被写体オブジェクト３３００の面上の点を潜在的に表す３Ｄ点を定義する。それぞれの潜在点を検査し、それが実際に被写体オブジェクト上の点を表すものか否かを判断する。次に実際の面点を連結し、被写体オブジェクト３３００の面を表す３Ｄ多角形メッシュで構成される３Ｄコンピュータモデルを生成する処理を行う。
【０１１４】図２に戻って、ステップＳ２−１２で、３Ｄ点計算器３０９０は被写体オブジェクト３３００の面上に存在する３Ｄ点を計算する処理を行う。生成された３Ｄコンピュータモデルが正確に被写体オブジェクト３３００の面を表せるように、被写体オブジェクトの面の頂点を形成する多角形のそれぞれの交点を計算する必要がある。第２実施形態で説明するように、これはそれぞれの多角形を他の多角形に対して検査し、３Ｄ点の完全な組を生成することで達成される。しかし、このようにして被写体オブジェクト面の頂点を表す３Ｄ点を計算するのに必要な計算数は極めて多い。具体的には、全ての多面体中の多角形の総数をｎとした場合、Ｏ（ｎ3）回の計算が必要となる。加えて、検査された多角形の多くは交差しないため（従って３Ｄ点を生成しないため）また被写体オブジェクト２１０の面上に存在しない３Ｄ点を生成しても良いため（従ってどの３Ｄ点が実際に被写体オブジェクト２１０のモデルの頂点を表すかを判断するために３Ｄ点の処理が必要となる）計算の多くは不必要である。
【０１１５】結果的に、この第１実施形態では、被写体オブジェクト面の頂点を表す３Ｄ点を計算するのに必要な計算の数を減らすように処理を行う。
【０１１６】この処理を詳細に説明する前に、処理の原則について説明する。
【０１１７】本実施形態では、この処理によって、ステップＳ２−１０で生成した多面体を含む３Ｄ空間のボリュームを検討し、ボリュームを検査することで以下のことを判断する。すなわち、（１）交差させることで３Ｄ点を生成できるだけの数（本実施形態では３つ）の多角形がボリューム中に存在しないか、あるいは、以下に詳細に説明するようにボリューム中の多角形が被写体オブジェクト３３００の面の頂点を表す３Ｄ点で交差できないといった理由でボリュームを破棄できるか否か。
（２）交差させることで所定数（本実施形態では１つ）より多い、被写体オブジェクト３３００の面の頂点を表す３Ｄ点を生成できる十分な数の多角形がボリューム中に含まれているので、より小さいボリュームを検討するためにボリュームを再分割するか否か。
（３）交差させることで十分に小さな所定数（本実施形態では１つ）の、被写体オブジェクト３３００の面の頂点を表す３Ｄ点を生成できる十分な数（本実施形態では３つ）の多角形がボリューム中に含まれているか否か。この場合、これらの点の３Ｄ位置を計算し検査することで、それらが実際に被写体オブジェクト３３００の頂点を表すか否か。
【０１１８】こうして、３Ｄ点の計算に無関係な不必要な処理を避けながら、デプスマップ多面体の交点によって定義された被写体オブジェクト３３００の面の全ての頂点が計算されるようにする。特に、３Ｄ空間のボリュームのかなりの部分はさらなる計算なしに破棄できる。
【０１１９】ボリューム中の多角形が、被写体オブジェクト３３００の面の頂点を表す３Ｄ点で交差できないためにそのボリュームを破棄できるか否かを判断するには、その３Ｄ点で交差する多面体を与えずにその３Ｄ点が全ての多面体に存在するか否かを判断する処理を行う。図３及び９ｃに示す例では、デプスマップ３２１０、３２２０、及び３２３０の多面体からの多角形の交点によって定義された３Ｄ点の場合、この３Ｄ点がデプスマップ３２００、３２４０、３２５０、３２６０及び３２７０の多面体の全てに存在するか否かを判断する（これはこれらの多面体は３Ｄ点で交差する３つの平面のうち１つを含まないためである）。以下に述べるように、３Ｄ点が少なくとも１つのデプスマップ多面体の外側に存在することがわかった場合、本実施形態の処理ではこの点を計算、検査せずに、行う処理量を削減する。
【０１２０】本実施形態では、３Ｄ点を計算したとき、引き続いて、それが被写体オブジェクト３３００の頂点を表すか否かを判断することを検査する。これは３つの平面多角形を含む３Ｄボリュームを識別したときに３Ｄ点を計算するためである。しかし、ボリューム中では多角形は３Ｄ点で実際に交差しない。そのため、本実施形態では検査を行って計算した３Ｄ点が識別したボリューム中にあるか否かを判断する。さらに、多角形が存在する３つの平面の交点を計算することで３Ｄ点を計算する。計算した３Ｄ点は１つ以上の多角形に存在しない可能性がある。本実施形態では検査を行い計算した３Ｄ点が識別したボリューム内にあり、３つの平面全てに含まれるか否かを判断する。
【０１２１】本実施形態で行われる被写体オブジェクト３３００の頂点を表す３Ｄ点を計算する処理について詳細に説明する。
【０１２２】図１３は、ステップＳ２−１２で３Ｄ点計算器３０９０により実行される処理動作を示す。
【０１２３】図１３のステップＳ１３−２において、３Ｄ点計算器３０９０は、被写体オブジェクト面の頂点を表す全ての３Ｄ点が存在する３Ｄ空間のボリュームを定義する。
【０１２４】詳しくは本実施形態において、ステップＳ１３−２で、３Ｄ点計算器３０９０はステップＳ８−４で生成した３Ｄ点の軸整列したバウンディングボリュームであるボリュームを定義する。換言すれば、３Ｄ点計算器３０９０はステップＳ８−４で生成された多面体の各「前」端面（例えば図９ｃの例では面３６１０）を形成する点に対してバウンディングボリュームを定義する。バウンディングボリュームは従来の方法でＸ軸、Ｙ軸、及びＺ軸に平行な稜線を有して定義される。従って、ここでは、この処理については説明を省略する。
【０１２５】ステップＳ１３−４で３Ｄ点計算器３０９０はステップＳ１３−２で定義された３Ｄボリュームを複数のより小さい子ボリュームに再分割し、その子ボリュームを格納スタックの最上部に加える。すなわち本実施形態では、ステップＳ１３−４でのボリューム再分割は、ボリュームを二値再分割して８つの新たな子ボリュームを生成することを含むものである。
【０１２６】ステップＳ１３−６で、３Ｄ点計算器３０９０はステップＳ１３−４で作成したスタックの最上部から次のボリューム（ステップＳ１３−６が初めて行われる場合は最初のボリューム）を取り出し、ステップＳ１３−８でスタックから取り出したボリュームの状態を判断する。
【０１２７】ステップＳ１３−８の処理において、３Ｄ点計算器３０９０は、ステップＳ１３−６でスタックから取り出されたボリュームが、被写体オブジェクト３３００の頂点を表す３Ｄ点を含む可能性がない（従って破棄できる）か否か、被写体オブジェクト３３００の頂点を表す２つ以上の３Ｄ頂点を定義する十分な数の多角形を含むためにボリュームを再分割する必要があるか否か、あるいは、被写体オブジェクトの頂点を表す単一の３Ｄ点のみを定義する十分な多角形をボリュームが含むか否かを判定する。この場合、３Ｄ点の位置を計算し、検査することができる。
【０１２８】図１４は、ステップＳ１３−８で３Ｄ点計算器３０９０によって行われる処理動作を示す。
【０１２９】図１４において、ステップＳ１４−２からＳ１４−１０で、３Ｄ点計算器３０９０はステップＳ２−１０で生成したデプスマップ多面体を定義するどの多角形がステップＳ１３−６でスタックから取り出したボリュームに交差するのかを判断する処理を行う。この処理は親ボリューム（すなわち、現在処理されているボリュームを作成するために分割したボリューム）に交差する多角形のみを検査し、親ボリュームの子ボリュームを処理するときに現在使用中のボリュームに交差する多角形のリストを記憶することで計算上高効率な方法で行われる。
【０１３０】具体的には、ステップＳ１４−２で、３Ｄ点計算器３０９０は親ボリュームに交差する多角形のリストを検討する（親ボリュームがステップＳ１３−２で定義されたバウンディングボリュームである場合、これらの多角形が全てデプスマップ多面体を定義する）。
【０１３１】ステップＳ１４−４で、３Ｄ点計算器３０９０はステップＳ１４−２で読み出されたリストの次の多角形（ステップＳ１４−１が初めて行われる場合は最初の多角形）を検討し、ステップＳ１４−６で現在のボリュームにその多角形が交差するか否かを判断する。本実施形態で行われる、多角形が現在のボリュームに交差するか否かを検査する処理は、例えばAlan W Paeth編Graphic Gems V (MorganKaufmann社刊、375〜379ページ、ISBN 0-12-543455-3”に記載されるような従来の方法で行われる。
【０１３２】ステップＳ１４−６で多角形が現在のボリュームに交差すると判断した場合、ステップＳ１４−８で、３Ｄ点計算器３０９０はその多角形を現在のボリュームに交差する多角形のリストに追加する。
【０１３３】これに対し、ステップＳ１４−６で多角形が現在のボリュームに交差しないと判断した場合、ステップＳ１４−８を省略する。
【０１３４】ステップＳ１４−１０で、３Ｄ点計算器３０９０はステップＳ１４−２で読み出されたリストに他の多角形があるか否かを判断する。ステップＳ１４−２で読み出されたリストの多角形をそれぞれ上記の方法で処理するまでステップＳ１４−４からＳ１４−１０を繰り返す。
【０１３５】ステップＳ１４−１２からＳ１４−２６で、３Ｄ点計算器３０９０は、１つ以上のデプスマップ多面体の完全に外側にある（従ってボリューム内の３Ｄ点は被写体オブジェクト３３００の頂点を表すことができない）ため、ステップＳ１３−６でスタックから取り出したボリュームが破棄可能か否かを判断する処理を行う。本実施形態ではこの処理はボリュームを検査することで、それがステップＳ２−１０で生成されたデプスマップ多面体の全てによって閉じられているか否かを判断することを含む。加えて、この処理は特に計算上高効率な方法で行われる。具体的には、あるボリュームは多角形で閉じられる場合、そのボリュームの子ボリュームも全てその多角形で閉じられる。そこで本実施形態では、３Ｄ点計算器３０９０は親ボリュームを閉じると検証されなかった多面体（以下「アクティブ多面体」という）のみを検査することでそれらが現在のボリュームを閉じるか否かを判断する。ある多面体が現在のボリュームを閉じると検証された場合、現在のボリュームの各子ボリュームに適用されるアクティブ多面体のリストからこの多面体を除去する。
【０１３６】具体的には、ステップＳ１４−１２で、３Ｄ点計算器３０９０は現在のボリュームについてのリストとして親ボリュームに関するアクティブ多面体のリスト（すなわち、上述したように、親ボリュームを閉じると検証されていない多面体のリスト）を複製する。親ボリュームがステップＳ１３−２で定義されたバウンディングボリュームの場合、アクティブ多面体のリストはステップＳ２−１０で生成された全ての多面体を含む。
【０１３７】ステップＳ１４−１４で、３Ｄ点計算器３０９０はステップＳ１４−１２で複製されたリストにある多面体の中で現在のボリュームに交差する少なくとも１つの多角形を含まないものがあるか否かを判断する。詳しくは、３Ｄ点計算器３０９０はステップＳ１４−８で生成された現在のボリュームに交差する多角形のリストを読み出すことで、現在のボリュームに交差する少なくとも１つの多角形を有さない、ステップＳ１４−１２で複製されたリストの多面体を識別する。
【０１３８】ある多面体が現在のボリュームに交差しない多角形を有する場合、現在のボリュームは一部は多面体の内側に、一部は外側に位置する。また、全ての多面体が現在のボリュームに交差する多角形を含む場合、現在のボリュームは１部がそれぞれの多面体の内側に、一部が外側に位置する。そのボリュームは少なくとも１つの多面体の外側に完全に位置しているわけではないので破棄できない。従って、ステップＳ１４−１４で全ての多面体が現在のボリュームに交差する少なくとも１つの多角形を含むと判断した場合、ステップＳ１４−２８に進む。この処理については後述する。
【０１３９】これに対し、ステップＳ１４−１４で、或る多面体が現在のボリュームに交差する多角形を１つも含まないと判断した場合、現在のボリュームは完全にその多面体の内側に位置するか（すなわちボリュームはその多面体によって閉じられる）、あるいは完全にその多面体の外側に位置する。この場合、３Ｄ点計算器３０９０はステップＳ１４−１６からＳ１４−２６で現在のボリュームに交差する多角形を１つも有さない多面体の各々について現在のボリュームがその内側に存在するか外側に存在するかを判断する処理を行う。
【０１４０】具体的には、ステップＳ１４−１６で、３Ｄ点計算器３０９０は現在のボリュームに交差する多角形を１つも有しない次の多面体（ステップＳ１４−１６が初めて行われる場合は最初の多面体）を検討する。
【０１４１】ステップＳ１４−１８で、３Ｄ点計算器３０９０はステップＳ１３−６でスタックから取り出したボリュームがその多面体の内側にあるか外側にあるかを検査する。
【０１４２】図１５はステップＳ１４−１８で３Ｄ点計算器３０９０によって行われる処理動作を示す。
【０１４３】図１５において、ステップＳ１５−２で、３Ｄ点計算器３０９０はステップＳ１３−６でスタックから取り出したボリューム中から１点を選択する。ボリューム中のどの点でも良いが、本実施形態では３Ｄ点計算器３０９０はボリュームの第１面の第１頂点を選択する。
【０１４４】ステップＳ１５−４で、３Ｄ点計算器３０９０はステップＳ１５−２で選択した点から、検査されている多面体を生成したデプスマップ画像に対するカメラの投影の中心の位置に向けて光線を投影する。換言すれば、図９ｃの例に示す多面体３６００を検査している場合、この多面体３６００はデプスマップ３２１０から生成されたものであるため、点３４１０に向けて光線を投影する。
【０１４５】光線の投影に加えて、３Ｄ点計算器３０９０は多面体と光線の交差の数を計算し、ステップＳ１５−６で、多面体と光線の交差の数が奇数か偶数かを判断する。
【０１４６】この検査の理由について図１６ａ及び１６ｂを参照して説明する。
【０１４７】図１６ａにおいて、ステップＳ１３−６でスタックから取り出したボリューム３７００がある多面体（例えば図９ｃの例に示す多面体３６００）の内側にある場合、ステップＳ１５−４で投影された光線３７１０は奇数回多面体３６００と交差する。図１６ａの例では、光線３７１０は点３７２０において１回多面体３６００と交差する。
【０１４８】多面体３６００の形状によっては、光線３７１０は多面体３６００と３回、５回、あるいはそれ以上の奇数回交差する可能性がある。それでもボリューム３７００が多面体３６００の内側にある限り、光線３７１０と多面体３６００の交差の数は奇数になる。これは光線３７１０が投影された投影位置３４１０のカメラ中心が、カメラに対して生成された多面体３６００の外側にあるためである。
【０１４９】これに対し、図１６ｂにおいて、ステップＳ１３−６でスタックから取り出したボリューム３７３０又は３７４０が多面体３６００の外側に位置する場合、ステップＳ１５−４で投影された光線は多面体３６００と偶数箇所で交差する。詳細には、ボリューム３７３０から投影位置３４１０のカメラ中心に対して投影された光線３７５０は多面体３６００と２箇所、すなわち点３７６０（光線が多面体に入射する位置）及び３７７０（光線が多面体から出射する位置）で交差する。もちろん、多面体３６００の形状によっては光線３７５０はそれ以上の偶数箇所で多面体３６００と交差する可能性がある。ボリューム３７４０から投影位置３４１０のカメラ中心に対して投影される光線３７８０の場合、この光線は多面体３６００と交差することはない（本実施形態では交差ゼロを偶数個の交差とみなす）。
【０１５０】図１５に戻って、ステップＳ１５−４で投影された光線と多面体の交差の数が奇数であるとステップＳ１５−６で判断した場合、３Ｄ点計算器３０９０はステップＳ１５−８で、ステップＳ１３−６でスタックから取り出したボリュームが多面体の内側に位置することを示すフラグを設定する。
【０１５１】これに対し、ステップＳ１５−４で投影された光線と多面体の交差の数が偶数であるとステップＳ１５−６で判断した場合、３Ｄ点計算器３０９０はステップＳ１５−１０で、ステップＳ１３−６でスタックから取り出したボリュームが多面体の外側に位置することを示すフラグを設定する。
【０１５２】図１４に戻って、ステップＳ１４−２０で、３Ｄ点計算器３０９０はステップＳ１５−８あるいはＳ１５−１０で設定されたフラグを読取り、現在のボリュームが多面体の内側か外側かを判断する。
【０１５３】ボリュームが多面体の外側に位置するならば、ステップＳ１４−２２で、３Ｄ点計算器３０９０は、ステップＳ１３−６でスタックから取り出したボリュームの状態を「破棄」と判断したことを示すフラグを設定する。これはボリュームが完全にデプスマップ多面体の１つの外側に位置しており、従って被写体オブジェクト３３００の頂点を表す３Ｄ点を含むことができないからである。
【０１５４】ステップＳ１４−２２を実行した後、処理は図１３のステップＳ１３−１０に戻る。これは、３Ｄ点計算器３０９０が現在のボリュームが被写体オブジェクト３３００の頂点を表す３Ｄ点を含むことができないと判断するには、現在のボリュームの外側にある１つの多面体を識別すれば十分であり、現在のボリュームと多面体の関係をこれ以上判断する必要がないからである。
【０１５５】これに対し、ステップＳ１３−６でスタックから取り出したボリュームが多面体の内側に位置するとステップＳ１４−２０で判断した場合、３Ｄ点計算器３０９０はステップＳ１４−２４でその多面体を現在のボリュームに対するアクティブ多面体のリストから削除する。そのためその多面体が現在のボリュームの子ボリュームを閉じるか否かを判断するためにその多面体を検査することはない。
【０１５６】処理はステップＳ１４−２６に進み、３Ｄ点計算器３０９０はステップＳ１４−１２で複製されたリストの中に現在のボリュームに交差する多角形を１つも含まない多面体が他にも存在するか否かを判断する。上記の方法でこうした多面体をそれぞれ処理するまで、あるいはステップＳ１４−２０で現在のボリュームが１つの多面体の外側に位置すると判断されるまで（この場合、ステップＳ１４−２２でボリュームの状態は「破棄」と判断され、処理はステップＳ１３−１０に戻る）、ステップＳ１４−１６からＳ１４−２６を繰り返す。
【０１５７】ステップＳ１４−１２で複製されたリストの中に現在のボリュームに交差する多角形を１つも含まない多面体が存在しないとステップＳ１４−１４で判断した場合、あるいはこのような多角形が全て処理され、現在のボリュームを閉じるものとステップＳ１４−２６で判断した場合、処理はステップＳ１４−２８に進む。
【０１５８】ステップＳ１４−２８で、３Ｄ点計算器３０９０はステップＳ１４−８で生成された、現在のボリュームと交差する多角形を定義したリストを読み出す。
【０１５９】ステップＳ１４−３０で、３Ｄ点計算器３０９０はステップＳ１４−２８で読み出されたリストの中の多角形の数が３つか、３つより多いかあるいは少ないかを判断する。
【０１６０】ステップＳ１４−３０で現在のボリュームに交差する多角形の数が３つ未満であると判断した場合、ステップＳ１４−３２で３Ｄ点計算器３０９０はステップＳ１３−６でスタックから取り出したボリュームの状態が「破棄」と判断されたことを示すフラグを設定する。このボリュームが交差することによって被写体オブジェクト３３００の頂点を表す３Ｄ点を生成する十分な数の多角形を含まないからである。処理は図１３のステップＳ１３−１０に進む。
【０１６１】ステップＳ１４−３０で現在のボリュームに交差する多角形の数を３と判断した場合、ステップＳ１４−３４で３Ｄ点計算器３０９０はステップＳ１３−６でスタックから取り出したボリュームの状態が「頂点計算」と判断されたことを示すフラグを設定する。このボリュームが交差することによって被写体オブジェクト３３００の頂点を表す単一の３Ｄ点を定義する適切な数の多角形を含むからである。処理は図１３のステップＳ１３−１０に進む。
【０１６２】ステップＳ１４−３０で、現在のボリュームに交差する多角形の数を３より大きいと判断した場合、ステップＳ１４−３６に進み、３Ｄ点計算器３０９０は現在のボリュームに交差する多角形が全て同じデプスマップ多面体のものであると判断する。これは例えばステップＳ８−１２で生成された仮想頂点で多角形が交差する場合に起こりうる。本実施形態ではある元の頂点に置換する仮想頂点は全て同じ３Ｄ位置を有するからである。
【０１６３】ステップＳ１４−３６で現在のボリュームに交差する多角形が全て同じ多面体からのものと判断した場合、ステップＳ１４−３８で、３Ｄ点計算器３０９０は、ステップＳ１３−６でスタックから取り出したボリュームの状態が「複数頂点計算」であることを示すフラグを設定する。次に処理は図１３のステップＳ１３−１０に進む。
【０１６４】これに対し、ステップＳ１４−３６で現在のボリュームに交差する多角形が全て同じ多面体からのものでなはいと判断した場合、ステップＳ１４−４０で、３Ｄ点計算器３０９０は、ステップＳ１３−６でスタックから取り出したボリュームの状態が「再分割」であることを示すフラグを設定する。これは交差し単一の、被写体オブジェクト３３００の頂点を表す３Ｄ点を生成する異なる多面体からの多角形が必要な数（３）より多く含まれているためである。次に処理は図１３のステップＳ１３−１０に進む。
【０１６５】図１４を参照して説明した処理の結果として、３Ｄ点計算器３０９０は、ステップＳ１３−６でスタックから取り出したボリュームの状態を判断し、そのボリュームに対して行われるべき次の処理を示す判断された状態に従ってフラグを設定する。
【０１６６】図１３に戻って、ボリュームの状態を判断する上述の処理を終えた後、ステップＳ１３−１０で３Ｄ点計算器３０９０はボリュームの状態が「頂点計算」であるか否かを判断する。
【０１６７】ステップＳ１３−１０で頂点を計算すると判断した場合、処理はステップＳ１３−１２に進み、頂点を計算する。それ以外の場合はステップＳ１３−１２を省略する。
【０１６８】図１７はステップＳ１３−１２で３Ｄ点計算器３０９０が頂点を計算する処理動作を示す。
【０１６９】図１７において、ステップＳ１７−２で、３Ｄ点計算器３０９０は３つの多角形（すなわち、ステップＳ１３−６でスタックから取り出したボリュームと交差することが判明した３つの多角形）を含む３つの平面が交差する点の３Ｄ位置を計算する。この処理は従来の平面交差法を用いて行われる。
【０１７０】ステップＳ１７−４で、３Ｄ点計算器３０９０はステップＳ１７−２で計算した３Ｄ点がステップＳ１３−６で取り出したボリュームと３つの２Ｄ多角形全てに存在するか否かを判断する。この検査が必要なのは、この３Ｄ点が多角形を含む平面の交点として計算され、従ってこれらの平面は必ずしもボリューム内の１点で、あるいは事実上多角形の一部（すなわち内部）の１点で、互いに交差する必要がないからである。ステップＳ１３−６でスタックから取り出したボリュームは軸整列した直平行六面体であるため、３Ｄ点の座標とボリュームのＸ、Ｙ、及びＺ座標の最大及び最小値の間の従来の不など式検査を用いて、その３Ｄ点がボリュームの内側にあるかどうかを判断する検査が行われる。３Ｄ点がそれぞれの２Ｄ多角形の中にあるか否かを判断する処理も、例えば、P.Heckbert編Graphics Gems IV (16〜46ページ、Morgan Kaufmann社刊、ISBN 0-12-336155-9)に記載されるような従来の方法で行われる。
【０１７１】ステップＳ１７−４で計算した３Ｄ点がボリュームと３つの多角形すべての内側にあると判断された場合、処理はステップＳ１７−６に進み、３Ｄ点計算器３０９０は被写体オブジェクト３３００の頂点を表す３Ｄ点のリストに計算した３Ｄ点を追加する。
【０１７２】これに対し、ステップＳ１７−４で計算した３Ｄ点がボリュームあるいは３つの多角形に少なくとも１つの外側にあると判断された場合、ステップＳ１７−６は省略される。
【０１７３】ステップＳ１７−８で、３Ｄ点計算器３０９０はステップＳ１３−６でスタックから取り出したボリュームは処理済のため次に破棄することを示すフラグを設定する。
【０１７４】図１３に戻って、ステップＳ１３−１４で３Ｄ点計算器３０９０はステップＳ１３−６でスタックから取り出したボリュームの状態が「複数頂点計算」であるか否かを判断し、もしもそうならば、ステップＳ１３−１６で複数の頂点を計算し検査する処理を行う。
【０１７５】図１８は、ステップＳ１３−１６で３Ｄ点計算器３０９０が行う処理動作を示す。
【０１７６】図１８において、ステップＳ１８−２で３Ｄ点計算器３０９０はボリュームに交差する各多角形の全ての頂点を含む頂点の組を頂点の開始組として検討する。
【０１７７】ステップＳ１８−４で、３Ｄ点計算器３０９０は、そこで接する３つの多角形がボリュームに交差する全ての多角形である組の中の頂点を識別する。
【０１７８】ステップＳ１８−６で、３Ｄ点計算器３０９０はステップＳ１８−４で識別した次の頂点（ステップＳ１８−６が初めて行われる場合は最初の頂点）を検討する。
【０１７９】ステップＳ１８−８で、３Ｄ点計算器３０９０はステップＳ１８−６で選択した頂点がステップＳ１８−６でスタックから取り出したボリュームの内側に存在するか否かを検査し、もしそうなら、ステップＳ１８−１０で被写体オブジェクトの頂点のリストにその頂点を追加する。これに対し、ステップＳ１８−８で頂点がボリュームの外側にあると判明した場合、ステップＳ１８−１０は省略される。この処理の結果、ステップＳ８−１２で生成された仮想頂点が被写体オブジェクトの頂点のリストに追加され、結果的に、同じ位置を有する頂点がリストに含まれることになる。
【０１８０】ステップＳ１８−１２で、３Ｄ点計算器３０９０はステップＳ１８−４で識別した頂点で他に処理すべきものがあるか否かを判断する。上記の方法でそれぞれの頂点が処理されるまでステップＳ１８−６からＳ１８−１２を繰り返す。
【０１８１】こうしてステップＳ１８−４で識別した頂点を全て処理すると、ステップＳ１８−１４で３Ｄ点計算器３０９０はステップＳ１３−６でスタックから取り出したボリュームは処理済のためその状態が「破棄」であることを示すフラグを設定する。
【０１８２】図１３に戻って、ステップＳ１３−１８で３Ｄ点計算器３０９０はステップＳ１３−６でスタックから取り出したボリュームの状態が「破棄」あるいは「再分割」に設定されているか否かを判断する。
【０１８３】状態が「破棄」に設定されている場合（ステップＳ１３−８の処理の結果、あるいはステップＳ１７−８かステップＳ１８−２４の結果）、ステップＳ１３−２０で３Ｄ点計算器３０９０はボリュームを破棄する。
【０１８４】これに対し、状態が「再分割」に設定されている場合、ステップＳ１３−２２で３Ｄ点計算器３０９０はボリュームを再分割し、ステップＳ１３−４で生成されたすタックの最上層に子ボリュームを追加する。本実施形態では、ステップＳ１３−２２のボリューム再分割はステップＳ１３−４における再分割と同じ方法で行われる。すなわち、２値再分割を行って８つの新たな子ボリュームを生成することを含む。
【０１８５】ステップＳ１３−２０あるいはステップＳ１３−２２に続いて処理はステップＳ１３−２４に進み、３Ｄ点計算器３０９０はスタック上に他のボリューム（ステップＳ１３−２２で追加した子ボリュームを含む）があるか否かを判断する。
【０１８６】スタック上の各ボリュームを上記の方法で処理するまでステップＳ１３−６からＳ１３−２４を繰り返す。
【０１８７】こうして処理を行う結果として、３Ｄ点計算器３０９０は被写体オブジェクト３３００の頂点を表す３Ｄ空間中の点の組を生成する。それぞれの頂点は１つ以上のデプスマップ多面体からの３つの多角形が接する位置を表す。
【０１８８】図２に戻って、被写体オブジェクト３３００の頂点を表す３Ｄ点を計算するステップＳ２−１２の処理の後、ステップＳ２−１４で多角形生成器３１００は計算した３Ｄ点を連結して被写体オブジェクトの面を表す多角形メッシュを生成する処理を行う。
【０１８９】図１９は、ステップＳ２−１４で多角形生成器３１００が行う処理動作を示す。
【０１９０】図１９において、ステップＳ１９−２で多角形生成器３１００は生成される多角形メッシュの多角形について識別データを生成し、３Ｄ点計算器３０９０によって生成された各３Ｄ点についていわゆる「署名」を判断する。
【０１９１】図２０は、ステップＳ１９−２で多角形生成器３１００によって行われる多角形ＩＤデータを生成し被写体オブジェクト３３００の頂点を表すそれぞれの計算した３Ｄ点について「署名」を定義する処理動作を示す。
【０１９２】図２０において、ステップＳ２０−２で多角形生成器３１００は被写体オブジェクト３３００の頂点として３Ｄ点計算器３０９０が３Ｄ点を計算する次の多角形（このステップが初めて行われる場合は最初の多角形）を検討する。
【０１９３】ステップＳ２０−４で、多角形生成器３１００はステップＳ２０−２で選択した多角形に、このステップの以前の繰り返しによりＩＤが割り当てられていない場合、特有のＩＤを割り当てる。
【０１９４】ステップＳ２０−６で、多角形生成器３１００は被写体オブジェクト３３００の頂点を計算するのに使われたその他の多角形が存在するか否かを判断する。上記の方法により、各多角形を処理するまでステップＳ２０−２からＳ２０−６を繰り返す。
【０１９５】ステップＳ２０−８で、多角形生成器３１００はステップＳ１７−６及びＳ１８−１０で多角形生成器３１００によって生成されたリストから被写体オブジェクト３３００の次の計算した頂点を検討し、ステップＳ２０−１０でその３Ｄ点で接する多角形のＩＤを含む頂点の署名を定義する（これらのＩＤはステップＳ２０−４で多角形に割り当てられる）。
【０１９６】ステップＳ２０−１２で、多角形生成器３１００はステップＳ１７−６及びＳ１８−１０で生成されたリストに被写体オブジェクト３３００の他の計算した頂点が存在するか否かを判断する。上記の方法により、各頂点を処理するまでステップＳ２０−８からＳ２０−１２を繰り返す。
【０１９７】図１９に戻って、ステップＳ１９−４で多角形生成器３１００は３Ｄ点計算器３０９０によって計算された３Ｄ点を、ステップＳ１９−２で定義された署名に従って組にまとめる。
【０１９８】図２１は、ステップＳ１９−４で多角形生成器３１００によって行われる処理動作を示す。
【０１９９】図２１において、ステップＳ２１−２で多角形生成器３１００はステップＳ２−１２で３Ｄ点計算器３０９０によって計算された次の３Ｄ点（ステップＳ１９−２が初めて行われる場合は最初の３Ｄ点）を検討する。
【０２００】ステップＳ２１−４で、多角形生成器３１００はステップＳ２１−２で選択した点の署名（ステップＳ１９−２で割り当てられた署名）を読み取り、ステップＳ２１−６で署名に定義された各多角形に対する点の組にこの３Ｄ点を割り当てる。つまり、３Ｄ点は３つの異なる組に割り当てられる。３Ｄ点の署名には各多角形に対して１つの組が定義されている。
【０２０１】ステップＳ２１−８で、多角形生成器３１００は３Ｄ点計算器３０９０によって計算された、処理を要する３Ｄ点が他にもあるか否かを判断する、上記の方法によって各３Ｄ点を処理するまでステップＳ２１−２からＳ２１−８を繰り返す。
【０２０２】図２１を参照して説明した処理の結果として、被写体オブジェクト３３００の面モデルの中の各多角形に対して点の組を生成する。各組の点は被写体オブジェクト３３００の面のある平面上に存在する１つ以上の多角形を定義する。
【０２０３】図１９に戻って、ステップＳ１９−６で多角形生成器３１００は被写体オブジェクト３３００の面の一部を表す１つの多角形を生成するように各組の３Ｄ点を連結する順番を判断する。
【０２０４】ステップＳ１９−６で多角形生成器３１００によって行われる処理ステップを詳細に説明する前に、この処理の原則を説明する。
【０２０５】図２２において、４つの３Ｄ点と５つの多角形を例示する。４つの３Ｄ点はステップＳ２−１２で３Ｄ点計算器３０９０によって計算されたもので、Ｖ１、Ｖ２、Ｖ３、及びＶ４とラベル付けする。５つの多角形をａ、ｂ、ｃ、ｄ、及びｅとラベル付けする。
【０２０６】ステップＳ１９−６で多角形生成器３１００によって計算されるべき各エッジ（連結）は２つの３Ｄ点を連結する。どの３Ｄ点を連結するかを判断するために、本実施形態では、多角形生成器３１００は３Ｄ点の署名を使う。より詳しくは、連結されるべき２つの３Ｄ点はステップＳ１９−２で割り当てられたその署名の中に双方の署名に共通な２つの多角形ＩＤを有する。例えば、図２２の３Ｄ点Ｖ１の署名は｛ａ、ｂ、ｅ｝、３Ｄ点Ｖ２の署名は｛ａ、ｂ、ｃ｝である。従って多角形ＩＤａ及びｂはこれらの署名に共通であり、３Ｄ点Ｖ１及びＶ２の連結を識別する。これらが図２２の３Ｄ点Ｖ１及びＶ２の間のエッジで接する多角形を定義するためである。
【０２０７】以下に述べるように、ステップＳ１９−６の処理において、多角形生成器３１００は、連結が最初の３Ｄ点に戻るまで上記の方法により３Ｄ点の署名を使って判断した多角形の周囲の稜線に沿って個々の多角形における３Ｄ点の連結を判断する。
【０２０８】凸型の被写体オブジェクトの場合、３Ｄ点を連結するのに必要な処理は１つしかない。というのはステップＳ１９−４で生成された３Ｄ点の組（同じ多角形平面上に存在する３Ｄ点）にはそれぞれ、同じ２つの多角形ＩＤを署名中に有する３Ｄ点は２つしかないためである。例えば、図２２において、多角形の３Ｄ点のセット（組）は点Ｖ１、Ｖ２、Ｖ３、及びＶ４を備えるが、点Ｖ１及びＶ２のみは署名中に多角形ＩＤａ及びｂを有している。
【０２０９】しかし、凸型ではない被写体オブジェクト面の一部については、署名中に同じ２つの多角形ＩＤを有する３Ｄ点が３つ以上存在する可能性がある。従って、３Ｄ点の連結は署名のみでは判断できない。
【０２１０】例えば、図２３に示す例では４つの３Ｄ点１０００、１０１０、１０２０、及び１０３０が２つの多角形９１０及び１０４０の交点上に存在する。この例では、４つの３Ｄ点１０００、１０１０、１０２０、及び１０３０のそれぞれの署名が多角形９１０及び１０４０の多角形ＩＤを含む。
【０２１１】この問題に対処するために、本実施形態では、多角形生成器３１００は多角形９１０及び１０４０の交点で定義された稜線に沿った順番に基づいた対の点を連結することで３Ｄ点間の連結を判断する処理を行う。この処理を以下に詳細に述べる。
【０２１２】以下に説明するように、本実施形態では、多角形生成器３１００は凸型ではない被写体オブジェクト面の一部に関して生じる可能性のある更なる問題、すなわち１つの多角形の同じ平面にオブジェクト面を表す２つ以上の多角形が存在するという問題に対処する処理をも行う。
【０２１３】こうしたことが生じる第１の例を図２８に示す。ここでは被写体オブジェクト面の一部を表す多角形１０５０及び１０６０が両方とも多角形９１０の平面に存在する。
【０２１４】２つ以上の多角形が同じ平面に存在する第２の例を図２４に示す。この例では、多角形１１００はオブジェクト面の一部を表し、多角形１１１０は被写体オブジェクト面の穴を表す。
【０２１５】ステップＳ１９−６で多角形生成器３１００によって行われる処理を以下に詳細に説明する。
【０２１６】図２５は、ステップＳ１９−６で多角形生成器３１００が行う処理動作を示す。
【０２１７】図２５において、ステップＳ２５−２で多角形生成器３１００は被写体オブジェクト３３００の３Ｄコンピュータモデルに対し空の多角形組（セット）「Ｓ」を作成する。被写体オブジェクト３３００の面の一部を表す多角形を計算しこの空の多角形に追加していく。
【０２１８】ステップＳ２５−４で、多角形生成器３１００は次の多角形「ｐ」を検討し、その多角形についてステップＳ１９−４で生成した組Ｖｐ中の３Ｄ点を読み出す。
【０２１９】ステップＳ２５−６で、多角形生成器３１００はステップＳ２５−４で読み出された組Ｖｐ中に３Ｄ点が存在するか否かを判断する。この処理の第１サイクルでは、組Ｖｐ中に３Ｄ点は存在し、処理はステップＳ２５−８に進む。しかし以降の処理では、点の連結を計算した後で、３Ｄ点を組Ｖｐから削除する。従って、以降のサイクルでは、ステップＳ２５−６において組Ｖｐに３Ｄ点はもう存在しないと判断される可能性があり、この場合、処理はステップＳ２５−５０に進む。これについては後述する。
【０２２０】ステップＳ２５−８で、多角形生成器３１００は新しい多角形データ構造(structure)「ｓ」をステップＳ２５−２で作成した多角形組「Ｓ」に追加する。多角形組「Ｓ」には多角形を定義するデータを生成して入力する。ステップＳ２５−８で、多角形生成器３１００は多角形データ構造「ｓ」で現在検討されている多角形の法線ベクトルを定義するデータを記憶し、多角形の法線を定義する。
【０２２１】ステップＳ２５−１０で、多角形生成器３１００は多角形の開始頂点「ｕ」として組Ｖｐから１つの３Ｄ点を選択する（開始頂点「ｕ」としてはどの３Ｄ点を選択しても良い）。
【０２２２】ステップＳ２５−１２で、多角形生成器３１００は現頂点ポインタ「ｗ」を頂点「ｕ」に設定し、これが現在処理中の頂点であることを表し、ステップＳ２５−１４で開始頂点「ｕ」の署名を読み出す。
【０２２３】ステップＳ２５−１６で、多角形生成器３１００はステップＳ３０−１４で読み出した署名中に定義された多角形「ｑ」を選択する。多角形「ｑ」は（ステップＳ２５−４で選択した）現在検討中の多角形「ｐ」と同じではない。
【０２２４】多角形生成器３１００によって行われる処理の理解を助けるために、図２２の例を参照する。図２２において、例えば、ステップＳ３０−４で選択した多角形「ｐ」を多角形「ａ」とする。組Ｖｐ中の３Ｄ点はＶ１、Ｖ２、Ｖ３、及びＶ４である。
【０２２５】さらに、３Ｄ点Ｖ２がステップＳ２５−１０で開始頂点（ｕ）として選択されたとする。そこでステップＳ２５−１６で、多角形生成器３１００は多角形ｂあるいは多角形ｃを選択する。これらの多角形はいずれも３Ｄ点Ｖ２の署名中に多角形ａとともに定義されているからである。ステップＳ２５−１６で、多角形ｃが選択されたと仮定する。
【０２２６】図２５に戻って、ステップＳ２５−１８で多角形生成器３１００は現在の頂点「ｗ」（すなわち検討した例では３Ｄ点Ｖ２）を組Ｖｐから除去し、ステップＳ２５−２０でこの頂点をステップＳ２５−８で生成した多角形データ構造「ｓ」に追加することで、多角形「ｓ」の１つの頂点を定義する。
【０２２７】ステップＳ２５−２２で、多角形生成器３１００は組Ｖｐに残った、署名の中にステップＳ２５−１６で選択した多角形「ｑ」のＩＤを有する３Ｄ点の組「Ｖｐｑ」を判断する。
【０２２８】再び図２２の例において、３Ｄ点Ｖ３は署名｛ａ、ｃ、ｄ｝を持ち、組Ｖｐでは署名に（ステップＳ２５−１６で選択した）多角形ｃを有する唯一の点である。
【０２２９】ステップＳ２５−２４で、多角形生成器３１００はステップＳ２５−２２で判断された組Ｖｐ中に３Ｄ点が存在するか否かを判断する。
【０２３０】処理の第１サイクルにおいて、組Ｖｐｑには３Ｄ点が存在する。しかし、上述したように、ステップＳ２５−１８で、処理の後組Ｖｐから各３Ｄ点を除去する。そのため、ある多角形の頂点を全て処理すれば、組Ｖｐｑには３Ｄ点は１つもなくなる。この場合、処理はステップＳ２５−６に戻り、多角形生成器３１００は組Ｖｐに３Ｄ点が残っているか否かを判断する。
【０２３１】上述した図２３及び図２４に示すように、多角形「ｐ」（デプスマップ多面体の多角形）中に存在する被写体オブジェクト３３００の多角形は３つ以上あるならば、組Ｖｐに点が残っている可能性はある。多角形「ｐ」に２つ以上の多角形がある場合、ステップＳ２５−２４の検査で、１つの多角形を処理すれば、組Ｖｐｑ中には多角形は１つも残らないと判断される。ステップＳ２５−６の処理では、多角形「ｐ」中の更なる多角形について連結を計算する必要なある場合、組Ｖｐ中に３Ｄ点が残っていると判断される。この場合、処理はステップＳ２５−６からＳ２５−８に進み、多角形「ｐ」中の更なる多角形について新たな多角形データ構造を生成する。
【０２３２】ステップＳ２５−２４で組Ｖｐｑの中に点が存在すると判断した場合、処理はステップＳ２５−２６に進み、多角形生成器３１００は組Ｖｐｑ中の点の数が１に等しいか否かを判断する。組Ｖｐｑ中の３Ｄ点はそれぞれ現在の頂点「ｗ」に連結する可能性のある３Ｄ点を表している。そこで、組Ｖｐｑ中に１つの、そして唯一の点があるならば、図２２に示す状況が生じる。しかし、組Ｖｐｑ中に２つ以上の点があるならば、上述の３Ｄ点１０００、１０１０、１０２０、及び１０３０に関する図２３に示す状況が生じる。
【０２３３】図２５−２６で組Ｖｐｑ中に１つの、そして唯一の３Ｄ点があると判断した場合、処理はステップＳ２５−２８に進み、多角形生成器３１００は多角形「ｓ」の次の頂点「ｘ」（現在の頂点に連結する頂点）を組Ｖｐｑ中の３Ｄ点に設定する。
【０２３４】図２２の例では、多角形ｃをステップＳ２５−１６で選択した多角形とすると、ステップＳ２５−２８で設定される次の頂点「ｘ」は３Ｄ点Ｖ３となる。
【０２３５】処理はステップＳ２５−４４に進み、多角形生成器３１００は現頂点ポインタ「ｗ」を頂点「ｘ」に設定する。
【０２３６】ステップＳ２５−４６で、多角形生成器３１００は現在の頂点の署名を読み出し、ステップＳ２５−４８で、ステップＳ２５−４で選択した多角形「ｐ」でもステップＳ２５−１６で選択した多角形「ｑ」でもない、署名中に定義された多角形「ｒ」を選択する。図２２の例では、３Ｄ点Ｖ３の署名は｛ａ、ｃ、ｄ｝なので、ステップＳ２５−４８では多角形ｄを選択する。
【０２３７】処理はステップＳ２５−１８に戻り、現在の頂点を組Ｖｐから除去する。
【０２３８】こうして、多角形生成器３１００は多角形中の３Ｄ点について順次、各頂点に連結する頂点を判断し、処理された頂点を削除していく。ステップＳ２５−２４で組Ｖｐｑにもはや３Ｄ点が存在しておらず、多角形の全ての頂点は連結されたと判断した場合、多角形の処理を終了する。
【０２３９】ステップＳ２５−２６に戻り、組Ｖｐｑ中に２つ以上の３Ｄ点が存在すると判断した場合、図２３に示した例のように、いくつかの３Ｄ点１０００、１０１０、１０２０、及び１０３０が２つの多角形の交点が定義した線の中に存在するという状況が生じる。この場合、多角形生成器３１００は、現在検討中の３Ｄ点の相対位置と全ての３Ｄ点が直線に沿って並ぶ、組Ｖｐｑ中の３Ｄ点に基づいて、現在検討中の３Ｄ点に連結されるべき組Ｖｐｑ中の３Ｄ点を判断する。
【０２４０】特に、ステップＳ２５−３０で、多角形生成器３１００は組Ｖｐｑ中の３Ｄ点の数は奇数が偶数かを判断する。
【０２４１】定義では、２つの多角形の交点により定義される稜線上に存在する３Ｄ点の数は偶数でなければならない。これは３Ｄ点が、第１の３Ｄ点と第２の３Ｄ点、第３の３Ｄ点と第４の３Ｄ点といったように対で連結されなければならないためである。従って、図２３の例では、３Ｄ点１０００を３Ｄ点１０１０に、３Ｄ点１０２０を３Ｄ点１０３０に連結する。
【０２４２】しかし、現在の頂点「ｗ」の処理を終えたために、ステップＳ２５−１８で組Ｖｐから２つの多角形の交点によって定義された稜線上に存在する３Ｄ点の１つを除去したがために、ステップＳ２５−３０で検査した組Ｖｐ中の３Ｄ点の数が奇数になることもある。
【０２４３】これに対し、ステップＳ２５−１０で選択した開始頂点「ｕ」が３つ以上の頂点が存在する稜線上の頂点の１つからなり、次の処理された頂点が３つ以上の頂点を有する稜線上にある頂点ではない場合（すなわち、開始頂点が３つ以上の頂点を有する稜線上の端頂点の１つであり、多角形が３つ以上の頂点を有する稜線に沿って通過しない方向にわたっている場合）、ステップＳ２５−３０で検査した組Ｖｐｑの３Ｄ点の数は偶数となる。これは開始頂点がステップＳ２５−１８で組Ｖｐから除去されており、３つ以上の頂点を有する稜線上に存在する頂点でもある現在の頂点ｗもまたステップＳ２５−１８で組Ｖｐから除去されているからである。
【０２４４】従って、例えば図２３の例で、多角形９１０をステップＳ２５−４で選択した多角形とし、３Ｄ点１０００がステップＳ２５−１０で開始頂点「ｕ」として選択されたと仮定する。多角形１０４０がステップＳ２５−１６で選択された場合、ステップＳ２５−１８で３Ｄ点１０００が組Ｖｐから除去され、ステップＳ２５−２２及びＳ２５−２４で組Ｖｐｑが３つの３Ｄ点、すなわち点１０１０、１０２０、及び１０３０を含むと判断される。これに対し、多角形１０８０がステップＳ２５−１６で多角形１０４０の代わりに選択された場合、ステップＳ２５−１８で３Ｄ点１０００を組Ｖｐから除去し、ステップＳ２５−２８以降で３Ｄ点１０７０を処理する。以降の処理では、３Ｄ点１０１０、１０２０、及び１０３０の１つが現在の頂点「ｗ」となる。これらの点の最初のものが現在の頂点「ｗ」になれば、それはステップＳ２５−１８で組Ｖｐから除去され、ステップＳ２５−２４及びＳ２５−２６で検査した組Ｖｐｑ中には多角形９１０及び１０４０の交点に存在する２つの点（すなわち偶数個の点）が残る。
【０２４５】結果的に、ステップＳ２５−３０で組Ｖｐｑの点の数は奇数であると判断した場合、多角形生成器３１００は多角形「ｐ」及び「ｑ」の交点に存在する３Ｄ点の組「Ｖｌｉｎｅ」を、それが現在の頂点「ｗ」と組Ｖｐｑ中の３Ｄ点で構成されるように定義する。
【０２４６】これに対し、ステップＳ２５−３０で組Ｖｐｑ中の点の数が偶数であると判断した場合、多角形生成器３１００はステップＳ２５−３２で多角形ｐ及びｑの交点に存在する３Ｄ点の組「Ｖｌｉｎｅ」を、それが現在の頂点「ｗ」、開始頂点「ｕ」、及び組Ｖｐｑ中の３Ｄ点で構成されるように定義する。
【０２４７】ステップＳ２５−３２又はＳ２５−３４に続いて、処理はステップＳ２５−３６に進み、多角形生成器３１００は多角形「ｐ」及び「ｑ」の交点で定義された線に沿った相対位置に従って、組Ｖｌｉｎｅのそれぞれの３Ｄ点に０からｎ−１（ｎは組Ｖｌｉｎｅの点の数）のランクをつける。詳細には、交点上の端点の１つ（どれでも良い）をランク０とし、組Ｖｌｉｎｅの他の点を、ランク０の点から離れる方向にランク１、２、．．．とする。図２３に示す例では、３Ｄ点１０００をランク０、３Ｄ点１０１０をランク１、３Ｄ点１０２０をランク２、３Ｄ点１０３０をランク３とする。
【０２４８】ステップＳ２５−３８で、多角形生成器３１００は現在の頂点「ｗ」のランクが偶数であるか奇数であるかを判断する。
【０２４９】ステップＳ２５−３８で現在の頂点「ｗ」のランクが偶数であると判断した場合、ステップＳ２５−４０で多角形生成器３１００は多角形「ｓ］の次の頂点「ｘ」（すなわち、現在の頂点に連結する頂点）を組Ｖｐｑ中の頂点「ｖ」に、rank(v) = rank(w) + 1 … (1)を満たすように設定する。
【０２５０】これに対し、ステップＳ２５−３８で現在の頂点「ｗ」のランクが奇数であると判断した場合、ステップＳ２５−４２で多角形生成器３１００は多角形「ｓ］の次の頂点「ｘ」を組Ｖｐｑ中の頂点「ｖ」に、rank(v) = rank(w) - 1 … (2)を満たすように設定する。
【０２５１】そして、処理はステップＳ２５−４４に進む。
【０２５２】上述したように、ステップＳ２５−４４で多角形生成器３１００は現頂点ポインタ「ｗ」を頂点「ｘ」に設定し、ステップＳ２５−４６で新たな現在の頂点の署名を読み出す。
【０２５３】ステップＳ２５−４８で、多角形生成器３１００はステップＳ２５−４で選択した多角形「ｐ」でもステップＳ２５−１６で選択した多角形「ｑ」でもない、ステップＳ２５−４６で読み出した署名中に定義された多角形「ｒ」を選択する。
【０２５４】ステップＳ２５−４８の後、処理はステップＳ２５−１８に戻る。
【０２５５】再びステップＳ２５−６で、（ステップＳ２５−１８の処理の前回のサイクルで全ての３Ｄ点を除去したため）組Ｖｐ中に３Ｄ点がもはや存在しないと判断した場合、ステップＳ２５−４で選択した多角形「ｐ」上に存在する３Ｄ点の全てについて連結を判断されており、処理はステップＳ２５−５０に進む。
【０２５６】ステップＳ２５−５０で、多角形生成器３１００はデプスマップ多面体多角形「ｐ」中に２つ以上の被写体オブジェクト多角形が存在するか否かを判断する。特に本実施形態では、多角形生成器３１００は多角形「ｐ」に対して２つ以上の多角形データ構造「ｓ」を生成したか否かを判断する（新たな多角形データ構造「ｓ」はステップＳ２５−８で多角形「ｐ」中に存在する各多角形について生成される）。
【０２５７】ステップＳ２５−５０で、多角形「ｐ」中に２つ以上の多角形が存在すると判断した場合、処理はステップＳ２５−５２に進み、多角形生成器３１００は多角形「ｐ」中の各多角形を検査することで、それが多角形「ｐ」中に存在する他の多角形のいずれかを含むか否かを判断する。
【０２５８】ステップＳ２５−５４で、多角形生成器３１００は多角形「ｐ」中の各多角形が被写体オブジェクト３３００の面の一部を表すか、あるいはその中の穴を表すかを判断する。特に、ある多角形が他のどの多角形にも含まれない場合、それは被写体オブジェクト３３００の面を表す。１つの、すなわち、唯一の多角形が他の多角形の内側に存在する場合には、大きい方の多角形が被写体オブジェクト３３００の面を表し、大きな多角形に含まれる小さい多角形が面の穴を表す。ある多角形中に２つ以上の多角形が含まれている場合、多角形生成器３１００は各親多角形が子多角形を含むように階層を作成する。次に多角形生成器３１００は階層中の奇数番目の層の各多角形を被写体オブジェクト３３００の面として識別し、偶数番目の層の多角形を穴として識別する。
【０２５９】これに対し、ステップＳ２５−５０で多角形「ｐ」中に多角形が１つしかないと判断した場合、ステップＳ２５−５２及びＳ２５−５４は省略される。
【０２６０】ステップＳ２５−５６で、多角形生成器３１００はステップＳ２５−２で識別した多角形の中で他に処理すべきものが残っているか否かと判断する。
【０２６１】ステップＳ２５−５６で処理すべき他の多角形が残っていると判断した場合、処理はステップＳ２５−４に戻る。
【０２６２】上記の方法で各多角形を処理するまで、ステップＳ２５−４からＳ２５−５６を繰り返す。
【０２６３】この処理の結果として、多角形生成器３１００は被写体オブジェクト３３００の面を表す多角形メッシュを計算する。
【０２６４】図１９に戻って、ステップＳ１９−８で多角形生成器３１００はステップＳ１９−６で生成された多角形中の３Ｄ点を連結することで連結された平面三角形のメッシュを生成する。本実施形態では、多角形生成器３１００はステップＳ１９−８の処理を例えばOpen GL Programming Guide 2nd edition (ISBN 0-201-46138-2) １１章に記載されたように、Open GL Utility library “glutess”からの従来の方法を用いて行う。
【０２６５】本実施形態では、ステップＳ１９−８で３Ｄ点を連結する際、多角形生成器３１００は３Ｄ空間において同じ位置を有する点（すなわち、ステップＳ８−１２で生成された仮想頂点）を連結しても良い。
【０２６６】図２に戻って、ステップＳ２−１６で多角形生成器３１００は、多角形メッシュ中のゼロ長さ稜線を削除する処理を行う。この処理は例えばHoppeなどの“Mesh Optimization”(ACM SIGGRAPH 93、Addison-Wesley社刊、ISBN 0-201-58889-7）に記載されるような従来の方法で行われる。
【０２６７】ステップＳ２−１８で、サーフェステクスチャラ３１１０は入力デプスマップの画像データを処理して、ステップＳ１９−８で多角形生成器３１００が生成した面モデルの各面三角形のテクスチャデータを生成する。
【０２６８】具体的には、本実施形態では、サーフェステクスチャラ３１１０は従来の方法で処理を行い、ステップＳ１９−８で生成された面メッシュの各三角形を選択し、選択した三角形の正面に最も近い入力デプスマップ「i」を見つける。つまり、
値が最大の入力画像が見出される。ここで、
は、各三角形法線であり、
は、ｉ番目のデプスマップのビューイング方向である。これにより選択した面三角形が最大の投影領域を有する入力デプスマップを識別する。
【０２６９】次に選択した面三角形を識別した入力デプスマップに投影し、投影された三角形の頂点をデプスマップの画像データのテクスチャ座標として用いることで画像テクスチャマップを定義する。
【０２７０】ステップＳ２−１８でテクスチャデータを生成するのにサーフェステクスチャラ３１１０が用いうる他の技術は同時係属出願の英国特許第００２６３３１．９号、第００２６３４３．４号、第００２６３４７．５号に記述されており、その内容はここに参照として含む。
【０２７１】上述した処理を行った結果が被写体オブジェクト３３００の面のＶＲＭＬ（あるいは同様の形式）のモデルであり、これはモデルにレンダリングされるべき画像データを定義するテクスチャ座標を備えている。
【０２７２】ステップＳ２−２０で、中央制御装置３０２０は出力データ記憶装置３１３０から多角形生成器３１００が生成した被写体オブジェクト３３００の面モデルを定義するデータ（さらに、サーフェステクスチャラ３１１０が生成した面モデルのテクスチャデータ）を出力する。このデータは例えばディスク３１４０などの記憶装置に記憶されたデータあるいは信号３１５０として出力される。代わりに、中央制御装置３０２０はディスプレイプロセッサ３１２０をしてテクスチャデータでレンダリングされた被写体オブジェクト３３００の３Ｄコンピュータモデルの画像を、ユーザが例えばユーザ入力装置３００６を使って入力した視点に従って、表示装置３００４に表示する。
【０２７３】第２実施形態本発明の第２実施形態を以下に説明する。
【０２７４】第２実施形態の構成要素及びそれらによってなされる処理動作は第１実施形態と同様だが、被写体オブジェクト３３００の頂点を表す３Ｄ点を計算し連結するために、図２ｂのステップＳ２−１２で３Ｄ点計算器３０９０によって行われる処理動作とステップＳ２−１４で多角形生成器３１００によって行われる処理動作が異なる。
【０２７５】詳しくは、第２実施形態では、図１３乃至１８を参照して説明した処理を行う代わりに、３Ｄ点計算器３０９０は最初の２つの（ステップＳ２−１０で多面体生成器３０７０によって生成された）デプスマップ多面体と形成する多角形の交点を計算し、多角形生成器３１００は例えばSzilvasi-Nagyの“An Algorithm for Determining the Intersection of Two Simple Polyhedra” (Computer Graphics Forum 3 (1984)、291〜225ページ）、或いは、Martin Lohleinの“A Volumetric Intersection Algorithm for 3D-Reconstruction Using a Boundary-Representation”(http://i31www.ira.uka.de/diplomarbeiten/da_martin_loehlein/Reconstruction.html)に記載されたような従来の方法を用いて、得られた点を連結する。これにより、多角形メッシュを有する被写体オブジェクトの最初の画像が生成される。最初の画像を形成する多角形と次のデプスマップ多面体の交点を３Ｄ点計算器３０９０によって計算し、被写体オブジェクトの第２の多角形メッシュ画像を生成する。この処理もまた、Szilvasi-Nagy又はMartin Lohleinの上記の参考文献に記述した従来の方法で行われる。デプスマップ多面体が全て交差するまでデプスマップ多面体を有する多角形メッシュ画像を交差させる処理を繰り返し、被写体オブジェクト３３００の最終的な多角形メッシュ画像を得る。
【０２７６】第１実施形態で３Ｄ点計算器３０９０によって行われる処理よりも計算上高いコストがかかるものの、第２実施形態で行われる処理は被写体オブジェクト３３００の頂点を表す３Ｄ点を正確に計算するうえでさらに効果的である。
【０２７７】第３実施形態本発明の第３実施形態を説明する。
【０２７８】第３実施形態の構成要素及びそれらによってなされる処理動作は第１実施形態と同様だが、被写体オブジェクト３３００の頂点を表す３Ｄ点を計算するために、図２のステップＳ２−１２で３Ｄ点計算器３０９０によって行われる処理動作が異なる。
【０２７９】詳しくは、第１実施形態では、ステップＳ１３−２で被写体オブジェクト３３００の面上の計算されるべき点を全て含むように定義された初期ボリュームをより小さなボリュームに再分割することを、各ボリュームがオブジェクト３３００の面上の３Ｄ点を所定数だけ含むことができるように十分に小さなボリュームを生成するまで繰り返す。再分割プロセスによって小さなボリュームを生成すると、３Ｄ点を計算し検査する。
【０２８０】しかし、これはオブジェクトの面上の点を表す点を計算するのに特に効率的な方法であるが、他の方法も可能である。
【０２８１】従って、第３実施形態では、多面体を形成する平面多角形の位置を参照することなく、計算した３Ｄ点を全て含む初期ボリュームを複数の部分に分割し、これらの部分を再分割することなく３Ｄ点計算を行う。
【０２８２】具体的には、ステップＳ１３−２で定義されたボリュームを複数の部分（例えば同じ形状とボリューム）に分割し、各部分を多面体に対して検査することで、ステップＳ２−１０で生成された多面体の少なくとも１つの多角形の完全に外側に位置するか否かを判断する。
【０２８３】ボリューム部分が少なくとも１つの多面体の外側にある場合、そのボリューム部分は破棄される。これに対し、ボリュームが少なくとも部分的に全ての多面体の内側にある場合、多面体の平面多角形が交差するボリューム部分の３Ｄ点を計算する。このようにして、各ボリューム部分を破棄、又は３Ｄ点を計算するが、更なる再分割は生じない。
【０２８４】ボリューム部分の３Ｄ点を計算するには、３つの平面多角形の各組み合わせを検討し、これらの多角形の交点を計算し検査することで、それがボリューム部分の内側にあるか否かを判断する。上述した第１実施形態に比べ、計算し検査すべき交点の数は増加するが、３Ｄコンピュータモデルを生成するにはより効率的な方法である。というのは、ボリューム部分が全ての多面体の外側に存在すればそれを破棄することができ。従って、多面体を形成する平面多角形の全てのありうる交点を計算し検査する必要なないからである。
【０２８５】第４実施形態本発明の第４実施形態を説明する。
【０２８６】第４実施形態の構成要素及びそれらによってなされる処理動作は第１実施形態と同様だが、被写体オブジェクト３３００の頂点を表す３Ｄ点を計算し連結するために、図２のステップＳ２−１２で３Ｄ点計算器３０９０によって行われる処理動作とステップＳ２−１４で多角形生成器３１００によって行われる処理動作が第４実施形態では異なる。
【０２８７】この相違点を説明する。
【０２８８】図２６は、第４実施形態でステップＳ２−１２で３Ｄ点計算器３０９０によって行われる処理動作を示す。
【０２８９】図２６において、ステップＳ２６−２で３Ｄ点計算器３０９０はステップＳ２−１０で生成した全ての多面体からの平面を全て検討し、３つの平面の次の組を検討する（ステップＳ２６−２が始めて実行される場合は最初の組となる）。
【０２９０】ステップＳ２６−４で、３Ｄ点計算器３０９０はステップＳ２６−２で検討した３つの平面の交点の点を計算する。より詳細には、本実施形態では従来の平面交点アルゴリズムを用いてそれぞれが３つの平面を含む３つの平面が接する点を計算することで交点の点を計算する。
【０２９１】ステップＳ２６−６で、３Ｄ点計算器３０９０はステップＳ２６−４で計算した交点の点がステップＳ２−１０で生成した全ての多面体の内側に存在するか否かを判断する。
【０２９２】ステップＳ２６−６で、点が少なくとも１つの多面体の外側にあると判断した場合、その点は被写体オブジェクト３３００の面上の点を表すことはできないので、ステップＳ２６−８でその点を破棄する。
【０２９３】これに対し、ステップＳ２６−６で点が全ての多面体の内側にあると判断した場合、ステップＳ２６−１０で３Ｄ点計算器３０９０はその点がステップＳ２６−２で検討した３つの平面の全ての内側に存在するか否かを判断する（尚、この点は平面自体の交点の点を計算するのではなく、面を含む平面の交点の点を計算することで計算されたので、これらの平面の１つ以上の外側に位置する可能性がある）。
【０２９４】ステップＳ２６−１０で点が少なくとも１つの平面の外側にあると判断した場合、その点は被写体オブジェクト３３００の面上の点を表すことはできないので、ステップＳ２６−８でその点を破棄する。
【０２９５】これに対し、ステップＳ２６−１０でその点が３つの平面全ての内側にあると判断した場合、ステップＳ２６−１２で被写体オブジェクト３３００の面上の１点としてその点を保持する。さらに、その点で接する平面の３つのＩＤで構成される３つの「署名」を割り当てる。
【０２９６】ステップＳ２６−１４で、３Ｄ点計算器３０９０は３つの平面の他の組があるか否かを判断する。上記の方法で３つの平面のそれぞれの組が処理されるまでステップＳ２６−２からＳ２６−１４を繰り返す。
【０２９７】この処理を行った結果、３Ｄ点計算器３０９０はステップＳ２−１０で生成した多面体からの３つの平面の可能な組み合わせについて交点の点を計算し検査することで、被写体オブジェクト３３００の面上の点を表す３Ｄ空間の点で構成される被写体オブジェクト３３００の３Ｄコンピュータモデルを生成する。
【０２９８】ステップＳ２−１４で、多角形生成器３１００はステップＳ２６−１２で保持した３Ｄ点を、どの点を連結すべきかを判断するために割り当てられた署名を用いて連結することで、被写体オブジェクト３３００の面を表す多角形メッシュを生成する。これにより、ステップＳ２−１０で生成した多面体全ての交点から生じた３Ｄ点を計算し検査した後で３Ｄ点を連結して多角形メッシュを生成する処理を行う。
【０２９９】第４実施形態で、ステップＳ２−１４で多角形生成器３１００が行う処理は第１実施形態のものと同じだが、第４実施形態では図１９に示すステップＳ１９−２を図２６のステップＳ２６−１２で代わりに行う。
【０３００】上記の実施形態は特許請求の範囲内でさまざまに変形できる。
【０３０１】例えば、上述した実施形態では、入力データはカメラ固有のパラメータを定義する。しかし、そうではなく、いくつかあるいは全てのカメラパラメータにデフォルト値を割り与えて良い、あるいは例えば、Hartleyの“Euclidean Reconstruction From Uncalibrated Views” (Application of Invariance in Computer Vision、Mundy、Zisserman、及びForsyth編、237〜256ページ、Azores1993)に記載された従来の方法によって、処理装置３００２が固有のパラメータ値を計算する処理を行っても良い。
【０３０２】上記の第１実施形態では、入力データは各デプスマップの各画素についてその画素が被写体オブジェクトあるいは他のもの（背景）を表すのかを定義し、処理装置３００２ではこの「分割（segmentation）」処理を行うための処理を行った。しかし、各画素が表すものが被写体オブジェクトか背景かを定義するためのこうした画像データの分割は、第１の実施形態では残りの処理を首尾よく動作させるために必要なものではない。これは被写体オブジェクトとは物理的に分離した背景はデプスマップから生成した多面体が交差するときに除去されるためである。
【０３０３】上述の実施形態では、ステップＳ８−１２で生成された仮想頂点は全て同じ３Ｄ位置を有している。そうではなく、仮想頂点をその３Ｄ位置にわずかな差を有して定義しても良い。こうして、第１実施形態では、ステップＳ１４−３６及びＳ１４−４０の処理をボリュームの状態を「再分割(subdivide)」に設定する処理ステップに代えることができ、ステップＳ１３−１４及びＳ１３−１６の処理を行う必要がない。しかしながら、第１実施形態のこの変形の不利な点は単一の仮想頂点を含むのに十分なほど小さいボリュームを得るためには３Ｄボリュームを何度も再分割する必要があることだ。
【０３０４】第１実施形態で、ステップＳ１３−４及びＳ１３−２２でスタックから取り出した３Ｄボリュームを再分割する際、行われる再分割は新たな８つの子ボリュームを生成するボリュームの２値再分割を有する。しかしながら、異なるタイプの再分割ももちろん可能である。
【０３０５】上述の実施形態では、コンピュータがプログラミング命令によって定義された処理ルーティンを用いて処理を行う。しかし、処理の１部あるいは全てをハードウェアを用いて行うことも可能である。
【出願人】 【識別番号】０００００１００７
【氏名又は名称】キヤノン株式会社
【出願日】 平成１４年６月１１日（２００２．６．１１）
【代理人】 【識別番号】１０００７６４２８
【弁理士】
【氏名又は名称】大塚 康徳 （外３名）
【公開番号】 特開２００３−８５５８４（Ｐ２００３−８５５８４Ａ）
【公開日】 平成１５年３月２０日（２００３．３．２０）
【出願番号】 特願２００２−１６９５８５（Ｐ２００２−１６９５８５）