Jurnal Informatika (Jan 2006)
PENERAPAN METODE FAST MARCHING PADA PERHITUNGAN GEODESIC DISTANCE PERMUKAAN OBYEK TRIANGULAR MESH
Abstract
In this paper, we will describe an algorithm for geodesic distance calculation that applied at the surface of triangular mesh object, to analyze its efficiency and accuracy. We applied the Fast Marching Method on Triangulated Domain (FMM On TD) with O(n lg n) time complexity, where n is the number of point/triangle vertex that represent the surface. The main task of this algorithm is to do the front propagation step from the starting point to all possible direction to obtained the final point. Every step of this algorithm, will calculate the distance from the current point to the starting point. After the calculation of the geodesic distance finished, the next process is to build the geodesic path. The main task of this step is to do the back propagation step at the object surface from the final point to the starting point. Based on the experimental result, the accuracy of the FMM on TD algorithm is more than 95%. This accuracy depend on the number of the triangles that represent the surface. The accuracy of the geodesic path and the computational times are depends on the number of the triangles that used to represent the surface Abstract in Bahasa Indonesia : 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.
