The Heat Method

2 min read•1 page

The Heat Method: Heat Diffusion Step: Rather than running slow Dijkstra or Fast Marching on discrete graph edges, the Heat Method computes exact polyhedral geodesic distances by simulating short-time heat diffusion from a source vertex du/dt = Δu. Heat flows smoothly across triangle interiors independent of mesh tessellation.

Heat Equation Formulation:

1. Backward Euler Integration: Solves $(M - t L_C) u = \delta_x$ where $L_C$ is cotangent Laplacian and $M$ is lumped area. 2. Time Step $t = h^2$: Scaled to mean edge length $h$, balancing numerical stability with Varadhan's asymptotic limit. 3. Linear System: Solvable via a single sparse Cholesky factorization for millisecond queries.

python

1import numpy as np
2
3def integrate_heat_diffusion(L_cot, M_lumped, source_idx, t_step=0.05):
4    """
5    Step 1 of the Heat Method (Crane et al. 2013).
6    Integrate backward Euler heat diffusion: (M - t*L) * u = delta_source.
7    t_step is chosen as h^2 (mean edge length squared).
8    """
9    n = L_cot.shape[0]
10    rhs = np.zeros(n)
11    rhs[source_idx] = 1.0  # Dirac delta heat source
12    
13    # System matrix A = M - t * L_cot (positive definite)
14    A = np.diag(M_lumped) - t_step * L_cot
15    u = np.linalg.solve(A, rhs)
16    return u

Diffusion Time (t)

0.12

3 min read•1 page

The Heat Method: Vector Field & Poisson Solve: Geodesics satisfy the Eikonal equation $\|\nabla \phi\| = 1$. Varadhan's formula guarantees that as $t \to 0$, $-\nabla u / \|\nabla u\|$ aligns precisely with the geodesic gradients $\nabla \phi$. Solving the Poisson problem $\Delta \phi = \nabla \cdot X$ integrates this vector field back into exact geodesic distances $\phi$.

Vector Field Integration:

1. Face Gradients: Evaluate linear piecewise gradient ∇u across each triangle. 2. Unit Normalization: X = -∇u / ||∇u|| eliminates exponential decay and preserves direction. 3. Poisson Reconstruction: Solve symmetric positive semi-definite system L_C φ = div(X) with Dirichlet shift φ(x_0)=0.

python

1import numpy as np
2
3def compute_heat_geodesics(vertices, faces, heat_u, L_cot):
4    """
5    Steps 2 & 3 of the Heat Method (Crane et al. 2013).
6    1. Compute gradient of u on each face: grad_u = sum(u_i * (N x e_i)) / (2*Area)
7    2. Normalize and negate: X = -grad_u / ||grad_u||
8    3. Integrated divergence at vertices: div_X
9    4. Solve Poisson equation for geodesic distance phi: L_cot * phi = div_X
10    """
11    # X vector field per face is unit length pointing away from source
12    # Poisson solve recovers true intrinsic metric phi(x) = geodesic distance
13    # Shift so that phi(source) = 0
14    return "phi (geodesic distance field)"

Geodesic Isolines

6.00