高飞
摘要:虚拟现实是计算机平台对客观现实世界的可视化仿真,虚拟现实的关键在于虚拟环境场景的构建,而三维模型是虚拟现实环境建立的基础。本文介绍网格简化的原则和主要方法,重点介绍了边折叠网格简化算法的二次误差测度算法的计算过程,利用该算法对模型进行了简化处理,结果表明,该算法可有效降低三维模型的复杂度,在虚拟漫游中发挥着非常重要的作用。
关键词:二次误差测度算法 网格简化 模型复杂度
中图分类号:TP319 文献标识码:A 文章编号:1007-9416(2016)09-0117-02
现如今,虚拟漫游在现代社会各个技术领域内具有非常好的应用前景,虚拟漫游不仅具有较好的真实性和直观性,同时为用户提供一个更好的沉浸感和实时互动的功能。但是,当满足虚拟漫游的真实度较高的情况下,虚拟场景内物体的模型复杂度就会越来越大,此时,数据量也将变得越来越大,这不仅给硬件的设备带来巨大的运行负担,而且在网络端下载大数据量的虚拟展示模型时的下载时间过长,从而导致用户在浏览时出现内容不顺畅,体验感下降的问题。因此,降低三维模型的复杂度的研究,对于虚拟漫游来说,起着至关重要的作用。本文的内容主要是围绕如何降低三维模型的复杂度进行开展研究。
1 网格简化
在计算机的图形学领域中,通常用多边形网格来对场景中的对象模型进行描述。所谓网格简化,就是通过相应的算法,以网格模型的外观的各种特征不改变的前提下,尽可能的缩减顶点的数目,将原始模型通过近似模型的方式来表示。
一般情况下,网格简化采取的方法是将一些对模型的整体外观影响非常小的图元(三角形、边或顶点)从多边形网格中移出来,从而简化了模型。
网格简化算法:网格模型简化的主要算法是二次误差测度算法(Quadric Error Metric,QEM),它是一种基于边折叠操作的典型的简化算法。QEM算法的主要原理是通过计算顶点到与其相关联平面距离的平方和作为误差度量,依据该误差度量计算边收缩代价。该算法与其他算法比较起来相对简单,且运行速度快,内存消耗小,简化后的网格与原模型具有非常高的相似度。同时,在简化过程中,会产生不同层次结构的简化模型,可以生成多分辨率的细节层次模型,以此显示细节层次模型。该模型不仅可以为物体提供不同的层次,而且还可以加速图形的绘制速度和控制场景的复杂度。
通过计算网格中每个顶点的误差矩阵,即用二次误差测度来测量边的折叠代价,然后再选取一些有效的顶点对进行边折叠操作。具体步骤如下:
(1)设三维网格中顶点v的坐标为(vx,vy,vz)T,平面P为ax+by+cz+d=0,其中a2+b2+c2=1,记P=(a,b,c,d)T。顶点v到平面P的距离平方为:
为新顶点的二次误差测度矩阵。
(2)有效顶点对选择。
三维网格中将满足以下两个条件的顶点对(V1 ,V2)称为有效顶点对:
①(V1,V2)为某一表面上的相邻点,是一条边;
②(V1,V2)不是在一条边上的,但||V1,V2||t。
其中||V1,V2||代表的是两个点之间的距离,t代表阈值参数,它由用户给定。
t的取值对模型的简化程度有很大的影响。当t=0时,算法为边折叠算法。当t值比较大的情况下,网格模型中将连接原本不相接的部分;当t值非常大的情况下,原本相距很远的点将合并起来,模型的简化质量将受到很大的影响。所以,算法不允许模型中本来不相连的部分连接了起来,顶点合并将以下面的形式存在。
(a)边收缩形式。即对模型中的任意一条边L(V1,V2)进行边收缩操作,将一条边的两点合并成一点,由(V1,V2)生成了一个新顶点v。
(b)不构成边的顶点对合并形式。当两个顶点不构成边的情况下,且满足||V1,V2||t,将这两个顶点进行合并。
(3)新顶点计算。
假如方程没有解,那么我们就选取该条边的两个端点V1,V2或其中心点三点位置处,对二次误差测度值最小的点,进行收缩操作,使之成为新的顶点。
(4)完成(3)后,会产生很多新的顶点,此时,对网格中所有的顶点对进行更新,对每一对顶点的Q值进行重新计算。
(5)最后,如果简化的模型符合要求,则结束迭代这个过程,如果不符合要求,重新选择有效的可进行折叠的顶点对,计算这些顶点对每一对的二次误差,将误差存入堆栈中,再次重新计算所有的每一对顶点的Q值,直至满意为止。
2 结果
通过利用网格模型简化的主要算法二次误差测度算法对模型进行简化,效果如图1、图2和图3。
参考文献
[1]张欣,秦茂玲,谢堂龙.基于特征保持的三角形折叠网格简化算法[J].计算机技术与发展,2012,22(1):94-97.
[2]俞静.三维复杂场景优化处理的研究与实现:(硕士学位论文)[D].成都:西南交通大学,2011.