Is there a good way to project a point onto navmesh in recast ?

[Peng Zhang]

Hi, Mikko:

    given a point that is not on the navmesh, is there is a way to project the point along Y-Axis and return the projected point on that navmesh ?

[Mikko Mononen]

The method getPolyHeight will do that for you:

https://github.com/memononen/recastnavigation/blob/master/Detour/Include/DetourNavMeshQuery.h#L448

--mikko

On Wed, Sep 10, 2014 at 2:19 PM, Peng Zhang <pizza...@gmail.com> wrote:

Hi, Mikko:

    given a point that is not on the navmesh, is there is a way to project the point along Y-Axis and return the projected point on that navmesh ?

--

---
You received this message because you are subscribed to the Google Groups "recastnavigation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to recastnavigati...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Peng Zhang]

the getPolyHeight takes a polyRef, which should be first to be queried out. I also have tried the findNearestPoly, and give the extend to some (0, largeY, 0), but sometimes I got incorrect result. I have a picture for you to describe my question:

[Mikko Mononen]

The point returned by findNearestPoly() is already on the surface of the navmesh. getPolyHeight expects that the input points is over the polygon (within some small slack).

--mikko

[Peng Zhang]

the findNearestPoly may return a point which is outside the search box. Instead I just use the queryPolygons and filter the points inside the search box and return a closest point then I use getPolyHeight to get the projected height.

here is my code below: 

dtPolyRef polys[128];

int polyCount = 0;

float nearestDistSqr = FLT_MAX;

if (dtStatusSucceed(_navquery->GetDetourQuery()->queryPolygons(pos, extend, &filter, polys, &polyCount, 128))) {

for (int i = 0; i < polyCount; ++i) {

dtPolyRef ref = polys[i];

float closestPtPoly[3];

bool posOverPoly = false;

_navquery->GetDetourQuery()->closestPointOnPoly(ref, pos, closestPtPoly, &posOverPoly);

if (dtAbs(closestPtPoly[0] - pos[0])>extend[0] || dtAbs(closestPtPoly[1] - pos[1]) > extend[1] || dtAbs(closestPtPoly[2] - pos[2]) > extend[2]) {

continue;

}

float d = dtVdistSqr(closestPtPoly, pos);

if (d < nearestDistSqr) {

nearestDistSqr = d;

poly = ref;

dtVcopy(nearest, closestPtPoly);

[Ben Hymers]

A bit late to the discussion, but I found that "finding the nearest on-mesh position" is much more complex than it seems! I had a number of bugs whose root cause was to do with finding 'closest' polys to a point. I ended up creating a few custom versions of findNearestPoly to accomplish subtly different things. Sometimes you really care about the found point being exactly the same in XZ, sometimes it's just literally the nearest point (which for inclined polys will not be the same in XZ!), sometimes it's somewhere in-between (so I provided a 'bias' for the Y axis distance), and sometimes it's "same XZ position if on a poly, otherwise closest Euclidean distance". Sometimes you want it to use the detail poly mesh even if the input point is outside the bounds of the poly (as polys whose detail verts vary a lot from the actual poly can give really strange results at the poly borders!). Sometimes you want something that'll give similar results just inside and just outside the XZ bounds of the poly (say, if you're checking navmesh position every frame and for whatever reason can't do a raycast).

Overall, the most commonly used version was to always check against detail polys (never the poly verts), finding the closest point on each detail tri (the expensive version which checks against corners and edges separately to the plane), then choosing the point closest to the input point but weighting distance in the Y axis about half as much as X and Z. The weighting is because often the input position will be some physics object or a character that's resting on something above the navmesh, and is physically closer to some poly e.g. in a nearby vent, but we'd prefer a point on the ground below it. Games with fewer vents (the game I'm talking about is Alien:Isolation, which is 99% vents!) will definitely want to behave differently!

[Mikko Mononen]

@Ben: Thanks for the excellent write up! I've noticed that same thing that often you want the point below, then then sometimes not. I've yet to find a heuristic that would work in all cases. For example in a point and click game, the logic becomes even more complex.

There was a recent addition, which tries to bias the nearest location to be directly below the query point, to capture the common case where the query point is already close to the detail mesh:
https://github.com/memononen/recastnavigation/blob/master/Detour/Source/DetourNavMeshQuery.cpp#L737  

@Peng: There are a couple of cases where I've treated the input bounds as suggestive (as in, if a polygon touches the query bounds) to keep the code simpler. For example in your case you actually should clip the detail mesh to the query box (or add additional constraint), instead of just discarding the points. I'm glad you found a solution that works in your case. 

--mikko