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

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

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

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

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

5、(調(diào)頻網(wǎng)屏)代表了彩色印刷的另外一種方案，能產(chǎn)生比傳統(tǒng)網(wǎng)屏更細(xì)微的顆粒，這種方法允許疊加多于3層而不會(huì)產(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)點(diǎn)大小，以適應(yīng)不同的

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

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

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