JP7703796B2

JP7703796B2 - 動的メッシュコーディングのためのパッチ生成

Info

Publication number: JP7703796B2
Application number: JP2024556568A
Authority: JP
Inventors: ダニーログラツィオージ; アレクサンドレザゲットー; アリタバタバイ
Original assignee: Sony Corp; Sony Group Corp
Current assignee: Sony Corp; Sony Group Corp
Priority date: 2022-03-25
Filing date: 2023-03-07
Publication date: 2025-07-07
Anticipated expiration: 2043-03-07
Also published as: CN117897957A; US20230306684A1; JP2025510194A; KR20240152867A; EP4480181A1; US12327313B2

Description

〔関連出願の相互参照〕
本出願は、２０２２年３月２５日に出願された「動的メッシュコーディングのためのパッチ生成（ＰＡＴＣＨＧＥＮＥＲＡＴＩＯＮＦＯＲＤＹＮＡＭＩＣＭＥＳＨＣＯＤＩＮＧ）」という名称の米国仮特許出願第６３／２６９，９１０号の米国特許法第１１９条に基づく優先権を主張するものであり、この出願は、全ての目的に対してその全体が引用により本明細書に組み込まれる。

本発明は、３次元グラフィックスに関する。より具体的には、本発明は、３次元グラフィックスのコーディングに関する。

近年、３Ｄから２Ｄへの投影に基づいて、ポイントクラウドなどのボリュームコンテンツを圧縮する新しい方法が標準化されつつある。Ｖ３Ｃ（視覚ボリュームビデオベースの圧縮）としても知られるこの方法は、３Ｄボリュームデータをいくつかの２Ｄパッチにマッピングし、更にパッチをアトラス画像に配置し、その後、ビデオエンコーダで符号化する。アトラス画像は、ポイントのジオメトリ、それぞれのテクスチャ、及びポイントクラウド再構築のためにどの位置を考慮すべきかを示す占有マップに対応する。

２０１７年、ＭＰＥＧは、ポイントクラウドの圧縮のための提案募集（ＣｆＰ）を実施した。いくつかの提案の評価の後、現在、ＭＰＥＧは、ポイントクラウド圧縮のための２つの異なる技術、すなわち、３Ｄネイティブコーディング技術（オクツリー及び同様のコーディング方法に基づく）、又は３Ｄから２Ｄへの投影後に従来のビデオコーディングを行うことを検討している。動的３Ｄシーンの場合、ＭＰＥＧは、パッチ表面モデリング、３Ｄから２Ｄ画像へのパッチの投影、及びＨＥＶＣなどのビデオエンコーダによる２Ｄ画像のコーディングに基づいて、テストモデルソフトウェア（ＴＭＣ２）を使用している。この方法は、ネイティブ３Ｄコーディングよりも効率的であることが判明しており、許容できる品質で競争力のあるビットレートを実現することができる。

投影ベースの方法（ビデオベースの方法、又はＶ－ＰＣＣとしても知られる）による３Ｄポイントクラウドのコーディングが成功したため、この標準の将来のバージョンでは、３Ｄメッシュなどの更なる３Ｄデータを含むことが予想される。しかしながら、この標準の現在のバージョンは、接続されていないポイントのセットの送信にのみ適しているため、３Ｄメッシュ圧縮で必要とされるようなポイントの接続性を送信する機構がない。

Ｖ－ＰＣＣの機能をメッシュに拡張するための方法も提案されている。１つの可能な方法は、Ｖ－ＰＣＣを使用して頂点を符号化し、次に、ＴＦＡＮ又はＥｄｇｅｂｒｅａｋｅｒなどのメッシュ圧縮方法を使用して接続性を符号化することである。この方法の制限は、頂点から生成されるポイントクラウドがまばらではなく、投影後に効率的に符号化することができるように、元のメッシュが高密度である必要があることである。更に、頂点の順序は接続性のコーディングに影響を及ぼすため、メッシュの接続性を再編成するための異なる方法が提案されている。まばらなメッシュを符号化するための代替の方法は、ＲＡＷパッチデータを使用して、３Ｄの頂点の位置を符号化することである。ＲＡＷパッチは（ｘ，ｙ，ｚ）を直接符号化するので、この方法では、全ての頂点がＲＡＷデータとして符号化され、一方、接続性は、前述のように、同様のメッシュ圧縮方法によって符号化される。ＲＡＷパッチにおいて、頂点は任意の好ましい順序で送信することができるため、接続性符号化から生成される順序を使用することができることに留意されたい。この方法は、まばらなポイントクラウドを符号化することができるが、ＲＡＷパッチは、３Ｄデータを符号化するのに効率的ではなく、この方法から、三角形の面の属性などの更なるデータが欠落している場合がある。

アーキテクチャは、メッシュの接続性を変換して非可逆圧縮を可能にする新しいブロックを含む。更に、方法は、メッシュから表面パッチを生成し、オブジェクトの全体的な態様を維持しながら、Ｖ３Ｃ標準を使用して効率的な符号化のためのパッチを生成する。三角形が、接続されたコンポーネント（ｃｏｎｎｅｃｔｅｄｃｏｍｐｏｎｅｎｔｓ）に一緒に結合され、各三角形の表面への条件付き投影が実行されて、投影された表面での接続性を強化する。新しい深度フィルタリングアルゴリズムを使用して、圧縮性能を向上させることができる。本明細書では、接続性圧縮のために追加される新しいブロックと、２Ｄの接続性を確保してＵＶテクスチャマップの送信を可能にし、深度値をフィルタリングして深度画像内の高周波エッジを回避するために導入される技術について説明する。

１つの態様では、パッチ生成の方法は、三角形の面法線を計算するステップと、前記三角形の面隣接（ｆａｃｅａｄｊａｃｅｎｃｙ）を計算するステップと、前記三角形の面近隣（ｆａｃｅｎｅｉｇｈｂｏｒｓ）を計算するステップと、前記三角形の前記法線を分類することを含む初期セグメンテーションを実装するステップと、前記分類された法線内の外れ値を特定して平滑化することを含む精緻化を実行するステップと、前記三角形のパッチセグメンテーションを実行するステップと、を含む。前記三角形の面隣接を計算するステップ及び前記三角形の面近隣を計算するステップは、隣接する三角形及び近隣の三角形のリストを生成することを含む。前記隣接する三角形及び前記近隣の三角形のリストを生成することは、テクスチャマップ境界を考慮に入れることを含む。前記テクスチャマップ境界を考慮に入れることは、現在の三角形の境界の反対側にある三角形を除外することを含む。パッチセグメンテーションを実行するステップは、縮退（ｄｅｇｅｎｅｒａｔｅｓ）を除去することと、頂点の遮蔽をチェックすることと、ハーフエッジをチェックすることと、表面の遮蔽をチェックすることと、深度フィルタリングと、深度範囲及び接続性の分析と、三角形をラスタ化することと、を含む。縮退した三角形（ｄｅｇｅｎｅｒａｔｅｔｒｉａｎｇｌｅｓ）を除去することは、点の間の領域が閾値より小さいことを判定することによって、線又は点である三角形を除去することを含み、頂点の遮蔽をチェックすることは、前記三角形の頂点が既に投影された三角形によって遮蔽されているかどうかを判定することを含み、ハーフエッジをチェックすることは、前記三角形が２つの投影された三角形によって既に共有されているエッジを共有しているかどうかを判定することを含み、表面の遮蔽をチェックすることは、前記三角形の点の間の領域が遮蔽されているか、又は前記既に投影された三角形を遮蔽する可能性があるかどうかを判定することを含み、深度フィルタリングは、近隣の点と前記三角形の点との深度差が深度閾値より小さいかどうかを判定し、深度範囲及び接続性の分析は、前記三角形が前記既に投影された三角形の少なくとも１つのエッジ又は頂点に接しているかどうかを判定することを含み、前記三角形を投影してラスタ化する。基準が満たされない時に、前記三角形は欠落三角形リスト（ｍｉｓｓｉｎｇｔｒｉａｎｇｌｅｓｌｉｓｔ）に追加される。

別の態様では、装置は、アプリケーションを記憶するための非一時的メモリであって、前記アプリケーションは、三角形の面法線を計算することと、前記三角形の面隣接を計算することと、前記三角形の面近隣を計算することと、前記三角形の前記法線を分類することを含む初期セグメンテーションを実装することと、前記分類された法線内の外れ値を特定して平滑化することを含む精緻化を実行することと、前記三角形のパッチセグメンテーションを実行することと、を行うためのものである、非一時的メモリと、前記メモリに結合され、前記アプリケーションを処理するように構成されるプロセッサと、を含む。前記三角形の面隣接を計算すること及び前記三角形の面近隣を計算することは、隣接する三角形及び近隣の三角形のリストを生成することを含む。前記隣接する三角形及び前記近隣の三角形のリストを生成することは、テクスチャマップ境界を考慮に入れることを含む。前記テクスチャマップ境界を考慮に入れることは、現在の三角形の境界の反対側にある三角形を除外することを含む。パッチセグメンテーションを実行することは、縮退を除去することと、頂点の遮蔽をチェックすることと、ハーフエッジをチェックすることと、表面の遮蔽をチェックすることと、深度フィルタリングと、深度範囲及び接続性の分析と、三角形をラスタ化することと、を含む。縮退した三角形を除去することは、点の間の領域が閾値より小さいことを判定することによって、線又は点である三角形を除去することを含み、頂点の遮蔽をチェックすることは、前記三角形の頂点が既に投影された三角形によって遮蔽されているかどうかを判定することを含み、ハーフエッジをチェックすることは、前記三角形が２つの投影された三角形によって既に共有されているエッジを共有しているかどうかを判定することを含み、表面の遮蔽をチェックすることは、前記三角形の点の間の領域が遮蔽されているか、又は前記既に投影された三角形を遮蔽する可能性があるかどうかを判定することを含み、深度フィルタリングは、近隣の点と前記三角形の点との深度差が深度閾値より小さいかどうかを判定し、深度範囲及び接続性の分析は、前記三角形が前記既に投影された三角形の少なくとも１つのエッジ又は頂点に接しているかどうかを判定することを含み、前記三角形を投影してラスタ化する。基準が満たされない時に、前記三角形は欠落三角形リストに追加される。

別の態様では、パッチセグメンテーションの方法は、縮退情報（ｄｅｇｅｎｅｒａｔｅｉｎｆｏｒｍａｔｉｏｎ）を除去するステップと、三角形の頂点の遮蔽をチェックするステップと、前記三角形のハーフエッジをチェックするステップと、前記三角形の表面の遮蔽をチェックするステップと、前記三角形の深度フィルタリングと、前記三角形の深度範囲及び接続性の分析を実行するステップと、前記三角形をキャンバスに投影してラスタ化するステップと、を含む。縮退した三角形を除去することは、点の間の領域が閾値より小さいことを判定することによって、線又は点である三角形を除去することを含む。頂点の遮蔽をチェックすることは、前記三角形の頂点が既に投影された三角形によって遮蔽されているかどうかを判定することを含む。ハーフエッジをチェックすることは、前記三角形が２つの投影された三角形によって既に共有されているエッジを共有しているかどうかを判定することを含む。表面の遮蔽をチェックすることは、前記三角形の点の間の領域が遮蔽されているか、又は前記既に投影された三角形を遮蔽する可能性があるかどうかを判定することを含む。深度フィルタリングは、近隣の点と前記三角形の点との深度差が深度閾値より小さいかどうかを判定する。深度範囲及び接続性の分析は、前記三角形が前記既に投影された三角形の少なくとも１つのエッジ又は頂点に接しているかどうかを判定することを含む。基準が満たされない時に、前記三角形は欠落三角形リストに追加される。

いくつかの実施形態による動的メッシュコーディングを実装する方法のフローチャートである。いくつかの実施形態によるパッチ生成を実装する方法のフローチャートである。いくつかの実施形態による法線を計算する図である。いくつかの実施形態による面隣接及び面近隣の分析の図である。いくつかの実施形態によるパッチ生成の図である。いくつかの実施形態による条件付きラスタ化を使用するパッチセグメンテーションのフローチャート及び図である。いくつかの実施形態による深度フィルタリングの図である。いくつかの実施形態による動的メッシュコーディングのためのパッチ生成方法を実装するように構成される例示的なコンピュータ装置のブロック図である。

アーキテクチャは、メッシュの接続性を変換して非可逆圧縮を可能にする新しいブロックを含む。更に、方法は、メッシュから表面パッチを生成し、オブジェクトの全体的な態様を維持しながら、Ｖ３Ｃ標準を使用して効率的な符号化のためのパッチを生成する。三角形が、接続されたコンポーネントに一緒に結合され、各三角形の表面への条件付き投影が実行されて、投影された表面での接続性を強化する。新しい深度フィルタリングアルゴリズムを使用して、圧縮性能を向上させることができる。本明細書では、接続性圧縮のために追加される新しいブロックと、２Ｄの接続性を確保してＵＶテクスチャマップの送信を可能にし、深度値をフィルタリングして深度画像内の高周波エッジを回避するために導入される技術について説明する。本明細書で説明するアーキテクチャは、２０２１年５月１７日に出願された「ビデオベースのメッシュ圧縮（ＶＩＤＥＯＢＡＳＥＤＭＥＳＨＣＯＭＰＲＥＳＳＩＯＮ）」という名称の米国特許出願第１７／３２２，６６２号、２０２０年１０月７日に出願された「ビデオベースのメッシュ圧縮」という名称の米国仮特許出願第６３／０８８，７０５号、及び２０２０年１０月６日に出願された「ビデオベースのメッシュ圧縮」という名称の米国仮特許出願第６３／０８７，９５８号に関連し、これらの出願はいずれも、全ての目的に対してその全体が引用により本明細書に組み込まれる。また、本明細書で説明する方法は、２０２１年１月２８日に出願された「投影ベースのメッシュ圧縮（ＰＲＯＪＥＣＴＩＯＮ－ＢＡＳＥＤＭＥＳＨＣＯＭＰＲＥＳＳＩＯＮ）」という名称の米国特許出願第１７／１６１，３００号に関連し、この出願は、全ての目的に対してその全体が引用により本明細書に組み込まれる。

図１に、いくつかの実施形態による動的メッシュコーディングを実装する方法のフローチャートを示す。入力メッシュ１００が受信又は取得される。例えば、入力メッシュは（例えば、ネットワークデバイスから）ダウンロードされるか、又はデバイス（例えば、カメラ又は自律走行車）によって取得／キャプチャされる。

メッシュボクセル化１０２が実行される。メッシュは、頂点の位置を浮動小数点数で有することができるため、これらの位置は整数空間に変換される。Ｖ－ＰＣＣ及びＶ３Ｃは、ボクセル化されたポイントクラウドを想定している。

次に、３Ｄメッシュの簡略化１０４が実行される。３Ｄメッシュの簡略化１０４は、パッチ生成の前に行われる。３Ｄメッシュの簡略化１０４は、投影する三角形の数を減らし、境界に低解像度情報を含むパッチを生成し、ジオメトリ画像から高解像度情報を回復することができるが、境界はまだ低解像度である。

ステップ１０６において、パッチ生成（又は作成）が実装される。パッチ生成１０６は、法線計算１５０、隣接計算１５２、近隣計算１５４、初期セグメンテーション１５６、精緻化１５８、及びパッチセグメンテーション１６０を含む。法線計算１５０では、各三角形の法線（例えば、三角形のエッジの外積）を計算する。隣接計算１５２では、各三角形の隣接関係（例えば、メッシュ内のどの三角形が、現在の三角形又は他の三角形に対して近隣である又は接触しているか）を計算する。近隣計算１５４は、近隣の三角形を計算することを含む。初期セグメンテーション１５６は、法線を向きに従って分類することを含む。例えば、三角形の法線は、上、下、左、右、前、又は後ろを向くことができ、方向／向きに基づいて分類することができる。いくつかの実施形態では、三角形は、法線の向きに基づいて色分けされる（例えば、法線が上を向いている三角形は全て緑色に着色される）。精緻化１５８は、外れ値（例えば、青い三角形に囲まれた単一の赤い三角形）を特定して、外れ値を平滑化する（例えば、単一の赤い三角形を、その近隣の青い三角形と一致するように変更する）ことを含む。精緻化１５８は、近隣を分析し、向きを平滑化する（例えば、法線の向きを調整する）ことによって実行される。滑らかな表面になると、パッチセグメンテーション１６０が実行されて、（例えば、向きに基づいて）特定の分類の三角形に対してパッチをセグメント化する。セグメンテーションは、パッチ投影を含むことができる。セグメンテーションでは、頂点及び接続性がパッチ上に表示される。例えば、この例の身体及び顔は、これらを分離する異なる分類の三角形があるため、別個のセグメンテーションである。いくつかの実施形態では、セグメンテーションはラスタ化される（例えば、ポイントの距離を含めて表面上のポイントをサンプリングして、ジオメトリ画像及び表面の属性を生成する）。ラスタ化されたメッシュ表面は、Ｖ３Ｃ画像と非常に類似する。

パッチ生成の結果として、セグメント化されたパッチ又はラスタ化されたメッシュ表面と、頂点の位置及び接続性がもたらされる。セグメント化されたパッチ又はラスタ化されたメッシュ表面は、ステップ１０８において、パッチパッキングで利用される。パッチパッキング１０８は、パッチをアトラス又は２Ｄキャンバスにパッキングすることを含むことができる。

パッチパッキング１０８の後、プロセスは、テクスチャ画像生成１１０、ジオメトリ画像生成１１２、及び２Ｄメッシュの簡略化１１４へと続く。２Ｄメッシュの簡略化１１４は、パッチ生成後に実行される。２Ｄメッシュの簡略化１１４は、パッチ内の三角形のみを削減し（境界三角形は削減されない）、境界に高解像度情報を含むパッチを生成し、パッチに保存された境界領域を含むジオメトリ画像から高解像度情報を回復することができる。

テクスチャ画像生成１１０から画像パディング１１６が行われ、その後、パディングされた画像は、ビデオコーデック１２２に送られて符号化される。テクスチャ画像は、テクスチャ情報を格納する。画像パディング１１６は、パッチ間の間隔を提供する。ビデオコーデック１２２は、任意の適切な符号化スキームを実行することができる。

ジオメトリ画像生成１１２から画像パディング１１８が行われ、その後、パディングされた画像は、ビデオコーデック１２４に送られて符号化される。ジオメトリ画像は、ジオメトリ情報を格納する。画像パディング１１８は、パッチ間の間隔を提供する。ビデオコーデック１２４は、任意の適切な符号化スキームを実行することができる。

２Ｄメッシュの簡略化１１４から接続性符号化１２０が行われ、その後、接続性情報は、メッシュジッパリング（ｍｅｓｈｚｉｐｐｅｒｉｎｇ）１２６及びアトラスコーデック１２８に送られて符号化される。メッシュジッパリング１２６は、ビデオコーデック１２４からも情報を受け取る。接続性符号化１２０は、ポイントの接続性情報を符号化することを含む。メッシュジッパリング１２６は、三角形又はパッチ間のギャップを除去するための実装である。

マルチプレクサ１３０は、Ｖ３Ｃビットストリームを出力する。Ｖ３Ｃビットストリームにより、ポイントクラウドの再構築及び／又はメッシュの構築が可能になる。ポイントクラウド及び／又はメッシュは、Ｖ３Ｃビットストリームから抽出することができ、これにより、大きな柔軟性をもたらす。いくつかの実施形態では、より少ないステップ又は追加のステップが実装される。いくつかの実施形態では、ステップの順序が変更される。

図２に、いくつかの実施形態によるパッチ生成を実装する方法のフローチャートを示す。パッチセグメンテーションにより、接続されたコンポーネント２００が生成される。接続されたコンポーネント２００は、同じ分類（例えば、図５では同じ色）を有する、近隣の三角形及び／又は隣接する三角形である。接続されたコンポーネント内の各三角形に対して、条件付きラスタ化２０２が実行される。つまり、三角形は、指定された基準を満たす場合にのみ、パッチに投影される。これにより、三角形が一貫して投影されることが保証される。三角形が指定された基準を満たさない場合、その三角形は欠落三角形とみなされ、欠落三角形はリストに戻され、異なる近隣の三角形又は隣接する三角形で再試行され、指定された基準による分析プロセスが繰り返される。

ラスタ化基準（例えば、三角形が投影されるかどうか）は、縮退の除去２０４、頂点の遮蔽のチェック２０６、ハーフエッジのチェック２０８、表面の遮蔽のチェック２１０、深度フィルタリング２１２、深度範囲及び接続性２１４、及び三角形のラスタ化２１６を含む。

縮退した三角形の除去２０４は、線である三角形（例えば、２つの点が重なり合って、三角形ではなく線が存在する場合）を除去することを含む。線又は点が除去され、少なくとも特定の領域（例えば、閾値を超える）を有する三角形のみが保持される。

頂点の遮蔽のチェック２０６は、三角形の頂点が遮蔽されているかどうかを判定することを含む。三角形の頂点が、既に投影されている三角形によって遮蔽されている（又はそれを閉塞する可能性がある）場合、投影は許可されず、三角形はリストから削除され、欠落三角形リストに移動する。

ハーフエッジのチェック２０８は、投影すべき三角形が、２つの投影された三角形によって既に共有されているエッジを共有しているかどうかを判定する。既に共有されている場合、投影は許可されず、三角形はリストから削除され、欠落三角形リストに移動する。

表面の遮蔽のチェック２１０では、三角形の頂点が遮蔽されていなくても、点の間の領域が既に投影された三角形（例えば、既に投影された三角形の頂点）によって遮蔽されている（又はそれを遮蔽する可能性がある）場合、投影は許可されず、三角形はリストから削除され、欠落三角形リストに移動する。

深度フィルタリング２１２は、近隣の点の三角形の深度差が閾値よりも小さいことを確認する（例えば、現在の三角形の点が、近隣の三角形の点と比較される）。深度差が閾値よりも大きい場合、三角形は投影されない。

深度範囲及び接続性２１４は、投影すべき三角形が既に投影された三角形の少なくとも１つ（例えば、共有エッジ又は頂点）に接しているかどうかを判定することを含む。投影すべき三角形と既に投影された三角形との間に接続性がない場合、投影は許可されず、三角形はリストから削除され、欠落三角形リストに移動する。深度範囲もチェックされる。

接続性及び許容可能な深度範囲がある場合（及び他の全ての基準が満たされている場合）、三角形は（例えば、キャンバスへの）投影が許容され、三角形はラスタ化（２１６）される（例えば、表面上の点を生成し、ジオメトリ画像及びテクスチャ画像を生成して、パッチ上の接続性を符号化する）。

図３に、いくつかの実施形態による法線を計算する図を示す。いくつかの実施形態では、面法線のみが計算される。法線３００は、２つのベクトル（例えば、ＡＢ及びＡＣ）の外積である。画像３０２は、面法線を含む例示的な画像を示す。

図４に、いくつかの実施形態による面隣接及び面近隣の分析の図を示す。三角形４００は、多くの隣接する三角形及び近隣の三角形を有する。隣接する三角形は、指定された三角形と少なくとも１つの頂点を共有する三角形である。例えば、三角形１～１５｛Ｔ₁、．．．、Ｔ₁₅｝は全て、三角形４００と頂点を共有する。近隣の三角形は、三角形とエッジを共有する。例えば、三角形４、１０、１４｛Ｔ₄、Ｔ₁₀、Ｔ₁₄｝は、三角形４００とエッジを共有する。隣接する三角形及び近隣の三角形のリストは、三角形ごとに保持することができる。境界を保持するためにフラグを含めることもできる。

３次元（３Ｄ）の三角形は、２次元（２Ｄ）の表面にマッピングされる。そのためには、メッシュの表面を（例えば、異なるグループ又はセクションに）分離する。例えば、テクスチャマップ境界４０２は、テクスチャマップ上の１つの部分又はグループ４０４と、テクスチャマップ上の第２の部分又はグループ４０６を分離する。換言すれば、２つの三角形が３Ｄ空間で互いに隣り合っている（例えば、近隣の三角形である）場合でも、２Ｄ空間では異なるグループにあるため、２Ｄ空間では分離されている（例えば、近隣の三角形ではない）場合がある。テクスチャマップ境界を維持するために、隣接する三角形及び近隣の三角形の２つのリストを生成する時に、テクスチャマップ境界４０２が考慮に入れられる。したがって、テクスチャマップ境界４０２を考慮すると（例えば、ターゲットの三角形と同じ境界側にない三角形を除外する）、三角形４００の場合、隣接する三角形のリストは｛Ｔ₆、．．．、Ｔ₁₄｝になり、近隣の三角形のリストは｛Ｔ₁₀、Ｔ₁₄｝になる。したがって、パッチが投影されると、境界が維持され、領域のテクスチャシーンが保存されるため、デコーダ側で使用できるようになる。

図５に、いくつかの実施形態によるパッチ生成の図を示す。説明したように、パッチ生成は、法線計算、隣接計算、初期セグメンテーション（又は法線カテゴリ化）、及びセグメンテーション精緻化（又はカテゴリ精緻化）を伴う。各三角形の法線の計算は、三角形のエッジ間の外積を伴う。隣接計算は、三角形が頂点を共有しているかどうかを判定し、共有している場合には三角形が近隣の三角形であると判定するものである。初期セグメンテーション及びセグメンテーション精緻化は、法線の向きを分析し、法線の向き（例えば、上、下、左、右、前、後）を分類し、全て同様に分類された近隣の法線に比べて法線の向きが異なるように分類されている（例えば、第１のパッチが上向きとして分類されたのに対し、ほとんど又は全ての近隣のパッチが前向きとして分類されている）かどうかを判定し、その後にパッチの法線の分類を近隣の法線の向きと一致するように変更する（例えば、第１のパッチの分類を前向きに変更する）ことによって、Ｖ－ＰＣＣと同様に実行される。

説明したように、メッシュをパッチにセグメント化するパッチ生成が実装される。パッチ生成は、１）ラスタ化されたメッシュ表面、及び２）頂点位置及び接続性情報も生成する。ラスタ化されたメッシュ表面は、Ｖ３Ｃ画像又はＶ－ＰＣＣ画像生成を受けるポイントのセットであり、Ｖ３Ｃ画像又はＶ－ＰＣＣ画像として符号化される。頂点位置及び接続性情報は、ベースメッシュコーディングのために受け取られる。

本明細書で説明するパッチ生成は、Ｖ－ＰＣＣにおけるパッチ生成と同様のものである。しかしながら、点ごとに法線を計算する代わりに、三角形ごとに法線を計算する。エッジ間の外積を使用して三角形ごとに法線を計算して、法線ベクトルを決定する。次に、法線に従って三角形をカテゴリ化する。例えば、法線を、前、後、上、下、左及び右などのｎ個（例えば、６個）のカテゴリに分割する。法線は、初期セグメンテーションを示すように異なる色で示される。図５には、異なる法線を示す異なる色として、黒色及び明るいグレーなどの異なる色をグレースケールで示す。見えにくいかもしれないが、上面（例えば、人の頭頂部、ボールの上面及びスニーカーの上面）は１つの色（例えば、緑色）であり、人物／ボールの第１の側は非常に暗く、別の色（例えば、赤色）を表しており、ボールの底面は別の色（例えば、紫色）であり、ほとんどが明るいグレーである人物及びボールの前面は別の色（例えば、シアン）を表している。

法線の積に方向を乗算することによって、主方向を求めることができる。近隣の三角形に目を向けることによって、平滑化／精緻化プロセスを実装することができる。例えば、閾値を上回る数の近隣の三角形が全て青色である三角形は、最初は赤色として示される異常があった場合でも青色として分類される。

三角形の接続されたコンポーネントを生成して、どの三角形が同じ色を有しているか（例えば、少なくとも１つの頂点を共有している同じカテゴリの三角形）を識別する。

接続性情報は、３Ｄにおいて点がどのように接続されているかを表す。これらの接続（より具体的には、３つの点を共有する３つの異なる接続）が組み合わさって三角形を生成し、この結果として（一群の三角形によって表される）表面が生成される。本明細書では三角形について説明するが、他の幾何学的形状（例えば、矩形）も可能である。

色を使用して、異なる色の三角形を識別することによって、接続性を符号化する。３つの接続によって識別される各三角形は、固有の色でコード化される。

図６に、いくつかの実施形態による条件付きラスタ化を使用するパッチセグメンテーションのフローチャート及び図を示す。パッチセグメンテーションにより、接続されたコンポーネント２００が生成される。接続されたコンポーネント２００は、同じ分類（例えば、図５では同じ色）を有する、近隣の三角形及び／又は隣接する三角形である。接続されたコンポーネント内の各三角形に対して、条件付きラスタ化２０２が実行される。つまり、三角形は、指定された基準を満たす場合にのみ、パッチに投影される。これにより、三角形が一貫して投影されることが保証される。三角形が指定された基準を満たさない場合、その三角形は欠落三角形とみなされ、欠落三角形はリストに戻され、異なる近隣の三角形又は隣接する三角形で再試行され、指定された基準による分析プロセスが繰り返される。

図７に、いくつかの実施形態による深度フィルタリングの図を示す。深度フィルタリングは、近隣の点の三角形の深度差が閾値よりも小さいことを確認する。深度差が閾値よりも大きい場合、三角形は投影されない。例えば、点の深度及び近隣の点の深度が分析される。しかしながら、他の三角形の近隣の点のみが分析される。図では、Ｔとラベル付けされた点は三角形からのものであるため、分析されない。三角形Ａ（ラベルＴ_A）及び三角形Ｂ（ラベルＴ_B）の点からの深度が分析される。換言すれば、グリッドの中央にある点Ｔの深度を比較するために、点Ｔの深度は、グリッドの左下の正方形にあるＴ_Aの深度、グリッドの左中央の正方形にあるＴ_Aの深度、グリッドの左上の正方形にあるＴ_Aの深度、グリッドの中央上部の正方形にあるＴ_Bの深度、及びグリッドの右上の正方形にあるＴ_Bの深度と比較される（例えば、それらの差を計算する）。比較された点の深度と他のいずれかの点の深度との差が閾値よりも大きい場合、三角形７００は投影されない。深度フィルタリングを実行することによって、大きな勾配が回避される。３ｘ３フィルタが示されているが、より大きなフィルタを実装することができる。いくつかの実施形態では、閾値は適応型であり、つまり、受け取られた情報又は特定の実装などの状況に応じて、閾値を変更することができる。

図８に、いくつかの実施形態による動的メッシュコーディングのためのパッチ生成方法を実装するように構成される例示的なコンピュータ装置のブロック図を示す。コンピュータ装置８００を使用して、３Ｄコンテンツを含む画像及びビデオなどの情報を取得、記憶、計算、処理、通信及び／又は表示することができる。コンピュータ装置８００は、符号化／復号化の態様のいずれかを実装することができる。一般に、コンピュータ装置８００を実装するのに適したハードウェア構造は、ネットワークインターフェイス８０２、メモリ８０４、プロセッサ８０６、（単複の）Ｉ／Ｏ装置８０８、バス８１０及び記憶装置８１２を含む。プロセッサの選択は、十分な速度の好適なプロセッサが選択される限り重要ではない。メモリ８０４は、当業で周知のいずれかの従来のコンピュータメモリとすることができる。記憶装置８１２は、ハードドライブ、ＣＤＲＯＭ、ＣＤＲＷ、ＤＶＤ、ＤＶＤＲＷ、高精細ディスク／ドライブ、超高精細ドライブ、フラッシュメモリカード、又はその他のいずれかの記憶装置を含むことができる。コンピュータ装置８００は、１又は２以上のネットワークインターフェイス８０２を含むことができる。ネットワークインターフェイスの例としては、イーサネット又は他のタイプのＬＡＮに接続されたネットワークカードが挙げられる。（単複の）Ｉ／Ｏ装置８０８は、キーボード、マウス、モニタ、画面、プリンタ、モデム、タッチ画面、ボタンインターフェイス及びその他の装置のうちの１つ又は２つ以上を含むことができる。記憶装置８１２及びメモリ８０４には、動的メッシュコーディングのためのパッチ生成の実装を実行するために使用される（単複の）動的メッシュコーディングのためのパッチ生成アプリケーション８３０が記憶されて、アプリケーションが通常処理されるように処理される可能性が高い。コンピュータ装置８００には、図８に示すものよりも多くの又は少ないコンポーネントを含めることもできる。いくつかの実施形態では、動的メッシュコーディングのためのパッチ生成ハードウェア８２０が含まれる。図８のコンピュータ装置８００は、動的メッシュコーディングのためのパッチ生成の実装のためのアプリケーション８３０及びハードウェア８２０を含むが、動的メッシュコーディングのためのパッチ生成方法は、ハードウェア、ファームウェア、ソフトウェア、又はこれらのいずれかの組み合わせでコンピュータ装置上に実装することもできる。例えば、いくつかの実施形態では、動的メッシュコーディングのためのパッチ生成アプリケーション８３０がメモリにプログラムされ、プロセッサを使用して実行される。別の例として、いくつかの実施形態では、動的メッシュコーディングのためのパッチ生成ハードウェア８２０は、動的メッシュコーディングのためのパッチ生成方法を実装するように特別に設計されたゲートを含むプログラムされたハードウェアロジックである。

いくつかの実施形態では、（単複の）動的メッシュコーディングのためのパッチ生成アプリケーション８３０は、複数のアプリケーション及び／又はモジュールを含む。いくつかの実施形態では、モジュールは１又は２以上のサブモジュールも含む。いくつかの実施形態では、これよりも少ない又は更なるモジュールを含めることもできる。

好適なコンピュータ装置の例としては、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、ハンドヘルドコンピュータ、携帯情報端末、セルラ／携帯電話機、スマート家電、ゲーム機、デジタルカメラ、デジタルカムコーダ、カメラ付き電話機、スマートホン、ポータブル音楽プレーヤ、タブレットコンピュータ、モバイル装置、ビデオプレーヤ、ビデオディスクライタ／プレーヤ（例えば、ＤＶＤライタ／プレーヤ、高精細ディスクライタ／プレーヤ、超高精細ディスクライタ／プレーヤ）、テレビ、家庭用エンターテイメントシステム、拡張現実装置、仮想現実装置、スマートジュエリ（例えば、スマートウォッチ）、車両（例えば、自動走行車両）、又はその他のいずれかの好適なコンピュータ装置が挙げられる。

動的メッシュコーディングのためのパッチ生成方法を利用するには、装置が３Ｄコンテンツ（例えば、ポイントクラウドコンテンツ）を取得又は受信する。動的メッシュコーディングのためのパッチ生成方法は、ユーザの支援を伴って、又はユーザの関与を伴わずに自動的に実装することができる。

動作時、動的メッシュコーディングのためのパッチ生成方法は、従来の実装と比較して、より効率的かつ正確な３Ｄコンテンツ符号化を可能にする。

動的メッシュコーディングのためのパッチ生成のいくつかの実施形態
１．パッチ生成の方法であって、
三角形の面法線を計算するステップと、
前記三角形の面隣接を計算するステップと、
前記三角形の面近隣を計算するステップと、
前記三角形の前記法線を分類することを含む初期セグメンテーションを実装するステップと、
前記分類された法線内の外れ値を特定して平滑化することを含む精緻化を実行するステップと、
前記三角形のパッチセグメンテーションを実行するステップと、
を含む方法。

２．前記三角形の面隣接を計算するステップ及び前記三角形の面近隣を計算するステップは、隣接する三角形及び近隣の三角形のリストを生成することを含む、第１項に記載の方法。

３．前記隣接する三角形及び前記近隣の三角形のリストを生成することは、テクスチャマップ境界を考慮に入れることを含む、第２項に記載の方法。

４．前記テクスチャマップ境界を考慮に入れることは、現在の三角形の境界の反対側にある三角形を除外することを含む、第３項に記載の方法。

５．パッチセグメンテーションを実行するステップは、縮退を除去することと、頂点の遮蔽をチェックすることと、ハーフエッジをチェックすることと、表面の遮蔽をチェックすることと、深度フィルタリングと、深度範囲及び接続性の分析と、三角形をラスタ化することと、を含む、第１項に記載の方法。

６．縮退した三角形を除去することは、点の間の領域が閾値より小さいことを判定することによって、線又は点である三角形を除去することを含み、
頂点の遮蔽をチェックすることは、前記三角形の頂点が既に投影された三角形によって遮蔽されているかどうかを判定することを含み、
ハーフエッジをチェックすることは、前記三角形が２つの投影された三角形によって既に共有されているエッジを共有しているかどうかを判定することを含み、
表面の遮蔽をチェックすることは、前記三角形の点の間の領域が遮蔽されているか、又は前記既に投影された三角形を遮蔽する可能性があるかどうかを判定することを含み、
深度フィルタリングは、近隣の点と前記三角形の点との深度差が深度閾値より小さいかどうかを判定し、
深度範囲及び接続性の分析は、前記三角形が前記既に投影された三角形の少なくとも１つのエッジ又は頂点に接しているかどうかを判定することを含み、
前記三角形を投影してラスタ化する、
第５項に記載の方法。

７．基準が満たされない時に、前記三角形は欠落三角形リストに追加される、第５項に記載の方法。

８．装置であって、
アプリケーションを記憶するための非一時的メモリであって、前記アプリケーションは、
三角形の面法線を計算することと、
前記三角形の面隣接を計算することと、
前記三角形の面近隣を計算することと、
前記三角形の前記法線を分類することを含む初期セグメンテーションを実装することと、
前記分類された法線内の外れ値を特定して平滑化することを含む精緻化を実行することと、
前記三角形のパッチセグメンテーションを実行することと、
を行うためのものである、非一時的メモリと、
前記メモリに結合され、前記アプリケーションを処理するように構成されるプロセッサと、
を含む装置。

９．前記三角形の面隣接を計算すること及び前記三角形の面近隣を計算することは、隣接する三角形及び近隣の三角形のリストを生成することを含む、第８項に記載の装置。

１０．前記隣接する三角形及び前記近隣の三角形のリストを生成することは、テクスチャマップ境界を考慮に入れることを含む、第９項に記載の装置。

１１．前記テクスチャマップ境界を考慮に入れることは、現在の三角形の境界の反対側にある三角形を除外することを含む、第１０項に記載の装置。

１２．パッチセグメンテーションを実行することは、縮退を除去することと、頂点の遮蔽をチェックすることと、ハーフエッジをチェックすることと、表面の遮蔽をチェックすることと、深度フィルタリングと、深度範囲及び接続性の分析と、三角形をラスタ化することと、を含む、第８項に記載の装置。

１３．縮退した三角形を除去することは、点の間の領域が閾値より小さいことを判定することによって、線又は点である三角形を除去することを含み、
頂点の遮蔽をチェックすることは、前記三角形の頂点が既に投影された三角形によって遮蔽されているかどうかを判定することを含み、
ハーフエッジをチェックすることは、前記三角形が２つの投影された三角形によって既に共有されているエッジを共有しているかどうかを判定することを含み、
表面の遮蔽をチェックすることは、前記三角形の点の間の領域が遮蔽されているか、又は前記既に投影された三角形を遮蔽する可能性があるかどうかを判定することを含み、
深度フィルタリングは、近隣の点と前記三角形の点との深度差が深度閾値より小さいかどうかを判定し、
深度範囲及び接続性の分析は、前記三角形が前記既に投影された三角形の少なくとも１つのエッジ又は頂点に接しているかどうかを判定することを含み、
前記三角形を投影してラスタ化する、
第１２項に記載の装置。

１４．基準が満たされない時に、前記三角形は欠落三角形リストに追加される、第１２項に記載の装置。

１５．パッチセグメンテーションの方法であって、
縮退情報を除去するステップと、
三角形の頂点の遮蔽をチェックするステップと、
前記三角形のハーフエッジをチェックするステップと、
前記三角形の表面の遮蔽をチェックするステップと、
前記三角形の深度フィルタリングと、
前記三角形の深度範囲及び接続性の分析を実行するステップと、
前記三角形をキャンバスに投影してラスタ化するステップと、
を含む方法。

１６．縮退した三角形を除去することは、点の間の領域が閾値より小さいことを判定することによって、線又は点である三角形を除去することを含む、第１５項に記載の方法。

１７．頂点の遮蔽をチェックすることは、前記三角形の頂点が既に投影された三角形によって遮蔽されているかどうかを判定することを含む、第１５項に記載の方法。

１８．ハーフエッジをチェックすることは、前記三角形が２つの投影された三角形によって既に共有されているエッジを共有しているかどうかを判定することを含む、第１５項に記載の方法。

１９．表面の遮蔽をチェックすることは、前記三角形の点の間の領域が遮蔽されているか、又は前記既に投影された三角形を遮蔽する可能性があるかどうかを判定することを含む、第１５項に記載の方法。

２０．深度フィルタリングは、近隣の点と前記三角形の点との深度差が深度閾値より小さいかどうかを判定する、第１５項に記載の方法。

２１．深度範囲及び接続性の分析は、前記三角形が前記既に投影された三角形の少なくとも１つのエッジ又は頂点に接しているかどうかを判定することを含む、第１５項に記載の方法。

２２．基準が満たされない時に、前記三角形は欠落三角形リストに追加される、第１５項に記載の方法。

本発明の構成及び動作の原理を容易に理解できるように、詳細を含む特定の実施形態に関して本発明を説明してきた。本明細書におけるこのような特定の実施形態及びその詳細についての言及は、本明細書に添付する特許請求の範囲を限定することを意図するものではない。当業者には、特許請求の範囲によって定められる本発明の趣旨及び範囲から逸脱することなく、例示のために選択した実施形態において他の様々な修正を行えることが容易に明らかになるであろう。

１００入力メッシュ
１０２メッシュボクセル化
１０４３Ｄメッシュの簡略化
１０６パッチ生成
１０８パッチパッキング
１１０テクスチャ画像生成
１１２ジオメトリ画像生成
１１４２Ｄメッシュの簡略化
１１６画像パディング
１１８画像パディング
１２０接続性符号化
１２２ビデオコーデック
１２４ビデオコーデック
１２６メッシュジッパリング
１２８アトラスコーデック
１３０マルチプレクサ
１５０法線計算
１５２隣接計算
１５４近隣計算
１５６初期セグメンテーション
１５８精緻化
１６０パッチセグメンテーション
２００接続されたコンポーネント
２０２条件付きラスタ化
２０４縮退の除去
２０６頂点の遮蔽のチェック
２０８ハーフエッジのチェック
２１０表面の遮蔽のチェック
２１２深度フィルタリング
２１４深度範囲及び接続性
２１６三角形のラスタ化
３００法線
３０２画像
４００三角形
７００三角形
８００コンピュータ装置
８０２ネットワークインターフェイス
８０４メモリ
８０６プロセッサ
８０８Ｉ／Ｏ装置
８１０バス
８１２記憶装置
８２０動的メッシュコーディングのためのパッチ生成ハードウェア
８３０動的メッシュコーディングのためのパッチ生成アプリケーション

Claims

パッチ生成の方法であって、
三角形の面法線を計算するステップと、
前記三角形の面隣接（ｆａｃｅａｄｊａｃｅｎｃｙ）を計算するステップと、
前記三角形の面近隣（ｆａｃｅｎｅｉｇｈｂｏｒｓ）を計算するステップと、
前記三角形の前記法線を分類することを含む初期セグメンテーションを実装するステップと、
前記分類された法線内の外れ値を特定して平滑化することを含む精緻化を実行するステップと、
前記三角形のパッチセグメンテーションを実行するステップと、
を含むことを特徴とする方法。
前記三角形の面隣接を計算するステップ及び前記三角形の面近隣を計算するステップは、隣接する三角形及び近隣の三角形のリストを生成することを含むことを特徴とする、請求項１に記載の方法。
前記隣接する三角形及び前記近隣の三角形のリストを生成することは、テクスチャマップ境界を考慮に入れることを含むことを特徴とする、請求項２に記載の方法。
前記テクスチャマップ境界を考慮に入れることは、現在の三角形の境界の反対側にある三角形を除外することを含むことを特徴とする、請求項３に記載の方法。
パッチセグメンテーションを実行するステップは、縮退（ｄｅｇｅｎｅｒａｔｅｓ）を除去することと、頂点の遮蔽をチェックすることと、ハーフエッジをチェックすることと、表面の遮蔽をチェックすることと、深度フィルタリングと、深度範囲及び接続性の分析と、三角形をラスタ化することと、を含むことを特徴とする、請求項１に記載の方法。
縮退した三角形（ｄｅｇｅｎｅｒａｔｅｔｒｉａｎｇｌｅｓ）を除去することは、点の間の領域が閾値より小さいことを判定することによって、線又は点である三角形を除去することを含み、
頂点の遮蔽をチェックすることは、前記三角形の頂点が既に投影された三角形によって遮蔽されているかどうかを判定することを含み、
ハーフエッジをチェックすることは、前記三角形が２つの投影された三角形によって既に共有されているエッジを共有しているかどうかを判定することを含み、
表面の遮蔽をチェックすることは、前記三角形の点の間の領域が遮蔽されているか、又は前記既に投影された三角形を遮蔽する可能性があるかどうかを判定することを含み、
深度フィルタリングは、近隣の点と前記三角形の点との深度差が深度閾値より小さいかどうかを判定し、
深度範囲及び接続性の分析は、前記三角形が前記既に投影された三角形の少なくとも１つのエッジ又は頂点に接しているかどうかを判定することを含み、
前記三角形を投影してラスタ化する、
ことを特徴とする、請求項５に記載の方法。
基準が満たされない時に、前記三角形は欠落三角形リスト（ｍｉｓｓｉｎｇｔｒｉａｎｇｌｅｓｌｉｓｔ）に追加されることを特徴とする、請求項５に記載の方法。
装置であって、
アプリケーションを記憶するための非一時的メモリであって、前記アプリケーションは、
三角形の面法線を計算することと、
前記三角形の面隣接を計算することと、
前記三角形の面近隣を計算することと、
前記三角形の前記法線を分類することを含む初期セグメンテーションを実装することと、
前記分類された法線内の外れ値を特定して平滑化することを含む精緻化を実行することと、
前記三角形のパッチセグメンテーションを実行することと、
を行うためのものである、非一時的メモリと、
前記メモリに結合され、前記アプリケーションを処理するように構成されるプロセッサと、
を含むことを特徴とする装置。
前記三角形の面隣接を計算すること及び前記三角形の面近隣を計算することは、隣接する三角形及び近隣の三角形のリストを生成することを含むことを特徴とする、請求項８に記載の装置。
前記隣接する三角形及び前記近隣の三角形のリストを生成することは、テクスチャマップ境界を考慮に入れることを含むことを特徴とする、請求項９に記載の装置。
前記テクスチャマップ境界を考慮に入れることは、現在の三角形の境界の反対側にある三角形を除外することを含むことを特徴とする、請求項１０に記載の装置。
パッチセグメンテーションを実行することは、縮退を除去することと、頂点の遮蔽をチェックすることと、ハーフエッジをチェックすることと、表面の遮蔽をチェックすることと、深度フィルタリングと、深度範囲及び接続性の分析と、三角形をラスタ化することと、を含むことを特徴とする、請求項８に記載の装置。
縮退した三角形を除去することは、点の間の領域が閾値より小さいことを判定することによって、線又は点である三角形を除去することを含み、
頂点の遮蔽をチェックすることは、前記三角形の頂点が既に投影された三角形によって遮蔽されているかどうかを判定することを含み、
ハーフエッジをチェックすることは、前記三角形が２つの投影された三角形によって既に共有されているエッジを共有しているかどうかを判定することを含み、
表面の遮蔽をチェックすることは、前記三角形の点の間の領域が遮蔽されているか、又は前記既に投影された三角形を遮蔽する可能性があるかどうかを判定することを含み、
深度フィルタリングは、近隣の点と前記三角形の点との深度差が深度閾値より小さいかどうかを判定し、
深度範囲及び接続性の分析は、前記三角形が前記既に投影された三角形の少なくとも１つのエッジ又は頂点に接しているかどうかを判定することを含み、
前記三角形を投影してラスタ化する、
ことを特徴とする、請求項１２に記載の装置。
基準が満たされない時に、前記三角形は欠落三角形リストに追加されることを特徴とする、請求項１２に記載の装置。
パッチセグメンテーションの方法であって、
縮退情報（ｄｅｇｅｎｅｒａｔｅｉｎｆｏｒｍａｔｉｏｎ）を除去するステップと、
三角形の頂点の遮蔽をチェックするステップと、
前記三角形のハーフエッジをチェックするステップと、
前記三角形の表面の遮蔽をチェックするステップと、
前記三角形の深度フィルタリングと、
前記三角形の深度範囲及び接続性の分析を実行するステップと、
前記三角形をキャンバスに投影してラスタ化するステップと、
を含むことを特徴とする方法。
縮退した三角形を除去することは、点の間の領域が閾値より小さいことを判定することによって、線又は点である三角形を除去することを含むことを特徴とする、請求項１５に記載の方法。
頂点の遮蔽をチェックすることは、前記三角形の頂点が既に投影された三角形によって遮蔽されているかどうかを判定することを含むことを特徴とする、請求項１５に記載の方法。
ハーフエッジをチェックすることは、前記三角形が２つの投影された三角形によって既に共有されているエッジを共有しているかどうかを判定することを含むことを特徴とする、請求項１５に記載の方法。
表面の遮蔽をチェックすることは、前記三角形の点の間の領域が遮蔽されているか、又は前記既に投影された三角形を遮蔽する可能性があるかどうかを判定することを含むことを特徴とする、請求項１５に記載の方法。
深度フィルタリングは、近隣の点と前記三角形の点との深度差が深度閾値より小さいかどうかを判定することを特徴とする、請求項１５に記載の方法。
深度範囲及び接続性の分析は、前記三角形が前記既に投影された三角形の少なくとも１つのエッジ又は頂点に接しているかどうかを判定することを含むことを特徴とする、請求項１５に記載の方法。
基準が満たされない時に、前記三角形は欠落三角形リストに追加されることを特徴とする、請求項１５に記載の方法。