Computer Graphics

浏览量:3,812

锯齿与抗锯齿技术介绍

本文主要介绍锯齿产生的原因,几种简单的抗锯齿技术,像前置滤波,后置滤波,基于光线追踪的抗锯齿技术中的一种。这篇文章是为后面介绍分布式射线追踪(Distributed Ray Tracing),随机采样(Stochastic Sampling)和累积缓存(Accumulation Buffer)作铺垫。 一.    锯齿的介绍 锯齿的概念最早出现在信号采样的采样理论中,以一定频率离散的采样一个信号,如果采样频率不够大就会发生锯齿。如图(1)所示的两个sine波,圆圈表示采样点。对(a)图中的sine波以图中所示的采样频率采样,足以构造出原始的sine波;对(b)图中的sine波以同样的采样频率采样,构造出来的sin波的频率就会降低,这就是一个锯齿信号(Aliased Signal)。奈奎斯特定理(Nyquist Theorem)就指出,为了精确的重构原始的信号,采样频率必需是原始信号中最高频率的两倍。在给定采样频率的条件下,能精确重构的信号中的最大频率是奈奎斯特极限(Nyquist Limit),即对所有在极限范围内的信号以给定的采样频率采样,可以精确的重构出原始信号,对超过那个范围的信号就会发生锯齿,出现下图的情况了。 图1. 在奈奎斯特极限范围内和范围外的点采样 在图形学范畴中,像素是一个个离散的点,在显示器上的光栅显示就相当于对图像进行采样,对于给定分辨率的显示器相当于给定了采样频率。如果要显示的图像的最高频率超过了奈奎斯特极限,就会发生锯齿,在图形学中称之为jaggies,翻译成中文也是锯齿的意思。 最好的避免锯齿的方法是要有足够大的采样频率,例如针对图形学来说,就是要有足够大的分辨率。但在多数情况下,并不能满足这个条件,所以就需要采用一些其它技术来解决这个问题。 显示器清晰度不够,能产生锯齿,使用一些高清显示器就可以解决这个问题,但这里叙述几种在显示器清晰度不够的情况下解决锯齿问题的技术,处理锯齿问题的方法称为抗锯齿技术。 二.    抗锯齿技术 图2. 未使用抗锯齿技术,使用抗锯齿技术和使用基于sinc过滤器的抗锯齿技术 图2(a)显示了图片未使用抗锯齿技术时发生失真,越靠近图片顶部,棋盘格子越小,图片越难以辨识;而图2(b)采用了一种抗锯齿操作,靠近顶部的棋盘逐渐变在灰色,在屏幕分辨率不足以显示远处的格子时,这种效果更加可接受,而越近的格子也越光滑;图(c)使用了另外一种抗锯齿算法,是基于sinc过滤器的抗锯齿算法,能达到比图片(b)更好的效果。 还有一些抗锯齿技术,像将图像模糊(bluring),根据Nyquist采样理论,是给定采样频率,通过降低原始信号的频率来使得信号能够被重构出来,如图3所示。对模糊化处理和未处理的原图像进行下采样,得到图中底部的两张图,模糊化处理的原图像下采样的图像还能看出一些轮廓,而未处理的原图像下采样的图像就显得更加混乱。 图3. 采样前未模糊化处理和模糊化处理形成的效果图 从上面看出,采用抗锯齿技术,可以一定程度上缓解样本不足导致的失真。这里在图形学的角度,介绍三种抗锯齿技术。 2.1. 前置滤波(Prefiltering) 前置滤波技术,是通过物体的覆盖范围来计算其像素颜色值的,即一个像素的多少区域被物体覆盖。每个像素会有一个灰度(Intensity),该值依赖物体或者直线对像素所在区域的覆盖率,如图4所示。灰度是0,表示黑色;灰度是1,表示白色。如果一个像素的一半被多边形覆盖,灰度是1/2;如果1/3被覆盖,灰度是1/3,依次类推。如果帧缓冲区中每个像素占4位,则黑色用0表示,白色用15表示,所以每个像素值是像素灰度值乘以15,图4(a)中的多边形,可以用图4(b)中的像素值来表示。 图4. 前置滤波像素值的计算 找到每个像素的灰度需要较大的运算量,这里介绍一种方法是由Pitteway和Watkinson提出的,是对布雷森汉姆直线绘制算法(参见文章《布雷森汉姆直线算法》)进行的修改。基本思想是:多边形填充时,采用的是逐行扫描的方式,用AEL数据结构确定要填充的像素段,当一条扫描线被填充完成后,采用布雷森汉姆算法更新存储在AEL结点中的数据xint,即改变了文章《区域填充算法和多边形填充的扫描线算法》2.2中所叙述的原则2。 通过一个例子来说明该算法,图5中的边的斜率是m=4/10,像素值所在方格用标准的布雷森汉姆算法进行计算,方格中像素强度依次为0.5,0.9,0.3,初始像素值是0.5。从左到右扫描边,如果y方向的坐标值不变,则像素强度加上m=0.4,如果y方向的坐标值加1,则像素的灰度值减去1-m=0.6,这相比于《区域填充算法和多边形填充的扫描线算法》中的多边形填充算法,锯齿问题能得到一定程度的缓解。 图5. 抗锯齿的扫描线算法 最后演示一个由参考【5】中找到的两张前置滤波的例子,如图6所示。总结下:前置滤波必需考虑对象的几何细节并计算每个像素的平均灰度,对于处理除多边形形状以外的几何图元来说,前置滤波运算量非常的大,不太适用。 图6. 前置滤波的对图像的影响 2.2. 后置滤波(Postfiltering) 首先介绍一个很重要的概念,就是超采样(Supersample),简单来说,就是原先一个像素只选择一个采样样本,现在一个像素中选取多个采样样本,即以亚像素(subpixel)作为样本。如图7所示,一个格子表示一个像素,每个像素上取9个采样点,即水平分辨率和垂直分辨率都是原来的3倍。如果要绘制圆圈A中的像素,因为有6个采样点在圆圈内部,3个采样点在外部,所以计算得到它的颜色值为:(2/3*圆圈内颜色+1/3圆圈外颜色)。B像素的9个采样点颜色都一样,它的颜色值就多边形的颜色,即圆圈内的颜色。

spacer
浏览量:16,069

区域填充算法和多边形填充的扫描线算法

本文主要介绍几种区域填充算法,重点解释多边形的扫描线填充算法,最后实现了多边形填充算法,包括在附录文件中。在参考【5】中,作者详细介绍了一系列区域填充算法,可以查看相应网页。代码的下载地址为:https://github.com/twinklingstar20/twinklingstar_cn_region_polygon_fill_scanline/ 1. 1.      区域的定义和填充 1.1   像素定义的区域(Pixel-Defined Region) 1.1.1        边界定义区域(boundary-defined) 定义某些像素是边界,边界包围着一块区域。填充所有在边界内的相连通的像素,主要分下面几个步骤: 从区域内部一个像素点开始 判断这个像素是否是一个边界像素点或者已经被填充了 如果都不是,就把它填充,然后开始设置邻居像素点。 用图片演示这个过程,如下面的幻灯片所示,代码片段如下所示: void boundaryFill4 (int x, int y, int fill, int boundary) { int current; current = getPixel (x,y); if (current != boundary && current

spacer
浏览量:2,086

布雷森汉姆直线算法

本篇文章,主要介绍布雷森汉姆直线算法,包括一个用glut实现的demo。代码的下载地址为:https://github.com/twinklingstar20/twinklingstar_cn_demo_bresenham-line-algorithm 一.             布雷森汉姆(Bresenham)算法说明 图1. 在显示器上绘制直线 如图1所示,在显示器上绘制一条直线,直线上一些像素会被启动,由此形成一条直线效果。直线绘制算法是图形学中的一个基本的算法,绘制直线时需要考虑哪些像素需要被启动,这里介绍布雷森汉姆直线绘制算法。它是一种基本的递增算法,基于前一个像素信息就可以计算出下一个像素值,能确定一条直线上哪些像素要启动,而且它的计算只采用整数值,避免了浮点运算运算。 布雷森汉姆算法有几种变种,这里考虑其中的一个中点算法。假设现在要绘制两个端点是(ax,ay)和(bx,by)之间的线段,需要确定介于它们之间的像素序列。为了简化讨论,这里考虑一种特殊的情况,即ax<bx,直线斜率0<k<1的情况。线段的宽是W=bx-ax,高是H=by-ay,则有W>H,所有穿过两个端点的直线都满足下面的一个等式: -W(y-ay)+H(x-ax)=0 定义一个函数如下所示: F(x,y) = -2W(y-ay)+2H(x-ax) 如果F(x,y)>0,则说明(x,y)位于直线下;如果F(x,y)<0,则说明(x,y)位于直线上。 图2. 中点算法的一个参数 图中所示,假设从黑色点(Px,Py)处开始考虑算法,现在考虑在Px+1的位置上,Y方向上最合适的值是Py +1还是Py,即U(Px+1, Py+1)还是L(Px +1,Py)。接着是要判断Q点更靠近U还是L,可以通过计算中间值M(Px+1,Py+1/2),可以使用上面所说的等式,如果F(Mx,My)<0,则点M在直线上,选择L点;如果F(Mx,My)>0,则点M在直线下,选择U点,Y方向上加1。 F(Mx,My)=-2W(Py+1/2-ay) + 2H(Px+1-ax) 接下来,当X方向上的值是Px+2时,判断现在的M取值是M’还是M’’。如果前面一步选择的是L点,则取M’(Px+2,Py+1/2);相反,如果前一步选择的是U点,则取M’’ (Px+2,Py+3/2)。    所以分下面两种情况讨论: 1)  如果前一步F的值是负的,则有Fnext=F(Px+2,Py+1/2)=-2W(Py+1/2-ay) + 2H(Px+2-ax) = F(Mx,My)+2H 2)  如果前一步F的值是正的,则有 Fnext=F(Px+2,Py+3/2)=-2W(Py+3/2-ay) + 2H(Px+2-ax) = F(Mx,My)+2(H-W) 初始情况下M=(ax+1,ay+1/2),则有F(x,y)=-2W(ay+1/2-ay)+2H(ax+1-ax)=2H-W,如果这里没有乘以2的话,就会有浮点数存在了。总结下算法流程就是: 1)  初始化F=2H-W,x=ax,y=ay

spacer