1 /*
2     Copyright © 2020, Luna Nielsen
3     Distributed under the 2-Clause BSD License, see LICENSE file.
4     
5     Authors: Luna Nielsen
6 */
7 module engine.render.texture.packer;
8 import gl3n.linalg;
9 import gl3n.math;
10 import std.exception;
11 import engine.core.log;
12 import std.format;
13 import std.algorithm.mutation : remove;
14 
15 private bool contains(vec4i a, vec4i b) {
16     return  a.x >= b.x && 
17             a.y >= b.y &&
18             a.x+a.z <= b.x+b.z &&
19             a.y+a.w <= b.y+b.w;
20 }
21 
22 /**
23     A bin
24 */
25 private struct Bin {
26 private:
27     vec2i size;
28     vec4i[] usedRectangles;
29     vec4i[] freeRectangles;
30 
31     vec4i scoreRect(vec2i size, out int score1, out int score2) {
32         vec4i newNode;
33 
34         // Find the best place to put the rectangle
35         score1 = int.max;
36         score2 = int.max;
37         newNode = findNewNodeFit(size, score1, score2);
38 
39         // reset score
40         if (newNode.w == 0) {
41             score1 = int.max;
42             score2 = int.max;
43         }
44         return newNode;
45     }
46 
47     vec4i scoreRect(vec2i size) {
48         vec4i newNode;
49 
50         // Find the best place to put the rectangle
51         int score1 = int.max;
52         int score2 = int.max;
53         newNode = findNewNodeFit(size, score1, score2);
54 
55         return newNode;
56     }
57 
58     void place(ref vec4i newNode) {
59 
60         // Rectangles to process
61         size_t rectanglesToProcess = freeRectangles.length;
62 
63         // Run through all rectangles
64         for(int i; i < rectanglesToProcess; ++i) {
65 
66             // Try splitting them up
67             if (splitFree(freeRectangles[i], newNode)) {
68                 freeRectangles.remove(i);
69                 --i;
70                 --rectanglesToProcess;
71             }
72         }
73 
74         prune();
75         usedRectangles ~= newNode;
76     }
77     
78     vec4i findNewNodeFit(vec2i size, int score1, int score2) {
79         vec4i bestNode = vec4i.init;
80 
81         int bestShortFit = int.max;
82         int bestLongFit = int.max;
83 
84         foreach(freeRect; freeRectangles) {
85             
86             // Try placing the rectangle in upright orientation
87             if (freeRect.z >= size.x && freeRect.w >= size.y) {
88                 int leftoverH = abs(freeRect.z - size.x);
89                 int leftoverV = abs(freeRect.w - size.y);
90                 int shortSideFit = min(leftoverH, leftoverV);
91                 int longSideFit = max(leftoverH, leftoverV);
92 
93                 if (shortSideFit < bestShortFit || (shortSideFit == bestShortFit && longSideFit < bestLongFit)) {
94                     bestNode.x = freeRect.x;
95                     bestNode.y = freeRect.y;
96                     bestNode.z = size.x;
97                     bestNode.w = size.y;
98                     bestShortFit = shortSideFit;
99                     bestLongFit = longSideFit;
100                 }
101             }
102         }
103 
104         return bestNode;
105     }
106 
107     bool splitFree(vec4i freeNode, ref vec4i usedNode) {
108         if (usedNode.x >= freeNode.x + freeNode.z || usedNode.x + usedNode.z <= freeNode.x ||
109             usedNode.y >= freeNode.y + freeNode.w || usedNode.y + usedNode.w <= freeNode.y) 
110             return false;
111 
112         // Vertical Splitting
113         if (usedNode.x < freeNode.x + freeNode.z && usedNode.x + usedNode.z > freeNode.x) {
114 
115             // New node at top of used
116             if (usedNode.y > freeNode.y && usedNode.y < freeNode.y + freeNode.w) {
117                 vec4i newNode = freeNode;
118                 newNode.w = usedNode.y - newNode.y;
119                 freeRectangles ~= newNode;
120             }
121 
122             // New node at bottom of used
123             if (usedNode.y + usedNode.w < freeNode.y + freeNode.w) {
124                 vec4i newNode = freeNode;
125                 newNode.y = usedNode.y + usedNode.w;
126                 newNode.w = freeNode.y + freeNode.w - (usedNode.y + usedNode.w);
127                 freeRectangles ~= newNode;
128             }
129         }
130 
131         // Horizontal Splitting
132         if (usedNode.y < freeNode.y + freeNode.w && usedNode.y + usedNode.w > freeNode.y) {
133 
134             // New node at left of used
135             if (usedNode.x > freeNode.x && usedNode.x < freeNode.x + freeNode.z) {
136                 vec4i newNode = freeNode;
137                 newNode.z = usedNode.x - newNode.x;
138                 freeRectangles ~= newNode;
139             }
140 
141             // New node at right of used
142             if (usedNode.x + usedNode.z < freeNode.x + freeNode.z) {
143                 vec4i newNode = freeNode;
144                 newNode.x = usedNode.x + usedNode.z;
145                 newNode.z = freeNode.x + freeNode.z - (usedNode.x + usedNode.z);
146                 freeRectangles ~= newNode;
147             }
148         }
149         return true;
150     }
151 
152     void prune() {
153         for(int i; i < freeRectangles.length; ++i) {
154             for(int j = i+1; j < freeRectangles.length; ++j) {
155 
156 
157                 if (freeRectangles[i].contains(freeRectangles[j])) {
158                     freeRectangles = freeRectangles.remove(i);
159                     --i;
160                     break;
161                 }
162 
163                 if (freeRectangles[j].contains(freeRectangles[i])) {
164                     freeRectangles = freeRectangles.remove(j);
165                     --j;
166                 }
167             }
168         }
169     }
170 
171 public:
172     this(vec2i size) {
173         this.size = size;
174         freeRectangles = [vec4i(0, 0, size.x, size.y)];
175     }
176 
177     /**
178         Inserts a new rectangle in to the bin
179     */
180     vec4i insert(vec2i size) {
181         int score1;
182         int score2;
183         vec4i newNode = scoreRect(size, score1, score2);
184 
185         // Place rectangle in to bin
186         place(newNode);
187         return newNode;
188     }
189 
190     /**
191         Removes the area from the packing
192     */
193     void remove(vec4i area) {
194         foreach(i, rect; usedRectangles) {
195             if (rect == area) {
196                 usedRectangles = usedRectangles.remove(i);
197                 break;
198             }
199         }
200         freeRectangles ~= area;
201     }
202 
203     void clear() {
204         freeRectangles = [vec4i(0, 0, size.x, size.y)];
205         usedRectangles = [];
206     }
207 
208     /**
209         Gets ratio of surface area used
210     */
211     float occupancy() {
212         ulong surfaceArea = 0;
213         foreach(rect; usedRectangles) {
214             surfaceArea += rect.z*rect.w;
215         }
216         return surfaceArea / (size.x*size.y);
217     }
218 }
219 
220 
221 class TexturePacker {
222 private:
223     Bin bin;
224 
225 public:
226 
227     /**
228         Max size of texture packer
229     */
230     this(vec2i textureSize = vec2i(1024, 1024)) {
231         bin = Bin(textureSize);
232     }
233 
234     /**
235         Packs a texture in to the bin
236 
237         Returns a vec4i(0, 0, 0, 0) on packing failure
238     */
239     vec4i packTexture(vec2i size) {
240         return bin.insert(size);
241     }
242 
243     /**
244         Remove an area from the texture packer
245     */
246     void remove(vec4i area) {
247         bin.remove(area);
248     }
249 
250     /**
251         Clear the texture packer
252     */
253     void clear() {
254         bin.clear();
255     }
256 }