#!BPY

"""
Name: 'MegaBool r4'
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 algorithm, 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                                         #
#  24-Aug-2004  Smart filling & other stuff...                    #
#  26-Aug-2004  Much cleanup, nothing new / fancy                 #
#                                                                 #
###################################################################



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

traversalCookie=0
messages=""

class CCVert:
	#intialize our vertex object
	def __init__(self,nmVert,ccObject):
		global traversalCookie
		self.parentObject=ccObject
		if nmVert:
			self.counterPart=nmVert
			v=list(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.edgeWith=[]
		self.newCounterpart=0
		self.used=0
		#print "\tAdded Vertex: ", self.tco

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)

		#Make notes on points for building loops later
		v1.edgeWith.append([v2,self])
		v2.edgeWith.append([v1,self])

		self.faces=[]

		#define a bounding box for fast intersection testing
		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

	def findSide(self):
		global traversalCookie
		ne=self
		v=self.v
		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

	def realize(self,newEdges,sweep,face):
		
		global traversalCookie
		v=self.v
		if len(v)==2:
			if sweep==1:
				return
		else:
			if sweep==2:
				return

		vA=face.verts.index(self.v[0])
		vB=face.verts.index(self.v[1])
		dir=0
		if vB!=(vA+1)%len(face.edges):
			#print "SD: ",vA,vB
			dir=1

		if len(v)==2:
			if dir:
				ne=CCEdge(v[1],v[0],self.parentObject)
			else:
				ne=CCEdge(v[0],v[1],self.parentObject)
			#v[0].edgeWith.append([v[1],self])
			#v[1].edgeWith.append([v[0],self])
			ne.findSide()
			newEdges.append(ne)
			return 0
		else:
			vec=v[1].tco-v[0].tco
			nv=[]
			ep=[]

			#Sort points a long the edge
			#if AddVert (below) inserts new verts in the right place, we can avoid this
			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

			#Make new edges
			outside=nv[0].outside
			nv[0].inside=1-outside
			for n in range(1,len(nv)):
				if dir:
					ne=CCEdge(nv[n],nv[n-1],self.parentObject)
				else:
					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)
				outside=1-outside

			return 1
			

	#add a vertex, and figure out if any others on the edge need to ne redefined as inside or outside
	#For the real implementation, this should probably be a linked list, and it should add itself in the right place and adjust prev and next accordingly
	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

		vec=Mathutils.Vector(list(nmFace.no))
		self.normal=Mathutils.VecMultMat(vec,ccObject.matrix.rotationPart())
		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])

	#this can probably be more directly integrated into the filling function
	#to yeild more optimized results (for example, all the extraverts are shared,
	#so they won't be the starting point for inside or outside loops, so when
	#building those loops, we don't need to bother with them
	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(list(omtx[0]),list(omtx[1]),list(omtx[2]),list(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 TestPointSideOfLine(point,v0,v1,normal):
	#Note: Maybe I should store the edge's normal on the edge?
	#This function gets called from different loops, so it may be worth it
	cp=CrossVecs(normal,v1-v0)
	s=DotVecs(point-v0,cp)
	if s < 0:
		return 0
	else:
		return 1


#test if a point is within the edges of a convex face
def TestPointInFace(p,f):
	vcount=len(f.verts)
	lastv=f.verts[vcount-1]
	for v in f.verts:
		if not TestPointSideOfLine(p,lastv.tco,v.tco,f.normal):
			return 0
		lastv=v
	return 1


def TestPointInEdge(v,vl):
	ev=vl[1].tco-vl[0].tco
	vA=v-vl[0].tco
	d=DotVecs(vA,ev)
	if d<0 or vA.length>ev.length:
		return 0
	return 1


def TestPointInFaceInEdge(v,f,ed):
	if not TestPointInEdge(v,ed.v):
		return 0
	if not TestPointInFace(v,f):
		return 0
	return 1

#Make a list of points out of a list of edges
def	EdgeLoopVxLoop(el):
	global traversalCookie
	traversalCookie=traversalCookie+1
	vxl=[]
	for e in el:
		for v in e.v:
			if v.traversalCookie<traversalCookie:
				v.traversalCookie=traversalCookie
				vxl.append(v)
	return vxl


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!!!!!!!!!!!!!!!"
		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
		return -1

#this is needed in cases where none of the original faces are cut
def FindEdgeSide(e,tc):
	if e.inside==0 and e.outside==0 and e.neither==0:
		#global messages
		#messages+="Had to find the side of an edge....\n"
		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

#After the call to blender's internal fill function, we have to figure out
#What it returns and match it up with its counterpart in out vertex set
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 0

#Starting with an edge and a point in that edge, this builds a loop
#of edges to fill later as a face
def MakeEdgeLoop(loop,edge,point,inside,outside,tc):
	v=point
	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],ew[0],inside,outside,tc)

#Add a face to an nmesh
#Select verts as applicable
def AddFace(f,nm,vl,objectflip):
	if objectflip<0:
		vl.reverse()
	vxl=[]
	for v in vl:
		#print v
		if v.used==0:
			v.newCounterpart=NMesh.Vert(v.tco[0],v.tco[1],v.tco[2])
			if v.inside:
				v.newCounterpart.sel=1
			nm.verts.append(v.newCounterpart)
			v.used=1
		vxl.append(v.newCounterpart)
	nf=NMesh.Face(vxl)
	nf.smooth=f.counterPart.smooth
	nm.faces.append(nf)

def ScanFillLoop(vl,f,nm,flip,vs,side):
			global messages
			try:
				fvl=nm.fillVertLoops(vl)
				fn=CrossVecs(Vector(fvl[0][1])-Vector(fvl[0][0]),Vector(fvl[0][2])-Vector(fvl[0][1]))
				fn.normalize()
				dv=DotVecs(fn,f.normal)
				if dv<0:
					messages+="FLIP!!!\n"
					localflip=-1
				else:
					localflip=1
				for vl in fvl:
					fvx=[]
					#frx=[]
					for	vp in vl:
						v=FindVertex(vp,vs)
						#frx.append(v)
						if v.used==0:
							v.newCounterpart=NMesh.Vert(v.tco[0],v.tco[1],v.tco[2])
							if v.inside:
								v.newCounterpart.sel=1
							nm.verts.append(v.newCounterpart)
							v.used=1
						fvx.append(v.newCounterpart)
					if flip*localflip<0:
						#print "flipping!!!",localflip
						fvx.reverse()
					nf=NMesh.Face(fvx)
					nf.smooth=f.counterPart.smooth
					nm.faces.append(nf)
			except:
					messages+="Couldn't fill face due to unpatched Blender version.\n"
					print "Couldn't fill face due to unpatched Blender version.\n"
					for vg in vl:
						lastv=FindVertex(vg[len(vg)-1],vs)
						for v in vg:
							v0=FindVertex(v,vs)
							if side==0:
								v0.outside=1
							elif side==1:
								v0.inside=1
							AddFace(f,nm,[lastv,v0],flip,side)
							lastv=v0


def BishieFill(el,vxl,f,nm,objectflip,side,gel,skipsplit=0,skipchecks=0):
	global traversalCookie
	global messages
	if len(vxl)<=3:
		AddFace(f,nm,vxl,objectflip)
		return
	count=len(vxl)
	if len(vxl)==4:

		#Test to see if quad is convex
		lcp=CrossVecs(vxl[0].tco-vxl[3].tco,vxl[1].tco-vxl[0].tco)
		for n in range(1,count):
			cp=CrossVecs(vxl[n].tco-vxl[n-1].tco,vxl[(n+1)%4].tco-vxl[n].tco)
			#print lcp,"---",cp,"->",DotVecs(cp,lcp)
			dv=DotVecs(cp,lcp)
			if dv<-0.00001:
				break
			lcp=cp
		#if it is convex, then we should add it
		if dv>-0.00001:
			AddFace(f,nm,vxl,objectflip)
			return
		else:
			print "4 Verts",dv
			for n in range(count):
				print vxl[n].tco

	segments=[[],[]]
	tossed=[]
	#Esegments=[[],[]]
	cseg=0
	print "E: ",len(el)," V: ",len(vxl)
	lastV=vxl[count-1]
	lastE=el[count-1]
	for i in range(0,count):
		v=vxl[i]
		e=el[i]
		#print i,": ",lastV.tco,"->",v.tco
		#print i,": ", e.v[0].tco,"->",e.v[1].tco
		#AddEdge(nm,[e.v[0],e.v[1]])
		#AddFace(nm,[lastV,v],0)
		if ((e.inside != lastE.inside) or (e.outside != lastE.outside)) and skipsplit==0:
			cseg=(cseg+1)%2
			tossed.append(i)
		else:
			#print "Plain",i,v.tco
			segments[cseg].append(i)
		lastV=v
		lastE=e

	print "Segments: ",segments,"\nTossed: ",tossed
	testnormals=1
	if skipsplit==0:
		if (len(segments[0])==0 or len(segments[1])==0) and len(tossed)>0:
			if len(segments[0])==0:
				segments[0]=tossed
			else:
				segments[1]=tossed
	if len(segments[0])==0 or len(segments[1])==0:
		segments[0]=range(count)
		segments[1]=range(count)
		#testnormals=1
	
	Cut=[0,0]
	Distance=-1
	print "Test Edges: ",len(gel)
	
	for pi0 in segments[0]:
		#for this 2nd for loop, in C version, be sure to avoid hitting
		#all options, just necissary ones when segments[0]==segment[1]
		for pi1 in segments[1]:
			nv=(vxl[pi0].tco-vxl[pi1].tco)
			if (pi0!=pi1 and (Distance<0 or (nv.length<Distance))):
				ok=1
				#Test that the ray is inside the shape
				#Should to an optimization test and see if it is faster
				#with this always on
				if testnormals:
					v0=vxl[(pi0+(count-1))%count].tco
					v1=vxl[pi0].tco
					v2=vxl[(pi0+1)%count].tco

					cp=CrossVecs(v1-v0,v2-v1)
					d=DotVecs(cp,f.normal)
					if d>0:
						if not (TestPointSideOfLine(vxl[pi1].tco,v0,v1,f.normal) and TestPointSideOfLine(vxl[pi1].tco,v1,v2,f.normal)):
							ok=0
							print "Falied Normals Test, Convex Case"
					else:
						if not (TestPointSideOfLine(vxl[pi1].tco,v0,v1,f.normal) or TestPointSideOfLine(vxl[pi1].tco,v1,v2,f.normal)):
							ok=0
							print "Failed Normals Test, Concave Case"

				p1=vxl[pi0].tco
				p2=vxl[pi1].tco
				d2121=DotVecs(p2-p1,p2-p1)

				#test for intersections
				for e in el:
				  if ok==0:
					break
				  p3=e.v[0].tco
				  p4=e.v[1].tco
				  #Test if the new edge is an edge that already exists in the edge list
				  if (vxl[pi0]==e.v[0] and vxl[pi1]==e.v[1]) or (vxl[pi0]==e.v[1] and vxl[pi1]==e.v[0]):
					if ok!=0:
						print "Edge already exists (%f,%f,%f)->(%f,%f,%f)"%(p1[0],p1[1],p1[2],p2[0],p2[1],p2[2])
					ok=0
					break
				  else:
					#Test to see of this edge overlaps an existing edge
					if vxl[pi0]==e.v[0] or vxl[pi1]==e.v[1] or vxl[pi0]==e.v[1] or vxl[pi1]==e.v[0]:
						if vxl[pi0]==e.v[0]:
							sp=e.v[0]
						if vxl[pi0]==e.v[1]:
							sp=e.v[1]
						if vxl[pi1]==e.v[0]:
							sp=e.v[0]
						if vxl[pi1]==e.v[1]:
							sp=e.v[1]

						if (vxl[pi0]==sp):
							ap=vxl[pi1]
						else:
							ap=vxl[pi0]

						if (e.v[0]==sp):
							bp=e.v[1]
						else:
							bp=e.v[0]
						vA=ap.tco-sp.tco
						vA.normalize()
						vB=bp.tco-sp.tco
						vB.normalize()
						d=DotVecs(vA,vB)
						if d>0.9999999:
							if ok!=0:
								print "DP failed at %f -- (%f,%f,%f)->(%f,%f,%f) vs (%f,%f,%f)->(%f,%f,%f)\n"%(d,p1[0],p1[1],p1[2],p2[0],p2[1],p2[2],p3[0],p3[1],p3[2],p4[0],p4[1],p4[2])
							ok=0
							break

				  #Test if the edges intersect (i.e. in concave shaps)
				  if vxl[pi0]!=e.v[0] and vxl[pi1]!=e.v[1] and vxl[pi0]!=e.v[1] and vxl[pi1]!=e.v[0]:

					#based on http://astronomy.swin.edu.au/~pbourke/geometry/lineline3d/
					d4321=DotVecs(p4-p3,p2-p1)
					d4343=DotVecs(p4-p3,p4-p3)
					d1343=DotVecs(p1-p3,p4-p3)
					d1321=DotVecs(p1-p3,p2-p1)
					mnad = (d2121*d4343-d4321*d4321)
					if mnad==0:
						print "\nParallel! ",p1,p2,p3,p4
						messages+="Parllel!!!\n"
						mna=1.1
					else:
						mna = (d1343*d4321-d1321*d4343)/mnad
						if (mna>-0.00001 and mna <1.000001):
							mnb = (d1343+mna*d4321)/d4343
							if (mnb > -0.00001 and mnb <1.000001):
								if ok:
									print "Intersection",p1,p2,p3,p4,mna,mnb
								ok=0
								break
				if ok:
					Distance=nv.length
					Cut=[pi0,pi1]
	if Distance < 0:
		print "Couldn't find good cut point",(len(segments[0]),len(segments[1]),)
		#if count==4:
			#AddFace(f,nm,vxl,objectflip,side)
			#return
		vl=[]
		for v in vxl:
			vl.append([v.tco[0],v.tco[1],v.tco[2]])
		#ScanFillLoop([vl],f,nm,objectflip,vxl,side)
		BishieFill(el,vxl,f,nm,objectflip,side,gel,1)
	else:
		print "Cut: ",Cut,Distance
		if Cut[1]<Cut[0]:
			a=Cut[0]
			Cut[0]=Cut[1]
			Cut[1]=a
		n=Cut[0]
		nvl=[]
		nel=[]

		nvl.append(vxl[Cut[1]])
		ne=CCEdge(vxl[Cut[1]],vxl[Cut[0]],el[0].parentObject)
		ne.insdide=el[0].inside
		ne.outside=el[0].outside
		nel.append(ne)
		f.edges.append(ne)

		while (n!=Cut[1]):
			nvl.append(vxl[n])
			nel.append(el[n])
			n+=1

		BishieFill(nel,nvl,f,nm,objectflip,side,gel)

		nvl=[]
		nel=[]
		nvl.append(vxl[Cut[0]])
		ne=CCEdge(vxl[Cut[0]],vxl[Cut[1]],el[0].parentObject)
		ne.insdide=el[0].inside
		ne.outside=el[0].outside
		nel.append(ne)

		f.edges.append(ne)

		while (n!=Cut[0]):
			nvl.append(vxl[n])
			nel.append(el[n])
			n+=1
			n%=count

		BishieFill(nel,nvl,f,nm,objectflip,side,gel)
	

def MakeFace(nm,f,vs,inside,outside,simple,objectflip):
	global traversalCookie
	mode=0
	
	if len(vs)<3:
		1
		#return traversalCookie
	elif len(vs)>3 or 1:

		el=[]
		#cutfaces=0

		if (simple==0):
			#add edges of original face
			for	e in f.edges:
				e.realize(el,1,f)
			for	e in f.edges:
				e.realize(el,2,f)
			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

				AddFace(f,nm,vs,objectflip)
			return traversalCookie	
		else:

			#add edges cut into face
			#messy nested for loops...maybe these edges can be added when they are cut
			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 "Edge Sides: ",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,eA.v[1],1,0,tc)
						insideLoops.append(newLoop)
			#print insideLoops

			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,eA.v[1],0,1,tc)
						outsideLoops.append(newLoop)
			#print outsideLoops

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

			#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


			if len(sharedLoops)==0:
				#No shared loops, so we can prbably doo nice filling.
				if outside:
					for le in outsideLoops:
						#BishieFill(le,nm,objectflip)
						BishieFill(le,EdgeLoopVxLoop(le),f,nm,objectflip,0,le)
				if inside:
					for le in insideLoops:
						#BishiFill(le,nm,objectflip)
						BishieFill(le,EdgeLoopVxLoop(le),f,nm,objectflip,1,le)
				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
				ScanFillLoop(outloops,f,nm,objectflip,vs,0)

			#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
				ScanFillLoop(inloops,f,nm,objectflip,vs,1)
			#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,flip):
		global traversalCookie
		for f in object.faces:
			if f.altered==1:
				vs=f.GetVertexSet()
				#This simplifies things bit, as we are guaranteed
				#the edgegraph will only contain data for this face
				for v in vs:
					v.edgeWith=[]

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

		#if inside/outside matters, to another pass
		if inside!=outside or 1:
			print "Pass two! (adding unaffected faces)"

			traversalCookie=traversalCookie+1

#			for f in object.faces:
#					for v in f.verts:
#						#v.edgeWith=[]
#						if f.altered==0:
#							s=FindVertexSide(v,traversalCookie)
#							#if s==-1:
#							#	global messages
#							#	messages+=("Vertex side unknown for <%.3f,%.3f,%.3f>\n"%(v.tco[0],v.tco[1],v.tco[2]))

			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!"
					MakeFace(self.nm,f,vs,inside,outside,1,flip)
			
			


def TestBounds(b1,b2):
	for i in range(3):
		if (b1[0][i]>b2[1][i])|(b2[1][i]<b1[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

						#add vertex to edge
						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


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,1)
	elif x==2:
		nmObject.addObject(ccCookie,1,0,1)
	elif x==3:
		nmObject.addObject(ccCookie,0,1,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,1)
	nmObject.addObject(ccCutter,1,0,-1)
	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,1)
	nmObject.addObject(ccCutter,1,0,1)
	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,1)
	nmObject.addObject(ccCutter,0,1,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()
#oA=Object.Get("Cookie")
#oB=Object.Get("Cutter")
#print oA
#print oB
#Intersection(Object.Get("Cookie"),Object.Get("Cutter"))

print "Done."

if len(messages)>0:
	txt=Blender.Text.New("Boolean Messages")
	txt.clear()
	txt.write(messages)