Hi everyone,
I have a voxelised representation of a 3D environment, as shown below:
![](https://i.gyazo.com/5013a2f770793dc7f84520945b4e4dbf.png)
What I want to do is essentially build a set of convex regions for the flat surfaces, something similar to what the Recast library does below (each colour is a different region), except that these regions are not convex:
![](https://i.gyazo.com/69443f6bd1bffa8f27f1b55f7c1702f6.png)
The algorithm is easy in a one-dimensional context: walk along the X or Y axis, end the region if it hits a wall or cliff (defined as a height difference greater than step height) or if the angle of the slope decreases (i.e. we go from an upwards rise to a flat section, or flat section to downwards curve etc.).
What I'm struggling with however is how to extend this to a 2D context. I'm not sure what the algorithm would look like to expand outwards in two directions and ensure all the voxels covered form a convex shape, and when to stop expanding in the X and Y directions. Is there any kind of algorithm available to assist with this?
Thanks!