1 /* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */
2
3 #include "RowAtlasAlloc.h"
4 #include <vector>
5 #include "System/bitops.h"
6
7 // texture spacing in the atlas (in pixels)
8 static const int ATLAS_PADDING = 1;
9
10
CRowAtlasAlloc()11 CRowAtlasAlloc::CRowAtlasAlloc()
12 : nextRowPos(0)
13 {
14 atlasSize.x = 256;
15 atlasSize.y = 256;
16 }
17
18
CompareTex(SAtlasEntry * tex1,SAtlasEntry * tex2)19 inline int CRowAtlasAlloc::CompareTex(SAtlasEntry* tex1, SAtlasEntry* tex2)
20 {
21 // sort by large to small
22 if (tex1->size.y == tex2->size.y) {
23 return (tex1->size.x > tex2->size.x);
24 }
25 return (tex1->size.y > tex2->size.y);
26 }
27
28
EstimateNeededSize()29 void CRowAtlasAlloc::EstimateNeededSize()
30 {
31 int spaceNeeded = 0;
32 int spaceFree = atlasSize.x * (atlasSize.y - nextRowPos);
33 for (auto it: entries) {
34 spaceNeeded += it.second.size.x * it.second.size.y;
35 }
36 for(auto& row: imageRows) {
37 spaceFree += row.height * (atlasSize.x - row.width);
38 }
39
40 while (spaceFree < spaceNeeded * 1.2f) {
41 if (atlasSize.x>=maxsize.x && atlasSize.y>=maxsize.y) {
42 break;
43 }
44
45 // Resize texture
46 if ((atlasSize.x << 1) <= maxsize.x) {
47 spaceFree += atlasSize.x * atlasSize.y;
48 atlasSize.x = std::min(maxsize.x, atlasSize.x << 1);
49 }
50 if ((atlasSize.y << 1) <= maxsize.y) {
51 spaceFree += atlasSize.x * atlasSize.y;
52 atlasSize.y = std::min(maxsize.y, atlasSize.y << 1);
53 }
54 }
55 }
56
57
AddRow(int glyphWidth,int glyphHeight)58 CRowAtlasAlloc::Row* CRowAtlasAlloc::AddRow(int glyphWidth, int glyphHeight)
59 {
60 const int wantedRowHeight = glyphHeight;
61 while (atlasSize.y < (nextRowPos + wantedRowHeight)) {
62 if (atlasSize.x>=maxsize.x && atlasSize.y>=maxsize.y) {
63 //throw texture_size_exception();
64 return nullptr;
65 }
66
67 // Resize texture
68 atlasSize.x = std::min(maxsize.x, atlasSize.x << 1);
69 atlasSize.y = std::min(maxsize.y, atlasSize.y << 1);
70 }
71
72 Row newrow(nextRowPos, wantedRowHeight);
73 nextRowPos += wantedRowHeight;
74 imageRows.push_back(newrow);
75 return &imageRows.back();
76 }
77
78
Allocate()79 bool CRowAtlasAlloc::Allocate()
80 {
81 bool success = true;
82
83 if (npot) {
84 // revert the used height clamping at the bottom of this function
85 // else for the case when Allocate() is called multiple times, the width would grew faster than height
86 // also AddRow() only works with PowerOfTwo values.
87 atlasSize.y = next_power_of_2(atlasSize.y);
88 }
89
90 // it gives much better results when we resize the available space before starting allocation
91 // esp. allocation is more horizontal and so we can clip more free space at bottom
92 EstimateNeededSize();
93
94 // sort new entries by height from large to small
95 std::vector<SAtlasEntry*> memtextures;
96 for (auto it = entries.begin(); it != entries.end(); ++it) {
97 memtextures.push_back(&it->second);
98 }
99 sort(memtextures.begin(), memtextures.end(), CRowAtlasAlloc::CompareTex);
100
101 // find space for them
102 for (auto& curtex: memtextures) {
103 Row* row = FindRow(curtex->size.x + ATLAS_PADDING, curtex->size.y + ATLAS_PADDING);
104 if (!row) {
105 success = false;
106 continue;
107 }
108
109 curtex->texCoords.x1 = row->width;
110 curtex->texCoords.y1 = row->position;
111 curtex->texCoords.x2 = row->width + curtex->size.x;
112 curtex->texCoords.y2 = row->position + curtex->size.y;
113 row->width += curtex->size.x + ATLAS_PADDING;
114 }
115
116 if (npot) {
117 atlasSize.y = nextRowPos;
118 } else {
119 atlasSize.y = next_power_of_2(nextRowPos);
120 }
121
122 return success;
123 }
124
125
FindRow(int glyphWidth,int glyphHeight)126 CRowAtlasAlloc::Row* CRowAtlasAlloc::FindRow(int glyphWidth, int glyphHeight)
127 {
128 int best_width = atlasSize.x;
129 float best_ratio = 10000.0f;
130 Row* best_row = nullptr;
131
132 // first try to find a row with similar height
133 for(auto& row: imageRows) {
134 // Check if there is enough space in this row
135 if (glyphWidth > (atlasSize.x - row.width))
136 continue;
137 if (glyphHeight > row.height)
138 continue;
139
140 const float ratio = float(row.height) / glyphHeight;
141 if ((ratio < best_ratio) || ((ratio == best_ratio) && (row.width < best_width))) {
142 best_width = row.width;
143 best_ratio = ratio;
144 best_row = &row;
145 }
146 }
147
148 if (best_row != nullptr)
149 return best_row;
150
151 // no row found create a new one
152 return AddRow(glyphWidth, glyphHeight);
153 }
154