跳至內容

吳小林直線算法

維基百科,自由的百科全書
吳小林直線算法
吳小林算法畫出的抗鋸齒線段
吳小林算法畫出的抗鋸齒線段
概況
類別計算機圖形學算法
複雜度
相關變量的定義

吳小林算法是一種繪製抗鋸齒直線的算法,因為其較高的執行效率被發表在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逆轉。

參考文獻

外部連結