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