diff options
author | Andre Susano Pinto <andresusanopinto@gmail.com> | 2008-08-02 01:37:36 +0400 |
---|---|---|
committer | Andre Susano Pinto <andresusanopinto@gmail.com> | 2008-08-02 01:37:36 +0400 |
commit | 289d875dfdd00165dacd92b554c472cc818dbd8f (patch) | |
tree | 97ef62b3769573cd50d8525453368de9066ff577 /intern | |
parent | 9e1ca2c1bef2d0e8db5e22a284134c37b2f6a457 (diff) |
svn merge -r 15688:15908 https://svn.blender.org/svnroot/bf-blender/trunk/blender
Diffstat (limited to 'intern')
-rw-r--r-- | intern/boolop/intern/BOP_Edge.cpp | 43 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Edge.h | 13 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Face.cpp | 2 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Face.h | 3 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Interface.cpp | 30 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Merge.cpp | 3 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Merge.h | 5 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Merge2.cpp | 944 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Merge2.h | 99 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Mesh.cpp | 11 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Mesh.h | 7 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Misc.h | 54 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Tag.h | 2 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Vertex.cpp | 19 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Vertex.h | 5 |
15 files changed, 1230 insertions, 10 deletions
diff --git a/intern/boolop/intern/BOP_Edge.cpp b/intern/boolop/intern/BOP_Edge.cpp index ac302b530df..44e7d5cb567 100644 --- a/intern/boolop/intern/BOP_Edge.cpp +++ b/intern/boolop/intern/BOP_Edge.cpp @@ -75,4 +75,47 @@ void BOP_Edge::replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex) 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> +using namespace std; + +/** + * Implements operator <<. + */ +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 + diff --git a/intern/boolop/intern/BOP_Edge.h b/intern/boolop/intern/BOP_Edge.h index 13426f6e63c..a817b3d624f 100644 --- a/intern/boolop/intern/BOP_Edge.h +++ b/intern/boolop/intern/BOP_Edge.h @@ -29,12 +29,16 @@ #define BOP_EDGE_H #include "BOP_Indexs.h" +#include "BOP_Misc.h" class BOP_Edge { private: BOP_Index m_vertexs[2]; BOP_Indexs m_faces; +#ifdef BOP_NEW_MERGE + bool m_used; +#endif bool containsFace(BOP_Index i); @@ -47,6 +51,15 @@ public: 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 + }; #endif diff --git a/intern/boolop/intern/BOP_Face.cpp b/intern/boolop/intern/BOP_Face.cpp index 12c94624517..01308de3e5d 100644 --- a/intern/boolop/intern/BOP_Face.cpp +++ b/intern/boolop/intern/BOP_Face.cpp @@ -402,6 +402,7 @@ bool BOP_Face4::getEdgeIndex(BOP_Index v1, BOP_Index v2, unsigned int &e) return true; } +#ifdef BOP_DEBUG /** * Implements operator <<. */ @@ -421,3 +422,4 @@ ostream &operator<<(ostream &stream, BOP_Face *f) return stream; } +#endif diff --git a/intern/boolop/intern/BOP_Face.h b/intern/boolop/intern/BOP_Face.h index e16425f78b3..965882db732 100644 --- a/intern/boolop/intern/BOP_Face.h +++ b/intern/boolop/intern/BOP_Face.h @@ -32,6 +32,7 @@ #include "MT_Plane3.h" #include "BOP_Indexs.h" #include "BOP_BBox.h" +#include "BOP_Misc.h" #include <iostream> #include <vector> using namespace std; @@ -80,7 +81,9 @@ public: virtual void replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex) = 0; virtual bool containsVertex(BOP_Index v) = 0; +#ifdef BOP_DEBUG friend ostream &operator<<(ostream &stream, BOP_Face *f); +#endif }; class BOP_Face3: public BOP_Face diff --git a/intern/boolop/intern/BOP_Interface.cpp b/intern/boolop/intern/BOP_Interface.cpp index 2a198103931..898ca708204 100644 --- a/intern/boolop/intern/BOP_Interface.cpp +++ b/intern/boolop/intern/BOP_Interface.cpp @@ -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,7 +211,32 @@ BoolOpState BOP_intersectionBoolOp(BOP_Mesh* meshC, #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; diff --git a/intern/boolop/intern/BOP_Merge.cpp b/intern/boolop/intern/BOP_Merge.cpp index 1e4139ab971..012d3409187 100644 --- a/intern/boolop/intern/BOP_Merge.cpp +++ b/intern/boolop/intern/BOP_Merge.cpp @@ -30,6 +30,7 @@ #include "BOP_Merge.h" +#ifdef BOP_ORIG_MERGE #ifdef _MSC_VER #if _MSC_VER < 1300 @@ -802,3 +803,5 @@ void BOP_Merge::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Indexs vertices, B } } } + +#endif /* BOP_ORIG_MERGE */ diff --git a/intern/boolop/intern/BOP_Merge.h b/intern/boolop/intern/BOP_Merge.h index 88999b2e734..ceb8ec10690 100644 --- a/intern/boolop/intern/BOP_Merge.h +++ b/intern/boolop/intern/BOP_Merge.h @@ -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 @@ class BOP_Merge { void mergeFaces(BOP_Mesh *m, BOP_Index v); }; +#endif /* BOP_ORIG_MERGE */ + #endif diff --git a/intern/boolop/intern/BOP_Merge2.cpp b/intern/boolop/intern/BOP_Merge2.cpp new file mode 100644 index 00000000000..bbf3f8ba702 --- /dev/null +++ b/intern/boolop/intern/BOP_Merge2.cpp @@ -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); + BOP_Indexs edges = vert->getEdges(); + edge = NULL; + for( BOP_IT_Indexs eit = edges.begin(); eit != edges.end(); ++eit) { + edge = m->getEdge(*eit); + if( edge->getFaces().size() > 1) { + edge = NULL; + continue; + } + if( edge->getVertex1() == next && edge->getVertex2() != last ) { + last = next; + next = edge->getVertex2(); + break; + } + if( edge->getVertex2() == next && edge->getVertex1() != last ) { + last = next; + next = edge->getVertex1(); + break; + } + edge = NULL; + } + if( !edge ) break; +#ifdef DEBUG + cout << " next edge is " << edge << endl; +#endif + tmpface = m->getFace(edge->getFaces().front()); + if( oface1->getOriginalFace() != tmpface->getOriginalFace() ) + oface2 = tmpface; + else + ++facecount; + vertList.push_back(last); + if( vertList.size() > 3 ) break; + if( next == first ) { + found = true; + break; + } + } + if(found) { + edge = *it; +#ifdef DEBUG + cout << " --> found a loop" << endl; +#endif + if( vertList.size() == 3 ) { + BOP_Face3 *face = (BOP_Face3 *)m->getFace(edge->getFaces().front()); + face->getNeighbours(first,last,next); + } else if( vertList.size() == 4 ) { + BOP_Face4 *face = (BOP_Face4 *)m->getFace(edge->getFaces().front()); + face->getNeighbours(first,last,next,last); + } else { +#ifdef DEBUG + cout << "loop has " << vertList.size() << "verts"; +#endif + continue; + } + if(facecount == 1) oface1 = oface2; + next = vertList[1]; + last = vertList[2]; + if( edge->getVertex2() == next ) { + BOP_Face3 *f = new BOP_Face3(next,first,last, + oface1->getPlane(),oface1->getOriginalFace()); + m->addFace( f ); +#ifdef DEBUG + cout << " face is backward: " << f << endl; +#endif + + } else { + BOP_Face3 *f = new BOP_Face3(last,first,next, + oface1->getPlane(),oface1->getOriginalFace()); + m->addFace( f ); +#ifdef DEBUG + cout << " face is forward: " << f << endl; +#endif + } + } + } +} + +/** + * Runs through mesh and makes sure vert/face/edge data is consistent. Most + * importantly: + * (1) mark edges which are no longer used + * (2) remove broken faces from edges + * (3) remove faces from mesh which have a single edge belonging to no other + * face (non-manifold edges) + */ + +void BOP_Merge2::cleanup( void ) +{ + BOP_Edges edges = m_mesh->getEdges(); + for (BOP_IT_Edges edge = edges.begin(); edge != edges.end(); ++edge) { + BOP_Indexs faces = (*edge)->getFaces(); + for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); ++face) { + BOP_Face *f = m_mesh->getFace(*face); + if(f->getTAG()== UNCLASSIFIED) ; + else (*edge)->removeFace(*face); + } + if( (*edge)->getFaces().size() == 0) (*edge)->setUsed(false); + } + + BOP_Vertexs v = m_mesh->getVertexs(); + for( BOP_IT_Vertexs it = v.begin(); it != v.end(); ++it ) { + if( (*it)->getTAG() != BROKEN) { + BOP_Indexs edges = (*it)->getEdges(); + for(BOP_IT_Indexs i = edges.begin();i!=edges.end();i++) + if( m_mesh->getEdge((*i))->getUsed( ) == false) (*it)->removeEdge( *i ); + if( (*it)->getEdges().size() == 0 ) (*it)->setTAG(BROKEN); + } + } + // clean_nonmanifold( m_mesh ); +} + +/** + * Simplifies a mesh, merging its faces. + */ +bool BOP_Merge2::mergeFaces() +{ + BOP_Indexs mergeVertices; + BOP_Vertexs vertices = m_mesh->getVertexs(); + BOP_IT_Vertexs v = vertices.begin(); + const BOP_IT_Vertexs verticesEnd = vertices.end(); + + // Advance to first mergeable vertex + advance(v,m_firstVertex); + BOP_Index pos = m_firstVertex; + + // Add unbroken vertices to the list + while(v!=verticesEnd) { + if ((*v)->getTAG() != BROKEN) { + mergeVertices.push_back(pos); + } + + v++; + pos++; + } + + // Merge faces with that vertices + return mergeFaces(mergeVertices); +} + +/** + * remove edges from vertices when the vertex is removed + */ +void BOP_Merge2::freeVerts(BOP_Index v, BOP_Vertex *vert) +{ + BOP_Indexs edges = vert->getEdges(); + BOP_Vertex *other; + + for( BOP_IT_Indexs it = edges.begin(); it != edges.end(); ++it) { + BOP_Edge *edge = m_mesh->getEdge(*it); + BOP_Indexs edges2; + if( edge->getVertex1() != v ) + other = m_mesh->getVertex( edge->getVertex1() ); + else + other = m_mesh->getVertex( edge->getVertex2() ); + other->removeEdge(*it); + vert->removeEdge(*it); + } +} + +/** + * Simplifies a mesh, merging the faces with the specified vertices. + * @param mergeVertices vertices to test + * @return true if a face merge was performed + */ +bool BOP_Merge2::mergeFaces(BOP_Indexs &mergeVertices) +{ + // Check size > 0! + if (mergeVertices.size() == 0) return false; + bool didMerge = false; + + for( BOP_Index i = 0; i < mergeVertices.size(); ++i ) { + BOP_LFaces facesByOriginalFace; + BOP_Index v = mergeVertices[i]; + BOP_Vertex *vert = m_mesh->getVertex(v); +#ifdef DEBUG + cout << "i = " << i << ", v = " << v << ", vert = " << vert << endl; + if (v==48) + cout << "found vert 48" << endl; +#endif + if ( vert->getTAG() != BROKEN ) { + getFaces(facesByOriginalFace,v); + + switch (facesByOriginalFace.size()) { + case 0: + // v has no unbroken faces (so it's a new BROKEN vertex) + freeVerts( v, vert ); + vert->setTAG(BROKEN); + break; + case 2: { +#ifdef DEBUG + cout << "size of fBOF = " << facesByOriginalFace.size() << endl; +#endif + BOP_Faces ff = facesByOriginalFace.front(); + BOP_Faces fb = facesByOriginalFace.back(); + BOP_Index eindexs[2]; + int ecount = 0; + + // look for two edges adjacent to v which contain both ofaces + BOP_Indexs edges = vert->getEdges(); +#ifdef DEBUG + cout << " ff has " << ff.size() << " faces" << endl; + cout << " fb has " << fb.size() << " faces" << endl; + cout << " v has " << edges.size() << " edges" << endl; +#endif + for(BOP_IT_Indexs it = edges.begin(); it != edges.end(); + ++it ) { + BOP_Edge *edge = m_mesh->getEdge(*it); + BOP_Indexs faces = edge->getFaces(); +#ifdef DEBUG + cout << " " << edge << " has " << edge->getFaces().size() << " faces" << endl; +#endif + if( faces.size() == 2 ) { + BOP_Face *f0 = m_mesh->getFace(faces[0]); + BOP_Face *f1 = m_mesh->getFace(faces[1]); + if( f0->getOriginalFace() != f1->getOriginalFace() ) { +#ifdef DEBUG + cout << " " << f0 << endl; + cout << " " << f1 << endl; +#endif + eindexs[ecount++] = (*it); + } + } + } + if(ecount == 2) { +#ifdef DEBUG + cout << " edge indexes are " << eindexs[0]; + cout << " and " << eindexs[1] << endl; +#endif + BOP_Edge *edge = m_mesh->getEdge(eindexs[0]); + BOP_Index N = edge->getVertex1(); + if(N == v) N = edge->getVertex2(); +#ifdef DEBUG + cout << " ## OK, replace "<<v<<" with "<<N << endl; +#endif + mergeVertex(ff , v, N ); + mergeVertex(fb , v, N ); +// now remove v and its edges + vert->setTAG(BROKEN); + for(BOP_IT_Indexs it = edges.begin(); it != edges.end(); + ++it ) { + BOP_Edge *edge = m_mesh->getEdge(*it); + edge->setUsed(false); + } + didMerge = true; + } +#ifdef DEBUG + else { + cout << " HUH: ecount was " << ecount << endl; + } +#endif + } + break; + default: + break; + } + } + } + + return didMerge; +} + +void BOP_Merge2::mergeVertex(BOP_Faces &faces, BOP_Index v1, BOP_Index v2) +{ + for(BOP_IT_Faces face=faces.begin();face!=faces.end();face++) { + if( (*face)->size() == 3) + mergeVertex((BOP_Face3 *) *face, v1, v2); + else + mergeVertex((BOP_Face4 *) *face, v1, v2); + (*face)->setTAG(BROKEN); +#ifdef DEBUG + cout << " breaking " << (*face) << endl; +#endif + } +} + +/* + * Remove a face from the mesh and from each edges's face list + */ + +static void deleteFace(BOP_Mesh *m, BOP_Face *face) +{ + BOP_Index l2 = face->getVertex(0); + BOP_Faces faces = m->getFaces(); + for(int i = face->size(); i-- ; ) { + BOP_Indexs edges = m->getVertex(l2)->getEdges(); + BOP_Index l1 = face->getVertex(i); + for(BOP_IT_Indexs it1 = edges.begin(); it1 != edges.end(); ++it1 ) { + BOP_Edge *edge = m->getEdge(*it1); + if( ( edge->getVertex1() == l1 && edge->getVertex2() == l2 ) || + ( edge->getVertex1() == l2 && edge->getVertex2() == l1 ) ) { + BOP_Indexs ef = edge->getFaces(); + for(BOP_IT_Indexs it = ef.begin(); it != ef.end(); ++it ) { + if( m->getFace(*it) == face) { + edge->removeFace(*it); + break; + } + } + break; + } + } + l2 = l1; + } + face->setTAG(BROKEN); +} + +void BOP_Merge2::mergeVertex(BOP_Face3 *face, BOP_Index v1, BOP_Index v2) +{ + BOP_Index next, prev; + face->getNeighbours(v1,prev,next); + + // if new vertex is not already in the tri, make a new tri + if( prev != v2 && next != v2 ) { + m_mesh->addFace( new BOP_Face3(prev,v2,next, + face->getPlane(),face->getOriginalFace()) ); +#ifdef DEBUG + cout << "mv3: add " << prev << "," << v2 << "," << next << endl; + } else { + cout << "mv3: vertex already in tri: doing nothing" << endl; +#endif + } + deleteFace(m_mesh, face); +} + +void BOP_Merge2::mergeVertex(BOP_Face4 *face, BOP_Index v1, BOP_Index v2) +{ + BOP_Index next, prev, opp; + face->getNeighbours(v1,prev,next,opp); + + // if new vertex is already in the quad, replace quad with new tri + if( prev == v2 || next == v2 ) { + m_mesh->addFace( new BOP_Face3(prev,next,opp, + face->getPlane(),face->getOriginalFace()) ); +#ifdef DEBUG + cout << "mv4a: add " << prev << "," << next << "," << opp << endl; +#endif + } + // otherwise make a new quad + else { + m_mesh->addFace( new BOP_Face4(prev,v2,next,opp, + face->getPlane(),face->getOriginalFace()) ); +#ifdef DEBUG + cout << "mv4b: add "<<prev<<","<<v2<<","<<next<<","<<opp<<endl; +#endif + } + deleteFace(m_mesh, face); +} + +// #define OLD_QUAD + +/** + * Simplifies the mesh, merging the pairs of triangles that come frome the + * same original face and define a quad. + * @return true if a quad was added, false otherwise + */ +bool BOP_Merge2::createQuads() +{ + + BOP_Faces quads; + + // Get mesh faces + BOP_Faces faces = m_mesh->getFaces(); + + // Merge mesh triangles + const BOP_IT_Faces facesIEnd = (faces.end()-1); + const BOP_IT_Faces facesJEnd = faces.end(); + for(BOP_IT_Faces faceI=faces.begin();faceI!=facesIEnd;faceI++) { +#ifdef OLD_QUAD + if ((*faceI)->getTAG() == BROKEN || (*faceI)->size() != 3) continue; + for(BOP_IT_Faces faceJ=(faceI+1);faceJ!=facesJEnd;faceJ++) { + if ((*faceJ)->getTAG() == BROKEN || (*faceJ)->size() != 3 || + (*faceJ)->getOriginalFace() != (*faceI)->getOriginalFace()) continue; + + + BOP_Face *faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face3*)*faceJ); + if (faceK != NULL) { + // Set triangles to BROKEN + deleteFace(m_mesh, *faceI); + deleteFace(m_mesh, *faceJ); +#ifdef DEBUG + cout << "createQuad: del " << *faceI << endl; + cout << "createQuad: del " << *faceJ << endl; + cout << "createQuad: add " << faceK << endl; +#endif + quads.push_back(faceK); + break; + } + } +#else + if ((*faceI)->getTAG() == BROKEN ) continue; + for(BOP_IT_Faces faceJ=(faceI+1);faceJ!=facesJEnd;faceJ++) { + if ((*faceJ)->getTAG() == BROKEN || + (*faceJ)->getOriginalFace() != (*faceI)->getOriginalFace()) continue; + + BOP_Face *faceK = NULL; + if((*faceI)->size() == 3) { + if((*faceJ)->size() == 3) + faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face3*)*faceJ); + else + faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face4*)*faceJ); + } else { + if((*faceJ)->size() == 3) + faceK = createQuad((BOP_Face3*)*faceJ,(BOP_Face4*)*faceI); + else + faceK = createQuad((BOP_Face4*)*faceI,(BOP_Face4*)*faceJ); + } + + if (faceK != NULL) { + // Set triangles to BROKEN + deleteFace(m_mesh, *faceI); + deleteFace(m_mesh, *faceJ); +#ifdef DEBUG + cout << "createQuad: del " << *faceI << endl; + cout << "createQuad: del " << *faceJ << endl; + cout << "createQuad: add " << faceK << endl; +#endif + quads.push_back(faceK); + break; + } + } +#endif + } + + // Add quads to mesh + const BOP_IT_Faces quadsEnd = quads.end(); + for(BOP_IT_Faces quad=quads.begin();quad!=quadsEnd;quad++) m_mesh->addFace(*quad); + return (quads.size() > 0); +} + +/** + * Returns a new quad (convex) from the merge of two triangles that share the + * vertex index v. + * @param faceI mesh triangle + * @param faceJ mesh triangle + * @param v vertex index shared by both triangles + * @return a new convex quad if the merge is possible + */ +BOP_Face* BOP_Merge2::createQuad(BOP_Face3 *faceI, BOP_Face3 *faceJ) +{ + // Test if both triangles share a vertex index + BOP_Index v; + unsigned int i; + for(i=0;i<3 ;i++) { + v = faceI->getVertex(i); + if( faceJ->containsVertex(v) ) break; + } + if (i == 3) return NULL; + + BOP_Face *faceK = NULL; + + // Get faces data + BOP_Index prevI, nextI, prevJ, nextJ; + faceI->getNeighbours(v,prevI,nextI); + faceJ->getNeighbours(v,prevJ,nextJ); + MT_Point3 vertex = m_mesh->getVertex(v)->getPoint(); + MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint(); + MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint(); + MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint(); + MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint(); + + // Quad test + if (prevI == nextJ) { + if (!BOP_collinear(vNextI,vertex,vPrevJ) && !BOP_collinear(vNextI,vPrevI,vPrevJ) && + BOP_convex(vertex,vNextI,vPrevI,vPrevJ)) { + faceK = new BOP_Face4(v,nextI,prevI,prevJ,faceI->getPlane(),faceI->getOriginalFace()); + faceK->setTAG(faceI->getTAG()); + BOP_Index edge; + m_mesh->getIndexEdge(v,prevI,edge); + m_mesh->getVertex(v)->removeEdge(edge); + m_mesh->getVertex(prevI)->removeEdge(edge); + } + } + else if (nextI == prevJ) { + if (!BOP_collinear(vPrevI,vertex,vNextJ) && !BOP_collinear(vPrevI,vNextI,vNextJ) && + BOP_convex(vertex,vNextJ,vNextI,vPrevI)) { + faceK = new BOP_Face4(v,nextJ,nextI,prevI,faceI->getPlane(),faceI->getOriginalFace()); + faceK->setTAG(faceI->getTAG()); + BOP_Index edge; + m_mesh->getIndexEdge(v,nextI,edge); + m_mesh->getVertex(v)->removeEdge(edge); + m_mesh->getVertex(nextI)->removeEdge(edge); + } + } + return faceK; +} + +/** + * Returns a new quad (convex) from the merge of two triangles that share the + * vertex index v. + * @param faceI mesh triangle + * @param faceJ mesh triangle + * @param v vertex index shared by both triangles + * @return a new convex quad if the merge is possible + */ +BOP_Face* BOP_Merge2::createQuad(BOP_Face3 *faceI, BOP_Face4 *faceJ) +{ + // Test if triangle and quad share a vertex index + BOP_Index v; + unsigned int i; + for(i=0;i<3 ;i++) { + v = faceI->getVertex(i); + if( faceJ->containsVertex(v) ) break; + } + if (i == 3) return NULL; + + BOP_Face *faceK = NULL; + + // Get faces data + BOP_Index prevI, nextI, prevJ, nextJ, oppJ; + faceI->getNeighbours(v,prevI,nextI); + faceJ->getNeighbours(v,prevJ,nextJ,oppJ); + + // Quad test + BOP_Index edge; + if (nextI == prevJ) { + if (prevI == nextJ) { // v is in center + faceK = new BOP_Face3(nextJ,oppJ,prevJ,faceI->getPlane(),faceI->getOriginalFace()); + faceK->setTAG(faceI->getTAG()); + m_mesh->getIndexEdge(v,prevI,edge); + m_mesh->getVertex(v)->removeEdge(edge); + m_mesh->getVertex(prevI)->removeEdge(edge); + m_mesh->getIndexEdge(v,nextI,edge); + m_mesh->getVertex(v)->removeEdge(edge); + m_mesh->getVertex(nextI)->removeEdge(edge); + freeVerts(v, m_mesh->getVertex(v)); + } else if (prevI == oppJ) { // nextI is in center + faceK = new BOP_Face3(v,nextJ,oppJ,faceI->getPlane(),faceI->getOriginalFace()); + faceK->setTAG(faceI->getTAG()); + m_mesh->getIndexEdge(v,nextI,edge); + m_mesh->getVertex(v)->removeEdge(edge); + m_mesh->getVertex(nextI)->removeEdge(edge); + m_mesh->getIndexEdge(prevI,nextI,edge); + m_mesh->getVertex(prevI)->removeEdge(edge); + m_mesh->getVertex(nextI)->removeEdge(edge); + freeVerts(nextI, m_mesh->getVertex(nextI)); + } + } else if (nextI == oppJ && prevI == nextJ ) { // prevI is in center + faceK = new BOP_Face3(prevJ,v,oppJ,faceI->getPlane(),faceI->getOriginalFace()); + faceK->setTAG(faceI->getTAG()); + m_mesh->getIndexEdge(v,prevI,edge); + m_mesh->getVertex(v)->removeEdge(edge); + m_mesh->getVertex(prevI)->removeEdge(edge); + m_mesh->getIndexEdge(nextI,prevI,edge); + m_mesh->getVertex(nextI)->removeEdge(edge); + m_mesh->getVertex(prevI)->removeEdge(edge); + freeVerts(prevI, m_mesh->getVertex(prevI)); + } + return faceK; +} + +/** + * Returns a new quad (convex) from the merge of two triangles that share the + * vertex index v. + * @param faceI mesh triangle + * @param faceJ mesh triangle + * @param v vertex index shared by both triangles + * @return a new convex quad if the merge is possible + */ +BOP_Face* BOP_Merge2::createQuad(BOP_Face4 *faceI, BOP_Face4 *faceJ) +{ + BOP_Face *faceK = NULL; + // + // Test if both quads share a vertex index + // + BOP_Index v; + unsigned int i; + for(i=0;i<4 ;i++) { + v = faceI->getVertex(i); + if( faceJ->containsVertex(v) ) break; + } + if (i == 3) return NULL; + + + // Get faces data + BOP_Index prevI, nextI, oppI, prevJ, nextJ, oppJ; + faceI->getNeighbours(v,prevI,nextI,oppI); + faceJ->getNeighbours(v,prevJ,nextJ,oppJ); + + // Quad test + BOP_Index edge; + if (nextI == prevJ) { + if (prevI == nextJ) { // v is in center + faceK = new BOP_Face4(nextI,oppI,nextJ,oppJ,faceI->getPlane(),faceI->getOriginalFace()); + faceK->setTAG(faceI->getTAG()); + m_mesh->getIndexEdge(v,prevI,edge); + m_mesh->getVertex(v)->removeEdge(edge); + m_mesh->getVertex(prevI)->removeEdge(edge); + m_mesh->getIndexEdge(v,nextI,edge); + m_mesh->getVertex(v)->removeEdge(edge); + m_mesh->getVertex(nextI)->removeEdge(edge); + freeVerts(v, m_mesh->getVertex(v)); + } else if (oppI == oppJ) { // nextI is in center + faceK = new BOP_Face4(v,nextJ,oppJ,prevI,faceI->getPlane(),faceI->getOriginalFace()); + faceK->setTAG(faceI->getTAG()); + m_mesh->getIndexEdge(v,nextI,edge); + m_mesh->getVertex(v)->removeEdge(edge); + m_mesh->getVertex(nextI)->removeEdge(edge); + m_mesh->getIndexEdge(prevI,nextI,edge); + m_mesh->getVertex(prevI)->removeEdge(edge); + m_mesh->getVertex(nextI)->removeEdge(edge); + freeVerts(nextI, m_mesh->getVertex(nextI)); + } + } else if (prevI == nextJ && oppI == oppJ) { // prevI is in center + faceK = new BOP_Face4(v,nextI,oppJ,prevJ,faceI->getPlane(),faceI->getOriginalFace()); + faceK->setTAG(faceI->getTAG()); + m_mesh->getIndexEdge(v,prevI,edge); + m_mesh->getVertex(v)->removeEdge(edge); + m_mesh->getVertex(prevI)->removeEdge(edge); + m_mesh->getIndexEdge(nextI,prevI,edge); + m_mesh->getVertex(nextI)->removeEdge(edge); + m_mesh->getVertex(prevI)->removeEdge(edge); + freeVerts(prevI, m_mesh->getVertex(prevI)); + } + return faceK; +} + +/** + * Returns if a index is inside a set of indexs. + * @param indexs set of indexs + * @param i index + * @return true if the index is inside the set, false otherwise + */ +bool BOP_Merge2::containsIndex(BOP_Indexs indexs, BOP_Index i) +{ + const BOP_IT_Indexs indexsEnd = indexs.end(); + for(BOP_IT_Indexs it=indexs.begin();it!=indexsEnd;it++) { + if (*it == i) return true; + } + return false; +} + +/** + * Creates a list of lists L1, L2, ... LN where + * LX = mesh faces with vertex v that come from the same original face + * @param facesByOriginalFace list of faces lists + * @param v vertex index + */ +void BOP_Merge2::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Index v) +{ + // Get edges with vertex v + + BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges(); + const BOP_IT_Indexs edgeEnd = edgeIndexs.end(); + for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) { + // For each edge, add its no broken faces to the output list + BOP_Edge* edge = m_mesh->getEdge(*edgeIndex); + BOP_Indexs faceIndexs = edge->getFaces(); + const BOP_IT_Indexs faceEnd = faceIndexs.end(); + for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) { + BOP_Face* face = m_mesh->getFace(*faceIndex); + if (face->getTAG() != BROKEN) { + bool found = false; + // Search if we already have created a list for the + // faces that come from the same original face + const BOP_IT_LFaces lfEnd = facesByOriginalFace.end(); + for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin(); + facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) { + if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) { + // Search that the face has not been added to the list before + for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) { + if ((*facesByOriginalFaceX)[i] == face) { + found = true; + break; + } + } + if (!found) { + // Add the face to the list + if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face); + else facesByOriginalFaceX->push_back(face); + found = true; + } + break; + } + } + if (!found) { + // Create a new list and add the current face + BOP_Faces facesByOriginalFaceX; + facesByOriginalFaceX.push_back(face); + facesByOriginalFace.push_back(facesByOriginalFaceX); + } + } + } + } +} + +/** + * Creates a list of lists L1, L2, ... LN where + * LX = mesh faces with vertex v that come from the same original face + * and without any of the vertices that appear before v in vertices + * @param facesByOriginalFace list of faces lists + * @param vertices vector with vertices indexs that contains v + * @param v vertex index + */ +void BOP_Merge2::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Indexs vertices, BOP_Index v) +{ + // Get edges with vertex v + BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges(); + const BOP_IT_Indexs edgeEnd = edgeIndexs.end(); + for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) { + // Foreach edge, add its no broken faces to the output list + BOP_Edge* edge = m_mesh->getEdge(*edgeIndex); + BOP_Indexs faceIndexs = edge->getFaces(); + const BOP_IT_Indexs faceEnd = faceIndexs.end(); + for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) { + BOP_Face* face = m_mesh->getFace(*faceIndex); + if (face->getTAG() != BROKEN) { + // Search if the face contains any of the forbidden vertices + bool found = false; + for(BOP_IT_Indexs vertex = vertices.begin();*vertex!= v;vertex++) { + if (face->containsVertex(*vertex)) { + // face contains a forbidden vertex! + found = true; + break; + } + } + if (!found) { + // Search if we already have created a list with the + // faces that come from the same original face + const BOP_IT_LFaces lfEnd = facesByOriginalFace.end(); + for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin(); + facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) { + if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) { + // Search that the face has not been added to the list before + for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) { + if ((*facesByOriginalFaceX)[i] == face) { + found = true; + break; + } + } + if (!found) { + // Add face to the list + if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face); + else facesByOriginalFaceX->push_back(face); + found = true; + } + break; + } + } + if (!found) { + // Create a new list and add the current face + BOP_Faces facesByOriginalFaceX; + facesByOriginalFaceX.push_back(face); + facesByOriginalFace.push_back(facesByOriginalFaceX); + } + } + } + } + } +} + +#endif /* BOP_NEW_MERGE */ diff --git a/intern/boolop/intern/BOP_Merge2.h b/intern/boolop/intern/BOP_Merge2.h new file mode 100644 index 00000000000..1e5945a889f --- /dev/null +++ b/intern/boolop/intern/BOP_Merge2.h @@ -0,0 +1,99 @@ +/** + * ***** 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): none yet. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef BOP_MERGE2_H +#define BOP_MERGE2_H + +#include "BOP_Misc.h" + +#ifdef BOP_NEW_MERGE + +#include "BOP_Mesh.h" +#include "BOP_Tag.h" +#include "BOP_MathUtils.h" +#include "MEM_SmartPtr.h" + +typedef vector< BOP_Faces > BOP_LFaces; +typedef vector< BOP_Faces >::iterator BOP_IT_LFaces; + +class BOP_Merge2 { + private: + BOP_Mesh* m_mesh; + BOP_Index m_firstVertex; + static BOP_Merge2 SINGLETON; + + BOP_Merge2() {}; + bool mergeFaces(); + bool mergeFaces(BOP_Indexs &mergeVertices); + bool mergeFaces(BOP_Faces &oldFaces, BOP_Faces &newFaces, BOP_Indexs &vertices, BOP_Index v); + bool mergeFaces(BOP_Faces &faces, BOP_Faces &oldFaces, BOP_Faces &newFaces, BOP_Indexs &vertices, BOP_Index v); + BOP_Face *mergeFaces(BOP_Face *faceI, BOP_Face *faceJ, BOP_Index v); + BOP_Face *mergeFaces(BOP_Face *faceI, BOP_Face *faceJ, BOP_Indexs &pending, BOP_Index v); + BOP_Face *mergeFaces(BOP_Face3 *faceI, BOP_Face3 *faceJ, BOP_Index v); + BOP_Face *mergeFaces(BOP_Face4 *faceI, BOP_Face3 *faceJ, BOP_Index v); + BOP_Face *mergeFaces(BOP_Face4 *faceI, BOP_Face3 *faceJ, BOP_Indexs &pending, BOP_Index v); + BOP_Face *mergeFaces(BOP_Face4 *faceI, BOP_Face4 *faceJ, BOP_Indexs &pending, BOP_Index v); + bool createQuads(); + bool containsIndex(BOP_Indexs indexs, BOP_Index index); + void getFaces(BOP_LFaces &facesByOriginalFace, BOP_Index v); + void getFaces(BOP_LFaces &facesByOriginalFace, BOP_Indexs vertices, BOP_Index v); + BOP_Face *createQuad(BOP_Face3 *faceI, BOP_Face3 *faceJ); + BOP_Face *createQuad(BOP_Face3 *faceI, BOP_Face4 *faceJ); + BOP_Face *createQuad(BOP_Face4 *faceI, BOP_Face4 *faceJ); + + bool mergeVertex(BOP_Face *faceI, BOP_Face *faceJ, BOP_Index v, + BOP_Indexs &mergeVertices); + bool mergeVertex(BOP_Face *faceI, BOP_Face *faceJ, BOP_Index v, + BOP_Indexs &pending, BOP_Faces &oldFaces, BOP_Faces &newFaces ); + BOP_Face *find3Neighbor(BOP_Face *faceI, BOP_Face *faceJ, + BOP_Index X, BOP_Index I, BOP_Index P, BOP_Index N ); + BOP_Face *find4Neighbor(BOP_Face *faceI, BOP_Face *faceJ, + BOP_Index X, BOP_Index I, BOP_Index P, BOP_Index N, + BOP_Face **faceL, BOP_Index &O); + BOP_Face3 *collapse(BOP_Face4 *faceC, BOP_Index X); + void mergeFaces(BOP_Face *A, BOP_Face *B, BOP_Index X, + BOP_Index I, BOP_Index N, BOP_Index P, BOP_Faces &newFaces ); + void freeVerts(BOP_Index v, BOP_Vertex *vert); + + void mergeVertex(BOP_Faces&, BOP_Index, BOP_Index); + void mergeVertex(BOP_Face3 *, BOP_Index, BOP_Index); + void mergeVertex(BOP_Face4 *, BOP_Index, BOP_Index); + void cleanup( void ); + + public: + + static BOP_Merge2 &getInstance() { + return SINGLETON; + } + + void mergeFaces(BOP_Mesh *m, BOP_Index v); +}; + +void dumpmesh(BOP_Mesh *, bool); + +#endif /* BOP_NEW_MERGE2 */ +#endif diff --git a/intern/boolop/intern/BOP_Mesh.cpp b/intern/boolop/intern/BOP_Mesh.cpp index 5659cd62a3f..075884a1920 100644 --- a/intern/boolop/intern/BOP_Mesh.cpp +++ b/intern/boolop/intern/BOP_Mesh.cpp @@ -449,6 +449,13 @@ bool BOP_Mesh::getIndexEdge(BOP_Index v1, BOP_Index v2, BOP_Index &e) printf ("found edge (%d %d)\n",v1,v2); #endif e = edge->index; +#ifdef BOP_NEW_MERGE + if( m_edges[e]->getUsed() == false ) { + m_edges[e]->setUsed(true); + m_vertexs[v1]->addEdge(e); + m_vertexs[v2]->addEdge(e); + } +#endif return true; } #ifdef HASH_PRINTF_DEBUG @@ -794,7 +801,8 @@ bool BOP_Mesh::isClosedMesh() } -/** *************************************************************************** +#ifdef BOP_DEBUG +/****************************************************************************** * DEBUG METHODS * * This functions are used to test the mesh state and debug program errors. * ******************************************************************************/ @@ -1075,3 +1083,4 @@ void BOP_Mesh::updatePlanes() } } +#endif diff --git a/intern/boolop/intern/BOP_Mesh.h b/intern/boolop/intern/BOP_Mesh.h index 9abff52545f..46c8fa53d20 100644 --- a/intern/boolop/intern/BOP_Mesh.h +++ b/intern/boolop/intern/BOP_Mesh.h @@ -1,10 +1,3 @@ -/* - * TEMPORARY defines to enable hashing support - */ - -#define HASH(x) ((x) >> 5) /* each "hash" covers 32 indices */ -// #define HASH_PRINTF_DEBUG /* uncomment to enable debug output */ - /** * * $Id$ diff --git a/intern/boolop/intern/BOP_Misc.h b/intern/boolop/intern/BOP_Misc.h new file mode 100644 index 00000000000..d021579d161 --- /dev/null +++ b/intern/boolop/intern/BOP_Misc.h @@ -0,0 +1,54 @@ +/** + * + * $Id: BOP_Misc.h 14444 2008-04-16 22:40:48Z khughes $ + * + * ***** 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): Ken Hughes + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/* + * This file contains various definitions used across the modules + */ + +/* + * define operator>> for faces, edges and vertices, and also add some + * debugging functions for displaying various internal data structures + */ + +// #define BOP_DEBUG + +#define HASH(x) ((x) >> 5) /* each "hash" covers 32 indices */ +// #define HASH_PRINTF_DEBUG /* uncomment to enable debug output */ + +/* + * temporary: control which method is used to merge final triangles and + * quads back together after an operation. If both methods are included, + * the "rt" debugging button on the Scene panel (F10) is used to control + * which is active. Setting it to 100 enables the original method, any + * other value enables the new method. + */ + +#define BOP_ORIG_MERGE /* include original merge code */ +#define BOP_NEW_MERGE /* include new merge code */ diff --git a/intern/boolop/intern/BOP_Tag.h b/intern/boolop/intern/BOP_Tag.h index 705f4885866..ead10fa6040 100644 --- a/intern/boolop/intern/BOP_Tag.h +++ b/intern/boolop/intern/BOP_Tag.h @@ -39,7 +39,7 @@ #define OUTON_TAG 0x11 // Above and on the plane #define UNCLASSIFIED_TAG 0x0F // Expecting to be classified -#define PHANTOM_TAG 0x0C // Phantom face +#define PHANTOM_TAG 0x0C // Phantom face: verts form collinear triangle #define OVERLAPPED_TAG 0x0D // Overlapped face #define BROKEN_TAG 0x0B // Splitted and unused ... diff --git a/intern/boolop/intern/BOP_Vertex.cpp b/intern/boolop/intern/BOP_Vertex.cpp index a429c26d204..edb53ea6a59 100644 --- a/intern/boolop/intern/BOP_Vertex.cpp +++ b/intern/boolop/intern/BOP_Vertex.cpp @@ -89,3 +89,22 @@ bool BOP_Vertex::containsEdge(BOP_Index i) return false; } + +#ifdef BOP_DEBUG +/** + * Implements operator <<. + */ +#include <iomanip> + +ostream &operator<<(ostream &stream, BOP_Vertex *v) +{ + char aux[20]; + BOP_stringTAG(v->m_tag,aux); + MT_Point3 point = v->getPoint(); + stream << setprecision(6) << showpoint << fixed; + stream << "Vertex[" << point[0] << "," << point[1] << ","; + stream << point[2] << "] (" << aux << ")"; + return stream; +} +#endif + diff --git a/intern/boolop/intern/BOP_Vertex.h b/intern/boolop/intern/BOP_Vertex.h index 3a9895df6d3..18b2f168f8c 100644 --- a/intern/boolop/intern/BOP_Vertex.h +++ b/intern/boolop/intern/BOP_Vertex.h @@ -31,6 +31,7 @@ #include "BOP_Tag.h" #include "BOP_Indexs.h" #include "MT_Point3.h" +#include "BOP_Misc.h" class BOP_Vertex { @@ -52,6 +53,10 @@ public: inline MT_Point3 getPoint() const { return m_point;}; inline BOP_TAG getTAG() { return m_tag;}; inline void setTAG(BOP_TAG t) { m_tag = t;}; +#ifdef BOP_DEBUG + friend ostream &operator<<(ostream &stream, BOP_Vertex *v); +#endif + }; #endif |