点云数据的三角剖分及计算机三维重建
|
摘要
为了解决直接剖分法因点云数据拓扑结构复杂出现的自交现象,提出了一种基于分治策略的三角剖分方法.首先,对原始点云数据进行平面投影并执行区域分割;其次,在每一个区域内进行直接剖分,剖分过程遵循异侧剖分准则、法向量夹角最大剖分准则、阈值距离剖分准则、最小内角最大剖分准则.最后,按照空间Delaunay剖分准则完成区域之间的连接.实验结果表明,该文提出的剖分方法对于规则曲面点云和非规则曲面点云都具有理想的剖分效果,并且执行速度快.
In order to solve the self-intersection of point cloud data caused by complex topological structure, a triangulation method based on divide-and-conquer strategy has been proposed. Firstly, the original point cloud data are projected on a plane and partitioned into regions. Secondly, each region is partitioned directly. The partitioning process follows the criteria of lateral partitioning, maximum normal vector angle partitioning, threshold distance partitioning and maximum minimum internal angle partitioning. Finally, the connection between regions is completed according to the spatial Delaunay partition criterion. The experimental results show that the proposed method has ideal segmentation effect for both regular and irregular surface point clouds, and the execution speed is fast.
In order to solve the self-intersection of point cloud data caused by complex topological structure, a triangulation method based on divide-and-conquer strategy has been proposed. Firstly, the original point cloud data are projected on a plane and partitioned into regions. Secondly, each region is partitioned directly. The partitioning process follows the criteria of lateral partitioning, maximum normal vector angle partitioning, threshold distance partitioning and maximum minimum internal angle partitioning. Finally, the connection between regions is completed according to the spatial Delaunay partition criterion. The experimental results show that the proposed method has ideal segmentation effect for both regular and irregular surface point clouds, and the execution speed is fast.
引文
[1]LHUILLIER M.Overview of Shelling for 2-Manifold Surface Reconstruction Based on 3DDelaunay Triangulation[J].Journal of Mathematical Imaging and Vision,2017,59(2):318-340.
[2]倪皓晨,伍钟洁,郏建,等.一种基于Delaunay三角网的栅格线划矢量化方法[J].武汉大学学报(信息科学版),2016,41(2):184-189.
[3]袁小翠,吴禄慎,陈华伟.Delaunay三角剖分算法改进与对比分析[J].计算机应用与软件,2016,33(9):163-166.
[4]WANG X J,XING F,LIU F.Stereo Matching of Objects with Same Features Based on Delaunay Triangulation and Affine Constraint[J].Acta Optica Sinica,2016,36(11):1115004
[5]王向军,邢峰,刘峰.Delaunay三角剖分和仿射约束的特征相同多物体同名点立体匹配[J].光学学报,2016,36(11):197-204.
[6]张蓓蓓,李国清,冯梅,等.基于Delaunay三角剖分的多尺度POI提取技术研究与实现[J].测绘与空间地理信息,2018,41(6):119-121,125.
[7]ALAEDDINI A,MOTASEMI A,FARUQUI S H A.A Spatiotemporal Outlier Detection Method Based on Partial Least Squares Discriminant Analysis and Area Delaunay Triangulation for Image-Based Process Monitoring[J].IISE Transactions,2018,50(2):74-87.
[8]夏俊,李映华.球面凸类图形Delaunay三角剖分再分算法及其收敛性分析[J].计算机应用,2017,37(12):3558-3562.
[9]HAKL■ H,U■UZ H,■AY T.A New Approach for Automating Land Partitioning Using Binary Search and Delaunay Triangulation[J].Computers and Electronics in Agriculture,2016,125(10):129-136.
[10]寿涛,刘朝晖.基于Delaunay三角剖分处理二维欧式空间MTSP的近似算法[J].华东理工大学学报(自然科学版),2017,43(6):895-898.
[11]BOISSONNAT J D,DYER R,GHOSH A,et al.An Obstruction to Delaunay Triangulations in Riemannian Manifolds[J].Discrete&Computational Geometry,2018,59(1):226-237.
[12]CAROLI M,TEILLAUD M.Delaunay Triangulations of Closed Euclidean d-Orbifolds[J].Discrete&Computational Geometry,2016,55(4):827-853.
[2]倪皓晨,伍钟洁,郏建,等.一种基于Delaunay三角网的栅格线划矢量化方法[J].武汉大学学报(信息科学版),2016,41(2):184-189.
[3]袁小翠,吴禄慎,陈华伟.Delaunay三角剖分算法改进与对比分析[J].计算机应用与软件,2016,33(9):163-166.
[4]WANG X J,XING F,LIU F.Stereo Matching of Objects with Same Features Based on Delaunay Triangulation and Affine Constraint[J].Acta Optica Sinica,2016,36(11):1115004
[5]王向军,邢峰,刘峰.Delaunay三角剖分和仿射约束的特征相同多物体同名点立体匹配[J].光学学报,2016,36(11):197-204.
[6]张蓓蓓,李国清,冯梅,等.基于Delaunay三角剖分的多尺度POI提取技术研究与实现[J].测绘与空间地理信息,2018,41(6):119-121,125.
[7]ALAEDDINI A,MOTASEMI A,FARUQUI S H A.A Spatiotemporal Outlier Detection Method Based on Partial Least Squares Discriminant Analysis and Area Delaunay Triangulation for Image-Based Process Monitoring[J].IISE Transactions,2018,50(2):74-87.
[8]夏俊,李映华.球面凸类图形Delaunay三角剖分再分算法及其收敛性分析[J].计算机应用,2017,37(12):3558-3562.
[9]HAKL■ H,U■UZ H,■AY T.A New Approach for Automating Land Partitioning Using Binary Search and Delaunay Triangulation[J].Computers and Electronics in Agriculture,2016,125(10):129-136.
[10]寿涛,刘朝晖.基于Delaunay三角剖分处理二维欧式空间MTSP的近似算法[J].华东理工大学学报(自然科学版),2017,43(6):895-898.
[11]BOISSONNAT J D,DYER R,GHOSH A,et al.An Obstruction to Delaunay Triangulations in Riemannian Manifolds[J].Discrete&Computational Geometry,2018,59(1):226-237.
[12]CAROLI M,TEILLAUD M.Delaunay Triangulations of Closed Euclidean d-Orbifolds[J].Discrete&Computational Geometry,2016,55(4):827-853.