22.3. 22.3 Geometry processing and tessellation algorithms

In Section 22.2 we met free-form surface and curve definition methods. During image synthesis, however, line segments and polygons play important roles. In this section we present methods that bridge the gap between these two types of representations. These methods convert geometric models to lines and polygons, or further process line and polygon models. Line segments connected to each other in a way that the end point of a line segment is the start point of the next one are called polylines. Polygons connected at edges, on the other hand, are called meshes. Vectorization methods approximate free-form curves by polylines. A polyline is defined by its vertices. Tessellation algorithms, on the other hand, approximate free-form surfaces by meshes. For illumination computation, we often need the normal vector of the original surface, which is usually stored with the vertices. Consequently, a mesh contains a list of polygons, where each polygon is given by its vertices and the normal of the original surface at these vertices. Methods processing meshes use other topology information as well, for example, which polygons share an edge or a vertex.

22.3.1. 22.3.1 Polygon and polyhedron

Definition 22.2 A polygon is a bounded part of the plane, i.e. it does not contain a line, and is bordered by line segments. A polygon is defined by the vertices of the bordering polylines.

Figure 22.11.  Types of polygons. (a) simple; (b) complex, single connected; (c) multiply connected.

Types of polygons. (a) simple; (b) complex, single connected; (c) multiply connected.

Definition 22.3 A polygon is single connected if its border is a single closed polyline (Figure 22.11).

Definition 22.4 A polygon is simple if it is single connected and the bordering polyline does not intersect itself (Figure 22.11(a)).

For a point of the plane, we can detect whether or not this point is inside the polygon by starting a half-line from this point and counting the number of intersections with the boundary. If the number of intersections is an odd number, then the point is inside, otherwise it is outside.

In the three-dimensional space we can form meshes, where different polygons are in different planes. In this case, two polygons are said to be neighboring if they share an edge.

Definition 22.5 A polyhedron is a bounded part of the space, which is bordered by polygons.

Similarly to polygons, a point can be tested for polyhedron inclusion by casting a half line from this point and counting the number of intersections with the face polygons. If the number of intersections is odd, then the point is inside the polyhedron, otherwise it is outside.

22.3.2. 22.3.2 Vectorization of parametric curves

Parametric functions map interval onto the points of the curve. During vectorization the parameter interval is discretized. The simplest discretization scheme generates evenly spaced parameter values (), and defines the approximating polyline by the points obtained by substituting these parameter values into parametric equation .

22.3.3. 22.3.3 Tessellation of simple polygons

Let us first consider the conversion of simple polygons to triangles. This is easy if the polygon is convex since we can select an arbitrary vertex and connect it with all other vertices, which decomposes the polygon to triangles in linear time. Unfortunately, this approach does not work for concave polygons since in this case the line segment connecting two vertices may go outside the polygon, thus cannot be the edge of one decomposing triangle.

Let us start the discussion of triangle conversion algorithms with two definitions:

Figure 22.12.  Diagonal and ear of a polygon.

Diagonal and ear of a polygon.

Definition 22.6 The diagonal of a polygon is a line segment connecting two vertices and is completely contained by the polygon (line segment and of Figure 22.12).

The diagonal property can be checked for a line segment connecting two vertices by trying to intersect the line segment with all edges and showing that intersection is possible only at the endpoints, and additionally showing that one internal point of the candidate is inside the polygon. For example, this test point can be the midpoint of the line segment.

Definition 22.7 A vertex of the polygon is an ear if the line segment between the previous and the next vertices is a diagonal (vertex of Figure 22.12).

Clearly, only those vertices may be ears where the inner angle is not greater than 180 degrees. Such vertices are called convex vertices.

For simple polygons the following theorems hold:

Theorem 22.8 A simple polygon always has a diagonal.

Proof. Let the vertex standing at the left end (having the minimal coordinate) be , and its two neighboring vertices be and , respectively (Figure 22.13). Since is standing at the left end, it is surely a convex vertex. If is an ear, then line segment is a diagonal (left of Figure 22.13), thus the theorem is proven for this case. Since is a convex vertex, it is not an ear only if triangle , , contains at least one polygon vertex (right of Figure22.13). Let us select from the contained vertices that vertex which is the farthest from the line defined by points . Since there are no contained points which are farther from line than , no edge can be between points and , thus must be a diagonal.

Figure 22.13.  The proof of the existence of a diagonal for simple polygons.

The proof of the existence of a diagonal for simple polygons.

Theorem 22.9 A simple polygon can always be decomposed to triangles with its diagonals. If the number of vertices is , then the number of triangles is .

Proof. This theorem is proven by induction. The theorem is obviously true when , i.e. when the polygon is a triangle. Let us assume that the statement is also true for polygons having () number of vertices, and consider a polygon with vertices. According to Theorem 22.8, this polygon of vertices has a diagonal, thus we can subdivide this polygon into a polygon of vertices and a polygon of vertices, where , and since the vertices at the ends of the diagonal participate in both polygons. According to the assumption of the induction, these two polygons can be separately decomposed to triangles. Joining the two sets of triangles, we can obtain the triangle decomposition of the original polygon. The number of triangles is .

The discussed proof is constructive thus it inspires a subdivision algorithm: let us find a diagonal, subdivide the polygon along this diagonal, and continue the same operation for the two new polygons.

Unfortunately the running time of such an algorithm is in since the number of diagonal candidates is , and the time needed by checking whether or not a line segment is a diagonal is in .

We also present a better algorithm, which decomposes a convex or concave polygon defined by vertices . This algorithm is called ear cutting. The algorithm looks for ear triangles and cuts them until the polygon gets simplified to a single triangle. The algorithm starts at vertex . When a vertex is processed, it is first checked whether or not the previous vertex is an ear. If it is not an ear, then the next vertex is chosen. If the previous vertex is an ear, then the current vertex together with the two previous ones form a triangle that can be cut, and the previous vertex is deleted. If after deletion the new previous vertex has index 0, then the next vertex is selected as the current vertex.

The presented algorithm keeps cutting triangles until no more ears are left. The termination of the algorithm is guaranteed by the following two ears theorem:

Theorem 22.10 A simple polygon having at least four vertices always has at least two not neighboring ears that can be cut independently.

Proof. The proof presented here has been given by Joseph O'Rourke. According to theorem 22.9, every simple polygon can be subdivided to triangles such that the edges of these triangles are either the edges or the diagonals of the polygon. Let us make a correspondence between the triangles and the nodes of a graph where two nodes are connected if and only if the two triangles corresponding to these nodes share an edge. The resulting graph is connected and cannot contain circles. Graphs of these properties are trees. The name of this tree graph is the dual tree. Since the polygon has at least four vertices, the number of nodes in this tree is at least two. Any tree containing at least two nodes has at least two leaves. Leaves of this tree, on the other hand, correspond to triangles having an ear vertex.

Footnote. A leaf is a node connected by exactly one edge.

According to the two ears theorem, the presented algorithm finds an ear in steps. Cutting an ear the number of vertices is reduced by one, thus the algorithm terminates in steps.

22.3.4. 22.3.4 Tessellation of parametric surfaces

Parametric forms of surfaces map parameter rectangle onto the points of the surface.

Figure 22.14.  Tessellation of parametric surfaces.

Tessellation of parametric surfaces.


In order to tessellate the surface, first the parameter rectangle is subdivided to triangles. Then applying the parametric equations for the vertices of the parameter triangles, the approximating triangle mesh can be obtained. The simplest subdivision of the parametric rectangle decomposes the domain of parameter to parts, and the domain of parameter to intervals, resulting in the following parameter pairs:

Taking these parameter pairs and substituting them into the parametric equations, point triplets , , , and point triplets , , are used to define triangles.

The tessellation process can be made adaptive as well, which uses small triangles only where the high curvature of the surface justifies them. Let us start with the parameter rectangle and subdivide it to two triangles. In order to check the accuracy of the resulting triangle mesh, surface points corresponding to the edge midpoints of the parameter triangles are compared to the edge midpoints of the approximating triangles. Formally the following distance is computed (Figure 22.15):

where and are the parameters of the two endpoints of the edge.

Figure 22.15.  Estimation of the tessellation error.

Estimation of the tessellation error.


A large distance value indicates that the triangle mesh poorly approximates the parametric surface, thus triangles must be subdivided further. This subdivision can be executed by cutting the triangle to two triangles by a line connecting the midpoint of the edge of the largest error and the opposing vertex. Alternatively, a triangle can be subdivided to four triangles with its halving lines. The adaptive tessellation is not necessarily robust since it can happen that the distance at the midpoint is small, but at other points is still quite large.

When the adaptive tessellation is executed, it may happen that one triangle is subdivided while its neighbour is not, which results in holes. Such problematic midpoints are called T vertices (Figure 22.16).

Figure 22.16.  T vertices and their elimination with forced subdivision.

T vertices and their elimination with forced subdivision.


If the subdivision criterion is based only on edge properties, then T vertices cannot show up. However, if other properties are also taken into account, then T vertices may appear. In such cases, T vertices can be eliminated by recursively forcing the subdivision also for those neighbouring triangles that share subdivided edges.

22.3.5. 22.3.5 Subdivision curves and meshes

This section presents algorithms that smooth polyline and mesh models.

Figure 22.17.  Construction of a subdivision curve: at each step midpoints are obtained, then the original vertices are moved to the weighted average of neighbouring midpoints and of the original vertex.

Construction of a subdivision curve: at each step midpoints are obtained, then the original vertices are moved to the weighted average of neighbouring midpoints and of the original vertex.


Let us consider a polyline of vertices . A smoother polyline is generated by the following vertex doubling approach (Figure 22.17). Every line segment of the polyline is halved, and midpoints are added to the polyline as new vertices. Then the old vertices are moved taking into account their old position and the positions of the two enclosing midpoints, applying the following weighting:

The new polyline looks much smoother. If we should not be satisfied with the smoothness yet, the same procedure can be repeated recursively. As can be shown, the result of the recursive process converges to the B-spline curve.

Figure 22.18.  One smoothing step of the Catmull-Clark subdivision. First the face points are obtained, then the edge midpoints are moved, and finally the original vertices are refined according to the weighted sum of its neighbouring edge and face points.

One smoothing step of the Catmull-Clark subdivision. First the face points are obtained, then the edge midpoints are moved, and finally the original vertices are refined according to the weighted sum of its neighbouring edge and face points.


The polyline subdivision approach can also be extended for smoothing three-dimensional meshes. This method is called Catmull-Clark subdivision algorithm. Let us consider a three-dimensional quadrilateral mesh (Figure 22.18). In the first step the midpoints of the edges are obtained, which are called edge points. Then face points are generated as the average of the vertices of each face polygon. Connecting the edge points with the face points, we still have the original surface, but now defined by four times more quadrilaterals. The smoothing step modifies first the edge points setting them to the average of the vertices at the ends of the edge and of the face points of those quads that share this edge. Then the original vertices are moved to the weighted average of the face points of those faces that share this vertex, and of edge points of those edges that are connected to this vertex. The weight of the original vertex is 1/2, the weights of edge and face points are 1/16. Again, this operation may be repeated until the surface looks smooth enough (Figure 22.19).

Figure 22.19.  Original mesh and its subdivision applying the smoothing step once, twice and three times, respectively.

Original mesh and its subdivision applying the smoothing step once, twice and three times, respectively.


If we do not want to smooth the mesh at an edge or around a vertex, then the averaging operation ignores the vertices on the other side of the edge to be preserved.

Figure 22.20.  Generation of the new edge point with butterfly subdivision.

Generation of the new edge point with butterfly subdivision.


The Catmull-Clark subdivision surface usually does not interpolate the original vertices. This drawback is eliminated by the butterfly subdivision, which works on triangle meshes. First the butterfly algorithm puts new edge points close to the midpoints of the original edges, then the original triangle is replaced by four triangles defined by the original vertices and the new edge points (Figure 22.20). The position of the new edge points depend on the vertices of those two triangles incident to this edge, and on those four triangles which share edges with these two. The arrangement of the triangles affecting the edge point resembles a butterfly, hence the name of this algorithm. The edge point coordinates are obtained as a weighted sum of the edge endpoints multiplied by , the third vertices of the triangles sharing this edge using weight , and finally of the other vertices of the additional triangles with weight . Parameter can control the curvature of the resulting mesh. Setting , the mesh keeps its original faceted look, while results in strong rounding.

22.3.6. 22.3.6 Tessellation of implicit surfaces

A surface defined by implicit equation can be converted to a triangle mesh by finding points on the surface densely, i.e. generating points satisfying , then assuming the close points to be vertices of the triangles.

First function is evaluated at the grid points of the Cartesian coordinate system and the results are stored in a three-dimensional array, called voxel array. Let us call two grid points as neighbours if two of their coordinates are identical and the difference in their third coordinate is 1. The function is evaluated at the grid points and is assumed to be linear between them. The normal vectors needed for shading are obtained as the gradient of function (equation 22.4), which are also interpolated between the grid points.

When we work with the voxel array, original function is replaced by its tri-linear approximation (tri-linear means that fixing any two coordinates the function is linear with respect to the third coordinate). Due to the linear approximation an edge connecting two neighbouring grid points can intersect the surface at most once since linear equations may have at most one root. The density of the grid points should reflect this observation, then we have to define them so densely not to miss roots, that is, not to change the topology of the surface.

Figure 22.21.  Possible intersections of the per-voxel tri-linear implicit surface and the voxel edges. From the possible 256 cases, these 15 topologically different cases can be identified, from which the others can be obtained by rotations. Grid points where the implicit function has the same sign are depicted by circles.

Possible intersections of the per-voxel tri-linear implicit surface and the voxel edges. From the possible 256 cases, these 15 topologically different cases can be identified, from which the others can be obtained by rotations. Grid points where the implicit function has the same sign are depicted by circles.


The method approximating the surface by a triangle mesh is called marching cubes algorithm. This algorithm first decides whether a grid point is inside or outside of the solid by checking the sign of function . If two neighbouring grid points are of different type, the surface must go between them. The intersection of the surface and the edge between the neighbouring points, as well as the normal vector at the intersection are determined by linear interpolation. If one grid point is at , the other is at , and function has different signs at these points, then the intersection of the tri-linear surface and line segment is:

The normal vector here is:

Having found the intersection points, triangles are defined using these points as vertices. When defining these triangles, we have to take into account that a tri-linear surface may intersect the voxel edges at most once. Such intersection occurs if function has different signs at the two grid points. The number of possible variations of positive/negative signs at the 8 vertices of a cube is 256, from which 15 topologically different cases can be identified (Figure 22.21).

The algorithm inspects grid points one by one and assigns the sign of the function to them encoding negative sign by 0 and non-negative sign by 1. The resulting 8 bit code is a number in 0–255 which identifies the current case of intersection. If the code is 0, all voxel vertices are outside the solid, thus no voxel surface intersection is possible. Similarly, if the code is 255, the solid is completely inside, making the intersections impossible. To handle other codes, a table can be built which describes where the intersections show up and how they form triangles.

Exercises

22.3-1 Prove the two ears theorem by induction.

22.3-2 Develop an adaptive curve tessellation algorithm.

22.3-3 Prove that the Catmull-Clark subdivision curve and surface converge to a B-spline curve and surface, respectively.

22.3-4 Build a table to control the marching cubes algorithm, which describes where the intersections show up and how they form triangles.

22.3-5 Propose a marching cubes algorithm that does not require the gradients of the function, but estimates these gradients from its values.