findNearestPoly should handle > 128 polygons about recastnavigation HOT 4 CLOSED

The DT_SUCCESS | DT_BUFFER_TOO_SMALL would be most appropriate.

[edit] Actually DT_BUFFER_TOO_SMALL is generally used to indicate that the user provided buffer is too small. So... DT_SUCCESS | DT_OUT_OF_NODES | DT_PARTIAL_RESULT, would be correct one, yet very odd.

An alternative would be to fix it. The method queryPolygons could be changed to take an interface like this:

struct dtPolyQuery {
    virtual void process(const dtMeshTile* tile, dtPoly** polys, dtPolyRef* refs, int count) = 0;
};

And process a bunch (i.e. 32) of polygons at time.

On Mon, Aug 17, 2015 at 9:03 PM, Jakob Botsch Nielsen <
[email protected]> wrote:

findNearestPoly currently uses an internal buffer size of 128 polygons.
When this is not enough, it still succeeds silently without any indication
of an error occurring.

I want to submit a PR to fix this, but I am not sure of the best way to
indicate this error. findNearestPoly can be changed to return DT_FAILURE
| DT_INVALID_PARAM immediately after queryPolygons indicates that the
buffer was too small; this, however, is a breaking change.

Another option could be to return DT_SUCCESS | DT_INVALID_PARAM or DT_SUCCESS
| DT_BUFFER_TOO_SMALL, and still find the nearest poly among the polygons
returned by queryPolygons. This would not be a breaking change.

Which solution do you think would be the best?

—
Reply to this email directly or view it on GitHub
#107.

from recastnavigation.

I was so busy wondering whether I could, I didn't stop to think if I should. Fixing it would indeed be pretty straightforward like that.

I did however find a post of yours, where you talk about solving it from the caller of the API: https://groups.google.com/d/msg/recastnavigation/Gz3CavAztxk/p9cNj1UgiYAJ

Here you recommend starting with small extents and increasing them until it finds the closest polygon. This is something findNearestPoly could also do by itself. Although there could be problems with it not finding the nearest polygons when it used deflated extents, since the box corners are farther away than the center of the box faces. Here's what I mean for 2D:

But as you note, findNearestPoly will be slow for large extents, so the dtPolyQuery solution would also be potentially breaking for some people, as it could end up having to process very large amounts of polygons, when not needed.

Is there a more ideal solution maybe? Perhaps a way to indicate in dtPolyQuery that we do not need all polygons.

from recastnavigation.

Isn't the problem with this function that it is implemented in a way that must gather all the polygons for consideration up front before processing them?

Why not make the bounding volume tree an internal dependency(and not user optional), such that these type of searches can use the tree structure to find the nearest polygon. No buffers to fill, and the extents can just be a restriction to which nodes of the tree may search.

from recastnavigation.

@jswigart that's essentially the fix suggested by @memononen. queryPolygons already uses the BV-tree if available, so if we passed dtPolyQuery to that we could avoid collecting them all and just process a chunk of them directly. I will look at getting that done.

from recastnavigation.