From: Gino van den Bergen <gvandenbergen@pl...>  20051115 20:58:05
Attachments:
Message as HTML

When it comes to speed and robustness I would put my money on (1) = construct separatingaxes tests for all pairs of simple polytopes = (prisms, OBBs, AABBs, triangles). The problem with this approach is that = if the number of primitive types is large you will spend a lot of time = coding, testing, and debugging. Furthermore, if you need contact = information, then a SAT is not very helpful. (2) I know several Convex = Hull approaches (Cameron's explicit Minkowski sum, LinCanny, = ChungWang, VClip, SWIFT, to name a few). These approaches are usually = far less robust than a SAT en slower for the object complexities that = you are interested in. (3) If you need a single magic solution "that = rules them all", try GJK. You can argue whether GJK is simple, but it = surely is the most powerful approach to collision detection of convex = shapes. So, my 2 cents worth would be: Try (1) if the number of = primitive types is small (fewer than, say, 5), and have lowcomplexity = (fewer than 5 edge directions and face orientations), otherwise, invest = some time in discovering GJK. Gino van den Bergen http://www.dtecta.com =20 Original Message From: gdalgorithmslistadmin@... on behalf of Diogo = de Andrade Sent: Tue 11/15/2005 8:55 PM To: gdalgorithmslist@... Cc:=09 Subject: [Algorithms] Prism problems... Hey all. =20 Continuing my ongoing saga on creating a 3rd person action title in an insanely short time, I have a piece of advice to ask you. I'm still trying to automate the building a navigation mesh for the AI's in my game (not using it for player anymore, though). I have limited success with my raycasting approach, if I use lots of samples per triangle (in the order of 500 per tri). Well, with 10000 tris upfacing tris in the whole scene, and with subdivisioning of the "ground" mesh, I have more than 25M rays being cast. Even using some optimizations, this still takes about 10 mins to calculate, and it misses some stuff sometime, which makes the enemies walk through walls and stuff like that. So, I wanted to make this better, and, following the suggestion of Jon Watte, and use a triangular prism per tri, instead of 500 rays. Well, I searched the net all over, my library, and still couldn't find an explanation on the best way to do Prism/OBB, Prism/AABB and Prism/Tri intersection test (I don't need intersection points, or any other of that sort of thing, just an yes or no answer will do). So, I have to roll my own, but before I leap into it (which already sounds like a terrible ordeal), I understand there are several approaches to this problem: =20 1) SAT test. While I understand it in concept, I still have some problem understanding which are the candidate planes, how to extract them and all that. So this one is very hard for me at the moment. 2) Convex Hull approach: treat the prism as a convex hull. Apparently I can find on the net more information on convex hull construction and testing than SAT tests, so although this seems pretty hard by itself, it's also better documented, I think. 3) Some magic/simple solution that I can't think of and someone did. This would be probably the best, but I guess that's just wishful thinking. =20 So, which of the solutions is faster/more robust/easier to implement?=20 Of course, if someone has a Prism/OBB and Prism/Triangle routine somewhere on the hard drive, I would appreciate that even more (call me lazy with a short development time), but considering the lack of info I found on the net, I guess not many people need this kind of algorithm, so it probably nobody has it/wants to give it away. :) =20 Well, thanks in advance for helping me with another simple problem. =20 Diogo de Andrade Spellcaster Studios <mailto:diogo.andrade@...> diogo.andrade@... <http://www.spellcasterstudios.com>; http://www.spellcasterstudios.com =20 =20 
From: Gino van den Bergen <gvandenbergen@pl...>  20051122 15:44:06
Attachments:
Message as HTML

First of all, do yourself a favor and get rid of the absolute epsilons. = They do not make any sense. If you think that in the end you can fix the = test by tweaking the epsilons you are in deeper throuble than you = imagined. Collinear edges are harmless. In the rare case where the cross product = is a zero vector (Under Visual C++ 7.1 the cross product of the same = vectors does not even yield a zero vector.) all points are projected to = zero and thus a zero vector is not a separating axis. (Make sure you = multiply out all divisions!) In the case where the cross product is very = close to zero, the direction of the cross product is of course very = noisy but this doesn't matter, since the cross product had a very VERY = slim chance of being a (unique) separating axis to start with. The worst = that could happen is that the theoricial cross product was a separating = axis (and the only separating axis), and its noisy computed counterpart = is not. In case the noisy version turns out to be a separating axis then = no harm is done, since albeit not the vector you intended to test, it = still is a valid separating axis. =20 In general, a pure finiteprecision SAT may return false positives, but = never false negatives. Using epsilons only makes its behavior worse = (more false positives).=20 Gino van den Bergen http://www.dtecta.com =20 Original Message From: gdalgorithmslistadmin@... on behalf of Diogo = de Andrade Sent: Tue 11/22/2005 12:50 PM To: gdalgorithmslist@... Cc:=09 Subject: RE: [Algorithms] Prism problems... Yes, that's what I did, sorry, got mixed up... :) I already do a more robust test for=20 if ( t > 0 ) positive++; else if ( t < 0 ) negative++; Replaced it with if (t>EPSILON_FLOAT) positive++; else if (t<EPSILON_FLOAT) negative++; Another thing that I've been thinking on is what to do if two edges of different convex hulls are parallel... it's cross product is the NULL vector, obviously enough... Should I detect it and skip that case, or should I just test the edge itself (don't think this last can hurt, but I think it won't yield nothing new on the test)... Regarding what Allen said, I think I understand the base math of what I'm doing, it's the details that confuse me, specially with conflicting and counterintuitive tests (specially when the examples come from people that know so much more than me) (the edge/edge part is particularly confusing in debug terms, not in math terms)... Still trying to debug it, though... Diogo de Andrade Creative & Technical Director Spellcaster Studios diogo.andrade@... http://www.spellcasterstudios.com =20 Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of James Levick Sent: Monday, November 21, 2005 20:17 To: gdalgorithmslist@... Subject: Re: [Algorithms] Prism problems... Diogo de Andrade wrote: > Yes, what I'm having are false negatives, basically everything that's > separated by an axis that is not one of the facenormal axis isn't being > detected... removing the " side0*side1 < 0" test gets me an almost ok > collision test, although in that case I get some false positives... Just checking this isn't a typo  my suggestion was to replace the=20 return false on the two earlier tests with continue, you will need to=20 keep the side0*side1 < 0 test. That is, change the algorithm to: for each pair of edges { int side0 =3D WhichSide(C0.V,D,C0.E(i).vertex); if ( side0 =3D=3D 0 ) continue; // not return false int side1 =3D WhichSide(C1.V,D,C0.E(i).vertex); if ( side1 =3D=3D 0 ) continue; // not return false if ( side0*side1 < 0 ) return false; } The first two tests just try for early outs in the case where the axis=20 cannot separate the two polyhedra (though the second test doesn't save=20 much). If you are still having problems, I would suggest it might come down to=20 issues with numerical robustness. The definition of the WhichSide=20 function given in the document is not very robust for points close to=20 the plane being tested; try modifying the line: if ( t > 0 ) positive++; else if ( t < 0 ) negative++; to compare against a tolerance value rather than 0. At least one vertex=20 is going to lie directly on the potential separating plane due to the=20 way the algorithm works, and any numerical error could cause this axis=20 to be dismissed as separating and thereby cause a false positive. HTH James  This SF.Net email is sponsored by the JBoss Inc. Get Certified Today Register for a JBoss Training Course. Free Certification Exam for All Training Attendees Through End of 2005. For more info visit: http://ads.osdn.com/?ad_id=3D7628&alloc_id=3D16845&op=3Dclick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188  This SF.Net email is sponsored by the JBoss Inc. Get Certified Today Register for a JBoss Training Course. Free Certification Exam for All Training Attendees Through End of 2005. For more info visit: http://ads.osdn.com/?ad_id=3D7628&alloc_id=3D16845&op=3Dclick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Erin Catto <erincatto@sb...>  20051122 17:34:31

Certain optimizations of the arithmetic for edge cross products can lead to false negatives. This came up in the BoxBox SAT. The edgeedge tests can be vectorized so that three tests can be combined into one 3vector computation (good for SIMD). The form of the expression is no longer: separation = dot(axis, ...) I had a case where two boxes always have parallel edges due to constraints. In some cases they would overlap deeply before the SAT failed. Thus, I had a false negative. To get a robust test I compare the separation measure to FLT_EPSILON times the length scale of the boxes. It is conceivable that I will now get false positives. However, in that case the distance is small and I would not generate contact points. Erin Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Gino van den Bergen Sent: Tuesday, November 22, 2005 7:44 AM To: gdalgorithmslist@... Subject: RE: [Algorithms] Prism problems... First of all, do yourself a favor and get rid of the absolute epsilons. They do not make any sense. If you think that in the end you can fix the test by tweaking the epsilons you are in deeper throuble than you imagined. Collinear edges are harmless. In the rare case where the cross product is a zero vector (Under Visual C++ 7.1 the cross product of the same vectors does not even yield a zero vector.) all points are projected to zero and thus a zero vector is not a separating axis. (Make sure you multiply out all divisions!) In the case where the cross product is very close to zero, the direction of the cross product is of course very noisy but this doesn't matter, since the cross product had a very VERY slim chance of being a (unique) separating axis to start with. The worst that could happen is that the theoricial cross product was a separating axis (and the only separating axis), and its noisy computed counterpart is not. In case the noisy version turns out to be a separating axis then no harm is done, since albeit not the vector you intended to test, it still is a valid separating axis. In general, a pure finiteprecision SAT may return false positives, but never false negatives. Using epsilons only makes its behavior worse (more false positives). Gino van den Bergen http://www.dtecta.com 
From: Diogo de Andrade <diogo.andrade@ne...>  20051122 18:31:57

I've already removed the epsilon tests, they were causing more problems that they solved (so thanks Gino!)... Now, Erin, what do you mean by separation measure? I'm approaching a suitable (not wholly robust, but for the purpose (navmesh generation) it doesn't matter that much, I have bigger problems on that) test for prism/OBB and prism/tri, and in the process I think I finally understood how SAT tests work... should come in handy someday... :) So I want to thank you all again for the invaluable help and the patience to get me through this! :) Diogo de Andrade Creative & Technical Director Spellcaster Studios diogo.andrade@... http://www.spellcasterstudios.com Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Erin Catto Sent: Tuesday, November 22, 2005 17:34 To: gdalgorithmslist@... Subject: RE: [Algorithms] Prism problems... Certain optimizations of the arithmetic for edge cross products can lead to false negatives. This came up in the BoxBox SAT. The edgeedge tests can be vectorized so that three tests can be combined into one 3vector computation (good for SIMD). The form of the expression is no longer: separation = dot(axis, ...) I had a case where two boxes always have parallel edges due to constraints. In some cases they would overlap deeply before the SAT failed. Thus, I had a false negative. To get a robust test I compare the separation measure to FLT_EPSILON times the length scale of the boxes. It is conceivable that I will now get false positives. However, in that case the distance is small and I would not generate contact points. Erin Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Gino van den Bergen Sent: Tuesday, November 22, 2005 7:44 AM To: gdalgorithmslist@... Subject: RE: [Algorithms] Prism problems... First of all, do yourself a favor and get rid of the absolute epsilons. They do not make any sense. If you think that in the end you can fix the test by tweaking the epsilons you are in deeper throuble than you imagined. Collinear edges are harmless. In the rare case where the cross product is a zero vector (Under Visual C++ 7.1 the cross product of the same vectors does not even yield a zero vector.) all points are projected to zero and thus a zero vector is not a separating axis. (Make sure you multiply out all divisions!) In the case where the cross product is very close to zero, the direction of the cross product is of course very noisy but this doesn't matter, since the cross product had a very VERY slim chance of being a (unique) separating axis to start with. The worst that could happen is that the theoricial cross product was a separating axis (and the only separating axis), and its noisy computed counterpart is not. In case the noisy version turns out to be a separating axis then no harm is done, since albeit not the vector you intended to test, it still is a valid separating axis. In general, a pure finiteprecision SAT may return false positives, but never false negatives. Using epsilons only makes its behavior worse (more false positives). Gino van den Bergen http://www.dtecta.com  This SF.Net email is sponsored by the JBoss Inc. Get Certified Today Register for a JBoss Training Course. Free Certification Exam for All Training Attendees Through End of 2005. For more info visit: http://ads.osdn.com/?ad_id=7628&alloc_id=16845&op=click _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Erin Catto <erincatto@sb...>  20051122 18:53:11

From page 83 of Gino's book, the SAT for boxbox is: dot(v, c) > dot(v, hA) + dot(Bt v, hB) Where v is the axis, c is the position of box B in box A's frame, B is the rotation matrix of box B relative to box A, hA are the halfwidths of box A, and hB are the halfwidths of box B. The separation measure is the amount that the left side of the relation is greater than the right side. Namely: separation = dot(v, c)  dot(v, hA)  dot(Bt v, hB) If v is formed from nearly parallel axes, then the separation measure may be a very small positive number, even when the boxes overlap. This is a false negative. Erin Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Diogo de Andrade Sent: Tuesday, November 22, 2005 10:27 AM To: gdalgorithmslist@... Subject: RE: [Algorithms] Prism problems... I've already removed the epsilon tests, they were causing more problems that they solved (so thanks Gino!)... Now, Erin, what do you mean by separation measure? I'm approaching a suitable (not wholly robust, but for the purpose (navmesh generation) it doesn't matter that much, I have bigger problems on that) test for prism/OBB and prism/tri, and in the process I think I finally understood how SAT tests work... should come in handy someday... :) So I want to thank you all again for the invaluable help and the patience to get me through this! :) Diogo de Andrade Creative & Technical Director Spellcaster Studios diogo.andrade@... http://www.spellcasterstudios.com 
From: <christer_ericson@pl...>  20051122 19:13:16

Gino van den Bergen wrote: > In general, a pure finiteprecision SAT may return false positives, > but never false negatives. Using epsilons only makes its behavior > worse (more false positives). Erin Catto already pointed out that this is not correct, but I thought I'd also disagree. In fact, I'd argue the exact opposite: you *need* epsilons to avoid false negatives. For a realworld example of a false negative see section 4.5 of Gottschalk's thesis, available for download here: http://www.cs.unc.edu/~geom/theses/gottschalk/main.pdf Christer Ericson http://realtimecollisiondetection.net/ 
From: Gino van den Bergen <gvandenbergen@pl...>  20051122 22:35:39
Attachments:
Message as HTML

I guess Erin and Christer are right about this case. False negatives = seem to occur for SATs, so this was a bad call from my side (*blush*). = The point still stands that you should not use absolute epsilons. = Gottshalk's fix adds an epsilon to the matrix values (before = multiplication) not to the terms of the inequality. =20 Gino van den Bergen http://www.dtecta.com Original Message From: gdalgorithmslistadmin@... on behalf of = christer_ericson@... Sent: Tue 11/22/2005 8:17 PM To: gdalgorithmslist@... Cc:=09 Subject: RE: [Algorithms] Prism problems... Gino van den Bergen wrote: > In general, a pure finiteprecision SAT may return false positives, > but never false negatives. Using epsilons only makes its behavior > worse (more false positives). Erin Catto already pointed out that this is not correct, but I thought I'd also disagree. In fact, I'd argue the exact opposite: you *need* epsilons to avoid false negatives. For a realworld example of a false negative see section 4.5 of Gottschalk's thesis, available for download here: http://www.cs.unc.edu/~geom/theses/gottschalk/main.pdf Christer Ericson http://realtimecollisiondetection.net/  This SF.Net email is sponsored by the JBoss Inc. Get Certified Today Register for a JBoss Training Course. Free Certification Exam for All Training Attendees Through End of 2005. For more info visit: http://ads.osdn.com/?ad_id=3D7628&alloc_id=3D16845&op=3Dclick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Jim Offerman <jofferman@ni...>  20051123 15:44:33

Hi guys, We're using linearz (as described here: http://www.mvps.org/directx/articles/linear_z/linearz.htm) to render our shadow maps. For reference, this is the shader code that is used to get linearz: float4 vPos = mul(Input.Pos,worldViewProj); vPos.z = vPos.z * vPos.w; Output.Pos = vPos; (additionally, the projection matrix has been modified so that the farplane is scaled to 1) It works perfectly in most cases, but we're having some problems with large polygons being clipped away when they really shouldn't be... Using my (admittedly limited) mathbrain, I have deduced that the clipping problems arise when one or more of the transformed vertices have both z < 0 and w < 0. In those cases, the sign for z/w (normal 1/z) and z*w/w (linearz) are different: z/w > 0, whereas z*w/w < 0 In order to correct this, I changed the shader to use "vPos.z = vPos.z * abs(vPos.w)". Now, the signs match up again (z/w > 0 and z*abs(w)/w > 0) and the polygons are no longer clipped away. So far so good, but is this mathematically correct? Any chance of this hackery upsetting the clipper completely (thus accepting *all* polygons)? If anyone of you math wizzards could shed some light on this, that would be greatly appreciated! thx, Jim.  Jim Offerman Nixxes Software http://www.nixxes.com / http://www.jimofferman.nl 
From: Pierre Terdiman <pierre.terdiman@no...>  20051130 14:57:12

We also found realworld examples where not using epsilons produced false negatives. Here is one: http://www.codercorner.com/CorrectBoxBoxOverlap.htm  Pierre  Original Message  From: "Gino van den Bergen" <gvandenbergen@...> To: <gdalgorithmslist@...> Sent: Tuesday, November 22, 2005 23:35 Subject: RE: [Algorithms] Prism problems... I guess Erin and Christer are right about this case. False negatives seem to occur for SATs, so this was a bad call from my side (*blush*). The point still stands that you should not use absolute epsilons. Gottshalk's fix adds an epsilon to the matrix values (before multiplication) not to the terms of the inequality. Gino van den Bergen http://www.dtecta.com Original Message From: gdalgorithmslistadmin@... on behalf of christer_ericson@... Sent: Tue 11/22/2005 8:17 PM To: gdalgorithmslist@... Cc: Subject: RE: [Algorithms] Prism problems... Gino van den Bergen wrote: > In general, a pure finiteprecision SAT may return false positives, > but never false negatives. Using epsilons only makes its behavior > worse (more false positives). Erin Catto already pointed out that this is not correct, but I thought I'd also disagree. In fact, I'd argue the exact opposite: you *need* epsilons to avoid false negatives. For a realworld example of a false negative see section 4.5 of Gottschalk's thesis, available for download here: http://www.cs.unc.edu/~geom/theses/gottschalk/main.pdf Christer Ericson http://realtimecollisiondetection.net/  This SF.Net email is sponsored by the JBoss Inc. Get Certified Today Register for a JBoss Training Course. Free Certification Exam for All Training Attendees Through End of 2005. For more info visit: http://ads.osdn.com/?ad_id=7628&alloc_id=16845&op=click _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Gino van den Bergen <gvandenbergen@pl...>  20051130 15:11:09

Thanks Piere! And I have found another reason why not to test the edgeedge cases in an oriented box test when doing culling. (Besides the fact that they make my AABBtree test slower and can not be used when transformations contain nonuniform scalings.)=20 Gino Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Pierre Terdiman Sent: Wednesday, November 30, 2005 3:57 PM To: gdalgorithmslist@... Subject: Re: [Algorithms] Prism problems... We also found realworld examples where not using epsilons produced false negatives. Here is one: http://www.codercorner.com/CorrectBoxBoxOverlap.htm  Pierre  Original Message =20 From: "Gino van den Bergen" <gvandenbergen@...> To: <gdalgorithmslist@...> Sent: Tuesday, November 22, 2005 23:35 Subject: RE: [Algorithms] Prism problems... I guess Erin and Christer are right about this case. False negatives seem to occur for SATs, so this was a bad call from my side (*blush*). The point still stands that you should not use absolute epsilons. Gottshalk's fix adds an epsilon to the matrix values (before multiplication) not to the terms of the inequality. Gino van den Bergen http://www.dtecta.com Original Message From: gdalgorithmslistadmin@... on behalf of christer_ericson@... Sent: Tue 11/22/2005 8:17 PM To: gdalgorithmslist@... Cc: Subject: RE: [Algorithms] Prism problems... Gino van den Bergen wrote: > In general, a pure finiteprecision SAT may return false positives, > but never false negatives. Using epsilons only makes its behavior > worse (more false positives). Erin Catto already pointed out that this is not correct, but I thought I'd also disagree. In fact, I'd argue the exact opposite: you *need* epsilons to avoid false negatives. For a realworld example of a false negative see section 4.5 of Gottschalk's thesis, available for download here: http://www.cs.unc.edu/~geom/theses/gottschalk/main.pdf Christer Ericson http://realtimecollisiondetection.net/  This SF.Net email is sponsored by the JBoss Inc. Get Certified Today Register for a JBoss Training Course. Free Certification Exam for All Training Attendees Through End of 2005. For more info visit: http://ads.osdn.com/?ad_id=3D7628&alloc_id=3D16845&op=3Dclick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188  This SF.net email is sponsored by: Splunk Inc. Do you grep through log files for problems? Stop! Download the new AJAX search engine that makes searching your log files as easy as surfing the web. DOWNLOAD SPLUNK! http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 