应该采用什么技术修剪2d碰撞检查？ [英] What technique should be used to prune 2d collision checks?
问题描述
从一开始，碰撞检测就像是O（n ^ 2）问题。
您有一堆对象，您需要检查每个对象是否与任何其他对象相冲突。但是，我知道检查每个对象对所有其他对象是非常不方便的。为什么两个球之间的碰撞检查相对较贵，如果它们不是彼此相近？
这里是我正在开发的简单程序的例子： p>
如果你有1000个球，那么如果你去了天真的碰撞检测，你将有1000 ^ 2的收集检查（一百万）！这种碰撞检查很快成为我应用程序中的瓶颈。我需要来实现一些广泛的相位修剪。
使用2d - 圆形对象时，应该使用什么技术来修剪冲突检查？我已经阅读了关于QuadTrees，BSP，空间哈希等，但很难弄清楚哪种方法最适合这种用例。
有没有人有任何知识关于什么可能最有效？
我不会使用QuadTrees或任何复杂的东西，因为你会不断平衡和重新平衡树木之间移动。只要拥有一个网格，可能会更有效 - 每次移动一个球时，您只需要计算它所在的网格单元格，并将其转换到那里即可更改。每次你需要进行碰撞检查，你可以检查中心在你的网格中的球，或者如果你足够靠近边缘，你可以在相邻的球中。
您可以用网格大小进行实验以找到最佳值。你可能会发现这取决于你有多少球。
我在下面的评论中说过，但我认为它应该是答案的一部分：
只有当事物移动时进行碰撞检测，所以只需要检查移动的物体是否与其网格正方形（和上述相邻的）正好相反。这样一来，如果您在底部没有移动的东西，很快这些对象就不会检查碰撞，因为没有任何东西在他们的网格内移动，也没有进入或离开网格。
From the outset, collision detection feels like it is an O(n^2) problem.
You have a bunch of objects and you need to check if each object is colliding with any of the other objects. However, I know that it is wildly ineffecient to check each object against all the other objects. Why do a relatively expensive collision check between two balls if they aren't even close to eachother?
Here is example of my simple program I'm working on:
If you have 1000 balls then if you went with the naive collision detection you would have 1000^2 collection checks (a million)! This collision checking has quickly become the bottleneck in my application. I need to implement some broad phase pruning.
What techniques should be used to prune collision checks when working with 2d - circular objects? I've read about QuadTrees, BSP, spatial hashing, etc but it is difficult to sort out what method is most appropriate to this use case.
Does anyone have any knowledge about what might work best?
I wouldn't use QuadTrees or anything that complicated because you'll be constantly balancing and rebalancing trees as balls move between them. It would probably be more efficient just to have a grid - every time you move a ball, you can just calculate what grid cell it's in, and throw it in there if it's changed. And every time you need to make a collision check, you can just check balls whose center is either in your grid, or in adjacent ones if you're sufficiently close to the edge.
You can experiment with grid size to find the optimum. You may find it depends on how many balls you have.
I said this in a comment below, but I think it deserves to be part of the answer: Only do collsion detection when something moves, so you only have to check the moving thing against things in its grid square (and ajacent ones as mentioned above). That way if you get a pile of things in the bottom that aren't moving, pretty soon those objects are never checked for collision, because nothing is moving within their grid nor is anything moving into or out of their grid.
这篇关于应该采用什么技术修剪2d碰撞检查？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
