三维空间建模方法之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。

北斗航天应用通过测试验证 民航将开展飞行测试 三维空间建模方法之Octree模型的生成算法

作者:,GIS爱好者。
分享本文,请您带上本文链接
分享到:

发表评论