Visualization Library v1.0.3A lightweight C++ OpenGL middleware for 2D/3D graphics |
[Download] [Tutorials] [All Classes] [Grouped Classes] |
00001 /**************************************************************************************/ 00002 /* */ 00003 /* Visualization Library */ 00004 /* http://visualizationlibrary.org */ 00005 /* */ 00006 /* Copyright (c) 2005-2010, Michele Bosi */ 00007 /* All rights reserved. */ 00008 /* */ 00009 /* Redistribution and use in source and binary forms, with or without modification, */ 00010 /* are permitted provided that the following conditions are met: */ 00011 /* */ 00012 /* - Redistributions of source code must retain the above copyright notice, this */ 00013 /* list of conditions and the following disclaimer. */ 00014 /* */ 00015 /* - Redistributions in binary form must reproduce the above copyright notice, this */ 00016 /* list of conditions and the following disclaimer in the documentation and/or */ 00017 /* other materials provided with the distribution. */ 00018 /* */ 00019 /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND */ 00020 /* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED */ 00021 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE */ 00022 /* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR */ 00023 /* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES */ 00024 /* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; */ 00025 /* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON */ 00026 /* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT */ 00027 /* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS */ 00028 /* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ 00029 /* */ 00030 /**************************************************************************************/ 00031 00032 /* The marching cubes tables are from Cory Bloyd. */ 00033 00034 #include <vlVolume/MarchingCubes.hpp> 00035 #include <vlCore/Time.hpp> 00036 #include <vlGraphics/DoubleVertexRemover.hpp> 00037 00038 using namespace vl; 00039 00059 //------------------------------------------------------------------------------ 00060 MarchingCubes::MarchingCubes() 00061 { 00062 mVertsArray = new ArrayFloat3; 00063 mNormsArray = new ArrayFloat3; 00064 mColorArray = new ArrayFloat4; 00065 00066 // OpenGL ES does not support DrawElementsUInt 00067 #if defined(VL_OPENGL) 00068 mDrawElements = new DrawElementsUInt(PT_TRIANGLES); 00069 #else 00070 mDrawElements = new DrawElementsUShort(PT_TRIANGLES); 00071 #endif 00072 mVolumeInfo.setAutomaticDelete(false); 00073 mHighQualityNormals = true; 00074 } 00075 //------------------------------------------------------------------------------ 00076 // MarchingCubes 00077 //------------------------------------------------------------------------------ 00078 void MarchingCubes::computeEdges(Volume* vol, float threshold) 00079 { 00080 // mEdges.clear(); 00081 mEdges.resize(vol->slices().x() * vol->slices().y() * vol->slices().z()); 00082 mCubes.clear(); 00083 mCubes.reserve(1024); 00084 00086 // note: this funtion can generate double vertices when the 't' is 0.0 or 1.0 00087 // this is why Geometry::computeNormals() doesn't work well with MarchingCubes 00088 // If we find a way not to generate such vertices quickly we could use always 00089 // Geometry::computeNormals() which is much quicker than computing the gradient. 00091 00092 const float dx = vol->cellSize().x() * 0.25f; 00093 const float dy = vol->cellSize().y() * 0.25f; 00094 const float dz = vol->cellSize().z() * 0.25f; 00095 float v0, v1, v2, v3, t; 00096 int iedge = 0; 00097 int w = vol->slices().x() -1; 00098 int h = vol->slices().y() -1; 00099 int d = vol->slices().z() -1; 00100 for(unsigned short z = 0; z < vol->slices().z(); ++z) 00101 { 00102 for(unsigned short y = 0; y < vol->slices().y(); ++y) 00103 { 00104 for(unsigned short x = 0; x < vol->slices().x(); ++x, ++iedge) 00105 { 00106 if (x != w && y != h && z != d) 00107 { 00108 if (vol->cube(x,y,z).includes(threshold)) 00109 { 00110 if (mCubes.capacity()-mCubes.size() == 0) 00111 mCubes.reserve(mCubes.size()*2); 00112 mCubes.push_back( usvec3(x,y,z) ); 00113 } 00114 else 00115 continue; 00116 } 00117 00118 if (mVerts.capacity() - mVerts.size() == 0) 00119 { 00120 mVerts.reserve( mVerts.size() * 2 ); 00121 mNorms.reserve( mNorms.size() * 2 ); 00122 } 00123 00124 v0 = vol->value( x,y,z ); 00125 fvec3 v0_coord = vol->coordinate(x, y, z); 00126 00127 if (x != w) 00128 { 00129 v1 = vol->value( x + 1, y, z ); 00130 if (v1!=v0) 00131 { 00132 //if (t>=0 && t<=1.0f) 00133 if ( (threshold>=v0 && threshold<=v1) || (threshold>=v1 && threshold<=v0) ) 00134 { 00135 t = (threshold-v0)/(v1-v0); 00136 VL_CHECK(t>=-0.001f && t<=1.001f) 00137 // emit vertex 00138 mEdges[iedge].mX = (int)mVerts.size(); 00139 // compute vertex and normal position 00140 mVerts.push_back( v0_coord * (1.0f-t) + vol->coordinate(x + 1, y, z) * t ); 00141 if (mHighQualityNormals) 00142 { 00143 fvec3 n; 00144 vol->normalHQ(n, mVerts.back(), dx, dy, dz); 00145 mNorms.push_back(n); 00146 } 00147 } 00148 } 00149 } 00150 if (y != h) 00151 { 00152 v2 = vol->value( x, y + 1, z ); 00153 if (v2!=v0) 00154 { 00155 //if (t>=0 && t<=1.0f) 00156 if ( (threshold>=v0 && threshold<=v2) || (threshold>=v2 && threshold<=v0) ) 00157 { 00158 t = (threshold-v0)/(v2-v0); 00159 VL_CHECK(t>=-0.001f && t<=1.001f) 00160 // emit vertex 00161 mEdges[iedge].mY = (int)mVerts.size(); 00162 // compute vertex and normal position 00163 mVerts.push_back( v0_coord * (1.0f-t) + vol->coordinate(x, y + 1, z) * t ); 00164 if (mHighQualityNormals) 00165 { 00166 fvec3 n; 00167 vol->normalHQ(n, mVerts.back(), dx, dy, dz); 00168 mNorms.push_back(n); 00169 } 00170 } 00171 } 00172 } 00173 if (z != d) 00174 { 00175 v3 = vol->value( x, y, z + 1 ); 00176 if (v3!=v0) 00177 { 00178 //if (t>=0 && t<=1.0f) 00179 if ( (threshold>=v0 && threshold<=v3) || (threshold>=v3 && threshold<=v0) ) 00180 { 00181 t = (threshold-v0)/(v3-v0); 00182 VL_CHECK(t>=-0.001f && t<=1.001f) 00183 // emit vertex 00184 mEdges[iedge].mZ = (int)mVerts.size(); 00185 // compute vertex and normal position 00186 mVerts.push_back( v0_coord * (1.0f-t) + vol->coordinate(x, y, z + 1) * t ); 00187 if (mHighQualityNormals) 00188 { 00189 fvec3 n; 00190 vol->normalHQ(n, mVerts.back(), dx, dy, dz); 00191 mNorms.push_back(n); 00192 } 00193 } 00194 } 00195 } 00196 } 00197 } 00198 } 00199 } 00200 //------------------------------------------------------------------------------ 00201 void MarchingCubes::processCube(int x, int y, int z, Volume* vol, float threshold) 00202 { 00203 int inner_corners = 0; 00204 00205 if ( vol->value( x, y, z ) < threshold ) inner_corners += 1; 00206 if ( vol->value( x + 1, y, z ) < threshold ) inner_corners += 2; 00207 if ( vol->value( x + 1, y + 1, z ) < threshold ) inner_corners += 4; 00208 if ( vol->value( x, y + 1, z ) < threshold ) inner_corners += 8; 00209 if ( vol->value( x, y, z + 1 ) < threshold ) inner_corners += 16; 00210 if ( vol->value( x + 1, y, z + 1 ) < threshold ) inner_corners += 32; 00211 if ( vol->value( x + 1, y + 1, z + 1 ) < threshold ) inner_corners += 64; 00212 if ( vol->value( x, y + 1, z + 1 ) < threshold ) inner_corners += 128; 00213 00214 int cut_edges = mCubeEdgeFlags[inner_corners]; 00215 00216 if(cut_edges == 0) 00217 return; 00218 00219 /* 00220 int cell0 = x + y * vol->slices().x() + z * vol->slices().x()*vol->slices().y(); 00221 int cell1 = (x+1) + y * vol->slices().x() + z * vol->slices().x()*vol->slices().y(); 00222 int cell2 = (x+1) + y * vol->slices().x() + (z+1) * vol->slices().x()*vol->slices().y(); 00223 int cell3 = x + y * vol->slices().x() + (z+1) * vol->slices().x()*vol->slices().y(); 00224 int cell4 = (x+1) + (y+1) * vol->slices().x() + z * vol->slices().x()*vol->slices().y(); 00225 int cell5 = x + (y+1) * vol->slices().x() + z * vol->slices().x()*vol->slices().y(); 00226 int cell6 = x + (y+1) * vol->slices().x() + (z+1) * vol->slices().x()*vol->slices().y(); 00227 */ 00228 00229 int z0 = z * vol->slices().x()*vol->slices().y(); 00230 int z1 = (z+1) * vol->slices().x()*vol->slices().y(); 00231 int y0 = y * vol->slices().x(); 00232 int y1 = (y+1) * vol->slices().x(); 00233 00234 int cell0 = x + y0 + z0; 00235 int cell1 = (x+1) + y0 + z0; 00236 int cell2 = (x+1) + y0 + z1; 00237 int cell3 = x + y0 + z1; 00238 int cell4 = (x+1) + y1 + z0; 00239 int cell5 = x + y1 + z0; 00240 int cell6 = x + y1 + z1; 00241 00242 int edge_ivert[12] = 00243 { 00244 mEdges[cell0].mX, 00245 mEdges[cell1].mY, 00246 mEdges[cell5].mX, 00247 mEdges[cell0].mY, 00248 00249 mEdges[cell3].mX, 00250 mEdges[cell2].mY, 00251 mEdges[cell6].mX, 00252 mEdges[cell3].mY, 00253 00254 mEdges[cell0].mZ, 00255 mEdges[cell1].mZ, 00256 mEdges[cell4].mZ, 00257 mEdges[cell5].mZ, 00258 }; 00259 00260 int ivertex; 00261 for(int icorner = 0; mTriangleConnectionTable[inner_corners][icorner]>=0; icorner+=3) 00262 { 00263 if (mIndices.capacity() - mIndices.size() == 0) 00264 mIndices.reserve( mIndices.size()*2 ); 00265 00266 ivertex = mTriangleConnectionTable[inner_corners][icorner+0]; 00267 int a = edge_ivert[ivertex]; 00268 00269 ivertex = mTriangleConnectionTable[inner_corners][icorner+1]; 00270 int b = edge_ivert[ivertex]; 00271 00272 ivertex = mTriangleConnectionTable[inner_corners][icorner+2]; 00273 int c = edge_ivert[ivertex]; 00274 00275 if (a<0 || b<0 || c<0) 00276 continue; 00277 00278 // skip degenerate tris #1 00279 if (a==b||b==c||c==a) 00280 continue; 00281 00282 #if 0 00283 // skip degenerate tris #2 00284 fvec3 v0 = mVerts[a]; 00285 fvec3 v1 = mVerts[b] - v0; 00286 fvec3 v2 = mVerts[c] - v1; 00287 if (cross(v2,v1).isNull()) 00288 continue; 00289 #endif 00290 00291 mIndices.push_back((IndexType)a); 00292 mIndices.push_back((IndexType)b); 00293 mIndices.push_back((IndexType)c); 00294 } 00295 } 00296 //------------------------------------------------------------------------------ 00297 void MarchingCubes::reset() 00298 { 00299 mVertsArray->clear(); 00300 mNormsArray->clear(); 00301 mColorArray->clear(); 00302 mDrawElements->indexBuffer()->clear(); 00303 mIndices.clear(); 00304 mVerts.clear(); 00305 mNorms.clear(); 00306 mColors.clear(); 00307 mCubes.clear(); 00308 mEdges.clear(); 00309 mVolumeInfo.clear(); 00310 } 00311 //------------------------------------------------------------------------------ 00312 void MarchingCubes::run(bool generate_colors) 00313 { 00314 mVerts.clear(); 00315 mNorms.clear(); 00316 mIndices.clear(); 00317 mVerts.reserve(1024); 00318 mNorms.reserve(1024); 00319 mColors.reserve(1024); 00320 mIndices.reserve(1024); 00321 00322 /*Time time; time.start();*/ 00323 00324 for(int ivol=0; ivol<mVolumeInfo.size(); ++ivol) 00325 { 00326 Volume* vol = mVolumeInfo.at(ivol)->volume(); 00327 float threshold = mVolumeInfo.at(ivol)->threshold(); 00328 int start = (int)mVerts.size(); 00329 00330 if (vol->dataIsDirty()) 00331 vol->setupInternalData(); 00332 00333 // note: this function takes the 90% of the time 00334 computeEdges(vol, threshold); 00335 00336 // note: this loop takes the remaining 10% of the time 00338 //for(int z = 0; z < mVolume->slices().z()-1; ++z) 00339 // for(int y = 0; y < mVolume->slices().y()-1; ++y) 00340 // for(int x = 0; x < mVolume->slices().x()-1; ++x) 00341 // if(vol->cube(x,y,z).includes(threshold)) 00342 // processCube(x, y, z, vol, threshold); 00343 00344 for(unsigned int i=0; i<mCubes.size(); ++i) 00345 processCube(mCubes[i].x(), mCubes[i].y(), mCubes[i].z(), vol, threshold); 00346 00347 int count = (int)mVerts.size() - start; 00348 mVolumeInfo.at(ivol)->setVert0(start); 00349 mVolumeInfo.at(ivol)->setVertC(count); 00350 00351 // fill color array 00352 if (generate_colors) 00353 { 00354 mColors.resize( mVerts.size() ); 00355 for(int i=start; i<start+count; ++i) 00356 mColors[i] = mVolumeInfo.at(ivol)->color(); 00357 } 00358 } 00359 00360 mVertsArray->resize(mVerts.size()); 00361 mVertsArray->setBufferObjectDirty(); 00362 if (mVerts.size()) 00363 memcpy(mVertsArray->ptr(), &mVerts[0], sizeof(mVerts[0]) * mVerts.size()); 00364 00365 mNormsArray->resize(mNorms.size()); 00366 mNormsArray->setBufferObjectDirty(); 00367 if (mNorms.size()) 00368 memcpy(mNormsArray->ptr(), &mNorms[0], sizeof(mNorms[0]) * mNorms.size()); 00369 00370 if (generate_colors) 00371 { 00372 mColorArray->resize(mColors.size()); 00373 mColorArray->setBufferObjectDirty(); 00374 if (mColors.size()) 00375 memcpy(mColorArray->ptr(), &mColors[0], sizeof(mColors[0]) * mColors.size()); 00376 } 00377 else 00378 mColorArray->clear(); 00379 00380 mDrawElements->indexBuffer()->resize(mIndices.size()); 00381 mDrawElements->indexBuffer()->setBufferObjectDirty(true); 00382 if (mIndices.size()) 00383 memcpy(mDrawElements->indexBuffer()->ptr(), &mIndices[0], sizeof(mIndices[0]) * mIndices.size()); 00384 00385 if (!mHighQualityNormals) 00386 { 00387 ref<Geometry> geom = new Geometry; 00388 geom->setVertexArray(mVertsArray.get()); 00389 geom->drawCalls()->push_back(mDrawElements.get()); 00390 00391 geom->computeNormals(); 00392 mNormsArray->resize( geom->normalArray()->size() ); 00393 mNormsArray->setBufferObjectDirty(); 00394 memcpy(mNormsArray->ptr(), geom->normalArray()->ptr(), sizeof(mNormsArray->at(0)) * mNormsArray->size()); 00395 } 00396 } 00397 //------------------------------------------------------------------------------ 00398 void MarchingCubes::updateColor(const fvec3& color, int volume_index) 00399 { 00400 if(volume_index>=mVolumeInfo.size()) 00401 { 00402 Log::error( Say("updateColor() volume index (%n) out of range.\n") << volume_index); 00403 return; 00404 } 00405 int start = mVolumeInfo.at(volume_index)->vert0(); 00406 int count = mVolumeInfo.at(volume_index)->vertC(); 00407 if (start+count > (int)mColorArray->size()) 00408 { 00409 Log::error("updateColor() color array not preset.\n"); 00410 return; 00411 } 00412 for(int i=start; i<start+count; ++i) 00413 { 00414 mColorArray->at(i).r() = color.r(); 00415 mColorArray->at(i).g() = color.g(); 00416 mColorArray->at(i).b() = color.b(); 00417 } 00418 } 00419 //------------------------------------------------------------------------------ 00420 void MarchingCubes::updateColor(const fvec4& color, int volume_index) 00421 { 00422 if(volume_index>=mVolumeInfo.size()) 00423 { 00424 Log::error( Say("updateColor() volume index (%n) out of range.\n") << volume_index); 00425 return; 00426 } 00427 int start = mVolumeInfo.at(volume_index)->vert0(); 00428 int count = mVolumeInfo.at(volume_index)->vertC(); 00429 if (start+count > (int)mColorArray->size()) 00430 { 00431 Log::error("updateColor() color array not preset.\n"); 00432 return; 00433 } 00434 for(int i=start; i<start+count; ++i) 00435 mColorArray->at(i) = color; 00436 } 00437 //------------------------------------------------------------------------------ 00438 void MarchingCubes::updateAlpha(float alpha, int volume_index) 00439 { 00440 if(volume_index>=mVolumeInfo.size()) 00441 { 00442 Log::error( Say("updateColor() volume index (%n) out of range.\n") << volume_index); 00443 return; 00444 } 00445 int start = mVolumeInfo.at(volume_index)->vert0(); 00446 int count = mVolumeInfo.at(volume_index)->vertC(); 00447 if (start+count > (int)mColorArray->size()) 00448 { 00449 Log::error("updateColor() color array not preset.\n"); 00450 return; 00451 } 00452 for(int i=start; i<start+count; ++i) 00453 mColorArray->at(i).a() = alpha; 00454 } 00455 //------------------------------------------------------------------------------ 00456 // Volume 00457 //------------------------------------------------------------------------------ 00458 Volume::Volume() 00459 { 00460 VL_DEBUG_SET_OBJECT_NAME() 00461 setup(NULL, false, false, fvec3(0,0,0), fvec3(1.0f,1.0f,1.0f), ivec3(50,50,50)); 00462 } 00463 //------------------------------------------------------------------------------ 00464 ref<Volume> Volume::downsample() const 00465 { 00466 ref<Volume> vol = new Volume; 00467 int w = mSlices.x() / 2; 00468 int h = mSlices.y() / 2; 00469 int d = mSlices.z() / 2; 00470 if (w<1) w = 1; 00471 if (h<1) h = 1; 00472 if (d<1) d = 1; 00473 00474 vol->setup(NULL, false, false, bottomLeft(), topRight(), ivec3(w,h,d)); 00475 00476 for(int z=0; z<d; ++z) 00477 { 00478 int z1=z*2; 00479 int z2=z*2+1; 00480 for(int y=0; y<h; ++y) 00481 { 00482 int y1=y*2; 00483 int y2=y*2+1; 00484 for(int x=0; x<w; ++x) 00485 { 00486 int x1 = x*2; 00487 int x2 = x*2+1; 00488 float v0 = value(x1,y1,z1); 00489 float v1 = value(x1,y1,z2); 00490 float v2 = value(x1,y2,z1); 00491 float v3 = value(x1,y2,z2); 00492 float v4 = value(x2,y1,z1); 00493 float v5 = value(x2,y1,z2); 00494 float v6 = value(x2,y2,z1); 00495 float v7 = value(x2,y2,z2); 00496 vol->value(x,y,z) = (v0+v1+v2+v3+v4+v5+v6+v7) * (1.0f/8.0f); 00497 } 00498 } 00499 } 00500 00501 return vol; 00502 } 00503 //------------------------------------------------------------------------------ 00504 void Volume::setupInternalData() 00505 { 00506 mDataIsDirty = false; 00507 int w = slices().x() -1; 00508 int h = slices().y() -1; 00509 int d = slices().z() -1; 00510 mCubes.resize(w*h*d); 00511 for(int z = 0; z < d; ++z) 00512 { 00513 for(int y = 0; y < h; ++y) 00514 { 00515 for(int x = 0; x < w; ++x) 00516 { 00517 float v[] = 00518 { 00519 value(x+0,y+0,z+0), 00520 value(x+0,y+0,z+1), 00521 value(x+0,y+1,z+0), 00522 value(x+0,y+1,z+1), 00523 value(x+1,y+0,z+0), 00524 value(x+1,y+0,z+1), 00525 value(x+1,y+1,z+0), 00526 value(x+1,y+1,z+1) 00527 }; 00528 int icube = x+w*y+w*h*z; 00529 mCubes[icube].mMin = v[0]; 00530 mCubes[icube].mMax = v[0]; 00531 for(int i=1; i<8; ++i) 00532 { 00533 if (mCubes[icube].mMin > v[i]) mCubes[icube].mMin = v[i]; 00534 if (mCubes[icube].mMax < v[i]) mCubes[icube].mMax = v[i]; 00535 } 00536 } 00537 } 00538 } 00539 } 00540 //------------------------------------------------------------------------------ 00541 void Volume::setup( float* data, bool use_directly, bool copy_data, const fvec3& bottom_left, const fvec3& top_right, const ivec3& slices ) 00542 { 00543 fvec3 size = top_right-bottom_left; 00544 00545 if (use_directly) 00546 { 00547 VL_CHECK(data); 00548 // discard internal data. 00549 std::vector<float>().swap( mInternalValues ); 00550 mValues = data; 00551 } 00552 else 00553 { 00554 // allocate internal data & copy 00555 mInternalValues.resize( slices.x() * slices.y() * slices.z() ); 00556 mValues = &mInternalValues[0]; 00557 if (copy_data) 00558 memcpy( mValues, data, slices.x() * slices.y() * slices.z() * sizeof(float) ); 00559 } 00560 00561 mBottomLeft = bottom_left; 00562 mTopRight = top_right; 00563 mSize = topRight()-bottomLeft(); 00564 mSlices = slices; 00565 mCellSize.x() = size.x() / (slices.x()-1); 00566 mCellSize.y() = size.y() / (slices.y()-1); 00567 mCellSize.z() = size.z() / (slices.z()-1); 00568 00569 mMinimum = +1; 00570 mMaximum = -1; 00571 mAverage = 0; 00572 mDataIsDirty = true; 00573 } 00574 //------------------------------------------------------------------------------ 00575 void Volume::setup(const Volume& volume) 00576 { 00577 *this = volume; 00578 mMinimum = +1; 00579 mMaximum = -1; 00580 mAverage = 0; 00581 mDataIsDirty = true; 00582 } 00583 //------------------------------------------------------------------------------ 00584 float Volume::sampleNearest(float x, float y, float z) const 00585 { 00586 x = (x - mBottomLeft.x()) / mSize.x(); 00587 y = (y - mBottomLeft.y()) / mSize.y(); 00588 z = (z - mBottomLeft.z()) / mSize.z(); 00589 if (x<0 || y<0 || z<0) return 0; 00590 if (x>1.0001 || y>1.0001 || z>1.0001) return 0; 00591 if (x > 0.9999f) x = 0.9999f; 00592 if (y > 0.9999f) y = 0.9999f; 00593 if (z > 0.9999f) z = 0.9999f; 00594 float xt = x * (mSlices.x()-1); 00595 float yt = y * (mSlices.y()-1); 00596 float zt = z * (mSlices.z()-1); 00597 int ix = int(xt); 00598 int iy = int(yt); 00599 int iz = int(zt); 00600 return value(ix , iy, iz); 00601 } 00602 //------------------------------------------------------------------------------ 00603 float Volume::sampleSmooth(float x, float y, float z) const 00604 { 00605 x = (x - mBottomLeft.x()) / mSize.x(); 00606 y = (y - mBottomLeft.y()) / mSize.y(); 00607 z = (z - mBottomLeft.z()) / mSize.z(); 00608 if (x<0 || y<0 || z<0) return 0; 00609 if (x>1.0f || y>1.0f || z>1.0f) return 0; 00610 if (x > 0.9999f) x = 0.9999f; 00611 if (y > 0.9999f) y = 0.9999f; 00612 if (z > 0.9999f) z = 0.9999f; 00613 float xt = x * (mSlices.x()-1); 00614 float yt = y * (mSlices.y()-1); 00615 float zt = z * (mSlices.z()-1); 00616 int ix = int(xt); xt -= ix; 00617 int iy = int(yt); yt -= iy; 00618 int iz = int(zt); zt -= iz; 00619 float val0 = value(ix , iy, iz); 00620 float val1 = value(ix+1, iy, iz); 00621 float val2 = value(ix+1, iy+1, iz); 00622 float val3 = value(ix, iy+1, iz); 00623 float val4 = value(ix , iy, iz+1); 00624 float val5 = value(ix+1, iy, iz+1); 00625 float val6 = value(ix+1, iy+1, iz+1); 00626 float val7 = value(ix, iy+1, iz+1); 00627 float xt1 = 1-xt; 00628 float yt1 = 1-yt; 00629 float zt1 = 1-zt; 00630 float v1 = val0*(yt1) + val3*yt; 00631 float v2 = val1*(yt1) + val2*yt; 00632 float a = v1*(xt1) + v2*xt; 00633 v1 = val4*(yt1) + val7*yt; 00634 v2 = val5*(yt1) + val6*yt; 00635 float b = v1*(xt1) + v2*xt; 00636 return a*(zt1) + b*zt; 00637 } 00638 //------------------------------------------------------------------------------ 00639 void Volume::normalHQ(fvec3 &normal, const fvec3& v, float dx, float dy, float dz) 00640 { 00642 // note: this is the performance killer, it would be nice to optimize it... 00644 normal.x() = sampleSmooth(v.x()-dx, v.y(), v.z()) - sampleSmooth(v.x()+dx, v.y(), v.z()); 00645 normal.y() = sampleSmooth(v.x(), v.y()-dy, v.z()) - sampleSmooth(v.x(), v.y()+dy, v.z()); 00646 normal.z() = sampleSmooth(v.x(), v.y(), v.z()-dz) - sampleSmooth(v.x(), v.y(), v.z()+dz); 00647 normal.normalize(); 00648 } 00649 //------------------------------------------------------------------------------ 00650 void Volume::normalLQ(fvec3 &normal, const fvec3& v, float dx, float dy, float dz) 00651 { 00652 // this function could be optimized even more by sampling the 8 points only once, 00653 // and computing the x and y gradient form the same slice... but since we don't use it... 00654 float v0 = sampleSmooth(v.x(), v.y(), v.z()); 00655 normal.x() = v0 - sampleSmooth(v.x()+dx, v.y(), v.z()); 00656 normal.y() = v0 - sampleSmooth(v.x(), v.y()+dy, v.z()); 00657 normal.z() = v0 - sampleSmooth(v.x(), v.y(), v.z()+dz); 00658 normal.normalize(); 00659 } 00660 //------------------------------------------------------------------------------ 00661 float Volume::computeMinimum() const 00662 { 00663 if (!mValues) 00664 return 0; 00665 float lowest = mValues[0]; 00666 int val_count = mSlices.x() * mSlices.y() * mSlices.z(); 00667 for(int i=1; i<val_count; ++i) 00668 if (mValues[i] < lowest) 00669 lowest = mValues[i]; 00670 return lowest; 00671 } 00672 //------------------------------------------------------------------------------ 00673 float Volume::computeMaximum() const 00674 { 00675 if (!mValues) 00676 return 0; 00677 float highest = mValues[0]; 00678 int val_count = mSlices.x() * mSlices.y() * mSlices.z(); 00679 for(int i=1; i<val_count; ++i) 00680 if (mValues[i] > highest) 00681 highest = mValues[i]; 00682 return highest; 00683 } 00684 //------------------------------------------------------------------------------ 00685 float Volume::computeAverage() const 00686 { 00687 if (!mValues) 00688 return 0; 00689 double average = 0; 00690 int val_count = mSlices.x() * mSlices.y() * mSlices.z(); 00691 for(int i=0; i<val_count; ++i) 00692 average += mValues[i]; 00693 average /= (double)val_count; 00694 return (float)average; 00695 } 00696 //------------------------------------------------------------------------------ 00697 const int MarchingCubes::mCubeEdgeFlags[256]= 00698 { 00699 0x000, 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c, 0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00, 00700 0x190, 0x099, 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c, 0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90, 00701 0x230, 0x339, 0x033, 0x13a, 0x636, 0x73f, 0x435, 0x53c, 0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30, 00702 0x3a0, 0x2a9, 0x1a3, 0x0aa, 0x7a6, 0x6af, 0x5a5, 0x4ac, 0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0, 00703 0x460, 0x569, 0x663, 0x76a, 0x066, 0x16f, 0x265, 0x36c, 0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60, 00704 0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0x0ff, 0x3f5, 0x2fc, 0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0, 00705 0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x055, 0x15c, 0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950, 00706 0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0x0cc, 0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0, 00707 0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc, 0x0cc, 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0, 00708 0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c, 0x15c, 0x055, 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650, 00709 0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc, 0x2fc, 0x3f5, 0x0ff, 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0, 00710 0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c, 0x36c, 0x265, 0x16f, 0x066, 0x76a, 0x663, 0x569, 0x460, 00711 0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac, 0x4ac, 0x5a5, 0x6af, 0x7a6, 0x0aa, 0x1a3, 0x2a9, 0x3a0, 00712 0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c, 0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x033, 0x339, 0x230, 00713 0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c, 0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x099, 0x190, 00714 0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c, 0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x000 00715 }; 00716 //------------------------------------------------------------------------------ 00717 const int MarchingCubes::mTriangleConnectionTable[256][16] = 00718 { 00719 {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00720 {0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00721 {0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00722 {1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00723 {1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00724 {0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00725 {9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00726 {2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1}, 00727 {3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00728 {0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00729 {1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00730 {1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1}, 00731 {3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00732 {0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1}, 00733 {3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1}, 00734 {9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00735 {4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00736 {4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00737 {0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00738 {4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1}, 00739 {1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00740 {3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1}, 00741 {9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1}, 00742 {2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1}, 00743 {8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00744 {11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1}, 00745 {9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1}, 00746 {4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1}, 00747 {3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1}, 00748 {1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1}, 00749 {4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1}, 00750 {4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1}, 00751 {9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00752 {9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00753 {0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00754 {8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1}, 00755 {1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00756 {3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1}, 00757 {5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1}, 00758 {2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1}, 00759 {9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00760 {0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1}, 00761 {0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1}, 00762 {2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1}, 00763 {10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1}, 00764 {4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1}, 00765 {5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1}, 00766 {5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1}, 00767 {9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00768 {9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1}, 00769 {0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1}, 00770 {1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00771 {9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1}, 00772 {10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1}, 00773 {8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1}, 00774 {2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1}, 00775 {7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1}, 00776 {9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1}, 00777 {2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1}, 00778 {11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1}, 00779 {9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1}, 00780 {5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1}, 00781 {11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1}, 00782 {11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00783 {10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00784 {0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00785 {9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00786 {1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1}, 00787 {1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00788 {1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1}, 00789 {9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1}, 00790 {5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1}, 00791 {2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00792 {11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1}, 00793 {0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1}, 00794 {5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1}, 00795 {6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1}, 00796 {0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1}, 00797 {3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1}, 00798 {6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1}, 00799 {5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00800 {4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1}, 00801 {1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1}, 00802 {10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1}, 00803 {6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1}, 00804 {1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1}, 00805 {8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1}, 00806 {7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1}, 00807 {3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1}, 00808 {5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1}, 00809 {0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1}, 00810 {9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1}, 00811 {8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1}, 00812 {5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1}, 00813 {0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1}, 00814 {6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1}, 00815 {10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00816 {4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1}, 00817 {10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1}, 00818 {8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1}, 00819 {1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1}, 00820 {3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1}, 00821 {0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00822 {8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1}, 00823 {10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1}, 00824 {0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1}, 00825 {3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1}, 00826 {6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1}, 00827 {9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1}, 00828 {8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1}, 00829 {3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1}, 00830 {6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00831 {7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1}, 00832 {0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1}, 00833 {10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1}, 00834 {10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1}, 00835 {1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1}, 00836 {2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1}, 00837 {7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1}, 00838 {7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00839 {2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1}, 00840 {2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1}, 00841 {1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1}, 00842 {11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1}, 00843 {8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1}, 00844 {0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00845 {7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1}, 00846 {7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00847 {7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00848 {3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00849 {0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00850 {8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1}, 00851 {10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00852 {1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1}, 00853 {2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1}, 00854 {6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1}, 00855 {7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00856 {7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1}, 00857 {2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1}, 00858 {1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1}, 00859 {10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1}, 00860 {10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1}, 00861 {0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1}, 00862 {7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1}, 00863 {6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00864 {3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1}, 00865 {8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1}, 00866 {9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1}, 00867 {6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1}, 00868 {1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1}, 00869 {4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1}, 00870 {10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1}, 00871 {8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1}, 00872 {0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00873 {1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1}, 00874 {1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1}, 00875 {8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1}, 00876 {10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1}, 00877 {4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1}, 00878 {10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00879 {4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00880 {0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1}, 00881 {5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1}, 00882 {11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1}, 00883 {9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1}, 00884 {6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1}, 00885 {7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1}, 00886 {3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1}, 00887 {7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1}, 00888 {9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1}, 00889 {3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1}, 00890 {6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1}, 00891 {9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1}, 00892 {1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1}, 00893 {4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1}, 00894 {7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1}, 00895 {6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1}, 00896 {3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1}, 00897 {0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1}, 00898 {6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1}, 00899 {1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1}, 00900 {0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1}, 00901 {11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1}, 00902 {6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1}, 00903 {5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1}, 00904 {9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1}, 00905 {1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1}, 00906 {1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00907 {1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1}, 00908 {10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1}, 00909 {0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00910 {10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00911 {11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00912 {11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1}, 00913 {5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1}, 00914 {10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1}, 00915 {11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1}, 00916 {0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1}, 00917 {9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1}, 00918 {7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1}, 00919 {2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1}, 00920 {8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1}, 00921 {9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1}, 00922 {9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1}, 00923 {1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00924 {0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1}, 00925 {9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1}, 00926 {9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00927 {5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1}, 00928 {5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1}, 00929 {0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1}, 00930 {10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1}, 00931 {2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1}, 00932 {0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1}, 00933 {0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1}, 00934 {9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00935 {2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1}, 00936 {5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1}, 00937 {3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1}, 00938 {5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1}, 00939 {8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1}, 00940 {0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00941 {8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1}, 00942 {9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00943 {4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1}, 00944 {0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1}, 00945 {1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1}, 00946 {3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1}, 00947 {4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1}, 00948 {9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1}, 00949 {11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1}, 00950 {11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1}, 00951 {2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1}, 00952 {9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1}, 00953 {3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1}, 00954 {1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00955 {4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1}, 00956 {4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1}, 00957 {4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00958 {4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00959 {9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00960 {3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1}, 00961 {0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1}, 00962 {3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00963 {1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1}, 00964 {3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1}, 00965 {0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00966 {3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00967 {2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1}, 00968 {9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00969 {2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1}, 00970 {1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00971 {1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00972 {0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00973 {0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 00974 {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1} 00975 }; 00976 //------------------------------------------------------------------------------