New files from new booleans
[blender.git] / 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 }