（计算机应用技术专业论文）分布式虚拟环境中几何模型数据实时传输技术的研究.pdf

摘要近年来随着分布式虚拟环境系统的广泛使用，对系统的交互性、实时性、真实感的要求越来越高，网络带宽和延迟成为了分布式虚拟环境的主要限制。由于分布式虚拟环境广泛采用三维几何模型来描述场景，几何模型数据成为分布式虚拟环境中需要传输的主要数据之一。要解决网络带宽和延迟对分布式虚拟环境的限制，满足其实时性的要求，其中一个方法就是减少几何模型数据的传输量。为了保证一定的实时性，本文分成两部分对三维网格数据的实时传输进行研究。首先，提出将曲率和边界边等网格形状特征与二次误差度量相结合的边折叠方法，先对需要传输的数据进行预处理简化操作，在既保持原始网格的拓扑结构又保证网格模型的形状特征的同时，降低了模型的复杂度。其次，以尽可能减少运算量为原则，采用基于递进网格的简化方法，提出对边定义权值的方法确定边折叠的选择顺序，并通过用三角形权值来代替边权值的排序的方法，提高了网格模型简化的质量和效率。对经过预处理的模型产生适合渐进式传输的基网格和一系列细节信息，这样在传输时只需先将基网格传输过去，然后再逐一传输模型的细节信息即可。关键词：分布式虚拟环境，几何模型，实时传输，边折叠，递进网格a b s t r a c ta st h ea p p l i c a t i o n so fd i s t r i b u t e dv i r t u a le n v i r o n m e n t ( d v e ) b e c o m i n gw i d e ra n dw i d e ri nr e c e n ty e a r s ，t h ed e m a n d so f i n t e r a c t i o n 、r e a l t i m e 、t h i r dd i m e n s i o na r eg r o w i n gh i g h e r a tt h es a m et i m en e t w o r kb a n d w i d t ha n dd e l a yb e c o m et h em a i nl i m i t a t i o no fd v e s i n c ed v ew i d e l yu s e s3 dm e s hm o d e l st od e s c r i b et h ew h o l ee n v i r o n m e n t ，t h ed a t ao f3 dm e s hm o d e l sb e c o m e so n eo ft h em a i nd a t an e e d e dt ot r a n s m i ti nd v e t os o l v et h eb a n d w i d t ha n dd e l a yl i m i t a t i o no nd v e ，a n dm e e tt h ed e m a n do f r e a l - t i m e ，o n eo f t h em e t h o di st r y i n gt or e d u c et h et r a n s m i s s i o na m o u n to fg e o m e t r ym o d e ld a t a t oe n s u r et h er e a l t i m ed e m a n d ，t h i st h e s i sd i v i d e st h er e s e a r c ho nt h er e a l t i m et r a n s m i s s i o no ft h e3 dm e s hm o d e l si n t ot w op a r t s f i r s t l y , a na l g o r i t h mo fe d g ec o l l a p s ei sp r e s e n t e dw h i c hc o m b i n e sc u r v a t u r ea n dt h eb o r d e re d g e sw i t ht h eq u a d r i ce r r o rm e t r i cm e t h o d i ts i m p l i f y st h eo r i g i n a lm e s hm o d e lw h e ni ti sn o tt u r e l yn e e d e dt ob et r a n s m i t e d p r e s e r v i n gb o t ht h et o p o l o g i c a ls t r u c t u r ea n dt h es h a p ef e a t u r eo ft h eo r i g i n a lm e s hm o d e l ，t h i sm e t h o dd e g r a d e st h ec o m p l e x i t yo ft h em o d e l s e c o n d l y ,t h i st h e s i si n t r o d u c e sam o d e ls i m p l i f i c a t i o nm e t h o db a s e do nt h ep mr e p r e s e n t a t i o nw i t l lam l eo fr e d u c i n gc o m p u t i n ga m o u n t i tp r e s e n t sam e t h o di nw h i c haw e i g h ti sc o m p u t e df o re a c he d g e a n dt h ee d g ew i ms m a l l e rw e i g h ti sa l w a y sr e m o v e de a r l i e r f i n d i n gt h et r i a n g l e 、i t l ls m a l l e rw e i g h ti su s e dt or e p l a c ef i n d i n gt h ee d g ew i ms m a l l e rw e i 曲t ，w h i c hi m p r o v e st h eq u a l i t ya n de f f i c i e n c yo ft h es i m p l i f i c a - t i o n i nt h ee n d ，t h eo u t p u tm o d e lo ft h ef i r s ts t e pi sc h a n g e di n t oac o a r s em o d e la n d as e r i e so fd e t a i li n f o r m a t i o n ，s ow h e ni nt r a n s m i s s i o nw ec a nt r a n s m i tt h ec o a r s em o d e l a tf i r s t ，a n dt h e nt r a n s m i tt h ed e t a i li n f o r m a t i o ng r a d u a l l y k e y w o r d s ：d v e ，g e o m e t r ym o d e l ，r e a l - t i m et r a n s m i s s i o n ，e d g ec o l l a p s e ，p mr e p r e s e n t a t i o n6学位论文独创性声明：本人所呈交的学位论文是我个人在导n i g h 导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。如有不实，本人负全部责任。“一论文作者( 签名) 芥9 群j2 0 0 6 年6 月1 4 日学位论文使用授权说明：河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河海大学研究生院办理。论文作者( 签名)和葫2 0 0 6 年6 月1 4 日1 1 研究背景第一章绪论目前，随着网络技术的高速发展，同时也是适应交互式应用的要求，分布式虚拟环境( d i s t r i b u t e dv i r t u a le n v i r o n m e n t ，简称d v e ) 已经成为非常活跃的研究领域和发展方向，有着十分广泛的应用。如电视会议、科学研究可视化、多种类型的训练模拟器、艺术设计、游戏、远程医疗、合作式c a d 等等。分布式虚拟环境技术结合了计算机图形、声音模拟技术和网络互联技术，代表着计算机人机界面的发展方向。在分布式虚拟环境中，位于不同地点的多个用户通过计算机网络连接在一起，在一个由计算机三维图形、三维声音构筑的虚拟空问里实时交互，用户能够相互看到或听到，感觉就像处于同一个空间。因此d v e 系统应具有以下5 个方面的特征i l 】：( 1 ) 共享的虚拟工作空问；( 2 ) 伪实体的行为真实感；( 3 ) 支持实时交互，共享时钟；( 4 ) 多个用户以多种方式相互通信：( 5 ) 资源信息共享以及用户自然操纵环境中的对象。d v e 的研究与开发最早开始于8 0 年代初，最有代表性的是美国国防部为军事训练模拟资助开发的s i m n e t 系统【“，它的研究目标是开发一个供军事训练用的、低价的分布式军事虚拟环境系统。该系统的成功，为后来d v e 的研究开发奠定了基础，d i s ( d i s t r i b u t e di n t e r a c t i v es i m u l a t i o n ) 协议就是在s i m n e t 协议的基础上开发的，并最终成为d v e 的一项标准( i e e e l 2 7 8 ) 。由于d v e 系统在军事、协同设计、多学科研究、远程教育、网上游戏等众多领域都有广泛的应用前景，因此，各国政府和国际上一些著名的大学和研究所都开展了研究，开发了d v e 实验系统货开发环境和工具，如美国n p s 开发的n p s n e t ! ”、瑞典计算机科学研究所的d w e l 4 1 、贝尔实验室的r i n g f 5 1 、新加坡国立大学的b r i c k n e t n e r e f f e t l 6 1 、加拿大a l b e r t 大学的m r 工具库、英国n o t t i n g h a m 大学的a v i a r y ，以及著名的网络v r 游戏d o o m 等。我国国内也有国防科技大学的y h v r pl 7 1 以及北京航空航天大学的d v e n e t 8 等。由于d v e 系统对系统的交互性、实时性、真实感有较高的要求，同时各用户又要通过网络进行交互模拟和游戏，因此，网络通信的带宽、延时就成为d v e系统的主要限制，若进一步考虑系统的可扩展性，网络带宽和延时问题就更为突出。d v e 要支持快速实时的网络通信，主要有两方面的问题i l j ：一方面是当d v e的规模变大时，多个v e 之间的通信量会激增。在d v e 中，大量分布于不同地点的计算机通过网络连接在一起，要使各工作站保持连续状态是d v e 颇具挑战性的课题之一。另一方面是几何模型数据的实时传输问题。由于d v e 系统较为广泛的是使用三维几何数据来描述场景，而同时几何模型的数据量往往比较大，在低速、窄带宽网络连接条件的限制下，用户等待时间很长，不能忍受。因此，如何减少网络传输的几何模型数据量、缩短传输延迟、提高系统实时性能成为分布式虚拟环境的一个关键性问题。1 2 研究现状近年来随着连网的分布式虚拟环境系统的广泛使用，对如何减少d v e 系统中庞大的数据传输量已经有了很多研究，但大多数研究都是致力于从通信的角度控制网络的流量，然而在采取各种方式控制网络流量的同时，分布式虚拟环境中仍然存在大量的几何模型数据需要传输。同时，随着三维激光测距和建模技术的不断发展，获得真实物体的三维模型变得越来越容易。从小型的零件、商品，到人体、雕塑，再到大型的建筑、街道甚至城市，三维网格模型的精度和规模都在快速提高，模型的数据量也随之急剧增长。这些复杂的模型动辄就产生数以百万计的面片，对计算机的存储容量、处理速度、绘制速度、传输效率等都提出了很高的要求。对于如此庞大的几何模型数据，研究人员提出了各种模型简化的技术和算法。模型简化是指在保持原模型几何形状不变的前提下，采用适当的算法减少该模型的面片数、边数和顶点数，以减少模型数据量的技术。一直到上个世纪9 0 年代后期，国外研究人员陆续提出了多种网格模型简化方法，包括顶点删除、三角形删除、边折叠、三角形折叠和近平面合并等1 9 】。国内研究人员近几年也开展了一些卓有成效的研究工作 1 0 , 1 1 , 1 2 , 1 3 】，有些对已有多边形网格算法进行改进，有些是提出新的多边形网格模型简化方法。尽管这些研究都取得了很大成就，但是由于大部分这些研究仍然要考虑保证简化网格模型的质量，因此其简化的数据仍然有限，如果要直接在分布式虚拟环境中传输通过这些方法得到的简化几何模型的话，其传输量仍然显得过大。基于前面传统的模型简化技术的不足，c l a r k 提出了多分辨率表示又称为多层次细节模型( l e v e lo f d e t a i l ) 技术【1 ，在不影响画面视觉效果的前提条件下，通过逐次简化景物的表面细节来减少场景的几何复杂性。该技术通常是对同一个几何模型，存在着多种精度不同的表示，这多种精度的表示模型从简单到复杂、由粗糙向精细逐渐变化，与原模型相比，每个模型均保留了一定层次的细节。当从近处观察物体时，采用精细模型，而当从远处观察物体时则采用较为粗糙的模型。而后，l o d 技术取得了很多有意义的研究结果。1 9 9 1 年，d e h a e m e r i l 5 】利用自适应递归方法，提出了基于规则四边形网格表示物体的简化多边形网格的方法：在1 9 9 2 年，s c h r o e d e r 1 6 1 提出了基于顶点移去的网格简化算法。g r e g 1 刀给出了基于网格重新划分的多边形网格模型简化方法。随后在这些模型简化研究的基础上出现了一种采用递进方式传输的思想。递进传输就是利用网格模型的多分辨率表示，先传输比较粗糙的模型，再逐渐传输精细模型，可以做到边传输边显示，显示结果逐渐细化i 阍。然而，前面提到的传统l o d 方法均是对原始模型产生一系列离散的简化模型，无法保证l o d 模型间过渡有连续性，而不在模型层次切换时出现跳跃感。并且简化的模型常常需要非常多的层次，这对存储和传输仍然十分困难。而在2 0 世纪9 0 年代末期出现了一种递进网格的思想。最早由h o p p e 于1 9 9 6年提出【1 9 】。它克服了以往l o d 技术只能产生离散简化模型的不足，能够实时的生成连续过渡的多层次细节，从而不会出现在不同层次模型间切换时的“跳跃”现象。这种递进网格把任意网格表示成一个简化网格和一组记录了网格精简信息的序列。简化网格通过一系列顶点分裂操作就可以动态实时地恢复成原始网格。这种方法不仅能够提供一组连续的多细节层次模型，还支持递进方式传输和提供一种有效的网格压缩方式。但是其在简化过程中的计算量非常庞大，需要耗费极大量的预处理时间。1 3 研究内容及成果研究的主要内容及成果包括以下方面：r 1 ) 为了保证一定的实时性，本文分成两部分对三维网格数据的传输进行研究。第一部分，基于建模时产生的三维网格数据冗余度较大的事实，在尽量保持网格拓扑结构的前提下，可以先对需要传输的数据进行预处理简化操作，降低模型的复杂度。第二部分，采用基于递进网格的简化方法，对经过预处理的模型产生适合渐进式传输的基网格和一系列细节信息，这样在传输时只需先将基网格传输过去，然后再逐一传输模型的细节信息即可。( 2 ) 基于边折叠的网格简化预处理。在进行网格简化预处理时，采用基于边折叠的网格简化预处理方法，根据应用领域的不同要求或用户指定的误差范围生成一个简化模型。本文从既能保持原始网格拓扑结构又能保持网格的形状特征出发，提出了曲率及二次误差度量相结合的方法，先通过曲率和边界边控制筛选出可折叠边集合，然后根据二次误差度量确定可折叠边的折叠代价，并根据折叠代价对的折叠边进行排序，然后取折叠代价最小的边进行合法性检测，合法的边就将其折叠。最后给出了整个算法流程与数据结构的详细定义，并给出了实验结果。( 3 ) 实时递进网格的快速生成。递进网格把任意网格表示成一个简化网格和一组记录了网格精简信息的序列。简化网格通过一系列顶点分裂操作就可以动态实时地恢复成原始网格。这种方法简化的效果较好，而且能够有效支持递进方式传输。要尽量满足实时性的要求，就必须减少需要等待的时间。为了保证一定的实时性，在生成网格模型的递进网格表示时，本章以尽可能减少运算量为原则，提出给边定义权值的方法，并通过用三角形权值来代替边权值的排序的方法，在一定程度上提高了网格模型简化的质量和效率。在每一次执行边折叠操作的同时，保存本次操作相关的细节层次信息，最后实现了可以进行递进式传输的递进网格表示。最后给出了对整个算法流程与数据结构进行了详细定义，并给出了实验结果。1 4 论文组织结构本文由以下五章和参考文献组成。这五章的内容是：第一章绪论。介绍了本文的研究背景和研究内容。第二章相关知识介绍。介绍了本文研究涉及的相关基础知识，包括分布式虚拟环境中三维几何模型的基本概念，递进传输技术，各种常见的三维网格简化方法和这些简化方法的简化原则，以及在简化过程中用到的各种常见的误差度量方法。第三章基于边折叠的网格简化预处理。介绍了典型的边折叠简化算法，并对其优劣性做了比较，提出了曲率和二次误差度量相结合的边折叠简化算法，给出了算法流程及数据结构的设计，并给出了实验结果。第四章实时递进网格的快速生成。介绍了递进网格的基本原理，对递进网格生成方法中两种不同的边折叠选择顺序的优劣性做了比较，提出了以减少运算量为准则的递进网格快速生成方法。给出了算法流程及数据结构的设计，并给出了实验结果。第五章总结与展望。2 1 基本概念第二章相关知识介绍在虚拟现实中三维几何模型的表示方法主要有：样条曲面表示方法、三角网格表示方法。三角网格表示是一种最流行、最重要、且得到最广泛支持的种表示方法。图形学中许多技术都可以产生物体的三角网格，如使用三维激光扫描仪获取物体对象的三维几何模型，这些模型都是用三角网格表示。另外，很多软件也支持以三角网格表示的数据格式。虽然不同的软件实现中都有自己不同的数据格式，但本质上都是采用基于三角网格表示结构进行分析、操作和绘制的，比如辐射度计算、有限元分析以及碰撞检测等。描述一个三维几何模型所需要的信息一般包括三类：几何数据，拓扑关系和属性信息。几何数据即顶点的位置坐标，一般有三个浮点数表示。拓扑关系描述了顶点和面之间的联结关系，通常用三角形面片来表示，每个三角形用三个整数表示，每一个整数为指向一个顶点的索引。顶点索引必须按照一定的顺序给出，不同的顺序代表了不同的面片方向。属性信息一般包括平面的法向量、顶点的颜色、三角面的材质、纹理和光照系数等。属性信息不是必须的，而且因模型不同而表示方法不同。通常情况下，对于只考虑顶点信息和拓扑信息的三角网格模型，其数据结构由顶点列表和三角形列表组成。其中，顶点列表的信息单元记录每个顶点的空间坐标，而三角形列表的每个单元则记录了该三角形三个顶点的索引。具体表示方法如图2 1 所示。y 镝i顶点列表三角形列表顶点序号顶点举标v 1( x 1 y l ，z 1 v 2( x 2 , y a ，z 2 ，v 3( x 3 ，v 1 ，砀jv 4( x 4 ，y 4 ，盈：v 5( x s , y 5 ，z 5 1( x 6 , v 6 ，7 - 6 三角形编号顶点索引f 1( v l ，v 2 ，v 6 )f 2( v 2 ，v 3 ，v 6 )f 3( v 3 ，v 4 ，v 6 )矗心、n ，n af 5( v 5 , v l ，v 6 )图2 1 网格模型表示示意图6三角网格可以分为两类：流形和非流形。简单地说，所谓流形就是没有三个以上的三角形共享一条边。非流形的模型通常表现为在正常的模型上多出一些悬挂面。而非流形的三角网格并不是我们所期望的，它将给包括绘制在内的各种处理带来很大困难。因此在对三角形网格进行简化时应尽量避免产生非流形三角网格。本文中讨论的三角形网格都是流形的。2 2 递进式传输技术随着三维激光扫描仪和三维建模技术的不断发展，人们已经可以比较方便地获取真实物体的三维网格模型数据，因此三维网格也逐渐成为了一种重要的三维造型工具。与一维和二维信号相比，三维网格模型一方面因为描述对象维数的增加，另一方面因为描述形式的变化，数据量往往很大1 2 0 。与此同时，随着智能计算硬件成本的不断降低和有线、无线网络的不断普及，智能计算已经深入到社会生活的方方面面。无所不在的智能计算要求数据能够在网上进行自由的传输，因此信息的快速增长和有限的带宽形成了尖锐的矛盾。设计三维网格模型的递进传输算法就成了充分利用有限网络带宽和减少等待时间的迫切需要。根据三维网格模型( v ，f ) 中f 的不同可以将三维网格模型分为任意拓扑结构的网格模型和具有半规整结构的网格模型两种。任意拓扑结构的网格模型对于顶点集合矿中不同顶点之间的连接关系不作特定的要求，也就是说每个顶点可以和任意个数的顶点相连。而具有半规整结构的网格模型则要求网格模型可以由一个原始的网格模型进行细分操作得来2 。不同拓扑结构的网格模型，有着不同的递进传输策略。对于任意拓扑结构的网格模型，h o p p e 提出了其著名的解决方案【l ，其主要思想是将网格模型的渐进传输转化为网格模型简化的逆过程。h o p p e 的渐进网格技术，表现为三角形数目由少到多，三角形形状由大到小的过程，尽管采用了几何变形技术，给人的视觉效果还是不连续的跳变。而对于参数化后的具有半规整结构的三角形网格模型，l a b s i k 提出了新的解决方案瞄l 。他的策略是先将参数化面片的基面片传输过去，然后逐渐传输几何细节并进行自适应细分。但是由于参数化后面片的几何数据和参数化面片的基面片之间存在着形状上的根本差异，因此l a b s i k 的传输方法虽然消除了视觉上的跳变，但是显示效果的真实性依然没有提高，而且传输的总数据量依然很大。2 3 网格简化方法2 3 1 网格简化方法简介目前，虚拟环境中所使用的模型越来越精细、越来越复杂，有些模型有数以百万计的面片。这些复杂的模型对计算机的存储容量、处理速度、绘制速度、传输效率等都提出了很高的要求。然而在很多情况下，模型的准确度以及需要处理的时间要有一个折衷，因此必须用一些相对简单的模型来代替原始模型，这就要对模型进行简化。模型简化是指在保持原模型几何形状不变的前提下，采用适当的算法减少该模型的面片数、边数和顶点数。早在2 0 世纪7 0 年代，就有学者讨论网格模型的简化问题i ，然而直到9 0 年代以后，网格简化才得到深入的研究，并有了很多成功的应用。很多学者提出了各自不同的网格简化算法，可以将这些算法按以下方式分类，如根据网格拓扑结构在简化前后是否改变，可以分为拓扑结构保持形【2 3 ，2 4 1和非拓扑结构保持形【2 5 # 6 】：根据模型简化的过程可以分为逐步求精口7 2 8 】和几何化简【1 6 0 9 】；根据网格简化过程是静态执行还是根据视点等因素动态执行，可将算法分为静态和动态简化方法两类等；根据误差可控性可分为误差受限 2 4 】和误差不受限1 1 6 】；根据视点相关性可以分为视点无关的简化 2 3 , 1 q 和视点相关的简化【3 0 3 。需要说明的是，这些分类方法都难以囊括所有的简化算法，同时有很多算法彼此交叉f 弛 。下面从静态简化到动态简化这个顺序分别介绍各种算法，因为这种顺序体现了简化算法发展的过程。2 3 2 静态网格简化方法早期的模型简化算法大多属于静态化简，它是根据一定的精简原则，由复杂模型构造出简单模型用于绘制，它只考虑模型自身的信息，与视点无关，也不能恢复原模型的信息。静态化简也可以构造多分辨率模型，但是它要事先存储多个不同分辨率的近似模型，不同分辨率的模型进行切换的时候，由于相邻两层模型之间的面片数差别较大，因此会引起跳跃的感觉。静态简化方法主要包括以下几种方法：( 1 ) 顶点聚类法顶点聚类方法 2 5 , 3 3 , 3 4 】首先用一个包围盒将原始模型包围起来，然后通过空间划分将包围盒分成若干个区域，这样，原始模型的所有顶点就分别落在这些小区域内，将区域类的顶点合并成一个新顶点，再根据原始网格的拓扑关系对这些新顶点进行三角化，就得到简化模型。这是一种通用的不保持拓扑结构的简化算法，它可以处理任意拓扑类型的网格模型，且速度较快【3 2 】。由于这个方法是将模型的包围盒均匀分割，所以无法保持那些大于分割频率的特征，同时新顶点的生成只是采取简单的加权平均，而没有较好的误差控制，因此这种方法生成模型的质量不高。( 2 ) 区域合并法k a l v i n 和t a y l o r 提出了一种比较典型的区域合并方法【2 4 1 ，该方法选择一个三角面为种子面，根据一定的准则将周围的面合并起来形成一个更大的面( 称为超面) 。再将超面边界拉直，并对其重新三角化，从而达到面片化简的目的。这种算法可以由用户自己控制简化模型的误差，且可以保持模型的拓扑结构，但是由于无法避免带洞超面的产生，且重新三角剖分计算复杂，影响了算法的运行效率【3 5 1 。( 3 ) 几何元素删除法s c h r o e d e r 于1 9 9 2 年提出了顶点删除的网格简化方法【1 6 】，此后，基于边折叠2 9 1 、基于三角形删除【3 6 】等几何元素删除的方法被相继提出。这些方法的共同特点是以几何元素的删除实现模型的简化，即根据原模型的几何拓扑信息，在保持一定的几何误差的前提下删除对模型几何特征影响相对较小的几何“图元”：( 点、边、面) 。总的来说，这些算法易于实现，简化模型的质量很高，是目前最为常用的一类方法。下面分别介绍顶点删除法、边折叠法、三角形折叠法等。( a ) 顶点删除法在三角网格中，若一顶点与它周围三角面片可以被认为是共面的( 这可以通过设定点到平面距离的闽值来判断) ，且这一点的删除不会带来拓扑结构的改变，那么就可将这一点删除，同时所有与该顶点相连的面均被从原始模型中删除，然后对其邻域重新三角化，以填补由于这一点被删除所带来的空洞，继续这种操作直到三角网格中无满足上述条件的顶点为止【1 6 1 。这种算法计算较快，也不需要占用太多的内存，但是由于重新三角化需要将局部表面投影到一个平面，这种算法只适用于流形，而且它在保持表面的光滑性方面存在一定困难p7 1 。随后又有算法对其改进，并提出了更精确的误差测度，这些算法可以生成较高质量的模型，但是需要花费更多的时间和空问 3 8 , 3 9 , 4 0 , 4 ”。国内在这方面的工作有文献【1 2 a 2 i 等。实际上，顶点删除与边折叠极为相似，但是顶点删除需要重新三角化，比边折叠要复杂。f b ) 边折叠法边折叠简化算法是指，在每一次简化操作中以边作为被删除的基本几何元素。在进行多次的选择性边折叠后，面片就可以被简化到我们想要的任何程度了。点分裂是边折叠的逆变换，可以用来恢复被简化掉的信息。h o p p e 通过边折叠和点分裂构建了渐进网格( p r o g r e s s i v em e s h ，简称p m ) 模型，实现了多分辨率( m u l t i r e s o l u t i o n ) 的层次细节模型( 1 e v e lo f d e t a i l ，简称l o d ) 的实时生成 捌。边折叠的关键是折叠的次序以及边折叠后新顶点的位置。h o p p e 在1 9 9 3 年采用能量优化的方式来确定折叠次序和新顶点的位置【2 9 1 ，能量优化计算复杂，所需时间较长，但是生成模型的效果却是在所有简化方法中最好的【4 3 1 。g a r l a n d和h e c k b e r t 在1 9 9 7 年提出了一种基于二次误差测度( q u a d r i ce r r o rm e t r i c ，简称q e m ) 脯j q g 算法h 4 j 。q e m 算法误差测度是基于顶点到平面的距离平方和，该算法速度快，简化生成的模型质量仅次于h o p p e 的能量优化方法。是一种非常有效的简化算法。h o p p e 将法向量、颜色以及纹理等信息加入到q e m 算法中，然后采用叫做翼( w e d g e ) i 掬1 数据结构来加以实现，也得到了较好的效果【4 5 j 。l i n d s t r o m 和t u r k 在1 9 9 8 年用化简前后体积和面积的变化作为误差测度，也得到了与q e m 类似的数学表达【4 6 】。这种方法在计算边折叠队列和新顶点的位置时只需要网格模型面的连接信息和顶点的位置，所以此算法占用内存量小，运算速度快。c o h e n 等人采用边折叠简化结合连续映射来简化多边形网格【4 7 】；a n d r eg u s z i e c 定义了边的重要度，按照重要度从小到大的顺序来对合法的边进行删除【4 8 j ；a l g o r f i 则通过确定模型的特征边来进行边折叠操作 4 9 1 ；李现民采用改进的蝶形细分算法来计算新顶点的位置，效果较好，但是时间复杂度较高1 5 0 】。( c ) 三角形折叠法三角形折叠算法是指，在简化时三角面作为被删除的基本元素。它是边折叠算法的延续。h a m a n n 将三角形的权重定义为等角度( e q u i - a n g u l a r i t y ) 与曲率的乘积，然后对网格模型上的所有三角形按权重进行排序，并依次折叠，这样细长且低曲率的面首先被删除3 6 1 ；t r a ns g i e n g 等人也提出类似的三角形折叠简化算法，他们定义每个三角形的权重为该三角面的面积与曲率等因素的乘积i5 1 1 ，这种算法复杂度较高，但是它可以较好地保持外形；i s l e r 等人则将边折叠与三角形折叠结合起来构造了半实时多分辨率模型5 2 1 ；周昆等人将三角形折叠与q e m 算法结合起来，并给出了一种传递简化误差的方法 5 3 1 ，国内在这方面的工作还有文献 5 3 , 5 4 , 5 5 1 等。( 4 ) 小波分解小波分解方法为首先由l o u n s b e r y 和d e r o s e 在1 9 9 4 年提出5 “。它的主要原理就是利用小波分析的方法将一个三维模型分解成低分辨率部分和细节部分，低分辨率部分是原始模型的一个子集，它的顶点为原始模型中对应顶点的邻域的加权平均，通常用低通滤波来实现，因此表现为低频信号，细节部分通常包含抽象的小波系数，这些系数通过高通滤波来得到，表现为高频信号，重建过程就是通过选择适量的高频信号与低频信号以合成相应精度的三维模型，通过略去其余的更高频分量来达到简化的效果。这种方法简单、高效，但它只适用于具有细分连通性的三角网格。1 9 9 5 年，m a t t h i a s e c k 等人改进了上述算法使其能够处理任意拓扑的网格 5 7 , 5 s 1 。2 3 3 动态网格简化方法动态网格简化的基本思想是：在模型的简化过程中，可以实时地得到具有所需要的分辨率的近似模型，每个模型的简化程度由模型之外的因素决定，例如视点。动态简化一般是通过一些简单的局部的几何变换来实现，从而生成具有连续的不同分辨率的近似模型。动态简化是静态简化的延续，它的很多基本操作采用的是静态简化的方法。( 1 ) 层次表示法i s l e r 等人提出了一种混合方法来实现半实时的层次细节表示【5 2 1 ，该算法预先产生几个关键的简化模型，并对其中的三角面按视觉重要度排序，在实时绘制中，选择一个比所需分辨率高的最简的逼近模型，并对该逼近模型按重要度从小到大的顺序删除三角面，直到满足当前精度为止，这样可以部分地解决计算量大的问题。r r o n f a r d 首先对每条边定义由于它的删除所造成的简化网格模型与原始网格模型之间的几何偏差，并将其按照从小到大进行排序，然后根据用户对模型复杂程度的需要，依次进行边删除操作，这个算法可以生成原始网格一系列连续的简化模型5 9 1 。( 2 ) 递进网格法在动态简化方法中，最著名的算法当属h o p p e 在s i g g r a p h 9 6 上提出的p m 算法1 9 】，p m 算法以边折叠和点分裂为基本操作，记录了模型简化过程中原顶点和新顶点位置以及顶点问的连接关系的变动信息，从而生成了一个由原始模型的最简化模型和一系列简化信息组成的p m 表示模式，p m 可以把任意拓扑网格表示为一种高效、无损且具有连续分辨率的编码。在实时绘制时，通过逆向跟踪简化信息序列，对每条简化信息执行点分裂逆操作，可以逐步恢复所删除的模型细节，实时得到原始模型的连续精度的简化模型，由此实现了l o d 模型的平滑过渡。p m 很大程度上克服了以往模型的平滑过渡方面的不足，可以支持不同细节的网格模型的实时生成。但是在实现同一网格不同区域多分辨率的细节的实时生成方面，p m 仍缺乏有力的数据结构的支持，同时由于边删除的先后顺序与边的几何拓扑信息无关，因此在模型恢复的过程中必须进行逐一判断，而很难实现l o d 模型的实时生成。陶志良对p m 的二义性，提出了支持快速恢复的可逆递进网格【捌。费广正则利用递进网格进行多层模型编辑”。( 3 ) 基于视点的简化方法1 9 9 6 年，j u l i ec x i a 提出了一种实时的基于视点的三角网格模型简化算法p o ，该算法可以实时地在同一模型的不同区域选择不同的精度层次；h o p p e 定义了一个基于视锥模型表面法向和屏幕空间几何误差的细化标准，该标准包括视锥原则、面的方向性原则和屏幕空间几何误差原则，并利用此准则进行选择性的边折叠和点分裂，建立多分辨率的模型6 2 ；d a v i dl u e b k e 等人采用八叉树将空间进行划分，当一个八叉树节点所对应空间的体积投影到屏幕上小于指定范围时，就将这个节点中的所有顶点折叠在一起，并删除所有的退化多边形 6 3 ，州；李捷通过对模型中每个顶点的重要度进行排序，建立了视点参数与被选择的分辨率的直接关系，生成了实时连续多分辨率模型”l ；周昆则将视点无关与视点相关结合起来，生成混合多细节层次模型1 6 ”。2 4 简化原则和误差度量方法2 4 1 简化原则和误差度量简介由于网格模型大部分由三角面片表示，而且即使原始模型不是三角面片，也可以对其进行三角化，因此网格模型简化的本质是：在尽可能保持原始模型特征的情况下，最大限度地减少原始模型的三角形和顶点的数目。它通常包括两个原则：定点最少原则，即在给定误差上界的情况下，使得简化模型的顶点数最少：误差最小原则，给定简化模型的顶点个数，使得简化模型与原始模型之间的误差最小【删。误差度量用来量化输入模型和输出模型的差异。它引导模型简化，使得简化后的误差在用户允许的误差范围之内。误差度量包括外观相似度量和几何误差度量【3 7 1 。外观相似度量用来计算原始模型与简化模型投影到视平面的差异，它最符合人们的视觉习惯，但由于它需要从各个视点进行采样，计算量大，因此在实际应用中通常用几何相似度量来代替。几何误差度量被定义为瓦。( m ，鸩) 2 m a x ( 理棼d r ( m 2 ) ，妥黔d v ( m ) )( 2 1 )其中矾( m ) 表示一个顶点v 到一+ n c l m 的距离( d ，( m ) = 卿一叫i ，l | 1 i 是两个向量的欧式距离) ，这个误差用来度量两个模型之间的最大偏差，同样两个模型之间的平均偏差可以定义为( m ，鸠) 2 百1f 。，( m ：) + 瓦li 。，刃( m 一)( 2 - 2 )其中，w j 和w 2 分别是m 和m 2 的面积。2 4 1 常用误差度量方法前面两种误差度量方法在实际应用中计算量是非常大的，因此人们又总结了以下较为通用的误差度量方法：( 1 ) 全局误差度量全局误差度量是指所有点上近似误差的总和，有。1 日托y ) 一( 舔) ( t y ) i( 2 3 )控制全局误差通常可以得到较好的近似效果，但也会增加计算量和算法的复杂性。在网格简化过程中，所删除的顶点必须有尽量小的全局误差，而在网格精化过程中，所增加的顶点必须有尽量小的全局误差。( 2 ) 局部误差度量局部误差度量是一种简单的误差度量方法，仅对局部点的误差进行统计。在高度场数据中，一个点( z ，y ) 的重要性可定义为i h ( x ，y ) ( r s ) ( 工，_ y ) i ，其中i - i ( x ，y )为原有模型中( x ，y ) 点处的高度值，而( f s ) ( 墨y ) 为近似模型e o ( x ，_ y ) 点处的高度值。很显然，这种局部误差越小，所产生的近似模型的质量越高。这种误差度量方法简单，快速，且只用到局部信息，因而得到了广泛应用。例如在s c h r o e d e r的算法中，使用点到平均平面的距离作为局部误差度量方法【1 6 】。( 3 ) 曲率度量曲率往往代表区域的平滑程度。在用三角形网格描述物体的表面时，根据曲率可以很好地区分表面的一些特征( 如地形数据中的峰、谷、脊) 。在进行简化时，可在高曲率处保留尽量多的点，而在低曲率处删除尽量多的点。对于由函数h ( x ，力给定的表面，通常使用下面的式子作为曲率度量：( a 2 h o x 2 ) 2 + 2 ( a 2 h o x o y ) 2 + ( a 2 h 匆2 ) 2 ( 2 4 )1 4t u r k 通过计算顶点和三角形的曲率，把新顶点分布在曲率较大的三角形上( 4 ) 特征角度量多边形网格中顶点的重要性也可以用特征角来衡量，特征角可以定义为顶点处任意两个相邻三角形的法向量之间的夹角中的最大者。除此之外，还有一些其它的误差度量方法：周晓云等1 2 1 利用几何模型的特征角度作为误差度量准则；c o h e n 等扣6 1 通过构造包络网格来控制简化网格的全局误差：b a j a j 等6 7 疑出通过误差传递方法来度量简化模型与原模型的误差；k a l v i n等2 4 1 则提出基于h a u s d o r f f g e 离来度量简化模型与原模型的误差等等。2 5 本章小结本章介绍了论文研究涉及的相关基础知识。包括计算机图形学中三维网格模型数据及相关概念，实现递进式传输采用的典型递进传输技术，以及网格传输过程中涉及到的各种网格简化方法，和网格简化过程中所采用的简化原则和常用的误差度量方法。第三章基于边折叠的网格简化预处理3 1 概述分布式虚拟环境中较为广泛的是使用三维几何数据来描述场景。随着三维激光测距和建模技术的不断发展，获得真实物体的三维模型变得越来越容易。从小型的零件、商品，到人体、雕塑，再到大型的建筑、街道甚至城市，三维网格模型的精度和规模都在快速提高，随之急剧增长的就是模型的数据量。目前包含数以百万计三角形的模型已不鲜见，而像美国s t a n f o r d 大学著名的“数字米开朗基罗工程( md i g i t a lm i c h e l a n g e l op r o j e c t ) ”【2 0 1 中采集的几尊大型雕像的三维模型，都是由数以亿计的三角形组成，其数据存储量达到f g b y t e 量级。与此同时，随着分布式虚拟环境技术的发展，要求不仅能够在p c 机上对这些三维模型进行浏览、编辑，还能在网络上自由地进行传输。于是数据量的快速增长与计算机有限的计算能力和带宽限制就形成了尖锐的矛盾。然而事实上，目前一方面，由于大多数网格模型是通过成熟的造型软件或三维测量设备自动生成的，为了保证对模型造型的精确性，对模型的采样是有很大的冗余度的( 例如，机械零件c a d 系统生成的零件模型有很多共面的顶点、边和三角形；科学计算可视化中的等值面抽取算法m a r c h i n gc u b e l 6 8 产生的大量三角面片也有冗余) 。在分布式虚拟环境中进行传输前先去除这些冗余的数据，就能够有效地减轻系统传输的压力。另一方面，不同的应用领域需要不同精细程度的模型，很多应用领域对实时性的要求都高于对精度的要求。基于以上两方面原因，可以根据应用领域的不同要求或用户指定的误差范围，先用一般网格简化算法对模型进行预处理，预生成满足要求的简化模型，再用得到的简化模型生成适合递进式传输的递进网格，达到实时传输的效果。在进行网格简化预处理时，并不是要预先生成一系列简化网格模型，而是根据应用领域的不同要求或用户指定的误差范围生成一个简化模型，这个简化模型将代替原始模型用于后继的实时传输过程。只要是能够控制简化操作带来的全局误差的简化算法都可以用在我们的预处理过程中。从现有的网格简化算法来看，对网格的简化策略，可以大致分为对网格几何6元素( 点，边，面) 的合并，或对网格几何元素的删除，或是在对拟合曲面的不同逼近误差下，对网格顶点重新采样。其中对网格几何元素删除的方法思想比较简洁，使用中较为方便，在实际应用中也最广。网格几何元素点，边面的删除，又可细分为顶点删除算法【1 矾，三角形删除算法【3 6 1 ，边折叠算法1 2 9 , 4 4 , 4 9 , 6 9 ，三角形折叠算法1 5 2 , 5 3 等等。从网格简化算法发展的过程来看，其中顶点删除算法，三角形删除算法是较早提出的算法，这两种算法执行顶点删除和三角形删除操作后需要对产生的空洞重新三角化。由于三角化的操作比较费时，当处理的网格的数据量较大时就显得处理速度太慢了。而折叠算法是将原来顶点的拓扑关系延续到新点上来，修改的仅仅是逻辑上的变更，所以在算法的运行效率上有很大的改进。因此，本文主要研究采用基于边折叠的简化算法完成数据传输的预处理过程。3 2 典型的边折叠简化算法在折叠算法中，边折叠( e d g e c o l l a p s e ) 算法是一种非常重要的简化算法。1 9 9 3年h o p p e 等人【2 9 1 首次提出了边折叠思想：在每一次简化操作中以边作为被删除的基本几何元素，并增加一个新点，所有与被删除边相连的点都与该新点相连，使模型仍保持是三角形网格。在进行多次的选择性边折叠后，模型就可以被简化到我们想要的任何程度。q 一( a ) 折