(57)【要約】  本発明は、幾何学モデルを単純化する方法に関し、この方法は、現在のポイントに関連付けられたMortonコードよりも低く関連付けられたMortonコードを有する複数のポイントに関連付けられた誤差測定結果の総和の関数として定義される積分誤差評価QSiの判定(607)と、複数のポイントの所与のセットが、新たなポイントによって単純化されるか否かの判定(614)であって、所与のセットすべてのポイントが、少なくとも、最大のMortonコード(las)を有する所与のセットのポイントのために判定された積分誤差測定結果QSlasと、セットのポイントに関連付けられたMortonコードのうち、最小のMortonコードの次に低いMortonコードを有する複数のポイントのために判定された積分誤差測定結果QSini-1との差分の関数として、所与の長さのうちの1つまたは同じプレフィクスに関連付けられたMortonコードを有する複数のポイントである、判定(614)とを備える。
2018518747.tif 000002
【特許請求の範囲】
【請求項１】
幾何学モデルを単純化する方法であって、
(a)複数のポイント(pi)を備える前記幾何学モデルの受信(601)であって、前記複数の各ポイントは、誤差評価(Qi)に関連付けられる、受信と、
(b)前記幾何学モデルの各現在のポイント(pi)について、
-  前記現在のポイントの座標の関数(Qi)として、前記現在のポイント(pi)に関連付けられたMortonコードの判定(602)、および
-  前記現在のポイントに関連付けられた前記Mortonコードよりも低く関連付けられたMortonコードを有する前記複数のポイントに関連付けられた誤差評価の総和の関数として定義される積分誤差評価
【数１】
2018518747.tif 000047
の判定(607)と、
(c)前記複数のポイントの所与のセットが、新たなポイントによって単純化され得るか否かの判定(614)であって、前記所与のセットすべてのポイントが、少なくとも、
-  最大のMortonコード(las)を有する前記所与のセットのポイントのために判定された前記積分誤差評価
【数２】
2018518747.tif 000048
と、
-  前記セットのポイントに関連付けられた前記Mortonコードのうち、最小のMortonコードの次に低いMortonコード(ini-1)を有する前記複数のポイントのために判定された前記積分誤差評価
【数３】
2018518747.tif 000049
との差分の関数として、同じ所与の長さのプレフィクスに関連付けられたMortonコードを有する前記複数のポイントである、判定と、を備える方法。
【請求項２】
前記複数の現在のポイント(pi)に関連付けられた前記誤差評価(Qi)が、頂点のうちの少なくとも1つが前記現在のポイントであるか、または、前記現在のポイントからあらかじめ決定された距離未満の距離にあるモデルの面を表す2次式の関数である、請求項1に記載の方法。
【請求項３】
前記複数の現在のポイント(pi)に関連付けられた前記誤差評価(Qi)が、頂点のうちの少なくとも1つが前記現在のポイントであるモデルの前記面の色の関数である、請求項1または2に記載の方法。
【請求項４】
前記複数の現在のポイント(pi)に関連付けられた前記誤差評価(Qi)が、前記現在のポイントに関連付けられた法線ベクトルを表す2次式の関数である、請求項1から3のいずれか一項に記載の方法。
【請求項５】
前記方法はさらに、
-  複数の第1のポイントが、複数の第2のポイントと同一のMortonコードに関連付けられているのであれば、前記複数のポイントからの前記第2のポイントの削除(604)を備える、請求項1から4のいずれか一項に記載の方法。
【請求項６】
前記新たなポイントは、前記セットのポイントの関数
【数４】
2018518747.tif 000050
である、請求項1から5のいずれか一項に記載の方法。
【請求項７】
前記新たなポイントは、前記差分の関数である値の最小化
【数５】
2018518747.tif 000051
によって判定される、請求項1から6のいずれか一項に記載の方法。
【請求項８】
前記方法はさらに、
-  Mortonコーディングに基づくk-dツリーの判定(605)を備え、前記ツリーは、前記複数のポイントをリーフ(201、202、203、204、205、206)として有する、請求項1から7のいずれか一項に記載の方法。
【請求項９】
前記k-dツリーは、内部ノード(207、208、209、210、211)を有し、各内部ノード(207、208、209、210、211)は、ポイント(p)に関連付けられ、
前記ステップ(c)における判定はまた、前記ポイントおよび前記ポイントの置換の関数である、請求項8に記載の方法。
【請求項１０】
各現在のポイントの前記積分誤差評価
【数６】
2018518747.tif 000052
は、
-  前記現在のポイントの前記Mortonコードの次に低いMortonコードを有するポイントの前記積分誤差評価
【数７】
2018518747.tif 000053
と、
-  前記現在のポイントの前記誤差評価(Qi)との総和の関数として計算される、請求項1から9のいずれか一項に記載の方法。
【請求項１１】
幾何学モデルの単純化のためのデバイスであって、
(a)複数のポイントを備える前記幾何学モデルを受信するためのインターフェース(903)であって、前記複数の各ポイントは、誤差評価に関連付けられる、インターフェースと、
(b)前記幾何学モデルの各現在のポイントについて、
-  前記現在のポイントの座標の関数として、前記現在のポイントに関連付けられたMortonコードの判定、および
-  前記現在のポイントに関連付けられた前記Mortonコードよりも低く関連付けられたMortonコードを有する前記複数のポイントに関連付けられた前記誤差評価の総和の関数として定義される積分誤差評価の判定のために適切な回路(904)と、
(c)前記複数のポイントの所与のセットが、新たなポイントによって単純化され得るか否かの判定のために適切な回路(904)であって、前記所与のセットすべてのポイントが、少なくとも、
-  最大のMortonコードを有する前記所与のセットのポイントのために判定された前記積分誤差評価と、
-  前記セットのポイントに関連付けられた前記Mortonコードのうち、最小のMortonコードの次に低いMortonコードを有する前記複数のポイントのために判定された前記積分誤差評価との差分の関数として、同じ所与の長さのプレフィクスに関連付けられたMortonコードを有する前記複数のポイントである、回路とを備える、デバイス。
【請求項１２】
1つまたは複数のプロセッサによってプログラムが実行された場合、請求項1から10のいずれか一項に記載の方法を実施するための命令を備えたコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オブジェクトモデリングの分野に関し、特に、3次元でモデル化されたオブジェクトのための幾何学モデル(たとえば、メッシュまたはポイントクラウド)の単純化の分野に関する。
【背景技術】
【０００２】
実際のオブジェクトに基づいてオブジェクトを3次元でモデル化した場合、取得されるポイントモデルまたはメッシュモデル(たとえば、三角形の面)は、オブジェクトの幾何学を複雑な詳細で表すために、非常に多くの数(たとえば、数百万の面/三角形)で存在し得る。
【０００３】
これら実際のオブジェクトの3次元モデリング(3D)は、特に、3Dスキャナを使用した技術の支援を用いて実行され得る。3Dスキャナは、オブジェクトの形状および恐らくはその外観(色、質感等)に関する正確な情報を収集するために、オブジェクトまたはその周囲を分析するデバイスである。これら3次元スキャナは、光(たとえば、レーザ、立体照明、変調光)、超音波、またはX線のような様々な技術を使用し得る。一般大衆のために意図された3Dスキャナの例は、Google TangoタブレットまたはMicrosoft Kinect製品である。任意の光センサは、潜在的な3Dスキャナであり、一連の写真から3D形状を再構築する立体映像プログラムの追加のみを必要とする。
【０００４】
デジタル化されるか、仮想的に生成されるかに関わらず、デジタル3Dオブジェクトは、異なるタイプおよび用途からなり、
-  都市および建築データ(たとえばビルディング)、
-  文化的データ(遺跡発掘現場のスキャン、美術品のスキャン)、
-  シミュレーションからのビックデータ、
-  医療画像から抽出されたデータ、
-  特殊効果をプレビューするような視覚的媒体のためにキャプチャされたデータ、
-  ビデオゲームのためのコンテンツの生成
-  等
を含む。
【０００５】
しかしながら、これらモデリングツールに起因する3Dモデルは、しばしば非常に複雑であり、したがって、非常に取り扱いにくい。(スマートフォンのような)低い計算能力のコンピュータ機器において、これらモデルを操作/ビューすることは複雑とされ得る。それに加えて、(低品質WiFiネットワーク、モバイルネットワークのような)制限されたネットワーク能力は、これら扱いにくいモデルの、即時で便利なダウンロードを阻止し得る。
【０００６】
そのような制約されたコンテキストへこれらモデルを適応させるために、既存の幾何単純化の方法は、主に、2つの大まかな技術カテゴリ、すなわち、
-  反復的単純化アルゴリズム:メッシュ頂点のグループ化またはエッジの省略(Hoppeら、「Mesh optimization」、1993年、または、Garlandら、「Surface simplification using quadric error metrics」、1997年)と、
-  分割アルゴリズム:メッシュの領域への分割(たとえば、Lindstromら、「Out-of-core simplification of large polygonal models」、2000年、または、Cohen-Streinerら、「Variational shape approximation」、2004年)とに基づく。
【０００７】
これらアルゴリズムは比較的遅く、大量のメモリを消費し得る。したがって、これらの大きなモデルへの応用は困難となり得る。それに加えて、いくつかの分割アルゴリズムの場合、アルゴリズムの収束が保証されないことがあり得る。
【０００８】
したがって、3Dモデリングツールによって生成され得る大きく複雑なモデルを、効率的かつ現実的に単純化する必要がある。
【０００９】
それに加えて、モデルをほぼリアルタイムで単純化できるため(たとえば、単純化を求める要求、移動中のモデルの送信のケースでは、高速応答が必要とされる)に、この単純化を非常に迅速に実行する必要もある。
【００１０】
もちろん、この単純化は高速でなければならないが、オリジナルの形状が最もよく保たれるように、単純化されたモデルの品質の低下を可能な限り回避しなければならない。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Hoppeら、「Mesh optimization」、1993年
【非特許文献２】Garlandら、「Surface simplification using quadric error metrics」、1997年
【非特許文献３】Lindstromら、「Out-of-core simplification of large polygonal models」、2000年
【非特許文献４】Cohen-Streinerら、「Variational shape approximation」、2004年
【非特許文献５】DecoroおよびTatarchuk、「Real-time mesh simplification using the gpu」、2007年
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本発明は、この状況を改善する。
【課題を解決するための手段】
【００１３】
この目的のために、本発明は、並列計算のための効率的かつ最適化された幾何学モデルを単純化する方法を提供する。
【００１４】
したがって、本発明は、幾何学モデルを単純化する方法に関し、この方法は、
(a)複数のポイントを備える幾何学モデルの受信であって、複数の各ポイントは、誤差評価に関連付けられる、受信と、
(b)幾何学モデルの各現在のポイントについて、
-  現在のポイントの座標の関数として、現在のポイントに関連付けられたMortonコードの判定、および、
-  現在のポイントに関連付けられたMortonコードよりも低く関連付けられたMortonコードを有する複数のポイントに関連付けられた誤差評価の総和の関数として定義される積分誤差評価の判定と、
(c)複数のポイントの所与のセットが、新たな単一のポイントによって単純化され得るか否かの判定であって、所与のセットすべてのポイントが、少なくとも、
-  最大のMortonコードを有する所与のセットのポイントのために判定された積分誤差評価と、
-  セットのポイントに関連付けられたMortonコードのうち、最小のMortonコードの次に低いMortonコードを有する複数のポイントのために判定された積分誤差評価との差分の関数として、同じ所与の長さのプレフィクスに関連付けられたMortonコードを有する複数のポイントである、判定とを備える。
【００１５】
「幾何学モデル」は、たとえば、メッシュまたはポイントクラウドであり得る。単純化のために、以下では「幾何学モデル」ではなく「メッシュ」という用語が使用される。
【００１６】
しばしば、「誤差評価」は、関数を使用して表され、行列(たとえば、4x4)は、2次式を表す。所与の誤差評価から、誤差値(ε)を計算することが可能である。
【００１７】
もちろん、「より低い」、「最大」、「最小」という用語は、(数学的な意味における)所与の順序関係に従って解釈されるべきである。したがって、この順序関係の意味における「より低い」または「未満」という用語は、「自然な」順序関係(すなわち、我々が慣れている順序関係であり、たとえば、1<2)における「より高い」または「〜を超える」を非常に良く意味し得る。したがって、所与の順序関係は、「自然な」順序関係(すなわち、001100<110101)であり得るか、または、この「自然な」順序関係の逆(すなわち、001100>110101)であり得る。
【００１８】
以下に説明されるように、k-dツリーにおけるポイントのセットに共通である親ノードを識別することによって、ステップ(c)の判定を実行することが可能である。
【００１９】
それに加えて、複数の現在のポイントに関連付けられた誤差評価は、頂点のうちの少なくとも1つが現在のポイントであるか、または、現在のポイントからあらかじめ決定された距離未満の距離にあるモデルの面を表す2次式の関数であり得る。
【００２０】
あらかじめ決定された距離は、面サイズ未満(たとえば、モデルの面のうち、または、モデルにおける近くの面のうち、最小の大きさの30%)として選択され得る。
【００２１】
1つの特定の実施形態では、複数の現在のポイントに関連付けられた誤差評価は、頂点のうちの少なくとも1つが現在のポイントであるモデルの面の色の関数であり得る。
【００２２】
誤差評価を判定する際におけるこの色の考慮は、著しい色変化を有するメッシュのエリアにおける過度の単純化を阻止し得る。
【００２３】
それに加えて、または、その代わりに、複数の現在のポイントに関連付けられた誤差評価は、現在のポイントに関連付けられた法線ベクトルを表す2次式の関数であり得る。
【００２４】
誤差評価を判定する際における法線ベクトルのこの考慮は、小さな振幅(たとえば、髪の毛を含む領域、または、ファイバ構造を含む領域等)からなる著しい幾何学的パターンを有するメッシュのエリアにおける過度の単純化を阻止し得る。
【００２５】
それに加えて、この方法は、
-  複数の第1のポイントが、複数の第2のポイントに同一なMortonコードに関連付けられているのであれば、複数のポイントからの第2のポイントの削除を備え得る。
【００２６】
したがって、メッシュにおける非常に類似したポイントを重複排除することが可能である。確かに、関連付けられたMortonコードは、空間座標の精度よりも低い精度を有し得る(すなわち、Mortonコードのために使用されるビットの数は、座標のおのおののために使用されるビットの数の3倍未満である)。したがって、2つの異なるモデルのポイントは、同じMortonコードを有し得る。
【００２７】
1つの実施形態では、新たなポイントは、セットのポイントの関数であり得る。たとえば、この新たなポイントは、このセットのポイントの(恐らくは、重み付けられた)重心であり得る。
【００２８】
それに加えて、または、その代わりに、新たなポイントは、この差分の関数である値の最小化によって判定され得る。たとえば、差分が2次式Qであり、新たなポイントがpと示されるのであれば、(p,1)TQ(p,1)を最小化することが可能である。この最小化は、反復的(すなわち、最小値に向かって移動するために、pの値を、何度も修正する)、フォーマル(すなわち、最小化方程式を解く)、またはセミフォーマル(最小値に近い結果を与える方程式を解く)でさえもあり得る。
【００２９】
この方法はさらに、
-  Mortonコーディングに基づくk-dツリーの判定であって、ツリーは、複数のポイントをリーフとして有する、判定を備え得る。
【００３０】
そのようなツリーの判定は、上記説明された方法のコンピュータ実施を単純化し、並列処理を用いて、実施を容易にする。この方法は、その後、ツリーにおけるパスによって説明され得る。パスは、スタティックなメモリ割当をサポートするように最適化され得る(たとえば、グループ化されるべきノードのリスト以外にグループ化されるべき、最初(ini)と最後(las)のリーフノードのみを記憶する等)。
【００３１】
したがって、k-dツリーは、内部ノードを有するので、各内部ノードはポイントに関連付けられ得る。ステップ(c)における判定はまた、ポイントの、および、ポイントの置換の関数であり得る。
【００３２】
1つの実施形態では、各現在のポイントの積分誤差評価は、
-  現在のポイントのMortonコードの次に低いMortonコードを有するポイントの積分誤差評価と、
-  現在のポイントの誤差評価との総和の関数として計算され得る。
【００３３】
したがって、各積分誤差評価の計算のために必要な多くの演算は、単一の数学的な演算へ限定される。
【００３４】
現在のポイントのMortonコードの次に低いMortonコードを有するポイントが存在しない(すなわち、現在のポイントが、最小のMortonコードを有する)のであれば、積分誤差評価は単に、現在のポイントの誤差評価である。これは、「現在のポイントのMortonコードの次に低いMortonコードを有するポイントの積分誤差評価」はゼロ要素(「0」と示されるが、恐らくは、ゼロ2次式/行列に対応する)に等しいことを考慮することになる。
【００３５】
本発明はまた、幾何学モデルの効率的な単純化のためのデバイスに関する。このデバイスは、
(a)複数のポイントを備える幾何学モデルを受信するためのインターフェースであって、複数の各ポイントは、誤差評価に関連付けられる、インターフェースと、
(b)幾何学モデルの各現在のポイントについて、
-  現在のポイントの座標の関数として、現在のポイントに関連付けられたMortonコードの判定、および
-  現在のポイントに関連付けられたMortonコードよりも低く関連付けられたMortonコードを有する複数のポイントに関連付けられた誤差評価の総和の関数として定義される積分誤差評価の判定のために適切な回路と、
(c)複数のポイントの所与のセットが、新たなポイントによって単純化され得るか否かの判定のために適切な回路であって、所与のセットすべてのポイントが、少なくとも、
-  最大のMortonコードを有する所与のセットのポイントのために判定された積分誤差評価と、
-  セットのポイントに関連付けられたMortonコードのうち、最小のMortonコードの次に低いMortonコードを有する複数のポイントのために判定された積分誤差評価との差分の関数として、同じ所与の長さのプレフィクスに関連付けられたMortonコードを有する複数のポイントである、回路とを備える。
【００３６】
既存の機器にインストールされ、上記説明された方法のすべてまたは一部を実施するコンピュータプログラムは、幾何学モデルの効率的な単純化を可能とするので、それ自体において有利である。
【００３７】
したがって、本発明はまた、コンピュータプログラムが1つまたは複数のプロセッサによって実行された場合に、上記説明された方法を実施するための命令を備えたコンピュータプログラムに関する。
【００３８】
このプログラムは、任意のプログラミング言語(たとえば、オブジェクト指向言語またはその他)を使用し得、部分的にコンパイルされたコード、または完全にコンパイルされたコードである、翻訳可能なソースコードの形式であり得る。
【００３９】
以下に詳細に説明されるように、図6a、図6b、および図6cは、そのようなコンピュータプログラムの一般的なアルゴリズムのためのフローチャートを形成し得る。
【００４０】
本発明の他の特徴および利点は、以下の説明を読むことによって明らかになるであろう。これは純粋に例示的であり、以下の添付図面を参照して読まれるべきである。
【図面の簡単な説明】
【００４１】
【図１ａ】Mortonコーディングを使用して、ポイントの座標の例示的なコーディングを例示する図である。
【図１ｂ】Mortonコーディングの例示的な切り捨てを例示する図である。
【図２】Mortonコーディングを使用して、異なるモデルのポイントを表す例示的なk-dツリーを図示する図である。
【図３】このモデルにおける幾何学的誤差の計算を有効化する2Dモデルにおける2次式の計算を表す図である。
【図４】このモデルにおける幾何学的誤差の計算を有効化する3Dモデルにおける2次式の計算を表す図である。
【図５】k-dツリーの内部ノードのための2次式の計算のための2次式の積分の計算を表す図である。
【図６ａ】kdツリーの生成のための例示的なフローチャートを図示する。
【図６ｂ】k-dツリーの内部ノードのための2次式の計算のための例示的なフローチャートを図示する。
【図６ｃ】単純化されたモデルのために維持されるべきノードの識別のための例示的なフローチャートである。
【図７】単純化されたモデルにおいて維持するために、いくつかのノードが選択された例示的なk-dツリーである。
【図８ａ】異なるアルゴリズムを使用することによって取得された単純化されたモデルの例を示す。
【図８ｂ】異なるアルゴリズムを使用することによって取得された単純化されたモデルの例を示す。
【図９】本発明の1つの実施形態における例示的なメッシュ単純化デバイスを図示する図である。
【発明を実施するための形態】
【００４２】
図1aは、Mortonコーディングを使用して、ポイントの座標の例示的なコーディングを例示する。
【００４３】
Mortonコーディングは、単一の整数を用いて、座標のセットを表すことを有効化するコーディングである。
【００４４】
例示として、ポイントpが、空間Eにおいて、3つの座標(x,y,z)のセットに関連付けられているのであれば、Mortonコードを表す整数pM(pMは、pの「Mortonコード」と呼ばれる)を使用することによって、これら座標を表すことが可能である。
【００４５】
本明細書では、xの値が、3つのビットx1 x2 x3(ここで、x1は、xの第1のビットの値であり、x2は、xの第2のビットの値であり、x3は、xの第3のビットの値である)を使用して2進数形式で表現されることが仮定される。同様に、yの値が、3つのビットy1 y2 y3(ここで、y1は、yの第1のビットの値であり、y2は、yの第2のビットの値であり、y3は、yの第3のビットの値である)を使用して2進数形式で表現されることが仮定される。最後に、zの値が、3つのビットz1 z2 z3(ここで、z1は、zの第1のビットの値であり、z2は、zの第2のビットの値であり、z3は、zの第3のビットの値である)を使用して2進数形式で表現されることが仮定される。
【００４６】
したがって、pの座標のMortonコードは、xの第1のビット、次にyの第1のビット、zの第1のビットを連続的に連結することによって計算され得る(ステップ100)。この連結は、各座標の第2のビットを取ることによって継続されるという具合である。図1aにおける例では、pMの値は、x1 y1 z1 x2 y2 z2 x3 y3 z3のように2進数で記述され得る。
【００４７】
したがって、2つのアイテムが、類似のMortonコード(特に、第1のビット)を有するのであれば、これらポイントは、通常、空間E内の近くにあるだろう。その逆は必ずしも真ではない。
【００４８】
図1bは、Mortonコードを切り捨てる例を例示する。
【００４９】
我々は、最後のビットが削除/無視されるMortonコードpMの値について、「次数1のMorton切り捨てコード」という用語を使用する。この値は、pM-1と示される。
【００５０】
我々は、N個の最後のビットが削除/無視されるMortonコードpMの値について、「次数NのMorton切り捨てコード」(Nは、自然数)という用語を使用する。この値は、pM-Nと示される。
【００５１】
したがって、MortonコードpMが2進数でx1 y1 z1 x2 y2 z2 x3 y3 z3であれば、pM-1は、x1 y1 z1 x2 y2 z2 x3 y3であり、pM-2は、x1 y1 z1 x2 y2 z2 x3である。
【００５２】
図2は、Mortonコーディングを使用して、異なるモデルのポイントを表す例示的なk-dツリーを図示する。
【００５３】
(「k次元のツリー」のための)k-dツリーは、各ノードが次元kにおけるポイントを含む2進数ツリーである。各「非終端」(すなわち、「非リーフ」または「内部」)ノードが、空間を、2つの半空間へ区分する。
【００５４】
図2の例では、「リーフ」ノードは、ノード201〜206である。これらのノードはおのおの、空間Eにおけるモデルのポイントに関連付けられ、上記説明されたようなこのポイントのためのMortonコードに関連付けられる。たとえば、ポイント201は、Mortonコード「0000」を有し、ノード204は、Mortonコード「0111」を有する。
【００５５】
以下に説明された処理を容易にするために、それらMortonコードに従って、「リーフ」ノードが、左から右への昇順で体系化される。これらノードを、異なる順序(たとえば、降順)で体系化することもまったく可能である。
【００５６】
もちろん、Mortonコードの精度は、モデルの座標の精度よりも低いことがあり得る。その後、2つの「リーフ」ノードが、同じMortonコードに関連付けられることが可能であれば、このケースでは、ある人は単に、順序付けられた「リーフ」ノードをトラバースする必要があり、重複が検出された場合、(リーフノードは順序付けられているので、連続する)これら2つのノードは、その後、単一のノードへ結合される。
【００５７】
「親」/「内部」ノードという用語は、リーフノードではないツリーのノードを称する。すべての親は、内部ノードである。たとえば、ノード209は、2つのリーフノード205および206の親ノードであり、ノード211は、親ノード209の親ノードである。
【００５８】
「所与のノードの子孫ノード」という用語は、所与のノードのMortonコードをプレフィクスとして有するMortonコードに関連付けられたノードを称する。したがって、ノード205は、ノード209の子孫ノードであり、ノード211の子孫ノードでもある。
【００５９】
「所与のノードの子ノード」という用語は、k-dツリーにおいてダイレクトに接続された所与のノードの子孫ノードを称する。したがって、ノード205は、ノード209の子ノードであるが、ノード211の子ノードではない。
【００６０】
「所与のノードの子孫リーフノード」という用語は、この子孫ノードもまた「リーフ」ノードである所与のノードの子孫ノードを称する。「リーフ」ノードは、子を持たない。
【００６１】
親ノードは、切り捨てられたMortonコードに対応し、このMortonコードは、「子孫」ノードに共通の最長のプレフィクスである。したがって、「親」ノード207は、2つの「子孫」201および202を有し、Mortonコード「000」(すなわち、ノード201に関連付けられた、または、ノード202に関連付けられたMortonコードの次数1の切り捨てられたMortonコード)に対応する。同様に、親ノード208は、2つの子孫203および204を有し、Mortonコード「01」(すなわち、ノード203に関連付けられた、または、ノード204に関連付けられたMortonコードの次数2の切り捨てられたMortonコードであり、ノード203に関連付けられた、および、ノード204に関連付けられたMortonコードの次数1の切り捨てられたMortonコードは異なる)に対応する。
【００６２】
「ルート」ノード212(RAC)は、どのMortonコードにも関連付けられていないが、親を有していないツリーの2つのノードを関連付けるツリーの終端を表す。
【００６３】
アルゴリズムが、k-dツリーを効率的にトラバースすることを有効化するために、(「リーフ」ノードを除外する)ツリーの各ノードについて、(空間を最大2つに区分する)「子孫」ノードを定義することが可能である。
【００６４】
それに加えて、各リーフノードについて、このノードiに関連付けられた幾何学的誤差を定量化するための2次式Qiを定義することが可能である。「リーフ」ノードについて、この2次式Qiは、Michael Garlandら(Surface Simplification Using Quadric Error Metrics、Section 5、1997年)によって表され、図3および図4に関して説明されたようなアルゴリズムに基づいて判定され得る。本質的に、この2次式は、空間内の任意のポイントにおいて、平面(たとえば、三角形の平面、または、ポイントおよびその法線によって定義される平面)への距離の平方を与える。
【００６５】
図3は、このモデルにおける幾何学的誤差の計算を有効化する2Dモデルにおける2次式の計算を図示する。
【００６６】
各リーフノードiについて、サイズ4x4の対称行列の形式で2次式Qiを判定することが可能である。
【００６７】
たとえば、ノード302に関連付けられた2次式を計算するために、ある人は、頂点の中でも、ノード302に関連付けられたポイントを有するメッシュの面の2次式を計算し、図3のケース(2Dモデル)では、平面的な面311の2次式(すなわち、Q311)と、平面的な面312の2次式(すなわち、Q312)が計算される。
【００６８】
平面的な面が、方程式ax+by+cz+d=0によって、または、ベクトル[a,b,c,d]Tによって説明されるのであれば、この面に関連付けられた2次式は、
【００６９】
【数１】
2018518747.tif 000003
【００７０】
の形式からなる。
【００７１】
さらに、空間における所与のポイントνについて、そのポイントから2次式(または、平面のコンテキストでは、平面)への距離の平方は、式
【００７２】
【数２】
2018518747.tif 000004
【００７３】
によって与えられる。
【００７４】
(ν,1)は、数字1が続くポイントνの3つの座標を備えたサイズ4のベクトルである。この表記は、同次座標におけるポイントνを記述することを可能にする。
【００７５】
それに加えて、2次式の総和は2次式であるので、少なくとも、ノード302に関連付けられたポイントを頂点として有するメッシュの面の2次式の総和として定義された2次式Q302を、ノード302に関連付けることが可能である。この例では、Q302=Q311+Q312を意味する。2次式Q302は、曲線352によって表され得る。
【００７６】
同様に、少なくとも、ノード303に関連付けられたポイントを頂点として有するメッシュの面の2次式の総和として定義された2次式Q303を、ノード303に関連付けることが可能である。この例では、Q303=Q312+Q313を意味する。2次式Q303は、曲線351によって表され得る。
【００７７】
2つのポイント302および303が、同じ親を有するk-dツリーの2つのポイントを表すと仮定すると、この親(すなわち、Qparent)に関連付けられた2次式を計算することが所望され得る。この2次式Qparentを、子孫「リーフ」ノードに関連付けられた、すなわち、ノード302に関連付けられた、または、ノード303に関連付けられたポイントを頂点として有する面の2次式の総和として計算することが可能であろう。すなわち、
-  Qparent=Q311+Q312+Q313(各2次式が、総和において一度だけ追加される場合)、または、
-  Qparent=Q311+2.Q312+Q313(各2次式が、この2次式に関連付けられた面の頂点「リーフ」ノードの数として、総和に何度も追加される場合)。
【００７８】
2次式Qparentは、曲線353によって表され得る。
【００７９】
さらに、内部ノード(すなわち、非「リーフ」ノード)について、「代表的」として称されるポイントνを関連付けることが可能である。この「代表的」なポイントは、所与の親ノードについて、
-  関連付けられた2次式を最小化する(すなわち、(ν,1)TQ(ν,1)を最小化する。ここで、Qは、親ノードに関連付けられた2次式である)空間のポイントνであり得る。これは、
【００８０】
【数３】
2018518747.tif 000005
【００８１】
が可逆的であれば(したがって、行列
【００８２】
【数４】
2018518747.tif 000006
【００８３】
が2次式Qの関数であり、最初の3行は、同一であれば)、
【００８４】
【数５】
2018518747.tif 000007
【００８５】
を解くことによって可能であり、
-  前述した行列が可逆的ではないのであれば、空間のポイントνは、
【００８６】
【数６】
2018518747.tif 000008
【００８７】
を満足し、Qpseudoは、たとえば、特異値分解または固有値分解を使用して計算された疑似逆行列Q'である平方4x4行列である。
【００８８】
-  行列Q'が可逆的ではないのであれば、および/または、実施形態がそのように提供するのであれば、空間のポイントνは、所与の(たとえば、ポイント302および303の重心、恐らくは重み付けられた)この親ノードの子孫「リーフ」ノードに関連付けられたポイントの関数として選択される。それに加えて、このポイントνはまた、(たとえば、ポイント302、303、301、および304の重心、恐らくは重み付けられた、ポイント302と面を共有するポイント301、および、ポイント304と面を共有するポイント304である)その特定の親ノードの子孫リーフノードに関連付けられたポイントの近隣ポイントの関数であり得る。
【００８９】
例示するために、2つの子孫ノード302、303の親ノードに関連付けられた「代表的」なポイントは、ポイント321であり得る。
【００９０】
しかしながら、このヒューリスティックは、k-dツリーの各親ノードについて、ツリーをその親ノードの子孫「リーフ」ノードまでトラバースするステップと、これらリーフノードのうちの少なくとも1つを頂点として有するメッシュ面を識別するステップと、関連付けられた2次式を判定するステップと、n個(整数n、ここでnは、判定された2次式の数に依存して大きくなり得る)の総和を計算するステップ等を必要とする。
【００９１】
したがって、このヒューリスティックは、非常に複雑(
【００９２】
【数７】
2018518747.tif 000009
【００９３】
ユニタリ演算、nbitは、本明細書では、最長のMortonコードのビット数)であり得、大きなメッシュ(すなわち、かなり大きなk-dツリー)のケースでは、非常に反復的である。
【００９４】
それに加えて、このヒューリスティックを実行するために、コンピュータ実施の場合、総和を実行する前に、子孫リーフノードの2次式のおのおのを記憶するためのメモリブロックを動的に割り当てることが有用であり得る。動的なメモリ割当は、並列的なコンテキストにおいて、アルゴリズム的な見地から効率的ではない。本明細書では、静的なメモリ割当を実行することは可能ではない。なぜなら、親ノードの2次式の計算のために考慮されるべき2次式の数は、前もって知られておらず、可能な最大数の子孫リーフノードに対応するメモリの静的な割当を実行することは、メモリを満たし得るので、可能ではないからである。
【００９５】
したがって、このヒューリスティックは、効率的な並列計算のために適切ではない。改善されたヒューリスティックが、図5および図6を参照して表される。
【００９６】
図4は、このモデルにおける幾何学的誤差の計算を有効化するための、3Dモデルにおける2次式の計算を表す。
【００９７】
図3に関して与えられた説明は、3Dメッシュ400のケースへ容易に適用され得る。
【００９８】
特に、メッシュのノード401について、このポイント401の隣接した面に関連付けられた2次式(すなわち、面t1、t2、およびt6)を考慮することが可能である。したがって、ポイント401に関連付けられた2次式は、Qt1+Qt2+Qt6であり得る。メッシュのノード402について、このポイント402の隣接した面に関連付けられた2次式(すなわち、面t1、t2、t3、t4、およびt5)を考慮することが可能である。したがって、ポイント402に関連付けられた2次式は、Qt1+Qt2+Qt3+Qt4+Qt5であり得る。
【００９９】
2つのノード401および402の親ノードについて(これら2つのリーフノードが同じ親を有すると仮定して)、関連付けられた2次式Qは、Qt1+Qt2+Qt3+Qt4+Qt5+Qt6であり得るか、さもなければ、2Qt1+2Qt2+Qt3+Qt4+Qt5+Qt6であり得る。
【０１００】
さらに、この親ノードの「代表的」なポイントは、以前のように、(行列Qの関数である行列の反転または疑似反転によって)2次式Qを最小化するポイント、または、ポイント401および402の関数(または、ポイント401〜406の関数)であるポイントであり得る。
【０１０１】
図5は、k-dツリーの内部ノードのための2次式の計算のための2次式の「積分」の計算を表す。
【０１０２】
上記に示されるように、k-dツリーにおける内部ノードの2次式を判定することは、複雑で扱いにくくなり得る。
【０１０３】
これら2次式を計算する処理を単純化するために、それらのMortonコードに従って「リーフ」ノードが分類される(図2を参照されたい。インデクスiを有するノードは、その次数を反映している)と、以下のアルゴリズムに従うことが可能である。すなわち、
-
【０１０４】
【数８】
2018518747.tif 000010
【０１０５】
の値を0へ初期化し、
-  Mortonコードの昇順または降順で得られた各ノードiについて、このノードiに関連付けられた値
【０１０６】
【数９】
2018518747.tif 000011
【０１０７】
を計算し、
【０１０８】
【数１０】
2018518747.tif 000012
【０１０９】
は、
【０１１０】
【数１１】
2018518747.tif 000013
【０１１１】
に等しい(Qiは、このノードに関連付けられた2次式である。図2を参照されたい)。
【０１１２】
我々は、
【０１１３】
【数１２】
2018518747.tif 000014
【０１１４】
を、ノードiに関連付けられた「積分2次式」と称する。
【０１１５】
【数１３】
2018518747.tif 000015
【０１１６】
が定義されていないのであれば、我々は、その値がゼロであると考慮し得る。
【０１１７】
これら積分2次式は、子孫リーフノードのうち最小のMortonコード(インデクスimin)を有するその子孫リーフノードと、子孫リーフノードのうち最大のMortonコード(インデクスimax)を有するその子孫リーフノードとを単に知ることによって、内部ノードに関連付けられた任意の2次式の非常に簡単な計算を有効化する。実際、この内部ノードの2次式の値は、
【０１１８】
【数１４】
2018518747.tif 000016
【０１１９】
と
【０１２０】
【数１５】
2018518747.tif 000017
【０１２１】
との差分として計算され得る。したがって、ノード207の2次式の値は
【０１２２】
【数１６】
2018518747.tif 000018
【０１２３】
であり、ノード208の2次式の値は
【０１２４】
【数１７】
2018518747.tif 000019
【０１２５】
であり、ノード211の2次式の値は、
【０１２６】
【数１８】
2018518747.tif 000020
【０１２７】
であり、ノード210の2次式の値は、
【０１２８】
【数１９】
2018518747.tif 000021
【０１２９】
であるという具合である。
【０１３０】
このヒューリスティックは、内部ノードのおのおのについて、1つの数学的演算(すなわち、4x4行列の差分)のみの実行を可能にする。結果的に、内部ノードのすべての2次式を計算するために、最大でも
【０１３１】
【数２０】
2018518747.tif 000022
【０１３２】
ユニタリ数学的演算(nbitは本明細書では最長のMortonコードのビット数である)しか必要とされない。それに加えて、各ノードについて、メモリにおける2つの子孫リーフノード(すなわち、インデクスimaxのノードと、インデクスiminのノード)へアクセスすることのみ必要である。したがって、動的なメモリ割当は必要とされない。これは、アルゴリズムの効率を高める。それに加えて、ノードに関連付けられた2次式の計算は、そのすべての子孫に関連付けられた2次式の以前の計算を必要とせず、このノードに依存する子孫リーフノードのみが、それらの2次式が初期化される(すなわち、計算される)必要がある。
【０１３３】
図6aは、k-dツリーの生成のための例示的なフローチャートを図示する。
【０１３４】
モデルを説明するメッシュのN個のポイント{p1,p2,…,pN}を受信する(601)と、これらポイントの座標を、図1aに関して説明されたようなMortonコードへ変換することが可能である(ステップ602)。
【０１３５】
Mortonコードが、これらポイントのおのおのに関連付けられると、図2に関して説明されたような、この関連付けられたMortonコードに従って、これらポイント(またはリーフノード)を順序付けることが可能である(ステップ603)。
【０１３６】
(Mortonコードのために使用される有限解によって)2つのリーフノードが、2つの同一のMortonコードを有しているのであれば、これらを1つのリーフノードへ結合することによって、これらノードを重複排除することが可能である(ステップ604)。
【０１３７】
次に、図2に関して説明されたような、順序付けられたリーフノードに基づいて(ステップ605)、k-dツリー(606)を生成することが可能である。k-dツリーを、「オクツリー」タイプのツリー(最大8つの子を有し得るツリー)に置き換えることがまったく可能である。
【０１３８】
図6bは、k-dツリーの内部ノードのための2次式の計算のための例示的なフローチャートを図示する。
【０１３９】
k-dツリーが判定されると、ツリーの各リーフノードiに関連付けることが可能である(iは、Morton順序におけるリーフノードのインデクスである)(ステップ607)。
-  p:関連付けられたMortonコードに対応するポイントの座標。
-  Q:図3または図4に関して説明されたように計算された2次式Qi。
-  QS:図5に関して説明されたように計算される積分2次式
【０１４０】
【数２１】
2018518747.tif 000023
【０１４１】
(すなわち、
【０１４２】
【数２２】
2018518747.tif 000024
【０１４３】
)。
【０１４４】
アルゴリズム効率化の理由で、
【０１４５】
【数２３】
2018518747.tif 000025
【０１４６】
の各値が、インデクスiによってアクセス可能であるテーブルにおける積分2次式の値を記憶することが可能である。確かに、積分2次式の値は、規則的にアクセスされ得る(以下参照)。
【０１４７】
それに加えて、ツリー606の各内部ノードjに関連付けることが可能である(ステップ608)。
-  ini:最小のインデクスを有する子孫リーフノードのインデクス。この値は、これら子ノードもまた内部ノードであれば、単に現在の内部ノードの子ノードのini値のうちの最小値として計算され得る。
-  las:最大のインデクスを有する子孫リーフノードのインデクス。この値は、これら子ノードが内部ノードであれば、単に現在の内部ノードの子ノードのlas値のうちの最大値として計算され得る。
-  Q:
-  積分2次式
【０１４８】
【数２４】
2018518747.tif 000026
【０１４９】
と、
-  積分2次式
【０１５０】
【数２５】
2018518747.tif 000027
【０１５１】
との差分の関数として計算される2次式Qj。
-
【０１５２】
【数２６】
2018518747.tif 000028
【０１５３】
:(計算が可能であれば)2次式Qjを最小化するポイントの座標。
-  w:現在の内部ノードに依存する子孫リーフノードの数。我々はまた、この数を「重み」とも呼ぶ。この値は単に、これら子ノードもまた内部ノードであれば、現在の内部ノードの子ノードの値wの総和として、または、las-ini+1として計算され得る。
-
【０１５４】
【数２７】
2018518747.tif 000029
【０１５５】
:この内部ノードに依存する子孫リーフノードのポイントpの重心を表す「平均」ポイントの座標。現在の内部ノードの子ノードについて、数wによって重み付けられた「平均」ポイント
【０１５６】
【数２８】
2018518747.tif 000030
【０１５７】
の重心を計算することによって、この平均ポイントを効率的に計算することが可能である(たとえば、図5を参照して示すように、
【０１５８】
【数２９】
2018518747.tif 000031
【０１５９】
である)。現在の内部ノードの子ノードがリーフノードであれば、それらの数wは、1であると考慮され得、それらの関連付けられた平均ポイントは、ポイントpであると考慮され得る(たとえば、図5を参照して示すように、
【０１６０】
【数３０】
2018518747.tif 000032
【０１６１】
である)。
【０１６２】
したがって、k-dツリー609のノードは、追加情報でこのように補強される。
【０１６３】
図6cは、単純化されたモデルのために維持されるべきノードの識別のための例示的なフローチャートである。
【０１６４】
誤差値ε(610)が示されると、単純化されたモデルのために維持されるべきノードの識別のためのアルゴリズムを初期化することが可能である(ステップ611)。
【０１６５】
これを行うために、平行してN個の計算処理を起動することが可能であり(Nは、k-dツリーのリーフノードの数である)、各並列計算処理iは、リーフノードpi(6121,…612i,…,612N)に関連付けられる。
【０１６６】
これら並列計算処理は、関連付けられたノード{pi}に達する前に「終了」していないのであれば、ルートノード(RAC)からそのノードまでツリーをトラバースするであろう(以下参照)。たとえば、処理が、図2のノード202に関連付けられているのであれば、この処理は、ノード212、210、207および202をトラバースするであろう。処理が図2のノード204に関連付けられているのであれば、この処理は、ノード212、210、208および204をトラバースするであろう。
【０１６７】
もちろん、この実施形態では、いくつかの処理は、同じノードをトラバースするであろうが、そのような多数の訪問を制限することを試みることは、多くの状況において処理全体のアルゴリズム効率に対して不利であり得ることが知られている。
【０１６８】
各並列計算処理について、この処理は、k-dツリー609のルートノードに位置され(このノードは、Mortonコードに関連付けられていないことを思い出されたい)、その後、処理に関連付けられたリーフノードに向かって1ノードを移動する。処理が位置されるノードは、「現在の処理のノード」と呼ばれる。
【０１６９】
現在の処理のノードについて、誤差値ε'が判定される(ステップ613)。ポイント
【０１７０】
【数３１】
2018518747.tif 000033
【０１７１】
がこのノードのために定義される(図6bに関して以下の説明を参照されたい)のであれば、この誤差値ε'は、
【０１７２】
【数３２】
2018518747.tif 000034
【０１７３】
として、または、ポイント
【０１７４】
【数３３】
2018518747.tif 000035
【０１７５】
がこのノードのために定義されていない(たとえば、
【０１７６】
【数３４】
2018518747.tif 000036
【０１７７】
の解有効化計算が可能ではない)のであれば、または、実施形態がそのように提供するのであれば、
【０１７８】
【数３５】
2018518747.tif 000037
【０１７９】
として計算される。もちろん、ε'の計算は、図6bに関して説明された処理の間、早期に実行され得る。
【０１８０】
判定された誤差値ε'が、示された誤差値εよりも大きい(テスト614、OK結果)のであれば、これは、ポイント
【０１８１】
【数３６】
2018518747.tif 000038
【０１８２】
または
【０１８３】
【数３７】
2018518747.tif 000039
【０１８４】
がメッシュの単純化のために許容可能ではないことを意味し、したがって、この処理は、この処理に関連付けられたリーフノードに向かって進む(ステップ615)。
【０１８５】
そうではない場合(テスト614、KO結果)、ノードは、メッシュの単純化のために許容可能であるとして選択/マークされ、処理が「終了」される(ステップ616)。
【０１８６】
処理がリーフノードに達した場合、ε'を計算する必要はない。なぜなら、この仮定の下では、このリーフノードは、その後、メッシュの単純化のために許容可能であるとして選択/マークされるからである。
【０１８７】
図7は、単純化されたモデルにおいて維持するために、いくつかのノードが選択された例示的なk-dツリーである。
【０１８８】
この例では、図6に説明された処理の実行後、ノード207、203、204および211は、メッシュの単純化のために許容可能であるとして選択/マークされる。
【０１８９】
初期モデルの面が、ノード202、203および204に関連付けられたポイント(p)によって説明されているのであれば、新たなメッシュが、ノード207、203および204に関連付けられたポイント
【０１９０】
【数３８】
2018518747.tif 000040
【０１９１】
によって説明される。一般に、新たな面は、初期面を説明する少なくとも1つの子孫リーフノードを有する選択された親ノードによって説明される。
【０１９２】
初期モデルの面が、ノード201、202および203に関連付けられたポイント(p)によって説明されるのであれば、この面は、縮約されていると言われる。なぜなら、それは、2つのポイントのみによって説明され(すなわち、ノード207および203に関連付けられ)、この面は、モデルから削除されるからである。これは、同じ面を説明する2つ(またはそれ以上の)リーフノードが、選択/マークされた同じ親ノードの子孫リーフノードである場合に生じ得る。
【０１９３】
しばしば、単純化中に、いくつかの面が「回転させられる」ことも生じる。初期面(すなわち、置き換えられるであろうもの)の法線ベクトルの平均を、新たな面の法線ベクトルと比較することによって、これをチェックすることが可能であり、法線ベクトルの方向が著しく変化するのであれば、モデルの一貫性を保証するために、最終的な面を「回転させる」ことが可能である。
【０１９４】
図8aおよび図8bは、異なるアルゴリズムを使用することによって取得された単純化されたモデルの例である。
【０１９５】
例示的な目的のために、約11万6千の面を有する単純化されたメッシュモデルを取得するために、2千8百万の面を含むメッシュモデル801について異なるアルゴリズムがテストされた。
【０１９６】
メッシュ802は、121ミリ秒において、DecoroおよびTatarchukによって提案された方法(Real-time mesh simplification using the gpu、2007年)に従って、均一分割(grid)に基づくアルゴリズムを用いて実行された単純化の例である。
【０１９７】
メッシュ803は、222ミリ秒において、上記表されたアルゴリズムを用いて実行された単純化の例である。
【０１９８】
メッシュ804は、234,985ミリ秒において、Michael Garlandらによって提案された方法(Surface Simplification Using Quadric Error Metrics、1997年)に基づくアルゴリズムを用いて実行された単純化の例である。
【０１９９】
ある人は、Garlandによって提案された単純化の品質は、より優れているが、それは、リアルタイム制約のために不適切である(単純化は、上記提案された単純化よりも1000倍以上遅い)ことに注目するであろう。
【０２００】
DecoroとTatarchukによって提案された単純化は、より高速であるが、単純化の品質もより低い。
【０２０１】
約1万8千の面を有する単純化されたメッシュモデルを取得するために、77万の面を含むメッシュモデル811についても、様々なアルゴリズムがテストされた。
【０２０２】
メッシュ812は、8ミリ秒において、DecoroおよびTatarchukによって提案された方法に従う均一分割(grid)に基づくアルゴリズムを用いて実行された単純化の例である。
【０２０３】
メッシュ813は、18ミリ秒において、上記提示されたアルゴリズムを用いて実行された単純化の例である。
【０２０４】
メッシュ814は、7544ミリ秒において、Michael Garlandらによって提案された方法(Surface Simplification Using Quadric Error Metrics、1997年)に基づくアルゴリズムを用いて実行された単純化の例である。
【０２０５】
図9は、本発明の1つの実施形態に従う例示的なメッシュ単純化デバイスを図示する。
【０２０６】
この実施形態では、デバイスは、この方法の実施を有効化する命令、受信された評価データ、および、上記説明された方法の様々なステップを実行するための一時的なデータを記憶するためのメモリ905を備えたコンピュータ900を含む。
【０２０７】
コンピュータはさらに、回路904を含む。この回路は、たとえば、
-  コンピュータプログラムの形式で命令を解釈することが可能な1つまたは複数のプロセッサ、または、
-  発明的な方法のステップがシリコンに記述される回路基板、または、
-  FPGA(Field-Programmable Gate Array)のようなプログラム可能な電子チップであり得る。
【０２０８】
このコンピュータは、メッシュポイントを受信するための入力インターフェース903と、単純化されたメッシュを、たとえば、遠隔コンピュータ907へ提供するための出力インターフェース906とを含む。最後に、コンピュータは、ユーザとの容易なインタラクションのために、スクリーン901およびキーボード902を含み得る。もちろん、キーボードは、オプションであり、特に、たとえば、タッチスクリーンタブレットの形式で、コンピュータのコンテキストにある。
【０２０９】
さらに、図6に提示された図解は、いくつかの命令が、説明されたデバイスとともに実行され得るプログラムの典型的な例である。そのため、図6は、本発明の意味の範囲内のコンピュータプログラムの一般的なアルゴリズムのフローチャートに対応し得る。
【０２１０】
もちろん、本発明は、例によって、上記説明された実施形態に限定されず、他の変形へ広がる。
【０２１１】
他の実施形態が可能である。
【０２１２】
たとえば、ノードに関連付けられた2次式に基づいて誤差ε'を計算するために、
-  ノードに関連付けられた色、および/または、
-  ノードに関連付けられた法線の値を考慮することも可能である。
【０２１３】
これを行うために、図6bに説明された処理(ステップ607)では、各リーフノードiについて、このリーフノードに関連付けられたポイントに隣接する面の色の平均色Coliを判定することが可能であり、平均色は、これら面の表面エリアによって、面の色を重み付けることによって判定される。
【０２１４】
積分2次式が、図5に関して計算されるのと同じ方式で、積分平均色
【０２１５】
【数３９】
2018518747.tif 000041
【０２１６】
を計算することも可能である。
【０２１７】
このリーフノードに関連付けられたポイントに隣接する面の表面エリアの総和が、Aiと示される。積分2次式が、図5に関して計算されるのと同じ方式で、積分表面エリア
【０２１８】
【数４０】
2018518747.tif 000042
【０２１９】
を計算することも可能である。
【０２２０】
【数４１】
2018518747.tif 000043
【０２２１】
および
【０２２２】
【数４２】
2018518747.tif 000044
【０２２３】
の値は、リーフノードiに関連付けられる。
【０２２４】
さらに、k-dツリーの各内部ノードjについて、色値Coljを、
【０２２５】
【数４３】
2018518747.tif 000045
【０２２６】
として判定することが可能である。
【０２２７】
図6cのステップ613において、誤差ε'を計算する場合、この誤差は、関数δCj=Colj-Cjであり得る。ここでCjは、これら隣接する面の表面エリアの総和によって重み付けられた単純化されたメッシュにおけるこのノードに関連付けられたポイントに隣接する面の色の平均色である。また、δCjを、
【０２２８】
【数４４】
2018518747.tif 000046
【０２２９】
として計算することも可能である。ε'の値は、幾何学的誤差(上記提示された)とδCjの値との重み付けられた総和であり得る。δCjの考慮は、より優れた色の考慮を有効化し、したがって、強い色変動を有するエリアにおける面の削除を回避する。
【０２３０】
(ポイントにおける表面への接平面の方位を示すベクトルであって、ポイントの位置へ導くものとは異なるキャプチャ/計算/モデリング、および、幾何学に関するより正確な情報を与える処理の結果から生じ得る)法線の考慮のために、このリーフノードに関連付けられたポイントにおける法線を表す第2の2次式を各リーフノードに関連付けることも可能である。その後、以前に述べられた2次式に類似しており、表面を表す様々な計算が図6において提案された処理において実行される。ε'の値は、幾何学的誤差(上記提示された)、および/または、δCjの値、および/または、(法線を表す第2の2次式を用いて計算された)法線における誤差の重み付けられた総和であり得る。法線の考慮は、モデルの詳細をより良く維持し、したがって、(たとえば、髪の毛のような)発音された詳細であるが低い幾何学的な振幅を有するエリアにおける面を削除することを回避する。
【０２３１】
k-dツリーは、メッシュのポイントの唯一の単純な表示(関連付けられたMortonコードに基づく単純化されたアクセス、最適化されたトラバース、コンピュータ実施の容易さ等)である。本発明を実施するために、このタイプのツリーを使用しないことはまったく可能であり、上記説明したような、よりグローバルなアプローチが可能である。
【符号の説明】
【０２３２】
201  ノード
202  ノード
203  ノード
204  ノード
205  ノード
206  ノード
207  ノード
208  ノード
209  ノード
210  ノード
211  ノード
212  ノード
301  ポイント
302  ポイント
303  ポイント
304  ポイント
311  2次式
312  2次式
313  2次式
321  ポイント
351  曲線
352  曲線
353  曲線
400  3Dメッシュ
401  ポイント
402  ポイント
403  ポイント
404  ポイント
405  ポイント
406  ポイント
606  k-dツリー
609  k-dツリー
801  メッシュモデル
802  メッシュ
803  メッシュ
804  メッシュ
811  メッシュモデル
812  メッシュ
813  メッシュ
814  メッシュ
900  コンピュータ
901  スクリーン
902  キーボード
903  入力インターフェース
904  回路
905  メモリ
906  出力インターフェース
907  遠隔コンピュータ
【図１ａ】
2018518747.tif 000054
【図１ｂ】
2018518747.tif 000055
【図２】
2018518747.tif 000056
【図３】
2018518747.tif 000057
【図４】
2018518747.tif 000058
【図５】
2018518747.tif 000059
【図６ａ】
2018518747.tif 000060
【図６ｂ】
2018518747.tif 000061
【図６ｃ】
2018518747.tif 000062
【図７】
2018518747.tif 000063
【図８ａ】
2018518747.tif 000064
【図８ｂ】
2018518747.tif 000065
【図９】
2018518747.tif 000066
【国際調査報告】
2018518747.tif 000067
2018518747.tif 000068
2018518747.tif 000069
2018518747.tif 000070
2018518747.tif 000071
2018518747.tif 000072
2018518747.tif 000073
2018518747.tif 000074