一种三维散乱点局部降维Delaunay网格自动生成算法

一种三维散乱点局部降维Delaunay网格自动生成算法摘要本文在对以往三维三角网重建算法研究的基础上，提出了一种基于局部降维原则的改进算法。该方法通过输入一系列不提供拓扑结构等附加信息的无组织散乱点而得到一个流型三角网。算法首先将数据点空间分块，然后在局部块中搜索k邻域，构建最小二乘切平面，并将坐标由三维转化成二维将三角剖分建立在二维上。通过将采样点投影到局部的切平面上，再对投影点进行三角化，最后将这些投影后点的连接关系直接映射回三维空间。本文创新性地利用局部降维方法，利用OPENGL编程实验证明，整个系统运行良好，可以为真三维三角面片自动构建提供新思路。【关键词】散乱点局部降维三角网重构OPENGL表面重建是在计算机图形学和几何学中一个非常重要的研究问题，在计算机视觉、逆向工程、虚拟现实等领域都有很重要的研究意义。鉴于点云数据格式简单，存储方便以及其可以突出复杂物体的细节部分，将其作为重建的模型具有很大的研究意义。二维散乱点Delaunay网格剖分已经得到很好的解决，在利用计算机视觉对客观世界重建的过程中，遇到更多的是三维散乱点。对三维散乱点三角面片自动生成，最常用的方法是投影到二维，然后利用二维算法构建，这种方法对2.5维的问题可以很好解决，但对真三维数据往往效果不好。本文改进了算法上的不足以尽可能提高重建的精确度，研究了一种通过三维散乱点集生成流形三角网的算法。本文算法是一种基于投影的方法，将三维空间局部看成二维，再利用Delaunay三角剖分，最后将各个部分无缝拼接，将三维图形重建出来。降低了问题的复杂度，也保证了重建的质量。1算法描述算法先进行K邻域搜索、切平面构建和法向量一致化，在得到法向量后将三维坐标系转化成二维坐标系，接着进行二维Delaunay三角剖分，最后重新投影回三维并用OpenGL显示重建后的模型。1.1k领域的搜索通常，计算某点的k个最近领域的方法是求出候选点与其余n-1个点的欧氏距离，并按从小到大的顺序排列，前面的k个点即为候选点的k个最邻近点。但是，这种算法只能运用于点较少的点集，对于海量数据点则因计算时间复杂度而不适应。本文运用了一种基于空间分块策略的k邻域快速搜索算法，考虑了数据点的范围、点的数目k，可以给出接近于最佳搜索速度的分块大小，提高了k个最近邻域的搜索速度。（1）划分包围盒，比较所有点的X，Y，Z坐标，求出其三个维度坐标的最大最小值，这样就可以确定一个长宽高分别为Xmax-Xmin，Ymax-Ymin，Zmax-Zmin的长方体。然后估计立方体子空间的边长L以及用实验系数调整估算其边长为L0。从而确定出此空间区域的栅格数目以及空间坐标位置。（2）将所有采样点分配到相应的包围盒之中，在每个栅格内计算中心点vi到格子内其他点vj（i≠j）的距离，将它们从小到大排列，并存入一个容器中。（3）若单个格子里的点的数目大于K（K近邻的K），则k近邻为从小到大的前K个，反之，则将该栅格边长扩大一倍，重复步骤（2）（3）。