#!BPY
# -*- coding: latin-1 -*-
""" Registration info for Blender menus
Name: 'Connect Tools'
Blender: 248
Group: 'Mesh'
Submenu:'Connect' C
Submenu:'Glue' G
Submenu:'Merge' M
Tip: 'Connect, Glue or Merge Contours'
"""

######################################################################
# C Tools v1 for Blender
#
# This script proposes tree tools :
#	- Connect	: connect two conours
#	- Glue		: Erase the selected faces and connect the contours 
#	- Merge		: Erase the selected faces and merge the contours 
#
# Glue and merge can be used to transfom two adjacent face loops in a face loop
# or a vert loop.
#
# When the contours don't have the same number of verts, you can use two
# methods to choose where to make tris or quads :
#	- "Nearest" will connect a vertice to the nearest vertice possible
#	- "Optim" will look into all the possible ways to connect the two contours
#	and choose the best one. By best I mean the way which will minimize the sum
#	of the length of the created edges.
#
# "Nearest" is fast and sufficient in most of the cases, but "Optim" should
# give better results if the geometry is complex. 
#
# When only one contour is found, this script will try to split it in two.
# It will try to find the extremities of the new contours and testing all
# the possibiliries if it doesn't find anything. When the selected area is too
# wide or contains a lot of triangle, this guess can be wrong. You can force
# the script to test all the possibities without initialy guess by choosing the
# opimal method. Be careful : testing all these possibilitis can take a lot of time.
#
# (c) 2004 Loïc Berthe (loic.berthe@lilotux.net)
# originally released under Blender Artistic License
# --------------------------------------------------------------------------
# ***** BEGIN GPL LICENSE BLOCK *****
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software Foundation,
# Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
#
# ***** END GPL LICENCE BLOCK *****
# --------------------------------------------------------------------------
######################################################################

import Blender
from Blender import NMesh
from Blender.Draw import *
from Blender.BGL import *
arg = __script__['arg'] 

from UserList import UserList

######################################################################
# Here are the tools to analyse the mesh (VertHash) and create the contours
# (Contour)

def add2H(H,key,val):
	if key in H.keys():
		H[key].append(val)
	else:
		H[key] = [val]

def orient(eed):
	if eed[0].index > eed[1].index:
		eed.reverse()
	return tuple(eed)

class VertHash:
	""" This class is used to analyse the selected vertices.
		- V is a dictionnary {v : [other selected vertices linked to v]}
	where v stands for a selected vertice. It will be used to build the contours.
		- state is used to know if a vertice has already be used.
		- F is a dictionnary {v : [faces containing v]}. It will be used to
	merge contours."""
	def __init__(self):
		self.V = {}
		self.F = {}
		self.state = {}
	
	def add_v(self, ede):
		if ede[0] in self.V.keys():
			if ede[1] not in self.V[ede[0]]:
				self.V[ede[0]].append(ede[1])
		else:
			self.V[ede[0]]=[ede[1]]
		#
		if ede[1] in self.V.keys():
			if ede[0] not in self.V[ede[1]]:
				self.V[ede[1]].append(ede[0])
		else:
			self.V[ede[1]]=[ede[0]]
		#
		if ede[0] not in self.state.keys():
			self.state[ede[0]]=1
		if ede[1] not in self.state.keys():
			self.state[ede[1]]=1
	
	def add_f(self,list,f):
		for v in list: add2H(self.F,v,f)

	def add_mesh(self,mode=1):
		""" This is the heart of the analyse of the mesh
		If mode = 0, it won't take the selected faces into consideration and
		will mark them to be erased."""
		for f in me.faces:
			V = f.v
			selected = [x.sel for x in V]
			if len(selected) == 2:
				if selected == [1, 1]:
					self.add_v(V)
			elif len(selected) == 4:
				if selected == [1, 1, 1, 1]:
					if mode:
						map(self.add_v,[[V[0],V[1]],[V[1],V[2]],[V[2],V[3]],[V[3],V[0]]])
						self.add_f([V[0],V[1],V[2],V[3]],f)
					else :
						Old_faces.append(f)
				elif selected == [1, 1, 1, 0]:
					map(self.add_v,[[V[0],V[1]],[V[1],V[2]]])
					self.add_f([V[0],V[1],V[2]],f)
				elif selected == [1, 1, 0, 1]:
					map(self.add_v,[[V[0],V[1]],[V[3],V[0]]])
					self.add_f([V[0],V[1],V[3]],f)
				elif selected == [1, 0, 1, 1]:
					map(self.add_v,[[V[2],V[3]],[V[3],V[0]]])
					self.add_f([V[2],V[3],V[0]],f)
				elif selected == [0, 1, 1, 1]:
					map(self.add_v,[[V[2],V[3]],[V[1],V[2]]])
					self.add_f([V[2],V[3],V[1]],f)
				elif selected == [1, 1, 0, 0]:
					self.add_v([V[0],V[1]])
					self.add_f([V[0],V[1]],f)
				elif selected == [0, 1, 1, 0]:
					self.add_v([V[1],V[2]])
					self.add_f([V[1],V[2]],f)
				elif selected == [0, 0, 1, 1]:
					self.add_v([V[2],V[3]])
					self.add_f([V[2],V[3]],f)
				elif selected == [1, 0, 0, 1]:
					self.add_v([V[0],V[3]])		
					self.add_f([V[0],V[3]],f)		
				else:
					[self.add_f([v],f) for v in V if v.sel]
			elif len(selected) == 3:
				if selected == [1, 1, 1]:
					if mode :
						map(self.add_v,[[V[0],V[1]],[V[1],V[2]],[V[2],V[0]]])
						self.add_f([V[0],V[1],V[2]],f)
					else:
						Old_faces.append(f)
				elif selected == [1, 1, 0]:
					self.add_v([V[0],V[1]])
					self.add_f([V[0],V[1]],f)
				elif selected == [1, 0, 1]:
					self.add_v([V[2],V[0]])
					self.add_f([V[2],V[0]],f)
				elif selected == [0, 1, 1]:
					self.add_v([V[1],V[2]])
					self.add_f([V[1],V[2]],f)
				else:
					[self.add_f([v],f) for v in V if v.sel]
	
	def __repr__(self):
		return "H :\n"+'\n'.join([str(v.index)+' ('+str(self.state[v])+') :'\
		+str([x.index for x in self.V[v]]) for v in self.V.keys()])

class Contour(UserList):
	""" This class stand for a contour.""" 
	def __init__(self, initlist=None):
		UserList.__init__(self,initlist)
		self.is_closed = self and self[0] == self[-1]
		#
	def get_list_from_vh(self,vh):
		if 1 not in vh.state.values():	return
		for v in vh.V.keys():
			if len(vh.V[v]) == 1 and vh.state[v]==1:
				break
		if vh.state[v] == 0 :
			for v in vh.V.keys():
				if vh.state[v]==1:
					break
		while vh.state[v]:
			self.append(v)
			vh.state[v]=0
			for vn in vh.V[v]:
				if vh.state[vn]:
					v = vn
					break
		#
		self.is_closed =  self[0] in vh.V[self[-1]] and len(self) > 2
		#
		if self.is_closed:
			self.append(self[0])
	#
	def __repr__(self):
		if self.is_closed: 	s = "Contour fermé : " 
		else: s = "Contour ouvert : " 
		return s+str([x.index for x in self])

######################################################################

def translate(list, k):
	return list[k:-1]+list[:k]+list[k:k+1]
		
def dist(a,b):
	s = 0.0
	for i in range(3):
		s += (a.co[i]- b.co[i])**2
	return s
	
def dist_total(b1,b2):
	""" Compute the sum of the length of the created edges when connecting b1 and b2."""
	i1,i2 = 0, 0
	s = 0.0
	#	
	q = len(b2) -1
	t = len(b1) -q -1
	#
	while (q>0 or t>0): 
		if q == 0 or (t > 0 and dist(b1[i1+1],b2[i2+1]) > \
					dist(b1[i1+1],b2[i2])) :
			i1+=1
			t-=1
			s += dist(b1[i1],b2[i2])
		else:
			i1+=1
			i2+=1
			q-=1
			s += dist(b1[i1],b2[i2])
	#
	return s

def get_nearest_u(nf,t,b1,b2):
	""" Find the simpler way to connect b1 and b2 with nf faces (including t triangles).
		Return a list u containing the position of the triangles."""
	u = []
	i = 0
	j = 0
	#
	q = nf-t
	#
	while (q>0 or t>0): 
		if q == 0 or (t > 0 and dist(b1[i+1],b2[j+1]) > \
					dist(b1[i+1],b2[j])) :
			u.append(i)
			t-=1
			i+=1
		else:
			q-=1
			i+=1
			j+=1
	#
	return u
	
def connect_u(u,nf,b1,b2):
	""" Make the differents faces """
	i1,i2 = 0,0
	#
	for i in xrange(nf):
		if i in u:
			f = NMesh.Face([b1[i1],b1[i1+1],b2[i2]])
			me.faces.append(f)
			i1+=1
		else:
			f = NMesh.Face([b1[i1],b1[i1+1],b2[i2+1],b2[i2]])
			me.faces.append(f)
			i1+=1
			i2+=1

######################################################################
# Optimal connect
# 
# To find the optimal connect, we will walk trough all the possibilities of making t triangles among nf faces.  
				
def dist_total_u(u,nf,b1,b2):
	""" Compute the sum of the length of the created edges when connecting b1 and b2.
	u contains the positions of the tri faces to be created."""
	i1,i2 = 0, 0
	s = 0.0
	#
	for i in range(nf):
		if	i in u:
			i1+=1
			s += dist(b1[i1],b2[i2])
		else:
			i1+=1
			i2+=1
			s += dist(b1[i1],b2[i2])
	#
	return s

def get_optim_u(nf,t,b1,b2):
	""" Find the way to make t triangles under nf faces connecting b1 and b2
	which minimizes the sum of the length of the created edges.
	To do so, we create a list u containing the position of the tri fraces
	and we analyse all the possible combinations. """
	nu = t-1
	u = range(nf-t,nf)
	#
	c0 = dist_total_u(u,nf,b1,b2)
	u0 = u[:]
	#
	if u :
		while u[nu] > nu:
			i = 0
			u[i] -= 1
			#
			while u[i] < i:
				i += 1
				u[i] -= 1
			#
			if i :
				for k in range(i):
					u[i-k-1] = u[i-k] -1
			#
			c = dist_total_u(u,nf,b1,b2)
			if c < c0:
				u0 = u[:]
				c0 = c
		#
	return (c0,u0)
				
######################################################################
# Merging tools

def pascal(k):
	""" Return the k-ieme line of Pascal's Triangle"""
	if k > 0:
		L = []
		l = pascal(k-1)
		L.append(l[0]/2)
		for i in range(k-1):
			L.append((l[i]+l[i+1])/2)
		L.append(l[0]/2)
	else:
		L = [1.0]
	return L

def merge(u,b1,b2):
	""" Merge b1 and b2 according to u"""
	# We need to build an equivalent of b1 (A), whose size equals those of b2
	# m is a list containing the number of edges of b1 to merge to obtain each element of A
	ia = 0
	m = []
	while ia < len(b1):
		im = 0
		while ia in u:
			im += 1
			ia += 1
		m.append(im)
		ia += 1
	#
	# Now we can make A easily :
	A = []
	ia = 0
	for im in m:
		if im:
			co = [0.0, 0.0, 0.0]
			b = b1[ia:ia+im+1]
			c = pascal(im)
			for i in range(im+1):
				for j in range(3):
					co[j] += c[i]*b[i].co[j]
			A.append(co)
			ia += im+1
		else:
			A.append(b1[ia].co)
			ia += 1
	#
	# We must have a way to rely the elements of b1 and A
	H = {}
	ia,k = 0,0
	for im in m:
		for i in range(im+1):
			H[b1[k]] = ia
			k += 1
		ia += 1	
	#
	if not b1.is_closed:
		A[0] = b1[0].co
		A[-1] = b1[-1].co
	#
	nb2 = len(b2)
	if b2.is_closed : nb2 -= 1
	for i in range(nb2):
		for k in range(3):
			b2[i].co[k] = (b2[i].co[k]+A[i][k])/2
	#
	Faces = []
	for v in b1:
		if vh.F.has_key(v):
			for f in vh.F[v]:
				if f not in Faces:Faces.append(f)
	#
	
	OldVerts = []
	if not Faces : OldVerts.extend(b1)

	for f in Faces:
		for i in range(len(f.v)):
			v = f.v[i]
			if v in H.keys():
				if v not in OldVerts and v not in b2 : OldVerts.append(v)
				f.v[i] = b2[H[v]]
		#
		for v in f.v:
			if v in f.v and f.v.count(v) > 1 :
				f.v.remove(v)
		#
		if len(f.v) < 3:
			me.faces.remove(f)
	##
	for v in OldVerts:
		me.verts.remove(v)
	
######################################################################
# Functions to split a contour

def get_extrem(l):
	ext = []
	#
	nl = len(l)
	n0,i = 0,0
	#
	while n0 < nl and l[n0] == 0:
		n0 += 1
	if n0 == nl-1 :
		return pair,impair
	l = l[n0:]+l[:n0]
	#
	while i < nl :
		n = 0
		while i < nl and l[i] != 0:
			i += 1
		while i < nl and l[i] == 0:
			i += 1
			n += 1
		#
		if n != 0 :
			if n%2 :
				ext.append((1,(n0+i-(n-1)/2-1)%nl))
			else:
				ext.append((0,(n0+i-n/2-1)%nl))
	#
	cmp = lambda a,b: a[1] - b[1]
	ext.sort(cmp)
	return ext

def spit_closed(b):
	VF = {}
	EF = {}
	FE = {}
	#
	if Old_faces and method != METHOD_OPTIM:
		# Try to guess where the extremities of the contours are. To do so, we
		# look into the faces to be erased for the faces that are the lower number
		# of neighbours. This method is not very efficient for wide area or area
		# containing a lot of triangle, but if you find any better way to guess
		# where these extremities are, please lt me know. 
		for f in Old_faces:
			V = f.v
			for v in V : add2H(VF,v,f)
			#
			if len(V) == 4:
				edges = map(orient,[[V[0],V[1]],[V[1],V[2]],[V[2],V[3]],[V[0],V[3]]])
			else:
				edges = map(orient,[[V[0],V[1]],[V[1],V[2]],[V[2],V[0]]])
			#
			for eed in edges:
				add2H(EF,eed,f)
				add2H(FE,f,eed)
		#
		nb_f = {}
		for f in Old_faces:
			nb_f[f] =sum([len(EF[eed])-1 for eed in FE[f]])
		#
		nb = [max([nb_f[f] for f in VF[v]]) for v in b[:-1]]
		nb_ = min(nb)
		nb = [i - nb_ for i in nb]
		ext = get_extrem(nb)
		#
		d0 = None
		b_inv= b[:]
		b_inv.reverse()	
		nb_ext = len(ext)
		if nb_ext > 1:
			for i1 in range(nb_ext-1):
				for i2 in range(i1+1,nb_ext):
					(t1,k1)= ext[i1]
					(t2,k2)= ext[i2]
					if t1 and t2:
						b1=b[k1:k2+1]
						b2=b_inv[-k1-1:]+b_inv[1:-k2]
					elif t1 and not t2:
						b1=b[k1:k2+1]
						b2=b_inv[-k1-1:]+b_inv[1:-k2-1]
					elif not t1 and t2:
						b1=b[k1+1:k2+1]
						b2=b_inv[-k1-1:]+b_inv[1:-k2]
					else:
						b1=b[k1+1:k2+1]
						b2=b_inv[-k1-1:]+b_inv[1:-k2-1]
					#
					if len(b1) < len(b2) : b1,b2 = b2,b1
					d = dist_total(b1,b2)
					if d0 == None or d < d0:
						d0 = d
						b10 = b1[:]
						b20 = b2[:]
			#
			return b10, b20
	# Otherwise,
	# Test all the possibilities...
	d0 = None
	b_inv= b[:]
	b_inv.reverse()	
	for i1 in range(len(b)-2):
		for i2 in range(i1+1,len(b)-1):
			b1=b[i1:i2+1]
			b2=b_inv[-i1-1:]+b_inv[1:-i2]
			if len(b1) < len(b2) : b1,b2 = b2,b1
			d = dist_total(b1,b2)
			if d0 == None or d < d0:
				d0 = d
				b10 = b1[:]
				b20 = b2[:]
			#
			b1=b[i1:i2+1]
			b2=b_inv[-i1-1:]+b_inv[1:-i2-1]
			if len(b1) < len(b2) : b1,b2 = b2,b1
			d = dist_total(b1,b2)
			if d0 == None or d < d0:
				d0 = d
				b10 = b1[:]
				b20 = b2[:]
			#
			b1=b[i1+1:i2+1]
			b2=b_inv[-i1-1:]+b_inv[1:-i2]
			if len(b1) < len(b2) : b1,b2 = b2,b1
			d = dist_total(b1,b2)
			if d0 == None or d < d0:
				d0 = d
				b10 = b1[:]
				b20 = b2[:]
			#
			b1=b[i1+1:i2+1]
			b2=b_inv[-i1-1:]+b_inv[1:-i2-1]
			if len(b1) < len(b2) : b1,b2 = b2,b1
			d = dist_total(b1,b2)
			if d0 == None or d < d0:
				d0 = d
				b10 = b1[:]
				b20 = b2[:]
			#
	#
	return b10, b20

def split_open(b):
	nb = len(b)-1
	d0 = None
	b_inv= b[:]
	b_inv.reverse()	
	for i in range(nb):
		b1=b[:i+1]
		b2=b_inv[:nb-i]
		if len(b1) < len(b2) : b1,b2 = b2,b1
		d = dist_total(b1,b2)
		if d0 == None or d < d0:
			d0 = d
			b10 = b1[:]
			b20 = b2[:]
		#
		b1=b[:i+2]
		b2=b_inv[:nb-i]
		if len(b1) < len(b2) : b1,b2 = b2,b1
		d = dist_total(b1,b2)
		if d0 == None or d < d0:
			d0 = d
			b10 = b1[:]
			b20 = b2[:]
	#
	return b10, b20

	
######################################################################
def init(mode):
	global	obj,me, vh,Old_faces, editmode
	objs = Blender.Object.GetSelected()
	#
	if not objs or objs[0].getType() != "Mesh":
		PupMenu("Error| Select a mesh.")
		return
	#
	editmode = Blender.Window.EditMode()
	if editmode : Blender.Window.EditMode(0)
	obj = objs[0]
	me = NMesh.GetRaw(obj.data.name)
	#
	vh = VertHash()
	Old_faces = []
	vh.add_mesh(mode)
	#
	b1 = Contour()
	b1.get_list_from_vh(vh)
	#
	if 1 not in vh.state.values():		# We have already used all the vertices
		if b1.is_closed:
			(b1,b2) = spit_closed(b1)
		else:
			(b1,b2) = split_open(b1)
	else :
		b2 = Contour()
		b2.get_list_from_vh(vh)
		#
		for s in vh.state.values():
			if s :
				PupMenu("Warning|Some vertices have not been taken into account")
				break
		#
		#----------------------
		# Arrange the contours. 
		if (not b1.is_closed and not b2.is_closed):
			if len(b2) > len(b1):
				b1, b2 = b2,b1
			#
			min_1 = dist(b1[0],b2[0])+dist_total(b1,b2)
			b2.reverse()
			min_2 = dist(b1[0],b2[-1])+dist_total(b1,b2)
			#
			if min_1 < min_2 :
				b2.reverse()
		else :
			if not b1.is_closed:
				b1 = b1 + b1[::-1][1:]
			elif not b2.is_closed:
				b2 = b2 + b2[::-1][1:]
			#
			if len(b2) > len(b1):
				b1, b2 = b2,b1
			# 
			min_1 = min([(dist_total(translate(b1, k),b2),k) for k in range(len(b1)-1)])
			b1.reverse()
			min_2 = min([(dist_total(translate(b1, k),b2),k) for k in range(len(b1)-1)])
			#
			if min_1 < min_2:
				b1.reverse()
				b1 = translate(b1,min_1[1])
			else :
				b1 = translate(b1,min_2[1])
			#
	#----------------
	#	
	# Number of faces and of tri faces to make :
	nf,t = len(b1)-1, len(b1)-len(b2)
	#
	if method == METHOD_OPTIM:
		(d,u) = get_optim_u(nf,t,b1,b2)
	#
	elif method == METHOD_NEAREST:
		u = get_nearest_u(nf,t,b1,b2)
	#
	return u,nf,b1,b2
	
def finish():
	if Old_faces:
		for f in Old_faces:
			me.faces.remove(f)
		vsel = [v for v in me.verts if v.sel]
		for v in vsel:
			if v not in vh.state.keys():
				me.verts.remove(v)
	#
	me.update(1)
	obj.makeDisplayList()
	if editmode : Blender.Window.EditMode(1)
	Blender.Redraw()

######################################################################
# Main
METHOD_NEAREST = 1
METHOD_OPTIM = 2

	
method = PupMenu('Method: %t|Nearest %x1|Optimal %x2')
#

if  arg == 'C':					# Connect
	(u,nf, b1, b2) = init(mode=1)
	connect_u(u,nf,b1,b2)
	finish()
#
elif  arg == 'G':				# Glue
	(u,nf, b1, b2) = init(mode=0)
	connect_u(u,nf,b1,b2)
	finish()
#
elif  arg == 'M':				# Merge
	(u,nf, b1, b2) = init(mode=0)
	merge(u,b1,b2)
	finish()
