#!BPY

#"""
#Name: 'LoopTools 2.4'
#Blender: 249
#Group: 'Mesh'
#Tooltip: 'Various tools to aid modelling that involves loops'
#"""

# script information
__author__ = 'Bartius Crouch'
__version__ = '2.4 2009-08-12'
__url__ = ["Script's homepage, http://sites.google.com/site/bartiuscrouch/scripts/looptools", "Support forum, http://blenderartists.org/forum/showthread.php?t=148728"]
__email__ = ["Bartius Crouch, bartius.crouch:gmail*com"]
__bpydoc__ = """\
A collection of tools to aid modelling involving loops.<br>
<br>
Circle:<br>
The selected vertices will be moved so they are in the shape of a circle<br>
If only 1 vertex is selected, the surrounding vertices will be operated on<br>
Curve:<br>
The selected vertices on an edgeloop will be used to caculate a smooth curve that passes through them. Non-selected vertices will be moved so they are located on the curve.<br>
If all vertices on an edgeloop are selected, the script will operate on all edgeloops that are perpendicular to it.<br>
Relax:<br>
Smooth the vertices in the current selection.<br>
Space:<br>
Move the vertices in the selection, so that the distances between them are more equally distributed.<br>
<br>
Visit the script's homepage for a more extensive documentation, including screencasts on how to use the tools.
"""

# ------------------------------------------------------------------------
# 
# LoopTools 2.4 - Various tools to aid modelling that involves loops
# Copyright (C) 2009: Bartius Crouch
# 
# 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 3 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, see <http://www.gnu.org/licenses/>.
# 
# ------------------------------------------------------------------------

import Blender
from Blender import *
import bpy
try:
	import webbrowser
	browser = True
except:
	browser = False

# parameter for testing
debug = [False, False] # general, edge loop visualisuation

# parameter for speed vs. accuracy of the tools
# drops are: 0: nothing | 1: circle, extended cycling | 2: circle, basic cycling | 4: all tools, modifier support
tool_speed = 0 # 0 = full accuracy, 7 = max speed

##################################################################
############# General Functions ##################################
##################################################################

# initialise data
def initialise():
	editmode = Window.EditMode()
	if editmode:
		Window.EditMode(0)
	Window.EditMode(1)
	scn = bpy.data.scenes.active
	ob = scn.objects.active
	if not ob:
		terminate("Error%t|No object selected", editmode)
		return editmode, False, False, False, False, False
	if ob.type != 'Mesh':
		terminate("Error%t|Active object isn't a mesh", editmode)
		return editmode, ob, False, False, False, False
	me = ob.getData(False, True)
	Window.EditMode(0)
	Window.EditMode(1)
	vsel = [v for v in me.verts.selected() if me.verts[v].hide!=1]
	edsel = [ed for ed in me.edges.selected() if (me.edges[ed].v1.hide!=1 and me.edges[ed].v2.hide!=1 and me.edges[ed].sel)]
	fsel = [f for f in me.faces.selected() if me.faces[f].hide!=1 and me.faces[f].sel]
	return editmode, ob, me, vsel, edsel, fsel

# being tidy when stopping
def terminate(msg, editmode):
	Window.EditMode(editmode)
	if msg:
		Draw.PupMenu(msg)

# Create a dictionary with the vert index as key and edge-keys as value
def getVertEdges(me):
	vert_edges = dict([(v.index, []) for v in me.verts if v.hide!=1])
	for ed in me.edges:
		for v in ed.key:
			if vert_edges.has_key(ed.key[0]) and vert_edges.has_key(ed.key[1]):
				vert_edges[v].append(ed.key)
	return vert_edges

# Create a dictionary with the vert index as key and face index as value
def getVertFaces(me):
	vert_faces = dict([(v.index, []) for v in me.verts if v.hide!=1])
	for f in me.faces:
		if f.hide != 1:
			for v in f.verts:
				if v.hide != 1:
					vert_faces[v.index].append(f.index)
	return vert_faces

# Create a dictionary with the edge-key as key and faces as value
def getEdgeFaces(me):
	edge_faces = dict([(ed.key, []) for ed in me.edges if (ed.v1.hide!=1 and ed.v2.hide!=1)])
	for f in me.faces:
		for key in f.edge_keys:
			if edge_faces.has_key(key) and f.hide!=1:
				edge_faces[key].append(f.index)
	return edge_faces

# returns all edge loops that a vertex is part of
def getLoops(me, v1, vert_edges, edge_faces):
	# making sure that the dictionaries are available
	if not vert_edges:
		vert_edges = getVertEdges(me)
	if not edge_faces:
		edge_faces = getEdgeFaces(me)
	
	ed_used = [] # starting edges that are already part of a loop that is found
	edgeloops = [] # to store the final results in
	for ed in vert_edges[v1]:
		if ed in ed_used:
			continue
		
		vloop = [] # contains all verts of the loop
		poles = [] # contains the poles at the ends of the loop
		circle = False # tells if loop is circular
		n = 0 # to differentiate between the start and the end of the loop
		
		for m in ed:
			n+=1
			active_ed = ed
			active_v  = m
			if active_v not in vloop:
				vloop.insert(0,active_v)
			else:
				break
			stillGrowing = True
			while stillGrowing:
				stillGrowing = False
				active_f = edge_faces[active_ed]
				new_ed = vert_edges[active_v]
				if len(new_ed)<3:
					break
				if len(new_ed)>4:
					# detect poles and stop growing
					if n>1:
						poles.insert(0,vloop.pop(0))
					else:
						poles.append(vloop.pop(-1))
					break
				for i in new_ed:
					eliminate = False # if edge shares face, it has to be eliminated
					for j in edge_faces[i]:
						if j in active_f:
							eliminate = True
							break
					if not eliminate: # it's the next edge in the loop
						stillGrowing = True
						active_ed = i
						if active_ed in vert_edges[v1]:
							ed_used.append(active_ed)
						for k in active_ed:
							if k != active_v:
								if k not in vloop:
									if n>1:
										vloop.insert(0,k)
									else:
										vloop.append(k)
									active_v = k
									break
								else:
									stillGrowing = False # we've come full circle
									circle = True
						break
		edgeloops.append([vloop, poles, circle])
	return edgeloops, vert_edges, edge_faces

# more information is needed to pick correct edge loop
def additionalVertex(origin, editmode, ob, me_orig, me, me_mapping, vsel, edgeloops):
	buttons[origin] = True
	reg = {}
	reg['origin'] = origin
	reg['editmode'] = editmode
	reg['ob'] = ob
	reg['me_orig'] = me_orig
	reg['me'] = me
	reg['me_mapping'] = me_mapping
	reg['vsel'] = vsel
	reg['edgeloops'] = edgeloops
	Registry.SetKey('LoopTools', reg, False)
	Draw.Draw()
	Draw.PupMenu("Extra information needed to determine correct edge loop%t|\
Please select an additional vertex that is located on the edge loop")
	Draw.Redraw()

# continue script with the extra user information
def newAdditionalVertex():
	buttons['curve_add'] = False
	buttons['relax_add'] = False
	buttons['space_add'] = False
	Draw.Redraw()
	# reading information from the registry
	reg = Registry.GetKey('LoopTools', False)
	Registry.RemoveKey('LoopTools')
	if reg:
		try:
			origin = reg['origin']
			editmode = reg['editmode']
			ob = reg['ob']
			me_orig = reg['me_orig']
			me = reg['me']
			me_mapping = reg['me_mapping']
			vsel = reg['vsel']
			edgeloops = reg['edgeloops']
		except:
			Draw.PupMenu("Error%t|Registry keys got corrupted")
	else:
		Draw.PupMenu("Error%t|Information couldn't be retrieved from registry")
	
	# check if we got a correct input and find unique edgeloop
	Window.EditMode(0)
	vsel_new = me.verts.selected()
	vsel_extra = []
	for v in vsel_new:
		if v not in vsel:
			vsel_extra.append(v)
	if len(vsel_extra)==0:
		terminate("Error%t|No additional vertex selected", editmode)
		return
	for v in vsel_extra:
		wrongloops = []
		for loop in edgeloops:
			if v not in loop[0] and v not in loop[1]:
				wrongloops.append(loop)
		if len(wrongloops) == len(edgeloops):
			if len(edgeloops)==1:
				terminate("Error%t|Additional selection is contradictory", editmode)
			else:
				terminate("Error%t|Additional selection not on edge loop", editmode)
			return
		for loop in wrongloops:
			edgeloops.remove(loop)
	if len(edgeloops)>1:
		terminate("Error%t|Additional selection doesn't result in a unique edge loop", editmode)
		return
	me.sel = False
	for v in vsel:
		me.verts[v].sel = True
	if origin == 'curve_add':
		curveloop([editmode, ob, me_orig, me, me_mapping, vsel, edgeloops, 0])
	elif origin == 'relax_add':
		relaxloop([editmode, ob, me_orig, me, me_mapping, vsel, edgeloops])
	elif origin == 'space_add':
		spaceloop([editmode, ob, me_orig, me, me_mapping, vsel, edgeloops])

# user aborted action
def cancelAdditionalVertex():
	buttons['curve_add'] = False
	buttons['relax_add'] = False
	buttons['space_add'] = False
	Registry.RemoveKey('LoopTools')
	Draw.Redraw()

# calculates natural cubic splines through all given knots
def calcCubicSplines(me, tknots, knots):
	# hack for circular loops
	if knots[0] == knots[-1] and len(knots)>1:
		circular = True
		knew1 = []
		for k in range(-1,-5,-1):
			if k-1<-len(knots):
				k+=len(knots)
			knew1.append(knots[k-1])
		knew2 = []
		for k in range(4):
			if k+1>len(knots)-1:
				k-= len(knots)
			knew2.append(knots[k+1])
		for k in knew1:
			knots.insert(0,k)
		for k in knew2:
			knots.append(k)
		tnew1 = []
		total1 = 0
		for t in range(-1,-5,-1):
			if t-1<-len(tknots):
				t+=len(tknots)
			total1 += tknots[t]-tknots[t-1]
			tnew1.append(tknots[0]-total1)
		tnew2 = []
		total2 = 0
		for t in range(4):
			if t+1>len(tknots)-1:
				t-= len(tknots)
			total2 += tknots[t+1]-tknots[t]
			tnew2.append(tknots[-1]+total2)
		for t in tnew1:
			tknots.insert(0,t)
		for t in tnew2:
			tknots.append(t)
	else:
		circular = False
	# end of hack
	
	n = len(knots)
	if n<2:
		return False
	x = []
	for t in tknots:
		x.append(float(t))
	locs = []
	for k in knots:
		locs.append(me.verts[k].co[:])
	result = []
	for j in range(3):
		a = []
		for i in locs:
			a.append(float(i[j]))
		h = []
		for i in range(n-1):
			h.append(x[i+1]-x[i])
		q = [False]
		for i in range(1,n-1):
			q.append(3.0/h[i]*(a[i+1]-a[i])-3.0/h[i-1]*(a[i]-a[i-1]))
		l = [1.0]
		u = [0.0]
		z = [0.0]
		for i in range(1,n-1):
			l.append(2.0*(x[i+1]-x[i-1])-h[i-1]*u[i-1])
			u.append(h[i]/l[i])
			z.append((q[i]-h[i-1]*z[i-1])/l[i])
		l.append(1.0)
		z.append(0.0)
		b = [False for i in range(n-1)]
		c = [False for i in range(n)]
		d = [False for i in range(n-1)]
		c[n-1] = 0.0
		for i in range(n-2,-1,-1):
			c[i] = z[i]-u[i]*c[i+1]
			b[i] = (a[i+1]-a[i])/h[i]-h[i]*(c[i+1]+2.0*c[i])/3.0
			d[i] = (c[i+1]-c[i])/(3.0*h[i])
		for i in range(n-1):
			result.append([a[i], b[i], c[i], d[i], x[i]])
	s = []
	for i in range(len(knots)-1):
		s.append([result[i], result[i+n-1], result[i+(n-1)*2]])
	if circular: # cleaning up after hack
		knots = knots[4:-4]
		tknots = tknots[4:-4]
	return s

# calculates linear splines through all given knots
def calcLinearSplines(me, tknots, knots):
	s = []
	for i in range(len(knots)-1):
		a = me.verts[knots[i]].co
		b = me.verts[knots[i+1]].co
		d = b-a
		t = tknots[i]
		u = tknots[i+1]-t
		s.append([a, d, t, u]) # [locStart, locDif, tStart, tDif]
	return s

# Create a dictionary with connection information between faces
def getConnectedFaces(me):
	edge_faces = getEdgeFaces(me)
	connected_faces = dict([(f.index, []) for f in me.faces if f.hide!=1])
	for f in me.faces:
		if f.hide==1:
			continue
		for key in f.edge_keys:
			for face in edge_faces[key]:
				connected_faces[f.index].append(face)
	return connected_faces

# turns a list with edge lists into a list with vertex lists
def edgesToVerts(me, edgeloops):
	vertloops = []
	for edges in edgeloops:
		loop = []
		for key in me.edges[edges[0]].key:
			loop.append(key)
		if len(edges)>1:
			if loop[1] not in me.edges[edges[1]].key:
				loop.reverse()
		for ed in edges[1:]:
			for key in me.edges[ed].key:
				if key not in loop:
					circular = False
					loop.append(key)
					break
				circular = True
		vertloops.append([loop[:], circular])
	return vertloops

# turns a list with vertex lists into a list with edge lists
def vertsToEdges(me, vertloops):
	edgeloops = []
	
	for loop in vertloops:
		edges = []
		for i in range(len(loop[0])-1):
			key = [loop[0][i], loop[0][i+1]]
			key.sort()
			edges.append((key[0], key[1]))
		if loop[1]: # circular
			key = [loop[0][-1], loop[0][0]]
			key.sort()
			edges.append((key[0], key[1]))
		edgeloops.append([edges, loop[1]])
	
	return edgeloops

# returns a list with selected vertices that are connected
def connectedSelections(me, edsel):
	# helping dictionary to create the dictionary we actually need
	vert_edges = dict([(v.index, []) for v in me.verts if v.hide!=1])
	for ed in me.edges:
		if ed.v1.hide!=1 and ed.v2.hide!=1:
			for key in ed.key:
				vert_edges[key].append(ed.index)
			
	# dictionary with the connection data between edges
	edge_edges = dict([(ed.index, []) for ed in me.edges if (ed.v1.hide!=1 and ed.v2.hide!=1)])
	for ed in me.edges:
		if ed.v1.hide!=1 and ed.v2.hide!=1:
			for key in ed.key:
				for con_ed in vert_edges[key]:
					if con_ed != ed.index: # an edge isn't connected to itself
						edge_edges[ed.index].append(con_ed)
	
	# find connected edges and put them in the correct order
	edge_loops = []
	edge_used = [edsel[0]]
	for ed in edsel:
		if ed in edge_used and ed!= edsel[0]:
			continue
		loop = [ed]
		edge_forbidden = edge_used[:]
		bothsides = False
		stillgrowing = True
		while stillgrowing:
			stillgrowing = False
			for con_ed in edge_edges[loop[-1]]:
				if con_ed in edsel and con_ed not in loop and con_ed not in edge_forbidden:
					stillgrowing = True
					edge_used.append(con_ed)
					edge_forbidden = edge_used#+edge_edges[loop[-1]]
					loop.append(con_ed)
					break
			if not stillgrowing:
				if bothsides:
					if len(loop)>1:
						edge_loops.append(loop[:])
				else:
					stillgrowing = True
					bothsides = True
					loop.reverse()
	
	# from the connected edges, build lists of verts
	vertloops = edgesToVerts(me, edge_loops)
	
	return vertloops

# returns a list of all loops parallel to the input, input included
def parallelLoops(vertloops, me, vsel, editmode):
	connected_faces = getConnectedFaces(me)
	edge_faces = getEdgeFaces(me)
	edgeloops = vertsToEdges(me, vertloops)
	all_edgeloops = []
	has_branches = False

	for loop in edgeloops:
		all_edgeloops.append(loop[0])
		newloops = [loop[0]]
		verts_used = []
		for edge in loop[0]:
			if edge[0] not in verts_used:
				verts_used.append(edge[0])
			if edge[1] not in verts_used:
				verts_used.append(edge[1])
		
		while len(newloops)>0:
			side_a = []
			side_b = []
			for i in newloops[-1]:
				forbidden_side = False
				if not edge_faces.has_key(i): # weird input with branches
					has_branches = True
					break
				for face in edge_faces[i]:
					if len(side_a) == 0 and forbidden_side != 'a':
						side_a.append(face)
						if forbidden_side:
							break
						forbidden_side = 'a'
						continue
					elif side_a[-1] in connected_faces[face] and forbidden_side != 'a':
						side_a.append(face)
						if forbidden_side:
							break
						forbidden_side = 'a'
						continue
					if len(side_b) == 0 and forbidden_side != 'b':
						side_b.append(face)
						if forbidden_side:
							break
						forbidden_side = 'b'
						continue
					elif side_b[-1] in connected_faces[face] and forbidden_side != 'b':
						side_b.append(face)
						if forbidden_side:
							break
						forbidden_side = 'b'
						continue
			
			if has_branches: # weird input with branches
				break
			newloops.pop(-1)
			sides = []
			if side_a:
				sides.append(side_a)
			if side_b:
				sides.append(side_b)
			
			for side in sides:
				extraloop = []
				for fi in side:
					for key in me.faces[fi].edge_keys:
						if key[0] not in verts_used and key[1] not in verts_used:
							extraloop.append(key)
							break
				if extraloop:
					for key in extraloop:
						for new_vert in key:
							if new_vert not in verts_used:
								verts_used.append(new_vert)
					newloops.append(extraloop)
					all_edgeloops.append(extraloop)
	
	# weird input that contains branches, leave mesh in original state
	if has_branches:
		terminate("Error%t|Selection contains branches", editmode)
		return []
	
	# changing from edge_keys to edge indices
	edge_key_indices = dict([(ed.key, ed.index) for ed in me.edges if (ed.v1.hide!=1 and ed.v2.hide!=1)])
	for i in range(len(all_edgeloops)):
		for j in range(len(all_edgeloops[i])):
			all_edgeloops[i][j] = edge_key_indices[all_edgeloops[i][j]]
	
	# convert from edges to verts
	vertloops = edgesToVerts(me, all_edgeloops)
	
	return vertloops

# remap the mesh to raw mesh data, if necessary
def mapMeshes(ob, me):
	realtime = [mod[Modifier.Settings.REALTIME] for mod in ob.modifiers]
	for mod in ob.modifiers:
		if mod.type in [Modifier.Types.MIRROR]:
			mod[Modifier.Settings.REALTIME] = True
		else:
			mod[Modifier.Settings.REALTIME] = False
	me_orig = me
	me = Mesh.New()
	me.getFromObject(ob)
	for i in range(len(ob.modifiers)):
		ob.modifiers[i][Modifier.Settings.REALTIME] = realtime[i]
	vsel = [v for v in me.verts.selected() if me.verts[v].hide!=1]
	edsel = [ed for ed in me.edges.selected() if (me.edges[ed].v1.hide!=1 and me.edges[ed].v2.hide!=1 and me.edges[ed].sel)]
	fsel = [f for f in me.faces.selected() if me.faces[f].hide!=1 and me.faces[f].sel]
	
	me_mapping = dict([(i, -1) for i in range(len(me.verts))])
	coords = dict([(v.index, v.co) for v in me.verts])
	for v in me_orig.verts:
		i = [key for key, val in coords.iteritems() if (val-v.co).length<1E-6]
		if i:
			me_mapping[i[0]] = v.index
	
	return me_orig, me, vsel, edsel, fsel, me_mapping

# move the vertices to their new locations
def moveVerts(me, me_orig, me_mapping, move, influence):
	for m in move:
		for loc in m:
			if me_mapping[loc[0]] != -1:
				if influence >= 0:
					me_orig.verts[me_mapping[loc[0]]].co = loc[1]*(influence/100.0) + me_orig.verts[me_mapping[loc[0]]].co*((100-influence)/100.0)
				else:
					me_orig.verts[me_mapping[loc[0]]].co = loc[1]


##################################################################
############# Circle Specific Functions ##########################
##################################################################

# return an ordered list of all vertices around the selected vertex
def circle_selectAroundVertex(me, vsel):
	vertex = me.verts[vsel[0]]
	faces = [f for f in me.faces if vertex in f.verts and f.hide!=1]
	edgekeys = []
	# get the edges around the selected vertex
	for f in faces:
		for ek in f.edge_keys:
			if ek[0]!=vsel[0] and ek[1]!=vsel[0]:
				if ek not in edgekeys:
					if me.verts[ek[0]].hide!=1 and me.verts[ek[1]].hide!=1:
						edgekeys.append(ek)
	
	# convert from edgekeys to edge indices (slightly expensive in computation time)
	select = []
	for ed in me.edges:
		if ed.key in edgekeys:
			select.append(ed.index)
	
	# get the edges ordered based on how they are connected
	vertloops = connectedSelections(me, select)
	return vertloops

# return only the loops that are long enough to make any sense
def circle_checkLengths(vertloops):
	checked = []
	for loop in vertloops:
		if len(loop[0])>=3:
			checked.append(loop)
	return checked

# calculate the index of the most optimal starting vertex
def circle_startVertex(me, loop):
	vert_faces = getVertFaces(me)
	faces = []
	for v in loop[0]:
		faces += vert_faces[v]
	face_count = dict([(f.index, 0) for f in me.faces if f.hide!=1])
	for f in faces:
		face_count[f]+=1
	max_face = face_count[max(face_count, key=lambda a: face_count.get(a))]
	max_faces = filter(lambda a: face_count.get(a) == max_face, face_count)
	corner_verts = []
	if len(face_count)-face_count.values().count(0) == len(max_faces):
		return 'NotYetCalculated'
	for f in max_faces:
		verts = [[loop[0].index(v.index), v.index] for v in me.faces[f].verts if v.index in loop[0]]
		if len(verts) < 3:
			continue
		verts.sort()
		c = int(len(verts)/2.0)
		if verts[c][0]-1==verts[c-1][0] and verts[c][0]+1==verts[c+1][0]:
			corner_verts.append(verts[c][1])
		elif verts[c][0]-verts[c-1][0]+2==len(loop[0]) and verts[c][0]+1==verts[c+1][0]:
			corner_verts.append(verts[c+1][1])
		elif verts[c][0]-1==verts[c-1][0] and verts[c+1][0]-verts[c][0]+2==len(loop[0]):
			corner_verts.append(verts[c-1][1])
	if len(corner_verts) == 0:
		return 0
	verts = [[loop[0].index(v), v] for v in corner_verts]
	verts.sort()
	corner_verts = [v[1] for v in verts]
	lengths = []
	for i in range(len(corner_verts)):
		v1 = loop[0].index(corner_verts[i])
		v2 = loop[0].index(corner_verts[i-1])
		if v2 > v1:
			v2 -= len(loop[0])
		dif = v1-v2-1
		index = v1-int(dif/2.0)
		if dif%2 != 0:
			index -= 1
		lengths.append([dif, index])
	lengths.sort()
	return lengths[-1][1]

# calculate the index of the starting vertex, based on a simple comparison of the min/max 2d-coordinates
def circle_extendedStartVertex(me, loop):
	com, normal = circle_calcPlane(me, loop)
	locs_2d, p, q = circle_convertTo2d(me, loop, com, normal)
	
	dif_locs = []
	avg_loc = Mathutils.Vector(0.0, 0.0)
	for i in locs_2d:
		v = Mathutils.Vector(i[0], i[1])
		dif_locs.append(v)
		avg_loc += v
	avg_loc /= len(locs_2d)
	for i in range(len(dif_locs)):
		dif_locs[i] = (dif_locs[i]-avg_loc).length
	avg_dif = float(sum(dif_locs))/len(dif_locs)
	if avg_dif-min(dif_locs) > max(dif_locs)-avg_dif:
		shift = loop[0].index(locs_2d[dif_locs.index(min(dif_locs))][2])
	else:
		min_co = [locs_2d[0][0], locs_2d[0][1]]
		min_coin = [locs_2d[0][2], locs_2d[0],[2]]
		max_co = [locs_2d[0][0], locs_2d[0][1]]
		max_coin = [locs_2d[0][2], locs_2d[0],[2]]
		avg_co = [0.0, 0.0]
		for i in locs_2d:
			avg_co[0] += i[0]
			avg_co[1] += i[1]
			if i[0] < min_co[0]:
				min_co[0] = i[0]
				min_coin[0] = i[2]
			if i[1] < min_co[1]:
				min_co[1] = i[1]
				min_coin[1] = i[2]
			if i[0] > max_co[0]:
				max_co[0] = i[0]
				max_coin[0] = i[2]
			if i[1] > max_co[1]:
				max_co[1] = i[1]
				max_coin[1] = i[2]
		loop_length = len(locs_2d)
		avg_co[0] /= float(loop_length)
		avg_co[1] /= float(loop_length)
		all_dif = []
		for i in range(2):
			min_co[i] = avg_co[i] - min_co[i]
			all_dif.append(min_co[i])
			max_co[i] = max_co[i] - avg_co[i]
			all_dif.append(max_co[i])
		max_dif_i = all_dif.index(max(all_dif))
		if max_dif_i%2 == 0:
			max_dif = min_coin[max_dif_i/2]
		else:
			max_dif = max_coin[(max_dif_i-1)/2]
		shift = loop[0].index(max_dif)
	return shift, com, normal

# check if all the verts in the loop are colinear (in which case the loop would be useless)
def circle_isColinear(me, loop):
	loc0 = Mathutils.Vector(me.verts[loop[0][0]].co[:])
	loc1 = Mathutils.Vector(me.verts[loop[0][1]].co[:])
	for v in loop[0][2:]:
		locn = Mathutils.Vector(me.verts[v].co[:])
		if loc0 == loc1 or loc1 == locn:
			loc0 = Mathutils.Vector(loc1[:])
			loc1 = Mathutils.Vector(locn[:])
			continue
		d1 = loc1-loc0
		d2 = locn-loc1
		if 0.0-1E-6 < Mathutils.AngleBetweenVecs(d1, d2) < 0.0+1E-6:
			loc0 = Mathutils.Vector(loc1[:])
			loc1 = Mathutils.Vector(locn[:])
			continue
		return False
	return True

# calculate a best-fit plane to the given vertices
def circle_calcPlane(me, loop):
	# getting the vertex locations
	locs = [Mathutils.Vector(me.verts[v].co[:]) for v in loop[0]]
	
	# calculating the center of masss
	com = Mathutils.Vector(0.0, 0.0, 0.0)
	for loc in locs:
		com += loc
	com /= len(locs)
	x, y, z = com
	
	# creating the covariance matrix
	mat = Mathutils.Matrix([0.0, 0.0, 0.0], [0.0, 0.0, 0.0], [0.0, 0.0, 0.0])
	for loc in locs:
		mat[0][0] += (loc[0]-x)**2
		mat[0][1] += (loc[0]-x)*(loc[1]-y)
		mat[0][2] += (loc[0]-x)*(loc[2]-z)
		mat[1][0] += (loc[1]-y)*(loc[0]-x)
		mat[1][1] += (loc[1]-y)**2
		mat[1][2] += (loc[1]-y)*(loc[2]-z)
		mat[2][0] += (loc[2]-z)*(loc[0]-x)
		mat[2][1] += (loc[2]-z)*(loc[1]-y)
		mat[2][2] += (loc[2]-z)**2
	
	# calculating the normal to the plane
	normal = False
	try:
		mat.invert()
	except:
		if sum(mat[0]) == 0.0:
			normal = Mathutils.Vector(1.0, 0.0, 0.0)
		elif sum(mat[1]) == 0.0:
			normal = Mathutils.Vector(0.0, 1.0, 0.0)
		elif sum(mat[2]) == 0.0:
			normal = Mathutils.Vector(0.0, 0.0, 1.0)
	if not normal:
		itermax = 500
		iter = 0
		vec = Mathutils.Vector(1.0, 1.0, 1.0)
		vec2 = (vec*mat)/(vec*mat).length
		while vec != vec2 and iter<itermax:
			iter+=1
			vec = vec2
			vec2 = (vec*mat)/(vec*mat).length
		normal = vec2

	if debug and debug[0]:
		print "plane, center of mass:", com
		print "plane, normal:", normal
	return com, normal

# convert the 3d coordinates of the vertices to 2d coordinates on the best-fit plane
def circle_convertTo2d(me, loop, com, normal):
	# project vertices onto the plane
	verts = [me.verts[v] for v in loop[0]]
	verts_projected = []
	for v in verts:
		verts_projected.append([Mathutils.Vector(v.co[:]) - Mathutils.DotVecs((Mathutils.Vector(v.co[:])-com), normal)*normal, v.index])
	
	# calculate two vectors (p and q) along the plane
	m = Mathutils.Vector(normal[0]+1.0, normal[1], normal[2])
	p = m - (Mathutils.DotVecs(m, normal)*normal)
	if Mathutils.DotVecs(p, p) == 0.0:
		m = Mathutils.Vector(normal[0], normal[1]+1.0, normal[2])
		p = m - (Mathutils.DotVecs(m, normal)*normal)
	q = Mathutils.CrossVecs(p, normal)
	
	# change to 2d coordinates using perpendicular projection
	locs_2d = []
	for v in verts_projected:
		vloc = v[0]-com
		x = Mathutils.DotVecs(p, vloc)/Mathutils.DotVecs(p, p)
		y = Mathutils.DotVecs(q, vloc)/Mathutils.DotVecs(q, q)
		locs_2d.append([x, y, v[1]])
	
	return locs_2d, p, q

# calculate a best-fit circle to the 2d locations on the plane
def circle_calcBestCircle(locs_2d):
	# calculate the center and the radius of the circle (non-linear least squares solution)
	x0 = 0.0
	y0 = 0.0
	r = 1.0
	for iter in range(500):
		jmat = []
		k = []
		for v in locs_2d:
			d = (v[0]**2-2.0*x0*v[0]+v[1]**2-2.0*y0*v[1]+x0**2+y0**2)**0.5
			jmat.append([(x0-v[0])/d, (y0-v[1])/d, -1.0])
			k.append(-(((v[0]-x0)**2+(v[1]-y0)**2)**0.5-r))
		jmat2 = Mathutils.Matrix([0.0, 0.0, 0.0], [0.0, 0.0, 0.0], [0.0, 0.0, 0.0])
		k2 = Mathutils.Vector(0.0, 0.0, 0.0)
		for i in range(len(jmat)):
			k2 += Mathutils.Vector(jmat[i])*k[i]
			jmat2[0][0] += jmat[i][0]**2
			jmat2[0][1] += jmat[i][0]*jmat[i][1]
			jmat2[0][2] += jmat[i][0]*jmat[i][2]
			jmat2[1][1] += jmat[i][1]**2
			jmat2[1][2] += jmat[i][1]*jmat[i][2]
			jmat2[2][2] += jmat[i][2]**2
		jmat2[1][0] = jmat2[0][1]
		jmat2[2][0] = jmat2[0][2]
		jmat2[2][1] = jmat2[1][2]
		jmat2.invert()
		dx0, dy0, dr = jmat2*k2
		x0 += dx0
		y0 += dy0
		r += dr
		if abs(dx0)<1E-7 and abs(dy0)<1E-7 and abs(dr)<1E-7:
			break
	
	if debug and debug[0]:
		print "circle, center:", x0, y0
		print "circle, radius:", r
	return x0, y0, r # center of circle + radius

# calculate a circle so that none of the vertices have to be moved away from the center
def circle_calcMinCircle(locs_2d):
	x0 = (min([i[0] for i in locs_2d])+max([i[0] for i in locs_2d]))/2.0
	y0 = (min([i[1] for i in locs_2d])+max([i[1] for i in locs_2d]))/2.0
	center = Mathutils.Vector(x0, y0)
	r = min([(Mathutils.Vector(i[0], i[1])-center).length for i in locs_2d])
	return x0, y0, r # center of circle + radius

# project 2d locations on circle, using a regular distribution (equal distance between all verts)
def circle_projectRegular(locs_2d, x0, y0, r):
	# mathematical constants
	try:
		import math
		pi = math.pi
		e = math.e
	except:
		pi = 3.14159265358979323846
		e = 2.71828182845904523536
	# find offset and circling direction
	x, y, i = locs_2d[0]
	loc = Mathutils.Vector(x-x0, y-y0)
	loc.length = r
	loca = Mathutils.Vector(x-x0, y-y0, 0.0)
	angle = Mathutils.AngleBetweenVecs(loc, Mathutils.Vector(1.0, 0.0))
	x, y, j = locs_2d[1]
	locb = Mathutils.Vector(x-x0, y-y0, 0.0)
	if loc[1] < -1E-6:
		angle *= -1
	if loca.cross(locb)[2] >= 0:
		ccw = 1
	else:
		ccw = -1
	angle = angle/180.0*pi
	# distribute vertices along the circle
	for i in range(len(locs_2d)):
		old = [locs_2d[i][0], locs_2d[i][1]]
		t = angle + ccw*(float(i)/len(locs_2d)*2.0*pi)
		x = ((e**complex(0.0, t)+e**complex(0.0, -t))/2.0).real*r
		y = ((e**complex(0.0, t)-e**complex(0.0, -t))/complex(0.0, 2.0)).real*r
		locs_2d[i] = [x, y, locs_2d[i][2]]
	
	return locs_2d

# project 2d locations on circle, using a non-regular distribution (distance relations between verts are maintained)
def circle_projectNonRegular(locs_2d, x0, y0, r):
	for i in range(len(locs_2d)):
		x, y, j = locs_2d[i]
		loc = Mathutils.Vector(x-x0, y-y0)
		loc.length = r
		locs_2d[i] = [loc[0], loc[1], j]
	return locs_2d

# recalculate positions based on the influence of the circle shape
def circle_influenceLocs(locs_2d, new_locs_2d, influence):
	for i in range(len(locs_2d)):
		oldx, oldy, j = locs_2d[i]
		newx, newy, k = new_locs_2d[i]
		altx = newx*(influence/100.0)+ oldx*((100-influence)/100.0)
		alty = newy*(influence/100.0)+ oldy*((100-influence)/100.0)
		locs_2d[i] = [altx, alty, j]
	return locs_2d

# triangulate the mesh, so intersection tests can be run on it
def circle_triangulateMesh(me):
	tri_me = me.copy()
	try:
		ob = bpy.data.objects["SCRIPT_circletool"]
		ob.link(tri_me)
		bpy.data.scenes.active.objects.link(ob)
	except:
		ob = bpy.data.scenes.active.objects.new(tri_me)
		ob.name = "SCRIPT_circletool"
	tri_me.sel = True
	tri_me.quadToTriangle()
	return tri_me

# clear the triangulated mesh, as far as possible
def circle_clearTriangulatedMesh(tri_me):
	tri_me.verts = None
	bpy.data.scenes.active.objects.unlink(bpy.data.objects["SCRIPT_circletool"])

# calculate the new locations of the vertices that need to be moved
def circle_calcVerts(tri_me, locs_2d, com, p, q, normal):
	# changing 2d coordinates back to 3d coordinates
	locs_3d = []
	for loc in locs_2d:
		locs_3d.append([loc[2], loc[0]*p + loc[1]*q + com])
	
	if not buttons['circle_project'].val: # flat circle, the default
		return locs_3d
	else: # project the locations on the existing mesh
		vert_faces = getVertFaces(tri_me)
		faces = [f for f in tri_me.faces if f.hide!=1]
		rays = [normal, -normal]
		new_locs = []
		for loc in locs_3d:
			projection = False
			if tri_me.verts[loc[0]].co == loc[1]: # vertex hasn't moved
				projection = loc[1]
			else:
				dif = Mathutils.AngleBetweenVecs(normal, loc[1]-tri_me.verts[loc[0]].co )
				if -1E-5<dif<1E-5 or 180.0-1E-5<dif<180.0+1E-5: # original location is already along projection normal
					projection = tri_me.verts[loc[0]].co
				else:
					for f in vert_faces[loc[0]]: # quick search through adjacent faces
						v1, v2, v3 = [v.co for v in tri_me.faces[f].verts]
						for ray in rays:
							intersect = Mathutils.Intersect(v1, v2, v3, ray, loc[1])
							if intersect:
								projection = intersect
								break
						if projection:
							break
			if not projection: # full search through the entire mesh
				for f in faces:
					v1, v2, v3 = [v.co for v in f.verts]
					for ray in rays:
						intersect = Mathutils.Intersect(v1, v2, v3, ray, loc[1])
						if intersect:
							projection = intersect
							break
					if projection:
						break
			if not projection: # nothing to project on, remain at flat location
				projection = loc[1]
			new_locs.append([loc[0], projection])
		return new_locs

# main function that controls the circle loop functionality
def circleloop():
	if debug and debug[0]:
		print "_____________ circle loop __________________"
	# get the connected selected edges in a list
	editmode, ob, me, vsel, edsel, fsel = initialise()
	if not ob or not me:
		return
	
	# some mapping so the tool can work with objects that have modifiers
	if len(ob.modifiers)>0 and tool_speed<4:
		me_orig, me, vsel, edsel, fsel, me_mapping = mapMeshes(ob, me)
	else:
		me_orig = me
		me_mapping = dict([(i, i) for i in range(len(me.verts))])
	
	if len(vsel)<1:
		terminate("Error%t|Select at least one vertex", editmode)
		return
	elif len(vsel)==1:
		vertloops = circle_selectAroundVertex(me, vsel)
	else:
		if len(edsel)==0:
			vertloops = []
			for v in vsel:
				vertloops.append(circle_selectAroundVertex(me, [v])[0])
		else:
			vertloops = connectedSelections(me, edsel)
	
	# Get parallel edges
	if buttons['circle_all'].val:
		vertloops = parallelLoops(vertloops, me, vsel, editmode)
	# Check length of loops
		vertloops = circle_checkLengths(vertloops)
	if len(vertloops)==0:
		terminate("Selection doesn't result in any loops that can be changed%t|No changes have been made to the scene", editmode)
		return
	
	move = []
	Window.EditMode(0)
	if buttons['circle_project'].val:
		tri_me = circle_triangulateMesh(me)
	else:
		tri_me = me
	loop_shift = -1
	com = False
	normal = False
	for loop in vertloops:
		if loop[1] and loop_shift == -1 and (tool_speed%4)//2==0:
			loop_shift = circle_startVertex(me, vertloops[0])
			if loop_shift == 'NotYetCalculated' and (tool_speed%4%2)==0:
				loop_shift, com, normal = circle_extendedStartVertex(me, vertloops[0])
			elif loop_shift == 'NotYetCalculated':
				loop_shift = -1
		if loop_shift != -1:
			loop[0] = loop[0][loop_shift:]+loop[0][:loop_shift]
		if circle_isColinear(me, loop):
			if vertloops.index(loop) == 0:
				terminate("Error%t|Selection is colinear", editmode)
				return
			else:
				continue
		if not com or not normal:
			com, normal = circle_calcPlane(me, loop)
		locs_2d, p, q = circle_convertTo2d(me, loop, com, normal)
		if buttons['circle_bestfit'].val:
			x0, y0, r = circle_calcBestCircle(locs_2d)
		else:
			x0, y0, r = circle_calcMinCircle(locs_2d)
		if buttons['circle_forcer'].val:
			r = buttons['circle_radius'].val / max(ob.size)
		if buttons['circle_reg'].val:
			new_locs_2d = circle_projectRegular(locs_2d[:], x0, y0, r)
		else:
			new_locs_2d = circle_projectNonRegular(locs_2d[:], x0, y0, r)
		locs_2d = circle_influenceLocs(locs_2d, new_locs_2d, int(buttons['circle_influence'].val))
		move.append(circle_calcVerts(tri_me, locs_2d, com, p, q, normal))
		
		com = False
		normal = False
		if not buttons['circle_all'].val:
			loop_shift = -1
	if buttons['circle_project'].val:
		circle_clearTriangulatedMesh(tri_me)
	moveVerts(me, me_orig, me_mapping, move, -1)
	
	Window.Redraw()
	terminate(False, editmode)


##################################################################
############# Curve Specific Functions ###########################
##################################################################

# check if all verts of an edgeloop are selected
def curve_fullLoopSelected(edgeloops, vsel):
	for loop in edgeloops:
		full = []
		for v in loop[0]:
			if v not in vsel:
				full = False
				break
			else:
				full.append(v)
		if full and len(full)>1:
			return loop
	return False

# returns all loops that are perpendicular to the given one
def curve_perpendicularLoops(loop, me, vert_edges, edge_faces, vsel):
	edgeloops = []
	vselfull = []
	vselused = []
	for v in loop[0]:
		lnew, vert_edges, edge_faces = getLoops(me, v, vert_edges, edge_faces)
		lcor = False
		for l in lnew:
			if loop[0][0] not in l[0] or loop[0][1] not in l[0]:
				lcor = l
				break
		if lcor:
			edgeloops.append(lcor)
			vsf = []
			for vs in vsel:
				if vs in lcor[0]:
					vselused.append(vs)
					vsf.append(vs)
			vselfull.append(vsf)
	if len(vselused)>len(vsel):
		# solution for non-equal length edge loops
		shortest = [len(edgeloops[0][0]),False]
		for i in edgeloops:
			if len(i[0]) <= shortest[0]:
				shortest = [len(i[0]), i[0]]
		for i in shortest[1]:
			if i in loop[0]:
				cut_shift = shortest[1].index(i)
				break
		
		cut_loops = []
		for i in edgeloops:
			# cut circular loops in half
			if len(i[0]) > shortest[0] and i[2]:
				cut_snip = []
				for j in i[0]:
					if j in loop[0]:
						cut_snip.append(i[0].index(j))
				
				cut_dif = (cut_snip[0]+cut_snip[1])/2.0
				cut_left1 = int(2.1*(cut_dif%int(cut_dif)))+int(cut_dif)
				cut_right1 = int(cut_dif)+1
				
				cut_dif2 = cut_dif-len(i[0])/2.0
				if cut_dif2 < 0:
					cut_dif2 += len(i[0])
				cut_left2 = int(cut_dif2)+1
				cut_right2 = int(2.1*(cut_dif2%int(cut_dif2)))+int(cut_dif2)
				
				if cut_left1>cut_left2:
					cut_interval1 = i[0][cut_left2:cut_left1]
				else:
					cut_interval1 = i[0][cut_left2:]+i[0][:cut_left1]
				if cut_right2>cut_right1:
					cut_interval2 = i[0][cut_right1:cut_right2]
				else:
					cut_interval2 = i[0][cut_right1:]+i[0][:cut_right2]
				
				# reverse order as necessary
				if shortest[0]-cut_shift > shortest[0]/2:
					cut_bigatend = True
				else:
					cut_bigatend = False
				for k in cut_interval1:
					if k in loop[0]:
						cut_snip = cut_interval1.index(k)
						break
				if len(cut_interval1)-cut_snip > len(cut_interval1)/2:
					if not cut_bigatend:
						cut_interval1.reverse()
				for k in cut_interval2:
					if k in loop[0]:
						cut_snip = cut_interval2.index(k)
						break
				if len(cut_interval2)-cut_snip > len(cut_interval2)/2:
					if not cut_bigatend:
						cut_interval2.reverse()
				
				cut_loops.append([cut_interval1, i[1], False])
				cut_loops.append([cut_interval2, i[1], False])
			else:
				cut_loops.append(i)
		# trim the loops
		for i in cut_loops:
			if len(i[0]) == shortest[0]:
				continue
			for j in i[0]:
				if j in loop[0]:
					cut_snip = i[0].index(j)
					break
			cut_start = cut_snip-cut_shift
			cut_end = cut_snip-cut_shift+shortest[0]
			if cut_start<0:
				cut_end += 0-cut_start-1
			if cut_end>len(i[0]):
				cut_start -= cut_end-len(i[0])-1
			i[0] = i[0][max(0,cut_start):min(len(i[0]),cut_end)]
		edgeloops = cut_loops[:]
		
		# create correct lists with selected vertices
		vselfull = []
		for i in edgeloops:
			vsf = []
			for vs in vsel:
				if vs in i[0]:
					vsf.append(vs)
			vselfull.append(vsf)
	
	return edgeloops, vselfull

# create lists with knots and points, all correctly sorted
def curve_calcKnots(loop, vsel):
	if debug and debug[0]:
		print "loop[0]", loop[0]
		print "vsel", vsel
	knots = []
	points = []
	for v in loop[0]:
		if v in vsel:
			knots.append(v)
	if loop[2]: # loop is circular, potential for weird splines
		offset = int(len(loop[0])/4.0)
		if len(vsel)==1: # only 1 user-defined control point
			k = loop[0].index(vsel[0])
			k1 = k-offset
			if k1<0:
				k1 += len(loop[0])
			k2 = k+offset
			if k2>len(loop[0])-1:
				k2 -= len(loop[0])
			knots.insert(0,loop[0][k1])
			knots.append(loop[0][k2])
			if k2>k1:
				points = loop[0][k1:k2+1]
			else:
				for i in loop[0][k1:]:
					points.append(i)
				for i in loop[0][0:k2+1]:
					points.append(i)
			if debug and debug[0]:
				print "broken circle 1 sel"
		else: # multiple user-defined control points
			kpos = []
			for k in knots:
				kpos.append(loop[0].index(k))
			kdif = []
			for i in range(len(kpos)-1):
				kdif.append(kpos[i+1]-kpos[i])
			kdif.append(len(loop[0])-kpos[-1]+kpos[0])
			kadd = []
			for k in kdif:
				if k>2*offset:
					kadd.append([kdif.index(k),True])
				# next 2 lines are optional, they insert
				# an extra control point in small gaps
				#elif k>offset:
				#   kadd.append([kdif.index(k),False])
			kins = []
			krot = False
			for k in kadd: # extra knots to be added
				if k[1]: # big gap (break circular spline)
					kpos = loop[0].index(knots[k[0]])+offset
					if kpos>len(loop[0])-1:
						kpos -= len(loop[0])
					kins.append([knots[k[0]],loop[0][kpos]])
					kpos2 = k[0]+1
					if kpos2>len(knots)-1:
						kpos2 -= len(knots)
					kpos2 = loop[0].index(knots[kpos2])-offset
					if kpos2<0:
						kpos2 += len(loop[0])
					kins.append([loop[0][kpos],loop[0][kpos2]])
					krot = loop[0][kpos2]
				else: # small gap (keep circular spline)
					k1 = loop[0].index(knots[k[0]])
					k2 = k[0]+1
					if k2>len(knots)-1:
						k2 -= len(knots)
					k2 = loop[0].index(knots[k2])
					if k2<k1:
						dif = len(loop[0])-1-k1+k2
					else:
						dif = k2-k1
					kn = k1+int(dif/2.0)
					if kn>len(loop[0])-1:
						kn -= len(loop[0])
					kins.append([loop[0][k1],loop[0][kn]])
			for j in kins: # insert new knots
				knots.insert(knots.index(j[0])+1,j[1])
			if not krot: # circular loop
				knots.append(knots[0])
				points = loop[0][loop[0].index(knots[0]):]
				points += loop[0][0:loop[0].index(knots[0])+1]
				if debug and debug[0]:
					print "circular >1 sel"
			else: # non-circular loop (broken by script)
				krot = knots.index(krot)
				knots = knots[krot:]+knots[0:krot]
				if loop[0].index(knots[0])>loop[0].index(knots[-1]):
					points = loop[0][loop[0].index(knots[0]):]
					points += loop[0][0:loop[0].index(knots[-1])+1]
				else:
					points = loop[0][loop[0].index(knots[0]):loop[0].index(knots[-1])+1]
				if debug and debug[0]:
					print "broken circle >1 sel"
	else: # non-circular loop
		if loop[0][0] not in knots:
			knots.insert(0,loop[0][0])
		if loop[0][-1] not in knots:
			knots.append(loop[0][-1])
		points = loop[0][:]
		if debug and debug[0]:
			print "non circular"
	if debug and debug[0]:
		print "points", points
		print "knots", knots
	return knots, points

# project knots on non-selected geometry
def curve_projectKnots(me, vsel, knots, points):
	# def to project vertex on edge
	def project(v1, v2, v3):
		# v1 and v2 are part of a line
		# v3 is projected onto it
		v2 -= v1
		v3 -= v1
		p = Mathutils.ProjectVecs(v3, v2)
		return p+v1

	if knots[0] == knots[-1]: # circular loop, project all knots
		start = 0
		end = len(knots)
		pknots = []
	else: # non-circular, first and last knot shouldn't be projected
		start = 1
		end = -1
		pknots = [Mathutils.Vector(me.verts[knots[0]].co[:])]
	for k in knots[start:end]:
		if k in vsel: # if knot is selected
			kleft = kright = False
			for i in range(points.index(k)-1,-1*len(points),-1):
				if points[i] not in knots:
					kleft = points[i]
					break
			for i in range(points.index(k)+1,2*len(points)):
				if i>len(points)-1:
					i -= len(points)
				if points[i] not in knots:
					kright = points[i]
					break
			if kleft and kright and kleft!=kright:
				kleft = Mathutils.Vector(me.verts[kleft].co[:])
				kright = Mathutils.Vector(me.verts[kright].co[:])
				k = Mathutils.Vector(me.verts[k].co[:])
				pknots.append(project(kleft, kright, k))
			else: pknots.append(Mathutils.Vector(me.verts[k].co[:]))
		else: # knot isn't selected, so shouldn't be changed
			pknots.append(Mathutils.Vector(me.verts[k].co[:]))
	if knots[0]!=knots[-1]: # non-circular
		pknots.append(Mathutils.Vector(me.verts[knots[-1]].co[:]))
	return pknots

# calculate relative positions compared to first point
def curve_calcT(me, knots, points, pknots):
	tpoints = []
	loc_prev = False
	len_total = 0
	for p in points:
		if p in knots:
			loc = pknots[knots.index(p)] # use projected knot location
		else:
			loc = Mathutils.Vector(me.verts[p].co[:])
		if not loc_prev:
			loc_prev = loc
		len_total += (loc-loc_prev).length
		tpoints.append(len_total)
		loc_prev = loc
	tknots = []
	for p in points:
		if p in knots:
			tknots.append(tpoints[points.index(p)])
	if knots[0] == knots[-1]: # hack for circular loops
		tknots[-1] = tpoints[-1]
	return tpoints, tknots

# change the location of non-selected points to their place on the spline
def curve_calcVerts(me_orig, me, me_mapping, points, tpoints, knots, tknots, splines, iter, editmode, ob, vsel):

	Window.EditMode(0)
	newlocs = {}
	move = []
	for p in points:
		if p in knots:
			continue
		m = tpoints[points.index(p)]
		if m in tknots:
			n = tknots.index(m)
		else:
			t = tknots[:]
			t.append(m)
			t.sort()
			n = t.index(m)-1
		if n>len(splines)-1:
			n = len(splines)-1
		elif n<0:
			n = 0
		
		if buttons['curve_cubic'].val:
			ax,bx,cx,dx,tx = splines[n][0]
			x = ax+bx*(m-tx)+cx*(m-tx)**2+dx*(m-tx)**3
			ay,by,cy,dy,ty = splines[n][1]
			y = ay+by*(m-ty)+cy*(m-ty)**2+dy*(m-ty)**3
			az,bz,cz,dz,tz = splines[n][2]
			z = az+bz*(m-tz)+cz*(m-tz)**2+dz*(m-tz)**3
			newloc = Mathutils.Vector([x,y,z])
		else:
			a, d, t, u = splines[n]
			newloc = ((m-t)/u)*d+a

		if buttons['curve_restrict'].val: # vertex movement is restricted
			newlocs[p] = newloc
		else: # vertices can be moved freely, so just set the vertex to its new location
			move.append([p, newloc])
		
	if buttons['curve_restrict'].val: # vertex movement is restricted
		iter += 1
		movelist = []
		for p in points:
			if newlocs.has_key(p):
				newloc = newlocs[p]
			else:
				movelist.append([p, me.verts[p].co])
				continue
			oldloc = me.verts[p].co
			normal = me.verts[p].no
			dloc = newloc-oldloc
			if dloc.length == 0.0:
				movelist.append([p, newloc])
			elif buttons['curve_plus'].val: # only extrusions
				if Mathutils.AngleBetweenVecs(dloc, normal) < 90+1E-6:
					movelist.append([p, newloc])
				else:
					movelist.append(False)
			else: # only indentations
				if Mathutils.AngleBetweenVecs(dloc, normal) > 90-1E-6:
					movelist.append([p, newloc])
				else:
					movelist.append(False)
		
		if False in movelist or iter>20:
			i = 1
			newloops = [[]]
			for m in movelist:
				if m:
					if i != len(newloops):
						newloops.append([])
						i = len(newloops)
					newloops[-1].append(m)
				elif len(newloops[-1]) != 0:
					i += 1
			for loop in newloops:
				if len(loop)>1:
					new_el = [[[l[0] for l in loop], [], False]]
					curveloop([editmode, ob, me_orig, me, me_mapping, vsel, new_el, iter])
		else: # all vertices can be moved, or max_iter is reached, so move the vertices
			for m in movelist:
				if m:
					move.append(m)
	return move

# general function that controls the creation of curve loops
def curveloop(skipAhead):
	if debug and debug[0]:
		print "_____________ curve loop __________________"
	
	if not skipAhead:
		editmode, ob, me, vsel, edsel, fsel = initialise()
		iter = 0
		if not ob or not me:
			return
		# some mapping so the tool can work with objects that have modifiers
		if len(ob.modifiers)>0 and tool_speed<4:
			me_orig, me, vsel, edsel, fsel, me_mapping = mapMeshes(ob, me)
		else:
			me_orig = me
			me_mapping = dict([(i, i) for i in range(len(me.verts))])
		
		if len(vsel)<1:
			terminate("Error%t|Select at least one vertex", editmode)
			return
		elif len(vsel)==1:
			edgeloops, vert_edges, edge_faces = getLoops(me, vsel[0], False, False)
			if len(edgeloops)>1:
				additionalVertex('curve_add', editmode, ob, me_orig, me, me_mapping, vsel, edgeloops)
				return
		else:
			edgeloops, vert_edges, edge_faces = getLoops(me, vsel[0], False, False)
			loop = curve_fullLoopSelected(edgeloops, vsel)
			if loop: # all verts of the loop are selected
				full = True
				edgeloops, vselfull = curve_perpendicularLoops(loop, me, vert_edges, edge_faces, vsel)
			else: # multiple selection, but not the full loop selected
				full = False
				for v in vsel[1:]:
					wrongloops = []
					for loop in edgeloops:
						if v not in loop[0] and v not in loop[1]:
							wrongloops.append(loop)
					if len(wrongloops) == len(edgeloops):
						terminate("Error%t|Selected vertices all need to be on the same edge loop", editmode)
						return
					for loop in wrongloops:
						edgeloops.remove(loop)
				if len(edgeloops)>1:
					additionalVertex('curve_add', editmode, ob, me, vsel, edgeloops)
					return
	else:
		editmode, ob, me_orig, me, me_mapping, vsel, edgeloops, iter = skipAhead
		full = False
	
	if debug and debug[1]:
		Window.EditMode(0)
		me.sel = False
		for loop in edgeloops:
			for v in loop[0]:
				me.verts[v].sel = True
		Window.EditMode(1)
	
	move = []
	for loop in edgeloops:
		if len(loop[0]) < 2:
			continue
		if full:
			vsel = vselfull[edgeloops.index(loop)]
		knots, points = curve_calcKnots(loop, vsel)
		pknots = curve_projectKnots(me, vsel, knots, points)
		tpoints, tknots = curve_calcT(me, knots, points, pknots)
		if buttons['curve_reg'].val:
			tpoints_avg = tpoints[-1]/float(len(tpoints)-1)
			for i in range(1,len(tpoints)-1):
				tpoints[i] = i*tpoints_avg
			for i in range(len(knots)):
				tknots[i] = tpoints[points.index(knots[i])]
			if loop[2]: # circular loop
				tknots[-1] = tpoints[-1]
		if buttons['curve_cubic'].val:
			splines = calcCubicSplines(me, tknots, knots)
		else:
			splines = calcLinearSplines(me, tknots, knots)
		move.append(curve_calcVerts(me_orig, me, me_mapping, points, tpoints, knots, tknots, splines, iter, editmode, ob, vsel))
	moveVerts(me, me_orig, me_mapping, move, int(buttons['curve_influence'].val))
	if iter == 0:
		Draw.Redraw()
		terminate(False, editmode)


##################################################################
############# Relax Specific Functions ###########################
##################################################################

# create lists with knots and points, all correctly sorted
def relax_calcKnots(vertloops):
	all_knots = []
	all_points = []
	for loop in vertloops:
		knots = [[], []]
		points = [[], []]
		if loop[1]: # circular
			if len(loop[0])%2 == 1: # odd
				extend = [False, True, 0, 1, 0, 1]
			else: # even
				extend = [True, False, 0, 1, 1, 2]
		else:
			if len(loop[0])%2 == 1: # odd
				extend = [False, False, 0, 1, 1, 2]
			else: # even
				extend = [False, False, 0, 1, 1, 2]
		for j in range(2):
			if extend[j]:
				loop[0] = [loop[0][-1]] + loop[0] + [loop[0][0]]
			for i in range(extend[2+2*j], len(loop[0]), 2):
				knots[j].append(loop[0][i])
			for i in range(extend[3+2*j], len(loop[0]), 2):
				if loop[0][i] == loop[0][-1] and not loop[1]:
					continue
				if len(points[j]) == 0:
					points[j].append(loop[0][i])
				elif loop[0][i] != points[j][0]:
					points[j].append(loop[0][i])
			if loop[1]:
				if knots[j][0] != knots[j][-1]:
					knots[j].append(knots[j][0])
		if len(points[1]) == 0:
			knots.pop(1)
			points.pop(1)
		for k in knots:
			all_knots.append(k)
		for p in points:
			all_points.append(p)
	
	if debug and debug[0]:
		print "knots", all_knots
		print "points", all_points
	return all_knots, all_points

# calculate relative positions compared to first knot
def relax_calcT(me, knots, points):
	all_tknots = []
	all_tpoints = []
	for i in range(len(knots)):
		amount = len(knots[i]) + len(points[i])
		mix  = []
		for j in range(amount):
			if j%2 == 0:
				mix.append([True, knots[i][j/2]])
			elif j == amount-1:
				mix.append([True, knots[i][-1]])
			else:
				mix.append([False, points[i][int(j/2)]])
		len_total = 0
		loc_prev = False
		tknots = []
		tpoints = []
		for m in mix:
			loc = Mathutils.Vector(me.verts[m[1]].co[:])
			if not loc_prev:
				loc_prev = loc
			len_total += (loc-loc_prev).length
			if m[0]:
				tknots.append(len_total)
			else:
				tpoints.append(len_total)
			loc_prev = loc
		if buttons['relax_reg'].val:
			tpoints = []
			for p in range(len(points[i])):
				tpoints.append((tknots[p]+tknots[p+1])/2.0)
		all_tknots.append(tknots)
		all_tpoints.append(tpoints)
	
	return all_tknots, all_tpoints

# change the location of the points to their place on the spline
def relax_calcVerts(me, tknots, knots, tpoints, points, splines):
	Window.EditMode(0)
	change = []
	move = []
	for i in range(len(knots)):
		for p in points[i]:
			m = tpoints[i][points[i].index(p)]
			if m in tknots[i]:
				n = tknots[i].index(m)
			else:
				t = tknots[i][:]
				t.append(m)
				t.sort()
				n = t.index(m)-1
			if n>len(splines[i])-1:
				n = len(splines[i])-1
			elif n<0:
				n = 0
			
			if buttons['relax_cubic'].val:
				ax,bx,cx,dx,tx = splines[i][n][0]
				x = ax+bx*(m-tx)+cx*(m-tx)**2+dx*(m-tx)**3
				ay,by,cy,dy,ty = splines[i][n][1]
				y = ay+by*(m-ty)+cy*(m-ty)**2+dy*(m-ty)**3
				az,bz,cz,dz,tz = splines[i][n][2]
				z = az+bz*(m-tz)+cz*(m-tz)**2+dz*(m-tz)**3
				change.append([p, Mathutils.Vector([x,y,z])])
			else:
				a, d, t, u = splines[i][n]
				change.append([p, ((m-t)/u)*d+a])
	for c in change:
		move.append([c[0], (me.verts[c[0]].co + c[1])/2.0])
	return move

# remap the mesh to raw mesh data, if necessary
def relax_mapMeshes(ob, me):
	realtime = [mod[Modifier.Settings.REALTIME] for mod in ob.modifiers]
	for mod in ob.modifiers:
		if mod.type in [Modifier.Types.MIRROR]:
			mod[Modifier.Settings.REALTIME] = True
		else:
			mod[Modifier.Settings.REALTIME] = False
	me_orig = me
	me = Mesh.New()
	me.getFromObject(ob)
	for i in range(len(ob.modifiers)):
		ob.modifiers[i][Modifier.Settings.REALTIME] = realtime[i]
	
	return me_orig, me

# main function that controls the relax loop functionality
def relaxloop(skipAhead):
	if debug and debug[0]:
		print "_____________ relax loop __________________"
	
	# Get the connected selected edges in a list
	if not skipAhead:
		editmode, ob, me, vsel, edsel, fsel = initialise()
		if not ob or not me:
			return
		# some mapping so the tool can work with objects that have modifiers
		if len(ob.modifiers)>0 and tool_speed<4:
			me_orig, me, vsel, edsel, fsel, me_mapping = mapMeshes(ob, me)
		else:
			me_orig = me
			me_mapping = dict([(i, i) for i in range(len(me.verts))])
		
		if len(vsel)<1:
			terminate("Error%t|Select at least one vertex", editmode)
			return
		elif len(vsel)==1:
			edgeloops, vert_edges, edge_faces = getLoops(me, vsel[0], False, False)
			if len(edgeloops)>1:
				additionalVertex('relax_add', editmode, ob, me_orig, me, me_mapping, vsel, edgeloops)
				return
			else:
				vertloops = [[edgeloops[0][0]]+[edgeloops[0][2]]]
		else:
			if len(edsel)==0:
				terminate("Error%t|No continuous selection", editmode)
				return
			else:
				vertloops = connectedSelections(me, edsel)
	else:
		editmode, ob, me_orig, me, me_mapping, vsel, vertloops = skipAhead
		vertloops = [[vertloops[0][0]]+[vertloops[0][2]]]
	
	# Get parallel edges
	if buttons['relax_all'].val:
		vertloops = parallelLoops(vertloops, me, vsel, editmode)
	
	iterations = buttons['relax_iter'].val
	knots, points = relax_calcKnots(vertloops)
	for iteration in range(iterations):
		move = []
		tknots, tpoints = relax_calcT(me, knots, points)
		splines = []
		if buttons['relax_cubic'].val:
			for i in range(len(knots)):
				splines.append(calcCubicSplines(me, tknots[i], knots[i][:]))
		else:
			for i in range(len(knots)):
				splines.append(calcLinearSplines(me, tknots[i], knots[i][:]))
		move.append(relax_calcVerts(me, tknots, knots, tpoints, points, splines))
		moveVerts(me, me_orig, me_mapping, move, -1)
		me_orig, me = relax_mapMeshes(ob, me_orig)
		me_orig.update()
		Window.Redraw()
	
	terminate(False, editmode)


##################################################################
############# Space Specific Functions ###########################
##################################################################

# calculate relative positions compared to first knots
def space_calcT(me, knots):
	tknots = []
	loc_prev = False
	len_total = 0
	for k in knots:
		loc = Mathutils.Vector(me.verts[k].co[:])
		if not loc_prev:
			loc_prev = loc
		len_total += (loc-loc_prev).length
		tknots.append(len_total)
		loc_prev = loc
	amount = len(knots)
	t_per_segment = len_total/float(amount-1)
	tpoints = []
	for i in range(amount):
		tpoints.append(i*t_per_segment)
	return tknots, tpoints

# change the location of the points to their place on the spline
def space_calcVerts(me, tpoints, points, tknots, splines):
	Window.EditMode(0)
	move = []
	for p in points:
		m = tpoints[points.index(p)]
		if m in tknots:
			n = tknots.index(m)
		else:
			t = tknots[:]
			t.append(m)
			t.sort()
			n = t.index(m)-1
		if n>len(splines)-1:
			n = len(splines)-1
		elif n<0:
			n = 0
		
		if buttons['space_cubic'].val:
			ax,bx,cx,dx,tx = splines[n][0]
			x = ax+bx*(m-tx)+cx*(m-tx)**2+dx*(m-tx)**3
			ay,by,cy,dy,ty = splines[n][1]
			y = ay+by*(m-ty)+cy*(m-ty)**2+dy*(m-ty)**3
			az,bz,cz,dz,tz = splines[n][2]
			z = az+bz*(m-tz)+cz*(m-tz)**2+dz*(m-tz)**3
			move.append([p, Mathutils.Vector([x,y,z])])
		else:
			a, d, t, u = splines[n]
			move.append([p, ((m-t)/u)*d+a])
	return move

# main function that controls the space loop functionality
def spaceloop(skipAhead):
	if debug and debug[0]:
		print "_____________ space loop __________________"
	
	# Get the connected selected edges in a list
	if not skipAhead:
		editmode, ob, me, vsel, edsel, fsel = initialise()
		if not ob or not me:
			return
		# some mapping so the tool can work with objects that have modifiers
		if len(ob.modifiers)>0 and tool_speed<4:
			me_orig, me, vsel, edsel, fsel, me_mapping = mapMeshes(ob, me)
		else:
			me_orig = me
			me_mapping = dict([(i, i) for i in range(len(me.verts))])
		
		if len(vsel)<1:
			terminate("Error%t|Select at least one vertex", editmode)
			return
		elif len(vsel)==1:
			edgeloops, vert_edges, edge_faces = getLoops(me, vsel[0], False, False)
			if len(edgeloops)>1:
				additionalVertex('space_add', editmode, ob, me_orig, me, me_mapping, vsel, edgeloops)
				return
			else:
				vertloops = [[edgeloops[0][0]]+[edgeloops[0][2]]]
		else:
			if len(edsel)==0:
				terminate("Error%t|No continuous selection", editmode)
				return
			else:
				vertloops = connectedSelections(me, edsel)
	else:
		editmode, ob, me_orig, me, me_mapping, vsel, vertloops = skipAhead
		vertloops = [[vertloops[0][0]]+[vertloops[0][2]]]
	
	# Get parallel edges
	if buttons['space_all'].val:
		vertloops = parallelLoops(vertloops, me, vsel, editmode)
	
	move = []
	for loop in vertloops:
		if loop[1]: # circular
			if loop[0][0] != loop[0][-1]:
				loop[0].append(loop[0][0])
		tknots, tpoints = space_calcT(me, loop[0])
		if buttons['space_cubic'].val:
			splines = calcCubicSplines(me, tknots, loop[0][:])
		else:
			splines = calcLinearSplines(me, tknots, loop[0][:])
		move.append(space_calcVerts(me, tpoints, loop[0][:-1], tknots, splines))
	moveVerts(me, me_orig, me_mapping, move, int(buttons['space_influence'].val))
	
	terminate(False, editmode)


##################################################################
############# Graphical User Interface ###########################
##################################################################

# change the GUI, this doesn't include dragging with the mouse
def changeGui(reset, val):
	# reset the GUI to the default
	if reset:
		# reset the position
		buttons['offset_x'] = buttons['default_offset_x']
		buttons['offset_y'] = buttons['default_offset_y']
		# reset the zoom
		buttons['zoom'] = buttons['default_zoom']
		resizeButtons()
		return
	# change the horizontal position of the GUI
	elif Window.GetKeyQualifiers() & Window.Qual.CTRL:
		buttons['offset_x'] += int(10.0 * val * buttons['sensitivity'])
		Draw.Redraw()
	# change the vertical position of the GUI
	elif Window.GetKeyQualifiers() & Window.Qual.SHIFT:
		buttons['offset_y'] += int(10.0 * val * buttons['sensitivity'])
		Draw.Redraw()
	# change the zoom of the GUI
	else:
		buttons['zoom'] = max(0.8, 0.05*val*buttons['sensitivity'] + buttons['zoom'])
		resizeButtons()

# calculate values for the new zoom value of the GUI
def resizeButtons():
	buttons['margin'] = int(buttons['default_margin']*buttons['zoom'])
	buttons['height'] = int(buttons['default_height']*buttons['zoom'])
	buttons['width'] = int(buttons['default_width']*buttons['zoom'])
	buttons['total_height'] = 4*buttons['height']+4*buttons['margin']+18
	if buttons['space_gui']:
		buttons['total_height'] -= buttons['height']+buttons['margin']
	buttons['total_width'] = max(4*buttons['width']+1, int(buttons['width']/2.0)+2*max(15,int(buttons['height']/2.0))+2*buttons['width']+5*buttons['margin'])
	Draw.Redraw()

# start or stop the dragging of the GUI with the middle mouse button
def dragmodeGui(start):
	if start:
		buttons['mouse'] = Window.GetMouseCoords()
	else:
		buttons['mouse'] = False

# move the GUI, as it is dragged with the middle mouse button
def dragGui():
	# cursor moved out of window
	if not Window.GetMouseButtons() & Window.MButs.M:
		dragmodeGui(False)
		return
	mouse_x, mouse_y = Window.GetMouseCoords()
	dmouse_x = mouse_x - buttons['mouse'][0]
	dmouse_y = mouse_y - buttons['mouse'][1]
	buttons['mouse'] = [mouse_x, mouse_y]
	buttons['offset_x'] += int(dmouse_x)
	buttons['offset_y'] += int(dmouse_y)
	Draw.Redraw()

# make the radiobuttons work
def changeRadio(evt):
	for but in radio_buttons[evt]:
		buttons[but] = Draw.Create(False)
	for item in but_evt.items():
		if evt == item[1]:
			buttons[item[0]] = Draw.Create(True)
			break
	Draw.Redraw()

# change the tab to the one that has been clicked
def changeTab():
	# extra vertex needs to be selected, can't change tabs
	if buttons['curve_add'] or buttons['relax_add'] or buttons['space_add']:
		return
	# something else has just been clicked on, user doesn't want to change tabs
	if buttons['tab_sleep']:
		if sys.time()-buttons['tab_sleep'] < 0.1:
			buttons['tab_sleep'] = False
			return
	
	# get offsets
	id = Window.GetAreaID()
	for area in Window.GetScreenInfo():
		if area['id'] == id:
			coord = area['vertices']
			break

	mouse_x, mouse_y = Window.GetMouseCoords()
	win_x, win_y = Window.GetAreaSize()
	tw = buttons['total_width']
	th = buttons['total_height']
	x = int((win_x - tw) / 2.0) + buttons['offset_x']+coord[0]
	y = int((win_y - th) / 2.0) + buttons['offset_y']+coord[1]
	m = buttons['margin']
	w = buttons['width']
	h = buttons['height']
	tabh = 18

	change = False
	if mouse_y >= y+th-h-tabh-m and mouse_y <= y+th-h-m:
		if mouse_x >= x+1 and mouse_x <=  x+4*w:
			if mouse_x <= x+w:
				change = 'circle_gui'
			elif mouse_x <= x+2*w:
				change = 'curve_gui'
			elif mouse_x <= x+3*w:
				change = 'relax_gui'
			elif mouse_x <= x+4*w:
				change = 'space_gui'
	
	if change:
		buttons['circle_gui'] = False
		buttons['curve_gui'] = False
		buttons['relax_gui'] = False
		buttons['space_gui'] = False
		buttons[change] = True
		resizeButtons()

# needed so that the tabs won't be changed when clicking on a menu item
def tabSleep(evt,val):
	buttons['tab_sleep'] = sys.time()

# open a website with more help information
def openWeb(evt):
	if not browser:
		Draw.PupMenu("Error%t|Missing standard Python module: webbrowser")
		return
	link = False
	url = "http://sites.google.com/site/bartiuscrouch/scripts/looptools"
	if evt == but_evt['circle_help']:
		link = True
		url += "/circle"
	elif evt == but_evt['curve_help']:
		link = True
		url += "/curve"
	elif evt == but_evt['relax_help']:
		link = True
		url += "/relax"
	elif evt == but_evt['space_help']:
		link = True
		url += "/space"
	if link:
		try:
			webbrowser.open(url)
		except:
			Draw.PupMenu("Error%t|Webbrowser couldn't be opened")

# pop-up blocks to set the influence of the tools
def setInfluence(evt):
	block = []
	if evt == but_evt['circle_f']:
		block.append(("Influence: ", buttons['circle_influence'], 0, 100))
		block.append(("0 = no circle, 100 = full circle"))
	elif evt == but_evt['curve_f']:
		block.append(("Influence: ", buttons['curve_influence'], 0, 100))
		block.append(("0 = no effect, 100 = full effect"))
	elif evt == but_evt['space_f']:
		block.append(("Influence: ", buttons['space_influence'], 0, 100))
		block.append(("0 = no effect, 100 = full effect"))
	response = Draw.PupBlock("Set influence", block)

# GUI and button values
buttons = {
	'default_zoom': 1.0,
	'default_margin': 10,
	'default_height': 20,
	'default_width': 50,
	'default_offset_x': 0,
	'default_offset_y': 0,
	'default_sensitivity': 1.0,
	
	'zoom': 1.0,
	'margin': 10,
	'height': 20,
	'width': 50,
	'offset_x': 0,
	'offset_y': 0,
	'sensitivity': 1.0,
	'mouse': False,
	'tab_sleep': False,
	
	'circle_reg': Draw.Create(True),
	'circle_all': Draw.Create(False),
	'circle_sel': Draw.Create(True),
	'circle_bestfit': Draw.Create(True),
	'circle_fitinside': Draw.Create(False),
	'circle_forcer': Draw.Create(False),
	'circle_radius': Draw.Create(1.0),
	'circle_influence': Draw.Create(100),
	'circle_project': Draw.Create(False),
	'circle_gui': True,
	
	'curve_reg': Draw.Create(True),
	'curve_cubic': Draw.Create(True),
	'curve_linear': Draw.Create(False),
	'curve_restrict': Draw.Create(False),
	'curve_plus': Draw.Create(True),
	'curve_min': Draw.Create(False),
	'curve_influence': Draw.Create(100),
	'curve_add': False,
	'curve_gui': False,
	
	'relax_reg': Draw.Create(True),
	'relax_all': Draw.Create(False),
	'relax_sel': Draw.Create(True),
	'relax_cubic': Draw.Create(True),
	'relax_linear': Draw.Create(False),
	'relax_iter': Draw.Create(1),
	'relax_add': False,
	'relax_gui': False,
	
	'space_all': Draw.Create(False),
	'space_sel': Draw.Create(True),
	'space_cubic': Draw.Create(True),
	'space_linear': Draw.Create(False),
	'space_influence': Draw.Create(100),
	'space_add': False,
	'space_gui': False
}
buttons['total_height'] = 4*buttons['height']+4*buttons['margin']+18
buttons['total_width'] = max(4*buttons['width']+1, int(buttons['width']/2.0)+2*max(15,int(buttons['height']/2.0))+2*buttons['width']+5*buttons['margin'])

# button event values
but_evt = {
	'circle': 1,
	'circle_reg': 2,
	'circle_all': 3,
	'circle_sel': 4,
	'circle_bestfit': 5,
	'circle_fitinside': 6,
	'circle_forcer': 7,
	'circle_radius': 8,
	'circle_influence': 9,
	'circle_f': 10,
	'circle_project': 11,
	'circle_help': 12,
	
	'curve': 21,
	'curve_reg': 22,
	'curve_cubic': 23,
	'curve_linear': 24,
	'curve_restrict': 25,
	'curve_plus': 26,
	'curve_min': 27,
	'curve_influence': 28,
	'curve_f': 29,
	'curve_done': 30,
	'curve_cancel': 31,
	'curve_help': 32,
	
	'relax': 41,
	'relax_reg': 42,
	'relax_all': 43,
	'relax_sel': 44,
	'relax_cubic': 45,
	'relax_linear': 46,
	'relax_iter': 47,
	'relax_done': 48,
	'relax_cancel': 49,
	'relax_help': 50,
	
	'space': 61,
	'space_all': 62,
	'space_sel': 63,
	'space_cubic': 64,
	'space_linear': 65,
	'space_influence': 66,
	'space_f': 67,
	'space_done': 68,
	'space_cancel': 69,
	'space_help': 70,
	
	'exit': 99
}

# radiobutton pairings
radio_buttons = {
	but_evt['circle_all']: ['circle_sel'],
	but_evt['circle_sel']: ['circle_all'],
	but_evt['circle_bestfit']: ['circle_fitinside'],
	but_evt['circle_fitinside']: ['circle_bestfit'],
	but_evt['curve_cubic']: ['curve_linear'],
	but_evt['curve_linear']: ['curve_cubic'],
	but_evt['curve_plus']: ['curve_min'],
	but_evt['curve_min']: ['curve_plus'],
	but_evt['relax_all']: ['relax_sel'],
	but_evt['relax_sel']: ['relax_all'],
	but_evt['relax_cubic']: ['relax_linear'],
	but_evt['relax_linear']: ['relax_cubic'],
	but_evt['space_all']: ['space_sel'],
	but_evt['space_sel']: ['space_all'],
	but_evt['space_cubic']: ['space_linear'],
	but_evt['space_linear']: ['space_cubic']
}

def gui():
	# just some short-named variables to save typing
	win_x, win_y = Window.GetAreaSize()
	tw = buttons['total_width']
	th = buttons['total_height']
	x = int((win_x - tw) / 2.0) + buttons['offset_x']
	y = int((win_y - th) / 2.0) + buttons['offset_y']
	m = buttons['margin']
	w = buttons['width']
	h = buttons['height']
	tabh = 18
	sw = int(w/2.0)
	sh = max(15, int(h/2.0))
	xsw = max(18, int((1.5*w)/5.0))
	xxsw = max(12, int((1.5*w)/5.0))
	
	# outer black line
	BGL.glColor3f(0.0, 0.0, 0.0)
	BGL.glRecti(x, y, x+tw, y+th)
	# main white area
	BGL.glColor3f(1.0, 1.0, 1.0)
	BGL.glRecti(x+1, y+1, x+tw-1, y+th-1)
	
	# TABS
	# black line underneath tabs
	BGL.glColor3f(0.0, 0.0, 0.0)
	BGL.glRecti(x, y+th-h-tabh-m-1, x+tw, y+th-h-tabh-m)
	# light grey tabs
	BGL.glColor3f(0.8, 0.8, 0.8)
	BGL.glRecti(x+1, y+th-h-tabh-m, x+tw-1, y+th-h-m)
	# white tabs
	BGL.glColor3f(1.0, 1.0, 1.0)
	BGL.glRecti(x+1, y+th-h-tabh-m, x+w, y+th-h-m-1)
	BGL.glRecti(x+w+1, y+th-h-tabh-m, x+2*w, y+th-h-m-1)
	BGL.glRecti(x+2*w+1, y+th-h-tabh-m, x+3*w, y+th-h-m-1)
	BGL.glRecti(x+3*w+1, y+th-h-tabh-m, x+4*w, y+th-h-m-1)
	if x+4*w+1 < tw+x-1:
		BGL.glRecti(x+4*w+1, y+th-h-tabh-m, tw+x-1, y+th-h-m)
	# active tab
	BGL.glColor3f(0.0, 0.0, 0.0)
	if buttons['circle_gui']:
		BGL.glRecti(x, y+th-h-tabh-m, x+w+1, y+th-h-m)
		BGL.glColor3f(1.0, 1.0, 1.0)
		BGL.glRecti(x+1, y+th-h-tabh-m-1, x+w, y+th-h-m-1)
	elif buttons['curve_gui']:
		BGL.glRecti(x+w, y+th-h-tabh-m, x+2*w+1, y+th-h-m)
		BGL.glColor3f(1.0, 1.0, 1.0)
		BGL.glRecti(x+w+1, y+th-h-tabh-m-1, x+2*w, y+th-h-m-1)
	elif buttons['relax_gui']:
		BGL.glRecti(x+2*w, y+th-h-tabh-m, x+3*w+1, y+th-h-m)
		BGL.glColor3f(1.0, 1.0, 1.0)
		BGL.glRecti(x+2*w+1, y+th-h-tabh-m-1, x+3*w, y+th-h-m-1)
	elif buttons['space_gui']:
		BGL.glRecti(x+3*w, y+th-h-tabh-m, x+4*w+1, y+th-h-m)
		BGL.glColor3f(1.0, 1.0, 1.0)
		BGL.glRecti(x+3*w+1, y+th-h-tabh-m-1, x+4*w, y+th-h-m-1)
	# texts
	BGL.glColor3f(0.0, 0.0, 0.0)
	str_x = int((w-Draw.GetStringWidth("Circle", 'normal'))/2.0)
	BGL.glRasterPos2i(x+1+str_x, y+th-h-tabh-m+4)
	Draw.Text("Circle", 'normal')
	str_x = int((w-Draw.GetStringWidth("Curve", 'normal'))/2.0)
	BGL.glRasterPos2i(x+w+1+str_x, y+th-h-tabh-m+4)
	Draw.Text("Curve", 'normal')
	str_x = int((w-Draw.GetStringWidth("Relax", 'normal'))/2.0)
	BGL.glRasterPos2i(x+2*w+1+str_x, y+th-h-tabh-m+4)
	Draw.Text("Relax", 'normal')
	str_x = int((w-Draw.GetStringWidth("Space", 'normal'))/2.0)
	BGL.glRasterPos2i(x+3*w+1+str_x, y+th-h-tabh-m+4)
	Draw.Text("Space", 'normal')
	BGL.glColor3f(0.0, 0.8, 0.8)
	BGL.glRasterPos2i(x+m, y+th-h)
	Draw.Text("LoopTools "+__version__.split()[0], 'large')
	
	# tool specific buttons
	if buttons['curve_add']:
		curve_done_but = Draw.PushButton("Done", but_evt['curve_done'], x+m, y+2*h+2*m, w, h, "Select an additional vertex on the intended edge loop")
		curve_cancel_but = Draw.PushButton("Cancel", but_evt['curve_cancel'], x+2*m+w, y+2*h+2*m, w, h, "Cancel action and return to main menu")
		curve_help = Draw.PushButton("?", but_evt['curve_help'], x+tw-2*int(h*0.75)-int(0.5*m), y+th-int(h*0.75)-int(0.5*m), int(h*0.75), int(h*0.75), "Click for online help on the curve tool")
	elif buttons['relax_add']:
		relax_done_but = Draw.PushButton("Done", but_evt['relax_done'], x+m, y+2*h+2*m, w, h, "Select an additional vertex on the intended edge loop")
		relax_cancel_but = Draw.PushButton("Cancel", but_evt['relax_cancel'], x+2*m+w, y+2*h+2*m, w, h, "Cancel action and return to main menu")
		relax_help = Draw.PushButton("?", but_evt['relax_help'], x+tw-2*int(h*0.75)-int(0.5*m), y+th-int(h*0.75)-int(0.5*m), int(h*0.75), int(h*0.75), "Click for online help on the relax tool")
	elif buttons['space_add']:
		space_done_but = Draw.PushButton("Done", but_evt['space_done'], x+m, y+h+m, w, h, "Select an additional vertex on the intendede edge loop")
		space_cancel_but = Draw.PushButton("Cancel", but_evt['space_cancel'], x+2*m+w, y+h+m, w, h, "Cancel action and return to main menu")
		space_help = Draw.PushButton("?", but_evt['space_help'], x+tw-2*int(h*0.75)-int(0.5*m), y+th-int(h*0.75)-int(0.5*m), int(h*0.75), int(h*0.75), "Click for online help on the space tool")

	elif buttons['circle_gui']:
		circle_but = Draw.PushButton("Go", but_evt['circle'], x+m, y+h+m-sh, w, h, "Move vertices of the loop into a circular shape")
		buttons['circle_all'] = Draw.Toggle("all", but_evt['circle_all'], x+m, y+2*h+2*m, sw, sh, buttons['circle_all'].val, "Act upon all edgeloops that are parallel to the selected one")
		buttons['circle_sel'] = Draw.Toggle("sel", but_evt['circle_sel'], x+m, y+2*h+2*m-sh, sw, sh, buttons['circle_sel'].val, "Act only upon the selected edgeloop(s)")
		buttons['circle_bestfit'] = Draw.Toggle("best fit", but_evt['circle_bestfit'], x+sw+2*m, y+2*h+2*m, w, sh, buttons['circle_bestfit'].val, "Calculate a circle that best fits all the vertices")
		buttons['circle_fitinside'] = Draw.Toggle("fit inside", but_evt['circle_fitinside'], x+sw+2*m, y+2*h+2*m-sh, w, sh, buttons['circle_fitinside'].val, "Calculate a circle so that none of the vertices will be moved outwards")
		if not buttons['circle_forcer'].val:
			buttons['circle_forcer'] = Draw.Toggle("radius", but_evt['circle_forcer'], x+w+sw+3*m, y+int(1.5*h)+2*m, w, h, buttons['circle_forcer'].val, "Force the circle to have the radius as defined by the user")
		else:
			buttons['circle_forcer'] = Draw.Toggle("radius", but_evt['circle_forcer'], x+w+sw+3*m, y+2*h+2*m, w, sh, buttons['circle_forcer'].val, "Force the circle to have the radius as defined by the user")
			buttons['circle_radius'] = Draw.Number("", but_evt['circle_radius'], x+w+sw+3*m, y+2*h+2*m-sh, w, sh, buttons['circle_radius'].val, 0.001, 1000.0, "Radius of the circle, overrides the radius calculated by the script")
		circle_f = Draw.PushButton("F", but_evt['circle_f'], x+w+m, y+h+m-sh, int(0.75*h), h, "Influence of the tool (Force) = "+str(buttons['circle_influence'].val))
		buttons['circle_project'] = Draw.Toggle("project", but_evt['circle_project'], x+w+int(0.75*h)+2*m, y+h+m-sh, w, h, buttons['circle_project'].val, "Project the circle on the existing mesh, instead of having a flat circle")
		buttons['circle_reg'] = Draw.Toggle("regular", but_evt['circle_reg'], x+2*w+int(0.75*h)+3*m, y+h+m-sh, w, h, buttons['circle_reg'].val, "Distribute vertices at constant distances along the circle")
		circle_help = Draw.PushButton("?", but_evt['circle_help'], x+tw-2*int(h*0.75)-int(0.5*m), y+th-int(h*0.75)-int(0.5*m), int(h*0.75), int(h*0.75), "Click for online help on the circle tool")
	elif buttons['curve_gui']:
		curve_but = Draw.PushButton("Go", but_evt['curve'], x+m, y+h+m-sh, w, h, "Change an edge loop into a smooth curve")
		buttons['curve_cubic'] = Draw.Toggle("cubic", but_evt['curve_cubic'], x+m, y+2*h+2*m, w, sh, buttons['curve_cubic'].val, "Curves will be calculated using a natural cubic spline algorithm (gives smoother results)")
		buttons['curve_linear'] = Draw.Toggle("linear", but_evt['curve_linear'], x+m, y+2*h+2*m-sh, w, sh, buttons['curve_linear'].val, "Vertices will be projected on straight lines")
		if not buttons['curve_restrict'].val:
			buttons['curve_restrict'] = Draw.Toggle("restrict", but_evt['curve_restrict'], x+w+2*m, y+int(1.5*h)+2*m, w, h, buttons['curve_restrict'].val, "Allow the vertices to move only one way. Either away from the mesh, or towards it")
		else:
			buttons['curve_restrict'] = Draw.Toggle("restrict", but_evt['curve_restrict'], x+w+2*m, y+2*h+2*m, w, sh, buttons['curve_restrict'].val, "Allow the vertices to move only one way. Either away from the mesh, or towards it")
			buttons['curve_plus'] = Draw.Toggle("+", but_evt['curve_plus'], x+w+2*m, y+2*h+2*m-sh, sw, sh, buttons['curve_plus'].val, "Restrict vertex movement to extrusions (indentations of the mesh are blocked)")
			buttons['curve_min'] = Draw.Toggle("-", but_evt['curve_min'], x+w+2*m+sw, y+2*h+2*m-sh, sw, sh, buttons['curve_min'].val, "Restrict vertex movement to indentations (extrusions of the mesh are blocked)")
		buttons['curve_reg'] = Draw.Toggle("regular", but_evt['curve_reg'], x+2*w+3*m, y+int(1.5*h)+2*m, w, h, buttons['curve_reg'].val, "Use a regular distribution to place vertices along the curve")
		curve_f = Draw.PushButton("F", but_evt['curve_f'], x+w+m, y+h+m-sh, int(0.75*h), h, "Influence of the tool (Force) = "+str(buttons['curve_influence'].val))
		curve_help = Draw.PushButton("?", but_evt['curve_help'], x+tw-2*int(h*0.75)-int(0.5*m), y+th-int(h*0.75)-int(0.5*m), int(h*0.75), int(h*0.75), "Click for online help on the curve tool")
	elif buttons['relax_gui']:
		relax_but = Draw.PushButton("Go", but_evt['relax'], x+m, y+h+m-sh, w, h, "Relax the loop, so it will be smoother")
		buttons['relax_all'] = Draw.Toggle("all", but_evt['relax_all'], x+m, y+2*h+2*m, sw, sh, buttons['relax_all'].val, "Act upon all edgeloops that are parallel to the selected one")
		buttons['relax_sel'] = Draw.Toggle("sel", but_evt['relax_sel'], x+m, y+2*h+2*m-sh, sw, sh, buttons['relax_sel'].val, "Act only upon the selected vertices")
		buttons['relax_cubic'] = Draw.Toggle("cubic", but_evt['relax_cubic'], x+sw+2*m, y+2*h+2*m, w, sh, buttons['relax_cubic'].val, "New loops will be calculated using a natural cubic spline algorithm (gives smoother results)")
		buttons['relax_linear'] = Draw.Toggle("linear", but_evt['relax_linear'], x+sw+2*m, y+2*h+2*m-sh, w, sh, buttons['relax_linear'].val, "New loops will be calculated using a simple linear algorithm")
		buttons['relax_reg'] = Draw.Toggle("regular", but_evt['relax_reg'], x+w+sw+3*m, y+int(1.5*h)+2*m, w, h, buttons['relax_reg'].val, "Distances between verts will be equalised")
		buttons['relax_iter'] = Draw.Menu("Iterations%t|1%x1|3%x3|5%x5|10%x10|25%x25", but_evt['relax_iter'], x+w+2*m, y+m+h-sh, w, h, buttons['relax_iter'].val, "Number of times the tool is run", tabSleep)
		relax_help = Draw.PushButton("?", but_evt['relax_help'], x+tw-2*int(h*0.75)-int(0.5*m), y+th-int(h*0.75)-int(0.5*m), int(h*0.75), int(h*0.75), "Click for online help on the relax tool")
	elif buttons['space_gui']:
		space_but = Draw.PushButton("Go", but_evt['space'], x+m, y+int(0.5*h)+m, w, h, "Space the vertices of the loop to give them a regular distribution")
		buttons['space_all'] = Draw.Toggle("all", but_evt['space_all'], x+w+int(0.75*h)+2*m, y+h+m, sw, sh, buttons['space_all'].val, "Act upon all edgeloops that are parallel to the selected one")
		buttons['space_sel'] = Draw.Toggle("sel", but_evt['space_sel'], x+w+int(0.75*h)+2*m, y+h+m-sh, sw, sh, buttons['space_sel'].val, "Act only upon the selected vertices")
		buttons['space_cubic'] = Draw.Toggle("cubic", but_evt['space_cubic'], x+w+int(0.75*h)+sw+3*m, y+h+m, w, sh, buttons['space_cubic'].val, "Vertices will be projected on a natural cubic spline (gives smoother results)")
		buttons['space_linear'] = Draw.Toggle("linear", but_evt['space_linear'], x+w+int(0.75*h)+sw+3*m, y+h+m-sh, w, sh, buttons['space_linear'].val, "Vertices will be projected on the existing edges")
		space_f = Draw.PushButton("F", but_evt['space_f'], x+w+m, y+int(0.5*h)+m, int(0.75*h), h, "Influence of the tool (Force) = "+str(buttons['space_influence'].val))
		space_help = Draw.PushButton("?", but_evt['space_help'], x+tw-2*int(h*0.75)-int(0.5*m), y+th-int(h*0.75)-int(0.5*m), int(h*0.75), int(h*0.75), "Click for online help on the space tool")
	
	# buttons that are always displayed
	exit_but = Draw.PushButton("x", but_evt['exit'], x+tw-int(h*0.75)-int(0.5*m), y+th-int(h*0.75)-int(0.5*m), int(h*0.75), int(h*0.75), "Exit this script")

def event(evt, val):
	if evt in [Draw.ESCKEY, Draw.QKEY, Draw.XKEY]:
		Draw.Exit()
	elif evt in [Draw.WHEELDOWNMOUSE, Draw.MINUSKEY, Draw.PADMINUS] and val:
		changeGui(False, -val)
	elif evt in [Draw.WHEELUPMOUSE, Draw.EQUALKEY, Draw.PADPLUSKEY] and val:
		changeGui(False, val)
	elif evt in [Draw.ZEROKEY, Draw.PADPERIOD, Draw.HOMEKEY] and val:
		changeGui(True, val)
	elif evt == Draw.MIDDLEMOUSE:
		dragmodeGui(val)
	elif evt == Draw.LEFTMOUSE and not val:
		changeTab()
	elif buttons['mouse']:
		if evt in [Draw.MOUSEX, Draw.MOUSEY]:
			dragGui()

def bevent(evt):
	if evt == but_evt['circle']:
		circleloop()
	elif evt == but_evt['curve']:
		curveloop(False)
	elif evt == but_evt['relax']:
		relaxloop(False)
	elif evt == but_evt['space']:
		spaceloop(False)
	elif evt in [but_evt['circle_forcer'], but_evt['curve_restrict']]:
		Draw.Redraw()
	elif evt in [but_evt['curve_done'], but_evt['relax_done'], but_evt['space_done']]:
		newAdditionalVertex()
	elif evt in [but_evt['curve_cancel'], but_evt['relax_cancel'], but_evt['space_cancel']]:
		cancelAdditionalVertex()
	elif evt in [but_evt['circle_help'], but_evt['curve_help'], but_evt['relax_help'], but_evt['space_help']]:
		openWeb(evt)
	elif evt in [but_evt['circle_f'], but_evt['curve_f'], but_evt['space_f']]:
		setInfluence(evt)
	elif evt in radio_buttons:
		changeRadio(evt)
	elif evt == but_evt['exit']:
		Draw.Exit()

Draw.Register(gui, event, bevent)