i
i
i
i
i
i
i
i
16.6. Warping 405
for f(P) is returned. In this case, the iso-value is returned and the implicit surface
(curve in 2D) passes through Q instead of P . Thus, the circle is warped into an
ellipse.
Barr introduced the notion of global and local deformations using the opera-
tions of twist, taper,andbend applied to parametric surfaces (Barr, 1984). The
deformations can be nested to produce models such as the one shown in Fig-
ure 16.27. Conceptually, these are easy to apply to an implicit surface, as indi-
cated in Equation (16.6).
Note that the normal cannot be calculated in a similar manner to warping a
point. This problem is similar to the problem outlined in Section 13.2 on in-
stancing. In this case, the normal can most easily be approximated using Equa-
tion (16.3.3) although the use of the Jacobian, as suggested in (Barr, 1984), yields
precise results. The Barr warps are described in the following sections.
16.6.1 Twist
In this example, the twist is around the z-axis by θ (see Figure 16.21) for three
blended implicit cylinders with a twist warp applied to them.
The twist around z is expressed as
w(x, y, z)=
⎧
⎨
⎩
x ∗ cos(θ(z)) − y ∗ sin(θ(z))
x ∗ sin(θ(z)) + y ∗cos(θ(z))
z
⎫
⎬
⎭
.
Figure 16.21. Three
blended implicit cylinders
twisted together.
Image
courtesy Erwin DeGroot
.
Figure 16.22. Three
blended implicit cylinders,
twisted then tapered.
Im-
age courtesy Erwin DeG-
root
.
16.6.2 Taper
Taper is applied along one major axis. A linear taper has proved to be the most
useful although quadratic and cubic tapers are easily implemented. For example
a linear taper along the y-axis involves changing both x-andz-coordinates. A
linear scale is applied to y between y
max
and y
min
:
s(y)=
y
max
− y
y
max
− y
min
w(x, y, z)=
⎧
⎨
⎩
s(y)x
y
s(y)z
⎫
⎬
⎭
16.6.3 Bend
Bend is also applied along one major axis. For the bend example below, the
bending rate is k measured in radians per unit length, the axis of the bend is
i
i
i
i
i
i
i
i
406 16. Implicit Modeling
(x
0
, 1/k), and the angle θ is defined as (x − x
0
) ∗ k. The bend around z is
Figure 16.23. Three
blended implicit cylinders,
twisted together, tapered
and bent.
Image courtesy
Erwin DeGroot
.
w(x, y, z)=
⎧
⎨
⎩
−sin(θ) ∗ (y −1/k)+x
0
cos(θ) ∗ (y − 1/k)+1/k
z
⎫
⎬
⎭
16.7 Precise Contact Modeling
Precise contact modeling (PCM) is a method of deforming implicit surface prim-
itives in contact situations while maintaining a precise contact surface with C
1
continuity (Gascuel, 1993). PCM is important in that it is a simple and automatic
way of showing how a model can react to its environment. This cannot be so
easily done with non-implicit methods (see Figure 16.24).
PCM is implemented by the inclusion of a deforming function s(p) that mod-
ifies the field value returned for each point. For each pair of objects, collision is
Figure 16.24. Sea
anemone deforms to im-
plicit rock.
Image courtesy
Mai Nur and X. Liang.
first detected using a bounding-box test. Once it is established that a collision is
likely, PCM is applied. A local, geometric deformation term s
i
is computed and
added to the implicit function f
i
. The volume of the colliding objects is divided
into an interpenetration region and a deformation region. The result of applying
s
i
is that the interpenetration region is compressed so that contact is maintained
without interpenetration occurring (see Figure 16.25). The effect of s
i
is attenu-
ated to zero within the propagation region so that the volume outside of the two
regions is not deformed.
interpenetration
region
propagation
region
f = f
0 1
f = 0
0
f = 0
1
P
0
P
Figure 16.25. A 2D slice through objects in collision showing the various regions and PCM
deformation.
Image courtesy Erwin DeGroot
.
i
i
i
i
i
i
i
i
16.7. Precise Contact Modeling 407
Given two skeletal elements generating fields f
1
(p) and f
2
(p), the surface
around each one is calculated as
f
1
(p)+s
1
(p)=0,
f
2
(p)+s
2
(p)=0.
We need to generate a surface common to both elements (dotted line in Fig-
ure 16.25), i.e., where they share a solution in the interpenetration region for some
p in that region:
s
1
(p) − f
1
(p)=iso, (16.7)
s
2
(p) − f
2
(p)=iso.
Intuitively, the deeper within object 1 that object 2 penetrates, the higher the im-
plicit value of object 1 and thus the more that object 2 will be compressed.
The function, s
i
is defined to produce a smooth junction at the boundary of
the interpenetration region, in other words where s
i
=0but its derivative is
greater than zero. From here to the boundary of the propagation region, s
i
is used
to attenuate the propagation to zero. The nearest point on the interpenetration
region boundary p
0
is found by following the gradient.
Within the propagation region s
i
(p)=h
i
(r),wherep =(x, y, z) is the point
whose implicit value is being calculated and r = p−p
0
(see Figure 16.26). The
value of r
i
, set by the user, defines the size of the propagation region; no defor-
mation occurs beyond this region. To control how much the objects inflate in the
propagation region, the user provides a value for the parameter α. The maximum
value of h
i
is M
i
. The current minimum of s
i
is negative in the interpenetra-
tion region and is given as s
imin
,whereM
i
= − α
i
s
i min
. Thus an object will
Figure 16.26. The function,
h
i
(
r
) is the value of the deformation function
w
i
in the propaga-
tion region.
i
i
i
i
i
i
i
i
408 16. Implicit Modeling
be compressed in the interpenetration region and will inflate in the propagation
region. The equation for h
i
is formed in two parts by two cubic polynomials that
are designed to join at r = r
i
/2, where the slope is zero:
c =
4(w
i
k − 4M
i
)
w
3
i
,
d =
4(3M
i
− w
i
k)
w
2
i
,
h
i
(r)=cr
3
+ dr
2
+ kr if r ∈ [0,w
i
/2],
h
i
(r)=
4M
i
w
3
i
(r −w
i
)
2
(4r − w
i
)
3
if r ∈ [w
i
/2,w
i
].
It is desirable that we have C
1
-continuity as we move from the interpenetra-
tion to the propagation region. Thus, h
i
(0) = k in Figure 16.26, is the directional
derivative of s
i
at the junction (marked as p
0
in Figure 16.25). As indicated in
Equation (16.7), s
i
= −f
i
in the interpenetration region, thus:
k = ∇(f
i
,p
0
)
PCM is only an approximation to a properly deformed surface, but it is an
attractive algorithm due to its simplicity.
16.8 The BlobTree
The BlobTree is a method that employs a tree structure that extended the CSG
tree to include various blending operations using skeletal primitives (Wyvill et
al., 1999). A system with similar capabilities, the Hyperfun project, used a spe-
cialized language to describe F-rep objects (Adzhiev et al., 1999).
In the BlobTree system, models are defined by expressions that combine im-
plicit primitives and the operators ∪ (union), ∩ (intersection), − (difference),
+ (blend), (super-elliptic blend), and w (warp). The BlobTree is not only the
data structure built from these expressions but also a way of visualizing the struc-
ture of the models. The operators listed above are binary with the exception of
warp, which is a unary operator. In general it is more efficient to use n-ary rather
than binary operators. The BlobTree incorporates affine transformations as nodes
so that it is also a scene graph and primitives (e.g., skeletons) form the leaf nodes.
i
i
i
i
i
i
i
i
16.8. The BlobTree 409
Figure 16.27. BlobTree. The spiral staircase is built from a central textured cylinder to
which the stairs and the railing are blended. The railing is comprised of a series of cylinders
blended with two circle (torus) primitives, blended together and further blended with a vertical
cylinder. The BlobTree is also a scene graph and instancing nodes repeat the various parts
transformed by the appropriate matrices. Each stair is made from a tapered polygon primitive
(that becomes an offset surface); intersection and union nodes combine the inflated disk with
the stair.
16.8.1 Traversing the BlobTree
An example of a BlobTree including the Barr warps and CSG operations is shown
in Figure 16.27. Other nodes can include 2D texturing (Schmidt et al., 2006), pre-
cise contact modeling, as well as animation and other attributes. The traversal of
the BlobTree is in essence very simple. All that is required to render the object
either by polygonizing or ray tracing is to find the implicit value of any point (and
the corresponding gradient). This can be done by traversing the tree. Polygoniza-
tion and ray-tracing algorithms need to evaluate the implicit field function at a
large number of points in space. The function f (N,M) returns the field value for
the node N at the point M, which depends on the type of the node. The values L
and R indicate that the left or right branch of the tree is explored.The algorithm
below is written (for simplicity) as if the tree were binary:
function f(N,M):
• primitive: f(M);
• warp: f (L(N),w(M));
• blend: f(L(N),M)+f(R(N),M));
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.