Persistent Manifold question

Please don't post Bullet support questions here, use the above forums instead.
Suslik[PGS]
Posts: 30
Joined: Fri Jan 04, 2008 1:51 pm
Contact:

Persistent Manifold question

Post by Suslik[PGS] »

My question is : "How could we update existing contacts in persistent contact manifold from frame to frame?" The common example is : we have a box sliding on a plane, after four frames, we could find all four collisions, but we have to update their position pfom frame to frame, how could we do this? As for me, the main problem is to solve this task in a general case - for example, for edge-edge or vertex-face convex contact or even sphere-sphere conact, because they behave in completely different manner.
If you are interested in my engine, you could look throght its screenshots on this page

PS I'm very sorry for my bad English - it's not my native language
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Persistent Manifold question

Post by Erwin Coumans »

You can keep the contact points in local space for each object. Then each frame, update the contacts in worldspace, and determine if they are still valid. I should have a bit more information and pictures on this topic soon.

You can see this implemented in Bullet btPersistentManifold.

By the way, the pictures of your engine looks nice, and it performs quite well. Do you have more information about its internals?

Thanks,
Erwin
Suslik[PGS]
Posts: 30
Joined: Fri Jan 04, 2008 1:51 pm
Contact:

Re: Persistent Manifold question

Post by Suslik[PGS] »

You can keep the contact points in local space for each object
Of course, I keep this information
Then each frame, update the contacts in worldspace, and determine if they are still valid
That's the problem. How could I update the contact in general case, without feature handling? And is it possible at all? Because it's not very elegant solution to keep information about ALL kinds of contacts such as : "convex's edge vs pyramid's corner", "sphere vs cylinder's side", or even "face vs capped cyliner' cap" :)
By the way, the pictures of your engine looks nice, and it performs quite well. Do you have more information about its internals?
Of course. I use SAT tests with all rigid primiteves(bottleneck currently is here) in collision detection, and Sequential Impulses with a couple of enhances in RigidRigid and RigidSoft solver. Also I use very simple approach in SoftSoft collision dection(handle only Vertex vs Face contacts), and solver is very similar to Agea's in their paper "Position Based Dynamics"
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Persistent Manifold question

Post by Dirk Gregorius »

I lately looked into the persistent manifold as well. Assuming I understand everything correctly it works something like this:

1) Find the closest points (GJK or EPA) on the hulls
2) Add these points to the persistent manifold
3) If you have more than 4 points substitute each point in the old manifold with the new point and compute the area of the quad defined by this four points. Keep the configuration that creates the biggest area. Additionally always keep the point with the deepest penetration. The later means that instead of substituting all four points, only substitute the three points other than the point with the deepest penetration.

Relatively simple. I think there exist different "dialects", e.g. using feature information, but I didn't look into this. If you have a working SAT why don't you stick with this?



Cheers,
-Dirk
Suslik[PGS]
Posts: 30
Joined: Fri Jan 04, 2008 1:51 pm
Contact:

Re: Persistent Manifold question

Post by Suslik[PGS] »

Unfortunately, you missed the main problem - how could we update contacts currently included in the contact manifold from frame to frame? That's why this method appeared be surprisingly difficult for me to to implement.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Persistent Manifold question

Post by Dirk Gregorius »

I think Erwin stores each contact point in local coordinates. Then each frame the points are transformed back to world coordinates and only kept if their new distance is within some distance threshold. Otherwise the contact is removed. (Think of a ball-socket joint - same idea, but you reject points that have moved apart too much). Of course this *theoretically* might result in problems when a box slides down an inclined plane, it also might be not sufficient quality for box puzzles like in Tomb Raider since you only have one contact point each frame, but I haven't tried it so you should implement it yourself. For ragdolls and simple debris it is definetely sufficient. Even stacking seems to work fine with this method. Note that there are also methods to find the full manifold each frame, e.g. the method suggested by Jan Bender (you can find it in his engine - I think even based on Bullet). Also you can scan the contact features by distorting the contact normal a little and use the support fuction. I think Erwin has implemented both methods so he might have more information on this.

HTH,
-Dirk


Link to Jan Bender's approach: http://www.impulse-based.de
Suslik[PGS]
Posts: 30
Joined: Fri Jan 04, 2008 1:51 pm
Contact:

Re: Persistent Manifold question

Post by Suslik[PGS] »

Of course this *theoretically* might result in problems when a box slides down an inclined plane
I think it's a real and definitely practical problem - box sliding along a plane with a jumpy behavior must look *strange* :)
Even stacking seems to work fine with this method
Stacking will act well, because contacts don't move in relative coordinates. But sliding is a problem.
Also you can scan the contact features by distorting the contact normal a little and use the support fuction.
What do you mean? I'm not too good at English, so I haven't understood this approach properly - could you explain it in other words?

Code: Select all

Link to Jan Bender's approach
Thanks, but after a lot of physics programing years, I think I saw most of physics programmers' blogs :) Your, Erin's, Gino's and, of course, Jan Bender's are not exceptions ;)
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Persistent Manifold question

Post by Dirk Gregorius »

I think it's a real and definitely practical problem
As do I, but since I never implemented it and use SAT because of these concerns I tagged it theoretically. I can only imagine these problems, but I am also sure you will run into them :-)

..could you explain it in other words?
I made a simple sketch. Note that I also never implemented this, so this is just to give you the idea. Imagine the two shapes that are overlapping withing their margins. So you identify the two black points as the closest points. I also sketched the contact normal, but outside the two boxes for clarity (also the normal points from shape1 towards shape2 per definition). So in order to scan the contact feature of e.g. the second shape I revert the normal and distort it a little (n1 and n2). If I now call Shape::GetSupport() using the distorted normals I find the original point and the red poin. The same works for the lower box where I find the two points in the upper corners. . With this technique I could *theoretically* build the full contact geometry. Once you have identified the upper and lower contact geometry you simply clip as e.g. suggested by Erin in Box2D. Did you get the idea?

Please share your experiences if you implement this!
FeatureScan.png
FeatureScan.png (7.97 KiB) Viewed 15050 times

HTH,
-Dirk
Suslik[PGS]
Posts: 30
Joined: Fri Jan 04, 2008 1:51 pm
Contact:

Re: Persistent Manifold question

Post by Suslik[PGS] »

OMG, that's brilliant! How could I disregard this idea? It still seems not too comprehensive to implement, and i couldn't find any cornerstones :) Thanks you very much, I'll definitely try to implement it.

Actually I have very general collider interface in my engine, so it supports different kinds of contact manifold - persistent and instant as well. So I could use Instant contact manifold alghorithm for for example Box-Box collision, but persistent for Box-Cylinder collision. I think there should be a couple of cases when approach you described should work really great!

I forgot to notice that I'm not using Shape margins - all shapes are allowed to penetrate.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Persistent Manifold question

Post by Dirk Gregorius »

Thank Gino. It is his idea and he shared it with me during a dinner :-)
I forgot to notice that I'm not using Shape margins - all shapes are allowed to penetrate
I am curious. What do you use to compute the closest points? Another reason I never implemented this approach are my concerns about the numerical robustness of GJK and EPA. In an ideal world we would like to have one function that can return the closest points for both penetrating and disjoint shapes.
Suslik[PGS]
Posts: 30
Joined: Fri Jan 04, 2008 1:51 pm
Contact:

Re: Persistent Manifold question

Post by Suslik[PGS] »

It is his idea and he shared it with me during a dinner
It's really a honour to have a dinner with people like Gino and and the rest of your "party" :)
I am curious. What do you use to compute the closest points?
I'm currently using silly SAT method and instant manifold generation, so I decided to implement persistent manifold only a few months ago and it's not actually working yet :) That's because I DO care about OOP structure of engine, it's extremely important for me, and it wasn't too easy to combine two approaches - persistent and instant manifold generation in one architecture.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Persistent Manifold question

Post by Dirk Gregorius »

If you are at the GDC we usually meet for a dinner. Erwin also meets people at the GDC when presenting Bullet in the show rooms. Besides this from my experience people are very open and relaxed to meet. So if you are around just ask. Gino I live only two hours apart so this was not too difficult.

So if you use SAT you currently don't suppurt cone and cylinder (not capsule) or did you implement this in terms of SAT? Personally I don't see a problem using the SAT approach since you can always use small convex meshes to model quadric shapes. There might be some bounciness, but this is very difficult to see *in practise* if you use a reasonable number of faces. Actually you get some rolling resistance for free this way. Valve uses this approach in Half-Life 2 and artists seem to like this approach since it is easy for them to create simple convex shapes from the render mesh. If you are interested in this browse the MollyRocket forum. Jay Stelly from Valve shared some ideas and numbers there. As you most probably know you find a nice GJK video there as well.


Cheers,
-Dirk


Link: https://mollyrocket.com/forums/viewforu ... 07270394ed
Suslik[PGS]
Posts: 30
Joined: Fri Jan 04, 2008 1:51 pm
Contact:

Re: Persistent Manifold question

Post by Suslik[PGS] »

So if you are around just ask
Actually, I live in Russia - it's quite far from you, and I study really hard, so I don't have free time to go abroad. :(
did you implement this in terms of SAT
No, I'm not currently suporting such kinds of geometries
Personally I don't see a problem using the SAT approach since you can always use small convex meshes to model quadric shapes
I pursue for two objects - efficiency and elegance of code. Approximating quadratics isn't very efficient or elegant solution ;) I think that approach you described in previous post should deal well with it! We could even control the number of points generated varying the number of distorted axes.
browse the MollyRocket
I've browsed througt it a long before and found there a lot of interesting information, bot now it seems to be dead :(
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Persistent Manifold question

Post by Dirk Gregorius »

I pursue for two objects - efficiency and elegance of code.
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.

Regarding MollyRocket:
There is still some information out there. But I agree it not much and the use cases of the GJK are different. Boolean intersection for visibility queries vs. closest points computations for contact generation. Still I would search for the comments of Jay. They are quite interesting and give some insights.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Persistent Manifold question

Post by Erwin Coumans »

Dirk Gregorius wrote:Of course this *theoretically* might result in problems when a box slides down an inclined plane
I think it's a real and definitely practical problem - box sliding along a plane with a jumpy behavior must look *strange* :)
It is not as bad as you think, a famous commercial game physics engine has using this method for several years and many games shipped this way without noticeable sliding problems. In one big upcoming game using Bullet collision detection (on Playstation 3 and XBox 360) we improved the sliding behaviour by adding the heuristic of only throwing away a maximum of one point at a time. Although I don't think this is necessary in most cases, it improves stability a bit. Of course, with this heuristic some points should have been discarded but stay 2 or 3 frames too long. But at 60 frames/second that is usually not a real issue.

Mirtich has been writing about persistent contact manifolds, using contact features to recognize existing points.
http://www.merl.com/reports/docs/TR98-01.pdf

I prefer a method that is not restricted to polyhedra, so it works with all Bullet shapes (capsules, cylinders, cones , convex multi-sphere shape etc). But when features are available a method can use them obviously.

We discussed the one-shot method by rotating the object around the separating normal to get multiple points here:
http://www.bulletphysics.com/Bullet/php ... ?f=4&t=288
Apart from Gino, my former collegue Eric Larsen also came up with this idea and implemented it a long time ago, and it works well. However, multiple collision checks are more costly then just adding one point at a time. So you could combine the two methods, and only use the most costly 'pertubation/rotation' method under certain conditions. For example at first contact, or if there are less then 2 contact points.

Right now, I'm working on a book on advanced game physics, collision detection and rigid body dynamics for commercial 3d games. I will be including a lot of documentation and samples about contact generation, caching and persistency etc. We could discuss this a bit further when I get to that chapter, ok?

Thanks,
Erwin
Post Reply