Transcript Particle-based Collision Detection

Time-dependent Shapes
(I)
Introduction
In
physical simulation collisions occur when two
objects move through space and hit one another
Whenever two objects attempt to inter-penetrate
each other, it is called as a collision. The related
issue is response to collisions once they are detected
A straightforward method of collision detection
involves the solution of a sequence of static
problems one per time step
 ballmovie2.avi
What is a Motion?
Definition of an Object’s
Configuration


The configuration of an object is a specification of
the positions of all the points in this object relative
to a fixed coordinate system
Usually it is expressed as a “vector”
of
position
and
qn
orientation parameters
q=(q1,…,qn)
q1
q2
q3
Rigid Object Example
workspace
robot
reference direction
q
y
reference point
x
Object’s configuration is: q = (x,y,q)
In a 3-D workspace q would be of the form (x,y,z,a,b,g)
Disc Robot in 2-D Workspace
C-Obstacle for Articulated Robot
Collision detection
Illustration of a
dependent shape
time-
Collision detection for particles
Consideration
of
a problem of nonoverlapping
arrangements of D-dimensional spheres, D = 1,2,3, confined
to a “rectangular” region d of size L1xL2x...xLD leads to
search of an interaction time of particles
Let the center positions of the N spheres in d be denoted by
the set of vectors r1...rN.
For two spheres with the diameters a1 and a2, interaction
time t is the least positive real solution of the equation
At2 + 2Bt +C =0,

which is derived from |r +vt|2 = (a0t)2, where a0 = a1 + a2
Collision detection for polygons
A correct
test must consider edges and triangles
However, in many cases merely testing points
versus triangles produces acceptable results
Polygon-polygon collision detection is performed
by testing for the penetration of each vertex point of
one polygon through the plane of the other and by
checking that no two edges intersect
Collision detection for polygons
Figure illustrates
intersection

This
path
point
and
triangle
technique is used to detect collision between
flexible surfaces. Two cases are considered
depending on whether the surface polygon is fixed or
moving
Collision detection for polygons
When
the surface polygon is fixed [a triangle with
vertices (P0,P1,P2)], the parametric vector equation is
given by
P + (P’ - P)t = P0 + (P1 - P0)u + (P2 - P0)v,
where P and P’ are the beginning and ending
position of the point, u and v are the parametric
variables for the plane defined by the triangle and t is
a time variable for the simulation step
By solving this system for t, u,v one determines
whether the point has intersected the triangle during
the time step by checking the conditions 0  t  1, u
 0, and u + v  1
Collision detection for polygons
When
the surface polygon is moving, the following
parametric vector equation is setup:
P + V t = P0 + V0t +((P1 - P0) + (V1 - V0)t)u + ((P2 - P0) +
(V2 - V0)t)v,
where P is the point with velocity V per time step, V0, V1, V2
are the respective velocities of the points P0, P1, P2
If we eliminate u and v from the three component equations,
we get a fifth order polynomial in t, which can be solved
numerically. Each value of t thus arrived at is used to get
values for u and v by back substitution, and then the standard
0  t  1, u  0, and u + v  1 conditions are used to
determine whether a collision has occurred.
Collision detection for convex
polyhedra
The
two polyhedra are assumed to be convex ones; concave
polyhedra can be decomposed into collections of convex ones
The method for detecting collisions is based on the CyrusBeck clipping algorithm
The
two-dimensional Cyrus-beck algorithm tells whether a
point is inside a convex polygon. It takes the dot product of
each side’s outward normal vector (n) with a vector from
some point (v) on the side to the point in question (p)
Collision detection for time
dependent shapes



Most algorithms described in the literature deal with
rigid bodies and are based on
some kind of
hierarchical representations. The alternative approach is
based on the idea of “sensor particles”
Collision detection based on a particles paradigm
between complex geometric objects represented by
polygonal models and undergoing rigid motions is
discussed
Quite interesting that almost the same approach can be
used in geometry modeling – mesh generation and
inhancement
Examples of particles distribution




(a) The model of Rocker Arm
with randomly distributed
particles
(b) Final distribution of
particles on the model of
Rocker Arm
(c) The Dragon model with
randomly distributed particles
(d) Final distribution of
particles on the Dragon model
Sensor particles


Sensor particles are interacting particles
distributed on a surface
Two types of particles that interact in a special
way are used for determining the minimum
distance between two models
Assumptions




Each model has a surface that is for the most part plain
Face's adjacency information is available, i.e., there is a
list of neighbor faces for each model point, or it can
easily be created
Adjacency information does not change during
deformation, which means that bodies do not change
their topology
The model remains plain for the most part and the
number of convex parts does not increase greatly
during deformation
Particle Interaction



Radial
attractive
and
repulsive forces act on
particles
Unlike the law for electric
charges, the laws for
repulsive and attractive forces
can be different
Reff is the effective radius of
attraction
Particle Interaction (cont)



A)
Initial
position
B) After one
simulation step
C) After one
interaction step
Particles Movement


In the simplest case, particles can be located only at
vertices. In this case, we can easily calculate the
potential of forces in every neighboring vertex and
move a particle to the vertex where the potential has
the minimum value
This technique can be generalized for cases when the
particle can be located on edges and faces
Collision Query


At every collision query we turn on an interaction
between particles and wait for the particle system to
relax
Two numbers, Nmax and Nmin, are used to control a
particle system to reach almost relaxed state. Nmax is
the maximum total number of interaction steps and
Nmin is the minimum number of moving particles.
Therefore, we wait until either the number of particles
moved in interaction step is less then Nmin or the
number of interaction steps becomes equal to Nmax
Collision Query (cont)

The values of Nmin and Nmax depend on the model's
geometry and number of particles n. Nmax should be
approximately equal to the number of vertices between
particles placed on the model. Experiments show that
about 10% of particles, in average, are placed near
equilibrium position. By this means Nmin should be
about 10 times smaller then number of particles n
Collision Query (cont)


The complexity of performing collision query is O(n2).
Since the number of particles n is essentially smaller
than the number of polygons, this complexity allows us
to perform fast collision queries even for models with
a large number of polygons
Performance can also be noticeably improved, by using
caching on the initial steps. If positional relationship
changes slowly, the influence of distant particles
remains almost constant. Thus we can efficiently cache
this influence
Results


Illustration of particle distribution.
Benchmarks. Collision detection
between two polygonal models of
letters "W", defined by 11920
polygons, with 5 particles on each
model. The average time needed to
perform a collision detection query
on active interval (queries nos. 9501984) was 12.67 ms., and the
maximum time was 47 ms.; average
time during the "warming" steps
(queries nos. 1-49) was 12.06 ms.,
maximum time was 47 ms. also
Results (cont)


Illustration
of
collision
detection
between two models
undergoing
deformations
collision_and_csrbf1.
mpg
Motion of Rigid Bodies Under
External Forces and Torques

•
•
•
The general motion of a rigid body can be
decomposed
into a linear motion of a point mass equal
to that of the body located at the center of
mass of the body under an external force
and
a rotational motion about the center of
mass under an external torque.
scrunchies_2160_comp.avi
Motion of Rigid Bodies Under
External Forces and Torques
The linear motion under a force F can be
calculated by solving the set of coupled
differential equations
V = F/m,
X = V,
where m is the mass of the object, X is the position
vector, and V is the linear velocity

Motion of Rigid Bodies Under
External Forces and Torques

Euler Equations

If we choose principal axes as the body fixed axes we get
a set of simplified coupled first order differential
equations for the angular velocity W, known as the Euler
equations:
Ix Wx +(Iz -Iy)WzWy = Nx
Iy Wy +(Ix -Iz)WxWz = Ny
Iz Wz +(Iy -Ix)WyWx = Nz
The x,y,z are the directions of the principal axes, I is the
moment of inertia tensor of the body. It is important to
realize that for any arbitrary shaped objects, one can find
principal axes and the principal moments of inertia.

Motion of Rigid Bodies Under
External Forces and Torques


Euler Equations
These along with
Tx = Wx
Ty = Wy
Tz = Wz
where Ts are the orientations in the principal
axes coordinate, form a set which can be solved
by a numerical technique such as Rung-Kutta
method.
Motion of Rigid Bodies Under
External Forces and Torques




Impact Dynamics
When two bodies collide and the
contact area of one of the bodies is
locally planar, one can define the
normal N to the tangent surface
Calculate the linear momentum p =
mv
And the torque  = rF, where F is
the force acting on the centre of mass
Penalty-based Multibody Animation



In penalty-based multibody animation, a
spring-damper system is used for penalizing
penetrations.
A spring-damper system behaves like a
harmonic oscilator in classical mechanics.
Spring-damper models are even found in
biomechanical muscle models.
Penalty-based Multibody Animation

•
•
The basics
The motion of a single rigid body is described
in the Newton-Euler equations.
The center of mass is given by r, the
orientation is given by the quaternion q and the
linear and angular velocities are given by v and

•
One needs to find the values of the force F
and torque  at a given instant in time in order
to perform the numerical integration.
Penalty-based Multibody Animation

•
•
•
The basics
In order to compute, the
contact forces springs are
inserted at all penetrations
as shown in Figure
The springs will try to
remove the penetrations
The springs penalize
penetrations
Penalty-based Multibody Animation

•
•
•
•
The basics
The contact force from each point of contact is
thus computed as a spring force.
Call the exernal contributions fext and ext and
the i’th spring force fspring and spring .
Now the total force an torque are computed as
In case of gravity being the only external force,
we have fext = mg, ext = 0.
Penalty-based Multibody Animation
The basics
 The simulation loop of the penalty method can
be summarized as
• Detect contact points
• Compute and accumulate spring forces
• Integrate equations of motion forward in time
 There
are, however, several difficulties
associated with it

Penalty-based Multibody Animation

•
The basics
First of all it is not trivial to compute
satisfactory contact normals or penetrating
depths (lack of global knowledje).
Penalty-based Multibody Animation

•
•
The basics
Some contact points like
the
face-face
case
appearing in a box stack is
difficult to handle.
To alleviate this problem,
researches have tried to
sample the entire contact
region with contact points.
Penalty-based Multibody Animation

Modeling Friction
•
Friction is very imporatnt to seem physically
plausible fo r a human observer.
It seems reasonable to use a spring-damper system
for friction force.
At first point of contact, an anchor point, a, is used.
The friction is determined by the spring force
stemming from the zero-length spring with spring
coefficient k between the anchor point and the
current position p of the contact point.
Ffriction = k(a – p).
•
•
•
Penalty-based Multibody Animation

Modeling Friction
•
The general idea is illustrated in Figure
During the simulation we keep an eye on
whether the following condition holds
Ffriction     Fnormal.
Here  is the coefficient of friction.
Fnormal is the normal force.
If the condition is fulfilled we have static
friction and we do nothing.
On the other hand we have dynamic
friction.
•
•
•
•