Re: [Algorithms] Collision fun in cube hell

[Pierre T. <p.t...@wa...>]

> I think the bottleneck for these test would be the contact force
computation
> or integration stepsize (if penalty methods are being used etc). Not the
> collision detection and contact determination.

Certainly. I'm just pleased to see I have a lot of CPU time left to handle
the rest of the story.


> I personally _HATE_ collision detection a lot. There are just too many
> special cases and it is difficult to get really accurate contact
> manifolds(not to mention debugging this)... But I love working on the
other
> physics simulation problems:-)

The main problem of "collision detection for dummies" is that there are a
lot of papers and libs all around, and no global overview to help you out.
You can read about SOLID, I-Collide, V-Clip, whatever, but I've never seen a
paper explicitely telling the differences/common points between all the
available libs and all the published methods. You must read all of them to
start guessing. When I first had a look at CD some months ago now, I just
didn't know where to start - I guess there are some mails in the archive
with my first CD questions. My original goal was to do something like the
Kano demo, but I got stuck in the CD part for quite a long time :) Now, I
see the whole picture and I think I'll move to the next level - I still have
your resting contact code to play with, but so far I've never really
examined it. Was too early.

BTW, don't you have a demo of your physics engine, or something? It must be
quite cool now.

What do you mean by "accurate contact manifolds", exactly? For the moment,
the GJK part gives me the standard 4 contact figures (I know, you have a
fifth one :), and I can use that to derive contact normals, impulses, and
all the things needed to handle colliding contacts. I don't know if it's
"enough". (I leave the resting contacts out of the way, I'd like all the
other parts to be perfect before even thinking about resting contacts and
quadratic programs.)

Unfortunately, and as you know, the GJK algorithm only works for convex
polytopes. So, for non-convex ones I'm stuck with OBB-trees, which can
provide a list of colliding triangles, no more. I just don't know how to
derive a correct distance function for non-convex meshes. So, when two
non-convex meshes collide, I get the pair of colliding triangles, back up
one frame, and computes the distance between those two triangles. Is this
correct? Duno. The real closest-points, as computed by GJK, may lie
somewhere else, anywhere. But since the collision can occur anywhere as
well, it looks like the real distance function is not needed.

Hmm, I also took some shortcuts which may hurt. When I get back in time in
search of the exact collision time for non-convex meshes, I only do the CD
on the two triangles whose collision has originally been detected, in order
to save precious cycles of course. Does someone know if that's a valid move?


Pierre