Skip to content

Instantly share code, notes, and snippets.

@thennequin

thennequin/RectPacker.cs

Last active July 11, 2018 15:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save thennequin/849505be168983f76a818bdc68a33e39 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save thennequin/849505be168983f76a818bdc68a33e39 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. thennequin renamed this gist Jul 11, 2018. 1 changed file with 433 additions and 168 deletions.
    601 changes: 433 additions & 168 deletions RectPackerV2.cs → RectPacker.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,13 +1,376 @@
    using System;
    using System.Collections.Generic;
    using System.Drawing;
    using System.Drawing.Drawing2D;
    using System.Threading.Tasks;
    using FastBitmap;
    using System;
    using System.Collections.Generic;

    namespace RectPacker
    namespace SkinsetGenerator
    {
    public class RectPackerV2
    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
    {
    @@ -25,14 +388,44 @@ struct CellPos
    int m_iPadding;
    Dictionary<int, Rectangle> m_oIds = new Dictionary<int, Rectangle>();

    public Bitmap GetBitmap()
    public RectPackerCells()
    {
    return m_oBitmap;
    }

    public RectPackerV2()
    public override void SetupImplementation(int iWidth, int iHeight)
    {
    Reset(1, 1, 0);
    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)
    @@ -75,23 +468,6 @@ void ResizeCells(int iColumns, int iRows, bool bCopy = true)
    m_iCellRows = iRows;
    }

    public void Reset(int iWidth, int iHeight, int iPadding)
    {
    ResizeCells(1, 1, false);
    m_iCellsID[0, 0] = 0;
    m_iCellsWidth[0] = iWidth;
    m_iCellsHeight[0] = iHeight;
    m_iPadding = iPadding;
    m_oIds.Clear();
    m_oBitmap = new Bitmap(iWidth, iHeight);
    m_oBitmap.MakeTransparent();

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

    UInt32 ClosestNextPowerOf2(UInt32 iValue)
    {
    iValue--;
    @@ -109,7 +485,8 @@ 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)
    @@ -183,19 +560,38 @@ bool SearchBestCell(int iWidth, int iHeight, out CellPos oCellPos)
    }
    if (bFree)
    {
    iBestCellDiff = iWidthNeeded;
    iBestCellX = iX;
    iBestCellY = iY;
    //break;

    oCellPos.X = iX;
    oCellPos.Y = iY;
    return true;
    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;
    @@ -243,7 +639,7 @@ void InsertAtPos(CellPos oPos, int iWidth, int iHeight, int iID)
    ++iNextY;
    }


    if (iTotalHeight > iHeight)
    {
    SplitRow(iNextY, iTotalHeight - iHeight);
    @@ -305,7 +701,7 @@ void SplitRow(int iRowToSplit, int iBottomSize)
    m_iCellsHeight[iRow] = m_iCellsHeight[iRow - 1];
    }


    for (int iCol = 0; iCol < m_iCellCols; ++iCol)
    {
    for (int iRow = m_iCellRows - 1; iRow > iRowToSplit; --iRow)
    @@ -337,137 +733,6 @@ void CellPosToPixelPos(CellPos oPos, out int iOutX, out int iOutY)
    iOutY = iPixelY;
    }

    public 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 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;
    }

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

    public bool SaveDebugToFile(string sPath)
    {
    int iScale = 1;
  2. thennequin revised this gist Jul 10, 2018. 1 changed file with 30 additions and 39 deletions.
    69 changes: 30 additions & 39 deletions RectPackerV2.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -7,7 +7,7 @@

    namespace RectPacker
    {
    public class RectPackerV2
    public class RectPackerV2
    {
    struct CellPos
    {
    @@ -45,47 +45,30 @@ void ResizeCells(int iColumns, int iRows, bool bCopy = true)
    int m_iPreviousWidth = m_iCellCols;
    int m_iPreviousHeight = m_iCellRows;

    UInt32 iColumnsPow2 = Math.Max(16, ClosestNextPowerOf2((UInt32)iColumns));
    UInt32 iRowsPow2 = Math.Max(16, ClosestNextPowerOf2((UInt32)iRows));
    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)
    {
    Parallel.For(0, m_iPreviousHeight, iY =>
    for (int iX = 0; iX < m_iPreviousWidth; ++iX)
    {
    for (int iX = 0; iX < m_iPreviousWidth; ++iX)
    {
    m_iCellsID[iX, iY] = iPreviousCellsID[iX, iY];
    };
    });

    /*for (int iY = 0; iY < m_iPreviousHeight; ++iY)
    {
    for (int iX = 0; iX < m_iPreviousWidth; ++iX)
    for (int iY = 0; iY < m_iPreviousHeight; ++iY)
    {
    m_iCellsID[iX, iY] = iPreviousCellsID[iX, iY];
    }
    }*/

    Parallel.For(0, m_iPreviousWidth, iX =>
    {
    m_iCellsWidth[iX] = iPreviousCellsWidth[iX];
    });
    Parallel.For(0, m_iPreviousHeight, iY =>
    {
    m_iCellsHeight[iY] = iPreviousCellsHeight[iY];
    });
    }

    /*for (int iX = 0; iX < m_iPreviousWidth; ++iX)
    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;
    @@ -94,9 +77,8 @@ void ResizeCells(int iColumns, int iRows, bool bCopy = true)

    public void Reset(int iWidth, int iHeight, int iPadding)
    {
    //ResizeCells(Math.Max(1, iWidth / 8), Math.Max(1, iHeight / 8), false);
    ResizeCells(1, 1, false);
    m_iCellsID[0, 0]= 0;
    m_iCellsID[0, 0] = 0;
    m_iCellsWidth[0] = iWidth;
    m_iCellsHeight[0] = iHeight;
    m_iPadding = iPadding;
    @@ -127,9 +109,10 @@ bool SearchBestCell(int iWidth, int iHeight, out CellPos oCellPos)
    int iBestCellDiff = int.MaxValue;
    int iBestCellX = -1;
    int iBestCellY = -1;
    for (int iY = 0; iY < m_iCellRows; ++iY)

    for (int iX = 0; iX < m_iCellCols; ++iX)
    {
    for (int iX = 0; iX < m_iCellCols; ++iX)
    for (int iY = 0; iY < m_iCellRows; ++iY)
    {
    if (m_iCellsID[iX, iY] == 0)
    {
    @@ -146,12 +129,13 @@ bool SearchBestCell(int iWidth, int iHeight, out CellPos oCellPos)
    bFree = false;
    break;
    }
    if (m_iCellsWidth[iNextX] >= iWidthNeeded)
    int iCellWidth = m_iCellsWidth[iNextX];
    if (iCellWidth >= iWidthNeeded)
    {
    break;
    }

    iWidthNeeded -= m_iCellsWidth[iNextX];
    iWidthNeeded -= iCellWidth;
    ++iNextX;
    }

    @@ -167,12 +151,13 @@ bool SearchBestCell(int iWidth, int iHeight, out CellPos oCellPos)
    bFree = false;
    break;
    }
    if (m_iCellsHeight[iNextY] >= iHeightNeeded)
    int iCellHeight = m_iCellsHeight[iNextY];
    if (iCellHeight >= iHeightNeeded)
    {
    break;
    }

    iHeightNeeded -= m_iCellsHeight[iNextY];
    iHeightNeeded -= iCellHeight;
    ++iNextY;
    }

    @@ -258,14 +243,15 @@ void InsertAtPos(CellPos oPos, int iWidth, int iHeight, int iID)
    ++iNextY;
    }

    if (iTotalWidth > iWidth)
    {
    SplitColumn(iNextX, iTotalWidth - iWidth);
    }

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

    for (int iTX = oPos.X; iTX <= iNextX; ++iTX)
    {
    @@ -317,7 +303,12 @@ void SplitRow(int iRowToSplit, int iBottomSize)
    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 iCol = 0; iCol < m_iCellCols; ++iCol)
    {
    for (int iRow = m_iCellRows - 1; iRow > iRowToSplit; --iRow)
    {
    m_iCellsID[iCol, iRow] = m_iCellsID[iCol, iRow - 1];
    }
    @@ -530,4 +521,4 @@ public bool SaveDebugToFile(string sPath)
    return false;
    }
    }
    }
    }
  3. thennequin revised this gist Jul 10, 2018. No changes.
  4. thennequin created this gist Jul 10, 2018.
    533 changes: 533 additions & 0 deletions RectPackerV2.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,533 @@
    using System;
    using System.Collections.Generic;
    using System.Drawing;
    using System.Drawing.Drawing2D;
    using System.Threading.Tasks;
    using FastBitmap;

    namespace RectPacker
    {
    public class RectPackerV2
    {
    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 Bitmap GetBitmap()
    {
    return m_oBitmap;
    }

    public RectPackerV2()
    {
    Reset(1, 1, 0);
    }

    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(16, ClosestNextPowerOf2((UInt32)iColumns));
    UInt32 iRowsPow2 = Math.Max(16, ClosestNextPowerOf2((UInt32)iRows));
    m_iCellsID = new int[iColumnsPow2, iRowsPow2];
    m_iCellsWidth = new int[iColumnsPow2];
    m_iCellsHeight = new int[iRowsPow2];
    if (iPreviousCellsID != null && bCopy)
    {
    Parallel.For(0, m_iPreviousHeight, iY =>
    {
    for (int iX = 0; iX < m_iPreviousWidth; ++iX)
    {
    m_iCellsID[iX, iY] = iPreviousCellsID[iX, iY];
    };
    });

    /*for (int iY = 0; iY < m_iPreviousHeight; ++iY)
    {
    for (int iX = 0; iX < m_iPreviousWidth; ++iX)
    {
    m_iCellsID[iX, iY] = iPreviousCellsID[iX, iY];
    }
    }*/

    Parallel.For(0, m_iPreviousWidth, iX =>
    {
    m_iCellsWidth[iX] = iPreviousCellsWidth[iX];
    });
    Parallel.For(0, m_iPreviousHeight, iY =>
    {
    m_iCellsHeight[iY] = iPreviousCellsHeight[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;
    }

    public void Reset(int iWidth, int iHeight, int iPadding)
    {
    //ResizeCells(Math.Max(1, iWidth / 8), Math.Max(1, iHeight / 8), false);
    ResizeCells(1, 1, false);
    m_iCellsID[0, 0]= 0;
    m_iCellsWidth[0] = iWidth;
    m_iCellsHeight[0] = iHeight;
    m_iPadding = iPadding;
    m_oIds.Clear();
    m_oBitmap = new Bitmap(iWidth, iHeight);
    m_oBitmap.MakeTransparent();

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

    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;
    for (int iY = 0; iY < m_iCellRows; ++iY)
    {
    for (int iX = 0; iX < m_iCellCols; ++iX)
    {
    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;
    }
    if (m_iCellsWidth[iNextX] >= iWidthNeeded)
    {
    break;
    }

    iWidthNeeded -= m_iCellsWidth[iNextX];
    ++iNextX;
    }

    if (bFree == false)
    continue;

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

    iHeightNeeded -= m_iCellsHeight[iNextY];
    ++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)
    {
    iBestCellDiff = iWidthNeeded;
    iBestCellX = iX;
    iBestCellY = iY;
    //break;

    oCellPos.X = iX;
    oCellPos.Y = iY;
    return true;
    }
    }
    }
    }

    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 (iTotalWidth > iWidth)
    {
    SplitColumn(iNextX, iTotalWidth - iWidth);
    }
    if (iTotalHeight > iHeight)
    {
    SplitRow(iNextY, iTotalHeight - iHeight);
    }

    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)
    {
    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 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 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;
    }

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

    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;
    }
    }
    }