Alternatives to EPA

[goruka]

Hi! I've been recently researching on migrating my SAT-based narrowphases to GJK+EPA, which seems to be the
new standard for doing this, as i'll likely need a lot less code for handling shapes.
GJK has been a pretty straightforward technique and I think i got it to work without much trouble.. although the limitations
were soon evident (not being able to obtain the best separation axis and depth) but so far EPA looks like
a very strange algorithm, and even though I seem to grasp the concept of growing the simplex until "it doesn't grow as much", i feel it's a pretty complex solution to what at firt sight it seemed to me like a simple problem.

So here's a question.. is not not possible to obtain at least a pretty good separation axis (SAT-like) in some other way? I gave a check at the Bullet source code and noticed it uses margins, so why not just do a sort of binary search from a "definitely inside margin" to "definitely outside margin", by making the margins of A and B shrink, repeating GJK until it "works" (the moment before they touch will give me separation axis)?

Well just a thought.. I'm sure someone else thought about this first and realized it doesn't work

[goruka]

Ah, i've been thinking a little more and definitely i can't do it with a plain gjk, because what I'd need to shrink is the actual minkowski sum volume, not the source volumes.. however i don't think i can shrink it by just asking the operands for supports.. but if i ask them for normals maybe i could somehow get it to work this way.. or maybe i could just do EPA anyway..
is this a path worth pursuing? or am I wasting my time?

[dog]

I strongly recommend trying to implement a version of Minkowski Portal Refinement such as Gary Snethen's XenoCollide. See Game Programming Gems 7 (it has source code!) and elsewhere on this site. It is easier to understand, has far fewer special cases, is numerically more robust (at least my implementation was) and is far easier to optimize for SIMD.

Getting a stable, robust and fast EPA is far more difficult (I have shipped games with various EPA implementations).

[Nathanael]

I don't think EPA is that complicated, considering that it work on all class of convex shapes (that included quadratics, ie: ellipsoid/ellipsoid ).

The core of the algorithm is basically an incremental convex hull builder, the current bullet implementation of EPA (btGjkEpa2.cpp) is less that 300 lines of code.

For alternative method, you may want to read this:
http://www.bulletphysics.com/Bullet/php ... f=6&t=1964
and
http://xenocollide.snethen.com/

Nathanael.

[goruka]

Oh, whoa... just some months ago, this MPR/Xenocollide technique didn't even seem to exist
I'm still not sure on performance (has anyone benchmarked it against GJK/EPA?)
but logic/code wise it seems a lot simpler to implement. I'll give it a try next week..
thanks!

[Dirk Gregorius]

I've been recently researching on migrating my SAT-based narrowphases to GJK+EPA, which seems to be the
new standard for doing this

How have you concluded that this is the new standard? From the third party and open source engines only Bullet uses this as far as I know.

[goruka]

How have you concluded that this is the new standard? From the third party and open source engines only Bullet uses this as far as I know.

I have worked with a few other commercial game engines (I'm not sure if i can say which ones, since I don't remember the exact terms of the NDA -likely i can't-), which have their own physics engine implementation.
Both used GJK+EPA, although the most curious thing about one of them is that it used GJK+EPA, but resorted to SAT in case they failed (and they had every kind of shape vs. shape algorithm). Seeing bullet only uses GJK+EPA, i'm not sure if they did this because of lack of robustness in their algorithm, or because of something special they know.

[Erwin Coumans]

I've been recently researching on migrating my SAT-based narrowphases to GJK+EPA, which seems to be the
new standard for doing this

How have you concluded that this is the new standard? From the third party and open source engines only Bullet uses this as far as I know.

Hi Dirk,

public documents by Havok literally refer to 'expanding polytope algorithm'.

Are you suggesting that Havok is not using the expanding polytope algorithm?
Thanks,
Erwin

[goruka]

Are you suggesting that Havok is not using the expanding polytope algorithm?
Erwin

Erwin, Not sure if i'm adding anything here, but I've never had the chance to use Havok, I actually meant other game engines (with their own inhouse physics engines) are also using GJK+EPA. As I'm not sure if i'm breaking an NDA i can't comment, but those are known ( not-so-large as gamebryo, UE, etc) engines.

[goruka]

As a sidenote, Just implemented XenoCollide without any problems. I'm using it together with GJK for intersection, as it appears to be faster than just XenoCollide alone, and while i don't have any numbers to compare, it seems to work nicely. Erwin, do you know if there are any plans for adding XC/MPR to bullet? as I'd love to see it compared to GJK+EPA..

[Dirk Gregorius]

Does XenoCollide now return the correct penetration distance and not just an conservative estimate? Last time I looked at it this was the case and Gary also agreed on this on the forum.

[Nathanael]

Does XenoCollide now return the correct penetration distance and not just an conservative estimate? Last time I looked at it this was the case and Gary also agreed on this on the forum.

I'd like to know that too, last time i implemented it, it was an approximation, but to be fair, in most polyhedral cases, it was the global minimum, but i never used it because it was really too approximate for heavily scaled quadratic like shapes.

Also, Gary Snethen stated that exact penetration depth is not that important, I'd like to know the rational behind that statement, we already gave up rotational penetration depth, it seem the me that exact computation can be quite important, especially when implementing drift correction at positions level, or doing some kind of shock propagation.

[dog]

1. Once you have a normal and the origin, rerun the code starting from the origin - normal and in the direction of the normal.

2. Project the origin along the collision normal onto the portal triangles of each object to get the correct witness points.