Surface triangulation on:
[Wikipedia]
[Google]
[Amazon]
Triangulation of a
File:Triang-cyl-sph4.svg, Triangulation: cylinder, surface
File:Triang-cyl-sph4-pov.png, Triangulation: cylinder, surface {{math, 1=''x''{{sup, 4 + ''y''{{sup, 4 + ''z''{{sup, 4 = 1,
File:Torus-triang.svg, Torus: triangulated by the marching method
File:Torus-cutting-cube.svg, Torus: polygonized by the cutting cube method
Surface reconstruction tutorial
an
in the
Triangulation of a surface
A surface, as the term is most generally used, is the outermost or uppermost layer of a physical object or space. It is the portion or region of the object that can first be perceived by an observer using the senses of sight and touch, and is ...
means
* a ''net'' of triangles, which covers a given surface partly or totally, ''or''
* the ''procedure'' of generating the points and triangles of such a net of triangles.
Approaches
This article describes the generation of a net of triangles. In literature there are contributions which deal with the optimization of a given net. Surface triangulations are important for * visualizing surfaces and * the application offinite element method
The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat ...
s.
The triangulation of a ''parametrically'' defined surface is simply achieved by triangulating the area of definition (see second figure, depicting the Monkey Saddle). However, the triangles may vary in shape and extension in object space, posing a potential drawback. This can be minimized through adaptive methods that consider step width while triangulating the parameter area.
To triangulate an ''implicit surface
In mathematics, an implicit surface is a surface in Euclidean space defined by an equation
: F(x,y,z)=0.
An ''implicit surface'' is the set of zeros of a function of three variables. ''Implicit'' means that the equation is not solved for ...
'' (defined by one or more equations) is more difficult.
There exist essentially two methods.
* One method divides the 3D region of consideration into cubes and determines the intersections of the surface with the edges of the cubes in order to get polygons on the surface, which thereafter have to be triangulated (''cutting cube method''). The expenditure for managing the data is great.
* The second and simpler concept is the ''marching method''.S. Akkouche & E Galin: ''Adaptive Implicit Surface Polygonization Using Marching Triangles'', COMPUTER GRAPHICS forum (2001), Vol. 20, pp. 67–80 The triangulation starts with a triangulated hexagon at a starting point. This hexagon is then surrounded by new triangles, following given rules, until the surface of consideration is triangulated. If the surface consists of several components, the algorithm has to be started several times using suitable starting points.
The cutting cube algorithm determines, at the same time, all components of the surface within the surrounding starting cube depending on prescribed limit parameters. An advantage of the marching method is the possibility to prescribe boundaries (see picture).
Polygonizing a surface means to generate a polygon mesh
In 3D computer graphics and solid modeling, a polygon mesh is a collection of , s and s that defines the shape of a polyhedral object. The faces usually consist of triangles ( triangle mesh), quadrilaterals (quads), or other simple convex p ...
.
The triangulation of a surface should not be confused with the triangulation of a discrete prescribed plane ''set of points''. See Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...
.
POV-Ray
The Persistence of Vision Ray Tracer, most commonly acronymed as POV-Ray, is a cross-platform ray-tracing program that generates images from a text-based scene description. It was originally based on DKBTrace, written by David Kirk Buck and Aaro ...
image
See also
*Computer-aided design
Computer-aided design (CAD) is the use of computers (or ) to aid in the creation, modification, analysis, or optimization of a design. This software is used to increase the productivity of the designer, improve the quality of design, improve co ...
* Mesh generation
Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells.
Often these cells form a simplicial complex.
Usually the cells partition the geometric input domain. ...
* Tessellation (computer graphics)
In computer graphics, tessellation refers to the dividing of datasets of polygons (sometimes called ''vertex sets'') presenting objects in a scene into suitable structures for rendering. Especially for real-time rendering, data is tessellated ...
* Marching cubes
Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three-dimensional discrete scalar field (the elements of which are sometim ...
* Point set triangulation
A triangulation of a set of points \mathcal in the Euclidean space \mathbb^d is a simplicial complex that covers the convex hull of \mathcal, and whose vertices belong to \mathcal. In the plane (when \mathcal is a set of points in \mathbb^2), tri ...
References
External links
*Tasso Karkanis & A. James Stewart: ''Curvature-Dependent Triangulation of Implicit Surfaces'Software
Surface reconstruction tutorial
an
in the
Point Cloud Library
The Point Cloud Library (PCL) is an open-source library of algorithms for point cloud processing tasks and 3D geometry processing, such as occur in three-dimensional computer vision. The library contains algorithms for filtering, feature estimatio ...
Surfaces
Computer-aided design
Finite element method