Simplifying Line Geometry with a Compute Pass

Every vertex a line renderer does not have to draw is bandwidth it does not have to spend, and at low zoom a coastline carries an order of magnitude more detail than a screen pixel can show. The obvious algorithm — Douglas-Peucker — is recursive, data-dependent and sequential, which makes it exactly the wrong shape for a GPU. What does fit is a local test: for each vertex, measure its perpendicular distance from the segment joining its neighbours, drop it if that distance falls below a tolerance, and compact the survivors. This page is that kernel, the fidelity it gives up, and the iteration scheme that recovers most of it. It is one stage of geometry filtering with WGSL compute shaders.

The per-vertex test, and what one pass removes Two strips of eleven vertices. The upper strip shows the perpendicular distance of each interior vertex from the segment joining its two neighbours, with vertices 2, 5, 6 and 9 falling below the tolerance and the rest above it. The lower strip shows the result after compaction: the two endpoints and the five interior vertices that exceeded the tolerance survive, in their original order, and the four below it are gone. VERTEX 0 1 2 3 4 5 6 7 8 9 10 11 end ok low ok ok low low ok ok low end Distance vs tolerance endpoints are never tested — dropping one would move the line end v1 v3 v4 v7 v8 end Kept 7 of 11 compacted in input order — an atomic counter would scramble the line Consecutive removals accumulate error — see the iteration discussion below.
The predicate is local and the compaction is global, which is the same two-stage shape as every filter in this section. Only the ordering requirement differs, and it is what forces the scan over an atomic.

Runnable reference implementation

The kernel is a per-vertex predicate followed by the compaction from the prefix-sum guide. Endpoints are always kept, because dropping them changes where the line starts and ends.

wgsl
struct Params {
  tolerance : f32,          // in the same units as the coordinates
};
@group(0) @binding(0) var<uniform> params : Params;
@group(0) @binding(1) var<storage, read>       verts : array<vec2<f32>>;
@group(0) @binding(2) var<storage, read_write> keep  : array<u32>;

/// Perpendicular distance from p to the infinite line through a and b.
fn perp_distance(p : vec2<f32>, a : vec2<f32>, b : vec2<f32>) -> f32 {
  let ab = b - a;
  let len = length(ab);
  // Degenerate segment: fall back to the point distance.
  if (len < 1e-6) { return distance(p, a); }
  return abs(ab.x * (a.y - p.y) - (a.x - p.x) * ab.y) / len;
}

@compute @workgroup_size(256)
fn mark(@builtin(global_invocation_id) gid : vec3<u32>) {
  let i = gid.x;
  let n = arrayLength(&verts);
  if (i >= n) { return; }

  // Endpoints are never dropped — they define the line's extent.
  if (i == 0u || i == n - 1u) { keep[i] = 1u; return; }

  let d = perp_distance(verts[i], verts[i - 1u], verts[i + 1u]);
  keep[i] = select(0u, 1u, d >= params.tolerance);
}

The compaction that follows is the standard scan-and-scatter, and the deterministic version matters here: line vertices must come out in input order or the line is drawn as a scribble.

wgsl
@group(0) @binding(0) var<storage, read>       verts   : array<vec2<f32>>;
@group(0) @binding(1) var<storage, read>       keep    : array<u32>;
@group(0) @binding(2) var<storage, read>       offsets : array<u32>;   // scanned
@group(0) @binding(3) var<storage, read_write> out     : array<vec2<f32>>;

@compute @workgroup_size(256)
fn compact(@builtin(global_invocation_id) gid : vec3<u32>) {
  let i = gid.x;
  if (i >= arrayLength(&verts)) { return; }
  if (keep[i] == 1u) { out[offsets[i]] = verts[i]; }
}

Parameter reference

Value Setting here Guidance
Tolerance ~0.5 screen pixels, in ground units Converted per zoom: pixels × metresPerPixel. Below half a pixel the removed vertex is genuinely invisible.
Iterations 2–3 One pass removes isolated vertices; each further pass removes vertices the previous pass made removable.
Endpoint handling always keep Dropping an endpoint moves the line, which no tolerance justifies.
Compaction prefix sum, not atomic Order must be preserved or the line self-intersects.
Degenerate guard len < 1e-6 Duplicate consecutive vertices are common in real data and make the distance undefined.
Vertices remaining after each iteration A bar chart in thousands of vertices for a coastline of 48 000 vertices simplified at a half-pixel tolerance. The original holds 48 000. One pass leaves about 19 000. A second pass leaves about 12 500. A third leaves about 11 200, and a fourth changes almost nothing at 11 000, because the remaining vertices are all genuinely further than the tolerance from their neighbours. VERTICES REMAINING · THOUSANDS Original 48 000 1 pass 19 000 2 passes 12 500 3 passes 11 200 4 passes 11 000 — converged 0 13 26 39 52 K unsimplified partial near-converged converged Modelled on typical coastline data; the convergence point moves with how smooth the source is.
The curve converges by the third pass, which is why two or three iterations is the right default. A fourth costs a full pass for a one-percent gain.

What the local test gives up

Douglas-Peucker is globally optimal for its criterion: it guarantees that no removed vertex is further than the tolerance from the simplified line. The local test guarantees only that no removed vertex was further than the tolerance from the segment joining its immediate neighbours, and those are different claims.

The gap shows on smooth curves. A gentle arc of many vertices, each individually within tolerance of its neighbours, gets thinned aggressively — and once several consecutive vertices are gone the remaining ones sit noticeably off the original curve, because the error accumulates across the removals that a global algorithm would have accounted for. A river meander simplified this way can drift by several times the tolerance.

Two mitigations recover most of it. The first is to run the pass more than once with the same tolerance, re-evaluating against the survivors each time: that is a cheap approximation to the global criterion, because each iteration measures against the line as it now stands. Two or three iterations gets close to Douglas-Peucker on typical map data. The second is to forbid consecutive removals in a single pass — keep every other candidate — which bounds the accumulated error at the cost of removing fewer vertices per pass.

For interactive rendering at half-pixel tolerances the difference is not visible, which is the case that matters here. For anything measured — a length computation, a published boundary — simplification belongs on the CPU with an algorithm whose error bound is stated.

Where the pass belongs relative to culling

Simplification and culling both reduce the work a line renderer does, and running them in the wrong order wastes most of the benefit of each.

Culling should come first. A line entirely outside the viewport should never be simplified at all, and the cull test is one bounding-box comparison against a simplification pass that touches every vertex. Running simplification over a whole tile and then culling most of it away is the most common arrangement and also the least efficient.

The exception is that simplification changes the bounding box — slightly, and only inwards, since removing vertices can only shrink an extent. That means a cull performed on the unsimplified bounds is conservative, which is the safe direction: it may keep a line the simplified version would have culled, and it will never cull one that should have been kept.

There is also an ordering question against styling. A wide line is drawn as a triangle strip expanded perpendicular to its path, and that expansion happens after simplification — which means a simplified line with a 12-pixel stroke can extend further from its original path than the tolerance suggests, because the join geometry at a removed vertex is computed from the survivors. In practice a half-pixel tolerance is small enough that it never matters; at the multi-pixel tolerances used for very low zoom it can produce visible corner cutting on wide strokes, and lowering the tolerance for wide layers is the fix.

Failure modes

  • The line becomes a scribble. The compaction used an atomic counter, so survivors came out in arbitrary order. Lines need the deterministic scan.
  • A long straight run collapses to two points and looks fine — until it is styled. Correct behaviour, but a dashed line or a chevron pattern needs vertices to place symbols on. Simplify for fill, not for symbol placement.
  • NaN appears in the output. Two consecutive identical vertices produce a zero-length segment; without the degeneracy guard the division is by zero.
  • Simplification changes as the user pans. The tolerance was computed from something view-dependent other than zoom. Tolerance should be a function of zoom only, so a tile’s simplified form is stable while it is on screen.
  • Endpoints move. The endpoint check was written as i == 0 || i == n rather than n - 1, so the last vertex is tested and can be dropped.
The local test against Douglas-Peucker A comparison across four properties. The local perpendicular test parallelises perfectly, guarantees only that each removed vertex was within tolerance of its immediate neighbours, can accumulate error across consecutive removals, and costs one compute pass per iteration. Douglas-Peucker does not parallelise, guarantees that every removed vertex is within tolerance of the final simplified line, accumulates no error, and is sequential and recursive. LOCAL TEST vs DOUGLAS-PEUCKER Local test Douglas-Peucker Parallelises perfectly not at all Error bound vs neighbours vs the final line Accumulates error yes no Cost one pass per iteration sequential recursion Iterating the local test approximates the global bound and is usually close enough by the third pass.
The two disagree about what "within tolerance" means, and the difference only becomes visible on smooth curves. For half-pixel tolerances on a screen it does not; for a published boundary it does.

Backend / Python interop note

The strongest argument for simplifying server-side is that the tolerance is a function of zoom, and a tile already knows its zoom. A vector tile generator that simplifies at build time ships fewer bytes and removes the pass entirely — and can afford Douglas-Peucker, because it runs once per tile rather than once per frame.

python
from shapely.geometry import LineString

def simplify_for_zoom(line: LineString, zoom: int, pixels: float = 0.5) -> LineString:
    """Tolerance in ground metres for a half-pixel error at this zoom."""
    metres_per_pixel = 40075016.686 / (256 * 2 ** zoom)
    # preserve_topology=True is slower and avoids self-intersections.
    return line.simplify(pixels * metres_per_pixel, preserve_topology=True)

preserve_topology=True is worth the cost for anything with fill or with neighbours: without it, simplification can make a boundary cross itself or separate from the polygon it was shared with, and adjacent administrative areas develop visible gaps. The GPU kernel above has the same weakness and no equivalent option, which is another reason to prefer the server where the geometry is shared.

It is worth checking the simplified output against the source once, at build time, with a Hausdorff distance rather than by eye: shapely computes it directly, and asserting that it stays under the tolerance turns “the simplification looks fine” into a number a review can disagree with.

The client-side pass still earns its place in two cases: data that arrives unsimplified because it is user-supplied or live, and pipelines where the tolerance depends on something the tile generator cannot know, such as a style-driven line width. For a static basemap, the server is the right answer and the compute pass is redundant.