太极图形60行代码实现经典论文，0.7秒搞定泊松盘采样，比Numpy实现快100倍

wju***

　　现在，太极图形基于Taichi实现了一个超快算法，同样的效果运行在单个CPU线程上，只需要0.7s就能生成这样的图案，快了100倍左右。


　　一起来看看他们是怎么做的。


　　采用Bridson算法实现


　　此前，有一种常见算法是dart throwing（像一个人蒙上眼睛胡乱扔飞镖的样子）：


　　每次在区域内随机选择一个点，并检查该点与所有已经得到的点之间是否存在“冲突”。


　　若该点与某个已得到的点的最小距离小于指定的下界，就抛弃这个点，否则这就是一个合格的点，把它加入已有点的集合。


　　重复这个操作直到获得了足够多的点，或者连续失败了N次为止（N是某个设定的正整数）。


　　但这种算法的效率很低。


　　因为随着得到的点的个数增加，冲突的概率越来越大，获得新的点所需的时间也越来越长，每次比较当前点和所有已有点之间的距离也会降低效率。


　　相比之下，Bridson算法则要更加高效。


　　这个算法的原理来自于Robert Bridson发表于2007年的论文”Fast Poisson Disk Sampling in Arbitrary Dimensions”[1]（论文非常短，只有一页A4纸），如果再去掉标题、引言的话，真正的算法内容只有一小段话。


　　开头这个动图，演示了Bridson圆盘采样算法在一个400x400的网格区域上的运行效果，算法尝试获得100K个均匀散布的点，实际生成了大约53.7K个：


　　这个动画是使用Taichi生成的，运行在单个CPU线程上，除去编译的时间计算，耗时仅在0.7s多一点，而同样的代码翻译成NumPy要耗时70s左右。[2]


　　从上面的动画效果可见，Bridson算法很像包菜的生长过程：我们从一个种子点开始，一层一层地向外添加新的点。


　　每一次我们添加的新的点，都位于最外层的点的周围，并且尽可能地包住最外层。


　　为了避免每次都检查和所有已有点之间的距离，Taichi采用了所谓网格化的技巧：


　　将整个空间划分为网格，对一个需要检查的点，只要找到它所在的网格，然后检查它和临近网格中的点之间的最小距离即可。


　　taichi只要这个距离大于指定的下界，更远处的点就不必再检查了。这个技巧在图形学和物理仿真中是非常常用的。taichi https://taichi-lang.cn/