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

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