1 /*
2  * For any voxel edge, if one end is inside the surface and the other is
3  * outside then the edge intersects the surface.
4  * Each of the 8 vertices of a voxel cube can be either inside or outside
5  * the volume defined by an isosurface, so there are 2^8=256 possible sets
6  * of vertex states.
7  * The cube_edge_flags table lists the edges intersected by the surface
8  * for each of these 256 vertex states.  For each entry in the table,
9  * if edge #n is intersected then bit #n is set to 1.
10  * There are 12 edges, so at most 12 bits are set.
11  */
12 
13 /* The positions relative to grid point [i,j,k] of the 8 vertices of a cube.
14  * This ordering is implicit in the tables below.
15  */
16 static const int vertex_offset[8][3] =
17 {
18         {0, 0, 0}, {1, 0, 0}, {1, 1, 0}, {0, 1, 0},
19         {0, 0, 1}, {1, 0, 1}, {1, 1, 1}, {0, 1, 1}
20 };
21 
22 /* EAM:  I used "static const short" for these but uint16_t might be safer */
23 
24 static const short cube_edge_flags[256]=
25 {
26         0x000, 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c, 0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,
27         0x190, 0x099, 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c, 0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,
28         0x230, 0x339, 0x033, 0x13a, 0x636, 0x73f, 0x435, 0x53c, 0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,
29         0x3a0, 0x2a9, 0x1a3, 0x0aa, 0x7a6, 0x6af, 0x5a5, 0x4ac, 0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,
30         0x460, 0x569, 0x663, 0x76a, 0x066, 0x16f, 0x265, 0x36c, 0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
31         0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0x0ff, 0x3f5, 0x2fc, 0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
32         0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x055, 0x15c, 0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,
33         0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0x0cc, 0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,
34         0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc, 0x0cc, 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
35         0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c, 0x15c, 0x055, 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
36         0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc, 0x2fc, 0x3f5, 0x0ff, 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
37         0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c, 0x36c, 0x265, 0x16f, 0x066, 0x76a, 0x663, 0x569, 0x460,
38         0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac, 0x4ac, 0x5a5, 0x6af, 0x7a6, 0x0aa, 0x1a3, 0x2a9, 0x3a0,
39         0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c, 0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x033, 0x339, 0x230,
40         0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c, 0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x099, 0x190,
41         0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c, 0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x000
42 };
43 
44 /* For each vertex state listed in cube_edge_flags there is a specific triangulation
45  * of the edge intersection points.  triangle_table lists all 256 of them in the
46  * form of 0 to 4 edge triples with the list terminated by the invalid value -1.
47  * For example: triangle_table[3] indicates the 2 triangles formed when corner[0]
48  * and corner[1] are inside of the isosurface, but the rest of the cube is not.
49  */
50 /*
51                    README file for
52 
53                Heller's Marching Cubes
54                        (HMC)
55              written by Geoffrey Heller
56                  <heller@arsc.edu>
57 
58          First official public domain release
59               Version 3.00 dated 8-6-94
60  */
61 static char triangle_table[256][13]=
62 {
63     {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
64     { 8, 3, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
65     { 9, 0, 1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
66     { 8, 3, 1, 8, 1, 9,-1,-1,-1,-1,-1,-1,-1},
67     {10, 1, 2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
68     { 8, 3, 0, 1, 2,10,-1,-1,-1,-1,-1,-1,-1},
69     { 9, 0, 2, 9, 2,10,-1,-1,-1,-1,-1,-1,-1},
70     { 3, 2, 8, 2,10, 8, 8,10, 9,-1,-1,-1,-1},
71     {11, 2, 3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
72     {11, 2, 0,11, 0, 8,-1,-1,-1,-1,-1,-1,-1},
73     {11, 2, 3, 0, 1, 9,-1,-1,-1,-1,-1,-1,-1},
74     { 2, 1,11, 1, 9,11,11, 9, 8,-1,-1,-1,-1},
75     {10, 1, 3,10, 3,11,-1,-1,-1,-1,-1,-1,-1},
76     { 1, 0,10, 0, 8,10,10, 8,11,-1,-1,-1,-1},
77     { 0, 3, 9, 3,11, 9, 9,11,10,-1,-1,-1,-1},
78     { 8,10, 9, 8,11,10,-1,-1,-1,-1,-1,-1,-1},
79     { 8, 4, 7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
80     { 3, 0, 4, 3, 4, 7,-1,-1,-1,-1,-1,-1,-1},
81     { 1, 9, 0, 8, 4, 7,-1,-1,-1,-1,-1,-1,-1},
82     { 9, 4, 1, 4, 7, 1, 1, 7, 3,-1,-1,-1,-1},
83     {10, 1, 2, 8, 4, 7,-1,-1,-1,-1,-1,-1,-1},
84     { 2,10, 1, 0, 4, 7, 0, 7, 3,-1,-1,-1,-1},
85     { 4, 7, 8, 0, 2,10, 0,10, 9,-1,-1,-1,-1},
86     { 2, 7, 3, 2, 9, 7, 7, 9, 4, 2,10, 9,-1},
87     { 2, 3,11, 7, 8, 4,-1,-1,-1,-1,-1,-1,-1},
88     { 7,11, 4,11, 2, 4, 4, 2, 0,-1,-1,-1,-1},
89     { 3,11, 2, 4, 7, 8, 9, 0, 1,-1,-1,-1,-1},
90     { 2, 7,11, 2, 1, 7, 1, 4, 7, 1, 9, 4,-1},
91     { 8, 4, 7,11,10, 1,11, 1, 3,-1,-1,-1,-1},
92     {11, 4, 7, 1, 4,11, 1,11,10, 1, 0, 4,-1},
93     { 3, 8, 0, 7,11, 4,11, 9, 4,11,10, 9,-1},
94     { 7,11, 4, 4,11, 9,11,10, 9,-1,-1,-1,-1},
95     { 9, 5, 4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
96     { 3, 0, 8, 4, 9, 5,-1,-1,-1,-1,-1,-1,-1},
97     { 5, 4, 0, 5, 0, 1,-1,-1,-1,-1,-1,-1,-1},
98     { 4, 8, 5, 8, 3, 5, 5, 3, 1,-1,-1,-1,-1},
99     { 2,10, 1, 9, 5, 4,-1,-1,-1,-1,-1,-1,-1},
100     { 0, 8, 3, 5, 4, 9,10, 1, 2,-1,-1,-1,-1},
101     {10, 5, 2, 5, 4, 2, 2, 4, 0,-1,-1,-1,-1},
102     { 3, 4, 8, 3, 2, 4, 2, 5, 4, 2,10, 5,-1},
103     {11, 2, 3, 9, 5, 4,-1,-1,-1,-1,-1,-1,-1},
104     { 9, 5, 4, 8,11, 2, 8, 2, 0,-1,-1,-1,-1},
105     { 3,11, 2, 1, 5, 4, 1, 4, 0,-1,-1,-1,-1},
106     { 8, 5, 4, 2, 5, 8, 2, 8,11, 2, 1, 5,-1},
107     { 5, 4, 9, 1, 3,11, 1,11,10,-1,-1,-1,-1},
108     { 0, 9, 1, 4, 8, 5, 8,10, 5, 8,11,10,-1},
109     { 3, 4, 0, 3,10, 4, 4,10, 5, 3,11,10,-1},
110     { 4, 8, 5, 5, 8,10, 8,11,10,-1,-1,-1,-1},
111     { 9, 5, 7, 9, 7, 8,-1,-1,-1,-1,-1,-1,-1},
112     { 0, 9, 3, 9, 5, 3, 3, 5, 7,-1,-1,-1,-1},
113     { 8, 0, 7, 0, 1, 7, 7, 1, 5,-1,-1,-1,-1},
114     { 1, 7, 3, 1, 5, 7,-1,-1,-1,-1,-1,-1,-1},
115     { 1, 2,10, 5, 7, 8, 5, 8, 9,-1,-1,-1,-1},
116     { 9, 1, 0,10, 5, 2, 5, 3, 2, 5, 7, 3,-1},
117     { 5, 2,10, 8, 2, 5, 8, 5, 7, 8, 0, 2,-1},
118     {10, 5, 2, 2, 5, 3, 5, 7, 3,-1,-1,-1,-1},
119     {11, 2, 3, 8, 9, 5, 8, 5, 7,-1,-1,-1,-1},
120     { 9, 2, 0, 9, 7, 2, 2, 7,11, 9, 5, 7,-1},
121     { 0, 3, 8, 2, 1,11, 1, 7,11, 1, 5, 7,-1},
122     { 2, 1,11,11, 1, 7, 1, 5, 7,-1,-1,-1,-1},
123     { 3, 9, 1, 3, 8, 9, 7,11,10, 7,10, 5,-1},
124     { 9, 1, 0,10, 7,11,10, 5, 7,-1,-1,-1,-1},
125     { 3, 8, 0, 7,10, 5, 7,11,10,-1,-1,-1,-1},
126     {11, 5, 7,11,10, 5,-1,-1,-1,-1,-1,-1,-1},
127     {10, 6, 5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
128     { 8, 3, 0,10, 6, 5,-1,-1,-1,-1,-1,-1,-1},
129     { 0, 1, 9, 5,10, 6,-1,-1,-1,-1,-1,-1,-1},
130     {10, 6, 5, 9, 8, 3, 9, 3, 1,-1,-1,-1,-1},
131     { 1, 2, 6, 1, 6, 5,-1,-1,-1,-1,-1,-1,-1},
132     { 0, 8, 3, 2, 6, 5, 2, 5, 1,-1,-1,-1,-1},
133     { 5, 9, 6, 9, 0, 6, 6, 0, 2,-1,-1,-1,-1},
134     { 9, 6, 5, 3, 6, 9, 3, 9, 8, 3, 2, 6,-1},
135     { 3,11, 2,10, 6, 5,-1,-1,-1,-1,-1,-1,-1},
136     { 6, 5,10, 2, 0, 8, 2, 8,11,-1,-1,-1,-1},
137     { 1, 9, 0, 6, 5,10,11, 2, 3,-1,-1,-1,-1},
138     { 1,10, 2, 5, 9, 6, 9,11, 6, 9, 8,11,-1},
139     {11, 6, 3, 6, 5, 3, 3, 5, 1,-1,-1,-1,-1},
140     { 0, 5, 1, 0,11, 5, 5,11, 6, 0, 8,11,-1},
141     { 0, 5, 9, 0, 3, 5, 3, 6, 5, 3,11, 6,-1},
142     { 5, 9, 6, 6, 9,11, 9, 8,11,-1,-1,-1,-1},
143     {10, 6, 5, 4, 7, 8,-1,-1,-1,-1,-1,-1,-1},
144     { 5,10, 6, 7, 3, 0, 7, 0, 4,-1,-1,-1,-1},
145     { 5,10, 6, 0, 1, 9, 8, 4, 7,-1,-1,-1,-1},
146     { 4, 5, 9, 6, 7,10, 7, 1,10, 7, 3, 1,-1},
147     { 7, 8, 4, 5, 1, 2, 5, 2, 6,-1,-1,-1,-1},
148     { 4, 1, 0, 4, 5, 1, 6, 7, 3, 6, 3, 2,-1},
149     { 9, 4, 5, 8, 0, 7, 0, 6, 7, 0, 2, 6,-1},
150     { 4, 5, 9, 6, 3, 2, 6, 7, 3,-1,-1,-1,-1},
151     { 7, 8, 4, 2, 3,11,10, 6, 5,-1,-1,-1,-1},
152     {11, 6, 7,10, 2, 5, 2, 4, 5, 2, 0, 4,-1},
153     {11, 6, 7, 8, 0, 3, 1,10, 2, 9, 4, 5,-1},
154     { 6, 7,11, 1,10, 2, 9, 4, 5,-1,-1,-1,-1},
155     { 6, 7,11, 4, 5, 8, 5, 3, 8, 5, 1, 3,-1},
156     { 6, 7,11, 4, 1, 0, 4, 5, 1,-1,-1,-1,-1},
157     { 4, 5, 9, 3, 8, 0,11, 6, 7,-1,-1,-1,-1},
158     { 9, 4, 5, 7,11, 6,-1,-1,-1,-1,-1,-1,-1},
159     {10, 6, 4,10, 4, 9,-1,-1,-1,-1,-1,-1,-1},
160     { 8, 3, 0, 9,10, 6, 9, 6, 4,-1,-1,-1,-1},
161     { 1,10, 0,10, 6, 0, 0, 6, 4,-1,-1,-1,-1},
162     { 8, 6, 4, 8, 1, 6, 6, 1,10, 8, 3, 1,-1},
163     { 9, 1, 4, 1, 2, 4, 4, 2, 6,-1,-1,-1,-1},
164     { 1, 0, 9, 3, 2, 8, 2, 4, 8, 2, 6, 4,-1},
165     { 2, 4, 0, 2, 6, 4,-1,-1,-1,-1,-1,-1,-1},
166     { 3, 2, 8, 8, 2, 4, 2, 6, 4,-1,-1,-1,-1},
167     { 2, 3,11, 6, 4, 9, 6, 9,10,-1,-1,-1,-1},
168     { 0,10, 2, 0, 9,10, 4, 8,11, 4,11, 6,-1},
169     {10, 2, 1,11, 6, 3, 6, 0, 3, 6, 4, 0,-1},
170     {10, 2, 1,11, 4, 8,11, 6, 4,-1,-1,-1,-1},
171     { 1, 4, 9,11, 4, 1,11, 1, 3,11, 6, 4,-1},
172     { 0, 9, 1, 4,11, 6, 4, 8,11,-1,-1,-1,-1},
173     {11, 6, 3, 3, 6, 0, 6, 4, 0,-1,-1,-1,-1},
174     { 8, 6, 4, 8,11, 6,-1,-1,-1,-1,-1,-1,-1},
175     { 6, 7,10, 7, 8,10,10, 8, 9,-1,-1,-1,-1},
176     { 9, 3, 0, 6, 3, 9, 6, 9,10, 6, 7, 3,-1},
177     { 6, 1,10, 6, 7, 1, 7, 0, 1, 7, 8, 0,-1},
178     { 6, 7,10,10, 7, 1, 7, 3, 1,-1,-1,-1,-1},
179     { 7, 2, 6, 7, 9, 2, 2, 9, 1, 7, 8, 9,-1},
180     { 1, 0, 9, 3, 6, 7, 3, 2, 6,-1,-1,-1,-1},
181     { 8, 0, 7, 7, 0, 6, 0, 2, 6,-1,-1,-1,-1},
182     { 2, 7, 3, 2, 6, 7,-1,-1,-1,-1,-1,-1,-1},
183     { 7,11, 6, 3, 8, 2, 8,10, 2, 8, 9,10,-1},
184     {11, 6, 7,10, 0, 9,10, 2, 0,-1,-1,-1,-1},
185     { 2, 1,10, 7,11, 6, 8, 0, 3,-1,-1,-1,-1},
186     { 1,10, 2, 6, 7,11,-1,-1,-1,-1,-1,-1,-1},
187     { 7,11, 6, 3, 9, 1, 3, 8, 9,-1,-1,-1,-1},
188     { 9, 1, 0,11, 6, 7,-1,-1,-1,-1,-1,-1,-1},
189     { 0, 3, 8,11, 6, 7,-1,-1,-1,-1,-1,-1,-1},
190     {11, 6, 7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
191     {11, 7, 6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
192     { 0, 8, 3,11, 7, 6,-1,-1,-1,-1,-1,-1,-1},
193     { 9, 0, 1,11, 7, 6,-1,-1,-1,-1,-1,-1,-1},
194     { 7, 6,11, 3, 1, 9, 3, 9, 8,-1,-1,-1,-1},
195     { 1, 2,10, 6,11, 7,-1,-1,-1,-1,-1,-1,-1},
196     { 2,10, 1, 7, 6,11, 8, 3, 0,-1,-1,-1,-1},
197     {11, 7, 6,10, 9, 0,10, 0, 2,-1,-1,-1,-1},
198     { 7, 6,11, 3, 2, 8, 8, 2,10, 8,10, 9,-1},
199     { 2, 3, 7, 2, 7, 6,-1,-1,-1,-1,-1,-1,-1},
200     { 8, 7, 0, 7, 6, 0, 0, 6, 2,-1,-1,-1,-1},
201     { 1, 9, 0, 3, 7, 6, 3, 6, 2,-1,-1,-1,-1},
202     { 7, 6, 2, 7, 2, 9, 2, 1, 9, 7, 9, 8,-1},
203     { 6,10, 7,10, 1, 7, 7, 1, 3,-1,-1,-1,-1},
204     { 6,10, 1, 6, 1, 7, 7, 1, 0, 7, 0, 8,-1},
205     { 9, 0, 3, 6, 9, 3, 6,10, 9, 6, 3, 7,-1},
206     { 6,10, 7, 7,10, 8,10, 9, 8,-1,-1,-1,-1},
207     { 8, 4, 6, 8, 6,11,-1,-1,-1,-1,-1,-1,-1},
208     {11, 3, 6, 3, 0, 6, 6, 0, 4,-1,-1,-1,-1},
209     { 0, 1, 9, 4, 6,11, 4,11, 8,-1,-1,-1,-1},
210     { 1, 9, 4,11, 1, 4,11, 3, 1,11, 4, 6,-1},
211     {10, 1, 2,11, 8, 4,11, 4, 6,-1,-1,-1,-1},
212     {10, 1, 2,11, 3, 6, 6, 3, 0, 6, 0, 4,-1},
213     { 0, 2,10, 0,10, 9, 4,11, 8, 4, 6,11,-1},
214     { 2,11, 3, 6, 9, 4, 6,10, 9,-1,-1,-1,-1},
215     { 3, 8, 2, 8, 4, 2, 2, 4, 6,-1,-1,-1,-1},
216     { 2, 0, 4, 2, 4, 6,-1,-1,-1,-1,-1,-1,-1},
217     { 1, 9, 0, 3, 8, 2, 2, 8, 4, 2, 4, 6,-1},
218     { 9, 4, 1, 1, 4, 2, 4, 6, 2,-1,-1,-1,-1},
219     { 8, 4, 6, 8, 6, 1, 6,10, 1, 8, 1, 3,-1},
220     { 1, 0,10,10, 0, 6, 0, 4, 6,-1,-1,-1,-1},
221     { 8, 0, 3, 9, 6,10, 9, 4, 6,-1,-1,-1,-1},
222     {10, 4, 6,10, 9, 4,-1,-1,-1,-1,-1,-1,-1},
223     { 9, 5, 4, 7, 6,11,-1,-1,-1,-1,-1,-1,-1},
224     { 4, 9, 5, 3, 0, 8,11, 7, 6,-1,-1,-1,-1},
225     { 6,11, 7, 4, 0, 1, 4, 1, 5,-1,-1,-1,-1},
226     { 6,11, 7, 4, 8, 5, 5, 8, 3, 5, 3, 1,-1},
227     { 6,11, 7, 1, 2,10, 9, 5, 4,-1,-1,-1,-1},
228     {11, 7, 6, 8, 3, 0, 1, 2,10, 9, 5, 4,-1},
229     {11, 7, 6,10, 5, 2, 2, 5, 4, 2, 4, 0,-1},
230     { 7, 4, 8, 2,11, 3,10, 5, 6,-1,-1,-1,-1},
231     { 4, 9, 5, 6, 2, 3, 6, 3, 7,-1,-1,-1,-1},
232     { 9, 5, 4, 8, 7, 0, 0, 7, 6, 0, 6, 2,-1},
233     { 4, 0, 1, 4, 1, 5, 6, 3, 7, 6, 2, 3,-1},
234     { 7, 4, 8, 5, 2, 1, 5, 6, 2,-1,-1,-1,-1},
235     { 4, 9, 5, 6,10, 7, 7,10, 1, 7, 1, 3,-1},
236     { 5, 6,10, 0, 9, 1, 8, 7, 4,-1,-1,-1,-1},
237     { 5, 6,10, 7, 0, 3, 7, 4, 0,-1,-1,-1,-1},
238     {10, 5, 6, 4, 8, 7,-1,-1,-1,-1,-1,-1,-1},
239     { 5, 6, 9, 6,11, 9, 9,11, 8,-1,-1,-1,-1},
240     { 0, 9, 5, 0, 5, 3, 3, 5, 6, 3, 6,11,-1},
241     { 0, 1, 5, 0, 5,11, 5, 6,11, 0,11, 8,-1},
242     {11, 3, 6, 6, 3, 5, 3, 1, 5,-1,-1,-1,-1},
243     { 1, 2,10, 5, 6, 9, 9, 6,11, 9,11, 8,-1},
244     { 1, 0, 9, 6,10, 5,11, 3, 2,-1,-1,-1,-1},
245     { 6,10, 5, 2, 8, 0, 2,11, 8,-1,-1,-1,-1},
246     { 3, 2,11,10, 5, 6,-1,-1,-1,-1,-1,-1,-1},
247     { 9, 5, 6, 3, 9, 6, 3, 8, 9, 3, 6, 2,-1},
248     { 5, 6, 9, 9, 6, 0, 6, 2, 0,-1,-1,-1,-1},
249     { 0, 3, 8, 2, 5, 6, 2, 1, 5,-1,-1,-1,-1},
250     { 1, 6, 2, 1, 5, 6,-1,-1,-1,-1,-1,-1,-1},
251     {10, 5, 6, 9, 3, 8, 9, 1, 3,-1,-1,-1,-1},
252     { 0, 9, 1, 5, 6,10,-1,-1,-1,-1,-1,-1,-1},
253     { 8, 0, 3,10, 5, 6,-1,-1,-1,-1,-1,-1,-1},
254     {10, 5, 6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
255     {11, 7, 5,11, 5,10,-1,-1,-1,-1,-1,-1,-1},
256     { 3, 0, 8, 7, 5,10, 7,10,11,-1,-1,-1,-1},
257     { 9, 0, 1,10,11, 7,10, 7, 5,-1,-1,-1,-1},
258     { 3, 1, 9, 3, 9, 8, 7,10,11, 7, 5,10,-1},
259     { 2,11, 1,11, 7, 1, 1, 7, 5,-1,-1,-1,-1},
260     { 0, 8, 3, 2,11, 1, 1,11, 7, 1, 7, 5,-1},
261     { 9, 0, 2, 9, 2, 7, 2,11, 7, 9, 7, 5,-1},
262     {11, 3, 2, 8, 5, 9, 8, 7, 5,-1,-1,-1,-1},
263     {10, 2, 5, 2, 3, 5, 5, 3, 7,-1,-1,-1,-1},
264     { 5,10, 2, 8, 5, 2, 8, 7, 5, 8, 2, 0,-1},
265     { 9, 0, 1,10, 2, 5, 5, 2, 3, 5, 3, 7,-1},
266     { 1,10, 2, 5, 8, 7, 5, 9, 8,-1,-1,-1,-1},
267     { 1, 3, 7, 1, 7, 5,-1,-1,-1,-1,-1,-1,-1},
268     { 8, 7, 0, 0, 7, 1, 7, 5, 1,-1,-1,-1,-1},
269     { 0, 3, 9, 9, 3, 5, 3, 7, 5,-1,-1,-1,-1},
270     { 9, 7, 5, 9, 8, 7,-1,-1,-1,-1,-1,-1,-1},
271     { 4, 5, 8, 5,10, 8, 8,10,11,-1,-1,-1,-1},
272     { 3, 0, 4, 3, 4,10, 4, 5,10, 3,10,11,-1},
273     { 0, 1, 9, 4, 5, 8, 8, 5,10, 8,10,11,-1},
274     { 5, 9, 4, 1,11, 3, 1,10,11,-1,-1,-1,-1},
275     { 8, 4, 5, 2, 8, 5, 2,11, 8, 2, 5, 1,-1},
276     { 3, 2,11, 1, 4, 5, 1, 0, 4,-1,-1,-1,-1},
277     { 9, 4, 5, 8, 2,11, 8, 0, 2,-1,-1,-1,-1},
278     {11, 3, 2, 9, 4, 5,-1,-1,-1,-1,-1,-1,-1},
279     { 3, 8, 4, 3, 4, 2, 2, 4, 5, 2, 5,10,-1},
280     {10, 2, 5, 5, 2, 4, 2, 0, 4,-1,-1,-1,-1},
281     { 0, 3, 8, 5, 9, 4,10, 2, 1,-1,-1,-1,-1},
282     { 2, 1,10, 9, 4, 5,-1,-1,-1,-1,-1,-1,-1},
283     { 4, 5, 8, 8, 5, 3, 5, 1, 3,-1,-1,-1,-1},
284     { 5, 0, 4, 5, 1, 0,-1,-1,-1,-1,-1,-1,-1},
285     { 3, 8, 0, 4, 5, 9,-1,-1,-1,-1,-1,-1,-1},
286     { 9, 4, 5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
287     { 7, 4,11, 4, 9,11,11, 9,10,-1,-1,-1,-1},
288     { 3, 0, 8, 7, 4,11,11, 4, 9,11, 9,10,-1},
289     {11, 7, 4, 1,11, 4, 1,10,11, 1, 4, 0,-1},
290     { 8, 7, 4,11, 1,10,11, 3, 1,-1,-1,-1,-1},
291     { 2,11, 7, 2, 7, 1, 1, 7, 4, 1, 4, 9,-1},
292     { 3, 2,11, 4, 8, 7, 9, 1, 0,-1,-1,-1,-1},
293     { 7, 4,11,11, 4, 2, 4, 0, 2,-1,-1,-1,-1},
294     { 2,11, 3, 7, 4, 8,-1,-1,-1,-1,-1,-1,-1},
295     { 2, 3, 7, 2, 7, 9, 7, 4, 9, 2, 9,10,-1},
296     { 4, 8, 7, 0,10, 2, 0, 9,10,-1,-1,-1,-1},
297     { 2, 1,10, 0, 7, 4, 0, 3, 7,-1,-1,-1,-1},
298     {10, 2, 1, 8, 7, 4,-1,-1,-1,-1,-1,-1,-1},
299     { 9, 1, 4, 4, 1, 7, 1, 3, 7,-1,-1,-1,-1},
300     { 1, 0, 9, 8, 7, 4,-1,-1,-1,-1,-1,-1,-1},
301     { 3, 4, 0, 3, 7, 4,-1,-1,-1,-1,-1,-1,-1},
302     { 8, 7, 4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
303     { 8, 9,10, 8,10,11,-1,-1,-1,-1,-1,-1,-1},
304     { 0, 9, 3, 3, 9,11, 9,10,11,-1,-1,-1,-1},
305     { 1,10, 0, 0,10, 8,10,11, 8,-1,-1,-1,-1},
306     {10, 3, 1,10,11, 3,-1,-1,-1,-1,-1,-1,-1},
307     { 2,11, 1, 1,11, 9,11, 8, 9,-1,-1,-1,-1},
308     {11, 3, 2, 0, 9, 1,-1,-1,-1,-1,-1,-1,-1},
309     {11, 0, 2,11, 8, 0,-1,-1,-1,-1,-1,-1,-1},
310     {11, 3, 2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
311     { 3, 8, 2, 2, 8,10, 8, 9,10,-1,-1,-1,-1},
312     { 9, 2, 0, 9,10, 2,-1,-1,-1,-1,-1,-1,-1},
313     { 8, 0, 3, 1,10, 2,-1,-1,-1,-1,-1,-1,-1},
314     {10, 2, 1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
315     { 8, 1, 3, 8, 9, 1,-1,-1,-1,-1,-1,-1,-1},
316     { 9, 1, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
317     { 8, 0, 3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
318     {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
319 };
320