Effective way to compute texture size for bin packer

07b9e9e8483468e4a0e1bac1843e6e74
0
Snoob 105 Jun 06, 2012 at 20:41

I’ve implemented a rectangle based bin packer to create a texture atlas for font glyphs. This packer works well but requires the width and height of the target area.

Actually I try to approximate the minimal pow2 texture by iterating over my set of target glyps and check if their right and bottom margins fits to the target texture size. If the size exceeds I double the size and check again. This works but results often in wasted space after bin packing.

But what is a more effective way to compute the target texture size? Actually I’ve thoughts about a “dry bin pack run” to check the glyphs against the target size and extends the size by two if a glyph doesn’t fit and check again… But this will result in multiple bin pack runs. Is this not too expensive?

Best regards,
Snoob

19 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Jun 06, 2012 at 21:41

First, do you need to use a pow2 texture? Many GPUs nowadays no longer have this restriction. (Although it’s possible performance will suffer from using non-pow2 textures). Anyway, it’s worth thinking about.

Second, you could choose a fixed width for the texture, e.g. 256 or 512 and just keep extending the height as you run out of space. That would keep you from having to re-layout the glyphs that have already been done. (I’m assuming you lay out the glyphs basically left-to-right and top-down.)

6837d514b487de395be51432d9cdd078
0
TheNut 179 Jun 07, 2012 at 01:53

For general sprite sheets, I do what Reed states. To be clear here, you don’t pack your images right away. Store their widths and heights as well as their (X,Y) coordinates where they would be stored in the packed image. Once you found your optimal size and packing order, then you can begin the packing operation. You can perform as many runs as you need to find the optimal packing size and solution as this is extremely fast. Any excess space can easily be cropped out.

Normally for bitmap fonts I maintain the same cell size for each glyph, for legibility purposes when viewing the file. This means I can calculate the exact image size before I even start reading in glyph information. You can tightly pack the glyphs if you want, but if you need to do some customizations (bevels, textures, drop shadows, etc.), it can be a bit difficult to manage like this.

07b9e9e8483468e4a0e1bac1843e6e74
0
Snoob 105 Jun 07, 2012 at 06:23

NPOT should be an option, maybe i support both, POT and NPOT texture sizes. Thanks for your advises, I will check it.

07b9e9e8483468e4a0e1bac1843e6e74
0
Snoob 105 Jun 12, 2012 at 20:24

I’ve followed your instruction and could optimize the POT calculation (Sorting my glyphs by descending size). Thanks!

But I’ve some trouble with NPOT textures. Using OpenGL NPOT textures works, but the rendered glyphs are not alligned correctly to the baseline. The glyphs are alligned minimal different (maybe rounding precision failures? But why only on NPOT?). I use GL_CLAMP_TO_EDGE as texture addressing mode and GL_LINEAR as filter option. I’ve created an debug image to check the NPOT texture, everything is fine. Have I to regard something special using NPOT?

http://s14.directupl…2bk8azd_jpg.htm //npot-debug image

http://s1.directuplo…2chxpbi_jpg.htm //npot-rendering result with baseline allignment failures

With DirectX9 NPOT using crashes. Actually have no time to figure out why, but I’ve googled that I’ve to use D3DXCreateTextureFromFileEx if i want to load a NPOT Texture. But I use DevIL to load my texture images, by this reason this function is not an option. Is it possible to use NPOT textures in DirectX9?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Jun 12, 2012 at 21:41

@Snoob

Is it possible to use NPOT textures in DirectX9?

Yes, but in general you have to check whether the hardware supports it; see the TextureCaps member of D3DCAPS9. I don’t know enough about DevIL to tell if it can handle non-pow2 textures, though I don’t see why it wouldn’t.

The texel alignment issue is bizarre, though. TBH, this feels like a misaligned UVs problem. Double-check your code that generates the UVs and quads for drawing the text? Is it possible some math in there is still assuming the texture is pow2, such as when rounding positions to the nearest texel or something like that?

07b9e9e8483468e4a0e1bac1843e6e74
0
Snoob 105 Jun 13, 2012 at 07:23

I have to check at home why my DX9 implementation crashes. DevIL is not the problem, the atlas image containing the glyphs has been allready created and is hold in memory. Maybe I’ve to regard something special when I create the texture from this image … But first see where the crash occurs …

I’ve checked my UV coordinate calculation, and can’t find a POT restriction:

  float invWidth  = 1.0f/(float)this->getTexture()->getWidth();
  float invHeight = 1.0f/(float)this->getTexture()->getHeight();
  this->set(x * invWidth, y * invHeight, (x + width) * invWidth, (y + height) * invHeight);   // this set's the u,v,u2,v2 coordinates as floats
07b9e9e8483468e4a0e1bac1843e6e74
0
Snoob 105 Jun 13, 2012 at 19:31

A played a little bit around with this issue. What I’ve figured out is, that i got acceptable results with NPOT if I got a
dimension which could be devided by two, i.e. 200x200 or 118x118 otherwise I got a chopped mapping result like
this (i.e. 135x135):

[url] http://s7.directupload.net/file/d/2920/hjsz3sw8_jpg.htm [/url]

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Jun 13, 2012 at 19:42

Weird! Another thing to look at might be your mipmaps, if you have any for this texture. Other than that, I can’t think of anything besides a weird driver / hardware bug.

07b9e9e8483468e4a0e1bac1843e6e74
0
Snoob 105 Jun 14, 2012 at 10:52

I’ve checked my mipmaps, there are no mipmaps. And I think driver/harware bugs could be excluded, I’ve tested my sources on two different systems with different hardware. On both systems same failure exists. So I’ve reduced anything to minimum and only render a single Glyph to a small atlas:

Here are some log outputs with details to the used atlas image and responding texture object:

Extension support of GL_ARB_texture_non_power_of_two is: true.

TextureAtlas :
- width : 37
- height : 37
- format : PF_BYTE_LA
- image id : Vera.ttf Font

Image :
- id : Vera.ttf Font
- width : 37
- height : 37
- format : PF_BYTE_LA
- bits per pixel : 16
- bytes per pixel : 2
- number of mipaps : 0

Texture :
- type : TYPE_TEXTURE_2D
- brImage id : Vera.ttf Font
- GL texture id : 1
- GL texture target : GL_TEXTURE_2D
- GL pixel format : GL_LUMINANCE_ALPHA
- GL pixel data type : GL_UNSIGNED_BYTE
- GL internal format : GL_LUMINANCE_ALPHA

  • GL min filter option : GL_LINEAR
  • GL mag filter option : GL_LINEAR
  • GL_TEXTURE_WRAP_S textrue addressing mode : GL_CLAMP_TO_EDGE
  • GL_TEXTURE_WRAP_T textrue addressing mode : GL_CLAMP_TO_EDGE
  • GL_TEXTURE_WRAP_R textrue addressing mode : GL_CLAMP_TO_EDGE

I’ve also tested the GL_REPEAT texture addressing mode. This results in the same mapping
issue…

And here are detailed informations to the font, glph and texture region, which defines the
final glyph mapping values:

Font :
- file : media/vera.ttf
- size : 28
- FreeType point size (w/h) : 28, 28
- FreeType resolution (h/v) : 100, 100

FontGlyph :
- charcode : 64
- name id : @
- width : 34
- height : 34
- offset_x : 3
- offset_y : 27
- advance_x : 39
- advance_y : 0

TextureRegion :
- u : 0
- v : 0
- u2 : 0.918919
- v2 : 0.918919
- x : 0
- y : 0
- width : 35 (rounded from uv values)
- height : 35 (rounded from uv values)

I can’t find a failure. Anything looks ok. Please take note that the width and height of the region are
rounded values back from uv values. By this reason the dimension is 1 greater, but it’s unused for
mapping, on mapping I access the glyph dimension values:

for(unsigned int c=0; c<text.length(); ++c )
{
         FontGlyph glyph = font.getGlyph(text[c]);
         TextureRegion region = atlas->getRegion(glyph.getName());
        
          float x0 = pen.m_fX + glyph.getOffsetX();
          float y0 = pen.m_fY + glyph.getOffsetY();

          float x1 = x0 + (float)glyph.getWidth();
          float y1 = y0 - (float)glyph.getHeight();

          float s0 = region.getU();
          float s1 = region.getU2();
          float t0 = region.getV();
          float t1 = region.getV2();
        
          Vertex vertices[] = {
            Vertex(  x0, y0, 0.0f, s0, t0),
            Vertex(  x0, y1, 0.0f, s0, t1),
            Vertex(  x1, y1, 0.0f, s1, t1),
            Vertex(  x1, y1, 0.0f, s1, t1),
            Vertex(  x1, y0, 0.0f, s1, t0),
            Vertex(  x0, y0, 0.0f, s0, t0)
          };
          textVB->writeData(offset, sizeof(vertices), &vertices);
          offset+=6*sizeof(Vertex);

          // move pen for next glyph
          pen.m_fX += glyph.getAdvanceX();
}

Stange is that i only got failures using NPOT dimension which cold not devide by two.

http://s1.directuplo…q7zoyhx_jpg.htm // Rendering issue with 37x37 texture atlas

http://s14.directupl…ilpon3w_jpg.htm // Correct rendering with 36x36 texture atlas and Texture atlas debug image in both cases.

I’m running out of ideas what could be wrong.

P.S. I’ve tested yesterday also the DirectX9 mapping. If it not crashes (crashes are undefined, I actually not figured out why) I got always same chopping glyph rendering results until I use the POT Dimensions on atlas texture. I’ve read somewhere that DirectX streches the NPOT textures to POT which could results in those wired effects. Could it be possible that this is done by OpenGL two somewhere?

6eaf0e08fe36b2c23ca096562dd7a8b7
0
__________Smile_ 101 Jun 14, 2012 at 11:12

Looks like alignment problem. How do you set texture data? Do you pack lines tightly or with some alignment?
See http://www.opengl.org/wiki/Common_Mistakes#Texture_upload_and_pixel_reads.

07b9e9e8483468e4a0e1bac1843e6e74
0
Snoob 105 Jun 14, 2012 at 12:01

Holy sh..! This was the issue! Thanks for your excellent help!

07b9e9e8483468e4a0e1bac1843e6e74
0
Snoob 105 Jun 15, 2012 at 20:12

Ok, here we are again ! Everything is running fine now with OpenGL. But now I’m struggle with the DirectX9 implementation …

Following the advise of Reedbeta I’ve implemented a NPOT hardware support check controling the device caps settings. My system
supports NPOT textures. But as before with the OpenGL implementation, the output is completly chopped:

http://s14.directupl…9tafglk_jpg.htm //glyph string

http://s14.directup…94i3xu_jpg.htm // single glyph @

I’ve consult my friend google and it say’s I’ve only to check if NPOT support exists or use a special flag if I load an NPOT from file, but when
I use CreateTexture as I do, there is nothing to do for NPOT support and CreateTexture should not stretch up my dimensions. By this reason
I’ve checked the surface description of my texture to control the dimensions, and those are NPOT as defined (117x117) …

But my Glyphs are chopped. I’ve also checked my mipmap and texture addressing settings, there is no mipmap defined:

  • D3D9 min filter option : D3DTEXF_LINEAR
  • D3D9 mag filter option : D3DTEXF_LINEAR
  • D3D9 mip filter option : D3DTEXF_NONE
  • D3D9_U texture addressing mode : D3DTADDRESS_CLAMP
  • D3D9_V texture addressing mode : D3DTADDRESS_CLAMP
  • D3D9_W texture addressing mode : D3DTADDRESS_CLAMP

Have I overseen something? Or is there an DX equivalent to the OpenGL pixel alignment I’ve to regard?

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Jun 15, 2012 at 22:57

@Snoob

Or is there an DX equivalent to the OpenGL pixel alignment I’ve to regard?

Yes there is. When you lock the texture, it gives you pitch value you must use to jump to the next line in the locked texture data.

Cheers, Jarkko

07b9e9e8483468e4a0e1bac1843e6e74
0
Snoob 105 Jun 16, 2012 at 08:38

Yes there is. When you lock the texture, it gives you pitch value you must use to jump to the next line in the locked texture data.

I regard this pitch already when I copy my data to texture and I think this is not the problem:

       this->lock(0,0);  
       unsigned int pitch = m_locked.rect->Pitch;

       BYTE* dst = (BYTE*)m_locked.rect->pBits;
       
       // determine bytes of the whole image and copy data
       unsigned int bytes = pitch * image->getHeight();
       memcpy( dst, (LPVOID)image->getImageData(), bytes);
      
       this->unlock(0);    

What I’ve figured out is that any NPOT texture I created will not work, also the NPOT textures,
whith dimension I could devide by two. Only POT works…

B5262118b588a5a420230bfbef4a2cdf
0
Stainless 151 Jun 16, 2012 at 09:51

Okay lets consider a small section, you have a bitmap that is 5 pixels wide.

In memory this bitmap will be stored (numbers = y coord)
00000
11111
22222
…. etc

When loaded it will probably have a pitch of 8, so when you copy the data in you cannot just memcpy the bits.

If you do that, then the bitmap in memory will be
00000111
11222223
33334444

Corrupted to hell

What you need to do is something like this

int dwidth = image->getWidth();
BYTE * src =image->getImageData();
for (int y=0; y<image->getHeight(); y++)
{
   memcpy(dst, (LPVOID)src,dwidth*sizeof(pixel));
   dst+=bytes;
   src+=dwidth*sizeof(pixel);
}

The easy way to check if this is the case is to put a breakpoint on the memcpy and look at bytes. If it isn’t the same as the width of the image * the byte size of the pixel, you know that I am right

07b9e9e8483468e4a0e1bac1843e6e74
0
Snoob 105 Jun 16, 2012 at 17:25

I’ve followed your advertise Stainless and it looks like working. Thanks! But what I haven’t understand is why is the pitch of the created DX texture is different from the stride of the image in memory when pixelformat and dimensons are the same?

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Jun 16, 2012 at 22:46

@Snoob

I regard this pitch already when I copy my data to texture and I think this is not the problem:

In your code you use the pitch value wrong. Your source image has probably pitch=width*sizeof(pixel), while created DX/OGL texture may have larger pitch (probably due to texture addressing reasons), which is why you have to copy the texture line-by-line instead.

B5262118b588a5a420230bfbef4a2cdf
0
Stainless 151 Jun 17, 2012 at 10:54

Some hardware platforms only support power of two textures.

so if your texture is 65 pixels wide, in the hardware it will be 128 pixels wide.

This is one of the things that often catches people out.

07b9e9e8483468e4a0e1bac1843e6e74
0
Snoob 105 Jun 17, 2012 at 12:21

Ah ok this makes sense. Thanks for the great explanations.