You can subscribe to this list here.
2000 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}
(390) 
_{Aug}
(767) 
_{Sep}
(940) 
_{Oct}
(964) 
_{Nov}
(819) 
_{Dec}
(762) 

2001 
_{Jan}
(680) 
_{Feb}
(1075) 
_{Mar}
(954) 
_{Apr}
(595) 
_{May}
(725) 
_{Jun}
(868) 
_{Jul}
(678) 
_{Aug}
(785) 
_{Sep}
(410) 
_{Oct}
(395) 
_{Nov}
(374) 
_{Dec}
(419) 
2002 
_{Jan}
(699) 
_{Feb}
(501) 
_{Mar}
(311) 
_{Apr}
(334) 
_{May}
(501) 
_{Jun}
(507) 
_{Jul}
(441) 
_{Aug}
(395) 
_{Sep}
(540) 
_{Oct}
(416) 
_{Nov}
(369) 
_{Dec}
(373) 
2003 
_{Jan}
(514) 
_{Feb}
(488) 
_{Mar}
(396) 
_{Apr}
(624) 
_{May}
(590) 
_{Jun}
(562) 
_{Jul}
(546) 
_{Aug}
(463) 
_{Sep}
(389) 
_{Oct}
(399) 
_{Nov}
(333) 
_{Dec}
(449) 
2004 
_{Jan}
(317) 
_{Feb}
(395) 
_{Mar}
(136) 
_{Apr}
(338) 
_{May}
(488) 
_{Jun}
(306) 
_{Jul}
(266) 
_{Aug}
(424) 
_{Sep}
(502) 
_{Oct}
(170) 
_{Nov}
(170) 
_{Dec}
(134) 
2005 
_{Jan}
(249) 
_{Feb}
(109) 
_{Mar}
(119) 
_{Apr}
(282) 
_{May}
(82) 
_{Jun}
(113) 
_{Jul}
(56) 
_{Aug}
(160) 
_{Sep}
(89) 
_{Oct}
(98) 
_{Nov}
(237) 
_{Dec}
(297) 
2006 
_{Jan}
(151) 
_{Feb}
(250) 
_{Mar}
(222) 
_{Apr}
(147) 
_{May}
(266) 
_{Jun}
(313) 
_{Jul}
(367) 
_{Aug}
(135) 
_{Sep}
(108) 
_{Oct}
(110) 
_{Nov}
(220) 
_{Dec}
(47) 
2007 
_{Jan}
(133) 
_{Feb}
(144) 
_{Mar}
(247) 
_{Apr}
(191) 
_{May}
(191) 
_{Jun}
(171) 
_{Jul}
(160) 
_{Aug}
(51) 
_{Sep}
(125) 
_{Oct}
(115) 
_{Nov}
(78) 
_{Dec}
(67) 
2008 
_{Jan}
(165) 
_{Feb}
(37) 
_{Mar}
(130) 
_{Apr}
(111) 
_{May}
(91) 
_{Jun}
(142) 
_{Jul}
(54) 
_{Aug}
(104) 
_{Sep}
(89) 
_{Oct}
(87) 
_{Nov}
(44) 
_{Dec}
(54) 
2009 
_{Jan}
(283) 
_{Feb}
(113) 
_{Mar}
(154) 
_{Apr}
(395) 
_{May}
(62) 
_{Jun}
(48) 
_{Jul}
(52) 
_{Aug}
(54) 
_{Sep}
(131) 
_{Oct}
(29) 
_{Nov}
(32) 
_{Dec}
(37) 
2010 
_{Jan}
(34) 
_{Feb}
(36) 
_{Mar}
(40) 
_{Apr}
(23) 
_{May}
(38) 
_{Jun}
(34) 
_{Jul}
(36) 
_{Aug}
(27) 
_{Sep}
(9) 
_{Oct}
(18) 
_{Nov}
(25) 
_{Dec}

2011 
_{Jan}
(1) 
_{Feb}
(14) 
_{Mar}
(1) 
_{Apr}
(5) 
_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}
(37) 
_{Sep}
(6) 
_{Oct}
(2) 
_{Nov}

_{Dec}

2012 
_{Jan}

_{Feb}
(7) 
_{Mar}

_{Apr}
(4) 
_{May}

_{Jun}
(3) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(10) 
2013 
_{Jan}

_{Feb}
(1) 
_{Mar}
(7) 
_{Apr}
(2) 
_{May}

_{Jun}

_{Jul}
(9) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2014 
_{Jan}
(14) 
_{Feb}

_{Mar}
(2) 
_{Apr}

_{May}
(10) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}
(3) 
_{Dec}

2015 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}
(12) 
_{Nov}

_{Dec}

S  M  T  W  T  F  S 



1
(13) 
2
(18) 
3
(11) 
4
(11) 
5

6

7
(5) 
8
(11) 
9
(1) 
10
(1) 
11
(4) 
12
(1) 
13
(1) 
14
(8) 
15
(4) 
16
(2) 
17
(22) 
18
(13) 
19
(3) 
20

21
(9) 
22
(9) 
23
(6) 
24
(16) 
25
(8) 
26

27

28
(4) 
29
(38) 
30
(18) 



From: Gino van den Bergen <gvandenbergen@pl...>  20051122 22:35:39

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: James Levick <james@in...>  20051122 20:21:56

Just to clarify, changing the test as you have below will make it less robust (as you discovered), what I had in mind was if (t > tolerance) positive++; else if (t < tolerance) negative++; The tolerance value should be computed such that it is appropriate to the computation, not just an absolute epsilon as the others have pointed out. This is the equivalent step in Eberly's algorithm to Erin's separation computation for boxbox. As Erin pointed out this can conceivably in the rare case result in false positives however this is probably preferable for your navmesh generation. James Diogo de Andrade wrote: > Yes, that's what I did, sorry, got mixed up... :) > I already do a more robust test for > > 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 > > > 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 > return false on the two earlier tests with continue, you will need to > keep the side0*side1 < 0 test. That is, change the algorithm to: > > for each pair of edges > { > int side0 = WhichSide(C0.V,D,C0.E(i).vertex); > if ( side0 == 0 ) > continue; // not return false > > int side1 = WhichSide(C1.V,D,C0.E(i).vertex); > if ( side1 == 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 > cannot separate the two polyhedra (though the second test doesn't save > much). > > If you are still having problems, I would suggest it might come down to > issues with numerical robustness. The definition of the WhichSide > function given in the document is not very robust for points close to > 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 > is going to lie directly on the potential separating plane due to the > way the algorithm works, and any numerical error could cause this axis > 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=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 > > > > > >  > 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: <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: 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: 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 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: Gino van den Bergen <gvandenbergen@pl...>  20051122 15:44:06

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: Diogo de Andrade <diogo.andrade@ne...>  20051122 13:16:31

Yes, that's what I did, sorry, got mixed up... :) I already do a more robust test for 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 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 return false on the two earlier tests with continue, you will need to keep the side0*side1 < 0 test. That is, change the algorithm to: for each pair of edges { int side0 = WhichSide(C0.V,D,C0.E(i).vertex); if ( side0 == 0 ) continue; // not return false int side1 = WhichSide(C1.V,D,C0.E(i).vertex); if ( side1 == 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 cannot separate the two polyhedra (though the second test doesn't save much). If you are still having problems, I would suggest it might come down to issues with numerical robustness. The definition of the WhichSide function given in the document is not very robust for points close to 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 is going to lie directly on the potential separating plane due to the way the algorithm works, and any numerical error could cause this axis 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=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: Greg Hjelstrom <ghjelstrom@lv...>  20051122 04:44:53

The way I debugged our SAT tests at my last job was to code two versions of the functions. One which used a very simple but overly slow method of doing all of the tests and then the optimized version with all of the redundant computations worked out etc. Then I just compared the results from both. Greg Hjelstrom > gdalgorithmslistadmin@... wrote on 21/11/2005 > 12:10:21: > > >> As far as I understand it, it should be the same, since I would obtain >> the reversed vector, that for the purposes of SAT tests should be >> basically the same... But I'll try it... >> > > You might be right... > > Quite difficult to debug SAT, theres nothing visually you can do to see > where things have gone wrong. This is why i like the minkoski difference > approach  you can draw the MD and its obvious when you have made a > mistake because the MD isn't a closed hull. > > I'm not suggesting that you move to a MD approach, just waxing lyrical, > really... > > Anyone know a nice way to debug SAT? > > Ta, Paul. > > ********************************************************************** > This email and any files transmitted with it are confidential and > intended solely for the use of the individual or entity to whom they > are addressed. If you have received this email in error please notify > postmaster@... > > This footnote also confirms that this email message has been checked > for all known viruses. > > ********************************************************************** > Sony Computer Entertainment Europe > > > >  > 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 > > 