26 #include "util/base/exception.h"
28 #include "atlasbook.h"
31 AtlasBlock AtlasBlock::intersects(AtlasBlock
const& rect)
const {
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);
39 if(ret.left > ret.right || ret.top > ret.bottom) {
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);
53 AtlasBlock* AtlasPage::getBlock(uint32_t width, uint32_t height) {
54 if(static_cast<int32_t>(width*height*pixelSize) > freePixels) {
58 blocks.push_back(AtlasBlock(Rect(), 0));
59 AtlasBlock* newBlock = &blocks[blocks.size() - 1];
61 for(uint32_t v = 0; (v+1)*height <= this->height; ++v) {
62 newBlock->top = v * height;
63 newBlock->bottom = (v+1) * height;
65 for(uint32_t u = 0; (u+1)*width <= this->width; ++u) {
67 newBlock->left = u * width;
68 newBlock->right = (u+1) * width;
70 AtlasBlock
const* intersection = intersects(newBlock);
72 freePixels -= width*height*pixelSize;
73 assert(freePixels >= 0);
76 if(newBlock->left > 0) {
77 AtlasBlock squeezed(*newBlock);
82 if(!(intersection = intersects(&squeezed))) {
85 int blockWidth = newBlock->getWidth();
88 for(
int i = 0, div = 2; i < 4; ++i) {
89 squeezed.left -= blockWidth / div;
90 squeezed.right -= blockWidth / div;
92 if((intersection = intersects(&squeezed))) {
93 squeezed.left += blockWidth / div;
94 squeezed.right += blockWidth / div;
100 while(!(intersection = intersects(&squeezed)) && squeezed.left > 0) {
105 newBlock->left = squeezed.left + 1;
106 newBlock->right = squeezed.right + 1;
111 if(newBlock->top > 0) {
112 AtlasBlock squeezed(*newBlock);
117 if(!(intersection = intersects(&squeezed))) {
120 int blockHeight = newBlock->getHeight();
123 for(
int i = 0, div = 2; i < 4; ++i) {
124 squeezed.top -= blockHeight / div;
125 squeezed.bottom -= blockHeight / div;
127 if((intersection = intersects(&squeezed))) {
128 squeezed.top += blockHeight / div;
129 squeezed.bottom += blockHeight / div;
135 while(!(intersection = intersects(&squeezed)) && squeezed.top > 0) {
140 newBlock->top = squeezed.top + 1;
141 newBlock->bottom = squeezed.bottom + 1;
145 newBlock->page = this->page;
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);
161 assert(boundaryBox.left == 0);
162 assert(boundaryBox.top == 0);
165 uint32_t bwidth = boundaryBox.getWidth();
166 uint32_t bheight = boundaryBox.getHeight();
171 while(powof2 < bwidth) powof2 <<= 1;
172 width = std::min(powof2, width);
175 if(bheight < height) {
178 while(powof2 < bheight) powof2 <<= 1;
179 height = std::min(powof2, height);
183 width = boundaryBox.getWidth();
184 height = boundaryBox.getHeight();
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())
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);
204 return extendCache(width, height)->getBlock(width, height);
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.");
213 assert(minPageWidth <= pageWidth);
214 assert(minPageHeight <= pageHeight);
216 pages.push_back(AtlasPage(pageWidth, pageHeight, pixelSize, pages.size()));
217 return &pages[pages.size()-1];
220 void AtlasBook::shrink(
bool pot) {
221 for(Pages::iterator page = pages.begin(); page != pages.end(); ++page) {
credit to phoku for his NodeDisplay example which the visitor code is adapted from ( he coded the qua...