cartan
⌥

Mesh Quality

DEC correctness requires two mesh properties:

  • Delaunay: for every interior edge, the sum of opposite angles is . This guarantees non-negative cotangent weights (), which makes the discrete Laplacian negative semi-definite.

  • Well-centred: every circumcentre lies inside its simplex. For triangles, this is equivalent to all angles being acute (). This guarantees positive dual cell volumes (), making the Hodge star a proper positive-definite diagonal operator.

The mesh_quality module provides predicates to check these properties and operators to improve them.

Predicates

use cartan_dec::mesh_quality::{is_delaunay, is_well_centered, quality_report};
 
let report = quality_report(&mesh, &manifold);
println!("Delaunay: {}", report.is_delaunay);
println!("Well-centred: {}", report.is_well_centered);
println!("Min angle: {:.1} deg", report.min_angle.to_degrees());
println!("Max angle: {:.1} deg", report.max_angle.to_degrees());
println!("Non-Delaunay edges: {}", report.non_delaunay_edges);

Mesh Improvement

Intrinsic edge flips convert any triangulation to Delaunay without adding vertices. Each non-Delaunay edge is flipped to its opposite diagonal. The algorithm preserves vertex count, triangle count, and Euler characteristic.

use cartan_dec::mesh_quality::make_delaunay;
 
let mesh = make_delaunay(mesh, &manifold);
assert!(is_delaunay(&mesh, &manifold));

Lloyd smoothing moves interior vertices toward the area-weighted centroid of their incident triangles, then re-Delaunays. This pushes the mesh toward well-centredness (all angles acute). For manifold meshes, vertex motion uses the exponential map.

use cartan_dec::mesh_quality::make_well_centered;
 
let mesh = make_well_centered(mesh, &manifold, 50, 1e-8);

Mesh Generators

The mesh_gen module provides generators with an optional well_centered flag:

use cartan_dec::mesh_gen::{icosphere, torus};
 
// Well-centred icosphere (level 3 = 642 vertices)
let mesh = icosphere(&Sphere::<3>, 3, true);
 
// Well-centred torus (R=3, r=1, 20x10 grid)
let mesh = torus(&Euclidean::<3>, 3.0, 1.0, 20, 10, true);

Circumcentric Hodge Star

On a well-centred mesh, the circumcentric dual preserves primal-dual orthogonality (which the default barycentric dual does not). Use HodgeStar::from_mesh_circumcentric for DEC-correct operators:

let hodge = HodgeStar::from_mesh_circumcentric(&mesh, &manifold)?;
// Returns Err if the mesh is not well-centred.

Why This Matters

On a non-Delaunay mesh, cotangent weights can be negative, inverting the diffusion direction on some edges. On a non-well-centred mesh, dual cell areas can be negative, making the Hodge star lose positive-definiteness. Both pathologies produce incorrect physics in PDE solvers. The mesh quality module ensures these never occur.

References

  • Bobenko, Springborn. "A Discrete Laplace-Beltrami Operator for Simplicial Surfaces." Discrete and Computational Geometry, 2007.
  • VanderZee, Hirani, Guoy, Ramos. "Well-centered Triangulation." SIAM J. Sci. Comput., 2010.