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

   1 /*
   2  * Copyright (c) 2021 Samsung Electronics Co., Ltd.
   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
  18 // CLASS HEADER
  19 #include "atlas-packer.h"
  20
  21 // EXTERNAL HEADER
  22 #include <dali/integration-api/debug.h>
  23 #include <cstdlib> // For abs()
  24
  25 namespace Dali
  26 {
  27 namespace Toolkit
  28 {
  29 namespace Internal
  30 {
  31 namespace
  32 {
  33 bool ApproximatelyEqual(uint32_t a, uint32_t b)
  34 {
  35   return std::abs(static_cast<int32_t>(a - b)) <= 1;
  36 }
  37
  38 uint16_t MaxDimension(const Uint16Pair& dimensions)
  39 {
  40   return dimensions.GetWidth() >= dimensions.GetHeight() ? dimensions.GetWidth() : dimensions.GetHeight();
  41 }
  42
  43 void Swap(Uint16Pair& first, Uint16Pair& second)
  44 {
  45   Uint16Pair temp = first;
  46   first           = second;
  47   second          = temp;
  48 }
  49
  50 } // namespace
  51
  52 AtlasPacker::Node::Node(Node* parent, SizeType x, SizeType y, SizeType width, SizeType height)
  53 : rectArea(x, y, width, height),
  54   parent(parent),
  55   occupied(false)
  56 {
  57   child[0] = NULL;
  58   child[1] = NULL;
  59 }
  60
  61 AtlasPacker::AtlasPacker(SizeType atlasWidth, SizeType atlasHeight)
  62 : mAvailableArea(atlasWidth * atlasHeight)
  63 {
  64   mRoot = new Node(NULL, 0u, 0u, atlasWidth, atlasHeight);
  65 }
  66
  67 AtlasPacker::~AtlasPacker()
  68 {
  69   DeleteNode(mRoot);
  70 }
  71
  72 bool AtlasPacker::Pack(SizeType blockWidth, SizeType blockHeight, SizeType& packPositionX, SizeType& packPositionY)
  73 {
  74   Node* firstFit = InsertNode(mRoot, blockWidth, blockHeight);
  75   if(firstFit != NULL)
  76   {
  77     firstFit->occupied = true;
  78     packPositionX      = firstFit->rectArea.x;
  79     packPositionY      = firstFit->rectArea.y;
  80     mAvailableArea -= blockWidth * blockHeight;
  81     return true;
  82   }
  83   return false;
  84 }
  85
  86 void AtlasPacker::DeleteBlock(SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight)
  87 {
  88   Node* node = SearchNode(mRoot, packPositionX, packPositionY, blockWidth, blockHeight);
  89   if(node != NULL)
  90   {
  91     mAvailableArea += blockWidth * blockHeight;
  92     MergeToNonOccupied(node);
  93   }
  94 }
  95
  96 unsigned int AtlasPacker::GetAvailableArea() const
  97 {
  98   return mAvailableArea;
  99 }
 100
 101 AtlasPacker::Node* AtlasPacker::InsertNode(Node* root, SizeType blockWidth, SizeType blockHeight)
 102 {
 103   if(root == NULL)
 104   {
 105     return NULL;
 106   }
 107
 108   if(root->occupied)
 109   {
 110     // if not the leaf, then try insert into the first child.
 111     Node* newNode = InsertNode(root->child[0], blockWidth, blockHeight);
 112     if(newNode == NULL) // no room, try insert into the second child.
 113     {
 114       newNode = InsertNode(root->child[1], blockWidth, blockHeight);
 115     }
 116     return newNode;
 117   }
 118
 119   // too small, return
 120   if(root->rectArea.width < blockWidth || root->rectArea.height < blockHeight)
 121   {
 122     return NULL;
 123   }
 124
 125   // right size, accept
 126   if(root->rectArea.width == blockWidth && root->rectArea.height == blockHeight)
 127   {
 128     return root;
 129   }
 130
 131   //too much room, need to split
 132   SplitNode(root, blockWidth, blockHeight);
 133   // insert into the first child created.
 134   return InsertNode(root->child[0], blockWidth, blockHeight);
 135 }
 136
 137 void AtlasPacker::SplitNode(Node* node, SizeType blockWidth, SizeType blockHeight)
 138 {
 139   node->occupied = true;
 140
 141   // decide which way to split
 142   SizeType remainingWidth  = node->rectArea.width - blockWidth;
 143   SizeType remainingHeight = node->rectArea.height - blockHeight;
 144
 145   if(remainingWidth > remainingHeight) // split vertically
 146   {
 147     node->child[0] = new Node(node, node->rectArea.x, node->rectArea.y, blockWidth, node->rectArea.height);
 148     node->child[1] = new Node(node, node->rectArea.x + blockWidth, node->rectArea.y, node->rectArea.width - blockWidth, node->rectArea.height);
 149   }
 150   else // split horizontally
 151   {
 152     node->child[0] = new Node(node, node->rectArea.x, node->rectArea.y, node->rectArea.width, blockHeight);
 153     node->child[1] = new Node(node, node->rectArea.x, node->rectArea.y + blockHeight, node->rectArea.width, node->rectArea.height - blockHeight);
 154   }
 155 }
 156
 157 AtlasPacker::Node* AtlasPacker::SearchNode(Node* node, SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight)
 158 {
 159   if(node != NULL)
 160   {
 161     if(node->child[0] != NULL) //not a leaf
 162     {
 163       Node* newNode = SearchNode(node->child[0], packPositionX, packPositionY, blockWidth, blockHeight);
 164       if(newNode == NULL) // try search from the second child.
 165       {
 166         newNode = SearchNode(node->child[1], packPositionX, packPositionY, blockWidth, blockHeight);
 167       }
 168       return newNode;
 169     }
 170     else if(ApproximatelyEqual(node->rectArea.x, packPositionX) && ApproximatelyEqual(node->rectArea.y, packPositionY) && ApproximatelyEqual(node->rectArea.width, blockWidth) && ApproximatelyEqual(node->rectArea.height, blockHeight))
 171     {
 172       return node;
 173     }
 174   }
 175
 176   return NULL;
 177 }
 178
 179 void AtlasPacker::MergeToNonOccupied(Node* node)
 180 {
 181   node->occupied = false;
 182   Node* parent   = node->parent;
 183   // both child are not occupied, merge the space to parent
 184   if(parent != NULL && parent->child[0]->occupied == false && parent->child[1]->occupied == false)
 185   {
 186     delete parent->child[0];
 187     parent->child[0] = NULL;
 188     delete parent->child[1];
 189     parent->child[1] = NULL;
 190
 191     MergeToNonOccupied(parent);
 192   }
 193 }
 194
 195 void AtlasPacker::DeleteNode(Node* node)
 196 {
 197   if(node != NULL)
 198   {
 199     DeleteNode(node->child[0]);
 200     DeleteNode(node->child[1]);
 201     delete node;
 202   }
 203 }
 204
 205 Uint16Pair AtlasPacker::GroupPack(const Dali::Vector<Uint16Pair>& blockSizes, Dali::Vector<Uint16Pair>& packPositions)
 206 {
 207   uint16_t count = blockSizes.Count();
 208   packPositions.Resize(count);
 209
 210   // Sort the blocks according to its maximum dimension. The bigger blocks are packed first.
 211   Dali::Vector<Uint16Pair> packOrder;
 212   packOrder.Resize(count);
 213   for(uint16_t i = 0; i < count; i++)
 214   {
 215     packOrder[i].SetX(MaxDimension(blockSizes[i]));
 216     packOrder[i].SetY(i);
 217   }
 218   for(uint16_t i = 0; i < count - 1; i++)
 219     for(uint16_t j = 0; j < count - i - 1; j++)
 220     {
 221       if(packOrder[j].GetX() < packOrder[j + 1].GetX())
 222       {
 223         Swap(packOrder[j], packOrder[j + 1]);
 224       }
 225     }
 226
 227   int         index = packOrder[0].GetY();
 228   AtlasPacker packer(blockSizes[index].GetWidth(), blockSizes[index].GetHeight());
 229
 230   SizeType packPositionX, packPositionY;
 231   // pack the blocks one by one with descending size, grows as necessary to accommodate each subsequent block.
 232   for(uint16_t i = 0; i < count; i++)
 233   {
 234     index = packOrder[i].GetY();
 235     packer.GrowPack(blockSizes[index].GetWidth(), blockSizes[index].GetHeight(), packPositionX, packPositionY);
 236     packPositions[index].SetX(packPositionX);
 237     packPositions[index].SetY(packPositionY);
 238   }
 239
 240   return Uint16Pair(packer.mRoot->rectArea.width, packer.mRoot->rectArea.height);
 241 }
 242
 243 void AtlasPacker::GrowPack(SizeType blockWidth, SizeType blockHeight, SizeType& packPositionX, SizeType& packPositionY)
 244 {
 245   Node* firstFit = InsertNode(mRoot, blockWidth, blockHeight);
 246   if(firstFit == NULL)
 247   {
 248     // Could fit in the current left space, grow the partition tree to get more space.
 249     GrowNode(blockWidth, blockHeight);
 250     firstFit = InsertNode(mRoot->child[1], blockWidth, blockHeight);
 251   }
 252
 253   DALI_ASSERT_ALWAYS(firstFit != NULL && "It should never happen!")
 254
 255   firstFit->occupied = true;
 256   packPositionX      = firstFit->rectArea.x;
 257   packPositionY      = firstFit->rectArea.y;
 258 }
 259
 260 void AtlasPacker::GrowNode(SizeType blockWidth, SizeType blockHeight)
 261 {
 262   // Attempts to maintain a roughly square ratio when choosing the growing direction: right or down
 263   bool canGrowRight = blockWidth <= mRoot->rectArea.width;
 264   bool canGrowDown  = blockHeight <= mRoot->rectArea.height;
 265
 266   bool shouldGrowRight = canGrowRight && mRoot->rectArea.height >= mRoot->rectArea.width + blockWidth;
 267   bool shouldGrowDown  = canGrowDown && mRoot->rectArea.width >= mRoot->rectArea.height + blockHeight;
 268
 269   if(canGrowRight && canGrowDown)
 270   {
 271     shouldGrowRight = mRoot->rectArea.width + blockWidth <= mRoot->rectArea.height + blockHeight;
 272     shouldGrowDown  = !shouldGrowRight;
 273   }
 274
 275   if(shouldGrowRight || (canGrowRight && !shouldGrowDown))
 276   {
 277     Node* newRoot     = new Node(NULL, 0u, 0u, mRoot->rectArea.width + blockWidth, mRoot->rectArea.height);
 278     newRoot->occupied = true;
 279     newRoot->child[0] = mRoot;
 280     newRoot->child[1] = new Node(newRoot, mRoot->rectArea.width, 0u, blockWidth, mRoot->rectArea.height);
 281
 282     mRoot = newRoot;
 283   }
 284   else if(shouldGrowDown || (canGrowDown && !shouldGrowRight))
 285   {
 286     Node* newRoot     = new Node(NULL, 0u, 0u, mRoot->rectArea.width, mRoot->rectArea.height + blockHeight);
 287     newRoot->occupied = true;
 288     newRoot->child[0] = mRoot;
 289     newRoot->child[1] = new Node(newRoot, 0u, mRoot->rectArea.height, mRoot->rectArea.width, blockHeight);
 290
 291     mRoot = newRoot;
 292   }
 293   else
 294   {
 295     DALI_LOG_ERROR(" Atlas Packer failed to grow: make sure the packing order is sorted with the block size to avoid this happening");
 296   }
 297 }
 298
 299 } // namespace Internal
 300
 301 } // namespace Toolkit
 302
 303 } // namespace Dali