1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.graphics; 18 19 /** 20 * @hide 21 */ 22 public class Atlas { 23 /** 24 * This flag indicates whether the packing algorithm will attempt 25 * to rotate entries to make them fit better in the atlas. 26 */ 27 public static final int FLAG_ALLOW_ROTATIONS = 0x1; 28 /** 29 * This flag indicates whether the packing algorithm should leave 30 * an empty 1 pixel wide border around each bitmap. This border can 31 * be useful if the content of the atlas will be used in OpenGL using 32 * bilinear filtering. 33 */ 34 public static final int FLAG_ADD_PADDING = 0x2; 35 /** 36 * Default flags: allow rotations and add padding. 37 */ 38 public static final int FLAG_DEFAULTS = FLAG_ADD_PADDING; 39 40 /** 41 * Each type defines a different packing algorithm that can 42 * be used by an {@link Atlas}. The best algorithm to use 43 * will depend on the source dataset and the dimensions of 44 * the atlas. 45 */ 46 public enum Type { 47 SliceMinArea, 48 SliceMaxArea, 49 SliceShortAxis, 50 SliceLongAxis 51 } 52 53 /** 54 * Represents a bitmap packed in the atlas. Each entry has a location in 55 * pixels in the atlas and a rotation flag. If the entry was rotated, the 56 * bitmap must be rotated by 90 degrees (in either direction as long as 57 * the origin remains the same) before being rendered into the atlas. 58 */ 59 public static class Entry { 60 /** 61 * Location, in pixels, of the bitmap on the X axis in the atlas. 62 */ 63 public int x; 64 /** 65 * Location, in pixels, of the bitmap on the Y axis in the atlas. 66 */ 67 public int y; 68 69 /** 70 * If true, the bitmap must be rotated 90 degrees in the atlas. 71 */ 72 public boolean rotated; 73 } 74 75 private final Policy mPolicy; 76 77 /** 78 * Creates a new atlas with the specified algorithm and dimensions 79 * in pixels. Calling this constructor is equivalent to calling 80 * {@link #Atlas(Atlas.Type, int, int, int)} with {@link #FLAG_DEFAULTS}. 81 * 82 * @param type The algorithm to use to pack rectangles in the atlas 83 * @param width The width of the atlas in pixels 84 * @param height The height of the atlas in pixels 85 * 86 * @see #Atlas(Atlas.Type, int, int, int) 87 */ 88 public Atlas(Type type, int width, int height) { 89 this(type, width, height, FLAG_DEFAULTS); 90 } 91 92 /** 93 * Creates a new atlas with the specified algorithm and dimensions 94 * in pixels. A set of flags can also be specified to control the 95 * behavior of the atlas. 96 * 97 * @param type The algorithm to use to pack rectangles in the atlas 98 * @param width The width of the atlas in pixels 99 * @param height The height of the atlas in pixels 100 * @param flags Optional flags to control the behavior of the atlas: 101 * {@link #FLAG_ADD_PADDING}, {@link #FLAG_ALLOW_ROTATIONS} 102 * 103 * @see #Atlas(Atlas.Type, int, int) 104 */ 105 public Atlas(Type type, int width, int height, int flags) { 106 mPolicy = findPolicy(type, width, height, flags); 107 } 108 109 /** 110 * Packs a rectangle of the specified dimensions in this atlas. 111 * 112 * @param width The width of the rectangle to pack in the atlas 113 * @param height The height of the rectangle to pack in the atlas 114 * 115 * @return An {@link Entry} instance if the rectangle was packed in 116 * the atlas, or null if the rectangle could not fit 117 * 118 * @see #pack(int, int, Atlas.Entry) 119 */ 120 public Entry pack(int width, int height) { 121 return pack(width, height, null); 122 } 123 124 /** 125 * Packs a rectangle of the specified dimensions in this atlas. 126 * 127 * @param width The width of the rectangle to pack in the atlas 128 * @param height The height of the rectangle to pack in the atlas 129 * @param entry Out parameter that will be filled in with the location 130 * and attributes of the packed rectangle, can be null 131 * 132 * @return An {@link Entry} instance if the rectangle was packed in 133 * the atlas, or null if the rectangle could not fit 134 * 135 * @see #pack(int, int) 136 */ 137 public Entry pack(int width, int height, Entry entry) { 138 if (entry == null) entry = new Entry(); 139 return mPolicy.pack(width, height, entry); 140 } 141 142 private static Policy findPolicy(Type type, int width, int height, int flags) { 143 switch (type) { 144 case SliceMinArea: 145 return new SlicePolicy(width, height, flags, 146 new SlicePolicy.MinAreaSplitDecision()); 147 case SliceMaxArea: 148 return new SlicePolicy(width, height, flags, 149 new SlicePolicy.MaxAreaSplitDecision()); 150 case SliceShortAxis: 151 return new SlicePolicy(width, height, flags, 152 new SlicePolicy.ShorterFreeAxisSplitDecision()); 153 case SliceLongAxis: 154 return new SlicePolicy(width, height, flags, 155 new SlicePolicy.LongerFreeAxisSplitDecision()); 156 } 157 return null; 158 } 159 160 /** 161 * A policy defines how the atlas performs the packing operation. 162 */ 163 private static abstract class Policy { 164 abstract Entry pack(int width, int height, Entry entry); 165 } 166 167 /** 168 * The Slice algorightm divides the remaining empty space either 169 * horizontally or vertically after a bitmap is placed in the atlas. 170 * 171 * NOTE: the algorithm is explained below using a tree but is 172 * implemented using a linked list instead for performance reasons. 173 * 174 * The algorithm starts with a single empty cell covering the entire 175 * atlas: 176 * 177 * ----------------------- 178 * | | 179 * | | 180 * | | 181 * | Empty space | 182 * | (C0) | 183 * | | 184 * | | 185 * | | 186 * ----------------------- 187 * 188 * The tree of cells looks like this: 189 * 190 * N0(free) 191 * 192 * The algorithm then places a bitmap B1, if possible: 193 * 194 * ----------------------- 195 * | | | 196 * | B1 | | 197 * | | | 198 * |-------- | 199 * | | 200 * | | 201 * | | 202 * | | 203 * ----------------------- 204 * 205 * After placing a bitmap in an empty cell, the algorithm splits 206 * the remaining space in two new empty cells. The split can occur 207 * vertically or horizontally (this is controlled by the "split 208 * decision" parameter of the algorithm.) 209 * 210 * Here is for the instance the result of a vertical split: 211 * 212 * ----------------------- 213 * | | | 214 * | B1 | | 215 * | | | 216 * |--------| C2 | 217 * | | | 218 * | | | 219 * | C1 | | 220 * | | | 221 * ----------------------- 222 * 223 * The cells tree now looks like this: 224 * 225 * C0(occupied) 226 * / \ 227 * / \ 228 * / \ 229 * / \ 230 * C1(free) C2(free) 231 * 232 * For each bitmap to place in the atlas, the Slice algorithm 233 * will visit the free cells until it finds one where a bitmap can 234 * fit. It will then split the now occupied cell and proceed onto 235 * the next bitmap. 236 */ 237 private static class SlicePolicy extends Policy { 238 private final Cell mRoot = new Cell(); 239 240 private final SplitDecision mSplitDecision; 241 242 private final boolean mAllowRotation; 243 private final int mPadding; 244 245 /** 246 * A cell represents a sub-rectangle of the atlas. A cell is 247 * a node in a linked list representing the available free 248 * space in the atlas. 249 */ 250 private static class Cell { 251 int x; 252 int y; 253 254 int width; 255 int height; 256 257 Cell next; 258 259 @Override 260 public String toString() { 261 return String.format("cell[x=%d y=%d width=%d height=%d", x, y, width, height); 262 } 263 } 264 265 SlicePolicy(int width, int height, int flags, SplitDecision splitDecision) { 266 mAllowRotation = (flags & FLAG_ALLOW_ROTATIONS) != 0; 267 mPadding = (flags & FLAG_ADD_PADDING) != 0 ? 1 : 0; 268 269 // The entire atlas is empty at first, minus padding 270 Cell first = new Cell(); 271 first.x = first.y = mPadding; 272 first.width = width - 2 * mPadding; 273 first.height = height - 2 * mPadding; 274 275 mRoot.next = first; 276 mSplitDecision = splitDecision; 277 } 278 279 @Override 280 Entry pack(int width, int height, Entry entry) { 281 Cell cell = mRoot.next; 282 Cell prev = mRoot; 283 284 while (cell != null) { 285 if (insert(cell, prev, width, height, entry)) { 286 return entry; 287 } 288 289 prev = cell; 290 cell = cell.next; 291 } 292 293 return null; 294 } 295 296 /** 297 * Defines how the remaining empty space should be split up: 298 * vertically or horizontally. 299 */ 300 private static interface SplitDecision { 301 /** 302 * Returns true if the remaining space defined by 303 * <code>freeWidth</code> and <code>freeHeight</code> 304 * should be split horizontally. 305 * 306 * @param freeWidth The rectWidth of the free space after packing a rectangle 307 * @param freeHeight The rectHeight of the free space after packing a rectangle 308 * @param rectWidth The rectWidth of the rectangle that was packed in a cell 309 * @param rectHeight The rectHeight of the rectangle that was packed in a cell 310 */ 311 boolean splitHorizontal(int freeWidth, int freeHeight, 312 int rectWidth, int rectHeight); 313 } 314 315 // Splits the free area horizontally to minimize the horizontal section area 316 private static class MinAreaSplitDecision implements SplitDecision { 317 @Override 318 public boolean splitHorizontal(int freeWidth, int freeHeight, 319 int rectWidth, int rectHeight) { 320 return rectWidth * freeHeight > freeWidth * rectHeight; 321 } 322 } 323 324 // Splits the free area horizontally to maximize the horizontal section area 325 private static class MaxAreaSplitDecision implements SplitDecision { 326 @Override 327 public boolean splitHorizontal(int freeWidth, int freeHeight, 328 int rectWidth, int rectHeight) { 329 return rectWidth * freeHeight <= freeWidth * rectHeight; 330 } 331 } 332 333 // Splits the free area horizontally if the horizontal axis is shorter 334 private static class ShorterFreeAxisSplitDecision implements SplitDecision { 335 @Override 336 public boolean splitHorizontal(int freeWidth, int freeHeight, 337 int rectWidth, int rectHeight) { 338 return freeWidth <= freeHeight; 339 } 340 } 341 342 // Splits the free area horizontally if the vertical axis is shorter 343 private static class LongerFreeAxisSplitDecision implements SplitDecision { 344 @Override 345 public boolean splitHorizontal(int freeWidth, int freeHeight, 346 int rectWidth, int rectHeight) { 347 return freeWidth > freeHeight; 348 } 349 } 350 351 /** 352 * Attempts to pack a rectangle of specified dimensions in the available 353 * empty space. 354 * 355 * @param cell The cell representing free space in which to pack the rectangle 356 * @param prev The previous cell in the free space linked list 357 * @param width The width of the rectangle to pack 358 * @param height The height of the rectangle to pack 359 * @param entry Stores the location of the packged rectangle, if it fits 360 * 361 * @return True if the rectangle was packed in the atlas, false otherwise 362 */ 363 @SuppressWarnings("SuspiciousNameCombination") 364 private boolean insert(Cell cell, Cell prev, int width, int height, Entry entry) { 365 boolean rotated = false; 366 367 // If the rectangle doesn't fit we'll try to rotate it 368 // if possible before giving up 369 if (cell.width < width || cell.height < height) { 370 if (mAllowRotation) { 371 if (cell.width < height || cell.height < width) { 372 return false; 373 } 374 375 // Rotate the rectangle 376 int temp = width; 377 width = height; 378 height = temp; 379 rotated = true; 380 } else { 381 return false; 382 } 383 } 384 385 // Remaining free space after packing the rectangle 386 int deltaWidth = cell.width - width; 387 int deltaHeight = cell.height - height; 388 389 // Split the remaining free space into two new cells 390 Cell first = new Cell(); 391 Cell second = new Cell(); 392 393 first.x = cell.x + width + mPadding; 394 first.y = cell.y; 395 first.width = deltaWidth - mPadding; 396 397 second.x = cell.x; 398 second.y = cell.y + height + mPadding; 399 second.height = deltaHeight - mPadding; 400 401 if (mSplitDecision.splitHorizontal(deltaWidth, deltaHeight, 402 width, height)) { 403 first.height = height; 404 second.width = cell.width; 405 } else { 406 first.height = cell.height; 407 second.width = width; 408 409 // The order of the cells matters for efficient packing 410 // We want to give priority to the cell chosen by the 411 // split decision heuristic 412 Cell temp = first; 413 first = second; 414 second = temp; 415 } 416 417 // Remove degenerate cases to keep the free list as small as possible 418 if (first.width > 0 && first.height > 0) { 419 prev.next = first; 420 prev = first; 421 } 422 423 if (second.width > 0 && second.height > 0) { 424 prev.next = second; 425 second.next = cell.next; 426 } else { 427 prev.next = cell.next; 428 } 429 430 // The cell is now completely removed from the free list 431 cell.next = null; 432 433 // Return the location and rotation of the packed rectangle 434 entry.x = cell.x; 435 entry.y = cell.y; 436 entry.rotated = rotated; 437 438 return true; 439 } 440 } 441 } 442
