Algoritma Bressenham


Setelah mengerjakan tugas ke 2 mata kuliah Grafika, aku mempelajari sebuah algoritma untuk menggambar garis ke layar monitor, yaitu Algoritma Bressenham. Bressenham sendiri merupakan seorang ahli komputer yang dulu pernah menjadi pionirnya IBM.

Algoritma ini merupakan optimasi dari algoritma penggambaran garis yang konvensional. Algoritma Bressenham mereduksi bahkan mengeliminasi operasi perkalian, pembagian, dan operasi pembulatan yang dilakukan pada algoritma konvensial. Dalam dunia komputasi dengan komputer, operasi-operasi tersebut memiliki harga yang ‘mahal’ (kompleksitas yang tinggi). Ide dari algoritma Bressenham ini cukup simple namun sangat powerful, yaitu memilih titik koordinat pixel tetangga yang akan digambar berikutnya secara iteratif dan berhenti di titik/pixel tujuan. Pixel tetangga yang dipilih dapat secara axial (horizontal dan vertikal) ataupun secara diagonal.

Pada algoritma Bressenham, diantara dari operasi-operasi yang ‘mahal’, hanya operasi pembagian yang dilakukan. Itu pun cuma 1 kali dilakukan, yaitu perhitungan galat/error. Nilai galat tersebut digunakan untuk menentukan pilihan koordinat pixel tetangga apakah secara axial atau diagonal. Jika galat < 5, pixel tetangga dipilih secara axial, sedangkan jika galat >= 5, pixel tetangga dipilih secara diagonal.

Kekuatan algoritma Bressenham bukan hanya ‘murahnya’ proses komputasi, tetapi juga menggambarkan sebuah garis lurus yang bersifat kontinyu ‘tampak terlihat lurus’ pada layar monitor yang diskrit. Berikut ini kode program algoritma konvensial dengan algoritma bressenham dalam bentuk prosedur bahasa C. Silakan diliat-liat perbedaannya. :>

Kode program algoritma konvensional

void plot_lines(int x1, int x2, int y1, int y2, byte color){
/* Prosedur untuk menggambar garis yang melalui 2 buah titik yaitu (x1,y1) dan (x2,y2) , kecepatan rendah (pendekatan konvensional) */
/* I.S. : sembarang */
/* F.S. : pixel(xi,yj) dengan i=x1 sampai i=x2 dan j=y1 sampai j=y2 berwarna 'color' sehingga seolah-olah membentuk sebuah garis */
	int y,xi,x,yi,dy,dx;
	dy = y2-y1;
	dx = x2-x1;

	if(abs(dx) >= abs(dy)){/* jika garis cenderung horizontal*/
		if((x2-x1)>=0){
			for(xi=x1;xi=x2;xi--){
				y = ((xi - x1)*(y2-y1)/(x2-x1)) + y1;
				y = abs(y);
				plot_pixel(xi,y,color);

			}
		}
	}
	else{/* jika garis cenderung vertikal */
		if((y2-y1)>=0){
			for(yi=y1;yi=y2;yi--){
				x = ((yi - y1)*(x2-x1)/(y2-y1)) + x1;
				x = abs(x);
				plot_pixel(x,yi,color);
			}
		}
	}
}

Kode program algoritma bressenham

void plot_lines_bresenham(int x1, int y1, int x2, int y2, byte warna){
int dx,dy,dx_abs,dy_abs;
float derror,error;
int x, y;
int sign = 0;
dy = y2 – y1;
dx = x2 – x1;
error = 0.0;
if(abs(dx) >= abs(dy)){/* jika garis cenderung horizontal*/
dx_abs = abs(dx);

if(dx_abs!=0){
derror = (float)dy/(float)dx_abs;/* error */
y = y1;
if(dy>0){/* jika y2 > y1*/
sign= 1;
}
else if(dy<0){ /*jika y2=0){ for(x = x1; x= 0.5 || error=x2; x--){ plot_pixel(x,y,warna); error = error + derror; if(error>= 0.5 || error0){

sign= 1;
}
else if(dx=0){
for(y = y1; y= 0.5 || error=y2; y–){
plot_pixel(x,y,warna);
error = error + derror;
if(error>= 0.5 || error<=-0.5){ x = x + sign * 1; error = error - sign* 1.0; } } } } else{ plot_pixel(x1,y1,warna); } } } [/sourcecode]

3 thoughts on “Algoritma Bressenham

  1. far, kalo nulis source code di wordpress lebih baik pake cara ini ini. Soalnya kalau kayak di atas, susah kebacanya.

    Sebenarnya error sama derror di algoritma itu ga perlu pake tipe float, bisa diakali pake integer juga. Nah, terus ngitung derrornya juga ga pake operasi pembagian floating point yg cukup mahal.. Di net ada kok contohnya.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s