基于体素的DEM处理技术

虽然建立地表地形的数字高程模型就是以地表空间高程信息为基础，建立一种用于描述地表三维形态的模型，但是地表地形模型所描述的侧重点也不尽相同。通常情况下，地表地形模型的描述被视为一种三维空间曲面的仿真，并不是通过实体结构进行构造，然而，当对地表地形中土壤、土质和含水量等进行分析时，地表地形模型的描述又可以视作实体结构对象进行描述。对于矿山复合场的地表对象的仿真来说，显然属于前者，而且若直接以体素形式进行矿区地表的描述，将会因矿区地表范围大而体素众多，以致效率低下、系统开销较高，故基于体素的面绘制方式进行矿区地表地形的仿真。

1.基于体素的面绘制

基于体素的面绘制技术与一般的面绘制技术在本质上是一致的，也是用多个三角形或多边形等面片进行对象的仿真，所不一样的是它们的基础数据结构不同，基于体素的面绘制技术是基于体素集合的数据结构，其形态、属性、位置等信息是直接由体素进行表征，而一般的面绘制技术则是以一系列的面片作为基础的数据结构，它的信息是在各个面片上体现的。若直接采用MC法等基于体素的面绘制技术进行地形表面的构造，则需要用很多三角形去模拟每个体素的形态，这对地形这个仅仅进行三维曲面表达的形体来说过于复杂，若采用面绘制技术进行仿真，则仅需要在原有体素信息的基础上作少量的处理就能满足需求，故采用后者绘制地表地形。

经不确定信息定量化和空间信息场量化等一系列处理后，地表地形对象的空间信息由一些稀疏的空间离散高程点转换成了一个较规则的空间体素的集合。在地表地形体素集合中，每个体素都包括体素位置、体素大小、体素属性等信息，这些体素的信息构成了地表地形模型仿真的基本要素。显然，这些信息需要作进一步转换以适应面绘制技术的需要，即将体素的位置、大小、属性等信息转换为三维空间点信息，并通过面绘制技术所形成的中间面元对地表地形进行三维仿真。根据坐标变换和属性的空间映射过程，可以很容易地进行体素点的逆向映射，从而在一体化模型中将地表地形的体素集合重新映射为空间离散点集合。

在空间离散点集合形成后，即可采用面绘制方式进行地表地形的三维可视化仿真。目前，面绘制方式有很多种，如规则网格法、规则三角形法、不规则三角形法、不规则四边形法等，其中不规则三角形法最为常见。

2.Delaunay三角剖分

Delaunay三角剖分不仅是面绘制方式最常用的方法，也是地表地形仿真比较常用的方法之一，该方法是由Peuker和他的同事于1978年设计的，它是根据区域的有限个点集将区域划分为三角面，三角面的形状和大小取决于不规则分布测点的密度和位置。该方法能够避免地形平坦时的数据冗余，又能按地形特征点表示数字高程特征，因而常用来拟合连续分布现象的覆盖表面。在TIN构成算法中，Delaunay三角剖分以稳定、耗时少、内存占用量小、对轮廓线点集的数据三维分布没有特殊限制等优点成为其最主要的方法之一。在此，采用Delaunay三角剖分作为核心构造地表地形仿真模型。

（1）三角剖分定义。三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段，E为e的集合。那么该点集V的一个三角剖分T=（V，E）是一个平面图G，该平面图满足以下条件。

1）除了端点，平面图中的边不包含点集中的任何点。

2）没有相交边。

3）平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。

（2）Delaunay三角剖分的定义。

1）Delaunay边：假设三角网的边集合E中的一条边e（两个端点为a、b），e若满足存在经过a、b两点一个圆且圆内不含点集V中任何其他点的条件，则称e为一条Delaunay边。

2）Delaunay三角剖分：若点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。

（3）Delaunay三角剖分的准则。

1）空圆准则。Delaunay三角网是唯一的（任意4点不能共圆），在Delaunay三角形网中任一三角形的外接圆范围内不会有其他点存在。

2）最大化最小角准则。在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。

（4）Delaunay三角剖分的特性。

1）最接近。以最近临的三点形成三角形，且各线段（三角形的边）皆不相交。

2）唯一性。不论从区域何处开始构建，最终都将得到一致的结果。

3）最优性。任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形6个内角中最小的角度不会变大。

4）最规则。如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大。

5）区域性。新增、删除、移动某一个顶点时只会影响邻近的三角形。

6）具有凸多边形的外壳。三角网最外层的边界形成一个凸多边形的外壳。(www.xing528.com)

（5）Delaunay三角剖分算法。Delaunay三角剖分是一种三角剖分的标准，实现它有多种算法，根据实现过程，把生成Delaunay三角网的各种算法分为3类，即分治算法、逐点插入法和三角网生长法。上述3类算法中，三角网生长法在20世纪80年代中期以后就很少用到，较常见的是分治算法和逐点插入法，而这两类算法又各有其长处和短处。逐点插入法虽然实现过程相对简单，所需内存较小，但它的时间复杂度高；分治算法虽然时间复杂度低，但算法中存在大量递归，故需要开辟较大内存空间。针对系统平台对内存的依赖较大的问题，故选择逐点插入法进行Delaunay三角剖分，其主要算法有Lawson算法和Bowyer-Watson算法两种。

Lawson算法是Lawson在1977年提出的。其基本原理：首先建立一个大的三角形或多边形，把所有数据点包围起来，向其中插入一点，该点与包含它的三角形3个顶点相连，形成3个新的三角形，然后逐个对它们进行空外接圆检测，同时用Lawson设计的局部优化过程进行优化，即通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。

Bowyer-Watson算法的基本步骤：首先，构造一个包含所有散点的超级三角形，将散点依次插入三角形中；其次，在三角形中找出其外接圆包含插入点的三角形，删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入；最后，根据优化准则对局部新形成的三角形进行优化。

由于Lawson算法思路简单，易于编程实现，故在此采用该算法完成地表地形的Delaunay三角剖分。

3.Delaunay三角网优化

为了使Delaunay三角剖分能够适合矿山地表地形仿真研究的需要，以Lawson算法为基础，对其进行了以下优化。

（1）解决狭长三角形问题。对于直接以地形数据生成的地表三角网格，因为Delaunay三角剖分所产生的剖分结果具有凸多边形性，易生成狭长的三角形，而这些狭长的三角形使地表表现得突兀、不光滑，故需对所生成的三角网格进行调整。其过程大致分为以下3步。

1）在已生成的地表地形三角网的基础上，逐个判断三角形的每个角度，若三角形内存在一角大于某一设定角度，则该三角形为要优化三角形。

2）取该角对边的中点作为新插入点，插入点Q（x，y，z）的坐标可利用对边两端点P（x1，y1，z1）、P（x2，y2，z2）的坐标值形成，计算方法为

3）将新点添加到原地形三角网中，按逐点插入算法重新生成地形三角网。

（2）插入地形特征线问题。对用于表达地形的Delaunay三角网，不仅需要三角形能够正确剖分，还需要对特殊的地形特征线等进行插入，即为建立带约束的Delaunay三角网，其过程包括以下5步。

1）在已生成的Delaunay三角网的基础上，判断所插入的地形特征线与三角网中哪些三角形相交，若线段两端在同一个三角形内则按照逐点插入法插入两端点。

2）判断特征线是否是三角网的一边，若是，则结束；若不是，则继续。

3）若线段两端点有一个在已有三角网顶点上，另一个在相邻三角内，则按照逐点插入法插入另一端点。

4）若线段两端点有一个在已有三角网顶点上，另一个不在相邻三角内，则计算三角网中所有三角形与该线的相交点，按照逐点插入法插入各个交点。

5）若两端点在两个三角形内，则计算三角网中所有三角形与该线的相交点，按照逐点插入法插入各个交点。

（3）解决凹多边形问题。由于Delaunay三角网具有凸多边形性，对于矿区地表地形某些区域如湖泊、河流等对象，它们大多数属于凹多边形特征的空间结构，难以采用Delaunay三角网结构进行直接描述，而需判断三角形边与凹边形拓扑关系，对于那些在凹边形外的边（即不应存在的边）进行裁剪，对于那些在凹边形内的边予以保留。

采用射线法进行凹多边形各边的判断，其过程可分为以下4步。

1）将三维的地表地形映射到二维平面上，并计算Delaunay三角网中各三角形的内心坐标。

2）确定凹边形边界线，以一点为起点，顺次连接各边界点。

3）以射线法为基础，求各三角形内心标与边界线关系，判断内心位置。

4）对于内心在边界以外的三角形，说明该三角形具有不应存在的边，故应删除该三角形。

采用Delaunay三角剖分建立地表地形模型，方法简单、高效，但是该模型所形成的地表地形的光滑度、连续性与高程点的疏密程度及数量关系密切，若采集到的数据量过于稀疏则易导致对实际地形模拟的失真。但由于该三角网格是建立在对体素集合映射的基础上，而在数据预处理中，已经采用不确定信息量化技术对数据量进行了补充，这就避免了这一现象出现，这时的地表地形表达得精确、细腻和连续程度较多的是与仿真地理区域内的体素尺寸相关，与原始采样的数据量和疏密程度关系不大。