在三维网格形变算法中,个人比较喜欢下面两个算法,算法的效果都比较不错, 不同的是文章[Lipman et al. 2005]算法对控制点平移不太敏感。下面分别介绍这两个算法:
文章[Lipman et al. 2005]提出的网格形变算法需要求解两次稀疏线性方程组:第一个方程定义了网格上离散坐标系之间的关系,通过求解该方程可以重组每个顶点的坐标系;第二个方程记录了顶点在局部坐标系的位置信息,通过求解该方程可以得到每个顶点的几何坐标。
在网格顶点建立局部坐标系(b1i,b2i,Ni),i∈V。对于(i,j)∈E,定义差分算子δ:
δj(b1i) = b1j – b1i
δj(b2i) = b2j – b2i
δj(Ni) = Nj – Ni
将差分算子表示为b1i,b2i,Ni的形式:
δj(b1i) = C11ijb1i + C12ijb2i + C13ijNi
δj(b2i) = C21ijb1i + C22ijb2i + C23ijNi
δj(Ni) = C31ijb1i + C32ijb2i + C33ijNi
进一步表示为:
b1j = (C11ij+1)b1i + C12ijb2i + C13ijNi
b2j = C21ijb1i + (C22ij+1)b2i + C23ijNi
Nj = C31ijb1i + C32ijb2i + (C33ij+1)Ni
上式为第一个方程,记录了网格上离散坐标系之间的关系,其中的系数可以由原始网格得到。
xj -xi= <eij , b1i >b1i + <eij , b2i >b2i + <eij , Ni >Ni
上式为第二个方程,记录了顶点在局部坐标系的位置信息,其中的系数也可以由原始网格得到。
算法效果:
文章[Sorkine et al. 2007]提出了ARAP的网格形变算法,网格顶点的一环邻域三角片组成一个单元(Cell),当顶点i对应的单元Ci变形为Ci’时,定义其刚性(rigidity)能量函数为:
网格上所有单元的刚性能量之和为:
根据能量函数,算法实现过程分两步进行迭代,第一步更新Ri,第二步更新 pi’,下面为具体推导过程。
1.更新Ri:
设eij = pi - pj,那么能量函数E(S’)可以表示为:
忽略不含Ri的项,那么:
定义协方差矩阵Si:,将Si奇异值分解:Si = UiΣiViT,那么Ri = ViUiT。
2.更新pi’:
权重wij和wi分别为:wij = 1/2(cotαij + cotβij),wi = 1。我们将E(S’)对pi’求偏导,并令其等于零:
上式中wij = wji,于是,那么我们可以得到:
上式相当于求解稀疏矩阵方程组。
算法效果:
本文为原创,转载请注明出处:http://www.cnblogs.com/shushen。
参考文献:
[1] Y. Lipman, O. Sorkine, D. Levin, and D. Cohen-Or. 2005. "Linear rotation-invariant coordinates for meshes." In ACM SIGGRAPH 2005 Papers (SIGGRAPH '05) 24:3 (2005), 479-487.
[2] O. Sorkine and M. Alexa. "As-Rigid-As-Possible Surface Modeling." In Proc. of Eurographics Symposium on Geometry Processing. Aire-la-Ville, Switzerland: Eurographics Association, 2007.