Keenan Crane - Navigating Intrinsic Triangulations (original) (raw)

Unlike an ordinary triangle mesh (top), an intrinsic triangulation (bottom) can include edges that take any straightest path between vertices. However, each region bounded by three edges can still be unfolded into a single planar triangle.

Our signpost data structure stores the direction and distance to each neighbor, making triangulations easy to update and to query on-demand.

Intrinsic versions of classic algorithms yield high quality triangulations for any mesh. We can obtain a Delaunay triangulation without increasing the vertex count (top right), achieve lower angle bounds (bottom left), or balance angles and triangle areas (bottom right).

As in the Euclidean case, we find that intrinsic Delaunay refinement can achieve a minimum angle bound of 30°, even on challenging models.

Our signpost data structure makes it easy to implement an intrinsic version of optimal Delaunay triangulation (iODT), which provides an excellent balance between element size and angle distribution while exactly preserving the input geometry.

Our data structure allows planar computational geometry algorithms to be easily translated into the polyhedral setting. Here we apply a classic Euclidean algorithm for Steiner tree approximation to find shorter cuts through polyhedral surfaces.

Even for domains with large, flat regions, solving a Poisson equation is about twice as accurate with an intrinsic triangulation. Rows show two refinements, with matching element counts in the last three columns.

Working with intrinsic triangulations allows one to accurately and efficiently approximate the exact polyhedral distance using PDE based methods like the heat method.

Intrinsic AMR allows extremely accurate computations of standard kernels from geometry processing with very few elements. Left: harmonic Green's function. Right: short time heat kernel. Performing uniform iDR to achieve the same accuracy requires 18x and 54x as many vertices, respectively.

Mappings computed on low-quality meshes can exhibit flipped triangles, as shown here for a harmonic mapping (left). An iDT guarantees the map is flip-free (center), and AMR intelligently reduces distortion (right).

Our signpost data structure is also well suited for tangent vector field processing. Here we draw streamlines of the vector field with smallest Dirichlet energy ED (showing vectors in the inset); using an intrinsic triangulation yields a much smoother field.

Intrinsic triangulations that satisfy the Delaunay condition help prevent flips in tangent direction fields. Here we compute the smoothest field interpolating given vectors at the boundary.

Flipping to the intrinsic Delaunay triangulation and extracting the edge crossings in the overlay mesh is extremely efficient with the signpost data structure. Prior methods update the overlay mesh every flip, while our approach reads it off after the fact.

Left: an extrinsic Delaunay triangulation which preserves geometry requires dramatically more vertices. Center: the intrinsic Delaunay triangulation requires no additional elements. Right: Even a modest number of additional intrinsic vertices can dramatically increase element quality.

A mechanical part (left) is made Delaunay with extrinsic splits and simplifications (center), or with intrinsic flips (right). For an equal number of elements, the extrinsic method loses important geometric detail, whereas the intrinsic triangulation exactly preserves the given shape.

An intrinsic edge can cross an extrinsic edge many times, as seen with this increasingly “twisted” cube. Rather than track these crossings explicitly, we introduce an implicit encoding that has constant size.