BOP_BSPNode.cpp

Go to the documentation of this file.

/*
 * ***** BEGIN GPL LICENSE BLOCK *****
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
 * All rights reserved.
 *
 * The Original Code is: all of this file.
 *
 * Contributor(s): none yet.
 *
 * ***** END GPL LICENSE BLOCK *****
 */

#include "BOP_MathUtils.h"
#include "BOP_BSPNode.h"
#include "MT_assert.h"
#include "MT_MinMax.h"
#include <iostream>

BOP_BSPNode::BOP_BSPNode(const MT_Plane3& plane)
{
    m_plane      = plane;
    m_inChild    = NULL;
    m_outChild   = NULL;
    m_deep       = 1;
}

BOP_BSPNode::~BOP_BSPNode()
{
    if (m_inChild!=NULL) delete m_inChild;
    if (m_outChild!=NULL) delete m_outChild;
}

unsigned int BOP_BSPNode::addFace(const BOP_BSPPoints& pts,
                                  const MT_Plane3& plane )
{
    unsigned int newDeep = 0;
    BOP_TAG tag = ON;

    // find out if any points on the "face" lie in either half-space
    BOP_IT_BSPPoints ptsEnd = pts.end();
    for(BOP_IT_BSPPoints itp=pts.begin();itp!=ptsEnd;itp++){
        tag = (BOP_TAG) ((int) tag | (int)testPoint(*itp));
    }
 
    if (tag == ON) { }      // face lies on hyperplane: do nothing
    else if ((tag & IN) != 0 && (tag & OUT) == 0) { // face is entirely on inside
        if (m_inChild != NULL)
            newDeep = m_inChild->addFace(pts, plane) + 1;
        else {
            m_inChild = new BOP_BSPNode(plane);
            newDeep = 2;
        }    
    } else if ((tag & OUT) != 0 && (tag & IN) == 0) { // face is entirely on outside
        if (m_outChild != NULL)
            newDeep = m_outChild->addFace(pts, plane) + 1;
        else {
            m_outChild = new BOP_BSPNode(plane);
            newDeep = 2;
        }      
    } else { // face lies in both half-spaces: split it
        BOP_BSPPoints inside, outside;
        MT_Point3 lpoint= pts[pts.size()-1];
        BOP_TAG ltag = testPoint(lpoint);
        BOP_TAG tstate = ltag;

        // classify each line segment, looking for endpoints which lie on different
        // sides of the hyperplane.

        ptsEnd = pts.end();
        for(BOP_IT_BSPPoints itp=pts.begin();itp!=ptsEnd;itp++){
            MT_Point3 npoint= *itp;
            BOP_TAG ntag = testPoint(npoint);

            if(ltag != ON) {    // last point not on hyperplane
                if(tstate == IN) {
                    if (m_inChild != NULL) inside.push_back(lpoint);
                } else {
                    if (m_outChild != NULL) outside.push_back(lpoint);
                }
                if(ntag != ON && ntag != tstate) {  // last, self in different half-spaces 
                    MT_Point3 mpoint = BOP_intersectPlane( m_plane, lpoint, npoint );
                    if (m_inChild != NULL) inside.push_back(mpoint);
                    if (m_outChild != NULL) outside.push_back(mpoint);
                    tstate = ntag;
                }
            } else {            // last point on hyperplane, so we're switching
                                // half-spaces
                                // boundary point belong to both faces
                if (m_inChild != NULL) inside.push_back(lpoint);    
                if (m_outChild != NULL) outside.push_back(lpoint);
                tstate = ntag;  // state changes to new point tag
            }
            lpoint = npoint;    // save point, tag for next iteration
            ltag = ntag;
        }

        if (m_inChild != NULL)
            newDeep = m_inChild->addFace(inside, plane) + 1;
        else {
            m_inChild = new BOP_BSPNode(plane);
            newDeep = 2;
        }    
        if (m_outChild != NULL)
            newDeep = MT_max(newDeep, m_outChild->addFace(outside, plane) + 1);
        else {
            m_outChild = new BOP_BSPNode(plane);
            newDeep = MT_max(newDeep,(unsigned int)2);
        }      
    }
    
    // update the deep attribute
    m_deep = MT_max(m_deep,newDeep);
    
    return m_deep;
}

BOP_TAG BOP_BSPNode::testPoint(const MT_Point3& p) const
{
  return BOP_createTAG(BOP_classify(p,m_plane));

}

BOP_TAG BOP_BSPNode::classifyFace(const MT_Point3& p1, 
                                  const MT_Point3& p2, 
                                  const MT_Point3& p3, 
                                  const MT_Plane3& plane) const
{
    // local variables
    MT_Point3 auxp1, auxp2;
    BOP_TAG auxtag1, auxtag2, auxtag3;

    switch(BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3))) {
        // Classify the face on the IN side
        case IN_IN_IN : 
            return classifyFaceIN(p1, p2, p3, plane);
        case IN_IN_ON :
        case IN_ON_IN :
        case ON_IN_IN :
        case IN_ON_ON :
        case ON_IN_ON :
        case ON_ON_IN :
            return BOP_addON(classifyFaceIN(p1, p2, p3, plane));
    
        // Classify the face on the OUT side
        case OUT_OUT_OUT :
            return classifyFaceOUT(p1, p2, p3, plane);
        case OUT_OUT_ON :
        case OUT_ON_OUT :
        case ON_OUT_OUT :
        case ON_ON_OUT :
        case ON_OUT_ON :
        case OUT_ON_ON :
            return BOP_addON(classifyFaceOUT(p1, p2, p3, plane));
    
        // Classify the ON face depending on it plane normal
        case ON_ON_ON :
            if (hasSameOrientation(plane))
                return BOP_addON(classifyFaceIN(p1, p2, p3, plane));
            else
                return BOP_addON(classifyFaceOUT(p1, p2, p3, plane));

        // Classify the face IN/OUT and one vertex ON
        // becouse only one ON, only one way to subdivide the face
        case IN_OUT_ON :
            auxp1 = BOP_intersectPlane(m_plane, p1, p2);
            auxtag1 = classifyFaceIN( p1,    auxp1 , p3, plane);
            auxtag2 = classifyFaceOUT(auxp1, p2,     p3, plane);
            return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);

        case OUT_IN_ON :
            auxp1 = BOP_intersectPlane(m_plane, p1, p2);
            auxtag1 = classifyFaceOUT(p1,    auxp1, p3, plane);
            auxtag2 = classifyFaceIN( auxp1, p2,    p3, plane);
            return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);

        case IN_ON_OUT :
            auxp1 = BOP_intersectPlane(m_plane, p1, p3);
            auxtag1 = classifyFaceIN( p1, p2, auxp1, plane);
            auxtag2 = classifyFaceOUT(p2, p3, auxp1, plane);
            return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);

        case OUT_ON_IN :
            auxp1 = BOP_intersectPlane(m_plane, p1, p3);
            auxtag1 = classifyFaceOUT(p1, p2, auxp1, plane);
            auxtag2 = classifyFaceIN( p2, p3, auxp1, plane);
            return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);

        case ON_IN_OUT :
            auxp1 = BOP_intersectPlane(m_plane, p2, p3);
            auxtag1 = classifyFaceIN( p1,    p2, auxp1, plane);
            auxtag2 = classifyFaceOUT(auxp1, p3, p1,    plane);
            return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);

        case ON_OUT_IN :
            auxp1 = BOP_intersectPlane(m_plane, p2, p3);
            auxtag1 = classifyFaceOUT(p1,    p2, auxp1, plane);
            auxtag2 = classifyFaceIN( auxp1, p3, p1,    plane);
            return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);

        // Classify IN/OUT face without ON vertices.
        // Two ways to divide the triangle, 
        // will chose the least degenerated sub-triangles.
        case IN_OUT_OUT :
            auxp1 = BOP_intersectPlane(m_plane, p1, p2);
            auxp2 = BOP_intersectPlane(m_plane, p1, p3);
    
            // f1: p1 auxp1 , auxp1 auxp2
            auxtag1 = classifyFaceIN(p1, auxp1, auxp2, plane);
    
            // f2: auxp1 p2 , p2 auxp2;  f3: p2 p3 , p3 auxp2  ||  
            // f2: auxp1 p3, p3 auxp2;   f3: p2 p3 , p3 auxp1
            if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) {
                auxtag2 = classifyFaceOUT(auxp1, p2, auxp2, plane);
                auxtag3 = classifyFaceOUT(p2,    p3, auxp2, plane);
            }
            else {
                auxtag2 = classifyFaceOUT(auxp1, p3, auxp2, plane);
                auxtag3 = classifyFaceOUT(p2,    p3, auxp1, plane);
            }
            return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);

        case OUT_IN_IN :
            auxp1 = BOP_intersectPlane(m_plane, p1, p2);
            auxp2 = BOP_intersectPlane(m_plane, p1, p3);
    
            // f1: p1 auxp1 , auxp1 auxp2
            auxtag1 = classifyFaceOUT(p1, auxp1, auxp2, plane);
    
            // f2: auxp1 p2 , p2 auxp2;  f3: p2 p3 , p3 auxp2  ||
            // f2: auxp1 p3, p3 auxp2;  f3: p2 p3 , p3 auxp1
            if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) {
                auxtag2 = classifyFaceIN(auxp1, p2, auxp2, plane);
                auxtag3 = classifyFaceIN(p2, p3, auxp2, plane);
            }
            else {
                auxtag2 = classifyFaceIN(auxp1, p3, auxp2, plane);
                auxtag3 = classifyFaceIN(p2,    p3, auxp1, plane);
            }
            return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);

        case OUT_IN_OUT :
            auxp1 = BOP_intersectPlane(m_plane, p2, p1);
            auxp2 = BOP_intersectPlane(m_plane, p2, p3);
    
            // f1: auxp1 p2 , p2 auxp2
            auxtag1 = classifyFaceIN(auxp1, p2, auxp2, plane);
    
            // f2: p1 auxp1 , auxp1 auxp2;  f3: p1 auxp2 , auxp2 p3  ||  
            // f2: p3 auxp1, auxp1 auxp2  f3:p1 auxp1, auxp1 p3
            if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) {
                auxtag2 = classifyFaceOUT(p1, auxp1, auxp2, plane);
                auxtag3 = classifyFaceOUT(p1, auxp2, p3,    plane);
            }
            else {
                auxtag2 = classifyFaceOUT(p3, auxp1, auxp2, plane);
                auxtag3 = classifyFaceOUT(p1, auxp1, p3,    plane);
            }
            return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
    
        case IN_OUT_IN :
            auxp1 = BOP_intersectPlane(m_plane, p2, p1);
            auxp2 = BOP_intersectPlane(m_plane, p2, p3);
    
            // f1: auxp1 p2 , p2 auxp2
            auxtag1 = classifyFaceOUT(auxp1, p2, auxp2, plane);
    
            // f2: p1 auxp1 , auxp1 auxp2;  f3: p1 auxp2 , auxp2 p3  ||  
            // f2: p3 auxp1, auxp1 auxp2  f3:p1 auxp1, auxp1 p3
            if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) {
                auxtag2 = classifyFaceIN(p1, auxp1, auxp2, plane);
                auxtag3 = classifyFaceIN(p1, auxp2, p3,    plane);
            }
            else {
                auxtag2 = classifyFaceIN(p3, auxp1, auxp2, plane);
                auxtag3 = classifyFaceIN(p1, auxp1, p3,    plane);
            }
            return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
    
        case OUT_OUT_IN :
            auxp1 = BOP_intersectPlane(m_plane, p3, p1);
            auxp2 = BOP_intersectPlane(m_plane, p3, p2);
    
            // f1: auxp1 auxp2 , auxp2 p3
            auxtag1 = classifyFaceIN(auxp1, auxp2, p3, plane);
    
            // f2: p1 p2 , p2 auxp2;   f3:p1 auxp2 , auxp2 auxp1  ||
            // f2: p1 p2, p2 auxp1;  f3:p2 auxp2, auxp2 auxp1
            if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) {
                auxtag2 = classifyFaceOUT(p1, p2,    auxp2, plane);
                auxtag3 = classifyFaceOUT(p1, auxp2, auxp1, plane);
            }
            else {
                auxtag2 = classifyFaceOUT(p1, p2,    auxp1, plane);
                auxtag3 = classifyFaceOUT(p2, auxp2, auxp1, plane);
            }
            return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);

        case IN_IN_OUT :
            auxp1 = BOP_intersectPlane(m_plane, p3, p1);
            auxp2 = BOP_intersectPlane(m_plane, p3, p2);
    
            // f1: auxp1 auxp2 , auxp2 p3
            auxtag1 = classifyFaceOUT(auxp1, auxp2, p3, plane);
    
            // f2: p1 p2 , p2 auxp2;   f3:p1 auxp2 , auxp2 auxp1  ||
            // f2: p1 p2, p2 auxp1;  f3:p2 auxp2, auxp2 auxp1
            if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) {
                auxtag2 = classifyFaceIN(p1, p2,    auxp2, plane);
                auxtag3 = classifyFaceIN(p1, auxp2, auxp1, plane);
            }
            else {
                auxtag2 = classifyFaceIN(p1, p2,    auxp1, plane);
                auxtag3 = classifyFaceIN(p2, auxp2, auxp1, plane);
            }
            return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);

        default:
            return UNCLASSIFIED;
    }
}

BOP_TAG BOP_BSPNode::classifyFaceIN(const MT_Point3& p1, 
                                    const MT_Point3& p2, 
                                    const MT_Point3& p3, 
                                    const MT_Plane3& plane) const
{
    if (m_inChild != NULL)
        return m_inChild->classifyFace(p1, p2, p3, plane);
    else
        return IN;
}

BOP_TAG BOP_BSPNode::classifyFaceOUT(const MT_Point3& p1, 
                                     const MT_Point3& p2, 
                                     const MT_Point3& p3, 
                                     const MT_Plane3& plane) const
{
    if (m_outChild != NULL)
        return m_outChild->classifyFace(p1, p2, p3, plane);
    else
        return OUT;
}

BOP_TAG BOP_BSPNode::simplifiedClassifyFace(const MT_Point3& p1, 
                                            const MT_Point3& p2, 
                                            const MT_Point3& p3, 
                                            const MT_Plane3& plane) const
{
    MT_Point3 ret[3];

    BOP_TAG tag = BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3));

    if ((tag & IN_IN_IN) != 0) {
        if ((tag & OUT_OUT_OUT) != 0) {     
          if (splitTriangle(ret,m_plane,p1,p2,p3,tag)<0)
            return simplifiedClassifyFaceIN(ret[0],ret[1],ret[2],plane);
          else
            return simplifiedClassifyFaceOUT(ret[0],ret[1],ret[2],plane);
        }
        else {
            return simplifiedClassifyFaceIN(p1,p2,p3,plane);
        }
    }
    else {
        if ((tag & OUT_OUT_OUT) != 0) {
            return simplifiedClassifyFaceOUT(p1,p2,p3,plane);
        }
        else {
            if (hasSameOrientation(plane)) {
                return simplifiedClassifyFaceIN(p1,p2,p3,plane);
            }
            else {
                return simplifiedClassifyFaceOUT(p1,p2,p3,plane);
            }
        }
    }
    
    return IN;
}

BOP_TAG BOP_BSPNode::simplifiedClassifyFaceIN(const MT_Point3& p1, 
                                              const MT_Point3& p2, 
                                              const MT_Point3& p3, 
                                              const MT_Plane3& plane) const
{
    if (m_inChild != NULL)
        return m_inChild->simplifiedClassifyFace(p1, p2, p3, plane);
    else
        return IN;
}

BOP_TAG BOP_BSPNode::simplifiedClassifyFaceOUT(const MT_Point3& p1, 
                                               const MT_Point3& p2, 
                                               const MT_Point3& p3, 
                                               const MT_Plane3& plane) const
{
    if (m_outChild != NULL)
        return m_outChild->simplifiedClassifyFace(p1, p2, p3, plane);
    else
        return OUT;
}

bool BOP_BSPNode::hasSameOrientation(const MT_Plane3& plane) const
{
    return (BOP_orientation(m_plane,plane)>0);
}

int BOP_BSPNode::compChildren() const
{
    unsigned int deep1 = (m_inChild == NULL?0:m_inChild->getDeep());
    unsigned int deep2 = (m_outChild == NULL?0:m_outChild->getDeep());
    
    if (deep1 == deep2)
        return 0;
    else if (deep1 < deep2)
        return -1;
    else
        return 1;
}

int BOP_BSPNode::splitTriangle(MT_Point3* res, 
                               const MT_Plane3& plane, 
                               const MT_Point3& p1, 
                               const MT_Point3& p2, 
                               const MT_Point3& p3, 
                               const BOP_TAG tag) const
{
    switch (tag) {
        case IN_OUT_ON :
          if (compChildren()<0) {
            // f1: p1 new p3 || new = splitedge(p1,p2)
            res[0] = p1;
            res[1] = BOP_intersectPlane( plane, p1, p2 );
            res[2] = p3;
            return -1;
          }else{
            // f1: p2 new p3 || new = splitedge(p1,p2)
            res[0] = p2;
            res[1] = p3;
            res[2] = BOP_intersectPlane( plane, p1, p2 );
            return 1;
          }
        case OUT_IN_ON :
          if (compChildren()<0) {
            // f1: p2 new p3 || new = splitedge(p1,p2)
            res[0] = p2;
            res[1] = p3;
            res[2] = BOP_intersectPlane( plane, p1, p2 );
            return -1;
          }else{
            // f1: p1 new p3 || new = splitedge(p1,p2)
            res[0] = p1;
            res[1] = BOP_intersectPlane( plane, p1, p2 );
            res[2] = p3;
            return 1;
          }
        case IN_ON_OUT :
          if (compChildren()<0) {
            // f1: p1 p2 new || new = splitedge(p1,p3)
            res[0] = p1;
            res[1] = p2;
            res[2] = BOP_intersectPlane( plane, p1, p3 );
            return -1;
          }else{
            // f1: p2 p3 new || new = splitedge(p1,p3)
            res[0] = p2;
            res[1] = p3;
            res[2] = BOP_intersectPlane( plane, p1, p3 );
            return 1;
          }
        case OUT_ON_IN :
          if (compChildren()<0) {
            // f1: p2 p3 new || new = splitedge(p1,p3)
            res[0] = p2;
            res[1] = p3;
            res[2] = BOP_intersectPlane( plane, p1, p3 );
            return -1;
          }else{
            // f1: p1 p2 new || new = splitedge(p1,p3)
            res[0] = p1;
            res[1] = p2;
            res[2] = BOP_intersectPlane( plane, p1, p3 );
            return 1;
          }
        case ON_IN_OUT :
          if (compChildren()<0) {
            // f1: p1 p2 new || new = splitedge(p2,p3)
            res[0] = p1;
            res[1] = p2;
            res[2] = BOP_intersectPlane( plane, p2, p3 );
            return -1;
          }else{
            // f1: p1 p3 new || new = splitedge(p2,p3)
            res[0] = p1;
            res[1] = BOP_intersectPlane( plane, p2, p3 );
            res[2] = p3;
            return 1;
          }
        case ON_OUT_IN :
          if (compChildren()<0) {
            // f1: p1 p2 new || new = splitedge(p2,p3)
            res[0] = p1;
            res[1] = BOP_intersectPlane( plane, p2, p3 );
            res[2] = p3;
            return -1;
          }else{
            // f1: p1 p2 new || new = splitedge(p2,p3)
            res[0] = p1;
            res[1] = p2;
            res[2] = BOP_intersectPlane( plane, p2, p3 );
            return 1;
          }
        case IN_OUT_OUT :
          if (compChildren()<=0) {
            // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
            res[0] = p1;
            res[1] = BOP_intersectPlane( plane, p1, p2 );
            res[2] = BOP_intersectPlane( plane, p1, p3 );
            return -1;
          }else{
            // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
            res[0] = BOP_intersectPlane( plane, p1, p2 );
            res[1] = p2;
            res[2] = p3;
            return 1;
          }
        case OUT_IN_IN :
          if (compChildren()<0) {
            // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
            res[0] = BOP_intersectPlane( plane, p1, p2 );
            res[1] = p2;
            res[2] = p3;
            return -1;
          }else {
            // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
            res[0] = p1;
            res[1] = BOP_intersectPlane( plane, p1, p2 );
            res[2] = BOP_intersectPlane( plane, p1, p3 );
            return 1;
          }
        case OUT_IN_OUT :
          if (compChildren()<=0) {
            // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
            res[0] = BOP_intersectPlane( plane, p2, p1 );
            res[1] = p2;
            res[2] = BOP_intersectPlane( plane, p2, p3 );
            return -1;
          }else {
            // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
            res[0] = p1;
            res[1] = BOP_intersectPlane( plane, p2, p1 );
            res[2] = BOP_intersectPlane( plane, p2, p3 );
            return 1;
          }
        case IN_OUT_IN :
          if (compChildren()<0) {
            // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
            res[0] = p1;
            res[1] = BOP_intersectPlane( plane, p2, p1 );
            res[2] = BOP_intersectPlane( plane, p2, p3 );
            return -1;
          }else{
            // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
            res[0] = BOP_intersectPlane( plane, p2, p1 );
            res[1] = p2;
            res[2] = BOP_intersectPlane( plane, p2, p3 );
            return 1;
          }
        case OUT_OUT_IN :
          if (compChildren()<=0) {
            // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
            res[0] = BOP_intersectPlane( plane, p3, p1 );
            res[1] = BOP_intersectPlane( plane, p3, p2 );
            res[2] = p3;
            return -1;
          }else{
            // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
            res[0] = BOP_intersectPlane( plane, p3, p1 );
            res[1] = p1;
            res[2] = p2;
            return 1;
          }
        case IN_IN_OUT :
          if (compChildren()<0) {
            // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
            res[0] = BOP_intersectPlane( plane, p3, p1 );
            res[1] = p1;
            res[2] = p2;
            return -1;
          }else{
            // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
            res[0] = BOP_intersectPlane( plane, p3, p1 );
            res[1] = BOP_intersectPlane( plane, p3, p2 );
            res[2] = p3;
            return 1;
          }
    default:
      return 0;
    }
}

void BOP_BSPNode::print(unsigned int deep)
{
    std::cout << "(" << deep << "," << m_plane << ")," << std::endl;
    if (m_inChild != NULL)
        m_inChild->print(deep + 1);
    else
        std::cout << "(" << deep+1 << ",None)," << std::endl;
    if (m_outChild != NULL)
        m_outChild->print(deep + 1);
    else
        std::cout << "(" << deep+1 << ",None)," << std::endl;
}