Computergeometrie - Triangulation

7

Ich versuche, komplexe 3D-Objekte zu triangulieren, die möglicherweise Löcher aufweisen. Jetzt habe ich versucht, das Problem selbst zu lösen. Nach ein paar Stunden habe ich nichts bekommen, was die ganze Zeit funktionieren würde. Also habe ich mich umgesehen und ohne viel Glück. Kennt jemand irgendwelche Algorithmen oder freien Bibliotheken, die meinen Bedürfnissen entsprechen würden? Links zu relevanten Dokumentationen sind ebenfalls willkommen.

Außerdem bin ich ein autodidaktischer Programmierer / CS-Tist.

Ich habe eine Reihe von Punkten und muss einer Spiel-Engine die Form in Dreiecken zur Verfügung stellen. Ich erhalte diese Punkte aus einer Form und füge dann Punkte hinzu, um Fläche hinzuzufügen, Fläche zu subtrahieren oder die Form zu teilen. Nach dem Ändern / Hinzufügen von Punkten muss ich der Spiel-Engine die Form in Dreiecken sowie andere Informationen geben. Löcher können überall in jeder Form sein.

computational-geometry triangulation Aaron
quelle
Können Sie erweitern, was Sie unter "komplexen 3D-Objekten" verstehen? Wie repräsentieren Sie die Objekte aktuell?
Nathan Reed
Haben Sie es nur mit geschlossenen Oberflächen mit Löchern (wie einem Bagel oder Donut) oder auch mit Löchern zu tun, die zum Inneren der Oberfläche führen (wie einer Kugel mit einem nach innen führenden Loch)?
Trichoplax
Eine bestimmte Sammlung von Punkten kann zu einer Vielzahl unterschiedlicher Formoberflächen verbunden werden. Können Sie erklären, wie diese Punkte erzeugt werden oder wie sie sich auf die beabsichtigte Oberfläche beziehen?
Trichoplax
Würde es für Sie funktionieren , einen Algorithmus wie das Würfeln von Würfeln über ein Dichtefeld zu verwenden? Sie können ein Dichtefeld mit Beiträgen der Punkte füllen und daraus eine Stichprobe erstellen.
Porglezomp

Antworten:

5

Was es bedeutet, "komplexe 3D-Objekte zu triangulieren", ist nicht eindeutig. Nur eine mögliche Interpretation: Sie haben ein 3D-Polygon im Raum und möchten dieses triangulieren. Das ist NP-schwer:

Barequet, Gill, Matthew Dickerson und David Eppstein. "Über das Triangulieren dreidimensionaler Polygone." Vorträge des 12. Symposiums für Computational Geometry . ACM, 1996. ( ACM-Link .)

         

Joseph O'Rourke
quelle