Pixels on a screen

How do you render an SVG? Well, let’s start somewhere a bit simpler than the SVG spec: how do you render a set of filled bezier shapes? We can take the approach that Skia does, decompose the shape into triangles and ask the GPU to rasterize (turn them into screen pixels), or we can take the approach that Cairo does, flatten them into line segments and then turn them into pixels ourselves.

Both Cairo and Skia are mammoth (100,000 lines +) C/C++ libraries with lots of hand-tuned algorithms and memory management. But the maths is pretty simple, all adding-upseys and the odd divide. Is there a better way to express the rasterization pipeline with an amount of code that a mere human could read and understand in a few hours?

Dan Amelang thought so and this was the basis of his Gezira/Nile project. We can express the pipeline in a higher level language, he called it Nile and, in source-code form, it looks a bit like this:

DecomposeBeziers : Bezier >> EdgeSample
    ∀ (A, B, C)
        inside = (⌊ A ⌋ = ⌊ C ⌋ ∨ ⌈ A ⌉ = ⌈ C ⌉)
        if inside.x ∧ inside.y
            P = ⌊ A ⌋ ◁ ⌊ C ⌋
            w = P.x + 1 - (C.x ~ A.x)
            h = C.y - A.y
            >> (P.x + 1/2, P.y + 1/2, w × h, h)
        else
            ABBC    = (A ~ B) ~ (B ~ C)
            min     = ⌊ ABBC ⌋
            max     = ⌈ ABBC ⌉
            nearmin = | ABBC - min | < 0.1
            nearmax = | ABBC - max | < 0.1
            M       = {min if nearmin, max if nearmax, ABBC}
            << (M, B ~ C, C) << (A, A ~ B, M)

This is a Nile kernel. It receives Bezier tokens from a queue and emits EdgeSample tokens; it can also put tokens back on the queue (a kind of recursion). This one looks at beziers and if the curve fits inside one pixel it emits a sample, otherwise it splits it and puts both halves back on the queue. Kernels can be composed into bigger ‘pipelines’. And the upshot is you can end up with a whole pipeline like this:

Rasterize : Bezier >> CoverageSpan
    ⇒ DecomposeBeziers → SortBy (@x) → SortBy (@y) → CombineEdgeSamples

Beziers go in one side and CoverageSpans (draw a line at x, y of length l covering c%) come out the other.

The language stays direct and tiny. It’s not entirely memory-less, kernels can keep their own internal state. All the work of optimisation and memory-management and execution happens in the compiler.

I’ve been working on a compiler/optimiser/backend for Nile for about ten years. Little experiments here and there. Reading and re-reading the source code and filing away research I’ve read that might be useful. I’ve finally got something I can show: a tiger. Let me just apologise to everyone I’ve bored in the pub with these ideas in the meantime.

The Nile code that renders that entire tiger is around 300 lines long, most of it reusing Amelang’s Gezira. The same 300 lines compile to three backends - JavaScript, WASM and WebGPU. The current pipelines are very much Cairo-shaped but I’m interested in making a pipeline that spews out triangles and letting the GPU do its rasterizing job.

The compiler, umgeni, is very much a work in progress and it’s, um, interesting.

I’ve tried to represent the language semantics with another little language I’m calling mooi. The Nile semantics, written in mooi, can act as a kind of symbolic interpreter: if you run values through it, it’ll interpret them; if you put symbols through it, you’ll get some IR out. It has a small prelude of useful functions to represent mapping and folding and writes against a small domain of eleven operations that the backends understand. The semantics of Nile (mostly! work in progress, remember) only exist as a handful of Mooi files. I have no idea if this is a good idea but I wanted to see if I could extend the idea of Nile for graphics to Mooi for compilation. We’ll see.

There are a number of stages to making this actually put pixels on an actual screen in a reasonable amount of time.

First the Nile code is preprocessed into a form without significant whitespace (Python does something similar) and I parse it to an AST.

The umgeni elaborator’s job is to take that AST and generate an IR (intermediate representation) out of it. It uses mooi to do most of the work but it also does some inlining and defunctionalisation substitutions itself. The IR is scalar, all types and structure gone. Before I hand it off to the backends, I do a few optimisation passes.

I ‘fuse’ kernels together, removing unnecessary intermediate queues and joining consecutive sorts. I do some tail call optimisations so that a kernel whose last act is to requeue a token just loops round instead. And also, I run a CSE (common subexpression elimination) pass to remove unnecessary assignments. Recent experiments include some dead-code-elimination and constant folding. Phew. Thank god I took this compiler course last year.

One of the coolest things I’ve just added is automatic memoisation where I can skip a whole host of calculations if they’re the same as the last frame. It doesn’t help the demos much, but for real world use I think it’ll be a big help.

I think this is going to be, has already been, a fun project. And almost totally useless: the rendering engines hand-tuned by experts against known hardware models might be significantly quicker (but only by a factor of 50 or so).

How do you render an SVG? Use Cairo or Skia. But if you want to understand how rendering works, maybe this project is for you. It might also give you a glimpse into a future where systems are made not from million-line programs no-one will ever have enough time on this earth to read but from clever compilers and simple direct languages you can grok in an afternoon.

My next job is to simplify the compiler/optimiser. Make it more readable and easier to understand. Then, I’ll put it away for another ten years. Will probably still bore people in pubs with it. Did I mention there was a tiger?

Elsewhere