基于GPU的Power图快速生成算法研究

发布时间：2021-07-20 02:12

　　Power图在图形学和工程学等领域有着广泛的应用,其中以具有质心约束和容量约束的质心容量限制Power图（Centroidal Capacity Constraint Power Diagram,简称CCCPD）尤为突出。现有的算法中,Power图的几何构造过程是CCCPD计算中较为复杂的过程之一,其消耗的时间占据总计算时间50%以上;Power图容量和质心约束优化计算过程也消耗大量的计算时间。为了解决这个性能瓶颈,本文分别针对2D-Power图和3D-Power图,提出了基于GPU的构造和优化计算算法。本文主要工作如下:1)综述了Voronoi图及Power图的研究进展。总结了现有Voronoi图和Power图在2D和3D领域各种计算算法,分析了它们的优缺点。2)提出一种基于GPU-CPU混合计算的2D-CCCPD计算算法。首先将基于GPU的Jump Flooding Algorithm（JFA）算法用于渲染并构造Power图,然后提出连通域算法（Connected Domain Method,简称CDM）用于提取2DPower图渲染图的几何结构数据,最后通过与基于CPU的L-BFG... 

【文章来源】：合肥工业大学安徽省 211工程院校 教育部直属院校

【文章页数】：62 页

【学位级别】：硕士

【部分图文】：

整体研究框架

Voronoi距离及Power距离

第二章Power图及相关概念介绍8()2*22jiiijjijjixxwwpxxxx+=(2-4)根据式(2-4)可知，对于站点ix与站点jx，如果固定站点ix，jx的位置以及jx的权重jw不变，仅增大站点ix的权重iw，那么交点*ijp会向jx方向移动，即站点ix的Power区域增大，jx的Power区域缩小，反之亦然。Voronoi区域的边界是相邻站点的垂直平分线而构成的，所以每个Voronoi站点都在其所属Voronoi划分区域内部。而Power图对距离的重新定义，导致在某些情况下，Power图的站点不在所属Power区域内部，或Power区域为空。如图2.3所示，有共线的三个站点ix，jx和kx。(,)ikexx为站点ix与站点kx的等Power距离线，(),kjexx为站点kx与站点jx的等Power距离线，图2.3中阴影区域Ⅰ为站点kx和站点ix所形成的，阴影区域Ⅱ为站点kx和站点jx所形成的。显然阴影区域Ⅰ与阴影区域Ⅱ交集为空，站点kx也不在其所属区域内。图2.3Power区域为空的情况Fig2.3Thepowercellisempty.2.1.22D-Power图与3D-Power图本文主要研究2D-Power图和3D-Power图的计算算法，本节对2D-Power图和3D-Power图中概念的区别做出解释。图2.42DPower图符号定义


本文编号：3291912