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