LenWinSonSoft
asked on
Best arrangement of many textures into a single texture
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...
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...
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
@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...
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...
ASKER
@thegilb:
this seems to be perfect... I will try to convert this to C#...
this seems to be perfect... I will try to convert this to C#...
ASKER
@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...
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...
ASKER
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.Chil ds[0]) + GetUnusedSpace(InNode.Chil ds[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 );
}
}
}
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
}
else
{
FillImage(InNode.Childs[0]
FillImage(InNode.Childs[1]
}
}
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.Chil
}
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
}
}
}
ASKER
oh sorry for german comments... but you will find the english version in the link that "MikeGeig" posted...
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