Experiment № 102 · The story
One Wall at a Time
Why I picked it
Two weeks ago I drew Bresenham's line algorithm, the routine that decides which pixels a line lights up. But a graphics pipeline does something before that: it throws away everything that falls outside the screen, so it never rasterizes what nobody will see. Ivan Sutherland, who had already built Sketchpad in 1963, and Gary Hodgman published their method for this in 1974 under the title "Reentrant Polygon Clipping." Graphics pipelines have used the same idea ever since, clipping triangles against the planes of the view volume. It is one of those algorithms that runs billions of times a day without anyone thinking about it, and I wanted to slow it down to one edge per beat.
What I enjoy about it
Clipping to a pentagon sounds like a geometry problem with lots of special cases: corners, edges that cross two walls at once, shapes that wrap around the window. The algorithm avoids all of it by never looking at the pentagon. A convex window is just the overlap of a few half-planes, so it clips against one straight wall, then passes the result to the next. Each pass is four lines of logic, and the window's corners show up on their own: one pass leaves a vertex on wall two, and the next pass cuts the edge leading to it where it crosses wall three. I like that the output of each stage is a valid input to the next, which is what "reentrant" means, and why it can be built as a hardware pipeline. I also like its honest flaw. Make the shape spiky enough that two arms poke into the window separately and the result comes back as one polygon, with the pieces joined by pink edges that run along the wall and back again. It doesn't know it made two pieces. Weiler and Atherton fixed that in 1977 with a much more complicated algorithm. Switch to Drift and those seams turn into the lead lines of a stained-glass window.
Something you might take away
When a constraint is the overlap of several simple ones, you can usually satisfy them one at a time, in a chain, with each step knowing nothing about the others. Clipping, filtering a query by several conditions, running a document through a series of checks: same shape. The cost is that the chain only sees what each step passes on, so look for where that loses information. Here it is the pieces: every step hands over one list of points, so the result can only ever be one polygon.