Xiaolin Wu Çizgi Algoritması

Bilgisayar ekranında çizgiler nasıl oluşur desek elbet bir çoğunuz pikseller yardımı ile cevabını verebilirsiniz. Ancak piksellerin bir araya gelmesi ve bunların farklı karşıtlık derecesi ile gerçeğe yakın görünmesi gerçekte nasıl sağlanır bilmediğinizden eminim. Bu makaleyi okurken aynı zamanda bilgisayar mühendisleri için matematiğin ne kadar önemli olduğunu da anlamanızı sağlayacağını umuyorum.

Bilgisayarın anlayacağı tek bir dil vardır o da matematik! Bu sebeble ekranda basit bir çizgi bile oluşturmak istesek bunu matematiksel olarak ifade etmek zorundayız. Bilgisayarı gelişmiş hesap makinesi olarak düşünebilirsiniz. Aslında tam olarak da bir çizgiyi ekrana getirirken arka planda aşağıdaki algoritma kodları çalışmaktadır. Örneğin (1,1) noktasından (3,5) noktasına bir düz çizgi oluşturalım deseniz bunu analitik geometri dersindeki öğrendikleriz yardımıyla kolayca yapabilirdiniz. İşi biraz daha zorlaştıralım ve bu çizginin dışında kalanlar azalarak rengi beyaza doğru kaysın. Bu uğraşı alanına bilgisayar mühendisleri görüntü işleme analizi demektedir. Bunlar basit örnek olsada aslında bugün kullandığımız yüz tanımlama sistemleri, renk ayrıştırma analizleri vb tekniklerin temelinde burada olduğu gibi matematik yatmaktadır.

Xiaolin Wu‘nun çizgi algoritması da, line anti-aliasing (resmin farklı tonda piksellere sahip bölgelerin kenarlarında ara tonlara sahip pikseller oluşturma) tekniği için oluşturulmuş bir algoritmadır. Computer Graphics’in temmuz 1991 sayısında verimli bir anti-aliasing tekniği ve yine Dr. Dobb’s Journal’ın Haziran 1992 sayısında hızlı Anti-aliasing makalesi olarak yayınlanmıştır.

Daha önce kullanılan Bresenham’ın algoritması, hatları çok hızlı bir şekilde çiziyordu ancak kenar yumuşatma işlemini gerçekleştirememekteydi. Buna ek olarak, çizgi bitiş noktalarının piksel grid (ızgarasının) tam sayı noktaları (integer points) olmadığı durumları kesin olarak halledememekteydi. Wu’nun algoritması nispeten hızlıdır, ancak Bresenham’ın algoritmasından daha yavaştır. Algoritmanın mantığı, hattın her iki yanının çizgiden uzaklığına göre renklendirilmiş piksel çiftleri çizmekten ibarettir. Çizgi bitimindeki pikseller ayrıca ele alınır. Bir pikselden daha kısa çizgiler özel bir vaka olarak ele alınır.

Xiaolin Wu’nun Graphics Gems II adlı kitabında daire çizimi algoritmasını da yayımlamıştır. Wu’nun düz çizgi algoritması Bresenham’ın çizgi algoritması yerini aldığı gibi aynı şekilde Wu’nun daire çizme algoritması da Bresenham’ın daire çizme algoritması yerini almıştır.

Algoritma Örneği

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 int(x)

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

// fractional part of x
function fpart(x) is
    if x < 0 return 1 - (x - floor(x)) 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
    
    // 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

• Referanslar
  Abrash, Michael (June 1992). “Fast Antialiasing (Column)”. Dr. Dobb’s Journal. 17 (6): 139(7).
• Wu, Xiaolin (July 1991). “An efficient antialiasing technique”. Computer Graphics. 25 (4): 143–152. doi:10.1145/127719.122734. ISBN 0-89791-436-8.
• Wu, Xiaolin (1991). “Fast Anti-Aliased Circle Generation”. In James Arvo (Ed.). Graphics Gems II. San Francisco: Morgan Kaufmann. pp. 446–450. ISBN 0-12-064480-0.