（计算机应用技术专业论文）计算机光栅图形反走样基础算法研究.pdf

辽宁师范大学硕+ 学位论文 摘要俐7 9 5 0 5 5y 1 光栅显示器上显示的图形，称之为光栅图形。它可以看作是一个象素矩阵， 在光栅显示器上显示的任何一个图形，实际上都是一些具有一种或多种颜色和灰 度象素的集合。对于一个具体的光栅显示器来说，象素的个数是有限的，象素的 大小是有限的，象素的颜色和灰度等级也是有限的，所以光栅图形只是近似的实 际图形。在光栅显示器上绘制非水平或非垂直的直线或多边形图形的边界时，或 多或少的会呈现锯齿状或台阶状走样现象。那么如何使光栅图形最真实地逼近实 际图形，便是本文所研究的主要内容。 基于查阅大量中英文文献的基础上，论文从现有的反走样技术入手，如提高 分辨率、普通区域取样、加权区域取样，对反走样的理论基础进行了深入的分析， 实现现有的经典反走样技术算法，并对时间与空间的计量代价、反走样效果进行 了分析研究。 本文的研究重点在直线反走样、曲线反走样和图像处理速度方面进行了研究 和改进。对于直线反走样，笔者基于b r e s e n h a m 算法的基础上，提出了 h e m i s p h e r e - f i l t e r 反走样算法，将h e m i s p h e r e - f i l t e r 算法与直线的对称快速 生成算法相结合，不仅克服了g u p t a p r o u l l 圆锥滤波及g a u s s 滤波在应用时 的积分运算，这样会消耗大量的时间；而且反走样效果比w u 反走样算法的效果 更佳。对于曲线反走样，笔者提出了双步圆的反走样算法，并引入及细化了灰度 级的概念，不仅克服了k u z m i n 单点生成圆算法速度慢的问题，而且反走样的效 果比w u r o k n e 双步算法效果更佳。并根据椭圆的任意一点的横坐标与其外切 圆的横坐标相同，而纵坐标与其内切圆的纵坐标相同，即部分圆的几何属性，提 出了椭圆的双步反走样。 反走样技术是提高光栅图形显示质量的重要技术之一。研究如何消除或减缓 走样现象，给人视觉上产生更舒适光滑的图形，在图形界面己成为人机交互主流 方式的今天，比如虚拟仪器中的虚拟仪表、数字化数字仪表、飞机座舱的导航系 统及各类仿真模拟系统等领域，具有一定的应用价值。 关键词：光栅图形；走样：反走样；像素：灰度级 广r 计算机光栅图形反走样基础算法研究 a b s t r a c t t h eg r a p h i c sd i s p l a y e do nt h er a s t e rm o n i t o ri sr e f e r r e dt oa sr a s t e rg r a p h i c s ，a n d i tc a nb ev i e w e da sap i x e l sm a t r i x a n yg r a p h i c sd i s p l a y e do nt h er a s t e rm o n i t o ri s t h ec o l l e c t i o no fo n eo rm o r ec o l o r sp i x e l so rg r a yp i x e l s a sag i v e nr a s t e rm o n i t o r , t h en u m b e ro fp i x e l si sl i m i t e d ，a n dt h es i z eo fp i x e l si sl i m i t e d ，a n db o t ht h ec o l o ro f p i x e l sa n d 笋a yl e v e l so fp i x e l sa r el i m i t e d a sw e l l ，t h e r e f o r e ，r a s t e rg r a p h i c si sj u s tt h e a p p r o x i m a t i o no f t h ea c t u a lg r a p h i c s w h i l en o n h o r i z o n t a ll i n e so rn o n v e r t i c a ll i n e s o rt h eb o r d e r so ft h ep o l y g o n sa r ed r a w no nt h er a s t e rm o n i t o r , s e r r a t i o na l i a s i n go r s t e p l i k ea l i a s i n gp h e n o m e n aw i l lm o r eo rl e s sb es h o w n h o wt om a k et h er a s t e r g r a p h i c st r u l yc l o s et ot h ea c t u a lg r a p h i c si st h ek e yc o n t e n to f t h et h e s i s o nt h eb a s i so fl o o k i n gu pal a r g en u m b e ro fc h i n e s ed o c u m e n t sa n de n g l i s h d o c u m e n t s ，t h ea u t h o rb e g i n s w i t hc u r r e n ta n t i a l i a s i n g t e c h n o l o g i e s ，i n c l u d i n g i n c r e a s i n gr e s o l u t i o n ，s a m p l i n go fc o m m o nr e g i o n ，a n ds a m p l i n go fw e i g h t e dr e g i o n ， a n da n a l y s e si nd e p t ht h ea n t i a l i a s i n gt h e o r e t i c a lf o u n d a t i o n s t h ea u t h o ri m p l e m e n t s t h ec u r r e n tc l a s s i c a la n t i - a l i a s i n ga l g o r i t h m ，a n da n a l y s e st h ec o s to f t i m ea n dm e m o r y a n da n a l y s e st h ee f f e c to fa n t i a l i a s i n g t h ek e yp o i n to ft h et h e s i si st h er e s e a r c ha n di m p r o v e m e n to fa n t i a l i a s i n g a l g o r i t h mo fl i n e s ，a n t i - a l i a s i n ga l g o r i t h mo f c u r v e sa n dt h ea c c e l e r a t i o no ft h ei m a g e p r o c e s s i n g w i t hr e g a r dt ot h ea n t i - a l i a s i n ga l g o r i t h mo fl i n e s ，t h ea u t h o rp u t sf o r w a r d h e m i s p h e r e - f i l t e ra n t i - a l i a s i n ga l g o r i t h mo nt h eb a s i so fb r e s e n h a ma l g o r i t h m t h e a u t h o rc o m b i n e st h eh e m i s p h e r e f i l t e ra l g o r i t h mw i t hs y m m e t r yr a p i dg e n e r a t i n g a l g o r i t h mo fl i n e s ，w h i c ha v o i d si n t e g r a lo p e r a t o ro fg u p t aa n dp r o u l lc o n ef i l t e r a p p l i c a t i o n sa n dg a u s sc o n ef i l t e ra p p l i c a t i o n ，a n dt a k e sal a r g ea m o u n to ft i m e f u r t h e r m o r e ，t h ee f f e c to fa n t i - a l i a s i n ga l g o r i t h mo fl i n e sp u tf o r w a r db yt h ea u t h o ri s b e t t e rt h a nt h ee f f e c to fw ua n t i - a l i a s i n ga l g o r i t h m w i t hr e g a r dt ot h ea n t i a l i a s i n g a l g o r i t h mo fc u r v e s ，t h ea u t h o rp u t sf o r w a r dd o u b l e s t e pc i r c l ea n t i - a l i a s i n ga l g o r i t h m ， a n di n t r o d u c e sa n dd e t a i l st h ec o n c e p to fg r a ys c a l e s t h ei s s u eo fl o ws p e e do f k u z m i na l g o r i t h m ，w h i c hi sr e l a t e dt ot h eg e n e r a t i o no ft h ec i r c l ef r o mt h es i m p l e p o i n t ，h a sb e e ns o l v e d ，a n dt h ee f f e c to fa n t i a l i a s i n gi sb e t t e rt h a nt h a to fw ua n d i i i i i 3 1 2 圆的单步与双步生成算法1 5 3 2 细化灰度级的双步圆反走样算法1 6 3 2 1 双步圆算法改进1 6 3 2 2 新双步圆反走样生成算法1 7 3 2 3 算法的复杂度分析及比较2 0 3 3 本章小结2 1 4 椭圆的双步反走样算法研究2 2 4 1 传统基本图形算法的不足2 2 4 2 椭圆曲线的离散模式及分域2 2 4 2 1 椭圆曲线的离散模式2 2 4 2 2 椭圆的分域2 3 4 3 引入双步走法的椭圆反走样算法2 3 4 3 1 判别式的构造2 3 4 3 2 反走样原理2 5 i v 辽宁师范大学硕士学位论文 4 3 3 区域i i 转向区域i 的终止条件2 5 4 4 算法步骤描述2 6 4 5 算法分析及计量比较2 6 5 应用领域的分析与展望2 8 5 1 汉字或矢量图形中的应用2 8 5 2 地图出版符号中的应用2 8 5 3 虚拟仪器虚拟仪表中的应用2 9 6 总结与展望3 0 6 1 本文工作总结一3 0 6 2 未来研究工作展望3 0 6 3 结束语3 l 参考文献3 2 攻读硕士学位期间发表论文3 5 致 射3 6 v 计算机光栅图形反走样基础算法研究 引言 自计算机图形学的概念出现以来，人们对图形显示效果的关注与研究一直是 计算机图形学领域内不懈努力的追寻目标。 光栅基本图形是由一系列离散的像素点组成，并以此来显示现实生活中的连 续且复杂的图形。由于其特殊性，不免会有锯齿走样或者让人视觉上感觉不美观 的现象。经典的反走样技术算法也在一定程度上，满足了人们的视觉需要，给相 关领域的应用带来了便利。 随着时代的发展与科技的进步，计算机图形学的反走样技术应用领域也在日 益的拓展，各种模拟仿真系统、数字化罗盘仪表等，都要利用反走样技术使其更 加的真实，误差效果在人的视觉范围内更加的不明显。人们对图形学领域中的反 走样技术的研究，可以使人们摆脱那种走样或扭曲的光栅图形所带来的不悦，让 人们在视觉上，欣赏到图形逼真显示的美感享受。 辽宁师范大学硕士学位论文 1 走样及反走样 1 1 走样及反走样的基本概念 1 1 1 走样与反走样概念诠释 光栅显示器上显示的图形，可以看作是一个象素矩阵，在光栅显示器上显示 的任何一个图形，实际上都是一些具有一种或多种颜色和灰度象素的集合。对于 一个具体的光栅显示器来说，象素的个数是有限的，象素的大小是有限的，象素 的颜色和灰度等级也是有限的，所以光栅图形只是近似的实际图形。 袅 b c 陷t e s ! ：氅弋2附nt e s _- 图1 1a 一组线条和文本 f i 9 1 1 a as e to f1 i n e sa n dt e x t b 、c 部分的放大，显示锯齿状 b 、c s h o w i n gs e r r a t e da f t e re n l a r g i n g 在光栅显示器上绘制非水平或非垂直的直线或多边形图形的边界时，如图 1 1 所显示的那样，或多或少的会呈现锯齿状或台阶状走样现象。这是因为直线、 多边形、色彩边界等是连续的，而光栅则是由离散的点组成，在光栅显示设备上 表现直线、曲线、多边形等，需要在离散位置取样。由于取样不充分重建后所造 成的信息失真或图形变形，称之为走样( a l i a s i n g ) 。而用于减少或消除这种视觉 显示效果的技术，就称为反走样( a n t i a l i a s i n g ) 。 1 1 2 走样现象的分类 计算机生成图像时通常存在的走样现象主要有2 种：锯齿形边以及图形细节 或纹理绘制的失真，其现象如下面图1 2 所示。 图1 2a 锯齿状走样现象 b 图形细节或纹理走样现象 f i 9 1 2a z i g z a ga l i a s i n gb g r a p h i cd e t a i lo rt e x t u r ea l i a s i n g 基于走样现象及所显示的形式，基本的反走样方法主要有两大类。 第一类是提高分辨率，即增加取样点( 提高取样频率) 。然而，c r t 光栅扫描 设备显示非常精细光栅的能力是有限的，比如把光栅显示器的分辨率提高了1 倍，那么当直线经过2 倍的象素，锯齿也会增加1 倍，不过，同时每个阶梯的宽 度也减小了1 倍，所以显示出的直线段或者曲线，在人的视觉范围内，看起来就 会平直光滑些。然而，这种反走样方法是以几倍的存储器代价和扫描转换时间获 得的。因此，增加分辨率虽然简单，但不是经济的方法，而且它也只能缩减或者 淡化这种现象，并不能消除锯齿问题。因此人们通常是在较高分辨率上对光栅进 行计算，然后采用某种平均算法( 滤除高频分量) 得到较低分辨率的象素的属性， 并显示在分辨率较低的显示器上，这种方法称为超取样或后置滤波。 垂拿 第二类反走样是把像素作为一个有限区域，对区域取样来调整像素的亮度， 以光顺边界来减小锯齿现象，这种方法等价于图像的前置滤波。针对线条的锯齿 状现象，比较经典的有w u 反走样算法；针对图形细节或纹理走样现象，比较经 典的方法有m i p - m a p 方法等。 1 2 反走样技术的发展及研究现状 1 2 1 反走样的发展历程 反走样技术的发展历程，离不开计算机图形学的发展，并且是自始至终的伴 随着计算机图形学的发展而发展的。 自上个世纪6 0 年代出现了计算机图形学概念以来，就随之而诞生了一种很 好的反锯齿w u 反走样算法( 图1 3 所示) ，这一算法至今还很受欢迎，曾经是被 8 0 x 8 6 汇编语言优化大师m i c h a e la b r a s h 强烈推荐的经典反走样算法。 辽宁师范大学硕士学位论文 图1 3 经过w u 反走样算法处理过的n e w t o n sc r a d l e 图形 f i 9 1 3n e w t o n sc r a d l eg r p ha f t e rw ua n t i a l i a s i n g 1 9 8 3 年，w i l l i a m s 提出了纹理映射中的反走样技术方法m i p m a p i n g ( h t t p ：e n w i k i p e d i a o r g w i k i m i p m a p ) ，这一方法可在平面像素的绘制过程 中实现实时反走样，它的基本思想是以适当大小的正方形来近表达每一像素在纹 理平面上的映射区域( 图1 4 所示) ，并预先将纹理图像表达为具有不用分辨率 的纹理数组，作为纹理查找表，其中低分辨率的图像由比它高一级分辨率图像取 平均得到。这一技术在时下的纹理映射中反走样中，应用仍然比较广泛。 图1 4m i p m a p 图的形象表示( 比如一张2 5 6 * 2 5 6 的图，在长和宽方向每次减少一倍，生 成：1 2 8 1 2 8 ，6 4 * 6 4 ，3 2 * 3 2 ，1 6 1 6 ，8 * 8 ，4 * 4 ，2 * 2 ，1 1 ，八张图，组成m i p m a p ) 1 2 2 反走样的研究现状 4 图1 62 0 0 7 8 - 2 0 0 8 1 2 期间用户关注度 f i 9 1 6u s e r sa t t e n t i o nb e t w e e n2 0 0 7 8a n d2 0 0 8 1 2 图1 5 折线的起伏变化，显示了近几年的反走样学术关注程度，可以预测， 今后的几年将会呈上升趋势。 图1 6 表示的是2 0 0 7 8 - 2 0 0 8 1 2 期间的用户关注度，可以看出用户在2 0 0 7 年的1 2 月份达到前所未有的高峰。不过通过折线的显示趋势，可以看出，今后 的几年也会呈上升趋势。 1 3 反走样技术的应用领域 1 ) 出版系统中的应用 对于追求符号精度的出版系统来说，反走样技术是不可忽略的。目前通用的 出版系统，比如1 1 l u s t r a t o r 、f r e e h a n d 、c o r e l d r a w 、p h o t o s h o p 、w o r d 等， 在显示图形时都不同程度的采用了反走样技术。同样，一些国内外常用的地图出 版系统和g i s 系统( 如m i c r o s t a t i o n 、m a p g i s 、方正智绘、a r c g i s 、m a p i n f o 等) ， 也都采用了反走样技术( 图1 7 所示) 。 辽宁师范大学硕士学位论文 蔓角点臣z 刁街隧 政籽驻地= 桥粱 。，一一一v 。“4 f 镓邑1 ，酋曲线 一， 十砦 击鳟 裔跟 医刁 = 、 ，。e 棕色) 。- ，。 h 。一体绝 短走榫情澄 图1 7 部分地图出版符号的反走样前后对比 f i 9 1 7c o m p a r i s o no fs o m em a ps y m b o i sb e f o r ea n da f t e ra n t i a l i a s i n g 2 ) 飞机座舱系统中罗盘仪表中的应用 随着计算机及图形学技术的发展，座舱仪表对图形显示的质量的要求也越来 越高，由于硬件系统采用的是光栅图形显示系统，罗盘画面旋转受光栅扫描显示 器的限制存在着锯齿形失真、扭曲等走样现象，因此也需要引入相应的反走样技 术，如图1 8 所示。 图1 8 产生锯齿状( 左) 与经过反走样处理后( 右) 的罗盘刻度线 f i 9 1 8c o m p a s sc a l i b r a t i o nb e f o r e ( 1 e f t ) a n da f t e r ( r i g h t ) a n t i - a l i a s i n g 1 4 本文主要研究内容及章节结构 第一部分，主要是对本文的一些综合性的概述。这一章节详细讲述了走样与 反走样技术的基本理论概念与方法；之后讲述了反走样技术的发展历程与研究现 状；最后说明了反走样技术的应用领域，同时对本文的结构进行了说明。 第二部分，主要是对直线反走样算法的研究与探讨。首先讲述了一些计算机 基本光栅图形的经典反走样算法；之后讲述了直线画线算法的发展历程及现状： 最后基于b r e s e n h a m 直线画线算法，提出了新的嵌入h e m i s p h e r e f i l t e r 的快速 6 计算机光栅图形反走样基础算法研究 画线算法，并对其运行速度与显示效果进行了分析。 第三部分，主要是对圆的反走样绘制算法的研究与探讨。首先介绍并引入圆 的对称生成的概念；之后简述了传统圆的绘制算法，如圆的k u z m i n 单步与双步 算法，并对其优缺点进行了比较与分析：最后在双步圆算法的基础上，引入细化 了的灰度级，并与其他的绘制算法，在复杂度上进行分析及比较。 第四部分，主要是对椭圆的反走样算法的研究与探讨。首先介绍了现有的一 些反走样算法的缺陷，然后由椭圆与圆的部分相似性，引入了椭圆的双步反走样 算法，并详述了算法的设计步骤。 第五部分，主要是简要罗列了反走样技术在一些领域中的应用，以及未来应 用范围的拓展与展望。这些领域主要是飞机座舱系统的罗盘仪表类、地图出版符 号类等。 第六部分，主要是对本文的核心内容作了一些简要概括，并简述了笔者对未 来科研工作的倾向及展望。然后，笔者从查阅中英文文献、去编程实现他人的算 法、以及被激发灵感在落笔写论文的过程中，不仅磨练了笔者的意志，铸就了笔 者的坚强，以及刻苦钻研的科研精神，也使笔者学到了很多有意义的东西。 7 萋一 辽宁师范人学硕士学位论文 2 直线的反走样算法研究 本章首先讲述了传统的直线生成算法，并对其优缺点进行详尽的分析与研 究。之后，介绍了最有效的直线生成算法b r e s e n h a m 算法，利用直线的两侧对称 性可以进一步加快生成速度。但由于受到光栅扫描显示器的限制，用离散像素绘 制的直线存在走样问题，实际应用中经常需要进行反走样处理。本章基于 b r e s e n h a m 算法，并依据直线的对称生成原理，与半球形滤波反走样技术相结合， 提出了一种新的快速反走样直线的生成算法。 2 1 传统画线算法 在现有计算机显示器的分辨率下，屏幕上的一条直线，若不是在0 。、4 5 。 9 0 或1 8 0 。的角度，则会呈现明显的锯齿或阶梯状，这是由于直线在光栅图形显 示器的对应图形是由一系列相同亮度的离散像素构成的。这种用离散量表示连续 量引起的失真，就称为走样( a 1 i a s i n g ) 走样使得图形变形，甚至会引起误解， 工程上有时需要采取措施，用于减少或消除这种效果的技术，就称为反走样( a n ti a l i a s i n g ) 。常用的反走样方法有：提高分辨率，未加权区域取样，加权区域取样。 2 1 1 提高分辨率 如图2 1 ( a ) 所示，采用中点画线算法在白色背景上绘制的一条单像素宽， 斜率为缸且0 = 舣= 1 的黑线，在理想直线经过每- n 的像素中，选择离直线最近 的一个，置为像素颜色，每当前一列像素和后一列所选的像素颜色不一样时，在 线上就会出现锯齿或阶梯状。如图2 1 ( b ) 所示，若把显示器分辨率提高一倍， 直线经过两倍的象素，锯齿也增加一倍，但同时每个阶梯的宽度也减小了一倍， 所以显示出的线段看起来就平直光滑一些。这种反走样方法是以4 倍的存储器代 价和扫描转换时间获得的。因此，增加分辨率虽然简单，却是不经济的方法，而 且它也只能减轻而不能消除锯齿问题。 a b 图2 1a 用中点算法扫描转换的一条直线 f i 9 2 1a as t r a i g h t li n ec o n v e r t e db ym i d p o i n ta l g o r it h m 图2 ib 把显示器分辨率提高一倍的显示效果 不 条 时 线 未加权取样所绘制的直线比相同分辨率下的直线效果好的多，但也有缺点： 一是无论线条以何种方式截取一个像素区域，只要截取面积相同，就会产生相同 的灰度值，这样仍然会导致锯齿；二是直线上沿理想直线方向的相邻像素有时会 有较大的灰度差。 2 i 3 加权区域取样 常用的加权区域取样方法有锥形滤波，高斯滤波等，靠近像素中心的小块区 域的作用大于远离中心的同样大小区域的作用，即将象素均匀分割成r 1 个子象 素，则每个象素的面积为i n 。计算每个子象素对原象素的贡献，并保存在一张 二维的加权表中，然后求出所有中心落于直线段内的子象素。最后计算所有这些 y 予像素对原像素亮度贡献之和蕊的值，该值乘以像素的最大狄度值作为像素 的显示灰度值。如对圆锥形滤波器加权体积取样，我们将屏幕划分为n = 3 3 个 子象素，得到加权表如图2 3 所示。 9 过调节像素的亮度和灰度， 从而达到较好的视觉效果。w u 反走样算法比1 是反走样技术较早使用的方法，文献 将其扩充到了三像素宽的直线绘制。而2 0 0 6 年，d d a 算法与改进的g u p t a p r o u l l 圆锥滤波算法相结合u 刨将直线的绘制又扩展到了任意宽度。 而且g u p t a p r o u ll 圆锥滤波及g a u s s 滤波在很多其他领域也得到了很好 的应用。例如高斯积分法反走样算法在罗盘仪表绘制中的应用u 引，但这两种滤 波算法都需要进行积分运算，这样会消耗大量时间。本文根据文献1 提出的 h e m i s p h e r e f i l t e r 反走样算法，试着将h e m i s p h e r e f i i t e r 算法与中点 b r e s e n h a m 快速画线算法相结合。 2 3 基于b r e s e n h a m 算法的新反走样快速画线算法 2 3 1b r e s e n h a m 直线算法 图2 4 显示了该算法的原理，设直线的斜率k = - 别如起点坐标为( o ，0 ) ，o k 1 ，z 轴每向右增加1 ，j ，轴增加k ，到底选取( 1 ，1 ) 还是( 1 ，0 ) ，取决于这两个像 素哪一个距离理想直线更近。图中直线l 。的斜率血 1 2 ，选取点( 1 ，1 ) 。以后每向x 轴前进一个像素，通过对j ， 轴增量的比较，依次选取距离理想直线最近的像素，即可完成直线的绘制。 1 0 计算机光 图2 4b r e s e n h a m 算法原理 f i 9 2 4 b r e s e n h a m sa l g o r i t h m 2 3 2 以b r e s e n h a m 算法为基础的直线对称生成 利用直线的两侧基于中心对称的性质，基于b r e s e n h a m 算法，可以进行一次 循环生成以直线中心为对称的两个点，这样，直线的生成是从两端点向中心对称 点同时进行，循环次数减半，生成速度得到提高。如图2 5 所示，要对称生成点 a 到点b 的直线，可以以中点c 为对称，同时从直线的两端点a 和b 出发，由于 直线对称，每次增减的量都是k ，故主循环减半，每次循环选取两个像素，加快 了直线的生成。 图2 5 直线的对称生成示意图 f i 9 2 5 t h eb i l a t e r a ls y m m e t r i cd r a w i n go fl i n e 2 3 3h e m is p h e r e - f ii t e r 求像素灰度值 由于锥形顶点在其所在的领域内不可导，当线段向像素中心移动并经过像素 中心，由像素狄度值而引起视觉上的效果会有不连续的感觉，并且锥形滤波需要 积分运算。h e m i s p h e r e - f i l t e r 是在锥形滤波上做的一些改进，它克服了锥形滤 波器的两个缺点。由于球上的每个点都是高阶可导，所以在视觉上连续性会比较 好，另外h e m is p h e r e - f i1t e r 的算法对子域w 。的计算可以通过计算球缺与球体积 的比值得到，不需要通过积分运算，因此在计算机上也容易实现。平面图与前视 图如图2 6 、图2 7 。 1 2 p h e r e f il t e r 底面 一 到 为 别从a ，斯口b 席向对称中点画点。 ( 3 ) 利用h e m i s p h e r e f i l t e r 方法，根据所选点与理想线条的距离，即球缺底 面平面与球心的距离，然后利用球缺与球的体积比值而得到像素灰度权值，继而 得到灰度值。 ( 4 ) 把由像素灰度权值而求得的像素灰度值，着色于所选的像素点，直到把 线条中点的两个像素点选取完毕，并同时着色完毕，反走样直线绘制也就完成。 z 轴在每次循环中，a 点和6 点横坐标沿z 轴一增一减，并且利用y 轴的增 量七来确定实际直线的两点。即一次主循环选取4 个像素点。直到把线条中点的 两个像素点选取完毕，反走样直线绘制也就完毕。实验环境是在w i n - t c 下完成 的，生成结果如图2 9 所示。 图2 9a 反走样前的直线 f i 9 2 9a t h el i n eb e f o r ea n t i a l i a s i n g 辽宁师范人学硕士学位论文 图2 9b 反走样后的直线 f i 9 2 9 b t h el i n ea f t e ra n t i a l i a s i n g 2 4 本章小结 本文将h e m i s p h e r e f i l t e r 与直线的对称生成相结合，原本是阶梯或锯齿状 的地方，由于使直线的灰度值连续变化有了一定的缓和，边缘被平滑，其显示的 效果相对反走样之前有了很大的提高。直线的对称生成，使主循环减少了一半， 速度也得到了很大的提高。另外半球滤波由于其形状的特殊性，不仅避免了积分 运算，而且由于其高阶可导，所以视觉连续性和平滑效果相对来说也比较好，所 以对速度要求高，而对图形质量不作苛刻要求的情况下，有较好的应用前景，仿 真效果如图2 1 0 所示。 ab 图2 1 0a 反走样前的图形b 反走样后的图形 f i 9 2 1 0 a t h ep i c t u r eb e f o r ea n t i a li a s i n g f i 9 2 i 0 b t h ep i c t u r ea f t e ra n t i a l i a s i n g 计算机光栅图形反走样基础算法研究 3 双步圆反走样画线算法研究 本章首先介绍了圆生成算法的发展及现状，接着对绘制圆的b r e s e n h a m 算法 及k u z m i n 单点生成算法进行了试验结果分析及总结，并指出了其存在的优缺点： 之后，基于w u r o k n e 双步圆算法提出了新的双步反走样生成算法，使其成为 一种反走样效果更佳的方法；并且该算法的灰度级数是原来w u r o k n e 算法的 3 倍，且最大灰度误差也比原来的减少了1 4 ；另外该算法由于只用整数运算， 避免了除法，因此便于硬件实现。 3 1 圆的传统生成算法 3 1 1 圆的对称生成算法的引入 由b r e s e n h a m 提出的圆生成算法铲最著名且被广泛使用，另一个 m i d p o i n t 算法是由f o l e y 等提出的u 驯。虽然两算法不同，但它们的计算量是一 样的：另外一些单点生成的算法，如逐点插补法及正负法1 等，其计算量也均 无太大的改进。对于圆的绘制也有行程长度算法比俨础。，该算法采用内外两层循环 结构，在外层循环计算每次行程的长度，即具有用相同y 坐标的点数，然后在内 循环中生成这些点，但这种算法的效率并不令人满意。 对多点圆生成算法的研究目前尚未得到满意的结果，因为圆弧上的点并不是 线性的，所以开发多点生成算法有很大的难度。但是圆相对于直线来说有很好的 对称性，所以圆的对称点生成要比直线更有效。 3 1 2 圆的单步与双步生成算法 k u z m i n 单点生成算法心钊是从( 尼0 ) 即x 正半轴上，以逆时针方向生成的一个 八分之一圆，其像素点的选取与b r e s e n h a m 提出的算法相似，只不过为了简化d 的递推公式，将其中的步长公式除以4 而又重新给了定义，所不同的是：k u z m i n 把d 的递推公式中在每次循环中的加1 2 ，变为每偶次循环时加1 ，每奇次循环时 加o 。笔者已编程实现了该算法，其试验结果表明：当半径斤取奇数时，生成的 并非一个圆，而是一个类似角度平滑的正四边形；半径厅取偶数时，生成的是逼 真的圆。两种情况无论哪一种，在半径取到一定值时，都会变形走样，并且在 4 5 。、1 3 5 。、2 2 5 。、3 1 5 。处偶尔会出现像素点的遗失。 2 0 0 5 年，文献比5 j 一文对此算法作了些改进，算法是从y 的正半轴上，以顺时 针方向生成的八分之一圆，其原理与k u z m i n 算法是一样的。试验结果表明：经改 进后的单点生成算法，d 的累加误差值有所减小，并且半径疗为偶数时，生成 的是圆；半径厅为奇数时，生成的也比较接近圆，其生成的圆弧比前者的效果要 好一些。但是无论哪一种情况，改进后的算法在o 。、9 0 。、1 8 0 。、2 7 0 。处仍会出现 可利用变量m ，, 7 分别取代8 * x + 1 2 与8 * y 一8 ，并且利用简单的递推公式推算出 它们，同时d 的递推公式也得到了简化。因此选点依据可如下： ( 1 ) d 0 ，取( x + 1 ，j ，) ，( x + 2 ，y ) ( 2 ) 0 = d m ，取( x + l ，y ) ，( x + 2 ，y 一1 ) 1 6 计算机光栅图形反走样基础算法研究 ( 3 ) m = d 刀，取( x + 1 ，y 一1 ) ，( x + 2 ，y - 1 ) ( 4 ) 刀 _ d ，取( x + 1 ，y 1 ) ，( x + 2 ，y 一2 ) 并转到第二个八分圆生成部分。 3 2 2 新双步圆反走样生成算法 c r o w 比引在1 9 7 7 年就提出了解决反走样问题的方法，其基本思想是：使图形 边界上的像素灰度值与其在图形理想边界内的面积大小成正比，这样图形的边缘 就得到了平滑，并且在移动时，由于边界像素的灰度值在不断缓慢的变化，因此 不会有跳跃的感觉。之后p i t t e w a y w a t k i n s o n 憎驯利用改进的b r e s e n h a m 直线 算法实现了与c r o w 方法一样的功能，但它们的方法都使用了浮点运算，因而限 制了算法的执行速度。在1 9 9 4 年p i t t e w a y 0 1 i v e 。提出了整数的反走样直线 算法，进而提高了速度。1 9 9 4 年的一篇文献u 在整数运算的基础上，又提出了 一个更快速有效的方法，并且还比p i t t e w a y 等算法多产生了2 个灰度级。 现在，我们将对3 2 1 部分的双步圆算法所绘制的像素点进行赋予不同级的 灰度钊。设圆内每个像素的狄度值为i ，圆外背景区域的光强度为0 ，要生成反 走样的圆弧就需要确定圆的每个边界像素点在圆内的面积，并且赋予相应的灰度 值。 ( 1 ) d 0 时，对于这种情况，被看作是小直线段的圆弧应位于中点m p 2 之上， 取像素点( x + 1 ，y ) 与( x + 2 ，y ) 。下面来确定小线段的位置，如图3 2 所示，斜率 s l o p e = - l 2 的小线段，对当前像素点( x ，y ) 来说，该像素点所占据的区域范围在 ( x ，y + 1 2 ) 与( x ，y 一1 2 ) 之间，若斜率小于一1 2 ，即使上限界定在( x ，y + 1 2 ) 处， 则该小直线段仍会位于m p 2 之下。所以，此情况下的小线段斜率应介于o 与一1 2 之间，我们取两者的中间值一1 4 。 6 c ，y + 1 e y ) s l o p e = 。1 z ， 1 ，y - 1 ) & + 2 ，y - i ) + r a p 3 图3 2d o 时小线段斜率的界定 f i 9 3 2 t h e1 i m i to ft h el i n es e g m e n t ( d o ) 如图3 3 所示，斜率为s l o p e = 一1 4 的小直线段的上限由( x ，y + l 2 ) 限定，而其下 1 7 下 的 小 其 与 组 ( 3 ) 朋 _ d 门时，选取点( 卅1 ，广1 ) 与( 时2 ，广1 ) 。如图3 5 所示，小直线段的 斜率仍为一1 2 ，其上下限分别由m p l 和m p 3 限定。用相同的分析方式，得知 ( 时1 ，广1 ) 面积的3 4 和( 时2 ，广1 ) 面积的1 4 在圆内，分别赋予相应的欢度值 3 i 4 和i 4 。 f i 9 3 6 脚的双裂嬲鳓_ d ：1 7 - 4 * r ；。郦謇虢。i 7 知4 ： i l 4 = i 4 ：i 1 2 = i 2 ：l j 7 气。 1 9 水 置m警 的叫 时 舻洳 酊 图o 辽宁师范大学硕士学位论文 i fa ( 7t h e ni fo k ot h e n d + = 2 * n r + 2 4 ： x + l ：s e t p i x e l ( 五月1 1 2 ) ：x = x + l ：s e t p i x e l ( 五只1 1 4 ) ： s e d + = 2 , n r - n + 2 4 ：n - = 8 ：x = x + l ：s e t p i x e l ( 五只1 1 4 ) ： x + l ：尸广1 ：s e t p i x e l ( 五月1 3 4 ) ：) s ei fd nt h e n d + = 2 , n r n + 2 4 ：n - = 8 ：x = x + l ：尸尸1 ：s e t p i x e l ( 五月1 3 4 ) ： x + l ：s e t p i x e l ( 五只1 1 4 ) ：) s e 丹= 2 木( 矿力) + 3 2 ：n - = 1 6 ：x = x + l ：尸厂1 ：s e t p i x e l ( 五j r , 1 1 4 ) ： x + l ：尸广1 ：s e t p i x e l ( 五只1 1 2 ) ： = 1 6 ：) ) = yt h e ns t o p s eg o t o 2 3 算法的复杂度分析及比较 为了对新双步圆反走样算法进行评价，我们将此改进算法与现有的圆绘制算 进行了比较，并且在沿圆弧跳转到其他的八分圆时，由于x 轴与y 轴的坐标转 在各种圆的算法中都存在，因此不进行比较。另外，由于主循环中的计算被重 的执行，因此，我们仅仅考虑这些主循环中的运算量，而忽略外部的计算量。 由于从( o ，尺) 到( j r 压，尺压) 八分圆是由尺压个像素点组成；其中通过4 5 。移动生成 的点数是r 一尺虿；通过水平或垂直移动生成的点数是 j r 压一( 尺一只压) = ( 压一1 ) r 。 ( 1 ) 计算量比较 表3 1 所示为本文算法与常用的b r e s e n h a m 算法、正负法、中点算法进行比较。 表3 1几种圆生成算法每生成一点所需的计算量比较 t a b 3 1c a l c u l a t i o n so ft h ec i r c l ed r a w i n ga l g o r it h m 2 0 ( 2 ) 反走样效果灰度级比较 由于常见的几种画圆算法没有反走样效果，因此( 1 ) 中只对它们的计算量进 行了比较，而w u & r o k n e 算法有反走样功能，表3 2 中两者在灰度级和光强误差 方面进行了比较，两算法所生成的圆弧如图3 7 所示。 中间灰度级数最大光强误差 w u b r o k m e 笪法 1 t 2 二 图3 7a w u & r o k n e 算法所绘制的圆弧 图3 7b 新双步反走样算法所绘制的圆弧 3 3 本章小结 本章首先对现有一些绘制圆的算法进行了试验、分析及总结，并指出了其存 在的一些优缺点；然后，基于w u & r o k n e 双步圆算法提出了赋予狄度值的新反走