Project: WebGL Marching Cubes

by Grant Forrest

Marching Cubes is an algorithm which creates a polygon mesh out of an implicit volume or surface. The algorithm was developed by William E. Lorensen and Harvey E. Cline and patented in 1987.

For this project, my objective was to implement the Marching Cubes algorithm in the browser, using JavaScript and WebGL. To do this, I used a library called Three.js and some of the prevalent literature concerning Marching Cubes.

My first objective was to create a completely synchronous version of the algorithm which would run on a static surface. Once this was accomplished, I proceeded to make the mesh generation asynchronous. In order to accomplish this, I used the relatively nascent JavaScript Web Workers, which bring client-side threading to JavaScript. Unfortunately, Web Workers are not quite as optimized as native system threading, and one tradeoff is that they have no shared memory. I was able to work around this constraint with a bit of detriment to performance.

Deformable terrain

After threading the algorithm, my next task was to make the terrain deformable. To do this, I began with my existing voxel model of the terrain's volume. Each voxel (a value corresponding to a 3-dimensional grid) stores a floating point number representing the 'density' of that grid location. In order to extract a surface, the Marching Cubes algorithm interpolates between adjacent voxel density values, defining a surface point between them along connecting edges. To modify the representation of the terrain, I only had to raycast a click into the scene and adjust the voxel values at the colliding location (lower the density of a cube to 'dig', raise it to 'build'). However, this did not effect the mesh representation, which was generated at initialization.

Smooth voxel terrain

Rebuilding the entire mesh on each change was prohibitively expensive, so I split the mesh into chunks of 8x8x8. Whenever the user interacts with the terrain, the appropriate chunk mesh is rebuilt. If the edit is on an edge between chunks, then both of them will be rebuilt. Each mesh rebuild task is also run on its own Web Worker, so that they do not interrupt the interface thread.

The final portion of the project was to implement shadows. Without any shadows, the caves which I created using 3D Perlin noise for my terrain appeared very unnatural. I first implemented shadows using simple shadow mapping with simple Lambertian lighting. Once that was completed, I added PCF filtering for softer edges. My lighting only supports a single directional light, but the shadows look nearly as good as Three.js' built-in shadow mapping techniques.

Flat voxel terrain

Video walkthrough
view the project on GitHub