#!BPY

"""
Name: 'MegaBool'
Blender: 234
Group: 'Object'
Tooltip: 'Perform boolean operations on meshes and get nice results'
"""
__bpydoc__ ="""\
                                                                 <br>
 Experimental New Mesh Boolean Operations                        <br>
                                                                 <br>
 (C) 2004 Theodore K Schundler (tschundler)(@)(scu)(edu)         <br>
 FOR TESTING ONLY, not for redistribution                        <br>
 Lastest version available for from:                             <br>
 http://astro.scu.edu/~ted/oss/blender/boolean                   <br>
                                                                 <br>
 USAGE:                                                          <br>
   -By Menu-                                                     <br>
     * Put this file in ~/.blender/scripts/                      <br>
     * Select two objects, then choose "MegaBool" from the       <br>
        scripts menu.                                            <br>
   -By Running the script-                                       <br>
     * Load this file into blender's internal text editor        <br>
     * Select two objects, then press Alt+P in the test editor   <br>
                                                                 <br>
 OPERATIONS:                                                     <br>
   On execution of the script, there are four operations         <br>
     * Intersect - Intersection of the two meshes (logical AND)  <br>
     * Union - Union of the two meshes (logical OR)              <br>
     * Difference - First selected mesh - Last selected mesh     <br>
     * Cookie Cutter - First mesh's faces are subdivided where   <br>
        they intersect with the second mesh                      <br>
   After the script executes, all "inside" vertices are selected <br>
                                                                 <br>
 IMPORTANT NOTES:                                                <br>
   Like any boolean algorithm, normals on the source meshes must <br>
 be all facing outside. To fix normals, select a mesh, enter     <br>
 edit mode, select all verticies, and press Ctrl+N. Also, all    <br>
 intersections must create closed loops. (Basically the meshes   <br>
 should be closed.) If you find a set of meshes that do not work <br>
 send me the .blend file and an explaination of the problem.     <br>
                                                                 <br>
 TO DO:                                                          <br>
  * Set materials, UVs, etc., on new mesh                        <br>
  * Intersection of curves? (use splines for smooth shapes)      <br>

-----------------------------------------------------------------
                                                                 
  Date:        Updates:                                          <br>
  16-Aug-2004  Initial Revision - working(?) & ready to go       <br>
  17-Aug-2004  Fixed some bugs based on incorrect assumptions.   <br>
                that means even more computation. Also made more <br>
                use of the traversalCookies to speed up a some   <br>
                sections                                         <br>
  24-Aug-2004  Smart filling & other stuff...                    <br>
  26-Aug-2004  Much cleanup, nothing new / fancy                 <br>
  18-Sep-2004  Re-did filling. 2nd object can now be a set of    <br>
                loops. Other minor refinements.                  <br>
  24-Sep-2004  Fixed a wrong assumption about vertex ordering    <br>
  26-Sep-2004  Got rid of special filling stuff that made face   <br>
                selection work better because with the new edit  <br>
                modes, it isn't necissary.                       <br>
  27-Oct-2004  Made some headway with the coplanar problem, but  <br>
                there is still a colinear problem, and sometimes <br>
                an issue if a point lies in another objects plane<br>
  01-Nov-2004  Fixed edge crossing tests in joinconcentric       <br>
  10-Dec-2004  Rewrite of almost everything                      <br>
                                                                 
"""

__author__ = "Theodore K. Schundler"
__version__ = "r8 10-Dec-04"
__email__ = ('Author EMail, tschundler:scu*edu')
__url__ = ('elysiun','Script Web Page, http://astro.scu.edu/~ted/oss/blender/boolean/')


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=""


###################################################################
# Utility Functions                                               #
###################################################################
def MidPoint(v1,v2):
	return (v1*0.49+v2*0.51); #a little bit of jitter ...

def ExpandBounds(Bounds,v):
	for i in range(3):
		if (Bounds[0][i]>v[i]):
			 Bounds[0][i]=v[i]
		if (Bounds[1][i]<v[i]):
			 Bounds[1][i]=v[i]
	return Bounds

def BuildBounds(v1,v2):
	Bounds=[[v1[0],v1[1],v1[2]],[v1[0],v1[1],v1[2]]]
	return ExpandBounds(Bounds,v2)

def TestBounds(b1,b2):
	for i in range(3):
		if (b1[0][i]>b2[1][i]) or (b2[0][i]>b1[1][i]):
			return 0
	return 1

def FindIntersectLineLine3D(p1,p2,p3,p4,stop_at_a=0,limits=0,advanced=0,tolerance=0.0002):
	if limits:
		#First test for shared points
		if (p1==p3 or p1==p4 or p2==p3 or p2==p4):
			return []

		#Bounds test...maybe it should be tested to see if this actually helps?
		if (TestBounds(BuildBounds(p1,p2),BuildBounds(p3,p4))==0):
			return []

	#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:#mnad>-0.00000000000001 and mnad<0.00000000000001: #parallel
		#print "Parallel!!!",mnad
		return []
	else:
		mna = (d1343*d4321-d1321*d4343)/mnad
		if (limits==0 or (mna>-0.000001 and mna <1.000001)):
			mnb = (d1343+mna*d4321)/d4343
			if ((limits==0 and stop_at_a==0) or (mnb > -0.00001 and mnb <1.000001)):
				if mnad<0.001 or advanced:
					dv=p1+(p2-p1)*mna-(p3+(p4-p3)*mnb)
					dis=DotVecs(dv,dv)
					#Needs to be 0.00001 for animtest to work...
					#Maybe is I break Quads into tris, this won't be a problem?
					if dis>tolerance:
						#print "Parallel - late detection",dv,dis,(p3+(p4-p3)*mnb)
						return []
					return [mna,mnb,dis]
				return [mna,mnb]
	return []

def FindDistPointToLine3D(p1,p2,p3):
	Va=p2-p1
	Vb=p3-p1
	d=DotVecs(Va,Va)
	if d!=0:
		p4= ((DotVecs(Vb,Va)/d)*Va)+p1
	else:
		p4=p1
	Vc=p4-p3
	return DotVecs(Vc,Vc)

def TestVertInEdge3D(v,e):
	d=e.dot
	if d!=0:
		vA=v.tco-e.v[0].tco
		dA=DotVecs(vA,e.vect)
		de=dA/d
		if (de>1.0001 or de<-0.0001):
			return 0
		dp=de*d+e.v[0].tco
	else:
		dp=e.v[0].tco
	vB=dp-v.tco
	dB=DotVecs(vB,vB)
	if dB<0.0001:
		return 1
	return 0

def TestIntersectLineLine3D(p1,p2,p3,p4):
	return len(FindIntersectLineLine3D(p1,p2,p3,p4,0,1))==2

def TestEdgeIntersectLoop3D(p0,p1,loop):
	lastv=loop[len(loop)-1]
	for v in loop:
		if TestIntersectLineLine3D(p0.tco,p1.tco,lastv.tco,v.tco):
			return 1
		lastv=v
	return 0

def TestPointSideOfLine3D(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.
#it may be worthwhile to optimize this since uit gets a called a lot when filling
def TestPointInConvexLoop(p,l,normal):
	lastv=l[len(l)-1]
	for v in l:
		if not TestPointSideOfLine3D(p,lastv.tco,v.tco,normal):
			return 0
		lastv=v
	return 1
	
def FindIntersectRayPlane(r_point,r_direction,p_point,p_normal,positive_only=0):
	d=DotVecs(p_normal,r_direction)
	if abs(d)<0.001:
		return 0
	n=DotVecs(p_normal,p_point-r_point)
	nd=n/d
	if nd<0 and positive_only:
		return 0
	return nd

def TestPointInPlane(point,normal,facevert):
	va=point-facevert
	#normal's length should always be 1....why isn't it?
	d=DotVecs(normal,va)/normal.length
	#must be <0.001 ....apparently much less than 0.001 is a problem too
	#>=0.001 needed for animtest frame 82
	if d<0.001 and d > -0.001:
		print "Point in Plane:",d,point,normal,facevert
		return 1
	return 0
					
def TestPointInFace(p,f):
	vcount=len(f.v)
	if vcount:
		return TestPointInConvexLoop(p,f.v,f.normal)
	else: #This is an infinitely large face, so we test between the two edges
		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

def TestIntersectRayFace(r_point,r_direction,face,positive_only=0):
	d=FindIntersectRayPlane(r_point,r_direction,face.e[0].v[0].tco,face.normal,positive_only)
	if d==0:
		return 0
	p=r_point+d*r_direction
	return TestPointInFace(p,face)

def FindIntersectEdgeFace(edge,face):
	r_point=edge.v[0].tco
	r_direction=edge.v[1].tco-r_point
	d=FindIntersectRayPlane(r_point,r_direction,face.e[0].v[0].tco,face.normal)
	if d==0:
		return 0
	#May need to fudge these valus for fuzzy intersections
	if (not edge.infinite) and (d<0 or d>1):
		return 0
	p=r_point+d*r_direction
	if TestPointInFace(p,face):
		return p
	return 0

def MakeLoopX(start,vA,state,face,lastEdge=0):
	global traversalCookie
	#print "LS",vA,vA.e
	for e in vA.e:
		if e.travCookie<traversalCookie and e.testState(state,face):
			for vB in e.v:
				if vB!=vA and e!=lastEdge:
					e.travCookie=traversalCookie
					return [vA]+MakeLoop(start,vB,state,face,e)
	return [vA]
				
def MakeLoop(start,vA,state,face,lastVert=0):
	global traversalCookie
	#print "LS",vA,vA.e
	for e in vA.e:
		if e.travCookie<traversalCookie and e.testState(state,face):
			for vB in e.v:
				if vB!=vA and vB!=lastVert: #it is unfortunately possible to have edges that connect to themselves or back trace
					if vB==start:
						e.travCookie=traversalCookie
						return [vA]
					if vB.travCookie<traversalCookie:
						eOTC=e.travCookie
						e.travCookie=traversalCookie
						#e.parent.travCookie=traversalCookie
						vOTC=vB.travCookie
						vB.travCookie=traversalCookie
						r=MakeLoop(start,vB,state,face,vA)
						if r:
							return [vA]+r
						vB.travCookie=vOTC
						e.travCookie=eOTC
	return []
				
def MakeLoopOld(start,vA,state,face):
	global traversalCookie
	#print "LS",vA,vA.e
	for e in vA.e:
		if e.travCookie<traversalCookie and e.testState(state,face):
			for vB in e.v:
				if vB.travCookie<traversalCookie:
					e.travCookie=traversalCookie
					vB.travCookie=traversalCookie
					return [vA]+MakeLoop(start,vB,state,face)
	return [vA]
				
#This should maybe split it into lists instead of needing to be called multiple times...
def FilterEdges(EdgeList,state,face):
	global traversalCookie
	traversalCookie=traversalCookie+1
	traversalBase=traversalCookie
	loops=[]
	for e in EdgeList:
		traversalCookie=traversalCookie+1
		if (e.travCookie<traversalBase and e.testState(state,face)):
			#e.travCookie=traversalCookie
			if 1 or e.v[0].travCookie<traversalBase: #this test isn't really needed (I think)
				e.v[0].travCookie=traversalCookie
				lp=MakeLoop(e.v[0],e.v[0],state,face)
				if len(lp)<3:
					print "DAMN:",lp," can't loop from",e.v[0]
				else:
					loops.append(lp)
	return loops

				
###################################################################
# Pretty Quad Filler                                              #
###################################################################


#This may be a little faster if conversted to a 2D function using the desired
#normal as the Z axis (doing a matrix transformation)

#Add a face to an nmesh
#Select verts as applicable
def AddFace(oldFace,newMesh,vertexList,selected):
	vxl=[]
	for v in vertexList:
		if v.newCounterpart==0:
			v.newCounterpart=NMesh.Vert(v.tco[0],v.tco[1],v.tco[2])
			newMesh.verts.append(v.newCounterpart)
			v.used=1
		if selected:
			v.newCounterpart.sel=1
		vxl.append(v.newCounterpart)
	newFace=NMesh.Face(vxl)
	if oldFace.counterPart:
		newFace.smooth=oldFace.counterPart.smooth
	newMesh.faces.append(newFace)

def JoinConcentric(vertList,enclosed,CCWlist,allList,normal,f,nm):
	#Preffer parallel edges (smaller dot product absolute value)
	#something is wrong here... should be both close _and_ parallel
	#not just close...
	bestOuter=0
	bestInner=0
	parallelness=10000000
	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+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?
				vc=vertList[On].tco-vl[In].tco
				par=par*DotVecs(vc,vc)
				if (par<parallelness):
					#does this not intersect w/ any existing edges?
					if TestEdgeIntersectLoop3D(vertList[On],vl[In],vertList)==0:
						ok=1
						for vl2 in CCWlist:
							if TestEdgeIntersectLoop3D(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<10000000:
		#if we have a winner, add its points to the real loop
		#this means one edge is in there twice
		#(as it should be since it is used by two faces)
		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)
		#remove the added points from the lists of loops
		#that might be inside this loop
		CCWlist.remove(bestInner[0])
		if FillProcessedLoop(newVL,CCWlist,allList,normal,f,nm):
			return 1
		else:
			print "attempt to connect loops failed... (uh-oh... bug?)"
	else:
		print "couldn't find path to connect concentric loops"
	return 0


#fill in terms of n-sided convex polygons
def nFillLoop(sides,vertList,CCWlist,normal,oldFace,newMesh,selected,tolerance):
		#try all ways to fill this loop using points on the edges
		#there are len(vertList) possible faces we need to test
		count=len(vertList);
		for i in range(count):
			convex=1
			#test convexity
			loop=[]
			loopReal=[]
			for j in range(sides):
				d=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)
				#print d,0.000001
				if d<tolerance:
					convex=0
					break
				loop.append((i+j)%count)
				loopReal.append(vertList[(i+j)%count])
			#if its convex, then we can investigate further
			#print "CX:",convex,loop,vertList
			if convex:
				#test no verts in face
				ok=1
				for p in vertList:
					nocheck=0
					for lp in loopReal: #don't test the verts that make the new face
						if p==lp:
							nocheck=1

					if nocheck==0 and TestPointInConvexLoop(p.tco,loopReal,normal):
						ok=0
						break
				#if the new edge doesn't cut into existing edges
				#(determined with the TestPointInConvexLoop above)
				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 FillProcessedLoop(newVL,CCWlist,normal,oldFace,newMesh,selected):
							#print "Face! ",[vertList[i],vertList[(i+1)%count],vertList[(i+2)%count],vertList[(i+3)%count]]
							AddFace(oldFace,newMesh,loopReal,selected)
							return 1
						else:
							1
							#print "failed..."
							#for vx in vertList:
							#	print vx.tco
							#print "--------------------------"
					else:
						#There is apparently a heirarchy of loops here
						#Connect this loop to a revelvant inner loop
						return JoinConcentric(vertList,enc,CCWlist,normal,oldFace,newMesh,selected)
			#else:
			#	print "Not Convex..."
		#print "Fail fill size",sides
		return 0


def FillProcessedLoop(vertList,CCWlist,normal,oldFace,newMesh,selected):
	#Four or more points, then we try to fill with quads
	if len(vertList)>3:
		if nFillLoop(4,vertList,CCWlist,normal,oldFace,newMesh,selected,0.00001):
			return 1
	#Three points or quad fill failed, we try to fill with tris
	if len(vertList)>2:
		if nFillLoop(3,vertList,CCWlist,normal,oldFace,newMesh,selected,0.00001):
			return 1
		else:
			#if it failed, don't be as picky about what is convex.
			if len(vertList)>3:
				if nFillLoop(4,vertList,CCWlist,normal,oldFace,newMesh,selected,0):
					return 1
				#Three points or quad fill failed, we try to fill with tris
			if nFillLoop(3,vertList,CCWlist,normal,oldFace,newMesh,selected,0):
					return 1
			else:
					return 0
	#if there are less than three points we're done
	else:
		return 1


def FillPreprocess(VertexLists,normal):
	RightWay=[]
	WrongWay=[]

	for ThisList in VertexLists:
		lastTest=ThisList[len(ThisList)-1]
		FlipList=0
		Direction=0
		#this runs the test multiple times. Realy just two times were you get the same result in
		#a row should be sufficient, or once in "fast mode"
		for testpt in ThisList:
			#Have the ray start midway on the segment because it may get confused on the edges
			midpt=MidPoint(lastTest.tco,testpt.tco)
			#The ray is perpendicular to the edge and the normal
			ray=CrossVecs(testpt.tco-lastTest.tco,normal)
			#print "B:",ThisList[0].tco,ThisList[1].tco,"->",midpt,ray

			isect_counter_all=0
			isect_counter_others=0

			for OtherList in VertexLists:
				prevVert=OtherList[len(OtherList)-1]
				for Vert in OtherList:
					#print Vert.tco
					if not ((prevVert==lastTest)): #Don't even try to test for intersection with self
						#print "TX: ",midpt,midpt+ray,prevVert.tco,Vert.tco,testpt.tco,lastTest.tco
						isect=FindIntersectLineLine3D(midpt,midpt+ray,prevVert.tco,Vert.tco,1,0,0)
						#if len(isect):
						#	print "\tX:",isect[0],isect[1],midpt+ray*isect[0],isect[2]
						if (len(isect)>0 and isect[0]>0):
							isect_counter_all+=1
							if (not OtherList==ThisList):
								isect_counter_others+=1
					prevVert=Vert

			#if the ray intersects an odd number of edges, it is pointing in the wrong direction
			#if it is pointing in the wrong direction, the verticies aren't ordered right
			if (isect_counter_all&1==1):
				#print "Flipped List"
				FlipList+=1
				#ThisList.reverse()
			else:
				FlipList-=1

			#if it intersects an even number of edges of objects other than it self
			#then it is an outer loop in a set of concentric loops (i.e. the outer edge of a doughnut)
			if (isect_counter_others&1==0):
				Direction+=1
				#RightWay.append(ThisList); 
			#otherwise it is an inner loop (the edges that make up the hole of a doughnut)
			#and the verts are ordered in the other direction
			else:
				Direction-=1
				#WrongWay.append(ThisList);
				
			lastTest=testpt
			
		#apply direction...
		#print "Flipped: ",FlipList,"Direction:",Direction 
		if FlipList>0:
			ThisList.reverse()
		if Direction>0:
			RightWay.append(ThisList)
		else:
			WrongWay.append(ThisList)
		lastTest=testpt
		
	#print "Right Way:",len(RightWay),"WrongWay:",len(WrongWay)
	return [RightWay,WrongWay]


def FillLoops(loops,oldFace,newMesh,flip,selected):

	if loops==[]:
		return
		
	#print "SRART FILLL------"		
		
	#if the face needs to be flipped (i.e. when doing a difference operation)
	normal=oldFace.normal*flip

	#First establish loop directions
	FixedLists=FillPreprocess(loops,normal)	

	#Now make two lists - clockwise and counterclockwise
	CWlist=FixedLists[0]
	CCWlist=FixedLists[1]

	#Time to fill!
	for l in CWlist:
		i=FillProcessedLoop(l,CCWlist,normal,oldFace,newMesh,selected)
		if i==0:
			print "\t\t\tFill Failed..."
			for v in l:
				print "\t\t\t\t",v.tco,v

###################################################################
# Boolean Op objects                                              #
###################################################################

# 0 -> Unknown
# 1 -> Outside
# 2 -> Inside
# 3 -> Coplanar -> normals in same direction
# 4 -> Coplanar -> opposing normals
# 5 -> cut face
		
class bVert:
	def __init__(self,coord,normal=0):
		global traversalCookie
		self.travCookie=traversalCookie
		coord.resize3D()
		self.tco=coord
		self.sharedvert=0
		if normal:
			self.normal=normal
		else:
			self.normal=Vector([0.0,0.0,0.0,1.0])
		self.e=[]
		self.f=[]
		self.newCounterpart=0
		self.redirect_to=0
		self.redirect_from=0

	def findSide(self,otherObject):
		print "\t\t\tlame vert side look up -",self,self.tco
		ray=Vector([1,0,0])
		ifaces=0
		for f in otherObject.faces:
			if TestIntersectRayFace(self.tco,ray,f,1):
				ifaces+=1
		if (ifaces%2)==1:
			return 2
		else:
			return 1

	def ApplyFaceIntersection(v,f):
							print "VERT LIES IN FACE! (",v," in ",f,")--------------------------------------------------------------------------------"

							for ve in v.e:
								if ve.v[0].GetRedirectTo()==v.GetRedirectTo():
									evect=ve.vect
								else:
									evect=ve.vect*(-1)
								d=DotVecs(evect,f.normal)
								if d>0.000001:
									ve.state=1
									for ef in ve.f:
										ef[0]=1
								elif d<-0.000001:
									ve.state=2
									for ef in ve.f:
										ef[0]=2
								else:
									print "EDGE LIES IN FACE!!!! ",d
									ve.ApplyIntersection(f,v)
													
							#mark as shared and such and move on
							v.sharedvert=1
							v.f.append(f)
							f.extraVerts.append(v)
							f.state=5

	def GetRedirectTo(vA):
		if vA.redirect_to==0:
			return vA
		return vA.redirect_to.GetRedirectTo()
	def GetRedirectFrom(vA):
		if vA.redirect_from==0:
			return vA
		return vA.redirect_from.GetRedirectFrom()
	def MergeVert(vA,vB):
		if vA.GetRedirectTo()==vB.GetRedirectTo():
			return
		dest=vA.GetRedirectFrom()
		src=vB.GetRedirectTo()
		src.redirect_to=dest
		dest.redirect_from=src
		print "Redirection Created!!!!",src.tco,dest.tco
	
	def real(self):
		if (self.redirect_to!=0):
			return self.GetRedirectTo().real()
		if (self.redirect_from==0):
			return self
		nextfrom=self.redirect_from
		while (nextfrom):
			#if nextfrom.crossed:
			#	self.crossed=1
			if nextfrom.sharedvert:
				self.sharedvert=1
			for nff in nextfrom.f:
				notfound=1
				for f in self.f:
					if (f==nff):
						notfound=0
				if (notfound):
					#print "af:",nff
					self.f.append(nff)
			for e in nextfrom.e:
				if e.v[0]==nextfrom:
					e.v[0]=self
				elif e.v[1]==nextfrom:
					e.v[1]=self
				self.e.append(e)
			nextfrom.redirect_to=self
			nextfrom=nextfrom.redirect_from
		self.redirect_from=0
		print "RVert: ",self,self.tco#,self.inside,self.outside,self.cutBy	
		return self
			
class bEdge:
	def __init__(self,bv0,bv1,infinite=0):
		global traversalCookie
		self.travCookie=traversalCookie
		i=0
		self.children=[]
		self.cutpoint=0
		self.f=[]
		self.v=[bv0,bv1]
		self.bb=BuildBounds(bv0.tco,bv1.tco)
		self.vect=bv1.tco-bv0.tco
		self.len=self.vect.length
		self.dot=DotVecs(self.vect,self.vect)
		self.infinite=0
		self.state=0
		bv0.e.append(self)
		bv1.e.append(self)
		print "\t\tAdding Edge... ",self,bv0.tco,bv1.tco

	def ApplyIntersection(e,f,v):
		#Step 1 - remove instances of this face:
		for ef in e.f:
			if ef[1]==f:
				e.f.remove(ef)
				
		op=Vector([0,0,0])
		cofaces=0
		#Step 2 - figure out the two original face's sides
		for ef in e.f:
		 	if ef[1].parent==e.f[0][1].parent:
				dc=DotVecs(f.normal,ef[1].center-v.tco)
				if abs(dc)<0.000001:
					if DotVecs(f.normal,ef[1].normal)>0:
						print "\tCOPLANAR FACES - SAME - ",ef,dc
						ef[0]=3
						e.f.append([3,f])
						f.coedges.append(e)
						cofaces=1
					else:
						print "\tCOPLANAR FACES - OPPOSING - ",ef,dc
						ef[0]=4
						e.f.append([4,f])
						f.coedges.append(e)
						cofaces=1
				elif dc>0: #outside
					print "\tOUTSIDE - ",ef,dc
					op+=ef[1].center
					ef[0]=1
				else:
					print "\tINSIDE - ",ef,dc
					ef[0]=2
					op+=ef[1].center
		
		#Step 3 - figure out if this face is anything relative to the edge's faces
		if (cofaces==0):
			#simple case - part is inside, the other is outside
			e.f.append([1,f])
			e.f.append([2,f])
		else:
			nt=e.f[0][1].normal+e.f[1][1].normal
			nt.normalize()
			dA=DotVecs(nt,f.normal)
			dB=DotVecs(op-v.tco,f.normal)
			if dA>0.9999999: #cosame
				print "\tSELF SAME - ",f,dA,dB,e.f
				e.f.append([3,f])
			elif dA<-0.9999999:
				print "\tSELF OPPOSING - ",f,dA,dB,e.f
				e.f.append([4,f])
			elif (dA>0 and dB<0) or (dA<0 and dB>0): #outside
				print "\tSELF OUTSIDE - ",f,dA,dB,e.f
				e.f.append([1,f])
			else:
				print "\tSELF INSIDE - ",f,dA,dB,e.f
				e.f.append([2,f])
				
	def partition(self,cutVert,normals):
		#cutpoint=DotVecs(self.vect,cutVert.tco-self.v[0].tco)
		cv=cutVert.tco-self.v[0].tco
		cutpoint=(DotVecs(cv,self.vect)/self.dot)*self.len
		#print "CUTPOINT: ",cutpoint,self.len-cutpoint
		#cv2=cutVert.tco-self.v[1].tco
		#cutpoint=DotVecs(cv,cv)
		print "\t\t   Partitioning edge",self," by ",cutVert.tco," between ",self.v[0].tco,self.v[1].tco

		#if applicable, perform operation on one of the child segments	
		if self.children:
			cd=cutpoint-self.cutPoint
			#0.00001 or smaller needed for booltest-anim? - refined
			#maybe 0.001 or so is good... for now using 0.0001
			if cd<0.001 and cd >-0.001:
				print "\t\tBranching both ways on ",self,"A"
				#If applicable...follow branch both ways - needed sometimes
				self.children[1].partition(cutVert,normals)
				print "\t\tBranching other way on ",self,"B"
				self.children[0].partition(cutVert,normals)
				return
			elif cutpoint>self.cutPoint:
				return self.children[1].partition(cutVert,normals)
			else:
				return self.children[0].partition(cutVert,normals)

		#if cutpoint is too close to one of our verts, mergeverts
		if cutpoint <0.0004:
			self.v[0].MergeVert(cutVert)
			A=0
			B=self
			Adone=1
			Bdone=0
		elif cutpoint>(self.len-0.0004):
			self.v[1].MergeVert(cutVert)
			A=self
			B=0
			Adone=0
			Bdone=1
		else:			
			#otherwise, make new edges
			self.v[0].e.remove(self)
			self.v[1].e.remove(self)
			self.cutPoint=cutpoint
			A=bEdge(self.v[0],cutVert)
			B=bEdge(cutVert,self.v[1])
			self.children.append(A)
			self.children.append(B)
			for f in self.f:
				B.f.append([0,f[1]])
				A.f.append([0,f[1]])
			Adone=0
			Bdone=0
			
		Astate=Bstate=0
		
		#determine inside vs outside
		normTot=Vector([0.0,0.0,0.0])
		ld=0
		print "\t\t   Normals:",normals
		for n in normals:
			normTot+=n[0]
			vx=n[1]-cutVert.tco
			ds=DotVecs(vx,self.vect)
			d=DotVecs(n[0],self.vect)
			if d<0.000001 and d>-0.000001:
				if ds>0:
					ae=B
					Bdone=1
				else:
					ae=A
					Adone=1
				print "\t\t\tEdge cut by parallel face...",cutVert.tco,ae
				if ae:
					for f in ae.f:
						if f[1].parent==ae.f[0][1].parent:
							nA=n[0]
							#print "f:",f,"n:",n
							nB=f[1].normal
							d=DotVecs(nA,nB)
							if d>0.99999:
								print "\t\t\t   COPLANAR - SAME",f[0],f[1],d
								f[0]=3
								ae.ApplyIntersection(n[2],cutVert)
							elif d<-0.99999:
								print "\t\t\t   COPLANAR - OPPOSING",f[0],f[1],d
								f[0]=4
							else:
								d=DotVecs(n[0],f[1].center-cutVert.tco)
								print "\t\t\t   EDGE-FACE PARALLEL WAS ",f[0],f[1],d
								if d>0:
									f[0]=1
								else:
									f[0]=2
								print "\t\t\t   EDGE-FACE PARALLEL",f[0],f[1],d
			else:
				if ds>0.00001:
					if d>0:
						Bstate=1
					else:
						Bstate=2
				elif ds <-0.00001:
					if d<0:
						Astate=1
					else:
						Astate=2
					
				print "\t\t\t\tFL:",ds,d
				
		d=DotVecs(normTot,self.vect)
		if (d==0): #parallel??
			print "Edge cut by a parallel face - something is wrong"
			return
		elif (d > 0):
			if Astate==0:
				Astate=2
			if Bstate==0:
				Bstate=1
		else:
			if Astate==0:
				Astate=1
			if Bstate==0:
				Bstate=2
		#print d,normTot,self.vect,normals
		if A and Adone==0:
			A.state=Astate
			print "\t\t\tA:",Astate,A.v[0].tco,A.v[1].tco,A.f
			for f in A.f:
				if f[0]>0 and f[0]!=Astate:
					print "#$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$#"
				if f[1].parent==A.f[0][1].parent:
					f[0]=Astate
		if B and Bdone==0:
			B.state=Bstate
			print "\t\t\tB:",Bstate,B.v[0].tco,B.v[1].tco,B.f
			for f in B.f:
				if f[0]>0 and f[0]!=Bstate:
					print "#$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$#"
				if f[1].parent==B.f[0][1].parent:
					f[0]=Bstate
				
		if A!=self and B!=self:
			self.state=5
		
	#WARNING: Must increase Traversal Cookie before calling this
	def getState(self,otherObject,dontguess=0):
		global traversalCookie
		if self.state:
			return self.state
		print "Need to resolve state for edge ",self,self.v[0].tco,self.v[1].tco
		ts=0
		for fc in self.f:
			if ts>0 and ts!=fc[0]:
				self.state=5
				return 5
			else:
				ts=fc[0]
		if ts>0:
			self.state=ts
			return ts
			
		self.travCookie=traversalCookie
		for v in self.v:
			rv=v#v.real()
			if rv.sharedvert==0:
				for e in rv.e:
					#if e.f[0][1].parent==self.f[0][1].parent and e.travCookie<traversalCookie:
					if e.travCookie<traversalCookie:
						es=e.getState(otherObject,1)
						if es>0 and es<5:
							print "\t",self,"using state from ",e,":",es
							self.state=es
							for f in self.f:
								f[0]=es
							return es
						else:
							print "\t",self,"not using state from ",e,":",es,e.f
		if dontguess==0:
			#all edge failed...gotta do it the lame way with a verts
			es=self.v[0].findSide(otherObject)
			self.state=es
			for f in self.f:
				f[0]=es
			return es
		else:
			return 0
					
	def testState(self,state,face):
		#if self.state>0 and self.state<5:
		#	if self.state==state:
		#		for f in self.f:
		#			if f[1]==face:
		#				return 1
		#	return 0
		for f in self.f:
			#print "\tState: ",self,f[0],self.state,f[1],face
			if f[0]==state and f[1]==face:
				return 1
		return 0
		
			
class bFace:
	def __init__(self,nmFace,parent,virtual=0):
		global traversalCookie
		self.travCookie=traversalCookie
		
		self.parent=parent
		self.state=0
		self.e=[]
		self.v=[]
		self.extraVerts=[]
		self.coedges=[]
		self.center=Vector([0.0,0.0,0.0])
		#self.altered=0
		
		print "\tAdding Face..."
		self.counterPart=nmFace


		if virtual:
			self.normal=0
		else:
			if parent.matrix:
				self.normal=VecMultMat(Vector(nmFace.no),parent.rot)
			else:
				self.normal=Vector(nmFace.no)
		
			#First the verts
			for v in nmFace.v:
				bv=parent.verts[v.index]
				bv.f.append(self) #maybe not needed...
				self.v.append(bv)
				self.center+=bv.tco
			self.center/=len(self.v)
			
			self.bb=BuildBounds(self.v[0].tco,self.v[1].tco)
			self.bb=ExpandBounds(self.bb,self.v[2].tco)
			
			self.e.append(MakeEdge(self.v[0],self.v[1],self))
			self.e.append(MakeEdge(self.v[1],self.v[2],self))
			
			if len(self.v)==3:
				self.e.append(MakeEdge(self.v[2],self.v[0],self))
			else:
				self.bb=ExpandBounds(self.bb,self.v[3].tco)
				self.e.append(MakeEdge(self.v[2],self.v[3],self))
				self.e.append(MakeEdge(self.v[3],self.v[0],self))

	def getState(self,otherObject):
		#figure out inside/outside/etc based on edge if needed
		if self.state==0:
			global traversalCookie
			traversalCookie=traversalCookie+1
			self.state=self.e[0].getState(otherObject)
		return self.state
	
	def BuildEdgeLoop(self,e1=0):
		global traversalCookie
		if e1==0:
			e1=self.e[0]
			while (e1.children):
				e1=e1.children[0]
			e1.travCookie=traversalCookie	
			return [e1]+self.BuildEdgeLoop(e1)
		for v in e1.v:
			for e in v.e:
				if e.travCookie<traversalCookie:
					for f in e.f:
						if f[1]==self:
							e.travCookie=traversalCookie
							return [e]+self.BuildEdgeLoop(e)
		return []
						
			
	def constructFace(self,otherObject,destMesh,inside,outside,cosame,coopposing,flip=1):
		global traversalCookie
		self.getState(otherObject)
		if self.state<3: #Simple inside/outside face
			if (self.state==1 and outside) or (self.state==2 and inside):
				print "\tAdded Simple"
				AddFace(self,destMesh,self.v,inside)
		else: #Complicated face
			print "FACE:",self
			#Make sure the state of all edges is established
			for e in self.e:
				e.getState(otherObject)
				
			#Build Vert List
			allVerts=[]
			traversalCookie+=1
			for v in self.extraVerts:
				rv=v.real()
				if rv.travCookie<traversalCookie:
					rv.travCookie=traversalCookie
					#print rv,rv.tco,len(rv.f),len(rv.e)
					#for fx in rv.f:
					#	print "\t",fx,fx.parent
					allVerts.append(rv)
			for v in self.v:
				rv=v.real()
				if rv.travCookie<traversalCookie:
					rv.travCookie=traversalCookie
					#print rv,rv.tco,len(rv.f),len(rv.e)
					allVerts.append(rv)
				
			#Build edge list (should probably just keep this up to date when making new edges)
			allEdges=[]
			traversalCookie+=1
			allEdges=self.BuildEdgeLoop();
			for e in self.coedges:
				try:
					allEdges.index(e)
				except:
					allEdges.append(e)
			
			print "\tE:",len(allEdges),"V:",len(allVerts)

			#Build face lists for verts (this can probably be more efficient by building them ad the verts are created / updated)
			for v in allVerts:
				v.fl=[]
				for f in v.f:
					if f.parent!=self.parent: #r7 also omits co-planar faces... is is needed? (apparently it is to avoid criss-crossing edges in coplanar faces....there may be a more efficient solution...)
						d=DotVecs(f.normal/f.normal.length,self.normal/self.normal.length)
						if d>-0.999999 and d <0.999999:
							v.fl.append(f)
#						else:
#							for e in v.e:
#								for ef in e.f:
#									if ef[1]==self:
#										allEdges.append(e)
					
			#Build new edges
			c=len(allVerts)
			for i in range(c):
				vA=allVerts[i]
				for j in range(i+1,c):
					vB=allVerts[j]
					for fA in vA.fl:
						for fB in vB.fl:
							if fA==fB:
								print "\t  Face Cut...",vA.tco,vB.tco,fA,self,fA.parent,self.parent
								e=MakeEdge(vA,vB,self,1)
								if e!=[]:
									e.state=5
									allEdges.append(e)
								break
			
			#for e in allEdges:
			#	print "ED:",e.getState(),e.v[0].tco,e.v[1].tco
		
			#Build & fill loops
			ol=[]
			il=[]
			cs=[]
			co=[]
			ol=FilterEdges(allEdges,1,self)
			il=FilterEdges(allEdges,2,self)
			cs=FilterEdges(allEdges,3,self)
			co=FilterEdges(allEdges,4,self)
			print "All Verts in ",self
			for v in allVerts:
				print "\t",v,v.tco
			print "All Edges in ",self
			for e in allEdges:
				print "\t",e,e.v[0].tco,e.v[1].tco,e.v
				for f in e.f:
					if f[1]==self:
						print "\t\t->",f
					else:
						print "\t\t  ",f
			print "Filtered loops: for ",self
			print "\tOL: ",ol
			print "\tIL: ",il
			print "\tCS: ",cs
			print "\tCO: ",co
			if outside:
				FillLoops(ol,self,destMesh,flip,0)
			if inside:
				FillLoops(il,self,destMesh,flip,0)
			if cosame:
				FillLoops(cs,self,destMesh,flip,0)
			if coopposing:
				FillLoops(co,self,destMesh,flip,0)
			
class bMesh:
	def __init__(self,blenderObject,matrix):
		print "Adding mesh from: %s"%blenderObject.getName()
		
		#setup variables
		self.verts=[]
		self.faces=[]
		self.edges=[]
		self.infinite=0
		
		m=NMesh.GetRawFromObject(blenderObject.getName())
		self.nmesh=m
		
		#process verts
		self.matrix=matrix
		if (matrix):
			self.rot=rotmatrix=matrix.rotationPart()
			for v in m.verts:
				self.verts.append(bVert(VecMultMat(Vector(list(v.co)+[1]),matrix),VecMultMat(Vector(list(v.no)),rotmatrix)))
		else:
			for v in m.verts:
				self.verts.append(bVert(Vector(list(v.co)),Vector(list(v.no))))
					
		#process faces
		for f in m.faces:
			if len(f.v)>2:
				self.faces.append(bFace(f,self))
			else:
				#stuff related to infinite faces
				1
		#if there are just edges & not faces, make this face object infinite

	def constructFaces(self,otherObject,destMesh,inside,outside,cosame,coopposing,flip=1):
		print "Constructing Faces for ",self
		for f in self.faces:
			f.constructFace(destMesh,otherObject,inside,outside,cosame,coopposing,flip)

def MakeEdge(v0,v1,face,inout=0):
	#Check if it already exists...
	for e in v0.e:
		if e.v[0]==v1 or e.v[1]==v1:
			facenotfound=1
			fdebug=[]
			fentries=[]
			for f in e.f:
				if f[1]==face:
					facenotfound=0
					fdebug.append(f[0])
					fentries.append(f)
			if inout:
				print "\t    Altering Existing edge...maybe not a good idea",e.f
				if facenotfound==0:
					print "\t       Prior state(s): ",fdebug, " keeping!"
					return []
					for f in fentries:
						e.f.remove(f)
				e.f.append([1,face])
				e.f.append([2,face])
			if facenotfound:
				e.f.append([0,face])
			return e
	#if not, make a new edge
	e=bEdge(v0,v1)
	if inout:
		e.f.append([1,face])
		e.f.append([2,face])
	else:
		e.f.append([0,face])
	face.parent.edges.append(e)
	return e
	
	
def OverlayEdges(e1,e2):
	return 1


###################################################################
# The Magic - the Intersection detector & processor               #
###################################################################

def IntersectMeshes(meshA,meshB,doEdges=0):
	global traversalCookie
	global travBase
	#with infinite meshes, we can't do bound box testing
	if meshA.infinite or meshB.infinite:
		skipbounds=1
	else:
		skipbounds=0
		
	traversalCookie=traversalCookie+1
	if doEdges==1:
		travBase=traversalCookie
	for e in meshA.edges:
		travA=traversalCookie
		eV=[]
		for v in e.v:
			#print v,v.travCookie,travBase
			if v.travCookie<travBase:
				eV.append(v)
				v.travCookie=traversalCookie
		e.travCookie=traversalCookie
		for f in meshB.faces:
			travB=traversalCookie
			if skipbounds or TestBounds(e.bb,f.bb):
				#worth testing...
				#print e, " vs ", f
				fE=[]
				for e_ in f.e:
					if e_.travCookie<travA or 1: #Actually it seems we always need to test edge intersections...
						e_.travCookie=traversalCookie
						fE.append(e_)
				
				skipnext=0
				#edge vs Edge:
				for eA in fE:
					#break
					#Are the edges parallel?
					#The tolerance for how close edges must be to count as intersecting must be very small < the tolerance for nearby verts to count as the same vert squared (0.000001), but nonzero
					il=FindIntersectLineLine3D(e.v[0].tco,e.v[1].tco,eA.v[0].tco,eA.v[1].tco,1-skipbounds,0,1,0.0000001)
					if len(il)>0: #intersect somewhere
						print "\tInterecting Edges...maybe"
						#test crossing edges
						if il[0]>-0.00001 and il[0]<1.00001 and il[1]>-0.00001 and il[1]<1.00001:
							ip=e.v[0].tco+il[0]*e.vect
							print "\t  INTERSECT!!!",e,eA,ip,il[2]
							normA=[]
							normB=[]
							nv=bVert(ip)
							nv.sharedvert=1
							for ef in e.f:
								if e.f[0][1].parent==ef[1].parent: #Only original faces
									ef[1].state=5
									ef[1].extraVerts.append(nv)
									nv.f.append(ef[1])
									normA.append([ef[1].normal,ef[1].center,ef[1]])
							for ef in eA.f:
								if eA.f[0][1].parent==ef[1].parent:
									ef[1].state=5
									ef[1].extraVerts.append(nv)
									nv.f.append(ef[1])
									normB.append([ef[1].normal,ef[1].center,ef[1]])
							print "\t   Processing 1/2:",e,nv,normB
							e.partition(nv,normB)
							print "\t   Processing 2/2:",eA,nv,normA
							eA.partition(nv,normA)
							skipnext=1
						
				#test points in face
				if 1 or skipnext==0:
					for v in eV:
						#if vert in face, mark its edges if they are at a sufficient angle with the face
						if v.sharedvert==0 and TestPointInPlane(v.tco,f.normal,f.center) and TestPointInFace(v.tco,f):
							#gotta test all edges against normal...
							v.ApplyFaceIntersection(f)
							skipnext=1
					
				#edge already in face at tip? (damn nested loops... oh, well)
				if skipnext==0:
					for ev in e.v:
						for ef in ev.f:
							if ef==f:
								skipnext=1
							
				#test edge intersects face (only if edge doesn't lie in face)
				if skipnext==0:
					p=FindIntersectEdgeFace(e,f)
					if p:
						print "\tIntersection: ",p," in edge: ",e,e.v[0].tco,e.v[1].tco
						nv=bVert(p)
						nv.sharedvert=1 #mark vertex as shared by both objects
					
						#attributes related to this faces
						nv.f.append(f)
						f.state=5 #mark as altered
						f.extraVerts.append(nv)
					
						#attributes related to edge's faces
						for ef in e.f:
							ef[1].state=5
							#print "Applying to face ",ef
							ef[1].extraVerts.append(nv)
							nv.f.append(ef[1])
						
						#partition the edge (make new edges)
						e.partition(nv,[[f.normal,f.center,f]])
						#if it got snapped to one of the verts, then the vert lies in the face...
						if nv.GetRedirectTo()==e.v[0].GetRedirectTo():
							e.v[0].ApplyFaceIntersection(f)
						if nv.GetRedirectTo()==e.v[1].GetRedirectTo():
							e.v[1].ApplyFaceIntersection(f)
							#e.v[1].f.append(f)

###################################################################
# Base functions direction the operation                          #
###################################################################


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

	MatA=Matrix(*map(list,cookie.getMatrix()))
	MatB=Matrix(*map(list,cutter.getMatrix()))
	#MatB.invert()
	#MatA=MatA*MatB
	#MatB.identity()

	bCookie=bMesh(cookie,MatA)
	bCutter=bMesh(cutter,MatB)

	IntersectMeshes(bCutter,bCookie,1)
	print "###############################################################"
	IntersectMeshes(bCookie,bCutter,0)
	#IntersectMeshes(bCookie,bCutter,1)
	print "###############################################################"
	#IntersectMeshes(bCutter,bCookie,0)
	
	nm=NMesh.New()
	
	if x==1:
		bCookie.constructFaces(nm,bCutter,1,1,1,1)
	elif x==2:
		bCookie.constructFaces(nm,bCutter,1,0,1,0)
	elif x==3:
		bCookie.constructFaces(nm,bCutter,0,1,0,1)

	nm.mode=bCookie.nmesh.mode
	NMesh.PutRaw(nm,"foo"	)
	return

def Difference(cookie,cutter):
	MatA=Matrix(*map(list,cookie.getMatrix()))
	MatB=Matrix(*map(list,cutter.getMatrix()))
	#MatB.invert()
	#MatA=MatA*MatB
	#MatB.identity()

	bCookie=bMesh(cookie,MatA)
	bCutter=bMesh(cutter,MatB)

	IntersectMeshes(bCookie,bCutter,1)
	IntersectMeshes(bCutter,bCookie,0)
	
	nm=NMesh.New()
	bCutter.constructFaces(nm,bCookie,1,0,0,1,-1)
	bCookie.constructFaces(nm,bCutter,0,1,0,0,1)

	nm.mode=bCookie.nmesh.mode
	NMesh.PutRaw(nm,"foo")
	return

def Intersection(cookie,cutter):
	MatA=Matrix(*map(list,cookie.getMatrix()))
	MatB=Matrix(*map(list,cutter.getMatrix()))
	#MatB.invert()
	#MatA=MatA*MatB
	#MatB.identity()

	bCookie=bMesh(cookie,MatA)
	bCutter=bMesh(cutter,MatB)

	IntersectMeshes(bCookie,bCutter,1)
	IntersectMeshes(bCutter,bCookie,0)
	
	nm=NMesh.New()
	bCutter.constructFaces(nm,bCookie,1,0,1,0)
	bCookie.constructFaces(nm,bCutter,1,0,0,0)
	#bCookie.constructFaces(nm,bCutter,0,1,0,0)
	
	nm.mode=bCookie.nmesh.mode
	NMesh.PutRaw(nm,"foo")
	
	return

def Union(cookie,cutter):
	MatA=Matrix(*map(list,cookie.getMatrix()))
	MatB=Matrix(*map(list,cutter.getMatrix()))
	#MatB.invert()
	#MatA=MatA*MatB
	#MatB.identity()

	bCookie=bMesh(cookie,MatA)
	bCutter=bMesh(cutter,MatB)

	IntersectMeshes(bCookie,bCutter,1)
	IntersectMeshes(bCutter,bCookie,0)
	
	nm=NMesh.New()
	bCutter.constructFaces(nm,bCookie,0,1,1,0)
	bCookie.constructFaces(nm,bCutter,0,1,0,0)

	nm.mode=bCookie.nmesh.mode
	NMesh.PutRaw(nm,"foo")
	
	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"))
#Union(Object.Get("Cookie"),Object.Get("Cutter"))
#CookieCutter(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
#difference op should maybe just flip the normals of the B object and do an intersection
#
#For f-gons, don't cut with internal edges
#when making face do whole f-gon at once (so outer edge & inner loops)