2.3.2 Algoritma DDA (Digital Diferential Analyzer ) DDA adalah algoritma pembentuk garis yang didasarkan pada perasamaan (2-8). Garis dibuat menggunakan titik awal (x1, y1) dan titik akhir (x2, y2). Setiap koordinat titik (xk, yk) yang membentuk garis diperoleh dari perhitungan, kemudian hasil perhitungan dikonversikan menjadi nilai integer. Algoritma ini bisa digunakan untuk menghitung garis dengan semua kemiringan. { 0 < m < 1 ; m>1 ; −1 < m < 0 ; m < −1 }. Berikut adalah langkah-langkah pembentukan garis berdasarkan algoritma DDA: =================================================================== 1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis. 2. Tentukan salah satunya sebagai titik awal (x1, y1) dan yang lain sebagai titik akhir (x2, y2). 3. Hitung : dx = x2 − x1 dan dy = y2 − y1 4. Tentukan step, dengan ketentuan berikut: - bila |dx| > |dy| maka step = |dx| - bila tidak, maka step = |dy| 5. Hitung penambahan koordinat piksel dengan persamaan: x_inc = dx / step y_inc = dy / step 6. Koordinat selanjutnya : x = x + x_inc y = y + y_inc 7. Lakukan pembulatan u = Round(x), v = Round(x), kemudian plot piksel (u, v) pada layar 8. Ulangi point 6 dan 7 untuk menentukan posisi piksel berikutnya sampai x = x2 dan y = y2.
Contoh 2.4 Diketahui 2 buah titik A(2,1) dan titik B(8,5) 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 (x1, y1) = A(2,1)
dan
Titik akhir (x2, y2) = B(8,5)
dx = x2 − x1 = 8 −2 = 6 dan dy = y2 − y1 = 5 − 1 = 4 Karena: |dx| > |dy|, maka step = |dx| = 6 x_inc = dx / step = 6/6 = 1 y_inc = dy / step = 4/6 = 0,67 ================================================= Iterasi ke-1: (x,y) = (2,1) x+x_inc = 2 + 1 = 3 y+y_inc = 1 + 0,67 = 1,67 Koordinat selanjutnya : (x,y) = (3; 1,67) Pembulatan (3; 1,67) ≈ (3,2). Gambar titik (3,2) dilayar =================================================
Iterasi ke-2: (x,y) = (3; 1,67) x+x_inc = 3 + 1 = 4 y+y_inc = 1,67 + 0,67 = 2,34 Koordinat selanjutnya : (x,y) = (4; 2,34) Pembulatan (4; 2,34) ≈ (4,2). Gambar titik (4,2) dilayar ================================================= Iterasi ke-3: (x,y) = (4; 2,34) xA+x_inc = 4 + 1 = 5 yA+y_inc = 2,34 + 0,67= 3,01 Koordinat selanjutnya : (x,y) = (5; 3,01) Pembulatan (5; 3,01) ≈ (5,3). Gambar titik (5,3) dilayar ================================================= Iterasi ke-4: (x,y) = (5; 3,01) xA+x_inc = 5 + 1 = 6 yA+y_inc = 3,01 + 0,67 = 3,68 Koordinat selanjutnya : (x,y) = (6; 3,68) Pembulatan (6; 3,68) ≈ (6,4). Gambar titik (6,4) dilayar ================================================= Iterasi ke-5: (x,y) = (6; 3,68) xA+x_inc = 6 + 1 = 7 yA+y_inc = 3,68 + 0,67 = 4,35 Koordinat selanjutnya : (x,y) = (7; 4,35) Pembulatan (7; 4,35) ≈ (7,4). Gambar titik (7,4) dilayar ================================================= Iterasi ke-6: (x,y) = (7; 4,35) xA+x_inc = 7 + 1 = 8 yA+y_inc = 4,35 + 0,67 = 5,02 Koordinat selanjutnya : (x,y) = (8; 5,02) Pembulatan (8; 5,02) ≈ (8,5). Gambar titik (8,5) dilayar Karena x = x2 = 8, maka iterasi dihentikan, sehingga diperoleh titik-titik pembentuk garis sebagai berikut: (2,1), (3,2), (4,2), (5,3), (6,4), (7,4) dan (8,5). ================================================= Bila digambar pada raster graphics diperoleh gambar 2.6: 7 6 5 4 3 2 2 1 1
2
3
4
5
6
7
8
9
10
11
Gambar 2.6: Titik-titik pembentuk garis hasil perhitungan menggunakan algoritma DDA digambar pada raster graphics. Kelebihan Algoritma DDA dibanding Algoritma Brute Force Algoritma DDA lebih cepat dibanding dengan algoritma Brute Force dan baik digunakan untuk kemiringan garis m > 1. Kelemahan Algoritma DDA • Prosedur untuk menggambar garis masih menggunakan fungsi pembulatan x maupun y, sehingga memerlukan waktu. • variabel x, y maupun m memerlukan bilangan real karena kemiringan merupakan nilai pecahan.
2.3.3 Algoritma Bressenham Dengan begini algoritma midpoint Bresenham (untuk kemiringan 0 < m < 1) adalah : 1. 2. 3. 4. 5.
Tentukan dua titik yang akan dihubungkan dalam pembentukan garis. Tentukan salah satu sebagai titik awal (x0, y0) dan titik akhir (x1, y1). Hitung dx, dy, 2|dy| dan 2|dy| − 2|dx| Hitung parameter : po = 2|dy| − |dx| Untuk setiap xk sepanjang jalur garis, dimulai dengan k = 0 - bila pk < 0 maka titik selanjutnya adalah: (xk+1, yk) dan pk+1 = pk + 2|dy| - bila tidak, titik selanjutnya adalah: (xk+1, yk+1) dan pk+1 = pk + 2|dy| – 2|dx| 6. Ulangi nomor 5 untuk menentukan posisi piksel berikutnya, sampai x = x1 dan y = y1.
Contoh 2.5 Diketahui 2 buah titik A(2,1) dan titik B(8,5) bila titik A sebagai titik awal dan titik B sebagai titik akhir, maka buatlah garis yang menghubungkan titik tersebut dengan menggunakan algoritma Bressenham. Jawab: Titik awal (x0, y0) = A(2,1) dan Titik akhir (x1, y1) = B(8,5) dx = x1 − x0 = 8 −2 = 6 dan dy = y1 − y0 = 5 − 1 = 4 m = dy/ dx = 4/6 ; kemiringan garis berada diantara 0 dan 1 : 0 < m < 1 2|dx|= 2.6 = 12 ; 2|dy|= 2.4 = 8
dan 2|dy| – 2|dx| = 8 − 12 = −4
po = 2|dy| − |dx| = 8 − 6 = 2 =================================================
Iterasi ke-1 ( k = 0): Titik awal = (2,1) Po = 2 > 0, maka titik selanjutnya adalah x = 2 + 1 = 3 dan y = 1 + 1 = 2, koordinat selanjutnya : (3,2) p1 = p0 + 2|dy| – 2|dx| = 2 − 4 = −2 ================================================= Iterasi ke-2 ( k = 1): Titik awal = (3,2) P1 = −2 < 0, maka titik selanjutnya adalah x = 3 + 1 = 4 dan y = 2, koordinat selanjutnya : (4,2) p2 = p1 + 2|dy| = −2 + 8 = 6 ================================================= Iterasi ke-3 ( k = 2): Titik awal = (4,2) P2 = 6 > 0, maka titik selanjutnya adalah x = 4 + 1 = 5 dan y = 2 + 1 = 3, koordinat selanjutnya : (5,3) p3 = p2 + 2|dy| – 2|dx| = 6 − 4 = 2 ================================================= Iterasi ke-4 ( k = 3): Titik awal = (5,3) P3 = 2 > 0, maka titik selanjutnya adalah x = 5 + 1 = 6 dan y = 3 + 1 = 4, koordinat selanjutnya : (6,4) p4 = p3 + 2|dy| – 2|dx| = 2 − 4 = −2 ================================================= Iterasi ke-5 ( k = 4): Titik awal = (6,4) P3 = −2 < 0, maka titik selanjutnya adalah x = 6 + 1 = 7 dan y = 4, koordinat selanjutnya : (7,4) p5 = p4 + 2|dy| = −2 + 8 = 6 ================================================= Iterasi ke-6 ( k = 5): Titik awal = (7,4) P5 = 6 > 0, maka titik selanjutnya adalah x = 7 + 1 = 8 dan y = 4 + 1 = 5, koordinat selanjutnya : (8,5) ================================================= Karena x = x2 = 8, maka iterasi dihentikan, sehingga diperoleh titik-titik penyusun garis sebagai berikut: (2,1), (3,2), (4,2), (5,3), (6,4), (7,4) dan (8,5).
Bila digambar pada raster graphics diperoleh Gambar 2.8:
7 6 5 4 3 2 2 1 1
2
3
4
5
6
7
8
9
10
11
Gambar 2.8: Titik-titik pembentuk garis dengan kemiringan 0 < m < 1, hasil perhitungan menggunakan algoritma Bressenham yang digambar pada raster graphics. 2.4
Lingkaran
2.4.1 Simetris Delapan Titik Pembuatan kurva lingkaran dapat dilakukan dengan menentukan titik awal (x,y) yang terletak pada lingkaran, maka tujuh titik yang lain (yang terletak pada lingkaran juga) dapat ditentukan sebagai berikut : (−x,y), (x, −y), (−x, −y), (y,x), (−y,x), (y, −x), (−y, −x) Sehingga terbentuk delapan titik: (x, y), (−x,y), (x, −y), (−x, −y), (y,x), (−y,x), (y, −x), (−y, −x) Dengan demikian sebenarnya hanya diperlukan untuk menghitung segmen 45 menentukan lingkaran selengkapnya.
dalam
2.4.2 Algoritma Midpoint Dari sini diperoleh langkah-langkah algoritma pembentuk lingkaran. • Langkah-langkah Algoritma Lingkaran Midpoint adalah: 1. Tentukan jari-jari r dan pusat lingkaran (xp, yp), kemudian setting sedemikian rupa sehingga titik awal berada pada: (x0, y0) = (0 , r) 2. Hitung nilai parameter : 5 p0 r Jika jari-jari r pecahan 4 p0
1 r
Jika jari-jari r bulat
3. Untuk setiap posisi xk, dimulai dengan k = 0 berlaku ketentuan:
- bila pk < 0 maka titik selanjutnya adalah (xk+1, yk) dan pk+1 = pk + 2 xk+1 + 1 - bila tidak, titik selanjutnya adalah (xk+1, yk – 1) dan pk+1 = pk + 2 xk+1 + 1 – 2 yk+1 4. Tentukan titik simetris pada ketujuh oktan yang lain 5. Gerakkan setiap posisi piksel (x, y) pada garis lingkaran dengan titik pusat (xp, yp) dan plot nilai koordinat : x = x + xp, y = y + yp 6. Ulangi langkah 3 sampai dengan 5 hingga x ≥ y Contoh 2.9 Buatlah gambar kurva lingkaran dengan pusat lingkaran (4,6) dan jari-jari 8, perhitungan berdasarkan dari oktan kuadran pertama dimana x = 0 sampai x = y. Koordinat titik awal dimulai dari (x,r) = (0,8). Karena jari-jari r bulat, maka gunakan P0 = 1 – r. Iterasi ke-1: K=0 X0 = 0 Y0 = r = 8 P0 = 1 – r = 1 – 8 = –7 Karena P0 < 0, maka : X1 = X0 + 1 = 0 + 1 = 1 dan Y1 = Y0 = 8, jadi Titik selanjutnya : (1,8) P1 = p0 + 2 x1 + 1 = –7 + 2.(1) + 1 = – 4 Dengan algoritma simetris delapan titik, maka diperoleh titik-titik berikut : (1,8), (–1,8), (1, –8), (–1, –8), (8,1), (–8,1), (8, –1), (–8, –1) Gerakkan setiap posisi piksel (x, y) pada garis lingkaran dengan titik pusat (4,6) diperoleh titiktitik berikut (5, 14), (3, 14), (5, –2), (3, –2), (12, 7), (–4, 7), (12, 5), (–4, 5) Iterasi ke-2: K=1 X1 = 1 Y1 = 8 P1 = – 4 Karena P1 < 0, maka X2 = X1 + 1 = 1 + 1 = 2 dan Y2 = Y1 = 8, jadi Titik selanjutnya : (2,8) P2 = p1 + 2 x2 + 1 = –4 + 2.(2) + 1 = 1 Dengan algoritma simetris delapan titik, maka diperoleh titik-titik berikut : (2,8), (–2,8), (2, –8), (–2, –8), (8,2), (–8,2), (8, –2), (–8, –2) Gerakkan setiap posisi piksel (x, y) pada garis lingkaran dengan titik pusat (4,6) diperoleh titiktitik berikut (6, 14), (2, 14), (6, –2), (2, –2), (12, 8), (–4, 8), (12, 4), (–4, 4) Iterasi ke-3: K=2 X2 = 2 Y2 = 8 P2 = 1 Karena P2 > 0, maka X3 = X2 + 1 = 2 + 1 = 3 dan Y3 = Y2 – 1 = 8 –1 = 7 , jadi Titik selanjutnya : (3,7) P3 = p2 + 2 x3 + 1 – 2 y3 = 1 + 2.(3) + 1 – 2.(7) = – 6 Dengan algoritma simetris delapan titik, maka diperoleh titik-titik berikut : (3,7), (–3,7), (3, –7), (–3, –7), (7,3), (–7,3), (7, –3), (–7, –3)
Gerakkan setiap posisi piksel (x, y) pada garis lingkaran dengan titik pusat (4,6) diperoleh titiktitik berikut (7, 13), (1, 13), (7, –1), (1, –1), (11, 9), (–3, 9), (11, 3), (–3, 3) Iterasi ke-4: K=3 X3 = 3 Y3 = 7 P3 = – 6 Karena P3 < 0, maka X4 = X3 + 1 = 3 + 1 = 4 dan Y4 = Y3 = 7, jadi Titik selanjutnya : (4,7) P4 = p3 + 2 x4 + 1 = –6 + 2.(4) + 1 = 3 Dengan algoritma simetris delapan titik, maka diperoleh titik-titik berikut : (4,7), (–4,7), (4, –7), (–4, –7), (7,4), (–7,4), (7, –4), (–7, –4) Gerakkan setiap posisi piksel (x, y) pada garis lingkaran dengan titik pusat (4,6) diperoleh titiktitik berikut (8, 13), (0, 13), (8, –1), (0, –1), (11, 10), (–3, 10), (11, 2), (–3, 2) Iterasi ke-5: K=4 X4 = 4 Y4 = 7 P4 = 3 Karena P4 > 0, maka X5 = X4 + 1 = 4 + 1 = 5 dan Y5 = Y4 – 1 = 7 –1 = 6 , jadi Titik selanjutnya : (5,6) P5 = p4 + 2 x4 + 1 – 2 y4 = 3 + 2.(5) + 1 – 2.(6) = 2 Dengan algoritma simetris delapan titik, maka diperoleh titik-titik berikut : (5,6), (–5,6), (5, –6), (–5, –6), (6,5), (–6,5), (6, –5), (–6, –5) Gerakkan setiap posisi piksel (x, y) pada garis lingkaran dengan titik pusat (4,6) diperoleh titiktitik berikut (9, 12), (–1, 12), (9, 0), (–1, 0), (10, 11), (–2, 11), (10, 1), (–2, 1) Iterasi ke-6: K=5 X5 = 5 Karena P5 > 0, maka X6 = X5 + 1 = 5 + 1 = 6
Y5 = 6
P5 = 2
dan Y6 = Y5 – 1 = 6 –1 = 5 ,
jadi Titik selanjutnya : (6,5)
Iterasi dihentikan karena X > Y. Bila digambar, hasil untuk oktan ke-1 ditunjukkan oleh gambar (2.13).
Gambar 2.13: Posisi piksel pada pembentukan lingkaran dengan titik pusat (0,0) dan jari-jari 8
Transformasi Geometri Dari persamaan tersebut, maka masing-masing transformasi diatas bisa dituliskan sebagai berikut :
1 0 tx Matrik penyajian Translasi : T = 0 1 t y , sehingga 0 0 1 x' 1 0 tx y' = 0 1 t y 0 0 1 1
x y 1
Sx Matrik penyajian Scalling : S = 0 0 x' Sx y' = 0 1 0
0 Sy 0
0 0 1
cos Matrik penyajian Rotasi: R = sin 0 x' cos y ' = sin 0 1
sin cos 0
0 Sy 0
0 0 , sehingga 1
x y 1
sin cos 0 0 0 1
0 0 , sehingga 1 x y 1
Contoh 4.7 Tentukan posisi dari segitiga ABC yang dibentuk oleh titik-titik A(10,2), B(10,8) dan C(3,2) jika dilakukan transformasi berikut : a) translasi kearah sumbu x = 4, kearah sumbu y = −2 b) Scalling dengan skala kearah sumbu x = 2, kearah sumbu y = −2 c) Diputar 90o berlawanan jarum jam Jawab:
a)
x' 1 0 y' = 0 1 1 0 0
4 2 1
10 10 3 14 14 7 2 8 2 = 0 6 0 1 1 1 1 1 1
diperoleh A’(14,0), B’(14,6) dan C’(7,0)
b)
x' 2 y' = 0 1 0
0 0 2 0 0 1
10 10 3 20 2 8 2 = 4 1 1 1 1
20 16 1
6 4 1
diperoleh A’(20, −4), B’(20, −16) dan C’(6, −4)
c)
x' cos900 y ' = sin 900 1 0
sin 900 cos900 0
0 0 1
10 10 3 2 8 2 8 2 = 10 10 1 1 1 1 1
2 3 1
diperoleh A’(−2, 10), B’(−8, 10) dan C’(−2, 3)
4.5
Komposisi Matrik Transformasi 2D
Contoh 4.8 Tentukan posisi dari segitiga ABC yang dibentuk oleh titik-titik A(5,5), B(10,5) dan C(8,10) jika dilakukan komposisi transformasi berikut: penggeseran pada
6 , dilanjutkan dengan rotasi 90º 6
berlawanan jarum jam, kemudian diakhiri dengan penskalaan dengan faktor skala titik pusat P(0,0). Jawab: Dalam hal ini kita harus menghitung matrik komposisi berikut
3 terhadap 3
x' y' 1
x S * R *T * y 1
Proses dilakukan terhadap operasi translasi terlebih dahulu
x' y' 1
x' y' 1
3 0 0 0 3 0 0 0 1
33 33 1
33 48 1
cos(90) sin(90) 0
sin(90) 0 cos(90) 0 0 1
1 0 6 0 1 6 0 0 1
5 10 8 5 5 10 0 0 1
48 42 1
Diperoleh titik hasil transformasi : A’(−33, 33), B’(−33, 48) dan C’(−48, 42)
4.8
Transformasi Geometri 3D
Transformasi geometri 3D merupakan pengembangan dari transformasi geometri 2D. Secara umum representasi transformasi pada 3D juga dibuat dalam bentuk matrik untuk memudahkan perhitungan. 4.8.1 Translasi
y (x’, y’, z’) T (Tx, Ty, Tz) x (x, y, z) z
x ' x Tx
Dalam hal ini, y '
y Ty .
Dalam bentuk matrik
z ' z Tz
x' y' z' 1
1 0 0 0
x' y' z' 1
Sx 0 0 0
0 1 0 0
0 Tx 0 Ty 1 Tz 0 1
x y z 1
4.8.2 Penskalaan (Scalling) y
(x’, y’, z’)
T (Sx, Sy, Sz) x (x, y, z) z
x ' S x .x
Dalam hal ini, y ' S y . y .
Dalam bentuk matrik
z ' S z .z
4.8.3 Rotasi Rotasi terhadap sumbu-z sebesar sudut Ө. y (x’, y’, z’) x (x, y, z) z x' x cos Dalam hal ini, y ' x sin z' z
y sin y cos
0 Sy 0 0
0 0 Sz 0
0 0 0 1
x y z 1
Dalam bentuk matrik rotasi terhadap sumbu-z sebesar sudut Ө. x' y' z' 1
cos sin 0 0
sin cos 0 0
0 0 1 0
0 0 0 1
x y z 1
Dengan cara yang sama diperoleh rotasi terhadap sumbu-x sebesar sudut Ө. x' x y ' y cos z ' y sin
z sin z cos
Dalam bentuk matrik rotasi terhadap sumbu-x sebesar sudut Ө. x' y' z' 1
1 0 0 cos 0 sin 0 0
0 sin cos 0
0 0 0 1
x y z 1
rotasi terhadap sumbu-y sebesar sudut Ө.
x' x cos y' y z' x sin
z sin z cos
Dalam bentuk matrik rotasi terhadap sumbu-y sebesar sudut Ө. x' y' z' 1
cos 0 sin 0
0 sin 1 0 0 cos 0 0
0 0 0 1
x y z 1
Viewing Dan Clipping 2D Dalam komputer grafik ada 5 macam sistem koordinat kartesian, yaitu Modeling coordinat/ local coordinat World coordinat Viewing coordinat Normalized device coordinat Device coordinat
Viewing 2D adalah transformasi sistem pandang dari World Coordinates system (sistem koordinat dunia) ke Device Coordinates System. Gambar 5-1 menunjukkan langkah-langkah viewing 2D.
Gambar 5-1: Langkah-langkah viewing 2D.
5.1.2 Viewing Transformation Window merupakan daerah yang dibatasi segi empat pada Viewing Coordinates. Arah pandang Viewing Coordinates tergantung pada arah pandang pengamat. Karena itu untuk melihat bagian obyek yang tertangkap pada window tadi diperlukan transformasi koordinat dari World Coordinates ke Viewing Coordinates yang disebut sebagai Viewing Transformation.
P Window Window
World Coordinates
Viewing Coordinates
Gambar 5-3: Transformasi dari World Coordinates ke Viewing Coordinates Perhatikan titik P dan Po yang bertindak sebagai vektor arah pandang atas pengamat (viewer). Koordinat titik asal window adalah :
Po= (xo, yo)
vektor arah pandang atas pengamat:
v
Gunakan v untuk memperoleh :
u = v × (0, 0, 1)
P
P0
P
P0
transformasi dari World Coordinates ke Viewer Coordinates System adalah
M WC
VC
ux vx 0
uy vy 0
0 1 0 * 0 1 0
0 1 0
x0 y0 1
Sehingga posisi titik terhadap Viewing Coordinates adalah
xv yv 1 Pviewer Pword
M WC
VC
M WC
xw * yw 1 VC
* Pword
(5-1)
= posisi titik terhadap World Coordinates (data posisi titik pembentuk permukaan obyek yang tersimpan di memori)
Pviewer = posisi titik terhadap Viewing Coordinates (posisi titik pembentuk bagian permukaan obyek yang ada di dalam window)
Contoh 5.1 Sebuah segitiga T dibentuk oleh titik-titik (3,1), (4,1) dan (4,2) terletak pada World Coordinates dilihat oleh seorang pengamat dengan arah pandang atas P-Po, dimana Po(2,1) dan P(3.5 , 3).
Arah pandang atas inilah yang dipakai sebagai Viewing Coordinates. Hitunglah koordinatkoordinat segitiga T, terhadap pengamat (Viewing Coordinates). Jawab:
P(3.5 , 3)
v u
Po(2,1)
P
P0
P
P0
vx(0,0,1)
M WC
(3.5,3) (2,1) (3.5,3) (2,1)
M WC
Tv
0.8 0.6 0
1.5 2
(0.6,0.8,0) x(0,0,1)
0.8 0.6 0
VC
Tv
(1.5,2)
VC
0.6 0.8 0
(0.6,0.8)
22
(0.8, 0.6)
0 1 0 * 0 1 0
0 1 0
2 1 1
0.8 0.6 0
0.6 0.8 0
1 2 1
* Tw
0.6 0.8 0
1 3 2 * 1 1 1
4 1 1
4 2 1
0.8 0.6 1
1 1.6 2 1.2 1 1
koordinat-koordinat segitiga T, terhadap pengamat adalah (0.8,0.6), (1,2), (1.6,1.2)
5.1.3 Window to Viewport Transformation Window merupakan daerah yang dibatasi segi empat pada World Coordinates sedangkan Viewport adalah bagian dari layar dimana gambar yang ditangkap oleh window pada World Coordinates ditampilkan di Device Coordinates (dilayar). Jadi window memilih bagian gambar yang akan ditampilkan dilayar, sedangkan viewport menunjukkan dimana posisi bagian gambar tersebut ditampilkan dilayar. Karena itu, untuk memindahkan gambar dari window ke viewport diperlukan Window to Viewport Transformation , yaitu transformasi dari World Coordinates ke Device Coordinates.
.
Window
YWmax
(xw, yw)
●
yw
Viewport
YVmax
Viewport (xv , yv)
●
yv YVmin
YWmin XWmin
xw XWmax
xv XVmax
XVmin
Word Coordinates System
Device Coordinates System
Gambar 5-5: Transformasi dari window ke viewport Teknik ini diperlukan untuk menjaga proporsionalitas ukuran obyek. Gambar 5-5 menunjukkan sebuah titik yang terletak di (xw, yw) pada koordinat window ditransformasi ke (xv,yv) pada koordinat viewport dengan persamaan 5-2:
xw xwmin xwmax xwmin
xv xvmin xvmax xvmin
dan
y w ywmin ywmax ywmin
yv yvmin yvmax yvmin
(5-2)
Pada umumnya ukuran device coordinates berbeda-beda tergantung dari kemampuan Graphics Card. Berikut adalah contoh beberapa ukuran device coordinates
Standart
x-maksimal
y-maksimal
Jumlah keseluruhan Piksel
VGA
640
480
307 200
SVGA
800
600
480 000
XGA
1024
768
786 432
SXGA
1280
1024
1 228 800
Karena alasan inilah maka ada beberapa sistem grafik yang menggunakan Normalized Coordinates, yaitu koordinat di normalisasi kedalam range [ –1, 1] seperti Gambar 5-6.
Window dalam viewing coordinat
Normalized Coordinates
Gambar 5-6: Normalisasi koordinat Sehingga, transformasi dari window ke Normalized Coordinates adalah
xn ( 1) 1 ( 1)
x w xwm in xwm ax xwm in
xn
1
y n ( 1) 1 ( 1)
y w ywm in atau y n ywm ax ywm in
1
atau
2 xwm ax xwm in 2 ywm ax
ywm in
( xw
xwm in )
( yw
ywm in )
Proses berikutnya adalah transformasi dari Normalized Coordinates ke Viewport (Device Coordinates).
xn ( 1) 1 ( 1)
xv xvm in atau xvm ax xvm in
xv
xvmin
( xvmax xvmin ) ( xn 1) 2
y n ( 1) 1 ( 1)
y v yvm in atau yvm ax yvm in
yv
yvmin
( yvmax yvmin ) ( y n 1) 2
Contoh 5.2 Diketahui sebuah titik terletak di (1, 0) pada World Coordinates dilihat melalui sebuah window berukuran (0, −1) – (2, 1). Tentukan posisi titik tersebut pada Device Coordinates, bila titik
tersebut ditempatkan pada viewport berukuran (50, 100) – (600, 400) seperti pada Gambar 5-6, (a) tanpa Normalized Coordinates (b) dengan Normalized Coordinates (c) dengan Normalized Coordinates menggunakan standart VGA 640 × 480
(d) dengan Normalized Coordinates
menggunakan standart SVGA 800 × 600
Gambar 5-6: Sebuah titik terletak di (1,0) pada World Coordinates System Jawab:
xw xwmin xwmax xwmin
(a)
xv xvmin xvmax xvmin
xv 50 600 50
1 0 2 0
y w ywmin ywmax ywmin 0 ( 1) 1 ( 1)
xv = 325
yv yvmin yvmax yvmin
y v 100 400 100
yv = 250
(b) Transformasi dari window ke Normalized Coordinates
xn
1
xn
2 xwm ax xwm in
1
2 2 0
( xw
xwm in )
(1 0) 0
yn
1
yn
1
2 ywm ax
ywm in
( yw
ywm in )
2 [0 ( 1)] 0 1 ( 1)
Transformasi dari Normalized Coordinates ke Device Coordinates (viewport)
xv
xvmin
( xvmax xvmin ) ( xn 1) 2
yv
yvmin
( yvmax yvmin ) ( y n 1) 2
xv
50
(600 50) (0 1) 325 2
(400 100) (0 1) 250 2
yv 100
(c) standart VGA 640 × 480
xv
xvmin
xv
0
( xvmax xvmin ) ( xn 1) 2
(640 0) (0 1) 320 2
yv
yvmin
yv
0
yv
yvmin
yv
0
( yvmax yvmin ) ( y n 1) 2
(480 0) (0 1) 240 2
(d) standart SVGA 800 × 600
xv
xvmin
xv
0
( xvmax xvmin ) ( xn 1) 2
(800 0) (0 1) 400 2
( yvmax yvmin ) ( y n 1) 2
(600 0) (0 1) 300 2
5.2 Clipping 2D
5.2.1 Clipping Titik 6
Sebuah sebuah titik (x,y) terletak didalam window yang diagonal titik-titiknya (xmin,ymin) − (xmax, ymax) jika memenuhi syarat berikut : x min
7
x
x max
y m in
dan
y
y m ax
(5-6)
Contoh 5.3 Diketahui sebuah koordinat window mempunyai diagonal titik (5,7) − (25,20). Diketahui pula titik-titik A(1,5), B(7,10), C(100,15) dan D(8,23), terletak seperti pada Gambar 5-10. Titik-titik yang akan ditampilkan dilayar adalah titik-titik yang berada didalam window, maka titik A(1,5) dan titik D(8,23) harus dilakukan clipping, sedangkan titik B(7,10) dan titik C(10,15) tidak dilakukan clipping.
•D(8,23) Ymax = 20
Window
•C(10,15) •B (7,10) Ymax = 7
•A(1,5) Xmin = 5
Xmax = 25
Gambar 5-10(a): Titik-titik A, B, C, dan D sebelum dilakukan clipping.
Ymax = 20
Window
•C(10,15) •B (7,10) Ymin = 7
Xmin = 5
Xmax = 25
Gambar 5-10(b): Setelah diclipping hanya titik B dan C saja yang ditampilkan di layar. 7.2.1 Clipping Garis B. Algoritma Clipping Garis Cohen-Sutherland Window di bagi-bagi menjadi wilayah-wilayah yang didasarkan pada urutan kode berikut : T
B
T : Top
R
L
B : Bottom
R : Right
L : Left
TL 1001
T 1000
TR 1010
L 0001
Window
R 0010
0000
Titik terletak di dalam window jika jumlah keempat pointcode adalah nol : L+R+T+B=0 Titik terletak di luar window jika jumlah keempat pointcode lebih besar dari nol. L+R+T+B>0 Algoritma Kliping Cohen-Sutherland : 1. Tentukan region code dari setiap ujung garis 2. Jika kedua ujung garis memiliki regioncode 0000, maka garis berada di dalam window clipping. Gambar garis tersebut. 3. Jika salah satu ujung garis terletak di dalam window (garis P1P2), lakukan clipping dengan cara berikut: tentukan titik potong garis dengan tepi window (misalnya titik P), kemudian gambar garis antara ujung garis yang didalam window P1 dengan titik potong P. 4. Jika kedua ujung garis tidak berada didalam window, lakukan operasi logika AND untuk kedua region code o Jika hasilnya tidak 0000, maka buang garis tersebut (invisible) o Jika hasilnya 0000 (garis EF, garis CD dan garis AB), cari titik potong antara garis dengan sisi-sisi window. Cari dua titik potong yang berada di dalam window (E’ dan F’ atau C’ dan D’), kemudian gambar garis antara kedua titik potong tersebut. 5. Ulangi langkah 2 untuk garis yang lain. Titik potong garis dengan batas window dihitung menggunakan persamaan berikut:
x
x1
( y batas y1 ) dan m
y
y1
m( xbatas
x1 )
Contoh 5.4 Diketahui kedudukan garis-garis pada sebuah window pada gambar 5-13:
(5-7)
Berdasarkan gambar tersebut tentukan : a. Region code dari titik-titik A, B, C, D, E, F, G, H, I, dan J, serta sebutkan berapa kategori yang dapat dibangun berdasakan region code tadi. b. Dengan menggunakan algoritma clipping Cohen-Sutherland, jelaskan bagaimana proses clipping dilakukan terhadap garis CD, EF dan GH. Jawab:
1000 C(5,11)
1001
1010
•
C’
10
B(5,9) E(0,5)
Window
0001 G(0, 3)
0010
A(3,4)
• • • G’• F’ E’ H’
1 0101 A)
I(10,8) D(7,8)
Titik
J(9,2) 0100
A(3,4)
Region code Kategori F(5, Titik−1) 2 H(3, −1) 0000 visible
B(5,9)
0000
visible
C(5,11)
1000
invisible
D(7,8)
0000
visible
E(0,5)
0001
invisible
F(5,-1)
0100
invisible
G(0,3)
0001
invisible
H(3,-1)
0100
invisible
I(10,8)
0010
invisible
J(9,2)
0010
invisible
0110 8
Kategori I :
Garis AB visible, karena region code kedua ujungnya 0000
Kategori II :
Garis I J invisible karena, region code I = 0010 , J = 0010 dan
0 0 1 0 AND 0 0 1 0 = 0 0 1 0 ≠ 0 0 0 0 Kategori III : Garis CD candidates for clipping, karena 1 0 0 0 AND 0 0 0 0 = 0 0 0 0
Garis EF candidates for clipping, karena 0 0 0 1 AND 0 1 0 0 = 0 0 0 0 Garis GH candidates for clipping, karena 0 0 0 1 AND 0 1 0 0 = 0 0 0 0
B) Proses Clipping Clipping garis CD Garis CD melewati titik C (5,11) region code 1000 (atas window) dan tittik D(7,8) region code 0000 (dalam window). Gradien garis CD :
m
y 2 y1 x 2 x1
8 11 7 5
3 2
Titik potong C’ antara garis CD dengan batas atas window ymax = 10 adalah
x x x
( y batas y1 ) m 10 11 5 3/ 2 5,67 x1
Titik potong C’ (5,67 , 10) region code = 0000 Clipp garis CC’ dan gambar garis C’D, karena garis C’D region code kedua ujungnya 0000 Clipping garis EF Garis EF melewati titik E (0, 5) region code 0001 (kiri window) dan titik F(5, −1) region code 0100 (bawah window).
m
Gradien garis EF
y 2 y1 x 2 x1
1 5 5 0
6 5
Titik potong E’ antara garis EF dengan batas kiri window xmin = 2 adalah
y
y1
m( xbatas
y
5
6 (2 0) 5
y
2,6
x1 )
Titik potong E’(2, 2,6) region code = 0000 Titik potong F’ antara garis EF dengan batas bawah window ymin = 1 adalah
x
x1
x
0
x
8 3
( ybatas y1 ) m 1 5 3/ 2 2,67
Titik potong F’ (2,67 , 1) region code = 0000 Clipp garis EE’ dan garis FF’ karena keduanya invisible, kemudian gambar garis E’F’, karena region code kedua ujungnya 0000
Clipping garis GH Garis GH melewati titik G (0, 3) region code 0001 (kiri window) dan H(3, −1) region code 0100 (bawah window)
m
y 2 y1 x 2 x1
1 3 3 0
4 3
Titik potong G’ antara garis GH dengan batas kiri window xmin = 2 adalah
y
y1
m( xbatas
y
3
4 (2 0) 3
y
0,3
x1 )
Titik potong G’(2, 0,3) region code = 0100 ≠ 0000 Titik potong H’ antara garis GH dengan batas bawah window ymin = 1 adalah
x
x1
x
0
( y batas y1 ) m 1 3 4/3
x 1,5 Titik potong H’ (1,5 , 1) region code = 0001 ≠ 0000 karena region code kedua titik potongnya ≠ 0000, maka garis G’H’ invisible. Hasil Clipping
C’
10
B(5,9) Window
D(7,8)
A(3,4)
E’ 1
• • •F’ 2
8
7.2.2 Clipping Polygon : Algoritma Sutherland-Hodgman Algoritma Sutherland-Hodgman melakukan clipping polygon terhadap tiap-tiap sisi window. Input algoritma ini adalah sebuah polygon yang terdiri dari urut-urutan verteks (titik-titik yang membentuk polygon) berikut : v1, v2, v3, .... vn, dan outputnya adalah kumpulan verteks pembentuk polygon yang dihasilkan dari aturan clipping polygon.
