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