src/edu/berkeley/qfat/voxel/MarchingCubes.java

   1 package edu.berkeley.qfat.voxel;
   2 import edu.berkeley.qfat.*;
   3 import edu.berkeley.qfat.geom.*;
   4
   5 /////////////////////////////////////////////////////////////////////////////////////
   6 // Derived from:                                                                   //
   7 // http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/marchingsource.cpp    //
   8 // (which is public domain)                                                        //
   9 /////////////////////////////////////////////////////////////////////////////////////
  10 //
  11 // Marching Cubes Example Program
  12 // by Cory Bloyd (corysama@yahoo.com)
  13 //
  14 // A simple, portable and complete implementation of the Marching Cubes
  15 // and Marching Tetrahedrons algorithms in a single source file.
  16 // There are many ways that this code could be made faster, but the
  17 // intent is for the code to be easy to understand.
  18 //
  19 // For a description of the algorithm go to
  20 // http://astronomy.swin.edu.au/pbourke/modelling/polygonise/
  21 //
  22 // This code is public domain.
  23 //
  24 //////////////////////////////////////////////////////////////////////////////////////
  25
  26 public class MarchingCubes {
  27
  28     private static class GLvector {
  29         public double fX;
  30         public double fY;
  31         public double fZ;
  32         public String toString() {
  33             return "("+fX+","+fY+","+fZ+")";
  34         }
  35     };
  36
  37     /** march iterates over the entire dataset, calling vMarchCube on each cube */
  38     public static void march(VoxelData voxels, Mesh mesh) { march(voxels, 0, mesh); }
  39     public static void march(VoxelData voxels, double threshold, Mesh mesh) {
  40         int initialTriangles = mesh.numTriangles();
  41         double scaleX = (voxels.getMaxX() - voxels.getMinX()) / (double)voxels.getNumSamplesX();
  42         double scaleY = (voxels.getMaxY() - voxels.getMinY()) / (double)voxels.getNumSamplesY();
  43         double scaleZ = (voxels.getMaxZ() - voxels.getMinZ()) / (double)voxels.getNumSamplesZ();
  44         for(int iX = 0; iX < voxels.getNumSamplesX(); iX++) {
  45             System.out.print("\r");
  46             for(int i=0; i<78; i++) System.out.print(' ');
  47             System.out.print("\r");
  48             System.out.print(Math.ceil((iX/((double)voxels.getNumSamplesX()))*100) + "% marched, " +
  49                              (mesh.numTriangles()-initialTriangles) + " triangles");
  50             for(int iY = 0; iY < voxels.getNumSamplesY(); iY++)
  51                 for(int iZ = 0; iZ < voxels.getNumSamplesZ(); iZ++)
  52                     /*marchCubes*/marchTetrahedrons(voxels, mesh, threshold,
  53                                                     iX*scaleX + voxels.getMinX(),
  54                                                     iY*scaleY + voxels.getMinY(),
  55                                                     iZ*scaleZ + voxels.getMinZ(),
  56                                                     scaleX, scaleY, scaleZ);
  57         }
  58         System.out.print("\r");
  59         for(int i=0; i<78; i++) System.out.print(' ');
  60         System.out.print("\r");
  61         System.out.println("done marching.");
  62     }
  63
  64     /** performs the Marching Cubes algorithm on a single cube */
  65     static void marchCubes(VoxelData voxels, Mesh mesh, double threshold,
  66                            double fX, double fY, double fZ,
  67                            double scaleX, double scaleY, double scaleZ) {
  68         int iCorner, iVertex, iVertexTest, iEdge, iTriangle, iFlagIndex, iEdgeFlags;
  69         double fOffset;
  70         GLvector sColor;
  71         double afCubeValue[] = new double[8];
  72         GLvector asEdgeVertex[] = new GLvector[12];
  73         GLvector asEdgeNorm[] = new GLvector[12];
  74
  75         for(int i=0; i<asEdgeVertex.length; i++) asEdgeVertex[i] = new GLvector();
  76         for(int i=0; i<asEdgeNorm.length; i++) asEdgeNorm[i] = new GLvector();
  77
  78         // Make a local copy of the values at the cube's corners
  79         for(iVertex = 0; iVertex < 8; iVertex++)
  80             afCubeValue[iVertex] = voxels.getSample(new Point(fX + a2fVertexOffset[iVertex][0]*scaleX,
  81                                                                     fY + a2fVertexOffset[iVertex][1]*scaleY,
  82                                                                     fZ + a2fVertexOffset[iVertex][2]*scaleZ));
  83
  84         // Find which vertices are inside of the surface and which are outside
  85         iFlagIndex = 0;
  86         for(iVertexTest = 0; iVertexTest < 8; iVertexTest++)
  87             if (afCubeValue[iVertexTest] >= threshold)
  88                 iFlagIndex |= 1<<iVertexTest;
  89
  90         // Find which edges are intersected by the surface
  91         iEdgeFlags = aiCubeEdgeFlags[iFlagIndex];
  92
  93         // If the cube is entirely inside or outside of the surface, then there will be no intersections
  94         if (iEdgeFlags == 0) return;
  95
  96         // Find the point of intersection of the surface with each edge
  97         // Then find the normal to the surface at those points
  98         for(iEdge = 0; iEdge < 12; iEdge++) {
  99             // If there is an intersection on this edge
 100             if ((iEdgeFlags & (1<<iEdge))==0) continue;
 101             fOffset = fGetOffset(afCubeValue[ a2iEdgeConnection[iEdge][0] ],
 102                                  afCubeValue[ a2iEdgeConnection[iEdge][1] ],
 103                                  threshold,
 104                                  Math.min(Math.min(scaleX, scaleY), scaleZ) * 0.1);
 105
 106             asEdgeVertex[iEdge].fX = fX + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][0]  +  fOffset * a2fEdgeDirection[iEdge][0]) * scaleX;
 107             asEdgeVertex[iEdge].fY = fY + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][1]  +  fOffset * a2fEdgeDirection[iEdge][1]) * scaleY;
 108             asEdgeVertex[iEdge].fZ = fZ + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][2]  +  fOffset * a2fEdgeDirection[iEdge][2]) * scaleZ;
 109
 110             vGetNormal(voxels, asEdgeNorm[iEdge], asEdgeVertex[iEdge].fX, asEdgeVertex[iEdge].fY, asEdgeVertex[iEdge].fZ);
 111         }
 112
 113         System.out.println();
 114
 115         // Draw the triangles that were found.  There can be up to five per cube
 116         for(iTriangle = 0; iTriangle < 5; iTriangle++) {
 117             if(a2iTriangleConnectionTable[iFlagIndex][3*iTriangle] < 0)
 118                 break;
 119
 120             Point[] points = new Point[3];
 121             Vec norm = new Vec(0,0,0);
 122             for(iCorner = 0; iCorner < 3; iCorner++) {
 123                 iVertex = a2iTriangleConnectionTable[iFlagIndex][3*iTriangle+iCorner];
 124                 points[iCorner] = new Point(asEdgeVertex[iVertex].fX, asEdgeVertex[iVertex].fY, asEdgeVertex[iVertex].fZ);
 125
 126                 // questionable, but we do it anyways
 127                 norm = norm.plus(new Vec(asEdgeNorm[iVertex].fX,   asEdgeNorm[iVertex].fY,   asEdgeNorm[iVertex].fZ));
 128             }
 129
 130             // Eliminate triangles with "length-zero" sides.
 131             // Unfortunately this puts holes in the mesh.
 132             if (points[0].equals(points[1]) ||
 133                 points[0].equals(points[2]) ||
 134                 points[1].equals(points[2]))
 135                 continue;
 136
 137             System.out.println("creating triangle: " + points[0] + " " + points[1] + " " + points[2]);
 138             try {
 139                 Mesh.T t = mesh.newT(points[0], points[1], points[2], norm.norm().times(-1));
 140                 System.out.println("  created " + t);
 141             } catch (Throwable t) { }
 142         }
 143     }
 144
 145     /**
 146      *  marchTetrahedron performs the Marching Tetrahedrons algorithm
 147      *  on a single tetrahedron
 148      */
 149     static void marchTetrahedron(VoxelData voxels, Mesh mesh, double threshold,
 150                                  GLvector[] pasTetrahedronPosition,
 151                                  float[] pafTetrahedronValue,
 152                                  double scaleX, double scaleY, double scaleZ) {
 153
 154         int iEdge, iVert0, iVert1, iEdgeFlags, iTriangle, iCorner, iVertex, iFlagIndex = 0;
 155         double fOffset, fInvOffset, fValue = 0.0;
 156         GLvector[] asEdgeVertex = new GLvector[6];
 157         GLvector[] asEdgeNorm = new GLvector[6];
 158         GLvector sColor = new GLvector();
 159         for(int i=0; i<asEdgeVertex.length; i++) asEdgeVertex[i] = new GLvector();
 160         for(int i=0; i<asEdgeNorm.length; i++) asEdgeNorm[i] = new GLvector();
 161
 162         // Find which vertices are inside of the surface and which are outside
 163         for(iVertex = 0; iVertex < 4; iVertex++)
 164             if(pafTetrahedronValue[iVertex] <= threshold)
 165                 iFlagIndex |= 1<<iVertex;
 166
 167         // Find which edges are intersected by the surface
 168         iEdgeFlags = aiTetrahedronEdgeFlags[iFlagIndex];
 169
 170         // If the tetrahedron is entirely inside or outside of the surface, then there will be no intersections
 171         if(iEdgeFlags == 0) return;
 172
 173         // Find the point of intersection of the surface with each edge
 174         // Then find the normal to the surface at those points
 175         for(iEdge = 0; iEdge < 6; iEdge++) {
 176             // if there is an intersection on this edge
 177             if( (iEdgeFlags & (1<<iEdge))==0 ) continue;
 178
 179             iVert0 = a2iTetrahedronEdgeConnection[iEdge][0];
 180             iVert1 = a2iTetrahedronEdgeConnection[iEdge][1];
 181             fOffset = fGetOffset(pafTetrahedronValue[iVert0], pafTetrahedronValue[iVert1], threshold,
 182                                  Math.min(Math.min(scaleX, scaleY), scaleZ) * 0.1);
 183             fInvOffset = 1.0f - fOffset;
 184
 185             asEdgeVertex[iEdge].fX = fInvOffset*pasTetrahedronPosition[iVert0].fX  +  fOffset*pasTetrahedronPosition[iVert1].fX;
 186             asEdgeVertex[iEdge].fY = fInvOffset*pasTetrahedronPosition[iVert0].fY  +  fOffset*pasTetrahedronPosition[iVert1].fY;
 187             asEdgeVertex[iEdge].fZ = fInvOffset*pasTetrahedronPosition[iVert0].fZ  +  fOffset*pasTetrahedronPosition[iVert1].fZ;
 188
 189             vGetNormal(voxels, asEdgeNorm[iEdge], asEdgeVertex[iEdge].fX, asEdgeVertex[iEdge].fY, asEdgeVertex[iEdge].fZ);
 190         }
 191
 192         // Draw the triangles that were found.  There can be up to 2 per tetrahedron
 193         for(iTriangle = 0; iTriangle < 2; iTriangle++) {
 194             if(a2iTetrahedronTriangles[iFlagIndex][3*iTriangle] < 0) break;
 195
 196             Point[] points = new Point[3];
 197             Vec norm = new Vec(0,0,0);
 198             for(iCorner = 0; iCorner < 3; iCorner++) {
 199                 iVertex = a2iTetrahedronTriangles[iFlagIndex][3*iTriangle+iCorner];
 200                 points[iCorner] = new Point(asEdgeVertex[iVertex].fX, asEdgeVertex[iVertex].fY, asEdgeVertex[iVertex].fZ);
 201                 // questionable, but we do it anyways
 202                 norm = norm.plus(new Vec(asEdgeNorm[iVertex].fX,   asEdgeNorm[iVertex].fY,   asEdgeNorm[iVertex].fZ));
 203             }
 204             // Eliminate triangles with "length-zero" sides.
 205             // Unfortunately this puts holes in the mesh.
 206             if (points[0].equals(points[1]) ||
 207                 points[0].equals(points[2]) ||
 208                 points[1].equals(points[2]))
 209                 continue;
 210             System.out.println("creating triangle: " + points[0] + " " + points[1] + " " + points[2]);
 211             Mesh.T t = mesh.newT(points[0], points[1], points[2], norm.norm().times(-1));
 212             System.out.println("  created " + t);
 213         }
 214     }
 215
 216     /**
 217      *  marchTetrahedrons performs the Marching Tetrahedrons algorithm on a
 218      *  single cube by making six calls to marchTetrahedron
 219      */
 220     static void marchTetrahedrons(VoxelData voxels, Mesh mesh, double threshold,
 221                                   double fX, double fY, double fZ,
 222                                   double scaleX, double scaleY, double scaleZ) {
 223         int iVertex, iTetrahedron, iVertexInACube;
 224         GLvector[] asCubePosition = new GLvector[8];
 225         float[]  afCubeValue = new float[8];
 226         GLvector[] asTetrahedronPosition = new GLvector[8];
 227         float[]  afTetrahedronValue = new float[4];
 228
 229         for(int i=0; i<asCubePosition.length; i++) asCubePosition[i] = new GLvector();
 230         for(int i=0; i<asTetrahedronPosition.length; i++) asTetrahedronPosition[i] = new GLvector();
 231
 232         // Make a local copy of the cube's corner positions
 233         for(iVertex = 0; iVertex < 8; iVertex++) {
 234             asCubePosition[iVertex].fX = fX + a2fVertexOffset[iVertex][0]*scaleX;
 235             asCubePosition[iVertex].fY = fY + a2fVertexOffset[iVertex][1]*scaleY;
 236             asCubePosition[iVertex].fZ = fZ + a2fVertexOffset[iVertex][2]*scaleZ;
 237         }
 238
 239         // Make a local copy of the cube's corner values
 240         for(iVertex = 0; iVertex < 8; iVertex++)
 241             afCubeValue[iVertex] =
 242                 voxels.getSample(new Point(asCubePosition[iVertex].fX,
 243                                            asCubePosition[iVertex].fY,
 244                                            asCubePosition[iVertex].fZ));
 245
 246         for(iTetrahedron = 0; iTetrahedron < 6; iTetrahedron++) {
 247             for(iVertex = 0; iVertex < 4; iVertex++) {
 248                 iVertexInACube = a2iTetrahedronsInACube[iTetrahedron][iVertex];
 249                 asTetrahedronPosition[iVertex].fX = asCubePosition[iVertexInACube].fX;
 250                 asTetrahedronPosition[iVertex].fY = asCubePosition[iVertexInACube].fY;
 251                 asTetrahedronPosition[iVertex].fZ = asCubePosition[iVertexInACube].fZ;
 252                 afTetrahedronValue[iVertex] = afCubeValue[iVertexInACube];
 253             }
 254             marchTetrahedron(voxels, mesh, threshold, asTetrahedronPosition, afTetrahedronValue, scaleX, scaleY, scaleZ);
 255         }
 256     }
 257
 258     /**
 259      *  vGetNormal() finds the gradient of the scalar field at a point
 260      *  This gradient can be used as a very accurate vertx normal for
 261      *  lighting calculations
 262      */
 263     static void vGetNormal(VoxelData voxels, GLvector rfNormal, double fX, double fY, double fZ) {
 264         rfNormal.fX =
 265             voxels.getSample(new Point(fX-0.01, fY, fZ)) -
 266             voxels.getSample(new Point(fX+0.01, fY, fZ));
 267         rfNormal.fY =
 268             voxels.getSample(new Point(fX, fY-0.01, fZ)) -
 269             voxels.getSample(new Point(fX, fY+0.01, fZ));
 270         rfNormal.fZ =
 271             voxels.getSample(new Point(fX, fY, fZ-0.01)) -
 272             voxels.getSample(new Point(fX, fY, fZ+0.01));
 273         vNormalizeVector(rfNormal, rfNormal);
 274     }
 275
 276     static void vNormalizeVector(GLvector rfVectorResult, GLvector rfVectorSource) {
 277         double fOldLength;
 278         double fScale;
 279
 280         fOldLength = Math.sqrt( (rfVectorSource.fX * rfVectorSource.fX) +
 281                                 (rfVectorSource.fY * rfVectorSource.fY) +
 282                                 (rfVectorSource.fZ * rfVectorSource.fZ) );
 283
 284         if(fOldLength == 0.0) {
 285             rfVectorResult.fX = rfVectorSource.fX;
 286             rfVectorResult.fY = rfVectorSource.fY;
 287             rfVectorResult.fZ = rfVectorSource.fZ;
 288         } else {
 289             fScale = 1.0/fOldLength;
 290             rfVectorResult.fX = rfVectorSource.fX*fScale;
 291             rfVectorResult.fY = rfVectorSource.fY*fScale;
 292             rfVectorResult.fZ = rfVectorSource.fZ*fScale;
 293         }
 294     }
 295
 296     // fGetOffset finds the approximate point of intersection of the surface
 297     // between two points with the values fValue1 and fValue2
 298     static double fGetOffset(double fValue1, double fValue2, double fValueDesired, double EPSILON) {
 299         double fDelta = fValue2 - fValue1;
 300         if(fDelta == 0.0) return 0.5;
 301
 302         // the following two lines are a hack; they "snap" the
 303         // estimate to one grid point or the other if the distance is
 304         // less than some EPSILON.  This ensures that the resulting
 305         // mesh is watertight and meets the requirements of Mesh.java
 306         if (Math.abs(fValueDesired-fValue1) < EPSILON) return 0;
 307         if (Math.abs(fValueDesired-fValue2) < EPSILON) return 1;
 308
 309         return (fValueDesired - fValue1)/fDelta;
 310     }
 311
 312     ////////////////////////////////////////////////////////////////////////////////////////
 313     // Tables //////////////////////////////////////////////////////////////////////////////
 314
 315     // These tables are used so that everything can be done in little
 316     // loops that you can look at all at once rather than in pages and
 317     // pages of unrolled code.
 318
 319     // a2fVertexOffset lists the positions, relative to vertex0, of
 320     // each of the 8 vertices of a cube
 321     static final double a2fVertexOffset[][] = {
 322         {0.0, 0.0, 0.0},{1.0, 0.0, 0.0},{1.0, 1.0, 0.0},{0.0, 1.0, 0.0},
 323         {0.0, 0.0, 1.0},{1.0, 0.0, 1.0},{1.0, 1.0, 1.0},{0.0, 1.0, 1.0}
 324     };
 325
 326     //a2iEdgeConnection lists the index of the endpoint vertices for each of the 12 edges of the cube
 327     static final int a2iEdgeConnection[][] = {
 328         {0,1}, {1,2}, {2,3}, {3,0},
 329         {4,5}, {5,6}, {6,7}, {7,4},
 330         {0,4}, {1,5}, {2,6}, {3,7}
 331     };
 332
 333     //a2fEdgeDirection lists the direction vector (vertex1-vertex0) for each edge in the cube
 334     static final double a2fEdgeDirection[][] = {
 335         {1.0, 0.0, 0.0},{0.0, 1.0, 0.0},{-1.0, 0.0, 0.0},{0.0, -1.0, 0.0},
 336         {1.0, 0.0, 0.0},{0.0, 1.0, 0.0},{-1.0, 0.0, 0.0},{0.0, -1.0, 0.0},
 337         {0.0, 0.0, 1.0},{0.0, 0.0, 1.0},{ 0.0, 0.0, 1.0},{0.0,  0.0, 1.0}
 338     };
 339
 340     // a2iTetrahedronEdgeConnection lists the index of the endpoint
 341     // vertices for each of the 6 edges of the tetrahedron
 342     static final int a2iTetrahedronEdgeConnection[][] = {
 343         {0,1},  {1,2},  {2,0},  {0,3},  {1,3},  {2,3}
 344     };
 345
 346     // a2iTetrahedronEdgeConnection lists the index of verticies from a cube
 347     // that made up each of the six tetrahedrons within the cube
 348     static final int a2iTetrahedronsInACube[][] = {
 349         {0,5,1,6},
 350         {0,1,2,6},
 351         {0,2,3,6},
 352         {0,3,7,6},
 353         {0,7,4,6},
 354         {0,4,5,6},
 355     };
 356
 357
 358     // For any edge, if one vertex is inside of the surface and the
 359     //  other is outside of the surface then the edge intersects the
 360     //  surface For each of the 4 vertices of the tetrahedron can be
 361     //  two possible states : either inside or outside of the surface
 362     //  For any tetrahedron the are 2^4=16 possible sets of vertex
 363     //  states This table lists the edges intersected by the surface
 364     //  for all 16 possible vertex states There are 6 edges.  For each
 365     //  entry in the table, if edge #n is intersected, then bit #n is
 366     //  set to 1
 367
 368     static int aiTetrahedronEdgeFlags[] = {
 369         0x00, 0x0d, 0x13, 0x1e, 0x26, 0x2b, 0x35, 0x38,
 370         0x38, 0x35, 0x2b, 0x26, 0x1e, 0x13, 0x0d, 0x00,
 371     };
 372
 373
 374     // For each of the possible vertex states listed in
 375     // aiTetrahedronEdgeFlags there is a specific triangulation of the
 376     // edge intersection points.  a2iTetrahedronTriangles lists all of
 377     // them in the form of 0-2 edge triples with the list terminated
 378     // by the invalid value -1.
 379     //
 380     // I generated this table by hand
 381
 382     static int a2iTetrahedronTriangles[][] = {
 383         {-1, -1, -1, -1, -1, -1, -1},
 384         { 0,  3,  2, -1, -1, -1, -1},
 385         { 0,  1,  4, -1, -1, -1, -1},
 386         { 1,  4,  2,  2,  4,  3, -1},
 387
 388         { 1,  2,  5, -1, -1, -1, -1},
 389         { 0,  3,  5,  0,  5,  1, -1},
 390         { 0,  2,  5,  0,  5,  4, -1},
 391         { 5,  4,  3, -1, -1, -1, -1},
 392
 393         { 3,  4,  5, -1, -1, -1, -1},
 394         { 4,  5,  0,  5,  2,  0, -1},
 395         { 1,  5,  0,  5,  3,  0, -1},
 396         { 5,  2,  1, -1, -1, -1, -1},
 397
 398         { 3,  4,  2,  2,  4,  1, -1},
 399         { 4,  1,  0, -1, -1, -1, -1},
 400         { 2,  3,  0, -1, -1, -1, -1},
 401         {-1, -1, -1, -1, -1, -1, -1},
 402     };
 403
 404     // For any edge, if one vertex is inside of the surface and the
 405     //  other is outside of the surface then the edge intersects the
 406     //  surface For each of the 8 vertices of the cube can be two
 407     //  possible states : either inside or outside of the surface For
 408     //  any cube the are 2^8=256 possible sets of vertex states This
 409     //  table lists the edges intersected by the surface for all 256
 410     //  possible vertex states There are 12 edges.  For each entry in
 411     //  the table, if edge #n is intersected, then bit #n is set to 1
 412
 413     static final int aiCubeEdgeFlags[] = {
 414         0x000, 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,
 415         0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,
 416         0x190, 0x099, 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,
 417         0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,
 418         0x230, 0x339, 0x033, 0x13a, 0x636, 0x73f, 0x435, 0x53c,
 419         0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,
 420         0x3a0, 0x2a9, 0x1a3, 0x0aa, 0x7a6, 0x6af, 0x5a5, 0x4ac,
 421         0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,
 422         0x460, 0x569, 0x663, 0x76a, 0x066, 0x16f, 0x265, 0x36c,
 423         0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
 424         0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0x0ff, 0x3f5, 0x2fc,
 425         0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
 426         0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x055, 0x15c,
 427         0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,
 428         0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0x0cc,
 429         0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,
 430         0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,
 431         0x0cc, 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
 432         0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,
 433         0x15c, 0x055, 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
 434         0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,
 435         0x2fc, 0x3f5, 0x0ff, 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
 436         0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c,
 437         0x36c, 0x265, 0x16f, 0x066, 0x76a, 0x663, 0x569, 0x460,
 438         0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,
 439         0x4ac, 0x5a5, 0x6af, 0x7a6, 0x0aa, 0x1a3, 0x2a9, 0x3a0,
 440         0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,
 441         0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x033, 0x339, 0x230,
 442         0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,
 443         0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x099, 0x190,
 444         0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,
 445         0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x000
 446     };
 447
 448     //  For each of the possible vertex states listed in
 449     //  aiCubeEdgeFlags there is a specific triangulation of the edge
 450     //  intersection points.  a2iTriangleConnectionTable lists all of
 451     //  them in the form of 0-5 edge triples with the list terminated
 452     //  by the invalid value -1.  For example:
 453     //  a2iTriangleConnectionTable[3] list the 2 triangles formed when
 454     //  corner[0] and corner[1] are inside of the surface, but the
 455     //  rest of the cube is not.
 456     //
 457     //  I found this table in an example program someone wrote long
 458     //  ago.  It was probably generated by hand
 459
 460     static final int a2iTriangleConnectionTable[][] = {
 461         {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 462         {0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 463         {0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 464         {1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 465         {1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 466         {0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 467         {9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 468         {2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1},
 469         {3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 470         {0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 471         {1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 472         {1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1},
 473         {3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 474         {0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1},
 475         {3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1},
 476         {9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 477         {4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 478         {4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 479         {0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 480         {4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1},
 481         {1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 482         {3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1},
 483         {9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
 484         {2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1},
 485         {8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 486         {11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1},
 487         {9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
 488         {4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1},
 489         {3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1},
 490         {1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1},
 491         {4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1},
 492         {4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1},
 493         {9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 494         {9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 495         {0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 496         {8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1},
 497         {1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 498         {3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
 499         {5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1},
 500         {2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1},
 501         {9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 502         {0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
 503         {0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
 504         {2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1},
 505         {10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1},
 506         {4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1},
 507         {5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1},
 508         {5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1},
 509         {9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 510         {9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1},
 511         {0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1},
 512         {1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 513         {9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1},
 514         {10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1},
 515         {8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1},
 516         {2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1},
 517         {7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1},
 518         {9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1},
 519         {2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1},
 520         {11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1},
 521         {9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1},
 522         {5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1},
 523         {11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1},
 524         {11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 525         {10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 526         {0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 527         {9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 528         {1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
 529         {1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 530         {1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1},
 531         {9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1},
 532         {5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1},
 533         {2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 534         {11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
 535         {0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
 536         {5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1},
 537         {6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1},
 538         {0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1},
 539         {3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1},
 540         {6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1},
 541         {5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 542         {4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1},
 543         {1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
 544         {10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1},
 545         {6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1},
 546         {1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1},
 547         {8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1},
 548         {7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1},
 549         {3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
 550         {5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1},
 551         {0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1},
 552         {9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1},
 553         {8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1},
 554         {5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1},
 555         {0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1},
 556         {6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1},
 557         {10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 558         {4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1},
 559         {10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1},
 560         {8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1},
 561         {1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1},
 562         {3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1},
 563         {0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 564         {8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1},
 565         {10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1},
 566         {0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1},
 567         {3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1},
 568         {6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1},
 569         {9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1},
 570         {8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1},
 571         {3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1},
 572         {6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 573         {7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1},
 574         {0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1},
 575         {10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1},
 576         {10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1},
 577         {1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1},
 578         {2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1},
 579         {7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1},
 580         {7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 581         {2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1},
 582         {2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1},
 583         {1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1},
 584         {11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1},
 585         {8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1},
 586         {0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 587         {7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1},
 588         {7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 589         {7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 590         {3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 591         {0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 592         {8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
 593         {10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 594         {1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
 595         {2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
 596         {6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1},
 597         {7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 598         {7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1},
 599         {2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1},
 600         {1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1},
 601         {10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1},
 602         {10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1},
 603         {0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1},
 604         {7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1},
 605         {6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 606         {3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1},
 607         {8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1},
 608         {9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1},
 609         {6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1},
 610         {1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1},
 611         {4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1},
 612         {10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1},
 613         {8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1},
 614         {0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 615         {1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1},
 616         {1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1},
 617         {8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1},
 618         {10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1},
 619         {4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1},
 620         {10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 621         {4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 622         {0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
 623         {5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
 624         {11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1},
 625         {9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
 626         {6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1},
 627         {7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1},
 628         {3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1},
 629         {7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1},
 630         {9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1},
 631         {3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1},
 632         {6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1},
 633         {9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1},
 634         {1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1},
 635         {4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1},
 636         {7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1},
 637         {6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1},
 638         {3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1},
 639         {0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1},
 640         {6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1},
 641         {1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1},
 642         {0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1},
 643         {11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1},
 644         {6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1},
 645         {5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1},
 646         {9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1},
 647         {1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1},
 648         {1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 649         {1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1},
 650         {10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1},
 651         {0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 652         {10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 653         {11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 654         {11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1},
 655         {5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1},
 656         {10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1},
 657         {11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1},
 658         {0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1},
 659         {9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1},
 660         {7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1},
 661         {2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1},
 662         {8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1},
 663         {9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1},
 664         {9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1},
 665         {1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 666         {0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1},
 667         {9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1},
 668         {9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 669         {5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1},
 670         {5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1},
 671         {0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1},
 672         {10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1},
 673         {2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1},
 674         {0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1},
 675         {0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1},
 676         {9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 677         {2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1},
 678         {5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1},
 679         {3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1},
 680         {5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1},
 681         {8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1},
 682         {0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 683         {8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1},
 684         {9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 685         {4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1},
 686         {0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1},
 687         {1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1},
 688         {3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1},
 689         {4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1},
 690         {9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1},
 691         {11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1},
 692         {11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1},
 693         {2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1},
 694         {9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1},
 695         {3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1},
 696         {1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 697         {4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1},
 698         {4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1},
 699         {4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 700         {4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 701         {9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 702         {3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1},
 703         {0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1},
 704         {3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 705         {1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1},
 706         {3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1},
 707         {0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 708         {3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 709         {2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1},
 710         {9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 711         {2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1},
 712         {1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 713         {1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 714         {0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 715         {0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 716         {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
 717     };
 718
 719 }