/*************************************************************************** * Copyright (C) 2005-2019 by the FIFE team * * http://www.fifengine.net * * This file is part of FIFE. * * * * FIFE is free software; you can redistribute it and/or * * modify it under the terms of the GNU Lesser General Public * * License as published by the Free Software Foundation; either * * version 2.1 of the License, or (at your option) any later version. * * * * This library is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * * Lesser General Public License for more details. * * * * You should have received a copy of the GNU Lesser General Public * * License along with this library; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * ***************************************************************************/ // FIFE includes // These includes are split up in two parts, separated by one empty line // First block: files included from the FIFE root src directory // Second block: files included from the same folder #include "util/base/exception.h" #include "atlasbook.h" namespace FIFE { AtlasBlock AtlasBlock::intersects(AtlasBlock const& rect) const { AtlasBlock ret; ret.left = std::max(rect.left, left); ret.right = std::min(rect.right, right); ret.top = std::max(rect.top, top); ret.bottom = std::min(rect.bottom, bottom); if(ret.left > ret.right || ret.top > ret.bottom) { ret.setTrivial(); } return ret; } void AtlasBlock::merge(AtlasBlock const& rect) { left = std::min(rect.left, left); right = std::max(rect.right, right); top = std::min(rect.top, top); bottom = std::max(rect.bottom, bottom); } AtlasBlock* AtlasPage::getBlock(uint32_t width, uint32_t height) { if(static_cast(width*height*pixelSize) > freePixels) { return 0; } blocks.push_back(AtlasBlock(Rect(), 0)); AtlasBlock* newBlock = &blocks[blocks.size() - 1]; for(uint32_t v = 0; (v+1)*height <= this->height; ++v) { newBlock->top = v * height; newBlock->bottom = (v+1) * height; for(uint32_t u = 0; (u+1)*width <= this->width; ++u) { newBlock->left = u * width; newBlock->right = (u+1) * width; AtlasBlock const* intersection = intersects(newBlock); if(!intersection) { freePixels -= width*height*pixelSize; assert(freePixels >= 0); // try to squeeze a little bit (horizontal) if(newBlock->left > 0) { AtlasBlock squeezed(*newBlock); --squeezed.left; --squeezed.right; if(!(intersection = intersects(&squeezed))) { ++squeezed.left; ++squeezed.right; int blockWidth = newBlock->getWidth(); // binary search for(int i = 0, div = 2; i < 4; ++i) { squeezed.left -= blockWidth / div; squeezed.right -= blockWidth / div; if((intersection = intersects(&squeezed))) { squeezed.left += blockWidth / div; squeezed.right += blockWidth / div; } div <<= 1; } // linear search while(!(intersection = intersects(&squeezed)) && squeezed.left > 0) { --squeezed.left; --squeezed.right; } newBlock->left = squeezed.left + 1; newBlock->right = squeezed.right + 1; } } // try to squeeze a little bit (vertical) if(newBlock->top > 0) { AtlasBlock squeezed(*newBlock); --squeezed.top; --squeezed.bottom; if(!(intersection = intersects(&squeezed))) { ++squeezed.top; ++squeezed.bottom; int blockHeight = newBlock->getHeight(); // binary search for(int i = 0, div = 2; i < 4; ++i) { squeezed.top -= blockHeight / div; squeezed.bottom -= blockHeight / div; if((intersection = intersects(&squeezed))) { squeezed.top += blockHeight / div; squeezed.bottom += blockHeight / div; } div <<= 1; } // linear search while(!(intersection = intersects(&squeezed)) && squeezed.top > 0) { --squeezed.top; --squeezed.bottom; } newBlock->top = squeezed.top + 1; newBlock->bottom = squeezed.bottom + 1; } } newBlock->page = this->page; return newBlock; } } } // couldn't find suitable place for a new block blocks.pop_back(); return 0; } void AtlasPage::shrink(bool pot) { AtlasBlock boundaryBox(Rect(), 0); for(Blocks::iterator block = blocks.begin(); block != blocks.end(); ++block) { boundaryBox.merge(*block); } assert(boundaryBox.left == 0); assert(boundaryBox.top == 0); if(pot) { uint32_t bwidth = boundaryBox.getWidth(); uint32_t bheight = boundaryBox.getHeight(); if(bwidth < width) { // look for next power of 2 for width uint32_t powof2 = 1; while(powof2 < bwidth) powof2 <<= 1; width = std::min(powof2, width); } if(bheight < height) { // look for next power of 2 for width uint32_t powof2 = 1; while(powof2 < bheight) powof2 <<= 1; height = std::min(powof2, height); } } else { width = boundaryBox.getWidth(); height = boundaryBox.getHeight(); } } AtlasBlock const* AtlasPage::intersects(AtlasBlock const* block) const { for(size_t b = 0; b < blocks.size() - 1; ++b) { if(!blocks[b].intersects(*block).isTrivial()) return block; } // no intersection return 0; } AtlasBlock* AtlasBook::getBlock(uint32_t width, uint32_t height) { for(Pages::iterator page = pages.begin(); page != pages.end(); ++page) { AtlasBlock* block = page->getBlock(width, height); if(block) { return block; } } return extendCache(width, height)->getBlock(width, height); } AtlasPage* AtlasBook::extendCache(uint32_t minPageWidth, uint32_t minPageHeight) { if(minPageWidth > pageWidth || minPageHeight > pageHeight) { throw Exception("Texture is too big for this atlas."); } assert(minPageWidth <= pageWidth); assert(minPageHeight <= pageHeight); pages.push_back(AtlasPage(pageWidth, pageHeight, pixelSize, pages.size())); return &pages[pages.size()-1]; } void AtlasBook::shrink(bool pot) { for(Pages::iterator page = pages.begin(); page != pages.end(); ++page) { page->shrink(pot); } } }