[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [11244] trunk/blender/intern/boolop/intern : Tools
Ken Hughes
khughes at pacific.edu
Thu Jul 12 17:24:09 CEST 2007
Revision: 11244
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=11244
Author: khughes
Date: 2007-07-12 17:24:08 +0200 (Thu, 12 Jul 2007)
Log Message:
-----------
Tools
-----
More improvements to boolean tools. The main change (although very little in
code) is changing fuzzy comparisons of floating point values. For testing, a
new define is added in intern/boolop/intern/BOP_MathUtils.h called
VAR_EPSILON, which enables better comparisons. This is turned on by default;
undefining it will revert to using the previous comparisons. The downside of
these new comparisons is a loss in speed, but the resulting meshes are more
likely to be manifold (although still not always).
The other changes include speed improvements based on profiling results and
fixes for the improper creation of triangular faces with only two vertices.
Modified Paths:
--------------
trunk/blender/intern/boolop/intern/BOP_Face.cpp
trunk/blender/intern/boolop/intern/BOP_Face.h
trunk/blender/intern/boolop/intern/BOP_Face2Face.cpp
trunk/blender/intern/boolop/intern/BOP_MathUtils.cpp
trunk/blender/intern/boolop/intern/BOP_MathUtils.h
trunk/blender/intern/boolop/intern/BOP_Merge.cpp
trunk/blender/intern/boolop/intern/BOP_Mesh.cpp
trunk/blender/intern/boolop/intern/BOP_Triangulator.cpp
Modified: trunk/blender/intern/boolop/intern/BOP_Face.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_Face.cpp 2007-07-12 15:18:14 UTC (rev 11243)
+++ trunk/blender/intern/boolop/intern/BOP_Face.cpp 2007-07-12 15:24:08 UTC (rev 11244)
@@ -44,6 +44,8 @@
m_plane = plane;
m_tag = UNCLASSIFIED;
m_originalFace = originalFace;
+ m_split = 0;
+ m_bbox = NULL;
}
/**
@@ -197,6 +199,14 @@
*/
void BOP_Face3::replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex)
{
+ /* if the old index really exists, and new index also exists already,
+ * don't create an edge with both vertices == newIndex */
+
+ if( (m_indexs[0] == oldIndex || m_indexs[1] == oldIndex || m_indexs[2] == oldIndex) &&
+ (m_indexs[0] == newIndex || m_indexs[1] == newIndex || m_indexs[2] == newIndex) ) {
+ setTAG(BROKEN);
+ }
+
if (m_indexs[0] == oldIndex) m_indexs[0] = newIndex;
else if (m_indexs[1] == oldIndex) m_indexs[1] = newIndex;
else if (m_indexs[2] == oldIndex) m_indexs[2] = newIndex;
Modified: trunk/blender/intern/boolop/intern/BOP_Face.h
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_Face.h 2007-07-12 15:18:14 UTC (rev 11243)
+++ trunk/blender/intern/boolop/intern/BOP_Face.h 2007-07-12 15:24:08 UTC (rev 11244)
@@ -34,6 +34,7 @@
#include "BOP_Tag.h"
#include "MT_Plane3.h"
#include "BOP_Indexs.h"
+#include "BOP_BBox.h"
#include <iostream>
#include <vector>
using namespace std;
@@ -53,10 +54,12 @@
protected:
BOP_Index m_indexs[4];
unsigned int m_size;
+ unsigned int m_split;
+ BOP_BBox *m_bbox;
public:
BOP_Face(MT_Plane3 plane, BOP_Index originalFace);
- virtual ~BOP_Face(){};
+ virtual ~BOP_Face(){if (m_bbox) delete m_bbox;};
inline MT_Plane3 getPlane() const {return m_plane;};
inline void setPlane(const MT_Plane3 plane) {m_plane = plane;};
inline BOP_TAG getTAG() const {return m_tag;};
@@ -65,7 +68,15 @@
inline void setOriginalFace(const BOP_Index originalFace) {m_originalFace=originalFace;};
inline BOP_Index getVertex(unsigned int i) const {return m_indexs[i];};
inline void setVertex(const BOP_Index idx, const BOP_Index i) {m_indexs[idx]=i;};
+ inline unsigned int getSplit() const {return m_split;};
+ inline void setSplit(const unsigned int i) {m_split=i;};
+
void invert();
+ inline void setBBox(const MT_Point3& p1,const MT_Point3& p2,const MT_Point3& p3) {
+ m_bbox = new BOP_BBox(p1, p2, p3);};
+ inline BOP_BBox *getBBox() {return m_bbox;};
+ inline void freeBBox(){if (m_bbox!=NULL) {delete m_bbox; m_bbox=NULL;} };
+
inline unsigned int size() const {return m_size;};
virtual bool getEdgeIndex(BOP_Index v1, BOP_Index v2, unsigned int &e) = 0;
Modified: trunk/blender/intern/boolop/intern/BOP_Face2Face.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_Face2Face.cpp 2007-07-12 15:18:14 UTC (rev 11243)
+++ trunk/blender/intern/boolop/intern/BOP_Face2Face.cpp 2007-07-12 15:24:08 UTC (rev 11244)
@@ -147,9 +147,18 @@
* @param mesh mesh that contains the faces, edges and vertices
* @param facesA set of faces from object A
* @param facesB set of faces from object B
+ *
+ * Two optimizations were added here:
+ * 1) keep the bounding box for a face once it's created; this is
+ * especially important for B faces, since they were being created and
+ * recreated over and over
+ * 2) associate a "split" index in the faceB vector with each A face; when
+ * an A face is split, we will not need to recheck any B faces have
+ * already been checked against that original A face
*/
+
void BOP_Face2Face(BOP_Mesh *mesh, BOP_Faces *facesA, BOP_Faces *facesB)
-{
+{
for(unsigned int idxFaceA=0;idxFaceA<facesA->size();idxFaceA++) {
BOP_Face *faceA = (*facesA)[idxFaceA];
MT_Plane3 planeA = faceA->getPlane();
@@ -157,23 +166,33 @@
MT_Point3 p2 = mesh->getVertex(faceA->getVertex(1))->getPoint();
MT_Point3 p3 = mesh->getVertex(faceA->getVertex(2))->getPoint();
- BOP_BBox boxA(p1,p2,p3);
-
- for(unsigned int idxFaceB=0;
+ /* get (or create) bounding box for face A */
+ if( faceA->getBBox() == NULL )
+ faceA->setBBox(p1,p2,p3);
+ BOP_BBox *boxA = faceA->getBBox();
+
+ /* start checking B faces with the previously stored split index */
+
+ for(unsigned int idxFaceB=faceA->getSplit();
idxFaceB<facesB->size() && (faceA->getTAG() != BROKEN) && (faceA->getTAG() != PHANTOM);) {
BOP_Face *faceB = (*facesB)[idxFaceB];
+ faceA->setSplit(idxFaceB);
if ((faceB->getTAG() != BROKEN) && (faceB->getTAG() != PHANTOM)) {
- BOP_BBox boxB(mesh->getVertex(faceB->getVertex(0))->getPoint(),
- mesh->getVertex(faceB->getVertex(1))->getPoint(),
- mesh->getVertex(faceB->getVertex(2))->getPoint());
- if (boxA.intersect(boxB)) {
+ /* get (or create) bounding box for face B */
+ if( faceB->getBBox() == NULL )
+ faceB->setBBox(mesh->getVertex(faceB->getVertex(0))->getPoint(),
+ mesh->getVertex(faceB->getVertex(1))->getPoint(),
+ mesh->getVertex(faceB->getVertex(2))->getPoint());
+ BOP_BBox *boxB = faceB->getBBox();
+
+ if (boxA->intersect(*boxB)) {
MT_Plane3 planeB = faceB->getPlane();
if (BOP_containsPoint(planeB,p1) &&
BOP_containsPoint(planeB,p2) &&
BOP_containsPoint(planeB,p3)) {
if (BOP_orientation(planeB,planeA)>0) {
- BOP_intersectCoplanarFaces(mesh,facesB,faceA,faceB,false);
+ BOP_intersectCoplanarFaces(mesh,facesB,faceA,faceB,false);
}
}
else {
@@ -181,10 +200,7 @@
}
}
}
- if (faceB->getTAG()==BROKEN){
- facesB->erase(facesB->begin()+idxFaceB);
- }else
- idxFaceB++;
+ idxFaceB++;
}
}
@@ -388,56 +404,11 @@
for(unsigned int idxFace = firstFace; idxFace < numFaces; idxFace++) {
BOP_Face *face = mesh->getFace(idxFace);
if ((face->getTAG() != BROKEN) && (face->getTAG() != PHANTOM)) {
- BOP_Index v1 = face->getVertex(0);
- BOP_Index v2 = face->getVertex(1);
- BOP_Index v3 = face->getVertex(2);
- MT_Point3 vertex1 = mesh->getVertex(v1)->getPoint();
- MT_Point3 vertex2 = mesh->getVertex(v2)->getPoint();
- MT_Point3 vertex3 = mesh->getVertex(v3)->getPoint();
- int dist12 = BOP_comp(vertex1,vertex2);
- int dist13 = BOP_comp(vertex1,vertex3);
- int dist23 = BOP_comp(vertex2,vertex3);
-
- if (dist12 == 0) {
- if (dist13 == 0) {
- // v1 ~= v2 , v1 ~= v3 , v2 ~= v3
- mesh->replaceVertexIndex(v2,v1);
- mesh->replaceVertexIndex(v3,v1);
- }
- else {
- if (dist23 == 0) {
- mesh->replaceVertexIndex(v1,v2);
- mesh->replaceVertexIndex(v3,v2);
- }
- else {
- mesh->replaceVertexIndex(v1,v2);
- }
- }
- }
- else {
- if (dist13 == 0) {
- // v1 ~= v3
- if (dist23 == 0) {
- mesh->replaceVertexIndex(v1,v3);
- mesh->replaceVertexIndex(v2,v3);
- }
- else {
- mesh->replaceVertexIndex(v1,v3);
- }
- }
- else {
- if (dist23 == 0) {
- // v2 ~= v3
- mesh->replaceVertexIndex(v2,v3);
- } else {
- // all differents
- if (BOP_collinear(vertex1,vertex2,vertex3)) {
- // collinear triangle
- face->setTAG(PHANTOM);
- }
- }
- }
- }
+ MT_Point3 vertex1 = mesh->getVertex(face->getVertex(0))->getPoint();
+ MT_Point3 vertex2 = mesh->getVertex(face->getVertex(1))->getPoint();
+ MT_Point3 vertex3 = mesh->getVertex(face->getVertex(2))->getPoint();
+ if (BOP_collinear(vertex1,vertex2,vertex3)) // collinear triangle
+ face->setTAG(PHANTOM);
}
}
}
@@ -510,7 +481,7 @@
if (size == 2) {
// Trivial case, only test the merge ...
- if (BOP_comp(0,points[0].distance(points[1]))==0) {
+ if (BOP_fuzzyZero(points[0].distance(points[1]))) {
face[0] = 3;
size--;
}
@@ -595,8 +566,8 @@
// Merge data
MT_Scalar d1 = sortedPoints[1].distance(sortedPoints[0]);
MT_Scalar d2 = sortedPoints[1].distance(sortedPoints[2]);
- if (BOP_comp(0,d1)==0 && sortedFaces[1] != sortedFaces[0]) {
- if (BOP_comp(0,d2)==0 && sortedFaces[1] != sortedFaces[2]) {
+ if (BOP_fuzzyZero(d1) && sortedFaces[1] != sortedFaces[0]) {
+ if (BOP_fuzzyZero(d2) && sortedFaces[1] != sortedFaces[2]) {
if (d1 < d2) {
// merge 0 and 1
sortedFaces[0] = 3;
@@ -608,7 +579,7 @@
if (size == 3) {
// merge 1 and 2 ???
d1 = sortedPoints[1].distance(sortedPoints[2]);
- if (BOP_comp(0,d1)==0 && sortedFaces[1] != sortedFaces[2]) {
+ if (BOP_fuzzyZero(d1) && sortedFaces[1] != sortedFaces[2]) {
// merge!
sortedFaces[1] = 3;
size--;
@@ -636,7 +607,7 @@
if (size == 3) {
// merge 1 i 2 ???
d1 = sortedPoints[1].distance(sortedPoints[2]);
- if (BOP_comp(0,d1)==0 && sortedFaces[1] != sortedFaces[2]) {
+ if (BOP_fuzzyZero(d1) && sortedFaces[1] != sortedFaces[2]) {
// merge!
sortedFaces[1] = 3;
size--;
@@ -645,7 +616,7 @@
}
}
else {
- if (BOP_comp(0,d2)==0 && sortedFaces[1] != sortedFaces[2]) {
+ if (BOP_fuzzyZero(d2) && sortedFaces[1] != sortedFaces[2]) {
// merge 1 and 2
sortedFaces[1] = 3;
for(i = 2; i<size-1;i++) {
@@ -656,7 +627,7 @@
}
else if (size == 4) {
d1 = sortedPoints[2].distance(sortedPoints[3]);
- if (BOP_comp(0,d1)==0 && sortedFaces[2] != sortedFaces[3]) {
+ if (BOP_fuzzyZero(d1) && sortedFaces[2] != sortedFaces[3]) {
// merge 2 and 3
sortedFaces[2] = 3;
size--;
Modified: trunk/blender/intern/boolop/intern/BOP_MathUtils.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_MathUtils.cpp 2007-07-12 15:18:14 UTC (rev 11243)
+++ trunk/blender/intern/boolop/intern/BOP_MathUtils.cpp 2007-07-12 15:24:08 UTC (rev 11244)
@@ -43,12 +43,41 @@
*/
int BOP_comp(const MT_Scalar A, const MT_Scalar B)
{
+#ifndef VAR_EPSILON
if (A >= B + BOP_EPSILON) return 1;
else if (B >= A + BOP_EPSILON) return -1;
else return 0;
+#else
+ int expA, expB;
+ float mant;
+ frexp(A, &expA); /* get exponents of each number */
+ frexp(B, &expB);
+
+ if(expA < expB) /* find the larger exponent */
+ expA = expB;
+ mant = frexp((A-B), &expB); /* get exponent of the difference */
+ /* mantissa will only be zero is (A-B) is really zero; otherwise, also
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list