Diktat Kuliah Grafika Komputer Fakultas Ilmu Komputer Universitas Indonesia Semester II 1999/2000
Kliping Dua Dimensi Dalam peragaan obyek (atau obyek-obyek) pada windownya maka tidak semua bagian dari obyek tersebut perlu diperagakan akibat keterbatasan ukuran viewport itu sendiri. Jadi akan ada sejumlah primitif grafika yang diperagakan karena sepenuhnya ada dalam window, ada sejumlah lainnya yang tidak perlu diperagakan karena sepenuhnya di luaw window, dan sisanya adalah primitif-primitif yang terpotong oleh window sehingga sebagian berada di dalam window dan sebagian lain di luar. Kita perlu menangani hal yang terakhir tersebut secara khusus karena dalam sejumlah lingkungan grafika hal ini bisa menghasilkan kekacauan peragaan, misalnya: bagian yang seharusnya tdak tampak, muncul di bagian ujung lain pada screen (wrap-around), atau menyebabkan program error karena akses keluar batas memory, atau minimal adalah ketidak-efisienan komputasi akibat komputasi pada data yang ternyata tidak perlu dimunculkan. Selama ini untuk menangani masalah tersebut dapat dilakukan sejumlah metoda sbb. ♦ Metoda penggunaan kanvas bitmap yang diperluas: teknik ini sederhana karena melakukan penggambaran pada suatu bitmap yang amat besar mencakup semua penggambaran primitif, kemudian mengambil bagian yang sesuai (cropping) dengan bagian window dengan operasi transfer blok memori. Masalah teknik ini jelas perlunya memory space yang amat besar. ♦ Melakukan “scissoring” yaitu memodifikasi algoritma penggambaran piksel dengan menambahkan pemeriksaan batas-batas window; piksel baru digambari jika berada dalam batas window. Masalah teknik ini adalah kliping hanya dapat dilakukan pada level operasi piksel demi piksel dan komputasi keseluruhan primitif grafika tetap dilakukan walaupun ternyata hanya sebagaian kecil saja yang perlu ditampilkan. Masalah selanjutnya adalah konsep kliping hanya berlaku di level bawah (peragaan) dan tidak bisa ditarik ke level konseptual (kliping seara umum). ♦ Melakukan usaha analitis untuk menemukan titik-titik perpotongannya lalu mendapatkan potonganpotongan garis untuk diperagakan. Kliping dapat digunakan di level konseptual karena garis dan window dinyatakan dalam besaran-besaran real. Masalahnya, tidak semua primitif grafika dapat dengan mudah dianalisis secara geometris demikian. Pembahasan berikut ini adalah berkaitan dengan sejumlah teknik pemotongan primitif berdasarkan metoda analitis di atas.
Kliping Garis Kita mengharapkan dari suatu garis akan diketahui apakah suatu garis itu sepenuhnya berada dalam window, sepenuhnya diluat window, diperolehnya suatu garis (atau garis-garis) baru hasil kliping dalam batas-batas window. Garis itu sendiri (baik yang sebelum maupun setelah kliping) dinyatakan dalam koordinat titik-titik ujungnya. Secara umum bentuk window adalah suatu poligon. Namun dalam kebanyakan metoda window adalah persegi panjang dengan batas-batasnya sejajar dengan sumbu-sumbu sistem koordinat. Hal ini dibedakan dari window dengan bentuk poligon yang umum karena tingkat kerumitan algoritmisnya berbeda jauh. Lebih lanjut lagi, window dengan poligon konveks jauh lebih sederhana dari window poligon konkaf karena jumlah titik perpotongan suatu garis dengan suatu poligon konveks maksimum hanya dua, sementara dengan poligon konkaf bisa lebih dari dua. Berikut ini akan dibahas algoritma-algoritma dalam bentuknya yang baku. Terdapat banyak varian dari algoritma-algoritma tersebut yang dibuat orang demi mendapatkan peningkatan efisiensinya.
Algoritma Cohen-Sutherland (CS) Algoritma ini terbatas pada window yang berbentuk segi empat dengan sisi-sisinya sejajar sumbu-sumbu koordinat. Ide dasarnya adalah sebagai berikut. Jika window dinyatakan dengan titik-titik ujung kiri bawah (xmin, ymin) dan kanan atas (xmax, ymax) maka ruang dua dimensi penggambaran dibagi ke dalam sembilan ruangan oleh garis-garis perpanjangan tepi window. Jadi ruang yang ditengah adalah window kliping itu sendiri. Titik-titik (x, y) yang berada pada masing-masign ruangan tersebut dapat diberi kode empat bit b1b2b3b4 dengan aturan pemberian kode-kode tersebut adalah sbb. jika y > ymax maka b1 = 1, dan jika y ≤ ymax maka b1 = 0 Author: Suryana Setiawan, MSc
1
Diktat Kuliah Grafika Komputer Fakultas Ilmu Komputer Universitas Indonesia Semester II 1999/2000 jika y < ymin maka b2 = 1, dan jika y ≥ ymin maka b2 = 0 jika x > xmax maka b3 = 1, dan jika x ≤ xmax maka b3 = 0 jika x < xmin maka b4 = 1, dan jika x ≥ xmin maka b4 = 0 Sehingga dapat digambarkan pembagian ruangan dan pengkodeannya adalah sebagai berikut. 1001 0001
0101
1000
1010 ymax
0000
0010 ymin 0110
0100 xmin
xmax
Apakah suatu garis diluar, atau di dalam window, atau memotongnya, dapat diketahui berdasarkan operasi lojik pada kode-kode dari kedua titik ujung garis tersebut. Misalkan garis dinyatakan dengan titik-titik ujung P0 dan P1 dengan pengkodean C0 dan C1. Maka dapat diketahui sbb. ♦ Jika (C0 or C1) != 0000 maka garis berada di luar window ♦ Jika (C0 and C1) == 0000 maka garis berada di dalam window ♦ Yang lainnya berarti memotong garis batas window atau hanya perpanjangannya (dalam hal ini mungkin saja tidak melintasi ruang window). Untuk kasus ketiga tersebut perlu dilakukan pemeriksaan lebih lanjut dengan memotong secara bertahap terhadap garis batas yang dilintasinya. Jika C1 == 0000 maka periksa P0, jika tidak maka P1 yang diperiksa, (misalkan yang diperiksa P0, jika P1 menjadi kebalikannya ) sbb. ♦ Jika (C0 and 1000) != 0000 maka cari perpotongan dengan garis y=ymax ♦ Jika tidak maka jika (C0 and 0100) != 0000 maka cari perpotongan dengan garis y=ymin ♦ Jika tidak maka jika (C0 and 0010) != 0000 maka cari perpotongan dengan garis x=xmax ♦ Jika tidak maka pasti (C0 and 0001) != 0000 dan cari perpotongan dengan garis x=xmin Jika P0’ adalah titik perpotongannya maka selanjutnya ulangi algoritma ini untuk ruas garis P0’Pj. Sampai akhirnya di peroleh potongan garis dengan titik-titik ujung P0* dan P1* yang bisa dipastikan keberadaannya di dalam window atau di luar window. Urutan pemeriksaan bisa diubah dan menghasilkan tahapan pemotongan yang berbeda tetapi hasilnya tetap sama. Contoh pada gambar berikut garis dari A ke B akan mengalami pemotongan menjadi A’B, kemudian menjadiA”B dan kemudian menjadi A”B’ yang berada dalam window. Sementara garis dari C ke D akan mengalami pemotongan menjadi C’D kemudian menjadi C”D yang berada di luar window. A
A’
ymax A”
C B’ C’
C” xmin
ymin B
D
xmax
Penghitungan untuk mencari perpotongan dapat disederhanakan berdasarkan persamaan garis y = y1 + m x x = x1 + 1/m y dengan m = (y2 - y1)/(x2 - x1). Titik perpotongan garis tsb dengan y = yt adalah (x, yt) dengan x = x1 + yt /m. Dan, titik perpotongan dengan x = xt adalah (xt, y) dengan y = y1 + m xt. Author: Suryana Setiawan, MSc
2
Diktat Kuliah Grafika Komputer Fakultas Ilmu Komputer Universitas Indonesia Semester II 1999/2000 Karena adanya pemotongan berulang maka jika koordinat direpresentasikan dengan bilangan integer maka setiap pemotongan menyebabkan pembulatan harga dan selanjutnya bentuk geometrisnya berubah. Untuk menghindari hal ini maka koordinat direpresentasikan dalam bilangan real hingga saat penggambaran potongan garis tsb. Algoritma selengkapnya adalah: Garis void CSClip(double xmin, double ymin, double xmax, double ymax) { int C0 = CSEncode (xmin, ymin, xmax, ymax, x0, y0); int C2 = CSEncode (xmin, ymin, xmax, ymax, x1, y1); if ((C0 ! C1) != 0) return null; if ((C0 & C1) == 0) return this; double m = (y1 - y0)/(x1 - x0); double xa, ya, xb, yb; int t; if (C0 != 0) { xa = x0; ya = y0; xb = x1; yb = y1; } else { xa = x1; ya = y1; xb = x0; yb = y0; t = C1; C1 = C0; C0 = t; } if ((C0 & BT_ATAS) != 0) return (new Garis(xa+ymax/m, ymax, xb, yb)).CSClip(xmin,ymin,xmax,ymax); else if ((C0 & BAT_BAWAH) != 0) return (new Garis(xa+ymin/m, ymin, xb, yb)).CSClip(xmin,ymin,xmax,ymax); else if ((C0 & BT_KANAN) != 0) return (new Garis(xmax, ya+xmax*m, xb, yb)).CSClip(xmin,ymin,xmax,ymax); else return (new Garis(xmax, ya+ymin*m, xb, yb)).CSClip(xmin,ymin,xmax,ymax); }
Algoritma Liang-Barsky (LB) Algoritma ini juga terbatas pada window yang berbentuk segi empat dengan sisi-sisinya sejajar sumbu-sumbu koordinat. Sementara dalam algoritma CS bisa terjadi (worse-case) empat kali iterasi pemotongan garis, algoritma LB berusaha untuk menghitung terlebih dahulu dimana seharusnya terjadi pemotongan pada window, baru kemudian dilakukan (worse-case) dua kali pemotongan. Algoritma ini didasarkan pada persamaan garis parametris sebagai berikut. Suatu garis dari P0 = (x0, y0) ke P1 = (x1, y1) dapat dinyatakan sebagai persamaan parametris P(t) = P0 + t∆P t ∈ [0, 1] serta ∆P = (x1 – x0, y1 – y0) Bagian dari garis yang akan muncul di dalam window kliping adalah titik-titik yang memenuhi ketidak-samaan: xmin ≤ x0 + t ∆x ≤ xmax ymin ≤ y0 + t ∆y ≤ ymax 0≤t≤1 Ketidak samaan di atas bisa dituliskan kembali secara umum menjadi tpk ≤ qk, dengan qk k pk 1 –∆x x0 – xmin 2 xmax – x0 ∆x 3 –∆y y0 – ymin 4 ymax – y0 ∆y Dalam bentuknya ini maka sifat-sifatnya suatu garis terhadap batas k (1=batas kiri, 2=batas kanan, 3=batas bawah, 4=batas atas) dari window dapat diketahui.
Author: Suryana Setiawan, MSc
3
Diktat Kuliah Grafika Komputer Fakultas Ilmu Komputer Universitas Indonesia Semester II 1999/2000 ♦ Jika pk = 0 maka garis tersebut sejajar dengan batas k, kemudian jika didapati qk < 0 maka sepenuhnya garis ada di luar batas k berarti juga berada diluar window; tapi jika didapati qk ≥ 0 maka garis ada di sebelah dalam batas tersebut tapi bisa jadi diluar batas yang lain. ♦ Jika pk < 0 maka garis bergerak “memasuki” batas window ybs dan sebaliknya jika pk > 0 maka garis bergerak “meninggalkan” batas window ybs.
Luar window
“memasuki”
Luar window
“meninggalkan”
Catatan: “memasuki”/”meninggalkan” ini hanya berkaitan dengan batas atau perpanjangan garis batas ybs dan bukannya pada window yang sebenarnya. Titik potong pada window adalah titik-titik dengan t=u1 dan t=u2 dan u1 =max(0, qk/pk, untuk setiap k dimana pk < 0) u2 =min(1, qk/pk, untuk setiap k dimana pk > 0) Catatan: tanda < atau > dari pk menyatakan bahwa pembandingan max untuk u1 dilakukan pada batas-batas di mana garis “memasuki” terhadap batas tsb, dan pembandingan min untuk u2 dilakukan pada batas-batas di mana garis bergerak dari “meninggalkan” terhadap batas tsb. Jika ternyata u1 > u2 maka garis berada di dalam window. Jika u1 < u2 maka titik-titik potong dengan batas-batas window dengan mudah dihitung sebagai P(u1) = (x0 + u1∆x, y0 + u1∆x) dan P(u2) = (x0 + u2∆x, y0 + u2∆x) serta garis perpotongannya dibatasi oleh kedua titik potong tersebut. Berikut ini contoh di mana suatu garis di kedua ujungnya mengalami pemotongan.
“memasuki”, t = q1/p1 = u1 “memasuki”, t = q3/p3
t=1 “meninggalkan”, t = q2/p2 “meninggalkan”, t = q2/p2 = u2
t=0
Berikut ini contoh di mana suatu garis hanya mengalami pemotongan di satu ujungnya.
Author: Suryana Setiawan, MSc
4
Diktat Kuliah Grafika Komputer Fakultas Ilmu Komputer Universitas Indonesia Semester II 1999/2000
t=1 “meninggalkan”, t = q2/p2 “meninggalkan”, t = q2/p2 = u2
“memasuki”, t = q1/p1 = u1 “memasuki”, t = q3/p3 t = 0 = u1
Dan berikut ini contoh di mana suatu garis tidak mengalami pemotongan karena u1 > u2. “memasuki”, t = q1/p1 = u1
t=1 “meninggalkan”, t = q2/p2
t=0
“meninggalkan”, t = q2/p2 = u2
“memasuki”, t = q3/p3
Algoritma selengkapnya adalah: Garis void LBClip(double xmin, double ymin, double xmax, double ymax) { double dx = x1-x0; double dy = y1-y0; ClipPars u = new ClipPars(0, 1); if (!u.clipTest(-dx, x0 - xmin)) return null; if (!u.clipTest(dx, xmax – x0)) return null; if (!u.clipTest(-dy, y0 - ymin)) return null; if (!u.clipTest(dy, ymax – y0)) return null; if (u.u1 == 0.0; u.u2 == 1.0) return this; return new Garis(x0+u.u1*dx, y0+u.u1*dy,x0+u.u2*dx, y0+u.u2*dy); } class ClipPars { double u1, u2; ClipPars(double u1, double u2) { this.u1 = u1; this.u2 = u2; } boolean clipTest(double pk, double qk) { if (pk < 0) { double r = qk/pk; if (r > u2) return false; else if (r > u1) u1 = r; Author: Suryana Setiawan, MSc
5
Diktat Kuliah Grafika Komputer Fakultas Ilmu Komputer Universitas Indonesia Semester II 1999/2000 } else if (pk > 0) { double r = qk/pk; if (r < u1) return false; else if (r < u2) u2 = r; } else if (qk < 0) return false; retun true; } } Dalam kasus dimana garis benar-benar berada di dalam window algoritma ini tetap akan memeriksa (clipTest) terhadap keempat batas windownya sementara pada algoritma CS proses akan segera berhenti setelah penghitungan kedua kode titik ujung (baris keempat). Jadi secara umum jika mayoritas primitif-primitif garis obyek berada dalam window maka algoritma CS lebih baik dari algoritma LB, dan sebaliknya jika mayoritas primitif garis obyek memotong garis batas.
Algoritma Cyrus-Beck (CB) Algoritma LB bisa dikategorikan kasus khusus dari algoritma CB. Algoritma CB ini mencari titik-titik potong terhadap sisi-sisi window degan bentuk yang umum (bisa berbentuk poligon) serta menggunakan perhitungan parametris yang mirip dengan algoritma LB. Titik potong terhadap suatu garis batas window di analisis sebagai berikut. Suatu garis dari titik P0 ke titik P1 yang dinyatakan sebagai suatu fungsi parametris P(t) = P0 + t∆P, dengan ∆P = (P1 – P0) Jika Ek suatu titik di garis batas ke-k dan Nk adalah vektor normal dari garis batas tersebut ke arah luar serta P(t2) adalah titik perpotongan garis pada batas maka perkalian titik antara Nk dengan (P(tx) – Ek) adalah 0. Nk•(P(tx) – Ek) = 0 Substitusi P(tx) dengan persamaan garis menjadi Nk•(P0 + tx∆P – Ek) = 0 Distribusi perkalian titik menghasilkan P Nk•(P0 – Ek) + (Nk•∆P) tx = 0 Sehingga jika ∆P ≠ 0 (yaitu P0 ≠ P1), dan Nk•∆P ≠ 0 (yaitu garis P( ) tidak sejajar garis batas; sudah jelas Nk ≠ 0) diperoleh tx = (Nk•(P0 – Ek))/(–Nk•∆P) P Suatu garis disebut “memasuki” batas window atau perpanjangannya jika vektor Nk dan ∆P berlawanan arah (mengapit sudut > 90o) yang berarti juga (Nk•∆P) < 0, dan sebaliknya “meninggalkan” jika satu arah yang berarti (Nk•∆P) > 0. Dengan formula ini maka pada suatu poligon yang konveks kita dapat mencari u1 dan u2 seperti halnya pada algoritma LB. u1 =max(0, txk, untuk setiap sisi k dimana Nk•∆P < 0) u2 =min(1, txk, untuk setiap sisi k dimana Nk•∆P > 0) Dan, anda bisa membuktikan bahwa formula u1 dan u2 di atas dapat diturunkan menjadi formula yang terdapat pada Algoritma LB. Dalam kasus poligon konkaf perlu suatu persoalannya sedikit lebih rumit karena suatu garis dapat muncul dalam window dalam sejumlah pemotongan. Salah satu ide adalah membagi poligon window yang konkaf menjadi sejumlah poligon konveks lalu melakukan pemotongan di masing-masing poligon konveks tersebut secara terpisah.
Algoritma Nicholl-Lee-Nicholl (NLN) Algoritma ini mengembangkan lagi konsep algoritma CS dengan berusaha mengurangi jumlah titik perpotongan yang dievaluasi. Idenya adalah mengganti pembagian ruang yang dilakukan CS ke pembagian yang mengakibatkan maksimum hanya ada perpotongan pada dua batas window saja. Ruang dibagi berpusatkan di Author: Suryana Setiawan, MSc
6
Diktat Kuliah Grafika Komputer Fakultas Ilmu Komputer Universitas Indonesia Semester II 1999/2000 salah satu titik ujung garis P0P1, biasanya titik P0, dan menarik dari titik ini melintasi setiap titik ujung window. Maka terjadi kasus-kasus sebagai berikut. 1. Jika P0 di dalam window (dalam daerah 0000 dari algoritma CS) 2. Jika P0 di luar window dan di samping salah satu batas (dalam daerah 1000, atau 0100, atau 0010, atau 0001 dari algoritma CS) 3. Jika P0 di luar window dan di samping sudut window (dalam daerah 1010, atau 1001, atau 0110, atau 0101 dari algoritma CS) P0 P0 P0
Dengan pembagian demikian maka dengan memeriksa slope garis P0P1 terhadap slop garis-garis batas pembagian ruang dapat diketahui bahwa garis P0P1 akan berpotongan dengan batas window mana saja. Selanjutnya perhitungan titik potong dilakukan hanya pada garis-garis batas yang sudah diidentifikasi tersebut.
Kliping Poligon Suatu poligon dinyatakan dengan deretan koordinat titik-titik verteksnya. Poligon bisa konveks atau konkaf. Diharapkan dari kliping poligon terhadap suatu window maka akan diperoleh poligon (atau poligon-poligon) baru irisan dari poligon asal dengan window. Window sendiri seperti halnya pada masalah kliping garis yang paling sederhana bisa berbentuk segi empat, atau poligon konveks atau poligon konkaf yaitu yang paling sulit.
Algoritma Sutherland-Hodgeman (SH) Algoritma ini adalah untuk kliping poligon konkaf/konveks terhadap suatu poligon konveks. Idenya adalah melakukan pemotongan terhadap batas demi batas window secara terpisah. Pemotongan terhadap suatu batas (dan perpanjangan batas itu) menghasilkan suatu poligon lain yang akan dipotongkan terhadap batas selanjutnya (dan perpanjangannya). Perhatikan contoh pada gambar berikut ini di mana suatu poligon dipotong terhadap suatu window berbentuk persegi panjang. Pemotongan dilakukan pertama terhadap sisi kiri, kemudian terhadap sisi kanan, bawah, dan terakhir atas.
Pertanyaan selanjutnya adalah bagaimana caranya pemotongan terhadap suatu garis batas? Algoritma ini memiliki aturan-aturan sebagai berikut jika poligon dinyatakan oleh verteks-verteks v1, v2, …, vn. ♦ Sisi demi sisi diperiksa terhadap batas window mulai dari sisi v1v2, v1v3, …, vn-1vn, dan vnv1, untuk mendapatkan verteks-verteks membentuk poligon baru hasil pemotongan tersebut. Pada tahap inisialisasi poligon hasil berisikan 0 verteks. ♦ Bila suatu sisi vivi+1 berpotongan dengan batas window dengan vi berada di luar mengarah dan vi+1 berada di dalam batas window maka dilakukan komputasi untuk mendapatkan titik perpotongannya yaitu vi’, dan verteks-verteks vi’ dan vi+1 dicatat sebagai verteks berikutnya di poligon hasil pemotongan. ♦ Bila suatu sisi vivi+1 berpotongan dengan batas window dengan vi berada di dalam mengarah dan vi+1 berada di luar batas window maka dilakukan komputasi untuk mendapatkan titik perpotongannya yaitu vi’, dan verteks vi’ dicatat sebagai verteks berikutnya di poligon hasil pemotongan. Author: Suryana Setiawan, MSc
7
Diktat Kuliah Grafika Komputer Fakultas Ilmu Komputer Universitas Indonesia Semester II 1999/2000 ♦ Bila suatu sisi vivi+1 tidak berpotongan dengan batas window dan berada di sebelah dalam batas window maka verteks vi+1 dicatat sebagai verteks berikutnya di poligon hasil pemotongan. ♦ Bila suatu sisi vivi+1 tidak berpotongan dengan batas window dan berada di sebelah luar batas window maka tidak ada yang dicatat. Contoh berikut adalah pemotongan poligon terhadap sisi kiri window persegi empat. v1 v1’
v1 v1’ v2
v4
v1 v1’ v2
v4
v1 v1’ v2
v4 v3’
v3 Pada pemeriksaan v1v2 diperoleh v1’, dan v2
v3 Pada pemeriksaan v2v3 diperoleh v3
v2 v4 v3’
v3 Pada pemeriksaan v3v4 diperoleh v3’
v3 Pada pemeriksaan v4v1 tidak ada verteks baru
Poligon yang dihasilkan adalah dengan verteks-verteks v1’v2v3v3’. Masalah yang muncul pada algoritma ini adalah apabila terjadi lebih dari satu kali keluar-masuk window maka akan terbentuk suatu poligon yang sebenarnya adalah beberapa area terpisah tapi dihubungkan oleh garis-garis. Ini mungkin terjadi pada poligon konkaf dan tidak terjadi pada poligon konveks. Perhatikan gambar berikut yang menggambarkan sebelum dan setelah kliping suatu poligon.
Jika diharapkan bahwa untuk kasus ini akan terbentuk bukan hanya satu poligon tetapi sejumlah piligon untuk setiap area maka perlu modifikasi pada algoritma dengan menambahkan pemeriksaan akhir ada tidaknya sisi-sisi poligon yang berimpit dan jika ada melakukan pemotongan pada tempat tersebut.
Author: Suryana Setiawan, MSc
8
