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