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

_{Feb}
(80) 
_{Mar}
(128) 
_{Apr}
(111) 
_{May}
(157) 
_{Jun}
(70) 
_{Jul}
(116) 
_{Aug}
(465) 
_{Sep}
(574) 
_{Oct}
(325) 
_{Nov}
(163) 
_{Dec}
(182) 

2001 
_{Jan}
(167) 
_{Feb}
(191) 
_{Mar}
(319) 
_{Apr}
(118) 
_{May}
(252) 
_{Jun}
(427) 
_{Jul}
(187) 
_{Aug}
(96) 
_{Sep}
(219) 
_{Oct}
(161) 
_{Nov}
(109) 
_{Dec}
(210) 
2002 
_{Jan}
(97) 
_{Feb}
(80) 
_{Mar}
(143) 
_{Apr}
(234) 
_{May}
(72) 
_{Jun}
(246) 
_{Jul}
(155) 
_{Aug}
(280) 
_{Sep}
(418) 
_{Oct}
(81) 
_{Nov}
(72) 
_{Dec}
(88) 
2003 
_{Jan}
(59) 
_{Feb}
(63) 
_{Mar}
(33) 
_{Apr}
(27) 
_{May}
(87) 
_{Jun}
(50) 
_{Jul}
(97) 
_{Aug}
(45) 
_{Sep}
(35) 
_{Oct}
(67) 
_{Nov}
(78) 
_{Dec}
(13) 
2004 
_{Jan}
(167) 
_{Feb}
(144) 
_{Mar}
(172) 
_{Apr}
(93) 
_{May}
(43) 
_{Jun}
(7) 
_{Jul}
(27) 
_{Aug}
(36) 
_{Sep}
(48) 
_{Oct}
(54) 
_{Nov}
(5) 
_{Dec}
(44) 
2005 
_{Jan}
(53) 
_{Feb}
(36) 
_{Mar}
(13) 
_{Apr}
(3) 
_{May}
(19) 
_{Jun}

_{Jul}
(49) 
_{Aug}
(39) 
_{Sep}
(8) 
_{Oct}
(8) 
_{Nov}
(51) 
_{Dec}
(23) 
2006 
_{Jan}
(26) 
_{Feb}
(5) 
_{Mar}
(26) 
_{Apr}
(26) 
_{May}
(52) 
_{Jun}
(36) 
_{Jul}
(8) 
_{Aug}
(12) 
_{Sep}
(6) 
_{Oct}
(75) 
_{Nov}
(34) 
_{Dec}
(25) 
2007 
_{Jan}
(46) 
_{Feb}

_{Mar}

_{Apr}
(1) 
_{May}

_{Jun}
(7) 
_{Jul}
(2) 
_{Aug}

_{Sep}
(40) 
_{Oct}
(9) 
_{Nov}
(3) 
_{Dec}

2008 
_{Jan}

_{Feb}

_{Mar}
(26) 
_{Apr}

_{May}

_{Jun}
(2) 
_{Jul}
(4) 
_{Aug}
(6) 
_{Sep}

_{Oct}

_{Nov}
(5) 
_{Dec}
(2) 
2009 
_{Jan}
(63) 
_{Feb}
(4) 
_{Mar}
(12) 
_{Apr}

_{May}
(5) 
_{Jun}
(1) 
_{Jul}

_{Aug}
(2) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}

2010 
_{Jan}

_{Feb}
(14) 
_{Mar}

_{Apr}

_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2011 
_{Jan}
(2) 
_{Feb}
(1) 
_{Mar}
(2) 
_{Apr}
(1) 
_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}
(5) 
2012 
_{Jan}

_{Feb}
(1) 
_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}
(3) 
_{Sep}

_{Oct}

_{Nov}
(2) 
_{Dec}

2013 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 





1

2
(1) 
3
(1) 
4
(1) 
5
(2) 
6
(1) 
7
(5) 
8
(1) 
9

10

11

12
(6) 
13
(2) 
14
(1) 
15

16
(11) 
17

18

19
(6) 
20

21
(14) 
22
(9) 
23
(4) 
24
(2) 
25
(3) 
26
(1) 
27
(4) 
28
(10) 
29
(1) 
30
(1) 
31

From: Gouthas, Themie <themie.gouthas@ds...>  20030529 00:34:33

handball it this way John, and i'll test it Original Message From: Fay John F Contr AAC/WMG [mailto:john.fay@...] Sent: Thursday, 29 May 2003 4:48 AM To: plibdevel@... Subject: [Plibdevel] Intersection of a Sphere with a Triangle Gentlemen, In my further looking at "ssgVtxTable::isect_triangles" and "ssgVTable::isect_triangles" I have found something more. Early on in the function, the function calls "sgMakePlane", which involves three square roots. This plane is used in the call to "_ssgAddHit", whose function escapes me. A little later on there are three more calls to "sgMakePlane", each with its three square root calls. I believe that these latter calls are unnecessary. Let us define our triangle as having the three corners V1, V2, and V3, and our sphere as having a center "C" and a radius "r". We are interested in seeing whether any part of the triangle is inside the sphere. We define three vectors: P = V1  C is the vector from the center of the sphere to the first corner of the triangle A = V2  V1 is the vector from the first to the second corner of the triangle B = V3  V1 is the vector from the first to the third corner of the triangle We can parameterize the plane in which the triangle lies by the following equation: R = V1 + A u + B v where "u" and "v" are scalar parametric coordinates in the plane. The vector from "C" to "R" is then R  C = P + A u + B v We would like to know first the minimum length of the vector "R  C". If this minimum length is greater than the radius of the sphere, then the sphere does not touch the triangle. (In fact, it does not touch the plane of the triangle at all.) Secondly, we would like to check the distance from the center of the sphere to each corner of the triangle. If any of the corners is within "r" of the center of the sphere, then the sphere definitely touches the triangle. Thirdly, we would like to check the minimum distance of each of the edges of the triangle to the center of the sphere. This we can do with the formula for "R  C" above by constraining "v" to be zero (for the V1V2 side), "u" to be zero (for the V1V3 side), and "v" to be "1  u" (for the V2V3 side). If the minimum distance is less than "r" and the relevant parametric coordinate is between zero and one for any of the three sides, then the sphere touches the triangle. Finally, we would like to calculate the values of "u" and "v" for which the (unconstrained) vector "R  C" is a minimum. If both "u" and "v" are between zero and one, and their sum is less than one, then the sphere touches the triangle. If the algorithm has run through all these tests and the question is still indeterminate, then the sphere does not touch the triangle. The first test, finding whether the sphere touches the plane of the triangle, is already done (and done efficiently, given that the calculation of the plane is otherwise necessary) in the code. The second test will be quite simple: sgFloat radsq = sgSquare ( s>getRadius () ) ; sgVec3 vc ; sgSubVec3( vc, vv1, s>getCenter () ) ; sgFloat distsq = sgScalarProductVec3 ( vc, vc ) ; if ( distsq < radsq ) /* First corner is within sphere */ { _ssgAddHit ( this, i, m, plane ) ; continue ; } sgSubVec3( vc, vv2, s>getCenter () ) ; distsq = sgScalarProductVec3 ( vc, vc ) ; if ( distsq < radsq ) /* Second corner is within sphere */ { _ssgAddHit ( this, i, m, plane ) ; continue ; } sgSubVec3( vc, vv3, s>getCenter () ) ; distsq = sgScalarProductVec3 ( vc, vc ) ; if ( distsq < radsq ) /* Third corner is within sphere */ { _ssgAddHit ( this, i, m, plane ) ; continue ; } These two tests will probably handle 99 percent of the cases; I would think it pretty pathological for a sphere to intersect a triangle and not have one of its corners inside of it. The third test, for intersection with the edges, will take a little vector calculus. We start with the V1V2 edge ("v" = 0): R  C = P + A u Define d2 to be the square of the distance from the center of the sphere to a point on the line: d2 = ( R  C ) dot ( R  C ) = ( P dot P ) + 2 ( P dot A ) u + ( A dot A ) u^2 Differentiate this with respect to "u" and set the derivative to zero to find the closest point: 2 ( P dot A ) + 2 ( A dot A ) u = 0 u =  ( P dot A ) / ( A dot A ) d2 = ( P dot P )  [ ( P dot A ) ^ 2 / ( A dot A ) ] The derivation for the second side is similar: v =  ( P dot B ) / ( B dot B ) d2 = ( P dot P )  [ ( P dot B ) ^ 2 / ( B dot B ) ] For the third side it is slightly more involved: R  C = P + A u + B ( 1  u ) = P + B + ( A  B ) u d2 = [ ( P + B ) dot ( P + B ) ] + 2 [ ( P + B ) dot ( A  B ) ] u + [ ( A  B ) dot ( A  B ) ] u^2 u =  [ ( P + B ) dot ( A  B ) ] / [ ( A  B ) dot ( A  B ) ] d2 = [ ( P + B ) dot ( P + B ) ]  { [ ( P + B ) dot ( A  B ) ] ^ 2 / [ ( A  B ) dot ( A  B ) ] } In code, ... sgVec3 a_vec, b_vec, p_vec ; sgSubVec3( a_vec, vv2, vv1 ) ; sgSubVec3( b_vec, vv3, vv1 ) ; sgSubVec3( p_vec, vv1, s>getCenter () ) ; sgFloat p_dot_p = sgScalarProductVec3 ( p_vec, p_vec ) ; sgFloat p_dot_a = sgScalarProductVec3 ( p_vec, a_vec ) ; sgFloat a_dot_a = sgScalarProductVec3 ( a_vec, a_vec ) ; distsq = p_dot_p  p_dot_a * p_dot_a / a_dot_a ; if ( distsq < radsq ) /* V1V2 side is close to sphere */ { sgFloat u =  p_dot_a / a_dot_a ; if ( ( u > 0.0 ) && ( u < 1.0 ) ) { _ssgAddHit ( this, i, m, plane ) ; continue ; } } sgFloat p_dot_b = sgScalarProductVec3 ( p_vec, b_vec ) ; sgFloat b_dot_b = sgScalarProductVec3 ( b_vec, b_vec ) ; distsq = p_dot_p  p_dot_b * p_dot_b / b_dot_b ; if ( distsq < radsq ) /* V1V3 side is close to sphere */ { sgFloat v =  p_dot_b / b_dot_b ; if ( ( v > 0.0 ) && ( v < 1.0 ) ) { _ssgAddHit ( this, i, m, plane ) ; continue ; } } sgVec3 ab_vec, pb_vec ; sgSubVec3 ( ab_vec, a_vec, b_vec ) ; sgAddVec3 ( pb_vec, p_vec, b_vec ) ; sgFloat pb_dot_pb = sgScalarProductVec3 ( pb_vec, pb_vec ) ; sgFloat pb_dot_ab = sgScalarProductVec3 ( pb_vec, ab_vec ) ; sgFloat ab_dot_ab = sgScalarProductVec3 ( ab_vec, ab_vec ) ; distsq = pb_dot_pb  pb_dot_ab * pb_dot_ab / ab_dot_ab ; if ( distsq < radsq ) /* V2V3 side is close to sphere */ { sgFloat u =  pb_dot_ab / ab_dot_ab ; if ( ( u > 0.0 ) && ( u < 1.0 ) ) { _ssgAddHit ( this, i, m, plane ) ; continue ; } } Finally, we have to check for the case in which the sphere touches the interior of the triangle but none of the edges. We already know that it touches the plane of the triangle somewhere; we just need to figure out where. From the formulae R  C = P + A u + B v d2 = ( R  C ) dot ( R  C ) = ( P dot P ) + 2 ( P dot A ) u + 2 ( P dot B ) v + ( A dot A ) u^2 + 2 ( A dot B ) u v + ( B dot B ) v^2 we can differentiate "d2" with respect to "u" and "v" to get two equations for their values at the minimum point: 2 ( P dot A ) + 2 ( A dot A ) u + 2 ( A dot B ) v = 0 2 ( P dot B ) + 2 ( A dot B ) u + 2 ( B dot B ) v = 0 Solving this is easier if you use matrix notation but here is what you get: determ = ( A dot A ) ( B dot B )  ( A dot B )^2 u = [ ( B dot B ) ( P dot A ) + ( A dot B ) ( P dot B ) ] / determ v = [ ( A dot B ) ( P dot A )  ( A dot A ) ( P dot B ) ] / determ In code, ... sgFloat a_dot_b = sgScalarProductVec3 ( a_vec, b_vec ) ; sgFloat determ = a_dot_a * b_dot_b  a_dot_b * a_dot_b ; sgFloat u = ( 0.0  b_dot_b * p_dot_a + a_dot_b * p_dot_b ) / determ ; sgFloat v = ( a_dot_b * p_dot_a  a_dot_a * p_dot_b ) / determ ; if ( ( u > 0.0 ) && ( v > 0.0 ) && ( ( u + v ) < 1.0 ) ) _ssgAddHit ( this, i, m, plane ) ; I have put this into my private copy of "ssgVTable.cxx" and it compiles, but I have no way of testing it. If anybody is interested I can email you the code and you can see if it works. For most of the cases where the sphere does intersect the triangle I can save you three, six, or nine square roots. John F. Fay john.fay@... 