Fix for very old bug in Boolean code. BSP trees were calculated incorrectly,

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).

5 files changed, 88 insertions, 67 deletions

diff --git a/intern/boolop/intern/BOP_BSPNode.cpp b/intern/boolop/intern/BOP_BSPNode.cpp
index af5c40baad9..646e8c22bd3 100644
--- a/intern/boolop/intern/BOP_BSPNode.cpp
+++ b/intern/boolop/intern/BOP_BSPNode.cpp
@@ -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;
 }
diff --git a/intern/boolop/intern/BOP_BSPNode.h b/intern/boolop/intern/BOP_BSPNode.h
index d4f7f1c28a1..39a84b94dec 100644
--- a/intern/boolop/intern/BOP_BSPNode.h
+++ b/intern/boolop/intern/BOP_BSPNode.h
@@ -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, 
diff --git a/intern/boolop/intern/BOP_BSPTree.cpp b/intern/boolop/intern/BOP_BSPTree.cpp
index 4e5c171bc83..3ae375294cd 100644
--- a/intern/boolop/intern/BOP_BSPTree.cpp
+++ b/intern/boolop/intern/BOP_BSPTree.cpp
@@ -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);
@@ -171,37 +179,6 @@ unsigned int BOP_BSPTree::getDeep() const
 }
 
 /**
- * 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.
  */
 void BOP_BSPTree::print()
diff --git a/intern/boolop/intern/BOP_BSPTree.h b/intern/boolop/intern/BOP_BSPTree.h
index 7e5b5a4fa76..412d5a40753 100644
--- a/intern/boolop/intern/BOP_BSPTree.h
+++ b/intern/boolop/intern/BOP_BSPTree.h
@@ -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;};
diff --git a/intern/boolop/intern/BOP_Interface.cpp b/intern/boolop/intern/BOP_Interface.cpp
index 6d1ae56da2d..3c61fd6c7b8 100644
--- a/intern/boolop/intern/BOP_Interface.cpp
+++ b/intern/boolop/intern/BOP_Interface.cpp
@@ -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;