（计算机软件与理论专业论文）嵌入式三维图形引擎的设计与实现.pdf

硕士论文：嵌入式三维图形引擎的设计与实现 摘要 从嵌入式操作系统未来的演变趋势看，p d a 、手机等移动终端设备的快 速增长，大大促进了嵌入式操作系统的发展。未来嵌入式系统的主要增长动 力来自于消费类行业，比如嵌入式游戏。这就需要在嵌入式设备上实时显示 图形，而且从发展趋势来看，很有可能要求实时显示三维图形，这就对运行 在嵌入式设备上的图形引擎提出了前所未有的挑战。要迎接这个挑战，就需 要研究如何将图形学算法应用到嵌入式系统中；如何借助真实感图形生成技 术和渲染技术，在嵌入式系统中实现场景造型、投影变换、消除隐藏面、光 照明模型等，使嵌入式系统可以实现高度真实感的模型和渲染强烈的感染效 果。但要在速度慢，内存小，显示分辨率低的情况下，在嵌入式设备上实时 显示三维图形，就不能完全照搬已有的图形学算法和引擎设计思路，需要对 已有的真实感图形学算法开展工程化，实用化的研究。 本文主要侧重研究在主频和内存都很小的情况下，如何在分辨率很低的 嵌入式设备上实时显示三维图形，进而实现一个能运行在嵌入式设备上的三 维图形引擎，以满足游戏及其他娱乐的需求，为此我们的思路是： ( 1 ) 确定最基本的渲染图元，设计中为方便嵌入式平台的图形硬件加 速器的设计，在参考其它的3 d 图形引擎的基础上，考虑本引擎的基本渲染 图元为三角形。选择三角形作为基本图元不仅能够方便建模、简化图形引擎 的a p i ( 应用程序编程接口) ，而且能够大大提高渲染效率。 ( 2 ) 尽量利用已经有的算法，例如：画直线的b r e s e n h a m 算法，填充多 边形的扫描转换算法，这些都被证明是目前已知效率最高的算法。 ( 3 ) 算法上尽量利用硬件的优势，减少软件所做的工作。这样必须对在 p c 机上使用的传统算法进行改进，同时我们注意到嵌入式设备上的显示分辨 率很低，在这种情况下，没有必要追求象在p c 机上那样的高准确度和高清 晰度，在一定范围内，我们可以改变算法来以一定的误差换取实时显示的速 度。 ( 4 ) 图形引擎接口的应尽量少。嵌入式操作系统非常简单，而在其上主 要是用c 语言来做丌发，所以图形引擎的编程接口应尽量简洁，可以考虑合 并一些功能，避免太多的a p i 。这样做不仅可以提高图形引擎本身的丌发效 率，同时还可方便应用程序员编程。 关键词三维图形，引擎，算法，嵌入式，消隐 硕士论文：嵌入式三维图形引擎的设计与实现 a b s t r a c t w h e n y o ua n a l y z e t h ef u t u r e t e c h n o l o g y t r e n do fe m b e d d e d o p e r a t i o n s y s t e m ，y o uc o u l ds e et h a tt h ee m b e d d e do p e r a t i o ns y s t e mw i l lh a v ee x t e n s i v e a p p l i c a t i o ni nt h e f i e l d so fc o m m u n i c a t i o n 、a u t o m o b i l e 、m e d i c a lt r e a t m e n t 、 s a f e t yi n f o r m a t i o n a tt h es a m et i m e ，i nt h ec o n s u m p t i o ne l e c t r o n i cp r o d u c tt h e e m b e d d e do p e r a t i n gs y s t e mh a ss h o w ns t r o n g e rg r o w t hs t r e n g t ht o o t h em a i n m o t i v ef o r c eo fg r o w t ho ft h ee m b e d d e do p e r a t i n gs y s t e mi nt h ef u t u r ec o m e s f r o mt h ec o n s u m p t i o nt r a d e ，s u c ha s ：e m b e d d e dg a m e t h i sr e q u i r e st h a ty o uc a n d i s p l a y t h e g r a p h i c s o nt h ee m b e d d e ds y s t e mi n r e a l t h e g r a p h i c se n g i n e o p e r a t e do n t h ee m b e d d e ds y s t e mc o n f r o n tau n p r e c e d e n t e d c h a l l e n g e t h eg r a p h i c sa l g o r i t h mi sa p p l i e dt ot h ee m b e d d e ds y s t e m st os e e kt om a k e t h eo b j e c t sv i s u a l l ya p p e a l i n ga n d r e a l i s t i c b yt h et e c h n o l o g yo f v i s u a lr e a l i s m a n dr e n d i n gw ec o u l dm a k et h ee m b e d d e ds y s t e mr e a l i z et h em o d e lo ft h eh i g h s e n s eo f r e a l i t y , p l a yu pt h es t r o n gi n f e c t i o nr e s u l t ，c a r r yo nl i f e l i k es i m u l a t i o n m e a n w h i l ew h e nw ed i s p l a yt h et h r e e d i m e n s i o n a lg r a p h i c so ns l o w 、m e m o r y l i m i t e d 、e m b e d d e ds y s t e mi nr e a lt i m e ，w en e e dt ol e a r nt o a d o p tt h ee x i s t i n g a l g o r i t h m t o p r a c t i c a lp r o j e c t i n t h r e e d i m e n s i o n s h o w , t h em o s ti m p o r t a n t f r a g m e n t s i st h eo r d e r so f r e n d i n g a n d u s u a l l yt h ek e y st os p e e ds u c ha sr e m o v i n g h i d d e ns u r f a c e ，c l i p p i n ge t c w em a i n l ys t u d y i n gh o wt od i s p l a ya n d r e n d i n g t h e t h r e e d i m e n s i o ns h o w sw i t hb o t hc p ua n dm e m o r y b e i n gl i t t l e ，a n dt h e nr e a l i z e o n ee n g i n eo p e r a t i n go nt h ee m b e d d e ds y s t e mw h i c hc a ns a t i s f yt h eg a m e ，a n d t h ed e m a n df o ro t h e ra m u s e m e n t f i r s t l yc o n f i r mt h eb a s i cr e n d i n gu n i tt h e n c o n s i d e rt h ed e s i g no fh a r d w a r ew h i c hc a l la c c e l e r a t et h ed i s p l a y i n g ，c h o o s i n g t h et r i a n g l ea sb a s i cr e n d i n gu n i tn o to n l yf a c i l i t a t e m o d e l i n gg r e a t l y , b u ta l s o s i m p l i f ya p i ( t h ep r o g r a m m i n gi n t e r f a c eo fa p p l i c a t i o np r o g r a m ) o f t h ef i g u r e e n g i n e ，a n dc a ni m p r o v et h ee f f i c i e n c yg r e a t l y t r yo n e s b e s tt ou t i l i z et h e a l g o r i t h mt h a th a s ，f o re x a m p l e ：b r e s e n h a ma l g o r i t h mo f t h es t r a i g h tl i n ed r a w , p a c k s t h e s c a n n i n g t r a n s f e r a l g o r i t h m o ft h e p o l y g o n a ut h e s e a r e p r o v e d c l a s s i c a l l yi t i st h em o s te f f e c t i v ea l g o r i t h ma tp r e s e n t t r yo n e sb e s tt ou t i l i z e t h e a d v a n t a g e o ft h eh a r d w a r ea tt h e a l g o r i t h m ，r e d u c e t h ew o r k d o i n gb y s o f t w a r e ，i nt h i sw a y , w em u s ti m p r o v et h et r a d i t i o n a la l g o r i t h mt h a ti su s e do n t h ep c ，a tt h es a m et i m ew en o t i c et h a tr e s o l u t i o nr a t i oo fe m b e d d e d e q u i p m e n t i l 硕十论文：嵌入式三维图形引擎的设计与实现 o ns h o wi sl o w , i nt h i sc a s e ，i ti su n n e c e s s a r yf o ru st op u r s u es u c ha c c u r a c yi n p c ，w i t ht h eh i g hd e f i n i t i o n ，w i t h i nt h es p e c i f i cl i m i t s ，w ec a nc h a n g ea l g o r i t h m s t oc o m ew i t hc e r t a i ne r r o rt h a tc a nb ea c c e p t e d ，g a i nt h es p e e ds h o w ni nr e a l t i m e t ot h ec o n s i d e r a t i o no ft h ee n g i n e ：i n t e r f a c eo ft h ef i g u r e ，b e c a u s em a i n l y u s ect o d e v e l o p o nt h ee m b e d d e d e q u i p m e n t ，e m b e d d e dc h a r a c t e r i s t i c o f o p e r a t i n gs y s t e mi na d d i t i o n ，s of i g u r ep r o g r a m m i n gi n t e r f a c eo fe n g i n ew a n ti n t r y i n g o n e sb e s t w h i l e f a c i l i t a t i n ga p p l i c a t i o np r o g r a m b a s i cu n i to f p r o g r a m m i n g ，s h o u l d a l s o t r y o n e sb e s tt ob e s u c c i n c t ，c a n c o n s i d e r a m a l g a m a t i n gs o m ef u n c t i o n s ，p r e v e n tt o om u c h a p if r o m c o n n e c t i n g k e y w o r d s 3 _ dg r a p h i c s ，e n g i n e ，a l g o r i t h m ，e m b e d d e ds y s t e m r e m o v i n g h i d d e ns u r f a c e i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 日期：羽送年月函 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：盟导师签名： 日期：产厂月i 船 硕士论文：嵌入式三维图形引擎的设计与实现 第一章引言 1 1 计算机真实感图形生成技术的应用及其发展 利用计算机绘制真实感图形在很多领域都很重要。例如，在飞行驾驶员 模拟训练中，受训练人员坐在模拟舱中，前面呈现的图像宛如在实际环境中， 进行模拟操纵时，景象随之改变，与真实飞行一样。这样可大大节约训练费 用。此外，在计算机动画片制作、城市规划、汽车制造业、建筑业、分子结 构的研究、影视广告、医学、气象学、地质学、考古学等领域都有广泛应用。 同样，在包装产品的计算机辅助设计中，设计者总希望看一下他的初步设计 究竟是什么样子，特别是产品设计，希望有一足够逼真的图像，以便让人来 评价一下他的设计。过去往往用人工绘图或制作实物模型来检查设计效果， 而且随着方案的修改，要反复绘图或反复制作模型，耗费大量人力物力。而 采用计算机图形显示技术，就可以很方便的在屏幕上显示产品的真实感图像， 而且可以从各种不同角度去观察产品外形，如发现不合适的地方，可在屏幕 上直接对产品外形进行交互式修改。这种技术犬大节约了人力和物力，并使 设计周期缩短、质量提高。 计算机图形学发展的初期，主要采用亘观型显示器( d v s t ) 及随机扫 摇显示器，所生成的图形只能是线框图。生成线框图形所用算法相对简单， 通过透视变换和消除隐藏线也能产生具有真实感的图形。但线框图仅在线条 经过的地方给出图形信息，距丰富多彩的现实世界相差甚远。计算机真实感 图形是一种光栅图形。光栅图形显示技术的基本思想是，将显示屏幕划分成 像素阵列，使得屏幕上不同的区域可以填上具有相当大变化范围的相应于景 物表面区域的色彩或光强度，以此来逼近真的图像或图形。自从6 0 年代中期 以来，计算机科学一直在探讨具有真实感的计算机图形显示方法。到了7 0 年代初，包括存储器在内的各种硬件价格开始下跌，这使得光栅图形显示技 术与当时尚占优势的向量式显示技术相比，在性能价格比上逐渐显露出优越 性来。也正是显示硬件的这一转变，使得显示具有真实感的逼真图形成为可 能，同时也打开了研究各种方法的大门。到七十年代的后期，随着光栅图形 显示器的广泛应用，更是为产生真实感图形提供了可能性。 随着对真实感图形生成技术研究的不断深入，越来越精确的模型被建立 起来，越来越逼真高效的绘制算法被提出柬。同时，各种模型、算法的不断 实现使得基于该项技术的各种图形绘制软件逐渐发展起来。尤其到近2 0 年 硕士论文：嵌入式三维圈形引擎的设计与实现 来，随着多色彩高分辨率光栅图形设备的发展，以及对光学与热能传播、某 些数学分支和材料科学的研究，计算机图形的生成己由过去的近似模拟发展 到今天越来越逼真的地步，有的己达到以假乱真的水平，并被广泛应用到军 事、航空、航天、医学、地质勘探、文化娱乐和艺术造型等各个领域。随着 计算机软、硬件突飞猛进的发展，计算机图形学在各个行业的应用也得到迅 速普及和深入。目前，计算机图形学己进入三维时代，三维图形在人们周围 无所不在。科学可视化、计算机动画和虚拟现实已经成为近年来计算机图形 学的三大热门话题，而这三大热门话题的技术核心均为三维图形。当前，三 维图形己在军事、航空、航天、医学、地质勘探、文化娱乐和艺术造型等方 面有着十分广泛的应用。同时随着三维图形加速硬件性能的不断提高，以及 图形硬件加速器的广泛使用，基于嵌入式设备的三维图形应用系统发展迅速。 1 2 嵌入式系统简介 1 2 1 发展与历史 嵌入式系统的定义 按照历史性、本质性、普遍性要求，嵌入式系统应定义为：“嵌入到对 象体系中的专用计算机系统”。“嵌入性”、“专用性”与“计算机系统”是嵌 入式系统的三个基本要素。对象体系则是指嵌入式系统所嵌入的宿主系统。 嵌入式系统的特点 嵌入式系统的特点与定义不同，它是由定义中的三个基本要素衍生出来 的。不同的嵌入式系统其特点会有所差异。与“嵌入性”相关的特点：由于 是嵌入到对象系统中，必须满足对象系统的环境要求，如物理环境( 小型) 、 电气气氛环境( 可靠) 、成本( 价廉) 等要求。与“专用性”相关的特点： 软、硬件的裁剪性；满足对象要求的最小软、硬件配置等。与“计算机系统” 相关的特点：嵌入式系统必须是能满足对象系统控制要求的计算机系统。与 上两个特点相呼应，这样的计算机必须配置有与对象系统相适应的接口电路。 另外，在理解嵌入式系统定义时，不要与嵌入式设备相混淆。嵌入式设 备是指内部有嵌入式系统的产品、设备，例如，内含单片机的家用电器、仪 器仪表、工控单元、机器人、手机、p d a 等。按照上述嵌入式系统的定义， 只要满足定义中三要素的计算机系统，都可称为嵌入式系统。嵌入式系统按 形态可分为设备级( 工控机) 、板级( 单板、模块) 、芯片级( m c u 、s o c ) 。 有些入把嵌入式处理器当作嵌入式系统，但由于嵌入式系统是一个嵌入式计 2 硕士论文：嵌入式三维图形引擎的设计与实现 算机系统，因此，只有将嵌入式处理器构成一个计算机系统，并作为嵌入式 应用时，这样的计算机系统才可称作嵌入式系统。嵌入式系统与对象系统密 切相关，其主要技术发展方向是满足嵌入式应用要求，不断扩展对象系统要 求的外围电路( 如a d c 、d a c 、p w m 、日历时钟、电源监测、程序运行监 测电路等) ，形成满足对象系统要求的应用系统。因此，嵌入式系统作为一个 专用计算机系统，要不断向计算机应用系统发展。因此，可以把定义中的专 用计算机系统引伸成满足对象系统要求的计算机应用系统。 嵌入式系统的独立发展道路 ( 1 ) 单片机开创了嵌入式系统独立发展道路 嵌入式系统虽然起源于微型计算机时代，然而，微型计算机的体积、价 位、可靠性都无法满足广大对象系统的嵌入式应用要求，因此，嵌入式系统 必须走独立发展道路。这条道路就是芯片化道路。将计算机做在一个芯片上， 从而开创了嵌入式系统独立发展的单片机时代。在探索单片机的发展道路时， 有过两种模式，即“模式”与“创新模式”。“模式”本质上是通用计算 机直接芯片化的模式，它将通用计算机系统中的基本单元进行裁剪后，集成 在一个芯片上，构成单片微型计算机；“创新模式”则完全按嵌入式应用要求 设计全新的，满足嵌入式应用要求的体系结构、微处理器、指令系统、总线 方式、管理模式等。i n t e l 公司的m c s - 4 8 、m c s 5 1 就是按照创新模式发展 起来的单片形态的嵌入式系统( 单片微型计算机) 。m c s 5 l 是在m c s 4 8 探 索基础上，进行全面完善的嵌入式系统。历史证明，“创新模式”是嵌入式系 统独立发展的正确道路，m c s 5 1 的体系结构也因此成为单片嵌入式系统的 典型结构体系。 ( 2 ) 单片机的技术发展史 单片机诞生于2 0 世纪7 0 年代末，经历了s c m 、m c u 、s o c 三大阶段。 s c m 即单片微型计算机( s i n g l e c h i pm i c r o c o m p u t e r ) 阶段，主要 是寻求最佳的单片形态嵌入式系统的最佳体系结构。“创新模式”获得成功， 奠定了s c m 与通用计算机完全不同的发展道路。在开创嵌入式系统独立发 展道路上，i n t e l 公司功不可没。m c u 即微控制器( m i c r oc o n t r o l l e r u n i t ) 阶段，主要的技术发展方向是：不断扩展满足嵌入式应用，对象系统 要求的各种外围电路与接口电路，突显其对象的智能化控制能力。它所涉及 的领域都与对象系统相关，因此，发展m c u 的重任不可避免地落在电气、 电子技术厂家。从这一角度来看，i n t e l 逐渐淡出m c u 的发展也有其客观 因素。在发展m c u 方面，最著名的厂家当数p h i l i 引擎公司。p h i l i 引擎 3 硕士论文：嵌入式三维图形引擎的设计与实现 公司以其在嵌入式应用方面的巨大优势，将m c s 5 1 从单片微型计算机迅速 发展到微控制器。因此，当我们回顾嵌入式系统发展道路时，不要忘记i n t e l 和p h i l i 引擎的历史功绩。单片机是嵌入式系统的独立发展之路。向m c u 阶段发展的重要因素，就是寻求应用系统在芯片上的最大化解决；因此，专 用单片机的发展自然形成了s o c 化趋势。随着微电子技术、i c 设计、e d a 工具的发展，基于s o c 的单片机应用系统设计会有较大的发展。因此，对单 片机的理解可以从单片微型计算机、单片微控制器延伸到单片应用系统。 嵌入式系统的两种应用模式 嵌入式系统的嵌入式应用特点，决定了它的多学科交叉特点。作为计算 机的内含，要求计算机领域人员介入其体系结构、软件技术、工程应用方面 的研究。然而，了解对象系统的控制要求，实现系统控制模式必须具备对象 领域的专业知识。因此，从嵌入式系统发展的历史过程，以及嵌入式应用的 多样性中，可以了解到客观上形成的两种应用模式。 ( 1 ) 客观存在的两种应用模式 嵌入式计算机系统起源于微型机时代，但很快就进入到独立发展的单片 机时代。在单片机时代，嵌入式系统以器件形态迅速进入到传统电子技术领 域中，以电子技术应用工程师为主体，实现传统电子系统的智能化，而计算 机专业队伍并没有真正进入单片机应用领域。因此，电子技术应用工程师以 自己习惯性的电子技术应用模式，从事单片机的应用开发。这种应用模式最 重要的特点是：软、硬件的底层性和随意性：对象系统专业技术的密切相关 性；缺少计算机工程设计方法。 虽然在单片机时代，计算机专业淡出了嵌入式系统领域，但随着后p c 时代的到来，网络、通信技术得以发展；同时，嵌入式系统软、硬件技术有 了很大的提升，为计算机专业人士介入嵌入式系统应用开辟了广阔天地。计 算机专业人士的介入，形成的计算机应用模式带有明显的计算机的工程应用 特点，即基于嵌入式系统软、硬件平台，以网络、通信为主的非嵌入式底层 应用。 ( 2 ) 两种应用模式的并存与互补 由于嵌入式系统最大、最广、最底层的应用是传统电子技术领域的智能 化改造，因此，以通晓对象专业的电子技术队伍为主，用最少的嵌入式系统 软、硬件开销，以8 位机为主，带有浓重的电子系统设计色彩的电子系统应 用模式会长期存在下去。另外，计算机专业人士会愈来愈多地介入嵌入式系 4 硕士论文：嵌入式三维图形引擎的设计与实现 统应用，但囿于对象专业知识的隔阂，其应用领域会集中在网络、通信、多 媒体、商务电子等方面，不可能替代原来电子工程师在控制、仪器仪表、机 械电子等方面的嵌入式应用。因此，客观存在的两种应用模式会长期并存下 去，在不同的领域中相互补充。电子系统设计模式应从计算机应用设计模式 中，学习计算机工程方法和嵌入式系统软件技术；计算机应用设计模式应从 电子系统设计模式中，了解嵌入式系统应用的电路系统特性、基本的外围电 路设计方法和对象系统的基本要求等。 ( 3 ) 嵌入式系统应用的高低端 由于嵌入式系统有过很长的一段单片机的独立发展道路，大多是基于8 位单片机，实现最底层的嵌入式系统应用，带有明显的电子系统设计模式特 点。大多数从事单片机应用开发人员，都是对象系统领域中的电子系统工程 师，加之单片机的出现，立即脱离了计算机专业领域，以“智能化”器件身 份进入电子系统领域，没有带入“嵌入式系统”概念。因此，不少从事单片 机应用的人，不了解单片机与嵌入式系统的关系，在谈到“嵌入式系统”领 域时，往往理解成计算机专业领域的，基于3 2 位嵌入式处理器，从事网络、 通信、多媒体等的应用。这样，“单片机”与“嵌入式系统”形成了嵌入式系 统中常见的两个独立的名词。但由于“单片机”是典型的、独立发展起来的 嵌入式系统，从学科建设的角度出发，应该把它统一成“嵌入式系统”。考虑 到原来单片机的电子系统底层应用特点，可以把嵌入式系统应用分成高端与 低端，把原来的单片机应用理解成嵌入式系统的低端应用，含义为它的底层 性以及与对象系统的紧耦合。 1 2 2 市场总体特征 2 0 0 3 年，中国嵌入式操作系统市场处于快速增长时期。嵌入式操作系统 的总体销售额将超过r m b6 5 0 0 万，相对于2 0 0 2 年。整个嵌入式操作系统市 保持了快速的增长。在未来的几年内，嵌入式系统的发展将为几乎所有的电 子设备注入新的活力，由于迅速发展的i n t e r n e t 和非常廉价的微处理器的出 现，嵌入式系统将在我们的日常生活里形成一个更大的应用领域。消费电子、 交通运输汽车、电信服务网络工业都表现出对这个市场的关注，嵌入式操 作系统将继续保持迅速的增长。从嵌入式操作系统未来的技术演变趋势来看， 嵌入式操作系统在通讯，汽车，医疗，：安全方面有比较有广泛的应用。同时 在消费类的电子产品中，嵌入式操作系统也显示了较强的增长力。移动终端 设备p d a ，手机等移动终端设备的快速增长，大大促进了嵌入式操作系统的 发展。在竞争激烈的嵌入式操作系统市场中，各个嵌入式操作系统厂商依靠 5 硕十论文：嵌入式三维图形引擎的设计与实现 不同的产品定位在垂直市场上拥有着自己的优势。w i n d r i v e r 和m o n t a v i s t a 在通讯，医疗等垂直市场中拥有自己的优势，并且在操作系统和开发工具上 有自己的客户群。微软，p a l m ，s y m b i a n 和l i n u x 阵营则在消费类电子等领 域确立了自己的优势。信息产业部有关部对我国嵌入技术的开发和应用给予 了一贯的支持，无论从芯片研发、嵌入式操作系统、嵌入式数据库到应用系 统研发乃至推广应用，在政策导向、标准制定、电子生产发展基金立项，倍 增计划款项目和贴息等，对嵌入技术及其应用，都给予了力所能及的支持。 2 0 0 4 年3 月1 1 日，北京信息产业部与微软公司在北京签署合作备忘录，双 方同意合作共建国家软件与集成电路产业公共服务平台的相关实验室，微软 将与国内外i t 合作伙伴一道，共同建设基于w i n d o w s n e t 的平台软件及嵌 入式软件实验室。这些举措预示着2 0 0 4 年我国将加快包括嵌入式软件在内的 软件和集成电路产业的发展。到2 0 0 3 年截止，中国嵌入式操作系统的主要客 户分布在电信，医疗，汽车，安全和消费类等行业。同时，未来的嵌入式操 作系统的主要的增长动力来自消费类等行业。2 0 0 3 年，l i n u x 的支出在各个 行业的分布比较平均，其中电信占5 0 ，医疗2 0 ，汽车1 5 ，工业控制 1 5 ，消费类电子2 0 。虽然近几年嵌入式操作系统得到了快速的发展，但 嵌入式厂商的开发人员远远不能满足快速发展的市场的需求，几个大的嵌入 式厂商都面临缺乏研发人员的困境。其它软件产品一样，嵌入式操作系统的 厂商也受盗版软件的影响，不能够大量的卖给有需求的终端用户，从而影响 了嵌入式厂商的生存环境。随着整个嵌入式市场的快速成长，更多的开发人 员需要厂商的支持，嵌入式厂商也面临着技术支持和服务能力的压力。国家 政策的支持将推动我国软件产业和集成电路产业的发展，增加信息产业创新 能力和国际竞争力，带动传统产业改造和产品升级换代，进一步促进国民经 济持续、快速、健康发展。通过政策引导，鼓励资金、人才等资源投向软件 产业和集成电路产业，进一步促进我国信息产业快速发展，力争到2 0 1 0 年使 我国软件产业研究丌发和生产能力达到或按近国际先进水平，并使我国集成 电路产业成为世界主要开发和生产基地之一。鼓励国内企业充分利用国际、 国内两种资源，努力开拓两个市场。经过5 到l o 年的努力，国产软件产品能 够满足国内市场大部分需求，并有大量出口：国产集成电路产品能够满足国 内市场大部分需求，并有一定数量的出口，同时进一步缩小与发达国家在开 发和生产技术上的差距。消费类电子产品，手机，p d a 的快速发展会推动嵌 入式产品的快速发展，预计在未来的几年内，我国将成为世界上最大的消费 类电子产品的使用国，这也预示着消费类电子产品对于嵌入式操作系统预示 6 硕士论文：嵌入式三维图形引擎的设计与实现 着巨大的商机。嵌入式软件和硬件都有良好的发展前景，特别是在图形显示 相关的游戏等领域。 1 3 课题研究的背景和内容 当前，随着微电子技术和和无线通讯技术的发展，无线嵌入式设备越来越 多的应用到社会生活的各个领域，只能在无线嵌入设各上显示二维图形已经 越来越不能满足人们对于图形显示真实感的要求了，有越来越多的证据表明 未来手机等手持通讯设备上将会要求像在p c 机上一样的显示具有真实感的 三维图形。s a m s u n g 、n i v i d a 、q u a l e o m m 和其它芯片制造商巨头开始宣布推 出支持3 d 图形的芯片。tn i v i d a 与h i 公司合作，将h i 公司的( 装有 j 2 m e a p i ) 3 d 加速解决方案加入它的g o f o r e e 结构中。s a m s u n g 已经在2 0 0 4 年下半年开始供应能够满足3 d 游戏所需带宽的芯片。手机的3 d 游戏预期 在2 0 0 6 年变得普及。 而要在速度慢，内存小，显示分辨率低下的嵌入式设备上实时显示三维 图形，我们需要对已有的真实感图形学算法开展工程化，实用化的的研究， 并将研究成果应用于嵌入式设备中，使其可以实现高度真实感的模型，渲染 强烈的感染效果，进行逼真的模拟，本课题就是在这个大背景下开始研究的。 7 硕士论文：嵌入式三维幽形引擎的设计与实现 2 1 引言 第二章光栅图形学及几何变换 光栅显示器上显示的图形，称之为光栅图形。光栅显示器可以看作是一 个象素矩阵，在光栅显示器上显示的任何一个图形，实际上都是一些具有一 种或多种颜色和灰度象索的集合。由于对一个具体的光栅显示器来说，象素 个数是有限的，象素的颜色和灰度等级也是有限的，象素是有大小的，所以 光栅图形只是近似的实际图形。如何使光栅图形最完美地逼近实际图形，便 是光栅图形学要研究的内容。以后，我们提到“显示器”时，如未特别声明， 均指光栅显示器。 确定最佳逼近图形的象素集合，并用指定的颜色和灰度设置象素的过程 称为图形的扫描转换或光栅化。对于一维图形，在不考虑线宽时，用一个象 素宽的直线或曲线来显示图形。二维图形的光栅化必须确定区域对应的象素 集，将各个象素设置成指定的颜色和灰度，也称之为区域填充。任何图形光 栅化后，显示在屏幕上的一个窗口里，超出窗口的部分不予显示。确定一个 图形的哪些部分在窗口内，必须显示：哪些部分落在窗1 3 之外，不予显示， 这需要对图形进行裁剪。裁剪通常在扫描转换之前进行，从而可以对图形不 可见部分不必进行扫描转换。在光栅图形中，非水平和垂直的直线用象素集 合表示时，会呈锯齿状，这种现象称之为走样( a l i a s i n g ) ；用于减少或消除走 样的技术称为反走样( a n t i a l i a s i n g ) 。提高显示器的空间分辨率可以减轻走样问 题，但这是以提高设备成本为代价的。实际上，当显示器象素可以用多亮度 ( 或灰度) 显示时，可以通过调整图形上各象素的亮度来减轻走样问题 2 2 扫描转换算法 直线扫描转换算法 数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器 只能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个象 素中，确定最佳逼近该直线的一组象素，并且按扫描线顺序，对这些象素进 行写操作，这个过程称为用显示器绘制直线或直线的扫描转换。 由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽 可能地快。一个象素宽直线绘制的有三个常用算法：数值微分法( d d a ) 、 8 硕士论文：嵌入式三维图形引擎的设计与实现 和b r e s e n h a m 算法，中值算法。其中，b r e s e n h a m 算法效率高速度快，是目 前公认的最好的光栅化直线扫描转换算法。 b r e s e n h a m 算法：b r e s e n h a m 算法是计算机图形学领域使用最广泛的直线 扫描转换算法。仍然假定直线斜率在0 一一1 之间，该方法类似于中点法，由一 个误差项符号决定下一个象素点。 算法原理如下：过各行各列象素中心构造一组虚拟网格线。按直线从起 点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列象素中与此 交点最近的象素。该算法的巧妙之处在于采用增量计算，使得对于每一列， 只要检查一个误差项的符号，就可以确定该列的所求象素。 设直线方程为y i + 1 = y i + k ( x i + 1 一x i ) + k 。假设列坐标象素已经确定为x i ，其 行坐标为y i 。那么下一个象素的列坐标为x i + l ，而行坐标要么为y i ，要么 递增1 为y i + 1 。是否增1 取决于误差项d 的值。误差项d 的初值d o = 0 ，x 坐标每增加l ，d 的值相应递增直线的斜率值k ，即d - - - - d + k 。一旦d l ，就 把它减去l ，这样保证d 在0 、1 之间。当d 芝o ，5 时，直线与垂线x = x i + l 交 点最接近于当前象素( x i ，y i ) 的右上方象素( x i + 1 ，y i + 1 ) ：而当d 0 时，取当前象素( x i ，y i ) 的右上方象素( x i + 1 ，y i + 1 ) ；而当 e 0 时，取( x i ，y i ) 右方象素( x i + 1 ，y i ) 。 上述b r e s e n h a m 算法在计算直线斜率与误差项时用到小数与除法。可以 改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换： 2 + 8 4 d x 。 多边形的扫描转换： 在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表 示。顶点表示是用多边形的顶点序列来表示多边形。这种表示直观、几何意 义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多 边形内，敌不能直接用于面着色：点阵表示是用位于多边形内的象素集合来 刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是 面着色所需要的图形表示形式。光栅图形的一个基本问题是把多边形的顶点 表示转换为点阵表示，这种转换称为多边形的扫描转换。其本质就是连续量 的快速离散化。 多边形扫描转换算法对多边形的形状没有限制，但多边形的边界必须时 封闭的，且不自交。我们可以将多边形分为三种：凸多边形、凹多边形、含 9 硕士论文：嵌入式三维图形引擎的设计与实现 内环的多边形。所谓凸多边形是指任意两顶点问的连线均在多边形内；凹多 边形是指任意两顶点间的连线有不在多边形内的部分；而含内环的多边形则 是指多边形内再套有多边形，多边形内的多边形也叫内环，内环之间不能相 交。 圈2 _ 1 多边形的种类 扫描线算法：扫描线算法是按扫描线顺序，计算扫描线与多边形的相交区 间，再用要求的颜色显示这些区间的象素，完成转换工作。区间的端点可以 通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的扫 描转换过程可以分为四个步骤： ( 1 ) 求交：计算扫描线与多边形各边的交点； ( 2 ) 排序：把所有交点按x 值递增顺序排序； ( 3 ) 配对：第一个与第二个，第三个与第四个等等：每对交点代表扫 描线与多边形的一个相交区间， ( 4 ) 着色：把相交区间内的象素置成多边形颜色，把相交区间外的象 素置成背景色。 l ? 4 ( 1 1 ，l f 一，_ g p 6 、一一一 a b 、l c d 一 p 5 ( 5 ，5 ) 一 _ 一 y 3 ( 1 1 ， 一? p l ( 历、一一_ e p 2 争1 ) 。 圈2 j 一个多边形与若干扫描线 l o 硕士论文：嵌入式三维图形引擎的设计与实现 为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行 求交运算。我们把与当前扫描线相交的边称为活性边，并把它们按与扫描线 交点x 坐标递增的顺序存放在一个链表中，称此链表为活性边表( a e t ) 。 p g p lp 5 p 6p 4 p 5p 3 p 4 ad xy m a x bd xy r r l a x c x y m a x d6 x ，n 协x 幻扫描线6 的活性边表 p 4 p jp 3 p 4 叵e 田卫习习习 fg ( b ) 扫描线7 的活性边表 图2 - 3 活性边表( a e t ) 前扫描线与多边形某一条边的交点的横坐标为x ，则下一条扫描线与该 边的交点不必要重计算，只要加一个增量a x 即可，下面，我们推导这个结 论。 设该边的直线方程为：甜+ b y + c = o ，当前扫描线及下一条扫描线与边的 交点分别为0 ，) 、 f + l i + 1 ) ，则： a x 一b y f + c = oa x i + l + 幻十1 + 1 2 = 0 ， x 。= 去( - b ：t 咒+ ，一o ) 公式( 2 1 ) 由于咒。= 儿+ 1 ，所以t n = ( 七y 一一勺) - - x i - ：b ； 其中x = 一b a 为常数， 另外使用增量法计算时，我们需要知道一条边何时不再与下一条扫描线 相交，以便及时把它从活性边表中删除出去。综上所述，活性边表的结点应 为对应边保存如下内容：第1 项存当前扫描线与边的交点坐标x 值；第2 项 存从当前扫描线到下一条扫描线问x 的增量d x ；第3 项存该边所交的最高扫 描线号y 。 为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表 ( n e t ) ，存放在该扫描线第一次出现韵边。也就是说，若某边的较低端点为 。，则该边就放在扫描线蜘，。的新边表中。 硕士论文：嵌入式三维图形引擎的没计与实现 图2 _ 4 各条扫描线的新边表n e t 扫描线与多边形顶点相交时，必须正确地取舍交点，如图25 所示。 + 扫描线与多边形相交的边分别位于扫描线的两侧，则计一个交点，如点 p 5 ，p 6 。 扫描线与多边形相交的边分别位于扫描线同侧，且朋9 ，一l ，m 印，+ l ，则 计2 个交点( 填色) ，如p 2 。若y ，净，- 1 ，y ，：秒，+ 1 ，则计0 个交点( 不填色) ，如 p l 。 扫描线与多边形边界重合( 当要区分边界和边界内区域时需特殊处理1 ， 则计1 个交点。 具体实现时，只需检查顶点的两条边的另外两个端点的y 值。按这两个 y 值中大于交点y 值的个数是0 ，1 ，2 来决定。 2 3 裁剪 蚓2 _ 5 扫描线与多边形相交，特殊情况的处理 在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而 屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之内， 哪些落在显示区之外，以便只显示落在显示区内的那部分图形。这个选择过 1 2 8 7 6 5 4 3 2 1 0 硕士论文：嵌入式三维图形引擎的设计与实现 程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点