We introduce the heat method for computing the geodesic distance to a specified subset (e.g., point or curve) of a given domain. The heat method is robust, efficient, and simple to implement since it is based on solving a pair of standard linear elliptic problems. The resulting systems can be prefactored once and subsequently solved in near-linear time. In practice, distance is updated an order of magnitude faster than with state-of-the-art methods, while maintaining a comparable level of accuracy. The method requires only standard differential operators and can hence be applied on a wide variety of domains (grids, triangle meshes, point clouds, etc.). We provide numerical evidence that the method converges to the exact distance in the limit of refinement; we also explore smoothed approximations of distance suitable for applications where greater regularity is required.
Efficient methods to compute intrinsic distances and geodesic paths have been presented for various types of surface representations, most importantly polygon meshes. These meshes are usually assumed to be well-structured and manifold. In practice, however, they often contain defects like holes, gaps, degeneracies, non-manifold configurations – or they might even be just a soup of polygons. The task of repairing these defects is computationally complex and in many cases exhibits various ambiguities demanding tedious manual efforts. We present a computational framework that enables the computation of meaningful approximate intrinsic distances and geodesic paths on raw meshes in a way which is tolerant to such defects. Holes and gaps are bridged up to a user-specified tolerance threshold such that distances can be computed plausibly even across multiple connected components of inconsistent meshes. Further, we show ways to locally parameterize a surface based on geodesic distance fields, easily facilitating the application of textures and decals on raw meshes. We do all this without explicitly repairing the input, thereby avoiding the costly additional efforts. In order to enable broad applicability we provide details on two implementation variants, one optimized for performance, the other optimized for memory efficiency. Using the presented framework many applications can readily be extended to deal with imperfect meshes. Since we abstract from the input applicability is not even limited to meshes, other representations can be handled as well. This paper presents a study of the computational efficiency, t hat is accuracy versus computational effort, for solving the Eikonal equation on quadrilateral grids. The algorithms that are benchmarked against each other for computations of distance functions are the following: the fast marching method, the fast sweeping method, an algebraic Newton method, and also a "brute force" approach. Some comments are also made on the solution of the Eikonal equation via reformulation to a hyperbolic PDE. The results of the benchmark clearly indicate that the fast marching method is the preferred algorithm due to both accuracy and computational speed in our tested context. An algorithm for the computationally optimal construction of intrinsic weighted distance functions on implicit hyper-surfaces is introduced in this paper. The basic idea is to approximate the intrinsic weighted distance by the Euclidean weighted distance computed in a band surrounding the implicit hyper-surface in the embedding space, thereby performing all the computations in a Cartesian grid with classical and efficient numerics. Based on work on geodesics on Riemannian manifolds with boundaries, we bound the error between the two distance functions. We show that this error is of the same order as the theoretical numerical error in computationally optimal, Hamilton‐Jacobi-based, algorithms for computing distance functions in Cartesian grids. Therefore, we can use these algorithms, modified to deal with spaces with boundaries, and obtain also for the case of intrinsic distance functions on implicit hyper-surfaces a computationally efficient technique. The approach can be extended to solve a more general class of Hamilton‐Jacobi equations defined on the implicit surface, following the same idea of approximating their solutions by the solutions in the embedding Euclidean space. The framework here introduced thereby allows for the computations to be performed on a Cartesian grid with computationally optimal algorithms, in spite of the fact that the distance and Hamilton‐Jacobi equations are intrinsic to the implicit hyper-surface. c ∞ 2001 Academic Press In this paper, we propose fast and accurate algorithms to remesh and flatten a genus-0 triangulated manifold. These methods naturally fits into a framework for 3D geometry modeling and processing that uses only fast geodesic computations. These techniques are gathered and extended from classical areas such as image processing or statistical perceptual learning. Using the Fast Marching algorithm, we are able to recast these powerful tools in the language of mesh processing. Thanks to some classical geodesic-based building blocks, we are able to derive a flattening method that exhibit a conservation of local structures of the surface. On large meshes (more than 500 000 vertices), our techniques speed up computation by over one order of magnitude in comparison to classical remeshing and parameterization methods. Our methods are easy to implement and do not need multilevel solvers to handle complex models that may contain poorly shaped triangles. A theoretical and computational framework for computing intrinsic distance functions and geodesics on submanifolds of @math given by point clouds is introduced and developed in this paper. The basic idea is that, as shown here, intrinsic distance functions and geodesics on general co-dimension submanifolds of @math can be accurately approximated by extrinsic Euclidean ones computed inside a thin offset band surrounding the manifold. This permits the use of computationally optimal algorithms for computing distance functions in Cartesian grids. We use these algorithms, modified to deal with spaces with boundaries, and obtain a computationally optimal approach also for the case of intrinsic distance functions on submanifolds of @math . For point clouds, the offset band is constructed without the need to explicitly find the underlying manifold, thereby computing intrinsic distance functions and geodesics on point clouds while skipping the manifold reconstruction step. The case of poin... Introduction 1. Formulations of interface propagation Part I. Theory and Algorithms: 2. Theory of curve and surface evolution 3. Hamilton-Jacobi equations and associated theory 4. Numerical approximations: first attempt 5. Numerical schemes for hyperbolic conservation laws 6. Algorithms for the initial and boundary value formulations 7. Efficient schemes: adaptivity 8. Triangulated versions of level set and fast marching method: extensions and variations 9. Tests of basic methods Part II. Applications: 10. Geometry 11. Grid generation 12 Image denoising 13. Computer vision: shape detection and recognition 14. Fluid mechanics and materials sciences: adding physics 15. Computational geometry and computer-aided-design 16. First arrivals, optimizations, and control 17. Applications to semi-conductor manufacturing 18. Comments, conclusions, future directions References Index.