Computing discrete geodesic distance over triangle meshes is one of the fundamental problems in computational geometry and computer graphics. In this problem, an effective window pruning strategy can significantly affect the actual running time. Due to its importance, we conduct an in-depth study of window pruning operations in this paper, and produce an exhaustive list of scenarios where one window can make another window partially or completely redundant. To identify a maximal number of redundant windows using such pairwise cross checking, we propose a set of procedures to synchronize local window propagation within the same triangle by simultaneously propagating a collection of windows from one triangle edge to its two opposite edges. On the basis of such synchronized window propagation, we design a new geodesic computation algorithm based on a triangle-oriented region growing scheme. Our geodesic algorithm can remove most of the redundant windows at
the earliest possible stage, thus significantly reducing computational cost and memory usage at later stages. In addition, by adopting triangles instead of windows as the primitive in propagation management, our algorithm significantly cuts down the data management overhead. As a result, it runs 4-15 times faster than MMP and ICH algorithms, 2-4 times faster than FWP-MMP and FWP-CH algorithms, and also incurs the least memory usage.
Surface parameterizations have been widely applied to computer graphics and digital geometry processing. In this paper, we propose a novel stretch energy minimization (SEM) algorithm for the computation of equiareal parameterizations of simply connected open surfaces with a very small area distortion and a highly improved computational efficiency. In addition, the existence of nontrivial limit points of the SEM algorithm is guaranteed under some mild assumptions of the mesh quality. Numerical experiments indicate that the efficiency, accuracy, and robustness of the proposed SEM algorithm outperform other state-of-the-art algorithms. Applications of the SEM on surface remeshing and surface registration for simply connected open surfaces are demonstrated thereafter. Thanks to the SEM algorithm, the computations for these applications can be carried out efficiently and robustly.
Automatic hexahedral mesh generation plays a fundamental role in CAD/CAE fields, especially for IGA (isogeometric
analysis). Recently, an automatic hex-mesh generation method has been proposed, which is based on the equivalence among
three key concepts: colorable quadrilateral meshes, finite measured foliations and Strebel differentials.
This work focuses on the computational aspect of Strebel differentials on high genus surfaces, which is based on graph-valued
harmonic mapping. The algorithmic pipeline is as follows: first, the user inputs an admissible curve system, which induces a
cylindric-decomposition graph; then the user specifies the lengths of the edges of the graph; third, the algorithm finds the unique
harmonic map from the surface to the metric graph by a non-linear heat flow; finally, the harmonic map induces a Strebel
differential, which can be further utilized to generate the hex-mesh.
The method has solid theoretic foundation, which guarantees the existence and the uniqueness of the graph-valued harmonic
map. The algorithm is capable of handling surfaces with complicated topologies, and producing all possible Strebel differentials
on the surface. The user has full control of the combinatorial type and the geometry of the Strebel differential. The computational
pipeline is automatic.
The experimental results show the efficiency and efficacy of the algorithm, and demonstrate the great potential for automating
the structured hexahedral mesh generation.