--- blender-2.44/release/scripts/bpymodules/boxpack2d.py.boxpack	2007-05-14 16:41:29.000000000 +0200
+++ blender-2.44/release/scripts/bpymodules/boxpack2d.py	2007-05-14 16:52:28.000000000 +0200
@@ -0,0 +1,498 @@
+'''
+# 2D Box packing function used by archimap
+# packs any list of 2d boxes into a square and returns a list of packed boxes.
+# Example of usage.
+import boxpack2d
+
+# Build boxe list.
+# the unique ID is not used.
+# just the width and height.
+boxes2Pack = []
+anyUniqueID = 0; w = 2.2; h = 3.8
+boxes2Pack.append([anyUniqueID, w,h])
+anyUniqueID = 1; w = 4.1; h = 1.2
+boxes2Pack.append([anyUniqueID, w,h])
+anyUniqueID = 2; w = 5.2; h = 9.2
+boxes2Pack.append([anyUniqueID, w,h])
+anyUniqueID = 3; w = 8.3; h = 7.3
+boxes2Pack.append([anyUniqueID, w,h])
+anyUniqueID = 4; w = 1.1; h = 5.1
+boxes2Pack.append([anyUniqueID, w,h])
+anyUniqueID = 5; w = 2.9; h = 8.1
+boxes2Pack.append([anyUniqueID, w,h])
+anyUniqueID = 6; w = 4.2; h = 6.2
+boxes2Pack.append([anyUniqueID, w,h])
+# packedLs is a list of [(anyUniqueID, left, bottom, width, height)...]
+packWidth, packHeight, packedLs = boxpack2d.boxPackIter(boxes2Pack)
+'''
+
+from Blender import NMesh, Window,   	Object, Scene
+'''
+def debug_(x,y,z):
+	ob = Object.New("Empty")
+	ob.loc= x,y,z
+	Scene.GetCurrent().link(ob)
+'''
+
+# a box packing vert
+class vt:
+	def __init__(self, x,y):
+		self.x, self.y = x, y
+		
+		self.free = 15
+		
+		# Set flags so cant test bottom left of 0/0
+		#~ BLF = 1; TRF = 2; TLF = 4; BRF = 8
+		
+		#self.users = [] # A list of boxes.
+		# Rather then users, store Quadrents
+		self.blb = self.tlb = self.brb = self.trb = None
+		
+		
+		# A hack to remember the box() that last intersectec this vert
+		self.intersectCache = ([], [], [], [])
+		
+class vertList:	
+	def __init__(self, verts=[]):
+		self.verts = verts
+	
+	def sortCorner(self,w,h):
+		'''
+		Sorts closest first. - uses the box w/h as a bias,
+		this makes it so its less likely to have lots of poking out bits
+		that use too much 
+		Lambada based sort
+		'''
+		# self.verts.sort(lambda A, B: cmp(max(A.x+w, A.y+h) , max(B.x+w, B.y+h))) # Reverse area sort
+		try:	self.verts.sort(key = lambda b: max(b.x+w, b.y+h) ) # Reverse area sort
+		except:	self.verts.sort(lambda A, B: cmp(max(A.x+w, A.y+h) , max(B.x+w, B.y+h))) # Reverse area sort
+		
+		
+
+class box:
+	def __init__(self, width, height, id=None):
+		
+		self.id= id
+		
+		self.area = width * height # real area
+		self.farea = width + height # fake area
+		#self.farea = float(min(width, height)) / float(max(width, height))  # fake area
+		
+		self.width = width
+		self.height = height
+		
+		# Append 4 new verts
+		# (BL,TR,TL,BR) / 0,1,2,3
+		self.v=v= [vt(0,0), vt(width,height), vt(0,height), vt(width,0)]
+		
+		# Set the interior quadrents as used.
+		v[0].free &= ~TRF
+		v[1].free &= ~BLF
+		v[2].free &= ~BRF
+		v[3].free &= ~TLF
+		
+		#for v in self.v:
+		#	v.users.append(self)
+		v[0].trb = self
+		v[1].blb = self
+		v[2].brb = self
+		v[3].tlb = self
+		
+		
+	def updateV34(self):
+		'''
+		Updates verts 3 & 4 from 1 and 2
+		since 3 and 4 are only there foill need is resizing/ rotating of patterns on the fly while I painr new box placement
+		but may be merged later with other verts
+		'''	
+		self.v[TL].x = self.v[BL].x
+		self.v[TL].y = self.v[TR].y
+		
+		self.v[BR].x = self.v[TR].x
+		self.v[BR].y = self.v[BL].y 
+		
+
+	def setLeft(self, lft):     
+		self.v[TR].x = lft + self.v[TR].x - self.v[BL].x
+		self.v[BL].x = lft
+		# update othere verts
+		self.updateV34()
+
+	def setRight(self, rgt):    
+		self.v[BL].x = rgt - (self.v[TR].x - self.v[BL].x)
+		self.v[TR].x = rgt
+		self.updateV34()
+
+	def setBottom(self, btm):     
+		self.v[TR].y = btm + self.v[TR].y - self.v[BL].y
+		self.v[BL].y = btm
+		self.updateV34()
+
+	def setTop(self, tp):    
+		self.v[BL].y = tp - (self.v[TR].y - self.v[BL].y)
+		self.v[TR].y = tp
+		self.updateV34()
+			
+	def getLeft(self):
+		return self.v[BL].x
+
+	def getRight(self):
+		return self.v[TR].x
+
+	def getBottom(self):
+		return self.v[BL].y
+
+	def getTop(self):
+		return self.v[TR].y
+	
+	def overlapAll(self, boxLs, intersectCache): # Flag index lets us know which quadere
+		''' Returns none, meaning it didnt overlap any new boxes '''
+		v= self.v
+		if v[BL].x < 0:
+			return True
+		elif v[BL].y < 0:
+			return True
+		else:
+			bIdx = len(intersectCache)
+			while bIdx:
+				bIdx-=1
+				b = intersectCache[bIdx]
+				if not (	v[TR].y <= b.v[BL].y or\
+							v[BL].y >= b.v[TR].y or\
+							v[BL].x >= b.v[TR].x or\
+							v[TR].x <= b.v[BL].x ):
+					
+					return True # Intersection with existing box
+			#return 0 # Must keep looking
+			
+			for b in boxLs.boxes:
+				if not (v[TR].y <= b.v[BL].y or\
+						v[BL].y >= b.v[TR].y or\
+						v[BL].x >= b.v[TR].x or\
+						v[TR].x <= b.v[BL].x ):
+						
+					return b # Intersection with new box.
+			return False
+	
+	
+	
+	def place(self, vert, quad):
+		'''
+		Place the box on the free quadrent of the vert
+		'''
+		if quad == BLF:
+			self.setRight(vert.x)
+			self.setTop(vert.y)
+			
+		elif quad == TRF:
+			self.setLeft(vert.x)
+			self.setBottom(vert.y)
+		
+		elif quad == TLF:
+			self.setRight(vert.x)
+			self.setBottom(vert.y)
+
+		elif quad == BRF:
+			self.setLeft(vert.x)
+			self.setTop(vert.y)
+	
+	# Trys to lock a box onto another box's verts
+	# cleans up double verts after
+	def tryVert(self, boxes, baseVert):
+		for flagIndex, freeQuad in enumerate(quadFlagLs):
+			#print 'Testing ', self.width
+			if baseVert.free & freeQuad:
+				
+				self.place(baseVert, freeQuad)
+				overlapBox = self.overlapAll(boxes, baseVert.intersectCache[flagIndex])
+				if overlapBox is False: # There is no overlap
+					baseVert.free &= ~freeQuad # Removes quad
+					# Appends all verts but the one that matches. this removes the need for remove doubles
+					for vIdx in (0,1,2,3): # (BL,TR,TL,BR) / 0,1,2,3
+						self_v= self.v[vIdx] # shortcut
+						if not (self_v.x == baseVert.x and self_v.y == baseVert.y):
+							boxList.packedVerts.verts.append(self_v)
+						else:
+							baseVert.free &= self_v.free # make sure the that any unfree areas are wiped.
+							
+							# Inherit used boxes from old verts
+							if self_v.blb: baseVert.blb = self_v.blb 
+							if self_v.brb: baseVert.brb = self_v.brb #print 'inherit2'
+							if self_v.tlb: baseVert.tlb = self_v.tlb #print 'inherit3'
+							if self_v.trb: baseVert.trb = self_v.trb #print 'inherit4'
+							self.v[vIdx] = baseVert
+
+					
+					
+					# Logical checking for used verts by compares box sized and works out verts that may be free.
+					# Verticle
+					
+					if baseVert.tlb and baseVert.trb and\
+					(self == baseVert.tlb or self == baseVert.trb):
+						if baseVert.tlb.height > baseVert.trb.height:
+							baseVert.trb.v[TL].free &= ~(TLF|BLF)
+						elif baseVert.tlb.height < baseVert.trb.height:
+							baseVert.tlb.v[TR].free &= ~(TRF|BRF)
+						else: # same
+							baseVert.tlb.v[TR].free &= ~BLF
+							baseVert.trb.v[TL].free &= ~BRF						
+								
+					
+					elif baseVert.blb and baseVert.brb and\
+					(self == baseVert.blb or self == baseVert.brb):
+						if baseVert.blb.height > baseVert.brb.height:
+							baseVert.brb.v[BL].free &= ~(TLF|BLF)
+						elif baseVert.blb.height < baseVert.brb.height:
+							baseVert.blb.v[BR].free &= ~(TRF|BRF)
+						else: # same
+							baseVert.blb.v[BR].free &= ~TRF
+							baseVert.brb.v[BL].free &= ~TLF
+					
+					# Horizontal
+					if baseVert.tlb and baseVert.blb and\
+					(self == baseVert.tlb or self == baseVert.blb):
+						if baseVert.tlb.width > baseVert.blb.width:
+							baseVert.blb.v[TL].free &= ~(TLF|TRF)
+						elif baseVert.tlb.width < baseVert.blb.width:
+							baseVert.tlb.v[BL].free &= ~(BLF|BRF)
+						else: # same
+							baseVert.blb.v[TL].free &= ~TRF
+							baseVert.tlb.v[BL].free &= ~BRF						
+								
+					
+					elif baseVert.trb and baseVert.brb and\
+					(self == baseVert.trb or self == baseVert.brb):
+						if baseVert.trb.width > baseVert.brb.width:
+							baseVert.brb.v[TR].free &= ~(TRF|TRF)
+						elif baseVert.trb.width < baseVert.brb.width:
+							baseVert.trb.v[BR].free &= ~(BLF|BRF)
+						else: # same
+							baseVert.brb.v[TR].free &= ~TLF
+							baseVert.trb.v[BR].free &= ~BLF	
+					# END LOGICAL VREE SIZE REMOVAL
+					
+					
+					
+					
+					return 1 # Working
+				
+				# We have a box that intersects that quadrent.
+				elif overlapBox is not False and overlapBox  is not True:  # True is used for a box thats alredt in the freq list or out of bounds error.
+					# There was an overlap, add this box to the verts list
+					#quadFlagLs = (BLF,BRF,TLF,TRF)
+					baseVert.intersectCache[flagIndex].append(overlapBox)
+					
+					# Limit the cache size
+					if len(baseVert.intersectCache[flagIndex]) > 8:
+						del baseVert.intersectCache[flagIndex][0]
+				
+		return 0
+
+
+class boxList:
+	#Global vert pool, stores used lists
+	packedVerts = vertList() # will be vertList()
+	
+	def __init__(self, boxes):
+		self.boxes = boxes
+		
+		# keep a running update of the width and height so we know the area
+		# initialize with first box, fixes but where we whwere only packing 1 box
+		# At the moment we only start with 1 box so the code below will loop over 1. but thats ok.
+		width = height = 0.0
+		if boxes:
+			for b in boxes:
+				if width  < b.width: width= b.width
+				if height < b.height: height= b.height
+		self.width= width
+		self.height= height
+		
+		# boxArea is the total area of all boxes in the list,
+		# can be used with packArea() to determine waistage.
+		self.boxArea = 0 # incremented with addBox()
+		
+	
+	# Just like MyBoxLs.boxes.append(), but sets bounds 
+	def addBoxPack(self, box):
+		'''Adds the box to the boxlist and resized the main bounds and adds area. '''
+		self.width = max(self.width, box.getRight())
+		self.height = max(self.height, box.getTop())
+		
+		self.boxArea += box.area
+		
+		# iterate through these
+		#~ quadFlagLs = (1,8,4,2) 
+		#~ # Flags for vert idx used quads
+		#~ BLF = 1; TRF = 2; TLF = 4; BRF = 8
+		#~ quadFlagLs = (BLF,BRF,TLF,TRF)
+		
+		# Look through all the free vert quads and see if there are some we can remove
+		# 
+		
+		for v in box.v:
+			
+			# Is my bottom being used.
+			
+			if v.free & BLF and v.free & BRF: # BLF and BRF
+				for b in self.boxes:
+					if b.v[TR].y == v.y:
+						if b.v[TR].x > v.x:
+							if b.v[BL].x < v.x:
+								v.free &= ~(BLF|BRF) # Removes quad
+				
+				# Is my left being used.
+			if v.free & BLF and v.free & TLF:
+				for b in self.boxes:
+					if b.v[TR].x == v.x:
+						if b.v[TR].y > v.y:
+							if b.v[BL].y < v.y:
+								v.free &= ~(BLF|TLF) # Removes quad
+				
+			if v.free & TRF and v.free & TLF:
+				# Is my top being used.
+				for b in self.boxes:
+					if b.v[BL].y == v.y:
+						if b.v[TR].x > v.x:
+							if b.v[BL].x < v.x:
+								v.free &= ~(TLF|TRF) # Removes quad
+								
+				
+				# Is my right being used.
+			if v.free & TRF and v.free & BRF:
+				for b in self.boxes:
+					if b.v[BL].x == v.x:
+						if b.v[TR].y > v.y:
+							if b.v[BL].y < v.y:
+								v.free &= ~(BRF|TRF) # Removes quad
+								
+		
+		self.boxes.append(box)
+		
+		
+		
+	# Just like MyBoxLs.boxes.append(), but sets bounds 
+	def addBox(self, box):
+		self.boxes.append(box)		
+		self.boxArea += box.area
+
+	# The area of the backing bounds.
+	def packedArea(self):
+		return self.width * self.height
+		
+	# Sort boxes by area
+	def sortArea(self):
+		try:	self.boxes.sort(key=lambda b: b.area )
+		except:	self.boxes.sort(lambda A, B: cmp(A.area, B.area) )
+			
+	
+	# BLENDER only
+	def draw(self):
+		m = NMesh.GetRaw()
+		
+		
+		for b in self.boxes:
+			z = min(b.width, b.height ) / max(b.width, b.height )
+			#z =  b.farea
+			#z=0
+			f = NMesh.Face()
+			m.verts.append(NMesh.Vert(b.getLeft(), b.getBottom(), z))
+			f.v.append(m.verts[-1])
+			m.verts.append(NMesh.Vert(b.getRight(), b.getBottom(), z))
+			f.v.append(m.verts[-1])		
+			m.verts.append(NMesh.Vert(b.getRight(), b.getTop(), z))		
+			f.v.append(m.verts[-1])
+			m.verts.append(NMesh.Vert(b.getLeft(), b.getTop(), z))
+			f.v.append(m.verts[-1])
+			m.faces.append(f)
+		NMesh.PutRaw(m, 's')	
+		Window.Redraw(1)
+	
+	def pack(self):
+		self.sortArea()
+		
+		if not self.boxes:
+			return
+			
+		packedboxes = boxList([self.boxes[-1]])
+		
+		# Remove verts we KNOW cant be added to
+		
+		unpackedboxes = self.boxes[:-1]
+		
+		# Start with this box, the biggest box
+		boxList.packedVerts.verts.extend(packedboxes.boxes[0].v)
+		
+		while unpackedboxes: # != [] - while the list of unpacked boxes is not empty.
+			
+			freeBoxIdx = len(unpackedboxes)
+			while freeBoxIdx:
+				freeBoxIdx-=1
+				freeBoxContext= unpackedboxes[freeBoxIdx]
+				# Sort the verts with this boxes dimensions as a bias, so less poky out bits are made.
+				boxList.packedVerts.sortCorner(freeBoxContext.width, freeBoxContext.height)
+				
+				vertIdx = 0
+				
+				for baseVert in boxList.packedVerts.verts:
+					if baseVert.free: # != 0
+						# This will lock the box if its possibel
+						if freeBoxContext.tryVert(packedboxes, baseVert):
+							packedboxes.addBoxPack( unpackedboxes.pop(freeBoxIdx) ) # same as freeBoxContext. but may as well pop at the same time.
+							freeBoxIdx = -1
+							break
+				
+				freeBoxIdx +=1
+				
+		boxList.packedVerts.verts = [] # Free the list, so it dosent use ram between runs.
+		
+		self.width = packedboxes.width
+		self.height = packedboxes.height
+	# 
+	def list(self):
+		''' Once packed, return a list of all boxes as a list of tuples - (X/Y/WIDTH/HEIGHT) '''
+		return [(b.id, b.getLeft(), b.getBottom(), b.width, b.height ) for b in self.boxes]
+
+
+''' Define all globals here '''
+# vert IDX's, make references easier to understand.
+BL = 0; TR = 1; TL = 2; BR = 3
+
+# iterate through these
+# Flags for vert idx used quads
+BLF = 1; TRF = 2; TLF = 4; BRF = 8
+quadFlagLs = (BLF,BRF,TLF,TRF)
+
+
+# Packs a list w/h's into box types and places then #Iter times
+def boxPackIter(boxLs, iter=1, draw=0):
+	iterIdx = 0
+	bestArea = None
+	# Iterate over packing the boxes to get the best FIT!
+	while iterIdx < iter:
+		myBoxLs = boxList([])
+		for b in boxLs:
+			myBoxLs.addBox( box(b[1], b[2], b[0]) ) # w/h/id
+		
+		myBoxLs.pack()
+		# myBoxLs.draw() # Draw as we go?
+		
+		newArea = myBoxLs.packedArea()
+		
+		#print 'pack test %s of %s, area:%.2f' % (iterIdx, iter, newArea)
+		
+		# First time?
+		if bestArea == None:
+			bestArea = newArea
+			bestBoxLs = myBoxLs
+		elif newArea < bestArea:
+			bestArea = newArea
+			bestBoxLs = myBoxLs
+		iterIdx+=1
+	
+	
+	if draw:
+		bestBoxLs.draw()
+	
+	#print 'best area: %.4f, %.2f%% efficient' % (bestArea, (float(bestBoxLs.boxArea) / (bestArea+0.000001))*100)
+
+	return bestBoxLs.width, bestBoxLs.height, bestBoxLs.list()