曲面重建中Voronoi圖的并行算法研究.pdf

1、從曲面的三維采樣點集恢復出曲面的幾何模型稱之為曲面重建。曲面重建是許多研究領(lǐng)域如逆向工程，醫(yī)學圖像可視化中的重要問題，因此，曲面重建問題被廣泛地研究，產(chǎn)生了許多曲面重建算法。基于Voronoi圖的曲面重建算法是其中一類使用較廣泛的重建算法，該算法主要是通過構(gòu)造采樣點集的Voronoi圖并對其進行三角剖分來重建曲面。但隨著激光測距掃描等測量設(shè)備的快速發(fā)展，人們得到的采樣點集呈海量的趨勢，致使Voronoi圖的構(gòu)造速度較慢，進而也降低了曲面

2、重建的速度。因此，為了最終提高此類曲面重建算法的速度，本文從并行角度出發(fā)，主要對其中Voronoi圖的并行構(gòu)造算法進行了研究。
　　首先，系統(tǒng)地分析了平面求交法、增量法、平面掃描法和分治法這四種串行構(gòu)造Voronoi圖的算法的并行性。從可否并行化、并行度、粒度和存儲類型四個方面對這四種算法的并行性進行了綜合對比。并且對其中分治法的并行性進行了挖掘，對分治法中的合并算法進行了擴展。
　　其次，基于以上對串行算法的并行性分析，結(jié)

3、合目前雙核系統(tǒng)的廣泛使用性。以平面掃描法為基礎(chǔ)，提出了一種適用于雙核系統(tǒng)的Voronoi圖的并行算法。該算法采用并行雙向掃描的思想，結(jié)合本文提出的一種組合結(jié)構(gòu)，使其既能提高Voronoi圖的構(gòu)造速度，又能保持雙核負載平衡。
　　最后，結(jié)合機群系統(tǒng)的廣泛使用性，以分治法為基礎(chǔ)，提出了一種適用于機群系統(tǒng)的Voronoi圖的并行算法。針對該并行算法中合并過程的復雜性，提出了最短等待合并策略并設(shè)計了一種節(jié)點狀態(tài)雙向鏈表來維持算法的正確執(zhí)行