Chapter 3

How a 3D Model Is Represented

In recent years, 3D digital data have gone through a revolution in terms of diffusion and use in several applications, just like it happened before for other digital media such as audio, video and images. This has motivated the development of new ways to represent digital 3D content. In this chapter, we will give an overview of several ways to represent the geometry of a 3D object on a computer. Our main goal is to provide insights to the reader about how to handle the geometry of a 3D model in his/her graphics application.

We advise the reader that many details provided about parametric curves and surfaces (Section 3.4) and about subdivision surfaces (Section 3.7) are given only for the sake of completeness but they will not be used in the practical examples and in the development of our game. Readers that prefer to go quickly to the heart of the graphics development, and hence move fast to the next chapters, can read the aforementioned sections considering only the concepts described, skipping the mathematical details. They should put more attention on the polygon meshes (Section 3.2) and their implementation (Section 3.8 plus the practical part), since we will use these types of representation for the rest of the book.

3.1 Introduction

In very general terms a 3D model is a mathematical representation of a physical entity that occupies space. In more practical terms, a 3D model is made of a description of its shape and a description of its color appearance. In this chapter we focus on geometric data representation, providing a panoramic of the most used representations and presenting the peculiarities of each.

One main categorization of 3D object’s representation can be done by considering whether the surface or the volume of the object is represented:

• Boundary-based: the surface of the 3D object is represented. This representation is also called b-rep. Polygon meshes, implicit surfaces and parametric surfaces, which we will describe in the following, are common representations of this type.
• Volume-based: the volume of the 3D object is represented. Voxels (described in Section 3.5) and Constructive Solid Geometry (CSG) (described in Section 3.6) are commonly used to represent volumetric data.

The representation of a 3D model depends on the way the model has been created and by its application context. A geometric representation may come from several sources. Just to mention a few:

3.1.1 Digitalization of the Real World

These techniques are what photography is for 2D images: they measure real objects to obtain a digital description of them. Among the most well known we can find the triangulation-based techniques. The fundamental idea is that a pattern of light is projected into the surface to be digitalized and a camera takes a photograph of how the light is reflected by the surface. The known relative position of projector and camera (which are usually mounted on the same physical device) make it possible to infer the position of each point of the surface where the light has been projected. Among the triangle-based scanners we find the laser scanners, where the pattern of light is simply a thin laser beam swept on the surface (and hence a 3D point per photo is found), or structured light scanners, where patterns such as stripes are projected. A well known exmple of this type is the Kinect®, where the pattern projected is on the infrared spectrum and hence not visible to human eyes. Time-of-light techniques also project a laser beam on the surface, and detect the time for the light to bounce on the surface and come back to the device. Then the distance is simply obtained with the equation space = lightspeed ∙ time.

These techniques are referred to as active techniques, because they project light on the surface. In contrast, the passive techniques use only cameras (photographic or video). In this case the 3D model is reconstructed from a set of images through the use of modern Computer Vision techniques. In very simple words, the idea is to be able to match the same point on two or more images. If we can do this for many points, it will be possible to estimate both the position of the cameras and the position of the points in 3D. Note that this is also how we perceive depth: our two eyes see two images and the brain finds the correspondences.

3.1.2 Modeling

An artist or a technician interactively designs the 3D model using geometric modeling software such as Maya®, 3D Studio Max®, Rhinoceros®, Blender and others.

3.1.3 Procedural Modeling

The model is automatically generated using procedural methods. A fractal is an example of procedural generation. A common way to generate a 3D model is to use grammar rules to describe in some way the object to generate.

3.1.4 Simulation

Numerical simulations are used for several goals. Winds, temperature and pressure are simulated for weather forecasts, fluid dynamics, that is, the study of how liquids behave, is used for designing engines, cardiac pumps, vehicles and so on. Very often the data produced can be naturally mapped on a three-dimensional model, whether a b-rep, for example the wavefront of a low pressure area, or with a volume, for example the fluid velocity.

In the following we analyze several 3D objects’ representation by underlining the advantages and the disadvantages of each one.

3.2 Polygon Meshes

Intuitively, a polygon mesh is the partition of a continuous surface in polygonal cells, such as triangles, quadrilaterals, etc. Figure 3.1 shows an example of triangle mesh. More formally, a mesh M can be defined as a tuple (V,K) where $\mathit{\text{V}}=\left\{{\mathit{\text{v}}}_{\mathit{\text{i}}}\in {\mathit{\text{ℝ}}}^3|\mathit{\text{i}}=1\dots {\mathit{\text{N}}}_{\mathit{\text{v}}}\right\}$ is the set of the vertices of the model (points in ℝ3) and K contains the adjacency information or, in other words, how the vertices are connected to form edges and faces of the mesh. For example a mesh made by a single triangle would be $\left(\left\{{\mathit{\text{v}}}_0,{\mathit{\text{v}}}_1,{\mathit{\text{v}}}_2\right\},\left\{\left\{{\mathit{\text{v}}}_0,{\mathit{\text{v}}}_1\right\},\left\{{\mathit{\text{v}}}_1,{\mathit{\text{v}}}_2\right\},\left\{{\mathit{\text{v}}}_2,{\mathit{\text{v}}}_0\right\},\left\{{\mathit{\text{v}}}_0,{\mathit{\text{v}}}_1,{\mathit{\text{v}}}_2\right\}\right\}\right)$, that is, the three vertices, the three edges and the triangle.

The most-used meshes in computer graphics are triangle meshes and quadrilateral meshes (shortened as quad meshes). When it comes to rendering, however, we will always render either points, of segments or triangles, and since a quad mesh can be turned into a triangle mesh just by splitting each quad into two triangles, from now on, when we write mesh we mean triangle mesh.

3.2.1 Fans and Strips

The set of all the neighbors of a vertex vi is called the 1-ring of the vertex and is defined as ${\mathit{\text{v}}}_1\left(\mathit{\text{i}}\right)=\left\{\mathit{\text{j}}|\left\{\mathit{\text{i}},\mathit{\text{j}}\right\}\in \mathit{\text{K}}\right\}$. The cardinality of v1(i) is called degree or valence of the vertex vi.

A sequence of adjacent triangles sharing the same vertex is called a fan of triangles (see Figure 3.2 (Right)). A strip is a sequence of triangles that can be specified by listing its vertices without ambiguity. To be more specific, given an ordered vertex list $\left\{{\mathit{\text{v}}}_0,{\mathit{\text{v}}}_1,\dots ,{\mathit{\text{v}}}_{\mathit{\text{n}}}\right\}$, the triangle i is represented by the vertices $\left\{{\mathit{\text{v}}}_{\mathit{\text{i}}},{\mathit{\text{v}}}_{\mathit{\text{i}}+1},{\mathit{\text{v}}}_{\mathit{\text{i}}+2}\right\}$ (see Figure 3.2 (Left)). Strips and fans are used to compact the mesh representations. A strip of triangles with n vertices represents n − 2 triangles. So, a strip of 100 triangle requires 102 vertices to be stored instead of 300. The amount of vertices saved increases with the number of triangles; the average number of vertices $\overline{v_t}$ to represent a triangle in a strip with m triangles is $\overline{v_t}=1+2/m$. In the case of a fan, the triangle i is represented by the vertices $\left\{v_0,v_{i+1},v_{i+2}\right\}$ assuming v0 is the shared vertex. Fans of triangles have the same performances as strips, that is, the same average number of vertices per triangles.

3.2.2 Manifoldness

A surface is said to be 2-manifold if the neighborhood of each point p on the surface is homeomorphic to a disk. Simply put, it means that if we have a rubber-made disk we can center it on p and make it adhere to the surface around it. Figure 3.3 (Right) shows two cases where we cannot do this. This definition of 2-manifold is extended to the surface with boundary by considering cutting away half of the disk and making it adhere to the boundary.

As stated above, manifoldness is a characteristic of general surfaces. When the surface is a polygon mesh, we can determine if it is manifold by checking if the following conditions are true:

• Edge Manifold. Every edge is shared by one (that means it is on the boundary of the mesh) or two faces.
• Vertex Manifold. If two faces fa and fb share a vertex, then we can move from fa to fb by traversing only edges in the 1-ring of the vertex. In other words, we can walk over all the neighborhood of the vertex without passing through the vertex itself.

3.2.3 Orientation

Each face is a polygon and hence it has two sides. Let us suppose we paint one side black and one white. If we can paint every face of the mesh so that faces that share an edge are painted the same color, we say the mesh is orientable and the orientation of a face is how we assigned black and white to its sides. Only we do not need to actually paint the faces, we can assign the orientation by the order in which the vertices are specified. More precisely, if we look at a face and follow its vertices in the order they are specified in K, they can describe a clockwise or anti-clockwise movement, like that shown in Figure 3.4. Obviously if we look at the same faces from behind, that is, from the back of the page, these orientations will be swapped. We can say that the black side of a face is the side from which the sequence of its vertices is counterclockwise. Note that two faces f1 and f2 have the same orientation if, for each shared edge, its vertices appear in the opposite order in the description of f1 and f2.

3.2.4 Advantages and Disadvantages

Polygon meshes suffer from several limitations. First of all, they are a discrete representation; curved surfaces can only be piecewise approximated by the planar faces that compose the mesh. The greater the number of faces, the better we can represent the surface, as shown in the example of Figure 3.5 for a sphere.

Another disadvantage is that mesh representation is not compact, that is, a high-detailed model may easily require a huge amount of data to be represented. Again, consider the sphere: we can completely describe its shape mathematically by specifying the radius (one number) while the polygon representation requires much more data to be defined. Figure 3.6 shows an example of a small statue and how even as many as 10, 000 faces give a quite poor description of all the details if compared to a version with 100,000 faces. Naturally this data may be compressed and there are many ad hoc techniques for it (see [33] for a survey).

Direct editing is also difficult; designers and artists have to carefully modify each element of the surface in order to obtain the desired result. Although proper user interfaces to edit meshes exist this task still remains problematic. Modeling is more easy and natural with other representations, for example, parametric surfaces such as NURBS (described in Section 3.4) are typically used to this aim. Finally, there is no obvious parameterization (for meshes take a look at Section 7.9 to learn more about the concept of parameterization).

Despite these problems the computer graphics community has put a lot of effort into mesh processing and a huge number of applications use this type of representation. One of the main reasons for this is that meshes are the common denominator of other representations, that is, it is easy to convert other representations to a polygon mesh. Another important motivation is that, as just stated during the description of the rendering pipeline, drawing triangles on the screen is much easier and optimizable than drawing more complex shapes and consequently modern graphics hardware has evolved towards this direction.

3.3 Implicit Surfaces

An implicit surface is defined as the set of points S such that a given trivariate function f(.) is equal to zero. In three dimensions:

$\begin{array}{ccc}\mathit{\text{S}}=\left\{\left(\mathit{\text{x}},\mathit{\text{y}},\mathit{\text{z}}\right)\in {\mathit{\text{ℝ}}}^3|\mathit{\text{f}}\left(\mathit{\text{x}},\mathit{\text{y}},\mathit{\text{z}}\right)=0\right\}& & \left(3.1\right)\end{array}$

where (x, y, z) are cartesian coordinates. The set S is also known as the zero set of f(.). For example, a sphere of radius r can be represented by the equation ${\mathit{\text{x}}}^2+{\mathit{\text{y}}}^2+{\mathit{\text{z}}}^2={\mathit{\text{r}}}^2$, which becomes ${\mathit{\text{x}}}^2+{\mathit{\text{y}}}^2+{\mathit{\text{z}}}^2-{\mathit{\text{r}}}^2=0$ in the canonical form. A plane in the space can be represented by the function $\mathit{\text{a}}\mathit{\text{x}}+\mathit{\text{b}}\mathit{\text{y}}+\mathit{\text{c}}\mathit{\text{z}}-\mathit{\text{d}}=0$, and so on. So, a 3D object more complex than a basic geometric such as a plane or a sphere can be represented by a set of implicit surface functions, each one describing a part of its shape.

Algebraic surfaces are a particular kind of implicit surface for which f(.) is a polynomial. The degree of an algebraic surface is given by the sum of the maximum powers of all terms ${\mathit{\text{a}}}_{\mathit{\text{m}}}{\mathit{\text{x}}}^{{\mathit{\text{i}}}_{\mathit{\text{m}}}}{\mathit{\text{y}}}^{{\mathit{\text{j}}}_{\mathit{\text{m}}}}{\mathit{\text{z}}}^{{\mathit{\text{k}}}_{\mathit{\text{m}}}}$ of the polynomial. An algebraic surface of degree two describes quadratic surfaces, a polynomial of degree three cubic surfaces, of degree four quartic surfaces and so on. Quadratic surfaces, also called quadrics, are very important in geometric modeling. This kind of surface intersects every plane in a proper or degenerate way forming 17 standard-form types of surfaces [40]. To mention some: parallel planes, ellipsoid, elliptic cone, elliptic cylinder, parabolic cylinder, hyperboloid of one sheet, hyperboloid of two sheets can all be obtained as the intersection of a quadric with a plane.

3.3.1 Advantages and Disadvantages

One of the main advantages of implicit representation is their compactness. In their most common implementation the surface is defined as a combination of sphere-like implicit surfaces that form what you usually find under the heading of blobby surfaces. These representations can be used for modelling the surface of fluids or even for solid objects. However, they are not very well suited for representing sharp features and for making global modifications to the surface. Implicit surfaces are difficult to render. Either they are tessellated in a polygon mesh or ray tracing is used. In the latter case we need to solve, for each view ray, the problem of finding its intersection with the surface.

3.4 Parametric Surfaces

In order to gently introduce the concepts related to parametric surfaces, we first give a brief description of the generic form of a parametric curve, then we present two important types of parametric curves in computer graphics, the Bézier and B-Spline curves, and finally we describe Bézier patches and NURBS, which are one of the most used parametric surfaces in modern geometric modeling software tools.

3.4.1 Parametric Curve

A parametric curve in three-dimensional space is defined by a mapping from the parameter domain, which is a subset of ℝ, to the 3D space ℝ3:

$\begin{array}{ccc}\mathit{\text{C}}\left(\mathit{\text{t}}\right)=\left(\mathit{\text{X}}\left(\mathit{\text{t}}\right),\mathit{\text{Y}}\left(\mathit{\text{t}}\right),\mathit{\text{Z}}\left(\mathit{\text{t}}\right)\right)& & \left(3.2\right)\end{array}$

where t is the curve parameter. Typically t ranges from 0 to 1, with the starting point of the curve being C(0) and the ending point C(1).

Suppose you want to freely draw a curve and then express it in parametric form. Aside from trivial cases, finding the formulas for X(t), Y(t) and Y(t) directly is a prohibitively difficult task. Fortunately, there are ways that allow us to derive these formulas from an intuitive representation of the curve. For example we can describe the curve as a sequence of points, called control points, like those shown in Figure 3.7. We could join these points directly and obtain a piecewise curve but we can do better and obtain a smooth curve by introducing a basis of blending functions used to join together the control points in a smooth way. The blending functions define the properties of the final curve/surface such as continuity and differentiability, if the curve/ surface is an approximation or an interpolation of the control points, and so on. We have an interpolation if the curve passes through the control points (see Figure 3.7 (Left)), and an approximation if the control points guide the curve but do not necessarily belong to it (see Figure 3.7 (Right)).

The typical formulation of this is:

$\begin{array}{cccc}\mathit{\text{C}}\left(\mathit{\text{t}}\right)={\displaystyle \sum _{\mathit{\text{i}}=0}^{\mathit{\text{n}}}{\mathit{\text{P}}}_{\mathit{\text{i}}}{\mathit{\text{B}}}_{\mathit{\text{i}}}\left(\mathit{\text{t}}\right)}& 0\le \mathit{\text{t}}\le 1& & \left(3.3\right)\end{array}$

where Pi are the control points and {Bi(.)} are the blending functions. The set of control points is also called the control polygon.

3.4.2 Bézier Curves

Béziers curves are one of the parametric curves most frequently used in computer graphics and were independently developed for computer-assisted car design by two engineers, both working for French automobile companies: Pierre Bézier, who was an engineer for Renault, and Paul de Casteljau, who was an engineer for Citroën. The mathematical definition of a Bézier curve is:

$\begin{array}{cccc}\mathit{\text{P}}\left(\mathit{\text{t}}\right)={\displaystyle \sum _{\mathit{\text{i}}=0}^{\mathit{\text{n}}}{\mathit{\text{P}}}_{\mathit{\text{i}}}{\mathit{\text{B}}}_{\mathit{\text{i}},\mathit{\text{n}}}\left(\mathit{\text{t}}\right)}& 0\le \mathit{\text{t}}\le 1& & \left(3.4\right)\end{array}$

where Pi are the control points and Bi,n(.) are Bernstein polynomials of degree n.

A Bernstein polynomial of degree n is defined as:

$\begin{array}{cccc}{\mathit{\text{B}}}_{\mathit{\text{i}},\mathit{\text{n}}}\left(\mathit{\text{t}}\right)=\left(\begin{array}{c}\mathit{\text{n}}\\ \mathit{\text{i}}\end{array}\right){\mathit{\text{t}}}^{\mathit{\text{i}}}{\left(1-\mathit{\text{t}}\right)}^{\mathit{\text{n}}-\mathit{\text{i}}}& \mathit{\text{i}}=0\dots \mathit{\text{n}}& & \left(3.5\right)\end{array}$

where $\left(\begin{array}{c}\mathit{\text{n}}\\ \mathit{\text{i}}\end{array}\right)$ is the binomial coefficient, that is, $\left(\begin{array}{c}\mathit{\text{n}}\\ \mathit{\text{i}}\end{array}\right)=\frac{\mathit{\text{n}}!}{\mathit{\text{i}}!\left(\mathit{\text{n}}-\mathit{\text{i}}\right)!}$. Figure 3.8 shows the Bernstein basis of degrees 1, 2 and 3.

Bernstein polynomials are widely used as blending functions for parametric curves and surfaces due to their properties:

1. The set of Bernstein polynomials of degree $\mathit{\text{n, }}{ℬ}_{\mathit{\text{n}}}=\left\{{\mathit{\text{B}}}_{\mathit{\text{0,n}}}(.),{\mathit{\text{B}}}_{\mathit{\text{1,n}}}(.),\dots ,{\mathit{\text{B}}}_{\mathit{\text{n,n}}}(.)\right\}$, forms a basis of the vector space of polynomials, called Bernstein basis.
2. ${\mathit{\text{ℬ}}}_{\mathit{\text{n}}}$ is a linear combination of ${\mathit{\text{ℬ}}}_{\mathit{\text{n}}-1}$.
3. They partition the unity (their sum is always one), that is: ${\displaystyle {\sum }_{\mathit{\text{i}}=0}^{\mathit{\text{n}}}{\mathit{\text{B}}}_{\mathit{\text{i}},\mathit{\text{n}}}\left(\mathit{\text{t}}\right)=1}$.

These properties make them suitable for efficient implementation; polynomials are easy to “treat”, a Bernstein basis of degree n can be expressed using the basis of degree n − 1 (property 2) and so on. Typically, the implementation employs matrix representation of the Bernstein basis, that is, the polynomial basis $\left\{1,\mathit{\text{t}},{\mathit{\text{t}}}^2,{\mathit{\text{t}}}^3,\dots ,{\mathit{\text{t}}}^{\mathit{\text{n}}}\right\}$ multiplies a matrix of coefficients that defines the Bernstein basis (property 1). For example, considering the basis of degree 2 we can write:

$\begin{array}{ccc}{\mathit{\text{B}}}_2\left(\mathit{\text{t}}\right)=\left[\begin{array}{ccc}{\left(1-\mathit{\text{t}}\right)}^2& \mathit{\text{t}}\left(1-\mathit{\text{t}}\right)& {\mathit{\text{t}}}^2\end{array}\right]=[\begin{array}{ccc}1& \mathit{\text{t}}& {\mathit{\text{t}}}^2\end{array}] \left[\begin{array}{ccc}1& 0& 0\\ -2& 2& 0\\ 1& -2& 1\end{array}\right]& & \left(3.6\right)\end{array}$

3.4.2.1 Cubic Bézier Curve

When we talk about Bézier curves, an important aspect, coming from its definition (3.4), is that the number of control points influences the degree of the Bernstein polynomial to use. More precisely n +1 control points require a Bernstein basis of degree n. This is not particularly efficient since a curve defined by several control points requires a set of high degree polynomials. For this reason, usually, after specifying the desired degree of the polynomials to use, the control points are grouped into sub-sequences in a way that guarantees the curve continuity. For example, if we want to join three points with a Bernstein polynomial of degree 1 we first join the points P0 and P1 and then join the points P1 and P2. It is interesting to note that this corresponds with connecting the given points with the corresponding segments, in fact the Bernstein polynomials of degree 1 are {(1 − t), t} thus resulting in:

$\begin{array}{cccc}\mathit{\text{P}}\left(\mathit{\text{t}}\right)={\mathit{\text{P}}}_0\left(1-\mathit{\text{t}}\right)+{\mathit{\text{P}}}_1\mathit{\text{t}}& 0\le \mathit{\text{t}}\le 1,& & \left(3.7\right)\end{array}$

which corresponds to the linear interpolation between the point P0 and the point P1.

Typically, when we have several points to connect, a cubic Bézier curve is used. Following the definition, this curve is formed by the linear combination of 4 control points with the Bernstein basis of degree 3. Taking into account Equation (3.5) the cubic Bézier curve can be written:

$\begin{array}{ccc}\mathit{\text{P}}\left(\mathit{\text{t}}\right)={\left(1-\mathit{\text{t}}\right)}^3{\mathit{\text{P}}}_0+3\mathit{\text{t}}{\left(1-\mathit{\text{t}}\right)}^2{\mathit{\text{P}}}_1+3{\mathit{\text{t}}}^2\left(1-\mathit{\text{t}}\right){\mathit{\text{P}}}_2+{\mathit{\text{t}}}^3{\mathit{\text{P}}}_3& & \left(3.8\right)\end{array}$

By re-arranging this formula in matrix notation it becomes:

$\begin{array}{lllll}\mathit{\text{P}}\left(\mathit{\text{t}}\right)\hfill & =\hfill & [\begin{array}{cccc}{\left(1-\mathit{\text{t}}\right)}^3& \mathit{\text{t}}{\left(1-\mathit{\text{t}}\right)}^2& {\mathit{\text{t}}}^2\left(1-\mathit{\text{t}}\right)& {\mathit{\text{t}}}^3\end{array}] \left[\begin{array}{c}{\mathit{\text{P}}}_0\\ {\mathit{\text{P}}}_1\\ {\mathit{\text{P}}}_2\\ {\mathit{\text{P}}}_3\end{array}\right]=\hfill & \hfill & \hfill \\ \hfill & =\hfill & [\begin{array}{cccc}1& \mathit{\text{t}}& {\mathit{\text{t}}}^2& {\mathit{\text{t}}}^3\end{array}] \left[\begin{array}{cccc}1& 0& 0& 0\\ -3& 3& 0& 0\\ 3& -6& 3& 0\\ 1& 3& -3& 1\end{array}\right] \left[\begin{array}{c}{\mathit{\text{P}}}_0\\ {\mathit{\text{P}}}_1\\ {\mathit{\text{P}}}_2\\ {\mathit{\text{P}}}_3\end{array}\right]\hfill & \hfill & \left(3.9\right)\hfill \end{array}$

The main characteristics of this curve is that it starts at the point P0 and ends at the point P4. The curve in P0 is tangent to the segment P1 − P0 and the curve in P4 is tangent to the segment P3 − P2. Figure 3.9 shows some examples of cubic Bézier curves. Two examples of Bézier curves with degree higher than 3, and so a number of control points higher than 4, are illustrated in Figure 3.10.

3.4.3 B-Spline Curves

The definition of a B-spline curve of order k is:

$\begin{array}{ccc}\mathit{\text{P}}\left(\mathit{\text{t}}\right)={\displaystyle \sum _{\mathit{\text{i}}=0}^{\mathit{\text{n}}}{\mathit{\text{P}}}_{\mathit{\text{i}}}{\mathit{\text{N}}}_{\mathit{\text{i}},\mathit{\text{k}}}\left(\mathit{\text{t}}\right)}& & \left(3.10\right)\end{array}$

where, as usual, Pi are the control points and Ni,k(t) are the blending functions defined recursively in the following way:

$\begin{array}{ccc}{\mathit{\text{N}}}_{\mathit{\text{i}},\mathit{\text{k}}}\left(\mathit{\text{t}}\right)=\left(\frac{\mathit{\text{t}}-{\mathit{\text{t}}}_{\mathit{\text{i}}}}{{\mathit{\text{t}}}_{\mathit{\text{i}}+\mathit{\text{k}}}-{\mathit{\text{t}}}_{\mathit{\text{i}}}}\right){\mathit{\text{N}}}_{\mathit{\text{i}},\mathit{\text{k}}-1}\left(\mathit{\text{t}}\right)+\frac{{\mathit{\text{t}}}_{\mathit{\text{i}}+\mathit{\text{k}}+1}-\mathit{\text{t}}}{{\mathit{\text{t}}}_{\mathit{\text{i}}+\mathit{\text{k}}+1}-{\mathit{\text{t}}}_{\mathit{\text{i}}+1}}{\mathit{\text{N}}}_{\mathit{\text{i}}+1,\mathit{\text{k}}-1}\left(\mathit{\text{t}}\right)& & \left(3.11\right)\end{array}$

for k > 0 and

$\begin{array}{ccc}{\mathit{\text{N}}}_{\mathit{\text{i}},0}\left(\mathit{\text{t}}\right)=\{\begin{array}{ll}1\hfill & \mathit{\text{t}}\in \left[{\mathit{\text{t}}}_{\mathit{\text{i}}},{\mathit{\text{t}}}_{\mathit{\text{i}}+1}\right)\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}& & \left(3.12\right)\end{array}$

for k = 0. The set $\left\{{\mathit{\text{t}}}_0,{\mathit{\text{t}}}_1,\dots ,{\mathit{\text{t}}}_{\mathit{\text{n}}+\mathit{\text{k}}}\right\}$ is a sequence of values referred to as knots sequence. Such sequence influences the shape of the B-spline. In particular, if the knots sequence is uniform, that is, the knots values are equidistant, the B-spline definition becomes ${\mathit{\text{N}}}_{\mathit{\text{i}}+1,\mathit{\text{k}}}\left(\mathit{\text{t}}\right)={\mathit{\text{N}}}_{\mathit{\text{i}},\mathit{\text{k}}}\left(\mathit{\text{t}}-{\mathit{\text{t}}}_{\mathit{\text{i}}}\right)$, that is, the blending functions move along the sequence (see Figure 3.11). A uniform B-spline blending function Ni,k(.) is a function of degree k having support in the interval $\left[{\mathit{\text{t}}}_{\mathit{\text{i}}},{\mathit{\text{t}}}_{\mathit{\text{i}}+\mathit{\text{k}}}\right)$. Note that for B-spline the number of knots k determines the degree of the curve joining the control points and not the number of control points as for the Bézier curves. In other words, B-splines are local and the way they locally influence the curve’s shape depends on the knots’ values; more precisely ${\mathit{\text{N}}}_{\mathit{\text{i}},\mathit{\text{p}}}\left(\mathit{\text{t}}\right)\ge 0$ when $\mathit{\text{t}}\in \left[{\mathit{\text{t}}}_{\mathit{\text{i}}},{\mathit{\text{t}}}_{\mathit{\text{i}}+\mathit{\text{p}}+1}\right)$. Another important difference between Bézier curves and B-splines is that Bézier curves must pass through their initial and final control points, making the smoothness between curves joined together more difficult to achieve than in the case of B-splines. For all of these reasons B-splines are, in general, more flexible than Bézier curves. Some examples of B-splines of different order k defined on the same eight control points of the Bézier curves of Figure 3.10 are shown in Figure 3.12 for comparison. Note the approximating character of the B-spline curves and the fact that the greater k is, the more limited is the support of the curve with respect to the control points. This can be avoided by increasing the multiplicity of the first and last values of the knots (see [11] for more details).

3.4.4 From Parametric Curves to Parametric Surfaces

The extension from parametric curves to parametric surfaces is simple. In this case the parameter domain is a subset of ℝ2 instead of ℝ and three bivariate functions (f : ℝ2 → ℝ) defining the mapping between the parameters and the 3D space:

$\begin{array}{ccc}\mathit{\text{S}}\left(\mathit{\text{u}},\mathit{\text{v}}\right)=\left(\mathit{\text{X}}\left(\mathit{\text{u}},\mathit{\text{v}}\right),\mathit{\text{Y}}\left(\mathit{\text{u}},\mathit{\text{v}}\right),\mathit{\text{Z}}\left(\mathit{\text{u}},\mathit{\text{v}}\right)\right)& & \left(3.13\right)\end{array}$

u and v are the surface parameters. Even in this case the u and v parameters usually range from 0 to 1.

In the case of parametric curves, we have seen that Equation (3.2) can be expressed as a linear combination of control points with some blending functions (3.3). This last equation can be extended to the case of surfaces in several ways. The most used one is the tensor product surface, defined as:

$\begin{array}{ccc}\mathit{\text{S}}\left(\mathit{\text{u}},\mathit{\text{v}}\right)={\displaystyle \sum _{\mathit{\text{i}}=0}^{\mathit{\text{n}}}{\displaystyle \sum _{\mathit{\text{j}}=0}^{\mathit{\text{m}}}{\mathit{\text{P}}}_{\mathit{\text{i}}\mathit{\text{j}}}{\mathit{\text{B}}}_{\mathit{\text{i}}}\left(\mathit{\text{u}}\right){\mathit{\text{B}}}_{\mathit{\text{j}}}\left(\mathit{\text{v}}\right)}}& & \left(3.14\right)\end{array}$

where Pij are the initial control points and {Bi(.)} and {Bj(.)} are the blending functions. In this case the control points Pij are referred to as the control net of the surface S. Tensor product surfaces are also named rectangular patches, since the domain of the parameter (u, v) is a rectangle (in ℝ2). In the following section we are going to describe two important parametric surfaces: Bézier patches, which are the extension of Bézier curves, and NURBS, which are the extensions of B-splines.

3.4.5 Bézier Patches

According to the tensor product surface the definition of Bézier curves can be extended to surfaces in the following way:

$\begin{array}{ccc}\mathit{\text{S}}\left(\mathit{\text{u}},\mathit{\text{v}}\right)={\displaystyle \sum _{\mathit{\text{j}}=0}^{\mathit{\text{m}}}{\displaystyle \sum _{\mathit{\text{i}}=0}^{\mathit{\text{n}}}{\mathit{\text{P}}}_{\mathit{\text{i}}\mathit{\text{j}}}{\mathit{\text{B}}}_{\mathit{\text{i}},\mathit{\text{n}}}\left(\mathit{\text{u}}\right){\mathit{\text{B}}}_{\mathit{\text{j}},\mathit{\text{m}}}\left(\mathit{\text{v}}\right)}}& & \left(3.15\right)\end{array}$

where Pij are the points of the control net, {Bi,n(.)} are Bernstein polynomials of degree n and {Bj,m(.)} are Bernstein polynomials of degree m. Figure 3.13 shows an example of a bi-cubic Bézier patch. In this case the control net of the patch is formed by 4 × 4 control points.

The Bézier patches can be assembled together to represent the shape of complex 3D objects. Figure 3.14 shows an example. The model represented in this example is the Utah teapot, a model of a teapot realized in 1975 by Martin Newell, a member of the pioneering graphics program at the University of Utah. Since then, this simple, round, solid, partially concave mathematical model has been a reference object (and something of an inside joke) in the computer graphics community.

3.4.6 NURBS Surfaces

The non-uniform rational B-splines, or NURBS, are the generalization of the non-rational B-splines (3.10) just seen. Such generalization consists of the use of ratios of blending functions. This extends the set of curves that can be represented. Note that Bézier curves are ultimately polynomes and polynomes cannot represent conic curves, that is, curves obtained by intersecting a cone with a plane (such as a circle), but the ratio of polynomials can. So using the ratio of blending functions expands the class of surfaces that can be represented. The term non-uniform refers to the fact that the knots sequence can not be uniform. So, a NURBS curve of order k is defined as:

$\begin{array}{ccc}\mathit{\text{P}}\left(\mathit{\text{t}}\right)=\frac{{\displaystyle {\sum }_{\mathit{\text{i}}=0}^{\mathit{\text{n}}}{\mathit{\text{w}}}_{\mathit{\text{i}}}{\mathit{\text{P}}}_{\mathit{\text{i}}}{\mathit{\text{N}}}_{\mathit{\text{i}},\mathit{\text{k}}}\left(\mathit{\text{t}}\right)}}{{\displaystyle {\sum }_{\mathit{\text{i}}=0}^{\mathit{\text{n}}}{\mathit{\text{w}}}_{\mathit{\text{i}}}{\mathit{\text{N}}}_{\mathit{\text{i}},\mathit{\text{k}}}\left(\mathit{\text{t}}\right)}}& & \left(3.16\right)\end{array}$

where n is the number of control points, Pi are the control points, {Ni,k (t)} is the same blending function as for the B-spline curves and wi are weights used to alter the shape of the curve. According to the tensor product surface we can extend the definition of NURBS curves in the same manner as Bézier patches to obtain NURBS surfaces:

$\begin{array}{ccc}\mathit{\text{S}}\left(\mathit{\text{u}},\mathit{\text{v}}\right)=\frac{{\displaystyle {\sum }_{\mathit{\text{i}}=0}^{\mathit{\text{n}}}{\displaystyle {\sum }_{\mathit{\text{j}}=0}^{\mathit{\text{m}}}{\mathit{\text{w}}}_{\mathit{\text{i}}\mathit{\text{j}}}{\mathit{\text{P}}}_{\mathit{\text{i}}\mathit{\text{j}}}{\mathit{\text{N}}}_{\mathit{\text{i}},\mathit{\text{k}}}\left(\mathit{\text{u}}\right){\mathit{\text{N}}}_{\mathit{\text{j}},\mathit{\text{m}}}\left(\mathit{\text{v}}\right)}}}{{\displaystyle {\sum }_{\mathit{\text{i}}=0}^{\mathit{\text{n}}}{\displaystyle {\sum }_{\mathit{\text{j}}=0}^{\mathit{\text{m}}}{\mathit{\text{w}}}_{\mathit{\text{i}}\mathit{\text{j}}}{\mathit{\text{N}}}_{\mathit{\text{i}},\mathit{\text{k}}}\left(\mathit{\text{u}}\right){\mathit{\text{N}}}_{\mathit{\text{j}},\mathit{\text{m}}}\left(\mathit{\text{v}}\right)}}}& & \left(3.17\right)\end{array}$

Thanks to the properties of B-Splines, the local control property still remains valid for the NURBS, that is, the modification of a control point only affects the surface shape in its neighborhood. So, it is easy to control the shape of a large surface. Mainly for this reason NURBS surfaces are the base modeling tool of powerful and famous geometric modellng software such as Maya® and Rhino®. Figure 3.15 depicts an example of a 3D model realized using NURBS.

3.4.7 Advantages and Disadvantages

Parametric surfaces are very flexible representations of 3D objects with a lot of interesting properties; for example, parameterization is just available by definition, geometry processing is analytical (that is, the tangent of the surface in a point is computed by derivation of the parametric equation), they can be easily converted to other representations, and so on. The main limitation of this representation concerns the difficulties in automatically generating a model composed of a set of parametric surfaces. In fact, as just mentioned, the most typical use of parametric surfaces is in geometric modeling software, that is, in the manual generation of 3D objects.

3.5 Voxels

Voxels are commonly used to represent volumetric data. This representation can be seen as the natural extension of two-dimensional images to the third dimension. Like a digital image is represented as a matrix of picture elements, called pixels, a volumetric image is represented by a set of volume elements, called voxels, arranged on a regular 3D grid (see Figure 3.16). Each voxel of this 3D grid provides information about the volume. Depending on the specific application, many types of data can be stored into each voxel. Such information could be the density of the volume element, the temperature, the color, etc.

One of the main application domains of the voxels representation is medical imaging, because devices to acquire medical information such as computerized tomography (CT) or magnetic resonance (MR) create a volume of data. For example a voxel may store a code indicating the type of tissue occupying that physical space, so that we can produce an image like the one shown in Figure 3.17.

3.5.1 Rendering Voxels

Unlike the other representations, rendering a volume of data does not have a unique meaning. The reason is that we are just able to see one 2D image at time. Figures 3.17 and 3.16 show two examples where the voxels in the boundary of the objects are shown, because there are representations of solid non-transparent objects. On the other hand, if we store a pressure value in each voxel we may want another type of visualization. Typically, we may want to see the region with a specific value of pressure. More formally, if we call f (x,y,z) the function that, given a three-dimensional point, returns the value stored in the voxel grid, and the pressure value we are looking for is c, we want to render the iso-surface $\mathit{\text{S}}=\left\{\left(\mathit{\text{x}},\mathit{\text{y}},\mathit{\text{z}}\right)|\mathit{\text{f}}\left(\mathit{\text{x}},\mathit{\text{y}},\mathit{\text{z}}\right)=\mathit{\text{c}}\right\}$. Note that this is none other than the implicit representation shown in Section 3.3, where the function f is not defined analytically but by samples. The most well established way to do that is to extract from the voxels a polygon representation of the isosurface S by means of the marching cubes algorithm [26]. Other more recent approaches to extract a mesh from volume data can be found in [20, 44].

Mesh-to-voxels conversion corresponds to the 3D version of polygon rasterization we will see in detail in Chapter 5. Although computationally demanding, it can be efficiently performed by exploiting modern graphics hardware [24].

3.5.2 Advantages and Disadvantages

The voxels representation has several advantages: it is conceptually simple and easy to encode in a data structure; it is easy to test if a point is inside or outside the volume, and the extension of many image processing algorithms to voxels is natural. Voxel representation may also be used for editing if very local modifications are done, such as in the case of digital sculpting.

The disadvantages of using voxels compared to polygon meshes or parametric surfaces is the very same as between raster images and vectorial images, that is: the accuracy of the description depends on the resolution of the grid. This means that if our goal is to represent a solid object such as the torus in Figure 3.16, a parametric surface will do a better job than a voxel representation. Furthermore, making global modifications to the shapes or changing their position in space (translating or rotating) is costly.

3.6 Constructive Solid Geometry (CSG)

Constructive solid geometry (or CSG) represents the volume of a 3D object by combining simple solid shapes called primitives with boolean operations such as union, difference, and intersection. Common primitives are planes, boxes, tetrahedra, spheres, cylinders, etc. Usually the model is stored as a binary tree where the leaf nodes are the primitives and each branch node is a boolean operator (Figure 3.18 shows an example).

The primitives can be defined, using implicit equations, as the set of points that satisfy the equation $\mathit{\text{f}}\left(\mathit{\text{x}},\mathit{\text{y}},\mathit{\text{z}}\right)<0$, where f(.) = 0 is an implicit surface function. From this definition the points such that $\mathit{\text{f}}\left(\mathit{\text{x}},\mathit{\text{y}},\mathit{\text{z}}\right)>0$ are outside the volume bounded by the surface defined through f(.). This last fact is assumed conventionally. Some primitives are defined by more than one implicit equations (e.g., a cube).

3.6.1 Advantages and Disadvantages

The constructive solid geometry finds its main application in the CAD/CAM field where the exact geometric modeling of the parts of the modeled object (e.g., a mechanical piece) is required. Though useful for such applications, in general CSG is not an efficient representation; the rendering must pass through a conversion step into triangle meshes, editing complex shape is difficult, and the compactness of the representation much depends on how the model is created.

3.7 Subdivision Surfaces

The techniques to create curves and surfaces through a process of subdivision are relatively recent. Informally, subdivision surfaces can be thought of as a polygon mesh plus a set of rules that enable it to be refined (through subdivision) to better approximate the surface it represents. In this way subdivision surfaces have the same properties as polygon meshes while alleviating the problem of discrete approximation. This motivates the growing interest in subdivision methods in geometric modeling: subdivision bridges the gap between discrete and continuous representations of curves and surfaces. In the next section, as for the description of parametric surfaces, we begin to present an example of curves generation through subdivision, and then we describe subdivision surfaces.

3.7.1 Chaikin’s Algorithm

The Chaikin’s algorithm is a method to generate curves starting from a set of control points by means of subdivision. Let us assume that the initial curve P0 is represented by the sequence of vertices $\left\{{\mathit{\text{p}}}_1^0,{\mathit{\text{p}}}_2^0,\dots ,{\mathit{\text{p}}}_{\mathit{\text{n}}}^0\right\}$ (the superscript of the points indicates the level of subdivision of the curve). The zero level corresponds to the original control polygon. At each subdivision step Chaikin’s scheme creates two new vertices between each pair of consecutive ones using the following subdivision rules:

$\begin{array}{ccc}\begin{array}{l}{\mathit{\text{q}}}_{2\mathit{\text{i}}}^{\mathit{\text{k}}+1}=\frac{3}{4}{\mathit{\text{p}}}_{\mathit{\text{i}}}^{\mathit{\text{k}}}+\frac{1}{4}{\mathit{\text{p}}}_{\mathit{\text{i}}+1}^{\mathit{\text{k}}}\hfill \\ {\mathit{\text{q}}}_{2\mathit{\text{i}}+1}^{\mathit{\text{k}}+1}=\frac{1}{4}{\mathit{\text{p}}}_{\mathit{\text{i}}}^{\mathit{\text{k}}}+\frac{3}{4}{\mathit{\text{p}}}_{\mathit{\text{i}}+1}^{\mathit{\text{k}}}\hfill \end{array}& & \left(3.18\right)\end{array}$

where ${\mathit{\text{q}}}_{\mathit{\text{i}}}^{\mathit{\text{k}}+1}$ are the new generated points at level of subdivision k + 1. After the generation of the new points the old vertices are discarded and only the new points ${\mathit{\text{q}}}_{\mathit{\text{i}}}^{\mathit{\text{k}}+1}$ define the curve at level k + 1. Figure 3.19 shows the result of the first step of subdivision on a curve formed by 4 points. By iteratively applying (3.18) we obtain the curves P1, P2 and so on. When k approaches infinity a continuous curve is generated. This limit curve is indicated with P∞. The geometric properties of the limit curve depend on the specific subdivision rules used to generate it. In particular, Chaikin’s scheme generates a quadratic B-spline. Like for parametric surfaces, a subdivision scheme may be interpolating or approximating. If the limit curve interpolates the points of the initial control polygon then the scheme is interpolating. This happens if after each subdivision step both the old and the new generated vertices belong to the curve, and the old vertices remain in the same position. On the other hand, if after each subdivision step the old vertices are discarded or moved according to some rules the limit curve does not interpolate the initial control points and the scheme is approximating. The Chaikin’s scheme belongs to the latter category since, after each subdivision step, the old vertices are discarded.

3.7.2 The 4-Point Algorithm

For completeness, we present an example of an interpolating scheme for curve generation called the 4-point algorithm [8]. This scheme uses the four consequent points in the sequence, ${\mathit{\text{p}}}_{\mathit{\text{i}}-2},{\mathit{\text{p}}}_{\mathit{\text{i}}-1},{\mathit{\text{p}}}_{\mathit{\text{i}}}$ and ${\mathit{\text{p}}}_{\mathit{\text{i}}+1}$, to create a new point. The subdivision rules are:

$\begin{array}{ccc}\begin{array}{l}{\mathit{\text{q}}}_{2\mathit{\text{i}}}^{\mathit{\text{k}}+1}={\mathit{\text{p}}}_{\mathit{\text{i}}}^{\mathit{\text{k}}}\hfill \\ {\mathit{\text{q}}}_{2\mathit{\text{i}}+1}^{\mathit{\text{k}}+1}=\left(\frac{1}{2}+\mathit{\text{w}}\right)\left({\mathit{\text{p}}}_{\mathit{\text{i}}}^{\mathit{\text{k}}}+{\mathit{\text{p}}}_{\mathit{\text{i}}+1}^{\mathit{\text{k}}}\right)-\mathit{\text{w}}\left({\mathit{\text{p}}}_{\mathit{\text{i}}-1}^{\mathit{\text{k}}}+{\mathit{\text{p}}}_{\mathit{\text{i}}+2}^{\mathit{\text{k}}}\right)\hfill \end{array}& & \left(3.19\right)\end{array}$

The first equation in (3.19) means that the original points do not change as required by an interpolating scheme. The second equation is for creating the new points between ${\mathit{\text{p}}}_{\mathit{\text{i}}}^{\mathit{\text{k}}}$ and ${\mathit{\text{p}}}_{\mathit{\text{i}}+1}^{\mathit{\text{k}}}$. The weight w enables us to control the final shape of the curve by increasing or decreasing the “tension” of the curve. When w = 0 the resulting curve is a linear interpolation of the starting points. For w = 1/16 a cubic interpolation is achieved. For 0 < w < 1/8 the resulting curve is always continuous and differentiable (C1).

3.7.3 Subdivision Methods for Surfaces

Subdivision methods for surfaces generation work in a way analogous to those for curves: starting from an initial control mesh (M0) the subdivision rules that define the subdivision scheme are iteratively applied to obtain a finer mesh (Mk) at level of subdivision k. The initial mesh can also be seen as the equivalent of the control net of the parametric surface. The difference between the two representations relies on the way the surface is generated.

Obviously, different subdivision schemes generate surfaces with different geometric properties. Here, we would like to give a panoramic of such methods and make the reader able to understand how a subdivision method is characterized. In particular we focus on stationary schemes. A subdivision scheme is said to be stationary if the subdivision rules do not depend on the level of subdivision but remain the same during all the subdivision steps. Other classes of subdivision schemes, such as variational subdivision, are not discussed here.

3.7.4 Classification

In these last years several stationary schemes have been developed. A classification of them related to their basic properties is particularly useful since it helps us to immediately understand how a certain subdivision method works depending on its categorization.

3.7.4.1 Triangular or Quadrilateral

Subdivision schemes work on polygon meshes. Although there are proposals for mesh with arbitrary combinations of cells, the most used and known approaches are designed for triangle mesh and quadrilateral meshes that have their specific subdivision schemes.

3.7.4.2 Primal or Dual

A scheme is said to be primal if it proceeds by subdividing the faces of the mesh (face splitting), and dual if it splits the vertices (vertex splitting).

The 1-to-4 split shown in Figure 3.20 is a common primal scheme: each face is subdivided into four new faces by inserting a new vertex for each edge of the coarse mesh, retaining old vertices, and then connecting the new inserted vertices together.

The dual schemes work on the dual of the polygon mesh, which is obtained by taking the centroids of the faces as vertices, and connecting those in adjacent faces by an edge. Then for each vertex a new one is created inside each face adjacent to the vertex, as shown in the top row of Figure 3.20 (third row from left), and they are connected as shown in the last row of the figure.

Note that for quadrilateral meshes this can be done in such a way that the refined mesh has only quadrilateral faces, while in the case of triangles, vertex split (dual) schemes result in non-nesting hexagonal tilings. In this sense quadrilateral tilings are special: they support both primal and dual subdivision schemes naturally.

3.7.4.3 Approximation vs Interpolation

As previously stated, a subdivision method can produce a curve/surface, that is an interpolation of the initial curve/surface, or that is an approximation of the initial control net. By considering this property we can classify the subdivision schemes into interpolating and approximating. Primal schemes can be approximating or interpolating. Dual schemes are always intrinsically approximating by definition. Interpolation is an attractive property for several reasons. First, the control points are also points of the limit surface. Second, many algorithms can be considerably simplified improving computational efficiency. Additionally, if needed, the refinement of the mesh can be tuned locally by performing a different number of subdivision steps in different parts of the mesh. Nevertheless, the quality of the surfaces generated by interpolating schemes is lower than that of approximating schemes. Also, the convergence to the limit surface is typically slower with respect to approximating schemes.

3.7.4.4 Smoothness

The smoothness of the limit surface, that is, of the surface obtained applying the subdivision scheme an infinite number of times, is measured by its continuity properties. The limit surface could be continuous and differentiable (C1), continuous and twice differentiable (C2) and so on.

Many subdivision schemes with different properties have been proposed, and analyzing them is out of the scope of this book. Just to give you an idea of how such schemes are designed, in the following we show some examples. In particular we will describe the Loop scheme, which is an approximating scheme for triangular meshes, and the (modified) butterfly scheme, which is an interpolation scheme for triangular meshes.

3.7.5 Subdivision Schemes

In this section we present some classical subdivision schemes for triangular meshes to give an idea of how a subdivision scheme is defined. The approximating Loop scheme [25] and the interpolating butterfly scheme [10] are presented. Both these schemes are primal. Often, the subdivision rules of a specific subdivision method are visualized using masks of weights. These masks are special drawings that show which control points are used to compute the new ones and the relative weights. This is a standard way to give a compact description of a subdivision scheme. Decoding the subdivision rules for these masks is not difficult, but before explaining it we need to introduce some of the terminology used for the description of the schemes.

We can see from Figure 3.20 that subdivision schemes defined on triangular meshes create new vertices of valence 6 in the interior of the mesh, while subdivision schemes for quadrilateral meshes generate vertices with valence 4. This fact relies on the definition of semi-regular meshes, where all the regular vertices have valence 6 (for triangle meshes) except the vertices of the initial control mesh, which can have any valence. For a quadrilateral mesh the regular vertices have valence 4. The non-regular vertices are called extraordinary vertices. Often, extraordinary vertices require different subdivision rules than the regular ones. The masks of weights can be of two typs: the masks of odd vertices and the masks for even vertices. The odd vertices are the ones created at the given level of subdivision while the even vertices are the ones inherited from the previous level of subdivision. This notation comes from analyzing the one-dimensional case, when vertices of the control polygon can be enumerated sequentially, thus resulting in odd numbers for the new inserted vertices [48]. The subdivision rules have to be adapted for the boundary of the mesh. The same rules can be used to preserve sharp features of the initial control mesh by tagging the interior edges of interest as boundary edges. Such tagged edges are called creases (see also Section 6.6.1). Obtaining the subdivision rules for its corresponding mask is not difficult. The new vertices are shown in the mask as a black dot. The edges indicate which neighbor vertices have to be taken into account to calculate the subdivision rules. For example, referring to the masks of the Loop scheme of Figure 3.21, the interior odd vertex ${\mathit{\text{v}}}^{\mathit{\text{j}}+1}$, that is the new inserted vertex, is computed by centering the relative mask over it, obtaining:

$\begin{array}{ccc}{\mathit{\text{v}}}^{\mathit{\text{j}}+1}=\frac{3}{8}{\mathit{\text{v}}}_1^{\mathit{\text{j}}}+\frac{3}{8}{\mathit{\text{v}}}_2^{\mathit{\text{j}}}+\frac{1}{8}{\mathit{\text{v}}}_3^{\mathit{\text{j}}}+\frac{1}{8}{\mathit{\text{v}}}_4^{\mathit{\text{j}}}& & \left(3.20\right)\end{array}$

where v1 and v2 are the immediate neighbors of the new vertex v, and v3 and v4 are the other two vertices of the triangles that share the edge where v will be inserted. The mask for the even vertices, which are present only in the approximating schemes, are used to modify the position of the existing vertices.

3.7.5.1 Loop Scheme

The Loop scheme is an approximating scheme for triangle meshes proposed by Charles Loop [25]. This scheme produces surfaces that are C2 continuous everywhere except at extraordinary vertices where the limit surface is C1-continuous. The masks of weights for the Loop scheme are shown in Figure 3.21. As proposed by Loop, the parameter β can be computed as $\mathit{\text{β}}=\frac{1}{\mathit{\text{n}}}\left(\frac{5}{8}-{\left(\frac{3}{8}+\frac{1}{4}\text{cos}\frac{2\mathit{\text{π}}}{\mathit{\text{n}}}\right)}^2\right)$ where n is the number of adjacent vertices.

3.7.5.2 Modified Butterfly Scheme

The butterfly scheme was first proposed by Dyn et al. [10]. The limit surface is not C1-continuous at extraordinary points of valence k = 3 and k > 7 [46], while it is C1 on regular meshes. A modification of the original butterfly scheme was proposed by Zorin et al. [47]. This variant guarantees C1-continuous surfaces for arbitrary meshes. The masks of this scheme are given in Figure 3.22. The coefficients si for the extraordinary vertices are $\left\{{\mathit{\text{s}}}_0=\frac{5}{12},{\mathit{\text{s}}}_1=-\frac{1}{12},{\mathit{\text{s}}}_2=-\frac{1}{12}\right\}$ for $\mathit{\text{k}}=3,\left\{{\mathit{\text{s}}}_0=\frac{3}{8},{\mathit{\text{s}}}_1=0,{\mathit{\text{s}}}_2=-\frac{1}{8},{\mathit{\text{s}}}_3=0\right\}$ for k = 4 and the general formula for k > 5 is:

$\begin{array}{ccc}{\mathit{\text{s}}}_{\mathit{\text{i}}}=\frac{1}{\mathit{\text{k}}}\left(\frac{1}{4}+\text{cos}\left(\frac{2\mathit{\text{i}}\mathit{\text{π}}}{\mathit{\text{k}}}\right)+\frac{1}{2}\text{cos}\left(\frac{4\mathit{\text{i}}\mathit{\text{π}}}{\mathit{\text{k}}}\right)\right)& & \left(3.21\right)\end{array}$

Since this scheme is interpolating, only the masks for the odd vertices are given, and the even vertices preserve its position during each subdivision step.

3.7.6 Advantages and Disadvantages

The subdivision surface attempts to overcome the weak point of meshes representation bridging the gap between a discrete and a continuous representation. Thanks to the subdivision schemes small meshes can be used to represent smooth surfaces, which otherwise require a huge number of triangles to be defined. Moreover, the editing operations are not as complex as in the case of meshes since the effort is only into the drawing of the initial mesh. Hence, this representation is powerful and flexible. In recent years, subdivision surfaces are gaining diffusion and several geometric modeling software tools such as Maya® include them.

3.8 Data Structures for Polygon Meshes

As stated before, polygon meshes are the common denominator of the other representations, and, furthermore, the graphics hardware is especially good in rendering triangle meshes. Therefore it is useful to see what data structures are used to encode this kind of representation. Please note that, although we will use trinagle meshes as examples, the following data structures work for generic polygon meshes.

One of the main factors that influences how a mesh should be implemented is the queries the application has to do on it. With the term query we mean the retrieval of information about the connectivity of the mesh elements. Some examples of queries on a mesh are:

• Which are the faces adjacent to a given vertex?
• Which are the edges adjacent to a given vertex?
• Which are the vertices connected with a given vertex v through the set of its adjacent edges (that is, the 1-ring of v)?

Data structures are often tailored to certain types of queries, which in turn are application dependent, so we cannot give a unique general criterion for assessing a data structure. However, we can analyze their performance in several regards:

• Queries—How efficient can the main queries listed above be made;
• Memory footprint—How much memory the data structure takes;
• Manifoldness Assumption—Can non-manifold meshes be encoded?

It will be clear that every data structure is a tradeoff between those three characteristics. Note that the memory footprint (and the description of the data structure) only takes into account the data for storing the mesh adjacencies and not data proper of the vertices, the edges or the faces (such as, for example, the normal) with the only exception being the position of the vertices.

3.8.1 Indexed Data Structure

One of the most intuitive implementations consists of storing the mesh as a sequence of triples of vertices. Typically, each face is stored as a triple of the vertices that define it.

class face {float v1 [3]; float v2[3];float v3[3];};

This data structure is trivial to update but that is the only good quality. No query besides the position of the vertex itself or “which other vertices are in the same face” can be done naturally because there is no explicit information on adjacency. The data stored is redundant, because each vertex must be stored once for each face adjacent to it.

In order to avoid vertices duplication, the vertex data can be stored in two separate arrays, the vertices array and the faces array.

class face{PointerToVertex v1, v2, v3;} ;

class vertex {float x,y,z;};

The type PointerToVertex indicates some kind of pointer to the vertices. In a C++ implementation they can be actual pointers to memory, while in JavaScript they will be integer indices indicating the position of the vertices in the array of vertices. This is why this data structure is also known as the Indexed Data Structure (see Figure 3.23). The Indexed Data Structure is still quite poor on queries. Although it allows us to query for the vertices of a given face in constant time (three pointers to follow), querying for all the faces (or edges, or vertices) adjacent to a vertex requires traversing the vector of the faces. The memory footprint is, on average, the same as the simple sequence of triples. This data structure is still very simple and update operations such as adding/removing one face are easy to do. Furthermore, the Indexed Data Structure can encode non-manifold meshes.

Both these data structures map directly on the WebGL internal format for rendering. This means that when we have the vector of vertices and the vector of faces, we may copy them directly on GPU memory for rendering, as we already did in Section 2.3.

If our application needs to store the edges explicitly, because some kind of value must be associated to them, we can extend the Indexed Data Structure by adding the list of edges and hence have three arrays: the vertices, the edges and the faces array. This time the faces point to edges and the edges point to their vertices. Note that, with respect to the indexed data structure, accessing all the vertices of a face costs twice as much because we need to access the edge first, and from the edge the vertices.

class vertex {float x,y,z;};

class edge {PointerToVertex v1, v2;};

class face {PointerToEdge L1, L2, L3;};

3.8.2 Winged-Edge

The winged-edge is an edge-based representation of polygon meshes. It was introduced by Bruce G. Baumgart [2] in 1975 and it is one of the first data structures for meshes that allows complex queries.

First of all, this data structure assumes that the mesh is two-manifold, so each edge is shared by two faces (or one face if it is a boundary edge). The name comes from the fact that the two faces sharing the edge are its “wings.” The main element of this data structure is the edge. As Figure 3.24 illustrates, the edge we2 stores, for each of the adjacent faces f1 and f2, a pointer to each edge that shares one of its two vertices with we2. Then it also stores the pointers to its two adjacent vertices and to the two adjacent faces. The faces store a single pointer to one (any) of their edges and the vertex stores a pointer to one of its adjacent edges.

The winged edge allows us to perform queries on the 1-ring in linear time because it allows us to jump from one edge to the other by pivoting on the shared vertex. On the average, the memory footprint is three times that of the IDS and updates are more involving, although linear in time.

3.8.3 Half-Edge

The half-edge [28] is another edge-based data structure that attempts to simplify the winged-edge while maintaining its flexibility. As the name suggests, the half-edge is the “half” of a winged-edge, that is, it is a winged-edge decomposed into two (oriented) half-edges as shown in Figure 3.25.

The half-edge keeps one pointer to the previous half edge and one to the next along the loop of half edges that describes the face, plus a pointer to the other half edge on the same edge but oriented in the opposite direction. The half edge has the same characteristics as the winged edge but it is more elegant and introducing the orientation makes it so that the same queries may be done more efficiently.

Other similar data structures include the doubly connected edge list (DCEL) [31] and/or the quad-edge data structure [13]. An overview and comparison of these different data structures together with a description of their implementations can be found in [16].

3.9 The First Code: Making and Showing Simple Primitives

In this section we create the first building block for drawing our scene in 3D.

We will show and explain the code to generate some basic 3D shapes that will be used in the rest of the book. In particular, we will learn how to define a cube, a cone and a cylinder. In the next chapter these basic shapes will be assembled together to form a first sketch of our world with trees (as a combination of cylinders and cones) and cars (as a combination of cubes and cylinders).

We will encode these shapes with an IDS. We do this since, as just described in Chapter 2, in WebGL we sent geometry and other information to the rendering pipeline using typed arrays of data. For each shape we have an array of vertices:

$\begin{array}{llllll}\begin{array}{c}\underset{}{\underbrace{\begin{array}{ccc}{\mathit{\text{x}}}_0& {\mathit{\text{y}}}_0& {\mathit{\text{z}}}_0\end{array}}}\\ {\mathit{\text{v}}}_0\end{array}\hfill & \begin{array}{c}\underset{}{\underbrace{\begin{array}{ccc}{\mathit{\text{x}}}_1& {\mathit{\text{y}}}_1& {\mathit{\text{z}}}_1\end{array}}}\\ {\mathit{\text{v}}}_1\end{array}\hfill & \begin{array}{c}\cdots \\ \cdots \end{array}\hfill & \begin{array}{c}\underset{}{\underbrace{\begin{array}{ccc}{\mathit{\text{x}}}_{{\mathit{\text{N}}}_{\mathit{\text{v}}}}& {\mathit{\text{y}}}_{{\mathit{\text{N}}}_{\mathit{\text{v}}}}& {\mathit{\text{z}}}_{{\mathit{\text{N}}}_{\mathit{\text{v}}}}\end{array}}}\\ {\mathit{\text{v}}}_{{\mathit{\text{N}}}_{\mathit{\text{v}}}}\end{array}\hfill & \hfill & \left(3.22\right)\hfill \end{array}$

where Nv is the number of vertices of the mesh, and an array of faces, where each face is defined by the indices of three vertex.

$\begin{array}{llllll}\begin{array}{c}\underset{}{\underbrace{\begin{array}{ccc}\mathit{\text{v}}{0}_0& \mathit{\text{v}}{1}_0& \mathit{\text{v}}{2}_0\end{array}}}\\ {\mathit{\text{f}}}_0\end{array}\hfill & \begin{array}{c}\underset{}{\underbrace{\begin{array}{ccc}\mathit{\text{v}}{0}_1& \mathit{\text{v}}{1}_1& \mathit{\text{v}}{2}_1\end{array}}}\\ {\mathit{\text{f}}}_1\end{array}\hfill & \begin{array}{c}\cdots \\ \cdots \end{array}\hfill & \begin{array}{c}\underset{}{\underbrace{\begin{array}{ccc}\mathit{\text{v}}{0}_{{\mathit{\text{N}}}_{\mathit{\text{f}}}}& \mathit{\text{v}}{1}_{{\mathit{\text{N}}}_{\mathit{\text{f}}}}& \mathit{\text{v}}{2}_{{\mathit{\text{N}}}_{\mathit{\text{f}}}}\end{array}}}\\ {\mathit{\text{f}}}_{{\mathit{\text{N}}}_{\mathit{\text{f}}}}\end{array}\hfill & \hfill & \left(3.23\right)\hfill \end{array}$

where Nf is the number of faces (triangles) of the mesh.

3.9.1 The Cube

We first begin creating a cube centered at the origin and with sides of length two.

Listing 3.1 shows the code to define a class that represents a cube primitive. The result is shown in Figure 3.26.

The vertices are stored in the vertices array while the index of the triangles are stored in the trianglelndices array. The number of vertices and faces are stored explicitly as member variables of the class (numTriangles and numFaces, respectively). We can see that the definition of the positions of each vertex is given explicitly. The things to pay attention to in this example concern the indices of each face. Since the cube is defined by triangles we need two triangles for each face of the cube. Moreover, each triangle should respect a precise order of definition to account for CW or CCW as explained in Section 3.2.3. The consistency of the triangles’ order is particularly important when certain processing is performed on the mesh. If it is wrong, some operations, like navigating the mesh or calculating the exitant normals of the face, for example, could give wrong results.

///// CUBE DEFINTION

/////

///// Cube is defined to be centered at the origin of the 

coordinate reference system.

///// Cube size is assumed to be 2.0 × 2.0 × 2.0 .

function Cube () {

 this.name = “cube”;

 // vertices definition

 ////////////////////////////////////////////////////////////

 this.vertices = new Float32Array([

 −1.0, −1.0, 1.0,

 1.0, −1.0, 1.0

 −1.0, 1.0, 1.0,

 1.0, 1.0, 1.0,

 −1.0, −1.0, −1.0,

 1.0, −1.0, −1.0,

 −1.0, 1.0, −1.0,

 1.0, 1.0, −1.0

]);

 // triangles definition

 ////////////////////////////////////////////////////////////

 this.triangleIndices = new Uint16Array([

 0, 1, 2, 2, 1, 3, // front

 5, 4, 7, 7, 4, 6, // back

 4, 0, 6, 6, 0, 2, // left

 1, 5, 3, 3, 5, 7, // right

 2, 3, 6, 6, 3, 7, // top

 4, 5, 0, 0, 5, 1 // bottom

]);

 this.numVertices = this.vertices.length/3;

 this.numTriangles = this.triangleIndices.length/3 ;

}

LISTING 3.1: Cube primitive.

3.9.2 Cone

The definition of the cone is a bit more complex than that of the cube. The cone is defined by fixing an apex at a certain height, creating a set of vertices posed on a circle that forms the base of the cone, and connecting them to form the triangle mesh. Our cone is centered at the origin of its coordinate system and has a height of 2 units and a radius of 1 unit, as you can see in Listing 3.2 (Figure 3.27 shows the result).

In this case the generation of the geometric primitive includes the concept of “resolution” of the geometry. For resolution we mean a parameter related to the number of triangles that will compose the final geometric primitive. The more triangles are used, the more the primitive will look smooth. In this particular case, a resolution of n gives a cone composed by 2n triangles.

The vertices that form the circular base are generated in the following way: first, an angle step (Δα) is computed by subdividing 2π for the resolution of the cone: ${\text{Δ}}_{\mathit{\text{α}}}=\frac{2\mathit{\text{π}}}{\mathit{\text{n}}}$. With simple trigonometry the base vertices are calculated as:

$\begin{array}{lllll}\mathit{\text{x}}\hfill & =\hfill & \text{cos}\mathit{\text{α}}\hfill & \hfill & \hfill \\ \mathit{\text{y}}\hfill & =\hfill & 0\hfill & \hfill & \left(3.24\right)\hfill \end{array}$

$\begin{array}{lllll}\mathit{\text{z}}\hfill & =\hfill & \text{sin}\mathit{\text{ α}}\hfill & \hfill & \left(3.25\right)\hfill \end{array}$

where, in this case, y is the up axis and xz form the base plane. α is the angle corresponding to the i-th vertex, that is α = iΔ. Hence, a resolution of n generates a base composed by n + 1 vertices, the additional vertex corresponds to the origin of the axis and it is used to connect the triangles of the base of the cone. The final cone is composed by n + 2 vertices, the n + 1 of the base plus the apex.

The triangles are created by first connecting the base of the cone, and then the lateral surface of the cone. Even in this case we have to pay attention to whether the order of the indices guarantees a consistent CW or CCW orientation. To facilitate the understanding of the connections we point out that the vertices are stored in the vertices array in the following way:

$\begin{array}{r}\hfill \text{index }0\\ \hfill \text{index 1}\dots \mathit{\text{n}}\\ \hfill \text{index }\mathit{\text{n}}+1\end{array}\begin{array}{c}\to \\ \to \\ \to \end{array}\begin{array}{l}\text{apex}\hfill \\ \text{base vertices}\hfill \\ \text{center of the base}\hfill \end{array}$

where n is the value of resolution.

///// CONE DEFINITION

/////

///// Resolution is the number of faces used to tesselate the cone .

///// Cone is defined to be centered at the origin of the coordinate reference system, and lying on the XZ plane.

///// Cone height is assumed to be 2.0. Cone radius is assumed to be 1.0 .

function Cone (resolution) {

 this.name = “cone";

 // vertices definition

 ////////////////////////////////////////////////////////////

 this.vertices = new Float32Array(3*(resolution+2));

 // apex of the cone

 this.vertices [0] = 0.0;

 this.vertices [1] = 2.0;

 this.vertices [2] = 0.0;

 // base of the cone

 var radius = 1.0;

 var angle ;

 var step = 6.283185307179586476925286766559 / resolution;

var vertexoffset = 3;

for (var i = 0; i < resolution; i++) {

 angle = step * i;

 this.vertices[vertexoffset] = radius * Math.cos(angle);

 this.vertices[vertexoffset+1] = 0.0; 

 this.vertices[vertexoffset+2] = radius * Math.sin(angle);

 vertexoffset += 3;

}

 this.vertices[vertexoffset] = 0.0;

 this.vertices[vertexoffset+1] = 0.0;

 this.vertices[vertexoffset+2] = 0.0;

 // triangles defition

 ////////////////////////////////////////////////////////////

 this.triangleIndices = new Uint16Array(3*2*resolution);

 // lateral surface

 var triangleoffset = 0;

 for (var i = 0; i < resolution; i++) {

 this.triangleIndices[triangleoffset] = 0;

 this.triangleIndices [triangleoffset+ 1] = 1 + (i % resolutions);

 this.triangleIndices[triangleoffset+2] = 1 + ((i+1) % resolution);

 triangleoffset += 3;

}

 // bottom part of the cone

 for (var i = 0; i < resolution; i++) {

 this.triangleIndices[triangleoffset] = resolution+1;

 this.triangleIndices[triangleoffset+1] = 1 + (i % resolutions);

 this.triangleIndices[triangleoffset+2] = 1 + ((i+1) % resolution);

 triangleoffset += 3;

}

 this.numVertices = this.vertices.length/3;

 this.numTriangles = this.triangleIndices.length/3;

}

LISTING 3.2: Cone primitive.

3.9.3 Cylinder

The generation of the cylinder primitive is similar to that of the cone (Listing 3.3). Figure 3.28 shows the resulting primitive. The base of the cylinder lies on the xz plane and it is centered at the origin. The base of the cylinder is generated in the same way as the base of the cone; even in this case the resolution parameter corresponds to the number of vertices of the base. The upper part of the cylinder is analogue to the bottom part. Hence, the final cylinder has 2n + 2 vertices and 4n triangles if the value of resolution is n. After both the vertices of the bottom and upper part are generated, the triangles are defined, taking care to have a consistent orientation, as usual. In this case the vertices-indices correspondence is:

$\begin{array}{l}\begin{array}{r}\hfill \text{index }0\dots \mathit{\text{n}}-1\\ \hfill \text{index }\mathit{\text{n}}\dots 2\mathit{\text{n}}-1\\ \hfill \text{index 2}\mathit{\text{n}}\end{array}\begin{array}{c}\to \\ \to \\ \to \end{array}\begin{array}{l}\text{base vertices}\hfill \\ \text{upper vertices}\hfill \\ \text{center of the lower circle}\hfill \end{array}\\ \text{index 2}\mathit{\text{n}}+1\to \text{center of the upper circle}\end{array}$

///// CYLINDER DEFINITION

/////

///// Resolution is the number of faces used to tesselate the cylinder.

///// Cylinder is defined to be centered at the origin of the coordinate axis, and lying on the XZ plane.

///// Cylinder height is assumed to be 2.0. Cylinder radius is assumed to be 1.0.

function Cylinder (resolution) {

 this.name = “cylinder”;

 // vertices definition

 ////////////////////////////////////////////////////////////

 this.vertices = new Float32Array(3*(2*resolution+2));

 var radius = 1.0;

 var angle; 

 var step = 6.283185307179586476925286766559 / resolution;

 // lower circle

 var vertexoffset = 0;

 for (var i = 0; i < resolution; i++) {

 angle = step * i;

 this.vertices[vertexoffset] = radius * Math.cos(angle);

 this.vertices[vertexoffset+1] = 0.0; 

 this.vertices[vertexoffset+2] = radius * Math.sin(angle);

 vertexoffset += 3;

}

 // upper circle

 for (var i = 0; i < resolution; i++) {

 angle = step * i;

 this.vertices[vertexoffset] = radius * Math.cos(angle);

 this.vertices[vertexoffset+1] = 2.0; 

 this.vertices[vertexoffset+2] = radius * Math.sin(angle);

 vertexoffset += 3;

}

 this.vertices[vertexoffset] = 0.0;

 this.vertices[vertexoffset+1] = 0.0; 

 this.vertices[vertexoffset+2] = 0.0;

 vertexoffset += 3 :

 this.vertices[vertexoffset] = 0.0;

 this.vertices[vertexoffset+1] = 2.0;

 this.vertices[vertexoffset+2] = 0.0;

 // triangles definition

 ////////////////////////////////////////////////////////////

 this.triangleIndices = new Uint16Array(3*4*resolution);

 // lateral surface

 var triangleoffset = 0;

 for (var i = 0; i < resolution; i++)

 {

 this.triangleIndices[triangleoffset] = i;

 this.triangleIndices[triangleoffset+1] = (i+1) % resolution;

 this.triangleIndices[triangleoffset+2] = (i % resolution) + resolution;

 triangleoffset += 3;

 this.triangleIndices[triangleoffset] = (i % resolution) + resolution;

 this.triangleIndices[triangleoffset+1] = (i+1) % resolution;

 this.triangleIndices[triangleoffset+2] = ((i+1)% resolution) + resolution;

 triangleoffset += 3;

}

 // bottom of the cylinder

 for (var i = 0; i < resolution; i++)

 {

 this.triangleIndices[triangleoffset] = i;

 this.triangleIndices[triangleoffset+1] = (i+1) % resolution;

 this.triangleIndices[triangleoffset+2] = 2*resolution;

 triangleoffset += 3;

}

 // top of the cylinder

 for (var i = 0; i < resolution; i++

 {

 this.triangleIndices[triangleoffset] = resolution + i;

 this.triangleIndices[triangleoffset+1] = ((i=1) % resolutions) + resolution;

 this.triangleIndices[triangleoffset+2] = 2*resolution+1;

 triangleoffset += 3;

}

 this.numVertices = this.vertices.length/3;

 this.numTriangles = = this.triangleIndices.length/3;

}

LISTING 3.3: Cylinder primitive.

3.10 Self-Exercises

3.10.1 General

1. Which is the most compact surface representation to describe sphere? And for the intersection of three spheres? And for a statue?
2. What are the main differences between the Bézier curves and the B-Splines curves?
3. In what way can we represent volumetric data?
4. What is the main weak point of polygon meshes representation?
5. What are the goals of the subdivision surfaces?
6. In what way can we represent volumes?
7. Define a 3D object that represents an N × M grid of equi-spaced points.
8. Define a 3D object that represents the surface defined by the function F (x, y) = sin(x)cos(y) x,y ∈ [0,1].
9. Consider the code example of the cube and try to subdivide each face of the cube in four faces.