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