算法小丑 阅读(115) 评论(0)

      在三维网格形变算法中,个人比较喜欢下面两个算法,算法的效果都比较不错, 不同的是文章[Lipman et al. 2005]算法对控制点平移不太敏感。下面分别介绍这两个算法:

  文章[Lipman et al. 2005]提出的网格形变算法需要求解两次稀疏线性方程组:第一个方程定义了网格上离散坐标系之间的关系,通过求解该方程可以重组每个顶点的坐标系;第二个方程记录了顶点在局部坐标系的位置信息,通过求解该方程可以得到每个顶点的几何坐标。

在网格顶点建立局部坐标系(b1ib2iNi),i∈V。对于(i,j)∈E,定义差分算子δ:

δj(b1i) = b1jb1i

δj(b2i) = b2jb2i

δj(Ni) = NjNi

       将差分算子表示为b1ib2iNi的形式:

δ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,于是,那么我们可以得到:

 

  上式相当于求解稀疏矩阵方程组。

  算法效果:

 

 

 

欢迎大家一起探讨计算机图形学算法问题,邮箱:shushen@126.com

本文为原创,转载请注明出处: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.