intern/boolop/intern/BOP_Mesh.cpp

   1 /**
   2  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version. The Blender
   8  * Foundation also sells licenses for use in proprietary software under
   9  * the Blender License.  See http://www.blender.org/BL/ for information
  10  * about this.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software Foundation,
  19  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  20  *
  21  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  22  * All rights reserved.
  23  *
  24  * The Original Code is: all of this file.
  25  *
  26  * Contributor(s): none yet.
  27  *
  28  * ***** END GPL/BL DUAL LICENSE BLOCK *****
  29  */
  30
  31 #include "BOP_Mesh.h"
  32 #include "BOP_MathUtils.h"
  33 #include <iostream>
  34 #include <fstream>
  35
  36
  37 /**
  38  * Destroys a mesh.
  39  */
  40 BOP_Mesh::~BOP_Mesh()
  41 {
  42         const BOP_IT_Vertexs vertexsEnd = m_vertexs.end();
  43         for(BOP_IT_Vertexs it=m_vertexs.begin();it!=vertexsEnd;it++){
  44                 delete *it;
  45         }
  46         m_vertexs.clear();
  47
  48         const BOP_IT_Edges edgesEnd = m_edges.end();
  49         for(BOP_IT_Edges it=m_edges.begin();it!=edgesEnd;it++){
  50                 delete *it;
  51         }
  52         m_edges.clear();
  53
  54         const BOP_IT_Faces facesEnd = m_faces.end();
  55         for(BOP_IT_Faces it=m_faces.begin();it!=facesEnd;it++){
  56                 delete *it;
  57         }
  58         m_faces.clear();
  59 }
  60
  61 /**
  62  * Adds a new vertex.
  63  * @param p vertex point
  64  * @return mesh vertex index
  65  */
  66 BOP_Index BOP_Mesh::addVertex(MT_Point3 p)
  67 {
  68         m_vertexs.push_back(new BOP_Vertex(p));
  69         return m_vertexs.size()-1;
  70 }
  71
  72 /**
  73  * Adds a new edge.
  74  * @param v1 mesh vertex index
  75  * @param v2 mesh vertex index
  76  * @return mesh edge index
  77  */
  78 BOP_Index BOP_Mesh::addEdge(BOP_Index v1, BOP_Index v2)
  79 {
  80         m_edges.push_back(new BOP_Edge(v1,v2));
  81         return (m_edges.size()-1);
  82 }
  83
  84 /**
  85  * Adds a new face.
  86  * @param face mesh face
  87  * @return mesh face index
  88  */
  89 BOP_Index BOP_Mesh::addFace(BOP_Face *face)
  90 {
  91         if (face->size()==3)
  92                 return addFace((BOP_Face3 *)face);
  93         else
  94                 return addFace((BOP_Face4 *)face);
  95 }
  96
  97 /**
  98  * Adds a new triangle.
  99  * @param face mesh triangle
 100  * @return mesh face index
 101  */
 102 BOP_Index BOP_Mesh::addFace(BOP_Face3 *face)
 103 {
 104         BOP_Index indexface = m_faces.size();
 105
 106         BOP_Index index1 = face->getVertex(0);
 107         BOP_Index index2 = face->getVertex(1);
 108         BOP_Index index3 = face->getVertex(2);
 109
 110         m_faces.push_back((BOP_Face *)face);
 111
 112         BOP_Index edge;
 113
 114         if (!getIndexEdge(index1,index2,edge)) {
 115                 edge = addEdge(index1,index2);
 116                 getVertex(index1)->addEdge(edge);
 117                 getVertex(index2)->addEdge(edge);
 118         }
 119
 120         getEdge(edge)->addFace(indexface);
 121
 122         if (!getIndexEdge(index2,index3,edge)) {
 123                 edge = addEdge(index2,index3);
 124                 getVertex(index2)->addEdge(edge);
 125                 getVertex(index3)->addEdge(edge);
 126         }
 127
 128         getEdge(edge)->addFace(indexface);
 129
 130         if (!getIndexEdge(index3,index1,edge)) {
 131                 edge = addEdge(index3,index1);
 132                 getVertex(index3)->addEdge(edge);
 133                 getVertex(index1)->addEdge(edge);
 134         }
 135
 136         getEdge(edge)->addFace(indexface);
 137
 138         if ((index1 == index2) || (index1 == index3) || (index2 == index3))
 139                 face->setTAG(BROKEN);
 140
 141         return indexface;
 142 }
 143
 144 /**
 145  * Adds a new quad.
 146  * @param face mesh quad
 147  * @return mesh face index
 148  */
 149 BOP_Index BOP_Mesh::addFace(BOP_Face4 *face)
 150 {
 151         m_faces.push_back((BOP_Face *)face);
 152         BOP_Index indexface = m_faces.size()-1;
 153
 154         BOP_Index index1 = face->getVertex(0);
 155         BOP_Index index2 = face->getVertex(1);
 156         BOP_Index index3 = face->getVertex(2);
 157         BOP_Index index4 = face->getVertex(3);
 158
 159         BOP_Index edge;
 160
 161         if (!getIndexEdge(index1,index2,edge)) {
 162                 edge = addEdge(index1,index2);
 163                 getVertex(index1)->addEdge(edge);
 164                 getVertex(index2)->addEdge(edge);
 165         }
 166
 167         getEdge(edge)->addFace(indexface);
 168
 169         if (!getIndexEdge(index2,index3,edge)) {
 170                 edge = addEdge(index2,index3);
 171                 getVertex(index2)->addEdge(edge);
 172                 getVertex(index3)->addEdge(edge);
 173         }
 174
 175         getEdge(edge)->addFace(indexface);
 176
 177         if (!getIndexEdge(index3,index4,edge)) {
 178                 edge = addEdge(index3,index4);
 179                 getVertex(index3)->addEdge(edge);
 180                 getVertex(index4)->addEdge(edge);
 181         }
 182
 183         getEdge(edge)->addFace(indexface);
 184
 185         if (!getIndexEdge(index4,index1,edge)) {
 186                 edge = addEdge(index4,index1);
 187                 getVertex(index4)->addEdge(edge);
 188                 getVertex(index1)->addEdge(edge);
 189         }
 190
 191         getEdge(edge)->addFace(indexface);
 192
 193         if ((index1 == index2) || (index1 == index3) || (index1 == index4) ||
 194                 (index2 == index3) || (index2 == index4) || (index3 == index4))
 195                 face->setTAG(BROKEN);
 196
 197         return m_faces.size()-1;
 198 }
 199
 200 /**
 201  * Returns if a faces set contains the specified face.
 202  * @param faces faces set
 203  * @param face face
 204  * @return true if the set contains the specified face
 205  */
 206 bool BOP_Mesh::containsFace(BOP_Faces *faces, BOP_Face *face)
 207 {
 208   const BOP_IT_Faces facesEnd = faces->end();
 209         for(BOP_IT_Faces it = faces->begin();it!=facesEnd;it++) {
 210                 if (face == *it)
 211                         return true;
 212         }
 213
 214         return false;
 215 }
 216 /**
 217  * Returns the first edge with the specified vertex index from a list of edge indexs.
 218  * @param edges edge indexs
 219  * @param v vertex index
 220  * @return first edge with the specified vertex index, NULL otherwise
 221  */
 222 BOP_Edge* BOP_Mesh::getEdge(BOP_Indexs edges, BOP_Index v)
 223 {
 224   const BOP_IT_Indexs edgesEnd = edges.end();
 225         for(BOP_IT_Indexs it=edges.begin();it!=edgesEnd;it++){
 226                 BOP_Edge *edge = m_edges[*it];
 227                 if ((edge->getVertex1() == v) || (edge->getVertex2() == v))
 228                         return edge;
 229         }
 230         return NULL;
 231 }
 232
 233 /**
 234  * Returns the mesh edge with the specified vertex indexs.
 235  * @param v1 vertex index
 236  * @param v2 vertex index
 237  * @return mesh edge with the specified vertex indexs, NULL otherwise
 238  */
 239 BOP_Edge* BOP_Mesh::getEdge(BOP_Index v1, BOP_Index v2)
 240 {
 241         const BOP_IT_Edges edgesEnd = m_edges.end();
 242         for(BOP_IT_Edges edge=m_edges.begin();edge!=edgesEnd;edge++) {
 243                 if (((*edge)->getVertex1() == v1 && (*edge)->getVertex2() == v2) ||
 244                         ((*edge)->getVertex1() == v2 && (*edge)->getVertex2() == v1))
 245                         return *edge;
 246         }
 247         return NULL;
 248 }
 249
 250 /**
 251  * Returns the mesh edge index with the specified vertex indexs.
 252  * @param v1 vertex index
 253  * @param v2 vertex index
 254  * @param e edge index with the specified vertex indexs
 255  * @return true if there is a mesh edge with the specified vertex indexs, false otherwise
 256  */
 257 bool BOP_Mesh::getIndexEdge(BOP_Index v1, BOP_Index v2, BOP_Index &e)
 258 {
 259         BOP_Index pos=0;
 260         const BOP_IT_Edges edgesEnd = m_edges.end();
 261         for(BOP_IT_Edges edge=m_edges.begin();edge!=edgesEnd;edge++,pos++) {
 262                 if (((*edge)->getVertex1() == v1 && (*edge)->getVertex2() == v2) ||
 263                     ((*edge)->getVertex1() == v2 && (*edge)->getVertex2() == v1)){
 264                   e = pos;
 265                   return true;
 266                 }
 267         }
 268         return false;
 269 }
 270
 271 /**
 272  * Returns the mesh edge on the specified face and relative edge index.
 273  * @param face mesh face
 274  * @param edge face relative edge index
 275  * @return mesh edge on the specified face and relative index, NULL otherwise
 276  */
 277 BOP_Edge* BOP_Mesh::getEdge(BOP_Face *face, unsigned int edge)
 278 {
 279         if (face->size()==3)
 280                 return getEdge((BOP_Face3 *)face,edge);
 281         else
 282                 return getEdge((BOP_Face4 *)face,edge);
 283 }
 284
 285 /**
 286  * Returns the mesh edge on the specified triangle and relative edge index.
 287  * @param face mesh triangle
 288  * @param edge face relative edge index
 289  * @return mesh edge on the specified triangle and relative index, NULL otherwise
 290  */
 291 BOP_Edge* BOP_Mesh::getEdge(BOP_Face3 *face, unsigned int edge)
 292 {
 293         switch(edge){
 294         case 1:
 295                 return getEdge(m_vertexs[face->getVertex(0)]->getEdges(),face->getVertex(1));
 296         case 2:
 297                 return getEdge(m_vertexs[face->getVertex(1)]->getEdges(),face->getVertex(2));
 298         case 3:
 299                 return getEdge(m_vertexs[face->getVertex(2)]->getEdges(),face->getVertex(0));
 300         };
 301
 302         return NULL;
 303 }
 304
 305 /**
 306  * Returns the mesh edge on the specified quad and relative edge index.
 307  * @param face mesh quad
 308  * @param edge face relative edge index
 309  * @return mesh edge on the specified quad and relative index, NULL otherwise
 310  */
 311 BOP_Edge * BOP_Mesh::getEdge(BOP_Face4 *face, unsigned int edge)
 312 {
 313         switch(edge){
 314         case 1:
 315                 return getEdge(m_vertexs[face->getVertex(0)]->getEdges(),face->getVertex(1));
 316         case 2:
 317                 return getEdge(m_vertexs[face->getVertex(1)]->getEdges(),face->getVertex(2));
 318         case 3:
 319                 return getEdge(m_vertexs[face->getVertex(2)]->getEdges(),face->getVertex(3));
 320         case 4:
 321                 return getEdge(m_vertexs[face->getVertex(3)]->getEdges(),face->getVertex(0));
 322         };
 323
 324         return NULL;
 325 }
 326
 327 /**
 328  * Returns the mesh face with the specified vertex indexs.
 329  * @param v1 vertex index
 330  * @param v2 vertex index
 331  * @param v3 vertex index
 332  * @return mesh edge with the specified vertex indexs, NULL otherwise
 333  */
 334 BOP_Face* BOP_Mesh::getFace(BOP_Index v1, BOP_Index v2, BOP_Index v3)
 335 {
 336         const BOP_IT_Faces facesEnd = m_faces.end();
 337         for(BOP_IT_Faces face=m_faces.begin();face!=facesEnd;face++) {
 338                 if ((*face)->containsVertex(v1) && (*face)->containsVertex(v2) &&
 339                         (*face)->containsVertex(v3))
 340                         return (*face);
 341         }
 342         return NULL;
 343 }
 344
 345 /**
 346  * Returns the mesh face index with the specified vertex indexs.
 347  * @param v1 vertex index
 348  * @param v2 vertex index
 349  * @param v3 vertex index
 350  * @param f face index with the specified vertex indexs
 351  * @return true if there is a mesh face with the specified vertex indexs, false otherwise
 352  */
 353 bool BOP_Mesh::getIndexFace(BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index &f)
 354 {
 355         BOP_Index pos=0;
 356         const BOP_IT_Faces facesEnd = m_faces.end();
 357         for(BOP_IT_Faces face=m_faces.begin();face!=facesEnd;face++,pos++) {
 358                 if ((*face)->containsVertex(v1) && (*face)->containsVertex(v2) &&
 359                     (*face)->containsVertex(v3)){
 360                   f = pos;
 361                   return true;
 362                 }
 363         }
 364         return false;
 365 }
 366
 367 /**
 368  * Returns the vertices set of this mesh.
 369  * @return vertices set
 370  */
 371 BOP_Vertexs &BOP_Mesh::getVertexs()
 372 {
 373         return m_vertexs;
 374 }
 375
 376 /**
 377  * Returns the edges set of this mesh.
 378  * @return edges set
 379  */
 380 BOP_Edges &BOP_Mesh::getEdges()
 381 {
 382         return m_edges;
 383 }
 384
 385 /**
 386  * Returns the faces set of this mesh.
 387  * @return faces set
 388  */
 389 BOP_Faces &BOP_Mesh::getFaces()
 390 {
 391         return m_faces;
 392 }
 393
 394 /**
 395  * Returns the mesh vertex with the specified index.
 396  * @param i vertex index
 397  * @return vertex with the specified index
 398  */
 399 BOP_Vertex* BOP_Mesh::getVertex(BOP_Index i)
 400 {
 401         return m_vertexs[i];
 402 }
 403
 404 /**
 405  * Returns the mesh edge with the specified index.
 406  * @param i edge index
 407  * @return edge with the specified index
 408  */
 409 BOP_Edge* BOP_Mesh::getEdge(BOP_Index i)
 410 {
 411         return m_edges[i];
 412 }
 413
 414 /**
 415  * Returns the mesh face with the specified index.
 416  * @param i face index
 417  * @return face with the specified index
 418  */
 419 BOP_Face* BOP_Mesh::getFace(BOP_Index i)
 420 {
 421         return m_faces[i];
 422 }
 423
 424 /**
 425  * Returns the number of vertices of this mesh.
 426  * @return number of vertices
 427  */
 428 unsigned int BOP_Mesh::getNumVertexs()
 429 {
 430         return m_vertexs.size();
 431 }
 432
 433 /**
 434  * Returns the number of edges of this mesh.
 435  * @return number of edges
 436  */
 437 unsigned int BOP_Mesh::getNumEdges()
 438 {
 439         return m_edges.size();
 440 }
 441
 442 /**
 443  * Returns the number of faces of this mesh.
 444  * @return number of faces
 445  */
 446 unsigned int BOP_Mesh::getNumFaces()
 447 {
 448         return m_faces.size();
 449 }
 450
 451 /**
 452  * Returns the number of vertices of this mesh with the specified tag.
 453  * @return number of vertices with the specified tag
 454  */
 455 unsigned int BOP_Mesh::getNumVertexs(BOP_TAG tag)
 456 {
 457         unsigned int count = 0;
 458         const BOP_IT_Vertexs vertexsEnd = m_vertexs.end();
 459         for(BOP_IT_Vertexs vertex=m_vertexs.begin();vertex!=vertexsEnd;vertex++) {
 460                 if ((*vertex)->getTAG() == tag) count++;
 461         }
 462         return count;
 463 }
 464 /**
 465  * Returns the number of faces of this mesh with the specified tag.
 466  * @return number of faces with the specified tag
 467  */
 468 unsigned int BOP_Mesh::getNumFaces(BOP_TAG tag)
 469 {
 470         unsigned int count = 0;
 471         const BOP_IT_Faces facesEnd = m_faces.end();
 472         for(BOP_IT_Faces face=m_faces.begin();face!=facesEnd;face++) {
 473                 if ((*face)->getTAG() == tag) count++;
 474         }
 475         return count;
 476 }
 477
 478 /**
 479  * Replaces a vertex index.
 480  * @param oldIndex old vertex index
 481  * @param newIndex new vertex index
 482  */
 483 BOP_Index BOP_Mesh::replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex)
 484 {
 485         if (oldIndex==newIndex) return newIndex;
 486
 487         // Update faces, edges and vertices
 488         BOP_Vertex *oldVertex = m_vertexs[oldIndex];
 489         BOP_Vertex *newVertex = m_vertexs[newIndex];
 490         BOP_Indexs oldEdges = oldVertex->getEdges();
 491
 492         BOP_Index edgeIdx=0;
 493         bool found = false;
 494
 495         // Update faces to the newIndex
 496         BOP_IT_Indexs oldEdgesEnd = oldEdges.end();
 497         for(BOP_IT_Indexs oldEdgeIndex=oldEdges.begin();oldEdgeIndex!=oldEdgesEnd;
 498                    oldEdgeIndex++) {
 499                 BOP_Edge *edge = m_edges[*oldEdgeIndex];
 500                 if ((edge->getVertex1()==oldIndex && edge->getVertex2()==newIndex) ||
 501                         (edge->getVertex2()==oldIndex && edge->getVertex1()==newIndex)) {
 502                         // Remove old edge  ==> set edge faces to BROKEN
 503                         BOP_Indexs edgeFaces = edge->getFaces();
 504                         const BOP_IT_Indexs edgeFacesEnd = edgeFaces.end();
 505                         for(BOP_IT_Indexs idxFace=edgeFaces.begin();idxFace!=edgeFacesEnd;
 506                                    idxFace++) {
 507                                 m_faces[*idxFace]->setTAG(BROKEN);
 508                         }
 509                         edgeIdx = *oldEdgeIndex;
 510                         found = true;
 511                 }
 512                 else {
 513                         BOP_Indexs faces = edge->getFaces();
 514                         const BOP_IT_Indexs facesEnd = faces.end();
 515                         for(BOP_IT_Indexs face=faces.begin();face!=facesEnd;face++) {
 516                                 if (m_faces[*face]->getTAG()!=BROKEN)
 517                                         m_faces[*face]->replaceVertexIndex(oldIndex,newIndex);
 518                         }
 519                 }
 520         }
 521         if (found) {
 522                 oldVertex->removeEdge(edgeIdx);
 523                 newVertex->removeEdge(edgeIdx);
 524         }
 525
 526         oldEdgesEnd = oldEdges.end();
 527         for(BOP_IT_Indexs oldEdgeIndex=oldEdges.begin();oldEdgeIndex!=oldEdgesEnd;
 528                    oldEdgeIndex++) {
 529                 BOP_Edge * edge = m_edges[*oldEdgeIndex];
 530                 BOP_Edge * edge2;
 531                 BOP_Index v1 = edge->getVertex1();
 532
 533                 v1 = (v1==oldIndex?edge->getVertex2():v1);
 534                 if ((edge2 = getEdge(newIndex,v1)) == NULL) {
 535                         edge->replaceVertexIndex(oldIndex,newIndex);
 536                         newVertex->addEdge(*oldEdgeIndex);
 537                 }
 538                 else {
 539                         BOP_Indexs faces = edge->getFaces();
 540                         const BOP_IT_Indexs facesEnd = faces.end();
 541                         for(BOP_IT_Indexs f=faces.begin();f!=facesEnd;f++) {
 542                                 if (m_faces[*f]->getTAG()!=BROKEN)
 543                                 edge2->addFace(*f);
 544                         }
 545                         BOP_Vertex *oppositeVertex = m_vertexs[v1];
 546                         oppositeVertex->removeEdge(*oldEdgeIndex);
 547                         edge->replaceVertexIndex(oldIndex,newIndex);
 548                 }
 549         }
 550         oldVertex->setTAG(BROKEN);
 551
 552         return newIndex;
 553 }
 554
 555
 556
 557 /** ***************************************************************************
 558  * DEBUG METHODS                                                              *
 559  * This functions are used to test the mesh state and debug program errors.   *
 560  ******************************************************************************/
 561
 562 /**
 563  * print
 564  */
 565 void BOP_Mesh::print()
 566 {
 567         cout << "--Faces--" << endl;
 568         for(unsigned int i=0;i<m_faces.size();i++){
 569                 cout << "Face " << i << ": " << m_faces[i] << endl;
 570         }
 571
 572         cout << "--Vertices--" << endl;
 573         for(unsigned int i=0;i<m_vertexs.size();i++){
 574                 cout << "Point " << i << ": " << m_vertexs[i]->getPoint() << endl;
 575         }
 576 }
 577
 578 /**
 579  * printFormat
 580  */
 581 void BOP_Mesh::printFormat(BOP_Faces *faces)
 582 {
 583         if (faces->size()) {
 584                 for(unsigned int it=1;it<faces->size();it++) {
 585                         if ((*faces)[it]->getTAG()!=BROKEN) {
 586                                 cout << m_vertexs[(*faces)[it]->getVertex(0)]->getPoint() << " ";
 587                                 cout << m_vertexs[(*faces)[it]->getVertex(1)]->getPoint() << " ";
 588                                 cout << m_vertexs[(*faces)[it]->getVertex(2)]->getPoint() << endl;
 589                         }
 590                 }
 591         }
 592 }
 593
 594 /**
 595  * saveFormat
 596  */
 597 void BOP_Mesh::saveFormat(BOP_Faces *faces,char *filename)
 598 {
 599         ofstream fout(filename);
 600
 601         if (!fout.is_open()) {
 602                 cerr << "BOP_Mesh::saveFormat Error: Could not create file." << endl;
 603                 return;
 604         }
 605
 606         unsigned int count = 0;
 607         if (faces->size()) {
 608                 for(unsigned int it=0;it<faces->size();it++) {
 609                         if ((*faces)[it]->getTAG()!=BROKEN) {
 610                                 count++;
 611                         }
 612                 }
 613         }
 614
 615         fout << count << endl;
 616         if (faces->size()) {
 617                 for(unsigned int it=0;it<faces->size();it++) {
 618                         if ((*faces)[it]->getTAG()!=BROKEN){
 619                                 fout << m_vertexs[(*faces)[it]->getVertex(0)]->getPoint() << " ";
 620                                 fout << m_vertexs[(*faces)[it]->getVertex(1)]->getPoint() << " ";
 621                                 fout << m_vertexs[(*faces)[it]->getVertex(2)]->getPoint() << endl;
 622                         }
 623                 }
 624         }
 625
 626         fout.close();
 627 }
 628
 629 /**
 630  * printFormat
 631  */
 632 void BOP_Mesh::printFormat()
 633 {
 634         cout << "--Vertices--" << endl;
 635         if (m_vertexs.size()>0) {
 636                 cout << "{" << m_vertexs[0]->getPoint().x() << ",";
 637                 cout << m_vertexs[0]->getPoint().y() << ",";
 638                 cout << m_vertexs[0]->getPoint().z() << "}";
 639                 for(unsigned int i=1;i<m_vertexs.size();i++) {
 640                         cout << ",{" << m_vertexs[i]->getPoint().x() << ",";
 641                         cout << m_vertexs[i]->getPoint().y() << ",";
 642                         cout << m_vertexs[i]->getPoint().z() << "}";
 643                 }
 644                 cout << endl;
 645         }
 646
 647         cout << "--Faces--" << endl;
 648         if (m_faces.size()>0) {
 649                 cout << "{" << m_faces[0]->getVertex(0) << ",";
 650                 cout << m_faces[0]->getVertex(1) << "," << m_faces[0]->getVertex(2) << "}";
 651                 for(unsigned int i=1;i<m_faces.size();i++) {
 652                         cout << ",{" << m_faces[i]->getVertex(0) << ",";
 653                         cout << m_faces[i]->getVertex(1) << "," << m_faces[i]->getVertex(2) << "}";
 654                 }
 655                 cout << endl;
 656         }
 657 }
 658
 659 /**
 660  * printFace
 661  */
 662 void BOP_Mesh::printFace(BOP_Face *face, int col)
 663 {
 664   cout << "--Face" << endl;
 665         cout << m_vertexs[face->getVertex(0)]->getPoint();
 666         cout << " " << m_vertexs[face->getVertex(1)]->getPoint();
 667         cout << " " << m_vertexs[face->getVertex(2)]->getPoint();
 668         if (face->size()==4)
 669           cout << " " << m_vertexs[face->getVertex(3)]->getPoint();
 670         cout << " " << col << endl;
 671 }
 672
 673 /**
 674  * testMesh
 675  */
 676 void BOP_Mesh::testMesh()
 677 {
 678
 679         BOP_Face* cares[10];
 680         unsigned int nedges=0;
 681         for(unsigned int i=0;i<m_edges.size();i++) {
 682                 BOP_Edge *edge = m_edges[i];
 683                 BOP_Indexs faces = edge->getFaces();
 684                 unsigned int count = 0;
 685                 const BOP_IT_Indexs facesEnd = faces.end();
 686                 for(BOP_IT_Indexs it = faces.begin();it!=facesEnd;it++) {
 687                         if (m_faces[*it]->getTAG()!=BROKEN) {
 688                                 cares[count] = m_faces[*it];
 689                                 count++;
 690
 691                         }
 692                 }
 693
 694                 if ((count%2)!=0) nedges++;
 695         }
 696         if (nedges)
 697           cout << nedges << " wrong edges." << endl;
 698         else
 699           cout << "well edges." << endl;
 700
 701         unsigned int duplFaces = 0;
 702         unsigned int wrongFaces = 0;
 703         for(unsigned int i=0;i<m_faces.size();i++){
 704           BOP_Face *faceI = m_faces[i];
 705           if (faceI->getTAG()==BROKEN)
 706             continue;
 707
 708           if (testFace(faceI)){
 709             wrongFaces++;
 710             cout << "Wrong Face: " << faceI << endl;
 711           }
 712
 713           for(unsigned int j=i+1;j<m_faces.size();j++){
 714             BOP_Face *faceJ = m_faces[j];
 715
 716             if (faceJ->getTAG()==BROKEN)
 717               continue;
 718
 719             if (testFaces(faceI,faceJ)){
 720               duplFaces++;
 721               cout << "Duplicate FaceI: " << faceI << endl;
 722               cout << "Duplicate FaceJ: " << faceJ << endl;
 723             }
 724           }
 725         }
 726
 727         cout << duplFaces << " duplicate faces." << endl;
 728         cout << wrongFaces << " wrong faces." << endl;
 729 }
 730
 731 /**
 732  * testFace
 733  */
 734 bool BOP_Mesh::testFace(BOP_Face *face){
 735
 736   for(unsigned int i=0;i<face->size();i++){
 737     for(unsigned int j=i+1;j<face->size();j++){
 738       if (face->getVertex(i)==face->getVertex(j))
 739         return true;
 740     }
 741   }
 742
 743   return false;
 744 }
 745
 746 /**
 747  * testFaces
 748  */
 749 bool BOP_Mesh::testFaces(BOP_Face *faceI, BOP_Face *faceJ){
 750
 751   if (faceI->size()<faceJ->size()){
 752     for(unsigned int i=0;i<faceI->size();i++){
 753       if (!faceJ->containsVertex(faceI->getVertex(i)))
 754         return false;
 755     }
 756     //faceI->setTAG(BROKEN);
 757   }
 758   else{
 759     for(unsigned int i=0;i<faceJ->size();i++){
 760       if (!faceI->containsVertex(faceJ->getVertex(i)))
 761         return false;
 762     }
 763     //faceJ->setTAG(BROKEN);
 764   }
 765
 766   return true;
 767 }
 768
 769 /**
 770  * testPlane
 771  */
 772 void BOP_Mesh::testPlane(BOP_Face *face)
 773 {
 774         MT_Plane3 plane1(m_vertexs[face->getVertex(0)]->getPoint(),
 775                                          m_vertexs[face->getVertex(1)]->getPoint(),
 776                                          m_vertexs[face->getVertex(2)]->getPoint());
 777
 778         if (BOP_orientation(plane1,face->getPlane()) < 0) {
 779                 cout << "Test Plane " << face << " v1: ";
 780                 cout << m_vertexs[face->getVertex(0)]->getPoint() << " v2: ";
 781                 cout << m_vertexs[face->getVertex(1)]->getPoint() << " v3: ";
 782                 cout << m_vertexs[face->getVertex(2)]->getPoint() << " plane: ";
 783                 cout << face->getPlane() << endl;
 784                 cout << "Incorrect vertices order!!! plane1: " << plane1 << " (";
 785                 cout << BOP_orientation(plane1,face->getPlane()) << ") " <<  " invert ";
 786                 cout <<  MT_Plane3(m_vertexs[face->getVertex(2)]->getPoint(),
 787                                                    m_vertexs[face->getVertex(1)]->getPoint(),
 788                                                    m_vertexs[face->getVertex(0)]->getPoint()) << endl;
 789                 if (BOP_collinear(m_vertexs[face->getVertex(0)]->getPoint(),
 790                                                   m_vertexs[face->getVertex(1)]->getPoint(),
 791                                                   m_vertexs[face->getVertex(2)]->getPoint())) {
 792                         cout << " COLLINEAR!!!" << endl;
 793                 }
 794                 else {
 795                         cout << endl;
 796                 }
 797         }
 798 }
 799
 800 /**
 801  * testEdges
 802  */
 803 bool BOP_Mesh::testEdges(BOP_Faces *facesObj)
 804 {
 805         for(unsigned int i=0;i<m_edges.size();i++) {
 806                 BOP_Edge *edge = m_edges[i];
 807                 BOP_Indexs faces = edge->getFaces();
 808                 unsigned int count = 0;
 809                 const BOP_IT_Indexs facesEnd = faces.end();
 810                 for(BOP_IT_Indexs it = faces.begin();it!=facesEnd;it++) {
 811                         if ((m_faces[*it]->getTAG()!=BROKEN) && containsFace(facesObj,m_faces[*it]))
 812                                 count++;
 813                 }
 814                 if ((count%2)!=0) {
 815                         return false;
 816                 }
 817         }
 818
 819         return true;
 820 }
 821
 822 /**
 823  * updatePlanes
 824  */
 825 void BOP_Mesh::updatePlanes()
 826 {
 827   const BOP_IT_Faces facesEnd = m_faces.end();
 828         for(BOP_IT_Faces it = m_faces.begin();it!=facesEnd;it++) {
 829           BOP_Face *face = *it;
 830           MT_Plane3 plane(m_vertexs[face->getVertex(0)]->getPoint(),
 831                           m_vertexs[face->getVertex(1)]->getPoint(),
 832                           m_vertexs[face->getVertex(2)]->getPoint());
 833           face->setPlane(plane);
 834         }
 835 }