Giải thuật Xiaolin Wu
Giải thuật vẽ đoạn thẳng Xiaolin Wu, tiếng Anh: XiaolinWu's line algorithm là giải thuật vẽ đường thẳng khử răng cưa, được giới thiệu lần đầu tiên trên bài báo An Efficient Antialiasing Technique vào tháng 7 năm 1991 trên tờ báo Computer Graphics, cũng như trên bài báo Fast Antialiasing vào tháng 6 năm 1992 trên tờ Dr. Dobb's Journal.

Giải thuật Bresenham vẽ đoạn thẳng vẽ đường thẳng rất nhanh, tuy nhiên lại không có chức năng khử răng cưa. Hơn nữa, giải thuật không kiểm soát được trường hợp điểm cuối của đoạn thẳng không nằm trên một điểm có tọa độ nguyên. Các phương pháp khử răng cưa thường tốn rất nhiều thời gian xử lý, nhưng giải thuật của Xiaolin Wu thì rất nhanh (mặc dù vẫn chậm hơn giải thuật của Bresenham). Thuật toán cơ bản của giải thuật là vẽ các cặp điểm gần nhau hai bên đoạn thẳng và tô màu dựa trên độ ưu tiên. Hai điểm ở hai đầu đoạn thẳng được kiểm soát riêng. Đoạn thẳng ngắn hơn 1 pixel sẽ được xử lý trong trường hợp riêng.

Một giải thuật mở rộng để vẽ đường tròn được giới thiệu bởi Xiaolin Wu trên tạp chí Graphics Gems II. Tương tự như giải thuật vẽ đoạn, giải thuật này dùng để thay thế giải thuật vẽ đường tròn của Bresenham.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</code>

Ghi chú: Nếu trong lần chạy đầu tiên điều kiện abs(dx) < abs(dy) là đúng, quá trình vẽ sẽ thực hiện với x và y ngược nhau.

Tham khảo

Liên kết ngoài
 Xiaolin Wu's homepage

Computer graphics algorithms
Giải thuật vẽ đoạn thẳng Xiaolin Wu , tiếng Anh : XiaolinWu 's line algorithm là giải thuật vẽ đường thẳng khử răng cưa , được giới thiệu lần đầu tiên trên bài báo An Efficient Antialiasing Technique vào thángnămtrên tờ báo Computer Graphics , cũng như trên bài báo Fast Antialiasing vào thángnămtrên tờ Dr . Dobb's Journal . Giải thuật Bresenham vẽ đoạn thẳng vẽ đường thẳng rất nhanh , tuy nhiên lại không có chức năng khử răng cưa . Hơn nữa , giải thuật không kiểm soát được trường hợp điểm cuối của đoạn thẳng không nằm trên một điểm có tọa độ nguyên . Các phương pháp khử răng cưa thường tốn rất nhiều thời gian xử lý , nhưng giải thuật của Xiaolin Wu thì rất nhanh (mặc dù vẫn chậm hơn giải thuật của Bresenham) . Thuật toán cơ bản của giải thuật là vẽ các cặp điểm gần nhau hai bên đoạn thẳng và tô màu dựa trên độ ưu tiên . Hai điểm ở hai đầu đoạn thẳng được kiểm soát riêng . Đoạn thẳng ngắn hơnpixel sẽ được xử lý trong trường hợp riêng . Một giải thuật mở rộng để vẽ đường tròn được giới thiệu bởi Xiaolin Wu trên tạp chí Graphics Gems II . Tương tự như giải thuật vẽ đoạn , giải thuật này dùng để thay thế giải thuật vẽ đường tròn của Bresenham.function plot(x , y , c) is plot the pixel at (x , y) with brightness c (where≤ c ≤ // integer part of x function ipart(x) is return floor(x) function round(x) is return ipart(x +5) // fractional part of x function fpart(x) is return x - floor(x) function rfpart(x) is return- fpart(x) function draw Line(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 then gradient \ :=0 end if / / handle first endpoint xend \ := round(x0) yend \ := y0 + gradient * (xend - x0) xgap \: = rfpart(x0 +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 +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 +to xpxl2 -do begin plot(ipart(intery) , x , rfpa rt(intery)) plot(ipart(intery)+1 , x , fpart(intery)) intery \: = intery + gradient end else for x from xpxl1 +to xpxl2 -do begin plot(x , ipart(intery) , rfpart(intery)) plot(x , ipart(intery)+1 , fpart(intery)) intery \: = intery + gradient end end if end function</code> Ghi chú : Nếu trong lần chạy đầu tiên điều kiện abs(dx) < abs(dy) là đúng , quá trình vẽ sẽ thực hiện với x và y ngược nhau . Tham khảo Liên kết ngoài Xiaolin Wu 's homepage Computer graphics algorithms