More UI message i18n fixes and improvements...
[blender.git] / source / blender / render / intern / source / volume_precache.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Matt Ebb, Ra˙l Fern·ndez Hern·ndez (Farsthary).
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/render/intern/source/volume_precache.c
29  *  \ingroup render
30  */
31
32
33 #include <math.h>
34 #include <stdlib.h>
35 #include <string.h>
36 #include <float.h>
37
38 #include "MEM_guardedalloc.h"
39
40 #include "BLI_blenlib.h"
41 #include "BLI_math.h"
42 #include "BLI_threads.h"
43 #include "BLI_voxel.h"
44 #include "BLI_utildefines.h"
45
46 #include "BLF_translation.h"
47
48 #include "PIL_time.h"
49
50 #include "RE_shader_ext.h"
51
52 #include "DNA_material_types.h"
53
54 #include "rayintersection.h"
55 #include "rayobject.h"
56 #include "render_types.h"
57 #include "rendercore.h"
58 #include "renderdatabase.h"
59 #include "volumetric.h"
60 #include "volume_precache.h"
61
62 #include "BKE_global.h"
63
64 /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
65 /* defined in pipeline.c, is hardcopy of active dynamic allocated Render */
66 /* only to be used here in this file, it's for speed */
67 extern struct Render R;
68 /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
69
70 /* *** utility code to set up an individual raytree for objectinstance, for checking inside/outside *** */
71
72 /* Recursive test for intersections, from a point inside the mesh, to outside
73  * Number of intersections (depth) determine if a point is inside or outside the mesh */
74 static int intersect_outside_volume(RayObject *tree, Isect *isect, float *offset, int limit, int depth)
75 {
76         if (limit == 0) return depth;
77         
78         if (RE_rayobject_raycast(tree, isect)) {
79                 
80                 isect->start[0] = isect->start[0] + isect->dist*isect->dir[0];
81                 isect->start[1] = isect->start[1] + isect->dist*isect->dir[1];
82                 isect->start[2] = isect->start[2] + isect->dist*isect->dir[2];
83                 
84                 isect->dist = FLT_MAX;
85                 isect->skip = RE_SKIP_VLR_NEIGHBOUR;
86                 isect->orig.face= isect->hit.face;
87                 isect->orig.ob= isect->hit.ob;
88                 
89                 return intersect_outside_volume(tree, isect, offset, limit-1, depth+1);
90         }
91         else {
92                 return depth;
93         }
94 }
95
96 /* Uses ray tracing to check if a point is inside or outside an ObjectInstanceRen */
97 static int point_inside_obi(RayObject *tree, ObjectInstanceRen *UNUSED(obi), const float co[3])
98 {
99         Isect isect= {{0}};
100         float dir[3] = {0.0f, 0.0f, 1.0f};
101         int final_depth=0, depth=0, limit=20;
102         
103         /* set up the isect */
104         copy_v3_v3(isect.start, co);
105         copy_v3_v3(isect.dir, dir);
106         isect.mode= RE_RAY_MIRROR;
107         isect.last_hit= NULL;
108         isect.lay= -1;
109         
110         isect.dist = FLT_MAX;
111         isect.orig.face= NULL;
112         isect.orig.ob = NULL;
113
114         final_depth = intersect_outside_volume(tree, &isect, dir, limit, depth);
115         
116         /* even number of intersections: point is outside
117          * odd number: point is inside */
118         if (final_depth % 2 == 0) return 0;
119         else return 1;
120 }
121
122 /* find the bounding box of an objectinstance in global space */
123 void global_bounds_obi(Render *re, ObjectInstanceRen *obi, float bbmin[3], float bbmax[3])
124 {
125         ObjectRen *obr = obi->obr;
126         VolumePrecache *vp = obi->volume_precache;
127         VertRen *ver= NULL;
128         float co[3];
129         int a;
130         
131         if (vp->bbmin != NULL && vp->bbmax != NULL) {
132                 copy_v3_v3(bbmin, vp->bbmin);
133                 copy_v3_v3(bbmax, vp->bbmax);
134                 return;
135         }
136         
137         vp->bbmin = MEM_callocN(sizeof(float)*3, "volume precache min boundbox corner");
138         vp->bbmax = MEM_callocN(sizeof(float)*3, "volume precache max boundbox corner");
139         
140         INIT_MINMAX(bbmin, bbmax);
141         
142         for (a=0; a<obr->totvert; a++) {
143                 if ((a & 255)==0) ver= obr->vertnodes[a>>8].vert;
144                 else ver++;
145                 
146                 copy_v3_v3(co, ver->co);
147                 
148                 /* transformed object instance in camera space */
149                 if (obi->flag & R_TRANSFORMED)
150                         mul_m4_v3(obi->mat, co);
151                 
152                 /* convert to global space */
153                 mul_m4_v3(re->viewinv, co);
154                 
155                 minmax_v3v3_v3(vp->bbmin, vp->bbmax, co);
156         }
157         
158         copy_v3_v3(bbmin, vp->bbmin);
159         copy_v3_v3(bbmax, vp->bbmax);
160         
161 }
162
163 /* *** light cache filtering *** */
164
165 static float get_avg_surrounds(float *cache, int *res, int xx, int yy, int zz)
166 {
167         int x, y, z, x_, y_, z_;
168         int added=0;
169         float tot=0.0f;
170         
171         for (z=-1; z <= 1; z++) {
172                 z_ = zz+z;
173                 if (z_ >= 0 && z_ <= res[2]-1) {
174                 
175                         for (y=-1; y <= 1; y++) {
176                                 y_ = yy+y;
177                                 if (y_ >= 0 && y_ <= res[1]-1) {
178                                 
179                                         for (x=-1; x <= 1; x++) {
180                                                 x_ = xx+x;
181                                                 if (x_ >= 0 && x_ <= res[0]-1) {
182                                                         const int i = BLI_VOXEL_INDEX(x_, y_, z_, res);
183                                                         
184                                                         if (cache[i] > 0.0f) {
185                                                                 tot += cache[i];
186                                                                 added++;
187                                                         }
188                                                         
189                                                 }
190                                         }
191                                 }
192                         }
193                 }
194         }
195         
196         if (added > 0) tot /= added;
197         
198         return tot;
199 }
200
201 /* function to filter the edges of the light cache, where there was no volume originally.
202  * For each voxel which was originally external to the mesh, it finds the average values of
203  * the surrounding internal voxels and sets the original external voxel to that average amount.
204  * Works almost a bit like a 'dilate' filter */
205 static void lightcache_filter(VolumePrecache *vp)
206 {
207         int x, y, z;
208
209         for (z=0; z < vp->res[2]; z++) {
210                 for (y=0; y < vp->res[1]; y++) {
211                         for (x=0; x < vp->res[0]; x++) {
212                                 /* trigger for outside mesh */
213                                 const int i = BLI_VOXEL_INDEX(x, y, z, vp->res);
214                                 
215                                 if (vp->data_r[i] < -0.f)
216                                         vp->data_r[i] = get_avg_surrounds(vp->data_r, vp->res, x, y, z);
217                                 if (vp->data_g[i] < -0.f)
218                                         vp->data_g[i] = get_avg_surrounds(vp->data_g, vp->res, x, y, z);
219                                 if (vp->data_b[i] < -0.f)
220                                         vp->data_b[i] = get_avg_surrounds(vp->data_b, vp->res, x, y, z);
221                         }
222                 }
223         }
224 }
225
226 #if 0
227 static void lightcache_filter2(VolumePrecache *vp)
228 {
229         int x, y, z;
230         float *new_r, *new_g, *new_b;
231         int field_size = vp->res[0]*vp->res[1]*vp->res[2]*sizeof(float);
232         
233         new_r = MEM_mallocN(field_size, "temp buffer for light cache filter r channel");
234         new_g = MEM_mallocN(field_size, "temp buffer for light cache filter g channel");
235         new_b = MEM_mallocN(field_size, "temp buffer for light cache filter b channel");
236         
237         memcpy(new_r, vp->data_r, field_size);
238         memcpy(new_g, vp->data_g, field_size);
239         memcpy(new_b, vp->data_b, field_size);
240         
241         for (z=0; z < vp->res[2]; z++) {
242                 for (y=0; y < vp->res[1]; y++) {
243                         for (x=0; x < vp->res[0]; x++) {
244                                 /* trigger for outside mesh */
245                                 const int i = BLI_VOXEL_INDEX(x, y, z, vp->res);
246                                 if (vp->data_r[i] < -0.f)
247                                         new_r[i] = get_avg_surrounds(vp->data_r, vp->res, x, y, z);
248                                 if (vp->data_g[i] < -0.f)
249                                         new_g[i] = get_avg_surrounds(vp->data_g, vp->res, x, y, z);
250                                 if (vp->data_b[i] < -0.f)
251                                         new_b[i] = get_avg_surrounds(vp->data_b, vp->res, x, y, z);
252                         }
253                 }
254         }
255         
256         SWAP(float *, vp->data_r, new_r);
257         SWAP(float *, vp->data_g, new_g);
258         SWAP(float *, vp->data_b, new_b);
259         
260         if (new_r) { MEM_freeN(new_r); new_r=NULL; }
261         if (new_g) { MEM_freeN(new_g); new_g=NULL; }
262         if (new_b) { MEM_freeN(new_b); new_b=NULL; }
263 }
264 #endif
265
266 BLI_INLINE int ms_I(int x, int y, int z, int *n) /* has a pad of 1 voxel surrounding the core for boundary simulation */
267 {
268         /* different ordering to light cache */
269         return x*(n[1]+2)*(n[2]+2) + y*(n[2]+2) + z;
270 }
271
272 BLI_INLINE int v_I_pad(int x, int y, int z, int *n) /* has a pad of 1 voxel surrounding the core for boundary simulation */
273 {
274         /* same ordering to light cache, with padding */
275         return z*(n[1]+2)*(n[0]+2) + y*(n[0]+2) + x;
276 }
277
278 BLI_INLINE int lc_to_ms_I(int x, int y, int z, int *n)
279
280         /* converting light cache index to multiple scattering index */
281         return (x-1)*(n[1]*n[2]) + (y-1)*(n[2]) + z-1;
282 }
283
284 /* *** multiple scattering approximation *** */
285
286 /* get the total amount of light energy in the light cache. used to normalize after multiple scattering */
287 static float total_ss_energy(Render *re, int do_test_break, VolumePrecache *vp)
288 {
289         int x, y, z;
290         int *res = vp->res;
291         float energy=0.f;
292         
293         for (z=0; z < res[2]; z++) {
294                 for (y=0; y < res[1]; y++) {
295                         for (x=0; x < res[0]; x++) {
296                                 const int i = BLI_VOXEL_INDEX(x, y, z, res);
297                         
298                                 if (vp->data_r[i] > 0.f) energy += vp->data_r[i];
299                                 if (vp->data_g[i] > 0.f) energy += vp->data_g[i];
300                                 if (vp->data_b[i] > 0.f) energy += vp->data_b[i];
301                         }
302                 }
303
304                 if (do_test_break && re->test_break(re->tbh)) break;
305         }
306         
307         return energy;
308 }
309
310 static float total_ms_energy(Render *re, int do_test_break, float *sr, float *sg, float *sb, int *res)
311 {
312         int x, y, z;
313         float energy=0.f;
314         
315         for (z=1;z<=res[2];z++) {
316                 for (y=1;y<=res[1];y++) {
317                         for (x=1;x<=res[0];x++) {
318                                 const int i = ms_I(x, y, z, res);
319                                 
320                                 if (sr[i] > 0.f) energy += sr[i];
321                                 if (sg[i] > 0.f) energy += sg[i];
322                                 if (sb[i] > 0.f) energy += sb[i];
323                         }
324                 }
325
326                 if (do_test_break && re->test_break(re->tbh)) break;
327         }
328         
329         return energy;
330 }
331
332 static void ms_diffuse(Render *re, int do_test_break, float *x0, float *x, float diff, int *n) //n is the unpadded resolution
333 {
334         int i, j, k, l;
335         const float dt = VOL_MS_TIMESTEP;
336         size_t size = n[0]*n[1]*n[2];
337         const float a = dt*diff*size;
338         
339         for (l=0; l<20; l++) {
340                 for (k=1; k<=n[2]; k++) {
341                         for (j=1; j<=n[1]; j++) {
342                                 for (i=1; i<=n[0]; i++) {
343                                    x[v_I_pad(i, j, k, n)] = (x0[v_I_pad(i, j, k, n)]) + a*(     x0[v_I_pad(i-1, j, k, n)]+ x0[v_I_pad(i+1, j, k, n)]+ x0[v_I_pad(i, j-1, k, n)]+
344                                                                                                                                                 x0[v_I_pad(i, j+1, k, n)]+ x0[v_I_pad(i, j, k-1, n)]+x0[v_I_pad(i, j, k+1, n)]
345                                                                                                                                                 ) / (1+6*a);
346                                 }
347                         }
348
349                         if (do_test_break && re->test_break(re->tbh)) break;
350                 }
351
352                 if (re->test_break(re->tbh)) break;
353         }
354 }
355
356 static void multiple_scattering_diffusion(Render *re, VolumePrecache *vp, Material *ma)
357 {
358         const float diff = ma->vol.ms_diff * 0.001f;    /* compensate for scaling for a nicer UI range */
359         const int simframes = (int)(ma->vol.ms_spread * (float)max_iii(vp->res[0], vp->res[1], vp->res[2]));
360         const int shade_type = ma->vol.shade_type;
361         float fac = ma->vol.ms_intensity;
362         
363         int x, y, z, m;
364         int *n = vp->res;
365         const int size = (n[0]+2)*(n[1]+2)*(n[2]+2);
366         const int do_test_break = (size > 100000);
367         double time, lasttime= PIL_check_seconds_timer();
368         float total;
369         float c=1.0f;
370         float origf;    /* factor for blending in original light cache */
371         float energy_ss, energy_ms;
372
373         float *sr0=(float *)MEM_callocN(size*sizeof(float), "temporary multiple scattering buffer");
374         float *sr=(float *)MEM_callocN(size*sizeof(float), "temporary multiple scattering buffer");
375         float *sg0=(float *)MEM_callocN(size*sizeof(float), "temporary multiple scattering buffer");
376         float *sg=(float *)MEM_callocN(size*sizeof(float), "temporary multiple scattering buffer");
377         float *sb0=(float *)MEM_callocN(size*sizeof(float), "temporary multiple scattering buffer");
378         float *sb=(float *)MEM_callocN(size*sizeof(float), "temporary multiple scattering buffer");
379
380         total = (float)(n[0]*n[1]*n[2]*simframes);
381         
382         energy_ss = total_ss_energy(re, do_test_break, vp);
383         
384         /* Scattering as diffusion pass */
385         for (m=0; m<simframes; m++) {
386                 /* add sources */
387                 for (z=1; z<=n[2]; z++) {
388                         for (y=1; y<=n[1]; y++) {
389                                 for (x=1; x<=n[0]; x++) {
390                                         const int i = lc_to_ms_I(x, y, z, n);   //lc index
391                                         const int j = ms_I(x, y, z, n);                 //ms index
392                                         
393                                         time= PIL_check_seconds_timer();
394                                         c++;
395                                         if (vp->data_r[i] > 0.0f)
396                                                 sr[j] += vp->data_r[i];
397                                         if (vp->data_g[i] > 0.0f)
398                                                 sg[j] += vp->data_g[i];
399                                         if (vp->data_b[i] > 0.0f)
400                                                 sb[j] += vp->data_b[i];
401                                         
402                                         /* Displays progress every second */
403                                         if (time-lasttime>1.0) {
404                                                 char str[64];
405                                                 BLI_snprintf(str, sizeof(str), IFACE_("Simulating multiple scattering: %d%%"),
406                                                              (int)(100.0f * (c / total)));
407                                                 re->i.infostr = str;
408                                                 re->stats_draw(re->sdh, &re->i);
409                                                 re->i.infostr = NULL;
410                                                 lasttime= time;
411                                         }
412                                 }
413                         }
414
415                         if (do_test_break && re->test_break(re->tbh)) break;
416                 }
417
418                 if (re->test_break(re->tbh)) break;
419
420                 SWAP(float *, sr, sr0);
421                 SWAP(float *, sg, sg0);
422                 SWAP(float *, sb, sb0);
423
424                 /* main diffusion simulation */
425                 ms_diffuse(re, do_test_break, sr0, sr, diff, n);
426                 ms_diffuse(re, do_test_break, sg0, sg, diff, n);
427                 ms_diffuse(re, do_test_break, sb0, sb, diff, n);
428                 
429                 if (re->test_break(re->tbh)) break;
430         }
431         
432         /* normalization factor to conserve energy */
433         energy_ms = total_ms_energy(re, do_test_break, sr, sg, sb, n);
434         fac *= (energy_ss / energy_ms);
435         
436         /* blend multiple scattering back in the light cache */
437         if (shade_type == MA_VOL_SHADE_SHADEDPLUSMULTIPLE) {
438                 /* conserve energy - half single, half multiple */
439                 origf = 0.5f;
440                 fac *= 0.5f;
441         }
442         else {
443                 origf = 0.0f;
444         }
445
446         for (z=1;z<=n[2];z++) {
447                 for (y=1;y<=n[1];y++) {
448                         for (x=1;x<=n[0];x++) {
449                                 const int i = lc_to_ms_I(x, y, z, n);   //lc index
450                                 const int j = ms_I(x, y, z, n);                 //ms index
451                                 
452                                 vp->data_r[i] = origf * vp->data_r[i] + fac * sr[j];
453                                 vp->data_g[i] = origf * vp->data_g[i] + fac * sg[j];
454                                 vp->data_b[i] = origf * vp->data_b[i] + fac * sb[j];
455                         }
456                 }
457
458                 if (do_test_break && re->test_break(re->tbh)) break;
459         }
460
461         MEM_freeN(sr0);
462         MEM_freeN(sr);
463         MEM_freeN(sg0);
464         MEM_freeN(sg);
465         MEM_freeN(sb0);
466         MEM_freeN(sb);
467 }
468
469
470
471 #if 0  /* debug stuff */
472 static void *vol_precache_part_test(void *data)
473 {
474         VolPrecachePart *pa = data;
475
476         printf("part number: %d\n", pa->num);
477         printf("done: %d\n", pa->done);
478         printf("x min: %d   x max: %d\n", pa->minx, pa->maxx);
479         printf("y min: %d   y max: %d\n", pa->miny, pa->maxy);
480         printf("z min: %d   z max: %d\n", pa->minz, pa->maxz);
481
482         return NULL;
483 }
484 #endif
485
486 typedef struct VolPrecacheQueue {
487         ThreadQueue *work;
488         ThreadQueue *done;
489 } VolPrecacheQueue;
490
491 /* Iterate over the 3d voxel grid, and fill the voxels with scattering information
492  *
493  * It's stored in memory as 3 big float grids next to each other, one for each RGB channel.
494  * I'm guessing the memory alignment may work out better this way for the purposes
495  * of doing linear interpolation, but I haven't actually tested this theory! :)
496  */
497 static void *vol_precache_part(void *data)
498 {
499         VolPrecacheQueue *queue = (VolPrecacheQueue *)data;
500         VolPrecachePart *pa;
501
502         while ((pa = BLI_thread_queue_pop(queue->work))) {
503                 ObjectInstanceRen *obi = pa->obi;
504                 RayObject *tree = pa->tree;
505                 ShadeInput *shi = pa->shi;
506                 float scatter_col[3] = {0.f, 0.f, 0.f};
507                 float co[3], cco[3], view[3];
508                 int x, y, z, i;
509                 int res[3];
510
511                 if (pa->re->test_break && pa->re->test_break(pa->re->tbh))
512                         break;
513
514                 res[0]= pa->res[0];
515                 res[1]= pa->res[1];
516                 res[2]= pa->res[2];
517
518                 for (z= pa->minz; z < pa->maxz; z++) {
519                         co[2] = pa->bbmin[2] + (pa->voxel[2] * (z + 0.5f));
520                         
521                         for (y= pa->miny; y < pa->maxy; y++) {
522                                 co[1] = pa->bbmin[1] + (pa->voxel[1] * (y + 0.5f));
523                                 
524                                 for (x=pa->minx; x < pa->maxx; x++) {
525                                         co[0] = pa->bbmin[0] + (pa->voxel[0] * (x + 0.5f));
526                                         
527                                         if (pa->re->test_break && pa->re->test_break(pa->re->tbh))
528                                                 break;
529                                         
530                                         /* convert from world->camera space for shading */
531                                         mul_v3_m4v3(cco, pa->viewmat, co);
532
533                                         i = BLI_VOXEL_INDEX(x, y, z, res);
534
535                                         /* don't bother if the point is not inside the volume mesh */
536                                         if (!point_inside_obi(tree, obi, cco)) {
537                                                 obi->volume_precache->data_r[i] = -1.0f;
538                                                 obi->volume_precache->data_g[i] = -1.0f;
539                                                 obi->volume_precache->data_b[i] = -1.0f;
540                                                 continue;
541                                         }
542                                         
543                                         copy_v3_v3(view, cco);
544                                         normalize_v3(view);
545                                         vol_get_scattering(shi, scatter_col, cco, view);
546                                 
547                                         obi->volume_precache->data_r[i] = scatter_col[0];
548                                         obi->volume_precache->data_g[i] = scatter_col[1];
549                                         obi->volume_precache->data_b[i] = scatter_col[2];
550                                         
551                                 }
552                         }
553                 }
554
555                 BLI_thread_queue_push(queue->done, pa);
556         }
557         
558         return NULL;
559 }
560
561
562 static void precache_setup_shadeinput(Render *re, ObjectInstanceRen *obi, Material *ma, ShadeInput *shi)
563 {
564         memset(shi, 0, sizeof(ShadeInput)); 
565         shi->depth= 1;
566         shi->mask= 1;
567         shi->mat = ma;
568         shi->vlr = NULL;
569         memcpy(&shi->r, &shi->mat->r, 23*sizeof(float));        /* note, keep this synced with render_types.h */
570         shi->har= shi->mat->har;
571         shi->obi= obi;
572         shi->obr= obi->obr;
573         shi->lay = re->lay;
574 }
575
576 static void precache_init_parts(Render *re, RayObject *tree, ShadeInput *shi, ObjectInstanceRen *obi, int totthread, int *parts)
577 {
578         VolumePrecache *vp = obi->volume_precache;
579         int i=0, x, y, z;
580         float voxel[3];
581         int sizex, sizey, sizez;
582         float bbmin[3], bbmax[3];
583         int *res;
584         int minx, maxx;
585         int miny, maxy;
586         int minz, maxz;
587         
588         if (!vp) return;
589
590         BLI_freelistN(&re->volume_precache_parts);
591         
592         /* currently we just subdivide the box, number of threads per side */
593         parts[0] = parts[1] = parts[2] = totthread;
594         res = vp->res;
595         
596         /* using boundbox in worldspace */
597         global_bounds_obi(re, obi, bbmin, bbmax);
598         sub_v3_v3v3(voxel, bbmax, bbmin);
599         
600         voxel[0] /= (float)res[0];
601         voxel[1] /= (float)res[1];
602         voxel[2] /= (float)res[2];
603
604         for (x=0; x < parts[0]; x++) {
605                 sizex = ceil(res[0] / (float)parts[0]);
606                 minx = x * sizex;
607                 maxx = minx + sizex;
608                 maxx = (maxx>res[0])?res[0]:maxx;
609                 
610                 for (y=0; y < parts[1]; y++) {
611                         sizey = ceil(res[1] / (float)parts[1]);
612                         miny = y * sizey;
613                         maxy = miny + sizey;
614                         maxy = (maxy>res[1])?res[1]:maxy;
615                         
616                         for (z=0; z < parts[2]; z++) {
617                                 VolPrecachePart *pa= MEM_callocN(sizeof(VolPrecachePart), "new precache part");
618                                 
619                                 sizez = ceil(res[2] / (float)parts[2]);
620                                 minz = z * sizez;
621                                 maxz = minz + sizez;
622                                 maxz = (maxz>res[2])?res[2]:maxz;
623                                 
624                                 pa->re = re;
625                                 pa->num = i;
626                                 pa->tree = tree;
627                                 pa->shi = shi;
628                                 pa->obi = obi;
629                                 copy_m4_m4(pa->viewmat, re->viewmat);
630                                 
631                                 copy_v3_v3(pa->bbmin, bbmin);
632                                 copy_v3_v3(pa->voxel, voxel);
633                                 copy_v3_v3_int(pa->res, res);
634                                 
635                                 pa->minx = minx; pa->maxx = maxx;
636                                 pa->miny = miny; pa->maxy = maxy;
637                                 pa->minz = minz; pa->maxz = maxz;
638                                 
639                                 
640                                 BLI_addtail(&re->volume_precache_parts, pa);
641                                 
642                                 i++;
643                         }
644                 }
645         }
646 }
647
648 /* calculate resolution from bounding box in world space */
649 static int precache_resolution(Render *re, VolumePrecache *vp, ObjectInstanceRen *obi, int res)
650 {
651         float dim[3], div;
652         float bbmin[3], bbmax[3];
653         
654         /* bound box in global space */
655         global_bounds_obi(re, obi, bbmin, bbmax);
656         sub_v3_v3v3(dim, bbmax, bbmin);
657         
658         div = max_fff(dim[0], dim[1], dim[2]);
659         dim[0] /= div;
660         dim[1] /= div;
661         dim[2] /= div;
662         
663         vp->res[0] = ceil(dim[0] * res);
664         vp->res[1] = ceil(dim[1] * res);
665         vp->res[2] = ceil(dim[2] * res);
666         
667         if ((vp->res[0] < 1) || (vp->res[1] < 1) || (vp->res[2] < 1))
668                 return 0;
669         
670         return 1;
671 }
672
673 /* Precache a volume into a 3D voxel grid.
674  * The voxel grid is stored in the ObjectInstanceRen, 
675  * in camera space, aligned with the ObjectRen's bounding box.
676  * Resolution is defined by the user.
677  */
678 static void vol_precache_objectinstance_threads(Render *re, ObjectInstanceRen *obi, Material *ma)
679 {
680         VolumePrecache *vp;
681         VolPrecachePart *pa;
682         RayObject *tree;
683         ShadeInput shi;
684         ListBase threads;
685         VolPrecacheQueue queue;
686         int parts[3] = {1, 1, 1}, totparts;
687         
688         int counter=0;
689         int totthread = re->r.threads, thread;
690         
691         double time, lasttime= PIL_check_seconds_timer();
692         
693         R = *re;
694
695         /* create a raytree with just the faces of the instanced ObjectRen, 
696          * used for checking if the cached point is inside or outside. */
697         tree = makeraytree_object(&R, obi);
698         if (!tree) return;
699
700         vp = MEM_callocN(sizeof(VolumePrecache), "volume light cache");
701         obi->volume_precache = vp;
702         
703         if (!precache_resolution(re, vp, obi, ma->vol.precache_resolution)) {
704                 MEM_freeN(vp);
705                 vp = NULL;
706                 return;
707         }
708
709         vp->data_r = MEM_callocN(sizeof(float)*vp->res[0]*vp->res[1]*vp->res[2], "volume light cache data red channel");
710         vp->data_g = MEM_callocN(sizeof(float)*vp->res[0]*vp->res[1]*vp->res[2], "volume light cache data green channel");
711         vp->data_b = MEM_callocN(sizeof(float)*vp->res[0]*vp->res[1]*vp->res[2], "volume light cache data blue channel");
712         if (vp->data_r==NULL || vp->data_g==NULL || vp->data_b==NULL) {
713                 MEM_freeN(vp);
714                 return;
715         }
716
717         /* Need a shadeinput to calculate scattering */
718         precache_setup_shadeinput(re, obi, ma, &shi);
719         
720         precache_init_parts(re, tree, &shi, obi, totthread, parts);
721         totparts = parts[0] * parts[1] * parts[2];
722
723         /* setup work and done queues */
724         queue.work = BLI_thread_queue_init();
725         queue.done = BLI_thread_queue_init();
726         BLI_thread_queue_nowait(queue.work);
727
728         for (pa= re->volume_precache_parts.first; pa; pa= pa->next)
729                 BLI_thread_queue_push(queue.work, pa);
730         
731         /* launch threads */
732         BLI_init_threads(&threads, vol_precache_part, totthread);
733
734         for (thread= 0; thread<totthread; thread++)
735                 BLI_insert_thread(&threads, &queue);
736         
737         /* loop waiting for work to be done */
738         while (counter < totparts) {
739                 if (re->test_break && re->test_break(re->tbh))
740                         break;
741
742                 if (BLI_thread_queue_pop_timeout(queue.done, 50))
743                         counter++;
744
745                 time= PIL_check_seconds_timer();
746                 if (time-lasttime>1.0) {
747                         char str[64];
748                         BLI_snprintf(str, sizeof(str), IFACE_("Precaching volume: %d%%"),
749                                      (int)(100.0f * ((float)counter / (float)totparts)));
750                         re->i.infostr = str;
751                         re->stats_draw(re->sdh, &re->i);
752                         re->i.infostr = NULL;
753                         lasttime = time;
754                 }
755         }
756         
757         /* free */
758         BLI_end_threads(&threads);
759         BLI_thread_queue_free(queue.work);
760         BLI_thread_queue_free(queue.done);
761         BLI_freelistN(&re->volume_precache_parts);
762         
763         if (tree) {
764                 /* TODO: makeraytree_object creates a tree and saves it on OBI,
765                  * if we free this tree we should also clear other pointers to it */
766                 //RE_rayobject_free(tree);
767                 //tree= NULL;
768         }
769         
770         if (ELEM(ma->vol.shade_type, MA_VOL_SHADE_MULTIPLE, MA_VOL_SHADE_SHADEDPLUSMULTIPLE)) {
771                 /* this should be before the filtering */
772                 multiple_scattering_diffusion(re, obi->volume_precache, ma);
773         }
774                 
775         lightcache_filter(obi->volume_precache);
776 }
777
778 static int using_lightcache(Material *ma)
779 {
780         return (((ma->vol.shadeflag & MA_VOL_PRECACHESHADING) && (ma->vol.shade_type == MA_VOL_SHADE_SHADED)) ||
781                 (ELEM(ma->vol.shade_type, MA_VOL_SHADE_MULTIPLE, MA_VOL_SHADE_SHADEDPLUSMULTIPLE)));
782 }
783
784 /* loop through all objects (and their associated materials)
785  * marked for pre-caching in convertblender.c, and pre-cache them */
786 void volume_precache(Render *re)
787 {
788         ObjectInstanceRen *obi;
789         VolumeOb *vo;
790
791         re->i.infostr = IFACE_("Volume preprocessing");
792         re->stats_draw(re->sdh, &re->i);
793
794         for (vo= re->volumes.first; vo; vo= vo->next) {
795                 if (using_lightcache(vo->ma)) {
796                         for (obi= re->instancetable.first; obi; obi= obi->next) {
797                                 if (obi->obr == vo->obr) {
798                                         vol_precache_objectinstance_threads(re, obi, vo->ma);
799
800                                         if (re->test_break && re->test_break(re->tbh))
801                                                 break;
802                                 }
803                         }
804
805                         if (re->test_break && re->test_break(re->tbh))
806                                 break;
807                 }
808         }
809         
810         re->i.infostr = NULL;
811         re->stats_draw(re->sdh, &re->i);
812 }
813
814 void free_volume_precache(Render *re)
815 {
816         ObjectInstanceRen *obi;
817         
818         for (obi= re->instancetable.first; obi; obi= obi->next) {
819                 if (obi->volume_precache != NULL) {
820                         MEM_freeN(obi->volume_precache->data_r);
821                         MEM_freeN(obi->volume_precache->data_g);
822                         MEM_freeN(obi->volume_precache->data_b);
823                         MEM_freeN(obi->volume_precache->bbmin);
824                         MEM_freeN(obi->volume_precache->bbmax);
825                         MEM_freeN(obi->volume_precache);
826                         obi->volume_precache = NULL;
827                 }
828         }
829         
830         BLI_freelistN(&re->volumes);
831 }
832
833 int point_inside_volume_objectinstance(Render *re, ObjectInstanceRen *obi, const float co[3])
834 {
835         RayObject *tree;
836         int inside=0;
837         
838         tree = makeraytree_object(re, obi);
839         if (!tree) return 0;
840         
841         inside = point_inside_obi(tree, obi, co);
842         
843         //TODO: makeraytree_object creates a tree and saves it on OBI, if we free this tree we should also clear other pointers to it
844         //RE_rayobject_free(tree);
845         //tree= NULL;
846         
847         return inside;
848 }
849