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