#!BPY

"""
Name: 'Triangles to Quads'
Blender: 240
Group: 'Mesh'
Tooltip: 'Triangles to Quads for all selected mesh objects.'
"""

__author__ = "Campbell Barton AKA Ideasman"
__url__ = ["http://members.iinet.net.au/~cpbarton/ideasman/", "blender", "elysiun"]

__bpydoc__ = """\
This script joins any triangles into quads for all selected mesh objects.

Usage:

Select the mesh(es) and run this script. Mesh data will be edited in place.
so make a backup copy first if your not sure of the results

The limit value allows you to choose how pedantic the algorithum is when detecting errors between 2 triangles.
Over 50 could result in quads that are not correct.

The joining of quads takes into account UV mapping, UV Images and Vertex colours
and will not join faces that have mis-matching data.
"""

# ***** BEGIN GPL LICENSE BLOCK *****
#
# Script copyright (C) Campbell J Barton
#
# 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 *****
# --------------------------------------------------------------------------



from Blender import Scene, Object, Mathutils, Draw, Window, sys

TRI_LIST = (0,1,2)

vecAngle = Mathutils.AngleBetweenVecs
TriangleNormal = Mathutils.TriangleNormal

#=============================================================================#
# All measurement algorithums for face compatibility when joining into quads					 #
# every function returns a value between 0.0 and 1.0																	 #
#=============================================================================#
# total diff is 1.0, no diff is 0.0
# measure accross 2 possible triangles in the imagined quad.
def isfaceNoDiff(imagQuag):
	# Divide the quad one way and measure normals
	noA1 = TriangleNormal(imagQuag[0].co, imagQuag[1].co, imagQuag[2].co)
	noA2 = TriangleNormal(imagQuag[0].co, imagQuag[2].co, imagQuag[3].co)
	
	if noA1 == noA2:
		normalADiff = 0.0
	else:
		try:
			normalADiff = vecAngle(noA1, noA2)
		except:
			#print noA1, noA2
			normalADiff = 179
		
	#print normalADiff, noA1, noA2
	
	# Alternade division of the quad
	noB1 = TriangleNormal(imagQuag[1].co, imagQuag[2].co, imagQuag[3].co)
	noB2 = TriangleNormal(imagQuag[3].co, imagQuag[0].co, imagQuag[1].co)	
	if noB1 == noB2:
		normalBDiff = 0.0
	else:
		try:
			normalBDiff = vecAngle(noB1, noB2)
		except:
			# print noB1, noB2
			normalBDiff = 179
	
	# Should never be NAN anymore.
	'''
	if normalBDiff != normalBDiff or normalADiff != normalADiff:
		raise "NAN"
	'''
	# The greatest possible difference is 180 for each
	return (normalADiff/360) + (normalBDiff/360)


# 4 90d angles == 0, each corner diff from 90 is added together.
# 360 is total possible difference,
def isfaceCoLin(imagQuag): 
	
	edgeVec1 = imagQuag[0].co - imagQuag[1].co
	edgeVec2 = imagQuag[1].co - imagQuag[2].co
	edgeVec3 = imagQuag[2].co - imagQuag[3].co
	edgeVec4 = imagQuag[3].co - imagQuag[0].co
	
	# Work out how different from 90 each edge is.
	diff = 0
	try:
		diff = abs(vecAngle(edgeVec1, edgeVec2) - 90)
		diff = max(diff, abs(vecAngle(edgeVec2, edgeVec3) - 90))
		diff = max(diff, abs(vecAngle(edgeVec3, edgeVec4) - 90))
		diff = max(diff, abs(vecAngle(edgeVec4, edgeVec1) - 90))
	except:
		return 1.0
	
	# Avoid devide by 0
	if not diff:
		return 0.0
	
	return min(diff/90, 1.0)


# Meause the areas of the 2 possible ways of subdividing the imagined quad.
# if 1 is very different then the quad is concave.
# We should probably throw out any pairs that are at all concave,
# since even a slightly concacve paor will definetly be co linear.
# though even virging on this can be a recipe for a bad join.
def isfaceConcave(imagQuag):
	# Add the 2 areas the deviding one way
	areaA =\
	Mathutils.TriangleArea(imagQuag[0].co, imagQuag[1].co, imagQuag[2].co) +\
	Mathutils.TriangleArea(imagQuag[0].co, imagQuag[2].co, imagQuag[3].co)
	
	# Add the tri's triangulated the alternate way.
	areaB =\
	Mathutils.TriangleArea(imagQuag[1].co, imagQuag[2].co, imagQuag[3].co) +\
	Mathutils.TriangleArea(imagQuag[3].co, imagQuag[0].co, imagQuag[1].co)
	
	# Make a ratio of difference so they are between 1 and 0
	# Need to invert the value so 1.0 is 0
	minarea = min(areaA, areaB)
	maxarea = max(areaA, areaB)
	
	# Aviod devide by 0
	if maxarea == 0.0:
		return 1
	else:
		return 1 - (minarea / maxarea)



# This returns a list of verts, to test
# dosent modify the actual faces.
def meshJoinFacesTest(f1, f2, V1FREE, V2FREE): 
	# pretend face
	dummyFace = f1.v[:]
	
	# We know the 2 free verts. insert the f2 free vert in 
	if V1FREE is 0:
		dummyFace.insert(2, f2.v[V2FREE])
	elif V1FREE is 1:
		dummyFace.append(f2.v[V2FREE])
	elif V1FREE is 2:
		dummyFace.insert(1, f2.v[V2FREE])
	
	return dummyFace


# Measure how good a quad the 2 tris will make,
def measureFacePair(f1, f2, f1free, f2free, limit):
	# Make a imaginary quad. from 2 tris into 4 verts
	imagFace = meshJoinFacesTest(f1, f2, f1free, f2free)
	if imagFace is False:
		return False
	
	measure = 0 # start at 0, a lower value is better.
	
	# Do a series of tests,
	# each value will add to the measure value
	# and be between 0 and 1.0
	
	measure+= isfaceNoDiff(imagFace)/3
	if measure > limit: return False
	measure+= isfaceCoLin(imagFace)/3
	if measure > limit: return False
	measure+= isfaceConcave(imagFace)/3
	if measure > limit: return False
	
	'''
	# For debugging.
	
	a1= isfaceNoDiff(imagFace)
	a2= isfaceCoLin(imagFace)
	a3= isfaceConcave(imagFace)
	
	#print 'a1 NODIFF  %f' % a1
	#print 'a2 COLIN   %f' % a2
	#print 'a3 CONCAVE %f' % a3
	
	measure = (a1+a2+a3)/3
	if measure > limit: return False
	'''
	
	return [f1,f2, measure, f1free, f2free]


# We know the faces are good to join, simply execute the join
# by making f1 into a quad and f2 inde an edge (2 vert face.)
INSERT_LOOKUP = (2,3,1)
OTHER_LOOKUP = ((1,2),(0,2),(0,1))
def meshJoinFaces(f1, f2, V1FREE, V2FREE, mesh):
	
	# Only used if we have edges.
	# DEBUG
	edgeVert1, edgeVert2 = OTHER_LOOKUP[V1FREE]
	edgeVert1, edgeVert2 = f1[edgeVert1], f1[edgeVert2]
	
	
	fverts = f1.v[:]
	if mesh.hasFaceUV():
		fuvs = f1.uv[:]
	if f1.col:
		fcols = f1.col[:]
		
	
	# We know the 2 free verts. insert the f2 free vert in 
	# Work out which vert to insert
	i = INSERT_LOOKUP[V1FREE]
	
	# Insert the vert in the desired location.
	fverts.insert(i, f2.v[V2FREE])
	if mesh.hasFaceUV():
		fuvs.insert(i, f2.uv[V2FREE])
	if f1.col:
		fcols.insert(i, f2.col[V2FREE])		
	
	# Assign the data to the faces.
	f1.v = fverts
	if mesh.hasFaceUV():
		f1.uv = fuvs
	if f1.col:
		f1.col = fcols
	
	# Make an edge from the 2nd vert.
	# removing anything other then the free vert will
	# remove the edge from accress the new quad
	f2.v.pop(not V2FREE)
	
	mesh.removeEdge(edgeVert1, edgeVert2)
	#return f2



def compare2(v1, v2, limit):
	if v1[0] + limit > v2[0] and v1[0] - limit < v2[0] and\
	v1[1] + limit > v2[1] and v1[1] - limit < v2[1]:
				return True
	return False


def compare3(v1, v2, limit):
	if v1[0] + limit > v2[0] and v1[0] - limit < v2[0] and\
	v1[1] + limit > v2[1] and v1[1] - limit < v2[1] and\
	v1[2] + limit > v2[2] and v1[2] - limit < v2[2]:
		return True
	return False


UV_LIMIT = 0.005 # 0.0 to 1.0, can be greater then these bounds tho
def compareFaceUV(f1, f2):
	if f1.image == None and f1.image == None:
		# No Image, ignore uv's
		return True
	elif f1.image != f2.image:
		# Images differ, dont join faces.
		return False
	
	# We know 2 of these will match.
	for v1i in TRI_LIST:
		for v2i in TRI_LIST:
			if f1[v1i] is f2[v2i]:
				# We have a vertex index match.
				# now match the UV's
				if not compare2(f1.uv[v1i], f2.uv[v2i], UV_LIMIT):
					# UV's are different
					return False
	
	return True


COL_LIMIT = 3 # 0 to 255
def compareFaceCol(f1, f2):
	# We know 2 of these will match.
	for v1i in TRI_LIST:
		for v2i in TRI_LIST:
			if f1[v1i] is f2[v2i]:
				# We have a vertex index match.
				# now match the UV's
				if not compare3(f1.col[v1i], f2.col[v2i], COL_LIMIT):
					# UV's are different
					return False
					
	return True	

def tri2quad(mesh, limit, selectedFacesOnly, respectUVs, respectVCols):
	print '\nStarting tri2quad for mesh: %s' % mesh.name
	print '\t...finding pairs'
	time1 = sys.time()	# Time the function
	pairCount = 0
	
	# each item in this list will be a list
	# [face1, face2, measureFacePairValue]
	facePairLs = [] 
	
	if selectedFacesOnly:
		faceList = [f for f in mesh.faces if f.sel if len(f) is 3 if not f.hide]
	else:
		faceList = [f for f in mesh.faces if len(f) == 3]
	
	# Set if applicable for this mesh.
	has_face_uv= has_vert_col = False
	if respectUVs:
		has_face_uv = mesh.hasFaceUV()
	if respectVCols:
		has_vert_col = mesh.hasVertexColours() 
	
	
	# Build a list of edges and tris that use those edges.
	# This is so its faster to find tri pairs.
	edgeFaceUsers = {}
	for f in faceList:
		
		edkey1a= edkey3b= f.v[0].index
		edkey1b= edkey2a= f.v[1].index
		edkey2b= edkey3a= f.v[2].index
		
		if edkey1a > edkey1b:  edkey1a, edkey1b = edkey1b, edkey1a
		if edkey2a > edkey2b:  edkey2a, edkey2b = edkey2b, edkey2a
		if edkey3a > edkey3b:  edkey3a, edkey3b = edkey3b, edkey3a
		
		# The second int in the tuple is the free vert, its easier to store then to work it out again.
		try: edgeFaceUsers[edkey1a, edkey1b].append((f, 2))
		except:	edgeFaceUsers[edkey1a, edkey1b] = [(f, 2)]
		
		try: edgeFaceUsers[edkey2a, edkey2b].append((f, 0))
		except:	edgeFaceUsers[edkey2a, edkey2b] = [(f, 0)]
		
		try: edgeFaceUsers[edkey3a, edkey3b].append((f, 1))
		except:	edgeFaceUsers[edkey3a, edkey3b] = [(f, 1)]
	
	
	edgeDoneCount = 0
	for faceListEdgeShared in edgeFaceUsers.itervalues():
		if len(faceListEdgeShared) == 2:
			f1, f1free = faceListEdgeShared[0]
			f2, f2free = faceListEdgeShared[1]
			
			if f1.mat != f2.mat:
				pass # faces have different materials.
			elif has_face_uv and (not compareFaceUV(f1, f2)):
				pass # UV's are there but dont match.
			elif has_vert_col and not compareFaceCol(f1, f2):
				pass # Colours are there but dont match.
			else:
				# We can now store the qpair and measure
				# there eligability for becoming 1 quad.
				pair = measureFacePair(f1, f2, f1free, f2free, limit)
				#if pair is not False and pair[2] < limit: # Some terraible error
				if pair is not False: # False means its above the limit.
					facePairLs.append(pair)
					pairCount += 1
			
			edgeDoneCount += 1
			if not edgeDoneCount % 20:
				p = float(edgeDoneCount) / len(edgeFaceUsers)
				Window.DrawProgressBar(p*0.5, 'Found pairs: %i' % pairCount)
	
	
	# Sort, best options first :)
	facePairLs.sort(lambda a,b: cmp(a[2], b[2]))
	draws = 0
	print '\t...joining pairs'
	joinCount = 0
	len_facePairLs = len(facePairLs)
	
	#faces_to_remove = []
	
	for pIdx, pair in enumerate(facePairLs):
		# We know the last item is the best option, and no other face pairs will get in the way.
		# now join the faces.
		
		# If any of the faces have alredy been used then they will not have a lengh of 3 verts
		if len(pair[0]) is 3 and len(pair[1]) is 3:
			joinCount +=1
			# print 'joining faces', joinCount, 'Limit:', facePairLs[-1][2]
			#faces_to_remove.append( meshJoinFaces(pair[0], pair[1], mesh) )
			meshJoinFaces(pair[0], pair[1], pair[3], pair[4], mesh)
			
			if not pIdx % 20:
				p = (0.5 + ((float((len_facePairLs - (len_facePairLs - pIdx))))/len_facePairLs*0.5)) * 0.99
				Window.DrawProgressBar(p, 'Joining Face count: %i of %i' % (joinCount, len_facePairLs))
				draws +=1
				
	# print 'Draws', draws
	
	# Remove faces, due to a bug in ZR's new BF-Blender CVS
	
	fIdx = len(mesh.faces)
	while fIdx:
		fIdx -=1
		if len(mesh.faces[fIdx]) < 3:
			mesh.faces.pop(fIdx)	
	
	if joinCount:
		print "tri2quad time for %s: %s	joined %s tri's into quads" % (mesh.name, sys.time()-time1, joinCount)
		
		#mesh.update(0, (mesh.edges != []), 0)
		mesh.update(0, 0, 0)
		
	else:
		print "tri2quad nothing done %s: %s	joined none" % (mesh.name, sys.time()-time1)
		


#====================================#
# Sanity checks                      #
#====================================#
def error(str):
	Draw.PupMenu('ERROR%t|'+str)

def main():
	scn= Scene.GetCurrent()
	
	#selection = Object.Get()
	selection = Object.GetSelected()
	actob = scn.getActiveObject()
	if not actob.sel:
		selection.append(actob)
	
	if len(selection) is 0:
		error('No object selected')
		return

	#	GET UNIQUE MESHES.
	meshDict = {}
	# Mesh names
	for ob in selection:
		if ob.getType() == 'Mesh':
			meshDict[ob.getData(1)] = ob # dont do doubles.
	
	# Create the variables.
	selectedFacesOnly = Draw.Create(1)
	respectUVs = Draw.Create(1)
	respectVCols = Draw.Create(1)
	limit = Draw.Create(25)
	
	
	pup_block = [\
	('Selected Faces Only', selectedFacesOnly, 'Use only selected faces from all selected meshes.'),\
	('UV Delimit', respectUVs, 'Only join pairs that have matching UVs on the joining edge.'),\
	('VCol Delimit', respectVCols, 'Only join pairs that have matching Vert Colors on the joining edge.'),\
	('Limit: ', limit, 1, 100, 'A higher value will join more tris to quads, even if the quads are not perfect.'),\
	]
	
	if not Draw.PupBlock('Tri2Quad for %i mesh object(s)' % len(meshDict), pup_block):
		return
	
	selectedFacesOnly = selectedFacesOnly.val
	respectUVs = respectUVs.val
	respectVCols = respectVCols.val
	limit = limit.val
	
	# We now know we can execute
	is_editmode = Window.EditMode()
	if is_editmode: Window.EditMode(0)
	
	limit = limit/100.0 # Make between 1 and 0
	
	for ob in meshDict.itervalues():
		mesh = ob.getData()
		tri2quad(mesh, limit, selectedFacesOnly, respectUVs, respectVCols)
	if is_editmode: Window.EditMode(1)

# Dont run when importing
if __name__ == '__main__':
	Window.DrawProgressBar(0.0, 'Triangles to Quads 1.1 ')
	main()
	Window.DrawProgressBar(1.0, '')