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.
The prevailing approach to distance computation is to solve the subject to boundary conditions ( |_ = 0 ) over some subset ( ) of the domain. This formulation is and , making it difficult to solve directly. Typically one applies an iterative relaxation scheme such as Gauss-Seidel -- special update orders are known as and , which are some of the most popular algorithms for distance computation on regular grids @cite_20 and triangulated surfaces @cite_16 . These algorithms can also be used on implicit surfaces @cite_15 , point clouds @cite_25 , and polygon soup @cite_29 , but only indirectly: distance is computed on a simplicial mesh or regular grid that approximates the original domain. Implementation of fast marching on simplicial grids is challenging due to the need for nonobtuse triangulations (which are notoriously difficult to obtain) or else a complex unfolding procedure to preserve monotonicity of the solution; moreover these issues are not well-studied in dimensions greater than two. Fast marching and fast sweeping have asymptotic complexity of (O(n n) ) and (O(n) ), respectively, but sweeping is often slower due to the large number of sweeps required to obtain accurate results @cite_12 .
@cite_29 @cite_12 @cite_15 @cite_16 @cite_25 @cite_20
45207152 92634156 2005794784 2623449798
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. We introduce the Fast Marching farthest point sampling (FastFPS) approach for the progressive sampling of planar domains and curved manifolds in triangulated, point cloud or implicit form. By using Fast Marching methods 2 , 3, 6 for the incremental computation of distance maps across the sampling domain, we obtain a farthest point sampling technique superior to earlier point sampling principles in two important respects. Firstly, our method performs equally well in both the uniform and the adaptive case. Secondly, the algorithm is applicable to both images and higher dimensional surfaces in triangulated, point cloud or implicit form. This paper presents the methods underlying the algorithm and gives examples for the processing of images and triangulated surfaces. A companion report 4 provides details regarding the application of the FastFPS algorithm to point clouds and implicit surfaces. We introduce an algorithm for constructing a high-quality triangulation directly from Point Set Surfaces. Our algorithm requires no intermediate representation and no post-processing of the output, and naturally handles noisy input data, typically in the form of a set of registered range scans. It creates a triangulation where triangle size respects the geometry of the surface rather than the sampling density of the range scans. Our technique does not require normal information, but still produces a consistent orientation of the triangles, assuming the sampled surface is an orientable two-manifold. Our work is based on using Moving Least-Squares (MLS) surfaces as the underlying representation. Our technique is a novel advancing front algorithm, that bounds the Hausdorff distance to within a user-specified limit. Specifically, we introduce a way of augmenting advancing front algorithms with global information, so that triangle size adapts gracefully even when there are large changes in surface curvature. Our results show that our technique generates high-quality triangulations where other techniques fail to reconstruct the correct surface due to irregular sampling on the point cloud, noise, registration artifacts, and underlying geometric features, such as regions with high curvature gradients. An algorithm for the generation of non-uniform, locally orthogonal staggered unstructured spheroidal grids is described. This technique is designed to generate very high-quality staggered Voronoi–Delaunay meshes appropriate for general circulation modelling on the sphere, including applications to atmospheric simulation, ocean-modelling and numerical weather prediction. Using a recently developed Frontal-Delaunay refinement technique, a method for the construction of high-quality unstructured spheroidal Delaunay triangulations is introduced. A locally orthogonal polygonal grid, derived from the associated Voronoi diagram, is computed as the staggered dual. It is shown that use of the Frontal-Delaunay refinement technique allows for the generation of very high-quality unstructured triangulations, satisfying a priori bounds on element size and shape. Grid quality is further improved through the application of hill-climbing-type optimisation techniques. Overall, the algorithm is shown to produce grids with very high element quality and smooth grading characteristics, while imposing relatively low computational expense. A selection of uniform and non-uniform spheroidal grids appropriate for high-resolution, multi-scale general circulation modelling are presented. These grids are shown to satisfy the geometric constraints associated with contemporary unstructured C-grid-type finite-volume models, including the Model for Prediction Across Scales (MPAS-O). The use of user-defined mesh-spacing functions to generate smoothly graded, non-uniform grids for multi-resolution-type studies is discussed in detail.