1 package edu.berkeley.qfat.voxel;
2 import edu.berkeley.qfat.*;
3 import edu.berkeley.qfat.geom.*;
5 /////////////////////////////////////////////////////////////////////////////////////
7 // http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/marchingsource.cpp //
8 // (which is public domain) //
9 /////////////////////////////////////////////////////////////////////////////////////
11 // Marching Cubes Example Program
12 // by Cory Bloyd (corysama@yahoo.com)
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.
19 // For a description of the algorithm go to
20 // http://astronomy.swin.edu.au/pbourke/modelling/polygonise/
22 // This code is public domain.
24 //////////////////////////////////////////////////////////////////////////////////////
26 public class MarchingCubes {
28 private static class GLvector {
32 public String toString() {
33 return "("+fX+","+fY+","+fZ+")";
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);
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.");
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;
71 double afCubeValue[] = new double[8];
72 GLvector asEdgeVertex[] = new GLvector[12];
73 GLvector asEdgeNorm[] = new GLvector[12];
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();
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));
84 // Find which vertices are inside of the surface and which are outside
86 for(iVertexTest = 0; iVertexTest < 8; iVertexTest++)
87 if (afCubeValue[iVertexTest] >= threshold)
88 iFlagIndex |= 1<<iVertexTest;
90 // Find which edges are intersected by the surface
91 iEdgeFlags = aiCubeEdgeFlags[iFlagIndex];
93 // If the cube is entirely inside or outside of the surface, then there will be no intersections
94 if (iEdgeFlags == 0) return;
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] ],
104 Math.min(Math.min(scaleX, scaleY), scaleZ) * 0.1);
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;
110 vGetNormal(voxels, asEdgeNorm[iEdge], asEdgeVertex[iEdge].fX, asEdgeVertex[iEdge].fY, asEdgeVertex[iEdge].fZ);
113 System.out.println();
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)
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);
126 // questionable, but we do it anyways
127 norm = norm.plus(new Vec(asEdgeNorm[iVertex].fX, asEdgeNorm[iVertex].fY, asEdgeNorm[iVertex].fZ));
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]))
137 System.out.println("creating triangle: " + points[0] + " " + points[1] + " " + points[2]);
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) { }
146 * marchTetrahedron performs the Marching Tetrahedrons algorithm
147 * on a single tetrahedron
149 static void marchTetrahedron(VoxelData voxels, Mesh mesh, double threshold,
150 GLvector[] pasTetrahedronPosition,
151 float[] pafTetrahedronValue,
152 double scaleX, double scaleY, double scaleZ) {
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();
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;
167 // Find which edges are intersected by the surface
168 iEdgeFlags = aiTetrahedronEdgeFlags[iFlagIndex];
170 // If the tetrahedron is entirely inside or outside of the surface, then there will be no intersections
171 if(iEdgeFlags == 0) return;
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;
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;
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;
189 vGetNormal(voxels, asEdgeNorm[iEdge], asEdgeVertex[iEdge].fX, asEdgeVertex[iEdge].fY, asEdgeVertex[iEdge].fZ);
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;
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));
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]))
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);
217 * marchTetrahedrons performs the Marching Tetrahedrons algorithm on a
218 * single cube by making six calls to marchTetrahedron
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];
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();
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;
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));
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];
254 marchTetrahedron(voxels, mesh, threshold, asTetrahedronPosition, afTetrahedronValue, scaleX, scaleY, scaleZ);
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
263 static void vGetNormal(VoxelData voxels, GLvector rfNormal, double fX, double fY, double fZ) {
265 voxels.getSample(new Point(fX-0.01, fY, fZ)) -
266 voxels.getSample(new Point(fX+0.01, fY, fZ));
268 voxels.getSample(new Point(fX, fY-0.01, fZ)) -
269 voxels.getSample(new Point(fX, fY+0.01, 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);
276 static void vNormalizeVector(GLvector rfVectorResult, GLvector rfVectorSource) {
280 fOldLength = Math.sqrt( (rfVectorSource.fX * rfVectorSource.fX) +
281 (rfVectorSource.fY * rfVectorSource.fY) +
282 (rfVectorSource.fZ * rfVectorSource.fZ) );
284 if(fOldLength == 0.0) {
285 rfVectorResult.fX = rfVectorSource.fX;
286 rfVectorResult.fY = rfVectorSource.fY;
287 rfVectorResult.fZ = rfVectorSource.fZ;
289 fScale = 1.0/fOldLength;
290 rfVectorResult.fX = rfVectorSource.fX*fScale;
291 rfVectorResult.fY = rfVectorSource.fY*fScale;
292 rfVectorResult.fZ = rfVectorSource.fZ*fScale;
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;
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;
309 return (fValueDesired - fValue1)/fDelta;
312 ////////////////////////////////////////////////////////////////////////////////////////
313 // Tables //////////////////////////////////////////////////////////////////////////////
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.
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}
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}
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}
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}
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[][] = {
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
368 static int aiTetrahedronEdgeFlags[] = {
369 0x00, 0x0d, 0x13, 0x1e, 0x26, 0x2b, 0x35, 0x38,
370 0x38, 0x35, 0x2b, 0x26, 0x1e, 0x13, 0x0d, 0x00,
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.
380 // I generated this table by hand
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},
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},
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},
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},
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
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
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.
457 // I found this table in an example program someone wrote long
458 // ago. It was probably generated by hand
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}