基于加权二次误差测度的边折叠简化算法.pdf

基于加权二次误差测度的边折叠简化算法 第六图书馆 针对许多边折叠网格简化算法在模型进行大规模简化后 不能很好地保持原始模型的重要几何特征 从而产生较严重的视觉失真 现象的问题 提出了2种改进的二次误差测度边折叠方法 定义2种三角形重要度并嵌入到原始Garland的二次误差测度中 使得误 差测度不仅能度量距离偏差 而且能反映模型局部表面几何变化 结果表明 新的算法在大规模简化后仍然能保留相当多的重要 几何特征 降低了视觉失真 针对许多边折叠网格简化算法在模型进行大规模简化后 不能很好地保持原始模型的重要几何特征 从而产生较严重的视觉失真现象的问题 提出了2种改进的二次误差测度边折叠方法 定义2种三角形重要度并嵌入到原始 Garland的二次误差测度中 使得误差测度不仅能度量距离偏差 而且能反映模型局部表面几何变化 结果表明 新的算法在大规 模简化后仍然能保留相当多的重要几何特征 降低了视觉失真 计算机图形学 表面简化 迭代方法 边折叠 二次误差测 度北京工业大学学报杜晓晖 尹宝才 孔德慧北京工业大学计算机学院多媒体与智能软件技术北京市重点实验室 北京 1000222007第六图书馆 第六图书馆 第 3 3 卷第 7期 2 0 0 7年7月 北京工业大学学报 J OURNAL OF B EI J I NG UNI VERS I TY 0F TE CHNOLOGY Vo 1 3 3 NO 7 J u 1 2 0 0 7 基于加权二次误差测度的边折叠简化算法 杜 晓晖 尹 宝才 孔德慧 北京工业大学 计算机学院 多媒体与智能软件技术北京市重点实验室 北京 1 0 0 0 2 2 摘要 针对许 多边折叠 网格简化算法在模型进行 大规模简 化后 不能很 好地保 持原始 模型的重 要几何特 征 从而产生较严重 的视觉失真现象的问题 提 出 r 2种改进的二次误差测度边折 叠方法 定 义 2种三 角形重要度 并嵌入到原 始 G a r l a n d的二次误差测度 中 使得误差测度不仅能度量距 离偏差 而且能反映模型局部表面几何变 化 结果表明 新的算法在大规模简化后仍然能保留相当多的重要几何特征 降低了视觉失真 关键词 计算机图形 学 表面简化 迭代方法 边 折叠 二次误差测度 中图分类号 TP 3 9 1 文献标识码 A 文章编号 0 2 5 4 0 0 3 7 2 0 0 7 0 7 0 7 3 1 0 6 网格简化一直是计算机图形学中一个重要 的研究分支 随着三维扫描技术和造型技术 的发展 获取 大数据量的三角网格模型变得越来越容易 然而数据量的增加给模型的存储 传输以及绘制等图形学中 很多的应用带来了困难 为了降低模型数据量 提高应用效率 网格简化成为一种简便有效的手段 目前 已有的网格简化算法主要有 顶点删除 三角形删 除 顶点 聚类 区域 合并 重新布 点 引 边折 叠 6 9 三角形折叠 m 以及基于小波的简化 l l J 等算法 其中边折叠算法是按照一定的误差度量准则不断 将引起误差最小的边折叠为一个新顶点 并将与该边 2个端点相连接的顶点与新顶点连接 这种方法可 以生成连续的细节层次 支持模型的渐进传输与绘制 l J 因此成为计算机图形学中一种重要的三角网 格简化算法 边折叠算法关键在于根据一定的误差测度确定折叠次序和边折 叠后新顶点的位置 H o p p e 在 1 9 9 3 年首先采用能量优化的方法实现边折叠算法 6 J 该算法 定义一个全局能量 函数来确定边折叠的误差 并 由此决定边折叠顺序和新顶点位置 由于求解能量函数的最优解是个非线性问题 因此时间复杂度高 速 度慢 不适用于对时间要求较高的场合 为了降低时间复杂度 G a r l a n d在 1 9 9 7年提出了二次误差测度的 方法 7 J 将边折叠的误差定义为 折叠后的新顶点到一组平面的距离平方之和 这组平面是与被折叠边的 2个端点相关联的原始平面 这种方法计算简单 速度快 而且能得到与 H o p p e 能量优化方法质量很接近 的简化模型 李现民于 2 0 0 2年在 Ga r l a n d 算法基础上 采用蝶形子分模式生成新的顶点 进一步减小了简 化模型和原始模型之 间的误差 但时间复杂度增加 8 J 由于以上方法在误差测度中只考虑了距离的度量 简化后的网格分布较为均匀 因此大规模简化后并不能很好地保持模型表面重要的几何特征 造成较大的 视觉失真 为了保持重要几何特征 Y o u n g i h n Kh o在 2 0 0 3年通过用户交互方法 9 J 在模型表面手工选择 重要区域 并增大这些区域中边折叠惩罚代价来保持这些 区域的几何特征 虽然这种方法能产生较好的 效果 但需要人工干预 不适用于自动简化的情况 为了在大规模 自动简化时保持模型在低分辨率下的视觉效果 同时不过多增加简化误差和时间复杂 度 作者定义了三角形重要度概念并嵌入到 G a r l a n d的二次误差测度中 使得误 差测度不仅能度量距离偏 差 而且能反映模型局部表面几何变化 实验结果表明 新的误差测度能合理分布顶点密度 保持 了二次 误差测度快速 高效的特点 在大规模简化后仍然能保留相当多的重要几何特征 降低了视觉失真 收稿 日期 2 0 0 6 1 1 2 7 基金项 目 国家 自然科学基金 6 0 5 7 2 1 0 4 6 0 5 3 3 0 3 0 北京 市 自然科学基 金 4 0 6 1 0 0 1 作者简介 杜 晓晖 1 9 7 5 一 男 山西五 台人 博士生 维普资讯 第六图书馆 第六图书馆 7 3 2 北京工业大学学报 2 0 0 7正 1 相关工作 由于 G a r l a n d的边折叠算法速度快 简化质量较高 因而成为一种经典的边折叠算法 该方法定义每 个顶点 1 T的误差为 与其相关联平面集合P 的距离平方和 这个误差测度可以写成 二次型形式 p T V T P P T T K p P p p P p p P p 式中 p是由方程 n z c d 0 n b C 2 1 定义的与 相关联三角形所在平面 Kp 是平面p 的基本误差二次 f u n d a me n t a l e r r o r q u a d r i c r a n b n c n l T l n 6 b b c b d K t I J a c b c c c I 6 c 把Q K 称 为 顶点 二 次 误差 测度 矩阵 初始 化时 由 于 每 个原 始 顶点 都是 其相 关 联三 角面 片的 pC P p 交点 因此原始顶点 的初始误差 0 当进行边折叠时 一 新顶点 的最优位置和边折叠 代价分别为 口1 1 口1 2 口1 2 口2 2 口1 3 口2 3 0 0 口1 3 口1 4 q2 3 q2 4 口3 3 q3 4 0 1 折 叠 后 的 二 次 误 差 测 度 矩 阵 Q Q Q I 口 1 1 口 1 2 口 1 3 口 I 口 口 口 口 14 l 口1 3 口2 3 q 3 3 口3 4 2 这种方法速度快 简化后模型表面误 差均值较低 但 由于只考虑距离的度量 因此 网格顶 点分布均匀 在大规模简化后 模型表面较为尖锐的 棱角等重要几何特征丢失 2 改进的二次误差测度 在基于二次误差测度的边折叠简化算法中 边折叠的顺序和新点的位置是 由二次误差测度决定 而二 次误差测度的值最终是 由原始模型三角面片的基本误差二次型 K 决定的 因此如果在每个原始三角面 片基本误差二次型上乘一个自适应的权值 将改变边折叠的顺序 并影响折叠后新顶点的最优位置 同时 并不改变二次型的基本性质以及初始误差值 在二次误差测度中 G a r l a n d用三 角形面积作为权值 对保 持模型整体质量取得一定效果 但三角形面积并不能反映局部表面变化程度 因此简化后模型网格分布仍 然较为均匀 为了使这个权值能够连续反映局部表面变化 同时能 自适应地选取 在本节定义了三角形重 要度概念 并将其作为权值嵌入二次误差测度中 2 1 三角形重要度 第 1种三角形重要度 对于给定的三角面片 p 以及 p的一个顶点 将 1 一I l n f I 0 1 维普资讯 第六图书馆 第六图书馆 第 7期 杜晓晖等 基于加权二次误差测度的边折叠简化算法 7 3 3 定义为三角形 P相对于顶点 v的重要度 即第 1 种三角形重要度 其中 是顶点 v的法向量 p是三角 形p所在平面的法向量且 J I 1 J J 1 图 1 a 给出了定义第 1种三角形重要度的三角面片法向量 和顶点法向量的示意图 由于 和 p都是单位向量 因此内积 n p就是这 2个向量夹角的余弦 顶点 v的法向量可以通过求其相关联三角面片P i 的法向量 p 之和得到 即 因此 n p p 酉 酉 这个内积包含了 P与 关联的所有三角面片P 之间二面角的变化 当顶点 的局部区域 为平面时 P与 P 的二面角都为 0 此时 P相对于 的重要度为 0 当 的局部表面 曲率较大时 P相对于 的重要度增 大 而当 v是局部尖锐点或凹陷点时 P的重要度趋于 1 因此三角形重要度连续反映 v了点附近区域表 面变化情况 第 2种三角形重要度 给定三角面片 P 定义 p的第 2种重要度为 P 专 卜 l 玑 p 1 p 0 1 i 1 其 中 i 1 2 3 是三角形 P的 3个顶 点 是对 应的顶点法向量 且 l l 1 图 1 b 给出了定义第 2种三角形重要度的三角面片法 向量和顶点法 向量 的示意图 第 2种三角形重要度是 P相对于 3个顶 点的第 1种重要度的平均值 涉及到 P的 3个顶点周 围局部区域的变化 第 2种三 角形重要度 比第 1种 三角形重要度能反映更大区域的表面变化 但由于是 平均变化量 对尖锐区域的反映不如第 1 种明显 2 2 新的误差测度 l a 第1 种 b 第2 种 图 1 三角面片的法 向量和顶点法的向量 F i g 1 Th e f a c e n o r ma l a n d v e r t e x n o r ma l 为了在二次误差中体现局部表面变化 将三角形重要度作为权值嵌入到二次误差测度中 基于第 1 种 三角形重要度的二次误差测度可以写作 卜f p I J K p 由于三角形的第 1种重要度对于每个顶点是不同的 初始化时为原始模型每个三角面片分别求对应 3个顶点的重要度 作为计算对应顶点二次误差测度矩阵时该面片基本误差二 次型的权值 则该顶点的二 次误差测度矩阵为Q 2 v p p P 基于第 2种三 角形重要度的二次误差测度为 3 1 1 一 l 玑 p 1 K p p 由于三角形的第 2种重要度对于 3个顶点相同 可为原始模型每个三角面片单独计算重要度 然后作 为该面片基本误差二次型 K 的权值 则原始模型中顶点 的二次误差测度矩阵 Q p P 把三角形重要度作为基本误差二次型的权值并不改变二次型矩阵的性质 仍然具有累加性 对于边 折叠 V j 一 新顶点位置和边折叠代价仍然可以用式 1 和式 2 的形式进行计算 新顶点 的二次误 一 维普资讯 第六图书馆 第六图书馆 北京工业大学学报 差测度矩阵分别为 Q Q Q 和 Q Q T Q 由于引入三角形重要度 2个新二次误差测度不但能度量距离偏差 而且体现了局部表面变化程度 边折叠的代价以及新顶点的最优位置不仅由距离因素决定 而且受到模型局部表面几何变化的强制约束 高曲率与低曲率区域的边折叠代价差距将被渐进增大 体现了低曲率 区域优先进行边折叠的思想 同时 由于新点的最优位置要使得新点到相关平面加权的距离平方和最小 因此最优位置将偏向权重较大的平 面 即靠近重要度较大的三角面片 因此新的误差测度有利于特征的保持 2 3 边界保持 对于有边界的模型 在简化时应该尽可能保持其边界 为此 为每个边界边生成一个虚拟平面 这个 平面通过该边界边 并垂直于边界边所在三角面片 给该虚拟平面规定一个很大 的重要度作为该平面基 本误差二次型的权值 然后累加到该边界边端点初始的二次误差测度矩阵中 由于虚拟平面重要度很大 所以边界边的折叠代价很高 因此边界可以得到很好的保持 3 结果与分析 为了评估本文基于新的二次误差测度简化算法的性 能 对牛 恐龙和脚骨模型进行 了大规模简化 并 与 Ga r l a n d 7 的箅法做 了比较和分析 牛 恐龙和脚骨的原始模型分别包含 5 8 0 4 4 9 9 9 8和 4 2 0 4个三 角 面片 简化后的模型分别含有 2 4 8 5 5 0和 2 5 0个三 角面片 对于几何误差 从表 1中可以看出 2种算法整体上比 Ga r l a n d算法具有更低的最大误差 在平均误 差上 除了脚骨模型外 Ga r l a n d算法具有最低的平均误差 最大误差值一般 出现在曲率高的区域 本文新 的二次误差测度能反映模型表面变化 因此在曲率较高的区域 本文算法会比 Ga r l a n d算法在简化后的模 型上保留更多的点 降低了最大误差 由于模型表面曲率高的区域往往 占整个表面 比例较小 而 G r l n d 算法在曲率低的区域分布的网格顶点相对较多 因此简化率相同情况下 Ga r l a n d算法具有较低的平均误 差 本文的第 2个误差测度比第 1 个误差测度能反映更大的区域变化 但第 1种更能体现尖锐 区域变化 因此第 1 种算法的最大误差小于第 2种 而第 2种算法的平均误差低于第 1 种 对于脚骨模型 由于有很 多不相连的部分 且各部分表面曲率较大 本文算法能反映表面变化 因此具有较低的误差值 表 1 简化后模型 的最大误差和平均误差 Ta b e l 1 M a x a nd me a n e r r o r s o f t h e s i reI p l i f i e d mo de l s 从图 2 4视觉效果上看 本文算法在大规模简化后仍然能保留原始模型相 当多的重要几何特征 比 如牛的角和耳朵 恐龙的背脊尖骨以及脚骨的末端指骨 同时模型整体形状保持得也较好 由于本文的第 1 种算法比第 2种对高曲率区域更为敏感 因此对细节特征保持得更好 而 Ga r l a n d算法在曲率较高或尖 锐区域特征丢失较多 从图中简化模型上的网格线能看出 本文箅法简化后的模型 曲率高或尖锐区域 网 格密度大 曲率低的区域网格稀疏 表面网格分布较 为合理 Ga r l a n d算法网格分布均匀 由于大部分重 要的几何特征集中在曲率较大的区域 比如尖角或凹陷等 Ga r l a n d 原始的二次误差测度只考虑了距离 因 素 不能根据局部表面的变化对边折叠的顺序进行强制约束 使得网格分布均匀 对高曲率区域特征保持 不好 本文三角形重要度是个 0 1 区间连续值 能对表面变化幅度较为细致地全面反映 因此边折叠过 维普资讯 第六图书馆 第六图书馆 第 7期 杜 晓晖等 基于加权二次误 差测度的边折 叠简化算 法 7 3 5 程受到充分的约束 简化模型表面网格分布较为合理 在对模型大规模简化后仍然能保持较多的重要几何 特征 同时模型的整体形状也能很好地保持 降低了视觉失真 iIf lI 膏 a 原始模型 b G a r l a n d c 算法1 图 2 牛模型简化结果 比较 Fi g 2 Compa r i s o n o f s i mp l i f i e d C O W mo de l s d 算法2 a 原始模 b G a r l a n d 算法 C 算法1 d 算法2 图 3 恐 龙模型 简化结果 比较 Fi g 3 Co mp a r i s on o f s i mp l i f i e d d r a g o n mo d e l s 一 4 结束语 a 1原始模 b Gar l and 算法 c 算法l d 箅法2 图 4 脚骨模 型简化结果 比较 Fig 4 Co mp a r i s o n o f s i mpl i f i e d b on e s mo d e l s 提出了三角形重要度的概念 并将其嵌入到 G a r l a n d原始二次误差测度中 在不改变二次误差测度矩 阵性质同时 使得二次误差测度不仅能度量距离误差 而且能全面反映表面变化程度 克服了 G a r l a n d算 法使网格分布过于均匀的弱点 合理分配了网格密度 使得模型大规模简化后 在保持较低的误差水平同 时 仍然能保持相当多的重要几何特征和较好的整体视觉效果 参考文献 1 S C HR OE D E R W J Z A R G E J A L O R E N S E N W E D e c i ma t i o n o f l fi a n g l e me s h e s C T h o ma s JJ P r o c e e d i n g s o f t h e 1 9t h Annu a l ACM Co nf e r e nc e o n Co mp ut e r Gr a ph i c s a n d I nt e r a c t i ve Te c hn i q u e s SI GGRAPH 9 2 Ne w Yo r k ACM Pr e s s 1 9 92 65 70 2 B E R N D H A d a t a r e d u c t i o n s c h e me f o r t r i a n g u l a t e d s u r f a c e s J C o mp u t e r A i d e d Ge o me t r i c D e s i g n 1 9 9 4 1 1 2 1 9 7 21 4 3 R OS S I GN A C J B OR R E I P Mu l t i R e sol u t i o n 3 D a p p r o x i ma t i o n for r e n d e r i n g c o mp l e x s c e n e s C F A I CI DI E N O B K U NI I T Geo met r i c M o d e l i ng i n Co mpu t e r Gr a p hi c s Me t ho d s a nd Ap pl i c a t ion s Be r l i n Spr i n g e r Ve r l a g 1 9 9 3 45 5 4 65 4 K A I V I N A D TA Y L OR R H S u r p e r f a c e s p o l y g o n a l me s h s i mp l if i c a t i o n w i t h b o u n d e d e r r o r t J I E E E C o mp u t e r Gr a p h ic s a n d Ap p l i c a t i o n s 1 9 9 6 1 6 3 6 4 7 7 5 T UR K G R e t i l i n g p o l y g o n a l s u r f a c e s C T HO MA S J J P r o c e e d i n g s o f t h e 1 9 t h A n n u a l A C M Co n f e r e n c e o n Comp u t e r Gr a phi c s a nd I n t e r a c t i ve Te c h ni q u e s SI GGRAPH 92 Ne w Yo r k ACM Pr e s s 1 9 92 5 5 6 4 维普资讯 第六图书馆 第六图书馆 7 3 6 北京工业大学学报 2 0 0 7焦 6 HO P P E H DE R O S E T D UC H A MP T e t a 1 Me s h o p t i m i z a t i o n C K A J I Y A J T P r o c e e d i n g s o f t h e 2 0 t h A n n u a l ACM Co n f e r e n c e o n C o mp u t e r Gr a p h i c s a n d I n t e r a c t i v e Te c h n i q u e s S I GGRAPH 9 2 Ne w Yo r k ACM P r e s s 1 9 9 3 1 9 2 6 7 8 G A RL A N D M H E C KB E R T P S S u rf a c e s i mp l i f i c a t i o n u s i n g q u a d r i c e r r o r me t ri c s C WHI T E T E D T P r oce e d i n g s o f t h e 2 4 t h An n u a l ACM C o n f e r e n c e o n Co mp u t e r Gr a p h i c s a n d I n t e r a c t i v e Te c h n i q u e s SI GGR AP H 9 7 Ne w Yo r k ACM Pr e s s 1 9 97 209 21 6 李现 民 李桂清 张 小玲 等 基于子分 规则 的边折叠简化方法 J 计算机辅助设 计与图形学学 报 2 0 0 2 1 4 1 8 1 3 L I X i a n mi n L I G u i q i n g Z H AN G X i a o l i n g e t a 1 E d g e c o l l a p s e s i m p l i f i c a t i o n b a s e d o n s u b d i v i s i o n J J o u r n a l o f C o m p u t e r A i d e d De s i g n a n d C o m p u t e r G r a p h i c s 2 0 0 2 1 4 1 8 1 3 i n C h i n e s e 9 KH O Y G A R L A N D M U s e r Gu i d e d s i m p l i f i c a t io n C ffS P E N C E R S P r o c e e d i n g s o f t h e A C M S y mp o s i u m o n I n t e r a c t i v e 3 D Gr a p h i c s Ne w Yo r k ACM Pr e s s 2 0 0 3 1 2 3 1 2 6 1 0 1 1 1 2 1 3 H AMA N N B A d a t a r e d u c t io n s c h e me f o r t ri a n g u l a t e d s u r f a c e J C o mp u t e r Ai d e d G e o m e t r i c D e s ig n 1 9 9 4 1 1 2 1 9 7 21 4 L O UN S B E R Y M D E R O S E T WAR R E N J Mu h i r e sol u t i o n a n a l y s is f o r s u r f a c e s o f a r b i t r a r y t o p o l o g i c a l t y p e J A C M Tr a n s a c t i o n o n Gr a p h i c s 1 9 9 7 1 6 1 3 4 7 3 T O D L A U R GR E E N M A me t h o d f o r p r o g r e ssi v e a n d s e l e c t i v e t r a n s mi ssi o n o f mu l t i r e s o l u t i o n mo d e b C S L A T E R M Pr o c e e d i n g s o f t h e ACM Vi r t u a l Re a l i t y a n d S o f t wa r e Te c h n o l o g y VRS T 9 9 L o n d o n ACM P r e ss 1 9 9 9 8 8 9 5 H O P P E H P r o g r e s s i v e me s h e s C R U S HME I E R H P r o c e e d i n g s o f t h e 2 3 r d A n n u a l A C M Con f e r e n c e o n Comp u t e r Gr a p h i c s a n d I n t e r a c t i v e Te c h n i q u e s SI GGR AP H 9 6 Ne w Yo r k AC M P r e ss 1 9 9 6 9 9 1 0 8 Ed g e Co l l a p s e S i mpl i f i c a t i o n Ba s e d o n W e i g ht e d Qu a d r i c E r r o r Me t r i c s DU Xi a o hu i YI N Ba o c a i KONG De h u i B e i j i n g Mu n i c i p a l K e y L a b o r a t o r y o f Mu l t i m e d i a a n d I n t e l l i g e n t Sof t w a r e T e c h n o l o g y C o l l e g e o f C o mp u t e r S c i e n c e B e i j i n g Un i v e r s i t y o f T e c h n o l o g y B e i j i n g 1 0 0 0 2 2 C h i n a Ab s t r a c t Af t e r d r a s t i c s i mp l i f i c a t i o n p r oc e s s mo s t o f t h e e x i s t i n g s i mp l i f i c a t i o n a l