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