path: root/source/blender/src/booleanops.c

#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);
}