2 * Copyright (c) 2016 Samsung Electronics Co., Ltd.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 #include "atlas-packer.h"
22 #include <stdlib.h> // For abs()
23 #include <dali/integration-api/debug.h>
37 bool ApproximatelyEqual( uint32_t a, uint32_t b )
39 return abs( a-b ) <= 1;
42 uint16_t MaxDimension( const Uint16Pair& dimensions )
44 return dimensions.GetWidth() >= dimensions.GetHeight() ? dimensions.GetWidth() : dimensions.GetHeight();
47 void Swap( Uint16Pair& first, Uint16Pair& second )
49 Uint16Pair temp = first;
56 AtlasPacker::Node::Node( Node* parent, SizeType x, SizeType y, SizeType width, SizeType height )
57 : rectArea( x, y, width, height ),
65 AtlasPacker:: AtlasPacker( SizeType atlasWidth, SizeType atlasHeight )
66 : mAvailableArea( atlasWidth * atlasHeight )
68 mRoot = new Node( NULL, 0u, 0u, atlasWidth, atlasHeight );
71 AtlasPacker::~AtlasPacker()
76 bool AtlasPacker::Pack( SizeType blockWidth, SizeType blockHeight,
77 SizeType& packPositionX, SizeType& packPositionY)
79 Node* firstFit = InsertNode( mRoot, blockWidth, blockHeight );
80 if( firstFit != NULL )
82 firstFit->occupied = true;
83 packPositionX = firstFit->rectArea.x;
84 packPositionY = firstFit->rectArea.y;
85 mAvailableArea -= blockWidth*blockHeight;
91 void AtlasPacker::DeleteBlock( SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight )
93 Node* node = SearchNode( mRoot, packPositionX, packPositionY, blockWidth, blockHeight );
96 mAvailableArea += blockWidth*blockHeight;
97 MergeToNonOccupied( node );
101 unsigned int AtlasPacker::GetAvailableArea() const
103 return mAvailableArea;
106 AtlasPacker::Node* AtlasPacker::InsertNode( Node* root, SizeType blockWidth, SizeType blockHeight )
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.
119 newNode = InsertNode(root->child[1], blockWidth, blockHeight);
125 if( root->rectArea.width < blockWidth || root->rectArea.height < blockHeight )
130 // right size, accept
131 if( root->rectArea.width == blockWidth && root->rectArea.height == blockHeight )
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);
142 void AtlasPacker::SplitNode( Node* node, SizeType blockWidth, SizeType blockHeight )
144 node->occupied = true;
146 // decide which way to split
147 SizeType remainingWidth = node->rectArea.width - blockWidth;
148 SizeType remainingHeight = node->rectArea.height - blockHeight;
150 if( remainingWidth > remainingHeight ) // split vertically
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 );
155 else // split horizontally
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 );
162 AtlasPacker::Node* AtlasPacker::SearchNode( Node* node, SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight )
166 if( node->child[0] != NULL) //not a leaf
168 Node* newNode = SearchNode(node->child[0], packPositionX, packPositionY, blockWidth, blockHeight);
169 if( newNode == NULL )// try search from the second child.
171 newNode = SearchNode(node->child[1], packPositionX, packPositionY, blockWidth, blockHeight);
175 else if( ApproximatelyEqual(node->rectArea.x, packPositionX) && ApproximatelyEqual(node->rectArea.y, packPositionY )
176 && ApproximatelyEqual(node->rectArea.width, blockWidth) && ApproximatelyEqual( node->rectArea.height, blockHeight) )
185 void AtlasPacker::MergeToNonOccupied( Node* node )
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)
192 delete parent->child[0];
193 parent->child[0] = NULL;
194 delete parent->child[1];
195 parent->child[1] = NULL;
197 MergeToNonOccupied( parent );
201 void AtlasPacker::DeleteNode( Node *node )
205 DeleteNode( node->child[0] );
206 DeleteNode( node->child[1] );
211 Uint16Pair AtlasPacker::GroupPack( const Dali::Vector<Uint16Pair>& blockSizes, Dali::Vector<Uint16Pair>& packPositions )
213 uint16_t count = blockSizes.Count();
214 packPositions.Resize( count );
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++ )
221 packOrder[i].SetX( MaxDimension( blockSizes[i] ) );
222 packOrder[i].SetY( i );
224 for( uint16_t i = 0; i < count-1; i++ )
225 for( uint16_t j = 0; j < count-i-1; j++ )
227 if( packOrder[j].GetX() < packOrder[j+1].GetX() )
229 Swap( packOrder[j], packOrder[j+1] );
233 int index = packOrder[0].GetY();
234 AtlasPacker packer( blockSizes[index].GetWidth(), blockSizes[index].GetHeight() );
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++ )
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 );
247 return Uint16Pair( packer.mRoot->rectArea.width, packer.mRoot->rectArea.height );
250 void AtlasPacker::GrowPack( SizeType blockWidth, SizeType blockHeight,
251 SizeType& packPositionX, SizeType& packPositionY )
253 Node* firstFit = InsertNode( mRoot, blockWidth, blockHeight );
254 if( firstFit == NULL )
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 );
261 DALI_ASSERT_ALWAYS( firstFit != NULL && "It should never happen!")
263 firstFit->occupied = true;
264 packPositionX = firstFit->rectArea.x;
265 packPositionY = firstFit->rectArea.y;
268 void AtlasPacker::GrowNode( SizeType blockWidth, SizeType blockHeight )
270 // Attempts to maintain a roughly square ratio when choosing the growing direction: right or down
271 bool canGrowRight = blockWidth <= mRoot->rectArea.width;
272 bool canGrowDown = blockHeight <= mRoot->rectArea.height;
274 bool shouldGrowRight = canGrowRight && mRoot->rectArea.height >= mRoot->rectArea.width+blockWidth;
275 bool shouldGrowDown = canGrowDown && mRoot->rectArea.width >= mRoot->rectArea.height+blockHeight;
277 if( canGrowRight && canGrowDown )
279 shouldGrowRight = mRoot->rectArea.width+blockWidth <= mRoot->rectArea.height+blockHeight;
280 shouldGrowDown = !shouldGrowRight;
283 if( shouldGrowRight || ( canGrowRight && !shouldGrowDown ) )
285 Node* newRoot = new Node( NULL, 0u, 0u, mRoot->rectArea.width+blockWidth, mRoot->rectArea.height );
286 newRoot->occupied = true;
287 newRoot->child[0] = mRoot;
288 newRoot->child[1] = new Node( newRoot, mRoot->rectArea.width, 0u, blockWidth, mRoot->rectArea.height );
292 else if( shouldGrowDown || ( canGrowDown && !shouldGrowRight ) )
294 Node* newRoot = new Node( NULL, 0u, 0u, mRoot->rectArea.width, mRoot->rectArea.height+blockHeight );
295 newRoot->occupied = true;
296 newRoot->child[0] = mRoot;
297 newRoot->child[1] = new Node( newRoot, 0u, mRoot->rectArea.height, mRoot->rectArea.width, blockHeight );
303 DALI_LOG_ERROR( " Atlas Packer failed to grow: make sure the packing order is sorted with the block size to avoid this happening");
307 } // namespace Internal
309 } // namespace Toolkit