[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15899] trunk/blender/intern/boolop/intern : Tools
Ken Hughes
khughes at pacific.edu
Thu Jul 31 20:37:03 CEST 2008
Revision: 15899
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15899
Author: khughes
Date: 2008-07-31 20:37:03 +0200 (Thu, 31 Jul 2008)
Log Message:
-----------
Tools
-----
New boolean merge algorithm. The current code often does a poor job of merging tris and quads after the operation, resulting in many unnecessary faces. This commit add a new algorithm which takes advantage of topology information saved in the interal BOP structures.
The file intern/boolop/intern/BOP_Misc.h has two #defines which control which algorithm(s) are compiled. They are set now to compile both, with the new algorithm as the default. The original algorithm can be enabled by setting the "rt" debugging button on the Scene panel (F10) to 100.
One note: the current boolean code still occasionally creates a non-manifold mesh from an operation on two manifold meshes. The original merge algorithm would sometimes "close" these meshes and sometimes not. The new algorithms behaves the same way, but sometimes closes a mesh the original would not and sometimes leaves open a mesh the original would close. My fairly extensive tests did not indicate any significant difference in the percentage of final non-manifold meshes.
Modified Paths:
--------------
trunk/blender/intern/boolop/intern/BOP_Edge.cpp
trunk/blender/intern/boolop/intern/BOP_Edge.h
trunk/blender/intern/boolop/intern/BOP_Interface.cpp
trunk/blender/intern/boolop/intern/BOP_Merge.cpp
trunk/blender/intern/boolop/intern/BOP_Merge.h
trunk/blender/intern/boolop/intern/BOP_Mesh.cpp
trunk/blender/intern/boolop/intern/BOP_Misc.h
trunk/blender/intern/boolop/intern/BOP_Tag.h
Added Paths:
-----------
trunk/blender/intern/boolop/intern/BOP_Merge2.cpp
trunk/blender/intern/boolop/intern/BOP_Merge2.h
Modified: trunk/blender/intern/boolop/intern/BOP_Edge.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_Edge.cpp 2008-07-31 18:16:01 UTC (rev 15898)
+++ trunk/blender/intern/boolop/intern/BOP_Edge.cpp 2008-07-31 18:37:03 UTC (rev 15899)
@@ -75,6 +75,28 @@
else if (m_vertexs[1] == oldIndex) m_vertexs[1] = newIndex;
}
+#ifdef BOP_NEW_MERGE
+
+/**
+ * Returns if this edge contains the specified face index.
+ * @param i face index
+ * @return true if this edge contains the specified face index, false otherwise
+ */
+bool BOP_Edge::removeFace(BOP_Index i)
+{
+ int pos=0;
+ for(BOP_IT_Indexs it = m_faces.begin();it!=m_faces.end();pos++,it++) {
+ if ((*it) == i) {
+ m_faces.erase(it);
+ return true;
+ }
+ }
+
+ return false;
+}
+
+#endif
+
#ifdef BOP_DEBUG
#include <iostream>
@@ -86,6 +108,12 @@
ostream &operator<<(ostream &stream, BOP_Edge *e)
{
stream << "Edge[" << e->getVertex1() << "," << e->getVertex2();
+#ifdef BOP_NEW_MERGE
+ if(e->m_used)
+ stream << "] (used)";
+ else
+ stream << "] (unused)";
+#endif
return stream;
}
#endif
Modified: trunk/blender/intern/boolop/intern/BOP_Edge.h
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_Edge.h 2008-07-31 18:16:01 UTC (rev 15898)
+++ trunk/blender/intern/boolop/intern/BOP_Edge.h 2008-07-31 18:37:03 UTC (rev 15899)
@@ -36,6 +36,9 @@
private:
BOP_Index m_vertexs[2];
BOP_Indexs m_faces;
+#ifdef BOP_NEW_MERGE
+ bool m_used;
+#endif
bool containsFace(BOP_Index i);
@@ -48,6 +51,11 @@
inline unsigned int getNumFaces(){return m_faces.size();};
inline BOP_Indexs &getFaces(){return m_faces;};
void addFace(BOP_Index face);
+#ifdef BOP_NEW_MERGE
+ bool removeFace(BOP_Index i);
+ bool getUsed() { return m_used;};
+ void setUsed(bool setting) { m_used=setting;};
+#endif
#ifdef BOP_DEBUG
friend ostream &operator<<(ostream &stream, BOP_Edge *e);
#endif
Modified: trunk/blender/intern/boolop/intern/BOP_Interface.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_Interface.cpp 2008-07-31 18:16:01 UTC (rev 15898)
+++ trunk/blender/intern/boolop/intern/BOP_Interface.cpp 2008-07-31 18:37:03 UTC (rev 15899)
@@ -33,9 +33,12 @@
#include "BOP_Mesh.h"
#include "BOP_Face2Face.h"
#include "BOP_Merge.h"
+#include "BOP_Merge2.h"
#include "BOP_Chrono.h"
-//#define DEBUG
+#if defined(BOP_ORIG_MERGE) && defined(BOP_NEW_MERGE)
+#include "../../source/blender/blenkernel/BKE_global.h"
+#endif
BoolOpState BOP_intersectionBoolOp(BOP_Mesh* meshC,
BOP_Faces* facesA,
@@ -208,8 +211,33 @@
#endif
// Merge faces
+#ifdef BOP_ORIG_MERGE
+#ifndef BOP_NEW_MERGE
BOP_Merge::getInstance().mergeFaces(meshC,numVertices);
+#endif
+#endif
+#ifdef BOP_NEW_MERGE
+#ifndef BOP_ORIG_MERGE
+ BOP_Merge2::getInstance().mergeFaces(meshC,numVertices);
+#else
+ static int state = -1;
+ if (G.rt == 100) {
+ if( state != 1 ) {
+ cout << "Boolean code using old merge technique." << endl;
+ state = 1;
+ }
+ BOP_Merge::getInstance().mergeFaces(meshC,numVertices);
+ } else {
+ if( state != 0 ) {
+ cout << "Boolean code using new merge technique." << endl;
+ state = 0;
+ }
+ BOP_Merge2::getInstance().mergeFaces(meshC,numVertices);
+ }
+#endif
+#endif
+
#ifdef DEBUG
c = chrono.stamp(); t += c;
cout << "Merge faces " << c << endl;
Modified: trunk/blender/intern/boolop/intern/BOP_Merge.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_Merge.cpp 2008-07-31 18:16:01 UTC (rev 15898)
+++ trunk/blender/intern/boolop/intern/BOP_Merge.cpp 2008-07-31 18:37:03 UTC (rev 15899)
@@ -30,6 +30,7 @@
#include "BOP_Merge.h"
+#ifdef BOP_ORIG_MERGE
#ifdef _MSC_VER
#if _MSC_VER < 1300
@@ -802,3 +803,5 @@
}
}
}
+
+#endif /* BOP_ORIG_MERGE */
Modified: trunk/blender/intern/boolop/intern/BOP_Merge.h
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_Merge.h 2008-07-31 18:16:01 UTC (rev 15898)
+++ trunk/blender/intern/boolop/intern/BOP_Merge.h 2008-07-31 18:37:03 UTC (rev 15899)
@@ -28,6 +28,9 @@
#ifndef BOP_MERGE_H
#define BOP_MERGE_H
+#include "BOP_Misc.h"
+
+#ifdef BOP_ORIG_MERGE
#include "BOP_Mesh.h"
#include "BOP_Tag.h"
#include "BOP_MathUtils.h"
@@ -68,4 +71,6 @@
void mergeFaces(BOP_Mesh *m, BOP_Index v);
};
+#endif /* BOP_ORIG_MERGE */
+
#endif
Added: trunk/blender/intern/boolop/intern/BOP_Merge2.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_Merge2.cpp (rev 0)
+++ trunk/blender/intern/boolop/intern/BOP_Merge2.cpp 2008-07-31 18:37:03 UTC (rev 15899)
@@ -0,0 +1,944 @@
+/**
+ *
+ * $Id: BOP_Merge22.cpp 14444 2008-04-16 22:40:48Z hos $
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Marc Freixas, Ken Hughes
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include "BOP_Merge2.h"
+
+#ifdef BOP_NEW_MERGE
+
+static void deleteFace(BOP_Mesh *m, BOP_Face *face);
+
+/**
+ * SINGLETON (use method BOP_Merge2.getInstance).
+ */
+BOP_Merge2 BOP_Merge2::SINGLETON;
+
+#ifdef BOP_DEBUG
+void dumpmesh ( BOP_Mesh *m, bool force )
+{
+ unsigned int nonmanifold = 0;
+ {
+ BOP_Edges edges = m->getEdges();
+ int count = 0;
+ for (BOP_IT_Edges edge = edges.begin(); edge != edges.end();
+ ++count, ++edge) {
+ if (!(*edge)->getUsed() && (*edge)->getFaces().size() == 0 ) continue;
+ BOP_Vertex * v1 = m->getVertex((*edge)->getVertex1());
+ BOP_Vertex * v2 = m->getVertex((*edge)->getVertex2());
+
+ if(v1->getTAG()!= BROKEN || v2->getTAG()!= BROKEN ) {
+ int fcount = 0;
+ BOP_Indexs faces = (*edge)->getFaces();
+ for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); face++) {
+ BOP_Face *f = m->getFace(*face);
+ if(f->getTAG()== UNCLASSIFIED) ++fcount;
+ }
+
+
+ if(fcount !=0 && fcount !=2 ) {
+ ++nonmanifold;
+ }
+ }
+ }
+ if (!force && nonmanifold == 0) return;
+ }
+ if( nonmanifold )
+ cout << nonmanifold << " edges detected" << endl;
+#ifdef DEBUG
+ cout << "---------------------------" << endl;
+
+ BOP_Edges edges = m->getEdges();
+ int count = 0;
+ for (BOP_IT_Edges edge = edges.begin(); edge != edges.end();
+ ++count, ++edge) {
+ BOP_Vertex * v1 = m->getVertex((*edge)->getVertex1());
+ BOP_Vertex * v2 = m->getVertex((*edge)->getVertex2());
+
+ if(v1->getTAG()!= BROKEN || v2->getTAG()!= BROKEN ) {
+ int fcount = 0;
+ BOP_Indexs faces = (*edge)->getFaces();
+ cout << count << ", " << (*edge) << ", " << faces.size() << endl;
+ for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); face++) {
+ BOP_Face *f = m->getFace(*face);
+ if(f->getTAG()== UNCLASSIFIED) ++fcount;
+ cout << " face " << f << endl;
+ }
+
+
+ if(fcount !=0 && fcount !=2 )
+ cout << " NON-MANIFOLD" << endl;
+ }
+ }
+
+ BOP_Faces faces = m->getFaces();
+ count = 0;
+ for (BOP_IT_Faces face = faces.begin(); face != faces.end(); face++) {
+ if( count < 12*2 || (*face)->getTAG() != BROKEN ) {
+ cout << count << ", " << *face << endl;
+ }
+ ++count;
+ }
+
+ BOP_Vertexs verts = m->getVertexs();
+ count = 0;
+ for (BOP_IT_Vertexs vert = verts.begin(); vert != verts.end(); vert++) {
+ cout << count++ << ", " << *vert << " " << (*vert)->getNumEdges() << endl;
+ BOP_Indexs edges = (*vert)->getEdges();
+ for( BOP_IT_Indexs it = edges.begin(); it != edges.end(); ++it) {
+ BOP_Edge *edge = m->getEdge(*it);
+ cout << " " << edge << endl;
+ }
+ }
+ cout << "===========================" << endl;
+#endif
+}
+#endif
+
+/**
+ * Simplifies a mesh, merging its faces.
+ * @param m mesh
+ * @param v index of the first mergeable vertex (can be removed by merge)
+ */
+
+void BOP_Merge2::mergeFaces(BOP_Mesh *m, BOP_Index v)
+{
+ m_mesh = m;
+
+#ifdef DEBUG
+ cout << "##############################" << endl;
+#endif
+ cleanup( );
+
+ m_firstVertex = v;
+ bool cont = false;
+
+ // Merge faces
+ mergeFaces();
+
+ do {
+ // Add quads ...
+ cont = createQuads();
+ // ... and merge new faces
+ if( cont ) cont = mergeFaces();
+
+#ifdef DEBUG
+ cout << "called mergeFaces " << cont << endl;
+#endif
+ // ... until the merge is not succesful
+ } while(cont);
+}
+
+void clean_nonmanifold( BOP_Mesh *m )
+{
+ return;
+
+ BOP_Edges nme;
+ BOP_Edges e = m->getEdges();
+ for( BOP_IT_Edges it = e.begin(); it != e.end(); ++it ) {
+ BOP_Indexs faces = (*it)->getFaces();
+ if( faces.size() & ~2 )
+ nme.push_back(*it);
+ }
+ if (nme.size() == 0) return;
+ for( BOP_IT_Edges it = nme.begin(); it != nme.end(); ++it ) {
+ if( (*it)->getFaces().size() > 1 ) {
+ BOP_Indexs faces = (*it)->getFaces();
+ for( BOP_IT_Indexs face = faces.begin(); face != faces.end(); ++face ) {
+ MT_Point3 vertex1 = m->getVertex(m->getFace(*face)->getVertex(0))->getPoint();
+ MT_Point3 vertex2 = m->getVertex(m->getFace(*face)->getVertex(1))->getPoint();
+ MT_Point3 vertex3 = m->getVertex(m->getFace(*face)->getVertex(2))->getPoint();
+ if (BOP_collinear(vertex1,vertex2,vertex3)) // collinear triangle
+ deleteFace(m,m->getFace(*face));
+ }
+ continue;
+ }
+ BOP_Face *oface1 = m->getFace((*it)->getFaces().front());
+ BOP_Face *oface2, *tmpface;
+ BOP_Index first =(*it)->getVertex1();
+ BOP_Index next =(*it)->getVertex2();
+ BOP_Index last = first;
+ unsigned short facecount = 0;
+ bool found = false;
+ BOP_Indexs vertList;
+#ifdef DEBUG
+ cout << " first edge is " << (*it) << endl;
+#endif
+ vertList.push_back(first);
+ BOP_Edge *edge;
+ while(true) {
+ BOP_Vertex *vert = m->getVertex(next);
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list