Finding the closest point on a concave mesh

Question

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.

Answer 1

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 as your best candidate.

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

3. For each remaining triangle, find the closest point within that triangle and update your best candidate to 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.

Answer 2

public static bool CheckSphereExtra(Collider target_collider,SphereCollider sphere_collider,out Vector3 closest_point,out Vector3 surface_normal)
{
    closest_point = Vector3.zero;
    surface_normal = Vector3.zero;
    float surface_penetration_depth = 0;

    Vector3 sphere_pos = sphere_collider.transform.position;
    if (Physics.ComputePenetration(target_collider,target_collider.transform.position,target_collider.transform.rotation,sphere_collider, sphere_pos, Quaternion.identity,out surface_normal,out surface_penetration_depth))
    {
        closest_point = sphere_pos + (surface_normal * (sphere_collider.radius - surface_penetration_depth));

        surface_normal = -surface_normal;

        return true;
    }

    return false;
}

This will find the closest point and normal to the center of a sphere collider as long as the colliders are intersecting (make the radius large). Works with all types of colliders as far as I know. You can place the sphere collider into a "No collision" layer so it won't physically collide with anything or possibly make it a trigger.