]> git.xonotic.org Git - xonotic/xonotic.git/blob - misc/tools/fft-normalmap-to-heightmap.c
libvorbis-0.dll - 1.3.6
[xonotic/xonotic.git] / misc / tools / fft-normalmap-to-heightmap.c
1 /*
2  *  FFT based normalmap to heightmap converter
3  *  Copyright (C) 2010  Rudolf Polzer
4  *
5  *  This program is free software; you can redistribute it and/or modify
6  *  it under the terms of the GNU General Public License as published by
7  *  the Free Software Foundation; either version 2 of the License, or
8  *  (at your option) any later version.
9  *
10  *  This program is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  *  GNU General Public License for more details.
14  *
15  *  You should have received a copy of the GNU General Public License
16  *  along with this program; if not, write to the Free Software
17  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18  */
19
20 #undef C99
21 #if __STDC_VERSION__ >= 199901L || __cplusplus__
22 #define C99
23 #endif
24
25 #ifdef C99
26 #include <complex.h>
27 #endif
28
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <math.h>
33
34 #include <fftw3.h>
35
36 #define TWO_PI (4*atan2(1,1) * 2)
37
38 int floatcmp(const void *a_, const void *b_)
39 {
40         float a = *(float *)a_;
41         float b = *(float *)b_;
42         if(a < b)
43                 return -1;
44         if(a > b)
45                 return +1;
46         return 0;
47 }
48
49 void nmap_to_hmap(unsigned char *map, const unsigned char *refmap, int w, int h, double scale, double offset, const double *filter, int filterw, int filterh, int renormalize, double highpass, int use_median)
50 {
51         int x, y;
52         int i, j;
53         double fx, fy;
54         double ffx, ffy;
55         double nx, ny, nz;
56         double v, vmin, vmed, vmax;
57 #ifndef C99
58         double save;
59 #endif
60         float *medianbuf = (float *) malloc(w*h * sizeof(*medianbuf));
61         fftw_complex *imgspace1 = (fftw_complex *) fftw_malloc(w*h * sizeof(fftw_complex));
62         fftw_complex *imgspace2 = (fftw_complex *) fftw_malloc(w*h * sizeof(fftw_complex));
63         fftw_complex *freqspace1 = (fftw_complex *) fftw_malloc(w*h * sizeof(fftw_complex));
64         fftw_complex *freqspace2 = (fftw_complex *) fftw_malloc(w*h * sizeof(fftw_complex));
65         fftw_plan i12f1 = fftw_plan_dft_2d(h, w, imgspace1, freqspace1, FFTW_FORWARD, FFTW_ESTIMATE);
66         fftw_plan i22f2 = fftw_plan_dft_2d(h, w, imgspace2, freqspace2, FFTW_FORWARD, FFTW_ESTIMATE);
67         fftw_plan f12i1 = fftw_plan_dft_2d(h, w, freqspace1, imgspace1, FFTW_BACKWARD, FFTW_ESTIMATE);
68
69         for(y = 0; y < h; ++y)
70         for(x = 0; x < w; ++x)
71         {
72                 /*
73                  * unnormalized normals:
74                  * n_x = -dh/dx
75                  * n_y = -dh/dy
76                  * n_z = -dh/dh = -1
77                  * BUT: darkplaces uses inverted normals, n_y actually is dh/dy by image pixel coordinates
78                  */
79                 nx = ((int)map[(w*y+x)*4+2] - 127.5) / 128;
80                 ny = ((int)map[(w*y+x)*4+1] - 127.5) / 128;
81                 nz = ((int)map[(w*y+x)*4+0] - 127.5) / 128;
82
83                 /* reconstruct the derivatives from here */
84 #ifdef C99
85                 imgspace1[(w*y+x)] =  nx / nz * w; /* = dz/dx */
86                 imgspace2[(w*y+x)] = -ny / nz * h; /* = dz/dy */
87 #else
88                 imgspace1[(w*y+x)][0] =  nx / nz * w; /* = dz/dx */
89                 imgspace1[(w*y+x)][1] = 0;
90                 imgspace2[(w*y+x)][0] = -ny / nz * h; /* = dz/dy */
91                 imgspace2[(w*y+x)][1] = 0;
92 #endif
93
94                 if(renormalize)
95                 {
96                         double v = nx * nx + ny * ny + nz * nz;
97                         if(v > 0)
98                         {
99                                 v = 1/sqrt(v);
100                                 nx *= v;
101                                 ny *= v;
102                                 nz *= v;
103                                 map[(w*y+x)*4+2] = floor(nx * 127.5 + 128);
104                                 map[(w*y+x)*4+1] = floor(ny * 127.5 + 128);
105                                 map[(w*y+x)*4+0] = floor(nz * 127.5 + 128);
106                         }
107                 }
108         }
109
110         /* see http://www.gamedev.net/community/forums/topic.asp?topic_id=561430 */
111
112         fftw_execute(i12f1);
113         fftw_execute(i22f2);
114         
115         for(y = 0; y < h; ++y)
116         for(x = 0; x < w; ++x)
117         {
118                 fx = x * 1.0 / w;
119                 fy = y * 1.0 / h;
120                 if(fx > 0.5)
121                         fx -= 1;
122                 if(fy > 0.5)
123                         fy -= 1;
124                 if(filter)
125                 {
126                         /* discontinous case; we must invert whatever "filter" would do on (x, y)! */
127 #ifdef C99
128                         fftw_complex response_x = 0;
129                         fftw_complex response_y = 0;
130                         double sum;
131                         for(i = -filterh / 2; i <= filterh / 2; ++i)
132                                 for(j = -filterw / 2; j <= filterw / 2; ++j)
133                                 {
134                                         response_x += filter[(i + filterh / 2) * filterw + j + filterw / 2] * cexp(-_Complex_I * TWO_PI * (j * fx + i * fy));
135                                         response_y += filter[(i + filterh / 2) * filterw + j + filterw / 2] * cexp(-_Complex_I * TWO_PI * (i * fx + j * fy));
136                                 }
137
138                         /*
139                          * we know:
140                          *   fourier(df/dx)_xy = fourier(f)_xy * response_x
141                          *   fourier(df/dy)_xy = fourier(f)_xy * response_y
142                          * mult by conjugate of response_x, response_y:
143                          *   conj(response_x) * fourier(df/dx)_xy = fourier(f)_xy * |response_x^2|
144                          *   conj(response_y) * fourier(df/dy)_xy = fourier(f)_xy * |response_y^2|
145                          * and
146                          *   fourier(f)_xy = (conj(response_x) * fourier(df/dx)_xy + conj(response_y) * fourier(df/dy)_xy) / (|response_x|^2 + |response_y|^2)
147                          */
148
149                         sum = cabs(response_x) * cabs(response_x) + cabs(response_y) * cabs(response_y);
150
151                         if(sum > 0)
152                                 freqspace1[(w*y+x)] = (conj(response_x) * freqspace1[(w*y+x)] + conj(response_y) * freqspace2[(w*y+x)]) / sum;
153                         else
154                                 freqspace1[(w*y+x)] = 0;
155 #else
156                         fftw_complex response_x = {0, 0};
157                         fftw_complex response_y = {0, 0};
158                         double sum;
159                         for(i = -filterh / 2; i <= filterh / 2; ++i)
160                                 for(j = -filterw / 2; j <= filterw / 2; ++j)
161                                 {
162                                         response_x[0] += filter[(i + filterh / 2) * filterw + j + filterw / 2] * cos(-TWO_PI * (j * fx + i * fy));
163                                         response_x[1] += filter[(i + filterh / 2) * filterw + j + filterw / 2] * sin(-TWO_PI * (j * fx + i * fy));
164                                         response_y[0] += filter[(i + filterh / 2) * filterw + j + filterw / 2] * cos(-TWO_PI * (i * fx + j * fy));
165                                         response_y[1] += filter[(i + filterh / 2) * filterw + j + filterw / 2] * sin(-TWO_PI * (i * fx + j * fy));
166                                 }
167
168                         sum = response_x[0] * response_x[0] + response_x[1] * response_x[1]
169                             + response_y[0] * response_y[0] + response_y[1] * response_y[1];
170
171                         if(sum > 0)
172                         {
173                                 double s = freqspace1[(w*y+x)][0];
174                                 freqspace1[(w*y+x)][0] = (response_x[0] * s                      + response_x[1] * freqspace1[(w*y+x)][1] + response_y[0] * freqspace2[(w*y+x)][0] + response_y[1] * freqspace2[(w*y+x)][1]) / sum;
175                                 freqspace1[(w*y+x)][1] = (response_x[0] * freqspace1[(w*y+x)][1] - response_x[1] * s                      + response_y[0] * freqspace2[(w*y+x)][1] - response_y[1] * freqspace2[(w*y+x)][0]) / sum;
176                         }
177                         else
178                         {
179                                 freqspace1[(w*y+x)][0] = 0;
180                                 freqspace1[(w*y+x)][1] = 0;
181                         }
182 #endif
183                 }
184                 else
185                 {
186                         /* continuous integration case */
187                         /* these must have the same sign as fx and fy (so ffx*fx + ffy*fy is nonzero), otherwise do not matter */
188                         /* it basically decides how artifacts are distributed */
189                         ffx = fx;
190                         ffy = fy;
191 #ifdef C99
192                         if(fx||fy)
193                                 freqspace1[(w*y+x)] = _Complex_I * (ffx * freqspace1[(w*y+x)] + ffy * freqspace2[(w*y+x)]) / (ffx*fx + ffy*fy) / TWO_PI;
194                         else
195                                 freqspace1[(w*y+x)] = 0;
196 #else
197                         if(fx||fy)
198                         {
199                                 save = freqspace1[(w*y+x)][0];
200                                 freqspace1[(w*y+x)][0] = -(ffx * freqspace1[(w*y+x)][1] + ffy * freqspace2[(w*y+x)][1]) / (ffx*fx + ffy*fy) / TWO_PI;
201                                 freqspace1[(w*y+x)][1] =  (ffx * save + ffy * freqspace2[(w*y+x)][0]) / (ffx*fx + ffy*fy) / TWO_PI;
202                         }
203                         else
204                         {
205                                 freqspace1[(w*y+x)][0] = 0;
206                                 freqspace1[(w*y+x)][1] = 0;
207                         }
208 #endif
209                 }
210                 if(highpass > 0)
211                 {
212                         double f1 = (fabs(fx)*highpass);
213                         double f2 = (fabs(fy)*highpass);
214                         /* if either of them is < 1, phase out (min at 0.5) */
215                         double f =
216                                 (f1 <= 0.5 ? 0 : (f1 >= 1 ? 1 : ((f1 - 0.5) * 2.0)))
217                                 *
218                                 (f2 <= 0.5 ? 0 : (f2 >= 1 ? 1 : ((f2 - 0.5) * 2.0)));
219 #ifdef C99
220                         freqspace1[(w*y+x)] *= f;
221 #else
222                         freqspace1[(w*y+x)][0] *= f;
223                         freqspace1[(w*y+x)][1] *= f;
224 #endif
225                 }
226         }
227
228         fftw_execute(f12i1);
229
230         /* renormalize, find min/max */
231         vmin = vmed = vmax = 0;
232         for(y = 0; y < h; ++y)
233         for(x = 0; x < w; ++x)
234         {
235 #ifdef C99
236                 v = creal(imgspace1[(w*y+x)] /= pow(w*h, 1.5));
237 #else
238                 v = (imgspace1[(w*y+x)][0] /= pow(w*h, 1.5));
239                 /*
240                  * imgspace1[(w*y+x)][1] /= pow(w*h, 1.5);
241                  * this value is never used
242                  */
243 #endif
244                 if(v < vmin || (x == 0 && y == 0))
245                         vmin = v;
246                 if(v > vmax || (x == 0 && y == 0))
247                         vmax = v;
248                 medianbuf[w*y+x] = v;
249         }
250         qsort(medianbuf, w*h, sizeof(*medianbuf), floatcmp);
251         if(w*h % 2)
252                 vmed = medianbuf[(w*h-1)/2];
253         else
254                 vmed = (medianbuf[(w*h)/2] + medianbuf[(w*h-2)/2]) * 0.5;
255
256         if(refmap)
257         {
258                 double f, a;
259                 double o, s;
260                 double sa, sfa, sffa, sfva, sva;
261                 double mi, ma;
262                 sa = sfa = sffa = sfva = sva = 0;
263                 mi = 1;
264                 ma = -1;
265                 for(y = 0; y < h; ++y)
266                 for(x = 0; x < w; ++x)
267                 {
268                         a = (int)refmap[(w*y+x)*4+3];
269                         v = (refmap[(w*y+x)*4+0]*0.114 + refmap[(w*y+x)*4+1]*0.587 + refmap[(w*y+x)*4+2]*0.299);
270                         v = (v - 128.0) / 127.0;
271 #ifdef C99
272                         f = creal(imgspace1[(w*y+x)]);
273 #else
274                         f = imgspace1[(w*y+x)][0];
275 #endif
276                         if(a <= 0)
277                                 continue;
278                         if(v < mi)
279                                 mi = v;
280                         if(v > ma)
281                                 ma = v;
282                         sa += a;
283                         sfa += f*a;
284                         sffa += f*f*a;
285                         sfva += f*v*a;
286                         sva += v*a;
287                 }
288                 if(mi < ma)
289                 {
290                         /* linear regression ftw */
291                         o = (sfa*sfva - sffa*sva) / (sfa*sfa-sa*sffa);
292                         s = (sfa*sva - sa*sfva) / (sfa*sfa-sa*sffa);
293                 }
294                 else /* all values of v are equal, so we cannot get scale; we can still get offset */
295                 {
296                         o = ((sva - sfa) / sa);
297                         s = 1;
298                 }
299
300                 /*
301                  * now apply user-given offset and scale to these values
302                  * (x * s + o) * scale + offset
303                  * x * s * scale + o * scale + offset
304                  */
305                 offset += o * scale;
306                 scale *= s;
307         }
308         else if(scale == 0)
309         {
310                 /*
311                  * map vmin to -1
312                  * map vmax to +1
313                  */
314                 scale = 2 / (vmax - vmin);
315                 offset = -(vmax + vmin) / (vmax - vmin);
316         }
317         else if(use_median)
318         {
319                 /*
320                  * negative scale = match median to offset
321                  * we actually want (v - vmed) * scale + offset
322                  */
323                 offset -= vmed * scale;
324         }
325
326         printf("Min: %f\nAvg: %f\nMed: %f\nMax: %f\nScale: %f\nOffset: %f\nScaled-Min: %f\nScaled-Avg: %f\nScaled-Med: %f\nScaled-Max: %f\n", 
327                 vmin, 0.0, vmed, vmax, scale, offset, vmin * scale + offset, offset, vmed * scale + offset, vmax * scale + offset);
328
329         for(y = 0; y < h; ++y)
330         for(x = 0; x < w; ++x)
331         {
332 #ifdef C99
333                 v = creal(imgspace1[(w*y+x)]);
334 #else
335                 v = imgspace1[(w*y+x)][0];
336 #endif
337                 v = v * scale + offset;
338                 if(v < -1)
339                         v = -1;
340                 if(v > 1)
341                         v = 1;
342                 map[(w*y+x)*4+3] = floor(128.5 + 127 * v); /* in heightmaps, we avoid pixel value 0 as many imaging apps cannot handle it */
343         }
344
345         fftw_destroy_plan(i12f1);
346         fftw_destroy_plan(i22f2);
347         fftw_destroy_plan(f12i1);
348
349         fftw_free(freqspace2);
350         fftw_free(freqspace1);
351         fftw_free(imgspace2);
352         fftw_free(imgspace1);
353         free(medianbuf);
354 }
355
356 void hmap_to_nmap(unsigned char *map, int w, int h, int src_chan, double scale)
357 {
358         int x, y;
359         double fx, fy;
360         double nx, ny, nz;
361         double v;
362 #ifndef C99
363         double save;
364 #endif
365
366         fftw_complex *imgspace1 = (fftw_complex *) fftw_malloc(w*h * sizeof(fftw_complex));
367         fftw_complex *imgspace2 = (fftw_complex *) fftw_malloc(w*h * sizeof(fftw_complex));
368         fftw_complex *freqspace1 = (fftw_complex *) fftw_malloc(w*h * sizeof(fftw_complex));
369         fftw_complex *freqspace2 = (fftw_complex *) fftw_malloc(w*h * sizeof(fftw_complex));
370         fftw_plan i12f1 = fftw_plan_dft_2d(h, w, imgspace1, freqspace1, FFTW_FORWARD, FFTW_ESTIMATE);
371         fftw_plan f12i1 = fftw_plan_dft_2d(h, w, freqspace1, imgspace1, FFTW_BACKWARD, FFTW_ESTIMATE);
372         fftw_plan f22i2 = fftw_plan_dft_2d(h, w, freqspace2, imgspace2, FFTW_BACKWARD, FFTW_ESTIMATE);
373
374         for(y = 0; y < h; ++y)
375         for(x = 0; x < w; ++x)
376         {
377                 switch(src_chan)
378                 {
379                         case 0:
380                         case 1:
381                         case 2:
382                         case 3:
383                                 v = map[(w*y+x)*4+src_chan];
384                                 break;
385                         case 4:
386                                 v = (map[(w*y+x)*4+0] + map[(w*y+x)*4+1] + map[(w*y+x)*4+2]) / 3;
387                                 break;
388                         default:
389                         case 5:
390                                 v = (map[(w*y+x)*4+0]*0.114 + map[(w*y+x)*4+1]*0.587 + map[(w*y+x)*4+2]*0.299);
391                                 break;
392                 }
393 #ifdef C99
394                 imgspace1[(w*y+x)] = (v - 128.0) / 127.0;
395 #else
396                 imgspace1[(w*y+x)][0] = (v - 128.0) / 127.0;
397                 imgspace1[(w*y+x)][1] = 0;
398 #endif
399                 if(v < 1)
400                         v = 1; /* do not write alpha zero */
401                 map[(w*y+x)*4+3] = floor(v + 0.5);
402         }
403
404         /* see http://www.gamedev.net/community/forums/topic.asp?topic_id=561430 */
405
406         fftw_execute(i12f1);
407         
408         for(y = 0; y < h; ++y)
409         for(x = 0; x < w; ++x)
410         {
411                 fx = x;
412                 fy = y;
413                 if(fx > w/2)
414                         fx -= w;
415                 if(fy > h/2)
416                         fy -= h;
417 #ifdef DISCONTINUOUS
418                 fx = sin(fx * TWO_PI / w);
419                 fy = sin(fy * TWO_PI / h);
420 #else
421 #ifdef C99
422                 /* a lowpass to prevent the worst */
423                 freqspace1[(w*y+x)] *= 1 - pow(abs(fx) / (double)(w/2), 1);
424                 freqspace1[(w*y+x)] *= 1 - pow(abs(fy) / (double)(h/2), 1);
425 #else
426                 /* a lowpass to prevent the worst */
427                 freqspace1[(w*y+x)][0] *= 1 - pow(abs(fx) / (double)(w/2), 1);
428                 freqspace1[(w*y+x)][1] *= 1 - pow(abs(fx) / (double)(w/2), 1);
429                 freqspace1[(w*y+x)][0] *= 1 - pow(abs(fy) / (double)(h/2), 1);
430                 freqspace1[(w*y+x)][1] *= 1 - pow(abs(fy) / (double)(h/2), 1);
431 #endif
432 #endif
433 #ifdef C99
434                 freqspace2[(w*y+x)] = TWO_PI*_Complex_I * fy * freqspace1[(w*y+x)]; /* y derivative */
435                 freqspace1[(w*y+x)] = TWO_PI*_Complex_I * fx * freqspace1[(w*y+x)]; /* x derivative */
436 #else
437                 freqspace2[(w*y+x)][0] = -TWO_PI * fy * freqspace1[(w*y+x)][1]; /* y derivative */
438                 freqspace2[(w*y+x)][1] =  TWO_PI * fy * freqspace1[(w*y+x)][0];
439                 save = freqspace1[(w*y+x)][0];
440                 freqspace1[(w*y+x)][0] = -TWO_PI * fx * freqspace1[(w*y+x)][1]; /* x derivative */
441                 freqspace1[(w*y+x)][1] =  TWO_PI * fx * save;
442 #endif
443         }
444
445         fftw_execute(f12i1);
446         fftw_execute(f22i2);
447
448         scale /= (w*h);
449
450         for(y = 0; y < h; ++y)
451         for(x = 0; x < w; ++x)
452         {
453 #ifdef C99
454                 nx = creal(imgspace1[(w*y+x)]);
455                 ny = creal(imgspace2[(w*y+x)]);
456 #else
457                 nx = imgspace1[(w*y+x)][0];
458                 ny = imgspace2[(w*y+x)][0];
459 #endif
460                 nx /= w;
461                 ny /= h;
462                 nz = -1 / scale;
463                 v = -sqrt(nx*nx + ny*ny + nz*nz);
464                 nx /= v;
465                 ny /= v;
466                 nz /= v;
467                 ny = -ny; /* DP inverted normals */
468                 map[(w*y+x)*4+2] = floor(128 + 127.5 * nx);
469                 map[(w*y+x)*4+1] = floor(128 + 127.5 * ny);
470                 map[(w*y+x)*4+0] = floor(128 + 127.5 * nz);
471         }
472
473         fftw_destroy_plan(i12f1);
474         fftw_destroy_plan(f12i1);
475         fftw_destroy_plan(f22i2);
476
477         fftw_free(freqspace2);
478         fftw_free(freqspace1);
479         fftw_free(imgspace2);
480         fftw_free(imgspace1);
481 }
482
483 void hmap_to_nmap_local(unsigned char *map, int w, int h, int src_chan, double scale, const double *filter, int filterw, int filterh)
484 {
485         int x, y;
486         double nx, ny, nz;
487         double v;
488         int i, j;
489         double *img_reduced = (double *) malloc(w*h * sizeof(double));
490
491         for(y = 0; y < h; ++y)
492         for(x = 0; x < w; ++x)
493         {
494                 switch(src_chan)
495                 {
496                         case 0:
497                         case 1:
498                         case 2:
499                         case 3:
500                                 v = map[(w*y+x)*4+src_chan];
501                                 break;
502                         case 4:
503                                 v = (map[(w*y+x)*4+0] + map[(w*y+x)*4+1] + map[(w*y+x)*4+2]) / 3;
504                                 break;
505                         default:
506                         case 5:
507                                 v = (map[(w*y+x)*4+0]*0.114 + map[(w*y+x)*4+1]*0.587 + map[(w*y+x)*4+2]*0.299);
508                                 break;
509                 }
510                 img_reduced[(w*y+x)] = (v - 128.0) / 127.0;
511                 if(v < 1)
512                         v = 1; /* do not write alpha zero */
513                 map[(w*y+x)*4+3] = floor(v + 0.5);
514         }
515
516         for(y = 0; y < h; ++y)
517         for(x = 0; x < w; ++x)
518         {
519                 nz = -1 / scale;
520                 nx = ny = 0;
521
522                 for(i = -filterh / 2; i <= filterh / 2; ++i)
523                         for(j = -filterw / 2; j <= filterw / 2; ++j)
524                         {
525                                 nx += img_reduced[w*((y+i+h)%h)+(x+j+w)%w] * filter[(i + filterh / 2) * filterw + j + filterw / 2];
526                                 ny += img_reduced[w*((y+j+h)%h)+(x+i+w)%w] * filter[(i + filterh / 2) * filterw + j + filterw / 2];
527                         }
528
529                 v = -sqrt(nx*nx + ny*ny + nz*nz);
530                 nx /= v;
531                 ny /= v;
532                 nz /= v;
533                 ny = -ny; /* DP inverted normals */
534                 map[(w*y+x)*4+2] = floor(128 + 127.5 * nx);
535                 map[(w*y+x)*4+1] = floor(128 + 127.5 * ny);
536                 map[(w*y+x)*4+0] = floor(128 + 127.5 * nz);
537         }
538
539         free(img_reduced);
540 }
541
542 unsigned char *FS_LoadFile(const char *fn, int *len)
543 {
544         unsigned char *buf = NULL;
545         int n;
546         FILE *f = fopen(fn, "rb");
547         *len = 0;
548         if(!f)
549                 return NULL;
550         for(;;)
551         {
552                 buf = (unsigned char *) realloc(buf, *len + 65536);
553                 if(!buf)
554                 {
555                         fclose(f);
556                         free(buf);
557                         *len = 0;
558                         return NULL;
559                 }
560                 n = fread(buf + *len, 1, 65536, f);
561                 if(n < 0)
562                 {
563                         fclose(f);
564                         free(buf);
565                         *len = 0;
566                         return NULL;
567                 }
568                 *len += n;
569                 if(n < 65536)
570                         break;
571         }
572         return buf;
573 }
574
575 int FS_WriteFile(const char *fn, unsigned char *data, int len)
576 {
577         FILE *f = fopen(fn, "wb");
578         if(!f)
579                 return 0;
580         if(fwrite(data, len, 1, f) != 1)
581         {
582                 fclose(f);
583                 return 0;
584         }
585         if(fclose(f))
586                 return 0;
587         return 1;
588 }
589
590 /* START stuff that originates from image.c in DarkPlaces */
591 int image_width, image_height;
592
593 typedef struct _TargaHeader
594 {
595         unsigned char   id_length, colormap_type, image_type;
596         unsigned short  colormap_index, colormap_length;
597         unsigned char   colormap_size;
598         unsigned short  x_origin, y_origin, width, height;
599         unsigned char   pixel_size, attributes;
600 }
601 TargaHeader;
602
603 void PrintTargaHeader(TargaHeader *t)
604 {
605         printf("TargaHeader:\nuint8 id_length = %i;\nuint8 colormap_type = %i;\nuint8 image_type = %i;\nuint16 colormap_index = %i;\nuint16 colormap_length = %i;\nuint8 colormap_size = %i;\nuint16 x_origin = %i;\nuint16 y_origin = %i;\nuint16 width = %i;\nuint16 height = %i;\nuint8 pixel_size = %i;\nuint8 attributes = %i;\n", t->id_length, t->colormap_type, t->image_type, t->colormap_index, t->colormap_length, t->colormap_size, t->x_origin, t->y_origin, t->width, t->height, t->pixel_size, t->attributes);
606 }
607
608 unsigned char *LoadTGA_BGRA (const unsigned char *f, int filesize)
609 {
610         int x, y, pix_inc, row_inci, runlen, alphabits;
611         unsigned char *image_buffer;
612         unsigned int *pixbufi;
613         const unsigned char *fin, *enddata;
614         TargaHeader targa_header;
615         unsigned int palettei[256];
616         union
617         {
618                 unsigned int i;
619                 unsigned char b[4];
620         }
621         bgra;
622
623         if (filesize < 19)
624                 return NULL;
625
626         enddata = f + filesize;
627
628         targa_header.id_length = f[0];
629         targa_header.colormap_type = f[1];
630         targa_header.image_type = f[2];
631
632         targa_header.colormap_index = f[3] + f[4] * 256;
633         targa_header.colormap_length = f[5] + f[6] * 256;
634         targa_header.colormap_size = f[7];
635         targa_header.x_origin = f[8] + f[9] * 256;
636         targa_header.y_origin = f[10] + f[11] * 256;
637         targa_header.width = image_width = f[12] + f[13] * 256;
638         targa_header.height = image_height = f[14] + f[15] * 256;
639         targa_header.pixel_size = f[16];
640         targa_header.attributes = f[17];
641
642         if (image_width > 32768 || image_height > 32768 || image_width <= 0 || image_height <= 0)
643         {
644                 printf("LoadTGA: invalid size\n");
645                 PrintTargaHeader(&targa_header);
646                 return NULL;
647         }
648
649         /* advance to end of header */
650         fin = f + 18;
651
652         /* skip TARGA image comment (usually 0 bytes) */
653         fin += targa_header.id_length;
654
655         /* read/skip the colormap if present (note: according to the TARGA spec it */
656         /* can be present even on 1color or greyscale images, just not used by */
657         /* the image data) */
658         if (targa_header.colormap_type)
659         {
660                 if (targa_header.colormap_length > 256)
661                 {
662                         printf("LoadTGA: only up to 256 colormap_length supported\n");
663                         PrintTargaHeader(&targa_header);
664                         return NULL;
665                 }
666                 if (targa_header.colormap_index)
667                 {
668                         printf("LoadTGA: colormap_index not supported\n");
669                         PrintTargaHeader(&targa_header);
670                         return NULL;
671                 }
672                 if (targa_header.colormap_size == 24)
673                 {
674                         for (x = 0;x < targa_header.colormap_length;x++)
675                         {
676                                 bgra.b[0] = *fin++;
677                                 bgra.b[1] = *fin++;
678                                 bgra.b[2] = *fin++;
679                                 bgra.b[3] = 255;
680                                 palettei[x] = bgra.i;
681                         }
682                 }
683                 else if (targa_header.colormap_size == 32)
684                 {
685                         memcpy(palettei, fin, targa_header.colormap_length*4);
686                         fin += targa_header.colormap_length * 4;
687                 }
688                 else
689                 {
690                         printf("LoadTGA: Only 32 and 24 bit colormap_size supported\n");
691                         PrintTargaHeader(&targa_header);
692                         return NULL;
693                 }
694         }
695
696         /* check our pixel_size restrictions according to image_type */
697         switch (targa_header.image_type & ~8)
698         {
699         case 2:
700                 if (targa_header.pixel_size != 24 && targa_header.pixel_size != 32)
701                 {
702                         printf("LoadTGA: only 24bit and 32bit pixel sizes supported for type 2 and type 10 images\n");
703                         PrintTargaHeader(&targa_header);
704                         return NULL;
705                 }
706                 break;
707         case 3:
708                 /* set up a palette to make the loader easier */
709                 for (x = 0;x < 256;x++)
710                 {
711                         bgra.b[0] = bgra.b[1] = bgra.b[2] = x;
712                         bgra.b[3] = 255;
713                         palettei[x] = bgra.i;
714                 }
715                 /* fall through to colormap case */
716         case 1:
717                 if (targa_header.pixel_size != 8)
718                 {
719                         printf("LoadTGA: only 8bit pixel size for type 1, 3, 9, and 11 images supported\n");
720                         PrintTargaHeader(&targa_header);
721                         return NULL;
722                 }
723                 break;
724         default:
725                 printf("LoadTGA: Only type 1, 2, 3, 9, 10, and 11 targa RGB images supported, image_type = %i\n", targa_header.image_type);
726                 PrintTargaHeader(&targa_header);
727                 return NULL;
728         }
729
730         if (targa_header.attributes & 0x10)
731         {
732                 printf("LoadTGA: origin must be in top left or bottom left, top right and bottom right are not supported\n");
733                 return NULL;
734         }
735
736         /* number of attribute bits per pixel, we only support 0 or 8 */
737         alphabits = targa_header.attributes & 0x0F;
738         if (alphabits != 8 && alphabits != 0)
739         {
740                 printf("LoadTGA: only 0 or 8 attribute (alpha) bits supported\n");
741                 return NULL;
742         }
743
744         image_buffer = (unsigned char *)malloc(image_width * image_height * 4);
745         if (!image_buffer)
746         {
747                 printf("LoadTGA: not enough memory for %i by %i image\n", image_width, image_height);
748                 return NULL;
749         }
750
751         /* If bit 5 of attributes isn't set, the image has been stored from bottom to top */
752         if ((targa_header.attributes & 0x20) == 0)
753         {
754                 pixbufi = (unsigned int*)image_buffer + (image_height - 1)*image_width;
755                 row_inci = -image_width*2;
756         }
757         else
758         {
759                 pixbufi = (unsigned int*)image_buffer;
760                 row_inci = 0;
761         }
762
763         x = 0;
764         y = 0;
765         pix_inc = 1;
766         if ((targa_header.image_type & ~8) == 2)
767                 pix_inc = (targa_header.pixel_size + 7) / 8;
768         switch (targa_header.image_type)
769         {
770         case 1: /* colormapped, uncompressed */
771         case 3: /* greyscale, uncompressed */
772                 if (fin + image_width * image_height * pix_inc > enddata)
773                         break;
774                 for (y = 0;y < image_height;y++, pixbufi += row_inci)
775                         for (x = 0;x < image_width;x++)
776                                 *pixbufi++ = palettei[*fin++];
777                 break;
778         case 2:
779                 /* BGR or BGRA, uncompressed */
780                 if (fin + image_width * image_height * pix_inc > enddata)
781                         break;
782                 if (targa_header.pixel_size == 32 && alphabits)
783                 {
784                         for (y = 0;y < image_height;y++)
785                                 memcpy(pixbufi + y * (image_width + row_inci), fin + y * image_width * pix_inc, image_width*4);
786                 }
787                 else
788                 {
789                         for (y = 0;y < image_height;y++, pixbufi += row_inci)
790                         {
791                                 for (x = 0;x < image_width;x++, fin += pix_inc)
792                                 {
793                                         bgra.b[0] = fin[0];
794                                         bgra.b[1] = fin[1];
795                                         bgra.b[2] = fin[2];
796                                         bgra.b[3] = 255;
797                                         *pixbufi++ = bgra.i;
798                                 }
799                         }
800                 }
801                 break;
802         case 9: /* colormapped, RLE */
803         case 11: /* greyscale, RLE */
804                 for (y = 0;y < image_height;y++, pixbufi += row_inci)
805                 {
806                         for (x = 0;x < image_width;)
807                         {
808                                 if (fin >= enddata)
809                                         break; /* error - truncated file */
810                                 runlen = *fin++;
811                                 if (runlen & 0x80)
812                                 {
813                                         /* RLE - all pixels the same color */
814                                         runlen += 1 - 0x80;
815                                         if (fin + pix_inc > enddata)
816                                                 break; /* error - truncated file */
817                                         if (x + runlen > image_width)
818                                                 break; /* error - line exceeds width */
819                                         bgra.i = palettei[*fin++];
820                                         for (;runlen--;x++)
821                                                 *pixbufi++ = bgra.i;
822                                 }
823                                 else
824                                 {
825                                         /* uncompressed - all pixels different color */
826                                         runlen++;
827                                         if (fin + pix_inc * runlen > enddata)
828                                                 break; /* error - truncated file */
829                                         if (x + runlen > image_width)
830                                                 break; /* error - line exceeds width */
831                                         for (;runlen--;x++)
832                                                 *pixbufi++ = palettei[*fin++];
833                                 }
834                         }
835
836                         if (x != image_width)
837                         {
838                                 /* pixbufi is useless now */
839                                 printf("LoadTGA: corrupt file\n");
840                                 break;
841                         }
842                 }
843                 break;
844         case 10:
845                 /* BGR or BGRA, RLE */
846                 if (targa_header.pixel_size == 32 && alphabits)
847                 {
848                         for (y = 0;y < image_height;y++, pixbufi += row_inci)
849                         {
850                                 for (x = 0;x < image_width;)
851                                 {
852                                         if (fin >= enddata)
853                                                 break; /* error - truncated file */
854                                         runlen = *fin++;
855                                         if (runlen & 0x80)
856                                         {
857                                                 /* RLE - all pixels the same color */
858                                                 runlen += 1 - 0x80;
859                                                 if (fin + pix_inc > enddata)
860                                                         break; /* error - truncated file */
861                                                 if (x + runlen > image_width)
862                                                         break; /* error - line exceeds width */
863                                                 bgra.b[0] = fin[0];
864                                                 bgra.b[1] = fin[1];
865                                                 bgra.b[2] = fin[2];
866                                                 bgra.b[3] = fin[3];
867                                                 fin += pix_inc;
868                                                 for (;runlen--;x++)
869                                                         *pixbufi++ = bgra.i;
870                                         }
871                                         else
872                                         {
873                                                 /* uncompressed - all pixels different color */
874                                                 runlen++;
875                                                 if (fin + pix_inc * runlen > enddata)
876                                                         break; /* error - truncated file */
877                                                 if (x + runlen > image_width)
878                                                         break; /* error - line exceeds width */
879                                                 for (;runlen--;x++)
880                                                 {
881                                                         bgra.b[0] = fin[0];
882                                                         bgra.b[1] = fin[1];
883                                                         bgra.b[2] = fin[2];
884                                                         bgra.b[3] = fin[3];
885                                                         fin += pix_inc;
886                                                         *pixbufi++ = bgra.i;
887                                                 }
888                                         }
889                                 }
890
891                                 if (x != image_width)
892                                 {
893                                         /* pixbufi is useless now */
894                                         printf("LoadTGA: corrupt file\n");
895                                         break;
896                                 }
897                         }
898                 }
899                 else
900                 {
901                         for (y = 0;y < image_height;y++, pixbufi += row_inci)
902                         {
903                                 for (x = 0;x < image_width;)
904                                 {
905                                         if (fin >= enddata)
906                                                 break; /* error - truncated file */
907                                         runlen = *fin++;
908                                         if (runlen & 0x80)
909                                         {
910                                                 /* RLE - all pixels the same color */
911                                                 runlen += 1 - 0x80;
912                                                 if (fin + pix_inc > enddata)
913                                                         break; /* error - truncated file */
914                                                 if (x + runlen > image_width)
915                                                         break; /* error - line exceeds width */
916                                                 bgra.b[0] = fin[0];
917                                                 bgra.b[1] = fin[1];
918                                                 bgra.b[2] = fin[2];
919                                                 bgra.b[3] = 255;
920                                                 fin += pix_inc;
921                                                 for (;runlen--;x++)
922                                                         *pixbufi++ = bgra.i;
923                                         }
924                                         else
925                                         {
926                                                 /* uncompressed - all pixels different color */
927                                                 runlen++;
928                                                 if (fin + pix_inc * runlen > enddata)
929                                                         break; /* error - truncated file */
930                                                 if (x + runlen > image_width)
931                                                         break; /* error - line exceeds width */
932                                                 for (;runlen--;x++)
933                                                 {
934                                                         bgra.b[0] = fin[0];
935                                                         bgra.b[1] = fin[1];
936                                                         bgra.b[2] = fin[2];
937                                                         bgra.b[3] = 255;
938                                                         fin += pix_inc;
939                                                         *pixbufi++ = bgra.i;
940                                                 }
941                                         }
942                                 }
943
944                                 if (x != image_width)
945                                 {
946                                         /* pixbufi is useless now */
947                                         printf("LoadTGA: corrupt file\n");
948                                         break;
949                                 }
950                         }
951                 }
952                 break;
953         default:
954                 /* unknown image_type */
955                 break;
956         }
957
958         return image_buffer;
959 }
960
961 int Image_WriteTGABGRA (const char *filename, int width, int height, const unsigned char *data)
962 {
963         int y;
964         unsigned char *buffer, *out;
965         const unsigned char *in, *end;
966         int ret;
967
968         buffer = (unsigned char *)malloc(width*height*4 + 18);
969
970         memset (buffer, 0, 18);
971         buffer[2] = 2;          /* uncompressed type */
972         buffer[12] = (width >> 0) & 0xFF;
973         buffer[13] = (width >> 8) & 0xFF;
974         buffer[14] = (height >> 0) & 0xFF;
975         buffer[15] = (height >> 8) & 0xFF;
976
977         for (y = 3;y < width*height*4;y += 4)
978                 if (data[y] < 255)
979                         break;
980
981         if (y < width*height*4)
982         {
983                 /* save the alpha channel */
984                 buffer[16] = 32;        /* pixel size */
985                 buffer[17] = 8; /* 8 bits of alpha */
986
987                 /* flip upside down */
988                 out = buffer + 18;
989                 for (y = height - 1;y >= 0;y--)
990                 {
991                         memcpy(out, data + y * width * 4, width * 4);
992                         out += width*4;
993                 }
994         }
995         else
996         {
997                 /* save only the color channels */
998                 buffer[16] = 24;        /* pixel size */
999                 buffer[17] = 0; /* 8 bits of alpha */
1000
1001                 /* truncate bgra to bgr and flip upside down */
1002                 out = buffer + 18;
1003                 for (y = height - 1;y >= 0;y--)
1004                 {
1005                         in = data + y * width * 4;
1006                         end = in + width * 4;
1007                         for (;in < end;in += 4)
1008                         {
1009                                 *out++ = in[0];
1010                                 *out++ = in[1];
1011                                 *out++ = in[2];
1012                         }
1013                 }
1014         }
1015         ret = FS_WriteFile (filename, buffer, out - buffer);
1016
1017         free(buffer);
1018
1019         return ret;
1020 }
1021 /* START stuff that originates from image.c in DarkPlaces */
1022
1023 int usage(const char *me)
1024 {
1025         printf("Usage: %s <infile_norm.tga> <outfile_normandheight.tga> filtertype [<scale> [<offset> [<infile_ref.tga>]]] (get heightmap from normalmap)\n", me);
1026         printf("or:    %s <infile_height.tga> <outfile_normandheight.tga> filtertype -1 [<scale>] (read from B)\n", me);
1027         printf("or:    %s <infile_height.tga> <outfile_normandheight.tga> filtertype -2 [<scale>] (read from G)\n", me);
1028         printf("or:    %s <infile_height.tga> <outfile_normandheight.tga> filtertype -3 [<scale>] (read from R)\n", me);
1029         printf("or:    %s <infile_height.tga> <outfile_normandheight.tga> filtertype -4 [<scale>] (read from A)\n", me);
1030         printf("or:    %s <infile_height.tga> <outfile_normandheight.tga> filtertype -5 [<scale>] (read from (R+G+B)/3)\n", me);
1031         printf("or:    %s <infile_height.tga> <outfile_normandheight.tga> filtertype -6 [<scale>] (read from Y)\n", me);
1032         return 1;
1033 }
1034
1035 static const double filter_scharr3[3][3] = {
1036         {  -3/32.0, 0,  3/32.0 },
1037         { -10/32.0, 0, 10/32.0 },
1038         {  -3/32.0, 0,  3/32.0 }
1039 };
1040
1041 static const double filter_prewitt3[3][3] = {
1042         { -1/6.0, 0, 1/6.0 },
1043         { -1/6.0, 0, 1/6.0 },
1044         { -1/6.0, 0, 1/6.0 }
1045 };
1046
1047 /* pathologic for inverting */
1048 static const double filter_sobel3[3][3] = {
1049         { -1/8.0, 0, 1/8.0 },
1050         { -2/8.0, 0, 2/8.0 },
1051         { -1/8.0, 0, 1/8.0 }
1052 };
1053
1054 /* pathologic for inverting */
1055 static const double filter_sobel5[5][5] = {
1056         { -1/128.0,  -2/128.0, 0,  2/128.0, 1/128.0 },
1057         { -4/128.0,  -8/128.0, 0,  8/128.0, 4/128.0 },
1058         { -6/128.0, -12/128.0, 0, 12/128.0, 6/128.0 },
1059         { -4/128.0,  -8/128.0, 0,  8/128.0, 4/128.0 },
1060         { -1/128.0,  -2/128.0, 0,  2/128.0, 1/128.0 }
1061 };
1062
1063 /* pathologic for inverting */
1064 static const double filter_prewitt5[5][5] = {
1065         { -1/40.0, -2/40.0, 0, 2/40.0, 1/40.0 },
1066         { -1/40.0, -2/40.0, 0, 2/40.0, 1/40.0 },
1067         { -1/40.0, -2/40.0, 0, 2/40.0, 1/40.0 },
1068         { -1/40.0, -2/40.0, 0, 2/40.0, 1/40.0 },
1069         { -1/40.0, -2/40.0, 0, 2/40.0, 1/40.0 }
1070 };
1071
1072 static const double filter_trivial[1][3] = {
1073         { -0.5, 0, 0.5 }
1074 };
1075
1076 int main(int argc, char **argv)
1077 {
1078         const char *infile, *outfile, *reffile;
1079         double scale, offset;
1080         int nmaplen, w, h;
1081         int use_median = 0;
1082         int renormalize = 0;
1083         double highpass = 0;
1084         unsigned char *nmapdata, *nmap, *refmap;
1085         const char *filtertype;
1086         const double *filter = NULL;
1087         int filterw = 0, filterh = 0;
1088 #define USE_FILTER(f) \
1089         do \
1090         { \
1091                 filterw = sizeof(*(f)) / sizeof(**(f)); \
1092                 filterh = sizeof((f)) / sizeof(*(f)); \
1093                 filter = &(f)[0][0]; \
1094         } \
1095         while(0)
1096
1097         if(argc > 1)
1098                 infile = argv[1];
1099         else
1100                 return usage(*argv);
1101
1102         if(argc > 2)
1103                 outfile = argv[2];
1104         else
1105                 return usage(*argv);
1106         
1107         if(argc > 3)
1108                 filtertype = argv[3];
1109         else
1110                 return usage(*argv);
1111         
1112         if(argc > 4)
1113                 scale = atof(argv[4]);
1114         else
1115                 scale = 0;
1116
1117         if(argc > 5)
1118                 offset = atof(argv[5]);
1119         else
1120                 offset = (scale<0) ? 1 : 0;
1121
1122         if(argc > 6)
1123                 reffile = argv[6];
1124         else
1125                 reffile = NULL;
1126
1127         /* experimental features */
1128         if(getenv("FFT_NORMALMAP_TO_HEIGHTMAP_RENORMALIZE"))
1129                 renormalize = atoi(getenv("FFT_NORMALMAP_TO_HEIGHTMAP_RENORMALIZE"));
1130         if(getenv("FFT_NORMALMAP_TO_HEIGHTMAP_HIGHPASS"))
1131                 highpass = atof(getenv("FFT_NORMALMAP_TO_HEIGHTMAP_HIGHPASS"));
1132         if(getenv("FFT_NORMALMAP_TO_HEIGHTMAP_USE_MEDIAN"))
1133                 use_median = atoi(getenv("FFT_NORMALMAP_TO_HEIGHTMAP_USE_MEDIAN"));
1134
1135         nmapdata = FS_LoadFile(infile, &nmaplen);
1136         if(!nmapdata)
1137         {
1138                 printf("FS_LoadFile failed\n");
1139                 return 2;
1140         }
1141         nmap = LoadTGA_BGRA(nmapdata, nmaplen);
1142         free(nmapdata);
1143         if(!nmap)
1144         {
1145                 printf("LoadTGA_BGRA failed\n");
1146                 return 2;
1147         }
1148         w = image_width;
1149         h = image_height;
1150
1151         if(reffile)
1152         {
1153                 nmapdata = FS_LoadFile(reffile, &nmaplen);
1154                 if(!nmapdata)
1155                 {
1156                         printf("FS_LoadFile failed\n");
1157                         return 2;
1158                 }
1159                 refmap = LoadTGA_BGRA(nmapdata, nmaplen);
1160                 free(nmapdata);
1161                 if(!refmap)
1162                 {
1163                         printf("LoadTGA_BGRA failed\n");
1164                         return 2;
1165                 }
1166                 if(image_width != w || image_height != h)
1167                 {
1168                         printf("reference map must have same size as input normalmap\n");
1169                         return 2;
1170                 }
1171         }
1172         else
1173                 refmap = NULL;
1174
1175         if(!strcmp(filtertype, "trivial"))
1176                 USE_FILTER(filter_trivial);
1177         if(!strcmp(filtertype, "prewitt3"))
1178                 USE_FILTER(filter_prewitt3);
1179         if(!strcmp(filtertype, "scharr3"))
1180                 USE_FILTER(filter_scharr3);
1181         if(!strcmp(filtertype, "sobel3"))
1182                 USE_FILTER(filter_sobel3);
1183         if(!strcmp(filtertype, "prewitt5"))
1184                 USE_FILTER(filter_prewitt5);
1185         if(!strcmp(filtertype, "sobel5"))
1186                 USE_FILTER(filter_sobel5);
1187
1188         if(scale < 0)
1189         {
1190                 if(filter)
1191                         hmap_to_nmap_local(nmap, image_width, image_height, -scale-1, offset, filter, filterw, filterh);
1192                 else
1193                         hmap_to_nmap(nmap, image_width, image_height, -scale-1, offset);
1194         }
1195         else
1196                 nmap_to_hmap(nmap, refmap, image_width, image_height, scale, offset, filter, filterw, filterh, renormalize, highpass, use_median);
1197
1198         if(!Image_WriteTGABGRA(outfile, image_width, image_height, nmap))
1199         {
1200                 printf("Image_WriteTGABGRA failed\n");
1201                 free(nmap);
1202                 return 2;
1203         }
1204         free(nmap);
1205         return 0;
1206 }