Blender V2.61 - r43446

BOP_BSPNode.cpp

Go to the documentation of this file.
00001 /*
00002  * ***** BEGIN GPL LICENSE BLOCK *****
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License
00006  * as published by the Free Software Foundation; either version 2
00007  * of the License, or (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software Foundation,
00016  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00017  *
00018  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
00019  * All rights reserved.
00020  *
00021  * The Original Code is: all of this file.
00022  *
00023  * Contributor(s): none yet.
00024  *
00025  * ***** END GPL LICENSE BLOCK *****
00026  */
00027 
00033 #include "BOP_MathUtils.h"
00034 #include "BOP_BSPNode.h"
00035 #include "MT_assert.h"
00036 #include "MT_MinMax.h"
00037 #include <iostream>
00038 
00043 BOP_BSPNode::BOP_BSPNode(const MT_Plane3& plane)
00044 {
00045     m_plane      = plane;
00046     m_inChild    = NULL;
00047     m_outChild   = NULL;
00048     m_deep       = 1;
00049 }
00050 
00054 BOP_BSPNode::~BOP_BSPNode()
00055 {
00056     if (m_inChild!=NULL) delete m_inChild;
00057     if (m_outChild!=NULL) delete m_outChild;
00058 }
00059 
00066 unsigned int BOP_BSPNode::addFace(const BOP_BSPPoints& pts,
00067                                   const MT_Plane3& plane )
00068 {
00069     unsigned int newDeep = 0;
00070     BOP_TAG tag = ON;
00071 
00072     // find out if any points on the "face" lie in either half-space
00073     BOP_IT_BSPPoints ptsEnd = pts.end();
00074     for(BOP_IT_BSPPoints itp=pts.begin();itp!=ptsEnd;itp++){
00075         tag = (BOP_TAG) ((int) tag | (int)testPoint(*itp));
00076     }
00077  
00078     if (tag == ON) { }      // face lies on hyperplane: do nothing
00079     else if ((tag & IN) != 0 && (tag & OUT) == 0) { // face is entirely on inside
00080         if (m_inChild != NULL)
00081             newDeep = m_inChild->addFace(pts, plane) + 1;
00082         else {
00083             m_inChild = new BOP_BSPNode(plane);
00084             newDeep = 2;
00085         }    
00086     } else if ((tag & OUT) != 0 && (tag & IN) == 0) { // face is entirely on outside
00087         if (m_outChild != NULL)
00088             newDeep = m_outChild->addFace(pts, plane) + 1;
00089         else {
00090             m_outChild = new BOP_BSPNode(plane);
00091             newDeep = 2;
00092         }      
00093     } else { // face lies in both half-spaces: split it
00094         BOP_BSPPoints inside, outside;
00095         MT_Point3 lpoint= pts[pts.size()-1];
00096         BOP_TAG ltag = testPoint(lpoint);
00097         BOP_TAG tstate = ltag;
00098 
00099         // classify each line segment, looking for endpoints which lie on different
00100         // sides of the hyperplane.
00101 
00102         ptsEnd = pts.end();
00103         for(BOP_IT_BSPPoints itp=pts.begin();itp!=ptsEnd;itp++){
00104             MT_Point3 npoint= *itp;
00105             BOP_TAG ntag = testPoint(npoint);
00106 
00107             if(ltag != ON) {    // last point not on hyperplane
00108                 if(tstate == IN) {
00109                     if (m_inChild != NULL) inside.push_back(lpoint);
00110                 } else {
00111                     if (m_outChild != NULL) outside.push_back(lpoint);
00112                 }
00113                 if(ntag != ON && ntag != tstate) {  // last, self in different half-spaces 
00114                     MT_Point3 mpoint = BOP_intersectPlane( m_plane, lpoint, npoint );
00115                     if (m_inChild != NULL) inside.push_back(mpoint);
00116                     if (m_outChild != NULL) outside.push_back(mpoint);
00117                     tstate = ntag;
00118                 }
00119             } else {            // last point on hyperplane, so we're switching
00120                                 // half-spaces
00121                                 // boundary point belong to both faces
00122                 if (m_inChild != NULL) inside.push_back(lpoint);    
00123                 if (m_outChild != NULL) outside.push_back(lpoint);
00124                 tstate = ntag;  // state changes to new point tag
00125             }
00126             lpoint = npoint;    // save point, tag for next iteration
00127             ltag = ntag;
00128         }
00129 
00130         if (m_inChild != NULL)
00131             newDeep = m_inChild->addFace(inside, plane) + 1;
00132         else {
00133             m_inChild = new BOP_BSPNode(plane);
00134             newDeep = 2;
00135         }    
00136         if (m_outChild != NULL)
00137             newDeep = MT_max(newDeep, m_outChild->addFace(outside, plane) + 1);
00138         else {
00139             m_outChild = new BOP_BSPNode(plane);
00140             newDeep = MT_max(newDeep,(unsigned int)2);
00141         }      
00142     }
00143     
00144     // update the deep attribute
00145     m_deep = MT_max(m_deep,newDeep);
00146     
00147     return m_deep;
00148 }
00149 
00155 BOP_TAG BOP_BSPNode::testPoint(const MT_Point3& p) const
00156 {
00157   return BOP_createTAG(BOP_classify(p,m_plane));
00158 
00159 }
00160 
00169 BOP_TAG BOP_BSPNode::classifyFace(const MT_Point3& p1, 
00170                                   const MT_Point3& p2, 
00171                                   const MT_Point3& p3, 
00172                                   const MT_Plane3& plane) const
00173 {
00174     // local variables
00175     MT_Point3 auxp1, auxp2;
00176     BOP_TAG auxtag1, auxtag2, auxtag3;
00177 
00178     switch(BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3))) {
00179         // Classify the face on the IN side
00180         case IN_IN_IN : 
00181             return classifyFaceIN(p1, p2, p3, plane);
00182         case IN_IN_ON :
00183         case IN_ON_IN :
00184         case ON_IN_IN :
00185         case IN_ON_ON :
00186         case ON_IN_ON :
00187         case ON_ON_IN :
00188             return BOP_addON(classifyFaceIN(p1, p2, p3, plane));
00189     
00190         // Classify the face on the OUT side
00191         case OUT_OUT_OUT :
00192             return classifyFaceOUT(p1, p2, p3, plane);
00193         case OUT_OUT_ON :
00194         case OUT_ON_OUT :
00195         case ON_OUT_OUT :
00196         case ON_ON_OUT :
00197         case ON_OUT_ON :
00198         case OUT_ON_ON :
00199             return BOP_addON(classifyFaceOUT(p1, p2, p3, plane));
00200     
00201         // Classify the ON face depending on it plane normal
00202         case ON_ON_ON :
00203             if (hasSameOrientation(plane))
00204                 return BOP_addON(classifyFaceIN(p1, p2, p3, plane));
00205             else
00206                 return BOP_addON(classifyFaceOUT(p1, p2, p3, plane));
00207 
00208         // Classify the face IN/OUT and one vertex ON
00209         // becouse only one ON, only one way to subdivide the face
00210         case IN_OUT_ON :
00211             auxp1 = BOP_intersectPlane(m_plane, p1, p2);
00212             auxtag1 = classifyFaceIN( p1,    auxp1 , p3, plane);
00213             auxtag2 = classifyFaceOUT(auxp1, p2,     p3, plane);
00214             return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
00215 
00216         case OUT_IN_ON :
00217             auxp1 = BOP_intersectPlane(m_plane, p1, p2);
00218             auxtag1 = classifyFaceOUT(p1,    auxp1, p3, plane);
00219             auxtag2 = classifyFaceIN( auxp1, p2,    p3, plane);
00220             return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
00221 
00222         case IN_ON_OUT :
00223             auxp1 = BOP_intersectPlane(m_plane, p1, p3);
00224             auxtag1 = classifyFaceIN( p1, p2, auxp1, plane);
00225             auxtag2 = classifyFaceOUT(p2, p3, auxp1, plane);
00226             return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
00227 
00228         case OUT_ON_IN :
00229             auxp1 = BOP_intersectPlane(m_plane, p1, p3);
00230             auxtag1 = classifyFaceOUT(p1, p2, auxp1, plane);
00231             auxtag2 = classifyFaceIN( p2, p3, auxp1, plane);
00232             return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
00233 
00234         case ON_IN_OUT :
00235             auxp1 = BOP_intersectPlane(m_plane, p2, p3);
00236             auxtag1 = classifyFaceIN( p1,    p2, auxp1, plane);
00237             auxtag2 = classifyFaceOUT(auxp1, p3, p1,    plane);
00238             return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
00239 
00240         case ON_OUT_IN :
00241             auxp1 = BOP_intersectPlane(m_plane, p2, p3);
00242             auxtag1 = classifyFaceOUT(p1,    p2, auxp1, plane);
00243             auxtag2 = classifyFaceIN( auxp1, p3, p1,    plane);
00244             return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
00245 
00246         // Classify IN/OUT face without ON vertices.
00247         // Two ways to divide the triangle, 
00248         // will chose the least degenerated sub-triangles.
00249         case IN_OUT_OUT :
00250             auxp1 = BOP_intersectPlane(m_plane, p1, p2);
00251             auxp2 = BOP_intersectPlane(m_plane, p1, p3);
00252     
00253             // f1: p1 auxp1 , auxp1 auxp2
00254             auxtag1 = classifyFaceIN(p1, auxp1, auxp2, plane);
00255     
00256             // f2: auxp1 p2 , p2 auxp2;  f3: p2 p3 , p3 auxp2  ||  
00257             // f2: auxp1 p3, p3 auxp2;   f3: p2 p3 , p3 auxp1
00258             if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) {
00259                 auxtag2 = classifyFaceOUT(auxp1, p2, auxp2, plane);
00260                 auxtag3 = classifyFaceOUT(p2,    p3, auxp2, plane);
00261             }
00262             else {
00263                 auxtag2 = classifyFaceOUT(auxp1, p3, auxp2, plane);
00264                 auxtag3 = classifyFaceOUT(p2,    p3, auxp1, plane);
00265             }
00266             return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
00267 
00268         case OUT_IN_IN :
00269             auxp1 = BOP_intersectPlane(m_plane, p1, p2);
00270             auxp2 = BOP_intersectPlane(m_plane, p1, p3);
00271     
00272             // f1: p1 auxp1 , auxp1 auxp2
00273             auxtag1 = classifyFaceOUT(p1, auxp1, auxp2, plane);
00274     
00275             // f2: auxp1 p2 , p2 auxp2;  f3: p2 p3 , p3 auxp2  ||
00276             // f2: auxp1 p3, p3 auxp2;  f3: p2 p3 , p3 auxp1
00277             if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) {
00278                 auxtag2 = classifyFaceIN(auxp1, p2, auxp2, plane);
00279                 auxtag3 = classifyFaceIN(p2, p3, auxp2, plane);
00280             }
00281             else {
00282                 auxtag2 = classifyFaceIN(auxp1, p3, auxp2, plane);
00283                 auxtag3 = classifyFaceIN(p2,    p3, auxp1, plane);
00284             }
00285             return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
00286 
00287         case OUT_IN_OUT :
00288             auxp1 = BOP_intersectPlane(m_plane, p2, p1);
00289             auxp2 = BOP_intersectPlane(m_plane, p2, p3);
00290     
00291             // f1: auxp1 p2 , p2 auxp2
00292             auxtag1 = classifyFaceIN(auxp1, p2, auxp2, plane);
00293     
00294             // f2: p1 auxp1 , auxp1 auxp2;  f3: p1 auxp2 , auxp2 p3  ||  
00295             // f2: p3 auxp1, auxp1 auxp2  f3:p1 auxp1, auxp1 p3
00296             if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) {
00297                 auxtag2 = classifyFaceOUT(p1, auxp1, auxp2, plane);
00298                 auxtag3 = classifyFaceOUT(p1, auxp2, p3,    plane);
00299             }
00300             else {
00301                 auxtag2 = classifyFaceOUT(p3, auxp1, auxp2, plane);
00302                 auxtag3 = classifyFaceOUT(p1, auxp1, p3,    plane);
00303             }
00304             return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
00305     
00306         case IN_OUT_IN :
00307             auxp1 = BOP_intersectPlane(m_plane, p2, p1);
00308             auxp2 = BOP_intersectPlane(m_plane, p2, p3);
00309     
00310             // f1: auxp1 p2 , p2 auxp2
00311             auxtag1 = classifyFaceOUT(auxp1, p2, auxp2, plane);
00312     
00313             // f2: p1 auxp1 , auxp1 auxp2;  f3: p1 auxp2 , auxp2 p3  ||  
00314             // f2: p3 auxp1, auxp1 auxp2  f3:p1 auxp1, auxp1 p3
00315             if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) {
00316                 auxtag2 = classifyFaceIN(p1, auxp1, auxp2, plane);
00317                 auxtag3 = classifyFaceIN(p1, auxp2, p3,    plane);
00318             }
00319             else {
00320                 auxtag2 = classifyFaceIN(p3, auxp1, auxp2, plane);
00321                 auxtag3 = classifyFaceIN(p1, auxp1, p3,    plane);
00322             }
00323             return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
00324     
00325         case OUT_OUT_IN :
00326             auxp1 = BOP_intersectPlane(m_plane, p3, p1);
00327             auxp2 = BOP_intersectPlane(m_plane, p3, p2);
00328     
00329             // f1: auxp1 auxp2 , auxp2 p3
00330             auxtag1 = classifyFaceIN(auxp1, auxp2, p3, plane);
00331     
00332             // f2: p1 p2 , p2 auxp2;   f3:p1 auxp2 , auxp2 auxp1  ||
00333             // f2: p1 p2, p2 auxp1;  f3:p2 auxp2, auxp2 auxp1
00334             if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) {
00335                 auxtag2 = classifyFaceOUT(p1, p2,    auxp2, plane);
00336                 auxtag3 = classifyFaceOUT(p1, auxp2, auxp1, plane);
00337             }
00338             else {
00339                 auxtag2 = classifyFaceOUT(p1, p2,    auxp1, plane);
00340                 auxtag3 = classifyFaceOUT(p2, auxp2, auxp1, plane);
00341             }
00342             return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
00343 
00344         case IN_IN_OUT :
00345             auxp1 = BOP_intersectPlane(m_plane, p3, p1);
00346             auxp2 = BOP_intersectPlane(m_plane, p3, p2);
00347     
00348             // f1: auxp1 auxp2 , auxp2 p3
00349             auxtag1 = classifyFaceOUT(auxp1, auxp2, p3, plane);
00350     
00351             // f2: p1 p2 , p2 auxp2;   f3:p1 auxp2 , auxp2 auxp1  ||
00352             // f2: p1 p2, p2 auxp1;  f3:p2 auxp2, auxp2 auxp1
00353             if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) {
00354                 auxtag2 = classifyFaceIN(p1, p2,    auxp2, plane);
00355                 auxtag3 = classifyFaceIN(p1, auxp2, auxp1, plane);
00356             }
00357             else {
00358                 auxtag2 = classifyFaceIN(p1, p2,    auxp1, plane);
00359                 auxtag3 = classifyFaceIN(p2, auxp2, auxp1, plane);
00360             }
00361             return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
00362 
00363         default:
00364             return UNCLASSIFIED;
00365     }
00366 }
00367 
00375 BOP_TAG BOP_BSPNode::classifyFaceIN(const MT_Point3& p1, 
00376                                     const MT_Point3& p2, 
00377                                     const MT_Point3& p3, 
00378                                     const MT_Plane3& plane) const
00379 {
00380     if (m_inChild != NULL)
00381         return m_inChild->classifyFace(p1, p2, p3, plane);
00382     else
00383         return IN;
00384 }
00385 
00393 BOP_TAG BOP_BSPNode::classifyFaceOUT(const MT_Point3& p1, 
00394                                      const MT_Point3& p2, 
00395                                      const MT_Point3& p3, 
00396                                      const MT_Plane3& plane) const
00397 {
00398     if (m_outChild != NULL)
00399         return m_outChild->classifyFace(p1, p2, p3, plane);
00400     else
00401         return OUT;
00402 }
00403 
00413 BOP_TAG BOP_BSPNode::simplifiedClassifyFace(const MT_Point3& p1, 
00414                                             const MT_Point3& p2, 
00415                                             const MT_Point3& p3, 
00416                                             const MT_Plane3& plane) const
00417 {
00418     MT_Point3 ret[3];
00419 
00420     BOP_TAG tag = BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3));
00421 
00422     if ((tag & IN_IN_IN) != 0) {
00423         if ((tag & OUT_OUT_OUT) != 0) {     
00424           if (splitTriangle(ret,m_plane,p1,p2,p3,tag)<0)
00425             return simplifiedClassifyFaceIN(ret[0],ret[1],ret[2],plane);
00426           else
00427             return simplifiedClassifyFaceOUT(ret[0],ret[1],ret[2],plane);
00428         }
00429         else {
00430             return simplifiedClassifyFaceIN(p1,p2,p3,plane);
00431         }
00432     }
00433     else {
00434         if ((tag & OUT_OUT_OUT) != 0) {
00435             return simplifiedClassifyFaceOUT(p1,p2,p3,plane);
00436         }
00437         else {
00438             if (hasSameOrientation(plane)) {
00439                 return simplifiedClassifyFaceIN(p1,p2,p3,plane);
00440             }
00441             else {
00442                 return simplifiedClassifyFaceOUT(p1,p2,p3,plane);
00443             }
00444         }
00445     }
00446     
00447     return IN;
00448 }
00449 
00457 BOP_TAG BOP_BSPNode::simplifiedClassifyFaceIN(const MT_Point3& p1, 
00458                                               const MT_Point3& p2, 
00459                                               const MT_Point3& p3, 
00460                                               const MT_Plane3& plane) const
00461 {
00462     if (m_inChild != NULL)
00463         return m_inChild->simplifiedClassifyFace(p1, p2, p3, plane);
00464     else
00465         return IN;
00466 }
00467 
00475 BOP_TAG BOP_BSPNode::simplifiedClassifyFaceOUT(const MT_Point3& p1, 
00476                                                const MT_Point3& p2, 
00477                                                const MT_Point3& p3, 
00478                                                const MT_Plane3& plane) const
00479 {
00480     if (m_outChild != NULL)
00481         return m_outChild->simplifiedClassifyFace(p1, p2, p3, plane);
00482     else
00483         return OUT;
00484 }
00485 
00491 bool BOP_BSPNode::hasSameOrientation(const MT_Plane3& plane) const
00492 {
00493     return (BOP_orientation(m_plane,plane)>0);
00494 }
00495 
00500 int BOP_BSPNode::compChildren() const
00501 {
00502     unsigned int deep1 = (m_inChild == NULL?0:m_inChild->getDeep());
00503     unsigned int deep2 = (m_outChild == NULL?0:m_outChild->getDeep());
00504     
00505     if (deep1 == deep2)
00506         return 0;
00507     else if (deep1 < deep2)
00508         return -1;
00509     else
00510         return 1;
00511 }
00512 
00523 int BOP_BSPNode::splitTriangle(MT_Point3* res, 
00524                                const MT_Plane3& plane, 
00525                                const MT_Point3& p1, 
00526                                const MT_Point3& p2, 
00527                                const MT_Point3& p3, 
00528                                const BOP_TAG tag) const
00529 {
00530     switch (tag) {
00531         case IN_OUT_ON :
00532           if (compChildren()<0) {
00533             // f1: p1 new p3 || new = splitedge(p1,p2)
00534             res[0] = p1;
00535             res[1] = BOP_intersectPlane( plane, p1, p2 );
00536             res[2] = p3;
00537             return -1;
00538           }else{
00539             // f1: p2 new p3 || new = splitedge(p1,p2)
00540             res[0] = p2;
00541             res[1] = p3;
00542             res[2] = BOP_intersectPlane( plane, p1, p2 );
00543             return 1;
00544           }
00545         case OUT_IN_ON :
00546           if (compChildren()<0) {
00547             // f1: p2 new p3 || new = splitedge(p1,p2)
00548             res[0] = p2;
00549             res[1] = p3;
00550             res[2] = BOP_intersectPlane( plane, p1, p2 );
00551             return -1;
00552           }else{
00553             // f1: p1 new p3 || new = splitedge(p1,p2)
00554             res[0] = p1;
00555             res[1] = BOP_intersectPlane( plane, p1, p2 );
00556             res[2] = p3;
00557             return 1;
00558           }
00559         case IN_ON_OUT :
00560           if (compChildren()<0) {
00561             // f1: p1 p2 new || new = splitedge(p1,p3)
00562             res[0] = p1;
00563             res[1] = p2;
00564             res[2] = BOP_intersectPlane( plane, p1, p3 );
00565             return -1;
00566           }else{
00567             // f1: p2 p3 new || new = splitedge(p1,p3)
00568             res[0] = p2;
00569             res[1] = p3;
00570             res[2] = BOP_intersectPlane( plane, p1, p3 );
00571             return 1;
00572           }
00573         case OUT_ON_IN :
00574           if (compChildren()<0) {
00575             // f1: p2 p3 new || new = splitedge(p1,p3)
00576             res[0] = p2;
00577             res[1] = p3;
00578             res[2] = BOP_intersectPlane( plane, p1, p3 );
00579             return -1;
00580           }else{
00581             // f1: p1 p2 new || new = splitedge(p1,p3)
00582             res[0] = p1;
00583             res[1] = p2;
00584             res[2] = BOP_intersectPlane( plane, p1, p3 );
00585             return 1;
00586           }
00587         case ON_IN_OUT :
00588           if (compChildren()<0) {
00589             // f1: p1 p2 new || new = splitedge(p2,p3)
00590             res[0] = p1;
00591             res[1] = p2;
00592             res[2] = BOP_intersectPlane( plane, p2, p3 );
00593             return -1;
00594           }else{
00595             // f1: p1 p3 new || new = splitedge(p2,p3)
00596             res[0] = p1;
00597             res[1] = BOP_intersectPlane( plane, p2, p3 );
00598             res[2] = p3;
00599             return 1;
00600           }
00601         case ON_OUT_IN :
00602           if (compChildren()<0) {
00603             // f1: p1 p2 new || new = splitedge(p2,p3)
00604             res[0] = p1;
00605             res[1] = BOP_intersectPlane( plane, p2, p3 );
00606             res[2] = p3;
00607             return -1;
00608           }else{
00609             // f1: p1 p2 new || new = splitedge(p2,p3)
00610             res[0] = p1;
00611             res[1] = p2;
00612             res[2] = BOP_intersectPlane( plane, p2, p3 );
00613             return 1;
00614           }
00615         case IN_OUT_OUT :
00616           if (compChildren()<=0) {
00617             // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
00618             res[0] = p1;
00619             res[1] = BOP_intersectPlane( plane, p1, p2 );
00620             res[2] = BOP_intersectPlane( plane, p1, p3 );
00621             return -1;
00622           }else{
00623             // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
00624             res[0] = BOP_intersectPlane( plane, p1, p2 );
00625             res[1] = p2;
00626             res[2] = p3;
00627             return 1;
00628           }
00629         case OUT_IN_IN :
00630           if (compChildren()<0) {
00631             // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
00632             res[0] = BOP_intersectPlane( plane, p1, p2 );
00633             res[1] = p2;
00634             res[2] = p3;
00635             return -1;
00636           }else {
00637             // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
00638             res[0] = p1;
00639             res[1] = BOP_intersectPlane( plane, p1, p2 );
00640             res[2] = BOP_intersectPlane( plane, p1, p3 );
00641             return 1;
00642           }
00643         case OUT_IN_OUT :
00644           if (compChildren()<=0) {
00645             // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
00646             res[0] = BOP_intersectPlane( plane, p2, p1 );
00647             res[1] = p2;
00648             res[2] = BOP_intersectPlane( plane, p2, p3 );
00649             return -1;
00650           }else {
00651             // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
00652             res[0] = p1;
00653             res[1] = BOP_intersectPlane( plane, p2, p1 );
00654             res[2] = BOP_intersectPlane( plane, p2, p3 );
00655             return 1;
00656           }
00657         case IN_OUT_IN :
00658           if (compChildren()<0) {
00659             // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
00660             res[0] = p1;
00661             res[1] = BOP_intersectPlane( plane, p2, p1 );
00662             res[2] = BOP_intersectPlane( plane, p2, p3 );
00663             return -1;
00664           }else{
00665             // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
00666             res[0] = BOP_intersectPlane( plane, p2, p1 );
00667             res[1] = p2;
00668             res[2] = BOP_intersectPlane( plane, p2, p3 );
00669             return 1;
00670           }
00671         case OUT_OUT_IN :
00672           if (compChildren()<=0) {
00673             // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
00674             res[0] = BOP_intersectPlane( plane, p3, p1 );
00675             res[1] = BOP_intersectPlane( plane, p3, p2 );
00676             res[2] = p3;
00677             return -1;
00678           }else{
00679             // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
00680             res[0] = BOP_intersectPlane( plane, p3, p1 );
00681             res[1] = p1;
00682             res[2] = p2;
00683             return 1;
00684           }
00685         case IN_IN_OUT :
00686           if (compChildren()<0) {
00687             // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
00688             res[0] = BOP_intersectPlane( plane, p3, p1 );
00689             res[1] = p1;
00690             res[2] = p2;
00691             return -1;
00692           }else{
00693             // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
00694             res[0] = BOP_intersectPlane( plane, p3, p1 );
00695             res[1] = BOP_intersectPlane( plane, p3, p2 );
00696             res[2] = p3;
00697             return 1;
00698           }
00699     default:
00700       return 0;
00701     }
00702 }
00703 
00707 void BOP_BSPNode::print(unsigned int deep)
00708 {
00709     std::cout << "(" << deep << "," << m_plane << ")," << std::endl;
00710     if (m_inChild != NULL)
00711         m_inChild->print(deep + 1);
00712     else
00713         std::cout << "(" << deep+1 << ",None)," << std::endl;
00714     if (m_outChild != NULL)
00715         m_outChild->print(deep + 1);
00716     else
00717         std::cout << "(" << deep+1 << ",None)," << std::endl;
00718 }