Voronoi圖在隨機(jī)聚合網(wǎng)屏和路徑規(guī)劃中的應(yīng)用研究.pdf

1、Voronoi圖是計算幾何的一種僅次于凸包的重要幾何結(jié)構(gòu)，也是計算幾何的重要研究內(nèi)容之一。由于Voronoi圖具有最近性、鄰接性等眾多性質(zhì)和比較系統(tǒng)的理論體系，如今已經(jīng)在圖形學(xué)、機(jī)械工程、地理信息系統(tǒng)、虛擬現(xiàn)實、機(jī)器人、圖像處理、CAD等領(lǐng)域得到廣泛應(yīng)用，也是解決距離計算、碰撞檢測、路徑規(guī)劃等計算幾何其它問題的有效工具。本文利用Voronoi圖理論，對路徑規(guī)劃，隨機(jī)聚合網(wǎng)屏等問題做了深入研究。 本文路徑規(guī)劃問題的主要研究背景是虛

2、擬博物館漫游。一般的，虛擬漫游方式分為兩種：一種是指定路徑的漫游，另一種是交互方式的漫游。傳統(tǒng)的鼠標(biāo)、鍵盤指引式的交互方式，漫游方式比較單一，用戶只能通過不斷的用鼠標(biāo)、鍵盤調(diào)整方位從而達(dá)到漫游的目的。指定路徑的漫游一般是先記錄一些路徑，在用戶漫游時再選擇這些路徑進(jìn)行漫游。這種方式需要程序員預(yù)先設(shè)定，用戶參與度低。由于我們研究開發(fā)的虛擬博物館是以平面多邊形的的Voronoi圖作為幾何數(shù)據(jù)結(jié)構(gòu)的，所以本文重點的是在平面多邊形的的Vorono

3、i圖已知的情況下，如何快速、有效提供幾種路徑進(jìn)行漫游。本文主要研究了offset路徑，skeleton路徑以及最短路徑三種路徑規(guī)劃方式，該三種路徑漫游方式可以大大提高用戶對于路徑漫游的參與度，系統(tǒng)根據(jù)用戶指定的漫游目的地可以快速的計算相應(yīng)的漫游路徑，滿足不同用戶的不同漫游需要。 其中的最短漫游路徑規(guī)劃問題涉及到了平面最短路問題。歐幾里德最短路徑問題是計算幾何中最重要也是最為人所知的問題之一。在本文中我們關(guān)注的是一類簡單的最短路問

4、題，即：簡單多邊形內(nèi)任意兩點s,f間的最短路徑SP(s,t)。常見的算法大都基于經(jīng)典的Dijkstra算法，Dijkstra算法能得出最短路徑的最優(yōu)解，但效率較低，算法的最壞時間復(fù)雜度為O(n2)。 另外，在印刷印染行業(yè)如何用單個或少數(shù)幾個顏色來印制連續(xù)的豐富色彩是一個基本和難點的問題。目前，工業(yè)上常用調(diào)幅網(wǎng)屏技術(shù)來實現(xiàn)。但是這種技術(shù)在印刷中會產(chǎn)生明顯的干擾圖案，不同角度和頻率的網(wǎng)屏疊加時也會產(chǎn)生龜紋，印刷質(zhì)量難以保證。隨機(jī)網(wǎng)屏

5、(調(diào)頻網(wǎng)屏)代表了彩色印刷的另外一種方案，能產(chǎn)生比傳統(tǒng)網(wǎng)屏更細(xì)微的顆粒，這種方法允許疊加多于3層而不會產(chǎn)生龜紋，可表現(xiàn)更加豐富的顏色及灰度過渡層次以及更加細(xì)膩的圖象細(xì)節(jié)。在本文的研究中，我們結(jié)合Voronoi圖理論和圖形處理器(Graphic Process Unit)技術(shù)提出了一種新的隨機(jī)聚合網(wǎng)屏生成算法。該算法生成的網(wǎng)屏，可以表現(xiàn)更加豐富細(xì)膩的圖像信息，且速度上比傳統(tǒng)算法有了很大的提高。通過調(diào)節(jié)參數(shù)，還可以改變網(wǎng)點大小，以適應(yīng)不同的

6、印刷設(shè)備與印刷需求。 歸納本文的創(chuàng)新和貢獻(xiàn)在于： 1．提出了一種基于Voronoi圖計算簡單多邊形P內(nèi)任意兩點s,t間的最短路徑的算法。該算法首先找到s,t間的Voronoi骨架路徑S(s,t)，以及骨架路徑S(s,t)上的關(guān)聯(lián)內(nèi)尖點與關(guān)聯(lián)邊；然后沿著骨架路徑S(s,t)進(jìn)行可見性計算，逐步求得s,t間的最短路徑SP(s,t)。該算法的時間復(fù)雜度為O(n)。 2．給出了三種基于多邊形Voronoi圖的路徑規(guī)劃方法

7、：即offset路徑、skeleton路徑、最短路徑等。其中的offset路徑利用了多邊形的offset曲線，使用戶在選擇漫游整個場景的同時可以選擇自己需要的觀察角度。skeleton路徑利用了多邊形Voronoi圖的Voronoi骨架作為路徑的主干，使用戶可以任意選擇游覽目的地，最短路徑采用了本文中提出的多邊形內(nèi)任意兩點間的最短路徑的算法，使用戶經(jīng)過最短的距離即可到達(dá)目的地。此三種路徑規(guī)劃方法大大提高了虛擬場景中交互式漫游的靈活性，豐

8、富了漫游方式，滿足用戶的不同漫游需要。 3．提出了一個基于GPU的隨機(jī)聚合網(wǎng)屏生成算法。算法首先構(gòu)造了一個大的抖動矩陣，隨機(jī)放置中心網(wǎng)點；然后根據(jù)離散點集的Voronoi圖的最近性、鄰接性利用GPU計算每個中心網(wǎng)點的最大覆蓋區(qū)域；最后利用GPU對每個網(wǎng)點的覆蓋區(qū)域進(jìn)行灰度填充，得到一個大的閾值矩陣，也就是我們的隨機(jī)聚合網(wǎng)屏。算法中可以通過參數(shù)，改變網(wǎng)點的大小，使其可以適應(yīng)不同的印刷設(shè)備。驗證明，采用這種方法生成的隨機(jī)網(wǎng)屏對高分辨