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

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

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

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