Alur dalam Pemrosesan Polygon Mesh

Karakter dalam film animasi, tokoh dalam permainan online, hasil scan 3D patung, hingga desain komponen mekanik seringkali direpresentasikan dalam bentuk polygon mesh (mayoritas triangle mesh). Kita sering melihat model dalam bentuk triangle mesh yang bagus, setiap segitiganya mempunyai sudut mendekati 60 derajat, ukuran segitiga yang satu dengan yang lainnya relatif mirip, serta mampu merepresentasikan objek 3D secara relatif akurat. Bagaimana caranya menghasilkan objek 3D seperti itu?

Secara umu ada 2 cara untuk menghasilkan objek 3D: (1) menangkap representasi objek yang sudah ada atau (2) menghasilkan sintesis objek 3D. Cara pertama bisa dengan meng-scan objek secara 3D dan cara kedua seringkali dikerjakan oleh artis/seniman grafis. Akhir-akhir ini perbaduan antara keduanya juga relatif marak, seperti misalnya motion capture pada film animasi. Pada artikel kali ini, kita akan membahas cara yang pertama, yaitu merepresentasikan model 3D yang diperoleh dari hasil scan objek yang sudah ada.

Kita akan membahas bagaimana proses dari akuisisi data hingga penggunaannya untuk produksi.

Secara umum, berikut berbagai proses yang diperlukan:

1. Akuisisi data. Langkah ini merupakan tahapan pertama dari geometry processing. Secara umum ada dua tipe: pemindaian objek di dunia nyata dan sintesis objek digital dengan berbagai perangkat lunak seperti Blender, Maya, dsb. Untuk tujuan riset/akademis/industri/medis, lebih sering model yang digunakan adalah hasil pemindaian karena ia merepresentasikan suatu objek secara lebih akurat. Beberapa teknik untuk melakukan akuisisi data dengan pemindaian antara lain:
   1. CMM (Coordinate Measurement Machine). Alat ini mempunyai ‘tangan’ yang mampu bergerak dalam 6 degree-of-freedom dengan ujung yang sensitif. CMM menelusuri setiap bagian dari permukaan objek, sehingga dihasilkan scan 3D dari objek tersebut.

      

   2. Structured light. Cahaya dengan pola spatio-temporal dipancarkan ke permukaan suatu benda, lalu dengan kamera lain pola tersebut ditangkap. Dengan secara cerdas menentukan pola dan menangkap polanya, bisa dihasilkan representasi 3D dari objek tersebut.
2. Penghapusan data yang salah (baik secara topologi maupun geometri).  Secara umum langkah ini bertujuan untuk menghilangkan artifak dari model geometri, sehingga bisa dihasilkan model yang sesuai untuk proses lebih lanjut. Apa saja artifak yang harus dihilangkan? Berikut 8 tipe artifak yang perlu dihilangkan pada fase ini:
   1. lubang (hole). Dari hasil scan, seringkali tidak semua bagian bisa di-scan dengan baik (karena tertutupi, dll.) sehingga ada lubang pada model. Lubang ini perlu ditutupi/dilengkapi sehingga modelnya akan menjadi tertutup (water-tight).
   2. verteks singular. Secara umum kita mensyaratkan representasi permukaan objek harus merupakan manifold dan tidak tidak ada verteks yang singular. Dengan kata lain, jika kita men-traverse segitiga yang mengelilingi suatu verteks, kita akan kembali ke segitiga yang sama dan bisa mengunjungi semua segitiga yang bertetangga dengan verteks tersebut.
   3. handle.
   4. jeda antar poligon dan tumpang tindih. Representasi model seharusnya rata dan tidak boleh ada tumpang tindih. Jika ada, maka diperlukan algoritme untuk memperbaikinya.
   5. tumpang tindih dalam skala besar. Kadang satu sisi objek di-scan beberapa kali sehingga terjadi tumpang tindih dalam skala besar. Keadaan seperti ini perlu diatasi agar menghasilkan representasi poligon mesh yang bagus.
   6. orientasi yang tidak konsisten. Normal pada suatu poligon sangat penting fungsinya dalam operasi lebih lanjut (misal: pencahayaan ketika rendering). Karena algoritme sebelumnya yang kurang sempurna, seringkali orientasi normal pada poligon tidak konsisten. Oleh karena itu, diperlukan algoritme untuk memperbaikinya.
   7. edge kompleks. Secara umum suatu edge hanya boleh menjadi bagian dari 2 poligon (segitiga), tidak boleh lebih. Jika ada lebih dari 2 segitiga yang mempunyai edge yang sama, maka bagian itu menjadi non-manifold dan perlu ditangani lebih lanjut.
   8. persimpangan (intersection).

      

3. Analisis kualitas mesh. Kualitas mesh biasanya ditentukan oleh smoothness dan fairness dari mesh tersebut.  Smoothness dan fairness merupakan dua istilah yang mirip tetapi berbeda relatif jauh. Smoothness lebih mudah didefinisikan secara matematis karena ia merepresentasikan differentiability dari suatu permukaan, sedangkan fairness lebih sulit didefinisikan secara formal, yakni ukuran aesthetic kebagusan bentuk dari suatu mesh. Salah satu bentuk visualisasi fairness adalah dengan nilai kurvatur pada masing-masing verteks di mesh tersebut.
4. Surface smoothing. Seringkali terdapat noise pada data scan objek 3D kita, sehingga diperlukan algoritme untuk menghaluskan permukaan dari objek tersebut. Secara umum terdapat dua tujuan dari surface smoothing:
   1. menghilangkan noise pada data. Hasil scan 3D biasanya masih relatif kasar, karena tingkat akurasi dari piranti pemindainya. Bagian ini bertujuan untuk menghilangkan noise (frekuensi tinggi) dan tetap mempertahankan bentuk keseluruhan dari model (frekuensi rendah). Dalam pengolahan sinyal dan pengolahan citra, ini sering disebut dengan low-pass filtering. 
   2. menghasilkan representasi permukaan kualitas tinggi. Proses ini sering disebut dengan fairing, dengan tujuan untuk menghasilkan permukaan model yang memenuhi beberapa prasyarat keindahan/aestetik.

      

5. Parameterisasi. Secara umum, parameterisasi bisa disebut sebagai upaya untuk memberikan sistem koordinat pada model tersebut, agar lebih mudah untuk proses selanjutnya. Langkah yang paling umum adalah ‘merobek’ objek 3D, lalu meletakkannya ke permukaan 2D (bisa berupa lingkaran, persegi/persegi panjang, bentuk sembarang, dll.) dengan koordinat tertentu. Langkah ini paling umum diperlukan untuk texture mapping pada objek, misal: pemberian warna kulit pada karakter permainan online.

   

6. Simplifikasi. Proses simplifikasi bertujuan untuk mengurangi jumlah faces, edges, dan vertices dari suatu polygon mesh, namun tetap bisa menampilkan model tersebut seoptimal mungkin. Misal kita mempunyai suatu model kuda dengan 250.000 vertices, akan cukup besar ukurannya dan berat untuk pemrosesan di mobile. Kita bisa menggunakan algoritme simplifikasi agar menghasilkan model dengan 40.000 vertices dan masih merepresentasikan model kuda tersebut.
7. Remeshing. Dengan model 3D mesh yang sudah ada, kita diminta untuk menghasilkan mesh baru yang lebih baik, yakni yang memenuhi berbagai kriteria kualitas yang telah ditentukan. Kualitas di remeshing biasanya sudah tidak menyentuk ranah topologi (ini domain langkah ke-2) tetapi masuk ke aspek geometri, seperti: densitas sampling, regularitas, ukuran dari poligon, dll. Berikut beberapa kualitas yang sering diperhatikan pada tahap remeshing.
   • Struktur lokal:
     1. tipe elemen: Tipe yang paling umum dalam polygon mesh adalah segitiga (triangles) dan segi-empat (quad-rangles). Bisa jadi dari triangular mesh kita diminta menghasilkan quad mesh.
     2. bentuk elemen: Bentuk elemen bisa berupa isotropik atau anisotropik. Isotropik artinya ukurannya sama (misal: segitiga sama sisi dan persegi) sedangkan anisotropic artinya ukurannya tidak sama (misal: segitiga tumpul, jajar genjang dengan lebar yang besar dan tinggi yang pendek).
     3. densitas elemen: Dalam uniform density, biasanya elemen penyusunnya mempunyai ukuran yang sama di hampir semua bagian dari model. Sedangkan sebaliknya, non-uniform distribution mengupayakan ukuran elemen yang berbeda untuk berbagai bentuk yang berbeda. Misalnya, untuk bagian yang rata, bisa direpresentasikan dengan lebih sedikit segitiga dibandingkan bagian yang banyak informasi mendetail.
   • Struktur global: ini berkaitan dengan valensi dari suatu verteks, yaitu jumlah verteks lain yang berada di sekelilingnya. Secara umum, triangle mesh dikatakan regular jika memiliki valensi 6 sedangkan quad-mesh disebut regular jika mempunyai valensi 4.

     

Referensi:

1. Prof. Charlie Wang’s course note. Shape Modeling and Computing for Design (TU Delft PhD Course). http://homepage.tudelft.nl/h05k3/Courses/TUDelftShapeModeling.htm
2. Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., & Lévy, B. (2010). Polygon mesh processing. CRC press.
3. Botsch, M., Pauly, M., Kobbelt, L., Alliez, P., Lévy, B., Bischoff, S., & Röossl, C. (2007). Geometric modeling based on polygonal meshes.