1 #ifndef DALI_TOOLKIT_ATLAS_PACKER_H
2 #define DALI_TOOLKIT_ATLAS_PACKER_H
5 * Copyright (c) 2021 Samsung Electronics Co., Ltd.
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
11 * http://www.apache.org/licenses/LICENSE-2.0
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
20 #include <dali/public-api/common/dali-vector.h>
21 #include <dali/public-api/math/rect.h>
22 #include <dali/public-api/math/uint-16-pair.h>
32 * Binary space tree based bin packing algorithm.
33 * It is initialised with a fixed width and height and will fit each block into the first node where it fits
34 * and then split that node into 2 parts (down and right) to track the remaining empty space.
40 * rectangular area (x,y,width,height)
42 typedef uint32_t SizeType;
43 typedef Rect<SizeType> RectArea;
50 Node(Node* parent, SizeType x, SizeType y, SizeType width, SizeType height);
61 * @param[in] atlasWidth The width of the atlas.
62 * @param[in] atlasHeight The height of the atlas.
64 AtlasPacker(SizeType atlasWidth, SizeType atlasHeight);
72 * Pack a block into the atlas.
74 * @param[in] blockWidth The width of the block to pack.
75 * @param[in] blockHeight The height of the block to pack.
76 * @param[out] packPositionX The x coordinate of the position to pack the block.
77 * @param[out] packPositionY The y coordinate of the position to pack the block.
78 * @return True if there are room for this block, false otherwise.
80 bool Pack(SizeType blockWidth, SizeType blockHeight, SizeType& packPositionX, SizeType& packPositionY);
85 * @param[in] packPositionX The x coordinate of the pack position.
86 * @param[in] packPositionY The y coordinate of the pack position.
87 * @param[in] blockWidth The width of the block to delete.
88 * @param[in] blockHeight The height of the block to delete.
90 void DeleteBlock(SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight);
93 * Query how much empty space left.
95 * @return The area available for packing.
97 unsigned int GetAvailableArea() const;
100 * Pack a group of blocks with different sizes, calculate the required packing size and the position of each block.
101 * @param[in] blockSizes The size list of the blocks .
102 * @param[out] packPositions The packing position of each block.
103 * @return The required size to accommodate all the blocks.
105 static Uint16Pair GroupPack(const Dali::Vector<Uint16Pair>& blockSizes, Dali::Vector<Uint16Pair>& packPositions);
109 * Search the node which can pack the block with given size.
111 * @param[in] root The root node of the subtree to be searched.
112 * @param[in] blockWidth The width of the block to pack.
113 * @param[in] blockHeight The height of the block to pack.
114 * @return The poniter pointing to node that can pack the block.
115 * If it is NULL, there are no room in the subtree to pack the block.
117 Node* InsertNode(Node* root, SizeType blockWidth, SizeType blockHeight);
120 * Split the node into two to fit the block width/size.
122 * @parm[in] node The node to split.
123 * @param[in] blockWidth The width of the block to pack.
124 * @param[in] blockHeight The height of the block to pack.
126 void SplitNode(Node* node, SizeType blockWidth, SizeType blockHeight);
129 * Search the node at the given position and with the given size.
131 * @param[in] node The root node of the subtree to be searched.
132 * @param[in] packPositionX The x coordinate of the pack position.
133 * @param[in] packPositionY The y coordinate of the pack position.
134 * @param[in] blockWidth The width of the block.
135 * @param[in] blockHeight The height of the block.
137 Node* SearchNode(Node* node, SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight);
140 * Merge the rect of the node to non-occupied area.
142 * @param[in] node The node to me merged to the non-occupied area
144 void MergeToNonOccupied(Node* node);
147 * Delete a node and its subtree.
149 * @parm[in] node The node to delete.
151 void DeleteNode(Node* node);
154 * Pack a block into the atlas. If there is no enough room, grow the partition tree.
156 * @param[in] blockWidth The width of the block to pack.
157 * @param[in] blockHeight The height of the block to pack.
158 * @param[out] packPositionX The x coordinate of the position to pack the block.
159 * @param[out] packPositionY The y coordinate of the position to pack the block.
161 void GrowPack(SizeType blockWidth, SizeType blockHeight, SizeType& packPositionX, SizeType& packPositionY);
164 * Add extra node into the partition tree to accommodate the given block.
166 * @param[in] blockWidth The width of the block to pack.
167 * @param[in] blockHeight The height of the block to pack.
169 void GrowNode(SizeType blockWidth, SizeType blockHeight);
172 AtlasPacker(const AtlasPacker& atlasPacker);
175 AtlasPacker& operator=(const AtlasPacker& atlasPacker);
178 Node* mRoot; ///< The root of the binary space tree
179 unsigned int mAvailableArea;
182 } // namespace Internal
184 } // namespace Toolkit
188 #endif // DALI_TOOLKIT_ATLAS_PACKER_H