一種四邊形網(wǎng)格上的Midedge細(xì)分格式

檀結(jié)慶 ，曹寧寧

（1.合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽合肥230601；2.合肥工業(yè)大學(xué)計算機(jī)學(xué)院，安徽合肥230601）

0 引 言

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

每一步細(xì)分過程都可分成兩部分：拓?fù)渖系姆蛛x，決定每一步控制網(wǎng)格的變化（連線規(guī)則）；幾何上的規(guī)則，決定新網(wǎng)格點(diǎn)的計算方式。

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

本文基于分離因子為1-2的Midedge細(xì)分格式的拓?fù)湟?guī)則，使用新的幾何規(guī)則對四邊形的每一條邊插入中點(diǎn)，并依次相連，然后去除原先的點(diǎn)，如此構(gòu)成新的四邊形網(wǎng)格。

1 細(xì)分格式的來源

要想得到新的細(xì)分格式，只能從改變細(xì)分的拓?fù)湟?guī)則或幾何規(guī)則入手。新的細(xì)分規(guī)則既要保證網(wǎng)格加細(xì)前后的拓?fù)浣Y(jié)構(gòu)不變，又要保證所選模板的對稱性和唯一性。對稱性，是指模板中的點(diǎn)相對于要插入的點(diǎn)具有相同的位置關(guān)系，其掩模相同；唯一性，是指細(xì)分規(guī)則設(shè)定好后，插入的新點(diǎn)的計算結(jié)果唯一。

圖1 四邊形網(wǎng)格細(xì)分的拓?fù)湟?guī)則Fig.1 Topological rules for subdivision of quadrilateral meshes

圖1為現(xiàn)有的一些細(xì)分格式的拓?fù)湟?guī)則。本文將新的細(xì)分格式的構(gòu)造轉(zhuǎn)到對幾何規(guī)則的改變上，即構(gòu)造一種全新的插入點(diǎn)的計算方式。通過對比三角形細(xì)分格式中的 Loop格式［4］和 Butterfly格式［10］（見圖2）易發(fā)現(xiàn)，同為三角形網(wǎng)格細(xì)分的中點(diǎn)格式，其主要區(qū)別為生成新點(diǎn)的模板不同。相應(yīng)的細(xì)分掩模（僅列出插值型）為：

（1）Loop格式掩模：

（2）Butterfly格式掩模：

模板選取時首先要滿足對稱性。三角形網(wǎng)格在3個方向上均對稱，因此，在Loop格式模板上修改時也必須滿足3個方向?qū)ΨQ。Butterfly格式即為對Loop格式模板的擴(kuò)張。在Loop模板的基礎(chǔ)上，以新加入的點(diǎn)P為中心，向P→P1P4，P→P4P2，P→P2P3和P→P3P1方向擴(kuò)張一步，得到Butterfly格式的模板，仍保持原模板關(guān)于新加入點(diǎn)的三方向的對稱性。

圖3細(xì)分格式Fig.3subdivision scheme

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

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

圖4 Midedge細(xì)分Fig.4 Midedge subdivision scheme

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

2 新的Midedge格式

本節(jié)，將以圖5（a）所示的新的模板為基準(zhǔn)，確定新的細(xì)分格式的掩模。

由圖5（a）知，細(xì)分掩模要滿足對稱性，則生成新的邊點(diǎn)的掩模應(yīng)具有以下形式：

其中，2α+4β=1。

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

其中，a1+a2+a3=1。

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

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

插入點(diǎn)的位置如圖6所示。

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

回顧之前的目標(biāo)，是為了用3個點(diǎn)生成1個新的中間點(diǎn)，于是，令

綜上所述，有

于是，確定此細(xì)分格式的掩模，新的Midedge格式的幾何規(guī)則為

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

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

3 細(xì)分的連續(xù)性

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

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

（2）矩陣S對應(yīng)于v2,v3的特征映射

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

細(xì)分矩陣的確定：首先要選取合適的初始控制網(wǎng)格M0，在給出的掩模矩陣S下，進(jìn)行細(xì)分，生成新的有著同樣拓?fù)涞目刂凭W(wǎng)格M1，如此往復(fù)，構(gòu)成迭代形式：

其中i為正整數(shù)。

從圖7中可以看出，由于單一Midedge格式拓?fù)湟?guī)則的特殊性，一個標(biāo)準(zhǔn)的n×n網(wǎng)格無法生成標(biāo)準(zhǔn)的m×m網(wǎng)格。于是，用2步Midedge格式，計算細(xì)分矩陣S2。若S2的特征值已知，由矩陣的性質(zhì)易得S的特征值（前者特征值是后者的平方）。

2步Midedge格式，要想選取的模板在細(xì)分矩陣S2加細(xì)下循環(huán)迭代，須選取6×6的網(wǎng)格點(diǎn)。因此，2步Midedge格式的細(xì)分矩陣S2應(yīng)該是36×36的。參照圖8，給出細(xì)分矩陣S2的形式：

其中

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

經(jīng)計算，得到細(xì)分矩陣S2的特征值從大到小依次為：由于細(xì)分矩陣S2對應(yīng)的特征映射無法用具體代數(shù)形式表示，可通過分析其特征值及對應(yīng)于第二、第三特征值的特征映射構(gòu)成的特征環(huán)（見圖9）的性質(zhì)，判斷其單射性和正則性。

圖9 新的Midedge格式正則區(qū)域的特征環(huán)Fig.9 Characteristic rings of Midedge subdivision in regular regions

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

4 邊界規(guī)則和特殊點(diǎn)規(guī)則

4.1 邊界規(guī)則

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

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

圖10 邊界處理Fig.10 Boundary treatment

4.2 特殊點(diǎn)規(guī)則

4.2.1 特殊點(diǎn)掩模

對于圖11所示的初始網(wǎng)格特殊點(diǎn)（即點(diǎn)的價不再是標(biāo)準(zhǔn)的4），細(xì)分時所對應(yīng)的掩模也要有相應(yīng)的變化。

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

4.2.2 特殊點(diǎn)處細(xì)分的連續(xù)性

本節(jié)，以k=3，5時的特殊點(diǎn)為例，驗證新的Midedge格式在特殊點(diǎn)時的連續(xù)性。

此時對應(yīng)于價為3的特殊點(diǎn)，本文提出的細(xì)分格式所對應(yīng)的模板如圖12所示。相應(yīng)的2步細(xì)分

圖11 k價特殊點(diǎn)模板Fig.11 Extraordinary point stencil of the valence k

圖12 特殊點(diǎn)價為3時的細(xì)分模板Fig.12 Extraordinary point stencil of the valence 3

圖13 矩陣的特征環(huán)Fig.13 Characteristic rings of matrix

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

圖14 特殊點(diǎn)價為5時的細(xì)分模板Fig.14 Extraordinary point stencil of the valence 5

圖15 矩陣的特征環(huán)Fig.15 Characteristic rings of matrix

5 數(shù)值實驗

圖16和圖17分別為對不含特殊點(diǎn)的初始控制網(wǎng)格使用新的Midedge格式和原始的Midedge格式細(xì)分4次后的圖像，圖18為初始網(wǎng)格為正方體的網(wǎng)格圖像細(xì)分7次后的圖像。圖19為與之對應(yīng)的使用原Midedge格式的效果圖。圖21為7個正方體構(gòu)成的多面體細(xì)分前后的圖像對比。圖22為與之對應(yīng)的使用原Midedge格式的效果圖。

圖16 正則網(wǎng)格上新的Midedge細(xì)分Fig.16 New Midedge subdivison on regular mesh

圖17 正則網(wǎng)格上的Midedge細(xì)分Fig.17 Midedge subdivison on regular mesh

圖18 正方體網(wǎng)格經(jīng)7次新Midedge細(xì)分后的圖像Fig.18 A cube mesh after new Midedge subdivision for 7 times

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

圖19 正方體網(wǎng)格經(jīng)7次Midedge細(xì)分后的圖像Fig.19 A cube mesh after Midedge subdivision for 7 times

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

圖21 新Midedge細(xì)分后的圖像Fig.21 Mesh with new Midedge subdivision

6 結(jié) 論

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

圖22 Midedge細(xì)分后的圖像Fig.22 Mesh after Midedge subdivision