FIFE
Main Page
Namespaces
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
atlasbook.cpp
Go to the documentation of this file.
1
/***************************************************************************
2
* Copyright (C) 2005-2013 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
}
FIFE::AtlasBlock::page
uint32_t page
Definition:
atlasbook.h:42
FIFE::AtlasBook::getBlock
AtlasBlock * getBlock(uint32_t width, uint32_t height)
Definition:
atlasbook.cpp:197
FIFE::AtlasBook::pageWidth
uint32_t pageWidth
Definition:
atlasbook.h:137
FIFE::AtlasBook::pixelSize
uint32_t pixelSize
Definition:
atlasbook.h:138
FIFE::AtlasBook::pageHeight
uint32_t pageHeight
Definition:
atlasbook.h:137
FIFE::AtlasPage::freePixels
int32_t freePixels
Definition:
atlasbook.h:108
FIFE::AtlasBlock::bottom
uint32_t bottom
Definition:
atlasbook.h:43
FIFE::AtlasBlock::getWidth
uint32_t getWidth() const
Definition:
atlasbook.h:76
FIFE::AtlasBlock
Definition:
atlasbook.h:40
FIFE::AtlasBlock::intersects
AtlasBlock intersects(AtlasBlock const &rect) const
Definition:
atlasbook.cpp:31
FIFE::AtlasPage::intersects
AtlasBlock const * intersects(AtlasBlock const *block) const
Definition:
atlasbook.cpp:188
FIFE::Exception
Exception base class.
Definition:
exception.h:43
FIFE::AtlasPage::pixelSize
uint32_t pixelSize
Definition:
atlasbook.h:106
FIFE::AtlasBlock::getHeight
uint32_t getHeight() const
Definition:
atlasbook.h:77
exception.h
FIFE::AtlasBlock::right
uint32_t right
Definition:
atlasbook.h:43
FIFE::AtlasBlock::merge
void merge(AtlasBlock const &rect)
Definition:
atlasbook.cpp:46
FIFE::AtlasBlock::top
uint32_t top
Definition:
atlasbook.h:43
FIFE::AtlasPage::height
uint32_t height
Definition:
atlasbook.h:105
FIFE::AtlasPage::width
uint32_t width
Definition:
atlasbook.h:105
atlasbook.h
FIFE::AtlasBook::extendCache
AtlasPage * extendCache(uint32_t minPageWidth, uint32_t minPageHeight)
Definition:
atlasbook.cpp:207
FIFE::AtlasPage
Definition:
atlasbook.h:83
FIFE::AtlasBlock::isTrivial
bool isTrivial() const
Definition:
atlasbook.h:72
FIFE::AtlasPage::getBlock
AtlasBlock * getBlock(uint32_t width, uint32_t height)
Definition:
atlasbook.cpp:53
FIFE::AtlasBook::pages
Pages pages
Definition:
atlasbook.h:141
FIFE::AtlasPage::blocks
Blocks blocks
Definition:
atlasbook.h:111
FIFE::Rect
RectType< int32_t > Rect
Definition:
rect.h:258
FIFE::AtlasPage::page
uint32_t page
Definition:
atlasbook.h:107
FIFE::AtlasBlock::left
uint32_t left
Definition:
atlasbook.h:43
FIFE::AtlasBook::shrink
void shrink(bool pot)
Definition:
atlasbook.cpp:220
utf8::uint32_t
unsigned int uint32_t
Definition:
core.h:40
FIFE::AtlasPage::shrink
void shrink(bool pot)
Definition:
atlasbook.cpp:155
FIFE::AtlasBlock::setTrivial
void setTrivial()
Definition:
atlasbook.h:68
engine
core
video
atlasbook.cpp
Generated on Tue Dec 10 2013 21:27:31 for FIFE by
1.8.5