用于移动物体的空间数据结构？
我想知道处理大量移动对象（球体、三角形、盒子、点等）的最佳数据结构是什么？ 我试图回答两个问题，最近邻和碰撞检测。
我确实意识到，传统上，像 R 树这样的数据结构用于最近邻查询，Oct/Kd/BSP 用于处理静态对象或很少移动对象的碰撞检测问题。
我只是希望还有其他更好的东西。
我感谢所有的帮助。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您可以将场景划分为八叉树并利用场景连贯性。 您正在测试的移动对象将在树的特定节点中持续特定数量的帧，具体取决于其速度。 这意味着您可以假设它将在节点中，因此可以快速删除许多不在节点中的对象。 当然，棘手的一点是，当您的对象靠近分区的边缘时，您必须确保更新对象所在的节点。
移动的对象具有方向和速度。 您可以通过使用对象移动方向的垂直划分轻松将场景分为两部分。 不需要检查位于该划分错误一侧的任何对象。 当然要补偿其他物体的速度。 因此，如果另一个对象相当慢，您可以轻松地将其从进一步的检查中剔除。
始终使用轴对齐边界框之类的东西来简化您正在测试的任何形状。 初始碰撞测试
您可以计算物体与另一个移动物体之间的距离以及速度。 如果另一个移动物体以更快的速度沿相同方向移动，您可以将其从检查中排除。
根据对象的形状，还有许多其他优化。 圆形、正方形或更复杂的形状都可以在移动时进行特定的优化。
假设某些对象确实停止或可以停止移动，您可以跟踪停止的对象。 这些对象可以像静态对象一样对待，因此检查速度更快，您可以对它们应用所有静态优化技术。
我知道更多，但一时想不出来。 有一段时间没这样做了。
当然，这取决于您如何进行碰撞检测。 您是否根据速度增量更新对象的位置并检查它是否是静态的。 或者您是否通过挤压形状并计算出初始碰撞点来补偿速度。 前者对于快速移动的物体需要一小步。 后者更复杂且成本更高，但效果更好。 另外，如果你要旋转物体，那么事情就会变得更加棘手。
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.
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.
Always simplify whatever shape you are testing with something like an axis aligned bounding box. An initial collision test
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.
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.
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.
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.
边界球可能会帮助您处理许多移动物体； 您计算对象的半径平方，并从其中心跟踪它。 如果两个物体中心之间的平方距离小于两个物体半径的平方和，那么就有可能发生碰撞。 一切都以平方距离完成； 没有平方根。
您可以根据对象之间的最小平方距离对最近的邻居进行排序。 当然，碰撞检测可能会变得复杂，对于非球形物体，边界球不一定会为您提供碰撞信息，但它可以很好地修剪需要比较碰撞的物体树。
当然，您需要跟踪对象的中心； 理想情况下，您希望每个对象都是刚性的，以避免必须重新计算边界球体大小（尽管重新计算并不是特别困难，特别是如果您使用刚性对象树，每个对象都有自己的边界球体是非刚性的；但它变得复杂）。
基本上，为了回答有关数据结构的问题，您可以将所有对象保存在主数组中； 我有一组“区域”数组，其中包含对主数组中对象的引用，您可以根据对象的笛卡尔坐标将对象快速排序； “区域”数组的重叠定义应该至少是主对象数组中最大对象半径的 2 倍（如果可行的话；显然会出现对象边界球缩放与对象数量的问题）。
一旦你有了您可以通过比较区域内所有对象的距离来进行快速碰撞测试；这也是区域定义变得重要的地方，因为您需要在区域数量和比较次数之间进行重大权衡。 ，它稍微简单一点，因为您的距离比较归结为简单的减法（当然，还有 abs() 操作），
然后您必须在非球形物体之间进行实际的碰撞检测，这可以是非球形物体。微不足道，但此时您已经极大地减少了潜在比较的数量。
基本上，它是一个两层系统；第一个是区域数组，您可以对场景进行粗略排序。 -区域距离比较； 其中您将对已碰撞的对象进行基本的碰撞检测和碰撞标记。
这种算法可能有空间在动态区域确定中使用树来平衡您的区域大小，以确保您的区域大小不会因“拥挤”区域而增长得太快； 不过，这类事情并不简单，因为对于不同大小的物体，你对密度的排序变得……至少可以说是复杂的。
Bounding Spheres probably would help you with many moving objects; you calculate the radius squared of the object, and track it from it's center. If the squared distance between the centers of two objects is less than the sum of the squared radii of the two objects, then you have a potential collision. Everything done with squared distances; no square roots.
You can sort nearest neighbors by the minimum squared distance between your objects. Collision detection can get complex, of course, and with non-spherically shaped objects, Bounding Spheres won't necessarily get you collision information, but it can prune your tree of objects you need to compare for collision quite nicely.
You'll need, of course, to track the CENTER of your object; and ideally you'd like for each object to be rigid, to avoid having to recalculate bounding sphere sizes (although the recalculation isn't particularly tough, particularly if you use a tree of rigid objects each with their own bounding sphere for the objects which are non-rigid; but it gets complicated).
Basically, to answer your question about data structures, you can keep all of your objects in a master array; I'd have a set of "region" arrays which consist of references to the objects in the master array that you can sort the objects into quickly based upon their cartesian coordinates; the "region' arrays should have an overlap defined of at least 2x the largest object radius in your master object array (if that's feasible; a question of object bounding sphere scaling vs. number of objects obviously comes up).
Once you've got that, you can do a quick collision test by comparing distances of all objects within a region to each other; again, this is where region definition becomes important, because you're doing a significant tradeoff of number of regions to number of comparisons. However, it's a little simpler just because your distance comparisons come down to simple subtractions (and abs() operations, of course).
Of course, then you have to do actual collision detection between your non-spherical objects, and that can be non-trivial, but you've reduced the number of potential comparisons very dramatically at that point.
Basically, it's a two-tiered system; the first is the region array, whereby you do a rough sort on your scene. Second, you have your intra-region distance comparison; wherein you're going to do your basic collision detection and collision flagging on the objects which have collided.
There probably is room in this sort of algorithm for use of trees in dynamic region determination to even out your region sizes to assure that your region size doesn't grow too rapidly with "crowded" regions; that sort of thing, though, is non-trivial, because with objects of differing sizes, your sort on density becomes... complex, to say the least.
进行碰撞检测的一种有趣方法是使用在特殊八叉树结构内组织的轴向对齐边界框（AABB）。 AABB 的帮助是因为它们使粗略碰撞计算变得非常快，因为您只需要执行最多 6 次比较。
对于八叉树结构，您应该使用一些技巧：
1) 节点占用的边界区域应该是普通八叉树的两倍（其中八叉树将空间划分为无重叠）。 因为每个节点应该重叠其相邻节点的一半面积。 由于 AABB 只能属于一个节点，这一额外的大小和重叠使其能够在一个节点中保留更长的时间。
2）同样在每个节点中 - 可能在层次结构的每个级别中 - 您都保持与该节点的邻居的链接。 这将涉及大量额外代码，但它允许您以接近 O(1) 的时间而不是 O(2logn) 的时间在节点之间移动元素。
如果八叉树占用了太多内存，您可以将其更改为使用稀疏八叉树结构，仅保留游戏世界中实际包含实体的部分的树。 然而，这意味着当实体在世界中移动时，您必须为每一帧执行更多计算。
您可能想要尝试代替八叉树的其他一些想法是使用 kd 树（我相信这是正确的名称），或者使用 AABB 自下而上构建结构。
KD 树（根据记忆）使用轴向对齐的平面来划分空间，因此它们非常适合与 AABB 一起使用。
另一个想法是，不要强制从上到下生成八叉树（从一个包围整个世界的盒子开始），而是从基本实体开始构建它，并构建更大的 AABB，不断增长，直到最大的一个包围整个世界。 尽管我不确定它如何与许多快速移动的实体一起工作。
（我已经有一段时间没有完成这种空间游戏开发编码了。）
One interesting method for doing collision detection is to use axially aligned bounding boxes (AABB's) organised within a special octree structure. The AABB's help because they make the coarse collision computations very quick to do because you only need to perform up to 6 comparisons.
There are a couple of tricks you should use with the octree structure:
1) The bounding area which a node occupies should be twice as large as it would be for a normal octree (where the octree partitions the space without overlap). As each node should overlap half of the area of its adjacent nodes. Since the AABB can belong to only one node this extra size and overlap allows it to remain in the one node for a longer period of time.
2) Also in each node - and probably in each level of the hierarchy - you keep links to the node's neighbours. This will involve a lot of extra code but it will allow you to move elements between nodes in close to O(1) time rather than O(2logn) time.
If the octree is taking up too much memory you could change it to use a sparse octree structure, only keeping the tree for the parts of the game world that actually contained entities. However this would mean that you'd have to perform more computations for each frame when entities move through the world.
Some other ideas you might want to try instead of an octree is to use a kd-tree (I believe that's the correct name), or use AABB's to build the structure from the bottom up.
KD trees (from memory) partition the space using axially aligned planes, thus they are a good fit for use with AABB.
The other idea is instead of forcing the octree generation from the top down (starting with a box envoloping the whole world), you build it up from the base entities and construct bigger AABB's that grow until the biggest one encompasses the whole world. Though I'm unsure of how it would work with many fast moving entities.
(It's been a while since I've done this kind of spatial game development coding.)
RDC 可能有用，特别是当你的对象稀疏时（不是很多）交叉点）。
RDC may be of use, especially if your objects are sparse (not many intersections).
扫除和修剪宽相 + gjk 窄相
sweep and prune broad phase + gjk narrow phase