diff options
Diffstat (limited to 'source/blender/src/booleanops.c')
| -rw-r--r-- | source/blender/src/booleanops.c | 795 |
1 files changed, 795 insertions, 0 deletions
diff --git a/source/blender/src/booleanops.c b/source/blender/src/booleanops.c new file mode 100644 index 00000000000..5c89dee1a46 --- /dev/null +++ b/source/blender/src/booleanops.c @@ -0,0 +1,795 @@ + +#include <string.h> +/** + * $Id$ + * + * ***** BEGIN GPL/BL DUAL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. The Blender + * Foundation also sells licenses for use in proprietary software under + * the Blender License. See http://www.blender.org/BL/ for information + * about this. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL/BL DUAL LICENSE BLOCK ***** + * CSG operations. + */ + + + +#include "MEM_guardedalloc.h" + +#include "BLI_ghash.h" + +#include "DNA_material_types.h" +#include "DNA_mesh_types.h" +#include "DNA_object_types.h" +#include "DNA_scene_types.h" + +#include "CSG_BooleanOps.h" + +#include "BKE_global.h" +#include "BKE_mesh.h" +#include "BKE_displist.h" +#include "BKE_object.h" +#include "BKE_booleanops.h" +#include "BKE_utildefines.h" +#include "BKE_library.h" +#include "BKE_material.h" + +#include <math.h> + +// TODO check to see how many of these includes are necessary + +#include "BLI_blenlib.h" +#include "BLI_editVert.h" +#include "BLI_arithb.h" +#include "BLI_linklist.h" +#include "BLI_memarena.h" + + +/** + * Here's the vertex iterator structure used to walk through + * the blender vertex structure. + */ + +typedef struct { + Object *ob; + Mesh *mesh; + int pos; +} VertexIt; + +/** + * Implementations of local vertex iterator functions. + * These describe a blender mesh to the CSG module. + */ + +static + void +VertexIt_Destruct( + CSG_VertexIteratorDescriptor * iterator +){ + if (iterator->it) { + // deallocate memory for iterator + MEM_freeN(iterator->it); + iterator->it = 0; + } + iterator->Done = NULL; + iterator->Fill = NULL; + iterator->Reset = NULL; + iterator->Step = NULL; + iterator->num_elements = 0; + +}; + +static + int +VertexIt_Done( + CSG_IteratorPtr it +){ + VertexIt * iterator = (VertexIt *)it; + return(iterator->pos >= iterator->mesh->totvert); +} + + +static + void +VertexIt_Fill( + CSG_IteratorPtr it, + CSG_IVertex *vert +){ + VertexIt * iterator = (VertexIt *)it; + MVert *verts = iterator->mesh->mvert; + + float global_pos[3]; + + VecMat4MulVecfl( + global_pos, + iterator->ob->obmat, + verts[iterator->pos].co + ); + + vert->position[0] = global_pos[0]; + vert->position[1] = global_pos[1]; + vert->position[2] = global_pos[2]; +} + +static + void +VertexIt_Step( + CSG_IteratorPtr it +){ + VertexIt * iterator = (VertexIt *)it; + iterator->pos ++; +} + +static + void +VertexIt_Reset( + CSG_IteratorPtr it +){ + VertexIt * iterator = (VertexIt *)it; + iterator->pos = 0; +} + +static + void +VertexIt_Construct( + CSG_VertexIteratorDescriptor * output, + Object *ob +){ + + VertexIt *it; + if (output == 0) return; + + // allocate some memory for blender iterator + it = (VertexIt *)(MEM_mallocN(sizeof(VertexIt),"Boolean_VIt")); + if (it == 0) { + return; + } + // assign blender specific variables + it->ob = ob; + it->mesh = ob->data; + + it->pos = 0; + + // assign iterator function pointers. + output->Step = VertexIt_Step; + output->Fill = VertexIt_Fill; + output->Done = VertexIt_Done; + output->Reset = VertexIt_Reset; + output->num_elements = it->mesh->totvert; + output->it = it; +} + +/** + * Blender Face iterator + */ + +typedef struct { + Object *ob; + Mesh *mesh; + int pos; +} FaceIt; + + +static + void +FaceIt_Destruct( + CSG_FaceIteratorDescriptor * iterator +) { + MEM_freeN(iterator->it); + iterator->Done = NULL; + iterator->Fill = NULL; + iterator->Reset = NULL; + iterator->Step = NULL; + iterator->num_elements = 0; +}; + + +static + int +FaceIt_Done( + CSG_IteratorPtr it +) { + // assume CSG_IteratorPtr is of the correct type. + FaceIt * iterator = (FaceIt *)it; + return(iterator->pos >= iterator->mesh->totface); +}; + +static + void +FaceIt_Fill( + CSG_IteratorPtr it, + CSG_IFace *face +){ + // assume CSG_IteratorPtr is of the correct type. + FaceIt * face_it = (FaceIt *)it; + Object *ob = face_it->ob; + MFace *mfaces = face_it->mesh->mface; + TFace *tfaces = face_it->mesh->tface; + int f_index = face_it->pos; + MFace *mface = &mfaces[f_index]; + FaceData *fdata = face->user_face_data; + + if (mface->v3) { + // ignore lines (faces with mface->v3==0) + face->vertex_index[0] = mface->v1; + face->vertex_index[1] = mface->v2; + face->vertex_index[2] = mface->v3; + if (mface->v4) { + face->vertex_index[3] = mface->v4; + face->vertex_number = 4; + } else { + face->vertex_number = 3; + } + } + + fdata->material = give_current_material(ob, mface->mat_nr+1); + + // pack rgba colors. + if (tfaces) { + TFace *tface= &tfaces[f_index]; + int i; + + fdata->tpage = tface->tpage; + fdata->flag = tface->flag; + fdata->transp = tface->transp; + fdata->mode = tface->mode; + fdata->tile = tface->tile; + + for (i=0; i<4; i++) { + FaceVertexData *fvdata= face->user_face_vertex_data[i]; + + fvdata->uv[0] = tface->uv[i][0]; + fvdata->uv[1] = tface->uv[i][1]; + fvdata->color[0] = (float) ((tface->col[i] >> 24) & 0xff); + fvdata->color[1] = (float) ((tface->col[i] >> 16) & 0xff); + fvdata->color[2] = (float) ((tface->col[i] >> 8) & 0xff); + fvdata->color[3] = (float) ((tface->col[i] >> 0) & 0xff); + } + } +}; + + +static + void +FaceIt_Step( + CSG_IteratorPtr it +) { + FaceIt * face_it = (FaceIt *)it; + face_it->pos ++; +}; + +static + void +FaceIt_Reset( + CSG_IteratorPtr it +) { + FaceIt * face_it = (FaceIt *)it; + face_it->pos = 0; +} + +static + void +FaceIt_Construct( + CSG_FaceIteratorDescriptor * output, + Object * ob +){ + + FaceIt *it; + if (output == 0) return; + + // allocate some memory for blender iterator + it = (FaceIt *)(MEM_mallocN(sizeof(FaceIt),"Boolean_FIt")); + if (it == 0) { + return ; + } + // assign blender specific variables + it->ob = ob; + it->mesh = ob->data; + it->pos = 0; + + // assign iterator function pointers. + output->Step = FaceIt_Step; + output->Fill = FaceIt_Fill; + output->Done = FaceIt_Done; + output->Reset = FaceIt_Reset; + output->num_elements = it->mesh->totface; + output->it = it; +}; + + +/** + * Interpolation functions for various user data types. + */ + + int +InterpNoUserData( + void *d1, + void *d2, + void *dnew, + float epsilon +) { + // nothing to do of course. + return 0; +} + + int +InterpFaceVertexData( + void *d1, + void *d2, + void *dnew, + float epsilon +) { + /* XXX, passed backwards, should be fixed inside + * BSP lib I guess. + */ + FaceVertexData *fv1 = d2; + FaceVertexData *fv2 = d1; + FaceVertexData *fvO = dnew; + + fvO->uv[0] = (fv2->uv[0] - fv1->uv[0]) * epsilon + fv1->uv[0]; + fvO->uv[1] = (fv2->uv[1] - fv1->uv[1]) * epsilon + fv1->uv[1]; + fvO->color[0] = (fv2->color[0] - fv1->color[0]) * epsilon + fv1->color[0]; + fvO->color[1] = (fv2->color[1] - fv1->color[1]) * epsilon + fv1->color[1]; + fvO->color[2] = (fv2->color[2] - fv1->color[2]) * epsilon + fv1->color[2]; + fvO->color[3] = (fv2->color[3] - fv1->color[3]) * epsilon + fv1->color[3]; + + return 0; +} + + + +/** + * Assumes mesh is valid and forms part of a fresh + * blender object. + */ + + + + int +NewBooleanMesh( + struct Base * base, + struct Base * base_select, + int int_op_type +){ + Mesh *me2 = get_mesh(base_select->object); + Mesh *me = get_mesh(base->object); + Mesh *me_new = NULL; + Object *ob; + int free_tface1,free_tface2; + + float inv_mat[4][4]; + int success = 0; + // build and fill new descriptors for these meshes + CSG_VertexIteratorDescriptor vd_1; + CSG_VertexIteratorDescriptor vd_2; + CSG_FaceIteratorDescriptor fd_1; + CSG_FaceIteratorDescriptor fd_2; + + CSG_MeshPropertyDescriptor mpd1,mpd2; + + // work out the operation they chose and pick the appropriate + // enum from the csg module. + + CSG_OperationType op_type; + + if (me == NULL || me2 == NULL) return 0; + + switch (int_op_type) { + case 1 : op_type = e_csg_intersection; break; + case 2 : op_type = e_csg_union; break; + case 3 : op_type = e_csg_difference; break; + case 4 : op_type = e_csg_classify; break; + default : op_type = e_csg_intersection; + } + + // Here is the section where we describe the properties of + // both meshes to the bsp module. + + if (me->mcol != NULL) { + // Then this mesh has vertex colors only + // well this is awkward because there is no equivalent + // test_index_mface just for vertex colors! + // as a temporary hack we can convert these vertex colors + // into tfaces do the operation and turn them back again. + + // create some memory for the tfaces. + me->tface = (TFace *)MEM_callocN(sizeof(TFace)*me->totface,"BooleanOps_TempTFace"); + mcol_to_tface(me,1); + free_tface1 = 1; + } else { + free_tface1 = 0; + } + + mpd1.user_face_vertex_data_size = 0; + mpd1.user_data_size = sizeof(FaceData); + + if (me->tface) { + mpd1.user_face_vertex_data_size = sizeof(FaceVertexData); + } + + // same for mesh2 + + if (me2->mcol != NULL) { + // create some memory for the tfaces. + me2->tface = (TFace *)MEM_callocN(sizeof(TFace)*me2->totface,"BooleanOps_TempTFace"); + mcol_to_tface(me2,1); + free_tface2 = 1; + } else { + free_tface2 = 0; + } + + mpd2.user_face_vertex_data_size = 0; + mpd2.user_data_size = sizeof(FaceData); + + if (me2->tface) { + mpd2.user_face_vertex_data_size = sizeof(FaceVertexData); + } + + ob = base->object; + + // we map the final object back into object 1's (ob) + // local coordinate space. For this we need to compute + // the inverse transform from global to local. + + Mat4Invert(inv_mat,ob->obmat); + + // make a boolean operation; + { + CSG_BooleanOperation * bool_op = CSG_NewBooleanFunction(); + CSG_MeshPropertyDescriptor output_mpd = CSG_DescibeOperands(bool_op,mpd1,mpd2); + // analyse the result and choose mesh descriptors accordingly + int output_type; + if (output_mpd.user_face_vertex_data_size) { + output_type = 1; + } else { + output_type = 0; + } + + BuildMeshDescriptors( + base->object, + &fd_1, + &vd_1 + ); + BuildMeshDescriptors( + base_select->object, + &fd_2, + &vd_2 + ); + + // perform the operation + + if (output_type == 0) { + + success = + CSG_PerformBooleanOperation( + bool_op, + op_type, + fd_1,vd_1,fd_2,vd_2, + InterpNoUserData + ); + } else { + success = + CSG_PerformBooleanOperation( + bool_op, + op_type, + fd_1,vd_1,fd_2,vd_2, + InterpFaceVertexData + ); + } + + if (success) { + // descriptions of the output; + CSG_VertexIteratorDescriptor vd_o; + CSG_FaceIteratorDescriptor fd_o; + + // Create a new blender mesh object - using 'base' as + // a template for the new object. + Object * ob_new= AddNewBlenderMesh(base); + + // get the output descriptors + + CSG_OutputFaceDescriptor(bool_op,&fd_o); + CSG_OutputVertexDescriptor(bool_op,&vd_o); + + me_new = ob_new->data; + // iterate through results of operation and insert into new object + // see subsurf.c + + ConvertCSGDescriptorsToMeshObject( + ob_new, + &output_mpd, + &fd_o, + &vd_o, + inv_mat + ); + + // initialize the object + tex_space_mesh(me_new); + + // free up the memory + + CSG_FreeVertexDescriptor(&vd_o); + CSG_FreeFaceDescriptor(&fd_o); + } + + CSG_FreeBooleanOperation(bool_op); + bool_op = NULL; + + } + + // We may need to map back the tfaces to mcols here. + if (free_tface1) { + tface_to_mcol(me); + MEM_freeN(me->tface); + me->tface = NULL; + } + if (free_tface2) { + tface_to_mcol(me2); + MEM_freeN(me2->tface); + me2->tface = NULL; + } + + if (free_tface1 && free_tface2) { + // then we need to map the output tfaces into mcols + if (me_new) { + tface_to_mcol(me_new); + MEM_freeN(me_new->tface); + me_new->tface = NULL; + } + } + + FreeMeshDescriptors(&fd_1,&vd_1); + FreeMeshDescriptors(&fd_2,&vd_2); + + return success; +} + + + Object * +AddNewBlenderMesh( + Base *base +){ + Mesh *old_me; + Base *basen; + Object *ob_new; + + // now create a new blender object. + // duplicating all the settings from the previous object + // to the new one. + ob_new= copy_object(base->object); + + // Ok we don't want to use the actual data from the + // last object, the above function incremented the + // number of users, so decrement it here. + old_me= ob_new->data; + old_me->id.us--; + + // Now create a new base to add into the linked list of + // vase objects. + + basen= MEM_mallocN(sizeof(Base), "duplibase"); + *basen= *base; + BLI_addhead(&G.scene->base, basen); /* addhead: anders oneindige lus */ + basen->object= ob_new; + basen->flag &= ~SELECT; + + // Initialize the mesh data associated with this object. + ob_new->data= add_mesh(); + G.totmesh++; + + // Finally assign the object type. + ob_new->type= OB_MESH; + + return ob_new; +}; + + + +/** + * + * External interface + * + * This function builds a blender mesh using the output information from + * the CSG module. It declares all the necessary blender cruft and + * fills in the vertex and face arrays. + */ + int +ConvertCSGDescriptorsToMeshObject( + Object *ob, + CSG_MeshPropertyDescriptor *props, + CSG_FaceIteratorDescriptor *face_it, + CSG_VertexIteratorDescriptor *vertex_it, + float parinv[][4] +){ + Mesh *me = ob->data; + FaceVertexData *user_face_vertex_data; + GHash *material_hash; + CSG_IVertex vert; + CSG_IFace face; + MVert *insert_pos; + MFace *mfaces; + TFace *tfaces; + int fi_insert_pos, nmaterials; + + // create some memory for the Iface according to output mesh props. + + if (face_it == NULL || vertex_it == NULL || props == NULL || me == NULL) { + return 0; + } + if (vertex_it->num_elements > 65000) return 0; + + // initialize the face structure for readback + + face.user_face_data = MEM_callocN(sizeof(FaceData),"BooleanOp_IFaceData"); + + if (props->user_face_vertex_data_size) { + user_face_vertex_data = MEM_callocN(sizeof(FaceVertexData)*4,"BooleanOp_IFaceData"); + face.user_face_vertex_data[0] = &user_face_vertex_data[0]; + face.user_face_vertex_data[1] = &user_face_vertex_data[1]; + face.user_face_vertex_data[2] = &user_face_vertex_data[2]; + face.user_face_vertex_data[3] = &user_face_vertex_data[3]; + } else { + user_face_vertex_data = NULL; + } + + // create memory for the vertex array. + + me->mvert = MEM_callocN(sizeof(MVert) * vertex_it->num_elements,"BooleanOp_VertexArray"); + me->mface = MEM_callocN(sizeof(MFace) * face_it->num_elements,"BooleanOp_FaceArray"); + + if (user_face_vertex_data) { + me->tface = MEM_callocN(sizeof(TFace) * face_it->num_elements,"BooleanOp_TFaceArray"); + if (me->tface == NULL) return 0; + } else { + me->tface = NULL; + } + + if (me->mvert == NULL || me->mface == NULL) return 0; + + insert_pos = me->mvert; + mfaces = me->mface; + tfaces = me->tface; + + fi_insert_pos = 0; + + // step through the iterators. + + while (!vertex_it->Done(vertex_it->it)) { + vertex_it->Fill(vertex_it->it,&vert); + + // map output vertex into insert_pos + // and transform at by parinv at the same time. + + VecMat4MulVecfl( + insert_pos->co, + parinv, + vert.position + ); + insert_pos ++; + vertex_it->Step(vertex_it->it); + } + + me->totvert = vertex_it->num_elements; + + // a hash table to remap materials to indices with + material_hash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp); + nmaterials = 0; + + while (!face_it->Done(face_it->it)) { + MFace *mface = &mfaces[fi_insert_pos]; + FaceData *fdata; + + face_it->Fill(face_it->it,&face); + + // cheat CSG never dumps out quads. + + mface->v1 = face.vertex_index[0]; + mface->v2 = face.vertex_index[1]; + mface->v3 = face.vertex_index[2]; + mface->v4 = 0; + + mface->edcode = ME_V1V2|ME_V2V3|ME_V3V4|ME_V4V1; + mface->puno = 0; + mface->mat_nr = 0; + mface->flag = 0; + + /* HACK, perform material to index mapping using a general + * hash table, just tuck the int into a void *. + */ + + fdata = face.user_face_data; + if (!BLI_ghash_haskey(material_hash, fdata->material)) { + int matnr = nmaterials++; + BLI_ghash_insert(material_hash, fdata->material, (void*) matnr); + assign_material(ob, fdata->material, matnr+1); + } + mface->mat_nr = (int) BLI_ghash_lookup(material_hash, fdata->material); + + // grab the vertex colors and texture cos and dump them into the tface. + + if (tfaces) { + TFace *tface= &tfaces[fi_insert_pos]; + int i; + + // copy all the tface settings back + tface->tpage = fdata->tpage; + tface->flag = fdata->flag; + tface->transp = fdata->transp; + tface->mode = fdata->mode; + tface->tile = fdata->tile; + + for (i=0; i<4; i++) { + FaceVertexData *fvdata = face.user_face_vertex_data[i]; + float *color = fvdata->color; + + tface->uv[i][0] = fvdata->uv[0]; + tface->uv[i][1] = fvdata->uv[1]; + tface->col[i] = + ((((unsigned int)floor(color[0] + 0.5f)) & 0xff) << 24) | + ((((unsigned int)floor(color[1] + 0.5f)) & 0xff) << 16) | + ((((unsigned int)floor(color[2] + 0.5f)) & 0xff) << 8) | + ((((unsigned int)floor(color[3] + 0.5f)) & 0xff) << 0); + } + + test_index_face(mface, tface, 3); + } else { + test_index_mface(mface, 3); + } + + fi_insert_pos++; + face_it->Step(face_it->it); + } + + BLI_ghash_free(material_hash, NULL, NULL); + + me->totface = face_it->num_elements; + // thats it! + + if (user_face_vertex_data) { + MEM_freeN(user_face_vertex_data); + } + MEM_freeN(face.user_face_data); + + return 1; +} + + void +BuildMeshDescriptors( + struct Object *ob, + struct CSG_FaceIteratorDescriptor * face_it, + struct CSG_VertexIteratorDescriptor * vertex_it +){ + VertexIt_Construct(vertex_it,ob); + FaceIt_Construct(face_it,ob); +} + + void +FreeMeshDescriptors( + struct CSG_FaceIteratorDescriptor *face_it, + struct CSG_VertexIteratorDescriptor *vertex_it +){ + VertexIt_Destruct(vertex_it); + FaceIt_Destruct(face_it); +} + |