跳转到内容

吴小林直线算法

维基百科，自由的百科全书
吴小林直线算法
吴小林算法画出的抗锯齿线段
吴小林算法画出的抗锯齿线段
概况
類別计算机图形学算法
复杂度
相关变量的定义

吴小林算法是一种绘制抗锯齿直线的算法，因为其较高的执行效率被发表在1991年7月的《 Computer Graphics》和1992年6月的《Dr. Dobb's Journal》上。

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

吴小林的《Graphics Gems II》一书描述了一个绘制圆的算法，作为布雷森汉姆圆绘制算法的替代品。 

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

// integer part of x
function ipart(x) is
    return floor(x)

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

// fractional part of x
function fpart(x) is
    return x - floor(x)

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

function drawLine(x0,y0,x1,y1) is
    boolean steep := abs(y1 - y0) > abs(x1 - x0)
    
    if steep then
        swap(x0, y0)
        swap(x1, y1)
    end if
    if x0 > x1 then
        swap(x0, x1)
        swap(y0, y1)
    end if
    
    dx := x1 - x0
    dy := y1 - y0
    gradient := dy / dx
    if dx == 0.0 then
        gradient := 1.0
    end if

    // handle first endpoint
    xend := round(x0)
    yend := y0 + gradient * (xend - x0)
    xgap := rfpart(x0 + 0.5)
    xpxl1 := xend // this will be used in the main loop
    ypxl1 := ipart(yend)
    if steep then
        plot(ypxl1,   xpxl1, rfpart(yend) * xgap)
        plot(ypxl1+1, xpxl1,  fpart(yend) * xgap)
    else
        plot(xpxl1, ypxl1  , rfpart(yend) * xgap)
        plot(xpxl1, ypxl1+1,  fpart(yend) * xgap)
    end if
    intery := yend + gradient // first y-intersection for the main loop
    
    // handle second endpoint
    xend := round(x1)
    yend := y1 + gradient * (xend - x1)
    xgap := fpart(x1 + 0.5)
    xpxl2 := xend //this will be used in the main loop
    ypxl2 := ipart(yend)
    if steep then
        plot(ypxl2  , xpxl2, rfpart(yend) * xgap)
        plot(ypxl2+1, xpxl2,  fpart(yend) * xgap)
    else
        plot(xpxl2, ypxl2,  rfpart(yend) * xgap)
        plot(xpxl2, ypxl2+1, fpart(yend) * xgap)
    end if
    
    // main loop
    if steep then
        for x from xpxl1 + 1 to xpxl2 - 1 do
           begin
                plot(ipart(intery)  , x, rfpart(intery))
                plot(ipart(intery)+1, x,  fpart(intery))
                intery := intery + gradient
           end
    else
        for x from xpxl1 + 1 to xpxl2 - 1 do
           begin
                plot(x, ipart(intery),  rfpart(intery))
                plot(x, ipart(intery)+1, fpart(intery))
                intery := intery + gradient
           end
    end if
end function

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

参考文献

外部链接

检索自“https://zh.wikipedia.org/w/index.php?title=吴小林直线算法&oldid=71758179”