#!BPY

"""
Name: 'Auto UV'
Blender: 234
Group: 'UV'
Tooltip: 'Generate UV coordinates for one or mesh on a single texture square'
""" 

__author__ = "z3r0_d (Nick Winters)"
##__url__ = ("")#to be determined
__version__ = "0.5a"

__bpydoc__ = """\
This script generates UV coordinates on selected meshes using what is mostly an
extension of a cube map.  Regions of faces are determined by their primary 
[local] axis, then these regions are packed into a square.  The relative size
of uvmapped regions should be the same [not considering the scaling of objects]
Also, some padding is added between regions.  

Usage:
  Select your objects, run this script

Notes:
  There is no guarntee that the faces do not overlap in a single uv region, 
this could occur if connected faces face primarily on the same axis, this would
happen with a spiral for example.  
  also, regions are not guarnteed efficent packing on their own, they can have
big holes.  
"""

# autouv.py
# copyright dec 2004, z3r0_d (nick winters)
# please do not redistribute, I'd like to complete it first
# [then it will be public domain]
#
# the intention is to use this to generate uv coords for non-overlapping
# polygonal regions, for example: for texture baking
#
# currently it works pretty well, however:
#  1. region decision code could use some work to make areas which fit better in a rectange
#  2. I haven't figured out how to add spaces of correct sizes between regions 
#      [to cope with interpolation and mipmapping]
#
# known bugs:
# *a region consists of faces which all are primarily facing the same axis, some 
#  situations exist where the resulting uvmap has overlapping regions [in a single
#  clump of faces].  An example would be a flat spiral, or perhaps suzanne's inner
#  ear [though that is only two faces, with a spiral you can create as many overlaps
#  as you want]
# *also, I have not anywhere near fully tested this

import math
import Blender

import random

# need to decide on box packing lib...

# a really big number
INFINITE = 3.4e38
#INFINITE = 1.79e308

# a smaller [than INFINITE] big number
BIGNUMBER = 3.0e38
#BIGNUMBER = 1.5e308

class Box:
	def __init__(self,width,height):
		self.width = width
		self.height = height
		
		self.area = self.width * self.height
		
		self.above = None
		self.right = None
		self.back = None
		
		# [width,height] available above and to the right of this box
		self.aboveRoom = [BIGNUMBER, BIGNUMBER]
		self.rightRoom = [BIGNUMBER, BIGNUMBER]
		
		self.x = -1.0
		self.y = -1.0
	def __cmp__(self,abox): # to simplify sorting
		return cmp(self.area,abox.area)
	def __str__(self): # not used
		return str(self.area)
	def __repr__(self):
		# apparently used when you print a list of boxes...
		return str(self.area)

# class name prefix "z3r0_" subject to change, likely to one or two letters

# I don't use Mathutils because... well, I don't know if I can just add vectors
# and I don't care too much, I can do pretty well with my own stuff
def vec_dot(u, v):
	return u[0]*v[0] + u[1]*v[1] + u[2]*v[2]
def vec_cross(u, v):
	#	|	i	j	k	|
	#	|	u0	u1	u2	|
	#	|	v0	v1	v2	|
	# (u1*v2-u2*v1)i - (u0*v2-u2*v0)j + (u0*v1-u1*v0)k
	# (u1*v2-u2*v1)i + (u2*v0-u0*v2)j + (u0*v1-u1*v0)k
	return [u[1]*v[2]-u[2]*v[1], u[2]*v[0]-u[0]*v[2], u[0]*v[1]-u[1]*v[0]]
def vec_mag(u):
	return math.sqrt(u[0]*u[0] + u[1]*u[1] + u[2]*u[2])
def vec_norm(u):
	n = vec_mag(u)
	return [u[0]/n, u[1]/n, u[2]/n]
def vec_between_points(u, v):
	# returns the vector from point u to point v
	return [v[0]-u[0], v[1]-u[1], v[2]-u[2]]

# the constructor for vert, edge, and face are stupid
# they do not worry themselves about the relationships with the other datatypes
# the constructor for a mesh will take care of that
# also, all methods which act on verts, edges, and faces must be responsible
# for preserving the structure when changes are made
class z3r0_vert:
	def __init__(self, nmvert_object):
		self.nmvert = nmvert_object
		self.co = nmvert_object.co
		# will not use self.index, it can be searched for if necescary
		self.no = nmvert_object.no
		self.sel = nmvert_object.sel
		# hrm, likely will cause error and I don't use sticky coords anyway
		#self.stickyco = nmvert_object.stickyco
		self.e = []
		self.f = []
	def __repr__(self):
		return str(id(self))+str(co)

class z3r0_edge:
	def __init__(self, z3r0_vert1, z3r0_vert2):
		self.v = (z3r0_vert1, z3r0_vert2)
		self.f = []

class z3r0_face:
	def __init__(self, nmface_object, z3r0_vert1, z3r0_vert2, z3r0_vert3, z3r0_vert4 = None):
		self.nmface = nmface_object
		# note that verticies are the actual object, not the index
		if z3r0_vert4:
			self.v = (z3r0_vert1, z3r0_vert2, z3r0_vert3, z3r0_vert4)
		else:
			self.v = (z3r0_vert1, z3r0_vert2, z3r0_vert3)
		self.e = ()
		self.uvco = tuple(nmface_object.uv)
		self.col = tuple(nmface_object.col)
		# ...
		self.flag = nmface_object.flag
		self.image = nmface_object.image
		self.mat = self.materialIndex = nmface_object.mat
		self.mode = nmface_object.mode
		# normal is depricated, use getNormal() instead
		self.smooth = nmface_object.smooth
		self.transp = nmface_object.transp
	def getNormal(self):
		vec = [0.0, 0.0, 0.0]
		if len(self.v) == 3:
			vec = vec_cross( \
				vec_between_points(self.v[0].co, self.v[1].co), \
				vec_between_points(self.v[1].co, self.v[2].co) )
		elif len(self.v) == 4:
			vec = vec_cross( \
				vec_between_points(self.v[0].co, self.v[2].co),
				vec_between_points(self.v[1].co, self.v[3].co) )
		if vec != [0.0, 0.0, 0.0]:
			return vec_norm( vec )
		else:
			return vec

class z3r0_mesh:
	def __init__(self, nmesh_object):
		self.nmesh = nmesh_object
		self.faces = []
		self.edges = []
		self.verts = []
		# several nmesh object properties should go here...
		#
		#
		# the following is used to search for edges based on two verts
		# it should have a key for both orders of the verts
		self.edgedict = {}
		# add verticies
		for vertex in nmesh_object.verts:
			self.verts.append(z3r0_vert(vertex))
		# now things begin to get interesting, go through the faces
		for nface in nmesh_object.faces:
			if len(nface.v) == 4:
				zface = z3r0_face(nface, \
					self.verts[nface.v[0].index], self.verts[nface.v[1].index], self.verts[nface.v[2].index], self.verts[nface.v[3].index] )
				self.faces.append(zface)
				# vertex objects, first element repeated for ease later
				tv = [self.verts[nface.v[0].index], self.verts[nface.v[1].index], self.verts[nface.v[2].index], self.verts[nface.v[3].index], self.verts[nface.v[0].index]]
				# edge stuffs, vertex stuffs
				zface.e = []
				for i in range(4):
					edge = None
					if self.edgedict.has_key((tv[i], tv[i+1])):
						# and edge exists, do my buisness with it
						edge = self.edgedict[(tv[i], tv[i+1])]
						edge.f.append(zface)
					else:
						edge = z3r0_edge(tv[i], tv[i+1])
						edge.f.append(zface)
						self.edgedict[(tv[i], tv[i+1])] = edge
						self.edgedict[(tv[i+1], tv[i])] = edge
						self.edges.append(edge)
					zface.e.append(edge)
					tv[i].e.append(edge)
					tv[i].f.append(zface)
				zface.e = tuple(zface.e)
			elif len(nface.v) == 3:
				zface = z3r0_face(nface, \
					self.verts[nface.v[0].index], self.verts[nface.v[1].index], self.verts[nface.v[2].index] )
				self.faces.append(zface)
				# vertex objects, first element repeated for ease later
				tv = [self.verts[nface.v[0].index], self.verts[nface.v[1].index], self.verts[nface.v[2].index], self.verts[nface.v[0].index]]
				# edge stuffs, vertex stuffs
				zface.e = []
				for i in range(3):
					edge = None
					if self.edgedict.has_key((tv[i], tv[i+1])):
						# and edge exists, do my buisness with it
						edge = self.edgedict[(tv[i], tv[i+1])]
						edge.f.append(zface)
					else:
						edge = z3r0_edge(tv[i], tv[i+1])
						edge.f.append(zface)
						self.edgedict[(tv[i], tv[i+1])] = edge
						self.edgedict[(tv[i+1], tv[i])] = edge
						self.edges.append(edge)
					zface.e.append(edge)
					tv[i].e.append(edge)
					tv[i].f.append(zface)
				zface.e = tuple(zface.e)
		#if len(self.faces) + len(self.verts) == len(self.edges) +2:
		#	print "##likely a completely manifold mesh!"

def majoraxis(vec):
	# returns index of largest (absolute value) number in list vec
	# given the chance, this should be made faster
	max = -1
	index = -5
	for b in enumerate(vec):
		if abs(b[1]) > max:
			index = b[0]+1
			max = abs(b[1])
	if abs(vec[index-1]) > vec[index-1]: index *= -1
	return index

timestart = Blender.sys.time()
print "\nSCRIPTSTART"

## DEBUG [useful]
# 16 unique and visibly different colors
# [same order as dos console colors]
colors = []
for i in range(16):
	b = 128*(i & 0x1) + 16*(i & 0x8)
	g = 64*(i & 0x2) + 16*(i & 0x8)
	r = 32*(i & 0x4) + 16*(i & 0x8)
	if i == 7:
		r, g, b = 192,192,192
	elif i == 8:
		r, g, b = 128,128,128
	colors.append((r,g,b))

def randomcolor():
	r = random.randrange(0,255)
	g = random.randrange(0,255)
	b = random.randrange(0,255)
	return (r,g,b)

meshObjs = []
nmeshes = []
z3r0_meshes = []

for obj in Blender.Object.GetSelected():
	if obj.getType() == "Mesh":
		meshObjs.append(obj)
		mynmesh = obj.getData()
		nmeshes.append(mynmesh)
		myz3r0_mesh = z3r0_mesh(mynmesh)
		z3r0_meshes.append(myz3r0_mesh)
print "Making z3r0_mesh objects took %f seconds"%(Blender.sys.time()-timestart)

fclumpstart = Blender.sys.time()
faceclumps = [] # each faceclump is a 2-tuple, (index of mesh, list of z3r0_faces)

mesh_index = -1
for z3r0_m in z3r0_meshes:
	mesh_index += 1
	if len(z3r0_m.faces) == 0: continue
	
	for z3r0_f in z3r0_m.faces:
		#for z3r0_f in z3r0_m.faces: ## debug, set all faces white
		#	z3r0_f.nmface.col = (Blender.NMesh.Col(*colors[15]),)*len(z3r0_f.v)
		z3r0_f.clump = -1 # index of face clump the face is in
		z3r0_f.lastcheck = -1 # index of last clump I checked if this face fits in
		z3r0_f.majoraxis = majoraxis(z3r0_f.getNormal())
		z3r0_f.adjfaces = []
		for edge in z3r0_f.e:
			for face in edge.f:
				if face != z3r0_f and z3r0_f.adjfaces.count(face) == 0:
					z3r0_f.adjfaces.append(face)
	
	
	clumpindex = -1
	insertedfaces = 0
	while 1:
		# create a new clump
		clumpindex += 1
		
		startface = None
		for aface in z3r0_m.faces:
			if aface.clump == -1:
				startface = aface
				break
		if not startface:
			break
		
		insertedfaces += 1
		
		mymajoraxis = startface.majoraxis
		
		clumpfaces = []
		startface.clump = clumpindex
		startface.lastcheck = clumpindex
		
		#possiblefaces = startface.adjfaces[:]
		#possiblefaces.append(startface)
		
		#for aface in possiblefaces:
		#	aface.lastcheck = clumpindex
		
		newfaces = [startface]
		
		# showing colors..
		coltmp = randomcolor()
		
		while newfaces:
			thisface = newfaces.pop()
			for aface in thisface.adjfaces:
				if aface.lastcheck < clumpindex:
					aface.lastcheck = clumpindex
					if aface.majoraxis == mymajoraxis:
						newfaces.append(aface)
			clumpfaces.append(thisface)
			thisface.clump = clumpindex
			insertedfaces += 1
			
			##DEBUGGING:
			#thisface.nmface.col = (Blender.NMesh.Col(*colors[clumpindex%16]),)*len(thisface.v)
			#thisface.nmface.col = (Blender.NMesh.Col(*coltmp),)*len(thisface.v)
		faceclumps.append((mesh_index,clumpfaces))
	## DEBUGGING
	z3r0_m.nmesh.update()

print "Took %f seconds to create %d clumps"%((Blender.sys.time()-fclumpstart),len(faceclumps))

boxes = []
clumpindex = -1
# generate uv coords for face regions
for clump in faceclumps:
	clumpindex += 1
	z3r0_mesh = z3r0_meshes[clump[0]]
	
	mymajoraxis = abs(clump[1][0].majoraxis)
	u = -1 # index of vert coord vector signifying u coordinate
	v = -1 # index of vert coord vector specifying v coordinate
	if mymajoraxis == 1:
		# faces perpendicular to x
		u = 1
		v = 2
	elif mymajoraxis == 2:
		# faces perpendicular to y
		u = 0
		v = 2
	elif mymajoraxis == 3:
		# faces perpendicular to z
		u = 0
		v = 1
	else:
		raise "major axis isn't in [1,3]"
	
	# find the min/max of uv values...
	umin = INFINITE
	vmin = INFINITE
	umax = -1 * INFINITE
	vmax = -1 * INFINITE
	
	for face in clump[1]:
		for vert in face.v:
			if vert.co[u] > umax: umax = vert.co[u]
			if vert.co[u] < umin: umin = vert.co[u]
			if vert.co[v] > vmax: vmax = vert.co[v]
			if vert.co[v] < vmin: vmin = vert.co[v]
	
	# create a box...
	newbox = Box(umax - umin, vmax - vmin)
	newbox.clump = clumpindex
	boxes.append(newbox)

## TODO: find best way to make boxes larger [to make a given space between boxes]
estimatedarea = 0.0
for box in boxes:
	estimatedarea += box.area

estimatedarea /= 0.85 # add box packing efficency error

estimatedwidth = math.sqrt(estimatedarea)

##still not good enough... :(
boxgrowth = (6.0/256)*math.sqrt(len(boxes))


for box in boxes:
	box.width += boxgrowth
	box.height += boxgrowth
	# not updating this puts more realistic results into my packing efficency
	box.area = box.height * box.width


print "Box Packing %d boxes"%len(boxes)

###### BOX PACKING!!
boxBeginTime = Blender.sys.time()
boxes_copy = boxes[:]
# smallest area to largest
boxes.sort()

# find area
area = 0.0
for box in boxes:
	area += box.area

### DEBUG:
##mesh = Blender.NMesh.GetRaw()
##mesh.hasVertexColours(1)
##mesh.hasFaceUV(1)
##mesh.update()
##Blender.NMesh.PutRaw(mesh, 's')
##def redraw(lb): # lb is the most recently added box
##	face = Blender.NMesh.Face()
##	face.v = [
##		Blender.NMesh.Vert(lb.x, lb.y,0.0),
##		Blender.NMesh.Vert(lb.x + lb.width, lb.y),
##		Blender.NMesh.Vert(lb.x + lb.width, lb.y + lb.height),
##		Blender.NMesh.Vert(lb.x, lb.y + lb.height) ]
##	r = random.randrange(0,255)
##	g = random.randrange(0,255)
##	b = random.randrange(0,255)
##	face.uv = [(0.0,0.0),(1.0,0.0),(1.0,1.0),(0.0,1.0)]
##	face.col = [
##		Blender.NMesh.Col(r,g,b,0),
##		Blender.NMesh.Col(r,g,b,0),
##		Blender.NMesh.Col(r,g,b,0),
##		Blender.NMesh.Col(r,g,b,0) ]
##	face.mode = 0
##	
##	mesh.faces.append(face)
##	mesh.verts.extend(face.v)
##	if 0:
##		mesh.update()
##		Blender.Window.Redraw(Blender.Window.Types.VIEW3D) 
##		time.sleep(0.2)

# start with largest box
root = boxes.pop()
root.x = 0.0
root.y = 0.0
##redraw(root) # debug

# highest x and y value so far
bounds = [root.width, root.height]

while boxes:
	newbox = boxes.pop()
	
	# insert in best spot...
	
	# informations about the best found spot
	adjbox = None  # best found box yet
	maxbound = INFINITE # lowest max for upper right corner is best fit
	rightof = -1 # 1 if best spot is right of adjbox
	
	# I do a depth first traversal using nearbyboxes as the stack when looking for nearest fit
	nearbyboxes = [root]
	while nearbyboxes:
		candidate = nearbyboxes.pop()
		
		# can I put newbox on the right side?
		if candidate.right:
			nearbyboxes.append(candidate.right)
		elif candidate.rightRoom[0] >= newbox.width and candidate.rightRoom[1] >= newbox.height:
				localmax = max(candidate.x + candidate.width + newbox.width, candidate.y + newbox.height)
				if localmax < maxbound:
					# this position is better than the one before
					rightof = 1
					adjbox = candidate
					maxbound = localmax
		
		# can I put newbox above candidate?
		if candidate.above:
			nearbyboxes.append(candidate.above)
		elif candidate.aboveRoom[0] >= newbox.width and candidate.aboveRoom[1] >= newbox.height:
				localmax = max(candidate.y + candidate.height + newbox.height, candidate.x + newbox.width)
				if localmax < maxbound:
					rightof = 0
					adjbox = candidate
					maxbound = localmax
		
	
	# insert the box
	if rightof == 1:
		if adjbox.right:
			raise "problems"
		adjbox.right = newbox
		newbox.left = adjbox
		newbox.x = adjbox.x + adjbox.width
		newbox.y = adjbox.y
	elif rightof == 0:
		if adjbox.above:
			raise "problems"
		adjbox.above = newbox
		newbox.below = adjbox
		newbox.x = adjbox.x
		newbox.y = adjbox.y + adjbox.height
	else:
		raise "problems"
	
	# update the bounds
	bounds[0] = max(bounds[0], newbox.x + newbox.width)
	bounds[1] = max(bounds[1], newbox.y + newbox.height)
	
	# update clearances....
	newboxes = [root]
	while newboxes:
		mybox = newboxes.pop()
		
		if mybox.above: newboxes.append(mybox.above)
		if mybox.right: newboxes.append(mybox.right)
		
		# mybox above newbox
		if mybox.y >= newbox.y + newbox.height:
			if mybox.x + mybox.width >= newbox.x and mybox.x < newbox.x:
				newbox.aboveRoom[1] = min(newbox.aboveRoom[1], mybox.y - newbox.y - newbox.height)
			if mybox.x + mybox.width >= newbox.x + newbox.width and mybox.x < newbox.x + newbox.width:
				newbox.rightRoom[1] = min(newbox.rightRoom[1], mybox.y - newbox.y)
		# mybox right of newbox
		if mybox.x >= newbox.x + newbox.width:
			if mybox.y + mybox.height >= newbox.y and mybox.y < newbox.y:
				newbox.rightRoom[0] = min(newbox.rightRoom[0], mybox.x - newbox.x - newbox.width)
			if mybox.y + mybox.height >= newbox.y + newbox.height and mybox.y < newbox.y + newbox.height:
				newbox.aboveRoom[0] = min(newbox.aboveRoom[0], mybox.x - newbox.x)
		
		# newbox above mybox
		if newbox.y >= mybox.y + mybox.height:
			if newbox.x + newbox.width >= mybox.x and newbox.x < mybox.x:
				mybox.aboveRoom[1] = min(mybox.aboveRoom[1], newbox.y - mybox.y - mybox.height)
			if newbox.x + newbox.width >= mybox.x + mybox.width and newbox.x < mybox.x + mybox.width:
				mybox.rightRoom[1] = min(mybox.rightRoom[1], newbox.y - mybox.y)
		# newbox right of mybox
		if newbox.x >= mybox.x + mybox.width:
			if newbox.y + newbox.height >= mybox.y and newbox.y < mybox.y:
				mybox.rightRoom[0] = min(mybox.rightRoom[0], newbox.x - mybox.x - mybox.width)
			if newbox.y + newbox.height >= mybox.y + mybox.height and newbox.y < mybox.y + mybox.height:
				mybox.aboveRoom[0] = min(mybox.aboveRoom[0], newbox.x - mybox.x)
	
	# redraw and stuff for debugging...
	##redraw(newbox)

maxbound = max(bounds)
invmaxbound = 1.0 / maxbound

##mesh.update() #debug

print "Took %f Seconds for %d boxes"%(Blender.sys.time()-boxBeginTime, len(boxes_copy))
print "maxbound %f, area %f"%(maxbound,area)
print "%f%% efficiency of box packing alone"%(100.0*area/(maxbound*maxbound))

print "setting UV coordinates"
uvStartTime = Blender.sys.time()
for box in boxes_copy:
	clump = faceclumps[box.clump]
	z3r0_mesh = z3r0_meshes[clump[0]]
	
	mymajoraxis = abs(clump[1][0].majoraxis)
	u = -1 # index of vert coord vector signifying u coordinate
	v = -1 # index of vert coord vector specifying v coordinate
	if mymajoraxis == 1:
		# faces perpendicular to x
		u = 1
		v = 2
	elif mymajoraxis == 2:
		# faces perpendicular to y
		u = 0
		v = 2
	elif mymajoraxis == 3:
		# faces perpendicular to z
		u = 0
		v = 1
	else:
		raise "major axis isn't in [1,3]"
	
	umin = INFINITE
	vmin = INFINITE
	umax = -1 * INFINITE
	vmax = -1 * INFINITE
	
	for face in clump[1]:
		for vert in face.v:
			if vert.co[u] > umax: umax = vert.co[u]
			if vert.co[u] < umin: umin = vert.co[u]
			if vert.co[v] > vmax: vmax = vert.co[v]
			if vert.co[v] < vmin: vmin = vert.co[v]
	
	
	for face in clump[1]:
		uv = []
		for vert in face.v:
			uv.append((invmaxbound*(box.x + vert.co[u] - umin), invmaxbound*(box.y + vert.co[v] - vmin)))
		face.nmface.uv = uv
	
	## just testing, ought ought to minimize updates if possible
	z3r0_mesh.nmesh.update()

#for z3r0_m in z3r0_meshes:
#	z3r0_mesh.nmesh.update()

print "Took %f seconds to restore uv"%(Blender.sys.time() - uvStartTime)

print "Took %f Seconds Total"%(Blender.sys.time() - timestart)
Blender.Window.Redraw()
print "SCRIPTEND!!!\n"