ABSTRACT

Triangulation under the line features constraint is the foundation of urban 3D modeling. Based on the analysis of the algorithms related with Constraint Delaunay Triangulation, a method based on two-step is proposed in this paper; firstly the data point index is established using Hash function method, then the initial triangulation mesh of unconstrained data is generated using the surface growth method, and local network is triangulated in the affected area of constrained line segments, and a complete three-dimensional model is reconstructed. Finally, taking the building reconstruction as an example, the validity and reliability of the proposed method are verified by comparison and analysis.

Keywords:Line Feature, Constraint, Reconstruction

线特征约束的三维无序点云网格模型重建

梁艳

江苏海事职业技术学院，江苏 南京

收稿日期：2018年4月3日；录用日期：2018年4月13日；发布日期：2018年4月20日

摘 要

顾及建筑物轮廓特征的三维表面网格剖分是城市三维建模的基础。本文在对比分析了约束数据域的Delaunay三角剖分相关算法的基础上，提出了一种适用于线特征约束的三维无序散乱点云的三角网格剖分方法，该方法首先用Hash函数方法建立数据索引，然后利用生长法对无约束数据域进行三角网格剖分构建初始三角形，再在约束线段的影响区域内采用插入–交换相结合的算法进行三角网局部重建，从而实现了线特征约束的三维点云网格模型重建。最后以建筑物的模型重建为例进行验证，结果表明本文方法能有效地保证模型的正确性，有助于城市三维建模工作。

关键词 :线特征，约束，重建

Copyright © 2018 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

随着数字城市进程的不断推进，基于城市三维点、线数据的模型重建越来越受到人们的重视 [1] ，由于不规则三角网(Triangulated Irregular Network，简称TIN)能够通过从不规则分布的数据点生成的连续三角面来逼近目标表面，因此在各领域中得到广泛应用。标准的Delaunay三角网可以满足无任何约束条件的散点域的三角形剖分，又称为Delaunay三角剖分(Delaunay，Triangulation，简称为DT)，目前最常用的算法有分治算法、逐点插入法、三角网生长法。而现实世界中的地理实体形态各异、千变万化，部分散点之间常常存在着某种约束关系，如道路边界、建构筑物的轮廓边界等，在对此种数据域进行三角剖分时，三角剖分结果应保持其原有的约束关系，即约束数据域下的三角剖分(Const rained Delaunay Triangulation，缩写为CDT) [2] ，单纯依靠无约束的标准Delaunay三角剖分，其重建结果的正确性很难得到保证。能否在建筑物的表面重建过程中顾及特征提取的结果进行约束三角剖分，实现建筑轮廓等线特征来对表面重建过程进行指导和约束，是本文研究的基本目的之所在。

本文首先简要分析现存的约束数据域下的Delaunay三角剖分算法，并重点剖析了两步法建立CDT的方法步骤，在建立数据索引的基础上，实现线特征约束的三维点云网格模型重建。

2. CDT相关算法分析

综合分析有关文献，CDT的构造算法可归纳为如下几种:

1) 约束图法。Lee在1986年通过计算约束数据域的可见性，并检测优化可见性图从而形成CDT [3] ，算法时间复杂度为O(n2)。

2) 分割-合并算法。Lee于1980年提出了非约束数据域Delaunay三角剖分的分割-合并算法，Chew将其运用至约束数据域 [4] ，分割-合并算法执行效率较高(O (nlogn))，但约束线段的存在使得分割过程的实现比较困难。

3) 加密算法。Boissonnar将约束数据转换为非约束数据，首先对约束线段进行加密，然后对加密后的数据进行非约束的Delaunay三角剖分 [5] 。加密过程的时间复杂度为O(NlogN)，该算法简单易实现，加密过程加大了数据量，并改变了原来的数据集。

4) Shell三角化算法。Piegl提出了Shell三角化算法，该算法由任一约束线段开始，以可见性和空外接圆特性为准则寻找可扩展的第三点 [6] 。将第三点确定之后，以三角形的三边为基础继续扩展三角网形成整个三角网。

5) 两步法。该算法是目前应用较多的一种方法，以Sloan [7] 和Floriani [8] 为代表，即首先对约束数据建立非约束Delaunay 三角网作为初始三角网，然后嵌入约束线段对局部网格进行调整优化。Floriani的算法较为灵活，第一步只需建立非约束数据点的初始三角网，第二步在初始三角网中通过调整插入约束线段。Sloan在约束线段嵌入过程中，利用对角线交换法实现，这一算法适用于对角线对应的四边形是严格凸的，因此实际应用较为困难。

3. 基于两步法建立CDT的过程

由于两步法建立CDT算法更具有灵活性，应用广泛。本文重点围绕两步法建立CDT的方法进行研究，首先对点进行初始Delaunay三角剖分，然后将约束边嵌入到初始Delaunay三角网中。为了提高数据搜索效率，在三角网格模型重建之前，本文采用Hash函数的方法对空间数据建立索引。

3.1. Hash索引建立

Hash函数算法是以空间划分为策略的一种散乱点云空间划分方法 [9] ，利用Hash函数的算法建立索引，可以进行数据点云包围盒的直接定位，以便快速搜索其k邻域。其基本思想是将散乱点集包含在一个长方体包围盒内，包围盒的边长Lx，Ly，Lz。

$\{\begin{array}{l}Lx=\max \_x-\min \_x\\ Ly=\max \_y-\min \_y\\ Lx=\max \_z-\min \_z\end{array}$ (1)

其中min-x，max-x，min-y，max-y，min-z，max-z为三维离散点集三个坐标轴方向的最大与最小坐标值。

然后再对整个长方体包围盒进一步进行划分，分成许多小包围盒，用于方便进行数据点的k邻域搜索。设定数据点最小包围盒的边长为M：

$Medge=\sqrt[3]{k\frac{LxLyLz}{N}}$ (2)

其中，N为数据点云的点云数目，k为阈值，一般取值为10~20。可以把长方体包围盒的划分为m * n * l个小正方体包围盒，沿着长方体包围盒的x，y，z坐标方向的划分数目分别为m，n，l。

$$ $\{\begin{array}{l}m=\mathrm{int}\left(Lx/Medge\right)+1\\ n=\mathrm{int}\left(Ly/Medge\right)+1\\ l=\mathrm{int}\left(Lz/Medge\right)+1\end{array}$ (3)

任一数据点P_xi,yi,zi所在的小立方体包围盒索引号为：

$\{\begin{array}{l}i=\left(\mathrm{int}\right)\left(p_{xi}-\min \_x\right)/Medge\\ n=\left(\mathrm{int}\right)\left(p_{yi}-\min \_y\right)/Medge\\ k=\left(\mathrm{int}\right)\left(p_{zi}-\min \_z\right)/Medge\end{array}$ (4)

$cell\_index=i\times j\times k+j\times k+k$ (5)

利用Hash函数方法可以根据所要搜索的目标的索引值计算出搜索目标即数据点所在的小立方体。根据Hash函数可以快速进行k邻域的搜索，提高搜索速度。

3.2. 无约束初始三角网构建

本文采用从空间散乱点局部开始向周围扩张的空间局部生长的方法建立初始三角网。即由种子三角形开始生长，逐步编织成整张三角网格模型 [10] 。如图1所示。具体步骤为：

1) 种子三角形，种子三角形首先需要确定第一个初始顶点，由这个初始顶点开始构建初始三角形。考虑到种子三角形初始点选取的便捷性，选取X，Y，Z坐标轴中单坐标值最大的点中的其中一个点作为种子三角形的初始顶点。根据右手螺旋法则，三角形的法向量向外，搜索三角形的另外两个邻近点，构成三角形的三条边。

2) 三角网格的生长，角网格的生长总是由一条待扩展边寻找一个最优扩展点，然后连接最优扩展点与待扩展边的两个端点，以形成新的三角形 [11] 。在生长过程中，三角网格总是以边界边为扩展边，逆时针方向依次扩展，直到所有点被扩展完毕。

在三角网构建之前，先建立k邻域搜索，将数据点云的空间划分，采用 Hash 函数的定位算法可以很容易寻找到各个数据点的索引号(index)，使得待扩展点的搜索加快效率。

3.3. 约束边的嵌入

在约束边的嵌入过程中，如何确定约束线段的影响域及约束线段影响区域三角网局部重建是实现约束边嵌入的关键 [12] 。

3.3.1. 确定约束线段的影响区

与约束线段相交的三角形组成约束线段的影响区域，线段与三角形的相交可以化简为线段与线段相交 [13] 。根据快速排斥试验和跨立试验判断线段与线段相交的条件 [14] ，线段相交有4种情况，如图2所示，以图2(a)为例，约束线段AB相交的边是P₂P₃，由相交边P₂P₃可以得到其邻接的三角形T₂，再由T₂中另一条与约束线段相交的边P₂P₅得到下1个三角形T₃，这样下去直到找到约束线段另1个端点B所在的三角形T₃为止 [15] 。

约束线段AB的影响域MT = {T₁, T₂, T₃}，为了建立影响域中的拓扑关系，用一个点链表存储影响区域的每个离散点和约束线段的端点，用一个边链表存储与约束线段AB相交的所有边(P₂P₃, P₂P₅)，用一个三角形链表存储三角形(T₁, T₂, T₃)，用一个边链表存储影响区域的外边界所有边(P₁P₂, P₁P₃, P₃P₅, P₄P₅)。当影响区域完成局部重建时，就将其清空，进行下一条约束线段的嵌入。

图1. 生长法三角网格剖分

图2. 约束线段与三角形相交的情况

3.3.2. 约束线段影响区域三角网局部重建

约束边嵌入算法大致可以分为两种，一种就是在嵌入的过程加入附加点，改变原始数据点集。另外一种就在嵌入的过程不加点，通过交换边实现局部重建。

由于基于对角线交换算法受到约束边的影响域是凹多边形的影响而使算法变得不那么稳定；插入附加点的算法不需要考虑凸凹多边形问题，但需要大量的插入点并同时修改三角网的结构。为实现两种算法的优势互补，本文采用插入–交换相结合的算法，实现约束边的嵌入。

1) 若判断与约束边相交边的两个相邻的三角形边界是一个凹四边形，则把约束边与相交边的交点作为附加点加入，连接相邻的顶点，生成两个新的三角形，其中，有一个新的三角形肯定不在新形成的影响域内。如图3(a)所示，约束线段AE，与其相交的第一条边为DF，交点为H，对应的影响三角形为DEF、CDF，影响的四边形CDEF为凹四边形，根据以上思想，将H作为附加点加入剖分，如图3(b)所示，连接与DF相对的顶点E，构成新的三角形DHE，HEF，连接与DF相对的顶点C，构成新的三角形CDH、CHF。在新的三角形DHE，HEF，CDH、CHF中，CDH不在新的影响域中。

2) 若判断与约束边相交边的两个相邻的三角形形成了一个凸四边形，则通过对角线直接交换即可除去相交边，新构成的两个三角形中有一个肯定不在影响域内，从而减少了约束边的影响域内三角形的个数。如图3(b)所示，约束线段AE，与其相交的第二条边为CF，对应的影响三角形为CHF、CFG，影响的四边形CHFG为凸四边形，根据以上思想，去除对角线CF，交换为GH，新构成的三角形影响域中，GHF不在影响域内，如图3(b)所示。

3) 如图3(c)所示，将附加点做为约束边新的起点，目的点不变继续进行约束边的嵌入，直到约束边是三角形的某一边为止，如图3(d)。

4. 实验结果与分析

对大量实际数据进行了测试。其中两组实验数据是某建筑利用近景摄影测量方法获取的三维点云数据，沿建筑物轮廓提取的三维线特征数据为约束数据，图4显示了实验数据中三维空间点与三维约束线线段两种数据配准的分布情况。对实验结果进行分析，按原始算法不经Hash索引构建总耗时分别为23 min、16 min，采用Hash索引后耗时在16 s、14 s左右，生成的三角网如图5所示。

从图5利用本文方法得到的三维网格剖分结果，可以看出三角剖分网格很好地展现了建筑物外表面的几何模型，三角网生长算法使得网格模型的法向量一致向外，本文的约束边嵌入算法使得建筑物的轮廓得到较好的保持，确保了几何模型轮廓信息的正确性。

5. 结论

本文详细研究了线特征约束下的三维无序点云的三角剖分问题，对现有算法进行分析的基础上，探

图3. 添加附加点构建三角形的过程

图4. 原始点云及约束线分布情况

图5. 本文方法生成的网格模型。(a) 建筑1三维网格；(b) 建筑2三维网格

讨了一种基于两步法的三角网格剖分方法，该方法采用Hash函数建立数据索引，利用生长法构建初始三角形，采用插入–交换相结合的算法进行三角网局部重建，实例表明，该方法不仅提高了三维建模的效率，而且保证了三维模型尤其是轮廓信息的完整性和准确性，有助于城市三维建模工作。

基金项目

江苏省测绘地理信息科研项目(JSCHKY201605)。

文章引用

梁 艳. 线特征约束的三维无序点云网格模型重建
Three Dimensional Space Reconstruction from Unordered Point Cloud under the Constraint of Line Feature[J]. 测绘科学技术, 2018, 06(02): 72-78. https://doi.org/10.12677/GST.2018.62009

参考文献