Polygon Triangulation Handoff Between CPU and GPU

Ear clipping — the algorithm every practical polygon triangulator is built on — walks a vertex ring removing one triangle at a time, and each removal changes the ring the next step examines. That data dependency makes it fundamentally sequential, which is the one shape of problem a GPU has nothing to offer. So triangulation stays on the CPU, and the interesting engineering question is not how to parallelise it but where exactly the boundary sits, what crosses it, and how to arrange things so a given polygon is triangulated once rather than once per frame. This page answers those three. It is one stage of geometry filtering with WGSL compute shaders.

Which half of polygon work goes where Two lanes divide polygon processing between the CPU and the GPU. The CPU lane holds the sequential work: parsing rings, checking winding order and ear-clipping into triangles, all of which depend on the result of the previous step and none of which parallelise. The GPU lane holds the parallel work: computing per-polygon bounding boxes as a reduction, culling whole polygons against the viewport with one test each, and drawing the surviving index ranges. A cache sits between the two so the sequential half runs once per polygon rather than once per frame. POLYGON WORK · SEQUENTIAL vs PARALLEL CPU (worker) GPU Parse rings outer + holes Check winding signed area per ring Ear clip sequential by nature Bounding boxes a reduction per polygon Cull polygons one test each Draw index ranges survivors only A cache between the lanes is what keeps the sequential half from running per frame.
The boundary is not arbitrary. Every box in the upper lane depends on the result of the box before it; every box in the lower lane is independent per element. That difference, not any property of the data, is what decides where the work belongs.

Runnable reference implementation

The boundary is a cache keyed on polygon identity, not on geometry. A triangulation is expensive to compute, cheap to store, and valid for the life of the polygon — so it belongs in a worker, behind a key, and its output crosses to the GPU as two buffers.

typescript
/** Triangulated output: what actually crosses to the GPU. */
interface Triangulated {
  vertices: Float32Array;   // interleaved x, y — tile-local residuals
  indices: Uint32Array;     // 3 per triangle, into `vertices`
}

const cache = new Map<string, Triangulated>();

/** Runs in a worker. `earcut` is the usual choice; any ear-clipper works. */
function triangulate(rings: number[][], holeStarts: number[]): Triangulated {
  const flat = rings.flat();
  const indices = earcut(flat, holeStarts, 2);   // 2 = dimensions per vertex
  return {
    vertices: new Float32Array(flat),
    indices: new Uint32Array(indices),
  };
}

/** Main thread: one triangulation per polygon, ever. */
async function getTriangulation(key: string, poly: PolygonSource): Promise<Triangulated> {
  const hit = cache.get(key);
  if (hit) return hit;
  const result = await runInWorker(poly);        // structured-clone the arrays back
  cache.set(key, result);
  return result;
}

The GPU side never sees a ring. It receives a vertex buffer and an index buffer and draws indexed triangles, and every subsequent operation — culling, filtering, styling — happens on triangles rather than on polygon topology.

wgsl
// The compute filter operates on per-polygon records, not per triangle.
// Each record names a contiguous index range, so culling a polygon means
// dropping a range rather than testing its triangles individually.
struct PolyRecord {
  bounds      : vec4<f32>,   // min_x, min_y, max_x, max_y
  index_start : u32,
  index_count : u32,
};
@group(0) @binding(0) var<storage, read>       polys   : array<PolyRecord>;
@group(0) @binding(1) var<storage, read_write> draws   : array<u32>;
@group(0) @binding(2) var<storage, read_write> draw_n  : atomic<u32>;
@group(0) @binding(3) var<uniform>             view    : vec4<f32>;

@compute @workgroup_size(256)
fn cull_polys(@builtin(global_invocation_id) gid : vec3<u32>) {
  let i = gid.x;
  if (i >= arrayLength(&polys)) { return; }
  let b = polys[i].bounds;
  // One bounding-box test per polygon, not per triangle.
  let visible = !(b.z < view.x || b.x > view.z || b.w < view.y || b.y > view.w);
  if (visible) { draws[atomicAdd(&draw_n, 1u)] = i; }
}

Parameter reference

Value Setting here Guidance
Cache key polygon id + version Never the geometry itself; hashing a ring costs more than the lookup saves.
Worker count 2–4 Triangulation is CPU-bound; more workers than physical cores adds scheduling noise, not throughput.
Vertex format tile-local f32 residuals The origin subtraction from coordinate precision happens before triangulation, not after.
Index width u32 u16 caps a polygon at 65 535 vertices, which real coastlines exceed.
Cull granularity per polygon One bounding-box test per polygon beats one per triangle by the triangle count.
Triangulating a complex polygon, by where it runs A bar chart in milliseconds of the cost of triangulating a coastline polygon with about 24 000 vertices. Running on the main thread costs about 41 milliseconds, which drops two and a half frames. Running in a worker costs the same 41 milliseconds of CPU time but none of it on the main thread, so the frame budget is untouched. Reading a pre-triangulated result from the server costs about 2 milliseconds, which is the buffer upload and nothing else. TRIANGULATING 24 K VERTICES · ms frame budget Main thread 41 ms — drops frames In a worker 41 ms, off the frame path Server-side 2 ms — upload only 0 9 18 27 36 45 ms blocks the frame same work, no stall upload only Modelled proportions; the ratio between the first two is exact, since it is the same computation.
The middle bar is the same work as the first and costs nothing visible, which is the whole argument for the worker. The third bar is the same work done once for every client that will ever ask for that tile.

What the GPU should do instead

Triangulation being sequential does not mean the GPU has nothing to contribute to polygon work. Three things around it parallelise well and are worth moving.

Bounding boxes. Computing a per-polygon extent is a reduction over its vertices, which is a compute pass, and having the extents on the GPU is what makes per-polygon culling possible without a readback.

Winding and orientation checks. Determining whether a ring is clockwise is a signed-area sum — one multiply-add per edge, perfectly parallel — and getting orientation wrong is the most common cause of holes rendering as solid. Doing it on the GPU at load, and storing a flag, avoids repeating it.

Simplification. Reducing vertex count before triangulation makes the sequential part faster, and simplification itself parallelises reasonably well; that is the subject of simplifying line geometry with a compute pass, and it applies to polygon rings equally.

The shape that emerges is a division of labour rather than a location: sequential topology on the CPU, parallel arithmetic on the GPU, and a cache in between so the sequential half runs once.

Keeping the cache honest

A triangulation cache is only useful if its entries stay valid, and validity here has a narrower definition than it first appears.

A triangulation depends on the ring geometry and on nothing else. It does not depend on the camera, the zoom, the style, or the viewport — so none of those belong in the key. It does depend on the simplification tolerance, if simplification runs before triangulation, which means a pipeline that changes tolerance with zoom has one triangulation per polygon per tolerance, and the key has to say so.

That is the usual reason a cache underperforms: keying on polygon id alone while quietly re-simplifying at each zoom produces a stream of cache hits returning geometry simplified for a different zoom, which renders subtly wrong, or a stream of misses if the key does include zoom. The honest fix is to make tolerance discrete — a small set of levels rather than a continuous function of zoom — and put the level in the key. Four or five levels covers a full zoom range and gives each one a real hit rate.

Eviction is the other half. Triangulated output is larger than the source ring, so a cache with no bound grows with every polygon the user has ever panned past. A byte-budgeted least-recently-used cache is the right structure, sized against host memory rather than VRAM, and the eviction cost is genuinely low: a re-triangulation is tens of milliseconds in a worker, off the frame path, and only for polygons that have come back into view.

Failure modes

  • Frame time spikes when a complex polygon enters the view. Triangulation is happening on the main thread. Move it to a worker; the spike is the whole reason the boundary exists.
  • Holes render as solid fill. Hole rings have the same winding as the outer ring. Ear clippers expect opposite windings; the check is a signed-area sum per ring.
  • A polygon flickers between frames. The cache key includes something that changes per frame — a style value, or the camera. Key on identity and version only.
  • The index buffer overflows at 65 535. u16 indices on a polygon with more vertices than that. Coastlines and administrative boundaries routinely exceed it.
  • Triangulation output is subtly wrong near tile edges. The origin subtraction happened after triangulation, so the ear clipper worked on full-magnitude coordinates and its area comparisons lost precision. Subtract first.
Triangulation failures and where they come from A table of four triangulation failures with cause and fix. Frame spikes when a complex polygon enters the view mean triangulation is running on the main thread. Holes rendering as solid fill mean the hole rings share the outer ring winding. A polygon flickering between frames means the cache key includes something that changes per frame. An index overflow past 65 535 means u16 indices on a polygon with more vertices than that. TRIANGULATION FAILURE · CAUSE · FIX Cause Fix frame spikes on entry running on the main thread move to a worker holes fill solid same winding as the outer signed-area check polygon flickers cache key changes per frame key on id + version index overflow u16 indices use u32 Check winding once at load and store a flag — recomputing it per frame is pure waste.
The winding row is the one that produces the most confusing output, because a hole rendered as fill looks like a data problem rather than a topology one and gets reported against the source.

Backend / Python interop note

The strongest version of this pipeline moves triangulation off the client entirely. A tile server that triangulates once, caches the result, and ships vertices and indices removes the CPU cost from every client that ever requests that tile — which for a popular basemap is a very large multiplier.

python
import numpy as np
from shapely.geometry import Polygon
import mapbox_earcut as earcut

def triangulate(poly: Polygon) -> tuple[np.ndarray, np.ndarray]:
    """Return interleaved f32 vertices and u32 indices for one polygon."""
    rings = [np.asarray(poly.exterior.coords)[:-1]]
    rings += [np.asarray(r.coords)[:-1] for r in poly.interiors]
    verts = np.concatenate(rings).astype(np.float32)
    ring_ends = np.cumsum([len(r) for r in rings]).astype(np.uint32)
    return verts, earcut.triangulate_float32(verts, ring_ends)

The output fits an Arrow schema naturally — a vertex column, an index column, and a per-polygon record of index start and count — which means it travels over the same Arrow transport as everything else and lands in a GPU buffer with no client-side parse. It also compresses well, because indices into a spatially coherent vertex array are numerically close.

One further server-side benefit is worth naming: a triangulation computed once can be checked once. Degenerate rings, self-intersections and unclosed geometry all cause an ear clipper to produce garbage rather than an error, and catching them in a build pipeline where the failure can be logged against a feature id is far more useful than catching them in a browser where the only symptom is a polygon that renders as a spray of thin slivers.

The trade is tile size: triangulated output is larger than the ring representation it replaces, typically by around a third once indices are included. For a vector basemap served to many clients that is a good trade; for a one-off analysis layer downloaded once and viewed by one person, triangulating in a worker is simpler and the bytes are better spent elsewhere.