DEFORMASI OBYEK TIGA DIMENSI DENGAN METODE LAPLACIAN Rizky Yuniar Hakkun(1), Mochammad Hariadi(2), 1) Pasca Sarjana JCM Jurusan Game Technology Jurusan Teknik Elektro ITS, Surabaya 60111, email :
[email protected] 2) Jurusan Teknik Elektro ITS, Surabaya 60111, email :
[email protected]
elastis yang bisa digunakan sebagai bahan acuan bagi peneliti selanjutnya di berbagai bidang, seperti grafika komputer untuk mensimulasikan benda lentur pada komputer.
Abstrak - Penelitian ini mengajukan sebuah konsep deformasi obyek tiga dimensi yang mengacu pada fenomena alam di dunia nyata khususnya yang berhubungan dengan benda elastis. Penelitian tentang elastisitas benda telah banyak dilakukan para peneliti di bidang fisika dan matematika.
Permasalahan yang diangkat pada penelitian ini adalah bagaimana mendeformasi obyek 3 dimensi dari data vertek diberikan. Tahapan permasalahan yang harus diselesaikan dalam penelitian ini adalah sebagai berikut :
Koordinat diferensial merupakan konsep representasi diferensial obyek pada ruang Euclidean. Laplacian merupakan salah satu operator dalam koordinat diferensial, yang menyimpan informasi detail lokal dari permukaan. Obyek diubah kedalam koordinat diferensial. Transformasi, seperti rotasi dan translasi, dilakukan pada koordinat diferensial permukaan, tidak pada koordinat Cartesian. Sehingga dibutuhkan rekonstruksi dari koordinat diferensial agar kembali ke koordinat Cartesian.
Merepresentasikan obyek mesh 3 dimensi dalam representasi koordinat diferensial. Merekonstruksi obyek 3 dimensi dari representasi koordinat diferensial ke koordinat Cartesian Mentrasnsformasi representasi koordinat diferensial bentuk 3 dimensi dengan menggunakan vertek kendali yang diberikan. Merekonstruksi representasi koordinat diferensial obyek 3 dimensi mesh yang terdeformasi.
Hasil percobaan menunjukkan rekonstruksi mesh dari koordinat diferensial membutuhkan penambahan minimal satu vertek jangkar stasioner pada pemecahan sistem persamaan linearnya. Penelitian menunjukkan bahwa pemilihan jangkar stasioner 6% 15% ROI dapat menghasilkan rekonstruksi yang baik. Semakin besar vertek dalam mesh, proses pemecahan sistem linear juga akan semakin lama.
2. LANDASAN TEORI 2.1. Representasi Koordinat Diferensial Matrik Laplacian (Cvetkovi ,1998) dari sebuah graph G, dimana = ( , ) graph tak berarah, tak berbobot tanpa loop atau edge multiple dari satu vertek ke vertek lain, adalah sekumpulan vertek = | | dan sekumpulan edge E, merupakan matriks simetris dengan satu baris dan kolom tiap node didefinisikan dengan L = D – A .
Kata Kunci : Deformasi, laplacian, mesh, geometri, animasi. 1. PENDAHULUAN
dimana D = diag( , , … , ) merupakan matrik derajat (Babic,2002), yaitu matriks diagonal yang dibentuk dari derajat vertek dan A adalah matrik berdekatan (adjacency).
Fenomena benda yang bersifat elastis menjadi daya tarik tersendiri bagi para peneliti khususnya di bidang grafika komputer. Benda elastis banyak sekali sering dijumpai di kehidupan nyata misalnya karet, pegas sampai benda padat seperti besi pun memiliki elastisitas. Suatu benda dinyatakan elastis jika benda tersebut berubah bentuk (deform) ketika diberikan sebuah gaya kepadanya dan kembali ke bentuk semula ketika gaya tersebut hilang. Beberapa peneliti telah menhasilkan beberapa formulasi mengenai benda
1
Derajat suatu vertek graph dalam graph G adalah jumlah edge graph yang menyentuh v. Derajat vertek minimum dalam suatu graph dinotasikan dalam ( ), sedangkan derajat vertek maksimum dinotasikan dalam ( ) (Skiena,1990).
Gambar 1. Vektor koordinat diferensial pada vertex yang mirip dengan karakteristik bentuk lokal permukaan.
Sorkine (Sorkine,2006) pada penelitiannya mendefinisikan tentang koordinat diferensial ( coordinates), operator Laplacian yang bersesusaian dan menjelaskan kerangka bangun kembali permukaan. Definisi koordinat diferensial yang dijelaskan merupakan koordinaat pada R3.
Kemudian vektor koordinat diferensial dapat ditulis sebagai berikut :
Misal = ( , , ) merupakan mesh triangle dengan n vertices dimana V merupakan kumpulan vertices (titik), E merupakan kumpulan edge (tepi) dan F merupakan kumpulan faces (muka). Setiap vertex merupakan koordinat Cartesian yang didefinisikan oleh = ( , , ). Koordinat diferensial atau -coordinates dari merupakan perbedaan antara koordinat absolut dengan pusat massa dari titik tersebut dengan titik tetangga terdekatnya dalam mesh. Berikut adalah persamaan diferensial titik : =
( )
,
( )
,
( )
=
Penjumlahan
lim|
diatas merupakan | |
(
diskritisasi dari ) ( ), dimana
|
| |
(
) ( )
( )
(6) dan
2.2. Rekonstruksi Permukaan -Coordinates ( )
(1)
Setiap kali melakukan manipulasi pada -coordinates, langkah terakhir yang akan dilakukan adalah memrekonstruksi permukaan dari mesh. Dengan kata lain yang harus dilakukan adalah mengembalikan mesh yang telah berubah menjadi -coordinates tersebut ke koordinat Cartesian Proses pengembalian dari -coordinates ke koordinat Cartesian tidak bisa langsung dilakukan. Laplacian matriks (L atau ) yang dihasilkan dari (4) tidak bisa langsung digunakan untuk mentransformasikan koordinat diferensial ke koordinat global karena matriks Laplacian tersebut adalah singular dan rank(L) adalah n-1. Pengembalian koordinat global dari koordinat diferensial membutuhkan pemecahan sistem linear full-rank Maka dibutuhkan penambahan constrain pada matriks L dan . = , (7) sehingga sistem linear menjadi :
(2)
(3)
, = 1, ( , 0, otherwise
(5)
dimana ( ) adalah curvature rerata dari adalah normal permukaan.
Kemudian matriks L diubah dalam bentuk versi simetris yang didefinisikan dengan = = , ( ) =
)
merupakan permukaan kurva tertutup sederhana sekitar vi dan | | adalah panjang dari . Telah diketahui dalam geometri diferensial bahwa :
dan jika D merupakan matriks diagonal sedemikian rupa sehingga = . Sehingga transformasi matriks koordinat absolute ke koordinat relatif adalah : =
( )(
integral curvilinear :
( ) = { |( , } dan dimana = | ( )| merupakan jumlah tetangga terdekat dari i (derajat i). Transformasi vektor koordinat absolut Cartesian ke vektor koordinat diferensial dapat ditampilkan dalam bentuk matriks. Jika A merupakan matriks bersesuaian pada mesh, maka : 1 (, = 0 otherwise
=
(4)
|
Sehingga = ( ), = ( ) dan = ( ), dimana x merupakan n-vektor yang berisi koordinat absolut x dari semua vertices, begitu pula y dan z. Gambar 2 merupakan contoh mesh dan matriks asosiasinya. Fiedler (Fiedler,1973) mendefinisikan bahwa matriks atau ( ) yang dijelaskan sebelumnya disebut sebagai Laplacian graph dari mesh.
=
( ) :
(8)
Sistem yang dibuat menjadi full-rank sehingga memiliki solusi unik secara least-square (9) Solusi least-square persaman diatas dapat diekspresikan dalam bentuk matriks persegi ( + ) × sebagai berikut : =( ) (10) 3. METODE PENELITIAN
Secara garis besar langkah-langkah dalam penelitian ini mulai proses pengumpulan referensi, perancangan data masukan obyek 3 dimensi sampai rekonstruksi
2
Transformasi (translasi atau rotasi) dilakukan pada koordinat diferensial, kemudian dilakukan rekonstruksi kembali untuk menghasilkan koordinat Cartesian yang terdeformasi.
obyek 3 dimensi dapat digambarkan dalam bentuk blok diagram seperti pada gambar berikut ini :
4. PENGUJIAN DAN ANALISA 4.1. Uji dan Analisa Representasi -Coordinates Pengujian dilakukan menggunakan obyek Kubus sederhana untuk memperlihatkan proses representasi koordinat diferensial, rekonstruksi dan deformasi.
Gambar 4. Kubus 8 vertek dan 12 facet
Gambar 2. Diagram Alur Penelitian
Vektor yang dihasilkan sebagai berikut :
Pada bagian representasi koordinat diferensial, proses pertama merupakan pembentukan vektor V yang berisi vertek obyek tiga dimensi data masukan. Proses selanjutnya adalah pembentuk matriks derajat dan adjacency dari vertek dan facet obyek. Matriks Laplacian selanjutnya dapat diperoleh dengan menggunakan persamaan L = D – A. Representasi koordinat diferensial dihasilkan dengan dot product matriks Laplacian L dan V pada masing masing komponen x, y dan z. Pada bagian deformasi dan rekonstruksi, proses yang dilakukan pertama adalah penentuan jangkar stationer (soft constraint) yang akan ditambahkan pada matrik L dan . Proses rekonstruksi dapat langsung dilakukan. Pada proses deformasi terlebih dahulu dilakukan pemilihan area pengeditan (region of interest) dan vertek kendali.
Gambar 5. Vektor komponen x, y dan z
Matriks adjacency didapatkan sebagai berikut :
Gambar 6. Matrik Adjacency
Matrik diagonal derajat adjacency dari vertek sebagai berikut :
Gambar 7. Matrik Degree of Adjacency
Matriks Laplacian didapatkan dengan menggunakah persamaan L = D – A.
Gambar 3. ROI, titik merah adalah soft constraint, vertek kendali (titik kuning) dan vertek yang berubah sesuai vertek kendali (titik hijau)
ROI digunakan untuk membagi mesh menjadi dua submesh, grup mesh yang akan berubah sesuai dengan perubahan vertek kendali dan grup mesh yang tetap dan tidak diikutkan dalam proses deformasi.
Gambar 8. Matriks Laplacian Kubus
3
Maka koordinat diferensial masing – masing titik didapatkan sebagai berikut :
Gambar 9. Koordinat Diferensial
4.2. Uji dan Analisa Rekonstruksi -Coordinates Proses rekonstruksi koordinat diferensial membutuhkan penambahan minimal satu jangkar stasioner pada matriks L dan vektor . Gambar 10. Hasil rekonstruksi pada transformasi koordinat diferensial
Berikut ini adalah tabel penambahan satu, dua dan tiga vertek sebagai jangkar stasioner pada rekonstruksi koordinat diferensial tanpa transformasi.
Tabel 2. Data hasil rekonstruksi pada tx = -1 dan satu jangkar v7
Tabel 1. Data hasil rekonstruksi tanpa adanya transformasi
Tabel 3. Data hasil rekonstruksi pada tx = -1.5, ty = 1.5, tz = -1 dan satu jangkar v7
Tabel 4. Data hasil rekonstruksi pada tx = -1 dan dua jangkar v7 , v8
Tabel 5. Data hasil rekonstruksi pada tx = -1.5, ty = 1.5, tz = -1 dan dua jangkar v7 , v8
Terlihat tidak ada perbedaan hasil rekonstruksi mesh dengan koordinat asal. Pemilihan satu atau lebih vertek konstrain tidak mengubah hasil rekonstruksi permukaan mesh terhadap koordinat asal. 4.3. Uji dan Analisa Deformasi -Coordinates
Pada tabel 2 sampai table 5 terlihat perubahan koordinat Cartesian ketika koordinat diferensial yang terdeformasi direkonstruksi kembali. Soft constraint (warna hijau) ‘dipaksa’ untuk tidak banyak berubah ketika deformasi terjadi.
Pada uji berikut dilakukan proses translasi berturut – turut yang dilakukan pada koordinat diferensial dengan tx = -1 dan satu jangkar v7 (Gambar 10(a)), tx = -1.5, ty = -1.5, tz = -1 dan satu jangkar v7 (Gambar 10(b)), tx = -1 dan dua jangkar v7, v8 (Gambar 10(c)) serta tx = -1.5, ty = -1.5, tz = -1 dan dua jangkar v7, v8 (Gambar 10(d)).
4
untuk menghasilkan rekonstruksi yang baik. Gambar 10 menunjukkan hasil pemilihan jangkar berturut – turut dari kiri atas ke kanan bawah
4.4. Uji dan Analisa ROI pada mesh kompleks
4.6. Uji dan Analisa transformasi rotasi
Gambar 11. ROI diberikan disekitar hidung dan mulut. Vertek kendali pada hidung
Pada pengujian berikut diberikan proses pemilihan ROI pada suatu area mesh tertentu. Contoh gambar 11 menunjukkan pemilihan ROI disekitar hidung dan mulut, dan vertek kendali berada pada hidung. Diberikan translasi searah sumbu x dengan t x = 0.03 (Gambar 11(a)) dan tx = 0.06 (Gambar 11(b)). Terlihat hasil deformasi halus, dan pemberian jangkar (titik merah) membuat transisi antara submesh pengeditan dan submesh tetap menjadi halus.
Gambar 11. Transformasi seragam pada ROI (a) Koordinat Cartesian (b) Koordinat Diferensial
Pada gambar 11 transformasi seragam dilakukan pada seluruh ROI dan soft konstrain ditambahkan sebagai pembatas deformasi. Gambar 11(a) merupakan transformasi pada vertek koordinat Cartesian. Bentuk geometri berubah dan terdapat penempatan transformasi vertek yang tidak baik antara konstrain (titik merah) dan ROI. Sedangkan gambar 11(b) transformasi yang dihasilkan menjadi halus, karena transformasi dilakukan pada level detail mesh (yaitu koordinat diferensial).
4.5. Uji dan Analisa pemilihan Jangkar Stasioner Pada pembahasan ini akan diperlihatkan pemilihan jangkar stasioner dalam proses pengeditan. Pemilihan jangkar stasioner berikut berturut - turut dilakukan pada mesh silinder dengan jumlah vertek 930.
Gambar 12. Obyek dibengkokan dalam beberapa pilihan derajat.
Gambar 10. Hasil rekonstruksi dengan pemilihan jumlah jangkar yang berbeda
Percobaan dilakukan dengan pemilihan vertek pada bagian bawah sekeliling mesh. Pemilihan dimulai dari 30 vertek (3.225%), 60 vertek (6.45%), 90 vertek (9.67%), 120 vertek (12.9%), 150 vertek (16.13%) dan 180 vertek (19.35%). Dari penelitian, pemilihan vertek sebagai jangkar pada rentang 6% sampai 15%
Proses deformasi dapat dilakukan dengan mentransformasikan vertek kendali dengan variasi rotasi. Gambar 12 merupakan contoh proses transformasi rotasi (pada sumbu z) berturut – turut sebesar 15 derajat, 30 derajat, 45 derajat, 60 derajat, 75 derajat dan 90 derajat. Hasil rekonstruksi setelah
5
2. Proses rekonstruksi melibatkan sistem pemecahan persamaan linier dengan penambahan soft constraint pada matrik Laplacian dan penambahan posisi jangkar stationer pada sisi sebelah kanan sistem persamaan linier. 3. Proses pemilihan jangkar stationer dalam rekonstruksi akan menghasilkan mesh yang baik dengan perbandingan antara 6% - 15% terhadap jumlah vertek dalam ROI. 4. Proses rekonstruksi memakan waktu yang lama pada mesh dengan jumlah vertek yang besar, sehingga dibutuhkan perangkat komputasi yang cukup dan komputasi pemecahan sistem persamaan linear yang efisien
transformasi terlihat baik pada transformasi rotasi yang kecil. Semakin besar derajat rotasi yang diberikan maka semakin tidak sesuai yang diharapkan.
Gambar 13. Obyek dipilin mengikuti derajat putar tertentu
Variasi transformasi pada koordinat diferensial yang lain dapat dilihat pada gambar 13. Terlihat bahwa koordinat diferensial dapat ditransformasikan pada sumbu yang berbeda – beda. Pada contoh gambar tersebut obyek 3 dimensi seakan terpilin mengikuti arah putar tertentu
Untuk pengembangan pada penelitian selanjutnya disarankan hal – hal berikut : 1. Menggunakan transformasi yang tepat untuk menangani sudut rotasi yang besar, sehingga hasil deformasi menjadi lebih baik. 2. Proses transformasi bisa menggunakan transformasi non uniform pada tiap verteknya
4.7. Uji dan Analisa Waktu Rekonstruksi Peneliti menggunakan sistem operasi Windws 7 dengan spesifikasi komputer Pentium 4 centrino duo, 4 GB memori, 120 GB hard disk dan Nvidia GeForce sebagai penampil grafis dalam ujicobanya. Percobaan menggunakan perangkat lunak Matlab dengan bantuan library TAUCS sebagai pustaka untuk pemecahan sistem linier pada matriks sparse berukuran besar Berikut adalah tabel waktu faktorisasi rekonstruksi terhadap jumlah vertek.
DAFTAR PUSTAKA Babi , D., Klein, D. J., Lukovits, I., Nikoli , S. dan Trinajsti , N. (2002), "Resistance-Distance Matrix: A Computational Algorithm and Its Applications." Int. J. Quant. Chem. 60, pp. 161-176. Carmo, do M. P., (1976), “Differential Geometry of Curves and Surfaces”, Prentice-Hall Cvetkovi , D. M., Doob, M. dan Sachs, H. (1998) “Spectra of Graphs: Theory and Applications, 3rd rev. enl. Ed”. New York: Wiley. Fiedler, M. (1973), “Algebraic Connectivity of Graphs”, Czech Math. Journal, 23, pp. 298– 305. Godsil, C., dan Royle, G. (2001). “Algebraic Graph Theory”, Springer. Skiena, S. (1990), “Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica”, Reading, MA. Addison-Wesley Sorkine O.,Y. Lipman, D. Cohen-Or, M. Alexa, C.Rossl, H.-P. Seidel, (2004), “Laplacian surface editing”. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry processing, ACM Press, pp. 179–188. Sorkine O., (2006), “Differential representations for mesh processing”. Computer Graphics Forum 25, 4 (2006), pp. 789–807
dan
Tabel 6. Tabel waktu faktorisasi dan pemecahan linier
Tabel 6 menunjukkan perbandingan proses faktorisasi terhadap jumlah vertek dan facet yang ada pada mesh. Terlihat bahwa semakin besar jumlah vertek maka waktu komputasi juga bertambah lama 5. KESIMPULAN DAN PENGEMBANGAN Penelitian mengenai deformasi dengan metode Laplacian ini menghasilkan beberapa kesimpulan sebagai berikut : 1. Representasi koordinat diferensial dapat ditransformasikan untuk mendapatkan obyek tiga dimensi yang terubah.
6
