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) 2021 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 <dali/public-api/common/dali-vector.h>
  21 #include <dali/public-api/math/rect.h>
  22 #include <dali/public-api/math/uint-16-pair.h>
  23 #include <stdint.h>
  24
  25 namespace Dali
  26 {
  27 namespace Toolkit
  28 {
  29 namespace Internal
  30 {
  31 /**
  32  * Binary space tree based bin packing algorithm.
  33  * It is initialised with a fixed width and height and will fit each block into the first node where it fits
  34  * and then split that node into 2 parts (down and right) to track the remaining empty space.
  35  */
  36 class AtlasPacker
  37 {
  38 public:
  39   /**
  40    * rectangular area (x,y,width,height)
  41    */
  42   typedef uint32_t       SizeType;
  43   typedef Rect<SizeType> RectArea;
  44
  45   /**
  46    * Tree node.
  47    */
  48   struct Node
  49   {
  50     Node(Node* parent, SizeType x, SizeType y, SizeType width, SizeType height);
  51
  52     RectArea rectArea;
  53     Node*    parent;
  54     Node*    child[2];
  55     bool     occupied;
  56   };
  57
  58   /**
  59    * Constructor.
  60    *
  61    * @param[in] atlasWidth The width of the atlas.
  62    * @param[in] atlasHeight The height of the atlas.
  63    */
  64   AtlasPacker(SizeType atlasWidth, SizeType atlasHeight);
  65
  66   /**
  67    * Destructor
  68    */
  69   ~AtlasPacker();
  70
  71   /**
  72    * Pack a block into the atlas.
  73    *
  74    * @param[in] blockWidth The width of the block to pack.
  75    * @param[in] blockHeight The height of the block to pack.
  76    * @param[out] packPositionX The x coordinate of the position to pack the block.
  77    * @param[out] packPositionY The y coordinate of the position to pack the block.
  78    * @return True if there are room for this block, false otherwise.
  79    */
  80   bool Pack(SizeType blockWidth, SizeType blockHeight, SizeType& packPositionX, SizeType& packPositionY);
  81
  82   /**
  83    * Delete the block.
  84    *
  85    * @param[in] packPositionX The x coordinate of the pack position.
  86    * @param[in] packPositionY The y coordinate of the pack position.
  87    * @param[in] blockWidth The width of the block to delete.
  88    * @param[in] blockHeight The height of the block to delete.
  89    */
  90   void DeleteBlock(SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight);
  91
  92   /**
  93    * Query how much empty space left.
  94    *
  95    * @return The area available for packing.
  96    */
  97   unsigned int GetAvailableArea() const;
  98
  99   /**
 100    * Pack a group of blocks with different sizes, calculate the required packing size and the position of each block.
 101    * @param[in] blockSizes The size list of the blocks .
 102    * @param[out] packPositions The packing position of each block.
 103    * @return The required size to accommodate all the blocks.
 104    */
 105   static Uint16Pair GroupPack(const Dali::Vector<Uint16Pair>& blockSizes, Dali::Vector<Uint16Pair>& packPositions);
 106
 107 private:
 108   /*
 109    * Search the node which can pack the block with given size.
 110    *
 111    * @param[in] root The root node of the subtree to be searched.
 112    * @param[in] blockWidth The width of the block to pack.
 113    * @param[in] blockHeight The height of the block to pack.
 114    * @return The poniter pointing to node that can pack the block.
 115    *          If it is NULL, there are no room in the subtree to pack the block.
 116    */
 117   Node* InsertNode(Node* root, SizeType blockWidth, SizeType blockHeight);
 118
 119   /**
 120    * Split the node into two to fit the block width/size.
 121    *
 122    * @parm[in] node The node to split.
 123    * @param[in] blockWidth The width of the block to pack.
 124    * @param[in] blockHeight The height of the block to pack.
 125    */
 126   void SplitNode(Node* node, SizeType blockWidth, SizeType blockHeight);
 127
 128   /**
 129    * Search the node at the given position and with the given size.
 130
 131    * @param[in] node The root node of the subtree to be searched.
 132    * @param[in] packPositionX The x coordinate of the pack position.
 133    * @param[in] packPositionY The y coordinate of the pack position.
 134    * @param[in] blockWidth The width of the block.
 135    * @param[in] blockHeight The height of the block.
 136    */
 137   Node* SearchNode(Node* node, SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight);
 138
 139   /**
 140    * Merge the rect of the node to non-occupied area.
 141    *
 142    * @param[in] node The node to me merged to the non-occupied area
 143    */
 144   void MergeToNonOccupied(Node* node);
 145
 146   /**
 147    * Delete a node and its subtree.
 148    *
 149    * @parm[in] node The node to delete.
 150    */
 151   void DeleteNode(Node* node);
 152
 153   /**
 154    * Pack a block into the atlas. If there is no enough room, grow the partition tree.
 155    *
 156    * @param[in] blockWidth The width of the block to pack.
 157    * @param[in] blockHeight The height of the block to pack.
 158    * @param[out] packPositionX The x coordinate of the position to pack the block.
 159    * @param[out] packPositionY The y coordinate of the position to pack the block.
 160    */
 161   void GrowPack(SizeType blockWidth, SizeType blockHeight, SizeType& packPositionX, SizeType& packPositionY);
 162
 163   /**
 164    * Add extra node into the partition tree to accommodate the given block.
 165    *
 166    * @param[in] blockWidth The width of the block to pack.
 167    * @param[in] blockHeight The height of the block to pack.
 168    */
 169   void GrowNode(SizeType blockWidth, SizeType blockHeight);
 170
 171   // Undefined
 172   AtlasPacker(const AtlasPacker& atlasPacker);
 173
 174   // Undefined
 175   AtlasPacker& operator=(const AtlasPacker& atlasPacker);
 176
 177 private:
 178   Node*        mRoot; ///< The root of the binary space tree
 179   unsigned int mAvailableArea;
 180 };
 181
 182 } // namespace Internal
 183
 184 } // namespace Toolkit
 185
 186 } // namespace Dali
 187
 188 #endif // DALI_TOOLKIT_ATLAS_PACKER_H