Traversing the AABB tree uses a fixed-length array of length 32 to simulate a stack. How does it ensure that the stack will not overflow? #3350

BlackantHermit · 2024-09-13T07:36:56Z

BlackantHermit
Sep 13, 2024

For example, this code located in MRMeshProject.cpp:

constexpr int MaxStackSize = 32; // to avoid allocations
SubTask subtasks[MaxStackSize];
int stackSize = 0;

Answered by Fedr

Thanks for the question. Currently we can have up to 2^31 faces in a mesh. And since all our trees are balanced, their depth is always at most 32.

Projection can be split on two stages:

initial depth-first search of some point on mesh, where such stack size is enough because it is more than the depth of any leaf in tree.
search of possible closer points in not yet visited subtrees, where active pruning discards nodes located further than known point on mesh. On practice we have not seen stack overflow here, but some theoretical proof would be nice to have at least for not fully degenerate meshes.

Fedr · 2024-09-13T09:16:22Z

Thanks for the question. Currently we can have up to 2^31 faces in a mesh. And since all our trees are balanced, their depth is always at most 32.

Projection can be split on two stages:

initial depth-first search of some point on mesh, where such stack size is enough because it is more than the depth of any leaf in tree.
search of possible closer points in not yet visited subtrees, where active pruning discards nodes located further than known point on mesh. On practice we have not seen stack overflow here, but some theoretical proof would be nice to have at least for not fully degenerate meshes.

0 replies