Sign in to follow this  

Finding closest point on tri to point

This topic is 3294 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to make a 'fake' lighting scheme using a multitextured pass that blends "light" over a dark surface to simulate light, like you might see in the Quake style of game. I've got a good idea of how to do it, but i need a way to determine the closest point on a tri, to an arbitrary point in space. Example; let's say i have a tri T defined by three verts, V1, V2 and V3. I want to find the closest point on tri T to point P (which could be anywhere). I know it must have something to do with plane intersections, but i just can't put an equation together that gives me what i'm looking for. Help's appreciated.

Share this post


Link to post
Share on other sites
Er... am I missing a piece of complexity here? Just find the distance (or, better yet, the squared distance) from the point to each vertex, then compare them. I suppose it would be possible to convert the problem into a small decision tree of point-plane sidedness tests, but why bother?

Share this post


Link to post
Share on other sites
Actually, it looks like the sidedness tree does involve a few fewer computations. Until it's obviously worth it, though, I'd go with the simpler approach.

Share this post


Link to post
Share on other sites
It's the same as closest point to a plane, just constrained by the triangle. First find the closest point on the plane. If it's inside the triangle, you're good. If not, you're now in 2d (uh, I think this is right because of triangle inequality, might be shooting myself in the foot though). Next, check each of the triangle edges against the point, which is a shortest point from line constrained by the vertices, etc.

Basically, each step is a projection down a dimension until the constraints (triangle->segment->vertex) are satisfied. This has to end because when you hit a vertex there aren't any more constraints.

Also, just checking the 3 vertices doesn't work. If you have one big triangle with the point just floating off the center of it, it's fairly clear the closest point should be near the center which is not a vertex. That said if your triangles are always small/far away from the point, it should be fine.

Share this post


Link to post
Share on other sites
Ahhhhh, I totally misinterpreted. Yeah, it's just a matter of projecting onto the plane, then constraining to the triangle. Simplest method for the latter is to convert the point to barycentric coordinates, clip those, then convert back to euclidean coordinates.

Share this post


Link to post
Share on other sites
Now that I think about it, if you're happy with approximations, you could throw an extra vertex in the center of the triangle. Find the 3 closest vertices. Throw a new vertex in the center of those, etc. I bet 1-2 iterations of that would be pretty fast and easy.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Ahhhhh, I totally misinterpreted. Yeah, it's just a matter of projecting onto the plane, then constraining to the triangle. Simplest method for the latter is to convert the point to barycentric coordinates, clip those, then convert back to euclidean coordinates.
Does not work. Closest point problems need to work with feature regions. Barycentric coordinates divides the plane (or space) into regions, but these regions do not coincide with feature regions, and therefore what you suggest fails.

Share this post


Link to post
Share on other sites
A straightforward way of solving this is to project your point to the plane of the trangle, using triangle edges as basis vectors for your plane. This will give you the projection of the 3d point on a 2d surface where the triangle has vertices in (0, 0), (0, 1) and (1, 0). So its very easy to check whether your projected point is inside the triangle or not.

So:


//Triangle has vertices in v0 v1 and v2. P is your point

r0 = P - v0
r1 = v1 - v0
r2 = v2 - v0

q1 = (r1 dot r0)/length(r1)^2
q2 = (r2 dot r0)/length(r2)^2

//now q1 and q2 are the coordinates of the projected point along r1 and r2

//is point in triangle?

if (q1 > 0 and q2 > 0 and q1 + q2 < 1)
yes
//projection point in 3d space is v0 + r1*q1 + r2*q2

else
no
//find the closest point on the triangle
if (q1 < 0){
if (q2 < 0) v0 is your closest point
if (q2 > 1) v2 is your closest point
else your closest point is v0 + r2*q2
}

// if q2 < 0 you do basically the same as above

if (q1 > 0 and q2 > 0) //this is trickier
{
t = (1 - q1 + q2)/2

if (t > 1) v2 is closest
if (t < 0) v0 is closest
else your closest point is v0 + v1 + (v2 - v1)*t
}







Lets hope i didnt screw that up to much now :)

Hope it helps
//Emil

Share this post


Link to post
Share on other sites

This topic is 3294 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this