THREE.js - Trying to get nearest point (Vector 3) of object from click-generated Vector 3

Question

I'm working on a point-and-click test game and have made a ton of progress through research and finding other stack overflow answers about this-or-that, but this is the first time I can't seem to find anything related to my question.

My plan is to implement PatrolJS into my project for pathfinding, and it seems like I shouldn't have any problem getting it working after this issue is solved. I have my environment as well as some NPC characters in my scene. I have the mouse interaction in 3d space able to select and store data about what is clicked on. I am able to move my character to the click positions. I believe my problem will come in registering clicks into the pathfinding area.

Here a visual representation of my question:

Here, you can see my environment simplified down to one color, as well as the area I am currently defining for my navmesh area. The player will be able to click anywhere on the 3d environment/NPC's etc to interact with/view/use elements in the environment. That clicking works already, returning me with the point in 3d space that the mouse/ray intersects with, and giving me any information about those elements clicked on that I have defined.

What I need some guidance with is, how can I get returned the most nearby point on the separate navmesh object to what was clicked in the environment object(s)? Say I click on some part of one of the tables. I want to be able to find the absolute closest Vector 3 point on the navmesh object. That way, if someone interacts with elements off of the navigable area, I can still define an endpoint and feed that into PatrolJS.

Answer 1

Given a mesh made out of n triangles and a point p you can find the closest point from the mesh to p using brute force in O(n), the algorithm is as follows

• For each triangle t that belongs to the mesh
  • project p onto the plane defined by t, let proj be this point
  • if proj lies on t then it's the closest point to p, store the distance from proj to p
  • if proj lies outside the triangle then compute the closest point to proj for each of the 3 sides of the triangle, store the distances from each of these points to p
• The overall answer is the point whose distance is closest to p

THREE.js Demo