Grafika Komputer "Contoh Soal Algoritma Bressenham"

Algoritma Bressenham

1. Tentukan 2 titik yang akan dihubungkan dalam pembentuk 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, Dy, 2DX dan 2Dy-2Dy
4. Hitung parameter P₀= 2Dy – 2Dx
5. Untuk setiap X1 sepanjang jalur garis, dimulai dengan k=0,

-          bila pk<0, makatitik selanjutnya adalah (X_k + 1, Y_k) dan P_k+1 = P_k +2D_y

-          bila tidak, maka titik selanjutnya adalah (X_k + 1, Y_k +1) dan P_k+1 = P_k +2D_y – 2Dx

6. Ulangi langkah no. 5 untuk menentukan posisi selanjutnya, sampai X=X1 dan Y=Y1

Contoh soal:

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 Bressenham

Jawab:

Periksa Xa dan Xb

Xa = 10 < Xb=17

Maka, X = Xa = 10

            Y=Ya = 10

Xend = xa= 17

Ulangi selama x < xend

* 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

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

MataKuliah Grafika Komputer "Algoritma Bresenham"

Untuk menentukan jumlah pixel yang membuat suatu garis menggunakan algoritma bresenham 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). Untuk mempermudah buatlah table seperti di bawah ini :

tabel :

Agar lebih mudah melihat hasil dari perhitungan diatas, mari kita lihat Gambar dibawah ini :