i
i
i
i
i
i
i
i
18.8. Virtual Sculpting in 3D 527
ically enabled and force feedback is simulated via the joysticks. Mathematical
models will be applied to the deformation of the mesh (as we push and pull
it) to make it look like it is made out of elastic material.
As has been the case with all the other projects proposed in this
chapter, we are not going to examine the code line by line; it’s far too long
for that. But, after reading this section and the previous chapters, you should
be able to follow the logic of the flow of execution in the program using the
commentary and comments within the code and most importantly make
changes, for example to experiment with the mathematical model of
deformation.
Figure 18.13 illustrates how our project looks and behaves. In (a). a few
shapes made up from polygon meshes will be formed into a new shape by
pushing and pulling at them with the tools. In (b), after a bit of prodding,
the shapes have been roughly deformed. In (c), part of the mesh is visible
behind some of the shapes. Bounding boxes surround the shapes in the scene.
By testing intersections between bounding boxes, the speed of the collision
detection functions is increased considerably. These simple shapes are loaded
from 3D mesh files, so it is possible to use almost any shape of mesh model.
Now, we will briefly highlight some key points in the design of the
program.
Figure 18.13. The sculpting program in action.
i
i
i
i
i
i
i
i
528 18. Building on the Basics, Some Projects in VR
18.8.1 The Idea
One of the key points about an application like this is that it must operate
in real time, so there are always going to be compromises that will have to be
made in designing it. The program has to run continuously, and it should
repeat the following tasks as quickly as possible:
1. Read the position and orientation of the joystick devices that are con-
trolling the sculpting implements/tools.
2. Check for collision between the tools and the elastic models.
3. Since the tools are regarded as solid and the models as deformable, if
they collide (and where they overlap), move the vertices in the model
out of the way. Use a mathematical algorithm to determine how other
parts of the mesh model are deformed so as to simulate the elastic be-
havior.
4. Send a signal back to the joysticks that represent the tools. This signal
will generate a force for the user to feel. On simple joysticks, all that
we can really expect to do is simulate a bit of a kick.
5. Render a 3D view of the scene, i.e., the elastic models and sculpting
tools.
The pr oject’s program code must do its best to follow the logic of these
steps. There are a number of functions to render the scene. These are called
in response to a
WM PAINT message. They act almost independently from the
rest of the code. When the program needs to indicate a change in the scene,
typically as a result of moving the tools or the math model of elasticity moving
some of the vertices in the mesh, a
WM PAINT message is dispatched.
The main action of the program is driven by a
WM TIMER message that
calls function RefreshScene() in which all these steps take place. Timing is
critical, and so the rate set for this timer is a very important design parameter.
If it is too slow, we will observe an unpleasant lag between our action in the
real world and the implements in the virtual sculptor. On the other hand, if
it is too fast, there will be insufficient time for the collision detection routines
to do their work or the mathematical elasticity simulation to come up with
an answer.
Choosing the timer interval is one of a number of critically important
decisions that have to be made in designing a program like this. The others
i
i
i
i
i
i
i
i
18.8. Virtual Sculpting in 3D 529
relate to which values to use for the parameters in the mathematical model
of elastic behavior. There is a good theoretical basis for the choice of many
parameter values in the mathematical model, but often in practice we have
to compromise because of the speed and power of the computer’s processor.
In our code, the timer setting and mathematical model parameters we quote
have evolved after experimentation, so you should feel free to see what effect
changing them has on your own system. In order to do this, we will give
a brief review of the theory underlying the core algorithm simulating elastic
deformation.
18.8.2 The Mathematical Model
When devising a method to simulate some phenomenon using a computer,
the best way to start is to see if anyone has proposed a mathematical model
for it (or for a very similar problem) before. In this case, there are many
interesting models around. Our problem is analogous to the fascinating sub-
ject of—the computer animation of cloth and similar materials [4]. Some
mathematical models for the dynamic behavior of cloth are very accurate,
and they give realistic results. Unfortunately, these rarely work in real time.
Other models may be less precise but still give acceptable-looking results, and
they do work well in real time. The model that we choose to use is one of a
spring-mass particle system, as illustrated in Figure 18.14.
In Figure 18.14(a), a 3D shape is represented by a mesh net-
work of interconnecting springs along each edge in the shape.
The vertices are represented by particles at points such as p.In
Figure 18.14(b), pulling p away from its original position es-
tablishes restoring forces in the springs that would tend to re-
Figure 18.14. A spring-mass particle system model for elastic deformation.
i
i
i
i
i
i
i
i
530 18. Building on the Basics, Some Projects in VR
turn the mesh to its original shape when we release the vertex at
point p
. In a simple one-dimensional spring (Figure 18.14(c)),
the restoring force is proportional to the extension in the length
of the spring. In Figure 18.14(d), when two or more springs
are connected, all the nonfixed points such as p
1
may move. All
new positions must be obtained simultaneously; in this 1D case
an analytic solution of the math model may be obtained. In Fig-
ure 18.14(e), if the springs forms a complex 3D network then
the effect of a distortion must be obtained using a numerical so-
lution technique. In Figure 18.14(f), when the point p is moved
to p
, the forces in all attached springs will change and the shape
of the network will adjust to a new state of equilibrium.
This model fits very well with our polygonal representation of shapes.
The edges in our mesh model correspond to the little springs connected into
a 3D network by joining the vertices together. We think of the original con-
figuration of the model as being its rest state, and as we pull one or more of
the vertices, the whole network of springs adjusts to take on a new shape, just
as they would if we really built the model out of real springs and pulled or
pushed on one of them.
The behavior of this network of springsismodeledmathematically by
using the well-known laws of Hooke and Newton. Hooke tells us that the
restoring force F in a spring is proportional to the extension in the spring
p. That is, F = k p,wherek is the constant of proportionality. Newton
tells us that the acceleration a of a particle (in our case a vertex in our mesh)
with a mass m is proportional to the force applied to it. That is, F = ma.We
also know that acceleration is the second differential of the distance moved, so
this equation can be rewritten as F = m
..
p
. This differential equation would
be relatively easy to solve for a single vertex and one spring, but in a mesh
with hundreds of vertices interconnected by springs in three dimensions, we
have to use a computer to solve it and also use a numerical approximation to
the modeling equations.
Several numerical techniques can be used to solve the equations that sim-
ulate how the vertices respond to an applied disturbance (House and Breen [4]
discuss this in depth). One technique that is fast and simple and has been used
by physicists for solving dynamic particle problems has also been shown by
computer game developers to be particularly good for our type of problem. It
is called Verlet integration [9], and whilst it allows us to avoid the complexity
of carrying out an implicit solution for the equations, we can also still avoid
i
i
i
i
i
i
i
i
18.8. Virtual Sculpting in 3D 531
some of the instabilities that occur in the simpler explicit solution techniques.
If you want to know all about the numerical solution of such problems and
all the challenges this poses, a good place to start is with [3].
Combining the laws of Hooke and Newton, we obtain a second-order
differential equation in 3D:
a =
..
p
i
=
F
m
=
k
m
n
j=1
(p
j
− p
i
), (18.1)
which we must solve at every vertex in the mesh. The term
n
j=1
(p
j
−p
i
)
sums the change in the length of each of the n edges that are connected to
vertex i. We must discretize Equation (18.1) by replacing the second order
differential
..
p
i
with an approximation. The key feature of Verlet integration
recognizes that the first order differential of p,thatis
.
p
i
, is a velocity, and that
if we are given initial values for position and velocity, we can write an iterative
pair of equations which may be used to determine how a vertex moves in
a short time inter val
t.Ifp is the current position of a vertex and v is
its current velocity then the updated position p
and updated velocity v
are
given by
v
= v + a t,
p
= p + v
t.
Normally, the velocity is not calculated explicitly and is appr oximated by
a finite difference expression for the differential. If the previous position is
given by
p then v =
p−p
t
. Thus we can rewrite our expression to compute p
as
p
= 2p − p + a t
2
.
And of course, we need to update our previous position to our current
position; that is,
p = p. By substituting for a asgiveninEquation(18.1),
we have a remarkably simple iterative algorithm that we can use to solve for
the transient behavior of a mesh. With the right choice of parameters, it
offers a visually reasonable approximation to the behavior of a squashy/elastic/
deformable object.
We can impro ve slightly on the spring-mass model of Equation (18.1) by
adding in the effect of a damper in parallel with the spring. This helps to make
the object appear less elastic. It is easy to model this effect mathematically
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.