WU反走样(Anti-aliased)直线初探|游戏开发|中国IT实验室

WU反走样(Anti-aliased)直线初探

来源：chinaitlab整理收集　作者：　时间：2005-3-3

　　普通的Breshenham算法画线很快,但并不是很精细.通常的整数画线因为只能在整数坐标上绘图,所以产生难看的锯齿.我在Michael Abrash的一本书力看到一个很好的反走样直线画法,并决定用非整数坐标改进它.　一个wu直线不仅仅是看上去比一个普通直线好,它也产生更好的动画.一个普通的直线从一个位置简单的跳到下一个位置.然而,一条wu直线非常悠闲的漂到下一个位置.
　　　

　　它是如何工作的?
　　让我们想一下一个反走样直线究竟意味这什么.一条恰当的直线看上去应该是什么样的?直线有多粗?尾端应该是怎么样的?直线是一个一维物体,无限长.它没有什么粗细.线段的尾端看上去什么都不象,它就是尾端而已.这样一个直线不能被画到一个基于像素的显示设备上.
　　在计算机图形中,通常假定线段为一个像素粗.这意味这它可以被画下来.这也意味着他足够细使得不必考虑它的末端应该是什么样子,因为它比一个像素还小,不可以画.
　　在我们设计一个新的wu直线的时候我们必须制定类似的假定.因为这个新的算法可以处理非整数坐标的端点,对于一个小于一像素长的线能做什么呢?
　　假定
　　.假定像素在它们坐标的中心
　　.直线是一个像素粗
　　.直线的末端的形状不重要
　　它可以更好,如果:
　　.两个平行线段,端点相连接,不能分辨出其中一个,一个长线段
　　.直线的亮度/透明的可以被定义
　　最终的算法是怎样的?
　　最终的算法相当容易实现,但是在实际应用中显得太慢.但也不是真正的必要,因为它的效果和另一个更快速的方法几乎相同.不管怎样,我将阐明一些基本的东西.
　　　

　　想像一下,你可以可以放大我们在上面画线的屏幕的像素.理想的画线算法将计算每条线覆盖的精确的区域,从而增
　　加那些像素的亮度.
　　这样一个算法很容易写,在一个更高的分辨率重画屏幕的相关部分,然后把线画到上面,计算出覆盖的像素或者
　　calculating it presicely.
　　然而这需要一些精确度.我们来看下一种方法.
　　一个更明智的算法
　　　

　　这个算法跨骑着直线绘制一对像素.一个主循环将沿着直线的长度画一对像素,端点的像素对将被分别计算.
　　像素对:
　　再想像一次,屏幕的一个特写.画一条几乎水平的线.
　　这个几乎水平的线穿过垂直的像素列.每次跨过像素,x坐标是整数,但是y坐标是非整数.
　　看的更近些,一个单个的跨越点:
　　在每个跨越点,我们将考虑跨骑直线的像素对.两个像素的亮度相应应该是1,中心点的亮度就是理想直线的亮度.
　　直线上的像素的亮度必须于(1-a)成比例,线下面的像素的亮度必须与(1-b)成比例.也就是说越靠近直线的像素应该越亮.
　　沿着直线长度画这样的像素对,那你基本上得到了一个反走样直线.
　　绘制端点
　　最后的事情就是画端点.这不好处理,我仍然没有完全正确的处理它们.这里是我现在用的一种方法.他不很理想,但是非常近似.你将注意到在直线从几乎垂直变得几乎水平的时候它有小心的失灵,反过程也是.你将在直线缓慢的移动过45度的时候注意到这点.
　　真正近距离的看一下端点:
　　　

　　可以看到直线的一个端点,用红色的点来表示.蓝色的点表示像素的中心点.你可以看到,顶点不在像素的中心点上.
　　计算直线端点的两个像素的正确亮度:
　　.把直线延长(向后或向前)到最近的整数x坐标(p).向计算直线上普通的像素对的亮度一样计算这个像素对.然后,因为直线只是覆盖这个像素的很小一部分(i),直线将降低它的亮度.所以亮度应该乘上i.因此,当整条直线向右移动,i将变小,使得这个像素对平滑的变暗.
　　特殊的情况
　　一个长度小于一像素的直线将是怎样的呢?因为它的长度太小以至不能精确表现,所以你可以随便按它应该的模样画.这是我自己的实现方法,我把线拉伸到一个像素常,然后降低它们的亮度.所以一个非常短的直线看上去很暗,当它变长,它就会变亮,当他是一个像素常,它在所在点上将被正常的画出.
　　最后,一些伪代码
　　wu直线的定点数计算需要的一些函数:
　　function trunc(x)
　　return integer part of x
　　end of function
　　function frac(x)
　　return fractional part of x
　　end of function
　　function invfrac(x)
　　return 1 - (fractional part of x)
　　end of function
　　wu直线程序:
　　procedure WuLine(fixpt x1, fixpt y1, fixpt x2, fixpt y2)
　　variable declerations:
　　fixpt variables:
　　grad, xd, yd, length,xm,ym
　　xgap, ygap, xend, yend, xf, yf
　　brigheness1, brigheness2
　　integer variables:
　　x, y, ix1, ix2, iy1, iy2
　　byte variables:
　　c1,c2
　　code starts here:
　　Width and Height of the line
　　xd = (x2-x1)
　　yd = (y2-y1)
　　if abs(xd) > abs(yd) then check line gradient
　　horizontal(ish) lines
　　if x1 > x2 then if line is back to front
　　swap x1 and x2 then swap it round
　　swap y1 and y2
　　xd = (x2-x1) 　　and recalc xd & yd
　　yd = (y2-y1)
　　end if
　　grad = yd/xd　　　　　　gradient of the line
　　
　　
　　End Point 1
　　-----------
　　xend = trunc(x1+.5)　　　　　　　　　　　find nearest integer X-coordinate
　　yend = y1 + grad*(xend-x1)　　　　　　　 and corresponding Y value
　　xgap = invfrac(x1+.5)　　　　　　　　　　distance i
　　ix1　= int(xend)　　　　　　　　　　　　 calc screen coordinates
　　iy1　= int(yend)
　　brightness1 = invfrac(yend) * xgap　　　 calc the intensity of the other
　　brightness2 =　　frac(yend) * xgap　　　 end point pixel pair.
　　c1 = byte(brightness1 * MaxPixelValue) calc pixel values
　　c2 = byte(brightness2 * MaxPixelValue)
　　DrawPixel(ix1,iy1), c1 　　　　 draw the pair of pixels
　　DrawPixel(ix1,iy1+1), c2
　　
　　yf = yend+grad　　　　　　　　　　　　　 calc first Y-intersection for
　　main loop
　　
　　End Point 2
　　-----------
　　xend = trunc(x2+.5)　　　　　　　　　　　find nearest integer X-coordinate
　　yend = y2 + grad*(xend-x2)　　　　　　　 and corresponding Y value
　　xgap = invfrac(x2-.5)　　　　　　　　　　distance i
　　ix2　= int(xend)　　　　　　　　　　　　 calc screen coordinates
　　iy2　= int(yend)
　　brightness1 = invfrac(yend) * xgap　　　 calc the intensity of the first
　　brightness2 =　　frac(yend) * xgap　　　 end point pixel pair.
　　c1 = byte(brightness1 * MaxPixelValue) calc pixel values
　　c2 = byte(brightness2 * MaxPixelValue)
　　DrawPixel(ix2,iy2), c1 draw the pair of pixels
　　DrawPixel(ix2,iy2+1), c2
　　MAIN LOOP
　　---------
　　Loop x from (ix1+1) to (ix2-1) main loop
　　brightness1 = invfrac(yf) 　　　　calc pixel brightnesses
　　brightness2 =　　frac(yf)
　　c1 = byte(brightness1 * MaxPixelValue) calc pixel values
　　c2 = byte(brightness2 * MaxPixelValue)
　　DrawPixel(x,int(yf)), c1 draw the pair of pixels
　　DrawPixel(x,int(yf)+1), c2
　　yf = yf + grad update the y-coordinate
　　end of x loop end of loop
　　else
　　vertical(ish) lines
　　handle the vertical(ish) lines in the
　　same way as the horizontal(ish) ones
　　but swap the roles of X and Y
　　end if
　　end of procedure
　　这里是上面所说的算法的更多的具体描述.为了方便和速度,我在这里使用了定点数.在这种情况下,它显然很方便.
　　首先,我定义了一些函数.
　　最后
　　它被证明是真的可以工作的,而且看上去很奇妙.
　　