Clipping 2 Dimensi : Cliping Garis

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 potongan-potongan 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.

Clipping 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

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.

 Kode Cohen Sutherland

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.

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.

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.