Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/intern/boolop
diff options
context:
space:
mode:
Diffstat (limited to 'intern/boolop')
-rw-r--r--intern/boolop/intern/BOP_BSPNode.cpp100
-rw-r--r--intern/boolop/intern/BOP_BSPNode.h7
-rw-r--r--intern/boolop/intern/BOP_BSPTree.cpp43
-rw-r--r--intern/boolop/intern/BOP_BSPTree.h1
-rw-r--r--intern/boolop/intern/BOP_Interface.cpp4
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;
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-16 02:51:27 +0300