marching_cubes_poisson.cpp
Go to the documentation of this file.
00001 /*
00002  * Software License Agreement (BSD License)
00003  *
00004  *  Point Cloud Library (PCL) - www.pointclouds.org
00005  *  Copyright (c) 2009-2012, Willow Garage, Inc.
00006  *  Copyright (c) 2006, Michael Kazhdan and Matthew Bolitho,
00007  *                      Johns Hopkins University
00008  *
00009  *  All rights reserved.
00010  *
00011  *  Redistribution and use in source and binary forms, with or without
00012  *  modification, are permitted provided that the following conditions
00013  *  are met:
00014  *
00015  *   * Redistributions of source code must retain the above copyright
00016  *     notice, this list of conditions and the following disclaimer.
00017  *   * Redistributions in binary form must reproduce the above
00018  *     copyright notice, this list of conditions and the following
00019  *     disclaimer in the documentation and/or other materials provided
00020  *     with the distribution.
00021  *   * Neither the name of Willow Garage, Inc. nor the names of its
00022  *     contributors may be used to endorse or promote products derived
00023  *     from this software without specific prior written permission.
00024  *
00025  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00026  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00027  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
00028  *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
00029  *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
00030  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
00031  *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00032  *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
00033  *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00034  *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
00035  *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00036  *  POSSIBILITY OF SUCH DAMAGE.
00037  *
00038  * $Id: marching_cubes_poisson.cpp 5027 2012-03-12 03:10:45Z rusu $
00039  *
00040  */
00041 
00042 #include <math.h>
00043 #include <pcl/surface/poisson/marching_cubes_poisson.h>
00044 
00045 
00046 namespace pcl {
00047   namespace poisson {
00048 
00050     // Square //
00052     int Square::CornerIndex(const int& x,const int& y){return (y<<1)|x;}
00053     void Square::FactorCornerIndex(const int& idx,int& x,int& y){
00054       x=(idx>>0)%2;
00055       y=(idx>>1)%2;
00056     }
00057     int Square::EdgeIndex(const int& orientation,const int& i){
00058       switch(orientation){
00059         case 0: // x
00060           if(!i)        {return  0;} // (0,0) -> (1,0)
00061           else  {return  2;} // (0,1) -> (1,1)
00062         case 1: // y
00063           if(!i)        {return  3;} // (0,0) -> (0,1)
00064           else  {return  1;} // (1,0) -> (1,1)
00065       };
00066       return -1;
00067     }
00068     void Square::FactorEdgeIndex(const int& idx,int& orientation,int& i){
00069       switch(idx){
00070         case 0: case 2:
00071           orientation=0;
00072           i=idx/2;
00073           return;
00074         case 1: case 3:
00075           orientation=1;
00076           i=((idx/2)+1)%2;
00077           return;
00078       };
00079     }
00080     void Square::EdgeCorners(const int& idx,int& c1,int& c2){
00081       int orientation,i;
00082       FactorEdgeIndex(idx,orientation,i);
00083       switch(orientation){
00084         case 0:
00085           c1=CornerIndex(0,i);
00086           c2=CornerIndex(1,i);
00087           break;
00088         case 1:
00089           c1=CornerIndex(i,0);
00090           c2=CornerIndex(i,1);
00091           break;
00092       };
00093     }
00094     int Square::ReflectEdgeIndex(const int& idx,const int& edgeIndex){
00095       int orientation=edgeIndex%2;
00096       int o,i;
00097       FactorEdgeIndex(idx,o,i);
00098       if(o!=orientation){return idx;}
00099       else{return EdgeIndex(o,(i+1)%2);}
00100     }
00101     int Square::ReflectCornerIndex(const int& idx,const int& edgeIndex){
00102       int orientation=edgeIndex%2;
00103       int x,y;
00104       FactorCornerIndex(idx,x,y);
00105       switch(orientation){
00106         case 0: return CornerIndex((x+1)%2,y);
00107         case 1: return CornerIndex(x,(y+1)%2);
00108       };
00109       return -1;
00110     }
00111 
00112 
00113 
00115     // Cube //
00117     int Cube::CornerIndex(const int& x,const int& y,const int& z){return (z<<2)|(y<<1)|x;}
00118     void Cube::FactorCornerIndex(const int& idx,int& x,int& y,int& z){
00119       x=(idx>>0)%2;
00120       y=(idx>>1)%2;
00121       z=(idx>>2)%2;
00122     }
00123     int Cube::EdgeIndex(const int& orientation,const int& i,const int& j){return (i | (j<<1))|(orientation<<2);}
00124     void Cube::FactorEdgeIndex(const int& idx,int& orientation,int& i,int &j){
00125       orientation=idx>>2;
00126       i=idx&1;
00127       j=(idx&2)>>1;
00128     }
00129     int Cube::FaceIndex(const int& x,const int& y,const int& z){
00130       if                (x<0)   {return  0;}
00131       else if   (x>0)   {return  1;}
00132       else if   (y<0)   {return  2;}
00133       else if   (y>0)   {return  3;}
00134       else if   (z<0)   {return  4;}
00135       else if   (z>0)   {return  5;}
00136       else                      {return -1;}
00137     }
00138     int Cube::FaceIndex(const int& dir,const int& offSet){return (dir<<1)|offSet;}
00139 
00140     void Cube::FactorFaceIndex(const int& idx,int& x,int& y,int& z){
00141       x=y=z=0;
00142       switch(idx){
00143         case 0:         x=-1;   break;
00144         case 1:         x= 1;   break;
00145         case 2:         y=-1;   break;
00146         case 3:         y= 1;   break;
00147         case 4:         z=-1;   break;
00148         case 5:         z= 1;   break;
00149       };
00150     }
00151     void Cube::FactorFaceIndex(const int& idx,int& dir,int& offSet){
00152       dir  = idx>>1;
00153       offSet=idx &1;
00154     }
00155 
00156     int Cube::FaceAdjacentToEdges(const int& eIndex1,const int& eIndex2){
00157       int f1,f2,g1,g2;
00158       FacesAdjacentToEdge(eIndex1,f1,f2);
00159       FacesAdjacentToEdge(eIndex2,g1,g2);
00160       if(f1==g1 || f1==g2){return f1;}
00161       if(f2==g1 || f2==g2){return f2;}
00162       return -1;
00163     }
00164 
00165     void Cube::FacesAdjacentToEdge(const int& eIndex,int& f1Index,int& f2Index){
00166       int orientation,i1,i2;
00167       FactorEdgeIndex(eIndex,orientation,i1,i2);
00168       i1<<=1;
00169       i2<<=1;
00170       i1--;
00171       i2--;
00172       switch(orientation){
00173         case 0:
00174           f1Index=FaceIndex( 0,i1, 0);
00175           f2Index=FaceIndex( 0, 0,i2);
00176           break;
00177         case 1:
00178           f1Index=FaceIndex(i1, 0, 0);
00179           f2Index=FaceIndex( 0, 0,i2);
00180           break;
00181         case 2:
00182           f1Index=FaceIndex(i1, 0, 0);
00183           f2Index=FaceIndex( 0,i2, 0);
00184           break;
00185       };
00186     }
00187     void Cube::EdgeCorners(const int& idx,int& c1,int& c2){
00188       int orientation,i1,i2;
00189       FactorEdgeIndex(idx,orientation,i1,i2);
00190       switch(orientation){
00191         case 0:
00192           c1=CornerIndex(0,i1,i2);
00193           c2=CornerIndex(1,i1,i2);
00194           break;
00195         case 1:
00196           c1=CornerIndex(i1,0,i2);
00197           c2=CornerIndex(i1,1,i2);
00198           break;
00199         case 2:
00200           c1=CornerIndex(i1,i2,0);
00201           c2=CornerIndex(i1,i2,1);
00202           break;
00203       };
00204     }
00205     void Cube::FaceCorners(const int& idx,int& c1,int& c2,int& c3,int& c4){
00206       int i=idx%2;
00207       switch(idx/2){
00208         case 0:
00209           c1=CornerIndex(i,0,0);
00210           c2=CornerIndex(i,1,0);
00211           c3=CornerIndex(i,0,1);
00212           c4=CornerIndex(i,1,1);
00213           return;
00214         case 1:
00215           c1=CornerIndex(0,i,0);
00216           c2=CornerIndex(1,i,0);
00217           c3=CornerIndex(0,i,1);
00218           c4=CornerIndex(1,i,1);
00219           return;
00220         case 2:
00221           c1=CornerIndex(0,0,i);
00222           c2=CornerIndex(1,0,i);
00223           c3=CornerIndex(0,1,i);
00224           c4=CornerIndex(1,1,i);
00225           return;
00226       }
00227     }
00228     int Cube::AntipodalCornerIndex(const int& idx){
00229       int x,y,z;
00230       FactorCornerIndex(idx,x,y,z);
00231       return CornerIndex((x+1)%2,(y+1)%2,(z+1)%2);
00232     }
00233     int Cube::FaceReflectFaceIndex(const int& idx,const int& faceIndex){
00234       if(idx/2!=faceIndex/2){return idx;}
00235       else{
00236         if(idx%2)       {return idx-1;}
00237         else            {return idx+1;}
00238       }
00239     }
00240     int Cube::FaceReflectEdgeIndex(const int& idx,const int& faceIndex){
00241       int orientation=faceIndex/2;
00242       int o,i,j;
00243       FactorEdgeIndex(idx,o,i,j);
00244       if(o==orientation){return idx;}
00245       switch(orientation){
00246         case 0: return EdgeIndex(o,(i+1)%2,j);
00247         case 1:
00248           switch(o){
00249             case 0:     return EdgeIndex(o,(i+1)%2,j);
00250             case 2:     return EdgeIndex(o,i,(j+1)%2);
00251           };
00252             case 2:     return EdgeIndex(o,i,(j+1)%2);
00253       };
00254       return -1;
00255     }
00256     int Cube::FaceReflectCornerIndex(const int& idx,const int& faceIndex){
00257       int orientation=faceIndex/2;
00258       int x,y,z;
00259       FactorCornerIndex(idx,x,y,z);
00260       switch(orientation){
00261         case 0: return CornerIndex((x+1)%2,y,z);
00262         case 1: return CornerIndex(x,(y+1)%2,z);
00263         case 2: return CornerIndex(x,y,(z+1)%2);
00264       };
00265       return -1;
00266     }
00267     int Cube::EdgeReflectCornerIndex(const int& idx,const int& edgeIndex){
00268       int orientation,x,y,z;
00269       FactorEdgeIndex(edgeIndex,orientation,x,y);
00270       FactorCornerIndex(idx,x,y,z);
00271       switch(orientation){
00272         case 0: return CornerIndex( x     ,(y+1)%2,(z+1)%2);
00273         case 1: return CornerIndex((x+1)%2, y     ,(z+1)%2);
00274         case 2: return CornerIndex((x+1)%2,(y+1)%2, z     );
00275       };
00276       return -1;
00277     }
00278     int Cube::EdgeReflectEdgeIndex(const int& edgeIndex){
00279       int o,i1,i2;
00280       FactorEdgeIndex(edgeIndex,o,i1,i2);
00281       return Cube::EdgeIndex(o,(i1+1)%2,(i2+1)%2);
00282     }
00283 
00284 
00286     // MarchingSquares //
00288     /*
00289 0} // (0,0) -> (1,0)
00290 1} // (1,0) -> (1,1)
00291 2} // (0,1) -> (1,1)
00292 3} // (0,0) -> (0,1)
00293      */
00294     const int MarchingSquares::edgeMask[1<<Square::CORNERS]={
00295                                                              0, //  0 ->         ->                         ->
00296                                                              9, //  1 -> 0       -> (0,0)                   -> 0,3     ->  9
00297                                                              3, //  2 -> 1       -> (1,0)                   -> 0,1     ->  3
00298                                                              10, //  3 -> 0,1     -> (0,0) (1,0)             -> 1,3     -> 10
00299                                                              12, //  4 -> 2       -> (0,1)                   -> 2,3     -> 12
00300                                                              5, //  5 -> 0,2     -> (0,0) (0,1)             -> 0,2     ->  5
00301                                                              15, //  6 -> 1,2     -> (1,0) (0,1)             -> 0,1,2,3 -> 15
00302                                                              6, //  7 -> 0,1,2   -> (0,0) (1,0) (0,1)       -> 1,2     ->  6
00303                                                              6, //  8 -> 3       -> (1,1)                   -> 1,2     ->  6
00304                                                              15, //  9 -> 0,3     -> (0,0) (1,1)             -> 0,1,2,3 -> 15
00305                                                              5, // 10 -> 1,3     -> (1,0) (1,1)             -> 0,2     ->  5
00306                                                              12, // 11 -> 0,1,3   -> (0,0) (1,0) (1,1)       -> 2,3     -> 12
00307                                                              10, // 12 -> 2,3     -> (0,1) (1,1)             -> 1,3     -> 10
00308                                                              3, // 13 -> 0,2,3   -> (0,0) (0,1) (1,1)       -> 0,1     ->  3
00309                                                              9, // 14 -> 1,2,3   -> (1,0) (0,1) (1,1)       -> 0,3     ->  9
00310                                                              0, // 15 -> 0,1,2,3 -> (0,0) (1,0) (0,1) (1,1) ->
00311     };
00312     const int MarchingSquares::edges[1<<Square::CORNERS][MAX_EDGES*2+1] = {
00313                                                                            { -1,  -1,  -1,  -1,  -1}, //
00314                                                                            {  3,   0,  -1,  -1,  -1}, // (0,0)
00315                                                                            {  0,   1,  -1,  -1,  -1}, // (1,0)
00316                                                                            {  3,   1,  -1,  -1,  -1}, // (0,0) (1,0)
00317                                                                            {  2,   3,  -1,  -1,  -1}, // (0,1)
00318                                                                            {  2,   0,  -1,  -1,  -1}, // (0,0) (0,1)
00319                                                                            {  0,   1,   2,   3,  -1}, // (1,0) (0,1)
00320                                                                            {  1,   2,  -1,  -1,  -1}, // (0,0) (1,0) (0,1)
00321                                                                            {  2,   1,  -1,  -1,  -1}, // (1,1)
00322                                                                            {  3,   0,   1,   2,  -1}, // (0,0) (1,1)
00323                                                                            {  0,   2,  -1,  -1,  -1}, // (1,0) (1,1)
00324                                                                            {  3,   2,  -1,  -1,  -1}, // (0,0) (1,0) (1,1)
00325                                                                            {  1,   3,  -1,  -1,  -1}, // (0,1) (1,1)
00326                                                                            {  1,   0,  -1,  -1,  -1}, // (0,0) (0,1) (1,1)
00327                                                                            {  0,   3,  -1,  -1,  -1}, // (1,0) (0,1) (1,1)
00328                                                                            { -1,  -1,  -1,  -1,  -1}, // (0,0) (1,0) (0,1) (1,1)
00329     };
00330 
00331     double MarchingSquares::vertexList[Square::EDGES][2];
00332     int MarchingSquares::GetIndex(const double v[Square::CORNERS],const double& iso){
00333       int idx=0;
00334       for(int i=0;i<Square::CORNERS;i++){if(v[i]<iso){idx|=(1<<i);}}
00335       return idx;
00336     }
00337 
00338     int MarchingSquares::IsAmbiguous(const double v[Square::CORNERS],const double& isoValue){
00339       int idx=GetIndex(v,isoValue);
00340       return (idx==5) || (idx==10);
00341     }
00342     int MarchingSquares::AddEdges(const double v[Square::CORNERS],const double& iso,Edge* isoEdges){
00343       int idx,nEdges=0;
00344       Edge e;
00345 
00346       idx=GetIndex(v,iso);
00347 
00348       /* Cube is entirely in/out of the surface */
00349       if (!edgeMask[idx]) return 0;
00350 
00351       /* Find the vertices where the surface intersects the cube */
00352       int i,j,ii=1;
00353       for(i=0;i<12;i++){
00354         if(edgeMask[idx] & ii){SetVertex(i,v,iso);}
00355         ii<<=1;
00356       }
00357       /* Create the triangle */
00358       for (i=0;edges[idx][i]!=-1;i+=2) {
00359         for(j=0;j<2;j++){
00360           e.p[0][j]=vertexList[edges[idx][i+0]][j];
00361           e.p[1][j]=vertexList[edges[idx][i+1]][j];
00362         }
00363         isoEdges[nEdges++]=e;
00364       }
00365       return nEdges;
00366     }
00367 
00368     int MarchingSquares::AddEdgeIndices(const double v[Square::CORNERS],const double& iso,int* isoIndices){
00369       int idx,nEdges=0;
00370 
00371       idx=GetIndex(v,iso);
00372 
00373       /* Cube is entirely in/out of the surface */
00374       if (!edgeMask[idx]) return 0;
00375 
00376       /* Create the triangle */
00377       for(int i=0;edges[idx][i]!=-1;i+=2){
00378         for(int j=0;j<2;j++){isoIndices[i+j]=edges[idx][i+j];}
00379         nEdges++;
00380       }
00381       return nEdges;
00382     }
00383     void MarchingSquares::SetVertex(const int& e,const double values[Square::CORNERS],const double& iso){
00384       int o,i,c1,c2;
00385       Square::FactorEdgeIndex(e,o,i);
00386       Square::EdgeCorners(e,c1,c2);
00387       switch(o){
00388         case 0:
00389           vertexList[e][0]=Interpolate(values[c1]-iso,values[c2]-iso);
00390           vertexList[e][1]=i;
00391           break;
00392         case 1:
00393           vertexList[e][1]=Interpolate(values[c1]-iso,values[c2]-iso);
00394           vertexList[e][0]=i;
00395           break;
00396       }
00397     }
00398     double MarchingSquares::Interpolate(const double& v1,const double& v2){return v1/(v1-v2);}
00399 
00400 
00402     // MarchingCubes //
00404     const int MarchingCubes::edgeMask[1<<Cube::CORNERS]={
00405                                                          0,  273,  545,  816, 2082, 2355, 2563, 2834,
00406                                                          1042, 1283, 1587, 1826, 3120, 3361, 3601, 3840,
00407                                                          324,   85,  869,  628, 2406, 2167, 2887, 2646,
00408                                                          1366, 1095, 1911, 1638, 3444, 3173, 3925, 3652,
00409                                                          644,  917,  165,  436, 2726, 2999, 2183, 2454,
00410                                                          1686, 1927, 1207, 1446, 3764, 4005, 3221, 3460,
00411                                                          960,  721,  481,  240, 3042, 2803, 2499, 2258,
00412                                                          2002, 1731, 1523, 1250, 4080, 3809, 3537, 3264,
00413                                                          2184, 2457, 2729, 3000,  170,  443,  651,  922,
00414                                                          3226, 3467, 3771, 4010, 1208, 1449, 1689, 1928,
00415                                                          2508, 2269, 3053, 2812,  494,  255,  975,  734,
00416                                                          3550, 3279, 4095, 3822, 1532, 1261, 2013, 1740,
00417                                                          2572, 2845, 2093, 2364,  558,  831,   15,  286,
00418                                                          3614, 3855, 3135, 3374, 1596, 1837, 1053, 1292,
00419                                                          2888, 2649, 2409, 2168,  874,  635,  331,   90,
00420                                                          3930, 3659, 3451, 3178, 1912, 1641, 1369, 1096,
00421                                                          1096, 1369, 1641, 1912, 3178, 3451, 3659, 3930,
00422                                                          90,  331,  635,  874, 2168, 2409, 2649, 2888,
00423                                                          1292, 1053, 1837, 1596, 3374, 3135, 3855, 3614,
00424                                                          286,   15,  831,  558, 2364, 2093, 2845, 2572,
00425                                                          1740, 2013, 1261, 1532, 3822, 4095, 3279, 3550,
00426                                                          734,  975,  255,  494, 2812, 3053, 2269, 2508,
00427                                                          1928, 1689, 1449, 1208, 4010, 3771, 3467, 3226,
00428                                                          922,  651,  443,  170, 3000, 2729, 2457, 2184,
00429                                                          3264, 3537, 3809, 4080, 1250, 1523, 1731, 2002,
00430                                                          2258, 2499, 2803, 3042,  240,  481,  721,  960,
00431                                                          3460, 3221, 4005, 3764, 1446, 1207, 1927, 1686,
00432                                                          2454, 2183, 2999, 2726,  436,  165,  917,  644,
00433                                                          3652, 3925, 3173, 3444, 1638, 1911, 1095, 1366,
00434                                                          2646, 2887, 2167, 2406,  628,  869,   85,  324,
00435                                                          3840, 3601, 3361, 3120, 1826, 1587, 1283, 1042,
00436                                                          2834, 2563, 2355, 2082,  816,  545,  273,    0
00437     };
00438     const int MarchingCubes::triangles[1<<Cube::CORNERS][MAX_TRIANGLES*3+1] = {
00439                                                                                {  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00440                                                                                {   0,   4,   8,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00441                                                                                {   5,   0,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00442                                                                                {   8,   9,   5,   8,   5,   4,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00443                                                                                {   1,   5,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00444                                                                                {   0,   4,   8,   1,   5,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00445                                                                                {   9,  11,   1,   9,   1,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00446                                                                                {   8,   9,  11,   8,  11,   1,   8,   1,   4,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00447                                                                                {   4,   1,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00448                                                                                {  10,   8,   0,  10,   0,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00449                                                                                {   5,   0,   9,   4,   1,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00450                                                                                {  10,   8,   9,  10,   9,   5,  10,   5,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00451                                                                                {  11,  10,   4,  11,   4,   5,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00452                                                                                {  11,  10,   8,  11,   8,   0,  11,   0,   5,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00453                                                                                {   9,  11,  10,   9,  10,   4,   9,   4,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00454                                                                                {   8,   9,  11,   8,  11,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00455                                                                                {   8,   6,   2,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00456                                                                                {   6,   2,   0,   4,   6,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00457                                                                                {   6,   2,   8,   5,   0,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00458                                                                                {   5,   4,   6,   9,   5,   6,   2,   9,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00459                                                                                {   1,   5,  11,   8,   6,   2,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00460                                                                                {   1,   5,  11,   6,   2,   0,   4,   6,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00461                                                                                {   6,   2,   8,   9,  11,   1,   9,   1,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00462                                                                                {   9,  11,   2,   2,  11,   1,   2,   1,   6,   6,   1,   4,  -1,  -1,  -1,  -1},
00463                                                                                {   1,  10,   4,   2,   8,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00464                                                                                {   2,   0,   1,   6,   2,   1,  10,   6,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00465                                                                                {   5,   0,   9,   4,   1,  10,   8,   6,   2,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00466                                                                                {   5,   2,   9,   5,   6,   2,   5,   1,   6,   1,  10,   6,  -1,  -1,  -1,  -1},
00467                                                                                {   2,   8,   6,   4,   5,  11,   4,  11,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00468                                                                                {   5,   2,   0,   6,   2,   5,  11,   6,   5,  10,   6,  11,  -1,  -1,  -1,  -1},
00469                                                                                {   9,  11,  10,   9,  10,   4,   9,   4,   0,   8,   6,   2,  -1,  -1,  -1,  -1},
00470                                                                                {   9,  11,   2,   2,  11,   6,  10,   6,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00471                                                                                {   9,   2,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00472                                                                                {   7,   9,   2,   4,   8,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00473                                                                                {   0,   2,   7,   0,   7,   5,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00474                                                                                {   7,   5,   4,   2,   7,   4,   8,   2,   4,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00475                                                                                {   7,   9,   2,   5,  11,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00476                                                                                {   1,   5,  11,   0,   4,   8,   9,   2,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00477                                                                                {   1,   0,   2,   1,   2,   7,   1,   7,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00478                                                                                {   1,   7,  11,   1,   2,   7,   1,   4,   2,   4,   8,   2,  -1,  -1,  -1,  -1},
00479                                                                                {   4,   1,  10,   9,   2,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00480                                                                                {   7,   9,   2,   0,   1,  10,   0,  10,   8,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00481                                                                                {   4,   1,  10,   2,   7,   5,   0,   2,   5,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00482                                                                                {   2,  10,   8,   1,  10,   2,   7,   1,   2,   5,   1,   7,  -1,  -1,  -1,  -1},
00483                                                                                {   7,   9,   2,  10,   4,   5,  11,  10,   5,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00484                                                                                {  11,  10,   8,  11,   8,   0,  11,   0,   5,   9,   2,   7,  -1,  -1,  -1,  -1},
00485                                                                                {  11,  10,   7,   7,  10,   4,   7,   4,   2,   2,   4,   0,  -1,  -1,  -1,  -1},
00486                                                                                {  11,  10,   7,   7,  10,   2,   8,   2,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00487                                                                                {   7,   9,   8,   6,   7,   8,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00488                                                                                {   4,   6,   7,   0,   4,   7,   9,   0,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00489                                                                                {   6,   7,   5,   8,   6,   5,   0,   8,   5,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00490                                                                                {   4,   6,   7,   5,   4,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00491                                                                                {   5,  11,   1,   8,   6,   7,   9,   8,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00492                                                                                {   4,   6,   7,   0,   4,   7,   9,   0,   7,  11,   1,   5,  -1,  -1,  -1,  -1},
00493                                                                                {   8,   1,   0,  11,   1,   8,   6,  11,   8,   7,  11,   6,  -1,  -1,  -1,  -1},
00494                                                                                {  11,   6,   7,   1,   6,  11,   6,   1,   4,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00495                                                                                {   1,  10,   4,   6,   7,   9,   6,   9,   8,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00496                                                                                {   0,   1,   9,   9,   1,  10,   9,  10,   7,   7,  10,   6,  -1,  -1,  -1,  -1},
00497                                                                                {   6,   7,   5,   8,   6,   5,   0,   8,   5,   1,  10,   4,  -1,  -1,  -1,  -1},
00498                                                                                {   1,   7,   5,  10,   7,   1,   7,  10,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00499                                                                                {  11,  10,   4,  11,   4,   5,   7,   9,   8,   6,   7,   8,  -1,  -1,  -1,  -1},
00500                                                                                {   0,   6,   9,   9,   6,   7,   6,   0,   5,   5,  11,  10,   5,  10,   6,  -1},
00501                                                                                {   8,   7,   0,   6,   7,   8,   4,   0,   7,  11,  10,   4,   7,  11,   4,  -1},
00502                                                                                {  11,  10,   6,  11,   6,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00503                                                                                {  11,   7,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00504                                                                                {   0,   4,   8,  11,   7,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00505                                                                                {   9,   5,   0,  11,   7,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00506                                                                                {  11,   7,   3,   4,   8,   9,   5,   4,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00507                                                                                {   3,   1,   5,   3,   5,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00508                                                                                {   0,   4,   8,   7,   3,   1,   5,   7,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00509                                                                                {   3,   1,   0,   3,   0,   9,   3,   9,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00510                                                                                {   7,   8,   9,   4,   8,   7,   3,   4,   7,   1,   4,   3,  -1,  -1,  -1,  -1},
00511                                                                                {   1,  10,   4,   3,  11,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00512                                                                                {   3,  11,   7,   8,   0,   1,  10,   8,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00513                                                                                {   4,   1,  10,   5,   0,   9,  11,   7,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00514                                                                                {  10,   8,   9,  10,   9,   5,  10,   5,   1,  11,   7,   3,  -1,  -1,  -1,  -1},
00515                                                                                {   4,   5,   7,   4,   7,   3,   4,   3,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00516                                                                                {  10,   8,   3,   3,   8,   0,   3,   0,   7,   7,   0,   5,  -1,  -1,  -1,  -1},
00517                                                                                {   4,   3,  10,   4,   7,   3,   4,   0,   7,   0,   9,   7,  -1,  -1,  -1,  -1},
00518                                                                                {  10,   8,   3,   3,   8,   7,   9,   7,   8,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00519                                                                                {  11,   7,   3,   8,   6,   2,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00520                                                                                {  11,   7,   3,   2,   0,   4,   2,   4,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00521                                                                                {  11,   7,   3,   8,   6,   2,   5,   0,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00522                                                                                {   5,   4,   6,   9,   5,   6,   2,   9,   6,   3,  11,   7,  -1,  -1,  -1,  -1},
00523                                                                                {   8,   6,   2,   3,   1,   5,   3,   5,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00524                                                                                {   3,   1,   5,   3,   5,   7,   6,   2,   0,   4,   6,   0,  -1,  -1,  -1,  -1},
00525                                                                                {   3,   1,   0,   3,   0,   9,   3,   9,   7,   2,   8,   6,  -1,  -1,  -1,  -1},
00526                                                                                {   9,   4,   2,   2,   4,   6,   4,   9,   7,   7,   3,   1,   7,   1,   4,  -1},
00527                                                                                {   8,   6,   2,  11,   7,   3,   4,   1,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00528                                                                                {   2,   0,   1,   6,   2,   1,  10,   6,   1,  11,   7,   3,  -1,  -1,  -1,  -1},
00529                                                                                {   5,   0,   9,   4,   1,  10,   8,   6,   2,  11,   7,   3,  -1,  -1,  -1,  -1},
00530                                                                                {  11,   7,   3,   5,   2,   9,   5,   6,   2,   5,   1,   6,   1,  10,   6,  -1},
00531                                                                                {   4,   5,   7,   4,   7,   3,   4,   3,  10,   6,   2,   8,  -1,  -1,  -1,  -1},
00532                                                                                {  10,   5,   3,   3,   5,   7,   5,  10,   6,   6,   2,   0,   6,   0,   5,  -1},
00533                                                                                {   8,   6,   2,   4,   3,  10,   4,   7,   3,   4,   0,   7,   0,   9,   7,  -1},
00534                                                                                {   9,   7,  10,  10,   7,   3,  10,   6,   9,   6,   2,   9,  -1,  -1,  -1,  -1},
00535                                                                                {   3,  11,   9,   2,   3,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00536                                                                                {   4,   8,   0,   2,   3,  11,   2,  11,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00537                                                                                {   0,   2,   3,   0,   3,  11,   0,  11,   5,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00538                                                                                {   2,   3,   8,   8,   3,  11,   8,  11,   4,   4,  11,   5,  -1,  -1,  -1,  -1},
00539                                                                                {   2,   3,   1,   2,   1,   5,   2,   5,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00540                                                                                {   2,   3,   1,   2,   1,   5,   2,   5,   9,   0,   4,   8,  -1,  -1,  -1,  -1},
00541                                                                                {   0,   2,   3,   0,   3,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00542                                                                                {   2,   3,   8,   8,   3,   4,   1,   4,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00543                                                                                {   1,  10,   4,   9,   2,   3,  11,   9,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00544                                                                                {  10,   8,   0,  10,   0,   1,   3,  11,   9,   2,   3,   9,  -1,  -1,  -1,  -1},
00545                                                                                {   0,   2,   3,   0,   3,  11,   0,  11,   5,   1,  10,   4,  -1,  -1,  -1,  -1},
00546                                                                                {   5,   2,  11,  11,   2,   3,   2,   5,   1,   1,  10,   8,   1,   8,   2,  -1},
00547                                                                                {  10,   2,   3,   9,   2,  10,   4,   9,  10,   5,   9,   4,  -1,  -1,  -1,  -1},
00548                                                                                {   5,  10,   0,   0,  10,   8,  10,   5,   9,   9,   2,   3,   9,   3,  10,  -1},
00549                                                                                {   0,   2,   4,   4,   2,  10,   3,  10,   2,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00550                                                                                {  10,   8,   2,  10,   2,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00551                                                                                {  11,   9,   8,   3,  11,   8,   6,   3,   8,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00552                                                                                {   0,  11,   9,   3,  11,   0,   4,   3,   0,   6,   3,   4,  -1,  -1,  -1,  -1},
00553                                                                                {  11,   5,   3,   5,   0,   3,   0,   6,   3,   0,   8,   6,  -1,  -1,  -1,  -1},
00554                                                                                {   3,   4,   6,  11,   4,   3,   4,  11,   5,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00555                                                                                {   3,   1,   6,   6,   1,   5,   6,   5,   8,   8,   5,   9,  -1,  -1,  -1,  -1},
00556                                                                                {   0,   6,   9,   4,   6,   0,   5,   9,   6,   3,   1,   5,   6,   3,   5,  -1},
00557                                                                                {   3,   1,   6,   6,   1,   8,   0,   8,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00558                                                                                {   3,   1,   4,   3,   4,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00559                                                                                {  11,   9,   8,   3,  11,   8,   6,   3,   8,   4,   1,  10,  -1,  -1,  -1,  -1},
00560                                                                                {   3,   9,   6,  11,   9,   3,  10,   6,   9,   0,   1,  10,   9,   0,  10,  -1},
00561                                                                                {   4,   1,  10,  11,   5,   3,   5,   0,   3,   0,   6,   3,   0,   8,   6,  -1},
00562                                                                                {   5,  10,   6,   1,  10,   5,   6,  11,   5,   6,   3,  11,  -1,  -1,  -1,  -1},
00563                                                                                {  10,   5,   3,   4,   5,  10,   6,   3,   5,   9,   8,   6,   5,   9,   6,  -1},
00564                                                                                {   6,   3,  10,   9,   0,   5,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00565                                                                                {   3,  10,   0,   0,  10,   4,   0,   8,   3,   8,   6,   3,  -1,  -1,  -1,  -1},
00566                                                                                {   6,   3,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00567                                                                                {  10,   3,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00568                                                                                {   3,   6,  10,   0,   4,   8,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00569                                                                                {   5,   0,   9,  10,   3,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00570                                                                                {   3,   6,  10,   8,   9,   5,   8,   5,   4,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00571                                                                                {  11,   1,   5,  10,   3,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00572                                                                                {   0,   4,   8,   1,   5,  11,  10,   3,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00573                                                                                {  10,   3,   6,   0,   9,  11,   1,   0,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00574                                                                                {   8,   9,  11,   8,  11,   1,   8,   1,   4,  10,   3,   6,  -1,  -1,  -1,  -1},
00575                                                                                {   4,   1,   3,   6,   4,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00576                                                                                {   0,   1,   3,   8,   0,   3,   6,   8,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00577                                                                                {   5,   0,   9,   3,   6,   4,   1,   3,   4,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00578                                                                                {   8,   9,   6,   6,   9,   5,   6,   5,   3,   3,   5,   1,  -1,  -1,  -1,  -1},
00579                                                                                {   6,   4,   5,   6,   5,  11,   6,  11,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00580                                                                                {   0,   6,   8,   0,   3,   6,   0,   5,   3,   5,  11,   3,  -1,  -1,  -1,  -1},
00581                                                                                {   3,   9,  11,   0,   9,   3,   6,   0,   3,   4,   0,   6,  -1,  -1,  -1,  -1},
00582                                                                                {   8,   9,   6,   6,   9,   3,  11,   3,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00583                                                                                {   2,   8,  10,   3,   2,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00584                                                                                {   3,   2,   0,  10,   3,   0,   4,  10,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00585                                                                                {   5,   0,   9,   8,  10,   3,   8,   3,   2,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00586                                                                                {   9,   3,   2,  10,   3,   9,   5,  10,   9,   4,  10,   5,  -1,  -1,  -1,  -1},
00587                                                                                {  11,   1,   5,   2,   8,  10,   3,   2,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00588                                                                                {   3,   2,   0,  10,   3,   0,   4,  10,   0,   5,  11,   1,  -1,  -1,  -1,  -1},
00589                                                                                {   9,  11,   1,   9,   1,   0,   2,   8,  10,   3,   2,  10,  -1,  -1,  -1,  -1},
00590                                                                                {  10,   2,   4,   3,   2,  10,   1,   4,   2,   9,  11,   1,   2,   9,   1,  -1},
00591                                                                                {   1,   3,   2,   4,   1,   2,   8,   4,   2,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00592                                                                                {   0,   1,   3,   2,   0,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00593                                                                                {   1,   3,   2,   4,   1,   2,   8,   4,   2,   9,   5,   0,  -1,  -1,  -1,  -1},
00594                                                                                {   9,   3,   2,   5,   3,   9,   3,   5,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00595                                                                                {   3,   2,  11,  11,   2,   8,  11,   8,   5,   5,   8,   4,  -1,  -1,  -1,  -1},
00596                                                                                {   5,   2,   0,  11,   2,   5,   2,  11,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00597                                                                                {   4,   3,   8,   8,   3,   2,   3,   4,   0,   0,   9,  11,   0,  11,   3,  -1},
00598                                                                                {   9,  11,   3,   9,   3,   2,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00599                                                                                {  10,   3,   6,   9,   2,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00600                                                                                {   9,   2,   7,  10,   3,   6,   0,   4,   8,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00601                                                                                {  10,   3,   6,   7,   5,   0,   7,   0,   2,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00602                                                                                {   7,   5,   4,   2,   7,   4,   8,   2,   4,  10,   3,   6,  -1,  -1,  -1,  -1},
00603                                                                                {  10,   3,   6,   9,   2,   7,   1,   5,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00604                                                                                {  10,   3,   6,   9,   2,   7,   1,   5,  11,   0,   4,   8,  -1,  -1,  -1,  -1},
00605                                                                                {   1,   0,   2,   1,   2,   7,   1,   7,  11,   3,   6,  10,  -1,  -1,  -1,  -1},
00606                                                                                {  10,   3,   6,   1,   7,  11,   1,   2,   7,   1,   4,   2,   4,   8,   2,  -1},
00607                                                                                {   9,   2,   7,   6,   4,   1,   6,   1,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00608                                                                                {   0,   1,   3,   8,   0,   3,   6,   8,   3,   7,   9,   2,  -1,  -1,  -1,  -1},
00609                                                                                {   0,   2,   7,   0,   7,   5,   4,   1,   3,   6,   4,   3,  -1,  -1,  -1,  -1},
00610                                                                                {   2,   5,   8,   7,   5,   2,   6,   8,   5,   1,   3,   6,   5,   1,   6,  -1},
00611                                                                                {   6,   4,   5,   6,   5,  11,   6,  11,   3,   7,   9,   2,  -1,  -1,  -1,  -1},
00612                                                                                {   9,   2,   7,   0,   6,   8,   0,   3,   6,   0,   5,   3,   5,  11,   3,  -1},
00613                                                                                {   3,   4,  11,   6,   4,   3,   7,  11,   4,   0,   2,   7,   4,   0,   7,  -1},
00614                                                                                {  11,   3,   8,   8,   3,   6,   8,   2,  11,   2,   7,  11,  -1,  -1,  -1,  -1},
00615                                                                                {   9,   8,  10,   7,   9,  10,   3,   7,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00616                                                                                {   9,   0,   7,   0,   4,   7,   4,   3,   7,   4,  10,   3,  -1,  -1,  -1,  -1},
00617                                                                                {   8,  10,   0,   0,  10,   3,   0,   3,   5,   5,   3,   7,  -1,  -1,  -1,  -1},
00618                                                                                {  10,   5,   4,   3,   5,  10,   5,   3,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00619                                                                                {   9,   8,  10,   7,   9,  10,   3,   7,  10,   1,   5,  11,  -1,  -1,  -1,  -1},
00620                                                                                {   1,   5,  11,   9,   0,   7,   0,   4,   7,   4,   3,   7,   4,  10,   3,  -1},
00621                                                                                {  11,   0,   7,   1,   0,  11,   3,   7,   0,   8,  10,   3,   0,   8,   3,  -1},
00622                                                                                {   7,   1,   4,  11,   1,   7,   4,   3,   7,   4,  10,   3,  -1,  -1,  -1,  -1},
00623                                                                                {   4,   9,   8,   7,   9,   4,   1,   7,   4,   3,   7,   1,  -1,  -1,  -1,  -1},
00624                                                                                {   7,   1,   3,   9,   1,   7,   1,   9,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00625                                                                                {   8,   7,   0,   0,   7,   5,   7,   8,   4,   4,   1,   3,   4,   3,   7,  -1},
00626                                                                                {   5,   1,   3,   7,   5,   3,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00627                                                                                {   3,   4,  11,  11,   4,   5,   4,   3,   7,   7,   9,   8,   7,   8,   4,  -1},
00628                                                                                {   3,   9,   0,   7,   9,   3,   0,  11,   3,   0,   5,  11,  -1,  -1,  -1,  -1},
00629                                                                                {   3,   7,  11,   8,   4,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00630                                                                                {   3,   7,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00631                                                                                {   6,  10,  11,   7,   6,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00632                                                                                {   0,   4,   8,  10,  11,   7,  10,   7,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00633                                                                                {   9,   5,   0,   6,  10,  11,   7,   6,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00634                                                                                {   8,   9,   5,   8,   5,   4,   6,  10,  11,   7,   6,  11,  -1,  -1,  -1,  -1},
00635                                                                                {   5,   7,   6,   5,   6,  10,   5,  10,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00636                                                                                {   5,   7,   6,   5,   6,  10,   5,  10,   1,   4,   8,   0,  -1,  -1,  -1,  -1},
00637                                                                                {   1,   0,  10,  10,   0,   9,  10,   9,   6,   6,   9,   7,  -1,  -1,  -1,  -1},
00638                                                                                {   1,   7,  10,  10,   7,   6,   7,   1,   4,   4,   8,   9,   4,   9,   7,  -1},
00639                                                                                {   7,   6,   4,   7,   4,   1,   7,   1,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00640                                                                                {  11,   0,   1,   8,   0,  11,   7,   8,  11,   6,   8,   7,  -1,  -1,  -1,  -1},
00641                                                                                {   7,   6,   4,   7,   4,   1,   7,   1,  11,   5,   0,   9,  -1,  -1,  -1,  -1},
00642                                                                                {  11,   6,   1,   7,   6,  11,   5,   1,   6,   8,   9,   5,   6,   8,   5,  -1},
00643                                                                                {   4,   5,   7,   4,   7,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00644                                                                                {   5,   7,   0,   0,   7,   8,   6,   8,   7,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00645                                                                                {   7,   6,   9,   9,   6,   0,   4,   0,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00646                                                                                {   8,   9,   7,   8,   7,   6,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00647                                                                                {   8,  10,  11,   2,   8,  11,   7,   2,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00648                                                                                {  10,  11,   4,   4,  11,   7,   4,   7,   0,   0,   7,   2,  -1,  -1,  -1,  -1},
00649                                                                                {   8,  10,  11,   2,   8,  11,   7,   2,  11,   5,   0,   9,  -1,  -1,  -1,  -1},
00650                                                                                {   9,   4,   2,   5,   4,   9,   7,   2,   4,  10,  11,   7,   4,  10,   7,  -1},
00651                                                                                {   1,   8,  10,   2,   8,   1,   5,   2,   1,   7,   2,   5,  -1,  -1,  -1,  -1},
00652                                                                                {   1,   7,  10,   5,   7,   1,   4,  10,   7,   2,   0,   4,   7,   2,   4,  -1},
00653                                                                                {   7,   1,   9,   9,   1,   0,   1,   7,   2,   2,   8,  10,   2,  10,   1,  -1},
00654                                                                                {   7,   2,   9,  10,   1,   4,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00655                                                                                {   8,   4,   2,   4,   1,   2,   1,   7,   2,   1,  11,   7,  -1,  -1,  -1,  -1},
00656                                                                                {  11,   0,   1,   7,   0,  11,   0,   7,   2,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00657                                                                                {   5,   0,   9,   8,   4,   2,   4,   1,   2,   1,   7,   2,   1,  11,   7,  -1},
00658                                                                                {   2,   5,   1,   9,   5,   2,   1,   7,   2,   1,  11,   7,  -1,  -1,  -1,  -1},
00659                                                                                {   4,   5,   8,   8,   5,   2,   7,   2,   5,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00660                                                                                {   7,   2,   0,   5,   7,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00661                                                                                {   7,   2,   4,   4,   2,   8,   4,   0,   7,   0,   9,   7,  -1,  -1,  -1,  -1},
00662                                                                                {   7,   2,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00663                                                                                {  10,  11,   9,   6,  10,   9,   2,   6,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00664                                                                                {  10,  11,   9,   6,  10,   9,   2,   6,   9,   0,   4,   8,  -1,  -1,  -1,  -1},
00665                                                                                {   5,  10,  11,   6,  10,   5,   0,   6,   5,   2,   6,   0,  -1,  -1,  -1,  -1},
00666                                                                                {   2,   5,   8,   8,   5,   4,   5,   2,   6,   6,  10,  11,   6,  11,   5,  -1},
00667                                                                                {  10,   1,   6,   1,   5,   6,   5,   2,   6,   5,   9,   2,  -1,  -1,  -1,  -1},
00668                                                                                {   0,   4,   8,  10,   1,   6,   1,   5,   6,   5,   2,   6,   5,   9,   2,  -1},
00669                                                                                {   1,   0,  10,  10,   0,   6,   2,   6,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00670                                                                                {   2,   6,   1,   1,   6,  10,   1,   4,   2,   4,   8,   2,  -1,  -1,  -1,  -1},
00671                                                                                {  11,   9,   1,   1,   9,   2,   1,   2,   4,   4,   2,   6,  -1,  -1,  -1,  -1},
00672                                                                                {   8,   1,   6,   0,   1,   8,   2,   6,   1,  11,   9,   2,   1,  11,   2,  -1},
00673                                                                                {  11,   6,   1,   1,   6,   4,   6,  11,   5,   5,   0,   2,   5,   2,   6,  -1},
00674                                                                                {   2,   6,   8,  11,   5,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00675                                                                                {   6,   4,   2,   2,   4,   9,   5,   9,   4,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00676                                                                                {   5,   9,   6,   6,   9,   2,   6,   8,   5,   8,   0,   5,  -1,  -1,  -1,  -1},
00677                                                                                {   0,   2,   6,   0,   6,   4,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00678                                                                                {   2,   6,   8,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00679                                                                                {   8,  10,  11,   9,   8,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00680                                                                                {   0,  11,   9,   4,  11,   0,  11,   4,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00681                                                                                {   5,  10,  11,   0,  10,   5,  10,   0,   8,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00682                                                                                {   4,  10,  11,   5,   4,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00683                                                                                {   1,   8,  10,   5,   8,   1,   8,   5,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00684                                                                                {   9,   4,  10,   0,   4,   9,  10,   5,   9,  10,   1,   5,  -1,  -1,  -1,  -1},
00685                                                                                {   0,   8,  10,   1,   0,  10,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00686                                                                                {  10,   1,   4,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00687                                                                                {   4,   9,   8,   1,   9,   4,   9,   1,  11,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00688                                                                                {   1,  11,   9,   0,   1,   9,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00689                                                                                {  11,   0,   8,   5,   0,  11,   8,   1,  11,   8,   4,   1,  -1,  -1,  -1,  -1},
00690                                                                                {  11,   5,   1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00691                                                                                {   5,   9,   8,   4,   5,   8,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00692                                                                                {   9,   0,   5,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00693                                                                                {   8,   4,   0,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1},
00694                                                                                {  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1}
00695     };
00696     const int MarchingCubes::cornerMap[Cube::CORNERS]={0,1,3,2,4,5,7,6};
00697     double MarchingCubes::vertexList[Cube::EDGES][3];
00698 
00699     int MarchingCubes::GetIndex(const double v[Cube::CORNERS],const double& iso){
00700       int idx=0;
00701       if (v[Cube::CornerIndex(0,0,0)] < iso) idx |=   1;
00702       if (v[Cube::CornerIndex(1,0,0)] < iso) idx |=   2;
00703       if (v[Cube::CornerIndex(1,1,0)] < iso) idx |=   4;
00704       if (v[Cube::CornerIndex(0,1,0)] < iso) idx |=   8;
00705       if (v[Cube::CornerIndex(0,0,1)] < iso) idx |=  16;
00706       if (v[Cube::CornerIndex(1,0,1)] < iso) idx |=  32;
00707       if (v[Cube::CornerIndex(1,1,1)] < iso) idx |=  64;
00708       if (v[Cube::CornerIndex(0,1,1)] < iso) idx |= 128;
00709       return idx;
00710     }
00711     int MarchingCubes::GetFaceIndex(const double values[Cube::CORNERS],const double& iso,const int& faceIndex){
00712       int i,j,x,y,z,idx=0;
00713       double v[2][2];
00714       Cube::FactorFaceIndex(faceIndex,x,y,z);
00715       if                (x<0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(0,i,j)];}}}
00716       else if   (x>0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(1,i,j)];}}}
00717       else if   (y<0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(i,0,j)];}}}
00718       else if   (y>0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(i,1,j)];}}}
00719       else if   (z<0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(i,j,0)];}}}
00720       else if   (z>0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(i,j,1)];}}}
00721       if (v[0][0] < iso) idx |=   1;
00722       if (v[1][0] < iso) idx |=   2;
00723       if (v[1][1] < iso) idx |=   4;
00724       if (v[0][1] < iso) idx |=   8;
00725       return idx;
00726     }
00727     int MarchingCubes::IsAmbiguous(const double v[Cube::CORNERS],const double& isoValue,const int& faceIndex){
00728       int idx=GetFaceIndex(v,isoValue,faceIndex);
00729       return (idx==5) || (idx==10);
00730     }
00731     int MarchingCubes::HasRoots(const double v[Cube::CORNERS],const double& isoValue,const int& faceIndex){
00732       int idx=GetFaceIndex(v,isoValue,faceIndex);
00733       return (idx!=0) && (idx !=15);
00734     }
00735     int MarchingCubes::HasRoots(const double v[Cube::CORNERS],const double& isoValue){
00736       int idx=GetIndex(v,isoValue);
00737       if(idx==0 || idx==255){return 0;}
00738       else{return 1;}
00739     }
00740     int MarchingCubes::HasRoots(const int& mcIndex){
00741       if(mcIndex==0 || mcIndex==255){return 0;}
00742       else{return 1;}
00743     }
00744     int MarchingCubes::AddTriangles(const double v[Cube::CORNERS],const double& iso,Triangle* isoTriangles){
00745       int idx,ntriang=0;
00746       Triangle tri;
00747 
00748       idx=GetIndex(v,iso);
00749 
00750       /* Cube is entirely in/out of the surface */
00751       if (!edgeMask[idx]) return 0;
00752 
00753       /* Find the vertices where the surface intersects the cube */
00754       int i,j,ii=1;
00755       for(i=0;i<12;i++){
00756         if(edgeMask[idx] & ii){SetVertex(i,v,iso);}
00757         ii<<=1;
00758       }
00759       /* Create the triangle */
00760       for (i=0;triangles[idx][i]!=-1;i+=3) {
00761         for(j=0;j<3;j++){
00762           tri.p[0][j]=vertexList[triangles[idx][i+0]][j];
00763           tri.p[1][j]=vertexList[triangles[idx][i+1]][j];
00764           tri.p[2][j]=vertexList[triangles[idx][i+2]][j];
00765         }
00766         isoTriangles[ntriang++]=tri;
00767       }
00768       return ntriang;
00769     }
00770 
00771     int MarchingCubes::AddTriangleIndices(const double v[Cube::CORNERS],const double& iso,int* isoIndices){
00772       int idx,ntriang=0;
00773 
00774       idx=GetIndex(v,iso);
00775 
00776       /* Cube is entirely in/out of the surface */
00777       if (!edgeMask[idx]) return 0;
00778 
00779       /* Create the triangle */
00780       for(int i=0;triangles[idx][i]!=-1;i+=3){
00781         for(int j=0;j<3;j++){isoIndices[i+j]=triangles[idx][i+j];}
00782         ntriang++;
00783       }
00784       return ntriang;
00785     }
00786 
00787     void MarchingCubes::SetVertex(const int& e,const double values[Cube::CORNERS],const double& iso){
00788       double t;
00789       switch(e){
00790         case 0:
00791           t=Interpolate(values[Cube::CornerIndex(0,0,0)]-iso,values[Cube::CornerIndex(1,0,0)]-iso);
00792           vertexList[e][0]=t;                   vertexList[e][1]=0.0;           vertexList[e][2]=0.0;
00793           break;
00794         case 1:
00795           t=Interpolate(values[Cube::CornerIndex(1,0,0)]-iso,values[Cube::CornerIndex(1,1,0)]-iso);
00796           vertexList[e][0]=1.0;         vertexList[e][1]=t;                     vertexList[e][2]=0.0;
00797           break;
00798         case 2:
00799           t=Interpolate(values[Cube::CornerIndex(1,1,0)]-iso,values[Cube::CornerIndex(0,1,0)]-iso);
00800           vertexList[e][0]=(1.0-t);     vertexList[e][1]=1.0;           vertexList[e][2]=0.0;
00801           break;
00802         case 3:
00803           t=Interpolate(values[Cube::CornerIndex(0,1,0)]-iso,values[Cube::CornerIndex(0,0,0)]-iso);
00804           vertexList[e][0]=0.0;         vertexList[e][1]=(1.0-t);       vertexList[e][2]=0.0;
00805           break;
00806         case 4:
00807           t=Interpolate(values[Cube::CornerIndex(0,0,1)]-iso,values[Cube::CornerIndex(1,0,1)]-iso);
00808           vertexList[e][0]=t;                   vertexList[e][1]=0.0;           vertexList[e][2]=1.0;
00809           break;
00810         case 5:
00811           t=Interpolate(values[Cube::CornerIndex(1,0,1)]-iso,values[Cube::CornerIndex(1,1,1)]-iso);
00812           vertexList[e][0]=1.0;         vertexList[e][1]=t;                     vertexList[e][2]=1.0;
00813           break;
00814         case 6:
00815           t=Interpolate(values[Cube::CornerIndex(1,1,1)]-iso,values[Cube::CornerIndex(0,1,1)]-iso);
00816           vertexList[e][0]=(1.0-t);     vertexList[e][1]=1.0;           vertexList[e][2]=1.0;
00817           break;
00818         case 7:
00819           t=Interpolate(values[Cube::CornerIndex(0,1,1)]-iso,values[Cube::CornerIndex(0,0,1)]-iso);
00820           vertexList[e][0]=0.0;         vertexList[e][1]=(1.0-t);       vertexList[e][2]=1.0;
00821           break;
00822         case 8:
00823           t=Interpolate(values[Cube::CornerIndex(0,0,0)]-iso,values[Cube::CornerIndex(0,0,1)]-iso);
00824           vertexList[e][0]=0.0;         vertexList[e][1]=0.0;           vertexList[e][2]=t;
00825           break;
00826         case 9:
00827           t=Interpolate(values[Cube::CornerIndex(1,0,0)]-iso,values[Cube::CornerIndex(1,0,1)]-iso);
00828           vertexList[e][0]=1.0;         vertexList[e][1]=0.0;           vertexList[e][2]=t;
00829           break;
00830         case 10:
00831           t=Interpolate(values[Cube::CornerIndex(1,1,0)]-iso,values[Cube::CornerIndex(1,1,1)]-iso);
00832           vertexList[e][0]=1.0;         vertexList[e][1]=1.0;           vertexList[e][2]=t;
00833           break;
00834         case 11:
00835           t=Interpolate(values[Cube::CornerIndex(0,1,0)]-iso,values[Cube::CornerIndex(0,1,1)]-iso);
00836           vertexList[e][0]=0.0;         vertexList[e][1]=1.0;           vertexList[e][2]=t;
00837           break;
00838       };
00839     }
00840     double MarchingCubes::Interpolate(const double& v1,const double& v2){return v1/(v1-v2);}
00841 
00842 
00844     int MarchingCubes::GetIndex(const float v[Cube::CORNERS],const float& iso){
00845       int idx=0;
00846       if (v[Cube::CornerIndex(0,0,0)] < iso) idx |=   1;
00847       if (v[Cube::CornerIndex(1,0,0)] < iso) idx |=   2;
00848       if (v[Cube::CornerIndex(1,1,0)] < iso) idx |=   4;
00849       if (v[Cube::CornerIndex(0,1,0)] < iso) idx |=   8;
00850       if (v[Cube::CornerIndex(0,0,1)] < iso) idx |=  16;
00851       if (v[Cube::CornerIndex(1,0,1)] < iso) idx |=  32;
00852       if (v[Cube::CornerIndex(1,1,1)] < iso) idx |=  64;
00853       if (v[Cube::CornerIndex(0,1,1)] < iso) idx |= 128;
00854       return idx;
00855     }
00856     int MarchingCubes::GetFaceIndex(const float values[Cube::CORNERS],const float& iso,const int& faceIndex){
00857       int i,j,x,y,z,idx=0;
00858       double v[2][2];
00859       Cube::FactorFaceIndex(faceIndex,x,y,z);
00860       if                (x<0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(0,i,j)];}}}
00861       else if   (x>0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(1,i,j)];}}}
00862       else if   (y<0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(i,0,j)];}}}
00863       else if   (y>0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(i,1,j)];}}}
00864       else if   (z<0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(i,j,0)];}}}
00865       else if   (z>0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=values[Cube::CornerIndex(i,j,1)];}}}
00866       if (v[0][0] < iso) idx |=   1;
00867       if (v[1][0] < iso) idx |=   2;
00868       if (v[1][1] < iso) idx |=   4;
00869       if (v[0][1] < iso) idx |=   8;
00870       return idx;
00871     }
00872     int MarchingCubes::GetFaceIndex(const int& mcIndex,const int& faceIndex){
00873       int i,j,x,y,z,idx=0;
00874       int v[2][2];
00875       Cube::FactorFaceIndex(faceIndex,x,y,z);
00876       if                (x<0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=mcIndex&(1<<MarchingCubes::cornerMap[Cube::CornerIndex(0,i,j)]);}}}
00877       else if   (x>0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=mcIndex&(1<<MarchingCubes::cornerMap[Cube::CornerIndex(1,i,j)]);}}}
00878       else if   (y<0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=mcIndex&(1<<MarchingCubes::cornerMap[Cube::CornerIndex(i,0,j)]);}}}
00879       else if   (y>0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=mcIndex&(1<<MarchingCubes::cornerMap[Cube::CornerIndex(i,1,j)]);}}}
00880       else if   (z<0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=mcIndex&(1<<MarchingCubes::cornerMap[Cube::CornerIndex(i,j,1)]);}}}
00881       else if   (z>0){for(i=0;i<2;i++){for(j=0;j<2;j++){v[i][j]=mcIndex&(1<<MarchingCubes::cornerMap[Cube::CornerIndex(i,j,1)]);}}}
00882       if (v[0][0]) idx |=   1;
00883       if (v[1][0]) idx |=   2;
00884       if (v[1][1]) idx |=   4;
00885       if (v[0][1]) idx |=   8;
00886       return idx;
00887     }
00888     int MarchingCubes::IsAmbiguous(const float v[Cube::CORNERS],const float& isoValue,const int& faceIndex){
00889       int idx=GetFaceIndex(v,isoValue,faceIndex);
00890       return (idx==5) || (idx==10);
00891     }
00892     int MarchingCubes::IsAmbiguous(const int& mcIndex,const int& faceIndex){
00893       int idx=GetFaceIndex(mcIndex,faceIndex);
00894       return (idx==5) || (idx==10);
00895     }
00896     int MarchingCubes::HasRoots(const float v[Cube::CORNERS],const float& isoValue){
00897       int idx=GetIndex(v,isoValue);
00898       if(idx==0 || idx==255){return 0;}
00899       else{return 1;}
00900     }
00901     int MarchingCubes::HasRoots(const float v[Cube::CORNERS],const float& isoValue,const int& faceIndex){
00902       int idx=GetFaceIndex(v,isoValue,faceIndex);
00903       return (idx!=0) && (idx!=15);
00904     }
00905     int MarchingCubes::HasFaceRoots(const int& mcIndex,const int& faceIndex){
00906       int idx=GetFaceIndex(mcIndex,faceIndex);
00907       return (idx!=0) && (idx!=15);
00908     }
00909     int MarchingCubes::HasEdgeRoots(const int& mcIndex,const int& edgeIndex){
00910       int c1,c2;
00911       Cube::EdgeCorners(edgeIndex,c1,c2);
00912       if(       ( (mcIndex&(1<<MarchingCubes::cornerMap[c1])) &&  (mcIndex&(1<<MarchingCubes::cornerMap[c2]))) ||
00913           (!(mcIndex&(1<<MarchingCubes::cornerMap[c1])) && !(mcIndex&(1<<MarchingCubes::cornerMap[c2])))){return 0;}
00914       else{return 1;}
00915     }
00916     int MarchingCubes::AddTriangles(const float v[Cube::CORNERS],const float& iso,Triangle* isoTriangles){
00917       int idx,ntriang=0;
00918       Triangle tri;
00919 
00920       idx=GetIndex(v,iso);
00921 
00922       /* Cube is entirely in/out of the surface */
00923       if (!edgeMask[idx]) return 0;
00924 
00925       /* Find the vertices where the surface intersects the cube */
00926       int i,j,ii=1;
00927       for(i=0;i<12;i++){
00928         if(edgeMask[idx] & ii){SetVertex(i,v,iso);}
00929         ii<<=1;
00930       }
00931       /* Create the triangle */
00932       for (i=0;triangles[idx][i]!=-1;i+=3) {
00933         for(j=0;j<3;j++){
00934           tri.p[0][j]=vertexList[triangles[idx][i+0]][j];
00935           tri.p[1][j]=vertexList[triangles[idx][i+1]][j];
00936           tri.p[2][j]=vertexList[triangles[idx][i+2]][j];
00937         }
00938         isoTriangles[ntriang++]=tri;
00939       }
00940       return ntriang;
00941     }
00942 
00943     int MarchingCubes::AddTriangleIndices(const float v[Cube::CORNERS],const float& iso,int* isoIndices){
00944       int idx,ntriang=0;
00945       idx=GetIndex(v,iso);
00946       /* Cube is entirely in/out of the surface */
00947       if (!edgeMask[idx]) return 0;
00948       /* Create the triangle */
00949       for(int i=0;triangles[idx][i]!=-1;i+=3){
00950         for(int j=0;j<3;j++){isoIndices[i+j]=triangles[idx][i+j];}
00951         ntriang++;
00952       }
00953       return ntriang;
00954     }
00955     int MarchingCubes::AddTriangleIndices(const int& idx,int* isoIndices){
00956       int ntriang=0;
00957 
00958       /* Cube is entirely in/out of the surface */
00959       if (!edgeMask[idx]) return 0;
00960 
00961       /* Create the triangle */
00962       for(int i=0;triangles[idx][i]!=-1;i+=3){
00963         for(int j=0;j<3;j++){isoIndices[i+j]=triangles[idx][i+j];}
00964         ntriang++;
00965       }
00966       return ntriang;
00967     }
00968 
00969     void MarchingCubes::SetVertex(const int& e,const float values[Cube::CORNERS],const float& iso){
00970       double t;
00971       switch(e){
00972         case 0:
00973           t=Interpolate(values[Cube::CornerIndex(0,0,0)]-iso,values[Cube::CornerIndex(1,0,0)]-iso);
00974           vertexList[e][0]=t;                   vertexList[e][1]=0.0;           vertexList[e][2]=0.0;
00975           break;
00976         case 1:
00977           t=Interpolate(values[Cube::CornerIndex(1,0,0)]-iso,values[Cube::CornerIndex(1,1,0)]-iso);
00978           vertexList[e][0]=1.0;         vertexList[e][1]=t;                     vertexList[e][2]=0.0;
00979           break;
00980         case 2:
00981           t=Interpolate(values[Cube::CornerIndex(1,1,0)]-iso,values[Cube::CornerIndex(0,1,0)]-iso);
00982           vertexList[e][0]=(1.0-t);     vertexList[e][1]=1.0;           vertexList[e][2]=0.0;
00983           break;
00984         case 3:
00985           t=Interpolate(values[Cube::CornerIndex(0,1,0)]-iso,values[Cube::CornerIndex(0,0,0)]-iso);
00986           vertexList[e][0]=0.0;         vertexList[e][1]=(1.0-t);       vertexList[e][2]=0.0;
00987           break;
00988         case 4:
00989           t=Interpolate(values[Cube::CornerIndex(0,0,1)]-iso,values[Cube::CornerIndex(1,0,1)]-iso);
00990           vertexList[e][0]=t;                   vertexList[e][1]=0.0;           vertexList[e][2]=1.0;
00991           break;
00992         case 5:
00993           t=Interpolate(values[Cube::CornerIndex(1,0,1)]-iso,values[Cube::CornerIndex(1,1,1)]-iso);
00994           vertexList[e][0]=1.0;         vertexList[e][1]=t;                     vertexList[e][2]=1.0;
00995           break;
00996         case 6:
00997           t=Interpolate(values[Cube::CornerIndex(1,1,1)]-iso,values[Cube::CornerIndex(0,1,1)]-iso);
00998           vertexList[e][0]=(1.0-t);     vertexList[e][1]=1.0;           vertexList[e][2]=1.0;
00999           break;
01000         case 7:
01001           t=Interpolate(values[Cube::CornerIndex(0,1,1)]-iso,values[Cube::CornerIndex(0,0,1)]-iso);
01002           vertexList[e][0]=0.0;         vertexList[e][1]=(1.0-t);       vertexList[e][2]=1.0;
01003           break;
01004         case 8:
01005           t=Interpolate(values[Cube::CornerIndex(0,0,0)]-iso,values[Cube::CornerIndex(0,0,1)]-iso);
01006           vertexList[e][0]=0.0;         vertexList[e][1]=0.0;           vertexList[e][2]=t;
01007           break;
01008         case 9:
01009           t=Interpolate(values[Cube::CornerIndex(1,0,0)]-iso,values[Cube::CornerIndex(1,0,1)]-iso);
01010           vertexList[e][0]=1.0;         vertexList[e][1]=0.0;           vertexList[e][2]=t;
01011           break;
01012         case 10:
01013           t=Interpolate(values[Cube::CornerIndex(1,1,0)]-iso,values[Cube::CornerIndex(1,1,1)]-iso);
01014           vertexList[e][0]=1.0;         vertexList[e][1]=1.0;           vertexList[e][2]=t;
01015           break;
01016         case 11:
01017           t=Interpolate(values[Cube::CornerIndex(0,1,0)]-iso,values[Cube::CornerIndex(0,1,1)]-iso);
01018           vertexList[e][0]=0.0;         vertexList[e][1]=1.0;           vertexList[e][2]=t;
01019           break;
01020       };
01021     }
01022     float MarchingCubes::Interpolate(const float& v1,const float& v2){return v1/(v1-v2);}
01023 
01024 
01025   }
01026 }

pcl
Author(s): Open Perception
autogenerated on Mon Oct 6 2014 03:15:39