26

さまざまな細分割アルゴリズム (catmull-clark など) の実装に取り​​組んでいます。これを効率的に行うには、テッセレーションされたポリゴンのグリッドに関する情報を適切に保存する方法が必要です。Flipcode で概説されているようにハーフエッジ データ構造を実装しましたが、頂点からデータ構造を取り込む方法がわかりません!

私の最初の試みは

  • 頂点を作成する
  • 頂点を面にグループ化する
  • 面内の頂点を並べ替える (重心に対する角度を使用)
  • 面ごとに、最初の頂点を取得し、並べ替えられた頂点リストをウォークスルーして、ハーフエッジ リストを作成します。

ただし、これにより、隣接する面に関する情報を持たない面 (半分のエッジを持つ) のリストが作成されます! これも少し間違っているように感じます。なぜなら、顔が本当に第一級のオブジェクトであり、エッジが補助的な情報を提供しているように見えるからです。頂点からエッジを作成し、そこから面を整理する必要があるように感じます。しかし、繰り返しになりますが、その方法をどのように実行すればよいかはよくわかりません。最初に面を作成せずに、半分のエッジのリストを作成する方法が思いつきません。

頂点 (および面) に関するデータをハーフエッジに変換する最善の方法について何か提案はありますか?

4

1 に答える 1

27

まず、ハーフエッジ データ構造の優れた C++ 実装であるOpenMesh を紹介したいと思います。使用したい場合は、必ずチュートリアルを進めてください。それを行う場合 (およびその場合にのみ)、OpenMesh での作業は非常に簡単です。また、サブディビジョンまたはリダクション アルゴリズムを実装できる優れたメソッドもいくつか含まれています。

今あなたの質問に：

ただし、これにより、隣接する面に関する情報を持たない面 (半分のエッジを持つ) のリストが作成されます! 顔が本当に第一級のオブジェクトであり、エッジが補助情報を提供しているかのように見えるため、これも少し間違っているように感じます。

これは、ハーフエッジのデータ構造の要点をやや逃していると思います。ハーフエッジ構造では、最も多くの情報を運ぶのはハーフエッジです!

OpenMeshのドキュメントから恥知らずに引用します(そこの図も参照してください)。

  • 各頂点は、1 つの出力ハーフエッジ、つまりこの頂点から始まるハーフエッジを参照します。
  • 各面は、それを囲むハーフエッジの 1 つを参照します。
  • 各ハーフエッジはハンドルを提供します
    • それが指す頂点、
    • それが属する顔
    • 面の内側の次のハーフエッジ (反時計回りの順序) 、
    • 反対側のハーフエッジ ,
    • (オプション: 面の前のハーフエッジ)。

ご覧のとおり、ほとんどの情報はハーフ エッジに格納されています。これらは主要なオブジェクトです。このデータ構造でメッシュを反復処理することは、ポインターを巧みに追跡することです。

ただし、これにより、隣接する面に関する情報を持たない面 (半分のエッジを持つ) のリストが作成されます!

これで全然OK！上記のように、面は1 つの境界ハーフ エッジのみを参照します。三角形のメッシュを想定すると、特定の面に隣接する 3 つの三角形を取得するためにたどるポインターのチェーンは次のようにFなります。

F -> halfEdge -> oppositeHalfEdge -> face

F -> halfEdge -> nextHalfEdge -> oppositeHalfEdge -> face

F -> halfEdge -> previousHalfEdge -> oppositeHalfEdge -> face

オプションでnextHalfEdge -> nextHalfEdge、「前の」ポインターを使用しない場合に使用できます。もちろん、これは四角形または高次のポリゴンに簡単に一般化できます。

メッシュを構築するときに上記のポインターを正しく設定すると、このようにメッシュ内のあらゆる種類の隣接関係を反復処理できます。OpenMesh を使用する場合は、ポインターを追跡する特別な反復子を多数使用できます。

「三角形のスープ」からハーフエッジ構造を構築する場合、「反対側のハーフエッジ」ポインタを設定することはもちろん難しい部分です。何らかのマップ データ構造を使用して、既に作成されているハーフ エッジを追跡することをお勧めします。

より具体的には、面からハーフエッジ メッシュを作成するための非常に概念的な擬似コードを次に示します。頂点部分は省いたほうがシンプルで、同じ精神で実装できます。顔のエッジに対する反復は順序付けられていると仮定します (たとえば、時計回り)。

HalfEdgeハーフエッジは、上記のポインターをメンバーとして含むtype の構造体として実装されていると想定しています。

   struct HalfEdge
   {
      HalfEdge * oppositeHalfEdge;
      HalfEdge * nextHalfEdge;
      Vertex * vertex;
      Face * face;
   }

頂点Edges識別子のペアから実際のハーフエッジ インスタンスへのポインタへのマップとします。

map< pair<unsigned int, unsigned int>, HalfEdge* > Edges;

C++で。構築の疑似コードは次のとおりです (頂点と面の部分を除く)。

map< pair<unsigned int, unsigned int>, HalfEdge* > Edges;

for each face F
{
   for each edge (u,v) of F
   {
      Edges[ pair(u,v) ] = new HalfEdge();
      Edges[ pair(u,v) ]->face = F;
   }
   for each edge (u,v) of F
   {
      set Edges[ pair(u,v) ]->nextHalfEdge to next half-edge in F
      if ( Edges.find( pair(v,u) ) != Edges.end() )
      {
         Edges[ pair(u,v) ]->oppositeHalfEdge = Edges[ pair(v,u) ];
         Edges[ pair(v,u) ]->oppositeHalfEdge = Edges[ pair(u,v) ];
       }
    }
 }

編集:Edgesマップとポインターをより明確にするために、コードを少し疑似的にしました。

于 2013-03-12T16:16:59.403 に答える