source/blender/blenkernel/intern/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) 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_arithb.h"
  37 #include "BLI_blenlib.h"
  38 #include "BLI_ghash.h"
  39
  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"
  45
  46 #include "CSG_BooleanOps.h"
  47
  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"
  56 #include "BKE_mesh.h"
  57 #include "BKE_object.h"
  58 #include "BKE_utildefines.h"
  59
  60
  61
  62 /**
  63  * Here's the vertex iterator structure used to walk through
  64  * the blender vertex structure.
  65  */
  66
  67 typedef struct {
  68         DerivedMesh *dm;
  69         Object *ob;
  70         int pos;
  71 } VertexIt;
  72
  73 /**
  74  * Implementations of local vertex iterator functions.
  75  * These describe a blender mesh to the CSG module.
  76  */
  77
  78 static void VertexIt_Destruct(CSG_VertexIteratorDescriptor * iterator)
  79 {
  80         if (iterator->it) {
  81                 // deallocate memory for iterator
  82                 MEM_freeN(iterator->it);
  83                 iterator->it = 0;
  84         }
  85         iterator->Done = NULL;
  86         iterator->Fill = NULL;
  87         iterator->Reset = NULL;
  88         iterator->Step = NULL;
  89         iterator->num_elements = 0;
  90
  91 }
  92
  93 static int VertexIt_Done(CSG_IteratorPtr it)
  94 {
  95         VertexIt * iterator = (VertexIt *)it;
  96         return(iterator->pos >= iterator->dm->getNumVerts(iterator->dm));
  97 }
  98
  99 static void VertexIt_Fill(CSG_IteratorPtr it, CSG_IVertex *vert)
 100 {
 101         VertexIt * iterator = (VertexIt *)it;
 102         MVert *verts = iterator->dm->getVertArray(iterator->dm);
 103
 104         float global_pos[3];
 105
 106         /* boolean happens in global space, transform both with obmat */
 107         VecMat4MulVecfl(
 108                 global_pos,
 109                 iterator->ob->obmat,
 110                 verts[iterator->pos].co
 111         );
 112
 113         vert->position[0] = global_pos[0];
 114         vert->position[1] = global_pos[1];
 115         vert->position[2] = global_pos[2];
 116 }
 117
 118 static void VertexIt_Step(CSG_IteratorPtr it)
 119 {
 120         VertexIt * iterator = (VertexIt *)it;
 121         iterator->pos ++;
 122 }
 123
 124 static void VertexIt_Reset(CSG_IteratorPtr it)
 125 {
 126         VertexIt * iterator = (VertexIt *)it;
 127         iterator->pos = 0;
 128 }
 129
 130 static void VertexIt_Construct(CSG_VertexIteratorDescriptor *output, DerivedMesh *dm, Object *ob)
 131 {
 132
 133         VertexIt *it;
 134         if (output == 0) return;
 135
 136         // allocate some memory for blender iterator
 137         it = (VertexIt *)(MEM_mallocN(sizeof(VertexIt),"Boolean_VIt"));
 138         if (it == 0) {
 139                 return;
 140         }
 141         // assign blender specific variables
 142         it->dm = dm;
 143         it->ob = ob; // needed for obmat transformations
 144
 145         it->pos = 0;
 146
 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);
 153         output->it = it;
 154 }
 155
 156 /**
 157  * Blender Face iterator
 158  */
 159
 160 typedef struct {
 161         DerivedMesh *dm;
 162         int pos;
 163         int offset;
 164         int flip;
 165 } FaceIt;
 166
 167 static void FaceIt_Destruct(CSG_FaceIteratorDescriptor * iterator)
 168 {
 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;
 175 }
 176
 177 static int FaceIt_Done(CSG_IteratorPtr it)
 178 {
 179         // assume CSG_IteratorPtr is of the correct type.
 180         FaceIt * iterator = (FaceIt *)it;
 181         return(iterator->pos >= iterator->dm->getNumFaces(iterator->dm));
 182 }
 183
 184 static void FaceIt_Fill(CSG_IteratorPtr it, CSG_IFace *face)
 185 {
 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];
 190
 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;
 196         } else {
 197                 face->vertex_index[2] = mface->v1;
 198                 face->vertex_index[0] = mface->v3;
 199         }
 200         if (mface->v4) {
 201                 face->vertex_index[3] = mface->v4;
 202                 face->vertex_number = 4;
 203         } else {
 204                 face->vertex_number = 3;
 205         }
 206
 207         face->orig_face = face_it->offset + face_it->pos;
 208 }
 209
 210 static void FaceIt_Step(CSG_IteratorPtr it)
 211 {
 212         FaceIt * face_it = (FaceIt *)it;
 213         face_it->pos ++;
 214 }
 215
 216 static void FaceIt_Reset(CSG_IteratorPtr it)
 217 {
 218         FaceIt * face_it = (FaceIt *)it;
 219         face_it->pos = 0;
 220 }
 221
 222 static void FaceIt_Construct(
 223         CSG_FaceIteratorDescriptor *output, DerivedMesh *dm, int offset, Object *ob)
 224 {
 225         FaceIt *it;
 226         if (output == 0) return;
 227
 228         // allocate some memory for blender iterator
 229         it = (FaceIt *)(MEM_mallocN(sizeof(FaceIt),"Boolean_FIt"));
 230         if (it == 0) {
 231                 return ;
 232         }
 233         // assign blender specific variables
 234         it->dm = dm;
 235         it->offset = offset;
 236         it->pos = 0;
 237
 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) {
 241                         it->flip = 1;
 242                 } else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) {
 243                         it->flip = 1;
 244                 } else {
 245                         it->flip = 0;
 246                 }
 247         } else {
 248                 if (ob->size[1] < 0.0f && ob->size[2] < 0.0f) {
 249                         it->flip = 0;
 250                 } else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) {
 251                         it->flip = 0;
 252                 } else {
 253                         it->flip = 1;
 254                 }
 255         }
 256
 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);
 263         output->it = it;
 264 }
 265
 266 static Object *AddNewBlenderMesh(Scene *scene, Base *base)
 267 {
 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.
 271         Mesh *old_me;
 272         Base *basen;
 273         Object *ob_new;
 274
 275         // now create a new blender object.
 276         // duplicating all the settings from the previous object
 277         // to the new one.
 278         ob_new= copy_object(base->object);
 279
 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;
 284         old_me->id.us--;
 285
 286         // Now create a new base to add into the linked list of
 287         // vase objects.
 288
 289         basen= MEM_mallocN(sizeof(Base), "duplibase");
 290         *basen= *base;
 291         BLI_addhead(&scene->base, basen);       /* addhead: anders oneindige lus */
 292         basen->object= ob_new;
 293         basen->flag &= ~SELECT;
 294
 295         // Initialize the mesh data associated with this object.
 296         ob_new->data= add_mesh("Mesh");
 297
 298         // Finally assign the object type.
 299         ob_new->type= OB_MESH;
 300
 301         return ob_new;
 302 }
 303
 304 static void InterpCSGFace(
 305         DerivedMesh *dm, DerivedMesh *orig_dm, int index, int orig_index, int nr,
 306         float mapmat[][4])
 307 {
 308         float obco[3], *co[4], *orig_co[4], w[4][4];
 309         MFace *mface, *orig_mface;
 310         int j;
 311
 312         mface = CDDM_get_face(dm, index);
 313         orig_mface = orig_dm->getFaceArray(orig_dm) + orig_index;
 314
 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;
 320
 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;
 326
 327         for (j = 0; j < nr; j++) {
 328                 // get coordinate into the space of the original mesh
 329                 if (mapmat)
 330                         VecMat4MulVecfl(obco, mapmat, co[j]);
 331                 else
 332                         VecCopyf(obco, co[j]);
 333
 334                 InterpWeightsQ3Dfl(orig_co[0], orig_co[1], orig_co[2], orig_co[3], obco, w[j]);
 335         }
 336
 337         CustomData_interp(&orig_dm->faceData, &dm->faceData, &orig_index, NULL, (float*)w, 1, index);
 338 }
 339
 340 /* Iterate over the CSG Output Descriptors and create a new DerivedMesh
 341    from them */
 342 static DerivedMesh *ConvertCSGDescriptorsToDerivedMesh(
 343         CSG_FaceIteratorDescriptor *face_it,
 344         CSG_VertexIteratorDescriptor *vertex_it,
 345         float parinv[][4],
 346         float mapmat[][4],
 347         Material **mat,
 348         int *totmat,
 349         DerivedMesh *dm1,
 350         Object *ob1,
 351         DerivedMesh *dm2,
 352         Object *ob2)
 353 {
 354         DerivedMesh *result, *orig_dm;
 355         GHash *material_hash = NULL;
 356         Mesh *me1= (Mesh*)ob1->data;
 357         Mesh *me2= (Mesh*)ob2->data;
 358         int i;
 359
 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);
 366
 367         // step through the vertex iterators:
 368         for (i = 0; !vertex_it->Done(vertex_it->it); i++) {
 369                 CSG_IVertex csgvert;
 370                 MVert *mvert = CDDM_get_vert(result, i);
 371
 372                 // retrieve a csg vertex from the boolean module
 373                 vertex_it->Fill(vertex_it->it, &csgvert);
 374                 vertex_it->Step(vertex_it->it);
 375
 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);
 379         }
 380
 381         // a hash table to remap materials to indices
 382         if (mat) {
 383                 material_hash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
 384                 *totmat = 0;
 385         }
 386
 387         // step through the face iterators
 388         for(i = 0; !face_it->Done(face_it->it); i++) {
 389                 Mesh *orig_me;
 390                 Object *orig_ob;
 391                 Material *orig_mat;
 392                 CSG_IFace csgface;
 393                 MFace *mface;
 394                 int orig_index, mat_nr;
 395
 396                 // retrieve a csg face from the boolean module
 397                 face_it->Fill(face_it->it, &csgface);
 398                 face_it->Step(face_it->it);
 399
 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);
 405
 406                 // copy all face layers, including mface
 407                 CustomData_copy_data(&orig_dm->faceData, &result->faceData, orig_index, i, 1);
 408
 409                 // set mface
 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;
 415
 416                 // set material, based on lookup in hash table
 417                 orig_mat= give_current_material(orig_ob, mface->mat_nr+1);
 418
 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));
 424                         }
 425                         else
 426                                 mface->mat_nr = GET_INT_FROM_POINTER(BLI_ghash_lookup(material_hash, orig_mat));
 427                 }
 428                 else
 429                         mface->mat_nr = 0;
 430
 431                 InterpCSGFace(result, orig_dm, i, orig_index, csgface.vertex_number,
 432                               (orig_me == me2)? mapmat: NULL);
 433
 434                 test_index_face(mface, &result->faceData, i, csgface.vertex_number);
 435         }
 436
 437         if (material_hash)
 438                 BLI_ghash_free(material_hash, NULL, NULL);
 439
 440         CDDM_calc_edges(result);
 441         CDDM_calc_normals(result);
 442
 443         return result;
 444 }
 445
 446 static void BuildMeshDescriptors(
 447         struct DerivedMesh *dm,
 448         struct Object *ob,
 449         int face_offset,
 450         struct CSG_FaceIteratorDescriptor * face_it,
 451         struct CSG_VertexIteratorDescriptor * vertex_it)
 452 {
 453         VertexIt_Construct(vertex_it,dm, ob);
 454         FaceIt_Construct(face_it,dm,face_offset,ob);
 455 }
 456
 457 static void FreeMeshDescriptors(
 458         struct CSG_FaceIteratorDescriptor *face_it,
 459         struct CSG_VertexIteratorDescriptor *vertex_it)
 460 {
 461         VertexIt_Destruct(vertex_it);
 462         FaceIt_Destruct(face_it);
 463 }
 464
 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)
 468 {
 469
 470         float inv_mat[4][4];
 471         float map_mat[4][4];
 472
 473         DerivedMesh *result = NULL;
 474
 475         if (dm == NULL || dm_select == NULL) return 0;
 476         if (!dm->getNumFaces(dm) || !dm_select->getNumFaces(dm_select)) return 0;
 477
 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);
 484
 485         {
 486                 // interface with the boolean module:
 487                 //
 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
 491
 492                 CSG_VertexIteratorDescriptor vd_1, vd_2;
 493                 CSG_FaceIteratorDescriptor fd_1, fd_2;
 494                 CSG_OperationType op_type;
 495                 CSG_BooleanOperation *bool_op;
 496
 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;
 505                 }
 506
 507                 BuildMeshDescriptors(dm_select, ob_select, 0, &fd_1, &vd_1);
 508                 BuildMeshDescriptors(dm, ob, dm_select->getNumFaces(dm_select) , &fd_2, &vd_2);
 509
 510                 bool_op = CSG_NewBooleanFunction();
 511
 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;
 516
 517                         CSG_OutputFaceDescriptor(bool_op, &fd_o);
 518                         CSG_OutputVertexDescriptor(bool_op, &vd_o);
 519
 520                         // iterate through results of operation and insert
 521                         // into new object
 522                         result = ConvertCSGDescriptorsToDerivedMesh(
 523                                 &fd_o, &vd_o, inv_mat, map_mat, mat, totmat, dm_select, ob_select, dm, ob);
 524
 525                         // free up the memory
 526                         CSG_FreeVertexDescriptor(&vd_o);
 527                         CSG_FreeFaceDescriptor(&fd_o);
 528                 }
 529 //              else
 530 // XXX                  error("Unknown internal error in boolean");
 531
 532                 CSG_FreeBooleanOperation(bool_op);
 533
 534                 FreeMeshDescriptors(&fd_1, &vd_1);
 535                 FreeMeshDescriptors(&fd_2, &vd_2);
 536         }
 537
 538         return result;
 539 }
 540
 541 int NewBooleanMesh(Scene *scene, Base *base, Base *base_select, int int_op_type)
 542 {
 543         Mesh *me_new;
 544         int a, maxmat, totmat= 0;
 545         Object *ob_new, *ob, *ob_select;
 546         Material **mat;
 547         DerivedMesh *result;
 548         DerivedMesh *dm_select;
 549         DerivedMesh *dm;
 550
 551         ob= base->object;
 552         ob_select= base_select->object;
 553
 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 ??
 556
 557         maxmat= ob->totcol + ob_select->totcol;
 558         mat= (Material**)MEM_mallocN(sizeof(Material*)*maxmat, "NewBooleanMeshMat");
 559
 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))
 563         {
 564                 MEM_freeN(mat);
 565                 return -1;
 566         }
 567
 568         result= NewBooleanDerivedMesh_intern(dm, ob, dm_select, ob_select, int_op_type, mat, &totmat);
 569
 570         if (result == NULL) {
 571                 MEM_freeN(mat);
 572                 return 0;
 573         }
 574
 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;
 578
 579         DM_to_mesh(result, me_new);
 580         result->release(result);
 581
 582         dm->release(dm);
 583         dm_select->release(dm_select);
 584
 585         /* add materials to object */
 586         for (a = 0; a < totmat; a++)
 587                 assign_material(ob_new, mat[a], a+1);
 588
 589         MEM_freeN(mat);
 590
 591         /* update dag */
 592         DAG_object_flush_update(scene, ob_new, OB_RECALC_DATA);
 593
 594         return 1;
 595 }
 596
 597 DerivedMesh *NewBooleanDerivedMesh(DerivedMesh *dm, struct Object *ob, DerivedMesh *dm_select, struct Object *ob_select,
 598                                    int int_op_type)
 599 {
 600         return NewBooleanDerivedMesh_intern(dm, ob, dm_select, ob_select, int_op_type, NULL, NULL);
 601 }
 602