Three.js Delaunay & Voronoi Terrain (TIN)

Triangulated irregular network terrain in Three.js using Bowyer–Watson Delaunay triangulation of uniform, Poisson-disc or feature-adaptive samples, with the Voronoi dual drawn beneath.

Key topics: three.js delaunay, voronoi, triangulated irregular network, tin terrain, poisson disc, bowyer watson

What this code does

- Bowyer–Watson: points are inserted one by one, and triangles whose circumcircle contains the point are replaced by a fan.
- Delaunay Property: no point lies inside any triangle's circumcircle, which maximizes the minimum angle.
- Sampling: uniform random, Bridson Poisson-disc (blue noise) or feature-adaptive sampling that puts vertices where curvature is high.
- TIN Terrain: each triangle is flat-shaded and colored by elevation, the way GIS terrain is stored.
- Voronoi Dual: joining circumcentres of triangles that share an edge draws the Voronoi cells.
- Controls: sampling method, point count, height, triangle edges, Voronoi, sample points and reseed.

Continue Learning

JavaScript Implementation

ES6+
// Bowyer–Watson: insert points one by one, re-triangulating the cavity of "bad" triangles

function delaunay (points) {
  const pts = points.concat([[-1e5, -1e5], [1e5, -1e5], [0, 1e5]]) // super-triangle
  const n = points.length
  const circ = (a, b, c) => { /* circumcentre (x, y) and squared radius r2 of triangle abc */ }
  let tris = [circ(n, n + 1, n + 2)]
  points.forEach(([px, py], p) => {
    const edges = new Map()
    tris = tris.filter(t => {
      if ((px - t.x) ** 2 + (py - t.y) ** 2 >= t.r2) return true
      for (const [u, v] of [[t.a, t.b], [t.b, t.c], [t.c, t.a]]) {
        const k = Math.min(u, v) + ',' + Math.max(u, v)
        edges.has(k) ? edges.delete(k) : edges.set(k, [u, v]) // keep only boundary edges
      }
      return false
    })
    edges.forEach(([u, v]) => tris.push(circ(u, v, p)))
  })
  return tris.filter(t => t.a < n && t.b < n && t.c < n)
}