Power圖在圖形學(xué)和工程學(xué)等領(lǐng)域有著廣泛的應(yīng)用,其中以具有質(zhì)心約束和容量約束的質(zhì)心容量限制Power圖（Centroidal Capacity Constraint Power Diagram,簡稱CCCPD）尤為突出。現(xiàn)有的算法中,Power圖的幾何構(gòu)造過程是CCCPD計算中較為復(fù)雜的過程之一,其消耗的時間占據(jù)總計算時間50%以上;Power圖容量和質(zhì)心約束優(yōu)化計算過程也消耗大量的計算時間。為了解決這個性能瓶頸,本文分別針對2D-Power圖和3D-Power圖,提出了基于GPU的構(gòu)造和優(yōu)化計算算法。本文主要工作如下:1)綜述了Voronoi圖及Power圖的研究進展�？偨Y(jié)了現(xiàn)有Voronoi圖和Power圖在2D和3D領(lǐng)域各種計算算法,分析了它們的優(yōu)缺點。2)提出一種基于GPU-CPU混合計算的2D-CCCPD計算算法。首先將基于GPU的Jump Flooding Algorithm（JFA）算法用于渲染并構(gòu)造Power圖,然后提出連通域算法（Connected Domain Method,簡稱CDM）用于提取2DPower圖渲染圖的幾何結(jié)構(gòu)數(shù)據(jù),最后通過與基于CPU的L-BFG... 

【文章來源】：合肥工業(yè)大學(xué)安徽省 211工程院校 教育部直屬院校

【文章頁數(shù)】：62 頁

【學(xué)位級別】：碩士

【部分圖文】：

整體研究框架

Voronoi距離及Power距離

第二章Power圖及相關(guān)概念介紹8()2*22jiiijjijjixxwwpxxxx+=(2-4)根據(jù)式(2-4)可知，對于站點ix與站點jx，如果固定站點ix，jx的位置以及jx的權(quán)重jw不變，僅增大站點ix的權(quán)重iw，那么交點*ijp會向jx方向移動，即站點ix的Power區(qū)域增大，jx的Power區(qū)域縮小，反之亦然。Voronoi區(qū)域的邊界是相鄰站點的垂直平分線而構(gòu)成的，所以每個Voronoi站點都在其所屬Voronoi劃分區(qū)域內(nèi)部。而Power圖對距離的重新定義，導(dǎo)致在某些情況下，Power圖的站點不在所屬Power區(qū)域內(nèi)部，或Power區(qū)域為空。如圖2.3所示，有共線的三個站點ix，jx和kx。(,)ikexx為站點ix與站點kx的等Power距離線，(),kjexx為站點kx與站點jx的等Power距離線，圖2.3中陰影區(qū)域Ⅰ為站點kx和站點ix所形成的，陰影區(qū)域Ⅱ為站點kx和站點jx所形成的。顯然陰影區(qū)域Ⅰ與陰影區(qū)域Ⅱ交集為空，站點kx也不在其所屬區(qū)域內(nèi)。圖2.3Power區(qū)域為空的情況Fig2.3Thepowercellisempty.2.1.22D-Power圖與3D-Power圖本文主要研究2D-Power圖和3D-Power圖的計算算法，本節(jié)對2D-Power圖和3D-Power圖中概念的區(qū)別做出解釋。圖2.42DPower圖符號定義


本文編號：3291912