Hi everyone,

I have a voxelised representation of a 3D environment, as shown below:

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:

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!

Neoptolemus said:
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?

I did this some years ago with similar goals of convex segmentation, but on regular triangle meshes.

If i remember correctly, this were the steps:

1. For each edge, classify by angle how likely the two faces should merge. Let's call this a ‘height’ value, low means they should merge easily, high means they should not merge.
2. Diffuse the height value over the whole mesh. But after each step, set the height to be the maximum of the diffused and the initial value. Or add the initial height after each step. Can't remember, but the goal is to preserve sharp features of the height map. Repeat this until every face has a height value. This gives us kind of a harmonic map, with smooth low height values at flat regions.
3. Use a watershed algorithm to grow clusters. Imagine to fill our height map with water. It starts to concentrate at low spots, hitting the high edges later in the process. To do, we search for local minima in the height map and assign a new cluster ID to each minima we find. Next step is iterations over each unassigned face, looking for adjacent faces already having an assigned ID, and picking the one with the least difference in height, taking the ID from that. Repeating this process we get our growing clusters, until every face is assigned.
4. We may now want to merge some adjacent clusters, as this initial assignment may have too many small clusters, or noisy clusters, etc. I remember this badly, but i got something like a merge tree, first merging clusters which agree better with each other. This also was the most expensive process. Some Heuristic was needed to rate likeliness to merge clusters.

In the end i was pretty happy with the results, but replaced it with something completely different later. ‘Watershed mesh segmentation’ may be a good search term.