diff options
Diffstat (limited to 'intern/boolop')
-rw-r--r-- | intern/boolop/intern/BOP_BSPNode.cpp | 100 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_BSPNode.h | 7 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_BSPTree.cpp | 43 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_BSPTree.h | 1 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Interface.cpp | 4 |
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; |