1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#include "Image/BsTextureAtlasLayout.h"
4#include "Debug/BsDebug.h"
5#include "Utility/BsBitwise.h"
6
7namespace bs
8{
9 bool TextureAtlasLayout::addElement(UINT32 width, UINT32 height, UINT32& x, UINT32& y)
10 {
11 if(width == 0 || height == 0)
12 {
13 x = 0;
14 y = 0;
15 return true;
16 }
17
18 // Try adding without expanding, if that fails try to expand
19 if(!addToNode(0, width, height, x, y, false))
20 {
21 if (!addToNode(0, width, height, x, y, true))
22 return false;
23 }
24
25 // Update size to cover all nodes
26 if(mPow2)
27 {
28 mWidth = std::max(mWidth, Bitwise::nextPow2(x + width));
29 mHeight = std::max(mHeight, Bitwise::nextPow2(y + height));
30 }
31 else
32 {
33 mWidth = std::max(mWidth, x + width);
34 mHeight = std::max(mHeight, y + height);
35 }
36
37 return true;
38 }
39
40 void TextureAtlasLayout::clear()
41 {
42 mNodes.clear();
43 mNodes.push_back(TexAtlasNode(0, 0, mWidth, mHeight));
44
45 mWidth = mInitialWidth;
46 mHeight = mInitialHeight;
47 }
48
49 bool TextureAtlasLayout::addToNode(UINT32 nodeIdx, UINT32 width, UINT32 height, UINT32& x, UINT32& y, bool allowGrowth)
50 {
51 TexAtlasNode* node = &mNodes[nodeIdx];
52 float aspect = node->width / (float)node->height;
53
54 if (node->children[0] != (UINT32)-1)
55 {
56 if (addToNode(node->children[0], width, height, x, y, allowGrowth))
57 return true;
58
59 return addToNode(node->children[1], width, height, x, y, allowGrowth);
60 }
61 else
62 {
63 if (node->nodeFull)
64 return false;
65
66 if (width > node->width || height > node->height)
67 return false;
68
69 if(!allowGrowth)
70 {
71 if (node->x + width > mWidth || node->y + height > mHeight)
72 return false;
73 }
74
75 if (width == node->width && height == node->height)
76 {
77 x = node->x;
78 y = node->y;
79 node->nodeFull = true;
80
81 return true;
82 }
83
84 float dw = (float)(node->width - width);
85 float dh = (node->height - height) * aspect;
86
87 UINT32 nextChildIdx = (UINT32)mNodes.size();
88 node->children[0] = nextChildIdx;
89 node->children[1] = nextChildIdx + 1;
90
91 TexAtlasNode nodeCopy = *node;
92 node = nullptr; // Undefined past this point
93 if (dw > dh)
94 {
95 mNodes.emplace_back(nodeCopy.x, nodeCopy.y, width, nodeCopy.height);
96 mNodes.emplace_back(nodeCopy.x + width, nodeCopy.y, nodeCopy.width - width, nodeCopy.height);
97 }
98 else
99 {
100 mNodes.emplace_back(nodeCopy.x, nodeCopy.y, nodeCopy.width, height);
101 mNodes.emplace_back(nodeCopy.x, nodeCopy.y + height, nodeCopy.width, nodeCopy.height - height);
102 }
103
104 return addToNode(nodeCopy.children[0], width, height, x, y, allowGrowth);
105 }
106 }
107
108 Vector<TextureAtlasUtility::Page> TextureAtlasUtility::createAtlasLayout(Vector<Element>& elements, UINT32 width,
109 UINT32 height, UINT32 maxWidth, UINT32 maxHeight, bool pow2)
110 {
111 for (size_t i = 0; i < elements.size(); i++)
112 {
113 elements[i].output.idx = (UINT32)i; // Preserve original index before sorting
114 elements[i].output.page = -1;
115 }
116
117 std::sort(elements.begin(), elements.end(),
118 [](const Element& a, const Element& b)
119 {
120 return a.input.width * a.input.height > b.input.width * b.input.height;
121 });
122
123 Vector<TextureAtlasLayout> layouts;
124 UINT32 remainingCount = (UINT32)elements.size();
125 while (remainingCount > 0)
126 {
127 layouts.push_back(TextureAtlasLayout(width, height, maxWidth, maxHeight, pow2));
128 TextureAtlasLayout& curLayout = layouts.back();
129
130 // Find largest unassigned element that fits
131 UINT32 sizeLimit = std::numeric_limits<UINT32>::max();
132 while (true)
133 {
134 UINT32 largestId = -1;
135
136 // Assumes elements are sorted from largest to smallest
137 for (UINT32 i = 0; i < (UINT32)elements.size(); i++)
138 {
139 if (elements[i].output.page == -1)
140 {
141 UINT32 size = elements[i].input.width * elements[i].input.height;
142 if (size < sizeLimit)
143 {
144 largestId = i;
145 break;
146 }
147 }
148 }
149
150 if (largestId == (UINT32)-1)
151 break; // Nothing fits, start a new page
152
153 Element& element = elements[largestId];
154
155 // Check if an element is too large to ever fit
156 if(element.input.width > maxWidth || element.input.height > maxHeight)
157 {
158 LOGWRN("Some of the provided elements don't fit in an atlas of provided size. Returning empty array of pages.");
159 return Vector<Page>();
160 }
161
162 if (curLayout.addElement(element.input.width, element.input.height, element.output.x, element.output.y))
163 {
164 element.output.page = (UINT32)layouts.size() - 1;
165 remainingCount--;
166 }
167 else
168 sizeLimit = element.input.width * element.input.height;
169 }
170 }
171
172 Vector<Page> pages;
173 for (auto& layout : layouts)
174 pages.push_back({ layout.getWidth(), layout.getHeight() });
175
176 return pages;
177 }
178}
179