|
Blender
V2.59
|
00001 /* 00002 * 00003 * $Id: BOP_Merge2.cpp 35143 2011-02-25 10:32:33Z jesterking $ 00004 * 00005 * ***** BEGIN GPL LICENSE BLOCK ***** 00006 * 00007 * This program is free software; you can redistribute it and/or 00008 * modify it under the terms of the GNU General Public License 00009 * as published by the Free Software Foundation; either version 2 00010 * of the License, or (at your option) any later version. 00011 * 00012 * This program is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU General Public License 00018 * along with this program; if not, write to the Free Software Foundation, 00019 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 00020 * 00021 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. 00022 * All rights reserved. 00023 * 00024 * The Original Code is: all of this file. 00025 * 00026 * Contributor(s): Marc Freixas, Ken Hughes 00027 * 00028 * ***** END GPL LICENSE BLOCK ***** 00029 */ 00030 00036 #include "BOP_Merge2.h" 00037 00038 #ifdef BOP_NEW_MERGE 00039 00040 static void deleteFace(BOP_Mesh *m, BOP_Face *face); 00041 00045 BOP_Merge2 BOP_Merge2::SINGLETON; 00046 00047 #ifdef BOP_DEBUG 00048 void dumpmesh ( BOP_Mesh *m, bool force ) 00049 { 00050 unsigned int nonmanifold = 0; 00051 { 00052 BOP_Edges edges = m->getEdges(); 00053 int count = 0; 00054 for (BOP_IT_Edges edge = edges.begin(); edge != edges.end(); 00055 ++count, ++edge) { 00056 if (!(*edge)->getUsed() && (*edge)->getFaces().size() == 0 ) continue; 00057 BOP_Vertex * v1 = m->getVertex((*edge)->getVertex1()); 00058 BOP_Vertex * v2 = m->getVertex((*edge)->getVertex2()); 00059 00060 if(v1->getTAG()!= BROKEN || v2->getTAG()!= BROKEN ) { 00061 int fcount = 0; 00062 BOP_Indexs faces = (*edge)->getFaces(); 00063 for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); face++) { 00064 BOP_Face *f = m->getFace(*face); 00065 if(f->getTAG()== UNCLASSIFIED) ++fcount; 00066 } 00067 00068 00069 if(fcount !=0 && fcount !=2 ) { 00070 ++nonmanifold; 00071 } 00072 } 00073 } 00074 if (!force && nonmanifold == 0) return; 00075 } 00076 if( nonmanifold ) 00077 cout << nonmanifold << " edges detected" << endl; 00078 #ifdef BOP_DEBUG 00079 cout << "---------------------------" << endl; 00080 00081 BOP_Edges edges = m->getEdges(); 00082 int count = 0; 00083 for (BOP_IT_Edges edge = edges.begin(); edge != edges.end(); 00084 ++count, ++edge) { 00085 BOP_Vertex * v1 = m->getVertex((*edge)->getVertex1()); 00086 BOP_Vertex * v2 = m->getVertex((*edge)->getVertex2()); 00087 00088 if(v1->getTAG()!= BROKEN || v2->getTAG()!= BROKEN ) { 00089 int fcount = 0; 00090 BOP_Indexs faces = (*edge)->getFaces(); 00091 cout << count << ", " << (*edge) << ", " << faces.size() << endl; 00092 for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); face++) { 00093 BOP_Face *f = m->getFace(*face); 00094 if(f->getTAG()== UNCLASSIFIED) ++fcount; 00095 cout << " face " << f << endl; 00096 } 00097 00098 00099 if(fcount !=0 && fcount !=2 ) 00100 cout << " NON-MANIFOLD" << endl; 00101 } 00102 } 00103 00104 BOP_Faces faces = m->getFaces(); 00105 count = 0; 00106 for (BOP_IT_Faces face = faces.begin(); face != faces.end(); face++) { 00107 if( count < 12*2 || (*face)->getTAG() != BROKEN ) { 00108 cout << count << ", " << *face << endl; 00109 } 00110 ++count; 00111 } 00112 00113 BOP_Vertexs verts = m->getVertexs(); 00114 count = 0; 00115 for (BOP_IT_Vertexs vert = verts.begin(); vert != verts.end(); vert++) { 00116 cout << count++ << ", " << *vert << " " << (*vert)->getNumEdges() << endl; 00117 BOP_Indexs edges = (*vert)->getEdges(); 00118 for( BOP_IT_Indexs it = edges.begin(); it != edges.end(); ++it) { 00119 BOP_Edge *edge = m->getEdge(*it); 00120 cout << " " << edge << endl; 00121 } 00122 } 00123 cout << "===========================" << endl; 00124 #endif 00125 } 00126 #endif 00127 00134 void BOP_Merge2::mergeFaces(BOP_Mesh *m, BOP_Index v) 00135 { 00136 m_mesh = m; 00137 00138 #ifdef BOP_DEBUG 00139 cout << "##############################" << endl; 00140 #endif 00141 cleanup( ); 00142 00143 m_firstVertex = v; 00144 bool cont = false; 00145 00146 // Merge faces 00147 mergeFaces(); 00148 00149 do { 00150 // Add quads ... 00151 cont = createQuads(); 00152 // ... and merge new faces 00153 if( cont ) cont = mergeFaces(); 00154 00155 #ifdef BOP_DEBUG 00156 cout << "called mergeFaces " << cont << endl; 00157 #endif 00158 // ... until the merge is not succesful 00159 } while(cont); 00160 } 00161 00162 void clean_nonmanifold( BOP_Mesh *m ) 00163 { 00164 return; 00165 00166 BOP_Edges nme; 00167 BOP_Edges e = m->getEdges(); 00168 for( BOP_IT_Edges it = e.begin(); it != e.end(); ++it ) { 00169 BOP_Indexs faces = (*it)->getFaces(); 00170 if( faces.size() & ~2 ) 00171 nme.push_back(*it); 00172 } 00173 if (nme.size() == 0) return; 00174 for( BOP_IT_Edges it = nme.begin(); it != nme.end(); ++it ) { 00175 if( (*it)->getFaces().size() > 1 ) { 00176 BOP_Indexs faces = (*it)->getFaces(); 00177 for( BOP_IT_Indexs face = faces.begin(); face != faces.end(); ++face ) { 00178 MT_Point3 vertex1 = m->getVertex(m->getFace(*face)->getVertex(0))->getPoint(); 00179 MT_Point3 vertex2 = m->getVertex(m->getFace(*face)->getVertex(1))->getPoint(); 00180 MT_Point3 vertex3 = m->getVertex(m->getFace(*face)->getVertex(2))->getPoint(); 00181 if (BOP_collinear(vertex1,vertex2,vertex3)) // collinear triangle 00182 deleteFace(m,m->getFace(*face)); 00183 } 00184 continue; 00185 } 00186 BOP_Face *oface1 = m->getFace((*it)->getFaces().front()); 00187 BOP_Face *oface2, *tmpface; 00188 BOP_Index first =(*it)->getVertex1(); 00189 BOP_Index next =(*it)->getVertex2(); 00190 BOP_Index last = first; 00191 unsigned short facecount = 0; 00192 bool found = false; 00193 BOP_Indexs vertList; 00194 #ifdef BOP_DEBUG 00195 cout << " first edge is " << (*it) << endl; 00196 #endif 00197 vertList.push_back(first); 00198 BOP_Edge *edge; 00199 while(true) { 00200 BOP_Vertex *vert = m->getVertex(next); 00201 BOP_Indexs edges = vert->getEdges(); 00202 edge = NULL; 00203 for( BOP_IT_Indexs eit = edges.begin(); eit != edges.end(); ++eit) { 00204 edge = m->getEdge(*eit); 00205 if( edge->getFaces().size() > 1) { 00206 edge = NULL; 00207 continue; 00208 } 00209 if( edge->getVertex1() == next && edge->getVertex2() != last ) { 00210 last = next; 00211 next = edge->getVertex2(); 00212 break; 00213 } 00214 if( edge->getVertex2() == next && edge->getVertex1() != last ) { 00215 last = next; 00216 next = edge->getVertex1(); 00217 break; 00218 } 00219 edge = NULL; 00220 } 00221 if( !edge ) break; 00222 #ifdef BOP_DEBUG 00223 cout << " next edge is " << edge << endl; 00224 #endif 00225 tmpface = m->getFace(edge->getFaces().front()); 00226 if( oface1->getOriginalFace() != tmpface->getOriginalFace() ) 00227 oface2 = tmpface; 00228 else 00229 ++facecount; 00230 vertList.push_back(last); 00231 if( vertList.size() > 3 ) break; 00232 if( next == first ) { 00233 found = true; 00234 break; 00235 } 00236 } 00237 if(found) { 00238 edge = *it; 00239 #ifdef BOP_DEBUG 00240 cout << " --> found a loop" << endl; 00241 #endif 00242 if( vertList.size() == 3 ) { 00243 BOP_Face3 *face = (BOP_Face3 *)m->getFace(edge->getFaces().front()); 00244 face->getNeighbours(first,last,next); 00245 } else if( vertList.size() == 4 ) { 00246 BOP_Face4 *face = (BOP_Face4 *)m->getFace(edge->getFaces().front()); 00247 face->getNeighbours(first,last,next,last); 00248 } else { 00249 #ifdef BOP_DEBUG 00250 cout << "loop has " << vertList.size() << "verts"; 00251 #endif 00252 continue; 00253 } 00254 if(facecount == 1) oface1 = oface2; 00255 next = vertList[1]; 00256 last = vertList[2]; 00257 if( edge->getVertex2() == next ) { 00258 BOP_Face3 *f = new BOP_Face3(next,first,last, 00259 oface1->getPlane(),oface1->getOriginalFace()); 00260 m->addFace( f ); 00261 #ifdef BOP_DEBUG 00262 cout << " face is backward: " << f << endl; 00263 #endif 00264 00265 } else { 00266 BOP_Face3 *f = new BOP_Face3(last,first,next, 00267 oface1->getPlane(),oface1->getOriginalFace()); 00268 m->addFace( f ); 00269 #ifdef BOP_DEBUG 00270 cout << " face is forward: " << f << endl; 00271 #endif 00272 } 00273 } 00274 } 00275 } 00276 00286 void BOP_Merge2::cleanup( void ) 00287 { 00288 BOP_Edges edges = m_mesh->getEdges(); 00289 for (BOP_IT_Edges edge = edges.begin(); edge != edges.end(); ++edge) { 00290 BOP_Indexs faces = (*edge)->getFaces(); 00291 for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); ++face) { 00292 BOP_Face *f = m_mesh->getFace(*face); 00293 if(f->getTAG()== UNCLASSIFIED) ; 00294 else (*edge)->removeFace(*face); 00295 } 00296 if( (*edge)->getFaces().size() == 0) (*edge)->setUsed(false); 00297 } 00298 00299 BOP_Vertexs v = m_mesh->getVertexs(); 00300 for( BOP_IT_Vertexs it = v.begin(); it != v.end(); ++it ) { 00301 if( (*it)->getTAG() != BROKEN) { 00302 BOP_Indexs iedges = (*it)->getEdges(); 00303 for(BOP_IT_Indexs i = iedges.begin();i!=iedges.end();i++) 00304 if( m_mesh->getEdge((*i))->getUsed( ) == false) (*it)->removeEdge( *i ); 00305 if( (*it)->getEdges().size() == 0 ) (*it)->setTAG(BROKEN); 00306 } 00307 } 00308 // clean_nonmanifold( m_mesh ); 00309 } 00310 00314 bool BOP_Merge2::mergeFaces() 00315 { 00316 BOP_Indexs mergeVertices; 00317 BOP_Vertexs vertices = m_mesh->getVertexs(); 00318 BOP_IT_Vertexs v = vertices.begin(); 00319 const BOP_IT_Vertexs verticesEnd = vertices.end(); 00320 00321 // Advance to first mergeable vertex 00322 advance(v,m_firstVertex); 00323 BOP_Index pos = m_firstVertex; 00324 00325 // Add unbroken vertices to the list 00326 while(v!=verticesEnd) { 00327 if ((*v)->getTAG() != BROKEN) { 00328 mergeVertices.push_back(pos); 00329 } 00330 00331 v++; 00332 pos++; 00333 } 00334 00335 // Merge faces with that vertices 00336 return mergeFaces(mergeVertices); 00337 } 00338 00342 void BOP_Merge2::freeVerts(BOP_Index v, BOP_Vertex *vert) 00343 { 00344 BOP_Indexs edges = vert->getEdges(); 00345 BOP_Vertex *other; 00346 00347 for( BOP_IT_Indexs it = edges.begin(); it != edges.end(); ++it) { 00348 BOP_Edge *edge = m_mesh->getEdge(*it); 00349 BOP_Indexs edges2; 00350 if( edge->getVertex1() != v ) 00351 other = m_mesh->getVertex( edge->getVertex1() ); 00352 else 00353 other = m_mesh->getVertex( edge->getVertex2() ); 00354 other->removeEdge(*it); 00355 vert->removeEdge(*it); 00356 } 00357 } 00358 00364 bool BOP_Merge2::mergeFaces(BOP_Indexs &mergeVertices) 00365 { 00366 // Check size > 0! 00367 if (mergeVertices.size() == 0) return false; 00368 bool didMerge = false; 00369 00370 for( BOP_Index i = 0; i < mergeVertices.size(); ++i ) { 00371 BOP_LFaces facesByOriginalFace; 00372 BOP_Index v = mergeVertices[i]; 00373 BOP_Vertex *vert = m_mesh->getVertex(v); 00374 #ifdef BOP_DEBUG 00375 cout << "i = " << i << ", v = " << v << ", vert = " << vert << endl; 00376 if (v==48) 00377 cout << "found vert 48" << endl; 00378 #endif 00379 if ( vert->getTAG() != BROKEN ) { 00380 getFaces(facesByOriginalFace,v); 00381 00382 switch (facesByOriginalFace.size()) { 00383 case 0: 00384 // v has no unbroken faces (so it's a new BROKEN vertex) 00385 freeVerts( v, vert ); 00386 vert->setTAG(BROKEN); 00387 break; 00388 case 2: { 00389 #ifdef BOP_DEBUG 00390 cout << "size of fBOF = " << facesByOriginalFace.size() << endl; 00391 #endif 00392 BOP_Faces ff = facesByOriginalFace.front(); 00393 BOP_Faces fb = facesByOriginalFace.back(); 00394 BOP_Index eindexs[2]; 00395 int ecount = 0; 00396 00397 // look for two edges adjacent to v which contain both ofaces 00398 BOP_Indexs edges = vert->getEdges(); 00399 #ifdef BOP_DEBUG 00400 cout << " ff has " << ff.size() << " faces" << endl; 00401 cout << " fb has " << fb.size() << " faces" << endl; 00402 cout << " v has " << edges.size() << " edges" << endl; 00403 #endif 00404 for(BOP_IT_Indexs it = edges.begin(); it != edges.end(); 00405 ++it ) { 00406 BOP_Edge *edge = m_mesh->getEdge(*it); 00407 BOP_Indexs faces = edge->getFaces(); 00408 #ifdef BOP_DEBUG 00409 cout << " " << edge << " has " << edge->getFaces().size() << " faces" << endl; 00410 #endif 00411 if( faces.size() == 2 ) { 00412 BOP_Face *f0 = m_mesh->getFace(faces[0]); 00413 BOP_Face *f1 = m_mesh->getFace(faces[1]); 00414 if( f0->getOriginalFace() != f1->getOriginalFace() ) { 00415 #ifdef BOP_DEBUG 00416 cout << " " << f0 << endl; 00417 cout << " " << f1 << endl; 00418 #endif 00419 eindexs[ecount++] = (*it); 00420 } 00421 } 00422 } 00423 if(ecount == 2) { 00424 #ifdef BOP_DEBUG 00425 cout << " edge indexes are " << eindexs[0]; 00426 cout << " and " << eindexs[1] << endl; 00427 #endif 00428 BOP_Edge *edge = m_mesh->getEdge(eindexs[0]); 00429 BOP_Index N = edge->getVertex1(); 00430 if(N == v) N = edge->getVertex2(); 00431 #ifdef BOP_DEBUG 00432 cout << " ## OK, replace "<<v<<" with "<<N << endl; 00433 #endif 00434 mergeVertex(ff , v, N ); 00435 mergeVertex(fb , v, N ); 00436 // now remove v and its edges 00437 vert->setTAG(BROKEN); 00438 for(BOP_IT_Indexs it = edges.begin(); it != edges.end(); 00439 ++it ) { 00440 BOP_Edge *tedge = m_mesh->getEdge(*it); 00441 tedge->setUsed(false); 00442 } 00443 didMerge = true; 00444 } 00445 #ifdef BOP_DEBUG 00446 else { 00447 cout << " HUH: ecount was " << ecount << endl; 00448 } 00449 #endif 00450 } 00451 break; 00452 default: 00453 break; 00454 } 00455 } 00456 } 00457 00458 return didMerge; 00459 } 00460 00461 void BOP_Merge2::mergeVertex(BOP_Faces &faces, BOP_Index v1, BOP_Index v2) 00462 { 00463 for(BOP_IT_Faces face=faces.begin();face!=faces.end();face++) { 00464 if( (*face)->size() == 3) 00465 mergeVertex((BOP_Face3 *) *face, v1, v2); 00466 else 00467 mergeVertex((BOP_Face4 *) *face, v1, v2); 00468 (*face)->setTAG(BROKEN); 00469 #ifdef BOP_DEBUG 00470 cout << " breaking " << (*face) << endl; 00471 #endif 00472 } 00473 } 00474 00475 /* 00476 * Remove a face from the mesh and from each edges's face list 00477 */ 00478 00479 static void deleteFace(BOP_Mesh *m, BOP_Face *face) 00480 { 00481 BOP_Index l2 = face->getVertex(0); 00482 BOP_Faces faces = m->getFaces(); 00483 for(int i = face->size(); i-- ; ) { 00484 BOP_Indexs edges = m->getVertex(l2)->getEdges(); 00485 BOP_Index l1 = face->getVertex(i); 00486 for(BOP_IT_Indexs it1 = edges.begin(); it1 != edges.end(); ++it1 ) { 00487 BOP_Edge *edge = m->getEdge(*it1); 00488 if( ( edge->getVertex1() == l1 && edge->getVertex2() == l2 ) || 00489 ( edge->getVertex1() == l2 && edge->getVertex2() == l1 ) ) { 00490 BOP_Indexs ef = edge->getFaces(); 00491 for(BOP_IT_Indexs it = ef.begin(); it != ef.end(); ++it ) { 00492 if( m->getFace(*it) == face) { 00493 edge->removeFace(*it); 00494 break; 00495 } 00496 } 00497 break; 00498 } 00499 } 00500 l2 = l1; 00501 } 00502 face->setTAG(BROKEN); 00503 } 00504 00505 void BOP_Merge2::mergeVertex(BOP_Face3 *face, BOP_Index v1, BOP_Index v2) 00506 { 00507 BOP_Index next, prev; 00508 face->getNeighbours(v1,prev,next); 00509 00510 // if new vertex is not already in the tri, make a new tri 00511 if( prev != v2 && next != v2 ) { 00512 m_mesh->addFace( new BOP_Face3(prev,v2,next, 00513 face->getPlane(),face->getOriginalFace()) ); 00514 #ifdef BOP_DEBUG 00515 cout << "mv3: add " << prev << "," << v2 << "," << next << endl; 00516 } else { 00517 cout << "mv3: vertex already in tri: doing nothing" << endl; 00518 #endif 00519 } 00520 deleteFace(m_mesh, face); 00521 } 00522 00523 void BOP_Merge2::mergeVertex(BOP_Face4 *face, BOP_Index v1, BOP_Index v2) 00524 { 00525 BOP_Index next, prev, opp; 00526 face->getNeighbours(v1,prev,next,opp); 00527 00528 // if new vertex is already in the quad, replace quad with new tri 00529 if( prev == v2 || next == v2 ) { 00530 m_mesh->addFace( new BOP_Face3(prev,next,opp, 00531 face->getPlane(),face->getOriginalFace()) ); 00532 #ifdef BOP_DEBUG 00533 cout << "mv4a: add " << prev << "," << next << "," << opp << endl; 00534 #endif 00535 } 00536 // otherwise make a new quad 00537 else { 00538 m_mesh->addFace( new BOP_Face4(prev,v2,next,opp, 00539 face->getPlane(),face->getOriginalFace()) ); 00540 #ifdef BOP_DEBUG 00541 cout << "mv4b: add "<<prev<<","<<v2<<","<<next<<","<<opp<<endl; 00542 #endif 00543 } 00544 deleteFace(m_mesh, face); 00545 } 00546 00547 // #define OLD_QUAD 00548 00554 bool BOP_Merge2::createQuads() 00555 { 00556 00557 BOP_Faces quads; 00558 00559 // Get mesh faces 00560 BOP_Faces faces = m_mesh->getFaces(); 00561 00562 // Merge mesh triangles 00563 const BOP_IT_Faces facesIEnd = (faces.end()-1); 00564 const BOP_IT_Faces facesJEnd = faces.end(); 00565 for(BOP_IT_Faces faceI=faces.begin();faceI!=facesIEnd;faceI++) { 00566 #ifdef OLD_QUAD 00567 if ((*faceI)->getTAG() == BROKEN || (*faceI)->size() != 3) continue; 00568 for(BOP_IT_Faces faceJ=(faceI+1);faceJ!=facesJEnd;faceJ++) { 00569 if ((*faceJ)->getTAG() == BROKEN || (*faceJ)->size() != 3 || 00570 (*faceJ)->getOriginalFace() != (*faceI)->getOriginalFace()) continue; 00571 00572 00573 BOP_Face *faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face3*)*faceJ); 00574 if (faceK != NULL) { 00575 // Set triangles to BROKEN 00576 deleteFace(m_mesh, *faceI); 00577 deleteFace(m_mesh, *faceJ); 00578 #ifdef BOP_DEBUG 00579 cout << "createQuad: del " << *faceI << endl; 00580 cout << "createQuad: del " << *faceJ << endl; 00581 cout << "createQuad: add " << faceK << endl; 00582 #endif 00583 quads.push_back(faceK); 00584 break; 00585 } 00586 } 00587 #else 00588 if ((*faceI)->getTAG() == BROKEN ) continue; 00589 for(BOP_IT_Faces faceJ=(faceI+1);faceJ!=facesJEnd;faceJ++) { 00590 if ((*faceJ)->getTAG() == BROKEN || 00591 (*faceJ)->getOriginalFace() != (*faceI)->getOriginalFace()) continue; 00592 00593 BOP_Face *faceK = NULL; 00594 if((*faceI)->size() == 3) { 00595 if((*faceJ)->size() == 3) 00596 faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face3*)*faceJ); 00597 else 00598 faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face4*)*faceJ); 00599 } else { 00600 if((*faceJ)->size() == 3) 00601 faceK = createQuad((BOP_Face3*)*faceJ,(BOP_Face4*)*faceI); 00602 else 00603 faceK = createQuad((BOP_Face4*)*faceI,(BOP_Face4*)*faceJ); 00604 } 00605 00606 if (faceK != NULL) { 00607 // Set triangles to BROKEN 00608 deleteFace(m_mesh, *faceI); 00609 deleteFace(m_mesh, *faceJ); 00610 #ifdef BOP_DEBUG 00611 cout << "createQuad: del " << *faceI << endl; 00612 cout << "createQuad: del " << *faceJ << endl; 00613 cout << "createQuad: add " << faceK << endl; 00614 #endif 00615 quads.push_back(faceK); 00616 break; 00617 } 00618 } 00619 #endif 00620 } 00621 00622 // Add quads to mesh 00623 const BOP_IT_Faces quadsEnd = quads.end(); 00624 for(BOP_IT_Faces quad=quads.begin();quad!=quadsEnd;quad++) m_mesh->addFace(*quad); 00625 return (quads.size() > 0); 00626 } 00627 00636 BOP_Face* BOP_Merge2::createQuad(BOP_Face3 *faceI, BOP_Face3 *faceJ) 00637 { 00638 // Test if both triangles share a vertex index 00639 BOP_Index v; 00640 unsigned int i; 00641 for(i=0;i<3 ;i++) { 00642 v = faceI->getVertex(i); 00643 if( faceJ->containsVertex(v) ) break; 00644 } 00645 if (i == 3) return NULL; 00646 00647 BOP_Face *faceK = NULL; 00648 00649 // Get faces data 00650 BOP_Index prevI, nextI, prevJ, nextJ; 00651 faceI->getNeighbours(v,prevI,nextI); 00652 faceJ->getNeighbours(v,prevJ,nextJ); 00653 MT_Point3 vertex = m_mesh->getVertex(v)->getPoint(); 00654 MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint(); 00655 MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint(); 00656 MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint(); 00657 MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint(); 00658 00659 // Quad test 00660 if (prevI == nextJ) { 00661 if (!BOP_collinear(vNextI,vertex,vPrevJ) && !BOP_collinear(vNextI,vPrevI,vPrevJ) && 00662 BOP_convex(vertex,vNextI,vPrevI,vPrevJ)) { 00663 faceK = new BOP_Face4(v,nextI,prevI,prevJ,faceI->getPlane(),faceI->getOriginalFace()); 00664 faceK->setTAG(faceI->getTAG()); 00665 BOP_Index edge; 00666 m_mesh->getIndexEdge(v,prevI,edge); 00667 m_mesh->getVertex(v)->removeEdge(edge); 00668 m_mesh->getVertex(prevI)->removeEdge(edge); 00669 } 00670 } 00671 else if (nextI == prevJ) { 00672 if (!BOP_collinear(vPrevI,vertex,vNextJ) && !BOP_collinear(vPrevI,vNextI,vNextJ) && 00673 BOP_convex(vertex,vNextJ,vNextI,vPrevI)) { 00674 faceK = new BOP_Face4(v,nextJ,nextI,prevI,faceI->getPlane(),faceI->getOriginalFace()); 00675 faceK->setTAG(faceI->getTAG()); 00676 BOP_Index edge; 00677 m_mesh->getIndexEdge(v,nextI,edge); 00678 m_mesh->getVertex(v)->removeEdge(edge); 00679 m_mesh->getVertex(nextI)->removeEdge(edge); 00680 } 00681 } 00682 return faceK; 00683 } 00684 00693 BOP_Face* BOP_Merge2::createQuad(BOP_Face3 *faceI, BOP_Face4 *faceJ) 00694 { 00695 // Test if triangle and quad share a vertex index 00696 BOP_Index v; 00697 unsigned int i; 00698 for(i=0;i<3 ;i++) { 00699 v = faceI->getVertex(i); 00700 if( faceJ->containsVertex(v) ) break; 00701 } 00702 if (i == 3) return NULL; 00703 00704 BOP_Face *faceK = NULL; 00705 00706 // Get faces data 00707 BOP_Index prevI, nextI, prevJ, nextJ, oppJ; 00708 faceI->getNeighbours(v,prevI,nextI); 00709 faceJ->getNeighbours(v,prevJ,nextJ,oppJ); 00710 00711 // Quad test 00712 BOP_Index edge; 00713 if (nextI == prevJ) { 00714 if (prevI == nextJ) { // v is in center 00715 faceK = new BOP_Face3(nextJ,oppJ,prevJ,faceI->getPlane(),faceI->getOriginalFace()); 00716 faceK->setTAG(faceI->getTAG()); 00717 m_mesh->getIndexEdge(v,prevI,edge); 00718 m_mesh->getVertex(v)->removeEdge(edge); 00719 m_mesh->getVertex(prevI)->removeEdge(edge); 00720 m_mesh->getIndexEdge(v,nextI,edge); 00721 m_mesh->getVertex(v)->removeEdge(edge); 00722 m_mesh->getVertex(nextI)->removeEdge(edge); 00723 freeVerts(v, m_mesh->getVertex(v)); 00724 } else if (prevI == oppJ) { // nextI is in center 00725 faceK = new BOP_Face3(v,nextJ,oppJ,faceI->getPlane(),faceI->getOriginalFace()); 00726 faceK->setTAG(faceI->getTAG()); 00727 m_mesh->getIndexEdge(v,nextI,edge); 00728 m_mesh->getVertex(v)->removeEdge(edge); 00729 m_mesh->getVertex(nextI)->removeEdge(edge); 00730 m_mesh->getIndexEdge(prevI,nextI,edge); 00731 m_mesh->getVertex(prevI)->removeEdge(edge); 00732 m_mesh->getVertex(nextI)->removeEdge(edge); 00733 freeVerts(nextI, m_mesh->getVertex(nextI)); 00734 } 00735 } else if (nextI == oppJ && prevI == nextJ ) { // prevI is in center 00736 faceK = new BOP_Face3(prevJ,v,oppJ,faceI->getPlane(),faceI->getOriginalFace()); 00737 faceK->setTAG(faceI->getTAG()); 00738 m_mesh->getIndexEdge(v,prevI,edge); 00739 m_mesh->getVertex(v)->removeEdge(edge); 00740 m_mesh->getVertex(prevI)->removeEdge(edge); 00741 m_mesh->getIndexEdge(nextI,prevI,edge); 00742 m_mesh->getVertex(nextI)->removeEdge(edge); 00743 m_mesh->getVertex(prevI)->removeEdge(edge); 00744 freeVerts(prevI, m_mesh->getVertex(prevI)); 00745 } 00746 return faceK; 00747 } 00748 00757 BOP_Face* BOP_Merge2::createQuad(BOP_Face4 *faceI, BOP_Face4 *faceJ) 00758 { 00759 BOP_Face *faceK = NULL; 00760 // 00761 // Test if both quads share a vertex index 00762 // 00763 BOP_Index v; 00764 unsigned int i; 00765 for(i=0;i<4 ;i++) { 00766 v = faceI->getVertex(i); 00767 if( faceJ->containsVertex(v) ) break; 00768 } 00769 if (i == 3) return NULL; 00770 00771 00772 // Get faces data 00773 BOP_Index prevI, nextI, oppI, prevJ, nextJ, oppJ; 00774 faceI->getNeighbours(v,prevI,nextI,oppI); 00775 faceJ->getNeighbours(v,prevJ,nextJ,oppJ); 00776 00777 // Quad test 00778 BOP_Index edge; 00779 if (nextI == prevJ) { 00780 if (prevI == nextJ) { // v is in center 00781 faceK = new BOP_Face4(nextI,oppI,nextJ,oppJ,faceI->getPlane(),faceI->getOriginalFace()); 00782 faceK->setTAG(faceI->getTAG()); 00783 m_mesh->getIndexEdge(v,prevI,edge); 00784 m_mesh->getVertex(v)->removeEdge(edge); 00785 m_mesh->getVertex(prevI)->removeEdge(edge); 00786 m_mesh->getIndexEdge(v,nextI,edge); 00787 m_mesh->getVertex(v)->removeEdge(edge); 00788 m_mesh->getVertex(nextI)->removeEdge(edge); 00789 freeVerts(v, m_mesh->getVertex(v)); 00790 } else if (oppI == oppJ) { // nextI is in center 00791 faceK = new BOP_Face4(v,nextJ,oppJ,prevI,faceI->getPlane(),faceI->getOriginalFace()); 00792 faceK->setTAG(faceI->getTAG()); 00793 m_mesh->getIndexEdge(v,nextI,edge); 00794 m_mesh->getVertex(v)->removeEdge(edge); 00795 m_mesh->getVertex(nextI)->removeEdge(edge); 00796 m_mesh->getIndexEdge(prevI,nextI,edge); 00797 m_mesh->getVertex(prevI)->removeEdge(edge); 00798 m_mesh->getVertex(nextI)->removeEdge(edge); 00799 freeVerts(nextI, m_mesh->getVertex(nextI)); 00800 } 00801 } else if (prevI == nextJ && oppI == oppJ) { // prevI is in center 00802 faceK = new BOP_Face4(v,nextI,oppJ,prevJ,faceI->getPlane(),faceI->getOriginalFace()); 00803 faceK->setTAG(faceI->getTAG()); 00804 m_mesh->getIndexEdge(v,prevI,edge); 00805 m_mesh->getVertex(v)->removeEdge(edge); 00806 m_mesh->getVertex(prevI)->removeEdge(edge); 00807 m_mesh->getIndexEdge(nextI,prevI,edge); 00808 m_mesh->getVertex(nextI)->removeEdge(edge); 00809 m_mesh->getVertex(prevI)->removeEdge(edge); 00810 freeVerts(prevI, m_mesh->getVertex(prevI)); 00811 } 00812 return faceK; 00813 } 00814 00821 bool BOP_Merge2::containsIndex(BOP_Indexs indexs, BOP_Index i) 00822 { 00823 const BOP_IT_Indexs indexsEnd = indexs.end(); 00824 for(BOP_IT_Indexs it=indexs.begin();it!=indexsEnd;it++) { 00825 if (*it == i) return true; 00826 } 00827 return false; 00828 } 00829 00836 void BOP_Merge2::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Index v) 00837 { 00838 // Get edges with vertex v 00839 00840 BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges(); 00841 const BOP_IT_Indexs edgeEnd = edgeIndexs.end(); 00842 for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) { 00843 // For each edge, add its no broken faces to the output list 00844 BOP_Edge* edge = m_mesh->getEdge(*edgeIndex); 00845 BOP_Indexs faceIndexs = edge->getFaces(); 00846 const BOP_IT_Indexs faceEnd = faceIndexs.end(); 00847 for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) { 00848 BOP_Face* face = m_mesh->getFace(*faceIndex); 00849 if (face->getTAG() != BROKEN) { 00850 bool found = false; 00851 // Search if we already have created a list for the 00852 // faces that come from the same original face 00853 const BOP_IT_LFaces lfEnd = facesByOriginalFace.end(); 00854 for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin(); 00855 facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) { 00856 if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) { 00857 // Search that the face has not been added to the list before 00858 for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) { 00859 if ((*facesByOriginalFaceX)[i] == face) { 00860 found = true; 00861 break; 00862 } 00863 } 00864 if (!found) { 00865 // Add the face to the list 00866 if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face); 00867 else facesByOriginalFaceX->push_back(face); 00868 found = true; 00869 } 00870 break; 00871 } 00872 } 00873 if (!found) { 00874 // Create a new list and add the current face 00875 BOP_Faces facesByOriginalFaceX; 00876 facesByOriginalFaceX.push_back(face); 00877 facesByOriginalFace.push_back(facesByOriginalFaceX); 00878 } 00879 } 00880 } 00881 } 00882 } 00883 00892 void BOP_Merge2::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Indexs vertices, BOP_Index v) 00893 { 00894 // Get edges with vertex v 00895 BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges(); 00896 const BOP_IT_Indexs edgeEnd = edgeIndexs.end(); 00897 for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) { 00898 // Foreach edge, add its no broken faces to the output list 00899 BOP_Edge* edge = m_mesh->getEdge(*edgeIndex); 00900 BOP_Indexs faceIndexs = edge->getFaces(); 00901 const BOP_IT_Indexs faceEnd = faceIndexs.end(); 00902 for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) { 00903 BOP_Face* face = m_mesh->getFace(*faceIndex); 00904 if (face->getTAG() != BROKEN) { 00905 // Search if the face contains any of the forbidden vertices 00906 bool found = false; 00907 for(BOP_IT_Indexs vertex = vertices.begin();*vertex!= v;vertex++) { 00908 if (face->containsVertex(*vertex)) { 00909 // face contains a forbidden vertex! 00910 found = true; 00911 break; 00912 } 00913 } 00914 if (!found) { 00915 // Search if we already have created a list with the 00916 // faces that come from the same original face 00917 const BOP_IT_LFaces lfEnd = facesByOriginalFace.end(); 00918 for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin(); 00919 facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) { 00920 if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) { 00921 // Search that the face has not been added to the list before 00922 for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) { 00923 if ((*facesByOriginalFaceX)[i] == face) { 00924 found = true; 00925 break; 00926 } 00927 } 00928 if (!found) { 00929 // Add face to the list 00930 if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face); 00931 else facesByOriginalFaceX->push_back(face); 00932 found = true; 00933 } 00934 break; 00935 } 00936 } 00937 if (!found) { 00938 // Create a new list and add the current face 00939 BOP_Faces facesByOriginalFaceX; 00940 facesByOriginalFaceX.push_back(face); 00941 facesByOriginalFace.push_back(facesByOriginalFaceX); 00942 } 00943 } 00944 } 00945 } 00946 } 00947 } 00948 00949 #endif /* BOP_NEW_MERGE */