基于TIN模型的LOD算法研究

基于TIN模型的LOD算法研究

为了实现基于不规则三角网(TIN)地形模型的动态细节简化模型,文中介绍了一种有效的方法,即在一种新的三角网数据结构基础上,通过重复执行模型中边的“折叠”(即顶点“合并”)操作,预先计算模型中每个顶点“重要性”值,根据“重要性”对模型的三角形和顶点列表进行重新排序并将结果存储在数据结构中。在显示过程中,根据对地形的精度要求和事先存储的结果自适应地快速获取所要显示的顶点和三角形,实现TIN模型的实时动态构网显示。基于该算法在两个不同细节的TIN模型进行过渡时可以进行快速线性插值,实现了不同细节模型间的连续过渡。

标签：不规则三角网(TIN);细节分层(LOD);动态构网

1 算法设计

LOD模型的建立,首先要面对模型简化的问题。为了得到模型中每个顶点对模型几何特征表现的价值,在模型简化时吸收了Hoppe H的累进网格(Progressive Mesh)算法思想。这种方法通过重复应用简单的边的折叠(顶点到顶点的合并)操作来简化一个复杂的模型。如果相邻的LOD模型之间相差仅一个或两个多边形,则转化的过程本身就可近似得到LOD模型的视觉连续性。另外,为了实现不规则三角网模型的实时动态构网,预先将所有可以事先完成的浮点计算任务提前做完并将结果存储下来,在显示时根据存储的结果迅速恢复当前条件下的不规则三角网结构达到实时动态构网的目的。在两个不同层次LOD模型进行过渡时进行线性插值,实现模型连续变换。算法的总体思路如下所述:

(1)读入地形模型数据,建立三角形拓扑关系,将数据保存在一个顶点和三角形的列表中。

(2)计算模型中每个顶点的“合并”价值,按照顶点合并价值,将原始三角形和顶点列表进行重新排序,使最重要的点,即最能保留地形模型特征的点排在最前面,并将数据处理结果存储起来。

(3)在视景显示过程中,根据显示精度或显示要求,自适应地推算出所要显示的顶点和三角形个数,按照存储的三角形和顶点列表的顺序,直接进行动态构网及显示。在两个LOD模型过渡时进行线性插值,实现连续平滑的过渡显示。

1.1 数据结构

对于TIN三角网而言,其基本的要素是构成三角网的离散点和三角形,同时还要兼顾三角网生成时需要的拓扑关系和简化时每个顶点相邻的顶点和三角面,以及为了构网快速而建立的点索引列表。为此设计了顶点和三角形数据结构。基于这样的数据结构,对于每个顶点可以知道其在点索引中的位置,在构网时是否满足狄洛尼的条件以及用于网络简化时所必须知道的顶点周围的邻接点、邻接三角形、折叠点以及折叠三角形、折叠代价值。顶点的ID号用来表示在按折叠值大小排号序号后的初始值,在另外建立的一个只有三角形点号的列表只需对这个序号进行排序即可。对于每个三角形,可以知道三角形的每条边、相邻三角形、法向量、在点分区中的位置以及为了建立拓扑关系所必须知道的三角形圆心。

1.2 边的折叠价值的计算

对于三角形的简化,核心是找到应该剔除的顶点。因此一个首要的原则是,当选中的边折叠后,整个模型的改变最小。我们采用了HoppeH的累进格网思想来计算每个点的重要性。边的折叠价值计算公式表示如1-2-1:

cost(u,v)=‖u-v‖×maxmin[(1-f·nomal·

nnomal)÷2]1-2-1

其中f∈Tu,n∈Tuv

其中,Tu是三角形数组中包含顶点u的三角形数组;Tuv是三角形数组中同时包含顶点u和顶点v的三角形数组。这样既考虑了折叠边长的影响,也考虑到了折叠边的弯曲程度的影响,较好地反应了折叠边的折叠度量。

1.3 顶点的折叠、移去和排序

对所有的顶点进行折叠代价值的计算并进行排序,记录每个顶点和邻近顶点组成的边的折叠代价值。通过比较得出最小的一个,将其存储在顶点的成员变量objdist和collaPSepoint中。然后再对所有顶点按折叠价值大小进行排序,把重新排序过的顺序存放在顶点的ID中,再把这一顺序放在新建的顶点列表中。对新顶点列表的第一个点进行折叠操作,在新顶点列表中找到这个点,将其删去。然后将

折叠三角形注上已经删除标志,将删除点的邻接点中不包括当前点的邻接点的点加到当前点中,将删除点的邻接三角形中不包括当前点的三角形加到当前三角形中,并把这些三角形顶点中的删除点替换为当前点。最后对涉及到折叠边两点的邻接点一一计算折叠值。并在新顶点列表中进行重新排序。然后依次折叠下一个折叠边,直到满足事先要求的顶点数或所有新顶点列表中的点均已进行折叠操作为止。

1.4 边自交现象的消除

若不对折叠边进行事先判断,而折叠边周围的几何形状又恰恰非常不理想,则会出现边的自交现象。经我们反复研究发现,边自交现象仅和删除点及其邻居点组成的多边形的形状有关。因此可以把这个多边形定义为影响多边形,把组成折叠边的两点定义为折叠点和当前点(欲折叠到折叠点的点),影响多边形底边与当前点组成的三角形定义为折叠后三角形。于是只有满足下列两个条件的影响多边形在折叠后才不会发生折叠现象:

(1)折叠点和当前点不能出现在影响多边形任一底边的异侧。

(2)除当前点外任何一个影响多边形的顶点不能出现在折叠后三角形当前点与两底边点形成的扇形区域内。

基于以上定义,在边折叠操作以前,先做一个预判,若删去点后会出现边的自交现象,就不进行边的折叠操作。这样就避免了点自交现象的出现,使构网能够顺利正确进行。

2 实验

为了检验本算法的实用性,采用一组地形模型数据对算法进行了检验。实验所用的设备主要配置为Intel(R) Core(TM)2 Duo CPU P8700,2G内存,ATI显卡,操作系统是Windows XP,实验时采用的分辨率为1280

*800,32位的增强色。实验

主要测试算法的简化效果以及对原始模型数据量的适应性。

3 结语

通过本算法,实现了基于不规则三角形连续LOD地形模型的快速构建和实时显示。但在实验过程中发现,在进行地形模型简化过程中,有时会出现边的自交现象。问题可能出现在显示时进行边的折叠操作仅仅考虑顶点和三角形数目的要求,而没有考虑到在顶点变化的过程中网络结构的优化,这需要在今后得到进一步解决。

参考文献 [1]

LINDSTROM P, KOLLER D,RIBARSKY W,et al. Real-time,continuous

level of detail rendering of height fields[EB/OL].

[2]

Hoppe H. Progressive meshes[A]. ACM Computer GraphicsProc. Annual

Conference Serie(Siggraph’96)[C].1996:99-108.

[3]

MARK DUCHAINEAUY,MURRAY WOLINSKY. ROAMing Terrain:

Real-time Optimally Adapting Meshes[EB/OL].

[4]

陳刚.虚拟地形环境的层次描述与实时渲染技术的研究[J].信息工程大

学测绘学院, 2000.