Clipping (Episode 2 - End) - Clipping Polygon

Annyeonghaseyo!!!! Apa kabar ni??? Wah, udah pada semangat aja ni mau ngelanjutin yang kemaren ya... Ayooo SEMANGAT PAGI!!!

Nah, sekarang berarti saatnya kita kenalan sama yang namanya Clipping Polygon. Sebelum kenal lebih jauh sama yang namanya Clipping Polygon, ada baiknya kalau kita kenalan dulu sama yang namanya Polygon. Polygon adalah gabungan ruas garis dari bagian yang bertemu hanya di titik akhir sehingga sebesar dua ruas garis bertemu di satu titik, dan tiap ruas garis bertemu tepat dua ruas garis lainnya. Polygon sendiri terdiri dari dua aspek berikut, yaitu Vertex(Titik) dan Edge(Garis).

Jika kita melihat contoh gambar di bawah, maka ada bagian dari poligon yang tidak akan ditampilkan pada layar komputer, karena bagian tersebut berada di luar clipping window yang telah tersedia. Untuk mengetahui bagian mana saja yang dapat kita gambarkan pada viewport kita, maka kita dapat menggunakan Algoritma Sutherland-Hodgman Clipping Polygon.

Untuk memulai Algoritma Sutherland-Hodgman Clipping Polygon, kita harus dapat menentukan intersection dari tiap-tiap edge. Intersection sendiri adalah letak titik potong dari setiap edge yang bersinggungan dengan batas maksimum atau batas minimum. Untuk mengetahui intersection dari masing-masing edge, maka kita perlu mengetahui rumusan berikut :

a. Titik potong pada viewport kiri (IX,IY)

b. Titik potong pada viewport kanan (IX,IY)

c. Titik potong pada viewport bawah (IX,IY)

d. Titik potong pada viewport atas (IX,IY)

Pada Algoritma Sutherland-Hodgman Clipping Polygon juga terdapat 4 kondisi yang harus kita perhatikan :

1. Out →In, Vertex baru yang dihasilkan {Vertex perpotongan, Vertex dalam}

2. In → In, Vertex baru yang dihasilkan {Vertex tujuan}

3. In → Out, Vertex baru yang dihasilkan {Vertex perpotongan }

4. Out →Out, Vertex baru yang dihasilkan { }

Berikut ini adalah contoh kasus pemecahan masalah dengan menggunakan Algoritma Sutherland-Hodgman Clipping Polygon.

A. Left Clipper

1. Mencari Titik Potong pada garis AB (3,13)(30,3)(Karena berada pada kondisi out → in, maka akan dihasilkan Vertex baru)

2. Mencari Titik Potong pada garis BC (Karena berada pada kondisi in→ in, maka tidak akan dihasilkan Vertex baru)

3. Mencari Titik Potong pada garis CD (Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

4. Mencari Titik Potong pada garis DE (Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

5. Mencari Titik Potong pada garis EA (12,38)(3,13)(Karena berada pada kondisi in → out, maka akan dihasilkan Vertex baru)

B. Right Clipper

1. Mencari Titik Potong pada garis A’B (Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

2. Mencari Titik Potong pada garis BC (Karena berada pada kondisi in→ in, maka tidak akan dihasilkan Vertex baru)

3. Mencari Titik Potong pada garis CD (Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

4. Mencari Titik Potong pada garis DE (Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

5. Mencari Titik Potong pada garis EE’ (Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

6. Mencari Titik Potong pada garis E’A (Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

C. Bottom Clipper

1. Mencari Titik Potong pada garis A’B (5,12.26)(30,3)(Karena berada pada kondisi in → out, maka akan dihasilkan Vertex baru)

2. Mencari Titik Potong pada garis BC (30,3)(31,40)(Karena berada pada kondisi out→ in, maka akan dihasilkan Vertex baru)

3. Mencari Titik Potong pada garis CD (Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

4. Mencari Titik Potong pada garis DE (Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

5. Mencari Titik Potong pada garis EE’ (Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

6. Mencari Titik Potong pada garis E’A’ (Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

D. Top Clipper

1. Mencari Titik Potong pada garis A’A’’(Karena berada pada kondisi in → in, maka tidak akan dihasilkan Vertex baru)

2. Mencari Titik Potong pada garis A’’B’ (Karena berada pada kondisi in→ in, maka tidak akan dihasilkan Vertex baru)

3. Mencari Titik Potong pada garis B’C (30.05 , 5)(31,40)(Karena berada pada kondisi in → out, maka akan dihasilkan Vertex baru)

4. Mencari Titik Potong pada garis CD(31,40)(20,30)(Karena berada pada kondisi out → in, maka akan dihasilkan Vertex baru)

5. Mencari Titik Potong pada garis DE(20,30)(12,38)(Karena berada pada kondisi in → out, maka akan dihasilkan Vertex baru)

6. Mencari Titik Potong pada garis EE’(12,38)(5,19.1)(Karena berada pada kondisi out → in, maka akan dihasilkan Vertex baru)

Dari proses perhitungan dengan menggunakan Algoritma Sutherland-Hodgman Clipping Polygon. Akan diperoleh Poligon baru yang telah melalui proses Clipping, berikut adalah Vertex-Vertex baru yang akan membentuk Poligon hasil clipping :

· Vertex A’(5,12.26)

· Vertex A’’(24.6,5)

· Vertex B’(30.05,5)

· Vertex B’’(30.8,35)

· Vertex C’(25.5,35)

· Vertex D’(15,35)

· Vertex E’’(10.9,35)

· Vertex E’(5,19.1)

Nah, karena perbincangan kita tentang Clipping telah usai, dan kayaknya udah kenal banget ni sama yang namanya Clipping, itu artinya saatnya bagi kita untuk berpisah...

Eits, tapi jangan bersedih kawan, karena Anis bakal kembali lagi dengan topik-topik yang nggak kalah menarik lainnya. Soalnya kalau dipikir-pikir nge-blog kayak gini bisa jadi salah satu cara belajar yang Efektif. Selain mengulang kita juga bisa nyari referensi yang lain biar gak asal posting...

Moga-moga bermanfaat KAWAN!!!

Annyeong!!!! @_@

Clipping (Episode 1) - Clipping Line

Wah, dah lama banget gak posting di ni blog... Biasanya Anis posting kalau emang lagi ada moodnya, nah sekarang kebetulan lagi ada semangat bwat ngerjain tugas.... Yah itung-itung bagi-bagi ilmu ke orang lain....

Berhubung kemaren pas kuliah Komputer Grafik a.k.a KomGraf, Anis baru aja belajar Clipping, sekarang anis mau ngasihsedikit step-step tentang bagaimana bikin Clipping terhadap Garis (Clipping Line) sama terhadap poligon (Clipping Polygon)...

Oiya sebelum kita melangkah lebih jauh, ada pepatah “Tak Kenal Maka Tak Sayang”, jadi mumpung belum kejauhan kita kenalan dulu sama “Clipping”. Clipping tu sebenarnya apaan si???

Clipping sebenarnya adalah pemotongan suatu objek dengan bentuk tertentu. Ada beberapa alasan kenapa clipping itu dilakukan :

1. Menghindari perhitungan pixel yang rumit
2. Intepolasi parameter

Nah, untuk mempermudah proses clipping ini sendiri maka dibutuhkan “Clipping Window” yang fungsinya adalah untuk mengidentifikasi objek yang akan di-clipping dan menastikan bahwa data yang diambilnya yang terdapat di dalam clipping window. Bentuk dari clipping window itu sendiri bisa bermacam-macam, bisa segitiga, segi empat, lingkaran atau elips, polygon, dll. Tapi pada kesempatan kali ini yang akan Anis pergunakan adalah clipping window berbentuk segi empat.

Kalau tadi kita udah kenalan sama yang namanya Clipping, berarti sekarang saatnya kenalan lebih jauh lagi sama yang namanya Clipping Line sama Clipping Polygon. Tapi biar gak bingung kita kenalannya gantian-gantian aja ya.Berhubung nenek moyangnya dari Clipping Polygon itu Clipping Line, ada baiknya kalau kita kenalan dulu sama Clipping Line dulu ya...

Clipping Line

Clipping Line dapat kita ilustrasi dngan menggunakan gambar berikut :

Terdapat sebuah Clipping Window yang dibatasi oleh garis L, T, R, dan B. Clipping window tersebut dilalui oleh garis dari titik P1 ke titik P2. Namun karena kedua titik tersebut terletak di luar dari clipping window yang telah ditentukan maka garis yang akan ditampilkan hanya garis P1’-P2’, sedangkan garis P1-P1’ dan garis P2’-P2 tidak akan ditampilkan.

Untuk menentukan letak suatu garis itu berada di dalam clipping window atau di luar clipping window maka dilakukan analisis untuk memastikan bahwa keberadaan garis tersebut adalah di dalam clippiing window.

Titik Asli	Titik Semu	Kondisi X	Kondisi Y
P1(x,y)	P1’(x,y)	P1(x)≥L	P1(y)≤T
P2(x,y)	P2’(x,y)	P2(x)≤R	P2(x)≥B

Secara garis besar, garis yang ditampilkan pada clipping line terbagi menjadi 4 kondisi, yaitu :

· Visible : Garis kelihatan seluruhnya, terletak di dalam clipping window

· Invisible : Garis tidak kelihatan sama sekali, terletak di luar clipping window

· Halfpartial : Garis terpotong sebagian oleh clipping window, bisa hanya dengan bagian atas, bawah, kiri, atau kanan.

· Vollpartial : Garis melewati window clipping atau terpotong penuh oleh clipping window.

Nah, dalam proses perhitungan clipping window ini sendiri ada banyak algoritma yang dapat digunakan, yaitu Cohen-Sutherland Line Clipping, Liang-Barsky Line clipping, dan Nicholl-Lee-Nicholl Line Clipping. Tapi pada kesempatan kali ini Anis akan memperkenalkan algoritma Cohen-Sutherland line Clipping dulu saja ya....

Algoritma Cohen-Sutherland Clipping Line

Pada Algoritma ini terdapat bit window yang fungsinya untuk merepresentasikan posisi dari suatu garis terhadap clipping window. Pada bit window tersebut terdapat pointcode yang fungsinya untuk mengidentifikasi posisi tehadap clipping window. Nilai dari pointcode ini adalah 1 dan 0, yang merupakan angka logika yang sama artinya dengan true dan false.

Berikut ini adalah gambaran dari posisi suatu pointcode :

Suatu titik itu visible dengan pointcode jika nilai L,R, T,dan B adalah nol, artinya jika salah satu nilai dari L, R, T, atau B tidak sama dengan nol maka dapat dipastikan bahwa titik tersebut berada di luar clipping window. Cara mudah memahaminya sebenernya cukup dengan mengetahui hal berikut :

1. Jika,pointcode L+R+T+B=0, maka titik terletak di dalam clipping window.
2. Jika,pointcode L+R+T+B>0, maka titik terletak di luar clipping window.

Susunan Region Code adalah seperti tabel berikut :

Bit ke	Region Bit	Isi
1	T	1 apabila y > ymax 0 apabila y ≤ ymax
2	B	1 apabila y <> 0 apabila y ≥ ymin
3	R	1 apabila x > xmax 0 apabila x ≤ xmax
4	L	1 apabila x <> 0 apabila x ≥ xmin

Nah, algoritma dari Cohen-Sutherland Clipping line sendiri adalah seperti berikut :

1. Tentukan regioncode dari setiap endpoint.
2. Jika kedua point code memiliki regioncode 0000, maka garis berada di dalam clipping window. Atau jika bit keduanya di-OR-kan hasilnya= 0 (Trivial Accepted)
3. Jika tidak, lakukan operasi logika AND untuk kedua regioncode

a.Jika hasilnya 0000, maka buang garis tersebut (tolak)

b.Jika hasilnya tidak samadengan 0000, maka dibutuhkan clipping (Trivial Rejected)

·Pilih salah satu endpoint yang berada di luar clipping window

·Cari titik persinggungan pada batas window.

·Ganti endpoint dengan titik persinggungan dan update regioncode

Titik singgung dihitung berdasarkan bit=1 dari region code seperti berikut

Berikut adalah perhitungan x1’, x2’, y1’, dan y2’ dengan menggunakan persamaan ini :

· Ulangi langkah 2 hingga diperoleh garis klipping yang diterima dan yang ditolak

4. Ulangi langkah 2 untuk garis yang lain.

Biar kita nggak bingung lagi, sekarang langsung aja ke contoh kasus berikut ya...

Dari gambar diatas dapat kita ketahui bahwa:

· xmin = 5 · xmax = 25 · ymin = 5 · ymax = 30

· Garis AB (6,4) (28,17) · Garis CD (16,17) (10,25) · Garis EF (19,25) (20,32)

1. Garis AB

1. Menentukan region dari setiap endcode

· Titik A (6,4)

L = 0 → Karena x > xmin yaitu 6> 5

R = 0 → Karena x <>

B = 1 → Karena y > ymin yaitu 4 <>

T = 0 → Karena y <>

Region code yang diperoleh dari titik A adalah 0100

· Titik B (28,17)

L = 0 → Karena x > xmin yaitu 28 > 5

R = 1 → Karena x <> 25

B = 0 → Karena y > ymin yaitu 17 > 5

T = 0 → Karena y <>

Region code yang diperoleh dari titik B adalah 0010

Karena kedua region code dari titik A & B bernilai 0000, dapat kita simpulkan bahwa garis yang terhubung terpotong penuh oleh clipping window (garis melintasi clipping window).

2. Dengan menggunakan operasi logika AND maka diperoleh hasil 0100 AND 0010 = 0000.
3. Titik singgung pada garis AB (6,4) (28,17)

Region code 0100 untuk titik A (6,4), maka B =1 → Karena B = 1, maka yang dicari x1’

Maka titik singgungnya adalah (x1’,ymin) = (7.6, 5)

Region code 0010 untuk titik B (28,17), maka R =1 → Karena R = 1, maka yang dicari y2’

Maka titik singgungnya adalah (xmax, y2’) = (25, 15.2)

2. Garis CD

1. Menentukan region garis dari setiao encode

·Titik C (16,17)

L = 0 → Karena x > xmin yaitu 16 > 5

R = 0 → Karena x <>

B = 0 → Karena y > ymin yaitu 17 > 5

T = 0 → Karena y <>

Region code yang diperoleh dari titik C adalah 0000

·Titik D (10,25)

L = 0 → Karena x > xmin yaitu 10 > 5

R = 0 → Karena x <>

B = 0 → Karena y > ymin yaitu 25 > 5

T = 0 → Karena y <>

Region code yang diperoleh dari titik D adalah 0000

Karena region code dari kedua titik adalah 0000 maka garis CD berada dalam kondisi Visible sehingga garis CD ini tidak perlu dipotong.

2. Dengan melakukan operasi logika AND juga dapat dibuktikan bahwa garis CD merupakan garis yang Visible. Perhitungannya 0000 AND 0000 = 0000

3. Garis EF

1. Menentukan region garis dari setiap encode

·Titik E (19,25)

L = 0 → Karena x > xmin yaitu 19 > 5

R = 0 → Karena x <>

B = 0 → Karena y > ymin yaitu 25 > 5

T = 0 → Karena y <>

Region code yang diperoleh dari titik E adalah 0000

·Titik F (20,32)

L = 0 → Karena x > xmin yaitu 20 > 5

R = 0 → Karena x <>

B = 0 → Karena y > ymin yaitu 32 > 5

T = 1 → Karena y <> 30

Region code yang diperoleh dari titik F adalah 1000

Karena region code dari salah satu titik ada yang bernilai 1000, maka garis EF tersebut berda pada kondisi Halfpartial dan perlu dipotong.

2. Dengan melakukan operasi logika AND maka dapat diperoleh hasil 0000 AND 1000 = 0000
3. Titik singgung pada garis EF (19,25) (20,32)

Region code 1000 untuk titik F (20,32), maka T =1 → Karena T = 1, maka yang dicari x2’

Maka titik singgungnya adalah (x2’,ymax) = (19.7, 30)

Akhirnya selesai juga proses Clipping Line dengan menggunakan Algoritma Cohen-Sutherlang Clipping Line....

Nah, perkenalan kita masih harus berlanjut ni... Berhubung yang pengen diajak kenalan (Clipping Polygon) dah capek seharian karena diajakin kenalan juga sama yang lainnya... Jadi, kita kenalan sama Clipping Polygon-nya besok aja ya...

Udah pagi ni, Ayo istirahat dulu...