一种快速三维散乱点云的三角剖分算法

改进了一种三维散乱点云三角剖分算法。三角剖分是点云数据曲面重构的主要算法之一,但针对三维散乱点云的三角剖分存在剖分效率不高,剖分得到的三角曲面形状无法控制,细节特征表现不足的问题。提出了基于空间栅格划分的三角剖分算法,并提出了一个新的评价函数,以控制三角网格曲面的生长。实验证明,改进后的算法极大的提高了剖分效率,而且能保证最终生成的三角网格曲面平滑而保有丰富的细节特征,适用于在虚拟现实、曲面重构等领

　　第26卷　第9期

文章编号:1006-9348(2009)09-0338-04

计　算　机　仿　真

2009年9月　　

一种快速三维散乱点云的三角剖分算法

陈　伟,刘肖琳

(国防科技大学机电工程与自动化学院,湖南长沙410073)

摘要:改进了一种三维散乱点云三角剖分算法。三角剖分是点云数据曲面重构的主要算法之一,但针对三维散乱点云的三角剖分存在剖分效率不高,剖分得到的三角曲面形状无法控制,细节特征表现不足的问题。提出了基于空间栅格划分的三角剖分算法,并提出了一个新的评价函数,以控制三角网格曲面的生长。实验证明,改进后的算法极大的提高了剖分效率,而且能保证最终生成的三角网格曲面平滑而保有丰富的细节特征,适用于在虚拟现实、曲面重构等领域推广使用。关键词:三角剖分;八叉树搜索;生长法中图分类号:TP391　　文献标识码:B

AFastTriangulationAlgorithmforUnorganized3-DPoints

CHENWei,LIUXiaolin

(NationalUniversityofDefenceTechnolABSTRACT:Atriangulationalgorithmforthreediclisimprovedinthispaper.TheDelaunaytriangulationisoneofthemainmon.Buttheefficiencyofthetriangulationforthreedimensionallitisdifficulttocontroltheshapeofthetrigonsandexpressthedetailof.Tosolvetheseproblems,thepaperproposedanewtriangulationalgo2rithmbasedonanddevelopedanewcriterionfunctiontocontrolthegrowthofthetrianglesur2face.Theresultexperimentshowsthattheefficiencyoftheimprovedalgorithmisgreatlyadvanced,andthetrian2glegridsurfaceproducedbytheimprovedalgorithmissmoothandpreservesdetailcharacters.It’ssuitedtopopular2izeinvirtualreality,surfacereconstruction,andsomeotherfield.KEYWORDS:Triangulation;Octreesearching;Growthalgorithms

1　引言

曲面重建的技术在计算机图形建模,医学成像,逆向工程等领域应用十分广泛,对三维散乱点云进行三角剖分以获取高质量三角网格曲面是曲面重建中的重要技术之一。三维点云数据三角剖分一般有以下两种途径:一种是对点云数据在三维空间直接剖分,另一种是把点云数据投影到二维平面,再对平面域内的点云剖分,剖分完的结果再映射回三维空间。对于后者,它只能适用于在某一方向的投影没有重叠的简单曲面,而对于某些定向投影有重叠的复杂曲面,则要对整个曲面分片剖分处理,然后再将剖分结果合并。而且在平面域内剖分达到最优时,在对应的三维空间里未必是最优的。

目前,国内外学者研究三角剖分算法的成果很多。其中,在平面域内的剖分的理论与算法均已比较成熟。Delau2

nay三角剖分的理论要求网格中的每一个三角形或四面体内

不含给定集合中的任意点,因此,Delaunay三角剖分不但唯一,而且最优。A.Bowyer[1]和D.Watson[2]和分别实现了平面域内Delaunay三角剖分的算法。鉴于此,关于映射法的三维三角剖分本文就不再赘述。1988年,Choi[3]提出了直接形成三维空间散乱点的拓扑关系的方法:先形成结点列表

TLIST后创成TBL(TransientBoundaryList),以TLIST为初

始,完成三角化。F.Bernardino和他的同事J.Mittleman[4]针对海量的密集激光扫描数据提出了基于BPA(Ball-Pivoting

Algorithm)的三角剖分算法,具有很高的时效性,但对散乱点

[5]

容易产生很多空洞。M.Gopi和S.Krishnan也提出了一种

针对三维散乱点云的表面重建技术,通过对每一点估计其法矢和正切平面,并将其邻域内的点投影到正切平面上,再对局部邻域内的点进行三角剖分,从而避免了通常映射法不能解决的具有复杂连通曲面的物体表面的剖分问题,但因为要对每一点估计其法矢和正切平面,存在着剖分效率不高的问题。董辰世结合法矢和经典的Delaunay三角剖分原理,提出了一种基于法矢的散乱点三角剖分算法,但是该算法需要预

收稿日期:2008-05-26　修回日期:2008-08-13

先知道散乱点的法矢信息[6]。哈尔滨工业大学的赵杰和他

—338—

改进了一种三维散乱点云三角剖分算法。三角剖分是点云数据曲面重构的主要算法之一,但针对三维散乱点云的三角剖分存在剖分效率不高,剖分得到的三角曲面形状无法控制,细节特征表现不足的问题。提出了基于空间栅格划分的三角剖分算法,并提出了一个新的评价函数,以控制三角网格曲面的生长。实验证明,改进后的算法极大的提高了剖分效率,而且能保证最终生成的三角网格曲面平滑而保有丰富的细节特征,适用于在虚拟现实、曲面重构等领

的同事[7]提出了一种新的空间离散点集的三角剖分算法,该算法能对空间任意曲面点云进行直接的剖分,生成的三角网格曲面均匀,质量较高。但是也存在以下两个方面的问题:一是剖分效率不高,且剖分所耗时间随点云数据增加成几何级增长;二是剖分后生成的三角网格曲面平滑了曲面原有的细节特征。本文着重从这两方面改进了该算法,在提高了原有算法的效率的同时,也使剖分后生成的三角网格曲面最大限度的保持了原有曲面的特征。此外 …… 此处隐藏：5667字，全部文档内容请下载后查看。喜欢就下载吧 ……