Skip to content
July 12, 2009 / Abe Pralle

Dynamic texture sheets, iPhone and Android dev, UTF-8 source files

Some odds and ends:

ITEM: We finished up Wyrmhunter for the iPhone a week ago and submitted it to Apple.  They haven’t gotten around to approving it yet, but we’re hopeful it’ll be soon.

ITEM: One of the last major things was a revamp of my dynamic texture sheet management system.  With its already limited drawing speed, the best bet for the iPhone is to place all images on one big texture (or several), queue up a bunch of triangles as different images are drawn, and then render everything at once.  Even better is if you don’t have to lay things out yourself but can have Plasmacore do it for you as you dynamically load and unload images.

My initial stab at the problem worked well in some cases and very poorly in others.  I started out with one big region of unused texture.  Then after the first allocation I split it into several chunks – one used, the others not.  I decided to make everything below the used area one chunk and then the remaining strip to the right another chunk.  If the original free chunk were:


Then after allocation “A” it would be:


The problem was that I could end up with a whole lot of “B” chunks of various sizes that didn’t quite fit together.  There would sometimes be plenty of room to put something but no chunk large enough to put it in.  It was fragmentation but worse: it wasn’t that there were used areas, it was that the free areas were adjacent but slightly disjoint.

I beat my head against the problem for about a week and tried 6 or 7 different approaches.  I felt that the key was being able to span multiple free regions, but if I used regions as they became available then they were too disjoint, and if I used some sort of grid layout then the search area was too big.

Then finally I finally hit on the solution: when I allocated a region I would split the entire layout area (including all regions used and unused) along both axes to make the allocated region the exact right size while keeping all cells lined up at all 4 edges.  Imagine an Excel spreadsheet where you’ve randomly adjusted the widths of some columns, the heights of some rows, and filled in random cells – that’s what my texture sheet would look like after some heavy cycles of allocation and freeing.  Incidentally two adjacent empty rows become merged again, as do two adjacent empty columns.

The allocation algorithm is this: scan all regions row by row.  If a region is unused and unmarked, see if it’s the corner of a space that will fit the image (ensure available width at region is <= necessary width, then ensure available height at each region is <= necessary height).  If the space is big enough, mark the all of the rows as in use that are wide enough all the way down, mark all of the columns that are high enough all the way to the right, add the space to a list of possibilities, and continue searching.

The neat thing is that by marking the possible matches as you go you really cut down on the number of candidate spots you have to check for – and each candidate region you find is a corner already.

For example, say we had allocation A already and free regions B, C, and D:


When we try to fit in a new allocation we’ll find spots B (corner of BB/DD) and C (corner of CDD) – and that’s it!  The other possible spots will already be marked as used as we find the top-left B and then C.  Between the two, we’ll pick the one that has the best {exact match, matching width, matching height, smallest area} crossed with the one that has {no gaps above, has gaps above}.

I hope you can see what I’m getting at here… I tried drawing some nicer graphics and so on but it was getting way too complicated for what it was worth.  Anyhow, the code is in and it’s working beautifully.

ITEM: I’ve now turned my attention to porting Plasmacore to Android – it’s pretty virgin territory and, like Google itself, I think Android could be a sleeping giant (albeit a slightly unwieldy, slightly dorky giant).  Over half of us at Plasmaworks now have G1 phones.  I still like my iPhone but I’ll admit there’s a lot of nice stuff about Android.

I got stuck for a while on an esoteric gcc pointer bug that cropped up in my Slag VM code.  It only happens when you have a certain optimization level turned on, which Android does by default.  Say I have a pointer to integer “ip” – I could retrieve an integer at that address and increment the pointer to the next value with:

int x = *(ip++);

This is equivalent to:

int** ip_ptr = &ip;
int x = *((*ip_ptr)++);

which is equivalent to:

int x = *((*(&ip))++);

What I really wanted to do was access a double instead of an int at that position and then advance “ip” to point past the double.  I had:

double n = *((*((double**)&ip))++);

I made it a macro and was using it in a place or two, but it was Bug City on Androids gcc configuration.  I went back to doing it a simpler way across a couple of steps.

ITEM: Finally let me tell you about an interesting discovery.  Some stray unicode characters were exposing a UTF-8 encoding/decoding bug in my compiler + VM.  What I didn’t realize is that Vim (and apparently other editors…?) load and save text files in UTF-8 already – I had assumed Vim would only operate on raw bytes.   UTF-8, by the by, is a scheme to translate text that would normally be 2 bytes per character into 1 byte per character for most symbols and then 2 or 3 bytes for the less common symbols.



Leave a Comment
  1. joeedh / Jul 21 2009 9:11 pm

    By UTF-8, you mean the encoding was UTF-8, or was vim spitting out a BOM header?

  2. Abe Pralle / Jul 21 2009 9:59 pm

    No header, just UTF-8 encoding!

  3. Uriah / Aug 23 2009 2:57 pm

    Were you able to get PVRTC compression with your dynamic texture atlas on the iPhone?

  4. Abe Pralle / Aug 23 2009 5:19 pm

    No, it wouldn’t really work. Compressed textures are still decoded upon loading (AFAIK), so really they’re just a file size optimization, not a runtime memory optimization. I DID consider allowing a 16-bit texture format instead, but then everything would have to be 16-bit and the 1 pixel of alpha just seems to limiting.

    • Julien C / Nov 16 2009 8:07 am

      Abe: compressed textures are compressed. Decompressing them at runtime would defeat their purpose.

      You upload them using glCompressedTexImage2D(), not glTexImage2D(). Using PVR-compressed textures greatly improve performances on the iPod/iPhone.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: