Vertiefende C-Techniken > Virtuelle Produktentwicklung > Design und Styling in der virtuellen Produktentwicklung > Rechnerunterstützung im Designprozess > Systeme und Verfahren zur Weiterverarbeitung der digitalen Rohdaten > Triangulierung von Punktewolken
Anstelle von CAD-Modellen können aber auch triangulierte Flächen1 zur Beschreibung geometrischer Formen Verwendung finden. Im Gegensatz zu einem CAD-Modell lässt sich eine triangulierte Fläche sehr schnell und vollautomatisch aus einer Punktewolke berechnen. Hierzu kann beispielsweise der Triangulierungsalgorithmus von Martin Sundin eingesetzt werden: Zu einem Startpunkt in der Punktewolke sind die benachbarten Punkte zu betrachten. Die Nachbarn zu einem Punkt sind diejenigen Punkte, die in einer Kugel mit kleinem Radius um den Startpunkt enthalten sind. Aus den benachbarten Punkten wird durch Berechnung einer Ausgleichsebene der lokale Flächenverlauf bestimmt. Dies ist zulässig, da sich Flächen, wie sie in der Fertigungstechnik verwendet werden, lokal wie Ebenen verhalten. Innerhalb der Ebene wird ein Startdreieck gewählt. Zu jeder Seite dieses Dreiecks wird in der Punktewolke nach einem Punkt gesucht, der diese Seite zu einem weiteren Dreieck ergänzt. Wendet man diesen Vorgang rekursiv an, so erhält man einen Triangulierungsalgorithmus, der die gewünschte triangulierte Fläche erzeugt. Der Triangulierungsalgoithmus läuft in mehreren Stufen ab, die nachfolgend am Beispiel einer Punktewolke von einer rechten Hand (Bild 1) dargestellt werden: [Wirt-02]
Aus der Punktewolke wird nach der oben skizzierten Methode eine Anfangstriangulierung (Bild 2) berechnet. Die Feinheit dieser Triangulierung hängt von einem Parameter ab, den der Benutzer angeben muss. Der Parameter entspricht dem Radius der Kugel, innerhalb der nach benachbarten Punkten gesucht wird. Je kleiner der Wert dieses Parameters gewählt wird, desto kleiner ist die Kugel und desto feiner wird die Triangulierung. Durch Ausprobieren lässt sich schnell ein guter Kompromiss zwischen hoher Genauigkeit und kleinem Speicherbedarf sowie kurzer Rechenzeit finden. [Wirt-02]
An Stellen, an denen die Punktewolke nicht dicht genug ist, sind eventuell Löcher in der Triangulierung vorhanden. Die Löcher können durch Triangulierung ihres Randes geschlossen werden (Bild 3). [Wirt-02]
Da durch die begrenzte Punktedichte der Digitalisierung die Flächenränder nicht genau erfasst werden können, erscheinen sie ausgefranst. Der nächste Schritt ist deshalb die Glättung der Ränder (Bild 4). [Wirt-02]
In stark gekrümmten Bereichen der Fläche müssen die Dreiecke sehr klein sein, um den Flächenverlauf gut genug zu approximieren. In ebenen Bereichen sollen sie hingegen größer sein, um Speicherplatz und Rechenleistung zu sparen. Der letzte Schritt bei der Triangulierung ist deshalb eine Dezimierung der Dreiecke (Bild 5). Die Rechenzeit für den gesamten Triangulierungsprozess liegt im Bereich weniger Minuten. Die Triangulierung ist daher wesentlich schneller als eine Flächenrückführung. [Wirt-02]
1 triangulierte Fläche: Approximation einer Fläche durch eine Menge zusammenhängender Dreiecke. In Bereichen großer Krümmung werden die Dreiecke kleiner, um dem Krümmungsverlauf der Fläche folgen zu können. In ebenen Bereichen sind die Dreiecke größer, also wird ihre Anzahl kleiner, um eine effiziente Speicherung sicherzustellen. [Wirt-02]