吳元翠

?

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

吳元翠

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

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

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

0 引言

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

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

1 Loop細分算法

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

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

其細分模板如圖1所示：

圖1 Loop細分曲面算法

Fig.1 The Loop subdivision surface algorithm

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

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

2.1 算法原理

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

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

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

2.2 裂縫處理

圖3 裂縫處理

2.3 實例分析

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

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

3 結(jié)論

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

[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)混合細分算法研究 [J]. 機械科學(xué)與技術(shù) ,2004,23(9):1090-1092.

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

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

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

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

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

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