什么是lloyd relaxation？

就是把一堆聚集的点重新调整，直到“均匀分布到空间”。

【资料图】

输入：点集

输出：点集

Houdini中的Point Relax节点似乎就是这个功能。

具体算法？

1.将每个点移动到此点的Voronoi几何体“中心”。

（中心可以是很多种，算术平均点，重心....）

2.重复迭代。

(由于每次移动后voronoi几何体和周围点都可能移动了，所以还能进行下一次迭代。)

3.迭代直到error收敛。

（error为一次迭代中，所有pArr[i]的移动距离总和）

什么是voronoi几何体？

在空间中，每个空间点sample都有在点集pArr中距离最近的一点pArr[i],所有sample的集合就是此pArr[i]的voronoi几何体。

由于点集有限，当sample趋近于取满全部空间时，由于距离判断的性质，一定会形成一条明显的分界“线”，所以一定是几何体。

最简暴力算法？

在空间中铺满合理个数的离散sample点，用离散sampleArr代替voronoi几何体，用sampleArr的算术平均就成为了voronoi几何重心。

relax前，准备好wholeSample点：

迭代直到error为0：

有点类似AI，恐怕可以固定pArr数量，训练一个神经网络去一步到位。