Planning the Spontaneous

It's more than just a blueprint.

glGenTexture(Atlas); // part2

Posted by Robert Chow on 19/03/2010

So from the plan I started to devise for my texture atlasing system, I decided to have a quick look at two methods. These two methods can help me to split up the texture in an efficient and appropriate way so I can maximise texture use and efficiency. These are the Binary Split Partitioning method, and the use of Quadtrees.

Binary Split Partitioning

This method takes a space and splits this into two, keeping a reference to each part. Using a binary tree, the tree can be used to keep a track of how the space is split at each stage.  This method works by taking the requested size (the image/sub-texture) and seeing if it fits into the space represented by a leaf node.  If not, then it will see if the requested size fits into the next leaf node using tree traversal.  To maximise efficiency, once a space that is free and large enough for the requested size is found, it splits this space into two;  both are represented as leaf nodes, yet one is the exact size as the requested size (and this is also where the requested texture is allocated) and the other is the remaining unallocated space.

Binary Split Partitioning.  This image represents the stages of how to insert a sub-texture(1) into a space managed by BSP.  Starting off at the top, (1) is requested and seen if it fits into space A.  A is too small, and it is split into 2 partitions, B and C.  (1) is compared to space B, and again splits this space into D and E.  As D is the perfect fit, (1) is allocated to this space.  The last image shows the final state of the tree after inserting (1).  The reason it cannot skip from stage 1 to stage 3 is because there is no possible way of splitting the space and keeping to an efficient BSP system – it is best to split each space linearly.  The splitting measurements are derived from the sub-texture to maximise efficiency.

I managed to find this method rather easy to implement, especially with the help from this page on lightmaps.  Using this, I also managed to come up with a simple demo, showcasing how it fits several random sub-textures into one.

BSP Texture Atlas.  This image shows my demo of inserting random sized images into a texture managed by BSP in progression.

Although easy to implement, there are a couple of drawbacks.  As this is an unbalanced binary tree, it becomes computationally very expensive to insert a sub-texture as the tree structure grows.  Adding tree rotation to balance the tree is possible – it doesn’t affect how the tree works when inserting a sub-texture.  However, it does affect the tree when it comes to deleting allocated space.  This is because the nodes derive from their parents; losing the connection between the parent and the children (which occurs heavily during tree rotation) means that to successfully delete an allocated space at node B derived from parent A and has sibling C, is more-or-less a very difficult feat.  If C is empty, A will be empty after the deallocation of space B – and thus B and C need not exist, leaving the big space referenced by A unsplit.  Taking away the natural bond between parent and child in a BSP tree due to tree rotation (or any other method for that matter) makes this problem rather hard to tackle as it could mean having to search the entire tree for the parent and other sibling.  These leaves me with a problem – do I keep the tree balanced, and make insertion less costly at the expense of not being able to delete; or do I allow for deallocation, whilst keeping insertion computationally expensive?  In the end, I will be inserting more times than not, and very rarely deleting, so I think the former is the best option for now.

Or I could look at quadtrees.

Quadtrees

This is where my planning goes wrong.  And I’ve also not researched quadtrees to the full extent.  I know what they are designed to do, I’m just unsure of how to implement them.

A quadtree is a structure whereby each node has four children.  Each node represents a square block in the texture, and each block is split into four smaller squares – the children.  This is repeatedly done until the size of a single block is a 1×1 square.

Quadtree Colour.  This displays how a texture is split up using quadtrees.  I have used colour to differentiate each node.  I guess it looks quite similar to one of those Dulux colour pickers.

As this structure is set in stone, its depth will be constant and we need not to worry about insertion/deletion costs.  It’s already a rather shallow structure in itself because each node has 4 children, as opposed to the typical 2.

The structure works by marking off what is allocated at the leaf nodes, and this is interpreted at the top.  If all of a node’s children is allocated, then that node too is marked as allocated.  From using this system, we can find if there is any space available in a node, and then check to see if the space provided is big enough to fit in the sub-texture.  My problem is that I’m unsure of how to do implement this efficiently.  For example, a very large sub-texture is inserted at the root, where everything is unallocated so far.  This takes up more than one quadrant of the root, and spills into the other quadrants.  By definition, the one quadrant the texture covers up is marked as allocated, yet the other quadrants are only partly allocated – some of their children are allocated but they also have children that are unallocated.  It is the next step which I cannot figure out; insert in another large texture – there is enough space in the root to place this, but it needs to take up the space given by two already partially filled quadrants.  How does it know how these quadrants are related in terms of position, and how does it then interpret the unallocated space in each of these quadrants?  They obviously need to be interpreted as adjacent, but then the available children of these quadrants also need to be interpreted as adjacent too.  It’s a puzzle I’ve decided to give this a miss, simply because I don’t have the time.

Quadtree Insert.  This depicts the problem I am having trouble with.  Inserting the first image will mark off the top-right quadrant as occupied, whilst the others are partially occupied.  It is easy to see that the second image will fit into the remaining space, but I am unsure of how to implement this.   This is because the second image will look at the root and find it is small enough to fit inside.  It will then look at the quadrants to see if it will fit in either of them, and it cannot because it is too big.   I do not know how to implement the detail where it looks at the quadrants together – I’m not even entirely sure if this is how quadtrees are supposed to work.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

 
%d bloggers like this: