Houdini Vellum 之 Graph Color 的算法分析

Houdini 18 的Vellum目前使用的是更高级的PBD: XPBD(eXtended Position Based Dynamics) 。XPBD使用了2^nd Order Integration ，传统的PBD使用的1^nd  Order Intergration 。想要查看的话，如下图（默认是2^nd Order Integration)。

Vellum Solver中因为要对约束重复的运算（Constraint Iterations 设置迭代的次数），需要比较高的效率。 为了能够让并行运算，引入了Graph Corlor技术。Graph Color说白了， 就是定义一个属性，每个约束的属性和与它相邻的约束的属性值不同。

比如用一个Grid，用Vellum Contraints 得到 distant contrainsts ，然后用Graph Color节点进行计算 （结果默认写入在一个整型color属性上），最后用wrangle 显示颜色（相同的color属性颜色相同）， 如下图，能够看到，每一条边（primitive）都与相邻的边的颜色不同。 这样让颜色相同的contrainst在同一个Workset。 不同颜色，不同的Workset。这样在对constrait进行迭代计算时（是在opencl里面进行的），Opencl会根据Workset，同一个Workset才会一起平行计算。

Houdini Vellum 之 Graph Color 的算法分析

原文：https://www.cnblogs.com/peng-vfx/p/13287309.html