tag:blogger.com,1999:blog-779328462175891131.post8829639391886235773..comments2017-09-19T06:10:15.576-07:00Comments on Mediocre game technology: Trapped in configuration spaceDennis Gustafssonhttp://www.blogger.com/profile/07339235520248351574noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-779328462175891131.post-45744878745895616082010-03-24T16:08:35.987-07:002010-03-24T16:08:35.987-07:00Caching of simplices was already part of Stephen C...Caching of simplices was already part of Stephen Cameron's GJK implementation. Things can get nasty when the cached simplex has rotated in the new frame so that the newly added support point creates a simplex that is almost flat (affinely dependent). For resting contacts this does not happen so you will see perforance gains there without the numerical issues.<br /><br />If you take a good stare at Johnson's formula you'll see that it is also testing for containment of the origin in the Voronoi regions of the simplex. The sign tests of the determinants are actually the plane tests of the Voronoi regions. So the only thing that Casey is doing differently is that he does not rely on computing the closest point (and normal to the sub-simplex) using the Barycentric coordinates found by Johnson's algorithm. Taking an explicit normal from a sub-simplex is cheaper and less noisy, but requires you to maintain proper handedness of the simplex or add case distinction on the side of the plane the origin is located. If you do need a closest point, you may find that the projection of the origin onto the sub-simplex does not lie on the sub-simplex at all due to rounding noise in the computed normal. With Johnson's algorithm both the computation of the normal and the closest point rely on the same set of Barycentric coordinates so closest point is guaranteed to be an internal point of the last found simplex. Then again, going through Barycentric coordinates adds more noise to the final result, so you will have more trouble terminating. Either way, both approaches require additional hacks for termination in all cases.<br /><br />In my case, one of these hacks involves checking for actual progress. If the distance does not drop significantly each iteration then it is safe to assume that we ran into numerical issues. Comparing distances needs a division. (You can use rational numbers but this becomes messy pretty quick.) On the bright side, a single GJK iteration (including support point computation) takes thousands of cycles. A division takes roughly 50, and we need only one division per iteration, so the added division is not going to hit us hard. Furthermore, divisions hardly have an influence on the robustness. It's the additions and subtractions that make our lives miserable. <br /><br />BTW, square roots are never needed in GJK, that is, if your objects are (dilated) polytopes (polyhedra, triangles, spheres, capsules).<br /><br />GinoGinohttps://www.blogger.com/profile/09864869947024404187noreply@blogger.comtag:blogger.com,1999:blog-779328462175891131.post-14283138243147041532010-03-18T13:54:37.169-07:002010-03-18T13:54:37.169-07:00It's not a bad idea, but it's kind of nice...It's not a bad idea, but it's kind of nice to support all convex shapes with the same algorithm. Small penetrations I handle with just reusing the last valid contact normal, so a deep penetration solver wouldn't be used very often.Dennis Gustafssonhttps://www.blogger.com/profile/07339235520248351574noreply@blogger.comtag:blogger.com,1999:blog-779328462175891131.post-88541364304788502442010-03-18T13:51:44.927-07:002010-03-18T13:51:44.927-07:00This comment has been removed by the author.Dennis Gustafssonhttps://www.blogger.com/profile/07339235520248351574noreply@blogger.comtag:blogger.com,1999:blog-779328462175891131.post-40096029962926497372010-03-17T16:02:04.472-07:002010-03-17T16:02:04.472-07:00Why not use SAT as penetration depth algorithm? It...Why not use SAT as penetration depth algorithm? It is simple and stable.Dirkhttps://www.blogger.com/profile/16163171860761476111noreply@blogger.com