Sunday, May 20, 2012

Progress Report

It's been a while, so I suppose I owe another post on my progress.

I've spent a while shuffling languages and ideas, trying to zero in on the best way to build an engine that can support the game I want to make.

I was originally working in Unity, but eventually decided that while Unity is a very powerful engine for rapid game development, its real strength lies in its 3D editor, which I wasn't using. My game is based almost entirely on procedural generation, well outside of what Unity is designed to handle. So I spent far more time than I liked with trying to figure out how to work around limitations in the engine, and in some places simply had to compromise on what I could do. I eventually decided this wasn't acceptable.

While working with Unity, though, I had fallen in love with C#. So I determined I'd make the engine in C#, but targeted at Mono, with the intent of keeping it multi-platform. Toward that end, I grabbed a library called OpenTK, which provides bindings for OpenGL, OpenAL and OpenCL, a set of multi-platform open standards for graphics, audio and general-purpose GPU processing, respectively. I made some pretty substantial progress using those, but when trying to utilize the more advanced graphics functionality I encountered some flaws with the bindings that I couldn't work around.

And thus I've arrived back at my old standby: C++, with SDL and OpenGL.

Unfortunately, all of this environment switching has a high cost. I'm not quite starting from scratch each time, but it almost feels like I am. It's a major setback, and a huge amount of work has to be redone. However, I'm confident I won't be switching again. C++ is a bit more complicated to work in, but it applies no artificial limits. Anything I want to do, and can't, will be because the hardware can't handle it, not because the environment is constrained.

Now this isn't the only reshuffling I've done. The first part of the game I'm attempting to implement is the terrain engine. The reason for this is that it's the riskiest component, and it's very central, in that how I implement it will heavily influence how I implement everything else, and even influence a lot of details of the game design. I've been unsure exactly how best to go about it, or whether I could even find a way to meet all of my fairly steep requirements. Those requirements are:
  1. It needs to be fully dynamic, so it can be reshaped on the fly.
  2. It needs to support overhangs and caves (a simple heightmap won't do).
  3. It needs a viewing distance of at least a few km, and a geometry resolution of no larger than a meter, on commonly available PC hardware.
Originally, I was trying to do this with voxel cube terrain, because that definitely fulfills the first two requirements, and the third is just optimization. Unfortunately, I couldn't find a way to optimize it sufficiently. It's easy to blame the slowness and low viewing distance (144m) of Minecraft on the fact that it's in Java, or accuse Notch of being a bad programmer, but the reality is that drawing that many cubes is really hard on the GPU. Also, given that there is no clean way to apply level of detail, and your view gets wider as the viewing distance increases, when you double the viewing distance, you roughly quadruple the amount of geometry you have to draw.

So in order to achieve point 3, I went back to the drawing board. I spent a couple weeks brainstorming, and reading. I came across this amazing blog called ProcWorld, by a very talented programmer, Miguel Cepero, who is working on his own procedural world generator. Many of his techniques aren't useful to me, because his worlds are pre-generated over hundreds of hours on a render farm, whereas mine need to be made on the fly. However, it exposed me to an algorithm by the name of marching cubes, which I'm honestly a bit embarrassed I hadn't heard of before.

Marching cubes is a very fast, clean and elegant way of taking a mathematically defined surface and turning it into a set of polygons, at an arbitrary resolution. This surface has to be described in terms of a 3D density map, and a threshold value, such that points that are denser than the threshold are inside the surface, and points less dense than the threshold are outside the surface.

The first chapter of GPU Gems 3 describes not just how to implement marching cubes, but how to implement it very efficiently in the GPU, using a multi-pass shader. I realized it would be relatively easy to extend their implementation to allow for smooth, seamless level of detail with geomorphing.

Unfortunately, this is where OpenTK failed me, and I realized I needed to switch away from C#. I got the basic, naive GPU implemention of marching cubes working, but of course it was way too slow. So I began work on the multi-pass version described in GPU Gems 3, and discovered that OpenTK had a bug I couldn't work around (or figured out how to fix) with its support for transform feedback, the OpenGL feature that allows for the multi-pass technique.

So now I'm back in C++, building up all the basic infrastructure of a new engine. I decided that, since I'm starting a new engine anyway, I'd build it with a component-based architecture. Which has slowed me down a little, because it's unfamiliar territory, but I believe it will pay dividends down the road. Anyway, I now have that mostly in place, and fairly soon I should be able to dive back into the terrain engine itself.

No promises on when I'll have visible results to show. I still have a day job, after all.

No comments:

Post a Comment