Debian Codegraph @

engine/core/video/atlasbook.cpp

raw
1 /***************************************************************************
2 * Copyright (C) 2005-2019 by the FIFE team *
3 * http://www.fifengine.net *
4 * This file is part of FIFE. *
5 * *
6 * FIFE is free software; you can redistribute it and/or *
7 * modify it under the terms of the GNU Lesser General Public *
8 * License as published by the Free Software Foundation; either *
9 * version 2.1 of the License, or (at your option) any later version. *
10 * *
11 * This library is distributed in the hope that it will be useful, *
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
14 * Lesser General Public License for more details. *
15 * *
16 * You should have received a copy of the GNU Lesser General Public *
17 * License along with this library; if not, write to the *
18 * Free Software Foundation, Inc., *
19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA *
20 ***************************************************************************/
21
22 // FIFE includes
23 // These includes are split up in two parts, separated by one empty line
24 // First block: files included from the FIFE root src directory
25 // Second block: files included from the same folder
26 #include "util/base/exception.h"
27
28 #include "atlasbook.h"
29
30 namespace FIFE {
31 AtlasBlock AtlasBlock::intersects(AtlasBlock const& rect) const {
32 AtlasBlock ret;
33
34 ret.left = std::max(rect.left, left);
35 ret.right = std::min(rect.right, right);
36 ret.top = std::max(rect.top, top);
37 ret.bottom = std::min(rect.bottom, bottom);
38
39 if(ret.left > ret.right || ret.top > ret.bottom) {
40 ret.setTrivial();
41 }
42
43 return ret;
44 }
45
46 void AtlasBlock::merge(AtlasBlock const& rect) {
47 left = std::min(rect.left, left);
48 right = std::max(rect.right, right);
49 top = std::min(rect.top, top);
50 bottom = std::max(rect.bottom, bottom);
51 }
52
53 AtlasBlock* AtlasPage::getBlock(uint32_t width, uint32_t height) {
54 if(static_cast<int32_t>(width*height*pixelSize) > freePixels) {
55 return 0;
56 }
57
58 blocks.push_back(AtlasBlock(Rect(), 0));
59 AtlasBlock* newBlock = &blocks[blocks.size() - 1];
60
61 for(uint32_t v = 0; (v+1)*height <= this->height; ++v) {
62 newBlock->top = v * height;
63 newBlock->bottom = (v+1) * height;
64
65 for(uint32_t u = 0; (u+1)*width <= this->width; ++u) {
66
67 newBlock->left = u * width;
68 newBlock->right = (u+1) * width;
69
70 AtlasBlock const* intersection = intersects(newBlock);
71 if(!intersection) {
72 freePixels -= width*height*pixelSize;
73 assert(freePixels >= 0);
74
75 // try to squeeze a little bit (horizontal)
76 if(newBlock->left > 0) {
77 AtlasBlock squeezed(*newBlock);
78
79 --squeezed.left;
80 --squeezed.right;
81
82 if(!(intersection = intersects(&squeezed))) {
83 ++squeezed.left;
84 ++squeezed.right;
85 int blockWidth = newBlock->getWidth();
86
87 // binary search
88 for(int i = 0, div = 2; i < 4; ++i) {
89 squeezed.left -= blockWidth / div;
90 squeezed.right -= blockWidth / div;
91
92 if((intersection = intersects(&squeezed))) {
93 squeezed.left += blockWidth / div;
94 squeezed.right += blockWidth / div;
95 }
96 div <<= 1;
97 }
98
99 // linear search
100 while(!(intersection = intersects(&squeezed)) && squeezed.left > 0) {
101 --squeezed.left;
102 --squeezed.right;
103 }
104
105 newBlock->left = squeezed.left + 1;
106 newBlock->right = squeezed.right + 1;
107 }
108 }
109
110 // try to squeeze a little bit (vertical)
111 if(newBlock->top > 0) {
112 AtlasBlock squeezed(*newBlock);
113
114 --squeezed.top;
115 --squeezed.bottom;
116
117 if(!(intersection = intersects(&squeezed))) {
118 ++squeezed.top;
119 ++squeezed.bottom;
120 int blockHeight = newBlock->getHeight();
121
122 // binary search
123 for(int i = 0, div = 2; i < 4; ++i) {
124 squeezed.top -= blockHeight / div;
125 squeezed.bottom -= blockHeight / div;
126
127 if((intersection = intersects(&squeezed))) {
128 squeezed.top += blockHeight / div;
129 squeezed.bottom += blockHeight / div;
130 }
131 div <<= 1;
132 }
133
134 // linear search
135 while(!(intersection = intersects(&squeezed)) && squeezed.top > 0) {
136 --squeezed.top;
137 --squeezed.bottom;
138 }
139
140 newBlock->top = squeezed.top + 1;
141 newBlock->bottom = squeezed.bottom + 1;
142 }
143 }
144
145 newBlock->page = this->page;
146 return newBlock;
147 }
148 }
149 }
150 // couldn't find suitable place for a new block
151 blocks.pop_back();
152 return 0;
153 }
154
155 void AtlasPage::shrink(bool pot) {
156 AtlasBlock boundaryBox(Rect(), 0);
157 for(Blocks::iterator block = blocks.begin(); block != blocks.end(); ++block) {
158 boundaryBox.merge(*block);
159 }
160
161 assert(boundaryBox.left == 0);
162 assert(boundaryBox.top == 0);
163
164 if(pot) {
165 uint32_t bwidth = boundaryBox.getWidth();
166 uint32_t bheight = boundaryBox.getHeight();
167
168 if(bwidth < width) {
169 // look for next power of 2 for width
170 uint32_t powof2 = 1;
171 while(powof2 < bwidth) powof2 <<= 1;
172 width = std::min(powof2, width);
173 }
174
175 if(bheight < height) {
176 // look for next power of 2 for width
177 uint32_t powof2 = 1;
178 while(powof2 < bheight) powof2 <<= 1;
179 height = std::min(powof2, height);
180 }
181
182 } else {
183 width = boundaryBox.getWidth();
184 height = boundaryBox.getHeight();
185 }
186 }
187
188 AtlasBlock const* AtlasPage::intersects(AtlasBlock const* block) const {
189 for(size_t b = 0; b < blocks.size() - 1; ++b) {
190 if(!blocks[b].intersects(*block).isTrivial())
191 return block;
192 }
193 // no intersection
194 return 0;
195 }
196
197 AtlasBlock* AtlasBook::getBlock(uint32_t width, uint32_t height) {
198 for(Pages::iterator page = pages.begin(); page != pages.end(); ++page) {
199 AtlasBlock* block = page->getBlock(width, height);
200 if(block) {
201 return block;
202 }
203 }
204 return extendCache(width, height)->getBlock(width, height);
205 }
206
207 AtlasPage* AtlasBook::extendCache(uint32_t minPageWidth, uint32_t minPageHeight) {
208 if(minPageWidth > pageWidth ||
209 minPageHeight > pageHeight) {
210 throw Exception("Texture is too big for this atlas.");
211 }
212
213 assert(minPageWidth <= pageWidth);
214 assert(minPageHeight <= pageHeight);
215
216 pages.push_back(AtlasPage(pageWidth, pageHeight, pixelSize, pages.size()));
217 return &pages[pages.size()-1];
218 }
219
220 void AtlasBook::shrink(bool pot) {
221 for(Pages::iterator page = pages.begin(); page != pages.end(); ++page) {
222 page->shrink(pot);
223 }
224 }
225 }