Zerlegen eines konkaven Netzes in einen Satz konvexer Netze

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?

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 ).

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:

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):

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 .

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:

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.

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.

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

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