16

マーチングキューブアルゴリズムの実装に成功しました。標準資料を参考にしましたが、一から書き直しました。それは機能しますが、メッシュに穴を開ける原因となるあいまいさを観察しています。

あいまいさの影響を受けないと思われるマーチング四面体アルゴリズムを検討していました。これがどのように可能かわかりません。

マーチング四面体アルゴリズムは、立方体の代わりに6つの四面体を使用し、各四面体に三角形分割を使用します。しかし、マーチングキューブアルゴリズムを実装するとしますが、256の三角形分割のそれぞれについて、立方体の四面体の三角形分割の「合計」（和集合）であるものを選択するだけですか？私の知る限り、これは行進する四面体が行うことです-それで、なぜそれが曖昧さを魔法のように修正するのですか？

16のユニークなケースがあると思いますが、他の240は、それらの16の反射/回転にすぎません。あいまいさを解決するには33のケースが必要であるという論文をどこかで読んだことを覚えています。これは、四面体の行進がどういうわけか問題に悩まされない理由に関連しているのでしょうか？

だから、質問：

  1. マーチング四面体があいまいさに悩まされないのはなぜですか？
  2. そうでない場合は、マーチングキューブアルゴリズムを使用せず、代わりに四面体の三角形分割を使用するのはなぜですか？

ここで何かが足りないような気がします。ありがとう。

4

3 に答える 3

9

さて、私はマーチング四面体のバージョンの実装を終えたところです。あいまいさがマーチングキューブのメッシュに問題を引き起こすことは簡単にわかりましたが、マーチング四面体のメッシュは一貫してトポロジ的に正しいようです。非常に薄いポイントに沿っていくつかの厄介な機能があり、一部の頂点は分割のどちら側に配置するかを完全に決定できませんが、メッシュは常に水密です。

私の質問に答えて：

  1. マーチングキューブアルゴリズムのあいまいさを解決するために、私が知る限り、セル内で関数をより注意深く評価します。四面体アルゴリズムでは、セルの中心を明示的にサンプリングし、それにポリゴン化します。特に四面体メッシュにはこの頂点が含まれているため、あいまいさは暗黙的に処理されているのではないかと思います。側面にある他の余分な頂点も、おそらくそれと関係があります。重要なポイントとして、関数を改良するために、実際にはより多くの場所で関数がサンプリングされています。
  2. 私は彼らがそうすることをかなり確信しています。私のマーチング四面体アルゴリズムはまさにそれを実行します。内部的には、従来のマーチング四面体アルゴリズムと同じことを実行していると思います。私の実装では、四面体の三角形はすべて、可能な立方体ごとにリストされています。これにより、個々の四面体ごとに1つまたは2つの三角形を個別に計算するよりも速くなると思います。

時間と注意のスパンがあれば（どちらもしません）、各キューブの内側を再メッシュして、最大で使用する三角形の数を減らすことが有益かもしれません。これは、害にはならないと思います。

于 2012-06-18T03:40:28.917 に答える
8

「マーチング四面体アルゴにあいまいさがあるのはなぜですか？」という質問に答えるため。マーチングキューブ法で最初にあいまいさが生じる理由を理解する必要があります。

立方体に2つの対角線上にある「正の」頂点と2つの対角線上にある「負の」頂点がある場合、あいまいさが発生する可能性があります。頭を悩ませるのに少し時間がかかりましたが、あいまいさの問題は、理論的には、互いに互換性のない隣接する立方体の等値面パッチを作成できることです。それは明らかな部分です。興味深い部分は、2つのあいまいな構成からの2つの隣接する等値面パッチは、一方が「負の」頂点を分離し、もう一方が「正の」頂点を分離する場合にのみ互換性がないことです。

これは、Rephael Wengerのすばらしい本「IsosurfacesGeometry、Topology＆Algorithms」からの関連する引用です（2つ以上のリンクを投稿できないため、この本の関連するすべての画像を1つに統合しました）。

立方体の3次元等値面パッチの境界は、立方体の各正方形ファセットの等値面を定義します。一部の構成の等値面パッチがファセットの負の頂点を分離し、隣接する構成の等値面パッチが正の頂点を分離する場合、共通ファセットの等値面エッジは整列しません。図2.16の等値面パッチは、どのファセットの正の頂点も分離しません。さらに、構成の回転または反射で導出された等値面パッチも、ファセット上の正の頂点を分離しません。したがって、隣接する2つの立方体の等値面パッチは、それらの境界に適切に配置されます。同様に有効ですが、組み合わせて区別されます。

これが意味するのは、使用されるすべてのあいまいな構成が同じパターンに従う場合（つまり、常に「負の」頂点を分離する場合）、トポロジ的に不正確なサーフェスを生成することは不可能であるということです。また、単一の等値面に対して「両方の世界からの」構成を使用すると、問題が発生します。

同じあいまいさの解決パターンを使用して構築されたサーフェスには、このような不要なエラーが含まれている可能性があります（Thomas Lewiner Helio Lopes、Antonio Wilson Vieira、Geovan Tavaresによる「マーチングキューブのケースのトポロジカル保証付きの効率的な実装」の記事から引用）。あなたが言ったように、水密になります。

これを実現するには、図2.16に示す22の固有の構成（標準の14または15ではない）に基づくルックアップテーブルを使用する必要があります。

さて、ついに元の質問に戻りましょう-なぜマーチング四面体は曖昧さに悩まされないのですか？同じ理由で、上記のように実行した場合、マーチングキューブにあいまいさはありません。これは、あいまいな構成解決の2つの利用可能なバリアントのいずれかを任意に使用することを選択したためです。マーチングキューブでは、これがオプションであるかどうかはまったくわかりません（少なくとも私にとっては、多くの掘り下げを行う必要がありました）が、マーチング四面体では、アルゴリズム自体によって実行されます。RephaelWengerの本からの別の引用は次のとおりです。

通常のグリッドキューブの構成はあいまいですが、四面体分解にはありません。あいまいな構成はどうなりましたか？これらの構成は、三角形分割を選択することで解決されます。たとえば、図2.31では、最初の三角測量により、図2.22の2B-IIに対応する2つのコンポーネントを持つ等値面パッチが得られ、2番目の三角測量では2B-Iに対応する1つのコンポーネントを持つ等値面パッチが得られます。

図2.31で、立方体が2つの異なる方法で四面体にスライスされる方法に注意してください。このスライスまたは他のスライスの選択は、あいまいさを解決する秘密のソースです。

すべてのキューブに同じパターンを使用するだけであいまいさの問題を解決できるのなら、なぜもっと複雑な解決策についての本や論文がたくさんあるのでしょうか。Asymptotic Deciderなどが必要なのはなぜですか？私が知る限り、それはすべてあなたが達成する必要があることに帰着します。トポロジーの正確さ（たとえば、穴がない）で十分な場合は、すべての高度な機能は必要ありません。上記の「マーチングキューブの効率的な実装」の記事に示されているような問題を解決したい場合は、さらに深く掘り下げる必要があります。

Rephael Wengerの著書「IsosurfacesGeometry、Topology＆Algorithms」の関連する章を読んで、これらのアルゴリズムの性質、問題とは何か、問題はどこから来ているのか、どのように解決できるのかを理解することを強くお勧めします。

Li Xiaoshengが指摘したように、最初にマーチングスクエアのアルゴを注意深く調べることで、基本をよりよく理解できます。実際、全体の答えはLi Xiaoshengによって定められたので、説明を少し拡張しました。

于 2015-04-07T10:38:39.930 に答える
2

次の2dの例（あいまいさを導入）を取り上げます。

01

10

この正方形を2つの三角形に分割すると、正方形を分割するために選択した対角線で異なる結果が得られます。0-0の対角線に沿って、三角形（010,010）を取得し、1-1の対角線に沿って、三角形（101,101）を取得します。明らかに、正方形の分解が異なると結果も異なります。どちらも正しく、これは3Dキューブでも同じです。

MTは実際にはあいまいさを解決しませんが、すべてのキューブに対して同じ分解戦略を選択することにより、トポロジー的に構成された結果を生成できます。それが曖昧さの苦しみを取り除く方法です。

于 2013-06-24T10:09:24.767 に答える