#!BPY

"""
Name: 'MegaBool r3'
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
messages=""

class CCVert:
	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.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 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:
			#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)):
				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)
				self.real.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
	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=list(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(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?
	cp=CrossVecs(normal,v1-v0)
	s=DotVecs(point-v0,cp)
	if s < 0:
		return 0
	else:
		return 1


## GAH!
## .index() is bad, need to use cookies later, or just be start and have full case for 3 and 4 vertex faces...
def TestPointInFace(v,f):
	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 TestPointInEdge(v,vl):
	ev=vl[1].tco-vl[0].tco
	vA=v-vl[0].tco
	d=vA.length
	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

def	EdgeLoopVxLoop(el):
	global traversalCookie
	traversalCookie=traversalCookie+1
	vxl=[]
	#vxl.append(el[0].v[0])
	#el[0].v[0].traversalCookie=traversalCookie
	for e in el:
		for v in e.v:
			if v.traversalCookie<traversalCookie:
				v.traversalCookie=traversalCookie
				vxl.append(v)
#	return SortVertexLoop(vxl,el)
	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

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 0

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,point,inside,outside,tc):
#  for v in edge.v:
	v=point
	#v.traversalCookie=tc
	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)
				MakeEdgeLoop(loop,ew[1],ew[0],inside,outside,tc)

def XXXMeshAppendFace(vl,nm,f,objflip,inside,outside):
	fvx=[]
	frx=[]
	flip=0
	for	v in vl:
		frx.append(v)
		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|=inside
		v.outside|=outside
	cp=CrossVecs(frx[1].tco-frx[0].tco,frx[2].tco-frx[1].tco)
	dp=DotVecs(cp,f.normal)
	if dp>0:
		flip=1
	else:
		flip=-1
	if flip*objectflip==-1:
		fvx.reverse()
	nf=NMesh.Face(fvx)
	nf.smooth=f.counterPart.smooth
	nm.faces.append(nf)

def AddFace(f,nm,vl,objectflip,side):
	if objectflip<0:
		vl.reverse()
	vxl=[]
	for v in vl:
		#print v
		if v.used==0:
			nm.verts.append(v.newCounterpart)
		v.used=1
		if v.inside:
			v.newCounterpart.sel=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)
						fvx.append(v.newCounterpart)
						if v.used==0:
							if v.inside:
								v.newCounterpart.sel=1
							nm.verts.append(v.newCounterpart)
						v.used=1
						if side==0:
							v.outside=1
						elif side==1:
							v.inside=1
					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:
		#lcp=CrossVecs(vxl[1].tco-vxl[0].tco,vxl[2].tco-vxl[1].tco)
		#if DotVecs(lcp,f.normal)<0:
		#	print "FLIPPED FACE!!!"
		#	for i in range(3):
		#		print i,": ",vxl[i].tco,"/",el[i].v[0].tco,el[i].v[1].tco,el[i].inside,el[i].outside
		#	#objectflip*=-1
		AddFace(f,nm,vxl,objectflip,side)
		return
	count=len(vxl)
	if len(vxl)==4:
		lastV=vxl[count-1]
		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 dv>-0.00001:
			AddFace(f,nm,vxl,objectflip,side)
			return
		else:
			print "4 Verts",dv
			for n in range(count):
				print vxl[n].tco

	segments=[[]]
	tossed=[]
	#Esegments=[[],[]]
	cseg=segments[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:
			#print "transition: ",i,v.tco
			if len(cseg)>0:
				cseg=[]
				segments.append(cseg)
			tossed.append(i)
		else:
			#print "Plain",i,v.tco
			cseg.append(i)
		lastV=v
		lastE=e

	testnormals=1
	if skipsplit==0:
		if len(segments)==1 and len(tossed)>0:
			segments.append(tossed)
			A=tossed[0]
			B=tossed[len(tossed)-1]
			if B<A:
				C=B
				B=A
				A=C
				messages+="Had to swap members of alternate group\n"
			print "Fixing...",segments[0],tossed,A,B,count
			if len(segments[0]):
				segments[0].remove((A+(count-1))%count)
			if len(segments[0]):
				segments[0].remove((B+1)%count)
			#testnormals=1
	if skipsplit==1 or 1:
		if len(segments)==1:
			segments.append(range(count))
			#testnormals=1
	
	Cut=[0,0]
	Distance=-1
	print "Test Edges: ",len(gel)
	
	for pi0 in segments[0]:
		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 gel:
				  if ok==0:
					break
				  p3=e.v[0].tco
				  p4=e.v[1].tco
				  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:
					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
					#vt0=p2-p1
					#vt1=p3-p1
					#vt0.normalize()
					#vt1.normalize()
					#d=DotVecs(vt0,vt1)
					#if vxl[pi0]!=e.v[0] and vxl[pi1]!=e.v[0] and (d<-0.99999 or d>0.99999) and TestPointInEdge(e.v[0].tco,[vxl[pi0],vxl[pi1]]):
					#	if ok!=0:
					#		print "other point exists on this edge"
					#	ok=0
					#	break

				  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:
						mna = (d1343*d4321-d1321*d4343)/mnad
					else:
						print "\nParallel! ",p1,p2,p3,p4
						messages+="Parllel!!!\n"
						mna=1.1
					mnb = (d1343+mna*d4321)/d4343
					#print (pi0,pi1),(mna,mnb)
					#if (mna>0.000001 and mna <0.99999 and mnb > 0.000001 and mnb <0.99999):
					if (mna>-0.00001 and mna <1.000001 and 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)
		gel.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)

		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
			#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:
				if objectflip<0:
					nf=NMesh.Face([vx[2].newCounterpart,vx[1].newCounterpart,vx[0].newCounterpart])
				else:
					nf=NMesh.Face([vx[0].newCounterpart,vx[1].newCounterpart,vx[2].newCounterpart])
			else:
				if objectflip<0:
					nf=NMesh.Face([vx[3].newCounterpart,vx[2].newCounterpart,vx[1].newCounterpart,vx[0].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 "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:
			#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,0,flip)

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

			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]))

			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,flip)
			
			


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,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 and 0:
	txt=Blender.Text.New("Boolean Messages")
	txt.clear()
	txt.write(messages)