Persistent Manifold question

[Dirk Gregorius]

Yeah, we discussed both approaches endlessly and both have advantages and disadvantages. Very important is that both work. In the future the expectations on physics will probably raise so it is a good idea to attack these problems. I looked at the link that you posted and it is already two years old and sadly nothing of this is implemented in Bullet. At least as experimental code. It looks simple when talking about it, but it appears hard to tweak in reality. I really would be interested to see how these discussed ideas work in reality.

Regarding your book:
You might make an extra thread for this and we should not only discuss contact point generation, but also solver design. You can make two sticky posts in this thread. I had a nice discussion with Allesandro from Chrono::Engine and we should gather this information as well.

[Suslik[PGS]]

Allowing for general small convex meshes is really nice to have. We are not necessarily talking about quadrics. To implement a general SAT efficiently is not an easy task. Anyway, once you have this it gives you cones and quadrics for free (more or less). It might not appear elegant, but it is simple and robust and works very well in practise.

It would be very inefficient to realise SphereSphere collision using a ConvexConvex collision, don't you think so? Of course, ConvexConvex collision detection is definitely nesessary in physics engine. But primitive collision detection is necessary until it works much(really much) faster than ConvexConvex one.

It is not as bad as you think

Let us consider a box sliding along the plane. After four frames it'll have four contact points. Then, after a few frames they will periodically appear and disappear. Am I right? If so, I think it wouldn't work great with, for example, sliding heap of ragdolls which is quite common case in game physics.

We could discuss this a bit further when I get to that chapter, ok?

Ok, but could you commnt upon "normal distoring" method? I'm going to realise it in a few days and it'll be interesting to now about its cornerstones.

we should not only discuss contact point generation, but also solver design

Yeah, I've got something to tell you about "lazy" solver enhancements - small "tips" which enhance its robustness and efficiency.

I completely forgot - what collision detection approach does Allesandro use in his Chrono::Engine? His CD seems to be very efficient. I've heard that he uses "native"(it means without serious enhancments) bullet CD library. Is that right?

[Suslik[PGS]]

Let me describe as I see "normal distortion" alghorithm(does it have any other name? ) :

1) We find the separating axis. With any alghorithm, it doesn't matter.
2) The we generate four(?) additional axes, which are under some angle(let's say, 30 degrees) to base axis
3) For each body get four support points in this directions
4)(very questionable) Clip two 4-point polygons, using not too complicated heuristics such as:
4.1) removing unnecessary points(degenerate cases, such as four points lying at one line)
4.2) and clipping each edge of one polygon to each edge of another, removing unnesessary points(?)
4.3) projecting two polygons to the separating plane a clipping them as in classic approach fo BoxBox collision test
5) Add all found points to contact manifold with computed in 4.1-4.3 heuristic depths and directions just the same as SAT direction

This method seems to be really general - even for quadratics, am I right?

Please comment on this thoughts

[Erwin Coumans]

Let us consider a box sliding along the plane. After four frames it'll have four contact points. Then, after a few frames they will periodically appear and disappear. Am I right? If so, I think it wouldn't work great with, for example, sliding heap of ragdolls which is quite common case in game physics

Indeed, points will drop but at 60 hertz there are usually no serious noticeable issues. The quality is good enough for sliding boxes and ragdolls. I recommend just trying out Bullet. There is some ragdoll demo in Bullet, and it should be easy to create some sliding boxes. There is plenty of room of improvements in Bullet, and I plan to add some of the things we discussed, for use in the book.

1) We find the separating axis. With any alghorithm, it doesn't matter.
2) The we generate four(?) additional axes, which are under some angle(let's say, 30 degrees) to base axis
[...]

Instead of support points, you can use the usual closest point calculations (SAT or GJK or other) using the rotated objects. We implemented this with several directions, 4 to 8 directions works pretty well in practice. Then those points can be added to the persistent manifold. The btPersistentManifold class as implemented in Bullet already takes care of contact point reduction, and merging duplicate points.

No need for clipping in that case.

I completely forgot - what collision detection approach does Allesandro use in his Chrono::Engine? His CD seems to be very efficient. I've heard that he uses "native"(it means without serious enhancments) bullet CD library. Is that right?

Chrono:Engine is using Bullet collision detection indeed. Bullet allows to register arbitrary collision algorithms. By default the sphere-sphere case is specific (not using generic GJK). The performance comes mainly from a good broadphase, aabb tree and persistent contact management.

Hope this helps,
Erwin

[Suslik[PGS]]

Instead of support points, you can use the usual closest point calculations (SAT or GJK or other) with the rotated objects. Then those points can be added to the persistent manifold. The btPersistentManifold class as implemented in Bullet already takes care of contact point reduction, and merging duplicate points.

Of course, but I'm writing my own Engine, and only sharing ideas with bullet - I'm not going to use it's code

Indeed, points will drop but at 60 hertz there are usually no serious noticeable issues. The quality is good enough for sliding boxes and ragdolls. I recommend just trying out Bullet. There is some ragdoll demo in Bullet, and it should be easy to create some sliding boxes.

The problem is that in this approach warmstarting impulses would be lost, and solver is going to recompute them each time the contact point is lost. I think it will cause instability of sliding heaps, but I really need a demo with test of this aproach here.

[dog]

Here is what I do, and it works well for me, but it may not be the best or fastest solution:

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.

To stop this being slow, or giving me spikes, I queue up queries and only process a certain number per frame. In our current game (which is wrapping up right now) the increase in cost to do this barely shows on the profiler. The stability this gives is noticeable.

Erwin's idea of only chucking out one point per frame is awesome in its simplicity, and may be a better choice. YMMV.

[Dirk Gregorius]

Suslik: It would be very inefficient to realise SphereSphere collision using a ConvexConvex collision

True, and of course I support spheres and capsules as special primitives. Whether you support a box as a special primtive or run it through the general convex code is a matter of choice. Anyway, these primitives give you everything you need.

Erwin: Indeed, points will drop but at 60 hertz there are usually no serious noticeable issues.

I think the best would be you add an example like Erin's "Varying Friction" demo in Box2D to Bullet. With this demo you can easily prove that your method works for sliding and we can stop this discussion that pops up endlessly. The lack of such a demo is suspicious and might be interpreted as if it not works.

Erwin: Instead of support points, you can use the usual closest point calculations (SAT or GJK or other) using the rotated objects

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.

[Dirk Gregorius]

Let me describe as I see "normal distortion" alghorithm(does it have any other name? ) :

I would implement the approach as Gino described it:

1) You find a separating axis
2) You build an arbitrary tangent vector in plane associated with the separating axis
3) Scale this axis to be really small (you need to test what really small needs to be - I would start with 1.0e-5 )
4) Add this "epsilon" vector to the separating axis
5) Rotate this axis (maybe 45 degrees) in the plane and repeat 4) until you have down a full circle


This way you "scan" the contact feature of each object using the support funtion. If you try it let me know how it works in practise. As Erwin correctly pointed out this might only be needed for polyhedral objects. You usually don't need to stack cylinder or capsules so the incremental manifold is sufficient. If you have a shape that is tagged to need extra contact points you run this additional step.


HTH,
-Dirk

[Dirk Gregorius]

Yeah, I've got something to tell you about "lazy" solver enhancements - small "tips" which enhance its robustness and efficiency.

You made me curious. Maybe you want to share some ideas

[Suslik[PGS]]

5) Rotate this axis (maybe 45 degrees) in the plane and repeat 4) until you have down a full circle

And what then?! How could we use generated points? Whe are able to clip one polygon to another, HOW - this is may question

I think the best would be you add an example like Erin's "Varying Friction" demo in Box2D to Bullet. With this demo you can easily prove that your method works for sliding and we can stop this discussion that pops up endlessly. The lack of such a demo is suspicious and might be interpreted as if it not works.

Totally agree. The only prove of the theory is practice

Even worse, when rotating the objects you might get into deep penetrations and need to call the even more expensive penetration solver

What rotation are you talking about?

You made me curious. Maybe you want to share some ideas

Yeah. For axample one of my simple ideas:
All whe know an ugly test when a pyramid or a box stack fall down and the bounce off very high, even gaining kinetic energy. It is especially obvious when we use few solving iterations of Gauss-Seidel with overrelaxation coefficient about 1.01f-1.1f Why this happens? Right after the box stack inmpacts against the ground, because of too few iterations with warmstarting lagrangian multipliers grow too high and then they simply don't have enough time to go down, giving additional impulses to boxes. Huh, I'm not too good at technical English, you know. But the motto of my approach is : "we'd better lose some energy in spite of gaining too much" So the alghorithm is extremely simple: we set overrelaxation coefficient for growing impulse about 1.03f(classic) and about 2.0f for reducing ones. It lets impulses to reduce much faster than to grow - a bit cheaty, but it works great with sphere stacks with about of 300 spheres. You could see screenshots of this approach here

And here is its code:

Code: Select all

inline void ContactNormalLimiter::ComputeDeltaImpulse()
{
	deltaImpulse = GetDeltaImpulse();
	if(deltaImpulse > 0.0f) deltaImpulse *= 1.03f; else
		                    deltaImpulse *= 1.5f;

	if(accumulatedImpulse + deltaImpulse < 0.0f) deltaImpulse = -accumulatedImpulse;
}

And I've got quite a few of this "tricky" simple methods, which let easily enhance you solver. If nesessary, we could discuss them in another thread, and now I'm very curios about "Normal Distortion" methos - it seems nearly awesome for me, but it isn't clear yet how to clip generated polygons against each other.

[Dirk Gregorius]

HOW - this is may question

Well, as I said I haven't implemented it, but I would start like this if I needed to implement it:

1) We have found two full polygons. (Special cases where you only find e.g. one point on the first shape and maybe two on the other are treated differently)
2) Choose one face to be the reference face and the other to be the incident face.
3) Clip the incident face against the *side* planes of the reference face. Where the side planes are orthorgonal to the reference face
4) Only keep points below the plane of the reference face
5) If you have more the e.g. 4 points reduce the contact set as e.g. described in GPG 4 by Pierre and Adam (approximate convex hull).

The two major steps are to build the clip planes and to clip the polygon against the side planes. The whole approach is explained in all its glory in the presentations of Erin Catto. So you might re-look there. Conceptually this is pretty similar to the SAT approach. The difference is that you use a ClosestPoints() function (e.g. GJK and EPA) and the support function to build the contact faces, while the SAT identifies the faces or edges depending on which feature pair gives the axis of minimum penetration.

I should note that during the "scan" process where you collect the support points I would directly dismiss points that you already found or that are in some epsilon neighborhood.


HTH,
-Dirk

[Suslik[PGS]]

3) Clip the incident face against the *side* planes of the reference face. Where the side planes are orthorgonal to the reference face

Maybe we'd better project one polygon against another not along orthogonal, but along separating axis direction? I used this approach in BoxBox face clipping, and it works great.

Ok, but what to do in degenerate cases, such as:
The first polygon isn't quadrangle, but triangle
The second polygon is a line.
How could we clip a line against the triangle? Should we construct another alghorithm, or use one general for all cases?

I should note that during the "scan" process where you collect the support points I would directly dismiss points that you already found or that are in some epsilon neighborhood.

Of course, not a problem. We'll have to remove even points lying on the same line or other degenerate cases.

[Dirk Gregorius]

Maybe we'd better project one polygon against another not along orthogonal, but along separating axis direction?

Sorry, I don't understand what you mean with this. The clip algorithm by Erin always worked for me and I truly recommend it.

How could we clip a line against the triangle?

Clip the line against the side planes of the triangle and keep the points below the triangle face. Personally I wouldn't care too much about this special cases at the moment since you can always fall back on the incremental manifold in these cases. The important case is face vs face in my opinion. Here you want extra contact points for the shapes.

[Suslik[PGS]]

Clip the line against the side planes of the triangle and keep the points below the triangle face. Personally I wouldn't care too much about this special cases at the moment since you can always fall back on the incremental manifold in these cases. The important case is face vs face in my opinion. Here you want extra contact points for the shapes.

Ok, but how could we generalize this approach to edge-edge contact?

[remark, after thinking a bit]
of course, it'll work if we clip one edge against a plane formed by separating axis and the other edge

[Dirk Gregorius]

For the edge vs edge case I would use the closest points between the segments as contact point. I think Erin suggests using the center. You might want to look this up. As for point vs edge or face you project onto the segment or plane.