(57)【要約】【課題】三次元モデル・データを処理するための方法および装置を提供すること。【解決手段】本発明は、コンピュータ・グラフィックスのネットワーク送信および表示に関する。三次元モデル・データを処理するための方法および装置が提供され、この方法は、元のメッシュ・モデルのメッシュ・データを取得するステップと、あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって元のメッシュ・モデルの頂点データから派生メッシュ・モデルを構築するステップと、元のメッシュ・モデルのメッシュ・データを派生メッシュ・モデルのメッシュ・データと比較して、派生メッシュ・モデルのエラー・データを取得するステップと、元のメッシュ・モデルに関連する頂点データを送信するステップと、派生メッシュ・モデルのエラー・データを送信するステップとを含む。【選択図】図３
2015507797.tif 000002
【特許請求の範囲】
【請求項１】
三次元モデル・データを処理するための方法であって、
元のメッシュ・モデルのメッシュ・データを取得するステップと、
あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって前記元のメッシュ・モデルの頂点データから派生メッシュ・モデルを構築するステップと、
前記元のメッシュ・モデルの前記メッシュ・データを前記派生メッシュ・モデルの前記メッシュ・データと比較して、前記派生メッシュ・モデルのエラー・データを取得するステップと、
前記元のメッシュ・モデルに関連する頂点データを送信するステップと、
前記派生メッシュ・モデルの前記エラー・データを送信するステップと
を含む、方法。
【請求項２】
前記元のメッシュ・モデルの前記メッシュ・データを前記派生メッシュ・モデルの前記メッシュ・データと前記比較するステップが、前記元のメッシュ・モデルの辺データを前記派生メッシュ・モデルの辺データと比較するステップを含み、前記エラー・データが、余分な辺データおよび欠けている辺データを含み、前記余分な辺データが、前記派生メッシュ・モデルに存在するが前記元のメッシュ・モデルには存在しないあらゆる辺を含み、前記欠けている辺データが、前記元のメッシュ・モデルに存在するが前記派生メッシュ・モデルには存在しないあらゆる辺を含む、請求項１に記載の方法。
【請求項３】
前記元のメッシュ・モデルの前記メッシュ・データを前記派生メッシュ・モデルの前記メッシュ・データと前記比較するステップが、前記元のメッシュ・モデルの面データを前記派生メッシュ・モデルの面データと比較するステップを含み、前記エラー・データが、余分な面データおよび欠けている面データを含み、前記余分な面データが、前記派生メッシュ・モデルに存在するが前記元のメッシュ・モデルには存在しないあらゆる面を含み、前記欠けている面データが、前記元のメッシュ・モデルに存在するが前記派生メッシュ・モデルには存在しないあらゆる面を含む、請求項１に記載の方法。
【請求項４】
前記派生メッシュ・モデルの前記エラー・データを前記送信するステップが、前記エラー・データを複数のエラー・データ部分集合に分割するステップと、前記エラー・データ部分集合のすべてが送信されるまで、毎回、前記エラー・データ部分集合の１つを送信するステップとを含む、請求項２または３に記載の方法。
【請求項５】
前記元のメッシュ・モデルに関連する前記頂点データが、前記元のメッシュ・モデルの前記頂点データである、請求項１に記載の方法。
【請求項６】
前記元のメッシュ・モデルの前記頂点データに従って導出頂点データを生成するステップ
をさらに含み、
前記元のメッシュ・モデルに関連する前記頂点データが、前記導出頂点データを含む、請求項１に記載の方法。
【請求項７】
三次元モデル・データを処理するための方法であって、
三次元メッシュ・モデルをレンダリングするためにデータを受信するステップと、
前記受信したデータが元のメッシュ・モデルに関連する頂点データであることに応じて、
あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって前記元のメッシュ・モデルの頂点データから派生メッシュ・モデルを構築すること、および
前記構築された派生メッシュ・モデルに基づいて三次元モデルを表示すること
を行うステップと、
前記受信したデータが前記派生メッシュ・モデルのエラー・データであることに応じて、前記受信されたエラー・データを用いて表示中の前記三次元メッシュ・モデルを修正するステップと
を含む、方法。
【請求項８】
前記元のメッシュ・モデルに関連する前記頂点データが、
前記元のメッシュ・モデルの前記頂点データ、または
前記元のメッシュ・モデルの前記頂点データから導出された頂点データ
のうちの１つを含む、請求項７に記載の方法。
【請求項９】
前記エラー・データが、
余分な辺データ、
欠けている辺データ、
余分な面データ、および
欠けている面データ
のうちの少なくとも１つを含み、
前記受信したエラー・データを用いて表示されている前記三次元メッシュ・モデルを前記修正するステップが、
前記エラー・データが前記余分な辺データを含むことに応じて、前記余分な辺データ中の辺を、現在表示されている前記三次元メッシュ・モデルから削除するステップと、
前記エラー・データが前記欠けている辺データを含むことに応じて、前記欠けている辺データ中の辺を、現在表示されている前記三次元メッシュ・モデルに追加するステップと、
前記エラー・データが前記余分な面データを含むことに応じて、前記余分な面データ中の面を、現在表示されている前記三次元メッシュ・モデルから削除するステップと、
前記エラー・データが前記欠けている面データを含むことに応じて、前記欠けている面データ中の面を、現在表示されている前記三次元メッシュ・モデルに追加するステップと
を含む、請求項７に記載の方法。
【請求項１０】
前記派生メッシュ・モデルの前記エラー・データが、
前記派生メッシュ・モデルのメッシュ・データと前記元のメッシュ・モデルのメッシュ・データとの差異を表すデータ、および
前記派生メッシュ・モデルと前記元のメッシュ・モデルとの差異を表す前記データの部分集合
のうちの１つを含む、請求項９に記載の方法。
【請求項１１】
三次元モデル・データを処理するための装置であって、
元のメッシュ・モデルのメッシュ・データを取得するように構成された、データ取得ユニットと、
あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって、前記元のメッシュ・モデルの頂点データから派生メッシュ・モデルを構築するように構成された、メッシュ・モデル構築ユニットと、
前記元のメッシュ・モデルの前記メッシュ・データを前記派生メッシュ・モデルのメッシュ・データと比較して、前記派生メッシュ・モデルのエラー・データを取得するように構成された、比較ユニットと、
前記元のメッシュ・モデルに関連する頂点データを送信するように構成された、頂点データ送信ユニットと、
前記派生メッシュ・モデルの前記エラー・データを送信するように構成された、エラー・データ送信ユニットと
を含む、装置。
【請求項１２】
前記比較ユニットが、前記元のメッシュ・モデルの辺データを前記派生メッシュ・モデルの辺データと比較するように構成され、前記エラー・データが、余分な辺データおよび欠けている辺データを含み、前記余分な辺データが、前記派生メッシュ・モデルに存在するが前記元のメッシュ・モデルには存在しないあらゆる辺を含み、前記欠けている辺データが、前記元のメッシュ・モデルに存在するが前記派生メッシュ・モデルには存在しないあらゆる辺を含む、請求項１１に記載の装置。
【請求項１３】
前記比較ユニットが、前記元のメッシュ・モデルの面データを前記派生メッシュ・モデルの面データと比較するように構成され、前記エラー・データが、余分な面データおよび欠けている面データを含み、前記余分な面データが、前記派生メッシュ・モデルに存在するが前記元のメッシュ・モデルには存在しないあらゆる面を含み、前記欠けている面データが、前記元のメッシュ・モデルに存在するが前記派生メッシュ・モデルには存在しないあらゆる面を含む、請求項１１に記載の装置。
【請求項１４】
前記エラー・データ送信ユニットが、前記エラー・データを複数のエラー・データ部分集合に分割し、前記エラー・データ部分集合のすべてが送信されるまで、毎回、前記エラー・データ部分集合の１つを送信するように構成された、請求項１２または１３に記載の装置。
【請求項１５】
前記元のメッシュ・データに関連する前記頂点データが、前記元のメッシュ・データの前記頂点データである、請求項１１に記載の装置。
【請求項１６】
前記元のメッシュ・モデルの前記頂点データに従って導出頂点データを生成するように構成された、データ導出ユニットをさらに含み、前記元のメッシュ・データに関連する前記頂点データが、前記導出頂点データを含む、請求項１１に記載の装置。
【請求項１７】
三次元モデル・データを処理するための装置であって、
三次元（３Ｄ）メッシュ・モデルをレンダリングするためにデータを受信するように構成された、データ受信ユニットと、
前記データ受信ユニットによって受信された前記データの型を判断するように構成された、データ型判断ユニットと、
前記受信したデータが元のメッシュ・モデルに関連する頂点データであることに応じて、あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって、前記元のメッシュ・モデルの頂点データから派生メッシュ・モデルを構築するように構成された、メッシュ・モデル構築ユニットと、
前記構築された派生メッシュ・モデルを表示するように構成された、３Ｄモデル・レンダリング・ユニットであって、前記受信したデータが前記派生メッシュ・モデルのエラー・データであることに応じて、受信した前記エラー・データを用いて表示されている３Ｄの前記メッシュ・モデルを修正するようにさらに構成された、前記３Ｄモデル・レンダリング・ユニットと
を含む、装置。
【請求項１８】
前記元のメッシュ・モデルに関連する前記頂点データが、
前記元のメッシュ・モデルの前記頂点データ、または
前記元のメッシュ・モデルの前記頂点データから導出された頂点データ
のうちの１つを含む、請求項１７に記載の装置。
【請求項１９】
前記エラー・データが、
余分な辺データ、
欠けている辺データ、
余分な面データ、および
欠けている面データ
のうちの少なくとも１つを含み、
前記３Ｄモデル・レンダリング・ユニットが、
前記エラー・データが前記余分な辺データを含んでいることに応じて、現在表示されている前記三次元メッシュ・モデルから前記余分な辺データ中の辺を削除する、
前記エラー・データが前記欠けている辺データを含んでいることに応じて、現在表示されている前記三次元メッシュ・モデルに前記欠けている辺データ中の辺を追加する、
前記エラー・データが前記余分な面データを含んでいることに応じて、現在表示されている前記三次元メッシュ・モデルから前記余分な面データ中の面を削除する、および
前記エラー・データが前記欠けている面データを含んでいることに応じて、現在表示されている前記三次元メッシュ・モデルに前記欠けている面データ中の面を追加する
ように構成された、請求項１７に記載の装置。
【請求項２０】
前記派生メッシュ・モデルの前記エラー・データが、
前記派生メッシュ・モデルのメッシュ・データと前記元のメッシュ・モデルのメッシュ・データとの差異を表すデータ、および
前記派生メッシュ・モデルと、前記元のメッシュ・モデルとの差異を表す前記データの部分集合
のうちの１つを含む、請求項１９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概してコンピュータ・グラフィックスのネットワーク送信および表示に関し、詳細には、三次元グラフィックスのためのメッシュ・データの処理に関する。
【背景技術】
【０００２】
三次元（３Ｄ）グラフィックスは、仮想世界、ビデオゲームなどのようなマルチメディア応用において広く使用されている。三次元グラフィックスは、通常三次元モデルを用いて表現され、メッシュ・モデルは一般的に使用される三次元モデルである。一般に、メッシュ・モデルを描くためのメッシュ・データは、膨大な量のデータである。インターネット・ベースの３Ｄグラフィックス・アプリケーションでは、多くの場合、ネットワークを介してソース・コンピュータ（例えば、サーバ）からターゲット・コンピュータ（例えば、クライアント）へ大量のメッシュ・データを送信することが必要とされる。ネットワーク帯域幅リソースが限られている場合、ソース・コンピュータからターゲット・コンピュータへ送信されるメッシュ・データの量が大きい場合、メッシュ・データを適時に送信することができない可能性があり、その結果、対応する３Ｄグラフィックスを適時に示すことができず、これはユーザ体験に悪影響を及ぼす。マルチメディア・ユーザは、帯域幅リソースが限られている場合でも、コンピュータ・ネットワークを介して満足のいく速度でメッシュ・データを送信できることを希望する場合がある。
【０００３】
従来の技術には、メッシュ・モデル・データをプログレッシブに（progressively）送信するための方法がある。例えば、論文「Progressive Mesh」（H.Hoppe, ACM SIGGRAPH 1996Proceedings）において、３Ｄメッシュ・モデルを送信するための方法が提案されている。この方法によれば、３Ｄメッシュ・モデルは、階層メッシュに変換され、これがサーバに格納される。階層メッシュは、いくつかのサブメッシュを含む。サブメッシュはそれぞれ、３Ｄメッシュ・モデルに関する情報の一部を含み、その情報量は様々である。各サブメッシュを送信することにより、３Ｄメッシュ・モデルのデータは受信側に徐々に送信される。受信側は、サブメッシュの情報を受信すると、対応する三次元グラフィックスを表示することになる。時間とともに、受信側で表示される三次元グラフィックスは、元の３Ｄメッシュ・モデルに次第に近くなり、最終的に同じになる。上述した従来の技術の方法は、サブメッシュを送信する際に、元の３Ｄメッシュ・モデルの頂点データと辺データの両方を同時に送信することが必要とされる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】「Progressive Mesh」（H.Hoppe, ACM SIGGRAPH 1996 Proceedings）
【非特許文献２】「A New Voronoi-Based SurfaceReconstruction Algorithm」(Amenta et al., SIGGRAPH 1998)
【非特許文献３】「Poisson Surface Reconstruction」(Kazhdan et al., Symposium on Geometry Processing 2006)
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、データを受信するターゲット・コンピュータにおいて３Ｄグラフィックスを表示する速度を上げるための、コンピュータ・ネットワークを介してメッシュ・モデルのメッシュ・データを送信する改善された方法を提供することである。
【課題を解決するための手段】
【０００６】
１つの態様では、元のメッシュ・モデルのメッシュ・データを取得するステップと、あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって元のメッシュ・モデルの頂点データから派生メッシュ・モデルを構築するステップと、元のメッシュ・モデルのメッシュ・データを派生メッシュ・モデルのメッシュ・データと比較して、派生メッシュ・モデルのエラー・データを取得するステップと、元のメッシュ・モデルと関連する頂点データを送信するステップと、派生メッシュ・モデルのエラー・データを送信するステップとを含む、三次元モデル・データを処理するための方法が提供される。
【０００７】
別の態様では、三次元メッシュ・モデルをレンダリングするためにデータを受信するステップと、受信したデータが元のメッシュ・モデルに関連する頂点データであることに応じて、あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって元のメッシュ・モデルの頂点データから派生メッシュ・モデルを構築すること、および構築した派生メッシュ・モデルに基づいて三次元モデルを表示することを行うステップと、受信したデータが派生メッシュ・モデルのエラー・データであることに応じて、受信したエラー・データを用いて表示されている三次元メッシュ・モデルを修正するステップとを含む、三次元モデル・データを処理するための方法が提供される。
【０００８】
さらに別の態様では、元のメッシュ・モデルのメッシュ・データを取得するように構成された、データ取得ユニットと、あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって元のメッシュ・モデルの頂点データから派生メッシュ・モデルを構築するように構成された、メッシュ・モデル構築ユニットと、元のメッシュ・モデルのメッシュ・データを派生メッシュ・モデルのメッシュ・データと比較して、派生メッシュ・モデルのエラー・データを取得するように構成された、比較ユニットと、元のメッシュ・データに関連する頂点データを送信するように構成された、頂点データ送信ユニットと、派生メッシュ・モデルのエラー・データを送信するように構成された、エラー・データ送信ユニットとを含む、三次元モデル・データを処理するための装置が提供される。
【０００９】
さらに別の態様では、三次元（３Ｄ）メッシュ・モデルをレンダリングするためにデータを受信するように構成された、データ受信ユニットと、データ受信ユニットによって受信されたデータの型を判断するように構成された、データ型判断ユニットと、受信されたデータが元のメッシュ・モデルに関連する頂点データであることに応じて、あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって元のメッシュ・モデルの頂点データから派生メッシュ・モデルを構築するように構成された、メッシュ・モデル構築ユニットと、構築された派生メッシュ・モデルを表示するように構成され、受信されたデータが派生メッシュ・モデルのエラー・データであることに応じて、受信されたエラー・データを用いて表示されている三次元メッシュ・モデルを修正するようにさらに構成された、３Ｄモデル・レンダリング・ユニットとを含む、三次元モデル・データを処理するための装置が提供される。
【００１０】
図面と併せて、また次の詳細な説明を参照して、限定的ではなく例示的な方法で示される本発明のいくつかの実施形態から、本発明の実施形態の特徴、利点、および他の側面がさらに明らかになるであろう。
【図面の簡単な説明】
【００１１】
【図１】本発明の様々な実施形態を実現するために使用されるように構成された例示的コンピューティング・システム１００の図である。
【図２】三次元グラフィックスのメッシュ・モデル、およびメッシュ・モデルのデータ表現を例示的に示す図である。
【図３】本発明の一実施形態による三次元モデル・データを処理するための方法のフロー・チャートを例示的に示す図である。
【図４】派生メッシュ・モデルを概略的に示す図である。
【図５】元のメッシュ・モデルに関連する頂点データを概略的に示す図である。
【図６】元のメッシュ・モデルに関連する頂点データを概略的に示す図である。
【図７】元のメッシュ・モデルに関連する頂点データを概略的に示す図である。
【図８】本発明の一実施形態による三次元モデル・データを処理するための方法のフロー・チャートを例示的に示す図である。
【図９】ターゲット・コンピュータ２０２において三次元メッシュ・モデルをレンダリングする処理を概略的に示す図である。
【図１０】ターゲット・コンピュータ２０２において三次元メッシュ・モデルをレンダリングする処理を概略的に示す図である。
【図１１】ターゲット・コンピュータ２０２において三次元メッシュ・モデルをレンダリングする処理を概略的に示す図である。
【図１２】本発明の一実施形態による三次元モデル・データを処理するための装置を例示的に示す図である。
【図１３】本発明の別の実施形態による三次元モデル・データを処理するための装置を例示的に示す図である。
【発明を実施するための形態】
【００１２】
図中のフロー・チャートおよびブロックは、本発明の実施形態によるコンピュータ・プログラム製品によって実行可能なシステム、方法、ならびにアーキテクチャ、機能、および動作を示す。この点に関して、フロー・チャートまたはブロック中の各ブロックは、モジュール、プログラム・セグメント、またはコードの一部を表すことができ、１つまたは複数の指定された論理機能を実行するための１つまたは複数の実行可能命令を含む。いくつかの代替的な実施では、ブロックに示した機能が、図に示した順序とは異なる順序で行われる場合もあることに注意すべきである。例えば連続して示される２つのブロックは、ほぼ並行して、または逆の順序で行われる場合がある。これは、関連機能によって決まる。ブロック図またはフロー・チャート、あるいはその両方の中の各ブロック、ならびにブロック図またはフロー・チャート、あるいはその両方の中のブロックの組合せは、特定機能または動作を行う専用ハードウェアベースのシステムによって、あるいは専用ハードウェアとコンピュータ命令の組合せによって、実行可能であることにも注意すべきである。
【００１３】
以下に、様々な例示の実施形態を参照して本発明の原理および趣旨を説明する。これらの実施形態の提供は、当業者が本発明をよりよく理解し、さらに実施できるようにするものであり、本発明の範囲をいかなる方法でも限定することを目的としていないことを理解すべきである。
【００１４】
図１は、本発明の実施形態を実装するように構成された例示的コンピューティング・システム１００のブロック図を示す。図１に示すコンピューティング・システム１００は、ＣＰＵ（中央処理装置）１０１と、ＲＡＭ（ランダム・アクセス・メモリ）１０２と、ＲＯＭ（読取り専用メモリ）１０３と、システム・バス１０４と、ハード・ディスク・コントローラ１０５と、キーボード・コントローラ１０６と、シリアル・インタフェース・コントローラ１０７と、パラレル・インタフェース・コントローラ１０８と、ディスプレイ・コントローラ１０９と、ハード・ディスク１１０と、キーボード１１１と、シリアル周辺装置１１２と、パラレル周辺装置１１３と、ディスプレイ１１４とを含む。これらの構成要素のうち、ＣＰＵ１０１、ＲＡＭ１０２、ＲＯＭ１０３、ハード・ディスク・コントローラ１０５、キーボード・コントローラ１０６、シリアル・インタフェース・コントローラ１０７、パラレル・インタフェース・コントローラ１０８、およびディスプレイ・コントローラ１０９は、システム・バス１０４に接続される。ハード・ディスク１１０は、ハード・ディスク・コントローラ１０５に接続され、キーボード１１は、キーボード・コントローラ１０６に接続され、シリアル周辺装置１１２は、シリアル・インタフェース・コントローラ１０７に接続され、パラレル周辺装置１１３は、パラレル・インタフェース・コントローラ１０８に接続され、ディスプレイ１１４は、ディスプレイ・コントローラ１０９に接続される。図１の構造ブロック図は、単に例示の目的で示しており、本発明の範囲を限定することを意図していないことを理解すべきである。いくつかの例では、必要に応じていくつかのデバイスを追加する、または削除することができる。例えば、コンピュータ・ネットワークにアクセスする能力を有するように、コンピューティング・システム１００のためにネットワーク・アダプタを構成することができる。
【００１５】
図１に示すコンピューティング・システム１００は、本発明の様々な実施形態に適用できるソース・コンピュータおよび宛先コンピュータの実装に使用することができる。
【００１６】
本発明の様々な実施形態を説明する前に、三次元グラフィックスのメッシュ・モデルおよびメッシュ・モデルのデータ表現についてまず説明する。図２は、三次元グラフィックスのメッシュ・モデル、およびメッシュ・モデルを表すデータ表現を概略的に示す。
【００１７】
図２には、三次元グラフィックス２１０の一例を示している。グラフィックスの頭部は、参照符号２２０で示す３Ｄメッシュ・モデル（「メッシュ・モデル」とも呼ばれる）で表現することができる。メッシュ・モデルの細部は、多数の三角形面によって構成される。
【００１８】
参照符号２３０は、単純化したメッシュ・モデルを示す。メッシュ・モデル２３０は、１０個の頂点ｖ１からｖ１０と、１１個の三角形面ｆ１からｆ１１とによって構成された、閉じた構造体である。
【００１９】
参照符号２４０は、メッシュ・モデル２３０の頂点の幾何学的情報を提供する、メッシュ・モデル２３０の頂点リストを示す。詳細には、頂点リスト２４０には、メッシュ・モデル２３０の頂点｛ｖ１，ｖ２，ｖ３．．．｝のすべてと、頂点のそれぞれの三次元座標、例えば頂点ｖ１とその座標（ｘ１，ｙ１，ｚ１）が一覧表示される。
【００２０】
参照符号２５０は、メッシュ・モデル２３０の面リストを示す。面リスト２５０では、メッシュ・モデル２３０の面（ｆ１，ｆ２，．．．）のすべてと、面のそれぞれを構成している頂点、例えば面ｆ１とその構成頂点（ｖ１，ｖ２，ｖ３）が一覧表示される。
【００２１】
面リスト２５０の等価の形式が、辺リスト２６０である。辺リスト２６０は、メッシュ・モデル２３０の辺のすべて、例えば２つの頂点ｖ１およびｖ２を結ぶ辺ｅ１を、一覧表示する。辺リスト２６０は、メッシュ・モデル２３０の頂点の間の接続の情報を提供する。
【００２２】
頂点リスト２４０および面リスト２５０は、「メッシュ・データ」と呼ばれる、メッシュ・モデル２３０のデータ集合を構成する。明らかに、メッシュ・モデル２３０のデータ集合、またはメッシュ・データもまた、頂点リスト２４０および辺リスト２６０で表されるデータからなる、すなわちメッシュ・モデルの頂点集合および辺集合からなることができる。
【００２３】
メッシュ・モデル（以下では、単に「メッシュ」とも呼ぶ）は、頂点および頂点を結んだ辺によって構成される閉じた構造体であると言うことができる。
【００２４】
説明の便宜上、次の説明では、頂点が位置している辺を頂点の「隣接辺」と呼び、例えば辺ｅ１と辺ｅ３の両方が頂点ｖ１の隣接辺である。明らかに、１つの頂点が、２つ以上の隣接辺を有する可能性がある。また頂点が位置している面は、頂点の「隣接面」と呼ばれ、例えば面ｆ１と面ｆ２の両方が頂点ｖ１の隣接面である。明らかに、１つの頂点が、２つ以上の隣接面を有する可能性がある。
【００２５】
図２の下部に、本発明の適用のシナリオを示す。図示のように、インターネット・ベースの三次元適用例では、送信側として機能しているソース・マシン（例えば、サーバ）２０１から、受信側として機能しているターゲット・コンピュータ（例えば、クライアント）２０２へ、ネットワーク２０３を介して三次元グラフィックスのメッシュ・データを送信する必要がある。三次元グラフィックスのメッシュ・モデルのデータ量は、通常非常に大きく（最大約１０メガバイト）、グラフィックスの精度の要求が高まるほど、データ量は大きくなる。これにより、ネットワーク２０３の帯域幅に対する要求が高まる。帯域幅が不十分である場合、メッシュ・モデル・データは、ソース・コンピュータ２０１からターゲット・コンピュータ２０２へ適時に送信できない恐れがある。その結果、３Ｄグラフィックスは、ターゲット・コンピュータにおいて適時にレンダリングされることが不可能であり、受信側におけるユーザの体験に悪影響を及ぼす。
【００２６】
発明者らは、メッシュ・モデルの辺の数は、頂点の数の増加とともに増えることに注目した。オイラーの公式によれば、実際の適用例におけるより複雑なメッシュ・モデルについては、辺の数は頂点の数のおよそ３倍である可能性がある。発明者らは、コンピュータ・ネットワークを介してメッシュ・モデルを送信するとき、ソース・コンピュータ２０１は頂点データに関する情報と、面／辺データに関する情報とを同時に送信する必要がなく、ターゲット・コンピュータ２０２は、３Ｄメッシュ・モデルをプログレッシブに表示することもできることを発見した。
【００２７】
本発明の基本的な考えは、ソース・コンピュータ２０１に、まずターゲット・コンピュータ２０２にメッシュ・データ中の頂点データに関する情報を個別に送信させ、次いでターゲット・コンピュータ２０２にメッシュ・データ中の辺／面データに関する情報を送信させることである。
【００２８】
したがって、ターゲット・コンピュータ２０２は、メッシュ・データ中の頂点データに関する情報を受信すると、従来の技術に既存のあらかじめ定義されたアルゴリズムを使用して派生メッシュ・モデルを推論的に構築し、構築した派生メッシュ・モデルを表示し、メッシュ・データ中の辺／面データに関する情報を受信した後に派生メッシュ・モデルを修正することになる。辺／面データに関する情報を送信するのと同時に頂点データに関する情報を送信する必要がないので、大量の送信帯域幅が節約され、頂点データに関する情報、および辺データもしくは面データに関する情報をターゲット・コンピュータ２０２に滞りなく、適時に送信することができる。頂点データに関する情報がターゲット・コンピュータに到着した後、ターゲット・コンピュータは、頂点データに関する情報に従ってメッシュ・モデルを推論的に構築し、元の３Ｄグラフィックスに近い３Ｄグラフィックスを表示することができる。その後、辺データまたは面データに関する情報がターゲット・コンピュータに到着した後、ターゲット・コンピュータは、表示される３Ｄグラフィックが３Ｄグラフィックスと同じになるまで、表示される３Ｄグラフィックを修正することができる。
【００２９】
次に図３を参照し、図２に示すメッシュ・モデル２３０例にとって、三次元モデルのメッシュ・データを処理するための方法を説明する。図３は、本発明の一実施形態による三次元モデルのメッシュ・データを処理するための方法のフロー・チャートを概略的に示す。
【００３０】
図３に示す方法は、ソース・コンピュータ２０１で実行することができる。処理は、次のようである。
【００３１】
まず、ステップＳ３１０において、元のメッシュ・モデルのメッシュ・データが取得される。
【００３２】
元のメッシュ・モデルは、ターゲット・コンピュータ２０２で表示されるべきメッシュ・モデルである。元のメッシュ・モデル・データのメッシュ・データは、頂点データ、ならびに辺データまたは面データを含む。
【００３３】
メッシュ・モデルは、例えば、図２のメッシュ・モデル２３０とすることができ、そのメッシュ・データは、頂点リスト２４０および辺リスト２６０によって表されるか、または等価なものとして、頂点リスト２４０および面リスト２５０によって表される。これらのリストのデータは、事前にデータベース（図示せず）に格納することができる。したがって、ステップＳ３１０において、メッシュ・モデルのメッシュ・データは、データベースから取得することができる。
【００３４】
ステップＳ３２０において、あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって元のメッシュ・モデルの頂点データから、派生メッシュ・モデルが構築される。
【００３５】
従来の技術には、様々なメッシュ・モデル構築アルゴリズムがある。これらのアルゴリズムは、入力として頂点の集合を用いて派生メッシュ・モデルを推論的に計算することができるように設計される。ドロネー三角形分割アルゴリズム（Delaunay Triangulation Algorithm）はこのようなアルゴリズムである。他の同様のアルゴリズムは、例えば「A New Voronoi-Based Surface Reconstruction Algorithm」(Amenta et al., SIGGRAPH 1998)および「PoissonSurface Reconstruction」(Kazhdan et al, Symposium onGeometry Processing 2006)に見つけることができる。これらのアルゴリズムから、あるアルゴリズムをあらかじめ定義されたメッシュ・モデル構築アルゴリズムとなるように決定することができる。
【００３６】
本発明の一実施形態によれば、ステップＳ３２０においてドロネー三角形分割アルゴリズムを選択することができる。
【００３７】
ドロネー三角形分割アルゴリズムは、頂点の集合から頂点間の空間幾何学的関係に基づいて、頂点間に辺を生成することができ、それによって三角形面の集合を構築し、ひいては目標とするメッシュ・モデルを構築することができる。詳細には、ドロネー三角形分割アルゴリズムは、各三角形面の３つの内角の最小の値を最大にしようと試みることによって、間に接続線が存在する頂点を推論的に計算することができる。ほとんどの場合、ドロネー三角形分割アルゴリズムは、細く、長すぎる形状の三角形（例えば、内角の少なくとも１つが１０度未満である三角形）を生成しない。いくつかの文献に開示された実験結果から、多数の頂点の場合、ドロネー三角形分割アルゴリズムは、頂点の間の辺について比較的正確な推測を行うことができることがわかる。
【００３８】
図２に示すメッシュ・モデル２３０を例にとる。メッシュ・モデル、すなわち派生メッシュ・モデルは、入力としてメッシュ・モデル２３０の頂点集合ＶＳ＝｛ｖ１，ｖ２，ｖ３，ｖ４，ｖ５，ｖ６，ｖ７，ｖ８，ｖ９，ｖ１０｝を用いてドロネー三角形分割アルゴリズムを使用して構築することができる。派生メッシュ・モデルは、図４に参照符号Ｍｋで示す。
【００３９】
図４に示すように、派生メッシュ・モデルＭｋは、正確にはメッシュ・モデル２３０と同じではないが、メッシュ・モデル２３０との一定の類似性を有する。例えば、派生メッシュ・モデルＭｋについては、頂点ｖ１と頂点ｖ６との間の辺、および頂点ｖ７と頂点ｖ８との間の辺があるが、メッシュ・モデル２３０については、頂点ｖ１と頂点ｖ６との間に辺はなく、また頂点ｖ７と頂点ｖ８との間に辺はない。また、メッシュ・モデル２３０については、頂点ｖ３と頂点ｖ４との間の辺、および頂点ｖ６と頂点ｖ９との間の辺があるが、派生メッシュ・モデルＭｋについては、頂点ｖ３と頂点ｖ４との間に辺（点線で示す）はなく、また頂点ｖ６と頂点ｖ９との間に辺（点線で示す）はない。
【００４０】
ステップＳ３３０において、元のメッシュ・モデルのメッシュ・データおよび派生メッシュ・モデルのメッシュ・データを比較して、派生メッシュ・モデルのエラー・データを取得する。
【００４１】
元のメッシュ・モデルのメッシュ・データは、元のメッシュ・モデルを定義するためのデータであり、例えば頂点データおよび辺データ／面データである。派生メッシュ・モデルのメッシュ・データは、派生メッシュ・モデルのデータを定義するためのデータであり、例えば頂点データおよび辺データ／面データである。上述のように、ドロネー三角形分割アルゴリズムは推論的アルゴリズムである。アルゴリズムによりメッシュ・モデル２３０の頂点データから構築された派生メッシュ・モデルは、メッシュ・モデル２３０と厳密には同じではない可能性があり、すなわち、派生メッシュ・モデルと元のメッシュ・モデル２３０との間にはいくつかの差異またはエラーがある。
【００４２】
このようなエラーは、元のメッシュ・モデルのメッシュ・データを、派生メッシュ・モデルＭｋのメッシュ・データと比較することによって確認することができる。
【００４３】
本発明の一実施形態によれば、元のメッシュ・モデルのメッシュ・データと派生メッシュ・モデルのメッシュ・データとの上記の比較は、元のメッシュ・モデルの辺データを派生メッシュ・モデルの辺データと比較することを含み、エラー・データは、余分な辺データおよび欠けている辺データを含み、余分な辺データは、派生メッシュ・モデルに存在するが元のメッシュ・モデルには存在しないあらゆる辺を含み、欠けている辺データは、元のメッシュ・モデルに存在するが派生メッシュ・モデルには存在しないあらゆる辺を含む。
【００４４】
例えば、元のメッシュ・モデル２３０の辺データを派生メッシュ・モデルＭｋの辺データと比較することによって、Ｍｋの派生メッシュ・モデルのエラー・データは、次のように取得することができる：
余分な辺データ：頂点ｖ１と頂点ｖ６との間の辺、および頂点ｖ７と頂点ｖ８との間の辺。
欠けている辺データ：頂点ｖ３と頂点ｖ４との間の辺および頂点ｖ６と頂点ｖ９との間の辺。
【００４５】
一般的には、派生メッシュ・モデルの余分な辺データＶ（ｉ，＋ｅ）は、次の式（１）に従って派生メッシュ・モデルの頂点に基づいて表すことができる。
Ｖ（ｉ，＋ｅ）＝｛ｅ（ｉ，１，＋），ｅ（ｉ，２，＋），...ｅ（ｉ，ｐ，＋）｝......(１)
ここで、プラス記号「＋」は「余分」を示し、表現「ｅ（ｉ，１，＋）」は頂点ｉと頂点１との間の余分な辺を示し、...「ｅ（ｉ，ｐ，＋）」は頂点ｉと頂点ｐとの間の余分な辺を示す。言い換えれば、式（１）によって、すべての余分な辺は、派生メッシュ・モデルの頂点ｉの隣接辺から示すことができる。
【００４６】
例えば、元のメッシュ・モデル２３０では、頂点ｖ１の隣接辺は、頂点ｖ１と頂点ｖ２との間、頂点ｖ３との間、および頂点ｖ４との間の辺ｅ１、辺ｅ２、辺ｅ３をそれぞれ含む。派生メッシュ・モデルＭｋの頂点ｖ１については、さらに隣接辺、すなわち頂点ｖ１と頂点ｖ６との間の辺がある。したがって、頂点ｖ１と頂点ｖ６との間の辺は余分な辺である。余分な辺は、余分な辺データＶ（１，＋ｅ）において「｛ｅ（１，６，＋）｝」として示すことができる。
【００４７】
同様に、頂点ｖ７と頂点ｖ８との間の辺もまた余分な辺であり、これは余分な辺データＶ（７，＋ｅ）において「｛ｅ（７，８，+) ｝」と示す。
【００４８】
一般的に、ｎ個の頂点（１...ｎ）を有する派生メッシュ・モデルの余分な辺の集合は、ＶＳ１で示され、ここで
ＶＳ１＝｛Ｖ（１，＋ｅ），Ｖ（２，＋ｅ）...Ｖ（ｎ，＋ｅ）｝......（２）
である。
【００４９】
その結果、派生メッシュ・モデルＭｋの余分な辺の集合は：
ＶＳ１＝{｛ｅ（１，６，＋）｝，{ｅ（７，８，＋）}｝
である。
【００５０】
一般的に、派生メッシュ・モデルの欠けている辺データＶ（ｉ，−ｅ）は、次の式（３）により派生メッシュ・モデル中の頂点に基づいて表すことができる。
Ｖ（ｉ，−ｅ）＝｛ｅ（ｉ，１，−）,ｅ（ｉ，２−），…ｅ（ｉ，ｐ−）｝．．．．．．（３）
ここでマイナス記号「−」は、「欠けている」ことを示し、表現「ｅ（ｉ，１，−）」は、頂点ｉと頂点１との間の欠けている辺を示し、...「ｅ（ｉ，ｐ，−）」は、頂点ｉと頂点ｐとの間の欠けている辺を示す。言い換えれば、式（３）によって、派生メッシュ・モデルの頂点ｉの隣接辺から、すべての欠けている辺を示すことができる。
【００５１】
例えば、派生メッシュ・モデルＭｋでは、頂点ｖ３と頂点ｖ４との間の辺はないが、元のメッシュ・モデル２３０では、ｖ３とｖ４との間の辺がある。したがって、派生メッシュ・モデルの頂点ｖ３と頂点ｖ４との間の辺は、欠けている辺であり、これを欠けている辺データＶ（３，−ｅ）において「｛ｅ（３，４，−）｝」と示すことができる。
【００５２】
同様に、派生メッシュ・モデルＭｋの欠けている辺は、頂点ｖ６と頂点ｖ９との間の辺も含み、これを欠けている辺データＶ（６，−ｅ）において「｛ｅ（６，９，−）｝」と示すことができる。
【００５３】
一般的に、ｎ個の頂点(１...ｎ）を有する派生メッシュ・モデルの欠けている辺の集合は、ＶＳ２で示され、ここで
ＶＳ２＝｛Ｖ（１，−ｅ），Ｖ（２，−ｅ）．．．Ｖ（ｎ，−ｅ）｝......(４)
である。
【００５４】
例えば、派生メッシュ・モデルＭｋについては、ＶＳ２＝｛｛ｅ（３，４，-)｝，｛ｅ（６，９，-)｝｝である。
【００５５】
したがって、派生メッシュ・モデルのエラー・データの集合は、ＶＳＥＲＲＯＲ＝ＶＳ１＋ＶＳ２、すなわち
ＶＳＥＲＲＯＲ＝｛Ｖ（１，＋ｅ），Ｖ（２，＋ｅ）．．．Ｖ（ｎ，＋ｅ），Ｖ（１，−ｅ），Ｖ（２，−ｅ）．．．Ｖ（ｎ，−ｅ）｝
である。
【００５６】
例えば、派生メッシュ・モデルＭｋのエラー・データ集合ＶＳＥＲＲＯＲ＝｛｛ｅ（１，６，＋）｝，｛ｅ（７，８，＋）｝，｛ｅ（３，４，−）｝，｛ｅ（６，９，−）｝｝である。
【００５７】
本発明の別の実施形態によれば、元のメッシュ・モデルのメッシュ・データと派生メッシュ・モデルのメッシュ・データとの上記の比較は、元のメッシュ・モデルの面データを派生メッシュ・モデルの面データと比較することを含み、エラー・データは、余分な面データと欠けている面データとを含み、余分な面データは、派生メッシュ・モデルに存在するが元のメッシュ・モデルには存在しないあらゆる面を含み、欠けている面データは、元のメッシュ・モデルに存在するが派生メッシュ・モデルには存在しないあらゆる面を含む。
【００５８】
図２と併せて上述したように、辺データと面データとの間には、一種の等価性がある。先の１つの実施形態で説明したように元のメッシュ・モデルの辺データと派生メッシュ・モデルの辺データとの比較によれば、元のメッシュ・モデルの面データと派生メッシュ・モデルの面データとの比較方法を理解し、エラー・データ、すなわち余分な面データおよび欠けている面データを取得することは困難ではない。
【００５９】
上記のステップＳ３１０〜Ｓ３３０は、ネットワーク２０３を介してターゲット・コンピュータ２０２に送信され、メッシュ・モデルのレンダリングに使用されるデータに行われる前処理である。明らかに、前処理は、いかなる時および処理においても行うことができる。前処理の結果を、格納することができる。
【００６０】
上記の前処理が行われ、前処理の結果が格納された後、データは、ネットワーク２０３を介して受信側２０２に送信することができる。
【００６１】
ネットワークを介して受信側２０２にデータを送信するとき、まずステップＳ３４０が行われる。
【００６２】
ステップ３４０において、元のメッシュ・モデルに関連する頂点データが送信される。
【００６３】
本発明の一実施形態によれば、元のメッシュ・モデルに関連する頂点データは、頂点の集合ＶＳ＝｛ｖ１，ｖ２，ｖ３，ｖ４，ｖ５，ｖ６，ｖ７，ｖ８，ｖ９，ｖ１０｝のような、元のメッシュ・モデルの頂点データである。
【００６４】
あるいは、元のメッシュ・モデルに関連する頂点データは、元のメッシュ・モデルの頂点データから導出された頂点データであることもある。
【００６５】
本発明の一実施形態によれば、導出頂点データは、ステップ３４０の前に元のメッシュ・モデルの頂点データに基づいて生成することができる。
【００６６】
したがって、ステップ３４０において、元のメッシュ・モデルに関連する頂点データは、導出頂点データであることもある。
【００６７】
次に図５〜７を参照して、導出頂点データを生成する方法について説明する。図５〜７は、元のメッシュ・モデルに関連する頂点データを概略的に示す。図５は、元のメッシュ・モデルの頂点集合ＶＳを示す。図に示すように、図５の点線ブロック中に示す頂点は、量および幾何学的位置に関して図２のメッシュ・モデル２３０の頂点と同じである。
【００６８】
本発明の１つの実施形態によれば、頂点集合は、いくつかの部分集合、すなわち、ＶＳ＿１、ＶＳ＿２、．．．ＶＳ＿ｘ（ｘ＞１）に分けることができる。部分集合のそれぞれに含まれる頂点データは、導出頂点データ、さら削減頂点データである。例えば、頂点集合ＶＳは、２つの部分集合、ＶＳ＿１＝｛ｖ３，ｖ６，ｖ７｝と、ＶＳ＿２＝ＶＳ−ＶＳ＿１とに分けられる。図６の点線ブロック中の頂点は、頂点部分集合ＶＳ＿２に含まれる頂点を表す。図５と比べると、図６の点線ブロックには頂点ｖ３、ｖ６、およびｖ７がない、すなわち頂点部分集合ＶＳ＿２は、頂点ｖ３、ｖ６、およびｖ７を含まない。
【００６９】
元のメッシュ・モデルの頂点集合が非常に大きく、帯域幅が不十分であるという状況下では、１つの頂点部分集合の頂点データ、例えば部分集合ＶＳ＿２の頂点データをまず送信することができる。次に、他の頂点部分集合の頂点データ、例えば部分集合ＶＳ＿１の頂点データを送信することができる。
【００７０】
本発明の一実施形態によれば、元のメッシュ・モデルの頂点集合ＶＳが非常に大きい場合、頂点集合ＶＳ中の頂点をクラスタリングし、生成された頂点集合のデータを、派生頂点データとして使用することができる。この派生頂点データは、削減頂点データである。例えば、図７は、頂点集合ＶＳ中の頂点のクラスタリングの結果として生成された、導出頂点データを示す。図７を図５と比較すると、図５では、頂点ｖ３、ｖ６、およびｖ７が、図４Ｄの点線ブロック中の頂点Ｖｃｌに削減されていることがわかり、頂点Ｖｃｌは頂点ｖ３、ｖ６、およびｖ７をクラスタリングした結果として生成された頂点であることを意味する。クラスタリングにより生成された頂点Ｖｃｌならびにクラスタリング前の頂点ｖ３、ｖ６、およびｖ７は、マッピング関係を有する、すなわちＶｃｌ＜−＞｛ｖ３，ｖ６，ｖ７｝である。マッピング関係もまた、一種の導出頂点データであり、元のメッシュ・モデルに関連する頂点データに属する。
【００７１】
元のメッシュ・モデルの頂点集合が大きく、帯域幅が不十分である場合、図７に示す導出頂点データ、すなわち｛ｖ１，ｖ２，ｖ４，ｖ５，ｖ８，ｖ９，ｖ１０，Ｖｃｌ｝をまず送信することができる。ターゲット・コンピュータは、図７に示す導出頂点データに基づいて３Ｄグラフィックスをレンダリングすることができる。次に、マッピング関係、すなわちＶｃｌ＜−＞｛ｖ３，ｖ６，ｖ７｝が送信される。ターゲット・コンピュータは、その後に受信されたマッピング関係Ｖｃｌ＜−＞｛ｖ３，ｖ６，ｖ７｝に従って頂点データをＶＳであると判断し、ＶＳに従って３Ｄグラフィックスを表示することができる。このようにして、三次元グラフィックスをプログレッシブに表示することができる。
【００７２】
元のメッシュ・モデル関連の頂点データは、ステップ３４０において送信され、ターゲット・コンピュータ２０２によって使用されて、三次元メッシュ・モデルを表示することができる。これについては、図８と併せて以下の記述でさらに説明する。
【００７３】
次に、ステップＳ３５０において、派生メッシュ・モデルＭｋのエラー・データが送信される。例えば、派生メッシュ・モデルＭｋのエラー・データ集合、すなわちＶＳＥＲＲＯＲ＝｛｛ｅ（１，６，＋）｝，｛ｅ（７，８，＋）｝，｛ｅ（３，４，−）｝，｛ｅ（６，９，−）｝｝が送信されることがある。
【００７４】
本発明の一実施形態によれば、派生メッシュ・モデルのエラー・データを送信することは、エラー・データを複数のエラー・データ部分集合に分割することと、エラー・データ部分集合のすべてが送信されるまで、毎回、エラー・データ部分集合の１つを送信することとを含む。
【００７５】
例えば、派生メッシュ・モデルのエラー・データ集合ＶＳＥＲＲＯＲは、次のようにいくつかのエラー・データ部分集合に分割することができる：
{Ｖ（１，＋ｅ），Ｖ（２，＋ｅ），Ｖ（１，−ｅ），Ｖ（２，−ｅ）｝
{Ｖ（３，＋ｅ），Ｖ（４，＋ｅ），Ｖ（３，−ｅ），Ｖ（４，−ｅ）｝
...
{Ｖ（ｎ−１，＋ｅ），Ｖ（ｎ，＋ｅ），Ｖ（ｎ−１，−ｅ）．．．Ｖ（ｎ，−ｅ）｝
【００７６】
エラー・データ部分集合のすべてが送信されるまで、毎回、エラー・データ部分集合の１つが送信される。
【００７７】
例えば、エラー・データ部分集合ＶＳＥＲＲＯＲ＝｛｛ｅ（１，６，＋）｝，｛ｅ（７，８，＋）｝，｛ｅ（３，４，−）｝，｛ｅ（６，９，−）｝｝は、２つのエラー・データ部分集合：｛｛ｅ（１，６，＋）｝，｛ｅ（３，４，−）｝｝および｛｛ｅ（６，９，−）｝，｛ｅ（７，８，＋）｝｝に分割することができる。次に、２つのエラー・データ部分集合は、それぞれ送信される。
【００７８】
上記の２つのエラー・データ部分集合は単に例であることに注意すべきである。実際の適用例では、各エラー・データ部分集合のデータ量は、例のデータ量よりもはるかに多い。しかしながら、個々のエラー・データ部分集合のデータ量は、エラー・データ集合ＶＳＥＲＲＯＲのデータ量よりも少ない。ネットワーク２０３の帯域幅が不十分である場合、ソース・コンピュータ２０１が帯域幅の状態に従ってより少ないデータ量のエラー・データ部分集合を送信すると、エラー・データ集合は適時にターゲット・コンピュータ２０２に到着することができる。
【００７９】
ステップＳ３５０において送信されたエラー・データは、三次元メッシュ・モデルをレンダリングするためにターゲット・コンピュータ２０２によって使用されることが可能である。
【００８０】
以下に、図８を参照して、元のメッシュ・モデルに関連する頂点データおよびソース・コンピュータ２０１から送信された派生メッシュ・モデルのエラー・データに対してそれぞれターゲット・コンピュータ２０２によって行われる処理について説明する。
【００８１】
図８は、本発明の一実施形態に従って三次元メッシュ・モデルをプログレッシブに表示するための方法のフロー・チャートを示す。図８に示す方法は、ターゲット・コンピュータ２０２で実行することができる。続いて処理が行われる。
【００８２】
ステップＳ５１０において、三次元モデルのデータが、ネットワーク２０３を介してソース・コンピュータ２０１から受信される。
【００８３】
図３と併せた上記の説明から、ソース・コンピュータ２０１からターゲット・コンピュータ２０２に送信されるデータは、元のメッシュ・モデルに関連する頂点データであることがあり（ステップＳ３４０）、導出メッシュ・モデルのエラー・データであることもある（ステップＳ３５０）ことがわかる。
【００８４】
ステップＳ５２０において、ターゲット・コンピュータ２０２は、対応する処理を行うために受信データの型を判断する。データの型を判断を実施する様々な方法がある。例えば、単純な方法は、送信側によって送信されるデータの型を区別するためにデータ型を示す識別子を設定することである。
【００８５】
受信データの様々な型に応じて、ターゲット・コンピュータ２０２は様々な処理を行うことになる。本発明の一実施形態によれば、プリズム・ブロック５２１および５２２にそれぞれ示すように、受信側は、単に頂点データおよびエラー・データの処理を行うことを要求される。
【００８６】
受信データが元のメッシュ・モデルに関連する頂点データであることに応じて、ステップＳ５３０において以下の動作が行われる：
あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって元のメッシュ・モデルの頂点データから、派生メッシュ・モデルを構築することと、
構築された派生メッシュ・モデルに基づいて、三次元モデルを表示すること。
【００８７】
本発明の一実施形態によれば、あらかじめ定義されたメッシュ・モデル構築アルゴリズムは、ドロネー三角形分割アルゴリズムとすることができる。
【００８８】
あらかじめ定義されたモデル構築アルゴリズムは、ソース・コンピュータ２０２によって使用されるメッシュ・モデル構築アルゴリズムと同じものであるべきである。実際には、あらかじめ定義されたメッシュ・モデル構築アルゴリズムは、ターゲット・コンピュータ上で展開されるメッシュ・モデル構築アルゴリズムとすることができ、これはあらかじめ指定される。ターゲット・コンピュータ上で様々なメッシュ・モデル構築アルゴリズムが展開される場合、ソース・コンピュータからの通知に基づいていかなる時でもメッシュ・モデル構築アルゴリズムの１つを選択することもできる。
【００８９】
図３と併せて上述した説明では、あらかじめ定義されたメッシュ・モデル構築アルゴリズムを用いて辺データまたは面データを生成する方法を説明した。
【００９０】
図３と併せて上述したステップ３４０についての説明では、ステップＳ３４０で送信される元のメッシュ・モデルに関連する頂点データは、元のメッシュ・モデルの頂点データ、または導出頂点データとすることができることが指摘されている。
【００９１】
本発明の一実施形態によれば、元のメッシュ・モデルに関連する頂点データは、元のメッシュ・モデル２３０の頂点データ、すなわち頂点の集合ＶＳ＝｛ｖ１，ｖ２，ｖ３，ｖ４，ｖ５，ｖ６，ｖ７，ｖ８，ｖ９，ｖ１０｝である。この場合、頂点集合ＶＳに従って、図４に示す派生メッシュ・モデルＭｋが構築される。次に、三次元メッシュ・モデルは、派生メッシュ・モデルＭｋのデータに従って表示される。
【００９２】
本発明の一実施形態によれば、元のメッシュ・モデルに関連する頂点データは、例えば上述の図６または７に示す導出頂点データのような、導出頂点データである。この場合、派生メッシュ・モデルＭｋは、図６または７に示す頂点集合に従って構築されることも可能である。次に、三次元メッシュ・モデルは、派生メッシュ・モデルＭｋのデータに従って表示される。
【００９３】
ステップ５３０の後、処理はステップＳ５１０に戻ってデータの受信を続ける。
【００９４】
受信データが派生メッシュ・モデルのエラー・データであることに応じて、現在表示されている三次元メッシュ・モデルは、ステップＳ５４０において受信したエラー・データで修正される。
【００９５】
上記で図３と併せて述べたように、派生メッシュ・モデルのエラー・データは、次のうちの少なくとも１つ、すなわち、余分な辺データ、欠けている辺データ、余分な面データ、および欠けている面データのうちの少なくとも１つを含む。
【００９６】
本発明の一実施形態によれば、エラー・データが余分な辺データを含むことに応じて、余分な辺データ中の辺は、現在表示されている三次元メッシュ・モデルから削除される。エラー・データが欠けている辺データを含むことに応じて、欠けている辺データ中の辺は、現在表示されている三次元メッシュ・モデルに追加される。エラー・データが余分な面データを含むことに応じて、余分な面データ中の面は、現在表示されている三次元メッシュ・モデルから削除される。また、エラー・データが欠けている面データを含むことに応じて、欠けている面データ中の面は、現在表示されている三次元メッシュ・モデルに追加される。
【００９７】
派生メッシュ・モデルのエラー・データは、派生メッシュ・モデルのメッシュ・データと元のメッシュ・モデルのメッシュ・データとの差異を表すデータ、または派生メッシュ・モデルのメッシュ・データと元のメッシュ・モデルのメッシュ・データとの差異を表すデータの部分集合、すなわちエラー・データの部分集合であることが可能である。
【００９８】
図９〜１１を参照すると、これらはターゲット・コンピュータ２０２において三次元メッシュ・モデルをレンダリングする処理を概略的に示している。例えば図４に示す派生メッシュ・モデルＭｋが、ステップ５３０において頂点集合ＶＳに基づいて構築されると仮定する。その後、三次元メッシュ・モデルは、派生メッシュ・モデルＭｋのデータに従って表示される。図９は、現在表示されている三次元メッシュ・モデルを示す。
【００９９】
図３を参照して先に説明したように、例えばメッシュ・モデルＭｋから導出されるエラー・データは、ＶＳＥＲＲＯＲ＝｛｛ｅ（１，６，＋）｝，｛ｅ（７，８，＋）｝，｛ｅ（３，４，−）｝，｛ｅ（６，９，−）｝｝である。すなわち、現在表示されている三次元メッシュについて、頂点ｖ１と頂点ｖ６との間の辺、頂点ｖ７と頂点ｖ８との間の辺は、余分な辺である。頂点ｖ３と頂点ｖ４との間の辺、および頂点ｖ６と頂点ｖ９との間の辺は、欠けている辺である。
【０１００】
エラー・データＶＳＥＲＲＯＲは、２つのエラー・データ部分集合、すなわち{｛ｅ（１，６，＋）｝，｛ｅ（３，４，−）｝}と、｛{ｅ（６，９，−）}，{ｅ（７，８，＋）}}とに分割されると仮定する。
【０１０１】
ステップＳ５１０において受信されたデータがエラー・データ部分集合｛{ｅ（１，６，＋）}，{ｅ（３，４，−）}｝である場合、ステップＳ５４０において、頂点ｖ１と頂点ｖ６との間の辺は、図９に示す、現在表示されている三次元メッシュ・モデルから削除されることになり、頂点ｖ３と頂点ｖ４との間の辺が追加されることになる。結果は、図１０に示す通りである。
【０１０２】
ステップ５４０の後に、処理はステップＳ５１０に戻る。
【０１０３】
次に、ステップＳ５１０で受信されたデータは、エラー・データ部分集合｛｛ｅ（６，９，−）｝，｛ｅ（７，８，＋）｝｝である。したがって、ステップＳ５４０において、頂点ｖ７と頂点ｖ８との間の辺は、図１０に示す、現在表示されている三次元メッシュ・モデルから削除されることになり、頂点ｖ６と頂点ｖ９との間の辺は追加される。結果は、図１１に示す通りである。
【０１０４】
上記において、本発明の実施形態に従って、三次元モデルのメッシュ・データを処理するための方法、および三次元モデルをプログレッシブにレンダリングするための方法を説明している。同じ発明の概念によれば、本発明はまた、三次元モデルのメッシュ・データを処理する装置、および三次元モデルをプログレッシブにレンダリングするための装置を提供する。
【０１０５】
図１２を参照すると、この図は、本発明の一実施形態により三次元モデルのメッシュ・データを処理するための装置のブロック図を概略的に示している。
【０１０６】
一般的に、図１２に示す装置は、データ取得ユニット７１０と、メッシュ・モデル構築ユニット７２０と、比較ユニット７３０と、頂点データ送信ユニット７４０と、エラー・データ送信ユニット７５０とを含む。
【０１０７】
データ取得ユニット７１０は、元のメッシュ・モデルのメッシュ・データを取得するように構成される。
【０１０８】
メッシュ・モデル構築ユニット７２０は、あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって、元のメッシュ・モデルの頂点データから派生メッシュ・モデルを構築するように構成される。
【０１０９】
比較ユニット７３０は、元のメッシュ・モデルのメッシュ・データを派生メッシュ・モデルのメッシュ・データと比較して、派生メッシュ・モデルのエラー・データを取得するように構成される。
【０１１０】
頂点データ送信ユニット７４０は、元のメッシュ・モデルに関連する頂点データを送信するように構成される。
【０１１１】
エラー・データ送信ユニット７５０は、派生メッシュ・モデルのエラー・データを送信するように構成される。
【０１１２】
本発明の一実施形態によれば、あらかじめ定義されたメッシュ・モデル構築アルゴリズムは、ドロネー三角形分割アルゴリズムを含む。
【０１１３】
本発明の一実施形態によれば、比較ユニット７３０は、元のメッシュ・モデルの辺データを派生メッシュ・モデルの辺データと比較するように構成され、エラー・データは、余分な辺データおよび欠けている辺データを含み、余分な辺データは、派生メッシュ・モデルに存在するが元のメッシュ・モデルには存在しないあらゆる辺を含み、欠けている辺データは、元のメッシュ・モデルに存在するが派生メッシュ・モデルには存在しないあらゆる辺を含む。
【０１１４】
本発明の一実施形態によれば、比較ユニット７３０は、元のメッシュ・モデルの面データを派生メッシュ・モデルの面データと比較するように構成され、エラー・データは、余分な面データおよび欠けている面データを含み、余分な面データは、派生メッシュ・モデルに存在するが元のメッシュ・モデルには存在しないあらゆる面を含み、欠けている面データは、元のメッシュ・モデルに存在するが派生メッシュ・モデルには存在しないあらゆる面を含む。
【０１１５】
本発明の一実施形態によれば、エラー・データ送信ユニット７５０は、エラー・データを複数のエラー・データ部分集合に分割し、エラー・データ部分集合のすべてが送信されるまで、毎回、エラー・データ部分集合の１つを送信するように構成される。
【０１１６】
次に図１３を参照すると、この図は、本発明の別の実施形態により三次元モデルのメッシュ・データを処理するための装置のブロック図を概略的に示している。
【０１１７】
一般に、図８に示す装置は、データ受信ユニット８１０と、データ型判断ユニット８２０と、メッシュ・モデル構築ユニット８３０と、３Ｄモデル・レンダリング・ユニット８４０とを含む。
【０１１８】
データ受信ユニット８１０は、三次元メッシュ・モデルをレンダリングするためにデータを受信するように構成される。
【０１１９】
データ型判断ユニット８２０は、データ受信ユニットによって受信されたデータの型を判断するように構成される。
【０１２０】
メッシュ・モデル構築ユニット８３０は、受信データが元のメッシュ・モデルに関連する頂点データであることに応じて、あらかじめ定義されたメッシュ・モデル構築アルゴリズムを使用することによって、元のメッシュ・モデルの頂点データから派生メッシュ・モデルを構築するように構成される。
【０１２１】
本発明の一実施形態によれば、元のメッシュ・モデルに関連する頂点データは、次のうちの１つ、すなわち元のメッシュ・モデルの頂点データ、元のメッシュ・モデルの頂点データから導出された頂点データのうちの１つを含む。
【０１２２】
３Ｄモデル・レンダリング・ユニット８４０は、構築された派生メッシュ・モデルを表示するように構成され、３Ｄモデル・レンダリング・ユニットはさらに、受信データが派生メッシュ・モデルのエラー・データであることに応じて、受信エラー・データを用いて、表示されている三次元メッシュ・モデルを修正するように構成される。
【０１２３】
本発明の一実施形態によれば、あらかじめ定義されたメッシュ・モデル構築アルゴリズムは、ドロネー三角形分割アルゴリズムを含む。
【０１２４】
本発明の一実施形態によれば、エラー・データは、次のうちの少なくとも１つ、すなわち、余分な辺データ、欠けている辺データ、余分な面データ、および欠けている面データのうちの少なくとも１つを含む。３Ｄモデル・レンダリング・ユニット８４０は、エラー・データが余分な辺データを含んでいることに応じて、現在表示されている三次元メッシュ・モデルから余分な辺データの辺を削除し、エラー・データが欠けている辺データを含んでいることに応じて、現在表示されている三次元メッシュ・モデルに欠けている辺データの辺を追加し、エラー・データが余分な面データを含んでいることに応じて現在表示されている三次元メッシュ・モデルから余分な面データの面を削除し、エラー・データが欠けている面データを含んでいることに応じて、現在表示されている三次元メッシュ・モデルに欠けている面データの面を追加するように構成される。
【０１２５】
本発明の諸実施形態により三次元モデルを処理するための装置について、上述している。本発明のＩＤ連携（identity federation）構成を構成するための方法の諸実施形態の詳細な説明を前の節で行っているが、上記における装置の説明は、繰り返しの内容、または方法の説明から容易に導き出すことができる内容を省略している。
【０１２６】
上記の説明は、単に例示であり、本発明を限定することを目的としていないことに注意すべきである。本発明の他の実施形態では、この方法はより多くのステップ、またはより少ないステップ、または異なるステップを有する可能性があり、ステップを番号付けするのは、単に説明をより簡潔に、さらに明確にするためであって、各ステップ間の順序を厳密に限定するためではなく、諸ステップの順序は、説明とは異なる可能性がある。
【０１２７】
したがって、いくつかの実施形態では、上記の１つまたは複数のオプションのステップを省略することができる。各ステップの特定の実施形態は、説明とは異なる可能性がある。これらの変形はすべて、本発明の趣旨および範囲に含まれる。
【０１２８】
本発明は、ハードウェアの実施形態、ソフトウェアの実施形態、またはハードウェア構成要素とソフトウェア構成要素とを含む実施形態の形を採用することができる。好ましい実施形態では、本発明は、これらに限定ではないが、ファームウェア、常駐ソフトウェア、マイクロコードなどを含む、ソフトウェアとして実装される。
【０１２９】
さらに、本発明は、コンピュータから利用できる、あるいはコンピュータもしくは任意の命令実行システムによって、またはこれらと接続して使用するためのプログラム・コードを提供するコンピュータ可読媒体によってアクセスできる、コンピュータ・プログラム製品として実装されることが可能である。説明のために、コンピュータ使用可能媒体またはコンピュータ可読媒体は、命令実行システム、装置、またはデバイスによって、あるいはこれらと接続して使用するためのプログラムを収容する、格納する、伝達する、伝搬するまたは搬送することができるいかなる有形手段とすることもできる。
【０１３０】
媒体は、電気、磁気、光、電磁気、赤外線、または半導体のシステム（装置もしくはデバイス）、もしくは伝搬媒体とすることができる。コンピュータ可読媒体の例には、半導体またはソリッド・ストレージ・デバイス、磁気テープ、ポータブル・コンピュータ・ディスケット、ランダム・アクセス・メモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）、ハード・ディスク、および光ディスクが含まれる。現在の光ディスクの例には、コンパクト・ディスク読取り専用メモリ（ＣＤ−ＲＯＭ）、コンパクト・ディスク読取り／書込み（ＣＤ−Ｒ／Ｗ）、およびＤＶＤが含まれる。
【０１３１】
プログラム・コードを格納する、または実行するように適合されたデータ処理システムは、直接に、またはシステム・バスを介して、メモリ素子に結合された少なくとも１つのプロセッサを含む。メモリ素子は、プログラム・コードを実際に実行中に利用できるローカル・メモリ、大容量メモリ、および実行中に大容量メモリからコードを検索するための回数を減らすためにプログラム・コードの少なくとも一部に対して一次記憶装置を提供するキャッシュを含むことができる。
【０１３２】
入力／出力すなわちＩ／Ｏ装置（キーボード、ディスプレイ、ポインティング・デバイスなどを含むが、これらに限らない）は、直接に、または中間Ｉ／Ｏコントローラを介して、システムに接続することができる。
【０１３３】
本発明の真の趣旨から逸脱することなく、本発明のそれぞれの実施形態に対して変更および改変を行うことができることを、前述の説明から理解されたい。本明細書中の説明は、例示となることを目的としており、限定するものではない。本発明の範囲は、添付の特許請求の範囲によってのみ限定される。
【０１３４】
本発明の真の趣旨から逸脱することなく、本発明のそれぞれの実施形態に対して変更および改変を行うことができることを、前述の説明から理解されたい。本明細書中の説明は、例示となることを目的としており、限定するものではない。本発明の範囲は、添付の特許請求の範囲によってのみ限定される。
【図１】
2015507797.tif 000003
【図３】
2015507797.tif 000004
【図４】
2015507797.tif 000005
【図５】
2015507797.tif 000006
【図６】
2015507797.tif 000007
【図７】
2015507797.tif 000008
【図８】
2015507797.tif 000009
【図９】
2015507797.tif 000010
【図１０】
2015507797.tif 000011
【図１１】
2015507797.tif 000012
【図１２】
2015507797.tif 000013
【図１３】
2015507797.tif 000014
【図２】
2015507797.tif 000015
【国際調査報告】
2015507797.tif 000016
2015507797.tif 000017