Abstrak
Dalam makalah ini akan dibahas penerapan algoritma perhitungan geodesic distance pada permukaan obyek triangular mesh untuk dibuktikan tingkat keakuratan dan efisiensinya. Algoritma yang diterapkan adalah Fast Marching Method on Triangulated Domain (FMM on TD) yang berjalan dengan kompleksitas waktu O(n lg n), dimana n adalah jumlah titik pada permukaan. Inti dari algoritma ini adalah melakukan front propagation dari titik awal ke segala arah yang mungkin sampai diperoleh titik akhir. Setiap bergerak maju algoritma ini selalu menghitung nilai jarak suatu titik terhadap titik awal. Setelah proses perhitungan geodesic distance selesai, dilakukan proses pembuatan geodesic path. Inti dari proses ini adalah melakukan back propagation pada permukaan dari titik akhir sampai diperoleh titik awal. Berdasarkan uji coba, tingkat keakuratan algoritma FMM on TD adalah lebih dari 95%. Keakuratan ini dipengaruhi oleh jumlah segitiga pembentuk permukaan. Semakin banyak segitiga semakin akurat geodesic distance yang dihasilkan, tetapi waktu yang dibutuhkan untuk melakukan proses perhitungan menjadi semakin lama.
Kata kunci: computational geometry, geodesic distance, geodesic path, triangular mesh, fast marching method on triangulated domain, front propagation, back propagation
Pendahuluan
Geodesic Distance adalah jarak terdekat antara pasangan titik pada permukaan obyek 3 dimensi. Jarak ini dihitung tanpa melewati bagian dalam dari obyek 3 dimensi tersebut. Geodesic Path adalah lintasan pada permukaan obyek 3 dimensi yang jaraknya direpresentasikan oleh Geodesic Distance. Triangular Mesh adalah representasi permukaan 3D (surface) yang dibentuk oleh segitiga-segitiga.
Peneliti: Rully Soelaiman
Untuk lebih lengkapnya silahkan download di link berikut:
Post a Comment
Post a Comment