Computing geodesic distances on triangle meshes is a fundamental problem in computational geometry and computer graphics. To date, two notable classes of algorithms, the Mitchell-Mount-Papadimitriou (MMP) algorithm and the Chen-Han (CH) algorithm, have been proposed. Although these algorithms can compute exact geodesic distances if numerical computation is exact, they are computationally expensive, which diminishes their usefulness for large-scale models and/or time-critical applications. In this paper, we propose the fast wavefront propagation (FWP) framework for improving the performance of both the MMP and CH algorithms. Unlike the original algorithms that propagate only a single window (a data structure locally encodes geodesic information) at each iteration, our method organizes windows with a bucket data structure so that it can process a large number of windows simultaneously without compromising wavefront quality. Thanks to its macro nature, the FWP method is less sensitive to mesh triangulation than the MMP and CH algorithms. We evaluate our FWP-based MMP and CH algorithms on a wide range of large-scale real-world models. Computational results show that our method can improve the speed by a factor of 3-10.

A fresh framework for mesh optimization, the Filtered Hooke's Optimization, is proposed. With the notion of the elasticity theory, the Hooke's Optimization is developed by modifying the Hooke's law, in which an elastic force is simulated on the edges of a mesh so that adjacent vertices are either attracted to each other or repelled from each other, so as to regularize the mesh in terms of triangulation. A normal torque force is acted on vertices to guarantee smoothness of the surface. In addition, a filtering scheme, called the Newtonian Filtering, is proposed as a supplementary tool for the proposed Hooke's Optimization to preserve the geometry of the mesh. Numerical simulations on meshes with different geometry indicate an impressive performance of our proposed framework to significantly improve the mesh triangulation without noteworthy distortions of the mesh geometry.

This work proposes a novel framework for optimization in the constrained diffeomorphism space for deformable surface registration. First the diffeomorphism space is modeled as a special complex functional space on the source surface, the Beltrami coefficient space. The physically plausible constraints, in terms of feature landmarks and deformation types, define subspaces in the Beltrami coefficient space. Then the harmonic energy of the registration is minimized in the constrained subspaces. The minimization is achieved by alternating two steps: 1) optimization - diffuse the Beltrami coefficient, and 2) projection - first deform the conformal structure by the current Beltrami coefficient and then compose with a harmonic map from the deformed conformal structure to the target. The registration result is diffeomorphic, satisfies the physical landmark and deformation constraints, and minimizes the conformality distortion. Experiments on human facial surfaces demonstrate the efficiency and efficacy of the proposed registration framework.

Presented in this paper is a sweepline algorithm to compute the Voronoi diagram of a set of circles in a two-dimensional Euclidean space. The radii of the circles are non-negative and not necessarily equal. It is allowed that circles intersect each other, and a circle contains others. The proposed algorithm constructs the correct Voronoi diagram as a sweepline moves on the plane from top to bottom. While moving on the plane, the sweepline stops only at certain event points where the topology changes occur for the Voronoi diagram being constructed. The worst-case time complexity of the proposed algorithm is $O((n+m)log n)$, where $n$ is the number of input circles, and $m$ is the number of intersection points among circles. As $m$ can be $O(n^22)$, the presented algorithm is optimal with $O(n^2 log n) $ worst-case time complexity.

We develop a general approach that uses holomorphic 1-forms to parameterize anatomical surfaces with complex (possibly branching) topology. Rather than evolve the surface geometry to a plane or sphere, we instead use the fact that all orientable surfaces are Riemann surfaces and admit conformal structures, which induce special curvilinear coordinate systems on the surfaces. Based on Riemann surface structure, we can then canonically partition the surface into patches. Each of these patches can be conformally mapped to a parallelogram. The resulting surface subdivision and the parameterizations of the components are intrinsic and stable. To illustrate the technique, we computed conformal structures for several types of anatomical surfaces in MRI scans of the brain, including the cortex, hippocampus, and lateral ventricles. We found that the resulting parameterizations were consistent across