NavMesh.getClosestRegion a better approach?

[Glidias]

The getClosestRegion is rather moot since it uses a naive distance to centroid which isn't very accruate. It should calculate it based on whether the point lies within the region bounds (in 2D), and if so, maybe use a distance to plane as a metric (or maybe downward ray distance to plane?). If it doesn't lie within region bounds, then check distance to closest edge on polygon.

It could also consider (maybe given an allowance setting?), the CellSpacePartioninig (if available), to speed up the query and zero in on cells that lie within the allowance setting from the point. Currently, this is only supported for getRegionForPoint(pt) method. For the case of querying multiple cells, visited polygons ma be marked as "dirty" for the given timestamp ID query. eg.

// for each query
timestamp++;
// .....
if (polygon.__myNavTimeStamp !== timestamp) {
   polygon.__myNavTimeStamp  = timestamp;
    // process polygon
 }

to avoid visiting polygon twice. (or maybe a Set to check for visited polygons).

Why not use something like getClosestRegion( point , allowance?, resultPt?) ....which can optionally get the resultPt that is clamped closest to the navmesh region. Also, during findPath(), in the event the start point lies OUTSIDE the navmesh, a dummy prior starting straight line route leading from current position to the clamped start position (closest to start) can be done.

I'd probably do up this feature later if/when I need it though.

CellSpacePartioning may also work quite well with a raycast, (probably an optional seperate utility), using a step-based DDA routine to only capture cells along the ray path, prefably with a max distance limit.

As of now, I must ensure that the input points given to the function always lie within the navmesh for optimal results.

[Glidias]

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.