Fix for very old bug in Boolean code. BSP trees were calculated incorrectly,
authorKen Hughes <khughes@pacific.edu>
Thu, 14 Jun 2007 14:42:35 +0000 (14:42 +0000)
committerKen Hughes <khughes@pacific.edu>
Thu, 14 Jun 2007 14:42:35 +0000 (14:42 +0000)
which caused faces of convex objects to be classified wrongly.  Also removed
some dead code.  For convex objects, the BSP trees would also be literally
orders of magnitude larger than they were supposed to be (one test with a
5000 face torus reduced the BSP tree size from 5.96 million nodes to just 72.1
thousand).

intern/boolop/intern/BOP_BSPNode.cpp
intern/boolop/intern/BOP_BSPNode.h
intern/boolop/intern/BOP_BSPTree.cpp
intern/boolop/intern/BOP_BSPTree.h
intern/boolop/intern/BOP_Interface.cpp

index af5c40baad99fc2bc3156c8b147bd06462395390..646e8c22bd36d70b4ea8ff76150f794e3a2c3484 100644 (file)
@@ -58,30 +58,82 @@ BOP_BSPNode::~BOP_BSPNode()
 
 /**
  * Adds a new face to this BSP tree.
- * @param p1 first face point.
- * @param p2 second face point.
- * @param p3 third face point.
+ * @param pts vector containing face points
  * @param plane face plane.
  */
-unsigned int BOP_BSPNode::addFace(const MT_Point3& p1, 
-                                                                 const MT_Point3& p2, 
-                                                                 const MT_Point3& p3, 
-                                                                 const MT_Plane3& plane)
+
+unsigned int BOP_BSPNode::addFace(BOP_BSPPoints pts,
+                                                                 const MT_Plane3& plane )
 {
        unsigned int newDeep = 0;
-       BOP_TAG tag = BOP_createTAG(testPoint(p1), testPoint(p2), testPoint(p3));
-       if ((tag & IN_IN_IN) != 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(p1, p2, p3, plane) + 1;
+                       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.
+
+               BOP_IT_BSPPoints 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 ((tag & OUT_OUT_OUT) != 0){
                if (m_outChild != NULL)
-                       newDeep = MT_max(newDeep, m_outChild->addFace(p1, p2, p3, plane) + 1);
+                       newDeep = MT_max(newDeep, m_outChild->addFace(outside, plane) + 1);
                else {
                        m_outChild = new BOP_BSPNode(plane);
                        newDeep = MT_max(newDeep,(unsigned int)2);
@@ -653,19 +705,13 @@ int BOP_BSPNode::splitTriangle(MT_Point3* res,
  */
 void BOP_BSPNode::print(unsigned int deep)
 {
-       for (unsigned int i = 0; i < deep; ++i)
-               cout << "  ";
-       
-       cout << m_plane.x() << ", ";
-       cout << m_plane.y() << ", ";
-       cout << m_plane.z() << ", ";
-       cout << m_plane.w() << endl;
-       if (m_inChild != NULL) {
-               cout << "IN:";
+       cout << "(" << deep << "," << m_plane << ")," << endl;
+       if (m_inChild != NULL)
                m_inChild->print(deep + 1);
-       }
-       if (m_outChild != NULL) {
-               cout << "OUT:";
+       else
+               cout << "(" << deep+1 << ",None)," << endl;
+       if (m_outChild != NULL)
                m_outChild->print(deep + 1);
-       }
+       else
+               cout << "(" << deep+1 << ",None)," << endl;
 }
index d4f7f1c28a112465700a421ee3fc0f6e66f6c33e..39a84b94dec25f77ba78e32c6c40123b01f7fc84 100644 (file)
@@ -35,6 +35,9 @@
 #include "BOP_Tag.h"
 #include "BOP_Face.h"
 
+typedef vector<MT_Point3> BOP_BSPPoints;
+typedef vector<MT_Point3>::iterator BOP_IT_BSPPoints;
+
 class BOP_BSPNode
 {
 protected:
@@ -47,9 +50,7 @@ public:
        // Construction methods
        BOP_BSPNode(const MT_Plane3& plane);
        ~BOP_BSPNode();
-       unsigned int addFace(const MT_Point3& p1, 
-                                                const MT_Point3& p2, 
-                                                const MT_Point3& p3, 
+       unsigned int addFace(BOP_BSPPoints pts, 
                                                 const MT_Plane3& plane);
        BOP_TAG classifyFace(const MT_Point3& p1, 
                                                 const MT_Point3& p2, 
index 4e5c171bc83113ecbe94a0bff1268aa28ac54daf..3ae375294cd1bfd7c962913df54f0d6e4fcbe32b 100644 (file)
@@ -69,6 +69,7 @@ void BOP_BSPTree::addMesh(BOP_Mesh* mesh, BOP_Faces& facesList)
  * @param mesh Input data for BSP tree.
  * @param face index to mesh face.
  */
+
 void BOP_BSPTree::addFace(BOP_Mesh* mesh, BOP_Face* face)
 {
        addFace(mesh->getVertex(face->getVertex(0))->getPoint(),
@@ -91,8 +92,15 @@ void BOP_BSPTree::addFace(const MT_Point3& p1,
 {
        if (m_root == NULL)
                m_root = new BOP_BSPNode(plane);
-       else
-               m_root->addFace(p1,p2,p3,plane);
+       else {
+               BOP_BSPPoints pts;
+
+               pts.push_back(p1);
+               pts.push_back(p2);
+               pts.push_back(p3);
+
+               m_root->addFace(pts,plane);
+       }
 
        // update bounding box
        m_bbox.add(p1);
@@ -170,37 +178,6 @@ unsigned int BOP_BSPTree::getDeep() const
          return 0;
 }
 
-/**
- * Computes the bounding BSP data.
- */
-void BOP_BSPTree::computeBox()
-{
-       if ( m_root != NULL ) {
-               MT_Point3 p1(m_bbox.m_minX,m_bbox.m_minY,m_bbox.m_minZ);
-               MT_Point3 p2(m_bbox.m_maxX,m_bbox.m_minY,m_bbox.m_minZ);
-               MT_Point3 p3(m_bbox.m_maxX,m_bbox.m_maxY,m_bbox.m_minZ);
-               MT_Point3 p4(m_bbox.m_minX,m_bbox.m_maxY,m_bbox.m_minZ);
-               MT_Point3 p5(m_bbox.m_minX,m_bbox.m_minY,m_bbox.m_maxZ);
-               MT_Point3 p6(m_bbox.m_maxX,m_bbox.m_minY,m_bbox.m_maxZ);
-               MT_Point3 p7(m_bbox.m_maxX,m_bbox.m_maxY,m_bbox.m_maxZ);
-               MT_Point3 p8(m_bbox.m_minX,m_bbox.m_maxY,m_bbox.m_maxZ);        
-               
-               MT_Plane3 plane1(p3,p2,p1);
-               MT_Plane3 plane2(p5,p6,p7);
-               MT_Plane3 plane3(p1,p2,p6);
-               MT_Plane3 plane4(p8,p7,p3);
-               MT_Plane3 plane5(p2,p3,p7);
-               MT_Plane3 plane6(p1,p5,p8);
-               
-               BOP_BSPNode bsp(plane1);
-               bsp.addFace(p5,p6,p7,plane2);
-               bsp.addFace(p1,p2,p6,plane3);
-               bsp.addFace(p8,p7,p3,plane4);
-               bsp.addFace(p2,p3,p7,plane5);
-               bsp.addFace(p1,p5,p8,plane6);
-       }
-}
-
 /**
  * Prints debug information.
  */
index 7e5b5a4fa76589ea3bfd0a78a69f8b8e81934b95..412d5a407536cfaaabce060149288b3845e8143e 100644 (file)
@@ -65,7 +65,6 @@ public:
                                                                   const MT_Point3& p3, 
                                                                   const MT_Plane3& plane) const;
        unsigned int getDeep() const;
-       void computeBox();
        void print();
        inline void setRoot(BOP_BSPNode* root) {m_root=root;};
        inline BOP_BSPNode* getRoot() const {return m_root;};
index 6d1ae56da2d41912e9ef85f3544035240a1e91f6..3c61fd6c7b895d2f1bd8b2fc2898cdad6378c83c 100644 (file)
@@ -152,12 +152,10 @@ BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
        // Create BSPs trees for mesh A & B
        BOP_BSPTree bspA;
        bspA.addMesh(meshC, *facesA);
-       bspA.computeBox();
 
        BOP_BSPTree bspB;
        bspB.addMesh(meshC, *facesB);
-       bspB.computeBox();
-       
+
        #ifdef DEBUG
        c = chrono.stamp(); t += c;
        cout << "Create BSP     " << c << endl;