一種四邊形網格上的Midedge細分格式

檀結慶 ，曹寧寧

（1.合肥工業大學數學學院，安徽合肥230601；2.合肥工業大學計算機學院，安徽合肥230601）

0 引 言

曲面細分就是通過對給定控制網格M的迭代計算，不斷加細原有網格，或保留原有控制頂點（插值型），或去除原有控制頂點（非插值型），生成一系列不斷加細的網格M1，M2，…，Mn，…，最終收斂到極限M∞。曲面細分由于格式簡單，只涉及局部計算，被廣泛應用于具有良好流線型性質的曲面設計、游戲、視頻場景的快速重建等幾何造型領域，以及醫學圖像的多分辨率分析，通過細分可得到醫學圖像的分層細節。

每一步細分過程都可分成兩部分：拓撲上的分離，決定每一步控制網格的變化（連線規則）；幾何上的規則，決定新網格點的計算方式。

由此看來，新的細分格式至少可通過2種方法得到：改變其拓撲規則或幾何規則。改變拓撲規則比較著名的細分格式主要有：四邊形網格細分中由CATMULL等［1］提出的分離因子為1-4的CC格式，PETERS等［2］提出的因子為 1-2的Midedge格式，LI等［3］提出的因子為1-2的格式；三角形網格中有LOOP［4］提出的因子為1-4的loop格式，KOBBELT［5］提出的因子為1-3的格式，VELHO 等［6］提出的4-8格式；此外，六邊形網格的細分格式中還有CLAES等［7］的 1-3切角細分格式,和鄭立垠等［8］提出的1-4砍邊格式。在細分的幾何規則方面：通過探求不同基函數，如拉格朗日函數、B樣條函數的性質,得到不同細分掩模的格式，而曲面細分控制頂點的空間分布多樣性，則可通過改變細分模板得到許多不同的曲面細分格式。如KOBBELT［9］提出的加參數后的四邊形網格細分格式，可視為對CC格式模板的改變；DYN等［10］提出的分離因子為1-4的Butterfly格式，即為對Loop格式模板的更改。

本文基于分離因子為1-2的Midedge細分格式的拓撲規則，使用新的幾何規則對四邊形的每一條邊插入中點，并依次相連，然后去除原先的點，如此構成新的四邊形網格。

1 細分格式的來源

要想得到新的細分格式，只能從改變細分的拓撲規則或幾何規則入手。新的細分規則既要保證網格加細前后的拓撲結構不變，又要保證所選模板的對稱性和唯一性。對稱性，是指模板中的點相對于要插入的點具有相同的位置關系，其掩模相同；唯一性，是指細分規則設定好后，插入的新點的計算結果唯一。

圖1 四邊形網格細分的拓撲規則Fig.1 Topological rules for subdivision of quadrilateral meshes

圖1為現有的一些細分格式的拓撲規則。本文將新的細分格式的構造轉到對幾何規則的改變上，即構造一種全新的插入點的計算方式。通過對比三角形細分格式中的 Loop格式［4］和 Butterfly格式［10］（見圖2）易發現，同為三角形網格細分的中點格式，其主要區別為生成新點的模板不同。相應的細分掩模（僅列出插值型）為：

（1）Loop格式掩模：

（2）Butterfly格式掩模：

模板選取時首先要滿足對稱性。三角形網格在3個方向上均對稱，因此，在Loop格式模板上修改時也必須滿足3個方向對稱。Butterfly格式即為對Loop格式模板的擴張。在Loop模板的基礎上，以新加入的點P為中心，向P→P1P4，P→P4P2，P→P2P3和P→P3P1方向擴張一步，得到Butterfly格式的模板，仍保持原模板關于新加入點的三方向的對稱性。

圖3細分格式Fig.3subdivision scheme

改變一個細分的模板，就能得到計算新頂點的新幾何規則，進而得到新的細分格式?；诜蛛x因子為1-2的最簡單的Midedge細分：由一條邊上的2個點進行加權平均，得到這條邊的中點。對四邊形網格的4條邊采用同樣的方式得到相應的4個邊點，依次相連，舍棄原來的點和邊，完成1次細分。DOO等[14]還發現，連續2次細分后，就成為DOOSABIN格式。

從圖4可以看出，Midedge格式的模板就是一條線段，用線段兩端點的信息生成1個中點。本文將對這一簡單模板進行推廣。因四邊形網格為二方向網格（也有人稱四方向網格），Midedge以邊為基本單位生成新的點，按網格方向對其模板進一步擴充，只能將其延伸成類似Loop格式的模板，即如圖5（a）所示的模板，由6個點生成1個點。 此模板仍具對稱性，且已有網格中每條邊生成的點是唯一的。本文采用圖5（a）所示的模板，雖然可對此模板進行擴充，但由這20個點生成1個邊點，有些浪費和煩瑣了，與實際應用所要求的簡單快捷不符，不再繼續討論。

圖4 Midedge細分Fig.4 Midedge subdivision scheme

圖5 對Midedge格式模板的擴充Fig.5 Stencil extension of Midedge subdivision scheme

2 新的Midedge格式

本節，將以圖5（a）所示的新的模板為基準，確定新的細分格式的掩模。

由圖5（a）知，細分掩模要滿足對稱性，則生成新的邊點的掩模應具有以下形式：

其中，2α+4β=1。

由于模板的對稱性，可將其中一個方向（這里顯然是橫向的）上的值看作1個定值，則可將問題轉化為 3 點問題，即可將P1與P4，P5與P6，P2與P3分別看作1個點，這樣原來的曲面細分為由3個點生成1個中間點的問題。本文采用三點二重的逼近型細分格式［15］來解決此問題。三點二重細分格式的形式如下：

其中，a1+a2+a3=1。

若令a1=m,a2=1-m-n,a3=n，則此三點二重格式的細分掩模為

[…,0,m,n,1-m-n,1-m-n,n,m,0,… ]，可通過曲線細分的生成多項式的相關充分條件［16］求得，也可通過4次B樣條生成多項式直接得到于是可得即三點二重格式的細分掩模為

插入點的位置如圖6所示。

圖6 三點二重曲線細分格式的插入點位置Fig.6 Position of the insertion point of three point binary curve subdivision

回顧之前的目標，是為了用3個點生成1個新的中間點，于是，令

綜上所述，有

于是，確定此細分格式的掩模，新的Midedge格式的幾何規則為

2步的Midedge格式就是一種Doo-Sabin格式。因此，將本文提出的新的Midedge格式應用于2步，便是如圖7所示模板的細分。由圖7知，2步Midedge格式可以生成P點，但空心點P14,P41,P44對生成P點并未做貢獻；其他3個點可用同樣的方式計算。P的細分掩模如下：

圖7 2步的Midedge格式Fig.7 Two-step-Midedge subdivision scheme

3 細分的連續性

定理［17］設細分矩陣S是一個n×n矩陣，λ1,λ2,?…,λn是 矩 陣S從 大 到 小 排 列 的 特 征 值 ，v1,v2,?…,vn分別是對應于特征值的特征向量，若滿足：

（1）1=λ1＞λ2=λ3＞λ4，并且λ2的幾何重數與代數重數都是2；

（2）矩陣S對應于v2,v3的特征映射

是單射且正則的（det(?ψ(u,v,j)/?(u,v))≠ 0）。其中Ω是J個單位正方形在一定拓撲結構下構成的參 數 空 間 ，j∈ (1,J),u,v∈ (0,1)，b(u,v,j)是 一個以方程為元素的n維行向量，滿足其 中bk(u,v,j)∈C1(Ω) 是b(u,v,j)的第k個元素。則細分矩陣S對應的細分格式的極限曲面是正則的，即C1連續。

細分矩陣的確定：首先要選取合適的初始控制網格M0，在給出的掩模矩陣S下，進行細分，生成新的有著同樣拓撲的控制網格M1，如此往復，構成迭代形式：

其中i為正整數。

從圖7中可以看出，由于單一Midedge格式拓撲規則的特殊性，一個標準的n×n網格無法生成標準的m×m網格。于是，用2步Midedge格式，計算細分矩陣S2。若S2的特征值已知，由矩陣的性質易得S的特征值（前者特征值是后者的平方）。

2步Midedge格式，要想選取的模板在細分矩陣S2加細下循環迭代，須選取6×6的網格點。因此，2步Midedge格式的細分矩陣S2應該是36×36的。參照圖8，給出細分矩陣S2的形式：

其中

則S2應是(S1,S2,S3,S4)構成的分塊循環矩陣，Si(i=1, ??2, ??3, ??4)為 9 × 9 的 矩 陣 。 由 式（7）得

經計算，得到細分矩陣S2的特征值從大到小依次為：由于細分矩陣S2對應的特征映射無法用具體代數形式表示，可通過分析其特征值及對應于第二、第三特征值的特征映射構成的特征環（見圖9）的性質，判斷其單射性和正則性。

圖9 新的Midedge格式正則區域的特征環Fig.9 Characteristic rings of Midedge subdivision in regular regions

特征映射指將原來的參數化網格映射到[v2v3]所構成的新網格上，即將如圖8所示的細分矩陣S2的初始網格映射到如圖9所示的[v2v3]所構成的新網格（將[v2v3]看作二維點所構成的列向量）上。另外，從圖9所示的細分矩陣S2的特征環中可以看出，該特征映射將一個具有25個面片的網格映射為一個具有25個網格的面片，在基本的二元二階B樣條基下（即bk(u v j)取相應的B樣條基函數），特征環的邊一定是原來圖像中的邊，說明該特征映射是單射的。至于特征映射的正則性，其實就是相應的雅可比行列式不為零。在同樣的基下，由圖8和圖9相似即可得到。所以，細分矩陣S2滿足前述2個條件，本文所提出的細分格式的極限曲面是正則的（C1連續）。

4 邊界規則和特殊點規則

4.1 邊界規則

對于非封閉的初始網格，如對圖10中的邊P22P32插入新的點，則本文所設計的細分模板便不再適用。為此，引入虛擬點P21,P31,P41，

使模板能夠適用。此即為用于本文提出的細分格式的邊界規則。

圖10 邊界處理Fig.10 Boundary treatment

4.2 特殊點規則

4.2.1 特殊點掩模

對于圖11所示的初始網格特殊點（即點的價不再是標準的4），細分時所對應的掩模也要有相應的變化。

此時，圖中Pk+1,Pk+2的掩模保持不變，對P1～Pk的掩模做特殊處理，P的生成規則為

4.2.2 特殊點處細分的連續性

本節，以k=3，5時的特殊點為例，驗證新的Midedge格式在特殊點時的連續性。

此時對應于價為3的特殊點，本文提出的細分格式所對應的模板如圖12所示。相應的2步細分

圖11 k價特殊點模板Fig.11 Extraordinary point stencil of the valence k

圖12 特殊點價為3時的細分模板Fig.12 Extraordinary point stencil of the valence 3

圖13 矩陣的特征環Fig.13 Characteristic rings of matrix

同理可得，k為5時所對應的細分模板，細分矩陣對應的特征環如圖14所示。相應地，2步細分矩陣為(S51,S52,S53,S54,S55)，所對應的分塊循環矩陣為，其中S5i(i=1,2,…?,5)為 9 × 9 的 矩陣?？梢郧蟪鼍仃嚨奶卣髦禐?，且各個特征值都不為0，細分矩陣對應于第2、第3特征值的特征映射構成的特征環如圖15所示，至此，驗證了價為3，5的特殊點處此細分格式所生成的極限曲面也是正則的（C1的）?？刹捎猛瑯拥姆绞津炞C其他價的特殊點，在此不再贅述。

圖14 特殊點價為5時的細分模板Fig.14 Extraordinary point stencil of the valence 5

圖15 矩陣的特征環Fig.15 Characteristic rings of matrix

5 數值實驗

圖16和圖17分別為對不含特殊點的初始控制網格使用新的Midedge格式和原始的Midedge格式細分4次后的圖像，圖18為初始網格為正方體的網格圖像細分7次后的圖像。圖19為與之對應的使用原Midedge格式的效果圖。圖21為7個正方體構成的多面體細分前后的圖像對比。圖22為與之對應的使用原Midedge格式的效果圖。

圖16 正則網格上新的Midedge細分Fig.16 New Midedge subdivison on regular mesh

圖17 正則網格上的Midedge細分Fig.17 Midedge subdivison on regular mesh

圖18 正方體網格經7次新Midedge細分后的圖像Fig.18 A cube mesh after new Midedge subdivision for 7 times

從圖21和22可以看出，本文的細分格式具有良好的收斂性和連續性。由于所提出的細分格式是一種逼近型格式，舍棄了初始網格控制點，使細分前后網格曲面大小不同。通過對比還發現，雖然新格式在大小保留上不及原始Midedge格式好，但是在特殊點處理上，新格式更為平滑，詳見圖20（為圖18、圖19特殊點處的截圖）。

圖19 正方體網格經7次Midedge細分后的圖像Fig.19 A cube mesh after Midedge subdivision for 7 times

圖20 新與原始Midedge細分局部圖Fig.20 Parts of images with new and origin Midedge subdivisions

圖21 新Midedge細分后的圖像Fig.21 Mesh with new Midedge subdivision

6 結 論

給出了一種通過擴充已有細分模板得到新的細分模板的思路，并對REIFU的Midedge細分格式進行了模板擴充，使用曲線的三點二重逼近格式，確定新模板的掩模。得到的新的Midege型逼近型曲面細分格式，具有良好的連續性，且證明了該細分格式至少是C1連續的。

圖22 Midedge細分后的圖像Fig.22 Mesh after Midedge subdivision