doxygen: intern/boolop tagged
[blender.git] / intern / boolop / intern / BOP_Interface.cpp
1 /*
2  * ***** BEGIN GPL 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.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file boolop/intern/BOP_Interface.cpp
29  *  \ingroup boolopintern
30  */
31
32  
33 #include <iostream>
34 #include <map>
35 #include "../extern/BOP_Interface.h"
36 #include "../../bsp/intern/BSP_CSGMesh_CFIterator.h"
37 #include "BOP_BSPTree.h"
38 #include "BOP_Mesh.h"
39 #include "BOP_Face2Face.h"
40 #include "BOP_Merge.h"
41 #include "BOP_Merge2.h"
42 #include "BOP_Chrono.h"
43
44 #if defined(BOP_ORIG_MERGE) && defined(BOP_NEW_MERGE) 
45 #include "../../../source/blender/blenkernel/BKE_global.h"
46 #endif
47
48 BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
49                                                                    BOP_Faces* facesA,
50                                                                    BOP_Faces* facesB,
51                                                                    bool       invertMeshA,
52                                                                    bool       invertMeshB);
53 BOP_Face3* BOP_createFace(BOP_Mesh* mesh, 
54                                                   BOP_Index vertex1, 
55                                                   BOP_Index vertex2, 
56                                                   BOP_Index vertex3, 
57                                                   BOP_Index origFace);
58 void BOP_addMesh(BOP_Mesh*                     mesh,
59                                  BOP_Faces*                    meshFacesId,
60                                  CSG_FaceIteratorDescriptor&   face_it,
61                                  CSG_VertexIteratorDescriptor& vertex_it,
62                                  bool                          invert);
63 BSP_CSGMesh* BOP_newEmptyMesh();
64 BSP_CSGMesh* BOP_exportMesh(BOP_Mesh*                  inputMesh, 
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 outputMesh Output mesh, the final result (the object C)
74  * @param obAFaces Object A faces list
75  * @param obAVertices Object A vertices list
76  * @param obBFaces Object B faces list
77  * @param obBVertices Object B vertices list
78  * @param interpFunc Interpolating function
79  * @return operation state: BOP_OK, BOP_NO_SOLID, BOP_ERROR
80  */
81 BoolOpState BOP_performBooleanOperation(BoolOpType                    opType,
82                                                                                 BSP_CSGMesh**                 outputMesh,
83                                                                                 CSG_FaceIteratorDescriptor    obAFaces,
84                                                                                 CSG_VertexIteratorDescriptor  obAVertices,
85                                                                                 CSG_FaceIteratorDescriptor    obBFaces,
86                                                                                 CSG_VertexIteratorDescriptor  obBVertices)
87 {
88         #ifdef BOP_DEBUG
89         cout << "BEGIN BOP_performBooleanOperation" << endl;
90         #endif
91
92         // Set invert flags depending on boolean operation type:
93         // INTERSECTION: A^B = and(A,B)
94         // UNION:        A|B = not(and(not(A),not(B)))
95         // DIFFERENCE:   A-B = and(A,not(B))
96         bool invertMeshA = (opType == BOP_UNION);
97         bool invertMeshB = (opType != BOP_INTERSECTION);
98         bool invertMeshC = (opType == BOP_UNION);
99         
100         // Faces list for both objects, used by boolean op.
101         BOP_Faces meshAFacesId;
102         BOP_Faces meshBFacesId;
103         
104         // Build C-mesh, the output mesh
105         BOP_Mesh meshC;
106
107         // Add A-mesh into C-mesh
108         BOP_addMesh(&meshC, &meshAFacesId, obAFaces, obAVertices, invertMeshA);
109
110         // Add B-mesh into C-mesh
111         BOP_addMesh(&meshC, &meshBFacesId, obBFaces, obBVertices, invertMeshB);
112
113         // for now, allow operations on non-manifold (non-solid) meshes
114 #if 0
115         if (!meshC.isClosedMesh())
116                 return BOP_NO_SOLID;
117 #endif
118
119         // Perform the intersection boolean operation.
120         BoolOpState result = BOP_intersectionBoolOp(&meshC, &meshAFacesId, &meshBFacesId, 
121                                                                                                 invertMeshA, invertMeshB);
122
123         // Invert the output mesh if is required
124         *outputMesh = BOP_exportMesh(&meshC, invertMeshC);
125
126         #ifdef BOP_DEBUG
127         cout << "END BOP_performBooleanOperation" << endl;
128         #endif
129         
130         return result;
131 }
132
133 /**
134  * Computes the intersection boolean operation. Creates a new mesh resulting from 
135  * an intersection of two meshes.
136  * @param meshC Input & Output mesh
137  * @param facesA Mesh A faces list
138  * @param facesB Mesh B faces list
139  * @param invertMeshA determines if object A is inverted
140  * @param invertMeshB determines if object B is inverted
141  * @return operation state: BOP_OK, BOP_NO_SOLID, BOP_ERROR
142  */
143 BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
144                                                                    BOP_Faces* facesA,
145                                                                    BOP_Faces* facesB,
146                                                                    bool       invertMeshA,
147                                                                    bool       invertMeshB)
148 {
149         #ifdef BOP_DEBUG
150         BOP_Chrono chrono;
151         float t = 0.0f;
152         float c = 0.0f;
153         chrono.start();  
154         cout << "---" << endl;
155         #endif
156
157         // Create BSPs trees for mesh A & B
158         BOP_BSPTree bspA;
159         bspA.addMesh(meshC, *facesA);
160
161         BOP_BSPTree bspB;
162         bspB.addMesh(meshC, *facesB);
163
164         #ifdef BOP_DEBUG
165         c = chrono.stamp(); t += c;
166         cout << "Create BSP     " << c << endl; 
167         #endif
168
169         unsigned int numVertices = meshC->getNumVertexs();
170         
171         // mesh pre-filter
172         BOP_simplifiedMeshFilter(meshC, facesA, &bspB, invertMeshB);
173         if ((0.25*facesA->size()) > bspB.getDeep())
174           BOP_meshFilter(meshC, facesA, &bspB);
175
176         BOP_simplifiedMeshFilter(meshC, facesB, &bspA, invertMeshA);
177         if ((0.25*facesB->size()) > bspA.getDeep())
178           BOP_meshFilter(meshC, facesB, &bspA);
179         
180         #ifdef BOP_DEBUG
181         c = chrono.stamp(); t += c;
182         cout << "mesh Filter    " << c << endl; 
183         #endif
184
185         // Face 2 Face
186         BOP_Face2Face(meshC,facesA,facesB);
187
188         #ifdef BOP_DEBUG
189         c = chrono.stamp(); t += c;
190         cout << "Face2Face      " << c << endl;
191         #endif
192
193         // BSP classification
194         BOP_meshClassify(meshC,facesA,&bspB);
195         BOP_meshClassify(meshC,facesB,&bspA);
196         
197         #ifdef BOP_DEBUG
198         c = chrono.stamp(); t += c;
199         cout << "Classification " << c << endl;
200         #endif
201         
202         // Process overlapped faces
203         BOP_removeOverlappedFaces(meshC,facesA,facesB);
204         
205         #ifdef BOP_DEBUG
206         c = chrono.stamp(); t += c;
207         cout << "Remove overlap " << c << endl;
208         #endif
209
210         // Sew two meshes
211         BOP_sew(meshC,facesA,facesB);
212
213         #ifdef BOP_DEBUG
214         c = chrono.stamp(); t += c;
215         cout << "Sew            " << c << endl;
216         #endif
217
218         // Merge faces
219 #ifdef BOP_ORIG_MERGE
220 #ifndef BOP_NEW_MERGE
221         BOP_Merge::getInstance().mergeFaces(meshC,numVertices);
222 #endif
223 #endif
224
225 #ifdef BOP_NEW_MERGE
226 #ifndef BOP_ORIG_MERGE
227         BOP_Merge2::getInstance().mergeFaces(meshC,numVertices);
228 #else
229         static int state = -1;
230         if (G.rt == 100) {
231                 if( state != 1 ) {
232                         cout << "Boolean code using old merge technique." << endl;
233                         state = 1;
234                 }
235                 BOP_Merge::getInstance().mergeFaces(meshC,numVertices);
236         } else {
237                 if( state != 0 ) {
238                         cout << "Boolean code using new merge technique." << endl;
239                         state = 0;
240                 }
241                 BOP_Merge2::getInstance().mergeFaces(meshC,numVertices);
242         }
243 #endif
244 #endif
245
246         #ifdef BOP_DEBUG
247         c = chrono.stamp(); t += c;
248         cout << "Merge faces    " << c << endl;
249         cout << "Total          " << t << endl;
250         // Test integrity
251         meshC->testMesh();
252         #endif
253         
254         return BOP_OK;
255 }
256
257 /**
258  * Preprocess to filter no collisioned faces.
259  * @param meshC Input & Output mesh data
260  * @param faces Faces list to test
261  * @param bsp BSP tree used to filter
262  */
263 void BOP_meshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp)
264 {
265         BOP_IT_Faces it;
266         BOP_TAG tag;
267         
268         it = faces->begin();
269         while (it!=faces->end()) {
270                 BOP_Face *face = *it;
271                 MT_Point3 p1 = meshC->getVertex(face->getVertex(0))->getPoint();
272                 MT_Point3 p2 = meshC->getVertex(face->getVertex(1))->getPoint();
273                 MT_Point3 p3 = meshC->getVertex(face->getVertex(2))->getPoint();
274                 if ((tag = bsp->classifyFace(p1,p2,p3,face->getPlane()))==OUT||tag==OUTON) {
275                         face->setTAG(BROKEN);
276                         it = faces->erase(it);
277                 }
278                 else if (tag == IN) {
279                         it = faces->erase(it);
280                 }else{
281                   it++;
282                 }
283         }
284 }
285
286 /**
287  * Pre-process to filter no collisioned faces.
288  * @param meshC Input & Output mesh data
289  * @param faces Faces list to test
290  * @param bsp BSP tree used to filter
291  * @param inverted determines if the object is inverted
292  */
293 void BOP_simplifiedMeshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp, bool inverted)
294 {
295         BOP_IT_Faces it;
296         
297         it = faces->begin();
298         while (it!=faces->end()) {
299                 BOP_Face *face = *it;
300                 MT_Point3 p1 = meshC->getVertex(face->getVertex(0))->getPoint();
301                 MT_Point3 p2 = meshC->getVertex(face->getVertex(1))->getPoint();
302                 MT_Point3 p3 = meshC->getVertex(face->getVertex(2))->getPoint();
303                 if (bsp->filterFace(p1,p2,p3,face)==OUT) {
304                         if (!inverted) face->setTAG(BROKEN);
305                         it = faces->erase(it);
306                 }
307                 else {
308                         it++;
309                 }
310         }
311 }
312
313 /**
314  * Process to classify the mesh faces using a bsp tree.
315  * @param meshC Input & Output mesh data
316  * @param faces Faces list to classify
317  * @param bsp BSP tree used to face classify
318  */
319 void BOP_meshClassify(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp)
320 {
321         for(BOP_IT_Faces face=faces->begin();face!=faces->end();face++) {
322                 if ((*face)->getTAG()!=BROKEN) {
323                         MT_Point3 p1 = meshC->getVertex((*face)->getVertex(0))->getPoint();
324                         MT_Point3 p2 = meshC->getVertex((*face)->getVertex(1))->getPoint();
325                         MT_Point3 p3 = meshC->getVertex((*face)->getVertex(2))->getPoint();
326                         if (bsp->simplifiedClassifyFace(p1,p2,p3,(*face)->getPlane())!=IN) {
327                                 (*face)->setTAG(BROKEN);
328                         }
329                 }
330         }
331 }
332
333 /**
334  * Returns a new mesh triangle.
335  * @param meshC Input & Output mesh data
336  * @param vertex1 first vertex of the new face
337  * @param vertex2 second vertex of the new face
338  * @param vertex3 third vertex of the new face
339  * @param origFace identifier of the new face
340  * @return new the new face
341  */
342 BOP_Face3 *BOP_createFace3(BOP_Mesh* mesh, 
343                                                    BOP_Index       vertex1, 
344                                                    BOP_Index       vertex2, 
345                                                    BOP_Index       vertex3, 
346                                                    BOP_Index       origFace)
347 {
348         MT_Point3 p1 = mesh->getVertex(vertex1)->getPoint();
349         MT_Point3 p2 = mesh->getVertex(vertex2)->getPoint();
350         MT_Point3 p3 = mesh->getVertex(vertex3)->getPoint();
351         MT_Plane3 plane(p1,p2,p3);
352
353         return new BOP_Face3(vertex1, vertex2, vertex3, plane, origFace);
354 }
355
356 /**
357  * Adds mesh information into destination mesh.
358  * @param mesh input/output mesh, destination for the new mesh data
359  * @param meshFacesId output mesh faces, contains an added faces list
360  * @param face_it faces iterator
361  * @param vertex_it vertices iterator
362  * @param inverted if TRUE adding inverted faces, non-inverted otherwise
363  */
364 void BOP_addMesh(BOP_Mesh*                     mesh,
365                                  BOP_Faces*                    meshFacesId,
366                                  CSG_FaceIteratorDescriptor&   face_it,
367                                  CSG_VertexIteratorDescriptor& vertex_it,
368                                  bool                          invert)
369 {
370         unsigned int vtxIndexOffset = mesh->getNumVertexs();
371
372         // The size of the vertex data array will be at least the number of faces.
373         CSG_IVertex vertex;
374         while (!vertex_it.Done(vertex_it.it)) {
375                 vertex_it.Fill(vertex_it.it,&vertex);
376                 MT_Point3 pos(vertex.position);
377                 mesh->addVertex(pos);
378                 vertex_it.Step(vertex_it.it);
379         }
380
381         CSG_IFace face;
382         
383         // now for the polygons.
384         // we may need to decalare some memory for user defined face properties.
385
386         BOP_Face3 *newface;
387         
388         while (!face_it.Done(face_it.it)) {
389                 face_it.Fill(face_it.it,&face);
390
391                 // Let's not rely on quads being coplanar - especially if they 
392                 // are coming out of that soup of code from blender...
393                 if (face.vertex_number == 4){
394                         // QUAD
395                         if (invert) {
396                                 newface = BOP_createFace3(mesh,
397                                                                                   face.vertex_index[2] + vtxIndexOffset,
398                                                                                   face.vertex_index[0] + vtxIndexOffset,
399                                                                                   face.vertex_index[3] + vtxIndexOffset,
400                                                                                   face.orig_face);
401                                 meshFacesId->push_back(newface);
402                                 mesh->addFace(newface);
403                                 newface = BOP_createFace3(mesh,
404                                                                                   face.vertex_index[2] + vtxIndexOffset,
405                                                                                   face.vertex_index[1] + vtxIndexOffset,
406                                                                                   face.vertex_index[0] + vtxIndexOffset,
407                                                                                   face.orig_face);
408                                 meshFacesId->push_back(newface);
409                                 mesh->addFace(newface);
410                         }
411                         else {
412                                 newface = BOP_createFace3(mesh,
413                                                                                  face.vertex_index[0] + vtxIndexOffset,
414                                                                                  face.vertex_index[2] + vtxIndexOffset,
415                                                                                  face.vertex_index[3] + vtxIndexOffset,
416                                                                                  face.orig_face);
417                                 meshFacesId->push_back(newface);
418                                 mesh->addFace(newface);
419                                 newface = BOP_createFace3(mesh,
420                                                                                  face.vertex_index[0] + vtxIndexOffset,
421                                                                                  face.vertex_index[1] + vtxIndexOffset,
422                                                                                  face.vertex_index[2] + vtxIndexOffset,
423                                                                                  face.orig_face);
424                                 meshFacesId->push_back(newface);
425                                 mesh->addFace(newface);
426                         }
427                 }
428                 else {
429                         // TRIANGLES
430                         if (invert) {
431                                 newface = BOP_createFace3(mesh,
432                                                                                   face.vertex_index[2] + vtxIndexOffset,
433                                                                                   face.vertex_index[1] + vtxIndexOffset,
434                                                                                   face.vertex_index[0] + vtxIndexOffset,
435                                                                                   face.orig_face);
436                                 meshFacesId->push_back(newface);
437                                 mesh->addFace(newface);
438                         }
439                         else {
440                                 newface = BOP_createFace3(mesh,
441                                                                                   face.vertex_index[0] + vtxIndexOffset,
442                                                                                   face.vertex_index[1] + vtxIndexOffset,
443                                                                                   face.vertex_index[2] + vtxIndexOffset,
444                                                                                   face.orig_face);
445                                 meshFacesId->push_back(newface);
446                                 mesh->addFace(newface);
447                         }
448                 }
449                 
450                 face_it.Step(face_it.it);
451         }
452 }
453
454 /**
455  * Returns an empty mesh with the specified properties.
456  * @return a new empty mesh
457  */
458 BSP_CSGMesh* BOP_newEmptyMesh()
459 {
460         BSP_CSGMesh* mesh = BSP_CSGMesh::New();
461         if (mesh == NULL) return mesh;
462
463         vector<BSP_MVertex>* vertices = new vector<BSP_MVertex>;
464         
465         mesh->SetVertices(vertices);
466
467         return mesh;
468 }
469
470 /**
471  * Exports a BOP_Mesh to a BSP_CSGMesh.
472  * @param mesh Input mesh
473  * @param invert if TRUE export with inverted faces, no inverted otherwise
474  * @return the corresponding new BSP_CSGMesh
475  */
476 BSP_CSGMesh* BOP_exportMesh(BOP_Mesh*                  mesh, 
477                                                         bool                       invert)
478 {
479         BSP_CSGMesh* outputMesh = BOP_newEmptyMesh();
480
481         if (outputMesh == NULL) return NULL;
482
483         // vtx index dictionary, to translate indeces from input to output.
484         map<int,unsigned int> dic;
485         map<int,unsigned int>::iterator itDic;
486
487         unsigned int count = 0;
488
489         // Add a new face for each face in the input list
490         BOP_Faces faces = mesh->getFaces();
491         BOP_Vertexs vertexs = mesh->getVertexs();
492
493         for (BOP_IT_Faces face = faces.begin(); face != faces.end(); face++) {
494                 if ((*face)->getTAG()!=BROKEN){    
495                         // Add output face
496                         outputMesh->FaceSet().push_back(BSP_MFace());
497                         BSP_MFace& outFace = outputMesh->FaceSet().back();
498
499                         // Copy face
500                         outFace.m_verts.clear();
501                         outFace.m_plane = (*face)->getPlane();
502                         outFace.m_orig_face = (*face)->getOriginalFace();
503
504                         // invert face if is required
505                         if (invert) (*face)->invert();
506                         
507                         // Add the face vertex if not added yet
508                         for (unsigned int pos=0;pos<(*face)->size();pos++) {
509                                 BSP_VertexInd outVtxId;
510                                 BOP_Index idVertex = (*face)->getVertex(pos);
511                                 itDic = dic.find(idVertex);
512                                 if (itDic == dic.end()) {
513                                         // The vertex isn't added yet
514                                         outVtxId = BSP_VertexInd(outputMesh->VertexSet().size());
515                                         BSP_MVertex outVtx((mesh->getVertex(idVertex))->getPoint());
516                                         outVtx.m_edges.clear();
517                                         outputMesh->VertexSet().push_back(outVtx);
518                                         dic[idVertex] = outVtxId;
519                                         count++;
520                                 }
521                                 else {
522                                         // The vertex is added
523                                         outVtxId = BSP_VertexInd(itDic->second);
524                                 }
525
526                                 outFace.m_verts.push_back(outVtxId);
527                         }
528                 }
529         }
530         
531         // Build the mesh edges using topological informtion
532         outputMesh->BuildEdges();
533         
534         return outputMesh;
535 }