相关热词搜索：
【关键词】散乱点 局部降维 三角网重构
文/张书睿 张鹏程
本文在对以往三维三角网重
建算法研究的基础上，提出了一
种基于局部降维原则的改进算法。
该方法通过输入一系列不提供拓
扑结构等附加信息的无组织散乱
点而得到一个流型三角网。算法
首先将数据点空间分块，然后在
局部块中搜索k 邻域，构建最小
二乘切平面，并将坐标由三维转
化成二维将三角剖分建立在二维
上。通过将采样点投影到局部的
切平面上，再对投影点进行三角
化，最后将这些投影后点的连接
关系直接映射回三维空间。本文
创新性地利用局部降维方法，利
用OPENGL 编程实验证明，整个系
统运行良好，可以为真三维三角
面片自动构建提供新思路。
摘 要
表面重建是在计算机图形学和几何学中
一个非常重要的研究问题，在计算机视觉、逆
向工程、虚拟现实等领域都有很重要的研究意
义。鉴于点云数据格式简单，存储方便以及其
可以突出复杂物体的细节部分，将其作为重建
的模型具有很大的研究意义。
二维散乱点Delaunay 网格剖分已经得到
很好的解决，在利用计算机视觉对客观世界重
建的过程中，遇到更多的是三维散乱点。对三
维散乱点三角面片自动生成，最常用的方法是
投影到二维，然后利用二维算法构建，这种方
法对2.5 维的问题可以很好解决，但对真三维
数据往往效果不好。本文改进了算法上的不足
以尽可能提高重建的精确度，研究了一种通过
三维散乱点集生成流形三角网的算法。本文算
法是一种基于投影的方法，将三维空间局部看
成二维，再利用Delaunay 三角剖分，最后将
各个部分无缝拼接，将三维图形重建出来。降
低了问题的复杂度，也保证了重建的质量。
1 算法描述
算法先进行K 邻域搜索、切平面构建和
法向量一致化，在得到法向量后将三维坐标系
转化成二维坐标系，接着进行二维Delaunay
三角剖分，最后重新投影回三维并用OpenGL
显示重建后的模型。
1.1 k领域的搜索
通常，计算某点的k 个最近领域的方法
是求出候选点与其余n-1 个点的欧氏距离，并
按从小到大的顺序排列，前面的k 个点即为候
选点的k 个最邻近点。但是，这种算法只能运
用于点较少的点集，对于海量数据点则因计算
时间复杂度而不适应。本文运用了一种基于空
间分块策略的k 邻域快速搜索算法，考虑了数
据点的范围、点的数目k，可以给出接近于最
佳搜索速度的分块大小，提高了k 个最近邻域
的搜索速度。
（1）划分包围盒，比较所有点的X,Y,Z
坐标，求出其三个维度坐标的最大最小值，
这样就可以确定一个长宽高分别为Xmax-
Xmin,Ymax-Ymin,Zmax-Zmin 的长方体。然后估计立
方体子空间的边长L 以及用实验系数调整估算
其边长为L0。从而确定出此空间区域的栅格
180 • 电子技术与软件工程 Electronic Technology & Software Engineering
计算机技术应用 • the Application of Computer Technology
数目以及空间坐标位置。
（2）将所有采样点分配到相应的包围盒
之中，在每个栅格内计算中心点vi 到格子内
其他点vj(i ≠ j) 的距离, 将它们从小到大排列，
并存入一个容器中。
（3）若单个格子里的点的数目大于K（K
近邻的K），则k 近邻为从小到大的前K 个，
反之，则将该栅格边长扩大一倍，重复步骤（2）
（3）。
1.2 切平面的估计
因为在重建过程中，我们需要先在二维空
间内实现约束Delaunay 三角剖分，所以我们
需要得到顶点v 及其相邻顶点（记作N(v)）
之间的连接关系，即需要把N(v) 投影至一个
二维平面上T(v)。重建表面的质量在很大程度
上取决于投影平面的选择，合理的选择投影平
面对之后的重建效果有非常大的影响。
选择顶点v 作为切平面的中心oi，要求k
个邻近点到切平面的距离的平方和最小，可以
建立以下矩阵：
矩阵CV 的最小的特征值所对应的单位特
征向量即为ni 或-ni，ni 是切平面的法向量。
1.3 法向量的一致化
重建以后得到的法向量可能指向表面
的内侧或外侧（如图1）， 为了满足应用
需要，相邻三角形的夹角要小于90°，亦即
ni·nj>0。所以需要对各顶点处切平面法向作
一致化处理。
假设pi 和pj 是表面上相邻的点，它们的
单位法向量应该连续变化，所以其变化应该非
常小，其点积的绝对值近似等于1，且点积的
符号应该为正。为了提高法向量调整速率，可
将法向量一致化的问题转化成图的最小生成树
问题。首先根据样本点和每个点的k 邻域生
成无向连通图G=(V,E)，这里每个样本点作为
图的顶点V，每个样本点和其邻域组成的边缘
作为图的边缘E，每个边缘i,j 的权值定义为
1-|ni·nj|，其中，ni 与nj 是点i 和j 的法向量。
相应的应该有1-|ni·nj| ≈ 0， 如果
|ni·nj|<0，说明它们方向分别指向了表面两侧，
则应当被反向。否则不改变nj 的方向继续这
个过程。最终得出法向量一致化后的图形（图
2 即为法向量一致化后的局部三角面片）。
1.4 坐标系转换
求得了点的法向量之后，要将中心点v
和它相邻的点投影在切平面T(v) 上，创建局
部的二维坐标系。以点v 为原点o，v 处的法
向量为z 轴，切平面上任意两正交向量为x 轴
y 轴，定义该局部坐标系。记法向量N 坐标为
（n0,n1,n2），X 方向上的单位向量记作X，其
坐标设为， )。Y 方
向上的单位向量Y 为N×X。
局部坐标系中的坐标为（u，v）=（d·N，
d·X），其中d 是从顶点指向待投影点的向量。
记投影后的近邻点为Q’={q1’，
q
