如何优化我的基本物理模拟器？

我写了一个简单的物理建模器,它允许我在屏幕周围弹跳球.您可以单击并拖动以启动球,或者您可以一次生成数百个球并观察它们彼此交互.

alt text http://i41.tinypic.com/2zr0oic.png
[链接到更大的版本]

这是一个很有趣的小程序,如果可以的话,我想进一步研究它.我知道他们说早熟优化是所有邪恶的根源,但我开始遇到实际的性能障碍,我想知道是否有任何有游戏/模拟器开发经验的人可以帮助我.

问题:

现在,如果你添加太多球(我的机器上似乎无法处理超过800个),我的程序就会窒息.如果这样做,模拟不再现实,并且所有球在底部彼此重叠.

问题在于碰撞检测.在最天真的情况下,碰撞检测是O(N ^ 2)问题.每个球都会检查每一个球.这很快就会导致性能下降(即使在100个球之后,你也会在每个循环周期进行10k次碰撞检查).

如果你看这里,你可以看到我添加了几百个球的截图.模拟器无法跟上,它们开始相互重叠.

alt text http://i41.tinypic.com/2nsnuqd.png
[链接到更大的版本]

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

它的效果很好,除非有太多的球,最小的平移距离变得明显.它们开始大量重叠并且不断地在底部互相挤压.我越是"增加"引力就越糟糕.它们上的压力增加,它们被压缩/相互重叠的量增加.

再说一次,我没有问题,直到我击中了相当数量的N球.

当前优化方法:

碰撞检测 -
扫描和修剪 - (又称排序和扫描)

我在我的球上使用插入排序,每个循环沿x轴循环.由于插入排序的性质,我可以利用我的模拟器的时间一致性.框架到框架,球的位置只是稍微改变,因此排序没有太多工作要做.这使得线性分类分摊运行时间为O(N)或线性而不是其平均运行时间O(N ^ 2).

由于球是排序的,我在检查碰撞之前在第二个循环中做了几次预检查.现在我只需要检查彼此附近的球(因为它们沿着x轴排序),并且当我检查球与另一个球的xmin大于当前球的xmax时,我会突破第二个循环.所以它跳过了成千上万的支票.

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

在运行了一个分析器之后,碰巧检测器占用了大约55%的时间,而渲染器占用了大约45%.所以,这是我最昂贵的两个成本.

题:

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

相关守则:

整个项目:

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

或者,单击此处在浏览器中手动浏览文件.

感兴趣的部分:

Pastebin:checkCollisions() - w/Sweep和Prune

Pastebin:resolveCollision() - 如果仍未通过Sweep和Prune删除,则进行昂贵的真正冲突检查和解决.

Pastebin:render() - 单独渲染占用了大约45%的时间.

patros.. 13

简单的方法是不测试Object vs Object碰撞,用每个球的中心点填充一个数组.然后,从每个中心扫描一个以该点为中心的4*半径的正方形(您可以通过不使用正方形来优化这一点,代价是使代码更复杂).如果这个方块中有另一个中心,那么你才会检查它们是否在彼此的2*半径范围内(因此发生碰撞).您可以通过降低分辨率和圆球位置来进一步优化这一点,从而减少您需要执行的检查次数.

另一种方法是将空间划分为网格,并将对象存储在网格区域中.您只需要检查相邻网格中对象之间的碰撞.

简单的方法是不测试Object vs Object碰撞,用每个球的中心点填充一个数组.然后,从每个中心扫描一个以该点为中心的4*半径的正方形(您可以通过不使用正方形来优化这一点,代价是使代码更复杂).如果这个方块中有另一个中心,那么你才会检查它们是否在彼此的2*半径范围内(因此发生碰撞).您可以通过降低分辨率和圆球位置来进一步优化这一点,从而减少您需要执行的检查次数.

另一种方法是将空间划分为网格,并将对象存储在网格区域中.您只需要检查相邻网格中对象之间的碰撞.

跟踪附近的球 -

就像插入排序是最佳的,因为每帧的变化很小,你可以使用相同的属性来跟踪球'邻居'

每个球最多只能与其他6个球相互作用.您可以每隔10帧左右运行一个算法,以确定每个球所具有的邻居,然后将该信息用于接下来的十个帧来计算实际碰撞.

您还可以跟踪每个球的矢量,绘制虚线,并查看在接下来的3-5帧中哪些线交叉,并且仅计算可能发生的碰撞(即使很少会因时间而发生).

正如您按x轴排序一样,您可以在主窗口内的细分中"分组"球.当球在细分内至少一个球直径时,它只需要在同一个细分中查看球.如果它更接近一个或两个边界,则需要查看一个或两个其他细分,但它应该是更少的计算.

此外,这些细分可以动态定位,因此平均细分只有100个球 - 不需要具有不同数量球的相同大小的细分.

根据细分的拥挤程度(每平方单位球数),你可以尝试不同的算法 - 稀疏填充的盒子只需要矢量计算来预测碰撞,而密集的细分可能只需要某种优化的六边形计算.对于许多帧,稀疏框可能不需要碰撞检测(因为重叠将不会像在人口密集的框中那样被注意到).

可以确定给定盒子的能量密度 - 具有低能量球的非常稀疏的盒子比具有高能量的稀疏盒子需要更少的碰撞计算.

-亚当