Growing up, Quake was one of those games that just
blew me away with what a computer was capable of. It helped inspire me to become a developer in my
own right. One of the first books I ever got on coding was the Graphics Programming Black Book
by Michael Abrash, although I confess that most of it was over my head at the time. Released in
1997, this book isn’t as relevant as it once was, but it holds stories and insider info about the
development of one of the most groundbreaking games ever made. Today, I’d like to dive into one
of those stories, but with fresh eyes after more than 20 years of additional experience.
So visibility determination isn’t easy, even today, as I showed with my recent deep dive
into current methods. It remains very much an area of active research and development.
Rewinding the clock back to the mid 90’s, and we go back to a time when this field was very
much in its infancy, comparatively speaking.
The Quake dev team faced this very
problem. The game was unplayably slow, and since they were breaking new ground,
there was no clear solution to turn to.
When we talk about visibility determination, for
the purposes of the video, we’re talking about what goes into drawing a pixel on the screen.
So you’re down here, this is the camera, and you’re looking off in this direction, so
what we need to know is what’s visible to you.
In modern games, this mostly boils down culling
out what’s off screen, which is called frustum culling, then doing some occlusion culling
to figure out what objects are behind other objects, so we can cull those as well.
But back in the 90’s, this was being done in software on a desktop computer that would choke
on just playing a song today, something we all take for granted as background work.
Quake originally required a pentium 75, which had a processing speed of approximately
126 MIPS, or million instructions per second, according to google. Take note that
this is instructions per second, not floating point operations per second, which
is what you might see on more modern hardware.
By comparison, the phone in my pocket is capable
of somewhere in the realm of 1142 GFLOPS, or 1.1 Million mflops, if I haven’t messed up a decimal
somewhere, so the gulf in computing power, even though this is a silly comparison, simultaneously,
it's’ good for younger viewers to have a grasp of just how much of a potato that thing was
compared to anything you have now. Not to take anything away from what it was, in its day.
The cost alone of simply rasterizing a triangle was high, so you needed to be fine grained, and
only draw the polygons that were visible.
There was also no gpu in any modern sense, as in
a gpu that you could offload a significant amount of the work to. No depth buffer, no shaders,
not even hardware T&L, like you had nothing.
So you’re working with a few more constraints than
today when doing your visibility determination, you don’t want to simply discard
the objects that aren’t visible, that’s still way too much. You want to get even
more granular than that. In an ideal world, you’d somehow know just the polygons that are visible,
that contribute actual pixels on the screen.
In an ideal world.
And of course, that magical test, whatever it is, has to be fast.
Quake stored its levels in a BSP, or binary space partition, which is a data
structure you don’t run into much these days.
Conceptually, they’re not especially difficult to
grasp. Let’s take a simple 2d example, and we’ll build a little tree to illustrate what they do.
So right now, the space, the level, whatever you wanna call it, it’s empty. We can add a wall,
let’s call that wall A, and the wall has an orientation, like this way is forward, and
obviously the other way is backwards.
The wall creates a splitting plane, so
that forward, or in front of the wall, we’ll call it empty space, while behind the
wall, this is solid. This is an important thing to take note of, because it’ll be
very relevant throughout using the BSP.
So we’ve defined the wall, let’s define a
node, in this case the root of the BSP tree, we’ll call it A. This node has 2 children,
the left node represents what’s in front of A, which is empty space, while the right
is behind A, which we’re calling solid, this represents the region behind the wall.
One wall isn’t terribly interesting, so let’s add a 2nd wall now, and for simplicity
I’m just going to make it down here, like this. So this is wall B, it faces in this
direction. We have to insert this wall into the BSP, so starting at A, we have to check,
is this wall B in front of, or behind A?
We know it’s in front of A, so we’re going
to go to A’s child, the empty space node, and replace it with a B node. And this
new node of course has a left child of empty space, and a right child of solid.
The left child of B represents this region here, notice how it's the region in front of A that's
now being split by B. The left child of B represents the region in front of B, while the
right child represents the region behind B.
Let’s repeat the process now, but
with a horizontal wall C on top, facing in this direction. So C is in
front of A, and it’s in front of B, so it get’s inserted here, replacing B’s left
child, and so you have this new node C, with a left empty child, and a right solid child.
And I’ll leave it to you to do this on paper, but if I were to add this new wall
D, which faces in this direction, then it’d end up here as a child of C.
So we end up with this kinda boring BSP tree, that’s basically just a line of nodes descending
to the left. But the really cool part of BSP’s is they enable you to do fast operations.
Let’s bring in a slightly more complex BSP, just to make the test’s a bit more
interesting. This one is basically the same, but I’ve inserted a few more walls.
If you’re following along on paper, take special note that I just inserted them
in alphabetical order, and notice how E is in front of D, but when I go to insert
F, it’s behind E, thus on the right.
Now, let’s test whether a point is in empty
space, or in solid space. This point here, very obviously by looking at it, is in empty
space, but we can confirm that with like, actual code trivially. Starting at the root node,
is this point in front or behind the splitting plane? In front, obviously, so we move to the next
node, and it’s in front of that, so again, we move on. And we repeat that process, over and over
again, until inevitably we end up in a leaf node, either a solid node, or an empty node. In this
case, an empty node, signifying that this point is in empty, or free space. Or in other words, if
that’s a player, they’re allowed to be there.
So BSP’s can accelerate these kind of
tests, they allow you to rapidly discard large sets of the world. But another interesting
property is that each of these nodes here. Each of these represent a portion of the space.
They, in fact, split the space of their parent. So starting at the root node, this is all space.
This node’s left child is one half of the space, while the right child is the other half.
When we look at this node, B, it partitions this space here, meaning that it’s left child
is this space in front of it’s splitting plane, while it’s right space is this space behind.
And we can continue in that way, looking at C, this node is splitting this highlighted
region here along the plane that we provided, meaning that the left child of C represents
this space over here, while the right child of C represents this space over here.
And likewise, we can continue on and on, and these nodes carve up the space
into these ever finer convex subspaces, and we end up with these 3 convex subspaces that
i’ve coloured, which correspond to these empty leaves in the tree. Which is kinda neat.
That’s one of the big takeaways, bsp’s carve up space, and you can of course calculate
bounding volumes for these subspaces if need be, and having bounds on these nodes allows you to
rapidly discard entire portions of the world, making bsp’s useful not only for rendering but
for other gameplay systems like physics.
Lastly, BSP trees give you a natural
ordering when you draw. They can be used to easily give you surfaces in front
to back or back to front order.
If we take a really simple bsp tree, we’re
just going to have a couple lines here, so you could follow along on paper if you wanted
to. And we’re going to place our eye here. Now the interesting thing with the bsp is, the direction
doesn’t matter, only the position of the eye.
So to draw, the algorithm is pretty
straightforward, you walk the tree and at each node, decide to either draw the left
or right child first. So you start at the root, if you’re in front of the splitting plane, draw
the back of the tree first, then this node, then the front. If you’re behind the
splitting plane, do the opposite. Then of course you recurse and do the same, so you
you go through nodes B, C, and D eventually.
So that gives you immediately the order B, because
that’s behind, then A, because that’s the node in question, then you have to draw this subtree,
so we recurse, we’re in front of C, so we draw behind C, which is nothing, then we draw C, then
we recurse, which just ends up drawing D last
So we get easy back-to-front order by
simply walking the tree, easy peasy.
So they give you quite a lot of advantages,
but this isn’t quite enough to draw effectively because of one major problem, overdraw.
Overdraw is a problem that’s still being tackled on modern hardware 30 years later,
and in Quake this was really serious. This was being done in software, and although they
did implement a z-buffer, it had a performance impact and was limited to dynamic stuff.
If you draw front to back, in some terrible cases, you may end up drawing and redrawing
the same pixels over and over again. You could easily imagine cases where
overdraw could reach 10x or more.
So this was the big problem to be tackled, how
do you reduce, or even eliminate overdraw?
This part in the story was one of the most
interesting to me, the sheer number of approaches Carmack took, attempting to solve this.
He attempted to use a beam-tree to track visible fragments, a subdividing raycast approach, almost
like binary search raycast, representing the world with planes rather than explicit vertices,
a 1 bit draw buffer tracking whether or not a pixel had been draw yet, rasterizing the
polygons into spans and clipping using those, and an approach that involves tracking the
portals between leaves, and clipping further away geo and portals to these portals.
I won’t dive into all of them, but let’s poke at the first couple of them.
The first thing mentioned, the beam tree is really interesting, because finding
information online was difficult, references are pretty sparse or result in dead links.
There’s some scattered references to some papers back in the mid 80’s that you can read,
which gave me a bit of context, and there’s a very brief explanation in the book as well.
From what I understand, they’re in essence a special type of bsp tree, but instead of being
built directly from the polygons of the world, you do something very different.
If you’re looking out at the world, your camera would be down here, and the viewing
volume that you see is formed by 6 planes. You’ve got your planes on the left and right,
you’ve got your planes on the top and bottom, and you’ve got your planes on the near and far.
Now let’s consider a single triangle out here in the world, and we have the camera looking at
it. So, if you take an edge of that triangle to begin with, and you form a new triangle
using those vertices on the edge, and the camera’s position. From this you can form a plane
that passes through the camera and the edges of the triangle, similar to the viewing volume.
You can then repeat the process for each edge of the triangle, building another plane that passes
through those 2 vertices and the origin.
So this is called a beam, this kinda volume
that’s projected out from the origin to the triangle, and you’d insert this into
a bsp, not the whole thing, only the planes that you calculated, the side planes.
So let’s visualize this, so this is our screen, and you’d start the beam tree off by inserting
4 planes representing the bounds of the view frustum, the visible area or the edges of the
screen. And you’d end up with a pretty basic tree, kinda similar to what we saw earlier.
We’ll colour the “drawable” area green, so anything in the drawable area is good to go.
So the basic idea is to use this secondary BSP to check what’s been drawn on the screen. So let’s
say I want to draw this triangle here, you can tell from a glance that this whole triangle falls
into the “drawable” area in the beam tree.
What would actually happen is that you’d insert
this triangle into the beam tree, by inserting each of the planes of the triangle, which in
2d basically look like lines. So one by one, those would get inserted into the tree, and
you’d end up with a tree more like the one on the right now. These open leaves of the beam tree
correspond to regions that are still drawable, which you can go test on paper if you like, but
I’ll leave that to you and we’ll move on.
Let’s say now, I want to draw this second
triangle, we know by just glancing at this that if we were to walk the BSP tree, we’d end up in
this region here in front of F, which corresponds to this leaf on the bsp tree itself.
As you prepare to draw this triangle, you walk the beam tree and if it ends up in a
visible area, you’d update the tree and draw the triangle. But if it doesn’t, there’s no tree
changes and thus the polygon isn’t visible.
That’s my understanding of it anyway. In
theory, a great approach, but as Abrash notes, the worst case was still terrible, and
maintaining the beam tree wasn’t free either, so in the end they had to scrap the approach.
Another interesting approach was to use raycasts, since the bsp is great at accelerating those.
So by this point, you should be reasonably familiar with the idea of walking the tree to
figure out whether a point is visible or not, it just involves descending and
doing the plane tests until one reaches either an empty or solid leaf.
So a raycast isn’t really all that different, except you’re of course dealing with a line. If
you were to say, overlay the line over the bsp, you can clearly see where it would
get cut by the splitting planes and chopped up. So you’d end up with a bunch of
fragments of the original ray, each fragment lying in either a solid or empty node.
Of course, you don’t need to chop it by every plane though, that’s just wasteful. You
can be smart and do the closest section first, you can see this section, if you walk it
down the tree, it ends up in an empty node, and thus it never hits anything.
So we go ahead and process the other side, and this part of the ray of course gets
chopped by this plane here, so of course what you’ll do is process that part first, so
we sorta can clearly see that it’ll end up in an empty node, and thus hits nothing.
This next part, behind the wall, well, we KNOW that it hits something, like us the
viewers, but we need to prove it in code. Well, the next node down the tree is this node here,
with this splitting plane, so the ray gets lopped into 2 parts, and we’ll take this part
here and walk it down the tree. And of course, it ends up in a solid node, so we’re done, we
know for a fact this intersects something, we know where it intersects, we know everything.
So if we take a look at an example screen, the subdividing raycast idea, at least in my head
given the description, kinda works like this. You divide the screen into some number of areas, they
mention use an 8x8 grid, so 64 in total, and for each you cast a ray, using the exact same raycast
approach to clip the ray against the BSP.
Let’s take a look from the side, so here’s
a side view, here’s the camera here, and we’ll have some walls here to fill out the
scene a little bit. So what you’d do is you’d fire out a bunch of rays at the world, which
of course would get clipped against the BSP as I showed before. Let’s assume that every ray hits
something, so each of these rays is being extended until they touch a surface. The question would
then be, what did they hit. We’ll colour them with the colour of the surface they touched.
Now, let’s focus on these 2 rays. If 2 rays are adjacent, and hit the same polygon,
then you can simply interpolate the surface in between, easy enough.
That’s a best case scenario, so now if we were to focus on another pair when they don’t hit
the same surface. So these neighbouring raycasts hit different surfaces, so then you in essence
have to do a binary search by firing a ray in between and repeating the process.
Then it kinda follows that eventually, after repeating this process a buncha
times, that either all the adjacent rays will be on the same surface, or they’ll be
at pixel level, at which point you bail.
I could easily imagine this working
great in one of those old Quake levels, where polys took up a lot of real estate on
screen, and chances were pretty good that just a few iterations of this subdivided raycast
approach could cover most of the screen.
From the sounds of it, this
ultimately failed due to dropouts, basically problems with tiny polygons.
There were other approaches, as Abrash mentions, some were merely kinda tossed around,
while others saw actual implementations. I’m guessing based on the descriptions that
the draw buffer and span buffer approaches, since they seem like iterations on existing
techniques, were tried out, as well as the portal clipping, but the vertex free surfaces idea, maybe
something they just punted around, who knows.
Here’s the point in the story where we have the
miraculous turnaround. If this was an episode of House, you’d have him look at a bus going
by, or a leaf falling, or something random, and suddenly have an epiphany.
According to Abrash, we’ll just read his words here: When I came in on
Monday, John had the look of a man who had broken through to the other side--and also
the look of a man who hadn’t had much sleep.
And then he goes on to describe how
Carmack figured it out. The solution being precalculating the visibility between
leaves in the bsp. This would be called a PVS, or potentially visible set, which now, nearly
30 years later, how it works is widely known, but it was a real game changer in its era.
The general idea is that, let’s say that we’ve got our level here, we’ll just do a 2d version
instead of a 3d version, and let’s just quickly understand what we’re looking at here.
So each of these regions here, let’s say these regions are leaves in a BSP. We’re taking
some liberties here, but let’s run with it.
Then each of these spaces is separated by these
green lines, these would have been splitting planes, and you can figure out that where there’s
no polygons, those form a sort of border between adjacent spaces that are called portals.
So given this shaded region here, of course any region that it’s immediately adjacent to
it, is, of course, visible right away. You can figure that out without a lot of effort using
the BSP since they basically share a portal. The trick is really whether or not these further away
regions are visible from that initial region.
I mean, you could do something like cast a
zillion rays from one portal to the next, and see which other leaves they manage to
hit, but that’ll be really unreliable.
Quake did this by erring on the side of being
conservative. Secondary neighbours are usually visible, not always, but pretty much most
of the time. So we’ll consider a neighbour of a neighbour to be visible right away.
So the effort was mostly on leaves further out than this. The question now is whether
section 4 here is visible from section 1.
The approach they employed was by using a
separating plane, so they’d create a plane from each edge of the portal, to the opposite
side of the other portal, here we have our separator plane, and the portal lies completely
in front of it, so it’s not eliminated yet.
We’ll do the separator plane for
the other side, and lo and behold, the portal lies completely behind the plane,
getting culled out. In a small way, this is just like the beam tree we just talked about.
If we were to say, expand section 2 so that the portals end up a bit fatter, you can see
that now the separating plane just catches the end of the portal from section 3 to 4,
making section 4 visible from section 1.
That's the general idea, and it extends
pretty easily into 3d from there. In 2d, of course we only needed the 2 separating
planes, but in 3d you would do this for each edge. As I said, it’s a conservative
approach, but works incredibly well.
BSP’s have since faded from their glory days,
you don’t really hear much about them anymore. Levels now are dynamic, requiring a degree of
flexibility that’s necessitated new approaches.
The original Quake source code was released
over 24 years ago at this point, and that, along with subsequent sequels, have been a source
of some incredible gems. Perhaps, most infamously, the fast inverse square root function, which
is this abomination you see before you.
This was a story that for some reason or other,
has stuck with me for over 20 years. I read this at a time when I was still struggling with basic
concepts, and it shaped, at least in a small way, how I approach things today.
I find that it’s really easy to be enamoured with a clever solution, I mean we
all appreciate an elegant answer to a problem, but it’s also in the failures, the missteps
and dead ends along the way, that we can find some really valuable insights.
The final solution, at least to me, evolves naturally from the failed attempts
that preceded it. Understanding the beam tree, the portal clipping ideas, a lot of
the basic ingredients were there.
I remember, I had just barely started learning
to program and struggled hard with the sparse information Abrash provided. Looking back
now, I actually appreciate how it pushed me to work harder, to really strive to
understand the underlying concepts.
If you think you’d like to learn more about
gamedev from an experienced graphics engineer, I have a variety of courses available, very
suitable for beginners, so if, for example, you ever wondered if understanding quaternions
was possible, check them out. Otherwise, if you’d still like to support me and help
choose what topic I cover next, you can vote on my Patreon page.
Cheers
