Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Drazgal

Optimal Packing

This topic is 5289 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ive been trying to come up with some code to automatically add bitmaps together so I dont need to switch textures with models etc. Ive come up with an algorithm that works (assuming the textures are all power of 2 and are added in order of size) and makes a bitmap that is power of 2 along both dimensions and that is made up of the smaller bitmaps (then the program edits and changes the models u,v''s etc). I was wondering if anyone knew of any algorithm names (or even the technique name for me to google) to do this so that I can look up to see what ways I can improve on my base implementation.

Share this post


Link to post
Share on other sites
Advertisement
The term "texture atlas" is generally given to the larger texture that combines several smaller ones to avoid texture state changes. That should get you some useful hits in google. I found a couple:

Least Squares Conformal Maps for Automatic Texture Atlas Generation - this one shows up a lot in google searches

Then, there''s the multi-chart geometry images stuff - probably less useful:

Multi-Chart Geometric Images



Graham Rhodes
Principal Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
I think grhodes mis-understood the problem.

It sounds like the problem Drazgal is solving is the "bin packing problem" or "knapsack problem" for the special case of power-of-two textures in a 2D bin. Some IC layout tools also solve similar problems, calling it "floor planning".

The name for a large texture that contains lots of small textures is typically a "texture sheet" and the process of generating them is "sheeting". However, you give up important abilities WRT filtering/MIP mapping and texture coordinate tiling if you do this. Make sure you know that texture switching really is a problem for you before you do this. On most modern and semi-modern cards, it won''t be worth it.

Last, a "texture atlas" is typically a parameterization of a mesh, i e a way of coming up with a U,V mapping for a mesh, and splat that U,V mapping onto (typically) a single texture, such that texel stretching and texture waste is minimized.

Share this post


Link to post
Share on other sites
thanks for the replies. Im only planning on using this for character models where tiling of the textures isn''t all that useful I might place it in the rest of the engine as a user selectable when building buildings, terrains etc and if tiling isn''t used, but its best to be a compile thing!

Anyway the system I have does work I just wanted to know the real terms (incase I use this for my next years uni project I''ll need ot be able to do the documentation properly). That and to see if there are any glaring errors that I''ve made.

Thanks alot to both of you!!

Share this post


Link to post
Share on other sites
I''ve been working with that for a time now, so here are a few tips, once you already have the algorithm: (btw, i handle tiling by automatically adding vertices and triangles)
*pad the textures with a few additional pixels, so the mipmaps will look good.
*Make sure the textures are mulitples of 4 so you xon''t get dxtc/s3tc "leaks"
*Take a look at centroid sampling.
*Since you will have to pad the textures, the original textures must be just below pow2 size, so once they are padded, they''ll be pow2 sized. Just above pow2 size is a pathlogical case.

I hope this helps. By the way, does your algorithm use trackback, does it try non square textures?

Share this post


Link to post
Share on other sites
I''ve done this to cache bitmaps for my GUI as well as font characters onto a larger texture. Most algorithms I''ve seen weren''t intended to be performant, but to receive the most optimal result, plus, they expected all objects to be packed known in advance.

This is what I came up with in the end. A single lower-left line packer without the ability to free once used rectangles.
  struct RectanglePacker {
/// Constructor

RectanglePacker(const Point2<size_t> &Size) :
m_Size(Size),
m_lCurrentLine(0),
m_lMaxHeight(0),
m_lXPosition(0) {}

/// Allocate space for a rectangle

Point2<long> placeRectangle(const Point2<size_t> &Size) {
// If it''s too wide for the entire packing area, just stop

if((Size.X > m_Size.X) || (Size.Y > m_Size.Y))
throw UnexpectedException("Nuclex::Video::VertexDrawer::RectanglePacker::placeRectangle()",
"Rectangle too large to fit in packing area");

// Do we have to start a new line ?

if((m_lXPosition + Size.X) > m_Size.X) {
m_lCurrentLine += m_lMaxHeight;
m_lMaxHeight = 0;
m_lXPosition = 0;
}

// If it doesn''t fit vertically now, the packing area is full

if((m_lCurrentLine + Size.Y) > m_Size.Y)
return Point2<long>(-1, -1);

// Generate the placement position and advance to the right

Point2<long> Position(m_lXPosition, m_lCurrentLine);
m_lXPosition += Size.X;
if(Size.Y > m_lMaxHeight)
m_lMaxHeight = Size.Y;

return Position;
}

private:
Point2<size_t> m_Size; ///< Total packing area size

long m_lCurrentLine; ///< Current packing line

size_t m_lMaxHeight; ///< Largest rectangle in current line

long m_lXPosition; ///< Offset within current line

};


Maybe take a look in flipcode''s code of the day section, there''s a contribution named "rectangle packing" which lead to an interesting discussion.

-Markus-

Share this post


Link to post
Share on other sites
I did understand the problem. We have the same issue here. It seems there is some inconsistency in terminology in the literature. Please refer to the presentation titled "Optimization for DirectX9 Graphics" by Ashu Rege of nVIDIA, where he uses the term "Texture Atlas" in the way I described it. I do see some references---older than the nVIDIA one---that use Texture Atlas to mean an optimum pattern mapping that minimizes stretch. I think this is the source of inconsistency.

nVIDIA GDC 2004 Presentations


Graham Rhodes
Principal Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
both are texture atlases, actually, except that in the acse we are talking about, the charts are rectangular and nothing is being done to pervent uv strecth (we asssume that the guy who did the graphics did it right)

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!