吳元翠

?

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

吳元翠

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

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

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

0 引言

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

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

1 Loop細(xì)分算法

V-頂點的計算規(guī)則為:

E-頂點的計算規(guī)則為：

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

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

Fig.1 The Loop subdivision surface algorithm

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

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

2.1 算法原理

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

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

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

2.2 裂縫處理

圖3 裂縫處理

2.3 實例分析

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

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

3 結(jié)論

綜上所述，本文提出的算法在進(jìn)行自適應(yīng)細(xì)分的時能較好地實現(xiàn)降低模型中的存儲量和運(yùn)算量；能準(zhǔn)確的分辨模型的較光滑和較粗糙區(qū)域。另外，作者在后續(xù)研究工作中，將對算法的規(guī)則和設(shè)計進(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] 鐘大平,周來水,周海. 自適應(yīng)混合細(xì)分算法研究 [J]. 機(jī)械科學(xué)與技術(shù) ,2004,23(9):1090-1092.

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

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

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

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

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

[11] 孫大松,鞠志濤,孫立鐫.約束自適應(yīng)Loop曲面細(xì)分 [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-)，女，安徽鳳陽人，講師，碩士生，主要從事計算機(jī)輔助幾何設(shè)計、計算機(jī)圖形學(xué)、數(shù)值計算等研究( E-mail:wuyuancui@ahau.edu.cn).