ALGORITMA DDA, BRESENHAM, DAN MID-POINT GARIS
1. Algoritma DDA atau Digital Differensial Analyzer
algoritma pembentukan garis berdasarkan perhitungan dx maupun dy, menggunakan rumus dy = m . dx. Garis dibuat menggunakan dua endpoint, yaitu titik awal dan titik akhir. Setiap koordinat titik yang membentuk garis diperoleh dari perhitungan, kemudian dikonversikan menjadi nilai integer.Langkah-langkah membentuk garis menurut algoritma DDA adalah :
- Tentukan dua titik yang akan dihubungkan dalam pembentukan garis
- Tentukan titik awal yaitu dan titik akhir .
- Hitung dx = x1- x0 dan dy = y1 – y0
- Tentukan step = max( |dx| , |dy| )
- Hitung penambahan koordinat pixel XInc = dx / step dan YInc = dy / step
- Koordinat selanjutnya (x+XInc, y+yInc)
- Posisi pada layar ditentukan dengan pembulatan nilai koordinat tersebut
- Ulangi nomor 6 dan 7 untuk menentukan posisi pixel berikutnya. sampai x=x1dan y=y1.
void DDA(float x1,float y1,float x2,float y2)
{
float x,y,dx,dy,step;
dx=abs(x2-x1);//absolute
dy=abs(y2-y1);
if(dx>=dy)
step=dx;
else
step=dy;
dx=dx/step;
dy=dy/step;
x=x1;
y=y1;
int i=1;
while(i<=step)
{
putpixel(x,y,5); //pembulatan nilai x dan y
x=x+dx;
y=y+dy;
i=i+1;
delay(100);
}
}
|
BACA JUGA : ALGORITMA MID-POINT ELIPS
2. Algoritma Bresenham
Untuk menggambarkan piksel-piksel dalam garis lurus, parameter yang digunakan tergantung dari gradient, jika besarnya gradient diantara 0 dan 1, maka digunakan sumbu x sebagai parameter dan sumbu y sebagai hasil dari fungsi, sebaliknya, bila gradient melebihi 1, maka sumbu y digunakan sebagai parameter dan sumbu x sebagai hasil dari fungsi, hal ini bertujuan untuk menghindari terjadinya gaps karena adanya piksel yang terlewatkan. Hasil dari fungsi biasanya merupakan bilangan real, sedangkan koordinat pixel dinyatakan dalam bilangan integer (x,y), maka diperlukan operasi pembulatan kedalam bentuk integer terdekat. Penggambaran garis lurus dengan metode diatas dimulai dengan operasibilangan real untuk menghitung gradient m dan konstanta c.Cara kerja dari algoritma ini adalah memeriksa garis yang telah diubah hanya dengan menggunakan perhitungan integer yang terus bertambah yang bisa diadaptasikan untuk menampilkan lingkaran dan bentuk kurva yang lain.
Inti dari Algoritma Bresenham hanya menentukan apakah langkah selanjutnya (xk+1,yk) atau (xk+1,yk+1).
Hal itu ditentukan oleh nilai Pk yang diperoleh dari Pk = 2∆y-∆x
Jika Pk < 0, maka langkah selanjutnya adalah (xk+1,yk), dan Pk+1 = Pk+ 2∆y,
Jika tidak, maka langkah selanjutnya adalah (xk+1,yk+1), dan Pk+1 = Pk+ 2∆y- 2∆x.
Langkah-langkah membuat garis menggunakan algoritma bresenham adalah :
- Input dua titik, dan simpan titik yang paling kiri sebagai (x0,y0)
- Plotkan titik pertama tersebut
- Hitunglah ∆x, ∆y, 2∆y dan 2∆y-2∆x serta perolehlah nilai awal parameter keputusan sbb: p0 = 2∆y-∆x
- Setiap xk sepanjang garis, mulai dari k = 0, lakukan pengujian sbb:
- Apabila pk < 0, maka titik berikutnya yang akan diplot adalah(xk+1,yk), kemudian : pk+1 = pk+ 2∆y
- Apabila Sebaliknya,maka titik berikutnya bernilai (xk+1,yk+1), lalu perhitungannya: pk+1 = pk+ 2∆y- 2∆x
- Ulangi langkah 4 sebanyak ∆x kali.
void bresenham(int x1, int y1, int x2, int y2)
{
float x,y,dx,dy,step;
int m_new = 2 * (y2 - y1);
int slope_error_new = 0.5;
for (int x = x1, y = y1; x <= x2; x++)
{
putpixel(x,y,5);
// Add slope to increment angle formed
slope_error_new += m_new;
// Slope error reached limit, time to
// increment y and update slope error.
if (slope_error_new >= 0)
{
y++;
slope_error_new -= 2 * (x2 - x1);
}
}
}
|
Sangat terlihat bahwa perbedaan algoritma DDA dan Bresenham ada di penentuan pixel selanjutnya, dan juga penggunaan bilangan real dan integer, pada DDA, dia menggunakan bilangan real, dan perlu pembulatan pada eksekusi ke pixelnya, pada bresenham, sudah menggunakan nilai integer yang sudah siap untuk eksekusikan ke dalam bentuk pixel, jadi secara teori, algoritma Bresenham akan lebih cepat dibanding algoritma DDA karena sudah menggunakan integer yang lebih cepat eksekusinya.
Comments
Post a Comment