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
vier Verfahren zur Triangulierung, welche im Parameter Method
ausgewählt werden: 'polygon_triangulation' , 'xyz_mapping' ,
'greedy' und 'implicit' .
'polygon_triangulation' ist eine einfache Routine, welche
Polygon-Flächen der bestehenden Oberfläche in dreieckige Flächen umwandelt.
'xyz_mapping' trianguliert die Punkte in 2D anhand eines 2D-Mapping.
Die anderen zwei Verfahren sind
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
='xyz_mapping' , dann werden die Punkte in 2D
anhand eines 2D-Mapping des Objekts ObjectModel3D
trianguliert.
Dabei wird dieselbe Methode benutzt wie in prepare_object_model_3d
für Purpose='segmentation'.
Enthält ObjectModel3D
kein 2D-Mapping, wird ein Fehler geworfen.
Als Nachverarbeitungsschritt können Dreiecke entfernt werden, deren
Normalenrichtung sich stark von einer festgelegten Richtung unterscheiden.
Genauere Informationen zur Anwendung sind in der Beschreibung von
GenParamName
zu finden.
Dies ist dann hilfreich falls die 2D-Nachbarschaft, die zur Triangulierung
verwendet wird, die 3D-Nachbarschaft nicht gut wiedergibt, beispielsweise
wenn entlang der Blickrichtung des Sensors Teile der Oberfläche verdeckt
sind oder die entlang Blickrichtung typischen Störungen auftreten.
Mit GenParamName
und GenParamValue
kann der folgende
zusätzliche Parameter der Map-Triangulierung eingestellt werden:
legt fest, welche Fläche die Löcher in den
Punktkoordinaten haben dürfen, damit diese mittels einer
Delaunay-Triangulierung geschlossen werden. Nur Löcher, die vollständig
von der Bildregion eingeschlossen sind, werden geschlossen. Falls
'xyz_mapping_max_area_holes' auf 0 gesetzt ist, werden
keine Löcher trianguliert. Der Parameter entspricht dem
GenParamName
'max_area_holes' von
prepare_object_model_3d
.
Wertevorschläge:
1, 10,
(Standardwert)
, 100
legt die maximal zulässige Winkeldifferenz zwischen der Normalen der
Dreiecken und der Blickrichtung des Sensors fest. Umso kleiner dieser
Wert gesetzt wird, desto weniger Dreiecke werden zurückgegeben.
Als Blickrichtung des Sensors wird die z-Achse des Koordinatensystems
von ObjectModel3D
angenommen, soweit nicht mittels
GenParamName
eine andere Blickrichtung
('xyz_mapping_max_view_dir_x' ,
'xyz_mapping_max_view_dir_y' ,
'xyz_mapping_max_view_dir_z' ) spezifiziert wird.
Es muss ein Winkel zwischen 0 und 90 Grad gesetzt werden.
Wertevorschläge:
'rad(60)' , 'rad(85)' , 'rad(90)'
(default)
legen die verwendete Blickrichtung des Sensors im Koordinatensystem von
ObjectModel3D
fest, wenn 'xyz_mapping_max_view_angle'
für GenParamName
gesetzt wird. Falls nicht alle drei Richtungen
gleichzeitig gesetzt werden oder die Richtung dem Nullvektor entspricht
wird ein Fehler geworfen.
Wertevorschläge:
[1, 0, 0], [0, 0, 1]
(default)
legt fest, ob alle Eingabepunkte zurückgegeben werden, unabhängig davon
ob sie für die Triangulierung verwendet wurden. Diese Option wird
hauptsächlich aus Gründen der Rückwärtskompatibilität zur Verfügung
gestellt. Wird 'xyz_mapping_output_all_points' auf
'false' gesetzt, werden die alten Punktindizes als das
erweiterte Attribut 'original_point_indices' im 3D-Objekt-Modell
TriangulatedObjectModel3D
abgespeichert. Dieses Attribut
kann daraufhin mit get_object_model_3d_params
abgefragt werden,
oder mit Operatoren weiterverarbeitet werden, welche erweiterte
Attribute verwenden.
Werteliste:
'false' (default)
,
'true'
(1) |
(2) |
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.
ObjectModel3D
(input_control) object_model_3d(-array) →
(handle)
Handle eines 3D-Objektmodells mit 3D-Punktdaten.
Method
(input_control) string →
(string)
Triangulierungsmethode.
Defaultwert: 'greedy'
Werteliste: 'greedy' , 'implicit' , 'polygon_triangulation' , 'xyz_mapping'
GenParamName
(input_control) attribute.name-array →
(string)
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_output_all_points' , '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' , 'xyz_mapping_max_area_holes' , 'xyz_mapping_max_view_angle' , 'xyz_mapping_max_view_dir_x' , 'xyz_mapping_max_view_dir_y' , 'xyz_mapping_max_view_dir_z' , 'xyz_mapping_output_all_points'
GenParamValue
(input_control) attribute.value-array →
(real / integer / string)
Werte der generischen Parameter.
Defaultwert: []
Wertevorschläge: 6, 8, 12, 'true' , 'false' , 'auto' , 'fixed' , 'z_factor' , 'verbose' , 'num_triangles'
TriangulatedObjectModel3D
(output_control) object_model_3d(-array) →
(handle)
Handle des triangulierten 3D-Objektmodells.
Information
(output_control) number(-array) →
(integer / string)
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