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

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

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

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

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