（计算机软件与理论专业论文）改进的图形管道与细节层次的实现.pdf

硕士论文：改进的图形管道与细节层次的实现 摘要 人们对于计算机的一个最大理想就是希望计算机有一天可以拥有足够强的 计算和处理能力。事实上，甚至在一个相对简单的应用程序中( 如文字处理) ，如 果拥有多余的处理能力，那么就可以利用它做很多事情。例如，可以利用多余的 资源进行拼写和语法检查，反走样文本显示，自动语音识别，以及听写等。 计算机图形绘制技术是对交互性要求很高的一个研究领域。当一副图像显示 在屏幕上的时候，用户可以对其进行反复操作，用户的反馈会影响下一副图像的 生成与显示。如果这个过程可以高速运行，那么用户不会看到单副图像，而是完 全沉浸在体验图像动态连续显示的过程中。 在实时绘制中，在性能上至少有3 个目标：每秒有更多的帧、更高的分辨率、 更多( 比较好的真实感效果) 的场景物体。为了达到这些目标，本文从系统结构 和简化物体模型方面对加速算法进行了研究。 【目的】 1 探讨传统图形引擎管道中可改进的方案。 2 探讨简化物体模型的算法。 3 探讨加速场景绘制的方法。 【方法】 1 通过改变图形管道结构，消除冗余的光照计算。 2 使用动态塌陷算法简化模型，从而构造不同细节层次，在不同的场景条 件下调用复杂度不同的模型以加速绘制。 【结果】 1 通过对结构和数据流的分析可以证明改进的图形管道可以有效加速绘制。 2 实现了塌陷算法。 3 提出并实现了新的直接删除顶点的模型简化方法。 4 设计出了细节层次的实现方案。 【结论】 1 加速算法和方案有效且可行。 2 对于更复杂的情况需要做很大的改进。 【关键词】 细节层次，管道，塌陷算法，模型简化 硕士论文：改进的图形管道与细节层次的实现 a b s t r a c t p e o p l eh o p e t h a ts o m e d a yo u rc o m p u t e rc a l lh a se n o u g hp o w e rt od e a lw i t ha n d c o m p u t ea n y t h i n g a c t u a l l y ，w h e ny o u r e i na s i m p l ea p p l i c a t i o np r o g r a m ，s u c h a s t e x t d i s p o s a l ，i ft h ec o m p u t e rh a sm o r ep o w e r ，i tc a nd e a l w i t hm u c hm o r e p r o b l e m s f o r i n s t a n c e ，i nt h ei d l et i m e ，w ec a nm a k eu s eo f t h et i m et oc h e c ks p e l l m a d s y n t a x ，t od i s p l a y t e x tm o r ec l e a r l y ，t oi d e n t i f yv o i c ei n f o r m a t i o na u t o m a t i c a l l y a n de v e nt ol i s t e nt oa n dw r i t es o m e t h i n g c o m p u t e rg r a p h i c st e c h n o l o g yi s ar e s e a r c ha r e at h a tr e q u i r e sh i g hi n t e r a c t i o n a b i l i t y w h e na ni m a g e i sb e e nd i s p l a y e do nt h es c r e e n ，u s e r sc a nr e p e a tt oo p e r a t e o ni t ，a n dt h eu s e r so p e r a t i o n sw i l le f f e c tt h ep r o d u c t i o na n dd i s p l a yo f t h ef o l l o w i n g i m a g e b u t i f t h i sp r o c e s sh a sv e r yh i g hs p e e d ，u s e l sw o n tn o t i c es i n g l ei m a g ea n d t h e yw i l le x p e r i e n c ead y n a m i c a n dc o n t i n u o u s p r o c e s s i nt h eg r a p h i c sr e n d e r i n g ，w eh a v ea tl e a s t3g o a l s ：m o r ef r a m e si no n es e c o n d ， h i g h e rs c r e e nr e s o l u t i o na n d m o l es c e n eo b j e c t sw i t hg o o dt h i r dd i m e n s i o ne f f e c t t o a c h i e v et h e s eg o a l s ，w ed i s c u s ss y s t e mf r a m e w o r ka n dh o wt os i m p l i f yo b j e c t s m o d e l st os p e e dt h er e n d e r i n g 【g o a l s 1 d i s c u s sh o w t oi m p r o v ec o n v e n t i o n a lg r a p h i c sp i p e l i n e 2 d i s c u s sh o wt os i m p l i f yo b j e c t s m o d e l s 3 d i s c u s sh o wt os p e e db i gs c e n er e n d e r i n g 【m yw a y s 1 t oe l i m i n a t er e d u n d a n tc o m p u t a t i o n so nl i g h t i n g 2 u s ec o l l a p s ea r i t h m e t i ct os i m p l i f yo b j e c t s m o d e l s ， a n dt h e r e f o r ew ec a ng e t d i f f e r e n tl e v e l so fd e t a i l s ， a n dt h e nw ec a l ld i f f e r e n tl e v e lo fd e t a i l su n d e rd i f f e r e n t c o n d i t i o n s 【r e s u l t s 1 t h e i m p r o v e m e n t o n g r a p h i c sp i p e l i n ei sp r o v e d t ob ee f f e c t i v e 2 i m p l e m e n t e dc o l l a p s e a r i t h m e t i c 3 i n v e n ta n dr e a l i z ean e wm e t h o dt os i m p l i f yt h em o d e l s 4 d e s i g n e d t h ei m p l e m e n t a t i o ns c h e m eo f l e v e lo fd e t a i l s 【c o n c l u s i o n n 硕士论文：改进的图形管道与细节层次的实现 1 s p e e da r i t h m e t i ca n ds c h e m e i se f f e c t i v ea n df e a s i b l e 2 i nt h em o r e c o m p l e x c o n d i t i o n so u rs c h e m e sn e e d s g r e a ti m p r o v e m e n t 【k e yw o r d s p i p e l i n e ，l e v e lo f d e t a i l s ，l o d ，c o l l a p s ea r i t h m e t i c ，m o d e ls i m p l i f i c a t i o n i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：垒堕生：日期：如。5 ，年j ，月f 1 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 链移乡般 f i 、 签名：一 ：新繇迹、导师签名：篮圣竺 日期：函。f 年y 月f p 日 硕士论文：改进的图形管道与细节层次的实现 第一章引言 1 1 计算机图形学的研究内容 如何在计算机中表示图形，以及如何利用计算机进行图形的生成、处理 和显示的相关原理与算法，构成了计算机图形学的主要研究内容。图形通常 由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。 从处理技术上来看，图形主要分为两类，一类是由线条组成的图形，如工程 图、等高线地图、曲面的线框图等，另一类是类似于照片的着色( s h a d i n g ) ， 也就是通常所说的真实感图形。 可以说，计算机图形学的一个重要研究内容就是要利用计算机产生令人 赏心悦目的真实感图形。为此，必须建立图形所描述的场景的几何表示，再 用某种光照模型，计算在假想的光源、纹理、材质属性下的光照明效果。所 以计算机图形学与另一门学科一计算机辅助几何设计有着密切的关系。事实 上，图形学也把可以表示几何场景的曲线曲面造型技术和实体造型技术作为 其重要的研究内容。同时，真实感图形计算的结果是以数字图像的方式提供 的，计算机图形学也就和图像处理有着密切的关系。图形与图像两个概念间 的区别越来越模糊，但我们认为还是有区别的：图像纯指计算机内以位图 ( b i t m a p ) 形式存在的灰度信息，丽图形含有几何属性，或者说更强调场景的 几何表示，是由场景的几何模型和景物的物理属性共同组成的。 计算机图形学的研究内容非常广泛，如图形硬件、图形标准、图形交互 技术、光栅图形生成算法、曲线曲面造型、实体造型、真实感图形计算与显 示算法，以及科学计算可视化、计算机动画、自然景物仿真、虚拟现实等。 作为一本面向计算机专业本科生和非计算机专业研究生的图形学教材，本书 着重讨论与光栅图形生成、曲线曲面造型和真实感图形生成相关的原理与算 法。 1 2 计算机图形学的发展简史 1 9 5 0 年，第一台图形显示器作为美国麻省理工学院( m i t ) 旋风i 号 ( w h i r l w i n di ) 计算机的附件诞生了。该显示器用一个类似于示波器的阴极 射线管( c r t ) 来显示一些简单的图形。1 9 5 8 年美国c a l c o m p 公司由联机的 数字记录仪发展成滚筒式绘图仪，g e r b e r 公司把数控机床发展成为平板式绘 硕士论文：改进的图形管道与细节层次的实现 图仪。在整个5 0 年代，只有电子管计算机，用机器语言编程，主要应用于科 学计算，为这些计算机配置的图形设备仅具有输出功能。计算机图形学处于 准备和酝酿时期，并称之为：“被动式”图形学。到5 0 年代末期，m i t 的林肯 实验室在“旋风”计算机上开发s a g e 空中防御体系，第一次使用了具有指挥 和控制功能的c r t 显示器，操作者可以用笔在屏幕上指出被确定的目标。与 此同时，类似的技术在设计和生产过程中也陆续得到了应用，它预示着交互 式计算机图形学的诞生。 1 9 6 2 年，m i t 林肯实验室的i v a ne s u t h e r l a n d 发表了一篇题为 “s k c t e h p a d ：个人机交互通信的图形系统”的博士论文，他在论文中首次使 用了计算机图形学“c o m p u t e rg r a p h i c s ”这个术语，证明了交互计算机图形学 是一个可行的、有用的研究领域，从而确定了计算机图形学作为一个崭新的 科学分支的独立地位。他在论文中所提出的一些基本概念和技术，如交互技 术、分层存储符号的数据结构等至今还在广为应用。1 9 6 4 年m i t 的教授 s t e v e na c o o n s 提出了被后人称为超限插值的新思想，通过插值四条任意的 边界曲线来构造曲面。同在6 0 年代早期，法国雷诺汽车公司的工程师p i e r r e b 6 z i e r 发展了套被后人称为b 6 z i e r 曲线、曲面的理论，成功地用于几何外 形设计，并开发了用于汽车外形设计的u n i s u r f 系统。c o o n s 方法和b 6 z i e r 方法是c a g d 最早的开创性工作。值得一提的是，计算机图形学的最高奖是 以c o o n s 的名字命名的，而获得第一届( 1 9 8 3 ) 和第二届( 1 9 8 5 ) s t e v e n a c o o n s 奖的，恰好是i v a ne s u t h e r l a n d 和p i e r r eb 6 z i e r ，这也算是计算机图 形学的一段佳话。 7 0 年代是计算机图形学发展过程中一个重要的历史时期。由于光栅显示 器的产生，在6 0 年代就已萌芽的光栅图形学算法，迅速发展起来，区域填充、 裁剪、消隐等基本图形概念、及其相应算法纷纷诞生，图形学进入了第一个 兴盛的时期，并开始出现实用的c a d 图形系统。又因为通用、与设备无关 的图形软件的发展，图形软件功能的标准化问题被提了出来。1 9 7 4 年，美国 国家标准化局( a n s i ) 在a c ms i g g r a p h 的一个与“与机器无关的图形技 术”的工作会议上，提出了制定有关标准的基本规则。此后a c m 专门成立了 一个图形标准化委员会，开始制定有关标准。该委员会于1 9 7 7 、1 9 7 9 年先后 制定和修改了“核心图形系统”( c o r eg r a p h i c ss y s t e m ) 。i s o 随后又发布了计 算机图形接口c g i ( c o m p u t e rg r a p h i c si n t e r f a c e ) 、计算机图形元文件标准 c g m ( c o m p u t e rg r a p h i c sm e t a f i l e ) 、计算机图形核心系统g k s ( g r a p h i c s k e r n e ls y s t e m ) 、面向程序员的层次交互图形标准p h l g s ( p r o g r a m m e r s h i e r a r c h i c a l m e r a c t i v eg r a p h i c ss t a n d a r d ) 等。这些标准的制定，为计算机图 2 硕士论文：改进的图形管道与细节层次的实现 形学的推广、应用、资源信息共享，起到了重要作用。 7 0 年代，计算机图形学另外两个重要进展是真实感图形学和实体造型技 术的产生。1 9 7 0 年b o u k n i g h t 提出了第一个光反射模型，1 9 7 1 年g o u r a n d 提 出“漫反射模型+ 插值”的思想，被称为g o u r a n d 明暗处理。1 9 7 5 年p h o n g 提 出了著名的简单光照模型一p h o n g 模型。这些可以算是真实感图形学晟早的开 创性工作。另外，从1 9 7 3 年开始，相继出现了英国剑桥大学c a d 小组的b u i l d 系统、美国罗彻斯特大学的p a d l 1 系统等实体造型系统。 1 9 8 0 年w h i t t e d 提出了一个光透视模型w h i t t e d 模型，并第一次给出光 线跟踪算法的范例，实现w h i t t e d 模型；1 9 8 4 年，美国c o m e l l 大学和日本 广岛大学的学者分别将热辐射工程中的辐射度方法引入到计算机图形学中， 用辐射度方法成功地模拟了理想漫反射表面间的多重漫反射效果；光线跟踪 算法和辐射度算法的提出，标志着真实感图形的显示算法已逐渐成熟。从8 0 年代中期以来，超大规模集成电路的发展，为图形学的飞速发展奠定了物质 基础。计算机的运算能力的提高，图形处理速度的加快，使得图形学的各个 研究方向得到充分发展，图形学已广泛应用于动画、科学计算可视化、 c a d c a m 、影视娱乐等各个领域。 最后，我们以s i g g r a p h 会议的情况，来结束计算机图形学的历史回顾。 a c ms i g g r a p h 会议是计算机图形学最权威的国际会议，每年在美国召开， 参加会议的人在5 0 ，0 0 0 人左右。世界上没有第二个领域每年召开如此规模 巨大的专业会议，s i g g r a p h 会议很大程度上促进了图形学的发展。 s i g g r a p h 会议是由b r o w n 大学教授a n d r i e sv a nd a m ( a n d y ) 和i b m 公司 s a mm a t s a 在6 0 年代中期发起的，全称是“t h es p e c i a li n t e r e s t g r o u p o n c o m p u t e rg r a p h i c sa n di n t e r a c t i v et e c h n i q u e s ”。19 7 4 年，在c o l o r a d o 大学召 开了第一届s 1 g g r a p h 年会，并取得了巨大的成功，当时大约有6 0 0 位来 自世界各地的专家参加了会议。到了1 9 9 7 年，参加会议的人数已经增j n 至t j 4 8 ，7 0 0 。因为每年只录取大约5 0 篇论文，在c o m p u t e rg r a p h i c s 杂志上发表， 因此论文的学术水平较高，基本上代表了图形学的主流方向。 1 3 应用及研究前沿 1 3 1计算机辅助设计与制造 c a d c a m 是计算机图形学在工业界最广泛、最活跃的应用领域。计算 机图形学被用来进行土建工程、机械结构和产品的设计，包括设计飞机、汽 车、船舶的外形和发电厂、化工厂等的布局以及电子线路、电子器件等。有 3 硕士论文：改进的图形管道与细节层次的实现 时，着眼予产生工程和产品相应结构的精确图形，然而更常用的是对所设计 的系统、产品和工程的相关图形进行人机交互设计和修改，经过反复的迭代 设计，便可利用结果数据输出零件表、材料单、加工流程和工艺卡，或者数 据加工代码。在电子工业中，计算机图形学应用于集成电路、印刷电路板、 电子线路和网络分析等方面的优势是十分明显的。一个复杂的大规模或超大 规模集成电路版图根本不可能用手工设计和绘制，用计算机图形系统不仅能 进行设计和画图，而且可以在较短的时间内完成，并把结果直接进行后续工 艺加工处理。在飞机工业中，美国波音飞机公司己用有关的c a d 系统实现 波音7 7 7 飞机的整体设计和模拟，其中包括飞机外型、内部零部件的安装和 检验。 随着计算机网络技术的发展，在网络环境下进行异地异构系统的协同设 计，已经成为c a d 领域最热门的课题之一。现代产品设计己不再是一个设 计领域内孤立的技术闯题，丽是综合了产品各个相关领域、相关过程、相关 技术资源和相关组织形式的系统化工程。它要求设计团队在合理的组织结构 下，采用群体工作方式来协调和综合设计者的专长，并且从设计一开始就考 虑产品生命周期的全部因素，从而达到快速响应市场需求的目的，协同设计 的出现使企业生产的时空观发生了根本的变化。异地设计、异地制造、异地 装配成为可能，从而为企业在市场竞争中赢得了宝贵的时间。 三维几何造型系统具有许多优点，例如，可以进行装配件的干涉检查， 可以用于有限元分析、仿真、数控加工等后续操作，它基本上代表了c a d 技术的发展方向。c a d 领域另一个非常重要的研究领域就是基于工程图纸的 三维形体重建。三维形体重建就是从二维信息中提取三维信息，通过对这些 信息进行分类、综合等一系列处理，在三维空间中重新构造出二维信息所对 应的三维形体，恢复形体的点、线、面及其拓扑关系。二维图纸设计在工程 界中仍占有主导地位，工程上有大量旧的透视图和投影图片可以利用、借鉴， 许多新的设计可凭借原有的设计基础进行修改即可完成，所以，三维形体重 建在工程中有重要的意义。不过，目前的三维形体重建算法主要是针对多面 体和对主轴方向有严格限制的二次曲面体的。任意曲面体的三维形体重建， 至今仍是一个未解决的世界难题。 1 3 2可视化 科学技术的迅猛发展，数据量的与日俱增使得人们对数据的分析和处理 变得越来越困难，人们难以从数据海洋中得到最有用的数据，找到数据的变 化规律，提取数据最本质的特征。但是，如果能将这些数据用图形形式表示 4 硕士论文：改进的图形管道与细节层次的实现 出来，常常会使问题迎刃而解。1 9 8 6 年，美国科学基金会( n s f ) 专门召开 了一次研讨会，会上提出了“科学计算可视化( v i s u a l i z a t i o ni ns c i e n t i f i c c o m p u t i n g ，简称为v i s c ) ”。第二年，美国计算机成像专业委员会向n s f 提交了“科学计算可视化的研究报告”后，v i s c 就迅速发展起来了。 目前科学计算可视化广泛应用于医学、流体力学、有限元分析、气像分 析当中。尤其在医学领域，可视化有着广阔的发展前途。机械人和医学专家 配合做远程手术是目前医学上很热门的课题，丽这些技术的实现的基础则是 可视化。可视化技术将医用c t 扫描的数据转化为三维图像，并通过一定的 技术生成在人体内漫游的图像，使得医生能够看到并准确地判别病人的体内 的患处，然后通过碰撞检测一类的技术实现手术效果的反馈，帮助医生成功 地完成手术。从目前的研究状况来看，这项技术还远未成熟，离实用还有一 定的距离。主要原因是生成人体内漫游图像的三维体绘制技术还没有达到实 时的程度，而且现在大多数体绘制技术是基于平行投影的，而漫游则需要真 实感更强的透视投影技术，然而体绘制的透视投影技术到还没有很好地解决。 另外在漫游当中还要根据c t 图像区分出不同的体内组织，这项技术叫 s e g m e n t a t i o n 。目前的s e g m e n t a t i o n 主要是靠人机交互来完成，远未达到自 动实时的地步。 1 3 3 图形实时绘制与自然景物仿真 在计算机中重现真实世界场景的过程叫做真实感绘制。真实感绘制的主 要任务是要模拟真实物体的物理属性，即物体的形状、光学性质、表面的纹 理和粗糙程度，以及物体间的相对位置、遮挡关系等等。其中，光照和表面 属性是最难模拟的。为了模拟光照，已有各种各样的光照模型。从简单到复 杂排列分别是：简单光照模型、局部光照模型和整体光照模型。从绘制方法 上看有模拟光的实际传播过程的光线跟踪法，也有模拟能量交换的辐射度方 法。除了在计算机中实现逼真物理模型外，真实感绘制技术的另一个研究重 点是加速算法，力求能在最短时间内绘制出最真实的场景。例如求交算法的 加速、光线跟踪的加速等等，像包围体树、自适应八叉树都是著名的加速算 法。实时的真实感绘制已经成为当前真实感绘制的研究热点，而当前真实感 图形实时绘制的两个热点问题则是物体网格模型的面片简化和基于图像的绘 制( i b ri m a g eb a s e dr e n d e r i n g ) 。网格模型的面片简化，就是指对网格面片 表示的模型，在一定的误差范围内，删除部分点、边、面，从而简化所绘制 场景的复杂层度，加快图形绘制速度。i b r 完全摒弃传统的先建模，然后确 定光源的绘制方法，它直接从一系列己知的图像中生成未知视角的图像。这 5 硕士论文：改进的图形管道与细节层次的实现 种方法省去了建立场景的几何模型和光照模型的过程，也不用进行如光线跟 踪等极费时的计算。该方法尤其适用于野外极其复杂场景的生成和漫游。 另外，真实感绘制已经从最初绘制简单的室内场景发展到现在模拟野外 自然景物，比如绘制山、水、云、树、火等等。人们提出了多种方法来绘制 这些自然景物，比如绘制火和草的粒子系统( p a r t i c l es y s t e m ) ，基于生理模 型的绘制植物的方法，绘制云的细胞自动机方法等。也出现了一些自然景物 仿真绘制的综合平台，如德国l i n t e r m a n n 和d e u s s e n 的绘制植物的平台 x f o r g ，以及清华大学自主开发的自然景物设计平台。 1 3 4 计算机动画 随着计算机图形学和计算机硬件的不断发展，人们已经不满足于仅仅生 成高质量的静态场景，于是计算机动画就应运而生。事实上计算机动画也只 是生成一幅幅静态的图像，但是每一幅都是对前一幅做一小部分修改( 如何 修改便是计算机动画的研究内容) ，这样，当这些画面连续播放时，整个场景 就动起来了。 早期的计算机动画灵感来源于传统的卡通片，在生成几幅被称做“关键 帧”的画面后，由计算机对两幅关键帧进行插值生成若干“中间帧”，连续播放 时两个关键帧就被有机地结合起来了。计算机动画内容丰富多彩，生成动画 的方法也多种多样，比如基于特征的图像变形、二维形状混合、轴变形方法、 三维自由形体变形( f f d ， f r e e - f o r md e f o r m a t i o n ) 等。 近年来人们普遍将注意力转向基于物理模型的计算机动画生成方法。这 是一种崭新的方法，该方法大量运用弹性力学和流体力学的方程进行计算， 力求使动画过程体现出最适合真实世界的运动规律。然而要真正达到真实运 动是很难的，比如人的行走或跑步是全身的各个关节协调的结果，要实现很 自然的人走路动画，计算方程非常复杂、计算量极大，基于物理模型的计算 机动画还有许多内容需要进一步研究。 2 0 世纪9 0 年代是计算机动画应用辉煌的十年。d i s n e y 公司每年都要出一 部制作精美的卡通动画片，好莱坞的大片屡屡大量运用计算机生成各种各样 精彩绝伦的动画特技效果，广告设计、电脑游戏也频频运用计算机动画。计 算机动画也因这些商业应用的大力推动而有了极大的发展。 1 3 5用户接口 用户接口是人们使用计算机的第一观感。一个友好的图形化的用户界面 能够大大提高软件的易用性，在d o s 时代，计算机的易用性很差，编写一个 6 硕士论文：改进的图形管道与细节层次的实现 图形化的界面要费去大量的劳动，过去软件中有6 0 的程序是用来处理与用 户接口有关的问题和功能的。进入8 0 年代后，随着x w i n d o w 标准的面世， 苹果公司图形化操作系统的推出，特别是微软公司w i n d o w s 操作系统的普 及，标志着图形学已经全面融入计算机的方方面面。如今在任何一台普通计 算机上都可以看到图形学在用户接口方面的应用。操作系统和应用软件中的 图形、动画比比皆是，程序直观易用。很多软件几乎可以不看任何说明书， 而根据它的图形、或动画界面的指示进行操作。 目前几个大的软件公司都在研究下一代用户界面，开发面向主流应 用的自然、离效多通道的用户界面。研究多通道语义模型、多通道整合算法 及其软件结构和界面范式是当前用户界面和接口方面研究的主流方向，而图 形学在其中起主导作用。 1 4 本文研究内容 人们对于计算机的一个最大理想就是希望计算机有一天可以拥有足够强 的计算和处理能力事实上，甚至在一个相对简单的应用程序中( 如文字处理) ， 如果拥有多余的处理能力，那么就可以利用它做很多事情例如，空闲时段的 平些和语法检查，反走样文本显示，自动语音识别，以及昕写等。 在实时绘制中，在性能上至少有3 个目标：每秒有更多的帧、更高的分 辨率、更多( 比较好的真实感效果) 的场景物体。6 0 - 8 5 帧率的速度通常认 为已经足够，针对目前的应用状况，大概1 6 0 0 * 1 2 0 0 的分辨率也是足够的， 但是在场景复杂度方面却没有上限。波音7 7 7 的绘制包括1 3 2 5 0 0 个零件和 3 0 0 0 0 0 0 个以上的扣件，相应的多边形模型也超过5 0 0 0 0 0 0 0 0 个以上的多边 形。这种情况普遍存在于上文提到的动画、用户界面、虚拟现实等等情况中， 因为所有这些技术都搭建在一个图形引擎之上，要改进性能，就需要加速算 法。 本文探讨的第一个问题是针对传统的图形引擎管道的数据传输过程、着 色顺序等进行考查，最后提出一种可去除大量冗余计算的图形管道结构。第 二个问题是，在大的场景越来越复杂的情况下，降低物体绘制复杂度的方法 及其实现。 7 硕士论文：改进的图形管道与细节层次的实现 第二章图形管道概述 图形绘制管道是图形学的核心内容。绘制管道的主要功能就是在给定虚 拟相机、三维物体、光源、照明模式，以及纹理等诸多条件下，如何生成或 者绘制一幅二维图像。因此，对于图形绘制来说，绘制管道是基础。 2 1 体系结构 图2 1 在现实生活中，管道概念的表现方式很多，例如输油管道、工厂的装配 线等。对于图形绘制来说，也采用了这个概念。 一条管道通常包括多个阶段，无论其中的个别管道速度多么快，管道的 整体快慢速度是由管道中最慢的那个阶段决定的。例如，在送水管道中，只 有等到水已经从第一阶段流到第二阶段以后，水才能从第二阶段流到第三阶 段。 理论上，如果要把一个非管道结构分成n 个管线阶段，就要给予一个大 小为n 的加速因子。例如，当一个滑雪缆车只有一个座位时，效率不会很高， 但是如果增加座位，就可以提高效率，在相同的时间内可以把更多的滑雪者 运送到山顶上。如果管道各个阶段用平行的方式工作，那么必须等到其中最 慢的一个阶段结束工作后，整个管道阶段才算结束。例如，在汽车装配线上， 如果驱动车轮的装配阶段需要3 分钟，而其他阶段需要两分钟，那么制造一 辆汽车的最快速度是3 分钟，对于其他过程就要闲置1 分钟。因此驱动车轮 的装配式一个瓶颈，因为它决定了整个装配过程的速度。 计算机图形学中也存在这种管道结构，如下图所示。 硕士论文：改进的图形管道与细节层次的实现 l 应用程序 叫 几何 卜叫 光栅 i i 7 _ 一口号 卜叫二卜一 图2 2 在概念上可以将其粗略分为3 个阶段：应用程序阶段、几何阶段以及光 栅阶段。这种结构是绘制管道的核心机制。在绘制管道中，每个阶段自身也 可能就是一条管道，这就是意味着它可以包含几个子阶段。这里给出概念阶 段、功能阶段和管道阶段之间的区别。功能阶段规定了这个阶段需要执行的 任务，并没有限制该任务在管道中的执行方式。从另外一方面来说，一个管 道阶段应该与其它管道阶段同时执行，但是为了满足高性能的要求，也可以 对它们进行并行化处理。一个具体的实现方法可能将两个功能阶段合并为一 个管道阶段，同时也可能将另外一个比较耗时的功能阶段分成几个管道阶段， 甚至可以让它们相互并行执行。 最慢的管道阶段决定绘制速度，即图像更新速度，这种速度般用f p s 表示，也就是每秒绘制的图像数量，或者用h z 来表示。由于涉及到管道， 因此不能将想绘制的所有数据通过整个管道的时间进行简单相加，这就是管 道结构的特点，它允许对某些阶段进行并行化处理。如果能够确定其中的瓶 颈位置，也就是管道中最慢的阶段，同时知道所有数据通过该阶段需要花费 的时间，就可以计算出绘制速度。例如，假设瓶颈阶段需要2 0 m s 来执行， 那么绘制速度就是5 0 h z 。前提条件是输出设备能够以这种速度不断更新，否 则实际的数据传输就会很慢。在其他一些管道应用中，绘制速度往往可以用 吞吐量来替代。 如同字面意思所表达的那样，应用程序阶段由应用程序来驱动，因此可 以通过软件来实现。例如，这个阶段可以包括碰撞检测、加速算法、动画， 以及力反馈等。第二阶段是几何阶段，根据体系结构，可以用软件或者硬件 来实现，包括变换、投影、光照等处理。此阶段主要是计算机绘制的内容， 决定如何绘制，以及在什么地方绘制。最后，光栅阶段是利用前面阶段产生 的数据进行图像绘制。 9 硕士论文：改进的图形管道与细节层次的实现 2 2 应用程序阶段 由于应用程序阶段是通过软件方式实现的，因此能够对该阶段发生的情 况进行完全的控制，可以通过改变实现方法来改变实际性能。而其他阶段， 由于它们全部或者部分建立在硬件基础上，因此要改变实现过程会非常困难。 即便如此，仍然有可能改变几何和光栅阶段所消耗的时间。例如，可以在应 用程序阶段通过减少三角形数量来达到目的。 在应用程序的末端，将需要绘制的几何体输入到绘制管线的下一个阶段。 这些几何体都是绘制图元，最终需要在屏幕上显示出来，这就是应用程序阶 段最重要的任务。 由于应用程序是基于软件方式实现的，因此不能像几何和光栅阶段那样 可以继续分成若干个子阶段。但是为了提高性能，该阶段可以在几个并行的 处理器中并行执行。这种形式称为超标量体系结构。 在应用程序阶段，通常实现的内容有碰撞检测。当检测到两个物体之间 存在碰撞关系时，就会产生一个信号并送回给碰撞物体，如同力反馈器那样。 此外，应用程序阶段也是检察其他输入信息源的地方，如键盘、鼠标、虚拟 现实的头盔等。在这个阶段实现的其他过程还包括纹理动画、变换仿真、几 何变形，以及其他一些计算。例如，层次视锥裁减就可以在这里实现。 2 3 几何阶段 几何阶段主要负责大部分多边形和顶点操作，可以将这个阶段进一步划 分为下图所示的几个功能阶段。 图2 3 需要注意的是，根据具体的实现，这些阶段可以和管道阶段等同，也可 以不等同。在一些情况下，一系列连续的功能阶段可以形成单个管道阶段( 和 其他管道阶段并行运行) 。在另外一些情况下，一个功能阶段可以划分为几个 更细小的管道阶段。 例如，在一种极端情况下，整条绘制管道中所有的阶段都可以用软件来 实现，这样可以认为整条管道是由几个管道阶段组成的。在另外一个极端情 1 0 硕士论文：改进的图形管道与细节层次的实现 况下，可以将每个功能阶段分成为若干个更小的管道阶段，每个这样的管道 阶段可以在设计好的浮点处理器中执行。 需要注意的是，几何阶段执行的是计算量非常高的任务，在只有一个光 源的情况下，每个顶点大概需要1 0 0 次左右精确的浮点运算操作。 2 3 1模型和视点转换 在屏幕上的显示过程中，模型通常需要变换到若干不同的空间或者坐标 系统中。开始的时候，模型处于自身所在的模型空间里，可以简单的认为它 根本没有进行任何变换。每个模型可以和一个模型变换相联系，这样它就可 以进行定位和定向。同一个模型还可以和几种不同的模型变换联系在一起。 允许同一个模型有多个副本( 称为实例) ，可以在同一场景中具有不同的位置、 方向和大小，而不需要对基本几何体进行复制操作。 模型变换的变换对像是模型的顶点和法线。物体的坐标称作模型坐标， 如果将模型变换应用到这些坐标中，那么可以说这个模型位于世界坐标中。 世界坐标是唯一的，所有模型经过变换以后都位于同一个空间中。 正如前面所述，只对相机( 或者视点) 可以看到的模型进行绘制。相机 在世界坐标中有一个位置和方向，用来放置和校准相机。为了便于投影和裁 剪，必须对相机和所有的模型进行视点变换。变换的目的就是要把相机放到 原点，然后进行视点校准，使其朝向z 轴的负方向，y 轴指向上方，x 轴指向 右边。在视点变换后，实际位置和方向就依赖于当前的应用程序接口，称上 述描绘的空间为相机空间或者观察空间。下图显示了视点变换对视点和模型 的影响。 幽2 4 所有的模型变换和视点变换都用一个4 x 4 的矩阵来实现。出于效率方面 的考虑，在模型变换之前首先将所有的矩阵级联起来，彼此相乘，形成一个 矩阵。但是，如果用这种方法，世界坐标将不再存在模型直接变换到了 观察空间。 很多精细的变换都发生在这个阶段，顶点混合技术可以把不同的刚体平 硕士论文：改进的图形管道与细节层次的实现 滑的连接在一起，例如，将手和手臂在手腕处连接在一起) 。 2 。3 。2 光照和着色 为了让模型看起来更加真实，可以给场景配上一个或者多个光源。同时 还可以选择是否使灯光影响几何体的外观，几何模型可以有与其每个顶点相 关联的颜色或者覆盖其上的一个纹理。如果注意观察在没有光照的情况下纹 理对图形表面产生的三维效果，会发现单纯依赖颜色的效果并不是很逼真。 对于受光源影响的模型来说，可以用光照方程来计算模型上的每个顶点 的颜色。这个方程近似模拟了光子和表面之间的实际作用。在现实世界中， 光源发出光子，然后被表面反射或者吸收。在图形学中，没有太多的时间来 模拟这种现像。例如，这个方程并没有包含真实的反射和阴影。此外，模型 在图形学上通常以三角形来表示，目前，大部分图形硬件都采用三角形这种 几何图元。物体表面每个顶点的颜色可以由光源及其特性、顶点的位置和法 线、顶点所在的材质属性来计算。当在屏幕上绘制三角形时，可以通过对三 角形顶点的颜色进行插值来绘制。 通常光照计算是在世界坐标中进行的。但是如果对光源进行视点变换， 在观察空间中会得到同样的光照效果。这是因为即使参与光照计算的所有实 体都变换到同一个空间中，光源、视点，以及模型之间的相对位置保持不变。 2 3 3 投影 在光照处理之后，绘制系统开始进行投影，鼠的是将视体变换为一个单 位立方体。这个立方体的对角顶点分别是( 一1 ，一1 ，- 1 ) 和( 1 ， 1 ， 1 ) 。 通常也称单位立方体为规范视体。目前主要有两种投影方法，即平行投影和 透视投影，这将在后面章节具体介绍。 2 3 4 裁剪 只有当图元完全或者部分存在于视体内部的时候，才需要将其发送到光 栅阶段，在这个阶段可以把这些图元在屏幕上绘制出来。当一个图元完全位 于一个视体内部的时候，那么它可以直接进入下一个阶段t 完全在视体外部 的图元，将来不会进入下一个阶段，因为它们无需被绘制。需要对那些部分 位于视体内的图元进行裁剪处理。例如，当一条线段的一个端点在视体内而 另外一个端点在视体外时，就需要根据视体对该线段进行裁剪，位于视体外 的那个端点由一个新的端点代替，这个新端点是线段和视体的交点a 1 2 硕士论文：改进的图形管道与细节层次的实现 n 艟 厂 i = 7 z ”t b l 蜘b 1 _ _ 一 图2 - 5 投影变换之后的图元只针对单位立方体进行裁剪，在裁剪之前进行视点 转换和投影的优势在于可以使裁剪比较一致，而且图元可以根据单位立方体 进行裁剪。除了视体的5 个裁剪平面之外，用户还可以自定义裁剪平面来进 行裁剪。 2 3 5 屏幕映射 只有在视体内部经过裁剪的图元，才可以进入屏幕映射阶段，进入到这 个阶段的时候，坐标仍然是三维的。每个图元的x 和y 坐标变换到了屏幕坐 标中，屏幕坐标系连同z 坐标一起成为窗口坐标系。假设在一个窗口里对场 景进行绘制，窗口的最小拐角( x l ，y 1 ) ，最大拐角为( x 2 ，y 2 ) ，其中x l x 2 ， y l y 2 。屏幕映射首先进行平移，随后进行缩放，在映射过程中z 坐标不受 影响，新的x 和y 坐标成为屏幕坐标系，与z 坐标一起( 1 z 3 。由于p h o n g 着色是像素级的操作，因此此方法p h o n g 着色无法受益。 但是对于一种增强的快速p h o n g 着色，延迟光照仍然可以节约其泰勒初始参 1 9 硕士论文：改进的图形管道与细节层次的实现 数的计算代价。 3 5 同步问题的解决 图3 3 由于两个部分的信息传送的异步，因此在产生最终结果的时候需要对其 进行同步操作。这里引入一个索引的数据结构来解决这个问题。我们给每个 三角形一个索引值，用这个索引值指示信息和像素从属于哪个父亲多边形。 这里我们假设有一个索引缓存，用来存储索引信息，如图3 3 所示。 当一个三角形被扫描转换时，可见的像素查询其在索引缓存中父亲三角 形的索引值。如果这个三角形不可见，则索引值为n u l l 。如果三角形可见， 光照单元中三角形着色操作结束后，这些被索引的像素就可以在光栅单元用 像素级的着色方法进行着色。因此，尽管两个部分的信息异步传送，最终还 是可以能正确产生需要的图像。 硕士论文：改进的图形管道与细节层次的实现 第四章l o d ( l e v e lo f d e t a i l ) 相关基础知识 计算机图形学的先锋总是在复杂度和性能上面作斗争。每一个图形编程 者都知道实时性和速度、保真度和帧率、高质量的图形和平滑流畅的动画之 间存在的矛盾。而细节层次就是计算机交互图形学试图用来平衡复杂度和性 能的一座桥梁。 为了实现l o d ，本章首先介绍一些图形学的相关知识。首先介绍几何变 换和三维空间观察，这是图形学基础，是理解所有内容的基础。然后简单介 绍真实感图形学、视觉外观对人视觉的影响因素，由此可以探讨从哪些方面 可以找到研究的方向。由于本文的l o d 选取方法是采用基于光照的方法， 而计算操作需要使用光照方程，因此光照方程将作为重点介绍。l o d 的动态 生成方法应用到动态塌陷技术，这里也会做一个简单介绍。 图形变换一般是指将图形的几何信息经过几何变换后产生新的图形。图 形变换既可以看作是图形不动而坐标系变动