Back to index

supertuxkart  0.5+dfsg1
btVoronoiSimplexSolver.cpp
Go to the documentation of this file.
00001 
00002 /*
00003 Bullet Continuous Collision Detection and Physics Library
00004 Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
00005 
00006 This software is provided 'as-is', without any express or implied warranty.
00007 In no event will the authors be held liable for any damages arising from the use of this software.
00008 Permission is granted to anyone to use this software for any purpose, 
00009 including commercial applications, and to alter it and redistribute it freely, 
00010 subject to the following restrictions:
00011 
00012 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
00013 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
00014 3. This notice may not be removed or altered from any source distribution.
00015        
00016        Elsevier CDROM license agreements grants nonexclusive license to use the software
00017        for any purpose, commercial or non-commercial as long as the following credit is included
00018        identifying the original source of the software:
00019 
00020        Parts of the source are "from the book Real-Time Collision Detection by
00021        Christer Ericson, published by Morgan Kaufmann Publishers,
00022        (c) 2005 Elsevier Inc."
00023               
00024 */
00025 
00026 
00027 #include "btVoronoiSimplexSolver.h"
00028 #include <assert.h>
00029 //#include <stdio.h>
00030 
00031 #define VERTA  0
00032 #define VERTB  1
00033 #define VERTC  2
00034 #define VERTD  3
00035 
00036 #define CATCH_DEGENERATE_TETRAHEDRON 1
00037 void   btVoronoiSimplexSolver::removeVertex(int index)
00038 {
00039        
00040        assert(m_numVertices>0);
00041        m_numVertices--;
00042        m_simplexVectorW[index] = m_simplexVectorW[m_numVertices];
00043        m_simplexPointsP[index] = m_simplexPointsP[m_numVertices];
00044        m_simplexPointsQ[index] = m_simplexPointsQ[m_numVertices];
00045 }
00046 
00047 void   btVoronoiSimplexSolver::reduceVertices (const btUsageBitfield& usedVerts)
00048 {
00049        if ((numVertices() >= 4) && (!usedVerts.usedVertexD))
00050               removeVertex(3);
00051 
00052        if ((numVertices() >= 3) && (!usedVerts.usedVertexC))
00053               removeVertex(2);
00054 
00055        if ((numVertices() >= 2) && (!usedVerts.usedVertexB))
00056               removeVertex(1);
00057        
00058        if ((numVertices() >= 1) && (!usedVerts.usedVertexA))
00059               removeVertex(0);
00060 
00061 }
00062 
00063 
00064 
00065 
00066 
00067 //clear the simplex, remove all the vertices
00068 void btVoronoiSimplexSolver::reset()
00069 {
00070        m_cachedValidClosest = false;
00071        m_numVertices = 0;
00072        m_needsUpdate = true;
00073        m_lastW = btVector3(btScalar(1e30),btScalar(1e30),btScalar(1e30));
00074        m_cachedBC.reset();
00075 }
00076 
00077 
00078 
00079        //add a vertex
00080 void btVoronoiSimplexSolver::addVertex(const btVector3& w, const btPoint3& p, const btPoint3& q)
00081 {
00082        m_lastW = w;
00083        m_needsUpdate = true;
00084 
00085        m_simplexVectorW[m_numVertices] = w;
00086        m_simplexPointsP[m_numVertices] = p;
00087        m_simplexPointsQ[m_numVertices] = q;
00088 
00089        m_numVertices++;
00090 }
00091 
00092 bool   btVoronoiSimplexSolver::updateClosestVectorAndPoints()
00093 {
00094        
00095        if (m_needsUpdate)
00096        {
00097               m_cachedBC.reset();
00098 
00099               m_needsUpdate = false;
00100 
00101               switch (numVertices())
00102               {
00103               case 0:
00104                             m_cachedValidClosest = false;
00105                             break;
00106               case 1:
00107                      {
00108                             m_cachedP1 = m_simplexPointsP[0];
00109                             m_cachedP2 = m_simplexPointsQ[0];
00110                             m_cachedV = m_cachedP1-m_cachedP2; //== m_simplexVectorW[0]
00111                             m_cachedBC.reset();
00112                             m_cachedBC.setBarycentricCoordinates(btScalar(1.),btScalar(0.),btScalar(0.),btScalar(0.));
00113                             m_cachedValidClosest = m_cachedBC.isValid();
00114                             break;
00115                      };
00116               case 2:
00117                      {
00118                      //closest point origin from line segment
00119                                    const btVector3& from = m_simplexVectorW[0];
00120                                    const btVector3& to = m_simplexVectorW[1];
00121                                    btVector3 nearest;
00122 
00123                                    btVector3 p (btScalar(0.),btScalar(0.),btScalar(0.));
00124                                    btVector3 diff = p - from;
00125                                    btVector3 v = to - from;
00126                                    btScalar t = v.dot(diff);
00127                                    
00128                                    if (t > 0) {
00129                                           btScalar dotVV = v.dot(v);
00130                                           if (t < dotVV) {
00131                                                  t /= dotVV;
00132                                                  diff -= t*v;
00133                                                  m_cachedBC.m_usedVertices.usedVertexA = true;
00134                                                  m_cachedBC.m_usedVertices.usedVertexB = true;
00135                                           } else {
00136                                                  t = 1;
00137                                                  diff -= v;
00138                                                  //reduce to 1 point
00139                                                  m_cachedBC.m_usedVertices.usedVertexB = true;
00140                                           }
00141                                    } else
00142                                    {
00143                                           t = 0;
00144                                           //reduce to 1 point
00145                                           m_cachedBC.m_usedVertices.usedVertexA = true;
00146                                    }
00147                                    m_cachedBC.setBarycentricCoordinates(1-t,t);
00148                                    nearest = from + t*v;
00149 
00150                                    m_cachedP1 = m_simplexPointsP[0] + t * (m_simplexPointsP[1] - m_simplexPointsP[0]);
00151                                    m_cachedP2 = m_simplexPointsQ[0] + t * (m_simplexPointsQ[1] - m_simplexPointsQ[0]);
00152                                    m_cachedV = m_cachedP1 - m_cachedP2;
00153                                    
00154                                    reduceVertices(m_cachedBC.m_usedVertices);
00155 
00156                                    m_cachedValidClosest = m_cachedBC.isValid();
00157                                    break;
00158                      }
00159               case 3: 
00160                      { 
00161                             //closest point origin from triangle 
00162                             btVector3 p (btScalar(0.),btScalar(0.),btScalar(0.)); 
00163 
00164                             const btVector3& a = m_simplexVectorW[0]; 
00165                             const btVector3& b = m_simplexVectorW[1]; 
00166                             const btVector3& c = m_simplexVectorW[2]; 
00167 
00168                             closestPtPointTriangle(p,a,b,c,m_cachedBC); 
00169                             m_cachedP1 = m_simplexPointsP[0] * m_cachedBC.m_barycentricCoords[0] + 
00170                             m_simplexPointsP[1] * m_cachedBC.m_barycentricCoords[1] + 
00171                             m_simplexPointsP[2] * m_cachedBC.m_barycentricCoords[2]; 
00172 
00173                             m_cachedP2 = m_simplexPointsQ[0] * m_cachedBC.m_barycentricCoords[0] + 
00174                             m_simplexPointsQ[1] * m_cachedBC.m_barycentricCoords[1] + 
00175                             m_simplexPointsQ[2] * m_cachedBC.m_barycentricCoords[2]; 
00176 
00177                             m_cachedV = m_cachedP1-m_cachedP2; 
00178 
00179                             reduceVertices (m_cachedBC.m_usedVertices); 
00180                             m_cachedValidClosest = m_cachedBC.isValid(); 
00181 
00182                             break; 
00183                      }
00184               case 4:
00185                      {
00186 
00187                             
00188                             btVector3 p (btScalar(0.),btScalar(0.),btScalar(0.));
00189                             
00190                             const btVector3& a = m_simplexVectorW[0];
00191                             const btVector3& b = m_simplexVectorW[1];
00192                             const btVector3& c = m_simplexVectorW[2];
00193                             const btVector3& d = m_simplexVectorW[3];
00194 
00195                             bool hasSeperation = closestPtPointTetrahedron(p,a,b,c,d,m_cachedBC);
00196 
00197                             if (hasSeperation)
00198                             {
00199 
00200                                    m_cachedP1 = m_simplexPointsP[0] * m_cachedBC.m_barycentricCoords[0] +
00201                                           m_simplexPointsP[1] * m_cachedBC.m_barycentricCoords[1] +
00202                                           m_simplexPointsP[2] * m_cachedBC.m_barycentricCoords[2] +
00203                                           m_simplexPointsP[3] * m_cachedBC.m_barycentricCoords[3];
00204 
00205                                    m_cachedP2 = m_simplexPointsQ[0] * m_cachedBC.m_barycentricCoords[0] +
00206                                           m_simplexPointsQ[1] * m_cachedBC.m_barycentricCoords[1] +
00207                                           m_simplexPointsQ[2] * m_cachedBC.m_barycentricCoords[2] +
00208                                           m_simplexPointsQ[3] * m_cachedBC.m_barycentricCoords[3];
00209 
00210                                    m_cachedV = m_cachedP1-m_cachedP2;
00211                                    reduceVertices (m_cachedBC.m_usedVertices);
00212                             } else
00213                             {
00214 //                                 printf("sub distance got penetration\n");
00215 
00216                                    if (m_cachedBC.m_degenerate)
00217                                    {
00218                                           m_cachedValidClosest = false;
00219                                    } else
00220                                    {
00221                                           m_cachedValidClosest = true;
00222                                           //degenerate case == false, penetration = true + zero
00223                                           m_cachedV.setValue(btScalar(0.),btScalar(0.),btScalar(0.));
00224                                    }
00225                                    break;
00226                             }
00227 
00228                             m_cachedValidClosest = m_cachedBC.isValid();
00229 
00230                             //closest point origin from tetrahedron
00231                             break;
00232                      }
00233               default:
00234                      {
00235                             m_cachedValidClosest = false;
00236                      }
00237               };
00238        }
00239 
00240        return m_cachedValidClosest;
00241 
00242 }
00243 
00244 //return/calculate the closest vertex
00245 bool btVoronoiSimplexSolver::closest(btVector3& v)
00246 {
00247        bool succes = updateClosestVectorAndPoints();
00248        v = m_cachedV;
00249        return succes;
00250 }
00251 
00252 
00253 
00254 btScalar btVoronoiSimplexSolver::maxVertex()
00255 {
00256        int i, numverts = numVertices();
00257        btScalar maxV = btScalar(0.);
00258        for (i=0;i<numverts;i++)
00259        {
00260               btScalar curLen2 = m_simplexVectorW[i].length2();
00261               if (maxV < curLen2)
00262                      maxV = curLen2;
00263        }
00264        return maxV;
00265 }
00266 
00267 
00268 
00269        //return the current simplex
00270 int btVoronoiSimplexSolver::getSimplex(btPoint3 *pBuf, btPoint3 *qBuf, btVector3 *yBuf) const
00271 {
00272        int i;
00273        for (i=0;i<numVertices();i++)
00274        {
00275               yBuf[i] = m_simplexVectorW[i];
00276               pBuf[i] = m_simplexPointsP[i];
00277               qBuf[i] = m_simplexPointsQ[i];
00278        }
00279        return numVertices();
00280 }
00281 
00282 
00283 
00284 
00285 bool btVoronoiSimplexSolver::inSimplex(const btVector3& w)
00286 {
00287        bool found = false;
00288        int i, numverts = numVertices();
00289        //btScalar maxV = btScalar(0.);
00290        
00291        //w is in the current (reduced) simplex
00292        for (i=0;i<numverts;i++)
00293        {
00294               if (m_simplexVectorW[i] == w)
00295                      found = true;
00296        }
00297 
00298        //check in case lastW is already removed
00299        if (w == m_lastW)
00300               return true;
00301        
00302        return found;
00303 }
00304 
00305 void btVoronoiSimplexSolver::backup_closest(btVector3& v) 
00306 {
00307        v = m_cachedV;
00308 }
00309 
00310 
00311 bool btVoronoiSimplexSolver::emptySimplex() const 
00312 {
00313        return (numVertices() == 0);
00314 
00315 }
00316 
00317 void btVoronoiSimplexSolver::compute_points(btPoint3& p1, btPoint3& p2) 
00318 {
00319        updateClosestVectorAndPoints();
00320        p1 = m_cachedP1;
00321        p2 = m_cachedP2;
00322 
00323 }
00324 
00325 
00326 
00327 
00328 bool   btVoronoiSimplexSolver::closestPtPointTriangle(const btPoint3& p, const btPoint3& a, const btPoint3& b, const btPoint3& c,btSubSimplexClosestResult& result)
00329 {
00330        result.m_usedVertices.reset();
00331 
00332     // Check if P in vertex region outside A
00333     btVector3 ab = b - a;
00334     btVector3 ac = c - a;
00335     btVector3 ap = p - a;
00336     btScalar d1 = ab.dot(ap);
00337     btScalar d2 = ac.dot(ap);
00338     if (d1 <= btScalar(0.0) && d2 <= btScalar(0.0)) 
00339        {
00340               result.m_closestPointOnSimplex = a;
00341               result.m_usedVertices.usedVertexA = true;
00342               result.setBarycentricCoordinates(1,0,0);
00343               return true;// a; // barycentric coordinates (1,0,0)
00344        }
00345 
00346     // Check if P in vertex region outside B
00347     btVector3 bp = p - b;
00348     btScalar d3 = ab.dot(bp);
00349     btScalar d4 = ac.dot(bp);
00350     if (d3 >= btScalar(0.0) && d4 <= d3) 
00351        {
00352               result.m_closestPointOnSimplex = b;
00353               result.m_usedVertices.usedVertexB = true;
00354               result.setBarycentricCoordinates(0,1,0);
00355 
00356               return true; // b; // barycentric coordinates (0,1,0)
00357        }
00358     // Check if P in edge region of AB, if so return projection of P onto AB
00359     btScalar vc = d1*d4 - d3*d2;
00360     if (vc <= btScalar(0.0) && d1 >= btScalar(0.0) && d3 <= btScalar(0.0)) {
00361         btScalar v = d1 / (d1 - d3);
00362               result.m_closestPointOnSimplex = a + v * ab;
00363               result.m_usedVertices.usedVertexA = true;
00364               result.m_usedVertices.usedVertexB = true;
00365               result.setBarycentricCoordinates(1-v,v,0);
00366               return true;
00367         //return a + v * ab; // barycentric coordinates (1-v,v,0)
00368     }
00369 
00370     // Check if P in vertex region outside C
00371     btVector3 cp = p - c;
00372     btScalar d5 = ab.dot(cp);
00373     btScalar d6 = ac.dot(cp);
00374     if (d6 >= btScalar(0.0) && d5 <= d6) 
00375        {
00376               result.m_closestPointOnSimplex = c;
00377               result.m_usedVertices.usedVertexC = true;
00378               result.setBarycentricCoordinates(0,0,1);
00379               return true;//c; // barycentric coordinates (0,0,1)
00380        }
00381 
00382     // Check if P in edge region of AC, if so return projection of P onto AC
00383     btScalar vb = d5*d2 - d1*d6;
00384     if (vb <= btScalar(0.0) && d2 >= btScalar(0.0) && d6 <= btScalar(0.0)) {
00385         btScalar w = d2 / (d2 - d6);
00386               result.m_closestPointOnSimplex = a + w * ac;
00387               result.m_usedVertices.usedVertexA = true;
00388               result.m_usedVertices.usedVertexC = true;
00389               result.setBarycentricCoordinates(1-w,0,w);
00390               return true;
00391         //return a + w * ac; // barycentric coordinates (1-w,0,w)
00392     }
00393 
00394     // Check if P in edge region of BC, if so return projection of P onto BC
00395     btScalar va = d3*d6 - d5*d4;
00396     if (va <= btScalar(0.0) && (d4 - d3) >= btScalar(0.0) && (d5 - d6) >= btScalar(0.0)) {
00397         btScalar w = (d4 - d3) / ((d4 - d3) + (d5 - d6));
00398               
00399               result.m_closestPointOnSimplex = b + w * (c - b);
00400               result.m_usedVertices.usedVertexB = true;
00401               result.m_usedVertices.usedVertexC = true;
00402               result.setBarycentricCoordinates(0,1-w,w);
00403               return true;         
00404        // return b + w * (c - b); // barycentric coordinates (0,1-w,w)
00405     }
00406 
00407     // P inside face region. Compute Q through its barycentric coordinates (u,v,w)
00408     btScalar denom = btScalar(1.0) / (va + vb + vc);
00409     btScalar v = vb * denom;
00410     btScalar w = vc * denom;
00411     
00412        result.m_closestPointOnSimplex = a + ab * v + ac * w;
00413        result.m_usedVertices.usedVertexA = true;
00414        result.m_usedVertices.usedVertexB = true;
00415        result.m_usedVertices.usedVertexC = true;
00416        result.setBarycentricCoordinates(1-v-w,v,w);
00417        
00418        return true;
00419 //     return a + ab * v + ac * w; // = u*a + v*b + w*c, u = va * denom = btScalar(1.0) - v - w
00420 
00421 }
00422 
00423 
00424 
00425 
00426 
00428 int btVoronoiSimplexSolver::pointOutsideOfPlane(const btPoint3& p, const btPoint3& a, const btPoint3& b, const btPoint3& c, const btPoint3& d)
00429 {
00430        btVector3 normal = (b-a).cross(c-a);
00431 
00432     btScalar signp = (p - a).dot(normal); // [AP AB AC]
00433     btScalar signd = (d - a).dot( normal); // [AD AB AC]
00434 
00435 #ifdef CATCH_DEGENERATE_TETRAHEDRON
00436 #ifdef BT_USE_DOUBLE_PRECISION
00437 if (signd * signd < (btScalar(1e-8) * btScalar(1e-8)))
00438        {
00439               return -1;
00440        }
00441 #else
00442        if (signd * signd < (btScalar(1e-4) * btScalar(1e-4)))
00443        {
00444 //            printf("affine dependent/degenerate\n");//
00445               return -1;
00446        }
00447 #endif
00448 
00449 #endif
00450        // Points on opposite sides if expression signs are opposite
00451     return signp * signd < btScalar(0.);
00452 }
00453 
00454 
00455 bool   btVoronoiSimplexSolver::closestPtPointTetrahedron(const btPoint3& p, const btPoint3& a, const btPoint3& b, const btPoint3& c, const btPoint3& d, btSubSimplexClosestResult& finalResult)
00456 {
00457        btSubSimplexClosestResult tempResult;
00458 
00459     // Start out assuming point inside all halfspaces, so closest to itself
00460        finalResult.m_closestPointOnSimplex = p;
00461        finalResult.m_usedVertices.reset();
00462     finalResult.m_usedVertices.usedVertexA = true;
00463        finalResult.m_usedVertices.usedVertexB = true;
00464        finalResult.m_usedVertices.usedVertexC = true;
00465        finalResult.m_usedVertices.usedVertexD = true;
00466 
00467     int pointOutsideABC = pointOutsideOfPlane(p, a, b, c, d);
00468        int pointOutsideACD = pointOutsideOfPlane(p, a, c, d, b);
00469        int    pointOutsideADB = pointOutsideOfPlane(p, a, d, b, c);
00470        int    pointOutsideBDC = pointOutsideOfPlane(p, b, d, c, a);
00471 
00472    if (pointOutsideABC < 0 || pointOutsideACD < 0 || pointOutsideADB < 0 || pointOutsideBDC < 0)
00473    {
00474           finalResult.m_degenerate = true;
00475           return false;
00476    }
00477 
00478    if (!pointOutsideABC  && !pointOutsideACD && !pointOutsideADB && !pointOutsideBDC)
00479         {
00480                return false;
00481         }
00482 
00483 
00484     btScalar bestSqDist = FLT_MAX;
00485     // If point outside face abc then compute closest point on abc
00486        if (pointOutsideABC) 
00487        {
00488         closestPtPointTriangle(p, a, b, c,tempResult);
00489               btPoint3 q = tempResult.m_closestPointOnSimplex;
00490               
00491         btScalar sqDist = (q - p).dot( q - p);
00492         // Update best closest point if (squared) distance is less than current best
00493         if (sqDist < bestSqDist) {
00494                      bestSqDist = sqDist;
00495                      finalResult.m_closestPointOnSimplex = q;
00496                      //convert result bitmask!
00497                      finalResult.m_usedVertices.reset();
00498                      finalResult.m_usedVertices.usedVertexA = tempResult.m_usedVertices.usedVertexA;
00499                      finalResult.m_usedVertices.usedVertexB = tempResult.m_usedVertices.usedVertexB;
00500                      finalResult.m_usedVertices.usedVertexC = tempResult.m_usedVertices.usedVertexC;
00501                      finalResult.setBarycentricCoordinates(
00502                                    tempResult.m_barycentricCoords[VERTA],
00503                                    tempResult.m_barycentricCoords[VERTB],
00504                                    tempResult.m_barycentricCoords[VERTC],
00505                                    0
00506                      );
00507 
00508               }
00509     }
00510   
00511 
00512        // Repeat test for face acd
00513        if (pointOutsideACD) 
00514        {
00515         closestPtPointTriangle(p, a, c, d,tempResult);
00516               btPoint3 q = tempResult.m_closestPointOnSimplex;
00517               //convert result bitmask!
00518 
00519         btScalar sqDist = (q - p).dot( q - p);
00520         if (sqDist < bestSqDist) 
00521               {
00522                      bestSqDist = sqDist;
00523                      finalResult.m_closestPointOnSimplex = q;
00524                      finalResult.m_usedVertices.reset();
00525                      finalResult.m_usedVertices.usedVertexA = tempResult.m_usedVertices.usedVertexA;
00526 
00527                      finalResult.m_usedVertices.usedVertexC = tempResult.m_usedVertices.usedVertexB;
00528                      finalResult.m_usedVertices.usedVertexD = tempResult.m_usedVertices.usedVertexC;
00529                      finalResult.setBarycentricCoordinates(
00530                                    tempResult.m_barycentricCoords[VERTA],
00531                                    0,
00532                                    tempResult.m_barycentricCoords[VERTB],
00533                                    tempResult.m_barycentricCoords[VERTC]
00534                      );
00535 
00536               }
00537     }
00538     // Repeat test for face adb
00539 
00540        
00541        if (pointOutsideADB)
00542        {
00543               closestPtPointTriangle(p, a, d, b,tempResult);
00544               btPoint3 q = tempResult.m_closestPointOnSimplex;
00545               //convert result bitmask!
00546 
00547         btScalar sqDist = (q - p).dot( q - p);
00548         if (sqDist < bestSqDist) 
00549               {
00550                      bestSqDist = sqDist;
00551                      finalResult.m_closestPointOnSimplex = q;
00552                      finalResult.m_usedVertices.reset();
00553                      finalResult.m_usedVertices.usedVertexA = tempResult.m_usedVertices.usedVertexA;
00554                      finalResult.m_usedVertices.usedVertexB = tempResult.m_usedVertices.usedVertexC;
00555                      
00556                      finalResult.m_usedVertices.usedVertexD = tempResult.m_usedVertices.usedVertexB;
00557                      finalResult.setBarycentricCoordinates(
00558                                    tempResult.m_barycentricCoords[VERTA],
00559                                    tempResult.m_barycentricCoords[VERTC],
00560                                    0,
00561                                    tempResult.m_barycentricCoords[VERTB]
00562                      );
00563 
00564               }
00565     }
00566     // Repeat test for face bdc
00567     
00568 
00569        if (pointOutsideBDC)
00570        {
00571         closestPtPointTriangle(p, b, d, c,tempResult);
00572               btPoint3 q = tempResult.m_closestPointOnSimplex;
00573               //convert result bitmask!
00574         btScalar sqDist = (q - p).dot( q - p);
00575         if (sqDist < bestSqDist) 
00576               {
00577                      bestSqDist = sqDist;
00578                      finalResult.m_closestPointOnSimplex = q;
00579                      finalResult.m_usedVertices.reset();
00580                      //
00581                      finalResult.m_usedVertices.usedVertexB = tempResult.m_usedVertices.usedVertexA;
00582                      finalResult.m_usedVertices.usedVertexC = tempResult.m_usedVertices.usedVertexC;
00583                      finalResult.m_usedVertices.usedVertexD = tempResult.m_usedVertices.usedVertexB;
00584 
00585                      finalResult.setBarycentricCoordinates(
00586                                    0,
00587                                    tempResult.m_barycentricCoords[VERTA],
00588                                    tempResult.m_barycentricCoords[VERTC],
00589                                    tempResult.m_barycentricCoords[VERTB]
00590                      );
00591 
00592               }
00593     }
00594 
00595        //help! we ended up full !
00596        
00597        if (finalResult.m_usedVertices.usedVertexA &&
00598               finalResult.m_usedVertices.usedVertexB &&
00599               finalResult.m_usedVertices.usedVertexC &&
00600               finalResult.m_usedVertices.usedVertexD) 
00601        {
00602               return true;
00603        }
00604 
00605     return true;
00606 }
00607