Magnum::TextureTools::AtlasLandfill class new in Git master

Landfill texture atlas packer.

Keeps track of currently filled height at every pixel with the aim to fill the available space bottom-up as evenly as possible. Packs to a 2D or a 2D array texture with either the height or depth optionally unbounded. See also atlasArrayPowerOfTwo() for a variant that always provides optimal packing for power-of-two sizes.

The Trash Algorithm. Naming credit goes to @lacyyy.

Example usage

The following snippets shows packing a list of images into an atlas with the width set to 1024 and height unbounded. The algorithm by default makes all images the same orientation as that significantly improves the layout efficiency while not making any difference for texture mapping.

Containers::ArrayView<const ImageView2D> images = ;
Containers::Array<Vector2i> offsets{NoInit, images.size()};
Containers::BitArray rotations{NoInit, images.size()};

/* Fill the atlas with an unbounded height */
TextureTools::AtlasLandfill atlas{{1024, 0}};
atlas.add(stridedArrayView(images).slice(&ImageView2D::size), offsets, rotations);

/* Copy the image data to the atlas, assuming all are RGBA8Unorm as well */
Image2D output{PixelFormat::RGBA8Unorm, atlas.filledSize().xy(),
    Containers::Array<char>{ValueInit, std::size_t(atlas.filledSize().product()*4)}};
Containers::StridedArrayView2D<Color4ub> dst = output.pixels<Color4ub>();
for(std::size_t i = 0; i != images.size(); ++i) {
    /* Rotate 90° counterclockwise if the image is rotated in the atlas */
    Containers::StridedArrayView2D<const Color4ub> src = rotations[i] ?
        images[i].pixels<Color4ub>().flipped<1>().transposed<0, 1>() :
        images[i].pixels<Color4ub>();
    Utility::copy(src, dst.sliceSize(
        {std::size_t(offsets[i].y()),
         std::size_t(offsets[i].x())}, src.size()));
}

Calculating a texture coordinate transformation matrix for a particular image can then be done with atlasTextureCoordinateTransformation(), see its documentation for an example of how to calculate and apply the matrix to either the mesh directly or to a material / shader.

If rotations are undesirable, for example if the resulting atlas is used by a linear rasterizer later, they can be disabled by clearing appropriate AtlasLandfillFlags. The process can then also use the add(const Containers::StridedArrayView1D<const Vector2i>&, const Containers::StridedArrayView1D<Vector2i>&) overload without the rotations argument.

atlas.clearFlags(TextureTools::AtlasLandfillFlag::RotatePortrait|
                 TextureTools::AtlasLandfillFlag::RotateLandscape)
     .add(stridedArrayView(images).slice(&ImageView2D::size), offsets);

/* Copy the image data to the atlas, assuming all are RGBA8Unorm as well */
Image2D output{PixelFormat::RGBA8Unorm, atlas.filledSize().xy(),
    Containers::Array<char>{ValueInit, std::size_t(atlas.filledSize().product()*4)}};
Containers::StridedArrayView2D<Color4ub> dst = output.pixels<Color4ub>();
for(std::size_t i = 0; i != images.size(); ++i) {
    Containers::StridedArrayView2D<const Color4ub> src = images[i].pixels<Color4ub>();
    Utility::copy(src, dst.sliceSize(
        {std::size_t(offsets[i].y()),
         std::size_t(offsets[i].x())}, src.size()));
}

Array atlas

The packing can be extended to a third dimension as well, in which case the packing overflows to next slices instead of expanding to potentially unbounded height.

Containers::ArrayView<const ImageView2D> images = ;
Containers::Array<Vector3i> offsets{NoInit, images.size()};
Containers::BitArray rotations{NoInit, images.size()};

/* Fill the atlas with an unbounded depth */
TextureTools::AtlasLandfill atlas{{1024, 1024, 0}};
atlas.add(stridedArrayView(images).slice(&ImageView2D::size), offsets, rotations);

/* Copy the image data to the atlas, assuming all are RGBA8Unorm as well */
Image3D output{PixelFormat::RGBA8Unorm, atlas.filledSize(),
    Containers::Array<char>{ValueInit, std::size_t(atlas.filledSize().product()*4)}};
Containers::StridedArrayView3D<Color4ub> dst = output.pixels<Color4ub>();
for(std::size_t i = 0; i != images.size(); ++i) {
    /* Rotate 90° counterclockwise if the image is rotated in the atlas */
    Containers::StridedArrayView3D<const Color4ub> src = rotations[i] ?
        images[i].pixels<Color4ub>().flipped<1>().transposed<0, 1>() :
        images[i].pixels<Color4ub>();
    Utility::copy(src, dst.sliceSize(
        {std::size_t(offsets[i].z()),
         std::size_t(offsets[i].y()),
         std::size_t(offsets[i].x())}, src.size()));
}

The layer has to be taken into an account in addition to the texture coordinate transformation matrix calculated with atlasTextureCoordinateTransformation(), for example by adding a texture layer attribute to Trade::MaterialData.

Packing process

On every add(), the algorithm first makes all sizes the same orientation depending on AtlasLandfillFlag::RotatePortrait or RotateLandscape being set and sorts the sizes highest first and then depending on AtlasLandfillFlag::WidestFirst or NarrowestFirst being set.

A per-pixel array of currently filled heights, initially all 0, and a horizontal insertion cursor, initially 0, is maintained. An item of given size gets placed at a height that's max(heights[cursor], heights[cursor + size.x]), this range gets then set to height + size.y and the cursor is updated to cursor + size.x. If cursor reaches the edge that an item cannot fit there anymore, it's reset to 0 and the process continues again in the opposite direction, or the same direction if the previous row ended higher than it started. With the assumption that the texture sizes are uniformly distributed, this results in a fairly leveled out height. The process is aborted if the atlas height is bounded and the next item cannot fit there anymore.

The sort is performed using std::stable_sort(), which is usually $ \mathcal{O}(n \log{} n) $ , the actual atlasing is a single $ \mathcal{O}(n) $ operation. Memory complexity is $ \mathcal{O}(n + wc) $ with $ n $ being a sorted copy of the input size array and $ wc $ being a 16-bit integer for every pixel of atlas width times filled atlas depth. Additionally std::stable_sort() performs its own allocation.

Incremental population

It's possible to call add() multiple times in order to incrementally fill the atlas with new data as much as the atlas height (if bounded) allows. In an ideal scenario, if the previous fill resulted in an uniform height the newly added data will be added in an optimal way as well, but in practice calling add() with all data just once will always result in a more optimal packing than an incremental one.

In case of an array atlas, the incremental process always starts from the first slice, finding the first that can fit the first (sorted) item. Then it attempts to place as many items as possible and on overflow continues searching for the next slice that can fit the first remaining item. If all slices are exhausted, adds a new one for as long as the depth (if bounded) allows.

Constructors, destructors, conversion operators

AtlasLandfill(const Vector3i& size) explicit
Constructor.
AtlasLandfill(const Vector2i& size) explicit
Construct a non-array atlas.
AtlasLandfill(const AtlasLandfill&) deleted
Copying is not allowed.
AtlasLandfill(AtlasLandfill&&) noexcept
Move constructor.

Public functions

auto operator=(const AtlasLandfill&) -> AtlasLandfill& deleted
Copying is not allowed.
auto operator=(AtlasLandfill&&) -> AtlasLandfill& noexcept
Move assignment.
auto size() const -> Vector3i
Atlas size specified in constructor.
auto filledSize() const -> Vector3i
Currently filled size.
auto flags() const -> AtlasLandfillFlags
Behavior flags.
auto setFlags(AtlasLandfillFlags flags) -> AtlasLandfill&
Set behavior flags.
auto addFlags(AtlasLandfillFlags flags) -> AtlasLandfill&
Add behavior flags.
auto clearFlags(AtlasLandfillFlags flags) -> AtlasLandfill&
Clear behavior flags.
auto padding() const -> Vector2i
Padding around each texture.
auto setPadding(const Vector2i& padding) -> AtlasLandfill&
Set padding around each texture.
auto add(const Containers::StridedArrayView1D<const Vector2i>& sizes, const Containers::StridedArrayView1D<Vector3i>& offsets, Containers::MutableBitArrayView rotations) -> bool
Add textures to the atlas.
auto add(std::initializer_list<Vector2i> sizes, const Containers::StridedArrayView1D<Vector3i>& offsets, Containers::MutableBitArrayView rotations) -> bool
auto add(const Containers::StridedArrayView1D<const Vector2i>& sizes, const Containers::StridedArrayView1D<Vector3i>& offsets) -> bool
Add textures to the atlas with rotations disabled.
auto add(std::initializer_list<Vector2i> sizes, const Containers::StridedArrayView1D<Vector3i>& offsets) -> bool
auto add(const Containers::StridedArrayView1D<const Vector2i>& sizes, const Containers::StridedArrayView1D<Vector2i>& offsets, Containers::MutableBitArrayView rotations) -> bool
Add textures to a non-array atlas.
auto add(std::initializer_list<Vector2i> sizes, const Containers::StridedArrayView1D<Vector2i>& offsets, Containers::MutableBitArrayView rotations) -> bool
auto add(const Containers::StridedArrayView1D<const Vector2i>& sizes, const Containers::StridedArrayView1D<Vector2i>& offsets) -> bool
Add textures to a non-array atlas with rotations disabled.
auto add(std::initializer_list<Vector2i> sizes, const Containers::StridedArrayView1D<Vector2i>& offsets) -> bool

Function documentation

Magnum::TextureTools::AtlasLandfill::AtlasLandfill(const Vector3i& size) explicit

Constructor.

The size is expected to have non-zero width, and height not larger than 65536. If height is 0, depth is expected to be 1 and the height is treated as unbounded, i.e. add() never fails. Otherwise, if depth is 0, depth is treated as unbounded.

Magnum::TextureTools::AtlasLandfill::AtlasLandfill(const Vector2i& size) explicit

Construct a non-array atlas.

Same as calling AtlasLandfill with depth set to 1.

Magnum::TextureTools::AtlasLandfill::AtlasLandfill(AtlasLandfill&&) noexcept

Move constructor.

Performs a destructive move, i.e. the original object isn't usable afterwards anymore.

Vector3i Magnum::TextureTools::AtlasLandfill::size() const

Atlas size specified in constructor.

Vector3i Magnum::TextureTools::AtlasLandfill::filledSize() const

Currently filled size.

Width is always taken from size().

If size() depth is 1, the returned depth is always 1, height is 0 initially, and at most the height of size() if it's bounded. It's calculated with a $ \mathcal{O}(w) $ complexity, with $ w $ being the atlas width.

Otherwise, if size() depth is not 1, the height is taken from size() and the depth is 0 initially, and at most size() depth if the size is bounded.

AtlasLandfillFlags Magnum::TextureTools::AtlasLandfill::flags() const

Behavior flags.

Default is AtlasLandfillFlag::RotatePortrait and WidestFirst.

AtlasLandfill& Magnum::TextureTools::AtlasLandfill::setFlags(AtlasLandfillFlags flags)

Set behavior flags.

Returns Reference to self (for method chaining)

Note that some flags are mutually exclusive, see documentation of particular AtlasLandfillFlag values for more information. Can be called with different values before each particular add().

AtlasLandfill& Magnum::TextureTools::AtlasLandfill::addFlags(AtlasLandfillFlags flags)

Add behavior flags.

Returns Reference to self (for method chaining)

Calls setFlags() with the existing flags ORed with flags. Useful for preserving the defaults.

AtlasLandfill& Magnum::TextureTools::AtlasLandfill::clearFlags(AtlasLandfillFlags flags)

Clear behavior flags.

Returns Reference to self (for method chaining)

Calls setFlags() with the existing flags ANDed with the inverse of flags. Useful for preserving the defaults.

Vector2i Magnum::TextureTools::AtlasLandfill::padding() const

Padding around each texture.

Default is a zero vector.

AtlasLandfill& Magnum::TextureTools::AtlasLandfill::setPadding(const Vector2i& padding)

Set padding around each texture.

Returns Reference to self (for method chaining)

Sizes are extended with twice the padding value before placement but the returned offsets are without padding again. The third dimension isn't treated in any special way. In order to have AtlasLandfillFlag::RotatePortrait and RotateLandscape work well also with non-uniform padding, the padding is applied before a potential rotation. I.e., the horizontal padding value is always applied on input image width independently on how it's rotated after. If you need different behavior, disable rotations with clearFlags() or pre-pad the input sizes directly instead of using this function.

Can be called with different values before each particular add().

bool Magnum::TextureTools::AtlasLandfill::add(const Containers::StridedArrayView1D<const Vector2i>& sizes, const Containers::StridedArrayView1D<Vector3i>& offsets, Containers::MutableBitArrayView rotations)

Add textures to the atlas.

Parameters
sizes in Texture sizes
offsets out Resulting offsets in the atlas
rotations out Which textures got rotated

The sizes, offsets and rotations views are expected to have the same size. The sizes are all expected to be not larger than size() after appying padding and then a rotation based on AtlasLandfillFlag::RotatePortrait or RotateLandscape being set. If neither RotatePortrait nor RotateLandscape is set, the rotations view can be also empty or you can use the add(const Containers::StridedArrayView1D<const Vector2i>&, const Containers::StridedArrayView1D<Vector2i>&) overload. The resulting offsets always point to the original (potentially rotated) sizes without padding applied.

Items with zero width or height don't contribute to the layout in any way if padding is zero, but are still sorted, rotated and placed relative to others. If padding is non-zero, items with zero width or height are treated as any others to make sure they don't overlap other items.

On success returns true and updates filledSize(). If size() is bounded, can return false if the items didn't fit, in which case the internals and contents of offsets and rotations are left in an undefined state. For an unbounded size() returns true always.

bool Magnum::TextureTools::AtlasLandfill::add(std::initializer_list<Vector2i> sizes, const Containers::StridedArrayView1D<Vector3i>& offsets, Containers::MutableBitArrayView rotations)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool Magnum::TextureTools::AtlasLandfill::add(const Containers::StridedArrayView1D<const Vector2i>& sizes, const Containers::StridedArrayView1D<Vector3i>& offsets)

Add textures to the atlas with rotations disabled.

Equivalent to calling add(const Containers::StridedArrayView1D<const Vector2i>&, const Containers::StridedArrayView1D<Vector3i>&, Containers::MutableBitArrayView) with the rotations view being empty. Can be called only if neither AtlasLandfillFlag::RotatePortrait nor RotateLandscape is set.

bool Magnum::TextureTools::AtlasLandfill::add(std::initializer_list<Vector2i> sizes, const Containers::StridedArrayView1D<Vector3i>& offsets)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool Magnum::TextureTools::AtlasLandfill::add(const Containers::StridedArrayView1D<const Vector2i>& sizes, const Containers::StridedArrayView1D<Vector2i>& offsets, Containers::MutableBitArrayView rotations)

Add textures to a non-array atlas.

Can be called only if size() depth is 1.

bool Magnum::TextureTools::AtlasLandfill::add(std::initializer_list<Vector2i> sizes, const Containers::StridedArrayView1D<Vector2i>& offsets, Containers::MutableBitArrayView rotations)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool Magnum::TextureTools::AtlasLandfill::add(const Containers::StridedArrayView1D<const Vector2i>& sizes, const Containers::StridedArrayView1D<Vector2i>& offsets)

Add textures to a non-array atlas with rotations disabled.

Equivalent to calling add(const Containers::StridedArrayView1D<const Vector2i>&, const Containers::StridedArrayView1D<Vector2i>&, Containers::MutableBitArrayView) with the rotations view being empty. Can be called only if size() depth is 1 and neither AtlasLandfillFlag::RotatePortrait nor RotateLandscape is set.

bool Magnum::TextureTools::AtlasLandfill::add(std::initializer_list<Vector2i> sizes, const Containers::StridedArrayView1D<Vector2i>& offsets)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.