4 * ***** BEGIN GPL LICENSE BLOCK *****
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.
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.
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.
20 * The Original Code is Copyright (C) Blender Foundation
21 * All rights reserved.
23 * The Original Code is: all of this file.
25 * Contributor(s): none yet.
27 * ***** END GPL LICENSE BLOCK *****
34 #include "MEM_guardedalloc.h"
36 #include "BLI_arithb.h"
37 #include "BLI_blenlib.h"
38 #include "BLI_ghash.h"
40 #include "DNA_material_types.h"
41 #include "DNA_mesh_types.h"
42 #include "DNA_meshdata_types.h"
43 #include "DNA_object_types.h"
44 #include "DNA_scene_types.h"
46 #include "CSG_BooleanOps.h"
48 #include "BKE_booleanops.h"
49 #include "BKE_cdderivedmesh.h"
50 #include "BKE_customdata.h"
51 #include "BKE_depsgraph.h"
52 #include "BKE_DerivedMesh.h"
53 #include "BKE_global.h"
54 #include "BKE_library.h"
55 #include "BKE_material.h"
57 #include "BKE_object.h"
58 #include "BKE_utildefines.h"
63 * Here's the vertex iterator structure used to walk through
64 * the blender vertex structure.
74 * Implementations of local vertex iterator functions.
75 * These describe a blender mesh to the CSG module.
78 static void VertexIt_Destruct(CSG_VertexIteratorDescriptor * iterator)
81 // deallocate memory for iterator
82 MEM_freeN(iterator->it);
85 iterator->Done = NULL;
86 iterator->Fill = NULL;
87 iterator->Reset = NULL;
88 iterator->Step = NULL;
89 iterator->num_elements = 0;
93 static int VertexIt_Done(CSG_IteratorPtr it)
95 VertexIt * iterator = (VertexIt *)it;
96 return(iterator->pos >= iterator->dm->getNumVerts(iterator->dm));
99 static void VertexIt_Fill(CSG_IteratorPtr it, CSG_IVertex *vert)
101 VertexIt * iterator = (VertexIt *)it;
102 MVert *verts = iterator->dm->getVertArray(iterator->dm);
106 /* boolean happens in global space, transform both with obmat */
110 verts[iterator->pos].co
113 vert->position[0] = global_pos[0];
114 vert->position[1] = global_pos[1];
115 vert->position[2] = global_pos[2];
118 static void VertexIt_Step(CSG_IteratorPtr it)
120 VertexIt * iterator = (VertexIt *)it;
124 static void VertexIt_Reset(CSG_IteratorPtr it)
126 VertexIt * iterator = (VertexIt *)it;
130 static void VertexIt_Construct(CSG_VertexIteratorDescriptor *output, DerivedMesh *dm, Object *ob)
134 if (output == 0) return;
136 // allocate some memory for blender iterator
137 it = (VertexIt *)(MEM_mallocN(sizeof(VertexIt),"Boolean_VIt"));
141 // assign blender specific variables
143 it->ob = ob; // needed for obmat transformations
147 // assign iterator function pointers.
148 output->Step = VertexIt_Step;
149 output->Fill = VertexIt_Fill;
150 output->Done = VertexIt_Done;
151 output->Reset = VertexIt_Reset;
152 output->num_elements = it->dm->getNumVerts(it->dm);
157 * Blender Face iterator
167 static void FaceIt_Destruct(CSG_FaceIteratorDescriptor * iterator)
169 MEM_freeN(iterator->it);
170 iterator->Done = NULL;
171 iterator->Fill = NULL;
172 iterator->Reset = NULL;
173 iterator->Step = NULL;
174 iterator->num_elements = 0;
177 static int FaceIt_Done(CSG_IteratorPtr it)
179 // assume CSG_IteratorPtr is of the correct type.
180 FaceIt * iterator = (FaceIt *)it;
181 return(iterator->pos >= iterator->dm->getNumFaces(iterator->dm));
184 static void FaceIt_Fill(CSG_IteratorPtr it, CSG_IFace *face)
186 // assume CSG_IteratorPtr is of the correct type.
187 FaceIt *face_it = (FaceIt *)it;
188 MFace *mfaces = face_it->dm->getFaceArray(face_it->dm);
189 MFace *mface = &mfaces[face_it->pos];
191 /* reverse face vertices if necessary */
192 face->vertex_index[1] = mface->v2;
193 if( face_it->flip == 0 ) {
194 face->vertex_index[0] = mface->v1;
195 face->vertex_index[2] = mface->v3;
197 face->vertex_index[2] = mface->v1;
198 face->vertex_index[0] = mface->v3;
201 face->vertex_index[3] = mface->v4;
202 face->vertex_number = 4;
204 face->vertex_number = 3;
207 face->orig_face = face_it->offset + face_it->pos;
210 static void FaceIt_Step(CSG_IteratorPtr it)
212 FaceIt * face_it = (FaceIt *)it;
216 static void FaceIt_Reset(CSG_IteratorPtr it)
218 FaceIt * face_it = (FaceIt *)it;
222 static void FaceIt_Construct(
223 CSG_FaceIteratorDescriptor *output, DerivedMesh *dm, int offset, Object *ob)
226 if (output == 0) return;
228 // allocate some memory for blender iterator
229 it = (FaceIt *)(MEM_mallocN(sizeof(FaceIt),"Boolean_FIt"));
233 // assign blender specific variables
238 /* determine if we will need to reverse order of face vertices */
239 if (ob->size[0] < 0.0f) {
240 if (ob->size[1] < 0.0f && ob->size[2] < 0.0f) {
242 } else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) {
248 if (ob->size[1] < 0.0f && ob->size[2] < 0.0f) {
250 } else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) {
257 // assign iterator function pointers.
258 output->Step = FaceIt_Step;
259 output->Fill = FaceIt_Fill;
260 output->Done = FaceIt_Done;
261 output->Reset = FaceIt_Reset;
262 output->num_elements = it->dm->getNumFaces(it->dm);
266 static Object *AddNewBlenderMesh(Scene *scene, Base *base)
268 // This little function adds a new mesh object to the blender object list
269 // It uses ob to duplicate data as this seems to be easier than creating
270 // a new one. This new oject contains no faces nor vertices.
275 // now create a new blender object.
276 // duplicating all the settings from the previous object
278 ob_new= copy_object(base->object);
280 // Ok we don't want to use the actual data from the
281 // last object, the above function incremented the
282 // number of users, so decrement it here.
283 old_me= ob_new->data;
286 // Now create a new base to add into the linked list of
289 basen= MEM_mallocN(sizeof(Base), "duplibase");
291 BLI_addhead(&scene->base, basen); /* addhead: anders oneindige lus */
292 basen->object= ob_new;
293 basen->flag &= ~SELECT;
295 // Initialize the mesh data associated with this object.
296 ob_new->data= add_mesh("Mesh");
298 // Finally assign the object type.
299 ob_new->type= OB_MESH;
304 static void InterpCSGFace(
305 DerivedMesh *dm, DerivedMesh *orig_dm, int index, int orig_index, int nr,
308 float obco[3], *co[4], *orig_co[4], w[4][4];
309 MFace *mface, *orig_mface;
312 mface = CDDM_get_face(dm, index);
313 orig_mface = orig_dm->getFaceArray(orig_dm) + orig_index;
315 // get the vertex coordinates from the original mesh
316 orig_co[0] = (orig_dm->getVertArray(orig_dm) + orig_mface->v1)->co;
317 orig_co[1] = (orig_dm->getVertArray(orig_dm) + orig_mface->v2)->co;
318 orig_co[2] = (orig_dm->getVertArray(orig_dm) + orig_mface->v3)->co;
319 orig_co[3] = (orig_mface->v4)? (orig_dm->getVertArray(orig_dm) + orig_mface->v4)->co: NULL;
321 // get the vertex coordinates from the new derivedmesh
322 co[0] = CDDM_get_vert(dm, mface->v1)->co;
323 co[1] = CDDM_get_vert(dm, mface->v2)->co;
324 co[2] = CDDM_get_vert(dm, mface->v3)->co;
325 co[3] = (nr == 4)? CDDM_get_vert(dm, mface->v4)->co: NULL;
327 for (j = 0; j < nr; j++) {
328 // get coordinate into the space of the original mesh
330 VecMat4MulVecfl(obco, mapmat, co[j]);
332 VecCopyf(obco, co[j]);
334 InterpWeightsQ3Dfl(orig_co[0], orig_co[1], orig_co[2], orig_co[3], obco, w[j]);
337 CustomData_interp(&orig_dm->faceData, &dm->faceData, &orig_index, NULL, (float*)w, 1, index);
340 /* Iterate over the CSG Output Descriptors and create a new DerivedMesh
342 static DerivedMesh *ConvertCSGDescriptorsToDerivedMesh(
343 CSG_FaceIteratorDescriptor *face_it,
344 CSG_VertexIteratorDescriptor *vertex_it,
354 DerivedMesh *result, *orig_dm;
355 GHash *material_hash = NULL;
356 Mesh *me1= (Mesh*)ob1->data;
357 Mesh *me2= (Mesh*)ob2->data;
360 // create a new DerivedMesh
361 result = CDDM_new(vertex_it->num_elements, 0, face_it->num_elements);
362 CustomData_merge(&dm1->faceData, &result->faceData, CD_MASK_DERIVEDMESH,
363 CD_DEFAULT, face_it->num_elements);
364 CustomData_merge(&dm2->faceData, &result->faceData, CD_MASK_DERIVEDMESH,
365 CD_DEFAULT, face_it->num_elements);
367 // step through the vertex iterators:
368 for (i = 0; !vertex_it->Done(vertex_it->it); i++) {
370 MVert *mvert = CDDM_get_vert(result, i);
372 // retrieve a csg vertex from the boolean module
373 vertex_it->Fill(vertex_it->it, &csgvert);
374 vertex_it->Step(vertex_it->it);
376 // we have to map the vertex coordinates back in the coordinate frame
377 // of the resulting object, since it was computed in world space
378 VecMat4MulVecfl(mvert->co, parinv, csgvert.position);
381 // a hash table to remap materials to indices
383 material_hash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
387 // step through the face iterators
388 for(i = 0; !face_it->Done(face_it->it); i++) {
394 int orig_index, mat_nr;
396 // retrieve a csg face from the boolean module
397 face_it->Fill(face_it->it, &csgface);
398 face_it->Step(face_it->it);
400 // find the original mesh and data
401 orig_ob = (csgface.orig_face < dm1->getNumFaces(dm1))? ob1: ob2;
402 orig_dm = (csgface.orig_face < dm1->getNumFaces(dm1))? dm1: dm2;
403 orig_me = (orig_ob == ob1)? me1: me2;
404 orig_index = (orig_ob == ob1)? csgface.orig_face: csgface.orig_face - dm1->getNumFaces(dm1);
406 // copy all face layers, including mface
407 CustomData_copy_data(&orig_dm->faceData, &result->faceData, orig_index, i, 1);
410 mface = CDDM_get_face(result, i);
411 mface->v1 = csgface.vertex_index[0];
412 mface->v2 = csgface.vertex_index[1];
413 mface->v3 = csgface.vertex_index[2];
414 mface->v4 = (csgface.vertex_number == 4)? csgface.vertex_index[3]: 0;
416 // set material, based on lookup in hash table
417 orig_mat= give_current_material(orig_ob, mface->mat_nr+1);
419 if (mat && orig_mat) {
420 if (!BLI_ghash_haskey(material_hash, orig_mat)) {
421 mat[*totmat] = orig_mat;
422 mat_nr = mface->mat_nr = (*totmat)++;
423 BLI_ghash_insert(material_hash, orig_mat, SET_INT_IN_POINTER(mat_nr));
426 mface->mat_nr = GET_INT_FROM_POINTER(BLI_ghash_lookup(material_hash, orig_mat));
431 InterpCSGFace(result, orig_dm, i, orig_index, csgface.vertex_number,
432 (orig_me == me2)? mapmat: NULL);
434 test_index_face(mface, &result->faceData, i, csgface.vertex_number);
438 BLI_ghash_free(material_hash, NULL, NULL);
440 CDDM_calc_edges(result);
441 CDDM_calc_normals(result);
446 static void BuildMeshDescriptors(
447 struct DerivedMesh *dm,
450 struct CSG_FaceIteratorDescriptor * face_it,
451 struct CSG_VertexIteratorDescriptor * vertex_it)
453 VertexIt_Construct(vertex_it,dm, ob);
454 FaceIt_Construct(face_it,dm,face_offset,ob);
457 static void FreeMeshDescriptors(
458 struct CSG_FaceIteratorDescriptor *face_it,
459 struct CSG_VertexIteratorDescriptor *vertex_it)
461 VertexIt_Destruct(vertex_it);
462 FaceIt_Destruct(face_it);
465 DerivedMesh *NewBooleanDerivedMesh_intern(
466 DerivedMesh *dm, struct Object *ob, DerivedMesh *dm_select, struct Object *ob_select,
467 int int_op_type, Material **mat, int *totmat)
473 DerivedMesh *result = NULL;
475 if (dm == NULL || dm_select == NULL) return 0;
476 if (!dm->getNumFaces(dm) || !dm_select->getNumFaces(dm_select)) return 0;
478 // we map the final object back into ob's local coordinate space. For this
479 // we need to compute the inverse transform from global to ob (inv_mat),
480 // and the transform from ob to ob_select for use in interpolation (map_mat)
481 Mat4Invert(inv_mat, ob->obmat);
482 Mat4MulMat4(map_mat, ob_select->obmat, inv_mat);
483 Mat4Invert(inv_mat, ob_select->obmat);
486 // interface with the boolean module:
488 // the idea is, we pass the boolean module verts and faces using the
489 // provided descriptors. once the boolean operation is performed, we
490 // get back output descriptors, from which we then build a DerivedMesh
492 CSG_VertexIteratorDescriptor vd_1, vd_2;
493 CSG_FaceIteratorDescriptor fd_1, fd_2;
494 CSG_OperationType op_type;
495 CSG_BooleanOperation *bool_op;
497 // work out the operation they chose and pick the appropriate
498 // enum from the csg module.
499 switch (int_op_type) {
500 case 1 : op_type = e_csg_intersection; break;
501 case 2 : op_type = e_csg_union; break;
502 case 3 : op_type = e_csg_difference; break;
503 case 4 : op_type = e_csg_classify; break;
504 default : op_type = e_csg_intersection;
507 BuildMeshDescriptors(dm_select, ob_select, 0, &fd_1, &vd_1);
508 BuildMeshDescriptors(dm, ob, dm_select->getNumFaces(dm_select) , &fd_2, &vd_2);
510 bool_op = CSG_NewBooleanFunction();
512 // perform the operation
513 if (CSG_PerformBooleanOperation(bool_op, op_type, fd_1, vd_1, fd_2, vd_2)) {
514 CSG_VertexIteratorDescriptor vd_o;
515 CSG_FaceIteratorDescriptor fd_o;
517 CSG_OutputFaceDescriptor(bool_op, &fd_o);
518 CSG_OutputVertexDescriptor(bool_op, &vd_o);
520 // iterate through results of operation and insert
522 result = ConvertCSGDescriptorsToDerivedMesh(
523 &fd_o, &vd_o, inv_mat, map_mat, mat, totmat, dm_select, ob_select, dm, ob);
525 // free up the memory
526 CSG_FreeVertexDescriptor(&vd_o);
527 CSG_FreeFaceDescriptor(&fd_o);
530 // XXX error("Unknown internal error in boolean");
532 CSG_FreeBooleanOperation(bool_op);
534 FreeMeshDescriptors(&fd_1, &vd_1);
535 FreeMeshDescriptors(&fd_2, &vd_2);
541 int NewBooleanMesh(Scene *scene, Base *base, Base *base_select, int int_op_type)
544 int a, maxmat, totmat= 0;
545 Object *ob_new, *ob, *ob_select;
548 DerivedMesh *dm_select;
552 ob_select= base_select->object;
554 dm = mesh_get_derived_final(scene, ob, CD_MASK_BAREMESH);
555 dm_select = mesh_create_derived_view(scene, ob_select, 0); // no modifiers in editmode ??
557 maxmat= ob->totcol + ob_select->totcol;
558 mat= (Material**)MEM_mallocN(sizeof(Material*)*maxmat, "NewBooleanMeshMat");
560 /* put some checks in for nice user feedback */
561 if (dm == NULL || dm_select == NULL) return 0;
562 if (!dm->getNumFaces(dm) || !dm_select->getNumFaces(dm_select))
568 result= NewBooleanDerivedMesh_intern(dm, ob, dm_select, ob_select, int_op_type, mat, &totmat);
570 if (result == NULL) {
575 /* create a new blender mesh object - using 'base' as a template */
576 ob_new= AddNewBlenderMesh(scene, base_select);
577 me_new= ob_new->data;
579 DM_to_mesh(result, me_new);
580 result->release(result);
583 dm_select->release(dm_select);
585 /* add materials to object */
586 for (a = 0; a < totmat; a++)
587 assign_material(ob_new, mat[a], a+1);
592 DAG_object_flush_update(scene, ob_new, OB_RECALC_DATA);
597 DerivedMesh *NewBooleanDerivedMesh(DerivedMesh *dm, struct Object *ob, DerivedMesh *dm_select, struct Object *ob_select,
600 return NewBooleanDerivedMesh_intern(dm, ob, dm_select, ob_select, int_op_type, NULL, NULL);