i
i
i
i
i
i
i
i
13.2. Parametric Curved Surfaces 605
Figure 13.26. The left column shows two B´ezier patches joined with only C
0
continuity.
Clearly, there is a shading discontinuity between the patches. The right column shows
similar patches joined with C
1
continuity, which looks better. In the top row, the dashed
lines indicate the border between the two joined patches. To the upper right, the black
lines show the collinearity of the control points of the joining patches.
Figure 13.27. a) Four patches, F , G, H,andI, are to be stitched together, where all
patches share one corner. b) In the vertical direction, the three sets of three points (on
each bold line) must use the same ratio, k. This relationship is not shown here; see the
rightmost figure. A similar process is done for c), where, in the horizontal direction,
both patches must use the same ratio, l. d) When stitched together, all four patches
must use ratio k vertically, and l horizontally. e) The result is shown, in which the ratios
are correctly computed for the nine control points closest to (and including) the shared
control point.
G
1
continuity at the corners (and only there), it suffices to make the nine
points coplanar. This uses fewer degrees of freedom.
Continuity for B´ezier triangles is generally more complex, as well as
the G
1
conditions for both B´ezier patches and triangles [332, 569]. When
constructing a complex object of many B´ezier surfaces, it is often hard to
i
i
i
i
i
i
i
i
606 13. Curves and Curved Surfaces
see to it that reasonable continuity is obtained across all borders. One
solution to this is to turn to subdivision surfaces, treated in Section 13.5.
Note that C
1
continuity is required for good-looking texturing across
borders. For reflections and shading, a reasonable result is obtained with
G
1
continuity. C
1
or higher gives even better results. An example is shown
in Figure 13.26.
13.3 Implicit Surfaces
To this point, only parametric curves and surfaces have been discussed.
However, another interesting and useful class of surfaces are implicit sur-
faces. Instead of using some parameters, say u and v, to explicitly describe
a point on the surface, the following form, called the implicit function,
is used:
f(x, y, z)=f(p)=0. (13.42)
This is interpreted as follows: A point p is on the implicit surface if
the result is zero when the point is inserted into the implicit function f.
Implicit surfaces are often used in intersection testing with rays (see Sec-
tions 16.6–16.9), as they can be simpler to intersect than the corresponding
(if any) parametric surface. Another advantage of implicit surfaces is that
constructive solid geometry algorithms can be applied easily to them, that
is, objects can be subtracted from each other, logically and:ed or or:ed with
each other. Also, objects can be easily blended and deformed.
A simple example is the unit sphere, which has f(x, y, z)=x
2
+ y
2
+
z
2
−1 as its implicit function. Sometimes it is also useful to use isosurfaces
of an implicit function. An isosurface is f(x, y, z)=c,wherec is a scalar
function. So, for the unit sphere, f(x, y, z) = 3 describes an isosurface that
is a sphere centered around the origin with a radius of two.
The normal of an implicit surface is described by the partial derivatives,
called the gradient and denoted ∇f:
∇f(x, y, z)=
∂f
∂x
,
∂f
∂y
,
∂f
∂z
. (13.43)
To be able to evaluate it, Equation 13.43 must be differentiable, and
thus also continuous.
Blending of implicit surfaces is a nice feature that can be used in what is
often referred to as blobby modeling [99], soft objects, or metaballs [117].
See Figure 13.28 for a simple example. The basic idea is to use several
simple primitives, such as spheres or ellipsoids, and blend these smoothly.
Each sphere can be seen as an atom, and after blending the molecule of
i
i
i
i
i
i
i
i
13.3. Implicit Surfaces 607
Figure 13.28. The two spheres on the left are blended together into the shape on the
right.
the atoms is obtained. More mathematically, the blended surface is de-
scribed by
f(p)=
n−1
i=0
h(r
i
). (13.44)
In Equation 13.44, we assume that there are n primitive objects (atoms),
and for each atom a distance r
i
is computed. The r
i
is often the distance
from p to the center of the sphere, or some other distance. Finally, the
blending function h describes the region of influence of the atom i.There-
fore, h(0) = 1, and h(r)=0forr ≥ R,whereR defines where the re-
gion of influence ends. As an example, the following blending function by
Wyvill [117] gives second-order continuity:
h(r)=
1 −
r
2
R
2
3
,h(r)=0,r≥ R. (13.45)
Wyvill also recommends using c =1/2, that is, use the implicit surface
defined by f(p)=1/2.
Every implicit surface can also be turned into a surface consisting of
triangles. There are a number of algorithms available for performing this
operation [115, 117, 624, 1299]. One well-known example is the marching
cubes algorithm [795]. This algorithm places a three-dimensional grid over
the entire surface, and samples the implicit function at each grid point.
Each point is either inside or outside the implicit surface. Because a cube
has 8 grid points for corners, there are 256 different combinations. Each
combination then generates from zero to four triangles inside the cube to
represent the implicit surface.
See Karkanis and Stewart’s article for a review of past work on trian-
gulation of implicit surfaces [624]. Code for performing polygonalization
using algorithms by Wyvill and Bloomenthal is available on the web [116].
Tatarchuk and Shopf [1250] describe a technique they call marching tetrahe-
dra, in which the GPU can be used to find isosurfaces in a three-dimensional
i
i
i
i
i
i
i
i
608 13. Curves and Curved Surfaces
data set. Figure 3.7 on page 42 shows an example of isosurface extraction
using the geometry shader.
13.4 Subdivision Curves
Subdivision techniques are a relatively new way for creating curves and
surfaces. One reason why they are interesting is that they bridge the gap
between discrete surfaces (triangle meshes) and continuous surfaces (e.g.,
a collection of B´ezier patches). Here, we will first describe how subdivi-
sion curves work, and then discuss the more interesting subdivision surface
schemes.
Subdivision curves are best explained by an example that uses corner
cutting. See Figure 13.29. The corners of the leftmost polygon are cut off,
creating a new polygon with twice as many vertices. Then the corners of
this new polygon are cut off, and so on to infinity (or more practically:
until we cannot see any difference). The resulting curve, called the limit
curve, is smooth since all corners are cut off.
3
This is often written as
P
0
→ P
1
→ P
2
···→P
∞
,whereP
0
is the starting polygon, and P
∞
is the
limit curve.
This subdivision process can be done in many different ways, and each
is characterized by a subdivision scheme. The one shown in Figure 13.29 is
called Chaikin’s scheme [167] and works as follows. Assume the n vertices of
a polygon are P
0
= {p
0
0
,...,p
0
n−1
}, where the superscript denotes the level
Figure 13.29. Chaikin’s subdivision scheme in action. The initial polygon P
0
is subdi-
vided once into P
1
, and then again into P
2
. As can be seen, the corners of each polygon,
P
i
, are cut off during subdivision. After infinitely many subdivisions, the limit curve
P
∞
is obtained. This is an approximating scheme as the curve does not go through the
initial points.
3
This process can also be thought of as a lowpass filter since all sharp corners (high
frequency) are removed.
i
i
i
i
i
i
i
i
13.4. Subdivision Curves 609
of subdivision. Chaikin’s scheme creates two new vertices between each
subsequent pair of vertices, say p
k
i
and p
k
i+1
, of the original polygon as
p
k+1
2i
=
3
4
p
k
i
+
1
4
p
k
i+1
,
p
k+1
2i+1
=
1
4
p
k
i
+
3
4
p
k
i+1
.
(13.46)
As can be seen, the superscript changes from k to k +1, which means
that we go from one subdivision level to the next, i.e., P
k
→ P
k+1
.After
such a subdivision step is performed, the original vertices are discarded
and the new points are reconnected. This kind of behavior can be seen in
Figure 13.29, where new points are created 1/4 away from the original ver-
tices toward neighboring vertices. The beauty of subdivision schemes comes
from the simplicity of rapidly generating smooth curves. However, you do
not immediately have a parametric form of the curve as in Section 13.1,
though it can be shown that Chaikin’s algorithm generates a quadratic B-
spline [68, 332, 569, 1328].
4
So far, the presented scheme works for (closed)
polygons, but most schemes can be extended to work for open polylines as
well. In the case of Chaikin, the only difference is that the two endpoints of
the polyline are kept in each subdivision step (instead of being discarded).
This makes the curve go through the endpoints.
There are two different classes of subdivision schemes, namely approxi-
mating and interpolating. Chaikin’s scheme is approximating, as the limit
curve, in general, does not lie on the vertices of the initial polygon. This
is because the vertices are discarded (or updated, for some schemes). In
contrast, an interpolating scheme keeps all the points from the previous
subdivision step, and so the limit curve P
∞
goes through all the points of
P
0
, P
1
, P
2
, and so on. This means that the scheme interpolates the initial
polygon. An example, using the same polygon as in Figure 13.29, is shown
in Figure 13.30. This scheme uses the four nearest points to create a new
point [290]:
p
k+1
2i
= p
k
i
,
p
k+1
2i+1
=(
1
2
+ w)(p
k
i
+ p
k
i+1
) − w(p
k
i−1
+ p
k
i+2
).
(13.47)
The first line in Equation 13.47 simply means that we keep the points
from the previous step without changing them (i.e., interpolating), and
the second line is for creating a new point in between p
k
i
and p
k
i+1
.The
weight w is called a tension parameter .Whenw = 0, linear interpolation
4
A type of curve that we do not cover in this book.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.