移动物体的空间数据结构？

问题描述

我想知道处理大量移动物体（球体，三角形，盒子，点等）的最佳数据结构是什么？我试图回答两个问题，最近邻居和Collsion检测。我发现传统上，像R树这样的数据结构用于最近邻居查询和Oct / Kd / BSP用于处理静态物体或移动物体很少的碰撞检测问题。

我只是希望有其他东西可以存在

我非常感谢所有帮助。 $ b

您可以在八叉树中分割场景并利用场景一致性。您正在测试的移动对象将根据其速度，位于树的特定节点中以获取特定数量的帧。这意味着您可以假定它将位于节点中，因此可以快速删除很多不在节点中的对象。当然，棘手的问题是当你的对象接近你的分区边缘时，你必须确保你更新了该对象所在的节点。

>移动物体具有方向和速度。您可以通过使用与对象移动方向垂直的分割，轻松地将场景分为两部分。不需要检查该分部错误的任何物体。当然补偿其他物体的速度。所以如果另一个对象是合理的缓慢的，你可以很容易地将它从进一步的检查中剪掉。 总是简化你正在测试的任何形状，边界框。初始碰撞测试

您可以将物体与另一个移动物体之间的距离加上速度。如果另一个移动物体以更快的速度以相同的总体方向移动，则可以将其从检查中消除。

还有许多其他优化，具体取决于对象的形状。圆形或正方形或更复杂的形状都可以在移动时做特定的优化。假设有些对象停止或停止移动，可以跟踪停止的对象。

这些对象可以被视为静态对象，因此检查速度更快，您可以将所有静态优化技术应用于它们。 我知道更多但是想不起我的头顶。有一段时间没有这样做。

现在当然这取决于您如何进行碰撞检测。您是否逐渐更新基于速度的对象位置并检查它是否是静态的。或者你是通过挤出形状并找出初始碰撞点来补偿速度。前者需要快速移动物体的一小步。后者更复杂，成本更高，但效果更好。另外，如果你要旋转物体，那么事情会变得更棘手。

I was wondering what is the best data structure to deal with a lot of moving objects(spheres, triangles, boxes, points, etc)? I'm trying to answer two questions, Nearest Neighbor and Collsion detection.

I do realize that traditionally, data structures like R trees are used for nearest neighbor queries and Oct/Kd/BSP are used for collision detection problems dealing with static objects, or with very few moving objects.

I'm just hoping that there is something else out there that is better.

I appreciate all the help.

解决方案

1. You can partition the scene in an octree and utilize scene coherence. Your moving object that you are testing is going to be in a specific node of the tree for a specific amount of frames depending on its speed. This means you can assume it will be in the node and therefore quickly cut out a lot of objects that are not in the node. Of course the tricky bit is when your object is close to the edge of your partition, you would have to make sure you update which node the object is in.

2. A moving object has a direction and a speed. You can easily divide the scene in two sections by using a perpendicular division from your objects direction of movement. Any object on the wrong side of this division do not need to be checked. Of course compensate for the other object's velocity. So if the other object is reasonable slow, you can easily cut it out from further checks.

3. Always simplify whatever shape you are testing with something like an axis aligned bounding box. An initial collision test

4. You can take the distance between your object and another moving object plus the velocities. If the other moving object is moving in the same general direction at a faster velocity, you can eliminate it from your check.

5. There are many other optimizations depending on the object's shape. Circles or squares or more complex shapes all have specific optimizations you can do while moving.

6. Assuming some objects do stop or can stop moving, you can keep track of objects that stop. these objects can than be treated like static objects and therefore the checks are faster and you can apply all the static optimization techniques to them.

7. I know of more but can't think of any off the top of my head. Haven't done this in a while.

Now of course this depends on how you are doing the collision detection. Are you incrementally updating the object's position based on velocity and checking as though it is static. Or are you compensating for velocity by extruding the shape and figuring out initial collision points. The former needs a small step for fast moving object. The latter is more complicated and costly but gives better results. Also if you are going to have rotating objects then things get a little more tricky.

这篇关于移动物体的空间数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！