I am looking forward to create a navigation volume to be utilized by AI actors.
The approach I am trying to tackle here is to first generate an octree and associate with respectable flags/data (type, what's contained for now). The octree is going to be fairly deep (up to 0.1 units).
This is the scene I am using for testing purposes:
results in 1947817 nodes in 9 levels. (22 x 9 x 22)
I am looking for an algorithm/concept/pseudo-code that would transform this octree into non-uniform, axis-aligned boxes derived from octants that match certain flags/data, that would, for instance, help me determine the navigation volume similar to what can be seen here (Havok):
With "I am looking for" - I have a feeling of such an algorithm/concept already existing, though, I am not sure. The feeling drives me towards this being a fairly mathematical problem that resides behind a common name.
The other approach would be to utilize a non-uniform grid (creates 4356000 cells) for the detailed shape to then be expanded (simplified) down to some boxes. Which my feeling tells, would utilize the same algorithm.
As for the "what have you tried part" - well... I have googled for some time with various combinations from keywords grid, merge, cell, flags, occupied, gamedev, octant, grow, largest space, adjacent and maybe some others to no avail. Well, before pushing the Post button, I did try some more keywords and ended up with this answer: https://gis.stackexchange.com/questions/23365/how-to-combine-adjacent-polygons-sharing-similar-trait-into-single-polygon which appears to be close to what I am looking for, except that it's 2D (though, I gave the keyword "polygon" for this query). Having learned that the process is called "dissolve", I made some more attempts with various combos with added word "dissolve". And through my findings some more searches and so on... Well... nothing.
If the answer wont yield any results, I know that I could attempt this by raying the hell out of the graph by starting at either corner and flooding through it all, basically, brute forcing my way.
So...
Is the common algorithm/concept already out there, that I could be pointed towards?;
or - what guidelines should I follow to produce such a product?