ppc.backend.packer source code

1 module ppc.backend.packer;
2 import ppc.backend;
3 
4 /++
5     Node used in generating a texture.
6 +/
7 struct FNode {
8     this(PVector origin, PVector size) {
9         this.origin = origin;
10         this.size = size;
11         this.empty = true;
12         this.left = null;
13         this.right = null;
14     }
15 
16     /// Origin of texture
17     PVector origin;
18     
19     /// Size of texture
20     PVector size;
21 
22     /// Wether the node is taken
23     bool empty = true;
24 
25     /// Node branch left
26     FNode* left;
27 
28     /// Node branch right
29     FNode* right;
30 }
31 
32 /++
33     Packing algorithm implementation
34 +/
35 class TexturePacker {
36     /// Size of texture so far
37     PSize textureSize;
38 
39     /// The output buffer
40     ubyte[] buffer;
41 
42     /// The root node for the packing
43     FNode* root;
44 
45     this() {
46         root = new FNode(PVector(0, 0), PVector(int.max, int.max));
47         textureSize = PSize(1024, 1024);
48         buffer = new ubyte[](1024*1024);
49     }
50 
51     /++
52         Packing algorithm
53 
54         Based on the packing algorithm from straypixels.net
55         https://straypixels.net/texture-packing-for-fonts/
56     +/
57     FNode* pack(FNode* node, PVector size) {
58         if (!node.empty) {
59             return null;
60         } else if (node.left !is null && node.right !is null) {
61             FNode* rval = pack(node.left, size);
62             return rval !is null ? rval : pack(node.right, size);
63         } else {
64             PVector realSize = PVector(node.size.x, node.size.y);
65 
66             // Calculate actual size if on boundary
67             if (node.origin.x + node.size.x == int.max) {
68                 realSize.x = textureSize.width-node.origin.x;
69             }
70             if (node.origin.y + node.size.y == int.max) {
71                 realSize.y = textureSize.height-node.origin.y;
72             }
73 
74             
75             if (node.size.x == size.x && node.size.y == size.y) {
76                 // Size is perfect, pack here
77                 node.empty = false;
78                 return node;
79             }
80 
81             // Not big enough?
82             if (realSize.x < size.x || realSize.y < size.y) {
83                 return null;
84             }
85 
86             FNode* left;
87             FNode* right;
88 
89             PVector remain = PVector(realSize.x - size.x, realSize.y - size.y);
90             bool vsplit = remain.x < remain.y;
91             if (remain.x == 0 && remain.y == 0) {
92                 // Edgecase, hitting border of texture atlas perfectly, split at border instead
93                 if (node.size.x > node.size.y) vsplit = false;
94                 else vsplit = true;
95             }
96 
97             if (vsplit) {
98                 left = new FNode(node.origin, PVector(node.size.x, size.y));
99                 right = new FNode(  PVector(node.origin.x, node.origin.y + size.y), 
100                                     PVector(node.size.x, node.size.y - size.y));
101             } else {
102                 left = new FNode(node.origin, PVector(size.x, node.size.y));
103                 right = new FNode(  PVector(node.origin.x + size.x, node.origin.y), 
104                                     PVector(node.size.x - size.x, node.size.y));
105             }
106 
107             node.left = left;
108             node.right = right;
109             return pack(node.left, size);
110         }
111     }
112 
113     void resizeBuffer(PSize newSize) {
114         ubyte[] newBuffer = new ubyte[](newSize.width*newSize.height);
115         foreach(y; 0..textureSize.height) {
116             foreach(x; 0..textureSize.width) {
117                 newBuffer[y * newSize.width + x] = buffer[y * textureSize.width + x];
118             }
119         }
120 
121         textureSize = newSize;
122         buffer = newBuffer;
123     }
124 
125     /++
126         Pack a texture
127 
128         Returns the position that the texture can be found at.
129     +/
130     PVector packTexture(ubyte[] textureBuffer, PVector size) {
131         FNode* node = pack(root, size);
132         if (node == null) {
133             this.resizeBuffer(PSize(textureSize.width*2, textureSize.height*2));
134             node = pack(root, size);
135 
136             assert(node !is null, "Was unable to pack texture!");
137         }
138 
139         assert(size.x == node.size.x, "Sizes did not match! This is as bug in the texture packer.");
140         assert(size.y == node.size.y, "Sizes did not match! This is as bug in the texture packer.");
141 
142         foreach (ly; 0..size.y) {
143             foreach(lx; 0..size.x) {
144                 int y = cast(int)node.origin.y + cast(int)ly;
145                 int x = cast(int)node.origin.x + cast(int)lx;
146                 this.buffer[y * textureSize.width + x] = textureBuffer[ly * size.x + lx];
147             }
148         }
149 
150         return node.origin;
151     }
152 }