Scene Management ---Spatial Partitioning
仅供个人学习使用，请勿转载，勿用于任何商业用途。
今天又仔细考虑了空间划分，偶有心得，记录下来:) 本文要讨论的问题非常简单，当以quadtree，k-d tree等空间数据接口划分场景时，所有节点都可以储存物体(方法一)，还是仅在叶节点储存(方法二)？为了方便讨论，此处的空间数据结构仅用于实现裁剪和碰撞检测，而不用于物体空间位置的层次变换。
两种不同的设计，最大的区别就在于我们希望如何处理跨越多个节点边界的物体。对于第一种方法，当物体跨越了多个节点时，则向上寻找一个刚好能完全包含物体的高级节点，把节点储存在这个节点中；第二种方法则把物体添加到所有与物体相交的叶节点中。第一种方法的好处在于设计简单，每个物体只有一个相对应的节点，物体的插入，移动，删除代价都比较小，空间储存需求也较低。但缺点也是明显的，所有节点都可能有物体，增加了碰撞检测时的逻辑，更重要的是高层节点中可能出现大量体积较小的物体，影响碰撞检测时的效率，也违背了空间划分的最初目的。第二种方法则恰恰相反，物体与节点一对多的关系，增加了物体在节点间移动的价相，但检测的效率则要不少。
面对两种各有优缺，甚至“相对”的方法，要解决所提出的问题，并没有唯一的答案，这也就是引擎开发的迷人之处，总是需要艰难的做出选择。以下是我自己的一些分析和思考:以不同的方式分别处理动态和静态物体。所有静态物体储存在叶节点，而动态物体储存在合适的最小节点。这样动态物体可以高效的在节点间移动，同时又减少了与静态物体之间碰撞检测的次数。一般来说，由于场景中动态物体相对较少，因此大部分非叶节点都不会储存任何物体，可以考虑把静态和动态物体放到完全不同的两个数据结构中(两棵树)。静态物体之间是不需要碰撞检测的，检测的逻辑可以更加高效，避免大量不必要的静态物体节点访问。更进一步，我们可以对静态物体的空间划分方式进行预处理，不再使用quadtree，octree等空间划分均匀，但物体分布不均匀的结构，而使用k-d tree/BSP等更合理的空间划分。同样，对于动态物体，也不必再坚持使用静态数据结构，loose k-d tree或者类似的动态结构效率也许会更高。再如WOW那样，动态物体都是生物，机械等体积差异不大的对象，数量不太多，不做动态物体间的碰撞检测，完全可以使用简单的均匀网格，或者深度非常浅的树来管理。