#!BPY

"""
 Name: 'Vector Render'
 Blender: 248
 Group: 'Render'
 Tooltip: 'Vector Output Render for Blender'
"""
__version__ = "0.1"
__author__  = "Alexandros Sigalas (alxarch)"
__license__ = "GPL"
__url__  = "#TODO: wiki page"
__bpydoc__ ="""#TODO: documentation"""

# +---------------------------------------------------------+
# | Copyright (c) 2009 Alexandros Sigalas                   |
# +---------------------------------------------------------+
# | Polygon Renderer for Blender                            |
# +---------------------------------------------------------+
# ***** BEGIN GPL LICENSE BLOCK *****
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software Foundation,
# Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
#
# ***** END GPL LICENCE BLOCK *****

#import rpdb2
#rpdb2.start_embedded_debugger("blender")
try:
	import psyco
	psyco.full()
except:
	#psyco gives a real boost in speed, only for 32bit though... :(
	pass

import sys as S
S.setrecursionlimit(10000)
import Blender as B
from Blender.Mathutils import Vector, DotVecs, ProjectVecs,Intersect, ScaleMatrix, \
								TriangleArea, TriangleNormal, MidpointVecs,LineIntersect, Matrix, AngleBetweenVecs
from Blender.Window import DrawProgressBar as Progress
import BPyMessages
from BPyMesh import meshCalcNormals
from math import *
from  dxfLibrary import *

#######  GLOBALS ###############
global DBG,DBGBOOL,SPLIT_CALLS
DBG = False
DBGBOOL = False
SPLIT_CALLS = 0

global	ONLYSELECTED, SCALE_FACTOR, DO_DXF, DO_SVG, DO_BLEND, LAYERS, LINEW, LINEW_S, UNITS, BSP
ONLYSELECTED = 1
SCALE_FACTOR = 1.0
DO_DXF = 0
DO_SVG = 0
DO_BLEND = 1
LAYERS = 1
LINEW = 0.2
LINEW_S = 0.5
UNITS = "m"
BSP=0

global filename_svg,filename_dxf,bscene_name
filename_svg = ""
filename_dxf = ""
bscene_name = ""

global dxfColors
dxfColors=None

global E,ZEROLENGTH,ZEROAREA, PL_THRES
E = 1E-8
ZEROLENGTH = 1E-4
ZEROAREA = 1E-3
PL_THRES = 6
global d2r
d2r = pi / 180.0

#Classifications for faces, points, polys
global ON,BEHIND,BACKTOUCH,INFRONT,FRONTTOUCH,CROSSING,TCROSSING,IN,OUT,INTOUCH,OUTTOUCH
ON =			0100	# 64

BEHIND = 		0001	# 1
IN =       		0001	# 1

INFRONT = 		0010	# 8
OUT =      		0010	# 8

BACKTOUCH =		0101	# 65
INTOUCH =  		0101    # 65

FRONTTOUCH = 	0110    # 72
OUTTOUCH = 		0110	# 72

CROSSING = 		0011	# 9
TCROSSING = 	0111	# 73
NOCLASS =		0000	# 0

global LEFT, RIGHT
LEFT = 0010
RIGHT = 0001

global  CREASE_ID, COPLANAR_ID, CREASE_ANGLE, DO_CREASE

CREASE_ID = 1 #special creaseID 0 reserved for sections
COPLANAR_ID = 1 #special coplanarID 0 reserved for sections
CREASE_ANGLE = 30.0
DO_CREASE = False

global VIEW_NORMAL, PERSP
#View normal is in camera Space coords, less Z means further away from camera
#all z infront of camera is Negative !!!
VIEW_NORMAL = Vector(0.0,0.0,-1.0)
NORMAL_2D = Vector(0.0,0.0,1.0)
PERSP = False

#default materials
MATERIAL=None
SECTION_MATERIAL=None

#### OBJECT UTILS ##############################
def dupTest(object):
	"""
	Checks objects for duplicates enabled (any type)
	object: Blender Object.
	Returns: Boolean - True if object has any kind of duplicates enabled.
	"""
	if (object.enableDupFrames or \
		object.enableDupGroup or \
		object.enableDupVerts):
		return True
	else:
		return False

def getObjectsAndDuplis(oblist,MATRICES=False,HACK=False):
	"""
	Return a list of real objects and duplicates and optionally their matrices
	oblist: List of Blender Objects
	MATRICES: Boolean - Check to also get the objects matrices default=False
	HACK: Boolean - See note default=False
	Returns: List of objects or
			 List of tuples of the form:(ob,matrix) if MATRICES is set to True
	NOTE: There is an ugly hack here that excludes all objects whose name
	starts with "dpl_" to exclude objects that are parented to a duplicating
	object, User must name objects properly if hack is used.
	"""
	supported_types = ["Mesh","Surf","Curve","Text","Meta"]
	result = []
	for ob in oblist:
		type = ob.type
		if not type in supported_types:
			continue
		if dupTest(ob):
			dup_obs=ob.DupObjects
			if len(dup_obs):
				for dup_ob, dup_mx in dup_obs:
					if MATRICES:
						result.append((dup_ob,dup_mx))
					else:
						result.append(dup_ob)
		else:
			if HACK:
				if ob.getName()[0:4] != "dpl_":
					if MATRICES:
						mx = ob.mat.copy()
						result.append((ob,mx))
					else:
						result.append(ob)
			else:
				if MATRICES:
					mx = ob.mat.copy()
					result.append((ob,mx))
				else:
					result.append(ob)
	return result

#def getCameras(sce):
	#active = sce.objects.camera.name
	#cams = [ob.name for ob in sce.objects if ob.type=="Camera"]
	#cams.sort(key= lambda x: (x!=active))
	#return cams

### GUI #############################

def vRender_ui(filepath):
	global	ONLYSELECTED,\
	SCALE_FACTOR,\
	PL_THRES,\
	DO_DXF,\
	DO_SVG,\
	DO_BLEND,\
	LAYERS,\
	LINEW,\
	LINEW_S,\
	UNITS,\
	BSP
	# Dont overwrite
	if not BPyMessages.Warning_SaveOver(filepath):
		print 'Aborted by user: nothing exported'
		return

	#test():return
	#cams = getCameras(sce)
	#camsMenu = "Select Camera %t"
	#for i,cam in enumerate(cams):
		#camsMenu += "|"cam+" %x"+str(i)

	PREF_ONLYSELECTED= B.Draw.Create(ONLYSELECTED)
	PREF_SCALE_FACTOR= B.Draw.Create(SCALE_FACTOR)
	#PREF_CAMERA = B.Draw.Menu(camsMenu, 2, 0, 0, 120, 40, 0, "Select Camera")

	PREF_PL_THRES = B.Draw.Create(6)

	PREF_LAYERS = B.Draw.Create(LAYERS)
	PREF_LINEW = B.Draw.Create(LINEW)
	PREF_LINEW_S = B.Draw.Create(LINEW_S)
	PREF_BSP = B.Draw.Create(BSP)
	PREF_DO_SVG = B.Draw.Create(DO_SVG)
	PREF_DO_DXF = B.Draw.Create(DO_DXF)
	PREF_DO_BLEND = B.Draw.Create(DO_BLEND)
	PREF_BLENDNAME = B.Draw.Create("Drawing")
	PREF_UNITS = B.Draw.Create(UNITS)
	#PREF_HELP= B.Draw.Create(0)
	block = [\
	("Options:"),\
	("Scale:", PREF_SCALE_FACTOR, 0.0001, 100, "Scale factor for output drawing (i.e. 1:100 =  0.01)"),\
	("Selected Only", PREF_ONLYSELECTED, "export only selected objects"),\
	("Separate layers", PREF_LAYERS, "separate layers by Material"),\
	("co-Planar Threshold", PREF_PL_THRES, 4, 8, "set threshold for coplanar faces merging (less = less strict)"),\
	("BSP Sorting", PREF_BSP, "sort polygons in a bsp tree, might improve or degrade speed"),\
	("Normal LineW:", PREF_LINEW, 0.01 , 10.00, "lineweight for non-cut geometry(mm)"), \
	("Section LineW:", PREF_LINEW_S, 0.01, 10.00, "select lineweight for cut geometry (mm)"), \
	("Export To:"),
	("Blender Scene", PREF_DO_BLEND, "create a new blender scene with output"),\
	("Scene Name:", PREF_BLENDNAME, 0, 20, "type in name for the new BlenderScene"),\
	(''),\
	("export DXF", PREF_DO_DXF,"export dxf file"),\
	("export SVG",PREF_DO_SVG, "export svg file"),\
	("Blender Units: ",PREF_UNITS, 0, 5,"valid options are km, m ,cm, mm, inch (set for proper svg output scaling)"),\
	("(km, m ,cm, mm, inch)")\
	]
	#(''),\
	#("online Help", PREF_HELP, "calls Manual Page on Wiki.Blender.org"),\


	if not B.Draw.PupBlock("vRender %s" %__version__[:10], block): return

	#if PREF_HELP.val!=0:
		#try:
			#import webbrowser
			#webbrowser.open('http://wiki.blender.org/index.php?title=Scripts/Manual/Export/autodesk_dxf')
		#except:
			#B.Draw.PupMenu('DXF Exporter: %t|no connection to manual-page on Blender-Wiki!	try:|\
#http://wiki.blender.org/index.php?title=Scripts/Manual/Export/autodesk_dxf')
		#return

	ONLYSELECTED = PREF_ONLYSELECTED.val
	SCALE_FACTOR = PREF_SCALE_FACTOR.val
	PL_THRES = 1.0 - float('5E-'+str(PREF_PL_THRES.val))
	LAYERS = PREF_PL_THRES.val
	LINEW = PREF_LINEW.val
	LINEW_S = PREF_LINEW_S.val
	UNITS = PREF_UNITS.val.lower()
	if not UNITS in Drawing.Units:
		print "Abort: unsupported units entered"
		B.Draw.PupMenu('vRender: valid values for units are: km, m ,cm, mm, inch')

	DO_DXF = PREF_DO_DXF.val
	if DO_DXF:
		global filename_dxf
		filename_dxf = B.sys.makename(path=filepath, ext='.dxf')
	DO_SVG = PREF_DO_SVG.val
	if DO_SVG:
		global filename_svg
		filename_svg = B.sys.makename(path=filepath, ext='.svg')
	DO_BLEND = PREF_DO_BLEND.val
	if DO_BLEND:
		global bscene_name
		bscene_name = filepath
	BSP = PREF_BSP.val
	sce = B.Scene.getCurrent()

	if ONLYSELECTED: sel_group = sce.objects.selected
	else: sel_group = sce.objects
	export_list = getObjectsAndDuplis(sel_group,MATRICES=True)

	if not export_list:
		print "Abort: selection was empty, no object to export!"
		B.Draw.PupMenu('vRender: nothing rendered!| selection was empty!')
	elif not (DO_SVG or DO_DXF or DO_BLEND):
		print "Abort: no output selected!"
		B.Draw.PupMenu('vRender: select at least one output!')
	else:
		cam = sce.objects.camera
		B.Window.WaitCursor(1)
		dwg = doRender(sce, cam, export_list)
		B.Window.WaitCursor(0)
		if LAYERS:
			dwg.makeLayers("byMaterial")
		else:
			dwg.makeLayers()

		if DO_SVG:
			dwg.exportSVG(filename_svg)
		if DO_DXF:
			dwg.exportDXF(filename_dxf)
		if DO_BLEND:
			bscene_name = PREF_BLENDNAME.val
			dwg.exportBLENDER(bscene_name)

###### MathUtils ################

def col2RGB(color):
	return [int(floor(255*color[0])),
			int(floor(255*color[1])),
			int(floor(255*color[2]))]

def col2DXF(rgbcolor):
	global dxfColors
	if dxfColors is None:
		from dxfColorMap import color_map
		dxfColors = [(tuple(color),idx) for idx, color in color_map.iteritems()]
		dxfColors.sort()
	entry = (tuple(rgbcolor), -1)
	dxfColors.append(entry)
	dxfColors.sort()
	i = dxfColors.index(entry)
	dxfColors.pop(i)
	return dxfColors[i][1]

def roundvec(v,i):
	try:
		return Vector(round(v[0],i), round(v[1],i), round(v[2],i))
	except IndexError:
		return Vector(round(v[0],i), round(v[1],i))

def rayHit(p, pp, pno, direction=VIEW_NORMAL):
	w = p - pp

	D = DotVecs(pno, direction)
	N = -DotVecs(pno, w)
	if abs(D) < E/100:
		if abs(N) < E/100:
			return p.copy()
		else:
			return None

	ratio = N / D
	return p + ratio * direction

def fixMesh(me,ob):
	for f in me.faces:
		f.sel = 1
	ob.link(me)
	me.quadToTriangle(0)
	#me.recalcNormals(0) # behaves strangely in planar meshes

def drawPlane(pp,pno):
	sce = B.Scene.getCurrent()
	ob = B.Object.New('Mesh', 'plane')
	me = B.Mesh.Primitives.Plane()
	ob.link(me)
	rx = AngleBetweenVecs(pno, Vector(1.0,0.0,0.0))
	ry = AngleBetweenVecs(pno, Vector(0.0,1.0,0.0))
	rz = AngleBetweenVecs(pno, Vector(1.0,0.0,1.0))
	ob.setEuler([rx,ry,rz])
	ob.setLocation(pp)
	sce.objects.link(ob)

def perp(p0,p1):
	p =  (p0[0] * p1[1]) - (p0[1] * p1[0])
	return p

def isLeft(p,lp0,lp1,EPSILON=0.0):

	t = (lp1[0] - lp0[0]) * (p[1] - lp0[1]) - \
		(p[0] - lp0[0]) * (lp1[1] - lp0[1])
	if t < -EPSILON:
		return RIGHT
	elif t > EPSILON:
		return LEFT
	else:
		return ON

def inSegment(p,s0,s1,D=0.0):
	if abs(s0.x - s1.x) > abs(s0.y - s1.y):
		#not vertical line
		if s0.x + D < p.x and p.x < s1.x - D:
			return True
		if s0.x - D > p.x and p.x > s1.x + D:
			return True
	else:
		if s0.y + D < p.y and p.y < s1.y - D:
			return True
		if s0.y - D > p.y and p.y > s1.y + D:
			return True
	return False

def same3D(p1,p2,EPSILON=ZEROLENGTH):
	return p1 == p2 or (p1-p2).length < EPSILON

def same2D(p1,p2,EPSILON=ZEROLENGTH):
	return p1 == p2 or (abs(p1[0] - p2[0]) < EPSILON and\
						abs(p1[1] - p2[1]) < EPSILON)

def relPointPlane(p,pp,pno):
	d = DotVecs(p - pp,pno)
	if d > ZEROLENGTH:
		return INFRONT
	elif d < -ZEROLENGTH:
		return BEHIND
	else:
		return ON

def LineIntersectPlane(p1,p2,pp,pno):
	u = p2 - p1
	w = p1 - pp
	D = DotVecs(pno,u)
	N = -DotVecs(pno,w)
	if abs(D) < E:
		if abs(N) == 0.0:
			#segment lies on the plane
			return p1.copy()
		else:
			#line parallel to plane
			return None

	ratio = N / D
	if ratio < -E or ratio > 1+E:
		return None
	else:
		return p1 + ratio * u

def perspectize(co):
	#convert to screen space coords
	# TODO: check to see if needs scale up for booleans to work properly
	return 10 * Vector([-co[0] / (co[2] + E), -co[1] / (co[2] + E), 1.0])

###### MeshUtils ################################

def polyFromFace(f,IDProps=dict()):
	verts = [v.co.copy() for v in f.verts]
	result = Poly(verts, IDProps=IDProps)
	result.simplify2D()
	if len(result.verts) < 3:
		return None
	if not DotVecs(result.normal,VIEW_NORMAL) < -E:
		result.attr |= BACKF

	if result.selfIntersecting():
		result.drawBlender('slf-isect-%i'%(f.index))
		raise ValueError("wrong conversion")
	return result

def mesh2Polys(me, mats=[]):
	global DO_CREASE, CREASE_ANGLE, PL_THRES
	meshCalcNormals(me)
	#me.calcNormals()

	try:
		faceNeighbours = face_edges(me)
	except:
		from BPyMesh import face_edges
		faceNeighbours = face_edges(me)

	if DO_CREASE :
		creases = getIslands(me,faceNeighbours, MODE='crease', TEST=CREASE_ANGLE, MAT=True)
	islands = getIslands(me,faceNeighbours, MODE='planarPL', TEST=PL_THRES, MAT=True)
	print "islands found: ",len(islands)

	polys = list()
	for edges, ff, copID in islands:

		if DO_CREASE:
			#all planar polys belong to the same crease
			#TODO: UI - set proper limits for values ANGLE 1.0 - 89.0, PL_THRES 5 - 10 ( and convert to 1.0 - float('5e-%iE'%(PL_THRES))  )
			crsID = creases[ff]
		else:
			crsID = 0
		IDProps = dict(coplanar=copID, crease=crsID)
		try:
			material = mats[ff.mat] #map face index to vRender material
		except IndexError:
			material = MATERIAL
		loops = list()
		while edges:
			loop_grows = True
			loop = list(edges.pop())
			while edges and loop_grows:
				loop_grows = False
				loopFirst = loop[0]
				loopLast = loop[-1]
				for e in edges:
					loop_grows = False
					edgeFirst = e[0]
					edgeLast = e[1]
					if loopFirst == edgeFirst:
						loop.insert(0,edgeLast)
						loop_grows = True

					elif loopLast == edgeFirst:
						loop.append(edgeLast)
						loop_grows = True

					elif loopFirst == edgeLast:
						loop.insert(0,edgeFirst)
						loop_grows = True

					elif loopLast == edgeLast:
						loop.append(edgeFirst)
						loop_grows = True

					if loop_grows:
						edges.remove(e)
						break

			if len(loop) > 3:
				loop.pop()
				pl = Poly([me.verts[i].co.copy() for i in loop], IDProps=IDProps)
				if pl.simplify3D() > 2:
					if DotVecs(ff.no,VIEW_NORMAL) > -E :
						pl.attr |= BACKF
						#pl.flatten3D()
					pl.material = material
					loops.append(pl)
		if loops:
			loops = [(loop.getArea2D(),loop) for loop in loops]
			loops.sort()
			loops = [loop for _,loop in loops]
			base = loops.pop()
			if not base.order:
				#TODO: on backfaces this will become an issue, needs seperate parsing for backfaces - frontfaces
				base.reverse()
			base.holes = loops[:]
			for hole in base.holes:
				hole.attr |= HOLE
				if hole.order:
					hole.reverse()
			polys.append(base)

	return polys

def getIslands(me, faceNeighbours=None, MODE=None, TEST=E, MAT=True):
	'''mode can be "planarF", "planarE", "crease", None ,"planarPL"'''

	PLANAR = FACES = EDGES = CREASE = POLYGONS = False
	if MODE is None:
		PLANAR = True
	elif MODE == 'planarE':
		PLANAR = True
		EDGES = True
	elif MODE == 'crease':
		CREASE = True
	elif MODE == 'planarF':
		PLANAR = True
		FACES = True
	elif MODE == 'planarPL':
		PLANAR = True
		EDGES = True
		POLYGONS = True

	if MAT:
		faceMats = [f.mat for f in me.faces]
	faceNormals = [f.no for f in me.faces]
	fIndices = range(len(me.faces))

	if faceNeighbours is None:
		try:
			faceNeighbours = face_edges(me)
		except:
			from BpyMesh import face_edges
			faceNeighbours = face_edges(me)

	if CREASE:
		global CREASE_ID
		islands = [None for i in fIndices]
	else:
		global COPLANAR_ID
		islands= list()

	times_used= [0 for i in fIndices]

	while True:
		new_island= False
		for i, times in enumerate(times_used):
			if  times == 0:
				island = [i]
				if EDGES:
					edges = set(me.faces[i].edge_keys)
				new_island = True
				times_used[i] = 1
				break

		if not new_island:
			break

		island_growing = True
		while island_growing:
			island_growing = False

			for fIndexA in island[:]:
				if times_used[fIndexA]==1:
					times_used[fIndexA] += 1

					fNormalA = faceNormals[fIndexA]
					if MAT: fMatIdxA = faceMats[fIndexA]
					for edgeFaces in faceNeighbours[fIndexA]:
						for fB in edgeFaces:
							fIndexB = fB.index
							if fIndexA != fIndexB and times_used[fIndexB] == 0:
								island_growing = True
								fNormalB = faceNormals[fIndexB]
								if MAT: fMatIdxB = faceMats[fIndexB]
								if (not MAT or fMatIdxA == fMatIdxB) and \
								   ((PLANAR and DotVecs(fNormalA,fNormalB) > TEST) or \
								    (CREASE and AngleBetweenVecs(fNormalA,fNormalB) < TEST)):
									times_used[fIndexB] = 1
									island.append(fIndexB)
									if EDGES:
										edges = edges.symmetric_difference(fB.edge_keys)

		if POLYGONS:
			islands.append((edges, me.faces[island[0]], COPLANAR_ID))
			COPLANAR_ID += 1
		elif EDGES:
			islands.append(edges)
		elif CREASE:
			for idx in island:
				islands[idx] = CREASE_ID
			CREASE_ID += 1
		elif FACES:
			islands.append(me.faces[idx] for idx in island)
		else:
			islands.append(island)

	return islands

def makeSection(xedges, singleVerts, material):
	'''
	Finds the section polys, hard to explain

	'''
	openloops = list()
	closedloops = list()
	while xedges:
		loop_grows = True
		loop = xedges.pop()
		while xedges and loop_grows:
			loop_grows = False
			loopFirst = loop[0]
			loopLast = loop[-1]
			for e in xedges:
				loop_grows = False
				edgeFirst = e[0]
				edgeLast = e[1]
				if loopFirst is edgeFirst:
					loop.insert(0,edgeLast)
					loop_grows = True

				elif loopLast is edgeFirst:
					loop.append(edgeLast)
					loop_grows = True

				elif loopFirst is edgeLast:
					loop.insert(0,edgeFirst)
					loop_grows = True

				elif loopLast is edgeLast:
					loop.append(edgeFirst)
					loop_grows = True

				if loop_grows:
					xedges.remove(e)
					break

		loop.pop()
		if len(loop) > 2:
			open = False
			for p in loop:
				if p in singleVerts:
					open = True
					break

			pl = Poly([co for co in loop])
			if pl.simplify2D() > 2:
				if open:
					openloops.append(pl)
				else:
					closedloops.append(pl)

	bases = list()

	if closedloops:
		bases.append(closedloops.pop())
		for i,base in enumerate(bases):
			while closedloops:
				pl = closedloops.pop()
				G = BooleanGraph(pl,base)
				A,B = G.classifications()

				if B is OUT and A is IN:
					base.holes.append(pl)

				elif B is IN and A is OUT:
					pl.holes.append(base)
					bases.remove(base)
					bases.append(pl)
					break

				elif B is OUT and A is OUT:
					bases.append(pl)

				elif B is INTOUCH and A is OUTTOUCH:
					tmp,_ = G.doSubtractBA()
					base = tmp[0]

				elif B is OUTTOUCH and A is INTOUCH:
					tmp,_ = G.doSubtractAB()
					base = tmp[0]

				else:
					tmp,holes = G.doUnion()
					base = tmp[0]
					base.holes = holes

			bases[i] = base

	for base in bases:
		base.attr |= SECTION
		base.IDProps = dict(coplanar = 0, crease = 0)
		base.material = material
		if not base.order:
			base.reverse()

		for hole in base.holes:
			hole.attr|= HOLE|SECTION
			hole.material = material #not sure it is needed...
			if hole.order:
				hole.reverse()

	return bases, openloops

def clipMeshPlane(me,pp,pno):
	'''
	clips a mesh on a plane (in place)
	me: the mesh the face belongs to
	pp: Vector - a point on the plane
	pno: Vector - the plane's normal

	Returns: a list of vertex pairs that form the edges on the plane
	     and a list of vertices that are endpoints of non-closed loops
		(this data is needed to cap the holes if needed)

	'''
	#t = time()
	clipped = False
	f2Del = list()
	f2Add = list()
	v2Add = list()
	xedges = list()
	singleVerts = list()
	#maps edge indices to coordinates to skip re-computation
	#and discarding of intersection coordinates
	emap = {}
	rmap = [relPointPlane(v.co,pp,pno) for v in me.verts]
	offset = len(me.verts)
	for f in me.faces:
		R = 0000
		for v in f.verts:
			R |= rmap[v.index]

		if R == INFRONT or R == FRONTTOUCH:
			pass
		elif R == BEHIND or R == BACKTOUCH or R == ON:
			f2Del.append(f.index)
		else:
			f2Del.append(f.index)
			newFaces = list()
			edge = list()

			for i,vx1 in enumerate(f.verts):
				r1 = rmap[vx1.index]
				try:
					vx2 = f.verts[i+1]
				except:
					vx2 = f.verts[0]
				r2 = rmap[vx2.index]

				if r1 == INFRONT:
					newFaces.append(vx1.index)

				if r1 != r2:
					if not clipped:
						clipped = True
					key = tuple(sorted([vx1.index,vx2.index]))
					#check to see if we have already computed the intersection
					if key not in emap:
						I = LineIntersectPlane(vx1.co,vx2.co,pp,pno)
						singleVerts.append(I)
						newFaces.append(offset+len(v2Add))
						v2Add.append(I)
						emap[key] = I
					else:
						I = emap[key]
						singleVerts.remove(I)
						newFaces.append(offset+v2Add.index(I))

					edge.append(I)

			xedges.append(edge)

			L = len(newFaces)
			if L > 4:
				fList = [newFaces[i:i+4] for i in xrange(0, L , 3) if i + 4 < L]
				fList += [[newFaces[0]] + newFaces[i:]]
				f2Add.append((fList,f.mat))

			else:
				f2Add.append(([newFaces],f.mat))

	if clipped:
		if v2Add: me.verts.extend(v2Add)
		for faces, mat in f2Add:
			nFaces = me.faces.extend(faces,indexList=True)
			for i in nFaces:
				me.faces[i].mat = mat
		if f2Del: me.faces.delete(1,f2Del)

	return xedges, singleVerts

def doCull(cull_me, me, proxy, mats):
	global DO_CREASE, CREASE_ANGLE
	me_bounds = Bounds(me.verts)

	cull_bounds = Bounds(cull_me.verts)
	if not cull_bounds.intersect3D(me_bounds):
		return [], [], []

	xedges = list()
	singleVerts = list()
	cullFaces = [f for f in cull_me.faces]
	f = cullFaces.pop()
	pp = f.verts[0].co
	pno = f.no

	xedges, singleVerts = clipMeshPlane(me,pp,pno)

	sectionmat = SECTION_MATERIAL
	for mt in mats:
		if not mt is None:
			sectionmat = mt.section
			break

	sectionPolys, sectionLines = makeSection(xedges, singleVerts, sectionmat)

	for f in cullFaces:
		pp = f.verts[0].co
		pno = f.no
		clipMeshPlane(me,pp,pno)
		#if DBG: print "faces left after clip:",len(me.faces)
		tmp = list()
		for section in sectionPolys:
			tmp.extend(section.split2Plane(pp,pno))
		sectionPolys = tmp

	fixMesh(me,proxy)
	#if DBG:print "faces left after fix:",len(me.faces)
	#f2del = [f.index for f in me.faces if abs(DotVecs(f.no,VIEW_NORMAL)) < 5E-3]
	#if f2del: me.faces.delete(1,f2del)
	#if DBG: print "faces left after backfacecull:",len(me.faces)
	facelist = mesh2Polys(me, mats)

	return facelist, sectionPolys, sectionLines

########## Material parsing ###############################
#-------------------------------------------------
# getMaterials(obj)
# helper function to get the material list of an object in respect of obj.colbits
# (ripped off luxblend)
#-------------------------------------------------
def getMaterials(obj, compress=False):
    mats = [None]*16
    colbits = obj.colbits
    objMats = obj.getMaterials(1)
    data = obj.getData(mesh=1)
    try:
        dataMats = data.materials
    except:
        try:
            dataMats = data.getMaterials(1)
        except:
            dataMats = []
            colbits = 0xffff
    m = max(len(objMats), len(dataMats))
    if m>0:
        objMats.extend([None]*16)
        dataMats.extend([None]*16)
        for i in range(m):
            if (colbits & (1<<i) > 0):
                mats[i] = objMats[i]
            else:
                mats[i] = dataMats[i]
        if compress:
            mats = [m for m in mats if m]
    else:
        print "Warning: object %s has no material assigned"%(obj.getName())
        mats = []
    ## clay option
    #if luxProp(Scene.GetCurrent(), "clay", "false").get()=="true":
        #if clayMat==None: clayMat = Material.New("lux_clayMat")
        #for i in range(len(mats)):
            #if mats[i]:
                #mattype = luxProp(mats[i], "type", "").get()
                #if (mattype not in ["portal","light","boundvolume"]): mats[i] = clayMat
    return mats

def convertMat(mat):
	#TODO: need proper materials editor for this to work nicely
	mname = mat.name
	fillCo = [mat.R,mat.G,mat.B]
	lineCo = Material.defLineColor
	lineW = Material.defLineWgt
	attr = 0000
	alpha = None
	if mat.getMode() & B.Material.Modes['ZTRANSP']:
		alpha = mat.getAlpha()
	section = SECTION_MATERIAL
	return Material(mname, fillCo, lineCo, lineW, alpha=alpha, section=section, type=Material.mTypes['normal'])

def makeMaterialsTable(oblist):
	materials = dict()
	for ob in oblist:
		tmp = getMaterials(ob,True)
		if not tmp:
			#object has no materials
			if not "Default" in materials:
				materials["Default"] = MATERIAL
		for mat in tmp:
			mname = mat.getName()
			if mname not in materials:
				materials[mname] = convertMat(mat)
	return materials

######### MAIN RENDER FUNCtioNS ###############################

def vRender(facelist,sections):
	#TODO: persp transform new way
	t = B.sys.time()
	print "Renderer, Polygons to render: %i"%(len(facelist))
	## clippers hunt #############################
	prText = "sorting..."
	Progress(0.0,prText)
	print prText
	total = len(facelist)
	clipers = [list() for i in xrange(total)]
	global PERSP
	if PERSP:
		screenSections = [mclip.toPerspective() for mclip in sections]
		screenlist = [pl.toPerspective() for pl in facelist]
	else:
		screenlist = [pl.copy() for pl in facelist]
		screenSections = [mclip.copy() for mclip in sections]
		[pl.flatten() for pl in screenlist]
		[pl.flatten() for pl in screenSections]
	#screenlist = [pl.convert2Screen(scalefactor) for pl in facelist]
	#screenSections = [mclip.convert2Screen(scalefactor) for mclip in sections]
	total = float(total)
	for i,pl in enumerate(facelist):
		if screenlist[i].attr&BACKF:
			continue
		Progress(i/total,prText)
		for j in xrange(len(sections)):
			if not screenlist[i].bounds.disjoint2D(screenSections[j].bounds):
				clipers[i].append(screenSections[j])

		for j,candidate in enumerate(facelist):
			if pl is candidate or \
			   screenlist[j].attr&BACKF or\
			   pl.IDProps['coplanar'] == candidate.IDProps['coplanar'] or\
			   screenlist[i].bounds.disjoint2D(screenlist[j].bounds):
				continue

			if not candidate.material is None and\
			   not candidate.material.alpha is None and\
			   not candidate.material is pl.material:
				   #special "speed" mode for detailed objects that need not affect backgroung polys
				   # i.e. drain pipes
				   continue

			clip = list()
			if pl.bounds.zmin > candidate.bounds.zmax:
				if DBG: print "Infront from z bounds"
				continue
			if pl.bounds.zmax < candidate.bounds.zmin:
				if DBG: print "Behind from z bounds"
				clip.append(screenlist[j])
			else:
				r,rmap = pl.rel2Poly3D(candidate)
				if r == BEHIND or r == BACKTOUCH:
					if DBG: print "Behind from  rel"
					clip.append(screenlist[j])
				elif r == ON or r == INFRONT or r == FRONTTOUCH:
					if DBG: print "INFRONT from  rel"
					continue
				else:
					r,rmap = candidate.rel2Poly3D(pl)
					if r == BEHIND or r == BACKTOUCH or r == ON:
						if DBG: print "candidate Behind from  rel"
						continue
					elif r == INFRONT or r == FRONTTOUCH:
						if DBG: print "candidate infront from  rel"
						clip.append(screenlist[j])
					else:
						if DBG: print "splittin"
						clip = candidate.split2Plane(pl.verts[0].co, pl.normal, rmap)
						if DBG: print "found %i clips"%(len(clip))

						if PERSP:
							clip = [c.toPerspective() for c in clip]
							clip = [c for c in clip if not c.attr&BACKF]
						else:
							[c.flatten() for c in clip]
						#smallArea = candidate.area2D*1E-6
						#clip = [c for c in clip if not c.attr&BACKF and c.simplify2D(smallArea) > 2]
			clipers[i].extend(clip)
	Progress(1.0,prText)
	prText = "cliping..."
	print prText
	Progress(0.0,prText)
	dwg = list()
	for i,pl in enumerate(screenlist):
		if pl.attr&BACKF:
			continue
		if not clipers[i]:
			if DBG: print 'dbg: poly has no clipers'
			dwg.append(pl)
			continue
		Progress(i/total, prText)
		#print "Poly has %i clippers" % len(clipers[pl.ID])
		visParts = [pl]
		#clips = doUnion(clipers[i])
		clips = clipers[i]
		if DBG: print 'dbg: poly has %i clipers'%(len(clips))
		for clip in clips:
			if visParts:
				visParts = doClip(clip,visParts)
			else:
				break

		for part in visParts:
			part.attr = pl.attr
			part.IDProps = pl.IDProps
			part.material = pl.material

		dwg.extend(visParts)
	Progress(1.0,prText)
	dwg.extend(screenSections)
	print 'Normal render method took %.2fsec'%(B.sys.time()-t)
	return dwg

def doClip(cliper,subjects):
	subj = subjects.pop()
	result = cliper.clipPoly(subj)

	if subjects:
		# !!!! RECURSION!!!!!
		result.extend(doClip(cliper,subjects))

	return result

def doUnion(subjects):
	#subjects.sort(key = lambda x:(x.bounds.area2D), reverse=True)
	result = list()
	while subjects:
		base = subjects.pop(0)
		growing = True
		while growing:
			growing = False
			for i,pl in enumerate(subjects):
				if pl is None: continue
				tmp = base.union(pl)
				if tmp is None:
					pass
				else:
					base = tmp
					growing = True
					subjects[i] = None
			if growing:
				subjects = [subj for subj in subjects if not subj is None]
		result.append(base)

	return result


def doRender (sce, cam, oblist):
	global MATERIAL, SECTION_MATERIAL
	SECTION_MATERIAL = Material("Default-section", type=Material.mTypes['section'])
	MATERIAL = Material("Default", section=SECTION_MATERIAL)
	materials = makeMaterialsTable([ob for ob,_ in oblist])
	cam_mx = cam.getInverseMatrix()
	camData = cam.getData()
	width, height, frstm_me = frustumMesh(camData)

	facelist = list()
	sectionPolys = list()
	sectionLines = list()
	proxy = B.Object.New('Mesh','proxy')
	sce.objects.link(proxy)

	for ob,ob_mx in oblist:
		tmp_me = B.Mesh.New('tmp')
		tmp_me.getFromObject(ob)
		mx = ob_mx * cam_mx
		tmp_me.transform(mx)
		tmp_me.update()
		if len(tmp_me.verts) == 0:
			continue
		mats = getMaterials(ob)
		if mats:
			for i,mat in enumerate(mats):
				if not mat is None:
					mats[i] = materials[mat.getName()]
		else:
			#object has no materials use default
			mats=[MATERIAL]

		tmp, sPolys, sLines = doCull(frstm_me, tmp_me, proxy, mats)

		facelist.extend(tmp)
		sectionPolys.extend(sPolys)
		sectionLines.extend(sLines)

	sce.objects.unlink(proxy)
	print "going to render.."
	#exclude polys vertical to camera
	facelist = [pl for pl in facelist if abs(DotVecs(pl.normal,VIEW_NORMAL))  > 7E-3]
	if BSP:
		dwg = vRenderBSP(facelist,sectionPolys)
	else:
		dwg = vRender(facelist,sectionPolys)

	return Drawing(dwg, materials, SCALE_FACTOR, width, height, UNITS)


	#if DO_CREASE:
		#crease_islands = [list() for i in xrange(CREASE_ID)]
		#section_island = list()
		#for pl in dwg:
			#crsID = pl.IDProps['crease']
			#if crsID == 0:
				#section_island.append(pl)
			#else:
				#crease_islands[crsID].append(pl)
		#result = list()
		#for island in crease_islands:
			#result.extend(doUnion(island))

		#result.extend(section_island)
		#dwg = result




def frustumMesh(camData):

	sce = B.Scene.GetCurrent()
	context = sce.getRenderingContext()
	#print 'deb: context=\n', context #------------------
	#print 'deb: context=\n', dir(context) #------------------
	sizeX = context.sizeX
	sizeY = context.sizeY
	ratioXY = sizeX/float(sizeY)
	#print 'deb: size X,Y, ratio=', sizeX, sizeY, ratioXY #------------------

	near_Z = - camData.clipStart
	far_Z = - camData.clipEnd
	#print 'deb: clip Start=', camData.clipStart #------------------
	#print 'deb: clip   End=', camData.clipEnd #------------------
	global PERSP
	if camData.type=='ortho':
		PERSP = False
		scale = camData.scale
		#print 'deb: camscale=', scale #------------------
		nearShiftX = farShiftX = camData.shiftX * scale
		nearShiftY = farShiftY = camData.shiftY * scale
		near_X = scale * 0.5
		near_Y = scale * 0.5
		if ratioXY > 1.0: near_Y /= ratioXY
		else: near_X *= ratioXY
		far_X = near_X
		far_Y = near_Y


	elif camData.type=='persp':
		PERSP = True
		#viewpoint = [0.0, 0.0, 0.0] #camData's coordinate system, hehe
		#lens = camData.lens
		angle = camData.angle
		#print 'deb: cam angle=', angle #------------------
		shiftX = camData.shiftX
		shiftY = camData.shiftY
		fov_coef = atan(angle * d2r)
		fov_coef *= 1.3  #incl. passpartou
		near_k = near_Z * fov_coef
		far_k = far_Z * fov_coef
		nearShiftX = -(camData.shiftX * near_k)
		farShiftX = -(camData.shiftX * far_k)
		nearShiftY = -(camData.shiftY * near_k)
		farShiftY = -(camData.shiftY * far_k)
		near_X = near_Y = near_k * 0.5
		far_X = far_Y = far_k * 0.5
		if ratioXY > 1.0:
			near_Y /= ratioXY
			far_Y /= ratioXY
		else:

			near_X *= ratioXY
			far_X *= ratioXY

	nearXmin = -near_X + nearShiftX
	nearXmax = near_X + nearShiftX
	nearYmin = -near_Y + nearShiftY
	nearYmax = near_Y + nearShiftY
	farXmin = -far_X + farShiftX
	farXmax = far_X + farShiftX
	farYmin = -far_Y + farShiftY
	farYmax = far_Y + farShiftY


	verts = []
	verts.append([nearXmin, nearYmin, near_Z])
	verts.append([nearXmax, nearYmin, near_Z])
	verts.append([nearXmax, nearYmax, near_Z])
	verts.append([nearXmin, nearYmax, near_Z])

	verts.append([farXmin, farYmin, far_Z])
	verts.append([farXmax, farYmin, far_Z])
	verts.append([farXmax, farYmax, far_Z])
	verts.append([farXmin, farYmax, far_Z])

	# !!! LAST FACE SHOULD BE CEAR CLIP PLANE
	if camData.type == 'persp':
		faces = [[4,5,6,7],[0,1,5,4],[1,2,6,5],[2,3,7,6],[0,4,7,3],[0,3,2,1]]
	else:
		faces = [[4,5,6,7],[0,3,2,1]]
	nme = B.Mesh.New()
	nme.verts.extend(verts)
	nme.faces.extend(faces)
	if PERSP:
		width = 2.0*abs(farXmax/far_Z)
		height = 2.0*abs(farYmax/far_Z)
	else:
		width = 2.0*abs(nearXmax)
		height = 2.0*abs(nearYmax)
	#test
	#frs_ob = B.Object.New("Mesh","testFRSTM")
	#frs_ob.link(nme)
	#sce.objects.link(frs_ob)
	#raise ValueError('test')
	return width, height, nme

####### Classes ##############
class Drawing(object):
	svgDPI = 90
	mm2SVG = 90.0/25.4
	inch2SVG = 90.0
	Units = ["km","m","cm","mm","inch"]
	__slots__=("polygons","scaleFactor", "materials", "width", "height", "layers", "layerMode", "unit")
	def __init__(self, polygons=[], materials=dict(), scaleFactor=1.0, width=None, height=None, units='m'):
		self.polygons = polygons
		self.materials = materials
		self.scaleFactor = scaleFactor
		self.width = width
		self.height = height
		self.unit = units
		self.layers = list()
		self.layerMode = None

	def makeLayers(self,mode=None):
		'''Modes: "noLayers", "byMaterial", "byLineweight", "byLinecolor", "byFillcolor" '''
		#TODO: fix layermodes

		self.layerMode = mode
		layers = dict()
		for pl in self.polygons:
			mat = pl.getMaterial()

			if mode is None:
				lname = "Drawing"
			elif mode == "byMaterial":
				lname = mat.name
			elif mode == "byLineweight":
				lname = str(round(mat.lineWeight,3))
			elif mode == "byLinecolor":
				c = col2RGB(mat.lineColor)
				lname = "rgb_"+str(c[0])+"_"+str(c[1])+"_"+str(c[2])
			elif mode == "byFillcolor":
				c = col2RGB(mat.fillColor)
				lname = "rgb_"+str(c[0])+"_"+str(c[1])+"_"+str(c[2])

			if lname not in layers:
				layers[lname] = [pl]
			else:
				layers[lname].append(pl)

		for L in layers:
			layers[L].sort(key=lambda x: (x.getMaterial().alpha))

		self.layers  = [(layername,layer) for layername,layer in layers.iteritems()]
		if mode == "byMaterial":
			#for proper export in svg format (and others supporting transparency), transparent layers must be after ones with opaque polys
			self.layers.sort(key=lambda x:(x[1][0].getMaterial().alpha))
			#TODO: fix other modes? (i think not possible)

	def exportSVG(self, filename=None):

		scaleF = self.scaleFactor
		#i need to convert to pixels, path data have no untis (stupid svg)
		if self.unit == 'mm':
			scaleF *= self.mm2SVG
		elif self.unit == 'cm':
			scaleF *= self.mm2SVG * 10
		elif self.unit == 'm':
			scaleF *= self.mm2SVG * 1000
		elif self.unit == 'km':
			scaleF *= self.mm2SVG * 1E6
		elif self.unit == 'inch':
			scaleF *= self.inch2SVG

		svgWidth = self.width*scaleF
		svgHeight = self.height*scaleF

		if not self.layers:
			self.makeLayers()

		svg = ['<?xml version="1.0" encoding="iso-8859-1" standalone="no"?>',\
				'<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">',\
				'<svg xmlns="http://www.w3.org/2000/svg" ',\
				'xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" ',\
				'width="%f" height="%f" >'% (svgWidth, svgHeight)]

		for layername,layer in self.layers:
			svg.append('<g id="%s" inkscape:groupmode="layer" inkscape:label="%s">'%(layername,layername))
			for pl in layer:
				svg_pl = pl.copy()
				svg_pl.flatten()
				svg_pl.scale(scaleF)
				#svg 0,0 is at top left corner
				svg_pl.move(svgWidth/2.0, -svgHeight/2.0 ,0.0)

				svg.append(svg_pl.drawSVG())

			svg.append("</g>")
		svg.append("</svg>")
		svg = '\n'.join(svg)
		if file is None:
			return svg
		else:
			F = open(filename, 'w+')
			F.write(svg)
			F.close()

	def exportDXF(self, filename):
		DXF = Drawing()
		DXF.styles.append(Style())			#table styles
		DXF.views.append(View('Normal'))	  #table view
		DXF.views.append(ViewByWindow('Window',leftBottom=(1,0),rightTop=(2,1)))  #idem

		for layername,layer in self.layers:

			if self.layerMode == "byMaterial":
				mat = self.materials[layername]
				Lcolor = col2DXF(mat.fillColor)
				plcolor = 256
			else:
				Lcolor = 255
				plcolor = None
			dxfLayers.append(Layer(color=Lcolor, name=layername))

			for pl in layer:
				dxfpl = pl.copy().scale(self.scaleFactor)
				dxfpl.flatten()
				DXF.extend(dxfpl.drawDXF(layer=layername, color=plcolor))

		DXF.saveas(filename)


	def exportBLENDER(self,scene_name="Drawing"):
		objects = []
		for pl in self.polygons:
			objects.append(pl.drawBlender(link=False))
		sce = B.Scene.New(scene_name)
		for ob in objects:
			sce.objects.link(ob)

class Poly(object):
	nextID = 0
	global CW,CCW
	CW = False
	CCW = True
	#Face attributes
	global BACKF,HOLE,NOATTR,HIDDEN,SECTION
	BACKF =  	0000001	#TODO: Handle backfaces as hidden geometry
	HOLE  =  	0000010
	HIDDEN =	0000100 #TODO: Handle hidden geometry
	SECTION =	0001000
	NOATTR = 	0000000

	__slots__ = ('ID','verts','material','normal','order','bounds','attr',\
				'holes','area2D', 'area3D', 'IDProps')
	def __init__ (self,plist=[],attr=NOATTR,IDProps=dict(),material=None):
		self.verts = list()
		self.ID = Poly.nextID
		Poly.nextID += 1
		self.material = material
		self.attr = attr
		self.IDProps = IDProps
		self.holes = list()
		if plist:
			self.extend(plist)
		self.bounds = Bounds(self)

	def __str__(self):
		res = ""
		for p in self.verts:
			res+= "\n"
			res+= str(p)
			res+= "\n"
		res+= "\n"
		return res

	def __iter__(self):
		return self.verts.__iter__()

	def getMaterial(self):
		if self.attr&SECTION:
			mat = self.material.section
			if mat is None:
				return SECTION_MATERIAL
			return mat
		#elif self.attr&HIDDEN:
			#return self.material.hidden
		#elif self.attr&PROJECTED:
			#return self.material.projected
		else:
			if self.material is None:
				return MATERIAL
			return self.material

	def getOrder2D(self):
		if len(self.verts) > 2:
			area = sum([perp(p.co, p.next.co) for p in self.verts])
			self.area2D = abs(area)/2.0
			if area < 0:
				self.order = CW
			else:
				self.order = CCW
			return self.order
		else:
			raise ValueError("Polygon has less than 3 points")

	def getArea2D(self):
		if len(self.verts) > 2:
			area = sum([perp(p.co, p.next.co) for p in self.verts])
			self.area2D = abs(area) / 2.0
			return self.area2D
		else:
			return 0.0
			#raise ValueError("Polygon has less than 3 points")

	def _fixArea(self,p):
		if p.pl is self:
			self.area2D += perp(p.co,p.next.co) / 2.0

	def getNormal(self):
		if len(self.verts) > 2:
			try:
				test = self.verts[0].co[2]
				N = Vector(0.0,0.0,0.0)
				for p in self.verts:
					N.x += (p.co[1] - p.next.co[1]) * (p.co[2] + p.next.co[2])
					N.y += (p.co[2] - p.next.co[2]) * (p.co[0] + p.next.co[0])
					N.z += (p.co[0] - p.next.co[0]) * (p.co[1] + p.next.co[1])
				self.area3D = N.length
				self.normal = N.normalize()
				return self.normal
			except IndexError:
				try:
					test = self.order
				except:
					self.getOrder2D()
				if self.order:
					self.normal = NORMAL_2D.copy()
				else:
					self.normal = -NORMAL_2D.copy()
				self.area3D = self.area2D
		else:
			raise ValueError("Polygon has less than 3 points")

	def getArea3D(self):
		if len(self.verts) > 2:
			self.getNormal()
			return self.area3D
		else:
			return 0.0
			#raise ValueError("Polygon has less than 3 points")

	#def copy(self):
		#cp = Poly([p.co.copy() for p in self.verts])
		#cp.holes = self.holes
		#cp.material = self.material
		#cp.attr = self.attr
		#cp.IDProps = self.IDProps
		#return cp
	def dumpVerts(self,HOLES=False,REV=False):
		result = [v.copy() for v in self.verts]
		if REV:
			result.reverse()
		for i,v in enumerate(result):
			try:
				v.next = result[i+1]
			except IndexError:
				v.next = result[0]
			v.prev = result[i-1]
			v.pl=self
		if HOLES:
			[result.extend(h.dumpVerts(HOLES=False, REV=REV)) for h in self.holes]
		return result

	def copy(self, HOLES=True, SHALLOW=False):
		'''Use SHALLOW with  caution, only if you are not going to affect vector data'''
		cp = Poly(attr=self.attr, IDProps=self.IDProps, material=self.material)
		if SHALLOW:
			cp.verts = [PL_Vertex(v.co, pl=cp) for v in self.verts]
		else:
			cp.verts = [PL_Vertex(v.co.copy(), pl=cp) for v in self.verts]
		for i,v in enumerate(cp.verts):
			try:
				v.next = cp.verts[i+1]
			except IndexError:
				v.next = cp.verts[0]
			v.prev = cp.verts[i-1]
		cp.order = self.order
		cp.area2D = self.area2D
		cp.bounds = self.bounds.copy()
		cp.bounds.ob = cp
		cp.area3D = self.area3D
		cp.normal = self.normal.copy()

		cp.holes = list()
		if HOLES and not self.attr & HOLE:
			cp.holes.extend([hole.copy(HOLES=False,SHALLOW=SHALLOW) for hole in self.holes])
		return cp

	def reverse(self):
		tmp = self.verts[1:]
		tmp.reverse()
		self.verts = [self.verts[0]]
		self.extend(tmp)
		if not self.attr & HOLE:
			[hole.reverse() for hole in self.holes]

	def addPoint(self, point, calc=True):
		if isinstance(point,PL_Vertex):
			if point in self.verts:
				return False
			p = point
			if not p.pl is self:
				p.pl = self
		else:
			p = PL_Vertex(point,pl=self)

		co = p.co
		self.verts.append(p)

		l = len(self.verts)
		if l > 2:
			self.verts[-2].next = p
			self.verts[0].prev = p
			p.prev = self.verts[-2]
			p.next = self.verts[0]

			if calc and l == 3:
				self.getOrder2D()
				self.getNormal()

		elif l == 2:
			self.verts[0].next = p
			self.verts[0].prev = p
			p.next = self.verts[0]
			p.prev = self.verts[0]

		if calc:
			self.bounds.checkNew(co)
			self._fixArea(p)

		return True

	def extend(self,newVerts, calc=True):
		if not newVerts:
			return
		offset = len(self.verts)
		if isinstance(newVerts[0], PL_Vertex):
			for v in newVerts:
				v.pl = self
			self.verts.extend(newVerts)
		else:
			self.verts.extend([PL_Vertex(v,pl=self) for v in newVerts])
		if offset > 0:
			self.verts[offset - 1].next = self.verts[offset]
			self.verts[0].prev = self.verts[-1]

		for i,v in enumerate(self.verts[offset:]):
			try:
				v.next = self.verts[offset + i + 1]
			except IndexError:
				v.next = self.verts[0]
			v.prev = self.verts[offset + i - 1]

		if calc:
			if offset < 3 and len(self.verts) > 2:
				self.getNormal()
				self.getOrder2D()

			try:
				self.bounds.recalc()
			except:
				self.bounds = Bounds(self)

	def insertPoint(self,i,co,calc=True):
		if i is 0 or i > len(self.verts) - 1:
			return self.addPoint(co, calc)
		else:
			if isinstance(co,PL_Vertex):
				if co in self.verts:
					return False
				p = co
				if not p.pl is self:
					p.pl = self
				co = p.co
			else:
				p = PL_Vertex(co,pl=self)

			self.verts.insert(i,p)
			p.prev = self.verts[i-1]
			p.next = self.verts[i+1]
			self.verts[i-1].next = p
			self.verts[i+1].prev = p
			l = len(self.verts)
			if calc:
				self.bounds.checkNew(co)
				self._fixArea(p)

			return True

	def insertPoints(self,points):
		offset = 0
		for i,point in points:
			#insert the points at corect position but don't recalc data, do it in the end
			if self.insertPoint(i+offset, point, False):
				offset+= 1
		self.bounds.recalc()
		self.getOrder2D()

	def removePoint(self,p,calc=True):
		if len(self.verts)>1:
			try:
				i = self.verts.index(p)
			except IndexError:
				raise ValueError("Point not in Polygon")

			self.verts.pop(i)
			try:
				self.verts[i-1].next = self.verts[i]
				self.verts[i].prev = self.verts[i - 1]
			except IndexError:
				self.verts[-1].next = self.verts[0]
				self.verts[0].prev = self.verts[- 1]

			if calc:
				self.bounds.checkRemoved(p.co)
				self.getArea2D()

	def removePointsByID(self,plist):
		newVerts = [v for v in self.verts if not v.ID in plist]
		self.verts = list()
		self.extend(newVerts)

	def removePoints(self,plist):
		for p in plist:
			self.removePoint(p)

	#def mirror(self,axis):
		#if axis == 'X':
			#centerX = self.bounds.xmax - self.bounds.xmin
			#for v in self.verts:
				#v.co[0] = 2.0*centerX - v.co[0]
		#elif axis == 'Y':
			#centerY = self.bounds.ymax - self.bounds.ymin
			#for v in self.verts:
				#v.co[1] = 2.0*centerY - v.co[1]
		#elif axis == 'Z':
			#centerZ = self.bounds.zmax - self.bounds.zmin
			#for v in self.verts:
				#v.co[2] = 2.0*centerY - v.co[2]
		#else:
			#raise ValueError("mirror axis parameter can only be 'X','Y','Z'")

	def scale(self,scalefactor, axis='XYZ'):
		#TODO: support arbitary axis scaling
		mx = ScaleMatrix(scalefactor, 3)
		for v in self.verts:
			v.co *= mx
		if not self.attr&HOLE:
			for hole in self.holes:
				hole.scale(scalefactor,axis)
		self.bounds.recalc()
		self.getOrder2D()
		self.getNormal()

	def move(self,dx,dy,dz):
		for v in self.verts:
			v.co.x += dx
			v.co.y += dy
			v.co.z += dz
		if not self.attr&HOLE:
			for hole in self.holes:
				hole.move(dx,dy,dz)
		self.bounds.recalc()

	def isValid2D(self):
		if len(self.verts) < 2 or self.area2D > ZEROAREA:
			return True
		return False

	def removeDoubles2D(self,EPSILON=ZEROLENGTH):
		if len(self.verts) > 1:
			doubles = [p.ID for p in self.verts if same2D(p.co,p.next.co,EPSILON)]
			self.removePointsByID(doubles)
			return len(self.verts)
		else:
			return 0

	def removeDoubles3D(self,EPSILON=ZEROLENGTH):
		if len(self.verts)>1:
			doubles = [p for p in self.verts if same3D(p.co,p.next.co,ZEROLENGTH)]
			self.removePoints(doubles)
			return len(self.verts)
		else:
			return 0

	def simplify3D(self,EPSILON=None):
		if EPSILON is None:
			#set threshold to 1/10000 of poly area so detail is preserved on small polys
			EPSILON = self.area3D*1E-6
		extras = [p.ID for p in self.verts if TriangleArea(p.prev.co, p.co, p.next.co) < EPSILON ]
		while extras:
			self.removePointsByID(extras)
			extras = [p.ID for p in self.verts if TriangleArea(p.prev.co, p.co, p.next.co) < EPSILON ]
		return len(self.verts)

	def simplify2D(self,EPSILON=None):
		if EPSILON is None:
			#set threshold to 1/10000 of poly area2D so detail is preserved on small polys
			EPSILON = self.area2D*1E-6
		extras = [p.ID for p in self.verts if  TriangleArea(p.co.copy().resize2D().resize3D(),
															p.next.co.copy().resize2D().resize3D(),
															p.prev.co.copy().resize2D().resize3D()) < EPSILON ]
		while extras:
			self.removePointsByID(extras)
			#extras = [p.ID for p in self.verts if abs(perp(p.co - p.next.co, p.co -p.prev.co)) < EPSILON ]
			extras = [p.ID for p in self.verts if TriangleArea(p.co.copy().resize2D().resize3D(),
															   p.next.co.copy().resize2D().resize3D(),
															   p.prev.co.copy().resize2D().resize3D()) < EPSILON ]

		return len(self.verts)

	def rel2Plane(self,pp,pno):
		rmap = [relPointPlane(p.co,pp,pno) for p in self.verts]
		rel = 0000
		for r in rmap:
			rel |= r
		return rel, rmap

	def rel2Poly3D(self,other):
		pp = other.verts[0].co
		pno = other.normal
		if other.attr & BACKF:
			pno = -pno
		#if self.attr & BACKF:
			#pno = -pno
		return self.rel2Plane(pp,pno)

	def selfIntersecting(self):
		#TODO: fix checking for vertical to xy polys
		if abs(DotVecs(self.normal,Vector(0.0,0.0,1.0))) < 100*E:
			return False

		for p0,p1 in [(p,p.next) for p in self.verts]:
			for P0,P1 in [(P,P.next) for P in self.verts]:
				if p0 is P0 or\
				   p1 is P0 or\
				   p0 is P1 or\
				   p1 is P1:
					continue
				if p0.co == P0.co:
					print 'same coords'
					return True

				u = p1.co - p0.co
				v = P1.co - P0.co
				w = p0.co - P0.co
				D = perp(u, v)
				if abs(D) < E:
					continue
				ratioA = perp(v,w)/D
				if ratioA > 1.0 - 10*E or ratioA < 10*E:
					continue
				ratioB = perp(u,w)/D
				if ratioB > 1.0 - 10*E or ratioB < 10*E:
					continue
				else:
					return True

		return False

	def classifyPoint2D(self, p, HOLES=False):
		if not self.bounds.pointIn2D(p):
			return OUT
		#if HOLES and self.holes:
			#for hole in self.holes:
				#c = hole.classifyPoint2D(p)
				#if c is IN:
					## in hole means out of poly
					#return OUT
				#elif c is ON:
					#return ON
		verts = self.dumpVerts(HOLES=HOLES)
		wn = 0
		#for v0 in self.verts:
		for v0 in verts:
			v1 = v0.next
			p0 = v0.co
			p1 = v1.co
			if abs(perp(p - p0, p1 - p0)) < E and inSegment(p,p0,p1,E):
				return ON

			if p0[1] <= p[1]:
				if p1[1] > p[1]:
					L = isLeft(p,p0,p1)
					if  L == LEFT:
						wn += 1

			elif p1[1] <= p[1]  :
				L = isLeft(p,p0,p1)
				if L == RIGHT:
					wn -= 1

		if wn:
			return IN
		else:
			return OUT

	def split2Plane(self, pp, pno, rmap=None, REV=False):
		if rmap is None:
			if REV:
				rmap = [relPointPlane(p.co,pp,-pno) for p in self.verts]
			else:
				rmap = [relPointPlane(p.co,pp,pno) for p in self.verts]
		elif REV:
			for i,r in enumerate(rmap):
				if r == INFRONT:
					rmap[i] = BEHIND
				elif r == BEHIND:
					rmap[i] = INFRONT

		split = list()
		splits = list()
		if rmap[0] == BEHIND or rmap[0] is ON:
			cross = 0
			last2first = False
		else:
			cross = 1
			last2first = True
		for i,p0 in enumerate(self.verts):

			r0 = rmap[i]
			try: r1 = rmap[i+1]
			except IndexError: r1 = rmap[0]
			p1 = p0.next
			lastR = rmap[i-1]

			if r0 == INFRONT:
				split.append(p0.co)
			elif r0 == BEHIND:
				pass
			elif r0 == ON:
				R = lastR | r1
				if R == BACKTOUCH or R == ON:
					pass
				else:
					I = p0.co
					split.append(I)
					cross +=1
					if cross == 2:
						splits.append(split)
						split=list()
						if R == INFRONT:
							#point is ENEX, need to add it to next split also
							split.append(I)
						cross = 0
				continue

			if r0 | r1 == CROSSING:
				cross +=1
				#I = rayHit(p0.co, pp, pno, p1.co - p0.co)
				I = LineIntersectPlane(p0.co,p1.co,pp,pno)
				if DBG and I is None:
					#part.drawBlender('slf-inter-split')
					drawPlane(pp,pno)
					self.drawBlender('wtf')
					raise ValueError('self-intersecting split')
				split.append(I)
				if cross == 2:
					cross = 0
					splits.append(split)
					split = list()

		if split:
			splits.append(split)
		if not splits:
			return []
		if last2first and len(splits) > 1 :
			splits[-1].extend(splits.pop(0))

		parts = list()
		holes = list()
		for split in splits:
			if len(split) > 2:
				pl = Poly([co.copy() for co in split])
				if pl.order == self.order:
					parts.append(pl)
				else:
					holes.append(pl)

		if not self.attr&HOLE:
			for hole in self.holes:
				if REV:
					hr,hrmap = hole.rel2Plane(pp, -pno)
				else:
					hr,hrmap = hole.rel2Plane(pp, pno)

				if hr == BEHIND or hr == BACKTOUCH:
					pass
				elif hr == INFRONT or hr == FRONTTOUCH:
					holes.append(hole)
				else:
					holes.extend(hole.split2Plane(pp,pno,hrmap))



		for part in parts:
			for i,hole in enumerate(holes):
				if hole.order == self.order:
					hole.reverse()
				if part.addHole(hole):
					del(holes[i])
			if part.order != self.order:
				part.reverse()
			part.attr = self.attr
			part.IDProps = self.IDProps
			part.material = self.material

			#if part.selfIntersecting():
				#print "WARNING: split self intersecting"
				#if DBG:

					#for part in parts:
						#part.drawBlender('slf-inter-split')
					#drawPlane(pp,pno)
					#self.drawBlender('slf-inter-poly')
					#raise ValueError('self-intersecting split')
				#else:
					#parts.remove(part)

		return parts

	def flatten(self):
		for p in self.verts:
			p.co.z = 0.0
		self.bounds.zmin = 0.0
		self.bounds.zmax = 0.0
		if self.order is CCW:
			self.normal = Vector(0.0,0.0,1.0)
		else:
			self.normal = Vector(0.0,0.0,-1.0)
		if not self.attr & HOLE:
			for hole in self.holes:
				hole.flatten()

	def flatten3D(self):
		if len(self.verts) < 2:
			return
		pp = self.verts[0].co
		pno = self.normal
		for v in self.verts:
			co = rayHit(v.co,pp,pno,pno)
			if co is None:
				continue
			else:
				v.co = co
		if not self.attr&HOLE:
			for hole in self.holes:
				hole.flatten3D()

	def toPerspective(self):
		#result =  self.copy(HOLES=False)
		#for v in result.verts:
			#w = - v.co[2] + E
			#if w == 0.0:
				#w = -E
			#v.co[0] *= 10/w
			#v.co[1] *= 10/w
			#v.co[2] = 1.0
		#result.getOrder2D()
		result = Poly([perspectize(v.co) for v in self.verts],attr=self.attr,IDProps=self.IDProps,material=self.material)
		if result.order != self.order:
			if self.attr&BACKF:
				#poly becomes frontface
				result.attr^=BACKF
			else:
				#poly becomes backface
				result.attr |= BACKF

		if not self.attr & HOLE:
			result.holes = [hole.toPerspective() for hole in self.holes]
		return result

	def project(self,pp,pno,direction=VIEW_NORMAL):
		for p in self.verts:
			p.co = rayHit(p.co, pp, pno, direction=direction)
		if not self.attr & HOLE:
			for hole in self.holes:
				hole.project(pp,pno,direction)

	def prj2Poly(self,other,direction=VIEW_NORMAL,COPY=False):
		pp = other.verts[0].co
		pno = other.normal
		if COPY:
			return self.pl.copy().project(pp,pno,direction)
		else:
			self.project(pp,pno,direction)

	#def getNonIsectPoint(self):
		#for p in self.verts:
			#if p.isect is None:
				#return p
		#return None

	def clipPoly(self,other):
		G = BooleanGraph(self,other)
		result = G.doSubtractAB()
		for pl in result:
			pl.prj2Poly(other)
		return result

	def addHole(self,hole):
		if self.bounds.disjoint2D(hole.bounds):
			if DBG: print "hole off bounds"
			return False
		G = BooleanGraph(hole,self)
		A,B = G.classifications()
		if A is OUT or A is OUTTOUCH or A is ON:
			return False
		result = G.doSubtractAB()
		if result and len(result) == 1:
			#whole point here is to keep ID and pass python "is" tests
			res = result[0]
			res.prj2Poly(self)
			self.verts = res.verts
			self.bounds = res.bounds
			self.area2D = res.area2D
			self.area3D = res.area3D
			self.holes = res.holes
		else:
			if DBG: print "hole covers self or splits it in 2"
			return False

	def union(self,other):
		if self.bounds.disjoint2D(other):
			return self
		G = BooleanGraph(self,other)
		result = G.doUnion()
		if result and len(result) == 1:
			res = result[0]
			res.prj2Poly(self)
			self.verts = res.verts
			self.holes = res.holes
			self.bounds = res.bounds
			self.area2D = res.area2D
			self.area3D = res.area3D
		else:
			return self

	def toMesh(self,offset=0):
		vlist = [v.co for v in self.verts]

		edgelist = list()
		L = len(self.verts)
		for i in xrange(L):
			j = i+offset
			if i < L - 1:
				edgelist.append((j,j+1))
			else:
				edgelist.append((j,offset))
		return vlist,edgelist

	def drawBlender(self, name="Mesh", flatten=False, AT_CUR=False, link=True):
		ob = B.Object.New("Mesh",name)
		me = B.Mesh.New(str(self.ID))
		#polys = list()
		for pl in [self]+self.holes:
			#vList = [v.co for v in pl]
			#me.verts.extend(vList)
			#polys.append(vList)
			vList,edgelist = pl.toMesh(offset=len(me.verts))
			me.verts.extend(vList)
			me.edges.extend(edgelist)
		#fill = B.Geometry.PolyFill(polys)
		#me.faces.extend(fill)
		if flatten:
			for v in me.verts:
				v.co.z = 0.0
		ob.link(me)
		if link:
			sce = B.Scene.getCurrent()
			sce.objects.link(ob)
		#me.triangleToQuad()
			if AT_CUR:
				cur_loc = B.Window.GetCursorPos()
				ob.setLocation(cur_loc)
		return ob

	def drawDXF(self,flatten=False, layer=None, color=None):
		entities = []
		org_point = [0.0,0.0,0.0]
		closed = 1

		if layer is None:
			layer = '0'
		if color is None:
			color = self.material.fillColor
			color = col2DXF(color)

		for pl in [self]+self.holes:
			if pl.verts:
				vlist = [v.co for v in pl.verts]
			if vlist:
				if flatten:
					for i, v in enumerate(vlist):
						vlist[i][2] = 0.0
				dxfPLINE = PolyLine(vlist, org_point, closed, layer=layer, color=color)
				entities.append(dxfPLINE)
		return entities

	def drawSVG(self):
		svg = list()
		s= '<path d="'
		s+=self.toSVGPath()
		for hole in self.holes:
			s+=hole.toSVGPath()
		s+='"'
		svg.append(s)
		s = 'id="'+str(self.ID)+'" '
		svg.append(s)
		if self.material:
			s = self.material.toSVGstyle()
			svg.append(s)

		svg.append('/>')
		return "\n".join(svg)

	def toSVGPath(self):
		if self.attr&HOLE and self.getOrder2D():
			self.reverse()
		elif not self.getOrder2D():
			self.reverse()

		s = "M %.3f,%.3f "%(self.verts[0].co[0],-self.verts[0].co[1])
		for p in self.verts:
			s+= "L %.3f,%3f "%(p.co[0],-p.co[1])
		s += "Z "
		return s

class Material(object):
	#TODO: Hook Materials to the core
	__slots__ = ('ID','name', 'fillColor', 'lineColor', 'lineWeight', 'section', 'type', 'alpha')
	matID = 0
	defLineColor =	[0.0, 0.0, 0.0]
	defLineColorS = [0.0, 0.0, 0.0]
	defFillColor =	[1.0, 1.0, 1.0, 0.0]
	defFillColorS = [0.0, 0.0, 0.0, 0.0]
	defLineWgt = 0.2
	defLineWgtS = 0.5

	mTypes = dict( normal ='normal',
				   section = 'section',
				   hidden = 'hidden',
				   projected = 'projected')


	#TODO: linestyle, hidden, projected
	def __init__(self, name=None, fillCo=None, lineCo=None, lineW=None, alpha=None, section=None, type=None):
		self.ID = Material.matID
		Material.matID += 1
		self.name = name or "material%i"%(self.ID)
		if type is Material.mTypes['section']:
			self.fillColor = fillCo or Material.defFillColorS
			self.lineColor = lineCo or Material.defLineColorS
			self.lineWeight = lineW or Material.defLineWgtS
		else:
			#TODO:need to add more types later
			self.fillColor = fillCo or Material.defFillColor
			self.lineColor = lineCo or Material.defLineColor
			self.lineWeight = lineW or Material.defLineWgt
		self.section = section or SECTION_MATERIAL
		self.alpha = alpha

	#def toDXFLayer(self):
		#from dxfLibrary import Layer
		#dxflayer = Layer(name=self.name, color=col2DXF(self.fillColor))
		#return str(dxflayer)

	def toSVGstyle(self,scalefactor=1.0):
		s='style="'
		fillC = col2RGB(self.fillColor)
		fillC = "rgb(" + str(fillC[0]) + "," + str(fillC[1]) + "," + str(fillC[2]) + ")"
		s+= 'fill:'+ fillC +';'
		lineC = col2RGB(self.lineColor)
		lineC = "rgb(" + str(lineC[0]) + "," + str(lineC[1]) + "," + str(lineC[2]) + ")"
		s+= 'stroke:'+ lineC +';'
		lineW = str(self.lineWeight * scalefactor)
		s+=' stroke-width:'+ lineW +'mm;'
		if not self.alpha is None:
			s+='fill-opacity:'+str(self.alpha)+';'
		s+='stroke-linecap:round ;stroke-linejoin :round; stroke-miterlimit:4; fill-rule:evenodd; enable-background:accumulate"'
		return s


	def toBlendMat(self):
		pass

	def toHPGLstyle(self):
		pass


class Bounds(object):
	__slots__=('xmin','xmax','ymin','ymax','zmin','zmax','ob','__init','area2D')
	#def __init__(self,ob):
		#self.ob = ob
		#self.__init = False
		#self.recalc()

	def __init__(self, ob, calc=True):
		self.ob = ob
		self.__init = False
		if calc:
			self.recalc()

	def copy(self):
		cp = Bounds(self.ob, calc=False)
		if self.__init:
			cp.__init = True
			cp.xmin = self.xmin
			cp.ymin = self.ymin
			cp.zmin = self.zmin
			cp.xmax = self.xmax
			cp.ymax = self.ymax
			cp.zmax = self.zmax
			cp.area2D = self.area2D
		return cp

	def recalc(self):
		x = [p.co[0] for p in self.ob]

		if not x:
			self.__init = False
			return
		y = [p.co[1] for p in self.ob]
		try:
			z = [p.co[2] for p in self.ob]
		except IndexError:
			z = [0.0]

		self.xmin = min(x) or -E
		self.ymin = min(y) or -E
		self.zmin = min(z) or -2*E
		self.xmax = max(x) or E
		self.ymax = max(y) or E
		self.zmax = max(z) or -E
		self._recalcArea2D()
		self.__init = True

	def _recalcArea2D(self):
		self.area2D = abs((self.xmax-self.xmin)*(self.ymax-self.xmin))

	def lineOut2D(self,l0,l1):
		return  (l0[1] > self.ymax and l1[1] > self.ymax) or\
				(l0[1] < self.ymin and l1[1] < self.ymin) or\
				(l0[0] > self.xmax and l1[0] > self.xmax) or\
				(l0[0] < self.xmin and l1[0] < self.xmin)

	def checkNew(self,co):
		if not self.__init:
			self.recalc()
			return
		x = co[0]
		if x < self.xmin:
			self.xmin = x
			self._recalcArea2D()
		elif x > self.xmax:
			self.xmax = x
			self._recalcArea2D()

		y = co[1]
		if y > self.ymax:
			self.ymax = y
			self._recalcArea2D()
		elif y < self.ymin:
			self.ymin = y
			self._recalcArea2D()

		try:
			z = co[2]
			if z > self.zmax:
				self.zmax = z
			elif z < self.zmin:
				self.zmin = z
		except IndexError:
			self.zmax = E
			self.zmin = -E


	def checkRemoved(self,co):
		if not self.__init:
			self.recalc()
			return
		if co[0] == self.xmin:
			xlist = [p.co[0] for p in self.ob.verts]
			self.xmin = min(xlist)
			self._recalcArea2D()
		elif co[0] == self.xmax:
			xlist = [p.co[0] for p in self.ob.verts]
			self.xmax = max(xlist)
			self._recalcArea2D()

		if co[1] == self.ymax:
			ylist = [p.co[1] for p in self.ob.verts]
			self.ymax = max(ylist)
			self._recalcArea2D()
		elif co[1] == self.ymin:
			ylist = [p.co[1] for p in self.ob.verts]
			self.ymin = min(ylist)
			self._recalcArea2D()

		try:
			if co[2] == self.zmin:
				zlist = [p.co[2] for p in self.ob.verts]
				self.zmin = min(zlist)
			elif co[2] == self.zmax:
				zlist = [p.co[2] for p in self.ob.verts]
				self.zmax = max(zlist)
		except IndexError:
			pass

	def pointIn2D(self,p):
		return not (p[0] < self.xmin - ZEROLENGTH or\
					p[0] > self.xmax + ZEROLENGTH or\
					p[1] < self.ymin - ZEROLENGTH or\
					p[1] > self.ymax + ZEROLENGTH)


	def disjoint2D(self,other):
		if not isinstance(other,Bounds):
			other = other.bounds
		if not self.__init: self.recalc()
		if not other.__init: other.recalc()

		return self.xmax < other.xmin or\
			   self.xmin > other.xmax or\
			   self.ymax < other.ymin or\
			   self.ymin > other.ymax

	def intersect3D(self,other):
		'''function taken from pantograph, altered to fit Bounds Class'''
		if not isinstance(other,Bounds):
			other = other.bounds
		if not self.__init:
			self.recalc()
		if not other.__init:
			other.recalc()
		if (((self.xmin < other.xmin < self.xmax) or\
			 (self.xmin < other.xmax < self.xmax) or\
			 (other.xmin < self.xmin < other.xmax) or\
			 (other.xmin < self.xmax < other.xmax)) and\
			((self.ymin < other.ymin < self.ymax) or\
			 (self.ymin < other.ymax < self.ymax) or\
			 (other.ymin < self.ymin < other.ymax) or\
			 (other.ymin < self.ymax < other.ymax)) and\
			((self.zmin < other.zmin < self.zmax) or\
			 (self.zmin < other.zmax < self.zmax) or\
			 (other.zmin < self.zmin < other.zmax) or\
			 (other.zmin < self.zmax < other.zmax))):
			return True

		else:
			return False

class PL_Vertex(object):
	nextID = 0
	__slots__ = ['ID','co', 'next', 'prev','isect','pl','itype']
	def __init__ (self, co, next=None, prev=None, pl=None):
		self.co = co
		self.ID = PL_Vertex.nextID
		PL_Vertex.nextID +=1
		self.next = next
		self.prev = prev
		self.pl = pl
		self.isect = None
		self.itype = NOTYPE

	def __str__(self):
		if self.isect is None:
			try:
				return "%i) %.4f, %.4f | %i"%(self.pl.verts.index(self), self.co.x, self.co.y,self.pl.ID)
			except:
				return "*) %.4f, %.4f | *"%(self.co.x, self.co.y)
		else:
			try:
				return "%i) %.4f, %.4f | %i --> %i) %.4f, %.4f | %i (%s)"%\
				(self.pl.verts.index(self), self.co.x, self.co.y, self.pl.ID, self.isect.pl.verts.index(self.isect), self.isect.co.x, self.isect.co.y, self.isect.pl.ID,str(self.itype))
			except:
				return "*) %.4f, %.4f | * --> *) %.4f, %.4f | *"%(self.co.x, self.co.y,self.isect.co.x,self.isect.co.y)

	def copy(self,SHALLOW=True):
		if SHALLOW:
			cp = PL_Vertex(self.co,self.pl)
		else:
			cp = PL_Vertex(self.co.copy(),self.pl)
		cp.next = self.next
		cp.prev = self.prev
		cp.isect = self.isect
		cp.itype = self.itype
		return cp

class BSPTree(object):
	__slots__ = ('root','front','back')
	def __init__(self, faceList):
		self.root = list()
		self.front = list()
		self.back = list()

		if len(faceList)>1:
			self.makeNewBranch(faceList)
		else:
			self.root = faceList

	def __str__(self):
		return "%s \n %s \n %s" % (str(self.root[0]), str(self.back), str(self.front))

	def makeNewBranch(self, faceList):
		faceList.sort(key= lambda x: (x.area2D))
		bestnode = faceList.pop()
		#print "Node:",bestnode.ID
		self.root = [bestnode]
		backlist = list()
		frontlist = list()
		pp = bestnode.verts[0].co
		pno = bestnode.normal
		for f in faceList:
			r,rmap = f.rel2Poly3D(bestnode)
			if r is ON:
				self.root.append(f)
			elif r is BEHIND or r is BACKTOUCH:
				backlist.append(f)
			elif r is INFRONT or r is FRONTTOUCH:
				frontlist.append(f)
			else:
				frontlist.extend(f.split2Plane(pp,pno,rmap))
				backlist.extend(f.split2Plane(pp,pno,rmap,REV=True))

				global SPLIT_CALLS
				SPLIT_CALLS += 1
		if backlist:
			self.back = BSPTree(backlist)
		if frontlist:
			self.front = BSPTree(frontlist)

	def backToFront(self):
		b2fList = list()
		if self.back:
			b2fList.extend(self.back.backToFront())

		b2fList.extend(self.root)

		if self.front:
			b2fList.extend(self.front.backToFront())

		return b2fList

	def frontToBack(self):
		f2bList = list()

		if self.front:
			f2bList.extend(self.front.frontToBack())

		f2bList.extend(self.root)

		if self.back:
			f2bList.extend(self.back.frontToBack())

		return f2bList

	def sortOnPoint(self,co):
		sortedList = list()
		partition = self.root[0]
		r = relPointPlane(co,partition.verts[0].co,partition.normal)
		if r is INFRONT:
			if self.back:
				sortedList.extend(self.back.sortOnPoint(co))
			sortedList.extend(self.root)
			if self.front:
				sortedList.extend(self.front.sortOnPoint(co))
		elif r is BEHIND:
			if self.front:
				sortedList.extend(self.front.sortOnPoint(co))
			sortedList.extend(self.root)
			if self.back:
				sortedList.extend(self.back.sortOnPoint(co))
		else:
			if self.front:
				sortedList.extend(self.front.sortOnPoint(co))
			if self.back:
				sortedList.extend(self.back.sortOnPoint(co))
		return sortedList



def vRenderBSP (faceList, sections):
	t = B.sys.time()
	print 'building tree...'
	if PERSP:
		screenList = [pl.toPerspective() for pl in faceList]
		bsptree = BSPTree([pl for i,pl in enumerate(faceList) if not screenList[i].attr&BACKF])
	else:
		bsptree = BSPTree([pl for pl in faceList if not pl.attr&BACKF])

	print 'sorting....'
	faceList = bsptree.backToFront()
	if PERSP:
		faceList = [pl.toPerspective() for pl in faceList]
		faceList = [pl for pl in faceList if not pl.attr&BACKF]
	else:
		[pl.flatten() for pl in faceList]
	print 'clipping...'
	dwg = list()
	#for pl in sections:
		#faceList = doCLip(pl,faceList)
		#dwg.append(pl)
	while faceList:
		clip = faceList.pop()
		mat = clip.material
		if faceList and mat and mat.alpha is None:
			newFacelist=list()
			[newFacelist.extend(clip.clipPoly(pl)) for pl in faceList]
			faceList=newFacelist
		dwg.append(clip)

	print 'rejoining....'
	islands = [list() for i in xrange(COPLANAR_ID)]
	for pl in dwg:
		islands[pl.IDProps['coplanar']].append(pl)

	final = list()
	for island in islands:
		final.extend(doUnion(island))
	print 'BSP render method took %.2fsec'%(B.sys.time()-t)
	print 'done!'

	return final

class BooleanGraph(object):
	global UNION,SUBTRACT_AB,SUBTRACT_BA,INTERSECT,DIFFERENCE,MODE_2D,MODE_3D
	UNION = 'UNION'
	SUBTRACT_AB = 'SUBTRACT_AB'
	SUBTRACT_BA = 'SUBTRACT_BA'
	DIFFERENCE = 'DIFFERENCE' #unimplemented
	INTERSECT =	'INTERSECT'
	MODE_2D = '2D'
	MODE_3D = '3D'

	global ENTER,EXIT,ENEX,EXEN,INVALID,NOTYPE

	ENTER = 	00010 # 8
	EXIT = 		00001 # 1
	ENEX = 		01001 # 513
	EXEN =  	00110 # 72
	INVALID = 	01111 # 585
	NOTYPE = 	00000 # 0

	__slots__=('classDictA', 'classDictB', 'classA', 'classB', 'iNum', 'vertsA', 'vertsB', 'origA', 'origB')
	def __init__ (self,plA,plB):
		self.origA = plA
		self.origB = plB
		self.classA = NOCLASS
		self.classB = NOCLASS
		self.classDictA = dict()
		self.classDictB = dict()
		self.classDictA[IN]=list()
		self.classDictB[IN]=list()
		self.classDictA[OUT]=list()
		self.classDictB[OUT]=list()
		if plA.order: self.vertsA = self.origA.dumpVerts()
		else: self.vertsA = self.origA.dumpVerts(REV=True)
		if plB.order: self.vertsB = self.origB.dumpVerts()
		else: self.vertsB = self.origB.dumpVerts(REV=True)

		for hole in self.origA.holes:
			if hole.order: self.vertsA.extend(hole.dumpVerts(REV=True))
			else: self.vertsA.extend(hole.dumpVerts())
		for hole in self.origB.holes:
			if hole.order: self.vertsB.extend(hole.dumpVerts(REV=True))
			else: self.vertsB.extend(hole.dumpVerts())

		self.iNum = 0
		self.findIntersections()

	def classifications(self):
		return self.classA, self.classB

	def __str__(self):
		res = "\n"
		res+= '###################################\n'
		res+= '########   POLY A: %i ##############\n'%(self.origA.ID)
		res+= '###################################\n'
		for v in self.vertsA:
			res+= str(v)+"\n"
		res+= '###################################\n'
		res+= '########   POLY B: %i ##############\n'%(self.origB.ID)
		res+= '###################################\n'
		for v in self.vertsB:
			res+= str(v)+"\n"
		res+= '###################################\n'
		res+= "\n"
		res+= "\n"
		return res

	def findIntersections(self):
		prec = 1E-5
		uList = [p.next.co - p.co for p in self.vertsA]
		vList = [p.next.co - p.co for p in self.vertsB]
		lineOutB = self.origB.bounds.lineOut2D
		for i,a0 in enumerate(self.vertsA):
			a1 = a0.next
			lineOutA = a0.pl.bounds.lineOut2D
			if lineOutB(a0.co,a1.co):
				continue
			u = uList[i]
			for j,b0 in enumerate(self.vertsB):
				b1 = b0.next
				if lineOutA(b0.co,b1.co):
					continue
				if b0.isect and (b0.isect is a0 or b0.isect is a1) or\
				   b1.isect and (b1.isect is a0 or b1.isect is a1):
					continue

				isectA = isectB = None
				v = vList[j]
				w = a0.co - b0.co
				D = perp(u,v)
				if abs(D) < E:
					#edges are parallel
					continue
				ratioA = perp(v,w)/D
				ratioB = perp(u,w)/D

				I = a0.co + ratioA*u

				inA = inSegment(I, a0.co, a1.co,-prec)
				if not inA:
					continue
				inB = inSegment(I, b0.co, b1.co,-prec)
				if not inB:
					continue

				if ratioA == 0.0 or same2D(I, a0.co, prec):
					if a0.isect is None:
						isectA = a0
					else:
						continue
				elif ratioA == 1.0 or same2D(I, a1.co, prec):
					if a1.isect is None:
						isectA = a1
					else:
						continue
				if ratioB == 0.0 or same2D(I, b0.co, prec):
					if b0.isect is None:
						isectB = b0
					else:
						continue
				elif ratioB == 1.0 or same2D(I, b1.co, prec):
					if b1.isect is None:
						isectB = b1
					else:
						continue

				if isectB is None:
					plB = b0.pl
					isectB = PL_Vertex(I, pl=plB)
					b0.next = isectB
					b1.prev = isectB
					isectB.next = b1
					isectB.prev = b0
					self.vertsB.append(isectB)
					vList.append(b1.co - isectB.co)
					v = isectB.co - b0.co
					vList[j] = v


				if isectA is None:
					plA = a0.pl
					isectA = PL_Vertex(I, pl=plA)
					a0.next = isectA
					a1.prev = isectA
					isectA.next = a1
					isectA.prev = a0
					self.vertsA.append(isectA)
					uList.append(a1.co - isectA.co)
					u = isectA.co - a0.co
					uList[i] = u
					a1 = isectA


				self.iNum+=1
				isectA.isect = isectB
				isectB.isect = isectA

		if DBGBOOL: print "Intersections found",self.iNum
		self.classifyIntersections()
		if DBGBOOL: print "Valid Intersections found",self.iNum

	def classifyIntersection(self,p):
		other = p.isect.pl
		hole = not(other is self.origA or other is self.origB)
		if p.prev.isect and\
			   (p.isect.prev is p.prev.isect or\
				p.isect.next is p.prev.isect):
				rPrev = ON
		else:
			testP = MidpointVecs(p.co,p.prev.co)
			rPrev = other.classifyPoint2D(testP)
			if hole:
				if rPrev is IN:
					rPrev = OUT
				elif rPrev is OUT:
					rPrev = IN

		if p.next.isect and\
		   (p.isect.next is p.next.isect or\
			p.isect.prev is p.next.isect):
			rNext = ON
		else:
			testP = MidpointVecs(p.co,p.next.co)
			rNext = other.classifyPoint2D(testP)
			if hole:
				if rNext is IN:
					rNext = OUT
				elif rNext is OUT:
					rNext = IN

		return rPrev,rNext

	def classifyIntersections(self):
		'''
		This function should classify all intersections on self.vertsA and self.vertsB
		'''
		classDict = dict()
		classDict[self.origA] = NOCLASS
		classDict[self.origB] = NOCLASS
		[classDict.setdefault(hole,NOCLASS) for hole in self.origA.holes]
		[classDict.setdefault(hole,NOCLASS) for hole in self.origB.holes]
		verts = self.vertsB[:] + self.vertsA[:]
		for v in verts:
			if v.isect is None:
				continue
			#else:
				#del(classDict[v.isect.pl])
			
			rPrev, rNext = self.classifyIntersection(v)
			R = rPrev | rNext
			classDict[v.pl] |= R
			#classDict[v.isect.pl] |= R
			if v.itype != NOTYPE:
				continue
			if R == ON:
				self.iNum -= 1
				v.itype = INVALID
				v.isect.itype = INVALID
			elif R == IN:
				v.itype = EXEN
				v.isect.itype = ENEX
			elif R == OUT:
				v.itype = ENEX
				#not definitive, need to check p.isect
				rAPrev,rANext = self.classifyIntersection(v.isect)
				RA = rAPrev | rANext
				if RA == IN:
					v.isect.itype = EXEN
				else:
					v.isect.itype = ENEX
			elif (rPrev == ON and rNext == IN) or\
				 (rPrev == OUT and rNext == IN) or\
				 (rPrev == OUT and rNext == ON):
				v.itype = ENTER
				v.isect.itype = EXIT
			else:
				v.itype = EXIT
				v.isect.itype = ENTER

		for pl,cls in classDict.iteritems():
			A = False
			if pl is self.origA or pl in self.origA.holes:
				A=True
			if cls == NOCLASS:
				p = pl.verts[0]
				start = p
				cls = ON
				while cls == ON:
					if A:
						cls = self.origB.classifyPoint2D(p.co,HOLES=True)
					else:
						cls = self.origA.classifyPoint2D(p.co,HOLES=True)
					p = p.next
					if p is start:
						raise AssertionError('WTF?')
			if A:
				self.classA |= cls
				if cls in self.classDictA:
					self.classDictA[cls].append(pl)
			else:
				self.classB |= cls
				if cls in self.classDictB:
					self.classDictB[cls].append(pl)

					

		if DBGBOOL: print 'dbgbool: classA is %i, classB is %i'%(self.classA, self.classB)

	#def _specialCases(self,op):
		#r = None
		#A = self.classA
		#B = self.classB
		#if A == OUT and B == OUT:
			#if DBGBOOL: print "dbg: special case A==OUT, B==OUT"
			#if op is UNION:			r = [self.origA.copy(),self.origB.copy()]
			#elif op is SUBTRACT_AB: r = [self.origB.copy()]
			#elif op is SUBTRACT_BA: r = [self.origA.copy()]
			#elif op is INTERSECT:	r = []
		#elif A == OUTTOUCH and B == OUTTOUCH:
			#if DBGBOOL: print "dbg: special case A==OUTTOUCH, B==OUTTOUCH"
			#if op is UNION:			r = None
			#elif op is SUBTRACT_AB: r = [self.origB.copy()]
			#elif op is SUBTRACT_BA: r = [self.origA.copy()]
			#elif op is INTERSECT:	r = []

		#if A == OUT and B == IN:
			#if DBGBOOL: print "dbg: special case A==OUT, B==IN"
			#if op is UNION:			r = [self.origA.copy()]
			#elif op is SUBTRACT_AB: r = []
			#elif op is SUBTRACT_BA:
				#if len(self.vertsA) > len(self.origA.verts):
					##poly B is touching from the inside, inscribed
					#r = None
				#else:
					#base = self.origA.copy()
					#h = self.origB.copy()
					#h.attr|=HOLE
					#h.reverse()
					#base.holes.append(h)
					#r = [base]
			#elif op is INTERSECT:	r = [self.origB.copy()]

		#elif A == IN and B == OUT:
			#if DBGBOOL: print "dbg: special case A==IN, B==OUT"
			#if op is UNION:			r = [self.origB.copy()]
			#elif op is SUBTRACT_AB:
				#if len(self.vertsB) > len(self.origB.verts):
					##poly A is touching from the inside, inscribed
					#r = None
				#else:
					#base = self.origB.copy()
					#h = self.origA.copy()
					#h.reverse()
					#h.attr|=HOLE
					#base.holes.append(h)
					#r = [base]
			#elif op is SUBTRACT_BA: r = []
			#elif op is INTERSECT:	r = [self.origA.copy()]

		#elif A == INTOUCH:
			#if DBGBOOL: print "dbg: special case A==INTOUCH, B==OUTTOUCH"
			##B is OUTTOUCH
			#if op is UNION:			r = [self.origB.copy()]
			#elif op is SUBTRACT_AB: r = None
			#elif op is SUBTRACT_BA: r = []
			#elif op is INTERSECT:	r = [self.origA.copy()]

		#elif B == INTOUCH:
			#if DBGBOOL: print "dbg: special case A==OUTTOUCH, B==INTOUCH"
			##A is OUTTOUCH
			#if op is UNION:			r = [self.origA.copy()]
			#elif op is SUBTRACT_AB: r = []
			#elif op is SUBTRACT_BA: r = None
			#elif op is INTERSECT:	r = [self.origB.copy()]

		#elif A == ON:
			#if DBGBOOL: print "dbg: special case A==ON, B==ON"
			## B is ON too, polys identical
			#if op is UNION:			r = [self.origA.copy()]
			#elif op is SUBTRACT_AB: r = []
			#elif op is SUBTRACT_BA: r = []
			#elif op is INTERSECT:	r = [self.origB.copy()]

		#return r

	def _entryPoints(self,op):
		'''
		EntryPoints:
		if no entry points and since out-out is already excluded the poly either
		lies inside a hole or lies inside the gaps between holes and ring.

		for every hole:
			classify a point to the hole
				if it is in, we are done it lies inside a hole so make outcome for op
			if point wasnt in any hole it lies on the "solid" part
				only problem here is subtract that poly from the other.
				easy behaviour is add outer ring as hole only.
				correct is return other with outer ring as hole + this holes as
				normal solid polygons
		'''
		entryPoints = list()

		if op is SUBTRACT_AB:
			entryPoints = [p for p in self.vertsB\
						   if (p.itype is EXIT and\
							   not p.next.itype is INVALID and\
							   not p.next.itype is EXIT) or\
							  p.itype is ENEX]
			entryPoints.extend([pl.verts[0] for pl in self.classDictA[IN]])
			entryPoints.extend([pl.verts[0] for pl in self.classDictB[OUT]])

		elif op is SUBTRACT_BA:
			entryPoints = [p for p in self.vertA\
						   if (p.itype is EXIT and\
							   not p.next.itype is INVALID and\
							   not p.next.itype is EXIT) or\
							  p.itype is ENEX]
			
			entryPoints.extend([pl.verts[0] for pl in self.classDictB[IN]])
			entryPoints.extend([pl.verts[0] for pl in self.classDictA[OUT]])
			
		elif op is UNION:
			entryPoints = [p for p in self.vertsA\
						   if (p.itype is EXIT and not p.next.itype is EXIT and not p.next.itype is INVALID) or\
							  (p.itype is ENEX and p.isect.itype is ENEX)]
			
			entryPoints.extend([pl.verts[0] for pl in self.classDictB[OUT]])
			entryPoints.extend([pl.verts[0] for pl in self.classDictA[OUT]])

		elif op is INTERSECT:
			entryPoints = [p for p in self.vertsB\
						   if (p.itype is ENTER and\
						      not p.next.itype is ENTER and\
							  not p.next.itype is INVALID)]
			entryPoints.extend([pl.verts[0] for pl in self.classDictA[IN]])
			entryPoints.extend([pl.verts[0] for pl in self.classDictB[IN]])
		return entryPoints


	def _doOperation(self,op):
		'''
		Walking:
		walking on vert chains will be trickier
		one thing is that we can't  reverse so there should exist added rules for going to current.prev
		instead of current.next all the time. note that holes are now allways CW and rings are CCW.
		This will be helpfull for defining holes in outcome polys
		This is a really nice and elegant solution if achieved :D
		'''
		entryPoints = self._entryPoints(op)
		if not entryPoints:
			if DBGBOOL: print "NO ENTRY POINTS"
			#print "classA = ", self.classA
			#print "classB = ", self.classB
			#raise AssertionError("No entry points found !?!")
			return []

		revPolys = list()
		if op is SUBTRACT_AB:
			revPolys.append(self.origA.ID)
			revPolys.extend([h.ID for h in self.origA.holes])
		elif op is SUBTRACT_BA:
			revPolys.append(self.origB.ID)
			revPolys.extend([h.ID for h in self.origB.holes])

		result = list()
		holes = list()
		TOO_MUCH = len(self.vertsA) + len(self.vertsB)
		if DBGBOOL: print 'walking....'
		while entryPoints:
			start = entryPoints.pop()
			part = list()
			part.append(start.co)
			if start.pl.ID in revPolys:
				current = start.prev
			else:
				current = start.next

			if DBGBOOL:#DEBUG
				print "new part"
				print start
			i = 0
			lastType = NOTYPE
			while not (current is start or current is start.isect):
				i += 1
				if i > TOO_MUCH:
					if DBGBOOL:#DEBUG
						print current
						flag = "ENDLESS-WALK-%s"%(op)
						part = Poly(part)
						part.drawBlender(flag,True)
						self.debug(flag)
					else:
						print "oops, lost some polys"
						flag = "ENDLESS-WALK-%s"%(op)
						part = Poly(part)
						part.drawBlender(flag,True)
						self.debug(flag)
						return result

				if DBGBOOL: print current
				part.append(current.co)
				
				if current.isect is None or current.itype is INVALID:
					pass
				else:
					if current in entryPoints and\
					   not (current.itype is EXEN or current.itype is ENEX):
						entryPoints.remove(current)
					elif current.isect in entryPoints and\
						not (current.itype is EXEN or current.itype is ENEX):
						entryPoints.remove(current.isect)

					if op is INTERSECT and current.itype == EXIT:
						current = current.isect

					elif op is UNION:
						if current.itype == ENTER or \
						   (current.itype is ENEX and \
						    current.isect.itype is ENEX):
								current = current.isect

					elif op is SUBTRACT_AB:
						if (current.itype is ENEX and \
						   (current.isect.itype is ENEX or current.pl.ID in revPolys)) or\
						   lastType == current.itype:
							pass
						else:
							current = current.isect

					elif op is SUBTRACT_BA:
						if (current.itype is ENEX and \
						   (current.isect.itype is ENEX or \
						    current.pl.ID in revPolys)) or \
						   lastType == curent.itype:
							pass
						else:
							current = current.isect

					lastType = current.itype

				if current.pl.ID in revPolys:
					current = current.prev
				else:
					current = current.next

			if len(part) > 2:
				part = Poly([co.copy() for co in part])
				if part.simplify2D() > 2:
					if part.order:
						result.append(part)
					else:
						holes.append(part)
		
		if DBGBOOL: print "found %i holes and %i parts"%(len(result),len(holes))
		for i,hole in enumerate(holes):
			h = hole.verts[0]
			for part in result:
				if part.classifyPoint2D(h.co,HOLES=True) == OUT:
					continue
				else:
					hole.attr|=HOLE
					part.holes.append(hole)
					del(holes[i])
					#each hole belongs only to one part, so break here
					break
		if holes:
			#any holes left, need to be made "real" polys
			if DBGBOOL: print "%i holes become real parts"%(len(holes))
			[h.reverse() for h in holes]
			result.extend(holes)
		
		if DBGBOOL: print "found %i parts in %s"%(len(result), op)
		return result

	def doSubtractAB(self,MODE=MODE_3D):
		op = SUBTRACT_AB
		if DBGBOOL: print "doing %s"%(op)
		result = self._doOperation(op)
		return result

	def doSubtractBA(self,MODE=MODE_3D):
		op = SUBTRACT_BA
		if DBGBOOL: print "doing %s"%(op)
		result = self._doOperation(op)
		return result

	def doIntersect(self):
		op = INTERSECT
		if DBGBOOL: print "doing %s"%(op)
		result = self._doOperation(op)
		return result

	def doUnion(self):
		op = UNION
		if DBGBOOL: print "doing %s"%(op)
		result = self._doOperation(op)
		return result

		#if DBGBOOL: print "success! (?) found %i holes and %i base(s)"%(len(holes),len(result))

	def debug(self,flag):
		self.origA.drawBlender('origA-'+flag)
		self.origB.drawBlender('origB-'+flag)

		print self
		raise Exception("BOOLEAN GRAPH "+flag) #debug

###### TEST FUNCTIONS
def getSelectedPolys():
	global PL_THRES
	PL_THRES = 1.0 - float("5E-"+str(PL_THRES))
	sce = B.Scene.getCurrent()

	clip_ob = sce.objects.active
	subj_ob =  [ob for ob in sce.objects.selected if ob.name != clip_ob.name][0]

	clip_me = B.Mesh.New()
	clip_me.getFromObject(clip_ob)
	clip_me.transform(clip_ob.mat)
	subj_me = B.Mesh.New()
	subj_me.getFromObject(subj_ob)
	subj_me.transform(subj_ob.mat)
	clip = mesh2Polys(clip_me)
	subj = mesh2Polys(subj_me)
	return clip,subj

def testBoolean(op):
	global DBGBOOL
	DBGBOOL = True
	sce = B.Scene.getCurrent()

	clip,subj = getSelectedPolys()
	clip = clip[0]
	subj = subj[0]
	G = BooleanGraph(clip,subj)
	if op == 'union':
		result = G.doUnion()
	elif op == 'subtract':
		result = G.doSubtractAB()
	elif op == 'int':
		result = G.doIntersect()

	if not result:
		print "no result"
	else:
		for pl in result:
			pl.drawBlender('main',AT_CUR=True)

	print G

def testSplit2Plane():
	global DO_CREASE,CREASE_ANGLE,PL_THRES
	PL_THRES = 1.0 - float('5e-6')
	CREASE_ANGLE = 30.0
	sce = B.Scene.getCurrent()
	plane_ob = sce.objects.active
	plane_me = plane_ob.getData(mesh=1)
	pp = plane_me.verts[0].co.copy() * plane_ob.mat
	pno = plane_me.faces[0].no.copy() * plane_ob.mat.rotationPart()
	pl2split = list()
	proxy = B.Mesh.New('proxy')
	for ob in sce.objects.selected:
		if ob.name == plane_ob.name:
			continue
		proxy.getFromObject(ob)
		proxy.transform(ob.mat)
		pl2split.extend(mesh2Polys(proxy))

	frontsplits = list()
	backsplits = list()
	for pl in pl2split:
		#print pl
		#pl.drawBlender('testpl')
	#return
		frontsplits.extend(pl.split2Plane(pp,pno))
		backsplits.extend(pl.split2Plane(pp,pno,REV=True))
	for pl in frontsplits:
		pl.drawBlender('frontsplit')
	for pl in backsplits:
		pl.drawBlender('backsplit')

def testClip():
	sce = B.Scene.getCurrent()
	ob = sce.objects.active
	tmp_me = B.Mesh.New('tmp')
	tmp_me.getFromObject(ob)
	cam = sce.objects.camera
	cam_mx = cam.getInverseMatrix()
	tmp_me.transform(cam_mx)
	camData = B.Camera.Get(cam.name)
	near = -camData.clipStart
	pp = Vector(0.0,0.0,near)
	xedges = clipMeshPlane(tmp_me,pp,VIEW_NORMAL)

def testSimplify2D(EPSILON=ZEROAREA):
	sce = B.Scene.getCurrent()
	ob = sce.objects.active
	tmp_me = B.Mesh.New('tmp')
	tmp_me.getFromObject(ob)
	tmp_me.transform(ob.mat)
	try:
		poly = mesh2Polys(tmp_me)[0]
		poly.flatten()
		EPSILON = poly.area2D*1E-4
	except IndexError:
		print "Poly VAnished in thin air on convert, is that good?"
	if poly.simplify2D(EPSILON) > 2:
		poly.drawBlender('simplified_poly')
	else:
		print "Poly VAnished in thin air, is that good?"

if __name__ == '__main__':
	#if not copy:
		#B.Draw.PupMenu('Error%t|This script requires a full python install')
	B.Window.FileSelector(vRender_ui, 'Output VectorFile')
	#testBoolean('subtract')
	#testBoolean('int')
	#testBoolean('union')
	#testClip()
	#testSplit2Plane()
	#testSimplify2D()
