Wednesday, July 31, 2013

Marching Cubes with demarcated polygons

I've made more progress with the evaluation of PolyVox. PolyVox comes with a Marching Cubes algorithm that can extract surfaces from voxel volumes. Paul Bourke calls this polygonising a scalar field. This surface extraction works just fine in Polyvox. However, it does lack that distinctive visual style of Little Crane. My signature renderer draws the outline of the polygons in the 3D model. So I decided to add the demarcation of the polygons to the Marching Cubes algorithm in Polyvox. This has been partly successful, as I was able to reconstruct the complete polygons from the triangle list in most of the 256 cases in the Marching Cubes algorithm. Below you can see what it now looks like. I think the visual is usable as terrain for Little Crane II. I still need to add fading of the edges, so that the lines disappear at larger distances to the viewer. This will reduce the clutter caused by the edge drawing.

To reassemble the polygons from the triangles, I used my trusty Python interpreter. Nothing beats Python in productivity for complex processing. For posterity, here is the source code for reassembling most of the cases. The basic idea behind the code is to fuse triangles that share a common edge.

#!/usr/bin/python

import os
import sys

triTable = [
  [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  1,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  8,  3,  9,  8,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3, 11,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0, 11,  2,  8, 11,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  9,  0,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1, 11,  2,  1,  9, 11,  9,  8, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3,  1,  2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  2, 10,  0,  2,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  8,  3,  2, 10,  8, 10,  9,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3, 10,  1, 11, 10,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0, 10,  1,  0,  8, 10,  8, 11, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  9,  0,  3, 11,  9, 11, 10,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  8, 10, 10,  8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  7,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  3,  0,  7,  3,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  1,  9,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  1,  9,  4,  7,  1,  7,  3,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  4,  7,  3, 11,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  4,  7, 11,  2,  4,  2,  0,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  0,  1,  8,  4,  7,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  7, 11,  9,  4, 11,  9, 11,  2,  9,  2,  1, -1, -1, -1, -1, ],
  [ 1,  2, 10,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  4,  7,  3,  0,  4,  1,  2, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  2, 10,  9,  0,  2,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2, 10,  9,  2,  9,  7,  2,  7,  3,  7,  9,  4, -1, -1, -1, -1, ],
  [ 3, 10,  1,  3, 11, 10,  7,  8,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1, 11, 10,  1,  4, 11,  1,  0,  4,  7, 11,  4, -1, -1, -1, -1, ],
  [ 4,  7,  8,  9,  0, 11,  9, 11, 10, 11,  0,  3, -1, -1, -1, -1, ],
  [ 4,  7, 11,  4, 11,  9,  9, 11, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  4,  0,  8,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  5,  4,  1,  5,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  5,  4,  8,  3,  5,  3,  1,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  4,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0, 11,  2,  0,  8, 11,  4,  9,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  5,  4,  0,  1,  5,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  1,  5,  2,  5,  8,  2,  8, 11,  4,  8,  5, -1, -1, -1, -1, ],
  [ 1,  2, 10,  9,  5,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  0,  8,  1,  2, 10,  4,  9,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  2, 10,  5,  4,  2,  4,  0,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2, 10,  5,  3,  2,  5,  3,  5,  4,  3,  4,  8, -1, -1, -1, -1, ],
  [10,  3, 11, 10,  1,  3,  9,  5,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  9,  5,  0,  8,  1,  8, 10,  1,  8, 11, 10, -1, -1, -1, -1, ],
  [ 5,  4,  0,  5,  0, 11,  5, 11, 10, 11,  0,  3, -1, -1, -1, -1, ],
  [ 5,  4,  8,  5,  8, 10, 10,  8, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  7,  8,  5,  7,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  3,  0,  9,  5,  3,  5,  7,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  7,  8,  0,  1,  7,  1,  5,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  5,  3,  3,  5,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  9,  5,  7,  8,  9,  3, 11,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  7,  9,  7,  2,  9,  2,  0,  2,  7, 11, -1, -1, -1, -1, ],
  [ 2,  3, 11,  0,  1,  8,  1,  7,  8,  1,  5,  7, -1, -1, -1, -1, ],
  [11,  2,  1, 11,  1,  7,  7,  1,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  7,  8,  9,  5,  7, 10,  1,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  1,  2,  9,  5,  0,  5,  3,  0,  5,  7,  3, -1, -1, -1, -1, ],
  [ 8,  0,  2,  8,  2,  5,  8,  5,  7, 10,  5,  2, -1, -1, -1, -1, ],
  [ 2, 10,  5,  2,  5,  3,  3,  5,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  8,  8,  5,  7, 10,  1,  3, 10,  3, 11, -1, -1, -1, -1, ],
  [ 5,  7,  0,  5,  0,  9,  7, 11,  0,  1,  0, 10, 11, 10,  0, -1, ],
  [11, 10,  0, 11,  0,  3, 10,  5,  0,  8,  0,  7,  5,  7,  0, -1, ],
  [11, 10,  5,  7, 11,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  0,  8, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  1,  9, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  1,  9,  8,  3,  1, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  2,  3,  6,  2,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  0,  8,  7,  6,  0,  6,  2,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  7,  6,  2,  3,  7,  0,  1,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  6,  2,  1,  8,  6,  1,  9,  8,  8,  7,  6, -1, -1, -1, -1, ],
  [10,  1,  2,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2, 10,  3,  0,  8,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  9,  0,  2, 10,  9,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 6, 11,  7,  2, 10,  3, 10,  8,  3, 10,  9,  8, -1, -1, -1, -1, ],
  [10,  7,  6, 10,  1,  7,  1,  3,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  7,  6,  1,  7, 10,  1,  8,  7,  1,  0,  8, -1, -1, -1, -1, ],
  [ 0,  3,  7,  0,  7, 10,  0, 10,  9,  6, 10,  7, -1, -1, -1, -1, ],
  [ 7,  6, 10,  7, 10,  8,  8, 10,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 6,  8,  4, 11,  8,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  6, 11,  3,  0,  6,  0,  4,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  6, 11,  8,  4,  6,  9,  0,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  4,  6,  9,  6,  3,  9,  3,  1, 11,  3,  6, -1, -1, -1, -1, ],
  [ 8,  2,  3,  8,  4,  2,  4,  6,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  4,  2,  4,  6,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  9,  0,  2,  3,  4,  2,  4,  6,  4,  3,  8, -1, -1, -1, -1, ],
  [ 1,  9,  4,  1,  4,  2,  2,  4,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 6,  8,  4,  6, 11,  8,  2, 10,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2, 10,  3,  0, 11,  0,  6, 11,  0,  4,  6, -1, -1, -1, -1, ],
  [ 4, 11,  8,  4,  6, 11,  0,  2,  9,  2, 10,  9, -1, -1, -1, -1, ],
  [10,  9,  3, 10,  3,  2,  9,  4,  3, 11,  3,  6,  4,  6,  3, -1, ],
  [ 8,  1,  3,  8,  6,  1,  8,  4,  6,  6, 10,  1, -1, -1, -1, -1, ],
  [10,  1,  0, 10,  0,  6,  6,  0,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  6,  3,  4,  3,  8,  6, 10,  3,  0,  3,  9, 10,  9,  3, -1, ],
  [10,  9,  4,  6, 10,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  9,  5,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3,  4,  9,  5, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  0,  1,  5,  4,  0,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  7,  6,  8,  3,  4,  3,  5,  4,  3,  1,  5, -1, -1, -1, -1, ],
  [ 7,  2,  3,  7,  6,  2,  5,  4,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  5,  4,  0,  8,  6,  0,  6,  2,  6,  8,  7, -1, -1, -1, -1, ],
  [ 3,  6,  2,  3,  7,  6,  1,  5,  0,  5,  4,  0, -1, -1, -1, -1, ],
  [ 6,  2,  8,  6,  8,  7,  2,  1,  8,  4,  8,  5,  1,  5,  8, -1, ],
  [ 9,  5,  4, 10,  1,  2,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 6, 11,  7,  1,  2, 10,  0,  8,  3,  4,  9,  5, -1, -1, -1, -1, ],
  [ 7,  6, 11,  5,  4, 10,  4,  2, 10,  4,  0,  2, -1, -1, -1, -1, ],
  [ 3,  4,  8,  3,  5,  4,  3,  2,  5, 10,  5,  2, 11,  7,  6, -1, ],
  [ 9,  5,  4, 10,  1,  6,  1,  7,  6,  1,  3,  7, -1, -1, -1, -1, ],
  [ 1,  6, 10,  1,  7,  6,  1,  0,  7,  8,  7,  0,  9,  5,  4, -1, ],
  [ 4,  0, 10,  4, 10,  5,  0,  3, 10,  6, 10,  7,  3,  7, 10, -1, ],
  [ 7,  6, 10,  7, 10,  8,  5,  4, 10,  4,  8, 10, -1, -1, -1, -1, ],
  [ 6,  9,  5,  6, 11,  9, 11,  8,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  6, 11,  0,  6,  3,  0,  5,  6,  0,  9,  5, -1, -1, -1, -1, ],
  [ 0, 11,  8,  0,  5, 11,  0,  1,  5,  5,  6, 11, -1, -1, -1, -1, ],
  [ 6, 11,  3,  6,  3,  5,  5,  3,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  8,  9,  5,  2,  8,  5,  6,  2,  3,  8,  2, -1, -1, -1, -1, ],
  [ 9,  5,  6,  9,  6,  0,  0,  6,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  5,  8,  1,  8,  0,  5,  6,  8,  3,  8,  2,  6,  2,  8, -1, ],
  [ 1,  5,  6,  2,  1,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2, 10,  9,  5, 11,  9, 11,  8, 11,  5,  6, -1, -1, -1, -1, ],
  [ 0, 11,  3,  0,  6, 11,  0,  9,  6,  5,  6,  9,  1,  2, 10, -1, ],
  [11,  8,  5, 11,  5,  6,  8,  0,  5, 10,  5,  2,  0,  2,  5, -1, ],
  [ 6, 11,  3,  6,  3,  5,  2, 10,  3, 10,  5,  3, -1, -1, -1, -1, ],
  [ 1,  3,  6,  1,  6, 10,  3,  8,  6,  5,  6,  9,  8,  9,  6, -1, ],
  [10,  1,  0, 10,  0,  6,  9,  5,  0,  5,  6,  0, -1, -1, -1, -1, ],
  [ 0,  3,  8,  5,  6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  5,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  6,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  0,  1,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  8,  3,  1,  9,  8,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  3, 11, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  0,  8, 11,  2,  0, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  1,  9,  2,  3, 11,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5, 10,  6,  1,  9,  2,  9, 11,  2,  9,  8, 11, -1, -1, -1, -1, ],
  [ 1,  6,  5,  2,  6,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  6,  5,  1,  2,  6,  3,  0,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  6,  5,  9,  0,  6,  0,  2,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  9,  8,  5,  8,  2,  5,  2,  6,  3,  2,  8, -1, -1, -1, -1, ],
  [ 6,  3, 11,  6,  5,  3,  5,  1,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8, 11,  0, 11,  5,  0,  5,  1,  5, 11,  6, -1, -1, -1, -1, ],
  [ 3, 11,  6,  0,  3,  6,  0,  6,  5,  0,  5,  9, -1, -1, -1, -1, ],
  [ 6,  5,  9,  6,  9, 11, 11,  9,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5, 10,  6,  4,  7,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  3,  0,  4,  7,  3,  6,  5, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  9,  0,  5, 10,  6,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  6,  5,  1,  9,  7,  1,  7,  3,  7,  9,  4, -1, -1, -1, -1, ],
  [ 3, 11,  2,  7,  8,  4, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5, 10,  6,  4,  7,  2,  4,  2,  0,  2,  7, 11, -1, -1, -1, -1, ],
  [ 0,  1,  9,  4,  7,  8,  2,  3, 11,  5, 10,  6, -1, -1, -1, -1, ],
  [ 9,  2,  1,  9, 11,  2,  9,  4, 11,  7, 11,  4,  5, 10,  6, -1, ],
  [ 6,  1,  2,  6,  5,  1,  4,  7,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2,  5,  5,  2,  6,  3,  0,  4,  3,  4,  7, -1, -1, -1, -1, ],
  [ 8,  4,  7,  9,  0,  5,  0,  6,  5,  0,  2,  6, -1, -1, -1, -1, ],
  [ 7,  3,  9,  7,  9,  4,  3,  2,  9,  5,  9,  6,  2,  6,  9, -1, ],
  [ 8,  4,  7,  3, 11,  5,  3,  5,  1,  5, 11,  6, -1, -1, -1, -1, ],
  [ 5,  1, 11,  5, 11,  6,  1,  0, 11,  7, 11,  4,  0,  4, 11, -1, ],
  [ 0,  5,  9,  0,  6,  5,  0,  3,  6, 11,  6,  3,  8,  4,  7, -1, ],
  [ 6,  5,  9,  6,  9, 11,  4,  7,  9,  7, 11,  9, -1, -1, -1, -1, ],
  [10,  4,  9,  6,  4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4, 10,  6,  4,  9, 10,  0,  8,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  0,  1, 10,  6,  0,  6,  4,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  3,  1,  8,  1,  6,  8,  6,  4,  6,  1, 10, -1, -1, -1, -1, ],
  [10,  4,  9, 10,  6,  4, 11,  2,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  2,  2,  8, 11,  4,  9, 10,  4, 10,  6, -1, -1, -1, -1, ],
  [ 3, 11,  2,  0,  1,  6,  0,  6,  4,  6,  1, 10, -1, -1, -1, -1, ],
  [ 6,  4,  1,  6,  1, 10,  4,  8,  1,  2,  1, 11,  8, 11,  1, -1, ],
  [ 1,  4,  9,  1,  2,  4,  2,  6,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  0,  8,  1,  2,  9,  2,  4,  9,  2,  6,  4, -1, -1, -1, -1, ],
  [ 0,  2,  4,  4,  2,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  3,  2,  8,  2,  4,  4,  2,  6, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  6,  4,  9,  3,  6,  9,  1,  3, 11,  6,  3, -1, -1, -1, -1, ],
  [ 8, 11,  1,  8,  1,  0, 11,  6,  1,  9,  1,  4,  6,  4,  1, -1, ],
  [ 3, 11,  6,  3,  6,  0,  0,  6,  4, -1, -1, -1, -1, -1, -1, -1, ],
  [ 6,  4,  8, 11,  6,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7, 10,  6,  7,  8, 10,  8,  9, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  7,  3,  0, 10,  7,  0,  9, 10,  6,  7, 10, -1, -1, -1, -1, ],
  [10,  6,  7,  1, 10,  7,  1,  7,  8,  1,  8,  0, -1, -1, -1, -1, ],
  [10,  6,  7, 10,  7,  1,  1,  7,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  3, 11, 10,  6,  8, 10,  8,  9,  8,  6,  7, -1, -1, -1, -1, ],
  [ 2,  0,  7,  2,  7, 11,  0,  9,  7,  6,  7, 10,  9, 10,  7, -1, ],
  [ 1,  8,  0,  1,  7,  8,  1, 10,  7,  6,  7, 10,  2,  3, 11, -1, ],
  [11,  2,  1, 11,  1,  7, 10,  6,  1,  6,  7,  1, -1, -1, -1, -1, ],
  [ 1,  2,  6,  1,  6,  8,  1,  8,  9,  8,  6,  7, -1, -1, -1, -1, ],
  [ 2,  6,  9,  2,  9,  1,  6,  7,  9,  0,  9,  3,  7,  3,  9, -1, ],
  [ 7,  8,  0,  7,  0,  6,  6,  0,  2, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  3,  2,  6,  7,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  9,  6,  8,  6,  7,  9,  1,  6, 11,  6,  3,  1,  3,  6, -1, ],
  [ 0,  9,  1, 11,  6,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 7,  8,  0,  7,  0,  6,  3, 11,  0, 11,  6,  0, -1, -1, -1, -1, ],
  [ 7, 11,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  5, 10,  7,  5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  5, 10, 11,  7,  5,  8,  3,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5, 11,  7,  5, 10, 11,  1,  9,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [10,  7,  5, 10, 11,  7,  9,  8,  1,  8,  3,  1, -1, -1, -1, -1, ],
  [ 2,  5, 10,  2,  3,  5,  3,  7,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  2,  0,  8,  5,  2,  8,  7,  5, 10,  2,  5, -1, -1, -1, -1, ],
  [ 9,  0,  1,  5, 10,  3,  5,  3,  7,  3, 10,  2, -1, -1, -1, -1, ],
  [ 9,  8,  2,  9,  2,  1,  8,  7,  2, 10,  2,  5,  7,  5,  2, -1, ],
  [11,  1,  2, 11,  7,  1,  7,  5,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3,  1,  2,  7,  1,  7,  5,  7,  2, 11, -1, -1, -1, -1, ],
  [ 9,  7,  5,  9,  2,  7,  9,  0,  2,  2, 11,  7, -1, -1, -1, -1, ],
  [ 7,  5,  2,  7,  2, 11,  5,  9,  2,  3,  2,  8,  9,  8,  2, -1, ],
  [ 1,  3,  5,  3,  7,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  7,  0,  7,  1,  1,  7,  5, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  0,  3,  9,  3,  5,  5,  3,  7, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9,  8,  7,  5,  9,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  8,  4,  5, 10,  8, 10, 11,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 5,  0,  4,  5, 11,  0,  5, 10, 11, 11,  3,  0, -1, -1, -1, -1, ],
  [ 0,  1,  9,  8,  4, 10,  8, 10, 11, 10,  4,  5, -1, -1, -1, -1, ],
  [10, 11,  4, 10,  4,  5, 11,  3,  4,  9,  4,  1,  3,  1,  4, -1, ],
  [ 2,  5, 10,  3,  5,  2,  3,  4,  5,  3,  8,  4, -1, -1, -1, -1, ],
  [ 5, 10,  2,  5,  2,  4,  4,  2,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3, 10,  2,  3,  5, 10,  3,  8,  5,  4,  5,  8,  0,  1,  9, -1, ],
  [ 5, 10,  2,  5,  2,  4,  1,  9,  2,  9,  4,  2, -1, -1, -1, -1, ],
  [ 2,  5,  1,  2,  8,  5,  2, 11,  8,  4,  5,  8, -1, -1, -1, -1, ],
  [ 0,  4, 11,  0, 11,  3,  4,  5, 11,  2, 11,  1,  5,  1, 11, -1, ],
  [ 0,  2,  5,  0,  5,  9,  2, 11,  5,  4,  5,  8, 11,  8,  5, -1, ],
  [ 9,  4,  5,  2, 11,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  4,  5,  8,  5,  3,  3,  5,  1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  4,  5,  1,  0,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 8,  4,  5,  8,  5,  3,  9,  0,  5,  0,  3,  5, -1, -1, -1, -1, ],
  [ 9,  4,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4, 11,  7,  4,  9, 11,  9, 10, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  8,  3,  4,  9,  7,  9, 11,  7,  9, 10, 11, -1, -1, -1, -1, ],
  [ 1, 10, 11,  1, 11,  4,  1,  4,  0,  7,  4, 11, -1, -1, -1, -1, ],
  [ 3,  1,  4,  3,  4,  8,  1, 10,  4,  7,  4, 11, 10, 11,  4, -1, ],
  [ 2,  9, 10,  2,  7,  9,  2,  3,  7,  7,  4,  9, -1, -1, -1, -1, ],
  [ 9, 10,  7,  9,  7,  4, 10,  2,  7,  8,  7,  0,  2,  0,  7, -1, ],
  [ 3,  7, 10,  3, 10,  2,  7,  4, 10,  1, 10,  0,  4,  0, 10, -1, ],
  [ 1, 10,  2,  8,  7,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4, 11,  7,  9, 11,  4,  9,  2, 11,  9,  1,  2, -1, -1, -1, -1, ],
  [ 9,  7,  4,  9, 11,  7,  9,  1, 11,  2, 11,  1,  0,  8,  3, -1, ],
  [11,  7,  4, 11,  4,  2,  2,  4,  0, -1, -1, -1, -1, -1, -1, -1, ],
  [11,  7,  4, 11,  4,  2,  8,  3,  4,  3,  2,  4, -1, -1, -1, -1, ],
  [ 4,  9,  1,  4,  1,  7,  7,  1,  3, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  9,  1,  4,  1,  7,  0,  8,  1,  8,  7,  1, -1, -1, -1, -1, ],
  [ 4,  0,  3,  7,  4,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 4,  8,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9, 10,  8, 10, 11,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  0,  9,  3,  9, 11, 11,  9, 10, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  1, 10,  0, 10,  8,  8, 10, 11, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  1, 10, 11,  3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  3,  8,  2,  8, 10, 10,  8,  9, -1, -1, -1, -1, -1, -1, -1, ],
  [ 9, 10,  2,  0,  9,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 2,  3,  8,  2,  8, 10,  0,  1,  8,  1, 10,  8, -1, -1, -1, -1, ],
  [ 1, 10,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  2, 11,  1, 11,  9,  9, 11,  8, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  0,  9,  3,  9, 11,  1,  2,  9,  2, 11,  9, -1, -1, -1, -1, ],
  [ 0,  2, 11,  8,  0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 3,  2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 1,  3,  8,  9,  1,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  9,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [ 0,  3,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ],
  [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ]
 ]

for idx, verts in enumerate( triTable ) :
 verts = [ x for x in verts if x != -1 ]
 triTable[ idx ] = verts


def merge_triangles( a, b ) :
 assert a
 assert b
 isshared = [ x in a for x in b ]
 shared   = [ x for x in b if x in a ]
 unshared = [ x for x in b if not x in a ]
 numshared = len( shared )
 if numshared == 0 :
  return False
 if numshared == 1 :
  return False
 if numshared == 2 :
  edge = [-1,-1]
  if not isshared[ 0 ] :
   edge = [ shared[1], shared[0] ]
  if not isshared[ 1 ] :
   edge = [ shared[0], shared[1] ]
  if not isshared[ 2 ] :
   edge = [ shared[1], shared[0] ]
  face = list( a )
  idx = face.index( edge[1] )
  face.insert( idx, unshared[0] )
  assert face
  return face


polyTable = []
lineTable = []

for casenr, verts in enumerate(triTable) :
 vc = len( verts )
 if vc == 0 :
  polyTable.append( None )
  continue
 if vc == 3 :
  polyTable.append( ( verts, ) )
  #print vc, verts
  continue
 if vc == 6 :
  a = verts[ :3 ]
  b = verts[ 3: ]
  face = merge_triangles( a, b )
  if face :
   polyTable.append( ( face, ) )
   #print "4",face
  else :
   polyTable.append( ( a, b ) )
   #print "3+3",a,b
 if vc == 9 :
  # This could be one quad and one triangle or a pentagon?
  a = verts[ 0:3 ]
  b = verts[ 3:6 ]
  c = verts[ 6:9 ]
  face_ab = merge_triangles( a, b )
  face_bc = merge_triangles( b, c )
  if face_ab and face_bc :
   face = merge_triangles( face_ab, c )
   #print "5", face
   assert face
   polyTable.append( ( face, ) )
   continue
  if face_ab :
   polyTable.append( ( face_ab, c ) )
   #print "4+3", face_ab, c
   continue
  if face_bc :
   polyTable.append( ( a, face_bc ) )
   #print "3+4", a,face_bc
   continue
  # just three triangles
  #print "3+3+3", a,b,c
  polyTable.append( ( a, b, c ) )
  continue
 if vc == 12 :
  # This could be two quads, or a hexagon?
  a = list(verts[ 0:3 ])
  b = list(verts[ 3:6 ])
  c = list(verts[ 6:9 ])
  d = list(verts[ 9:12])
  face_ab = merge_triangles( a, b )
  face_bc = merge_triangles( b, c )
  face_cd = merge_triangles( c, d )
  if face_ab and face_cd and not face_bc :
   polyTable.append( ( face_ab, face_cd ) )
   #print "4+4", face_ab, face_cd
   continue
  if face_ab and face_cd and face_bc :
   # One big hexagon
   face_abc = merge_triangles( face_ab, c )
   assert face_abc
   face_abcd = merge_triangles( face_abc, d )
   assert face_abcd
   #print "6", face_abcd
   polyTable.append( ( face_abcd, ) )
   continue
  if face_ab and face_bc :
   face_abc = merge_triangles( face_ab, c )
   #print "5+3", face_abc, d
   polyTable.append( ( face_abc, d ) )
   continue
  if face_bc and face_cd :
   face_bcd = merge_triangles( face_bc, d )
   #print "3+5", a, face_bcd
   polyTable.append( ( a, face_bcd ) )
   continue
  if face_ab and face_cd :
   #print "4+4", face_ab, face_cd
   polyTable.append( ( face_ab, face_cd ) )
   continue
  # Difficult case: give up.
  polyTable.append( None )

 if vc == 15 :
  # Five triangles.
  a = list(verts[ 0:3 ])
  b = list(verts[ 3:6 ])
  c = list(verts[ 6:9 ])
  d = list(verts[ 9:12])
  e = list(verts[12:15])
  face_ab = merge_triangles( a, b )
  face_bc = merge_triangles( b, c )
  face_cd = merge_triangles( c, d )
  face_de = merge_triangles( d, e )
  #print a,b,c,d,e
  #print face_ab, face_bc, face_cd, face_de
  # Difficult case: give up
  polyTable.append( None )
#print len( polyTable )
#print polyTable

for polies in polyTable :
 print polies
 v = []
 if polies :
  for p in polies :
   l = len( p )
   for i in range( l ) :
    v.append( p[ i       ] )
    v.append( p[ (i+1)%l ] )
 while len( v ) < 20 :
  v.append( -1 )
 lineTable.append( v )

print len( lineTable )

s = repr(lineTable)
s = s.replace( '[', '{' )
s = s.replace( ']', '}' )
s = s.replace( '},', '},\n' )

print s


Saturday, July 27, 2013

Evaluating PolyVox

In my pursuit of simulating soil digging, I started to evaluate the PolyVox library. This is a report on that evaluation.

Building on MacOSX is tricky. With LLVM version 4.2 (clang-425.0.28) installed, this error comes up when compiling the very first file: fatal error: 'cstdint' file not found. According to this StackOverflow thread this should be solved by invoking with: /usr/bin/clang++ -std=c++11 but I found this not to be the case. So instead I decided to just drag in the source files into a new XCode project.

After dragging in sources and headers, you need to set the project's header include path. It needs to find its way to polyvox/library/PolyVoxCore/include/ e.g.

In PolyVoxCore two warnings are issued by the compiler for SurfaceMesh::addVertex() and SurfaceMesh::getNoOfIndices() because they return 32 bit ints, and vector::size() returns 64 bit ints. Other than this, the code is very clean. Even LLVM's Analyzer does not find anything else on it.

PolyVox can store the volume as a series of 32x32x32 blocks. It would make sense to do the surface extraction on a per-block basis. That way, if voxels change, you only have to create new OpenGL VBOs for the blocks that are affected. It's not entirely clear how to do this. It may be enough to create multiple extractors on 32/32/32 boundaries, and then only execute extractors for blocks that have changed.

Redux

So, my opus magnum is the game The Little Crane That Could. Every day, people tell me that they want more levels for it. The truth is, my inspiration for new tasks/puzzles to be solved with a crane is now exhausted. That is why I released a level editor for the game. Still, people want more. Others suggest a sequel to the game. But I think there can only be a sequel if there is a significant improvement to the current game. So let's talk about this sequel. First, how to name it?

  • The Little Crane Reloaded
  • The Little Crane: Redux
  • The Little Crane Strikes Back
  • The Little Crane 2014 edition
  • The Little Crane That Could: The Diggening (thanks Matt)

With whatever name it ends up, some serious new tech needs to be part of it. A logical next step would be to add deformable terrain to it. It needs soil that you can dig into, pile up, move around, maybe even compact. Doing a convincing simulation of soil digging is incredibly hard. I don't think anyone has actually done this properly, and certainly not at a smooth 60fps real time manner. Can I do it? Probably not, but it would sure be fun to try. Let me list a few attempts by others.


Digger Simulator 2011 does not look too convincing at timestamp 27sec. The loading of the scoop is too contrived. Whatever approach they took, it is not worth pursuing judging from this video.

This paper from the university of Aachen looks more promising. However, since they incorporate height fields into their solution, it makes tunnels and overhangs impossible. The video is impressive. And their model supports compacting of the soil.

Atomontage is definitely one of the most impressive demos out there. The rock sections show cliffs and overhangs, but it is hard to judge whether the sand can do overhangs as well. Tyre impressions are done well, could it do digging, tunnelling?

Spin Tires looks pretty, but when closely examining the soil, you will see that they are using a simple height field. Again, this means no overhangs, no tunnelling, etc.

This video of Cubiquity Voxel Engine (using PolyVox) is not a soil simulator. But a powerful voxel engine could possible be a great starting point for simulating soil.

For now, I think I will study PolyVox, and see what is possible with this. If you have come across a good soil simulator (or deformable terrain algorithm) that is convincing and suitable for games, please drop a link in the comments. And thank you for reading.

Introduction

I will use this first post to introduce myself. I am a software developer from Vancouver, British Columbia. I am best known for a hit game I developed for iOS, called The Little Crane That Could. Since then, I've published many other games, none reaching the popularity of Little Crane. This is why I consider myself, for now, a one-hit-wonder. Because game development is so much fun, I will keep publishing new games though. It is more than a job, it is my life's biggest passion.

I graduated at the University of Amsterdam. I've spent a large part of my career specializing in Virtual Reality, and developing VR simulations for industry and academia.

I have kept a weblog before, but since my primary weblog was a mix between development topics and personal articles I decided to branch off a new weblog. The weblog you are reading now will solely be dedicated to documenting my game development efforts. This means less noise, more signal, for my tech oriented audience. Also, I love reading comments from you!