# Definition: Laplacian Matrix for triangle meshes

Quick definition of the Laplacian matrix on a triangular mesh. I give an in depth explanation here.

What is commonly called the **Laplacian matrix** \( \mathbf L \) in the literature of geometry processing is:

$$

\mathbf L_{ij} =

\left \{

\begin{matrix}

w_{ij} = \frac{1}{2} \cot \alpha_{ij} + \cot \beta_{ij} & \text{ if j adjacent to i} \\

-\sum\limits_{{j \in \mathcal N(i)}} { w_{ij} } & \text{ when } i = j \\

0 & \text{ otherwise } \\

\end{matrix}

\right .

$$

- \( \mathbf L \in \mathbb R^{n \times n} \) with \( n \) the number of vertices of the mesh
- \( \mathbf L_{ij} \) is a single element of the matrix
- The row \( i \) and column \( j \) of the matrix represent vertex indices as well
- \( {j \in \mathcal N(i)} \) is the list of vertices directly adjacent to the vertex \( i \)
- Each row of \( \mathbf L \) contains the list of vertices weights adjacent to \( i \)
- \( \mathbf L \) is symmetric positive semi-definite

On the other hand the **Laplacian *operator*** is defined as \( \mathbf {\Delta f} = {\mathbf M}^{-1} \mathbf L \) with the Mass matrix \( \mathbf M \), a diagonal matrix that stores the cell area (blue area on the figure) of each vertex:

$$

\mathbf M^{-1} =

\begin{bmatrix}

\frac{1}{A_0} & 0 & 0 \\

0 & \ddots & 0 \\

0 & 0 & \frac{1}{A_n}\\

\end{bmatrix}

$$

$$A_i = 3 \sum\limits_{{T_j \in \mathcal N(i)}} {area(T_j)}$$

- \( T_j \in \mathcal N(i) \) list of triangles adjacent to \( i \)
- \( A_i \) can also be computed with mixed voronoi area.

## Code

See the [ C++ code ] to build the laplacian matrix with cotan weights (`get_laplacian()`

procedure)

If your mesh is represented with an half-edge data structure (each vertex knows its direct neighbours) the pseudo code to compute \( \mathbf L \) is:

// angle(i,j,t) -> angle at the vertex opposite to the edge (i,j) for(int i : vertices) { for(int j : one_ring(i)) { sum = 0; for(int t : triangle_on_edge(i,j)) { w = cot(angle(i,j,t)); L(i,j) = w; sum += w; } L(i,i) = -sum; } }

On the other hand the Laplacian \( \mathbf L \) may be built by summing together contributions for each triangle, this way only the list of triangles is needed:

for(triangle t : triangles) { for(edge i,j : t) { w = cot(angle(i,j,t)); L(i,j) += w; L(j,i) += w; L(i,i) -= w; L(j,j) -= w; } }

No comments