基于GPU的計算幾何算法研究與應(yīng)用.pdf

1、計算幾何可以應(yīng)用于計算機圖形學(xué)、地理信息系統(tǒng)和三維地質(zhì)建模等生產(chǎn)和生活中的各個方面，本文研究了基于GPU的并行計算幾何相關(guān)算法，以及相關(guān)計算幾何算法在三維地質(zhì)建模方面的應(yīng)用，充分開發(fā)了GPU的通用計算能力，取得了較好的性能加速效果。
　　 本文主要的研究工作內(nèi)容如下：
　　 1、設(shè)計了基于GPU的并行計算幾何軟件包的主要架構(gòu)；它由C/C++語言編寫串行算法、CUDA實現(xiàn)并行算法、圖形庫OpenGL進行科學(xué)計算結(jié)果的渲染和

2、顯示等組件構(gòu)成；擁有凸包求解、Voronoi圖生成、網(wǎng)格插值和網(wǎng)格剖切等功能。
　　 2、研究了計算幾何中的四個基本問題——二維凸包求解、二維Voronoi圖生成、網(wǎng)格插值和網(wǎng)格剖切的GPU并行化問題。在求解凸包時，Quickhull法形成的子問題是獨立的，不需要進一步的合并求解操作，因此使用GPU并行化Quickhull凸包求解算法；提出了基于GPU的Voronoi圖生成算法，彌補了原有GPU并行算法不能生成真正Voronoi

3、網(wǎng)格的不足；在構(gòu)建三維地質(zhì)模型時，研究了地層面構(gòu)建時常用到的普通克里金插值和Shepard插值算法，針對插值數(shù)據(jù)量越來越大的情況，設(shè)計和實現(xiàn)了它們基于GPU的并行算法；在剖切三維地質(zhì)模型時，現(xiàn)有的剖切算法并不適合GPU并行化，因此設(shè)計了基于GPU的折線剖切和折線裁剪剖切算法，實現(xiàn)了各種剖切效果。實驗結(jié)果表明，基于GPU的并行算法相比串行算法取得了很好的加速性能。
　　 3、最后研究了并行計算幾何在三維地質(zhì)建模領(lǐng)域的應(yīng)用問題。在剖

4、切算法的基礎(chǔ)上設(shè)計了基于GPU的斷層模擬算法，模擬了各種類型的斷層；基于VisualC++9.O、CUDA和OpenGL，在Windows平臺實現(xiàn)了基于GPU的三維地質(zhì)建模系統(tǒng)，集成了插值、剖切、斷層構(gòu)造等算法，實現(xiàn)了多種模型繪制效果（如揭蓋顯示、地層透明和符號模式等）和易用的交互方式（軌跡球和漫游等的交互方式等）。
　　 本文研究的基于GPU的并行計算幾何的相關(guān)算法及其在三維地質(zhì)建模領(lǐng)域的應(yīng)用，取得了較好的加速效果，大幅度提高