Datenstrukturen für allgemeine (nicht tetraedrische) Zellkomplexe

Für polygonale 2D-Netze reichen die QuadEdge- und HalfEdge-Datenstrukturdarstellungen aus, um alle topologischen Informationen und Inzidenzinformationen zu speichern und effizient abzufragen. Gibt es kompakte und effiziente Datenstrukturen für polyedrische 3D-Netze? Ich weiß, dass es in letzter Zeit einige Arbeiten zu kompakten Darstellungen für tetraedrische Netze gegeben hat, wie zum Beispiel SOT . Ich weiß nicht genug darüber, um zu wissen, ob sie sich auf unstrukturierte nicht-tetraedrische Netze verallgemeinern lassen.

Ich kann mir vorstellen, dass Halbkanten auf Halbflächen mit zugehörigen Halbkanten verallgemeinert werden könnten, aber es scheint, dass viele Daten gespeichert werden müssen und es möglicherweise kompaktere Darstellungen gibt. Ich sollte hinzufügen, dass es mir wirklich nur darum geht, Facetteninformationen abzurufen (z. B. welche Facetten an der Grenze liegen, welche Facetten zu einer bestimmten Zelle gehören). Die Informationen zur Kanteninzidenz sind nicht so nützlich.

data-structures computational-geometry Victor Liu
quelle

Antworten:

Es gibt eine Erweiterung der Halbkante in jeder Dimension, die in kombinatorischen Karten als Pfeile bezeichnet wird . In CGAL gibt es zwei Pakete, mit denen diese kombinatorischen Karten in jeder Dimension verwendet werden können (siehe hier für kombinatorische Karten und hier für LinearCellComplex ).

Mit dieser Datenstruktur können Sie jedes quasi mannigfaltig orientierbare unterteilte 3D-Objekt darstellen. Zitieren von der CGAL-Webseite (Abschnitt 2.4 Kombinatorische Karteneigenschaften ):

Ein quasi-vielfältiges Objekt ist definiert als:

Eine dD-Quasi-Mannigfaltigkeit ist ein Objekt, das erhalten wird, indem einige isolierte d-Zellen genommen werden und d-Zellen entlang (d-1) -Zellen geklebt werden können.

und orientierbar als:

Es ist orientierbar, ob es möglich ist, es in den euklidischen Raum einzubetten und in jedem Punkt des eingebetteten Objekts eine globale "linke" und "rechte" Richtung zu definieren.

gdamiand
quelle

Wie ist dies mit der FacetEdge-Darstellung von Dobkin & Laszlo zu vergleichen? Das scheint das einzige andere zu sein, was ich finden kann.

Victor Liu

Sie sind gleichwertig. In der FacetEdge-Darstellung gibt es hauptsächlich drei Funktionen: clock , Enext und Fnext ; und in einer kombinatorischen 3D-Karte gibt es 3 Funktionen , und .

β_{1}

$\beta_1$

β_{2}

$\beta_2$

β_{3}

$\beta_3$

gdamiand

Beachten Sie, dass diese Seite über Computer ist die Wissenschaft , nicht Bibliothek - Implementierungen. Daher schätzen wir Antworten, die Ideen und Konzepte enthalten, nicht nur Verweise auf Implementierungen.

Raphael