Bresenham'ın çizgi algoritması - Bresenham's line algorithm

Bresenham'ın çizgi algoritması a, çizgi çizimi algoritması bir noktaları tespit n boyutlu raster bir yakın bir yaklaşım oluşturmak amacıyla seçilmelidir iki nokta arasındaki düz çizgi . Standart bilgisayar mimarilerinde hepsi çok ucuz işlemler olan yalnızca tamsayı toplama, çıkarma ve bit kaydırma kullandığından, bir bitmap görüntüsünde (örneğin bir bilgisayar ekranında ) çizgi ilkelleri çizmek için yaygın olarak kullanılır . Bu bir olan artan hata algoritması . Bilgisayar grafikleri alanında geliştirilen en eski algoritmalardan biridir . Bir uzantı orijinal algoritmaya çiziminde kullanılabilir çevreler .

Wu'nun algoritması gibi algoritmalar , antialiasing'i destekleyebildikleri için modern bilgisayar grafiklerinde de sıklıkla kullanılırken , Bresenham'ın çizgi algoritmasının hızı ve basitliği, bunun hala önemli olduğu anlamına gelir. Algoritma, çiziciler gibi donanımlarda ve modern grafik kartlarının grafik yongalarında kullanılır . Ayrıca birçok yazılım grafik kitaplığında bulunabilir . Algoritma çok basit olduğu için, genellikle modern grafik kartlarının belleniminde veya grafik donanımında uygulanır .

"Bresenham" etiketi bugün Bresenham'ın orijinal algoritmasını genişleten veya değiştiren bir algoritma ailesi için kullanılmaktadır.

Tarih

Bresenham'ın çizgi algoritması, adını 1962'de IBM'de geliştiren Jack Elton Bresenham'dan almıştır . 2001 yılında Bresenham şunları yazdı:

IBM'in San Jose geliştirme laboratuvarındaki hesaplama laboratuvarında çalışıyordum. IBM 1401'e 1407 daktilo konsolu aracılığıyla bir Calcomp çizici bağlanmıştı . [Algoritma] 1962 yazında, muhtemelen bir ay kadar önce üretimdeydi. O günlerde programlar şirketler arasında serbestçe değiş tokuş edildi, bu nedenle Calcomp'un (Jim Newland ve Calvin Hefte) kopyaları vardı. 1962 sonbaharında Stanford'a döndüğümde, bir kopyasını Stanford bilgisayar merkezi kütüphanesine koydum. Çizgi çizme rutininin bir açıklaması, Denver, Colorado'daki 1963 ACM ulusal kongresinde sunulmak üzere kabul edildi . Hiçbir bildiri kitabının yayımlanmadığı, sadece konuşmacıların gündeminin ve ACM'nin İletişimleri'nin bir sayısında yer alan konuların yayınlandığı bir yıldı. IBM Systems Journal'dan bir kişi, sunumumu yaptıktan sonra makaleyi yayınlayıp yayınlamayacaklarını sordu. Memnuniyetle kabul ettim ve 1965'te bastılar.

Bresenham'ın algoritması, daireler, elipsler, kübik ve ikinci dereceden bezier eğrilerinin yanı sıra bunların yerel anti-aliased versiyonlarını üretecek şekilde genişletildi.

Yöntem

Bresenham'ın çizgi algoritmasının sonucunun çizimi. (0,0) ızgaranın sol üst köşesinde, (1,1) satırın sol üst ucunda ve (11, 5) satırın sağ alt ucundadır.

Aşağıdaki konvansiyonlar kullanılacaktır:

• sol üst kısım (0,0)'dır, öyle ki piksel koordinatları sağ ve aşağı yönlerde artar (örn. (7,4)'deki piksel, (7,5)'daki pikselin hemen üzerindedir) ve
• piksel merkezlerinin tamsayı koordinatları vardır.

Hattın bitiş noktaları olarak pikselleri ve kolon birinci çiftin koordine edilir ve ikinci satırdır. ${\görüntüleme stili (x_{0},y_{0})}$${\görüntüleme stili (x_{1},y_{1})}$

Algoritma başlangıçta yalnızca segmentin aşağı ve sağa ( ve ) gittiği ve yatay projeksiyonunun dikey projeksiyondan daha uzun olduğu oktant için sunulacaktır (çizginin pozitif eğimi 1'den azdır). Bu oktanda, ve arasındaki her bir x sütunu için , çizginin bir pikselini içeren tam olarak bir y satırı (algoritma tarafından hesaplanmıştır) vardır ve aradaki ve arasındaki her satır birden fazla rasterleştirilmiş piksel içerebilir. ${\displaystyle x_{0}\leq x_{1}}$${\displaystyle y_{0}\leq y_{1}}$${\displaystyle x_{1}-x_{0}}$${\displaystyle y_{1}-y_{0}}$${\görüntüleme stili x_{0}}$${\görüntüleme stili x_{1}}$${\görüntüleme stili y_{0}}$${\görüntüleme stili y_{1}}$

Bresenham'ın algoritması , aynı x için ideal (kesirli) y'ye en yakın piksel merkezine karşılık gelen y tamsayısını seçer ; ardışık sütunlarda y aynı kalabilir veya 1 artabilir. Uç noktalardan geçen doğrunun genel denklemi şu şekilde verilir:

${\displaystyle {\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}} }$.

x sütununu bildiğimiz için pikselin satırı y , bu miktar en yakın tam sayıya yuvarlanarak verilir:

${\displaystyle y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}}$.

Eğim yalnızca son nokta koordinatlarına bağlıdır ve önceden hesaplanabilir ve x'in ardışık tamsayı değerleri için ideal y , eğimden başlayarak ve eğimi tekrar tekrar ekleyerek hesaplanabilir . ${\displaystyle (y_{1}-y_{0})/(x_{1}-x_{0})}$${\görüntüleme stili y_{0}}$

Pratikte, algoritma , x'in her bir arttığında m = ∆y/∆x artan y koordinatını takip etmez ; (a) çizginin pikselden çıktığı nokta ile (b) pikselin üst kenarı arasındaki mesafenin negatifini temsil eden her aşamada bir hatayı bağlı tutar. Bu değer ilk olarak (pikselin merkez koordinatlarının kullanılması nedeniyle) olarak ayarlanır ve x koordinatı her bir artırıldığında m ile artırılır. Hata 0,5'ten büyük olursa, çizginin bir piksel yukarı hareket ettiğini ve y koordinatımızı artırmamız gerektiğini ve hatayı, yeni pikselin tepesinden olan mesafeyi temsil edecek şekilde yeniden ayarlamamız gerektiğini biliriz . hata. ${\displaystyle y_{0}-0.5}$

türetme

Bresenham'ın algoritmasını türetmek için iki adım atılmalıdır. İlk adım, bir doğrunun denklemini tipik eğim-kesişim biçiminden farklı bir şeye dönüştürmektir; ve sonra bu yeni denklemi, hata birikimi fikrine dayalı bir çizgi çizmek için kullanmak.

çizgi denklemi

y=f(x)=.5x+1 veya f(x,y)=x-2y+2

Pozitif ve negatif yarım düzlemler

Bir doğrunun eğim-kesişim biçimi şu şekilde yazılır:

${\görüntüleme stili y=f(x)=mx+b}$

burada m eğim ve b y-kesişim noktasıdır. Bu sadece x'in bir fonksiyonudur ve bu denklemi hem x hem de y'nin bir fonksiyonu olarak yazmak faydalı olacaktır. Cebirsel manipülasyonu kullanma ve eğimin "koşu üzerinde yükselme" veya daha sonra olduğunun farkına varma${\displaystyle \Delta y/\Delta x}$

${\displaystyle {\begin{hizalanmış}y&=mx+b\\y&={\frac {(\Delta y)}{(\Delta x)}}x+b\\(\Delta x)y&=(\ Delta y)x+(\Delta x)b\\0&=(\Delta y)x-(\Delta x)y+(\Delta x)b\end{hizalı}}}$

Bu son denklemin x ve y'nin bir fonksiyonu olmasına izin verilirse şöyle yazılabilir:

${\displaystyle f(x,y)=0=Ax+By+C}$

sabitler nerede

• ${\displaystyle A=\Delta y}$
• ${\görüntüleme stili B=-\Delta x}$
• ${\görüntüleme stili C=(\Delta x)b}$

Çizgi daha sonra bazı A, B ve C sabitleri için herhangi bir yerde tanımlanır . Herhangi için değil on line sonra . Bu formla ilgili her şey, yalnızca x ve y tamsayılarsa tamsayıları içerir, çünkü sabitler zorunlu olarak tamsayılardır. ${\görüntüleme stili f(x,y)=0}$${\görüntüleme stili (x,y)}$${\görüntüleme stili f(x,y)\neq 0}$

Örnek olarak, o zaman bu satır şu şekilde yazılabilir . (2,2) noktası doğru üzerindedir. ${\displaystyle y={\frac {1}{2}}x+1}$${\görüntüleme stili f(x,y)=x-2y+2}$

${\displaystyle f(2,2)=x-2y+2=(2)-2(2)+2=2-4+2=0}$

ve (2,3) noktası doğru üzerinde değil

${\görüntüleme stili f(2,3)=(2)-2(3)+2=2-6+2=-2}$

ve nokta da (2,1) değil

${\görüntüleme stili f(2,1)=(2)-2(1)+2=2-2+2=2}$

(2,1) ve (2,3) noktalarının doğrunun zıt taraflarında olduğuna ve f(x,y)'nin pozitif veya negatif olarak değerlendirildiğine dikkat edin. Bir doğru, bir düzlemi yarıya böler ve eksi f(x,y) olan yarı-düzlem, negatif yarı-düzlem ve diğer yarısı, pozitif yarı-düzlem olarak adlandırılabilir. Bu gözlem, türetmenin geri kalanında çok önemlidir.

algoritma

Açıkçası, başlangıç ​​noktası çizgide

${\displaystyle f(x_{0},y_{0})=0}$

sadece çizgi tamsayı koordinatlarında başlayacak ve bitecek şekilde tanımlandığı için (tamsayı olmayan bitiş noktalarına sahip bir çizgi çizmek tamamen mantıklı olsa da).

Aday noktası (2,2) mavi ve iki aday noktası yeşil (3,2) ve (3,3)

Eğimin bire eşit veya daha küçük olduğunu akılda tutarak, sorun şimdi bir sonraki noktanın veya 'da mı olması gerektiği konusunda kendini gösteriyor . Belki de sezgisel olarak nokta, çizgiye hangisinin daha yakın olduğuna göre seçilmelidir . Birincisine daha yakınsa, o zaman ilk noktayı çizgiye, ikincisi ise ikincisini dahil edin. Bunu yanıtlamak için, bu iki nokta arasındaki orta noktada çizgi işlevini değerlendirin: ${\displaystyle (x_{0}+1,y_{0})}$${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle x_{0}+1}$

${\displaystyle f(x_{0}+1,y_{0}+{\tfrac {1}{2}})}$

Bunun değeri pozitif ise ideal doğru orta noktanın altında ve aday noktaya daha yakındır ; aslında y koordinatı ilerlemiştir. Aksi takdirde ideal çizgi orta noktanın içinden veya üstünden geçer ve y koordinatı ilerlememiştir; bu durumda noktayı seçin . Bu gözlemi anlamak çok önemlidir! Bu orta noktadaki çizgi fonksiyonunun değeri, hangi noktanın seçilmesi gerektiğinin tek belirleyicisidir. ${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle (x_{0}+1,y_{0})}$

Yandaki resim, yeşil (3,2) ve (3,3) olarak iki aday noktası olan doğru üzerinde olmak üzere seçilen mavi noktayı (2,2) göstermektedir. Siyah nokta (3, 2.5), iki aday nokta arasındaki orta noktadır.

Tamsayı aritmetiği için algoritma

Alternatif olarak, orta noktalarda f(x,y)'yi değerlendirmek yerine noktalar arasındaki fark kullanılabilir. Bu alternatif yöntem, genellikle kayan nokta aritmetiği kullanmaktan daha hızlı olan yalnızca tamsayı aritmetiğine izin verir. Alternatif yöntemi türetmek için farkı aşağıdaki gibi tanımlayın:

${\displaystyle D=f(x_{0}+1,y_{0}+{\tfrac {1}{2}})-f(x_{0},y_{0})}$

İlk karar için bu formülasyon, başlangıç ​​noktasından itibaren orta nokta yöntemine eşdeğerdir . Bu ifadenin sadeleştirilmesi şunları sağlar: ${\displaystyle f(x_{0},y_{0})=0}$

${\displaystyle {\begin{array}{rclcl}D&=&\left[A(x_{0}+1)+B\left(y_{0}+{\frac {1}{2}}\sağ) +C\sağ]&-&\sol[Ax_{0}+By_{0}+C\sağ]\\&=&\left[Ax_{0}+By_{0}+C+A+{\frac { 1}{2}}B\sağ]&-&\sol[Ax_{0}+By_{0}+C\sağ]\\&=&A+{\frac {1}{2}}B\end{dizi }}}$

Tıpkı orta nokta yönteminde olduğu gibi, eğer D pozitifse 'yi seçin , aksi halde 'yi seçin . ${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle (x_{0}+1,y_{0})}$

Eğer seçilirse seçilsin, D değişim olacak: ${\displaystyle (x_{0}+1,y_{0})}$

${\displaystyle {\begin{array}{lclcl}\Delta D&=&f(x_{0}+2,y_{0}+{\tfrac {1}{2}})-f(x_{0}+1) ,y_{0}+{\tfrac {1}{2}})&=&A&=&\Delta y\\\end{dizi}}}$

seçilirse , D'deki değişiklik şöyle olacaktır: ${\displaystyle (x_{0}+1,y_{0}+1)}$

${\displaystyle {\begin{array}{lclcl}\Delta D&=&f(x_{0}+2,y_{0}+{\tfrac {3}{2}})-f(x_{0}+1) ,y_{0}+{\tfrac {1}{2}})&=&A+B&=&\Delta y-\Delta x\end{dizi}}}$

Yeni D pozitifse seçilir, aksi halde . Bu karar, sonraki her noktada hata toplanarak genelleştirilebilir. ${\displaystyle (x_{0}+2,y_{0}+1)}$${\görüntüleme stili (x_{0}+2,y_{0})}$

Izgara çizgileri ve piksellerin bir çizimini gösteren (0,1) ile (6,4) arasındaki çizgiyi çizme

Algoritma için tüm türetme işlemleri yapılır. Bir performans sorunu, D'nin başlangıç ​​değerindeki 1/2 faktörüdür. Tüm bunlar, birikmiş farkın işaretiyle ilgili olduğundan, sonuç olmadan her şey 2 ile çarpılabilir.

Bu, yalnızca tamsayı aritmetiği kullanan bir algoritma ile sonuçlanır.

plotLine(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    D = 2*dy - dx
    y = y0

    for x from x0 to x1
        plot(x,y)
        if D > 0
            y = y + 1
            D = D - 2*dx
        end if
        D = D + 2*dy

Bu algoritmayı (0,1) ile (6,4) arasında çalıştırmak, dx=6 ve dy=3 ile aşağıdaki farklılıkları verir: ${\görüntüleme stili f(x,y)=x-2y+2}$

D=2*3-6=0
Loop from 0 to 6
 * x=0: plot(0, 1), D≤0: D=0+6=6
 * x=1: plot(1, 1), D>0: D=6-12=-6, y=1+1=2, D=-6+6=0
 * x=2: plot(2, 2), D≤0: D=0+6=6
 * x=3: plot(3, 2), D>0: D=6-12=-6, y=2+1=3, D=-6+6=0
 * x=4: plot(4, 3), D≤0: D=0+6=6
 * x=5: plot(5, 3), D>0: D=6-12=-6, y=3+1=4, D=-6+6=0
 * x=6: plot(6, 4), D≤0: D=0+6=6

Bu grafiğin sonucu sağda gösterilir. Çizim, çizgilerin kesiştiği noktada çizerek (mavi daireler) veya piksel kutularını doldurarak (sarı kareler) görüntülenebilir. Ne olursa olsun kurgu aynı.

Tüm vakalar

Bununla birlikte, yukarıda bahsedildiği gibi, bu yalnızca sıfır oktanı içindir , yani orijinde 0 ile 1 arasında bir eğimle başlayan, x'in yineleme başına tam olarak 1 arttığı ve y'nin 0 veya 1 arttığı çizgiler için geçerlidir.

Algoritma, y'nin artması veya azalması gerekip gerekmediği (yani dy < 0) kontrol edilerek 0 ile -1 arasındaki gradyanları kapsayacak şekilde genişletilebilir.

plotLineLow(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    yi = 1
    if dy < 0
        yi = -1
        dy = -dy
    end if
    D = (2 * dy) - dx
    y = y0

    for x from x0 to x1
        plot(x, y)
        if D > 0
            y = y + yi
            D = D + (2 * (dy - dx))
        else
            D = D + 2*dy
        end if

X ve y eksenini değiştirerek, pozitif veya negatif dik eğimler için bir uygulama şu şekilde yazılabilir:

plotLineHigh(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    xi = 1
    if dx < 0
        xi = -1
        dx = -dx
    end if
    D = (2 * dx) - dy
    x = x0

    for y from y0 to y1
        plot(x, y)
        if D > 0
            x = x + xi
            D = D + (2 * (dx - dy))
        else
            D = D + 2*dx
        end if

Eksiksiz bir çözümün x1 > x0 veya y1 > y0 olup olmadığını algılaması ve çizimden önce giriş koordinatlarını tersine çevirmesi gerekir, böylece

plotLine(x0, y0, x1, y1)
    if abs(y1 - y0) < abs(x1 - x0)
        if x0 > x1
            plotLineLow(x1, y1, x0, y0)
        else
            plotLineLow(x0, y0, x1, y1)
        end if
    else
        if y0 > y1
            plotLineHigh(x1, y1, x0, y0)
        else
            plotLineHigh(x0, y0, x1, y1)
        end if
    end if

Doğrudan video belleğine erişen düşük seviyeli uygulamalarda, dikey ve yatay çizgilerin özel durumlarının yüksek düzeyde optimize edilebildiklerinden ayrı olarak ele alınması tipik olacaktır.

Bazı sürümler, x ve y koordinatları arasındaki pozitif ve negatif hatayı dengeleyerek tüm oktant çizgi çizimlerini gerçekleştirmek için Bresenham'ın tamsayı artımlı hata ilkelerini kullanır. Siparişin mutlaka garanti edilmediğini unutmayın; başka bir deyişle, (x0, y0)'dan (x1, y1)'e veya (x1, y1)'den (x0, y0)'a doğru çizilebilir.

plotLine(int x0, int y0, int x1, int y1)
    dx =  abs(x1-x0);
    sx = x0<x1 ? 1 : -1;
    dy = -abs(y1-y0);
    sy = y0<y1 ? 1 : -1;
    err = dx+dy;  /* error value e_xy */
    while (true)   /* loop */
        plot(x0, y0);
        if (x0 == x1 && y0 == y1) break;
        e2 = 2*err;
        if (e2 >= dy) /* e_xy+e_x > 0 */
            err += dy;
            x0 += sx;
        end if
        if (e2 <= dx) /* e_xy+e_y < 0 */
            err += dx;
            y0 += sy;
        end if
    end while

benzer algoritmalar

Bresenham algoritması, biraz değiştirilmiş dijital diferansiyel analizör olarak yorumlanabilir (örtüşmeyen çokgen rasterleştirme için gerekli olan 0 yerine hata eşiği olarak 0,5 kullanılır).

Bölme işlemleri yerine artan bir hata kullanma ilkesi, grafiklerde başka uygulamalara sahiptir. Doku haritalı çokgenlerin raster taraması sırasında U,V koordinatlarını hesaplamak için bu tekniği kullanmak mümkündür . Voksel bazı PC oyunlarında görülen heightmap yazılım render motorları da bu ilkeyi kullandı.

Bresenham ayrıca bir Run-Slice (Run-Length'in aksine) hesaplama algoritmasını yayınladı. Bu yöntem bir dizi ABD patentinde temsil edilmiştir:

Kalın çizgileri işleyen algoritmanın bir uzantısı, IBM'de Alan Murphy tarafından oluşturuldu.

Ayrıca bakınız

• Sayısal diferansiyel çözümleyici (grafik algoritması) , çizgileri ve üçgenleri rasterleştirmek için basit ve genel bir yöntem
• Xiaolin Wu'nun çizgi algoritması , antialiasing ile benzer şekilde hızlı bir çizgi çizme yöntemi
• Orta nokta daire algoritması , daire çizmek için benzer bir algoritma

Notlar

Referanslar

• Bresenham, JE (1965). "Dijital çizicinin bilgisayar kontrolü için algoritma" (PDF) . IBM Sistemleri Dergisi . 4 (1): 25–30. doi : 10.1147/sj.41.0025 . Arşivlenmiş orijinal (PDF) 28 Mayıs 2008 tarihinde.
• "Bresenham Çizgi Çizme Algoritması" , Colin Flanagan
• Abrash, Michael (1997). Michael Abrash'ın grafik programlama kara kitabı . Albany, NY: Coriolis. s.  654–678 . ISBN'si 978-1-57610-174-2. C'deki algoritmanın çok optimize edilmiş bir versiyonu ve iç işleyişinin tüm detayları ile video oyunlarında kullanım için montaj
• Zingl, Alois (2012). "Eğrileri Çizmek için Rasterleştirme Algoritması" (PDF) ., Bresenham Algoritmalarının Güzelliği

daha fazla okuma

• Patrick-Gilles Maillot'un Tezi , Bresenham çizgi çizme algoritmasının 3B gizli çizgileri ortadan kaldırmaya yönelik bir uzantısıdır; ayrıca CAD/CAM ve Bilgisayar Grafikleri üzerine MICAD '87 tutanaklarında yayınlanmıştır, sayfa 591 - ISBN  2-86601-084-1 .
• Bresenham's Algorithm'de Değişiklik Yaparak Çizgi Kalınlaştırma , AS Murphy, IBM Teknik Açıklama Bülteni, Cilt. 20, Sayı 12, Mayıs 1978.

yerine [ki] ACM 20 Dairesel Yaylar Şubat 1977 Haberleşme Artan Dijital Ekran Teknik Raporu 1964 Ocak-27 -11- Çember Algoritması TR-02-286 IBM San Jose Laboratuarı veya A Lineer Algoritma (2: daire uzatma kullanım için ):100-106 DOI:10.1145/359423.359432

Dış bağlantılar

• Michael Abrash'ın Grafik Programlama Kara Kitap Özel Baskısı: Bölüm 35: Bresenham Hızlıdır ve Hızlıdır İyidir
• Colin Flanagan'ın Bresenham Çizgi Çizimi Algoritması
• Bresenham'ın algoritmasında Ulusal Standartlar ve Teknoloji Enstitüsü sayfası
• Calcomp 563 Artımlı Plotter Bilgileri
• Çeşitli programlama dillerinde Bresenham Algoritması
• Bresenham Algoritmasının Güzelliği – Çizgileri, daireleri, elipsleri ve Bézier eğrilerini çizmek için basit bir uygulama