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