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
  24 namespace Dali
  25 {
  26
  27 namespace Toolkit
  28 {
  29
  30 namespace Internal
  31 {
  32
  33 namespace
  34 {
  35
  36 bool ApproximatelyEqual( uint32_t a, uint32_t b  )
  37 {
  38   return abs( a-b ) <= 1;
  39 }
  40
  41 }
  42
  43 AtlasPacker::Node::Node( Node* parent, SizeType x, SizeType y, SizeType width, SizeType height  )
  44 : rectArea( x, y, width, height ),
  45   parent(parent),
  46   occupied( false )
  47 {
  48   child[0] = NULL;
  49   child[1] = NULL;
  50 }
  51
  52 AtlasPacker:: AtlasPacker( SizeType atlasWidth, SizeType atlasHeight )
  53 : mAvailableArea( atlasWidth * atlasHeight )
  54 {
  55   mRoot = new Node( NULL, 0u, 0u, atlasWidth, atlasHeight );
  56 }
  57
  58 AtlasPacker::~AtlasPacker()
  59 {
  60   DeleteNode( mRoot );
  61 }
  62
  63 bool AtlasPacker::Pack( SizeType blockWidth, SizeType blockHeight,
  64                         SizeType& packPositionX, SizeType& packPositionY)
  65 {
  66   Node* firstFit = InsertNode( mRoot, blockWidth, blockHeight );
  67   if( firstFit != NULL )
  68   {
  69     firstFit->occupied = true;
  70     packPositionX = firstFit->rectArea.x;
  71     packPositionY = firstFit->rectArea.y;
  72     mAvailableArea -= blockWidth*blockHeight;
  73     return true;
  74   }
  75   return false;
  76 }
  77
  78 void AtlasPacker::DeleteBlock( SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight )
  79 {
  80   Node* node =  SearchNode( mRoot, packPositionX, packPositionY, blockWidth, blockHeight  );
  81   if( node != NULL )
  82   {
  83     mAvailableArea += blockWidth*blockHeight;
  84     MergeToNonOccupied( node );
  85   }
  86 }
  87
  88 unsigned int AtlasPacker::GetAvailableArea() const
  89 {
  90   return mAvailableArea;
  91 }
  92
  93 AtlasPacker::Node* AtlasPacker::InsertNode( Node* root, SizeType blockWidth, SizeType blockHeight )
  94 {
  95   if( root == NULL )
  96   {
  97     return NULL;
  98   }
  99
 100   if( root->occupied )
 101   {
 102     // if not the leaf, then try insert into the first child.
 103     Node* newNode = InsertNode(root->child[0], blockWidth, blockHeight);
 104     if( newNode == NULL )// no room, try insert into the second child.
 105     {
 106       newNode = InsertNode(root->child[1], blockWidth, blockHeight);
 107     }
 108     return newNode;
 109   }
 110
 111   // too small, return
 112   if( root->rectArea.width < blockWidth || root->rectArea.height < blockHeight )
 113   {
 114     return NULL;
 115   }
 116
 117   // right size, accept
 118   if( root->rectArea.width == blockWidth && root->rectArea.height == blockHeight )
 119   {
 120     return root;
 121   }
 122
 123   //too much room, need to split
 124   SplitNode( root, blockWidth, blockHeight );
 125   // insert into the first child created.
 126   return InsertNode( root->child[0], blockWidth, blockHeight);
 127 }
 128
 129 void AtlasPacker::SplitNode( Node* node, SizeType blockWidth, SizeType blockHeight )
 130 {
 131   node->occupied = true;
 132
 133   // decide which way to split
 134   SizeType remainingWidth = node->rectArea.width - blockWidth;
 135   SizeType remainingHeight = node->rectArea.height - blockHeight;
 136
 137   if( remainingWidth > remainingHeight ) // split vertically
 138   {
 139     node->child[0] = new Node( node, node->rectArea.x, node->rectArea.y, blockWidth, node->rectArea.height  );
 140     node->child[1] = new Node( node, node->rectArea.x+blockWidth, node->rectArea.y, node->rectArea.width-blockWidth, node->rectArea.height );
 141   }
 142   else // split horizontally
 143   {
 144     node->child[0] = new Node( node, node->rectArea.x, node->rectArea.y, node->rectArea.width, blockHeight  );
 145     node->child[1] = new Node( node, node->rectArea.x, node->rectArea.y+blockHeight, node->rectArea.width, node->rectArea.height-blockHeight );
 146   }
 147 }
 148
 149 AtlasPacker::Node* AtlasPacker::SearchNode( Node* node, SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight  )
 150 {
 151   if( node != NULL )
 152   {
 153     if( node->child[0] != NULL) //not a leaf
 154     {
 155       Node* newNode = SearchNode(node->child[0], packPositionX, packPositionY, blockWidth, blockHeight);
 156       if( newNode == NULL )// try search from the second child.
 157       {
 158         newNode = SearchNode(node->child[1], packPositionX, packPositionY, blockWidth, blockHeight);
 159       }
 160       return newNode;
 161     }
 162     else if( ApproximatelyEqual(node->rectArea.x, packPositionX) && ApproximatelyEqual(node->rectArea.y, packPositionY )
 163         && ApproximatelyEqual(node->rectArea.width, blockWidth) && ApproximatelyEqual( node->rectArea.height, blockHeight) )
 164     {
 165       return node;
 166     }
 167   }
 168
 169   return NULL;
 170 }
 171
 172 void AtlasPacker::MergeToNonOccupied( Node* node )
 173 {
 174   node->occupied = false;
 175   Node* parent = node->parent;
 176   // both child are not occupied, merge the space to parent
 177   if( parent != NULL && parent->child[0]->occupied == false && parent->child[1]->occupied == false)
 178   {
 179     delete parent->child[0];
 180     parent->child[0] = NULL;
 181     delete parent->child[1];
 182     parent->child[1] = NULL;
 183
 184     MergeToNonOccupied( parent );
 185   }
 186 }
 187
 188 void AtlasPacker::DeleteNode( Node *node )
 189 {
 190   if( node != NULL )
 191   {
 192     DeleteNode( node->child[0] );
 193     DeleteNode( node->child[1] );
 194     delete node;
 195   }
 196 }
 197
 198 } // namespace Internal
 199
 200 } // namespace Toolkit
 201
 202 } // namespace Dali