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?
Please log in or register to post a reply.
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.
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.
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.