Tetgen Triangulation

[Ein ehemaliger Benutzer]

Danke,
aber das haben die doch in "Tetgen" schon implementiert...
Wollte mir doch die Arbeit sparen das selber zu programmieren...
Kennt eventuell jemand ne andere (gute, brauchbare) Library, die aus Punktewolken ein Dreiecksnetz rekonstruiert ?

[Gast25250]

Frei im Netz:

Nina Amenta: The PowerCrust
Tamal Dey: Robust/Tight Cocone
Ohtake and Belayev: Multi Level Partition of Unity Implicit (MPU)
Ohtake and Belayev: An Integrating Approach to Meshing Scattered Point Data (QPoly)
Kazhdan and Hoppe: Poisson Surface Reconstruction

Zeig mir doch mal deine Punkewolke, dann kann ich dir sagen, welche Verfahren dafür geeignet sind.

Gruss, Jochen

[Ein ehemaliger Benutzer]

Danke Jochen,
für deine interessante Antwort....

Wir haben einen Roboter, der seine Umgebung bzw. einen Ausschnitt seiner Umgebung mit einem Laserschnitt-Triangulationsverfahren abtastet und eine Punktewolke zurückgibt.
Aus dieser müssen Objekte und deren Lage bestimmt werden.
Das Verfahren, welches Ich verwenden möchte, braucht Normalen der Punkte und eine Topologie (Zusammenhangsbeschreibung, welcher Knoten ist mit welchem verbunden) um die zu bestimmten Knoten adjazenten(verbundenen) Nachbarn zu bestimmen.

Deshalb wollte ich eine Oberflächenrekonstruktion durchführen um aus den Normalen der Facetten die Normalen der Knoten zu mitteln.

Habe jetzt zwar keine konkrete Punktewolke angegeben aber ich hoffe das hilft dir weiter...

Was bei der Wahl der Rekonstruktionssoftware ausschlaggebend sein könnte, ist die Tatsache, dass die Punktediche nicht konstant sein wird.
Ausserdem begrenzt die Punktewolke Objekte nicht vollständig, da sie ja nur aus einer Richtung aufgenommen wird. Zusätzlich hat die Punktewolke Grenzen die aus dem begrenzten Abtastungsauschnitt resultieren.

Hoffe das war jetzt nicht zuviel Info auf einmal.

Werde mir jetzt mal deine Vorschläge zu Gemüte führen.
Danke nochmal...

[Gast25250]

Hmmm, das ist natürlich maximal schwierig.

Somit bleibt von den erwähnten Verfahren nur noch

* Ohtake and Belayev: An Integrating Approach to Meshing Scattered Point Data (QPoly)

Lad dir einfach mal das Prog down und versuchs damit, mach dir aber keine zu große Hoffnung.

Ein anderes Verfahren das mir da gerade einfällt wäre
"A Surface Reconstruction Method for Highly Noisy Point Clouds" von DanFeng Lu et. al. Davon habe ich jedoch keine Implementierung.

Mit etwas (oder viel) Glück bringt dir auch das Verfahren von Gopi et. al "Surface Reconstruction based on Lower Dimensional Localized Delaunay Triangulation" was, glaube ich aber nur bedingt.

Für die Normalen der Punkte brauchst du übrigens keine Triangulierung der Punktewolke.

Wenn du mal Daten hast, kannst du sie mir schicken und ich kann mal probieren sie zu rekonstruieren.

Gruss, Jochen

[huckfinn]

Es gibt ein Tool aus dem Tetgen offensichtlich entwickelt wurde zumindest ist die Syntax der Kommandozeile ähnlich. Der Entwickler ist Jonathan Shewchuk und das Teil heißt Triangle. Es ist allerdings in ANSI-C geschrieben und wird in der GTS benutzt. Hier der Link:
http://www.cs.cmu.edu/~quake/triangle.html
Gruß huck

[Ein ehemaliger Benutzer]

Danke dir huckfinn...
Aber das Ding scheint nur auf zweidimensionalen Punktewolken zu arbeiten.
Meine Daten sind aber dreidimensional...

mfG

[huckfinn]

Na ja Oberflächenbaut das Ding schon, aber die Z Koordiante wird nur als Attribut angehängt. Mit Triangle habe ich schon gearbeitet und DGM's interpoliert.

Es gibt eine Bibliothek mit Beispielen, die auf das Triangle-Program zurückgreift und genau das tut was du willst ..hoffe ich

GNU Triangulated Surface Library:
http://gts.sourceforge.net/

Bis denne Huck

[Ein ehemaliger Benutzer]

Ok nehmen wir mal an ich benutze Triangle.
Da ich die Punktewolke von einer festen Position aufnehme, kann man die Tiefeninformation bei der Triangulation doch vernachlässigen, oder ?

D.h. ich projeziere die Punkte auf die x-y-Ebene, führe mit Triangle die Triangulation der Punktewolke durch und verschiebe die Punkte anschließend wieder auf ihre Ursprungsposition.

Was haltet ihr davon ?

@Gast25250: Dass ich für die Normalen keine Triangulation brauch weiss ich schon. Ich kann ja die Hauptkomponentenanalyse durchführen, aber dafür muss ich die eine sinnvolle Anzahl von k nächsten Nachbarn bestimmen, was mir etwas kompliziert erscheint. Aber auch diese Möglichkeit ziehe ich in Erwägung. Möchte es jetzt erstmal mit oben genannter Methode versuchen.

mfG

Blue

[huckfinn]

Ich denke, daß du mal erklären mußt was du mit "Organisation" der Oberfläche über Polygone meinst. Wenn ich ein DGM habe gehe ich davon aus, daß die Punkte über der Ebene x-y die Oberfläche bilden und, die Triangulation "nur" auf die Gestalt des Meshes in der X-Y Ebene zutrifft.

Dabei gibt es Einschränkungen für das Resultat z.B. Überhänge (akonvexe Teile) werden immer in die x-y Ebene zurückprojeziert und verschwinden. Wenn man die Polygone nimmt die irgenwie in einem Raum liegen und in eine 2D Ebene abbildet verliert man meiner Meinung nach die Metrik für die Delauay-Bedingung.

Gruß Huck

[huckfinn]

Sorry ich habe mir jetzt erst den Lex mit dem Roboter durchgelesen. Man kann davon ausgehen, daß eine Zentralprojktion für die Punktwolke vorliegt. Wenn man die Kugelquadranten als Fallunterscheidung beachetet sollte dein Vorschlag funktionieren ..in der Geodäsie und Kartenentwurfslehre wird nichts anderes getan.

Gruß Huck