科技

您的位置:主页 > 科技 >

基于GPU的并行Voronoi图栅格生成算法“乐鱼体育app”

发布日期:2021-03-26 00:36浏览次数:
本文摘要:Voronoi图是一种室内空间分拆优化算法。其是对室内空间中的n个线形点来讲的,它将平面图拆分成n个地区,每一个地区还包含一个点,此地区是到该点距离近期的点的非空子集。因为Voronoi图具有最周边性,邻近性等诸多特性和完善的思想体系,其被广泛的运用于在生态学、天文学、结晶学、航空航天、智能机器人等行业。 Voronoi图的溶解关键有矢量素材方法和栅格方法。矢量素材法中,典型性的方法有增加量法、共治法和间接性法。

乐鱼体育

Voronoi图是一种室内空间分拆优化算法。其是对室内空间中的n个线形点来讲的,它将平面图拆分成n个地区,每一个地区还包含一个点,此地区是到该点距离近期的点的非空子集。因为Voronoi图具有最周边性,邻近性等诸多特性和完善的思想体系,其被广泛的运用于在生态学、天文学、结晶学、航空航天、智能机器人等行业。

  Voronoi图的溶解关键有矢量素材方法和栅格方法。矢量素材法中,典型性的方法有增加量法、共治法和间接性法。

共治法是一种迭代更新方法,优化算法构思比较简单,可是难以在运用于全过程中搭建动态性重做。间接性规律是依据其对偶图Delaunay三角网来构造Voronoi图,因而其特性的高低由所应用的Delaunay三角网的构造优化算法所规定。增加量法根据大大的向已溶解的Voronoi图上降低点来动态性创设Voronoi图。

相对性于前二种方法,增加量法构造比较简单而且更非常容易搭建统一化,因此 被广泛运用。矢量素材方法的优点是溶解Voronoi图高精度,可是不会有储存简易,生长发育元不可以是点和线,及其没法向三维及低维空间扩展等难题。因而文中关键科学研究了Voronoi图的栅格溶解方法,最先比较了罕见的栅格方法溶解Voronoi图的优点和缺点,随后结合CUDA的经常会出现,明确指出一种根据GPU的Voronoi图分段栅格溶解优化算法。

  1栅格法简述  栅格方法溶解Voronoi图主要是将二值图像转换变成栅格图象,随后确定每个空缺栅格属于。关键方法有两大类,一类以空缺栅格为管理中心,计算出来每一个空缺栅格到生长发育总体目标的距离,以确定其属于,罕见的方法有解析几何距离转换法,逐一空缺栅格确定法等;另一类以生长发育总体目标为管理中心,大大的拓展生长发育总体目标的距离半经,铺满在其中的空缺栅格,直至将全部图象铺满顺利完成,关键有圆拓展法,数学课组织学距离转换法等。解析几何距离转换法对距离图象进行下滑扫瞄(从上向下,从左往右)和上涨扫瞄(从下向上,从右到左)2次扫瞄,计算出来出有每一个空缺栅格最周边的生长发育总体目标,为此生长发育总体目标做为其属于。

此方法中栅格距离的界定立即危害了空缺栅格的属于和Voronoi图的溶解精密度,一般来说用以的栅格距离界定有商街距离、八角形距离、旗盘距离等。距离变换的栅格溶解方法精密度较低、用时宽,所务必花销的時间和栅格的总数正相关,当栅格为nn大钟头,其算法复杂度为O(nn)。

乐鱼体育app

圆测定法以生长发育总体目标为圆心点,以一定的步幅为原始半经,全部生长发育总体目标另外对其包括的圆内的空缺栅格进行覆盖范围。根据不断发展生长发育总体目标的半经,将不容易有更为多的空缺栅格被每个圆所覆盖范围,直至最终覆盖范围初始个图象。数学课组织学距离转换法与圆测定法类似,其观念来源于数学课组织学中收拢作业者,收拢作业者起着了不断发展图象的实际效果,根据极大地对生长发育总体目标进行收拢作业者,最终拓展到全部的空缺栅格。

这二种方法有一个协同的缺陷,在每一次拓展后,都务必鉴别全部栅格图象否顺利完成拓展,而这务必迭代更新栅格图象,十分用时。  2GPU下的栅格溶解方法  2.1CUDA程序编写实体模型与GPU  CUDA是一个分段程序编写实体模型和一个电脑编程自然环境,其应用了C语言做为计算机语言,获得了很多的性能卓越计算出来命令研发能力,使开发人员必须在GPU的强悍数学计算上建立起一种更加高效率的聚集数据信息计算出来解决方法。  CUDA将CPU做为服务器尾端,GPU做为机器设备尾端,一个服务器尾端能够有好几个机器设备尾端。

其应用CPU和GPU协调工作的方法,CPU关键承担管理流程中的串行通信计算出来的一部分,GPU关键承担管理流程中的并行处理的一部分。GPU上经营的编码称之为核心涵数,其必须被GPU上内嵌的好几个线程并行执行。一个初始的每日任务程序处理由CPU尾端串行通信应急处置编码和GPU尾端分段核心涵数协同包括。

当CPU中执行到GPU编码时,其最先将涉及到数据信息载入GPU中,随后启用GPU的核心涵数,GPU中好几个线程并行执行此核心涵数,当顺利完成计算出来后,GPU尾端再作把计算出来的結果返回给CPU,程序流程执行。根据将程序流程中用时的且有助于并行计算的计算出来移往到GPU中用以GPU并行计算,以提高全部程序流程的经营速率。

CUDA是以线程网格图(Grid),线程块(Block),线程(Thread)为三层的的组织结构,每一个网格图由好几个线程块包括,而一个线程块又由好几个线程包括,如图所示1下图。在GPU中,线程是分段经营的超过模块,不难看出,当不会有很多的线程时,程序流程的分段水平将不容易十分低。


本文关键词:基于,GPU,的,并行,Voronoi,图,栅格,生成,算法,“,乐鱼体育

本文来源:乐鱼体育-www.f2fcenter.com