RectPacker

RectPacker.cs

using System.Drawing;
using System.Drawing.Drawing2D;
using FastBitmap;
using System;
using System.Collections.Generic;

namespace SkinsetGenerator
{
	public abstract class RectPacker
	{
		int m_iPadding;
		Bitmap m_oBitmap;
		public RectPacker()
		{
			Reset(1, 1, 0);
		}

		public Bitmap GetBitmap()
		{
			return m_oBitmap;
		}

		protected int Padding { get { return m_iPadding; } }

		public void Reset(int iWidth, int iHeight, int iPadding)
		{
			m_iPadding = iPadding;
			m_oBitmap = new Bitmap(iWidth, iHeight);
			m_oBitmap.MakeTransparent();

			using (var oFast = m_oBitmap.FastLock())
			{
				oFast.Clear(Color.FromArgb(0, 0, 0, 0));
			}

			SetupImplementation(iWidth, iHeight);
		}

		public bool Insert(Bitmap oBitmap, int iID)
		{
			Point oPoint;
			return Insert(oBitmap, iID, out oPoint);
		}

		public bool Insert(Bitmap oBitmap, int iID, out Point oOutPoint)
		{
			Point oPoint;
			if (Insert(oBitmap.Width + m_iPadding * 2, oBitmap.Height + m_iPadding * 2, iID, out oPoint))
			{
				oOutPoint = oPoint;
				using (var oLock = m_oBitmap.FastLock())
				{
					Rectangle oDstRect = new Rectangle(oPoint.X + m_iPadding, oPoint.Y + m_iPadding, oBitmap.Width, oBitmap.Height);
					oLock.CopyRegion(oBitmap, new Rectangle(0, 0, oBitmap.Width, oBitmap.Height), oDstRect);

					if (m_iPadding > 0)
					{
						using (FastBitmap.FastBitmap oLockSrc = oBitmap.FastLock())
						{

							//Corner Top Left
							{
								Color oColor = oLockSrc.GetPixel(0, 0);
								for (int iX = Math.Max(0, oDstRect.Left - 1), iEndX = Math.Max(0, oDstRect.Left - m_iPadding); iX >= iEndX; --iX)
								{
									for (int iY = Math.Max(0, oDstRect.Top - 1), iEndY = Math.Max(0, oDstRect.Top - m_iPadding); iY >= iEndY; --iY)
									{
										oLock.SetPixel(iX, iY, oColor);
									}
								}
							}

							//Corner Top Right
							{
								Color oColor = oLockSrc.GetPixel(oLockSrc.Width - 1, 0);
								for (int iX = Math.Min(oLock.Width - 1, oDstRect.Right), iEndX = Math.Min(oLock.Width - 1, oDstRect.Right + m_iPadding - 1); iX <= iEndX; ++iX)
								{
									for (int iY = Math.Max(0, oDstRect.Top - 1), iEndY = Math.Max(0, oDstRect.Top - m_iPadding); iY >= iEndY; --iY)
									{
										oLock.SetPixel(iX, iY, oColor);
									}
								}
							}

							//Corner Bottom Left
							{
								Color oColor = oLockSrc.GetPixel(0, oLockSrc.Height - 1);
								for (int iX = Math.Max(0, oDstRect.Left - 1), iEndX = Math.Max(0, oDstRect.Left - m_iPadding); iX >= iEndX; --iX)
								{
									for (int iY = Math.Min(oLock.Height - 1, oDstRect.Bottom), iEndY = Math.Min(oLock.Height - 1, oDstRect.Bottom + m_iPadding - 1); iY <= iEndY; ++iY)
									{
										oLock.SetPixel(iX, iY, oColor);
									}
								}
							}

							//Corner Bottom Right
							{
								Color oColor = oLockSrc.GetPixel(oLockSrc.Width - 1, oLockSrc.Height - 1);
								for (int iX = Math.Min(oLock.Width - 1, oDstRect.Right), iEndX = Math.Min(oLock.Width - 1, oDstRect.Right + m_iPadding - 1); iX <= iEndX; ++iX)
								{
									for (int iY = Math.Min(oLock.Height - 1, oDstRect.Bottom), iEndY = Math.Min(oLock.Height - 1, oDstRect.Bottom + m_iPadding - 1); iY <= iEndY; ++iY)
									{
										oLock.SetPixel(iX, iY, oColor);
									}
								}
							}

							//Top / Bottom
							for (int iX = 0; iX < oLockSrc.Width; ++iX)
							{
								Color oColorTop = oLockSrc.GetPixel(iX, 0);
								Color oColorBottom = oLockSrc.GetPixel(iX, oLockSrc.Height - 1);

								for (int iP = 1; iP <= m_iPadding; ++iP)
								{
									oLock.SetPixel(oDstRect.X + iX, oDstRect.Top - iP, oColorTop);
									oLock.SetPixel(oDstRect.X + iX, oDstRect.Bottom - 1 + iP, oColorBottom);
								}
							}

							//Left / Right
							for (int iY = 0; iY < oLockSrc.Height; ++iY)
							{
								Color oColorTop = oLockSrc.GetPixel(0, iY);
								Color oColorBottom = oLockSrc.GetPixel(oLockSrc.Width - 1, iY);

								for (int iP = 1; iP <= m_iPadding; ++iP)
								{
									oLock.SetPixel(oDstRect.Left - iP, oDstRect.Top + iY, oColorTop);
									oLock.SetPixel(oDstRect.Right - 1 + iP, oDstRect.Top + iY, oColorBottom);
								}
							}
						}
					}
				}
				return true;
			}
			oOutPoint = new Point(-1, -1);
			return false;
		}

		//Pure virtual functions
		public abstract void SetupImplementation(int iWidth, int iHeight);
		public abstract Rectangle GetRectangleById(int iID);
		public abstract bool Insert(int iWidth, int iHeight, int iID, out Point oPoint);

	}

	public class RectPackerNode : RectPacker
	{
		class Node
		{
			public Node[] Child;
			public Rectangle Rect;
			public int ImageID = 0;
			public bool VerticalSplit = false;

			public Node GetById(int iId)
			{
				if (ImageID == iId)
					return this;

				if (Child != null)
				{
					Node oNode = Child[0].GetById(iId);
					if (oNode != null)
						return oNode;

					oNode = Child[1].GetById(iId);
					if (oNode != null)
						return oNode;
				}

				return null;
			}

			int GetFreeWidthSpace()
			{
				if( ImageID == 0)
				{
					return Rect.Width;
				}
				else if (Child != null)
				{
					int iHeightA = Child[0].GetFreeWidthSpace();
					int iHeightB = Child[1].GetFreeWidthSpace();
					return System.Math.Max(iHeightA, iHeightB);
				}

				return 0;
			}

			int GetFreeHeightSpace()
			{
				if (ImageID == 0)
				{
					return Rect.Height;
				}
				else if (Child != null)
				{
					int iHeightA = Child[0].GetFreeHeightSpace();
					int iHeightB = Child[1].GetFreeHeightSpace();
					return System.Math.Max(iHeightA, iHeightB);
				}

				return 0;
			}

			public Node Insert(int iWidth, int iHeight, bool bPerfect, int iPadding)
			{
				int iInputRectWidth = iWidth + iPadding * 2;
				int iInputRectHeight = iHeight + iPadding * 2;

				if (Child != null)
				{
					/*try inserting into first child*/

					Node newNode = null;
					/*if (iHeight == Child[1].Rect.Height)
					{
						newNode = Child[1].Insert(img, bPerfect, iPadding);
						if (newNode != null)
							return newNode;
					}*/

					int iHeightA = Child[0].GetFreeHeightSpace();
					int iHeightB = Child[1].GetFreeHeightSpace();
					int iHeightDiffA = Math.Abs(iHeightA - iHeight);
					int iHeightDiffB = Math.Abs(iHeightB - iHeight);

					int iWidthA = Child[0].GetFreeWidthSpace();
					int iWidthB = Child[1].GetFreeWidthSpace();
					int iWidthDiffA = Math.Abs(iWidthA - iWidth);
					int iWidthDiffB = Math.Abs(iWidthB - iWidth);

					if ((iWidthDiffA + iHeightDiffA) < (iWidthDiffB + iHeightDiffB))
					{
						newNode = Child[0].Insert(iWidth, iHeight, bPerfect, iPadding);
						if (newNode != null)
							return newNode;

						newNode = Child[1].Insert(iWidth, iHeight, bPerfect, iPadding);
						if (newNode != null)
							return newNode;
					}
					else
					{
						newNode = Child[1].Insert(iWidth, iHeight, bPerfect, iPadding);
						if (newNode != null)
							return newNode;

					newNode = Child[0].Insert(iWidth, iHeight, bPerfect, iPadding);
					if (newNode != null)
						return newNode;
					}

					return null;

					
					/*newNode = Child[0].Insert(img, bPerfect, iPadding);
					if (newNode != null)
						return newNode;*/

					/*no room, insert into second*/
					//return Child[1].Insert(img, bPerfect, iPadding);
				}
				else
				{
					/*if there's already a lightmap here, return*/
					if (ImageID != 0)
						return null;

					/*if we're too small, return*/
					if (iInputRectWidth > Rect.Width || iInputRectHeight > Rect.Height)
						return null;

					/*if we're just right, accept*/
					if (iInputRectWidth == Rect.Width && iInputRectHeight == Rect.Height)
						return this;

					if (bPerfect && (iInputRectWidth < Rect.Width && iInputRectHeight < Rect.Height))
						return null;

					/*otherwise, gotta split this node and create some kids*/
					Child = new Node[2] { new Node(), new Node() };

					/*decide which way to split*/
					int width = iInputRectWidth;
					int height = iInputRectHeight;
					int dw = Rect.Width - width;
					int dh = Rect.Height - height;

					if (dw > dh)
					{
						VerticalSplit = false;
						Child[0].Rect = new Rectangle(Rect.X, Rect.Y,
												   width, Rect.Height);
						Child[1].Rect = new Rectangle(Rect.X + width + 1, Rect.Y,
												   Rect.Width - width - 1, Rect.Height);
					}
					else
					{
						VerticalSplit = true;
						Child[0].Rect = new Rectangle(Rect.X, Rect.Y,
												   Rect.Width, height);
						Child[1].Rect = new Rectangle(Rect.X, Rect.Y + height + 1,
												   Rect.Width, Rect.Height - height - 1);
					}

					/*insert into first child we created*/
					return Child[0].Insert(iWidth, iHeight, bPerfect, iPadding);
				}
			}
		}

		Node m_oRoot;

		public RectPackerNode()
		{
		}

		public override void SetupImplementation(int iWidth, int iHeight)
		{
			m_oRoot = new Node();
			m_oRoot.Rect = new Rectangle(0, 0, iWidth, iHeight);
		}

		public override bool Insert(int iWidth, int iHeight, int iID, out Point oPoint)
		{
			Node pNode = m_oRoot.Insert(iWidth, iHeight, true, Padding);
			if (pNode == null)
				pNode = m_oRoot.Insert(iWidth, iHeight, false, Padding);
			if (pNode != null)
			{
				pNode.ImageID = iID;
				oPoint = pNode.Rect.Location;
				return true;
			}

			oPoint = new Point(-1, -1);
			return false;
		}

		/*public void PrintNodes()
		{
			using (Graphics g = Graphics.FromImage(m_oBitmap))
			{
				g.CompositingMode = CompositingMode.SourceCopy;
				PrintNode(m_oRoot, g);
			}
		}

		void PrintNode(Node oNode, Graphics g)
		{
			g.DrawRectangle(new Pen(Color.Green), oNode.Rect);
			if (null != oNode.Child)
			{
				PrintNode(oNode.Child[0], g);
				PrintNode(oNode.Child[1], g);
			}
		}*/

		public override Rectangle GetRectangleById(int iID)
		{
			Node oNode = m_oRoot.GetById(iID);
			if (null != oNode)
				return oNode.Rect;
			return Rectangle.Empty;
		}
	}

	public class RectPackerCells : RectPacker
	{
		struct CellPos
		{
			public int X;
			public int Y;
		}

		int[] m_iCellsWidth;
		int[] m_iCellsHeight;
		int[,] m_iCellsID;

		int m_iCellCols;
		int m_iCellRows;
		Bitmap m_oBitmap;
		int m_iPadding;
		Dictionary<int, Rectangle> m_oIds = new Dictionary<int, Rectangle>();

		public RectPackerCells()
		{
		}

		public override void SetupImplementation(int iWidth, int iHeight)
		{
			ResizeCells(1, 1, false);
			m_iCellsID[0, 0] = 0;
			m_iCellsWidth[0] = iWidth;
			m_iCellsHeight[0] = iHeight;
			m_oIds.Clear();
		}

		public override bool Insert(int iWidth, int iHeight, int iID, out Point oPoint)
		{
			CellPos oCellPos;
			oCellPos.X = 0;
			oCellPos.Y = 0;
			oPoint = new Point(-1, -1);
			if (SearchBestCell(iWidth, iHeight, out oCellPos))
			{
				InsertAtPos(oCellPos, iWidth, iHeight, iID);
				int iX, iY;
				CellPosToPixelPos(oCellPos, out iX, out iY);
				oPoint = new Point(iX, iY);
				m_oIds[iID] = new Rectangle(oPoint.X, oPoint.Y, iWidth, iHeight);
				return true;
			}
			return false;
		}

		public override Rectangle GetRectangleById(int iID)
	{
			if (m_oIds.ContainsKey(iID))
			{
				return m_oIds[iID];
			}
			return new Rectangle();
		}

		void ResizeCells(int iColumns, int iRows, bool bCopy = true)
		{
			if (m_iCellsID == null || m_iCellsID.GetLength(0) < iColumns || m_iCellsID.GetLength(1) < iRows)
			{
				int[] iPreviousCellsWidth = m_iCellsWidth;
				int[] iPreviousCellsHeight = m_iCellsHeight;
				int[,] iPreviousCellsID = m_iCellsID;
				int m_iPreviousWidth = m_iCellCols;
				int m_iPreviousHeight = m_iCellRows;

				UInt32 iColumnsPow2 = Math.Max(32, ClosestNextPowerOf2((UInt32)iColumns));
				UInt32 iRowsPow2 = Math.Max(32, ClosestNextPowerOf2((UInt32)iRows));
				m_iCellsID = new int[iColumnsPow2, iRowsPow2];
				m_iCellsWidth = new int[iColumnsPow2];
				m_iCellsHeight = new int[iRowsPow2];
				if (iPreviousCellsID != null && bCopy)
				{
					for (int iX = 0; iX < m_iPreviousWidth; ++iX)
					{
						for (int iY = 0; iY < m_iPreviousHeight; ++iY)
						{
							m_iCellsID[iX, iY] = iPreviousCellsID[iX, iY];
						}
					}

					for (int iX = 0; iX < m_iPreviousWidth; ++iX)
					{
						m_iCellsWidth[iX] = iPreviousCellsWidth[iX];
					}

					for (int iY = 0; iY < m_iPreviousHeight; ++iY)
					{
						m_iCellsHeight[iY] = iPreviousCellsHeight[iY];
					}
				}
			}
			m_iCellCols = iColumns;
			m_iCellRows = iRows;
		}

		UInt32 ClosestNextPowerOf2(UInt32 iValue)
		{
			iValue--;
			iValue |= iValue >> 1;
			iValue |= iValue >> 2;
			iValue |= iValue >> 4;
			iValue |= iValue >> 8;
			iValue |= iValue >> 16;
			iValue++;
			return iValue;
		}

		bool SearchBestCell(int iWidth, int iHeight, out CellPos oCellPos)
		{
			int iBestCellDiff = int.MaxValue;
			int iBestCellX = -1;
			int iBestCellY = -1;
			int iBestCellFound = 0;

			for (int iX = 0; iX < m_iCellCols; ++iX)
			{
				for (int iY = 0; iY < m_iCellRows; ++iY)
				{
					if (m_iCellsID[iX, iY] == 0)
					{
						int iWidthNeeded = iWidth;
						int iHeightNeeded = iHeight;

						//Check free area on X
						int iNextX = iX;
						bool bFree = true;
						while (iWidthNeeded > 0)
						{
							if (iNextX >= m_iCellCols)
							{
								bFree = false;
								break;
							}
							int iCellWidth = m_iCellsWidth[iNextX];
							if (iCellWidth >= iWidthNeeded)
							{
								break;
							}

							iWidthNeeded -= iCellWidth;
							++iNextX;
						}

						if (bFree == false)
							continue;

						//Check free area on Y
						int iNextY = iY;
						while (iHeightNeeded > 0)
						{
							if (iNextY >= m_iCellRows)
							{
								bFree = false;
								break;
							}
							int iCellHeight = m_iCellsHeight[iNextY];
							if (iCellHeight >= iHeightNeeded)
							{
								break;
							}

							iHeightNeeded -= iCellHeight;
							++iNextY;
						}

						if (bFree == false)
							continue;

						//Check free on all area
						for (int iTX = iX; iTX <= iNextX; ++iTX)
						{
							for (int iTY = iY; iTY <= iNextY; ++iTY)
							{
								if (m_iCellsID[iTX, iTY] != 0)
								{
									bFree = false;
									break;
								}
							}

							if (bFree == false)
							{
								break;
							}
						}
						if (bFree)
						{
							CellPos oTempCellPos;
							oTempCellPos.X = iX;
							oTempCellPos.Y = iY;
							int iPixelX, iPixelY;
							CellPosToPixelPos(oTempCellPos, out iPixelX, out iPixelY);
							int iDiff = iPixelX*2 + iPixelY;
							if (iBestCellDiff > iDiff)
							{
								iBestCellDiff = iDiff;
								iBestCellX = iX;
								iBestCellY = iY;
							}

							if (++iBestCellFound >= 16)
							{
								break;
							}

							//oCellPos.X = iX;
							//oCellPos.Y = iY;
							//return true;
						}
					}
				}
				if (iBestCellFound >= 16)
				{
					break;
				}
			}



			if (iBestCellX != -1 && iBestCellY != -1)
			{
				oCellPos.X = iBestCellX;
				oCellPos.Y = iBestCellY;
				return true;
			}

			oCellPos.X = -1;
			oCellPos.Y = -1;
			return false;
		}

		void InsertAtPos(CellPos oPos, int iWidth, int iHeight, int iID)
		{
			int iWidthNeeded = iWidth;
			int iHeightNeeded = iHeight;

			int iNextX = oPos.X;
			int iTotalWidth = 0;
			while (iWidthNeeded > 0)
			{
				int iCellWidth = m_iCellsWidth[iNextX];
				iTotalWidth += iCellWidth;
				if (iCellWidth >= iWidthNeeded)
				{
					break;
				}

				iWidthNeeded -= iCellWidth;
				++iNextX;
			}

			int iNextY = oPos.Y;
			int iTotalHeight = 0;
			while (iHeightNeeded > 0)
			{
				int iCellHeight = m_iCellsHeight[iNextY];
				iTotalHeight += iCellHeight;
				if (iCellHeight >= iHeightNeeded)
				{
					break;
				}

				iHeightNeeded -= iCellHeight;
				++iNextY;
			}


			if (iTotalHeight > iHeight)
			{
				SplitRow(iNextY, iTotalHeight - iHeight);
			}
			if (iTotalWidth > iWidth)
			{
				SplitColumn(iNextX, iTotalWidth - iWidth);
			}

			for (int iTX = oPos.X; iTX <= iNextX; ++iTX)
			{
				for (int iTY = oPos.Y; iTY <= iNextY; ++iTY)
				{
					m_iCellsID[iTX, iTY] = iID;
				}
			}
		}

		void SplitColumn(int iColToSplit, int iRightSize)
		{
			if (iColToSplit < 0 || iColToSplit >= m_iCellCols)
				throw new Exception("Invalid column to split");

			int iLeftSize = m_iCellsWidth[iColToSplit] - iRightSize;
			if (m_iCellsWidth[iColToSplit] <= iRightSize)
				throw new Exception("Invalid right size");

			ResizeCells(m_iCellCols + 1, m_iCellRows);

			//Move data to right for columns after iColToSplit (and copy for splitted column)
			for (int iCol = m_iCellCols - 1; iCol > iColToSplit; --iCol)
			{
				m_iCellsWidth[iCol] = m_iCellsWidth[iCol - 1];
				for (int iRow = 0; iRow < m_iCellRows; ++iRow)
				{
					m_iCellsID[iCol, iRow] = m_iCellsID[iCol - 1, iRow];
				}
			}

			//Split column size
			m_iCellsWidth[iColToSplit] = iLeftSize;
			m_iCellsWidth[iColToSplit + 1] = iRightSize;
		}

		void SplitRow(int iRowToSplit, int iBottomSize)
		{
			if (iRowToSplit < 0 || iRowToSplit >= m_iCellRows)
				throw new Exception("Invalid column to split");

			int iTopSize = m_iCellsHeight[iRowToSplit] - iBottomSize;
			if (m_iCellsHeight[iRowToSplit] <= iBottomSize)
				throw new Exception("Invalid bottom size");

			ResizeCells(m_iCellCols, m_iCellRows + 1);

			//Move data to bottom for rows after iRowToSplit (and copy for splitted row)
			for (int iRow = m_iCellRows - 1; iRow > iRowToSplit; --iRow)
			{
				m_iCellsHeight[iRow] = m_iCellsHeight[iRow - 1];
			}


			for (int iCol = 0; iCol < m_iCellCols; ++iCol)
			{
				for (int iRow = m_iCellRows - 1; iRow > iRowToSplit; --iRow)
				{
					m_iCellsID[iCol, iRow] = m_iCellsID[iCol, iRow - 1];
				}
			}

			//Split row size
			m_iCellsHeight[iRowToSplit] = iTopSize;
			m_iCellsHeight[iRowToSplit + 1] = iBottomSize;
		}

		void CellPosToPixelPos(CellPos oPos, out int iOutX, out int iOutY)
		{
			int iPixelX = 0;
			int iPixelY = 0;

			for (int iX = 0; iX < oPos.X; ++iX)
			{
				iPixelX += m_iCellsWidth[iX];
			}
			for (int iY = 0; iY < oPos.Y; ++iY)
			{
				iPixelY += m_iCellsHeight[iY];
			}

			iOutX = iPixelX;
			iOutY = iPixelY;
		}

		public bool SaveDebugToFile(string sPath)
		{
			int iScale = 1;
			int iWidth = 0;
			for (int iX = 0; iX < m_iCellCols; ++iX)
				iWidth += m_iCellsWidth[iX];

			int iHeight = 0;
			for (int iY = 0; iY < m_iCellRows; ++iY)
				iHeight += m_iCellsHeight[iY];

			Bitmap oBitmap = new Bitmap(iWidth * iScale, iHeight * iScale);
			using (Graphics g = Graphics.FromImage(oBitmap))
			{
				g.SmoothingMode = SmoothingMode.AntiAlias;
				g.InterpolationMode = InterpolationMode.HighQualityBicubic;
				g.PixelOffsetMode = PixelOffsetMode.HighQuality;
				StringFormat oFormat = new StringFormat()
				{
					Alignment = StringAlignment.Center,
					LineAlignment = StringAlignment.Center
				};

				int iCurrentY = 0;
				for (int iY = 0; iY < m_iCellRows; ++iY)
				{
					int iCurrentX = 0;
					for (int iX = 0; iX < m_iCellCols; ++iX)
					{
						Rectangle oRect = new Rectangle(iCurrentX * iScale, iCurrentY * iScale, m_iCellsWidth[iX] * iScale, m_iCellsHeight[iY] * iScale);
						if (m_iCellsID[iX, iY] != 0)
						{
							Random rnd = new Random(m_iCellsID[iX, iY]);
							Color oColor = Color.FromArgb(rnd.Next(255), rnd.Next(255), rnd.Next(255));
							g.FillRectangle(new SolidBrush(oColor), oRect);
						}
						else
						{
							g.FillRectangle(new SolidBrush(Color.White), oRect);
						}
						g.DrawRectangle(new Pen(Color.Green), oRect);

						g.DrawString(string.Format("{0}\n{1}x{2}", m_iCellsID[iX, iY], m_iCellsWidth[iX], m_iCellsHeight[iY]), new System.Drawing.Font("Tahoma", 10), Brushes.Black, oRect, oFormat);

						iCurrentX += m_iCellsWidth[iX];
					}
					iCurrentY += m_iCellsHeight[iY];
				}
			}
			oBitmap.Save(sPath);
			return false;
		}
	}
}