Lighting by hand #4: into the shadows

PICO-8

This article is the final part in a series describing my real-time lighting engine for the PICO-8, a cute fantasy console with limited horsepower. It works as a stand-alone article, but you still might want to start from the beginning if you haven’t read the previous entries yet.

Last time we parted, we had a cute flickering light with most of the features already in place, but one important component was still missing: real-time shadows. To add that missing component, we need to figure a few things out: how to represent shadows, how to calculate where they are and how to draw them efficiently.

We’re in luck, since that’s what this article is all about.

Speaking volumes

Every lit object casts a shadow behind it. In the real world, this is caused by rays of light from the light source being blocked by the object.

Some rendering techniques, such as raytracing, create virtual light rays and simulate how they would behave. These simulated rays are blocked just like real ones would, so pretty shadows just happen for free. What doesn’t happen is any kind of reasonable performance — despite all the technological advances since it was invented, raytracing is still woefully slow and mostly inadequate for real-time rendering.

The way GPUs actually do business is by concentrating on the objects themselves. There are no light rays in a modern rendering pipeline. Instead, we start from a pixel on the object’s surface and apply lighting to it based on it’s position relative to the light source. The downside of doing it this way is that effects created by bouncing light rays (like shadows and reflections) become much more difficult to achieve, as we no longer have an actual ray to work with.

Two common ways to get around that are shadow volumes and shadow mapping. The latter approach is what people usually use these days, but both have their strengths, and shadow volumes have one important advantage — they adapt very easily to 2D and don’t really require off-screen buffers, which are hard to do on the PICO-8.

Each yellow shape is a shadow volume for one of the spheres (image from English Wikipedia)

The idea behind shadow volumes is all in the name. For every object, we can imagine its shadow as a volume of space in which everything is darkened. These volumes are three-dimensional objects themselves, and the basic approach to using them looks like this:

for each lit object:generate a shadow volumedraw this shadow volume to a special bufferwhen we draw actual objects later: check each pixel against the buffer to see if it's in shadowlight it only if it's not

Explaining this in detail would be an article on its own, but the core idea we can take away from it is this: an object’s shadow can be represented as a shape.

Flat press

The two-dimensional equivalent of the shadow volume is actually a shadow area — a flat shape representing all the pixels in a given object’s shadow.

A 2D object and the shadow “volume” behind it

Calculating that area for a complex object can be troublesome, so we’ll use our favorite cop-out: we’ll break it down into simpler components. In the 3D world, this is usually achieved by dividing surfaces into triangles. It’s much easier to figure out the shadow volume of a triangle than, say, a teapot.

The 2D equivalent of the triangle is the line segment. Just like we can break a 3D object’s surface into triangles, we can break any two-dimensional shape into its constituent edges.

How the shadow volumes of the three segments add up

The shadow volume of each segment can be calculated separately. The volumes of neighboring segments will be connected with each other, adding up to the shadow of the whole thing.

Building up the walls

Once we know that all shadow caster are going to be represented by line segments, we have to tell our engine where these lines are.

The basic idea is like this: every object in the game (wall, pillar, enemy) is allowed to have a list of walls — lines casting shadows. These lines are represented by s and e, the endpoints of the segment itself, and a unit vector d that points away from the wall and lets us know which side of the wall is the outside (if you’re vector-savvy: the wall’s normal).

Walls and their d-vectors in a sample corridor.

Once we have our shadow-casting structure, it’s time to make use of it.

The original 3D algorithm uses a special off-screen buffer to be able to quickly figure out whether a pixel is inside a shadow volume. That’s not really an option on the PICO-8 and the alternative of doing a point-in-polygon collision check for each potentially-lit pixel doesn’t sound too promising either.

Thankfully, we can use the shadow volumes in a simpler manner: we can just draw them in black on top of the rendered scene. For a single light source and pitch-black shadows, the end result will be the same, but rendering a polygon is going to be much more efficient than doing a check for every pixel we draw.

After this simplification, the whole process of adding shadows to the engine boils down to a single loop at the very bottom of our render loop.

for each wall: figure out if its shadow is visible at allif it is, calculate the shadow volumedraw the shadow volume in solid black

The first step is crucial, as it cuts down the number of shadows we need to draw significantly. This is shown in the image above, with the walls that we actually need to do anything about highlighted in yellow. There are just two rules:

• if the light source is behind the wall, no shadow needs to be drawn
• if both ends of the wall are outside the light’s maximum range, we can ignore that wall as well — the shadow wouldn’t be visible anyway

What’s in a shadow

Now that we know which walls can be safely ignored, our new mission is figuring out the shadow volumes for those that we do have to handle. Warning: this section may contain trace amounts of vector math.

A shadow volume and the light rays bounding it (shown in red)

From the illustration above, it’s evident that the shadow area of a single wall is some kind of polygon. The wall casting the shadow becomes one of the polygon’s edges, since it’s part of the shadow’s perimeter. Two more edges can be obtained by connecting the light source with each of the wall’s endpoints and projecting forward —we can actually think of those as light rays bounding our shadow. In theory, these rays go to infinity, but drawing infinite polygons works just as well as counting to infinity does.

Fortunately, the light already has a finite range, represented by the handy clipping rectangle that contains all potentially-lit pixels. We can use this rectangle to truncate our unwieldy infinite polygon into a smaller, self-contained equivalent with no delusions of grandeur, using the intersection points of the light rays with the rectangle.

-- light position and rangelocal p,rng = lgt.pos,lgt.rng-- wall endpointslocal s,e = wall.s, wall.e-- calculate light rays towards s and elocal ds,de = s-p,e-p-- extend the rays until they intersect with the-- nearest boundary defined by light range-- (white points)local cs, ce=rng/max(abs(ds.x),abs(ds.y)),rng/max(abs(de.x),abs(de.y))local proj_s, proj_e=p+ds*cs, p+de*ce

This gives us four vertices which we could connect up into a polygon right now and get a reasonable shadow in this one simple case. By this point in the series though, we have already learned that the simple case is never the only one.

Two situations in which four points aren’t enough — the regions in red would miss out on all the fun

When the light rays intersect different edges of the rectangle, using just the four points isn’t going to cut it. To hit all shadowed pixels within the rectangle, we need to add more vertices —namely, the corners we would encounter by going from one intersection point to the other along the perimeter. We do this by checking which quadrant each intersection point belongs to and iterating clockwise until we get all the missing corners.

-- find the quadrantslocal qs,qe = quadrant(ps), quadrant(pe)-- make sure qe->qs is increasingif (qs<qe) qs += 4-- assemble vertices in clockwise orderlocal vertices = {s, e, proj_e}for q = qe,qs-1 do_-- corners are pre-stored in a table as [_±_1,±_1] vectors-- we just have to translate/scale them to our rectangleadd(vertices, p+corners[q]*rng)endadd(pts, proj_s)

Drawn and ordered

We have our shadow volume, but actually drawing it is another story. Most rasterizing algorithms deal only with triangles, but what we have can be anything from a quad to hexagon.

The go-to solution for more amply-faced polygons is breaking them down into triangles first. This works great in GPU-world, since “rendering a triangle” is accelerated so much there that it’s basically free. On the PICO-8, the overhead of drawing a triangle is pretty significant, and that’s bad news for us and our hexagons, which consist of a total of four annoying triangles.

Fortunately, there is a simple algorithm for rendering polygons regardless of the number of faces they have, as long as they are convex — which our shadow volumes are.

The first step is going to be our usual fare when dealing with rendering a shape: we’re going to split the polygon into individual lines. This turns the problem of rendering a polygon into simply figuring out its extents line by line.

ymin, ymax = Y coordinates of the top/bottom of the polygonfor each y between ymin, ymax:xls[y] = find the leftmost x still inside the polygon at line yxrs[y] = find the rightmost x still inside the polygon at line yfor each y between ymin, ymax:fill(xls[y], xrs[y], y)

The way polygons work, both extremes have to lie on one of the edges. This means we can take all the edges, go through all the pixels on each (as if we wanted to draw it as a line) and update the xls or xrs table accordingly. The only problem is that we don’t know which table to update: we have no idea whether any given edge is on the left or right side of the polygon.

What is stuffily known as the clockwise winding order.

The simplest way out of this conundrum is making an assumption about the vertices, namely that they always come in a defined order: either clockwise or counterclockwise. Once we do that, we can easily figure out which side an edge belongs to by looking at the direction it’s going. Our shadow volume code gives us clockwise-ordered points, so any edge going up (ending y less than starting y) must be on the left side of the polygon. On the other hand, if an edge is going down, it must be on the right side.

function ngon(pts, ln)local xls, xrs, npts = {}, {}, #pts-- update xls and xrs using each edge in turnfor i=1, npts dongon_edge(pts[i],pts[i%npts+1],xls, xrs)end-- use the tables to draw each horizontal linefor y, xl in pairs(xls) dolocal xr = xrs[y]ln(xl, xr, y)endend

In this code snippet, the “figure out minimum/maximum y” section from the pseudo-code is nowhere to be found. That’s because we get this part for free: the xls/xrs tables will only contain an entry for the y coordinates our polygon actually hits. Instead of going through all y's in order, we can iterate on one of these tables directly.

Inversion diversion

Having gone through all that trouble, we’re finally ready to plug everything in. We set up the walls, plug the shadow rendering loop in, and…

Well, we’re definitely seeing some shadows, so that’s a plus. The problem is that the shadow of each wall completely obscures the wall itself. This might work for some games, but we didn’t go to all the trouble of drawing a cool ancient temple tileset just to limit our rendering to the floors. We’d like to stop the walls from casting shadow on themselves.

There are a few ways to achieve that, and the one we’re going to use is a dirty trick. We’re going to turn our walls inside out by reversing the d vector, making all the shadow-casting segments face inward. Since we check what side of the wall the light is on, this will make only the back faces able to cast a shadow. The engine will behave as if a ray of light was only blocked whenever it leaves a solid object, not when it tries to enter.

Back-face shadows, in garish Technicolor

This gets us what we wanted. The shadows from the back walls add up to the correct shape, but the interior of the walls is untouched.

Hole in the whole

Since it works so well for solid walls, let’s apply it to something more ancient-templey. Say, an etched pillar.

The base behind the spire casts a shadow on the spire. MC Escher approves.

Well, that’s still not it. The shadow cast by the base covers the part that should be high above it, completely ruining the illusion of depth.

This is the second time vertical surfaces cause us pain, and also the second time we will get around this problem by using a simple trick. Objects with vertical components will define a special hole mask in their walls table, which is just a rectangle labeled “do not touch”. We can use this rectangle to cover the vertical spire and make sure it won’t get shadows drawn on top of it.

We extend the polygon routine to accept such masks and take them into account when drawing. Each line, we will split the segment we’re drawing into a “before the hole” and “after the hole” section, and draw these instead — leaving the interior of the rectangle intact.

MC Escher no longer approves.

All’s well that ends well

At this point, I‘m happy with how the shadows look. The engine can still draw nonsense at times, with an object shadowing something it really shouldn’t, but such situations are pretty rare and hard to notice when you have a whole game to care about. I’m pretty sure the only way to definitively fix these remaining issues would be to actually do it in 3D — and I have to leave something fun for future articles, don’t I?

That concludes our four-part journey from a black screen to a workable lighting engine on the PICO-8. I hope you enjoyed it as much as I did. I had to omit a lot of detail to finish this write-up before the next century comes calling, so if you have any questions or feedback, I’ll be happy to take it on Twitter.

Writing these has been equal parts great fun and absolute exhaustion, so I will probably take a short break from writing now. Still, do keep an eye out for my next article — we’ll talk about how having strict limitations (like PICO-8’s) can influence game design for the better.

Until then, may you always finish what you start.

Part 1 | Part 2 | Part 3 | Part 4 | Play the game