Sunday, 28 September 2014

Dual Contouring: Seams & LOD for Chunked Terrain

There was a mistake in the original version of this post, the second last selectionFunc was a duplicate of the previous entry in the table. The table has now been corrected. Apologies to anyone who was tearing their hair out trying to debug that one!

Introduction

A couple of years ago I read these blog posts (1, 2) on 0 FPS, and like a lot of programmers decided I should write one of these voxel renderers. I implemented Marching Cubes first, but I was unhappy with the way terrain looked using MC -- it was far too blocky. I then implemented Naive Surface Nets and was pleased that I now had smooth terrain, but I soon discovered that Surface Nets couldn't support sharp features, like a 90 degree angle. That meant it would never be possible to have both a smooth terrain and a realistic looking building produced by the Surface Nets algorithm. I was aware of Dual Contouring from the 0 FPS posts, and my main source of information Miguel Cepero's Procedural World blog. Dual Contouring sounded like a significant step up in difficulty from Surface Nets, and I was quite skeptical about how feasible it would be to use Dual Contouring in a game. I never tried to upgrade my renderer to use DC and my interest in the project faded.

Then about a year ago, EverQuest Next was announced. Far from using blocky Minecraft style graphics EQN looked like a typical AAA game. I wanted to know how this was possible, and quickly discovered that I already knew -- it was based on the Procedural World project. I realised Miguel was really on to something here, and the next day started on a new voxel renderer. I set myself a goal: learn how this technology worked by creating a Dual Contouring renderer that would be capable of handling large terrains.