Bresenham'ın çizgi algoritması

Bresenham'ın çizgi algoritması kullanılınca ortaya çıkan bir çizgi

Tarihçe

Bresenham'ın çizgi algoritması, Amerikalı bilgisayar mühendisi Jack Bresenham tarafindan, 1960'lı yıllarda IBM için doğrunun bilgisayar ekranına çizimi için geliştirilen bir algoritmadır.

Artıları

Bresenham Algoritmasi DDA'ya göre daha hızlıdır, çünkü DDA'nın aksine ondalıklı sayılarla (float) işlem yapılmaz. Bresenham algoritması tam sayılarla(int) toplama, çıkarma ve ikiyle çarpma işlemlerini içerir. İkiyle çarpma işlemi shift Operasyonu ile Assembler düzeyinde çok hızlı yapılabildiğinden, Bresenham algoritması oldukça verimli bir algoritmadır.

Genel Algoritma

Pseudo kod ile şu şekilde ifade edilir. Bu hali ondalıklı sayılarla işlem içerdiği için kullanılmaz.

 function line(x0, x1, y0, y1)
     int deltax := abs(x1 - x0)
     int deltay := abs(y1 - y0)
     real error := 0
     real deltaerr := deltay / deltax    // Assume deltax != 0 (line is not vertical)
     int y := y0
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         if error ≥ 0.5 then
             y := y + 1
             error := error - 1.0

Optimize Edilmiş Hali

Bu hali sadece tam sayılar kullandığı için oldukça verimlidir. Aşağıdaki hali algoritmanın anlaşılması için basitleştirilmiştir. aşağıdaki hali x-eksenin y-ekseninden daha hızlı arttığını (yani deltax'in deltay'den büyük olduğunu) ve x0'ın x1'den küçük olduğunu varsaymaktadır.

  function line(x0, y0, x1, y1)
      int deltax := abs(x1 - x0)
      int deltay := abs(y1 - y0)
      int error := 2 * deltay - deltax
      int xk := x0
      int yk := y0
      while xk < x1 
           xk+1 := xk + 1
           if error > 0
                yk+1 := yk + 1
                error := error + 2 * deltay - 2 * deltax
           else
                yk+1 := yk
                error := error + 2 * deltay
           xk := xk+1

Matematiksel İspatı

Bresenham algoritması verimliliğini, yavaş artan eksenin belirli bir kurala göre arttığını gözlemlemesine borçludur. Hızlı artan eksen her iterasyondan 1 piksel artarken, yavaş artan eksen bazen sabit kalıp, bazen bir piksel artar. Matematiksel olarak anlatmak istersek:

En son çizilen pikselin koordinatlarının (x_k, y_k) olduğunu ve y-ekseninin yavaş arttığını varsayalım. d_alt gerçek doğruyla y_k arasındaki uzaklık olsun. d_üst gerçek doğruyla y_k + 1 arasındaki uzaklık olsun.

Eğer (d_alt < d_üst) ise y_k+1 := y_k olmalıdır. Aksi halde y_k+1 := y_k + 1 olmalıdır.

y = mx + b doğrusu için

    dalt = y - yk = m(xk + 1) + b - yk

    düst = yk + 1 - y = yk + 1 - m(xk + 1)

    m = (y1 - y0) / (x1 - x0) = deltay / deltax

    dalt - düst = 2 * m * (xk + 1) - 2 * yk - 1
                = 2 * deltay * (xk + 1) / deltax - 2 * yk - 1

Bölüm halindeki deltax'den kurtulmak için bulduğumuz formülü deltax'le çarpalım ve p_k olarak adlandıralım. p_k değeri optimize edilmiş algoritmada error olarak isimlendirilmişti ama burda ardışık error değerlerini karıştırmamak için p_k olarak adlandıracağız.

   pk = deltax * (dalt - düst) = 2 * deltay * (xk + 1) - 2 * deltax * yk - deltax

Eğer p_k pozitifse gerçek doğru üst piksele daha yakın olduğu için y_k+1 = y_k + 1, aksi halde y_k+1 = y_k olacaktır.

  pk+1 - pk = 2 * deltay * (xk+1 - xk) - 2 * deltax * (yk+1 - yk)
 

x_k+1 = x_k + 1 olduğundan

  pk+1 = pk + 2 * deltay - 2 * deltax * (yk+1 - yk)

Eğer p_k pozitifse (y_k+1 - y_k) = 1; aksi halde (y_k+1 - y_k) = 0

Görüldüğü üzere error değeri (yani p_k) pozitifse 2 * deltax kadar azaltılıyor ve y_k değeri artırılıyor. Ayrıca error değeri, her adımda 2 * deltay kadar artırılmaktadır.