|
Blender
V2.59
|
00001 /* 00002 * 00003 * $Id: BOP_Mesh.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): none yet. 00027 * 00028 * ***** END GPL LICENSE BLOCK ***** 00029 */ 00030 00036 #include "BOP_Mesh.h" 00037 #include "BOP_MathUtils.h" 00038 #include <iostream> 00039 #include <fstream> 00040 00041 #include "MEM_guardedalloc.h" 00042 #include "BLI_blenlib.h" 00043 00044 BOP_Mesh::BOP_Mesh() 00045 { 00046 #ifdef HASH 00047 #ifdef HASH_PRINTF_DEBUG 00048 printf ("has hashing\n"); 00049 #endif 00050 hash = NULL; 00051 hashsize = 0; 00052 #endif 00053 } 00054 00058 BOP_Mesh::~BOP_Mesh() 00059 { 00060 const BOP_IT_Vertexs vertexsEnd = m_vertexs.end(); 00061 for(BOP_IT_Vertexs itv=m_vertexs.begin();itv!=vertexsEnd;itv++){ 00062 delete *itv; 00063 } 00064 m_vertexs.clear(); 00065 00066 const BOP_IT_Edges edgesEnd = m_edges.end(); 00067 for(BOP_IT_Edges ite=m_edges.begin();ite!=edgesEnd;ite++){ 00068 delete *ite; 00069 } 00070 m_edges.clear(); 00071 00072 const BOP_IT_Faces facesEnd = m_faces.end(); 00073 for(BOP_IT_Faces itf=m_faces.begin();itf!=facesEnd;itf++){ 00074 delete *itf; 00075 } 00076 m_faces.clear(); 00077 00078 #ifdef HASH 00079 while( hashsize ) { 00080 --hashsize; 00081 BLI_freelistN( &hash[hashsize] ); 00082 } 00083 MEM_freeN( hash ); 00084 hash = NULL; 00085 #endif 00086 } 00087 00093 BOP_Index BOP_Mesh::addVertex(MT_Point3 p) 00094 { 00095 m_vertexs.push_back(new BOP_Vertex(p)); 00096 return m_vertexs.size()-1; 00097 } 00098 00105 BOP_Index BOP_Mesh::addEdge(BOP_Index v1, BOP_Index v2) 00106 { 00107 #ifdef HASH 00108 /* prepare a new hash entry for the edge */ 00109 int minv; 00110 EdgeEntry *h = (EdgeEntry *)MEM_callocN( sizeof( EdgeEntry ), "edgehash" ); 00111 00112 /* store sorted, smallest vert first */ 00113 if( v1 < v2 ) { 00114 minv = HASH(v1); 00115 h->v1 = v1; 00116 h->v2 = v2; 00117 } else { 00118 minv = HASH(v2); 00119 h->v1 = v2; 00120 h->v2 = v1; 00121 } 00122 h->index = m_edges.size(); 00123 00124 /* if hash index larger than hash list, extend the list */ 00125 if( minv >= hashsize ) { 00126 int newsize = (minv + 8) & ~7; 00127 ListBase *nhash = (ListBase *)MEM_mallocN( 00128 newsize * sizeof( ListBase ), 00129 "edgehashtable" ); 00130 /* copy old entries */ 00131 memcpy( nhash, hash, sizeof( ListBase ) * hashsize ); 00132 /* clear new ones */ 00133 while( hashsize < newsize ) { 00134 nhash[hashsize].first = nhash[hashsize].last = NULL; 00135 ++hashsize; 00136 } 00137 if( hash ) 00138 MEM_freeN( hash ); 00139 hash = nhash; 00140 } 00141 00142 /* add the entry to tail of the right hash list */ 00143 BLI_addtail( &hash[minv], h ); 00144 #endif 00145 m_edges.push_back(new BOP_Edge(v1,v2)); 00146 return m_edges.size()-1; 00147 } 00148 00149 #ifdef HASH 00150 00156 void BOP_Mesh::rehashVertex(BOP_Index o, BOP_Index n, BOP_Index x) 00157 { 00158 EdgeEntry *edge; 00159 int minv = HASH(o); 00160 BOP_Index v1, v2; 00161 00162 /* figure out where and what to look for */ 00163 if( o < x ) { 00164 minv = HASH(o); 00165 v1 = o; v2 = x; 00166 } else { 00167 minv = HASH(x); 00168 v1 = x; v2 = o; 00169 } 00170 00171 /* if hash is valid, search for the match */ 00172 if( minv < hashsize ) { 00173 for(edge = (EdgeEntry *)hash[minv].first; 00174 edge; edge = edge->next ) { 00175 if(edge->v1 == v1 && edge->v2 == v2) 00176 break; 00177 } 00178 00179 /* NULL edge == no match */ 00180 if(!edge) { 00181 #ifdef HASH_PRINTF_DEBUG 00182 printf ("OOPS! didn't find edge (%d %d)\n",v1,v2); 00183 #endif 00184 return; 00185 } 00186 #ifdef HASH_PRINTF_DEBUG 00187 printf ("found edge (%d %d)\n",v1,v2); 00188 #endif 00189 /* remove the edge from the old hash list */ 00190 BLI_remlink( &hash[minv], edge ); 00191 00192 /* decide where the new edge should go */ 00193 if( n < x ) { 00194 minv = HASH(n); 00195 v1 = n; v2 = x; 00196 } else { 00197 minv = HASH(x); 00198 edge->v1 = x; edge->v2 = n; 00199 } 00200 00201 /* if necessary, extend the hash list */ 00202 if( minv >= hashsize ) { 00203 #ifdef HASH_PRINTF_DEBUG 00204 printf ("OOPS! new vertex too large! (%d->%d)\n",o,n); 00205 #endif 00206 int newsize = (minv + 8) & ~7; 00207 ListBase *nhash = (ListBase *)MEM_mallocN( 00208 newsize * sizeof( ListBase ), 00209 "edgehashtable" ); 00210 memcpy( nhash, hash, sizeof( ListBase ) * hashsize ); 00211 while( hashsize < newsize ) { 00212 nhash[hashsize].first = nhash[hashsize].last = NULL; 00213 ++hashsize; 00214 } 00215 if( hash ) 00216 MEM_freeN( hash ); 00217 hash = nhash; 00218 } 00219 00220 /* add the entry to tail of the right hash list */ 00221 BLI_addtail( &hash[minv], edge ); 00222 } else { 00223 #ifdef HASH_PRINTF_DEBUG 00224 printf ("OOPS! hash not large enough for (%d %d)\n",minv,hashsize); 00225 #endif 00226 } 00227 } 00228 #endif 00229 00235 BOP_Index BOP_Mesh::addFace(BOP_Face *face) 00236 { 00237 if (face->size()==3) 00238 return addFace((BOP_Face3 *)face); 00239 else 00240 return addFace((BOP_Face4 *)face); 00241 } 00242 00248 BOP_Index BOP_Mesh::addFace(BOP_Face3 *face) 00249 { 00250 BOP_Index indexface = m_faces.size(); 00251 00252 BOP_Index index1 = face->getVertex(0); 00253 BOP_Index index2 = face->getVertex(1); 00254 BOP_Index index3 = face->getVertex(2); 00255 00256 m_faces.push_back((BOP_Face *)face); 00257 00258 BOP_Index edge; 00259 00260 if (!getIndexEdge(index1,index2,edge)) { 00261 edge = addEdge(index1,index2); 00262 getVertex(index1)->addEdge(edge); 00263 getVertex(index2)->addEdge(edge); 00264 } 00265 00266 getEdge(edge)->addFace(indexface); 00267 00268 if (!getIndexEdge(index2,index3,edge)) { 00269 edge = addEdge(index2,index3); 00270 getVertex(index2)->addEdge(edge); 00271 getVertex(index3)->addEdge(edge); 00272 } 00273 00274 getEdge(edge)->addFace(indexface); 00275 00276 if (!getIndexEdge(index3,index1,edge)) { 00277 edge = addEdge(index3,index1); 00278 getVertex(index3)->addEdge(edge); 00279 getVertex(index1)->addEdge(edge); 00280 } 00281 00282 getEdge(edge)->addFace(indexface); 00283 00284 if ((index1 == index2) || (index1 == index3) || (index2 == index3)) 00285 face->setTAG(BROKEN); 00286 00287 return indexface; 00288 } 00289 00295 BOP_Index BOP_Mesh::addFace(BOP_Face4 *face) 00296 { 00297 m_faces.push_back((BOP_Face *)face); 00298 BOP_Index indexface = m_faces.size()-1; 00299 00300 BOP_Index index1 = face->getVertex(0); 00301 BOP_Index index2 = face->getVertex(1); 00302 BOP_Index index3 = face->getVertex(2); 00303 BOP_Index index4 = face->getVertex(3); 00304 00305 BOP_Index edge; 00306 00307 if (!getIndexEdge(index1,index2,edge)) { 00308 edge = addEdge(index1,index2); 00309 getVertex(index1)->addEdge(edge); 00310 getVertex(index2)->addEdge(edge); 00311 } 00312 00313 getEdge(edge)->addFace(indexface); 00314 00315 if (!getIndexEdge(index2,index3,edge)) { 00316 edge = addEdge(index2,index3); 00317 getVertex(index2)->addEdge(edge); 00318 getVertex(index3)->addEdge(edge); 00319 } 00320 00321 getEdge(edge)->addFace(indexface); 00322 00323 if (!getIndexEdge(index3,index4,edge)) { 00324 edge = addEdge(index3,index4); 00325 getVertex(index3)->addEdge(edge); 00326 getVertex(index4)->addEdge(edge); 00327 } 00328 00329 getEdge(edge)->addFace(indexface); 00330 00331 if (!getIndexEdge(index4,index1,edge)) { 00332 edge = addEdge(index4,index1); 00333 getVertex(index4)->addEdge(edge); 00334 getVertex(index1)->addEdge(edge); 00335 } 00336 00337 getEdge(edge)->addFace(indexface); 00338 00339 if ((index1 == index2) || (index1 == index3) || (index1 == index4) || 00340 (index2 == index3) || (index2 == index4) || (index3 == index4)) 00341 face->setTAG(BROKEN); 00342 00343 return m_faces.size()-1; 00344 } 00345 00352 bool BOP_Mesh::containsFace(BOP_Faces *faces, BOP_Face *face) 00353 { 00354 const BOP_IT_Faces facesEnd = faces->end(); 00355 for(BOP_IT_Faces it = faces->begin();it!=facesEnd;it++) { 00356 if (face == *it) 00357 return true; 00358 } 00359 00360 return false; 00361 } 00368 BOP_Edge* BOP_Mesh::getEdge(BOP_Indexs edges, BOP_Index v) 00369 { 00370 const BOP_IT_Indexs edgesEnd = edges.end(); 00371 for(BOP_IT_Indexs it=edges.begin();it!=edgesEnd;it++){ 00372 BOP_Edge *edge = m_edges[*it]; 00373 if ((edge->getVertex1() == v) || (edge->getVertex2() == v)) 00374 return edge; 00375 } 00376 return NULL; 00377 } 00378 00385 BOP_Edge* BOP_Mesh::getEdge(BOP_Index v1, BOP_Index v2) 00386 { 00387 #ifdef HASH 00388 int minv; 00389 EdgeEntry *edge; 00390 00391 /* figure out where and what to search for */ 00392 if( v1 < v2 ) { 00393 minv = HASH(v1); 00394 } else { 00395 minv = HASH(v2); 00396 BOP_Index tmp = v1; 00397 v1 = v2; 00398 v2 = tmp; 00399 } 00400 00401 /* if hash index valid, search the list and return match if found */ 00402 if( minv < hashsize ) { 00403 for(edge = (EdgeEntry *)hash[minv].first; 00404 edge; edge = edge->next ) { 00405 if(edge->v1 == v1 && edge->v2 == v2) 00406 return m_edges[edge->index]; 00407 } 00408 } 00409 #else 00410 const BOP_IT_Edges edgesEnd = m_edges.end(); 00411 for(BOP_IT_Edges edge=m_edges.begin();edge!=edgesEnd;edge++) { 00412 if (((*edge)->getVertex1() == v1 && (*edge)->getVertex2() == v2) || 00413 ((*edge)->getVertex1() == v2 && (*edge)->getVertex2() == v1)) 00414 return *edge; 00415 } 00416 #endif 00417 return NULL; 00418 } 00419 00427 bool BOP_Mesh::getIndexEdge(BOP_Index v1, BOP_Index v2, BOP_Index &e) 00428 { 00429 #ifdef HASH 00430 int minv; 00431 EdgeEntry *edge; 00432 00433 /* figure out what and where to look */ 00434 if( v1 < v2 ) { 00435 minv = HASH(v1); 00436 } else { 00437 minv = HASH(v2); 00438 BOP_Index tmp = v1; 00439 v1 = v2; 00440 v2 = tmp; 00441 } 00442 00443 /* if hash index is valid, look for a match */ 00444 if( minv < hashsize ) { 00445 for(edge = (EdgeEntry *)hash[minv].first; 00446 edge; edge = edge->next ) { 00447 if(edge->v1 == v1 && edge->v2 == v2) 00448 break; 00449 } 00450 00451 /* edge != NULL means match */ 00452 if(edge) { 00453 #ifdef HASH_PRINTF_DEBUG 00454 printf ("found edge (%d %d)\n",v1,v2); 00455 #endif 00456 e = edge->index; 00457 #ifdef BOP_NEW_MERGE 00458 if( m_edges[e]->getUsed() == false ) { 00459 m_edges[e]->setUsed(true); 00460 m_vertexs[v1]->addEdge(e); 00461 m_vertexs[v2]->addEdge(e); 00462 } 00463 #endif 00464 return true; 00465 } 00466 #ifdef HASH_PRINTF_DEBUG 00467 else 00468 printf ("didn't find edge (%d %d)\n",v1,v2); 00469 #endif 00470 } 00471 #else 00472 BOP_Index pos=0; 00473 const BOP_IT_Edges edgesEnd = m_edges.end(); 00474 for(BOP_IT_Edges edge=m_edges.begin();edge!=edgesEnd;edge++,pos++) { 00475 if (((*edge)->getVertex1() == v1 && (*edge)->getVertex2() == v2) || 00476 ((*edge)->getVertex1() == v2 && (*edge)->getVertex2() == v1)){ 00477 e = pos; 00478 return true; 00479 } 00480 } 00481 #endif 00482 return false; 00483 } 00484 00491 BOP_Edge* BOP_Mesh::getEdge(BOP_Face *face, unsigned int edge) 00492 { 00493 if (face->size()==3) 00494 return getEdge((BOP_Face3 *)face,edge); 00495 else 00496 return getEdge((BOP_Face4 *)face,edge); 00497 } 00498 00505 BOP_Edge* BOP_Mesh::getEdge(BOP_Face3 *face, unsigned int edge) 00506 { 00507 switch(edge){ 00508 case 1: 00509 return getEdge(m_vertexs[face->getVertex(0)]->getEdges(),face->getVertex(1)); 00510 case 2: 00511 return getEdge(m_vertexs[face->getVertex(1)]->getEdges(),face->getVertex(2)); 00512 case 3: 00513 return getEdge(m_vertexs[face->getVertex(2)]->getEdges(),face->getVertex(0)); 00514 }; 00515 00516 return NULL; 00517 } 00518 00525 BOP_Edge * BOP_Mesh::getEdge(BOP_Face4 *face, unsigned int edge) 00526 { 00527 switch(edge){ 00528 case 1: 00529 return getEdge(m_vertexs[face->getVertex(0)]->getEdges(),face->getVertex(1)); 00530 case 2: 00531 return getEdge(m_vertexs[face->getVertex(1)]->getEdges(),face->getVertex(2)); 00532 case 3: 00533 return getEdge(m_vertexs[face->getVertex(2)]->getEdges(),face->getVertex(3)); 00534 case 4: 00535 return getEdge(m_vertexs[face->getVertex(3)]->getEdges(),face->getVertex(0)); 00536 }; 00537 00538 return NULL; 00539 } 00540 00548 BOP_Face* BOP_Mesh::getFace(BOP_Index v1, BOP_Index v2, BOP_Index v3) 00549 { 00550 const BOP_IT_Faces facesEnd = m_faces.end(); 00551 for(BOP_IT_Faces face=m_faces.begin();face!=facesEnd;face++) { 00552 if ((*face)->containsVertex(v1) && (*face)->containsVertex(v2) && 00553 (*face)->containsVertex(v3)) 00554 return (*face); 00555 } 00556 return NULL; 00557 } 00558 00567 bool BOP_Mesh::getIndexFace(BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index &f) 00568 { 00569 BOP_Index pos=0; 00570 const BOP_IT_Faces facesEnd = m_faces.end(); 00571 for(BOP_IT_Faces face=m_faces.begin();face!=facesEnd;face++,pos++) { 00572 if ((*face)->containsVertex(v1) && (*face)->containsVertex(v2) && 00573 (*face)->containsVertex(v3)){ 00574 f = pos; 00575 return true; 00576 } 00577 } 00578 return false; 00579 } 00580 00585 BOP_Vertexs &BOP_Mesh::getVertexs() 00586 { 00587 return m_vertexs; 00588 } 00589 00594 BOP_Edges &BOP_Mesh::getEdges() 00595 { 00596 return m_edges; 00597 } 00598 00603 BOP_Faces &BOP_Mesh::getFaces() 00604 { 00605 return m_faces; 00606 } 00607 00613 BOP_Vertex* BOP_Mesh::getVertex(BOP_Index i) 00614 { 00615 return m_vertexs[i]; 00616 } 00617 00623 BOP_Edge* BOP_Mesh::getEdge(BOP_Index i) 00624 { 00625 return m_edges[i]; 00626 } 00627 00633 BOP_Face* BOP_Mesh::getFace(BOP_Index i) 00634 { 00635 return m_faces[i]; 00636 } 00637 00642 unsigned int BOP_Mesh::getNumVertexs() 00643 { 00644 return m_vertexs.size(); 00645 } 00646 00651 unsigned int BOP_Mesh::getNumEdges() 00652 { 00653 return m_edges.size(); 00654 } 00655 00660 unsigned int BOP_Mesh::getNumFaces() 00661 { 00662 return m_faces.size(); 00663 } 00664 00669 unsigned int BOP_Mesh::getNumVertexs(BOP_TAG tag) 00670 { 00671 unsigned int count = 0; 00672 const BOP_IT_Vertexs vertexsEnd = m_vertexs.end(); 00673 for(BOP_IT_Vertexs vertex=m_vertexs.begin();vertex!=vertexsEnd;vertex++) { 00674 if ((*vertex)->getTAG() == tag) count++; 00675 } 00676 return count; 00677 } 00682 unsigned int BOP_Mesh::getNumFaces(BOP_TAG tag) 00683 { 00684 unsigned int count = 0; 00685 const BOP_IT_Faces facesEnd = m_faces.end(); 00686 for(BOP_IT_Faces face=m_faces.begin();face!=facesEnd;face++) { 00687 if ((*face)->getTAG() == tag) count++; 00688 } 00689 return count; 00690 } 00691 00698 static void removeBrokenFaces( BOP_Edge *edge, BOP_Mesh *mesh ) 00699 { 00700 BOP_Faces m_faces = mesh->getFaces(); 00701 00702 BOP_Indexs edgeFaces = edge->getFaces(); 00703 const BOP_IT_Indexs edgeFacesEnd = edgeFaces.end(); 00704 for(BOP_IT_Indexs idxFace=edgeFaces.begin();idxFace!=edgeFacesEnd; 00705 idxFace++) 00706 m_faces[*idxFace]->setTAG(BROKEN); 00707 } 00708 00714 BOP_Index BOP_Mesh::replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex) 00715 { 00716 BOP_IT_Indexs oldEdgeIndex; 00717 if (oldIndex==newIndex) return newIndex; 00718 00719 // Update faces, edges and vertices 00720 BOP_Vertex *oldVertex = m_vertexs[oldIndex]; 00721 BOP_Vertex *newVertex = m_vertexs[newIndex]; 00722 BOP_Indexs oldEdges = oldVertex->getEdges(); 00723 00724 // Update faces to the newIndex 00725 BOP_IT_Indexs oldEdgesEnd = oldEdges.end(); 00726 for(oldEdgeIndex=oldEdges.begin();oldEdgeIndex!=oldEdgesEnd; 00727 oldEdgeIndex++) { 00728 BOP_Edge *edge = m_edges[*oldEdgeIndex]; 00729 if ((edge->getVertex1()==oldIndex && edge->getVertex2()==newIndex) || 00730 (edge->getVertex2()==oldIndex && edge->getVertex1()==newIndex)) { 00731 // Remove old edge ==> set edge faces to BROKEN 00732 removeBrokenFaces( edge, this ); 00733 oldVertex->removeEdge(*oldEdgeIndex); 00734 newVertex->removeEdge(*oldEdgeIndex); 00735 } 00736 else { 00737 BOP_Indexs faces = edge->getFaces(); 00738 const BOP_IT_Indexs facesEnd = faces.end(); 00739 for(BOP_IT_Indexs face=faces.begin();face!=facesEnd;face++) { 00740 if (m_faces[*face]->getTAG()!=BROKEN) 00741 m_faces[*face]->replaceVertexIndex(oldIndex,newIndex); 00742 } 00743 } 00744 } 00745 00746 oldEdgesEnd = oldEdges.end(); 00747 for(oldEdgeIndex=oldEdges.begin();oldEdgeIndex!=oldEdgesEnd; 00748 oldEdgeIndex++) { 00749 BOP_Edge * edge = m_edges[*oldEdgeIndex]; 00750 BOP_Edge * edge2; 00751 BOP_Index v1 = edge->getVertex1(); 00752 00753 v1 = (v1==oldIndex?edge->getVertex2():v1); 00754 if ((edge2 = getEdge(newIndex,v1)) == NULL) { 00755 edge->replaceVertexIndex(oldIndex,newIndex); 00756 if ( edge->getVertex1() == edge->getVertex2() ) { 00757 removeBrokenFaces( edge, this ); 00758 oldVertex->removeEdge(*oldEdgeIndex); 00759 } 00760 #ifdef HASH 00761 rehashVertex(oldIndex,newIndex,v1); 00762 #endif 00763 newVertex->addEdge(*oldEdgeIndex); 00764 } 00765 else { 00766 BOP_Indexs faces = edge->getFaces(); 00767 const BOP_IT_Indexs facesEnd = faces.end(); 00768 for(BOP_IT_Indexs f=faces.begin();f!=facesEnd;f++) { 00769 if (m_faces[*f]->getTAG()!=BROKEN) 00770 edge2->addFace(*f); 00771 } 00772 BOP_Vertex *oppositeVertex = m_vertexs[v1]; 00773 oppositeVertex->removeEdge(*oldEdgeIndex); 00774 edge->replaceVertexIndex(oldIndex,newIndex); 00775 if ( edge->getVertex1() == edge->getVertex2() ) { 00776 removeBrokenFaces( edge, this ); 00777 oldVertex->removeEdge(*oldEdgeIndex); 00778 newVertex->removeEdge(*oldEdgeIndex); 00779 } 00780 #ifdef HASH 00781 rehashVertex(oldIndex,newIndex,v1); 00782 #endif 00783 } 00784 } 00785 oldVertex->setTAG(BROKEN); 00786 00787 return newIndex; 00788 } 00789 00790 bool BOP_Mesh::isClosedMesh() 00791 { 00792 for(unsigned int i=0; i<m_edges.size(); i++) { 00793 BOP_Edge *edge = m_edges[i]; 00794 BOP_Indexs faces = edge->getFaces(); 00795 unsigned int count = 0; 00796 const BOP_IT_Indexs facesEnd = faces.end(); 00797 for(BOP_IT_Indexs it = faces.begin();it!=facesEnd;it++) { 00798 if (m_faces[*it]->getTAG()!=BROKEN) 00799 count++; 00800 } 00801 00802 if ((count%2)!=0) return false; 00803 } 00804 00805 return true; 00806 } 00807 00808 00809 #ifdef BOP_DEBUG 00810 /****************************************************************************** 00811 * DEBUG METHODS * 00812 * This functions are used to test the mesh state and debug program errors. * 00813 ******************************************************************************/ 00814 00818 void BOP_Mesh::print() 00819 { 00820 unsigned int i; 00821 cout << "--Faces--" << endl; 00822 for(i=0;i<m_faces.size();i++){ 00823 cout << "Face " << i << ": " << m_faces[i] << endl; 00824 } 00825 00826 cout << "--Vertices--" << endl; 00827 for(i=0;i<m_vertexs.size();i++){ 00828 cout << "Point " << i << ": " << m_vertexs[i]->getPoint() << endl; 00829 } 00830 } 00831 00835 void BOP_Mesh::printFormat(BOP_Faces *faces) 00836 { 00837 if (faces->size()) { 00838 for(unsigned int it=1;it<faces->size();it++) { 00839 if ((*faces)[it]->getTAG()!=BROKEN) { 00840 cout << m_vertexs[(*faces)[it]->getVertex(0)]->getPoint() << " "; 00841 cout << m_vertexs[(*faces)[it]->getVertex(1)]->getPoint() << " "; 00842 cout << m_vertexs[(*faces)[it]->getVertex(2)]->getPoint() << endl; 00843 } 00844 } 00845 } 00846 } 00847 00851 void BOP_Mesh::saveFormat(BOP_Faces *faces,char *filename) 00852 { 00853 ofstream fout(filename); 00854 00855 if (!fout.is_open()) { 00856 cerr << "BOP_Mesh::saveFormat Error: Could not create file." << endl; 00857 return; 00858 } 00859 00860 unsigned int count = 0; 00861 if (faces->size()) { 00862 for(unsigned int it=0;it<faces->size();it++) { 00863 if ((*faces)[it]->getTAG()!=BROKEN) { 00864 count++; 00865 } 00866 } 00867 } 00868 00869 fout << count << endl; 00870 if (faces->size()) { 00871 for(unsigned int it=0;it<faces->size();it++) { 00872 if ((*faces)[it]->getTAG()!=BROKEN){ 00873 fout << m_vertexs[(*faces)[it]->getVertex(0)]->getPoint() << " "; 00874 fout << m_vertexs[(*faces)[it]->getVertex(1)]->getPoint() << " "; 00875 fout << m_vertexs[(*faces)[it]->getVertex(2)]->getPoint() << endl; 00876 } 00877 } 00878 } 00879 00880 fout.close(); 00881 } 00882 00886 void BOP_Mesh::printFormat() 00887 { 00888 cout << "--Vertices--" << endl; 00889 if (m_vertexs.size()>0) { 00890 cout << "{" << m_vertexs[0]->getPoint().x() << ","; 00891 cout << m_vertexs[0]->getPoint().y() << ","; 00892 cout << m_vertexs[0]->getPoint().z() << "}"; 00893 for(unsigned int i=1;i<m_vertexs.size();i++) { 00894 cout << ",{" << m_vertexs[i]->getPoint().x() << ","; 00895 cout << m_vertexs[i]->getPoint().y() << ","; 00896 cout << m_vertexs[i]->getPoint().z() << "}"; 00897 } 00898 cout << endl; 00899 } 00900 00901 cout << "--Faces--" << endl; 00902 if (m_faces.size()>0) { 00903 cout << "{" << m_faces[0]->getVertex(0) << ","; 00904 cout << m_faces[0]->getVertex(1) << "," << m_faces[0]->getVertex(2) << "}"; 00905 for(unsigned int i=1;i<m_faces.size();i++) { 00906 cout << ",{" << m_faces[i]->getVertex(0) << ","; 00907 cout << m_faces[i]->getVertex(1) << "," << m_faces[i]->getVertex(2) << "}"; 00908 } 00909 cout << endl; 00910 } 00911 } 00912 00916 void BOP_Mesh::printFace(BOP_Face *face, int col) 00917 { 00918 cout << "--Face" << endl; 00919 cout << m_vertexs[face->getVertex(0)]->getPoint(); 00920 cout << " " << m_vertexs[face->getVertex(1)]->getPoint(); 00921 cout << " " << m_vertexs[face->getVertex(2)]->getPoint(); 00922 if (face->size()==4) 00923 cout << " " << m_vertexs[face->getVertex(3)]->getPoint(); 00924 cout << " " << col << endl; 00925 } 00926 00930 void BOP_Mesh::testMesh() 00931 { 00932 00933 BOP_Face* cares[10]; 00934 unsigned int nedges=0,i; 00935 for(i=0;i<m_edges.size();i++) { 00936 BOP_Edge *edge = m_edges[i]; 00937 BOP_Indexs faces = edge->getFaces(); 00938 unsigned int count = 0; 00939 const BOP_IT_Indexs facesEnd = faces.end(); 00940 for(BOP_IT_Indexs it = faces.begin();it!=facesEnd;it++) { 00941 if (m_faces[*it]->getTAG()!=BROKEN) { 00942 cares[count] = m_faces[*it]; 00943 count++; 00944 00945 } 00946 } 00947 00948 if ((count%2)!=0) nedges++; 00949 } 00950 if (nedges) 00951 cout << nedges << " wrong edges." << endl; 00952 else 00953 cout << "well edges." << endl; 00954 00955 unsigned int duplFaces = 0; 00956 unsigned int wrongFaces = 0; 00957 for(i=0;i<m_faces.size();i++){ 00958 BOP_Face *faceI = m_faces[i]; 00959 if (faceI->getTAG()==BROKEN) 00960 continue; 00961 00962 if (testFace(faceI)){ 00963 wrongFaces++; 00964 cout << "Wrong Face: " << faceI << endl; 00965 } 00966 00967 for(unsigned int j=i+1;j<m_faces.size();j++){ 00968 BOP_Face *faceJ = m_faces[j]; 00969 00970 if (faceJ->getTAG()==BROKEN) 00971 continue; 00972 00973 if (testFaces(faceI,faceJ)){ 00974 duplFaces++; 00975 cout << "Duplicate FaceI: " << faceI << endl; 00976 cout << "Duplicate FaceJ: " << faceJ << endl; 00977 } 00978 } 00979 } 00980 00981 cout << duplFaces << " duplicate faces." << endl; 00982 cout << wrongFaces << " wrong faces." << endl; 00983 } 00984 00988 bool BOP_Mesh::testFace(BOP_Face *face){ 00989 00990 for(unsigned int i=0;i<face->size();i++){ 00991 for(unsigned int j=i+1;j<face->size();j++){ 00992 if (face->getVertex(i)==face->getVertex(j)) 00993 return true; 00994 } 00995 } 00996 00997 return false; 00998 } 00999 01003 bool BOP_Mesh::testFaces(BOP_Face *faceI, BOP_Face *faceJ){ 01004 01005 if (faceI->size()<faceJ->size()){ 01006 for(unsigned int i=0;i<faceI->size();i++){ 01007 if (!faceJ->containsVertex(faceI->getVertex(i))) 01008 return false; 01009 } 01010 //faceI->setTAG(BROKEN); 01011 } 01012 else{ 01013 for(unsigned int i=0;i<faceJ->size();i++){ 01014 if (!faceI->containsVertex(faceJ->getVertex(i))) 01015 return false; 01016 } 01017 //faceJ->setTAG(BROKEN); 01018 } 01019 01020 return true; 01021 } 01022 01026 void BOP_Mesh::testPlane(BOP_Face *face) 01027 { 01028 MT_Plane3 plane1(m_vertexs[face->getVertex(0)]->getPoint(), 01029 m_vertexs[face->getVertex(1)]->getPoint(), 01030 m_vertexs[face->getVertex(2)]->getPoint()); 01031 01032 if (BOP_orientation(plane1,face->getPlane()) < 0) { 01033 cout << "Test Plane " << face << " v1: "; 01034 cout << m_vertexs[face->getVertex(0)]->getPoint() << " v2: "; 01035 cout << m_vertexs[face->getVertex(1)]->getPoint() << " v3: "; 01036 cout << m_vertexs[face->getVertex(2)]->getPoint() << " plane: "; 01037 cout << face->getPlane() << endl; 01038 cout << "Incorrect vertices order!!! plane1: " << plane1 << " ("; 01039 cout << BOP_orientation(plane1,face->getPlane()) << ") " << " invert "; 01040 cout << MT_Plane3(m_vertexs[face->getVertex(2)]->getPoint(), 01041 m_vertexs[face->getVertex(1)]->getPoint(), 01042 m_vertexs[face->getVertex(0)]->getPoint()) << endl; 01043 if (BOP_collinear(m_vertexs[face->getVertex(0)]->getPoint(), 01044 m_vertexs[face->getVertex(1)]->getPoint(), 01045 m_vertexs[face->getVertex(2)]->getPoint())) { 01046 cout << " COLLINEAR!!!" << endl; 01047 } 01048 else { 01049 cout << endl; 01050 } 01051 } 01052 } 01053 01057 bool BOP_Mesh::testEdges(BOP_Faces *facesObj) 01058 { 01059 for(unsigned int i=0;i<m_edges.size();i++) { 01060 BOP_Edge *edge = m_edges[i]; 01061 BOP_Indexs faces = edge->getFaces(); 01062 unsigned int count = 0; 01063 const BOP_IT_Indexs facesEnd = faces.end(); 01064 for(BOP_IT_Indexs it = faces.begin();it!=facesEnd;it++) { 01065 if ((m_faces[*it]->getTAG()!=BROKEN) && containsFace(facesObj,m_faces[*it])) 01066 count++; 01067 } 01068 if ((count%2)!=0) { 01069 return false; 01070 } 01071 } 01072 01073 return true; 01074 } 01075 01079 void BOP_Mesh::updatePlanes() 01080 { 01081 const BOP_IT_Faces facesEnd = m_faces.end(); 01082 for(BOP_IT_Faces it = m_faces.begin();it!=facesEnd;it++) { 01083 BOP_Face *face = *it; 01084 MT_Plane3 plane(m_vertexs[face->getVertex(0)]->getPoint(), 01085 m_vertexs[face->getVertex(1)]->getPoint(), 01086 m_vertexs[face->getVertex(2)]->getPoint()); 01087 face->setPlane(plane); 01088 } 01089 } 01090 01091 #endif