NavMesh.getClosestRegion a better approach? about yuka HOT 1 OPEN

Here's my possible approach:

Begin with a BFS search starting from current cell position at current point towards potentially up to 26 neighbours (for 2D case with cellsY === 1), up to 8 neighbours only). Consider doing this up to a maximum depth setting before "giving" up and going along with worse case scenerio (note, this unlikely to be case, and for such cases, usually a more globalised an octree strcuture that leads down to individual localised CellSPacePartionings, would be done to avoid such a worse case situation by narrowing down to neighboring occupied spaces from current position. This is typically done for highly convex navmesh worlds lot of empty spaces where a single monolithic CellSpacePartioning structure wouldn't be too ideal. (A generalised utility that actually handles such common grid-based searches on generalised 2D/3D with function callback, could come in handy)

The general idea is to start with the current celll and hope to find a closest distance candidate result (best case scenerio). With that result, the subsequech s searches along neighboring cells will be bounded and eventually the overall search space is kept small.

Pseudo code:

curMinRequiredDist = minRequiredDistParam != null ? minRequiredDistParam : Infinity;
currentClosestPolygon = null

foreach cell in BFS, starting from root currentCellAtPosition {
   if (cell === currentCellAtPosition || distToCellFrom(currentPos) < curMinRequiredDist) {
   for all (not yet visited) polygons in cell:
    dist = getDistToPolygonForCurrentCycle(poly)
    if (dist < curMinRequiredDist) {
       dist = curMinRequiredDist;
       currentClosestPolygon = polygon;
    }
  }
}

Offhand, i think the generalised closest 3D distance to polygon can start out by checking on whether the point lies within polygon's plane projected bounds. (basically the point has to lie within all edge planes extruded out along the plane normal of the polygon, which you can get with the cross product between each edge delta (<- normalised edge.direction() not needed) and plane normal vector). Note that normalisation of this cross product product result isn't need for this case either since you are measuring inside/outside case only. If point lies positively "within" all of the projected polygon bounds (dot product of point vs edge crossed direction), use the distance to polygon's plane. Else , get distance to closest line segment of polygon's edge. (can also early-out skip "back-facing" edges normals in relation to the point as well as those points definitely lie further away), so not all line segments needs to be tested. So, the closest point is than clamped to either the plane or edge of the polygon, depending on whether the point is inside or outside the projected plane normal bounds of the polygon.

And oh yes, if the input point lies outside the entire bounding box of the cell space partitioning, it should also clamp and start the start from the closest cell to the point.

getClosestRegionAndPoint would be more useful as such, particularly for those google sketchup kind of snapping behaviours.

from yuka.