MaxRects Bin Packing by Skn3

Monkey Forums/Monkey Code/MaxRects Bin Packing by Skn3

Belimoth

(Posted 2013) [#1]

If you are Skn3: I hope you don't mind me touching your code.

If you are not Skn3: Here is a monkey conversion of the MaxRects code that Skn3 posted here. I've converted it to the best of my understanding, ~~but I still get node-related error messages occasionally... I'll continue trying to fix it but if anyone has some insight to share that would be cool too.~~
EDIT: I think I've found the issue.

Here it is so far:

'skn3packer.monkey

' --- arbitrary values --- Belimoth
Const TEXTURE_SIZE_DEFAULT:Int = 256
Const TEXTURE_SIZE_MIN:Int = 16
Const TEXTURE_SIZE_MAX:Int = 512

' --- I've added these classes to cover the things that BlitzMax can do but Monkey can't --- Belimoth
Class Skn3PackerRectList Extends List<Skn3PackerRect>
	Global comparisonCallback:Skn3PackerCompare
	
	Method Compare:Int(lhs:Skn3PackerRect, rhs:Skn3PackerRect)
		Return comparisonCallback.Compare(lhs, rhs)
	End
End

Class Skn3PackerCompare
	Global ByArea := New Skn3PackerCompareByArea()
	
	Method Compare:Int(o1:Object, o2:Object) Abstract
End

Class Skn3PackerCompareByArea Extends Skn3PackerCompare
	Method Compare:Int(o1:Object, o2:Object)
		Local rect1:Skn3PackerRect = Skn3PackerRect(o1)
		Local rect2:Skn3PackerRect = Skn3PackerRect(o2)
		'Assert rect1 And rect2
		If rect1.area < rect2.area Return -1
		If rect1.area > rect2.area Return 1
	End
End

Class Skn3PackerFindPositionForNewNodeResult
	Field bestNode:Skn3PackerRect
	Field bestShortSideFit:Int
	Field bestLongSideFit:Int
	
	Method New(bestNode:Skn3PackerRect, bestShortSideFit:Int, bestLongSideFit:Int)
		Self.bestNode = bestNode
		Self.bestShortSideFit = bestShortSideFit
		Self.bestLongSideFit = bestLongSideFit
	End
End

' --- this is a packer class that should be extended with other algorithms ---
Class Skn3Packer Abstract
	Field algorithm:String
	Field canRotate:Bool = False 'can rotate items
	Field canSplit:Bool = False 'can split onto a new file
	Field border:Int = 3
	Field spacing:Int = 3
	Field errorsTotal:Int = 0
	Field width:Int = TEXTURE_SIZE_DEFAULT
	Field height:Int = TEXTURE_SIZE_DEFAULT
	Field rects := New Skn3PackerRectList()
	Field sheetTotal:Int = 0
	
	'api
	Method Reset:Void() Abstract
	
	Method Repack:Void() Abstract
	
	Method PackRect:Int(rect:Skn3PackerRect) Abstract
	
	Method AttemptPack:Bool(rect:Skn3PackerRect) Abstract
	
	Method AddRect:Skn3PackerRect(width:Int, height:Int, extra:Object = Null, pack:Bool = True)
		' --- add a rect that should be packed ---
		'create a new rect
		Local rect := New Skn3PackerRect()
		
		'set it up
		rect.x = 0
		rect.y = 0
		rect.width = width
		rect.height = height
		rect.area = rect.width * rect.height
		rect.extra = extra
		
		'add it to the packer list of rects
		rects.AddLast(rect)
		
		'sort the rects by largest area first
		Skn3PackerRectList.comparisonCallback = Skn3PackerCompare.ByArea
		rects.Sort(False)
		
		'insert teh pack into the rect
		If pack
			'Local score1:Int
			'Local score2:Int
			AttemptPack(rect)',score1,score2)
		EndIf
		
		'return the rect
		Return rect
	End
	
	Method CopyRects:Skn3PackerRectList()
		' --- return a copy of the rects ---
		Local list := New Skn3PackerRectList
		Local link:list.Node<Skn3PackerRect> = rects.FirstNode()
		Local rect:Skn3PackerRect
		
		While link
			rect = link.Value()
			list.AddLast( rect.Copy() )
			link = link.NextNode()
		Wend
		
		Return list
	End
	
	Method RemoveRect(rect:Skn3PackerRect, pack:Bool = True)
		' --- remove a rect from the packer ---
		If rects.Contains(rect)
			If rect.error Then errorsTotal -= 1
			rects.Remove(rect)
			If pack Then Repack()
		EndIf
	End
	
	Method HasError:Bool(code:Int = 0)
		' --- returns true if there was an error packing one of the rects ---
		If code = 0
			'general error check
			Return (errorsTotal > 0)
		Else
			'specific error check
			Local link:list.Node<Skn3PackerRect> = rects.FirstNode()
			Local rect:Skn3PackerRect
			While link
				rect = link.Value()
				If rect.error = code Then Return True
				link = link.NextNode()
			Wend
		EndIf
	End
	
	Method BestFit:Bool(split:Int = True, guideSize:Int = TEXTURE_SIZE_DEFAULT, minSize:Int = TEXTURE_SIZE_MIN, maxSize:Int = TEXTURE_SIZE_MAX)
		' --- this will best fit the packer ---
		Local oldWidth:Int = width
		Local oldHeight:Int = height
		Local oldCanSplit:Bool = canSplit
		Local oldSheetsTotal:Int = sheetTotal
		Local oldRects:Skn3PackerRectList = CopyRects()
		
		Local smallestSize:Int
		
		'fix size params to correct texture sizes
		If guideSize <> TEXTURE_SIZE_DEFAULT Then guideSize = SizeToPowerOf2(guideSize)
		If minSize <> TEXTURE_SIZE_MIN Then minSize = SizeToPowerOf2(minSize)
		If maxSize <> TEXTURE_SIZE_MAX Then maxSize = SizeToPowerOf2(maxSize)
		
		'figure out the largest item size so we know the minimum the texture can be
		Local link:list.Node<Skn3PackerRect> = rects.FirstNode()
		Local rect:Skn3PackerRect
		While link
			'get rect
			rect = link.Value()
			
			If rect.width > smallestSize Then smallestSize = rect.width
			If rect.height > smallestSize Then smallestSize = rect.height
			
			'next rect
			link = link.NextNode()
		Wend
		
		'convert smallestSize size into power of 2
		smallestSize = SizeToPowerOf2(smallestSize + border + border + spacing + spacing)
		
		'find size that fits without splitting
		Local scanSize:Int = Max(smallestSize, minSize)
		Local scanFound:Bool = False
		canSplit = False
		While scanSize <= maxSize
			'test this size
			width = scanSize
			height = scanSize
			Repack()
			If errorsTotal = 0
				'found a size that works
				scanFound = True
				Exit
			EndIf
			
			scanSize = scanSize * 2
		Wend
		
		'split if not found
		If scanFound = False
			width = maxSize
			height = maxSize
			canSplit = True
			Repack()
			If errorsTotal = 0 Then scanFound = True
		EndIf
		
		'what action to return
		If scanFound = False
			'no success return fail
			width = oldWidth
			height = oldHeight
			canSplit = oldCanSplit
			sheetTotal = oldSheetsTotal
			rects = oldRects
			Return False
		EndIf
		
		'return success and keep changes
		oldRects = Null
		Return True
	End
End

Class Skn3PackerRect
	Field error:Int = 0
	Field sheet:Int = -1
	Field x:Int = 0
	Field y:Int = 0
	Field width:Int = 0
	Field height:Int = 0
	Field area:Int = 0
	Field flipped:Bool = False
	Field extra:Object = Null
	
	'api
	Method Copy:Skn3PackerRect()
		' --- return copy of this rect ---
		Local rect:Skn3PackerRect = New Skn3PackerRect()
		rect.error = error
		rect.sheet = sheet
		rect.x = x
		rect.y = y
		rect.width = width
		rect.height = height
		rect.area = area
		rect.flipped = flipped
		rect.extra = extra
		Return rect
	End
End

Function CreatePacker:Skn3Packer(algorithm:String, width:Int, height:Int, border:Int = 3, spacing:Int = 3, canSplit:Bool = False, canRotate:Bool = False)
	' --- create a packer of a given algorithm ---
	'create packer
	Local packer:Skn3Packer
	Select algorithm.ToLower()
		Case "maxrects"
			packer = New Skn3PackerMaxRects()
		Default
	End
	
	'setup packer
	If packer
		packer.canRotate = canRotate
		packer.canSplit = canSplit
		packer.border = border
		packer.spacing = spacing
		packer.width = width
		packer.height = height
		
		'return packer
		Return packer
	EndIf
End

' --- max rects ---
Class Skn3PackerMaxRectsSheet
	'helper type for max rects sheet
	Field index:Int
	Field usedList := New Skn3PackerRectList
	Field freeList := New Skn3PackerRectList
End

Class Skn3PackerMaxRects Extends Skn3Packer
	Field hasFirstInit:Bool = False
	Field sheet:Skn3PackerMaxRectsSheet
	Field sheets:Skn3PackerMaxRectsSheet[]
	
	'constructor/destructor
	Method New()
		algorithm = "maxrects"
	End
	
	'api
	Method Init()
		' --- init the packer ---
		hasFirstInit = True
		
		'resize/create array
		sheets = New Skn3PackerMaxRectsSheet[1]
		
		'create first sheet
		sheets[0] = New Skn3PackerMaxRectsSheet()
		sheets[0].index = 0
		
		'setup the packer with this sheet
		sheetTotal = 1
		sheet = sheets[0]
		
		'create an intital rect for the texture (use border here sneaky sneaky)
		Local rect:Skn3PackerRect = New Skn3PackerRect
		rect.x = border + spacing
		rect.y = border + spacing
		rect.width = Self.width - border - border - spacing - spacing
		rect.height = Self.height - border - border - spacing - spacing
		sheet.freeList.AddLast(rect)
		
		'reset all rects
		errorsTotal = 0
		Local link:list.Node<Skn3PackerRect> = rects.FirstNode()
		While link
			rect = link.Value()
			rect.error = False
			rect.sheet = -1
			link = link.NextNode()
		Wend
	End
	
	Method Reset:Void()
		' -- this resets all rects to not packed ---
		Init()
	End
	
	Method Repack:Void()
		' --- do the maxrects pack ---
		Local scanRect:Skn3PackerRect
		Local rect:Skn3PackerRect
		
		'Init packer
		Init()
				
		'need to repack all of the rects again
		Local sheetIndex:Int
		Local scanLink:list.Node<Skn3PackerRect> = rects.FirstNode()
		While scanLink
			scanRect = scanLink.Value()
			'check to see if this rect is too large to fit
			
			'set the current sheet to first one (there still might be space)
			sheetIndex = 0
			sheet = sheets[0]
			
			'loop through until the item is packed
			While AttemptPack(scanRect) = False And scanRect.error = False
				'keep the system alive
				KeepSystemAlive()
				
				'increase sheet index
				sheetIndex += 1
				
				'check if the sheet data index slot exists
				If sheetIndex > sheetTotal - 1
					'resize sheets array
					sheets = sheets[..sheetIndex + 1]
					sheetTotal = sheetIndex + 1
					
					'create new sheet
					sheets[sheetIndex] = New Skn3PackerMaxRectsSheet()
					sheets[sheetIndex].index = sheetIndex
					
					'create empty rect
					rect = New Skn3PackerRect()
					rect.x = border + spacing
					rect.y = border + spacing
					rect.width = width - border - border - spacing - spacing
					rect.height = height - border - border - spacing - spacing
					
					'add empty rect to sheet
					sheets[sheetIndex].freeList.AddLast(rect)
				EndIf
				
				'change the active sheet
				sheet = sheets[sheetTotal - 1]
			Wend
			
			'next scan rect
			scanLink = scanLink.NextNode()
		Wend
	End
	
	Method PackRect:Int(rect:Skn3PackerRect)
		' --- pack this rect ---
		If hasFirstInit = False Init()
		
		'set the current sheet to first one (there still might be space)
		Local tempRect:Skn3PackerRect
		Local sheetIndex:Int = 0
		sheet = sheets[0]
				
		'loop through until the item is packed
		While AttemptPack(rect) = False And rect.error
			'keep the system alive
			KeepSystemAlive()
			
			'increase sheet index
			sheetIndex += 1
			
			'check if the sheet data index slot exists
			If sheetIndex > sheetTotal-1
				'resize sheets array
				sheets = sheets[..sheetIndex+1]
				sheetTotal = sheetIndex+1
				
				'create new sheet
				sheets[sheetIndex] = New Skn3PackerMaxRectsSheet()
				sheets[sheetIndex].index = sheetIndex
				
				'create empty rect
				tempRect = New Skn3PackerRect()
				tempRect.x = border + spacing
				tempRect.y = border + spacing
				tempRect.width = width - border - border - spacing - spacing
				tempRect.height = height - border - border - spacing - spacing
				
				'add empty rect to sheet
				sheets[sheetIndex].freeList.AddLast(tempRect)
			EndIf
			
			'change the active sheet
			sheet = sheets[sheetTotal - 1]
		Wend
		
		'return the success of the operation
		Return rect.error
	End
	
	Method AttemptPack:Bool(rect:Skn3PackerRect)
		' --- attempt a pack ---
		'remove error count as we are essentially repacking
		If rect.error Then errorsTotal -= 1
		
		'check for skipping
		If (rect.width = 0) Or (rect.height = 0)
			rect.error = True
			rect.sheet = -1
			rect.x = 0
			rect.y = 0
			rect.flipped = False
			
			'increase error count
			errorsTotal += 1
			
			Return False
		EndIf
		
		'check to see if the rect is out of bounds to start with
		'checking for too large
		Local maxWidth:Int = width - border - border - spacing - spacing
		Local maxHeight:Int = height - border - border - spacing - spacing
		If (canRotate = False And (rect.width > maxWidth Or rect.height > maxHeight)) Or (canRotate = True And Not((rect.width <= maxWidth And rect.height <= maxHeight) Or (rect.height <= maxWidth And rect.width <= maxHeight)))
			'setup rect with error
			rect.error = True
			rect.sheet = -1
			rect.x = 0
			rect.y = 0
			rect.flipped = False
			
			'increase error count
			errorsTotal += 1
			
			Return False
		EndIf
		
		'process this item as it can fit
		Local findRect:Skn3PackerRect
		Local scanRect:Skn3PackerRect
		Local scanLink1:list.Node<Skn3PackerRect>
		Local scanLastLink:list.Node<Skn3PackerRect>
		
		Local _result:Skn3PackerFindPositionForNewNodeResult = FindPositionForNewNodeBestShortSideFit(rect.width, rect.height)
		findRect = _result.bestNode
		Local score1:Int = _result.bestShortSideFit
		Local score2:Int = _result.bestLongSideFit
		'findRect = FindPositionForNewNodeBottomLeft(rect.width, rect.height, score1, score2)
		'findRect = FindPositionForNewNodeContactPoint(rect.width, rect.height, score1)
		'findRect = FindPositionForNewNodeBestLongSideFit(rect.width, rect.height, score2, score1)
		'findRect = FindPositionForNewNodeBestAreaFit(rect.width, rect.height, score1, score2)
		
		'a space could not be found so how do we proceed
		If findRect.height = 0
			If canSplit
				'ONLY return false so the texture is split in teh next attempt
				Return False
			Else
				'can't split onto multiple sheets
				'setup rect with error
				rect.error = True
				rect.sheet = -1
				rect.x = 0
				rect.y = 0
				rect.flipped = False
				
				'increase error count
				errorsTotal += 1
				
				Return False
			EndIf
		EndIf
		
		'slice and prune existing free nodes
		scanLink1 = sheet.freeList.FirstNode()
		scanLastLink = sheet.freeList.LastNode()
		While scanLink1
			'get teh rect from teh link
			scanRect = scanLink1.Value()
			
			'---Belimoth
			Local nextLink := scanLink1.NextNode()
			Local isLast:Bool = False
			If scanLink1 = scanLastLink Then isLast = True
			
			'do some slicing on the rect if it returns true it means that the rect was infact sliced (so remove it)
			If SplitFreeNode(scanRect, findRect) Then scanLink1.Remove()
			
			'exit loop if got to end (determined before starting the loop)
			If isLast Then Exit'If scanLink1 = scanLastLink Then Exit
			
			'move to next rect
			scanLink1 = nextLink
		Wend
		PruneFreeList()
		
		'add self to used rectangles
		sheet.usedList.AddLast(findRect)
		
		'update the passed in rect position
		rect.sheet = sheet.index
		rect.x = findRect.x
		rect.y = findRect.y
		rect.flipped = findRect.flipped
		
		'return success
		Return True
	End
	
	Method FindPositionForNewNodeBestShortSideFit:Skn3PackerFindPositionForNewNodeResult(width:Int, height:Int)
		Local scanLink:list.Node<Skn3PackerRect>
		Local scanRect:Skn3PackerRect
		Local bestNode := New Skn3PackerRect()
		Local leftoverHoriz:Int
		Local leftoverVert:Int
		Local shortSideFit:Int
		Local longSideFit:Int
		Local flippedLeftoverHoriz:Int
		Local flippedLeftoverVert:Int
		Local flippedShortSideFit:Int
		Local flippedLongSideFit:Int

		Local bestShortSideFit:Int = 2147483647
		Local bestLongSideFit:Int = 0
		
		scanLink = sheet.freeList.FirstNode()
		While scanLink
			scanRect = scanLink.Value()
			
			'Try To place the Rectangle in upright (non-flipped) orientation.
			If scanRect.width >= width And scanRect.height >= height
				leftoverHoriz = Abs(scanRect.width - width)
				leftoverVert = Abs(scanRect.height - height)
				shortSideFit = Min(leftoverHoriz, leftoverVert)
				longSideFit = Max(leftoverHoriz, leftoverVert)
	
				If shortSideFit < bestShortSideFit Or (shortSideFit = bestShortSideFit And longSideFit < bestLongSideFit)
					bestNode.x = scanRect.x
					bestNode.y = scanRect.y
					bestNode.width = width
					bestNode.height = height
					bestNode.flipped = False
					
					bestShortSideFit = shortSideFit
					bestLongSideFit = longSideFit
				EndIf
			EndIf
			
			If canRotate And scanRect.width >= height And scanRect.height >= width
				flippedLeftoverHoriz = Abs(scanRect.width - height)
				flippedLeftoverVert = Abs(scanRect.height - width)
				flippedShortSideFit = Min(flippedLeftoverHoriz, flippedLeftoverVert)
				flippedLongSideFit = Max(flippedLeftoverHoriz, flippedLeftoverVert)
	
				If flippedShortSideFit < bestShortSideFit Or (flippedShortSideFit = bestShortSideFit And flippedLongSideFit < bestLongSideFit)
					bestNode.x = scanRect.x
					bestNode.y = scanRect.y
					bestNode.width = height
					bestNode.height = width
					bestNode.flipped = True
					
					bestShortSideFit = flippedShortSideFit
					bestLongSideFit = flippedLongSideFit
				EndIf
			EndIf
		
			scanLink = scanLink.NextNode()
		Wend
		
		Return New Skn3PackerFindPositionForNewNodeResult(bestNode, bestShortSideFit, bestLongSideFit)
	End
	
	#Rem
	Method FindPositionForNewNodeBottomLeft:Skn3PackerRect(width:Int, Height:Int,bestY:Int Var,bestX:Int Var)
		Local scanLink:TLink
		Local scanRect:Skn3PackerRect
		Local bestNode:Skn3PackerRect = New Skn3PackerRect
		Local topSideY:Int
		
		bestY = 2147483647
		
		scanLink = sheet.freeList.FirstLink()
		While scanLink
			scanRect = Skn3PackerRect(scanLink.value())	
		
			'Try To place the Rectangle in upright (non-flipped) orientation.
			If scanRect.width >= width And scanRect.Height >= Height
				topSideY = scanRect.Y + Height
				If topSideY < bestY Or (topSideY = bestY And scanRect.X < bestX)
					bestNode.X = scanRect.X
					bestNode.Y = scanRect.Y
					bestNode.width = width
					bestNode.Height = Height
					bestNode.flipped = False
					
					bestY = topSideY
					bestX = scanRect.X
				EndIf
			EndIf
			
			If canRotate And scanRect.width >= Height And scanRect.Height >= width
				topSideY = scanRect.Y + width
				If topSideY < bestY Or (topSideY = bestY And scanRect.X < bestX)
					bestNode.X = scanRect.X
					bestNode.Y = scanRect.Y
					bestNode.width = height
					bestNode.Height = width
					bestNode.flipped = True
					
					bestY = topSideY
					bestX = scanRect.X
				End If
			End If
			
			scanLink = scanLink.NextLink()
		Wend
		
		Return bestNode
	End Method
	
	Method FindPositionForNewNodeBestLongSideFit:Skn3PackerRect(width:Int,Height:Int,bestShortSideFit:Int Var,bestLongSideFit:Int Var)
		Local scanLink:TLink
		Local scanRect:Skn3PackerRect
		Local bestNode:Skn3PackerRect = New Skn3PackerRect
		Local leftoverHoriz:Int
		Local leftoverVert:Int
		Local shortSideFit:Int
		Local longSideFit:Int
		
		bestLongSideFit = 2147483647
	
		scanLink = sheet.freeList.FirstLink()
		While scanLink
			scanRect = Skn3PackerRect(scanLink.Value())
			
			'Try To place the Rectangle in upright (non-flipped) orientation.
			If scanRect.width >= width And scanRect.Height >= Height
				leftoverHoriz = Abs(scanRect.width - width)
				leftoverVert = Abs(scanRect.Height - Height)
				shortSideFit = min(leftoverHoriz, leftoverVert)
				longSideFit = max(leftoverHoriz, leftoverVert)
	
				If longSideFit < bestLongSideFit Or (longSideFit = bestLongSideFit And shortSideFit < bestShortSideFit)
					bestNode.X = scanRect.X
					bestNode.y = scanRect.y
					bestNode.width = width
					bestNode.Height = Height
					bestNode.flipped = False
					
					bestShortSideFit = shortSideFit
					bestLongSideFit = longSideFit
				End If
			End If
	
			If canRotate And scanRect.width >= Height And scanRect.Height >= width
				leftoverHoriz = Abs(scanRect.width - Height)
				leftoverVert = Abs(scanRect.Height - width)
				shortSideFit = min(leftoverHoriz, leftoverVert)
				longSideFit = max(leftoverHoriz, leftoverVert)
	
				If longSideFit < bestLongSideFit Or (longSideFit = bestLongSideFit And shortSideFit < bestShortSideFit)
					bestNode.X = scanRect.X
					bestNode.y = scanRect.y
					bestNode.width = height
					bestNode.Height = width
					bestNode.flipped = True
					
					bestShortSideFit = shortSideFit
					bestLongSideFit = longSideFit
				End If
			End If
		
			scanLink = scanLink.NextLink()
		Wend
		return bestNode
	End Method
	
	Method FindPositionForNewNodeBestAreaFit:Skn3PackerRect(width:Int,Height:Int,bestAreaFit:Int Var,bestShortSideFit:Int Var)
		Local scanLink:TLink
		Local scanRect:Skn3PackerRect
		Local bestNode:Skn3PackerRect = New Skn3PackerRect
		Local areaFit:Int
		Local leftoverHoriz:Int
		Local leftoverVert:Int
		Local shortSideFit:Int
		
		bestAreaFit = 2147483647
	
		scanLink = sheet.freeList.FirstLink()
		While scanLink
			scanRect = Skn3PackerRect(scanLink.Value())
			
			areaFit = scanRect.width * scanRect.Height - width * Height
	
			'Try to place the rectangle in upright (non-flipped) orientation.
			If scanRect.width >= width And scanRect.Height >= Height
				leftoverHoriz = Abs(scanRect.width - width)
				leftoverVert = Abs(scanRect.Height - Height)
				shortSideFit = min(leftoverHoriz, leftoverVert)
	
				If areaFit < bestAreaFit Or (areaFit = bestAreaFit And shortSideFit < bestShortSideFit)
					bestNode.X = scanRect.X
					bestNode.y = scanRect.y
					bestNode.width = width
					bestNode.Height = Height
					bestNode.flipped = False
					
					bestShortSideFit = shortSideFit
					bestAreaFit = areaFit
				End If
			End If
	
			If canRotate And scanRect.width >= Height And scanRect.Height >= width
				leftoverHoriz = Abs(scanRect.width - Height)
				leftoverVert = Abs(scanRect.Height - width)
				shortSideFit = min(leftoverHoriz, leftoverVert)
	
				If areaFit < bestAreaFit Or (areaFit = bestAreaFit And shortSideFit < bestShortSideFit)
					bestNode.X = scanRect.X
					bestNode.y = scanRect.y
					bestNode.width = height
					bestNode.Height = width
					bestNode.flipped = True
					
					bestShortSideFit = shortSideFit
					bestAreaFit = areaFit
				End If
			End If
		
			scanLink = scanLink.NextLink()
		Wend
		return bestNode
	End Method
	
	Method FindPositionForNewNodeContactPoint:Skn3PackerRect(width:Int,Height:Int,bestContactScore:Int Var)
		Local scanLink:TLink
		Local scanRect:Skn3PackerRect
		Local bestNode:Skn3PackerRect = New Skn3PackerRect
		Local score:Int
		
		bestContactScore = -1
	
		scanLink = sheet.freeList.FirstLink()
		While scanLink
			scanRect = Skn3PackerRect(scanLink.Value())
			
			'Try To place the Rectangle in upright (non-flipped) orientation.
			If scanRect.width >= width And scanRect.Height >= Height
				score = ContactPointScoreNode(scanRect.X, scanRect.Y, width, Height)
				If score > bestContactScore
					bestNode.X = scanRect.X
					bestNode.y = scanRect.y
					bestNode.width = width
					bestNode.Height = Height
					bestNode.flipped = False
					
					bestContactScore = score
				End If
			End If
			
			If canRotate And scanRect.width >= Height And scanRect.Height >= width
				score = ContactPointScoreNode(scanRect.X, scanRect.Y, width, Height)
				If score > bestContactScore
					bestNode.X = scanRect.X
					bestNode.y = scanRect.y
					bestNode.width = height
					bestNode.Height = width
					bestNode.flipped = True
					
					bestContactScore = score
				End If
			End If
		
			scanLink = scanLink.NextLink()
		Wend
		return bestNode
	End Method
	#End
	
	Method CommonIntervalLength:Int(i1start:Int, i1end:Int, i2start:Int, i2end:Int)
		If i1end < i2start Or i2end < i1start Then Return 0
		Return Min(i1end, i2end) - Max(i1start, i2start)
	End
	
	Method ContactPointScoreNode:Int(x:Int, y:Int, width:Int, height:Int)
		Local score:Int = 0
	
		If x = 0 Or y + width = Self.width Then score += height
		If x = 0 Or y + height = Self.height Then score += width
		
		Local link:list.Node<Skn3PackerRect> = sheet.usedList.FirstNode()
		Local scanRect:Skn3PackerRect
		While link
			scanRect = link.Value()
			If scanRect.x = x + width Or scanRect.x + scanRect.width = x Then score += CommonIntervalLength(scanRect.y, scanRect.y + scanRect.height, y, y + height)
			
			If scanRect.x = x + height Or scanRect.y + scanRect.height = y Then score += CommonIntervalLength(scanRect.x, scanRect.x + scanRect.width, x, x + width)
			link = link.NextNode()
		Wend
		return score
	End
	
	Method SplitFreeNode:Bool(freeNode:Skn3PackerRect, usedNode:Skn3PackerRect)
		Local newRect:Skn3PackerRect
		Local newSize:Int
		
		'Test with SAT If the rectangles Even Intersect.
		If usedNode.x - spacing >= freeNode.x + freeNode.width Or usedNode.x + usedNode.width + spacing <= freeNode.x Or usedNode.y - spacing >= freeNode.y + freeNode.height Or usedNode.y + usedNode.height + spacing <= freeNode.y  Then Return False
		
		If usedNode.x < freeNode.x + freeNode.width And usedNode.x + usedNode.width > freeNode.x
			' New node at the top side of the used node.
			If usedNode.y > freeNode.y And usedNode.y < freeNode.y + freeNode.height
				newSize = usedNode.y - freeNode.y - spacing
				If newSize > 0
					newRect = New Skn3PackerRect()
					
					newRect.x = freeNode.x
					newRect.y = freeNode.y
					newRect.width = freeNode.width
					newRect.height = newSize
					
					sheet.freeList.AddLast(newRect)
				EndIf
			EndIf
	
			' New node at the bottom side of the used node.
			If usedNode.y + usedNode.height < freeNode.y + freeNode.height
				newSize = freeNode.y + freeNode.height - (usedNode.y + usedNode.height) - spacing
				If newSize > 0
					newRect = New Skn3PackerRect()
					
					newRect.x = freeNode.x
					newRect.y = usedNode.y + usedNode.height + spacing
					newRect.width = freeNode.width
					newRect.height = newSize
					
					sheet.freeList.AddLast(newRect)
				EndIf
			EndIf
		EndIf
	
		If usedNode.y < freeNode.y + freeNode.height And usedNode.y + usedNode.height > freeNode.y
			' New node at the left side of the used node.
			If usedNode.x > freeNode.x And usedNode.x < freeNode.x + freeNode.width
				newSize = usedNode.x - freeNode.x - spacing
				If newSize
					newRect = New Skn3PackerRect()
					
					newRect.x = freeNode.x
					newRect.y = freeNode.y
					newRect.width = newSize
					newRect.height = freeNode.height
					
					sheet.freeList.AddLast(newRect)
				EndIf
			EndIf
	
			' New node at the right side of the used node.
			If usedNode.x + usedNode.width < freeNode.x + freeNode.width
				newSize = freeNode.x + freeNode.width - (usedNode.x + usedNode.width) - spacing
				If newSize
					newRect = New Skn3PackerRect()
					
					newRect.x = usedNode.x + usedNode.width + spacing
					newRect.y = freeNode.y
					newRect.width = newSize
					newRect.height = freeNode.height
					
					sheet.freeList.AddLast(newRect)
				EndIf
			EndIf
		EndIf
	
		Return True
	End
	
	Method SplitFreeNodeWithoutSpacing:Bool(freeNode:Skn3PackerRect, usedNode:Skn3PackerRect)
		Local newRect:Skn3PackerRect
		
		'Test with SAT If the rectangles Even Intersect.
		If usedNode.x >= freeNode.x + freeNode.width Or usedNode.x + usedNode.width <= freeNode.x Or usedNode.y >= freeNode.y + freeNode.height Or usedNode.y + usedNode.height <= freeNode.y Then Return False
		
		If usedNode.x < freeNode.x + freeNode.width And usedNode.x + usedNode.width > freeNode.x
			' New node at the top side of the used node.
			If usedNode.y > freeNode.y And usedNode.y < freeNode.y + freeNode.height
				newRect = New Skn3PackerRect()
				
				newRect.x = freeNode.x
				newRect.y = freeNode.y
				newRect.width = freeNode.width
				newRect.height = usedNode.y - newRect.y
				
				sheet.freeList.AddLast(newRect)
			EndIf
	
			' New node at the bottom side of the used node.
			If usedNode.y + usedNode.height < freeNode.y + freeNode.height
				newRect = New Skn3PackerRect()
				
				newRect.x = freeNode.x
				newRect.y = usedNode.y + usedNode.height
				newRect.width = freeNode.width
				newRect.height = freeNode.y + freeNode.height - (usedNode.y + usedNode.height)
				
				sheet.freeList.AddLast(newRect)
			EndIf
		EndIf
	
		If usedNode.y < freeNode.y + freeNode.height And usedNode.y + usedNode.height > freeNode.y
			' New node at the left side of the used node.
			If usedNode.x > freeNode.x And usedNode.x < freeNode.x + freeNode.width
				newRect = New Skn3PackerRect()
				
				newRect.x = freeNode.x
				newRect.y = freeNode.y
				newRect.width = usedNode.x - newRect.x
				newRect.height = freeNode.height
				
				sheet.freeList.AddLast(newRect)
			End If
	
			' New node at the right side of the used node.
			If usedNode.x + usedNode.width < freeNode.x + freeNode.width
				newRect = New Skn3PackerRect()
				
				newRect.x = usedNode.x + usedNode.width
				newRect.y = freeNode.y
				newRect.width = freeNode.x + freeNode.width - (usedNode.x + usedNode.width)
				newRect.height = freeNode.height
				
				sheet.freeList.AddLast(newRect)
			EndIf
		EndIf
	
		Return True
	End
		
	Method PruneFreeList:Void()
		Local scanLink1:list.Node<Skn3PackerRect>
		Local scanLink2:list.Node<Skn3PackerRect>
		Local scanRect1:Skn3PackerRect
		Local scanRect2:Skn3PackerRect
		
		'go through each free rectangle
		scanLink1 = sheet.freeList.FirstNode()
		While scanLink1
			'---Belimoth
			Local nextLink1 := scanLink1.NextNode()
			
			'get the rect from teh tlink
			scanRect1 = scanLink1.Value()
			
			'test self against all over free rectangles
			scanLink2 = sheet.freeList.FirstNode()
			While scanLink2
				'---Belimoth
				Local nextLink2 := scanLink2.NextNode()
				
				'dont bother testing against self.. duh!
				If scanLink1 <> scanLink2
					'get rect from link
					scanRect2 = scanLink2.Value()
					
					'check to see if the rect1 is inside rect2
					If IsContainedIn(scanRect1, scanRect2)
						scanLink1.Remove()
						Exit
					EndIf
					
					'check to see if the rect2 is inside rect1
					If IsContainedIn(scanRect2, scanRect1) Then scanLink2.Remove()
				Else
					'---Belimoth, this should fix the error I was getting
					If nextLink2 = Null Then Exit
					nextLink2 = nextLink2.NextNode()
				EndIf
				
				'get next link
				scanLink2 = nextLink2 'scanLink2 = scanLink2.NextNode()
			Wend
			
			'get the next link
			scanLink1 = nextLink1 'scanLink1 = scanLink1.NextNode()
		Wend
	End
	
	Method IsContainedIn:Bool(a:Skn3PackerRect, b:Skn3PackerRect)
		Return (a.x >= b.x) And (a.y >= b.y) And (a.x + a.width <= b.x + b.width) And (a.y + a.height <= b.y + b.height)
	End
End

'---Belimoth
Function KeepSystemAlive:Void()
	'I don't know what this is supposed to do???---Belimoth
End

Function SizeToPowerOf2:Int(size:Int)
	Local sizeToPowerOf2:Int = 1
	While sizeToPowerOf2 < size
		sizeToPowerOf2 *= 2
	Wend
	Return sizeToPowerOf2
End

Here is an example:

Strict
Import mojo
Import skn3packer
'#REFLECTION_FILTER="*"
'Import reflection

Class MyObject
	Global idNext:Int
	
	Field width:Int
	Field height:Int
	
	Field color:Int[]
	Field id:Int
	
	Method New(width:Int, height:Int)
		Self.width = width
		Self.height = height
				
		color = [ Int( Rnd(255) ), Int( Rnd(255) ), Int( Rnd(255) ) ]
		
		id = idNext
		idNext += 1
	End
End

Class MyApp Extends App
	Field packer:Skn3PackerMaxRects
	Field sheet:Int
	Field toggle:Bool
	Field mx:Int, my:Int
	
	Method OnCreate:Int()
		packer = Skn3PackerMaxRects( CreatePacker("maxrects", 256, 256, True) )
		packer.Init()
		SetUpdateRate(60)
		Return 0
	End
	
	Method OnUpdate:Int()
		If MouseHit(MOUSE_LEFT)
			If Not toggle
				mx = MouseX()
				my = MouseY()
				toggle = True
			Else
				Local x0:Int = Min( MouseX(), Float(mx) )
				Local y0:Int = Min( MouseY(), Float(my) )
				Local x1:Int = Max( MouseX(), Float(mx) )
				Local y1:Int = Max( MouseY(), Float(my) )
				Local w:Int = x1 - x0 + 1
				Local h:Int = y1 - y0 + 1
				Local myObject := New MyObject(w, h)
				packer.AddRect(w, h, myObject, True)
				toggle = False
			EndIf
		EndIf
		
		If KeyHit(KEY_SPACE)
			packer.Repack()
		EndIf
		
		If KeyHit(KEY_LEFT) Then sheet = (sheet + packer.sheetTotal) Mod packer.sheetTotal
		If KeyHit(KEY_RIGHT) Then sheet = (sheet + 1) Mod packer.sheetTotal
		
		Return 0
	End
	
	Method OnRender:Int()
		Cls()
		SetColor 10, 10, 10
		DrawRect 10, 10, packer.width, packer.height
		
		SetColor 255, 255, 255
		DrawText (sheet + 1) + " / " + packer.sheetTotal, 0, 0
		
		If toggle
			Local x0:Int = Min( MouseX(), Float(mx) )
			Local y0:Int = Min( MouseY(), Float(my) )
			Local x1:Int = Max( MouseX(), Float(mx) )
			Local y1:Int = Max( MouseY(), Float(my) )
			DrawRect x0, y0, x1 - x0 + 1, y1 - y0 + 1
		EndIf
		
		For Local rect:Skn3PackerRect = EachIn packer.rects
			If rect.sheet = sheet
				Local color:Int[] = MyObject(rect.extra).color
				SetColor color[0], color[1], color[2]
				DrawRect 10 + rect.x, 10 + rect.y, rect.width, rect.height
			EndIf
		Next
		Return 0
	End
End

Function Main:Int()
	New MyApp()
	Return 0
End

Click to make a shape and add it to the bin, space to repack. Haven't figured out exactly how sheets work yet.