（电路与系统专业论文）纹理映射算法研究与FPGA实现[电路与系统专业优秀论文].pdf

中用科学技术人学烦f 学位论上 摘要 纹理映射在计算机图形计算中属于光栅化阶段，处理的是像素，主要的特点 是数据的吞吐量大，对实时系统来说转换的速度是一个关键的因素，人们寻求各 种加速算法来提高运算速度。传统的方法是用更快的处理器，并行算法或专用硬 件。随着数字技术的发展，尤其是可编程逻辑门阵列( f p g a s ) 的发展，提供了 一种新的加速方法。i 即g a s 在密度和性能上都有突破性的发展，当前的f p o a 芯片已经能够运算各种图形算法，而在速度上与专用的图形卡硬件相同。因此， f p g a 芯片非常适合这项工作。 本文主要工作包括以下几个方面： i 、本文提出了一种m i p m a p p i n g 纹理映射优化方法，改进t m i p m a p p i n g 映射 细化层次算法及纹理图像的存储方式，减少纹理寻址的计算量，提高纹理存储的 相关性。详细内容请阅读第三章。 2 、提出了一种m i p m a p p i n g 纹理映射优化方法的硬件实现方案，该方案针对 移动设备对功耗和面积的要求，以及分辨率不高的特点，在参数空间到纹理地址 的计算中用定点数来实现。详细内容请阅读第四章。 3 、实现了纹理映射流水线单元纹理地址产生电路，及纹理滤波电路的f p g 陡 设计，并给出设计的综合和仿真结果。详细内容请阅读第五章 4 、实现了符合1 e e e7 5 4 单精度标准的乘法、乘累加及除法运算器电路。乘 法器采用改进型b o o t h 编码电路以减少部分积数量，用w a l l a c e 对部分积进行压 缩；乘累加器采用m u l t i p l y a d df u s e d 算法，对关键路径进行了优化；除法器为基 于改进型泰勒级数展开的查找表结构实现，查找表尺寸只有2 0 8 字节，电路为固 定时延，在电路尺寸，延时及复杂度方面进行了较好的平衡。详细内容请阅读第 六章 关键词：实时纹理映射走样f p g a 浮点 中田科学技术人学坝 ：学位论文a b s t r a c t a b s t r a c t i nt h e3 d g r a p h i c sh a r d w a r ea c c e l e r a t o r s ，t h et e x t u r em a p p i n g i sb e l o n g e dt op i x e l s p r o c e s s i n gp h a s e t h i sp h a s ei sg e n e r a l l yc o m p u t a t i o n a l l ye x p e n s i v e t h i sf a c ti st h e r e a s o nw h y p e o p l es t r u g g l et oa c c e l e r a t es u c ha l g o r i t h m su s i n ga n yr e a s o n a b l em e a n s t h et r a d i t i o n a ls o u r c e so fs p e e d u pa r cf a s t e rp r o c e s s o r s ，p a r a l l e l i s m ，o rd e d i c a t e d h a r d w a r e d e v e l o p m e n ti nd i g i t a lc i r c u i tt e c h n o l o g y , e s p e c i a l l yr a p i dd e v e l o p m e n to f f i e l dp r o g r a m m a b l eg a t ea r r a y s ) 晤g ，o f f e r sa l t e r n a t i v ew a yt oa c c e l e r a t i o n c u r r e n tf p g ac h i p sh a v ev e r yh i g hd e n s i t ya n dc a p a b i l i t y , a r ec a p a b l eo fr u n n i n g g r a p h i c sa l g o r i t h m sa t t h es p e e dc o m p a r a b l et od e d i c a t e dg r a p h i c sc h i p s s ot h e f p g a c h i p sa r ev e r ys u i t a b l ed e v i c e sf o rt h i st a s k t h i sp a p e ri n c l u d e ： 1 i nt h i sp a p e r , w ep r o v i d ea no p t i m i z e dm i p m a p p i n gt e x t u r em a p p i n ga l g o r i t h m s t h i st e c h n i q u ei si m p r o v e do nm i p m a p p i n gc a l c u l a t ea n dt e x t u r ei m a g e ss t o r a g e m a n n e r , t or e d u c i n gt h ec o m p u t a t i o n a lc o s ta n di n c r e a s et h er e l a t i v i t yo ft e x t u r e w ed e s c r i b et h e mi nc h a p t e r3 2 as c h e m ei sp r o v i d e da b o u th a r d w a r ei m p l e m e n to fm i p m a p p i n g s i n c e ，t h e p o r t a b l ed e v i c ei sr e q u i r e ds t r i c tw i t hc o m p u t a t i o na n dc h i pa r e a ，a tt h es a m et i m e ， i t ss c r e e ns i z ei ss m a l l s o ，w eh a v ef i x e dp o i n tn u m b e rt oc a l c u l a t et h et r a n s f o r m b e t w e e np a r a m e t e rs p a c ea n dt e x t u r es p a c e t h e s ea r cd e s i r e do nc h a p t e r4 3 w ed e s i g nt h et e x t u r ea d d r e s sg e n e r a t i n gc i r c u i ta n dt e x t u r ef i l t e r i n gc i r c u i to n f p g a ，m o r e o v e r , w ep r o v i d et h er e s u l to fs y n t h e s i sa n ds i m u l a t i o n t h e s ea g e s h o w e do nc h a p t e r5 4 w ea l s od e s i g n e dam u l t i p l i e r ，am a ca n dad i v i d e r , w h oa r ea c c o r d e dw i t hi e e e 7 5 4s i n g l ep r e c i s i o ns t a n d a r d m u l t i p l i e ru s et h em o d i f i e db o o t he n c o d i n gt o r e d u c et h en u m b e ro fp a r t i a lp r o d u c t s ，a n dw a l l a c et r e ei su s e dt or e d u c et h e l a t e n c y m u l t i p l y a d di n t r o d u c em u l t i p l y a d df u s e da l g o r i t h m s t h ek e yr o u t ei s o p t i m i z e d d i v i d e ri sb a s e do nm o d i f i e dt a y l o rs e r i e se x p a n s i o na n dl o o k u pt a b l e ， t h el o o k u pt a b l ei so n l y2 0 8 b y t e s ，a n df i x e dl a t e n c yp i p e l i n e d w es h o wa9 0 0 d b a l a n c eo nc h i pa r e a , l a t e n c ya n dc o m p l e x i t y w ed e s c r i b et h e mo nc h a p t e r6 - k e yw o r d s ：r e a l t i m e t e x t u r em a p p i n g a l i a s i n g f p g a f l o a t i n g p o i n t h 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 乏 作者签名： 簿红 歹伊d 乜年互月升日 1 、， 、孑 中国科学技术人学硕士论文 绪论 第一章绪论 真实感图形是一种应用计算机图形学算法生成图形的技术，而二十世纪七十 年代中期表面纹理的提出，大大加快了计算机合成图像的真实感进程。表面纹理 技术对物体表面贴上纹理图像，使计算机产生的图像更具真实感。人们探索了许 多的纹理技术，纹理己成为现今图像合成中的一个期望的重要特征，纹理映射技 术是绘制复杂场景真实感图形最为常用的技术之- - 1 1 1 1 2 1 。 1 1 研究意义 在计算机图形学中，引入注目的研究方向之一是图形的真实感问题。图形的 真实感是计算机所生成的图形反映客观世界的程度。长期以来，图形真实感问题 一直是计算机图形学研究的一个主要课题。随着计算机技术的飞速发展，其应用 越来越广泛，某些应用领域( 计算机艺术造型、计算机制作、三维游戏、计算机 娱乐和广告动画设计等) 已把高度真实感的图形作为其发展的目标，要求我们能 逼真地在计算机屏幕上再现真实世界。纹理映射是提高计算机产生的图像真实感 最为有效的方法，它是将一幅程序图像或实际图像映射到三维场景的过程，如同 给墙贴墙纸。纹理映射用于图像综合的绘制技术，好处是给场景增加更多细节， 但所需增加的渲染时间并不多。纹理映射不影响隐藏面消除，只是在绘制过程中 增加很小的开销，该项技术也可很容易用到曲面上。 计算机图形学除了在个人计算机及工作站上大量应用外，随着电子技术及个 人电子产品不断发展，诸如p d a 、汽车导航系统、第三代( 3 g ) 移动电话等领 域都得到了大量的应用。尤其是3 g 手机，在一些发达的市场，具备游戏、动画、 广告等功能已经成为必备的选择。这类产品相对于个人计算机、图形工作站的应 用有较大的区别，通常都是基于嵌入式系统的专用电路，对芯片的能耗、面积、 价格等方面都有特定的要求 2 1 1 3 1 。开发出低功耗，低成本的专用图形加速器有 着广阔的应用前景，同时也是科技术创新，走拥有自主知识产权的必由之路。 在图形硬件加速研究中，纹理映射一直是一个主要的研究内容。纹理映射处 于绘制流水线的像素处理阶段，这个阶段的特点是数据的吞吐量及运算量都非常 大。对于实时系统来说，速度是一个关键性的问题，软件加速必须是基于高性能 的c p u ，专用图形系统所有算法必须是基于硬件加速的。通常硬件加速的速度 可以达到软件的1 0 0 倍。甚至更高。 1 2 国内外研究现状及分析 对于图形加速器来说，经历了大概4 个发展阶段 4 1 1 5 1 , 第一代是线框 ( w i r e f r a m e ) 显示，顶点处理主要完成转换、裁剪及投影，光栅化完成的是点线 的颜色插值，这个阶段在1 9 8 7 年之前。第二代是着色体( s h a d e ds o l i d s ) ，加入 了顶点灯光计算，光栅化采用基于三角形的深度插值，同时发展了深度缓冲及颜 色混合。这个时期段在1 9 8 7 1 9 9 2 年之间。第三代是纹理贴图( t e x t u r em a p p i n g ) ， 时间在1 9 9 2 2 0 0 0 年间。这时加入了基于顶点的纹理坐标转换，光栅化阶段采用 纹理坐标插值，实现了纹理评估及反走样技术。随着可编程管线 ( p r o g r a m m a b i l i t y ) 的出现，在2 0 0 1 年开始出现了第四代。这时的图形芯片加入 离可编程明暗处理、基于图像的绘制、集成了图形多媒体处理，并可对曲面进行 纹理等的操作。作为s g l 公司的创始人，目前在斯坦福和n v l d a 的k u r t a k e l e y 预 测，第五代图形硬件可称为g l o b a le v a l u a t i o n ，面临和处理的问题有真实阴影、 光线跟踪，光子映射、以及其它光照技术。图形学发展可以说是当前计算机技术 最为突出的一个领域，对人们的生活产生了巨大的影响。 纹理映射最早期的开拓者应归功于c a m u l l ，他可能是第一个于1 9 7 5 年将纹理 图案( 砖块) 映射到平面和圆柱体上。b l i n n 和n e w e l l 在1 9 7 6 年把这个方法更进一 步推广这个概念，他们把照片纹理映射到并表示出一个新的茶壶。a o k i 、l e v i n e 在1 9 7 8 年和f e i b u s h 等各自用这种技术将合成纹理映射绘制到个房子的3 d 模型 上。f e i b u s h 和g r e e n b e r g 也开发了一种纹理映射系统用于建筑设计。之后， e c o n o m y 、b u n k e r a 和b u n k e r 等于1 9 8 4 年提出计算机合成“te l l ”纹理概念，在可视 化飞行模拟器上用来产生地形地貌。d u n g a n 等于1 9 7 8 年用实际的照片纹理图案 来产生地形。在以后的实践中，各种纹理映射模式在仿真器中得到了大量的应用， 纹理映射技术发展也就起来快，越来越重要。 纹理映射技术主要有双线性映射、仿射映射及投影映射【6 】【7 h 8 1 【9 1 【1 0 】【1 1 1 ， 目兹采用的大都是投影映射，主要是由于透视投影能产生透视缩短的效果，它的 逆向和前向映射都是单值的，便于实现。纹理映射技术更为关注是纹理采样的数 量及采样纹理重建时的滤波问题，也就是要解决所谓的走样及图像模糊问题。纹 理反走样分为各向同性及各向异性两种基本类型，在当前的个人计算机及图形工 作站中基本都对这两种算法采用不同程度的支持，不管它们是不是实时系统。对 于3 d 手机、p d a 、汽车导航系统等产品，更为关注的算法的复杂性、实时性、 能耗及芯片面积，同时由于这类产品的屏幕分辨率的限制，所以标准的 m i p m a p p i n g 纹理映射算法是移动产品必然的选择。这种算法易于硬件实现，纹 理存储花费不大，产生的图像质量较好。更为重要的是，由于它每个像素访问纹 理的数量是固定的，计算的时间也是一个常数，解决了实时系统带宽总是有限及 延迟的问题。 中国科学技术大学硕士论文绪论 1 3 选题依据 在过去十几年里，3 d 图形卡工业有了显著的发展，尤其是个人便携式数字 设备，如3 d 手机、p d a 等，多媒体变得越来越重要，要求实现实时3 d 图形，如 广告、游戏、导航等。 个人多媒体产品已经成为电子工业一个重要的增长点，韩国、日本及西方主 要发达国家已经达到广泛应用阶段，并不断开发出更有竞争力的产品。我们希望 关注这方面的内容，做一些尝试性工作。 另外，随着数字技术及集成电路的发展，尤其是可编程逻辑门阵列( f p g a s ) 的发展，在各种柔性平台上得到了广泛的应用，也为我们提供了一种新的设计选 择。当前的f p g a s 在密度和性能上都有突破性的发展，最近期的f p g a 芯片已 经能够运算各种图形算法，而在速度上与专用的图形卡硬件相同。因此，f p g a 芯片非常适合这项工作。 1 4 论文内容安排 本文的内容组织如下： 第二期章关注的是纹理映射中相关的问题，这些问题主要包括纹理映射方 法、纹理映射中的走样及反走样，最后对几种快速反走样算法进行分析和比较。 第三章仔细研究了m i p m a p p i n g 算法的实现。接下来第四章对m i p m a p p i n g 算法 中纹理地址产生电路及滤波电路进行了研究及实现，并给出实验结果。第五章完 成的是透视校正纹理映射地址计算中所需要的浮点运算器的设计工作。最后一章 对本文的工作做了个总结，并对未来的需要改进及进一步的工作提出计划。 中国科学技术大学硕士论文2 d 纹理映射技反走样 第二章2 d 纹理映射及反走样 纹理映射就是将任意的平面图形或图像覆盖到物体表面，在物体表面形成真 实感的表面细节。纹理映射涉及纹理空间、景物空间( 目标参数空间) 、屏幕空 间三个空间的映射1 1 2 1 1 1 3 。 i 蚋甸前向 映射映射 _ 卜 图2 1 纹理映射 纹理映射通常采用的是逆向映射，即由屏幕空间向纹理空间进行映射。纹理 映射一般分为两步，先将屏幕空问的点。r ，) ，) 投影到参数空间( m ，加) ，这时可采用 的方法有仿射映射、双线性映射及投影映射。再将参数空间坐标铆，加) 转换到纹 理空间的纹理像素点的坐标似，n 。读取对应的纹理值后进行后处理，并取代原屏 幕像素颜色，就完成了整个映射过程。 纹理过程中的主要问题是，首先是走样问题，即所要访问的纹理数量及这些 纹理对最终的屏幕像素颜色的作用大小，其次是映射方法，要有利于参数计算。 这章节的主要任务就是要分析纹理走样的原因及反走样的方法，同时对各种 纹理殃射方法遴行分析与比较。 2 1 采样及滤波理论 2 1 1 走样现象( a l i a s i n g ) 由于计算机生成的图形是由离散点组成的数字化图像，因而生成的图形必然 与真实景物之问存在误差。这种误差表现为图形上的直线或光滑的曲线呈现锯齿 状、彩色花纹失去原有的形态和色彩、细小物体在画面上得不到反映等。在计算 机图形学中，上述问题称为图形走样( a l i a s i n g ) 。 在进行纹理映射时，采用点采样读取纹理像素时，是将屏幕像素中心映射到 纹理空间，读出离其最近的纹理像素的值。这种方法简单、快速，对纹理图像与 屏幕图像大小一致时效果很好。当被采样的纹理图像与屏幕图像大小不一致，也 就是存在纹理放大及纹理缩小时，避免不了会产生走样现象，称为纹理走样 4 中国科学技术大学硕士论文2 d 纹理映射发反主样 ( t e x t u r ea l i a s i n g ) 【1 2 1 。在静态图像中表现为边缘锯齿、色块或是小的图案无法 显示等，在动画中，波纹会一帧一帧地沸腾和闪烁。这种走样在现实的图像和动 画中都是不能容忍的。 2 1 2 走样产生的原因 一个连续信号在数字信号处理时，首先对其进行离散化。即采样( s a m p l e ) ， 然后量化得到二进制编码，这是我们进行运算、再加工的对象。最后对这些处理 过的数字信号还要还原成自然界中的连续信号，这个过程称为重建 ( r e c o n s t r u c t i o n ) 。能否完整地重建连续信号也就是决定了是否会产生走样。 巡，巡， i 衄。秭衄， l 燃。燃， 图2 2n y q u i s t 频率以上的采样( 无走样) 图2 3n y q u i s t 频率以下的采样( 走样) 事实上，每一幅数字化图像都可认为是对真实画面的一个采样，分辨率( 即 图像中所含像素的个数) 的高低表示采样的频率的高低。形象地说，图像中的细 节( 如景物轮廓边、画面上光亮度急剧变化区域或细小物体) 反映了该图像的高 频分量，图像中的大致形态则反映了图像的低频分量，因而当采样频率过低( 即 分辨率过低) 时，图像的细节就会丢失。根据采样理论，要想得到比较好的采样 信号( 也就是说，可以基于采样信号来重建原始信号) ，采样频率必须大于被采 样信号最高频率的两倍，这个频率称为n y q u i s t 频率。当信号采样频率过低的时 候，重建后的图像通常会产生走样。 中国科学技术大学顾l ：论文 2 d 纹理映射及反走样 图2 。2 是在n y q u i s t 频率以上进行的采样，这时能很好地重建原始信号，没 有走样；图2 3 是在n y q u i s t 频率以下进行的采样，重建信号与原始信号存在着 差异，出现了走样【1 2 】【1 3 】【1 4 】【1 5 1 【1 6 1 。 为了解释重建在走样中所扮演的角色，这里复习采样理论，定义采样和重建 的一些操作。一维信号可以用一个连续函数来胎) 表示，通过乘以一个称为梳状 函数的无限脉冲列来进行采样，得到一个离散的信号： 无g ) 一，仁) c o m b ( x ) ( 2 ，1 ) 这里c o m b ( x ) y6 b 一 ) 。 i 兰 假设式( 2 1 ) 采样点为单位间隔，d ( x ) 称为d i r a c 函数。根据采样定理， 如果采样频率小于半个周期，即大于n y q u i s t 频率，则可由采样信号重建厂( 工) 。 重建是通过离散信号与一个滤波器核进行卷积来得到的： ，g ) 无b ) 七b ) 一f 只缸) j | b 一“mt ，如) 七扛一n ) ( 2 2 ) - - w i 女 f 是连续信号， g ) 采样后的信号， b ) 是重建后的信号，k ( z ) 为重建滤 波器。除了在数学上的理想情况，在采样及重建中都会引入误差，f ( x ) 与 ( 工) 总有差异。为分析这种差异，在频域看这个问题可能会更好些。设信号，( x ) 的 傅里叶变换的频谱为f ( v ) ，滤波器的傅里叶变换的频谱为k ( v ) ，y 为频率。 因为空间域的积在频域可用卷积来表示，采样可以表述为： 只d ) 一f ( v ) * c o m b ( v ) ( 2 3 ) 重建可以写成： t ) 一只扣) 置( v ) ( 2 4 ) 梳状函数的傅里叶转换仍然是梳状函数。 一r k 。万1 一 v 图2 4 频域空间的采样与蕈建 图2 4 显示了式( 2 3 ) 卷积的结果，被采样信号的频谱只( v ) 是原始信号的频 谱的移位复制的无限序列和，它们的中心在梳状的脉冲上。式( 2 4 ) 表明，在 频域重建可以解释为乘以k ( p ) ，k ( v ) 在图2 t 4 中用虚线表示，认为是消除了 信号频谱所有无关的重复，只保持最初的位于原点的基带。 图2 4 也说明了一个问题，信号频谱有混叠，重建滤波器没有只隔绝纯粹的 基带信号。当重复的频谱的部分能量进入要重建的信号，就会产生走样。如果信 6 号带宽再窄一点或者采样频率更高一点，重复的频谱就不会有交迭，则有可能精 确地重建【4 】1 1 2 】。 然而，既使重复的频谱没有交迭，也有可能由于差劲的重建而出现走样。我 们这里假设已经对带宽受限信号采样完毕，这种情况与已经离散化的纹理图像相 一致。接下来我们讨论用这些采样信号重建原始信号。为此需要用到滤波器，图 2 5 所示为常用的3 种滤波器。 图2 5 几种滤波器：a ) 箱式滤波器械；b ) 蓬式滤波器：e ) s i n c 使用箱式滤波器( 最邻近的) 来重建信号，由于得到的信号结果是非连续的 阶梯状，因此这种滤波器非常差。但是，因为在形式上非常简单，所以在计算机 图形学中依然广为应用。 箱式滤波器可以由任何其它的滤波器代替。篷式滤波器( 亦称为三角滤波器) 用来重建信号时，是在相邻样本之间采用了线性插值，效果就要比箱式滤波器好， 得到的信号也是连续的。然而，这种滤波器重建信号光滑度并不是很好，在采样 点处有突然的斜度变化。 为了得到令人满意的结果，必须使用理想的低通滤波器，信号的每个频率分 量应该是一个正弦波：s i n ( 2z d ，其中，是该分量的频率。理想的低通滤波器是 s i n e 滤波器： s i n c 0 ) ，兰! 堕型( 2 5 ) 7 中国科学技术大学硕- | ：论文 2 d 纹理映射及反走样 如图2 6 所示，使用s i n c 滤波器进行信号重建，可以得到比较光滑的结果。 它能够去除所有频率大于采样频率一半的分量，这在信号重建时是非常有用的。 但这种函数的滤波宽度是无限的，有时还会出现负数，所以并不实用。 图2 6 使用s i n c 滤波器重建信号 另一个问题是重采样，就是对样本信号进行放大或者缩小。假设原始样本点 都处在整数坐标值上( 0 ，1 ，2 ) ，也就是说，相邻样本点之间的距离都是一个单 位。假设在重采样后需要均匀定位新的样本点，样本点间距离是d 。如果口大于 1 ，那么信号就被缩小了( 减采样，d o w n s a m p l i n g ) 如果a 小于1 ，信号则被放 大了( 过采样，u p s a m p l i n g ) 。 图2 7 重采样：放大 ( 左图为采样信号与重建信号，右图以一半的样本频率对重建信号进行采样) 放大是两者中比较简单的一种。由于信号已经重建而且是连续的，这时只要 以所要求的时间距离来对重建信号进行重采样就可以了。见图2 7 。 图2 8 熏采样：缩小 ( 左图为采样信号与熏建信号，右图以一倍的样本频率对熏建信弓进行缩小) 8 图2 8 为重采样中的缩小，这时的情况与放大不一样。由于采样频率减小， 原来的重建信号频率对滤波器来说就过高了。这时所要做的就是在重采样前对重 建信号进行滤波，除掉高频成份。 2 1 3 反走样 一般来说，只要在生成图形时采用点采样技术，都会导致图形走样现象，解 决图形走样问题的最根本方法一是在更高的频率上进行采样在使用点采样绘制 三维场景的时候，一般不对场景进行带宽限制。但是，多边形的边缘、阴影边界， 以及其他一些现象会产生非连续变化的信号，频率可能会无限大。此外，不管采 样距离多小，物体仍然可以小到根本无法采样的程度。而且在很多情况下这样做 是不现实的，它会导致运算量和存储器增加太大，因此，在使用点采样绘制场景 的时候，就不可能完全避免走样问题。通常的做法是使用面积采样来代替点采样 【4 】【1 7 】 面积采样的特点是对于每个屏幕像素在纹理空间采样多个纹理，每个纹理赋 予权重，即根据每个纹理的对最终像素的影响来确定权重大小。在实际应用中， 权重的赋值方式取决于所选择的滤波器。下式为基于多纹理像素采样加权表达 式： p k y ) 一罗w l c ( f ，x , y ) ( 2 6 ) 蔼 式中雕，) ，) 为最终的屏幕像素颜色值，c ( i ，x ，y ) 为被采样纹理，w i 纹理的权重， 其值在【o ，1 】之间，对以个纹理进行采样，权重之和为1 。 另一种处理方法是对原始的连续信号进行前置滤波( p r o - f i l t e r i n g ) ，但表现图 像细节的高频特性可能损失，造成图像模糊。对于计算机中处理的已经离散后的 图形图像，我们这里不考虑这个问题。 图2 9 采样前进行前置滤波 信号采样完毕，就是信号的重建，为此需要用到滤波器。如前所说介绍的几 种滤波器：箱式滤波器、篷式滤波器、s i n c 滤波器都有各自的特点及缺点。虽然 在实际图形学中由于箱式滤波器的简单及易于实现，用的比较多，但高斯滤波器 也是一种较好的滤波器，它接近理想低通滤波器s i n c ，在各种实时图形学中，应 9 中国科学技术大学硕j j 论文 2 d 纹堙映射发反走样 用越来越普遍。当然，一般的应用方法是对其进行指数运算采样用查找表结构来 降低运算的复杂度，提高运算效率。 2 22 d 纹理映射 由于显示器只能用二维空间来表示图形，要显示图形就要用投影的方法来降 低维数。将一个源空间的点映射到目标空间，依据的是映射函数的不同。常用的 投影方式有仿射映射、双线性映射及投影映射1 1 2 1 1 1 7 j 。 2 2 1 仿射映射( a f f i n em a p p i n g s ) 仿射映射包括缩放、旋转、转换和裁剪，它们是线性映射加上一个转换。形 式上，当且仅当对任何缩放系数口有丁协+ 力= z 毽) + 丁) 和霸蕊) = a 砸，时，一个映 射瓦；j f ) 为线性的；一个映射z 酶) 是仿射映射，则必须存在一个常数c 和一个线性映 射l 对所有白钮x 都有z 铆= l + c 。很显然，线性映射是仿射映射的一个子集。 一个2 d 仿射映射可以用代数式表示： 只，p ，m “ f 4 d 0 1 gy1 ) - 0 v 1 l b b 0 i ( 2 7 ) i c ，1j 转换矩阵表示为肘矗，口是初始坐标系统，6 是最终的坐标系统。注意，不失一般 性，我们这里选择w = q = l 。3 x 3 矩阵 倒有6 个自由度。几何学上，向量0 ，回和 散0 为目标空间基本向量，( c ，) 为原点。 图2 1 0 仿射映射 图2 1 0 仿射映射保持了平行线和保持了沿着线的点间隔平均( 也就是说，源 空间沿着直线平均间隔的点，在目标空间也同样是沿线平均问隔的，尽管这两个 坐标系统不一定相同) 。我们能只要简单地对映射矩阵 幻取逆，就可得到目标 到源的逆向仿射映射转换。同样地，仿射映射可以通过连接它们的矩阵来组成。 既然仿射映射有6 个自由度，在几何上它可以在源坐标和目标坐标中用3 个相 应的点来定义。如果这3 个点在两个空闽中是菲共线的，则映射和逆变换不会退 化。为了推出从3 个相应的点 i ，n ) 映射到陬，儿) 仿射映射矩阵( 七= 0 ，l ，2 ) ， 我们写出下面的等式： 1 0 中国科学技术人学硕士论文2 d 纹理映射及反走样 ；( 兰萋刁一( 兰兰顶l ；习 c 2 8 ， 2 2 2 双线性映射( b i l i n e a rm a p p i n g s ) s o u r c es p a c e i d e s t i n a t i o ns p a c e 图2 1 1 双线性映射 双线性映射最普通的定义是将一个正方形映射成四边形。如图2 1 1 ，这个映 射可以沿着四边形边从上到下用小数“来线性插值计算，再用小数v 在两个插值 点线性插值来产生最终的点( x ，y ) ： 仁，y ) - ( 1 一u x l 一v ) p 。+ ( 1 一v ) p 。+ ( 1 一邸) 甲。，+ u v p 。， ( 2 9 ) 用矩阵表示的普通形式为： 0 ，) ，) 一( u v - 麒 ( 2 1 0 ) 如果仿射映射中的口= e = 0 就成为双线性映射。从图2 1 1 中的四个点可以算 出矩阵的8 个参数： a e bf cg d h l 一1 1 l ( x y o o 一1lo o 忡。y ” 一10 1 00 y l00 o h y l l ( 2 1 1 ) 该映射将一个单位正方形转换成一般四边形p 0 0 ，p 1 0 ，p l l ，p 0 1 ，仿射映射则 不行。 双线性映射是一个与众不同的特性的混合。由于它是线性插值t 从源空白j 到 目标空间的前向转换保持了源空间的水平或垂直线还是直线，保持了直线上的点 的平均间隔，但它不能保证对角线，如图2 ，1 2 。另外，两个双线性映射组合不是 双线性映射，而是四次方程式。 、 ，、， 、 ，7 、 、 ： = ，、：，： f ， ， ： ： ： l 、 ：、 ： ： 、， 、 、 、， ，、 ，夕：、， 、 图2 1 2 双线性映射：a ) 源空间；b ) 、c ) 目标空间 从目标空间到源空间的逆向映射也不是双线性映射，事实上它不是单值的。 将善式中的v 用正式代入： v 。x - b u - d ( 2 1 2 ) a u + c 同理y 式中的“也代入得： ( a u + c ) ( 卢+ j i l y ) - ( e u + 譬) ( 妇+ d x ) = 0 ( 口y + 6 ) ( + _ i l y ) 一( 纠+ g ) ( 卯+ d x ) 。0 ( 2 1 3 ) 所以 a u2 + b u + c o d v 2 + e v + ，；0 ( 2 1 4 ) 这里 a 西一b e ，b m 践一时+ o h d e + c f b g ，c = g x c ) + c h d g d - a g 一卯，e - “一掣+ 砒一如+ c ，一船，f 一声一妙+ b h 一彤 ( 2 1 5 ) 中国科学技术大学颈上论文2 d 纹理映射及反走样 能发现通过计算参数a 、b 和c ，再依据( z ，y ) 可以算出( 甜，y ) ： f 2 1 6 ) 它的逆转换是多值的，相对于前身映射来说，计算要困难得多。 2 2 3 投影映射( p r o j e c t i v em a p p i n g s ) 投影映射，也称为透视或齐次转换，就是通过一个点从一个平面投影到另一 平面。齐次转换广泛地用于3 d 仿射转换和透视相机转换。我们这里研究的2 d 投影映射是与3 d 齐次转换相似的一个子集。 投影映射的一般形式是一个有理线性映射： 毒a u + b ：_ y + _ c ，y d u + e _ v + _ f ( 2 1 7 ) g 雄+ 以p 4 - f g u + i v 十l 用齐次矩阵形式处理投影映射更为容易： 只- p ，m “ f a d 9 1 一g y ，) 一0 v q l b ehl ( 2 1 8 ) i c f fj 这里似y ) = o 肋，y w ) 且w o ，0 ，= q ，v q ) 且口o 。 尽管在上面的矩阵中有9 个参数，这些映射是齐次的，所以任何非零标量与 这些矩阵乘得到相等的映射。因此，在2 d 投影映射中只有8 个自由度。不失一 般性，除了点( 0 ，0 ) 映射到无穷远处的特殊情况，我们可以设i = l 。当g = h - - o 时，投影映射成为仿射映射。 投影映射一般将无穷远处理直线投影到实际平面一条直线。通过分析透视投 影，我们可能认为这条线为所有水平线的消失点。仿射映射是投影映射的特殊情 况，它将无穷远处直线映射到本身。定义投影平面上的投影映射，不仅是实际平 面，投影映射成为双向单射，当映射矩阵是单一的除外。对非退化的映射，前向 映射和逆向映射都是单值的，就象一个仿射映射。 投影映射享有仿射映射许多可贵的特色，不象双线性映射，它沿着某一线平 均地分布各点，投影映射一般不保持平均分布点( 图2 ，1 2 ) 。用点的“c r o s sr a t i o ” 称呼来代替平均分布各点。象仿射映射，投影映射在所有的方向上保持线。事实 上，投影映射是最普通的线保持双向单值映射。投影映射可以组合它们的矩阵来 组成。 另一个值得称道的特性是它的逆映射也是投影映射。逆映射： p l = p d m n 中国科学技术大学硕士论文 2 d 纹理跌射发反走栉 一函v g ) 一b f e i 一，g 唐一刎d h e g - g y w l c h b i a l 一c g6 9 a hi( 2 1 9 ) 【6 ) 。- - c ec d 一巧4 e - b d j 逆映射将一个点( 工，) ，) 映射到点 ，d ，如果w o ，q o ，我们可以取w = l ，有下 式： u = 揣，矿一淼2 0 )瓯+ 协+ ，7繇+ 协+ j 2 3 快速纹理反走样 常用的纹理算法有c a t m u l l 算法和b l i n n 算法。由于这两种技术对每个像素 区域均要计算图像空间到景物空间、景物空间到纹理空阃之间的映射对应关系， 因而其计算量非常大。为避免实时和重复计算，一个较好的方法是采用查找表技 术。目前常用的查找表技术有三种，它们分别是椭圆加权平均技术、m i p m a p p i n g 技术和区域求和表技术。 2 3 1 点采样 纹理贴图最简单方法是以点取样f 1 9 】方式从纹理图像中读取数据：将屏幕像 素映射到纹理空间，读出最近的纹理颜色值来替换屏幕像素颜色值。这种方法所 以又称为最邻近方法( n e a r e s tn e i g h b o r ) 。该方法简单、快速，每个像素只要提 取一个纹理元素。当屏幕像素与纹理的大小一致时，这种取样方法能够产生可以 接受的图像质量，也就是说点采样只有在纹理像素与屏幕像素一一对应时效果才 好，否则图形的扭曲难以接受。纹理放大时，即屏幕图像要大于纹理图像，这时 一个纹理元素要对应几个像素，这时进行点采样则会出现色块，也就是屏幕中几 个像素都有相同韵颜色值。另一种情况是纹理缩小，即多个纹理元素对应一个屏 幕像素，在选取最邻近纹理像素时，没有考虑其余的纹理元素对最终像素颜色的 影响，这时就会产生明显的失真走样现象，在向远处投影时，表现出来的是波纹 现象。 1 4 d ， 4 口c ，fjli 桫 y 中国科学技术大学硕士论文 2 d 纹理映射及反走杵 3 3 2 m i p m a p p i n g 图2 1 4 m i p m a p p i n g 纹理映射流程 纹理方面最常用的一种反走样方法是分级细化方法( m i p m a p p i n g ) 【2 0 【2 1 】。 基于分级细化的纹理贴图( m l p m a p ) ，由于它的运算量小和易于硬件实现，成为 最普遍的纹理滤波方法，当前各种图形加速卡都以各自的方式对它进行支持。分 级细化方法的主要分为下面几个过程： 1 前置滤波：产生将纹理图像从原始图像开始，以1 2 的分辨率进行缩减采 样，并将不同分辨率的图像存储在存储器中，不同分辨率的图像称为不 同细节层次( i o d ) 。这个过程是基于软件的预处理。 2 透视投影：利用投影函数将屏幕像素投影到参数空间，这时参数空间的 数值在1 0 ，1 】之间。这个过程又叫透视校正地址计算。 3 纹理地址计算：透视投影之后得到的地址是参数空间的地址，还需要将 其转换到纹理空间坐标，并将其进一步将其转换到存储器的物理地址。 在转换到纹理空间后，首先要计算所要采样的纹理所在细节层次上，在 该细节层次上的纹理坐标可能不在整数位置上，这时要对其邻近的4 个 纹理进行采样。另外，映射后的纹理坐标还可能不在整数细节层次上， 这时还要在两个细节层次上进行采样，每个层次各采样4 个纹理。 4 后置滤波：对应的细节层次上采样的4 个纹理进行加权，称为双线性插 值。两个层次双线性插值后的纹理还要进行一次插值，称为三线性插值。 得到的最终颜色值送到帧缓冲中，将用来取代屏幕上的像素颜色值。 2 3 3 椭圆权重平均( e r a ) g r e e n e 和h e c k b e r t 基于椭圆形加权平均( e w a ) 【a 2 1 1 2 2 1 ，构造了一种纹理 反走样滤波器；h e c k b e r t 采样金字塔形数据结构来提高算法的效率。 e w a 是一种可随空间变化的椭圆形滤波器。就是因为随着滤波器在图像上 的移动，它的形状也会发生变化。当需要高质量反走样效果和采用非仿射映射时， 需要采用随空问变化的滤波器。 首先e w a 是将屏幕空间的像素看成是单位圆，将其四个角逆映射到纹理空 间后就变成了椭圆形。映射到纹理空间的椭圆形的大小、方向和偏心率会随着位 置的不同而不同。 图2 1 5e w a 单位像素的映射 图2 1 5 中，像素的中心坐标为( x o ，y o ) ，在纹理空间的映射中心为( 坳，v o ) ， 纹理空间中的h ，v 相对于图像空间的工，y 变化的偏导数为： “，丝，。竺，h ，塑，v 。丝(220)irx 叱。磊。i 吩。丙”r 。石 娌 如果将高斯滤波器在纹理空闯的中心坐标转换为( o 0 ) ，则映射到纹理空间 的滤波器可以表示为： d 2 0 ，v ) - a u 2 + b u y + c v 2( 2 ，2 1 ) 表示将纹理像素位置映射回到屏幕空间后，从像素中心到边距离的平方。 这样，d 2 就可以用来做为权重表的索引，它与仿射投影无关，仅与像素滤波 器相关。e w a 以每个像素是否在椭圆形足迹内来确定d 2 ，在足迹内( 矿1 ) 的 纹理像素被采样、加权并累加，结果再除以权重和，即椭圆形滤波器的体积。 用来计算扩的椭圆系数a 、b 、c 可由下式计算： 以t v 2 j + v 2 y 易- - 2 * q ，4 以4 u ， v ，) c m 一跖2 j + ! y f t a m c m b 0 4 中国科学技术人学硕上论文 2 d 纹理映射及反正样 a a 。| f b = v c 一