1 /****************************************************************************
2 * MeshLab o o *
3 * An extendible mesh processor o o *
4 * _ O _ *
5 * Copyright(C) 2005, 2009 \/)\/ *
6 * Visual Computing Lab /\/| *
7 * ISTI - Italian National Research Council | *
8 * \ *
9 * All rights reserved. *
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the GNU General Public License as published by *
13 * the Free Software Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 * This program is distributed in the hope that it will be useful, *
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
19 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) *
20 * for more details. *
21 * *
22 ****************************************************************************/
23
24 #include <stdio.h>
25 #include <assert.h>
26 #include <algorithm>
27
28 #include "rect_packer.h"
29
30 using namespace std;
31
32 class point2iConf
33 {
34 public:
35 const std::vector<Point2i> & v;
36
point2iConf(const std::vector<Point2i> & nv)37 inline point2iConf( const std::vector<Point2i> & nv ) : v(nv) { }
38
operator ()(int a,int b)39 inline bool operator() ( int a, int b )
40 {
41 return v[a]>v[b];
42 //return v[a][0]*v[a][1]>v[b][0]*v[b][1];
43 }
44 };
45
46 /*
47 1) 'sizes' is a vector of points corresponding to the width/height of each texture
48 2) 'max_size' is a single point that represents the maximum height/width of the texture atlas you want to create
49 3) 'posiz' is a vector of points that indicate for each texture in 'sizes', where to place this texture in the texture atlas (initially this would be empty)
50 4) 'global_size' represents the minimum height/width necessary to encompass the resulting texture atlas (initially null)
51 */
pack(const std::vector<Point2i> & sizes,const Point2i & max_size,std::vector<Point2i> & posiz,Point2i & global_size)52 bool rect_packer::pack(const std::vector<Point2i> & sizes, const Point2i & max_size, std::vector<Point2i> & posiz, Point2i & global_size)
53 {
54 int n = (int)(sizes.size());
55 if (n<=0)
56 return false;
57 //assert(n>0);
58 assert(max_size[0]>0);
59 assert(max_size[1]>0);
60
61 int gdim = max_size[0]*max_size[1]; // grid size
62 int i,j,x,y;
63
64 posiz.resize(n);
65 for(i=0;i<n;i++) // reset initial positions
66 posiz[i][0] = -1;
67
68 std::vector<int> grid(gdim); // grid creation
69 for(i=0;i<gdim;++i) grid[i] = 0;
70
71 #define Grid(q,w) (grid[(q)+(w)*max_size[0]])
72
73 std::vector<int> perm(n); // permutation creation - vector, one element for each size in sizes - this is what you want the result of
74 for(i=0;i<n;i++) perm[i] = i;
75 point2iConf conf(sizes);
76 sort(perm.begin(),perm.end(),conf);
77
78 if(sizes[perm[0]][0]>max_size[0] ||
79 sizes[perm[0]][1]>max_size[1] )
80 return false;
81
82 // Find the position of the first one
83 j = perm[0];
84 global_size[0] = sizes[j][0];
85 global_size[1] = sizes[j][1];
86 posiz[j][0] = 0;
87 posiz[j][1] = 0;
88 for(y=0;y<global_size[1];y++)
89 for(x=0;x<global_size[0];x++)
90 {
91 assert(x>=0);
92 assert(x<max_size[0]);
93 assert(y>=0);
94 assert(y<max_size[1]);
95 grid[x+y*max_size[0]] = j+1;
96 }
97
98 // Lets position all the others
99 for(i=1;i<n;++i)
100 {
101 j = perm[i];
102 assert(j>=0);
103 assert(j<n);
104 assert(posiz[j][0]==-1);
105
106 int bestx,besty,bestsx,bestsy,besta;
107
108 besta = -1;
109
110 int sx = sizes[j][0]; // it is easier to copy the sizes
111 int sy = sizes[j][1];
112 assert(sx>0);
113 assert(sy>0);
114
115 // limit positions
116 int lx = min(global_size[0],max_size[0]-sx);
117 int ly = min(global_size[1],max_size[1]-sy);
118
119 assert(lx>0);
120 assert(ly>0);
121
122 int finterior = 0;
123
124 for(y=0;y<=ly;y++)
125 {
126 for(x=0;x<=lx;)
127 {
128 int px;
129 int c;
130 // intersection check
131 c = Grid(x,y+sy-1);
132 if(!c) c = Grid(x+sx-1,y+sy-1);
133 if(!c)
134 {
135 for(px=x;px<x+sx;px++)
136 {
137 c = Grid(px,y);
138 if(c) break;
139 }
140 }
141
142 if(c) // do not consider this rectangle
143 {
144 --c;
145 assert(c>=0);
146 assert(c<n);
147 assert(posiz[c][0]!=-1);
148 x = posiz[c][0] + sizes[c][0];
149 }
150 else
151 {
152 int nsx = max(global_size[0],x+sx);
153 int nsy = max(global_size[1],y+sy);
154 int a = nsx*nsy;
155
156 if(besta==-1 || besta>a)
157 {
158 bestx = x;
159 besty = y;
160 bestsx = nsx;
161 bestsy = nsy;
162 besta = a;
163 if( bestsx==global_size[0] && bestsy==global_size[1] )
164 finterior = 1;
165 }
166 break;
167 }
168 if(finterior) break;
169 }
170 if( finterior ) break;
171 }
172
173 if(besta==-1)
174 {
175 return false;
176 }
177
178 posiz[j][0] = bestx;//new U offset for texture at position j
179 posiz[j][1] = besty;//new V offset for texture at position j
180 global_size[0] = bestsx;//holds smallest encompassing width for texture atlas
181 global_size[1] = bestsy;//holds smallest encompassing height for texture atlas
182 for(y=posiz[j][1];y<posiz[j][1]+sy;y++)
183 for(x=posiz[j][0];x<posiz[j][0]+sx;x++)
184 {
185 assert(x>=0);
186 assert(x<max_size[0]);
187 assert(y>=0);
188 assert(y<max_size[1]);
189 grid[x+y*max_size[0]] = j+1;
190 }
191 }
192
193 #if 0
194 // debugging code: it saves into a simple bitmap the computed packing.
195 FILE * fp = fopen("debpack.ppm","wb");
196 fprintf(fp,"P6\n%d %d\n255\n",global_size[0],global_size[1]);
197 for(j=0;j<global_size[1];++j)
198 for(i=0;i<global_size[0];++i)
199 {
200 unsigned char c0[3] = {0,0,0};
201 unsigned char c1[3] = {255,0,0};
202 unsigned char c2[3] = {0,255,0};
203 unsigned char c3[3] = {0,0,255};
204 if( Grid(i,j)==0 ) fwrite(c0,1,3,fp);
205 else if( Grid(i,j)==1 ) fwrite(c1,1,3,fp);
206 else if( Grid(i,j)==2 ) fwrite(c2,1,3,fp);
207 else if( 1/*Grid(i,j)==3*/ ) fwrite(c3,1,3,fp);
208 }
209 fclose(fp);
210 #endif
211
212 #undef Grid
213
214 return true;
215
216 }
217