Deleting unreachable polys from navmesh

[Bogey]

Hi,

I'm generating nav meshes of fairly large maps. These can easily reach hundreds of MB. A sizeable chunk of them, however, consists of polygon islands that will never be reachable by the player's starting position.

Is there any good approach to remove them from the nav mesh entirely, in order to reduce size a bit?

I've seen the PruneTool in recast demo, which does something relatively similar with its flood fill algorithm. From what I understand, this simply flags unreachable polys, but does not actually remove them from the mesh, so doesn't appear to impact/reduce the size of the navmesh.

The only way I could think of so far is to 1) generate the mesh, 2) mark unreachable polys, then 3) revisit the original input-data and remove all vertices/tris that are close to the flagged polys, and then 4) re-generate the mesh with the pruned mesh data. I haven't tried implementing this yet, so I have no idea if this would work (it does sound somewhat hack-y); so wanted to check in here first to discuss if there are any (other) ways of achieving this.

Thanks!

[Mikko Mononen]

Hi!

Prune tool is good starting point. You should be able to make a function which takes a tile and removes all the polygons which are marked with specific type. It's mostly just bunch of annoying book keeping and index mapping. Take a look at DetourNavMeshBuilder to see how to parse the tile data.

Basically something like this:

- create navmesh

- run the prune tool to mark unused polygons

- for each tile

    - run the custom function to unpack the tile data, remove polys, remove details polys and remove unnecessary vertices

    - pass the data to dtCreateNavMeshData

--mikko

--

---
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/recastnavigation/1d67ab5e-c852-49ef-9973-0a14a968690b%40googlegroups.com.

[Bill Bierman]

I posted some code to this list many years ago that did exactly what
you suggest, Bogey. As I recall it re-built an IR from the mesh data
and pruned the unreachable polygons, then rasterized back into a mesh.
I had it working, though the code was not pretty. It is also not very
fast, which didn't matter for me as it was done "ahead of time".

> To view this discussion on the web visit https://groups.google.com/d/msgid/recastnavigation/CAPyD2nYSksuCcS7CEe%3DTLq5sCrJVbfvKotYDj5U9tUgja7-U5w%40mail.gmail.com.

[Bogey]

Thanks very much for the input both Mikko & Bill. That's a great starting point! I'll have a look at DetourNavMeshBuilder & see if I can sort out the housekeeping for removing the polys.

(And Mikko, on a more general note: Thanks a bunch for this absolutely fantastic library :)

To unsubscribe from this group and stop receiving emails from it, send an email to recastna...@googlegroups.com.