高效空間分割算法及保細節(jié)模型編輯算法.pdf

1、空間分割算法在計算機圖形學(xué)中占據(jù)重要地位。本文分別針對層次劃分結(jié)構(gòu)中的八叉樹和非層次劃分結(jié)構(gòu)中的Voronoi圖在GPU上進行了高效的實現(xiàn)。并且將GPU端的八叉樹建立方法應(yīng)用于高分辨率三角形網(wǎng)格求交。針對模型編輯問題，本文提出了一種新的基于近似剛度(ARAP)算法的模型編輯算法，提高了ARAP算法的細節(jié)保持能力。
　　 在高分辨率三角形網(wǎng)格模型間的幾何布爾運算中，求解兩網(wǎng)格模型間的相交區(qū)域是很多求解算法中核心的一步。本文使用了自

2、適應(yīng)高度的八叉樹作為空間分割結(jié)構(gòu)，降低了算法的時間復(fù)雜度。同時將主要算法在GPU端進行實現(xiàn)，利用GPU的并行計算能力對八叉樹建立及三角形間的求交過程進行并行化，提高了算法的效率。針對以往GPU端層次空間劃分結(jié)構(gòu)需要在建立過程中分割三角形，造成大量退化三角形，并降低了數(shù)值精度的情況，本文中的算法盡量避免了在空間分割過程中對三角形進行的分割，從而提高了最終三角形求交區(qū)域計算的精度。同時，在三角形求交階段使用更精確的求解方式。通過與GTS軟件

3、的整合，最終實現(xiàn)了高效的幾何布爾運算。
　　 提出了一種GPU端的魯棒的二維Voronoi圖構(gòu)建算法。本算法有著較好的平均性能，并在種子節(jié)點分布較稠密和均勻的情況下取得最優(yōu)性能。同時在GPU上實現(xiàn)了魯棒Voronoi圖的構(gòu)建算法中的BFA算法以及非魯棒算法中的JFA算法。經(jīng)驗證，此算法能夠在種子數(shù)一定的情況下獲得比BFA好的平均性能，并在種子較多的情況下獲得接近JFA的性能。
　　 作為幾何建模的重要手段，曲面變形有著廣

4、泛的應(yīng)用。傳統(tǒng)的近似剛性(ARAP)曲面編輯算法存在局部塌陷的問題，并在變形過程中可能產(chǎn)生退化三角形，影響了曲面的質(zhì)量。本文提出了一種新的基于ARAP曲面編輯算法框架與三角形局部能量的三角形網(wǎng)格編輯算法，通過對每個三角形定義其允許的變換集合，在細節(jié)豐富的區(qū)域得到了更好的保形效果。通過限制三角形縮放因子的比例，減少了ARAP算法在變形過程中產(chǎn)生退化三角形的情況。本算法提高了ARAP變形算法的魯棒性，增強了變形過程中對網(wǎng)格局部細節(jié)的保持能力