algorithmdata-structurescgoctree

When i need to to stop dividing octants in Octree?

I'm implementing octree data structure. In octants i store triangles. So question: When i need to to stop dividing octants in Octree? I think about max depth or number of max number of triangles in octant, but how i can calculate this values?

Solution

  • A good rule for many circumstances is to subdivide a box if the number of triangles in it is more than twice its depth in the tree. This ensures that:

    1. The total space consumed by the tree is at most proportional to the number of trianges;
    2. The total time spent traversing down the tree is at most proportional to the number of triangles you'll have to directly process in the target leaf; and
    3. You can still go deep when necessary to decompose a tight cluster.