REKONSTRUKSI PERMUKAAN TIGA DIMENSI AREA POINT CLOUDS DENGAN ALGORITMA TRIANGULASI DELAUNAY Taufiqurrahman1), Mochammad Hariadi, ST., M.Sc., Ph.D.2) 1)Pasca Sarjana JCM (Game Technology) Jurusan Teknik Elektro ITS, Surabaya, email:
[email protected] 2)Jurusan Teknik Elektro ITS, Surabaya, email:
[email protected] Abstrak Seiring adanya perkembangan grafika pada beberapa produk seperti game, iklan dan animasi telah banyak menggunakan model tiga dimensi – 3D. Sehingga diperlukan suatu pemroses yang mampu mengidentifikasi dan mempresentasikan menjadi tiga dimensi dengan cepat dan mudah. Pada penelitian ini akan melakukan suatu cara dalam merekonstruksi objek dalam tiga dimensi yang berasal dari kumpulan informasi point clouds dengan menggunakan beberapa pendekatan algoritma sistem triangulasi. Metode ini melakukan rekonstruksi permukaan objek dengan beberapa cara pendekatan diantaranya Voronoi Diagram dan Delaunay Triangulation. Proses dilakukan secara berulang untuk semua point cloud hingga didapatkan semua bagian bidang yang membentuk objek 3D. Hasil dari penelitian ini, proses rekonstruksi diperoleh dengan dua cara yaitu Delaunay2D dan Delaunya3D. Keduanya mendapatkan hasil yang berbeda ketika diujicobakan pada model yang sama. Triangulasi Delaunay2D dilakukan pada bidang planar sedangkan pada Delaunay3D pada bidang paraboloid. Kesimpulan pertama didapatkan yaitu model 3D yang diujicobakan sebaiknya model yang bersifat seragam dan permukaan terbuka. Kedua, kegagalan rekonstruksi permukaan dengan Delaunay3D disebabkan tidak ada proses minimalisasi sudut ketika proses triangulasi. Ketiga, vertek yang bersifat simetri dengan vertel yang akan diproses tidak bisa dilakukan triangulasi. Kata Kunci: : Rekonstruksi Permukaan, Triangulasi, Delaunay 1.
PENDAHULUAN
Kebutuhan akan suatu proses rekonstruksi objek menjadi hal yang menarik untuk dibahas di dalam dunia komputasi geometri [1][4]. Dualitas geometri antara poligon Delaunay dan Voronoi dapat digunakan untuk mengimplementasikan suatu pendekatan untuk rekonstruksi objek [2]. Perencanaan metode rekonstruksi permukaan objek dua dimensi dengan memanfaatkan metode yang sudah ada, bisa menjadikan suatu rekayasa alternatif yang nantinya berguna dalam membangun objek gambar dua atau tiga dimensi. Hal ini diharapkan bisa menjadikan angin segar buat dunia peranimasian khususnya. Di dalam paper ini akan membahas suatu generasi rekonstruksi permukaan. Pendekatan metode yang nantinya digunakan adalah Diagram Voronoi dan Delaunay Triangulasi. [3][4][5]. 1.1.
Latar Belakang
Di dalam penelitian ini, mengusulkan suatu gabungan penggunaan sistem rekonstruksi permukaan tiga dimensi. Dimana perencanaan yang akan dilakukan adalah melakukan pendekatan sistem triangulasi. Dengan menggunakan metode delaunay triangulasi dan diagram voronoi diharapkan informasi dari sekumpulan point set atau point clouds bisa menjadi reka bentuk permukaan tiga dimensi [9][10][11]. Sehingga dengan menggabungkan hal-hal tersebut diharapkan sistem ini dapat menjadi sistem yang bisa menghasilkan objek model dengan output permukaan yang lebih baik.
2.
TINJAUAN PUSTAKA DAN DASAR TEORI
Pada penelitian ini akan dikembangkan suatu cara dalam merekonstruksi bidang permukaan pada area bidang tiga dimensi. Dengan metode dari algoritma Delaunay Triangulasi serta dilakukannya aproksimasi dari dualitas voronoi dengan delaunay diharapkan sebagai rekonstruksi permukaan bidang tiga dimensi. 2.1.
Fundamental Geometri pada Point Clouds
Didalam pemodelan permukaan 3D, titik-titik awan (point clouds) dipresentasikan sebagai sekumpulan triplet (x,y,z) dimana . Triplet tersebut disebut vertek di dalam pemodelan tiga dimensi. Permukaan 3D dipresentasikan sebagai sekumpulan segitiga , dimana masing-masing , dan adalah koordinat 3D (x,y,z). Satu segitiga sebagai bidang permukaan atau face. Setiap sisi segitiga dapat saling terkoneksi satu sama lain. Untuk membentuk permukaan yang lebih luas lagi sehingga diasumsikan . Polygon dengan empat vertek disebut sebagai persegi atau quad. Dua segitiga dapat digabungkan untuk membuat quad di salah satu sisi kedua segitiga.
Gambar 2.1 (a) Vertek, (b) Segitiga, (c) Tetrahedron 3D
1
2.2.
Clustering
3.1.
Pada penelitian ini, point clouds memiliki vertek mulai kisaran 400 hingga 1.4 juta vertek. Kebanyakan algoritma rekonstruksi permukaan dapat melakukan komputasi tersebut hanya kurang dari 1000 point dan diselesaikan dengan waktu yang cukup lama. Dengan begitu diperlukan suatu proses penyederhanaan pada model. Salah satu cara penyederhanaan tersebut adalah menggunakan metode pengelompokan (clustering method) (Pauly, Gross, & Kobbelt, 2002). 2.3.
Pengertian triangulasi adalah suatu metode pembangkitan jalinan segitiga – triangulasi pada pola reka bentuk mesh. Dimana jalinan tersebut terdapat sekumpulan titik-titik yang membentuk pola. Untuk menggunakan mesh yang menerapkan triangulasi langkah pertama yang dilakukan adalah mengikuti aturan dan struktur vertek. Pada disipilin ilmu komputer grafik pada umumnya teknik geometri sangat bersesuaian dengan triangulasi. Istilah Triangulation T dari dua dimensi ataupun dengan ordo lebih Rn dimana n adalah dimensi ordo[3]. Dalam kasus ini adalah dua dimensi maka :
Model Permukaan 3D
Permukaan tiga dimensi dibentuk oleh beberapa titik dengan beberapa metode. Tiga titik dihubungkan dengan tiga garis (edge) yang berturut – turut sehingga membentuk sebuah segitiga (triangle). Pada model yang kompleks jumlah triangle terdiri dari ribuan, sehingga membentuk sebuah model yang halus (Sorkine, 2006), (Sorkine dan Alexa, 2007). Beberapa model dibentuk dengan beberapa cara seperti Delaunay Triangulation versi Constrained Delaunay Triangulation untuk proses lebih lanjut dari optimasi terhadap waktu keputusan dalam tautan (de Aguiar, Stoll, Theobalt, Ahmed, Seidel, & Thrun, 2008).
Setiap bagian dari triangulasi saling terkait oleh salah satu bagian triangulasi yang lain atau tidak sama sekali.
Setiap batas di sekumpulan pada Rn saling berpotongan hanya terbatas pada bagian triangulasi di T .
Dari triangulasi yaitu setiap P bagian dari triangulasi dari n point. Dan semua triangulasi terdiri dari 2n-2-k segitiga serta 3n-3-k edges (tepian). Dengan asumsi n adalah jumlah titik (point) di P , dan k adalah jumlah titik (point) pada area convex hull di P [6][7]. 3.2.
Perancangan Triangulasi Delaunay
Triangulasi Delaunay Del(P) pada sekumpulan vertek P = {p1, p2, ... ,pn} dikenalkan oleh Delaunay pada tahun 1934 yang sangat berguna ketika ada pekerjaan yang berkaitan dengan mesh. Keuntungan utama dari triangulasi delaunay ini adalah memaksimalkan dengan membuat sudut minimum diantara semua triangulasi yang terbentuk oleh sekumpulan vertek tersebut. Dengan adanya keuntungan tersebut memunculkan suatu kriteria dalam kualitas mesh.
Gambar 2.2 Point Clouds dan Triangulasi Nefertiti
3.
Definisi Triangulasi
METODE PENELITIAN
Pada pembahasan penelitian, secara garis besar langkah-langkah dalam tahap penelitian ini dimulai dari proses pengumpulan referensi tentang riset yang akan dilakukan. Kemudian, perancangan data masukan objek 3 dimensi hingga proses bangun kembali objek 3 dimensi berdasarkan kajian-kajian metode berikut ini.
Literatur
Studi Literatur
Representasi Objek 3D
REKONSTRUKSI PERMUKAAN TIGA DIMENSI
Model 3D Titik-titik Awan
Gambar 3.2 Traingulasi Delaunay 2D dan 3D
Start Tidak
Ya
QHull
Delaunay dan Voronoi
Kriteria Detri ?
Tidak
Keluaran
Ya
Model 3D FINAL
Perancangan Diagram Voronoi
Sebagai contoh misalnya terdapat sekumpulan set point P = {p1, p2, ... ,pn} pada bidang Rn pada kasus ini adalah dua dimensi. Maka voronoi diagram V atau (P) adalah bagian dari Rn ke dalam n daerah polyhedral. Setiap daerah diketahui sebagai sel voronoi yang didenotasikan vo(p) saling melingkupi dan berhubungan satu dengan lainnya pada tiap n point. Masing-masing point yang berdekatan tersebut ditarik garis tegak lurus.
Optional Test
Metode Traingulasi
3.3.
Node ? Threshold ? Radius ?
Clustering
Finish
Gambar 3.1 Blok Diagram Penelitian
2
Lebih tepatnya dengan vo(p) menjadi sel voronoi setiap point P dan set S dari setiap point sebagai berikut :
lingkaran. Sehingga belum termasuk kriteria delaunay. B. Notasi e’ merupakan delaunay karena berpotongan pada satu lingkaran akan tetapi kriteria delaunay menyatakan minimal 3 verek untuk bisa triangulasi. Maka masih belum dinyatakan delaunay.
dimana dist adalah fungsi euclidian distance
C. Pada triangulasi t sudah terbentuk dan berpotongan pada satu lingkaran. Akan tetapi di dalam lingkaran tersebut terdapat vertek v yang berdiri bebas. Sehingga kondisi tersebut belum dikatakan delaunay. D. Letak triangulasi t sudah terhubung dan berpotongan pada satu lingkaran dan terdapat vertek v yang berada diluar lingkaran. Dengan kondisi demikian triangulasi t termasuk kriteria delaunay dan dinyatakan triangulasi delaunay.
Gambar 3.3 Voronoi dua dimensi dengan 5 vertek
3.4.
Kriteria Triangulasi Delaunay
Untuk triangulasi T dari P untuk menjadi Delaunay terdapat kriteria delaunay yaitu properti lingkaran kosong vertek. Dikatakan begitu jika beberapa vertek saling terhubung pada satu lingkaran tertentu dalam satu dimensi jari-jari yang sama. Sehingga kriteria tersebut bisa digambarkan sebagai berikut : 1. 2. 3.
Tidak diijinkan ada vertek di dalam lingkran tersebut. Minimal terbentuk triangulasi dalam satu lingkaran. Meskipun terbentuk triangulasi tetapi ada vertek independen di dalam lingkaran maka masih belum dikategorikan delaunay
Gambar 3.5 Triangulasi Delaunay pada bidangdengan sekumpulan lingkaran yang menyatakan kriteri delaunay
3.5.
Dualitas Delaunay dan Voronoi
Setelah membahas satu-persatu antara diagram voronoi dan triangulasi delauanay. Berikutnya memperinci penjelasan hubungan antara keduanya. Setelah dijelaskan tentang voronoi verteks yaitu inteseksi titik pada tepian voronoi. Berperan pada sentral di dalam aturan triangulasi delaunay. Berdasarkan pada gambar 3.6 pusat lingkaran triangulasi terpusat di vertek voronoi pada vertek v. Kemudian vertek sesungguhnya p,q,r saling berpotongan pada lingkaran yang terbentuk secara triangulasi. Kejadian seperti itu yang menjadi dasar triangulasi delaunay.
Kriteria tersebut bisa di deskripsikan pada gambar 3.4 yang memvalidasikan kriteria triangulasi delaunay.
Gambar 3.4 Triangulasi Delaunay menurut kriteria delaunay pada gambar abjad D
Pembahasan pada gambar 3.4 pada setiap abjad : A. Terdapat dua vertek yang terhubung pada nota e pada lingkaran tapi terdapat dua vertek lain di dalam lingkaran yang tidak berpotongan dengan
Gambar 3.6 Dualitas voronoi dan delaunay
3
Secara spesifik, diagram voronoi V atau (V) pada R2 dan triangulasi Delaunay Del(V) pada sekumpulan vertek V adalah dual satu sama lainnya pada teori grafik.
2.
4.2. 3.6.
Triangulasi Delaunay Bidang Paraboloid
Uji Simplifikasi
Didalam kenyataannya proses dengan vertek yang lebih besar dari titik-titik awan tersebut membuat proses kinerja metode menjadi penentu. Didalam triangulasi dengan vertek yang terlalu banyak perlu diadakan penyederhanaan vertek. Maka data-data vertek yang ada disederhanakan dengan cara pengelompokan atau clustering. Metode clustering vertek ini dibangun memanfaatkan kalkulasi dari voronoi yaitu euclidean distance. Berdasarkan persamaan euclidean distance diujikan dengan data koordinat yang diberikan secara random pada dua dimensi dengan asumsi memudahkan proses analisa pendekatan zona area pada titik-titik awan di permukaan model tiga dimensi.
Triangulasi delaunay pada bidang planar dapat di intepretasikan ke dalam bidang tiga dimensi dengan merujuk pada bidang tertentu. Konsep yang digunakan menggunakan convex hull dari organisasi Qhull. Dimana bidang tersebut menggunakan fungsi paraboloid. Sehingga fungsi yang didapatkan dari paraboloid tersebut adalah sebagai berikut:
Ilustrasi fungsi persamaan diatas dinyatakan pada gambar berikut ini.
(a) planar ke parabol
Menggunakan model tiga dimensi yang sudah ada baik terbuka maupun tertutup.
Penjelasan dari gambar berikut ini menunjukkan perilaku pada vertek untuk melakukan pergerakan pada vertek lain. Misalnya terdapat vertek tetangga (merah) yang kemungkinan mendekati vertek utama (biru) atau tidak sama sekali. Sehingga ada pergerakan pindah vertek menuju vertek yang diminati, tentunya dengan aturan yang diberlakukan.
(b)Kalkulasi Convex Hull
(c) parabol ke planar (b)Delaunay3D Gambar 3.7 Delaunay bidang Paraboloid
4.
(a)
HASIL DAN PEMBAHASAN
Komposisi distribusi yang akan diujikan dalam penelitian kali ini adalah pada distribusi seragam saja. Hal ini berkaitan dengan istilah penggunaan pada judul penelitian ini yaitu titik-titik awan (point clouds). Titiktitik awan tersebut sangatlah tepat pada distribusi tersebut dan lebih umum dalam menguji kinerja algoritma triangulasi delaunay. 4.1.
4.3.
(d)
Uji Triangulasi Delaunay Bidang Planar
Didalam pengujian metode triangulasi kali ini dimulai dari model dua dimensi. Dimana ada perbedaan mendasar dalam proses triangulasi untuk triangulasi delaunay dua dimensi dan tiga dimensi. Tahapan di dalam uji triangulasi delaunay ini ada tiga hal yaitu delaunay dan edge delaunay serta voronoi. Kedua tahapan tersebut merupakan syarat wajib di dalam legalisasi Triangulasi Delaunay. Berikut ini tampilan masing-masing tahapan tersebut.
Uji Model
Algoritma pada penelitian ini diujicobakan pada Notebook Personal Computer Intel Core 2 Duo 2GHz dengan memori 2GB. Sistem operasi yang dipakaikan untuk pengujian adalah Windows XP Service Pack 2. Algoritma dibangun dengan Matlab dan visualisasi dua dimensi dan tiga dimensi pun juga dibangun dengan menggunakan Matlab. Ada beberapa tool tambahan dalam mendukung analisa lebih dalam seperti visual studio 6.0 dan .NET 2005 dan 2008. Ada dua hal dalam menguji algoritma yaitu: 1.
(b) (c) Gambar 4.1 Data 50 vertek
Pembangkitan model secara acak membentuk ruang tertentu.
(a) Delaunay (b)Voronoi Gambar 4.2 Delaunay dan Voronoi dengan 40 vertek
4
Penjelasan proses waktu uji delaunay dan voronoi didalam konsep dualitas tersebut disajikan pada tabel berikut ini berdasarkan gambar 4.2: Tabel 4.1 Keluaran waktu proses triangulasi Item (a) (b)
Penjelasan -Delaunay 2D dengan 40 vertek selama : 0.00239 detik -Print Edge Delaunay 2D dengan 67 edge selama : 0.01733 detik -Delaunay 2D dengan 40 vertek selama : 0.00253 detik -Voronoi 2D dengan 107 vertek selama : 0.00086 detik
Jika urutan proses berdasarkan gambar 4.11 dan 4.12 disatukan maka ada integrasi sistem untuk menyatakan legalisasi triangulasi delaunay. Proses tersebut divisual pada gambar berikut ini.
(c) keluaran convex hull Gambar 4.4 Proses komputasi convex hull bidang planar
Jika dibuat tabel kinerja proses dari convex hull ini akan didapatkan grafik berdasarkan tabel yang direncanakan sebagai berikut. Tabel 4.3 Perbandingan waktu proses Convhull dan Convhull2D LAMA (detik) CONVHULL CONHULL2D 0.01 0.11 0.02 0.2 0.03 0.38 0.06 0.69 0.1 1.27
VERTEK 100000 177828 316228 562342 1000000
4.4.1. Model3D – Coba01 Gambar 4.3 Triangulasi Delaunay yang memiliki ketentuan kriteria Delaunay
Berikut ini percobaan dari data coba01.off mempunyai data vertek sebagai berikut:
Berdasarkan penjelasan dari bab 3 diatas, proses legalisasi berdasarkan kriteria circumcircle dimana dalam segitiga memiliki 3 vertek yang membentuk facet segitiga.
Tabel 4.4 Tabel vertek coba01.off Koordinat
Delaunay Voronoi
3 1 0 0
4 1 0 1
Vertek 5 6 0 0 1 0 1 1 1 0 1
7 0 1 1
8 0.9 0.1 0.1
9 0.5 0.5 0.5
Uji
Waktu (detik) 0.00247 Input points Edge Delaunay 2D dengan 69 15 edge 0.0179 17 5 Voronoi 108 vertek 0.00074 14 0.9 2D dengan Delaunay 2D dengan 40 vertek
Total waktu traingulasi Delaunay 2D 16 0.8 10
8
After the filtering 12
1
13 (a) vertek3D=11 (b) Delaunay2D (c) Delaunay3D 0.6 Gambar 4.5 Hasil triangulasi Delaunay2D dan 3D coba01.off 12
0.5
Dari proses diatas waktu yang diperlukan 0.4 triangulasi delaunay2D dan 3D adalah sebagai berikut, 0.3
0.4
Uji Triangulasi Delaunay Bidang Paraboloid 0.3
0.2 Selanjutnya penggunaan convex hull disini 20 menjadikan proses vertek 0.1 acuan dalam mengindikasi 9 bagian terluar dari model. Mekanisme yang diberikan 4 0.2 0.4 0.6 0.8 sangat beragam terutama0 terhadap waktu proses kinerja penyelesaian. 14
0.8
0.2 (a) Pembacaan OFF 9 vertek selama : 0.00099 s14 4 (b) Delaunay 2D dengan 9 vertek 6 selama : 0.00109 s 0.1 (c) Delaunay 3D dengan 9 vertek selama :2 0.00109 s 0 1 0 0.2 0.4 0.6 0.8 1 Dari proses file coba01.off terdapat 9 vertek The Convex 4Hull menghasilkan facet. Sedangkan ada 4 vertek yaitu 12 15 {3,4,7,8}17 yang 5 diatas facet tidak bisa dilakukan 7 triangulasi dikarenakan ada simetri vertek terhadap 16 8 pusat {9}. 10 {1,2,5,6} dengan vertek 2 6
3
13
19
4.4.2. Model 3D –111 Coba02
0.6
Berikut ini percobaan dari data coba02.off mempunyai data vertek sebagai berikut:
18
0.5 0.4
(b) filter vertek tengah 0.3
5
0.2
20
0.1 0
5
7 0.7
3
13 1 11
0.7
3
0.8
19 Total waktu yang diperlukan untuk triangulasi 0.6 delaunay 2D pidang planar sebayak 40 vertek adalah 18 0.02111 detik. 0.5
(a) vertek=20
11
9
0.9
2
0.9
8
10
7
0.02111
0.7
4.4.
2 0 0 0
x y z
Tabel 4.2 Keluaran waktu proses triangulasi Delaunay 2D Metode
1
6
9 4 0
0.2
0.4
0.6
The End
0.8
1
4.4.4. Model 3D – Nefertiti-Entire
Tabel 4.5 Tabel vertek coba02.off Koordinat x y z
1
2 0 0 0
3 1 0 0
4 0 1 0
1 1 0
5 0.5 0.5 0
Vertek 6 7 0.1 0.5 0.1 1 0.1 1
(a) vertek3D=11 (b) Delaunay2D
Sedangkan model berikut ini tidak sepenuhnya open surface.
8 9 10 11 0.9 0.25 0.75 0.5 0.1 1 1 1.5 0.1 0.25 0.25 0.5
(c) Delaunay3D Gambar 4.8 Model 3D Nefertiti-Entire
Gambar 4.6 Hasil triangulasi Delaunay2D dan 3D coba02.off
Waktu yang didapatkan untuk Delaunay adalah sebagai berikut:
untuk
uji
(a) Pembacaan OFF 11 vertek selama : 0.00119 s (b) Delaunay 2D dengan 11 vertek selama : 0.00150 s (c) Delaunay 3D dengan 11 vertek selama : 0.00119 s 4.4.3. Model 3D – Nefertiti Model berikutnya adalah nefertiti yang merupaka model topeng yang bersifat open surface.
(a) Delaunay2D (b) Delaunay3D Gambar 4.9 Kegagalan proses Delaunay pada Nefertiti-Entire yang bersifat semi-open surface
Pada pengujian triangulasi delaunay nefertitientire yang memiliki 654 vertek. Lama proses traingulasi dari model tersebut dari gambar 4.9 sebagai berikut :
(a) vertek3D=299
(a) Delaunay 2D input = 654 vertek, output = 1283 facet selama : 0.01960 s (b) Delaunay 3D input = 654 vertek, output = 4056 facet selama : 0.06901 s
(b) Facet Asli (c) Delaunay2D
4.4.5. Model 3D – Beetle Penjelasan untuk model beetle berikut ini, mendapatkan hasil triangulasi yang tidak berhasil baik delaunay 2D dan 3D.
(d) Delaunay2D
(e) Delaunay3D
Gambar 4.7 Keluaran proses triangulasi Delaunay pada Nefertiti.off
Hasil keluaran dari gambar 4.7 terhadap komputasi delaunay sebagai berikut :
Gambar 4.10 Model 3D Beetle
(d) Delaunay 2D input = 299 vertek, output = 568 facet selama : 0.00917 s (e) Delaunay 3D input = 299 vertek, output = 1629 facet selama : 0.02881 s Jika diamati maka terdapat perbedaan yang sangat signifikan. Pada model nefertiti tidak bisa diperoses delaunay3D. Karena terdapat proses penyebrangan antar vertek tetangga yang sangat berjauhan. Karena tidak ada pengecekan sudut terkecil yang diijinkan pada segitiga yang divalidkan menjadi facet pada delaunay.
(a) Facet Delaunay 2D
(b) Facet Delaunay 3D
Gambar 4.11 Hasil proses Delaunay 2D dan 3D pada Beetle
6
Pada pengujian triangulasi delaunay beetle yang memiliki 988 vertek. Lama proses traingulasi dari model tersebut sebagai berikut :
DAFTAR REFERENSI [1] Marc van Kreveld, “Algorithms for Triangulated Terrains”, ESPRIT IV LTR Project No. 21957 (CGAL), 1997.
(a) Delaunay 2D input = 988 vertek, output = 1934 facet selama : 0.03348 s (b) Delaunay 3D input = 988 vertek, output = 5218 facet selama : 0.10115 s 4.5.
[2] Y. Saito, Y. Nakazawa, S. Hayano ”Application of The Voronoi-Delaunay Transformation Method to Eigen Value Problems”, Applied Electromagnetics in Materials 1, 1990, hal. 59-64.
Analisa Model 3D Open Surface
[3] Henrik Zimmer, “Voronoi Techniques”, 30 Juli 2005.
Sehingga proses dari triangulasi Delaunay model ini jika dibandingkan dibandingkan dengan model sebelumnya yaitu nefertiti. Maka secara keseluruhan untuk performasi keluaran masih lebih baik pada nefertiti. Untuk menvisualkan pendapat yang bersifat logika boolean tersebut maka dibandingkan model kedua nefertiti yang dianggap sebagai kategori open surface.
TRIANGULASI DELAUNAY 2D 3D
NEFERTITI
TRUE
FALSE
NEFERTITIENTIRE
FALSE
FALSE
BEETLE
FALSE
FALSE
[5] Chen G., Ouyang P., Liu S., XIAO G., ”Research on Model Mergence Algorithm Based on Delaunay Triangulation”, The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. XXXVII. Part B1, Beijing, 2008, hal. 805-808.
PENJELASAN KETERANGAN 2D KETERANGAN 3D Perubahan pada gagal rekonstruksi hidung berubah, kecuali gagal rekonstruksi pada dahi dalam gagal
Delaunay
[4] Franz Aurenhanmer, “Voronoi Diagram – A Survey of a Fundamental Geometric Data Structure” ACM Computing Surveys, Vol 23 No.3, September 1991, hal. 345-405.
Tabel 4.6Perbandingan Boolean dengan keterangan pada model Open Surface MODEL
and
[6] J. Shewchuk, “The Delaunay Triangulation and Unstructured Lecture Notes on Delaunay Mesh Generation 1:10-15”, 1999.
gagal rekonstruksi
[7] Glenn Eguchi, “Delaunay Triangulation Handout”, 5.
October 2003.
KESIMPULAN
[8] Anurag Sharma, “Unstructured Mesh Generation by Advancing Front Method.” B.Tech. Project Report, Indian Institute of Technology - Bombay, Department of Aerospace Engineering, April 1996.
Fungsi triangulasi dengan menggunakan metode delaunay dibuat dua fungsi dipenelitian ini yaitu Delaunay2D dan Delaunay3D. Penggunaan model sebagai representasi titik-titik awan diwakili dari model yang sudah ada seperti nefertiti. Selain dicoba triangulasi seperti hasil yang didapat pada 4.4.1, 4.4.2, 4.4.3, 4.4.4 dan 4.4.5. Hasil yang signifikan berhasil pada 4.4.1 dan 4.4.2
[9] Alliez, P., Cohen-Steiner, D., Tong, Y., & Desbrun, M. (2007). Voronoi-based Variational Reconstruction of Unoriented Point Sets. Eurographics Symposium on Geometry Processing. The Eurographics Association.
Kemudian percobaan selanjutnya dilakukan poda model open surface seperti 4.4.3, 4.4.4 dan 4.4.5. Ternyata uji Delaunay 2D dan 3D tidak bisa diharapkan terutama pada 4.4.4. Karena pada Nefertiti-Entire terdapat selubung yang tidak terkategori open surface. Namun pada bagian dahi berhasil dilakukan secara delaunay 2D tapi tidak pada 3D.
[10] Chew, L. P. Triangulations.
(1987).
Constrained
Delaunay
[11] Carmichael, G. (2008). A Survey of Delaunay Triangulations: Algorithms and Applications.
.
7
