Triangulation (Fläche)

Triangulation einer impliziten Fläche vom Geschlecht 3

Triangulation einer parametrisierten Fläche (Affensattel)

Unter Triangulation oder Triangulierung einer Fläche versteht man

a) ein Netz von Dreiecken im Raum, das auf einer vorgegebenen Fläche liegt und diese teilweise oder vollständig überdeckt, oder

b) die Prozedur der Erzeugung der Punkte und Dreiecke eines solchen Dreiecks-Netzes.

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.

• 
  Triangulation: Zylinder, Fläche $x^{4}+y^{4}+z^{4}=1$
• 
  Triangulation: Zylinder, Fläche $x^{4}+y^{4}+z^{4}=1$, povray-Bild

• 
  Torus: mit Verfolgungsalgorithmus trianguliert
• 
  Torus: cutting cube Methode, polygonisiert

Spezielle Triangulierungen

Man kann Triangulierungen noch weiter Klassifizieren und ist vor allem in den Numerischen Brechung (wie zum Beispiel Finite Elemente Methode) wichtig:

Zulässige Triangulierung

Eine zulässige Triangulierung wird folgendermassen Definiert:
Eine Triangulierung ${\mathcal {T}}=\left\{{\mathit {T}}_{1},{\mathit {T}}_{2},...,{\mathit {T}}_{M}\right\}$ heisst zulässig fals gilt:

1. Besteht der Durchschnitt ${\mathit {T}}_{i}\cap {\mathit {T}}_{i}$ genau aus einem Punkt, so ist dieser Punkt ein Eckpunkt von ${\mathit {T}}_{i}$ und von ${\mathit {T}}_{j}$
2. Besteht der Durchschnitt ${\mathit {T}}_{i}\cap {\mathit {T}}_{i}$ für $i\neq j$ aus mehr als einem Punkt, so ist ${\mathit {T}}_{i}\cap {\mathit {T}}_{j}$ eine Kante von ${\mathit {T}}_{i}$ und ${\mathit {T}}_{j}$.

Alternativ gibt es auch folgende Definition:
Eine Zerlegung ${\mathcal {T}}=\left\{{\mathit {T}}_{1},{\mathit {T}}_{2},...,{\mathit {T}}_{M}\right\}$ des Gebiets $\Omega$ heisst zulässig wenn folgendes erfüllt ist:

1. ${\overline {\Omega }}=\bigcup _{i=1}^{M}{\mathit {T}}_{i}$
2. Besteht der Durchschnitt ${\mathit {T}}_{i}\cap {\mathit {T}}_{i}$ genau aus einem Punkt, so ist dieser Punkt ein Eckpunkt von ${\mathit {T}}_{i}$ und von ${\mathit {T}}_{j}$
3. Besteht der Durchschnitt ${\mathit {T}}_{i}\cap {\mathit {T}}_{i}$ für $i\neq j$ aus mehr als einem Punkt, so ist ${\mathit {T}}_{i}\cap {\mathit {T}}_{j}$ eine Kante von ${\mathit {T}}_{i}$ und ${\mathit {T}}_{j}$.

Dabei ist ${\overline {\Omega }}$ der Abschluss von $\Omega$ und $\bigcup _{i=1}^{M}{\mathit {T}}_{i}$ die Vereinigung der Elemente ${\mathit {T}}_{i}$ von $i=1$ bis $M$ ist.

Quasiuniforme Triangulierung

Die Familie von Triangulerungen ${\mathcal {T}}_{h}$ heisst quasiuniform, wenn es eine Zahl $\mathrm {K} >0$ gibt so dass jedes ${\mathit {T}}\in {\mathcal {T}}_{h}$ gilt $\mathrm {K} \geq {\frac {h_{T}}{\rho _{T}}}$. Dabei sind $h_{T}$ der halbe Durchmessers von ${\mathit {T}}$ und $\rho _{T}$ der Innendurchmesser des Elements ${\mathit {T}}$.

Uniforme Triangulierung

Die Familie von Triangulerungen ${\mathcal {T}}_{h}$ heisst uniform, wenn es eine Zahl $\mathrm {K} >0$ gibt so dass jedes ${\mathit {T}}\in {\mathcal {T}}_{h}$ gilt $\mathrm {K} \geq {\frac {h}{\rho _{T}}}$. Wobei $h$ die Gitterweite ist.

Siehe auch

• Gitter (Geometrie)
• Geometrische Modellierung

Weblinks

• E. Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN, S. 81
• Tasso Karkanis & A. James Stewart: Curvature-Dependent Triangulation of Implicit Surfaces [1]