基于椭球面投影的散乱点云建立三角格网方法

郑德华,庞逸群,曹操

(河海大学土木工程学院,江苏南京 210098)

郑德华,庞逸群,曹操

(河海大学土木工程学院,江苏南京 210098)

空间点云数据建立三角格网是三维激光扫描数据处理中重要的处理内容之一。已有的点云三角格网建立方法的网形结构良好,但存在数据量大、计算效率低的特点。提出借助椭球面进行高斯投影建立点云的空间三角格网建立方法,有效地实现四周型点云数据格网建立过程。结合某矿井点云数据实例,对基于圆柱面和椭球面投影的两种方法建立的三角格网进行对比,结果表明,利用椭球面投影法建立三角格网能更有效地建立顶部和底部点云数据的拓扑关系。

散乱点云;三角格网;椭球面投影;高斯投影

三维激光扫描目前已广泛应用于计算机可视化、人工智能以及逆向工程等方面,三角格网贯穿于三维激光点云数据处理的整个过程。S-M Hur等人研究了基于Delaunay三角化过程中实现点云数据的缩减[1],1997年Chen Liang-Chia和 Grier CI L IN提出了将构建的三角格网进行最小二乘自由曲面模型的重建[3]。三角格网的建立在点云数据处理中具有十分重要的作用,研究合适的三角格网建立方法是建立复杂物体模型的一项重要内容。目前许多文献对此都进行了大量的研究,发现直接在三维空间中利用点与点之间的关系构建三角格网,当点云数据量较大时,构网非常耗时,计算效率低下,且在点密度不均匀或存在噪声的情况下,难以判断点对之间的真正邻接关系。作者提出了利用圆柱面坐标系在可保证点云中各点之间的相对关系不变的前提下,将三维点坐标转换成可以用来生成平面三角格网的二维坐标[7],实现四周形点云数据的格网构建;张帆等提出了利用球面投影对单站地面激光扫描点云的构网方法[8],但对于多站三维激光扫描数据其适用性仍有待探讨。本文将三维点云数据分别采用圆柱面坐标系统和椭球面坐标系统投影至二维平面上,然后利用平面上的坐标计算Delaunay三角形方法建立三维物体表面格网模型,有效地建立了具有顶部和底部点云数据的拓扑关系。

1 椭球面投影法

1.1 椭球面坐标系统

椭球面坐标系[9]是在三维直角坐标系统中定义一个长、短半轴分别为a、b的椭圆绕其短轴旋转而形成的椭球基准面,椭球面的中心为右手系的原点O(见图1)。若椭球面坐标系中包含一点P,则在椭球面上一定存在一点P′,P′为P点相对于椭球中心O在椭球面上的投影。图1中B表示P′点在椭球面上的法线与xoy平面的夹角;L表示PP′连线在xoy平面上的投影与ox轴的夹角。

图1 椭球面坐标系

在计算过程中,ti前一次迭代值,第一次迭代令

ti=t0。将点云中的点坐标(X,Y,Z)和自定义的椭球的长、短半轴a、b分别代入式(1)、(2)中,计算点在椭球面坐标系统中的坐标(B,L)。

1.2 平面坐标计算

1.2.1 高斯投影坐标计算公式

在高斯投影中,将大地坐标(B,L)转化成高斯平面直角坐标系下的坐标采用以下公式计算:

1.2.2 平面坐标计算

利用自定义的椭球长、短半轴a、b和椭球坐标系坐标(B,L)直接代入X、l、N、t、η的计算公式,将计算结果代入式(4)即可计算出三维空间点利用椭球面投影后的平面坐标(x,y)。

由高斯投影原理可知,按某一度数划分投影带后,不同带的点通过高斯投影坐标正算公式获得的平面坐标位于不同的平面直角坐标系中,因此无法保持点与点之间原有的相对位置关系,通过式(5)可将计算获得的平面点归化到同一坐标系中。

式中:x、y为归化前的坐标,x1、y1为归化后的坐标,a为椭球长半轴,n为分带度数。

2 基于椭球面投影的空间三角格网建立方法

2.1 三角格网建立的基本思路

利用面投影将点云中的所有点投影到二维平面后,空间三角格网的建立则转化到二维平面上进行。建立三角格网的原则为由邻近的散乱点组成三角格网时,应尽可能地确保每个三角形三边长度接近相等,避免出现过大钝角和过小钝角的三角形。建立三角格网时,首先建立一个核心三角形,由此三角形的三个边向外围建立扩展三角形,建立方法是根据已构三角形的边与外围一点构成三角形的外接圆半径最小建立扩展三角形,然后由原三角形的三个顶点和新搜索的点构成四边形,若构成凸四边形则根据连接四边形对角线短边来重构两个三角形以达到优化三角形形状的目的,若构成凹四边形则不需进行三角形形状连接优化。

2.2 三角格网实现方法

根据上述思想,采用数据库设计方法实现三维空间建立点的三角格网算法。首先在Access数据库中建立一个数据表格,即原始点云三维坐标point表,在程序中定义了5个向量类模板 vector的变量:ThreeVertex,Twow Vertex,Twoww Vertex, LaterList,TriangleList。XCoor、Ycoor、Zcoor和Intens四个元素分别表示三维激光扫描点的三维坐标和点的反射强度,m_index、X、Y、Z4个元素分别存储投影前的三维点云坐标的顺序点号和对应点的三维坐标,m_pindex、x、y元素分别存储投影后的二维点云数据的顺序点号和对应点的二维坐标, num元素表示在进行扩展三角形时,从 Twow Vertex中选取的满足条件的点的点号,m_Tindex、m_ point1、m_point2、m_point3四个元素分别用于存储三角形的序号和相应的三角形三个顶点的序号,m_ Lindex元素用于存储边的序号,m_point1、m_ point2分别存储边的起点和终点,m_LatDist存储边的长度,m_Old Tri、m_New Tri分别用于存储原三角形和扩展三角形的序号,m_Old Trip t、m_New TriPt分别用于存储原三角形第三个顶点和扩展三角形第三个顶点的序号,m_CroDist用于存储Old TriPt和New TriPt两点的距离。

根据建立的数据结构,利用椭球面投影法实现三维激光扫描点云的空间三角格网建立的步骤:

1)坐标投影转换。首先,将point表中的点坐标依次存入向量 ThreeVertex中,m_index元素值从1开始依次累加1,表示点的序号;然后,将每个点的三维坐标经过上述的椭球面投影转换变为二维平面坐标,存储到向量 Twow Vertex中,其元素m_ pindex的值与向量 ThreeVertex中相对应的点的元素m_index的值一致。

2)构建核心三角形。选取 Twow Vertex向量中的第一个点作为整个建网的开始,遍历 Twow-Vertex中的所有点找出其最近的点i形成第1个三角形的一条边。在寻找核心三角形第三点时,根据第三点到该边的距离最短原则确定,即由余弦定理求取该边对应角最大的点k作为核心三角形的第3点。首先将核心三角形的3个顶点按选取的先后顺序存入到向量 Twoww Vertex,点的序号分别为0、i、k;然后将核心三角形的编号设为0,3个顶点号按选取的顺序即:0、i、k,存储在向量 TriangleList中;最后根据向量 TriangleList中的记录,将三角形的三条边作为序号为0、1、2的3个记录存入向量LaterList,并将各边的边长、三角形编号及第3点的序号写入LatDist、Old Tri和Old TriPt中。

3)利用核心三角形扩展三角形。依次将向量Twoww Vertex中的点与其向下的每一个点组合成边,如果该边在向量LaterList中存在,则该边为进行扩展三角形的基础,将向量 Twow Vertex中满足扩展要求的点存入向量Twoww Vertex中。三角形边扩展过程如图2所示:0-14-15为核心三角形,按顺序以0-14为边扩展得到3号点,加入到向量Twoww Vertex中;0-15扩展得到5号点,加入到向量 Twoww Vertex中;0-3扩展得到16号点;0 -5得到1号点;0-16得到1号点,加入到向量Twoww Vertex。接着以14号点开始向下遍历,即以14-15为边进行扩展得到6号点,依次类推直到所有的点都成为三角格网中的顶点。

图2 平面三角格网建立示意图

由一条边扩展三角形时,首先要排除与该边所对的原三角形的顶点位于同侧的点。可根据该边两个端点坐标构造的直线方程判别式(6)来进行判断。

将向量LaterList中Old TriPt元素中的三角形顶点所对应的坐标代入式(6),得到函数值F0。由于扩展三角形的顶点必须与扩展边对应原三角形的顶点分别在扩展边的两侧,因此,参与扩展三角形的顶点的坐标代入式(6)后得到的函数值F(x,y)的符号应与F0的符号相反。对于满足以上判断条件的点,再根据余弦定理获取扩展边对应的角最大的点,作为扩展三角形的第3个顶点。将扩展三角形的编号及三个顶点写入向量 TriangleList,并在向量LaterList中增加两条新增边的记录;然后,将扩展三角形的顶点加入向量LaterList的原记录的New TriPt元素中,并计算Old TriPt和New TriPt所存放的两点的距离,将计算结果存放在CroDist元素中。

4)三角格网优化。如果原三角形3个顶点与新扩展的顶点构成凸四边形,则要判断CroDist值是否小于LatDist值。当CroDist值小于LatDist值时,原三角形与扩展三角形的图形结构要进行优化。在进行三角形图形优化时,只需根据向量LaterList中Old Tri和New Tri值查找到向量TriangleList中相应的两条记录,并将重构成的三角形作为两个记录分别替换向量TriangleList中相应的记录。

5)格网映射。经过上述2)、3)、4)过程,实现平面上三角格网建立后,需将平面三角格网映射为三维空间三角格网。由于点间相对位置不变,所以向量TriangleList中保存的每个平面三角形的信息与三维空间三角格网的信息一致,即:三维空间三角形的3个顶点与向量 TriangleList中存储的三角形的3个顶点相对应。

3 两种投影法建立矿井基坑格网实例

某矿井基坑深约为 10 m,水平截面约为4.7 m×4.7 m的方形截面,基坑内表面不光滑,并且有一定的起伏。对该基坑进行三维激光数据采集,共获得了46 365个基坑内表面的点,平均点间隔约为60 mm。为了清晰的反映利用椭球面投影法建立包含顶部或底部数据的空间格网效果,在Access数据库中分别截取表示基坑底部的三维点(共计2 341个点)和矿井中部一段点云(共计4 000个点)(见图3(a)、(b)、(c))。对基坑底部的点云分别利用圆柱面投影法和椭球面投影法进行坐标转换后,生成三维空间的矿井基坑底部三角格网,并通过OpenGL三维图形函数库绘制和显示(见图3中的(d)和(e));对矿井中部点云先整体绕X轴旋转90°,然后分别利用圆柱面投影法和椭球面投影法建立三维空间的矿井基坑中部三角格网(见图3中的(f)和(g))。

从图3可知,借助面投影法,利用平面建立Delaunay三角形的方法建立点云三角格网,生成的三角形形状均匀,整体图形结构合理。对于四周型物体表面的三维激光扫描点云利用椭球面投影法建立三角格网与利用圆柱面投影法建立的三角格网具有相同的网形效果。对于包含顶部和底部数据的点云利用圆柱面投影法实现三维空间三角格网建立时,顶部和底部的点云所生成格网的拓扑关系比较混乱;利用椭球面投影法实现三维空间三角网建立时,生成三角形的形状较为均匀,整体的网形结构较为合理,能够较好的保持三维空间点原始的拓扑关系。但利用椭球面投影法实现空间三角格网建立的效率比圆柱面投影法的效率低,且随着点云数量越多,这种差异越明显。这是由于在利用椭球面投影法需运用迭代方法计算椭球面坐标B,且坐标值x1和y1的计算较复杂。

因此当点云的数据量较大时,用圆柱面投影法实现空间三角格网的建立在效率上优于椭球面投影;当点云数据为具有顶部和底部数据的情况下,采用椭球面投影法建立空间三角格网在网形上具有明显的优势。

4 结束语

采用圆柱面投影法和椭球面投影法将点云数据投影至二维平面上,将复杂的三维问题转化为二维问题在平面上进行构网,然后格网映射成整体的三维模型,能够取得较好的构网效果,且具有较高的效率。通过对比实验表明,对于具有顶部和底部数据的点云数据,利用圆柱面投影法建立三维空间三角格网,顶部和底部的点云所生成格网的拓扑关系比较混乱;利用椭球面投影法实现三维空间三角网建立时,生成三角形的形状较为均匀,整体的网形结构较为合理,能够较好的保持三维空间点原始的拓扑关系。但当点云数据量较大时,用圆柱面投影法实现空间三角格网的建立在效率上优于椭球面投影。因此针对不同的点云数据选择必须不同的投影方法方能有效保证点云构网的精度和效率。

[1]S-M HUR,H-C KIM,S-H LEE.STL File generation w ith data reduction by the delaunay triangulation method in reverse engineering[J].The International Journal of Advanced Manufacturing Technology.2002,19:669-678

[2]H-C KIM,S-M HUR,S-H LEE.Segmentation of the measured point data in reverse engineering[J].International Journal of Advanced Manufacturing Technology, 2002,20:571-580.

[3]CHEN L IANG-CH IA,GRIER C IL IN.A vision-aided reverse engineering app roach to reconstructing free-form surface[J].Robotics&Computer-Integrated Manufacturing.1997,13:323-336

[4]CHO IBK,SH IN HY,YOON YI,et al..Triangulation of scattered data in 3D space[J].Compute Aided Des. 1988,0(5):239-248.

[5]FANG TP,PIEGL L.Delaunay triangulation in three dimensions[J].IEEE Comput Graph App l.1995,15(5): 62-69.

[6]XIANG-YANG L I.Sliver-free tree dimensional delaunay mesh generation[D].PhD Dissertation of the University of Illinois at U rbana Champaign.January,2001.

[7]郑德华,张云涛.基于物体表面散乱三维激光扫描点的三角形格网建立[J].测绘工程,2004,13(4):62-65.

[8]张帆,黄先锋,李德仁.基于球面投影的单站地面激光扫描点云构网方法[J].测绘学报,2009,38(1):48-54.

[9]孔祥元,郭际明.大地测量学基础[M].武汉:武汉大学出版社,2001.

[10]黄淼,张海朝.散乱点云的三角划分算法研究[J].微计算机应用,2007,28(10):1 039-1 042.

Triangular grid establishment based on disordered point cloud of ellipsoidal surface projection

ZHENGDe-hua,PANG Yi-qun,CAO Cao
(College of Civil Engineering,Hohai University,Nanjing 210098,China)

The spatial point cloud data to establish a triangular grid in 3D laser scan data p rocessing is one impo rtant p rocess.Previousmethods of establishing triangular grid are shape and structurally sound,but have p roblem to calculate the characteristics of low efficiency w ith large amount of points.In this paper, carried out w ith Gaussian ellipsoid p rojection for the establishment of point cloud to establish triangular grid method,effective imp lementation of the surrounding grid-based point cloud data building p rocess. Combination of point cloud data instance of amine,based on cylindrical surface and the ellipsoid p rojection to establish a triangular grid of two methodswere compared;results showed that the use of ellipsoid to establish a triangular grid p rojection method is more effective in building the top and bottom of the points cloud data topology.

disordered point cloud;triangular mesh;ellipsoidal surface p rojection;Gauss p rojection

P226

1006-7949(2010)04-0019-05

2009-11-24

江苏省交通科学研究计划项目(09Y08)

郑德华(1972-),男,副教授,博士.

[责任编辑:张德福]