/*
* Copyright (C) 2013 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package android.graphics;
/**
* @hide
*/
public class Atlas {
/**
* This flag indicates whether the packing algorithm will attempt
* to rotate entries to make them fit better in the atlas.
*/
public static final int FLAG_ALLOW_ROTATIONS = 0x1;
/**
* This flag indicates whether the packing algorithm should leave
* an empty 1 pixel wide border around each bitmap. This border can
* be useful if the content of the atlas will be used in OpenGL using
* bilinear filtering.
*/
public static final int FLAG_ADD_PADDING = 0x2;
/**
* Default flags: allow rotations and add padding.
*/
public static final int FLAG_DEFAULTS = FLAG_ADD_PADDING;
/**
* Each type defines a different packing algorithm that can
* be used by an {@link Atlas}. The best algorithm to use
* will depend on the source dataset and the dimensions of
* the atlas.
*/
public enum Type {
SliceMinArea,
SliceMaxArea,
SliceShortAxis,
SliceLongAxis
}
/**
* Represents a bitmap packed in the atlas. Each entry has a location in
* pixels in the atlas and a rotation flag. If the entry was rotated, the
* bitmap must be rotated by 90 degrees (in either direction as long as
* the origin remains the same) before being rendered into the atlas.
*/
public static class Entry {
/**
* Location, in pixels, of the bitmap on the X axis in the atlas.
*/
public int x;
/**
* Location, in pixels, of the bitmap on the Y axis in the atlas.
*/
public int y;
/**
* If true, the bitmap must be rotated 90 degrees in the atlas.
*/
public boolean rotated;
}
private final Policy mPolicy;
/**
* Creates a new atlas with the specified algorithm and dimensions
* in pixels. Calling this constructor is equivalent to calling
* {@link #Atlas(Atlas.Type, int, int, int)} with {@link #FLAG_DEFAULTS}.
*
* @param type The algorithm to use to pack rectangles in the atlas
* @param width The width of the atlas in pixels
* @param height The height of the atlas in pixels
*
* @see #Atlas(Atlas.Type, int, int, int)
*/
public Atlas(Type type, int width, int height) {
this(type, width, height, FLAG_DEFAULTS);
}
/**
* Creates a new atlas with the specified algorithm and dimensions
* in pixels. A set of flags can also be specified to control the
* behavior of the atlas.
*
* @param type The algorithm to use to pack rectangles in the atlas
* @param width The width of the atlas in pixels
* @param height The height of the atlas in pixels
* @param flags Optional flags to control the behavior of the atlas:
* {@link #FLAG_ADD_PADDING}, {@link #FLAG_ALLOW_ROTATIONS}
*
* @see #Atlas(Atlas.Type, int, int)
*/
public Atlas(Type type, int width, int height, int flags) {
mPolicy = findPolicy(type, width, height, flags);
}
/**
* Packs a rectangle of the specified dimensions in this atlas.
*
* @param width The width of the rectangle to pack in the atlas
* @param height The height of the rectangle to pack in the atlas
*
* @return An {@link Entry} instance if the rectangle was packed in
* the atlas, or null if the rectangle could not fit
*
* @see #pack(int, int, Atlas.Entry)
*/
public Entry pack(int width, int height) {
return pack(width, height, null);
}
/**
* Packs a rectangle of the specified dimensions in this atlas.
*
* @param width The width of the rectangle to pack in the atlas
* @param height The height of the rectangle to pack in the atlas
* @param entry Out parameter that will be filled in with the location
* and attributes of the packed rectangle, can be null
*
* @return An {@link Entry} instance if the rectangle was packed in
* the atlas, or null if the rectangle could not fit
*
* @see #pack(int, int)
*/
public Entry pack(int width, int height, Entry entry) {
if (entry == null) entry = new Entry();
return mPolicy.pack(width, height, entry);
}
private static Policy findPolicy(Type type, int width, int height, int flags) {
switch (type) {
case SliceMinArea:
return new SlicePolicy(width, height, flags,
new SlicePolicy.MinAreaSplitDecision());
case SliceMaxArea:
return new SlicePolicy(width, height, flags,
new SlicePolicy.MaxAreaSplitDecision());
case SliceShortAxis:
return new SlicePolicy(width, height, flags,
new SlicePolicy.ShorterFreeAxisSplitDecision());
case SliceLongAxis:
return new SlicePolicy(width, height, flags,
new SlicePolicy.LongerFreeAxisSplitDecision());
}
return null;
}
/**
* A policy defines how the atlas performs the packing operation.
*/
private static abstract class Policy {
abstract Entry pack(int width, int height, Entry entry);
}
/**
* The Slice algorightm divides the remaining empty space either
* horizontally or vertically after a bitmap is placed in the atlas.
*
* NOTE: the algorithm is explained below using a tree but is
* implemented using a linked list instead for performance reasons.
*
* The algorithm starts with a single empty cell covering the entire
* atlas:
*
* -----------------------
* | |
* | |
* | |
* | Empty space |
* | (C0) |
* | |
* | |
* | |
* -----------------------
*
* The tree of cells looks like this:
*
* N0(free)
*
* The algorithm then places a bitmap B1, if possible:
*
* -----------------------
* | | |
* | B1 | |
* | | |
* |-------- |
* | |
* | |
* | |
* | |
* -----------------------
*
* After placing a bitmap in an empty cell, the algorithm splits
* the remaining space in two new empty cells. The split can occur
* vertically or horizontally (this is controlled by the "split
* decision" parameter of the algorithm.)
*
* Here is for the instance the result of a vertical split:
*
* -----------------------
* | | |
* | B1 | |
* | | |
* |--------| C2 |
* | | |
* | | |
* | C1 | |
* | | |
* -----------------------
*
* The cells tree now looks like this:
*
* C0(occupied)
* / \
* / \
* / \
* / \
* C1(free) C2(free)
*
* For each bitmap to place in the atlas, the Slice algorithm
* will visit the free cells until it finds one where a bitmap can
* fit. It will then split the now occupied cell and proceed onto
* the next bitmap.
*/
private static class SlicePolicy extends Policy {
private final Cell mRoot = new Cell();
private final SplitDecision mSplitDecision;
private final boolean mAllowRotation;
private final int mPadding;
/**
* A cell represents a sub-rectangle of the atlas. A cell is
* a node in a linked list representing the available free
* space in the atlas.
*/
private static class Cell {
int x;
int y;
int width;
int height;
Cell next;
@Override
public String toString() {
return String.format("cell[x=%d y=%d width=%d height=%d", x, y, width, height);
}
}
SlicePolicy(int width, int height, int flags, SplitDecision splitDecision) {
mAllowRotation = (flags & FLAG_ALLOW_ROTATIONS) != 0;
mPadding = (flags & FLAG_ADD_PADDING) != 0 ? 1 : 0;
// The entire atlas is empty at first, minus padding
Cell first = new Cell();
first.x = first.y = mPadding;
first.width = width - 2 * mPadding;
first.height = height - 2 * mPadding;
mRoot.next = first;
mSplitDecision = splitDecision;
}
@Override
Entry pack(int width, int height, Entry entry) {
Cell cell = mRoot.next;
Cell prev = mRoot;
while (cell != null) {
if (insert(cell, prev, width, height, entry)) {
return entry;
}
prev = cell;
cell = cell.next;
}
return null;
}
/**
* Defines how the remaining empty space should be split up:
* vertically or horizontally.
*/
private static interface SplitDecision {
/**
* Returns true if the remaining space defined by
* freeWidth and freeHeight
* should be split horizontally.
*
* @param freeWidth The rectWidth of the free space after packing a rectangle
* @param freeHeight The rectHeight of the free space after packing a rectangle
* @param rectWidth The rectWidth of the rectangle that was packed in a cell
* @param rectHeight The rectHeight of the rectangle that was packed in a cell
*/
boolean splitHorizontal(int freeWidth, int freeHeight,
int rectWidth, int rectHeight);
}
// Splits the free area horizontally to minimize the horizontal section area
private static class MinAreaSplitDecision implements SplitDecision {
@Override
public boolean splitHorizontal(int freeWidth, int freeHeight,
int rectWidth, int rectHeight) {
return rectWidth * freeHeight > freeWidth * rectHeight;
}
}
// Splits the free area horizontally to maximize the horizontal section area
private static class MaxAreaSplitDecision implements SplitDecision {
@Override
public boolean splitHorizontal(int freeWidth, int freeHeight,
int rectWidth, int rectHeight) {
return rectWidth * freeHeight <= freeWidth * rectHeight;
}
}
// Splits the free area horizontally if the horizontal axis is shorter
private static class ShorterFreeAxisSplitDecision implements SplitDecision {
@Override
public boolean splitHorizontal(int freeWidth, int freeHeight,
int rectWidth, int rectHeight) {
return freeWidth <= freeHeight;
}
}
// Splits the free area horizontally if the vertical axis is shorter
private static class LongerFreeAxisSplitDecision implements SplitDecision {
@Override
public boolean splitHorizontal(int freeWidth, int freeHeight,
int rectWidth, int rectHeight) {
return freeWidth > freeHeight;
}
}
/**
* Attempts to pack a rectangle of specified dimensions in the available
* empty space.
*
* @param cell The cell representing free space in which to pack the rectangle
* @param prev The previous cell in the free space linked list
* @param width The width of the rectangle to pack
* @param height The height of the rectangle to pack
* @param entry Stores the location of the packged rectangle, if it fits
*
* @return True if the rectangle was packed in the atlas, false otherwise
*/
@SuppressWarnings("SuspiciousNameCombination")
private boolean insert(Cell cell, Cell prev, int width, int height, Entry entry) {
boolean rotated = false;
// If the rectangle doesn't fit we'll try to rotate it
// if possible before giving up
if (cell.width < width || cell.height < height) {
if (mAllowRotation) {
if (cell.width < height || cell.height < width) {
return false;
}
// Rotate the rectangle
int temp = width;
width = height;
height = temp;
rotated = true;
} else {
return false;
}
}
// Remaining free space after packing the rectangle
int deltaWidth = cell.width - width;
int deltaHeight = cell.height - height;
// Split the remaining free space into two new cells
Cell first = new Cell();
Cell second = new Cell();
first.x = cell.x + width + mPadding;
first.y = cell.y;
first.width = deltaWidth - mPadding;
second.x = cell.x;
second.y = cell.y + height + mPadding;
second.height = deltaHeight - mPadding;
if (mSplitDecision.splitHorizontal(deltaWidth, deltaHeight,
width, height)) {
first.height = height;
second.width = cell.width;
} else {
first.height = cell.height;
second.width = width;
// The order of the cells matters for efficient packing
// We want to give priority to the cell chosen by the
// split decision heuristic
Cell temp = first;
first = second;
second = temp;
}
// Remove degenerate cases to keep the free list as small as possible
if (first.width > 0 && first.height > 0) {
prev.next = first;
prev = first;
}
if (second.width > 0 && second.height > 0) {
prev.next = second;
second.next = cell.next;
} else {
prev.next = cell.next;
}
// The cell is now completely removed from the free list
cell.next = null;
// Return the location and rotation of the packed rectangle
entry.x = cell.x;
entry.y = cell.y;
entry.rotated = rotated;
return true;
}
}
}