Abstract: One of the key technology of character animation editing is not only to achieve as-rigid-as-possible shape deformation, but also real-time operations. Computing in the shape manipulation, by defining the square difference metric of vertex neighborhood and face neighborhood on mesh, coordinates separation of free and constrain vertex is simplified. This algorithm can solve x and y coordinates independently in general fitting. In the implementing, the design of appropriate chain structure of coefficient matrix and constant vector. Duplication of data computing is reduced by indexed storage of sparse matrix and conjugate gradient method. Experiments show that in the ordinary personal computer to about 1000 mesh vertexes can be deformed in real-time interaction.

Key words: as-rigid-as-possible shape manipulation, least squares of vertex-neighborhood, coordinates separation, sparse linear system

摘要： 角色动画编辑的核心技术之一，是形状既能实现刚性变形，又能实现实时操作。在形状刚性操作计算中，通过定义三角网格顶点的面邻域和点邻域的平方差度量，简化自由顶点与约束顶点的坐标分离。这种表示法，在整体拟合中使得x坐标与y坐标能够独立求解。在算法实现中，设计恰当的系数矩阵和常数项向量的链表结构，采用矩阵索引存储和共轭梯度求解，减少数据的重复计算。实验表明，在普通的PC机上能够实现约1 000个顶点的网格实时交互变形操作。

关键词: 形状刚性操作, 点邻域平方差, 坐标分离, 稀疏线性方程组