碰撞用的四叉树的搜索效率如何才能体现出来？

zlcnkkm

哦~这样的~还是先理解理解四叉树

zlcnkkm

有个疑问，按场景空间来划分，那么物体有可能同时存在于多个节点中吗？

无影无踪

都可以，这主要看你自己希望如何实现。一般比较简单的做法是如果同时占用多个节点的，那么把它放到所有被占用的节点的共同祖先节点中去（也就是刚好可以完全包裹该物体的节点）。

zlcnkkm

当物体完全包裹某节点所代表的区域时，才把物体加入到该节点吗？

无影无踪

是的，这使得整个场景的管理规范和简单，而且对于动态的物体来说尤其简单。

zlcnkkm

哦~基本明白了，十分感谢！

我该睡了，明天再讨论~ ：）

bigbook2000

我还是那个观点，不建议动态对象使用树来管理，可能我接触网络游戏多了，动态对象变换节点和搜索速度之间的代价很难平衡，一般场景管理使用BSP树来处理，当然场景中也有动态对象，但那些对象运动的频率都是有限的

3D的网络游戏一般不会有人物碰撞检测，就是人和人之间可以穿行，但人和场景之间有碰撞检测

无影无踪

其实我觉得应该看具体应用，动态对象用树来管理其实没有什么问题，即使BSP也是树，都有着划分场景的本质。但对于室内场景来说，叉树在渲染速度方面比BSP的确逊色不少，因为BSP有很好的Portal和PVS的支持，BSP的结构化面很多时候就是一块遮挡板。但叉树在室外场景的例地形中却是很好的应用。只要选择合适的构造参数基本上可以保证每一帧的碰撞等运算量在可接受范围之内。搜索速度也是挺快的。因为每一个动态的物体都会记录了自己上一帧在那个节点，这一帧很可能是在原来节点的父节点的另一个子节点中（毕竟正如正如所说运动频率是有限的），这样的搜索可以很好的进行优化。

zlcnkkm

如果场景中的动态物体不单是在地面上，而是整个空间中，每个人物（或者其它对象）会同时放出相当数量的攻击道具，道具也不是一定会打中的，整个场景使用一点较拟真的物理运算，不用树来管理不是更糟吗？