FIFE  6e1afdbeda11afe9ac53e6023a4be96ef88f1dc6
atlasbook.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005-2017 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 {
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 
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 
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 }
uint32_t page
Definition: atlasbook.h:43
AtlasBlock * getBlock(uint32_t width, uint32_t height)
Definition: atlasbook.cpp:197
uint32_t bottom
Definition: atlasbook.h:44
uint32_t getWidth() const
Definition: atlasbook.h:77
AtlasBlock intersects(AtlasBlock const &rect) const
Definition: atlasbook.cpp:31
AtlasBlock const * intersects(AtlasBlock const *block) const
Definition: atlasbook.cpp:188
Exception base class.
Definition: exception.h:43
uint32_t getHeight() const
Definition: atlasbook.h:78
uint32_t right
Definition: atlasbook.h:44
void merge(AtlasBlock const &rect)
Definition: atlasbook.cpp:46
uint32_t top
Definition: atlasbook.h:44
AtlasPage * extendCache(uint32_t minPageWidth, uint32_t minPageHeight)
Definition: atlasbook.cpp:207
bool isTrivial() const
Definition: atlasbook.h:73
AtlasBlock * getBlock(uint32_t width, uint32_t height)
Definition: atlasbook.cpp:53
RectType< int32_t > Rect
Definition: rect.h:258
uint32_t left
Definition: atlasbook.h:44
void shrink(bool pot)
Definition: atlasbook.cpp:220
unsigned int uint32_t
Definition: core.h:40
void shrink(bool pot)
Definition: atlasbook.cpp:155
void setTrivial()
Definition: atlasbook.h:69