Initialisierung der Half-Edge-Datenstruktur aus Vertices

Zuerst, ich möchte an dieser Stelle auf eine ausgezeichnete C++ - Implementierung der half-edge-Datenstruktur: OpenMesh. Wenn Sie es verwenden möchten, stellen Sie sicher, arbeiten Sie sich durch das tutorial. Wenn (und nur wenn) Sie das tun, das arbeiten mit OpenMesh ist ganz einfach. Es enthält auch ein paar nette Methoden auf, von denen Sie implementieren können, Unterteilung oder Verkleinerung algorithmen.

Nun zu deiner Frage:

Jedoch, dieses erstellt eine Liste der Gesichter (mit halb-Kanten), denen keine information über die angrenzenden Flächen! Dieser fühlt sich auch ein bisschen falsch, denn es scheint, als ob die Gesichter sind wirklich das erste-Klasse-Objekt und die Kanten stellen zusätzliche Informationen

Ich denke, dass dies etwas findet den Punkt, der die half-edge-Datenstruktur. In einer half-edge-Struktur ist es die Hälfte-Kanten, tragen die meisten Informationen!

Zitieren schamlos von der OpenMesh-Dokumentation (siehe auch die Abbildung):

• Jeder Knoten verweist auf eine outgoing halfedge, d.h. ein halfedge, beginnt an diesem Knoten.
• Jedes Gesicht Verweise eine der halfedges bounding.
• Jeder halfedge bietet einen Griff zu
  • die vertex es Punkte ,
  • das Gesicht, es gehört zu
  • die nächste halfedge im Gesicht (bestellt gegen den Uhrzeigersinn) ,
  • das Gegenteil halfedge ,
  • (Optional: das Vorherige halfedge im Gesicht ).

Wie Sie sehen, die meisten Informationen werden in die halb-Kanten - dies sind die primären Objekte. Iteriert Maschen in diese Daten-Struktur ist, dass alle über clever folgenden Hinweise.

Jedoch, dieses erstellt eine Liste der Gesichter (mit halb-Kanten), denen keine information über die angrenzenden Flächen!

Das ist vollkommen ok! Wie Sie oben sehen, ein Gesicht Verweise nur eine bounding-halb-Kante. Unter der Annahme einer Dreieck-mesh, die Kette der Hinweise, die Sie Folgen, um die 3 angrenzenden Dreiecke zu einem bestimmten Gesicht F ist folgende:

F -> halfEdge -> oppositeHalfEdge -> face

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

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

Optional können Sie nextHalfEdge -> nextHalfEdge wenn Sie nicht die 'Vorherige' - Zeiger. Dies ist natürlich verallgemeinert sich leicht auf quads oder höher, um Polygone.

Wenn Sie den Zeiger oben aufgeführt korrekt, wenn Sie den Aufbau Ihrer Masche, dann können Sie iterieren über alle Arten von produktnachbarschaften in Ihrem Netz wie dieses. Wenn Sie OpenMesh, die Sie verwenden können, eine Reihe von besonderen Iteratoren, dass der Zeiger jagt für Sie.

Einstellung "gegenüber half-edge" - Zeiger ist natürlich der knifflige Teil beim Bau einer half-edge-Struktur aus einer "Dreiecks-Suppe". Ich schlage vor, auf der Karte Daten-Struktur von einer Art zu verfolgen, halbe Kanten schon angelegt.

Um genauer zu sein, hier einige sehr konzeptionellen pseudo-code für die Erstellung einer half-edge-mesh aus den Gesichtern. Ich ließ das vertex-Teil, der ist einfacher, und es kann umgesetzt werden in dem gleichen Geist. Ich gehe davon aus, dass die iteration über ein Gesicht Kanten bestellt (z.B. clock-wise).

Ich nehme an, die Hälfte Kanten umgesetzt werden als Strukturen des Typs HalfEdge enthalten Zeiger oben aufgeführt, als Mitglieder zu.

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

Lassen Edges eine Karte aus Paaren von Scheitelpunkt-Identifizierer, um die Zeiger zu den eigentlichen half-edge-Instanzen, z.B.

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

in C++. Hier ist der Bau pseudo-code (ohne die vertex-und face-Teil):

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) ];
       }
    }
 }

EDIT: Gemacht, den code ein bisschen weniger pseudo, mehr Klarheit über die Edges anzeigen und Zeiger.

InformationsquelleAutor der Antwort DCS