Search Unity

  1. Looking for a job or to hire someone for a project? Check out the re-opened job forums.
    Dismiss Notice
  2. Unity 2020 LTS & Unity 2021.1 have been released.
    Dismiss Notice
  3. Good news ✨ We have more Unite Now videos available for you to watch on-demand! Come check them out and ask our experts any questions!
    Dismiss Notice

Closest point on mesh / collider

Discussion in 'Editor & General Support' started by pgbrandao, Nov 16, 2009.

  1. pgbrandao

    pgbrandao

    Joined:
    Jul 28, 2009
    Posts:
    15
    Hi everyone!

    I'm stumbling across a small problem, here's hoping someone can help. :D Basically what I need is the nearest point to an object.

    For now, I've been trying to use Collider.ClosestPointOnBounds. It looks perfect! Right? Unfortunately, the results I'm getting from this method are axis-aligned. Whenever the object is rotated (which is just about always), the method returns an invalid point which isn't actually on the surface. :( So I'll have to use another approach...

    Also, it doesn't matter to me whether the nearest point is on the collider or the mesh. I just need a way to know which point on the surface of an object is nearest to another point.

    Any help is really appreciated! :D
     
  2. andeeeee

    andeeeee

    Joined:
    Jul 19, 2005
    Posts:
    8,768
    OK, this is actually quite complicated, so I've attached an example project. You can use the code roughly as it is in NearestPointTest.cs, but this is arranged to use Gizmo drawing as a demonstration. In game code, you should initialise the VertTriList once and save the mesh's vertices and triangles arrays in instance variables (the calls to GetComponent are an unnecessary overhead at runtime).

    Post again if you have any questions about this.

    Update: the original code scanned through all vertices each time to see which was nearest to the target point. The new version includes a KDTree, a spatial data structure that makes searching through the vertices very efficient.
     

    Attached Files:

    Droo and HiddenMonk like this.
  3. pgbrandao

    pgbrandao

    Joined:
    Jul 28, 2009
    Posts:
    15
    Hi andeeee,

    Thanks so much for the solution. It works perfectly. :D Since it's rather computationally-intensive (even using KDTree) when using complex meshes, I'm using a simplified mesh for this nearest-point test, that way it taxes the CPU much less.

    I'm sorry for taking so long to reply, I ended up forgetting about this topic, only to come back a month later and see this. :)

    Cheers!
     
  4. Asprum

    Asprum

    Joined:
    Mar 21, 2012
    Posts:
    1
    Dear andeeee,

    I found your code very cool, and it works perfectly !
    But, sometimes, the nearest point returned is an edge when it should be a point inside a triangle. The NearestPointOnTri function seems to be responsable.

    I hope you will read this thread and comment my reply if I am in fault.

    Thanks a lot

    EDIT: The problem appears on a simple Cube GameObject.
    Replace the target by a Cube on position (0,0,0).
    Move the point pt on (-0.28, -0.07, -1): It works.
    Move the point pt on (-0.28, 0.02, -1): It fails.
     
    Last edited: Mar 21, 2012
  5. Wahooney

    Wahooney

    Joined:
    Mar 8, 2010
    Posts:
    275
    This worked out fine for me, until I got a mesh from a client that had ridiculously long, thin tris, where the closest verts weren't actuallt connected to the closest triangle. Any suggestions? Besides retopoing the mesh, obviously.
     
  6. dansav

    dansav

    Joined:
    Sep 22, 2005
    Posts:
    461
    I just opened this in 3.5+ and it doesn't seem to work. I get no output in console. No nothing when I press play. Any instructions or reason why it would no longer work?

    Thanks,
    Dan
     
  7. ZoomDomain

    ZoomDomain

    Joined:
    Aug 30, 2012
    Posts:
    150
    Code (csharp):
    1. function findminimum (arrayobjects : GameObject[])  {//not used function was supposed to find extremities of selected wall
    2.          floatmax.x = arrayobjects[0].transform.position.x;
    3.          floatmin.x = floatmax.x;
    4.          floatmax.y = arrayobjects[0].transform.position.y;
    5.          floatmin.y = floatmax.y;
    6.          floatmax.z = arrayobjects[0].transform.position.z;
    7.          floatmin.z = floatmax.z;
    8.        
    9.         for (var arrayobject in arrayobjects) {
    10.             if (arrayobject.transform.position.x > floatmax.x) {
    11.                 floatmax.x = arrayobject.transform.position.x;
    12.             }
    13.             if (arrayobject.transform.position.x < floatmin.x) {
    14.                 floatmin.x = arrayobject.transform.position.x;
    15.             }
    16.             if (arrayobject.transform.position.y > floatmax.y) {
    17.                 floatmax.y = arrayobject.transform.position.y;
    18.             }
    19.             if (arrayobject.transform.position.y < floatmin.y) {
    20.                 floatmin.y = arrayobject.transform.position.y;
    21.             }
    22.             if (arrayobject.transform.position.z > floatmax.z) {
    23.                 floatmax.z = arrayobject.transform.position.z;
    24.             }
    25.             if (arrayobject.transform.position.z < floatmin.z) {
    26.                 floatmin.z = arrayobject.transform.position.z;
    27.             }
    28.         }
    29. }
    that would work with using transform point distance () of everything
     
    Last edited: Mar 14, 2013
  8. HiddenMonk

    HiddenMonk

    Joined:
    Dec 19, 2014
    Posts:
    987
    Sorry to bump up an old thread, but it has been very useful in the ever so dry land of custom collision detection in unity.
    I also ran into this problem and found the issue.
    The problem seems to be that the KDTree finds a vertex that is closest, but doesnt take into account that there can be vertices that are in the exact same spot. Unity takes meshes and duplicates the vertices in order to have the normals be calculated properly.
    I have added a fix to the KDTree with the method FindNearestEpsilon and SearchEpsilon which will find all the nearest that are within epsilon range of eachother.

    Here is the relevant code...
    Code (CSharp):
    1.  
    2.     //Its possible for vertices the be in the exact same position, so we want to grab all of them.
    3.     public IList<int> FindNearestEpsilon(Vector3 pt, IList<int> resultBuffer) //Use result buffer to avoid garbage collection.
    4.     {
    5.         resultBuffer.Clear();
    6.         float bestSqDist = 1000000000f;
    7.         int bestIndex = -1;
    8.  
    9.         SearchEpsilon(pt, ref bestSqDist, ref bestIndex, resultBuffer);
    10.  
    11.         return resultBuffer;
    12.     }
    13.  
    14.     void SearchEpsilon(Vector3 pt, ref float bestSqSoFar, ref int bestIndex, IList<int> resultBuffer)
    15.     {
    16.         float mySqDist = (pivot - pt).sqrMagnitude;
    17.  
    18.         if((mySqDist < bestSqSoFar || Mathf.Abs(mySqDist - bestSqSoFar) < Mathf.Epsilon))
    19.         {
    20.             if(mySqDist < bestSqSoFar + Mathf.Epsilon + Mathf.Epsilon) resultBuffer.Clear();
    21.  
    22.             bestSqSoFar = mySqDist;
    23.             bestIndex = pivotIndex;
    24.             resultBuffer.Add(pivotIndex);
    25.         }
    26.  
    27.         float planeDist = pt[axis] - pivot[axis]; //DistFromSplitPlane(pt, pivot, axis);
    28.  
    29.         int selector = planeDist <= 0 ? 0 : 1;
    30.  
    31.         if(lr[selector] != null)
    32.         {
    33.             lr[selector].SearchEpsilon(pt, ref bestSqSoFar, ref bestIndex, resultBuffer);
    34.         }
    35.  
    36.         selector = (selector + 1) % 2;
    37.  
    38.         float sqPlaneDist = planeDist * planeDist;
    39.  
    40.         if((lr[selector] != null) && (bestSqSoFar > sqPlaneDist))
    41.         {
    42.             lr[selector].SearchEpsilon(pt, ref bestSqSoFar, ref bestIndex, resultBuffer);
    43.         }
    44.     }
    Code (CSharp):
    1.  
    2.     List<int> nearests = new List<int>();
    3.     Vector3 NearestPointOnMesh(Vector3 pt, Vector3[] verts, KDTree vertProx, int[] tri, VertTriList vt)
    4.     {
    5.         //    First, find the nearest vertex (the nearest point must be on one of the triangles
    6.         //    that uses this vertex if the mesh is convex).
    7.         //  Since there can be multiple vertices on a single spot, we need to find the correct vert and triangle.
    8.         vertProx.FindNearestEpsilon(pt, nearests);
    9.  
    10.         Vector3 nearestPt = Vector3.zero;
    11.         float nearestSqDist = 100000000f;
    12.         Vector3 possNearestPt;
    13.  
    14.         for(int i = 0; i < nearests.Count; i++)
    15.         {
    16.             //    Get the list of triangles in which the nearest vert "participates".
    17.             int[] nearTris = vt[nearests[i]];
    18.  
    19.             for(int j = 0; j < nearTris.Length; j++)
    20.             {
    21.                 int triOff = nearTris[j] * 3;
    22.                 Vector3 a = verts[tri[triOff]];
    23.                 Vector3 b = verts[tri[triOff + 1]];
    24.                 Vector3 c = verts[tri[triOff + 2]];
    25.  
    26.                 ClosestPointOnTriangleToPoint(ref pt, ref a, ref b, ref c, out possNearestPt);
    27.  
    28.                 float possNearestSqDist = (pt - possNearestPt).sqrMagnitude;
    29.                 if(possNearestSqDist < nearestSqDist)
    30.                 {
    31.                     nearestPt = possNearestPt;
    32.                     nearestSqDist = possNearestSqDist;
    33.                 }
    34.             }
    35.         }
    36.  
    37.         return nearestPt;
    38.     }

    The full code here
    http://forum.unity3d.com/threads/ge...in-physics-overlapsphere.395176/#post-2581349

    Edit - There is another issue with the kdtree in that it only searches for the closest vertex and then uses that as the closest triangle, when in reality the closest vertex does not have to be the closest triangle. In the thread linked above I post a BSPTree someone else made, but it is a lot slower depending on how many triangles you are overlapping.
     
    Last edited: Apr 20, 2016
  9. tedesignz1

    tedesignz1

    Joined:
    Nov 9, 2016
    Posts:
    1
    Resurrecting this thread from the dead to thank you. This is incredibly useful for changing gravity to attract an object to the surface of another object. Thanks a bunch!
     
  10. HiddenMonk

    HiddenMonk

    Joined:
    Dec 19, 2014
    Posts:
    987
    Unity now has a built in Physics.ClosestPoint so you probably dont need this kdtree anymore. They also added a Physics.ComputePenetration method.
     
    petey and SunnySunshine like this.
  11. enragedmrt

    enragedmrt

    Joined:
    Oct 5, 2009
    Posts:
    91
    Dead thread rez time :D. Just posting to let everyone know that if you're using the Unity built-ins for ClosestPoint, the collider can't be a non-convex mesh collider. So the helper scripts listed here are still very useful.
     
unityunity