Bilgisayar grafiği algoritmaları

'Bilgisayar' forumunda Özgür tarafından 17 Eyl 2009 tarihinde açılan konu

Konu etiketleri:
  1. Özgür

    Özgür Administrator Site Yetkilisi

    Bresenham'ın Çizgi Algoritması

    Tarihçe

    Bresenham'ın çizgi algoritması, Amerikalı bilgisayar mühendisi Jack Bresenham1960'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

    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ı [değiştir]

    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 (xk, yk) olduğunu ve y-ekseninin yavaş arttığını varsayalım. dalt gerçek doğruyla yk arasındaki uzaklık olsun. düst gerçek doğruyla yk + 1 arasındaki uzaklık olsun.
    Eğer (dalt < düst) ise yk+1 := yk olmalıdır. Aksi halde yk+1 := yk + 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 pkk değeri optimize edilmiş algoritmada error olarak isimlendirilmişti ama burda ardışık error değerlerini karıştırmamak için pk olarak adlandıracağız. olarak adlandıralım. p
    pk = deltax * (dalt - düst) = 2 * deltay * (xk + 1) - 2 * deltax * yk - deltax
    Eğer pk pozitifse gerçek doğru üst piksele daha yakın olduğu için yk+1 = yk + 1, aksi halde yk+1 = yk olacaktır.
    pk+1 - pk = 2 * deltay * (xk+1 - xk) - 2 * deltax * (yk+1 - yk)

    xk+1 = xk + 1 olduğundan
    pk+1 = pk + 2 * deltay - 2 * deltax * (yk+1 - yk)
    Eğer pk pozitifse (yk+1 - yk) = 1; aksi halde (yk+1 - yk) = 0
    Görüldüğü üzere error değeri (yani pk) pozitifse 2 * deltax kadar azaltılıyor ve yk değeri artırılıyor. Ayrıca error değeri, her adımda 2 * deltay kadar artırılmaktadır.
     

Bu Sayfayı Paylaş