As-rigid-as possible shape manipulation：优化1——Igarashi09论文代码实现
- 2019 年 10 月 8 日
- 笔记
由于[1]使用了边的结构，我们需要使用新的数据结构。重新思考[1]中的讲述。对于如下的示例。
我们考察边
，当边不是边界点时都有四个邻接点。如下。
但是当
是图形的边界，则邻接点只有三个。
所以这里首先简单的声明两个数据结构表示这两种边。
另外，我们还要声明控制点的数据结构，由于[1]中的控制点除了要包含他的坐标，还需要知道这个点所在的三角形及其在该三角形的质心坐标。
因为[1]中末尾介绍到如果用户点击到图形内的某个三角形内部时，我们需要得到该点所在的三角形的三个角点，令这三个角点作为三个控制点。如下所示。
红色点为鼠标点击的位置，绿色点表示红色点所在三角形的三个角点。
再看论文[1]中第7页提到的
显然
即由每条边
的邻接点坐标组成的。
在表示边
的结构体中加入
，以及计算
的函数。
现在声明Mesh类，以表示整个图形，以及图形内部关于变形的计算。
[1]中第11页第6章说到需要在图形读取、点击控制点、变形期间预计算几个矩阵。具体请见前篇文章末尾。
在Mesh类中，声明了点集、三角形集合、边界边集合、内边集合、控制点集合。
然后声明了几个需要预计算的矩阵，以及计算他们的函数。如，
另外，还定义了一个mPMesher用来求解控制点在三角形中的质心坐标。而求解控制点质心坐标的算法中需要向mPMesher中加载所有的点和三角形。没必要在每计算一次质心坐标都要加载一次，所以，在Read()函数中通过函数preComputeBarycentric()提前定义mPMesher。
我们看这两个函数preComputeBarycentric()和computeBarycentric()。
在这里，我们使用第三方库GTEngine[3]来计算质心坐标。
对computeBarycentric()需要简单说明一下，由于GTEngine计算质心坐标的算法分为两种，一种是针对图形边界多边形是凸多边形，这种情况需要GetContainingTriangle()函数就可以计算该控制点所在的三角形的序号，这个函数相对快一些。另一种情况是非凸多边形，这种情况就只能遍历所有三角形，找到包含该控制点的三角形序号，这种情况就比较慢了。所以我们定义了一个预处理指令CONVEX_MODEL。
现在考虑这几个预计算的矩阵该在什么阶段计算。
首先，按照论文[1]中说法，A₁上半部分L₁、A₂上半部分L₂都可以在读取Mesh的函数Read()中预计算。再看一下A₁、A₂的构成。
A₁上半部分L₁、A₂上半部分L₂都是由原始Mesh中的点坐标构成的。
我们使用第三方库OpenMesh[4]来读取Mesh文件，并使用半边数据结构来读取边界边、内边及其邻接点。先看Read()函数。
在Read()函数中，首先读取所有的点，然后按照模型中是否边界为条件，分别读取边界边和内边。最后读取所有的三角形的三个角点的序号。
之后我们预计算几个矩阵。接下来看下面两个预计算函数。
buildA1top()函数。
buildA2top()函数。
接下来看显示和交互的程序。绝大部分显示、交互的代码都和前几篇文章对Igarashi 05年[2]的代码类似。
[1]中说到，在用户点击控制点时，生成A₁下半部分C₁、A₂下半部分C₂，还有计算每个控制点的质心坐标。
由上篇文章的勘误，[1]中末尾说到如何构造A₁和A₂的下半部分。
buildA1bottom()函数。
buildA2bottom()函数。
用户拖拉控制点使图形变形时，这时要实时的构建b₁，b₂。还要计算出变形后所有点的坐标。
看一下b₁，b₂是如何构造的。
b₁的上半部分是边向量坐标，都是0。下半部分由控制点的坐标构成。
buildB1()函数。
b₂的上半部分是由原始的边向量经过第一步变换后的向量坐标组成，下半部分由控制点坐标构成。
buildB2()函数。
最后，我们看如何通过上面构造的矩阵来对图形做变形。
SimilarityTransformation()函数，表示[1]中的第一步，相似变换。
ScaleAdjustment()函数，表示[1]中的第二步，尺度适配。
前篇文章提到，[1]和[2]的原理类似，实现效果有些许不同。在[1]中，作者提到，该文的算法适用于均匀的三角形模型。
所以，我们使用一个特别均匀的网格模型来展示其效果。
该文所有代码都已开源，地址为：
https://coding.net/u/forestsen/p/ARAPShapeManipulation
引用
[1] Igarashi T , Igarashi Y . Implementing As-Rigid-As-Possible Shape Manipulation and Surface Flattening[J]. Journal of Graphics Gpu & Game Tools, 2009, 14(1):17-30.
[2] Igarashi T . As-rigid-as-possible shape manipulation[J]. ACM Trans. Graph. 2005, 24.
[3] https://www.geometrictools.com/
[4] http://openmesh.org/
