Visibility
Given a point and a plan of walls, the lit region is a single polygon. Cast a ray at every wall endpoint — and a hair either side of it, which is what turns corners into corners — keep the nearest hit, sort by angle, join the dots. That polygon is the whole thing: fill it for light, subtract it for shadow, accumulate it for memory. Jitter the source over a small disc and average a handful of polygons and you get penumbra for free.
A light in a plan
Move the pointer. Three fixed lights hold their own hues and blend additively, so overlaps read as sums rather than as the topmost layer. Samples is the number of visibility polygons averaged across the source disc — set it to 1 for hard shadows and watch the penumbra collapse.
How the polygon is built
The same computation, slowed to walking pace on a plan of four walls. The dial around the light carries a tick per endpoint angle; the sweep hand is the current ray; the wall it lands on is picked out in red. Each pair of consecutive hits emits one triangle. Drag the light inside the figure.
Fog of war
One application, done properly. Every frame the current visibility polygon is stamped into a mask. The mask is what the walker remembers: geometry it has seen stays faintly drawn, geometry it has not seen does not exist. One room on this floor has no door onto the patrol route, which is why the number never reaches 100.
What it actually does
- Three rays per endpoint, not one. The middle ray lands on the corner; the two rays either side of it slip past and hit whatever is behind. With one ray per endpoint every corner leaks.
- The penumbra is not a blur. It is n hard-edged polygons drawn at one over n alpha, so a pixel’s brightness is literally the fraction of the source disc that can see it.
- Several lights with their own hues blend additively, so overlapping pools read as sums rather than as whichever was drawn last.
- Fog of war is the same polygon stamped into an alpha channel. The remembered layer is the plan composited through that mask, with no per-tile bookkeeping and no grid anywhere.
- A bounding rectangle has to be in the segment list at all times or the polygon never closes.
What the rebuild taught
- Correct beats clever at this size. The naive sweep runs a few thousand rays a frame in under two milliseconds, and the version that would have been faster is the version that would have had corner bugs.
- Degeneracies are the whole difficulty: rays parallel to a wall, duplicate endpoints, and a light sitting exactly on a wall. Skipping near-zero determinants and pushing the light a couple of pixels along the wall normal handles all three, and both guards need saying out loud.
- Sampling turns a binary answer into a continuous one at no conceptual cost. Same trick as antialiasing and motion blur, which is a good sign it belongs in the vocabulary.
- Alpha channels are a perfectly good place to keep state. Not everything that persists needs a data structure.
- Accumulate coverage, then tint. The obvious implementation, filling each of the n polygons with the radial gradient at 1/n alpha, lays a visible one-pixel halftone screen over every lit surface: the renderer dithers radial gradients, and drawing the same dithered gradient n times amplifies the dither instead of averaging it away. Accumulating solid white and applying one gradient tint afterwards is both correct and faster.
- Falloff carries more of the look than the polygon does. A gentle power curve left most of a room above a third brightness and the whole scene read as flat coloured rectangles rather than as pools of light.
- Beware layouts that mix units. Lights placed in fractions of the canvas and furniture sized in pixels means that at some aspect ratios a light lands sealed inside a box, lighting nothing but its own four walls. Nudging off a wall cannot detect this, because the light is not on a wall, it is enclosed. Only a narrow-viewport test found it.
- An endpoint’s three rays are not adjacent in the sorted order, they are only coincidentally so. A debug overlay that assumed adjacency drew the neighbouring endpoints’ rays instead and quietly taught the wrong thing, which is worse than not having the overlay.
Rebuild
Three figures: a lit plan with coloured lights and soft shadows, a slowed-down sweep that can be stepped by hand and shows the epsilon pair, and fog of war on a patrol route. The reference is a teaching article, so this one deliberately explains less and plays more.