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

《一种三维散乱点局部降维delaunay 网格自动生成算法 》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一种三维散乱点局部降维Delaunay网格自动生成算法【关键词】散乱点局部降维三角X重构文/张书睿张鹏程本文在对以往三维三角X重建算法研究的基础上，提出了一种基于局部降维原则的改进算法。该方法通过输入一系列不提供拓扑结构等附加信息的无组织散乱点而得到一个流型三角X。算法首先将数据点空间分块，然后在局部块中搜索k邻域，构建最小二乘切平面，并将坐标由三维转化成二维将三角剖分建立在二维上。通过将采样点投影到局部的切平面上，再对投影点进行三角化，最后将这些投影后点的连接关系直接映射回三维空间。本文创新性地利用局部降维方法，利用OPENGL编

2、程实验证明，整个系统运行良好，可以为真三维三角面片自动构建提供新思路。摘要表面重建是在计算机图形学和几何学中一个非常重要的研究问题，在计算机视觉、逆向工程、虚拟现实等领域都有很重要的研究意义。鉴于点云数据格式简单，存储方便以及其可以突出复杂物体的细节部分，将其作为重建的模型具有很大的研究意义。二维散乱点DelaunayX格剖分已经得到很好的解决，在利用计算机视觉对客观世界重建的过程中，遇到更多的是三维散乱点。对三维散乱点三角面片自动生成，最常用的方法是投影到二维，然后利用二维算法构建，这种方法对2.5维的问题可以很好解决，但对真三维

3、数据往往效果不好。本文改进了算法上的不足以尽可能提高重建的精确度，研究了一种通过三维散乱点集生成流形三角X的算法。本文算法是一种基于投影的方法，将三维空间局部看成二维，再利用Delaunay三角剖分，最后将各个部分无缝拼接，将三维图形重建出来。降低了问题的复杂度，也保证了重建的质量。1算法描述算法先进行K邻域搜索、切平面构建和法向量一致化，在得到法向量后将三维坐标系转化成二维坐标系，接着进行二维Delaunay三角剖分，最后重新投影回三维并用OpenGL显示重建后的模型。1.1k领域的搜索通常，计算某点的k个最近领域的方法是求出候选

4、点与其余n-1个点的欧氏距离，并按从小到大的顺序排列，前面的k个点即为候选点的k个最邻近点。但是，这种算法只能运用于点较少的点集，对于海量数据点则因计算时间复杂度而不适应。本文运用了一种基于空间分块策略的k邻域快速搜索算法，考虑了数据点的范围、点的数目k，可以给出接近于最佳搜索速度的分块大小，提高了k个最近邻域的搜索速度。（1）划分包围盒，比较所有点的X,Y,Z坐标，求出其三个维度坐标的最大最小值，这样就可以确定一个长宽高分别为Xmax-Xmin,Ymax-Ymin,Zmax-Zmin的长方体。然后估计立方体子空间的边长L以及用实验

5、系数调整估算其边长为L0。从而确定出此空间区域的栅格180•电子技术与软件工程ElectronicTechnologySoft0cm0pt;mso-layout-grid-align:none"class=MsoNormalalign=left>计算机技术应用•theApplicationofputerTechnology数目以及空间坐标位置。（2）将所有采样点分配到相应的包围盒之中，在每个栅格内计算中心点vi到格子内其他点vj(i≠j)的距离,将它们从小到大排列，并存入一个容器中。（3）若单个格子里的点的数

6、目大于K（K近邻的K），则k近邻为从小到大的前K个，反之，则将该栅格边长扩大一倍，重复步骤（2）（3）。1.2切平面的估计因为在重建过程中，我们需要先在二维空间内实现约束Delaunay三角剖分，所以我们需要得到顶点v及其相邻顶点（记作N(v)）之间的连接关系，即需要把N(v)投影至一个二维平面上T(v)。重建表面的质量在很大程度上取决于投影平面的选择，合理的选择投影平面对之后的重建效果有非常大的影响。选择顶点v作为切平面的中心oi，要求k个邻近点到切平面的距离的平方和最小，可以建立以下矩阵：矩阵CV的最小的特征值所对应的单位特征向

7、量即为ni或-ni，ni是切平面的法向量。1.3法向量的一致化重建以后得到的法向量可能指向表面的内侧或外侧（如图1），为了满足应用需要，相邻三角形的夹角要小于90°，亦即ni·nj>0。所以需要对各顶点处切平面法向作一致化处理。假设pi和pj是表面上相邻的点，它们的单位法向量应该连续变化，所以其变化应该非常小，其点积的绝对值近似等于1，且点积的符号应该为正。为了提高法向量调整速率，可将法向量一致化的问题转化成图的最小生成树问题。首先根据样本点和每个点的k邻域生成无向连通图G=(V,E)，这里每个样本点作为图的顶点V，每个样本点

8、和其邻域组成的边缘作为图的边缘E，每个边缘i,j的权值定义为1-

9、ni·nj

10、，其中，ni与nj是点i和j的法向量。相应的应该有1-

11、ni·nj

12、≈0，如果

13、ni·nj

14、<0，说明它们方向分别指向了表面两侧，则应当被反向。否则不