三维空间建模方法之TEN模型生成算法

在三维空间建模方法中，TEN模型的生成算法应用非常广泛，主要有基于三维栅格的TEN模型生成算法和基于矢量的TEN模型生成算法。

什么是TEN模型？

TEN模型主要有四个基元构成：四面体、三角形 、边和节点 。 一个空间实体由四面体组成，面由三角形组成，线由小三角形的边组成，点由节点组成。 总之，在TEN模型当中，每个节点必须属于某一条边，每条边属于某一三角形，每个三角形属于某一个四面体。由于TEN模型采用的是simplex-complex思想，因此它可以完全描述三维空间中的各种拓扑关系

具体的可以看我之前的文章：面向地理的三维空间模型之TEN模型

基于三维栅格的TEN模型生成算法

基本思想：

三维空间由栅格矩阵表示，空间点通过矢-栅转换算法转换为三维栅格矩阵的一个体元，先利用距离变换生成各空间点的三维Voronoi多面体，再从中提取TEN结构。

距离变换：

将一个含有特征元素和非特征元素的二值图像转换为一个距离图像，其中每个元素的值是该元素到最近特征元素的距离。

基于矢量的TEN模型生成算法

① 基于八叉树的空间分块索引：将顾及参照点的密度差异来对三维空间进行分块，并利用八叉树Morton码作为块的编号；

② 三维凸边界形成：该三维凸边界是由满足Delaunay条件的三角形格网构成的最小封闭多面体，点集中任意两点的空间连线均包含其中。典型方法有前沿推进法和环切边界法。

前沿推进法

以凸包的每一条边作为新生成三角形 的起始边(所有三角形的边按逆时针方向存储)，向 凸包内逐渐“推进”，找到相应一点满足Delaunay构网法则，生成第一层Delaunay三角形。之后，依次以第一层三角形的各边为起始边，找到相应一点满足Delaunay构网法则，生成第二层Delaunay三角形…如此进行下去，直到构网结束(每条新边最多参与两次构网)。

环切边界法

是在凸包链表中每次寻找一个由相邻两条凸包边组成的三角形，在该三角形的内部和边界上都不包含凸包上任何其他点；将这两条凸包边的公共点去掉，得到新的凸包链表。重复以上过程，直到凸包链表中只剩下3个离散点为止。将凸包链表中的最后3个点构成一个三角形，该三角形连同已经找到的三角形形成整体，成为凸包三角形剖分结果。

③ TEN模型生成：由凸边界上的点构成初始四面体格网，然后逐点插入其他包含在凸边界内部的点，形成普通TEN，最后插入约束，形成约束TEN。