This project delves into an ingenious approach to ensure favorable triangle shapes in meshes without altering connectivity or employing complex data structures. By incorporating intrinsic mollification, the research showcases how this technique enhances the resilience of mesh processing algorithms, optimizing triangle quality.
Many geometry processing algorithms require that meshes have “good quality” triangles, e.g., no large obtuse angles or small slivers. A traditional way to improve element quality is to re-mesh the input, i.e., replace the original triangles with a new set of “good” triangles that approximate the same shape. However, changing the mesh connectivity causes headaches: data on the input must some how be transferred to the new mesh, and likewise, results computed on the “improved” mesh may not be directly usable by algorithms further downstream. Another possibility is to leave connectivity unchanged, and try to “wiggle” the vertex positions so that no triangles have degenerate angles. However, making one triangle better might make another one worse, and in general there may no even exist vertex coordinates that simultaneously make all triangles well-shaped.
This project explores a simple but elegant trick for guaranteeing that all triangles have good shape, without changing the mesh connectivity or using special data structures. The starting point is to observe that one can implement many standard algorithms using only the edge lengths of a mesh, rather than the vertex positions (e.g., the Laplace matrix can be built purely from lengths). Hence, rather than trying to wiggle vertex positions, we can simply lengthen alledge lengths simultaneously until all triangles meet a target quality measure. This technique is called “intrinsic mollification,” and was recently introduced in the paper A Laplacian for Nonmanifold Triangle Meshes. In the original algorithm, intrinsic mollification was applied after performing changes to the mesh connectivity. The observation of this SGI project is that intrinsic mollification can add robustness to mesh processing algorithms without changing the mesh connectivity. We will implement and validate the approach, and compare it to common alternatives.
The project will be broken down into several phases:
- Phase I. Implement the intrinsic mollification scheme by (i) reading off the original edge lengths and (ii) implementing the formula defined by Sharp & Crane to get new lengths that describe higher-quality triangles.
- Phase II. Build the cotan-Laplace matrix from the intrinsic lengths. (A description of how to do this can be found in the same paper by Sharp & Crane).
- Phase III. Use cotan-Laplace to run some standard algorithms from geometry processing. Rather than implement these algorithms from scratch, we should use existing algorithms in packages like libigl or GeometryCentral. Some good possibilities are (i) manifold harmonics, (ii) spectral conformal parameterization, and (iii) geodesic distance via the heat method.
- Phase IV. Compare to alternatives. In the case of the cotan-Laplace matrix, there are a variety of standard “hacks” that are used to deal with bad triangles, such as (i) clamping negative cotangent weights to zero, or a small positive value near zero, (ii) negating negative cotangent weights, and/or (iii) replacing bad edge weights with "1." We should implement each of these alternatives, and compare the algorithms from Phase III in terms of accuracy and visual fidelity.