Alternatives to EPA
-
- Posts: 27
- Joined: Wed Nov 07, 2007 12:49 am
Alternatives to EPA
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
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
-
- Posts: 27
- Joined: Wed Nov 07, 2007 12:49 am
Re: Alternatives to EPA
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?
is this a path worth pursuing? or am I wasting my time?
-
- Posts: 40
- Joined: Fri Jul 22, 2005 8:00 pm
- Location: Santa Monica
Re: Alternatives to EPA
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).
Getting a stable, robust and fast EPA is far more difficult (I have shipped games with various EPA implementations).
-
- Posts: 78
- Joined: Mon Nov 13, 2006 1:44 am
Re: Alternatives to EPA
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.
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.
-
- Posts: 27
- Joined: Wed Nov 07, 2007 12:49 am
Re: Alternatives to EPA
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!
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!
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Alternatives to EPA
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've been recently researching on migrating my SAT-based narrowphases to GJK+EPA, which seems to be the
new standard for doing this
-
- Posts: 27
- Joined: Wed Nov 07, 2007 12:49 am
Re: Alternatives to EPA
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.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.
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.
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: Alternatives to EPA
Hi Dirk,Dirk Gregorius wrote: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've been recently researching on migrating my SAT-based narrowphases to GJK+EPA, which seems to be the
new standard for doing this
public documents by Havok literally refer to 'expanding polytope algorithm'.
Are you suggesting that Havok is not using the expanding polytope algorithm?
Thanks,
Erwin
-
- Posts: 27
- Joined: Wed Nov 07, 2007 12:49 am
Re: Alternatives to EPA
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.Erwin Coumans wrote: Are you suggesting that Havok is not using the expanding polytope algorithm?
Erwin
-
- Posts: 27
- Joined: Wed Nov 07, 2007 12:49 am
Re: Alternatives to EPA
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..
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Alternatives to EPA
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.
-
- Posts: 78
- Joined: Mon Nov 13, 2006 1:44 am
Re: Alternatives to EPA
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.Dirk Gregorius wrote: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.
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.
-
- Posts: 40
- Joined: Fri Jul 22, 2005 8:00 pm
- Location: Santa Monica
Re: Alternatives to EPA
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.
2. Project the origin along the collision normal onto the portal triangles of each object to get the correct witness points.