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.
ol...@ludens.elte.hu
Hello!
I had the same problem, but solved and has a class which detects multiple
collision points between two AABB-s, but a bit buggy.
I don't know any library, which gives multiple points with exact normals and
collision points. Maybe this is why I don't know any library:)
I think You should implement, your own method. You should analyze polygon to
polygon, polygon to edge, polygon to vertex and edge to edge collision. Vertex
to vertex is not needed. The problem can be solved very fast, because the
AABB-s can have bounding spheres and inner spheres. If the bounding spheres
don't intersect->nothing to do. If the inner spheres intersect bigger than
epsilon than the two boxes interpenetrate too much, so take smaller time step.
If a vertex from the first box is a bit inside the second box, and is too far
from the other planes of the first box, than it is a collision point.
If two polygon intersects each other and the minimum distance of the edges are
very close each other than you have edge to edge collision. Vertex to edge is
not problem. Did I covered every cases?
Not only the second box should be checked against the first but the first
against the second while avoiding collision point duplications.
The collision points are easy. The normals can be one plane normal or the
average of the normals having the edge bordering planes.
Krisztian Pocza,
who started to implement the whole stuff including Baraff's algorithm but was
too lazy to finish
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
