Fix #34040: Moving Normal Node with enabled Cycles Material Preview crashes
[blender.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_global.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         }
193         else {
194                 face->vertex_index[2] = mface->v1;
195                 face->vertex_index[0] = mface->v3;
196         }
197         if (mface->v4) {
198                 face->vertex_index[3] = mface->v4;
199                 face->vertex_number = 4;
200         }
201         else {
202                 face->vertex_number = 3;
203         }
204
205         face->orig_face = face_it->offset + face_it->pos;
206 }
207
208 static void FaceIt_Step(CSG_IteratorPtr it)
209 {
210         FaceIt *face_it = (FaceIt *)it;
211         face_it->pos++;
212 }
213
214 static void FaceIt_Reset(CSG_IteratorPtr it)
215 {
216         FaceIt *face_it = (FaceIt *)it;
217         face_it->pos = 0;
218 }       
219
220 static void FaceIt_Construct(
221         CSG_FaceIteratorDescriptor *output, DerivedMesh *dm, int offset, Object *ob)
222 {
223         FaceIt *it;
224         if (output == 0) return;
225
226         /* allocate some memory for blender iterator */
227         it = (FaceIt *)(MEM_mallocN(sizeof(FaceIt), "Boolean_FIt"));
228         if (it == 0) {
229                 return;
230         }
231         /* assign blender specific variables */
232         it->dm = dm;
233         it->offset = offset;
234         it->pos = 0;
235
236         /* determine if we will need to reverse order of face vertices */
237         if (ob->size[0] < 0.0f) {
238                 if (ob->size[1] < 0.0f && ob->size[2] < 0.0f) {
239                         it->flip = 1;
240                 }
241                 else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) {
242                         it->flip = 1;
243                 }
244                 else {
245                         it->flip = 0;
246                 }
247         }
248         else {
249                 if (ob->size[1] < 0.0f && ob->size[2] < 0.0f) {
250                         it->flip = 0;
251                 }
252                 else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) {
253                         it->flip = 0;
254                 }
255                 else {
256                         it->flip = 1;
257                 }
258         }
259
260         /* assign iterator function pointers. */
261         output->Step = FaceIt_Step;
262         output->Fill = FaceIt_Fill;
263         output->Done = FaceIt_Done;
264         output->Reset = FaceIt_Reset;
265         output->num_elements = it->dm->getNumTessFaces(it->dm);
266         output->it = it;
267 }
268
269 static Object *AddNewBlenderMesh(Scene *scene, Base *base)
270 {
271         /* This little function adds a new mesh object to the blender object list
272          * It uses ob to duplicate data as this seems to be easier than creating
273          * a new one. This new oject contains no faces nor vertices. */
274         Mesh *old_me;
275         Base *basen;
276         Object *ob_new;
277
278         /* now create a new blender object.
279          * duplicating all the settings from the previous object
280          * to the new one. */
281         ob_new = BKE_object_copy(base->object);
282
283         /* Ok we don't want to use the actual data from the
284          * last object, the above function incremented the
285          * number of users, so decrement it here. */
286         old_me = ob_new->data;
287         old_me->id.us--;
288
289         /* Now create a new base to add into the linked list of
290          * vase objects. */
291
292         basen = MEM_mallocN(sizeof(Base), "duplibase");
293         *basen = *base;
294         BLI_addhead(&scene->base, basen);   /* addhead: anders oneindige lus */
295         basen->object = ob_new;
296         basen->flag &= ~SELECT;
297                                 
298         /* Initialize the mesh data associated with this object. */
299         ob_new->data = BKE_mesh_add(G.main, "Mesh");
300
301         /* Finally assign the object type. */
302         ob_new->type = OB_MESH;
303
304         return ob_new;
305 }
306
307 static void InterpCSGFace(
308         DerivedMesh *dm, DerivedMesh *orig_dm, int index, int orig_index, int nr,
309         float mapmat[4][4])
310 {
311         float obco[3], *co[4], *orig_co[4], w[4][4];
312         MFace *mface, *orig_mface;
313         int j;
314
315         mface = CDDM_get_tessface(dm, index);
316         orig_mface = orig_dm->getTessFaceArray(orig_dm) + orig_index;
317
318         /* get the vertex coordinates from the original mesh */
319         orig_co[0] = (orig_dm->getVertArray(orig_dm) + orig_mface->v1)->co;
320         orig_co[1] = (orig_dm->getVertArray(orig_dm) + orig_mface->v2)->co;
321         orig_co[2] = (orig_dm->getVertArray(orig_dm) + orig_mface->v3)->co;
322         orig_co[3] = (orig_mface->v4) ? (orig_dm->getVertArray(orig_dm) + orig_mface->v4)->co : NULL;
323
324         /* get the vertex coordinates from the new derivedmesh */
325         co[0] = CDDM_get_vert(dm, mface->v1)->co;
326         co[1] = CDDM_get_vert(dm, mface->v2)->co;
327         co[2] = CDDM_get_vert(dm, mface->v3)->co;
328         co[3] = (nr == 4) ? CDDM_get_vert(dm, mface->v4)->co : NULL;
329
330         for (j = 0; j < nr; j++) {
331                 /* get coordinate into the space of the original mesh */
332                 if (mapmat)
333                         mul_v3_m4v3(obco, mapmat, co[j]);
334                 else
335                         copy_v3_v3(obco, co[j]);
336
337                 interp_weights_face_v3(w[j], orig_co[0], orig_co[1], orig_co[2], orig_co[3], obco);
338         }
339
340         CustomData_interp(&orig_dm->faceData, &dm->faceData, &orig_index, NULL, (float *)w, 1, index);
341 }
342
343 /* Iterate over the CSG Output Descriptors and create a new DerivedMesh
344  * from them */
345 static DerivedMesh *ConvertCSGDescriptorsToDerivedMesh(
346         CSG_FaceIteratorDescriptor *face_it,
347         CSG_VertexIteratorDescriptor *vertex_it,
348         float parinv[4][4],
349         float mapmat[4][4],
350         Material **mat,
351         int *totmat,
352         DerivedMesh *dm1,
353         Object *ob1,
354         DerivedMesh *dm2,
355         Object *ob2)
356 {
357         DerivedMesh *result, *orig_dm;
358         GHash *material_hash = NULL;
359         Mesh *me1 = (Mesh *)ob1->data;
360         Mesh *me2 = (Mesh *)ob2->data;
361         int i, *origindex_layer;
362
363         /* create a new DerivedMesh */
364         result = CDDM_new(vertex_it->num_elements, 0, face_it->num_elements, 0, 0);
365         CustomData_merge(&dm1->faceData, &result->faceData, CD_MASK_DERIVEDMESH & ~(CD_MASK_NORMAL | CD_MASK_ORIGINDEX),
366                          CD_DEFAULT, face_it->num_elements);
367         CustomData_merge(&dm2->faceData, &result->faceData, CD_MASK_DERIVEDMESH & ~(CD_MASK_NORMAL | CD_MASK_ORIGINDEX),
368                          CD_DEFAULT, face_it->num_elements);
369
370         /* step through the vertex iterators: */
371         for (i = 0; !vertex_it->Done(vertex_it->it); i++) {
372                 CSG_IVertex csgvert;
373                 MVert *mvert = CDDM_get_vert(result, i);
374
375                 /* retrieve a csg vertex from the boolean module */
376                 vertex_it->Fill(vertex_it->it, &csgvert);
377                 vertex_it->Step(vertex_it->it);
378
379                 /* we have to map the vertex coordinates back in the coordinate frame
380                  * of the resulting object, since it was computed in world space */
381                 mul_v3_m4v3(mvert->co, parinv, csgvert.position);
382         }
383
384         /* a hash table to remap materials to indices */
385         material_hash = BLI_ghash_ptr_new("CSG_mat gh");
386
387         if (mat)
388                 *totmat = 0;
389
390         origindex_layer = result->getTessFaceDataArray(result, CD_ORIGINDEX);
391
392         /* step through the face iterators */
393         for (i = 0; !face_it->Done(face_it->it); i++) {
394                 Mesh *orig_me;
395                 Object *orig_ob;
396                 Material *orig_mat;
397                 CSG_IFace csgface;
398                 MFace *mface;
399                 int orig_index, mat_nr;
400
401                 /* retrieve a csg face from the boolean module */
402                 face_it->Fill(face_it->it, &csgface);
403                 face_it->Step(face_it->it);
404
405                 /* find the original mesh and data */
406                 orig_ob = (csgface.orig_face < dm1->getNumTessFaces(dm1)) ? ob1 : ob2;
407                 orig_dm = (csgface.orig_face < dm1->getNumTessFaces(dm1)) ? dm1 : dm2;
408                 orig_me = (orig_ob == ob1) ? me1 : me2;
409                 orig_index = (orig_ob == ob1) ? csgface.orig_face : csgface.orig_face - dm1->getNumTessFaces(dm1);
410
411                 /* copy all face layers, including mface */
412                 CustomData_copy_data(&orig_dm->faceData, &result->faceData, orig_index, i, 1);
413
414                 /* set mface */
415                 mface = CDDM_get_tessface(result, i);
416                 mface->v1 = csgface.vertex_index[0];
417                 mface->v2 = csgface.vertex_index[1];
418                 mface->v3 = csgface.vertex_index[2];
419                 mface->v4 = (csgface.vertex_number == 4) ? csgface.vertex_index[3] : 0;
420
421                 /* set material, based on lookup in hash table */
422                 orig_mat = give_current_material(orig_ob, mface->mat_nr + 1);
423
424                 if (mat && orig_mat) {
425                         if (!BLI_ghash_haskey(material_hash, orig_mat)) {
426                                 mat[*totmat] = orig_mat;
427                                 mat_nr = mface->mat_nr = (*totmat)++;
428                                 BLI_ghash_insert(material_hash, orig_mat, SET_INT_IN_POINTER(mat_nr));
429                         }
430                         else
431                                 mface->mat_nr = GET_INT_FROM_POINTER(BLI_ghash_lookup(material_hash, orig_mat));
432                 }
433                 else if (orig_mat) {
434                         if (orig_ob == ob1) {
435                                 /* No need to change materian index for faces from left operand */
436                         }
437                         else {
438                                 /* for faces from right operand checn if there's needed material in left operand and if it is,
439                                  * use index of that material, otherwise fallback to first material (material with index=0) */
440                                 if (!BLI_ghash_haskey(material_hash, orig_mat)) {
441                                         int a;
442
443                                         mat_nr = 0;
444                                         for (a = 0; a < ob1->totcol; a++) {
445                                                 if (give_current_material(ob1, a + 1) == orig_mat) {
446                                                         mat_nr = a;
447                                                         break;
448                                                 }
449                                         }
450
451                                         BLI_ghash_insert(material_hash, orig_mat, SET_INT_IN_POINTER(mat_nr));
452
453                                         mface->mat_nr = mat_nr;
454                                 }
455                                 else
456                                         mface->mat_nr = GET_INT_FROM_POINTER(BLI_ghash_lookup(material_hash, orig_mat));
457                         }
458                 }
459                 else
460                         mface->mat_nr = 0;
461
462                 InterpCSGFace(result, orig_dm, i, orig_index, csgface.vertex_number,
463                               (orig_me == me2) ? mapmat : NULL);
464
465                 test_index_face(mface, &result->faceData, i, csgface.vertex_number);
466
467                 if (origindex_layer && orig_ob == ob2)
468                         origindex_layer[i] = ORIGINDEX_NONE;
469         }
470
471         if (material_hash)
472                 BLI_ghash_free(material_hash, NULL, NULL);
473
474         CDDM_calc_edges_tessface(result);
475
476         CDDM_tessfaces_to_faces(result); /*builds ngon faces from tess (mface) faces*/
477
478         /* this fixes shading issues but SHOULD NOT.
479          * TODO, find out why face normals are wrong & flicker - campbell */
480 #if 0
481         DM_debug_print(result);
482
483         CustomData_free(&result->faceData, result->numTessFaceData);
484         result->numTessFaceData = 0;
485         DM_ensure_tessface(result);
486 #endif
487
488         CDDM_calc_normals(result);
489
490         return result;
491 }
492         
493 static void BuildMeshDescriptors(
494         struct DerivedMesh *dm,
495         struct Object *ob,
496         int face_offset,
497         struct CSG_FaceIteratorDescriptor *face_it,
498         struct CSG_VertexIteratorDescriptor *vertex_it)
499 {
500         VertexIt_Construct(vertex_it, dm, ob);
501         FaceIt_Construct(face_it, dm, face_offset, ob);
502 }
503         
504 static void FreeMeshDescriptors(
505         struct CSG_FaceIteratorDescriptor *face_it,
506         struct CSG_VertexIteratorDescriptor *vertex_it)
507 {
508         VertexIt_Destruct(vertex_it);
509         FaceIt_Destruct(face_it);
510 }
511
512 static DerivedMesh *NewBooleanDerivedMesh_intern(
513         DerivedMesh *dm, struct Object *ob, DerivedMesh *dm_select, struct Object *ob_select,
514         int int_op_type, Material **mat, int *totmat)
515 {
516
517         float inv_mat[4][4];
518         float map_mat[4][4];
519
520         DerivedMesh *result = NULL;
521
522         if (dm == NULL || dm_select == NULL) return 0;
523         if (!dm->getNumTessFaces(dm) || !dm_select->getNumTessFaces(dm_select)) return 0;
524
525         /* we map the final object back into ob's local coordinate space. For this
526          * we need to compute the inverse transform from global to ob (inv_mat),
527          * and the transform from ob to ob_select for use in interpolation (map_mat) */
528         invert_m4_m4(inv_mat, ob->obmat);
529         mult_m4_m4m4(map_mat, inv_mat, ob_select->obmat);
530         invert_m4_m4(inv_mat, ob_select->obmat);
531
532         {
533                 /* interface with the boolean module:
534                  *
535                  * the idea is, we pass the boolean module verts and faces using the
536                  * provided descriptors. once the boolean operation is performed, we
537                  * get back output descriptors, from which we then build a DerivedMesh */
538
539                 CSG_VertexIteratorDescriptor vd_1, vd_2;
540                 CSG_FaceIteratorDescriptor fd_1, fd_2;
541                 CSG_OperationType op_type;
542                 CSG_BooleanOperation *bool_op;
543
544                 /* work out the operation they chose and pick the appropriate
545                  * enum from the csg module. */
546                 switch (int_op_type) {
547                         case 1: op_type = e_csg_intersection; break;
548                         case 2: op_type = e_csg_union; break;
549                         case 3: op_type = e_csg_difference; break;
550                         case 4: op_type = e_csg_classify; break;
551                         default: op_type = e_csg_intersection;
552                 }
553
554                 BuildMeshDescriptors(dm_select, ob_select, 0, &fd_1, &vd_1);
555                 BuildMeshDescriptors(dm, ob, dm_select->getNumTessFaces(dm_select), &fd_2, &vd_2);
556
557                 bool_op = CSG_NewBooleanFunction();
558
559                 /* perform the operation */
560                 if (CSG_PerformBooleanOperation(bool_op, op_type, fd_1, vd_1, fd_2, vd_2)) {
561                         CSG_VertexIteratorDescriptor vd_o;
562                         CSG_FaceIteratorDescriptor fd_o;
563
564                         CSG_OutputFaceDescriptor(bool_op, &fd_o);
565                         CSG_OutputVertexDescriptor(bool_op, &vd_o);
566
567                         /* iterate through results of operation and insert
568                          * into new object */
569                         result = ConvertCSGDescriptorsToDerivedMesh(
570                             &fd_o, &vd_o, inv_mat, map_mat, mat, totmat, dm_select, ob_select, dm, ob);
571
572                         /* free up the memory */
573                         CSG_FreeVertexDescriptor(&vd_o);
574                         CSG_FreeFaceDescriptor(&fd_o);
575                 }
576                 else
577                         printf("Unknown internal error in boolean\n");
578
579                 CSG_FreeBooleanOperation(bool_op);
580
581                 FreeMeshDescriptors(&fd_1, &vd_1);
582                 FreeMeshDescriptors(&fd_2, &vd_2);
583         }
584
585         return result;
586 }
587
588 int NewBooleanMesh(Scene *scene, Base *base, Base *base_select, int int_op_type)
589 {
590         Mesh *me_new;
591         int a, maxmat, totmat = 0;
592         Object *ob_new, *ob, *ob_select;
593         Material **mat;
594         DerivedMesh *result;
595         DerivedMesh *dm_select;
596         DerivedMesh *dm;
597
598         ob = base->object;
599         ob_select = base_select->object;
600
601         dm = mesh_get_derived_final(scene, ob, CD_MASK_BAREMESH);
602         dm_select = mesh_create_derived_view(scene, ob_select, 0); // no modifiers in editmode ??
603
604         maxmat = ob->totcol + ob_select->totcol;
605         mat = (Material **)MEM_mallocN(sizeof(Material *) * maxmat, "NewBooleanMeshMat");
606         
607         /* put some checks in for nice user feedback */
608         if (dm == NULL || dm_select == NULL) {
609                 return 0;
610         }
611
612         if (!dm->getNumTessFaces(dm) || !dm_select->getNumTessFaces(dm_select)) {
613                 MEM_freeN(mat);
614                 return -1;
615         }
616         
617         result = NewBooleanDerivedMesh_intern(dm, ob, dm_select, ob_select, int_op_type, mat, &totmat);
618
619         if (result == NULL) {
620                 MEM_freeN(mat);
621                 return 0;
622         }
623
624         /* create a new blender mesh object - using 'base' as  a template */
625         ob_new = AddNewBlenderMesh(scene, base_select);
626         me_new = ob_new->data;
627
628         DM_to_mesh(result, me_new, ob_new);
629         result->release(result);
630
631         dm->release(dm);
632         dm_select->release(dm_select);
633
634         /* add materials to object */
635         for (a = 0; a < totmat; a++)
636                 assign_material(ob_new, mat[a], a + 1, BKE_MAT_ASSIGN_USERPREF);
637
638         MEM_freeN(mat);
639
640         /* update dag */
641         DAG_id_tag_update(&ob_new->id, OB_RECALC_DATA);
642
643         return 1;
644 }
645
646 DerivedMesh *NewBooleanDerivedMesh(DerivedMesh *dm, struct Object *ob, DerivedMesh *dm_select, struct Object *ob_select,
647                                    int int_op_type)
648 {
649         return NewBooleanDerivedMesh_intern(dm, ob, dm_select, ob_select, int_op_type, NULL, NULL);
650 }