Struct guillotiere::AtlasAllocator

pub struct AtlasAllocator { /* fields omitted */ }

A dynamic texture atlas allocator using the guillotine algorithm.

The guillotine algorithm is assisted by a data structure that keeps track of neighboring rectangles to provide fast deallocation and coalescing.

Goals

Coalescing free rectangles, in the context of dynamic atlas allocation can be prohibitively expensive under real-time constraints if the algorithm needs to visit a large amount of free rectangles to find merge candidates.

This implementation proposes a compromise with fast (constant time) search for merge candidates at the expense of some (constant time) bookkeeping overhead when allocating and removing rectangles and imperfect defragmentation (see the “Limitations” section below.

The subdivision scheme uses the worst fit variant of the guillotine algorithm for its simplicity and CPU efficiency.

The data structure

We maintain a tree with allocated and free rectangles as leaf nodes and containers as non-leaf nodes.

The direct children of a Containers’s form an ordered horizontal or vertical sequence of rectangles that cover exactly their parent container’s area.

For example, a subdivision such as this one:

+-----------+----------+---+---+--+---------+---+
|           |          | C | D |E | F       | G |
|           |          +---+---+--+---------+---+
|     A     |    B     |                        |
|           |          |           H            |
|           |          |                        |
+------+----+----------+-+----------------------+
|      |        J        |                      |
|  I   +-----------------+          L           |
|      |        K        |                      |
+------+-----------------+----------------------+

Would have a tree of the form:

 Tree                | Layout
---------------------+------------
                     |
          |          |
     +----+----+. . .|. vertical
     |         |     |
     |         |     |
   +-+-+ . . +-+-+. .|. horizontal
   | | |     | | |   |
   A B #     I # L   |
       |       |     |
     +-+-+ . +-+-+. .|. vertical
     |   |   |   |   |
     |               |
 +-+-+-+-+. . . . . .|. horizontal
 | | | | |           |
 C D E F G           |

Where container nodes are represented with “#”.

Note that if a horizontal container is the direct child of another horizontal container, we can merge the two into a single horizontal sequence. We use this property to always keep the tree in its simplest form. In practice this means that the orientation of a container is always the opposite of the orientation of its parent, if any.

The goal of this data structure is to quickly find neighboring free rectangles that can be coalesced into fewer rectangles. This structure guarantees that two consecutive children of the same container, if both rectangles are free, can be coalesced into a single one.

An important thing to note about this tree structure is that we only use it to visit neighbor and parent nodes. As a result we don’t care about whether the tree is balanced, although flat sequences of children tend to offer more opportunity for coalescing than deeply nested structures Either way, the cost of finding potential merges is the same because each node stores the indices of their siblings, and we never have to traverse any global list of free rectangle nodes.

Merging siblings

As soon as two consecutive sibling nodes are marked as “free”, they are coalesced into a single node.

In the example below, we just deallocated the rectangle B, which is a sibling of A which is free and C which is still allocated. A and B are merged and this change is reflected on the tree as shown below:

+---+---+---+         #               +-------+---+         #
|   |   |///|         |               |       |///|         |
| A | B |/C/|     +---+---+           | AB    |/C/|     +---+---+
|   |   |///|     |       |           |       |///|     |       |
+---+---+---+     #       D           +-------+---+     #       D
| D         |     |            ->     | D         |     |
|           |   +-+-+                 |           |   +-+-+
|           |   | | |                 |           |   |   |
+-----------+   A B C                 +-----------+   AB  C

Merging unique children with their parents

In the previous example C was an allocated slot. Let’s now deallocate it:

+-------+---+         #               +-----------+         #                 #
|       |   |         |               |           |         |                 |
| AB    | C |     +---+---+           | ABC       |     +---+---+         +---+---+
|       |   |     |       |           |           |     |       |         |       |
+-------+---+     #       D           +-----------+     #       D        ABC      D
| D         |     |            ->     | D         |     |           ->
|           |   +-+-+                 |           |     +
|           |   |   |                 |           |     |
+-----------+   AB  C                 +-----------+    ABC

Deallocating C allowed it to merge with the free rectangle AB, making the resulting node ABC the only child of its parent container. As a result the node ABC was lifted up the tree to replace its parent.

In this example, assuming D to also be a free rectangle, ABC and D would be immediately merged and the resulting node ABCD, also being only child of its parent container, would replace its parent, turning the tree into a single node ABCD.

Limitations

This strategy can miss some opportunities for coalescing free rectangles when the two sibling containers are split exactly the same way.

For example:

+---------+------+
|    A    |  B   |
|         |      |
+---------+------+
|    C    |  D   |
|         |      |
+---------+------+

Could be the result of either a vertical followed with two horizontal splits, or an horizontal then two vertical splits.

 Tree            | Layout             Tree            | Layout
-----------------+------------       -----------------+------------
        |        |                           |        |
    +---+---+ . .|. Vertical             +---+---+ . .|. Horizontal
    |       |    |                       |       |    |
    |       |    |                       |       |    |
  +-+-+ . +-+-+ .|. Horizontal         +-+-+ . +-+-+ .|. Vertical
  |   |   |   |  |                     |   |   |   |  |
  A   B   C   D  |                     A   C   B   D  |

In the former case A can’t be merged with C nor B with D because they are not siblings.

For a lot of workloads it is rather rare for two consecutive sibling containers to be subdivided exactly the same way. In this situation losing the ability to merge rectangles that aren’t under the same container is good compromise between the CPU cost of coalescing and the fragmentation of the atlas.

This algorithm is, however, not the best solution for very “structured” grid-like subdivision patterns where the ability to merge across containers would have provided frequent defragmentation opportunities.

Implementations

impl AtlasAllocator

pub fn new(size: Size) -> Self

Create an atlas allocator.

pub fn with_options(size: Size, options: &AllocatorOptions) -> Self

Create an atlas allocator with the provided options.

pub fn size(&self) -> Size

The total size of the atlas.

pub fn allocate(&mut self, requested_size: Size) -> Option<Allocation>

Allocate a rectangle in the atlas.

pub fn deallocate(&mut self, node_id: AllocId)

Deallocate a rectangle in the atlas.

pub fn is_empty(&self) -> bool

pub fn clear(&mut self)

Drop all rectangles, clearing the atlas to its initial state.

pub fn reset(&mut self, size: Size, options: &AllocatorOptions)

Clear the allocator and reset its size and options.

pub fn rearrange(&mut self) -> ChangeList

Recompute the allocations in the atlas and returns a list of the changes.

Previous ids and rectangles are not valid anymore after this operation as each id/rectangle pair is assigned to new values which are communicated in the returned change list. Rearranging the atlas can help reduce fragmentation.

pub fn resize_and_rearrange(&mut self, new_size: Size) -> ChangeList

Identical to AtlasAllocator::rearrange, also allowing to change the size of the atlas.

pub fn grow(&mut self, new_size: Size)

Resize the atlas without changing the allocations.

This method is not allowed to shrink the width or height of the atlas.

pub fn for_each_free_rectangle<F>(&self, callback: F) where
    F: FnMut(&Rectangle), 

Invoke a callback for each free rectangle in the atlas.

pub fn for_each_allocated_rectangle<F>(&self, callback: F) where
    F: FnMut(AllocId, &Rectangle), 

Invoke a callback for each allocated rectangle in the atlas.

Trait Implementations

impl Clone for AtlasAllocator

fn clone(&self) -> AtlasAllocator

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Index<AllocId> for AtlasAllocator

type Output = Rectangle

The returned type after indexing.

fn index(&self, index: AllocId) -> &Rectangle

Performs the indexing (container[index]) operation.