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 nighboring 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) bookeeping overhead when allocating and removing rectangles and imperfect defragmentation (see the "Limitations" section below.

The subdivision scheme uses the worst fit varriant 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
     |   |   |   |   |
     #   h   J   K   |
     |               |
 +-+-+-+-+. . . . . .|. 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 coalesed into a single one.

An important thing to note about this tree structure is that we only use it to visit niieghbor 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 sibblings, and we never have to traverse any global list of free rectangle nodes.

Merging sibblings

As soon as two consecutive sibbling nodes are marked as "free", they are coalesced into a single node.

In the example below, we juct deallocated the rectangle B, which is a sibblig 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 sibbling 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
    |       |    |                       |       |    |
    #       #    |               or      #       #    |
    |       |    |                       |       |    |
  +-+-+ . +-+-+ .|. 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 sibblings.

For a lot of workloads it is rather rare for two consecutive sibbling 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.

Methods

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 that rounds out the allocated rectangles to multiples of the provided value.

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 rearrange(&mut self) -> ChangeList

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

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.