[Question] Suitability For 2D Navmesh Generation

[zicklag]

I have a use-case where I need to generate a 2D navigation mesh for a non-voxel game. Currently I have a mesh that looks like this ( pardon the green line and paused icon ):

The issue I have is that the navigation mesh is way higher resolution than it needs to be. Those great swaths of terain with no obstacles in them are represented by many more triangles than necessary.

I noticed in your voxel meshing example, the example seems to optimize the mesh properly for the areas that are solid surfaces, not using more triangles than necessary:

Looking at the greedy_quads algorithm, though, it only takes a 3D voxel array.

Do you think this is a proper use-case for building-blocks and if so, do you think we could make the greedy_quads function generic over 2D and 3D or else make a 2D version? Or is there a simple way for me to convert my 2D data to 3D before feeding it to greedy quads, andthen only taking the quads that I want out of it to get a 2D surface?

[bonsairobo]

Good question. Something like greedy quads could work for your use case. I'm not sure what your navmesh data structure looks like or how it's generated. But the greedy quads algorithm is not terribly complicated at its core. I think you would likely be able to implement your own algorithm for quad combining without too much effort.

As for whether a 2D version of this would be a good addition to building-blocks, there is certainly potential! My strategy up until now has been to focus on 3D but make things work in 2D as well when it's easy. I think this is a case where the 2D algorithm is very similar to the 3D one, but I'm not sure if it would be beneficial to actually make it generic.

A 2D version of greedy_quads would be a welcome feature addition though! I'd be happy to provide guidance on implementing that, but implementing it myself is not a priority.

[zicklag]

A 2D version of greedy_quads would be a welcome feature addition though! I'd be happy to provide guidance on implementing that, but implementing it myself is not a priority.

Cool! I'll probably take a look at the 3D algorithm and see if I can figure out how it works and I'll ask you if I have any questions.

How would you immagine organizing the two different modes for 2D and 3D?

Would we rename the current greedy_mesh function to greedy_mesh_3d and then make a new greedy_mesh_2d?

[bonsairobo]

Yea to follow the existing pattern I'd go with greedy_quads2 and greedy_quads3.

There's a good animation for how the algorithm works here: https://gedge.ca/blog/2014-08-17-greedy-voxel-meshing