Implementing Dual Contouring

If you've read the Dual Contouring paper and the ProcWorld post From Voxels To Polygons but haven't been able to get an implementation working, then this post is for you. I've put together a Dual Contouring implementation and added it to a Github repo. The rest of this post will explain how it works.

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.