吴小林直线算法

维基百科,自由的百科全书
跳转至: 导航搜索
吴小林算法画出的抗锯齿线段

吴小林算法是一种抗锯齿线性算法,并作为一种快速有效的抗锯齿算法发表在1991年7月的《 Computer Graphics》和1992年6月的《Dr. Dobb's Journal》上。

布雷森汉姆(Bresenham)直线算法绘制直线非常快,但它不支持抗锯齿。此外,它不能处理线段末端恰好在整数点像素网格上的情况。一个不成熟的反锯齿画线方法需要非常长的时间,但吴的算法是相当快的(虽然它仍然较布雷森汉姆直线算法慢)。该算法的基本思想是画两个像素点在岔在直线两边,并按照直线相近的颜色着色,而线段末端的像素点另外处理。如果线段宽度小于一像素,将会被作为特殊情况考虑。

这里有一个绘制圆的扩展算法出版在吴小林的《Graphics Gems II》一书中。就像画线算法是布雷森汉姆直线算法的替代品一样,圆绘制算法也是布雷森汉姆圆绘制算法的替代品。

function plot(x, y, c) is
    plot the pixel at (x, y) with brightness c (where 0 ≤ c ≤ 1)

function ipart(x) is
    return integer part of x

function round(x) is
    return ipart(x + 0.5)

function fpart(x) is
    return fractional part of x

function rfpart(x) is
    return 1 - fpart(x)

function drawLine(x1,y1,x2,y2) is
    dx = x2 - x1
    dy = y2 - y1
    if abs(dx) < abs(dy) then                 
      swap x1, y1
      swap x2, y2
      swap dx, dy
    end if
    if x2 < x1
      swap x1, x2
      swap y1, y2
    end if
    gradient = dy / dx
    
    // handle first endpoint
    xend = round(x1)
    yend = y1 + gradient * (xend - x1)
    xgap = rfpart(x1 + 0.5)
    xpxl1 = xend  // this will be used in the main loop
    ypxl1 = ipart(yend)
    plot(xpxl1, ypxl1, rfpart(yend) * xgap)
    plot(xpxl1, ypxl1 + 1, fpart(yend) * xgap)
    intery = yend + gradient // first y-intersection for the main loop
    
    // handle second endpoint
    xend = round (x2)
    yend = y2 + gradient * (xend - x2)
    xgap = fpart(x2 + 0.5)
    xpxl2 = xend  // this will be used in the main loop
    ypxl2 = ipart (yend)
    plot (xpxl2, ypxl2, rfpart (yend) * xgap)
    plot (xpxl2, ypxl2 + 1, fpart (yend) * xgap)
    
    // main loop
    for x from xpxl1 + 1 to xpxl2 - 1 do
        plot (x, ipart (intery), rfpart (intery))
        plot (x, ipart (intery) + 1, fpart (intery))
        intery = intery + gradient
end function

注意:如果在程序开始abs(dx) < abs(dy) 为 true,那么所有的绘图应该做X和Y逆转。

参考文献[编辑]

外部链接[编辑]