Bresenham Çizgi Algoritması

Geometrik şekillerin bilgisayar ekranlarında çizdirilmesi, modern bilgisayarların ilk kez ortaya çıktığı zamanlardan bu yana geçerli bir problemdir. Bildiğiniz gibi kullandığımız dijital aygıtların ekranları piksel denilen, gözümüzle ayırt edemeyeceğimiz kadar küçük noktalardan oluşur. Pikseller dikdörtgen şeklindedir ve kırmızı-yeşil-mavi renklerinin belirli oranlarda bir araya gelerek oluşturduğu farklı renkleri yayarlar. Binlerce hatta milyonlarca piksel bir araya getirilir ve her bir pikselin doğru zamanda doğru renkleri oluşturması sağlanarak; ekranlarımızda fotoğraf, video ve diğer görsel ifadeler canlandırılabilir.

Image for post
Image for post
Piksellerin yakından görünümü. kaynak

Bilgisayarların geometrik şekilleri çizebilmesi üzerine geliştirilen ilk yöntemlerden biri DDA (Digital Differential Analyzer) algoritmasıdır. DDA algoritması; çizilecek doğrunun eğimini hesaplar ve iterasyon miktarını eğimin büyüklüğüne göre belirler. Buna göre; eğim 1'den büyükse doğrunun y-eksenindeki uzunluğu kadar, 1'den küçükse x-eksenindeki uzunluğu kadar işlemler tekrarlanır (uzunluklar piksel sayısı ile ölçülür). Buradaki sorun: Doğru, aynı satır veya sütunda birden fazla piksel üzerinden geçerse hangisini seçmek gerektiğidir. Doğrunun mümkün olduğu kadar düzgün gözükebilmesi için, (eğime göre) x veya y eksenindeki pikselleri tekrara düşmeden boyamak sağlıklı bir yöntem olacaktır. DDA algoritması basitçe; aynı satır/sütunda kesilen piksellerden, doğruya en yakın olanı seçmektedir.

Image for post
Image for post
İstenen doğuyu oluşturan pikseller görülmektedir. Dikkatli incelenirse, aynı eksende kesilen pikseller arasından doğruya en yakın olanların seçildiği anlaşılabilir.

Bilgisayarın DDA algoritmasını yürütmesi görece maliyetli ve yavaştır. Çünkü bahsettiğimiz en uygun pikselin belirlenmesi işlemi, aslında ondalıklı bir sayının yuvarlamasına tekabül eder. Bilindiği gibi bilgisayarların ondalıklı sayılar üzerinden işlemler yapması, tam sayılara göre daha yavaş gerçekleşir. On binlerce piksel için bu işlemin tekrarlanması, devasa bir hesaplama maliyeti ortaya çıkarır. Bu yüzden DDA algoritması, anlaşılması ve uygulanması bakımından kolay olsa da performanslı bir algoritma değildir.

1960’lı yıllarda IBM’de çalışmakta olan Jack E. Bresenham, geometrik şekilleri hızlı ve düşük bir performans maliyetiyle çizebilmek için yeni bir algoritma geliştirmeye koyulur. Çalışmalarının neticesinde Bresenham Algoritması olarak literatüre kazandırılan yeni yöntem, temelde şu prensipleri sağlamaktadır:

  • Ondalıklı sayılarla işlemler olmayacak.
  • Mümkün olduğu kadar az aritmetik işlem olacak.
  • Sayıların birbirleriyle karşılaştırılması yerine 0 ile karşılaştırılması sağlanacak (0 ile karşılaştırmak, yalnızca tek bir bitin sorgulanmasıyla gerçekleştiği için daha hızlıdır).

Teoride geliştirilen bu düşüncelerin, beklendiği gibi daha verimli sonuçlar ürettiği günümüzde ispatlanmıştır.

Bresenham algoritmasının basit bir uygulamasını JavaScript üzerinde gerçekleştirmeyi deneyelim (İşimizi bir nebze kolaylaştırdığı için p5.js kütüphanesini bu örnek üzerinde kullandım.)

  • Öncelikle, ekranda kullanıcı tarafından belirtilecek pikselleri tanımlayan basit bir sınıf oluşturalım.
class Point {
constructor(x, y) {
this.x;
this.y;
}
setX(x) {this.x = x}
setY(y) {this.y = y}
getX() {return this.x;}
getY() {return this.y;}
}
  • Ardından ‘mousePressed’ fonksiyonu içerisine, fareye hangi piksel üzerinde tıklanmışsa o pikselin bilgilerini alıp ‘Point’ nesnelerine kaydeden bloğu oluşturalım (mousePressed, p5.js kütüphanesinin otomatik çalıştırdığı bir fonksiyondur).
let points = [];
let check = false;
let bresenhamCheck = false;
let p1 = new Point();
let p2 = new Point();
function mousePressed() {
if (mouseX >= 0 && mouseX <= width && mouseY >= 0 && mouseY <= height) {
if (!check) {
p1.setX(mouseX - mouseX % w);
p1.setY(mouseY - mouseY % h);
points.push([p1.getX(), p1.getY()]);
} else {
p2.setX(mouseX - mouseX % w);
p2.setY(mouseY - mouseY % h);
points.push([p2.getX(), p2.getY()]);
bresenhamCheck = true;
}
check = !check;
}
}
  • ‘points’ dizisi boyanacak pikselleri tutmaktadır. ‘bresenhamCheck’ ise ikinci noktanın belirtilmesinden sonra Bresenham algoritmasının çalışmasını sağlayan değişkendir.
  • Şimdi de Bresenham algoritmasını oluşturalım. Algoritmayı ‘runBresenham’ adında bir fonksiyon ile oluşturuyoruz:
let x, y, dx, dy;
let s1, s2;

x = p1.getX();
y = p1.getY();
dx = abs(p2.getX() - p1.getX()) / w;
dy = abs(p2.getY() - p1.getY()) / h;
s1 = getSign(p2.getX() - p1.getX()) * w;
s2 = getSign(p2.getY() - p1.getY()) * h;
let interchange;
  • ‘x’ ve ‘y’ değişkenleri ilk pikselin koordinatlarını, ‘dx’ ve ‘dy’ iki noktanın x ve y eksenlerindeki mutlak farkını, ‘s1’ ve ‘s2’ ise doğrunun yönelimini belirlemek için bu farkların işaretlerini tutmaktadır. ‘interchange’ değişkeni ise adım sayısını belirlemek üzere yardımcı bir değişkendir. Not: ‘w’ ve ‘h’ değişkenleri algoritmanın bir parçası değildir. Piksellerin ekrandaki gösterimini büyütmek/küçültmek için kullanılmaktadır.
if (dy > dx) {
let temp = dy;
dy = dx;
dx = temp;
interchange = 1;
}
  • Buradaki işlemlerle adım sayısını belirliyoruz. Adım sayısı, DDA algoritmasında da olduğu gibi, doğrunun eksenlerdeki uzunluklarından en büyük olanına eşitlenir.
let err = 2 * dy - dx;

for (let i = 0; i < (dx - 1); ++i) {
if (err > 0) {
if (interchange == 1) x += s1;
else y += s2;
err -= 2 * dx;
}

if (interchange == 1) y += s2;
else x += s1;

err += 2 * dy;

points.push([x, y]);
}
  • Son olarak belirlenen adım sayısı kadar döngümüzü çalıştıralım. ‘err’ değişkeni bir hata değişkenidir ve belirlenen piksellerin doğrudan ne kadar saptığını hesaplamaktadır. Yapılan hesaplamalara göre en doğru pikseller belirlenir ve points dizisine eklenir.

Uygulamayı çalıştırıp noktaları belirttikten sonraki çıktımız şu şekildedir:

Image for post
Image for post

Uygulamanın kaynak kodlarına buradan ulaşabilirsiniz.

Kaynak dosyalarını bilgisayarınıza indirmeden tarayıcı üzerinde çalıştırmak için buradaki bağlantıyı kullanabilirsiniz.

Written by

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store