on Jul 24, 2014
I know this shadow volumes stuff is getting to be pretty tedious. I kind of whiffed my initial explanation, so lots of people are a little confused about how it works. Then I’ve endlessly fussed with it without clearing up the earlier confusion. I think this is the last time I’ll bring it up for a long while. It won’t even take up the entire entry. And next we’ll do something fun. Just humor me for a bit longer.
Right now the world is cut up into chunks, and those chunks are often irregular shapes. In 2D, they’re something like this:
The geometry shader looks for points that are right on the edge between the light side and dark side of the object, and extrudes those out to make a shadow volume.
You’ll notice that even though the top edge is flat, it’s still broken up into a row of six line segments. What would happen if I broke this odd shape up using an octree? I’d be able to remove a lot of these redundant points, at the cost of breaking a single volume into many smaller volumes. The geometry shader would have to consider fewer vertices, but it might have to extrude more of them. The question of “is this worth it?” depends a lot on how the stuff is shaped in the first place. If an entire chunk was one great big cube, then breaking it into an octree would be objectively, drastically better. But if the shape is really irregular, then the division might do more harm than good.
It’s impossible for me to intuit where the break-even point might be, so let’s just do the experiment and see what we get. I have it divide chunks using an octree, which results in large areas being consolidated into single cubes at the cost of creating a bunch more volumes. So this single volume:
Becomes many smaller ones, made up of fewer points:
The idea here is that there are less vertices (the red dots) to process, and less total polygons (line segments, in our 2D diagram) to worry about, but more overlapping shadows. The end result might look something like this:
Note that I’m depicting the shadows stacking on top of each other just so you can see what I’m talking about. In practice, the shadows won’t actually be darker or different. But you can see these smaller, simpler shapes get turned into more total volumes.
The results would vary a lot depending on how your scenery is shaped, but in my case using an octree reduces the polygons to 1/3 their original number. At the same time, it cut the framerate in half. So in this case less polygons means a slower running program.
Now, we could probably achieve some kind of polygon reduction without using an octree. But… I don’t wanna. At least not now. That would be a long research project (it would basically be a 3D version of this) and not the sort of thing I want to mess with right now. Let’s just move on.
(There. All done now. No more shadow volumes for a bit.)
You know, I kind of want to see what this looks like with the marching cubes I was messing around with back in 2012. I’ve still got the code, and it’s basically ready for copy/paste right into the project.
Wow. That’s… really striking. Now, you might remember that back on project octant, this same idea looked like this:
Both images are using the same sort of beveled shapes, but the latter image is using smooth shading. I haven’t brought over the code for smoothing out the surface normals, and now that I’ve seen it flat-shaded I don’t think I’ll bother. Flat-shaded marching cubes have a certain geometric charm.
The only thing I don’t like about the old code is the way variables are named. The term “marching cubes” is a really odd name for a thing. That’s a verb and a noun, and the noun is already used elsewhere in the code to describe something different. (Actual cubes.) Ideally you want one-word descriptions for things in your code. And if you ARE going to have two-word names, then you probably don’t want one of the words to be a VERB. In C++ (and lots of other languages) coders usually get really fussy about naming things nouns and verbs. If a function does something then you want to give it an active, verb-y name, usually in the form of thing+action to perform on thing:
But if it just returns information then you give it a more passive name:
Note that this is just one of many approaches. The goal here isn’t to make the One True Naming Convention, but only to pick a system where you should be able to guess the name (or purpose) of something without needing to look it up. So having a thing with a verb in its name creates a situation where you end up with verbs where you don’t want them. This doesn’t hurt anything mind you, but it’s annoying when you settle on a set of rules and have this ONE THING that doesn’t follow them.
Back in 2012 I dealt with this in various ways. Some places they’re called marching_cubesToo long, has a verb. and other places marched_cubesToo long. Kinda awkward. and other places marchesUGH. Terrible., all in some kind of desperate attempt to make this thing less annoying to use.
This is stupid. They aren’t cubes. They do not march, or perform any marching-type activity. The name is long and confusing. So why not just call them “blobs”?
So I have to run through this old code and touch it up, re-naming all these ridiculous variables.
Other than this bit of housekeeping, I’m actually really pleased at how nice the code is. Sometimes I go through old code and cringe. Sometimes I’ll find a whole page of complex operations with no comments, numerous sections of unused code, or several things with nearly the same name, and get frustrated with my former self. This is especially true if the code was originally written as a prototype. You start off just slapping stuff together to see what works, with the idea that you’ll come back later and clean it up if it works out. And then you… don’t.
Some people deal with this by insisting on writing everything right the first time. That doesn’t work for me. It slows down work too much, especially when you’re making sweeping changes. It also results in a lot of wasted time and effort. Earlier in this entry I talked about making octree-based shadow volumes. Those were hacked into place with all sorts of shenanigans. And since I ended up deleting the entire thing the moment the experiment was complete, it would have been a huge waste of time to pretty up the code as I worked.
For other coders: My usual prototyping crimes are: Public class variables. Function names that no longer describe the function they perform, or do so poorly. No comments. Blocks of disabled code. Excessive nesting. Grossly inefficient code. Overly terse variable names. Passing around huge structs or classes by value instead of by reference. Pretty much the same sins everyone else commits, I’d imagine.
This is less of a problem if you know exactly what you’re doing. If you’re working from a detailed specification (or if you’re doing something inherently straightforward) then it’s a lot easier to write it all correctly the first time. But when I’m prototyping, I think the best approach is to do LEGO-style building: Dump everything out and make a mess, build what you need, then clean up when you’re done. The only reason this is a problem is that sometimes I run into an interesting distraction just as it comes time to clean up. I make a note to come back later, and then get so involved with the New Thing that I forget about the mess I left for myself.
The condition of the Pixel City code was ghastly. I can’t look at it now without flinching. I’m really sorry to everyone who had to untangle that mess. (I suppose my self-imposed time limit was a major contributor to that.) Project Octant was left in far better shape, and so I’ve been able to recycle bits of it without much effort.
marching cubes blobs make for less processing-intensive shadow volumes. So not only does this look nicer and more unique, but I can push the view distance a little higher before it hurts the framerate.
So this is where it leaves us:
And (roughly) the same thing in VR-view:
Looking forward to getting my Oculus Rift, although I have no idea where this project will go or how I’ll write about it once that happens. We’ll figure that out when the time comes. In the meantime, I’m kind of looking for excuses to tinker with this a bit more. I’ve basically met my goals with regards to shaders, but this is kind of fun. On the other hand, I might get back to Good Robot. Based on what I’ve learned, I could rip the guts out of the particle and sprite-drawing engine and replace it with something much, much more efficient.
 Too long, has a verb.
 Too long. Kinda awkward.
 UGH. Terrible.