Last time I promised we’d be dealing with rendering performance problems. Lies. We’re going to backtrack instead. I skimmed a lot of concepts back in part 2, and I think we need to talk about stencil shadows in more detail before we can proceed.
I’ve gone over this before, but polygons have front and back faces. Typically, the back face isn’t drawn. If I’m staring at a wall in (say) Doom 3:
In the real world, if I pass through the wallHow? and turn around, I’d find myself looking at the back side of this blue wall. But in a videogame…
…I just look back into the level. The back side of the blue wall (and indeed, of all the walls) isn’t drawn. It would be a waste to do so, since you’d never see it during the normal course of play. Similarly, if you stuck your head inside a Minecraft cube, you wouldn’t find your head in a box. Instead, you would find yourself outside the world looking in, as with the Doom image above.
Let’s go back to the horrible MS Paint diagram I was using before:
As I said before, we take the thing that should cast a shadow (the green cube) and extrude it away from the light. Everywhere this new object pierces the existing scenery is a place where the light can’t reach. What I neglected to mention is that for this to work we also have to draw the back faces and not the front ones. So, the object is effectively inside-out. Normally, that green cube would only draw the polygons that face the viewer. (The blue eye.) So the downward facing line and the leftward facing line would get drawn, and the other two would be left out. When we turn the cube inside-out, the opposite is true.
This also means that everything that casts a shadow must be an enclosed solid. This is sometimes called making an object “airtight”. Here’s why:
Let’s imagine our clever level designer realizes that, for whatever gameplay reason, the player will never, ever be able to reach the space to the right of the green cube. Since this is true, then we can just leave off that polygon:
Now the green cube is no longer an enclosed solid. Sure, it leaves hole in the level, but if the player can never get in a position to see it then it won’t do any harm, right? This is fine, and you can see this sort of polygon-trimming done frequently in older gamesIt’s generally not worth optimizing these one-poly cases on modern machines, but you can see it in titles like Half-Life 2. Use cheat codes to fly around and you’ll see how aggressive the team was at removing stuff like this.. But it becomes a problem when you use these objects to project shadows.
Without the right-side face, there’s nothing to project a shadow onto the wall.
EDIT: If you’re one of the many people annoyed/ confused by this and are wondering why the LEFT side of the cube isn’t blocking the light, then reading part 2 might help you out. I know this is tricky stuff. Good luck!
You can also think of it this way:
The little regions between the dotted lines could (depending on viewing angle) have proper shadows, but the space between them would be fully bright because the back face of the cube isn’t there to project shadows. And while this is an extreme example, it’s actually easy for tiny flaws to produce scene-altering results. Since the polygons are projected away from the light to infinity, any leak ends up expanding to cover large areas of the screen. In practice this looks like a bright stripe of light, visible through all the walls, standing at a great distance away.
The requirement that all shadow-making shapes need to be enclosed solids puts some interesting additional challenges on those of us working with large dynamic worlds. If you’re looking at a mountain in Minecraft, then in theory the mountain should be a fully enclosed solidOtherwise there would be somewhere you could go to “fall out of the world”.. But in practice this isn’t the case. Maybe the mountain is so huge that we don’t have the far side of the mountain in memory. Or maybe that part of the mountain hasn’t been generated yet. And even when the far side of the mountain is loaded, there are sill more hills and caves behind that, and more beyond those. You never get to a hard edge where all the space is closed off once and for all. The scenery on the far edge of your view always has a gaping void facing the horizon, and those missing faces – like our broken green cube above – will project malfunctioning shadowsYou may say, “Who cares if the far side of a mountain isn’t shadowed right, we can’t see it!” But imagine if you’re looking into the sunrise over that mountain. Those broken shadows will be projected RIGHT INTO YOUR FACE. The area around you will be shadowed all wrong..
Again, reducing the problem to 2d, the typical Minecraft world looks like this-ish:
Think of this as a sort of cutaway view. When turned into polygons, it looks like this:
Those open gaps at the sides and bottom are the problem. That’s where our bad shadows will originate. The solution I’ve settled on is to just cut up the world into chunks. Actually, you have to do this anyway so you can load and render the world piecemeal. The world is sectioned off into 8x8x8 chunks and so all we need to do is have it cap off every chunk.
This is really wasteful, but as far as I can tell it’s unavoidable if we want to use this shadow technique. (I might noodle around with other shadowing systems. I might not. We’ll see what sounds interesting when the time comes.) This also means we’re now working with two different sets of polygons: There are the polygons that you see, and there are the polygons that project shadows. The visible version of the chunk can be open (not enclosed) but needs to have information for normal mapping and surface texture included. The other version just needs to be a flat-color enclosed solid.
Now we’re ready to look into this ridiculous low framerate. And by “now” I mean “next time”.
 It’s generally not worth optimizing these one-poly cases on modern machines, but you can see it in titles like Half-Life 2. Use cheat codes to fly around and you’ll see how aggressive the team was at removing stuff like this.
 Otherwise there would be somewhere you could go to “fall out of the world”.
 You may say, “Who cares if the far side of a mountain isn’t shadowed right, we can’t see it!” But imagine if you’re looking into the sunrise over that mountain. Those broken shadows will be projected RIGHT INTO YOUR FACE. The area around you will be shadowed all wrong.
MMO Population Problems
Computers keep getting more powerful. So why do the population caps for massively multiplayer games stay about the same?
A programming project where I set out to make a gigantic and complex world from simple data.
Diablo III Retrospective
We were so upset by the server problems and real money auction that we overlooked just how terrible everything else is.
If Star Wars Was Made in 2006?
Imagine if the original Star Wars hadn't appeared in the 1970's, but instead was pitched to studios in 2006. How would that turn out?
A horrible, railroading, stupid, contrived, and painfully ill-conceived roleplaying campaign. All in good fun.