(57)【特許請求の範囲】
【請求項１】
現実世界環境の３Ｄモデルを生成するためにコンピューターによって実行される方法であって、
前記モデルを格納するためのメモリー・デバイスに三次元立体空間を作成するステップであって、前記立体空間は複数のボクセルを含む、ステップと、
キャプチャー・デバイスの位置および向きを記述するデーターと、前記キャプチャー・デバイスから出力された前記環境の少なくとも一部の深度画像とを受け取るステップであって、前記深度画像は複数の画素を含み、各画素は、前記キャプチャー・デバイスから前記環境内における１つの点までの距離を示す、ステップと、
前記立体空間の平面内にある各ボクセルに、別個の実行スレッドを割り当てるステップと、
各実行スレッドが、前記キャプチャー・デバイスの位置および向きを用いて、当該実行スレッドに関連付けられたボクセルに対する前記深度画像内の対応位置を判定し、前記関連付けられたボクセルと前記環境内の前記対応位置における点との間の距離に関係する係数を決定し、前記係数を用いて前記関連付けられたボクセルに格納されている値を更新するステップと、
各実行スレッドが、前記立体空間の残りの平面の各々における同様のボクセルのそれぞれについて、前記係数を決定するステップと、格納されている値を更新するステップを繰り返すステップと、
を含み、
前記係数を決定するステップは、前記関連付けられたボクセルが前記点の第１側に位置する場合、前記係数が正の値を有し、前記関連付けられたボクセルが前記点の反対側に位置する場合、前記係数が負の値を有するように、前記関連付けられたボクセルと、前記環境内の前記対応する位置における前記点との間における符合付き距離を計算するステップを含む、
方法。
【請求項２】
請求項１記載の方法であって、更に、前記係数を判定するステップの前に、前記対応位置が前記キャプチャー・デバイスの視野の内部にあるか否か判定するステップを含む、方法。
【請求項３】
請求項１記載の方法において、前記キャプチャー・デバイスの位置および向きを用いて、前記深度画像においてそれに関連付けられたボクセルに対する対応位置を判定するステップは、
現実世界座標において前記ボクセルの位置を判定するステップと、
前記深度画像において前記関連付けられたボクセルに対する対応座標を決定するために、前記位置および向きを用いて、前記キャプチャー・デバイスの投影によって前記現実世界座標を投影するステップと、
を含む、方法。
【請求項４】
請求項１記載の方法であって、更に、レイキャスティングを用いて、ディスプレイ・デバイス上における表示のために前記モデルの画像を生成するステップを含み、前記モデルの画像を生成する前記ステップは、
仮想カメラについての姿勢データーを受け取るステップと、
実行スレッドを各画像画素に割り当てるステップと、
各画像画素実行スレッドが、前記仮想カメラから発して前記関連付けられた画素を通る経路を決定し、前記経路を前記立体空間における座標に変換し、表面においてボクセルが検出されるまで前記経路に沿って前記立体空間内を動き、当該ボクセルに格納されている値を用いて、前記関連付けられたボクセルに対して陰影を計算するステップと、
を含む、方法。
【請求項５】
請求項１記載の方法であって、更に、前記モデルからポリゴン・メッシュを生成し、前記ポリゴン・メッシュを記憶デバイスに格納するステップを含み、前記モデルからポリゴン・メッシュを生成する前記ステップは、前記モデルの一部を表すポリゴンを選択するために、マーチング・キューブ・アルゴリズムを用いるステップを含む、方法。
【請求項６】
請求項１記載の方法において、前記係数を用いて前記関連付けられたボクセルに格納されている前記値を更新する前記ステップは、前記係数と、前記関連付けられたボクセルに格納されている以前の値とを合算するステップを含む、方法。
【請求項７】
請求項６記載の方法において、更に、前記格納されている値と、前記関連付けられたボクセルの前記キャプチャー・デバイスからの距離に関係する重み付け関数とを用いて、加重平均を決定するステップを含む、方法。
【請求項８】
請求項１記載の方法において、前記係数を決定するステップは、更に、
前記係数が既定の正の閾値よりも大きいか否か判定を行い、大きい場合、前記係数を前記正の閾値に切り上げるステップと、
前記係数が既定の負の閾値よりも小さいか否か判定を行い、小さい場合、前記係数を前記負の第２閾値に切り下げるステップと、
を含む、方法。
【請求項９】
現実世界環境の３Ｄモデルを生成するグラフィクス処理システムであって、
キャプチャー・デバイスの位置および向きを記述するデーターと、前記キャプチャー・デバイスからの出力された前記環境の少なくとも一部の深度画像とを受け取るように構成されている通信インターフェースであって、前記深度画像は複数の画素を含み、各画素は、前記キャプチャー・デバイスから前記環境における１つの点までの距離を示す、通信インターフェースと、
複数のスレッドの同時実行を提供するように構成されているグラフィクス処理ユニットと、
メモリー・デバイスと、
を備え、
前記グラフィクス処理ユニットは、前記モデルを格納するための前記メモリー・デバイスに三次元立体空間を作成し、前記立体空間は複数のボクセルを含み、前記立体空間の平面内にある各ボクセルに、別個の実行スレッドを割り当て、実行スレッド毎に、前記キャプチャー・デバイスの位置および向きを用いて、当該実行スレッドに関連付けられたボクセルに対する前記深度画像内の対応位置を判定し、前記関連付けられたボクセルと前記環境内の前記対応位置における点との間の距離に関係する係数を決定し、前記係数を用いて前記関連付けられたボクセルに格納されている値を更新し、前記立体空間の残りの平面の各々における同様のボクセルのそれぞれについて、前記係数の決定および格納されている値の更新を繰り返すように構成され、
前記グラフィクス処理ユニットは更に、前記関連付けられたボクセルが前記点の第１側に位置する場合、前記係数が正の値を有し、前記関連付けられたボクセルが前記点の反対側に位置する場合、前記係数が負の値を有するように、前記関連付けられたボクセルと、前記環境内の前記対応する位置における前記点との間における符合付き距離を計算することによって、前記係数を決定するように構成されている、グラフィクス処理システム。
【請求項１０】
請求項９記載のグラフィクス処理システムにおいて、前記グラフィクス処理ユニットは、前記係数と、前記関連付けられたボクセルに格納されている以前の値とを合算することによって、前記値を更新するように構成されている、グラフィクス処理システム。
【請求項１１】
請求項９記載のシステムにおいて、前記キャプチャー・デバイスが、あるフレーム・レートで複数の深度画像を供給するビデオ・カメラであり、前記グラフィクス処理ユニットが、更に、前記フレーム・レートで、前記立体空間内にある各ボクセルの前記格納値を繰り返し更新するように構成されている、システム。
【請求項１２】
請求項９記載のシステムにおいて、前記キャプチャー・デバイスが、構造化光発光器、飛行時間カメラ、およびステレオ・カメラの内少なくとも１つを備えている、システム。
【発明の詳細な説明】
【背景技術】
【０００１】
[0001]  現実世界環境の三次元コンピューター・モデルは、広範囲の多様な用途において有用である。例えば、このようなモデルは、没入型ゲーミング、拡張現実、建築／計画ロボット、および設計原型作成というような用途において用いることができる。
【０００２】
[0002]  深度カメラ（ｚ−カメラとしても知られている）は、現実世界環境のリアル・タイム深度マップを生成することができる。これらの深度マップにおける各画素は、環境における３Ｄ点からカメラによって取り込まれた離散距離測定値に対応する。これが意味するのは、これらのカメラは、１組の順序付けられていない点（点クラウドとしても知られている）によって構成される深度マップを、リアル・タイムのレートで供給するということである。
【発明の概要】
【０００３】
[0003]  しかしながら、深度カメラによって供給される深度マップを用いて、環境の有用な３Ｄモデルを生成するのは、複雑である。多くの深度カメラを用いると、個々の深度マップは各々解像度が低すぎ、更にノイズが多すぎて、十分に精度が高く詳細な３Ｄモデルを生成することができない。更に、多くの用途では、点クラウドではなく、検知した環境の表面再現(surface reconstruction)を利用する。例えば、３Ｄ再現表面モデルは、物理シミュレーションにおいて、仮想物体と、環境において深度カメラによって取り込まれた実物体との間における物理的相互作用の効果をモデリングするために用いることができる。点クラウドは、点クラウドにおける個々の点間に接続がないため、モデル全体にわたって孔(hole)があるので、このシナリオではしかるべく作用しない。
【０００４】
[0004]  深度カメラからの点クラウドの多数のフレームを組み合わせて、コヒーレントで使用可能なモデルを作り、これらの点クラウドにおける点間の接続を判断することによって表面外形を推論するのは、非常に計算集約的である。表面再現は、この接続を推論することによって、カメラに見ることができる表面を抽出するプロセスである。深度カメラからリアル・タイムで受け取るデーター量を仮定し、そして対話処理できる速度 (interactive rate)をサポートすることが望ましいとすると、ポアソン表面再現のような既知のアルゴリズムは、リアル・タイム処理をサポートするには計算集約的過ぎる。
【０００５】
[0005]  以下で説明する実施形態は、既知の３Ｄ再現技法の欠点のうちいずれかを解決する実施態様にも、その全てを解決する実施態様にも限定されない。
【０００６】
[0006]  以下に、基本的な理解を読み手に与えるために、本開示を簡略化した摘要を紹介する。この摘要は、本開示の広範な全体像ではなく、本発明の主要な／重要な要素を特定するのでも、本発明の範囲を明確に定めるのでもない。その唯一の目的は、本明細書において開示する概念から選択したものを、簡略化した形態で、後に紹介する更に詳細な説明に対する序説として提示することである。
【０００７】
[0007]  三次元環境の再現について記載する。一例では、現実世界環境の３Ｄモデルを、メモリー・デバイス上に格納されているボクセルで構成された３Ｄ立体空間に生成する。このモデルは、カメラの位置および向きを記述するデーター、ならびにカメラから環境における１点までの距離を示す画素を有する深度画像から構築する。立体空間の平面における各ボクセルに、別個の実行スレッドを割り当てる。各スレッドは、このカメラ位置および向きを用いて、それと関連付けられたボクセルについて対応する深度画像位置を判定し、関連付けられたボクセルと環境内の対応する位置における点との間の距離に関係する係数を決定し、この係数を用いて、関連付けられたボクセルにおいて格納されている値を更新する。各スレッドは、立体空間の残りの平面における同等のボクセル毎に反復し、格納されている値を更新するプロセスを繰り返す。
【０００８】
[0008]  付帯する特徴の多くは、以下の詳細な説明を参照し、添付図面と合わせて検討することによって一層深く理解されていくに連れて、一層容易に認められるようになるであろう。
【０００９】
[0009]  この記載は、添付図面を参照しながら以下の詳細な説明を読むことによって、一層深く理解できよう。
【００１０】
添付図面における同様の部分を示すために、同様の参照番号を用いる。
【図面の簡単な説明】
【００１１】
【図１】図１は、部屋の３Ｄモデルを生成するために用いることができる可動深度カメラを保持して、この部屋の中にいる人の模式図を示す。
【図２】図２は、可動深度カメラを保持している人によって調べられている建物のフロアの平面図を示す。
【図３】図３は、リアル・タイム・カメラ追跡システム、緻密３Ｄモデル形成システム、およびゲーム・システムに接続された可動深度カメラの模式図を示す。
【図４】図４は、３Ｄ環境モデルを生成する並列化可能なプロセスのフローチャートを示す。
【図５】図５は、線形間隔メモリー(linear pitched memory)で構成された３Ｄ立体空間を示す。
【図６】図６は、並列化可能な符合付き距離関数計算の一例を示す。
【図７】図７は、４Ｄ立体空間からレイキャスティング(raycasting)する並列化可能なプロセスのフローチャートを示す。
【図８】図８は、並列化可能な３Ｄモデリング技法の実施形態を実現することができる計算主体デバイス(computing-based device)の一例を示す。
【発明を実施するための形態】
【００１２】
[0010]  添付図面と合わせて以下に示す詳細な説明は、本例の説明であることを意図するのであって、本例を構成または利用することができる唯一の形態を表すことを意図するのではない。この説明では、本例の機能、および本例を構成し動作させるためのステップのシーケンスを明記する。しかしながら、同じまたは等価な機能およびシーケンスが、異なる例によって遂行されてもよい。
【００１３】
[0011]  本明細書では、コンピューター・ゲーミング・システムにおいて実現するものとして、本例について説明し図示するが、説明するシステムは、一例として示すのであって限定ではない。当業者には認められようが、本例は、３Ｄモデルを用いる種々の異なるタイプの計算システムにおける用途に適している。
【００１４】
[0012]  図１は、部屋の中で起立して可動深度カメラ１０２を保持している人１００の模式図である。この部屋には、椅子、扉、窓、植物、他の人１０４、および猫１０８というような種々の物体１０６が入っている。物体１０６の多くは静止しているが、人１０４および猫１０８のように、物体の一部は動くこともできる。人が部屋を動き回ると、可動深度カメラは部屋および物体の深度画像を取り込む。
【００１５】
[0013]  可動深度カメラ１０２は、緻密環境モデリング・システム１１０と通信する（この場合、環境とは部屋のことである）。この例における「緻密」とは、暗示的に表面を記述するための、入ってくる深度マップからの点の全てまたは多くの使用によって得られるモデルの精度および解像度が高度であることを指す。これは、計算を高速化しメモリー・フットプリントを削減するために点の部分集合のみを取り込む「疎」モデルとは対照をなすことができる。例えば、可動深度カメラ１０２によって取り込まれた画像は、人が部屋の中で動き回り、可動深度カメラ１０２をあちこち動かすに連れて、環境の緻密３Ｄモデルを形成し構築するために用いられる。
【００１６】
[0014]  リアル・タイム・カメラ追跡システム１１２は、部屋におけるカメラの位置および向きを監視する。リアル・タイム・カメラ追跡システム１１２は、可動深度カメラ１０２と一体化されてもよく、または可動深度カメラ１０２から直接または間接的に通信を受信することができるのであれば、他の場所にあってもよい。例えば、リアル・タイム・カメラ追跡システム１１２は、パーソナル・コンピューター、専用コンピューター・ゲーム装置、または部屋の中にあり可動深度カメラ１０２とワイヤレスで通信する他の計算デバイスに設けることもできる。他の例では、リアル・タイム・カメラ追跡システム１１２は、建物のどこにあってもよく、またはいずれかの適したタイプの通信ネットワークを用いて可動深度カメラ１０２と通信できる他の離れた場所にあってもよい。
【００１７】
[0015]  リアル・タイム・カメラ追跡システム１１２は、個々の深度画像を全体的な３Ｄモデル内に組み立てることを可能にするために、入力を緻密３Ｄモデリング・システムに供給する。また、リアル・タイム・カメラ追跡システム１１２は、環境の３Ｄモデルに対するカメラの位置を追跡することもできる。カメラ追跡および３Ｄモデリングの組み合わせは、同時定位およびマッピング（ＳＬＡＭ：simultaneous localization and mapping）として知られている。尚、他の例では、例えば、マッピングとは独立したカメラ測位技法を用いることによって、マッピングおよび定位を独立して（即ち、ＳＬＡＭシステムを用いずに）実行することもできることを注記しておく。
【００１８】
[0016]  リアル・タイム・カメラ追跡システム１１２および緻密３Ｄモデリング・システム１１０の出力は、ゲーム・システムまたは他のアプリケーションによって用いることができるが、これは必須ではない。例えば、モデリングした現実世界物体をゲーミング環境に含ませることができる。他の例では、現実世界カメラ追跡システム１１２および３Ｄモデリング・システム１１０の出力に応じて画像を投影するように、可動深度カメラ１０２におけるプロジェクタを構成することもできる。
【００１９】
[0017]  更に他の例として、図２は、建物のフロア２００の平面図を示す。可動深度カメラ２０４を保持している人２０２が、点線矢印で示すように、フロア上を動き回っている。この人は、部屋および家具２１０を通り過ぎて廊下２０６に沿って歩く。リアル・タイム・カメラ追跡システム１１２は、可動深度カメラ２０４が動くに連れて、その位置を追跡することができ、３Ｄモデリング・システムは、フロアの３Ｄモデルまたはマップを生成する。人２０２が可動深度カメラ２０４を携行することは必須ではない。他の例では、可動深度カメラ２０４は、ロボットまたは車両上に装着される。これも図１の例に該当する。
【００２０】
[0018]  図３は、リアル・タイム・カメラ追跡システム３１６、緻密モデル形成システム３２４、および任意にゲーム・システム３３２と共に使用するための可動環境キャプチャー・デバイス３００の模式図である。可動環境キャプチャー・デバイス３００は、場面の深度画像のシーケンス（または連続）を取り込むように構成されている深度カメラ３０２を備えている。各深度画像３１４（または深度マップ・フレーム）は、二次元画像を構成し、各画像エレメント（即ち、画素）は、カメラから取り込まれた場面において、その画像エレメントを生じさせたある物体までの長さ即ち距離というような深度値を含む。この深度値は、メートル、またはセンチメートルというような、指定された測定単位で与えられる絶対値であってもよく、または相対的な深度値でもよい。取り込まれた各深度画像３１４において、約３００，０００個以上の画像エレメントがあることもあり、その各々が深度値を有する。深度カメラ３０２のフレーム・レートは、作業ロボット(working robotics)、コンピューター・ゲーム、または他のアプリケーションに深度画像を用いることを可能にするのに十分な高さである。例えば、フレーム・レートは、毎秒２０から１００フレームの範囲にするとよい。
【００２１】
[0019]  深度情報は、適した技法であればそのいずれを用いてでも得ることができる。これらの技法には、飛行時間、構造化光、およびステレオ画像が含まれるが、これらに限定されるのではない。また、可動環境キャプチャー・デバイス３００は、深度情報を深度カメラ３０２によって確認できるように、場面を照らすように構成された発光器３０４も備えることができる。
【００２２】
[0020]  例えば、深度カメラ３０２が赤外線（ＩＲ）飛行時間カメラである場合、発光器３０４はＩＲ光を場面に発光し、深度カメラ３０２は、場面における１つ以上の物体の表面からの後方散乱光を検出するように構成される。例の中には、パルス状赤外線光を発光器３０４から発光し、出立光パルスと対応する到来光パルスとの間の時間を深度カメラによって検出し、これを測定して、環境キャプチャー・デバイス３００から場面における物体上の位置までの物理的距離を判定するために用いるとよい場合がある。加えて、例の中には、発光器３０４からの出立光波の位相を、深度カメラ３０２における到来光波の位相と比較して、位相ずれを判定するとよい場合もある。この位相ずれは、次に、例えば、散乱光パルス撮像(shuttered light pulse imaging)を含む種々の技法によって経時的に反射光ビームの強度を分析することによって、可動環境キャプチャー・デバイス３００から物体上の位置までの物理距離を判定するために用いることができる。
【００２３】
[0021]  他の例では、可動環境キャプチャー・デバイス３００は、構造化光を用いて深度情報を取り込むことができる。このような技法では、パターン化光（例えば、スポット、格子、または縞模様パターンのような既知のパターンとして表示される光。これらは時間可変であってもよい）を、発光器３０４を用いて場面上に投影することができる。場面における物体の表面に衝突すると、このパターンは変形する。このようなパターンの変形を分析して、深度カメラ３０２から場面における物体までの絶対距離または相対距離を判定する。
【００２４】
[0022]  他の例では、深度カメラ３０２は、１対のステレオ・カメラを備え、視覚的ステレオ・データーを入手し、解明して相対的深度情報を生成する。この場合、発光器３０４は、場面を照らすために用いることができ、あるいは省略してもよい。
【００２５】
[0023]  例の中には、深度カメラ３０２に加えて、可動環境キャプチャー・デバイス３００が、ＲＧＢカメラ３０６と呼ばれる、カラー・ビデオ・カメラを備えている場合もある。ＲＧＢカメラ３０６は、可視光周波数で場面の画像のシーケンスを取り込むように構成されている。
【００２６】
[0024]  可動環境キャプチャー・デバイス３００は、慣性測定ユニット（ＩＭＵ）のような方位センサー３０８、加速度計、ジャイロスコープ、コンパス、あるいは他の方位センサーまたは動きセンサー３０８を備えることができる。しかしながら、方位センサーを用いることは必須ではない。可動環境キャプチャー・デバイス３００は、ＧＰＳのような位置追跡デバイスを備えることもできるが、これも必須ではない。
【００２７】
[0025]  可動環境キャプチャー・デバイスは、前述のようなプロジェクタ３１２を備えることもできるが、これは必須ではない。また、可動環境キャプチャー・デバイスは、以下で更に詳細に説明するように、１つ以上のプロセッサー、メモリー、および通信インフラストラクチャも備えている。可動環境キャプチャー・デバイスは、ユーザーが手の中に収めるまたはユーザーが装着するような形状およびサイズに作られた筐体内に設けることもできる。他の例では、可動環境キャプチャー・デバイスは、車両、おもちゃ、または他の移動可能な装置に組み込むまたは装着するようなサイズおよび形状に作られる。
【００２８】
[0026]  可動環境キャプチャー・デバイス３００は、リアル・タイム追跡装置３１６に接続されている。この接続は、物理的な有線接続とするとよく、またはワイヤレス通信を用いてもよい。例の中には、インターネットのような１つ以上の通信ネットワークを通じて、可動環境キャプチャー・デバイス３００を間接的にリアル・タイム追跡装置３１６に接続する場合もある。
【００２９】
[0027]  リアル・タイム追跡装置３１６は、１つ以上のグラフィクス処理ユニット（ＧＰＵ）または他の並列計算ユニットを制御する汎用マイクロプロセッサーを用いて、コンピューターで実現する。これは、フレーム整列エンジン３１８と、任意に、ループ閉鎖エンジン３２０および再定位エンジン(relocalization engine)３２２とを備えている。リアル・タイム追跡装置３１６は、深度カメラ３０２からの深度画像フレームを取り込み、任意に可動環境キャプチャー・デバイス３００からの入力、および任意のマップ・データー３３４も取り込む。リアル・タイム追跡装置３１６は、深度カメラ３０２の一連のリアル・タイム６自由度（６ＤＯＦ）姿勢推定値を生成するために、深度画像フレームを空間的に整列するように動作する。また、１対の深度画像フレーム間における変換のための変換パラメーターも生成することができる。例の中には、リアル・タイム追跡装置が、深度カメラからの深度画像フレーム３１４に１対毎に動作する場合もある。他の例では、リアル・タイム追跡装置３１６は、１つの深度画像３１４を取り込み、それを、他の深度画像とではなく、環境の緻密３Ｄモデル３２６と整列する。
【００３０】
[0028]  リアル・タイム追跡装置３１６は、カメラ姿勢を出力として緻密３Ｄモデル生成システム３２４に供給する。緻密３Ｄモデル生成システム３２４は、この情報を、深度画像フレームと共に用いて、可動環境キャプチャー・デバイス３００が動いている場面即ち環境の緻密３Ｄモデル３２６を形成し格納する。例えば、図１の場合、３Ｄモデルは部屋における表面および物体の３Ｄモデルである。図２の場合、３Ｄモデルは、建物のフロアの３Ｄモデルである。以下で説明するように、緻密３Ｄモデルは、ＧＰＵメモリーに格納することができる。緻密３Ｄモデルは、リアル・タイムで組み立てることができ、または緻密３Ｄモデル生成システム３２４がカメラの姿勢についてのデーターおよび深度画像を収集し、後の時点において３Ｄモデルを組み立てることもできる。
【００３１】
[0029]  可動環境キャプチャー・デバイス３００は、ディスプレイ３３０に接続されているゲーム・システム３３２と共に用いることもできる。例えば、ゲームは、ＦＰＳゲーム、ゴルフ・ゲーム、ボクシング・ゲーム、自動車レース・ゲーム、またはその他のタイプのコンピューター・ゲームとすることができる。緻密３Ｄモデルは、ゲーム・システム３３２に供給することができ、モデルの側面をゲームに組み込むことができる。例えば、３Ｄモデルは、部屋の中にある物体の形状および向きを判定するために用いることができる。これらは、背景の除去を改善するために、カメラに基づくゲームと共に用いることができ、あるいはゲーム自体に組み込むことができる（例えば、プレーヤが対話処理することができるゲーム内物体）。ゲーム状態またはゲームについてのメタデーターというようなゲーム・システム３３２からのデーターは、リアル・タイム・カメラ追跡装置３１６に供給することもできる。
【００３２】
[0030]  ユーザーが緻密３Ｄモデルを構築するのを補助するために、緻密３Ｄモデルのリアル・タイム・レンダリングの形態で、ユーザーにフィードバックを提供することができる。これによって、ユーザーは緻密モデルの状態を、これが組み立てられていくに連れて見ることが可能になり、これによって、失われていた領域をユーザーが取り込むのを補助する。これによって、一層対話処理し易い環境をユーザーに提供する。緻密３Ｄモデルからの光景(view)をレンダリングする技法の一例について、以下で図７を参照して論ずる。また、失われているエリアまたは緻密３Ｄモデルの中では品質が劣るエリアにユーザーを導くために、聴覚または視覚的キューをユーザーに供給することもできる。
【００３３】
[0031]  マップ・データー３３４は、任意に、リアル・タイム・カメラ追跡装置３１６にも利用可能になる。例えば、これは、建築家の環境の図面（例えば、建物の部屋またはフロア）、環境内において知られている陸標、他のソースから入手可能な建物のマップとすることもできる。
【００３４】
[0032]  リアル・タイム追跡装置のフレーム整列エンジン３１８は、深度画像フレームの対を整列するように、または深度画像フレームと緻密３Ｄモデルからの深度画像フレームの推定値とを整列するように構成されている。これは、フレーム整列エンジンがリアル・タイムで動作するために、１つ以上のグラフィクス処理ユニットを用いて実現される反復プロセスを用いる。ループ閉鎖エンジン３２０は、可動環境キャプチャー・デバイスが移動してループ内に入って、現在の深度フレーム内において描かれている場面が、モデルに既に統合されている以前の深度フレームのそれと少なくとも部分的に重なり合っているときを検出するように構成されている。例えば、これは、ユーザーが図２の建物のフロア全体を歩き回り、再度出発地点に達したときに起こると考えられる。また、ユーザーがある家具の背後で部屋内を動き回り、元の出発地点に再度戻ったとき、またはその元の出発地点の近くに戻ったときにも起こると考えられる。再定位エンジン３２２は、リアル・タイム追跡装置が可動環境キャプチャー・デバイス３００の現在の位置を失い、再度現在の位置を再定位または発見するという状況に対処するように構成されている。
【００３５】
[0033]  前述のように、リアル・タイム追跡装置３１６および／または緻密３Ｄモデル生成システム３２４によって実行する処理は、一例では、可動環境キャプチャー・デバイス３００の位置から離れて実行することができる。例えば、可動環境キャプチャー・デバイス３００を、比較的処理パワーが低い計算デバイスに接続すること（またはこれを備えること）ができ、深度画像をサーバーに通信ネットワークを通じてストリーミングする。サーバーは、比較的高い処理パワーを有し、リアル・タイム追跡装置３１６および／または緻密３Ｄモデル生成システム３２４の計算的に複雑なタスクを実行する。サーバーは、レンダリングした緻密再現画像をフレーム毎に戻して、ユーザーに対話処理体験を提供し、更にモデルの完成時における最終的な３Ｄ再現を、今後のローカルな使用（例えば、ゲームにおいて）のために戻すこともできる。このような構成は、ユーザーが高パワーのローカル計算デバイスを所有する必要性を回避する。
【００３６】
[0034]  更に他の例では、ローカルおよびリモート計算デバイス間で、処理を分割することができる。例えば、高解像度緻密３Ｄモデルを組み立てるために、通信ネットワークを通じて深度画像を送信することができ、前述のように、この高解像度緻密３Ｄモデルが完成したときに戻す。これと同時に、少ない処理パワーおよびメモリーを用いて、このモデルの低解像度版をローカルに組み立てる。これらは、ユーザーが見るために、モデルのリアル・タイムの光景をレンダリングするために用いられる。これによって、ユーザーはローカル・プロセッサーからのモデル組み立てから視覚的フィードバックを得ることができ、ネットワーク・レイテンシーの問題を回避することができる。
【００３７】
[0035]  これより図４を参照すると、図４は、３Ｄ環境モデルを生成する平行化可能なプロセスのフローチャートを示す。一例では、図４のプロセスは、ＧＰＵプロセッサー、マルチコア・プロセッサー、または高度な実行並列性を可能にする他のタイプのプロセッサー上で実行する。他の例では、単一コア・プロセッサーが十分に速いのであれば、これを用いることもできる。最初に、モデルを格納するためのメモリー・デバイス上に、３Ｄ立体空間(volume)を作成する（４００）。一例では、この３Ｄ立体空間は、グラフィクス処理システムのメモリー上に作成する。このグラフィクス処理システムは、ＧＰＵからの高速並列アクセスを可能にする。
【００３８】
[0036]  ３Ｄ立体空間は、メモリーの直方体として可視化することができ、各メモリー位置は、モデル化する環境の空間内における一点を表すボクセルとなる。したがって、３Ｄ立体空間は現実世界環境の空間部分を直接表す。３Ｄ立体空間は現実世界立体空間に直接対応するので、固定サイズのメモリーにおいて表される現実世界立体空間のサイズが、モデルの解像度を決定する。例えば、大きな現実世界立体空間をモデル化しようとする場合、メモリーの各ボクセルは、それよりも小さな現実世界立体空間をモデル化する場合よりも、現実世界空間において大きな領域を表し、したがって、解像度は低くなる。しかしながら、利用可能なメモリーが多い程、大きな現実世界立体空間をもっと高い解像度でモデル化することができる。また、メモリーのフットプリントを縮小し空間解像度を高めるために、効率的なデーター格納の計画的実施(strategies)および／または圧縮アルゴリズムも用いることができる。
【００３９】
[0037]  図５は、ＧＰＵメモリー内においてどのように３Ｄ立体空間を組み立てることができるかを示す一例である。図５は、４×４×４の３Ｄ立体空間例５００を示す。これは単なる代表例に過ぎず、実際の３Ｄ立体空間はこれよりも大きくてもまたは小さくても可能である。この３Ｄ空間はｘ−軸５０２、ｙ−軸５０４、およびｚ−軸５０６を有する。ｘ−軸５０２に沿ったボクセルの数がこの立体空間の幅５０８（この例では４つ）を定め、ｙ−軸５０４に沿ったボクセルの数がこの立体空間の高さ５１０（この例では、これも４つ）を定める。次いで、ｘ、ｙ、ｚ−座標を用いて、個々のボクセルを特定することができる。例えば、ボクセル５１２は、座標（０，３，２）を有する。３Ｄ立体空間とこれが表す現実世界の立体空間との間の関係は分かっているので、３Ｄ立体空間におけるボクセルは、３Ｄ立体空間の座標と現実世界の座標との間で、その位置を変換することができる。
【００４０】
[0038]  しかしながら、モデルを格納するために用いられる物理的なメモリー・デバイスは、一般に、図５に示すような、直方体として配列されていない。代わりに、メモリー・デバイスは、一般に、メモリー・アレイ５１４のように、メモリー位置の線形アレイを構成する。メモリー・アレイ上に３Ｄ立体空間を作成するために、x+(y×幅）+(z×幅×高さ)にしたがって、メモリー・アレイ・インデックスに各ボクセルをマッピングする。例えば、座標（０，３，２）を有するボクセル５１２では、これは、図５に示すように、４４のインデックスに変換する。この配列を線形間隔メモリー(linear pitched memory)と呼び、以下で説明するように、ＧＰＵメモリー上に格納されているデーターに対して、高速で並列なアクセスを可能にする手段となる。また、メモリー上に格納されているデーターは、例えば、データーを膨らして(pad out)これらの境界と揃えることによって、そのデーターの格納アドレスが２乗の歩幅(stride)で離間されるように、位置合わせすることもできる。これによって、包括的な乗算の使用を伴わずに、データーに対して処理を実行することが可能になることにより、計算速度を更に高めることができる。
【００４１】
[0039]  尚、代替例では、先に説明したような３Ｄ立体空間とは異なるやり方でモデルを格納できることを注記しておく。例えば、オクトツリーのようなデーター構造を用いると、更にメモリー消費を低減し、計算を高速化することができる。あるいは、３Ｄ空間とそれよりも低い次元の表現との間における伝達関数を適用すると、格納効率を高めることができる。このタイプの伝達関数の一例に「幾何学的画像」(geometry images)と呼ばれるものがある。
【００４２】
[0040]  再度図４に戻ると、一旦３Ｄ立体空間をメモリーにおいて作成したなら（４００）、モデリング・プロセスを開始して、可動環境キャプチャー・デバイス３００からインド画像４１４を受け取り、その深度画像を取り込むときの深度カメラ３０２の６ＤＯＦ姿勢推定値を受け取る（４０２）。６ＤＯＦ姿勢推定値は、深度カメラ３０２の位置および向きを示し、リアル・タイム追跡装置３１６によって供給することができる。一例では、６ＤＯＦ姿勢推定値は、現実世界座標に対する深度カメラ３０２の回転および並進を記述するＳＥ３マトリクスの形態とすることができる。更に形式的には、この変換マトリクスは、次のように表すことができる。
【００４３】
【数１】
0005906258.tif 000002
【００４４】
[0041]  ここで、Ｔｋは深度画像フレームｋに対する変換マトリクスであり、Ｒｋはフレームｋに対するカメラの回転であり、ｔｋはフレームｋにおけるカメラの並進であり、ユークリッド集合ＳＥ３は、次のようになる。
【００４５】
【数２】
0005906258.tif 000003
【００４６】
この変換マトリクスを乗算することによって、カメラ空間における座標（即ち、カメラ視線からの）を現実世界座標にマッピングすることができ、更に逆変換を適用することによってその逆も行うことができる。
【００４７】
[0042]  ３Ｄ立体空間の平面における各ボクセルに、別個の実行スレッドを割り当てることができる（４０４）。例えば、立体空間の平面がｚ−平面である場合、３Ｄ立体空間のｘ−座標およびｙ−座標の各組み合わせに実行スレッドを割り当てる。図５の３Ｄ立体空間について考えると、この結果、１６個のスレッドが得られ、（０，０）、（１．０）、（２．０）、...、（１，３）、（２，３）、（３，３）のｘ、ｙ座標を有するボクセルに割り当てられる。
【００４８】
[0043]  次いで、別個の実行スレッドは各々、図４における点線ボックス４０６で示すように、同じ動作を実行する。各スレッドによって実行する動作を図６に模式的に示す。図６は、３Ｄ立体空間の上面図(top-down view)を示す（即ち、ｘ−軸５０２およびｚ−軸６を示し、ｙ−軸は、明確さの目的上、無視する）。この立体空間のｚ−平面上にある各座標に、実行スレッドを割り当て、Ｔ１  ６０２、Ｔ２  ６０４、...、Ｔｎ−１  ６０６、Ｔｎ  ６０８で示す。ボックス４０６において各スレッドによって実行する動作を、最初にＴ１  ６０２を参照して示す。
【００４９】
[0044]  実行スレッドに対するｚ−座標をゼロに設定し（４０８）、このスレッドに関連付けられたボクセルに対するｘ、ｙ、ｚ座標を、現実世界座標に変換する（４１０）。例えば、スレッドＴ１  ６０２の場合、このスレッドに関連付けられたｘ、ｙ座標は（０，０）であるので、ｚ−座標をゼロに設定すると、これによって（０，０，０）の座標が得られる（即ち、図６におけるボクセル６１０）。これを現実世界座標に変換することができる。一旦ボクセル６１０に対する現実世界座標が決定されたなら、深度カメラの６ＤＯＦ位置および向きを用いてこれらを変換し、このボクセルに対する深度画像３１４における対応位置を判定することができる。これが意味するのは、このスレッドに関連付けられた現在のボクセルに対する現実世界座標が、深度カメラの投影によって投影された全体像(perspective)になるということである。言い換えると、現実世界におけるこの点を表すボクセルが、位置および向きを有する深度カメラによって捉えられているとすると、これによって、深度画像４１４におけるその点に対する座標を決定する。このボクセルに対する深度カメラの視野における座標をｐＸ、ｐＹ、ｐＺで示す。深度カメラの視野における座標を、ｕ＝ｐＸ／ｐＺおよびｖ＝ｐＹ／ｐＺによって、深度画像画素座標（ｕ、ｖによって示す）に変換する。
【００５０】
[0045]  深度カメラ３０２の台形６１２を示す破線によって、深度カメラ３０２の視野を図６に示す。また、図６は、深度カメラから出力された画像３１４における表面６１４も示す。
【００５１】
[0046]  現在スレッドに関連付けられたボクセルに対する深度画像座標（ｕ、ｖ）を用いて、このボクセルが深度カメラの台形６１２内部に位置するか否か判定を行う（４１４）。位置していない場合、このボクセルを飛ばすことができる。図６を参照すると、スレッドＴ１の場合、現ボクセル６１０はカメラの台形６１２内部にあることに気付く。これは、例えば、スレッドＴｎ−１によって考慮される第１ボクセルがカメラの台形６１２の外側にあり、したがって飛ばされるのとは対照をなすことができる。
【００５２】
[0047]  現在のボクセルがカメラの台形６１２の内部にあると判定した場合、このボクセルと、カメラの視線からのこのボクセルに対応する位置における環境内の点との間の距離に関係する係数を判定する。この対応する位置における環境内の点は、深度画像における深度値によって（ｕ，ｖ）において与えることができる。したがって、図６を参照すると、この係数は、ボクセル６１０とボクセル６１０上にマッピングする深度画像３１４の表面６１４上にある点との間の距離６１６を考慮する。
【００５３】
[0048]  一例では、計算した係数（４２０）は、符合付きの距離関数であるが、いずれの暗黙的な表面表現も適用可能とすることができる（例えば、正確な表面位置を、数値法(numerical method)および規則的な格子上に格納されている有限数の点の間における補間によって決定することができるもの）。符合付き距離関数の計算は、現在のボクセルと深度画像３１４における対応点との間の距離の値を与え、深度画像（カメラの視線からの）における対応点の外側（即ち、外部）にあるボクセルには正の距離が与えられ、深度画像（カメラの視線からの）における対応点の内側（即ち、内部）にあるボクセルには負の距離が与えられるように、符合が付けられる。ゼロの値は、関連付けられたボクセルが正確に対応点と一致することを示す。この符合付き距離関数は、深度画像内の（ｕ，ｖ）における深度値からｐＺを減算することによって、容易に計算することができる。
【００５４】
[0049]  例えば、図６におけるボクセル６１０は、表面６１４上の対応点の前にあり、したがって、正の符号がついた距離関数値を有する。逆に、図６におけるボクセル６１８は、表面６１４上でその対応点の背後にあり、したがって、負の符号がついた距離関数値を有する。
【００５５】
[0050]  次に、この符号付き距離関数値を、既定の距離値に対して正規化する（４２２）。一例では、この既定値は、５ｃｍというような小さな距離にすることができるが、適した値であればいずれでも用いることができる。例えば、正規化は、再現されるノイズ・レベルおよび物体の厚さに応じて適応させることができる。これは、ユーザーによって手動で定めることができ、またはデーター内におけるノイズの分析によって自動的に導き出すことができる。次に、正規化した距離が正の閾値よりも大きいか（符合付き距離が正の場合）、または負の閾値よりも小さいか（符合付き距離が負の場合）判定を行う（４２４）。そうである場合、符合付き距離関数値を最大値または最小値に切り上げ（切り下げ）る（４２６）。例えば、正規化した距離が正の閾値よりも大きい場合、この値を＋１（正規化後の正の閾値）に切り上げることができ、正規化した距離が負の閾値よりも小さい場合、この値を−１（正規化後の負の閾値）に切り下げることができる。この計算の結果は、丸め符合付き距離関数（ＴＳＤＦ）として知られている。
【００５６】
[0051]  例えば、図６を参照すると、ボクセル６１０は、表面６１４の外側の比較的大きな距離にあり、したがって＋１に切り上げることができる。逆に、ボクセル６１８は表面６１４の内側の比較的短い距離にあり、したがって切り下げられず、その正規化した距離（例えば、−０．６）を維持すればよい。
【００５７】
[0052]  正規化した（そして、該当する場合には、丸めた）符合付き距離関数値を、次に、現在のボクセルに格納されている以前の値があればそれと組み合わせる。これが３Ｄ立体空間に組み込まれた最初の深度画像である場合、以前の値は存在しない。しかしながら、深度カメラから別のフレームを受け取り組み込んでいくと、ボクセルにおいて値が既に存在する可能性がある。
【００５８】
[0053]  一例では、符合付き距離関数値を以前の値と平均化によって組み合わせる（４２８）。これは、移動物体で環境のモデルを構築するのを補助することができる。何故なら、これによって、追加された測定値が古くなりもっと新しい測定値と平均化されるに連れて、移動した物体がときの経過とともに消えていくことが可能になるからである。例えば、指数的に減衰する移動平均を用いることができる。他の例では、この平均は、深度カメラから関連付けられたボクセルの距離に関係する重み関数を用いる加重平均とすることができる。平均符合付き距離関数値は、次に、現在のボクセルに格納することができる（４３０）。
【００５９】
[0054]  代替例では、各ボクセルに２つの値を格納することができる。符合付き距離関数値の加重和を計算して格納することができ、更に重みの総和も計算して格納することができる。次いで、（加重和）／（重みの総和）として、加重平均を計算することができる。
【００６０】
[0055]  次いで、３Ｄ立体空間の全てのｚ−平面がこのスレッドによって考慮されたか否か判定を行う（４１６）。されていない場合、ｚ−座標を増分し（４１８）、ｚ方向における次のボクセルに対して、本プロセスを繰り返す。言い換えると、スレッドは、立体空間のｚ方向に沿って同等のボクセル（即ち、同じｘ、ｙ座標を有するもの）にわたって繰り返して、丸め符合付き距離関数値を決定し、以前の値とこれらとの平均を取る。
【００６１】
[0056]  スレッドが全てのｚ−平面にわたって繰り返し終えるまで、これを繰り返す。これは各スレッドによって実行され、その各々がｚ−平面上にある異なるｘ、ｙ座標に割り当てられる。一度に立体空間の１つ平面ずつ順次行うことは、図５におけるメモリー・レイアウトには、相応しいメモリー・アクセス効率特性を有することになる。何故なら、１つのｚ−平面は線形間隔アレイ(linearly pitched array)の小さな連続領域に対応するからである。したがって、一旦全てのスレッドによってこれを完了したなら、３Ｄ立体空間全体が分析されたことになり、深度画像３１４に関するボクセル毎に、丸め符合付き距離関数が計算されたことになる。次いで、本プロセスは、深度カメラから次の深度画像が受け取られるのを待ち、可能な場合には、再び更に多くの値を３Ｄ立体空間に追加し始める。
【００６２】
[0057]  このプロセスの結果、１と＋１との間の平均値を有するボクセルを含む３Ｄ立体空間が得られる（しかし、この平均値は、以上の「加重和」および「重みの総和」値というような、多数の値によって表すことができることを注記しておく）。平均値がゼロである場合、環境における表面がその位置に存在することを示す。ときの経過と共に深度画像の多数のフレームが立体空間に追加されるので、この立体空間に格納されるモデルは、徐々に増々詳しく構築されていく。環境の同じ領域の測定を繰り返すことによって、更なる詳細が追加され、深度カメラによって提供される情報の解像度が効果的に高められる。更に、平均を取ることによって、深度画像からノイズも効果的に消し去られ、遙かに平滑な表面が残る。これによって、個々の深度画像からは見ることができない詳細を、モデルにおいて見ることが可能になる。
【００６３】
[0058]  このような別個に実行するスレッドの使用によって、３Ｄ立体空間全体にわたって計算的に効率的な処理が可能になる。例えば、ＧＰＵプロセッサーは、並列プログラム・スレッドを効率的に実行するように構成され、各スレッドが同じ動作を実行する。これによって、図４を参照して以上で説明したモデル生成プロセスをリアル・タイムで実行することが可能になり、深度カメラのフレーム・レートでモデルが組み立てられるようになる。
【００６４】
[0059]  一旦以上で説明したように３Ｄ立体空間においてモデルが組み立てられたなら、多数の方法でこれを利用することができる。例えば、この立体空間に格納されているモデルの光景(view)は、図７に示すようなレイキャスティング技法を用いてレンダリングすることができる。図７のフローチャートは、３Ｄ立体空間からレイキャスティングする並列化可能なプロセスを示す。これは、以上のモデル生成プロセスと同様なやり方でＧＰＵまたはマルチコアＣＰＵ上で実行するのに適している。
【００６５】
[0060]  モデルの光景をレンダリングするために、最初に、レンダリングしようとする画像に対して視点を定める仮想カメラの姿勢を受け取る（７００）。この姿勢は、仮想カメラの６ＤＯＦ位置および向きの形態とすることができる。次いで、レンダリングしようとする画像における各画素に、別個の実行スレッドを割り当てる（７０２）。
【００６６】
[0061]  次いで、ボックス７０４に示す動作を各実行スレッドによって実行して、スレッドの関連付けられた画素に適用する値（例えば、陰影、色等）を決定する。このスレッドと関連付けられている画素のｘ−およびｙ−座標を、既定の初期ｚ−値と組み合わせて、この画素に３Ｄ座標を与え、仮想カメラの姿勢を用いて、この画素の３Ｄ  ｘ、ｙ、ｚ座標を、Ｘ，Ｙ，Ｚで示す現実世界座標に変換する。次いで、現実世界座標Ｘ，Ｙ，Ｚを３Ｄ立体空間におけるボクセル座標に変換する（７０８）。
【００６７】
[0062]  これらの座標は、仮想カメラの位置から発して３Ｄ立体空間を通る経路を有する、画素に対する光線上において１つの点を定める。次いで、３Ｄ立体空間におけるどのボクセルにこの光線が最初に接触したのか判断し（７１０）、これをレイキャスティングの開始ボクセルとして設定する。レイキャスティング動作は、この光線に沿って（開始ボクセルから）移動し（７１２）、光線が接触したボクセルの平均符合付き距離関数値を各ボクセルにおいて読み取り、ボクセル値においてゼロ交差が生じたか否か判定を行う（７１４）（即ち、光線上の１つのボクセルに格納されている平均符合付き距離関数値と、光線に沿った次のボクセルに格納されている平均符合付き距離関数値との間の符合変化）。任意に、これは、正から０を通って負への符合変化の存在のみを判定するように構成することもできる。これによって、前方から見た表面と、物体の「内側」から見た表面との間で区別を行うことが可能になる。
【００６８】
[0063]  ゼロ交差が検出された場合、これは、モデルにおける表面の存在を示す（前述のように）。したがって、これは、表面が光線と交差するボクセルを示す。ゼロ交差の両側における光線上のボクセルの符合付き距離関数値間に、適した線形補間技法を用いると、正確にゼロ交差の位置を突き止めることができ、したがって、ゼロ交差表面との交点の位置を突き止めることができる。一例では、光線に沿った表面交点は、検出したゼロ交差の両側において３つの線に囲まれてサンプリングされた点(trilinearly sampled points)を仮定して、単純な線形補間を用いて計算して、ゼロが生ずる点を発見することができる。ゼロ交差が発生した点において、法線曲面を計算する（７１６）。これは、近隣ボクセルからの勾配を用いて実行することができる。また、線形補間は、近隣ボクセルからの勾配を一層精度高く決定するため、したがって一層正確な法線曲面を生成するためにも用いることができる。一例では、法線曲面は、後方差分数値微分(backward difference numerical derivatives)を用いて、次のように計算することができる。
【００６９】
【数３】
0005906258.tif 000004
【００７０】
[0064]  ここで、n^(x)は、ボクセルｘに対する法線であり、f(x)はボクセルｘに対する符合付き距離関数値である。この微分は、各次元において調整し、潜在的に任意のボクセル解像度および再現次元を仮定して、正しい等方性を確保することができる。
【００７１】
[0065]  ゼロ交差が生じたボクセルの座標を、現実世界座標に変換し（７１８）、モデルにおける表面の位置に現実世界座標を与える。この表面の現実世界座標から、その法線曲面を加えて、陰影および／または色を計算することができる（７２０）。計算する陰影および／または色は、適した陰影モデルであればいずれにでも基づくことができ、仮想光源の位置を考慮することができる。
【００７２】
[0066]  前述のように、ボックス７０４における動作は、各実行スレッドによって並列に実行され、最終出力画像における画素毎に、陰影および／または色を与える。次いで、画素毎に計算したデーターを組み合わせて出力画像を与えることができる（７２２）。これは、仮想カメラからのモデルの光景(view)のレンダリングとなる。
【００７３】
[0067]  以上で説明したレイキャスティングの並列性によって、３Ｄ環境の光景をリアル・タイムでレンダリングすることが可能になる。モデルをＧＰＵメモリーの３Ｄ立体空間に格納するときにＧＰＵ上でレイキャスティング動作を実行することは、高速で計算上効率的である。
【００７４】
[0068]  また、レイキャスティング動作は、空き空間飛び越しアルゴリズムを採用することによって、更に改良することができる。各光線はその経路に沿って数百ものボクセルと接触するので、空のボクセル（モデルについて何の情報も収容していないボクセル）を分析することによって計算リソースを浪費するのを回避することは有効である。一例では、光線に沿ってボクセルを１つずつ分析することを回避するために、ボクセルにおける値が既定値よりも大きい場合、その光線に沿った１つよりも多いボクセルを飛ばす。飛ばすボクセルの数、および既定値は、空間を飛ばすことによってゼロ交差が失われないことを確保するように、先に論じた既定距離値（正規化を制御する）の知識を用いてこれらのパラメーターを選択するのであれば、効率およびレイキャスティングの精度の間で折衷案を得るように定めることができる。
【００７５】
[0069]  他の例では、Ｎ次ツリー、例えば、オクトツリーのような、多レベル・データー構造を利用することによって、空間飛ばしを実行することができる。ここでは、主要な３Ｄ立体空間から、この３Ｄ立体空間よりも解像度が低い、少なくとも１つの追加の立体空間を生成する。低解像度の立体空間を最初に分析して、光線に沿ってどこに空き空間があるか判断し、主要な３Ｄ立体空間を分析して、空でないボクセルを通過する光線の部分を求めることができる。
【００７６】
[0070]  更に他の例では、３Ｄ立体空間に格納したモデルを用いて、環境のポリゴン・メッシュ表現を抽出することができる。これは、例えば、マーチング・キューブ・アルゴリズム(marching cube algorithm)、マーチング・テトラへドロン・アルゴリズム(marching tetrahedron algorithm)、ブルーメントール・ポリゴナイザー(Bluementhal Polygonizer)、またはモデルの部分を表すポリゴンを選択するための適したアルゴリズムであれば他のいずれを用いても遂行することができる。モデルのポリゴン表現は、一定の「水密」表面を利用する物理に基づくアプリケーションまたは他のアプリケーションには有用であることができる。
【００７７】
[0071]  例の中には、ポリゴン・メッシュが、モデルを表す格納効率を更に高める方法になることができる場合もあるが、深度カメラからの新たな測定値によって容易に更新することができない。したがって、ポリコン・メッシュは、深度カメラから３Ｄ立体空間内にモデルが作られた後に、このモデルを効率的に格納するために用いることができる。例えば、ポリゴン・メッシュは、ＧＰＵメモリー内ではなく、ＣＰＵメモリーのような記憶デバイス、またはディスク上に格納することができる。例の中には、モデルを組み立てた後、ポリゴン・メッシュ形態で「キャッシュし」、必要に応じて変換して符合付き距離関数形態に戻すことができる。例えば、ポリゴン・メッシュは、３Ｄ立体空間メモリーに収容(fit)できるよりも大きな現実世界エリアをカバーする大きなモデルを組み立てるために用いることができる。ある現実世界領域に対してモデルを３Ｄ立体空間において完成すると、これをポリゴン・メッシュ形態で書き出すことができ、３Ｄ立体空間をクリアして新たな現実世界領域をモデリングすることができる。これは、任意に、ポリゴン・メッシュに後から追加することができる。例の中には、先に説明したレイキャスティング動作を、３Ｄ立体空間からではなく、ポリゴン・メッシュから実行できる場合もある。更に他の例では、モデルの光景は、表充填機なグラフィクス・レンダリング・ラスタ化パイプラインのような代替技法を用いて、ポリゴン・メッシュから生成することができる。
【００７８】
[0072]  また、ポリゴン・メッシュとして格納した「キャッシュ」モデル(cached model)は、立体空間上に格納されている３Ｄモデルに変換することができる。例えば、格納されているキャッシュ・モデルを３Ｄ立体空間に「シード」(seed)として書き出すことができ、これに対して更に多くの深度画像を追加して、モデルの精度および詳細を更に高めることができる。
【００７９】
[0073]  尚、例の中には、暗黙的な表面表現が適用可能であるかもしれない場合もあることを注記しておく（例えば、正確な表面位置が、数値方法および規則的な格子上に格納された有限数の点間の補間によって決定することができるもの）。
【００８０】
[0074]  これより図８を参照すると、図８は、いずれかの形態の計算および／または電子デバイスとして実現することができ、以上で説明した３Ｄ環境モデリング技法の実施形態を実現することができる計算主体デバイス例１０００の種々のコンポーネントを示す。
【００８１】
[0075]  計算主体デバイス８００は、１つ以上のプロセッサー８０２を備えている。プロセッサー８０２は、マイクロプロセッサー、コントローラー、または３Ｄ再現を実験するためにデバイスの動作を制御する計算実行可能命令を処理するのに適したタイプのプロセッサーであれば他のいずれでもよい。例の中には、例えば、チップ・アーキテクチャ上のシステムを用いる場合、プロセッサー８０２は、本明細書において説明した方法の一部をハードウェアで実現する（ソフトウェアでもファームウェアでもなく）１つ以上の固定機能ブロック（アクセレレーターとも呼ぶ）を含むのでもよい。
【００８２】
[0076]  また、計算主体デバイス８００は、グラフィクス処理システム８０４も備えることができる。グラフィクス処理システム８０４は、通信インターフェース８０６を通じてプロセッサー８０２と通信し、１つ以上のグラフィクス処理ユニット８０８を備えている。グラフィクス処理ユニット８０８は、高速でしかも効率的に並列なスレッド動作を実行するように構成されている。また、グラフィクス処理システム８０４は、メモリー・デバイス８１０も備えている。メモリー・デバイス８１０は、ＧＰＵ８０８からの高速並列アクセスを可能にするように構成されている。例では、メモリー・デバイス８１０は３Ｄ立体空間を格納することができ、グラフィクス処理ユニット８０８は、以上で説明したモデル生成およびレイキャスティング動作を実行することができる。
【００８３】
[0077]  また、計算主体デバイス８００は、入力／出力インターフェース８１２も備えている。入力／出力インターフェース８１２は、可動環境キャプチャー・デバイス（深度カメラを備えている）、および任意に１つ以上のユーザー入力デバイス（例えば、ゲーム・コントローラ、マウス、キーボード等）というような１つ以上のデバイスから入力を受け取り、これらを処理するように構成されている。また、Ｉ／Ｏインターフェース８１２は、通信インターフェースとして動作することもできる。通信インターフェースは、１つ以上のネットワーク（例えば、インターネット）と通信するように構成することができる。
【００８４】
[0078]  また、表示インターフェース８１４も設けられ、表示情報をディスプレイ・デバイスに出力するように構成されている。ディスプレイ・デバイスは、計算主体デバイスと一体化されているかまたはこれと通信する。ディスプレイ・システムは、グラフィカル・ユーザー・インターフェース、またはいずれかの適したタイプの他のユーザー・インターフェースを設けるとよいが、これは必須ではない。
【００８５】
[0079]  計算主体デバイス８００によってアクセスすることができるいずれかのコンピューター読み取り可能媒体を用いて、コンピューター実行可能命令を供給することもできる。コンピューター読み取り可能媒体は、例えば、メモリー８１６のようなコンピューター記憶媒体、および通信媒体を含むことができる。メモリー８１６のようなコンピューター記憶媒体は、揮発性および不揮発性、リムーバブルおよび非リムーバブル媒体を含み、コンピューター読み取り可能命令、データー構造、プログラム・モジュール、またはその他のデーターというような情報の格納のためのいずれかの方法または技術で実現される。コンピューター記憶媒体は、限定ではなく、ＲＡＭ、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ，フラッシュ・メモリーまたは他のメモリー技術、ＣＤ−ＲＯＭ、ディジタル・バーサタイル・ディスク（ＤＶＤ）またはその他の光学ストレージ、磁気カセット、磁気テープ、磁気ディスク・ストレージまたは他の磁気記憶デバイス、あるいは計算デバイスによるアクセスのために情報を格納することができる他のあらゆる媒体を含むことができる。対照的に、通信媒体は、コンピューター読み取り可能命令、データー構造、プログラム・モジュール、または他のデーターを、搬送波というような変調データー信号、または他の伝達メカニズム内に具体化することができる。本明細書において定義する場合、コンピューター記憶媒体は通信媒体を含まないこととする。コンピューター記憶媒体（メモリー８１６）は計算主体デバイス８００内部に示されているが、記憶媒体は、分散することまたは離れて配置することもでき、ネットワークまたは他の通信リンクを通じてアクセスできる（例えば、Ｉ／Ｏインターフェース８１２を用いる）ことは認められよう。
【００８６】
[0080]  オペレーティング・システム８１８を構成するプラットフォーム・ソフトウェアまたは他のいずれかの適したプラットフォーム・ソフトウェアは、アプリケーション・ソフトウェア８２０を計算主体デバイス上で実行することを可能にするために、計算主体デバイスにおいて設けることができる。メモリー８１６は、緻密モデル統合エンジン８２２（例えば、図４を参照して説明したプロセスを用いて３Ｄモデル内にモデルを構築するように構成されている）、緻密モデル可視化エンジン８２４（例えば、図７のレイキャスティング・プロセスを用いてレンダリングしたモデルの画像を出力するように構成されている）、および緻密モデル・クエリー・エンジン８２６（例えば、ポリゴン・メッシュを組み立てるために、モデルからデーターを得るように構成されている）の機能を実現するための実行可能命令を格納することができる。また、メモリー８１６は、データー・ストア８３０も設けることができる。データー・ストア８３０は、ポリゴン・メッシュを格納するためにというように、３Ｄモデリング技法を実行するときに、プロセッサー８０２によって用いられるデーターのためのストレージを設けるために用いることができる。
【００８７】
[0081]  「コンピューター」という用語は、本明細書では、命令を実行することができるような処理能力を有するあらゆるデバイスを指すために用いられる。このような処理能力が多くの異なるデバイスに組み込まれており、したがって、「コンピューター」という用語はＰＣ、サーバー、移動体電話機、パーソナル・ディジタル・アシスタント、および多くの他のデバイスを含むことが、当業者にはわかるであろう。
【００８８】
[0082]  本明細書において記載した方法は、有形記憶媒体上における機械読み取り可能な形態としたソフトウェアによって実行することができ、例えば、コンピューター・プログラムの形態をなし、このプログラムをコンピューター上で実行すると、本明細書において記載した方法のいずれでも、全てのステップを実行するように構成されたコンピューター・プログラム・コードを備えており、このコンピューター・プログラムは、コンピューター読み取り可能媒体上に具体化することができる。有形（または、非一時的）記憶媒体の例には、ディスク、サム・ドライブ(thumb drive)、メモリー等が含まれ、伝搬信号は含まれない。ソフトウェアは、本方法ステップをいずれかの適した順序で、または同時に実行することができるように、並列プロセッサーまたは直列プロセッサー上で実行するのに適していると言うことができる。
【００８９】
[0083]  これは、ソフトウェアが、価値があり、別個に取引可能な産物であることができることを認めるものである。所望の機能を実行するために、「ダムターミナル」(dumb)または標準的なハードウェア上で実行するまたはこれを制御するソフトウェアを包含することを意図している。また、所望の機能を実行するために、シリコン・チップを設計するためあるいはユニバーサル・プログラマブル・チップを構成するために用いられる、ＨＤＬ（ハードウェア記述言語）ソフトウェアのような、ハードウェアの構成を「記述する」または定義するソフトウェアを包含することも意図している。
【００９０】
[0084]  当業者には、プログラム命令を格納するために利用する記憶デバイスはネットワークを跨がって分散できることは分かるであろう。例えば、リモート・コンピューターが、ソフトウェアとして記述されたプロセスの一例を格納することができる。ローカル・コンピューター即ち端末コンピューターがこのリモート・コンピューターにアクセスして、そのソフトウェアの一部または全部をダウンロードしてプログラムを実行することができる。あるいは、ローカル・コンピューターが必要に応じて複数のソフトウェア(pieces of software)をダウンロードすることもでき、または一部のソフトウェア命令をローカル端末において実行し、一部をリモート・コンピューター（またはコンピューター・ネットワーク）で実行することもできる。また、当業者には周知の従来の技術を利用することによって、ソフトウェア命令の全部または一部が、ＤＳＰ、プログラマブル・ロジック・アレイ等のような専用回路によって実行するのでもよいことは、当業者には分かるであろう。
【００９１】
[0085]  本明細書において示した範囲またはデバイス値はいずれも、求めようとする効果を失うことなく、広げることまたは変更することもでき、これは当業者には明白であろう。
【００９２】
[0086]  尚、以上で記載した効果および利点は、一実施形態に関する場合もあり、または様々な実施形態に関する場合もあることは言うまでもない。実施形態は、記載した問題のいずれを解決するものにも、またその全てを解決するものにも限定されず、更には記載した効果および利点のいずれかを有するものにも、またその全てを有するものにも限定されない。更に、「１つの」品目に対する引用は、１つ以上のこれらの品目にも言及することは言うまでもない。
【００９３】
[0087]  本明細書において記載した方法のステップは、いずれの順序でも実行することができ、またしかるべき場合には同時に実行することもできる。加えて、本明細書に記載した主題の主旨および範囲から逸脱することなく、個々のブロックを前述の方法のいずれからでも削除することもできる。以上で説明した例のいずれの態様も、求めようとする効果を失うことなく、更に他の例を形成するために、説明した他の例のいずれの態様とでも組み合わせることができる。
【００９４】
[0088]  「備えている」(comprising)という用語は、本明細書では、特定された方法のブロックまたはエレメントを含むことを意味するが、このようなブロックまたはエレメントが排他的なリストを構成するのではなく、方法または装置が追加のブロックまたはエレメントを含んでもよいことを意味する。
【００９５】
[0089]  尚、好ましい実施形態についての以上の説明は、一例として示したに過ぎず、種々の変更が当業者によってなされてもよいことは言うまでもない。以上の明細書、例、およびデーターは、本発明の代表的実施形態の構造および使用についての完全な説明を提供する。以上では本発明の種々の実施形態についてある程度の特定性をもって、または１つ以上の個々の実施形態を参照して説明したが、当業者であれば、本発明の主旨または範囲から逸脱することなく、開示した実施形態に対して多数の変更を行うことができよう。
【図１】
0005906258.tif 000005
【図２】
0005906258.tif 000006
【図３】
0005906258.tif 000007
【図４】
0005906258.tif 000008
【図５】
0005906258.tif 000009
【図６】
0005906258.tif 000010
【図７】
0005906258.tif 000011
【図８】
0005906258.tif 000012