Triangular mesh generation algorithm of point clouds
-
摘要: 对海量数据散乱密集难以自动得到邻近点间正确拓扑连接关系的问题,给出了一种用于海量数据的基于增量网格扩展的三角剖分方法.该方法以k阶最近邻域算法快速搜寻边界点的最近邻域,以增量算法的边界环为基础向外生成三角形,实现点云数据点之间合理的三角剖分网格建立.对最佳点的选择提出了3种需遵循的新准则,并根据最佳点的位置不同,详细给出了3种网格拓扑操作来构建新三角网格,可以准确的进行三角剖分.车身曲面测量点云的应用实例表明,该算法可以高效,稳定地直接构建出车身曲面三角网格.Abstract: The establishment of topological mesh problem in point clouds preprocessing was researched. To solve the problem obtaining the correct topological relations of the scattered point clouds, a sort of triangulation based on incremental growth was researched for point clouds. Searched the nearest neighbors of boundary points by using the algorithm of k-nearest neighbors quickly, it constructs triangles based on the boundary ring of incremental algorithm, and realizes the construction of topological mesh. Three new criteria were presented for the selection of the optimal points, and three operations of mesh topology based on the different position of the optimal points was given out to construct new triangular mesh,which the triangulation could be proceeded precisely. The overlapping , pore as well as long and narrow triangles were eliminated. The application for the point clouds of auto body indicates that triangulation mesh of body surface can be constructed effectively and steadily.
-
Key words:
- reverse engineering /
- point clouds /
- triangulation
-
[1] 李旭,高峰,杨宪武,等.车身曲面逆向设计投影法参数化方法的应用[J].汽车设计,2007,5:23-24 Li Xu,Gao Feng,Yang Xianwu,et al.Application of messy points clouds parameterization based on reverse designing of an automobile body curve surface[J].Automobile Technology,2007,5:23-24(in Chinese) [2] Algorri M E, Schmitt F. Surface reconstruction from unstructured 3D data[J].Computer Graphics Forum, 1996,15(1):47-60 [3] Boissonnat J D. Geometric structures for three-dimensional shape reconstruction[J].ACM Transaction on Graphics, 1984,3(4):266-286 [4] Hoppe H, DeRose T, Duchamp T, et al. Surface reconstruction from unorganized point clouds [J].Computer Graphics,1992, 26(2):71-78 [5] Huang J, Menq C H. Combinatorial manifold mesh reconstruction and optimization from unorganized points with arbitrary topology[J].Computer Aided Design, 2002, 34(2):149-165 [6] 王青,王融清,鲍虎军,等.散乱数据点的增量快速曲面重建算法[J].软件学报,2000,11(9):1221-1227 Wang Qing,,Wang Rongqing,,Bao Hujun,et al. A fast progressive surface reconstruction algorithm for unorganized points[J].Journal of Software, 2000,11(9):1221-1227(in Chinese)
点击查看大图
计量
- 文章访问数: 2639
- HTML全文浏览量: 320
- PDF下载量: 1977
- 被引次数: 0