|
在很多粒子系统中,你希望粒子可以产生某种方式的交互作用.你可能会希望它们互相排斥,反弹或者粘着.不管是什么,把每一个粒子与其他所有其他粒子比较的过程将会非常的慢.你必须做的比较的次数和粒子个数的平方成正比.如果你把粒子的个数增加一倍,比较的次数将增加四倍.
| 粒子个数 |
比较次数 |
象表中所示,比较的次数真的非常大.例如你模拟一个10,000个星星在重力下移动,你每帧将执行149985000次乘法和49995000次平方根运算.所以,需要作任何事来减少执行比较时间或者,更好的是,减少比较的次数,这是非常值得的.
在本文中,我将介绍blockmap的概念,用来减少比较次数.它有一个缺点就是占用很多内存,并且只能应用到某些环境中,但是他带来速度的真正提高.
我第一次听说这个方法是在我学习制作Doom II.WADs.Doom使用一个block map来管理object和墙之间的碰撞检测.
blockmap背后的概念是只比较临近的粒子.整个区域别分为分离的块,然后粒子检查周围的块,看是否它们包含(其他)粒子.
如果你允许你的粒子可以在一个无限的区域中移动,你会发现你很难有效的分割空间.如果你是在3D环境中,那要注意这点.你将需要很多的块.所以这种方法比较适合于有效的空间和2D,例如Doom.
一个快速预览
这样你可以把空间分成块.每个块有能力支持一个在它里面的粒子的列表.每帧的开始,你清空每个快中的数据.把所有粒子循环一遍,然后决定
它属于那个块.把块中包含的粒子标记在块中.下一个,你循环所有被修改的块,如果一个块中包含粒子超过一个,那个你可以在这些粒子之间执
行执行你的交互作用.
一个例子
这里有一个4*4的blockmap,包含三个不同尺寸的粒子.
绿色的一个覆盖在d1块.
黄色的一个覆盖a2, a3, b2, b3
红色的覆盖b3, b4, c3, c4 |
| 1 |
0 |
| 2 |
1 |
| 3 |
3 |
| 4 |
6 |
| 5 |
10 |
| 6 |
15 |
| 7 |
21 |
| 8 |
28 |
| 9 |
36 |
| 10 |
45 |
| 11 |
55 |
| 12 |
66 |
| 13 |
78 |
| 14 |
91 |
| 15 |
105 |
| 16 |
120 |
| 17 |
136 |
| 18 |
153 |
| 19 |
171 |
| 20 |
190 |
| 50 |
124750 |
| 100 |
499500 |
| 500 |
124750 |
| 1000 |
499500 |
| 5000 |
12497500 |
| 10000 |
49995000 |
于是每个块被标记所包含的粒子为:
现在你有两个选择:
* 查看每个块,检查在它里面是否有超过两个例子,如果有,在所有这些粒子之间执行比较.这最好是在几乎所有块都包含粒子的情况下执行.我们从小图中可以看到b3中包含两个粒子.所以你指导这两个粒子可能接触.
* 查看每个粒子,计算(再一次)它在那个块中然后检查是否有其他粒子在这些块中,如果有,在它们之间执行比较.这最好是在粒子在区域中分布很稀疏的情况下执行.
块结构
你将如何存储这些块呢,这将取决于你的粒子系统.
随便的写一个你可以为空间空有限个粒子分配块的结构:
structure BLOCK
INT number_of_particles
POINTER p1, p2, p3, p4, p5
end structure
或者,你可以使用一个链表:
structure BLOCK
INT number_of_particles
POINTER first_particle
end structure
如果你能确定在一个块中决不会超过5个粒子,那个用第一种方式很不错.但是,如果你不能确定,你最好使用第二种,尽管它可能比较慢.
Notes on BlockMaps
一点需要注意,相当很容易的,偶尔你会比较两个粒子两次.想像一下如果黄色的块比一个块更大.blockmap象这样:
如果你不仔细处理,你的程序将认为红色和黄色的粒子碰撞了两次.这种情况可能会没问题.如果它产生了问题,你将必须从前措施避免它.
blockmap只适合于短距离交互作用的粒子系统,象桌球.长距离或者无限距离的系统,象有引力的星体最后留给引力方法去处理.
| |
