Abstract:

In the field of digital geometry processing, the computation of geodesic distances on surfaces is a fundamental and crucial task. During the calculation process, each surface point serves as both a receiver and a transmitter to propagate distances across the entire surface. When there are open boundary defects, existing algorithms attempt to fill holes and gaps in the ambient space. However, this approach remains inadequate when dealing with open-boundary defects occurring in highly curved regions. To address this, a new approach was proposed allowing geodesic distance propagation to naturally traverse holes without filling them. It was observed that traditional algorithms, after crossing holes, formed a “shadow” region. In this region, the shortest path was found to pass through the hole’s boundary, producing distances larger than the true geodesic distance. Based on this observation, three significant improvements were made to the classical fast marching method (FMM): First, boundary points are treated solely as distance receivers, preventing them from propagating distances to other points. Second, each point was allowed to propagate distances in both forward and backward directions, enabling points in the shadow region to obtain geodesic distances from the surrounding visible points. Finally, a balance was achieved between “near to far” and “visible region to shadow region” propagation modes by adjusting the priority of distance propagation. Experimental results demonstrated that even with highly complex open boundary defects, our method produced geodesic distances closely approximating the true solution (the solution for a model without defects).

Key words: computational geometry, geodesic distance, fast marching method, broken mesh, open boundary