视点相关的复杂模型的简化算法

杨关良， 王 芳

（海军工程大学船舶与动力学院，湖北 武汉 430033）

虚拟现实技术是利用计算机生成逼真的三维视觉、听觉、触觉等感觉形式而形成虚拟世界。但是在实时仿真应用中，场景模型日益趋于多样化，虚拟环境的规模不断扩大，因此在保证较高图像质量的前提下对模型进行简化是有效提高绘制效率的重要手段。

边折叠算法是Hoppe[1]在1993年首先提出来的，它是一种适用于任意二维流形的三角网格模型的优化方法。由于Hoppe 是对一个全局能量函数进行优化，并且几何优化是非线性的，因此，计算量很大，运行速度很慢。为此，Garland[2-3]在1997 年用局部二次误差测度来衡量边折叠的代价，以新顶点到被折叠边的两个顶点相关联平面的距离平方和作为误差测度。论文在Garland边折叠算法基础上，结合视点相关因子对复杂模型进行了简化，并对通用的多边形模型的数据结构进行了改进，实时动态地生成了多层次的LOD模型[4-6]。LOD（Level of Details）技术是指将三维物体用多种不同精度的模型表示，并根据观察点位置的变化而选择不同精度的模型予以成像。

本文在边折叠算法基础上，将边折叠算法与视点相关因子相结合，对复杂模型进行了简化；并使用改进的多边形模型的数据结构，实时动态地生成了多层次的LOD 模型。

1 边折叠算法

图1 边折叠操作(vi, vj )合并为v

2 模型简化算法

2.1 误差测度及新顶点的计算

误差测度用于评价折叠前后产生的模型误差情况。论文中的算法是以执行折叠操作后得到 的新顶点v 到与该顶点相关的三角形集合ip 中每个三角形所在平面的距离的平方和为误差测度，表示为 )(vQ ，这个距离越小越好。

原始模型中的三角面片定义成满足方程nTv+d=0 的平面，其中n=[a b c]T为单位法矢量，d 为常数，则顶点到某一平面上的距离的平方为

如果定义误差矩阵为Mi=(A b c)=( nidini)，则= Mi( v ) = vTAv + 2bTv +c ，将顶点和误差矩阵均用齐次形式表达即为

则 Mi( v ) =vTMiv，所以误差值为

当边对折叠成一个顶点时，折叠后的面片组成与初始边对的两个端点相关的面片组的并集。对原始网格中的每个三角形面片，依照式（2）来计算其误差矩阵，当对原始网格执行折叠操作后，一些顶点的坐标发生改变，在程序中直接使 新顶点的误差矩阵 M = Mi+Mj，其误差值为M ( v) = Mi( v ) +Mj( v)。

由式（2）可知，边折叠操作后的误差测度值为

新顶点位置的确定最优的方法是取v 的位置使 )(vQ 最小，即令 )(vQ 的偏导数为0，求得梯度为 bAv 22 + 。因此，所求最优新顶点的位置为

2.2 层次细节模型的生成

给定初始精细的多边形模型M0，通过连续的边折叠操作，可以自动生成具有不同细节的多个模型，每一个LOD 模型对应于一边折叠操作序列

式中 M0为原始的模型，edgecol 为边折叠，Mn为简化后的模型。

在实际应用中，可依据视点的距离、方向或将LOD 模型投影到屏幕空间，按照模型所覆盖的像素多少来选择适当的LOD 模型。本文采用视点相关因子来选择适当的LOD 模型。

设坐标系原点为O(0，0，0)，视点为V(xv，yv，zv)，目标点坐标为P(xp，yp，zp)，设VP 与VO 的夹角为θ（见图2），则距离d 可表示如下

在VP 的长度一定时，θ 越小的点视觉效果越好。因此，除了考虑距离因素以外，加入一个 视向因子F=sinθ，得到d 的最终表达式为

d 越小，则模型越精细。

图2 视角的影响

2.3 算法实现

在计算机图形学中，常用多边形网格（通常是三角形网格）来描述对象模型，因此本算法的输入模型使用三角形网格表示的模型。对通用的数据结构进行了改进，不仅可以获取每一个三角形顶点信息、每个顶点邻近三角形和顶点信息，而且可以获取顶点与视点的位置参数。数据结构如下：

数据结构定义后，即可通过存储删除顶点和与边折叠操作的序列信息来实现模型的层次细节转化，在交互显示时可随时调用任意层次细节的LOD 模型。

3 实例与分析

为了验证本文所提出的算法，采用了人物面部模型进行了实验，模型简化结果如图3 所示，实验结果表明，该算法在提高绘制速率的同时很好地近似了原始模型的几何特征。

图3(a)为原始模型，有13364 个三角面。

图3(b)为使用Garland 算法简化后的模型，从13364 个三角面简化到2313 个。

图3(c)为使用本文改进算法简化后的模型，从13364 个三角面简化到1628 个。

图3 简化的模型

4 结 束 语

将折叠算法与视点相关因子有机结合所作的改进，达到了在保证视觉效果的前提下，得到较大幅度简化的模型，节省了存储空间，加速了虚拟场景中复杂模型的绘制。但如何将模型的其他一些属性信息如纹理信息、颜色信息、光照信息等，附加到误差度量准则中以获得更符合视觉感知特性的简化模型，有待进一步研究。

[1] Hoppe H, DeRose T, Duchamp T, et al. Mesh optimization [J]. Proc. of the Computer Graphics, 1993, 27： 19-26.

[2] Garland M, Heckbert P S. Surface simplification using quadric error metrics [J]. Proc. of the Computer Graphics, 1997, 18： 209-216.

[3] Schmeder W J, Zarge J A. Decimation of triangle meshes [J]. Computer Graphic, 1992, 16(3)： 64-77.

[4] Alliez P, Meyer M, Debrun M. Interactive geometry remeshing [J]. ACM Transactions on Graphics, 2002, 21(3)： 347-354.

[5] 李现民, 李桂清, 张小铃, 等. 基于子分规则的边折叠简化算法[J]. 计算机辅助设计与图形学学报, 2002, 14(1)： 8-13.

[6] [美]CASTLEMANKR. 数字图像处理[M]. 朱志刚译. 北京： 电子工业出版社, 2002. 390-393.