Following is an excerpt from GDAlgorithms-list (http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list) ================================================================================ From: "Ola Olsson" Subject: [Algorithms] Sweep sphere test Date: Wed, 15 Jan 2003 09:14:50 +1000 Hello everyone. I've implemented a sweep sphere to triangle collision routine but it seems to me it's a tad big (and slow) so I was wondering what people are doing about it around the globe. The routine has to return the first contact point (and normalised time). The algorithm I've implemented goes roughly as follows 1. Sweep sphere to plane [fail if not] 2. Check if plane contact point is inside triangle [complete if so] 3. for each edge: sweep to edge [store closest hit] 4. for each corner: ray/sphere test corner [store closest hit] 5. return closest hit. Naturally I dont just call this on every poly in the universe but have a grid on top of that and also do polygon aabb checks. Any comments/suggestions/pointers to resources welcome. cheers .ola ================================================================================ From: "Mark Wayland" Subject: RE: [Algorithms] Sweep sphere test Date: Wed, 15 Jan 2003 11:04:03 +1100 Interesting, I just re-coded our swept sphere-polygon test from = Carmageddon TDR2000 in the last few days ... All our collisions return position, normal and time. As a rule, test face, then edges, then vertices. In your tests, don't = normalise your normals if you don't need to (and you don't need to!) and if you return normals = from your collision, only normalise when you're returning... What you're doing doesn't sound that different, as long as you've got = lots of early-outs and only calculate more complex things if a previous, simpler test fails... As a start you could look at Tim Schroeder's code and perform quite a = bit of optimisation on that (we used something quite different on TDR2000). Cheers, Mark ================================================================================ From: "Ola Olsson" Subject: Re: [Algorithms] Sweep sphere test Date: Wed, 15 Jan 2003 14:02:41 +1000 Thanks. Had a look at the source, it certainly is neater (smaller) than my own sweep-edge test, so I might change. By the way, how'd you do a sweepsphere-plane test without normalising the normal? cheers .ola ================================================================================ From: "Mark Wayland" Subject: RE: [Algorithms] Sweep sphere test Date: Wed, 15 Jan 2003 17:20:01 +1100 If you currently perform poly_normal.dot(sphere_center - polygon_vert) to get the distance from the plane using a unit length poly_normal, then if you use a non-unit length normal, you'll get the distance scaled by the length of the normal. As getting the length of the normal = requires a square root, we'll try to avoid it by squaring the result. We end up = with distance squared by normal magnitude squared. So to compare distance squared with radius squared, as you probably do now, simply pre-scale = the radius by the normal magnitude squared... if (distance^2 > radius^2) ... becomes if (distance^2 > poly_normal.dot(poly_normal) * radius^2) when distance is calculated using a non-normalised normal. You can use = this on your edge tests to avoid the normalisation of the edge normal too. Hope this helps, Mark ================================================================================ From: =?iso-8859-1?Q?Ignacio_Casta=F1o?= Subject: Re: [Algorithms] Sweep sphere test Date: Wed, 15 Jan 2003 15:55:22 +0100 Ola Olsson wrote: > The algorithm I've implemented goes roughly as follows > 1. Sweep sphere to plane [fail if not] > 2. Check if plane contact point is inside triangle [complete if so] In this test, you can also obtain the nearest edge or the nearest vertex, so you don't have to test each one. I use the following code to obtain the outcode: uint32 TiCDFace::CheckPointInFace( const Vec3 &point ) const { Vec3 edge, edge_normal; float dot; int pos = 0; int neg = 0; uint32 outcode = 0; edge.Sub( v1, v0 ); edge_normal.Cross( edge, normal ); dot = Vec3DotProduct( point, edge_normal ) - Vec3DotProduct( v0, edge_normal ); if( dot < 0 ) outcode |= 0x01; edge.Sub( v2, v1 ); edge_normal.Cross( edge, normal ); dot = Vec3DotProduct( point, edge_normal ) - Vec3DotProduct( v1, edge_normal ); if( dot < 0 ) outcode |= 0x02; edge.Sub( v0, v2 ); edge_normal.Cross( edge, normal ); dot = Vec3DotProduct( point, edge_normal ) - Vec3DotProduct( v2, edge_normal ); if( dot < 0 ) outcode |= 0x04; return outcode; } Note that: dot = Vec3DotProduct( point, edge_normal ) - Vec3DotProduct( v0, edge_normal ); can also be written as: dot = Vec3DotProduct( point-v0, edge_normal ); that is probably faster. if outcode is 0 then the contact point is inside the triangle, if not, the outcode is computed as follows: switch( outcode ) { case 1: ClosestPointOnSegment( v0, v1, intersect, closest ); break; case 2: ClosestPointOnSegment( v1, v2, intersect, closest ); break; case 3: closest = v1; break; case 4: ClosestPointOnSegment( v2, v0, intersect, closest ); break; case 5: closest = v0; break; case 6: closest = v2; break; } Hope that helps. Ignacio Castaņo castanyo^yahoo_es ================================================================================ From: Oscar Cooper Subject: RE: [Algorithms] Sweep sphere test Date: Wed, 15 Jan 2003 16:29:19 -0000 There's also an equivalent optimisation for finding the closest feature = when using the other common test for containment of a planar point by a = triangle. Not really sure which method will be more efficient... seems like a = highly platform dependent issue. A point Q on a plane can be expressed as a linear combination of one = vertex of the triangle and the two edges connecting that vertex to the others, = such that: Q =3D V0 + s(V1 - V0) + t(V2 - V0) To find the values of s and t that correspond to the contact point P, minimise the squared length of (P - Q) with respect to small changes in = s and t by finding when the partial differentials of the squared length = with respect to s and t are both zero. This yields a linear system of two equations in two unknowns, which can = be solved by substitution to find s and t: a =3D [(P - V0).(V1 - V0) * (V2 - V0).(V2 - V0)] - [(P - V0).(V2 - V0) = * (V1 - V0).(V2 - V0)] b =3D [(P - V0).(V2 - V0) * (V1 - V0).(V1 - V0)] - [(P - V0).(V1 - V0) = * (V1 - V0).(V2 - V0)] c =3D [(V1 - V0).(V1 - V0) * (V2 - V0).(V2 - V0)] - [(V1 - V0).(V2 - = V0) * (V1 - V0).(V2 - V0)] s =3D a / c t =3D b / c I'm not going to try ASCII art for this, but it's easy to draw the six regions outside the triangle for which the contact point is closest to = each feature by extending each edge out at both ends. The ranges of s and t dictate which region the contact point occupies: (s < 0) and (t < 0) outside triangle, closest to V0 (t < 0) and (s + t >=3D 1) outside triangle, closest to V1 (s < 0) and (s + t >=3D 1) outside triangle, closest to V2 (s >=3D 0) and (t < 0) and (s + t < 1) outside triangle, closest to (V1 = - V0) (s < 0) and (t >=3D 0) and (s + t < 1) outside triangle, closest to (V2 = - V0) (s >=3D 0) and (t >=3D 0) and (s + t > 1) outside triangle, closest to = (V2 - V1) (s >=3D 0) and (t >=3D 0) and (s + t <=3D 1) inside triangle ================================================================================ From: christer_ericson^playstation_sony_com Subject: RE: [Algorithms] Sweep sphere test Date: Wed, 15 Jan 2003 10:28:51 -0800 Oscar Cooper wrote: >[...] >This yields a linear system of two equations in two unknowns, which can be >solved by substitution to find s and t: >[...] > >s = a / c >t = b / c > >I'm not going to try ASCII art for this, but it's easy to draw the six >regions outside the triangle for which the contact point is closest to each >feature by extending each edge out at both ends. The ranges of s and t >dictate which region the contact point occupies: > >(s < 0) and (t < 0) outside triangle, closest to V0 >(t < 0) and (s + t >= 1) outside triangle, closest to V1 >(s < 0) and (s + t >= 1) outside triangle, closest to V2 >(s >= 0) and (t < 0) and (s + t < 1) outside triangle, closest to (V1 - V0) >(s < 0) and (t >= 0) and (s + t < 1) outside triangle, closest to (V2 - V0) >(s >= 0) and (t >= 0) and (s + t > 1) outside triangle, closest to (V2 - V1) >(s >= 0) and (t >= 0) and (s + t <= 1) inside triangle This is not correct. The s and t you compute correspond to (2/3rds of) the barycentric coordinates for the point with respect to the triangle, and the 7 tests you describe corresponds to testing which _barycentric region_ the point lies in. However, for finding which feature (vertex, edge of face) the point is closest to, you need to find out which _Voronoi feature region_ the point lies in. Using the barycentric regions instead of the Voronoi feature regions breaks down when the triangle has an obtuse angle, in which case the barycentric region encompasses the Voronoi region at that vertex, and also cuts into the Voronoi regions of the two neighboring edges. Christer Ericson Sony Computer Entertainment, Santa Monica ================================================================================ From: christer_ericson^playstation_sony_com Subject: Re: [Algorithms] Sweep sphere test Date: Wed, 15 Jan 2003 12:23:15 -0800 Ignacio Casta=F1o wrote: >[...] > switch( outcode ) { > case 1: > ClosestPointOnSegment( v0, v1, intersect, closest ); > break; > case 2: > ClosestPointOnSegment( v1, v2, intersect, closest ); > break; > case 3: > closest =3D v1; > break; > case 4: > ClosestPointOnSegment( v2, v0, intersect, closest ); > break; > case 5: > closest =3D v0; > break; > case 6: > closest =3D v2; > break; > } This too is incorrect for the same reasons I already mentioned in a previous reply: the cases of this switch-statement correspond to testing the point against the _barycentric regions_ of the triangle, which fails when the triangle has an obtuse angle. To be correct, the code must test the point for containment in the _Voronoi regions_ of the triangle's features. Christer Ericson Sony Computer Entertainment, Santa Monica ================================================================================ From: =?iso-8859-1?Q?Ignacio_Casta=F1o?= Subject: Re: [Algorithms] Sweep sphere test Date: Thu, 16 Jan 2003 02:09:27 +0100 christer_ericson^playstation_sony_com wrote: This too is incorrect for the same reasons I already mentioned in a previous reply: the cases of this switch-statement correspond to testing the point against the _barycentric regions_ of the triangle, which fails when the triangle has an obtuse angle. To be correct, the code must test the point for containment in the _Voronoi regions_ of the triangle's features. I knew it wasn't exact, but never noticed that it failed with obtuse angles. Now I wonder how could it work so good. Maybe there were no obtuse-angled triangles in my test scene :-) So instead of generating the outcode from dot product of the edge_normals I should use dot of the edges themselfs... I will have to revisit that code soon. Ignacio Castaņo castanyo^yahoo_es ================================================================================ From: Oscar Cooper Subject: RE: [Algorithms] Sweep sphere test Date: Thu, 16 Jan 2003 09:13:19 -0000 Yeah, you're completely right. I forgot to mention how I was using the regions computed from s and t, as I thought Ignacio had already covered this - but looking back it seems it was left out. Having determined the region based on s and t, it is necessary only to find the first contact from the features in the PVS from that region. For an edge region, that set includes the edge and the two adjacent vertices. For a vertex region, the two adjacent edges and all three vertices must be included.