MOD_boolean_util.c

Go to the documentation of this file.

/*
 * $Id: MOD_boolean_util.c 35178 2011-02-25 13:57:17Z jesterking $
 *
 * ***** BEGIN GPL 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.
 *
 * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * The Original Code is Copyright (C) Blender Foundation
 * All rights reserved.
 *
 * The Original Code is: all of this file.
 *
 * Contributor(s): none yet.
 *
 * ***** END GPL LICENSE BLOCK *****
 * CSG operations. 
 */

#include "DNA_material_types.h"
#include "DNA_mesh_types.h"
#include "DNA_meshdata_types.h"
#include "DNA_object_types.h"
#include "DNA_scene_types.h"

#include "MEM_guardedalloc.h"

#include "BLI_math.h"
#include "BLI_utildefines.h"
#include "BLI_ghash.h"

#include "BKE_cdderivedmesh.h"
#include "BKE_depsgraph.h"
#include "BKE_material.h"
#include "BKE_mesh.h"
#include "BKE_object.h"

#include "CSG_BooleanOps.h"

#include "MOD_boolean_util.h"

typedef struct {
        DerivedMesh *dm;
        Object *ob;
        int pos;
} VertexIt;

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->dm->getNumVerts(iterator->dm));
}

static void VertexIt_Fill(CSG_IteratorPtr it, CSG_IVertex *vert)
{
        VertexIt * iterator = (VertexIt *)it;
        MVert *verts = iterator->dm->getVertArray(iterator->dm);

        float global_pos[3];

        /* boolean happens in global space, transform both with obmat */
        mul_v3_m4v3(
                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, DerivedMesh *dm, 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->dm = dm;
        it->ob = ob; // needed for obmat transformations 
        
        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->dm->getNumVerts(it->dm);
        output->it = it;
}

typedef struct {
        DerivedMesh *dm;
        int pos;
        int offset;
        int flip;
} 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->dm->getNumFaces(iterator->dm));
}

static void FaceIt_Fill(CSG_IteratorPtr it, CSG_IFace *face)
{
        // assume CSG_IteratorPtr is of the correct type.
        FaceIt *face_it = (FaceIt *)it;
        MFace *mfaces = face_it->dm->getFaceArray(face_it->dm);
        MFace *mface = &mfaces[face_it->pos];

        /* reverse face vertices if necessary */
        face->vertex_index[1] = mface->v2;
        if( face_it->flip == 0 ) {
        face->vertex_index[0] = mface->v1;
        face->vertex_index[2] = mface->v3;
        } else {
                face->vertex_index[2] = mface->v1;
                face->vertex_index[0] = mface->v3;
        }
        if (mface->v4) {
                face->vertex_index[3] = mface->v4;
                face->vertex_number = 4;
        } else {
                face->vertex_number = 3;
        }

        face->orig_face = face_it->offset + face_it->pos;
}

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, DerivedMesh *dm, int offset, 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->dm = dm;
        it->offset = offset;
        it->pos = 0;

        /* determine if we will need to reverse order of face vertices */
        if (ob->size[0] < 0.0f) {
                if (ob->size[1] < 0.0f && ob->size[2] < 0.0f) {
                        it->flip = 1;
                } else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) {
                        it->flip = 1;
                } else {
                        it->flip = 0;
                }
        } else {
                if (ob->size[1] < 0.0f && ob->size[2] < 0.0f) {
                        it->flip = 0;
                } else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) {
                        it->flip = 0;
                } else {
                        it->flip = 1;
                }
        }

        // assign iterator function pointers.
        output->Step = FaceIt_Step;
        output->Fill = FaceIt_Fill;
        output->Done = FaceIt_Done;
        output->Reset = FaceIt_Reset;
        output->num_elements = it->dm->getNumFaces(it->dm);
        output->it = it;
}

static Object *AddNewBlenderMesh(Scene *scene, Base *base)
{
        // This little function adds a new mesh object to the blender object list
        // It uses ob to duplicate data as this seems to be easier than creating
        // a new one. This new oject contains no faces nor vertices.
        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(&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("Mesh");

        // Finally assign the object type.
        ob_new->type= OB_MESH;

        return ob_new;
}

static void InterpCSGFace(
        DerivedMesh *dm, DerivedMesh *orig_dm, int index, int orig_index, int nr,
        float mapmat[][4])
{
        float obco[3], *co[4], *orig_co[4], w[4][4];
        MFace *mface, *orig_mface;
        int j;

        mface = CDDM_get_face(dm, index);
        orig_mface = orig_dm->getFaceArray(orig_dm) + orig_index;

        // get the vertex coordinates from the original mesh
        orig_co[0] = (orig_dm->getVertArray(orig_dm) + orig_mface->v1)->co;
        orig_co[1] = (orig_dm->getVertArray(orig_dm) + orig_mface->v2)->co;
        orig_co[2] = (orig_dm->getVertArray(orig_dm) + orig_mface->v3)->co;
        orig_co[3] = (orig_mface->v4)? (orig_dm->getVertArray(orig_dm) + orig_mface->v4)->co: NULL;

        // get the vertex coordinates from the new derivedmesh
        co[0] = CDDM_get_vert(dm, mface->v1)->co;
        co[1] = CDDM_get_vert(dm, mface->v2)->co;
        co[2] = CDDM_get_vert(dm, mface->v3)->co;
        co[3] = (nr == 4)? CDDM_get_vert(dm, mface->v4)->co: NULL;

        for (j = 0; j < nr; j++) {
                // get coordinate into the space of the original mesh
                if (mapmat)
                        mul_v3_m4v3(obco, mapmat, co[j]);
                else
                        copy_v3_v3(obco, co[j]);

                interp_weights_face_v3( w[j],orig_co[0], orig_co[1], orig_co[2], orig_co[3], obco);
        }

        CustomData_interp(&orig_dm->faceData, &dm->faceData, &orig_index, NULL, (float*)w, 1, index);
}

/* Iterate over the CSG Output Descriptors and create a new DerivedMesh
   from them */
static DerivedMesh *ConvertCSGDescriptorsToDerivedMesh(
        CSG_FaceIteratorDescriptor *face_it,
        CSG_VertexIteratorDescriptor *vertex_it,
        float parinv[][4],
        float mapmat[][4],
        Material **mat,
        int *totmat,
        DerivedMesh *dm1,
        Object *ob1,
        DerivedMesh *dm2,
        Object *ob2)
{
        DerivedMesh *result, *orig_dm;
        GHash *material_hash = NULL;
        Mesh *me1= (Mesh*)ob1->data;
        Mesh *me2= (Mesh*)ob2->data;
        int i;

        // create a new DerivedMesh
        result = CDDM_new(vertex_it->num_elements, 0, face_it->num_elements);
        CustomData_merge(&dm1->faceData, &result->faceData, CD_MASK_DERIVEDMESH,
                                          CD_DEFAULT, face_it->num_elements); 
        CustomData_merge(&dm2->faceData, &result->faceData, CD_MASK_DERIVEDMESH,
                                          CD_DEFAULT, face_it->num_elements); 

        // step through the vertex iterators:
        for (i = 0; !vertex_it->Done(vertex_it->it); i++) {
                CSG_IVertex csgvert;
                MVert *mvert = CDDM_get_vert(result, i);

                // retrieve a csg vertex from the boolean module
                vertex_it->Fill(vertex_it->it, &csgvert);
                vertex_it->Step(vertex_it->it);

                // we have to map the vertex coordinates back in the coordinate frame
                // of the resulting object, since it was computed in world space
                mul_v3_m4v3(mvert->co, parinv, csgvert.position);
        }

        // a hash table to remap materials to indices
        if (mat) {
                material_hash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "CSG_mat gh");
                *totmat = 0;
        }

        // step through the face iterators
        for(i = 0; !face_it->Done(face_it->it); i++) {
                Mesh *orig_me;
                Object *orig_ob;
                Material *orig_mat;
                CSG_IFace csgface;
                MFace *mface;
                int orig_index, mat_nr;

                // retrieve a csg face from the boolean module
                face_it->Fill(face_it->it, &csgface);
                face_it->Step(face_it->it);

                // find the original mesh and data
                orig_ob = (csgface.orig_face < dm1->getNumFaces(dm1))? ob1: ob2;
                orig_dm = (csgface.orig_face < dm1->getNumFaces(dm1))? dm1: dm2;
                orig_me = (orig_ob == ob1)? me1: me2;
                orig_index = (orig_ob == ob1)? csgface.orig_face: csgface.orig_face - dm1->getNumFaces(dm1);

                // copy all face layers, including mface
                CustomData_copy_data(&orig_dm->faceData, &result->faceData, orig_index, i, 1);

                // set mface
                mface = CDDM_get_face(result, i);
                mface->v1 = csgface.vertex_index[0];
                mface->v2 = csgface.vertex_index[1];
                mface->v3 = csgface.vertex_index[2];
                mface->v4 = (csgface.vertex_number == 4)? csgface.vertex_index[3]: 0;

                // set material, based on lookup in hash table
                orig_mat= give_current_material(orig_ob, mface->mat_nr+1);

                if (mat && orig_mat) {
                        if (!BLI_ghash_haskey(material_hash, orig_mat)) {
                                mat[*totmat] = orig_mat;
                                mat_nr = mface->mat_nr = (*totmat)++;
                                BLI_ghash_insert(material_hash, orig_mat, SET_INT_IN_POINTER(mat_nr));
                        }
                        else
                                mface->mat_nr = GET_INT_FROM_POINTER(BLI_ghash_lookup(material_hash, orig_mat));
                }
                else
                        mface->mat_nr = 0;

                InterpCSGFace(result, orig_dm, i, orig_index, csgface.vertex_number,
                                          (orig_me == me2)? mapmat: NULL);

                test_index_face(mface, &result->faceData, i, csgface.vertex_number);
        }

        if (material_hash)
                BLI_ghash_free(material_hash, NULL, NULL);

        CDDM_calc_edges(result);
        CDDM_calc_normals(result);

        return result;
}
        
static void BuildMeshDescriptors(
        struct DerivedMesh *dm,
        struct Object *ob,
        int face_offset,
        struct CSG_FaceIteratorDescriptor * face_it,
        struct CSG_VertexIteratorDescriptor * vertex_it)
{
        VertexIt_Construct(vertex_it,dm, ob);
        FaceIt_Construct(face_it,dm,face_offset,ob);
}
        
static void FreeMeshDescriptors(
        struct CSG_FaceIteratorDescriptor *face_it,
        struct CSG_VertexIteratorDescriptor *vertex_it)
{
        VertexIt_Destruct(vertex_it);
        FaceIt_Destruct(face_it);
}

static DerivedMesh *NewBooleanDerivedMesh_intern(
        DerivedMesh *dm, struct Object *ob, DerivedMesh *dm_select, struct Object *ob_select,
        int int_op_type, Material **mat, int *totmat)
{

        float inv_mat[4][4];
        float map_mat[4][4];

        DerivedMesh *result = NULL;

        if (dm == NULL || dm_select == NULL) return 0;
        if (!dm->getNumFaces(dm) || !dm_select->getNumFaces(dm_select)) return 0;

        // we map the final object back into ob's local coordinate space. For this
        // we need to compute the inverse transform from global to ob (inv_mat),
        // and the transform from ob to ob_select for use in interpolation (map_mat)
        invert_m4_m4(inv_mat, ob->obmat);
        mul_m4_m4m4(map_mat, ob_select->obmat, inv_mat);
        invert_m4_m4(inv_mat, ob_select->obmat);

        {
                // interface with the boolean module:
                //
                // the idea is, we pass the boolean module verts and faces using the
                // provided descriptors. once the boolean operation is performed, we
                // get back output descriptors, from which we then build a DerivedMesh

                CSG_VertexIteratorDescriptor vd_1, vd_2;
                CSG_FaceIteratorDescriptor fd_1, fd_2;
                CSG_OperationType op_type;
                CSG_BooleanOperation *bool_op;

                // work out the operation they chose and pick the appropriate 
                // enum from the csg module.
                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;
                }
                
                BuildMeshDescriptors(dm_select, ob_select, 0, &fd_1, &vd_1);
                BuildMeshDescriptors(dm, ob, dm_select->getNumFaces(dm_select) , &fd_2, &vd_2);

                bool_op = CSG_NewBooleanFunction();

                // perform the operation
                if (CSG_PerformBooleanOperation(bool_op, op_type, fd_1, vd_1, fd_2, vd_2)) {
                        CSG_VertexIteratorDescriptor vd_o;
                        CSG_FaceIteratorDescriptor fd_o;

                        CSG_OutputFaceDescriptor(bool_op, &fd_o);
                        CSG_OutputVertexDescriptor(bool_op, &vd_o);

                        // iterate through results of operation and insert
                        // into new object
                        result = ConvertCSGDescriptorsToDerivedMesh(
                                &fd_o, &vd_o, inv_mat, map_mat, mat, totmat, dm_select, ob_select, dm, ob);

                        // free up the memory
                        CSG_FreeVertexDescriptor(&vd_o);
                        CSG_FreeFaceDescriptor(&fd_o);
                }
                else
                        printf("Unknown internal error in boolean");

                CSG_FreeBooleanOperation(bool_op);

                FreeMeshDescriptors(&fd_1, &vd_1);
                FreeMeshDescriptors(&fd_2, &vd_2);
        }

        return result;
}

int NewBooleanMesh(Scene *scene, Base *base, Base *base_select, int int_op_type)
{
        Mesh *me_new;
        int a, maxmat, totmat= 0;
        Object *ob_new, *ob, *ob_select;
        Material **mat;
        DerivedMesh *result;
        DerivedMesh *dm_select;
        DerivedMesh *dm;

        ob= base->object;
        ob_select= base_select->object;

        dm = mesh_get_derived_final(scene, ob, CD_MASK_BAREMESH);
        dm_select = mesh_create_derived_view(scene, ob_select, 0); // no modifiers in editmode ??

        maxmat= ob->totcol + ob_select->totcol;
        mat= (Material**)MEM_mallocN(sizeof(Material*)*maxmat, "NewBooleanMeshMat");
        
        /* put some checks in for nice user feedback */
        if (dm == NULL || dm_select == NULL) return 0;
        if (!dm->getNumFaces(dm) || !dm_select->getNumFaces(dm_select))
        {
                MEM_freeN(mat);
                return -1;
        }
        
        result= NewBooleanDerivedMesh_intern(dm, ob, dm_select, ob_select, int_op_type, mat, &totmat);

        if (result == NULL) {
                MEM_freeN(mat);
                return 0;
        }

        /* create a new blender mesh object - using 'base' as  a template */
        ob_new= AddNewBlenderMesh(scene, base_select);
        me_new= ob_new->data;

        DM_to_mesh(result, me_new);
        result->release(result);

        dm->release(dm);
        dm_select->release(dm_select);

        /* add materials to object */
        for (a = 0; a < totmat; a++)
                assign_material(ob_new, mat[a], a+1);

        MEM_freeN(mat);

        /* update dag */
        DAG_id_tag_update(&ob_new->id, OB_RECALC_DATA);

        return 1;
}

DerivedMesh *NewBooleanDerivedMesh(DerivedMesh *dm, struct Object *ob, DerivedMesh *dm_select, struct Object *ob_select,
                                                                   int int_op_type)
{
        return NewBooleanDerivedMesh_intern(dm, ob, dm_select, ob_select, int_op_type, NULL, NULL);
}