Unter Triangulation oder Triangulierung einer Fläche versteht man
Hier wird ausschließlich die Erzeugung eines Dreiecksnetzes beschrieben. In der Literatur gibt es Beiträge, die sich mit der Optimierung eines vorhandenen Netzes beschäftigen.
Triangulationen sind ein wichtiges Hilfsmittel bei
- der Visualisierung von Flächen und
- der Anwendung von Finite-Elemente-Methoden.
Die Triangulation einer parametrisierten Fläche kann man durch eine Triangulierung ihres Definitionsbereichs erhalten (s. 2. Bild). Aber die Bilder dieser Dreiecke können im Objektraum sehr verschieden in Gestalt und Größe ausfallen, was ihre Verwendung einschränken kann. Diesen Mangel kann man mit adaptiven Methoden verringern. Dabei werden 3D-Informationen (Schrittweiten) zur Triangulierung des Parameterbereichs verwendet.
Die Triangulierung einer implizit gegebenen Fläche (durch eine oder mehrere Gleichungen bestimmte Fläche) ist wesentlich schwieriger. Die meisten Algorithmen unterteilen den zu betrachtenden Bereich (im Raum) in Quader und approximieren den Schnitt der Fläche mit diesen Quadern durch Polygone, die dann noch trianguliert werden müssen (cutting cube method). Der Aufwand dieser Algorithmen zur Verwaltung der Daten ist erheblich. Ein vom Konzept her einfacherer Algorithmus, der Verfolgungs-Algorithmus (marching method), erzeugt von einem Startpunkt ausgehend zunächst ein Sechseck von näherungsweise gleichseitigen Dreiecken und fügt schrittweise nach vorgegebenen Regeln immer wieder neue Dreiecke hinzu, bis der zur Triangulation vorgesehene Bereich der Fläche trianguliert ist. Bei Flächen mit mehreren Zusammenhangskomponenten muss der Verfolgungsalgorithmus allerdings entsprechend oft mit geeigneten Startpunkten durchlaufen werden, was bei dem cutting cube Algorithmus nicht der Fall ist. D. h. beim Verfolgungsalgorithmus muss man schon eine gewisse Vorstellung von der zu triangulierenden Fläche haben, was in der Regel der Fall ist. Der cutting cube Algorithmus entdeckt bei entsprechenden Vorgaben für die Unterteilungstiefe automatisch alle Komponenten der Fläche in dem vorgegebenen Ausgangswürfel. Ein weiterer Vorteil des Verfolgungs-Algorithmus besteht in der Möglichkeit Begrenzungskurven vorzugeben (s. Beispiel).
Polygonalisierung von Flächen wird in der weitgehend englischen Literatur meshing genannt. Die Erzeugung von 4-Ecksnetzen heißt dort paving.
Die Triangulierung einer Fläche sollte nicht verwechselt werden mit der Triangulierung einer vorgegebenen diskreten ebenen Punktmenge. Siehe Delaunay-Triangulation.
Siehe auch Bearbeiten
Einzelnachweise Bearbeiten
- M. Schmidt: Cutting Cubes - visualizing implicit surfaces by adaptive polygonization. Visual Computer (1993) 10, S. 101–115
- J. Bloomenthal: Polygonization of implicit surfaces, Computer Aided Geometric Design (1988), S. 341–355
- CDKG: Computerunterstützte Darstellende und Konstruktive Geometrie (TU Darmstadt) (PDF; 3,4 MB), S. 187
- E. Hartmann: A marching method for the triangulation of surfaces, The Visual Computer (1998), 14, S. 95–108
- S. Akkouche & E Galin: Adaptive Implicit Surface Polygonization Using Marching Triangles, COMPUTER GRAPHICS forum (2001), Vol. 20, S. 67–80
Weblinks Bearbeiten
- E. Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN, S. 81
- Tasso Karkanis & A. James Stewart: Curvature-Dependent Triangulation of Implicit Surfaces [1]