【doc】空间封闭点云的八象限三角剖分算法

1、空间封闭点云的八象限三角剖分算法第l4卷第3期2009年6月哈尔滨理工大学journalofharbinuniversityofscienceandtechnologyvo1.14no.3jun.2009空间封闭点云的八象限三角剖分算法关明山,周波,韩娜,王洋,陈新河(黑龙江科技学院计算机与信息工程学院,黑龙江哈尔滨150027)摘要:提出了一种针对空间封闭点云的三角剖分算法.该算法首先根据空间封闭点云的分布特征,将其划分到三维坐标的八个象限中,使每部分点云的包角均小于180.;然后适当旋转各部分点云,使其对应投影平面面积最大化,再运用平面三角剖分方法对其进行三角剖分,从而得到各部分点云的剖分

2、结果;最后将已处理的各部分用三角面片对其边界进行缝合,进而形成空间封闭点云的立体三角化.实验结果表明,该方法剖分速度快,形成的三角网格质量高,能够较好地再现原三维物体的表面特征.关键词:封闭点云;散乱点集;平面三角剖分;立体三角剖分中图分类号:tp391文献标志码:a文章编号:10072683(2009)03002005eightquadrantstriangulationalgorithmaboutspaceclosedpoint-cloudguanmingshan,zhoubo,hanna,wang,chenxinhe(departmentofcomputerandinformatione

3、ngineering,heilongjianginstituteofscienceandtechnology,harbin150027,china)abstract:thispaperputsforwardatriangulationalgorithmusedforspaceclosedpoint-cloud.atfirstthisal-gorithmaccordingdistributingcharactersofspace3dunorganizedpointsets,dividsspaceclosedpointcloudintoeightquadrantsandpointcloudembr

4、acedcentralangleofeachpartislessthan180degrees.thenthedividedpointcloudsarerevolvedproperlyinordertomaximizeprojectionarea,andtriangulatedbyplanetriangulationalgorithmgettingtheresultoftriangulation.intheendthetriangulatedparts'boundaryaresewnupusingtrianglermingthefinaltridimensionaltriangulari

5、zationofspaceclosedpointcloud.theresultprovesthatthisalgorithmprocessestriangulationrapidly,formshighqualitytrianglegridandreproducesinitial3dobject'sexternalcharacteristic.keywords:closedpointcloud;unorganizedpointset;planetriangulation;tridimensionaltriangularizationl引言空间散乱点的三角剖分是计算机几何领域中的重要课题

6、之一,它广泛应用于计算机辅助设计(cad),医学成像,逆向工程及计算机视觉等领域,也是当前计算机在图形图像方向研究的一个热点和收稿日期:20080912基金项目:黑龙江省教育厅科学研究项目(11511354)作者简介:关明山(1974),男,讲师;周波(1963),男,教授.难点.对于空间散乱点的三角剖分,国内外相关专家,学者经过多年研究,积累了大量成功的经验,其中绝大多数是基于delaunay三角化的剖分算法.文14为国外关于三角剖分比较有代表性的算法,国内对空间曲面重构的研究也取得了很大进展5.总的看来,空问散乱点的三角剖分方法可划分为直接剖分法和平面投影法两大类.直接剖分法基本思想是第3

7、期关明山,等:空间封闭点云的八象限三角剖分算法21直接由三维点构造三角面片,最终连接成空间曲面;平面投影法基本思想是将空间三维点云投影到某平面上,然后对投影点集做平面三角剖分.上述关于空间散乱点的三角剖分方法很多,优化准则也有数种,但无论是直接剖分法还是平面投影法,都只针对空间曲面片的点云做三角剖分,对于空问自封闭散乱点云的三角剖分尚在探索之中,而医学成像,逆向工程等实际问题恰恰需要对三维物体进行整个表面的重建.为此,本文提出一种基于分治思想的八象限空间立体三角剖分算法,有效解决了空间闭合曲面的三角剖分问题.2基本概念本文所涉及到的一些基本概念如下:1)平面曲线包角:平面曲线拟合圆上对应该曲线

8、的那段圆弧所对应的圆心角即为平面曲线包角.当平面曲线是闭合的时候,该平面曲线的包角为360.2)点云的包角:对于摄像机或者ccd获取的一片点云数据,通过点云拟合球体的球心及点云几何中心的平面与点云交线所对应的包角中最大的角即为点云的包角.一般摄像机,ccd一次获取的一片点云包角都小于180.3)点云朝向:对于摄像机或者ccd获取的一片点云数据,其外边缘线(只有一条且封闭)上的所有点拟合成一个平面的法向方向就为点云的朝向.4)圆准则:严格凸的四边形中的3个点确定一个圆,如果第4个顶点落在圆内,则将第四个顶点与其相对的顶点相连,否则将另两个相对顶点相连,从而得到两个优化的三角形.如图1所示.日3算

9、法实现图1圆准则示意图3.1基本数据结构1)点云数组(ca).ca用来临时存储点云数据,每个元素能够存储一个空间点的三维信息.2)投影表(pn).pn代表pnxrangeyrange二维数组,每个元素为一链表指针,该链表用来临时存储一个网格内投影进来的所有点信息.xrange,yrange表示平面投影沿,y方向的网格个数.3)待连接点链表(tlp).tlp用来临时存储平面网格中待连接点的三维信息及一个bool类型的域,初始化为false,表示此网格中无待连接点.4)三角形链表(tl).tl用来存储三角剖分的结果,每个节点包含一个剖分三角形的三个顶点信息以及该三角形的法矢量信息.5)起止位置表(

10、be).be代表bexrange2二维数组,用来存储投影网格中每一行待连接点的起止位置,初始化为一1.t6)边界循环链表(bl).bl用来存储每片点云边界点(按逆时针顺序加人)的信息.7)内边界表(tib)和外边界表(tob).用来临时存储缝合曲面的内,外边界点的链表.3.2算法的实现过程1)读人点云并检测点云空间大小:读入点云数据并保存到ca中.循环查看ca,计算点云包围盒的length,width,height值.据此再结合程序的要求,确定在,y,z方向上所要划分网格的数目,就可以算出每个投影平面上网格的长和宽,即将投影面上的网格划分好,等待空间点的投影.2)分割点云:首先依据下式,即.=

11、p.x/n=0.y=p.y/ni=0.z=p.z/ni=o求出整个点云集的重心.p(,y,).其中p是点云中的点,凡为点云中点的个数.如图2所示,过重心p(,y,z),沿,y,三个坐标轴方向做三个相互垂直的平面y,l,一z和z,这三个互相垂直的平面将整个点云分割在8个区域中,将这8个区域中的点云数据分别存人ca1一ca8八个数组中,这八个数组元素的数据结构和ca完全一样.图2点云分割图22哈尔滨理工大学第l4卷3)旋转投影及平面剖分:点云经过分割,形成八个朝向各异,包角都小于180.的部分点云,可以用平面网格法对每部分进行三角化.为优化程序,也防止同一部分点云不同位置的点在投影时发生重叠,在投

12、影前对每块部分点云都进行适当的旋转,使其点云朝向正对某个平面,以保证各块部分点云三角化的曲面片法向矢量的一致性,以及投影面积最大化.对于旋转后的部分点云中的每一点,利用其旋转坐标的值和平面上网格的长,宽,即可计算出该点投影的网格位置,进而将点加入该网格.将这八个象限的部分点云投影分别记录在pn1至pn8中.由于这时投影进同一个单元网格中的点可能不止一个,为了能够连接出最优的三角面片,取网格最中间的点做为平面网格剖分的待连接点.将选取的八块部分点云的待连接点分别存进数组tlp1一tlp8中.此时,空间曲面的三角剖分问题就转化为平面三角剖分问题.最后对记录待连接点的数组进行遍历,分别找到每个待连接

13、点的下邻接点进行三角形的连接,并用圆的准则进行优化,计算出三角形的单位法向量,再将三角形的三个顶点和单位法向量记录进tl中.关于平面三角剖分的具体实现过程见文.4)寻找部分点云边界:如图3所示,点云已经投影进了平面网格中.首先遍历tlp,记录下各行中第一个和最后一个待连接点的位置,将这些位置信息存储到数组be中.找到各行待连接点的起止位置后,就开始沿逆时针方向加入部分点云的边界点,八块部分点云的边界分别加入到bl1bl8八个边界点数组中.下面以第一象限点云边界搜索过程为例表述其具体步骤.87一6一4气,321o123456,了8母1011l213140图3部分点云边界的寻找首先扫描be1数组,

14、找到第一行有非负值的行号,记做top,找到最后一行有非负值的行号记做bottom.加入零行待连接点:取出位置从be1top0到be!top1中的待连接点,并按从左到右顺序依次加入边界数组bl1中;加入右侧边界点:加入右侧边界时是依次从第top行加-n第bottom行减一分别加入的,如图3右侧的箭头所示,具体加入过程伪代码如下:fbr(i=top+1;i<bottom;i+)t1=be1i1一be1i一11;t2=be1i1一be1i+11;if(t11andt21)/情况1如图中的行七,则将be1i1位置的待连接点加人bl1中;elseif(t1>1)/情况2如图中

15、的行一,行二则将当前行从be1i一11+1到be1i1的待连接点从左到右顺序加入bl1中;elseif(t2>1)/情况3如图中的行三则将当前行从be1i+11+1到be1i1的待连接点逆序加入bl1中;else出错处理;lj加入最后行待连接点:从be1bottom0到be1bottom1位置读取最后行的待连接点,然后逆序加入到边界数组bl1中;加入左边界点:加左边界与加右边界相似,只不过是从bottom一1行到top+1行依次加入的,而且加入是从各行的起待连接点一侧加入,如图3左侧的箭头所示,具体加人伪代码如下:for(i=bottom一1;i>top;i一一)t

16、1:be1i0一be1i+10;t2=be1i0一be1i一10;if(tl一1andt2一1)/情况1如图中的行七,则将be1i0位置的待连接点加入bl1中;elseif(t1<一1)/情况2如图中的行四,则将当前行从be1i儿0到be1i+10一1的待连接点逆序加人bl1中;elseif(t2<一1)/情况3如图中的行二,则将当前行从be1i0到be1i一10一1的待连接点顺序加入bl1中;else出错处理;找边界中的转折点:由图4可见,每块点云的边界需要和三块部分点云的边界进行缝合,而一块点云的边界只有一条,所以这条边界应分为三部分,分别对应与它相邻的三块点云

17、的边界.如图4中的点1,点2和点3就为点云边界中的转折点,这3个点将一个闭合的边界分为三段边界,分别与其第3期关明山,等:空间封闭点云的八象限三角剖分算法23相邻的三块点云边界进行缝合三角化.只要求取边界中离两个坐标平面距离之和最小的点就为边界中的转折点.例如只要在边界中寻找到离平面y和平面yz距离之和最小的点,即min(z+xz)就可以找到转折点1.同样,找到点2和点3的位置并分别将点1,点2,点3在边界中的位置记录到bl的头节点中.图4寻找边界中的转折点5)边界缝合:在边界缝合时,首先找到要缝合的内,外边界,如图5所示.对于点云1的边界即为要缝合的内边界,因为在加入部分点云边界点时就是按照

18、逆时针加人,所以部分点云1的边界已经有序.对于缝合的外边界就需要从部分点云2,3和4的边界中截取相应部分并连接起来而形成.由于在前边已经将各块部分点云边界的转折点找到并存储起来,故只要找到相应的转折点分别截取再连接就可以了.本例依次在点云2,4,3的边界中取出相应边界段上的点,然后将这些部分边界段进行连接.由图5可以看到,这样加进来的外边界是按顺时针方向排列的,为了和内边界进行正确的缝合连接,就必须将外边界的点序进行反序,使内,外边界点序一致.最后将找到的内,外边界分别存储到两个以点对象为元素的动态数组tib和tob中,准备进行边界缝合.,'_.1''蠹缝合边界过程如图

19、6所示,伪代码如下:读取tib起始点作为nowptl;nextptr图6缝合内,外边界示意图读取tob中与nowptl距离最近点作为nowptr;读取内边界数组起始点的邻下边界点nextptl;读取外边界数组起始点的邻下边界点nextptr;while(runl<numlandrunr<numr)/runl,runr分别为左右读数组元素的计数器,numl,numr为左右边界数组中元素个数$/计算图6中的1,2;if(/1>l2)/此处实际是依据圆准则进行的优化处理将以nextptl,nowptl,nowptr为顶点的三角形及其法向量存入三角形链表tl中

20、;nowptlc=nextptl;从内边界数组读取下一点做为nextptl;runl+:else将以nextptr,nowptl,nowptr为顶点的三角形及其法向量存入三角形链表tl中;nowptrnextptr;从外边界数组读取下一点做为nextptr;runr+;/endwhileif(runli>numl)将以nextptr,nowptl,nowptr为顶点的三角形及其法向量存人三角形链表,i'l中;if(runrnumr)将以nextptl,nowptl,nowptr为顶点的三角形及其法向量存人三角形链表tl中;4实验结果及分析本程序利用一个完整的鼠标空间点云进

21、行三角化检验,点云原来包含128826个点,包含该点云的n>左边界点哈尔滨理工大学第l4卷最小盒子的长,宽,高分别为126.513,66.4591和40.7198,该点云重心p(,y,z)的坐标为(一6.23912,一273.537,一223.420),y方向上的投影网格个数都为8o个,网格的长宽分别为1.5814125和0.83073875,分割后的八块部分点云经过投影选点后总共剩下17583个点,第一到第八象限的部分点云其边界上的点数分别为125,131,128,126,117,119,119和120,最后剖分的三角面片数总共为20378.图7为整个鼠标空间点云三角化的最终结

22、果.(a)点视图(b)三角连接视图(c)实体渲染视图图7整个鼠标空间点云三角化的结果以上实验结果同直接剖分法比较,大大减少了参与三角剖分的点的数量(参与直接剖分的点数为128826个;实际参与三角剖分点数为17583个),提高了程序执行的速度;同普通的平面投影法比较,平面网格投影法对投影点进行了有效筛选,使剖分的三角形质量更高.5结语1)本算法采用分治思想,将空间散乱点集划分成八部分,再分别对各部分点集进行旋转投影及平面网格三角剖分,最后找到各部分点云的边界进行三角缝合,从而使整个空间点云得到三角化,有效解决了空间闭合点云的三角剖分问题.2)平面网格投影的三角剖分方法可实现对空间曲面上点云的有效筛选,降低了无效的三角剖分计算,优化了生成的三角面片,从而大大提高了程序执行的效率及三角剖分质量.实验结果表明,八象限空间立体三角剖分算法是一个有效率的,成功的三角剖分算法.参考文献:1amentan,bernm,kamvysselism.anewvoronoibasedsurfacereconstructionalgorithmc/proceedingsoftheacmsiggraphconferenceoncomputergraphics,orlando,fl,newyork,usa,1998:415421.2atrenem,spagnuoo