#!BPY

"""
Name: 'MegaBool r6'
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:                                                #
#   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                 #
#  18-Sep-2004  Re-did filling. 2nd object can now by a test of   #
#                loops. Other minor refinements.                  #
#                                                                 #
###################################################################



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,append=1,infinite=0):
		global traversalCookie
		self.parentObject=ccObject
		self.normal=0
		self.infinite=infinite
		if append:
			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 or self.infinite:
				return
		else:
			if sweep==2:
				return

		if self.infinite:
			
			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 i in range(2,len(v)):
				vtx=v[i]
				vtx.edgePos=DotVecs(vtx.tco,vec)
				#vtx.edgePos=(vtx.tco-v[0].tco).length
				ep.append(vtx.edgePos)
				nv.append(vtx)
			ep.sort()
			for i in range(2,len(v)):
				vtx=v[i]
				nv[ep.index(vtx.edgePos)]=vtx
			#print "sort edges",nv[0].outside,nv[0].inside
			nv[0].outside=outside=0
			nv[0].inside=1

			for n in range(1,len(nv)):
				ne=CCEdge(nv[n],nv[n-1],self.parentObject)
				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

		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):
		if self.infinite:
			self.v.append(v)
			return
		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,virtual=0):
		self.edges=[]
		self.verts=[]
		self.extraVerts=[]
		self.altered=0
		self.traversalCookie=0

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

		self.parentObject=ccObject

		if virtual:
			self.normal=0
		else:
			vec=Mathutils.Vector(list(nmFace.no))
			self.normal=Mathutils.VecMultMat(vec,ccObject.matrix.rotationPart())
			self.normal.normalize()


			#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"
		self.FacelessEdges=[]
		#build up faces & edges
		for f in m.faces:
			if len(f.v)>2:
				self.faces.append(CCFace(f,self))
			elif len(f.v)==2:
				self.FacelessEdges.append(CCEdge(self.verts[f.v[0].index],self.verts[f.v[1].index],self,0,0))


def TestIntersection(p1,p2,p3,p4,negativeok=0):
	#First test for shared points
	if p1==p3 or p1==p4 or p2==p3 or p2==p4:
		if negativeok:
			return -2
		return 0

	#Maybe bounds should be tested too, to avoid unneeded math
	#For now though, this is good enough
	#based on http://astronomy.swin.edu.au/~pbourke/geometry/lineline3d/
	d2121=DotVecs(p2-p1,p2-p1) #note: square of the edge's length (maybe should be precomputed for all edges?)
	d4321=DotVecs(p4-p3,p2-p1)
	d4343=DotVecs(p4-p3,p4-p3) #note: square of edge's length again
	d1343=DotVecs(p1-p3,p4-p3)
	d1321=DotVecs(p1-p3,p2-p1)
	mnad = (d2121*d4343-d4321*d4321)
	if mnad>-0.0001 and mnad<0.0001:
		#print "\nParallel! ",p1,p2,p3,p4
		#messages+="Parllel!!!\n"
		if negativeok:
			return -2
		else:
			return 0
	else:
		mna = (d1343*d4321-d1321*d4343)/mnad
		if (mna>-0.00001 and mna <1.000001) or negativeok:
			mnb = (d1343+mna*d4321)/d4343
			if (mnb > -0.00001 and mnb <1.000001):
				#if ok:
				#print "Intersection",p1,p2,p3,p4,mna,mnb,mnad
				if mna==0:
					return 0.00001
				return mna
	if negativeok:
		#print mna,mnb
		return -2
	return 0

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
#Basically we make sure the point is on the "inside" side
#of all the edges of the shape.
def TestPointInConvexLoop(p,l,normal):
	lastv=l[len(l)-1]
	for v in l:
		if not TestPointSideOfLine(p,lastv.tco,v.tco,normal):
			return 0
		lastv=v
	return 1
	

def TestPointInFace(p,f):
	vcount=len(f.verts)
	if vcount:
		return TestPointInConvexLoop(p,f.verts,f.normal)
	else: #This is an infinitely large face
		v0=f.edges[0].v[0]
		v1=f.edges[1].v[0]
		d0=DotVecs(v1.tco-v0.tco,p-v0.tco)
		d1=DotVecs(v0.tco-v1.tco,p-v1.tco)
		if d0>0 and d1>0:
			#print "PIF",d0,d1,v0.tco,v1.tco,p
			return 1
		else:
			#print "PNIF"
			return 0

#Take advantage of dot product to test if a point is in an edge
#This is more complicated than it needs to be. Just bounds testing
#would work. This is just easier in python
def TestPointInEdge(v,vl):
	#Maybe the v[1]-v[0] vector should be stored for each edge
	#So we don't have to keep recomputing it.
	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 ed.infinite==0:
		if not TestPointInEdge(v,ed.v):
			return 0
	if not TestPointInFace(v,f):
		return 0
	return 1


def TestEdgeIntersectLoop(p0,p1,loop):
	lastv=loop[len(loop)-1]
	for v in loop:
		if TestIntersection(p0.tco,p1.tco,lastv.tco,v.tco)!=0:
			#print "Intersect: ",p0.tco,p1.tco,lastv.tco,v.tco
			return 1
	return 0

#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:
					v.outside=1
					return sv
				elif sv==0:
					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):
  try:
	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
  except:
	print "Failed to find vertex (WTF) ",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)
	if f.counterPart:
		nf.smooth=f.counterPart.smooth
	nm.faces.append(nf)

def JoinConcentric(vertList,enclosed,CCWlist,allList,normal,f,nm):
						#Preffer parallel edges (smaller dot product absolute value)
						bestOuter=0
						bestInner=0
						parallelness=100
						Ocount=len(vertList)
						for On in range(Ocount):
							I0=vertList[(On+Ocount-1)%Ocount].tco-vertList[On].tco;
							I1=vertList[(On+1)%Ocount].tco-vertList[On].tco;
							for vl in enclosed:
								Icount=len(vl)
								for In in range(Icount):
									vect=vertList[On].tco-vl[In].tco;
									d=vect.length;
									par=parallelness
									O0=vl[(In+Icount-1)%Icount].tco-vl[In].tco;
									O1=vl[(In+Icount-1)%Icount].tco-vl[In].tco;
									pt=(abs(DotVecs(I0,O0))+0.01)*d
									if (pt<par):
										par=pt
									pt=(abs(DotVecs(I0,O1))+0.01)*d
									if (pt<par):
										par=pt
									pt=(abs(DotVecs(I1,O0))+0.01)*d
									if (pt<par):
										par=pt
									pt=(abs(DotVecs(I1,O1))+0.01)*d
									if (pt<par):
										par=pt
									#is this worth considering?
									if (par<parallelness):
										#does this not intersect w/ any existing edges
										if TestEdgeIntersectLoop(vertList[On],vl[In],vertList)==0:
											ok=1
											for vl2 in allList: #CCWlist:
												if TestEdgeIntersectLoop(vertList[On],vl[In],vl2):
													#print On," to ",On," failed. ",vl,vl2
													ok=0
													break
											if ok:
												bestOuter=On
												bestInner=(vl,In)
												parallelness=par
						if parallelness<100:
							newVL=[]
							print "Connect ",bestOuter," to ",bestInner[1]
							for n in range(len(vertList)):
								v=vertList[n]
								if n==bestOuter:
									newVL.append(v)
									print v.tco,vertList.index(v)
									vl=bestInner[0]
									for i in range(bestInner[1],len(vl)):
										newVL.append(vl[i])
										print vl[i].tco,":",i
									for i in range(bestInner[1]+1):
										newVL.append(vl[i])
										print vl[i].tco,":",i
									newVL.append(v)
									print v.tco,vertList.index(v)
								else:
									print v.tco,vertList.index(v)
									newVL.append(v)
							#Maybe I should have two CCWlists?
							#I still need to test for edge intersections
							CCWlist.remove(bestInner[0])
							return QuadFillLoop(newVL,CCWlist,allList,normal,f,nm)
						else:
							print "couldn't find path to connect concentric loops"
							return 0

def nFillLoop(sides,vertList,CCWlist,allList,normal,f,nm):
		#print "nfill"
		#for v in vertList:
		#	print "\t",v.tco
		count=len(vertList);
		for i in range(count):
			convex=1
			#test convexity
			loop=[]
			loopReal=[]
			for j in range(sides):
				if DotVecs(CrossVecs(vertList[(i+(j+1)%sides)%count].tco-vertList[(i+j)%count].tco,vertList[(i+(j+sides-1)%sides)%count].tco-vertList[(i+j)%count].tco),normal)<0.000001:
					convex=0
					break
				loop.append((i+j)%count)
				loopReal.append(vertList[(i+j)%count])
			if convex:
				#test no verts in face
				ok=1
				#loop.reverse()
				for p in vertList:
					nocheck=0
					for lp in loopReal:
						if p==lp:
							nocheck=1

					if nocheck==0 and TestPointInConvexLoop(p.tco,loopReal,normal):
						ok=0
						break
				if ok:
					ok=1
					#test verts in inner loop
					enc=[]
					for vl in CCWlist:
						for lp in vl:
							if TestPointInConvexLoop(lp.tco,loopReal,normal):
								try:
									enc.index(vl)
								except:
									enc.append(vl)
								ok=0
					if ok:
						newVL=[]
						n=loop[sides-1]
						while n!=loop[1]:
							newVL.append(vertList[n])
							n+=1
							n%=count
						if QuadFillLoop(newVL,CCWlist,allList,normal,f,nm):
							print "Face! ",[vertList[i],vertList[(i+1)%count],vertList[(i+2)%count],vertList[(i+3)%count]]
							AddFace(f,nm,loopReal,1)
							return 1
						else:
							print "failed..."
							for vx in vertList:
								print vx.tco
							print "--------------------------"
					else:
						print "Concentric loops!"
						#There is apparently a heirarchy of loops here
						#Connect this loop to a revelvant inner loop
						if JoinConcentric(vertList,enc,CCWlist,allList,normal,f,nm):
							return 1
						else:
							print "Join conventric failed..."
		return 0

def QuadFillLoop(vertList,CCWlist,allList,normal,f,nm):
	#try to find a quad that works
	print "Filling ",len(vertList)," point loop"
	if len(vertList)>3:
		if nFillLoop(4,vertList,CCWlist,allList,normal,f,nm):
			return 1
	if len(vertList)>2:
		if nFillLoop(3,vertList,CCWlist,allList,normal,f,nm):
			return 1
		else:
			return
	else:
		return 1

def NewFillLoop(vl,f,nm,flip,vs,side):
	print "Fill face..." 
	#Note this can probably be made more efficient if made into a 2D problem using aligning the Z axis with the face's normal
	global messages
	#First establish loop directions
	normal=f.normal*flip

	#Note: this is based on very similar code in "Cut 2D Edges" -- these should probably call a function to do this
	#Here we find edge normals
	EdgeNormals=[]
	EdgeIntersects=[]
	print len(vl)
	for l in vl:
		count=len(l)
		NormalList=[]
		IntersectList=[]
		for i in range(count):
			#print vl.index(l),",",i,": ",l[i].tco
			v0=l[i].tco
			v1=l[(i+1)%(count)].tco
			midpt=(v0+v1)/2
			ray=CrossVecs(v1-v0,normal)
			intersections=[]
			isectcount=0
			for il in vl:
				icount=len(il)
				for j in range(icount):
					v2=il[j].tco
					v3=il[(j+1)%(icount)].tco
					if (v0!=v2):
						a=TestIntersection(midpt,midpt+ray,v2,v3,1)
						#print vl.index(l),i,"vs",vl.index(il),j,"=",a
						#print midpt,ray,v2,v3
						if (a>0):
							isectcount+=1
							intersections.append((vl.index(il),j))
			#Here we want the normals point inside, not outside like in the Cut2DEdges
			if (isectcount%2)==0:
				ray*=(-1)
			NormalList.append(ray)
			IntersectList.append(intersections)
		EdgeNormals.append(NormalList)
		EdgeIntersects.append(IntersectList)


	#Now correct the directions if need be
	for i in range(len(vl)):
		l=vl[i]
		NormalList=EdgeNormals[i]
		if (DotVecs(CrossVecs(l[1].tco-l[0].tco,NormalList[0]),normal)<0):
			print "Had to reverse list ",i
			vl[i].reverse();
			EdgeNormals[i].reverse();
			t=EdgeNormals[i][0];
			EdgeNormals[i].remove(t);
			EdgeNormals[i].append(t);
			EdgeIntersects[i].reverse();
			t=EdgeIntersects[i][0];
			EdgeIntersects[i].remove(t);
			EdgeIntersects[i].append(t);
		else:
			print "List ",i,"already in the right direction"
	
	#Now make two lists - clockwise and counterclockwise
	CWlist=[]
	CCWlist=[]

	for i in range(len(vl)):
		l=vl[i]
		Normal0=EdgeNormals[i][0]*(-1)
		intersections=EdgeIntersects[i][0]
		counter=0
		for ie in intersections:
			if (ie[0]!=i):
				counter+=1
		if (counter%2)==0:
			CWlist.append(l)
			print i,"is clockwise"
		else:
			CCWlist.append(l)

	print "Clockwise: ",len(CWlist)," Counterclockwise: ",len(CCWlist)

	#Time to fill!
	for l in CWlist:
		print "Start Seg"
		QuadFillLoop(l,CCWlist,vl,normal,f,nm)

#This re-orders the points in certain cases for slighly better filling
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]
		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
	apex=0
	if len(segments[0])==1:
		apex=segments[0][0]
	if len(segments[1])==3:
		apex=segments[1][1]
	if len(segments[0])==1:
		apex=segments[0][0]
	if len(segments[1])==3:
		apex=segments[1][1]
	print "APEX:",apex
	newVL=[vxl[apex]]
	vp=(apex+1)%count
	while vp!=apex:
		newVL.append(vxl[vp])
		vp+=1
		vp%=count
	#print f.normal,objectflip
	QuadFillLoop(newVL,[],[],f.normal*objectflip,f,nm)

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

		el=[]
		#cutfaces=0

		#add edges of original face
		infinite=0
		print "Initial Edges: ",len(f.edges)
		for	e in f.edges:
			if e.infinite:
				infinite=1
			e.realize(el,1,f)
		for	e in f.edges:
			e.realize(el,2,f)
		f.edges=el
		print "Side Edges: ",len(f.edges)
		print "Vertex Set: ",len(vs)

		if 1:

			#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 i in range(len(vs)):
				vA=vs[i]
				for cfA in vA.cutBy:
					#we only care about stuff cut by the other object
					#Perhaps things would be more eifficient if each object has a separate
					#CutBy list.
					if cfA.parentObject!=f.parentObject and cfA.traversalCookie<tc:
						for j in range(i+1,len(vs)):
							vB=vs[j]
							for cfB in vB.cutBy:
								if cfA==cfB:
									cfA.traversalCookie=tc
									ne=CCEdge(vA,vB,f.parentObject)
									#print ne,vA.tco,vB.tco
									ne.inside=1
									ne.outside=1
									f.edges.append(ne)
									print "Cut Edge",vA.tco,vB.tco

			#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:
				#print "E:", eA.v[0].tco,eA.v[1].tco
				if eA.inside==1 and eA.outside==0:
					#print "Inside:", eA.v[0].tco,eA.v[1].tco
					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:
					#print "Outside:", eA.v[0].tco,e.Av[1].tco
					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 or e.inside==1:
						for v in e.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
						nm.faces.append(NMesh.Face([e.v[0].newCounterpart,e.v[1].newCounterpart]))
				return tc

			if len(sharedLoops)==0 and infinite==0:
				#No shared loops, so we can prbably do 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=[]
				outloopsnf=[]
				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)
					outloopsnf.append(vxl)
				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)
					outloopsnf.append(vxl)

				#Do the filling
				#ScanFillLoop(outloops,f,nm,objectflip,vs,0)
				NewFillLoop(outloopsnf,f,nm,objectflip,vs,0)

			#traversalCookie=traversalCookie+1

			if (inside):
				inloops=[]
				inloopsnf=[]
				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)
						inloopsnf.append(vxl)
				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)
						inloopsnf.append(vxl)

				#Do the filling
				#ScanFillLoop(inloops,f,nm,objectflip,vs,1)
				NewFillLoop(inloopsnf,f,nm,objectflip,vs,1)


#Re-add one of the unmodified faces, first testing to see if it is visible or not
def MakeSimpleFace(nm,f,vs,inside,outside,objectflip,otherObject):
	global traversalCookie
	if len(vs):
		if inside!=outside:
			#for v in vs: #Actually for existing faces we just need to test one point
			#print len(vs),vs,"--"
			v=vs[0]
			traversalCookie+=1
			s=FindVertexSide(v,traversalCookie)
			if (s==-1):
				print "NEITHER!"
				ifaces=0
				ray=Vector([1,0,0])
				for f in otherObject.faces:
					#Based on code in CutEdges, should really be one function
					p_point=f.edges[0].v[0].tco
					to_point=p_point-v.tco
					if (DotVecs(to_point,ray)>0):
						p_normal=f.normal
						d=DotVecs(p_normal,ray)
						if d!=0:
							n=DotVecs(p_normal,p_point-v.tco)
							intersect=v.tco+(n/d)*ray
							if TestPointInFace(intersect,f):
								ifaces+=1
				v.inside=v.outside=0
				if (ifaces%2)==1:
					v.inside=1
				else:
					v.outside=1
			if (v.outside<outside or v.inside<inside):
				return

		AddFace(f,nm,vs,objectflip)

		

class CCNewMesh:
	def __init__(self):
		self.nm=NMesh.New()
	def addObject(self,object,inside,outside,flip,otherObject):
		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=[]
				print "Adding Altered Face"
				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:
				if f.altered==0:
					vs=f.verts
					print "Adding unaltered face"
					MakeSimpleFace(self.nm,f,vs,inside,outside,flip,otherObject)
			

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 Make2DLoop(v,loop):
	global traversalCookie
	v.traversalCookie=traversalCookie
	loop.append(v)
	for ew in v.edgeWith:
		if ew[0].traversalCookie<traversalCookie:
			Make2DLoop(ew[0],loop)

def CutEdges2D(cookie,cutter):
	global traversalCookie

	print "Doing 2D Cut"

	cutterloops=[]
	brokenverts=0
	#Quick non-manifold test
	for v in cutter.verts:
		if len(v.edgeWith)>2:
			brokenverts=1
			break
	if brokenverts:
		for v in cutter.verts:
			if len(v.edgeWith)>2:
				v.counterPart.sel=1
			else:
				v.counterPart.sel=0
		Draw.PupMenu("All verticies in cutter must be used by no more than two faces. Problematic verts have been selected in editmode")
		exit

	#build edgeloops
	traversalCookie+=1
	for v in cutter.verts:
		if v.traversalCookie<traversalCookie:
			newLoop=[]
			Make2DLoop(v,newLoop)
			if len(newLoop)<3:
				Draw.PupMenu("Make sure all loops are closed in cutter object")
				exit
			cutterloops.append(newLoop)

	print "Cutter has %d loops"%(len(cutterloops))

	#Find a normal to use
	normal=Vector([0,0,0])
	for l in cutterloops:
		count=len(l)
		for i in range(count):
			tn=CrossVecs(l[i].tco-l[(1+1)%(count)].tco,l[(1+2)%(count)].tco-l[(1+1)%(count)].tco)
			#print tn
			if (DotVecs(tn,normal)>=0):
				normal+=tn
	print "Cutter Normal: <%f,%f,%f>"%(normal[0],normal[1],normal[2])

	#determine edge normals
	EdgeNormals=[]
	for l in cutterloops:
		count=len(l)
		NormalList=[]
		for i in range(count):
			v0=l[i].tco
			v1=l[(i+1)%(count)].tco
			midpt=(v0+v1)/2
			ray=CrossVecs(v1-v0,normal)
			intersections=0
			for il in cutterloops:
				icount=len(il)
				for j in range(icount):
					v2=il[j].tco
					v3=il[(j+1)%(icount)].tco
					if (v0!=v2):
						###a=TestIntersection(midpt,midpt+ray,v2,v3,0)
						a=TestIntersection(midpt,midpt+ray,v2,v3,1)
						if (a>0):
							intersections+=1
			if (intersections%2)==1:
				ray*=(-1)
			NormalList.append(ray)
		EdgeNormals.append(NormalList)

	#Build infinite length edges
	cutter.edges=[]
	for l in cutterloops:
		for v in l:
			v.outside=1
			v.edgeWith=[]
			Compliment=CCVert(0,cutter)
			Compliment.tco=v.tco+normal
			Compliment.outside=0
			e=CCEdge(v,Compliment,cutter,1,1)
	
	#Build infite length faces
	cutter.faces=[]
	for i in range(len(cutterloops)):
		vloop=cutterloops[i]
		nloop=EdgeNormals[i]
		count=len(vloop)
		for j in range(count):
			nf=CCFace(0,cutter,1)
			nf.normal=nloop[j]
			v=vloop[j]
			e=v.edgeWith[0][1]
			e.faces.append(nf)
			nf.edges.append(e)
			v=vloop[(j+1)%count]
			e=v.edgeWith[0][1]
			e.faces.append(nf)
			nf.edges.append(e)
			cutter.faces.append(nf)
	
	CutEdges(cookie,cutter,1)
	CutEdges(cutter,cookie,1)


def CutEdges(cookie,cutter,nobounds=0):
	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 nobounds or 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:

						print "New Point: ", intersect

						#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)
	if len(ccCutter.faces)<len(ccCutter.FacelessEdges):
		CutEdges2D(ccCookie,ccCutter)
	else:
		CutEdges(ccCookie,ccCutter)
		CutEdges(ccCutter,ccCookie)
	nmObject=CCNewMesh()

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

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

def Difference(cookie,cutter):
	ccCookie=CCObject(cookie)
	ccCutter=CCObject(cutter)
	if len(ccCutter.faces)<len(ccCutter.FacelessEdges):
		CutEdges2D(ccCookie,ccCutter)
	else:
		CutEdges(ccCookie,ccCutter)
		CutEdges(ccCutter,ccCookie)
	nmObject=CCNewMesh()
	nmObject.addObject(ccCookie,0,1,1,ccCutter)
	nmObject.addObject(ccCutter,1,0,-1,ccCookie)
	nmObject.nm.mode=ccCookie.nmesh.mode;
	NMesh.PutRaw(nmObject.nm);
	return

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

def Union(cookie,cutter):
	ccCutter=CCObject(cutter)
	if len(ccCutter.faces)<len(ccCutter.FacelessEdges):
		Draw.PupMenu("no... Union doesn't work for this")
		return
	ccCookie=CCObject(cookie)
	CutEdges(ccCookie,ccCutter)
	CutEdges(ccCutter,ccCookie)
	nmObject=CCNewMesh()
	nmObject.addObject(ccCookie,0,1,1,ccCutter)
	nmObject.addObject(ccCutter,0,1,1,ccCookie)
	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"))
#Difference(Object.Get("Cookie"),Object.Get("Cutter"))

print "Done."

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


#Note to self:
# Re-orient the messhes when doing a 2D cut so
#two-axis bounding box test can be done