Persistent Manifold question

[Erwin Coumans]

When a point exceeds a lateral threshold, instead of chucking it out I do a very short ray check from the object with the greatest velocity at the contact point against the other object, and if that returns a contact point that is close enough I update the point on both objects and leave it.
[...]
Erwin's idea of only chucking out one point per frame is awesome in its simplicity, and may be a better choice. YMMV.

Interesting. Can you do a short ray check faster then closest point calculation? Can you compare the cost and elaborate on the ray testing method?
By the way, it is not my idea: a developer kindly shared his improvements for Bullet collision detection in their game.

Erin's "Varying Friction". [...] Lack of such a demo is suspicious and might be interpreted as if it not works

Dirk, you seem to contradict yourself. In a a recent posting you seem to acknowledge that a sliding box using Bullet persistent manifold works fine:

[...] since I could imagine that due to the sliding some points might fall out of the distance threshold. I doubt that the later is the reason since I would guess you would see the same issues with the other box in this case as well.

Preparing my talk for the GDC Physics Tutorial, creating physics demos for the Sony booth and some deliverables for my book doesn't give me much time to create such demo right now, but I'll add it to the todo list.

This wouldn't be very clever. The elegance of Gino's (or Larsen's) approach is that you get the full manifold by just calling the cheap GetSupport() function instead of running a full GJK. Even worse, when rotating the objects you might get into deep penetrations and need to call the even more expensive penetration solver. You also need to multiply matrices to rotate the objects. No, I would argue that this is not a good solution.

Eric Larsen and Gino van den Bergen both used closest point calculations (in personal communication and in their implementations). You can trivially avoid deep penetration (just don't fallback into EPA), and rotate by a limited amount based on the extremal points, an application of conservative advancement. Just using the supporting vertex method is not sufficient: they are not closest points.

I'll ask Gino to comment on this, but he is probably busy too.

Thanks,
Erwin

[dog]

My ray-check code performs better than my closest point code - this may not be true for other people. Possibly my closest point code is not the world's greatest.

I have a single central templated batched ray-cast function that supports all my collision queries (swept collision, line and capsule tests etc). The ray-cast operates with a conservative advancement scheme. There are a couple of gotchas with guaranteeing a perfect normal if the ray starts off in, or nearly in collision. I don't want to go into them yet, because it is an area of active research and I don't want to sound off on the "right" way to do it until I'm really sure.

In my patch management code I chuck out a point if it strays too far away from its partner in the direction of the surface, and if it exceeds a distance threshold along the surface. Only in the case of moving along the surface do I initiate an update check to see if I can keep the point. Possibly I can eliminate some further narrow-phase collision checks if I have just done this - it hasn't been slow enough for me to look into it though.

[Suslik[PGS]]

I'll ask Gino to comment on this, but he is probably busy too.

I'm looking forward. And, please, ask him to comment upon my favourite "normal distortion" approach - I do love it!

[Erwin Coumans]

I'll ask Gino to comment on this, but he is probably busy too.

I'm looking forward. And, please, ask him to comment upon my favourite "normal distortion" approach - I do love it!

Gino actually discussed two different approaches based on perturbing objects, around the separating normal. Initially he used the simulation (apply impulse) to get the pertubation/new rotation, and perform a new closest point calculation. This is implemented in his Solid library, dynamics demo.

He discussed this approach in a posting on comp.graphics.algorithms. In the same thread, John Nagle discusses the projection onto the separating plane and clipping. Gino's posting on this forum is a combination of both, using the supporting vector.

So his idea posted here:

Taking the closest features of the last-found simplices (sets of support points) for the two objects tested using GJK gives you a rough approximation of the contact manifold but you can do better, since (a) this simplex is usually not the complete manifold and (b) it is not necessarily a face of the boundary.

The following single-shot method for computing the contact manifold does a better job:

Given a contact normal N and a support mapping A, the contact area can be defined as the set of support points

lim conv{S_A(U) : angle between N and U < alpha}
alpha -> 0

Thus, the contact area is the convex hull of the set of support points found by slightly perturbing the contact normal. You can perturb the contact normal by adding a tiny vector orthogonal to the contact normal. These tiny vectors can lie on a circle or can be generated randomly. For instance, you could generate the vectors by hierarchically slicing the unit circle until for some iterations no new support points are found. The actual contact manifold is the intersection (after projection) of the two convex areas.
This method is somewhat cumbersome, so in many cases Erwin's solution of maintaining the last-found contact in a persistent manifold is often sufficient and a lot cheaper.

Finally, when doing convex vs complex mesh, it is better to use the face normals of the mesh rather than the penetration depth vector between the convex and each face in the mesh as contact normal. This is cheaper, since it does not require a penetration depth computation, and behaves better since objects will always slide along the surface of the mesh rather than bounce of the internal edges of the mesh.

I might someday put this stuff in a paper and add some illustration but for the time being this should get you going.

This is not calculating multiple closest points, but a projection and clipping. Either this or multiple calls to closest point are likely more expensive then just adding one point at a time.

I'm curious if it is really worth it in general. It could be combined with Bullet persistent manifold approach, and only used when there are insufficient points (or as a high-quality/LOD setting.). As I mentioned before, I will definately implement the variations, and discuss this with others for my contact generation chapter.

[Suslik[PGS]]

Thanks you very much, Erwin

[Suslik[PGS]]

I'll be on holydays for two weeks, so I'll be offline. But then I hope we'll discuss my solver enhancements and implementation of Gino's CD approach. See you!

[Suslik[PGS]]

I'm proud to introduce you my new demos with Convex-Convex Collision Detection based on approach discussed above. I've finished its implementation just a few minutes ago, so I hadn't enough time to test it properly, but it seems to work really great!

I've made a simple demo in hurry. There are lots of convex pyramids spawned with left mouse button, and 80 of them in one heap seem to work in 80-90fps speed.
Screenshot:

You could test the alghorithm by yourself. Demo is here: http://rghost.ru/files/2101