Skip to content

Instantly share code, notes, and snippets.

@amezh

amezh/MarchingCubes.js

Forked from dwilliamson/MarchingCubes.js
Created January 24, 2025 00:51
Show Gist options
  • Save amezh/0ff79c93024b72090b97af33a9549c4d to your computer and use it in GitHub Desktop.
Save amezh/0ff79c93024b72090b97af33a9549c4d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @dwilliamson dwilliamson revised this gist Feb 8, 2022. 1 changed file with 160 additions and 158 deletions.
    318 changes: 160 additions & 158 deletions MarchingCubes.js
    View file
    Original file line number Diff line number Diff line change
    @@ -30,6 +30,8 @@
    // | / | / | / | /
    // 0 +-------------+ 1 +------0------+
    //
    // Triangulation cases are generated prioritising rotations over inversions, which can introduce non-manifold geometry.
    //


    // Pair of vertex indices for each edge on the cube
    @@ -87,259 +89,259 @@ const EdgeMasks = [
    // For each MC case, a list of triangles, specified as triples of edge indices, terminated by -1
    const TriangleTable = [
    [ -1 ],
    [ 3, 8, 0, -1 ],
    [ 1, 0, 9, -1 ],
    [ 9, 1, 8, 8, 1, 3, -1 ],
    [ 3, 2, 11, -1 ],
    [ 2, 11, 0, 0, 11, 8, -1 ],
    [ 1, 0, 9, 3, 2, 11, -1 ],
    [ 0, 3, 8, -1 ],
    [ 0, 9, 1, -1 ],
    [ 3, 8, 1, 1, 8, 9, -1 ],
    [ 2, 11, 3, -1 ],
    [ 8, 0, 11, 11, 0, 2, -1 ],
    [ 3, 2, 11, 1, 0, 9, -1 ],
    [ 11, 1, 2, 11, 9, 1, 11, 8, 9, -1 ],
    [ 10, 2, 1, -1 ],
    [ 2, 1, 10, 0, 3, 8, -1 ],
    [ 0, 9, 2, 2, 9, 10, -1 ],
    [ 1, 10, 2, -1 ],
    [ 0, 3, 8, 2, 1, 10, -1 ],
    [ 10, 2, 9, 9, 2, 0, -1 ],
    [ 8, 2, 3, 8, 10, 2, 8, 9, 10, -1 ],
    [ 1, 10, 3, 3, 10, 11, -1 ],
    [ 11, 3, 10, 10, 3, 1, -1 ],
    [ 10, 0, 1, 10, 8, 0, 10, 11, 8, -1 ],
    [ 9, 3, 0, 9, 11, 3, 9, 10, 11, -1 ],
    [ 9, 11, 8, 10, 11, 9, -1 ],
    [ 7, 4, 8, -1 ],
    [ 0, 3, 4, 4, 3, 7, -1 ],
    [ 0, 9, 1, 4, 8, 7, -1 ],
    [ 8, 9, 11, 11, 9, 10, -1 ],
    [ 4, 8, 7, -1 ],
    [ 7, 4, 3, 3, 4, 0, -1 ],
    [ 4, 8, 7, 0, 9, 1, -1 ],
    [ 1, 4, 9, 1, 7, 4, 1, 3, 7, -1 ],
    [ 11, 3, 2, 8, 7, 4, -1 ],
    [ 8, 7, 4, 11, 3, 2, -1 ],
    [ 4, 11, 7, 4, 2, 11, 4, 0, 2, -1 ],
    [ 3, 2, 11, 0, 9, 1, 4, 8, 7, -1 ],
    [ 1, 4, 9, 2, 4, 1, 7, 4, 2, 11, 7, 2, -1 ],
    [ 7, 4, 8, 1, 10, 2, -1 ],
    [ 0, 9, 1, 8, 7, 4, 11, 3, 2, -1 ],
    [ 7, 4, 11, 11, 4, 2, 2, 4, 9, 2, 9, 1, -1 ],
    [ 4, 8, 7, 2, 1, 10, -1 ],
    [ 7, 4, 3, 3, 4, 0, 10, 2, 1, -1 ],
    [ 10, 2, 9, 9, 2, 0, 7, 4, 8, -1 ],
    [ 7, 4, 9, 2, 7, 9, 2, 3, 7, 2, 9, 10, -1 ],
    [ 10, 2, 3, 10, 3, 4, 3, 7, 4, 9, 10, 4, -1 ],
    [ 1, 10, 3, 3, 10, 11, 4, 8, 7, -1 ],
    [ 1, 4, 0, 11, 7, 4, 11, 4, 1, 10, 11, 1, -1 ],
    [ 8, 3, 0, 7, 4, 11, 4, 9, 11, 9, 10, 11, -1 ],
    [ 10, 11, 1, 11, 7, 4, 1, 11, 4, 1, 4, 0, -1 ],
    [ 7, 4, 8, 9, 3, 0, 9, 11, 3, 9, 10, 11, -1 ],
    [ 7, 4, 11, 4, 9, 11, 9, 10, 11, -1 ],
    [ 5, 9, 4, -1 ],
    [ 8, 0, 3, 9, 4, 5, -1 ],
    [ 1, 0, 5, 5, 0, 4, -1 ],
    [ 9, 4, 5, -1 ],
    [ 9, 4, 5, 8, 0, 3, -1 ],
    [ 4, 5, 0, 0, 5, 1, -1 ],
    [ 5, 8, 4, 5, 3, 8, 5, 1, 3, -1 ],
    [ 3, 2, 11, 5, 9, 4, -1 ],
    [ 9, 4, 5, 11, 3, 2, -1 ],
    [ 2, 11, 0, 0, 11, 8, 5, 9, 4, -1 ],
    [ 4, 5, 0, 0, 5, 1, 11, 3, 2, -1 ],
    [ 2, 5, 1, 8, 4, 5, 8, 5, 2, 11, 8, 2, -1 ],
    [ 5, 9, 4, 1, 10, 2, -1 ],
    [ 0, 3, 8, 1, 10, 2, 5, 9, 4, -1 ],
    [ 5, 1, 4, 1, 2, 11, 4, 1, 11, 4, 11, 8, -1 ],
    [ 1, 10, 2, 5, 9, 4, -1 ],
    [ 9, 4, 5, 0, 3, 8, 2, 1, 10, -1 ],
    [ 2, 5, 10, 2, 4, 5, 2, 0, 4, -1 ],
    [ 2, 5, 10, 3, 5, 2, 4, 5, 3, 8, 4, 3, -1 ],
    [ 10, 2, 5, 5, 2, 4, 4, 2, 3, 4, 3, 8, -1 ],
    [ 11, 3, 10, 10, 3, 1, 4, 5, 9, -1 ],
    [ 9, 0, 1, 4, 5, 8, 5, 10, 8, 10, 11, 8, -1 ],
    [ 4, 5, 10, 3, 4, 10, 3, 0, 4, 3, 10, 11, -1 ],
    [ 4, 5, 9, 10, 0, 1, 10, 8, 0, 10, 11, 8, -1 ],
    [ 11, 3, 0, 11, 0, 5, 0, 4, 5, 10, 11, 5, -1 ],
    [ 4, 5, 8, 5, 10, 8, 10, 11, 8, -1 ],
    [ 5, 9, 7, 7, 9, 8, -1 ],
    [ 8, 7, 9, 9, 7, 5, -1 ],
    [ 3, 9, 0, 3, 5, 9, 3, 7, 5, -1 ],
    [ 7, 0, 8, 7, 1, 0, 7, 5, 1, -1 ],
    [ 1, 7, 5, 3, 7, 1, -1 ],
    [ 7, 5, 3, 3, 5, 1, -1 ],
    [ 5, 9, 7, 7, 9, 8, 2, 11, 3, -1 ],
    [ 5, 9, 0, 11, 5, 0, 11, 7, 5, 11, 0, 2, -1 ],
    [ 3, 0, 8, 2, 11, 1, 11, 7, 1, 7, 5, 1, -1 ],
    [ 2, 11, 7, 2, 7, 9, 7, 5, 9, 0, 2, 9, -1 ],
    [ 2, 11, 3, 7, 0, 8, 7, 1, 0, 7, 5, 1, -1 ],
    [ 2, 11, 1, 11, 7, 1, 7, 5, 1, -1 ],
    [ 8, 7, 9, 9, 7, 5, 2, 1, 10, -1 ],
    [ 1, 9, 0, 10, 2, 5, 2, 3, 5, 3, 7, 5, -1 ],
    [ 8, 2, 0, 5, 10, 2, 5, 2, 8, 7, 5, 8, -1 ],
    [ 10, 2, 1, 3, 9, 0, 3, 5, 9, 3, 7, 5, -1 ],
    [ 7, 5, 8, 5, 10, 2, 8, 5, 2, 8, 2, 0, -1 ],
    [ 10, 2, 5, 2, 3, 5, 3, 7, 5, -1 ],
    [ 9, 8, 3, 1, 9, 3, 5, 11, 7, 5, 10, 11, -1 ],
    [ 8, 7, 5, 8, 5, 9, 11, 3, 10, 3, 1, 10, -1 ],
    [ 5, 11, 7, 10, 11, 5, 1, 9, 0, -1 ],
    [ 11, 5, 10, 7, 5, 11, 8, 3, 0, -1 ],
    [ 11, 5, 10, 7, 5, 11, -1 ],
    [ 11, 6, 7, -1 ],
    [ 3, 8, 0, 7, 11, 6, -1 ],
    [ 1, 0, 9, 7, 11, 6, -1 ],
    [ 5, 11, 7, 10, 11, 5, -1 ],
    [ 6, 7, 11, -1 ],
    [ 7, 11, 6, 3, 8, 0, -1 ],
    [ 6, 7, 11, 0, 9, 1, -1 ],
    [ 9, 1, 8, 8, 1, 3, 6, 7, 11, -1 ],
    [ 6, 7, 2, 2, 7, 3, -1 ],
    [ 3, 2, 7, 7, 2, 6, -1 ],
    [ 0, 7, 8, 0, 6, 7, 0, 2, 6, -1 ],
    [ 6, 7, 2, 2, 7, 3, 9, 1, 0, -1 ],
    [ 6, 7, 8, 1, 6, 8, 1, 2, 6, 1, 8, 9, -1 ],
    [ 10, 2, 1, 11, 6, 7, -1 ],
    [ 2, 1, 10, 3, 8, 0, 7, 11, 6, -1 ],
    [ 6, 7, 8, 6, 8, 1, 8, 9, 1, 2, 6, 1, -1 ],
    [ 11, 6, 7, 10, 2, 1, -1 ],
    [ 3, 8, 0, 11, 6, 7, 10, 2, 1, -1 ],
    [ 0, 9, 2, 2, 9, 10, 7, 11, 6, -1 ],
    [ 11, 2, 3, 6, 7, 10, 7, 8, 10, 8, 9, 10, -1 ],
    [ 6, 7, 11, 8, 2, 3, 8, 10, 2, 8, 9, 10, -1 ],
    [ 7, 10, 6, 7, 1, 10, 7, 3, 1, -1 ],
    [ 0, 7, 8, 1, 7, 0, 6, 7, 1, 10, 6, 1, -1 ],
    [ 6, 9, 10, 3, 0, 9, 3, 9, 6, 7, 3, 6, -1 ],
    [ 8, 0, 7, 7, 0, 6, 6, 0, 1, 6, 1, 10, -1 ],
    [ 7, 3, 6, 3, 0, 9, 6, 3, 9, 6, 9, 10, -1 ],
    [ 6, 7, 10, 7, 8, 10, 8, 9, 10, -1 ],
    [ 4, 8, 6, 6, 8, 11, -1 ],
    [ 11, 6, 8, 8, 6, 4, -1 ],
    [ 6, 3, 11, 6, 0, 3, 6, 4, 0, -1 ],
    [ 11, 6, 8, 8, 6, 4, 1, 0, 9, -1 ],
    [ 11, 1, 3, 4, 9, 1, 4, 1, 11, 6, 4, 11, -1 ],
    [ 1, 3, 9, 3, 11, 6, 9, 3, 6, 9, 6, 4, -1 ],
    [ 2, 8, 3, 2, 4, 8, 2, 6, 4, -1 ],
    [ 0, 6, 4, 2, 6, 0, -1 ],
    [ 0, 8, 3, 9, 1, 4, 1, 2, 4, 2, 6, 4, -1 ],
    [ 4, 0, 6, 6, 0, 2, -1 ],
    [ 9, 1, 0, 2, 8, 3, 2, 4, 8, 2, 6, 4, -1 ],
    [ 9, 1, 4, 1, 2, 4, 2, 6, 4, -1 ],
    [ 4, 8, 6, 6, 8, 11, 1, 10, 2, -1 ],
    [ 2, 3, 11, 1, 10, 0, 10, 6, 0, 6, 4, 0, -1 ],
    [ 2, 0, 8, 11, 2, 8, 10, 4, 9, 10, 6, 4, -1 ],
    [ 1, 10, 2, 6, 3, 11, 6, 0, 3, 6, 4, 0, -1 ],
    [ 11, 6, 4, 11, 4, 8, 10, 2, 9, 2, 0, 9, -1 ],
    [ 10, 4, 9, 6, 4, 10, 11, 2, 3, -1 ],
    [ 4, 8, 3, 10, 4, 3, 10, 6, 4, 10, 3, 1, -1 ],
    [ 4, 8, 3, 4, 3, 10, 3, 1, 10, 6, 4, 10, -1 ],
    [ 1, 10, 0, 10, 6, 0, 6, 4, 0, -1 ],
    [ 4, 10, 6, 9, 10, 4, 0, 8, 3, -1 ],
    [ 10, 4, 9, 6, 4, 10, -1 ],
    [ 4, 5, 9, 6, 7, 11, -1 ],
    [ 7, 11, 6, 8, 0, 3, 9, 4, 5, -1 ],
    [ 4, 10, 6, 9, 10, 4, -1 ],
    [ 6, 7, 11, 4, 5, 9, -1 ],
    [ 4, 5, 9, 7, 11, 6, 3, 8, 0, -1 ],
    [ 1, 0, 5, 5, 0, 4, 11, 6, 7, -1 ],
    [ 7, 8, 4, 11, 6, 3, 6, 5, 3, 5, 1, 3, -1 ],
    [ 11, 6, 7, 5, 8, 4, 5, 3, 8, 5, 1, 3, -1 ],
    [ 3, 2, 7, 7, 2, 6, 9, 4, 5, -1 ],
    [ 4, 7, 8, 5, 9, 6, 9, 0, 6, 0, 2, 6, -1 ],
    [ 0, 4, 7, 3, 0, 7, 1, 6, 5, 1, 2, 6, -1 ],
    [ 5, 9, 4, 0, 7, 8, 0, 6, 7, 0, 2, 6, -1 ],
    [ 3, 2, 6, 3, 6, 7, 1, 0, 5, 0, 4, 5, -1 ],
    [ 6, 1, 2, 5, 1, 6, 4, 7, 8, -1 ],
    [ 6, 7, 11, 5, 9, 4, 1, 10, 2, -1 ],
    [ 8, 4, 7, 11, 2, 3, 0, 1, 9, 6, 5, 10, -1 ],
    [ 6, 5, 10, 7, 11, 4, 11, 2, 4, 2, 0, 4, -1 ],
    [ 2, 3, 11, 8, 4, 7, 10, 6, 5, -1 ],
    [ 5, 10, 6, 9, 4, 1, 4, 7, 1, 7, 3, 1, -1 ],
    [ 7, 8, 4, 0, 1, 9, 6, 5, 10, -1 ],
    [ 10, 2, 1, 6, 7, 11, 4, 5, 9, -1 ],
    [ 0, 3, 8, 4, 5, 9, 11, 6, 7, 10, 2, 1, -1 ],
    [ 7, 11, 6, 2, 5, 10, 2, 4, 5, 2, 0, 4, -1 ],
    [ 8, 4, 7, 5, 10, 6, 3, 11, 2, -1 ],
    [ 9, 4, 5, 7, 10, 6, 7, 1, 10, 7, 3, 1, -1 ],
    [ 10, 6, 5, 7, 8, 4, 1, 9, 0, -1 ],
    [ 4, 3, 0, 7, 3, 4, 6, 5, 10, -1 ],
    [ 8, 4, 7, 10, 6, 5, -1 ],
    [ 10, 6, 5, 8, 4, 7, -1 ],
    [ 9, 6, 5, 9, 11, 6, 9, 8, 11, -1 ],
    [ 3, 9, 0, 11, 9, 3, 5, 9, 11, 6, 5, 11, -1 ],
    [ 11, 6, 5, 0, 11, 5, 0, 8, 11, 0, 5, 1, -1 ],
    [ 11, 6, 3, 3, 6, 0, 0, 6, 5, 0, 5, 9, -1 ],
    [ 11, 6, 5, 11, 5, 0, 5, 1, 0, 8, 11, 0, -1 ],
    [ 11, 6, 3, 6, 5, 3, 5, 1, 3, -1 ],
    [ 3, 9, 8, 6, 5, 9, 6, 9, 3, 2, 6, 3, -1 ],
    [ 9, 8, 5, 8, 3, 2, 5, 8, 2, 5, 2, 6, -1 ],
    [ 5, 9, 6, 9, 0, 6, 0, 2, 6, -1 ],
    [ 1, 6, 5, 2, 6, 1, 3, 0, 8, -1 ],
    [ 6, 1, 2, 5, 1, 6, -1 ],
    [ 10, 6, 5, 2, 1, 11, 1, 9, 11, 9, 8, 11, -1 ],
    [ 6, 5, 10, 9, 0, 1, 11, 2, 3, -1 ],
    [ 1, 6, 5, 2, 6, 1, -1 ],
    [ 2, 1, 10, 9, 6, 5, 9, 11, 6, 9, 8, 11, -1 ],
    [ 9, 0, 1, 3, 11, 2, 5, 10, 6, -1 ],
    [ 11, 0, 8, 2, 0, 11, 10, 6, 5, -1 ],
    [ 5, 10, 6, 3, 11, 2, -1 ],
    [ 3, 11, 2, 5, 10, 6, -1 ],
    [ 1, 8, 3, 9, 8, 1, 5, 10, 6, -1 ],
    [ 0, 1, 9, 6, 5, 10, -1 ],
    [ 0, 8, 3, 10, 6, 5, -1 ],
    [ 5, 10, 6, -1 ],
    [ 6, 10, 5, -1 ],
    [ 3, 8, 0, 5, 6, 10, -1 ],
    [ 9, 1, 0, 10, 5, 6, -1 ],
    [ 6, 5, 10, 0, 1, 9, -1 ],
    [ 8, 3, 0, 5, 10, 6, -1 ],
    [ 6, 5, 10, -1 ],
    [ 10, 5, 6, -1 ],
    [ 0, 3, 8, 6, 10, 5, -1 ],
    [ 10, 5, 6, 9, 1, 0, -1 ],
    [ 3, 8, 1, 1, 8, 9, 6, 10, 5, -1 ],
    [ 6, 10, 5, 2, 11, 3, -1 ],
    [ 2, 11, 3, 6, 10, 5, -1 ],
    [ 8, 0, 11, 11, 0, 2, 5, 6, 10, -1 ],
    [ 10, 5, 6, 1, 0, 9, 3, 2, 11, -1 ],
    [ 10, 1, 2, 5, 6, 9, 6, 11, 9, 11, 8, 9, -1 ],
    [ 2, 1, 6, 6, 1, 5, -1 ],
    [ 1, 0, 9, 2, 11, 3, 6, 10, 5, -1 ],
    [ 5, 6, 10, 11, 1, 2, 11, 9, 1, 11, 8, 9, -1 ],
    [ 5, 6, 1, 1, 6, 2, -1 ],
    [ 5, 6, 1, 1, 6, 2, 8, 0, 3, -1 ],
    [ 6, 9, 5, 6, 0, 9, 6, 2, 0, -1 ],
    [ 3, 6, 2, 9, 5, 6, 9, 6, 3, 8, 9, 3, -1 ],
    [ 6, 2, 5, 2, 3, 8, 5, 2, 8, 5, 8, 9, -1 ],
    [ 3, 6, 11, 3, 5, 6, 3, 1, 5, -1 ],
    [ 8, 0, 1, 6, 8, 1, 6, 11, 8, 6, 1, 5, -1 ],
    [ 9, 3, 0, 5, 3, 9, 11, 3, 5, 6, 11, 5, -1 ],
    [ 8, 0, 1, 8, 1, 6, 1, 5, 6, 11, 8, 6, -1 ],
    [ 11, 3, 6, 6, 3, 5, 5, 3, 0, 5, 0, 9, -1 ],
    [ 5, 6, 9, 6, 11, 9, 11, 8, 9, -1 ],
    [ 7, 4, 8, 5, 6, 10, -1 ],
    [ 5, 6, 10, 7, 4, 8, -1 ],
    [ 0, 3, 4, 4, 3, 7, 10, 5, 6, -1 ],
    [ 4, 8, 7, 9, 1, 0, 10, 5, 6, -1 ],
    [ 5, 4, 9, 6, 10, 7, 10, 1, 7, 1, 3, 7, -1 ],
    [ 11, 3, 2, 7, 4, 8, 5, 6, 10, -1 ],
    [ 6, 11, 7, 10, 5, 2, 5, 4, 2, 4, 0, 2, -1 ],
    [ 4, 9, 5, 6, 11, 7, 8, 3, 0, 10, 1, 2, -1 ],
    [ 11, 7, 6, 4, 9, 5, 2, 10, 1, -1 ],
    [ 5, 6, 10, 4, 8, 7, 0, 9, 1, -1 ],
    [ 6, 10, 5, 1, 4, 9, 1, 7, 4, 1, 3, 7, -1 ],
    [ 7, 4, 8, 6, 10, 5, 2, 11, 3, -1 ],
    [ 10, 5, 6, 4, 11, 7, 4, 2, 11, 4, 0, 2, -1 ],
    [ 4, 8, 7, 6, 10, 5, 3, 2, 11, 1, 0, 9, -1 ],
    [ 1, 2, 10, 11, 7, 6, 9, 5, 4, -1 ],
    [ 2, 1, 6, 6, 1, 5, 8, 7, 4, -1 ],
    [ 4, 0, 1, 5, 4, 1, 7, 2, 3, 7, 6, 2, -1 ],
    [ 4, 9, 5, 8, 7, 0, 7, 6, 0, 6, 2, 0, -1 ],
    [ 0, 3, 7, 0, 7, 4, 2, 1, 6, 1, 5, 6, -1 ],
    [ 8, 7, 4, 6, 9, 5, 6, 0, 9, 6, 2, 0, -1 ],
    [ 7, 2, 3, 6, 2, 7, 5, 4, 9, -1 ],
    [ 7, 6, 11, 4, 8, 5, 8, 3, 5, 3, 1, 5, -1 ],
    [ 4, 8, 7, 3, 6, 11, 3, 5, 6, 3, 1, 5, -1 ],
    [ 5, 0, 1, 4, 0, 5, 7, 6, 11, -1 ],
    [ 6, 11, 7, 3, 0, 8, 5, 4, 9, -1 ],
    [ 9, 5, 4, 11, 7, 6, -1 ],
    [ 9, 4, 10, 10, 4, 6, -1 ],
    [ 9, 5, 4, 6, 11, 7, 0, 8, 3, -1 ],
    [ 11, 7, 6, 9, 5, 4, -1 ],
    [ 6, 10, 4, 4, 10, 9, -1 ],
    [ 6, 10, 4, 4, 10, 9, 3, 8, 0, -1 ],
    [ 0, 10, 1, 0, 6, 10, 0, 4, 6, -1 ],
    [ 6, 10, 1, 8, 6, 1, 8, 4, 6, 8, 1, 3, -1 ],
    [ 6, 10, 1, 6, 1, 8, 1, 3, 8, 4, 6, 8, -1 ],
    [ 9, 4, 10, 10, 4, 6, 3, 2, 11, -1 ],
    [ 10, 9, 0, 2, 10, 0, 6, 8, 4, 6, 11, 8, -1 ],
    [ 2, 10, 1, 11, 3, 6, 3, 0, 6, 0, 4, 6, -1 ],
    [ 2, 11, 8, 2, 8, 0, 6, 10, 4, 10, 9, 4, -1 ],
    [ 11, 3, 2, 0, 10, 1, 0, 6, 10, 0, 4, 6, -1 ],
    [ 6, 8, 4, 11, 8, 6, 2, 10, 1, -1 ],
    [ 4, 1, 9, 4, 2, 1, 4, 6, 2, -1 ],
    [ 0, 1, 9, 3, 8, 2, 8, 4, 2, 4, 6, 2, -1 ],
    [ 4, 2, 0, 6, 2, 4, -1 ],
    [ 3, 8, 0, 4, 1, 9, 4, 2, 1, 4, 6, 2, -1 ],
    [ 6, 2, 4, 4, 2, 0, -1 ],
    [ 3, 8, 2, 8, 4, 2, 4, 6, 2, -1 ],
    [ 11, 4, 6, 1, 9, 4, 1, 4, 11, 3, 1, 11, -1 ],
    [ 4, 6, 9, 6, 11, 3, 9, 6, 3, 9, 3, 1, -1 ],
    [ 8, 6, 11, 4, 6, 8, 9, 0, 1, -1 ],
    [ 11, 3, 6, 3, 0, 6, 0, 4, 6, -1 ],
    [ 6, 8, 4, 11, 8, 6, -1 ],
    [ 8, 6, 11, 4, 6, 8, -1 ],
    [ 10, 7, 6, 10, 8, 7, 10, 9, 8, -1 ],
    [ 0, 10, 9, 7, 6, 10, 7, 10, 0, 3, 7, 0, -1 ],
    [ 0, 10, 1, 8, 10, 0, 6, 10, 8, 7, 6, 8, -1 ],
    [ 3, 7, 0, 7, 6, 10, 0, 7, 10, 0, 10, 9, -1 ],
    [ 6, 10, 7, 7, 10, 8, 8, 10, 1, 8, 1, 0, -1 ],
    [ 6, 10, 7, 10, 1, 7, 1, 3, 7, -1 ],
    [ 11, 7, 6, 3, 2, 8, 2, 10, 8, 10, 9, 8, -1 ],
    [ 3, 2, 11, 10, 7, 6, 10, 8, 7, 10, 9, 8, -1 ],
    [ 2, 9, 0, 10, 9, 2, 6, 11, 7, -1 ],
    [ 10, 1, 2, 0, 8, 3, 6, 11, 7, -1 ],
    [ 1, 2, 10, 7, 6, 11, -1 ],
    [ 2, 1, 9, 7, 2, 9, 7, 6, 2, 7, 9, 8, -1 ],
    [ 0, 8, 3, 7, 6, 11, 1, 2, 10, -1 ],
    [ 7, 6, 11, 1, 2, 10, -1 ],
    [ 2, 1, 9, 2, 9, 7, 9, 8, 7, 6, 2, 7, -1 ],
    [ 2, 7, 6, 3, 7, 2, 0, 1, 9, -1 ],
    [ 8, 7, 0, 7, 6, 0, 6, 2, 0, -1 ],
    [ 2, 7, 6, 3, 7, 2, -1 ],
    [ 7, 2, 3, 6, 2, 7, -1 ],
    [ 8, 1, 9, 3, 1, 8, 11, 7, 6, -1 ],
    [ 9, 0, 1, 6, 11, 7, -1 ],
    [ 0, 8, 3, 6, 11, 7, -1 ],
    [ 7, 6, 11, -1 ],
    [ 10, 5, 11, 11, 5, 7, -1 ],
    [ 11, 7, 6, 1, 9, 0, -1 ],
    [ 6, 11, 7, 0, 8, 3, -1 ],
    [ 11, 7, 6, -1 ],
    [ 7, 11, 5, 5, 11, 10, -1 ],
    [ 10, 5, 11, 11, 5, 7, 0, 3, 8, -1 ],
    [ 7, 11, 5, 5, 11, 10, 0, 9, 1, -1 ],
    [ 8, 9, 5, 7, 8, 5, 3, 10, 1, 3, 11, 10, -1 ],
    [ 7, 11, 10, 7, 10, 5, 3, 8, 1, 8, 9, 1, -1 ],
    [ 5, 2, 10, 5, 3, 2, 5, 7, 3, -1 ],
    [ 10, 0, 2, 7, 8, 0, 7, 0, 10, 5, 7, 10, -1 ],
    [ 1, 2, 10, 0, 9, 3, 9, 5, 3, 5, 7, 3, -1 ],
    [ 5, 7, 10, 7, 8, 0, 10, 7, 0, 10, 0, 2, -1 ],
    [ 0, 9, 1, 5, 2, 10, 5, 3, 2, 5, 7, 3, -1 ],
    [ 9, 7, 8, 5, 7, 9, 10, 1, 2, -1 ],
    [ 1, 11, 2, 1, 7, 11, 1, 5, 7, -1 ],
    [ 3, 11, 2, 8, 0, 7, 0, 1, 7, 1, 5, 7, -1 ],
    [ 0, 9, 5, 11, 0, 5, 11, 2, 0, 11, 5, 7, -1 ],
    [ 8, 0, 3, 1, 11, 2, 1, 7, 11, 1, 5, 7, -1 ],
    [ 7, 11, 2, 7, 2, 9, 2, 0, 9, 5, 7, 9, -1 ],
    [ 7, 9, 5, 8, 9, 7, 3, 11, 2, -1 ],
    [ 1, 7, 3, 5, 7, 1, -1 ],
    [ 3, 1, 7, 7, 1, 5, -1 ],
    [ 8, 0, 7, 0, 1, 7, 1, 5, 7, -1 ],
    [ 0, 9, 3, 9, 5, 3, 5, 7, 3, -1 ],
    [ 7, 9, 5, 8, 9, 7, -1 ],
    [ 9, 7, 8, 5, 7, 9, -1 ],
    [ 8, 5, 4, 8, 10, 5, 8, 11, 10, -1 ],
    [ 10, 5, 4, 3, 10, 4, 3, 11, 10, 3, 4, 0, -1 ],
    [ 9, 5, 4, 1, 0, 10, 0, 8, 10, 8, 11, 10, -1 ],
    [ 0, 3, 11, 0, 11, 5, 11, 10, 5, 4, 0, 5, -1 ],
    [ 1, 0, 9, 8, 5, 4, 8, 10, 5, 8, 11, 10, -1 ],
    [ 10, 3, 11, 1, 3, 10, 9, 5, 4, -1 ],
    [ 8, 5, 4, 3, 5, 8, 10, 5, 3, 2, 10, 3, -1 ],
    [ 3, 2, 8, 8, 2, 4, 4, 2, 10, 4, 10, 5, -1 ],
    [ 10, 5, 2, 5, 4, 2, 4, 0, 2, -1 ],
    [ 8, 3, 0, 2, 10, 1, 4, 9, 5, -1 ],
    [ 4, 9, 5, 2, 10, 1, -1 ],
    [ 2, 8, 11, 5, 4, 8, 5, 8, 2, 1, 5, 2, -1 ],
    [ 5, 4, 9, 8, 3, 0, 10, 1, 2, -1 ],
    [ 2, 10, 1, 4, 9, 5, -1 ],
    [ 8, 11, 4, 11, 2, 1, 4, 11, 1, 4, 1, 5, -1 ],
    [ 0, 5, 4, 1, 5, 0, 2, 3, 11, -1 ],
    [ 0, 11, 2, 8, 11, 0, 4, 9, 5, -1 ],
    [ 11, 2, 3, 4, 9, 5, -1 ],
    [ 5, 4, 9, 2, 3, 11, -1 ],
    [ 4, 8, 5, 8, 3, 5, 3, 1, 5, -1 ],
    [ 5, 0, 1, 4, 0, 5, -1 ],
    [ 3, 0, 8, 5, 4, 9, -1 ],
    [ 4, 9, 5, -1 ],
    [ 0, 5, 4, 1, 5, 0, -1 ],
    [ 5, 4, 9, 3, 0, 8, -1 ],
    [ 5, 4, 9, -1 ],
    [ 11, 4, 7, 11, 9, 4, 11, 10, 9, -1 ],
    [ 8, 4, 7, 0, 3, 9, 3, 11, 9, 11, 10, 9, -1 ],
    [ 7, 0, 4, 10, 1, 0, 10, 0, 7, 11, 10, 7, -1 ],
    [ 0, 3, 8, 11, 4, 7, 11, 9, 4, 11, 10, 9, -1 ],
    [ 11, 10, 7, 10, 1, 0, 7, 10, 0, 7, 0, 4, -1 ],
    [ 3, 10, 1, 11, 10, 3, 7, 8, 4, -1 ],
    [ 9, 4, 7, 2, 9, 7, 2, 10, 9, 2, 7, 3, -1 ],
    [ 3, 2, 10, 3, 10, 4, 10, 9, 4, 7, 3, 4, -1 ],
    [ 9, 2, 10, 0, 2, 9, 8, 4, 7, -1 ],
    [ 3, 4, 7, 0, 4, 3, 1, 2, 10, -1 ],
    [ 8, 4, 7, 2, 10, 1, -1 ],
    [ 4, 1, 9, 7, 1, 4, 2, 1, 7, 11, 2, 7, -1 ],
    [ 11, 2, 3, 1, 9, 0, 7, 8, 4, -1 ],
    [ 7, 8, 4, 10, 1, 2, -1 ],
    [ 7, 11, 4, 4, 11, 9, 9, 11, 2, 9, 2, 1, -1 ],
    [ 1, 9, 0, 4, 7, 8, 2, 3, 11, -1 ],
    [ 7, 11, 4, 11, 2, 4, 2, 0, 4, -1 ],
    [ 2, 3, 11, 4, 7, 8, -1 ],
    [ 4, 7, 8, 2, 3, 11, -1 ],
    [ 9, 4, 1, 4, 7, 1, 7, 3, 1, -1 ],
    [ 1, 9, 0, 7, 8, 4, -1 ],
    [ 4, 3, 0, 7, 3, 4, -1 ],
    [ 8, 4, 7, -1 ],
    [ 8, 10, 9, 11, 10, 8, -1 ],
    [ 7, 8, 4, 1, 9, 0, -1 ],
    [ 3, 4, 7, 0, 4, 3, -1 ],
    [ 7, 8, 4, -1 ],
    [ 11, 10, 8, 8, 10, 9, -1 ],
    [ 0, 3, 9, 3, 11, 9, 11, 10, 9, -1 ],
    [ 1, 0, 10, 0, 8, 10, 8, 11, 10, -1 ],
    [ 3, 10, 1, 11, 10, 3, -1 ],
    [ 10, 3, 11, 1, 3, 10, -1 ],
    [ 3, 2, 8, 2, 10, 8, 10, 9, 8, -1 ],
    [ 2, 9, 0, 10, 9, 2, -1 ],
    [ 10, 1, 2, 8, 3, 0, -1 ],
    [ 1, 2, 10, -1 ],
    [ 9, 2, 10, 0, 2, 9, -1 ],
    [ 8, 3, 0, 10, 1, 2, -1 ],
    [ 2, 10, 1, -1 ],
    [ 2, 1, 11, 1, 9, 11, 9, 8, 11, -1 ],
    [ 9, 0, 1, 11, 2, 3, -1 ],
    [ 0, 11, 2, 8, 11, 0, -1 ],
    [ 11, 2, 3, -1 ],
    [ 8, 1, 9, 3, 1, 8, -1 ],
    [ 9, 0, 1, -1 ],
    [ 0, 8, 3, -1 ],
    [ 11, 2, 3, 9, 0, 1, -1 ],
    [ 11, 0, 8, 2, 0, 11, -1 ],
    [ 3, 11, 2, -1 ],
    [ 1, 8, 3, 9, 8, 1, -1 ],
    [ 1, 9, 0, -1 ],
    [ 8, 3, 0, -1 ],
    [ -1 ],
    ];
  2. @dwilliamson dwilliamson revised this gist Feb 7, 2022. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion MarchingCubes.js
    View file
    Original file line number Diff line number Diff line change
    @@ -20,7 +20,7 @@
    //
    // Vertex and edge layout:
    //
    // 7 6
    // 6 7
    // +-------------+ +-----6-------+
    // / | / | / | /|
    // / | / | 11 7 10 5
  3. @dwilliamson dwilliamson created this gist Feb 7, 2022.
    345 changes: 345 additions & 0 deletions MarchingCubes.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,345 @@
    //
    // Lookup Tables for Marching Cubes
    //
    // These tables differ from the original paper (Marching Cubes: A High Resolution 3D Surface Construction Algorithm)
    //
    // The co-ordinate system has the more convenient properties:
    //
    // i = cube index [0, 7]
    // x = (i & 1) >> 0
    // y = (i & 2) >> 1
    // z = (i & 4) >> 2
    //
    // Axes are:
    //
    // y
    // | z
    // | /
    // | /
    // +----- x
    //
    // Vertex and edge layout:
    //
    // 7 6
    // +-------------+ +-----6-------+
    // / | / | / | /|
    // / | / | 11 7 10 5
    // 2 +-----+-------+ 3 | +-----+2------+ |
    // | 4 +-------+-----+ 5 | +-----4-+-----+
    // | / | / 3 8 1 9
    // | / | / | / | /
    // 0 +-------------+ 1 +------0------+
    //


    // Pair of vertex indices for each edge on the cube
    const EdgeVertexIndices = [
    [0, 1],
    [1, 3],
    [3, 2],
    [2, 0],
    [4, 5],
    [5, 7],
    [7, 6],
    [6, 4],
    [0, 4],
    [1, 5],
    [3, 7],
    [2, 6],
    ];

    // For each MC case, a mask of edge indices that need to be split
    const EdgeMasks = [
    0x0, 0x109, 0x203, 0x30a, 0x80c, 0x905, 0xa0f, 0xb06,
    0x406, 0x50f, 0x605, 0x70c, 0xc0a, 0xd03, 0xe09, 0xf00,
    0x190, 0x99, 0x393, 0x29a, 0x99c, 0x895, 0xb9f, 0xa96,
    0x596, 0x49f, 0x795, 0x69c, 0xd9a, 0xc93, 0xf99, 0xe90,
    0x230, 0x339, 0x33, 0x13a, 0xa3c, 0xb35, 0x83f, 0x936,
    0x636, 0x73f, 0x435, 0x53c, 0xe3a, 0xf33, 0xc39, 0xd30,
    0x3a0, 0x2a9, 0x1a3, 0xaa, 0xbac, 0xaa5, 0x9af, 0x8a6,
    0x7a6, 0x6af, 0x5a5, 0x4ac, 0xfaa, 0xea3, 0xda9, 0xca0,
    0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc, 0x1c5, 0x2cf, 0x3c6,
    0xcc6, 0xdcf, 0xec5, 0xfcc, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
    0x950, 0x859, 0xb53, 0xa5a, 0x15c, 0x55, 0x35f, 0x256,
    0xd56, 0xc5f, 0xf55, 0xe5c, 0x55a, 0x453, 0x759, 0x650,
    0xaf0, 0xbf9, 0x8f3, 0x9fa, 0x2fc, 0x3f5, 0xff, 0x1f6,
    0xef6, 0xfff, 0xcf5, 0xdfc, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
    0xb60, 0xa69, 0x963, 0x86a, 0x36c, 0x265, 0x16f, 0x66,
    0xf66, 0xe6f, 0xd65, 0xc6c, 0x76a, 0x663, 0x569, 0x460,
    0x460, 0x569, 0x663, 0x76a, 0xc6c, 0xd65, 0xe6f, 0xf66,
    0x66, 0x16f, 0x265, 0x36c, 0x86a, 0x963, 0xa69, 0xb60,
    0x5f0, 0x4f9, 0x7f3, 0x6fa, 0xdfc, 0xcf5, 0xfff, 0xef6,
    0x1f6, 0xff, 0x3f5, 0x2fc, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
    0x650, 0x759, 0x453, 0x55a, 0xe5c, 0xf55, 0xc5f, 0xd56,
    0x256, 0x35f, 0x55, 0x15c, 0xa5a, 0xb53, 0x859, 0x950,
    0x7c0, 0x6c9, 0x5c3, 0x4ca, 0xfcc, 0xec5, 0xdcf, 0xcc6,
    0x3c6, 0x2cf, 0x1c5, 0xcc, 0xbca, 0xac3, 0x9c9, 0x8c0,
    0xca0, 0xda9, 0xea3, 0xfaa, 0x4ac, 0x5a5, 0x6af, 0x7a6,
    0x8a6, 0x9af, 0xaa5, 0xbac, 0xaa, 0x1a3, 0x2a9, 0x3a0,
    0xd30, 0xc39, 0xf33, 0xe3a, 0x53c, 0x435, 0x73f, 0x636,
    0x936, 0x83f, 0xb35, 0xa3c, 0x13a, 0x33, 0x339, 0x230,
    0xe90, 0xf99, 0xc93, 0xd9a, 0x69c, 0x795, 0x49f, 0x596,
    0xa96, 0xb9f, 0x895, 0x99c, 0x29a, 0x393, 0x99, 0x190,
    0xf00, 0xe09, 0xd03, 0xc0a, 0x70c, 0x605, 0x50f, 0x406,
    0xb06, 0xa0f, 0x905, 0x80c, 0x30a, 0x203, 0x109, 0x0,
    ];

    // For each MC case, a list of triangles, specified as triples of edge indices, terminated by -1
    const TriangleTable = [
    [ -1 ],
    [ 3, 8, 0, -1 ],
    [ 1, 0, 9, -1 ],
    [ 9, 1, 8, 8, 1, 3, -1 ],
    [ 3, 2, 11, -1 ],
    [ 2, 11, 0, 0, 11, 8, -1 ],
    [ 1, 0, 9, 3, 2, 11, -1 ],
    [ 11, 1, 2, 11, 9, 1, 11, 8, 9, -1 ],
    [ 10, 2, 1, -1 ],
    [ 2, 1, 10, 0, 3, 8, -1 ],
    [ 0, 9, 2, 2, 9, 10, -1 ],
    [ 8, 2, 3, 8, 10, 2, 8, 9, 10, -1 ],
    [ 1, 10, 3, 3, 10, 11, -1 ],
    [ 10, 0, 1, 10, 8, 0, 10, 11, 8, -1 ],
    [ 9, 3, 0, 9, 11, 3, 9, 10, 11, -1 ],
    [ 9, 11, 8, 10, 11, 9, -1 ],
    [ 7, 4, 8, -1 ],
    [ 0, 3, 4, 4, 3, 7, -1 ],
    [ 0, 9, 1, 4, 8, 7, -1 ],
    [ 1, 4, 9, 1, 7, 4, 1, 3, 7, -1 ],
    [ 11, 3, 2, 8, 7, 4, -1 ],
    [ 4, 11, 7, 4, 2, 11, 4, 0, 2, -1 ],
    [ 3, 2, 11, 0, 9, 1, 4, 8, 7, -1 ],
    [ 1, 4, 9, 2, 4, 1, 7, 4, 2, 11, 7, 2, -1 ],
    [ 7, 4, 8, 1, 10, 2, -1 ],
    [ 7, 4, 3, 3, 4, 0, 10, 2, 1, -1 ],
    [ 10, 2, 9, 9, 2, 0, 7, 4, 8, -1 ],
    [ 7, 4, 9, 2, 7, 9, 2, 3, 7, 2, 9, 10, -1 ],
    [ 1, 10, 3, 3, 10, 11, 4, 8, 7, -1 ],
    [ 1, 4, 0, 11, 7, 4, 11, 4, 1, 10, 11, 1, -1 ],
    [ 8, 3, 0, 7, 4, 11, 4, 9, 11, 9, 10, 11, -1 ],
    [ 7, 4, 11, 4, 9, 11, 9, 10, 11, -1 ],
    [ 5, 9, 4, -1 ],
    [ 8, 0, 3, 9, 4, 5, -1 ],
    [ 1, 0, 5, 5, 0, 4, -1 ],
    [ 5, 8, 4, 5, 3, 8, 5, 1, 3, -1 ],
    [ 3, 2, 11, 5, 9, 4, -1 ],
    [ 2, 11, 0, 0, 11, 8, 5, 9, 4, -1 ],
    [ 4, 5, 0, 0, 5, 1, 11, 3, 2, -1 ],
    [ 2, 5, 1, 8, 4, 5, 8, 5, 2, 11, 8, 2, -1 ],
    [ 5, 9, 4, 1, 10, 2, -1 ],
    [ 0, 3, 8, 1, 10, 2, 5, 9, 4, -1 ],
    [ 2, 5, 10, 2, 4, 5, 2, 0, 4, -1 ],
    [ 2, 5, 10, 3, 5, 2, 4, 5, 3, 8, 4, 3, -1 ],
    [ 11, 3, 10, 10, 3, 1, 4, 5, 9, -1 ],
    [ 9, 0, 1, 4, 5, 8, 5, 10, 8, 10, 11, 8, -1 ],
    [ 4, 5, 10, 3, 4, 10, 3, 0, 4, 3, 10, 11, -1 ],
    [ 4, 5, 8, 5, 10, 8, 10, 11, 8, -1 ],
    [ 5, 9, 7, 7, 9, 8, -1 ],
    [ 3, 9, 0, 3, 5, 9, 3, 7, 5, -1 ],
    [ 7, 0, 8, 7, 1, 0, 7, 5, 1, -1 ],
    [ 1, 7, 5, 3, 7, 1, -1 ],
    [ 5, 9, 7, 7, 9, 8, 2, 11, 3, -1 ],
    [ 5, 9, 0, 11, 5, 0, 11, 7, 5, 11, 0, 2, -1 ],
    [ 3, 0, 8, 2, 11, 1, 11, 7, 1, 7, 5, 1, -1 ],
    [ 2, 11, 1, 11, 7, 1, 7, 5, 1, -1 ],
    [ 8, 7, 9, 9, 7, 5, 2, 1, 10, -1 ],
    [ 1, 9, 0, 10, 2, 5, 2, 3, 5, 3, 7, 5, -1 ],
    [ 8, 2, 0, 5, 10, 2, 5, 2, 8, 7, 5, 8, -1 ],
    [ 10, 2, 5, 2, 3, 5, 3, 7, 5, -1 ],
    [ 9, 8, 3, 1, 9, 3, 5, 11, 7, 5, 10, 11, -1 ],
    [ 5, 11, 7, 10, 11, 5, 1, 9, 0, -1 ],
    [ 11, 5, 10, 7, 5, 11, 8, 3, 0, -1 ],
    [ 11, 5, 10, 7, 5, 11, -1 ],
    [ 11, 6, 7, -1 ],
    [ 3, 8, 0, 7, 11, 6, -1 ],
    [ 1, 0, 9, 7, 11, 6, -1 ],
    [ 9, 1, 8, 8, 1, 3, 6, 7, 11, -1 ],
    [ 6, 7, 2, 2, 7, 3, -1 ],
    [ 0, 7, 8, 0, 6, 7, 0, 2, 6, -1 ],
    [ 6, 7, 2, 2, 7, 3, 9, 1, 0, -1 ],
    [ 6, 7, 8, 1, 6, 8, 1, 2, 6, 1, 8, 9, -1 ],
    [ 10, 2, 1, 11, 6, 7, -1 ],
    [ 2, 1, 10, 3, 8, 0, 7, 11, 6, -1 ],
    [ 0, 9, 2, 2, 9, 10, 7, 11, 6, -1 ],
    [ 11, 2, 3, 6, 7, 10, 7, 8, 10, 8, 9, 10, -1 ],
    [ 7, 10, 6, 7, 1, 10, 7, 3, 1, -1 ],
    [ 0, 7, 8, 1, 7, 0, 6, 7, 1, 10, 6, 1, -1 ],
    [ 6, 9, 10, 3, 0, 9, 3, 9, 6, 7, 3, 6, -1 ],
    [ 6, 7, 10, 7, 8, 10, 8, 9, 10, -1 ],
    [ 4, 8, 6, 6, 8, 11, -1 ],
    [ 6, 3, 11, 6, 0, 3, 6, 4, 0, -1 ],
    [ 11, 6, 8, 8, 6, 4, 1, 0, 9, -1 ],
    [ 11, 1, 3, 4, 9, 1, 4, 1, 11, 6, 4, 11, -1 ],
    [ 2, 8, 3, 2, 4, 8, 2, 6, 4, -1 ],
    [ 0, 6, 4, 2, 6, 0, -1 ],
    [ 0, 8, 3, 9, 1, 4, 1, 2, 4, 2, 6, 4, -1 ],
    [ 9, 1, 4, 1, 2, 4, 2, 6, 4, -1 ],
    [ 4, 8, 6, 6, 8, 11, 1, 10, 2, -1 ],
    [ 2, 3, 11, 1, 10, 0, 10, 6, 0, 6, 4, 0, -1 ],
    [ 2, 0, 8, 11, 2, 8, 10, 4, 9, 10, 6, 4, -1 ],
    [ 10, 4, 9, 6, 4, 10, 11, 2, 3, -1 ],
    [ 4, 8, 3, 10, 4, 3, 10, 6, 4, 10, 3, 1, -1 ],
    [ 1, 10, 0, 10, 6, 0, 6, 4, 0, -1 ],
    [ 4, 10, 6, 9, 10, 4, 0, 8, 3, -1 ],
    [ 10, 4, 9, 6, 4, 10, -1 ],
    [ 4, 5, 9, 6, 7, 11, -1 ],
    [ 7, 11, 6, 8, 0, 3, 9, 4, 5, -1 ],
    [ 1, 0, 5, 5, 0, 4, 11, 6, 7, -1 ],
    [ 7, 8, 4, 11, 6, 3, 6, 5, 3, 5, 1, 3, -1 ],
    [ 3, 2, 7, 7, 2, 6, 9, 4, 5, -1 ],
    [ 4, 7, 8, 5, 9, 6, 9, 0, 6, 0, 2, 6, -1 ],
    [ 0, 4, 7, 3, 0, 7, 1, 6, 5, 1, 2, 6, -1 ],
    [ 6, 1, 2, 5, 1, 6, 4, 7, 8, -1 ],
    [ 6, 7, 11, 5, 9, 4, 1, 10, 2, -1 ],
    [ 8, 4, 7, 11, 2, 3, 0, 1, 9, 6, 5, 10, -1 ],
    [ 6, 5, 10, 7, 11, 4, 11, 2, 4, 2, 0, 4, -1 ],
    [ 2, 3, 11, 8, 4, 7, 10, 6, 5, -1 ],
    [ 5, 10, 6, 9, 4, 1, 4, 7, 1, 7, 3, 1, -1 ],
    [ 7, 8, 4, 0, 1, 9, 6, 5, 10, -1 ],
    [ 4, 3, 0, 7, 3, 4, 6, 5, 10, -1 ],
    [ 8, 4, 7, 10, 6, 5, -1 ],
    [ 9, 6, 5, 9, 11, 6, 9, 8, 11, -1 ],
    [ 3, 9, 0, 11, 9, 3, 5, 9, 11, 6, 5, 11, -1 ],
    [ 11, 6, 5, 0, 11, 5, 0, 8, 11, 0, 5, 1, -1 ],
    [ 11, 6, 3, 6, 5, 3, 5, 1, 3, -1 ],
    [ 3, 9, 8, 6, 5, 9, 6, 9, 3, 2, 6, 3, -1 ],
    [ 5, 9, 6, 9, 0, 6, 0, 2, 6, -1 ],
    [ 1, 6, 5, 2, 6, 1, 3, 0, 8, -1 ],
    [ 6, 1, 2, 5, 1, 6, -1 ],
    [ 10, 6, 5, 2, 1, 11, 1, 9, 11, 9, 8, 11, -1 ],
    [ 6, 5, 10, 9, 0, 1, 11, 2, 3, -1 ],
    [ 11, 0, 8, 2, 0, 11, 10, 6, 5, -1 ],
    [ 5, 10, 6, 3, 11, 2, -1 ],
    [ 1, 8, 3, 9, 8, 1, 5, 10, 6, -1 ],
    [ 0, 1, 9, 6, 5, 10, -1 ],
    [ 0, 8, 3, 10, 6, 5, -1 ],
    [ 5, 10, 6, -1 ],
    [ 6, 10, 5, -1 ],
    [ 3, 8, 0, 5, 6, 10, -1 ],
    [ 9, 1, 0, 10, 5, 6, -1 ],
    [ 3, 8, 1, 1, 8, 9, 6, 10, 5, -1 ],
    [ 6, 10, 5, 2, 11, 3, -1 ],
    [ 8, 0, 11, 11, 0, 2, 5, 6, 10, -1 ],
    [ 10, 5, 6, 1, 0, 9, 3, 2, 11, -1 ],
    [ 10, 1, 2, 5, 6, 9, 6, 11, 9, 11, 8, 9, -1 ],
    [ 2, 1, 6, 6, 1, 5, -1 ],
    [ 5, 6, 1, 1, 6, 2, 8, 0, 3, -1 ],
    [ 6, 9, 5, 6, 0, 9, 6, 2, 0, -1 ],
    [ 3, 6, 2, 9, 5, 6, 9, 6, 3, 8, 9, 3, -1 ],
    [ 3, 6, 11, 3, 5, 6, 3, 1, 5, -1 ],
    [ 8, 0, 1, 6, 8, 1, 6, 11, 8, 6, 1, 5, -1 ],
    [ 9, 3, 0, 5, 3, 9, 11, 3, 5, 6, 11, 5, -1 ],
    [ 5, 6, 9, 6, 11, 9, 11, 8, 9, -1 ],
    [ 7, 4, 8, 5, 6, 10, -1 ],
    [ 0, 3, 4, 4, 3, 7, 10, 5, 6, -1 ],
    [ 4, 8, 7, 9, 1, 0, 10, 5, 6, -1 ],
    [ 5, 4, 9, 6, 10, 7, 10, 1, 7, 1, 3, 7, -1 ],
    [ 11, 3, 2, 7, 4, 8, 5, 6, 10, -1 ],
    [ 6, 11, 7, 10, 5, 2, 5, 4, 2, 4, 0, 2, -1 ],
    [ 4, 9, 5, 6, 11, 7, 8, 3, 0, 10, 1, 2, -1 ],
    [ 11, 7, 6, 4, 9, 5, 2, 10, 1, -1 ],
    [ 2, 1, 6, 6, 1, 5, 8, 7, 4, -1 ],
    [ 4, 0, 1, 5, 4, 1, 7, 2, 3, 7, 6, 2, -1 ],
    [ 4, 9, 5, 8, 7, 0, 7, 6, 0, 6, 2, 0, -1 ],
    [ 7, 2, 3, 6, 2, 7, 5, 4, 9, -1 ],
    [ 7, 6, 11, 4, 8, 5, 8, 3, 5, 3, 1, 5, -1 ],
    [ 5, 0, 1, 4, 0, 5, 7, 6, 11, -1 ],
    [ 6, 11, 7, 3, 0, 8, 5, 4, 9, -1 ],
    [ 9, 5, 4, 11, 7, 6, -1 ],
    [ 9, 4, 10, 10, 4, 6, -1 ],
    [ 6, 10, 4, 4, 10, 9, 3, 8, 0, -1 ],
    [ 0, 10, 1, 0, 6, 10, 0, 4, 6, -1 ],
    [ 6, 10, 1, 8, 6, 1, 8, 4, 6, 8, 1, 3, -1 ],
    [ 9, 4, 10, 10, 4, 6, 3, 2, 11, -1 ],
    [ 10, 9, 0, 2, 10, 0, 6, 8, 4, 6, 11, 8, -1 ],
    [ 2, 10, 1, 11, 3, 6, 3, 0, 6, 0, 4, 6, -1 ],
    [ 6, 8, 4, 11, 8, 6, 2, 10, 1, -1 ],
    [ 4, 1, 9, 4, 2, 1, 4, 6, 2, -1 ],
    [ 0, 1, 9, 3, 8, 2, 8, 4, 2, 4, 6, 2, -1 ],
    [ 4, 2, 0, 6, 2, 4, -1 ],
    [ 3, 8, 2, 8, 4, 2, 4, 6, 2, -1 ],
    [ 11, 4, 6, 1, 9, 4, 1, 4, 11, 3, 1, 11, -1 ],
    [ 8, 6, 11, 4, 6, 8, 9, 0, 1, -1 ],
    [ 11, 3, 6, 3, 0, 6, 0, 4, 6, -1 ],
    [ 6, 8, 4, 11, 8, 6, -1 ],
    [ 10, 7, 6, 10, 8, 7, 10, 9, 8, -1 ],
    [ 0, 10, 9, 7, 6, 10, 7, 10, 0, 3, 7, 0, -1 ],
    [ 0, 10, 1, 8, 10, 0, 6, 10, 8, 7, 6, 8, -1 ],
    [ 6, 10, 7, 10, 1, 7, 1, 3, 7, -1 ],
    [ 11, 7, 6, 3, 2, 8, 2, 10, 8, 10, 9, 8, -1 ],
    [ 2, 9, 0, 10, 9, 2, 6, 11, 7, -1 ],
    [ 10, 1, 2, 0, 8, 3, 6, 11, 7, -1 ],
    [ 1, 2, 10, 7, 6, 11, -1 ],
    [ 2, 1, 9, 7, 2, 9, 7, 6, 2, 7, 9, 8, -1 ],
    [ 2, 7, 6, 3, 7, 2, 0, 1, 9, -1 ],
    [ 8, 7, 0, 7, 6, 0, 6, 2, 0, -1 ],
    [ 2, 7, 6, 3, 7, 2, -1 ],
    [ 8, 1, 9, 3, 1, 8, 11, 7, 6, -1 ],
    [ 9, 0, 1, 6, 11, 7, -1 ],
    [ 0, 8, 3, 6, 11, 7, -1 ],
    [ 7, 6, 11, -1 ],
    [ 10, 5, 11, 11, 5, 7, -1 ],
    [ 10, 5, 11, 11, 5, 7, 0, 3, 8, -1 ],
    [ 7, 11, 5, 5, 11, 10, 0, 9, 1, -1 ],
    [ 8, 9, 5, 7, 8, 5, 3, 10, 1, 3, 11, 10, -1 ],
    [ 5, 2, 10, 5, 3, 2, 5, 7, 3, -1 ],
    [ 10, 0, 2, 7, 8, 0, 7, 0, 10, 5, 7, 10, -1 ],
    [ 1, 2, 10, 0, 9, 3, 9, 5, 3, 5, 7, 3, -1 ],
    [ 9, 7, 8, 5, 7, 9, 10, 1, 2, -1 ],
    [ 1, 11, 2, 1, 7, 11, 1, 5, 7, -1 ],
    [ 3, 11, 2, 8, 0, 7, 0, 1, 7, 1, 5, 7, -1 ],
    [ 0, 9, 5, 11, 0, 5, 11, 2, 0, 11, 5, 7, -1 ],
    [ 7, 9, 5, 8, 9, 7, 3, 11, 2, -1 ],
    [ 1, 7, 3, 5, 7, 1, -1 ],
    [ 8, 0, 7, 0, 1, 7, 1, 5, 7, -1 ],
    [ 0, 9, 3, 9, 5, 3, 5, 7, 3, -1 ],
    [ 7, 9, 5, 8, 9, 7, -1 ],
    [ 8, 5, 4, 8, 10, 5, 8, 11, 10, -1 ],
    [ 10, 5, 4, 3, 10, 4, 3, 11, 10, 3, 4, 0, -1 ],
    [ 9, 5, 4, 1, 0, 10, 0, 8, 10, 8, 11, 10, -1 ],
    [ 10, 3, 11, 1, 3, 10, 9, 5, 4, -1 ],
    [ 8, 5, 4, 3, 5, 8, 10, 5, 3, 2, 10, 3, -1 ],
    [ 10, 5, 2, 5, 4, 2, 4, 0, 2, -1 ],
    [ 8, 3, 0, 2, 10, 1, 4, 9, 5, -1 ],
    [ 4, 9, 5, 2, 10, 1, -1 ],
    [ 2, 8, 11, 5, 4, 8, 5, 8, 2, 1, 5, 2, -1 ],
    [ 0, 5, 4, 1, 5, 0, 2, 3, 11, -1 ],
    [ 0, 11, 2, 8, 11, 0, 4, 9, 5, -1 ],
    [ 11, 2, 3, 4, 9, 5, -1 ],
    [ 4, 8, 5, 8, 3, 5, 3, 1, 5, -1 ],
    [ 5, 0, 1, 4, 0, 5, -1 ],
    [ 3, 0, 8, 5, 4, 9, -1 ],
    [ 4, 9, 5, -1 ],
    [ 11, 4, 7, 11, 9, 4, 11, 10, 9, -1 ],
    [ 8, 4, 7, 0, 3, 9, 3, 11, 9, 11, 10, 9, -1 ],
    [ 7, 0, 4, 10, 1, 0, 10, 0, 7, 11, 10, 7, -1 ],
    [ 3, 10, 1, 11, 10, 3, 7, 8, 4, -1 ],
    [ 9, 4, 7, 2, 9, 7, 2, 10, 9, 2, 7, 3, -1 ],
    [ 9, 2, 10, 0, 2, 9, 8, 4, 7, -1 ],
    [ 3, 4, 7, 0, 4, 3, 1, 2, 10, -1 ],
    [ 8, 4, 7, 2, 10, 1, -1 ],
    [ 4, 1, 9, 7, 1, 4, 2, 1, 7, 11, 2, 7, -1 ],
    [ 11, 2, 3, 1, 9, 0, 7, 8, 4, -1 ],
    [ 7, 11, 4, 11, 2, 4, 2, 0, 4, -1 ],
    [ 2, 3, 11, 4, 7, 8, -1 ],
    [ 9, 4, 1, 4, 7, 1, 7, 3, 1, -1 ],
    [ 1, 9, 0, 7, 8, 4, -1 ],
    [ 4, 3, 0, 7, 3, 4, -1 ],
    [ 8, 4, 7, -1 ],
    [ 8, 10, 9, 11, 10, 8, -1 ],
    [ 0, 3, 9, 3, 11, 9, 11, 10, 9, -1 ],
    [ 1, 0, 10, 0, 8, 10, 8, 11, 10, -1 ],
    [ 3, 10, 1, 11, 10, 3, -1 ],
    [ 3, 2, 8, 2, 10, 8, 10, 9, 8, -1 ],
    [ 2, 9, 0, 10, 9, 2, -1 ],
    [ 10, 1, 2, 8, 3, 0, -1 ],
    [ 1, 2, 10, -1 ],
    [ 2, 1, 11, 1, 9, 11, 9, 8, 11, -1 ],
    [ 9, 0, 1, 11, 2, 3, -1 ],
    [ 0, 11, 2, 8, 11, 0, -1 ],
    [ 11, 2, 3, -1 ],
    [ 8, 1, 9, 3, 1, 8, -1 ],
    [ 9, 0, 1, -1 ],
    [ 0, 8, 3, -1 ],
    [ -1 ],
    ];