[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [10925] trunk/blender/intern/boolop/intern : Fix for very old bug in Boolean code.
Ken Hughes
khughes at pacific.edu
Thu Jun 14 16:42:35 CEST 2007
Revision: 10925
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=10925
Author: khughes
Date: 2007-06-14 16:42:35 +0200 (Thu, 14 Jun 2007)
Log Message:
-----------
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).
Modified Paths:
--------------
trunk/blender/intern/boolop/intern/BOP_BSPNode.cpp
trunk/blender/intern/boolop/intern/BOP_BSPNode.h
trunk/blender/intern/boolop/intern/BOP_BSPTree.cpp
trunk/blender/intern/boolop/intern/BOP_BSPTree.h
trunk/blender/intern/boolop/intern/BOP_Interface.cpp
Modified: trunk/blender/intern/boolop/intern/BOP_BSPNode.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_BSPNode.cpp 2007-06-14 14:36:27 UTC (rev 10924)
+++ trunk/blender/intern/boolop/intern/BOP_BSPNode.cpp 2007-06-14 14:42:35 UTC (rev 10925)
@@ -58,32 +58,84 @@
/**
* 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;
}
- }
-
- if ((tag & OUT_OUT_OUT) != 0){
+ } else if ((tag & OUT) != 0 && (tag & IN) == 0) { // face is entirely on outside
if (m_outChild != NULL)
- newDeep = MT_max(newDeep, m_outChild->addFace(p1, p2, p3, plane) + 1);
+ 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 (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);
}
}
@@ -653,19 +705,13 @@
*/
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;
}
Modified: trunk/blender/intern/boolop/intern/BOP_BSPNode.h
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_BSPNode.h 2007-06-14 14:36:27 UTC (rev 10924)
+++ trunk/blender/intern/boolop/intern/BOP_BSPNode.h 2007-06-14 14:42:35 UTC (rev 10925)
@@ -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 @@
// 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,
Modified: trunk/blender/intern/boolop/intern/BOP_BSPTree.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_BSPTree.cpp 2007-06-14 14:36:27 UTC (rev 10924)
+++ trunk/blender/intern/boolop/intern/BOP_BSPTree.cpp 2007-06-14 14:42:35 UTC (rev 10925)
@@ -69,6 +69,7 @@
* @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,9 +92,16 @@
{
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);
m_bbox.add(p2);
@@ -171,37 +179,6 @@
}
/**
- * 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()
Modified: trunk/blender/intern/boolop/intern/BOP_BSPTree.h
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_BSPTree.h 2007-06-14 14:36:27 UTC (rev 10924)
+++ trunk/blender/intern/boolop/intern/BOP_BSPTree.h 2007-06-14 14:42:35 UTC (rev 10925)
@@ -65,7 +65,6 @@
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;};
Modified: trunk/blender/intern/boolop/intern/BOP_Interface.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_Interface.cpp 2007-06-14 14:36:27 UTC (rev 10924)
+++ trunk/blender/intern/boolop/intern/BOP_Interface.cpp 2007-06-14 14:42:35 UTC (rev 10925)
@@ -152,12 +152,10 @@
// 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;
More information about the Bf-blender-cvs
mailing list