1 #ifndef __DALI_TOOLKIT_ATLAS_PACKER_H__
2 #define __DALI_TOOLKIT_ATLAS_PACKER_H__
5 * Copyright (c) 2015 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.
21 #include <dali/public-api/common/dali-vector.h>
22 #include <dali/public-api/math/rect.h>
23 #include <dali/public-api/math/uint-16-pair.h>
35 * Binary space tree based bin packing algorithm.
36 * It is initialised with a fixed width and height and will fit each block into the first node where it fits
37 * and then split that node into 2 parts (down and right) to track the remaining empty space.
44 * rectangular area (x,y,width,height)
46 typedef uint32_t SizeType;
47 typedef Rect<SizeType> RectArea;
54 Node( Node* parent, SizeType x, SizeType y, SizeType width, SizeType height );
65 * @param[in] atlasWidth The width of the atlas.
66 * @param[in] atlasHeight The height of the atlas.
68 AtlasPacker( SizeType atlasWidth, SizeType atlasHeight );
76 * Pack a block into the atlas.
78 * @param[in] blockWidth The width of the block to pack.
79 * @param[in] blockHeight The height of the block to pack.
80 * @param[out] packPositionX The x coordinate of the position to pack the block.
81 * @param[out] packPositionY The y coordinate of the position to pack the block.
82 * @return True if there are room for this block, false otherwise.
84 bool Pack( SizeType blockWidth, SizeType blockHeight,
85 SizeType& packPositionX, SizeType& packPositionY);
90 * @param[in] packPositionX The x coordinate of the pack position.
91 * @param[in] packPositionY The y coordinate of the pack position.
92 * @param[in] blockWidth The width of the block to delete.
93 * @param[in] blockHeight The height of the block to delete.
95 void DeleteBlock( SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight );
98 * Query how much empty space left.
100 * @return The area available for packing.
102 unsigned int GetAvailableArea() const;
105 * Pack a group of blocks with different sizes, calculate the required packing size and the position of each block.
106 * @param[in] blockSizes The size list of the blocks .
107 * @param[out] packPositions The packing position of each block.
108 * @return The required size to accommodate all the blocks.
110 static Uint16Pair GroupPack( const Dali::Vector<Uint16Pair>& blockSizes, Dali::Vector<Uint16Pair>& packPositions );
115 * Search the node which can pack the block with given size.
117 * @param[in] root The root node of the subtree to be searched.
118 * @param[in] blockWidth The width of the block to pack.
119 * @param[in] blockHeight The height of the block to pack.
120 * @return The poniter pointing to node that can pack the block.
121 * If it is NULL, there are no room in the subtree to pack the block.
123 Node* InsertNode( Node* root, SizeType blockWidth, SizeType blockHeight );
126 * Split the node into two to fit the block width/size.
128 * @parm[in] node The node to split.
129 * @param[in] blockWidth The width of the block to pack.
130 * @param[in] blockHeight The height of the block to pack.
132 void SplitNode( Node* node, SizeType blockWidth, SizeType blockHeight );
135 * Search the node at the given position and with the given size.
137 * @param[in] node The root node of the subtree to be searched.
138 * @param[in] packPositionX The x coordinate of the pack position.
139 * @param[in] packPositionY The y coordinate of the pack position.
140 * @param[in] blockWidth The width of the block.
141 * @param[in] blockHeight The height of the block.
143 Node* SearchNode( Node* node, SizeType packPositionX, SizeType packPositionY, SizeType blockWidth, SizeType blockHeight );
146 * Merge the rect of the node to non-occupied area.
148 * @param[in] node The node to me merged to the non-occupied area
150 void MergeToNonOccupied( Node* node );
153 * Delete a node and its subtree.
155 * @parm[in] node The node to delete.
157 void DeleteNode( Node* node );
160 * Pack a block into the atlas. If there is no enough room, grow the partition tree.
162 * @param[in] blockWidth The width of the block to pack.
163 * @param[in] blockHeight The height of the block to pack.
164 * @param[out] packPositionX The x coordinate of the position to pack the block.
165 * @param[out] packPositionY The y coordinate of the position to pack the block.
167 void GrowPack( SizeType blockWidth, SizeType blockHeight,
168 SizeType& packPositionX, SizeType& packPositionY );
171 * Add extra node into the partition tree to accommodate the given block.
173 * @param[in] blockWidth The width of the block to pack.
174 * @param[in] blockHeight The height of the block to pack.
176 void GrowNode( SizeType blockWidth, SizeType blockHeight );
179 AtlasPacker( const AtlasPacker& atlasPacker);
182 AtlasPacker& operator=( const AtlasPacker& atlasPacker );
186 Node* mRoot; ///< The root of the binary space tree
187 unsigned int mAvailableArea;
192 } // namespace Internal
194 } // namespace Toolkit
198 #endif /* __DALI_TOOLKIT_ATLAS_PACKER_H__ */