PENYEDERHANAAN MODEL 3D DENGAN METODE QUADRIC-BASED

PENYEDERHANAAN MODEL 3D DENGAN METODE QUADRIC-BASED Kuswara Setiawan Sekolah Tinggi Teknik Surabaya

ABSTRAK Pada era digital peranan citra tiga dimensi sangat penting dalam kalangan masyarakat. Berbagai bidang, seperti simulasi, medis, dan entertainment telah menggunakan citra tiga dimensi sebagai alat utama untuk menampilkan gambar dengan lebih realistis dan efisien. Dalam penggunaan sehari-hari, dibutuhkan suatu aplikasi untuk menyederhanakan citra tiga dimensi yang ada. Banyak perusahaan yang mendesain produk menggunakan sistem Computer-Aided Design (CAD), yang menghasilkan model tiga dimensi yang sangat kompleks dan mempunyai detil yang sangat halus, sementara banyak aplikasi yang sebenarnya hanya membutuhkan model dengan detil yang jauh lebih sedikit dari model orisinil. Akan tidak praktis dan membutuhkan banyak waktu dan biaya jika aplikasi-aplikasi ini menggunakan model orisinil. Oleh karena itu, dibutuhkan suatu algoritma penyederhanaan yang dapat menghasilkan model yang telah disederhanakan dengan kualitas yang cukup tinggi, tetapi hanya membutuhkan waktu yang relatif pendek dalam prosesnya. Makalah ini membahas sebuah algoritma penyederhanaan model tiga dimensi. Algoritma ini akan menyederhanakan sebuah model tiga dimensi yang terdiri dari kumpulan face dan vertex dengan cara menggabungkan pasangan vertex secara iteratif. Pasangan vertex yang akan digabung, dipilih berdasarkan sebuah metrik error quadric yang juga menentukan posisi vertex baru hasil penggabungan pasangan vertex tersebut. Dasar penggabungan pasangan vertex secara iteratif dan metrik error quadric akan dijelaskan dalam makalah ini beserta algoritmaalgoritma yang digunakan dan rumus-rumus matematika yang mendasarinya. Kata Kunci : Penyederhanaan Model 3D, Quadric-Based

PENDAHULUAN Penyederhanaan Model 3D adalah proses penyederhanaan sebuah model 3D yang kompleks dan memiliki detil yang rumit menjadi

model yang lebih sederhana dan memiliki ukuran yang lebih kecil. Proses penyederhanaan ini harus dapat menghasilkan model dengan kualitas yang cukup baik, dan hanya

SETIAWAN, PENYEDERHANAAN MODEL …

141

membutuhkan waktu yang relatif pendek. Proses harus berjalan secara otomatis tanpa campur tangan dari user. Satu-satunya input dari user hanya jumlah face dari model hasil penyederhanaan. Model 3D yang digunakan adalah model 3D yang terdiri dari poligon triangular (segitiga) dan hanya terdiri dari vertex dan face, tanpa properti lain, seperti warna atau tekstur. Latar Belakang Diperlukannya penyederhanaan model 3D karena perkembangan teknologi di bidang grafik yang pesat menyebabkan banyak alat seperti scanner laser, computer vision, dan alat-alat imaging di bidang kedokteran yang dapat menghasilkan model 3D yang sangat kompleks dengan detil yang sangat tinggi, sementara banyak aplikasi-aplikasi yang menggunakan model-model tersebut, seperti pada aplikasi simulasi, game komputer dan lain-lain hanya membutuhkan model dengan tingkat detil yang jauh lebih rendah. Karena itu, dibutuhkan sebuah penyederhanaan model 3D untuk menyederhanakan model yang sangat besar dan kompleks agar sesuai untuk aplikasinya dan untuk menghasilkan model yang lebih ekonomis. Penyederhanaan harus dapat menghasilkan model yang jauh lebih kecil dari model orisinil, tetapi masih mempunyai kualitas yang tinggi. Model Multiresolusi Model poligon tradisional terdiri dari sekumpulan vertex yang tetap dan sekumpulan face yang juga

142

tetap. Karena itu, model itu merepresentasikan suatu obyek dalam sebuah resolusi yang tetap. Sebuah resolusi yang tetap ini tidak akan cocok untuk semua konteks di mana model itu akan digunakan. Contohnya dapat dilihat pada Gambar 1.

Gambar 1. Model Naga dalam Tiga Cara Pandang

Tidak ada sebuah model dengan kualitas detil tertentu yang cocok untuk ketiga cara pandang untuk model naga ini. Cara pandang pertama membutuhkan model dengan detil tinggi, tetapi cara pandang ketiga mungkin hanya membutuhkan beberapa poligon untuk menghasilkan gambar yang sama. Sebuah model multiresolusi adalah sebuah representasi model dari sebuah obyek dengan tambahan - tambahan informasi sedemikian rupa sehingga dapat menghasilkan model dengan jangkauan resolusi yang cukup besar. Biaya untuk membuat sebuah penyederhanaan dengan tingkat detil tertentu harus kecil karena akan dibutuhkan banyak penyederhanaan yang berbeda. Kriteria Kualitas Penyederhanaan Tujuan utama dari penyederhanaan adalah untuk menghasilkan model yang semirip mungkin dengan yang asli. Untuk menentukan kualitas dari suatu penyederhanaan, dibutuhkan suatu cara untuk mengukur tingkat kesamaan suatu model dengan yang asli.

JURNAL INFORMATIKA & KOMPUTER NO. 3, JILID 8, 2003

Kriteria kesamaan suatu model yang paling akurat adalah kesamaan penampilan. Suatu model dikatakan sama dengan model lain bila setelah proses rendering, kedua model itu mempunyai penampilan yang sama. Cara lain untuk mengukur kesamaan model adalah dengan mengukur kesamaan geometris. Walaupun kesamaan penampilan merupakan kriteria yang paling akurat, tetapi dalam prakteknya sangat sulit untuk diimplementasikan, sedangkan kesamaan geometris dapat digunakan untuk pengganti kesamaan penampilan. Bila dua buah model mirip secara geometris, kedua model itu juga akan mirip penampilannya. Metode Penyederhanaan yang Ada Metode-metode penyederhanaan model 3D yang ada sampai saat ini antara lain adalah metode penyederhanaan manual, di mana seorang desainer melakukan penyederhanaan model secara manual. Metode lainnya adalah metode polihedral refinement, di mana dibuat sebuah penyederhanaan awal dengan detil yang paling sederhana, kemudian diperbaiki terus – menerus hingga tingkat penyederhanaan yang diinginkan tercapai. Salah satu metode yang paling banyak digunakan adalah metode vertex clustering, di mana model dibagi menjadi bagian – bagian yang sama besar, kemudian semua vertex dalam bagian yang sama digabung menjadi satu vertex. Contoh metode ini dapat dilihat pada Gambar 2.

Sebelum

Sesudah

Gambar 2. Contoh Vertex Clustering Dalam 2D

Metode vertex clustering ini mudah diimplementasikan dan prosesnya sangat cepat, tetapi hasilnya mempunyai kualitas yang rendah. Metode lainnya adalah metode penggabungan daerah, yaitu membagi model menjadi beberapa daerah, menyederhanakan daerah – daerah tersebut secara terpisah, kemudian menggabungkan daerah – daerah tersebut. Metode ini sulit untuk diimplementasikan dan tidak dapat menghasilkan model yang bagus. Metode lainnya adalah metode vertex decimation, di mana sebuah vertex dihapus, semua face yang berbatasan dengan vertex tersebut dihapus, kemudian daerah tersebut diretriangulasi. Proses ini diulang terus – menerus hingga tercapai hasil yang diinginkan. Contoh metode ini dapat dilihat pada Gambar 3.


143

Sebelum

Sesudah

Gambar 3. Contoh Vertex Decimation

Metode vertex decimation ini dapat diperbaiki menjadi metode kontraksi edge secara iteratif. Metode ini menggabungkan sepasang vertex yang membentuk edge dan face – face yang menjadi rusak. Hasil penyederhanaan pada Gambar 3 dapat diperoleh dengan kontraksi edge paling bawah dan kedua face yang mengapitnya. Metode ini cukup sederhana, hasil yang didapat mempunyai kualitas yang cukup tinggi, dan relatif mudah diimplementasikan. Selain itu metode ini juga dapat menghasilkan hirarki vertex yang berguna untuk membuat model multiresolusi.

1. Pilih sekumpulan pasangan kandidat vertex yang akan dikontraksi (vi,vj) 2. Beri nilai biaya kontraksi untuk setiap kandidat pasangan. 3. Tempatkan semua kandidat dalam heap, disortir dengan pasangan yang mempunyai biaya paling kecil di posisi paling atas. 4. Ulangi sampai penyederhanaan yang diinginkan tercapai. • Hapus pasangan paling atas dari heap(vi,vj). • Gabungkan pasangan vertex ini. • Update biaya semua pasangan kandidat termasuk vi. Pemilihan Pasangan Kandidat Untuk memilih kandidat pasangan yang akan dikontraksi, dipilih semua pasangan vertex yang membentuk edge, seperti dapat dilihat pada Gambar 4.

PENYEDERHANAAN QUADRIC-BASED Pada metode ini, dibutuhkan tiga array untuk menyimpan data. Yang pertama adalah array vertex untuk menyimpan semua vertex pada model, array face untuk menyimpan semua face pada model, dan array heap untuk menyimpan pasangan vertex yang akan dikontraksi, posisi hasil kontraksi, dan biaya kontraksi pasangan tersebut. Secara garis besar, proses yang dilakukan oleh algoritma ini adalah:

144

Gambar 4. Contoh Edge

Pada model yang ditunjukkan pada Gambar 4, dipilih semua pasangan vertex yang membentuk edge, yang ditunjukkan oleh garis yang menghubungkan dua vertex, contohnya adalah v dan v1, v dan v2, v1 dan v2, dan lain-lain.


Perhitungan Biaya Kontraksi Salah satu langkah yang paling penting dalam metode ini adalah penghitungan biaya kontraksi. Karena salah satu tujuan penyederhanaan adalah menghasilkan model yang semirip mungkin dengan yang asli, maka biaya sebuah kontraksi harus dapat merefleksikan seberapa banyak sebuah kontraksi mengubah sebuah model. Untuk menghitung biaya kontraksi ini, dibutuhkan suatu metrik error yang dapat mengukur seberapa besar perbedaan yang terjadi pada model setelah terjadi pemindahan suatu vertex ke tempat lain yang diakibatkan oleh proses kontraksi. Metrik error pada suatu vertex ini didefinisikan sebagai kuadrat jarak dari vertex itu ke semua planar yang berbatasan dengannya. Pasangan vertex yang akan dihapus lebih dulu dipilih berdasarkan besarnya nilai error posisi target. Pasangan vertex yang mempunyai nilai error yang paling kecil akan dikontraksi lebih dulu. Pemilihan posisi target juga berdasarkan pada posisi target yang memiliki nilai error paling kecil, seperti dapat dilihat pada Gambar 5.

Gambar 5. Contoh Pemilihan Posisi Target Ideal Dalam 2D

Pada Gambar 5, ditunjukkan posisi ideal untuk kontraksi sepasang vertex (vi, vj) dalam dua dimensi. Posisi target ideal adalah posisi target yang memiliki error paling kecil terhadap semua planar yang membentuk vi dan vj. Posisi ini ditunjukkan oleh vertex v. Elips – elips di sekeliling v menunjukkan titik – titik yang mempunyai nilai error yang sama. Dalam tiga dimensi, isosurface seperti ini disebut permukaan quadric, karena itu metrik ini disebut metrik error quadric. Metrik Error Quadric Telah disebutkan bahwa error suatu vertex didefinisikan sebagai jumlah kuadrat jarak antara vertex tersebut dengan semua planar yang membentuk vertex tersebut. Persamaan standar untuk planar adalah ax+by+cz+d=0 atau bisa dituliskan sebagai nTv+d=0. Kuadrat jarak antara suatu vertex dengan suatu planar adalah D2(v)=(nTv+d)2. Persamaan ini bisa diturunkan menjadi D2(v)=(vT(nnT)v+2(dn)Tv+d2), di mana nnT adalah sebuah matriks:

 a 2 ab ac    nn T =  ab b 2 bc   ac bc c 2   

sehingga sebuah quadric Q untuk setiap planar dapat didefinisikan sebagai Q=(A,b,c), dengan A adalah matriks 3x3 nnT, b adalah sebuah vektor-3 dn, dan c adalah skalar d. Ini adalah quadric fundamental untuk setiap planar. Quadric untuk setiap vertex merupakan jumlah quadric


145

fundamental dari semua planar yang membentuk vertex tersebut. Nilai error suatu vertex v dapat dihitung dengan memasukkan nilai v ke dalam persamaan awal Q(v)=vTAv+2bv+c. Setelah dua buah vertex dikontraksi menjadi satu, quadric vertex hasil gabungan kedua vertex tersebut merupakan jumlah quadric kedua vertex tersebut, dan biaya kontraksi (vi,vj)v adalah Q(v)=Qi(v)+ Qj(v). Efisiensi dari metrik error quadric ini merupakan keuntungan utamanya. Setiap vertex hanya mempunyai satu quadric, dan hanya inilah memori yang dibutuhkan oleh metrik error. Hanya dibutuhkan 10 koefisien untuk menyimpan matriks A 3x3 yang simetris, vektor-3 b, dan skalar c. Biaya untuk mengevaluasi metrik ini guna menentukan error suatu kontraksi juga kecil. Selain itu metrik error ini juga dapat menghasilkan penyederhanaan yang berkualitas tinggi. Metrik error ini menghitung error suatu model

(a)

berdasarkan perbedaan model tersebut dengan model orisinil. Ini menjaga kualitas model agar tidak melenceng terlalu jauh dari model orisinil.

Quadric-Based Extended Metode quadric-based ini masih mempunyai beberapa kelemahan yang dapat diperbaiki dengan sedikit perubahan, selain itu kualitas hasil metode ini dapat ditingkatkan dengan penambahan – penambahan tertentu. Pemilihan Kandidat Non-Edge Pemilihan semua pasangan vertex yang membentuk edge sebagai kandidat pasangan untuk dikontraksi merupakan pilihan yang sederhana dan efektif, tetapi terkadang akan diperoleh hasil yang lebih baik dengan menambahkan pasangan vertex yang tidak membentuk edge, terutama bila model terdiri dari lebih dari satu objek yang terpisah.

(b)

(c)

Gambar 6. Pasangan Kandidat Edge dan Non-Edge

Gambar 6 menunjukkan bahwa pada model yang terdiri dari lebih dari satu objek (gambar a), penyederhanaan yang didapat akan lebih baik bila pasangan kandidat selain edge juga dipilih untuk dikontraksi (gambar c), daripada

146

hanya pasangan yang membentuk edge (gambar b). Pada pemilihan pasangan kandidat yang tidak dibatasi edge ini, semua pasangan vertex, baik berupa edge ataupun tidak, akan dipilih sebagai kandidat pasangan bila


memenuhi kriteria tertentu. Kriteria yang paling umum adalah bila pasangan tersebut hanya dipisahkan oleh jarak threshold tertentu. Garis besar pemilihan pasangan vertex (vi,vj) dengan metode ini adalah semua pasangan vertex dipilih sebagai kandidat bila memenuhi kondisi: 1. (vi,vj) adalah sebuah edge, atau 2. (vi,vj) bukan sebuah edge dan || vi–vj||<τ di mana τ adalah sebuah parameter threshold yang dimasukkan oleh user, tergantung dari kepadatan model dan kualitas penyederhanaan yang diinginkan. Normalisasi Metrik Quadric Dalam metode awal, perhitungan quadric dilakukan dengan mengasumsikan setiap face sebagai bidang planar. Ini dapat mengakibatkan kesalahan dalam penghitungan nilai quadric. Semua face akan dianggap sebagai bidang planar dengan luas yang sama, sehingga nilai quadric akan sangat tergantung pada tesselasi permukaan model.

(a)

(b)

Gambar 7. Perbedaan Tesselasi dari Bidang Planar yang Sama

Gambar 7 menunjukkan dua tesselasi yang berbeda dari sebuah bidang datar yang sama. Nilai

quadric secara keseluruhan (bila semua vertex dikontraksi menjadi satu vertex) pada gambar a menunjukkan nilai 9Q, sementara nilai quadric untuk gambar b menunjukkan nilai 18Q. Ini jelas – jelas merupakan kesalahan karena quadric dari dua buah bidang datar yang sama luas seharusnya menunjukkan nilai yang sama besar. Untuk mengatasi masalah ini, pada waktu penghitungan quadric fundamental setiap face dapat ditambahkan suatu nilai beban yaitu sepertiga luas face tersebut. Ini mengakibatkan quadric juga akan memperhitungkan luas area suatu face, dan bukannya mengasumsikan setiap face sebagai bidang planar. Nilai quadric yang telah dijelaskan sebelumnya dapat diubah menjadi Q=(wA,wb,wc), di mana w adalah nilai beban yang berupa sepertiga luas face yang sedang dihitung nilai quadric-nya. Aturan Penempatan Optimal Pemilihan salah satu dari pasangan vertex yang dikontraksi sebagai posisi target setelah kontraksi adalah sebuah cara yang sederhana dan dapat menghasilkan model yang relatif cukup bagus, tetapi sebenarnya posisi tujuan yang paling ideal adalah titik di mana error setelah kontraksi paling kecil, dan titik tersebut tidak berada pada salah satu dari pasangan yang akan dikontraksi. Pemilihan salah satu dari pasangan vertex sebagai posisi tujuan disebut penempatan subset, sedangkan pemilihan titik yang mempunyai error paling kecil sebagai


147

posisi tujuan disebut penempatan optimal. Minimum dari Q(v) adalah bila dQ/dx=dQ/dy=dQ/dz=0. Diketahui turunan dari persamaan Q(v) adalah ∇ Q ( v ) = 2 Av + 2b . Untuk ∇Q(v) minimum, posisi optimalnya adalah v = -A-1b, dan error-nya adalah Q ( v ) = b T v + c = − b T A − 1b + c . Secara garis besar, langkah – langkah untuk penempatan optimal ini adalah: 1. Coba menghitung v menggunakan v = -A-1b. 2. Jika A singular, cari posisi optimal di sepanjang edge (vi,vj). 3. Jika tidak , pilih yang terbaik antara vi dan vj (gunakan penempatan subset). Discontinuities dan Constraints Diskontinyu dari sebuah model, seperti lipatan, perbatasan terbuka, dan perbatasan antara daerah – daerah dengan warna yang berbeda, sering merupakan fitur yang paling signifikan secara visual. Karena itu, diskontinyu ini harus dipertahankan untuk menghasilkan penyederhanaan yang berkualitas. Diskontinyu pada model yang berbentuk benda padat telah dapat dipertahankan oleh metrik error tanpa membutuhkan perbaikan apapun. Contohnya pada pinggiran yang tajam pada sebuah kubus. Sebuah titik pada pinggiran sebuah kubus mempunyai planar yang mempengaruhinya dari dua face pada dua sisi kubus yang berbeda. Karena dua sisi kubus yang berbeda ini membentuk sudut siku – siku, maka biaya untuk memindah titik itu di sepanjang 148

pinggiran kubus tersebut akan jauh lebih kecil daripada memindahkannya menjauhi pinggiran. Karena itu, metode ini akan mempertahankan bentuk pinggiran ini. Sebaliknya, pada model yang merupakan permukaan 3D, seperti pada model permukaan suatu daerah, akan terdapat perbatasan terbuka pada pinggir model. Untuk model seperti ini, algoritma quadricbased dasar akan mengabaikan perbatasan ini dan memungkinkan terjadinya kontraksi yang menyebabkan perbatasan ini menjadi rusak. Salah satu cara yang sederhana untuk mengatasi masalah ini adalah dengan memberi flag untuk semua edge perbatasan pada waktu inisialisasi quadric. Kemudian untuk setiap face yang berbatasan dengan edge perbatasan tersebut ditambahkan sebuah planar pada edge perbatasan itu yang tegak lurus dengan face tersebut. Planar yang tegak lurus ini disebut planar constraint, seperti dapat dilihat pada Gambar 8.

Gambar 8. Penambahan Planar Constraint

Quadric untuk planar ini dapat dihitung seperti pada planar face yang lain. Untuk membuat constraint dari quadric ini, planar ini harus diberi nilai quadric dengan faktor penalti yang besar, dan ditambahkan ke dalam quadric untuk setiap vertex


yang membentuk edge perbatasan pada waktu inisialisasi.

(a) Model Orisinil

(b)Tanpa Constraint

(c)Dengan Constraint

Gambar 9. Penyederhanaan Sebuah Peta dengan dan tanpa Constraint

Pengecekan Konsistensi Metrik error quadric adalah alat untuk memilih kontraksi yang akan dilakukan dan lokasi untuk meletakkan vertex yang dihasilkan. Tetapi, sebuah kontraksi berpotensi menghasilkan inkonsistensi atau degenerasi mesh yang tidak diharapkan. Masalah ini dapat diatasi dengan menerapkan pengecekan konsistensi pada sebuah kontraksi. Jika kontraksi tersebut gagal dalam salah satu pengecekan tersebut, dapat ditambahkan faktor penalti yang besar (seperti pada constraint perbatasan), atau kontraksi itu dibatalkan sama sekali.

Pengecekan konsistensi yang paling umum berkaitan dengan masalah mesh fold-over. Gambar 10 menunjukkan bahwa pada posisi v, mesh akan terlipat menutupi face yang lain. Cara untuk mengatasi masalah ini adalah dengan memperhitungkan bahwa untuk semua face di sekeliling vi, tidak termasuk face yang dibagi bersama vj, terdapat sebuah edge yang berlawanan dengan vi. Jika ditempatkan sebuah planar tegak lurus dengan face tersebut melalui edge-nya, posisi v harus berada pada sisi yang sama dari planar dengan vertex vi. Kriteria yang sama berlaku untuk face – face yang mengelilingi vj. Gambar 11 menggambarkan planar – planar ini, anak panah menunjukkan daerah di mana v harus berada.

(a) Daerah di Sekeliling vi

(b) Daerah di Sekeliling vj

Gambar 11. Pengecekan Konsistensi dengan Planar di Sekeliling vi dan vj

ANALISA

(Sebelum)

(Sesudah)

Gambar 10. Kontraksi Edge yang Menyebabkan Mesh Fold-Over

Salah satu tujuan utama dari algoritma ini adalah untuk menghasilkan sebuah algoritma penyederhanaan yang efisien, baik dalam waktu yang diperlukan ataupun memori. Untuk analisa berikut, diasumsikan terdapat sebuah model M yang


149

mempunyai r vertex dan n face. Penyederhanaan akan menghasilkan model M’ yang mempunyai m face, dengan p adalah jumlah pasangan kandidat yang dipilih dalam inisialisasi. Selain itu jumlah face yang akan dihapus dalam sebuah iterasi dianggap sebanyak k, dan sebuah vertex dianggap mempunyai g face. Efisiensi Waktu Dimulai dari fase inisialisasi, penghitungan seluruh quadric fundamental membutuhkan waktu O(n). Memilih dan mengevaluasi

pasangan kandidat juga membutuhkan waktu O(n). Menempatkan semua kandidat dalam heap dan mensortirnya berdasarkan biaya membutuhkan waktu O(n log n). Jadi, kompleksitas total dari inisialisasi adalah O(n log n). Pada fase penyederhanaan, dalam sebuah iterasi i, proses yang dilakukan adalah memilih pasangan dengan biaya minimum, mengkontraksinya, dan meng-update lingkungan pasangan tersebut. Tabel 1 menunjukkan biaya untuk operasi – operasi tersebut.

Tabel 1. Kompleksitas Waktu untuk Fase Penyederhanaan

Kompleksitas Waktu Operasi

Iterasi i

Total

Pilih pasangan

O(log(n-ki))

O(n log n – m log m)

Kontraksi pasangan Update lingkungan TOTAL :

O(g)

O(n – m)

O(g log(n – ki))


O(log(n – ki)


Karena diasumsikan bahwa g adalah konstan, biaya untuk sebuah proses iterasi adalah O(log(n – ki)). Jika dijumlahkan untuk semua iterasi, kompleksitas total untuk fase penyederhanaan adalah : log n + log(n–k) + log(n–2k) +...+ log m, Karena k juga sebuah konstanta, maka : log n + log(n-1) + log(n–2) +...+ log m Yang merupakan :

log

150

n! = log n!− log m!= O(n log n − m log m) m!

Dari dua fase ini, dapat dihitung kompleksitas keseluruhan dari algoritma ini, yaitu O(n log n). Penggunaan Memori Selain waktu, konsumsi memori juga merupakan aspek penting dari efisiensi, terutama untuk model yang besar dengan jumlah face yang sangat banyak. Tabel 2 menunjukkan penggunaan memori pada algoritma ini, dengan diasumsikan n = 2r dan p = 3r.


Tabel 2. Konsumsi Memori

Data Vertex

Posisi Quadric

Disimpan Sebagai 3r real 10r real

Face

Vertex

Subtotal 3n integer

104r 12n

Heap

vi, vj Target v Biaya (v)

Subtotal 2p integer 1p boolean 1p real

8p 1p 8p

Subtotal TOTAL Kualitas Hasil Untuk menunjukkan kualitas hasil penyederhanaan dengan metode quadric-based ini, gambar berikut menunjukkan model seekor sapi dalam bentuk wireframe. Dengan 5804 face, model ini mempunyai banyak fitur – fitur yang digambarkan dengan baik dengan jumlah poligon yang relatif sedikit. Kepadatan poligon hanya terlihat pada bagian kepala dan kaki. Karena itu, jika model ini disederhanakan, maka harus ada fitur – fitur yang dihilangkan. Pada 2000 face (35% dari model orisinil), model ini masih terlihat cukup baik dan bentuk keseluruhan

Ukuran (byte) 24r 80r

24r

51r 179r

model tidak berubah. Semua fitur utama seperti kaki, kepala, tanduk, dan ekor masih terlihat jelas. Jika dibandingkan dengan Gambar (a), distribusi poligon pada model juga terlihat lebih seragam. Penyederhanaan dengan 578 face (10% dari orisinil) juga masih dapat dikenali sebagai sapi, walaupun fitur – fitur penting telah disederhanakan lebih lanjut. Proses penyederhanaan ini dilanjutkan dalam penyederhanaan dengan 100 face. Bagian kepala hanya digambarkan dengan sebuah poligon, dan kaki – kaki telah kehilangan bentuknya.


151

(a) Model Awal dengan 5804 face

(b) Penyederhanaan dengan 2000 face

(c) Penyederhanaan dengan 578 face

(d) Penyederhanaan dengan 100 face

Gambar 12. Penyederhanaan Model Sapi

•

•

•

152

PENUTUP Ketidakmampuan metode ini untuk menyederhanakan properti model selain vertex dan face merupakan kekurangan yang sangat besar. Properti warna dan tekstur pada model 3D merupakan fitur yang sangat vital dan harus dipertahan-kan. Algoritma ini tidak memiliki metode eksplisit untuk menangani input model yang mempunyai noise. Walaupun secara teori algoritma ini dapat menyederhanakan model yang sangat besar, yang

•

memiliki ratusan ribu atau bahkan jutaan face, pada kenyataannya algoritma ini tidak bisa melakukannya karena keterbatasan memori dan karena waktu yang dibutuhkan akan terlalu lama yang disebabkan karena algoritma ini hanya melakukan satu kontraksi untuk setiap iterasi. Untuk aplikasi – aplikasi rendering, kesamaan penampilan adalah tujuan utama. Untuk aplikasi – aplikasi ini, akan sangat membantu bila ada sebuah metrik appearance –


•

•

based untuk membandingkan kesamaan visual dua model. Performa metode – metode penyederhanaan yang ada saat ini (termasuk algoritma quadric – based ini) akan menurun drastis pada penyederhanaan dengan level yang rendah. Salah satu cara yang paling menjanjikan dalam memperbaiki kualitas penyederhanaan yang di-hasilkan secara otomatis adalah dengan memisahkan fase analisa dan fase sintesis pada proses penyederhanaan.

DAFTAR PUSTAKA Foley, James D., Andries van Dam, Steven K. Feiner, dan John F. Hughes, 1990, Computer Graphics: Principles and Practice, Second Edition. AddisonWesley Publishing Company.


Garland, Michael. Mei 1999. Quadric-Based Polygonal Surface Simplification, Ph.D Thesis. Carnegie Mellon University. Garland, Michael., dan Paul Heckbert. 1997. Surface Simplification Using Quadric Error Metrics, SIGGRAPH. Setiawan, Kuswara., Oswald Baskoro Satyoadi, Tjwanda Putra Gunawan. 2001. Aljabar Linier & Matriks: Diktat Kuliah. Sekolah Tinggi Teknik Surabaya.

153

PENYEDERHANAAN MODEL 3D DENGAN METODE QUADRIC-BASED

Recommend Documents