New files from new booleans
[blender.git] / intern / boolop / intern / BOP_Interface.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 <iostream>
32 #include <map>
33 #include "../extern/BOP_Interface.h"
34 #include "../../bsp/intern/BSP_CSGMesh_CFIterator.h"
35 #include "BOP_BSPTree.h"
36 #include "BOP_Mesh.h"
37 #include "BOP_Face2Face.h"
38 #include "BOP_Merge.h"
39 #include "BOP_MaterialContainer.h"
40 #include "BOP_Chrono.h"
41
42 //#define DEBUG
43
44 BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
45                                                                    BOP_Faces* facesA,
46                                                                    BOP_Faces* facesB,
47                                                                    bool       invertMeshA,
48                                                                    bool       invertMeshB);
49 BOP_Face3* BOP_createFace(BOP_Mesh* mesh, 
50                                                   BOP_Index vertex1, 
51                                                   BOP_Index vertex2, 
52                                                   BOP_Index vertex3, 
53                                                   BOP_Index idxFace);
54 void BOP_addMesh(BOP_Mesh*                     mesh,
55                                  BOP_Faces*                    meshFacesId,
56                                  BOP_MaterialContainer*        materials,
57                                  CSG_MeshPropertyDescriptor    props,
58                                  CSG_FaceIteratorDescriptor&   face_it,
59                                  CSG_VertexIteratorDescriptor& vertex_it,
60                                  bool                          invert);
61 BSP_CSGMesh* BOP_newEmptyMesh(CSG_MeshPropertyDescriptor props);  
62 BSP_CSGMesh* BOP_exportMesh(BOP_Mesh*                  inputMesh, 
63                                                         BOP_MaterialContainer*     materials, 
64                                                         CSG_MeshPropertyDescriptor props,
65                                                         bool                       invert);
66 void BOP_meshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp);
67 void BOP_simplifiedMeshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp, bool inverted);
68 void BOP_meshClassify(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp);
69
70 /**
71  * Performs a generic booleam operation, the entry point for external modules.
72  * @param opType Boolean operation type BOP_INTERSECTION, BOP_UNION, BOP_DIFFERENCE
73  * @param outputProps Output mesh properties
74  * @param outputMesh Output mesh, the final result (the object C)
75  * @param obAProps Object A properties
76  * @param obAFaces Object A faces list
77  * @param obAVertices Object A vertices list
78  * @param obBProps Object B properties
79  * @param obBFaces Object B faces list
80  * @param obBVertices Object B vertices list
81  * @param interpFunc Interpolating function
82  * @return operation state: BOP_OK, BOP_NO_SOLID, BOP_ERROR
83  */
84 BoolOpState BOP_performBooleanOperation(BoolOpType                    opType,
85                                                                                 CSG_MeshPropertyDescriptor    outputProps,
86                                                                                 BSP_CSGMesh**                 outputMesh,
87                                                                                 CSG_MeshPropertyDescriptor    obAProps,
88                                                                                 CSG_FaceIteratorDescriptor    obAFaces,
89                                                                                 CSG_VertexIteratorDescriptor  obAVertices,
90                                                                                 CSG_MeshPropertyDescriptor    obBProps,
91                                                                                 CSG_FaceIteratorDescriptor    obBFaces,
92                                                                                 CSG_VertexIteratorDescriptor  obBVertices,
93                                                                                 CSG_InterpolateUserFaceVertexDataFunc interpFunc)
94 {
95         #ifdef DEBUG
96         cout << "BEGIN BOP_performBooleanOperation" << endl;
97         #endif
98
99         // Set invert flags depending on boolean operation type:
100         // INTERSECTION: A^B = and(A,B)
101         // UNION:        A|B = not(and(not(A),not(B)))
102         // DIFFERENCE:   A-B = and(A,not(B))
103         bool invertMeshA = (opType == BOP_UNION);
104         bool invertMeshB = (opType != BOP_INTERSECTION);
105         bool invertMeshC = (opType == BOP_UNION);
106         
107         // Faces list for both objects, used by boolean op.
108         BOP_Faces meshAFacesId;
109         BOP_Faces meshBFacesId;
110         
111         // Build C-mesh, the output mesh
112         BOP_Mesh meshC;
113
114         // Prepare the material container
115         BOP_MaterialContainer materials;
116         materials.setInterpFunc(interpFunc);
117
118         // Add A-mesh into C-mesh
119         BOP_addMesh(&meshC, &meshAFacesId, &materials, obAProps, obAFaces, obAVertices, invertMeshA);
120
121         // Add B-mesh into C-mesh
122         BOP_addMesh(&meshC, &meshBFacesId, &materials, obBProps, obBFaces, obBVertices, invertMeshB);
123
124         // Perform the intersection boolean operation.
125         BoolOpState result = BOP_intersectionBoolOp(&meshC, &meshAFacesId, &meshBFacesId, 
126                                                                                                 invertMeshA, invertMeshB);
127
128         // Invert the output mesh if is required
129         *outputMesh = BOP_exportMesh(&meshC, &materials, outputProps, invertMeshC);
130
131         #ifdef DEBUG
132         cout << "END BOP_performBooleanOperation" << endl;
133         #endif
134         
135         return result;
136 }
137
138 /**
139  * Computes the intersection boolean operation. Creates a new mesh resulting from 
140  * an intersection of two meshes.
141  * @param meshC Input & Output mesh
142  * @param facesA Mesh A faces list
143  * @param facesB Mesh B faces list
144  * @param invertMeshA determines if object A is inverted
145  * @param invertMeshB determines if object B is inverted
146  * @return operation state: BOP_OK, BOP_NO_SOLID, BOP_ERROR
147  */
148 BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
149                                                                    BOP_Faces* facesA,
150                                                                    BOP_Faces* facesB,
151                                                                    bool       invertMeshA,
152                                                                    bool       invertMeshB)
153 {
154         #ifdef DEBUG
155         BOP_Chrono chrono;
156         float t = 0.0f;
157         float c = 0.0f;
158         chrono.start();  
159         cout << "---" << endl;
160         #endif
161
162         // Create BSPs trees for mesh A & B
163         BOP_BSPTree bspA;
164         bspA.addMesh(meshC, *facesA);
165         bspA.computeBox();
166
167         BOP_BSPTree bspB;
168         bspB.addMesh(meshC, *facesB);
169         bspB.computeBox();
170         
171         #ifdef DEBUG
172         c = chrono.stamp(); t += c;
173         cout << "Create BSP     " << c << endl; 
174         #endif
175
176         unsigned int numVertices = meshC->getNumVertexs();
177         
178         // mesh pre-filter
179         BOP_simplifiedMeshFilter(meshC, facesA, &bspB, invertMeshB);
180         if ((0.25*facesA->size()) > bspB.getDeep())
181           BOP_meshFilter(meshC, facesA, &bspB);
182
183         BOP_simplifiedMeshFilter(meshC, facesB, &bspA, invertMeshA);
184         if ((0.25*facesB->size()) > bspA.getDeep())
185           BOP_meshFilter(meshC, facesB, &bspA);
186         
187         #ifdef DEBUG
188         c = chrono.stamp(); t += c;
189         cout << "mesh Filter    " << c << endl; 
190         #endif
191
192         // Face 2 Face
193         BOP_Face2Face(meshC,facesA,facesB);
194
195         #ifdef DEBUG
196         c = chrono.stamp(); t += c;
197         cout << "Face2Face      " << c << endl;
198         #endif
199
200         // BSP classification
201         BOP_meshClassify(meshC,facesA,&bspB);
202         BOP_meshClassify(meshC,facesB,&bspA);
203         
204         #ifdef DEBUG
205         c = chrono.stamp(); t += c;
206         cout << "Classification " << c << endl;
207         #endif
208         
209         // Process overlapped faces
210         BOP_removeOverlappedFaces(meshC,facesA,facesB);
211         
212         #ifdef DEBUG
213         c = chrono.stamp(); t += c;
214         cout << "Remove overlap " << c << endl;
215         #endif
216
217         // Sew two meshes
218         BOP_sew(meshC,facesA,facesB);
219
220         #ifdef DEBUG
221         c = chrono.stamp(); t += c;
222         cout << "Sew            " << c << endl;
223         #endif
224
225         // Merge faces
226         BOP_Merge::getInstance().mergeFaces(meshC,numVertices);
227
228         #ifdef DEBUG
229         c = chrono.stamp(); t += c;
230         cout << "Merge faces    " << c << endl;
231         cout << "Total          " << t << endl;
232         // Test integrity
233         meshC->testMesh();
234         #endif
235         
236         return BOP_OK;
237 }
238
239 /**
240  * Preprocess to filter no collisioned faces.
241  * @param meshC Input & Output mesh data
242  * @param faces Faces list to test
243  * @param bsp BSP tree used to filter
244  */
245 void BOP_meshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp)
246 {
247         BOP_IT_Faces it;
248         BOP_TAG tag;
249         
250         it = faces->begin();
251         while (it!=faces->end()) {
252                 BOP_Face *face = *it;
253                 MT_Point3 p1 = meshC->getVertex(face->getVertex(0))->getPoint();
254                 MT_Point3 p2 = meshC->getVertex(face->getVertex(1))->getPoint();
255                 MT_Point3 p3 = meshC->getVertex(face->getVertex(2))->getPoint();
256                 if ((tag = bsp->classifyFace(p1,p2,p3,face->getPlane()))==OUT||tag==OUTON) {
257                         face->setTAG(BROKEN);
258                         it = faces->erase(it);
259                 }
260                 else if (tag == IN) {
261                         it = faces->erase(it);
262                 }else{
263                   it++;
264                 }
265         }
266 }
267
268 /**
269  * Pre-process to filter no collisioned faces.
270  * @param meshC Input & Output mesh data
271  * @param faces Faces list to test
272  * @param bsp BSP tree used to filter
273  * @param inverted determines if the object is inverted
274  */
275 void BOP_simplifiedMeshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp, bool inverted)
276 {
277         BOP_IT_Faces it;
278         
279         it = faces->begin();
280         while (it!=faces->end()) {
281                 BOP_Face *face = *it;
282                 MT_Point3 p1 = meshC->getVertex(face->getVertex(0))->getPoint();
283                 MT_Point3 p2 = meshC->getVertex(face->getVertex(1))->getPoint();
284                 MT_Point3 p3 = meshC->getVertex(face->getVertex(2))->getPoint();
285                 if (bsp->filterFace(p1,p2,p3,face)==OUT) {
286                         if (!inverted) face->setTAG(BROKEN);
287                         it = faces->erase(it);
288                 }
289                 else {
290                         it++;
291                 }
292         }
293 }
294
295 /**
296  * Process to classify the mesh faces using a bsp tree.
297  * @param meshC Input & Output mesh data
298  * @param faces Faces list to classify
299  * @param bsp BSP tree used to face classify
300  */
301 void BOP_meshClassify(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp)
302 {
303         for(BOP_IT_Faces face=faces->begin();face!=faces->end();face++) {
304                 if ((*face)->getTAG()!=BROKEN) {
305                         MT_Point3 p1 = meshC->getVertex((*face)->getVertex(0))->getPoint();
306                         MT_Point3 p2 = meshC->getVertex((*face)->getVertex(1))->getPoint();
307                         MT_Point3 p3 = meshC->getVertex((*face)->getVertex(2))->getPoint();
308                         if (bsp->simplifiedClassifyFace(p1,p2,p3,(*face)->getPlane())!=IN) {
309                                 (*face)->setTAG(BROKEN);
310                         }
311                 }
312         }
313 }
314
315 /**
316  * Returns a new mesh triangle.
317  * @param meshC Input & Output mesh data
318  * @param vertex1 first vertex of the new face
319  * @param vertex2 second vertex of the new face
320  * @param vertex3 third vertex of the new face
321  * @param idxFace identifier of the new face
322  * @return new the new face
323  */
324 BOP_Face3 *BOP_createFace3(BOP_Mesh* mesh, 
325                                                    BOP_Index       vertex1, 
326                                                    BOP_Index       vertex2, 
327                                                    BOP_Index       vertex3, 
328                                                    BOP_Index       idxFace)
329 {
330         MT_Point3 p1 = mesh->getVertex(vertex1)->getPoint();
331         MT_Point3 p2 = mesh->getVertex(vertex2)->getPoint();
332         MT_Point3 p3 = mesh->getVertex(vertex3)->getPoint();
333         MT_Plane3 plane(p1,p2,p3);
334
335         return new BOP_Face3(vertex1, vertex2, vertex3, plane, idxFace);
336 }
337
338 /**
339  * Adds mesh information into destination mesh.
340  * @param mesh input/output mesh, destination for the new mesh data
341  * @param meshFacesId output mesh faces, contains an added faces list
342  * @param materials used to store material data
343  * @param props Properties of the input mesh data
344  * @param face_it faces iterator
345  * @param vertex_it vertices iterator
346  * @param inverted if TRUE adding inverted faces, non-inverted otherwise
347  */
348 void BOP_addMesh(BOP_Mesh*                     mesh,
349                                  BOP_Faces*                    meshFacesId,
350                                  BOP_MaterialContainer*        materials,
351                                  CSG_MeshPropertyDescriptor    props,
352                                  CSG_FaceIteratorDescriptor&   face_it,
353                                  CSG_VertexIteratorDescriptor& vertex_it,
354                                  bool                          invert)
355 {
356         unsigned int vtxIndexOffset = mesh->getNumVertexs();
357
358         // The size of the vertex data array will be at least the number of faces.
359         CSG_IVertex vertex;
360         while (!vertex_it.Done(vertex_it.it)) {
361                 vertex_it.Fill(vertex_it.it,&vertex);
362                 MT_Point3 pos(vertex.position);
363                 mesh->addVertex(pos);
364                 vertex_it.Step(vertex_it.it);
365         }
366
367         CSG_IFace face;
368         
369         // now for the polygons.
370         // we may need to decalare some memory for user defined face properties.
371         unsigned int sizeFace = props.user_data_size;
372         if (sizeFace) {
373                 face.user_face_data = new char[sizeFace];
374         } 
375         else {
376                 face.user_face_data = NULL;
377         }
378
379         unsigned int sizeVertex = props.user_face_vertex_data_size;
380         if (sizeVertex) {
381                 char * fv_data2 = NULL;
382                 fv_data2 = new char[4 * sizeVertex];
383                 
384                 face.user_face_vertex_data[0] = fv_data2;
385                 face.user_face_vertex_data[1] = fv_data2 + sizeVertex;
386                 face.user_face_vertex_data[2] = fv_data2 + 2*sizeVertex;
387                 face.user_face_vertex_data[3] = fv_data2 + 3*sizeVertex;
388         } 
389         else {
390                 face.user_face_vertex_data[0] = NULL;
391                 face.user_face_vertex_data[1] = NULL;
392                 face.user_face_vertex_data[2] = NULL;
393                 face.user_face_vertex_data[3] = NULL;
394         }
395
396         unsigned int idFaceMaterial;
397         BOP_Material faceMaterial(sizeFace,sizeVertex);
398         BOP_Material* materialHandler;
399         BOP_Face3 *newface;
400         
401         while (!face_it.Done(face_it.it)) {
402                 face_it.Fill(face_it.it,&face);
403
404                 faceMaterial.setFaceMaterial((char *)face.user_face_data);
405                 faceMaterial.setFaceVertexMaterial((char *)face.user_face_vertex_data[0]);
406                 faceMaterial.setOriginalFace(mesh->getNumFaces());
407                 faceMaterial.setIsQuad(face.vertex_number == 4);
408                 idFaceMaterial = materials->addMaterial(faceMaterial);
409                 materialHandler = materials->getMaterial(idFaceMaterial);
410
411                 // Let's not rely on quads being coplanar - especially if they 
412                 // are coming out of that soup of code from blender...
413                 if (face.vertex_number == 4){
414                         // QUAD
415                         if (invert) {
416                                 newface = BOP_createFace3(mesh,
417                                                                                   face.vertex_index[2] + vtxIndexOffset,
418                                                                                   face.vertex_index[0] + vtxIndexOffset,
419                                                                                   face.vertex_index[3] + vtxIndexOffset,
420                                                                                   idFaceMaterial);
421                                 meshFacesId->push_back(newface);
422                                 mesh->addFace(newface);
423                                 materialHandler->setOriginalFaceVertex(newface->getVertex(0),2);
424                                 materialHandler->setOriginalFaceVertex(newface->getVertex(1),0);
425                                 materialHandler->setOriginalFaceVertex(newface->getVertex(2),3);
426                                 newface = BOP_createFace3(mesh,
427                                                                                   face.vertex_index[2] + vtxIndexOffset,
428                                                                                   face.vertex_index[1] + vtxIndexOffset,
429                                                                                   face.vertex_index[0] + vtxIndexOffset,
430                                                                                   idFaceMaterial);
431                                 meshFacesId->push_back(newface);
432                                 mesh->addFace(newface);
433                                 materialHandler->setOriginalFaceVertex(newface->getVertex(1),1);
434                         }
435                         else {
436                                 newface = BOP_createFace3(mesh,
437                                                                                  face.vertex_index[0] + vtxIndexOffset,
438                                                                                  face.vertex_index[2] + vtxIndexOffset,
439                                                                                  face.vertex_index[3] + vtxIndexOffset,
440                                                                                  idFaceMaterial);
441                                 meshFacesId->push_back(newface);
442                                 mesh->addFace(newface);
443                                 materialHandler->setOriginalFaceVertex(newface->getVertex(0),0);
444                                 materialHandler->setOriginalFaceVertex(newface->getVertex(1),2);
445                                 materialHandler->setOriginalFaceVertex(newface->getVertex(2),3);
446                                 newface = BOP_createFace3(mesh,
447                                                                                  face.vertex_index[0] + vtxIndexOffset,
448                                                                                  face.vertex_index[1] + vtxIndexOffset,
449                                                                                  face.vertex_index[2] + vtxIndexOffset,
450                                                                                  idFaceMaterial);
451                                 meshFacesId->push_back(newface);
452                                 mesh->addFace(newface);
453                                 materialHandler->setOriginalFaceVertex(newface->getVertex(1),1);
454                         }
455                 }
456                 else {
457                         // TRIANGLES
458                         if (invert) {
459                                 newface = BOP_createFace3(mesh,
460                                                                                   face.vertex_index[2] + vtxIndexOffset,
461                                                                                   face.vertex_index[1] + vtxIndexOffset,
462                                                                                   face.vertex_index[0] + vtxIndexOffset,
463                                                                                   idFaceMaterial);
464                                 meshFacesId->push_back(newface);
465                                 mesh->addFace(newface);
466                                 materialHandler->setOriginalFaceVertex(newface->getVertex(0),2);
467                                 materialHandler->setOriginalFaceVertex(newface->getVertex(1),1);
468                                 materialHandler->setOriginalFaceVertex(newface->getVertex(2),0);
469                         }
470                         else {
471                                 newface = BOP_createFace3(mesh,
472                                                                                   face.vertex_index[0] + vtxIndexOffset,
473                                                                                   face.vertex_index[1] + vtxIndexOffset,
474                                                                                   face.vertex_index[2] + vtxIndexOffset,
475                                                                                   idFaceMaterial);
476                                 meshFacesId->push_back(newface);
477                                 mesh->addFace(newface);
478                                 materialHandler->setOriginalFaceVertex(newface->getVertex(0),0);
479                                 materialHandler->setOriginalFaceVertex(newface->getVertex(1),1);
480                                 materialHandler->setOriginalFaceVertex(newface->getVertex(2),2);
481                         }
482                 }
483                 
484                 face_it.Step(face_it.it);
485         }
486         
487         // delete temporal material data
488         if (face.user_face_data)
489                 delete[] static_cast<char *>(face.user_face_data);
490         if (face.user_face_vertex_data)
491                 delete[] static_cast<char *>(face.user_face_vertex_data[0]);
492 }
493
494 /**
495  * Returns an empty mesh with the specified properties.
496  * @param props Output mesh properties
497  * @return a new empty mesh
498  */
499 BSP_CSGMesh* BOP_newEmptyMesh(CSG_MeshPropertyDescriptor props)
500 {
501         BSP_CSGMesh* mesh = BSP_CSGMesh::New();
502         if (mesh == NULL) return mesh;
503
504         vector<BSP_MVertex>* vertices = new vector<BSP_MVertex>;
505         BSP_CSGUserData* faceData     = new BSP_CSGUserData(props.user_data_size);
506         BSP_CSGUserData* faceVtxData  = new BSP_CSGUserData(props.user_face_vertex_data_size);
507         
508         mesh->SetVertices(vertices);
509         mesh->SetFaceData(faceData);
510         mesh->SetFaceVertexData(faceVtxData);
511
512         return mesh;
513 }
514
515 /**
516  * Exports a BOP_Mesh to a BSP_CSGMesh.
517  * @param mesh Input mesh
518  * @param materials used to reconstruct original faces materials
519  * @param props Properties of output mesh
520  * @param invert if TRUE export with inverted faces, no inverted otherwise
521  * @return the corresponding new BSP_CSGMesh
522  */
523 BSP_CSGMesh* BOP_exportMesh(BOP_Mesh*                  mesh, 
524                                                         BOP_MaterialContainer*     materials, 
525                                                         CSG_MeshPropertyDescriptor props,
526                                                         bool                       invert)
527 {
528         BSP_CSGMesh* outputMesh = BOP_newEmptyMesh(props);
529
530         // User data handlers
531         BSP_CSGUserData* outputFaceVtxData = &(outputMesh->FaceVertexData());
532         BSP_CSGUserData* outputFaceData    = &(outputMesh->FaceData());
533   
534         // vtx index dictionary, to translate indeces from input to output.
535         map<int,unsigned int> dic;
536         map<int,unsigned int>::iterator itDic;
537
538         unsigned int count = 0;
539
540         // Add a new face for each face in the input list
541         BOP_Faces faces = mesh->getFaces();
542         BOP_Vertexs vertexs = mesh->getVertexs();
543
544         // Reserve temporal memory
545         char* tmpFaceVtxData = new char[props.user_face_vertex_data_size];
546                         
547         for (BOP_IT_Faces face = faces.begin(); face != faces.end(); face++) {
548                 if ((*face)->getTAG()!=BROKEN){    
549                         // Add output face
550                         outputMesh->FaceSet().push_back(BSP_MFace());
551                         BSP_MFace& outFace = outputMesh->FaceSet().back();
552
553                         // Copy face
554                         outFace.m_verts.clear();
555                         outFace.m_fv_data.clear();
556                         outFace.m_plane = (*face)->getPlane();
557
558                         // Copy face user data from input mesh
559                         outputFaceData->Duplicate(materials->getFaceMaterial((*face)->getOriginalFace()));
560
561                         // invert face if is required
562                         if (invert) (*face)->invert();
563                         
564                         // Add the face vertex if not added yet
565                         for (unsigned int pos=0;pos<(*face)->size();pos++) {
566                                 BSP_VertexInd outVtxId;
567                                 BOP_Index idVertex = (*face)->getVertex(pos);
568                                 itDic = dic.find(idVertex);
569                                 if (itDic == dic.end()) {
570                                         // The vertex isn't added yet
571                                         outVtxId = BSP_VertexInd(outputMesh->VertexSet().size());
572                                         BSP_MVertex outVtx((mesh->getVertex(idVertex))->getPoint());
573                                         outVtx.m_edges.clear();
574                                         outputMesh->VertexSet().push_back(outVtx);
575                                         dic[idVertex] = outVtxId;
576                                         count++;
577                                 }
578                                 else {
579                                         // The vertex is added
580                                         outVtxId = BSP_VertexInd(itDic->second);
581                                 }
582                                 
583                                 // Add vertex to output face
584                                 outFace.m_verts.push_back(outVtxId);
585
586                                 // Add face vertex user data
587                                 char* faceVtxData = materials->getFaceVertexMaterial(mesh,
588                                                                                                                                         (*face)->getOriginalFace(),
589                                                                                                                                         (mesh->getVertex(idVertex))->getPoint(),
590                                                                                                                                         tmpFaceVtxData);
591                                 BSP_UserFVInd userFVInd(outputFaceVtxData->Duplicate((void*) faceVtxData));
592                                 outFace.m_fv_data.push_back(userFVInd);
593                         }
594                 }
595         }
596         // free temporal memory
597         delete[] tmpFaceVtxData;
598         
599         // Build the mesh edges using topological informtion
600         outputMesh->BuildEdges();
601         
602         return outputMesh;
603 }