import maya.cmds as cmds
import random
import math
import warnings
warnings.filterwarnings("ignore",category=DeprecationWarning)
import itertools
import profile

class cubus:
	def initStuff(self):
		self.facings = [0]*6
		self.pushme = [0]*6
		self.detail = False
		self.ranges = [0]*3
		self.setRanges()
		self.vDirty = True

		# some constants for later reference
		# z+ y+ z- y- x+ x-
		self.fromFace = ( 2, 1, 5, 4, 0, 3 )
		# x+ y+ z+ x- y- z-
		self.toFace = ( 4, 1, 0, 5, 3, 2 )
	
	def __init__(self, *args, **kwargs):
		# overloaded python constructors necessitate no anonymous arguments
		self.hollow = kwargs.get("hollow", None)
		
		mass = kwargs.get( "mass", 0 )
		if mass == "empty" or mass == -1:
			self.mass = -1
		elif mass == "solid" or mass == 1:
			self.mass = 1
		else:
			self.mass = 0

		if kwargs.get("prim"):
			self.initFromPrim(kwargs.get("prim"))
			return
		
		dim = kwargs.get("dim", None)
		org = kwargs.get("org", None)
		min = kwargs.get("min", None)
		max = kwargs.get("max", None)
		corner = kwargs.get("corner", None)
		
		if dim and org:
			self.initFromDim(dim, org, corner)
		elif min and max:
			self.initFromBounds(min,max)

	def initFromPrim(self, prim):
		# take a cube in maya and create a cubus() out of it
		self.size = [None, None, None]

		bb = cmds.polyEvaluate(prim, b=1)
		[self.size[0], self.size[1], self.size[2]] = map(lambda (mn,mx): mx-mn, bb)
		self.origin = map(lambda (mn,mx): float(mx+mn)*0.5, bb)
		
		# TODO: minmaxopt
		self.min = map(lambda (mn,mx): mn, bb)
		self.max = map(lambda (mn,mx): mx, bb)

		self.tex = ["common/caulk"]*6
		self.initStuff()
		
		# assume six faces are in the predicted order, and lift their material assignments
		faces = cmds.ls(cmds.polyListComponentConversion(prim, tf=1), fl=1)
		sgList = cmds.listConnections(cmds.listRelatives(prim,s=1)[0], type="shadingEngine")
		
		if self.sgFromTex("lun3dm5__c_crete6gs") in sgList:
			self.detail = True
		
		if len(sgList) == 1:
			if sgList[0] != "initialShadingGroup":
				self.tex = [self.texFromSG(sgList[0])]*6
		elif len(sgList) > 1:
			i=0
			for face in faces:
				for sg in sgList:
					if cmds.sets(face, isMember=sg):
						self.tex[self.fromFace[i]] = self.texFromSG(sg)
				i += 1

	def initFromDim(self, dim=(4,4,4), org=(0,0,0), corner=None):
		# org here represents an origin corner, not the center
		self.size = [None, None, None]

		self.tex = ["lun3dm5/c_crete6gs"]*6
		if 0 in dim:
			return False
			
		self.size = dim[:]
		self.corner = corner # remember this for future shrinkage
		corg = list(org) # remember this for future shrinkage
		if corner & 1:
			corg[0] -= (self.size[0]-1)
		if corner & 2:
			corg[1] -= (self.size[1]-1)
		if corner & 4:
			corg[2] -= (self.size[2]-1)

		if corner is None:
			self.origin = list(org) 
		else:
			self.origin = map(lambda x, y: x + 0.5*y, corg, self.size)
		# TODO: minmaxopt
		self.min = map(lambda x, y: x - 0.5*y, self.origin, self.size)
		self.max = map(lambda x, y: x + 0.5*y, self.origin, self.size)
		self.initStuff()

	def initFromBounds(self, min, max):
		self.size = map(lambda mx,mn: mx-mn, max, min)

		self.tex = ["lun3dm5/c_crete6gs"]*6
		if 0 in self.size:
			return False
			
		self.origin = map(lambda mx,mn: 0.5*(mx+mn), max, min)
		self.min = min
		self.max = max
		self.initStuff()

	def setSizeFromBounds(self,min,max):
		self.size = map(lambda mx,mn: mx-mn, max, min)
		self.origin = map(lambda mx,mn: 0.5*(mx+mn), max, min)
		self.min = min
		self.max = max
		self.setRanges()
		self.vDirty = True

	def setSizeFromVolume(self, set):
		l = list(set)
		x, y, z = zip(*set)
		newmins = (min(x), min(y),min(z))
		newmaxs = (max(x)+1, max(y)+1,max(z)+1)
		
		self.setSizeFromBounds(newmins, newmaxs)
	
	def scale(self, f):
		self.size = map(lambda x: int(x*f), self.size)
		self.origin = map(lambda x: x * f, self.origin)
		# TODO: minmaxopt
		self.min = map(lambda x: int(x * f), self.min)
		self.max = map(lambda x: int(x * f), self.max)
		self.setRanges()
		self.vDirty = True
		
	def spew(self):
		# TODO: minmaxopt
		print "org",self.origin,"Min",self.min,"Max",self.max,"Size",self.size

	def volume(self):
		return self.size[0] * self.size[1] * self.size[2]
		
	def createPrimitive(self, name=None):
		cubePrim = cmds.polyCube(ch=0,w=self.size[0],h=self.size[1],d=self.size[2])[0]
		cmds.xform(cubePrim, r=1, t=[self.origin[0], self.origin[1], self.origin[2]] )
	
		for i in xrange(6):
			cmds.sets(cubePrim + ".f["+str(self.toFace[i])+"]", fe=self.sgFromTex(self.tex[i]))
		
		if name:
			cubePrim = cmds.rename(cubePrim, name)
		
		return cubePrim

	def pointMask(self, mask):
		# TODO: minmaxopt
		points = self.max[:] * 3
		for i in xrange(9):
			if not mask[i]:
				points[i] = self.min[i%3]
		points[2] *= -1
		points[5] *= -1
		points[8] *= -1
		return map(str, map(int, map(round, points))) # whee
		
	def brushPlanePoints(self, plane):
		"""
		x+	x+ y+ z+, x+ y- z+, x+ y- z-
		y+	x+ y+ z+, x+ y+ z-, x- y+ z-
		z+	x+ y+ z+, x+ y- z+, x- y- z+
		x-	x- y+ z+, x- y+ z-, x- y- z-
		y-	x+ y- z+, x- y- z+, x- y- z-
		z-	x+ y+ z-, x- y+ z-, x- y- z-

		if plane == 0:
			p = self.pointMask([1,1,1, 1,1,0, 1,0,0])
		elif plane == 1:
			p = self.pointMask([1,1,1, 0,1,1, 0,1,0])
		elif plane == 2:
			p = self.pointMask([1,1,1, 1,0,1, 0,0,1])
		elif plane == 3:
			p = self.pointMask([0,1,1, 0,0,1, 0,0,0])
		elif plane == 4:
			p = self.pointMask([1,0,1, 1,0,0, 0,0,0])
		elif plane == 5:	
			p = self.pointMask([1,1,0, 0,1,0, 0,0,0])
		"""
		
		# cheapass mask of bounds to face coordinates in proper order
		pm = (	[1,1,1, 1,1,0, 1,0,0],
				[1,1,1, 0,1,1, 0,1,0],
				[1,1,1, 1,0,1, 0,0,1],
				[0,1,1, 0,0,1, 0,0,0],
				[1,0,1, 1,0,0, 0,0,0],
				[1,1,0, 0,1,0, 0,0,0] )
		
		p = self.pointMask( pm[plane] )
		return "( "+p[0]+" "+p[2]+" "+p[1]+" )	( "+p[3]+" "+p[5]+" "+p[4]+" )	( "+p[6]+" "+p[8]+" "+p[7]+" )	"
	
	def roundTex(self, n):
		# snap a brush dimension to the closest division in one of the panel pages
		if n > 160:
			v = 32
		elif n > 80:
			v = 16
		else:
			v = 8

		q, r = divmod(n, v)
		if r < v/2:
			rnd = q * v
		else:
			rnd = q * v + v
			
		if rnd == 160:
			rnd = 144
		
		if rnd == 0:
			rnd = 8

		return rnd
	
	def seamAlignment(self, plane):
		# determine x and y texture shifts for this brush plane
		# TODO: figure out rotation
		offset = {	8:(0,8), 
					16:(16,16), 
					24:(32,32), 
					32:(56,992), 
					40:(88,88), 
					48:(128,128), 
					56:(176,176), 
					64:(232,928), 
					72:(296,296), 
					80:(368,368),
					96:(448,448),
					112:(544,544),
					128:(656,656),
					144:(784,784),
					192:(0,0),
					224:(96,96),
					256:(208,208),
					288:(336,336),
					320:(480,480),
					352:(640,640),
					384:(816,816),
					}
		# hshift vshift rotate hscale vscale
		# up is z+ (y+ in maya) on side planes and y+ (z- in maya) on top/bottom planes
		# texture is mirrored in radiant on the -x, +y, and -z planes
		# in radiant, scale is applied first (from the origin), then translate, then rotate (around the origin)
		
		# the joy of weak typing: make sure potential ints don't screw up the float math
		fsize = map(float, self.size)
		fmin = map(float, self.min)
		fmax = map(float, self.max)

		if plane == 1 or plane == 4: # floor/ceiling
			ls, min_s, max_s = fsize[0], fmin[0], fmax[0]
			lt, min_t, max_t = fsize[2], -fmax[2], -fmin[2] #flip z
		else:
			lt, min_t, max_t = fsize[1], fmin[1], fmax[1]
			if plane == 0 or plane == 3: # east/west
				ls, min_s, max_s = fsize[2], -fmax[2], -fmin[2] #flip z
			else: # north/south
				ls, min_s, max_s = fsize[0], fmin[0], fmax[0]

		lsOct = self.roundTex(ls)
		ltOct = self.roundTex(lt)

		self.tex[plane] = "lun3dm5/c_crete6gs"
		qMod = 1.0
		if lsOct >= 192 or ltOct >= 192:
			if bool(lsOct >= 192) != bool(ltOct >= 192):
				print "Weird dimensions on a cube\n"
				self.tex = ["common/caulk"]*6
				return			
			self.tex[plane] = "lun3dm5/c_crete6gsl"
			qMod = 2.0

		srand,trand=random.randint(0,1),random.randint(0,1)
		sscale = (ls / lsOct) * qMod
		tscale = (lt / ltOct) * qMod
		sshift = (-round(min_s / sscale) + offset[lsOct][srand]) % 1024  # horizontal shift is to the left in radiant
		tshift = (round(max_t / tscale) + offset[ltOct][trand]) % 1024 # vertical shift is up in radiant
		rotate = 0
		
		return str(sshift) + " " + str(tshift) + " " + str(rotate) + " " + str(sscale) + " " + str(tscale)
	
	def emitBrushPlane(self, plane):
		if self.detail:
			flags = "134217728 0 0"
		else:
			flags = "0 0 0"

		if self.tex[plane] == "lun3dm5/c_crete6gs" or self.tex[plane] == "lun3dm5/c_crete6gsl":
			alignment = self.seamAlignment(plane)
		else:
			alignment = "0 0 0 0.25 0.25"
		
		# (p1) (p2) (p3) tex hshift vshift rotate hscale vscale cflags sflags lightval
		return "	" + self.brushPlanePoints(plane) + " " + self.tex[plane] + " " + alignment + " " + flags + "\n"
	
	def emitBrush(self):
		# print a .map brush definition
		brush = map(self.emitBrushPlane, xrange(6))
		
		return "{\n" + "".join(brush) + "}\n"

	def sgFromTex(self, tex):
		sg = cmds.connectionInfo(tex.replace("/","__") + ".outColor", dfs=1)[0]
		return sg[0:sg.find(".")]
	
	def texFromSG(self, sg):
		mat = cmds.connectionInfo(sg + ".surfaceShader", sfd=1)
		return mat[0:mat.find(".")].replace("__","/")
	
	def setVolumes(self):
		# regenerate the set of coordinates within the volume
		# only generate a new volume set if we've changed size
		if not self.vDirty:
			return
		self.vSet = set( list( (x,y,z) for x in self.ranges[0] for y in self.ranges[1] for z in self.ranges[2] ))
		self.vSetI = set([])
		if self.hollow:
			self.vSetI = self.hollow.volumeSet()
		self.vSetB = self.vSet - self.vSetI
		self.vDirty = False
	
	def volumeSet(self):
		self.setVolumes()
		return self.vSet
	
	def volumeSetInterior(self):
		self.setVolumes()
		return self.vSetI
		
	def volumeSetBorder(self):
		self.setVolumes()
		return self.vSetB
	
	def setRange(self, i):
		# keep ranges of all three dimensions handy for quickly generating volume sets, and only change them when
		# the cube changes size on that axis
		# TODO: minmaxopt
		self.ranges[i] = range(self.min[i], self.max[i])
	
	def setRanges(self):
		for i in xrange(3):
			# TODO: minmaxopt
			self.ranges[i] = range(self.min[i], self.max[i])
		self.diagonals = [None]*8
		self.diagonalOffsets = [-1]*8

	def diagonalSet(self, corner, dist):
		# generate or retrieve the diagonal sweep
		# TODO: minmaxopt
		# keep previously generated diagonal sets around until we know we need a different one
		if self.diagonalOffsets[corner] != dist:
		
			cornerMod = [1,1,1]
			cornerCoord = self.min[:]
			for i in range(3):
				if corner & 2**i:
					cornerMod[i] = -1
					cornerCoord[i] = self.max[i]

			# x shift
			if cornerMod[0] == 1:
				offset = self.min[0] - self.size[1] - self.size[2] + 2
			else:
				offset = self.max[0] - 1

			offset += dist * cornerMod[0]

			# x coords (1,2,3),(2,3,4)(3,4,5)...
			x = []
			for i in range(self.size[2]):
				x += range(offset+i, offset+i+self.size[1])
			if cornerMod[0] > 0:
				x.reverse()

			# y coords (1,2,3),(1,2,3),(1,2,3)...
			y = range(self.min[1],self.max[1]) * self.size[2]
			if cornerMod[1] < 0:
				y.reverse()
				
			# z coords (1,1,1),(2,2,2)(3,3,3)...
			z = []
			for i in range(self.min[2],self.max[2]):
				z += ([i]*self.size[1])
			if cornerMod[2] < 0:
				z.reverse()

			self.diagonalOffsets[corner] = dist
			self.diagonals[corner] = set(zip(x,y,z))

		return self.diagonals[corner]
	
	def push(self, (pushMin, pushMax)):
		# for doing the spew offset to make the surface look broken up
		# if any sides were marked 'flat', they're floor or putty surfaces - put plain concrete on them

		for i in range(6):
			if self.pushme[i]:
				p = random.randrange(pushMin, pushMax, 1)
				self.shrink(i, -p)
				self.tex[i] = "lun3dm5/c_crete6gs"
	
	def intersects(self, other):
		sects = [0,0,0]
		for i in xrange(3):
			# TODO: minmaxopt
			if self.min[i] >= other.min[i] and self.min[i] <= other.max[i]: # min is inside
				sects[i] += 1
			if self.max[i] >= other.min[i] and self.max[i] <= other.max[i]: # max is inside
				sects[i] += 2
			if self.max[i] > other.max[i] and self.min[i] < other.min[i]: 
				sects[i] += 4
		
		# a non-zero number for all three axes means the cubes intersect
		# 1 overlaps the max boundary, 2 overlaps the min boundary, 3 is entirely engulfed by, 4 entirely engulfs
		
		return sects
	
	def faceIntersect(self, other):
		sec = self.intersects(other)
		i = -1
		if sec.count(3) == 2:
			if 1 in sec:
				i = sec.index(1)
			elif 2 in sec:
				i = sec.index(2)
			else:
				return None
				
			if sec[i] == 1:
				i += 3
			return i
		return None
	
	def expandInto(self,other):
		# not used
		# opposite of lop - extend this cubus as far into 'other' as it will go without sticking out the other side
		# used to produce overlapping solid or empty volumes, to encourage positive intersect results
		axis = self.faceIntersect(other)
		if axis is not None:
			if axis > 2:
				d = self.min[axis-3] - other.min[axis-3]
			else:
				d = other.max[axis] - self.max[axis]
			self.shrink(axis, -d)
			return True
		return False
	
	def lop(self, hollows):
		# chop away what extends into any hollows
		# not used - this is based on bounds, so it can't effectively lop a cubus
		#	that straddles two caulk brushes
		for h in hollows:
			axis = self.faceIntersect(h)
			if axis is not None:
				if axis > 2:
					d = h.max[axis-3] - self.min[axis-3]
				else:
					d = self.max[axis] - h.min[axis]
				self.shrink(axis, d)
				if h.mass == 1:
					self.tex[axis] = "common/caulk"
				elif h.mass == -1:
					self.pushme[axis] = True
	
	def newLop(self, hollowSet, mass, floors=False):
		# chop away what extends into all hollows
		# get volume set
		# subtract hollows total volume set from self.volume
		# if bounds change, lop that much in that direction
		oldbounds = self.max[:] + self.min[:]
		self.setSizeFromVolume(self.volumeSet() - hollowSet)
		bounds = self.max[:] + self.min[:]
				
		lops = [0,0,0,0,0,0]
		for axis in range(6):
			if bounds[axis] != oldbounds[axis]:
				lops[axis] = 1
				if mass == 1:
					# lopping from a solid, caulk the lopped faces
					self.tex[axis] = "common/caulk"
				else:
					# lopping from a void, mark the lopped faces as pushable
					if floors and axis == 1:
						self.tex[axis] = "lun3dm5/c_crete6gs"
						continue
					self.tex[axis] = "lun3dm5/c_crete6g"
					self.pushme[axis] = True
		return lops
		
	def expand(self, envelope, mask=[1,1,1,1,1,1]): # [maxx maxy maxz minx miny minz]
		# expand cubus by the same amount in every direction
		
		self.max = map(lambda x,y: y+envelope*x, mask[:3], self.max)
		self.min = map(lambda x,y: y-envelope*x, mask[3:], self.min)
		self.size = map(lambda x,y: y+envelope*x, map(lambda a, b: (a+b), mask[:3], mask[3:]), self.size)

		self.origin = map(lambda mx,mn: 0.5*(mx+mn), self.max, self.min)
		
		self.setRanges()
		self.vDirty = True
			
	def grow(self, axis, d=1.0):
		# move the plane facing down "axis" outward by "d" units - d can be negative
		# axis = 0x+ 1y+ 2z+ 3x- 4y- 5z-
		bounds = list(self.max + self.min) # [maxx maxy maxz minx miny minz]
		
		m = 1
		if axis > 2:
			m = -1
		
		self.size[axis%3] += d
		self.origin[axis%3] += 0.5 * d * m
		bounds[axis] += d * m
		self.max, self.min = bounds[0:3], bounds[3:6]

		self.setRange(axis%3)
		self.vDirty = True	
	
	def shrink(self, axis, d=1.0):
		if self.size[axis%3] - d <= 0:
			return False
		
		self.grow(axis, -d)
	
	def shrinkToExclude(self, overlap, corner):
		# pulls back the dimensions of a cubus towards the corner it was spawned from to
		# avoid overlapping any volume already marked as used
		q = 0
		intersect = self.volumeSet() & overlap
		while intersect:
			q += 1
			if q > 64:
				print "FFFFFUUUUUU"
				return False
	
			if self.volume() <= 1:
				print "Overlap detected on a 1-unit cube"
				return False
			
			cornerMod = [0,1,2]
			# TODO: minmaxopt
			cCell = self.min[:]
			
			for i in range(3):
				if corner & 2**i:
					cornerMod[i] += 3
					cCell[i] = self.max[i]-1
			
			difs = [0,0,0]
			for sect in intersect:
				for i in range(3):
					dif = abs(cCell[i] - sect[i])
					if dif > difs[i]:
						difs[i] = dif
			
			difAxes = []
			for i in range(3):
				if self.size[i] > 1:
					difAxes.append((cornerMod[i],difs[i],self.size[i]-difs[i]))

			random.shuffle(difAxes)
			difAxes.sort(key=lambda s: s[1],reverse=1)
			
			self.shrink(difAxes[0][0], difAxes[0][2])
			
			intersect = self.volumeSet() & overlap
			
		return True

	def divideSpew(self, cubeList, org=[0,0,0], falloff=[64,64,64], div=(2,8), exp=1, interval=8, density=0.5):
		if cubeList is None:
			create = True
			cubeList=[]
		
		self.divide(cubeList, div, exp, interval, pushy=(0,0))
		
		cmds.progressWindow( t='Cube Spewin',ii=1,max=len(cubeList),pr=0,status='Thinning Spew' )
		for c in cubeList[:]:
			if cmds.progressWindow( q=1, ic=1 ):
				break
				
			cmds.progressWindow(s=1,status='Thinning Spew')
			if c.volume() < 20**3:
				cubeList.remove(c)
				del c
				continue
			dist = map(lambda x,y,z: math.fabs((x-y)/z)**2, c.origin, org, falloff)
			bias = math.sqrt(sum(dist))
			if random.random() < bias or random.random() > density:
				cubeList.remove(c)
				del c
				continue
			if create:
				c.createPrimitive()
			else:
				c.detail = True			
				
		cmds.progressWindow(ep=1)
		
	def divide(self, cubeList=None, div=(1,4), exp=1.0, interval=8, pushy=(-4,12), flats=[1,1,1,1,1,1], hollows=None, cellsLeftX=None):
		# interval is the minimum grid increment
		minD, maxD = div
		# maxD * interval is size of biggest division
		# smallest division will always be interval * 1, but no division will be created smaller than minD to start with
		#	large values of minD can waste a lot of extra time in shrinkToExclude		
		# exp is for biasing sub-cubes towards the small (high values) or the large (low values)
		
		create = False
		if cubeList is None:
			create=True
			cubeList=[]
		
		cmds.progressWindow( t='Cube Spewin',ii=1,max=6,status='Initial Setup' )

		# keep track of how far on each diagonal we've swept inward
		diagMarker=[ 0 ] * 8 

		cmds.progressWindow( pr=1,status='Getting Volumes' )

		# get selected maya objects and create subtractive/additive cubi based on their names

		if hollows is None:
			hollowMeshes = cmds.ls(sl=True)
			self.hollows = []
			excludes = []
			if hollowMeshes:
				for hM in hollowMeshes:
					if hM[0:5] == "empty":
						self.hollows.append(cubus(prim=hM,mass=-1))
					elif hM[0:5] == "solid":
						self.hollows.append(cubus(prim=hM,mass=1))
					else:
						excludes.append(cubus(prim=hM))
		else:
			self.hollows = hollows

		i, corner = 0, 0
		
		cmds.progressWindow( pr=2,status='Scaling to Working Size' )

		# reduce everything to working integerization scale
		scalei = 1/float(interval)
		self.scale( scalei )
		map (lambda h: h.scale(scalei), self.hollows)

		cmds.progressWindow( pr=3,status='Making Exclusion Sets' )

		# create a set of the cubus' volume, and subtract all hollows and exclusion volumes
		# a solid is a caulk brush, and a cubus that extends into one is lopped off so it's flush
		# a hollow is the space around a caulk brush, and a cubus that borders one is push()ed by a random amount
		# an exclusion volume is a zone it is not valid for any cubus to overlap at all
		
		if cellsLeftX:
			cellsLeft = cellsLeftX
			cellsLeftV = cellsLeftX
		else:
			excludeCells = set([])
			for ex in excludes:
				ex.scale( scalei )
				excludeCells |= ex.volumeSet()
				ex.scale( interval )
			cellsLeft = self.volumeSet() - excludeCells
			cellsLeftV = self.volumeSet() - excludeCells
		
		cmds.progressWindow( pr=5,status='Hollowing Volume Sets' )

		hollowSet = set()
		for h in self.hollows:
			hollowSet |= h.volumeSet()
		cellsLeft = cellsLeft - hollowSet
				
		# cellsLeft - all volume where it is valid to BEGIN plotting a cubus fragment. hollows and excludes subtracted.
		# cellsLeftV - all volume which is valid for a finished cubus fragment to overlap. excludes subtracted, but not hollows.
		#	(fragments are lopped out of hollows later)
		
		cmds.progressWindow(ep=1)

		volume = len(cellsLeft)
		
		if volume is 0:
			print "You excluded every cubic inch with a volume. Do you have the source cubus selected? Well, don't."
			return
		
		cmds.progressWindow( t='Cube Spewin',ii=1,max=volume,status='Dividing' )

		while cellsLeft:
			j = 0
			u = False
			
			if cmds.progressWindow( q=1, ic=1 ):
				break
				
			while not u:
				j+=1
				if j > 4096:
					print "OH FUUUUCK"
					break
				# take diagonal intersections looking for an unused cell
				slash = self.diagonalSet(corner,diagMarker[corner])
				u = cellsLeft & slash
				if u:
					break
				#advance the marker until an unused cell is found
				diagMarker[corner] = diagMarker[corner] + 1
			
			# spawn a new cubus
			newCorner = u.pop() # could be several in the set, so pop the first one
			nc = list(newCorner)
			
			rdim = [1,1,1]
			for i in range(3):
				cor = corner & 2**i
				if cor:
					nc[i] -= 1
				
				# random dimensions
				arrr = (random.random() + random.random() + random.random()) / 3
				dim = minD + int( math.ceil( ( arrr ** exp ) * maxD ) )
				if (nc[i] + dim) % 2 == 1:
					if random.random() > 0.5:
						dim += dim % (interval * 2)	# try to snap to 2s and 4s now and then to reduce frequency of large
					if random.random() > 0.9:		# brushes with long thin rivers of 1 unit cubes jammed between
						dim += dim % (interval * 4)
				rdim[i] = dim
				
			newCube = cubus( dim=rdim, org=newCorner, corner=corner )

			# find where this random block overreaches the available area, and shrink it so it doesn't
			overlap = newCube.volumeSet() - cellsLeftV
			shrunk = newCube.shrinkToExclude(overlap, corner)
			if not shrunk:
				print "cellsLeft:", cellsLeft
				print "overlap:", overlap
				print "rdim:", rdim
				print "newCorner:", newCorner
			
			# mark the new block's volume as unavailable
			nrc = newCube.volumeSet()
			cellsLeft = cellsLeft - nrc
			cellsLeftV = cellsLeftV - nrc
			
			cubeList.append(newCube)
			
			# proceed inward from another corner
			corner = ( corner + 3 ) % 8
			cmds.progressWindow( e=1, pr=volume-len(cellsLeft), status=str(len(cellsLeft)) + ' cells unfilled')

		cmds.progressWindow(ep=1)
		cmds.progressWindow( t='Cube Spewin',ii=1,max=len(cubeList),status='Lop/Push' )
		
		# volume is divided into blocks, now process them
		i=0
		for chunk in cubeList:
			if cmds.progressWindow( q=1, ic=1 ):
				break
			# do plane test against self to determine facing
			chunk.pushme = map(lambda x,y,z: (x==y)*z, chunk.max + chunk.min, self.max + self.min, flats)
			
			# lop off useless interior mass, if solid
			if self.hollows:
				chunk.lop(self.hollows)
			
			# scale back to regular size
			chunk.scale(interval)
			
			# push face in or out randomly
			if pushy != (0,0) and flats.count(0) != 6:
				chunk.push(pushy)
			
			# make a primitive for visualisation
			if create:
				chunk.createPrimitive()
				del chunk
			else:
				chunk.detail = True			

			cmds.progressWindow( e=1, progress=i,status='Lop/Push: ' + str(i) )
			i += 1
			
		self.scale(interval)
		#if self.hollow:
		#	self.hollow.scale( interval ) # scale up now for loppage
		cmds.progressWindow(ep=1)
	
	# fin
#

# divide() requires too much setup (manual creation of solid and hollow volumes), but 99% of the time I
# only wanted a 16-unit thick envelope of cubage around caulk brushes anyway, so this just assumes
# that's the desired outcome and sets up all the volumes automatically
def lazyDivide(div=(1,4), exp=1.0, interval=8, pushy=(-4,12), flats=[1,1,1,1,1,1], carves=[], yeszone=[], floors=False, stairs=False):
	innerCubes = cmds.ls(sl=True)
	if not innerCubes:
		print "You didn't select anything."
		return

	if stairs:
		floors = True
	
	cmds.progressWindow( t='Cubespew Setup',max=10,status='Inner Cubi Setup' )

	innerCubi = map(lambda x: cubus(prim=x), innerCubes) # caulk bases
	for c in innerCubi:
		c.scale(1.0/interval)
	#	c.createPrimitive()
		
	cmds.progressWindow( e=1, pr=1,status='Expanded Cubi Setup' )

	exCMask = [1]*6
	if floors:
		exCMask[1] = 0
	expandedCubi = map(lambda x: cubus(prim=x), innerCubes) # expanded blocks around caulk bases
	for c in expandedCubi:
		c.scale(1.0/interval)
		c.expand(1,exCMask)
	#	c.createPrimitive()
	
	# carves are exclusion volumes - no cubus intersects an exclusion at all
	for c in carves:
		c.scale(1.0/interval)
	# the yes zone is the opposite of the no zone - cubes will only be created inside this
	for c in yeszone:
		c.scale(1.0/interval)
	
	cmds.progressWindow( e=1, pr=2,status='Shell Setup' )

	shellMin = [9999,9999,9999]
	shellMax = [-9999,-9999,-9999]
	for c in innerCubi:
		shellMin = map(lambda x,y: min(x,y), shellMin, c.min)
		shellMax = map(lambda x,y: max(x,y), shellMax, c.max)
	
	shellCubus = cubus(min=shellMin, max=shellMax)
	
	expandedShellCubus = cubus(min=shellMin, max=shellMax)
	expandedShellCubus.expand(1, flats)
	
	# =====================
	# set up volume sets
	
	# all caulk bases - "matter"
	cmds.progressWindow( e=1, pr=3,status='solidVolume Setup' )
	solidVolume = set()	
	for c in innerCubi:
		solidVolume |= c.volumeSet()
	
	# all empty space within the working bounds - "air"
	cmds.progressWindow( e=1, pr=4,status='voidVolume Setup' )
	voidVolume = set()	
	voidVolume |= expandedShellCubus.volumeSet()

	# 1-unit thick shell around caulk bases - all cube corners originate here
	cmds.progressWindow( e=1, pr=5,status='faceVolume Setup' )
	faceVolume = set()	
	for c in expandedCubi:
		faceVolume |= c.volumeSet()
	
	# exclusion volume - cubes cannot enter this volume at all
	cmds.progressWindow( e=1, pr=6,status='carveVolume Setup' )
	carveVolume = set()	
	for c in carves:
		carveVolume |= c.volumeSet()
	
	# reverse exclusion volume - cubes are constrained entirely within this volume
	cmds.progressWindow( e=1, pr=7,status='yesVolume Setup' )
	yesVolume = set()
	for c in yeszone:
		yesVolume |= c.volumeSet()
	
	cmds.progressWindow( e=1, pr=8,status='Volume Arithmetic' )
	voidVolume -= faceVolume
	faceVolume -= solidVolume
	# progressVolume = set() | faceVolume		# "progressVolume = faceVolume" just makes them aliases of each other
	progressVolume = set() | expandedShellCubus.volumeSet() # flood outside as well as inside!

	cmds.progressWindow( e=1, pr=9,status='More Volume Arithmetic' )
	# intersections to chop away what's inside the carves and outside the yeszone
	faceVolume -= carveVolume
	progressVolume -= carveVolume
	if yesVolume:
		progressVolume &= yesVolume
		faceVolume &= yesVolume
	
	faceVolume &= expandedShellCubus.volumeSet() # intersection to chop away flats
	
	if len(faceVolume) == 0:
		cmds.progressWindow( e=1, ep=1 )
		raise Exception("Your yes volumes exclude all solids.")
		return
	
	# =====================

	cmds.progressWindow( e=1, t='Cubespew Fill', pr=len(faceVolume), max=len(faceVolume), status='Filling...' )
	
	diagMarker=[ 0 ] * 8 
	corner = 0
	cubeList = []

	# proceed with diagonal sweeps, the same as divide()
	while faceVolume:
		faceSlice = False
		while not faceSlice:
			# sweep diagonally looking for an empty cell
			slash = expandedShellCubus.diagonalSet(corner, diagMarker[corner])
			faceSlice = faceVolume & slash
			if faceSlice:
				break
			diagMarker[corner] = diagMarker[corner] + 1
		
		cmds.progressWindow( e=1, pr=len(faceVolume),status='Filling...' )

		newCorner = faceSlice.pop()
		nc = list(newCorner)
		
		# pick random size for new cubus
		randomDims = [1,1,1]
		for i in range(3): # fix stupid lower-left-corner offsets
			if (corner & 2**i):
				nc[i] -= 1
		
			randy = (random.random() + random.random() + random.random()) / 3.0
			dim = div[0] + int( math.ceil( ( randy ** exp ) * div[1] ) )
			if (nc[i] + dim) % 2 == 1:
				if random.random() > 0.5:
					dim += 1
				if random.random() > 0.9:
					dim += 3
			randomDims[i] = dim

		# special 'stairs' flag for not making cubes too high to step up over
		if stairs:
			randomDims[1] = random.choice([1,1,2])
	
		# make a cubus out of it
		newCube = cubus( dim=randomDims, org=newCorner, corner=corner )
		# find where it overlaps existing cubes and shrink it
		overlap = newCube.volumeSet() - progressVolume
		newCube.shrinkToExclude(overlap, corner)
		
		# mark new cube's volume as used
		newCubeSpace = newCube.volumeSet() & faceVolume
		progressVolume -= newCubeSpace
		faceVolume -= newCubeSpace
		
		cubeList.append(newCube)
		
		# proceed from the next corner
		corner = ( corner + 3 ) % 8
		
	# =====================

	cmds.progressWindow( e=1, max=9,pr=8,status='Cubing...' )

	for cube in cubeList:
		# plane test against working volume to find any cubes that kiss the edge of the volume
		cube.pushme = map(lambda x,y,z: (x==y)*z, cube.max + cube.min, expandedShellCubus.max + expandedShellCubus.min, flats)

		# test axes one at a time
		# FIXME: doing this three times is stupid
		for q in [ [1,0,0]*2, [0,1,0]*2, [0,0,1]*2 ]:
			cube.expand(1, mask=q)
			lops = map(lambda s, v: 1 - (s ^ v), cube.newLop(solidVolume, 1, floors), cube.newLop(voidVolume, -1, floors))
			cube.expand(-1, map (lambda m, l: m*l, lops, q))
		# but "if it's stupid and it works ..."
		
		# return to map scale since we're done messing with volume sets
		cube.scale(interval)
		
		if pushy != (0,0):
			cube.push(pushy)
	
	# clean up after ourselves
	for c in carves:
		c.scale(interval)
	for c in yeszone:
		c.scale(interval)
	
	cmds.progressWindow( e=1, ep=1 )
	return cubeList

#


def cubeSpew(spewvol,div=(2,8),density=0.75,exp=1.25):
	s = cubus(prim=spewvol)
	o = cmds.xform('spewMarker',q=1,ws=1,t=1)
	f = cmds.xform('spewMarker',q=1,r=1,s=1)
	s.divideSpew(None, org=o, falloff=f, exp=exp, div=div, density=density)


def cubusOverlap():
	ci = cmds.ls(sl=1)
	c1 = cubus(prim=ci[0])
	c2 = cubus(prim=ci[1])
	c1.expandInto(c2)
	cmds.delete(ci[0])
	c1.createPrimitive(ci[0])

def cubes2brushes(outmap, cubelist=[],overwrite=False):
	brushes = "// brush def export\n"
	
	if len(cubelist) > 0:
		cmds.select(cl=1)
		for c in cubelist:
			brushes += "//brush\n"
			brushes += c.emitBrush()
	
	objs = cmds.ls(sl=1)
	if len(objs) > 0:
		for obj in objs:
			c = cubus(prim=obj)
			brushes += "//brush\n"
			brushes += c.emitBrush()
		del c
	
	if overwrite:
		mode='w+'
	else:
		mode='a+'
	mapExport = open( 'd:/games/quake3/baseq3/maps/'+outmap+'.map', mode )
	mapExport.write('{\n"classname"	"func_group"\n')
	mapExport.write(brushes)
	mapExport.write('\n}\n')
	mapExport.close()


def cubePreviewZone(cubeList):
	zone = cmds.ls(sl=True)
	if not zone:
		print "You didn't select anything."
		return
	
	z = cubus(prim=zone[0])
	dc = []
	for c in cubeList:
		if 0 not in c.intersects(z):
			c.createPrimitive()
			dc.append(c)
	for c in dc:
		cubeList.remove(c)
		del(c)

		
#====================

# map2maya.py
# All of this was imported from an older script I wrote to get brushwork into Maya to
# use for reference when making static mesh for maps that never happened

import re, maya.cmds as cmds, sys

# globals are lazy and fun
entities = []
token = ""
numBrushes = 0
objID = 1 # shared by brushes and entities, including brushes that are part of entities
planeID = 1 # shared by all brush faces globally

class Plane():
	def __init__(self):
		self.points = [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]
		self.texture = ""

class Brush():
	def __init__(self):
		self.planes = []
		self.mins = [512000]*3
		self.maxs = [-512000]*3
		
	def getBounds(self):
		mns = [512000]*3
		mxs = [-512000]*3
		for pl in self.planes:
			for i in [0,1,2]:
				if pl.points[0][i] == pl.points[1][i] == pl.points[2][i]:
					ploff = pl.points[0][i]
					if ploff > mxs[i]:
						mxs[i] = ploff 
					if ploff < mns[i]:
						mns[i] = ploff 
		self.mins = [mns[0], mns[2], -mxs[1]]
		self.maxs = [mxs[0], mxs[2], -mns[1]]
	
	def makePrim(self):
		self.getBounds()
		self.size = map(lambda n,x: n-x, self.maxs, self.mins)
		self.origin = map(lambda n,x: (x+n)*0.5, self.maxs, self.mins)
		cubePrim = cmds.polyCube(w=self.size[0],h=self.size[1],d=self.size[2])[0]
		cmds.xform(cubePrim, r=1, t=[self.origin[0], self.origin[1], self.origin[2]] )

class Entity():
	def __init__(self):
		self.brushes = [] #may be empty

def getToken( l = 1 ):
	global token
	try:
		for i in range(l):
			nextToken = mapTokens.next()
	except StopIteration:
		return False
	token = nextToken.group(1)
	return True

def checkToken( test ):
	global token
	getToken()
	if token != test:
		print "Bad token: expected " + test + ", got " + token + "\n"
		raise

def parsePlane( v = 0):
	p = Plane()
	for i in range(3):
		for j in range(3):
			getToken()
			p.points[i][j] = int(token)
		getToken(2) # skip ) (

	getToken(8)

	return p

def parseBrush( v = 0 ):
	global numBrushes
	planes = []
	while getToken():
		if token[:-1] == "patchDef":
			while token != "}":
				getToken()
			getToken()
			return
		elif token == "}":
			break
		elif token == "(":
			planes.append(parsePlane( v ))
	if len(planes) > 0:
		numBrushes += 1
		b = Brush()
		b.planes = planes
		b.makePrim()
		return b
	else:
		return False

def parseEntity( v = 0 ):
	global entities
	e = Entity()
	
	while getToken():
		if token[0] == '"':
			while token[-1] != '"':
				# multiword keyvalue, advance tokens until one ends in "
				getToken()

		elif token == "{":
			# brush def
			b = parseBrush( v )
			if b:
				e.brushes.append(b)
		elif token == "}":
			break
	entities.append(e)

def parseMap(mapFileContents, v = 0):
	global mapTokens
	global token
	global numBrushes
	global entities

	entities = []
	token = ""
	numBrushes = 0

	mapTokenRE = re.compile( '(\S+?)\s+', re.S )
	mapTokens = mapTokenRE.finditer( mapFileContents )

	print "Parsing map file ... "

	while getToken():
		if token == "{":
			parseEntity( v )

	worldBrushes = len(entities[0].brushes)
	print "Entities: " + str(len(entities))
	print "Brushes: " + str(worldBrushes) + " worldspawn, " + str(numBrushes - worldBrushes) + " brush entities"

def importMap(mapIn):
	print "Opening " + mapIn + " ..."
	try:
		mapFileHandle = open( "d:/games/quake3/baseq3/maps/" + mapIn )
		mapFileContents = mapFileHandle.read()
		mapFileHandle.close()
	except:
		print "Couldn't open " + mapIn
		sys.exit()
	
	print "Read " + str(len(mapFileContents)) + " bytes from " + mapIn
	
	parseMap(mapFileContents)

	
#=================================

# Below is the contents of the maya python tab I used to store regularly called functions and methods,
# usually modifying the parameters before calling it.  This was basically my UI.

importMap("cubes/uchunks_xs.map")
 

cubes2brushes("cubes/uchunks_i6",cubez)
cubes2brushes("cubes/uchunks_i6")
cubes2brushes("bigtest")

cubez = lazyDivide(div=(2,9),pushy=(-4,8),exp=1.4,flats=[1,1,1,1,1,1],carves=NO,yeszone=YES)
cubez2 = lazyDivide(div=(1,8),pushy=(8,20),exp=1.5,flats=[1,1,1,1,1,1],carves=NO,yeszone=YES,stairs=1)
cubez = lazyDivide(div=(2,15),pushy=(-4,14),exp=1.6,flats=[1,1,1,1,1,1],carves=NO,yeszone=YES,floors=1)
cubez = lazyDivide(div=(2,15),pushy=(-4,14),exp=1.6,flats=[1,1,1,1,1,1],carves=NO,yeszone=YES)
cubez = lazyDivide(div=(2,16),pushy=(-6,10),exp=1.6,flats=[1,1,1,1,1,1],carves=NO)
cubez = lazyDivide(div=(1,7),pushy=(-4,14),exp=1.35,flats=[1,1,1,1,1,1],carves=NO,yeszone=YES,interval=16)

cubez = lazyDivide(div=(2,8),pushy=(-4,14),exp=1.6,flats=[1,0,0,0,0,0],carves=NO)
cubez = []
cubePreviewZone(cubez)

q = cubus(prim="pCube97")
q.spew()

NO = []
for mesh in cmds.ls(sl=1):
	NO.append(cubus(prim=mesh))

YES = []
for mesh in cmds.ls(sl=1):
	YES.append(cubus(prim=mesh))

lastcube = 0
for c in xrange(lastcube, lastcube+128):
	cubez[c].createPrimitive()
lastcube += 128

for y in YES:
	y.scale(8.0)
for c in CARVE:
	c.scale(8.0)
len(cubez)


# random scatter that I always always had to run three times and then heavily modify
# basically a "create some cubes I can change entirely because I'm too lazy to just make them myself"
cubeSpew("spube",div=(2,6),exp=1.3,density=0.6)
x=2.0
for i in cmds.ls(sl=1):
	cmds.xform(i,r=1,t=[random.randrange(-x,x),random.randrange(-x,x),random.randrange(-x,x)])



a = cubus(prim='no1')
bz = lazyDivide(div=(2,8),pushy=(-4,14),exp=1.65,carves=[a])
bz = lazyDivide(div=(2,12),pushy=(-4,14),exp=1.65,floors=1)
for b in bz:
	b.createPrimitive()


cubeSpew("spube",maxD=6,density=0.6)


map(lambda c: c.createPrimitive(), cList)

# make clip brushes out of lazydivided caulk
for obj in cmds.ls(sl=1):
	c = cubus(prim=obj)
	c.expand(16)
	c.tex = ["common/clip"]*6
	c.createPrimitive()

del(cubez)

for obj in cmds.ls(sl=1):
	cmds.rename(obj, "solid1")

for obj in cmds.ls(sl=1):
	cmds.rename(obj, "empty1")

profile.run('lazyDivide()')

