基于自适应八叉树分割点云的表面模型重建
|
摘要
传统的三角网生长法进行点云数据表面模型重建时,搜索第三点耗时太长,导致重建效率很低。采用自适应八叉树划分算法将点云数据分割成相互覆盖的子域,在每个子域内进行三角网格重建,避免网格拼接的过程;采用最大角最小化原则进行三角网格优化;并运用三角面片定向的方法进行网格法向量一致化处理。实验结果表明,该方法极大地提高了表面模型重建的效率,形成的网格质量也很好,能够较好地体现模型的细节特征,鲁棒性好。
In surface model reconstruction with regard to point cloud data,traditional triangulation growth method has very low efficiency because it takes too long time in searching the third vertex.The adaptive octree subdivision algorithm is used in this paper.Point cloud data are divided into subdomains covering each other,and the triangular grids are reconstructed in every subdomain,thus the process of the grid stitching is avoided.The produced triangular grids are optimised using the principle of minimising the maximum angle.A triangular facet orientation method is used for uniformisation of the normal vectors of grids.Experimental results show that the efficiency of the surface model reconstruction is greatly improved by using this method,and the quality of the triangular grids produced are very good as well,the detail features of the model are better reflected,and the algorithm is robust.
In surface model reconstruction with regard to point cloud data,traditional triangulation growth method has very low efficiency because it takes too long time in searching the third vertex.The adaptive octree subdivision algorithm is used in this paper.Point cloud data are divided into subdomains covering each other,and the triangular grids are reconstructed in every subdomain,thus the process of the grid stitching is avoided.The produced triangular grids are optimised using the principle of minimising the maximum angle.A triangular facet orientation method is used for uniformisation of the normal vectors of grids.Experimental results show that the efficiency of the surface model reconstruction is greatly improved by using this method,and the quality of the triangular grids produced are very good as well,the detail features of the model are better reflected,and the algorithm is robust.
引文
[1]Miles R E.Probability distribution of a network of triangles(a solution to problem 67 -15)[J].Society for Industrial and Applied Mathematics, 1969,11(3):399-422.
[2]Lingas A.The greedy and Delaunay triangulations are not bad in the average case[J].Information Processing Letters,1986,22(1):25 -31.
[3]余杰,吕品,郑昌文.Delaunay三角网构建方法比较研究[J].中国图象图形学报,2010,15(8):1158-1167.
[4]Green P J,Sibson R.Computing dirichlet tessellations in the plane[J]. The Computer Journal,1978,21(2):168- 173.
[5]Bowyer A.Computing dirichlet tessellations[J].The Computer Journal, 1981,24(2):162 - 166.
[6]Watson D F.Computing the n-dimensional delaunay tessellation with application to Voronoi polytopes[J].The Computer Journal,1981,24 (2):167 -172.
[7]董洪伟.散乱点云的三角网格重构[J].计算机工程,2005,31 (15):30-32.
[8]邓曙光,刘刚.一种TIN生成算法的改进与实现[J].计算机时代, 2006,2(1):1-2.
[9]李泽宇,李德华,胡汉平,等.基于八叉树的三维散乱点的法矢的估计[J].计算机与数字工程,2000,28(4):44-65.
[10]Ohtake Y,Belyaew A.Alexa M,et al.Multi-level partition of unity implicits [J].ACM Transactions on Graphics,2003,22(3);463 -470.
[11]伍军,杨杰,秦红星.基于广度搜索的增量式点云表面重建[J].上海交通大学学报,2008,42(10):1740-1744.
[12]陈伟,刘肖琳.一种快速三维散乱点云的三角剖分算法[J].计算??机仿真,2009,26(9):338-341.
[2]Lingas A.The greedy and Delaunay triangulations are not bad in the average case[J].Information Processing Letters,1986,22(1):25 -31.
[3]余杰,吕品,郑昌文.Delaunay三角网构建方法比较研究[J].中国图象图形学报,2010,15(8):1158-1167.
[4]Green P J,Sibson R.Computing dirichlet tessellations in the plane[J]. The Computer Journal,1978,21(2):168- 173.
[5]Bowyer A.Computing dirichlet tessellations[J].The Computer Journal, 1981,24(2):162 - 166.
[6]Watson D F.Computing the n-dimensional delaunay tessellation with application to Voronoi polytopes[J].The Computer Journal,1981,24 (2):167 -172.
[7]董洪伟.散乱点云的三角网格重构[J].计算机工程,2005,31 (15):30-32.
[8]邓曙光,刘刚.一种TIN生成算法的改进与实现[J].计算机时代, 2006,2(1):1-2.
[9]李泽宇,李德华,胡汉平,等.基于八叉树的三维散乱点的法矢的估计[J].计算机与数字工程,2000,28(4):44-65.
[10]Ohtake Y,Belyaew A.Alexa M,et al.Multi-level partition of unity implicits [J].ACM Transactions on Graphics,2003,22(3);463 -470.
[11]伍军,杨杰,秦红星.基于广度搜索的增量式点云表面重建[J].上海交通大学学报,2008,42(10):1740-1744.
[12]陈伟,刘肖琳.一种快速三维散乱点云的三角剖分算法[J].计算??机仿真,2009,26(9):338-341.