2 * Copyright (c) 2015 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()
36 bool ApproximatelyEqual( uint32_t a, uint32_t b )
38 return abs( a-b ) <= 1;
43 AtlasPacker::Node::Node( Node* parent, SizeType x, SizeType y, SizeType width, SizeType height )
44 : rectArea( x, y, width, height ),
52 AtlasPacker:: AtlasPacker( SizeType atlasWidth, SizeType atlasHeight )
53 : mAvailableArea( atlasWidth * atlasHeight )
55 mRoot = new Node( NULL, 0u, 0u, atlasWidth, atlasHeight );
58 AtlasPacker::~AtlasPacker()
63 bool AtlasPacker::Pack( SizeType blockWidth, SizeType blockHeight,
64 SizeType& packPositionX, SizeType& packPositionY)
66 Node* firstFit = InsertNode( mRoot, blockWidth, blockHeight );
67 if( firstFit != NULL )
69 firstFit->occupied = true;
70 packPositionX = firstFit->rectArea.x;
71 packPositionY = firstFit->rectArea.y;
72 mAvailableArea -= blockWidth*blockHeight;
78 void AtlasPacker::DeleteBlock( SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight )
80 Node* node = SearchNode( mRoot, packPositionX, packPositionY, blockWidth, blockHeight );
83 mAvailableArea += blockWidth*blockHeight;
84 MergeToNonOccupied( node );
88 unsigned int AtlasPacker::GetAvailableArea() const
90 return mAvailableArea;
93 AtlasPacker::Node* AtlasPacker::InsertNode( Node* root, SizeType blockWidth, SizeType blockHeight )
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.
106 newNode = InsertNode(root->child[1], blockWidth, blockHeight);
112 if( root->rectArea.width < blockWidth || root->rectArea.height < blockHeight )
117 // right size, accept
118 if( root->rectArea.width == blockWidth && root->rectArea.height == blockHeight )
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);
129 void AtlasPacker::SplitNode( Node* node, SizeType blockWidth, SizeType blockHeight )
131 node->occupied = true;
133 // decide which way to split
134 SizeType remainingWidth = node->rectArea.width - blockWidth;
135 SizeType remainingHeight = node->rectArea.height - blockHeight;
137 if( remainingWidth > remainingHeight ) // split vertically
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 );
142 else // split horizontally
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 );
149 AtlasPacker::Node* AtlasPacker::SearchNode( Node* node, SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight )
156 if( node->child[0] != NULL) //not a leaf
158 Node* newNode = SearchNode(node->child[0], packPositionX, packPositionY, blockWidth, blockHeight);
159 if( newNode == NULL )// try search from the second child.
161 newNode = SearchNode(node->child[1], packPositionX, packPositionY, blockWidth, blockHeight);
165 else if( ApproximatelyEqual(node->rectArea.x, packPositionX) && ApproximatelyEqual(node->rectArea.y, packPositionY )
166 && ApproximatelyEqual(node->rectArea.width, blockWidth) && ApproximatelyEqual( node->rectArea.height, blockHeight) )
174 void AtlasPacker::MergeToNonOccupied( Node* node )
176 node->occupied = false;
177 Node* parent = node->parent;
178 // both child are not occupied, merge the space to parent
179 if( parent != NULL && parent->child[0]->occupied == false && parent->child[1]->occupied == false)
181 delete parent->child[0];
182 parent->child[0] = NULL;
183 delete parent->child[1];
184 parent->child[1] = NULL;
186 MergeToNonOccupied( parent );
190 void AtlasPacker::DeleteNode( Node *node )
194 DeleteNode( node->child[0] );
195 DeleteNode( node->child[1] );
200 } // namespace Internal
202 } // namespace Toolkit