#!BPY

"""
Name: 'MegaBool r2'
Blender: 234
Group: 'Object'
Tooltip: 'Perform boolean operations on meshes and get nice results'
"""

###################################################################
#                                                                 #
# Experimental New Mesh Boolean Operations                        #
#                                                                 #
# (C) 2004 Theodore K Schundler (tschundler)(@)(scu)(edu)         #
# FOR TESTING ONLY, not for redistribution                        #
# Lastest version available for from:                             #
# http://astro.scu.edu/~ted/oss/blender/boolean                   #
#                                                                 #
# USAGE:                                                          #
#   -By Menu-                                                     #
#     * Put this file in ~/.blender/scripts/                      #
#     * Select two objects, then choose "MegaBool" from the       #
#        scripts menu.                                            #
#   -By Running the script-                                       #
#     * Load this file into blender's internal text editor        #
#     * Select two objects, then press Alt+P in the test editor   #
#                                                                 #
# OPERATIONS:                                                     #
#   On execution of the script, there are four operations         #
#     * Intersect - Intersection of the two meshes (logical AND)  #
#     * Union - Union of the two meshes (logical OR)              #
#     * Difference - First selected mesh - Last selected mesh     #
#     * Cookie Cutter - First mesh's faces are subdivided where   #
#        they intersect with the second mesh                      #
#   After the script executes, all "inside" vertices are selected #
#                                                                 #
# IMPORTANT NOTES:                                                #
#   This script uses Blender's internal scan fill to fill faces.  #
# It does not have an official python interface *yet*, so I       #
# quickly hacked one together. A patch to the bf-blender cvs code #
# base is available at the URL above. Patch your blender source   #
# and recompile. Then this script will run. Without the patched   #
# blender this script will fail on "fillVertLoops".               #
#   Like any boolean algorith, normals on the source meshes must  #
# be all facing outside. To fix normals, select a mesh, enter     #
# edit mode, select all verticies, and press Ctrl+N. Also, all    #
# intersections must create closed loops. (Basically the meshes   #
# should be closed.) If you find a set of meshes that do not work #
# send me the .blend file and an explaination of the problem.     #
#                                                                 #
# TO DO:                                                          #
#  * After the operation, should probably translate results, so   #
#     the mesh isn't centered around <0,0,0>, use one of the base #
#     meshes instead                                              #
#  * Set materials, UVs, etc., on new mesh                        #
#  * Use correct normals on new mesh                              #
###################################################################
#                                                                 #
#  Date:        Updates:                                          #
#  16-Aug-2004  Initial Revision - working(?) & ready to go       #
#  17-Aug-2004  Fixed some bugs based on incorrect assumptions.   #
#                that means even more computation. Also made more #
#                use of the traversalCookies to speed up a some   #
#                sections                                         #
#                                                                 #
###################################################################



import Blender
from Blender import NMesh
from Blender import Object
from Blender import Draw
from Blender import Mathutils
from Blender.Mathutils import *

traversalCookie=0

#Mathutils doesn't like NMesh data, this makes it happy
def TransList(o):
	l=[]
	for a in o:
		l.append(a)
	return l


class CCVert:
	def __init__(self,nmVert,ccObject):
		global traversalCookie
		self.parentObject=ccObject
		if nmVert:
			self.counterPart=nmVert
			v=TransList(nmVert.co)
			vec=Mathutils.Vector(v)
			vec.resize4D()
			vec.w=1
			self.tco=Mathutils.VecMultMat(vec,ccObject.matrix)
			#self.tco=Mathutils.MatMultVex(vec,ccObject.matrix)
			self.tco.resize3D()
			#print vec,"->",self.tco
		else:
			self.tco=[0,0,0]
		self.inside=0
		self.outside=0
		self.neither=0
		self.traversalCookie=traversalCookie
		self.cutBy=[]
		self.cutFrom=[]
		self.edgeWith=[]
		#self.newIndex=0
		self.newCounterpart=0
		self.edgePos=0
		self.used=0
		#print "\tAdded Vertex: ", self.tco
	def DetermineSide(self,traversalCookie):
		return

class CCEdge:
	def __init__(self,v1,v2,ccObject):
		global traversalCookie
		self.parentObject=ccObject
		ccObject.edges.append(self)
		self.index=len(ccObject.edges)-1
		self.v=[v1,v2]
		#print "\t\tNew Edge[%d]: (v%d -> v%d)"%(self.index,v1.counterPart.index,v2.counterPart.index)

		v1.edgeWith.append([v2,self])
		v2.edgeWith.append([v1,self])

		self.faces=[]
		self.bb=[[v1.tco[0],v1.tco[1],v1.tco[2]],[v2.tco[0],v2.tco[1],v2.tco[2]]]
		for i in range(3):
			if self.bb[0][i]>self.bb[1][i]:
				t=self.bb[0][i]
				self.bb[0][i]=self.bb[1][i]
				self.bb[1][i]=t
		self.inside=0
		self.outside=0
		self.neither=0
		self.traversalCookie=traversalCookie
		self.real=[]

	def realize(self,newEdges,sweep):
		global traversalCookie
		v=self.v
		if len(v)==2:
			if sweep==1:
				return
			ne=CCEdge(v[0],v[1],self.parentObject)
			traversalCookie=traversalCookie+1
			FindVertexSide(v[0],traversalCookie)
			FindVertexSide(v[1],traversalCookie)
			if (v[0].outside!=v[0].inside):
				ne.outside=v[0].outside
				ne.inside=v[0].inside
				ne.neither=v[0].neither
			else:
				ne.outside=v[1].outside
				ne.inside=v[1].inside
				ne.neither=v[1].neither
			#v[0].edgeWith.append([v[1],self])
			#v[1].edgeWith.append([v[0],self])

			newEdges.append(ne)
		else:
			if sweep==2:
				return
			#if len(self.real)>1:
			#	print "teh leet"
			#	for e in self.real:
			#		newEdges.append(e)
			#	return
			vec=v[1].tco-v[0].tco
			nv=[]
			ep=[]
			for vtx in v:
				#vtx.edgePos=DotVecs(vtx.tco,vec)
				vtx.edgePos=(vtx.tco-v[0].tco).length
				ep.append(vtx.edgePos)
				nv.append(vtx)
			ep.sort()
			for vtx in v:
				nv[ep.index(vtx.edgePos)]=vtx
			#print "sort edges",nv[0].outside,nv[0].inside
			outside=nv[0].outside
			nv[0].inside=1-outside
			for n in range(1,len(nv)):
				ne=CCEdge(nv[n-1],nv[n],self.parentObject)
				#print self,"--",outside,"--",ne
				ne.outside=outside
				ne.inside=1-ne.outside
				nv[n-1].outside=nv[n-1].outside|outside
				nv[n-1].inside=nv[n-1].inside|ne.inside
				nv[n].outside=outside
				nv[n].inside=1-outside
				newEdges.append(ne)
				self.real.append(ne)
				outside=1-outside
			
			

	#add a vertex, and figure out if any others on the edge need to ne redefined as inside or outside
	def AddVert(self,v,normal):
		insideVec=[]
		insideL=(self.v[1].tco-self.v[0].tco).length
		outsideVec=[]
		outsideL=(self.v[1].tco-self.v[0].tco).length
		for vx in self.v:
			vec=vx.tco-v.tco
			if DotVecs(vec,normal)>0:
				if vec.length<outsideL:
					outsideVec=vx
					outsideL=vec.length
			else:
				if vec.length<insideL:
					insideVec=vx
					insideL=vec.length
		#if insideVec.outside!=insideVec.inside:
		insideVec.inside=1
		insideVec.outside=0
		#if outsideVec.outside!=outsideVec.inside:
		outsideVec.inside=0
		outsideVec.outside=1

		self.v.append(v)

		return


class CCFace:
	def addEdge(self, v1,v2):
		o1=self.parentObject.verts[v1.index]
		self.verts.append(o1)
		o2=self.parentObject.verts[v2.index]
		for ew in o1.edgeWith:
			if o2==ew[0]:
				self.edges.append(ew[1])
				ew[1].faces.append(self)
				return
		e=CCEdge(o1,o2,self.parentObject)
		self.edges.append(e)
		e.faces.append(self)
	def __init__(self,nmFace,ccObject):
		self.edges=[]
		self.verts=[]
		self.extraVerts=[]
		self.altered=0

		#print "\tAdding Face..."
		self.counterPart=nmFace

		v=TransList(nmFace.no)
		vec=Mathutils.Vector(v)
		#vec.resize4D()
		#vec.w=1
		self.normal=Mathutils.VecMultMat(vec,ccObject.matrix.rotationPart())
		#self.normal.resize3D()
		self.normal.normalize()

		self.parentObject=ccObject

		#Define bounding box
		#first fill base data
		self.bb=[[0,0,0],[0,0,0]]
		for i in range(3):
			self.bb[0][i]=ccObject.verts[nmFace.v[0].index].tco[i]
			self.bb[1][i]=self.bb[0][i]

		#then fill real data
		for vo in nmFace.v:
			v=ccObject.verts[vo.index].tco
			for i in range(3):
				#print i,":",self.bb[0][i],"<",v[i],"<",self.bb[1][i]
				if v[i]<self.bb[0][i]:
					self.bb[0][i]=v[i]
				if v[i]>self.bb[1][i]:
					self.bb[1][i]=v[i]

		#Add Edges
		self.addEdge(nmFace.v[0],nmFace.v[1])
		self.addEdge(nmFace.v[1],nmFace.v[2])
		if len(nmFace.v)==3:
			self.addEdge(nmFace.v[2],nmFace.v[0])
		else:
			self.addEdge(nmFace.v[2],nmFace.v[3])
			self.addEdge(nmFace.v[3],nmFace.v[0])
	def GetVertexSet(self):
		vs=[]
		for e in self.edges:
			for v in e.v:
				try:
					vs.index(v)
				except:
					vs.append(v)
		for v in self.extraVerts:
			try:
				vs.index(v)
			except:
				#try:
				#v.cutBy.index(self)
				#except:
				#print self,v
				vs.append(v)
		return vs

class CCObject:
	def __init__(self,blenderObject):
		self.counterPart=blenderObject
		print "Adding Object %s"%blenderObject.getName()

		#setup variables
		self.verts=[]
		self.faces=[]
		self.edges=[]

		#store some matrices for future use
		omtx=blenderObject.getMatrix()
		#print "OMTX:",omtx
		self.matrix=Mathutils.Matrix(TransList(omtx[0]),TransList(omtx[1]),TransList(omtx[2]),TransList(omtx[3]))
		#self.matrix.transpose()
		#print "SELF:",self
		
		print "\tAdding verts"
		#build up vertex list
		m=NMesh.GetRawFromObject(blenderObject.getName())
		self.nmesh=m
		for v in m.verts:
			self.verts.append([])
		#print "vtx: ",len(self.verts)
		for v in m.verts:
			self.verts[v.index]=CCVert(v,self)

		print "\tAdding Faces & Edges"
		#build up faces & edges
		for f in m.faces:
			if len(f.v)>2:
				self.faces.append(CCFace(f,self))


def TestPointInFaceInEdge(v,f,ed):
	ev=ed.v[1].tco-ed.v[0].tco
	vA=v-ed.v[0].tco
	d=vA.length
	d=DotVecs(vA,ev)
	if d<0 or vA.length>ev.length:
		return 0
	for e in f.edges:
		cp=CrossVecs(f.normal,e.v[1].tco-e.v[0].tco)
		for ew in e.v[0].edgeWith:
			if ew[0]!=e.v[1]:
				try:
					f.edges.index(ew[1])
					v2=ew[0].tco
				except:
					1
		d=DotVecs(cp,v2-e.v[0].tco)
		cp=cp*d
		cp.normalize()
		s=DotVecs((v-e.v[0].tco),cp)
		if s<0:
			return 0
	return 1

def	EdgeLoopVxLoop(el):
	global traversalCookie
	traversalCookie=traversalCookie+1
	vxl=[]
	for e in el:
		for v in e.v:
			if v.traversalCookie<traversalCookie:
#			try:
#				vxl.index(v)
#			except:
				v.traversalCookie=traversalCookie
				vxl.append(v)
	return SortVertexLoop(vxl,el)


def FindVertexSide(v,tc):
	#print "fvs"
	if v.outside==1:
		return 1
	elif v.inside==1:
		return 0
	elif v.neither==1:
		print "Predetermined NEITHER!!!!!!"
		return -1
	else:
		#don't know what side I'm on
		v.traversalCookie=tc
		if len(v.edgeWith)==0:
			print "DEAD POINT!!!!!!!!!!!!!!!"
		if len(v.edgeWith)>10:
			print "APEX!!! -- ", len(v.edgeWith)
		for ew in v.edgeWith:
			if ew[0].traversalCookie<tc:
				sv=FindVertexSide(ew[0],tc)
				#print "\t found",sv
				if sv==1:
					if len(v.edgeWith)>10:
						print "Apex Outside"
					v.outside=1
					return sv
				elif sv==0:
					if len(v.edgeWith)>10:
						print "Apex Inside"
					v.inside=1
					return sv
				#else:
				#	print "NEITHER@!!!!!!!!!!!!!!!!!!!!!!!"
				#	v.neither=1
		#if loop failed, this must be floating out in space somewhere
		#v.neither=1
		if len(v.edgeWith)>10:
			print "APEX died"
		else:
			print "died...",tc
		return -1

def FindEdgeSide(e,tc):
	if e.inside==0 and e.outside==0 and e.neither==0:
		v1=FindVertexSide(e.v[0],tc)
		v2=FindVertexSide(e.v[1],tc)
		if v1<0 or v2<0:
			e.outside=1
			return 1
		#print "findlike ",v1,"--",v2
		if v1==v2:
			if v1==1:
				e.outside=1
			elif v1==0:
				e.inside=1
			else:
				e.neither=1
		else:
			e.neither=1
	if e.neither==1:
		return 0
	elif e.inside==1 and e.outside==1:
		return 3
	elif e.inside==1:
		return 2
	else:
		return 1

def FindVertex(vtx,vxlist):
	for v in vxlist:
		m=0
		for n in range(3):
			if v.tco[n]==vtx[n]:
				m=m+1
		if m==3:
				return v
	print "Failed to find vertex ",vtx
	return []

def	SortVertexLoop(vs,es):
		global traversalCookie
		#traversalCookie=traversalCookie+1
		vx=[vs[0]]
		print "Sort ",len(vs)," verts"
		for n in range(0,len(vs)-1):
			#if n==len(vx):
			#	print "SCRIPT FAILED!!!!"
			#	return []
			print "try ",n,":",vx[n].tco,", options: ",len(vx[n].edgeWith)
			for ew in vx[n].edgeWith:
				#print "\t",ew[0].tco
				try:
					vx.index(ew[0])
				except:
					try:
						es.index(ew[1])
						vs.index(ew[0])
						vx.append(ew[0])
						#ew[0].traversalCookie=traversalCookie
						break
					except:
						1
		return vx


def MakeEdgeLoop(loop,edge,inside,outside,tc):
	for v in edge.v:
		for ew in v.edgeWith:
			if ew[1].inside>=inside and ew[1].outside>=outside:
				if ew[1].traversalCookie<tc:
					ew[1].traversalCookie=tc
					loop.append(ew[1])
					MakeEdgeLoop(loop,ew[1],inside,outside,tc)


def MakeFace(nm,f,vs,inside,outside,simple=0):
	global traversalCookie
	mode=0
	
	if len(vs)<3:
		1
		#return traversalCookie
	elif len(vs)==3 and 0:
		for v in vs:
			if (v.outside<outside or v.inside<inside) and not (outside==1 and v.neither==1):
				#print "\t Rejected"
				#return traversalCookie
				1
		for v in vs:
			if v.used==0:
				if v.inside:
					v.newCounterpart.sel=1
				nm.verts.append(v.newCounterpart)
			v.used=1
		#print "Adding Tri"
		nf=NMesh.Face([vs[0].newCounterpart,vs[1].newCounterpart,vs[2].newCounterpart])
		nf.smooth=f.counterPart.smooth
		nm.faces.append(nf)
		return
	elif len(vs)>3 or 1:

		el=[]

		if (simple==0):
			#add edges of original face
			for	e in f.edges:
				e.realize(el,1)
			for	e in f.edges:
				e.realize(el,2)
			f.edges=el

		if (len(vs)==4 or len(vs)==3) and simple==1:
			if inside!=outside:
				for v in vs:
					if (v.outside<outside or v.inside<inside):# and not (outside==1 and v.neither==1):
						return
			#print "Adding Quad"
			for v in vs:
				if v.used==0:
					if v.inside:
						v.newCounterpart.sel=1
					nm.verts.append(v.newCounterpart)
				v.used=1
			if simple==1:
				vx=vs
			else:
				vx=SortVertexLoop(vs,f.edges)
			if len(vs)==3:
				nf=NMesh.Face([vx[0].newCounterpart,vx[1].newCounterpart,vx[2].newCounterpart])
			else:
				nf=NMesh.Face([vx[0].newCounterpart,vx[1].newCounterpart,vx[2].newCounterpart,vx[3].newCounterpart])
			nf.smooth=f.counterPart.smooth
			nm.faces.append(nf)
			return traversalCookie	
		else:

			#add edges cut into face
			tc=traversalCookie
			tc=tc+1
			for vA in vs:
				if vA.traversalCookie<tc:
					vA.traversalCookie=tc
					for cfA in vA.cutBy:
						#we only care about stuff cut by the other object
						if cfA.parentObject!=f.parentObject:
							for vB in vs:
								if vB.traversalCookie<tc:
									for cfB in vB.cutBy:
										if cfA==cfB:
											ne=CCEdge(vA,vB,f.parentObject)
											#print ne,vA.tco,vB.tco
											ne.inside=1
											ne.outside=1
											f.edges.append(ne)

			#Determine what side the edges are on
			tc=tc+1
			et=[0,0,0,0]
			for e in f.edges:
				n=FindEdgeSide(e,tc)
				et[n]=et[n]+1
			#print "ETETET: ",et

			tc=tc+1
			btc=tc
			insideLoops=[]
			for eA in f.edges:
				if eA.inside==1 and eA.outside==0:
					if eA.traversalCookie<tc:
						eA.traversalCookie=tc
						newLoop=[eA]
						MakeEdgeLoop(newLoop,eA,1,0,tc)
						insideLoops.append(newLoop)
			
			tc=tc+1
			outsideLoops=[]
			for eA in f.edges:
				if eA.inside==0 and eA.outside==1:
					if eA.traversalCookie<tc:
						eA.traversalCookie=tc
						newLoop=[eA]
						MakeEdgeLoop(newLoop,eA,0,1,tc)
						outsideLoops.append(newLoop)

			sharedLoops=[]			
			for eA in f.edges:
				if eA.traversalCookie<btc:
					eA.traversalCookie=tc
					newLoop=[eA]
					#print eA.inside,"==",eA.outside
					MakeEdgeLoop(newLoop,eA,0,0,tc)
					sharedLoops.append(newLoop)

			#print "Loops: Inside ",insideLoops,", Outside ",outsideLoops,", Shared ",sharedLoops
			print "Loops: Inside ",len(insideLoops),", Outside ",len(outsideLoops),", Shared ",len(sharedLoops)
			traversalCookie=tc

			if mode==1:
				for e in f.edges:
					if e.outside==1:
						for v in e.v:
							if v.used==0:
								if v.inside:
									v.newCounterpart.sel=1
								nm.verts.append(v.newCounterpart)
							v.used=1
						nm.faces.append(NMesh.Face([e.v[0].newCounterpart,e.v[1].newCounterpart]))
				return tc


			#test for loop heirarchies

			if (outside):
				outloops=[]
				for le in outsideLoops:
					vxl=EdgeLoopVxLoop(le)
					vl2=[]
					for vx in vxl:
						 vl2.append([vx.tco[0],vx.tco[1],vx.tco[2]])
					outloops.append(vl2)
				for le in sharedLoops:
					vxl=EdgeLoopVxLoop(le)
					vl2=[]
					for vx in vxl:
						 vl2.append([vx.tco[0],vx.tco[1],vx.tco[2]])
					outloops.append(vl2)

				#Do the filling
				fvl=nm.fillVertLoops(outloops)

				#Make the faces
				for vl in fvl:
					fvx=[]
					for	vp in vl:
						v=FindVertex(vp,vs)
						fvx.append(v.newCounterpart)
						if v.used==0:
							if v.inside:
								v.newCounterpart.sel=1
							nm.verts.append(v.newCounterpart)
						v.used=1
						v.outside=1
					nf=NMesh.Face(fvx)
					nf.smooth=f.counterPart.smooth
					nm.faces.append(nf)

			#traversalCookie=traversalCookie+1

			if (inside):
				inloops=[]
				for le in insideLoops:
					vxl=EdgeLoopVxLoop(le)
					if len(vxl):
						vl2=[]
						for vx in vxl:
							 vl2.append([vx.tco[0],vx.tco[1],vx.tco[2]])
						inloops.append(vl2)
				for le in sharedLoops:
					vxl=EdgeLoopVxLoop(le)
					if len(vxl):
						vl2=[]
						for vx in vxl:
							 vl2.append([vx.tco[0],vx.tco[1],vx.tco[2]])
						inloops.append(vl2)

				#Do the filling
				fvl=nm.fillVertLoops(inloops)

				#Make the faces
				for vl in fvl:
					fvx=[]
					for	vp in vl:
						v=FindVertex(vp,vs)
						fvx.append(v.newCounterpart)
						if v.used==0:
							if v.inside:
								v.newCounterpart.sel=1
							nm.verts.append(v.newCounterpart)
						v.used=1
						v.inside=1
					nf=NMesh.Face(fvx)
					nf.smooth=f.counterPart.smooth
					nm.faces.append(nf)

			#for e in f.edges:
			#	for	v in e.v:
			#		if v.used==0:
			#			nm.verts.append(v.newCounterpart)
			#		v.used=1
			#	nm.faces.append(NMesh.Face([e.v[0],e.v[1]]))
				
		

class CCNewMesh:
	def __init__(self):
		self.nm=NMesh.New()
		self.verts=[]
	def addObject(self,object,inside,outside):
		global traversalCookie
		for f in object.faces:
			#print "Adding Face"
			#if f.altered==0:
				#print "unaltered"
				#if (inside==outside):
				#	self.traversalCookie=MakeFace(self.nm,f,f.verts,self.traversalCookie,inside,outside,1)
			if f.altered==1:
				vs=f.GetVertexSet()
				for v in vs:
					#add new mesh couterpart if applicable
					if not v.newCounterpart:
						self.verts.append(v)
						#v.newIndex=self.verts.index(v)
						v.newCounterpart=NMesh.Vert(v.tco[0],v.tco[1],v.tco[2])
					#clear potentially bad edge data
					v.edgeWith=[]

				MakeFace(self.nm,f,vs,inside,outside)

		#if inside/outside matters, to another pass
		if inside!=outside or 1:
			print "Pass two!"
			print "\tCalculating sides...", traversalCookie

			traversalCookie=traversalCookie+1
			#for f in object.faces:
			#		for v in f.verts:
			#			v.edgeWith=[]

			#traversalCookie=traversalCookie+1
			#for f in object.faces:
			#		for e in f.edges:
			#			if e.traversalCookie<traversalCookie:
			#				e.v[0].edgeWith.append([e.v[1],e])
			#				e.v[1].edgeWith.append([e.v[0],e])
			#				e.traversalCookie=traversalCookie

			for f in object.faces:
					for v in f.verts:
						#v.edgeWith=[]
						if f.altered==0:
							FindVertexSide(v,traversalCookie)

			print "\tAdding faces"
			for f in object.faces:
				if f.altered==0:
					#vs=f.GetVertexSet()
					vs=f.verts
					for v in vs:
						traversalCookie=traversalCookie+1
						s=FindVertexSide(v,traversalCookie)
						if (s==-1):
							v.neither=1
							print "NEITHER!"
						if not v.newCounterpart:
							self.verts.append(v)
							#v.newIndex=self.verts.index(v)
							v.newCounterpart=NMesh.Vert(v.tco[0],v.tco[1],v.tco[2])
					#if len(f.verts)>3:
					MakeFace(self.nm,f,vs,inside,outside,1)
			
			


print "Running Megabool!"

objsel=Object.GetSelected()

def TestBounds(b1,b2):
	#return 1
	b0=[[0,0,0],[0,0,0]]
	for i in range(3):
		#Lower bound?
		b0[0][i]=b1[0][i]
		if b0[0][i]<b2[0][i]:
			b0[0][i]=b2[0][i]
		#Upper bound?
		b0[1][i]=b1[1][i]
		if b0[1][i]>b2[1][i]:
			b0[1][i]=b2[1][i]

		if b0[1][i]<b0[0][i]:
			return 0
	return 1

def CutEdges(cookie,cutter):
	print "cutting edges in ",cookie.counterPart.getName()
	for e in cookie.edges:
		for f in cutter.faces:
			#first do a quick bounding box test
			if TestBounds(e.bb,f.bb)==1:
				#define the plane using a normal and one point
				p_normal=f.normal
				p_point=f.edges[0].v[0].tco

				#define the edge with two points
				e_point1=e.v[0].tco
				e_point2=e.v[1].tco
				e_vect=e_point2-e_point1

				#test for intersection
				d=DotVecs(p_normal,e_vect)
				if d!=0:
					n=DotVecs(p_normal,p_point-e_point1)
					intersect=e_point1+(n/d)*e_vect

					#do some more testing!
					if TestPointInFaceInEdge(intersect,f,e)==1:

						#build new vertex
						ip=CCVert(0,cookie)
						ip.tco=intersect
						ip.cutBy.append(f)
						cookie.verts.append(ip)
						ip.index=len(cookie.verts)-1
						ip.outside=1
						ip.inside=1

						#setup inside vs outside
						#for v in e.v:
						#	if v.inside==0 and v.outside==0:
						#		v.outside=1
						#for fe in f.edges:
						#	for v in fe.v:
						#		if v.inside==0 and v.outside==0:
						#			v.outside=1

						#add vertex to edge, fixing inside vs outside as need be
						e.AddVert(ip,p_normal)

						#mark faces as changed
						for ef in e.faces:
							ef.altered=1
							ip.cutBy.append(ef)

						#add vertex to face
						f.extraVerts.append(ip)
						f.altered=1

						#all done
						#print ip.index,"::",intersect


def CookieCutter(cookie,cutter):
	x=Draw.PupMenu("Faces to keep%t|Keep all|Inside only|Outside Only")
	if x<1:
		return
	ccCookie=CCObject(cookie)
	ccCutter=CCObject(cutter)
	CutEdges(ccCookie,ccCutter)
	CutEdges(ccCutter,ccCookie)
	nmObject=CCNewMesh()

	if x==1:
		nmObject.addObject(ccCookie,1,1)
	elif x==2:
		nmObject.addObject(ccCookie,1,0)
	elif x==3:
		nmObject.addObject(ccCookie,0,1)

	nmObject.nm.mode=ccCookie.nmesh.mode;
	NMesh.PutRaw(nmObject.nm);
	return

def Difference(cookie,cutter):
	ccCookie=CCObject(cookie)
	ccCutter=CCObject(cutter)
	CutEdges(ccCookie,ccCutter)
	CutEdges(ccCutter,ccCookie)
	nmObject=CCNewMesh()
	nmObject.addObject(ccCookie,0,1)
	nmObject.addObject(ccCutter,1,0)
	nmObject.nm.mode=ccCookie.nmesh.mode;
	NMesh.PutRaw(nmObject.nm);
	return

def Intersection(cookie,cutter):
	ccCookie=CCObject(cookie)
	ccCutter=CCObject(cutter)
	CutEdges(ccCookie,ccCutter)
	CutEdges(ccCutter,ccCookie)
	nmObject=CCNewMesh()
	nmObject.addObject(ccCookie,1,0)
	nmObject.addObject(ccCutter,1,0)
	nmObject.nm.mode=ccCookie.nmesh.mode;
	NMesh.PutRaw(nmObject.nm,"foo");
	return

def Union(cookie,cutter):
	ccCookie=CCObject(cookie)
	ccCutter=CCObject(cutter)
	CutEdges(ccCookie,ccCutter)
	CutEdges(ccCutter,ccCookie)
	nmObject=CCNewMesh()
	nmObject.addObject(ccCookie,0,1)
	nmObject.addObject(ccCutter,0,1)
	nmObject.nm.mode=ccCookie.nmesh.mode;
	NMesh.PutRaw(nmObject.nm);
	return

def DoBool():
	#Check the sanity of the selection
	objsel=Object.GetSelected()
	meshes=0
	for ob in objsel:
		if ob.getType() == 'Mesh':
			meshes += 1
	if meshes!=2 :
		Draw.PupMenu("ERROR: Exactly two mesh objects must be selected")
		return
	x=Draw.PupMenu("MegaBool%t|1: Intersect|2: Union|3: Difference|4: Cookie Cutter")
	#print x
	if x==1:
		Intersection(objsel[1],objsel[0])
	elif x==2:
		Union(objsel[1],objsel[0])
	elif x==3:
		Difference(objsel[1],objsel[0])
	elif x==4:
		CookieCutter(objsel[1],objsel[0])

DoBool()
print "Done."