|
ABSTRACT
The purpose of this project is to create 3D engine
that displays the interaction of non-rigid bodies. As a part
of our project we researched existing models for elastic and
deformable bodies and algorithms for their collision detection
and collision response. We have created a model of the object
as a set of points connected by springs of given elasticity factor
k. The model uses spring forces and damping to give elasticity
to the objects. Object collisions are determined using our collision
detection engine. After collision occurs the response is calculated
using physics laws.
MODEL
OF A SINGLE OBJECT
- Overview
The
objects we are working with are elastic and deformable bodies.
They change their shape under the influence of outside forces
and then return to their original shapes. Considering gravity
as an
external force, in the real world situation, even in a state
of rest, for example sitting on a table, this type of object
will
have a slight deformation of shape and due to it the springs
will not be in equilibrium. This can be used to model objects
made out
of rubber, jell, metal or other similar substances.
These objects behave according to a set of rules commonly used
in physics models. They maintain constant velocity and shape
if no external forces are applied (Newton’s First Law).
Without deformation the object has six degrees of freedom (three
for translation
and three for rotation). If an external force is applied to
some part of the object it deforms to find a state of rest
where its
internal energy is balanced by its external forces. If the
influence of the force stops, the object returns to its previous
shape, after
any vibrations have dampened. We will assume that objects are
non-breakable, do not change their elasticity over time, and
do not deform permanently.
- Prior
Work
Over the past two decades, people in academia and industry
have been working on simulating physically realistic
elastic objects.
Different models have been developed over time. Most of
them use some kind of elasticity rule combined with different
constraints Terzopoulos and Witkin presented the Hybrid
model [4], where
an object has a reference component, which represent shape
and displacement
components. These components represent a deformation from
the initial shape. In later research other models and ideas
were introduced,
including the concept of local and global deformations
[5]; using extra layer coatings [8]; using elastic grids with
additional constraints.
Recently, adaptive models for elastic and deformable bodies
were developed; some of them use mass-spring system similar
to the one
we used for our project [6]. Compared to these models,
our
model is quite simple; however it includes all the main
factors needed
to animate and provide interaction between elastic and
deformable bodies.
- Description
For our models an object is represented as a mesh of polygons,
namely triangles. The edges of the triangles possess
the physical qualities of springs. Vertices have properties
of rigid bodies
that are connected by springs. Vertices have only three
degrees of freedom – they can move in space but cannot
rotate. If a distance between two adjacent vertices shortens,
the spring
which
connects them forces them to move farther from each other
and vice versa.
The principal idea behind our model is that each point
behaves as an independent body, or particle, and only spring
forces
of its direct neighbors affect velocity and acceleration
of this point.
In our model we do not maintain information about linear
and angular acceleration or the velocity of the object,
and instead we only
store the accelerations and velocities of each particle.
-
Physics Involved
As mentioned earlier, the main forces that move and deform
the objects are the internal spring forces of is
edges. The force applied
on each vertex is calculated by the spring equation
[1]:
Where
k is elasticity constant of the object and Dx is the displacement
of the length of
the edge, and n is
number of
direct neighbors
of the vertex. Although we work in
3D, this force is calculated as projection on 1D space of each
edge.
While working with springs the problem of damping
arises. In a real world,
springs do not oscillate forever because
of the
loss
of internal energy. In graphics
and mechanics the loss can be simulated by applying
a damping on the spring.
There are
several ways to
do damping: viscous damping,
linear damping, or Rayleigh’s
damping [1]. For this project
we have chosen the viscous damping. After including
damping
the formula for the force
applied to
each vertex changes to the
following:
Where c is a damping constant and v is the velocity
of a vertex.
The displacement of each
vertex is calculated
using Newton’s
Laws and basic
formulas for the motion of the body
[2]:
To
achieve the best performance, some assumptions
should be made about
the object. As each
vertex of an object
is assumed
to have
the same
mass, the
distances between
adjacent vertices should be approximately
equal to each other. So even
if it is not needed for
the appearance,
the mesh
of the object
should
be equally
distributed
over the object’s surface,
otherwise a more sophisticated
algorithm is needed
to compute
mass
of each vertex so
that mass of the body is
uniform.
-
Algorithms
and Other Issues
After deriving the formulas for the
vertex forces there
are two problems that need
to be solved: creating
a data structure for
the object
and applying linear
algebra for projection
of 3D space to 2D or 1D.
The data structure of the model
includes a set of vertices
with velocities
and accelerations for each
vertex. Each vertex
also
holds a list
of its direct neighbors
as well as the initial (rest)
distances to each of them.
So in order to update
the position of a vertex, we
calculate the force
applied
(using
the difference
between the current and initial
distances between the vertex
and each neighbor),
then update acceleration and
velocity, and finally
compute
the displacement
from previous position. There
is also set of faces (triangles)
and
edges stored
for
each object and are used later
for the collision detection
and rendering.
The principal advantage of
our model is that natural behavior
of the elastic
object can be achieved using
a number of easily computed
algebraic
physics
equations of degree at most
two.
The object mesh is easy to
create using standard
3D graphics
tool, for example 3D
Studio Max [13]. Note that our model
does not necessarily
preserve the volume of the
body. If this is desired,
additional constrains
must be added. Also the elasticity
constant depends on the complexity
of the object
and has to be calculated for
each different object. One
of the
disadvantages
of our model is that creating
objects with no elasticity
(rigid bodies)
results in strong oscillation
which damping cannot
handle.
For this
reason, non-elastic
objects are handled by a different method.
MECHANICS
BEHIND OBJECT INTERACTION
- Overview
Given the object model presented in the previous section,
the next building block to consider is how to combine them
into a
single world. One of the factors involved in this is updating
movements between objects, namely applying the appropriate
forces to each object and updating their coordinates over
some time
step. Following any type of non-predetermined movement, some
sort of collision detection algorithm is run between all
appropriate pairs of objects. If any contact is detected,
all of the information
regarding the collision must be extracted and the appropriate
collision response mechanism is applied.
Typically in complex rendering programs or games, the objects
in space would be contained in some type of data structure,
such as an octree or kd-tree as proposed by Samet [11]. Such
an implementation
can provide several performance gains, including rendering
of objects and limiting the pairs of objects to which the
collision test must be applied. In the rendering process
these data structures
can help to determine whether an object needs to be drawn
on the screen. For example the partitioning nature of these
structures
organizes spatial information such as objects in such a way
that
they can determine when other objects are very close to it
or when one is occluded behind another. These properties
help when
trying to decide what objects need to be drawn or need to
have complex operations applied to them such namely collision
detection.
Inaccuracies in the collision detection can arise when the
time step between screen updates is large enough that the
physical forces would place them on opposite sides of each
other. To
compensate
for this scenario the objects typically require being sufficiently
scaled in size or a smaller time step has to be used in the
collision detection process.
- Prior
Work
There are many methods that have been proposed for collision
detection. Generally all objects have some sort of
boundary or more commonly a radius in which they are contained
within,
and
whenever another object comes sufficiently near, a
series of calculations are performed to see if there was
an actual
collision.
When dealing with convex objects, this method works
well because the object can be simplified to a sphere or
ellipse
and your
chances of finding a collision are higher in an early
time step. With concave objects there is a chance that
the object
could
be very complex and a collision might not be found
until several time steps later. To get around this problem
this
idea has
been taken to another level with the use of hierarchal
collision detection
[12]. As the name suggests, there are layers of boundaries
or radii that have to be penetrated before a collision
is detected. In the case of concave objects this works
well
because, after
the primary radius has been penetrated, the collision
detection is done against the next set of radii and so
forth, as necessary.
This works well when the nature of the object is sparse
or has
convex substructures, because it increases the accuracy
of the collision detection while reducing the need for
computationally
expensive algorithms.
When it is determined that the collision boundary has
been penetrated, it is required to be known exactly
if there was
a collision and
where. There are various algorithms that can calculate
this but the overall method used by most of them is
to compare
all the
faces or edges of one object and see if any of them
lie within the boundaries of the other object. While
simple in concept,
most techniques require several floating-point calculations
to check against many edges and points of every polygon
in one object
to the other. Typically there is a check to see if
either point of any edge in one object penetrates any
polygon in
the other
object. This procedure is run twice, reversing the
roles of edges and polygons between the two objects.
If this does
not
reveal
an intersection, all the individual faces and edges
are checked to see if they are coplanar and/or coincident.
When naively
implemented, this technique will still work but can
be very expensive if the
object consists of a large number of edges. In this
instance some type of selection against the object
is done in order
to select a minimal set of edges and polygons to check
against. For example, if the relative centers of two
objects can be
determined
and the two points used as a vector and treated as
the normal of a plane, then it suffices to test only
points that lie
on one side of that plane. In the situation where the
objects are represented by polynomial equations, it
is common to
check
if
the surfaces defined by these equations intersect using
any of several techniques based on integral calculus.
After it has been determined that a collision has occurred,
we need to know where the collision has occurred and
make an appropriate
response to the point of intersection. In this stage,
the need for accuracy in the location of the collision
is the
driving
factor for what collision information should collected.
In one case we can attempt to calculate the actual
point of
collision and try to isolate all the elements involved,
such as the direction
of the collision and the force being applied at that
point. At
the time of collision, if it is determined that the
two objects have penetrated each other, somewhere between
the previous
time step and the current step there was a point in
time when the
collision first occurs. So in order to find the instance
of collision, the collision data is recalculated using
a time
step that is
a half of the current time step and the previous. This
process is repeated until there is collision without
penetration
or until some threshold is met. While this solution
provides accuracy
in the collision data, it is computationally expensive
to repeat several calculations, which can produce redundant
information
between iterations. What can happen instead is that
all the
information
about the collision can be collected and then approximate
what the real collision information data should be.
- Algorithms Used
In our implementation we maintain a collection of objects,
and then at arbitrary time intervals we update their
positions in
space, check for collisions and respond appropriately
to them and repeat this process as necessary [10].
For the collision
detection step, we used a variation of a ray to triangle
intersection
algorithm. For any two objects that we find to be
within each other’s collision boundary, we iterate over the edges of
one object and check for any intersection with any of the planes
of the triangles that make up the other object. If the edge has
been found to be crossing or touching the plane, the point of
intersection with the plane is then calculated. If that point
is contained within the triangle on that plane then we have detected
a collision. As we continue to iterate over the rest of the edges,
we mark all the edges and points of one object that were found
to have intersected the other object. Then with this set of edges,
we run a depth-first search against the graph of the object’s
polygonal mesh to collect all the points that are
contained within the other object. Once this set
is complete, we apply
our collision
response system with the appropriate physics, as
described in the previous section.
IMPLEMENTATION
DETAILS
In order
to illustrate the models and algorithms we created and used,
we developed an application that takes text file
of meshes and their initial velocities as input and animates
the behavior
of these objects. This application was developed using
C++ under the Microsoft Visual C++ .NET Compiler and the
Standard C, OpenGL,
STL libraries and the Win32 API. The program structure
is intended to be cross platform compatible so there are
areas where things
such as the timing mechanism is abstracted away into
its own object.
You can download the source code here and
text files with model meshes here.
The most general class in our program is World, which contains
list of objects displayed on the screen (EObject).
Each object has list of faces (Triangle), edges (Edge), and
points (GLPoint).
The principal functional elements of the program, including
collision detection, collision response, and each point location
update
can be found in the source file EObject.cpp. In the
main loop for our program, after all models have been loaded
into memory
and initialized, we iterate over our collection of
objects calling an update on their movements using the time
span between the
last iteration and the current as the time step. After
the updates, we check all appropriate objects for collisions
against each
other. If a collision is found, we apply the appropriate
collision response mechanism for that collision.
In Windows, the standard timing library did not allow
for precision in timing beyond seconds so we had to
use the WIN32 API to achieve
greater precision. Our program uses a single thread
for execution. Rather than using the timestamps from
the system clock which
would include time allocated to other programs by the
processor, we used the timestamp for the lifetime of
the thread.
CONCLUSIONS
AND SCREENSHOTS
In the project
we presented a 3D engine for the animation of non-rigid bodies.
We were able to achieve natural
behavior of
elastic bodies and their collisions. Here is set
of screen shots which were taken from the engine:
Animation of multiple objects falling on the
ground and interaction with each other.
A
box falling on the ground and flipping over.
POSSIBLE FUTURE WORK
There are several ways to extend
this project. The first is to improve current engine. This
might include adding
global constraints
such as preserving object volume; optimizing the collision
detection algorithm by creating more sophisticated bounding
boxes for each object, improving the algorithm for spring
damping. The other possible direction is to use a similar system
to
create other types of flexible objects, for example cloth
[9] or hair. As longer term work, it might be possible to extend
our approach to create a model for much more general classes
of substances. That would require adding more physically
realistic
elements into the model, creating uniform mesh over all
the volume of the object, and finding specific constraints to
satisfy properties of different types of the material
REFERENCES
- Tongue, Benson H., “Principles of Vibration,” 1996
- Hibbeler, R. C., “Engineering mechanics. Dynamics,” 8th
ed, 1997
- Bourge, David M. “Physics for Game Developers”,
November 2001
- Terzopoulos,
D., Witkin, A, “Physically based models
with rigid and deformable components,”
Computer Graphics
and Applications, IEEE, Volume: 8 Issue: 6, Nov 1988, Page(s):
41 -51
- Metaxas,
D., Terzopoulos, D., ”Dynamic 3D models with
local and global deformations: deformable superquadrics,”
Pattern
Analysis and Machine Intelligence, IEEE Transactions, Volume:
13 Issue: 7, Jul 1991, Page(s): 703 -714
- Barr,
A., Cani, M.-P., Debunne, G., Desbrun, M.,”Adaptive
simulation of soft bodies in real-time,”
Computer Animation
2000. Proceedings, 2000, Page(s): 15 -20
- Wang,
J.-F., Wang, Y.F., “Surface reconstruction using
deformable models with interior and boundary constraints,”
Computer
Vision, 1990. Proceedings, Third International Conference,
4-7 Dec 1990, Page(s): 300 -303
- Cani-Gascuel,
M., Desbrun, M., “Animation of deformable
models using implicit surfaces,”
Visualization and Computer
Graphics, IEEE Transactions, Volume: 3 Issue: 1, Jan-Mar 1997,
Page(s): 39 -50
- Eberhardt,
B., Strasser, W., Weber, A., “A fast, flexible,
particle-system model for cloth draping,”
Computer Graphics
and Applications, IEEE, Volume: 16 Issue: 5, Sep 1996, Page(s):
52 -59
- Miller,
Kurt “flipCode - Tutorial - Collision Detection” Jan
2000. Jul 14, 2002
- Samet, Hanan, “Design and Analysis of Spatial Data Structures,” Addison-Wesley,
Reading MA.
- Ramaekers,
Marc, “Hierarchical Collision Detection Methods” May
1999. Jul 12, 2002
- “Discreet products - 3ds max” http://www.discreet.com/products/3dsmax/
|
