基于二次误差度量的网格简化算法.pdf

第20卷 第5期 2000年10月 北 京 理 工 大 学 学 报 Journal of Beijing Institute of Technology Vol 20 No 5 Oct 2000 文章编号 100120645 2000 0520607206 基于二次误差度量的网格简化算法 吴亚东 刘玉树 高春晓 北京理工大学 计算机科学与工程系 北京 100081 摘 要 网格简化是提高计算机处理复杂模型速度的有效方法 要求算法时间和空间复杂 性低 简化质量高且简化结果中三角形紧致性好 给出一种简化三角形网格表示的三维模 型的算法 算法采用边折叠为基本操作 以点到相关直线的距离的平方为误差度量 为降 低算法的空间复杂性 简化过程中每个点只保留一个浮点数的历史记录 实验结果表明 在P 上 算法可在12 s内简化含7万个三角形的模型 简化结果中三角形紧致性大于019 的三角形数为56 关键词 网格简化 误差度量 细节层次 紧致性 中图分类号 TP 391141 文献标识码 A 收稿日期 20000313 基金项目 高等学校博士学科点专项科研基金资助项目 作者简介 吴亚东 1974年生 博士生 复杂的多边形网格模型对计算机的分析 显示 存储与传输都是很大的负担 网格简化是 提高计算机处理复杂模型速度的有效方法 在众多的网格简化算法中 边折叠的方法得到了广 泛的认同 1 6 其中 Garland的 二次误差度量 Q uadric error metrics 简化算法在时间复杂 度和简化质量两方面都有较为出色的表现 1 该算法以边折叠为基本操作 以点到相关三角形 平面的距离的平方为度量 折叠点的坐标由最小化二次误差确定 此后 L indstrom对点到平 面的距离加权以三角形的面积 以最优化体积的平方求得折叠点的坐标 2 Erikson和Hoppe 的几何误差简化方法也与文献 1 类似 3 4 作者提出一种新的基于边折叠的网格简化算法 注意到Garland的算法对空间要求较高 每个点需10个浮点数的历史记录 L indstrom算法则不保留任何历史记录 为降低空间复杂 度 减少简化误差 算法对每个点保留了1个浮点数的历史记录 文献 1 4 均采用点到相关 平面的距离的平方为误差度量 本算法则以点到相关直线的距离的平方为误差度量 此外 寻 求简化结果三角形紧致性更好的算法是网格简化的重要任务之一 7 实验表明 作者提出的算 法不仅可以产生高质量的简化结果 而且简化结构网格的三角形紧致性很好 1 网格简化算法 111 术语说明 为叙述方便 先简要介绍文中用到的术语及概念 向量均指三维列向量 顶点v的坐标v x y z T 所指的边均为有向边 即e v0 v1 将边e写作v0v1 v1 v0 把点到边所在直线 的距离简称为点到边的距离 v 3 表示所有与顶点v相邻的边的集合 如图1所示 边折叠操作如图2所示 边v0v1折叠为折叠点v引起网格局部形状的变化 如v0v1不是 边界边 则一次边折叠减少2个三角形 3条边 1个顶点 v 边折叠 v1 v0 v 图2边折叠操作图1v 与顶点v相邻的边的集合 112 误差度量 见图2所示 设边v0v1折叠为点v 定义v到v 3 0和v 3 1中各边距离的平方和为该折叠操作 的误差 如图3所示 点v到边v0v1的距离的平方 r 2 v0v 2sin2 v0v 2 1 v0v v0v1 v0v v0v1 2 v0v 2 v0v v0v1 v0v1 2 令s v0v t v0v1 v0v1 则 r 2 s Ts sTt 2 s Ts s T ttT s sT I ttT s 其中 I为单位矩阵 设s0 v v0 ti为v 3 0中边的单位向量 则点v到v 3 0中各边距离的平方和 d v v 3 0 n i 1 sT0 I titTi s0 s T 0 n i 1 I titTi s0 令Q0 n i 1 I titTi 则 d v v 3 0 s T 0Q0s0 1 同样 设s1 v v1 可得点v到v 3 1中各边的距离的平方和 d v v 3 1 s T 1Q1s1 2 综合式 1 2 可得如图2中边v0v1折叠为点v 顶点v到v 3 0和v 3 1中各边距离的平方和 v d v v 3 0 d v v 3 1 s T 0Q0s0 s T 1Q1s1 3 以s0 v v0 s1 v v1代入式 3 整理得 v v T Q0 Q1 v 2 v T 0Q0 v T 1Q1 v v T 0Q0v0 v T 1Q1v1 令A Q0 Q1 bT vT0Q0 vT1Q1 c vT0Q0v0 vT1Q1v1 则边v0v1折叠为点v的误差 v v TAv 2bTv c 4 113 折叠点坐标的确定 在采用边折叠操作的简化算法中 选取折叠点坐标的原则是使简化后的网格形状尽可能 接近原始网格 但目前对简化前后网格的相似程度尚没有公认的度量标准 如边v0v1折叠为 点v 为简单起见 一般可选取折叠点v的坐标为v0 v1或 v0 v1 2 但更好的选择应该是不 局限于边v0v1甚至于该局部网格表面 这里取使 v 值最小的v作为折叠点v的坐标 考虑 到所采用的误差度量方法 这种选择是很自然的 下面推导使 v 值最小的v的值 806北 京 理 工 大 学 学 报第20卷 v 可写作 v v TAv 2bTv c v T 1 A b bT c v 1 P TQP 由矩阵A的定义知A为对称矩阵 故Q也为对称矩阵 又由 v 定义知 v 0 v 3 0 v 3 1中各边所在直线不会全部共线 故 v 是正定二次型 即Q 为对称正定矩阵 A也为对称 正定矩阵 由线性代数最小原理可知 v 在v A 1b 处取得最小值 因A为正定矩阵 故A可 逆 因此 当边v0v1折叠为点v时 点v的坐标v A 1b 114 边折叠消耗函数 注意到112中的误差度量 v 仅表示一次边折叠前后局部网格的差异 而为了有效控制 简化后网格与原始网格的距离 就需要定义一个全局误差函数 如前所述 目前尚没有公认的 网格相似程度的度量标准 一些文献中采用的Hausdorff距离度量计算又比较复杂 8 为减少 计算量 提高简化速度 当边v0v1折叠为点v时 定义其消耗函数 c v v e v0 e v1 5 其中 v 为本次折叠操作引起的误差 e v0 与e v1 分别为点v0 与v1的历史记录误差 设 m为常数 执行该边折叠操作后折叠点v的历史记录误差 e v m c v 6 未执行任何边折叠操作前 即在原始网格中 各顶点历史记录误差均为0 即e vi 0 在 网格简化过程中 随着边折叠操作的进行 每次折叠操作误差的积累 各边折叠的c v 值将不 断增大 因此 消耗函数c v 即可作为本算法网格简化的全局误差函数 在式 5 中 权值m决定了顶点v的历史记录误差对v 3 中各边的消耗函数值的 贡献 m 值越大 则v 3 中各边的消耗函数值将相应增大 v 3 中各边折叠的概率将会减小 在边折叠优先 队列中位置靠后 即v 3 所在的局部区域不会很快再次被简化 实验中取m 1 可得到很好的 简化结果 115 算法流程 本算法以边折叠为基本操作 以点到相关直线的距离的平方为误差度量 按边折叠消耗函 数值的大小将所有边排为升序优先队列 取队首元素执行边折叠操作 删除队列中无效的边 并重新计算与折叠点相邻的边的消耗函数值 将其插入队列 算法执行过程如下 初始化网格中所有点的历史记录误差e vi 0 计算网格中所有边的折叠误差 v 及折叠点v的坐标v 计算边折叠的消耗值c v 按c v 大小将所有边排为升序优先队列 取队首消耗值最小的边vivj执行折叠操作 折叠点v的历史记录误差e v c vivj 删除队列中所有因该边折叠而导致消失的边v 3 i v 3 j 计算v 3 中各边的折叠误差及其折叠后点的坐标v 并计算其消耗值 然后把该边插入 队列 如此时网格的三角形个数多于用户指定的数目 转至 执行下一个边折叠操作 116 三角形紧致性 在网格中 紧致性差的三角形会引起光照处理时的不连续现象 并可能导致某些绘制方法 速度下降 对模型的其他处理结果有很大影响 9 因此网格中应尽量避免紧致性差的三角形 906 第5期吴亚东等 基于二次误差度量的网格简化算法 Delaunary三角剖分的广泛应用在很大程度上正是因为它可以产生紧致性较好的三角形 文 献 2 6 中均对网格中三角形的紧致性做了处理 其中文献 2 是在算法规定的约束不能够确 定折叠点的坐标时 才考虑到三角形的形状 文献 6 则在简化过程中 对边折叠前后局部三角 形的形状进行比较 如边折叠后的三角形形状不满足要求 则放弃该边折叠操作 作者采用文 献 6 中对三角形紧致性的评估方法 即三角形的紧致性 c 43A l20 l21 l22 7 其中 A为三角形的面积 li为边的长度 当三角形为等边三角形时 c为1 三角形面积为0 时 c 0 本算法并未对网格中三角形形状做任何特殊处理 紧致性的计算是在网格简化后进行的 2 实验结果 作者在P 450上用C 实现了上述算法 图4 图5为实验的部分结果 表1为与文献 1 算法相比较的实验数据 a 原始模型 b 简化结果 图4 兔子模型简化结果 简化98 a 原始模型 b 简化结果 图5 手模型简化结果 简化98 本算法的时间复杂度与文献 1 相同 为O nlgn 由于这类算法本身比较简洁 其速度与 其他类型的算法相比是很快的 这一点已为文献 1 2 所证实 本算法空间复杂度小于文献 1 的算法 在简化三角形数很多的模型时 由于内存的限制 程序要进行频繁的磁盘交换 此 时本算法的优点表现得相当明显 016北 京 理 工 大 学 学 报第20卷 表1 与文献 1 算法实验数据比较 模型类型 原始模型 三角形个数 简化模型 三角形个数 Q slim210 1 t s Q slim210 2 简化结构中 c 019的三角形个数 本算法 t s 本算法简化结果中 c 019的三角形个数 兔子69 4511 5008281256 手654 66610 00014 186219 61354 值得注意的是 用本算法简化后的网格的三角形紧致性较好 事实上 利用本算法简化结 果中c 018的三角形数达82 而c 019的三角形数所占比例均大于50 而文献 6 中给出的结果为39 作者对不保留历史记录的情况也做了实验 发现在不保留历史记录的情况下 即e vi 始 终为0时 简化结果的三角形形状更为规则 例如不保留历史记录时 简化兔子模型为1 500 个三角形 c 019的三角形数达65 但在这种情况下 模型简化结果的细节消失得较快 3 结 论 作者提出的网格简化算法以边折叠为基本操作 以点到相关直线的距离的平方为误差度 量 简化过程中每个点保留一个浮点数的历史记录误差 算法按边折叠的消耗函数值对网格中 的边进行排序 依次取消耗值最小的边执行折叠操作 直至网格中的三角形数达到用户指定的 数目时为止 算法速度快 空间复杂度小 简化结果质量较高 此外 算法所用的误差度量方法 可以获得三角形紧致性很好的简化结果 该算法可用于交互可视化中的多细节层次场景的自 动生成和有限元模拟 进一步的工作包括改进算法以使其能够更好地处理边界边 并提供对模 型法向量和纹理属性简化的支持 参考文献 1 Garland M Heckbert P Surface si mplification using quadric error metrics A W hitted T Proceedings of SIGGRA PH 97 Computer Graphics Proceedings A nnual Conference Series C Los A ngeles A ddison W esley 1997 209 216 2 L indstrom P Turk G Fast and memory efficient polygonal si mplification A Ebert D Hagen H Rushmeier H IEEE V isualization 98 C North Carolina IEEE 1998 279 286 3 Erikson C M anocha D GA PS General and automatic polygonal si mplification A Hodgins J Foley J 1999ACM Symposium on Interactive 3D Graphics C A tlanta ACM 1999 79 88 4 Hoppe H N ew quadricmetric for si mplifyingmeshesw ith appearance attibutes A EbertD GrossM Hamann B IEEE V isualization 99 C San Francisco IEEE 1999 59 66 5 Hoppe H Progressive meshes A Rushmeier H Proceedings of SIGGRA PH 96 Computer Graphics Proceedings A nnual Conference Series C N ew O rleans A ddison W esley 1996 99 108 6 Gu ziecA Locally toleranced surface si mplification J IEEE T ransactions on V isualization and Computer Graphics 1999 5 2 168 189 7 Heckbert P Garland M Opti mal triangulation and quadric2based surface si mplification J 116 第5期吴亚东等 基于二次误差度量的网格简化算法 Journal of Computational Geometry Theory and Applications 1999 14 1 3 49 65 8 Klein R L iebich G Stra erW M esh reduction w ith error control A YagelR N ielson G IEEE V isualization 96 C San Francisco IEEE 1996 311 318 9 M arkosian L Cohen J Crulli T et al Skin a constructive approach to modeling free2form shapes A Rockwood A Proceedings of SIGGRA PH 99 Computer Graphics Proceedings A nnual Conference Series C Los A ngeles A ddison W esley Longman 1999 393 400 M esh Si mplif ication Based on Quadric ErrorM etrics WU Ya2dong L I U Yu2shu GAO Chun2xiao Department of Computer Science and Engineering Beijing Institute of Technology Beijing100081 Abstract M eshsimplification can efficiently improvethe p