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

Question

我写了一个简单的物理模拟器，可以让我在屏幕上弹球。您可以点击和拖动来发射球，或者生成数百个球并观察它们彼此交互。 [链接到更大的版本] 这是一个有趣的小程序，如果可能的话，我想进一步发展它。我知道他们说过早的优化是万恶之源，但我开始遇到实际的性能障碍，我想知道是否有任何有经验的游戏/模拟开发人员可以帮助我。

问题：

现在，如果您添加太多球（在我的机器上无法处理超过800个），我的程序会崩溃。如果这样做，模拟就不再真实，所有球都重叠在底部。

问题在于碰撞检测。在最简单的情况下，碰撞检测是一个O（N ^ 2）问题。每个球都检查其他每个球。这很快就会导致性能下降（即使在100个球之后，您每个循环周期都将进行10,000次碰撞检查）。

如果您在这里看一下，您可以看到我添加了几百个球的屏幕截图。模拟器无法跟上，它们开始重叠在一起。

[链接到更大的版本]

目前，我通过查找重叠的球来检测碰撞。如果我找到两个重叠的球，我就会用它们的最小平移距离（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（） - 使用Sweep and Prune
• Pastebin：resolveCollision（） - 如果Sweep and Prune仍未删除，则进行昂贵的真实碰撞检查和解决。
• Pastebin：render（） - 仅渲染就占用了我大约45％的时间。

- Simucal

---

没有什么有用的建议可以提供，但我对你表示尊重和钦佩。看起来是一项非常出色的工作。很抱歉我没有更多可以提供的帮助。 - duffymo

渲染几百个球，不应该占用你45%的CPU，除非你在进行软件渲染。也许你应该使用利用视频卡的矢量图形。 - Robert Gould

是的，我刚刚在一台核心2双核1.83GHz的电脑上运行了它，配备了Vista操作系统和最新版本的Java，现在球体彼此碰撞了。我必须说这是一个相当酷的模拟。 - dotjoe

哇，这巧合有点神奇。我正在为.NET构建一个非常相似的库！ - RCIX

我知道这已经有点老了，但我正在尝试在JavaScript中实现Sweep and Prune算法，你的代码对我帮助很大。谢谢你。顺便问一下，你是否将此项目修改为更高效的模拟？ - jonathancardoso

Answer 1

简单的方法是不要测试对象与对象之间的碰撞，而是用每个球的中心点填充一个数组。然后，从每个中心扫描一个以该点为中心、大小为4*半径的正方形（您可以通过不使用正方形来优化这个过程，但会使代码更加复杂）。如果在这个正方形内有另一个中心，则只需要检查它们是否相距2*半径（因此发生碰撞）。您还可以通过减少分辨率、四舍五入球的位置来进一步优化，从而减少需要执行的检查次数。

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

- patros

---

在http://www.metanetsoftware.com/technique/tutorialB.html上有一个相当不错的解释。 - Nikhil

在分子模拟中，我们经常使用cell_list作为起点来创建一个包含相邻粒子对的列表。但也许这对于这个项目来说有些过度了。http://en.wikipedia.org/wiki/Verlet_list - nielsle

Answer 2

跟踪附近的球 -

就像插入排序由于每帧最小的更改而是最优的一样，您可以利用相同的属性来跟踪球“邻居”

每个球最多只能与可能的6个其他球交互。 您可以大约每10帧运行一次算法，找出每个球有哪些邻居，然后使用该信息计算下一个10帧中的实际碰撞。

您还可以跟随每个球的向量，绘制虚拟线，并查看哪些线在接下来的3-5帧中相交，仅计算可能发生的碰撞（尽管由于时间很少发生）。

就像您按x轴排序一样，您可以将球“分组”到主窗口内的子分区中。 当一个球至少被一个球直径所包含时，它只需要查看相同子分区中的球。 如果它靠近边界或两个边界，您需要查看一个或两个其他子分区，但应该少做一些计算。

此外，这些子分区可以动态定位，因此平均子分区仅具有100个球 - 没有必要具有不同数量的球的相同大小的子分区。

根据分区拥挤的程度（每平方单位球数），您可能会尝试不同的算法 - 稀疏填充的框只需要向量计算来预测碰撞，而密集填充的子分区可能仅需要某种优化的六角形计算。 稀疏框在很多帧中可能不需要碰撞检测（因为与在密集人口的框中一样，重叠不会被多注意）。

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

-亚当

- Adam Davis

Answer 3

硬核物理引擎使用浮点向量化，如果幸运的话，可以在当前硬件上提供16倍的性能提升，并且在专门的硬件上可以获得更多的性能提升。例如，Larrabee可以处理1024个同时计算以进行理论上的x1024倍的数学处理(但它需要这样做是因为它还是GPU)。

我还没有看过代码，但您是否正在使用像快速平方根和二进制绝对值、位符号翻转等数学优化技术？单独使用这些技术并不能帮助你，但当你处理大量数据时，这些技术会将一些数学重定向到主CPU，从而释放FPU，基本上给你一个更大的吞吐量。

此外，GCC的SIMD代码生成简直太糟糕了，我曾经通过使用VC或IntelCompiler获得高达16倍的性能提升，这意味着，如果您注意到了，GCC根本不使用任何SIMD指令！

此外，那些所谓的10k碰撞并没有在您模拟的那么密集的区域内发生，因此不能直接进行比较。

- Robert Gould

---

最新的GCC似乎有一个-ftree-vectorize选项（由-O3隐含），以及一个相关的-ftree-vectorizer-verbose=n选项，可以在它不起作用时提供更多信息。或者你可以使用编译器内置的SIMD特性来显式调用（第一个谷歌搜索结果为“gcc simd”）。 - Wim Coenen

Answer 4

一旦一个球被其他球完全包围，就停止考虑它进行碰撞检测。从你的截图中看，似乎只有“表面”球应该被考虑。为什么要检查球6个深度，而这些球不可能发生碰撞？这将大大减少潜在的碰撞次数。

- richyrich

Answer 5

你的主要问题在于碰撞解决算法--你可以加快绘制和碰撞检测的速度，但这并不能阻止球互相碰撞。这个问题比看起来要难以干净地解决得多；但是有可能做得对。

在你的情况下，在失败的配置（大球桶）中，你的对象应该真正相互滑动，而不是弹跳。滑动是一种连续的约束，与你的实现处理的基于脉冲的约束不同。

最简单的防止崩溃的方法是，在执行碰撞处理之后重新检查所有碰撞的对象，以确保它们不会相互穿透--必要时可以迭代多次，直到没有一个违反约束为止。这当然需要更长时间--可能要花费更长的时间（甚至可能会引起无限循环，尽管在那种特定情况下可能不会...）。

有好的算法可以使你的模拟行为良好，但它们比你的基于脉冲的系统更复杂。一般来说，它们涉及将相互作用的物体（如桶中的球）视为一个整体，并调整它们的集体配置以满足它们的相互约束。

你应该寻找关于多体模拟的作品（书籍、论文、网站）。我无法说哪一个对你的目的最有用；如果我是你，我会先去一所好的大学图书馆，浏览他们在这个主题上的任何书籍。你应该准备好一些严肃的数学；如果像“Lagrange乘数”这样的术语让你感到瘙痒，那就小心8^)。基本上，如果你选择这条路，你可能会学到很多数学，还有不少物理知识。

- comingstorm

---

是的，我同意你所说的。我研究了各种流行的物理引擎如何处理它，这可能会变得非常复杂。在 Box2D 中仔细研究连续碰撞检测代码后，我能够大致理解他们在做什么，但我需要时间来处理数学问题。 - mmcdole

感谢您的回答，这是在SO上非常好的第一个答案！+1 - mmcdole

Answer 6

现在这个情况开始听起来像是一个受重力影响的略微可压缩流体。使用欧拉视角的计算流体力学思想可能会有所帮助。如果你创建一个网格，使得每个单元格一次只能容纳一个球，那么你可以为每个单元格编写质量、动量和能量守恒平衡方程，并通过这种方式跟踪球的运动。

- duffymo

Answer 7

我一直在关注Chipmunk的发展，据我所知，优化的答案在数据结构中（不是吗？）...

Chipmunk用于实现this的数据结构是Spacial Hash。

- Nick

Answer 8

尝试这个：

将你的矩形分成N*M个小正方形，使得这些小正方形略宽于一个球的半径。最好让这些小正方形覆盖矩形的边缘，而不是完全适应其中。

创建一个BitSet数组。不要使用Bitset[M][N]，只需使用new Bitset[M*N] - 一点乘法不会伤害你。

用一个数字来标识每个球。当你将一个球放在某个位置时，设置该正方形及其周围8个正方形的位（为了更容易地实现这一点，扩展你的正方形数组，使其超出矩形的边缘一格 - 这样你就不必剪裁了）。

遍历所有正方形。对于每个正方形中的每对球，将该对标记为潜在碰撞。为此，创建一个BitSet，并假设你有H个球和球A、B占据同一个正方形，则设置位A+BH和AH+B。

现在查找潜在碰撞已经很容易了，因为BitSet包括一个方法，它说“找到在此之后被设置的下一个位”。请记住，每个位都是双重计数的，所以当检测到位Q被设置时，请确保取消设置配对的另一个位(Q%H)*H + (Q/H)。

或者：您可以轻松地折叠碰撞数组。A和B之间的碰撞-假设A>B-可以通过设置位A * (A-1) / 2 + B来标记。这样做的好处是您不需要关心球的总数。

实际上：忘了吧。只需使用我编写的这个类作为练习：

import java.util.BitSet;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class PairSet extends BitSet implements
    Iterable<PairSet.Pair> {
  public static class Pair implements Comparable<Pair> {
    public final int a;
    public final int b;

    private Pair(int a, int b) {
      if (a < 0 || b < 0 || a == b) { throw new IllegalArgumentException(
          "Pair(" + a + "," + b + ")"); }
      if (a > b) {
        this.a = a;
        this.b = b;
      } else {
        this.a = b;
        this.b = a;
      }
    }

    public String toString() {
      return "Pair(" + a + "," + b + ")";
    }

    public int hashCode() {
      return a * (a - 1) / 2 + b;
    }

    public boolean equals(Object o) {
      return o instanceof Pair
          && hashCode() == ((Pair) o).hashCode();
    }

    public int compareTo(Pair o) {
      return hashCode() - o.hashCode();
    }

  }

  PairSet() {}

  PairSet(BitSet z) {
    or(z);
  }

  PairSet(Iterable<Pair> z) {
    for (Pair p : z)
      set(p);
  }

  public void set(Pair p) {
    set(p.a, p.b);
  }

  public void clear(Pair p) {
    clear(p.a, p.b);
  }

  public void set(int a, int b) {
    if (a < 0 || b < 0 || a == b) { throw new IllegalArgumentException(
        "add(" + a + "," + b + ")"); }
    if (a > b) {
      set(a * (a - 1) / 2 + b);
    } else {
      set(b * (b - 1) / 2 + a);
    }
  }

  public void clear(int a, int b) {
    if (a < 0 || b < 0 || a == b) { throw new IllegalArgumentException(
        "add(" + a + "," + b + ")"); }
    if (a > b) {
      clear(a * (a - 1) / 2 + b);
    } else {
      clear(b * (b - 1) / 2 + a);
    }
  }

  public Iterator<Pair> iterator() {
    return new Iterator<Pair>() {
      int at       = -1;
      int triangle = 0;
      int a        = 0;

      public boolean hasNext() {
        return nextSetBit(at + 1) != -1;
      }

      public Pair next() {
        int nextat = nextSetBit(at + 1);
        if (nextat == -1) { throw new NoSuchElementException(); }
        at = nextat;
        while (triangle <= at) {
          triangle += a++;
        }
        return new Pair(a - 1, at - (triangle - a) - 1);

      }

      public void remove() {
        throw new UnsupportedOperationException();
      }
    };
  }
}

这将很好地跟踪您的潜在碰撞。伪代码如下：

SW = width of rectangle
SH = height of rectangle
R = radius of balls + 1 // +1 is a fudge factor.

XS = number of squares across = SW/R + 4; // the +4 adds some slop
YS = number of squares hight = SH/R + 4; // the +4 adds some slop

int sx(Point2D.Float p) // the square into which you put a ball at x
   // never returns a number < 1
 := (int)((p.x-R/2)/R) + 2;

int sy(Point2D.Float p) // the square into which you put a ball at y
   // never returns a number < 1
 := (int)((p.y-R/2)/R) + 2;

Bitset[] buckets = new BitSet[XS*YS];
{for(int i: 0; i<buckets.length; i++) bukets[i] = new BitSet();}

BitSet bucket(int x, int y) {return bucket[y*XS + x]}
BitSet bucket(Point2D.Float p) {return bucket(sy(p),sx(p));}

void move(int ball, Point2D.Float from, Point2D.Float to) {
  if bucket(from) == bucket(to) return;
  int x,y;
  x = sx(from); y=sy(from);
  for(int xx==-1;xx<=1; xx++)
  for(int yy==-1;yy<=1; yy++)
  bucket(sx+xx, sy+yy).clear(ball);
  x = sx(to); y=sy(to);
  for(int xx==-1;xx<=1; xx++)
  for(int yy==-1;yy<=1; yy++)
  bucket(sx+xx, sy+yy).set(ball);
} 

PointSet findCollisions() {
    PointSet pp = new PointSet();
    for(BitSet bb: buckets) {
    int a;
    int prev_a;
    for(prev_a = -1; (a = bb.nextSetBit(prev_a+1))!=-1; prev_a=a) {
      int b;
      int prev_b;
      for(prev_b = a; (b = bb.nextSetBit(prev_b+1))!=-1; prev_b=b) {
        pp.add(a,b);
      }
    }
    return pp;
}

- paulmurray

---

实际上，您可以通过获取一个迭代器并将其实例化为可变Pair对象的引用来消除分配和释放“Pair”对象的操作。它的工作是填充指向的Pair对象的x和y。 - paulmurray

Answer 9

Simucal。我知道我回答晚了一年半，但我仍然想写下我的想法。

最近我写了一个关于与你的球重叠相同的问题的问题，实际上使用了你使用的相同算法。当我提交问题时没有看到你的问题，所以是我的错。

首先，

优化：我使用一个简单的网格分割系统，整个屏幕被划分为与最大球直径相同宽度和高度的单元格。该网格跟踪每个球所在的单元格，因此当需要进行碰撞检查时，我使用nearBy()函数填充一个列表，其中包含与我正在检查的单元格相邻的每个球的ID。

网格方法非常有效，我可以拥有多达2000个球而不会出现延迟。不过，从网格中删除和添加球有点麻烦，但这只是我实现的方式（网格基于球列表和每个球的索引位置）。

将来，我希望研究其他分区和优化碰撞检查的方法。

重叠：这里和其他地方的很多答案都建议每一帧递归地纠正碰撞。这对我来说实际上在某种程度上起到了作用。通过良好的优化，您每帧可以获得两次或三次检查，这似乎可以防止一些重叠的混乱。但它并不完美。我怀疑，通过提高准确性（使用插值和更好的积分等花哨的术语）可以帮助解决抖动和重叠问题。

我考虑根据优先级（最高的是触摸墙壁的物体，然后是与之接触的物体，接下来是优先级列表中较低的等等）来排序碰撞检查，并将其纳入到最小平移距离中。 MyPhysicsLab谈到了处理多个同时发生的碰撞，但我还没有去研究那个。

如果您找到任何信息，请更新！我正在解决完全相同的问题，球模拟器似乎非常流行。如果我们以后转向刚体物理，这种经验可能会派上用场。

谢谢。

- BlueThen

Answer 10

也许问题在于球“堆积”时有太多的交互作用？如果我在做这个，我会尝试以下方法：

• 将重力设置为0，以便不会同时发生太多碰撞
• 对您的碰撞检测算法进行分析 - 如果您正在使用排序后的球数组，并且仅分析最近的6或7个球，则不应该有任何问题...每个周期只需要大约8000次碰撞检查，假设有800个球，这并不是很多

- LuckyLindy