dali-toolkit/internal/image-loader/atlas-packer.h

   1 #ifndef __DALI_TOOLKIT_ATLAS_PACKER_H__
   2 #define __DALI_TOOLKIT_ATLAS_PACKER_H__
   3
   4 /*
   5  * Copyright (c) 2015 Samsung Electronics Co., Ltd.
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  * http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 #include <stdint.h>
  21 #include <dali/public-api/common/dali-vector.h>
  22 #include <dali/public-api/math/rect.h>
  23 #include <dali/public-api/math/uint-16-pair.h>
  24
  25 namespace Dali
  26 {
  27
  28 namespace Toolkit
  29 {
  30
  31 namespace Internal
  32 {
  33
  34 /**
  35  * Binary space tree based bin packing algorithm.
  36  * It is initialised with a fixed width and height and will fit each block into the first node where it fits
  37  * and then split that node into 2 parts (down and right) to track the remaining empty space.
  38  */
  39 class AtlasPacker
  40 {
  41 public:
  42
  43   /**
  44    * rectangular area (x,y,width,height)
  45    */
  46   typedef uint32_t SizeType;
  47   typedef Rect<SizeType> RectArea;
  48
  49   /**
  50    * Tree node.
  51    */
  52   struct Node
  53   {
  54     Node( Node* parent, SizeType x, SizeType y, SizeType width, SizeType height );
  55
  56     RectArea rectArea;
  57     Node* parent;
  58     Node* child[2];
  59     bool occupied;
  60   };
  61
  62   /**
  63    * Constructor.
  64    *
  65    * @param[in] atlasWidth The width of the atlas.
  66    * @param[in] atlasHeight The height of the atlas.
  67    */
  68   AtlasPacker( SizeType atlasWidth, SizeType atlasHeight );
  69
  70   /**
  71    * Destructor
  72    */
  73   ~AtlasPacker();
  74
  75   /**
  76    * Pack a block into the atlas.
  77    *
  78    * @param[in] blockWidth The width of the block to pack.
  79    * @param[in] blockHeight The height of the block to pack.
  80    * @param[out] packPositionX The x coordinate of the position to pack the block.
  81    * @param[out] packPositionY The y coordinate of the position to pack the block.
  82    * @return True if there are room for this block, false otherwise.
  83    */
  84   bool Pack( SizeType blockWidth, SizeType blockHeight,
  85              SizeType& packPositionX, SizeType& packPositionY);
  86
  87   /**
  88    * Delete the block.
  89    *
  90    * @param[in] packPositionX The x coordinate of the pack position.
  91    * @param[in] packPositionY The y coordinate of the pack position.
  92    * @param[in] blockWidth The width of the block to delete.
  93    * @param[in] blockHeight The height of the block to delete.
  94    */
  95   void DeleteBlock( SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight );
  96
  97   /**
  98    * Query how much empty space left.
  99    *
 100    * @return The area available for packing.
 101    */
 102   unsigned int GetAvailableArea() const;
 103
 104   /**
 105    * Pack a group of blocks with different sizes, calculate the required packing size and the position of each block.
 106    * @param[in] blockSizes The size list of the blocks .
 107    * @param[out] packPositions The packing position of each block.
 108    * @return The required size to accommodate all the blocks.
 109    */
 110   static Uint16Pair GroupPack( const Dali::Vector<Uint16Pair>& blockSizes, Dali::Vector<Uint16Pair>& packPositions );
 111
 112 private:
 113
 114   /*
 115    * Search the node which can pack the block with given size.
 116    *
 117    * @param[in] root The root node of the subtree to be searched.
 118    * @param[in] blockWidth The width of the block to pack.
 119    * @param[in] blockHeight The height of the block to pack.
 120    * @return The poniter pointing to node that can pack the block.
 121    *          If it is NULL, there are no room in the subtree to pack the block.
 122    */
 123   Node* InsertNode( Node* root, SizeType blockWidth, SizeType blockHeight );
 124
 125   /**
 126    * Split the node into two to fit the block width/size.
 127    *
 128    * @parm[in] node The node to split.
 129    * @param[in] blockWidth The width of the block to pack.
 130    * @param[in] blockHeight The height of the block to pack.
 131    */
 132   void SplitNode( Node* node, SizeType blockWidth, SizeType blockHeight );
 133
 134   /**
 135    * Search the node at the given position and with the given size.
 136
 137    * @param[in] node The root node of the subtree to be searched.
 138    * @param[in] packPositionX The x coordinate of the pack position.
 139    * @param[in] packPositionY The y coordinate of the pack position.
 140    * @param[in] blockWidth The width of the block.
 141    * @param[in] blockHeight The height of the block.
 142    */
 143   Node* SearchNode( Node* node, SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight  );
 144
 145   /**
 146    * Merge the rect of the node to non-occupied area.
 147    *
 148    * @param[in] node The node to me merged to the non-occupied area
 149    */
 150   void MergeToNonOccupied( Node* node );
 151
 152   /**
 153    * Delete a node and its subtree.
 154    *
 155    * @parm[in] node The node to delete.
 156    */
 157   void DeleteNode( Node* node );
 158
 159   /**
 160    * Pack a block into the atlas. If there is no enough room, grow the partition tree.
 161    *
 162    * @param[in] blockWidth The width of the block to pack.
 163    * @param[in] blockHeight The height of the block to pack.
 164    * @param[out] packPositionX The x coordinate of the position to pack the block.
 165    * @param[out] packPositionY The y coordinate of the position to pack the block.
 166    */
 167   void GrowPack( SizeType blockWidth, SizeType blockHeight,
 168                  SizeType& packPositionX, SizeType& packPositionY );
 169
 170   /**
 171    * Add extra node into the partition tree to accommodate the given block.
 172    *
 173    * @param[in] blockWidth The width of the block to pack.
 174    * @param[in] blockHeight The height of the block to pack.
 175    */
 176   void GrowNode( SizeType blockWidth, SizeType blockHeight );
 177
 178   // Undefined
 179   AtlasPacker( const AtlasPacker& atlasPacker);
 180
 181   // Undefined
 182   AtlasPacker& operator=( const AtlasPacker& atlasPacker );
 183
 184 private:
 185
 186   Node* mRoot; ///< The root of the binary space tree
 187   unsigned int mAvailableArea;
 188
 189 };
 190
 191
 192 } // namespace Internal
 193
 194 } // namespace Toolkit
 195
 196 } // namespace Dali
 197
 198 #endif /* __DALI_TOOLKIT_ATLAS_PACKER_H__ */