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

文/张书睿 张鹏程

本文在对以往三维三角网重

建算法研究的基础上，提出了一

种基于局部降维原则的改进算法。

该方法通过输入一系列不提供拓

扑结构等附加信息的无组织散乱

点而得到一个流型三角网。算法

首先将数据点空间分块，然后在

局部块中搜索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