吳元翠

?

基于Loop細(xì)分的自適應(yīng)細(xì)分曲面算法

吳元翠

(安徽農(nóng)業(yè)大學(xué)理學(xué)院應(yīng)用數(shù)學(xué)研究所，安徽，合肥 230036)

首先研究了傳統(tǒng)的Loop細(xì)分曲面算法，通過(guò)分析發(fā)現(xiàn)隨著細(xì)分次數(shù)的增多細(xì)分算法中三角形網(wǎng)格片數(shù)增長(zhǎng)過(guò)快。針對(duì)這一問(wèn)題提出一種自適應(yīng)細(xì)分曲面算法。算法根據(jù)相鄰兩個(gè)三角形面上的法向量的夾角，判斷細(xì)分網(wǎng)格中較為光滑和非光滑的區(qū)域。實(shí)驗(yàn)結(jié)果表明，算法提高了數(shù)據(jù)處理速度，并且模型簡(jiǎn)單易實(shí)現(xiàn)。

細(xì)分曲面；Loop細(xì)分；自適應(yīng)細(xì)分

0 引言

然而，細(xì)分網(wǎng)格在應(yīng)用中面臨的的難題是細(xì)化光滑度與數(shù)據(jù)量成幾何級(jí)數(shù)劇增的矛盾，針對(duì)這一問(wèn)題，一種可行的辦法是采用自適應(yīng)細(xì)分曲面算法實(shí)現(xiàn)細(xì)分。自適應(yīng)細(xì)分曲面算法是根據(jù)一定的光滑性和連續(xù)性的要求，判斷細(xì)分網(wǎng)格中較為光滑的區(qū)域和非光滑的區(qū)域，從而只對(duì)非光滑區(qū)域進(jìn)行細(xì)分，以達(dá)到降低網(wǎng)格數(shù)提高效率的目的。由于存在不同的細(xì)分曲面算法，故自適應(yīng)細(xì)分算法的適用性較廣。國(guó)外Ashish Amresh等人對(duì)三角網(wǎng)格自適應(yīng)細(xì)分[4]作了探索，Hamid-Reza提出了一種增量自適應(yīng)細(xì)分[5]，該方法可以根據(jù)用戶(hù)的需求只對(duì)選定的區(qū)域進(jìn)行細(xì)分。另外，近幾年來(lái)很多三角形網(wǎng)格的自適應(yīng)細(xì)分方法[5-10]已被提出，但這些算法中有些會(huì)產(chǎn)生一些退化三角形，使得部分面片處于不同層，破壞了整體細(xì)分曲面的連續(xù)性，也有些算法原理復(fù)雜，難以實(shí)現(xiàn)。

本文提出的基于Loop細(xì)分中網(wǎng)格邊光滑度的自適應(yīng)細(xì)分算法，以相鄰兩個(gè)三角形網(wǎng)格面的法向量夾角為判據(jù)，區(qū)分細(xì)分網(wǎng)格中較為光滑和非光滑的區(qū)域，從而達(dá)到自適應(yīng)細(xì)分的目的，能夠有效的降低細(xì)分過(guò)程三角網(wǎng)格片數(shù)的增加量。

1 Loop細(xì)分算法

V-頂點(diǎn)的計(jì)算規(guī)則為:

E-頂點(diǎn)的計(jì)算規(guī)則為：

其細(xì)分模板如圖1所示：

圖1 Loop細(xì)分曲面算法

Fig.1 The Loop subdivision surface algorithm

2 基于邊光滑度的自適應(yīng)細(xì)分算法

目前廣泛采用的自適應(yīng)細(xì)分的判據(jù)是網(wǎng)格頂點(diǎn)與對(duì)應(yīng)的極限位置的距離以及頂點(diǎn)的曲率等。這些算法中有些會(huì)產(chǎn)生一些退化三角形，使得部分面片處于不同層，破壞了整體細(xì)分曲面的連續(xù)性，也有些算法原理復(fù)雜，難以實(shí)現(xiàn)。本文提出一種基于Loop三角形網(wǎng)格邊光滑度的自適應(yīng)細(xì)分算法，以相鄰兩個(gè)三角形面片的外法向量的夾角作為判據(jù)確定各邊的光滑性，從而達(dá)到自適應(yīng)細(xì)分的目的。

2.1 算法原理

圖2 自適應(yīng)細(xì)分算法

(4)在下一級(jí)細(xì)分中，光滑邊的中點(diǎn)取為E-點(diǎn)；如果頂點(diǎn)對(duì)應(yīng)的邊均為光滑邊，則標(biāo)記該頂點(diǎn)為不動(dòng)點(diǎn)，在下一級(jí)細(xì)分中保持其幾何位置不變。當(dāng)一個(gè)面片的所有頂點(diǎn)都為不動(dòng)頂點(diǎn)時(shí)，該面片為不動(dòng)面片，在后面的細(xì)分中，不再對(duì)該面片細(xì)分。

每一次細(xì)分前，都按照上述算法對(duì)控制網(wǎng)格進(jìn)行檢測(cè)，對(duì)于非不動(dòng)頂點(diǎn)和非光滑邊，按照Loop細(xì)分的幾何規(guī)則完成本次細(xì)分中新的邊點(diǎn)和頂點(diǎn)的計(jì)算，并按照其拓?fù)湟?guī)則產(chǎn)生新的網(wǎng)格。

2.2 裂縫處理

圖3 裂縫處理

2.3 實(shí)例分析

為了驗(yàn)證本文算法的有效性，利用 C++和OPENGL 圖形函數(shù)庫(kù)，在 VC++6.0 環(huán)境編程實(shí)現(xiàn)了相應(yīng)算法，對(duì)原始面片數(shù)為 319的模型兩次細(xì)分，如圖4所示。

圖4 細(xì)分網(wǎng)格圖

3 結(jié)論

綜上所述，本文提出的算法在進(jìn)行自適應(yīng)細(xì)分的時(shí)能較好地實(shí)現(xiàn)降低模型中的存儲(chǔ)量和運(yùn)算量；能準(zhǔn)確的分辨模型的較光滑和較粗糙區(qū)域。另外，作者在后續(xù)研究工作中，將對(duì)算法的規(guī)則和設(shè)計(jì)進(jìn)行適當(dāng)修改，使其能更廣泛應(yīng)用于其他細(xì)分曲面模式中。

[1] Loop C.Smooth Subdivision Surfaces Based on Triangles [D]. Utah: University of Utah, 1987.

[2] Catmul E, Clark J. Recursively generated B-spline surfaces Oil topological meshes [J].Computer Aided Design, 1978,l0(6):350-355.

[3] Doo D, Sabin M. Behaviour of recursive division surfaces Deal extraordinary points[J].Computer Aided Design, 1978, 10 (6):156-160.

[4] Amresh A, Farin G, Razdan A. Adaptive Subdivision Yw. Hemes for triangle Meshes [M]. Arizona: Arizona State University, 2000.

[5] 鐘大平,周來(lái)水,周海. 自適應(yīng)混合細(xì)分算法研究 [J]. 機(jī)械科學(xué)與技術(shù) ,2004,23(9):1090-1092.

[6] 王艷艷,張榮國(guó),王蓉,等. 向量線性相關(guān)的三角網(wǎng)格自適應(yīng) Loop 細(xì)分方法 [J]. 工程圖學(xué)學(xué)報(bào) ,2009,1: 91-96.

[7] 趙宏慶,彭國(guó)華,葉正麟,等. 自適應(yīng)細(xì)分方法進(jìn)行曲面造型 [J]. 計(jì)算機(jī)應(yīng)用研究. 2006, 9:72-76.

[8] 李桂清,吳壯志,馬維銀.自適應(yīng)細(xì)分技術(shù)研究進(jìn)展[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào),2006,18(12): 1789-1799.

[9] 吳劍煌,劉偉軍,王天然. 面向三角網(wǎng)格的自適應(yīng)細(xì)分[J]. 計(jì)算機(jī)工程 , 2006 , 32(12):14-16.

[10] 李李,王亞平.裁剪曲面自適應(yīng)三角化剖分 [J].計(jì)算機(jī)應(yīng)用, 2006, 26 : 2-13.

[11] 孫大松,鞠志濤,孫立鐫.約束自適應(yīng)Loop曲面細(xì)分 [J]. 計(jì)算機(jī)應(yīng)用研究 ,2012,29(9):3506-3508.

Adaptive subdivision surface algorithm based on the Loop subdivision

WU Yuan-cui

(Institute of Applied Mathematics, Anhui Agricultural University, Hefei, Aihui 230036, China)

Firstly, the traditional Loop subdivision surface algorithm is studied. The analysis show that the increase of the number of triangular mesh is growing too fast in the traditional Loop subdivision algorithm. Secondly, in order to solve this problem, an adaptive subdivision surface algorithm is given. This algorithm bases on the included angle of the two normal vector of the two adjacent triangles to judge the more smooth and nonsmooth area in subdivision grid, than subdivides the nonsmooth area only. Finally, the experimental results show that this algorithm improves the speed of subdivision processing, and the model is easy to implement.

subdivision surface; Loop subdivision algorithm; adaptive subdivision algorithm

1674-8085(2013)05-0041-04

TP391

A

10.3969/j.issn.1674-8085.2013.05.010

2013-03-13；

2013-05-26

吳元翠(1980-)，女，安徽鳳陽(yáng)人，講師，碩士生，主要從事計(jì)算機(jī)輔助幾何設(shè)計(jì)、計(jì)算機(jī)圖形學(xué)、數(shù)值計(jì)算等研究( E-mail:wuyuancui@ahau.edu.cn).