Deflated GJK for contact generation w/o sampling or EPA

[Johnnylightbulb]

Has anyone ever considered 'deflating' two objects prior to performing the GJK algorithm? I've read a number of whiz-bang ideas here that have been shot down, many of which I've tried before reading about them here (Oh well...) - but I think I've got an evolutionary enhancement to the existing methods that I'd like to talk about.

The idea is stolen from Erwin's GJK 'margin' but just basically works inward (vs outward). The change is so minor and simple I'm sure to be missing a large case this method will fail to work within. Anyways, here's the general idea, given two input bodies:

1. Deflate/Scale each body by any fraction (let's assume 0.1) around it's local origin (Affect S but not RT)
2. Perform full GJK (If during this step you enclose the origin repeat step 1)
3. Find, in world coordinates:
- Closest points on each deflated body as p1 & p2
- Closest points on each non-deflated body as t1 & t2 (transform by the inverse of all step 1's)
4. Test (p1 - t1) dot (t2 - t1)
- If < 0 then the non-deflated bodies are not in contact, return NO_INTERSECTION or Distance(t1 to t2)
- If >= 0 then return CONTACT at t1 & t2 with depth of Distance(t1 to t2)

The central idea is that for any two bodies in contact, the closest points are locally the same no matter what scale* the two bodies are. So if GJK can't find the closest points between two interpenetrated objects, shrink them and get the points, then transform the points back to world space (if needed).

(Attached is a diagram of two potential cases to illustrate the test in #4, above)

For my purposes, I might disregard contacts that enclose the origin on step 2, thus very deep contacts might get missed but the code will be simpler (no stacked transforms) and the entire thing can be done without allocating memory (XNA on the 360 does not like heap-based algorithms). I'm not yet sure if numerical robustness is an issue due to comparing two potentially very different deflated bodies - but I'd doubt it, especially if your fraction is closer to 1.

* The scale must be uniform and be around the true center of a body, not it's center of mass
* Transforms must be applied in Scale*Rotatation*Translation order

[raigan2]

This is something I looked into a few months ago; I was more interested in concave collision and/or morphing geometry, which it turns out sucks with this sort of approach since calculating the "deflation"/medial axis/straight skeleton of concave shapes on-the-fly isn't trivial

One thing is that AFAIK you can't simply use a simple "scaling" to define the deflated version, you need to offset the edges of the shape inward (if anyone knows of a more correct mathematical term for this I'd love to know what to be googling for, the main thing is that it's far more complicated than scaling -- deflating can cause features to vanish/etc). Maybe you can find some way around this, I may also be mis-remembering/confused.. I just gave up since it seemed not as simple as I had initially hoped.

[Erwin Coumans]

Thanks for sharing your ideas.

We discussed scaling down collision shapes, but it causes problems: unlike a margin, the distortion of the collision normal (and hence penetration depth estimation) when using scaling is huge. This causes objects to be pushed in the wrong direction. EPA and sampling don't suffer this problem, especially when the triangle normal is added as sample direction.

Note that the collision margin for a sphere in Bullet is already the entire radius, so the margin is applied 'inwards'.

This is something I looked into a few months ago; I was more interested in concave collision and/or morphing geometry, which it turns out sucks with this sort of approach since calculating the "deflation"/medial axis/straight skeleton of concave shapes on-the-fly isn't trivial

Have you checked the Bullet ConcaveDemo, and pressing 'g'? It handles arbitrary concave models with deformation, as long as the topology/index arrays are not changing.

One thing is that AFAIK you can't simply use a simple "scaling" to define the deflated version, you need to offset the edges of the shape inward (if anyone knows of a more correct mathematical term for this I'd love to know what to be googling for, the main thing is that it's far more complicated than scaling -- deflating can cause features to vanish/etc).

The Bullet ConvexDecompositionDemo implements this for convex polyhedra brute force (but it can be done offline). In a nutshell, it calculates all plane equations, shifts the planes inward, and recalculates the intersection points of the shifted planes. Those intersection points are used in the actual convex hull. This prevents the pieces in the convex decomposition to start in a penetrating state, while still having a margin.

Hope this helps,
Erwin

[raigan2]

Have you checked the Bullet ConcaveDemo, and pressing 'g'? It handles arbitrary concave models with deformation, as long as the topology/index arrays are not changing.

Sadly I haven't looked through the sources in a long time -- over a year ago probably. I have almost no C++ experience, so it's fairly overwhelming for me

Is it still conservative-advancement-based? My issue with such approaches is that the collision detection is solved, but the structure of the simulator becomes much more complicated -- rather than a nice and simple single pass through each step [step world forward; query/generate collision constraints; solve all constraints] you end up having to implement a scheduling system where you test collision and incrementally step objects forward/backward, solving inbetween.. we're already doing this in a limited case (for "rope/wire", which is simply run after rigid bodies have updated in order to simplify things) and it's a major PITA.

[Erwin Coumans]

Is it still conservative-advancement-based? My issue with such approaches is that the collision detection is solved, but the structure of the simulator becomes much more complicated -- rather than a nice and simple single pass through each step [step world forward; query/generate collision constraints; solve all constraints]

By default Bullet uses a single pass discrete physics pipeline [find collisions -> resolve collisions and penetrations -> update positions], using the btDiscreteDynamicsWorld. The continuous version btContinuousDynamicsWorld is not enabled currently, but there is a continuous collision detection query available.

You could just compile and play with the latest Bullet demos to see the effect.
Thanks,
Erwin

[Johnnylightbulb]

unlike a margin, the distortion of the collision normal (and hence penetration depth estimation) when using scaling is huge

Ah... I see this - When I rotate the box in the above picture to be horizontal and make it really long it has wildly different collision normals on the full size and deflated versions. I suppose at best I could minimize the error with a binary search towards the 'least deflated' bodies - but of course it would still be inaccurate and eat up and performance bene's.

Back to implementing proper margins and sampling in my app... Thanks for the insight!