Final merge of HEAD (bf-blender) into the orange branch.
[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 itv=m_vertexs.begin();itv!=vertexsEnd;itv++){
44                 delete *itv;
45         }
46         m_vertexs.clear();
47   
48         const BOP_IT_Edges edgesEnd = m_edges.end();
49         for(BOP_IT_Edges ite=m_edges.begin();ite!=edgesEnd;ite++){
50                 delete *ite;
51         }
52         m_edges.clear();
53   
54         const BOP_IT_Faces facesEnd = m_faces.end();
55         for(BOP_IT_Faces itf=m_faces.begin();itf!=facesEnd;itf++){
56                 delete *itf;
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         BOP_IT_Indexs oldEdgeIndex;
486         if (oldIndex==newIndex) return newIndex;
487   
488         // Update faces, edges and vertices  
489         BOP_Vertex *oldVertex = m_vertexs[oldIndex];
490         BOP_Vertex *newVertex = m_vertexs[newIndex];
491         BOP_Indexs oldEdges = oldVertex->getEdges();
492
493         BOP_Index edgeIdx=0;
494         bool found = false;
495
496         // Update faces to the newIndex
497         BOP_IT_Indexs oldEdgesEnd = oldEdges.end();
498         for(oldEdgeIndex=oldEdges.begin();oldEdgeIndex!=oldEdgesEnd;
499                    oldEdgeIndex++) {
500                 BOP_Edge *edge = m_edges[*oldEdgeIndex];
501                 if ((edge->getVertex1()==oldIndex && edge->getVertex2()==newIndex) ||
502                         (edge->getVertex2()==oldIndex && edge->getVertex1()==newIndex)) {
503                         // Remove old edge  ==> set edge faces to BROKEN      
504                         BOP_Indexs edgeFaces = edge->getFaces();
505                         const BOP_IT_Indexs edgeFacesEnd = edgeFaces.end();
506                         for(BOP_IT_Indexs idxFace=edgeFaces.begin();idxFace!=edgeFacesEnd;
507                                    idxFace++) {
508                                 m_faces[*idxFace]->setTAG(BROKEN);
509                         }
510                         edgeIdx = *oldEdgeIndex;
511                         found = true;
512                 }
513                 else {
514                         BOP_Indexs faces = edge->getFaces();
515                         const BOP_IT_Indexs facesEnd = faces.end();
516                         for(BOP_IT_Indexs face=faces.begin();face!=facesEnd;face++) {
517                                 if (m_faces[*face]->getTAG()!=BROKEN)
518                                         m_faces[*face]->replaceVertexIndex(oldIndex,newIndex);
519                         }
520                 }
521         } 
522         if (found) {
523                 oldVertex->removeEdge(edgeIdx);
524                 newVertex->removeEdge(edgeIdx);
525         }
526
527         oldEdgesEnd = oldEdges.end();
528         for(oldEdgeIndex=oldEdges.begin();oldEdgeIndex!=oldEdgesEnd;
529                    oldEdgeIndex++) {
530                 BOP_Edge * edge = m_edges[*oldEdgeIndex];
531                 BOP_Edge * edge2;
532                 BOP_Index v1 = edge->getVertex1();
533     
534                 v1 = (v1==oldIndex?edge->getVertex2():v1);      
535                 if ((edge2 = getEdge(newIndex,v1)) == NULL) {
536                         edge->replaceVertexIndex(oldIndex,newIndex);
537                         newVertex->addEdge(*oldEdgeIndex);
538                 }
539                 else {
540                         BOP_Indexs faces = edge->getFaces();
541                         const BOP_IT_Indexs facesEnd = faces.end();
542                         for(BOP_IT_Indexs f=faces.begin();f!=facesEnd;f++) {
543                                 if (m_faces[*f]->getTAG()!=BROKEN)
544                                 edge2->addFace(*f);
545                         }
546                         BOP_Vertex *oppositeVertex = m_vertexs[v1];
547                         oppositeVertex->removeEdge(*oldEdgeIndex);
548                         edge->replaceVertexIndex(oldIndex,newIndex);
549                 }
550         }
551         oldVertex->setTAG(BROKEN);
552
553         return newIndex;
554 }
555
556
557
558 /** ***************************************************************************
559  * DEBUG METHODS                                                              * 
560  * This functions are used to test the mesh state and debug program errors.   *
561  ******************************************************************************/
562
563 /**
564  * print
565  */
566 void BOP_Mesh::print() 
567 {
568         unsigned int i;
569         cout << "--Faces--" << endl;
570         for(i=0;i<m_faces.size();i++){
571                 cout << "Face " << i << ": " << m_faces[i] << endl;
572         }
573
574         cout << "--Vertices--" << endl;
575         for(i=0;i<m_vertexs.size();i++){
576                 cout << "Point " << i << ": " << m_vertexs[i]->getPoint() << endl;
577         }
578 }
579
580 /**
581  * printFormat
582  */
583 void BOP_Mesh::printFormat(BOP_Faces *faces)
584 {
585         if (faces->size()) {
586                 for(unsigned int it=1;it<faces->size();it++) {
587                         if ((*faces)[it]->getTAG()!=BROKEN) {
588                                 cout << m_vertexs[(*faces)[it]->getVertex(0)]->getPoint() << " ";
589                                 cout << m_vertexs[(*faces)[it]->getVertex(1)]->getPoint() << " ";
590                                 cout << m_vertexs[(*faces)[it]->getVertex(2)]->getPoint() << endl;
591                         }
592                 }
593         }
594 }
595
596 /**
597  * saveFormat
598  */
599 void BOP_Mesh::saveFormat(BOP_Faces *faces,char *filename)
600 {
601         ofstream fout(filename);
602   
603         if (!fout.is_open()) {
604                 cerr << "BOP_Mesh::saveFormat Error: Could not create file." << endl;
605                 return;
606         }
607
608         unsigned int count = 0;
609         if (faces->size()) {
610                 for(unsigned int it=0;it<faces->size();it++) {
611                         if ((*faces)[it]->getTAG()!=BROKEN) {
612                                 count++;
613                         }
614                 }
615         }
616
617         fout << count << endl;
618         if (faces->size()) {
619                 for(unsigned int it=0;it<faces->size();it++) {
620                         if ((*faces)[it]->getTAG()!=BROKEN){
621                                 fout << m_vertexs[(*faces)[it]->getVertex(0)]->getPoint() << " ";
622                                 fout << m_vertexs[(*faces)[it]->getVertex(1)]->getPoint() << " ";
623                                 fout << m_vertexs[(*faces)[it]->getVertex(2)]->getPoint() << endl;
624                         }
625                 }
626         }
627
628         fout.close();
629 }
630
631 /**
632  * printFormat
633  */
634 void BOP_Mesh::printFormat()
635 {
636         cout << "--Vertices--" << endl;
637         if (m_vertexs.size()>0) {
638                 cout << "{" << m_vertexs[0]->getPoint().x() << ",";
639                 cout << m_vertexs[0]->getPoint().y() << ",";
640                 cout << m_vertexs[0]->getPoint().z() << "}";
641                 for(unsigned int i=1;i<m_vertexs.size();i++) {
642                         cout << ",{" << m_vertexs[i]->getPoint().x() << ",";
643                         cout << m_vertexs[i]->getPoint().y() << ",";
644                         cout << m_vertexs[i]->getPoint().z() << "}";
645                 }
646                 cout << endl;
647         }
648
649         cout << "--Faces--" << endl;
650         if (m_faces.size()>0) {
651                 cout << "{" << m_faces[0]->getVertex(0) << ",";
652                 cout << m_faces[0]->getVertex(1) << "," << m_faces[0]->getVertex(2) << "}";
653                 for(unsigned int i=1;i<m_faces.size();i++) {
654                         cout << ",{" << m_faces[i]->getVertex(0) << ",";
655                         cout << m_faces[i]->getVertex(1) << "," << m_faces[i]->getVertex(2) << "}";
656                 }
657                 cout << endl;
658         }
659 }
660
661 /**
662  * printFace
663  */
664 void BOP_Mesh::printFace(BOP_Face *face, int col)
665 {
666   cout << "--Face" << endl;
667         cout << m_vertexs[face->getVertex(0)]->getPoint();
668         cout << " " << m_vertexs[face->getVertex(1)]->getPoint();
669         cout << " " << m_vertexs[face->getVertex(2)]->getPoint();
670         if (face->size()==4)
671           cout << " " << m_vertexs[face->getVertex(3)]->getPoint();
672         cout << " " << col << endl;
673 }
674
675 /**
676  * testMesh
677  */
678 void BOP_Mesh::testMesh()
679 {
680
681         BOP_Face* cares[10];
682         unsigned int nedges=0,i;
683         for(i=0;i<m_edges.size();i++) {
684                 BOP_Edge *edge = m_edges[i];
685                 BOP_Indexs faces = edge->getFaces();
686                 unsigned int count = 0;
687                 const BOP_IT_Indexs facesEnd = faces.end();
688                 for(BOP_IT_Indexs it = faces.begin();it!=facesEnd;it++) {
689                         if (m_faces[*it]->getTAG()!=BROKEN) {
690                                 cares[count] = m_faces[*it];
691                                 count++;
692                                 
693                         }
694                 }
695
696                 if ((count%2)!=0) nedges++;
697         }
698         if (nedges)
699           cout << nedges << " wrong edges." << endl;
700         else
701           cout << "well edges." << endl;
702
703         unsigned int duplFaces = 0;
704         unsigned int wrongFaces = 0;
705         for(i=0;i<m_faces.size();i++){
706           BOP_Face *faceI = m_faces[i];
707           if (faceI->getTAG()==BROKEN)
708             continue;
709
710           if (testFace(faceI)){
711             wrongFaces++;
712             cout << "Wrong Face: " << faceI << endl;
713           }
714
715           for(unsigned int j=i+1;j<m_faces.size();j++){
716             BOP_Face *faceJ = m_faces[j];
717
718             if (faceJ->getTAG()==BROKEN)
719               continue;
720
721             if (testFaces(faceI,faceJ)){
722               duplFaces++;
723               cout << "Duplicate FaceI: " << faceI << endl;
724               cout << "Duplicate FaceJ: " << faceJ << endl;
725             }
726           }
727         }
728
729         cout << duplFaces << " duplicate faces." << endl;
730         cout << wrongFaces << " wrong faces." << endl;
731 }
732
733 /**
734  * testFace
735  */
736 bool BOP_Mesh::testFace(BOP_Face *face){
737   
738   for(unsigned int i=0;i<face->size();i++){
739     for(unsigned int j=i+1;j<face->size();j++){
740       if (face->getVertex(i)==face->getVertex(j))
741         return true;
742     }
743   }
744
745   return false;
746 }
747
748 /**
749  * testFaces
750  */
751 bool BOP_Mesh::testFaces(BOP_Face *faceI, BOP_Face *faceJ){
752
753   if (faceI->size()<faceJ->size()){
754     for(unsigned int i=0;i<faceI->size();i++){
755       if (!faceJ->containsVertex(faceI->getVertex(i)))
756         return false;
757     }
758     //faceI->setTAG(BROKEN);
759   }
760   else{
761     for(unsigned int i=0;i<faceJ->size();i++){
762       if (!faceI->containsVertex(faceJ->getVertex(i)))
763         return false;
764     }
765     //faceJ->setTAG(BROKEN);
766   }
767
768   return true;
769 }
770
771 /**
772  * testPlane
773  */
774 void BOP_Mesh::testPlane(BOP_Face *face)
775 {
776         MT_Plane3 plane1(m_vertexs[face->getVertex(0)]->getPoint(), 
777                                          m_vertexs[face->getVertex(1)]->getPoint(),
778                                          m_vertexs[face->getVertex(2)]->getPoint());
779
780         if (BOP_orientation(plane1,face->getPlane()) < 0) {       
781                 cout << "Test Plane " << face << " v1: ";
782                 cout << m_vertexs[face->getVertex(0)]->getPoint() << " v2: ";
783                 cout << m_vertexs[face->getVertex(1)]->getPoint() << " v3: ";
784                 cout << m_vertexs[face->getVertex(2)]->getPoint() << " plane: ";
785                 cout << face->getPlane() << endl;
786                 cout << "Incorrect vertices order!!! plane1: " << plane1 << " (";
787                 cout << BOP_orientation(plane1,face->getPlane()) << ") " <<  " invert ";
788                 cout <<  MT_Plane3(m_vertexs[face->getVertex(2)]->getPoint(),
789                                                    m_vertexs[face->getVertex(1)]->getPoint(),
790                                                    m_vertexs[face->getVertex(0)]->getPoint()) << endl;
791                 if (BOP_collinear(m_vertexs[face->getVertex(0)]->getPoint(),
792                                                   m_vertexs[face->getVertex(1)]->getPoint(),
793                                                   m_vertexs[face->getVertex(2)]->getPoint())) {
794                         cout << " COLLINEAR!!!" << endl;
795                 }
796                 else {
797                         cout << endl;
798                 }
799         }
800 }
801
802 /**
803  * testEdges
804  */
805 bool BOP_Mesh::testEdges(BOP_Faces *facesObj)
806 {
807         for(unsigned int i=0;i<m_edges.size();i++) {
808                 BOP_Edge *edge = m_edges[i];
809                 BOP_Indexs faces = edge->getFaces();
810                 unsigned int count = 0;
811                 const BOP_IT_Indexs facesEnd = faces.end();
812                 for(BOP_IT_Indexs it = faces.begin();it!=facesEnd;it++) {
813                         if ((m_faces[*it]->getTAG()!=BROKEN) && containsFace(facesObj,m_faces[*it]))
814                                 count++;
815                 }
816                 if ((count%2)!=0) {
817                         return false;
818                 }
819         }
820         
821         return true;
822 }
823
824 /**
825  * updatePlanes
826  */
827 void BOP_Mesh::updatePlanes() 
828 {
829   const BOP_IT_Faces facesEnd = m_faces.end();
830         for(BOP_IT_Faces it = m_faces.begin();it!=facesEnd;it++) {
831           BOP_Face *face = *it;
832           MT_Plane3 plane(m_vertexs[face->getVertex(0)]->getPoint(), 
833                           m_vertexs[face->getVertex(1)]->getPoint(),
834                           m_vertexs[face->getVertex(2)]->getPoint());
835           face->setPlane(plane);
836         }
837 }