Virtual Sculpting Menggunakan Tool Berbasis Vector Pada Triangle Mesh

Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.

Virtual Sculpting Menggunakan Tool Berbasis Vector Pada Triangle Mesh

I Ketut Purnamawan 1*, Handayani Tjandrasa 2 Jurusan Teknik Informatika, Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia1* [email protected] Jurusan Teknik Informatika, Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia 2

Abstrak Virtual sculpting menjadi salah satu bidang penelitian pada grafika komputer. Berbagai metode virtual sculpting beserta model tool yang menyertainya dikembangkan untuk menciptakan suatu sistem pemodelan yang intuitif, cepat, dan mampu menciptakan model dengan tingkat kerumitan tinggi. Masing-masing metode memiliki kelebihan dan kekurangan tersendiri. Pada makalah ini diajukan suatu metode untuk melakukan virtual sculpting pada triangle mesh dengan menggunakan tool berbasis vector. Tool dibentuk dari vector-vector searah yang dapat dibuat dalam berbagai bentuk. Collision detection antara tool dan objek memanfaatkan fungsi ray-triangle intersection yang ada pada graphics processing unit (GPU). Decay function digunakan untuk menciptakan lengkungan yang halus pada pinggiran area terdeformasi. Proses deformasi yang dihasilkan cepat. Sistem yang dibangun memiliki kemampuan pemodelan yang bagus dan intuitif. Dengan model tool yang diajukan, tool dalam berbagai bentuk dapat dengan mudah dibuat dari gambar sketsa. Katakunci: Virtual sculpting, Ray-triangle intersection, Triangle mesh, Collision detection.

1. Pendahuluan Virtual sculpting atau sering disebut computer sculpting merupakan suatu pemodelan geometrik. Bill dan Lodha (Bill and Lodha, 1994) memberikan definisi virtual sculpting sebagai pemodelan geometrik yang interaktif dimana tujuan dan cara-cara sculpture tradisional diemulasikan. Tujuan yang dimaksud adalah mendesain objek 3D yang free-form. Sedangkan cara-cara yang dimaksud adalah manipulasi secara langsung terhadap bahan dengan menggunakan tangan atau manipulasi secara tidak langsung dengan menggunakan peralatan sculpting (sculpting tools). Pada Virtual sculpting, ada beberapa hal yang harus dipenuhi. Yang pertama, representasi objek yang digunakan haruslah memiliki karakteristik yang semirip-miripnya dengan bahan-bahan pada kehidupan nyata, dan bisa membentuk bentuk yang sebebas-bebasnya. Kedua, representasi objek yang digunakan memungkinkan objek dapat dirender dengan cepat, agar tidak menjadi hambatan dalam proses sculpting yang real-time. Ketiga, desain dan mekanisme kerja virtual sculpting tools (untuk selanjutnya, virtual sculpting tools akan disebut dengan tool) harus seintuitif mungkin dan dapat digunakan untuk melakukan manipulasi bentuk serumit mungkin. Keempat, komputasi yang dilakukan untuk proses sculpting tidak terlalu komplek, sehingga proses sculpting bisa dilakukan secara real-time.

Beberapa sistem virtual sculpting telah dikembangkan sebelumnya. Sederberg dan Parry mengenalkan Free-Form Deformation (FFD) untuk melakukan solid modeling (Sederberg and Parry, 1986). Pada FFD, penggunaan tool sulit diterapkan karena manipulasi objeknya bersifat tidak langsung. Hsu, Huges, dan Kaufman mengenalkan Direct Manipulation Free-Form Deformation (DMFFD), yang merupakan pengembangan dari FFD (Hsu, Huges, dan Kaufman, 1992). Pada DMFFD, penerapan tool menjadi lebih mudah. Hsu menggunakan tool sederhana untuk melakukan operasi pushing dan pulling pada vertex-vertex yang dipilih. Hilton dan Egbert (Hilton dan Egbert, 1994) mengenalkan tool berbasis vector field. Collision detection antara tool dan objek ditentukan dengan melihat apakah titik-titik objek berada di dalam wilayah tool. Disini bentuk-bentuk tool yang dapat diterapkan terbatas pada bentukbentuk sederhana. Bill dan Lodha (Bill and Lodha, 1994) pada sistem yang dinamai SAMIAM, memanfaatkan persamaan superkudratik untuk mendefinisikan tool, yang digunakan untuk melakukan pemodelan pada polygon mesh. Bentuk tool pada SAM-IAM juga terbatas pada bentuk-bentuk sederhana. Gain dan Marais pada metodenya yang disebut Warp Sculpting (Gain dan Marais, 2005) memanfaatkan distance field untuk melakukan collision detection antara tool dan objek. Zhang dan Leu (Zhang and Leu, 2009) menerapkan metode yang hampir sama


dengan Warp Sculpting pada implicit object, dengan menambahkan metode level-set untuk menentukan deformasi. Pada makalah ini diajukan suatu metode virtual sculpting dengan menggunakan tool berbasis vector yang diterapkan pada triangle mesh. Tool dibentuk dari sekumpulan vector-vector searah yang tersusun dalam bentuk tertentu. Mekanisme collision detection-nya memanfaatkan fungsi ray-triangle intersection yang terdapat pada graphics processing unit (GPU). Dengan menggunakan fungsi yang terdapat pada GPU, proses deformasi dapat berlangsung dengan cepat. Tool dapat dibentuk dalam bentuk-bentuk yang rumit, dan dapat dengan mudah dibentuk dari gambar sketsa. 2. Metode 2.1 Ray-Triangle Intersection Fungsi ray-triangle intersection adalah fungsi untuk menentukan perpotongan antara suatu sinar dengan segitiga. Fungsi ini digunakan dalam proses pencahayaan pada kartu grafis. Sinar dinyatakan dengan dua buah vector, yaitu vector yang menyatakan letak sumber cahaya, dan vector satuan yang menyatakan arah sinar. Jika O adalah vector posisi sumber sinar, dan D adalah vector satuan yang menunjukkan arah sinar, maka sinar akan mempunyai persamaan titik sebagai berikut. R (t ) = O + tD (1) Persamaan titik suatu segi tiga yang dibentuk oleh tiga buah titik V1, V2, dan V2 dinyatakan sebagai berikut. T (u , v) = (1 − u − v)V1 + uV2 + vV3

(2) dimana (u,v) adalah koordinat barycentric, yang harus memenuhi u ≥ 0, v ≥ 0, dan u + v ≤ 1. Moller dan Trumbore mengajukan satu metode untuk menentukan perpotongan antara sinar dan segitiga dengan cepat (Moller and Trumbore, 1997). Jika sinar berpotongan dengan segitiga, maka akan ada nilai t, u, dan v yang memenuhi persamaan berikut. O + tD = (1 − u − v )V1 + uV 2 + vV3

(3)

v=

((O − V2 ) × (V2 − V1 )) • D ( D × (V3 − V1 )) • (V2 − V1 )

(7)

Jika u ≥ 0, v ≥ 0, dan u + v ≤ 1, maka sinar akan berpotongan dengan segitiga pada titik potong O + tD . 2.2 Ide Dasar Ide dasar metode yang diajukan adalah mendeformasi objek dengan cara menusukkan tool kedalamnya. Kondisi apakah tool telah menusuk objek dideteksi dengan mencari perpotongan cahaya dengan sumber O yang terletak pada pangkal vector-vector pembentuk tool, dengan arah D yang merupakan arah vectorvector tool, dengan segitiga-segitiga yang membentuk permukaan objek (faces).

Gambar 1. Proses penusukan tool pada objek

Jika satu face ditembus oleh cahaya yang berasal dari vector tool Vp, pada titik P, dan jarak P dengan O lebih kecil atau sama dengan panjang Vp, maka face tersebut ditembus oleh vector tool. Vertex objek yang semua face yang dibentuk olehnya ditembus oleh vector tool dinyatakan berada di dalam tool dan ditransformasikan menggunakan vector transformasi Vt yang merupakan potongan vector tool terdekat yang berada di dalam objek. (8) Vt = Vp − ( P − O ) Vertex-vertex yang berada diluar tool dan berada disekitar titik-titik potong ditransformasikan menggunakan decay function.

Dari perhitungan yang dilakukan oleh Moller dan Trumbore didapatkan persamaan sebagai berikut. ⎡((O − V1 ) × (V2 − V1 )) • (V3 − V1 )⎤ ⎡t ⎤ 1 ⎢ ⎥ ⎢u ⎥ = ⎥ ⎢ ⎥ ( D × (V − V )) • (V − V ) ⎢( D × (V3 − V1 )) • (O − V1 ) 3 1 2 1 ⎢⎣((O − V2 ) × (V2 − V1 )) • D ⎥⎦ ⎢⎣v ⎥⎦

(4) Jadi, t=

((O − V1 ) × (V2 − V1 )) • (V3 − V1 ) ( D × (V3 − V1 )) • (V2 − V1 )

u=

( D × (V3 − V1 )) • (O − V1 ) ( D × (V3 − V1 )) • (V2 − V1 )

(5) (6)

Gambar 2. Deformasi menggunakan potongan vector-vector tool yang berada didalam objek

Namun dari analisa didapatkan bahwa, dengan mekanisme seperti ini, komputasi yang diperlukan cukup besar. Kualitas hasil sculpting juga sangat tergantung dari tingkat kerapatan vector tool. Semakin rapat vector tool nya, maka


semakin baik kualitas hasil sculpting nya. Di lain pihak, semakin padat vector tool nya, maka semakin banyak vector yang diperlukan, dan semakin besar pula komputasi yang diperlukan. 2.3 Metode yang Dioptimasi Untuk melakukan optimasi, cara untuk melakukan collision detection diubah. Vector sinar tidak lagi berasal dari pangkal vector-vector tool, dan tidak dipotongkan dengan face-face objek, melainkan dipancarkan dari vertex-vertex objek dengan arah berlawanan dengan arah vector-vector tool. Di sini, pangkal tool akan diisi dengan triangle mesh yang berbentuk segiempat, yang dibentuk dari dua buah face. Mesh segi empat ini tegak lurus dengan vectorvector tool, dan semua pangkal vector-vector tool berada di dalam wilayah segiempatnya. Pada mesh segiempat tersebut akan dibuat suatu grid, dengan panjang sisi sel grid merupakan jarak antar vector tool, seperti yang diperlihatkan pada gambar 3. Pada sel-sel grid yang berisi vector tool, satu sel grid mewakili satu vector tool. Pada sel-sel grid yang tidak berisi vector tool, setiap selnya akan berisi informasi jarak ke vector tool terdekat, dan vector tool yang mana yang terdekat. Jaraknya dihitung berdasarkan jarak antar sel. Informasi jarak ini akan dipergunakan pada perhitungan decay function.

Gambar 3. Grid yang terdapat pada pangkal tool yang berbentuk elip. Grid dibentuk dari mesh berbentuk segiempat yang terdiri dari dua buah face. Sel yang berwarna hitam adalah sel yang berisi vector tool.

Sinar yang berasal dari vertex-vertex objek akan dipotongkan dengan segiempat yang berada pada pangkal tool. Sekarang asal sinar O adalah posisi vertex objek. Dan arah sinar D sekarang berlawanan dengan arah vector-vector tool. P adalah titik potong sinar dengan mesh segiempat. Jika P berada pada sel yang berisi vector tool, maka vertex objek pada O ditransformasikan menggunakan vector transformasi Vt. Misalkan Vp adalah vector tool yang berada pada sel tempat terjadinya perpotongan, maka Vt dapat ditentukan dengan persamaan berikut. Vt = Vp − (O − P )

Vt = Vp + P − O

(9)

Gambar 4. Proses penusukan tool pada objek dengan metode yang dioptimasi .

Gambar 5. Deformasi menggunakan potongan vector-vector tool yang berada didalam objek pada metode yang dioptimasi.

Jika P berada pada sel yang tidak berisi vector tool, maka vertex objek yang berada pada O ditransformasikan menggunakan decay function. Jika sinar tidak memotong mesh segiempat, maka vertex objek pada O tidak ditransformasikan. Decay function yang digunakan adalah decay function yang digunakan pada (Gain and Marais, 2005) dan (Singh and Fiume, 1998), dan yang digunakan pada (Bill and Lodha, 1994). Persamaan-persamaannya adalah sebagai berikut. ⎧(( d ) 2 − 1) 2 → if d ≤ r w(d ) = ⎨ r → otherwise ⎩0

(10)

⎧(1 + sin( π2 − dr π )) / 2 → if d ≤ r w(d ) = ⎨ → otherwise ⎩0

(11)

⎧1 − ( dr ) 2 → if d ≤ r w(d ) = ⎨ → otherwise ⎩0

(12)

⎧( d − 1) 2 → if d ≤ r w( d ) = ⎨ r → otherwise ⎩0 ⎧1 − d w(d ) = ⎨ r ⎩0

→ if d ≤ r

⎧1 w(d ) = ⎨ ⎩0

→ if d ≤ r → otherwise

→ otherwise

(13)

(14) (15)

dimana d adalah jarak titik objek ke titik collision terdekat, r adalah radius decay function yang ditetapkan, dan w(d) adalah proporsi transformasi yang nilainya 0 ≤ w(d) ≤ 1. Pada


metode ini, nilai d adalah jarak sel yang tidak berisi vector tool, dengan sel yang berisi vector tool terdekat. Jika Vts adalah potongan vector tool terdekat, yang masuk kedalam objek, maka vector transformasi yang dihasilkan dari decay function (Vd) dapat ditentukan sebagai berikut.

dibentuk oleh sebuah vector, decay function menentukan bentuk hasil deformasi. Gambar 7 menunjukkan berbagai bentuk hasil deformasi menggunakan tool vector tunggal, dengan menggunakan decay function berbeda-beda.

Vd = w( d ).Vts

(16) Untuk menghemat komputasi, perhitungan tidak dilakukan pada semua vertex objek. Penerapan region of influence (ROI) akan membatasi jumlah vertex yang diproses dengan hanya memproses vertex-vertex yang ada pada ROI. Pada algoritma ide dasar, perhitungan raytriangle intersection akan dilakukan sebanyak p×l, dimana p adalah jumlah vector tool, dan l adalah jumlah face objek. Setelah dilakukan optimasi, perhitungan ray-triangle intersection akan dilakukan sebanyak 2m, dimana m adalah jumlah vertex objek. Dan dengan penerapan ROI, perhitungan ray-triangle intersection menjadi sebanyak 2n, dimana n adalah jumlah vertex objek yang berada di dalam ROI, dan n ≤ m. 3. Hasil dan Pembahasan 3.1 Bentuk Tool Dengan model tool yang diajukan, tool dapat dibentuk dengan bentuk yang rumit, dan dapat dengan mudah dibentuk dari formula dan gambar sketsa. Gambar 6 menunjukkan contoh bentukbentuk tool yang dapat dibentuk dan diterapkan oleh sistem.

Gambar 7. Bentuk-bentuk hasil deformasi yang dihasilkan oleh decay functions.

Bentuk deformasi pada barisan depan dari kiri ke kanan berturut-turut dihasilkan oleh persamaan (10), (11), dan (12), pada barisan belakang, dari kiri ke kanan berturut-turut dihasilkan oleh persamaan (13), (14), dan (15). Persamaan (10) menghasilkan bentuk gundukan melandai. Persamaan (11) menghasilkan bentuk menyerupai bel. Persamaan (12) menghasilkan bentuk gundukan cembung. Persamaan (13) menghasilkan bentuk gundukan lancip. Persamaan (14) menghasilkan bentuk kerucut. Persamaan (15) menghasilkan bentuk gundukan datar. Gambar 8 menunjukkan kegunaan decay function untuk membentuk lengkungan halus pada pinggiran daerah terdeformasi. Semua bentuk hasil deformasi didapatkan dengan menggunakan tool yang sama, namun dengan menggunakan decay function yang berbeda. Dari kiri ke kanan, depan ke belakang, decay function yang digunakan berturut-turut adalah persamaan (10), (11), (12), (13), (14), dan (15).

Gambar 8. Lengkungan pinggiran yang berbeda, didapatkan dari decay function berbeda.

Gambar 6. Berbagai bentuk tool yang bisa dihasilkan dan digunakan oleh sistem.

Tool yang berbentuk kotak dan elipsoid, dibuat dengan menggunakan formula. tool elipsoid diciptakan dengan mengunakan persamaan elipsoid. Tool yang berbentuk jarum adalah tool yang terdiri dari satu vector tool. Tool-tool dengan berbagai bentuk lainnya, dibuat dari gambar sketsa. 3.2 Penerapan Decay Function Pada dasarnya, decay function digunakan untuk membuat lengkungan halus pada pinggiran wilayah terdeformasi. Namun pada penggunaan tool vector tunggal, yaitu tool yang hanya

3.3 Kemampuan Pemodelan Sistem Kemampuan pemodelan sistem sangat menjanjikan. Gambar 9 dan gambar 10 menunjukkan objek yang dihasilkan oleh sistem. Objek yang ditunjukkan pada gambar 9 adalah objek berbentuk kepala yang dihasilkan dari objek dasar berbentuk bola. Objek dibuat dalam waktu kurang dari satu jam oleh tester yang belum berpengalaman menggunakan sistem. Alat inputan yang digunakan adalah mouse dan keyboard standar. Untuk mengulang membuat objek yang serupa, dapat dilakukan dalam waktu kurang dari tiga puluh menit. Objek yang ditunjukkan pada gambar 10 adalah objek berbentuk relief dinding. Objek ini dihasilkan dari bentuk dasar berupa bidang


segiempat. Relief dibentuk dengan menggunakan beberapa tool dengan berbagai bentuk, yang dihasilkan dari gambar. Objek dapat dibuat dalam waktu sekitar 10 menit.

Gambar 9. Objek berbentuk kepala yang dihasilkan oleh sistem. Objek dihasilkan dari objek dasar berbentuk bola.

Gambar 10. Objek berbentuk relief pada dinding yang dihasilkan dari bentuk dasar berbentuk bidang segiempat.

3.4 Kecepatan Deformasi Kecepatan deformasi yang dihasilkan sangat mendukung proses pemodelan yang real-time. Kecepatan deformasi diukur dalam kondisi jumlah vertex objek yang berada dalam ROI berbeda-beda. Tabel 1 menunjukkan kecepatan deformasi berdasarkan jumlah vertex yang berada di dalam ROI. Kecepatan deformasi diukur pada lingkungan notebook dengan sistem operasi Microsoft Windows XP, proccessor Pentium DualCore 2.0GHz, RAM 1GB, dan GPU Intel GMA4500 dengan memori share. Tabel 1: Kecepatan proses deformasi berdasarkan jumlah vertex objek yang berada di dalam ROI. Jumlah vertex objek di dalam ROI 1000 5000 10000 20000 30000 40000 50000

Rentang kecepatan deformasi (kali/detik) >1000 62.50 – >1000 31.25 – 66.67 16.13 – 21.28 7.09 – 12.82 5.85 – 9.09 4.57 – 8.00

Dengan kecepatan yang didapatkan, seperti yang terlihat pada tabel 1, proses sculpting menjadi bisa dilakukan secara benar-benar real-time. Pada jumlah vertex lebih kecil dari 5000, kecepatan deformasi bahkan mecapai lebih besar dari 60 kali/detik, yang merupakan frekwensi standar refresh rate monitor LCD. Pada jumlah vertex sebesar 50000, kecepatan turun sampai mencapai 4.5 kali/detik.

4. Kesimpulan Suatu sistem virtual sculpting telah dibangun dengan menggunakan metode yang diajukan. Dengan model tool yang diajukan, tool dapat dibentuk dalam bentuk-bentuk yang rumit dan dapat dengan mudah dibuat dari gambar sketsa. Kemampuan pemodelan sistem sangat baik. Pemodelan dapat dilakukan secara intuitif dan real-time. Dengan menggunakan sistem yang dibangun, pengguna yang belum berpengalaman dapat menciptakan model yang cukup rumit dalam waktu yang cukup singkat. Kecepatan deformasi yang dihasilkan oleh metode yang diajukan sangat baik. Kecepatan yang dihasilkan memungkinkan pengguna dapat melakukan pemodelan secara real-time dengan benar-benar nyaman.

5. Pustaka Sederberg, T. and Parry, S. (1986), Free-Form Deformation of Solid Geometric Models, Computer Graphics (Proc. ACM SIGGRAPH ’86), vol. 20, no 4, p.161-171. Hsu, W.M., Huges, J.F., and Kaufman, H. (1992), Direct Manipulation of Free-Form Deformation, Computer Graphics (Proc. ACM SIGGRAPH 92), vol. 26, no. 2, p. 177184. Hilton, T.L. and Egbert, P.K. (1994), Vector Fields: An Interactive Tool for Animation, Modeling and Simulation with Physically Based 3D Particle System and Soft Objects, Computer Graphics Forum (Proc. Eurographics 94), vol. 13, no. 3, p. 329-338. Bill, J.R and Lodha, S. (1994), Computer Sculpting of Polygonal Models using Virtual Tools, Technical Report UCSC-CRL-94-27, Baskin Center for Computer Engineering and Information Sciences, University of California, Santa Cruz, US. Moller, T. and Trumbore, B. (1997), Fast, Minimum Storage Ray-Triangle Intersection, Journal of Graphics Tools, vol.2, No. 1, p. 21-28. Singh, K. and Fiume, E. (1998), Wires: A Geometric Deformation Technique, Proc. ACM SIGGRAPH ‘98, p. 405-414.


Gain, J. and Marais, P. (2005), Warp Sculpting, IEEE Transaction on Visualitation and Computer Graphics, vol. 11, no. 2, p. 217227. Zhang, W. and Leu, M.C. (2009), A Spatial Warping Method for Freeform Modeling Based on a Level-set Method, ComputerAided Design, 41, p. 765-771.

Virtual Sculpting Menggunakan Tool Berbasis Vector Pada Triangle Mesh

Recommend Documents