Seminar Nasional Sistem dan Informatika 2006; Bali, November 17, 2006
SNSI06-019
PEMBENTUKAN MESH POLYGON SEGITIGA BERDASARKAN POLYGON NON-CONVEX Jimmy, S.T. Jurusan Teknik Informatika, Universitas Surabaya
[email protected] ABSTRACT A polygon is said to be convex if a line connecting any two points within the polygon lies entirely within it[Hill, 2001]. Convexity is required when we want to fill a polygon with a single solid color or pattern. On the other hand, graphic libraries, such as OpenGL, can only fill convex polygons. Problem arises when we need to draw a filled (solid colored or patterned) non-convex polygon. One way to finish this task is by dividing the non-convex polygon into several convex polygons. To ensure that all polygons are convex, they all must take the forms of triangle polygons. Therefore, the objective of this research is to create an application that is able to divide two dimensional polygons into several triangle polygons. The basic idea of the method used in this research is to connect three consecutive vertexes_ within the polygon observed. Those three connected vertexes will form a new triangle polygon. All lines that form the new triangle polygon must be assessed to assure that none of them has parts that lie outside the original polygon area. When an appropriate new triangle is acquired, the second vertex of that triangle polygon can be removed from the original polygon. These processes have to be conducted until the observed polygon has only three vertexes left and it will be the last triangle polygon that constructs the triangle mesh. When the routine finished, a triangle mesh that has a shape exactly the same as the original polygon is completed. Now, we can fill the polygon with a solid color or pattern as needed Keywords: Polygon, Non-Convex, Mesh, Triangle, Conversion.
1. Pendahuluan Istilah grafika komputer mengacu kepada gambar-gambar yang dibuat dengan atau dihasilkan oleh komputer. Komputer menghasilkan gambar berdasarkan data deskripsi gambar yang ada. Komputer dan manusia mempunyai cara yang berbeda dalam membuat gambar. Komputer memiliki sejumlah batasan dan aturan penggambaran yang harus dipatuhi. Salah satu batasan yang dimiliki grafika komputer adalah kemampuan untuk mengisi polygon dengan warna atau dengan pola tertentu. Graphic Library (kumpulan fungsi yang dapat digunakan untuk menghasilkan grafika komputer) yang beredar saat ini, seperti openGL, hanya dapat melakukan pengisian warna atau pola pada polygon – polygon convex[2]. Polygon dikatakan convex apabila sebuah garis yang menghubungkan dua buah titik manapun dari polygon berada seluruhnya diatas polygon tersebut. Gambar 1 menunjukkan contoh polygon convex dan polygon yang tidak convex.
A
C
B
D
Gambar 1. Polygon A Dan B Merupakan Polygon Convex. Polygon C Dan D Bukan Polygon Convex Keterbatasan tersebut menjadi masalah karena tidak semua objek polygon yang harus digambar merupakan polygon convex. Tujuan dari penelitian ini adalah membuat dan mengimplementasikan algoritma yang dapat mengubah sebuah polygon dua dimensi yang tidak convex menjadi sebuah jaringan polygon (mesh) segitiga. Polygon segitiga dipilih karena semua polygon segitiga pasti merupakan sebuah polygon convex.
2. Landasan Teori Algoritma yang dibuat dalam penelitian ini memanfaatkan sejumlah teori yang telah ada. Bab Landasan Teori ini akan membahas landasan teori yang digunakan dalam penelitian ini. 2.1. Vektor[1] Vektor adalah objek yang memiliki panjang dan arah. Vektor dapat digunakan untuk mewakili berbagai entiti fisik seperti gaya, perpindahan dan kecepatan. Sebuah vektor sering kali digambarkan sebagai sebuah panah dengan panjang tertentu yang mengarah ke suatu arah. Vektor dapat dianggap sebagai perpindahan dari suatu titik ke titik yang lain. Sehingga dapat dikatakan bahwa perbedaan antara dua titik merupakan sebuah vektor. Apabila terdapat titik A dan titik B maka vektor v dapat diperoleh menggunakan rumus : v=B–A (1) Operasi dasar yang dapat dilakukan pada vektor meliputi operasi penjumlahan dengan vektor lain dan operasi pengalian dengan skalar. Fasilitas lain yang memudahkan penggunaan vektor adalah dot product dan cross product. Dot product 114
Seminar Nasional Sistem dan Informatika 2006; Bali, November 17, 2006
SNSI06-019
menghasilkan sebuah skalar. Untuk menghitung dot product dari dua buah vektor, lakukan perkalian setiap pasangan komponen vektor yang berkorespondensi dan jumlahkan hasilnya. Contoh, dot product dari vektor (3,4) dan vektor (1,6) adalah 27. Cross product dari dua buah vektor adalah sebuah vektor baru yang tegak lurus terhadap kedua vektor yang dioperasikan. Cross product hanya dapat dihasilkan dari vektor – vektor tiga demensi. Untuk mendapatkan cross product dari vektor a = (ax, ay, az) dan vektor b = (bx, by, bz) dapat digunakan rumus berikut a x b = (aybz – azby)i + (azbx – axbz)j + (axby – aybx)k (2) 2.2. Pencarian Perpotongan dari Dua Garis[2] Permasalahan yang ingin dipecahkan pada sub bab ini adalah: apabila terdapat dua buah garis, tentukan apakah kedua garis tersebut berpotongan, jika mereka berpotongan, tentukan titik potong antar kedua garis tersebut. Misalkan garis pertama memiliki titik ujung A dan B serta garis lainnya memiliki titik ujung C dan D. Contoh variasi posisi kedua garis dapat dilihat di Gambar 2.
B
B
D
D
A C
A
B
D
B
C A
D
C
A
C
B
A
C
D
Gambar 2. Berbagai Contoh Variasi Posisi Dua Garis Setiap garis akan memiliki sebuah garis induk. Garis induk adalah perpanjaangan garis sampai tak terhingga panjangnya. Sehingga kecuali kedua garis saling paralel, garis induk kedua garis akan saling bertumbukan pada suatu titik. Titik tumbuk inilah yang akan dicari pertama kali. Langkah pertama adalah menetapkan representasi parametric untuk tiap garis. Apabila AB adalah segment dari A menuju ke B dan CD adalah segment dari C menuju ke D maka: AB(t) = A + bt (3) CD(u) = C + du (4) Dimana b=B–A d=D–C menggunakan persamaan (3), kita dapat menelusuri garis AB dari titik A ke titik B dengan menggerakkan t dari 0 menuju 1. Hal serupa dapat dilakukan terhadap garis CD menggunakan persamaan (4). Untuk menelusuri garis induk, nilai t dapat diperluas dari -∞ sampai ∞. Apabila garis induk pasti bertumbukan, maka pasti terdapat suatu nilai t dan u dimana persamaan (3) dan (4) akan menghasilkan posisi yang sama: A + bt = C + du dengan mendifinisikan c = C – A, maka akan didapatkan persamaan berikut : bt = c + du (5) kalikan kedua sisi dengan d⊥ untuk menghilangkan komponen d. maka akan didapatkan persamaan berikut: d⊥ . bt = d⊥ . c ⊥ Apabila d tidak NOL, maka nilai t dapat diperoleh dengan persamaan (6) t = (d⊥ . c) / (d⊥ . b) Garis AB dan CD berpotongan apabila nilai t diperoleh antara 0 sampai 1. Apabila d⊥ NOL, maka dapat dipastikan bahwa d dan b paralel. Sehingga kedua garis AB dan CD tidak akan pernah berpotongan.
3. Desain Algoritma Untuk memecahkan masalah pengisian polygon dua dimensi yang tidak convex dengan warna atau pola, dalam penelitian ini penulis membuat sebuah algoritma yang dapat mengubah sebuah polygon menjadi sebuah jaringan jaringan (mesh) polygon segitiga. Bentuk polygon segitiga dipilih karena semua polygon segitiga merupakan polygon convex. Batasan terpenting dalam proses pembentukan mesh polygon segitiga adalah mesh polygon yang dihasilkan harus memiliki bentuk yang sama seperti bentuk polygon awal. Ide dasar algoritma yang akan dibuat adalah mengambil tiga vertex polygon yang berurutan sebagai calon polygon segitiga penyusun mesh polygon. Kemudian calon polygon segitiga tersebut harus diperiksa kelayakannya. Calon polygon segitiga dianggap layak apabila tiga garis penyusunnya tidak memotong garis – garis penyusun polygon yang lain dan seluruh area polygon segitiga berada diatas polygon awal. Apabila calon polygon segitiga layak, maka calon polygon segitiga ditambahkan dalam mesh polygon dan vertex kedua dari calon polygon dihilangkan dari polygon awal. 115
Seminar Nasional Sistem dan Informatika 2006; Bali, November 17, 2006
SNSI06-019
Proses ini dilakukan sampai jumlah vertex yang tersisa pada polygon awal berjumlah 3 buah vertex. Flowchart dari algoritma yang dibuat dapat dilihat pada Gambar 3.
Gambar 3. Flow Chart Algoritma Pembentukan Mesh Polygon Segitiga Proses penentuan apakah tiga garis penyusun segitiga memotong garis-garis penyusun polygon dilakukan dengan mencari titik potong antara tiap garis segitiga dengan semua garis polygon. Pencarian titik potong dilakukan menggunakan algoritma yang dijelaskan pada sub bab 2.2. Garis 1 dan garis 2 merupakan garis yang terbentuk dari vertex – vertex yang berurutan. Sehingga garis 1 dan garis 2 pasti berada di area polygon. Sedangkan garis 3 merupakan garis baru yang dibuat untuk menghubungkan vertex 1 dan 116
Seminar Nasional Sistem dan Informatika 2006; Bali, November 17, 2006
SNSI06-019
vertex 3 dari ketiga vertex calon segitiga. Sehingga hanya garis 3 yang memiliki kemungkinan berada diluar area polygon. Proses penentuan apakah garis 3 berada di dalam polygon dilakukan dengan menggunakan sebuah garis bantu. Garis bantu menghubungkan sembarang titik pada garis 3 dengan sembarang titik yang letaknya lebih jauh dari garis terluar polygon. Setelah garis bantu tercipta, hitung jumlah titik perpotongan garis bantu terhadap polygon. Apabila jumlah titik perpotongan genap atau nol, maka dapat dipastikan garis ketiga berada di luar area polygon. Apabila garis ketiga berada di dalam polygon, maka jumlah titik perpotongan garis bantu terhadap polygon pasti ganjil. Gambar 4 menunjukkan ilustrasi penggunaan garis bantu.
Gambar 4. (A) Garis Bantu Di Dalam Polygon Memiliki 3 Titik Tabrak (B) Garis Bantu Di Luar Polygon Memiliki 2 Titik Tabrak Untuk mempermudah pemahaman algoritma, Gambar 5 akan menunjukkan ilustrasi proses pembentukan mesh polygon segitiga. Garis putus – putus adalah garis calon segitiga. Nomor urut digunakan untuk mengurutkan vertex polygon sesuai urutan searah jarum jam. Vertex pertama bisa ditunjuk dari vertex yang manapun pada polygon. Gambar ke-4 menunjukkan calon segitiga yang tidak layak karena garis ketiga berada diluar area polygon awal. Sehingga calon segitiga tidak dipakai dan nomor urut vertex digeser satu posisi.
Gambar 5. Ilustrasi Proses Pembentukan Mesh Polygon Segitiga
4. Hasil dan Diskusi Penelitian ini diimplementasikan menggunakan Microsoft Visual C#.NET dengan .NET framework versi 1.1. Untuk menampilkan gambar digunakan library OpenGL. Gambar 6 menunjukkan tampilan aplikasi yang menampilkan hasil pembentukan mesh polygon segitiga. Formasi mesh polygon segitiga sangat bergantung pada vertex yang digunakan sebagai acuan pertama. Sebuah uji coba telah dilakukan untuk memproses polygon yang sama seperti pada Gambar 5. Uji coba kali ini akan menggunakan vertex nomor 2 sebagai acuan pertama. Hasil ujicoba tampak pada Gambar 7. Tampak pada gambar kanan bahwa formasi 117
Seminar Nasional Sistem dan Informatika 2006; Bali, November 17, 2006
SNSI06-019
polygon segitiga penyusun mesh polygon berubah namun secara keseluruhan tetap menghasilkan bentuk yang sama seperti polygon awal.
Gambar 6. Hasil Implementasi Algoritma Pembentukan Mesh Polygon Segitiga Berdasarkan Polygon. Gambar Kiri Menampilkan Kerangka Mesh Polygon Segitiga. Gambar Kanan Menampilkan Mesh Polygon Segitiga Yang Diisi Dengan Warna Solid.
Gambar 7. Mesh Polygon Hasil Ujicoba Menggunakan Vertex Ke 2 Sebagai Acuan Pertama Algoritma yang dibuat pada penelitian ini dapat digunakan tidak hanya untuk polygon non-convex namun juga dapat digunakan untuk polygon convex. Gambar 8 menunjukkan hasil uji coba algoritma pada sebuah polygon convex.
Gambar 8. Hasil Uji Coba Pada Objek Polygon Convex Karena algoritma yang dibuat pada penelitian ini memproses tiap vertex secara berurutan searah jarum jam, maka algoritma yang dihasilkan hanya dapat digunakan untuk memproses polygon sederhana. Sebuah polygon dikatakan sederhana jika tidak ada garis-garis polygon yang saling berpotongan. Gambar 9 menunjukkan contoh polygon yang tidak sederhana.
118
Seminar Nasional Sistem dan Informatika 2006; Bali, November 17, 2006
SNSI06-019
Gambar 9. Polygon Tidak Sederhana
5. Kesimpulan dan Saran Setelah melakukan penelitian ini, diambil beberapa kesimpulan sebagai berikut : • Algoritma yang dibuat pada penelitian ini telah berhasil mengubah poligon convex maupun non convex menjadi mesh polygon segitiga yang memiliki bentuk yang sama dengan polygon awal. • Formasi polygon segitiga penyusun mesh polygon segitiga bergantung dari vertex yang digunakan sebagai acuan pertama. Meskipun formasi polygon penyusun segitiga berbeda, namun secara keseluruhan tetap menghasilkan bentuk yang sama seperti polygon awal. Algoritma yang dibuat pada penelitian ini hanya dapat digunakan pada polygon dua dimensi sederhana. Keterbatasan tersebut dapat digunakan sebagai sasaran tujuan penelitian lanjutan dari hasil penelitian ini.
Daftar Pustaka
[1] Hill, Jr, F.S. (2001). Computer Graphics Using OpenGL, 2nd Edition. New Jersey : Prentice Hall [2] Neider, T., Davis, T., Woo, M. (1994). OpenGL Programming Guide, The Official Guide to Learning OpenGL, Release 1, Addison-Wesley.
119
