4 Representing, Storing and Visualizing 3D Data

143

4.2.2 Surface Representations

The vast majority of geometric algorithms in computer vision and graphics operate on representations of 3D data based on surfaces. Of these representations, by far the most common is the triangular mesh. For this reason, we focus in more detail on this representation in Sect. 4.3. For many applications in Computer Aided Design (CAD), it is necessary to be able to guarantee a certain class of surface smoothness. For example, this may relate to aerodynamic or aesthetic requirements. Smoothness can be categorized according to differentiability class. A surface belongs to class C0 if it is continuous (i.e. the surface or function value changes smoothly). The class C1 consists of all surfaces which are differentiable and whose derivative is continuous (i.e. the surface normal changes smoothly), while C2 surfaces have continuous second derivatives (i.e. the surface curvature changes smoothly). A representation which can provide such guarantees, as well as providing a convenient interface for interactive editing is subdivision surfaces. We focus in more detail on this representation in Sect. 4.4. Here, we give a brief overview of alternative surface representations and provide a comparison of the desirable features exhibited by each representation.

4.2.2.1 Triangular Mesh

The most common surface representation comprises 3D vertices, connected together to form triangular faces, which in turn represent or approximate a 2D manifold embedded in 3D space. A number of categorizations are possible here. An important distinction is whether the mesh is closed (i.e. the surface completely encloses a volume) or open (i.e. the mesh contains “boundary” edges that are used by only one triangle). Meshes can represent surfaces with different genera. The genus of a surface is an integer representing the maximum number of cuttings along non-intersecting closed simple curves without rendering the resultant manifold disconnected. For example, a sphere has genus zero, while a torus has genus 1. An important property of a triangle is that it has a single surface normal. When a mesh is used to approximate a curved surface, the differential properties of the surface, such as normals and curvature, can only be approximately computed from the mesh faces. Mesh storage and representation is discussed in more detail in Sect. 4.3.

Often, mesh vertices are augmented with texture coordinates, also known as UV coordinates [23]. These are most often 2D coordinates which describe a mapping from the surface to a 2D planar parameterization. 1D, 3D (volumetric) and 4D (volumetric plus time) texture coordinates are also occasionally used. Texture coordinates range over the unit square, (u, v) [0, 1] × [0, 1]. RGB intensity (known as texture maps), surface normals (known as bump maps) or 3D displacements (known as displacement maps) are stored as images which are indexed by the texture coordinates. When rendering a polygonal mesh, texture within the interior of polygons can be looked up by interpolating the texture coordinates of the vertices of the polygon. Transforming an arbitrary mesh to a 2D parameterization with minimal distortion is a difficult problem [59].

144	W.A.P. Smith

4.2.2.2 Quadrilateral Mesh

The polygons in a mesh need not be triangular. Meshes may contain polygons of arbitrary shape and number of vertices, though non-planar polygons will require additional processing for rendering (e.g. to interpolate surface normal direction over the polygon). One commonly used polygon mesh is based on quadrilateral polygons (sometimes known as a quadmesh). Quadmeshes can be easily converted to a triangular mesh by diagonally subdividing each quadrilateral. Quadrilateral meshes are preferred to triangular meshes in a number of circumstances. One example is when Finite Element Analysis is used to simulate surface deformation such as in automobile crash simulation or sheet-metal forming. In these cases, the solution accuracy is improved by using a quadmesh.

4.2.2.3 Subdivision Surfaces

Subdivision surfaces are used to represent a smooth surface using a low resolution base mesh and a subdivision rule (or refinement scheme). When applied recursively, the subdivided surface tends towards the smooth surface. The limit subdivision surface is the surface produced when the refinement scheme is iteratively applied infinitely many times. The limit surface can be computed directly for most subdivision surfaces, without the need to evaluate the iterative refinement. This allows a subdivision surface to be rendered without explicitly subdividing the original base mesh. We describe a number of subdivision schemes in Sect. 4.4.

4.2.2.4 Morphable Model

A space efficient representation, which can be used to approximate members of a class of surfaces (such as human faces [6] or automobiles [36]), is the morphable model. This is a compact statistical representation learnt from training samples. A mesh of N vertices may be written as a long vector: s = [x1 y1 z1 . . . xN yN zN ]T . From a sample of such meshes that are in dense correspondence (i.e. the ith vertex in each mesh corresponds to a point with the same meaning, such as the tip of the nose), a mean vector, s¯, and a set of orthonormal basis vectors, e1, . . . , ek R3N , are derived using Principal Components Analysis (PCA). These vectors correspond to the most common modes of variation within the training data and they are sorted by the variance captured by each mode, σ1 > · · · > σk . Hence, only the most important modes need be retained to explain a large proportion of the variance in the training data, i.e. k N . Any member of the class of objects can be approximated as a linear combination of the mean vector and the principal modes of variation:

s = Pb + s¯,

(4.1)

where P = [e1| . . . |ek ] R3N ×k is the matrix formed by stacking the basis vectors and b Rk is a vector of weights associated with each mode. The advantage of such

4 Representing, Storing and Visualizing 3D Data

145

Fig. 4.1 A 3D morphable model of human faces [48]. The top left panel shows the mean face surface. The remainder show the mean face deformed by ±5 standard deviations along the first three principal modes of variation

a representation is that the high dimensional mesh can be approximated by the low dimensional parameter vector. Moreover, the parameter space is useful for recognition and classification and the modes themselves often correspond to meaningful global descriptors. For example, in Fig. 4.1, we show a morphable model of human faces. The first mode appears to capture the difference between adult and child faces. A morphable model is limited to representing objects from within the same class as the training data. The ability of the model to generalize to unseen samples is characterized by the generalization error, which is a function of the diversity of the training samples. There is also an implicit assumption that the original high dimensional data approximates a Gaussian distribution (hyperelliposoid), which can be accurately approximated by a small number of axes.

4.2.2.5 Implicit Surface

An implicit surface [8] (also known as a level set or an isosurface) is the set of all points [x y z]T which satisfy the function f (x, y, z) = 0. Typically, function values greater than zero indicate points that are outside the object, while negative values indicate points that are inside. For example, the surface of a sphere of radius r can be represented by the set of points satisfying x2 + y2 + z2 − r2 = 0. The surface normal to an implicit surface can be obtained simply by taking partial derivatives:

n(x, y, z) = ∂x f (x, y, z) ∂y f (x, y, z) ∂zf (x, y, z) T .

(4.2)

146	W.A.P. Smith

Fig. 4.2 The three possible cases for a line-sphere intersection

Inside/outside tests can also be performed efficiently by simply evaluating the sign of the surface function at a given point. One of the most attractive properties of the implicit surface representation is that intersections can be computed analytically. By substituting a parametric ray equation into the implicit surface function and solving for the parameter, all intersections can be found exactly. For example, consider the ray described by:

x	x0	a
y	= y0	+ t b .	(4.3)
z	z0	c

Substituting into the parametric surface for the sphere, radius r , given above yields:

−(ax0 + by0 + cz0) ±		(ax0 + by0 + cz0)2 − (a2 + b2 + c2)(x02 + y02 + z02 − r2)
t =			.
		(a2 + b2 + c2)

(4.4) There are three possible cases for this intersection (see Fig. 4.2). Two real roots means that the ray intersects the sphere in two places. One real root means the ray touches the sphere tangentially. No real roots means the ray misses the surface. Higher order surfaces involve the solution of higher order intersection equations, which may not be possible analytically.

In general, obtaining a function which exactly describes a general surface is difficult. However, for applications involving visualization of physical effects such as fluid dynamics (where functional descriptions of the dynamics are readily available) an implicit surface is a natural representation. There are a number of commonly used ways to define an implicit surface. The example above is algebraic. The most common such form is a quadric which can be used to describe regular shapes such as spheres, ellipsoids and tori.

An alternative is to derive an algebraic representation from an intermediate representation [9], which is specified by a designer or fitted to data. The most common approach is to define a control structure from primitives such as points, line segments and planar patches. A field function is defined and its value at some point is determined by the distance, r , from that point to a control structure. For example: f (r) = r12 . The value of this function is known as the field strength. The total field