13b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy/* 23b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Copyright (C) 2013 The Android Open Source Project 33b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 43b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Licensed under the Apache License, Version 2.0 (the "License"); 53b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * you may not use this file except in compliance with the License. 63b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * You may obtain a copy of the License at 73b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 83b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * http://www.apache.org/licenses/LICENSE-2.0 93b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 103b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Unless required by applicable law or agreed to in writing, software 113b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * distributed under the License is distributed on an "AS IS" BASIS, 123b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 133b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * See the License for the specific language governing permissions and 143b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * limitations under the License. 153b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 163b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 173b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guypackage android.graphics; 183b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 193b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy/** 203b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @hide 213b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 223b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guypublic class Atlas { 233b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 24a039182d6157bc0487df4ad8e373685c9dd7d662John Reck * WARNING: These flag values are part of the on-disk configuration information, 25a039182d6157bc0487df4ad8e373685c9dd7d662John Reck * do not change their values. 263b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 27a039182d6157bc0487df4ad8e373685c9dd7d662John Reck 28a039182d6157bc0487df4ad8e373685c9dd7d662John Reck /** DELETED: FLAG_ROTATION = 0x01 */ 29a039182d6157bc0487df4ad8e373685c9dd7d662John Reck 303b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 313b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * This flag indicates whether the packing algorithm should leave 323b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * an empty 1 pixel wide border around each bitmap. This border can 333b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * be useful if the content of the atlas will be used in OpenGL using 343b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * bilinear filtering. 353b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 363b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public static final int FLAG_ADD_PADDING = 0x2; 373b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 383b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Default flags: allow rotations and add padding. 393b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 403b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public static final int FLAG_DEFAULTS = FLAG_ADD_PADDING; 413b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 423b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 433b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Each type defines a different packing algorithm that can 443b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * be used by an {@link Atlas}. The best algorithm to use 453b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * will depend on the source dataset and the dimensions of 463b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * the atlas. 473b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 483b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public enum Type { 493b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy SliceMinArea, 503b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy SliceMaxArea, 513b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy SliceShortAxis, 523b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy SliceLongAxis 533b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 543b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 553b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 563b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Represents a bitmap packed in the atlas. Each entry has a location in 57a039182d6157bc0487df4ad8e373685c9dd7d662John Reck * pixels in the atlas and a rotation flag. 583b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 593b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public static class Entry { 603b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 613b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Location, in pixels, of the bitmap on the X axis in the atlas. 623b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 633b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public int x; 643b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 653b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Location, in pixels, of the bitmap on the Y axis in the atlas. 663b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 673b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public int y; 683b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 693b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 703b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private final Policy mPolicy; 713b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 723b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 733b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Creates a new atlas with the specified algorithm and dimensions 743b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * in pixels. Calling this constructor is equivalent to calling 753b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * {@link #Atlas(Atlas.Type, int, int, int)} with {@link #FLAG_DEFAULTS}. 763b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 773b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param type The algorithm to use to pack rectangles in the atlas 783b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param width The width of the atlas in pixels 793b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param height The height of the atlas in pixels 803b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 813b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @see #Atlas(Atlas.Type, int, int, int) 823b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 833b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public Atlas(Type type, int width, int height) { 843b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy this(type, width, height, FLAG_DEFAULTS); 853b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 863b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 873b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 883b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Creates a new atlas with the specified algorithm and dimensions 893b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * in pixels. A set of flags can also be specified to control the 903b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * behavior of the atlas. 913b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 923b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param type The algorithm to use to pack rectangles in the atlas 933b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param width The width of the atlas in pixels 943b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param height The height of the atlas in pixels 953b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param flags Optional flags to control the behavior of the atlas: 963b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * {@link #FLAG_ADD_PADDING}, {@link #FLAG_ALLOW_ROTATIONS} 973b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 983b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @see #Atlas(Atlas.Type, int, int) 993b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 1003b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public Atlas(Type type, int width, int height, int flags) { 1013b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy mPolicy = findPolicy(type, width, height, flags); 1023b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 1033b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 1043b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 1053b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Packs a rectangle of the specified dimensions in this atlas. 1063b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1073b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param width The width of the rectangle to pack in the atlas 1083b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param height The height of the rectangle to pack in the atlas 1093b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1103b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @return An {@link Entry} instance if the rectangle was packed in 1113b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * the atlas, or null if the rectangle could not fit 1123b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1133b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @see #pack(int, int, Atlas.Entry) 1143b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 1153b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public Entry pack(int width, int height) { 1163b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return pack(width, height, null); 1173b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 1183b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 1193b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 1203b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Packs a rectangle of the specified dimensions in this atlas. 1213b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1223b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param width The width of the rectangle to pack in the atlas 1233b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param height The height of the rectangle to pack in the atlas 1243b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param entry Out parameter that will be filled in with the location 1253b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * and attributes of the packed rectangle, can be null 1263b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1273b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @return An {@link Entry} instance if the rectangle was packed in 1283b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * the atlas, or null if the rectangle could not fit 1293b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1303b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @see #pack(int, int) 1313b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 1323b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public Entry pack(int width, int height, Entry entry) { 1333b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy if (entry == null) entry = new Entry(); 1343b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return mPolicy.pack(width, height, entry); 1353b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 1363b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 1373b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private static Policy findPolicy(Type type, int width, int height, int flags) { 1383b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy switch (type) { 1393b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy case SliceMinArea: 1403b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return new SlicePolicy(width, height, flags, 1413b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy new SlicePolicy.MinAreaSplitDecision()); 1423b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy case SliceMaxArea: 1433b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return new SlicePolicy(width, height, flags, 1443b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy new SlicePolicy.MaxAreaSplitDecision()); 1453b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy case SliceShortAxis: 1463b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return new SlicePolicy(width, height, flags, 1473b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy new SlicePolicy.ShorterFreeAxisSplitDecision()); 1483b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy case SliceLongAxis: 1493b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return new SlicePolicy(width, height, flags, 1503b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy new SlicePolicy.LongerFreeAxisSplitDecision()); 1513b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 1523b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return null; 1533b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 1543b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 1553b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 1563b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * A policy defines how the atlas performs the packing operation. 1573b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 1583b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private static abstract class Policy { 1593b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy abstract Entry pack(int width, int height, Entry entry); 1603b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 1613b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 1623b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 1633b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * The Slice algorightm divides the remaining empty space either 1643b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * horizontally or vertically after a bitmap is placed in the atlas. 1653b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1663b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * NOTE: the algorithm is explained below using a tree but is 1673b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * implemented using a linked list instead for performance reasons. 1683b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1693b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * The algorithm starts with a single empty cell covering the entire 1703b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * atlas: 1713b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1723b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * ----------------------- 1733b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | 1743b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | 1753b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | 1763b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | Empty space | 1773b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | (C0) | 1783b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | 1793b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | 1803b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | 1813b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * ----------------------- 1823b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1833b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * The tree of cells looks like this: 1843b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1853b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * N0(free) 1863b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1873b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * The algorithm then places a bitmap B1, if possible: 1883b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 1893b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * ----------------------- 1903b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | | 1913b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | B1 | | 1923b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | | 1933b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * |-------- | 1943b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | 1953b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | 1963b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | 1973b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | 1983b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * ----------------------- 1993b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 2003b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * After placing a bitmap in an empty cell, the algorithm splits 2013b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * the remaining space in two new empty cells. The split can occur 2023b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * vertically or horizontally (this is controlled by the "split 2033b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * decision" parameter of the algorithm.) 2043b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 2053b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Here is for the instance the result of a vertical split: 2063b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 2073b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * ----------------------- 2083b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | | 2093b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | B1 | | 2103b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | | 2113b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * |--------| C2 | 2123b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | | 2133b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | | 2143b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | C1 | | 2153b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * | | | 2163b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * ----------------------- 2173b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 2183b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * The cells tree now looks like this: 2193b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 2203b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * C0(occupied) 2213b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * / \ 2223b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * / \ 2233b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * / \ 2243b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * / \ 2253b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * C1(free) C2(free) 2263b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 2273b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * For each bitmap to place in the atlas, the Slice algorithm 2283b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * will visit the free cells until it finds one where a bitmap can 2293b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * fit. It will then split the now occupied cell and proceed onto 2303b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * the next bitmap. 2313b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 2323b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private static class SlicePolicy extends Policy { 2333b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private final Cell mRoot = new Cell(); 2343b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2353b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private final SplitDecision mSplitDecision; 2363b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2373b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private final int mPadding; 2383b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2393b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 2403b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * A cell represents a sub-rectangle of the atlas. A cell is 2413b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * a node in a linked list representing the available free 2423b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * space in the atlas. 2433b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 2443b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private static class Cell { 2453b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy int x; 2463b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy int y; 2473b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2483b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy int width; 2493b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy int height; 2503b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2513b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy Cell next; 2523b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2533b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy @Override 2543b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public String toString() { 2553b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return String.format("cell[x=%d y=%d width=%d height=%d", x, y, width, height); 2563b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 2573b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 2583b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2593b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy SlicePolicy(int width, int height, int flags, SplitDecision splitDecision) { 2603b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy mPadding = (flags & FLAG_ADD_PADDING) != 0 ? 1 : 0; 2613b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2623b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // The entire atlas is empty at first, minus padding 2633b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy Cell first = new Cell(); 2643b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy first.x = first.y = mPadding; 2653b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy first.width = width - 2 * mPadding; 2663b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy first.height = height - 2 * mPadding; 2673b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2683b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy mRoot.next = first; 2693b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy mSplitDecision = splitDecision; 2703b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 2713b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2723b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy @Override 2733b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy Entry pack(int width, int height, Entry entry) { 2743b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy Cell cell = mRoot.next; 2753b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy Cell prev = mRoot; 2763b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2773b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy while (cell != null) { 2783b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy if (insert(cell, prev, width, height, entry)) { 2793b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return entry; 2803b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 2813b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2823b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy prev = cell; 2833b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy cell = cell.next; 2843b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 2853b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2863b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return null; 2873b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 2883b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 2893b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 2903b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Defines how the remaining empty space should be split up: 2913b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * vertically or horizontally. 2923b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 2933b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private static interface SplitDecision { 2943b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 2953b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Returns true if the remaining space defined by 2963b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * <code>freeWidth</code> and <code>freeHeight</code> 2973b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * should be split horizontally. 2983b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 2993b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param freeWidth The rectWidth of the free space after packing a rectangle 3003b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param freeHeight The rectHeight of the free space after packing a rectangle 3013b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param rectWidth The rectWidth of the rectangle that was packed in a cell 3023b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param rectHeight The rectHeight of the rectangle that was packed in a cell 3033b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 3043b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy boolean splitHorizontal(int freeWidth, int freeHeight, 3053b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy int rectWidth, int rectHeight); 3063b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3073b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3083b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // Splits the free area horizontally to minimize the horizontal section area 3093b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private static class MinAreaSplitDecision implements SplitDecision { 3103b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy @Override 3113b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public boolean splitHorizontal(int freeWidth, int freeHeight, 3123b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy int rectWidth, int rectHeight) { 3133b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return rectWidth * freeHeight > freeWidth * rectHeight; 3143b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3153b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3163b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3173b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // Splits the free area horizontally to maximize the horizontal section area 3183b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private static class MaxAreaSplitDecision implements SplitDecision { 3193b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy @Override 3203b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public boolean splitHorizontal(int freeWidth, int freeHeight, 3213b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy int rectWidth, int rectHeight) { 3223b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return rectWidth * freeHeight <= freeWidth * rectHeight; 3233b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3243b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3253b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3263b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // Splits the free area horizontally if the horizontal axis is shorter 3273b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private static class ShorterFreeAxisSplitDecision implements SplitDecision { 3283b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy @Override 3293b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public boolean splitHorizontal(int freeWidth, int freeHeight, 3303b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy int rectWidth, int rectHeight) { 3313b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return freeWidth <= freeHeight; 3323b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3333b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3343b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3353b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // Splits the free area horizontally if the vertical axis is shorter 3363b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private static class LongerFreeAxisSplitDecision implements SplitDecision { 3373b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy @Override 3383b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy public boolean splitHorizontal(int freeWidth, int freeHeight, 3393b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy int rectWidth, int rectHeight) { 3403b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return freeWidth > freeHeight; 3413b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3423b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3433b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3443b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy /** 3453b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * Attempts to pack a rectangle of specified dimensions in the available 3463b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * empty space. 3473b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 3483b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param cell The cell representing free space in which to pack the rectangle 3493b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param prev The previous cell in the free space linked list 3503b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param width The width of the rectangle to pack 3513b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param height The height of the rectangle to pack 3523b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @param entry Stores the location of the packged rectangle, if it fits 3533b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * 3543b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy * @return True if the rectangle was packed in the atlas, false otherwise 3553b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy */ 3563b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy private boolean insert(Cell cell, Cell prev, int width, int height, Entry entry) { 3573b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy if (cell.width < width || cell.height < height) { 358a039182d6157bc0487df4ad8e373685c9dd7d662John Reck return false; 3593b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3603b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3613b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // Remaining free space after packing the rectangle 3623b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy int deltaWidth = cell.width - width; 3633b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy int deltaHeight = cell.height - height; 3643b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3653b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // Split the remaining free space into two new cells 3663b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy Cell first = new Cell(); 3673b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy Cell second = new Cell(); 3683b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3693b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy first.x = cell.x + width + mPadding; 3703b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy first.y = cell.y; 3713b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy first.width = deltaWidth - mPadding; 3723b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3733b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy second.x = cell.x; 3743b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy second.y = cell.y + height + mPadding; 3753b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy second.height = deltaHeight - mPadding; 3763b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3773b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy if (mSplitDecision.splitHorizontal(deltaWidth, deltaHeight, 3783b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy width, height)) { 3793b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy first.height = height; 3803b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy second.width = cell.width; 3813b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } else { 3823b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy first.height = cell.height; 3833b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy second.width = width; 3843b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3853b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // The order of the cells matters for efficient packing 3863b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // We want to give priority to the cell chosen by the 3873b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // split decision heuristic 3883b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy Cell temp = first; 3893b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy first = second; 3903b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy second = temp; 3913b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3923b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3933b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // Remove degenerate cases to keep the free list as small as possible 3943b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy if (first.width > 0 && first.height > 0) { 3953b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy prev.next = first; 3963b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy prev = first; 3973b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 3983b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 3993b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy if (second.width > 0 && second.height > 0) { 4003b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy prev.next = second; 4013b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy second.next = cell.next; 4023b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } else { 4033b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy prev.next = cell.next; 4043b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 4053b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 4063b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // The cell is now completely removed from the free list 4073b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy cell.next = null; 4083b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 4093b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy // Return the location and rotation of the packed rectangle 4103b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy entry.x = cell.x; 4113b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy entry.y = cell.y; 4123b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy 4133b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy return true; 4143b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 4153b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy } 4163b748a44c6bd2ea05fe16839caf73dbe50bd7ae9Romain Guy} 417