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/
