Bresenhams çizgi algoritması - Bresenhams line algorithm - Wikipedia

Bresenham'ın çizgi algoritması bir çizgi çizme algoritması bu, bir n-boyutlu raster yakın bir yaklaşım oluşturmak için seçilmelidir iki nokta arasındaki düz çizgi. Genellikle çizmek için kullanılır çizgi ilkelleri içinde bitmap görüntüsü (ör. bir bilgisayar ekranı ), yalnızca tamsayı toplama, çıkarma ve biraz değişiyor hepsi standart olarak çok ucuz işlemlerdir bilgisayar mimarileri. O bir artımlı hata algoritması. Alanında geliştirilen en eski algoritmalardan biridir. bilgisayar grafikleri. Bir uzantı^{[hangi? ]} orijinal algoritmaya göre çizim için kullanılabilir daireler.

Gibi algoritmalar Wu'nun algoritması modern bilgisayar grafiklerinde de sıklıkla kullanılır çünkü antialiasing, Bresenham'ın çizgi algoritmasının hızı ve basitliği, onun hala önemli olduğu anlamına gelir. Algoritma aşağıdaki gibi donanımlarda kullanılır: çiziciler Ve içinde grafik yongaları modern grafik kartları. Ayrıca birçok yerde bulunabilir yazılım grafik kitaplıkları. Algoritma çok basit olduğundan, genellikle her iki aygıt yazılımı ya da grafik donanımı modern grafik kartları.

"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ı Jack Elton Bresenham 1962'de kim geliştirdi? IBM. 2001'de Bresenham şunları yazdı:^[1]

IBM'in San Jose geliştirme laboratuvarında hesaplama laboratuvarında çalışıyordum. Bir Calcomp plotter bir IBM 1401 1407 daktilo konsolu aracılığıyla. [Algoritma] 1962 yazında, muhtemelen bir ay kadar önce üretim kullanımındaydı. O günlerdeki programlar şirketler arasında serbestçe değiş tokuş edildi, böylece Calcomp (Jim Newland ve Calvin Hefte) kopyaları elde etti. 1962 Sonbaharında Stanford'a döndüğümde, Stanford bilgisayar merkezi kütüphanesine bir kopya koydum. 1963'te sunum için çizgi çizim rutininin bir açıklaması kabul edildi. ACM Denver, Colorado'daki ulusal kongre. Hiçbir bildirinin yayınlanmadığı, yalnızca konuşmacıların gündeminin ve ACM'nin Communications of the ACM sayısındaki konuların yayınlandığı bir yıldı. IBM Systems Journal'dan bir kişi, sunumumu yaptıktan sonra makaleyi yayınlayıp yayınlayamayacaklarını sordu. Mutlu bir şekilde kabul ettim ve 1965'te basmışlar.

Bresenham'ın algoritması daireler, elipsler, kübik ve kuadratik bezier eğrileri ve bunların doğal kenar yumuşatılmış versiyonlarını üretmek için genişletildi.^[2]

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 kurallar kullanılacaktır:

• sol üst, piksel koordinatlarının sağ ve aşağı yönlerde artacağı şekilde (0,0) 'dır (örneğin, (7,4)' deki piksel (7,5) 'deki pikselin tam üstünde olacak şekilde) ve
• piksel merkezleri tamsayı koordinatlarına sahiptir.

Çizginin uç noktaları şu noktadaki piksellerdir: ${ displaystyle (x_ {0}, y_ {0})}$ ve ${ displaystyle (x_ {1}, y_ {1})}$, çiftin ilk koordinatı sütun ve ikincisi satırdır.

Algoritma başlangıçta yalnızca oktant segmentin aşağı ve sağa gittiği (${ displaystyle x_ {0} leq x_ {1}}$ ve ${ displaystyle y_ {0} leq y_ {1}}$) ve yatay izdüşümü ${ displaystyle x_ {1} -x_ {0}}$ dikey izdüşümden daha uzun ${ displaystyle y_ {1} -y_ {0}}$ (satırda pozitif eğim 1'den az). Bu oktanda, her sütun için x arasında ${ displaystyle x_ {0}}$ ve ${ displaystyle x_ {1}}$tam olarak bir satır var y (algoritma tarafından hesaplanır) çizginin bir pikselini içerirken, aradaki her satır ${ displaystyle y_ {0}}$ ve ${ displaystyle y_ {1}}$ birden çok rasterleştirilmiş piksel içerebilir.

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

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

Sütunu bildiğimiz için, x, 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 ${ displaystyle (y_ {1} -y_ {0}) / (x_ {1} -x_ {0})}$ yalnızca uç nokta koordinatlarına bağlıdır ve önceden hesaplanabilir ve ideal y ardışık tamsayı değerleri için x başlayarak hesaplanabilir ${ displaystyle y_ {0}}$ ve eğimi tekrar tekrar ekleyerek.

Pratikte, algoritma y koordinatını takip etmez ve m = ∆y / ∆x her seferinde x birer birer artar; her aşamada bir hata sınırını korur ve (a) çizginin pikselden çıktığı noktadan (b) pikselin üst kenarına olan mesafenin negatifini temsil eder. Bu değer ilk olarak ${ displaystyle y_ {0} -0,5}$ (pikselin merkez koordinatlarının kullanılması nedeniyle) ve m her seferinde x koordinat bir artırılır. Hata daha büyük olursa 0.5, çizginin bir piksel yukarı çıktığını biliyoruz ve y yeni pikselin üstünden mesafeyi temsil etmek için hatayı koordine edin ve yeniden ayarlayın - bu, hatadan bir tane çıkararak yapılır. ^[3]

Aşağıda sözde kod örneklem, arsa (x, y) işlev, pikselleri koordinatlarda ortalayarak çizer (x, y) ve abs İadeler mutlak değer:

işlevi satır (x0, y0, x1, y1) gerçek deltax: = x1 - x0 gerçek deltay: = y1 - y0 gerçek deltaerr: = abs (deltay / deltax) // deltax! = 0 varsayalım (çizgi dikey değil),          // bu bölmenin kesirli kısmı koruyacak şekilde yapılması gerektiğine dikkat edin    gerçek error: = 0.0 // Başlangıçta hata yok int y: = y0 için x itibaren x0 -e x1 plot (x, y) hatası: = hata + deltaerr Eğer hata ≥ 0.5 sonra            y: = y + işareti (deltay) hatası: = hata - 1.0

Bu sözde kodun yalnızca yukarıda açıklanan belirli durum için çalıştığını, satırın aşağı ve sağa gittiği ve x değişimden daha büyüktür y.

Türetme

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

Çizgi denklemi

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

Olumlu ve olumsuz yarı düzlemler

Bir çizginin eğim-kesme noktası biçimi şu şekilde yazılır:

${ displaystyle y = f (x) = mx + b}$

burada m eğim ve b y kesme 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ülasyon ve eğimin "yatay mesafeden yükselme" olduğunun kabul edilmesi veya ${ displaystyle Delta y / Delta x}$ sonra

${ displaystyle { başlar {hizalı} 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 şu şekilde yazılabilir:

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

sabitler nerede

• ${ displaystyle A = Delta y}$
• ${ displaystyle B = - Delta x}$
• ${ displaystyle C = ( Delta x) b}$

Çizgi daha sonra herhangi bir yerde A, B ve C sabitleri için tanımlanır. ${ displaystyle f (x, y) = 0}$. Herhangi ${ displaystyle (x, y)}$ o zaman hatta değil ${ displaystyle f (x, y) neq 0}$. Bu formla ilgili her şey yalnızca tamsayıları içerir, eğer x ve y tamsayı ise, sabitler zorunlu olarak tamsayılardır.

Örnek olarak, çizgi ${ displaystyle y = { frac {1} {2}} x + 1}$ o zaman bu şu şekilde yazılabilir ${ displaystyle f (x, y) = x-2y + 2}$. (2,2) noktası doğrunun üzerindedir

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

ve (2,3) noktası çizgide değil

${ displaystyle f (2,3) = (2) -2 (3) + 2 = 2-6 + 2 = -2}$

ve nokta (2, 1) değil

${ displaystyle 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 çizgi, bir düzlemi yarıya böler ve negatif f (x, y) olan yarı düzlem, negatif yarı düzlem olarak adlandırılabilir ve diğer yarı, pozitif yarı düzlem olarak adlandırılabilir. Bu gözlem, türetmenin geri kalanında çok önemlidir.

Algoritma

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

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

sadece çizgi tamsayı koordinatlarında başlayıp bitecek şekilde tanımlandığı için (tamsayı olmayan uç noktalara sahip bir çizgi çizmek tamamen mantıklı olsa da).

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

Eğimin bire eşit veya daha az olduğunu akılda tutarak, sorun şimdi bir sonraki noktanın şu noktada olması gerekip gerekmediğini ortaya koyuyor. ${ displaystyle (x_ {0} + 1, y_ {0})}$ veya ${ displaystyle (x_ {0} + 1, y_ {0} +1)}$. Belki sezgisel olarak, nokta, çizgiye daha yakın olan noktaya göre seçilmelidir. ${ displaystyle x_ {0} +1}$. Birincisine daha yakınsa, çizgiye ilk noktayı, ikincisi ise sonra ikincisini ekleyin. Bunu cevaplamak için, bu iki nokta arasındaki orta noktada çizgi fonksiyonunu değerlendirin:

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

Bunun değeri pozitifse, ideal çizgi orta noktanın altında ve aday noktaya daha yakındır. ${ displaystyle (x_ {0} + 1, y_ {0} +1)}$; gerçekte 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 ${ displaystyle (x_ {0} + 1, y_ {0})}$. Bu gözlemi anlamak çok önemlidir! Bu orta noktadaki çizgi fonksiyonunun değeri, hangi noktanın seçilmesi gerektiğinin tek belirleyicisidir.

Yandaki görüntü, yeşil (3,2) ve (3,3) ile gösterilen iki aday nokta ile doğru üzerinde 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ı şu şekilde 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 orta nokta yöntemine eşdeğerdir çünkü ${ displaystyle f (x_ {0}, y_ {0}) = 0}$ başlangıç ​​noktasında. Bu ifadeyi basitleştirmek şunları sağlar:

${ displaystyle { begin {array} {rclcl} D & = & left [A (x_ {0} +1) + B left (y_ {0} + { frac {1} {2}} sağ) + C right] & - & left [Ax_ {0} + By_ {0} + C right] & = & 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 }}}$

Orta nokta yönteminde olduğu gibi, D pozitifse, o zaman şunu seçin: ${ displaystyle (x_ {0} + 1, y_ {0} +1)}$, yoksa seç ${ displaystyle (x_ {0} + 1, y_ {0})}$.

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

${ displaystyle { begin {dizi} {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}}}$

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

${ displaystyle { begin {dizi} {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 o zaman ${ displaystyle (x_ {0} + 2, y_ {0} +1)}$ aksi takdirde seçilir ${ displaystyle (x_ {0} + 2, y_ {0})}$. Bu karar, hatayı takip eden her noktada toplayarak genelleştirilebilir.

(0,1) 'den (6,4)' e kadar olan çizginin, ızgara çizgileri ve piksellerin bir grafiğini göstererek çizilmesi

Algoritma için tüm türetme yapılır. Performans sorunlarından biri,¹⁄₂ D'nin başlangıç ​​değerindeki faktör. Bunların tümü birikmiş farkın işaretiyle ilgili olduğundan, o zaman her şey sonuçsuz 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 için x, x0'dan x1'e (x, y) Eğer D> 0 y = y + 1 D = D - 2 * dx eğer biterse        D = D + 2 * dy

Bu algoritmayı çalıştırma ${ displaystyle f (x, y) = x-2y + 2}$ (0,1) 'den (6,4)' e kadar olan dx = 6 ve dy = 3 ile aşağıdaki farkları verir:

D = 2 * 3-6 = 0 0'dan 6'ya döngü * x = 0: arsa (0, 1), D≤0: D = 0 + 6 = 6 * x = 1: arsa (1, 1), D> 0: D = 6-12 = -6, y = 1 + 1 = 2, D = -6 + 6 = 0 * x = 2: arsa (2, 2), D≤0: D = 0 + 6 = 6 * x = 3: arsa (3, 2), D> 0: D = 6-12 = -6, y = 2 + 1 = 3, D = -6 + 6 = 0 * x = 4: arsa (4, 3), D≤0: D = 0 + 6 = 6 * x = 5: arsa (5, 3), D> 0: D = 6-12 = -6, y = 3 + 1 = 4, D = -6 + 6 = 0 * x = 6: arsa (6, 4), D≤0: D = 0 + 6 = 6

Bu grafiğin sonucu sağda gösterilmektedir. Çizim, çizgilerin kesişme noktasında (mavi daireler) veya piksel kutularını (sarı kareler) doldurarak görüntülenebilir. Her şeye rağmen, çizim aynıdır.

Tüm vakalar

Ancak, yukarıda belirtildiği gibi bu yalnızca oktant sıfır, yani başlangıçta 0 ile 1 arasındaki bir gradyanla başlayan çizgilerdir; burada x, her yineleme için tam olarak 1 artar ve y, 0 veya 1 artar.

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

plotLineLow (x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 yi = 1 Eğer dy <0 yi = -1 dy = -dy eğer biterse    D = (2 * dy) - dx y = y0 için x, x0'dan x1'e (x, y) Eğer D> 0 y = y + yi D = D + (2 * (dy - dx)) eğer biterse        Başka            D = D + 2 * dy

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

plotLineHigh (x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 xi = 1 Eğer dx <0 xi = -1 dx = -dx eğer biterse    D = (2 * dx) - dy x = x0 için y y0'dan y1'e (x, y) Eğer D> 0 x = x + xi D = D + (2 * (dx - dy)) eğer biterse        Başka            D = D + 2 * dx

Eksiksiz bir çözümün x1> x0 veya y1> y0 olup olmadığını tespit etmesi ve çizimden önce girdi koordinatlarını tersine çevirmesi gerekir.

plotLine (x0, y0, x1, y1) Eğer abs (y1 - y0) Eğer x0> x1 plotLineLow (x1, y1, x0, y0) Başka            plotLineLow (x0, y0, x1, y1) eğer biterse    Başka        Eğer y0> y1 plotLineHigh (x1, y1, x0, y0) Başka            plotLineHigh (x0, y0, x1, y1) eğer biterse    eğer biterse

Doğrudan video belleğine erişen düşük seviyeli uygulamalarda, dikey ve yatay hatların özel durumlarının, oldukça optimize edilebildikleri için ayrı ayrı ele alınması tipik olacaktır.

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

plotLine (int x0, int y0, int x1, int y1) dx = abs (x1-x0); sx = x0 süre (doğru) / * döngü * / plot (x0, y0); Eğer (x0 == x1 && y0 == y1) ara; e2 = 2 * hata; Eğer (e2> = dy) / * e_xy + e_x> 0 * / err + = dy; x0 + = sx; eğer biterse        Eğer (e2 <= dx) / * e_xy + e_y <0 * / err + = dx; y0 + = sy; eğer biterse    bitince

Benzer algoritmalar

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

Bir kullanma ilkesi artan hata Bölünme işlemleri yerine grafikte başka uygulamalar vardır. Bu tekniği hesaplamak için kullanmak mümkündür. U, V koordinatları doku eşlemeli çokgenlerin raster taraması sırasında.^[4] voksel Bazı PC oyunlarında görülen yükseklik haritası yazılım oluşturma motorları da bu prensibi kullandı.

Bresenham ayrıca bir Run-Slice (Run-Length'in aksine) hesaplama algoritması yayınladı.^{[belirsiz ]}

IBM'de Alan Murphy tarafından kalın çizgileri işleyen algoritmanın bir uzantısı oluşturuldu.^[5]

Ayrıca bakınız

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

Notlar

Referanslar

• Bresenham, J.E. (1965). "Bir dijital çizicinin bilgisayar kontrolü için algoritma" (PDF). IBM Systems Journal. 4 (1): 25–30. doi:10.1147 / sj.41.0025. Arşivlenen orijinal (PDF) 28 Mayıs 2008.
• "Bresenham Çizgi Çizme Algoritması" Colin Flanagan tarafından,
• Abrash, Michael (1997). Michael Abrash'ın grafik programlama kara kitabı. Albany, NY: Coriolis. pp.654–678. ISBN  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ğriler Çizmek İç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 3D gizli çizgilerin kaldırılmasını sağlayan bir uzantısı; ayrıca MICAD '87'de CAD / CAM ve Bilgisayar Grafikleri üzerine yayınlanmıştır, sayfa 591 - ISBN  2-86601-084-1.
• Bresenham Algoritmasına Değişiklik Yaparak Çizgi Kalınlaştırma, GİBİ. Murphy, IBM Teknik Açıklama Bülteni, Cilt. 20, No.12, Mayıs 1978.

Dış bağlantılar

• Michael Abrash'ın Grafik Programlama Kara Kitap Özel Sürümü: Bölüm 35: Bresenham Hızlıdır ve Hızlıdır İyi
• Didaktik Javascript uygulaması
• Bresenham Çizgi Çizme Algoritması Colin Flanagan tarafından
• Bresenham algoritmasıyla ilgili Ulusal Standartlar ve Teknoloji Enstitüsü sayfası
• Calcomp 563 Artımlı Plotter Bilgileri
• 3D uzantısı
• Bresenham 2D, 3D, 6D'ye kadar
• Birkaç programlama dilinde Bresenham Algoritması
• Bresenham Algoritmasının Güzelliği - Çizgileri, daireleri, elipsleri ve Bézier eğrilerini çizmek için basit bir uygulama
• Bresenham Algoritmasını Kullanarak Bir Çizgi Çizin
• Java uygulaması
• N-D'de Bresenham Python (numpy) uygulaması