__init__.py

# ##### BEGIN GPL LICENSE BLOCK #####
#
#  SCA Tree Generator, a Blender addon
#  (c) 2013 Michel J. Anders (varkenvarken)
#
#  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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
#
# ##### END GPL LICENSE BLOCK #####

bl_info = {
	"name": "SCA Tree Generator",
	"author": "michel anders (varkenvarken)",
	"version": (0, 0, 8),
	"blender": (2, 66, 0),
	"location": "View3D > Add > Mesh",
	"description": "Adds a tree created with the space colonization algorithm starting at the 3D cursor",
	"warning": "",
	"wiki_url": "https://github.com/varkenvarken/spacetree/wiki",
	"tracker_url": "",
	"category": "Add Mesh"}

from time import time
from random import random,gauss
from functools import partial
from math import sin,cos

import bpy
from bpy.props import FloatProperty, IntProperty, BoolProperty, EnumProperty
from mathutils import Vector,Euler,Matrix,Quaternion

from .simplefork import simplefork, simplefork2, quadfork, bridgequads # simple skinning algorithm building blocks
from .sca import SCA, Branchpoint # the core class that implements the space colonization algorithm and the definition of a segment
from .timer import Timer

def availableGroups(self, context):
	return [(name, name, name, n) for n,name in enumerate(bpy.data.groups.keys())]

def availableGroupsOrNone(self, context):
	groups = [ ('None', 'None', 'None', 1) ]
	return groups + [(name, name, name, n+1) for n,name in enumerate(bpy.data.groups.keys())]

def availableObjects(self, context):
	return [(name, name, name, n+1) for n,name in enumerate(bpy.data.objects.keys())]

def ellipsoid(r=5,rz=5,p=Vector((0,0,8)),taper=0):
	r2=r*r
	z2=rz*rz
	if rz>r : r = rz
	while True:
		x = (random()*2-1)*r
		y = (random()*2-1)*r
		z = (random()*2-1)*r
		f = (z+r)/(2*r)
		f = 1 + f*taper if taper>=0 else (1-f)*-taper
		if f*x*x/r2+f*y*y/r2+z*z/z2 <= 1:
			yield p+Vector((x,y,z))

def pointInsideMesh(pointrelativetocursor,ob):
	# adapted from http://blenderartists.org/forum/showthread.php?195605-Detecting-if-a-point-is-inside-a-mesh-2-5-API&p=1691633&viewfull=1#post1691633
	mat = ob.matrix_world.inverted()
	orig = mat*(pointrelativetocursor+bpy.context.scene.cursor_location)
	count = 0
	axis=Vector((0,0,1))
	while True:
		location,normal,index = ob.ray_cast(orig,orig+axis*10000.0)
		if index == -1: break
		count += 1
		orig = location + axis*0.00001
	if count%2 == 0:
		return False
	return True
	
def ellipsoid2(rxy=5,rz=5,p=Vector((0,0,8)),surfacebias=1,topbias=1):
	while True:
		phi = 6.283*random()
		theta = 3.1415*(random()-0.5)
		r = random()**(surfacebias/2)
		x = r*rxy*cos(theta)*cos(phi)
		y = r*rxy*cos(theta)*sin(phi)
		st=sin(theta)
		st = (((st+1)/2)**topbias)*2-1
		z = r*rz*st
		#print(">>>%.2f %.2f %.2f "%(x,y,z))
		m = p+Vector((x,y,z))
		reject = False
		for ob in bpy.context.selected_objects:
			# probably we should check if each object is a mesh
			if pointInsideMesh(m,ob) :
				reject = True
				break
		if not reject:
			yield m

def halton3D(index):
	"""
	return a quasi random 3D vector R3 in [0,1].
	each component is based on a halton sequence. 
	quasi random is good enough for our purposes and is 
	more evenly distributed then pseudo random sequences. 
	See en.m.wikipedia.org/wiki/Halton_sequence
	"""

	def halton(index, base):
		result=0
		f=1.0/base
		I=index
		while I>0:
			result += f*(I%base)
			I=int(I/base)
			f/=base
		return result
	return Vector((halton(index,2),halton(index,3),halton(index,5)))

def insidegroup(pointrelativetocursor, group):
	if bpy.data.groups.find(group)<0 : return False
	for ob in bpy.data.groups[group].objects:
		if pointInsideMesh(pointrelativetocursor,ob):
			return True
	return False

def groupdistribution(crowngroup,shadowgroup=None,seed=0,size=Vector((1,1,1)),pointrelativetocursor=Vector((0,0,0))):
	if crowngroup == shadowgroup:
		shadowgroup = None # safeguard otherwise every marker would be rejected
	nocrowngroup = bpy.data.groups.find(crowngroup)<0
	noshadowgroup = (shadowgroup is None) or (bpy.data.groups.find(shadowgroup)<0) or (shadowgroup == 'None')
	index=100+seed
	nmarkers=0
	nyield=0
	while True:
		nmarkers+=1
		v = halton3D(index)
		v[0] *= size[0]
		v[1] *= size[1]
		v[2] *= size[2]
		v+=pointrelativetocursor
		index+=1
		insidecrown = nocrowngroup or insidegroup(v,crowngroup)
		outsideshadow = noshadowgroup or not insidegroup(v,shadowgroup)
		# if shadowgroup overlaps all or a significant part of the crowngroup
		# no markers will be yielded and we would be in an endless loop.
		# so if we yield too few correct markers we start yielding them anyway.
		lowyieldrate = (nmarkers>200) and (nyield/nmarkers < 0.01)
		if (insidecrown and outsideshadow) or lowyieldrate:
			nyield+=1
			yield v
		
def groupExtends(group):
	"""
	return a size,minimum tuple both Vector elements, describing the size and position
	of the bounding box in world space that encapsulates all objects in a group.
	"""
	bb=[]
	if bpy.data.groups.find(group) >=0 :
		for ob in bpy.data.groups[group].objects:
			rot = ob.matrix_world.to_quaternion()
			scale = ob.matrix_world.to_scale()
			translate = ob.matrix_world.translation
			for v in ob.bound_box: # v is not a vector but an array of floats
				p = ob.matrix_world * Vector(v[0:3])
				bb.extend(p[0:3])
	mx = Vector((max(bb[0::3]), max(bb[1::3]), max(bb[2::3])))
	mn = Vector((min(bb[0::3]), min(bb[1::3]), min(bb[2::3])))
	return mx-mn,mn

def createLeaves(tree, probability=0.5, size=0.5, randomsize=0.1, randomrot=0.1, maxconnections=2, bunchiness=1.0):
	p=bpy.context.scene.cursor_location
	
	verts=[]
	faces=[]
	c1=Vector((-size/10,-size/2,0))
	c2=Vector((    size,-size/2,0))
	c3=Vector((    size, size/2,0))
	c4=Vector((-size/10, size/2,0))
	t=gauss(1.0/probability,0.1)
	bpswithleaves=0
	for bp in tree.branchpoints:
		if bp.connections < maxconnections:
		
			dv = tree.branchpoints[bp.parent].v - bp.v if bp.parent else Vector((0,0,0))
			dvp = Vector((0,0,0))
			
			bpswithleaves+=1
			nleavesonbp=0
			while t<bpswithleaves:
				nleavesonbp+=1
				rx = (random()-0.5)*randomrot*6.283 # TODO vertical tilt in direction of tropism
				ry = (random()-0.5)*randomrot*6.283
				rot = Euler((rx,ry,random()*6.283),'ZXY')
				scale = 1+(random()-0.5)*randomsize
				v=c1.copy()
				v.rotate(rot)
				verts.append(v*scale+bp.v+dvp)
				v=c2.copy()
				v.rotate(rot)
				verts.append(v*scale+bp.v+dvp)
				v=c3.copy()
				v.rotate(rot)
				verts.append(v*scale+bp.v+dvp)
				v=c4.copy()
				v.rotate(rot)
				verts.append(v*scale+bp.v+dvp)
				n = len(verts)
				faces.append((n-4,n-3,n-2,n-1))
				t += gauss(1.0/probability,0.1)					 # this is not the best choice of distribution because we might get negative values especially if sigma is large
				dvp = nleavesonbp*(dv/(probability**bunchiness)) # TODO add some randomness to the offset
				
	mesh = bpy.data.meshes.new('Leaves')
	mesh.from_pydata(verts,[],faces)
	mesh.update(calc_edges=True)
	mesh.uv_textures.new()
	return mesh

def createMarkers(tree,scale=0.05):
	#not used as markers are parented to tree object that is created at the cursor position
	#p=bpy.context.scene.cursor_location
	
	verts=[]
	faces=[]

	tetraeder = [Vector((-1,1,-1)),Vector((1,-1,-1)),Vector((1,1,1)),Vector((-1,-1,1))]
	tetraeder = [v * scale for v in tetraeder]
	tfaces = [(0,1,2),(0,1,3),(1,2,3),(0,3,2)]
	
	for ep in tree.endpoints:
		verts.extend([ep + v for v in tetraeder])
		n=len(faces)
		faces.extend([(f1+n,f2+n,f3+n) for f1,f2,f3 in tfaces])
		
	mesh = bpy.data.meshes.new('Markers')
	mesh.from_pydata(verts,[],faces)
	mesh.update(calc_edges=True)
	return mesh


def createObjects(tree, parent=None, objectname=None, probability=0.5, size=0.5, randomsize=0.1, randomrot=0.1, maxconnections=2, bunchiness=1.0):

	if (parent is None) or (objectname is None) or (objectname == 'None') : return
	
	# not necessary, we parent the new objects: p=bpy.context.scene.cursor_location
	
	theobject = bpy.data.objects[objectname]
	
	t=gauss(1.0/probability,0.1)
	bpswithleaves=0
	for bp in tree.branchpoints:
		if bp.connections < maxconnections:
		
			dv = tree.branchpoints[bp.parent].v - bp.v if bp.parent else Vector((0,0,0))
			dvp = Vector((0,0,0))
			
			bpswithleaves+=1
			nleavesonbp=0
			while t<bpswithleaves:
				nleavesonbp+=1
				rx = (random()-0.5)*randomrot*6.283 # TODO vertical tilt in direction of tropism
				ry = (random()-0.5)*randomrot*6.283
				rot = Euler((rx,ry,random()*6.283),'ZXY')
				scale = size+(random()-0.5)*randomsize
				
				# add new object and parent it
				obj = bpy.data.objects.new(objectname,theobject.data)
				obj.location = bp.v+dvp
				obj.rotation_mode = 'ZXY'
				obj.rotation_euler = rot[:]
				obj.scale = [scale,scale,scale]
				obj.parent = parent
				bpy.context.scene.objects.link(obj)
				
				t += gauss(1.0/probability,0.1)					 # this is not the best choice of distribution because we might get negative values especially if sigma is large
				dvp = nleavesonbp*(dv/(probability**bunchiness)) # TODO add some randomness to the offset

def vertextend(v,dv):
	n=len(v)
	v.extend(dv)
	return tuple(range(n,n+len(dv)))

def vertcopy(loopa, v, p):
	dv=[v[i]+p for i in loopa]
	#print(loopa,p,dv)
	return vertextend(v,dv)

def bend(p0, p1, p2, loopa, loopb, verts):
	# will extend this with a tri centered at p0
	#print('bend')
	return bridgequads(loopa, loopb, verts)

def extend(p0, p1, p2, loopa, verts):
	# will extend this with a tri centered at p0
	#print('extend')
	#print(p0,p1,p2,[verts[i] for i in loopa])
	
	# both difference point upward, we extend to the second
	d1=p1-p0
	d2=p0-p2
	p=(verts[loopa[0]]+verts[loopa[1]]+verts[loopa[2]]+verts[loopa[3]])/4
	a=d1.angle(d2,0)
	if abs(a)<0.05:
		#print('small angle')
		loopb = vertcopy(loopa, verts, p0-d2/2-p)
		# all verts in loopb are displaced the same amount so no need to find the minimum distance
		n=4
		return ([(loopa[(i)%n], loopa[(i+1)%n], loopb[(i+1)%n], loopb[(i)%n]) for i in range(n)] ,loopa, loopb)

	r=d2.cross(d1)
	q=Quaternion(r,-a)
	dverts=[verts[i]-p for i in loopa]
	#print('large angle',dverts,'axis',r)
	for dv in dverts:
		dv.rotate(q)
	#print('rotated',dverts)
	for dv in dverts:
		dv+=(p0-d2/2)
	#print('moved',dverts)
	loopb=vertextend(verts,dverts)
	# none of the verts in loopb are rotated so no need to find the minimum distance
	n=4
	return ([(loopa[(i)%n], loopa[(i+1)%n], loopb[(i+1)%n], loopb[(i)%n]) for i in range(n)] ,loopa, loopb)

def nonfork(bp,parent,apex,verts,p,branchpoints):
	#print('nonfork bp    ',bp.index,bp.v,bp.loop if hasattr(bp,'loop') else None)
	#print('nonfork parent',parent.index,parent.v,parent.loop if hasattr(parent,'loop') else None)
	#print('nonfork apex  ',apex.index,apex.v,apex.loop if hasattr(apex,'loop') else None)
	if hasattr(bp,'loop'):
		if hasattr(apex,'loop'):
			#print('nonfork bend bp->apex')
			return bend(bp.v+p, parent.v+p, apex.v+p, bp.loop, apex.loop, verts)
		else:
			#print('nonfork extend bp->apex')
			faces,loop1,loop2 = extend(bp.v+p, parent.v+p, apex.v+p, bp.loop, verts)
			apex.loop = loop2
			return faces,loop1,loop2
	else:
		if hasattr(parent,'loop'):
			#print('nonfork extend from bp->parent')
			#faces,loop1,loop2 =  extend(bp.v+p, apex.v+p, parent.v+p, parent.loop, verts)
			if parent.parent is None :
				return None, None, None
			grandparent=branchpoints[parent.parent]
			faces,loop1,loop2 =  extend(grandparent.v+p, parent.v+p, bp.v+p, parent.loop, verts)
			bp.loop = loop2
			return faces,loop1,loop2
		else:
			#print('nonfork no loop')
			# neither parent nor apex already have a loop calculated
			# will fill this later ...
			return None,None,None

def endpoint(bp,parent,verts,p):
	# extrapolate to tip of branch. we do not close the tip for now
	faces,loop1,loop2 = extend(bp.v+p, parent.v+p, bp.v+(bp.v-parent.v)+p, bp.loop, verts)
	return faces,loop1,loop2

def root(bp,apex,verts,p):
	# extrapolate non-forked roots
	faces,loop1,loop2 = extend(bp.v+p, bp.v-(apex.v-bp.v)+p, apex.v+p, bp.loop, verts)
	apex.loop=loop2
	return faces,loop1,loop2

def skin(aloop, bloop, faces):
	n = len(aloop)
	for i in range(n):
		faces.append((aloop[i],aloop[(i+1)%n],bloop[(i+1)%n],bloop[i]))
			
def createGeometry(tree, power=0.5, scale=0.01, addleaves=False, pleaf=0.5, leafsize=0.5, leafrandomsize=0.1, leafrandomrot=0.1,
	nomodifiers=True, skinmethod='NATIVE', subsurface=False,
	maxleafconnections=2, bleaf=1.0,
	timeperf=True):
	
	timings = Timer()
	
	p=bpy.context.scene.cursor_location
	verts=[]
	edges=[]
	faces=[]
	radii=[]
	roots=set()
	
	# Loop over all branchpoints and create connected edges
	for n,bp in enumerate(tree.branchpoints):
		verts.append(bp.v+p)
		radii.append(bp.connections)
		bp.index=n
		if not (bp.parent is None) :
			edges.append((len(verts)-1,bp.parent))
		else :
			nv=len(verts)
			roots.add(nv-1)
	
	timings.add('skeleton')
	
	# native skinning method
	if nomodifiers == False and skinmethod == 'NATIVE': 
		# add a quad edge loop to all roots
		for r in roots:
			rootp=verts[r]
			nv=len(verts)
			radius = 0.7071*((tree.branchpoints[r].connections+1)**power)*scale
			verts.extend( [rootp+Vector((-radius,-radius,0)),rootp+Vector((radius,-radius,0)),rootp+Vector((radius,radius,0)),rootp+Vector((-radius,radius,0))])
			tree.branchpoints[r].loop=(nv,nv+1,nv+2,nv+3)
			#print('root verts',tree.branchpoints[r].loop)
			#faces.append((nv,nv+1,nv+2))
			edges.extend([(nv,nv+1),(nv+1,nv+2),(nv+2,nv+3),(nv+3,nv)])
		
		# skin all forked branchpoints, no attempt is yet made to adjust the radius
		forkfork=set()
		for bpi,bp in enumerate(tree.branchpoints):
			if not( bp.apex is None or bp.shoot is None) :
				apex = tree.branchpoints[bp.apex]
				shoot = tree.branchpoints[bp.shoot]
				p0 = bp.v
				r0 = ((bp.connections+1)**power)*scale
				p2 = apex.v
				r2 = ((apex.connections+1)**power)*scale
				p3 = shoot.v
				r3 = ((shoot.connections+1)**power)*scale
				
				if bp.parent is not None:
					parent = tree.branchpoints[bp.parent] 
					p1 = parent.v
					r1 = (parent.connections**power)*scale
				else:
					p1 = p0-(p2-p0)
					r1=r0
				
				skinverts,skinfaces = quadfork(p0,p1,p2,p3,r0,r1,r2,r3)
				nv=len(verts)
				verts.extend([v+p for v in skinverts])
				faces.extend([ tuple(v+nv for v in f) for f in skinfaces])
				
				# the vertices of the quads at the end of the internodes are returned as the first 12 vertices of a total of 22
				# we store them for reuse by non-forked internodes but first check if we have a fork to fork connection
				nv=len(verts)
				if hasattr(bp,'loop') and not (bpi in forkfork) : # already assigned by another fork
					faces.extend(bridgequads(bp.loop, [nv-22,nv-21,nv-20,nv-19], verts )[0])
					forkfork.add(bpi)
				else:
					bp.loop = [nv-22,nv-21,nv-20,nv-19]
					
				if hasattr(apex,'loop') and not (bp.apex in forkfork) : # already assigned by another fork but not yet skinned
					faces.extend(bridgequads(apex.loop, [nv-18,nv-17,nv-16,nv-15], verts )[0])
					forkfork.add(bp.apex)
				else:
					apex.loop = [nv-18,nv-17,nv-16,nv-15]
					
				if hasattr(shoot,'loop') and not (bp.shoot in forkfork) : # already assigned by another fork but not yet skinned
					faces.extend(bridgequads(shoot.loop, [nv-14,nv-13,nv-12,nv-11], verts )[0])
					forkfork.add(bp.shoot)
				else:
					shoot.loop = [nv-14,nv-13,nv-12,nv-11]
		
		# skin the roots that are not forks
		for r in roots:
			bp=tree.branchpoints[r]
			if bp.apex is not None and bp.parent is None and bp.shoot is None:
				bfaces, apexloop, parentloop = root(bp,tree.branchpoints[bp.apex],verts,p)
				if bfaces is not None:
					faces.extend(bfaces)
				
		# skin all non-forking branchpoints, that is those not a root or and endpoint
		skinnednonforks=set()
		start=-1
		while(start != len(skinnednonforks)):
			start = len(skinnednonforks)
			#print('-'*20,start)
			for bp in tree.branchpoints:
				if bp.shoot is None and not (bp.parent is None or bp.apex is None or bp in skinnednonforks) :
					bfaces, apexloop, parentloop = nonfork(bp,tree.branchpoints[bp.parent],tree.branchpoints[bp.apex],verts,p,tree.branchpoints)
					if bfaces is not None:
						#print(bfaces,apexloop,parentloop)
						faces.extend(bfaces)
						skinnednonforks.add(bp)
		
		# skin endpoints
		for bp in tree.branchpoints:
			if bp.apex is None and bp.parent is not None:
				bfaces, apexloop, parentloop = endpoint(bp,tree.branchpoints[bp.parent],verts,p)
				if bfaces is not None:
					faces.extend(bfaces)
	# end of native skinning section
	timings.add('nativeskin')
	
	# create the tree mesh
	mesh = bpy.data.meshes.new('Tree')
	mesh.from_pydata(verts, edges, faces)
	mesh.update(calc_edges=True)
	
	# create the tree object an make it the only selected and active object in the scene
	obj_new = bpy.data.objects.new(mesh.name, mesh)
	base = bpy.context.scene.objects.link(obj_new)
	for ob in bpy.context.scene.objects:
		ob.select = False
	base.select = True
	bpy.context.scene.objects.active = obj_new
	bpy.ops.object.origin_set(type='ORIGIN_CURSOR')
	
	timings.add('createmesh')
	
	# add a subsurf modifier to smooth the branches 
	if nomodifiers == False:
		if subsurface:
			bpy.ops.object.modifier_add(type='SUBSURF')
			bpy.context.active_object.modifiers[0].levels = 1
			bpy.context.active_object.modifiers[0].render_levels = 1

		# add a skin modifier
		if skinmethod == 'BLENDER':
			bpy.ops.object.modifier_add(type='SKIN')
			bpy.context.active_object.modifiers[-1].use_smooth_shade=True
			bpy.context.active_object.modifiers[-1].use_x_symmetry=True
			bpy.context.active_object.modifiers[-1].use_y_symmetry=True
			bpy.context.active_object.modifiers[-1].use_z_symmetry=True

			skinverts = bpy.context.active_object.data.skin_vertices[0].data

			for i,v in enumerate(skinverts):
				v.radius = [(radii[i]**power)*scale,(radii[i]**power)*scale]
				if i in roots:
					v.use_root = True
			
			# add an extra subsurf modifier to smooth the skin
			bpy.ops.object.modifier_add(type='SUBSURF')
			bpy.context.active_object.modifiers[-1].levels = 1
			bpy.context.active_object.modifiers[-1].render_levels = 2
	
	timings.add('modifiers')

	# create the leaves object
	if addleaves:
		mesh = createLeaves(tree, pleaf, leafsize, leafrandomsize, leafrandomrot, maxleafconnections, bleaf)
		obj_leaves = bpy.data.objects.new(mesh.name, mesh)
		base = bpy.context.scene.objects.link(obj_leaves)
		obj_leaves.parent = obj_new
		bpy.context.scene.objects.active = obj_leaves
		bpy.ops.object.origin_set(type='ORIGIN_CURSOR')
		bpy.context.scene.objects.active = obj_new
	
	timings.add('leaves')
	
	if timeperf:
		print(timings)
		
	return obj_new
	
class SCATree(bpy.types.Operator):
	bl_idname = "mesh.sca_tree"
	bl_label = "SCATree"
	bl_options = {'REGISTER', 'UNDO', 'PRESET'}

	internodeLength = FloatProperty(name="Internode Length",
					description="Internode length in Blender Units",
					default=0.75,
					min=0.01,
					soft_max=3.0,
					subtype='DISTANCE',
					unit='LENGTH')
	killDistance = FloatProperty(name="Kill Distance",
					description="Kill Distance as a multiple of the internode length",
					default=3,
					min=0.01,
					soft_max=100.0)
	influenceRange = FloatProperty(name="Influence Range",
					description="Influence Range as a multiple of the internode length",
					default=15,
					min=0.01,
					soft_max=100.0)
	tropism = FloatProperty(name="Tropism",
					description="The tendency of branches to bend up or down",
					default=0,
					min=-1.0,
					soft_max=1.0)
	power = FloatProperty(name="Power",
					description="Tapering power of branch connections",
					default=0.3,
					min=0.01,
					soft_max=1.0)
	scale = FloatProperty(name="Scale",
					description="Branch size",
					default=0.01,
					min=0.0001,
					soft_max=1.0)
	
	# the group related properties are not saved as presets because on reload no groups with the same names might exist, causing an exception
	useGroups = BoolProperty(name="Use object groups",
					options={'ANIMATABLE','SKIP_SAVE'},
					description="Use groups of objects to specify marker distribution",
					default=False)
	
	crownGroup = EnumProperty(items=availableGroups,
					options={'ANIMATABLE','SKIP_SAVE'},
					name='Crown Group',
					description='Group of objects that specify crown shape')
	
	shadowGroup = EnumProperty(items=availableGroupsOrNone,
					options={'ANIMATABLE','SKIP_SAVE'},
					name='Shadow Group',
					description='Group of objects subtracted from the crown shape')
	
	exclusionGroup = EnumProperty(items=availableGroupsOrNone,
					options={'ANIMATABLE','SKIP_SAVE'},
					name='Exclusion Group',
					description='Group of objects that will not be penetrated by growing branches')
	
	useTrunkGroup = BoolProperty(name="Use trunk group", 
					options={'ANIMATABLE','SKIP_SAVE'},
					description="Use the locations of a group of objects to specify trunk starting points instead of 3d cursor",
					default=False)
	
	trunkGroup = EnumProperty(items=availableGroups,
					options={'ANIMATABLE','SKIP_SAVE'},
					name='Trunk Group',
					description='Group of objects whose locations specify trunk starting points')
	
	crownSize = FloatProperty(name="Crown Size",
					description="Crown size",
					default=5,
					min=1,
					soft_max=29)
	crownShape = FloatProperty(name="Crown Shape",
					description="Crown shape",
					default=1,
					min=0.2,
					soft_max=5)
	crownOffset = FloatProperty(name="Crown Offset",
					description="Crown offset (the length of the bole)",
					default=3,
					min=0,
					soft_max=20.0)
	surfaceBias = FloatProperty(name="Surface Bias",
					description="Surface bias (how much markers are favored near the surface)",
					default=1,
					min=-10,
					soft_max=10)
	topBias = FloatProperty(name="Top Bias",
					description="Top bias (how much markers are favored near the top)",
					default=1,
					min=-10,
					soft_max=10)
	randomSeed = IntProperty(name="Random Seed",
					description="The seed governing random generation",
					default=0,
					min=0)
	maxIterations = IntProperty(name="Maximum Iterations",
					description="The maximum number of iterations allowed for tree generation",
					default=40,
					min=0)
	numberOfEndpoints = IntProperty(name="Number of Endpoints",
					description="The number of endpoints generated in the growing volume",
					default=100,
					min=0)
	newEndPointsPer1000 = IntProperty(name="Number of new Endpoints",
					description="The number of new endpoints generated in the growing volume per thousand iterations",
					default=0,
					min=0)
	maxTime = FloatProperty(name="Maximum Time",
					description=("The maximum time to run the generation for "
								"in seconds/generation (0.0 = Disabled). Currently ignored"),
					default=0.0,
					min=0.0,
					soft_max=10)
	pLeaf = FloatProperty(name="Leaves per internode",
					description=("The average number of leaves per internode"),
					default=0.5,
					min=0.0,
					soft_max=4)
	bLeaf = FloatProperty(name="Leaf clustering",
					description=("How much leaves cluster to the end of the internode"),
					default=1,
					min=1,
					soft_max=4)
	leafSize = FloatProperty(name="Leaf Size",
					description=("The leaf size"),
					default=0.5,
					min=0.0,
					soft_max=1)
	leafRandomSize = FloatProperty(name="Leaf Random Size",
					description=("The amount of randomness to add to the leaf size"),
					default=0.1,
					min=0.0,
					soft_max=10)
	leafRandomRot = FloatProperty(name="Leaf Random Rotation",
					description=("The amount of random rotation to add to the leaf"),
					default=0.1,
					min=0.0,
					soft_max=1)
	leafMaxConnections = IntProperty(name="Max Connections",
					description="The maximum number of connections of an internode elegible for a leaf",
					default=2,
					min=0)
	addLeaves = BoolProperty(name="Add Leaves", default=False)
	
	objectName = EnumProperty(items=availableObjects,
					options={'ANIMATABLE','SKIP_SAVE'},
					name='Object Name',
					description='Name of additional objects to duplicate at the branchpoints')
	pObject = FloatProperty(name="Objects per internode",
					description=("The average number of objects per internode"),
					default=0.3,
					min=0.0,
					soft_max=1)
	bObject = FloatProperty(name="Object clustering",
					description=("How much objects cluster to the end of the internode"),
					default=1,
					min=1,
					soft_max=4)
	objectSize = FloatProperty(name="Object Size",
					description=("The object size"),
					default=1,
					min=0.0,
					soft_max=2)
	objectRandomSize = FloatProperty(name="Object Random Size",
					description=("The amount of randomness to add to the object size"),
					default=0.1,
					min=0.0,
					soft_max=10)
	objectRandomRot = FloatProperty(name="Object Random Rotation",
					description=("The amount of random rotation to add to the object"),
					default=0.1,
					min=0.0,
					soft_max=1)
	objectMaxConnections = IntProperty(name="Max Connections for Object",
					description="The maximum number of connections of an internode elegible for a object",
					default=1,
					min=0)
	addObjects = BoolProperty(name="Add Objects", default=False)
	
	updateTree = BoolProperty(name="Update Tree", default=False)
	
	noModifiers = BoolProperty(name="No Modifers", default=True)
	subSurface = BoolProperty(name="Sub Surface", default=False, description="Add subsurface modifier to trunk skin")
	skinMethod = EnumProperty(items=[('NATIVE','Native','Built in skinning method',1),('BLENDER','Skin modifier','Use Blenders skin modifier',2)],
					options={'ANIMATABLE','SKIP_SAVE'},
					name='Skinning method',
					description='How to add a surface to the trunk skeleton')
	
	showMarkers = BoolProperty(name="Show Markers", default=False)
	markerScale = FloatProperty(name="Marker Scale",
					description=("The size of the markers"),
					default=0.05,
					min=0.001,
					soft_max=0.2)
	timePerformance = BoolProperty(name="Time performance", default=False, description="Show duration of generation steps on console")
	
	@classmethod
	def poll(self, context):
		# Check if we are in object mode
		return context.mode == 'OBJECT'

	def execute(self, context):
		
		if not self.updateTree:
			return {'PASS_THROUGH'}

		timings=Timer()
		
		# necessary otherwize ray casts toward these objects may fail. However if nothing is selected, we get a runtime error ...
		try:
			bpy.ops.object.mode_set(mode='EDIT', toggle=False)
			bpy.ops.object.mode_set(mode='OBJECT', toggle=False)
		except RuntimeError:
			pass
		
		if self.useGroups:
			size,minp = groupExtends(self.crownGroup)
			volumefie=partial(groupdistribution,self.crownGroup,self.shadowGroup,self.randomSeed,size,minp-bpy.context.scene.cursor_location)
		else:
			volumefie=partial(ellipsoid2,self.crownSize*self.crownShape,self.crownSize,Vector((0,0,self.crownSize+self.crownOffset)),self.surfaceBias,self.topBias)
		
		startingpoints = []
		if self.useTrunkGroup:
			if bpy.data.groups.find(self.trunkGroup)>=0 :
				for ob in bpy.data.groups[self.trunkGroup].objects :
					p = ob.location - context.scene.cursor_location
					startingpoints.append(Branchpoint(p,None))
		
		timings.add('scastart')
		sca = SCA(NBP = self.maxIterations,
			NENDPOINTS=self.numberOfEndpoints,
			d=self.internodeLength,
			KILLDIST=self.killDistance,
			INFLUENCE=self.influenceRange,
			SEED=self.randomSeed,
			TROPISM=self.tropism,
			volume=volumefie,
			exclude=lambda p: insidegroup(p, self.exclusionGroup),
			startingpoints=startingpoints)
		timings.add('sca')
			
		if self.showMarkers:
			mesh = createMarkers(sca, self.markerScale)
			obj_markers = bpy.data.objects.new(mesh.name, mesh)
			base = bpy.context.scene.objects.link(obj_markers)
		timings.add('showmarkers')
		
		sca.iterate2(newendpointsper1000=self.newEndPointsPer1000,maxtime=self.maxTime)
		timings.add('iterate')
		
		obj_new=createGeometry(sca,self.power,self.scale,self.addLeaves, self.pLeaf, self.leafSize, self.leafRandomSize, self.leafRandomRot,
			self.noModifiers, self.skinMethod, self.subSurface,
			self.leafMaxConnections, self.bLeaf,
			self.timePerformance)
		
		timings.add('objcreationstart')
		if self.addObjects:
			createObjects(sca, obj_new,
				objectname=self.objectName,
				probability=self.pObject,
				size=self.objectSize,
				randomsize=self.objectRandomSize,
				randomrot=self.objectRandomRot,
				maxconnections=self.objectMaxConnections,
				bunchiness=self.bObject)
		timings.add('objcreation')
		
		if self.showMarkers:
			obj_markers.parent = obj_new
		
		self.updateTree = False
		
		if self.timePerformance:
			timings.add('Total')
			print(timings)
			
		return {'FINISHED'}

	def draw(self, context):
		layout = self.layout

		layout.prop(self, 'updateTree', icon='MESH_DATA')

		columns=layout.row()
		col1=columns.column()
		col2=columns.column()
		
		box = col1.box()
		box.label("Generation Settings:")
		box.prop(self, 'randomSeed')
		box.prop(self, 'maxIterations')

		box = col1.box()
		box.label("Shape Settings:")
		box.prop(self, 'numberOfEndpoints')
		box.prop(self, 'internodeLength')
		box.prop(self, 'influenceRange')
		box.prop(self, 'killDistance')
		box.prop(self, 'power')
		box.prop(self, 'scale')
		box.prop(self, 'tropism')
		
		newbox = col2.box()
		newbox.label("Crown shape")
		newbox.prop(self,'useGroups')
		if self.useGroups:
			newbox.label("Object groups defining crown shape")
			groupbox = newbox.box()
			groupbox.prop(self,'crownGroup')
			groupbox = newbox.box()
			groupbox.alert=(self.shadowGroup == self.crownGroup)
			groupbox.prop(self,'shadowGroup')
			groupbox = newbox.box()
			groupbox.alert=(self.exclusionGroup == self.crownGroup)
			groupbox.prop(self,'exclusionGroup')
		else:
			newbox.label("Simple ellipsoid defining crown shape")
			newbox.prop(self, 'crownSize')
			newbox.prop(self, 'crownShape')
			newbox.prop(self, 'crownOffset')
		newbox = col2.box()
		newbox.prop(self,'useTrunkGroup')
		if self.useTrunkGroup:
			newbox.prop(self,'trunkGroup')
			
		box.prop(self, 'surfaceBias')
		box.prop(self, 'topBias')
		box.prop(self, 'newEndPointsPer1000')
		
		box = col2.box()
		box.label("Skin options:")
		box.prop(self, 'noModifiers')
		if not self.noModifiers:
			box.prop(self,'skinMethod')
			box.prop(self,'subSurface')
		
		layout.prop(self, 'addLeaves', icon='MESH_DATA')
		if self.addLeaves:
			box = layout.box()
			box.label("Leaf Settings:")
			box.prop(self,'pLeaf')
			box.prop(self,'bLeaf')
			box.prop(self,'leafSize') 
			box.prop(self,'leafRandomSize') 	
			box.prop(self,'leafRandomRot')
			box.prop(self,'leafMaxConnections')
		
		layout.prop(self,'addObjects', icon='MESH_DATA')
		if self.addObjects:
			box = layout.box()
			box.label("Object Settings:")
			box.prop(self,'objectName')
			box.prop(self,'pObject')
			box.prop(self,'bObject')
			box.prop(self,'objectSize')
			box.prop(self,'objectRandomSize')
			box.prop(self,'objectRandomRot')
			box.prop(self,'objectMaxConnections')

		box = layout.box()
		box.label("Debug Settings:")
		box.prop(self, 'showMarkers')
		if self.showMarkers:
			box.prop(self, 'markerScale')
		box.prop(self, 'timePerformance')
		
def menu_func(self, context):
	self.layout.operator(SCATree.bl_idname, text="Add Tree to Scene",
												icon='PLUGIN').updateTree = True

def register():
	bpy.utils.register_module(__name__)
	bpy.types.INFO_MT_mesh_add.append(menu_func)


def unregister():
	bpy.types.INFO_MT_mesh_add.remove(menu_func)
	bpy.utils.unregister_module(__name__)


if __name__ == "__main__":
	register()