Experiment № 067 · The story
Aim at the Corners
Why I picked it
Put a lamp in a dark room full of pillars and ask what it lights. Almost everyone's first program answers by brute force: fire a thousand rays out in a fan, stop each at the first wall, join the dots. It looks fine until you zoom in, and then the shadows have serrated edges that shimmer as the lamp moves, because a ray fan is a sampling grid and sampling grids alias. The fix isn't more rays. It's noticing that the answer is a polygon, and that a polygon only turns where something makes it turn — and the only thing in a room that can make a shadow boundary turn is the end of a wall. So you don't sample. You aim: one ray straight at every corner, and two more nudged a hair either side of it, because the interesting thing at a corner is what lies just past it. Sort the hits by angle, join them in order, and you have not an approximation but the exact visibility polygon, in about a hundred rays instead of a thousand. There is a lot of good mathematics stacked behind that little picture. Victor Klee asked in 1973 how many guards a gallery of n walls could possibly need; Chvátal proved ⌊n/3⌋ in 1975, and Steve Fisk found the proof from the book three years later — triangulate the polygon, three-colour the vertices, station your guards on the rarest colour. The linear-time algorithm for one guard's view had a rockier ride: it was published, then republished, and Joe and Simpson were still issuing corrections to it in 1987.
What I enjoy about it
The two nudged rays. The ray that hits the corner dead-on is the boring one — it just lands there. Its neighbours are the whole trick: one slides past the corner and travels on until it finds whatever is hiding behind, and that long jump is the shadow's edge. Turn on draw the rays and you can see the pairs splitting apart, each corner spitting out one short ray and one long one. Then switch to the fan and watch the same room come apart at the seams: the outline of the true answer is still drawn over it, and the fan's polygon keeps cutting inside it or leaping outside it, lighting slivers of floor that are genuinely in shadow. The readout counts those misses honestly, as a percentage of the room, and the number is stubborn — in a room like the one that loads, 176 rays get one or two percent of the floor wrong, and every doubling of the rays only halves that, forever. Meanwhile the exact method is sitting there at about 120 rays with an error of zero. My other favourite is how cheaply softness arrives. A real lamp is not a point, so make it nine points on a small ring, run the same code nine times and average — and the hard shadow grows a proper penumbra, wide where the occluder is far away and tight where it is close, which is exactly the physics, with nobody having written any physics.
Something you might take away
When you're tempted to sample something uniformly, ask first where the answer is actually allowed to change. Sampling spends its whole budget in the flat places where nothing is happening and still gets the edges wrong; if you can name the events — the corners, the crossings, the discontinuities — you can go straight to them and be exactly right for less money. That one move is most of computational geometry: Bentley and Ottmann finding line-segment crossings by sweeping a line and only stopping at endpoints, Fortune's beach line only stopping when a circle closes, a discrete-event simulator jumping between the moments the queue changes rather than ticking through empty time. Even graphics does it — Crow's 1977 shadow volumes extrude the silhouette edges of an object, which are corners again, wearing a hat. The habit generalises past geometry, too: the expensive part of most problems is a small set of places where behaviour switches, and finding them beats sampling around them. It's worth being suspicious of any loop whose accuracy you improve by making it longer. That's often a sign you're approximating something that has an exact answer waiting one insight away.