Collision points with SOLID
Hilaire VERSCHUERE
I'm using SOLID for collision detection in a physic engine. At a collision,
SOLID give me only one collision point between two mesh.
Does anyone know a way to obtain several collision points if we have a face
to face collision ?
Hilaire.
Mikkel Gjøl
You should probably concretisize this question a bit - not all physics
engines act the exact same. :)
Best regards,
\\Mikkel Gjoel
Hilaire VERSCHUERE
I want to implemant resting contact between Rigid Bodies as Baraff explained
in one of his documents for a physic engine.
I'm using SOLID to detect collisions between Rigid Bodies, but SOLID give me
only one collision point betwen two mesh. If my rigid body is a box falling
on a plan, at the collision, I've got to act on the four vertex of the box
in contact with the plan. SOLID give me only the first collision point he
met, usually one of the four vertex and it is not sufficient to put reaction
on the box.
I could use an other collision detection library but SOLID has the advantage
to give me the normal of collision and a real collision point between Rigid
Body and not the faces concerned by the collision as other library do.
So if someone has understood my problem ( i hope it is clear now ) and has a
solution to help me.
Hilaire.
John Nagle
> OK I better explain my problem.
>
> I want to implemant resting contact between Rigid Bodies as Baraff explained
> in one of his documents for a physic engine.
> I'm using SOLID to detect collisions between Rigid Bodies, but SOLID give me
> only one collision point betwen two mesh. If my rigid body is a box falling
> on a plan, at the collision, I've got to act on the four vertex of the box
> in contact with the plan. SOLID give me only the first collision point he
> met, usually one of the four vertex and it is not sufficient to put reaction
> on the box.
> I could use an other collision detection library but SOLID has the advantage
> to give me the normal of collision and a real collision point between Rigid
> Body and not the faces concerned by the collision as other library do.
What SOLID is giving you are the two closest points involved
in the collision. What you want is the "contact polygon".
For two nearby, non-intersecting convex polyhedra, here's
the algorithm.
1. First, get from GJK (inside SOLID) the final simplex from
the GJK algorithm. This defines the closest set of features
for the two nearby bodies. Each body will have one, two,
or three points in the simplex. A body with one point
indicates the closest point is a vertex. A body with three
points indicates the closest point is in the interior of
a face. A body with two points indicates either that the
contact is along an edge or on a diagonal of a face.
2. With this data extracted, for each face, find the
"most parallel face" for each object. This is the
face most perpendicular to the line through the
closest points reported by GJK. If the GJK simplex
defined a face, that's the face. If it defined a
vertex, pick the most parallel face of those meeting
at that vertex. If the simplex defined an edge, pick
the most parallel face that includes that edge. The
output of this step is two faces, one on each body.
3. Project both faces from the previous step onto the
plane which goes through the midpoint of the line segment
between the closest points, and is perpendicular to
that line. This yields two convex polygons in a plane.
4. Compute the intersection of those two convex polygons.
This is the contact polygon.
This is all straightforward geometry and bookkeeping. Check
those GJK simplicies, though; if you get a simplex that has
points from more than one face, you've found a problem
with GJK (roundoff errors can occur) or the original geometry
wasn't convex. The input geometry should not have coplanar
faces. So don't tesselate your convex hulls. When you
have a cube on a bigger cube, you want a square contact
polygon, not a triangle.
John Nagle
Animats
Giorgio Rossi
"John Nagle" <na...@animats.com> wrote in message
news:3C4089B...@animats.com...
Gino van den Bergen
found that the smart response feature in SOLID 2.0 (closest points of a
frame prior to the collision), wasn't a very useful way of extracting the
contact information. In order for this method to work, you have to make sure
that all collisions are resolved in each frame before proceeding to the next
frame. It is almost impossible to meet this constraint in a real-life
application. As a replacement for this feature I started working on a
penetration depth algorithm
http://www.win.tue.nl/~gino/solid/gdc2001depth.pdf, which can be used to
extract contact information for colliding objects.
The approach I took to finding contact information (which, BTW, I'm still in
the proces of perfecting, but due to other projects hasn't had a lot of
attention lately), is to let the physics simulator iteratively "sense" the
contact plane. The penetration depth algorithm returns a normal and a pair
of contact points. By applying a collision resolving impulse to these
contact points, an performing an integration step, another pair of contact
points for the same pair of objects may be found. By iteratively
backtracking to the collision frame, but keeping the impulses applied to the
found contact points, the simulator "senses" a contact plane. After three
iterations you've defined a contact plane in this way. The benefit of this
approach is that the contact plane doesn't have to be a face of any of the
objects (resting concave objects), and it allows objects to be shoved of the
table in a natural way (objects tilt over and start tumbling) without the
need for doing static analysis to find the balance point for an object on
the edge of te table.
Gino
"Hilaire VERSCHUERE" <h.vers...@cryo-networks.fr> wrote in message
news:3c3f1296$0$24010$4d4e...@read.news.fr.uu.net...
Gino van den Bergen
"Giorgio Rossi" <gro...@mon.net> wrote in message
news:5Wc08.18127$aD.6...@twister2.libero.it...
> Isn't GJK too slow for real-time applications?
>
>
The incremental separating axis (ISA) GJK algorithm is one of the fastest
collision detection methods for general convex objects, and is generally
faster than SWIFT (a Lin-Canny derived feature walking algorithm). For
distance computation between complex convex polyhedra (> 500 vertices)
SWIFT is faster but its use is restricted to convex polyhedra only.
Real-time performance isn't that much dependent on the choice of
primitive-primitive collision test / distance computation algorithm. Since
these proximity queries are performed in the narrowest phase, i.e., after
culling all pairs of non-intersecting objects based on bounding volume
checks, the real performance gains can be achieved in these broader phases
(bounding volume hierarchies, incremental sweep and prune on the set of
axis-aligned bounding boxes).
Gino
Erwin Coumans
Gino's iterative approach of retrieving the contact points is pretty
straighforward and simple to implement, as the Nagle approach seems to be a
bit more work and has more preconditions on the input.
Does Nagle's solution have important benefits ?
Erwin Coumans
John Nagle
Gino is working on interpenetrating bodies, which
is a slightly different problem. I preferred to work with
non-overlapping bodies, which results in a physics system
that always has some airspace between bodies. (I hid
this from the user in Falling Bodies by using a slightly
smaller geometry for collision than for graphics, which
I call a "skin and bone" model. The "bones" never
quite touch, but the "skins" do. It's a good model for
character work.)
The closest-points vector between two nearby
bodies is well-behaved in a way that the penetration
depth vector for overlapping bodies is not. The
penetration depth vector, remember, is the shortest
move that will get the two bodies out of contact.
There are cases where that vector can suddenly change
direction by a large angle in response to an arbitrarily
small move of one of the bodies. The visible effect of
this is that two bodies forced into contact suddenly
move sideways, rather than apart. That's why I
didn't like penetration vectors.
But Gino has taken the next step, which is to
compute the volume intersection of the two bodies
(I think). That's better behaved than the penetration
vector, just as the contact polygon, which I compute,
is better behaved than the closest points vector.
So Gino has an improvement over Steven Cameron's
previous work on penetration vector extensions
to GJK.
Because I was
building a system that used spring/damper collisions
with implicit integrators, it was highly desirable
to avoid all discontinuities in forces as the bodies
move. Implicit integrators behave badly over
discontinuities, and making the system to be
integrated continuous everywhere improved
system behavior.
The original poster is building a Baraff-type
impulse/LCP constraint type system, which has a different
set of problems than a spring/damper system. But
it, too, needs a well-behaved contact area.
I think that Gino's algorithm will produce
a well-behaved contact area, provided that something
is done to prevent the penetration depth from
becoming too deep. "Too deep" needs to be
formalized. At some depth, the penetration direction
to get out of the contact jumps to another face,
which can result in unexpected sideways moves of
bodies in contact. That needs to be avoided by
the levels above collision detection.
All this finicky stuff is the difference between
"sort of works most of the time" and "works robustly".
It's not fun, but you've got to do it before you ship.
(Or license a physics engine and pay someone else
to suffer.)
John Nagle
Animats
Steven Walker
implemented the gjk algorithm and expanding polytope algorithm (as
described by Gino Van De Bergen in his most excellent book).
However my physics system requires the contact polygon rather than just
the deepest points. I've managed to implement a system that works
having pursued the ideas in John's post below, however I'm currently
unhappy with the speed/ efficiency of what I've got and I'm looking for
some clarification on what's below or whether anyone has developed
any new techniques for this in the mean time.
My system runs the GJK algorithm first,
then the expanding polytope algorithm (EPA),
then uses the normal from the expanding polytope to find the most
perpendiclar faces on the convex hulls,
then finds the contact polygon from the intersection of these faces.
(NB: edge/edge cases use the points/ normal directly from EPA)
This is quite costly as while the GJK algorithm is quick the EPA can be
quite costly and feels like overkill just to find the correct two faces
to intersect.
>From my first reading of John's post below my understanding was that he
was using the simplex directly from the GJK algorithm somehow (rather
than EPA), however I've been unable to get anything working with that
as GJK can return any shape in the minkowski sum that contains the
origin - often this does not contain an external face of the polytype?
Has anyone got any ideas/advice or have I done it as efficiently as it
can be done?
Thanks in advance
Steven Walker
John Nagle
> Hi, I am currently implementing a GJK based collision system. I've
> implemented the gjk algorithm and expanding polytope algorithm (as
> described by Gino Van De Bergen in his most excellent book).
> However my physics system requires the contact polygon rather than just
> the deepest points. I've managed to implement a system that works
> having pursued the ideas in John's post below, however I'm currently
> unhappy with the speed/ efficiency of what I've got and I'm looking for
> some clarification on what's below or whether anyone has developed
> any new techniques for this in the mean time.
>
> My system runs the GJK algorithm first,
> then the expanding polytope algorithm (EPA),
> then uses the normal from the expanding polytope to find the most
> perpendiclar faces on the convex hulls,
> then finds the contact polygon from the intersection of these faces.
> (NB: edge/edge cases use the points/ normal directly from EPA)
>
> This is quite costly as while the GJK algorithm is quick the EPA can be
> quite costly and feels like overkill just to find the correct two faces
> to intersect.
>>From my first reading of John's post below my understanding was that he
> was using the simplex directly from the GJK algorithm somehow (rather
> than EPA), however I've been unable to get anything working with that
> as GJK can return any shape in the minkowski sum that contains the
> origin - often this does not contain an external face of the polytype?
When GJK terminates, the final simplex is supposed to contain
the "closest points". There can be as many as six, three on each
polytope, representing closest face to face approach, or as few as two,
representing vertex to vertex contact.
If you have a GJK implementation that terminates
before achieving the entire set of closest points, check the termination
condition. Termination should not occur when there's some point
in the simplex that isn't in the "closest" set. I went round and round
with Steven Cameron at Oxford to get this right back in 1996-1998. See
http://web.comlab.ox.ac.uk/oucl/work/stephen.cameron/distances/
It's non-trivial to get this right. There are roundoff
problems. But Cameron's final implementation should work.
Incidentally, testing a GJK implementation with random
polytopes is of marginal value. The hard cases come up as two
objects settle into contact and become parallel.
John Nagle
Animats