merge with trunk at r27259 and commit of a patch by anthony jones to fix msvc (though...
[blender-staging.git] / source / blender / blenkernel / intern / booleanops.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) Blender Foundation
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  * CSG operations. 
29  */
30
31 #include <string.h>
32 #include <math.h>
33
34 #include "MEM_guardedalloc.h"
35
36 #include "BLI_math.h"
37 #include "BLI_blenlib.h"
38 #include "BLI_ghash.h"
39
40 #include "DNA_material_types.h"
41 #include "DNA_mesh_types.h"
42 #include "DNA_meshdata_types.h"
43 #include "DNA_object_types.h"
44 #include "DNA_scene_types.h"
45
46 #include "CSG_BooleanOps.h"
47
48 #include "BKE_booleanops.h"
49 #include "BKE_cdderivedmesh.h"
50 #include "BKE_customdata.h"
51 #include "BKE_depsgraph.h"
52 #include "BKE_DerivedMesh.h"
53 #include "BKE_global.h"
54 #include "BKE_library.h"
55 #include "BKE_material.h"
56 #include "BKE_mesh.h"
57 #include "BKE_object.h"
58 #include "BKE_utildefines.h"
59
60
61
62 /**
63  * Here's the vertex iterator structure used to walk through
64  * the blender vertex structure.
65  */
66
67 typedef struct {
68         DerivedMesh *dm;
69         Object *ob;
70         int pos;
71 } VertexIt;
72
73 /**
74  * Implementations of local vertex iterator functions.
75  * These describe a blender mesh to the CSG module.
76  */
77
78 static void VertexIt_Destruct(CSG_VertexIteratorDescriptor * iterator)
79 {
80         if (iterator->it) {
81                 // deallocate memory for iterator
82                 MEM_freeN(iterator->it);
83                 iterator->it = 0;
84         }
85         iterator->Done = NULL;
86         iterator->Fill = NULL;
87         iterator->Reset = NULL;
88         iterator->Step = NULL;
89         iterator->num_elements = 0;
90
91 }               
92
93 static int VertexIt_Done(CSG_IteratorPtr it)
94 {
95         VertexIt * iterator = (VertexIt *)it;
96         return(iterator->pos >= iterator->dm->getNumVerts(iterator->dm));
97 }
98
99 static void VertexIt_Fill(CSG_IteratorPtr it, CSG_IVertex *vert)
100 {
101         VertexIt * iterator = (VertexIt *)it;
102         MVert *verts = iterator->dm->getVertArray(iterator->dm);
103
104         float global_pos[3];
105
106         /* boolean happens in global space, transform both with obmat */
107         mul_v3_m4v3(
108                 global_pos,
109                 iterator->ob->obmat, 
110                 verts[iterator->pos].co
111         );
112
113         vert->position[0] = global_pos[0];
114         vert->position[1] = global_pos[1];
115         vert->position[2] = global_pos[2];
116 }
117
118 static void VertexIt_Step(CSG_IteratorPtr it)
119 {
120         VertexIt * iterator = (VertexIt *)it;
121         iterator->pos ++;
122
123  
124 static void VertexIt_Reset(CSG_IteratorPtr it)
125 {
126         VertexIt * iterator = (VertexIt *)it;
127         iterator->pos = 0;
128 }
129
130 static void VertexIt_Construct(CSG_VertexIteratorDescriptor *output, DerivedMesh *dm, Object *ob)
131 {
132
133         VertexIt *it;
134         if (output == 0) return;
135
136         // allocate some memory for blender iterator
137         it = (VertexIt *)(MEM_mallocN(sizeof(VertexIt),"Boolean_VIt"));
138         if (it == 0) {
139                 return;
140         }
141         // assign blender specific variables
142         it->dm = dm;
143         it->ob = ob; // needed for obmat transformations 
144         
145         it->pos = 0;
146
147         // assign iterator function pointers.
148         output->Step = VertexIt_Step;
149         output->Fill = VertexIt_Fill;
150         output->Done = VertexIt_Done;
151         output->Reset = VertexIt_Reset;
152         output->num_elements = it->dm->getNumVerts(it->dm);
153         output->it = it;
154 }
155
156 /**
157  * Blender Face iterator
158  */
159
160 typedef struct {
161         DerivedMesh *dm;
162         int pos;
163         int offset;
164         int flip;
165 } FaceIt;
166
167 static void FaceIt_Destruct(CSG_FaceIteratorDescriptor * iterator)
168 {
169         MEM_freeN(iterator->it);
170         iterator->Done = NULL;
171         iterator->Fill = NULL;
172         iterator->Reset = NULL;
173         iterator->Step = NULL;
174         iterator->num_elements = 0;
175 }
176
177 static int FaceIt_Done(CSG_IteratorPtr it)
178 {
179         // assume CSG_IteratorPtr is of the correct type.
180         FaceIt * iterator = (FaceIt *)it;
181         return(iterator->pos >= iterator->dm->getNumTessFaces(iterator->dm));
182 }
183
184 static void FaceIt_Fill(CSG_IteratorPtr it, CSG_IFace *face)
185 {
186         // assume CSG_IteratorPtr is of the correct type.
187         FaceIt *face_it = (FaceIt *)it;
188         MFace *mfaces = face_it->dm->getTessFaceArray(face_it->dm);
189         MFace *mface = &mfaces[face_it->pos];
190
191         /* reverse face vertices if necessary */
192         face->vertex_index[1] = mface->v2;
193         if( face_it->flip == 0 ) {
194         face->vertex_index[0] = mface->v1;
195         face->vertex_index[2] = mface->v3;
196         } else {
197                 face->vertex_index[2] = mface->v1;
198                 face->vertex_index[0] = mface->v3;
199         }
200         if (mface->v4) {
201                 face->vertex_index[3] = mface->v4;
202                 face->vertex_number = 4;
203         } else {
204                 face->vertex_number = 3;
205         }
206
207         face->orig_face = face_it->offset + face_it->pos;
208 }
209
210 static void FaceIt_Step(CSG_IteratorPtr it)
211 {
212         FaceIt * face_it = (FaceIt *)it;                
213         face_it->pos ++;
214 }
215
216 static void FaceIt_Reset(CSG_IteratorPtr it)
217 {
218         FaceIt * face_it = (FaceIt *)it;                
219         face_it->pos = 0;
220 }       
221
222 static void FaceIt_Construct(
223         CSG_FaceIteratorDescriptor *output, DerivedMesh *dm, int offset, Object *ob)
224 {
225         FaceIt *it;
226         if (output == 0) return;
227
228         // allocate some memory for blender iterator
229         it = (FaceIt *)(MEM_mallocN(sizeof(FaceIt),"Boolean_FIt"));
230         if (it == 0) {
231                 return ;
232         }
233         // assign blender specific variables
234         it->dm = dm;
235         it->offset = offset;
236         it->pos = 0;
237
238         /* determine if we will need to reverse order of face vertices */
239         if (ob->size[0] < 0.0f) {
240                 if (ob->size[1] < 0.0f && ob->size[2] < 0.0f) {
241                         it->flip = 1;
242                 } else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) {
243                         it->flip = 1;
244                 } else {
245                         it->flip = 0;
246                 }
247         } else {
248                 if (ob->size[1] < 0.0f && ob->size[2] < 0.0f) {
249                         it->flip = 0;
250                 } else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) {
251                         it->flip = 0;
252                 } else {
253                         it->flip = 1;
254                 }
255         }
256
257         // assign iterator function pointers.
258         output->Step = FaceIt_Step;
259         output->Fill = FaceIt_Fill;
260         output->Done = FaceIt_Done;
261         output->Reset = FaceIt_Reset;
262         output->num_elements = it->dm->getNumTessFaces(it->dm);
263         output->it = it;
264 }
265
266 static Object *AddNewBlenderMesh(Scene *scene, Base *base)
267 {
268         // This little function adds a new mesh object to the blender object list
269         // It uses ob to duplicate data as this seems to be easier than creating
270         // a new one. This new oject contains no faces nor vertices.
271         Mesh *old_me;
272         Base *basen;
273         Object *ob_new;
274
275         // now create a new blender object.
276         // duplicating all the settings from the previous object
277         // to the new one.
278         ob_new= copy_object(base->object);
279
280         // Ok we don't want to use the actual data from the
281         // last object, the above function incremented the 
282         // number of users, so decrement it here.
283         old_me= ob_new->data;
284         old_me->id.us--;
285
286         // Now create a new base to add into the linked list of 
287         // vase objects.
288         
289         basen= MEM_mallocN(sizeof(Base), "duplibase");
290         *basen= *base;
291         BLI_addhead(&scene->base, basen);       /* addhead: anders oneindige lus */
292         basen->object= ob_new;
293         basen->flag &= ~SELECT;
294                                 
295         // Initialize the mesh data associated with this object.                                                
296         ob_new->data= add_mesh("Mesh");
297
298         // Finally assign the object type.
299         ob_new->type= OB_MESH;
300
301         return ob_new;
302 }
303
304 static void InterpCSGFace(
305         DerivedMesh *dm, DerivedMesh *orig_dm, int index, int orig_index, int nr,
306         float mapmat[][4])
307 {
308         float obco[3], *co[4], *orig_co[4], w[4][4];
309         MFace *mface, *orig_mface;
310         int j;
311
312         mface = CDDM_get_tessface(dm, index);
313         orig_mface = orig_dm->getTessFaceArray(orig_dm) + orig_index;
314
315         // get the vertex coordinates from the original mesh
316         orig_co[0] = (orig_dm->getVertArray(orig_dm) + orig_mface->v1)->co;
317         orig_co[1] = (orig_dm->getVertArray(orig_dm) + orig_mface->v2)->co;
318         orig_co[2] = (orig_dm->getVertArray(orig_dm) + orig_mface->v3)->co;
319         orig_co[3] = (orig_mface->v4)? (orig_dm->getVertArray(orig_dm) + orig_mface->v4)->co: NULL;
320
321         // get the vertex coordinates from the new derivedmesh
322         co[0] = CDDM_get_vert(dm, mface->v1)->co;
323         co[1] = CDDM_get_vert(dm, mface->v2)->co;
324         co[2] = CDDM_get_vert(dm, mface->v3)->co;
325         co[3] = (nr == 4)? CDDM_get_vert(dm, mface->v4)->co: NULL;
326
327         for (j = 0; j < nr; j++) {
328                 // get coordinate into the space of the original mesh
329                 if (mapmat)
330                         mul_v3_m4v3(obco, mapmat, co[j]);
331                 else
332                         copy_v3_v3(obco, co[j]);
333
334                 interp_weights_face_v3( w[j],orig_co[0], orig_co[1], orig_co[2], orig_co[3], obco);
335         }
336
337         CustomData_interp(&orig_dm->faceData, &dm->faceData, &orig_index, NULL, (float*)w, 1, index);
338 }
339
340 /* Iterate over the CSG Output Descriptors and create a new DerivedMesh
341    from them */
342 static DerivedMesh *ConvertCSGDescriptorsToDerivedMesh(
343         CSG_FaceIteratorDescriptor *face_it,
344         CSG_VertexIteratorDescriptor *vertex_it,
345         float parinv[][4],
346         float mapmat[][4],
347         Material **mat,
348         int *totmat,
349         DerivedMesh *dm1,
350         Object *ob1,
351         DerivedMesh *dm2,
352         Object *ob2)
353 {
354         DerivedMesh *result, *orig_dm;
355         GHash *material_hash = NULL;
356         Mesh *me1= (Mesh*)ob1->data;
357         Mesh *me2= (Mesh*)ob2->data;
358         int i;
359
360         // create a new DerivedMesh
361         result = CDDM_new(vertex_it->num_elements, 0, face_it->num_elements, 0, 0);
362         CustomData_merge(&dm1->faceData, &result->faceData, CD_MASK_DERIVEDMESH,
363                           CD_DEFAULT, face_it->num_elements); 
364         CustomData_merge(&dm2->faceData, &result->faceData, CD_MASK_DERIVEDMESH,
365                           CD_DEFAULT, face_it->num_elements); 
366
367         // step through the vertex iterators:
368         for (i = 0; !vertex_it->Done(vertex_it->it); i++) {
369                 CSG_IVertex csgvert;
370                 MVert *mvert = CDDM_get_vert(result, i);
371
372                 // retrieve a csg vertex from the boolean module
373                 vertex_it->Fill(vertex_it->it, &csgvert);
374                 vertex_it->Step(vertex_it->it);
375
376                 // we have to map the vertex coordinates back in the coordinate frame
377                 // of the resulting object, since it was computed in world space
378                 mul_v3_m4v3(mvert->co, parinv, csgvert.position);
379         }
380
381         // a hash table to remap materials to indices
382         if (mat) {
383                 material_hash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
384                 *totmat = 0;
385         }
386
387         // step through the face iterators
388         for(i = 0; !face_it->Done(face_it->it); i++) {
389                 Mesh *orig_me;
390                 Object *orig_ob;
391                 Material *orig_mat;
392                 CSG_IFace csgface;
393                 MFace *mface;
394                 int orig_index, mat_nr;
395
396                 // retrieve a csg face from the boolean module
397                 face_it->Fill(face_it->it, &csgface);
398                 face_it->Step(face_it->it);
399
400                 // find the original mesh and data
401                 orig_ob = (csgface.orig_face < dm1->getNumTessFaces(dm1))? ob1: ob2;
402                 orig_dm = (csgface.orig_face < dm1->getNumTessFaces(dm1))? dm1: dm2;
403                 orig_me = (orig_ob == ob1)? me1: me2;
404                 orig_index = (orig_ob == ob1)? csgface.orig_face: csgface.orig_face - dm1->getNumTessFaces(dm1);
405
406                 // copy all face layers, including mface
407                 CustomData_copy_data(&orig_dm->faceData, &result->faceData, orig_index, i, 1);
408
409                 // set mface
410                 mface = CDDM_get_tessface(result, i);
411                 mface->v1 = csgface.vertex_index[0];
412                 mface->v2 = csgface.vertex_index[1];
413                 mface->v3 = csgface.vertex_index[2];
414                 mface->v4 = (csgface.vertex_number == 4)? csgface.vertex_index[3]: 0;
415
416                 // set material, based on lookup in hash table
417                 orig_mat= give_current_material(orig_ob, mface->mat_nr+1);
418
419                 if (mat && orig_mat) {
420                         if (!BLI_ghash_haskey(material_hash, orig_mat)) {
421                                 mat[*totmat] = orig_mat;
422                                 mat_nr = mface->mat_nr = (*totmat)++;
423                                 BLI_ghash_insert(material_hash, orig_mat, SET_INT_IN_POINTER(mat_nr));
424                         }
425                         else
426                                 mface->mat_nr = GET_INT_FROM_POINTER(BLI_ghash_lookup(material_hash, orig_mat));
427                 }
428                 else
429                         mface->mat_nr = 0;
430
431                 InterpCSGFace(result, orig_dm, i, orig_index, csgface.vertex_number,
432                               (orig_me == me2)? mapmat: NULL);
433
434                 test_index_face(mface, &result->faceData, i, csgface.vertex_number);
435         }
436
437         if (material_hash)
438                 BLI_ghash_free(material_hash, NULL, NULL);
439
440         CDDM_calc_edges(result);
441         CDDM_calc_normals(result);
442
443         CDDM_tessfaces_to_faces(result);
444
445         return result;
446 }
447         
448 static void BuildMeshDescriptors(
449         struct DerivedMesh *dm,
450         struct Object *ob,
451         int face_offset,
452         struct CSG_FaceIteratorDescriptor * face_it,
453         struct CSG_VertexIteratorDescriptor * vertex_it)
454 {
455         VertexIt_Construct(vertex_it,dm, ob);
456         FaceIt_Construct(face_it,dm,face_offset,ob);
457 }
458         
459 static void FreeMeshDescriptors(
460         struct CSG_FaceIteratorDescriptor *face_it,
461         struct CSG_VertexIteratorDescriptor *vertex_it)
462 {
463         VertexIt_Destruct(vertex_it);
464         FaceIt_Destruct(face_it);
465 }
466
467 DerivedMesh *NewBooleanDerivedMesh_intern(
468         DerivedMesh *dm, struct Object *ob, DerivedMesh *dm_select, struct Object *ob_select,
469         int int_op_type, Material **mat, int *totmat)
470 {
471
472         float inv_mat[4][4];
473         float map_mat[4][4];
474
475         DerivedMesh *result = NULL;
476
477         if (dm == NULL || dm_select == NULL) return 0;
478         if (!dm->getNumTessFaces(dm) || !dm_select->getNumTessFaces(dm_select)) return 0;
479
480         // we map the final object back into ob's local coordinate space. For this
481         // we need to compute the inverse transform from global to ob (inv_mat),
482         // and the transform from ob to ob_select for use in interpolation (map_mat)
483         invert_m4_m4(inv_mat, ob->obmat);
484         mul_m4_m4m4(map_mat, ob_select->obmat, inv_mat);
485         invert_m4_m4(inv_mat, ob_select->obmat);
486
487         {
488                 // interface with the boolean module:
489                 //
490                 // the idea is, we pass the boolean module verts and faces using the
491                 // provided descriptors. once the boolean operation is performed, we
492                 // get back output descriptors, from which we then build a DerivedMesh
493
494                 CSG_VertexIteratorDescriptor vd_1, vd_2;
495                 CSG_FaceIteratorDescriptor fd_1, fd_2;
496                 CSG_OperationType op_type;
497                 CSG_BooleanOperation *bool_op;
498
499                 // work out the operation they chose and pick the appropriate 
500                 // enum from the csg module.
501                 switch (int_op_type) {
502                         case 1 : op_type = e_csg_intersection; break;
503                         case 2 : op_type = e_csg_union; break;
504                         case 3 : op_type = e_csg_difference; break;
505                         case 4 : op_type = e_csg_classify; break;
506                         default : op_type = e_csg_intersection;
507                 }
508                 
509                 BuildMeshDescriptors(dm_select, ob_select, 0, &fd_1, &vd_1);
510                 BuildMeshDescriptors(dm, ob, dm_select->getNumTessFaces(dm_select) , &fd_2, &vd_2);
511
512                 bool_op = CSG_NewBooleanFunction();
513
514                 // perform the operation
515                 if (CSG_PerformBooleanOperation(bool_op, op_type, fd_1, vd_1, fd_2, vd_2)) {
516                         CSG_VertexIteratorDescriptor vd_o;
517                         CSG_FaceIteratorDescriptor fd_o;
518
519                         CSG_OutputFaceDescriptor(bool_op, &fd_o);
520                         CSG_OutputVertexDescriptor(bool_op, &vd_o);
521
522                         // iterate through results of operation and insert
523                         // into new object
524                         result = ConvertCSGDescriptorsToDerivedMesh(
525                                 &fd_o, &vd_o, inv_mat, map_mat, mat, totmat, dm_select, ob_select, dm, ob);
526
527                         // free up the memory
528                         CSG_FreeVertexDescriptor(&vd_o);
529                         CSG_FreeFaceDescriptor(&fd_o);
530                 }
531                 else
532                         printf("Unknown internal error in boolean");
533
534                 CSG_FreeBooleanOperation(bool_op);
535
536                 FreeMeshDescriptors(&fd_1, &vd_1);
537                 FreeMeshDescriptors(&fd_2, &vd_2);
538         }
539
540         return result;
541 }
542
543 int NewBooleanMesh(Scene *scene, Base *base, Base *base_select, int int_op_type)
544 {
545         Mesh *me_new;
546         int a, maxmat, totmat= 0;
547         Object *ob_new, *ob, *ob_select;
548         Material **mat;
549         DerivedMesh *result;
550         DerivedMesh *dm_select;
551         DerivedMesh *dm;
552
553         ob= base->object;
554         ob_select= base_select->object;
555
556         dm = mesh_get_derived_final(scene, ob, CD_MASK_BAREMESH);
557         dm_select = mesh_create_derived_view(scene, ob_select, 0); // no modifiers in editmode ??
558
559         maxmat= ob->totcol + ob_select->totcol;
560         mat= (Material**)MEM_mallocN(sizeof(Material*)*maxmat, "NewBooleanMeshMat");
561         
562         /* put some checks in for nice user feedback */
563         if (dm == NULL || dm_select == NULL) return 0;
564         if (!dm->getNumTessFaces(dm) || !dm_select->getNumTessFaces(dm_select))
565         {
566                 MEM_freeN(mat);
567                 return -1;
568         }
569         
570         result= NewBooleanDerivedMesh_intern(dm, ob, dm_select, ob_select, int_op_type, mat, &totmat);
571
572         if (result == NULL) {
573                 MEM_freeN(mat);
574                 return 0;
575         }
576
577         /* create a new blender mesh object - using 'base' as  a template */
578         ob_new= AddNewBlenderMesh(scene, base_select);
579         me_new= ob_new->data;
580
581         DM_to_mesh(result, me_new);
582         result->release(result);
583
584         dm->release(dm);
585         dm_select->release(dm_select);
586
587         /* add materials to object */
588         for (a = 0; a < totmat; a++)
589                 assign_material(ob_new, mat[a], a+1);
590
591         MEM_freeN(mat);
592
593         /* update dag */
594         DAG_id_flush_update(&ob_new->id, OB_RECALC_DATA);
595
596         return 1;
597 }
598
599 DerivedMesh *NewBooleanDerivedMesh(DerivedMesh *dm, struct Object *ob, DerivedMesh *dm_select, struct Object *ob_select,
600                                    int int_op_type)
601 {
602         return NewBooleanDerivedMesh_intern(dm, ob, dm_select, ob_select, int_op_type, NULL, NULL);
603 }
604