算法4 二维碰撞(冲量方案)

碰撞检测分为两种类型,一种是“后验的(posteriori )”离散点的碰撞检测,另一种则是“先验的(priori)”连续碰撞检测

离散碰撞检测

时间驱动模拟将时间离散成大小为dt的量子,在每个dt时间后更新每个粒子的位置,并检查是否有重叠。如果存在重叠,则将时钟回溯到碰撞时间,更新碰撞粒子的速度,然后继续进行模拟。这种方法很简单,但是有两个明显的缺点。首先,我们必须在每个dt时间范围内执行N^2/2次重叠检查。其次,如果dt太大我们可能会错过碰撞。为了确保合理准确的模拟,需要选择比较小的dt,但是这会减低模拟的速度。

离散碰撞检测的回滚操作也很麻烦,需要通过重叠的程度和粒子间的相对速度计算出重叠的时间,将产生很多额外的计算,一般情况下使用离散碰撞检测的系统都会忽略这一步骤。

连续碰撞检测

连续碰撞检测是基于整个物理系统的初始状态和影响因素建立方程组,直接预测接下来将会发生的事件:碰到墙体或与另一个粒自子碰撞?

从系统初始状态开始,预测所有即将发生的事件放入优先队列中,然后取出发生时间t最早的那个事件取出。将系统时间推进到t后碰撞模拟,处理碰撞完成后再次预测它们的实践重新放入优先队列中,如此反复。

事件驱动的物理系统中并没有固定渲染的时机。此时可以发送一个"渲染事件"放入到队列中,例如Event(null, null, t + 0.5),处理到这个事件时渲染界面,渲染时我们可以暂停50毫秒表示每50毫秒渲染一次。这种方式等价于“时间驱动模拟”中的示例代码。

连续碰撞检测对比离散碰撞检测消耗非常多的内存,碰撞次数较少的情况下性能要优于离散碰撞检测。但是碰撞次数如果非常多的话,内存和性能消耗要比离散碰撞检测消耗的更多。

  • 离散点的碰撞检测性能取决于粒子的数量还有每帧的间隔,
  • 连续碰撞检测的性能取决于粒子的碰撞次数,启动时需要耗费约 比例的时间。在之后假设一帧时间内碰撞次数为M,那么它的时间复杂度为 2MNlogN / 每帧。(每次处理碰撞时需要取出事件,一共取出M次,所以这里花费MlogN的时间。每次碰撞完后要重新预测两个粒子的下一次碰撞,这里花费2N的时间,再次放入队列需要2logN的时间,所以一共花费2MNlogN + 2MlogN),所以当每一帧内碰撞次数较多的情况时性能会很差。

碰撞预测(粒子和墙壁)

预测和墙壁的碰撞预测比较简单,只需要看对应方向的速度和墙体的距离即可,例如下面是预测垂直方向的墙体碰撞。

表示不会和墙体碰撞。

碰撞预测(粒子和粒子)

涉及高中知识,可提前预习下:解一元二次方程组,韦达定理,平面向量。

假设 分别表示粒子i和j碰撞时的位置,为碰撞时的时间,那么根据勾股定理有以下表达式: 在这里我们先预设几个将要用到的向量:

这几个向量所代表的含义:

  • :粒子间的相对速度

  • :粒子间圆心的连线(碰撞时为它们的法线,即垂直于接触平面的线)

  • :向量的点积(数量积)

将2、3行的式子带入第一行表达式有:

上面方程中,当 时, 没有正数解,所以我们得出以下结论:

由细心的网友可能发现,d好像能继续化简?并不能!

这里需要非常注意指的是向量的点积(数量积),意义明确的同时防止我们的方程组过长。而向量的点积符合乘法交换律、分配律、结合律,但是不符合消去律,所以上面的方程组无法继续化简。

处理碰撞

上面分别介绍了两种碰撞的检测方式,现在则是需要处理他们碰撞后的情况,粒子碰撞后的速度会发生什么样的变化?包括他们的方向?

处理碰撞都是通过牛顿第二定律,二维弹性碰撞可以转化为法线方向上的一维弹性碰撞。而转化方式通常有三种:三角函数,向量、冲量。

  1. 三角函数的方式最容易理解,通过计算角度的方式将模型转化为一维碰撞解决。

  2. 而向量方式其实和三角函数方式一样并没有本质上的差别,只是二维坐标的向量计算本身就是依赖勾股定理的,所以它是用各种向量计算代替了角度计算。

上面这两种方式都是使用牛顿第二定律的延伸:动量守恒和能量守恒实现的。具体可以看 wiki百科-Elastic_collision#Two-dimensional

而冲量的方式方式就比较难理解了,这也是我们接下来要讲的部分。

冲量的解决方式

涉及高中知识,可提前预习下:平面向量、冲量、牛顿第二定律。

为了简化问题,下面将二维碰撞视为法线上的以为碰撞,而涉及到的物理量都会转化为法线方向上的向量。首先要计算出法线方向上的单位向量,要做到这一点,只需要将向量除以它的模即可得到单位向量。

向量是有方向的,向量的数乘也是向量,所以只要将一个标量乘以法线方向上的单位向量即可将标量转化为法线方向上的向量(共线)。

两个向量的点积的含义是向量的投影,即用其中一个向量的长度去量化另一个向量。所以如果一个向量a乘以另一个向量b的单位向量,那么可以简单理解为将向量a的方向旋转到向量b的方向。下面例子中 即领用这个原理。

首先根据冲量的定义与牛顿第二定律,我们可以得到以下公式(下面 特指碰撞前后的速度差,而不是上面方程中定义的向量):

法线的单位向量为:

现在我们需要计算小球i和j在法线方向上的速度差,即它们碰撞前的相对速度: 而碰撞后的在法线方向上的相对速度为: e表示碰撞的恢复系数,取值为0~1。0时表示非弹性碰撞,1时表示完全弹性碰撞。因为碰撞后方向相反,所以取负号。


假设碰撞时产生的净冲量(类似合力的描述,合力也称为净力,net force)为,那么在法线方向上的冲量为

若小球i 所受到的冲量为, 那么小球j会受到一个相反的冲量

将这两条公式代入相对速度的公式,得到以下公式(单位向量的数量积结果为1,即 ): 因为在这个碰撞系统中,我们将所有碰撞视为完全弹性碰撞,所以e取值1。另外单位向量n的值一开始已经给出,代理上面的结果最终得到: 现在,让 乘上对应方向的比值即可得到该方向上的分冲量。

现在根据牛顿第二定律即可求得碰撞后的速度:(记住小球j是受到相反的冲量,所以用减)

实现粒子碰撞模拟系统

由于篇幅过长,而官网有完整代码,所以这里就不贴出完整代码,只拿关键代码进行说明。

官方完整代码,包含测试数据:https://algs4.cs.princeton.edu/61event/

实现流程

下面我们使用连续碰撞检测的方式实现一个简单的粒子碰撞模拟系统。

首先是初始化时,先遍历所有粒子,预测他们的碰撞时间,放入优先队列中。然后执行以下循环:

  1. 从优先队列中删除并取出时间t最小的事件
  2. 忽略无效事件(因为存在很多重复事件,例如A碰B和B碰A实际上是同一个事件。)
  3. 将所有粒子的时间推进到t
  4. 处理碰撞事件
  5. 重新预测事件涉及的粒子的下次碰撞,重新放回优先队列中

粒子API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Particle {
private double rx, ry; // position
private double vx, vy; // velocity
private final double radius; // radius
private final double mass; // mass
private int count; // number of collisions

public Particle(...) { }

public void move(double dt) { }
public void draw() { }

// 预测粒子碰撞的时间
public double timeToHit(Particle that) { }
public double timeToHitVerticalWall() { }
public double timeToHitHorizontalWall() { }

// 处理碰撞
public void bounceOff(Particle that) { }
public void bounceOffVerticalWall() { }
public void bounceOffHorizontalWall() { }
}

事件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
private static class Event implements Comparable<Event> {
private final double time; // time that event is scheduled to occur
private final Particle a, b; // particles involved in event, possibly null
private final int countA, countB; // collision counts at event creation


// create a new event to occur at time t involving a and b
public Event(double t, Particle a, Particle b) {
this.time = t;
this.a = a;
this.b = b;
if (a != null) countA = a.count();
else countA = -1;
if (b != null) countB = b.count();
else countB = -1;
}

// compare times when two events will occur
public int compareTo(Event that) {
return Double.compare(this.time, that.time);
}

// has any collision occurred between when event was created and now?
public boolean isValid() {
if (a != null && a.count() != countA) return false;
if (b != null && b.count() != countB) return false;
return true;
}

}

事件对象中最主要的逻辑就是判断该事件是否是有效的,因为在预测的时候存在很多重复性的预测,例如A和B碰撞还有B和A碰撞是同一个事件。为了判断这个,我们在创建事件时记录粒子的碰撞次数,如果下次处理这个事件时发现粒子的碰撞次数增加了,表示这个粒子的状态已经变化,所以废弃这个事件。

另外,事件有好几种类型:和墙壁碰撞、和另一个小球碰撞、重绘。但是我们不需要给事件加上类型的属性,只需要判断粒子是否为空即可。

  • 如果两个粒子都为空,那么是一个重绘事件。
  • 如果其中一个粒子为空,那么是和墙壁碰撞。
  • 如果两个粒子都不为空,那么就是粒子和粒子碰撞。

模拟系统

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class CollisionSystem {    
private MinPQ<Event> pq; // the priority queue
private double t = 0.0; // simulation clock time
private Particle[] particles; // the array of particles

public CollisionSystem(Particle[] particles) { }

// 碰撞预测
private void predict(Particle a) {
if (a == null) return;
for (int i = 0; i < N; i++) {
double dt = a.timeToHit(particles[i]);
pq.insert(new Event(t + dt, a, particles[i]));
}
pq.insert(new Event(t + a.timeToHitVerticalWall(), a, null));
pq.insert(new Event(t + a.timeToHitHorizontalWall(), null, a));
}

private void redraw() { }

public void simulate() { /* see next slide */ }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void simulate(){
pq = new MinPQ<Event>();
// 预测所有粒子
for(int i = 0; i < N; i++) predict(particles[i]);
// 重绘事件
pq.insert(new Event(0, null, null));
while(!pq.isEmpty()) {
// 获取下一个事件
Event event = pq.delMin();
if(!event.isValid()) continue;
Particle a = event.a;
Particle b = event.b;
// 将所有粒子的时间推进到当前事件的发生时间
for(int i = 0; i < N; i++)
particles[i].move(event.time - t);
t = event.time;
// 处理碰撞事件
if (a != null && b != null) a.bounceOff(b);
else if (a != null && b == null) a.bounceOffVerticalWall();
else if (a == null && b != null) b.bounceOffHorizontalWall();
else if (a == null && b == null) redraw();
// 继续预测
predict(a);
predict(b);
}
}

Reference

Coursera: Event driven simulation

Algs4: Event driven simulation

高中数学:平面向量

Elastic Collisions Using Vectors instead of Trigonometry

Research:Physics - Collision Response

How to Create a Custom 2D Physics Engine: The Basics and Impulse Resolution

Rigid Body Collisions