An adaptive collision detection and resolution for deformable objects using spherical implicit surface

Material Information

An adaptive collision detection and resolution for deformable objects using spherical implicit surface
Jung, Sunhwa
Place of Publication:
Denver, Colo.
University of Colorado Denver
Publication Date:
Physical Description:
viii, 45 leaves : ; 28 cm

Thesis/Dissertation Information

Master's ( Master of Science)
Degree Grantor:
University of Colorado Denver
Degree Divisions:
Department of Computer Science and Engineering, CU Denver
Degree Disciplines:
Computer Science
Committee Chair:
Choi, Min-Hyung
Committee Members:
Clark, John
Welch, Samuel


Subjects / Keywords:
Computer graphics -- Mathematical models ( lcsh )
Computer animation -- Mathematical models ( lcsh )
Collision detection (Computer animation) ( lcsh )
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )


Includes bibliographical references (leaves 42-45).
General Note:
Department of Computer Science and Engineering
Statement of Responsibility:
by Sunhwa Jung.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
62768632 ( OCLC )
LD1193.E52 2005m J86 ( lcc )

Full Text
Sunhwa Jung
B.L. Kyunghee University, 1994
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of requirements for the degree of
Master of Science
Computer Science

This thesis for the Master of Science
degree by
Sunhwa Jung
has been approved
Min-Hyung Choi
John Clark
Samuel Welch

Jung, Sunhwa (M.S., Computer Science)
An Adaptive Collision Detection and Resolution for Deformable Objects Using
Spherical Implicit Surface
Thesis directed by Associate Professor Min-Hyung Choi
A fast collision detection and resolution scheme is one of the key components for
interactive simulation of deformable objects. It is particularly challenging to reduce
the computational cost in collision detection and to achieve the robust treatment at
the same time. Since the shape and topology of a deformable object changes
continuously unlike the rigid body, an efficient and effective collision detection and
resolution is a major challenge. We present a fast and robust collision detection and
resolution scheme for deformable objects using a new enhanced spherical implicit
surface hierarchy. The penetration depth and separating distance criteria can be
adjusted depending on the application specific error tolerance. Our comparative
experiments show that the proposed method performs substantially faster than
existing algorithms for deformable object simulation with massive element-level
collisions at each iteration step. Our adaptive hierarchical approach enables us to
achieve a real-time simulation rate, well suited for interactive applications.

This abstract accurately represents the content of the candidates thesis. I recommend
its publication.
Min-Hyung Choi

I dedicate this thesis to my wife, Maria, and my two daughters, Gloria and Sarah, for
their supports for my research.

1. Introduction................................................................1
2. Related Works...............................................................3
3. Collision Handling.........................................................10
3.1 Collision Detection ......................................................10
3.1.1 Approximation Using Spherical Implicit Surface..........................10 Triangle and Node Collision Test......................................10 Edge and Edge Collision Test..........................................12
3.2 Adaptive Re-Sampling..................................................13
3.3 Collision Resolution.....................................................14
4. Cloth Simulation with Our Method ..........................................16
4.1 Cloth Simulation..........................................................16
4.2 Cloth Modeling...........................................................18
4.2.1 Mass-Spring System .....................................................18
4.2.2 Spring Connectivity.....................................................21
4.2.3 Preventing Extreme Elongation...........................................24
4.3 Experiment Simulations..................................................28

4.3.1 Cloth Piling Up Simulation
4.3.2 Cloth Falling on the Sphere Simulation.................................33
4.3.3 Sphere Colliding Simulation............................................36
5. Conclusion................................................................41

2.1 Triangles in collision detection.............................................5
3.1 Level 0 collision detection in triangle Cl, C2, and C3 and with the node P.12
3.2 Level 0 collision detection between two edges..............................13
3.3 Collision response.........................................................14
4.1 Simple mass-spring system with mass nodes and springs......................19
4.2 Three types of springs for cloth simulation................................22
4.3 Extremely elongated cloth patch............................................26
4.4 The performance comparison in the piling cloth simulation
between our method and the conventional method.............................30
4.5 The snapshots of the piling up simulation .................................31
4.6 The performance comparison in the falling cloth on the sphere simulation..33
4.7 Cloth patch remains without tangling with a busy pattern of folding........34
4.8 The performance comparison in the sphere collision cloth simulation .......36
4.9 Sphere colliding simulation................................................38

1. Introduction
Physically based simulation for deformable objects [1], [2], [4] is indispensable for
many modem character animation and medical simulation. A deformable object is
usually discretized into a set of basic meshed elements to model the geometry and
behavior of the object. It often consists of thousands of nodes to avoid undesirable
sharp folds and to represent its detailed dynamic behavior. The collision detection
and contact resolution often cost more than 90% of the total simulation time per
iteration and it is considered a major bottleneck for any deformable object
simulation. Although several researchers [9], [11], [12], [14], [16], [17] achieved
robust collision detection schemes recently, they are not applicable to interactive
applications due to the complexity of their algorithms. Recently stochastic collision
detection methods [30] have been proposed to achieve the interactive rate of
simulation. These approaches guarantee the desirable computation time for the
collision detection, but they miss significant amounts of collisions, thus robust
behavior can not be expected. In addition, the more critical issue is that the collision
resolution scheme cannot be separated from the collision detection methods. If the
collision is not resolved properly in the current step, the collision detection query in
the next step will start with unacceptable initial conditions and consequently the
collision resolution will fail. Therefore the collision detection method must

guarantee a comprehensive collision check and it has to provide enough information
about the colliding and penetrating objects so that the collision resolution scheme
can handle the collisions properly. So collision detection and resolution are
inseparable and accurate collision response can only be achieved with a well
coordinated detection and resolution scheme. In addition there must be a way to
adjust the error tolerance and a strategy to resolve a degenerate penetration situation
that guarantees the penetration free status after the collision resolution, since
unavoidable numerical drift and other geometric errors could result in element level
Our proposed method is based on a spherical implicit surface that provides a fast
and robust collision detection and resolution approximation between deformable
objects. It extends the hierarchical spherical surface to the sub-divided triangle level
adaptively to detect and resolve collisions within a tight error bound. It is designed
to handle massive collisions at a given iteration step so its applicability is wide
across variety of deformable structures as long as their surface is meshed with
triangles. Due to the controllability of collision tolerance, the view dependent
adaptive application of collision resolution can be applied to reduce the
computational cost.

2. Related Works
To reduce collision detection query space, several bounding volume hierarchies and
spatial subdivision schemes have been proposed [16], [26], [31], [32], [33], [34].
Most of them require pre-computing to generate the efficient tree structures, and
they are designed to perform a series of quick rejection tests to reduce the collision
query space. But they cannot provide enough collision information to resolve the
collisions, i.e. proximity information, separating and penetrating depth, and
involved features, for the accurate collision resolution. Therefore after finding the
primitives that violate the bounding volume conditions, a geometry based exact
collision detection method should be applied. For an exact collision detection
between surface geometric primitives, the continuous collision detection using a
coplanar condition is a de-facto standard. Originally the continuous collision
detection for a moving triangle and a point was proposed by Moore and Wilhelms
[3], It required solving a fifth polynomial, but Provot [14] reformulated the cubic
equation for the problem and extended to an edge-edge case. Bridson et al. [12]
further addressed the numerical error handling method to achieve robust collision
detection. But these methods are still expensive and have no ability to reduce the
computation time due to the nature of the triangle-triangle geometric computation.

Moreover the numerical error is inevitable in degenerated cases such as severally
stacked and pinched triangles, often found in complex cloth patches [7].
Hubbard [21] proposed a method to approximate polyhedra using a hierarchical
bounding sphere for collision detection between rigid polyhedra. This method
achieved accuracy through searching down the collision spheres in the hierarchical
structure and it provided the ability to control the computational cost by adjusting
the level of detail of the bounding spheres. But building a hierarchy that fits the
model with minimal overestimation is computationally expensive. Bradshaw
OSullivan [29] proposed methods that generate better fit sphere trees for rigid
polyhedra. However deformable objects are difficult to generate proper sphere trees
because fixed size spheres can not cover the changing geometry of the deformed
structure effectively. Recently James and Pai [34] proposed a method to build an
efficient bounding tree for reduced deformable objects but it can not be used for
general deformable objects with large deformation since it only works for simple
and limited deformation based on modal analysis.
Collision resolution is also a crucial component to achieve accurate post-collision
behavior. Baraff and Witkin [6] applied the penalty force to resolve cloth and cloth
collision. But it could be difficult to find the correct magnitude of forces for the
collision resolution, and when the contact spring force is too strong or weak it will
generate oscillations between collided regions. The other popular method is to

resolve geometrically after the penetration happens. Volino and Thalmann [9], [11]
and Provot [13] used this method and most deformable objects with volume can
utilize this method. Bridson et al [12] combined these two methods to take
advantages of them. These approaches require accurate collision information from
the previous iteration steps. Baraff et al [7] proposed a method that does not require
historical information but it has a limitation when the colliding objects do not have
closed surfaces.
Figure 2.1 Triangles in collision detection. The triangle ABC and node P are at the
initial time step, and the line triangles are the expected position of the triangles at
the next time step.

Figure 2.1 illustrates the example of the collision between moving two triangles. A,
B, and C are the nodes in the one triangle and P is the one node in the other triangle.
Va, Vb, Vc, and VPare the velocity of A, B, C, and P respectively. PA, Pb, Pc, and PP
are the position of A, B, C, and P respectively. The lined triangles are the expected
positions of the triangles at the next time step. Let t the time of the collision. The
surface normal of the triangle ABC is
N = ((Pa -Pb + 1(Va Vb)) x (Pc -Pb + t(Vc Vb))). (2.1)
The coplanar condition between the triangle ABC and point P is
N>(Pp-PB + t(Vp-VB)) = 0. (2.2)
This is the cubic equation of t. The solution of t should be in the interval (0 < t <
time step). If this condition is met, whether P is in the triangle ABC at the time to+t
should be checked.
The coefficients for the equation are following. The coefficient for t3 is
VA.y* Va.z* Vc.x VA.y* Vb.z* Vc.x Va.x*Va.z* Vc.y + VA.x*VB.z*Vc.y
- VA.y* Va.z* Vp.x + VA.y* Vb.z* Vp.x + VA.z*Vc.y*Vp.x Vb.z* Vc.y* Vp.x (2.3)
+ Va.x Va.z Vp.y Va.x Vb.z Vp.y Va.z Vc.x Vp.y + Vb.z Vc.x Vp.y.

The coefficient for t is
-Pc.y Va.x Va.z + Pp.y Va.x Va.z + Pc.x VA.y Va.z Pp.x VA.y Va.z
+ Pc.y Va.x Vb.z Pp.y Va.x Vb.z Pc.x VA.y Vb.z + Pp.x VA.y Vb.z
+ Pa.z VA.y VC.x Pb.z VA.y Vc.x + PB.y Va.z Vc.x Pp.y Va.z Vc.x
- PA.y Vb.z Vc.x + Pp.y Vb.z Vc.x Pa.z Va.x Vc.y + Pb.z Va.x Vc.y
- Pb.x Va.z Vc.y + Pp.x Va.z Vc.y + Pa.x Vb.z Vc.y Pp.x Vb.z Vc.y
+ PA.y Va.x Vc.z PB.y Va.x Vc.z Pa.x VA.y Vc.z + Pb.x VA.y Vc.z
- Pa.z VA.y Vp.x + Pb.z VA.y Vp.x PB.y Va.z Vp.x + Pc.y Va.z Vp.x (2-4)
+ PA.y Vb.z Vp.x Pc.y Vb.z Vp.x + Pa.z Vc.y Vp.x Pb.z Vc.y Vp.x
- PA.y Vc.z Vp.x + PB.y Vc.z Vp.x + Pa.z Va.x Vp.y Pb.z Va.x Vp.y
+ Pb.x Va.z Vp.y Pc.x Va.z Vp.y Pa.x Vb.z Vp.y + Pc.x Vb.z Vp.y
- Pa.z Vc.x Vp.y + Pb.z Vc.x Vp.y + Pa.x Vc.z Vp.y Pb.x Vc.z Vp.y
- PA.y Va.x Vp.z + PB.y Va.x Vp.z + Pa.x VA.y Vp.z Pb.x VA.y Vp.z
+ PA.y Vc.x Vp.z PB.y Vc.x Vp.z Pa.x Vc.y Vp.z + Pb.x Vc.y Vp.z.

The coefficient for t is
-Pa.z Pc.y Va.x + Pb.z Pc.y Va.x + PA.y Pc.z Va.x PB.y Pc.z Va.x
+ Pa.z Pp.y Va.x Pb.z Pp.y Va.x PA.y Pp.z Va.x + PB.y Pp.z Va.x
+ Pa.z Pc.x VA.y Pb.z Pc.x VA.y Pa.x Pc.z VA.y + Pb.x Pc.z VA.y
- Pa.z Pp.x VA.y + Pb.z Pp.x VA.y + Pa.x Pp.z VA.y Pb.x Pp.z VA.y
+ PB.y Pc.x Va.z Pb.x Pc.y Va.z PB.y Pp.x Va.z + Pc.y Pp.x Va.z
+ Pb.x Pp.y Va.z Pc.x Pp.y Va.z PA.y Pc.x Vb.z + Pa.x Pc.y Vb.z
+ PA.y Pp.x Vb.z Pc.y Pp.x Vb.z Pa.x Pp.y Vb.z + Pc.x Pp.y Vb.z
+ Pa.z PB.y Vc.x PA.y Pb.z Vc.x Pa.z Pp.y Vc.x + Pb.z Pp.y Vc.x
+ PA.y Pp.z Vc.x PB.y Pp.z Vc.x Pa.z Pb.x Vc.y + Pa.x Pb.z Vc.y
+ Pa.z Pp.x Vc.y Pb.z Pp.x Vc.y Pa.x Pp.z Vc.y + Pb.x Pp.z Vc.y
+ PA.y Pb.x Vc.z Pa.x PB.y Vc.z PA.y Pp.x Vc.z + PB.y Pp.x Vc.z
+ Pa.x Pp.y Vc.z Pb.x Pp.y Vc.z Pa.z PB.y Vp.x + PA.y Pb.z Vp.x
+ Pa.z Pc.y Vp.x Pb.z Pc.y Vp.x PA.y Pc.z Vp.x + PB.y Pc.z Vp.x
+ Pa.z Pb.x Vp.y Pa.x Pb.z Vp.y Pa.z Pc.x Vp.y + Pb.z Pc.x Vp.y
+ Pa.x Pc.z Vp.y Pb.x Pc.z Vp.y PA.y Pb.x Vp.z + Pa.x PB.y Vp.z
+ PA.y Pc.x Vp.z PB.y Pc.x Vp.z Pa.x Pc.y Vp.z + Pb.x Pc.y Vp.z.
The coefficient for t is
Pa.z PB.y Pc.x PA.y Pb.z Pc.x Pa.z Pb.x Pc.y + Pa.x Pb.z Pc.y
+ PA.y Pb.x Pc.z Pa.x PB.y Pc.z Pa.z PB.y Pp.x + PA.y Pb.z Pp.x
+ Pa.z Pc.y Pp.x Pb.z Pc.y Pp.x PA.y Pc.z Pp.x + PB.y Pc.z Pp.x
+ Pa.z Pb.x Pp.y Pa.x Pb.z Pp.y Pa.z Pc.x Pp.y + Pb.z Pc.x Pp.y
+ Pa.x Pc.z Pp.y Pb.x Pc.z Pp.y PA.y Pb.x Pp.z + Pa.x PB.y Pp.z
+ PA.y Pc.x Pp.z PB.y Pc.x Pp.z Pa.x Pc.y Pp.z + Pb.x Pc.y Pp.z.
Constructing the cubic equation requires 320 times multiplications and 156
subtractions or additions. In these operations, the numerical errors can be
accumulated. This error is inevitable in the conventional method. The thin object

like cloth suffers from it severely. The collision detection results might be wrong.
Once the collision detection result is incorrect, the cloth remains tangled because the
next collision detection considered the penetrated part is the collision free status.
Our approach takes the other way for collision detection query to avoid this time
consuming and erratic query.

3. Collision Handling
Handling collisions robustly is arduous in deformable object simulations. Since
the deformable objects require more than thousands of particles to achieve visually
realistic simulation. Highly deformable objects like cloth can generate thousands
of collisions in a time step. Resolving all the collisions is expensive and
painstaking in computation.
3.1 Collision Detection
3.1.1 Approximation Using Spherical Implicit Surface
Our method [36] is based on spherical implicit surface. The detailed approximation
of the collision is described. The spherical implicit surface is computed in adaptive
ways, and the user can control the level of detail according to the collision situation
and view conditions. Triangle and Node Collision Test
First we calculate the proper radius of the sphere d to generate the spherical implicit
surface of the triangle for collision detection, d is 2/3 of the distance between the
triangles center of mass (C4) to one of its nodes. The distance fields (spheres S1-S3)
are created from each triangles node using radius d and S4 is created from the

triangles center of mass. In Figure 5.1 (level 0) four spheres (S1-S4) represent the
spherical implicit surface of the triangle. The spherical implicit surface of the
triangle is the sum of the distance field from the three nodes of the triangle and the
triangles center of the mass. Node P is the one of three nodes in the other triangle in
the exact collision detection. After performing the distance calculations from the
center of each sphere to the node P, we can conclude whether node P is inside of the
spherical implicit surface or not. Then we can check the distance between the
closest location of the triangle and node P. If node P is in the one of spheres SI, S2,
S3, and S4, the approximated distance between the triangle and the node is the
distance from node P to one of the closest sphere centers. The collision normal for
collision resolution is the vector from the selected center of the sphere to the node P.
But if node P is in the two spheres, the approximated distance between triangle and
node P is the distance between the mid point of the center of the two involved
spheres and node P. If node P is in the three spheres, the approximation can be done
from the three involved spheres center. This collision result can be used to decide
the collision resolution direction. The key idea of our method is using the result of
the quick distance check to determine the collision resolution information (direction
and distance). If more accuracy for the exact collision location and distance is
required and the error tolerance (floating distance between triangles) is set below the

size of the radius of the spherical implicit surface, we can perform the same
algorithm recursively using the subdivided triangles.
Level 0
Level 1
Level 2
Figure 3.1 Level 0 collision detection in triangle Cl, C2, and C3 and with the node P.
Nl, N2, and N3 are the node positions of the triangle. Level 1 and Level 2 illustrates
the detailed levels. Edge and Edge Collision Test
After checking triangle and point collision, the possibly missed collision might be
the edge and edge case which the points of the edge are outside of the implicit
surface. To check these collisions, the distance between two mid points of the edges
is checked. If they are overlapped, the distance between two mid points of the edge
is tested whether it is within the threshold. Figure 3.2 illustrates that the collision
detection can be performed in different levels. To select the collision check points
(C3 and C4) at the next level, we use a binary search method. For example, in

Figure 5.2 (level 0) we select the minimum distance between four nodes (AC, AD,
BC, and BD). In this case distance between BC is the minimum distance, thus the
next level sets are edge Cl and B and edge C2 and C. We can pre-store the distance
data in the previous triangle and node collision test and can reduce the computation
Figure 3.2 Level 0 collision detection between two edges. Cl and C2 are the mid
points of the edges. If the distance between Cl and C2 is less than the threshold, the
collision is determined.
3.2 Adaptive Re-Sampling
Typically we found that the level 0 collision result would be sufficiently accurate
enough for the robust collision handling. If we use the relatively finer mesh, we do
not need any further collision detection query. But when the triangle is too coarse,
we need to adaptively search down to the next level. The collision detection
algorithm on level 0 can be applied recursively until we get a satisfying result. No
extra storage is required for the substructure to achieve this. Since we have already
four distance calculations at the upper level, we need three more distance
Level 0
Level 1
Level 2

calculations for the next lower level collision detection. The beauty of our method is
that we can have enough collision resolution information whenever we stop
collision detection processing. The decision of further searching can be done using
human collision perception, which OSullivan [28] researched with psychophysical
experiment. We changed the threshold according to the distance between the camera
and the object to reduce the computational burden. If the user wants to achieve more
accuracy, it can be done by simply expanding the tree structure but the cost is not
substantial since the involved triangles will be subdivided and each operation only
includes a quick distance comparison.
3.3 Collision Resolution
Figure 3.3 Collision response. The red arrow in (A) is the collision normal in the
point and triangle collision detection result from Figure 3.1. The red arrow in (B) is
the collision normal in the edge and edge collision detection result from Figure 3.2

Figure 3.3 illustrates the collision results in level 0 when we consider that the
distance is less than the threshold. We can use the distance vector as the collision
normal to apply the collision resolution method. From Figure 3.1, the node P was
detected as collided with sphere 4. Figure 3.3 shows the normal of the collisions in
triangle-point case and edge and edge case. Using these collision reports, geometry
method and penalty force method are used for the collision resolution. Our method
utilizes both methods to handle the collisions depending on the collision situation.
Penalty force method reduces the number of collisions and geometry method
guarantees the collision-free states. For the penalty force method, we sum up the
mass of the object (edge, node or triangle) and calculate the repulsion force for two
objects and the forces are distributed to each node according to their masses [5], For
the geometry method, we modified the velocity to the collision response velocity
and moved the position to the legal location.

4. Cloth Simulation with Our Method
Our method is applicable for any objects if only the objects consist of a set of points
and a set of faces. Fortunately most models for animation and simulation are
represented by triangulated meshes. Our method can be utilized for them well. But
collision resolution scheme is not generalized. Collision resolution scheme can
determine the dynamic behavior of the objects. We need to be careful to select a
proper method for each model. To verify our method we applied it for cloth
4.1 Cloth Simulation
Before the physically based simulation technique was not introduced to the
computer graphics, cloth was modeled through the geometric expressions such as
Bezier curves, B-splines, non-uniform rational B-splines (NURBS), and Polygons.
This cloth representation uses control points to express the curve or surface. The
shape of cloth can be generated by moving these control points. This level of
representation was painstaking to achieve realistic cloth animations because even a
little change of curve may require laborious work to modify the curve. The detailed
dynamic behavior of the cloth is difficult for the trained animators to catch. The
physically based simulation technique enabled animators to generate realistic cloth

without tedious modifications of the detail of the cloth.
Over the past decades several cloth models have been proposed. There are four
major physically based cloth modeling schemes. The continuum mechanics of
bending plates and shells were employed [1]. The limitations of this model are a
complex mechanical mechanism and the poor modeling in buckling and folding.
Thus, this model cannot represent the dynamic behavior of cloth in busy pattern of
Breen et al [19] employed the particle systems for cloth modeling. They derived the
cloth models energy equations from empirical mechanical data produced by the
Kawabata Evaluation System. The energy function consists of five components
(repel component, stretch component, bend component, trellis component, and
gravity component). The repel component is keeping the minimum distance. The
stretch component is the opposite components. They calculate the energy function
for each node. They introduced particle system for simulating the behavior of the
cloth. But this method has not been attractive to animators because it requires too
many particles to model a simple patch of cloth and most animators generate the
models using triangle mesh because it is convenient for users to display and
manipulate, but this method requires a detailed regular mesh.
Provot [13] added spring dynamics to the particle systems. Since then most
researchers and animators take advantage of the simplicity of the particle system

model and adapt springs between the particles to catch the interaction of particles on
the surface [8], [9], [10], [12], [13], Mass-spring system has been widely adapted to
cloth simulation. Several types of modeling technique were introduced. Though
mass-spring system is simple and easy to implement, there are several limitations.
One of the significant weaknesses of this modeling is instability. But the simulation
technique for mass-spring modeling has been improved with employing the higher
order ordinary differential equation solvers [6], [12], [18],
In the simulation, there are many interactions between other objects and cloth itself.
Those interactions are generated by the collision and contact. When cloth is put on a
virtual human, there are numerous interactions between human skin and the cloth.
When the cloth is folding, it generates a lot of collisions. Without handling the
collisions robustly, it is impossible to achieve realistic cloth simulations. Thus, the
collision detection and resolution was one of the important techniques in cloth
simulation. Since cloth is deformable and very thin, it is difficult to track all the
collisions and detect collisions between cloth patch and other objects and between
cloth patches (self-collision).
4.2 Cloth Modeling
4.2.1 Mass-Spring System
In this chapter we describe the basic mass-spring system for cloth modeling. It has

been widely adapted to model deformable objects in computer graphics.
Figure 4.1 Simple mass-spring system with mass nodes and springs. The nodes are
connected with springs.
Figure 4.1 illuminates the structure of a simple mass-spring system. The mass points
are connected by different types of springs to propagate the energy in the mass-
spring system. The interaction between the mass points is generated by the springs.
The governing Lagranges equation for the mass-spring model is
>n,x, + Y,-x, + kix, =fi+gi (4-1)
where xt, and xi are the position, the velocity and the acceleration vectors of
node i, respectively. mj, yi, and k{ are scalar values to represent the nodal mass,
the damping and stiffness coefficient at node /. gi is the spring force vector to be

applied on node i through the springs connecting node i, and is the external
force vector on node i. To calculate spring force g(., the spring length at the resting
stage r is pre-computed from the initial positions of the nodes that define an
objects original shape. The spring forces between a pair of nodes at position x,
and x2 with velocity v, and v2 are
where g\ and gi are the spring forces on node 1 and node 2, respectively, k is a
spring constant, and kd is a damping constant. Av = x, -x2 is the actual distance
between the two nodes, and Av = v, -v2 is the difference between the two nodes
velocities, r is the rest length to be pre-computed based on the initial positions of
nodes. ks, kd and r are scalar values and Ax and Av are vector components.
The operator represents an inner product of two vectors. In Equation (4.2), the
spring force magnitude affected by the spring constant is proportional to the
difference between the actual length and the rest length of the spring, while the
damping force magnitude related to the damping constant is proportional to the
nodes speed of approach.
In order to select a pertinent ODE solver to estimate next status of simulation,
g 2 = ~g I

several ODE solvers are comparatively analyzed from the perspective of numerical
stability and efficiency. In case of a large time step and a stiff object, implicit
methods are unconditionally more robust and more efficient than explicit methods.
However, implicit methods may be inefficient when a small step size is applied
because inversion of a large sparse matrix is required in each time step. In contrast,
explicit methods are only conditionally stable, and therefore tend to converge more
slowly than implicit methods. The explicit Euler or the fourth order Runge-Kutta
method are good general candidates for numerical solving of differential equations.
The following equations are simple Euler method to calculate next status of system:
q(t + At) = q(t) + AtM~lF (4.3)
q(t + At) = q(t) +Atq(t + At) (4.4)
here q and q are the position and the velocity vector respectively. M~' is
inverse mass matrix and F is a force vector. Equation (4.3) computes next status
of velocities for each node and Equation (4.4) estimates next status of position for
every node. This model is a simple physical model, easy to construct, and can be
quickly animated.
4.2.2 Spring Connectivity
Provot [13] proposed the different cloth model using particles and springs to
represent the rigidity of the cloth. They added the springs between cross nodes.

These springs regulate the mass points. Choi and Ko [18] modified Provots particle
and spring cloth model introducing the non-linear spring function measuring real
fabrics. This model gives more dynamic movement of the cloth. We have
implemented cloth simulation system using a mass-spring system similar to the
model used in Choi and Ko [18]. Because of distinct material properties of the cloth
which are easy to bend but hard to stretch, the cloth model is constructed by a mesh
of nodal masses and three types of springs in Figure 4.2.
Figure 4.2 Three types of springs for cloth simulation. This illustrates the
connectivity of the springs between neighbor nodes.
Bending springs provide the resistance for cloth folding and they are connected
between every other mass. Structure springs: provide structural basis of cloth and
they connect the masses in a rectangular shape. Sheering springs: provide the
resistance for cloth sheering and they connect diagonal masses.

To represent responsive and realistic behavior of cloth, we used two types of energy
functions by Choi and Ko [18]. For type 1 interaction, we used structure and
sheering springs for a simple linear spring model. The energy function for node i
and j is
E = \
\xu\ (4.5)
here xtJ = x. -x., ks is a spring constant, and r is the rest length between node i and
j. The acting force on node i due to the deformation between node i and j is

i: \xa\-r
\xij\ (4.6)
The type 2 interaction gives the post-buckling response generated by compressive
and bending forces. They anticipate the shape of the fabric after bucking and define
the deformation energy from the deformed shape. The energy function for type 2
interaction is
E =
where kb is the flexural rigidity and k is the curvature of bending. Because the
arc lenght is same with initial rest length of r the curvature k can be expressed by

k = sine
v /
where sinc(x) =
The force vector can be computed by
When the compression forces are applied to cloth, the cloth reamins straigth until
the load reaches certain treshold. However, real phicial process for buckling
includes physical instability for modeling because compression causes shortening
until certain treshold then causes bending, they bypassed shortening and imediately
reached to bending when the compression force is over treshold.
4.2.3 Preventing Extreme Elongation
Current modeling for cloth patches, which most researchers are using, is based on
the mass-spring model. It represents the behaviors of cloth in most cases. But it has
a limitation to model the rigidity of cloth. The linear springs are imaginary and it
could be stretched without limits. Thus cloth could look like rubber. Figure 4.3
shows the extremely elongated cloth patch. The two comers of the cloth patch are
fixed. After 100 iterations, the springs connected to the fixed comers are stretched

more than 2 times. To prevent this, Provot [13] introduced a method to limit the rate
of elongation with reducing the length of the springs in each time step. They simply
moved the position of the nodes which are involved with the elongated springs in
arbitrary order. Thus, this method has an ordering problem and generates the
discontinuity of simulation due to changing the positions of nodes abruptly. Besides
they have to iterate their method until the all springs are in the admissible distances.
It is computationally expensive and may not find the solution. Bridson et al. [12]
attempted to solve this problem with limiting the strain rate of springs. They
modified the velocity to enforce the strain rate of the spring. But this is not
bulletproof in extreme cases. They might not converge to a solution in case a ball
collides in the middle of the cloth patch when the four comers of cloth are fixed.
Baraff [23] introduced efficient constraint using Lagrange multiplier. The constraint
method was employed to simulate rigid body [24], [25], In order to solve this
problem, we applied the implicit constraint method using Lagrange multiplier to
prevent the extreme elongation of the spring without discontinuity because
constraint force preserves the dynamic behavior of the model.

Figure 4.3 Extremely elongated cloth patch. The two top comers are fixed and
gravity is applied to the rest of cloth.
We adaptively applied constraint forces to the nodes involved with extremely
elongated springs using implicit constraint method [20]. As constraint method,
Baumgarte method [22] has been widely used because of its simplicity. The
limitation of this method is that it requires parameter tweaking for stabilization.
Cline and Pai [27] proposed a post-stabilization method that reduces the dynamic
behavior of the system. But implicit constraint method preserves the dynamic
behavior and reduces the numerical drifts efficiently. This implicit constraint

method is applied various applications and preserves the dynamic behavior of the
system [35]. We adapted this method to enforce the strain rate of springs.
When the spring is elongated more than 10 percentage of the original length, we
activated the constraint force using the distance constraint. When the spring began
shrinking, we deactivated the constraints. Our method guarantees the exact distance
of the spring in each time step. Unlike the previous proposed methods, our method
does not require iterations to find the solution. We find the constrain forces using
improved implicit method [20] which to keep the exact distance of the spring at
each time. Our method need to solve linear system one time in each time step, but
the size of the system is the minimum because each time we activate and deactivate
the constraints. This method keeps the distance of the spring at the strain rate of
10% accurately, so our cloth model has no artifacts like Figure 4.3.

4.3 Experiment Simulations
For all the simulations, we adapted a fast Aligned axis bounding box (AABB)
hierarchy. AABB is proper for deformable object simulation because deformable
objects require updating AABB each time step. AABB is stored in the quad-tree
which is the most efficient for self-collision check. Our AABB is built in a bottom-
up manner to minimize the depth of the tree, and the collision detection for self-
collision starts at the third level to reduce the traverse time of the tree structure
because in most of cases the collision detection the search has to come down to the
lower level than 3 to determine the collision status. On top of this we adapted the
surface curvature of the deformable object. After the overlapping tests between
AABB, the pairs of triangles are reported for exact collision detection query. We
applied our method and the conventional method to compare the computational time.
We tested the collision detection and response scheme in three cases. We used
Pentium 4 processor 2.4 GHz CPU computer and it takes about 0.5 second to
simulate one frame. The program generates the Pov-ray scene description files and
the snapshots are produced by Pov-ray, the ray-tracer application [37],
4.3.1 Cloth Piling Up Simulation
The cloth model contains 3000 (30 by 100) particles. The total number of iteration

for this simulation is 1230. The cloth patch is dropped on the floor vertically and the
cloth patch is piling up. The cloth patch generates many folds and wrinkles when it
piles up. This simulation illustrates the robust collision resolution of our method
with maintaining the thickness of the cloth model. Figure 4.4 is the comparison
chart between our method and the conventional method. At the beginning of the
simulation, the cloth patch is collision free and a few collision detection queries are
performed, but after the cloth is folded, numerous collision approximations are
performed. The computational time of our method stays under 1 second throughout
the simulation. But the conventional method is over 0.5 second always. Figure 4.5 is
the snapshots of the simulation. It illustrates the robustness of our method and the
dynamic behavior of the cloth patch. After 800 iterations, the computation time of
our method is growing faster than the conventional method due to the
approximation of our method is less accurate than the conventional method. Our
method requires more iterations to guarantee collision free at the time step.

Computational Time(second)
1 78 155 232 309 386 463 540 617 694 771 848 925 1002 1079 1156 1233
Number of Iterations
-Our method NConventional method
Figure 4.4 The performance comparison in the piling cloth simulation between our
method and the conventional method.

Figure 4.5 The snapshots of the piling up simulation. The cloth patch is folded
naturally without penetrations.


4.3.2 Cloth Falling on the Sphere Simulation
Figure 4.7 are the snapshots of the falling cloth patch simulation on the sphere.
This model has 1600 (40 by 40) particles. The total number of iterations for this
simulation is 810. Initially the cloth patch is flat over the sphere, and begins falling
at the beginning of the simulation and the cloth patch is dropped on the floor with
busy pattern of folds at the end of the simulation. The computation time of our
method is less than 0.05 second. But the conventional method is over 0.15. Our
method is 300 times faster than the conventional method. There are various folding
and wrinkles when the cloth is on the floor. Our method resolves the collisions
robustly. This simulation has less exact collision detection queries than the pile-up
simulation, so the total computation time is less overall. Our method performs at a
negligible time.
Figure 4.6 The performance comparison in the falling cloth on the sphere simulation.

Figure 4.7 Cloth patch remains without tangling with a busy pattern of folding.

Figure 4.7 (Cont)

4.3.3 Sphere Colliding Simulation
The cloth is hanged at the two comers, and the initial position of the cloth patch is
flat. As the simulation begins, the cloth patch falls down, and the sphere approaches
to the cloth patch. At the middle of the simulation the sphere begins colliding with
the cloth patch at the middle of the cloth. Due to the large velocity at the collision
time, the cloth patch generates big forces, and the cloth patch can go through to the
other side at a given time step.
Figure 4.8 The performance comparison in the sphere collision cloth simulation.
But our method handles the collision correctly. Figure 4.9 illustrates the robust
collision handling of our method. The performance difference between two collision

methods in the sphere collision cloth simulation in Figure 4.8 is presented. Our
method maintains the constant computing time. Since AABB reduces the
computation time at the beginning of the simulation due to the low curvature of the
surface, the computation time for the collision detection for the model is the
minimum. After the cloth model began to fold, the computation time grows because
the collision detection for exact collision method is performed more. Throughout the
simulation, sphere collision method remains the constant, but the conventional
method grows two times or three times.

Figure 4.9 Sphere colliding simulation. The sphere collides in the middle of the
cloth with infinite velocity.

Figure 4.9 (Cont)

Figure 4.9 (Cont)

5. Conclusion
We propose a fast and robust collision detection and resolution for deformable
objects. We adopted human perception to determine the necessary accuracy of
collision detection. Our experimental results demonstrate that the massive collisions
between deformable objects can be effectively handled. Our method substantially
reduces the complexity of the collision management and alleviates the numerical
error in calculation. Due to the simplicity of our method, it is possible to achieve
even better performance when it employs a GPU based hardware acceleration. For
coarsely meshed objects, the proposed method may have to go down to the
numerous levels of details to achieve the necessary accuracy of a collision, and the
depth of the tree is inversely proportional to the size of a triangle mesh. However,
since deformable models should be meshed reasonably to generate plausible motion,
the levels of detail are limited within a few steps.

[1] D. Terzopoulos and K. Fleischer, Modeling inelastic deformation:
viscoelasticity, plasticity, fracture, in Proceedings of SIGGRAPH 1998, ACM
Press /ACMSIGGRAPH, Computer Graphics Proceeding, 1998, pp. 269-278.
[2] D. Terzopoulos and A. Witkin, Physically based models with rigid and
deformable components, IEEE Computer Graphics and Applications, vol. 8,
pp. 146-154, November 1988.
[3] M. Moore and J. Wilhelms, Collision detection and response for computer
animation, in Proceedings of SIGGRAPH 1998, ACM Press / ACM
SIGGRAPH, Computer Graphics Proceeding, 1998, pp. 289-298.
[4] D. Baraff and A. Witkin, Dynamic simulation of non-penetrating flexible
bodies, in Proceedings of SIGGRAPH 1992, ACM Press /ACM SIGGRAPH,
Computer Graphics Proceeding, 1992, pp. 303-308.
[5] A. Witkin and D. Barraf, Physically based modeling, in Course notes for
SIGGRAPH 03, 2003.
[6] D. Baraff and A. Witkin, Large steps in cloth simulation, in Proceedings of
SIGGRAPH 1998, ACM Press / ACM SIGGRAPH, Computer Graphics
Proceeding, 1998, pp. 1-12.
[7] D. Baraff, M. Kass, and A. Witkin, Untangling cloth, in Proceedings of
SIGGRAPH 2003, ACM Press / ACM SIGGRAPH, Computer Graphics
Proceeding, 2003, pp. 862-870.
[8] P. Volino and N. Magnenat Thalmann, Collision and self-collision detection:
Efficient and robust solutions for highly deformable surfaces, in Computer
Animation and Simulation, Springer-Verlag, 1995, pp. 55-65.

[9] P. Volino and N. Magnenant Thalmann, Efficient self-collision detection on
smoothly discretized surface animations using geometrical shape regularity, in
Proceedings of Eurographics, vol. 13 of Computer Graphics Forum,
Eurographics Association, 1994, pp. 155-166.
[10] P. Volino, M. Courchesne and N. Magnenant Thalmann, Versatile and efficient
techniques for simulating cloth and other deformable objects, in Proceedings
of the 22nd Annual Conference on Computer Graphics and Interactive
Techniques, 1995, pp. 137-144.
[11] P. Volino, M. Courchesne and N. Magnenant Thalmann, Accurate collision
response on polygonal meshes, in Proceedings of the Computer Animation,
2000, pp. 179-188.
[12] R. Bridson, R. Fedkiw, and J. Anderson, Robust treatment of collisions,
contact and friction for cloth animation, in Proceedings of SIGGRAPH 2002,
ACM Press / ACM SIGGRAPH, Computer Graphics Proceeding, 2002, pp.
[13] X. Provot, Deformation constraints in a mass-spring model to describe rigid
cloth behavior, in Proceedings of Graphics Interface, 1995, pp. 147-154.
[14] X. Provot, Collision and self-collision handling in cloth model dedicated to
design garment, in Proceedings of Graphics Interface, 1997, pp. 177-189.
[15] B. Lafleur, N. Magnenat Thalmann, and D. Thalmann, Cloth animation with
self-collision detection, in Proceedings of the Conference on Modeling in
Computer Graphics, 1991, pp. 179-187.
[16] D. Zhang and M. Yuen, Collision detection for clothed human animation, in
Proceedings of the 8th Pacific Graphics Conference on Computer Graphics and
Application (PACIFIC GRAPHICS-00), 2002, pp. 328-337.
[17] M. Lin and S. Gottschalk, Collision detection between geometric models: A
survey, in Proceedings of IMA Conf on Mathematics of Surfaces, 1998, pp.

[18] K. Choi and H. Ko, Stable but responsive cloth, in Proceedings of
SIGGRAPH 2002, ACM Press / ACM SIGGRAPH, Computer Graphics
Proceedings, 2002, pp. 604-611.
[19] D. E. Breen, D. H. House, and M. J. Wozny, Predicting the drape of woven
cloth using interacting particles, in Proceedings of SIGGRAPH 1994, ACM
Press / ACM SIGGRAPH, Computer Graphics Proceedings, 1994, pp. 365-372.
[20] M. Choi, M. Hong, and W. Samuel, Implicit constraint enforcement for stable
and effective control of cloth behavior, in A Technical Report Form University
of Colorado at Denver, Computer Science and Engineering Department TR-02-
01, 2004.
[21] P. M. Hubbard, Approximating polyhedra with spheres for time-critical
collision detection, in ACM Transactions on Graphics, 1996, pp. 179-210.
[22] J. Baumgarte, Stabilization of constraints and integrals of motion in dynamical
systems, in Computer Methods in Applied Mechanics, 1972, pp. 1-16.
[23] D. Baraff, Linear-time dynamics using Lagrange Multipliers, in Proceedings
of SIGGRAPH 1996, ACM Press / ACM SIGGRAPH, Computer Graphics
Proceedings, 1996, pp. 137-146.
[24] R. Barzel and A. H. Barr, A modeling system based on dynamic constraints,
Computer Graphics Proceedings. Annual Conference Series. ACM Press, 1998,
pp. 179-188.
[25] Witkin, M. Gleicher, and W. Welch, Interactive dynamics, in Proceedings of
SIGGRAPH 1990, ACM Press / ACM SIGGRAPH, Computer Graphics
Proceedings. 1990, pp. 11-21.
[26] M. Teschner et al, "Collision detection for deformable objects," in Proceedings
Eurographics State-of-the-Art Report, 2004, pp. 119-139.
[27] M. B. Cline and D. K. Pai. Post-stabilization for rigid body simulation with
contact and constraints, in Proceedings of the IEEE International Conference
on Robotics and Automation, 2003, pp. 3744-3751.

[28] C. OSullivan, A model of collision perception for real-time animation, in
Computer Animation and Simulation 99, 1999, pp. 67-76.
[29] G. Bradshaw and C. OSullivan, Sphere-tree construction using dynamic
medial axis approximation, in ACM SIGGRAPH Symposium on Computer
Animation, 2002, pp. 33-40.
[30] S. Kimmerle, M. Nesme, and F. Faure, Hierarchy accelerated stochastic
collision detection, presented at 9th Vision, Modeling, and Visualization,
Stanford, USA, 2004.
[31] S. Gottschalk, M. C. Lin, and D. Manocha, OBBTree: A hierarchical structure
for rapid interference detection, in Proceedings of SIGGRAPH 1996, ACM
Press / ACM SIGGRAPH, Computer Graphics Proceedings, 1996, pp. 171-180.
[32] J. T. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan,
Efficient collision detection using bounding volume hierarchies of k-DOPs,
in IEEE Transactions on Visualization and Computer Graphics, vol.4 no.l, pp.
21-36, 1998.
[33] I. J. Palmer and R. L. Grimsdale, Collision detection for animation using
sphere-trees, in Computer Graphics Forum, 1995, pp. 105-116.
[34] D. L. James and D. K. Pai, BD-Tree: Output-sensitive collision detection for
reduced deformable models, in Proceedings of SIGGRAPH 2004, ACM Press /
ACM SIGGRAPH, Computer Graphics Proceedings, 2004, pp. 393-398.
[35] M. Hong, M. Choi, S. Jung, and S. Welch, Effective constrained dynamic
simulation using implicit constraint enforcement, in Proceedings of the 2005
IEEE International Conference on Robotics and Animation, 2005, pp. 4531-
[36] S. Jung, M. Hong, and M. Choi, Adaptive collision detection and resolution
scheme using spherical implicit surface, in International Conference on
Computational Science, 2005, pp. 735-742.
[37] Persistence of Vision Raytracer Pty. Ltd, 2005,