2 * Copyright (c) 2021 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 <dali/integration-api/debug.h>
23 #include <cstdlib> // For abs()
33 bool ApproximatelyEqual(uint32_t a, uint32_t b)
35 return std::abs(static_cast<int32_t>(a - b)) <= 1;
38 uint16_t MaxDimension(const Uint16Pair& dimensions)
40 return dimensions.GetWidth() >= dimensions.GetHeight() ? dimensions.GetWidth() : dimensions.GetHeight();
43 void Swap(Uint16Pair& first, Uint16Pair& second)
45 Uint16Pair temp = first;
52 AtlasPacker::Node::Node(Node* parent, SizeType x, SizeType y, SizeType width, SizeType height)
53 : rectArea(x, y, width, height),
61 AtlasPacker::AtlasPacker(SizeType atlasWidth, SizeType atlasHeight)
62 : mAvailableArea(atlasWidth * atlasHeight)
64 mRoot = new Node(NULL, 0u, 0u, atlasWidth, atlasHeight);
67 AtlasPacker::~AtlasPacker()
72 bool AtlasPacker::Pack(SizeType blockWidth, SizeType blockHeight, SizeType& packPositionX, SizeType& packPositionY)
74 Node* firstFit = InsertNode(mRoot, blockWidth, blockHeight);
77 firstFit->occupied = true;
78 packPositionX = firstFit->rectArea.x;
79 packPositionY = firstFit->rectArea.y;
80 mAvailableArea -= blockWidth * blockHeight;
86 void AtlasPacker::DeleteBlock(SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight)
88 Node* node = SearchNode(mRoot, packPositionX, packPositionY, blockWidth, blockHeight);
91 mAvailableArea += blockWidth * blockHeight;
92 MergeToNonOccupied(node);
96 unsigned int AtlasPacker::GetAvailableArea() const
98 return mAvailableArea;
101 AtlasPacker::Node* AtlasPacker::InsertNode(Node* root, SizeType blockWidth, SizeType blockHeight)
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.
114 newNode = InsertNode(root->child[1], blockWidth, blockHeight);
120 if(root->rectArea.width < blockWidth || root->rectArea.height < blockHeight)
125 // right size, accept
126 if(root->rectArea.width == blockWidth && root->rectArea.height == blockHeight)
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);
137 void AtlasPacker::SplitNode(Node* node, SizeType blockWidth, SizeType blockHeight)
139 node->occupied = true;
141 // decide which way to split
142 SizeType remainingWidth = node->rectArea.width - blockWidth;
143 SizeType remainingHeight = node->rectArea.height - blockHeight;
145 if(remainingWidth > remainingHeight) // split vertically
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);
150 else // split horizontally
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);
157 AtlasPacker::Node* AtlasPacker::SearchNode(Node* node, SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight)
161 if(node->child[0] != NULL) //not a leaf
163 Node* newNode = SearchNode(node->child[0], packPositionX, packPositionY, blockWidth, blockHeight);
164 if(newNode == NULL) // try search from the second child.
166 newNode = SearchNode(node->child[1], packPositionX, packPositionY, blockWidth, blockHeight);
170 else if(ApproximatelyEqual(node->rectArea.x, packPositionX) && ApproximatelyEqual(node->rectArea.y, packPositionY) && ApproximatelyEqual(node->rectArea.width, blockWidth) && ApproximatelyEqual(node->rectArea.height, blockHeight))
179 void AtlasPacker::MergeToNonOccupied(Node* node)
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)
186 delete parent->child[0];
187 parent->child[0] = NULL;
188 delete parent->child[1];
189 parent->child[1] = NULL;
191 MergeToNonOccupied(parent);
195 void AtlasPacker::DeleteNode(Node* node)
199 DeleteNode(node->child[0]);
200 DeleteNode(node->child[1]);
205 Uint16Pair AtlasPacker::GroupPack(const Dali::Vector<Uint16Pair>& blockSizes, Dali::Vector<Uint16Pair>& packPositions)
207 uint16_t count = blockSizes.Count();
208 packPositions.Resize(count);
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++)
215 packOrder[i].SetX(MaxDimension(blockSizes[i]));
216 packOrder[i].SetY(i);
218 for(uint16_t i = 0; i < count - 1; i++)
219 for(uint16_t j = 0; j < count - i - 1; j++)
221 if(packOrder[j].GetX() < packOrder[j + 1].GetX())
223 Swap(packOrder[j], packOrder[j + 1]);
227 int index = packOrder[0].GetY();
228 AtlasPacker packer(blockSizes[index].GetWidth(), blockSizes[index].GetHeight());
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++)
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);
240 return Uint16Pair(packer.mRoot->rectArea.width, packer.mRoot->rectArea.height);
243 void AtlasPacker::GrowPack(SizeType blockWidth, SizeType blockHeight, SizeType& packPositionX, SizeType& packPositionY)
245 Node* firstFit = InsertNode(mRoot, blockWidth, blockHeight);
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);
253 DALI_ASSERT_ALWAYS(firstFit != NULL && "It should never happen!")
255 firstFit->occupied = true;
256 packPositionX = firstFit->rectArea.x;
257 packPositionY = firstFit->rectArea.y;
260 void AtlasPacker::GrowNode(SizeType blockWidth, SizeType blockHeight)
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;
266 bool shouldGrowRight = canGrowRight && mRoot->rectArea.height >= mRoot->rectArea.width + blockWidth;
267 bool shouldGrowDown = canGrowDown && mRoot->rectArea.width >= mRoot->rectArea.height + blockHeight;
269 if(canGrowRight && canGrowDown)
271 shouldGrowRight = mRoot->rectArea.width + blockWidth <= mRoot->rectArea.height + blockHeight;
272 shouldGrowDown = !shouldGrowRight;
275 if(shouldGrowRight || (canGrowRight && !shouldGrowDown))
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);
284 else if(shouldGrowDown || (canGrowDown && !shouldGrowRight))
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);
295 DALI_LOG_ERROR(" Atlas Packer failed to grow: make sure the packing order is sorted with the block size to avoid this happening");
299 } // namespace Internal
301 } // namespace Toolkit