remove RSA's md4.c, replace by DP's
[xonotic/netradiant.git] / tools / quake2 / qdata_heretic2 / animcomp.c
1 /*
2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
4
5 This file is part of GtkRadiant.
6
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
20 */
21
22
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include <math.h>
26 #include <memory.h>
27 #include "animcomp.h"
28
29
30 void    *SafeMalloc(size_t n, char *desc);
31
32
33
34 float *matrix;
35 float *delta;
36 float *best;
37 float *comp;
38 float *tcomp;
39 float *bestcomp;
40 float *frames;
41 float *base;
42
43 int MatWidth;
44 int MatHeight;
45 int CFrameSize;
46 int nFrames;
47
48
49 void AnimCompressInit(int nframes,int nVerts,int CompressedFrameSize)
50 {
51         nFrames=nframes;
52         MatWidth=nVerts*3;
53         MatHeight=CompressedFrameSize;
54         CFrameSize=CompressedFrameSize;
55         matrix=(float *)SafeMalloc(MatWidth*MatHeight*sizeof(float), "AnimCompressInit");
56         best=(float *)SafeMalloc(MatWidth*MatHeight*sizeof(float), "AnimCompressInit");
57         delta=(float *)SafeMalloc(MatWidth*MatHeight*sizeof(float), "AnimCompressInit");
58         comp=(float *)SafeMalloc(CFrameSize*nFrames*sizeof(float), "AnimCompressInit");
59         tcomp=(float *)SafeMalloc(CFrameSize*nFrames*sizeof(float), "AnimCompressInit");
60         bestcomp=(float *)SafeMalloc(CFrameSize*nFrames*sizeof(float), "AnimCompressInit");
61         base=(float *)SafeMalloc(MatWidth*sizeof(float), "AnimCompressInit");
62         frames=(float *)SafeMalloc(MatWidth*nFrames*sizeof(float), "AnimCompressInit");
63 }
64
65 void AnimSetFrame(int frame,int index,float x,float y,float z)
66 {
67         frames[frame*MatWidth+index*3]=x;
68         frames[frame*MatWidth+index*3+1]=y;
69         frames[frame*MatWidth+index*3+2]=z;
70 }
71
72 typedef struct 
73 {
74         int index;
75         float val;
76 } SORTP;
77
78
79 #define F_RANDOM (((float)rand())/(float)RAND_MAX)
80
81 extern void DOsvd(float *a,float *res,float *comp,float *values,int nframes,int framesize,int compressedsize);
82
83 void AnimCompressDoit()
84 {
85         float compression;
86         float *rescale;
87         float *ans;
88         float maxdev;
89         float avedev;
90         float tmp;
91         int j,k,l,numave;
92
93         for (k=0;k<MatWidth;k++)
94                 base[k]=0.0f;
95         for (j=0;j<nFrames;j++)
96                 for (k=0;k<MatWidth;k++)
97                         base[k]+=frames[j*MatWidth+k];
98         tmp=1.0f/(float)nFrames;
99         for (k=0;k<MatWidth;k++)
100                 base[k]*=tmp;
101         for (j=0;j<nFrames;j++)
102                 for (k=0;k<MatWidth;k++)
103                         frames[j*MatWidth+k]-=base[k];
104
105         ans=(float *)SafeMalloc(sizeof(float)*MatWidth, "AnimCompressDoit");
106         rescale=(float *)SafeMalloc(sizeof(float)*CFrameSize, "AnimCompressDoit");
107         DOsvd(frames,best,bestcomp,rescale,nFrames,MatWidth,MatHeight);
108         avedev=0.0;
109         for (l=0;l<CFrameSize;l++)
110                 avedev+=rescale[l];
111         for (l=0;l<CFrameSize;l++)
112                 printf("%3.1f ",100.0f*rescale[l]/avedev);
113         printf("\n");
114         for (j=0;j<nFrames;j++)
115         {
116                 for (l=0;l<CFrameSize;l++)
117                 {
118                         bestcomp[j*CFrameSize+l]=0.0;
119                         for (k=0;k<MatWidth;k++)
120                                 bestcomp[j*CFrameSize+l]+=best[l*MatWidth+k]*frames[j*MatWidth+k];
121                 }
122         }
123         numave=0;
124         avedev=0.0;
125         maxdev=0.0;
126         for (j=0;j<nFrames;j++)
127         {
128                 for (k=0;k<MatWidth;k++)
129                 {
130                         ans[k]=0.0;
131                         for (l=0;l<CFrameSize;l++)
132                                 ans[k]+=best[l*MatWidth+k]*bestcomp[j*CFrameSize+l];
133                         ans[k]-=frames[j*MatWidth+k];
134                         tmp=(float)fabs(ans[k]);
135                         if (tmp>maxdev)
136                                 maxdev=tmp;
137                         avedev+=tmp;
138                         numave++;
139                 }
140         }
141         avedev/=(float)numave;
142 printf("%f Max Deviation (inches)  %f Ave Dev. (inches)\n",maxdev,avedev);
143 printf("%d bytes original size\n",MatWidth*nFrames);
144 printf("%d bytes of overhead\n",MatWidth*MatHeight);
145 printf("%d bytes/frame * %d frames = %d bytes\n",CFrameSize,nFrames,CFrameSize*nFrames);
146         compression=(float)(MatWidth*MatHeight+CFrameSize*nFrames+MatWidth);
147         compression/=(float)(MatWidth*nFrames);
148 printf("Overall compression = %f %%\n",100.0f-100.0f*compression);
149         compression=(float)(CFrameSize);
150         compression/=(float)(MatWidth);
151 printf("frame size compression = %f %%\n",100.0f-100.0f*compression);
152         free(rescale);
153         free(ans);
154 }
155
156 void AnimCompressToBytes(float *trans,float *scale,char *mat,char *ccomp,unsigned char *cbase,float *cscale,float *coffset,float *bmin,float *bmax)
157 {
158         int k,l,nv,j;
159         float maxdev;
160         float avedev;
161         float tmp;
162         int numave;
163         float t,mx;
164         float *ans;
165
166
167         nv=MatWidth/3;
168
169         trans[0]=1E30f;
170         scale[0]=-1E30f;
171         trans[1]=1E30f;
172         scale[1]=-1E30f;
173         trans[2]=1E30f;
174         scale[2]=-1E30f;
175         for (k=0;k<MatWidth;k+=3)
176         {
177                 if (base[k]>scale[0])
178                         scale[0]=base[k];
179                 if (base[k]<trans[0])
180                         trans[0]=base[k];
181
182                 if (base[k+1]>scale[1])
183                         scale[1]=base[k+1];
184                 if (base[k+1]<trans[1])
185                         trans[1]=base[k+1];
186
187                 if (base[k+2]>scale[2])
188                         scale[2]=base[k+2];
189                 if (base[k+2]<trans[2])
190                         trans[2]=base[k+2];
191         }
192
193         scale[0]-=trans[0];
194         scale[1]-=trans[1];
195         scale[2]-=trans[2];
196         scale[0]/=255.0f;
197         scale[1]/=255.0f;
198         scale[2]/=255.0f;
199         for (k=0;k<MatWidth;k+=3)
200         {
201                 t=(base[k]-trans[0])/scale[0];
202                 if (t<0.0f)
203                         t=0.0f;
204                 if (t>255.0f)
205                         t=255.0f;
206                 cbase[k]=(unsigned char)t;
207
208                 t=(base[k+1]-trans[1])/scale[1];
209                 if (t<0.0f)
210                         t=0.0f;
211                 if (t>255.0f)
212                         t=255.0f;
213                 cbase[k+1]=(unsigned char)t;
214
215                 t=(base[k+2]-trans[2])/scale[2];
216                 if (t<0.0f)
217                         t=0.0f;
218                 if (t>255.0f)
219                         t=255.0f;
220                 cbase[k+2]=(unsigned char)t;
221         }
222         for (l=0;l<MatHeight;l++)
223         {
224                 mx=0.0;
225                 for (k=0;k<MatWidth;k++)
226                 {
227                         if (fabs(best[l*MatWidth+k])>mx)
228                                 mx=(float)fabs(best[l*MatWidth+k]);
229                 }
230                 if (mx>1E-8)
231                 {
232                         mx/=127.0f;
233                         coffset[l]=1E30f;
234                         cscale[l]=-1E30f;
235                         for (j=0;j<nFrames;j++)
236                         {
237                                 bestcomp[j*MatHeight+l]*=mx;
238                                 if (bestcomp[j*MatHeight+l]>cscale[l])
239                                         cscale[l]=bestcomp[j*MatHeight+l];
240                                 if (bestcomp[j*MatHeight+l]<coffset[l])
241                                         coffset[l]=bestcomp[j*MatHeight+l];
242                         }
243                         cscale[l]-=coffset[l];
244                         if (cscale[l]>1E-10)
245                         {
246                                 for (j=0;j<nFrames;j++)
247                                 {
248                                         tmp=254.0f*(bestcomp[j*MatHeight+l]-coffset[l])/cscale[l]-127.0f;
249                                         if (tmp>127.0f)
250                                                 tmp=127.0f;
251                                         if (tmp<-127.0f)
252                                                 tmp=-127.0f;
253                                         ccomp[j*MatHeight+l]=(char)floor(tmp+0.5);
254                                 }
255                                 coffset[l]+=cscale[l]*127.0f/254.0f;
256                                 cscale[l]/=254.0f;
257                         }
258                         else
259                         {
260                                 cscale[l]=1.0f;
261                                 coffset[l]=0.0f;
262                                 for (j=0;j<nFrames;j++)
263                                         ccomp[j*MatHeight+l]=0;
264                         }
265                         mx=1.0f/mx;
266                         for (k=0;k<MatWidth;k++)
267                         {
268                                 tmp=best[l*MatWidth+k]*mx;
269                                 if (tmp>127.0f)
270                                         tmp=127.0f;
271                                 if (tmp<-127.0f)
272                                         tmp=-127.0f;
273                                 mat[k*MatHeight+l]=(char)floor(tmp+0.5);
274                         }
275                 }
276                 else
277                 {
278                         cscale[l]=1.0f;
279                         coffset[l]=0.0f;
280                         for (j=0;j<nFrames;j++)
281                                 ccomp[j*MatHeight+l]=0;
282                         for (k=0;k<MatWidth;k++)
283                                 mat[k*MatHeight+l]=0;
284                 }
285         }
286         bmin[0]=1E30f;
287         bmin[1]=1E30f;
288         bmin[2]=1E30f;
289         bmax[0]=-1E30f;
290         bmax[1]=-1E30f;
291         bmax[2]=-1E30f;
292         numave=0;
293         avedev=0.0;
294         maxdev=0.0;
295         ans=(float *)SafeMalloc(sizeof(float)*MatWidth, "AnimCompressToBytes");
296         for (j=0;j<nFrames;j++)
297         {
298                 for (k=0;k<MatWidth;k++)
299                 {
300                         ans[k]=0.0;
301                         for (l=0;l<CFrameSize;l++)
302                                 ans[k]+=(float)(mat[l+k*MatHeight])*((float)(ccomp[j*CFrameSize+l])*cscale[l]+coffset[l]);
303                         ans[k]+=(float)(cbase[k])*scale[k%3]+trans[k%3];
304                         tmp=(float)fabs(ans[k]-frames[j*MatWidth+k]-base[k]);
305                         if (tmp>maxdev)
306                                 maxdev=tmp;
307                         avedev+=tmp;
308                         numave++;
309
310                         if (bmin[k%3]>ans[k])
311                                 bmin[k%3]=ans[k];
312                         if (bmax[k%3]<ans[k])
313                                 bmax[k%3]=ans[k];
314                 }
315         }
316         avedev/=(float)numave;
317 printf("%f Max Deviation (inches)  %f Ave Dev. (inches)\n",maxdev,avedev);
318         free(ans);
319 }
320
321 void AnimCompressGetMatrix(float *mat)
322 {
323         int k,l;
324         for (k=0;k<MatWidth;k++)
325                 for (l=0;l<MatHeight;l++)
326                         mat[k*MatHeight+l]=best[l*MatWidth+k];
327 }
328
329 void AnimCompressGetFrames(float *mat)
330 {
331         memcpy(mat,bestcomp,CFrameSize*nFrames*sizeof(float));
332 }
333
334 void AnimCompressGetBase(int i,float *x,float *y,float *z)
335 {
336         *x=base[i*3];
337         *y=base[i*3+1];
338         *z=base[i*3+2];
339 }
340
341 void AnimCompressEnd()
342 {
343         free(matrix);
344         free(best);
345         free(delta);
346         free(comp);
347         free(tcomp);
348         free(bestcomp);
349         free(base);
350         free(frames);
351 }