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
(11) 
2
(24) 
3
(9) 
4
(15) 
5
(2) 
6
(12) 
7
(42) 
8
(19) 
9
(35) 
10
(18) 
11
(6) 
12
(2) 
13
(10) 
14
(14) 
15
(49) 
16
(8) 
17

18
(4) 
19
(2) 
20
(6) 
21
(39) 
22
(19) 
23
(21) 
24
(32) 
25
(10) 
26
(11) 
27
(29) 
28
(28) 
29
(2) 
30
(4) 
31
(18) 

From: Charles Bloom <cbloom@cb...>  20020531 23:40:38

I've found that there are some interesting approximations to separating axis. If all you want to know is a boolean : A) they're definitely not intersecting B) they may or may not be Then you can use whatever axes you want, and as many or few as you want. In particular, for OBBOBB , you can test just the axis between their two centers. In typical cases, I've found this to be correct 90% of the time (that is, only on 10% of the cases did I return "B" when I could have returned "A"). At 03:19 PM 5/31/2002 0700, christer_ericson@... wrote: >Igor Kravtchenko wrote: > >[...] > >What is the problem to take the plane of each boxe's face > >and test to have all the points on the same side. It requires > >a maximum of 2 * 6 = 12 tests with just a serie of trivial dot > >products. However, I suppose the SAT has a great advantage but > >I have to admit it doesn't thunder me... > >Because that test (testing to see if the other box is fully >outside one face of the other) won't detect all cases when the >boxes are nonintersecting. > >There are configurations when the boxes are almost touching >edge to edge with the edges meeting at an X where neither box >is fully outside a face of the other, yet they don't intersect. > >In fact, these configurations correspond exactly to those >covered by the 9 extra tests of the separating axis test (the >cross product axes). > >In other words, the test you're suggesting is just the first >6 (face) tests of the separating axis test. They're required >to find nonintersection, but they are not sufficient. > > >Christer Ericson >Sony Computer Entertainment, Santa Monica > > >_______________________________________________________________ > >Don't miss the 2002 Sprint PCS Application Developer's Conference >August 2528 in Las Vegas  http://devcon.sprintpcs.com/adp/index.cfm > >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=6188  Charles Bloom cbloom@... http://www.cbloom.com 
From: <christer_ericson@pl...>  20020531 23:27:56

Igor Kravtchenko wrote: >for a pass of only 6 tests it's true that it could return >an intersection case whereas it's not. However, with a >pass of 12 tests (A>B and then B>A), it seems to me to >be solved. I'm searching on paper a case where it wouldn't >be true. I'm afraid you misunderstood what I wrote. The 6 axis tests I'm referring to are the same as the 12 tests you're talking about. Each axis test, of the first six separating axis tests, amounts to testing whether the other box is outside the two faces of this box perpendicular to the current axis. So the case I outlined of two boxes approaching contact transversely edge to edge *is* a counterexample of what you're saying. >It's maybe bigger than a nose in the center of a face, >but well... :) No, it's like Michael Jackson's nose: phoney and doesn't work. Christer Ericson Sony Computer Entertainment, Santa Monica 
From: LtJ<ax@t...>  20020531 23:15:34

I have my world as a 2.5D quadtree now ( 2D quadtree with 3d AABBs). Now I want to have objects in there and reuse the hierachie for culling them. My problem is the case when an object crosses the edges of an AABB node. I thought I could just store it one level higher in the hierachie, but that would make the whole thing very ineffective for objects that cross the major axes. I presume this problem isn't new.. any suggestions or pointers to something that might help me? Thanx in advance, Marius Elvert 
From: Ron Levine <ron@do...>  20020531 23:13:34

On Fri, 31 May 2002 15:31:39 0700, you wrote: >It's not entirely true that the boxes have to be close together in order for >the 6axis test to detect a collision erroneously  two long thin boxes of >length L can be separated by a distance of slightly less than L / sqrt(2) >and still be detected as colliding when using only 6 separating axes >(imagine the two boxes on opposing edges of a tetrahedron, turned 45 degrees >along the axes of the tetrahedron edges, and then pushed together until >they're a bit less than L / sqrt(2) apart). > Right, I shouldn't have said "always" without further qualfication on the shapes of the boxes. In the experience I described the boxes were bounding boxes of cars, not needles. Thanks, Ron >Austin Appleby >aappleby@... > > > >Original Message >From: Ron Levine [mailto:ron@...] >Sent: Friday, May 31, 2002 5:04 PM >To: Igor Kravtchenko >Cc: gdalgorithmslist@... >Subject: Re: [Algorithms] separating axis > > >On Fri, 31 May 2002 23:27:39 +0200, you wrote: > >> >>There is something I don't get with the SAT. It tolds that if we can found >an axis for which the projected >>boxes don't overlap then the boxes don't indeed collide. That would >represent 15 potentials axis to test for. >>However, at first glance, it doesn't seem to me very interesting in a term >of cpu time consumption. What is the >>problem to take the plane of each boxe's face and test to have all the >points on the same side. It requires a >>maximum of 2 * 6 = 12 tests with just a serie of trivial dot products. >However, I suppose the SAT has a great >>advantage but I have to admit it doesn't thunder me... >> > >First let's point out that your first statement ("It tolds that if we >can found an axis for which the projected boxes don't overlap then the >boxes don't indeed collide") is not the part of the theorem that is >most relevant to your question. Indeed, as soon as you find just one >axis on which the projected boxes are separated, you are done, for you >know that the boxes cannot intersect in space. That is the trivial >part of the theorem. (And in many game situations, you can increase >the efficiency by cleverly ordering the axes for testing, to maximize >the frequency of "early outs"). > >The meat of the theorem is in the other partif the projected boxes >do overlap on all 15 axes then you know that the 3D boxes intersect in >space. THAT is the powerful part of the theorem. THAT is what should >thunder you. > >Now you are asking is it not enough to test just the axes >perpendicular to the faces of the boxes (up to six at most). That is, >if the projected boxes overlap on the six face axes, can we conclude >that the 3D boxes intersect? > >The answer is NO, but ALMOST YES. Namely, it is quite possible that >the projections overlap on all six face axes but still the boxes are >separated in space. However, when this happens the two boxes will >always be very close to colliding, that is, close in comparison to >their own dimensions, so close that you can treat them as colliding >for all practical purposes in game situations. In fact, that is >exactly how I have implemented the SAT for collisions of oriented >boxes in published games, using only the six face axes for an >approximate collision test, rather than the fifteen axes needed for an >exact collision test. This approximation has worked quite well. > >You can see the phenomenon I am describing by holding a pair of >rectangular boxes in your two hands and trying to place them so that >they overlap on all six face axes without colliding. You will find >that it is possible, but only when the two boxes are very close >together > > > >_______________________________________________________________ > >Don't miss the 2002 Sprint PCS Application Developer's Conference >August 2528 in Las Vegas  http://devcon.sprintpcs.com/adp/index.cfm > >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Igor Kravtchenko <igor@ob...>  20020531 22:57:01

Christer, for a pass of only 6 tests it's true that it could return an intersection case whereas it's not. However, with a pass of 12 tests (A>B and then B>A), it seems to me to be solved. I'm searching on paper a case where it wouldn't be true. It's maybe bigger than a nose in the center of a face, but well... :) Igor.  Original Message  From: <christer_ericson@...> To: "Igor Kravtchenko" <igor@...>; <gdalgorithmslist@...> Sent: Saturday, June 01, 2002 12:19 AM Subject: Re: [Algorithms] separating axis > > Igor Kravtchenko wrote: > >[...] > >What is the problem to take the plane of each boxe's face > >and test to have all the points on the same side. It requires > >a maximum of 2 * 6 = 12 tests with just a serie of trivial dot > >products. However, I suppose the SAT has a great advantage but > >I have to admit it doesn't thunder me... > > Because that test (testing to see if the other box is fully > outside one face of the other) won't detect all cases when the > boxes are nonintersecting. > > There are configurations when the boxes are almost touching > edge to edge with the edges meeting at an X where neither box > is fully outside a face of the other, yet they don't intersect. > > In fact, these configurations correspond exactly to those > covered by the 9 extra tests of the separating axis test (the > cross product axes). > > In other words, the test you're suggesting is just the first > 6 (face) tests of the separating axis test. They're required > to find nonintersection, but they are not sufficient. > > > Christer Ericson > Sony Computer Entertainment, Santa Monica > > > _______________________________________________________________ > > Don't miss the 2002 Sprint PCS Application Developer's Conference > August 2528 in Las Vegas  http://devcon.sprintpcs.com/adp/index.cfm > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 
From: Igor Kravtchenko <igor@ob...>  20020531 22:46:15

Ron, > First let's point out that your first statement ("It tolds that if we > can found an axis for which the projected boxes don't overlap then the > boxes don't indeed collide") is not the part of the theorem that is > most relevant to your question. Indeed, as soon as you find just one > axis on which the projected boxes are separated, you are done, for you > know that the boxes cannot intersect in space. That is the trivial > part of the theorem. (And in many game situations, you can increase > the efficiency by cleverly ordering the axes for testing, to maximize > the frequency of "early outs"). > The meat of the theorem is in the other partif the projected boxes > do overlap on all 15 axes then you know that the 3D boxes intersect in > space. THAT is the powerful part of the theorem. THAT is what should > thunder you. Yes, you stop as soon as a test returned TRUE. I was aware of that but anyway, another method like the planes' test also return as soon as TRUE is returned to inform there is no intersection. So anyway, that's a 1 to 1 score for both algorithms (SAT and boxes' planes). > Now you are asking is it not enough to test just the axes > perpendicular to the faces of the boxes (up to six at most). That is, > if the projected boxes overlap on the six face axes, can we conclude > that the 3D boxes intersect? > The answer is NO, but ALMOST YES. Namely, it is quite possible that > the projections overlap on all six face axes but still the boxes are > separated in space. However, when this happens the two boxes will > always be very close to colliding, that is, close in comparison to > their own dimensions, so close that you can treat them as colliding > for all practical purposes in game situations. In fact, that is > exactly how I have implemented the SAT for collisions of oriented > boxes in published games, using only the six face axes for an > approximate collision test, rather than the fifteen axes needed for an > exact collision test. This approximation has worked quite well. > You can see the phenomenon I am describing by holding a pair of > rectangular boxes in your two hands and trying to place them so that > they overlap on all six face axes without colliding. You will find > that it is possible, but only when the two boxes are very close > together I'm not sure to understand or we maybe don't take exactly about the same thing. When I make reference to the boxes' planes, I didn't said to use any axis to make a "first approximation". In fact, there are no axis at all. We take one plane and test if all the points of the other box are in the positive side (by admitting our normals are ofcourse properly oriented). If all the points are positive, we can immediatly return TRUE to inform the two boxes don't intersect. Because an OOB is convex, I don't see any possible failure to such "assumption". Once you have done with one box, you then pass to the second and start again to manage "embedded" cases (if you see what I mean). If after all of this, there aren't any case where all points are positive from a plane, the two OOBs don't intersect. That makes a maximum of 12 tests (not only 6) with 8 dot products per test. Izidor. 
From: <christer_ericson@pl...>  20020531 22:19:55

Igor Kravtchenko wrote: >[...] >What is the problem to take the plane of each boxe's face >and test to have all the points on the same side. It requires >a maximum of 2 * 6 = 12 tests with just a serie of trivial dot >products. However, I suppose the SAT has a great advantage but >I have to admit it doesn't thunder me... Because that test (testing to see if the other box is fully outside one face of the other) won't detect all cases when the boxes are nonintersecting. There are configurations when the boxes are almost touching edge to edge with the edges meeting at an X where neither box is fully outside a face of the other, yet they don't intersect. In fact, these configurations correspond exactly to those covered by the 9 extra tests of the separating axis test (the cross product axes). In other words, the test you're suggesting is just the first 6 (face) tests of the separating axis test. They're required to find nonintersection, but they are not sufficient. Christer Ericson Sony Computer Entertainment, Santa Monica 
From: Ron Levine <ron@do...>  20020531 22:05:56

On Fri, 31 May 2002 23:27:39 +0200, you wrote: > >There is something I don't get with the SAT. It tolds that if we can found an axis for which the projected >boxes don't overlap then the boxes don't indeed collide. That would represent 15 potentials axis to test for. >However, at first glance, it doesn't seem to me very interesting in a term of cpu time consumption. What is the >problem to take the plane of each boxe's face and test to have all the points on the same side. It requires a >maximum of 2 * 6 = 12 tests with just a serie of trivial dot products. However, I suppose the SAT has a great >advantage but I have to admit it doesn't thunder me... > First let's point out that your first statement ("It tolds that if we can found an axis for which the projected boxes don't overlap then the boxes don't indeed collide") is not the part of the theorem that is most relevant to your question. Indeed, as soon as you find just one axis on which the projected boxes are separated, you are done, for you know that the boxes cannot intersect in space. That is the trivial part of the theorem. (And in many game situations, you can increase the efficiency by cleverly ordering the axes for testing, to maximize the frequency of "early outs"). The meat of the theorem is in the other partif the projected boxes do overlap on all 15 axes then you know that the 3D boxes intersect in space. THAT is the powerful part of the theorem. THAT is what should thunder you. Now you are asking is it not enough to test just the axes perpendicular to the faces of the boxes (up to six at most). That is, if the projected boxes overlap on the six face axes, can we conclude that the 3D boxes intersect? The answer is NO, but ALMOST YES. Namely, it is quite possible that the projections overlap on all six face axes but still the boxes are separated in space. However, when this happens the two boxes will always be very close to colliding, that is, close in comparison to their own dimensions, so close that you can treat them as colliding for all practical purposes in game situations. In fact, that is exactly how I have implemented the SAT for collisions of oriented boxes in published games, using only the six face axes for an approximate collision test, rather than the fifteen axes needed for an exact collision test. This approximation has worked quite well. You can see the phenomenon I am describing by holding a pair of rectangular boxes in your two hands and trying to place them so that they overlap on all six face axes without colliding. You will find that it is possible, but only when the two boxes are very close together 
From: Igor Kravtchenko <igor@ob...>  20020531 21:29:53

There is something I don't get with the SAT. It tolds that if we can found an axis for which the projected boxes don't overlap then the boxes don't indeed collide. That would represent 15 potentials axis to test for. However, at first glance, it doesn't seem to me very interesting in a term of cpu time consumption. What is the problem to take the plane of each boxe's face and test to have all the points on the same side. It requires a maximum of 2 * 6 = 12 tests with just a serie of trivial dot products. However, I suppose the SAT has a great advantage but I have to admit it doesn't thunder me... Izidor. 
From: Ville Miettinen <wili@hy...>  20020531 20:48:22

Using xor reg,reg is a good idea (code size optimization); however, if you had read the code in question, you would have noticed that the next instruction is addwithcarry; therefore xor cannot be used (we cannot modify the carry register)  mov does not change flags. cheers, wili On Fri, 31 May 2002, Jon Watte wrote: > > The problem with this piece of assembly is that it will predict poorly > and it has lots of zerolatency dependencies. It'll basically end up > serializing the execution of the CPU. If your data is in cache (which > is likely for the next two load sets after you've completed the first > load set) then it's possibly faster to just always do all of them and > merge them using nonbranching logic such as CMOV and/or SETL and/or a > simple unsigned shift by 31 bits after oring the results together (the > last is slow on P4, though :( ). You could even keep using ADC to add > to the return register, if you're OK with returning 2 or 3 if all three > test smaller, although this consumes one nonvolatile register. > > Oh, and I always use XOR EAX,EAX to clear the register. Dunno that it's > really any faster than MOV these days, though; it was a good way of > preventing partial register stalls in the distant past of 1998 or so... > > Cheers, > > / h+ > > > > Just a quick thought: I'm no x86 assembler guru (as a oldschool console > > developer, I've tried to stay away from it wherever possible), but in the > > order() routine you posted, is it really necessary to do all three > > subtracts? Might the following execute fractionally quicker: > > > > mov ecx,a > > mov edx,b > > mov eax,[ecx+0] > > cmp eax,[edx+0] > > jnz,@exit // if we have a definitive result here, finish now > > mov eax,[ecx+4] > > cmp eax,[edx+4] > > jnz,@exit // if we have a definitove result here, finish now > > mov eax,[ecx+8] > > cmp eax,[edx+8] > > @exit > > mov eax,0 > > adc eax,0 // return value in eax > > 
From: <castanyo@ya...>  20020531 18:00:02

Jon Watte wrote: > Oh, and I always use XOR EAX,EAX to clear the register. Dunno that it's > really any faster than MOV these days, though; it was a good way of > preventing partial register stalls in the distant past of 1998 or so... In these days that doesn't help the register allocator of the cpu, that doesn't know that eax has been cleared. So, it could be using a new register and is waiting for eax to be freed. Note, that internal cpu registers don't match the x86 registers (there are much more), and can even be asigned to memory addresses. Ignacio Castaño castanyo@... _________________________________________________________ Do You Yahoo!? Get your free @yahoo.com address at http://mail.yahoo.com 
From: Jon Watte <hplus@mi...>  20020531 17:25:09

The problem with this piece of assembly is that it will predict poorly and it has lots of zerolatency dependencies. It'll basically end up serializing the execution of the CPU. If your data is in cache (which is likely for the next two load sets after you've completed the first load set) then it's possibly faster to just always do all of them and merge them using nonbranching logic such as CMOV and/or SETL and/or a simple unsigned shift by 31 bits after oring the results together (the last is slow on P4, though :( ). You could even keep using ADC to add to the return register, if you're OK with returning 2 or 3 if all three test smaller, although this consumes one nonvolatile register. Oh, and I always use XOR EAX,EAX to clear the register. Dunno that it's really any faster than MOV these days, though; it was a good way of preventing partial register stalls in the distant past of 1998 or so... Cheers, / h+ > Just a quick thought: I'm no x86 assembler guru (as a oldschool console > developer, I've tried to stay away from it wherever possible), but in the > order() routine you posted, is it really necessary to do all three > subtracts? Might the following execute fractionally quicker: > > mov ecx,a > mov edx,b > mov eax,[ecx+0] > cmp eax,[edx+0] > jnz,@exit // if we have a definitive result here, finish now > mov eax,[ecx+4] > cmp eax,[edx+4] > jnz,@exit // if we have a definitove result here, finish now > mov eax,[ecx+8] > cmp eax,[edx+8] > @exit > mov eax,0 > adc eax,0 // return value in eax 
From: Nick Pelling <NP<elling@cl...>  20020531 12:06:22

Hi Wili, One last insane suggestion. :) If your world geometry is made up purely of static triangles (and = you're not storing the plane equation), then you ~could~ preprocess all the xcoordinates in the world so that  across each edge  they were = different. :9 Thinking about it... if you're careful, the jitter involved might not = be too bad. All you have to make sure is that the xcoordinates of each = triangle are different, and that each change doesn't compromise any triangle = sharing a common edge. :9 This would also be portable between platforms. :) Cheers, .....Nick Pelling..... PS: I know you don't actually need it, but it's quite fun. :) Original Message From: Ville Miettinen [mailto:wili@...] Sent: 31 May 2002 10:46 To: gdalgorithmslist@... Subject: [Algorithms] RE: [Algorithms] RE: [Algorithms] RE: = [Algorithms] RE: [Algorithms] M=F6llerTrumbore ray/triangle intersection code For truly random data the jnzvariant is slightly faster (misprediction chance is 1/(2^32), i.e. ~0%). For "reallife" data (such as Quake levels), it is slower than the nonbranching variants, as there are so many axisaligned edges in the world (causing a[0] =3D=3D b[0] or a[1] =3D=3D b[1]). i 
From: Nick Pelling <NP<elling@cl...>  20020531 10:22:53

Hi Wili, Have you tried caching edgetests? class vert { public: float x; float y; float z; }; class edge { public: vert * v1; vert * v2; uint32 edge_id; }; class triangle { public: edge * e1; edge * e2; edge * e3; bool flip_e1; bool flip_e2; bool flip_e3; }; You'd then cache the (last_ray_id, edge_id, result) 3tuple in your local thread (perhaps hashing it simply), etc. YGTGI. :) [*] Cheers, ....Nick Pelling.... [*] "you get the general idea" :) 
From: Ville Miettinen <wili@hy...>  20020531 09:46:28

=46or truly random data the jnzvariant is slightly faster (mispredicti= on chance is 1/(2^32), i.e. ~0%). For "reallife" data (such as Quake levels), it is slower than the nonbranching variants, as there are so many axisaligned edges in the world (causing a[0] =3D=3D b[0] or a[1] =3D=3D b[1]). Because the axis varies (floors,= walls) and there are also nonaligned surfaces, one does indeed get an almost 50% misprediction rate. The difference between the truly random and "real= life" sets is ~10 cycles on a P3 (more on a P4). This was confirmed with a s= mall test program that timed both routines under varying conditions and by measuring the branch probabilities with VTune. The timing of the nonbranching variant was, of course, independent of the input data. cheers, wili  o Ville Miettinen, Lead Programmer o Hybrid Graphics, Ltd. o Email: wili@... o Web: http://www.hybrid.fi Original Message =46rom: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Nick Pelling Sent: Friday, May 31, 2002 12:30 To: gdalgorithmslist@... Subject: [Algorithms] RE: [Algorithms] RE: [Algorithms] RE: [Algorithms= ] M=F6llerTrumbore ray/triangle intersection code 1. Note that the test I proposed is "jnz", which (on random data) shoul= d give a near100% prediction success rate. However, if your data is as degenerate as you make it sound, this would almost certainly slow your = code down. As always, YMMV. :/ 2. You can make this boolfriendly without too much difficulty: mov ecx,a mov edx,b mov eax,[ecx+0] sub eax,[edx+0] jnz,@exit // if we have a definitive result here, finish now mov eax,[ecx+4] sub eax,[edx+4] jnz,@exit // if we have a definitove result here, finish now mov eax,[ecx+8] sub eax,[edx+8] @exit shr eax,31 // is this the unsigned shift? I never can remember x86. :( Cheers, .....Nick P..... Original Message =46rom: Ville Miettinen [mailto:wili@...] Sent: 31 May 2002 09:34 To: gdalgorithmslist@... Subject: [Algorithms] RE: [Algorithms] RE: [Algorithms] M=F6llerTrumbo= re ray/triangle intersection code 1. Well, you just introduced two conditional branches there (on a P4, a mispredicted branch can be 20+ cycles), thus slowing the routine down quite a bit. On x86 t= he main rule is to always always use arithmetic ops and to get rid of all branches.. This routine= is about the worstcase scenario for the branch predictor: the input vectors have 5050 random chances (in most cases) for each of the branches, and as they are unrelated (x and y components of = a vector are not tied to each other), this means that a branch predictor will mispredict ever= y other time. This means that each of the branch instructions take 10+ cycles. Avoiding the memory accesses is not useful, as this routine is used for sorting data that is subsequently (or just before it) processed; the data is either in L1 cache or is nee= ded to be in L1 cache (also, if you need to touch the first element, the two other dwords are extremely likely to recide on the same cache line). 2. When programming in C++, I like to use 'bool' instead of int.. And a= bool is always 0 or 1. By optimizing the single mov eax,0 away, you'll probably win one third of a cycle :).= =2E Also, the routine has a C++ implementation on different platforms, and in debug builds, I like to validate my asse= mbly code by executing it against the C++ version and comparing the results. Would be a bit boring to cripple the= C++ version to return 0/1. I do use the 0/1 notation quite a bit in other places, though.. conditional mov= es etc. are best implemented (in a portable way!) by generating a 0/1 mask, then computing d =3D (a= + (ba) & mask). cheers, wili _______________________________________________________________ Don't miss the 2002 Sprint PCS Application Developer's Conference August 2528 in Las Vegas  http://devcon.sprintpcs.com/adp/index.cfm _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Nick Pelling <NP<elling@cl...>  20020531 09:31:53

1. Note that the test I proposed is "jnz", which (on random data) = should give a near100% prediction success rate. However, if your data is as degenerate as you make it sound, this would almost certainly slow your = code down. As always, YMMV. :/ 2. You can make this boolfriendly without too much difficulty: mov ecx,a mov edx,b mov eax,[ecx+0] sub eax,[edx+0] jnz,@exit // if we have a definitive result here, finish now mov eax,[ecx+4] sub eax,[edx+4] jnz,@exit // if we have a definitove result here, finish now mov eax,[ecx+8] sub eax,[edx+8] @exit shr eax,31 // is this the unsigned shift? I never can remember x86. :( Cheers, .....Nick P..... Original Message From: Ville Miettinen [mailto:wili@...] Sent: 31 May 2002 09:34 To: gdalgorithmslist@... Subject: [Algorithms] RE: [Algorithms] RE: [Algorithms] = M=F6llerTrumbore ray/triangle intersection code 1. Well, you just introduced two conditional branches there (on a P4, a mispredicted branch can be 20+ cycles), thus slowing the routine down quite a bit. On x86 = the main rule is to always always use arithmetic ops and to get rid of all branches.. This routine = is about the worstcase scenario for the branch predictor: the input vectors have 5050 random chances (in most cases) for each of the branches, and as they are unrelated (x and y components of = a vector are not tied to each other), this means that a branch predictor will mispredict = every other time. This means that each of the branch instructions take 10+ cycles. Avoiding the memory accesses is not useful, as this routine is used for sorting data that is subsequently (or just before it) processed; the data is either in L1 cache or is = needed to be in L1 cache (also, if you need to touch the first element, the two other dwords are extremely likely to recide on the same cache line). 2. When programming in C++, I like to use 'bool' instead of int.. And a = bool is always 0 or 1. By optimizing the single mov eax,0 away, you'll probably win one third of a cycle = :).. Also, the routine has a C++ implementation on different platforms, and in debug builds, I like to validate my = assembly code by executing it against the C++ version and comparing the results. Would be a bit boring to cripple the = C++ version to return 0/1. I do use the 0/1 notation quite a bit in other places, though.. conditional = moves etc. are best implemented (in a portable way!) by generating a 0/1 mask, then computing d =3D (a = + (ba) & mask). cheers, wili 
From: Ville Miettinen <wili@hy...>  20020531 08:33:34

1. Well, you just introduced two conditional branches there (on a P4, a mispredicted branch can be 20+ cycles), thus slowing the routine down quite a bit. On x86 t= he main rule is to always always use arithmetic ops and to get rid of all branches.. This routine= is about the worstcase scenario for the branch predictor: the input vectors have 5050 random chances (in most cases) for each of the branches, and as they are unrelated (x and y components of = a vector are not tied to each other), this means that a branch predictor will mispredict ever= y other time. This means that each of the branch instructions take 10+ cycles. Avoiding the memory accesses is not useful, as this routine is used for sorting data that is subsequently (or just before it) processed; the data is either in L1 cache or is nee= ded to be in L1 cache (also, if you need to touch the first element, the two other dwords are extremely likely to recide on the same cache line). 2. When programming in C++, I like to use 'bool' instead of int.. And a= bool is always 0 or 1. By optimizing the single mov eax,0 away, you'll probably win one third of a cycle :).= =2E Also, the routine has a C++ implementation on different platforms, and in debug builds, I like to validate my asse= mbly code by executing it against the C++ version and comparing the results. Would be a bit boring to cripple the= C++ version to return 0/1. I do use the 0/1 notation quite a bit in other places, though.. conditional mov= es etc. are best implemented (in a portable way!) by generating a 0/1 mask, then computing d =3D (a= + (ba) & mask). cheers, wili  o Ville Miettinen, Lead Programmer o Hybrid Graphics, Ltd. o Email: wili@... o Web: http://www.hybrid.fi Original Message =46rom: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Nick Pelling Sent: Friday, May 31, 2002 11:15 To: 'Ville Miettinen'; gdalgorithmslist@... Subject: [Algorithms] RE: [Algorithms] M=F6llerTrumbore ray/triangle intersection code Hi Wili, Just a quick thought: I'm no x86 assembler guru (as a oldschool consol= e developer, I've tried to stay away from it wherever possible), but in t= he order() routine you posted, is it really necessary to do all three subtracts? Might the following execute fractionally quicker: mov ecx,a mov edx,b mov eax,[ecx+0] cmp eax,[edx+0] jnz,@exit // if we have a definitive result here, finish now mov eax,[ecx+4] cmp eax,[edx+4] jnz,@exit // if we have a definitove result here, finish now mov eax,[ecx+8] cmp eax,[edx+8] @exit mov eax,0 adc eax,0 // return value in eax Or a roughlysimilar C version: inline bool order(const uint32 a[3], const uint32 b[3]) { int h; if ((h =3D a[0]  b[0]) =3D=3D 0) if ((h =3D a[1]  b[1]) =3D=3D 0) h =3D a[2]  b[2]; return (h < 0); } =46inally: call me a cycle miser (I don't mind, it's true :)), but per= sonally I'd change the return value to (int) so that the last two instructions = could be collapsed into: @exit sbb eax,eax // consistently return 0 or 1 Cheers, .....Nick Pelling..... PS: consultancy fees to the normal address. :) _______________________________________________________________ Don't miss the 2002 Sprint PCS Application Developer's Conference August 2528 in Las Vegas  http://devcon.sprintpcs.com/adp/index.cfm _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Nick Pelling <NP<elling@cl...>  20020531 08:17:07

Hi Wili, Just a quick thought: I'm no x86 assembler guru (as a oldschool console developer, I've tried to stay away from it wherever possible), but in the order() routine you posted, is it really necessary to do all three subtracts? Might the following execute fractionally quicker: mov ecx,a mov edx,b mov eax,[ecx+0] cmp eax,[edx+0] jnz,@exit // if we have a definitive result here, finish now mov eax,[ecx+4] cmp eax,[edx+4] jnz,@exit // if we have a definitove result here, finish now mov eax,[ecx+8] cmp eax,[edx+8] @exit mov eax,0 adc eax,0 // return value in eax Or a roughlysimilar C version: inline bool order(const uint32 a[3], const uint32 b[3]) { int h; if ((h = a[0]  b[0]) == 0) if ((h = a[1]  b[1]) == 0) h = a[2]  b[2]; return (h < 0); } Finally: call me a cycle miser (I don't mind, it's true :)), but personally I'd change the return value to (int) so that the last two instructions could be collapsed into: @exit sbb eax,eax // consistently return 0 or 1 Cheers, .....Nick Pelling..... PS: consultancy fees to the normal address. :) 
From: Willmott, Andrew <AW<illmott@ma...>  20020530 23:19:28

Well, for starters, most surface simplification routines do this. You = build a multiresolution hierarchy by repeatedly collapsing edges, i.e., = merging vertices. This forms a hierarchy where for each subtree the = children are the original vertices, and the parent is the replacement = vertex. (In some cases this is one of the two original vertices, but = it's usually some "best fit" vertex derived from the original vertices.) = Any cut through this tree defines a model at a particular resolution. = See Hoppe's original multiresolution model paper, or pretty much any of = the multiresolution geometry papers.) Face clustering does something similar but with faces: it builds a = hierarchy bottomup by recursively clustering nearby groups of faces. = (See Garland/some other guy/Heckbert.) (These algorithms usually keep a list of potential mergers in a heap, = and iteratively pick the lowest cost merge and perform it, updating the = heap as necessary. So they're n log(n).) The GoldsmithSalmon algorithm for boundingvolume hierarchy = construction is another bottomup algorithm. Often referred to in = raytracing literature. Some hierarchical nested grid algorithms are = constructed bottomup. In general, topdown algorithms are easier to write, but bottomup ones = produce better quality hierarchies. (Think of the difference between = simplifying a model by vertex clustering  collapsing all vertices = within a subcell to a single vertex  and the more computeintensive = but higher quality Hoppe/Garland/Lindstrom methods.) You might try looking at the following paper: JeanMarc Hasenfratz, Cyrille Damez, Fran=C1ois Sillion, and George Drettakis. A practical analysis of clustering strategies for = hierarchical radiosity. Computer Graphics Forum, 18(3):221232, September 1999. which has a nice analysis of hierarchy building in radiosity algorithms, = including bottomup versus topdown algorithms. "The research is out there!" =3D) Cheers, Andrew > Original Message > From: Brian Marshall [mailto:Brian.Marshall@...] > Sent: Wednesday, May 29, 2002 1:20 AM > To: GdalgorithmsList (Email) > Subject: [Algorithms] BottomUp Tree Building >=20 >=20 > A while back, I experimented with bottom up tree building for=20 > collision > detection with some nice results. But it bugged me that I=20 > couldn't find much > in the way of research on this. >=20 > In fact, about the only resource I found was Wesley Hunt's work: > http://www.cs.unc.edu/~hunt/c290/project/ >=20 > Now, I'm looking into this again. Does anyone else have any=20 > links or ideas > for bottom up tree building. Not necessarily from collision =20 > I'm sure it's > been tried for other problems. It's just bugging me that=20 > there doesn't seem > to be much work on bottom up tree building anywhere! >=20 > Brian. >=20 >=20 >=20 > _______________________________________________________________ >=20 > Don't miss the 2002 Sprint PCS Application Developer's Conference > August 2528 in Las Vegas  http://devcon.sprintpcs.com/adp/index.cfm >=20 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 
From: Nick Pelling <NP<elling@cl...>  20020530 17:41:43

Hi everyone, It's not relevant to my current engine, but while doodling in my notepad just now, I wondered about the maths involved in handling colliding a moving sphere with a *rotating* triangle  ie, handling pivoting doors properly, etc. This is obviously similar to (though probably simpler than) Stephane Redon's screwing polytopoly continuous collision detection papers. He mentions "hierarchical englobing structures", so this is probably something he's thought about, if not actually coded. :) What struck me about this movingspherevsrotatingtriangle test is that it probably can (my guess!) be solved *exactly*, whereas Redon's solutions are lowprecision approximations. This seems like a really cool paper for someone to do... but has it already been written? [If so, I haven't seen it]. :/ Any pointers? Cheers, .....Nick Pelling...... 
From: Nick Pelling <NP<elling@cl...>  20020530 09:02:30

Cool  I'm glad you found an edgecentric solution with sufficient = precision for your needs. :) I hadn't seen the Shewchuk paper, that was a good = find, thanks for posting a link to it! :) Cheers, .....Nick Pelling.... Original Message From: Ville Miettinen [mailto:wili@...] Sent: 30 May 2002 09:35 To: 'Nick Pelling'; gdalgorithmslist@... Subject: Re: [Algorithms] M=F6llerTrumbore ray/triangle intersection = code Got the problem solved. Actually we have now two separate solutions. = The first one used three line segment vs. edge tests to find out whether = the line segment (ray) passes through the triangle. The trick was to sort = the vertices so that edges are always computed the same way, but the = results had different signs for edges (v0,v1) and (v1,v0). The code for getting a unique ordering (without branches) of two vertices is below. = This approach guaranteed that rays would not leak through connected meshes, = but still had some problems with rays almost parallel with the triangle's plane. The second (and better) solution was based on mr. Shewchuk's paper and original C source code (Jonathan Richard Shewchuk: Robust Adaptive FloatingPoint Geometric Predicates; code can be found from http://www.cs.cmu.edu/~quake/robust.html). He provides code for computing the (guaranteedly correct) sign of the = volume of a tetrahedron. Although there may be inaccuracies in the floatingpoint value representing the volume, its sign is always correct (and the return = value is 0.0f iff the volume is exactly zero). In the code below the function Predicate::orient3d() is this function. We use the "adaptive" version = of Shewchuk's function, i.e. it computes an approximation of the results, checks if = its error interval may cross zero (thus causing the sign to be incorrect) and = only in that case falls back to the more expensive code. The code is on average twice as slow as M=F6llerTrumbore, but in our = case we are very happy to pay the price. After all, if a routine doesn't need to = work, one can always make it arbitrarily fast :). cheers, wili 
From: Ville Miettinen <wili@hy...>  20020530 08:35:36

Got the problem solved. Actually we have now two separate solutions. Th= e first one used three line segment vs. edge tests to find out whether th= e line segment (ray) passes through the triangle. The trick was to sort t= he vertices so that edges are always computed the same way, but the result= s had different signs for edges (v0,v1) and (v1,v0). The code for getting a unique ordering (without branches) of two vertices is below. = This approach guaranteed that rays would not leak through connected meshes, = but still had some problems with rays almost parallel with the triangle's plane. The second (and better) solution was based on mr. Shewchuk's paper and original C source code (Jonathan Richard Shewchuk: Robust Adaptive FloatingPoint Geometric Predicates; code can be found from http://www.cs.cmu.edu/~quake/robust.html). He provides code for computing the (guaranteedly correct) sign of the v= olume of a tetrahedron. Although there may be inaccuracies in the floatingpoint value representing the volume, its sign is always correct (and the return val= ue is 0.0f iff the volume is exactly zero). In the code below the function Predicate::orient3d() is this function. We use the "adaptive" version o= f Shewchuk's function, i.e. it computes an approximation of the results, checks if i= ts error interval may cross zero (thus causing the sign to be incorrect) and onl= y in that case falls back to the more expensive code. The code is on average twice as slow as M=F6llerTrumbore, but in our c= ase we are very happy to pay the price. After all, if a routine doesn't need to wo= rk, one can always make it arbitrarily fast :). cheers, wili /*= //* ! * \brief Internal function for computing (robustly) if * a line segment and a triangle intersect * \param lineStart Start of the line segment * \param lineEnd End of the line segment * \param triangleVertex0 First vertex of the triangle * \param triangleVertex1 Second vertex of the triangle * \param triangleVertex2 Third vertex of the triangle * \return true if intersection occurs, false otherwise * \note The intersection distance is not computed (see * getLineSegmentTrianglePlaneIntersectionDistance()). * \note If the line segment is _exactly_ on the triangle's plane, * we consider the case to be nonintersecting. For such * cases a 2D line segment/triangle intersection routine * is more suitable. * \note If either end of the line segment touches the triangle (exactly), * we consider the case to be _intersecting_. *= */ inline bool intersectLineSegmentTriangle ( const Vector3& lineStart, const Vector3& lineEnd, const Vector3& triangleVertex0, const Vector3& triangleVertex1, const Vector3& triangleVertex2) { // Perform triangle edges vs. line segment tests. The line segment = must // pass on the same "side" of all triangle edges. float a =3D Predicate::orient3d (lineStart, lineEnd, triangleVertex= 0, triangleVertex1); float b =3D Predicate::orient3d (lineStart, lineEnd, triangleVertex= 1, triangleVertex2); if (a*b < 0.0f) return false; float c =3D Predicate::orient3d (lineStart, lineEnd, triangleVertex= 2, triangleVertex0); if ((a*c < 0.0f)  (b*c < 0.0f)) return false; // Perform line segment vs. triangle plane test. The line segment e= nd points must // be on different sides of the triangle's plane. float sd =3D Predicate::orient3d (triangleVertex0, triangleVertex1, triangleVertex2, lineStart); float se =3D Predicate::orient3d (triangleVertex0, triangleVertex1, triangleVertex2, lineEnd); if ((sd*se > 0.0f)  (sd =3D=3D 0.0f && se =3D=3D 0.0f)) return false; return true; } * * * #if defined (_MSC_VER) #pragma warning (disable:4035) // don't whine about no return value #endif /*= //* ! * \brief Determines order of two 96bit integer values (we use this * function for sorting two Vector3s) * \param a Pointer to first three values * \param b Pointer to second three values * \return boolean value (see below) * \note If a !=3D b, then it is guaranteed that order(a,b) !=3D ord= er(b,a). * \note This function is used to ensure that certain math computati= ons * are done always in the same order, regardless of the input * order of their parameters. * \note We have both an x86 assembly implementation and a portable * C implementation. Decent C/C++compilers should be able to optimize * away the three comparisons and use subtractwithborrow * instead, thus resulting in a branchless function. *= */ inline bool order (const uint32 a[3], const uint32 b[3]) { #if defined (SUPPORT_MSVC_ASSEMBLER) __asm { mov ecx,a mov edx,b mov eax,[ecx+0] sub eax,[edx+0] mov eax,[ecx+4] sbb eax,[edx+4] mov eax,[ecx+8] sbb eax,[edx+8] mov eax,0 adc eax,0 // return value in eax } #else signed int h =3D a[2]b[2]; unsigned int m =3D a[1]b[1]; unsigned int l =3D a[0]b[0]; m =3D (l > a[0]) ? 1 : 0; h =3D (m > a[1]) ? 1 : 0; return (h < 0); #endif } #if defined (_MSC_VER) #pragma warning (default:4035) #endif * * *  o Ville Miettinen, Lead Programmer o Hybrid Graphics, Ltd. o Email: wili@... o Web: http://www.hybrid.fi Original Message =46rom: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Nick Pelling Sent: Tuesday, May 28, 2002 12:01 To: 'Ignacio Casta=F1o'; Ville Miettinen; gdalgorithmslist@... Subject: [Algorithms] RE: [Algorithms] Re: [Algorithms] M=F6llerTrumbo= re ray/triangle intersection code Nice little piece of code, Ignacio, thanks for posting it! :) Overnight, I've been thinking about the problem in both geometric and strategic terms... and I'm not 100% sure that there is likely to be a solution that he'll really like. In one sense, the ideal first step would be to find the intersection wi= th the triangle's plane  everything after that is high accuracy (compare = the arithmetic precision of a [potentially very long] ray with a point with= in a plane). However, the very slight edgecentric inaccuracy involved would= make this unsuitable for his needs  and epsilons won't help resolve this. This really points to edgecentricity being the only approach that will= work  but because he has potentially long rays (relative to triangles' dimensions), your kind of tetrahedron area approach may well also gener= ate intermediate results approaching the limit of precision. Not having the luxury of relative values to carry out geometric transformations on may limit its practical usefulness, especially as Wili has numerous neardegenerate cases. Hmmm.... Cheers, .....Nick Pelling..... Original Message =46rom: Ignacio Casta=F1o [mailto:castanyo@...] Sent: 27 May 2002 20:56 To: Ville Miettinen; gdalgorithmslist@... Subject: [Algorithms] Re: [Algorithms] M=F6llerTrumbore ray/triangle intersection code Ville Miettinen wrote: > This is exactly what I pointed out to Charles in some of our private mails. > So, the question remains: is there publicly available source for a > *symmetrically correct* ray/triangle intersection code that is approximately > on par with the performance of the M=F6ller/Trumbore algorithm and do= es not > require precomputation/additional storage?? I wrote this one a lot of time ago, I used it to test segments against triangles. I precomputed the normals (for other reasons) but it shouldn= 't be necessary, because I only use it to test that both points of the segmen= t are in opposite sides of the plane. In your case you use rays, so that shou= ldn't be a problem. I think that the last conditional made some assumptions about the windi= ng of the face and the direction of the ray, and I don't remember exactly wha= t they were. I don't know if this is more robust than M=F6ller test or not, I only k= now that it is slower ;) However, you should be able to precompute the tetrahedron areas for each edge of your mesh, and take advantage of fac= e conectivities in the same way as in the pl=FCcker test. You can find an explanation of this test and a review of other tests in= : "Algorithms to test raytriangle intersection. Comparative study.", Raf= ael J. Segura, Francisco R. Feito. bool TestSegmentTriangle2( const Vec3 &q0, const Vec3 &q1, const TiGeom= =46ace & face ) { float dist =3D Vec3DotProduct( GeomVertices[face.v0], face.Normal ); float side0 =3D Vec3DotProduct( q0, face.Normal )  dist; float side1 =3D Vec3DotProduct( q1, face.Normal )  dist; if( side0*side1>0 ) return false; // the volume of the tetrahedrons must to be >=3D 0 // v =3D 1/3! =B7 a =B7 ( b * c ) // edgesegments Vec3 e0, e1, e2; e0.Sub( face.v0, q0 ); e1.Sub( face.v1, q0 ); e2.Sub( face.v2, q0 ); // edgepoint normals Vec3 n0, n1, n2; n0.Cross( e0, e1 ); n1.Cross( e1, e2 ); n2.Cross( e2, e0 ); // segment Vec3 q; q.Sub( q1, q0 ); // determinants float d0, d1, d2; d0 =3D Vec3DotProduct( q, n0 ); d1 =3D Vec3DotProduct( q, n1 ); d2 =3D Vec3DotProduct( q, n2 ); if( d0*d1>=3D0 && d1*d2>=3D0 ) return true; // if( d0>=3D0 && d1>=3D0 && d2>=3D0 ) // return true; return false; } Ignacio Casta=F1o castanyo@... _______________________________________________________________ Don't miss the 2002 Sprint PCS Application Developer's Conference August 2528 in Las Vegas  http://devcon.sprintpcs.com/adp/index.cfm _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Stephen J Baker <sjbaker@li...>  20020529 12:57:42

On Tue, 28 May 2002, Christian Henning wrote: > To be honest I don't want implement an algo. for solving a set of linear > equations. In case there is no other way, how to solve the equations? You don't have to solve the equations in realtime. Do that on paper (or with MathCAD or something)  symbolically  and you'll wind up with four horrible expressions relating the (x,y,z) of the center of the circle plus it's radius to the nine numbers that represent the coordinates of the points. That'll turn into four lines of C code (which you'll then want to optimise to eliminate common subexpressions, things you've already computed, etc, etc). An algorithm for solving an arbitary set of equations would be relatively nasty  but you don't have an arbitary set  you have a very fixed set.  Steve Baker (817)6192657 (Vox/VoxMail) L3Com/Link Simulation & Training (817)6192466 (Fax) Work: sjbaker@... http://www.link.com Home: sjbaker1@... http://www.sjbaker.org 
From: Brian Marshall <Brian.M<arshall@wa...>  20020529 08:29:39

A while back, I experimented with bottom up tree building for collision detection with some nice results. But it bugged me that I couldn't find much in the way of research on this. In fact, about the only resource I found was Wesley Hunt's work: http://www.cs.unc.edu/~hunt/c290/project/ Now, I'm looking into this again. Does anyone else have any links or ideas for bottom up tree building. Not necessarily from collision  I'm sure it's been tried for other problems. It's just bugging me that there doesn't seem to be much work on bottom up tree building anywhere! Brian. 
From: Christian Henning <henning@ro...>  20020528 19:23:44

The link Ignacio was sending seems to me a bit easier to implement. Which I have already done. ;) But thanks for the link. This website looks very promising and a good base to browse through math. problems. greets, Christian  Original Message  From: "Killpack, Chris" <ChrisK@...> To: "Christian Henning" <henning@...>; "Algorithms" <gdalgorithmslist@...> Sent: Tuesday, May 28, 2002 7:42 PM Subject: RE: [Algorithms] algorithm for calculating a circle out of three points What you are after is called the circumcircle of a triangle. I found this link at MathWorld http://mathworld.wolfram.com/Circumcircle.html Is this what you are after? Chris Original Message From: Christian Henning [mailto:henning@...] Sent: Tuesday, May 28, 2002 10:05 AM To: Algorithms Subject: [Algorithms] algorithm for calculating a circle out of three points Hi there, at this time I'm sitting on the delaunay triangulation. So I need an algorithm for computing a circle out of three points.The only one I know does use a set of linear equations, I don't want. Is there any other algorithm available? And by the way, how can I compute if a point is in the interior of a circle? Thanks in advance, Christian _______________________________________________________________ Don't miss the 2002 Sprint PCS Application Developer's Conference August 2528 in Las Vegas  http://devcon.sprintpcs.com/adp/index.cfm _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 _______________________________________________________________ Don't miss the 2002 Sprint PCS Application Developer's Conference August 2528 in Las Vegas  http://devcon.sprintpcs.com/adp/index.cfm _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 