问题标签 [collision-detection]

从一开始，碰撞检测就好像是一个 O(n^2) 问题。

您有一堆对象，您需要检查每个对象是否与任何其他对象发生碰撞。但是，我知道将每个对象与所有其他对象进行检查是非常低效的。如果两个球甚至彼此不靠近，为什么要在两个球之间进行相对昂贵的碰撞检查？

这是我正在处理的简单程序的示例：

如果您有 1000 个球，那么如果您使用简单的碰撞检测，您将有 1000^2 次收集检查（一百万）！这种碰撞检查很快成为我的应用程序的瓶颈。我需要实施一些广泛的阶段修剪。

使用 2d 圆形对象时，应该使用哪些技术来修剪碰撞检查？我读过关于 QuadTrees、BSP、空间散列等的信息，但很难找出最适合这个用例的方法。

有没有人知道什么可能最有效？

重力游戏如何处理玩家、怪物或物体等移动物体与地板之间的关系？球员是否经常“落入”地板并被弹起来？

我发现对碰撞做出反应的两种方法是将玩家移回碰撞前的先前位置，并在移动之前测试新位置以查看是否会导致碰撞，但我不知道其中任何一个如何可以处理一个向上上升的平台，需要能够抬起玩家。我从 2D 游戏设计的角度来看这个问题，但我想同样的问题也会出现在 3D 游戏设计中。有什么提示吗？我应该查看任何参考资料吗？谢谢。

有很多关于碰撞检测的文献，我已经阅读了至少足够多的部分，以便对大多数技术相当熟悉。但是，有一些事情一直困扰着我，我想，既然 StackOverflow 可以同时访问一大群聪明的头脑，我会先在这里问一下，然后再在书架上四处寻找。

在这个时代，越来越多的工作被委派给 GPU 而不是 CPU，在很多情况下这是一件好事。例如，有几何着色器可以创建新的几何图形，或者（稍微不那么新，但仍然很吸引人）顶点着色器，您可以通过一堆顶点访问它们，并且会从中产生一些优雅的东西。不过我正在考虑的是，由于这些原语仅存在于图形硬件上，您将如何使用这些原语执行可靠的碰撞检测？假设我有某种极其简化的网格，它在顶点着色器中被置换（我没有具体问题，我更喜欢这个想法，而且我还没有深入了解几何着色器）。

到目前为止，我考虑的是从合适的角度单独的“渲染”通道，或多或少地关闭阴影，也许是较低分辨率的网格，渲染我的第二个基元的内部（面向内翻转）以及我想要的网格针对网格进行测试并执行遮挡查询。如果网格完全被遮挡，则不会有交集。这当然需要我的第二个原语是凸的。

不知何故，我觉得随着基元数量的增加，这种测试将非常昂贵（即使可以直接剔除大部分）。还有其他人有其他想法或技术吗？我对opengl和cg比directx更熟悉，但是如果你在directx中有一些例子，我想我可以找出opengl对应的部分。

感谢所有想法，所以请集思广益。:)

我编写了一个简单的物理建模器，可以让我在屏幕上弹跳球。您可以单击并拖动来发射一个球，或者您可以一次生成数百个球并观察它们之间的相互作用。

[链接到更大的版本]

这是一个有趣的小程序，如果可以的话，我想更进一步。我知道他们说过早的优化是万恶之源，但我开始遇到实际的性能障碍，我想知道是否有经验丰富的游戏/模拟器开发人员可以帮助我。

问题：

现在，如果你添加太多球，我的程序就会窒息（在我的机器上它似乎无法处理超过 800 个）。如果这样做，模拟将不再真实，并且所有球在底部相互重叠。

问题在于碰撞检测。在最简单的情况下，碰撞检测是一个 O(N^2) 问题。每个球检查每个其他球。这很快就会变得很糟糕（即使在 100 个球之后，每个循环周期你也要进行 10k 次碰撞检查）。

如果你看这里，你可以看到我添加了数百个球的屏幕截图。模拟器跟不上，它们开始相互重叠。

[链接到更大的版本]

目前，我通过寻找重叠的球来检测碰撞。如果我找到两个重叠的球，我会用它们的最小平移距离 (MTD) 将它们分开，或者将它们推开。然后我使用一个简单的物理方程来调整它们的冲量矢量，然后它们在碰撞后会朝不同的方向移动。

它工作得很好，除非球太多，最小平移距离变得明显。它们开始大量重叠，并在底部不断地相互推挤。我增加“重力”越多，情况就越糟。对它们施加的压力增加并且它们彼此压缩/重叠的量增加。

同样，在我击中相当数量的 N 个球之前，我没有任何问题。

当前优化方法：

碰撞检测 -
扫描和修剪- （又名排序和扫描）

我在我的球上使用插入排序，每个循环沿着它们的 x 轴循环。由于插入排序的性质，我可以利用模拟器的时间连贯性。逐帧，球的位置变化很小，所以排序没有太多工作要做。这将线性排序摊销运行时间带到 O(N) 或线性，而不是 O(N^2) 的平均运行时间。

由于球已排序，因此在检查碰撞之前，我在第二个循环中进行了几次预检查。现在我只需要检查彼此靠近的球（因为它们是沿 x 轴排序的），并且每当我检查一个球与另一个 xmin 大于当前球的 xmax 的球时，我都会跳出第二个循环. 所以它跳过了成千上万的检查。

当我实现这个时，它带来了巨大的速度提升。但是，我仍然希望能够处理超过 600-800 个球。我读过物理引擎可以轻松同时处理 10k 个对象之间的碰撞检测，所以我想我可以通过一些工作达到 1-2k。

运行分析器后，碰撞检测占用了我大约 55% 的时间，而渲染占用了大约 45% 的时间。所以，这是我最昂贵的两项费用。

问题：

你能想到任何更好的算法或技术让我的模拟器能够处理更多的球吗？

相关代码：

整个项目：

svn 结帐http://simucal-projects.googlecode.com/svn/ballbounce/trunk/

或者，单击此处在浏览器中手动浏览文件。

感兴趣的部分：

• Pastebin：checkCollisions() - 带扫描和修剪
• Pastebin：resolveCollision() - 如果仍然没有被 Sweep 和 Prune 删除，那么昂贵的真实碰撞检查和解决方案。
• Pastebin: render() - 单独渲染占用了我大约 45% 的时间。

参考我目前正在构建的这个编程游戏。

多亏了这篇文章的答案，我现在能够找到矩形所有点的 xy 坐标（即使在旋转时），并且墙壁碰撞检测现在几乎可以完美运行。

现在我需要用机器人自己实现碰撞检测（因为很明显，Arena 中会有不止一个机器人）。

Square-Square Collision Detection (Non-rotated) 在这种情况下无效，因为机器人会以一定角度转动（就像我在这里描述的那样）。

那么在 WPF 中实现这种形式的旋转矩形碰撞检测的最佳方法是什么？

我想肯定涉及到一些数学，但通常事实证明 WPF 中有一些函数可以为您“计算”这些数学（就像在这种情况下一样）

我想将一个 Texture2D 对象缩小为 XNA 中的另一个 Texture2D 对象。

原因是使用缩小的对象进行基于像素的碰撞检测。

这可以做到吗？

好的，我正在尝试编写一个程序，它可以告诉我旋转到 140 度的 30x100 矩形中的任何点是否在另一个旋转到 200 度的 30x100 矩形内。

老实说，我什至不知道从哪里开始。我考虑过在进行正常计算之前重新旋转它们，但它们仍然不匹配。

我怎样才能做到这一点？

While working on a really only-for-fun project I encountered some problem.

There is a 2D world populated with Round Balls, Pointy Triangles and Skinny Lines (and other wildlife too, maybe). They all are subclasses of WorldCreatures. They can move inside this world. When they meet each other, a Collision happens.

The thing I'd like to do is to make a way of detecting Collision between them. Here's what I'm standing on right now:

• For me Ball-Ball is easy, I just calculate their distance from their positions and compare it with the sum of their 'sizes'.
• Collision between Ball and edge of the world is simple too - I just check the distance from it, which, in Cartesian coordinates, is simple.
• More generic problems are - how to detect a collision between Line (starting and ending at some points) or other objects I could have there? Distance between a line and a point can be calculated easily too, but what I'd like is to have

Some kind of generic way to say if Object A collides with Object B. The code as it is now looks somewhat like:

Now, the collision detection mechanizm should depend on what objects can collide. So will the effect.

Should I just keep a list of all the objects in memory and loop through all them in every single step? Or, is there some better way to improve the performance of this task?

我正在尝试编写一种方法来计算两个圆圈是否重叠。我想出了以下内容，我只是想知道是否可以进一步优化它。

我正在做乒乓球比赛，我必须移动球并检测与外部边界以及移动桨的碰撞。我想使用向量而不是三角函数来实现它。

我的数学很弱，所以请指导我。