Sursday Update: Zee Voxel Engine – Marching Cubes and View Distance
Hey
Rafael here. Last weekend I’ve met Oskar (hey there!), the creator of that cool city block demo, for a coffee, and we talked a bit about the voxel engine of Proven Lands. Great guy, btw. So let’s talk about voxels a bit too.
The foundation of our engine is, as for Minecraft and other voxel games, the Marching Cubes algorithm. This algorithm was first published in 1987 for extracting a polygonal mesh from voxels (a 3D discrete scalar field). If you want to learn about voxels, see my blog on voxel data, or if you are into Marching Cubes, better check the web because I cannot cover the whole topic in a dev blog post.
In short, Marchin Cubes is a clever way to “extract” meshes from a “cloud of dots”, so to speak. It has deep scientifically roots like visualisation of brains. It was improved a few times since then. The voxel engine “Voxel Farm” of EverQuest Next used Marching Cubes at the beginning, too, before its creator, Miguel, decided to use Dual Contouring, if I’m not mistaken, which is basically a better looking algorithm. The bad thing about Marching Cubes though is that it was patented until 2005. Yep, thank you science. So until 2005 it was expensive or even forbidden to use it sometimes. So no games touched it really, and that’s why games like Infiniminer probably appeared first after 2005– and then voxel things became the next big thing for some Minecraft reason.
Basically, what you do in Marching Cubes you “march” through the data and create cube parts. It’s like: This could be the top of the polygon, this the left side, this is small corner there, and so on It is one of the reasons why nearly all voxel based games like StarForge start with a low view distance. They do it because the polygons are created through such “marching” on the CPU, which takes time. A world based on voxel data is probably the future, whether in polygons or on a hardware-based voxel level, but today on our crappy primitive machines it takes minutes to create huge worlds. So what do we do in order to create an okay-ish huge scene? How to get a huge view distance?
We optimise the loader, the generator, the data structure. For instance, we create a Level of detail-based (LOD) terrain system. That’s why trees and whole mountains flicker in the background in many games. The closer you are to the player, the higher the resolution of the terrain. The further away you are, the rougher the terrain and the bigger the area you render. How do I know what to render and how close I am? You use an “octree” data structure. Octree is the 3D equivalent of a quadtree, which is used in AI programming, for instance. You “walk” through the tree until you hit the bottom level of one node and then you render it. How do I know what the bottom level is? Every node has an LOD ID. If LOD 0 is the player and LOD 8 is 16 km away. If you render all LOD 1 nodes it is clear that you cannot render LOD 2 or 3 within the same area, because LOD 2 is bigger than LOD 1 and consists of all LOD 0 and LOD 1 nodes, respectively. So when the player moves, you determine the position of LOD 0 all the time and adjust the surrounding “terrain meshes” to it by “walking” through the octree again until you hit the bottom level that has to be rendered. If it’s too much in a quick post, see here for a nice video on how LOD works in general, without knowing their engine: No Man’s Sky, a different game, gameplay and engine though, shows pretty well how this works here.
It is no rocket science, it is pretty known to engineers working on huge scenes or planets, but there’s one downside for Proven Lands however. Doing such a LOD system for a non-voxel based game is already complicated and expensive (in terms of performance, math and coding magic). But for voxel engines it is rare. It is so rare that, as far as I know, only one PhD dissertation exists on that topic until today. The reason are the cracks (or “holes”) between LOD terrain meshes based on voxel data. Due to the voxel nature of the terrain, there is a high chance that you find tiny cracks between the LOD’s, so your scene is filled with cracks. There are some tricks for normal terrain like “skirts” that help, but if we imagine complex voxel-based overhangs and caves, those solutions won’t help you anymore due to the mesh complexity of some caves or pillars. In Landmark you would have holes in every house, for instance. So the (talented) creator of the C4 engine proposed to create an LOD 0.5 between LOD 0 and LOD 1 which works basically like a “zipper” or like glue, called it Transvoxel algorithm and wrote his dissertation about it. In that aspect Minecraft’s terrain is more simple compared to all Landmark’s out there, because in a Minecraft-like game you are less affected by LOD holes or issues.
Now, back to our little game, what does it mean to us? Being the only coder here, and doing many other things at the same time *cough*, means we need to be hyper pragmatic. There’s plenty of room for improvements, not only lighting or loading time. But what we have already is a nice looking terrain and a hopefully interesting view distance of 16 to 32 km at an altitude of 10 m (it is higher the higher the altitude). It is not optimized yet, but we’re on it.
For as long you use the top-down camera everything is fine Diablo 3-Don’t Starve-style, but if you turn the camera in a cave or on a high flying island, I thought I’d like to give us that emotion of being truly alone in the desert, on a huge planet, with a huge view distance -- like Sparth’s art. At some point we hope to add vehicles and aircrafts to the game too. So let’s see how it goes.
Cheers, Rafael
