Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
Posted 10 July 2011 - 03:00 PM
Posted 11 July 2011 - 09:19 AM
Posted 11 July 2011 - 01:09 PM
My experience with GJK is that 32 floating point precision is not sufficient to get reliable results for quadric shapes. GJK works very well and reliable for convex polyedra though. Note that spheres and capsules can be treated as points and segments and you add the radius later. This trick makes them robust as well. My personal recommendation is to NOT use GJK for cylinders, cones and other quadric shapes.
See GJK Erin Catto's presentation from 2010. It is setup to address a lot of precision problems you are describing here. Keep in mind that this presentation is based on experiences on his work at Blizzard and with Box2D. These are real world experiences with many games and not just some physic demos.
Regarding EPA I totally recommend against even trying it and waste time thinking about it. Besides its complexity to implement it can fail and you need a third algorithm for this case. From my experience GJK with convex polyhedra and SAT work very robust and reliable.
HTH,
-Dirk
http://code.google.c...to.zip&can=2&q=
// start looping for (int i = 0; i < maxIteration; i++) { // find new point for the simplex support(newestPoint, actorA, actorB, direction); // test newest points position relative to origin if (m3dDotProduct3(newestPoint, direction) < 0) { // last point added did not pass the origin, Minkowski Sum cannot possibly contain the origin return false; } // add a new point to the simplex simplex.add(newestPoint); // update simplex and direction, return true if simplex encompasses origin if (updateSimplexAndDirection(simplex, direction)) { // collision detected return true; } } return false;
Posted 11 July 2011 - 01:44 PM
Posted 11 July 2011 - 05:08 PM
From the picture I would say it might be a bug. From the code snippet you posted it looks like you are using Casey's code. I remember that there was a bug with this code and it can report false positives. When I discussed this with Casey he said it wasn't an issue for him since he used it for culling. False positives are clipped away anyway later so in his particular case it isn't a problem. Sorry, but this is years ago. I really don't remember exactly.
If you want to figure this out you need to debug it. And that means you need to render the state of simplex relative to the origin at each iteration. This is what I did. The good thing about collision detection is that you can visualize everything! So make use of this.
Ah, I remember now. I think there was some issue with his argument that you only have to search specific Voronoi regions in practice. In reality you could search these regions first, but you must also check for the others as well. Just assert() that the origin is never in one of the regions - I hit that assert() quite often. I even discussed this with Erin and in the end we both agreed that Casey's optimization is causing too many problems. If I remember the exact problem I let you know here.
So I guess you need to write you own simplex solver. Look at Erin's code in Box2D or Erwin's code in Bullet for good examples.
HTH,
-Dirk
Posted 11 July 2011 - 06:13 PM
Posted 11 July 2011 - 06:49 PM
Well, Casey's presentation is very nice, but it by no means a reference implementation! As I already said in another post here I recommend looking at Erin Catto's presentation. It is *trivial* to write an efficient simplex solver for the tetrahedron case from his work. Note that even Bullet uses a fallback implementation onto the triangle case as suggested in Christer Ericson's book. A solid GJK implementation is not an easy problem . So don't worry if it takes some time.
Posted 11 July 2011 - 07:56 PM
Posted 11 July 2011 - 08:28 PM
You will do it! If you have questions post here and if I miss your post for some reason just feel free to send me a PM.
Good Luck
if ( ((BCxBA)xBA) · BX >= 0 ) { //<--- should that be >= or >? i've seen both used, also, if i dotted it by AX instead of BX, would that make a difference? if (AX · AB >= 0) { if (BX ·BA >= 0) { // the origin exists only in Eab // remove point c from simplex // what should search direction be? } }
Posted 11 July 2011 - 10:43 PM
[b]line simplex:[/b] check if closest to A remove point B return check if closest to B remove point A return assume its closest to AB edge [b]triangle simplex:[/b] check if closest to A remove point B remove point C return check if closest to B remove point A remove point C return check if closest to C remove point A remove point B return check if closest to AB edge remove point C return check if closest to AC edge remove point B return check if closest to BC edge remove point A assume its above or below triangle if above triangle, continue if below triangle, rewind triangle so it faces down [b]tetrahedron simplex[/b] check if closest to A remove point B remove point C remove point D return check if closest to B remove point A remove point C remove point D return check if closest to C remove point A remove point B remove point D return check if closest to D remove point A remove point B remove point C return
if (dot(ABC, AO) >= 0 ) { if (dot(ACD, AO) >= 0) { // the origin is within an acute angle of both faces, and therefore is somewhere between them along the edge AC // remove B and D // what should i set the direction to? } }
Posted 12 July 2011 - 09:12 AM
Posted 12 July 2011 - 12:36 PM
This looks all good. For the tetrahedron case the origin can be closest to a vertex, edge, face or be inside the tetrahedron. I would use Erin's approach where you compute the barycentric coordinates and use these to check the Voronoi regions. This is very structured and efficient.
Regarding the search direction it is all in the code. Use the right-hand-rule to figure it out.
http://en.wikipedia....Right-hand_rule
if (m3dDotProduct3(ABxAC, AO) > 0) { if (m3dDotProduct3(ACxAD, AO) <= 0) { if (m3dDotProduct3(ADxAB, AO) <= 0) { if (m3dDotProduct3(DCxDB, DO) <= 0) { // origin is closest to ABC face } } } }
Posted 13 July 2011 - 09:02 AM
Posted 13 July 2011 - 04:37 PM
You can use the triple product and compute the volume when you are creating a tetrahedron simplex. If you get a negative result you can revert the winding of the triangle. Another way to verify this is to use the other vertex on a triangle. E.g. you looking at triangle ACD. Then you know that B must be behind this triangle. Same is true for all other combinations.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
GameDev.net™, the GameDev.net logo, and GDNet™ are trademarks of GameDev.net, LLC.