MAKALAH
“Algoritma
Pembuatan Garis
(DDA dan Bressenham)”
Disusun Oleh:
Muhammad
Miftakhur Rozak
(120911013)
PROGRAM
STUDI TEKNIK INFORMATIKA
SEKOLAH
TINGGI TEKNIK QOMARUDDIN
GRESIK
2012
KATA PENGANTAR
Segala puji syukur kehadirat Allah SWT yang telah
memberikan rahmat dan karunia-NYA, sehingga penulis dapat menyelesaikan makalah
ini. Makalah ini penulis beri judul ”Algoritma
Pembuatan Garis (DDA dan Bresenham)”.
Penulis menyadari bahwa dalam proses penulisan makalah
ini, tidak terlepas dari bantuan banyak pihak, sehingga kami dapat
menyelesaikan makalah ini. Pada kesempatan ini kami mengucapkan terima kasih
kepada:
1.
Dosen
pengampu mata kuliah Desain Grafis.
2. Ibu
dan ayah tercinta untuk setiap tetesan keringat dan curahan perhatian dan
pengorbanan serta lantunan doa yang teruntai dalam setiap sholat yang telah mengukir cita dan cinta dihatiku.
3. Para sahabatku atas dukungan, bantuan dan kebersamaannya selama ini, sehingga penulis
dapat merasakan indahnya arti sebuah persahabatan.
4.
Semua
pihak yang tidak dapat disebutkan satu persatu yang telah membantu dalam
penyusunan makalah ini.
Terima kasih atas bantuan yang diberikan kepada penulis,
semoga mendapatkan balasan dari Allah SWT sebagai amalan yang diperhitungkan
dan mendapat imbalan yang jauh berharga.
Di dalam penyusunan Makalah
ini, penulis menyadari dengan sepenuh hati akan kurang sempurnanya Makalah ini,
mengingat tingkat kemampuan serta pengalaman penulis belum luas. Namun demikian, penulis akan berusaha keras
untuk menyusun Makalah ini sehingga dapat terselesaikan dengan baik. Oleh sebab
itu, penulis mengharapkan saran dan kritik dari pembaca. Terimakasih.
Wassalamu’alaikum Wr. Wb
Lamongan, 01 November 2012
Penulis
DAFTAR ISI
HALAMAN
JUDUL......................................................................................................... i
KATA
PENGANTAR........................................................................................................ ii
DAFTAR
ISI................................................................................................................. iii
BAB
I
PENDAHULUAN
1.1 Latar Belakang.................................................................................................... 1
1.2 Rumusan Masalah............................................................................................... 1
BAB
II PEMBAHASAN
2.1. Algoritma
DDA (Digital Defferential Analyzer)................................................. 2
2.2.1. Langkah-langkah Algoritma DDA............................................................. 2
2.2.2. Bahasa Pascal Prosedur DDA.................................................................. 3
2.2. Algoritma Bressenham.......................................................................................... 4
2.2.1.
Langkah-langkah Algoritma Bressenham................................................... 5
2.2.2. Sub
Rutim Bressenham............................................................................. 6
BAB III PENUTUP
3.1. Kesimpulan......................................................................................................... 9
DAFTAR
PUSTAKA.................................................................................................... 10
BAB I
PENDAHULUAN
1.1 Latar Belakang
Garis
merupakan kumpulan dari titik-titik, untuk membentuk garis lurus adalah dengan
mengetahui titik awal dan titik akhir. Dengan mengetahui titik awal dan titik
akhir maka kita dapat membentuk garis. Untuk menggambarkan proses pembuatan
garis dari titik awal ke titik akhir ada berbagai algoritma. Algoritma yang umum
adalah DDA dan Bressenham.
Perkembangan
kemampuan komputasi prosesor yang pesat telah membuat komputer desktop
mempunyai kemampuan komputasi yang besar. Hal ini mendorong perkembangan
program aplikasi yang memerlukan komputasi yang besar seperti program aplikasi
yang menggunakan grafik 3 dimensi. Peningkatan kemampuan komputasi prosesor
untuk aplikasi grafik yang sarat komputasi, perlu dibarengi peningkatan efisiensi
algoritma, sehingga pembuatan grafik garis dan kurva yang merupakan dasar
pembuatan grafik dapat memberikan hasil yang optimal.
1.2 Rumusan Masalah
Berdasarkan
latar belakang yang diuraikan di muka maka dapat dikemukakan dua rumusan
masalah penelitian:
1. Apakah
Algoritma DDA itu?
2. Apakah
Algoritma Bressenham itu?
BAB II
PEMBAHASAN
2.1 Algoritma DDA (Digital
Defferential Analyzer)
Algoritma DDA bekerja bekerja atas dasar penambahan nilai x dan
nilai y. Pada garis lurus, turunan pertama dari x dan y adalah konstanta.
Sehingga untuk memperoleh suatu tampilan dengan ketelitian tinggi, suatu garis
dapat dibangkitkan dengan menambah nilai x dan y masing-masing sebesar eΔx dan
eΔy, dengan besaran dengan nilai yang sangat kecil. Kondisi ideal ini sukar
dicapai, karenanya pendekatan yang mungkin dilakukan adalah berdasarkan
piksel-piksel yang bisa dialamati/dicapai atau melalui penambahan atau
pengurangan nilai x dan y dengan suatu besaran dan membulatkannya ke nilai
integer terdekat.
2.2.1. Langkah-langkah Algoritma DDA
Langkah-langkah untuk membuat
algoritma DDA adalah sebagai berikut:
1. Tentukan 2 buah titik.
2. Tentukan yang menjadi titik awal (X0,Y0)
dan titik akhir (X1,Y1).
3. Hitung Dx dan Dy. Dx = X1-X0 dan Dy =
Y1 – Y0
4. Bandingkan Abs(Dx) dan Abs(Dy).
Jika Abs(Dx) > Abs(Dy) maka Steps = Abs(Dx)
bila tidak Steps = Abs(Dy)
5. Hitung penambahan koordinat pixel,
yaitu:X_increment = dx/steps, danY_increment = dy/steps.
6. Koordint selanjutnya, yaitu X+X_increment
Y+Y_increment.
7. Posisi pixel ditentukan dengan pembulatan
nilai koordinat tersebut.
8. Ulangi langkah 6 dan 7 untuk posisi selanjutnya sampai X = X1,
Y = Y1
2.2.2. Bahasa Pascal Prosedur DDA
Bahasa
pascal prosedur algoritma DDA dapat di tulis seperti dibawah ini:
Begin
Write(‘Masukkan Nilai X0 : ‘);
Readln(X0);
Write(‘Masukkan Nilai Y0 : ‘);
Readln(Y0);
Write(‘Masukkan Nilai X1 : ‘);
Readln(X1);
Write(‘Masukkan Nilai Y1 : ‘);
Readln(Y1);
Dx:=
X1-X0;
Dy:=
Y1-Y0;
If Abs(Dx) > Abs(Dy) Then
Steps:= Abs(Dx)
Else
Steps:= Abs(Dy);
Endif
PutPixel(x,y,Hitam);
For
x = 1 to Steps Do
X
:= X + Xincrement;
Y
:= Y + Yincrement;
PutPixel(x,y,Hitam);
End;
End;
Contoh:
Diketahui
2 buah titik A(10,10) dan titik B(17,16), bila titik A sebagai titik awal dan
titik B sebagai titik akhir maka buatlah garis yang menghubungkan titik
tersebut dengan menggunakan algoritma DDA.
Jawab:
Titik Awal = A(10,10)
Titik Akhir = B(17,16)
Dx = (X1-X0) (17-10) = 7
Dy = (Y1-Y0) (16-10) = 6
Abs(Dx) = Abs(7) = 7
Abs(Dy) = Abs(6) = 6
Abs(Dx) > Abs(Dy) maka
Steps= Abs(Dx) = 7
Xincrement = Dx / Steps. 7 / 7 = 1
Yincrement = Dy / Steps. 6 / 7 = 0,86
Tabel 2.1.
Nilai perhitungan
K
|
X
|
Y
|
Xinc
|
Yinc
|
-
|
-
|
-
|
10
|
10
|
0
|
11
|
10,86
|
11
|
11
|
1
|
12
|
11,71
|
12
|
12
|
2
|
13
|
12,57
|
13
|
13
|
3
|
14
|
13,43
|
14
|
14
|
4
|
15
|
14,28
|
15
|
15
|
5
|
16
|
15,14
|
16
|
16
|
6
|
17
|
16
|
17
|
16\
|
2.2 Algoritma Bressenham
Tujuan
dari algoritma Bressenham ini adalah untuk menghindari pembulatan nilai
seperti pada algoritma DDA. Pada algoritma bressenham, 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.
2.2.1. Langkah-langkah Algoritma Bressenham
a. Langkah-langkah Algoritma Bressenham
(Dx>Dy)
1. Tentukan
2 titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan
salah satu titik disebelah kiri sebagai titik awal, yaitu (X0, Y0) dan titik
lainnya sebagai titik akhir (X1, Y1).
3. Hitung
Dx=x2-x1, Dy=y2-y1, d1=2*DX dan d2=2*Dy - 2*Dx, e=d1-dx, x=x1, y=y1
4. Gambar
pixel di (x,y)
5. Untuk
setiap e>=0 hitung e=e+d2 dan y=y+1 Jika tidak hitung e=e+d1 dan y=y
6. Hitung
x=x+1
7. Jika
x>=x2 stop, jika tidak kembali ke langkah 4
b. Langkah-langkah Algoritma Bressenham
(Dx<Dy)
1. Tentukan
2 titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan
salah satu titik disebelah kiri sebagai titik awal, yaitu (X0, Y0) dan titik
lainnya sebagai titik akhir (X1, Y1)
3. Hitung
Dx=x2-x1, Dy=y2-y1, d1=2*Dy dan d2=2*Dy - 2*Dx, e=d1-dy, x=x1, y=y1
4. Gambar
pixel di (x,y)
5. Untuk
setiap e>=0 hitung e=e+d2 dan x=x+1 Jika tidak hitung e=e+d1 dan x=x
6. Hitung
y=y+1. Jika y>=y2 stop, jika tidak kembali ke langkah 4
2.2.2. Sub Rutim Bressenham
Sub
Rutim Bressenham dalam CVoid line (int xa, ya, xb, yb, xEnd; flot x,y)
{
Int
dx = abs(xb-xa), dy=abs(yb-ya);
Int
p = 2*dy-dx;
Int
twoDy = 2*dy,
twodyDx
= 2*(dy-dx);
If
(xa>xb)
{
X
= xb;
Y
= yb;
Xend
= xa;
}
Else
{
X
= xa;
Y
= ya;
xEnd
= xb;
}
SetPixel(x,y);
while(x
{
X++;
If (p<0) P+ = twody;
Else { Y++; P+ = twoDyDx; } SetPixel(x,y); } };
Contoh:
Berdasarkan contoh pada
algoritma DDA buatlah dengan metode bressenham:
Jawab:
dx
= abs(xb – xa)= abs(17 – 10 ) = 7 dy = abs(yb – ya)= abs(16 – 10) = 6 p = 2 *
dy - dx = 2 * 6 – 7 = 5 twody = 2 * dy = 2 * 6 = 12 twodydx= 2 * (dy – dx ) = 2
* ( 6 – 7 ) = -2 Periksa xa dan xb xa = 10 < xb =" 17Maka">
x
= xa = 10
y
= ya = 10
Xend
= xa = 17
Ulangi
selama x <>
K0:
x = x + 1 = 10 + 1 = 11
Periksa
nilai p , dimana p = 5
y
= y + 1 = 10 + 1 = 11
p
= p + twodydx = 5 + (-2) = 3
K1:
x = x + 1 = 11 + 1 = 12
Periksa
nilai p, dimana p = 3
y
= y +1 = 11 + 1 = 12
p
= p + twodydx = 3 + (-2) = 1
K2:
x = x + 1 = 12 + 1 = 13
Periksa
nilai p, dimana p = 1
y
= y +1 = 12 + 1 = 13
p
= p + twodydx = 1 + (-2) = -1
K3:
x = x + 1 = 13 + 1 = 14
Periksa
nilai p, dimana p = -1 Nilai y tetap yaitu y=13
p
= p + twody = (-1) + 12 = 11
K4:
x = x + 1 = 14 + 1 = 15
Periksa
nilai p, dimana p = 11
y
= y +1 = 13 + 1 = 14
p
= p + twodydx = 11 + (-2) = 9
K5:
x = x + 1 = 15 + 1 = 16
Periksa
nilai p, dimana p = 9
y
= y +1 = 14 + 1 = 15
p
= p + twodydx = 9 + (-2) = 7
K6:
x = x + 1 = 16 + 1 = 17
Periksa
nilai p, dimana p = 7 y = y +1 = 15 + 1 = 16
p
= p + twodydx = 7 + (-2) = 5
Proses
berhenti karena x = x1 dan y = y1
Masukkan
nilai kedalam tabel seperti pada tabel 2.2.
Tabel
2.2.
Hasil penelusuran dengan bressenham
K
|
Pk
|
(Xk+1, Yk+1)
|
-
|
-
|
10,10
|
0
|
3
|
11,11
|
1
|
1
|
12,12
|
2
|
-1
|
13,13
|
3
|
11
|
14,13
|
4
|
9
|
15,14
|
5
|
7
|
16,15
|
6
|
5
|
17,16
|
BAB III
PENUTUP
3.1 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 DDA bekerja bekerja atas dasar
penambahan nilai x dan nilai y. Pada garis lurus, turunan pertama dari x dan y
adalah konstanta. Sehingga untuk memperoleh suatu tampilan dengan ketelitian
tinggi, suatu garis dapat dibangkitkan dengan menambah nilai x dan y
masing-masing sebesar eΔx dan eΔy, dengan besaran dengan nilai yang sangat
kecil. Sedangkan Tujuan dari algoritma Bressenham
ini adalah untuk menghindari pembulatan nilai seperti pada algoritma DDA.
Pada algoritma bressenham, nilai y kedua dan seterusnya, dihitung dari nilai y
sebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara
lengkap.
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 DDAdan algoritma yang lebih cepat, baik pada pembuatan garis lurus
maupun lingkaran dibandingan waktu komputasi dengan algoritma yang menggunakan
dasar operasi bilangan riel.
DAFTAR PUSTAKA
