| Operatoren |
triangulate_object_model_3d — Erstellen einer Oberflächentriangulierung eines 3D-Objekt-Modells.
triangulate_object_model_3d( : : ObjectModel3D, Method, GenParamName, GenParamValue : TriangulatedObjectModel3D, Information)
Der Operator triangulate_object_model_3d erstellt eine Oberfläche aus dreieckigen Flächen für das 3D-Objekt-Modell ObjectModel3D und liefert die dadurch entstandene Oberfläche in TriangulatedObjectModel3D zurück. Zur Zeit bietet der Operator drei Verfahren zur Triangulierung, welche im Parameter Method ausgewählt werden: 'polygon_triangulation', 'greedy' und 'implicit'. Während 'polygon_triangulation' eine einfache Routine ist, welche Polygon-Flächen der bestehenden Oberfläche in dreieckige Flächen umwandelt, sind die anderen zwei Verfahren eher komplexer. Bei ihnen wird eine Oberfläche aus reinen 3D-Punktdaten berechnet, wobei die Oberflächentopologie unbekannt ist. Ein detaillierter Vergleich der 'greedy' und 'implicit' Algorithmen kann weiter unten im Paragraph "Vergleich der Triangulierungsmethode" nachgelesen werden.
Wenn Method='polygon_triangulation', dann werden alle Polygonen des Objekts ObjectModel3D trianguliert. Für dieses Verfahren werden keine generische Parameter unterstützt.
Wenn Method='greedy', dann wird der so genannte 'greedy' (gierig) Triangulierungsalgorithmus aufgerufen. Dieser Algorithmus braucht 3D-Punktdaten mit Normalen. Wenn die Normalen nicht im ObjectModel3D vorhanden sind, werden sie vorher intern berechnet. Die Durchführung erfolgt mit der gleichen Methode wie in surface_normals_object_model_3d unter Verwendung der Defaultwerte. Der Triangulierungsalgorithmus baut eine Oberfläche, welche durch die einzelnen Punkte verläuft und deren Orientierung mit der Orientierung der entsprechenden Punktnormale bis auf eine bestimmte Toleranz übereinstimmt. Die Oberfläche wird aus einzelnen dreieckigen Flächen zusammengesetzt, welche Dreiergruppen von benachbarten Punkten verbinden. Um bestimmen zu können, welche Dreiergruppen sich für ein Oberflächendreieck eignen, verwendet der Algorithmus einen lokalen Nachbarschaftstest. Er wird surface neighborhood criteria (SNC), bzw. Nachbarschaftsbedingungen innerhalb einer Oberfläche genannt:
Liegt ein Punkt P auf einer Oberfläche mit Orientierung (Normale) N, dann kann angenommen werden, dass der Punkt P' mit der Normale N' auch auf dieser Oberfläche liegt, wenn:
Der Abstand zwischen beiden Punkten ist kleiner gleich r, d.h.,
Beide Normalen sind ähnlich orientiert, d.h. der Winkel dazwischen ist oder auch, wenn keine strenge Konsistenz der Normalen erforderlich ist,
Der Vektor ist möglichst orthogonal zu der Normale N, d.h. der Winkel ist
Wenn P' die 3. Regel nicht erfüllt dafür aber nicht weiter als d von der durch [P,N] definierten Ebene liegt, wird der Punkt trotzdem akzeptiert.
Die vier Parameter r (siehe 'greedy_radius_type' und 'greedy_radius_value'), (siehe 'greedy_neigh_orient_tol'), (siehe 'greedy_neigh_latitude_tol') und d (siehe 'greedy_neigh_vertical_tol') steuern die Nachbarschaftsbedingunen SNC und haben die folgenden Bedeutungen:
Der Parameter steuert im Grunde genommen die Krümmung der generierten Oberfläche: niedrigere -Werte ergeben eine - lokal betrachtet - flachere Oberfläche.
Die anderen drei Parameter definieren den Anteil einer Kugel, in deren innerem Raum alle Punkte gültige SNC Nachbarn des Kugelzentrums sind. Die Kugel hat einen Radius von r, ihr Zentrum liegt in P und ihr Äquatorebene entspricht der Ebene [P,N]. Nur Punkte innerhalb r können als Nachbarn betrachtet werden (1. SNC-Regel). Die weiteren Voraussetzungen diese Punkte als gültige SNC-Nachbarn zu erkennen sind: sie müssen entweder einen Breitengrad (im Sinne einer "geographischen" Breite) innerhalb des Bereichs [-; ] relativ zu der Äquator haben (2. SNC-Regel), oder sie müssen innerhalb einer Schicht beiderseits des Äquators, bzw. nicht weiter als d von ihm entfernt liegen (4. SNC-Regel).
Der Parameter r verhindert, dass der Algorithmus zu große Dreiecke erzeugt. Das ist insbesondere dann wichtig, wenn die Punkte entweder mehrere einzelne, getrennte Oberflächen, oder Oberflächen mit nicht zu schließenden Lücken darstellen. Das von definierte Breitengradfenster erlaubt, dass Punkte, die auf Grund von Rauschen oder Oberflächenkrümmung außerhalb der Ebene [P,N] liegen, auch als Nachbarn in Betracht gezogen werden. Ähnlich erlaubt der Parameter d, dass Punkte, welche knapp ober- oder unterhalb der Äquatorebene liegen, auch als Nachbarn betrachtet werden können. Letzteres ist wichtig, um Probleme auf Grund von Datenrauschen zu vermeiden.
Hier werden einige Hinweise angeboten, wie man die einzelne Parameter einstellen kann:
Wenn die resultierende Oberfläche zu unterbrochen oder lückenhaft aussieht, dann könnte das ein Hinweis dafür sein, dass r zu niedrig ist. Ein höherer Wert von r sollte diese Probleme lösen.
Wenn die Normalen im ObjectModel3D verrauscht sind (d.h. die Normalen benachbarter Punkten weichen stark voneinander ab), dann ist normalerweise der Wert von zu erhöhen. Es gibt zwei mögliche und typische Quellen für verrauschte Normalen. Die eine liegt an Ungenauigkeiten verursacht von dem ursprünglichen Sensor, von dem die 3D-Punkte, bzw. -Normalen stammen. Die zweite ist eine ungenaue Normalenberechnung in einer Routine, die verwendet wurde, um die Normalen aus den reinen Punktdaten zu berechnen.
Die Punkte können eine Oberfläche mit sehr starker Krümmung darstellen, d.h. die Oberfläche weist eine sehr feine Struktur auf, z.B., sind kleine Dellen, feine Wellen, Falten oder scharfe Kanten zu erkennen. Dann sollen typischerweise die Parameter und/oder erhöht werden.
Umgekehrt kann die Oberfläche eher flach aussehen, dafür aber viele Ausreißer haben (d.h. Punkte welche nah an der Oberfläche liegen, dafür aber eine komplett falsche Orientierung haben und deswegen nicht zu der Oberfläche gehören). Dann soll typischerweise der Parameter niedriger gestellt werden, um die Ausreißer aus der Oberflächengenerierung auszuschließen.
Wenn die Punkte sehr verrauscht sind und eher eine breite Schicht formen als eine eindeutige glatte Oberfläche, dann sollen und/oder d erhöht werden. Damit können auch Punkte außerhalb der optimalen [P,N]-Ebene immer noch als Nachbarn von P angenommen werden.
Umgekehrt, wenn die Daten eher rauschfrei sind, dafür aber zwei Oberflächen sehr nah parallel aneinander (z.B. Oberflächen welche beide Seiten eines flachen Objekts darstellen) verlaufen, dann sollen typischerweise und d niedriger eingestellt werden, sodass sich beide Oberflächen nicht gegenseitig stören.
Der Greedy-Triangulalierungs-Algorithmus fängt mit der Initialisierung einer Oberfläche an, indem er ein erstes Dreieck aus drei SNC-geeigneten, benachbarten Punkten bildet. Weisen alle gültigen Nachbarschaften lokale Inkonsistenzen wie kollineare oder 'doppelte' Punkte auf, wird ein Fehler geworfen. Ein vorangehender Aufruf von sample_object_model_3d mit Method 'fast' und kleiner SampleDistance wird die lokalen Inkonsistenzen von ObjectModel3D in den meisten Fällen beseitigen. Ist ein erstes Dreieck gebildet, setzt der Algorithmus "gierig" immer ein neues Dreieck dazu, wenn er von einem beliebigen Punkt am Oberflächenrand einen neuen Punkt nach dem SNC-Regeln erreichen kann. Wenn keine neue Punkte nach diesen Regeln erreicht werden können, es aber immer noch Punkte gibt, welche noch gar nicht angefasst worden sind, dann wird eine neue Oberfläche initialisiert. Da die SNC-Regeln lediglich nur in für eine vergleichsweise kleine lokale Nachbarschaft einzelner Punkte definiert sind, kann die resultierende Oberfläche globale, topologische Artefakte aufweisen wie, z.B., Lücken oder Flips. Letztere entstehen, wenn die Oberfläche sich selber trifft während sie wächst, allerdings mit invertierter Orientierung beiderseits der Trefffront (die Oberfläche ist irgendwo entlang ihres Wachstumsverlaufs "geflippt"). Diese Artefakte werden in zwei Nachbearbeitungsstufen behandelt: hole filling, bzw. flip resolval.
Zum Schluss kann noch zusätzlich mesh morphology auf die resultierende Oberfläche angewendet werden, um Artefakte am Oberflächenrand zu eliminieren. Die Mesh-Morphologie besteht aus einigen Erosions- und einigen Dilatationsschleifen. Jede Erosionschleife trägt alle Dreiecke ab, die von allen Oberflächenrändern direkt erreichbar sind. Damit schrumpft die Oberfläche zusammen. Im Nachhinein werden mit jeder Dilatationsschleife alle gerade abgetragenen Dreiecke außerhalb der zusammengeschrumpften Ränder, die direkt von den Rändern erreichbar sind, wieder angeschlossen. Es ist zu beachten, dass Dreiecke welche vor dem Anfang der Morphologie (d.h. vor der ersten Erosionsschleife) gar nicht existiert haben, von einer Dilatationsschleife auch nicht generiert werden können. Werden die ursprünglichen Oberflächenränder einmal von der Dilatation erreicht, so kann diese keine weitere Schleifen erzeugen. Deswegen kann die Anzahl der Dilatationsschleifen nicht höher sein als die der Erosionsschleifen. Die Anwendung von Mesh-Erosion und anschließend Mesh-Dilatation ist analog zu den HALCON üblichen Region-Opening. Zusätzlich gehört zu der Mesh-Morphologie auch ein Schritt, in welchem alle Oberflächen beseitigt werden, wenn die Anzahl ihrer Dreiecke unter einer bestimmten Schwelle liegt.
Die einzelnen Schritte des Algorithmus sind hier zusammengefasst.
Triangulierung aller Punkte, die durch SNC erreichbar sind
Hole filling (siehe 'greedy_hole_filling')
Flip resolval (siehe 'greedy_fix_flips')
Mesh-Morphologie (siehe 'greedy_mesh_erosion', 'greedy_mesh_dilation' und 'greedy_remove_small_surfaces')
Mit GenParamName und GenParamValue können die folgenden zusätzlichen Parameternamen und -werte des Greedy-Algorithmus eingestellt werden:
setzt die Anzahl k der zu betrachtenden Nachbarn. Der Algorithmus betrachtet nur die nächsten k-Nachbarn eines Punkts, um von diesen die SNC-Nachbarn zu ermitteln.
Wertevorschläge: 20, 30, 40 (Standardwert), 50, 60
wenn 'greedy_radius_type'='fixed', dann stellt 'greedy_radius_value' den SNC-Radius r in Metereinheiten ein.
Wenn 'greedy_radius_type'='z_factor', dann wird r für jeden Punkt P berechnet, indem die Z-Koordinate des Punkts mit dem Wert des Parameters 'greedy_radius_value' multipliziert wird. Diese Darstellung von r ist besser für Daten geeignet, bei welchen die Punktdichte mit dem Abstand von dem Sensor, mit welchem die Punkte aufgenommen wurden, korreliert. Das ist typischerweise der Fall bei der Verwendung von TOF-Kameras.
Wenn 'greedy_radius_type'='auto', dann wird intern vom Algorithmus entschieden, ob ein Radius vom Typ 'fixed' oder 'z_factor' besser für die Daten geeignet ist. Der Radius wird auch intern geschätzt und mit dem vom Benutzer eingegebenen Wert des Parameters 'greedy_radius_value' multipliziert. Dadurch ist 'greedy_radius_value' als Faktor einsetzbar, um den geschätzten Radius bei Bedarf zu korrigieren.
Werteliste: 'auto' (Standardwert), 'fixed', 'z_factor'
siehe 'greedy_radius_type'.
Wertevorschläge: 0.01, 0.05, 0.5, 0.66, 1.0, 1.5, 2.0, 3.0, 4.0
setzt den SNC-Parameter in Gradeinheiten. steuert die Oberflächenkrümmung (siehe die oben definierten SNC-Regeln).
Wertevorschläge: 10, 20, 30 (Standardwert), 40
erzwingt, dass die Normalen von zwei SNC-benachbarten Punkte eine ähnliche Orientierung haben müssen (d.h. sie zeigen nicht in Gegenrichtungen). Wenn dieser Parameter freigeschaltet ist, wird der zweite Teil der 2. SNC-Regel entkräftet, d.h. wenn dann können beide Punkte nicht als SNC-Nachbarn betrachtet werden selbst wenn .
Werteliste: 'true', 'false' (Standardwert)
setzt den SNC-Parameter in Gradeinheiten. steuert die Größe des Breitengradfensters (siehe die oben definierten SNC-Regeln).
Wertevorschläge: 10, 20, 30 (Standardwert), 40
setzt den SNC-Parameter d als Multiplikationsfaktor relativ zum Radiuswert r.
Wertevorschläge: 0.01, 0.1 (Standardwert), 0.2, 0.3
setzt die maximale Länge der Oberflächenränder (als Anzahl von Punkten), welche zum Schließen von Lücken in Betracht gezogen werden müssen. Wenn 'greedy_hole_filling'='false', dann wird das Lückenschließen deaktiviert.
Wertevorschläge: 'false', 20, 40 (Standardwert), 60
aktiviert/deaktiviert den Orientierungskorrektur-Schritt des Algorithmus.
Werteliste: 'true' (Standardwert), 'false'
aktiviert/deaktiviert das Vorbereiten gecachter Listen von Nachbarn. Diese Listen enthalten die Indizes der nächsten k Punkte für jeden Punkt. Die Listen tragen erheblich zu der Algorithmusgeschwindigkeit bei, aber sie verursachen einen vergleichsweise hohen Speicherverbrauch (in einer Großenordnung von (O(k*n), wobei k ist der mit 'greedy_kNN' gesetzten Wert und n die Anzahl der Punkte im ObjectModel3D ist). Für größere Punktmengen kann es vorkommen, dass der benötigte Speicher nicht allokiert werden kann. Dann liefert der Operator entsprechend eine Speicher bezogene Fehlermeldung zurück. In solchen Fällen sollen die gecachten Listen deaktiviert werden.
Werteliste: 'true' (Standardwert), 'false'
setzt die Anzahl von Erosionsschleifen, welche im Mesh-Morphologie-Schritt des Algorithmus angewendet werden müssen.
Wertevorschläge: 0 (Standardwert), 1, 2, 3
setzt die Anzahl von Dilatationsschleifen. Die Mesh-Dilatation wird nach der Mesh-Erosion angewendet. Wenn 'greedy_mesh_dilation' einen höheren Wert als 'greedy_mesh_erosion' bekommt, wird der Parameter intern auf den Wert von 'greedy_mesh_erosion' gesetzt.
Wertevorschläge: 0 (Standardwert), 1, 2, 3
steuert die Entfernung kleinerer Oberflächen von dem Endergebnis. Wenn 'greedy_remove_small_surfaces'='false', dann wird die Entfernung deaktiviert. Wenn ein Wert zwischen 0.0 und 1.0 gesetzt wird, dann werden alle Oberflächen entfernt, die weniger Dreiecke haben als 'greedy_remove_small_surfaces'xnum_triangles, wobei num_triangles die gemeinsame Anzahl der Dreiecke in TriangulatedObjectModel3D angibt. Wenn der Wert höher als 1 gesetzt ist, dann werden alle Oberflächen entfernt, die weniger Dreiecke haben als 'greedy_remove_small_surfaces'.
Wertevorschläge: 'false' (Standardwert), 0.01, 0.05, 0.1, 10, 100, 1000, 10000
der Timeout gibt die Möglichkeit den Operator nach einer bestimmten Zeitspanne in Sekunden zu unterbrechen. Das ist insbesondere dann wichtig, wenn eine maximale Zeit der Ausführung unabhängig von dem Ergebnis des Operators zu gewährleisten ist. Die zeitliche Auflösung des Timeout-Mechanismus liegt bei ungefähr 10 ms. Werte kleiner als 0 werden nicht angenommen. Durch das Setzen von 'greedy_timeout' auf 'false' wird der Timeout deaktiviert. Die zeitliche Genauigkeit des Timeouts hängt von vielen Faktoren ab, darunter ist die Größe des Modells, die Geschwindigkeit des Rechners und der 'timer_mode' der über set_system gesetzt wurde.
Wertevorschläge: 'false' (Standardwert), 0.1, 0.5, 1, 10, 100
wenn ein Timeout auftritt, liefert der Operator eine entsprechende Fehlermeldung zurück. Wenn 'greedy_suppress_timeout_error' auf 'true' gesetzt ist, liefert der Operator keine Fehlermeldung mehr, sondern liefert die Zwischenergebnisse der Vermaschung in TriangulatedObjectModel3D zurück. Ob ein Timeout aufgetreten ist, sieht man im Feld 'timeout_occured' des Ausgabeparameters Information (nur im 'verbose'-Modus).
Werteliste: 'false' (Standardwert), 'true'
legt fest welche Informationen in Information zurückgegeben werden. Wenn 'information'='num_triangles' (default), dann wird nur die Anzahl der generierten Dreiecke zurückgeliefert. Wenn 'information'='verbose' wird eine Liste von Name-Wert Paaren zurückgeliefert. Zur Zeit enthalten die Paare die folgenden Informationen:
Name Wert Beschreibung
----------------------- -------------------------------- -------------------------------------------
num_triangles <Anzahl der Dreiecke> berichtet die Anzahl der generierten drei-
eckigen Flächen.
specified_radius_type auto | fixed | z_factor | none berichtet den Radiustyp, der vom Benut-
zer gesetzt wurde.
specified_radius_value <gesetzter Radiuswert> berichtet den Radiuswert, der vom Benut-
zer gesetzt wurde.
used_radius_type fixed | z_factor | sampling berichtet den intern verwendeten Ra-
diustyp; wenn der Benutzer
'specified_radius_type' auf 'auto' setzt,
dann berichtet dieses Feld, was für ein
Radiustyp von dem Algorithmus intern
ausgewählt wurde; wennObjectModel3D
ein 3D-Primitiv ist, dann wird der
vom Benutzer gesetzten Radiuswert in-
tern als Abtastschritt verwendet und
used_radius_typeberichtet 'sampling'.
used_radius_value <interner Radiuswert> berichtet den intern verwendeten
Radiuswert; wenn used_radius_type='fixed',
dann wird der SNC-Nachbarschaftsradius
in Meter berichtet; wenn
used_radius_type='z_factor', dann
wird der Multiplikationsfaktor be-
richtet, welcher benutzt wurde,
um den SNC-Nachbarschaftsradius
aus der Z-Koordinate des Zen-
trumpunkts zu berechnen; wenn
used_radius_type='sampling', dann
wird der Abtastschritt berichtet, der für
die Triangulierung eines 3D-Primitivs ver-
wendet wurde, insbesondere für Zylinder
und Kugel.
neigh_orient_tol <alpha> berichtet den Krümmungsparameter alpha in
Grad, welcher für die Triangulierung ver-
wendet wurde.
neigh_latitude_tol <betta> berichtet den Breitengradtoleranzwinkel beta
in Grad, welcher für die Triangulierung ver-
wendet wurde.
neigh_vertical_tol <d> berichtet den Abstandsparameter d als
Faktor vomused_radius_value.
fix_flips true | false berichtet ob der Orientierungskorrektur-Schritt
aktiviert wurde.
hole_filling false | <max. Lückenumkreis> berichtet 'false', wenn das Lückenschlie-
ßen deaktiviert wurde, ansonsten der maximale
Umkreis (als Anzahl von Punkten), der in Betracht
gezogenen Lücken.
timeout false | <Timeout> berichtet 'false', wenn der Timeout vom
Benutzer deaktiviert wurde, oder die Länge des
aktivierten Timeouts in Sekunden.
timeout_occured yes | no berichtet ob ein Timeout aufgetreten ist.
Werteliste: 'num_triangles' (Standardwert),
'verbose'
Wenn Method='implicit', dann wird ein impliziter Triangulierungsalgorithmus aufgerufen, der auf dem Poisson-Gleichungslöser basiert (siehe die Referenzen). Er erstellt eine wasserdichte Oberfläche, d.h. die Oberfläche ist komplett geschlossen. Die implizite Triangulierung benötigt 3D-Punktdaten mit Normalen. Darüber hinaus, müssen die Normalen streng nach Außen oder nach Innen bezüglich des Raums ausgerichtet sein, der von der zu rekonstruierenden Oberfläche umschlossen wird. Im Gegensatz zum 'greedy'-Algorithmus baut der 'implicit'-Algorithmus die Oberfläche nicht durch die Punkte des Eingabeobjekts ObjectModel3D. Stattdessen erstellt der Algorithmus eine Oberfläche, welche die Punkte approximiert und generiert einen neuen Satz von Punkten, die auf dieser Oberfläche liegen.
Als erstes organisiert der Algorithmus die Punkte in einer adaptiven Octree-Struktur: der Raum der kleinsten umschließenden Quader um die Punkte wird in der Mitte seiner drei Dimensionen in acht Sub-Räume, oder Voxels aufgespalten. Die Voxels, welche immer noch große Punktmenge enthalten, können weiter in acht Subvoxels aufgespalten werden. Die Voxel, die keine oder zu wenig Punkte enthalten, müssen nicht unbedingt weiter aufgespalten werden. Das Spalten entwickelt sich solange rekursiv in Regionen des Raums wo die Punktdaten dichter sind weiter, bis die am feinsten aufgespaltenen Voxels keine oder nur wenige Punkte enthalten. Die Rekursionebene, welche von den kleinsten Voxels erreicht wird, wird als Octree-Tiefe bezeichnet.
Als nächstes berechnet der Algorithmus die Werte einer sogenannten impliziten Indikatorfunktion der Oberfläche. Die Berechnung basiert auf der Annahme, dass die 3D-Punkte des Modells ObjectModel3D auf der Oberfläche eines Körpers liegen und dass die Normalen des Modells bezüglich des Körpers streng nach Außen oder Innen gerichtet sind (siehe die Referenzen). Diese Annahme erklärt auch die Vorgabe, dass die Normalen unbedingt konsistent untereinander sein müssen. Die implizite Funktion hat einen Wert von 1 in Octree-Voxelecken, welche streng innerhalb des Körpers liegen und 0 - wenn sie streng außerhalb des Körpers liegen. Wegen Rauschen kann das für manche Voxelecken nicht eindeutig bestimmt werden und sie bekommen einen Wert zwischen 0 und 1.
Eine implizite Oberfläche, welche durch die implizite Funktion definiert wird, verläuft so, dass alle ihrer Punkte einen Indikatorwert von 0.5 haben. Die 'implicit'-Triangulierung verwendet am Ende einen üblichen Maching Cubes Algorithmus, um die Schnittpunkte zwischen der impliziten Oberfläche und den Seiten der Octree-Voxels zu bestimmen. Die Schnittpunkte werden als neuer 3D-Punktsatz in TriangulatedObjectModel3D zurückgegeben. Als Folge davon wird die Granularität der rekonstruierten Oberfläche im Wesentlichen durch die Auflösung des Octrees bestimmt (d.h., durch seine Tiefe).
Mit GenParamName und GenParamValue können die folgenden zusätzlichen Parameternamen und -werte des 'implicit'-Algorithmus eingestellt werden:
setzt die Tiefe des Octrees. Die Octree-Tiefe bestimmt die Granularität der rekonstruierten Oberfläche - je höher der Tiefenwert ist, desto feiner werden Oberflächendetails rekonstruiert. Die Tiefe hat allerdings einen exponenziellen Einfluss auf den Speicherverbrauch des Verfahrens. Deswegen ist die Octree-Tiefe auf 12 begrenzt.
Wertvorschläge: 5, 6 (Standardwert), 8, 10, 11, 12
Einschränkung: 5 'implicit_octree_depth' 12
aktiviert ein alternatives Verfahren, welches die implizite Funktion bis zu einer benutzerdefinierten Tiefe vorbereitet. Danach übernimmt das Standardverfahren die weitere Berechnungen. Dieser Algorithmus braucht weniger Speicher als der Original, dafür ist er aber etwas langsamer.
Wertvorschläge: 2, 4, 6 (Standardwert), 8, 10, 11, 12
Einschränkung: 'implicit_solver_depth' 'implicit_octree_depth'
setzt die minimale Anzahl der Punkte pro Octree-Voxel. Wenn die Anzahl der Punkte in einem Voxel kleiner als dieser Wert ist, wird das Voxel nicht weiter aufgespalten. Für rauschfreie Daten kann dieser Wert niedriger gesetzt werden (z.B. zwischen 1 und 5), was eine feinere Auflösung des Octrees erlaubt. Für verrauschten Daten soll dieser Wert höher gestellt werden (z.B. 10-20, oder sogar noch höher), um mehrere verrauschten Punkte in einzelnen Voxeln zu sammeln und damit den Einfluss des Rauschens zu minimieren.
Wertvorschläge: 1 (Standardwert), 5, 10, 15, 20, 30
legt fest, welche Informationen in Information zurückgegeben werden. Wenn 'information'='num_triangles' (default), dann wird nur die Anzahl der generierten Dreiecke zurückgeliefert. Wenn 'information'='verbose' wird eine Liste von Name-Wert Paaren zurückgeliefert. Zur Zeit enthalten die Paare die folgenden Informationen:
| Name | Wert | Beschreibung |
|---|---|---|
| num_triangles | <Anzahl der Dreiecke> | berichtet die Anzahl der generierten dreieckigen Flächen. |
| num_points | <Anzahl der Punkte> | berichtet die Anzahl der neu generierten 3D-Punkte. |
Werteliste: 'num_triangles' (Standardwert), 'verbose'
In diesem Paragraph wird ein einfacher Vergleich beider unterstützter Triangulierungsverfahren angeboten:
| Merkmal | Greedy-Triangulierung | Implicit-Triangulierung |
|---|---|---|
| benötigte Daten: | 3D-Punkte mit 3D-Normale | 3D-Punkte mit 3D-Normale, konsistent nach Außen oder Innen ausgerichtet |
| resultierende Oberfläche: | offen, Triangulierung der Eingabepunkte | geschlossen (wasserdicht), Approximierung der Eingabepunkte |
| resultierende Punkte: | die Eingabepunkte bleiben | neue Punkte werden generiert |
| Behandlung des Rauschens: | moderate Punkt- und Normalenrauschen werden adäquat behandelt | Punkt- und Normalenrauschen werden implizit behandelt; moderate and hohe Rauschgrade werden akzeptiert |
| Auflösung der Triangulierung: | explizit, gesteuert durch die SNC-Parameter | implizit, gesteuert durch die Octree-Tiefe und die minimale Anzahl von Punkten pro Voxel |
| Geschwindigkeit: | O(N k log(N)) | O(N D^3) |
| Speicherverbrauch: | O(N k), mit Nachbarschaftscaches | O(D^3) |
| O(N), ohne Nachbarschaftscaches | ||
| wobei: | ||
| N: Anzahl von Punkte | ||
| k: Anzahl der betrachteten Nachbarn | ||
| D: Tiefe des Octrees
|
Je nach Anzahl von Punkten in 'ObjectModel3D', Rauschgrad und spezifischer Struktur der Eingabedaten, liefern beide Triangulierungsverfahren unterschiedliche Ergebnisse und werden mit unterschiedlicher Geschwindigkeit und Speicherverbrauch ausgeführt. Der Greedy-Algorithmus arbeitet schnell, beansprucht wenig Speicher und liefert eine Oberfläche mit großer Detailauflösung zurück wenn die Punktmenge der Eingabe vergleichsweise klein ist (z.B. bis zu 500.000 Punkte). Dadurch, dass der Algorithmus grundsätzlich jeden Punkt anfassen muss, kann seine Geschwindigkeit von der Anzahl der Punkte nicht abgekoppelt werden und der Algorithmus beansprucht mehr Zeit, wenn größere Punktmengen zu behandeln sind. Sollten jedoch solche trotzdem mit dem Greedy-Verfahren trianguliert werden, empfiehlt es sich, sie zuerst mit dem Operator sample_object_model_3d herunterzusampeln.
Im Gegensatz dazu organisiert wie bereits früher erklärt der Implicit-Algorithm die Punktdaten in Octree. Demzufolge werden die Auflösung der Triangulierung, die Geschwindigkeit und der Speicherverbrauch des Algorithmus im Grunde genommen von der Octree-Tiefe bestimmt. Der Nachteil davon ist, dass eine höhere Auflösung der Oberfläche nur auf Kosten von unverhältnismäßig höherer Geschwindigkeit und höherem Speicherverbrauch erzielt werden kann. Der Vorteil der Octree-basierte Triangulierung ist jedoch, dass große Punktmengen effektiv im Octree organisiert werden können (insbesondere bei niedrigen Werten der Octree-Tiefe) und die Kosten der Rekonstruktion hauptsächlich von der Octree-Tiefe und weniger von der Punktmenge abhängig gemacht werden kann. Ein erheblicher Nachteil des Implicit-Algorithmus ist die Forderung nach konsistenten benachbarten Normalen, da diese selten oder nur schwierig von typischen Routinen zur Normalenberechnung zurückgeliefert werden.
Wenn ein 3D-Objektmodell überschrieben werden soll oder es nicht länger benötigt wird, muss der Speicher durch Aufrufen des Operators clear_object_model_3d freigegeben werden.
Handle eines 3D-Objektmodells mit 3D-Punktdaten.
Triangulierungsmethode.
Defaultwert: 'greedy'
Werteliste: 'greedy', 'implicit', 'polygon_triangulation'
Namen der generischen Parameter.
Defaultwert: []
Werteliste: 'greedy_fix_flips', 'greedy_hole_filling', 'greedy_kNN', 'greedy_mesh_dilation', 'greedy_mesh_erosion', 'greedy_neigh_latitude_tol', 'greedy_neigh_orient_consistent', 'greedy_neigh_orient_tol', 'greedy_neigh_vertical_tol', 'greedy_prefetch_neighbors', 'greedy_radius_type', 'greedy_radius_value', 'greedy_remove_small_surfaces', 'greedy_suppress_timeout_error', 'greedy_timeout', 'implicit_min_num_samples', 'implicit_octree_depth', 'implicit_solver_depth', 'information'
Werte der generischen Parameter.
Defaultwert: []
Wertevorschläge: 6, 8, 12, 'true', 'false', 'auto', 'fixed', 'z_factor', 'verbose', 'num_triangles'
Handle des triangulierten 3D-Objektmodells.
Zusätzliche Information über der Triangulierung.
read_object_model_3d, gen_plane_object_model_3d, gen_sphere_object_model_3d, gen_cylinder_object_model_3d, gen_box_object_model_3d, gen_sphere_object_model_3d_center, sample_object_model_3d
write_object_model_3d, render_object_model_3d, project_object_model_3d, simplify_object_model_3d
M. Kazhdan, M. Bolitho, and H. Hoppe: „Poisson Surface Reconstruction.“ Symposium on Geometry Processing (June 2006).
3D Metrology
| Operatoren |