Solved

Best arrangement of many textures into a single texture

Posted on 2007-03-19
7
352 Views
Last Modified: 2012-06-27
Hello,

I have a little or big problem...
For a graphic engine there are many textures or images given by a rectangle with two values, width and height (in pixel).

Now I have to calculate the best arrangement for all given textures on one plane... I want to arrange all those textures on a single texture, in other words... "best" is defined by the space requirement. I need one arrangement with a minimum amount of space (width, height)... So all textures have to be placed on a single texture with a minimum amount of "unused" spaces between them...

This operation is something like calculating the best arragement of figures on expensive silver paper...
The only diffenrence is, that my textures are rectangles and unrotateable...

I thought of using A*, but I have NO idea how to implement this for my specific problem...

Thanks for advance...
0
Comment
Question by:LenWinSonSoft
  • 5
7 Comments
 
LVL 5

Accepted Solution

by:
thegilb earned 500 total points
ID: 18750032
A* is a path finding algorithm and in this particular situation would be more or less useless. The algorithm you are likely to have the most success with is the best fit (BF) algorithm.

The most common reason for using such an algorithm is with lightmap packing. When lightmaps are generated for a level they are packed into a texture using the best fit algorithm. Adapting this algorithm for your needs should be ludicrously simple.

See an overview of the algorithm with sample code here:
http://www.blackpawn.com/texts/lightmaps/default.html

Hope that helps!
0
 
LVL 4

Expert Comment

by:MikeGeig
ID: 18750041
Len,

I am not entirely sure what you are asking. Are you looking for the math that would find an arrangement of squares? Or are you looking for the algorithm that will pull the squares out of a sheet that you have made? Could you be more specific about what you need?

Thanks

Mike
0
 

Author Comment

by:LenWinSonSoft
ID: 18754891
@Mike:

I need the algorithm that calculates the position of the squares... Putting them into one texture is not the problem... Only where I have to put them...
0
Optimizing Cloud Backup for Low Bandwidth

With cloud storage prices going down a growing number of SMBs start to use it for backup storage. Unfortunately, business data volume rarely fits the average Internet speed. This article provides an overview of main Internet speed challenges and reveals backup best practices.

 

Author Comment

by:LenWinSonSoft
ID: 18754923
@thegilb:

this seems to be perfect... I will try to convert this to C#...
0
 

Author Comment

by:LenWinSonSoft
ID: 18755153
@thegilb:

really wonderful... exactly what I want... The generated Atlas looks pretty nice... And even with very strange textures there are nearly no free spaces... I cannt believe it ^^

Many thanks for advance...
0
 

Author Comment

by:LenWinSonSoft
ID: 18755161
My c# implementation looks like this:

class CNode
    {
        CNode[] Childs = new CNode[2];
        Int32 Left, Top, Width, Height;
        CPackageTexture Texture;

        public CNode(Int32 InLeft, Int32 InTop, Int32 InWidth, Int32 InHeight)
        {
            Left = InLeft;
            Top = InTop;
            Width = InWidth;
            Height = InHeight;
        }

        static private void GetSize(ref Int32 InMaxWidth, ref Int32 InMaxHeight, CNode InNode)
        {
            if(InNode == null)
                return;

            if (InNode.Texture != null)
            {
                InNode.Width = InNode.Left + InNode.Width;
                InNode.Height = InNode.Top + InNode.Height;

                if (InNode.Width > InMaxWidth)
                    InMaxWidth = InNode.Width;

                if (InNode.Height > InMaxHeight)
                    InMaxHeight = InNode.Height;
            }
            else
            {
                GetSize(ref InMaxWidth, ref InMaxHeight, InNode.Childs[0]);
                GetSize(ref InMaxWidth, ref InMaxHeight, InNode.Childs[1]);
            }
        }

        public void GetSize(out Int32 OutWidth, out Int32 OutHeight)
        {
            OutWidth = 0;
            OutHeight = 0;

            GetSize(ref OutWidth, ref OutHeight, this);
        }

        static private void FillImage(CNode InNode, Graphics g)
        {
            if (InNode == null)
                return;

            if (InNode.Texture != null)
            {
                g.DrawImage(InNode.Texture.Bmp, InNode.Left, InNode.Top);
            }
            else
            {
                FillImage(InNode.Childs[0], g);
                FillImage(InNode.Childs[1], g);
            }
        }

        public void FillImage(Image InImage)
        {
            Graphics g = Graphics.FromImage(InImage);

            FillImage(this, g);
        }

        static private Int32 GetUnusedSpace(CNode InNode)
        {
            if(InNode == null)
                return 0;

            if((InNode.Childs[0] == null) && (InNode.Childs[1] == null) && (InNode.Texture == null))
            {
                return InNode.Width * InNode.Height;
            }

            return GetUnusedSpace(InNode.Childs[0]) + GetUnusedSpace(InNode.Childs[1]);
        }

        public Int32 GetUnusedSpace()
        {
            return GetUnusedSpace(this);
        }

        public CNode Insert(CPackageTexture InTexture)
        {
            if ((Childs[0] != null) || (Childs[1] != null))
            {
                // Versuchen in erstes Child einzusetzten
                CNode NewNode = Childs[0].Insert(InTexture);

                if (NewNode != null)
                    return NewNode;

                // Versuchen in zweites Child einzusetzten
                return Childs[1].Insert(InTexture);
            }
            else
            {
                // Prüfen ob hier bereits ein Bild vorhanden ist
                if (Texture != null)
                    return null;

                // Prüfen ob Textur zu groß ist
                if ((Width < InTexture.Width) || (Height < InTexture.Height))
                    return null;

                // Prüfen ob textur genau hinein passt
                if ((Width == InTexture.Width) && (Height == InTexture.Height))
                {
                    Texture = InTexture;

                    return this;
                }

                // beste Aufteilung ermitteln
                Int32 DiffWidth = Width - InTexture.Width;
                Int32 DiffHeight = Height - InTexture.Height;

                if (DiffWidth > DiffHeight)
                {
                    // Vertikal splitten
                    Childs[0] = new CNode(Left, Top, InTexture.Width, Height);
                    Childs[1] = new CNode(Left + InTexture.Width, Top, DiffWidth, Height);
                }
                else
                {
                    // Horizontal splitten
                    Childs[0] = new CNode(Left, Top, Width, InTexture.Height);
                    Childs[1] = new CNode(Left, Top + InTexture.Height, Width, DiffHeight);
                }

                // In das erste, neu erstellte, Child einfügen
                return Childs[0].Insert(InTexture);
            }
        }
    }
0
 

Author Comment

by:LenWinSonSoft
ID: 18755166
oh sorry for german comments... but you will find the english version in the link that "MikeGeig" posted...
0

Featured Post

ScreenConnect 6.0 Free Trial

Want empowering updates? You're in the right place! Discover new features in ScreenConnect 6.0, based on partner feedback, to keep you business operating smoothly and optimally (the way it should be). Explore all of the extras and enhancements for yourself!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
groupSum5 challenge 5 85
WPF - Tooltips for ComboBox items 5 75
What language/protocol is the Angular Chat? 2 77
Advice in Xamarin 21 80
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
Having just graduated from college and entered the workforce, I don’t find myself always using the tools and programs I grew accustomed to over the past four years. However, there is one program I continually find myself reverting back to…R.   So …
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

831 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question