Zerlegen eines konkaven Netzes in einen Satz konvexer Netze

10

Ich möchte in der Lage sein, ein konkaves Netz aus zwei Gründen in einen Satz konvexer Netze zu zerlegen:

  1. Transparentes Rendern
  2. Physikformen

Gibt es einen Algorithmus, der eine Reihe von Dreiecken (konkav) als Eingabe verwendet und mehrere Sätze von Dreiecken (konvex) ausgibt? Ich möchte, dass die Löcher zwischen Teilen des ursprünglichen Netzes nicht ausgefüllt werden.

Ich bin bereits auf eine kleine Idee gestoßen: Finde alle konkaven Kanten und teile die Maschen entlang der Kantenschleifen. Bin ich auf dem richtigen Weg? Wie könnte ich das umsetzen?

jmegaffin
quelle
Was ist ein "konkaves / konvexes" Netz? Wenn Mesh Dreiecksnetzwerk bedeutet, dann ist es nur eine Reihe von Dreiecken, die konvex sind. Oder sprechen Sie über das Volumen von 3D-Objekten? Vielleicht Polyeder?
Ivan Kuckir
@IvanKuckir Meshes oder Polyeder können auch konkav / konvex sein, und die Definition ist ziemlich gleich. Beispielsweise schneidet keine gerade Linie das Innere des Polyeders mehr als einmal.
Congusbongus

Antworten:

11

Ich würde sagen, Sie sind auf dem richtigen Weg, aber einen optimalen und / oder effizienten Algorithmus zu finden, ist eine andere Sache: Es ist ein schwieriges Problem. Wenn Ihr Interesse jedoch nicht akademisch ist, kann eine ausreichend gute Lösung ausreichen.

Wenn Sie nicht daran interessiert sind, eine eigene Lösung zu finden, enthält CGAL bereits einen Algorithmus für die konvexe Polyederzerlegung: http://doc.cgal.org/latest/Convex_decomposition_3/index.html

Nun zur Methode; Wie bei vielen Problemen in 3D ist es oft hilfreich, das 2D-Problem zu betrachten, das leichter zu verstehen ist. Bei 2D besteht die Aufgabe darin, Reflexscheitelpunkte zu identifizieren und das Polygon in zwei Teile zu teilen, indem aus diesem Reflexscheitelpunkt eine neue Kante (und möglicherweise neue Scheitelpunkte) erstellt wird und so lange fortgefahren wird, bis Sie keine Reflexscheitelpunkte (und damit alle konvexen Polygone) mehr haben ).

Reflexscheitelpunkte

Die Polygonzerlegung von J. Mark Keil enthält den folgenden Algorithmus (in nicht optimierter Form):

diags = decomp(poly)
    min, tmp : EdgeList
    ndiags : Integer
    for each reflex vertex i
        for every other vertex j
            if i can see j
                left = the polygon given by vertices i to j
                right = the polygon given by vertices j to i
                tmp = decomp(left) + decomp(right)
                if(tmp.size < ndiags)
                    min = tmp
                    ndiags = tmp.size
                    min += the diagonal i to j
    return min

Grundsätzlich werden alle möglichen Partitionen ausführlich verglichen und die Partition mit den geringsten erzeugten Diagonalen zurückgegeben. In diesem Sinne ist es etwas brutal und auch optimal.

Wenn Sie "schönere" Zerlegungen wünschen , dh solche, die kompaktere als längliche Formen erzeugen, können Sie auch diese von Mark Bayazit hergestellte in Betracht ziehen , die gierig ist (daher viel schneller) und schöner aussieht, aber einige Mängel aufweist. Grundsätzlich funktioniert es, indem versucht wird, Reflexscheitelpunkte mit dem besten gegenüberliegenden zu verbinden, normalerweise mit einem anderen Reflexscheitelpunkt:

Bayazit neuer Scheitelpunkt Bayazit verbinden sich mit einem anderen Reflexscheitelpunkt

Einer der Mängel besteht darin, dass "bessere" Zerlegungen ignoriert werden, indem Steiner-Punkte erstellt werden (Punkte, die an einer vorhandenen Kante nicht vorhanden sind):

Kleezersetzung mit zwei Steinerpunkten

Das Problem in 3D kann ähnlich sein. Anstelle von Reflexscheitelpunkten identifizieren Sie "Kerbkanten". Eine naive Implementierung wäre, Kerbkanten zu identifizieren und wiederholt ebene Schnitte am Polyeder durchzuführen, bis alle Polyeder konvex sind. Weitere Informationen finden Sie unter "Konvexe Partitionen von Polyedern: Ein unterer gebundener und im schlimmsten Fall optimaler Algorithmus" von Bernard Chazelle .

Polyeder mit Kerbe

Beachten Sie, dass dieser Ansatz im schlimmsten Fall eine exponentielle Anzahl von Subpolyedern erzeugen kann. Dies liegt daran, dass Sie solche entarteten Fälle haben könnten:

viele gekerbte Polyeder

Wenn Sie jedoch ein nicht triviales Netz haben (denken Sie an eine holprige Oberfläche), erhalten Sie trotzdem schlechte Ergebnisse. Es ist sehr wahrscheinlich, dass Sie im Voraus eine Menge Vereinfachungen vornehmen möchten, falls Sie dies jemals für komplexe Netze verwenden müssen.

Congusbongus
quelle
6

Die Berechnung einer exakten konvexen Zerlegung einer Oberfläche S ist ein NP-hartes Problem und erzeugt normalerweise eine hohe Anzahl von Clustern. Um diese Einschränkungen zu überwinden, kann die genaue Konvexitätsbeschränkung gelockert werden und stattdessen wird eine ungefähre konvexe Zerlegung von S berechnet. Hier besteht das Ziel darin, eine Partition der Maschendreiecke mit einer minimalen Anzahl von Clustern zu bestimmen und gleichzeitig sicherzustellen, dass jeder Cluster eine Konkavität aufweist, die unter einem benutzerdefinierten Schwellenwert liegt.

Genaue konvexe Zerlegung vs. ungefähre konvexe Zerlegung

Überprüfen Sie die folgenden ungefähren konvexen Zerlegungsbibliotheken: https://code.google.com/p/v-hacd/ http://sourceforge.net/projects/hacd/

khaled
quelle
0

Hier ist ein Code , der Ihnen helfen könnte. Es ist in Java, also müssen Sie es in C ++ konvertieren.

Hier ist auch ein weiterer Artikel , der Ihnen helfen kann


quelle
1
Hallo Masked Rebel, von Antworten nur auf Links wird hier abgeraten. Wenn sich die URL jemals ändert oder die Ressource nicht mehr verfügbar ist, können Antworten, die vollständig vom Link abhängen, für zukünftige Benutzer völlig frei von Lösungen bleiben. Es ist großartig, Links für Gutschriften und weiterführende Literatur bereitzustellen, solange Ihre Antwort für sich allein stehen kann und eine Anleitung zur Lösung des Problems bietet, noch bevor der Leser tiefer klickt. Bitte bearbeiten Sie diese Antwort, um zumindest einen umfassenden Überblick über die Funktionsweise der Lösung zu erhalten, mit der Sie verknüpfen.
DMGregory
@DMGregory Bitte löschen Sie die Antwort, die ich selbst nicht kann.
Die Antwort muss nicht unbedingt gelöscht werden. Wenn Sie es nur bearbeiten, um weitere Informationen aufzunehmen, ist dies möglicherweise eine gute Antwort.
DMGregory
@ DMGregory, aber dann wird es ein Duplikat einer anderen Antwort auf diesen Beitrag sein. Ich werde einfach die andere Antwort bearbeiten und meine Informationen dort ablegen.
Ich nehme an, Sie hatten das Gefühl, etwas Neues hinzuzufügen, als Sie diese Antwort überhaupt geteilt haben. Ich bezweifle nicht, dass Sie den Code, den Sie verlinkt haben, auf eine Weise erklären können, die keine Kopie einer vorhandenen Antwort ist. Wenn Sie es jedoch lieber löschen möchten, steht Ihnen der entsprechende Link auf der Desktop-Version der Site zur Verfügung.
DMGregory