Digital Representation and Analysis of Shapes

Contents

• Introduction and overview
• 0. Refresher: convexity, least squares, eigenvalues
• 1. Representing a shape: meshes and half-edges
• 2. Voronoi diagrams and duality
• 3. Delaunay triangulations: the empty circle criterion
• 4. Sampling and reconstruction of surfaces
• 5. Smoothing: from uniform to cotangent Laplacian
• 6. Simplification and remeshing
• 7. Discrete curvature and Gauss–Bonnet
• 8. The spectrum of shapes
• 9. Combinatorial topology: Euler, Betti, persistence
• 10. Course research notes (Desbrun, Memari)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: a data or 3D engineer who has handled points or a mesh and wants reliable tools for sampling, smoothing and comparing shapes. Empirical first: each topic starts from a failure you can observe — a poorly normalized LiDAR cloud that gives a leaky reconstruction, a badly discretized Laplacian whose smoothing melts the corners — and only then names the notions that fix it: half-edges, curvature, spectral signatures.

The module lays the discrete geometric foundations that Geometric Deep Learning (M2) builds on.

What you will be able to do

• Represent surfaces with meshes and manipulate the half-edge structure that encodes them.
• Generate smooth 2D curves — interpolation, splines, Hermite, Bézier — and evaluate them with the de Casteljau algorithm.
• Build Voronoi diagrams and Delaunay triangulations, and move from one to the other by duality.
• Reconstruct a continuous surface from a point cloud, with sampling guarantees.
• Smooth a mesh with the discrete Laplacian — from the uniform Laplacian to cotangent weights — while preserving details.
• Simplify and remesh a surface without denaturing its geometry.
• Compute discrete curvatures and verify the Gauss–Bonnet relation on real meshes.
• Use the spectrum of a shape (eigenvalues of the Laplacian) as a signature to compare it with others.
• Read the topological invariants of a shape: Euler characteristic, Betti numbers, persistence.

Official objectives and syllabus (2026-2027 catalog)

The official description announces the project: “this course will introduce the fundamental concepts of computer-based shape creation and analysis”, starting with “generating and representing smooth curves in 2D using splines and Bézier curves”, then the 3D representation techniques — with the emphasis on “triangular meshes and the associated methods” — and, in parallel, shape analysis methods up to “the definition and the computation of the similarity between shapes and shape correspondences”.

These materials follow exactly this arc, from 2D curves to non-rigid correspondences. Official prerequisites: not displayed; the assessment rests on the lab assignments turned in and the quizzes, with no written exam (an oral resit if necessary). The table follows the “Programme détaillé” of the sheet, in its order.

The 2D curves (def. 1.5–1.6), surface subdivision (def. 6.5), rigid registration (def. 4.6) and non-rigid correspondences (def. 8.4) were added earlier; against the 2026-2027 sheet, point-cloud processing (def. 4.7), feature detection (def. 7.5) and spectral segmentation (def. 8.5), until then only named in passing, were added: all official topics are now covered. Our extensions, beyond the official syllabus: the refresher chapter 0, the geometric signal processing of chapter 5 (smoothing operators beyond what is asked), the combinatorial topology of chapter 9 (Euler, Betti, persistence — a bridge to the TDA module) and chapter 10 (research of the course instructors).

Where this course fits in the program

Module of period 1 of M1 (36 h, 4.5 ECTS), one of the “Choose 3” electives of Period 1 and preselected by the AI-systems route of the home page (signal, vision, 3D shapes): a geometric specialization choice particularly relevant if you are aiming for 3D data, image synthesis or learning on shapes.

• Prerequisites — official: not communicated on the course description. Internally: the programming fluency of the Refresher in Computer Science and foundations in linear algebra; the refresher chapter covers convexity, least squares and eigenvalues, the three recurring tools of the course.
• Downstream modules — the Laplacian and the spectrum of shapes studied here are at the heart of Analysis and Deep Learning on Geometric Data (M2), which generalizes neural networks to surfaces and graphs; the representation of meshes also serves Image Synthesis: Theory and Practice in P2 for surface rendering.

Course outline

• Refresher: convexity, least squares, eigenvalues — the three algebraic pillars reactivated before tackling geometry.
• Representing a shape: meshes and half-edges — first the smooth 2D curves (interpolation, splines, Bézier, de Casteljau), then the fundamental data structure of discrete surfaces.
• Voronoi diagrams and duality — partitioning space by nearest neighbor, and what duality says about it.
• Delaunay triangulations: the empty circle criterion — the canonical triangulation and its properties.
• Sampling and reconstruction of surfaces — from point cloud to surface, with guarantees — not forgetting rigid registration (ICP), which aligns the acquisitions.
• Smoothing: from uniform to cotangent Laplacian — the central operator of all shape analysis.
• Simplification and remeshing — reducing the number of elements while preserving geometry, or on the contrary refining by surface subdivision.
• Discrete curvature and Gauss–Bonnet — measuring curvature on a polyhedral object, and the theorem that ties it all together.
• The spectrum of shapes — the eigenvalues of the Laplacian as a shape’s fingerprint, up to non-rigid correspondences.
• Combinatorial topology: Euler, Betti, persistence — Euler’s formula, a recall of the Betti numbers and persistence taught in the TDA module, and the alpha filtration that a point cloud carries.
• Course research notes (Desbrun, Memari) — the research work of Desbrun and Memari related to the course; the functional maps of chapter 8 come from the work of the other coordinator, Maks Ovsjanikov.
• Exercises, Projects and assessment and References — systematic training, project subjects with a sample exam and a rubric, and sources to go further.

Session plan

36 h in class = 12 sessions of 3 h. The volume is the one of the SynapseS 2026–2027 sheet (36 h in person, no lecture / lab split displayed); the sheet lists its programme but publishes no session-by-session plan, so the split below is our proposal for covering these notes in that time; it follows the order of the sheet’s programme except that Voronoi and Delaunay (ch. 2–3) are taught before reconstruction, which needs them.

Level 1 = foundations (refreshers, representations, first worked examples), 2 = core algorithms and their proofs, 3 = advanced material (spectral analysis, persistence); the level never goes down from one session to the next.

Two topics are recalled rather than re-taught: homology and persistence, taught in Topological Data Analysis ch. 3–4, and the proofs of the spectral invariances, given in Geometric Data (Year 2). The time saved goes to the two labs of sessions 10 and 12.

Self-study, outside the 36 h (about 1.5 h in total): ch. 10 Course research notes (Desbrun, Memari) — discrete exterior calculus and geometric tomography, read as an opening toward internships and the M2 (≈ 1.5 h).

How to study this module

• Work through the refresher chapter seriously, even if it seems easy: least squares and eigenvalues come back in half of the course.
• Draw! Voronoi, Delaunay and duality are understood with pencil and paper on small 2D examples before being coded.
• Implement the half-edge structure yourself once: you will durably understand what a mesh is.
• For each operator (smoothing, curvature), test on a sphere then on a real shape: the cases where theory is exact serve as unit tests.
• Connect every concept to the Laplacian: smoothing, spectrum, and later the spectral filters of GNNs are the same object seen from different angles.
• Redo the exercises of each section before moving on to the next; they build the reflexes used in the graded assignments.

0. Refresher: convexity, least squares, eigenvalues

This chapter reactivates the three algebraic tools that the geometric chapters use constantly — convex hulls, least squares and the spectral theorem — and shows on one example how convex hulls, Voronoi diagrams and Delaunay triangulations are three faces of the same object.

Notation. This page follows the site-wide notation conventions, without deviations. On a mesh graph, A is the adjacency matrix and D the degree matrix, with L = D - A. The cotangent stiffness matrix is L_c and the mass matrix is M (ch. 5, 8). Laplacian eigenvalues are sorted in increasing order and numbered from 1, and the mean-curvature normal follows \Delta x = -2H\mathbf{n} with the outward normal (ch. 7).

1. Representing a shape: meshes and half-edges

Concrete scene: a 3D reconstruction pipeline that “works” in the lab and fails as soon as the density of the cloud changes. Before any algorithm, one must decide how a shape is stored in memory; this chapter compares the possible representations, then studies the two that the course uses most: triangle meshes, with their half-edge structure, and smooth 2D curves.

2. Voronoi diagrams and duality

Given a set of sites — sensors, shops, sample points of a surface — which site is closest to each point of space? The Voronoi diagram answers this question once and for all by cutting space into cells; this chapter defines it, proves its basic properties and computes a small example by hand.

import numpy as np
from scipy.spatial import Voronoi, Delaunay

rng = np.random.default_rng(0)
P = rng.uniform(0, 1, (60, 2))

vor = Voronoi(P)          # Voronoi diagram
dela = Delaunay(P)        # dual triangulation

# --- numerical verification of the empty circle criterion (chapter 3) ---
def circumcenter(a, b, c):
    d = 2 * (a[0]*(b[1]-c[1]) + b[0]*(c[1]-a[1]) + c[0]*(a[1]-b[1]))
    ux = ((a[0]**2+a[1]**2)*(b[1]-c[1]) + (b[0]**2+b[1]**2)*(c[1]-a[1])
          + (c[0]**2+c[1]**2)*(a[1]-b[1])) / d
    uy = ((a[0]**2+a[1]**2)*(c[0]-b[0]) + (b[0]**2+b[1]**2)*(a[0]-c[0])
          + (c[0]**2+c[1]**2)*(b[0]-a[0])) / d
    return np.array([ux, uy])

worst = np.inf
for tri in dela.simplices:                 # for each Delaunay triangle
    a, b, c = P[tri]
    o = circumcenter(a, b, c); r = np.linalg.norm(a - o)
    dmin = min(np.linalg.norm(P[j] - o) for j in range(len(P))
               if j not in tri)
    worst = min(worst, dmin - r)           # must remain >= 0 (margin)
print("minimal empty circle margin:", round(worst, 6))   # ~1e-2 or more

# --- Lloyd relaxation: toward a centroidal diagram ---
for _ in range(20):
    vor = Voronoi(P)
    for i, reg in enumerate(vor.point_region):  # cell of site i
        r_idx = vor.regions[reg]
        if r_idx and -1 not in r_idx:           # skip unbounded cells
            poly = vor.vertices[r_idx]
            c = poly.mean(axis=0)           # approx. of the cell centroid
            P[i] = 0.8 * P[i] + 0.2 * c     # damped displacement
# result: sites almost coincident with the centroids of their cells

3. Delaunay triangulations: the empty circle criterion

A point set can be triangulated in many ways, and most of them contain long, flat triangles that ruin interpolation and simulation. This chapter characterizes the best one, the Delaunay triangulation, by an empty-circle criterion, proves that it maximizes the smallest angle, and gives an algorithm to build it.

4. Sampling and reconstruction of surfaces

A scanner returns points, not a surface. This chapter asks when a set of points carries enough information to recover the surface it was sampled from, and presents the main ways of rebuilding a mesh from it — after aligning the separate scans with ICP.

Processing point clouds: neighbourhoods, normals, outliers

The official programme pairs the point-cloud representation with its processing algorithms. Raw scans carry no connectivity, no normals and some outliers; three local operations, all built on nearest neighbours, turn them into the input that reconstruction (Poisson needs oriented normals) and registration expect.

5. Smoothing: from uniform to cotangent Laplacian

Scanned meshes are noisy, and the natural cure is to move each vertex toward the average of its neighbors. This chapter shows why this naive smoothing shrinks the shape, and how the cotangent Laplacian — the discrete version of the Laplace–Beltrami operator — gives a smoothing that respects the geometry.

6. Simplification and remeshing

A scanned statue may have ten million triangles, while a game needs ten thousand. This chapter shows how to remove triangles while controlling the geometric error (quadric error metrics), how to make a mesh regular again (remeshing), and how to go the other way, from a coarse mesh to a smooth surface (subdivision).

7. Discrete curvature and Gauss–Bonnet

Curvature tells a corner from a flat zone and a bump from a saddle, but its classical definition needs second derivatives, which a mesh does not have. This chapter defines curvature on a polyhedral surface through angles and cotangents, and proves that the discrete Gauss–Bonnet theorem holds exactly.

Feature detection on meshes

The official programme lists feature detection with curvature. On a mesh, “features” are the sharp creases, the corners and the salient points used as landmarks for matching; all are read from the discrete quantities of this chapter and of chapter 1.

import numpy as np
from collections import defaultdict

def subdivided_cube():
    """Unit cube, each face split into 4 triangles around its centre (Example 7.4)."""
    P = [np.array(c, float) for c in np.ndindex(2, 2, 2)]   # the 8 corners
    F = []
    for axis in range(3):
        for side in (0.0, 1.0):
            ring = [i for i in range(8) if P[i][axis] == side]
            u, v = [a for a in range(3) if a != axis]
            ring.sort(key=lambda i: np.arctan2(P[i][v] - .5, P[i][u] - .5))
            c = np.full(3, .5); c[axis] = side
            P.append(c); ic = len(P) - 1
            for a, b in zip(ring, ring[1:] + ring[:1]):      # outward orientation
                out = np.cross(P[a] - c, P[b] - c) @ (c - .5) > 0
                F.append((ic, a, b) if out else (ic, b, a))
    return np.array(P), np.array(F)

def detect_features(P, F, tau=45.0):
    """Sharp edges (dihedral deviation > tau degrees), corners, angle deficits."""
    N = np.cross(P[F[:, 1]] - P[F[:, 0]], P[F[:, 2]] - P[F[:, 0]])
    N /= np.linalg.norm(N, axis=1, keepdims=True)
    faces_of = defaultdict(list)                       # edge -> its two faces
    for f, t in enumerate(F):
        for k in range(3):
            faces_of[tuple(sorted((t[k], t[(k + 1) % 3])))].append(f)
    sharp = []
    for e, (f, g) in faces_of.items():
        dev = np.degrees(np.arccos(np.clip(N[f] @ N[g], -1, 1)))
        if dev > tau:
            sharp.append(e)
    deficit = np.full(len(P), 2 * np.pi)               # Definition 7.2
    for t in F:
        for k in range(3):
            i, j, l = t[k], t[(k + 1) % 3], t[(k + 2) % 3]
            a, b = P[j] - P[i], P[l] - P[i]
            deficit[i] -= np.arccos(a @ b / np.linalg.norm(a) / np.linalg.norm(b))
    n_sharp = np.bincount(np.ravel(sharp), minlength=len(P)) if sharp else np.zeros(len(P), int)
    return sharp, np.flatnonzero(n_sharp >= 3), deficit

P, F = subdivided_cube()
rng = np.random.default_rng(0)
for noise in (0.0, 0.01, 0.3):
    Q = P + noise * rng.standard_normal(P.shape)
    sharp, corners, deficit = detect_features(Q, F)
    print(f"noise {noise}: {len(sharp)} sharp edges, {len(corners)} corners, "
          f"total deficit / pi = {deficit.sum() / np.pi:.6f}")

8. The spectrum of shapes

How can a computer recognize that two meshes represent the same object in different poses, when their coordinates have nothing in common? This chapter uses the eigenvalues and eigenfunctions of the Laplacian, which do not change when a shape is bent without stretching, as a fingerprint of the shape and as a basis for matching.

Spectral segmentation

Segmentation — cutting a shape into meaningful parts — is listed by the official programme among the analysis tasks. The spectrum gives a principled cut: the second eigenvector of the Laplacian, the Fiedler vector, varies slowly inside well-connected parts and fast across narrow necks.

import numpy as np
import scipy.sparse as sp
from scipy.sparse.linalg import eigsh

def peanut(n_theta=41, n_phi=60):
    """Closed star-shaped surface r = 1 + 0.6 cos(2 theta): two lobes, a waist at z = 0."""
    th = np.linspace(0, np.pi, n_theta + 1)[1:-1]
    ph = np.linspace(0, 2 * np.pi, n_phi, endpoint=False)
    T, Ph = np.meshgrid(th, ph, indexing="ij")
    R = 1 + 0.6 * np.cos(2 * T)
    P = np.c_[(R * np.sin(T) * np.cos(Ph)).ravel(),
              (R * np.sin(T) * np.sin(Ph)).ravel(), (R * np.cos(T)).ravel()]
    P = np.vstack([P, [0, 0, 1.6], [0, 0, -1.6]])      # the two poles
    N, S, m = len(P) - 2, len(P) - 1, n_theta - 1
    v = lambda i, j: i * n_phi + j % n_phi
    F = []
    for j in range(n_phi):
        F += [(N, v(0, j), v(0, j + 1)), (S, v(m - 1, j + 1), v(m - 1, j))]
        for i in range(m - 1):
            F += [(v(i, j), v(i + 1, j), v(i + 1, j + 1)),
                  (v(i, j), v(i + 1, j + 1), v(i, j + 1))]
    return P, np.array(F)

def cotan_laplacian(P, F):
    """PSD cotangent stiffness L_c and lumped (barycentric) mass matrix M."""
    rows, cols, vals = [], [], []
    for k in range(3):
        i, j, o = F[:, k], F[:, (k + 1) % 3], F[:, (k + 2) % 3]
        u, w = P[i] - P[o], P[j] - P[o]                # angle at o faces edge (i, j)
        cot = (u * w).sum(1) / np.linalg.norm(np.cross(u, w), axis=1)
        rows += [i, j]; cols += [j, i]; vals += [-cot / 2, -cot / 2]
    n = len(P)
    Lc = sp.csr_matrix((np.concatenate(vals), (np.concatenate(rows), np.concatenate(cols))), (n, n))
    Lc = Lc - sp.diags(np.asarray(Lc.sum(axis=1)).ravel())   # rows sum to zero
    area = np.linalg.norm(np.cross(P[F[:, 1]] - P[F[:, 0]], P[F[:, 2]] - P[F[:, 0]]), axis=1) / 2
    mass = np.zeros(n)
    for k in range(3):
        np.add.at(mass, F[:, k], area / 3)
    return Lc, sp.diags(mass)

P, F = peanut()
Lc, M = cotan_laplacian(P, F)
lam, phi = eigsh(Lc, k=4, M=M, sigma=-1e-3)            # eigenvalues closest to 0
order = np.argsort(lam); lam, phi = lam[order], phi[:, order]
fiedler = phi[:, 1]                                     # phi_2 (numbered from 1)
print("lambda_1..4:", np.round(lam, 4))
side = np.sign(fiedler) == np.sign(fiedler[-2])        # same side as the north pole
print("cut agrees with z > 0 on", np.mean(side == (P[:, 2] > 0)))

9. Combinatorial topology: Euler, Betti, persistence

Some properties of a shape survive any deformation: the number of pieces, of handles, of cavities. This chapter counts them combinatorially on a mesh with the Euler characteristic, recalls the Betti numbers and the persistence taught in the TDA module, and builds the filtration that a point cloud carries naturally: the alpha complex of chapter 4.

10. Course research notes (Desbrun, Memari)

Exercises

1. ★ Guided duality. For the sites p_1 = (0,0), p_2 = (4,0), p_3 = (0,3) of Example 2.4: (a) verify that (2, 1.5) is at distance 2.5 from the three sites; (b) draw the three perpendicular bisectors and the unbounded cell of p_2; (c) add p_4 = (4,3) — why are the four points cocircular, and which Delaunay triangulations does one obtain (lift the degeneracy by perturbation)?

2. ★ Guided lift and incircle. (a) Implement the test of Theorem 3.4: for each triangle of Delaunay (scipy), construct the plane \Pi and verify that no lifted point is under \Pi (tolerance 10^{-12}). (b) Compare with the incircle determinant (signs: interior/exterior). (c) Perturb a point toward the circumcircle of a neighboring triangle: observe the flip in the computed triangulation.

3. ★ Guided shrinking. (a) Complete the proof of Theorem 5.2: why does mode j decay exactly like \rho_j^k? What happens for \lambda > 1?

   (b) Simulate a ring of radius 1, n = 50, \lambda = 0.5; plot the mean radius — by how much does it shrink in 100 iterations?

   (c) Apply Taubin \lambda = 0.5, \mu = -0.53 and measure.

4. ★ QEM. (a) Recover Example 6.3 (cube corner) in detail: write Q, b, c, verify Q = I. (b) Two perpendicular planes x = 0, y = 0 plus a “ceiling” plane z = 1: where does the optimal point fall and what is the cost? (c) Implement quadric edge contractions on a torus mesh (libigl) and plot the Hausdorff error as a function of the number of faces.

5. ★ Gauss–Bonnet. (a) Verify Theorem 7.3 on the tetrahedron and the cube (by hand), then on the minimal 3 \times 3 torus (9 vertices, 27 edges, 18 faces — \chi = 0). (b) Show that an edge split does not change \chi (counting). (c) Subdivide the cube 3 times and numerically verify the invariance of the total deficit.

6. ★★ Empty circle criterion. In a convex quadrilateral, \angle abc = 70° and \angle adc = 125° (diagonal ac). (a) Decide whether a flip is needed (Theorem 3.2). (b) After the flip, what is at least the smallest of the angles opposite the new diagonal? (c) Prove point (ii) of the proof: b \in \mathrm{disk}(a,c,d) \iff d \in \mathrm{disk}(a,b,c) for a convex quadrilateral.

7. ★★ Lloyd. (a) Show that Lloyd relaxation decreases the quantization energy \mathcal{E} = \sum_i \int_{\mathcal{V}(p_i)} \|x - p_i\|^2\,dx (each iteration is an alternation: optimal cells for the sites, then optimal centroids for the cells). (b) Implement and plot \mathcal{E} (approximated by sampling) as a function of iterations on 100 points of the square.

8. ★★ Spectra. (a) Prove the formula of Example 8.2 for the path (verify that u^{(k)}_i = \sin\frac{k\pi i}{n+1} is an eigenvector). (b) Compute the first 10 cotangent eigenvalues of a flat strip mesh and of the same bent strip (isometric); compare. (c) Discuss: why do the spectra diverge in practice (sampling, triangulation) while theory predicts equality?

9. ★★ A functional map by least squares. (a) Prove the expression of the commutativity term given in Definition 8.4, and derive the k row systems.

   (b) Take the peanut of Lab 8.7 and a copy whose vertices are randomly permuted (faces renumbered accordingly) and rotated: an exact isometry with a known answer. With k = 10 eigenfunctions, the HKS at five times from 0.01 to 1 as descriptors and \gamma = 10^{-3}, compute C and the point-to-point map, and count the vertices sent to their true image.

   (c) Almost none are: explain why, from the symmetries of the peanut and the double eigenvalues of Lab 8.7. Then push the surface out by two Gaussian bumps at non-symmetric places and repeat: C becomes diagonal with entries \pm 1, and every vertex is matched.

10. ★★ Guided persistence. (a) Build the alpha filtration of the noisy ring of Example 9.3, for instance with GUDHI’s AlphaComplex (its filtration values are squared radii: take square roots to compare with Definition 9.2), and check the central H_1 bar against the example.

    (b) Increase σ from 0.1 to 0.5 and plot the lengths of the two longest H_1 bars. At what σ does the central bar stop standing out, and why does its death value fall as σ grows? Compare with the heuristic σ ≈ hole radius / 3, at which the noise starts to carry points to the centre of the hole.

    (c) Replace the ring by two disjoint rings and verify \beta_1 = 2.

Projects and assessment

The official assessment, as quoted in the fiche above, is “lab assignments turned in during the semester and quizzes — no written exam; oral resit if necessary” (sections of the engineering degree and of the exchange programs; the LLGA section of the 2026–2027 sheet is empty). The solo subjects below are sized like a graded lab assignment and the group subjects like a course project. Since the course has no written exam, the exam below is a sample of what the quizzes and the oral resit can test. Everything in this section is a proposal, not an official rule.

The projects exercise mainly O6 (multimodal generative AI, through its 3D side: representing, reconstructing and matching shapes) and O4 (graph-structured data: a mesh is a graph, and its Laplacian is the one of Graph ML), with O7 (hands-on geometry processing on public scans) throughout and O1 for the learning subject. The retrieval subject builds, at course scale, the non-learned spectral baseline (ShapeDNA, HKS) that the learned shape tower of the Year 2 capstone Y2.3 is compared with, and every subject prepares Geometric Data (Year 2).

Solo projects

1. [Solo · ≈ 20 h] A half-edge library tested by its own invariants. Paper: Garland and Heckbert (1997), Surface simplification using quadric error metrics, SIGGRAPH.
   • Question: can a small NumPy library match a reference implementation on simplification quality, and which invariants of the course catch its bugs?
   • Work: implement a half-edge mesh (Proposition 1.3) with QEM edge collapses (Definition 6.1, Theorem 6.2), Loop subdivision (Definition 6.5) and uniform, Taubin and cotangent smoothing (ch. 5). Turn the course’s invariants into unit tests: the planar test of Example 5.4, V - E + F kept by every collapse that passes the link condition, the total angle deficit 2\pi\chi of Theorem 7.3 kept by subdivision and simplification, the volume nearly kept by Taubin smoothing.
   • Data: the Stanford Bunny and Armadillo (Stanford 3D Scanning Repository), and the minimal torus of Exercise 5.
   • Success: every invariant test passes on every mesh; at 10 %, 5 % and 1 % of the faces, a symmetric Hausdorff error within 10 % of MeshLab’s quadric edge-collapse decimation (through PyMeshLab), measured with the same point sampling.
   • Deliverables: code with its tests, 4–6 page report, 10-minute talk. Chapters: ch. 1, ch. 5, ch. 6, ch. 7, ch. 9.
2. [Solo · ≈ 20 h] Spectral shape retrieval across poses. Papers: Reuter, Wolter and Peinecke (2006), Laplace–Beltrami spectra as “Shape-DNA” of surfaces and solids, Computer-Aided Design; Sun, Ovsjanikov and Guibas (2009), A concise and provably informative multi-scale signature based on heat diffusion, SGP. It builds the spectral baseline of the shape tower of the capstone Y2.3.
   • Question: how well do the spectrum and the heat kernel signature recognise an object in a new pose, and how much does remeshing perturb them?
   • Work: assemble L_c and M as in Lab 8.7 and compute the first 51 eigenpairs per shape (\lambda_1 = 0 and 50 non-zero values). Compare three global descriptors: ShapeDNA (the eigenvalues \lambda_2, \dots, \lambda_{51}, normalised by the area), a histogram of the HKS at a few times (Proposition 8.3), and the extrinsic D2 shape distribution of Osada, Funkhouser, Chazelle and Dobkin (2002) as a baseline. Then remesh each shape to 2,000 and 8,000 vertices (Definition 6.4) and plot the relative drift of \lambda_k against k.
   • Data: TOSCA high-resolution (Bronstein, Bronstein and Kimmel, 2008): 80 meshes of animals and people, each in several poses.
   • Success: leave-one-out nearest-neighbour accuracy and mean average precision of the class for the three descriptors, with the intrinsic ones ahead of D2 on the classes that change pose, or the gap explained; the index where the drift exceeds 1 %, compared with the \sqrt{N} rule of ch. 8.
   • Deliverables: code, 4–6 page report, 10-minute talk. Chapters: ch. 5, ch. 6, ch. 8.
3. [Solo · ≈ 20 h] Functional maps reproduced on FAUST. Paper: Ovsjanikov, Ben-Chen, Solomon, Butscher and Guibas (2012), Functional maps: a flexible representation of maps between shapes, ACM Transactions on Graphics (SIGGRAPH).
   • Question: how much does the commutativity term of Definition 8.4 improve a map computed from descriptors alone, and how does the answer depend on the number k of eigenfunctions?
   • Work: implement the row-by-row least-squares solver of Definition 8.4 (Exercise 9), with HKS descriptors at several times and the indicators of feature points (Definition 7.5). Compare \gamma = 0 with \gamma > 0, for k from 10 to 60, against direct nearest-neighbour matching of the HKS; then remesh one shape of each pair (Definition 6.4) and repeat.
   • Data: FAUST (Bogo, Romero, Loper and Black, 2014), ten people in ten poses with ground-truth correspondences; pairs of poses of one person, then of two people.
   • Success: the cumulative geodesic-error curve of Kim, Lipman and Funkhouser (2011), with geodesics approximated by Dijkstra on the mesh edges; the functional map above the HKS baseline at every radius; left–right symmetric flips counted and explained (Exercise 9c).
   • Deliverables: code, 4–6 page report, 10-minute talk. Chapters: ch. 5, ch. 7, ch. 8.

Group projects

1. [Group of 3 · ≈ 30 h each] From scans to a watertight mesh, with guarantees. Papers: Hoppe, DeRose, Duchamp, McDonald and Stuetzle (1992), Surface reconstruction from unorganized points, SIGGRAPH; Kazhdan, Bolitho and Hoppe (2006), Poisson surface reconstruction, SGP.
   • Question: how do sampling density and noise drive the error and the topology of a reconstruction, and does the \varepsilon-sampling picture of Definition 4.1 predict the failures?
   • Work: simulate partial depth scans of a known mesh from 6 to 10 viewpoints by ray casting, with controlled density and Gaussian noise. Clean them (statistical outliers), estimate and orient PCA normals (Definition 4.7), align them with ICP and a point-to-plane or trimmed variant (Definition 4.6), and reconstruct by marching cubes on a signed distance and by Poisson (ch. 4). Then run the pipeline on the ten original range scans of the Stanford Bunny.
   • Split: scan simulation and cleaning; registration; reconstruction and evaluation.
   • Success: the symmetric Hausdorff error to the ground-truth mesh against density and noise, decreasing as the samples densify (Proposition 4.2); watertight outputs with V - E + F = 2 (ch. 1, ch. 9); every topological failure traced to a region sampled coarsely compared with the reach.
   • Deliverables: code, joint 8–10 page report, 20-minute talk. Chapters: ch. 1, ch. 4, ch. 9.
2. [Group of 3 · ≈ 30 h each] From the cotangent Laplacian to a spectral GNN on meshes. Paper: Sharp, Attaiki, Crane and Ovsjanikov (2022), DiffusionNet: discretization agnostic learning on surfaces, ACM Transactions on Graphics. Connects this course to Graph ML, ch. 4–5 and to Geometric Data, ch. 6.
   • Question: for vertex segmentation, what does a learned model gain over the unsupervised Fiedler cut, and does the cotangent Laplacian make it robust to remeshing where a graph operator fails?
   • Work: compare (i) a GCN on the mesh graph with HKS input features, (ii) a spectral network filtering in the first 128 eigenvectors of L_c\phi = \lambda M\phi, (iii) the same network with the uniform Laplacian, (iv) a DiffusionNet-style model with learned diffusion times, and (v) recursive Fiedler cuts (Definition 8.5) as the unsupervised baseline.
   • Data: the human-body segmentation dataset of Maron et al. (2017), eight body parts with its standard train / test split, as used by DiffusionNet; test meshes also remeshed with Definition 6.4.
   • Split: data, operators and the Fiedler baseline; GCN and spectral networks; DiffusionNet-style model and the remeshing study.
   • Success: per-vertex test accuracy (mean ± spread over 3 seeds) of the five methods on the original and remeshed test sets; a smaller drop under remeshing for the cotangent operators than for the graph and uniform ones, or the reason why not.
   • Deliverables: code, joint 8–10 page report, 20-minute talk. Chapters: ch. 5, ch. 6, ch. 8.
3. [Group of 2 · ≈ 25 h each] Choosing α by persistence for alpha-shape reconstruction. Paper: Edelsbrunner, Kirkpatrick and Seidel (1983), On the shape of a set of points in the plane, IEEE Transactions on Information Theory. Connects this course to Topological Data Analysis, ch. 4–5.
   • Question: a fixed α must be tuned for every cloud; can the barcode of the alpha filtration choose α so that the reconstruction has the right Betti numbers?
   • Work: implement the alpha filtration of Definition 9.2 in 2D with scipy’s Delaunay and its persistence, then use GUDHI’s AlphaComplex in 3D. Choose α in the widest gap of the barcode, after the noise bars have died and before the first long bar dies. Compare with a fixed α tuned on one cloud and with Poisson reconstruction.
   • Data: synthetic clouds of known topology (rings, two rings, sphere, torus, double torus), then meshes of Thingi10K (Zhou and Jacobson, 2016) whose genus is listed, sampled with noise and with non-uniform density.
   • Split: filtration and persistence; the choice of α and the reconstructions; the noise and sampling study.
   • Success: the fraction of clouds rebuilt with the correct Betti numbers, against noise and non-uniformity, higher for the persistence rule than for the fixed α at every level, or each failure explained (Example 9.3: a hole that the data have filled).
   • Deliverables: code, joint 6–8 page report, 15-minute talk. Chapters: ch. 3, ch. 4, ch. 9.

Written exam (proposal)

Two hours, no documents, no electronic device; four questions. The official assessment has no written exam: this is a sample of what the quizzes and the oral resit can test.

1. Question (5 points). Explain why uniform Laplacian smoothing shrinks a closed mesh, how Taubin’s λ|μ scheme prevents it, and why the cotangent Laplacian is preferred on irregular meshes. State the test that checks an implementation of the cotangent Laplacian.

   Expected: on a ring, the iteration multiplies the mode of frequency j by \rho_j = 1 - \lambda(1 - \cos\frac{2\pi j}{n}) (Theorem 5.2). The mean is kept and every other mode decays, so the shape collapses to its barycentre.

   Taubin alternates a step \lambda > 0 and a step \mu < -\lambda. With k an eigenvalue of L_{\mathrm{rw}}, the mode is multiplied by (1 - \lambda k)(1 - \mu k), slightly above 1 below the pass-band frequency k_{\mathrm{PB}} = 1/\lambda + 1/\mu and below 1 above it: the noise goes and the volume stays.

   The uniform Laplacian sees only the connectivity: on an irregular mesh it drifts vertices tangentially and converges to no geometric operator. The cotangent Laplacian is the finite-element discretization of Laplace–Beltrami (Definition 5.3). The check is the planar test of Example 5.4: on a planar mesh every interior \delta_i vanishes.

2. Question (6 points). The regular octahedron has the six vertices \pm e_1, \pm e_2, \pm e_3.

   1. Give V, E, F and \chi. (b) Compute the angle deficit of each vertex and check Theorem 7.3. (c) Compute the cotangent weight of an edge and the barycentric area of a vertex.

   2. Compute the mean-curvature normal at e_3 by Definition 7.2, and compare with the circumscribed sphere. (e) Where does one step of uniform smoothing with \lambda = 1/2 send e_3?

   Expected: (a) (V, E, F) = (6, 12, 8) and \chi = 6 - 12 + 8 = 2. (b) Four angles of 60° meet at each vertex, so the deficit is 2\pi - 4\pi/3 = 2\pi/3, and the total is 6 \cdot 2\pi/3 = 4\pi = 2\pi\chi.

   3. Both angles opposite an edge are 60°, so w_{ij} = \tfrac12 \cdot 2\cot 60° = 1/\sqrt3. A face of side \sqrt2 has area \sqrt3/2, so A_i = 4 \cdot \tfrac{\sqrt3}{2} / 3 = 2/\sqrt3.

   4. The four neighbours of e_3 sum to zero, so \frac{1}{A_i}\sum_j w_{ij}\,(p_j - e_3) = \frac{\sqrt3}{2}\cdot\Big(-\frac{4}{\sqrt3}\Big)e_3 = -2e_3 = -2H\mathbf{n}. Hence H = 1 with the outward normal \mathbf{n} = e_3: exactly the mean curvature of the circumscribed unit sphere. (e) The neighbour average is 0, so e_3 \mapsto e_3/2: one step halves the octahedron, the shrinkage of Theorem 5.2.

3. Question (5 points). Take a = (0, 0), b = (2, -1), c = (4, 0), d = (2, 1), triangulated by the diagonal ac.

   1. Decide with Theorem 3.2 whether the diagonal must be flipped, and compare the smallest angles before and after. (b) Give the entry value of each simplex of the Delaunay triangulation in the alpha filtration (Definition 9.2), and the H_0 and H_1 barcodes.

   Expected: (a) At b, \cos\angle abc = \frac{(-2, 1)\cdot(2, 1)}{5} = -\frac35, \qquad \angle abc \approx 126.9° = \angle adc . The sum, 253.7°, exceeds 180°: the diagonal must be flipped to bd.

   The smallest angle goes from \arctan\frac12 \approx 26.6°, at a and c, to 53.1°, with 63.4° at b and d: the flip doubles it (Theorem 3.3).

   2. Vertices enter at 0. The diametral disk of bd, of centre (2, 0) and radius 1, misses a and c: the diagonal enters at 1.

   Each side has length \sqrt5 and its diametral disk misses the opposite vertex, so it enters at \sqrt5/2 \approx 1.118.

   The triangles abd and bcd have circumcentres (5/4, 0) and (11/4, 0), hence the circumradius 5/4 at which both enter.

   Barcodes: H_0 has [0, \infty), [0, 1) and twice [0, \sqrt5/2).

   At \sqrt5/2 the four sides close two loops, filled at 5/4 by the two triangles, so H_1 has twice [\sqrt5/2,\ 5/4).

4. Question (4 points). Let L = D - A be the Laplacian of a graph with weights w_{ij} > 0. (a) Prove that f^\top L f = \sum_{(i,j) \in E} w_{ij}\,(f_i - f_j)^2 .

   2. Deduce that L is positive semi-definite, and that the multiplicity of its eigenvalue 0 is the number of connected components. (c) Show that f = \mathbf{1}_{V_1} - \mathbf{1}_{V_2} gives f^\top L f = 4\,\mathrm{cut}(V_1, V_2).

   Expected: (a) f^\top L f = \sum_i d_i f_i^2 - \sum_{i,j} A_{ij} f_i f_j; an edge (i, j) contributes w_{ij}(f_i^2 + f_j^2) to the first sum and -2w_{ij} f_i f_j to the second, that is w_{ij}(f_i - f_j)^2.

   2. Every term is non-negative, so L \succeq 0. For a positive semi-definite matrix, Lf = 0 if and only if f^\top L f = 0, that is f_i = f_j on every edge: f is constant on each component, and the kernel is spanned by the indicators of the components.

   3. f_i - f_j is 0 inside a part and \pm 2 across, so each cut edge contributes 4w_{ij}.

Grading rubric (proposal)

References

• M. Desbrun, A. Hirani, M. Leok, J. Marsden, Discrete Exterior Calculus, 2005; M. Desbrun, E. Kanso, Y. Tong, Discrete Differential Forms for Computational Modeling; M. Meyer, M. Desbrun, P. Schröder, A. Barr, Discrete Differential-Geometry Operators for Triangulated 2-Manifolds, 2003 (mixed Voronoi, deficits).
• K. Crane, F. de Goes, M. Desbrun, P. Schröder, Digital Geometry Processing with Discrete Exterior Calculus, SIGGRAPH Asia Courses 2013 — notes: DDG.
• O. Amini, J.-D. Boissonnat, P. Memari, Geometric Tomography with Topological Guarantees, Discrete & Computational Geometry, 2013 (Springer version); team page: LIX — P. Memari.
• J.-D. Boissonnat, F. Chazal, M. Yvinec, Geometric and Topological Inference, Cambridge Texts, 2018 (sampling, reach, reconstruction); H. Edelsbrunner, Geometry and Topology for Mesh Generation, Cambridge, 2001 (alpha-shapes, filtrations).
• N. Amenta, M. Bern, Surface Reconstruction by Voronoi Filtering, Discrete & Computational Geometry, 1999; M. Kazhdan, M. Bolitho, H. Hoppe, Poisson Surface Reconstruction, SGP 2006; W. Lorensen, H. Cline, Marching Cubes, SIGGRAPH 1987.
• M. Garland, P. Heckbert, Surface Simplification Using Quadric Error Metrics, SIGGRAPH 1997; G. Taubin, A Signal Processing Approach to Fairing (λ|μ), ICCV 1995; U. Pinkall, K. Polthier, Computing Discrete Minimal Surfaces (cotangents), 1993.
• M. Reuter, F.-E. Wolter, N. Peinecke, Shape DNA (Laplace–Beltrami spectrum), CAD 2006; C. Gordon, D. Webb, S. Wolpert, One Cannot Hear the Shape of a Drum, Bull. AMS 1992; Sun, Ovsjanikov, Guibas, Heat Kernel Signature, SGP 2009.
• H. Edelsbrunner, J. Harer, Persistent Homology — a Survey, Contemporary Mathematics 2008; the library GUDHI (Inria) for the labs.
• Lab tools: SciPy (scipy.spatial: Voronoi, Delaunay, cKDTree), libigl, CGAL (alpha-shapes, Delaunay, reconstruction), MeshLab.