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