# Closest point on a triangle to a line

## Recommended Posts

Jiia    592
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]

##### Share on other sites
Guest Anonymous Poster
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 :)

Squirm    481
that was me :/

##### Share on other sites
Jiia    592
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

##### Share on other sites
Squirm    481
That was almost right - Im going to go back and fix the formatting in my post :) [I cant I was anonymous :(]

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 :)

##### Share on other sites
Jiia    592
Quote:
 Original post by SquirmIf 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 SquirmInstead, 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]

##### Share on other sites
oliii    2196
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... :)

##### Share on other sites
oliii    2196
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.

##### Share on other sites
Jiia    592
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?

##### Share on other sites
Squirm    481
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!):

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.

##### Share on other sites
Jiia    592
I'm a little confused. Is it not a line we are checking against each edge, and not a point? If it is a point, what point? The plane intersection we got from the infinite line? I had thought this wouldn't work.

Quote:
 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.

But the capsule will almost always be aimed at a point on the plane outside of the triangle. If it is not aimed directly at the triangle and not intersecting the plane, only when it is parallel does it not aim at the plane. How can we assume it will be the end of the capsule? What about in a case such as when the capsule line is almost completely parallel to the plane, the line intersects at some extremely far distance from the triangle, but the capsule center area is closest to the triangle. eg, both end points are farther from the triangle than the center is. So we can't assume it is on one of the ends of the capsule because of this aim, can we?

Here is a really crappy picture of what I mean:

Here is yet another crappy image of how I'm pretty sure the intersect point is useless if it doesn't hit the triangle:

Maybe I've been up too late [smile]

Thanks much

[Edited by - Jiia on November 10, 2004 9:11:10 AM]

##### Share on other sites
Squirm    481
Nope, that's fine. It's a better diagram than the one I decided not to draw ;)

Back to the "test line against all three edges" situation then :(

Bother.

Still, atleast you can get the intersection cases out of the way, but the annoying case you've drawn is probably also the most common one :(

Perhaps this is why people use ellipsoids instead [wink]

##### Share on other sites
Jiia    592
But doesn't an ellipsoid distort the shape of the capsule? It converts it into a sort of stretched sphere, right? Like if a beach ball was traveling at such insane speeds, the sides of it are squished [smile]

This wouldn't be very useful to me since I'm really doing sphere collision, and just want to stretch the very center of the sphere only, and not the ends.

By the way, anyone have an idea about finding the closest point on a line to another line? A document or such will be just as good. This is what I need to do, right? On the edges? Is the closest point always where they will cross on their shared plane?

##### Share on other sites
Jiia    592
I found this very useful article giving another idea on how to handle a moving sphere against triangles.

This guy is saying to turn the triangle vertices into spheres (I'm guessing you use the radius of the real sphere), the edges turn to cylinders, and the triangle plane into a slab. The moving sphere simply turns into a intersecting line.

Would this work?? It sounds right to me. The math involved here is less than what I do for static spheres!