Closest point on a quad

855230605f07055d00f3f9c25c60fc63
0
Sniffman 101 Nov 14, 2008 at 21:48

So, I have a mesh of quads, on which I want to find the closest point to any given reference point.

My strategy is to divide the problem into finding the closest point to the reference on each of the faces and then choosing the closest of all these points. I’ve seen it like this a few times during a quick search and I believe this is the fastest way of doing it.

More interesting though is the problem of finding the closest point on one face. For this, I thought of calculating the corresponding plane equation from the normal and one of the corners. From this I can get the equation for the closest point on this plane to the origin of the current coordinate frame. If I just move my plane into a coordinate system translated in such a way that the reference point is the origin (simply using a slightly modified corner vector should do that trick), I should be able to find my desired result.

But, assuming this is all right, I am still faced with the problem of finding out whether this point is even within the bounds on the plane set by the quad’s edges. Otherwise, this result is no good. So how do I do a fast check for this? Or would it be faster if I abandoned the current way altogether and did something else?

3 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Nov 14, 2008 at 22:35

You can create a plane from each edge of a quad, using the edge vector and the quad’s normal. You can then test the nearest point on the quad’s plane against these planes to see if it’s inside the quad.

However, I think what you want to do is snap the nearest point on the quad’s plane to the nearest point on the quad itself. For this, it’s more straightforward to use barycentric coordinates (google for it; you’ll find mostly resources about triangles, but it can be extended to quads, or you can just split each quad into a pair of triangles). Once you have the barycentric coordinates, you can just clamp them into the [0, 1] range, which will automatically clamp to the nearest edge or corner of the quad if applicable.

That being said, if it’s a large mesh you can speed things up considerably by not considering every quad of the mesh, but using a spatial partitioning structure like a BSP tree or octree.

855230605f07055d00f3f9c25c60fc63
0
Sniffman 101 Nov 15, 2008 at 15:29

Yes, you’re very right, of course my aim is to find the closest point within the bounds.

I’ve looked into barycentric coordinates. It looks like for a quad I’ll need four barycentic coordinates. Any point on a quad is the weighted sum of its corner vectors with these area coordinates, so p = A * v1 + B * v2 + C * v3 + D * v4. This of course yields a set of three equations with four unknowns. The fourth equation is A + B + C + D = 1. Then it should be possible to get the barycentric coordinates (A, B, C, D) for the previously found closest point. (Provided the last equation holds also for points outside the quad? I’m not so sure…)

But then, how do you suppose I get the point “moved” into the quad? Really just by clamping? How does that work?

As for partitioning measures, I don’t think that’ll be worth the effort, as we’re talking about a mesh of about 60 quads max. But it might be practical to divide the quads into triangles, as it will remove one dimension from the whole thing.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Nov 15, 2008 at 22:03

Yes, the summing to one is correct for all barycentric coordinates, including those outside the quad.

Clamping the barycentric coordinates to [0, 1] really does move them onto the quad. Points with the barycentrics in [0, 1] are on the quad; all points off the quad have at least one coordinate < 0 or > 1. Try it and you’ll see.