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