Makalah metode Bresenham


Disusun oleh :

-Rhainy Rahmi 11108636
-Reza Febrian 12108217
-Sri Dewi Ekasari 12108362
-Vicky 11108999
-Vikry Yuansyah 12108003
-Yoan Dwi Utami 12108080



Algoritma Bresenham

1. PENDAHULUAN
Perkembangan kemampuan komputasi prosesor yang pesat telah membuatkomputer desktop mempunyai kemampuan komputasi yang besar. Hal inimendorong perkembangan program aplikasi yang memerlukan komputasi yangbesar seperti program aplikasi yang menggunakan grafik 3 dimensi.Peningkatan kemampuan komputasi prosesor untuk aplikasi grafik yangsarat komputasi, perlu dibarengi peningkatan efisiensi algoritma,sehingga pembuatan grafik garis dan kurva yang merupakan dasar pembuatangrafik dapat memberikan hasil yang optimal.
Algoritma midpoint merupakan algoritma pembuatan garis dan kurva dengan dasar operasi bilangan integer yang menonjolkan ciri kecepatan. Sehingga algoritma ini dapat dipakai sebagai algoritma pembuatan grafik yang menuntut kecepatan sebagai hal yang diutamakan. Pembahasan algoritma Midpoint dilakukan dengan mengasumsikan garis lurus dari kiri ke kanan,dan gadient antara 0 dan 1, sedangkan untuk lingkaran dengan mengasumsikan hanya sebagian lingkaran dengan sudut sebesar 45° , hal ini dilakukan untuk mempermudah penjelasan, sedangkan untuk kondisi yanglain dapat diderivasi dengan cara yang serupa. Untuk mendapatkan kinerja algoritma midpoint, dilakukan uji kecepatan komputasi dengan cara mengimplementasikan kedalam bahasa pemrograman C, dan melakukan perbandingan waktu komputasi dengan algoritma yang menggunakan dasar komputasi bilangan riel, maupun algoritma lain yang telah banyak dikenal seperti algoritma dda dan algoritma bressenham.



Algoritma Bresenham menggunakan aritmatika integer yang tidak memerlukan
perkalian dan pembagian dalam proses perhitungannya didalam seluruh implementasi,
yang mana aritmatika integer ini memiliki kecepatan perhitungan yang lebih tinggi
daripada aritmatika floating point.

ALGORITMA GARIS BRESENHAM
•dikembangkan oleh Bresenham
•berdasarkan selisih antara garis yang diinginkan terhadap setengah ukuran dari pixel yang
sedang digunakan.

Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat piksel yang menggunakan persamaan (1), dengan cara menggantikan operasi bilangan rii perkalian dengan operasi penjumlahan, yang kemudian dikenal dengan Algoritma Bresenham. Pada algoritma bresenham, nilai y kedua dan seterusnya, dihitung dari nilai y sebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara lengkap. Perbaikan algoritma ini ternyata tidak menghasilkan perbaikan yang cukup siginifikan. Perbaikan berikutnya dilakukan dengan cara menghilangkan operasi bilangan riel dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan riel, terutama pada penambahan dan pengurangan.

untuk menentukan jumlah pixel yang membuat suatu garis menggunakan algoritma bresenhem adalah sebagai berikut :
1. Masukan 2 endpoints, simpan endpoints kiri sebagai (x0, y0) dan kanan (x1,y1)
2. Hitung konstanta Δx, Δy, 2Δy, 2Dx,2Δy–2Δx dan nilai awal parameter keputusan
p0= 2Δy –Δx
3. Pada setiap xk di garis, dimulai dari k=0, ujilah :
Jika pk 0 maka plot (xk+1, yk+1) dan pk= pk+ 2Δy -2Δx
4.Ulangi tahap 4 sampai mencapai x,y yang di tuju.
Contoh :
Hitunglah posisi piksel hingga membentuk sebuah garis yang menghubungkan titik (4,1) dan (14,8) !
1. Menentukan endpoints (x0,y0)= (4,1) dan (x1,y1)=(14,8)
2. Hitung kostanta :
Dx = x1-x0 Dx= 14-4=10
Dy= y1-y0 Dy= 8-1=7
2Dx= 2.10=20
2Dy= 2.7=14
2Dy-2Dx= 14-20= -6
pk=p0= 2Dy-Dx pk=p0= 14-10=4
3. jadi nilai keputusan awal= 4, karena pk=4 maka kita gunakan pk>0 maka
plot (xk+1,yk+1) = (4+1,1+1) = (5,2) adalah plot yang terbentuk pada K=0.
dan kita hitung nilai keputusan untuk plot selanjutnya. Dengan rumus
pk= pk+ 2Δy -2Δx pk=4+(-6)=-2 adalah nilai keputusan yang ke 2. karena
pk=-2 kita gunakan rumus pk<0 maka plot (xk+1,yk) = (5+1,2) = (6,2)
plot yang terbentuk pada K=1. Ulangi cara tersebut hingga mencapai end point (x1,y1).

Contoh Source Code Program Bresenham pada C++

#include

#include

#include
#include

using namespace std;

void sumbu(){
glPushMatrix();
glBegin(GL_LINES);
glVertex3f(0, 0, 0.0);
glVertex3f(0, 1, 0.0);
glVertex3f(0, 0, 0.0);
glVertex3f(1, 0, 0.0);
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(1.0, 1.0, 1.0);
glPopMatrix();
glEnd();
glFlush();
}

void Diagonal() {
float a,b,c,d;
cout<<"Masukan X0 : ";cin>>a;
cout<<"Masukan Y0 : ";cin>>b;
cout<<"Masukan X1 : ";cin>>c;
cout<<"Masukan Y1 : ";cin>>d;
glPushMatrix();
glBegin(GL_LINES);
glVertex3f(a+0.5, b+0.5, 0.0);
glVertex3f(c+0.5, d+0.5, 0.0);
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(1.0, 1.0, 1.0);
glPopMatrix();
glEnd();
glFlush();

}
void Horizontal() {

float c,d,y;
cout<<"Masukan XAwal :";cin>>c;
cout<<"Masukan XAkhir :";cin>>d;
cout<<"Masukan Ytetap :";cin>>y;
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(1.0, 1.0, 1.0);
glBegin(GL_LINES);
glVertex3f(c+0.1, y+0.1, 0.0);
glVertex3f(d+0.1, y+0.1, 0.0);
glEnd();
glFlush();
}
void Vertikal() {

float a,b,x;
cout<<"Masukan Yawal : ";cin>>a;
cout<<"Masukan Yakhir : ";cin>>b;
cout<<"Masukan Xtetap : ";cin>>x;
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(1.0, 1.0, 1.0);
glBegin(GL_LINES);
glVertex3f(x+0.5,a+0.5,0.0);
glVertex3f(x+0.5,b+0.5,0.0);
glEnd();
glFlush();
}

void Initialize() {
glClearColor(0.0, 0.0, 0.0, 0.0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0.0, 1.0, 0.0, 1.0, -1.0, 1.0);
}

int main(int iArgc, char** cppArgv) {
menu:
int a;
cout<<"------MENU------\n";
cout<<"1.Garis Vertikal\n";
cout<<"2.Garis Horizontal\n";
cout<<"3.Garis Diagonal\n";
cout<<"4.Exit\n";
cout<<"----------------\n";
cout<<"Masukan pilihan anda:";cin>>a;
cout<<"\n";
glutInit(&iArgc, cppArgv);
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
glutInitWindowSize(500, 500);
glutInitWindowPosition(600, 200);
glutCreateWindow("OPenGL with C++");
Initialize();
while (a<=4){
switch(a){
case 1:
glutDisplayFunc(Vertikal);
glutMainLoop();
return 0;

case 2:
glutDisplayFunc(Horizontal);
glutMainLoop();
return 0;
case 3:
glutDisplayFunc(Diagonal);
glutMainLoop();
return 0;
default:
cout<<"anda salah memasukan";
goto menu;
}}



}

Pada Saat Di Run :

Vertikal





Horizontal





Diagonal





KESIMPULAN
Panjang garis atau banyak piksel dalam garis lurus sangat berpengaruh terhadap perbandingan performance antara sebuah algoritma dengan algoritma yang lain, hal ini disebabkan adanya perbedaan waktu operasi yang berada didalam perulangan sepanjang pembuatan piksel, dan waktu operasi yang berada pada sebelumnya. Panjang jari-jari dalam lingkaran tidak berpengaruh terhadap perbandingan performance antara sebuah algoritma dengan algoritma yang lain, hal ini menunjukkan perbandingan waktu operasi yang berada didalam perulangan sepanjang pembuatan piksel, dan waktu operasi yang berada pada sebelumnya berimbang.
Algoritma dengan dasar operasi bilangan integer memberikan waktu operasi yang lebih cepat dibandingkan dengan algoritma dengan dasar operasi bilangan riel, hal ini ditunjukkan dengan waktu komputasi algoritma DDA, algoritma Bresenham dan algoritma Midpoint yang lebih cepat, baik pada pembuatan garis lurus maupun lingkaran dibandingan waktu komputasi dengan algoritma yang menggunakan dasar operasi bilangan riel. Algoritma midpoint memberikan waktu operasi tercepat diantara algoritma penggambaran garis lurus yang telah menggunakan dasar operasi bilangan integer, seperti algoritma DDA, algoritma Bresenham. Jadi algoritma Midpoint merupakan algoritma yang cocok untuk penggambaran grafik yang menuntut kecepatan sebagai hal yang diutamakan.