1
\$\begingroup\$

One of my game systems requires that I find the closest point on a generalized mesh, which more often than not will be concave. This prevents me from just using Unity's built in ClosestPoint function, and all other alternatives have some other caveat which prevents me from using them so far.

The meshes are dynamically generated, pretty complex, and altered often, so it would be computationally unreasonable to split it into multiple convex meshes, unless there's some way I don't know about which allows fast splitting/reattachment of said meshes.

I considered checking a sphere around the point, and increasing the size of that sphere until I get a collision, but OverlapSphere and CheckSphere don't give any means to check the point of collision, only to check whether there was a collision at all.

Continuing with that train of thought, I tried a Spherecast with the same method and the maximum distance set to zero, but that didn't work either. Spherecasts don't detect any objects which are inside of the starting sphere location, so setting the distance to zero will result in no collision every time.

As a workaround to that, I tried setting the distance to a small positive number, equal to the step size which the Spherecast increases by each pass (in my case, 0.2). This almost works, but causes the cast to only detect collision points if I have a general direction to give it. There are two ways I tried to resolve this:

The first is by just passing in the direction from the point towards the center of the mesh I am trying to find collisions with, and although this works for a sphere, it breaks down for most of my other test cases, and just in a lot of different scenarios (Very concave polyhedra and shapes such as torii being two examples of situations where this method does not work.)

The second method I tried was to just take the direction to the closest point on the last frame, and pass that into the Spherecast. Again, works in some situations, but breaks down on large dihedral angles. Neither of these are really sufficient for what I need them for.

In terms of the constraints which I have to work under, the point should always be on the outside of the mesh, and the point should never be too far away from the mesh, but other than that there isn't really much else I can guarantee. Both the shape and the topology of the mesh are subject to change over time.

Any help would be greatly appreciated, thanks in advance!

\$\endgroup\$
0
\$\begingroup\$

We know that the closest point on a given triangle can't be any further away than the closest of its vertices.

But it could be closer than the closest vertex, so we need to use some knowledge of our mesh structure to make some better estimates here. For instance, if you have a maximum bounding radius the triangle would ever have.

  1. Iterate over your vertices and store the distance of that vertex from your point.

    Store the smallest such distance you find.

  2. Iterate through your triangles and, if the triangle has no vertex closer than this distance minus your bounding radius, skip over it.

  3. For each remaining triangle, find the closest point within that triangle and keep the closest one you find.

If you can, try storing your mesh in some type of acceleration structure like an octree so you can quickly find a subset of the vertices & triangles worth testing, and discard most of the mesh from consideration.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.