Closest point on a triangle to a line
Author
Heh, yeah [disturbed]
Maybe I'm about to do this the wrong way, so let me explain my reasoning. I want to perform capsule like collision rather than sphere collision. By capsule, I mean two halves of a sphere connected by a cylinder. Eg, a pill shape. Does this shape have a geometry name?
When I perform sphere collision, I find the closest point on the triangle to the sphere, then check the distance from the sphere center + radius to the closest point. I was considering doing capsule collision in the same way, but instead of a point, finding the closest point on the triangle to a line. The line being the entire run of the center most part of the middle cylinder area.
So the closest point on the line to the closest point on the triangle is then used to perform the exact same radius-distance check as spheres. Is this right? Or is there a better way to do it?
The reason I'm doing this is to simulate a sphere moving a straight line of motion in a single frame. The cylinder part is showing how much the sphere moved. Imagine drawing a sphere on screen, and without clearing the background, move it in a straight line over a bunch of frames. That's what I want to use for collision.
I have all of the math routines ready to go for sphere collision. But I'm not even sure where to start to find the closest point on a traingle to a line (or vice versa). Is this even possible? You need one to find the other..?
Thanks for absolutely any advice, heh.
[Edited by - Jiia on November 10, 2004 3:56:30 AM]
I think the google search you need is "swept sphere collision detection" or something like. Also a search for "fluid studios" and "collision detection using ellipsoids"
Last time I lokoed at code which did exactly what you asked, however, it simply did binary splits of spheres along the length of the capsule. I think I can do better than that... Id like to try anyway:
Trying to visualize it in my head, there is no way for the closest point to a line-segment to be inside the triangle unless the closest point on the line-segment is an end point, or the line-segment itself passes through the triangle.
if (infinite-ray-through-capsule intersects plane)
if (line-segment intersects plane)
if (point of intersection is within triangle)
[closest point is point of intersection.]
else
[determine the edge we go past (which we know from the last test) and the closest point is on that edge.]
endif
else
[determine the edge we go past (as above) and the closest point is on that edge.]
endif
else
[the capsule is parallel to the plane of the triangle - special case.]
endif
When testing for point-on-plane-inside-triangle, we determine which borders of the triangle include it, and which exclude it, so we already know which edge segment to test against.
I hope that was clear :)
Last time I lokoed at code which did exactly what you asked, however, it simply did binary splits of spheres along the length of the capsule. I think I can do better than that... Id like to try anyway:
Trying to visualize it in my head, there is no way for the closest point to a line-segment to be inside the triangle unless the closest point on the line-segment is an end point, or the line-segment itself passes through the triangle.
if (infinite-ray-through-capsule intersects plane)
if (line-segment intersects plane)
if (point of intersection is within triangle)
[closest point is point of intersection.]
else
[determine the edge we go past (which we know from the last test) and the closest point is on that edge.]
endif
else
[determine the edge we go past (as above) and the closest point is on that edge.]
endif
else
[the capsule is parallel to the plane of the triangle - special case.]
endif
When testing for point-on-plane-inside-triangle, we determine which borders of the triangle include it, and which exclude it, so we already know which edge segment to test against.
I hope that was clear :)
Author
Ahh, I think I see. So the task is very simular to a closest-point-on-triangle-to-point test, except I use the point where the infinite line intersects the triangle's plane as the point to check against? And the result will be the closest point on the triangle to the line?
And if the line is parallel to the triangle normal, there really is no closest point. The closest point is any point where the line overlaps the triangle on it's plane. Hmmm. Maybe just use the center of the overlapped portion?
This is much simplier than the other methods I've seen. I really hope it works, hehe [grin]
Ratings+=max
And if the line is parallel to the triangle normal, there really is no closest point. The closest point is any point where the line overlaps the triangle on it's plane. Hmmm. Maybe just use the center of the overlapped portion?
This is much simplier than the other methods I've seen. I really hope it works, hehe [grin]
Ratings+=max
That was almost right - Im going to go back and fix the formatting in my post :) <br><br>If the line is at a very shallow angle and misses the triangle, it is likely that the nearest point isn't the point of intersection with the plane. Instead, having found that we miss the triangle, we determine which edge of the triangle we just missed, and do a closest point on line-to-another-line test on that. If you don't follow the 'which edge we missed' bit, then just test all 3 and take the smallest :)
Author
Quote:Original post by Squirm
If the line is at a very shallow angle and misses the triangle, it is likely that the nearest point isn't the point of intersection with the plane.
But it is the best point to use with a closest-point-on-triangle-to-point test, isn't it? If the line misses the triangle but still intersects it's plane, then one of it's edges is the closest point to the line. The edge that wins is the one closest to that plane intersection point. Err I think [smile] But I would have to also find the closest point on my line to the closest point on the triangle, if it didn't intersect.
edit: Haha, I think I see what has happened. You were explaining how to find the closest point on the line to a triangle, and I was reading it as how to find the closest point on a triangle to a line. It's really just about the same deal, I suppose [smile]
edit2: Nope, I was wrong. You're totally correct. The plane intersect point is not always the best point to use for a closest point on triangle test. Damn. So I need a new closest point on line to line method, heheh.
Quote:Original post by Squirm
Instead, having found that we miss the triangle, we determine which edge of the triangle we just missed, and do a closest point on line-to-another-line test on that. If you don't follow the 'which edge we missed' bit, then just test all 3 and take the smallest :)
I'm really not sure how to know which edge we missed without comparing the distances of all three. Finding the closest point on a triangle to a point also involves this task, and I do it the same way there. By finding the closest point on a line for each edge.
This is the correct formatting?
if (infinite-ray-through-capsule intersects plane){ if (line-segment intersects plane) { if (point of intersection is within triangle) { [closest point is point of intersection.] } else { [determine the edge we go past (which we know from the last test) and the closest point is on that edge.] } } else { [determine the edge we go past (as above) and the closest point is on that edge.] }}else{ [the capsule is parallel to the plane of the triangle - special case.]}I'm not sure I know what you mean by "which we know from the last test". You mean the point-is-in-triangle test?
Thanks again
[Edited by - Jiia on November 10, 2004 6:52:42 AM]
Quote:So the task is very simular to a closest-point-on-triangle-to-point test, except I use the point where the infinite line intersects the triangle's plane as the point to check against? And the result will be the closest point on the triangle to the line?
not quite... if you look at Paul Nettle's paper, there is a subtility.
analytically,
P = V0 + u.(V1 - V0) + v.(V2 - V0)
Q = O + t.L
(P-Q)2 = r2
0 <= t <= 1
0 <= u <= 1
0 <= v <= 1
0 <= u+v <= 1
the first equation defines a point in a triangle (with the constraints on u and v below it)
the second equation defines a point travelling along a line (the centre of the sphere)
the third is the condition when the centre of the sphere is at distance r (radius of the capsule) from the point on the triangle.
P is the point of collision on the triangle
Q is the path of the centre of the sphere
u, v defines a point inside triangle (V0, V1, V2)
t defines a point on segment [O, O+L]
r is the radius of the capsule.
replace P and Q into the last equation, and solve for t, u, v
so, if you feel like solving that system of inequations... :)
note that, that set of equation is probably imcpomlpete... maybe missing some important stuff. anyway, maybe someone had a shot at this and solved the problem in a more elegant way than the usual swept-sphere algorithm.
Author
Not quite, to me or Squirm's entire strategy? Please tell me you were just referring to my suggestion of using the plane intersection to test as closest point on the triangle..? [smile]
If the intersection misses, finding the closest point on each edge to the line, then using the edge that is closest will work, right?
If the intersection misses, finding the closest point on each edge to the line, then using the edge that is closest will work, right?
I was slightly wrong in the case where we don't reach the plane ... if the capsule is "aimed" at a point on the plane which is outside the triangle, but doesnt actually pass through it, then we do need to check all of the edges for the closest one, but we can do it very quickly, because we know we need the closest end of the capsule, so we can revert to the simple sphere-triangle collision on the end point.
An aside on Paul Nettles approach:
Paul Nettle combined a bunch of tests into a single if statement. These tests are for which side of each edge of the triangle the point lies (in his case, the projection of the center of the sphere onto the plane of the triangle, in our case the intersection of our ray with the same plane). Now. Deep breath.
If we make sure all our triangles go the same way (clockwise/anticlockwise) then we can guarantee all those normals point inwards/outwards (odd meaning of normal here...think prisms). If we then also split the if statement up, we can skip one or two bits of his code under certain circumstances. This gives rise to a function something like the following, which is actually slightly longer than his because of all the code blocks. (note the assert(false) which I have only ever hit when I had a bug elsewhere in my code and consider to be a bonus!):
Using this form of the if statement we know which edge we 'missed' immediately, without doing any comparisons. This is what I meant. In the case that we intersect the plane but not the triangle, this is the edge we need. In the case that we don't intersect the plane, see my first paragraph.
An aside on Paul Nettles approach:
Paul Nettle combined a bunch of tests into a single if statement. These tests are for which side of each edge of the triangle the point lies (in his case, the projection of the center of the sphere onto the plane of the triangle, in our case the intersection of our ray with the same plane). Now. Deep breath.
If we make sure all our triangles go the same way (clockwise/anticlockwise) then we can guarantee all those normals point inwards/outwards (odd meaning of normal here...think prisms). If we then also split the if statement up, we can skip one or two bits of his code under certain circumstances. This gives rise to a function something like the following, which is actually slightly longer than his because of all the code blocks. (note the assert(false) which I have only ever hit when I had a bug elsewhere in my code and consider to be a bonus!):
inline Vec3f ClosestPointInTriangle(const Vec3f & pVertex0, const Vec3f & pVertex1, const Vec3f & pVertex2, const Vec3f & pPoint){ // Some vectors we are going to need: Vec3f Edge0 = pVertex1 - pVertex0; Vec3f Edge1 = pVertex2 - pVertex1; Vec3f Edge2 = pVertex0 - pVertex2; Vec3f TriangleNormal = cross(Edge1, Edge0); Vec3f Norm0 = cross(TriangleNormal, Edge0); Vec3f Norm1 = cross(TriangleNormal, Edge1); Vec3f Norm2 = cross(TriangleNormal, Edge2); // Determine on which side of which edges our point lies: bool OutsideEdge0 = dot(pPoint, Norm0) > dot(pVertex0, Norm0); bool OutsideEdge1 = dot(pPoint, Norm1) > dot(pVertex1, Norm1); bool OutsideEdge2 = dot(pPoint, Norm2) > dot(pVertex2, Norm2); if(OutsideEdge0) { if(OutsideEdge1) { if(OutsideEdge2) { // Ouside all edges. This is impossible unless the triangle is inside out or zero size: assert(false); return(pPoint); } else { // Only inside one edge (edge 2): return(pVertex1); } } else { if(OutsideEdge2) { // Only inside one edge (edge 1): return(pVertex0); } else { // Only outside one edge (edge 0): return(ClosestPointOnLineSegment(pVertex0, pVertex1, pPoint)); } } } else { if(OutsideEdge1) { if(OutsideEdge2) { // Only inside one edge (edge 0): return(pVertex2); } else { // Only outside one edge (edge 1) return(ClosestPointOnLineSegment(pVertex1, pVertex2, pPoint)); } } else { if(OutsideEdge2) { // Only outside one edge (edge 2) return(ClosestPointOnLineSegment(pVertex2, pVertex0, pPoint)); } else { // Point completely inside triangle - project onto triangle and return: TriangleNormal /= mag(TriangleNormal); return(pPoint - (DistanceToPlane(pVertex0, TriangleNormal, pPoint) * TriangleNormal)); } } }}Using this form of the if statement we know which edge we 'missed' immediately, without doing any comparisons. This is what I meant. In the case that we intersect the plane but not the triangle, this is the edge we need. In the case that we don't intersect the plane, see my first paragraph.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
