Triangulation (area)

Triangulation of an implicit area of gender 3

Triangulation of a parameterized surface ( monkey saddle )

Under triangulation or triangulation of a surface is meant

a) a network of triangles in space that lies on a given surface and partially or completely covers it, or

b) the procedure for generating the points and triangles of such a triangular network.

Here is only generating a triangle mesh described. There are articles in the literature that deal with the optimization of an existing network.

Triangulations are an important tool in

• the visualization of surfaces and
• the application of finite element methods .

The triangulation of a parameterized surface can be obtained by triangulating its domain (see 2nd picture). But the images of these triangles can turn out to be very different in shape and size in the object space, which can limit their use. This deficiency can be reduced with adaptive methods. 3D information (step sizes) is used to triangulate the parameter area.

Triangulating an implicitly given surface ( surface determined by one or more equations) is much more difficult. Most algorithms subdivide the area to be considered (in space) into cuboids and approximate the intersection of the surface with these cuboids using polygons, which then have to be triangulated ( cutting cube method ). The complexity of these algorithms for managing the data is considerable. A simpler in concept algorithm, the tracking algorithm ( marching method ), generated from a starting point, starting first a hexagon of approximately equilateral triangles and added gradually to the predetermined rules always new triangles added, is triangulated to the proposed triangulation area of the surface . In the case of areas with several connected components, however, the tracking algorithm must be run through correspondingly often with suitable starting points, which is not the case with the cutting cube algorithm. I.e. with the tracking algorithm one has to have some idea of ​​the surface to be triangulated, which is usually the case. The cutting cube algorithm automatically detects all components of the surface in the specified starting cube if the corresponding specifications for the subdivision depth are met. Another advantage of the tracking algorithm is the possibility of defining limiting curves (see example).

The polygonalization of surfaces is called meshing in largely English literature . The creation of 4-corner nets is called paving there .

The triangulation of a surface should not be confused with the triangulation of a given discrete flat set of points . See Delaunay triangulation .

• 

  Triangulation: cylinder, surface ${\displaystyle x^{4}+y^{4}+z^{4}=1}$

• 

  Triangulation: cylinder, area , povray image ${\displaystyle x^{4}+y^{4}+z^{4}=1}$

• 

  Torus: triangulated with tracking algorithm

• 

  Torus: cutting cube method, polygonized

See also

• Grid (geometry)
• Geometric modeling

Individual evidence

1. ^ M. Schmidt: Cutting Cubes - visualizing implicit surfaces by adaptive polygonization . Visual Computer (1993) 10, pp. 101-115
2. ↑ J. Bloomenthal: Polygonization of implicit surfaces, Computer Aided Geometric Design (1988), pp. 341-355
3. ↑ CDKG: Computer- assisted Descriptive and Constructive Geometry (TU Darmstadt) (PDF; 3.4 MB), p. 187
4. ^ E. Hartmann: A marching method for the triangulation of surfaces , The Visual Computer (1998), 14, pp. 95-108
5. ↑ S. Akkouche & E Galin: Adaptive Implicit Surface Polygonization Using Marching Triangles , COMPUTER GRAPHICS forum (2001), Vol. 20, pp. 67-80

Web links

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