Skip to content

Related approaches

Jump to bottom
Patrick Walton edited this page Jan 17, 2019 · 3 revisions

Over the past two years, Pathfinder has considered several approaches that didn't pan out. This page briefly categorizes them.

Note that none of this implies that these approaches are bad approaches. It simply means that these approaches didn't meet Pathfinder's goals. Tradeoffs are everywhere in this space.

Signed distance fields (SDF)

  • Monochrome only.

  • Generation of the SDF is very expensive, typically much more expensive than just rendering the path on CPU in the first place.

  • Requires slow generation of mipmaps to handle zooming out correctly.

Single-channel SDFs

  • Edges become rounded when zooming in.

Multi-channel SDFs (msdfgen)

  • Heuristics to encode sharp edges can fail.

On-the-fly SDF encoding (GLyphy)

  • Still relatively slow, even when done on GPU.

  • Inherits the general problems of SDFs.

  • Bézier-to-arc conversion is done on CPU and is slow.

Multi-color SDF-like techniques

  • Too slow to generate.

  • Have various limitations on scene complexity.

Scanline traversal in fragment shader

Examples: Slug, W. Dobbie's vector texture approach.

  • Variable-length loop in shader causes thread utilization hazards.

  • No ability to parallelize over overlapping fragments on desktop GPUs.

Note that speed of scanline traversal is likely to be hardware-dependent, and this may be the most optimal way for certain scenes on certain hardware.

Tessellation

  • Hardware multisample antialiasing uses too much memory bandwidth at the levels needed to match the quality of Skia/Cairo/Core Graphics (16xMSAA bare minimum).

  • Reliable analytic antialiasing without hacks that degrade quality (e.g. Loop-Blinn) is basically impossible.

  • Suffers temporal stability problems—very noticeable in VR.

Ear clipping

Includes FIST.

  • Doesn't handle self-intersecting paths.

  • Unclear how to handle curves.

Monotone polygon triangulation

Includes GLU tessellator.

  • No self-intersecting paths, no curves.

  • Sensitive to floating-point error.

Lorenzetto trapezoidation

Example: Pathfinder 2.

  • Unlike the others, this does handle self-intersecting paths and curves, but extending the algorithm to handle them is complex.

  • Sensitive to floating-point error.

  • Generates lots of sliver triangles.

Seidel trapezoidation

  • Asymptotically faster than Lorenzetto, but slower in practice due to use of binary trees.

  • Despite the name of the paper, it's not really simple, especially once extended to handle self-intersecting paths and curves.

Constrained Delaunay triangulation

  • O(n³).

  • No self-intersecting paths.

Stencil-and-cover

Example: NV_path_rendering.

  • Inherits antialiasing quality problems of tessellation.

  • Lots of overdraw.

  • Switching between stencil and cover phases and clearing stencil are expensive.

Summed area tables

Example: Pathfinder 1 (GPU), font-rs (CPU).

  • Sensitive to floating point error.

  • Requires either compute shader or evil multiple render targets hacks on GPU.

Note that it may be worth revisiting this, as it has better asymptotic complexity than Pathfinder 3's current approach. But the above two problems would have to be addressed.

Compute

Includes all techniques based on compute shader, OpenCL, CUDA, etc.

  • More limited hardware compatibility.

  • Harder to fit into traditional GPU pipelines like WebRender and game engines.

Rendering on CPU

  • Arithmetic intensity/memory bandwidth of analytic AA is not ideal for CPU.

  • Texture upload time.

Clone this wiki locally