COMPARATIVE ANALYSIS OF MOBILE ROBOTS’ GEODESIC PATH PLANNING ALGORITHMS ON 3D MESH TERRAIN REPRESENTATIONS

ABSTRACT

Choosing an effective path planning algorithm for robotic terrain navigation on uneven terrain represented as 3D mesh structures is still an open problem. Current comparative analyses are mostly focused on 2D grid or obstacle field settings, and the 3D mesh environment has remained largely unexplored. This paper describes a comprehensive benchmarking analysis of eight geodesic and graph-based path planning algorithms, including A*, Dijkstra, FlipOut, Fast Marching Method, Greedy Best-First Search, Heat Method, Mitchell-Mount-Papadimitriou (MMP), and Theta*, on ten different scenarios for two geometrically different mesh terrains using the MeshNav3D toolkit. The algorithms’ performance is measured in terms of four metrics: path length, optimality error, running time, and maximum memory usage. Our results show that geometry-aware planners (FlipOut, MMP, Theta*) always produce paths with near-geodesic optimality, while graph-based planners (Dijkstra, Greedy BFS) are significantly faster but less optimal. The Heat Method produces the longest paths and is also more robust to noisy or irregular terrain. We also analyze the impact of mesh size and density on the differences between the planners’ performance, and provide a practical guide for algorithm selection based on empirical evidence.

АННОТАЦИЯ

Выбор эффективного алгоритма планирования маршрута для роботизированной навигации по неровной местности, представленной в виде трехмерных сетчатых структур, все еще остается открытой проблемой. Известные работы в этой области в основном сосредоточены на использовании 2D-сетки или поля препятствий. В этой работе описывается всесторонний сравнительный анализ восьми алгоритмов планирования траекторий на основе геодезических данных и графов, включая A*, Дейкстру, FlipOut, метод быстрого перехода, жадный поиск по принципу «Лучший-первый», «тепловой метод», метод Митчелла-Маунта-Пападимитриу (MMP) и Theta*, в десяти различных сценариях для двух геометрически разных объектов. Сетка ландшафтов генерируется с помощью инструментария MeshNav3D. Производительность алгоритмов измеряется с помощью четырех показателей: длины пути, ошибки оптимальности, времени выполнения и максимального использования памяти. Полученные результаты показывают, что планировщики, ориентированные на геометрию (FlipOut, MMP, Theta*), всегда создают траектории с оптимальностью, близкой к геодезической, в то время как графические планировщики (Dijkstra, Greedy BFS) работают значительно быстрее, но менее оптимальны. «Тепловой метод» позволяет создавать самые длинные траектории, а также более устойчив к шумам или неровностям местности. Также выполнен анализ влияния размера и плотности сетки на различия в производительности проектировщиков и предоставлено практическое руководство по выбору алгоритма, основанное на эмпирических данных.

Keywords: path planning, 3D mesh terrain, geodesic algorithms, benchmarking, uneven terrain navigation, mobile robotics

Ключевые слова: планирование маршрута, трехмерная сетчатая местность, геодезические алгоритмы, бенчмаркинг, навигация по неровной местности, мобильная робототехника

I. INTRODUCTION

Outdoor or disaster response ground robots that are autonomous must operate on terrain that is geometrically complex: rocky slopes, excavation sites, and planetary examples all have height discontinuities and curvatures that are not flat world assumptions made in 2D planners [6], [13]. A natural and increasingly common way to represent such terrain is as a triangular mesh, reconstructed from LiDAR data using reconstruction pipelines such as LVR2 [14] and stored in standard formats (.obj, .ply).

Despite this, the motion planning community lacks a thorough empirical comparison of planning algorithms evaluated directly on 3D mesh surfaces. Prior benchmarking efforts focus on 2D occupancy grids [11] or manipulator configuration spaces [1], leaving practitioners without principled guidance when selecting algorithms for mesh-terrain navigation.

This paper addresses that gap. Using the MeshNav3D computational framework [5], we benchmark eight representative algorithms spanning graph search, continuous propagation, and differential-geometry approaches across ten planning scenarios on two mesh environments of contrasting complexity. Our study makes the following contributions:

• A rigorous multi-metric comparison of eight geodesic and graph-based planners on 3D mesh terrains, across ten distinct start-goal scenarios spanning two geometrically contrasting environments.
• Empirical characterization of the trade-off surface between path optimality, runtime, and memory usage across all evaluated methods.
• Analysis of how mesh complexity (scale vs. density) modulates inter-planner performance differences.
• A practical algorithm selection guide grounded in quantitative evidence from the benchmarking results.

II. RELATED WORK

A. Graph-Based Planners on Surfaces

A* [4] and Dijkstra’s algorithm [3] are still the most popular graph methods for shortest path problems. In the context of mesh surfaces, these algorithms work on the dual graph of mesh vertices and edges, leading to a discretization error dependent on the mesh resolution. Theta* [8] alleviates this problem by allowing parent pointers with arbitrary angles and validating them using line-of-sight tests.

B. Continuous and Differential-Geometry Methods

The Fast Marching Method (FMM) [9] numerically solve the Eikonal equation by propagating a wave front from the source vertex, and providing globally consistent distance fields.

The Heat Method [2] recasts the geodesic computation into two sparse linear solves (heat diffusion followed by a Poisson equation) and is robust on irregular/noisy meshes.

Hence, the Mitchell-Mount-Papadimitriou (MMP) algorithm [7] that computes exact polyhedral geodesics via continuous Dijkstra wavefront propagation on face interiors is considered the ground-truth reference in this study.

The FlipOut algorithm [10] tackles exactness using iterative edge-flip refinement, thus providing a workable tradeoff between MMP accuracy and runtime.

C. Benchmarking Frameworks

OMPL [11] offers full algorithm implementations with standardized benchmarking but is based on abstract configuration spaces, which demand substantial adaptation for 3D mesh environments. MeshNav3D [5] fills this gap with native mesh loading, interactive visualization, and a common planner interface that constitutes the experimental basis of this work. To the best of our knowledge, there is no existing work that systematically compares geodesic and graph-based planners on multiple metrics and under a common experimental setting on 3D triangular mesh terrains.

III. EXPERIMENTAL SETUP

A. Mesh Environments

Two mesh environments were chosen to investigate complementary aspects of planner behavior (see Table I).

Mesh 1 is a larger terrain (≈10m×10m bounding box) with strong elevation variation, irregular gradient changes, and moderate vertex density. It emphasizes path length optimality and runtime scaling.

Mesh 2 is a small, high-density terrain (≈1m×1m bounding box) with a high face density. It emphasizes efficiency and surface-projection overheads.

The two meshes were tested with five scenarios each, with start and goal positions varying in distance (short, medium, and long Euclidean distances) and terrain type (flat, sloped, and ridge-crossing). Scenarios 1 through 5 are for Mesh 1, and scenarios 6 through 10 for Mesh 2.

B. Evaluated Algorithms

The MeshNav3D system tested eight different planners.

The first algorithm that was tested through the MeshNav3D framework uses A* algorithm as its standard search method which combines heuristic graph search with Euclidean distance measurement via its priority queue system that runs on heapq according to the source document.

The Dijkstra algorithm conducts exhaustive graph searches through its optimal search method which PyVista implements through its geodesic method that allows users to manage edge weights in mesh-based systems according to reference Dijkstra 1959 and PyVista.

FlipOut algorithm uses potpourri3d EdgeFlipGeodesicSolver to perform its geodesic refinement process through iterative edge-flip method.

The Fast Marching Method (FMM) algorithm uses heapbased Eikonal solver to perform gradient-descent path extraction according to the research of Sethian in 1999.

Greedy BFS algorithm expands only toward nearby goals which makes it the fastest option but it does not provide good path results.

The Heat Method process operates through two stages which solve sparse linear equations for heat diffusion and

Table I.

Evaluation scenarios: start/end coordinates and euclidean distance

Poisson problems through the use of potpourri3d according to reference Crane 2013 Geodesics.

The MMP system uses pygeodesic to calculate precise polyhedral geodesics which function as the absolute reference point for measurement according to the research of Mitchell and Pygeodesic.

Theta* algorithm functions as an A* version which enables movement through any angle while conducting line-of-sight surface inspections according to the study Nash 2007 Theta.

C. Metrics

Four metrics were recorded per scenario:

Path Length (PL):

                                                             (1)

where p_i is the i-th waypoint in Euclidean 3D space. Optimality Deviation (Opt):

Opt = PL −∥p_n − p₁∥                                                                (2)

the excess path length above the straight-line Euclidean distance. Lower is better; zero is unachievable on non-flat terrain.

Runtime (Time): Wall-clock seconds from algorithm invocation to path output.

Peak Memory (Mem): Maximum resident set size (MB) sampled via psutil.Process.memory_info().rss [12].

D. Hardware and Software

The researchers conducted their tests on an ASUS ROG Strix G614JU workstation that operated Ubuntu Linux and had a 13th Gen Intel Core i7 processor with 32 GB of DDR5 SODIMM RAM at 5600 MT/s and an NVIDIA GeForce RTX 4050 Max-Q and a 512 GB NVMe SSD. The planners were tested without GPU acceleration and all time measurements documented single-threaded CPU performance.

IV. RESULTS

Full quantitative results are presented in Table II. We report per-scenario values for all four metrics; discussion of trends follows in the subsections below. PL is path length, OPT is optimality deviation, TIME is runtime (s), MEM is peak memory (mb). Lowest pl and opt in each scenario are shown in bold.

Table II.

 Planner performance across all scenarios

A. Path Quality (Length and Optimality)

The geometry-aware techniques (FlipOut and MMP) proceeded to obtain the shortest routes together with their optimality assessments during both mesh tests. The two planners on Mesh 1 generated path distances that ranged from 8.84 meters to 12.20 meters, while their optimality assessments showed deviations between 0.41 meters and 0.91 meters during five tests. The results show a significant drop when compared to the A* and Dijkstra algorithms, which achieve an optimality range of 0.87 to 2.02 through their edge graph execution, because they use the discretization errors from that graph system.

Theta* occupied an intermediate position: its any-angle parent updates reduced discretization artefacts relative to A* and Dijkstra, yielding optimality deviations of 0.48–0.92 on Mesh 1 and 0.09–0.31 on Mesh 2. The graph search system produced better results than standard graph search results, but it was unable to deliver the same level of geometric accuracy which FlipOut and MMP reached.

The Heat Method produced markedly longer paths across every scenario (Opt values of 8.74–12.40) on Mesh 1 and 1.11–2.22 on Mesh 2. The method’s global diffusion process operates without path length optimization because it aims to create a distance field which remains smooth and consistent throughout the entire area; this results in paths that use gradient descent to handle complex geometrical shapes.

The Fast Marching Method occupied the middle ground between the Heat Method and MMP, with Opt values of 1.62– 2.07 (Mesh 1) and 0.19–0.73 (Mesh 2). Eikonal-based propagation methods operate close to actual geodesics, but their accuracy falls short of MMP’s precise polyhedral structure.

The results show that greedy BFS produced the highest path quality range between 0.31 and 2.72 on Mesh 1, together with a 0.53 to 1.23 range on Mesh 2, which proved that greedy heuristic expansion without accumulated-cost tracking produces path quality that is scenario-dependent.

B. Runtime

The runtime hierarchy was consistent across both meshes and all scenarios. Dijkstra (via PyVista’s optimized native geodesic method) and Greedy BFS were the fastest planners, with execution times at or below 0.001 s in virtually all scenarios. Despite Dijkstra’s O(V logV ) complexity, the mesh-native implementation exploits precomputed adjacency structures that substantially reduce constant factors.

A* and Theta* ran at similar speeds to one another (0.002– 0.026 s), both slower than raw Dijkstra due to heuristic computation and, in the case of Theta*, per-step line-of-sight validation. FMM exhibited moderate runtimes (0.003–0.028 s) with the peak occurring on Scenario 2, likely attributable to the particular mesh connectivity around that region’s start vertex.

MMP was faster than expected given its exact computation guarantee (0.000–0.004 s), a reflection of pygeodesic’s optimized C++ backend. FlipOut showed comparable performance (0.000–0.002 s). The Heat Method, despite involving two sparse linear solves, ran within 0.009 s on Mesh 1 and 0.004 s on Mesh 2, enabled by potpourri3d’s precomputed factorizations.

C. Memory Consumption

Peak memory usage was uniformly low (under 2 MB for all planners), reflecting the small mesh sizes used and the 32 GB RAM available. FlipOut exhibited the highest memory spike (1.95 MB in Scenario 1) likely due to solver initialization overhead; this overhead amortizes across repeated queries on the same mesh. FMM and A* recorded secondary peaks (≤1.45 MB), while MMP, Greedy BFS, and Theta* consistently required near-zero additional memory. The Heat Method’s precomputed factorization, despite its linear-solve overhead, contributed only 0.36 MB in the worst case.

D. Mesh Complexity Effects

Comparing Mesh 1 (large, irregular) and Mesh 2 (small, dense) reveals that mesh scale amplifies inter-planner path length differences while mesh density increases sensitivity to heuristic accuracy. On Mesh 1, the gap between the best performers (FlipOut/MMP, Opt ≈ 0.41–0.91) and worst (Heat Method, Opt ≈ 8.74–12.40) is approximately a factor of 14. On Mesh 2 this ratio narrows to roughly ×9 (0.01–0.12 vs. 1.11–2.22). Greedy BFS shows the opposite trend: its Opt values increase from Mesh 1 to Mesh 2 on several scenarios, suggesting that its greedy heuristic is more easily misled by the denser, more locally ambiguous structure of Mesh 2.

V. DISCUSSION

A. Interpreting the Optimality-Runtime Trade-off

The results expose a clear stratification of the eight planners into three tiers when both path quality and speed are considered jointly. The first tier—FlipOut and MMP—dominates on path quality: across all ten scenarios and both meshes their optimality deviations are consistently the lowest, often matching one another to two decimal places. This is expected given that MMP computes exact polyhedral geodesics by definition, and FlipOut’s iterative edge-flip refinement converges to the same result on well-conditioned meshes. Crucially, this quality advantage comes at negligible additional runtime cost relative to the graph-based planners at the mesh scales tested.

The second tier, (A*, Dijkstra, and Theta*) occupies the middle ground on path quality but spans a wide range on runtime. Dijkstra’s implementation via PyVista’s mesh-native backend exploits precomputed adjacency and achieves submillisecond execution, matching or beating Greedy BFS despite guaranteeing optimal graph-shortest paths. A* adds a Euclidean heuristic but paradoxically runs slower than Dijkstra in several scenarios; on mesh graphs the heuristic provides limited pruning benefit because graph distances frequently deviate substantially from Euclidean distances over uneven terrain, causing many nodes to be re-expanded. Theta* recovers some optimality over A* by permitting any-angle parents, but its per-step line-of-sight validation adds a consistent overhead that grows with path length, visible in the monotonically increasing runtimes across Scenarios 1–5 on Mesh 1.

The third tier, (FMM and the Heat Method—involves) additional computational structure (PDE solving) that neither consistently improves path quality over the first tier nor matches the speed of the second. FMM’s Eikonal wavefront propagation yields globally consistent distances but its path quality on the test meshes was generally worse than FlipOut or MMP, suggesting that the finite-difference Eikonal approximation on coarse, irregular triangulations introduces numerical error that compounds along gradient-descent path extraction. The Heat Method’s distance estimates are even less tight, as its two-stage linear solve is designed for broad robustness rather than geodesic precision.

B. The Role of Mesh Geometry

An important and practically relevant finding is that mesh scale and mesh density affect planners differently. Mesh 1’s larger spatial extent amplifies absolute path length differences between planners—the gap in optimality deviation between FlipOut/MMP and the Heat Method spans roughly 8–12 m. On Mesh 2 the same gap is 1–2 m, but expressed as a ratio to the Euclidean start-goal distance (itself only 1–1.6 m), the Heat Method’s paths are proportionally more expensive—often 1.5–2.4× the Euclidean distance, compared with 1.03–1.08× for FlipOut/MMP.

Greedy BFS exhibits the most pronounced sensitivity to mesh density. On Mesh 1 its optimality deviations are moderate and fairly consistent (1.56–2.31), but on Mesh 2 they become erratic (0.53–1.23), with the worst case (Scenario 9, Opt=1.23) representing a 78% excess over the Euclidean distance on a path of only 2.82 m. This behavior arises because on dense meshes the local neighborhood of each node contains many vertices at similar goal distances, making the greedy heuristic poorly discriminating and susceptible to guiding the search into topological dead-ends from which backtracking is not performed.

FMM shows the opposite trend: its relative performance improves on Mesh 2 compared with Mesh 1. On Mesh 1

FMM’s optimality deviations (1.62–2.07) exceed those of A* and Dijkstra in three out of five scenarios. On Mesh 2 they are consistently below those of Greedy BFS and the Heat Method and comparable to A*/Dijkstra. This suggests that FMM’s Eikonal approximation benefits from denser triangulations, where shorter edge lengths reduce finite-difference discretization error.

C. Algorithm Selection Guide

Drawing on the quantitative results, we offer the following evidence-based recommendations for practitioners selecting a planner for 3D mesh terrain navigation:

Prioritize path quality (Opt): Use FlipOut for irregular or coarse meshes where iterative refinement converges quickly, or MMP when a formal exactness guarantee is required (e.g., ground-truth generation, safety-critical planning). Both are competitive on runtime and memory.

Prioritize speed: Use Dijkstra via a mesh-native backend. It matches Greedy BFS in runtime while delivering substantially better path quality. Greedy BFS is only preferable if path quality is entirely irrelevant and even the minor overhead of tracking accumulated cost is unacceptable.

Coarse or low-resolution meshes: Use Theta*. Its anyangle parent updates significantly reduce staircase artefacts that afflict standard graph search on coarse meshes, recovering path quality approaching FlipOut/MMP at a fraction of the geometric solver’s complexity.

Noisy or geometrically degenerate meshes: Use the Heat Method. Despite producing the longest paths in all tested scenarios, its diffusion-based distance computation is inherently robust to degenerate triangles, locally inconsistent normals, and other artefacts common in raw LiDAR reconstructions. For downstream applications that require a smooth, globally consistent distance field rather than a precisely minimal path, it is the most reliable choice.

Dense, fine-resolution meshes: Consider FMM. Its Eikonal approximation quality improves with mesh resolution, and its moderate runtime (2–28ms in these experiments) is acceptable when mesh density makes graph-based methods computationally equivalent anyway.

D. Limitations

This study contains multiple limitations which need future research to resolve. The test corpus contains only two mesh environments which were selected to display different scale and density but they did not show extreme environmental conditions because they lacked multi-level structures and nearvertical cliff faces and planetary analogue terrains. The test environment used all static meshes without any obstacles because the presence of forbidden areas and dynamic changes would impact planners who use global structure precomputation methods differently from those who use incremental operational methods. The hardware system used 32 GB DDR5 RAM and NVMe SSD which substantial memory and runtime changes will occur when using outdoor terrain meshes that contain millions of faces because MMP and Heat Method show increasing initialization costs based on mesh size. The planners executed in single-threaded mode while methods that naturally use parallel structures like FMM wavefront propagation would benefit from parallelization.

The future research should assess planners using large-scale LiDAR-derived meshes that originate from actual robotics fieldwork while testing dynamic obstacle handling and incremental replanning and investigating parallel implementations for multi-core processing.

VI. CONCLUSION

This paper presented a systematic benchmarking study of eight path planning algorithms on 3D mesh terrain representations, evaluated across ten scenarios on two geometrically distinct mesh environments using the MeshNav3D framework. The central finding is that algorithm class; (graph-based, continuous PDE, or differential-geometry) is the primary determinant of path quality, while implementation quality and mesh-native integration primarily determine runtime.

FlipOut and MMP consistently achieve the shortest, neargeodesic paths (Opt ≈ 0.41–0.91 on Mesh 1; 0.01–0.12 on Mesh 2) with runtimes at or below 4ms, making them the preferred choice when path quality is paramount. Dijkstra and Greedy BFS offer sub-millisecond planning suited to latency-sensitive contexts, albeit with higher optimality deviations. Theta* provides the best quality–speed trade-off on coarse meshes by reducing discretization artefacts via anyangle parent pointers. The Heat Method yields longer paths but is the most robust on irregular or noisy meshes such as raw LiDAR-derived terrain. Finally, mesh geometry matters independently of planner choice: scale amplifies absolute path length differences, while density disproportionately degrades heuristic-only methods (Greedy BFS) and benefits PDE-based methods (FMM).

These results provide a principled, empirically grounded basis for algorithm selection in terrain-aware robotic navigation. The full benchmark protocol and planner implementations are available through the MeshNav3D framework [5], enabling reproducible extension to new mesh environments and planning methods.

References:

1. Chitta S., "MoveIt!: An Introduction," / S. Chitta // in Robot Operating System (ROS): The Complete Reference (Volume 1), A. Koubaa, Ed. Cham: Springer International Publishing, 2016, pp. 3–27. doi: 10.1007/978-3-319-26054-9_1.
2. Crane K., “Geodesics in heat: A new approach to computing distance based on heat flow,” / K. Crane, C. Weischedel, and M. Wardetzky // ACM Transactions on Graphics (TOG), vol. 32, no. 5, pp. 1–11, 2013.
3. Dijkstra E., “A note on two problems in connexion with graphs.” / E. Dijkstra // Numerische Mathematik, vol. 1, pp. 269–271, 1959. [Online]. Available: http://eudml.org/doc/131436
4. Hart P. E., “A formal basis for the heuristic determination of minimum cost paths,” / P. E. Hart, N. J. Nilsson, and B. Raphael // Systems Science and Cybernetics, IEEE Transactions on, vol. 4, no. 2, pp. 100–107, 1968.
5. Jerome O., “Meshnav3d: Software for visualizing and benchmarking uneven terrain planning algorithms,” / O. Jerome, C. Bassey, C. Okeme, A. Maloletov, and G. Kulathunga // Journal of Open Research Software, Sep 2025.
6. LaValle S. M., "Planning Algorithms," / S. M. LaValle // Cambridge: Cambridge University Press, 2006.
7. Mitchell J. S., “The discrete geodesic problem,”/ J. S. Mitchell, D. M. Mount, and C. H. Papadimitriou // SIAM Journal on Computing, vol. 16, no. 4, pp. 647–668, 1987.
8. Daniel K., "Theta*: Any-angle path planning on grids," / K. Daniel, A. Nash, S. Koenig, and A. Felner // Journal of Artificial Intelligence Research, vol. 39, pp. 533–579, 2010. doi: 10.1613/jair.2994.
9. Sethian J. A., “Fast marching methods,” / J. A. Sethian // SIAM review, vol. 41, no. 2, pp. 199–235, 1999.
10. Sharp N., “You can find geodesic paths in triangle meshes by just flipping edges,”/ N. Sharp and K. Crane // ACM Transactions on Graphics (TOG), vol. 39, no. 6, pp. 1–15, 2020.
11. Sucan I. A., “The open motion planning library,”/ I. A. Sucan, M. Moll, and L. E. Kavraki // pp. 72–82, 2012.
12. Rodola G., "psutil: Cross-platform library for process and system monitoring in Python,"/G.Rodola// 2025. [Online]. Available: https://github.com/giampaolo/psutil. [Accessed: Apr. 9, 2025].
13. Wang C. , “Autonomous mobile robot navigation in uneven and unstructured indoor environments,”/ C. Wang, L. Meng, S. She, I. M. Mitchell, T. Li, F. Tung, W. Wan, M. Q.H. Meng, and C. W. de Silva // IEEE, pp. 109–116, 2017.
14. Wiemann T., “Surface Reconstruction from Arbitrarily Large Point Clouds,” / T. Wiemann, I. Mitschke, A. Mock, and J. Hertzberg // pp. 278–281, 2018.