曲面重建中voronoi图并行算法的研究

《曲面重建中voronoi图并行算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、国内图书分类号：TP391.75国际图书分类号：621.3工学硕士学位论文曲面重建中Voronoi图的并行算法研究硕士研究生：冯亮导师：张世辉副教授申请学位级别：工学硕士学科、专业：计算机软件与理论所在单位：信息科学与工程学院授予学位单位：燕山大学万方数据ClassifiedIndex:TP391.75U.D.C.:621.3DissertationfortheMasterDegreeinEngineeringRESEARCHONPARALLELALGORITHMOFVORONOIDIAGRAMINSURFACERECONSTRU

2、CTIONCandidate:FengLiangSupervisor:AssociateProf.ZhangShihuiAcademicDegreeAppliedfor:MasterofEngineeringSpeciality:ComputerSoftwareandTheoryUniversity:YanshanUniversity万方数据燕山大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《曲面重建中Voronoi图的并行算法研究》，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。据

3、本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签字：日期：年月日燕山大学硕士学位论文使用授权书《曲面重建中Voronoi图的并行算法研究》系本人在燕山大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。

4、本人授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。保密□，在年解密后适用本授权书。本学位论文属于不保密□。(请在以上相应方框内打“√”)作者签名：日期：年月日导师签名：日期：年月日万方数据摘要从曲面的三维采样点集恢复出曲面的几何模型称之为曲面重建。曲面重建是许多研究领域如逆向工程，医学图像可视化中的重要问题，因此，曲面重建问题被广泛地研究，产生了许多曲面重建算法。基于Voronoi图的曲面重建算法是其中一类使用较广泛的重建算法，该算法主要是通过构造采样点集的Voronoi图并对其进行三角剖分

5、来重建曲面。但随着激光测距扫描等测量设备的快速发展，人们得到的采样点集呈海量的趋势，致使Voronoi图的构造速度较慢，进而也降低了曲面重建的速度。因此，为了最终提高此类曲面重建算法的速度，本文从并行角度出发，主要对其中Voronoi图的并行构造算法进行了研究。首先，系统地分析了平面求交法、增量法、平面扫描法和分治法这四种串行构造Voronoi图的算法的并行性。从可否并行化、并行度、粒度和存储类型四个方面对这四种算法的并行性进行了综合对比。并且对其中分治法的并行性进行了挖掘，对分治法中的合并算法进行了扩展。其次，基于以上对串行算法

6、的并行性分析，结合目前双核系统的广泛使用性。以平面扫描法为基础，提出了一种适用于双核系统的Voronoi图的并行算法。该算法采用并行双向扫描的思想，结合本文提出的一种组合结构，使其既能提高Voronoi图的构造速度，又能保持双核负载平衡。最后，结合机群系统的广泛使用性，以分治法为基础，提出了一种适用于机群系统的Voronoi图的并行算法。针对该并行算法中合并过程的复杂性，提出了最短等待合并策略并设计了一种节点状态双向链表来维持算法的正确执行并实现了动态合并。关键词曲面重建；Voronoi图；分治法；并行算法万方数据Abstract

7、Howtocomputeapiecewiselinearapproximationtoasurfacefromasetofsamplingpointsabstractedfromthesurface,whichiscalledsurfacereconstructionterminologically,isatopiccoverssomanyfieldssuchasreverseengineering,medicineimageprocessing.Consequently,manyresearchonsurfacereconstr

8、uctionhavebeingmadeandmanyalgorithmsonitarealsoproposed,amongwhichthereconstructionalgorithmbasedonVoronoidiagramiswidelyuse