（计算机应用技术专业论文）基于视觉感知的模型简化算法研究与实现.pdf

大连理工大学硕士学位论文 摘要 随着三维模型数据越来越庞大和复杂，使得图形绘制系统和网络传输的压力越来越 大。为了能更好的显示和传输模型数据，需要对模型进行简化，删除对模型显示贡献不 大或者对模型所描述的对象影响较小的图形元素，以此来达到加速绘制和降低网络负载 韵目的。传统的模型简化算法所考虑的简化依据主要是几何特征( 曲率、边长等) ，通过 计算图形元素几何特征值来确定图形元素的重要性进而确定简化的顺序。 本文首先根据g a r l a n d 原始的二次误差简化算法提出了一个基于边收缩的快速的网 格简化算法，该算法属于利用几何特征进行模型简化的算法，但它提高了模型简化的效 率，适于实时应用。从人类视觉的生理角度考虑，即使几何特性相同的模型区域，由于 光照、纹理、颜色等特征的不同，它们所产生的视觉刺激也是有所差别的。本课题在传 统算法的基础上，引入了视觉感知因素，提出了一种基于视觉感知的模型简化算法，并 且结合视觉感知因素和显示质量度量模型提出了一种细节层次控制方法。首先对一些虚 拟场景中基本的视觉感知因素进行了较为详细的分析，包括线框分辨率、纹理、距离、 光照、颜色和亮度，通过对这些视觉因素的分析，得到了如何从模型中提取和度量这些 信息的方法。然后把它们作为标量场信息引入到了g a r l a n d 的任意维度的二次误差模型 简化度量公式中，得到了新的基于视觉感知因素的误差度量公式。为了能够根据人类视 觉感知特性来确定模型简化过程的结束条件，本文根据视觉感知因素得到一个细节层次 控制参数，通过把这个参数与显示质量度量模型的结合得到了基于视觉感知的细节层次 控制的方法。通过新的模型简化算法和细节层次控制方法，使模型的简化结果更符合人 类的视觉特征，达到更好的视觉效果。 本文利用公用的三维网格模型进行了有关实验，通过比较传统简化算法和基于视觉 感知的简化算法的简化结果，发现引入视觉感知因素后，在模型的视觉特征区域可以保 留较高的细节信息，在其他区域则可以简化掉更多冗余的图形元素。并且通过基于视觉 的细节层次控制方法来约束模型简化过程，可以使得细节层次的选择更加符合人类的视 觉习惯和适应虚拟场景的状态要求。最后本文通过一个虚拟场景构建工具说明了如何把 基于视觉感知的模型简化算法应用到实际的虚拟场景中。 关键词：显示质量；细节层次；视觉感知；误差度量 大连理工大学硕士学位论文 r e s e a r c ha n dr e a l i z a t i o no f m o d e ls i m p l i f i c a t i o nb a s eo nv i s u a l p e r c e p t i o n a b s t r a c t t h ep r e s s u r eo fr e n d e r i n gs y s t e m sa n dt r a n s m i s s i o nb yn e t w o r ki sh i d e ra n dh i g h e r b e c a u s eo ft h em o r ea n dm o r ec o m p l e xm o d e ld a t a ，t h em o d e l sn e e dt ob es i m p l i f i e df o r b e t t e rd i s p l a ya n dt r a n s m i s s i o n m o d e ls i m p l i f i c a t i o nd e l e t e sg r a p h i c se l e m e n t sw h o s ee f f e c t f o rm o d e ld i s p l a yo rt h eo b j e c tc h a r a c t e r i z e db ym o d e li se x i g u o l i sa sm u c ha sp o s s i b l e8 0a s t oa c c e l e r a t et h er e n d e r i n gp r o c e s sa n dd e p r e s st h en e t w o r kl o a d g e o m e 雠cc h a r a c t e r so f m e s h e sa r em a i r d ys u r v e y e di nt r a d i t i o n a la l g o r i t h m s ，n es e q u e n c eo fs i m p l i f i e de l e m e n t si s d e t e r m i n e db yc a l c u l a t i n gt h ee i g e n v a l u eo f t h e m af a s tm e s hs i m p l i f i c a t i o na l g o r i t h mb a s e do ne d g e c o l l a p s ei sp r e s e n t e di nt h i sp a p e r a l t h o u g hi tj u s ta d o p t so n l yg e o m e t r i cc h a r a c t e r st os i m p l ym o d e l s i ta c c e l e r a t e s 血e s i m p l i f i c a t i o ne 衔c i e n c ya n di sf i to fr e a l t i m ea p p l i c a t i o n s a tt h ep o i n to fh u m a nv i s i o n p h y s i o l o g y ，s o m em o d e lr e g i 。o n sw i t ht h es a m eg e o m e t r i cc h a r a c t e r sm a y b eh a v ed i f f e r e n t v i s i o ns t i m u l a t i o n t h i ss u b j e c ti m p o r t sv i s u a lp e r c e p t i o nf a c t o r si n t ot r a d i t i o n a la l g o r i t h m s a n dp r e s e n t sas i m p l i f i c a t i o na l g o r i t h mb a s e do nv i s u a lp e r c e p t i o na n dc o m b i n e st h ev i s u a l p e r c e p t i o nf a c t o r sa n dt h ed i s p l a yq u a l i t ym e t r i c s 幻f o r mas t r a t e g yo fc o n t r o l l i n gt h el o d 。 f i r s t l y ，s o m eb a s i cv i l t u a lp e r c e p t i o nf a c t o r s i nv i r t u a ls c e n ea r e a n a l y z e d ，i n c l u d i n g w i r e f r a m er e s o l u t i o n , t e x t u r e ，d i s t a n c e ，i l h u n i n a t i o n ，c o l o ra n d1 u m i n a l e e b yt h e s ea n a l y s e s ， t h ew a yo fd i s t i l l i n ga n dm e a s u r i n gt h e s ef a c t o r si sf o u n do u t s e c o n d l y ，t h e s ep e r c e p t i o n f a c t o r sa r ei r e p o r t e di n t og a r l a n d sq u a d r i cm e t r i c ss i m p l i f i c a t i o ni na n yd i m e n s i o n s 勰s c a l a r i n f o r m a t i o n t h e nan e we r r o rm e t r i c si sf o u n d e d i no r d e rt od e t e r m i n et h ee n dc o n d i t i o no f t h es i m p l i f i c a t i o np r o c e d u r e ap a r a m e t e rt oc o n t r o ll o db a s e do nv i s u a lp e r c e p t i o ni s c o m p m e do u ti nt h i sp a p e r b yt h i sp a r a m e t e ra n dd i s p l a yq u a l i v ym e t r i c s ，t h es t r a t e g yt o c o n t r o ll o db a s e do nv i s u a lp e r c e p t i o ni sp r e s e n t e d t h es i m p l i f i c a t i o na l g o r i t h ma n dl o d c o n t r o ls t r a t e g yc a nr o a k et h es i m p l i f i e dm e s h e sa d a p t e dt oh u m a nv i s u a lp e r c e p t i o n s o m ep u b l i c3 - dm o d e l sa r ea d o p t e di nt h ee x p e r i m e n t s b ya n a l y z i n gt h ee x p e r i m e n t r e s u l t s ，i tc a l lb ef o u n dt h a tm o r ed e t a i l sa r ek e p ti nt h ev i s u a lp e r c e p t u a la r e a s ，w h i l em o r e r e d u n d a n c yd a t aa r ed e l e t e di no t h e ra r e a s t h ec h o i c eo fl o d i ss u i t a b l ef o rh u m a nv i s i o n a n dt h ed e m a n do fv i r t u a ls c e n es t a t e a t1 a s t , ac o n s t r u c t o ro fv i r t u a ls c e n ei si n t r o d u c e dt o e x p l a i nh o w t oa d o p tt h en e w s i m p l i f i c a t i o na l g o r i t h mi nt h ea c t u a lv i r t u a ls c e n e k e yw o r d s ：d i s p l a yq u a l i t y tl o d ：v i s u a lp e r c e p t i o n ：e r r o rm e t r i c s 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 储躲弘喻冽u ；垒 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名：壶毒 赳年月亚日 大连理工大学硕士学位论文 引言 在虚拟现实、科学计算可视化、动画游戏等各个方面，三维模型因其具有更加丰富、 全面和生动的细节信息，正在逐渐取代传统的基于二维图像的表现方式，而快速发展的 计算机辅助设计( c a d ) 技术也已经使三维建模在实际生产中得到广泛应用。随着数据采 集设备和建模技术的不断发展，获得真实物体的三维模型变得越来越容易，三维网格模 型的精度和规模都在快速提高。与此同时，随着计算机硬件成本的不断降低和网络的不 断普及，越来越多的用户要求能够在p c 机上对这些三维模型进行测览、编辑，甚至在 网络上自由地进行传输。于是数据量的快速增长与计算机有限的计算能力和带宽限制就 形成了尖锐的矛盾。解决这些问题的一个途径就是对复杂的三维模型进行简化。事实上， 目前通过激光扫描、等值面提取等方法取得的三维模型有很多是过采样的，其精度可能 已经远远超过了用户的需求。去除这些冗余的数据，就能够有效地减轻系统绘制、传输 的压力。 传统的模型简化算法所考虑的网格特征主要是几何特征( 曲率、距离等) ，通过计算 图形元素几何特征值来确定图形元素的重要性进而确定简化的顺序。从人类视觉的生理 角度考虑，即使几何特性相同的模型区域，由于光照、纹理、颜色等特征的不同，它们 所产生的视觉刺激也是有所差别的。本课题所探讨的就是在传统算法的基础上，引入了 视觉感知特性，使模型的简化结果更符合人类的视觉特征，达到更好的视觉效果。 目前已经有一些工作开始关注把视觉感知因素引入模型简化的必要性以及如何将 这些因素引入简化过程中。这些工作对网格模型简化的误差度量依据做出了重要的扩 展，不再仅仅局限于空间距离或者是曲率等几何特性的约束，而是将网格特征、标量场 信息和显示质量等新的概念和特性加以考察，分析它们对于网格模型简化的重要程度。 并且通过实验等方式给出了一些重要结论。 视觉感知因素的种类有很多，其中还有一些涉及心理感应的因素，在本文中只对一 些简单直观的视觉感知因素进行了考察和分析，它们是线框分辨率、纹理、距离、光照、 颜色和亮度。这些因素有的作为简化过程中误差度量公式的一部分加以运用，有的则帮 助选择合适的细节层次和生成模型简化的终止条件。 本文在前人工作的基础上提出了基于视觉感知因素的简化算法，并且给出了实验结 果，通过对实验结果的分析来考察基于视觉感知因素的模型简化所具有的优势。此外， 本文还通过结合显示质量度量公式得到了控制细节层次的方式，使得细节层次的选择更 加符合视觉感知特性，并且将这种简化方法应用到了一个虚拟场景构建工具中，说明了 在实际应用中如何对模型进行组织和处理。 基于视觉感知的模型简化算法研究与实现 1 三维网格模型 将三维模型以相互连接的多边形表示出来，这样的模型就是网格模型，在传统的计 算机图形系统中，三角形面片是最通用的绘图元语。一方面因为三角形的拓扑关系简单， 另一方面几乎所有的图形硬件系统都能很好的支持三角形网格的处理。又由于其它的多 边形网格可以很方便的通过剖分转化为三角形网格，所以三角形网格是最通用的网格表 示形式。 用多边形表示三维物体是三维图形学中的一个经典表示形式，在这种形式中，物体 由网格状的多边形面来近似表示物体中所包含的曲面。在创建某些模型的时候，我们需 要顶点计数来记录构成多边形的顶点，或者可以规定所有的多边形均为三角形。多边形 表示法在计算机图形系统中被广泛应用，这主要有两个原因： ( 1 ) 创建多边形物体比较容易( 尽管对于复杂的物体这种处理费时而且代价大) ，同 时存在高效的可视化算法( 集成在硬件中) 为用这种方式表示的物体产生阴影。 ( 2 ) 多边形网格是一种严格的机器表示法，它可以用来表示其它方法不能直接渲染 的物体。 因此双三次曲面片和体元表示的曲面在渲染之前一般需要先转化成多边形网格。 在简单情况下，多边形网格的最终信息由一系列顶点表示，作为物体表示的一部分 也需要存储其它的几何信息用于后续处理，这就是经常提到的多边形法向量与顶点法向 量。这些值仅计算一次，并且存储在目标数据结构中，当物体进行线形变换时，它们也 随之进行线形变换。 1 1 三维网格模型的用途 网格模型因为在数学性质上的简洁特性，在计算机图形领域得到了广泛应用，由于 大部分硬件对于三角形图元良好的支持，使得三角形网格的应用范围最为广泛。在虚拟 现实环境、三维游戏、地形模拟、科学计算可视化、计算机艺术等很多领域都有大量应 用。 ( 1 ) 网格模型特别是三角网格具有数学上的规整性，容易表示和存储，便于修改网 格形状，所以在很多专业的三维模型工具软件中都是以多边形网格作为模型的基本表示 形式，比如3 d s m a x 、p o s e r 、m a y a 。 ( 2 ) 在虚拟现实领域，真实感是最重要的目标，要让观察者产生身临其境的感觉。 此外灵活的人机交互也是非常重要的，虽然基于图像的虚拟现实技术具有简单快捷的优 点，但是在交互的灵活性上却有很大的弊端，而且用户很难对虚拟场景进行修改，利用 大连理工大学硕士学位论文 图形技术将网格模型作为基本的场景内容可以避免这些问题。此外利用纹理映射结合三 维建模技术也可以提供真实度非常高的场景。 ( 3 ) 由于三维显示的巨大优越性，它在游戏娱乐和影视特效方面也有强大的生命力， 随着技术的进步，三维游戏渐渐成为主流，比如有名的 c o u n t e rs t r i k e ) ) 。在近几年的 好莱坞大片中，三维模型技术得到了广泛应用，比如侏罗纪公园和魔戒等等。 ( 4 ) 在地形模拟、科学计算可视化等方面，三维网格模型也有广泛应用，因为在网 格模型上很容易附带其他标量信息，并且可以建立空间位置与标量场信息之间的对应关 系，便于直接在模型上显示和分析科学信息，比如大规模地理环境的模拟，企业信息的 模拟都是将标量信息用三维技术进行模拟。 1 2 三维网格模型的获取 获得现实物体的网格模型最常用的方法包括： ( 1 ) 使用手动的三维绘图仪，操作者需要根据自己的经验以确定某个具体顶点的位 置，这些点就是多边形的顶点，其三维坐标经由三维数字仪记录在系统中。 ( 2 ) 另一种快捷的方式是利用激光扫描仪，激光扫描仪是一种能够根据实际物体产 生准确的高清晰度的多边形对象的设备。通过测量到物体表面的距离，激光测量仪将返 回一个轮廓线集合，即物体与平行平面相交所形成的封闭曲线集合，然后利用“皮肤” 算法对成对的轮廓线进行操作，将边界数据转化成大量的三角片，这个过程会产生大量 的冗余数据，并且激光扫描仪只适合测量凸面体。 ( 3 ) 除了上述方法外还有利用数学方法生成多边形数据或者利用构造性实体几何法 生成多边形数据。 尽管在计算机图形学的建模过程中，多边形网格是最常见的表示形式，它的实现过 程非常简单，但是却相当的枯燥和乏味。使用探测仪器获取三维模型的过程包括数据采 集、数据配准、网格生成以及后期的去除噪音等操作过程，对于带有颜色、纹理信息的 模型，还需要一个纹理映射的过程。 用多边形网格法处理实际问题时也会遇到一些困难。其中最重要的是精度问题，模 型的精度一或者说多边形与物体的曲面之间的差异是任意的。对最终画面质量而言，在 理想状况下，单个多边形的大小取决于局部空间曲率。当曲率变化迅速时，每一个曲面 单元都需要用更多的多边形来表示。 在三维图形学领域内，一个最重要的进步是在2 0 世纪7 0 年代明暗处理算法的出现， 这种算法能够有效地处理多边形物体，同时通过插值的方法减少在表示中分片线性的视 基于视觉感知的模型简化算法研究与实现 觉效果。这种算法以及渲染硬件的飞速发展，使得多边形网格结构日趋完美。图1 1 是 一个网格模型典型的表示结构【”。 嚣一表面一多边形一边顶点 1 ) 概念层次表示 2 ) 拓扑袭示 3 ) 一个实际的数据结构 图1 1 用多边形表示一个物体 f i g 1 1r e p r e s e n t 觚o b j e c tb yp o l y g o n s r 4 - 大连理工大学硕士学位论文 2 网格模型简化 网格简化也称为数据缩小或者数据删减，它是在试图保持图形外观不变的情况下尽 可能的减少详细模型的多边形数量。对于实时应用来说，通常需要这个过程来减少存储 的顶点数量并将这些顶点发送到图形管线，而且可以使程序具有一定的伸缩性。这样对 于图形处理能力较弱的机器来说，可以显示较少的多边形。此外，模型数据往往有过多 的细节，这些对模型显示贡献不大的细节理应被删除掉。 事实上，目前通过激光扫描、等值面提取等方法取得的三维模型有很多是过采样的， 其精度可能已经远远超过了用户的需求。去除这些冗余的数据，就能够有效地减轻系统 绘制和传输的压力。 目前已经有许多针对模型几何特征的简化算法，其中具代表性的有：自适应细分型 算法、采样型算法、几何元素删除型算法、近平面结合型算法和边收缩型算法1 2 - 6 1 。 2 1 经典方法 ( i ) 自适应细分型算法 d e h a e m e r 提出的自适应细分算法【。刀，该算法利用输入数据的规整性，根据用户指 定的误差容限通过多次细分，来自动生成一个简化模型，该算法保持了模型的拓扑结构， 但只适用于正规网格，而且计算初始供细分的简化模型比较困难。 ( 2 1 采样型算法 r o s s i g n a c 提出的多分辨率近似算法是一种采样型算法【8 】，该算法适用于任意类型的 输入模型，快速有效。缺点是不能保持原模型的拓扑结构因而视觉效果不佳，近似误差 也不可控。 ( 3 ) 几何元素删除型算法 s c h r o e d e r 的三角形网格简化算法属于这类算法1 9 1 ，该算法计算量小，时间复杂度为 线性，很好的保持了模型细节，保持模型的拓扑结构，但是这个算法多次迭代后误差会 积累下去，并且它只适用于流形物体。为了有效约束近似误差，c o h e n 提出了基于包络 网格的简化算法1 1 0 1 ，该算法通过内外层包络网格来控制简化过程，该算法保持了拓于 结 构，有效地约束误差，但是该算法仅适用于流形物体，包络网格也难于构造。 “) 近平面结合型算法 这类算法的一个典型是k a l v i n 提出的基于区域生长的贪婪简化算法【1 ”。该算法适 用于用任意多边形面片表示的复杂模型，简化速度快，简化模型的顶点是原始模型顶点 集的子集。 基于视觉感知的模型简化算法研究与实现 ( 5 ) 边收缩型算法 边收缩型算法有很多，使用边收缩操作容易构成连续过渡的多个l o d 模型，便于 多分辨率模型管理。h o p p e 在1 9 9 3 年提出一种边收缩算法，但是计算复杂度高，难以 实现实时性的要求。后来他在1 9 9 6 年提出了递进网格f 埘，可以支持多分辨率表示，能 够抽取多个连续的细节层次，后来又在1 9 9 7 年提出基于视点的渐进网格【1 3 1 。g a r l a n d 提出了二次误差简化算法可以产生高质量的简化结果，可以控制顶点对来决定是否保持 拓扑结构n 4 1 ，并且在2 0 0 2 年进步作了改进【”】。另一个基于边收缩的算法是x i a 提出 的动态的与视点相关的简化算法【】6 1 ，a n t 6 n i ow v i e i r a 等人提出的快速星型算法【。 随着模型数据的急剧扩充，有大量的工作集中在大规模网格模型简化和基于视点的 l o d 控制上【1 8 0 1 ，在国内，北京大学三维视觉计算与机器人实验室在大规模网格模型 简化与l o d 控制、海量数据的模型压缩等方面作了大量有益的工作。此外浙江大学计 算机辅助设计与图形学国家重点实验室、中国科学院计算机技术研究所也作了很多有益 的工作。 近年来，有人开始研究视觉感知因素对模型显示所产生的影响，这些工作主要是在 大量实验基础上，分析不同的模型特征对于视觉感知所产生的刺激的不同等级，以及它 们对于三维模型真实度和简化效果的影响，希望可以找到对模型简化和显示的新的质量 度量公式，并将新的质量度量公式应用到传统的模型简化算法和系统中，提高简化结果 的精度。 2 2 二次误差简化方法 g a r l a n d 提出的二次误差简化方法( q e m ) 是一个典型的边收缩型算法【14 1 ，q e m 算法 首先为每一个顶点v ( 坐标向量为p = i 匕v ，心1l 。) 计算一个4 x 4 的对称矩阵q ，称其为 误差矩阵，顶点v 的误差定义为a ( v ) = v q l ，。假设边( h ，v 2 ) 收缩成顶点b ，那么鸭的误 差矩阵就可以定义为幺= q 1 + q 2 。为了完成边的收缩，必须计算出新顶点v 3 的位置， 一种简单的策略是在v 。，v ：和( 叶+ p ：) 2 中选择一个可以使得a ( v 3 ) 最小的值为了得到 更好的效果，可以计算出使得( v 3 ) 取最小值的的位置坐标，这就要通过解方程： 一a a ：旦垒：丝：0 ， ( 2 1 ) 8 x 8 y a z 来求得该坐标，上述方程可以变换为： 一6 一 盔塑三查兰堡主些笙壅 一 q l lq n q 2 19 2 2 q 3 1q 3 z 00 q 1 3q 如q 2 4 q 3 3 ol 假设方程中的矩阵是可逆的，又得到： v a 。 9 1 1q 1 2 吼， 级l 拿芷如 q 3 1 q 3 2 q 3 3 0 0 0 嵋= ( 2 | 3 ) 如果矩阵不可逆，q e m 算法会试图沿着边( v l ，v 2 ) 找到一个最优化的顶点，如果这样 仍旧失败，那么就要在h ，1 2 和( 叶+ v 2 ) 2 中寻找一个合适的位置。为了得到误差矩阵 q ，设p 表示一个平面，它的法向量为p = k bc d 】7 ，那么平面方程是甜+ 砂+ c z 2 d ， 而且，+ 矿+ ，= 1 。因此有： ( v ) = ( 【仉仉1 t ) = ( p t v ) 2 ， ( 2 _ 4 ) p e m 即1 其中1 a e s ( v ) 表示所有以v 为顶点的三角形集合，上式变形为： r、 ( v ) = ( v o ) ( p t v ) p e p l a n e 。( v ) 2 p e 毛。，( 矿) 归，l ，毛，k 2 5 ) p 妇叫jp e 鲫时9 ， 其中k 。= 刀= 西 a b 6 2 a cb c a db d 钟础 b cb d c 2c d c a a 1 ，得到q = k p p e 加州r ) q e m 算法的执行过程是： ( 1 ) 对所有的顶点计算q ，求出( v ) ； ( 2 ) 选择合适的顶点对； ( 3 ) 为每一个顶点对计算最佳的收缩目标顶点； ( 4 ) 将所有的顶点对按照收缩代价由小到大的顺序放到个堆中； ( 5 ) 从堆顶迭代地取出顶点对并完成收缩操作，同时更新相关顶点对的收缩代价并 且更新堆； 基于视觉感知的模型简化算法研究与实现 ( 6 ) 如果满足结束条件，结束：否则，转到( 5 ) 。 后来很多算法的误差度量都是采用了g a r l a n d 的二次误差简化算法中的度量方式， 但是在一些数据结构上做出过改变。 2 3 快速网格简化算法 本文提出的快速网格简化算法( f m s ) 在执行过程上与q e m 算法类似，但是在收缩 代价的定义和计算上有很大差别。为了提高计算速度，f m s 算法舍弃了顶点的对称矩阵 q ，并且用一个称为顶点权值的数值来表示一个顶点的重要性，权值越大的顶点就越重 要，对应于q e m 中的收缩代价就越大。同时f m s 中用来控制收缩顺序的堆存储的元素 是顶点的权值，这样相对于q e m 以顶点对为存储对象，其中的元素减少了约2 3 。 2 3 1 顶点权值 为了能在一个迭代的简化过程中选择合适的边来进行收缩，需要知道每条边的收缩 代价，在基于二次误差度量的算法中，为了计算收缩代价，首先要得到每个顶点的误差， 为此每一个顶点都要先计算一个误差矩阵，然后再计算顶点误差，最后计算边的收缩代 价。 为了能在误差计算中降低计算量，本文的快速简化算法( f m s ) 舍弃了顶点的误差和 误差矩阵，而采用了顶点权值来描述一个顶点的重要程度，对于顶点权值，仅考虑了曲 率和边长因素。如果一个顶点的曲率越大说明该顶点的位置越能表现模型的形体特征， 如果一个顶点所邻接的边的长度越长说明该顶点在模型表面上影响的区域越广。所以在 综合考虑了曲率和边长后，顶点权值可以较好的反映模型上一个顶点的重要程度。 为了得到顶点的曲率，首先要计算顶点的法线向量甩，在由三角形数据构成的曲面 上计算某点的法向量最简单的方法是计算每个三角形的法线向量，然后将相邻三角形的 法线进行平均，对于相邻三角形的共同顶点使用平均法线。要计算三角形的法向量，可 以取三个顶点v l ，k 和b ，然后按式2 6 计算向量积： f x , - x 2 x 2 - - 毛 一= 1 只一咒l l 乃一只i ( 2 6 ) l 互一乞jl 乞一毛j 以。可以利用式2 7 计算： q = n f ， f e v j h 一8 一 ( 2 7 ) 大连理工大学硕士学位论文 其中v f a c e s 删v 的所有邻接三角形集合，三角形面，的单位法向量= 忍删一一 般情况下也会将以，归一化。 得到顶点的法向量后，可以通过式2 8 计算顶点曲率： 么( n f ) 西：丛兰丝! l 一一 i v f a c e s i ( 2 8 ) 其中么( 以，勺) 表示向量与_ 的夹角，i 啦j l 表示顶点v 的邻接三角形个数，称c v 为顶点的相对曲率值，顶点相对曲率值能代表顶点的几何位置的重要性：相对曲率值越 大，顶点的位置就越重要。 边( v ，的收缩代价e ( v ，“) 可以利用式2 9 计算 e ( v ，甜) = 巴 ，+ 三( c v + c ”) ， 其中巴是边( v ，“) 的边长的平方。 一个顶点的权值计算如下式： ( 2 9 ) 西= m i ne ( v ，f ) + 以， ( 2 1 0 ) ，er - 口 其中v v e r t i c e s 是顶点v 的邻接顶点集合，丑是收缩后顶点v 的权值与其初始权值之差的 绝对值，口是一个可调参数，在第一次收缩前五= 0 ，引入五的目的是防止在某一区域内 过度的简化。瓦表示一个顶点的几何位置的重要性，这种定义形式可以将边收缩所影响 的区域控制在收缩形成的新顶点的邻接三角形区域内。 在选择要收缩的边时，本文算法先从优先权队列中取出堆顶的权值所对应的顶点， 然后在其邻接顶点集合内找到满足式2 1 0 的边进行收缩操作。 2 ，3 2 优先权队列 优先权队列用来控制边收缩的顺序，在传统的边收缩算法中所使用的优先权队列存 放的元素是边、三角形或者是满足一定收缩条件的顶点对，如果优先权队列中的元素越 少，那么对队列的维护所花费的时间和空间代价就越小，所以在优先权队列中最好存放 网格模型中数量最少的图形元素。网格模型的图形元素包括顶点、边和三角形，根据欧 拉定理可以证明，一个具有m 个顶点的三角形网格，约有2 m 个三角形和3 m 条边，所 以本文算法采用了顶点的优先权队列。为了避免在更新队列时改变顶点在顶点序列中的 基于视觉感知的模型简化算法研究与实现 索引，优先权队列中并没有直接存放顶点而是存放了顶点的权值。执行简化操作时从队 列中取出最小的权值，然后找到它所对应的顶点，进而选择合适的边进行简化。 为了每次都能从队列中容易的取出最小权值需要对队列排序，和q e m 算法一样本 文也是采用了堆排序的方法，在第一次简化之前要将所有的权值都进行排序，时间复杂 度为o ( n l o g n ) ，每次在边收缩后调整堆的时间复杂度是o ( 1 0 9 n ) 。 2 3 3 边收缩 假设要收缩的边是( v l ，v 2 ) ，这条边收缩后将形成新的顶点v 3 ，理论上v 3 的位置应该 使得它的权值最小，但是这样无疑将增加计算的复杂性，一个折衷的方案是如果v l 和 中有边界顶点，那么新顶点的位置取边界顶点的位置，否则就取v 1 和v 2 中点的位置，边 界顶点在网格预处理的过程中已经做好标记，这个选择新顶点位置的策略是影响简化精 度的，但是可以大幅度的提高效率。 产生新顶点v 3 后，首先删除v 1 和鸭的公共三角形并将其余的三角形都作为v 3 的邻接 三角形，然后要计算新顶点u 的权值，还要重新计算屹的所有邻接顶点的权值。 2 3 4 算法执行过程 f m s 算法的执行过程与q e m 算法基本上是一致的，执行步骤如下： ( 1 ) 计算所有顶点的权值毛； ( 2 ) 将优先权队列中的顶点权值由小到大堆排序； ( 3 ) 找到堆顶的权值所对应的顶点并在该顶点的邻域内找到满足式2 1 0 的边； f 4 ) 进行边收缩操作； ( 5 ) 重新计算收缩形成的新顶点以及它邻域内所有顶点的权值，并对优先权队列进 行调整； ( 6 ) 如果满足了简化的约束条件则停止，否则转到( 3 ) 继续。 2 3 5 实验结果 通过实验对q e m 算法和本文提出的f m s 算法进行比较，实验的硬件环境是，处理 器：c e l e r o n ( r ) c p u2 0 0 g h z ，内存：5 1 2 m b 内存，显卡：n v i d i ag e f o r c e 2 。软件环 境是，操作系统：w i n d o w sx p ，图形a ho p e n g l 。实验所采用的模型来自于g a r l a n d 的个人网站，如图2 1 所示。表2 1 是三个模型的图形元素的数量信息，包括顶点数、 边数和三角形数。 大连理工大学硕士学位论文 图2 1 三个网格模型的线框表示 f i g 2 1w i r ef l a m eo f t h r e em e s hm o d e l s 表2 1 图2 1 中各模型的图元数量 t a b 2 1t h eq u a n t i t yo f g r a p h i c se l e m e n t sa b o u tt h em o d e l si nf i g 2 1 通过对比表2 1 中各模型的图形元素数量，可以看出这些模型符合前文中提到的根 据欧拉定理所得到的关于各图形元素数量关系的结论，也可以将它们看作对这个结论的 印证。本文在程序实现中参考了h o r s tb i r t h e l m e r 等人提出的网格表示形式，这种表示 形式有利于对网格的简化操作【2 ”，针对f m s 算法又增加了顶点权值的结构。 首先比较一下f m s 与q e m 在简化精度上的差别，图2 2 和图2 3 表示了分别对 b u n n y 、b o n e s 和c o w 模型采用两个算法进行简化的情况，简化后b u n n y 模型有9 5 8 9 个 三角形，b o n e s 模型有2 2 0 4 个三角形，c o w 模型有2 8 0 4 个三角形。两个算法在精度上 的差别很小。q e m 算法简化后的模型比f m s 简化后的模型三角形的分布更加均匀。 图2 2q e m 简化结果的线框表示 f i g 2 2w i r ef l a m eo f s i m p l i f i c a t i o nw i t hq e m 基于视觉感知的模型简化算法研究与实现 攀霄 图2 3f m s 简化结果的线框表示 f i g 2 3w i r ef i a n l eo f s i m p l i f i c a t i o nw i t l lf m s 通过图2 2 和图2 3 来比较q e m 算法和f m s 算法在简化精度上的差别，可以看出 在模型的整体形态上差别并不大，如果仅从模型显示的角度来看，这种差别可以忽略。 下面比较两个算法在简化效率上的差别。f m s 算法在损失一定精度的情况下，在简 化效率上有了较大改进，图2 4 是对两个算法在时间上的比较，简化的模型是前面实验 中采用的b u n n y 模型。 5 0 1 0 0 0 0 1 5 0 0 02 0 0 0 0 2 5 0 0 03 0 0 0 0 被删除的顶点数 叵量叵珂 图2 4q e m 与f m s 的效率比较 f i g 2 4c o m p a r et h ee f f i c i e n c yo f q e mw i t ht h a to f f m s 通过图2 4 可以看到f m s 在时间效率上比q e m 表现要好，并且随着简化的顶点越 多，效率提高越明显，这样在刑侦现场重现或者虚拟会议等实时系统中就可以迅速地得 到简化后的模型，提高模型绘制的速度。 2 4 任意维度的二次误差模型简化 这个算法是由g a r l a n d 在2 0 0 5 年提出的，是对由他提出的原始的二次误差简化算法 的重大扩展【2 2 1 。在这一部分首先要明确几个拓扑学上的概念：流形、单形与复形。 ( 1 ) 流形( m a n i f o l d ) ，一般可以认为是局部具有欧氏空间性质的空间。而实际上欧 氏空间就是流形最简单的实例。像地球表面这样的球面是一个稍为复杂的例子。一般的 大连理工大学硕士学位论文 流形可以通过把许多平直的面片折弯并粘连而成。 ( 2 ) 单形( s i l n p l e x ) ，欧氏空间中处于一般位置的刀+ 1 个点 风，a ，扔，b 0 o ) 的 凸包称为一个n 一单纯形，称只为它的顶点，i = o ，1 ，2 ，聆。凸包记为( p o ，p l 9 oo9 以) 或( p ) 。 整数，z 是( 尸) 的维数。如果t p ，那么凸壳r 是包含在( p ) 中的单纯形，称为( p ) 的面， p 与r 的关系可表示为：( t ) ( p ) 。如果两个不相交或者相交部分是它们的公共面，称 为单形规则相处。 ( 3 ) 复形( c o m p l e x ) ，复形由单形构成，包括单纯复形和非单纯复形，单纯复形c 是 满足下列条件的单形的优先集合： c 中的任何两个单形规则相处； 如果单形k c ，m 是置的面，那么m c 。 单纯复形的维数是构成它的单形维数的最大值。不满足单纯复形条件的复形称为非 单纯复形。， 在三维欧几里德空间中的单形如图2 5 所示，复形如图2 6 所示。 因 0 一单形卜单形2 一单形3 一单形 图2 5 三维欧几里的空间的单形 f i g 2 5s 劬p i e m si ne u c l i d e a ns p a c e so f 3 一d 非单纯复形 单纯复形 图2 6 复形示例 f i g 2 6e x a m p l 铭o f c o m p l e x 金 基于视觉感知的模型简化算法研究与实现 g a r l a n d 后来对由他提出的二次误差模型简化算法进行了扩展，使得该方法可以应 用在任意维度的包含于欧几里德空间的单纯复形上。为了方便将误差度量公式推广到任 意维度的模型，首先g a r l a n d 改变了简化误差的定义形式。假设在空间f 中包含有一个 d 维流形m ，对于m 表面上的任意顶点烈坐标向量为p ) 可以构造组标准正交基 e if ：，岛，e n ) ，其中 e 1 吃，岛， 沿着p 点的切空间延伸，i 而 e a + ，e a + ：，e n 必然与 切空间正交。对坐标向量为x 的任意顶点z 矿，通过广义的毕达哥拉斯定理可以写出 从x 到p 的平方距离： 其中j 是单位矩阵，并且p ，p 。7 = ，设4 = j 一q p j ，6 = 叫p ，c = p 7 4 p 。公式2 1 1 告诉我们：误差度量只与m 的维度有关，而与肘所在空间的维度无关。并且对不同维 度的m 来说，只有4 是不同的，而b ，c 的形式不变。 2 4 1 单形的二次度量 在给出了在一个顶点处的表面的切空间的更一般化的二次度量定义后，g a r l a n d 又 给出了一般单体的二次度量形式，给定任意的非退化的拥有角1 1 0 ，u i ，u ：，u d 的d 维单形 盯，“，的坐标向量为，它定义了唯一的d 维切平面。取任意一个存在于该单体的顶点p 可以得到gx ) ，这个单体的二次度量形式定义为： q ) 二l ，q ( 工) ( 2 1 2 ) 因为属于盯的顶点都有相同的切平面，这就意味着可以将单体的二次度量形式简单 的定义为： q = q ， ( 2 1 3 ) 其中是单体盯的超体积，p 点是属于单体盯的任意点，为了简便通常取1 7 的质心， p 的坐标向量为p ，p = - 者，q 。 “r 1 正交切向量是通过对向量( q 一) 进行施密特正交化获得，图2 7 表示了最常见的 dg 力卜 力 吖卜喉弘 p 一 卜 g 大连理工大学硕士学位论文 三种单体的正交切向量的计算。 _ _ _ _ _ _ 1 - 。 _ ot l0 l熔u 邀6 e i 图2 7 三种常见单体的标准正交切线向量结构 f i g 2 7t h es t a n d a r do r t h o n o r m a lt a n g e n tf r a m e sf o rt h r e ec o m m o ns i m p l e x e s 对于一个顶点v ( 坐