我什么时候需要停止在八叉树中划分八分圆？

Question

我正在实现八叉树数据结构。在八分圆中我存储三角形。所以问题：我什么时候需要停止在八叉树中划分八分圆？我考虑最大深度或八分圆中三角形的最大数量，但我如何计算这些值？

Answer 1

在很多情况下，一个好的规则是细分一个盒子，如果它里面的三角形数量是它在树中深度的两倍以上。这确保：

1. 树消耗的总量space最多与三角形的数量成正比；
2. 沿着树向下遍历的总时间最多与您必须在目标叶子中直接处理的三角形数量成正比；和
3. 必要时你仍然可以深入分解一个紧密的集群。