#!BPY

"""
Name: 'MegaBool r15/pre1'
Blender: 243
Group: 'Object'
Tooltip: 'Perform boolean operations on meshes and get nice results.'
"""
__bpydoc__ ="""\
                                                                 <br>
 Experimental New Mesh Boolean Operations                        <br>
                                                                 <br>
 (C) 2007 Theodore K Schundler (tschundler)(@)(gmail)(com)       <br>
 FOR TESTING ONLY: Not production ready yet                      <br>
 Lastest version available for from:                             <br>
 http://epii.info/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>
   Subsurf and Edge Split should be turned off before using this <br>
 script. (Actually any modifiers are best disabled.)             <br>
                                                                 <br>
 TO DO:                                                          <br>
  * Set vertex colors & groups & weights                         <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. (per discussion with toloban)     <br>
                Also, 2nd object can now be a set of edge loops. <br>
                And 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>
  08-Apr-2005  Rewrite of alot - completely changed how inside   <br>
                vs outside determination works                   <br>
  24-Apr-2005  Rewrite filling (handles complicated cases faster)<br>
                fixed dumb mistakes in intersecting edges, fixed <br>
                transform of vertex normals.                     <br>
  25-Apr-2005  Fixed compatability issues with released versions <br>
                of Blender for Vector() constructor.             <br>
  02-May-2005  Fixed some issues with certain angles in building <br>
                loops. Better detection of intersecting edges.   <br>
                Filling avoids making faces with an area of zero.<br>
                Debugging data doesn't display by default, so it <br>
                runs faster. Creates a new mesh instead of       <br>
                writting over an old one.                        <br>
  14-Apr-2007  Updated with fixes from Henrik Pitkala, Hoehrer,  <br>
                and intrr. This fixes some version compatability <br>
                issues. It makes the order and selection the same<br>
                as Blender's internal bools. Also, the default   <br>
                recusion depth is increased - you can increase   <br>
                it further by updating the max_recusion variable.<br>
                Lastly, I added progress bar support             <br>
  21-Apr-2007  Faces now keep material and UVs.                  <br>
  02-Jun-2007  Rewrote intersection system again. New approach   <br>
                splits things into tris first, avoiding nonplanar<br>
                quad problems, and laying the ground work for    <br>
                f/n-gon support.
"""
__author__ = "Theodore K. Schundler"
__version__ = "r15/pre1 02-Jun-2007"
__email__ = ('Author EMail, tschundler:gmail*com')
__url__ = ('Script Web Page, http://epii.info/oss/blender/boolean',
	       'BlenderArtists Thread, http://blenderartists.org/forum/showthread.php?t=28414')

#Debugging Options
showdbg      = 0 #Spit out debugging info
drawenorm    = False #Draw Normals on Edges
drawoutline  = False #Draw outline of faces, but don't fill them
drawxpt      = False #Mark intersection points
makenewobj   = True  #Make a new object rather than replacing an existing one
usepsyco     = False #Use Psyco acceleration if available
fullpsyco    = False #Apply acceleration to the full script
max_recursion= 16384 #Increase this if you have recursion depth problems.


#Initialize defaults
traversalCrumb=0
messages=""
xpt=[]
fxf=0
exf=0
vxf=0
exe=0
vxe=0
vxv=0
#sfxf=0
sexf=0
svxf=0
sexe=0
svxe=0
svxv=0
fexf=0
ffxf=0
fexe=0

#Setup environment
import Blender
import sys
import time
from Blender import Object
from Blender.Window import DrawProgressBar
from Blender.Mathutils import *
from Blender import Mesh
from time import time
if usepsyco:
	try:
		import psyco
		print "Using Psyco for script acceleration"
	except:
		usepsyco=0

sys.setrecursionlimit(max_recursion)


#Match f'ns
def TestIntersectRayFacet(r_point,r_direction,face,positive_only=0):
	global showdbg
	d=FindIntersectRayPlane(r_point,r_direction,face.e[0].v[0].co,face.normal,positive_only)
	if d==0:
		return 0
	p=r_point+d*r_direction
	return TestPointInFacet(p,face)

def FindIntersectRayPlane(r_point,r_direction,p_point,p_normal,positive_only=0):
	global showdbg
	d=DotVecs(p_normal,r_direction)
	if abs(d)<0.0000001:
		return 0
	n=DotVecs(p_normal,p_point-r_point)
	nd=n/d
	if nd<0 and positive_only:
		return 0
	return nd

#same logic as Intersect Vert x Face
def TestPointInFacet(pt,f):
	el = f.el #edge loop
	elend = el
	in_edge = None
	while 1:
		enorm = el.getENorm()
		dv = DotVecs(pt - el.e.v[0].co, enorm)
		if dv < 0:
			return False
		el = el.next
		if el==elend: break

	return True

def BuildBasis(normal,edge):
	e2=CrossVecs(normal,edge)
	return [edge,e2]

def Make2D(basis,vector):
	return Vector([DotVecs(basis[0],vector),DotVecs(basis[1],vector)])

#Note, there should probably be three versions of the loop that calls this
#That way there isn't lots of unnecissary branching
def Make2DwIX(index,normscale,vector):
	if normscale>0:
		if index==0:
			return Vector([vector[1],vector[2]])
		if index==1:
			return Vector([vector[0],-vector[2]])
		return Vector([vector[0],vector[1]])
	else:
		if index==0:
			return Vector([vector[1],-vector[2]])
		if index==1:
			return Vector([vector[0],vector[2]])
		return Vector([vector[0],-vector[1]])


def xptdraw(nm):
	global showdbg
	global xpt,drawxpt
	if drawxpt:
		for pt in xpt:
			if pt[0]==0:
				p=pt[1]
				AddFace(0,nm,[bVert(p+Vector([0.0,0.01,0.0])),bVert(p-Vector([0.0,0.01,0.0]))],0)
				AddFace(0,nm,[bVert(p+Vector([0.01,0.0,0.0])),bVert(p-Vector([0.01,0.0,0.0]))],0)
				AddFace(0,nm,[bVert(p+Vector([0.0,0.0,0.01])),bVert(p-Vector([0.0,0.0,0.01]))],0)
			if pt[0]==1:
				p=pt[1]
				AddFace(0,nm,[bVert(p+Vector([0.007,0.007,0.0])),bVert(p-Vector([0.007,0.007,0.0]))],0)
				AddFace(0,nm,[bVert(p+Vector([0.007,0.0,0.007])),bVert(p-Vector([0.007,0.0,0.007]))],0)
				AddFace(0,nm,[bVert(p+Vector([0.0,0.007,0.007])),bVert(p-Vector([0.0,0.007,0.007]))],0)


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

#Objects
class LoopElement:
	def __init__(self,co,link):
		global showdbg
		self.co=co
		self.link=link
		self.bb=0
		self.next=0
	def copy(self):
		global showdbg
		ne=LoopElement(self.co,self.link)
		ne.next=self.next
		return ne
	def SetNext(self,next):
		global showdbg
		self.next=next
	def GetNext(self):
		global showdbg
		return self.next
	def Reverse(self,first,prev):
		global showdbg
		next=self.next
		self.next=prev
		if next==first:
			next.next=self
			return
		next.Reverse(first,self)
	def GetCo(self):
		global showdbg
		return self.co
	def GetNextCo(self):
		global showdbg
		return self.next.co
	def GetVector(self):
		global showdbg
		return self.next.co-self.co
	def GetEdgeNormal(self):
		global showdbg
		return CrossVec2D(self.GetVector())
	def TestEdgeIntersect(self,ptA,ptB,bb,stop):
		global showdbg
		if not self.bb:
			self.bb=BuildBounds2D(self.co)
			self.bb=ExpandBounds2D(self.bb,self.next.co)
		if TestBounds2D(self.bb,bb):
			if TestEdgeIntersectEdge2D(ptA,ptB,self.co,self.next.co):
				return True
		if self==stop:
			return False
		return self.next.TestEdgeIntersect(ptA,ptB,bb,stop)
	def nFill(self,n,tolerance,stop=0):
		global showdbg
		#print "nFill(",n,stop,")"
		if stop==self:
			return False
		if not stop:
			stop=self
		c=self
		ok=1
		#test if we can make a convex loop
		
		for i in range(n-2):
			no=c.GetEdgeNormal()
			no.normalize()
			#print "\t",c.next.co,c.next.GetVector(),no
			#this can probably be optimized to jump past the convex point
			#maybe convex points can be cached?
			if DotVecs(c.GetEdgeNormal(),c.next.GetVector())<tolerance:
				#print "Convex fail at ",c.next.co
				return self.next.nFill(n,tolerance,stop)
			prev=c
			c=c.next
		#print "\t",c.next.co,self.co-c.next.co,c.GetEdgeNormal()
		if DotVecs(c.GetEdgeNormal(),self.co-c.next.co)<tolerance+0.00000001:
			#print "Convex fail at 2p ",c.next.co
			return self.next.nFill(n,tolerance,stop)
		#print "\t",self.co,c.next.co-self.co,self.GetEdgeNormal()
		if DotVecs(self.GetEdgeNormal(),c.next.co-self.co)<tolerance+0.00000001:
			#print "Convex fail at 3p ",self.co
			return self.next.nFill(n,tolerance,stop)
		lastpt=c.next
		#print "\tconvex OK"
		
		#Does it break out of the loop (if the loop size is > n)
		if self!=lastpt.next:
			if (not Over180(c.next.GetVector(),c.GetVector()*-1.0,c.next.GetEdgeNormal(),c.GetEdgeNormal())) and DotVecs(self.co-c.next.co,c.next.GetEdgeNormal())<0.00001+tolerance:
				#print "Breaks out of original poly (test 1)",self.co,c.next.co,c.next.GetEdgeNormal()
				return self.next.nFill(n,tolerance,stop)
		
		#ok, so it's convex. But does it intersect any existing edges?
		c=c.next
		if c!=self:
			prev=c
			c=c.next
			#print "cross?",prev.co,c.co
			#test through all the other points in the loop to make sure
			#our face doesn't enclose them (which would mean edges intersect somewhere)
			while c!=self:
				#print "\tcross?",c.co
				tp=self
				ok=0
				#Note: should probably use and epsilon instead of zero.
				for i in range(n-1):
					if DotVecs(c.co-tp.co,tp.GetEdgeNormal())<0 or c.link==tp.link:
						ok=1
						break
					tp=tp.next
				if not ok:
					if DotVecs(c.co-tp.co,CrossVec2D(self.co-tp.co))<0 or c.link==tp.link:
						ok=1
				if not ok:
					#print "Cross Fail at ",c.co
					return self.next.nFill(n,tolerance,stop)
				prev=c
				c=c.next
			#print "no cross OK ------------------"

			#Test again that edge doesn't break out of loop
			if self!=lastpt.next:
				if (not Over180(-1.0*prev.GetVector(),self.GetVector(),prev.GetEdgeNormal(),self.GetEdgeNormal())) and DotVecs(lastpt.co-self.co,prev.GetEdgeNormal())<0.00001+tolerance:
					#print "Breaks out of original poly (test 2)",lastpt.co,self.co,prev.next.co,prev.co
					return self.next.nFill(n,tolerance,stop)
			nextnoprev=prev


			#make facet
			c=self
			facet=[]
			for i in range(n):
				#print "\t",c.co
				facet.append(c.link)
				prev=c
				c=c.next
			#do next
			self.next=prev

			#When moving on to the next step, take a step back if possible
			if self!=lastpt.next:
				res=nextnoprev.Fill()
			else:
				res=self.Fill()
			if res:
				res.append(facet)
				return res
			#for fault tolerance, something is returned if we got this far
			return [facet]
				
		else:
			#Apparently there is nothing else in the loop, so we're done
			c=self
			facet=[]
			for i in range(n):
				facet.append(c.link)
				c=c.next
			return [facet]
			
	def Fill(self):
		global showdbg
		#Maybe this would be better if it kept track of the loop size...
		#only or two vx? Then done.
		if self.next==self or self.next.next==self:
			#print self,"end"
			return []
		#only three faces?
		if self.next.next.next==self:
			#print self,"end3"
			return [[self.link,self.next.link,self.next.next.link]]
		#try to fill using Quads
		ret=self.nFill(4,0.01)
		if ret:
			#print self,"quads.."
			return ret
		#else try tris
		ret=self.nFill(3,0.01)
		if ret:
			#print self,"tris.."
			return ret 
		ret=self.nFill(4,0.0)
		if ret:
			#print self,"quads.. hightolerance"
			return ret
		#else try tris
		#print self,"high tolerance tris?"
		return self.nFill(3,0.0)
		
		
	def display(self,stop):
		global showdbg
		if showdbg:
			print "\t",self.co,self.link.tco
		if self==stop:
			return
		self.next.display(stop)

class BSPElement2D:
	def __init__(self,pt,normal):
		global showdbg
		self.pt=pt
		self.normal=normal
		self.inside=0
		self.outside=0
	def TestPoint(self,pt):
		global showdbg
		return DotVecs(pt-self.pt,self.normal)
	def AddEdge(self,ptA,ptB,normal):
		global showdbg
		testA=self.TestPoint(ptA)
		testB=self.TestPoint(ptB)
		if testA<0 or testB<0 or (testA==0 and testB==0):
			if self.outside:
				self.outside.AddEdge(ptA,ptB,normal)
			else:
				self.outside=BSPElement2D(ptA,normal)
		if testA>0 or testB>0  or (testA==0 and testB==0):
			if self.inside:
				self.inside.AddEdge(ptA,ptB,normal)
			else:
				self.inside=BSPElement2D(ptA,normal)
	def TestPointRecursive(self,pt):
		global showdbg
		if self.TestPoint(pt)>0:
			if self.inside:
				return self.inside.TestPointRecursive(pt)
			else:
				return True
		else:
			if self.outside:
				return self.outside.TestPointRecursive(pt)
			else:
				return False
			
#Expand Bounding Box
def ExpandBounds2D(Bounds,v):
	for i in range(2):
		if (Bounds[0][i]>v[i]):
			 Bounds[0][i]=v[i]
		if (Bounds[1][i]<v[i]):
			 Bounds[1][i]=v[i]
	return Bounds

#Build a bounding box
def BuildBounds2D(v):
	Bounds=[[v[0],v[1]],[v[0],v[1]]]
	return Bounds

#Test if bounding boxes overlap
def TestBounds2D(b1,b2):
	for i in range(2):
		if (b1[0][i]-0.001>b2[1][i]) or (b2[0][i]-0.001>b1[1][i]):
			return 0
	return 1

def CrossVec2D(v):
	return Vector([-v[1],v[0]])

def TestEdgeIntersectEdge2D(pA,pB,pC,pD):
	global showdbg
	vDC=pD-pC
	vBA=pB-pA
	Base=DotVecs(vBA,CrossVec2D(vDC))
	if Base==0:
		#Parallel
		return False
	CvAC=CrossVec2D(pA-pC)
	uA=DotVecs(vDC,CvAC)/Base
	if uA>=0 and uA<=1:
		uB=DotVecs(vBA,CvAC)/Base
		if uB>=0 and uB<=1:
			return True
	return False


#Determine if an angle should be regarded as > 180 degrees
def Over180(VectorA,VectorB,EdgeVectorA,EdgeVectorB):
	#return DotVecs(VectorA+VectorB,EdgeVectorA+EdgeVectorB)<0
	return DotVecs(VectorA,EdgeVectorB)<0


class VertexLoop:
	def __init__(self):
		global showdbg
		self.loopBase=self.loopLast=0
		self.enclosed=[]
		self.BSPBase=0
		
	#Adding points to the loop
	def AddPoint(self,co,link):
		global showdbg
		if self.loopLast:
			ne=LoopElement(co,link)
			self.loopLast.SetNext(ne)
			self.loopLast=ne
			self.bb=ExpandBounds2D(self.bb,co)
		else:
			self.loopBase=self.loopLast=LoopElement(co,link)
			self.bb=BuildBounds2D(co)
	def DonePoints(self):
		global showdbg
		self.loopLast.SetNext(self.loopBase)
		self.loopBase=self.loopBase.next
		
	#Are the verts ordered in the right direction for an outer loop?
	def IsWrongDirection(self):
		global showdbg
		
		#Find the leftmost point on the object
		leftmost=self.loopBase
		lp=leftmost.GetNextCo()
		cb=self.loopBase.GetNext()
		while cb!=self.loopBase:
			if cb.GetNextCo()[0]<lp[0]:
				leftmost=cb
				lp=cb.GetNextCo()
			cb=cb.GetNext()
		
		#Now compare it with a point even further left -
		#if the normals indicate that it is "inside", then the loop is backwards
		leftmostnext=leftmost.GetNext()
		refVect=Vector([self.bb[0][0]-1.0,self.bb[0][1]])-leftmostnext.GetCo()
		if Over180((-1)*leftmost.GetVector(),leftmostnext.GetVector(),leftmost.GetEdgeNormal(),leftmostnext.GetEdgeNormal()):
			if DotVecs(refVect,leftmost.GetEdgeNormal())>0 or DotVecs(refVect,leftmostnext.GetEdgeNormal())>0:
				return True
			else:
				return False
		else:
			if DotVecs(refVect,leftmost.GetEdgeNormal())>0 and DotVecs(refVect,leftmostnext.GetEdgeNormal())>0:
				return True
			else:
				return False
			
	
	def Reverse(self):
		global showdbg
		self.loopBase.Reverse(self.loopBase,0)

		
	#BSPs for determining loop heirarchy
	def BuildBSP(self):
		global showdbg
		current=stop=self.loopBase
		self.BSPBase=BSPElement2D(current.GetCo(),current.GetEdgeNormal())
		while (current.GetNext()!=stop):
			current=current.GetNext()
			self.BSPBase.AddEdge(current.GetCo(),current.GetNextCo(),current.GetEdgeNormal())
	def TestLoopInLoop(self,other):
		global showdbg
		if not TestBounds2D(self.bb,other.bb):
			return False
		if not self.BSPBase:
			self.BuildBSP()
		return self.BSPBase.TestPointRecursive(other.loopBase.GetCo())
	
	def TestEdgeIntersect(self,pA,pB):
		global showdbg
		bb=BuildBounds2D(pA)
		bb=ExpandBounds2D(bb,pB)
		self.loopBase.GetNext().TestEdgeIntersect(pA,pB,bb,self.loopBase)
	
	def JoinLoop(self,other):
		global showdbg
		#Reasonably big distance - bigger than anithing inside the shape
		dist=(self.bb[1][0]-self.bb[0][0])*(self.bb[1][1]-self.bb[0][1])
		pair=[]
		
		Ostop=Ocurrent=self.loopBase.GetNext()
		prevVect=self.loopBase.GetVector()*(-1)
		prevNorm=self.loopBase.GetEdgeNormal()
		Istop=other.loopBase
		while (1):
			
			Icurrent=Istop
			while (1):
				Icurrent=Icurrent.GetNext()
				
				vect=Icurrent.GetCo()-Ocurrent.GetCo()
				evect=Ocurrent.GetVector()
				enorm=Ocurrent.GetEdgeNormal()
				o180=Over180(evect,prevVect,enorm,prevNorm)

				#distance is less than current winner?
				d=DotVecs(vect,vect)
				#print "Distance: ",d
				if d<dist:
					#connecting edge would stay inside the outer loop?
					if (o180 and (DotVecs(vect,enorm)>0 or DotVecs(vect,prevNorm))) or ((not o180) and (DotVecs(vect,enorm)>0 and DotVecs(vect,prevNorm))):
						#And not intersect with anything?
						if not self.TestEdgeIntersect(Icurrent.GetCo(),Ocurrent.GetCo()):
							#And not with any other loops:
							ok=1
							for lp in self.enclosed:
								if lp.TestEdgeIntersect(Icurrent.GetCo(),Ocurrent.GetCo()):
									ok=0
									break
							if ok:
								#print "Winner: ",d
								dist=d
								pair=[Icurrent,Ocurrent]
							
				
				if Icurrent==Istop:
					break
			
			prevVect=evect*(-1)
			prevNorm=enorm
			Ocurrent=Ocurrent.GetNext()
			if Ocurrent==Ostop:
				break
	
		#success?
		if pair:
			#keep the edges going in the right direction...
			Icurrent=pair[0]
			Ocurrent=pair[1]
			#print "I/O",Icurrent.GetCo(),Ocurrent.GetCo()
			other.Reverse()
			#Connect the two loops
			Icopy=Icurrent.copy()
			Ocopy=Ocurrent.copy()
			Ocurrent.SetNext(Icopy)
			Icurrent.SetNext(Ocopy)
			return True
		if showdbg:
			print "ERROR: Could not connect loops."
		return False
	
	
	#Recursive filling!
	def Fill(self):
		global showdbg
		facets=[]
		#print "----Fill Loops: ",self,facets
		#If there are loops encompased by this loop, they must be done first
		if (self.enclosed):
			#If there are any loops inside this loop, fill then first
			for eeloop in self.enclosed[0].enclosed:
				#print "Fill enc"
				facets.extend(eeloop.Fill())
					
			#Get on with the connecting...
			self.JoinLoop(self.enclosed[0])
			print "Fill(): Connect:",self.loopBase.co,self.enclosed[0].loopBase.co
			self.enclosed.remove(self.enclosed[0])
			facets.extend(self.Fill())
			return facets
		#self.Display()
		res=self.loopBase.Fill()
		if res:
			facets.extend(res)
		return facets

#Figure out loop directions and such, building up loop objects
#Input: loops - an array of arrays of objects with a ".co" attribute
#       norm - Face normal
#Ouput: array of arrays or arrays [EdgeNormal,Coordinate,LinkToOriginal]
def BuildLoops(loops,norm):
	global showdbg
	#Re-orient points so we can safely use just X&Y coordinates
	# (note: if Normal *dot* <0,0,1>  is >>0, this isn't really necissary)
	#Basis=BuildBasis(norm,loops[0][1].tco-loops[0][0].tco)
	normix=0
	dirscale=abs(norm[0])
	if abs(norm[1])>dirscale:
		normix=1
		dirscale=abs(norm[1])
	if abs(norm[2])>dirscale:
		normix=2
	if norm[normix]>0:
		normscale=1.0
	else:
		normscale=-1.0

	NewLoops=[]
	for loop in loops:
		
		#Build Loop Content
		NL=VertexLoop()
		for pt in loop:
			#NL.AddPoint(Make2D(Basis,pt.tco),pt)
			NL.AddPoint(Make2DwIX(normix,normscale,pt.co),pt)
		NL.DonePoints()
		
		#NL.Reverse()
		
		#Fix direction if need be
		if NL.IsWrongDirection():
			if showdbg:
				print "loop at ",NL.loopBase.co," is backwards"
			NL.Reverse()

		NewLoops.append(NL)
		
	return NewLoops

#Make loops into a heirarchy of loops
def BuildHierarchy(loops):
	global showdbg
	for loopA in loops:
		for loopB in loops:
			if loopA!=loopB:
				if loopA.TestLoopInLoop(loopB):
					loopA.enclosed.append(loopB)
					loopA.enclosed=BuildHierarchy(loopA.enclosed)
					loops.remove(loopB)
					return BuildHierarchy(loops)
	return loops
				

def BuildFacets(loops,normal):
	global showdbg
	#Build up loops in the structure we need, and make sure
	#they are going the right direction
	newloops=BuildLoops(loops,normal)
	
	#if their are multiple loops, make a loop heirarchy
	if len(newloops)>1:
		newloops=BuildHierarchy(newloops)
	
	facets=[]
	for loop in newloops:
		r=loop.Fill()
		if showdbg:
			print r
		if r:
			facets.extend(r)
	return facets

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

	#Make loops of verts
	vxloops = []
	for loop in loops:
		vxloop = []
		e = loop
		elend = e
		while 1:
			vxloop.append(e.getL2NextVert())
			e = e.l2_next
			if e == elend:
				break
		vxloops.append(vxloop)

	if vxloops==[]:
		return
		
	global drawoutline
	if drawoutline:
		for loop in vxloops:
			c = len(loop)
			for i,v in enumerate(loop):
				AddFace(oldFace, newMesh, [v,loop[(i+1)%c]], 1)
		return

	fl=BuildFacets(vxloops,oldFace.facets[0].normal*flip)
	for facet in fl:
		AddFace(oldFace,newMesh,facet,selected)


def AddFace(oldFace,newMesh,vertexList,selected=False):
	global showdbg
	vxl=[]
	for v in vertexList:
		if not v.newCounterpart:
			newMesh.verts.extend(v.co)
			v.newCounterpart = newMesh.verts[len(newMesh.verts)-1]
			v.used=1
		if selected:
			v.newCounterpart.sel=1
		vxl.append(v.newCounterpart)
	if len(vxl) == 2:
		newMesh.edges.extend(vxl[0], vxl[1])
	else:
		#newFace=NMesh.Face(vxl)
		newMesh.faces.extend(vxl)
		nf = newMesh.faces[len(newMesh.faces)-1]
		if oldFace:
			1 #copy attributes


ES_UNKNOWN = 0
ES_OUTSIDE = 1
ES_INSIDE  = 2
ES_COSAME  = 3
ES_COOPPO  = 4
ES_CUTFACE = 5 #unused?
ES_DONE    = 6 #unused?

#to get "break 2" type behavior in an awkward as all get out python
class BreakLoop(Exception): pass

#Maybe mark BB done and add epsilon? Or add it on each vert add?
class BoundingBox:
	def __init__(self, v):
		self.bb=[]
		for pt in v:
			self.bb.append([pt,pt])
			
	def expand(self, v):
		for i,b in enumerate(self.bb):
			if (b[0] > v[i]):
				b[0] = v[i]
			elif (b[1] < v[i]):
				b[1] = v[i]
		return self

	#Tolerance Should be a little bigger than the default epsilon used later
	def test(self, other, tolerance = 0.0005):
		for i,b in enumerate(self.bb):
			o = other.bb[i]
			if b[0]-tolerance > o[1] or o[0]-tolerance > b[1]: 
				return False
		return True
	
	def testpt(self, pt, tolerance = 0.0005):
		for i,b in enumerate(self.bb):
			o = pt[i]
			if b[0] - tolerance > o or o - tolerance > b[1]:
				return False
		return True


class bVert:
	def __init__(self, co, original = None):
		self.original = original
		self.new = None
		self.co = co
		self.e = []
		self.shared = False
		self.newCounterpart = None
		self.merged = False
	def findEdge(self, other):
		for e in self.e:
			if e.getOtherVert(self) == other:
				return self
	def findSide(self, otherObject):
		global showdbg
		if showdbg:
			print "v.fS(): \t\t\tlame vert side look up -",self,self.co
		#Note: Maybe it would be faster to find the closest face,
		# (vector projection based's equation for the face, then test
		# if perpenduclar ray from face to pt lies in face. If not,
		# use closest vertex in the face.)
		ray=Vector([1,0,0])
		ifaces=0
		for f in otherObject.faces:
			for ft in f.facets:
				if TestIntersectRayFacet(self.co,ray,ft,1):
					ifaces+=1
		if (ifaces%2)==1:
			return 2
		else:
			return 1


#Faces have many facets.
#facets are flat surfaces (share the same normal)
#facets are convex (could use BSP, but it's probably more work than worth it)
#whereas faces may not always be flat or convex
class bFacet:
	def __init__(self, edges, face):
		global traversalCrumb
		self.altered = False
		self.traversalCrumb = traversalCrumb
		self.face = face #needed for calc sides to find mesh

		shared = edges[0].getSharedVert(edges[1])

		self.normal = CrossVecs(edges[1].getOtherVert(shared).co - shared.co,edges[0].getOtherVert(shared).co - shared.co)
		self.normal.normalize() #normalized to make it easy to calc distance of point from plane
		self.e = edges
		self.ell = []
		for e in edges:
			bEdgeFaceLink(e,self) #This sets up the self.ell entry
		for i,el in enumerate(self.ell):
			el.setNext(self.ell[(i+1)% len(edges)])
			el.assignLoop(self.ell[0])
		self.el = self.ell[0]
		self.loops = [self.el]
	def markAltered(self):
		self.altered = True
	def testAltered(self):
		return self.altered

class bFace:
	def __init__(self, mesh, original):
		global showdbg
		
		self.original = original
		self.mesh = mesh
		self.edges = []
		self.allVerts = []
		self.altered = False
		self.built = False
		
		for e in original.edge_keys:
			be = mesh.getEdge(e[0], e[1])
			#be.addFace(self)
			self.edges.append(be)
		
		for i,v in enumerate(original.verts):
			vp = mesh.verts[v.index]
			self.allVerts.append(vp)
			if i == 0:
				self.bb = BoundingBox(vp.co)
			else:
				self.bb.expand(vp.co)
		
		self.facets = []
		
		if len(original.v) == 3:
			nf = bFacet(self.edges, self)
			self.facets.append(nf)
		else:
			#For now, all quads are two tris
			v0 = mesh.verts[original.v[0].index]
			v1 = mesh.verts[original.v[2].index]
			fe = bEdge(v0, v1, None, False)
			nf = bFacet([self.edges[0],self.edges[1],fe], self)
			self.facets.append(nf)
			nf = bFacet([fe, self.edges[2],self.edges[3]], self)
			self.facets.append(nf)

	def constructFace(self,altered, otherObject,destMesh,inside,outside,cosame,coopposing,flip=1):
		global showdbg
		if showdbg:
			print "f.cf():\tConstructing face ",self
		#if self.built:
		#	return
		loops=[[],[],[],[],[]]
		for f in self.facets:
		 #print altered,f.testAltered()
		 if altered == f.testAltered():
		 #if True == altered:
			fl = []
			#if f.altered:
			#	print "Altered"
			#else:
			#	print "Same"
			#print "Handle facet",f
			for e in f.loops:
				#todo: Join applicable facets if edge has
				#    exactly two faces, same side + same face
				#    the join. If both halfedges are in different
				#    loops, join to one loop. If halfedges are
				#    from the same loop, split into two loops
				#print " +-- Go loop",e
				elend = e
				state = ES_UNKNOWN
				while 1:
					s = e.e.calcSides()
					if e.state != ES_UNKNOWN:
						state = e.state
						if not drawenorm:
							break
					#AddFace(None, destMesh, [e.e.v[0],e.e.v[1]])
					nv = e.getL2NextVert()
					pv = e.e.getOtherVert(nv)
					
					#print "   +-- Add Edge ", e,pv.co, nv.co
					#print "     +-- loop entry", e.f, e.loopstart, e.e
					if drawenorm:
						edge_dir = nv.co-pv.co
						edge_dir.normalize()
						enorm = e.getENorm();
						edge_angle = enorm - edge_dir
						mid =(e.e.v[0].co + e.e.v[1].co)*0.5
						for i in range(e.state+1):
							AddFace(None, destMesh, [bVert(mid+edge_dir * (i*0.025)),bVert(mid+edge_angle * 0.05+edge_dir * (i*0.025))])

					fl.append(e)
					e = e.l2_next
					if e == elend:
						break
					if e in fl:
						print "NON TERMINATING LOOP - next: ",e
						raise Exception
				if state == ES_UNKNOWN:
					if showdbg:
						print "Unknown side - traverse surface?"
					state = e.recursiveSideLookup()
				if state == ES_UNKNOWN:
					if showdbg:
						print "Unknown side - needs manual lookup"
					state = e.e.v[0].findSide(otherObject)
					if showdbg:
						print "result: ", state
				loops[state-1].append(e)

		#loops found, now fill them
		if outside:
			FillLoops(loops[0], self, destMesh, flip, 0)
		if inside:
			FillLoops(loops[1], self, destMesh, flip, 0)
		if cosame:
			FillLoops(loops[2], self, destMesh, flip, 0)
		if coopposing:
			FillLoops(loops[3], self, destMesh, flip, 0)
		self.built = True
			

class bEdgeFaceLink:
	def __init__(self,edge,facet):
		self.e = edge
		self.f = facet
		facet.ell.append(self)
		self.enorm = None
		self.state = ES_UNKNOWN
		edge.addFacet(self)
		
		#l2 next/prev are for building edge loops
		self.l2_next = None
		self.l2_prev = None
		self.loopstart = None
	def setNext(self, next):
		self.next = next
		self.l2_next = next
		next.l2_prev = self
		self.l2_vert = self.getNextVert()
	def getNextVert(self):
		return self.e.getSharedVert(self.next.e)
	def getL2NextVert(self):
		if self.e == self.l2_next.e:
			if self.e == self.l2_prev.e: #loop has only one edge
				return self.e.v[self.l2_vert]
			return self.e.getOtherVert(self.e.getSharedVert(self.l2_prev.e))
		return self.e.getSharedVert(self.l2_next.e)
	def printLoop(self):
		el = self
		elend = el
		print "  Loop: ",self.loopstart
		while 1:
			v = el.getL2NextVert()
			print "    ",v,el.e,v.co,el
			el = el.l2_next
			if el == elend:
				break
	def reverseLoop(self):
		self._reverseLoop(self)
	def _reverseLoop(self, stop):
		next = self.l2_next
		self.l2_next = self.l2_prev
		self.l2_prev = next
		if next == stop:
			return
		return next._reverseLoop(stop)
	def initLoop(self, other):
		#print "Init loop",self
		self.l2_next = self.l2_prev = other
		other.l2_next = other.l2_prev = self
		self.l2_vert = 0
		other.l2_vert = 1
		self.loopstart = self
		other.loopstart = self
	def reassignLoop(self, loop):
		if len(self.e.children):
			print "BUG: reassigning loops using a parent edgeloop entry"
		elend = self
		el = self
		while 1:
			#if el.loopstart == el:
			#	print "Reassign ",el," to ",loop
			el.loopstart = loop
			el = el.l2_next
			if el == elend :
				break
		
	def setL2Next(self, next):
		self.l2_next = next
		next.l2_prev = self
	def setEdge(self, e):
		self.e = e
	def assignLoop(self, loopstart):
		self.loopstart = loopstart
	def getLoop(self):
		return self.loopstart
	def getENorm(self):
		#Should it always be calculated? Something to check in the C version for impact
		#Or maybe calc on FxF - if BB hit, then make sure enorms are set up
		if self.enorm:
			return self.enorm
		#Note: here is another candidate for the edge ray
		sv =  self.getNextVert()
		if not sv:
			#eh? There's no shared vert?
			print "My Edge:",self.e," their edge",self.next.e
			print "My Verts:",self.e.v[0],self.e.v[0].co,self.e.v[1],self.e.v[1].co
			print "Their Verts:",self.next.e.v[0],self.next.e.v[0].co,self.next.e.v[1],self.next.e.v[1].co
			raise Exception
		eray = self.e.getOtherVert(sv).co - sv.co
		self.enorm = CrossVecs(eray,self.f.normal)
		#normalized for distance of vert from edge calc without extra dot product
		#Whether this is too expensive needs to be explored in the C version
		self.enorm.normalize()
		return self.enorm
	def assignLoopState(self, state):
		el = self
		elend = el
		while 1:
			el.state = state
			el = el.l2_next
			if el == elend:
				return

	#travel along the object's surface to find other faces whose side may have already been determined
	def recursiveSideLookup(self):
		global traversalCrumb
		traversalCrumb += 1
		return self._recursiveSideLookup(traversalCrumb)
	def _recursiveSideLookup(self,tc):
		el = self
		elend = el
		state = self.state
		el.f.traversalCrumb = tc
		while state == ES_UNKNOWN:
			if el.state != ES_UNKNOWN:
				state = el.state
			elif len(el.e.f) == 2:
				if el.e.f[0] == el:
					dl = el.e.f[1]
				else:
					dl = el.e.f[0]
				if dl.f.traversalCrumb < tc:
					state = dl._recursiveSideLookup(tc)
			el = el.l2_next
			if el == elend:
				break
		if state !=ES_UNKNOWN:
			self.assignLoopState(state)
		return state
			

class bEdge:
	#Maybe edge ray should be stored in edge?
	def __init__(self, v1, v2, original = None, real = True):
		global traversalCrumb
		self.traversalCrumb = traversalCrumb
		#print "Add Edge",v1.co,v2.co
		self.original = original
		self.v = [v1,v2]
		self.f = [] #Basically a radial edge loop like in bmesh
		self.real = real
		v1.e.append(self)
		v2.e.append(self)
		self.children = []
		self.cutpoint = -100000
		self.cutparent = None
		self.sidescomputed = False
	def getAllVerts(self):
		v = [self.v[0]]
		for c in self.children:
			v.extend(c.getAllVerts())
		v.append(self.v[1])
		return v
	def addFacet(self, facet):
		self.f.append(facet)
	def replaceVert(self, prev, new):
		if self.children:
			print "BUG? replace verts in edge that has been split"
			raise Exception
		if self.cutparent:
			print "replacing verts in child... potentially problematic - you can probably ignore a subsequent message about merging shared edges"
			cp = self.cutparent
			while cp.cutparent:
				cp = cp.cutparent
			return cp._replaceVert(prev,new)
		return self._replaceVert(prev, new)
	def _replaceVert(self,prev,new):
		#print "EE Replace verts in ",self
		if prev in self.v:
			ix = self.v.index(prev)
			self.v[ix] = new
			if len(self.children): #If first or last, only follow applicable branch
				return self.children[ix]._replaceVert(prev,new)
		for c in  self.children: #vert shared between children... could maybe figure out which child using bounds or dot product
			c._replaceVert(prev, new)
			
	def getOtherVert(self, vert):
		if self.v[0] == vert:
			return self.v[1]
		else:
			return self.v[0]
	def getSharedVert(self, other):
		for vA in self.v:
			for vB in other.v:
				if vA==vB:
					return vA
	def fixLoop(self, facet, el0, el1):
		if self.children:
			print "BUG! Call fixLoop() on parent edge instead of child."
		for v in self.v:
			#find a pair pf edges that this edge is inbetween
			if showdbg:
				print "Fix loops at vert",v,v.co
			OK = False
			try:
				for e in v.e:
					if e!=self:
						for el in e.f:
							if el.f == facet and showdbg:
								print "fL() candidate: ",el,el.f,el.l2_next
							#Note: if edge loops back on itself, get shared vert might not work right
							if el.f == facet and el != el0 and el!= el1 and (el.getL2NextVert() == v):
								#print " +-- Pass 1"
								###
								# Maybe this would be better testing the position of the other verts vs. the new edge's normals
								#   ....though there's still the >180 degrees problem...
								prev_el = el
								next_el = el.l2_next
								prev_v = el.e.getOtherVert(v)
								next_v = el.l2_next.e.getOtherVert(v)
								#maybe >180 should be precomputed?
								new_ray = self.getOtherVert(v).co - v.co
								
								if prev_el.e == next_el.e:
									#print " +-- Pass auto"
									#Edge loops back on itself -> no other candidates
									if showdbg:
										print " +-- PASS AUTO loops",prev_el.e,prev_el,next_el
										print "   - loops ",prev_el.getLoop(),el0.getLoop(),el1.getLoop(),next_el.getLoop()
									OK = True
								else:
									o180 = DotVecs(next_v.co - v.co, prev_el.getENorm())
									if (o180 > 0): #less than 180 degrees - test against both normals
										if DotVecs(new_ray, prev_el.getENorm()) > 0:
											if DotVecs(new_ray, next_el.getENorm()) > 0:
												OK = True
										if OK:
											if showdbg:
												print " +-- pass < 180",v.co
										elif showdbg:
											print " X-- fail < 180"
									else: #over 180 degrees - either normal
										if DotVecs(new_ray, prev_el.getENorm()) > 0:
											OK = True
										elif DotVecs(new_ray, next_el.getENorm()) > 0:
											OK = True
										if OK:
											if showdbg:
												print " +-- pass > 180",v.co
										elif showdbg:
											print " X-- fail > 180"
								if OK: #We have a winner
									#Need to figure out which side to join with with edge
									prev_ray = prev_v.co - v.co
									dRR = DotVecs(prev_ray, new_ray) #ray vs ray
									dNN = DotVecs(prev_el.getENorm(), el0.getENorm()) #normal vs normal
									new_next = el1
									new_prev = el0
									#perhaps better tolerance is the smaller of prev.prev^2 vs new.new^2
									if abs(dRR) > 0.00000000001 and abs(dNN) > 0.00001: #not perpendicular
										if showdbg:
											print "   +-- OK / not perpendicular",v.co, dRR, dNN
										if (dRR < 0 and dNN > 0) or (dRR > 0 and dNN < 0):
											new_next = el0
											new_prev = el1
									else:
										#if perpendicular test normals vs rays from each other
										dRN0 = DotVecs(prev_ray, el0.getENorm())
										dRN1 = DotVecs(new_ray, prev_el.getENorm())
										if showdbg:
											print "   +-- OK / perp",v.co, dRN0, dRN1,"(",dRR,dNN,")"
										if (dRN0 < 0 and dRN1 < 0) or (dRN0 > 0 and dRN1 > 0):
											new_next = el0
											new_prev = el1
									#print "reloop",new_prev, next_el, prev_el, new_next
									if new_prev.l2_next != new_next:
										#What causes this?
										if new_next.loopstart == next_el.loopstart:
											print "BUG! Joining same loop, but different directions"
											print " WAS:",prev_el,next_el,prev_el.getL2NextVert()
											print " INS:",new_next,new_prev,new_next.getL2NextVert()
											print " inxt:",new_next.l2_next,new_prev.l2_next
											print " iprv:",new_next.l2_prev,new_prev.l2_prev
											el = prev_el
											elend = prev_el
											me = Mesh.New("mm")
											lv = el.e.getOtherVert(el.getL2NextVert)
											print " st: ",lv,lv.co
											while 1:
												vvv = el.getL2NextVert()
												AddFace(0,me,[lv,vvv],0)
												print " * ",el,vvv,vvv.co
												el = el.l2_next
												lv = vvv
												if el == elend:
													break
											o = Blender.Scene.GetCurrent().objects.new(me, "mm")
											raise Exception
											#This fix is invalid
											t = new_next
											new_next = new_prev
											new_prev = t
										else:
											new_prev.reverseLoop()
										#if new_next.loopstart == next_el.loopstart:
										#	print "nofix"
									
									reloop = False
									if new_next.loopstart == next_el.loopstart:
										if showdbg:
											print "Joining loop to itself => need to make new loop"
										reloop = True
									else:
										if new_prev.loopstart in facet.loops: #may not have been added yet
											facet.loops.remove(new_prev.loopstart)
										if showdbg:
											print "Join ",new_prev.loopstart," to ",next_el.loopstart
										new_prev.reassignLoop(next_el.loopstart)
										
									new_prev.setL2Next(next_el)
									prev_el.setL2Next(new_next)

									if reloop:
										if next_el.loopstart != prev_el.loopstart:
											print "WTF... edges in same loop w/ different starts",next_el.loopstart, prev_el.loopstart
											
										loop = next_el.loopstart

										if showdbg:
											print "Current :",facet.loops
											print "Shared: ",next_el.loopstart, prev_el.loopstart
											print "Split",loop,"into",next_el,prev_el

										facet.loops.remove(loop)
										next_el.reassignLoop(next_el)
										prev_el.reassignLoop(prev_el)
										
										if next_el in facet.loops:
											#Shouldn't already be there
											raise Exception
										facet.loops.append(next_el)
										if prev_el in facet.loops:
											#Shouldn't already be there
											print facet.loops
											raise Exception
										facet.loops.append(prev_el)
										if next_el.loopstart == prev_el.loopstart:
											print "BUG! Loops same (",next_el.loopstart,") after reassignment"
									
									raise BreakLoop #Break out of loop to move to the next vert
			except BreakLoop:
				if showdbg:
					print "Join Loops for",facet,"OK at",v.co,prev_v.co,next_v.co
				pass
			if not OK:
				if showdbg:
					print "Could not find edge to link to",v.co,"in",facet
		#if not el0.l2_next and not el1.l2_next:
		#	facet.loops.append(el1)
		#	el0.assignLoop(el1)
		#	el1.assignLoop(el1)
		#if not el0.l2_next:
		#	el0.setL2Next(el1)
		#	if showdbg:
		#		print "loop",el0,el1,"in",facet
		#if not el1.l2_next:
		#	el1.setL2Next(el0)
		#	if showdbg:
		#		print "loop",el1,el0,"in",facet
		
		#if loops back on itself, it should be added to the main edge loop list
		if el0.l2_next == el0.l2_prev and el1.l2_next == el1.l2_prev:
			if showdbg:
				print "Add self loop: ",el0,el0.loopstart

			if el0.loopstart in facet.loops:
				#Shouldn't already be there
				raise Exception
			facet.loops.append(el0.loopstart)

	def cut(self, pt, vert = None):
		if self.cutparent:
			print "BUG!BUG!BUG! Cut child instead of parent"
			return self.cutparent.cut(pt, vert)
		
		dist = DotVecs(pt - self.v[1].co, pt - self.v[1].co)
		if showdbg:
			print "@#@#@#@#@#@#@# CUT: ",self,dist
		return self._cut(pt, dist, vert)
	def _cut(self, pt, dist, vert):
		global vxv, svxv
		#Branch to children if applicable
		if len(self.children):
			if dist > self.cutpoint:
				return self.children[0]._cut(pt,dist, vert)
			else:
				return self.children[1]._cut(pt,dist,vert)
			
		#Check for merging
		v0 = pt - self.v[0].co
		vxv += 1
		dist0 = DotVecs(v0,v0)
		#print "dist0: ",dist0, self.v[0].co
		if dist0 < 0.0000001: #Distance (0.0003) squared....maybe faster to test each axis separately?
			svxv +=1
			#need to merge verts
			if vert and self.v[0]!=vert:
				MergeVert(self.v[0], vert)
			return self.v[0]
		
		v1 = pt - self.v[1].co
		vxv +=1
		dist1 = DotVecs(v1,v1)
		#print "dist1: ",dist1, self.v[1].co
		if dist1 < 0.0000001: #Distance squared....maybe faster to test each axis separately?
			svxv +=1
			#need to merge verts
			if vert and self.v[1]!=vert:
				MergeVert(self.v[1], vert)
			return self.v[1]

		#No merge means we need to subdivide
		vtemp = vert
		vert = bVert(pt)

		self.cutpoint = dist
		if showdbg:
			print "CutEdge(): Partitioning Edge",self,"at",pt,"with",vert
		self.v[0].e.remove(self)
		self.v[1].e.remove(self)
		A = bEdge(self.v[0], vert) #maybe if using an existing vert, it could check for an existing edge?
		A.cutparent = self
		B = bEdge(vert, self.v[1])
		B.cutparent = self
		self.children = [A,B]
		for efl in self.f:
			efl.f.ell.remove(efl)
			flA = bEdgeFaceLink(A,efl.f)
			flB = bEdgeFaceLink(B,efl.f)
			flA.enorm = efl.getENorm()
			flB.enorm = efl.getENorm()
			#need to set next/prev based on loop direction
			if A.getSharedVert(efl.l2_next.e):
				flB.setL2Next(flA)
				flA.setL2Next(efl.l2_next)
				efl.l2_prev.setL2Next(flB)
			else:
				flA.setL2Next(flB)
				flB.setL2Next(efl.l2_next)
				efl.l2_prev.setL2Next(flA)

			if efl.loopstart == efl:
				#we are about to remove an edge that marks the start of a loop
				#loopstart must be reassigned
				efl.f.loops.remove(efl)
				if flA in efl.f.loops:
					#Shouldn't already be there
					raise Exception

				efl.f.loops.append(flA)
				flA.reassignLoop(flA)
			else:
				#otherwise, keep in same loop as parent
				flA.assignLoop(efl.loopstart)
				flB.assignLoop(efl.loopstart)
		if vtemp:
			MergeVert(vtemp, vert)
			vert = vtemp

		return vert

	#This is being really slow
	def calcSides(self):
		global showdbg
		if self.sidescomputed:
			if showdbg:
				print "e.CS(",self,"): Request to compute sides on edge already done"
			return
		if showdbg:
			print "e.CS(",self,"): start"
		if len(self.f) == 2: #futile on edge with only two faces
			self.sidescomputed = 1
			return
		#Possible check: if # of sides is odd, and > 1, then there is
		# an awkward non-manifold situation

		#if only two links in same facet, and other facet has side, use that
		for elA in self.f:
			if elA.state == ES_UNKNOWN or elA.state == ES_CUTFACE:
				closest = -1.1
				cf = None
				for elB in self.f:
					if elA.f.face.mesh != elB.f.face.mesh:
						d = DotVecs(elA.getENorm(), elB.getENorm())
						if d > closest:
							closest = d
							cf = elB
				if cf:
					#This second dot vecs shouldn't be needed
					#something is wrong here it seems. miscalculated edge normals?
					if closest > 0.9999 or DotVecs(cf.f.normal, elA.f.normal) > 0.9999:
						if showdbg:
							print "e.CS(): COPLANAR FACES!!!"
						#WARNING! This is error-prone. Really the full loop should be tested
						### This DOES cause problems, i.e. intersecting the numbers 2 and 5
						if DotVecs(elA.f.normal,cf.f.normal)>0:
							elA.state=cf.state=ES_COSAME
							cf.sidescomputed = True
						else:
							elA.state=cf.state=ES_COOPPO
							cf.sidescomputed = True
					else:
						d=DotVecs(elA.getENorm(),cf.f.normal)
						#print "!!!!!!!!!!!this face:",fA,"other:",cf
						if (d>-0.00001 and d < 0.00001):
							if showdbg or 1:
								print "e.cS(): BUG? Coplanar, but not?",d,closest,cf.getENorm(),elA.getENorm(),cf.f.normal,elA.f.normal
						elif d>0:
							elA.state=ES_OUTSIDE
						else:
							elA.state=ES_INSIDE
							
						#might as well to the other at the same time
						if cf.state == ES_UNKNOWN:
							d=DotVecs(cf.getENorm(),elA.f.normal)
							if (d>-0.00001 and d < 0.00001):
								if showdbg or 1:
									print "e.cS(): BUG? Coplanar, but not? (2)",d,closest
							elif d>0:
								cf.state=ES_OUTSIDE
								cf.sidescomputed = True
							else:
								cf.state=ES_INSIDE
								cf.sidescomputed = True

				else:
					if showdbg:
						print "e.cS(): Need to determine side recursively..."
					self.sidescomputed = 1
					return
		if showdbg:
			print "e.cS(): Computed Sides!",self.f		
		self.sidescomputed=1
		return
								
	def addFacetLinks(e, f):
		if len(e.children): #if edge split, facet links belong to children
			for c in e.children:
				c.addFacetLinks(f)
			return
		
		#double check
		for ef in e.f:
			if ef.f  == f:
				if showdbg:
					print "Inefficency: Facelink added for an edge that already has it"
				return
		
		ray = e.v[0].co - e.v[1].co #Yet another use for edge ray
		eflA0 = bEdgeFaceLink(e, f)
		eflA0.enorm = CrossVecs(f.normal, ray)
		eflA0.enorm.normalize()
		eflA1 = bEdgeFaceLink(e, f)
		eflA1.enorm = CrossVecs(f.normal, -ray)
		eflA1.enorm.normalize()
		eflA0.initLoop(eflA1)
		e.fixLoop(f, eflA0, eflA1)
		f.altered = True
	def addFacetLinksBetween(self, v0, v1, f):
		state = False
		if self.v[0] == v0 or self.v[0] == v1:
			state = True
		return self._addFacetLinksBetween(v0, v1, f, state)
	def _addFacetLinksBetween(self, v0, v1, f, state):
		if self.children:
			state = self.children[0]._addFacetLinksBetween(v0, v1, f, state)
			state = self.children[1]._addFacetLinksBetween(v0, v1, f, state)
			return state
		else:
			if state == True:
				self.addFacetLinks(f)
			if self.v[1] == v0 or self.v[1] == v1:
				state = not state
			return state
				
			

class bMesh:
	def __init__(self,blenderObject,matrix = None):
		print "Adding mesh from: %s"%blenderObject.getName()
		mt = time()
		
		self.obj = blenderObject
		self.name = blenderObject.getName()
		self.mesh = m = blenderObject.getData(False, True)
		
		progress_lbl = "Importing %s"%(self.name)
		progress_max = float(len(m.verts)+len(m.edges)+len(m.faces))
		progress = 0
		DrawProgressBar(0, progress_lbl)
		
		
		self.verts = []
		if (matrix):
			for v in m.verts:
				self.verts.append(bVert(v.co * matrix, v))
				progress+=1
				if ((progress & 511) == 0):
					DrawProgressBar(progress / progress_max, progress_lbl)
		else:
			for v in m.verts:
				self.verts.append(bVert(v.co, v))
				progress+=1
				if ((progress & 511) == 0):
					DrawProgressBar(progress / progress_max, progress_lbl)
		
		self.edges = []
		for e in m.edges:
			self.edges.append(bEdge(self.verts[e.v1.index],self.verts[e.v2.index],e))
			progress+=1
			if ((progress & 511) == 0):
				DrawProgressBar(progress / progress_max, progress_lbl)
	
		self.facets = []
		self.faces = []
		for f in m.faces:
			if len(f.v) > 2:
				self.faces.append(bFace(self, f))
		progress+=1
		if ((progress & 511) == 0):
			DrawProgressBar(progress / progress_max, progress_lbl)

		print "\tAdd Time: ",time()-mt

	def getEdge(self, i1, i2):
		v1 = self.verts[i1]
		v2 = self.verts[i2]
		for e in v1.e:
			if e.v[0] == v2 or e.v[1] == v2:
				return e
		return None


	def constructFaces(self,otherObject,destMesh,inside,outside,cosame,coopposing,flip=1):
		global showdbg
		#if showdbg:
		print "m.cF(): Constructing Faces for ",self

		global cf_progress
		cf_progress = 0
		if (len(self.faces)):
			DrawProgressBar(cf_progress / float(len(self.faces)), "Rebuild %s"%(self.name))


		t=time()
		for f in self.faces:
			#print "r0"
			f.constructFace(True, destMesh,otherObject,inside,outside,cosame,coopposing,flip)

		#return
		#take care of any loose ends in a 2nd pass
		for f in self.faces:
			#print "r1"
			f.constructFace(False, destMesh,otherObject,inside,outside,cosame,coopposing,flip)

		print "Face fill time: ",time()-t

def MergeEdge(eA, eB):
	global showdbg
	if eA == eB:
		return eA
	if showdbg:
		print "-=-=-=-=-=-=   MERGE EDGES",eA.v[0].co, eA.v[1].co,eA,eB
	if len(eA.children) or len(eB.children):
		print "BUG! merging edges that have already been split"
	#ghf = ghjg
	for v in eB.v:
		v.e.remove(eB)
		if not eA in v.e:
			print "BUG? Edge not already linked to vert"
			v.e.append(eA)
	for f in eB.f:
		f.setEdge(eA)
		ok = 1
		#This should maybe check that it isn't adding effectively the same facelink twice
		for efl in eA.f:
			if efl.f == f.f:
				print "BUG! Duplicate face entires in merged loop ##########################"
				print "fl:",f,efl
				print "e:",f.e,efl.e
				efl.printLoop()
				f.printLoop()
				#Make it so same item isn't in loop twice
				if efl.l2_next == f:
					print "A"
					efl.setL2Next(f.l2_next)
				elif f.l2_next == efl:
					print "B"
					f.l2_prev.setL2Next(efl)
				efl.printLoop()
				ok = 0
				#raise Exception
		if ok:
			eA.f.append(f)

	return eA

def MergeVert(vA, vB):
	global showdbg
	if vA==vB:
		return vA
	if showdbg:
		v = vA.co - vB.co
		print "+=+=+=+=+=+=+=+=+ I   MERGEVERTS",vA,vB,v.length,vA.co,vB.co
		print "MV Edges: ",vA.e,vB.e
	for e in vB.e:
		if e in vA.e:
			print "BUG! Edge from old vert already assigned to new vert"
		if e.v[0] == vA or e.v[1] == vA:
			
			print "BUG? Merge shared edge?", e,e.v[0],e.v[0].co,e.v[1],e.v[1].co
		else:
			#print "Replace verts in ",e
			e.replaceVert(vB, vA)
			#if vB in e.v:
			#	e.v[e.v.index(vB)]=vA
		vA.e.append(e)
	vB.merged = True
	#test if merge-edge neded
	for eA in vA.e:
		for eB in vA.e:
			if eA!=eB:
				shared = eA.getSharedVert(eB)
				ov1 = eA.getOtherVert(shared)
				ov2 = eB.getOtherVert(shared)
				if ov1==ov2:
					MergeEdge(eA, eB)
				else:
					#Does this really need to be done?
					v = ov1.co-ov2.co
					if v.length < 0.00001:
						if showdbg or 1:
							print "BUG? DOUBLE VERT at", ov1.co
						#MergeVert(ov1, ov2)

def IntersectVertEdge(el, pt, vert = None):
	return el.e.cut(pt,vert)


#Really vert x facet - must be convex + coplanar
def IntersectVertFace(f,pt,vert = None):
	global vxf,svxe,svxf,sexe,sexf,vxe,exe
	#we can maybe do a bounds test here
	vxf+=1
	el = f.el #edge loop
	elend = el
	in_edge = None
	while 1:
		if vert:
			vxe+=1
		else:
			exe+=1
		enorm = el.getENorm()
		dv = DotVecs(pt - el.e.v[0].co, enorm)
		if dv < -0.00001:
			return False
		if dv < 0.00002: #distance of vert from edge (Must be > than the prior test to make sure it doesn't count as inside a face where it should be outside)
			in_edge = el
			#note: if two edges in convex loop have an angle of near 180 degrees, it
			#may be necissary to keep multiple candidates for where the actual intersection was
		el = el.next
		if el==elend: break
	
	#vert lies in an edge
	if in_edge:
		if vert:
			svxe+=1
		else:
			sexe+=1
		return IntersectVertEdge(in_edge, pt, vert)
	
	#vert lies in the face
	if vert:
		svxf+=1
		return vert
	else:
		sexf+=1
		return True

def CoplanarIntersectEdgeFace(e,f):
	#Both points of e lie in the plane of f
	global fexe
	fexe+=1
	el = f.el #edge loop
	elend = el
	p0_inside = True
	p1_inside = True
	#Test points of test tedge vs. points of face edge
	cuts = []
	while 1:
		enorm = el.getENorm()
		dv0 = DotVecs(e.v[0].co - el.e.v[0].co, enorm)
		dv1 = DotVecs(e.v[1].co - el.e.v[0].co, enorm)
		if abs(dv0) < 0.00005 and abs(dv1) < 0.00005: #edges share common segment
			
			#for each edge, test if any of its verts lie in the other edge
			if showdbg:
				print "Edges overlap each other", e, el.e
			bb0 = BoundingBox(el.e.v[0].co)
			bb0.expand(el.e.v[1].co)
			for v in e.getAllVerts():
				bb1 = BoundingBox(v.co)
				if bb0.test(bb1, 0.00005):
					#print "A Cut edge at:",v.co
					nv = el.e.cut(v.co, v)
					#print " +-- ",nv ,v

			bb0 = BoundingBox(e.v[0].co)
			bb0.expand(e.v[1].co)
			for v in el.e.getAllVerts():
				bb1 = BoundingBox(v.co)
				if bb0.test(bb1, 0.00005):
					#print "B Cut edge at:",v.co
					nv = e.cut(v.co, v)
					#print " +-- ",nv ,v

			return
		if (dv0 < 0):
			p0_inside = False
		if (dv1 < 0):
			p1_inside = False

		#If they cross the straddle the edge (or lie in edge?), find intersection of virtual edge-plane and edge
		if (dv0 < 0 and dv1 > 0) or (dv0 > 0 and dv1 < 0): #edges cross
			eray = e.v[1].co - e.v[0].co #again with the edge ray
			d = DotVecs(enorm, eray)
			n = DotVecs(enorm, el.e.v[0].co - e.v[0].co) #aka -1 * dv1
			nd = n/d
			pt = e.v[0].co+nd * eray
			#is point with the range of the face's edge?
			bb0 = BoundingBox(el.e.v[0].co)
			bb0.expand(el.e.v[1].co)
			bb1 = BoundingBox(pt)
			if bb0.test(bb1, 0.00005): #tolerance here _must_ be less that the cut edge vert snap tolerant
				if showdbg:
					print "EDGE x EDGE at ",pt
				vert = e.cut(pt)
				vert = el.e.cut(pt, vert)
				if not vert in cuts:
					cuts.append(vert)
			#else:
			#	print "**************** ExE fail @ ",pt
		el = el.next
		if el==elend: break

	if len(cuts) > 2:
		print "BUG! edge in face cut more than twice",e.v[0].co,e.v[1].co
		for v in cuts:
			print " \-- cut at ",v.co

	if len(cuts):
		f.markAltered()

	#cut twice - edges crosses completely through face
	if len(cuts) == 2:
		if showdbg:
			print "Edge ",e," crosses completely through face",f, cuts[0].co, cuts[1].co
		e.addFacetLinksBetween(cuts[0], cuts[1],f)

	#if both verts of the edge lie inside the face, add it to the face		
	elif p0_inside and p1_inside:
		if showdbg:
			print "EDGE ",e," LIES COMPLETELY IN FACE"
		e.addFacetLinks(f)
		for ft in e.f:
			ft.f.markAltered()
		
	#cut once => one of the two end verts lie in the face:
	elif len(cuts) == 1:
		if p0_inside and e.v[0] != cuts[0]:
			#print "outside to inside",e
			e.addFacetLinksBetween(e.v[0], cuts[0],f)
		elif p1_inside and e.v[1] != cuts[0]:
			#print "outside to inside2",e
			e.addFacetLinksBetween(cuts[0], e.v[1],f)
		else:
			if cuts[0] not in e.getAllVerts():
				print "BUG: Edge cuts face's edge once, but no other point lines in face"
				print " |-- edge: ",e.v[0].co, e.v[1].co
				print " \-- cut: ",cuts[0].co
			return cuts[0]  #I'm not 100% sure this should be returned
	return False


def IntersectEdgeFace(e,f):
	global showdbg
	global exf, sexf,fexe
	
	if showdbg:
		print "Edge ",e, " vs Facet",f
		print " +-- E: ",e.v[0].co, e.v[1].co, e.cutpoint
		el = f.el
		elend = el
		while True:
			print " +-- Fs: ",el,el.e, el.getNextVert().co
			el = el.next
			if el == elend:
				break
	
	exf+=1
	d0 = DotVecs(e.v[0].co - f.e[0].v[0].co, f.normal)
	d1 = DotVecs(e.v[1].co - f.e[0].v[0].co, f.normal)
	i = 0
	if abs(d0) < 0.00001 and abs(d1) < 0.00001:
		#both points of the edge lie in this face, so need to do ExE testing
		return CoplanarIntersectEdgeFace(e,f)
	elif abs(d0) < 0.00001: #distance of vert from surface
		iv = IntersectVertFace(f,e.v[0].co,e.v[0])
		if iv:
			i = 1
	elif abs(d1) < 0.00001:
		iv = IntersectVertFace(f,e.v[1].co,e.v[1])
		if iv:
			i+= 1

	#Edge lies in face -- actually we won't get here...
	if i == 2:
		#Need to add new EdgeFace Links
		e.addFacetLinks(f)
		return None
		
	#Edge touches faces
	elif i == 1:
		sexf += 1
		return iv

	#Are the verts of either side of the face (different signs)
	elif i == 0 and d0 * d1 < 0:
		#print "maybe?"
		er = e.v[1].co - e.v[0].co #edge ray - maybe precomputed
		d = DotVecs(f.normal, er)
		if abs(d) > 0.000000000001: #avoid divide by zero, and unusably large results
			nd = -d0/d
			if (nd > -0.00000001 and nd < 1.0000001): #Note: relative to length of edge, maybe should be absolute length
				p = e.v[0].co + er * nd
				pt = IntersectVertFace(f,p)
				if pt == True:
					np = e.cut(p)
					if showdbg:
						print "Cut Edge new",p
						print "\- new point: ",np
					xpt.append([0,p])
					return np
				elif pt:
					if showdbg:
						print "Cut edge with ",pt,"at",p
					e.cut(p,pt)
					return pt

def DumbN2FullIntersect(meshA, meshB):
	global showdbg
	global traversalCrumb
	global fxf,ffxf
	if showdbg:
		print "Intersect",meshA,meshB
	for fA in meshA.faces:
		traversalCrumb+=1
		fATrav = traversalCrumb
		for fB in meshB.faces:
			traversalCrumb+=1
			fBTrav = traversalCrumb
			fxf+=1
			#Bound check
			if fA.bb.test(fB.bb):
				ffxf+=1

				for ftA in fA.facets:
					for ftB in fB.facets:
						#facet vs facet
						xpoints = []
						for e in ftB.e:
							xA = IntersectEdgeFace(e,ftA)
							if xA and not xA in xpoints:
								#print "isectA @ ",xA
								xpoints.append(xA)
						#potentially, if two points have already been found, we can skip this loop
						for e in ftA.e:
							xB = IntersectEdgeFace(e,ftB)
							if xB and not xB in xpoints:
								#print "isectB @ ",xB
								xpoints.append(xB)
							
						#exactly two points => new edge
						if len(xpoints) == 2:
							#Does an edge exist already?
							found_edge = False
							for e in xpoints[0].e:
								if e.getOtherVert(xpoints[0]) == xpoints[1]:
									found_edge = True
									#Add edge links if not there already
									found_fa = None
									found_fb = None
									for el in e.f:
										if el.f == ftA:
											found_fa = el
										elif el.f == ftA:
											found_fb = el
									if not found_fa:
										e.addFacetLinks(ftA)
									if not found_fb:
										e.addFacetLinks(ftB)
							if not found_edge:
								
								if showdbg:
									xlen = xpoints[0].co - xpoints[1].co
									print "Make edge", xpoints[0].co, xpoints[1].co,xlen.length
								e = bEdge(xpoints[0], xpoints[1])
								ftA.markAltered()
								ftB.markAltered()
								e.addFacetLinks(ftA)
								e.addFacetLinks(ftB)
							
						#one xpoint means faces touch, but don't intersect
						#over two and something weird happened
						elif len(xpoints) > 2:
							print "BUG:s Weird Facet x Facet"
							for pt in xpoints:
								print "\-- X@ ",pt,pt.co
###################################################################
# Base functions direction the operation                          #
###################################################################


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

	bCookie=bMesh(cookie)
	bCutter=bMesh(cutter,cutter.getMatrix() * cookie.getInverseMatrix())

	DumbN2FullIntersect(bCookie,bCutter)
	
	nm = Mesh.New(newobjname)
	
	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)

	xptdraw(nm)
	nm.mode=bCookie.mesh.mode
	newobj=Blender.Scene.GetCurrent().objects.new(nm, newobjname)
	newobj.layers = cookie.layers
	newobj.setMatrix(cookie.getMatrix())
	cookie.select(1)
	cutter.select(1)
	newobj.select(0)
	return

def Difference(cookie,cutter,newobjname="BoolResult"):
	global showdbg
	global makenewobj

	bCookie=bMesh(cookie)
	bCutter=bMesh(cutter,cutter.getMatrix() * cookie.getInverseMatrix())

	DumbN2FullIntersect(bCookie,bCutter)
	
	nm = Mesh.New(newobjname)
	bCutter.constructFaces(nm,bCookie,1,0,0,1,-1)
	bCookie.constructFaces(nm,bCutter,0,1,0,0,1)

	xptdraw(nm)
	nm.mode=bCookie.mesh.mode
	newobj=Blender.Scene.GetCurrent().objects.new(nm, newobjname)
	newobj.layers = cookie.layers
	newobj.setMatrix(cookie.getMatrix())
	cookie.select(1)
	cutter.select(1)
	newobj.select(0)
	return

def Intersection(cookie,cutter,newobjname="BoolResult"):
	global showdbg
	global makenewobj

	bCookie=bMesh(cookie)
	bCutter=bMesh(cutter,cutter.getMatrix() * cookie.getInverseMatrix())

	DumbN2FullIntersect(bCookie,bCutter)
	
	nm = Mesh.New(newobjname)
	bCutter.constructFaces(nm,bCookie,1,0,1,0)
	bCookie.constructFaces(nm,bCutter,1,0,0,0)
	#bCookie.constructFaces(nm,bCutter,0,1,0,0)

	xptdraw(nm)
	nm.mode=bCookie.mesh.mode
	newobj=Blender.Scene.GetCurrent().objects.new(nm, newobjname)
	newobj.layers = cookie.layers
	newobj.setMatrix(cookie.getMatrix())
	cookie.select(1)
	cutter.select(1)
	newobj.select(0)
	
	return

def Union(cookie,cutter,newobjname="BoolResult"):
	global showdbg
	global makenewobj

	bCookie=bMesh(cookie)
	bCutter=bMesh(cutter,cutter.getMatrix() * cookie.getInverseMatrix())

	DumbN2FullIntersect(bCookie,bCutter)
	
	nm = Mesh.New(newobjname)
	bCutter.constructFaces(nm,bCookie,0,1,1,0)
	bCookie.constructFaces(nm,bCutter,0,1,0,0)

	xptdraw(nm)
	nm.mode=bCookie.mesh.mode
	newobj=Blender.Scene.GetCurrent().objects.new(nm, newobjname)
	newobj.layers = cookie.layers
	newobj.setMatrix(cookie.getMatrix())
	cookie.select(1)
	cutter.select(1)
	newobj.select(0)
	
	return

def DoBool():
	global showdbg
	#Check the sanity of the selection
	objsel=Object.GetSelected()
	meshes=0
	for ob in objsel:
		if ob.getType() == 'Mesh':
			meshes += 1
	if meshes!=2 :
		Blender.Draw.PupMenu("ERROR: Exactly two mesh objects must be selected")
		return
	x=Blender.Draw.PupMenu("MegaBool%t|1: Intersect|2: Union|3: Difference|4: Cookie Cutter")
	#print x
	ts=time()
	Blender.Window.WaitCursor(1)
	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])
	Blender.Window.WaitCursor(0)
	print "Script Execution Time: ",time()-ts

#Try speed boost w/ psycho
if usepsyco:
	if fullpsyco:
		psyco.full()
	else:
		1
#Non coplanar quads
#oA = Object.Get("SqSubCube")
#oB = Object.Get("Cube")

#Edge v face / virtual edge
#oA = Object.Get("02-B.002")
#oB = Object.Get("02-A.002")

#Edge x Edge + vert in face
#oA = Object.Get("02-B.001")
#oB = Object.Get("02-A.001")

#Edge + vert
#oA = Object.Get("Cylinder.003")
#oB = Object.Get("Cylinder.004")

#vert x vert only
#oA = Object.Get("02-B")
#oB = Object.Get("02-A")

#Edge & face intersections
#oA = Object.Get("02-B.003")
#oB = Object.Get("02-A.003")

#Edges in face
#oA = Object.Get("03-B")
#oB = Object.Get("03-A")

#Edges in face & verts fully in face w. tetrahedrons
#oA = Object.Get("03-B.001")
#oB = Object.Get("03-A.001")

#Edges in face & edges in edges
#oA = Object.Get("04-B")
#oB = Object.Get("04-A")

#Edges in face & edges in edges & cross edges
#oA = Object.Get("05-B")
#oB = Object.Get("05-A")

#Weird Angles
#oA = Object.Get("Cube.004")
#oB = Object.Get("Cube")

#Big Meshes
#oA = Object.Get("BigSphereA")
#oB = Object.Get("BigSphereB")

#nonconvex face lies in face
#oA = Object.Get("Cube.016")
#oB = Object.Get("Cube.017")

#nonconvex with full intersections
#oA = Object.Get("Cube.010")
#oB = Object.Get("Cube.008")

#My "classic" test case used to demo problems with existing bools
#oA = Object.Get("Cube.009")
#oB = Object.Get("Cube.006")

#Easy ExF only Tetrahedronds
#oA = Object.Get("Pyramid-A")
#oB = Object.Get("Pyramid-B")

#Legan non-manifold meshes
#oA = Object.Get("Cube.001")
#oB = Object.Get("LegalNonManifold")

#Selection
#objsel = Object.GetSelected()
#oA = objsel[0]
#oB = objsel[1]

#ts=time()

#boA = bMesh(oA)
#boB = bMesh(oB, oB.getMatrix()*oA.getInverseMatrix())
#DumbN2FullIntersect(boA,boB)

#me = Mesh.New("mm")
#boA.constructFaces(me, boB,1,0,1,0)
#boB.constructFaces(me, boA,1,0,0,0)

#xptdraw(me)
#o = Blender.Scene.GetCurrent().objects.new(me, "mm")
#o.setMatrix(oA.getMatrix())
#print "Script Execution Time: ",time()-ts

DoBool()



print "Done. Tests:\n\tFxF",fxf,"\t",ffxf,"\n\tExF",exf,"\t",fexf,"\t",sexf
print "\tVxF",vxf,"\t--\t",svxf,"\n\tExE",exe,"\t",fexe,"\t",sexe,"\n\tVxE",vxe,"\t--\t",svxe,"\n\tVxV",vxv,"\t--\t",svxv
			
if len(messages)>0 and 0:
	txt=Blender.Text.New("Boolean Messages")
	txt.clear()
	txt.write(messages)

Blender.Window.DrawProgressBar(0.0, "Megabool Done")

#Update traversal crumb on exe detection, to avoid multiple exe with the second face?

#For handling vert merges, maybe old should always point to the child