|
现在，太极图形基于Taichi实现了一个超快算法，同样的效果运行在单个CPU线程上，只需要0.7s就能生成这样的图案，快了100倍左右。 6 X- M6 j: ^, i* [
一起来看看他们是怎么做的。 * @/ {9 c6 x) o- _- o
采用Bridson算法实现 3 U y7 E4 d: N B; `
此前，有一种常见算法是dart throwing（像一个人蒙上眼睛胡乱扔飞镖的样子）：
, q+ | C" I' W3 z9 f! u' e 每次在区域内随机选择一个点，并检查该点与所有已经得到的点之间是否存在“冲突”。 1 v+ T* r' r7 G0 @
若该点与某个已得到的点的最小距离小于指定的下界，就抛弃这个点，否则这就是一个合格的点，把它加入已有点的集合。
: V: A! c- b' T/ l5 q' \' A! n 重复这个操作直到获得了足够多的点，或者连续失败了N次为止（N是某个设定的正整数）。 # |' J5 C1 M0 W+ w$ y% }1 r
但这种算法的效率很低。
% C2 S8 g8 e7 b3 c 因为随着得到的点的个数增加，冲突的概率越来越大，获得新的点所需的时间也越来越长，每次比较当前点和所有已有点之间的距离也会降低效率。
% t8 B( z8 t5 d6 ~$ K' j9 N 相比之下，Bridson算法则要更加高效。 . }: M: y- b& H: q- N; E
这个算法的原理来自于Robert Bridson发表于2007年的论文”Fast Poisson Disk Sampling in Arbitrary Dimensions”[1]（论文非常短，只有一页A4纸），如果再去掉标题、引言的话，真正的算法内容只有一小段话。 9 o" F/ [$ L: \' X4 Q8 {4 ] _
开头这个动图，演示了Bridson圆盘采样算法在一个400x400的网格区域上的运行效果，算法尝试获得100K个均匀散布的点，实际生成了大约53.7K个：
) ~* U% ]1 n9 E% o1 } 这个动画是使用Taichi生成的，运行在单个CPU线程上，除去编译的时间计算，耗时仅在0.7s多一点，而同样的代码翻译成NumPy要耗时70s左右。[2]
5 A3 d: }$ t" w9 b 从上面的动画效果可见，Bridson算法很像包菜的生长过程：我们从一个种子点开始，一层一层地向外添加新的点。
# G, u \! V, h% t$ K1 ~ o G 每一次我们添加的新的点，都位于最外层的点的周围，并且尽可能地包住最外层。 + G% ], j) m9 S i
为了避免每次都检查和所有已有点之间的距离，Taichi采用了所谓网格化的技巧：
& B6 |- P" A! Q3 ?9 z: T' C, f 将整个空间划分为网格，对一个需要检查的点，只要找到它所在的网格，然后检查它和临近网格中的点之间的最小距离即可。
% m8 J# T4 O' X) }' G8 R- ]; o taichi只要这个距离大于指定的下界，更远处的点就不必再检查了。这个技巧在图形学和物理仿真中是非常常用的。taichi https://taichi-lang.cn/
5 x. K2 r# i) y" E O | 
