面向虚拟制造的多细节层次模型研究

PAGEIV摘要为适应市场的瞬息多变并减少生产成本和周期，各制造企业将许多先进技术引入到设计和制造领域，由此产生了许多新的制造技术和制造系统。虚拟制造是先进制造技术发展的必然结果，已成为先进制造技术研究领域的热点之一。虚拟制造技术的迅速发展，对虚拟现实技术的要求与日俱增；作为虚拟现实的核心技术，真实感图形实时绘制技术在很大程度上影响着虚拟制造技术的进步。本文就多细节层次模型的网格简化算法这一实时绘制技术作了初步探讨与实践。首先，在广泛阅读国内外相关文献资料基础上，介绍了实时绘制技术的基本理论，给出了课题的研究背景、研究现状和发展趋势，总结了网格简化算法的有关理论和技术。然后，在真实感图形绘制算法有关理论的基础上，提出了一种视相关的网格模型简化算法，结合网格模型的四个简化标准，根据视觉敏感度加大场景简化幅度，从而提高绘制速度。利用空间八叉树建立场景网格模型的层次结构，并给出一种基于z-Buffer的场景模型快速消隐算法。接着，根据视相关的网格简化算法，利用OpenGL编程，开发了一个加工设备快速绘制的原型系统。并以模块化的思想设计了原型系统的总体结构，详细介绍了它的基本功能和各模块的具体实现。该系统为开发具有实际应用价值的相关系统进行了有益的探索。最后，总结了本文的工作，并指出进一步的研究方向。关键字：虚拟制造网格简化细节层次视相关八叉树

AbstractTokeepupwiththerapidlyshiftingmarketandreduceproductioncostandtime,manufacturingenterprisesintroducemanyadvancedtechnologyintodesignandmanufacturingarea.Virtualmanufacturingistheinevitableresultofthedevelopmentofadvancedmanufacturingtechnology,anditbecomesoneofthefocusesintheresearchareaofadvancedmanufacturingtechnology.Therequirementsfortechniqueofvirtualrealitywiththerapiddevelopmentofvirtualmanufacturingincreasesteadily.Asakeytechniqueofvirtualreality,3Dgraphicsreal-timerenderingtechniqueaffectstheprogressofvirtualmanufacturingtechniqueinaconsiderabledegree.Inthispaper,themeshsimplificationofmultiplelevelofdetail,oneofreal-timerenderingtechniques,isstudiedandimplemented.Firstofall,basedonthesystematicreadingoftherelativeliteratures,thegeneraltheoryofreal-timerenderingtechniqueisintroduced.Thebackground,currentstateofart,thefuturetrend,thepurposeandsignificanceofthisresearcharereviewed,andthenthetheoriesandtechniquesoftherelativealgorithmofmeshsimplificationaresummarized.Secondly,basedontherelativetheoryof3Dgraphicsrenderingalgorithm,aview-dependentsimplificationalgorithmofmeshmodelisproposed，whichcombiningvisualacutenessandfourcriterionsforsimplificationofmeshmodel.Thisalgorithmcansimplifythemeshesofthescenedrasticallyandacceleraterenderingspeed.Furthermore,themeshmodelofsceneisbuiltbyusingspatialoctreeandaz-bufferhiddenalgorithmisputforward.Thirdly,aprototypingsystemforthequickrenderingofworkshopsceneisdeveloped.Thegeneralstructureofthesystemisdesignedinmodules;thefunctionsandrealizationofdifferentmodulesaredescribedindetail.Thissystemwillbenefitforthedevelopmentofrelativesystemswhichhavethevalueofpracticalapplication.Finally,allworkofthethesisissummarized,andtheproblemsthatneedtobesolvedinthefuturearealsopointedout.KeyWords:virtualmanufacturinglevelofdetail(LoD)meshsimplificationview-dependentoctree

目录摘要 IAbstract II1绪论1.1课题来源 (1)1.2课题的研究背景、目的及意义 (1)1.3国内外发展状况 (4)1.4三维图形应用程序接口 (7)1.5本文的主要工作 (8)2真实感图形的绘制技术2.1虚拟场景表示 (10)2.2基本消隐技术 (11)2.3纹理映射 (14)2.4图形生成的加速方法综述 (16)2.5本章小结 (21)3多细节层次模型绘制算法研究3.1三维图形显示中的一些概念 (22)3.2视相关的网格动态简化算法 (23)3.3实验结果 (34)3.4本章小结 (35)4多细节层次模型绘制中空间八叉树的应用4.1引言 (36)4.2构造八叉树 (36)4.3基于z-Buffer的快速消隐算法 (39)4.4本章小结 (42)5多细节层次模型在加工设备快速绘制中的应用5.1引言 (43)5.2原型系统的结构与功能 (43)5.3原型系统各模块的实现 (45)5.4研究实例 (47)5.4本章小结 (48)6全文总结与展望6.1全文总结 (49)6.2后续工作展望 (49)致谢 (51)参考文献 (52)附录1攻读学位期间发表学术论文目录 (56)1绪论1.1课题来源本课题研究属于下列项目的重要组成部分：(1)国家863计划“先进制造与自动化技术”领域“机器人技术主题”项目：“开放式数控装备的远程操作、监控与诊断技术研究”(项目编号：2001AA423230)；(2)中国－新加坡“中新联合研究计划”项目：“基于网络的产品开发平台”；(3)新加坡国家科技局资助项目：“基于多智能体的数字制造（Multi-Agent-basedDigitalManufacturing）”；(4)湖北省自然科学基金项目：“数控加工远程监控中的可重构理论与技术研究”（项目编号：2003ABA002）。1.2课题的研究背景、目的及意义随着现代科技的日新月异，国际市场的动态多变和竞争的加剧，世界经济一体化进程的逐渐加速，制造企业所处的环境发生了巨大的变化。全球性商业竞争给制造模式和制造方法带来了深刻的变革，其中的显著特点是产品多样化、质量高、价位低、周期短。决定制造企业全球竞争能力的主要指标是产品的开发时间(Time)、质量(Quality)、成本(Cost)以及相应的服务(Service)，即TQCS。为适应市场的瞬息多变并减少生产成本和周期，各制造企业将许多先进技术引入到设计和制造领域，由此产生了许多新的制造技术和制造系统[1]。虚拟制造(VirtualManufacturing,VM)是先进制造技术发展的必然结果，已成为先进制造技术研究领域的热点之一。目前，虚拟制造技术还缺乏从产品生产全过程的高度开展虚拟制造技术的系统研究，因此，虚拟制造技术的内涵到目前为止也没有统一的定义，许多学者从不同角度对虚拟制造技术进行了探索，并给出了相应的定义。通过对各种已有虚拟制造的定义进行综合，可以发现，虚拟制造本质上属于仿真技术，是各种制造仿真技术的系统集成[2]，其核心是虚拟现实技术、建模技术、仿真技术、网络技术和管理技术等[3]。虚拟现实技术是利用计算机技术建立一种逼真的虚拟环境，人们可以沉浸在这个环境中与环境进行实时交互；建模技术包括产品的立体几何模型、物理模型、加工过程模型、工厂运作模型等；仿真是虚拟制造技术的核心内容，只有通过仿真才能确定产品设计和生产工艺的可行性和合理性，才能保证产品制造的成功和生产周期；网络技术的应用，建立了技术人员之间的直接联系和协同工作的基础，使得并行工程、人力和技术集成、信息交流等现代制造技术成为可能，企业内部的管理和虚拟企业的实现，没有网络是不可能的。总之，虚拟制造技术是利用仿真与虚拟现实技术，在高性能计算机及高速网络的支持下，采用群组协同工作，通过模型来模拟和预估产品功能、性能及可加工性等各方面可能存在的问题，实现产品制造的本质过程，包括产品的设计、工艺规划、加工制造、性能分析、质量检验，并进行过程管理与控制[4]。作为虚拟制造的一个支撑技术，虚拟现实(VirtualReality,VR)技术己渗透到各个领域，发展成为多学科的交叉领域。近年来，虚拟现实对于人类生活的各个方面都产生了巨大的影响，虚拟现实技术已经在科学计算可视化、医学应用、培训、娱乐、产品设计等广阔的领域中得到了广泛的应用。从游戏、娱乐、家居设计到战场模拟，耗资巨大的实物被计算机变成了一个虚拟世界。凭借虚拟现实技术，人们可以进入这个由计算机模拟的虚幻世界，并可以像对待真实世界那样去操纵和改变它。所有这些应用都是以实时绘制技术的研究突破为背景，只有提高了系统的实时性，用户与虚拟场景才能进行互动和交流，产生沉浸感。这项技术还有更广泛的应用前景，通过与互联网技术结合，应该可以创造更加完美的虚拟世界，人们可以在虚拟世界中购物、工作，如同在真实世界一样。虽然现在的互联网也提供了一些类似的应用，但用户在虚拟世界中的视觉与听觉等感觉与真实世界还存在较大差距。这种差距的产生原因是多方面的，但最主要的原因是受到了虚拟现实技术发展水平的限制。也就是说虚拟现实技术的发展状况仍制约了虚拟现实进一步的推广应用。其中虚拟场景的快速生成，实时的人机交互是制约其发展的主要原因。实时性是虚拟现实技术的关键因素之一，它要求系统能实时地对各种输入做出反应。例如，当观察者在虚拟环境中走动时，随着观察者视点和视线方向的变化，系统必须实时更新场景画面。根据人眼的视觉暂留特性，要给人以连续运动的感觉，画面更新速度应达到24帧／秒。虽然高速发展的CPU技术和专用图形处理器使得现今的图形工作站和个人PC机的性能得到了很大的提高，但距离VR的应用需求仍相当遥远。如波音公司推出的完全由计算机设计的波音飞机模型的复杂度远远超过了当今最先进图形工作站的实时处理能力，需要几百台图形工作站的联网运算；PC机更是无能为力。因此，虚拟现实系统中场景模型的复杂度和交互实时性之间的矛盾是虚拟场景绘制中存在的主要问题，也是制约虚拟现实应用发展的瓶颈技术。随着虚拟现实应用领域的日益扩大及应用内容的复杂化，真实感图形实时绘制技术的需求急剧增加。因此研究并采用一些可应用于现有通用计算机平台、高效的图形绘制算法，以加速对复杂场景和造型的绘制，进而解决绘制算法在速度、质量及场景复杂度之间越来越突出的矛盾，已成为计算机图形学领域一个非常重要的课题。虽然可以用高档计算机来处理、存储复杂的模型，如使用计算速度高、存储容量大、图形功能强的图形工作站等。这是一个有效的办法，但不能完全解决问题。首先随着应用需求的发展，模型复杂程度的增长几乎是无限的。机器的性能提高了，可是模型的复杂程度会成倍增加。其次，高档计算机需要大量的投资，非一般用户所能承受。因此，如何利用中低档的计算机，特别是PC机来处理复杂的几何模型，是一个重要课题。因此，在利用高性能计算机的同时，人们提出了多种技术和算法，力求更有效的解决复杂模型的处理、存储、传输和绘制问题。其中，复杂模型的多分辨率表示和绘制是最有效的方法之一。计算机图形学、科学计算可视化中所生成的模型一般是由多面体表示的。模型简化指的是采用适当的算法减少该模型的面片数、边数和顶点数。模型的多分辨率表示则是指对于同一模型，存在着由简到繁、由粗到精的几种表示。模型的面片数减少以后，其表示精度必然下降。但是，在许多情况下对应用并无影响。一个典型的例子是，在对多面体模型进行动态显示时，如果模型距图像平面很远，其在图像平面上的投影必然很小，只有几个像素。那么，无论模型精确到何种程度，其细节在屏幕上都不可能表示出来。因此，只需使用简化的、比较粗糙的模型就可以了，从而可以大大减少存储容量、提高计算速度。当一个模型存在着多种分辨率的表示时，可以根据不同要求选用不同分辨率的模型。具体来说，应根据模型在屏幕上覆盖的像素的多少选择相应的层次。对近的物体绘制时，使用较精细的模型；对远的物体则使用较粗糙的模型。从而保证在对原模型的图像有良好的形状逼近的前提下，尽量减少用于表示该模型的多边形数目[5]。这就是细节层次模型的基本思想。细节层次（LevelofDetail，LoD）基本原理是，利用透视投影的特性——距离当前观察视点越远的物体，其在成像平面上的投影面积越小，那么对远处的物体在绘制阶段可用较少的等效绘制元素来表现它。这里提到的所谓“物体”是指具有一定逻辑意义的绘制模型，而“等效”是指两者的透视投影基本相同或差异很小。为物体提供不同的LoD模型是控制场景复杂度和加速图形绘制速度的一个非常有效的方法[6]。LoD模型的研究为解决图形显示质量和显示速度之间的矛盾提供了一条可行而有效的方法。它改变了图形越精确越好的片面看法，而是依据视线的主方向、视线在景物表面的停留时间、景物离视点的远近、景物在屏幕投影区域的大小和场景中每个图形对象的重要性等因素决定景物应选择的绘制精度。从而实现场景模型的实时绘制。1.3国内外发展状况1.3.1虚拟制造技术的发展概况虚拟制造自1993年出现以来，经过十来年的发展，取得了长足的进步。因其具有诱人的应用前景，西方工业国家相继成立了一大批虚拟制造研究机构，开展应用基础技术的研究，建立了虚拟制造技术体系，并在企业已经得到广泛的实际应用，取得了巨大效果。在美国，目前已形成了由政府、企业、大学组成的多层次、多方位的综合研究开发力量。其中主要研究项目有：(1)美国国家技术标准研究所正在建立国家先进制造实验基地。该基地与马里兰大学、芝加哥大学、佛罗里达大学、俄亥俄大学、波音公司等34家单位合作，主要进行制造电子商务等研究。(2)华盛顿州立大学的VRCIM实验室的设计与制造虚拟环境项目。(3)马里兰大学的虚拟制造数据库项目等等。在欧洲，许多大学如英国曼彻斯特大学、巴斯大学、德国达姆斯特技术大学计算机图形研究所等等都确定以VM作为重点研究方向。在日本，形成以大阪大学为中心的研究开发力量，进行了大量VM系统体系结构的基础研究和系统开发。国外许多知名企业已在积极地开展虚拟制造技术的应用研究。虚拟制造技术在汽车、飞机、工程机械以及武器等产品上的应用实例和成果已经陆续见诸报端。比如，美国国防部先进计划署ARPA致力于将虚拟环境于物理建模、发布离散性模拟等技术结合，为虚拟武器设计提供先进的手段。加利福尼亚RockwellInternational公司开发了将现有CAD数据转换传递到虚拟环境的软件，工程技术人员能看见设备部件是如何被装配的，无需制作零部件的物理模型。美国Metalagraphics公司应用虚拟检测技术于航空和军事产品的零部件加工。食品生产商Nabisco计划将组装生产线进行拟实化，以便培训人员去维护和维修生产线。摩托罗拉公司自1994年起使用虚拟产品开发技术。据报道，该项技术节约了该公司数百万美元的培训费用。波音公司采用虚拟原型技术在计算机上建立了波音777飞机的最终模型。福特汽车公司已应用虚拟环境技术于汽车设计与工程。该公司的先进车辆技术组应用虚拟制造技术于装配仿真和虚拟成型，以提高空气动力学、人机工程学和表面建筑的效果。世界最大的挖土机和建筑设备制造企业CaterpillarInc.将虚拟设计用于评价新样车的内部可视性，节约了机型试制费用，大大缩短了开发周期[7]。我国自1996年开始虚拟制造技术的跟踪研究，并日益引起我国科技工作者的关注，目前全国已有几十家科研机构、高等院校和企业正在开展VM技术方面的研究，进行初步的应用。作为虚拟制造技术的核心技术，虚拟现实技术这些年来也得到迅速发展，而其中的实时绘制技术在20世纪80年代以真实感图形生成为主线的蓬勃发展，今天已能够生成达到照片真实感的图形，并在计算机辅助设计(CAD)技术、工业设计、室内设计以及计算机动画、电影特技镜头等领域获得广泛的应用。近年来，计算机运算速度与图形硬件加速器的性能均有很大提高，但与用户对模型的复杂度、真实感和实时性的追求相比仍然落后于实际需要。因此，为了处理大规模几何模型，基于几何的建模和绘制技术派生了一系列新技术。例如，模型的多分辨率表示(multi-resolutionrepresentation)、多细节层次处理技术[8]。如何解决模型的复杂度、绘制的真实感和实时性三者之间的矛盾一直是计算机图形学和虚拟现实技术所努力的方向。自20世纪90年代初以来，基于图像的建模和绘制（Image-basedModelingandRendering，IBMR）技术应运而生。它通过对真实（或虚拟）世界进行有限的采样，即获得一组图像（如照片），根据给定视线方向，通过对上述采样图像的重组，即重采样，来获得新视图。相对于基于几何的建模和绘制技术，这种技术具有建模容易、真实感强、绘制速度快等优点。但采用单一的IBMR技术无法创建虚拟对象，通常需要与基于几何的建模和绘制技术结合来进行虚拟场景的绘制[8]。1.3.2网格简化技术的发展概况近年来，作为实时绘制的一个重要手段，网格简化技术也得到了迅速发展。网格简化的目的是把一个复杂多边形表示的模型用一个近似的模型表示，近似模型基本保持了原模型的可视特点，但顶点数目少于原网格的顶点数目。网格模型的简化算法即通过一定的误差判定，删除那些对模型几何形状影响不大的几何“图元”(顶点、边或三角形)，达到模型简化的目的，得到在不同精度上逼近原复杂模型的近似模型。为了保证拓扑特性，许多算法必须对几何元素删除后所遗留的空洞、进行复杂的三角化过程。Schroeder于1992年首次提出一种以顶点操作实现模型简化的方法[9]。该方法的基本思想是：首先根据模型局部的几何拓扑特性，将顶点划分。然后用距离误差分别计算顶点的重要性，根据各类顶点删除所导致的误差决定该顶点的删除。如在误差允许范围内，则删除该顶点并对删除该顶点所遗留下的空洞进行三角化。顶点删除法算法计算量小，时间复杂度为线性，执行效率高。它能很好地保留几何特征，保持拓扑结构。但多次迭代的情况下会积累误差。1993年，Hoppe提出一种以边操作实现模型简化的LoD模型自动生成算法[10]。该方法最大的特点即通过对边的各种操作（边蜕化为点、边对换、顶点分裂）来求取能量意义上的原模型的最优逼近模型。该方法以边蜕化为一新的顶点，以被蜕化的边的两端点对应新顶点，由原端点的连接关系就可得到简化区域的保持原连接关系的三角片模型，避免简化操作后的三角化问题。这个算法首次提出了以顶点合并，即边的顶点合并为一个新顶点这一复杂模型简化方式，避免模型简化后复杂的三角化过程，为任意网格模型的层次细节模型的实时生成的提出作了良好的先期工作。1994年，Hamann提出了一种以面操作实现模型简化的方法[11]。该方法以三角面各顶点的主曲率判定模型中各三角面所处区域的平坦程度，并由此决定各三角面对原模型的重要程度。算法以各三角面的重要性的大小决定各三角面删除的先后。为避免对三角面删除所遗留的空洞进行复杂的三角化过程，算法采取了类似于边退化为顶点的方法来避免局部区域的复杂三角化过程。算法将所删除的三角面的顶点合并为一新的顶点，由此新顶点对应所删除三角面的三个顶点，按原顶点的连接关系即生成该局部区域的三角化模型。此后，研究人员又提出了基于面合并的模型简化方法[12]。虽然这些方法能有效地简化各种复杂模型，但所有这些方法由于必须对原模型大量数据进行逐个的判定且必须对简化后所遗留的空洞进行复杂的三角化过程，使得算法无法达到实时，尽管基于边蜕化的模型简化方法以及基于面操作的模型简化方法在避免复杂的三角化过程方面作了一定的改进。因而算法不得不预先产生原模型间断的简化模型空间，即预先生成满足不同几何精度的多个简化模型。这不仅带来了存储空间的耗费，而且由于绘制模型的不同必然带来图形画面的跳跃。为避免图形画面的跳跃，几何模型的复杂度在相邻帧之间应该是平滑过度的。即被控制的模型的三角面的数目应随视点的连续变化而连续的变化。视点的小变化不会也不应导致模型的大变化。这个性质将会避免动态显示中出现图形画面的跳跃。1995年，Hoppe在原有的边操作算法基础上提出了累进网格的概念[13]，首次较好地解决了模型简化方法在实际应用中所遇到的问题。该算法根据边蜕化简化操作的可逆性及边蜕化方法良好的局部拓扑维护性，将三维模型中每条边按照它们被删除后导致的几何误差大小排列，从小到大进行删除得到一个可逆的原模型的累边网格表示。而利用顶点分裂这一与模型简化操作——顶点合并相逆的过程来恢复模型简化所删除的信息。为了得到模型细节的删除信息，算法在模型简化的预计算中记录下边蜕化为新顶点这一简化过程中原顶点与新顶点的对应关系，并由预计算中记录下的每一简化过程得到一个由原模型的基本网格和一系列的简化信息组成的渐进网格表示模式。在实时绘制时，通过跟踪记录下的边蜕化为新顶点的对应关系，算法可以根据这一跟踪线索由基本网格模型逐步恢复所删除的模型细节，实时得到原模型连续精度的简化模型。该算法以边蜕化所导致的模型几何误差的大小指导模型简化的顺序，并由此生成几何误差由小到大的渐进网格模型。这个算法可生成连续细节层次，支持模型的递进传送和有选择精化，并且考虑到面片上色彩和纹理信息的处理[14]。此后，Isler基于以上算法特点，根据面删除以及边蜕化简化算法的特点，提出了一种实时的多分辩率方法[15]。该方法首先以围绕各顶点的三角面之间的夹角大小判定各顶点所处区域的平坦程度，并由此决定各三角面的视觉重要度。该方法根据三角面各顶点所处区域的平坦度决定三角面蜕化的方式，即是否此三角面蜕化为一新顶点或此三角面的一边蜕化为一新顶点。为减少计算，算法有三角面上的一顶点作为新顶点，从而避免了三角化过程。当然，由于复杂模型庞大的数据量，如果算法必须对各三角面作逐一的判定，算法是无法达到实时的。为避免对复杂模型的各个三角面逐一判定，算法采用了静态简化方法预先产生几个关键的简化模型，并对其中的三角面按照它们的视觉重要度进行排序。在实时绘制过程中，算法选择一个最少的但又比所需要的分辨率高的近似模型，按重要度从小到大地删除三角面直到刚满足当前精度为止。算法建立三角面删除队列，记录三角面在实时计算中最近被删除的信息，以此加速实时模型的简化，实时得到原模型连续精度的网格模型。1.4三维图形应用程序接口虚拟现实系统中的模型通常很复杂，需用3D图形加速卡来增加图形显示速度，因此，需要三维图形应用程序接口(3DAPI)。3DAPI是架设在3D图形应用程序和3D图形加速卡之间用于沟通的桥梁。随着计算机硬件技术的提高，低成本高性能的显示卡已十分普及，三维模型的显示采用硬件加速已十分普遍，基于硬件加速的接口语言如SGI公司OpenGL、Microsoft公司的Direct3D等已很成熟。对开发者来说，必须在开发工作开始前详细了解这些API的功能和优缺点，以便做出恰当的抉择。Direct3D是Microsoft于1996年6月发布的三维API，它为程序员提供了—个显示三维图形的与硬件无关的应用编辑接口，使软件开发者在不了解硬件的详细资料的状况下也能充分发挥硬件特性。Direct3D的核心是3D渲染引擎。它由3个单独的模块组成，即变换模块、照明模块和光栅化模块。Direct3D传送管线利用3个软件模块生成图像，这3个软件模块可在软件控制下交换位置，或对图形加速硬件传送数据和命令。变换模块对由4个可修改的状态注册器组成，即视口、视图矩阵、世界矩阵和投影矩阵，变换矩阵可对目标作几何变换。照明模块计算照明和颜色信息，它支持环境光源、直射光源、点光源和聚光灯光源，并且支持光照模型(单色和RGB)。光栅化使用前2个模块的输出来渲染场景，生成二维视图。Direct3D支持多线程环境，在该环境中不同的应用可同时对各自不同的窗口进行操作。Direct3D图形库是以COM接口形式提供的，比较复杂，稳定性差，且目前只在Windows平台上可用。Direct3D发展迅速，应用面主要是游戏方面，升级虽快，但前后版本的兼容性很差，暴露出了技术的成熟度问题。OpenGL(OpenGraphicsLibrary)即开放式图形库，是SGI公司推出的三维图形库。由于OpenGL的作用机制是客户(Client)服务器(Server)机制，由客户(用OpenGL绘制图形的应用程序)向服务器(OpenGL内核)发送OpenGL命令，服务器则负责解释这些命令。OpenGL的主要功能包括几何建模、坐标变换、颜色模式设置、光照和材质设置、图像处理、纹理映射、实时动画、交互技术等。OpenGL的函数OpenGL的函数虽然包括OpenGL核心函数、OpenGL实用库函数、辅助库函数、Windows专用函数、Win32API函数，多达几百个。但由于有一套非常规范的语法规则，应用起来很方便。这与Direct3D那种比较杂乱的语法规则相比，显然更加清晰明了。OpenGL可运行在Unix、WindowsXP、WindowsNT、Windows95以及Mac平台之上，具有很好的移植性，适于跨平台的应用开发，可以获得非常广泛的应用。OpenGL被设计成独立于硬件，独立于窗口系统的，在运行各种操作系统的各种计算机上都可用，并能在网络环境下以客户/服务器模式工作，是专业图形处理、科学计算等高端应用领域的标准图形库。自1992年OpenGL发布以来，OpenGL被广泛地应用于CAD/CAM/CAE、虚拟现实、医学图形处理、娱乐、广告、电视、特别是早期的游戏，成为一种名副其实的、开放的三维图形开发工具。OpenGL的规范由独立的OpenGL结构评审委员会负责管理，保证它的独立性、开放性、前瞻性和跨平台性；图形硬件加速厂商都以支持OpenGL为首要目标，这使得OpenGL成为首选的三维图形开发工具。1.5本文的主要工作本文主要在以下几个方面进行了探索和实践：(1)在查阅国内外相关文献的基础上，分析了已有网格简化算法的优缺点。(2)根据真实感图形绘制的有关理论，结合现有算法，提出视相关的多细节层次网格模型简化算法，结合网格模型细节层次的选择标准，利用视觉敏感度加大场景简化幅度。(3)利用空间八叉树建立场景模型的层次结构；将八叉树与图像包围盒四叉树结合，给出一种基于z-Buffer的快速消隐算法。(4)结合图形技术标准OpenGL，开发了一个加工设备快速绘制的原型系统。并给出了原型系统的总体结构，介绍了各模块的功能和实现。

2真实感图形的绘制技术作为一种人机交互技术，虚拟现实技术的最终目的是使用户置身于一个由计算机及其相关设备生成的虚拟环境中，使之产生身临其境感受的交互式视景仿真。一些专用硬件设备如头盔显示器、数据手套等的发明，为人类和计算机之间的信息传递提供了新的通道。视觉是人类感知外部世界的主要渠道，所获得的信息近80％是通过眼睛得到的[16]。要使用户对虚拟环境产生沉浸感，首先要求他所观察到的场景画面必须是立体的，即在立体眼镜和头盔显示器的左右眼显示器上同步放映具有给定视差的场景画面以产生立体视觉。其次，上述立体画面必须随用户视点和视线方向的变化或场景中景物的运动而实时刷新。由于当前虚拟环境中所涉及的景物包含数十万甚至上百万个多边形，虚拟现实系统的这两个基本要求对图形绘制技术提出了严峻的挑战。传统真实感图形绘制算法追求的是图形的真实感和高质量，而对每帧画面的绘制速度并没有严格的限制。而虚拟现实系统要求的图形实时绘制技术本质上是一种实时计算技术，即要求算法必须在给定时间内完成对场景的绘制。由于目前图形软硬件还无法实现日益复杂的场景的高度真实感画面的实时绘制，往往通过损失图形质量来加快画面绘制的速度。本章从真实感图形的基本原理出发，介绍当前图形实时绘制技术的主流算法。2.1虚拟场景表示在过去的30年中，几何造型技术得到了极大的发展，使得用户可以方便、逼真的构造各种工业产品和自然景物，从而为虚拟场景的描述奠定了基础。鉴于曲面绘制的复杂性，一般的图形绘制系统通常将连续曲面离散为一系列的多边形或三角形，并直接绘制这些多边形得到最终画面。尽管这些多边形逼近损失了景物表示的精度，但这种逼近表示具有下述良好的性质：●可借助硬件来快速绘制。●形状简单，便于计算和处理。●以统一的方式描述任意复杂形状的景物。多边形网格模型可由设计者交互生成，或者通过三维激光扫描仪在实物表面上测得一系列离散点后由算法生成，或者从某种隐式扫描中自动生成，或者由参数曲面离散得到。绘制多面体所需信息通常以层次结构存储。每个面由指向多边形表的指针来索引，而每个多边形则由指向顶点表的指针来定义，多边形的顶点通常只存储一次。每个多边形需存储的信息包含：(1)多边形的顶点表。每个顶点处存储其在所属景物局部坐标系中的三维坐标。(2)顶点的法向量表。每一顶点处的法向量记录景物表面在该采样点处的真实法向量。(3)多边形的法向量。即多边形所在平面的法向量，在背面剔除中要用到该信息。上述表示的不足在于，相邻多边形的共享边在上述数据结构中没有得到显式表达。这使得同一条边在绘制过程中可能被处理两次。由于许多传统的多边形绘制算法都把多边形当成绘制对象，采用上述结构可能导致部分计算重复。另一种方法是基于边的绘制方法。该方法采用一系列多边形的边而不是多边形本身来表示一个物体，边数组每个元素含有４个指针，分别指向对应边的两个顶点和它邻接的两个多边形法向量。该方法表示物体更有效，数据结构更简单。例如，一个多边形可能有任意数目的顶点，但每条边只有两个顶点并有两个多边形共享，共享的边在数据结构中只保存和处理一次。基于边表示方法的缺点是其图形绘制只能采用基于扫描线的绘制算法。场景的实时绘制大多由硬件z缓存来完成。许多图形加速卡提供硬件z缓存消隐功能，每秒钟可处理三角形的数目目前已经达到几百万个，并且这个数字仍呈快速上升的趋势，因此CPU应以最快的速度把景物数据传输给图形加速卡。一些图形标准如OpenGL等均提供可快速传输多边形网格模型的三角形条和四边形条结构。由于这种结构所需传输的数据比逐个传输三角形或四边形要少，因而，无论绘制由硬件还是由软件完成，这种结构的执行效率均较高。例如，输入ｎ个顶点，采用如图所示的多边形网格可传输ｎ-2个三角形。图2.1：18个顶点构成16个三角形2.2基本消隐技术图2.1：18个顶点构成16个三角形在真实感图形生成中，一个重要的问题是：给定视点和视线方向，决定场景中哪些物体的表面是可见的，哪些是被遮挡而不可见的。这一问题简称为场景的消隐。所有隐藏面消除算法都涉及各景物表面离视点远近的排序。一个物体离视点越远，它越有可能被另一个离视点较近的物体遮挡。因此，消隐可看成是一个排序问题，消隐算法很大程度上取决于排序的效率[8]。消隐算法按其实现方式可分为景物空间消隐算法和图像空间消隐算法两大类。前者直接在景物空间（摄像机坐标系）中确定视点不可见的表面区域，并将他们表达成同原表面一致的数据结构；而后者则以屏幕像素为采样单位，确定投影于每一像素的可见表面区域，并将其颜色作为该像素的显示亮度。景物空间消隐算法有表优先级算法、空间二叉树算法、Weiler-Atherton算法等。表优先算法从各景物表面多边形深度排序开始，按场景中各景物表面离视点的距离确定一个深度优先级表。若场景中任何两个表面在深度上均不重叠，则各表面的优先级顺序可完全确定。表优先级算法从离视点最远的景物表面开始，一次计算每一表面的光亮度并将其写入帧缓冲器，表中离视点较近的景物表面的光亮度覆盖帧缓冲器原有的内容，从而实现了景物的消隐。由于算法的过程与画家创作油画类似，该方法亦称为画家算法。空间二叉树算法是一种决定场景可见性的有效方法[17,18,19]。与画家类似，该算法也是从远到近往屏幕覆盖画面元素。该算法非常适合在场景不变、视点变化的场景中对景物表面作快速排序。建立空间二叉树的过程实际上是对场景所含景物表面片递归的进行二叉分类的过程。先在场景中选取一个剖分平面将景物空间分割成两个半空间，它相应地把场景中的景物分成两组。相对于视线方向，一组景物位于剖分面的前面，一组景物位于剖分面的后面。剖分面将与其相交的景物分割成一部分在剖分面前，另一部分在剖分面后。然后我们再用另一平面对所生成的两个子空间继续进行分割，并对每一个子空间所含景物进行分类。上述空间剖分和景物分类的过程递归进行，直至每一个子空间所含景物数少于给定的阈值为止。上述分割过程可表示成一棵空间二叉树，在该树中，景物位于叶子结点，左子树为场景中位于分割平面前面的景物，右子树为场景中位于分割平面后面的景物。对于由多边形表面组成的场景，通常选择某一多边形所在平面作为分割平面。一旦空间二叉树构造完成，则依据当前视点所在的位置，对场景中每一分割平面所生成的两个子空间进行分类。其中包含视点的子空间标识为“front”，位于分割平面另一侧的子空间标识为“back”，然后，递归搜索场景二叉树，优先绘制标识为“back”的子空间所含景物。Weiler-Atherton消隐算法[20]是基于Weiler-Atherton多边形裁剪操作，可在景物空间给定精度进行计算，输出结果仍为多边形，因此适合于作隐藏线和隐藏面消除。隐藏面是场景中的表面或表面的一部分，它们位于画面上的可见面之后，其在画面上的投影区域完全为可见面的投影所覆盖。因而，我们可以先将变换到屏幕坐标系中的景物按z向排序，位于最前面的景物表面必为可见面，取该可见面为裁剪窗口，对排列在其后面的景物表面进行裁剪。位于裁剪窗口之内的景物表面后表面的一部分必为当前视点的隐藏面，可以消去。位于裁剪窗口以外的景物表面组成外裁剪结果多边形表，取该表中最前面表面为裁剪窗口，继续对表中其他景物表面继续裁剪。上述过程递归进行，直到外裁剪结果多边形表为空。图像空间消隐算法有z缓冲器算法、扫描线算法、光线跟踪算法等。z缓冲器算法[21]是一种最简单的隐藏面消除算法，已成为图形学中的标准算法。z缓冲器是帧缓冲器概念的简单推广，用来存储画面上每一像素内可见表面采样点的深度，是一个独立的深度缓冲器。绘制时，先将待处理的景物表面上的采样点变换到图像空间，计算其深度值z，并根据采样点在屏幕上的投影位置，将z值与以存储在z缓冲器中相应像素处的原可见点的深度值进行比较。如果该采样点位于z缓冲器所记录的可见点之前，则将该采样点处的表面光亮度填入帧缓冲器相应像素，同时用其深度值更新z缓冲器存储的深度值。否则，不作任何改动。该算法实质上是根据景物表面各采样点在图像空间中的x、y坐标确定其所属像素，对于投影于同一像素的采样点，查找具有最小z值的可见点。该算法的最大优点是算法简单，可轻易消除隐藏面及显示复杂曲面之间的交线，而计算量仅仅呈线性复杂度。由于景物表面上可见点可按任意次序写入帧缓冲器和z缓冲器，故无需对组成场景的各景物面片作深度优先级排序，从而省去了深度预排序时间。目前，在许多中高档的图形工作站上都配置有硬件实现的z缓冲器算法，以便于图形的快速生成和实时显示。但是z缓冲器算法是一种点采样算法，在实现反走样、透明和半透明等效果方面会出现一定的困难和产生较大的开销。z缓冲器算法的另一个缺点是庞大的内存耗费。若将屏幕空间划分为4、16或更多的子正方形或带状区域，则所需的存储量可以减少。当对每一个扫描行设置ｚ缓冲器时可使存储量减至最小，这就是扫描线缓冲器算法。在扫描线z缓冲器算法[8]中，z缓冲器所需的存储量仅为1×水平显示分辨率×深度存储位。z缓冲器的深度位数取决于z的取值范围。该算法原理也比较简单，对于每一条扫描线，帧缓冲器中各像素点取背景属性作为初始值，z缓冲器中个像素的初始值为最大z值。然后求取这条扫描线与场景表面在屏幕上的二维投影之间的交点。显然，这些交点都是成对出现的。逐个考虑扫描线上位于一对交点之间的各像素，将每一像素处表面采样点的深度值与z缓冲器中该位置上原存储的深度值进行比较。若表面采样点的深度值小于z缓冲器中的原有值，则该采样点可见，计算表面在该点处的光亮度值，并写入与场景表面在帧缓冲器的相应像素中，同时更新z缓冲器中的原存储值。当场景中所有表面处理完毕后，扫描线帧缓冲器中的内容即为画面在此扫描线的消隐结果。由于消隐过程涉及对场景中景物的排序，因而它是真实感图形绘制过程中耗时最多的部分。尽管z缓冲器算法是唯一具有线性计算复杂度的消隐算法，且采用硬件实现，但由于硬件z缓冲器算法需要逐个面片进行扫描转换和逐个像素进行深度比较，因而对于高度复杂的场景，该算法仍难以满足实时绘制的要求。本文将着重考虑利用相邻帧画面的可见性连贯性及图像、景物空间连贯性来加速消隐的过程。2.3纹理映射在现实世界中的物体，其表面往往有多种表面细节，即纹理。纹理分成两种[22]：一种称为颜色纹理，如机器外壳表面有文字说明它的名称、型号，家具表面有木纹，建筑物墙壁上有装饰图案等，这是通过颜色色彩或明暗度的变化体现出来的表面细节。另一种称为几何纹理，是由于不规则的细小凹凸造成的，如桔子皮表面的皱纹和未磨光石材表面的凹痕等。生成颜色纹理的一般方法是在一平面区域（即纹理空间）上预先定义纹理图案，然后建立物体表面的点与纹理空间的点之间的对应（即映射）。当物体表面的可见点确定之后，以纹理空间的对应点的值乘以亮度值，就可以把纹理图案附到物体的表面上。也可以用类似的方法给物体表面产生凸凹不平的几何纹理。为使生成的物体图形具有真实感，采用许多算法进行消隐处理以产生明暗效应，建立颜色模型、光照模型和光线跟踪等图形生成技术。为了能用计算机模拟物体各种表面细节，纹理映射就成为真实感图形生成中必不可少的方法。纹理映射过程是先在一个二维空间(又称纹理空间)中制作纹理图案，然后确定三维空间中物体表面的点与纹理空间中点的映射关系，按一定算法将纹理空间的纹理图案映射到三维物体上。2.3.1纹理图案的生成纹理定义一般采用连续法和离散法两种方式[21]。连续法把映射函数定义为一个二元函数，函数的定义域就是纹理空间。离散法把纹理定义在一个二维数组中，代表纹理空间中行间隔、列间隔固定的一组网络点上的的纹理数据——该点的颜色值和明暗度。网格点之间的其他纹理值可通过网格点上值的插值获得。通过纹理空间与物体空间之间的坐标变换，可把纹理映射到物体表面。(1)用连续法生成纹理图案的方法纹理一般定义在单位正方形区域(0≤u≤1，0≤v≤1,)之上，称为纹理空间。理论上，任何定义在此空间上的函数可以作为纹理函数。但在实际应用中，往往采用一些特殊的函数，以便模拟现实生活中常见的一些纹理。其中0<a<b<1，[X]表示小于X的最大整数，用这个纹理函数可以模拟国际象棋盘上黑白相间的方格。又例如可用以下函数来模拟粗布纹理其中A为[0,1]上的随机变量，p、q为频率系数，u、v为函数参数。这种方法是由计算机根据纹理函数自动计算纹理图案的数据，以计算出在不同光源和视点情况下纹理的颜色和形状数据。因此，将这些数据进行纹理映射，可生成任意视点和光源位置的真实感图形。(2)利用离散的数字化图像的方法将纹理信息定义在一个二维数组中，数组元素代表纹理空间中行间隔、列间隔确定的一组网格点上的纹理数据。最直接有效的方法是用拍摄的、反映实际物体的纹理的照片，再用数码摄像机或者扫描仪输入将图像数字化，作为纹理图案。但是由于是在某种视点和光源的情况下得到纹理图案，可能与三维图形制作时的视点和光源处于不同的状态，所以纹理映射往往会产生不自然的图像。2.3.2纹理映射的原理纹理映射既能增加绘制图像的真实性、丰富度，又不影响图像的基本几何复杂度，得到了广泛的应用。纹理映射的基本原理可描述如下。纹理是一个平面的区域与指定的颜色(或光的强度)之间的映射。区域中的每个点都有自己的颜色值，纹理只是离散的图像，它是统计了颜色值的二维阵列。纹理映射的目标是通过一种可行的手段给模型表面上的点赋值[23]。纹理映射涉及纹理、景物和屏幕三个空间之间的映射，把屏幕空间中的象素映射到物体表面，然后从景物空间向纹理空间映射，即确定景物空间中的坐标所对应的纹理坐标[24]。一般的纹理映射过程如图2.2所示。2.4图形生成的加速方法综述就计算机图形学发展而言，起关键作用的无疑是图形硬件加速器的发展。高性能的图形工作站和高度并行的图形处理硬件及软件体系结构是实现图形实时生成的重要保证。但今天的图形工作站性能距离VR的充足需求仍相当遥远。换句话说，当前图形生成的速度相对于通常虚拟环境的规模来说仍存在相当大的差距。例如，UCBerkely大学的计算机科学大楼的计算机模型具有1.4兆个多边形的数据；帝国大厦的计算机模型则由167兆个多边形组成；而波音公司推出的完全由计算机设计的波音777是一个有着500兆个多边形计算机建模模型。这些应用模型的复杂程度往往超过当前图形工作站的实时处理能力。考虑到VR对场景复杂度几乎无限制的要求，在VR高质量图形的实时生成要求下，如何从软件着手，加速虚拟环境的生成，成为VR图形生成的主要目标。我们知道，图形硬件流水线划分为几何处理和绘制两个阶段。从计算机开始遍历整个虚拟场景到最终生成虚拟场景的图形画面，虚拟环境的图形生成的时间耗费大致包括：主机遍历时间、几何处理时间以及绘制时间[25]。几何处理时间可以由所要处理的图形单元的顶点数目决定；而绘制时间则由所绘制面片所覆盖的像素总数决定。虚拟环境中图形生成的时间由这三个阶段组成的流水线中时间耗费最长的阶段决定。如何降低这三个阶段的时间耗费，除了利用图形硬件本身的功能，如利用三角面串以减少几何处理阶段的时间耗费，尽量减少图形特性的设置以减少几何计算的时间等措施外，图形生成加速的方法大致可以分为可见性的判定、细节层次模型技术、动态图象加速技术以及预计算。下面就这几个方面作简单的介绍。2.4.1可见性的判定由于视线方向性、视角的局限性以及物体相互遮挡，人眼所看到的往往只是场景中的一部分。所谓可见性的判定即利用物体空间的相关性、图象空间的相关性和时间空间的相关性加快可见面的判定，减小绘制深度[8]。物体空间的相关性即利用物体空间的分割预先确定景物在空间的分布情况以加速可见面的判定。图象空间的相关性即利用当前已绘制场景决定可见面的判定。时间空间的相关性即利用相邻帧可见面的连贯性加速可见面的判定。早期的可见性判定主要是指视见体的判定。这一时期的可见性判定主要是利用场景的有效组织来加快位于视见体内物体的判定。七十年代末发展起来的物体分层次表示(hierachicalrepresentation)是这一时期的典型代表。层次表示的主要方法是包围盒技术和八叉树技术。这两种方法的主要特点是将场景组织成为一棵树，充分利用空间连贯性以加速场景的遍历，从而大大地减少了画面绘制过程的时间复杂度。此后，Fuchs以物体的半空间表示将其空间一分为二，将场景组织为二叉树(BSP)的结构[26]。此方法可利用已建立起来的二叉树很快地决定相对视点面的前后排列，加快由于物体相互遮挡所产生的可见面的判定。但该方法由于以面作为划分单元，因而会产生大量新的面片。鉴于以上方法的特点，Teller基于建筑CAD的特点，探索了一种基于“房间”结构的可见性预处理方法[27]。此算法以建筑模型中主要的遮挡面为空间划分面，从而将建筑模型划分为以房间为基本单位(cell)的数据模型。在空间划分的基础上，根据基本单位之间共有的可见口(portal)，如门、窗等，建立起单位之间的邻接图。考虑到实时漫游时观察点的任意性，算法定义单位的可见性为观察者所能看到的区域，即一个观察者在此单位中任一位置、任一方向所能看到的区域。由于单位之间可见就意味着有一条光线能无遮挡地从此单位达到彼单位。算法根据单位之间的邻接图，通过深度遍历建立起单位之间的可见口序列(portalsequence)，从而得到单位之间的可见性集、单位对景物的可见性集。在实时漫游时，算法利用预计算的结果实施内存与外存的调度管理，并从所得的集计算视点对单位、视点对景物的可见性集合，有效地加速了可见性的计算。但本算法的预计算比较复杂，且目前局限于轴向的建筑模型。不论哪种空间划分技术，都仅仅只利用物体空间的相关性来加快可见性的判定。传统的z缓冲器算法利用同一象素的深度信息，决定可见面的判定，有效地利用了图像空间的相关性来加快可见性的判定。但z缓冲器算法并没有利用空间的相关性来加速可见性的判定。在利用物体空间、图象空间和时间空间相关性方面，Greene提出了非常有创意性的思想[28]。该方法利用绘制画面的z缓冲存储器，通过物体空间和图象空间两个结构的建立，提出了一个利用物体空间、图象空间和时间空间相关性的算法。我们知道，八叉树中一个单元如其六个面不可见，则此单元所包物体不可见。那么如何判定此单元不可见?Greene利用已绘制场景的z缓冲器结果，作为z缓冲器层次结构第一级，将上一级数据压缩一倍(即取每相邻四个数据的最大值)就得到第二级数据。依此压缩下去，就得到图象空间的层次结构。可以看出，层次结构中的任一数值都对应于屏幕空间上大小不同区域的最大z值。以八叉树中一单元在屏幕空间所在区域的最大z与此单元的最小z值比较，如果此屏幕空间的最大z值比此单元的最小z值小，那么此单元不可见。否则将此单元分为四个子空间，再将这四个子空间的最小z值与所对应的屏幕空间区域的最大z值分别进行比较，直到子空间的最小z值大于相应屏幕空间区域的最大z值或者相应屏幕空间区域已对应屏幕一象素。虽然此算法的实施依赖于可否对z缓冲器进行访问，但其方法在利用物体空间、图象空间和时间空间一致性方面作了很有效的尝试，算法的实施非常便利于并行计算。2.4.2细节层次模型所谓细节层次模型方法即为每个物体建立多个相似的模型，不同的模型对物体的细节描述不同，对物体细节的描述越精细，模型越复杂。由于今天高精度的遥感测绘技术以及三维扫描技术，复杂物体的建模已不难获取。这些模型通常由大量密集的数据组成。虽然计算机的处理速度在不断提高，存储空间也在不断扩大，但仍远远赶不上模型复杂度的增长，如此庞大的模型存储、显示、传输上都面临巨大的困难，由此，对细节层次(LoD)模型的研究应运而生。层次模型由在不同尺度上逼近原始复杂模型的一系列模型组成。在具体应用中，可根据需要选用相应的模型进行显示或传输。LoD模型具有广泛的应用前景，在实时图象通信、碰撞检测、限时图形绘制[29]和虚拟现实等领域中已显示其强大的生命力。特别是在虚拟现实等交互式计算机图形应用领域中，细节层次模型技术已成为图形实时生成的关键技术。LoD模型技术改变了传统的图象质量越精细越好的片面观点，而是通过对场景的复杂度以及图形系统的综合评判，以一定的算法为各物体选择适当的细节模型，从而使图形显示在保证实时恒定的帧频率的前提下，最大程度地提高视觉效果。2.4.3动态图像加速技术利用动态绘制产生的图形画面来加速整个虚拟场景的图形画面的实时生成是十几年来发展起来的一种基于图形图象混合绘制的图形生成加速方法。该方法充分利用相邻帧画面的相关性加速虚拟场景的图形生成。算法基于这样一个事实：即相对于一个观察者，一个场景的某些部分在一段时间内在该观察者分辨范围内是不变的，如远处的树木、高楼。动态图像加速技术即利用这种相关性，动态几何绘制生成并存储虚拟场景这些区域的生成图形画面。在以后帧，根据当前观察者的实际位置以一定的误差判定决定存储的该区域的图形画面是否有效。如误差允许，则以该图像作为当前帧观察者所看到的该区域的图形画面。最后以几何绘制和已有的各区域的图形画面生成整个虚拟场景的图形画面。该方法适合于任意复杂的虚拟场景。根据如何由已有的图形画面最后生成各区域当前帧的图形画面，该方法又可分为基于纹理映射的动态图像加速法和基于图像合成的动态图像加速法。基于纹理映射的图像加速法实际上早已存在。在早期，为加强图形画面的真实性而又尽量减少图形生成的负担，研究人员通常采用一种叫作Billboard的技术[30]来生成一些非常复杂而又具有一定对称性的自然物，如树木。Billboard是这样一个带有纹理的半透明的长方形。其纹理图像为该Billboard所代表的物体的影象，即以带有该物体影象的长方形代替该物体生成该物体的图形画面。Billboard放置于所代表物体的位置中心，并随用户的运动而转动，始终面对用户。早期的Billboard的物体的影象是预先得到的，且只对具有一定对称性的物体而言。Shade将此方法推广[31]，实时动态地生成任意物体的图形画面作为该物体的影象存储起来。只要误差允许，就可以以该影象作为以后帧该物体的影象映射到相应的面上生成观察者当前帧所看到的该物体的图形画面。只是该映射面不再随用户的移动而转动。为了最大程度地减轻图形生成的负担，该算法进一步将以上思想推广应用到整个虚拟场景的一些区域。即认为在一段时间内该区域相对一个观察者在其分辨范围内其图形画面是不变的。为此，算法以二叉树建立整个虚拟场景的层次结构。在实时绘制时，算法首先遍历二叉树，根据当前观察者的位置决定该结点存储的相应于虚拟场景某区域的影象是否仍有效。如无效，则继续遍历该结点的前后子树，并以当前观察者的运动参数及误差精度估算以决定是否生成此结点当前的图形画面以作为以后帧的影象；否则，以该结点所存储的该区域的影象生成该区域当前的图形画面。此算法以包围该结点的四方体内各空间点最大角度变化来计算由于观察者运动所产生的图形画面的误差，并以此决定所存储的图像是否有效。基于图像合成的图像加速技术[32]是Regan提出的另一种动态图像加速技术。该方法根据当前观察者与物体的相对运动以及误差精度赋予各物体一定的绘制速率。算法由不同速率绘制生成的各物体的图形画面根据深度值的比较最后生成整个虚拟场景的图形画面。在算法中，作者提出了一种崭新的图形生成流水线框架，最大限度地减少由于随视线方向变化观察者所观察到的图形画面变化所产生的图形生成延迟。Regan认为，人的视线变化是引起相邻帧画面变化的最大原因。如果能将视线方向的最后定位与图形绘制过程分开，而仅在确定知道人的视线方向后进行一个视见窗的映射变换，那么图形绘制就可以最大限度地减少由于设备定位所引起的延迟。从而也最大限度地减少由于视线方向变化所引起的图形绘制开销。作者将此思想与图像合成方法相结合，从而免除了仅仅因为视线方向变化所引起的图形画面的重新绘制，大大减轻了图形系统的绘制开销。该算法试验统计数据表明一个场景中大概只有1～2％的物体需要每秒60帧的绘制速度，而大部分的物体只需每秒重新生成3.75～7.5次。为了使所绘制生成的图形画面包括观察者在所有观察方向上所能看到的所有的图形画面，该算法利用基于图象绘制生成虚拟场景的基本原理，以立方体的六个投影面绘制生成包括观察者所有的观察方向所能观察到的图形画面，只需一个映射变换就能生成当前观察者观察方向所看到的画面。动态图象加速技术结合了当前加速生成虚拟环境的LoD技术、场景划分技术以及静态图象绘制技术。虽然，动态图象生成技术的研究尚处于初步阶段，但其潜在能力已得到人们的注意。2.4.4脱机计算脱机计算是减轻计算机实时计算负载的常用方法之一。由于VR系统是一个多任务的模拟系统，有必要尽可能地将一些可预先计算好的结果预先计算并贮存在相应的结构中。这其中包括全局光照模型、动态模型的计算等。就图形生成质量而言，VR所期待的目标自然是高质量真实感的逼真图形，并具有各种自然场景的复杂图形画面。但如前所述，图形处理的硬件能力尚远远满足不了VR的需求，因而在现今的条件下，实时的真实感图形生成几乎是完全不可能的。对于大多数的VR应用来说，仍只是采用简单的局部光照模型，且在硬件部件的支持下实现质量并不高的图形显示。但从将来的发展来看，使用全局光照模型和显示具有复杂场景的真实感图形必然是VR所应追求的目标。就全局光照模型来说，光线跟踪技术由于其计算量大，且因其生成结果固有的与视点相关而很难进行预计算，因而这一技术几乎很难应用于VR。与此相对，辐射度技术因其计算结果与视点无关，大量计算可作为预计算，因而很可能更广泛地应用于真实感图形生成。自1984年C.M.Goral等从热辐射工程中引进了辐射度方法，辐射度技术已得到了很大的发展。特别是逐步求精算法的提出，大大加快了辐射度技术的速度，使得辐射度技术成为真正实用的全局光照模型技术。进入90年代后，辐射度技术进一步走向实用。多层次划分技术利用N-body问题的方法将传统辐射度方法的时空复杂度从o(n2)降为o(n)，并根据用户定义的误差，自动建立起面片的划分，进一步提高了辐射度技术的实用性。1994年，Smits在将视点参数引进辐射度计算中[33]，建立起与视点范围有关的importance函数，将视点与辐射度技术结合起来，使辐射度技术向实时计算迈进一步。物体的动态模拟模型的计算是VR的一大任务。在这些动态模拟中包括一些较有规律的动态特征的模拟，如具有动画特征的随时间变化而变化的动态模型和一些基于特定事件的动态事件的模拟。它们的物理模型的各种参数并不由于各种偶然性发生变化，如物体的独自运动。为减少实时动态模拟计算的负载，可以将这些动态描述作脱机计算，并作为实时计算的输入。2.5本章小结本章首先介绍了虚拟场景表示的基本概念，阐述了景物空间消隐算法和图像空间消隐算法，并说明了纹理定义方法，论述了纹理映射原理；最后给出了图形加速绘制的几种算法。

3多细节层次模型简化算法研究通常，图形绘制速度与模型中的三角片数目成反比。随着描述场景中几何模型的三角片数目的增多，所绘制的图形质量越来越高，而绘制速度也越来越慢，从而形成了一对矛盾。尽管图形绘制系统的性能在近些年有明显提高，但是总会有一些场景太过复杂，现有的软硬件不能满足实时绘制的要求。而实时绘制是虚拟现实系统的一项基本要求。为了实现复杂模型的快速绘制，加速画面生成，解决模型的实时显示问题，从而实现人与虚拟环境实时交互，网格简化和多细节层次模型(LoD)技术相继应运而生。LoD技术由Clark于1976年首次提出，其主要思想是首先将复杂模型简化为一系列不同分辨率的逼近模型，然后根据场景和视点的不同切换适当的模型进行绘制，以此加速图形的显示[34]。LoD方法的基本思想是：对场景中的不同物体或物体的不同部分，采用不同的细节绘制方法，在绘制时，如果一个物体离视点比较远，或者这个物体比较小，就可以用较粗的LoD模型绘制。反之，如果一个物体离视点比较近，或者物体比较大，就必须用较精细的LoD模型来绘制。同样，如果场景中有运动的物体，也可以采用类似的方法，对运动速度快或处于运动中的物体，采用较粗的LoD，而对于静止的物体，采用较精细的LoD。显然，LoD利用了人的视觉特性。为物体提供不同的LoD描述是控制场景复杂度和加速特性绘制速度的一个非常有效的方法。近20年来，国内外提出了多种网格模型简化方法，包括顶点删除、三角形删除、边折叠、三角形折叠和近平面合并等。国内研究人员近些年也开展了一些卓有成效的研究工作[35,36,37,38]，对已有多边形网格算法进行改进或提出新的多边形网格模型简化方法。本文在Luebke的视点相关的LoD技术[39]的基础上，考虑到人眼对处于不同区域的模型细节的不同分辨能力，提出一种利用视觉敏感度加快图形的绘制速度的网格简化方法。3.1三维图形显示中的一些概念场景坐标系：物体的造型总是在某个坐标系中进行的，该坐标系就称之为场景坐标系。视点坐标系：视点坐标系的原点是视点（即场景的观察点），其正z轴方向取为视线方向。定义过视点且垂直于视线方向的平面为视平面。取景变换：由于三维场景是在场景坐标系中建立的，但屏幕上显示的是在给定视点和视线方向下，三维景物在垂直于视线方向的二维成象平面（即屏幕）上的投影。取景变换就是将几何对象的三维坐标转换到屏幕上的像素坐标所需进行的一系列的坐标变换。在视平面中，选择垂直向上的方向为y轴方向，x轴方向由z轴方向和y轴方向叉积获得。屏幕：为真实模拟从给定视点观察场景所产生的透视效果，场景中的所有景物最后都要通过透视变换变换到屏幕上。屏幕是垂直于视线方向、位于正z轴上，与视点距离为D的投影平面上的一个矩形区域。该区域的中心O为视线与成像平面的交点(图3.1)。成像平面（屏幕）成像平面（屏幕）视点CP’PQDO图3.1透视变换示意图xeyezeze=Dze=F图3.2视域四棱锥示意图视域四棱锥：以视点为顶点，连接视点与屏幕四角点的连线为交边的四棱锥为视域四棱锥。场景中所有投影在屏幕上的景物都位于视域四棱锥中。考虑到所有待绘制的景物必须位于投影屏幕之后，并假设与视点相距足够远的景物在绘制时不予处理，则可定义视域四棱锥的z向近裁剪平面和远裁剪平面分别为：Ze＝D， Ze＝F经z向裁剪后的视域四棱锥转化为一棱台（图3.2），图中所示即为视点坐标系中的视域四棱锥。3.2视相关的网格动态简化算法与视点无关的LoD技术要预先生成并存储多个简化模型，一方面需要很多存储空间；另一方面，当随着视点变化在不同精细程度的模型间切换时会产生视觉效果的跳变。与视点相关的LoD技术则根据视点动态地生成简化模型，可以保证模型连续平滑地过渡，不会产生视觉效果的跳变。国内外已有许多学者对网格简化方法开展了一些卓有成效的研究工作[39,40,41]。在LoD中，通过对场景中每个图形对象的重要性进行分析，使得最重要的图形对象进行较高质量的绘制，而不重要的图形对象则采用较低质量的绘制。在保证图形实时显示速度的前提下，尽可能地提高视觉效果。即一个图形对象越重要，其对观察者所观察到的画面质量贡献越大；图形对象的重要性取决于对视觉效果的贡献程度。例如，若一个图形对象离视点很近，或位于视线方向上，相对而言，它应具有比其它图形对象更详细的细节、更好的显示效果[42]。衡量视觉效果是一个非常复杂的问题，它涉及到视觉生理学和心理学。在实际应用中，一般根据经验，将图形对象重要性的评价归结为以下几个因素：视觉敏感度：指人眼对图形对象的注意程度。描述了图形对象偏离人眼视线方向的程度。显然，视线周围的图形对象应具有更详尽的细节。如图3.3所示，视锥体O中，即使三角片A与B在屏幕上的投影大小一样，人眼对A和B的敏感度也是不同的，显然，人眼对靠近视线OO1的三角片B的敏感度更高。Funkhouser等人的算法根据图形对象重心距屏幕中心的距离的增加逐渐降低图形对象屏幕投影的权值[43]。图图3.3视觉敏感度成像平面（屏幕）O1BγAO投影面积：指图形对象在屏幕上投影所占面积。同样情况下，面积越大，图形对象对显示效果的贡献越大。在现存的LoD算法中，面积通常用图形对象的平均多边形所占象素数量来计算[44]，或用图形对象距视点的距离来计算[45]。为此，本文提出了一种动态层次结构简化方法。该方法可适用于任意的网格场景，通过一种层次方式动态聚合网格顶点，简化过程能够连续搜索这个层次以获得合适的细节层次用于显示。在此基础上，考虑到人眼对处于不同区域的网格细节具有不同分辨能力（对于偏离视线区域部分，人眼的视觉分辨力将急速下降），为提高网格的动态生成速度，充分利用人的视觉特点，对处于视锥中网格的不同区域在屏幕上赋予不同的显示精度，最大限度地减少网格的面片数量，从而降低绘制的复杂程度，加快场景绘制速度。本文在网格简化算法中考虑视觉敏感度的因素：将视觉敏感度与投影面积二者有效的结合（见3.2.3节），将它们作为网格细节的重要度评价尺度，有效的加大了网格的简化。该算法主要针对大规模场景可视化的需求而设计的。用一棵八叉树表示整个景物空间，即将景物空间递归剖分成一系列子空间，按每一子空间对顶点的包含关系将场景几何结构组织成一棵顶点树，并通过动态查询树结点来生成简化场景模型。本文将在第四章详细描述八叉树的建立过程。算法通过顶点合并的方式进行网格简化，由于三角片相对其他多边形更具有稳定性，而且可用于大多数网格简化算法，因此，假设所有网格模型均是由三角片组成的。通过一棵顶点树记录整个细节层次模型中可能的顶点合并操作。一个结点的顶点合并操作将结点内的所有顶点合并成单个顶点，并删除那些已经合并的三角片，称为折叠结点。同样，一个结点可通过单个顶点展开为一颗顶点子树。顶点树仅仅包含模型中顶点和三角片的信息。算法按照用户指定的条件根据视点的运动情况来进行结点折叠或展开。在该模式中，使用者在改变视点与网格模型的相对位置之前设定一个屏幕显示阈值（如四个像素）。每一个结点在屏幕上显示的范围都受到监测：当视点变化时，顶点树上的某些低于四个像素阈值的结点会明显收缩。这些结点收缩并从场景中删除相应的三角片。而其他结点会将它的子结点展开，并将新的顶点和三角片加入显示列表。调整阈值大小可让使用者能够控制简化程度并在逼真度和性能上保持较佳的平衡。本方法的实质是顶点树的折叠和展开，其简化准则将在3.2.3节中详细阐述。3.2.1结点的折叠和展开顶点树的根结点表示整个模型，每个叶子结点分别表示原始模型中的单个顶点，内结点表示将原始模型中的多个顶点合并成的单个顶点。如果表示顶点V的叶子结点P11是结点P的子孙结点，则称结点P包含原始模型中的顶点V(图3.4)。因此，顶点树中的每一个结点都包含原始模型中的一个顶点子集；根结点则包含整个模型中的所有顶点。如果一个结点至少包含原始模型中的某个三角片的一个顶点，则它包含该三角片。PPP1P11………P18P2…P8P88P81…………图3.4结点P与顶点V包含关系示意图（叶子结点P11表示顶点V）将几个顶点聚合的折叠操作与展开结点的操作是一个互逆过程。为简便起见，假设一个结点必须在它的子结点折叠后才能被折叠；这个假定将某一个结点所包含的所有的顶点合并过程简化到只需合并该结点的子结点到该结点。同样，可展开一个其父结点已展开的结点，也可将一个结点仅分裂成其子结点而不是结点所包含的所有顶点。根据上述定义，折叠和展开其实仅仅是对顶点树进行渐近改变的局部操作。折叠和展开操作必然会影响一些三角片。一组为结点相关三角片(relativetris)，它们在折叠和展开操作时将改变形状。另一组为结点子三角片(subtris)在结点折叠时被删除，在结点展开时重新显示。因此结点相关三角片和结点子三角片不依赖于其他结点的状态，他们能够预先计算并在运行时快速访问。如图3.5所示，△V1V3V4、△V4V3V8、△V7V8V6均为结点相关三角片，△V1V4V5、△V4V7V5、△V7V6V5、△V4V8V7均为结点子三角片。VV1V5V6V10V9V2V4V3V7V8PV1V6V10V9V2V3V8折叠结点P图