Spelling Cleanup
[blender.git] / source / blender / render / intern / source / occlusion.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) 2008 Blender Foundation.
20  * All rights reserved.
21  *
22  * The Original Code is: all of this file.
23  *
24  * Contributor(s): Brecht Van Lommel.
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 /** \file blender/render/intern/source/occlusion.c
30  *  \ingroup render
31  */
32
33
34 #include <math.h>
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <string.h>
38
39 #include "MEM_guardedalloc.h"
40
41 #include "DNA_material_types.h"
42
43 #include "BLI_math.h"
44 #include "BLI_blenlib.h"
45 #include "BLI_memarena.h"
46 #include "BLI_threads.h"
47 #include "BLI_utildefines.h"
48
49 #include "BKE_global.h"
50 #include "BKE_scene.h"
51
52
53 #include "RE_shader_ext.h"
54
55 /* local includes */
56 #include "occlusion.h"
57 #include "render_types.h"
58 #include "rendercore.h"
59 #include "renderdatabase.h"
60 #include "pixelshading.h"
61 #include "shading.h"
62 #include "zbuf.h"
63
64 /* ------------------------- Declarations --------------------------- */
65
66 #define INVALID_INDEX ((int)(~0))
67 #define INVPI 0.31830988618379069f
68 #define TOTCHILD 8
69 #define CACHE_STEP 3
70
71 typedef struct OcclusionCacheSample {
72         float co[3], n[3], ao[3], env[3], indirect[3], intensity, dist2;
73         int x, y, filled;
74 } OcclusionCacheSample;
75
76 typedef struct OcclusionCache {
77         OcclusionCacheSample *sample;
78         int x, y, w, h, step;
79 } OcclusionCache;
80
81 typedef struct OccFace {
82         int obi;
83         int facenr;
84 } OccFace;
85
86 typedef struct OccNode {
87         float co[3], area;
88         float sh[9], dco;
89         float occlusion, rad[3];
90         int childflag;
91         union {
92                 //OccFace face;
93                 int face;
94                 struct OccNode *node;
95         } child[TOTCHILD];
96 } OccNode;
97
98 typedef struct OcclusionTree {
99         MemArena *arena;
100
101         float (*co)[3];         /* temporary during build */
102
103         OccFace *face;          /* instance and face indices */
104         float *occlusion;       /* occlusion for faces */
105         float (*rad)[3];        /* radiance for faces */
106         
107         OccNode *root;
108
109         OccNode **stack[BLENDER_MAX_THREADS];
110         int maxdepth;
111
112         int totface;
113
114         float error;
115         float distfac;
116
117         int dothreadedbuild;
118         int totbuildthread;
119         int doindirect;
120
121         OcclusionCache *cache;
122 } OcclusionTree;
123
124 typedef struct OcclusionThread {
125         Render *re;
126         StrandSurface *mesh;
127         float (*faceao)[3];
128         float (*faceenv)[3];
129         float (*faceindirect)[3];
130         int begin, end;
131         int thread;
132 } OcclusionThread;
133
134 typedef struct OcclusionBuildThread {
135         OcclusionTree *tree;
136         int begin, end, depth;
137         OccNode *node;
138 } OcclusionBuildThread;
139
140 /* ------------------------- Shading --------------------------- */
141
142 extern Render R; // meh
143
144 static void occ_shade(ShadeSample *ssamp, ObjectInstanceRen *obi, VlakRen *vlr, float *rad)
145 {
146         ShadeInput *shi= ssamp->shi;
147         ShadeResult *shr= ssamp->shr;
148         float l, u, v, *v1, *v2, *v3;
149         
150         /* init */
151         if(vlr->v4) {
152                 shi->u= u= 0.5f;
153                 shi->v= v= 0.5f;
154         }
155         else {
156                 shi->u= u= 1.0f/3.0f;
157                 shi->v= v= 1.0f/3.0f;
158         }
159
160         /* setup render coordinates */
161         v1= vlr->v1->co;
162         v2= vlr->v2->co;
163         v3= vlr->v3->co;
164         
165         /* renderco */
166         l= 1.0f-u-v;
167         
168         shi->co[0]= l*v3[0]+u*v1[0]+v*v2[0];
169         shi->co[1]= l*v3[1]+u*v1[1]+v*v2[1];
170         shi->co[2]= l*v3[2]+u*v1[2]+v*v2[2];
171
172         shade_input_set_triangle_i(shi, obi, vlr, 0, 1, 2);
173
174         /* set up view vector */
175         copy_v3_v3(shi->view, shi->co);
176         normalize_v3(shi->view);
177         
178         /* cache for shadow */
179         shi->samplenr++;
180         
181         shi->xs= 0; // TODO
182         shi->ys= 0;
183         
184         shade_input_set_normals(shi);
185
186         /* no normal flip */
187         if(shi->flippednor)
188                 shade_input_flip_normals(shi);
189
190         madd_v3_v3fl(shi->co, shi->vn, 0.0001f); /* ugly.. */
191
192         /* not a pretty solution, but fixes common cases */
193         if(shi->obr->ob && shi->obr->ob->transflag & OB_NEG_SCALE) {
194                 negate_v3(shi->vn);
195                 negate_v3(shi->vno);
196                 negate_v3(shi->nmapnorm);
197         }
198
199         /* init material vars */
200         // note, keep this synced with render_types.h
201         memcpy(&shi->r, &shi->mat->r, 23*sizeof(float));
202         shi->har= shi->mat->har;
203         
204         /* render */
205         shade_input_set_shade_texco(shi);
206         shade_material_loop(shi, shr); /* todo: nodes */
207         
208         copy_v3_v3(rad, shr->combined);
209 }
210
211 static void occ_build_shade(Render *re, OcclusionTree *tree)
212 {
213         ShadeSample ssamp;
214         ObjectInstanceRen *obi;
215         VlakRen *vlr;
216         int a;
217
218         R= *re;
219
220         /* setup shade sample with correct passes */
221         memset(&ssamp, 0, sizeof(ShadeSample));
222         ssamp.shi[0].lay= re->lay;
223         ssamp.shi[0].passflag= SCE_PASS_DIFFUSE|SCE_PASS_RGBA;
224         ssamp.shi[0].combinedflag= ~(SCE_PASS_SPEC);
225         ssamp.tot= 1;
226
227         for(a=0; a<tree->totface; a++) {
228                 obi= &R.objectinstance[tree->face[a].obi];
229                 vlr= RE_findOrAddVlak(obi->obr, tree->face[a].facenr);
230
231                 occ_shade(&ssamp, obi, vlr, tree->rad[a]);
232         }
233 }
234
235 /* ------------------------- Spherical Harmonics --------------------------- */
236
237 /* Use 2nd order SH => 9 coefficients, stored in this order:
238    0 = (0,0),
239    1 = (1,-1), 2 = (1,0), 3 = (1,1),
240    4 = (2,-2), 5 = (2,-1), 6 = (2,0), 7 = (2,1), 8 = (2,2) */
241
242 static void sh_copy(float *shresult, float *sh)
243 {
244         memcpy(shresult, sh, sizeof(float)*9);
245 }
246
247 static void sh_mul(float *sh, float f)
248 {
249         int i;
250
251         for(i=0; i<9; i++)
252                 sh[i] *= f;
253 }
254
255 static void sh_add(float *shresult, float *sh1, float *sh2)
256 {
257         int i;
258
259         for(i=0; i<9; i++)
260                 shresult[i]= sh1[i] + sh2[i];
261 }
262
263 static void sh_from_disc(float *n, float area, float *shresult)
264 {
265         /* See formula (3) in:
266            "An Efficient Representation for Irradiance Environment Maps" */
267         float sh[9], x, y, z;
268
269         x= n[0];
270         y= n[1];
271         z= n[2];
272
273         sh[0]= 0.282095f;
274
275         sh[1]= 0.488603f*y;
276         sh[2]= 0.488603f*z;
277         sh[3]= 0.488603f*x;
278         
279         sh[4]= 1.092548f*x*y;
280         sh[5]= 1.092548f*y*z;
281         sh[6]= 0.315392f*(3.0f*z*z - 1.0f);
282         sh[7]= 1.092548f*x*z;
283         sh[8]= 0.546274f*(x*x - y*y);
284
285         sh_mul(sh, area);
286         sh_copy(shresult, sh);
287 }
288
289 static float sh_eval(float *sh, float *v)
290 {
291         /* See formula (13) in:
292            "An Efficient Representation for Irradiance Environment Maps" */
293         static const float c1 = 0.429043f, c2 = 0.511664f, c3 = 0.743125f;
294         static const float c4 = 0.886227f, c5 = 0.247708f;
295         float x, y, z, sum;
296
297         x= v[0];
298         y= v[1];
299         z= v[2];
300
301         sum= c1*sh[8]*(x*x - y*y);
302         sum += c3*sh[6]*z*z;
303         sum += c4*sh[0];
304         sum += -c5*sh[6];
305         sum += 2.0f*c1*(sh[4]*x*y + sh[7]*x*z + sh[5]*y*z);
306         sum += 2.0f*c2*(sh[3]*x + sh[1]*y + sh[2]*z);
307
308         return sum;
309 }
310
311 /* ------------------------------ Building --------------------------------- */
312
313 static void occ_face(const OccFace *face, float co[3], float normal[3], float *area)
314 {
315         ObjectInstanceRen *obi;
316         VlakRen *vlr;
317         float v1[3], v2[3], v3[3], v4[3];
318
319         obi= &R.objectinstance[face->obi];
320         vlr= RE_findOrAddVlak(obi->obr, face->facenr);
321         
322         if(co) {
323                 if(vlr->v4)
324                         mid_v3_v3v3(co, vlr->v1->co, vlr->v3->co);
325                 else
326                         cent_tri_v3(co, vlr->v1->co, vlr->v2->co, vlr->v3->co);
327
328                 if(obi->flag & R_TRANSFORMED)
329                         mul_m4_v3(obi->mat, co);
330         }
331         
332         if(normal) {
333                 normal[0]= -vlr->n[0];
334                 normal[1]= -vlr->n[1];
335                 normal[2]= -vlr->n[2];
336
337                 if(obi->flag & R_TRANSFORMED)
338                         mul_m3_v3(obi->nmat, normal);
339         }
340
341         if(area) {
342                 copy_v3_v3(v1, vlr->v1->co);
343                 copy_v3_v3(v2, vlr->v2->co);
344                 copy_v3_v3(v3, vlr->v3->co);
345                 if(vlr->v4) copy_v3_v3(v4, vlr->v4->co);
346
347                 if(obi->flag & R_TRANSFORMED) {
348                         mul_m4_v3(obi->mat, v1);
349                         mul_m4_v3(obi->mat, v2);
350                         mul_m4_v3(obi->mat, v3);
351                         if(vlr->v4) mul_m4_v3(obi->mat, v4);
352                 }
353
354                 /* todo: correct area for instances */
355                 if(vlr->v4)
356                         *area= area_quad_v3(v1, v2, v3, v4);
357                 else
358                         *area= area_tri_v3(v1, v2, v3);
359         }
360 }
361
362 static void occ_sum_occlusion(OcclusionTree *tree, OccNode *node)
363 {
364         OccNode *child;
365         float occ, area, totarea, rad[3];
366         int a, b, indirect= tree->doindirect;
367
368         occ= 0.0f;
369         totarea= 0.0f;
370         if(indirect) zero_v3(rad);
371
372         for(b=0; b<TOTCHILD; b++) {
373                 if(node->childflag & (1<<b)) {
374                         a= node->child[b].face;
375                         occ_face(&tree->face[a], 0, 0, &area);
376                         occ += area*tree->occlusion[a];
377                         if(indirect) madd_v3_v3fl(rad, tree->rad[a], area);
378                         totarea += area;
379                 }
380                 else if(node->child[b].node) {
381                         child= node->child[b].node;
382                         occ_sum_occlusion(tree, child);
383
384                         occ += child->area*child->occlusion;
385                         if(indirect) madd_v3_v3fl(rad, child->rad, child->area);
386                         totarea += child->area;
387                 }
388         }
389
390         if(totarea != 0.0f) {
391                 occ /= totarea;
392                 if(indirect) mul_v3_fl(rad, 1.0f/totarea);
393         }
394         
395         node->occlusion= occ;
396         if(indirect) copy_v3_v3(node->rad, rad);
397 }
398
399 static int occ_find_bbox_axis(OcclusionTree *tree, int begin, int end, float *min, float *max)
400 {
401         float len, maxlen= -1.0f;
402         int a, axis = 0;
403
404         INIT_MINMAX(min, max);
405
406         for(a=begin; a<end; a++)
407                 DO_MINMAX(tree->co[a], min, max)
408
409         for(a=0; a<3; a++) {
410                 len= max[a] - min[a];
411
412                 if(len > maxlen) {
413                         maxlen= len;
414                         axis= a;
415                 }
416         }
417
418         return axis;
419 }
420
421 static void occ_node_from_face(OccFace *face, OccNode *node)
422 {
423         float n[3];
424
425         occ_face(face, node->co, n, &node->area);
426         node->dco= 0.0f;
427         sh_from_disc(n, node->area, node->sh);
428 }
429
430 static void occ_build_dco(OcclusionTree *tree, OccNode *node, const float co[3], float *dco)
431 {
432         int b;
433         for(b=0; b<TOTCHILD; b++) {
434                 float dist, d[3], nco[3];
435
436                 if(node->childflag & (1<<b)) {
437                         occ_face(tree->face+node->child[b].face, nco, NULL, NULL);
438                 }
439                 else if(node->child[b].node) {
440                         OccNode *child= node->child[b].node;
441                         occ_build_dco(tree, child, co, dco);
442                         copy_v3_v3(nco, child->co);
443                 }
444                 else {
445                         continue;
446                 }
447
448                 sub_v3_v3v3(d, nco, co);
449                 dist= dot_v3v3(d, d);
450                 if(dist > *dco)
451                         *dco= dist;
452         }
453 }
454
455 static void occ_build_split(OcclusionTree *tree, int begin, int end, int *split)
456 {
457         float min[3], max[3], mid;
458         int axis, a, enda;
459
460         /* split in middle of boundbox. this seems faster than median split
461          * on complex scenes, possibly since it avoids two distant faces to
462          * be in the same node better? */
463         axis= occ_find_bbox_axis(tree, begin, end, min, max);
464         mid= 0.5f*(min[axis]+max[axis]);
465
466         a= begin;
467         enda= end;
468         while(a<enda) {
469                 if(tree->co[a][axis] > mid) {
470                         enda--;
471                         SWAP(OccFace, tree->face[a], tree->face[enda]);
472                         SWAP(float, tree->co[a][0], tree->co[enda][0]);
473                         SWAP(float, tree->co[a][1], tree->co[enda][1]);
474                         SWAP(float, tree->co[a][2], tree->co[enda][2]);
475                 }
476                 else
477                         a++;
478         }
479
480         *split= enda;
481 }
482
483 static void occ_build_8_split(OcclusionTree *tree, int begin, int end, int *offset, int *count)
484 {
485         /* split faces into eight groups */
486         int b, splitx, splity[2], splitz[4];
487
488         occ_build_split(tree, begin, end, &splitx);
489
490         /* force split if none found, to deal with degenerate geometry */
491         if(splitx == begin || splitx == end)
492                 splitx= (begin+end)/2;
493
494         occ_build_split(tree, begin, splitx, &splity[0]);
495         occ_build_split(tree, splitx, end, &splity[1]);
496
497         occ_build_split(tree, begin, splity[0], &splitz[0]);
498         occ_build_split(tree, splity[0], splitx, &splitz[1]);
499         occ_build_split(tree, splitx, splity[1], &splitz[2]);
500         occ_build_split(tree, splity[1], end, &splitz[3]);
501
502         offset[0]= begin;
503         offset[1]= splitz[0];
504         offset[2]= splity[0];
505         offset[3]= splitz[1];
506         offset[4]= splitx;
507         offset[5]= splitz[2];
508         offset[6]= splity[1];
509         offset[7]= splitz[3];
510
511         for(b=0; b<7; b++)
512                 count[b]= offset[b+1] - offset[b];
513         count[7]= end - offset[7];
514 }
515
516 static void occ_build_recursive(OcclusionTree *tree, OccNode *node, int begin, int end, int depth);
517
518 static void *exec_occ_build(void *data)
519 {
520         OcclusionBuildThread *othread= (OcclusionBuildThread*)data;
521
522         occ_build_recursive(othread->tree, othread->node, othread->begin, othread->end, othread->depth);
523
524         return 0;
525 }
526
527 static void occ_build_recursive(OcclusionTree *tree, OccNode *node, int begin, int end, int depth)
528 {
529         ListBase threads;
530         OcclusionBuildThread othreads[BLENDER_MAX_THREADS];
531         OccNode *child, tmpnode;
532         /* OccFace *face; */
533         int a, b, totthread=0, offset[TOTCHILD], count[TOTCHILD];
534
535         /* add a new node */
536         node->occlusion= 1.0f;
537
538         /* leaf node with only children */
539         if(end - begin <= TOTCHILD) {
540                 for(a=begin, b=0; a<end; a++, b++) {
541                         /* face= &tree->face[a]; */
542                         node->child[b].face= a;
543                         node->childflag |= (1<<b);
544                 }
545         }
546         else {
547                 /* order faces */
548                 occ_build_8_split(tree, begin, end, offset, count);
549
550                 if(depth == 1 && tree->dothreadedbuild)
551                         BLI_init_threads(&threads, exec_occ_build, tree->totbuildthread);
552
553                 for(b=0; b<TOTCHILD; b++) {
554                         if(count[b] == 0) {
555                                 node->child[b].node= NULL;
556                         }
557                         else if(count[b] == 1) {
558                                 /* face= &tree->face[offset[b]]; */
559                                 node->child[b].face= offset[b];
560                                 node->childflag |= (1<<b);
561                         }
562                         else {
563                                 if(tree->dothreadedbuild)
564                                         BLI_lock_thread(LOCK_CUSTOM1);
565
566                                 child= BLI_memarena_alloc(tree->arena, sizeof(OccNode));
567                                 node->child[b].node= child;
568
569                                 /* keep track of maximum depth for stack */
570                                 if(depth+1 > tree->maxdepth)
571                                         tree->maxdepth= depth+1;
572
573                                 if(tree->dothreadedbuild)
574                                         BLI_unlock_thread(LOCK_CUSTOM1);
575
576                                 if(depth == 1 && tree->dothreadedbuild) {
577                                         othreads[totthread].tree= tree;
578                                         othreads[totthread].node= child;
579                                         othreads[totthread].begin= offset[b];
580                                         othreads[totthread].end= offset[b]+count[b];
581                                         othreads[totthread].depth= depth+1;
582                                         BLI_insert_thread(&threads, &othreads[totthread]);
583                                         totthread++;
584                                 }
585                                 else
586                                         occ_build_recursive(tree, child, offset[b], offset[b]+count[b], depth+1);
587                         }
588                 }
589
590                 if(depth == 1 && tree->dothreadedbuild)
591                         BLI_end_threads(&threads);
592         }
593
594         /* combine area, position and sh */
595         for(b=0; b<TOTCHILD; b++) {
596                 if(node->childflag & (1<<b)) {
597                         child= &tmpnode;
598                         occ_node_from_face(tree->face+node->child[b].face, &tmpnode);
599                 }
600                 else {
601                         child= node->child[b].node;
602                 }
603
604                 if(child) {
605                         node->area += child->area;
606                         sh_add(node->sh, node->sh, child->sh);
607                         madd_v3_v3fl(node->co, child->co, child->area);
608                 }
609         }
610
611         if(node->area != 0.0f)
612                 mul_v3_fl(node->co, 1.0f/node->area);
613
614         /* compute maximum distance from center */
615         node->dco= 0.0f;
616         if(node->area > 0.0f)
617                 occ_build_dco(tree, node, node->co, &node->dco);
618 }
619
620 static void occ_build_sh_normalize(OccNode *node)
621 {
622         /* normalize spherical harmonics to not include area, so
623          * we can clamp the dot product and then mutliply by area */
624         int b;
625
626         if(node->area != 0.0f)
627                 sh_mul(node->sh, 1.0f/node->area);
628
629         for(b=0; b<TOTCHILD; b++) {
630                 if(node->childflag & (1<<b));
631                 else if(node->child[b].node)
632                         occ_build_sh_normalize(node->child[b].node);
633         }
634 }
635
636 static OcclusionTree *occ_tree_build(Render *re)
637 {
638         OcclusionTree *tree;
639         ObjectInstanceRen *obi;
640         ObjectRen *obr;
641         Material *ma;
642         VlakRen *vlr= NULL;
643         int a, b, c, totface;
644
645         /* count */
646         totface= 0;
647         for(obi=re->instancetable.first; obi; obi=obi->next) {
648                 obr= obi->obr;
649                 for(a=0; a<obr->totvlak; a++) {
650                         if((a & 255)==0) vlr= obr->vlaknodes[a>>8].vlak;
651                         else vlr++;
652
653                         ma= vlr->mat;
654
655                         if((ma->shade_flag & MA_APPROX_OCCLUSION) && (ma->material_type == MA_TYPE_SURFACE))
656                                 totface++;
657                 }
658         }
659
660         if(totface == 0)
661                 return NULL;
662         
663         tree= MEM_callocN(sizeof(OcclusionTree), "OcclusionTree");
664         tree->totface= totface;
665
666         /* parameters */
667         tree->error= get_render_aosss_error(&re->r, re->wrld.ao_approx_error);
668         tree->distfac= (re->wrld.aomode & WO_AODIST)? re->wrld.aodistfac: 0.0f;
669         tree->doindirect= (re->wrld.ao_indirect_energy > 0.0f && re->wrld.ao_indirect_bounces > 0);
670
671         /* allocation */
672         tree->arena= BLI_memarena_new(0x8000 * sizeof(OccNode), "occ tree arena");
673         BLI_memarena_use_calloc(tree->arena);
674
675         if(re->wrld.aomode & WO_AOCACHE)
676                 tree->cache= MEM_callocN(sizeof(OcclusionCache)*BLENDER_MAX_THREADS, "OcclusionCache");
677
678         tree->face= MEM_callocN(sizeof(OccFace)*totface, "OcclusionFace");
679         tree->co= MEM_callocN(sizeof(float)*3*totface, "OcclusionCo");
680         tree->occlusion= MEM_callocN(sizeof(float)*totface, "OcclusionOcclusion");
681
682         if(tree->doindirect)
683                 tree->rad= MEM_callocN(sizeof(float)*3*totface, "OcclusionRad");
684
685         /* make array of face pointers */
686         for(b=0, c=0, obi=re->instancetable.first; obi; obi=obi->next, c++) {
687                 obr= obi->obr;
688                 for(a=0; a<obr->totvlak; a++) {
689                         if((a & 255)==0) vlr= obr->vlaknodes[a>>8].vlak;
690                         else vlr++;
691
692                         ma= vlr->mat;
693
694                         if((ma->shade_flag & MA_APPROX_OCCLUSION) && (ma->material_type == MA_TYPE_SURFACE)) {
695                                 tree->face[b].obi= c;
696                                 tree->face[b].facenr= a;
697                                 tree->occlusion[b]= 1.0f;
698                                 occ_face(&tree->face[b], tree->co[b], NULL, NULL); 
699                                 b++;
700                         }
701                 }
702         }
703
704         /* threads */
705         tree->totbuildthread= (re->r.threads > 1 && totface > 10000)? 8: 1;
706         tree->dothreadedbuild= (tree->totbuildthread > 1);
707
708         /* recurse */
709         tree->root= BLI_memarena_alloc(tree->arena, sizeof(OccNode));
710         tree->maxdepth= 1;
711         occ_build_recursive(tree, tree->root, 0, totface, 1);
712
713         if(tree->doindirect) {
714                 occ_build_shade(re, tree);
715                 occ_sum_occlusion(tree, tree->root);
716         }
717         
718         MEM_freeN(tree->co);
719         tree->co= NULL;
720
721         occ_build_sh_normalize(tree->root);
722
723         for(a=0; a<BLENDER_MAX_THREADS; a++)
724                 tree->stack[a]= MEM_callocN(sizeof(OccNode)*TOTCHILD*(tree->maxdepth+1), "OccStack");
725
726         return tree;
727 }
728
729 static void occ_free_tree(OcclusionTree *tree)
730 {
731         int a;
732
733         if(tree) {
734                 if(tree->arena) BLI_memarena_free(tree->arena);
735                 for(a=0; a<BLENDER_MAX_THREADS; a++)
736                         if(tree->stack[a])
737                                 MEM_freeN(tree->stack[a]);
738                 if(tree->occlusion) MEM_freeN(tree->occlusion);
739                 if(tree->cache) MEM_freeN(tree->cache);
740                 if(tree->face) MEM_freeN(tree->face);
741                 if(tree->rad) MEM_freeN(tree->rad);
742                 MEM_freeN(tree);
743         }
744 }
745
746 /* ------------------------- Traversal --------------------------- */
747
748 static float occ_solid_angle(OccNode *node, const float v[3], float d2, float invd2, const float receivenormal[3])
749 {
750         float dotreceive, dotemit;
751         float ev[3];
752
753         ev[0]= -v[0]*invd2;
754         ev[1]= -v[1]*invd2;
755         ev[2]= -v[2]*invd2;
756         dotemit= sh_eval(node->sh, ev);
757         dotreceive= dot_v3v3(receivenormal, v)*invd2;
758
759         CLAMP(dotemit, 0.0f, 1.0f);
760         CLAMP(dotreceive, 0.0f, 1.0f);
761         
762         return ((node->area*dotemit*dotreceive)/(d2 + node->area*INVPI))*INVPI;
763 }
764
765 static void VecAddDir(float result[3], const float v1[3], const float v2[3], const float fac)
766 {
767         result[0]= v1[0] + fac*(v2[0] - v1[0]);
768         result[1]= v1[1] + fac*(v2[1] - v1[1]);
769         result[2]= v1[2] + fac*(v2[2] - v1[2]);
770 }
771
772 static int occ_visible_quad(float *p, const float n[3], const float v0[3], const float *v1, const float *v2, float q0[3], float q1[3], float q2[3], float q3[3])
773 {
774         static const float epsilon = 1e-6f;
775         float c, sd[3];
776         
777         c= dot_v3v3(n, p);
778
779         /* signed distances from the vertices to the plane. */
780         sd[0]= dot_v3v3(n, v0) - c;
781         sd[1]= dot_v3v3(n, v1) - c;
782         sd[2]= dot_v3v3(n, v2) - c;
783
784         if(fabsf(sd[0]) < epsilon) sd[0] = 0.0f;
785         if(fabsf(sd[1]) < epsilon) sd[1] = 0.0f;
786         if(fabsf(sd[2]) < epsilon) sd[2] = 0.0f;
787
788         if(sd[0] > 0) {
789                 if(sd[1] > 0) {
790                         if(sd[2] > 0) {
791                                 // +++
792                                 copy_v3_v3(q0, v0);
793                                 copy_v3_v3(q1, v1);
794                                 copy_v3_v3(q2, v2);
795                                 copy_v3_v3(q3, q2);
796                         }
797                         else if(sd[2] < 0) {
798                                 // ++-
799                                 copy_v3_v3(q0, v0);
800                                 copy_v3_v3(q1, v1);
801                                 VecAddDir(q2, v1, v2, (sd[1]/(sd[1]-sd[2])));
802                                 VecAddDir(q3, v0, v2, (sd[0]/(sd[0]-sd[2])));
803                         }
804                         else {
805                                 // ++0
806                                 copy_v3_v3(q0, v0);
807                                 copy_v3_v3(q1, v1);
808                                 copy_v3_v3(q2, v2);
809                                 copy_v3_v3(q3, q2);
810                         }
811                 }
812                 else if(sd[1] < 0) {
813                         if(sd[2] > 0) {
814                                 // +-+
815                                 copy_v3_v3(q0, v0);
816                                 VecAddDir(q1, v0, v1, (sd[0]/(sd[0]-sd[1])));
817                                 VecAddDir(q2, v1, v2, (sd[1]/(sd[1]-sd[2])));
818                                 copy_v3_v3(q3, v2);
819                         }
820                         else if(sd[2] < 0) {
821                                 // +--
822                                 copy_v3_v3(q0, v0);
823                                 VecAddDir(q1, v0, v1, (sd[0]/(sd[0]-sd[1])));
824                                 VecAddDir(q2, v0, v2, (sd[0]/(sd[0]-sd[2])));
825                                 copy_v3_v3(q3, q2);
826                         }
827                         else {
828                                 // +-0
829                                 copy_v3_v3(q0, v0);
830                                 VecAddDir(q1, v0, v1, (sd[0]/(sd[0]-sd[1])));
831                                 copy_v3_v3(q2, v2);
832                                 copy_v3_v3(q3, q2);
833                         }
834                 }
835                 else {
836                         if(sd[2] > 0) {
837                                 // +0+
838                                 copy_v3_v3(q0, v0);
839                                 copy_v3_v3(q1, v1);
840                                 copy_v3_v3(q2, v2);
841                                 copy_v3_v3(q3, q2);
842                         }
843                         else if(sd[2] < 0) {
844                                 // +0-
845                                 copy_v3_v3(q0, v0);
846                                 copy_v3_v3(q1, v1);
847                                 VecAddDir(q2, v0, v2, (sd[0]/(sd[0]-sd[2])));
848                                 copy_v3_v3(q3, q2);
849                         }
850                         else {
851                                 // +00
852                                 copy_v3_v3(q0, v0);
853                                 copy_v3_v3(q1, v1);
854                                 copy_v3_v3(q2, v2);
855                                 copy_v3_v3(q3, q2);
856                         }
857                 }
858         }
859         else if(sd[0] < 0) {
860                 if(sd[1] > 0) {
861                         if(sd[2] > 0) {
862                                 // -++
863                                 VecAddDir(q0, v0, v1, (sd[0]/(sd[0]-sd[1])));
864                                 copy_v3_v3(q1, v1);
865                                 copy_v3_v3(q2, v2);
866                                 VecAddDir(q3, v0, v2, (sd[0]/(sd[0]-sd[2])));
867                         }
868                         else if(sd[2] < 0) {
869                                 // -+-
870                                 VecAddDir(q0, v0, v1, (sd[0]/(sd[0]-sd[1])));
871                                 copy_v3_v3(q1, v1);
872                                 VecAddDir(q2, v1, v2, (sd[1]/(sd[1]-sd[2])));
873                                 copy_v3_v3(q3, q2);
874                         }
875                         else {
876                                 // -+0
877                                 VecAddDir(q0, v0, v1, (sd[0]/(sd[0]-sd[1])));
878                                 copy_v3_v3(q1, v1);
879                                 copy_v3_v3(q2, v2);
880                                 copy_v3_v3(q3, q2);
881                         }
882                 }
883                 else if(sd[1] < 0) {
884                         if(sd[2] > 0) {
885                                 // --+
886                                 VecAddDir(q0, v0, v2, (sd[0]/(sd[0]-sd[2])));
887                                 VecAddDir(q1, v1, v2, (sd[1]/(sd[1]-sd[2])));
888                                 copy_v3_v3(q2, v2);
889                                 copy_v3_v3(q3, q2);
890                         }
891                         else if(sd[2] < 0) {
892                                 // ---
893                                 return 0;
894                         }
895                         else {
896                                 // --0
897                                 return 0;
898                         }
899                 }
900                 else {
901                         if(sd[2] > 0) {
902                                 // -0+
903                                 VecAddDir(q0, v0, v2, (sd[0]/(sd[0]-sd[2])));
904                                 copy_v3_v3(q1, v1);
905                                 copy_v3_v3(q2, v2);
906                                 copy_v3_v3(q3, q2);
907                         }
908                         else if(sd[2] < 0) {
909                                 // -0-
910                                 return 0;
911                         }
912                         else {
913                                 // -00
914                                 return 0;
915                         }
916                 }
917         }
918         else {
919                 if(sd[1] > 0) {
920                         if(sd[2] > 0) {
921                                 // 0++
922                                 copy_v3_v3(q0, v0);
923                                 copy_v3_v3(q1, v1);
924                                 copy_v3_v3(q2, v2);
925                                 copy_v3_v3(q3, q2);
926                         }
927                         else if(sd[2] < 0) {
928                                 // 0+-
929                                 copy_v3_v3(q0, v0);
930                                 copy_v3_v3(q1, v1);
931                                 VecAddDir(q2, v1, v2, (sd[1]/(sd[1]-sd[2])));
932                                 copy_v3_v3(q3, q2);
933                         }
934                         else {
935                                 // 0+0
936                                 copy_v3_v3(q0, v0);
937                                 copy_v3_v3(q1, v1);
938                                 copy_v3_v3(q2, v2);
939                                 copy_v3_v3(q3, q2);
940                         }
941                 }
942                 else if(sd[1] < 0) {
943                         if(sd[2] > 0) {
944                                 // 0-+
945                                 copy_v3_v3(q0, v0);
946                                 VecAddDir(q1, v1, v2, (sd[1]/(sd[1]-sd[2])));
947                                 copy_v3_v3(q2, v2);
948                                 copy_v3_v3(q3, q2);
949                         }
950                         else if(sd[2] < 0) {
951                                 // 0--
952                                 return 0;
953                         }
954                         else {
955                                 // 0-0
956                                 return 0;
957                         }
958                 }
959                 else {
960                         if(sd[2] > 0) {
961                                 // 00+
962                                 copy_v3_v3(q0, v0);
963                                 copy_v3_v3(q1, v1);
964                                 copy_v3_v3(q2, v2);
965                                 copy_v3_v3(q3, q2);
966                         }
967                         else if(sd[2] < 0) {
968                                 // 00-
969                                 return 0;
970                         }
971                         else {
972                                 // 000
973                                 return 0;
974                         }
975                 }
976         }
977
978         return 1;
979 }
980
981 /* altivec optimization, this works, but is unused */
982
983 #if 0
984 #include <Accelerate/Accelerate.h>
985
986 typedef union {
987         vFloat v;
988         float f[4];
989 } vFloatResult;
990
991 static vFloat vec_splat_float(float val)
992 {
993         return (vFloat){val, val, val, val};
994 }
995
996 static float occ_quad_form_factor(float *p, float *n, float *q0, float *q1, float *q2, float *q3)
997 {
998         vFloat vcos, rlen, vrx, vry, vrz, vsrx, vsry, vsrz, gx, gy, gz, vangle;
999         vUInt8 rotate = (vUInt8){4,5,6,7,8,9,10,11,12,13,14,15,0,1,2,3};
1000         vFloatResult vresult;
1001         float result;
1002
1003         /* compute r* */
1004         vrx = (vFloat){q0[0], q1[0], q2[0], q3[0]} - vec_splat_float(p[0]);
1005         vry = (vFloat){q0[1], q1[1], q2[1], q3[1]} - vec_splat_float(p[1]);
1006         vrz = (vFloat){q0[2], q1[2], q2[2], q3[2]} - vec_splat_float(p[2]);
1007
1008         /* normalize r* */
1009         rlen = vec_rsqrte(vrx*vrx + vry*vry + vrz*vrz + vec_splat_float(1e-16f));
1010         vrx = vrx*rlen;
1011         vry = vry*rlen;
1012         vrz = vrz*rlen;
1013
1014         /* rotate r* for cross and dot */
1015         vsrx= vec_perm(vrx, vrx, rotate);
1016         vsry= vec_perm(vry, vry, rotate);
1017         vsrz= vec_perm(vrz, vrz, rotate);
1018
1019         /* cross product */
1020         gx = vsry*vrz - vsrz*vry;
1021         gy = vsrz*vrx - vsrx*vrz;
1022         gz = vsrx*vry - vsry*vrx;
1023
1024         /* normalize */
1025         rlen = vec_rsqrte(gx*gx + gy*gy + gz*gz + vec_splat_float(1e-16f));
1026         gx = gx*rlen;
1027         gy = gy*rlen;
1028         gz = gz*rlen;
1029
1030         /* angle */
1031         vcos = vrx*vsrx + vry*vsry + vrz*vsrz;
1032         vcos= vec_max(vec_min(vcos, vec_splat_float(1.0f)), vec_splat_float(-1.0f));
1033         vangle= vacosf(vcos);
1034
1035         /* dot */
1036         vresult.v = (vec_splat_float(n[0])*gx +
1037                      vec_splat_float(n[1])*gy +
1038                      vec_splat_float(n[2])*gz)*vangle;
1039
1040         result= (vresult.f[0] + vresult.f[1] + vresult.f[2] + vresult.f[3])*(0.5f/(float)M_PI);
1041         result= MAX2(result, 0.0f);
1042
1043         return result;
1044 }
1045
1046 #endif
1047
1048 /* SSE optimization, acos code doesn't work */
1049
1050 #if 0
1051
1052 #include <xmmintrin.h>
1053
1054 static __m128 sse_approx_acos(__m128 x)
1055 {
1056         /* needs a better approximation than taylor expansion of acos, since that
1057          * gives big erros for near 1.0 values, sqrt(2*x)*acos(1-x) should work
1058          * better, see http://www.tom.womack.net/projects/sse-fast-arctrig.html */
1059
1060         return _mm_set_ps1(1.0f);
1061 }
1062
1063 static float occ_quad_form_factor(float *p, float *n, float *q0, float *q1, float *q2, float *q3)
1064 {
1065         float r0[3], r1[3], r2[3], r3[3], g0[3], g1[3], g2[3], g3[3];
1066         float a1, a2, a3, a4, dot1, dot2, dot3, dot4, result;
1067         float fresult[4] __attribute__((aligned(16)));
1068         __m128 qx, qy, qz, rx, ry, rz, rlen, srx, sry, srz, gx, gy, gz, glen, rcos, angle, aresult;
1069
1070         /* compute r */
1071         qx = _mm_set_ps(q3[0], q2[0], q1[0], q0[0]);
1072         qy = _mm_set_ps(q3[1], q2[1], q1[1], q0[1]);
1073         qz = _mm_set_ps(q3[2], q2[2], q1[2], q0[2]);
1074
1075         rx = qx - _mm_set_ps1(p[0]);
1076         ry = qy - _mm_set_ps1(p[1]);
1077         rz = qz - _mm_set_ps1(p[2]);
1078
1079         /* normalize r */
1080         rlen = _mm_rsqrt_ps(rx*rx + ry*ry + rz*rz + _mm_set_ps1(1e-16f));
1081         rx = rx*rlen;
1082         ry = ry*rlen;
1083         rz = rz*rlen;
1084
1085         /* cross product */
1086         srx = _mm_shuffle_ps(rx, rx, _MM_SHUFFLE(0,3,2,1));
1087         sry = _mm_shuffle_ps(ry, ry, _MM_SHUFFLE(0,3,2,1));
1088         srz = _mm_shuffle_ps(rz, rz, _MM_SHUFFLE(0,3,2,1));
1089
1090         gx = sry*rz - srz*ry;
1091         gy = srz*rx - srx*rz;
1092         gz = srx*ry - sry*rx;
1093
1094         /* normalize g */
1095         glen = _mm_rsqrt_ps(gx*gx + gy*gy + gz*gz + _mm_set_ps1(1e-16f));
1096         gx = gx*glen;
1097         gy = gy*glen;
1098         gz = gz*glen;
1099
1100         /* compute angle */
1101         rcos = rx*srx + ry*sry + rz*srz;
1102         rcos= _mm_max_ps(_mm_min_ps(rcos, _mm_set_ps1(1.0f)), _mm_set_ps1(-1.0f));
1103
1104         angle = sse_approx_cos(rcos);
1105         aresult = (_mm_set_ps1(n[0])*gx + _mm_set_ps1(n[1])*gy + _mm_set_ps1(n[2])*gz)*angle;
1106
1107         /* sum together */
1108         result= (fresult[0] + fresult[1] + fresult[2] + fresult[3])*(0.5f/(float)M_PI);
1109         result= MAX2(result, 0.0f);
1110
1111         return result;
1112 }
1113
1114 #endif
1115
1116 static void normalizef(float *n)
1117 {
1118         float d;
1119         
1120         d= dot_v3v3(n, n);
1121
1122         if(d > 1.0e-35F) {
1123                 d= 1.0f/sqrtf(d);
1124
1125                 n[0] *= d; 
1126                 n[1] *= d; 
1127                 n[2] *= d;
1128         } 
1129 }
1130
1131 static float occ_quad_form_factor(const float p[3], const float n[3], const float q0[3], const float q1[3], const float q2[3], const float q3[3])
1132 {
1133         float r0[3], r1[3], r2[3], r3[3], g0[3], g1[3], g2[3], g3[3];
1134         float a1, a2, a3, a4, dot1, dot2, dot3, dot4, result;
1135
1136         sub_v3_v3v3(r0, q0, p);
1137         sub_v3_v3v3(r1, q1, p);
1138         sub_v3_v3v3(r2, q2, p);
1139         sub_v3_v3v3(r3, q3, p);
1140
1141         normalizef(r0);
1142         normalizef(r1);
1143         normalizef(r2);
1144         normalizef(r3);
1145
1146         cross_v3_v3v3(g0, r1, r0); normalizef(g0);
1147         cross_v3_v3v3(g1, r2, r1); normalizef(g1);
1148         cross_v3_v3v3(g2, r3, r2); normalizef(g2);
1149         cross_v3_v3v3(g3, r0, r3); normalizef(g3);
1150
1151         a1= saacosf(dot_v3v3(r0, r1));
1152         a2= saacosf(dot_v3v3(r1, r2));
1153         a3= saacosf(dot_v3v3(r2, r3));
1154         a4= saacosf(dot_v3v3(r3, r0));
1155
1156         dot1= dot_v3v3(n, g0);
1157         dot2= dot_v3v3(n, g1);
1158         dot3= dot_v3v3(n, g2);
1159         dot4= dot_v3v3(n, g3);
1160
1161         result= (a1*dot1 + a2*dot2 + a3*dot3 + a4*dot4)*0.5f/(float)M_PI;
1162         result= MAX2(result, 0.0f);
1163
1164         return result;
1165 }
1166
1167 static float occ_form_factor(OccFace *face, float *p, float *n)
1168 {
1169         ObjectInstanceRen *obi;
1170         VlakRen *vlr;
1171         float v1[3], v2[3], v3[3], v4[3], q0[3], q1[3], q2[3], q3[3], contrib= 0.0f;
1172
1173         obi= &R.objectinstance[face->obi];
1174         vlr= RE_findOrAddVlak(obi->obr, face->facenr);
1175
1176         copy_v3_v3(v1, vlr->v1->co);
1177         copy_v3_v3(v2, vlr->v2->co);
1178         copy_v3_v3(v3, vlr->v3->co);
1179
1180         if(obi->flag & R_TRANSFORMED) {
1181                 mul_m4_v3(obi->mat, v1);
1182                 mul_m4_v3(obi->mat, v2);
1183                 mul_m4_v3(obi->mat, v3);
1184         }
1185
1186         if(occ_visible_quad(p, n, v1, v2, v3, q0, q1, q2, q3))
1187                 contrib += occ_quad_form_factor(p, n, q0, q1, q2, q3);
1188
1189         if(vlr->v4) {
1190                 copy_v3_v3(v4, vlr->v4->co);
1191                 if(obi->flag & R_TRANSFORMED)
1192                         mul_m4_v3(obi->mat, v4);
1193
1194                 if(occ_visible_quad(p, n, v1, v3, v4, q0, q1, q2, q3))
1195                         contrib += occ_quad_form_factor(p, n, q0, q1, q2, q3);
1196         }
1197
1198         return contrib;
1199 }
1200
1201 static void occ_lookup(OcclusionTree *tree, int thread, OccFace *exclude, float *pp, float *pn, float *occ, float rad[3], float bentn[3])
1202 {
1203         OccNode *node, **stack;
1204         OccFace *face;
1205         float resultocc, resultrad[3], v[3], p[3], n[3], co[3], invd2;
1206         float distfac, fac, error, d2, weight, emitarea;
1207         int b, f, totstack;
1208
1209         /* init variables */
1210         copy_v3_v3(p, pp);
1211         copy_v3_v3(n, pn);
1212         madd_v3_v3fl(p, n, 1e-4f);
1213
1214         if(bentn)
1215                 copy_v3_v3(bentn, n);
1216         
1217         error= tree->error;
1218         distfac= tree->distfac;
1219
1220         resultocc= 0.0f;
1221         zero_v3(resultrad);
1222
1223         /* init stack */
1224         stack= tree->stack[thread];
1225         stack[0]= tree->root;
1226         totstack= 1;
1227
1228         while(totstack) {
1229                 /* pop point off the stack */
1230                 node= stack[--totstack];
1231
1232                 sub_v3_v3v3(v, node->co, p);
1233                 d2= dot_v3v3(v, v) + 1e-16f;
1234                 emitarea= MAX2(node->area, node->dco);
1235
1236                 if(d2*error > emitarea) {
1237                         if(distfac != 0.0f) {
1238                                 fac= 1.0f/(1.0f + distfac*d2);
1239                                 if(fac < 0.01f)
1240                                         continue;
1241                         }
1242                         else
1243                                 fac= 1.0f;
1244
1245                         /* accumulate occlusion from spherical harmonics */
1246                         invd2 = 1.0f/sqrtf(d2);
1247                         weight= occ_solid_angle(node, v, d2, invd2, n);
1248
1249                         if(rad)
1250                                 madd_v3_v3fl(resultrad, node->rad, weight*fac);
1251
1252                         weight *= node->occlusion;
1253
1254                         if(bentn) {
1255                                 bentn[0] -= weight*invd2*v[0];
1256                                 bentn[1] -= weight*invd2*v[1];
1257                                 bentn[2] -= weight*invd2*v[2];
1258                         }
1259
1260                         resultocc += weight*fac;
1261                 }
1262                 else {
1263                         /* traverse into children */
1264                         for(b=0; b<TOTCHILD; b++) {
1265                                 if(node->childflag & (1<<b)) {
1266                                         f= node->child[b].face;
1267                                         face= &tree->face[f];
1268
1269                                         /* accumulate occlusion with face form factor */
1270                                         if(!exclude || !(face->obi == exclude->obi && face->facenr == exclude->facenr)) {
1271                                                 if(bentn || distfac != 0.0f) {
1272                                                         occ_face(face, co, NULL, NULL); 
1273                                                         sub_v3_v3v3(v, co, p);
1274                                                         d2= dot_v3v3(v, v) + 1e-16f;
1275
1276                                                         fac= (distfac == 0.0f)? 1.0f: 1.0f/(1.0f + distfac*d2);
1277                                                         if(fac < 0.01f)
1278                                                                 continue;
1279                                                 }
1280                                                 else
1281                                                         fac= 1.0f;
1282
1283                                                 weight= occ_form_factor(face, p, n);
1284
1285                                                 if(rad)
1286                                                         madd_v3_v3fl(resultrad, tree->rad[f], weight*fac);
1287
1288                                                 weight *= tree->occlusion[f];
1289
1290                                                 if(bentn) {
1291                                                         invd2= 1.0f/sqrtf(d2);
1292                                                         bentn[0] -= weight*invd2*v[0];
1293                                                         bentn[1] -= weight*invd2*v[1];
1294                                                         bentn[2] -= weight*invd2*v[2];
1295                                                 }
1296
1297                                                 resultocc += weight*fac;
1298                                         }
1299                                 }
1300                                 else if(node->child[b].node) {
1301                                         /* push child on the stack */
1302                                         stack[totstack++]= node->child[b].node;
1303                                 }
1304                         }
1305                 }
1306         }
1307
1308         if(occ) *occ= resultocc;
1309         if(rad) copy_v3_v3(rad, resultrad);
1310         /*if(rad && exclude) {
1311                 int a;
1312                 for(a=0; a<tree->totface; a++)
1313                         if((tree->face[a].obi == exclude->obi && tree->face[a].facenr == exclude->facenr))
1314                                 copy_v3_v3(rad, tree->rad[a]);
1315         }*/
1316         if(bentn) normalize_v3(bentn);
1317 }
1318
1319 static void occ_compute_bounces(Render *re, OcclusionTree *tree, int totbounce)
1320 {
1321         float (*rad)[3], (*sum)[3], (*tmp)[3], co[3], n[3], occ;
1322         int bounce, i;
1323
1324         rad= MEM_callocN(sizeof(float)*3*tree->totface, "OcclusionBounceRad");
1325         sum= MEM_dupallocN(tree->rad);
1326
1327         for(bounce=1; bounce<totbounce; bounce++) {
1328                 for(i=0; i<tree->totface; i++) {
1329                         occ_face(&tree->face[i], co, n, NULL);
1330                         madd_v3_v3fl(co, n, 1e-8f);
1331
1332                         occ_lookup(tree, 0, &tree->face[i], co, n, &occ, rad[i], NULL);
1333                         rad[i][0]= MAX2(rad[i][0], 0.0f);
1334                         rad[i][1]= MAX2(rad[i][1], 0.0f);
1335                         rad[i][2]= MAX2(rad[i][2], 0.0f);
1336                         add_v3_v3(sum[i], rad[i]);
1337
1338                         if(re->test_break(re->tbh))
1339                                 break;
1340                 }
1341
1342                 if(re->test_break(re->tbh))
1343                         break;
1344
1345                 tmp= tree->rad;
1346                 tree->rad= rad;
1347                 rad= tmp;
1348
1349                 occ_sum_occlusion(tree, tree->root);
1350         }
1351
1352         MEM_freeN(rad);
1353         MEM_freeN(tree->rad);
1354         tree->rad= sum;
1355
1356         if(!re->test_break(re->tbh))
1357                 occ_sum_occlusion(tree, tree->root);
1358 }
1359
1360 static void occ_compute_passes(Render *re, OcclusionTree *tree, int totpass)
1361 {
1362         float *occ, co[3], n[3];
1363         int pass, i;
1364         
1365         occ= MEM_callocN(sizeof(float)*tree->totface, "OcclusionPassOcc");
1366
1367         for(pass=0; pass<totpass; pass++) {
1368                 for(i=0; i<tree->totface; i++) {
1369                         occ_face(&tree->face[i], co, n, NULL);
1370                         negate_v3(n);
1371                         madd_v3_v3fl(co, n, 1e-8f);
1372
1373                         occ_lookup(tree, 0, &tree->face[i], co, n, &occ[i], NULL, NULL);
1374                         if(re->test_break(re->tbh))
1375                                 break;
1376                 }
1377
1378                 if(re->test_break(re->tbh))
1379                         break;
1380
1381                 for(i=0; i<tree->totface; i++) {
1382                         tree->occlusion[i] -= occ[i]; //MAX2(1.0f-occ[i], 0.0f);
1383                         if(tree->occlusion[i] < 0.0f)
1384                                 tree->occlusion[i]= 0.0f;
1385                 }
1386
1387                 occ_sum_occlusion(tree, tree->root);
1388         }
1389
1390         MEM_freeN(occ);
1391 }
1392
1393 static void sample_occ_tree(Render *re, OcclusionTree *tree, OccFace *exclude, float *co, float *n, int thread, int onlyshadow, float *ao, float *env, float *indirect)
1394 {
1395         float nn[3], bn[3], fac, occ, occlusion, correction, rad[3];
1396         int envcolor;
1397
1398         envcolor= re->wrld.aocolor;
1399         if(onlyshadow)
1400                 envcolor= WO_AOPLAIN;
1401
1402         negate_v3_v3(nn, n);
1403
1404         occ_lookup(tree, thread, exclude, co, nn, &occ, (tree->doindirect)? rad: NULL, (env && envcolor)? bn: NULL);
1405
1406         correction= re->wrld.ao_approx_correction;
1407
1408         occlusion= (1.0f-correction)*(1.0f-occ);
1409         CLAMP(occlusion, 0.0f, 1.0f);
1410         if(correction != 0.0f)
1411                 occlusion += correction*expf(-occ);
1412
1413         if(env) {
1414                 /* sky shading using bent normal */
1415                 if(ELEM(envcolor, WO_AOSKYCOL, WO_AOSKYTEX)) {
1416                         fac= 0.5f * (1.0f + dot_v3v3(bn, re->grvec));
1417                         env[0]= (1.0f-fac)*re->wrld.horr + fac*re->wrld.zenr;
1418                         env[1]= (1.0f-fac)*re->wrld.horg + fac*re->wrld.zeng;
1419                         env[2]= (1.0f-fac)*re->wrld.horb + fac*re->wrld.zenb;
1420
1421                         mul_v3_fl(env, occlusion);
1422                 }
1423                 else {
1424                         env[0]= occlusion;
1425                         env[1]= occlusion;
1426                         env[2]= occlusion;
1427                 }
1428 #if 0
1429                 else {  /* WO_AOSKYTEX */
1430                         float dxyview[3];
1431                         bn[0]= -bn[0];
1432                         bn[1]= -bn[1];
1433                         bn[2]= -bn[2];
1434                         dxyview[0]= 1.0f;
1435                         dxyview[1]= 1.0f;
1436                         dxyview[2]= 0.0f;
1437                         shadeSkyView(ao, co, bn, dxyview);
1438                 }
1439 #endif
1440         }
1441
1442         if(ao) {
1443                 ao[0]= occlusion;
1444                 ao[1]= occlusion;
1445                 ao[2]= occlusion;
1446         }
1447
1448         if(tree->doindirect) copy_v3_v3(indirect, rad);
1449         else zero_v3(indirect);
1450 }
1451
1452 /* ---------------------------- Caching ------------------------------- */
1453
1454 static OcclusionCacheSample *find_occ_sample(OcclusionCache *cache, int x, int y)
1455 {
1456         x -= cache->x;
1457         y -= cache->y;
1458
1459         x /= cache->step;
1460         y /= cache->step;
1461         x *= cache->step;
1462         y *= cache->step;
1463
1464         if(x < 0 || x >= cache->w || y < 0 || y >= cache->h)
1465                 return NULL;
1466         else
1467                 return &cache->sample[y*cache->w + x];
1468 }
1469
1470 static int sample_occ_cache(OcclusionTree *tree, float *co, float *n, int x, int y, int thread, float *ao, float *env, float *indirect)
1471 {
1472         OcclusionCache *cache;
1473         OcclusionCacheSample *samples[4], *sample;
1474         float wn[4], wz[4], wb[4], tx, ty, w, totw, mino, maxo;
1475         float d[3], dist2;
1476         int i, x1, y1, x2, y2;
1477
1478         if(!tree->cache)
1479                 return 0;
1480         
1481         /* first try to find a sample in the same pixel */
1482         cache= &tree->cache[thread];
1483
1484         if(cache->sample && cache->step) {
1485                 sample= &cache->sample[(y-cache->y)*cache->w + (x-cache->x)];
1486                 if(sample->filled) {
1487                         sub_v3_v3v3(d, sample->co, co);
1488                         dist2= dot_v3v3(d, d);
1489                         if(dist2 < 0.5f*sample->dist2 && dot_v3v3(sample->n, n) > 0.98f) {
1490                                 copy_v3_v3(ao, sample->ao);
1491                                 copy_v3_v3(env, sample->env);
1492                                 copy_v3_v3(indirect, sample->indirect);
1493                                 return 1;
1494                         }
1495                 }
1496         }
1497         else
1498                 return 0;
1499
1500         /* try to interpolate between 4 neighboring pixels */
1501         samples[0]= find_occ_sample(cache, x, y);
1502         samples[1]= find_occ_sample(cache, x+cache->step, y);
1503         samples[2]= find_occ_sample(cache, x, y+cache->step);
1504         samples[3]= find_occ_sample(cache, x+cache->step, y+cache->step);
1505
1506         for(i=0; i<4; i++)
1507                 if(!samples[i] || !samples[i]->filled)
1508                         return 0;
1509
1510         /* require intensities not being too different */
1511         mino= MIN4(samples[0]->intensity, samples[1]->intensity, samples[2]->intensity, samples[3]->intensity);
1512         maxo= MAX4(samples[0]->intensity, samples[1]->intensity, samples[2]->intensity, samples[3]->intensity);
1513
1514         if(maxo - mino > 0.05f)
1515                 return 0;
1516
1517         /* compute weighted interpolation between samples */
1518         zero_v3(ao);
1519         zero_v3(env);
1520         zero_v3(indirect);
1521         totw= 0.0f;
1522
1523         x1= samples[0]->x;
1524         y1= samples[0]->y;
1525         x2= samples[3]->x;
1526         y2= samples[3]->y;
1527
1528         tx= (float)(x2 - x)/(float)(x2 - x1);
1529         ty= (float)(y2 - y)/(float)(y2 - y1);
1530
1531         wb[3]= (1.0f-tx)*(1.0f-ty);
1532         wb[2]= (tx)*(1.0f-ty);
1533         wb[1]= (1.0f-tx)*(ty);
1534         wb[0]= tx*ty;
1535
1536         for(i=0; i<4; i++) {
1537                 sub_v3_v3v3(d, samples[i]->co, co);
1538                 //dist2= dot_v3v3(d, d);
1539
1540                 wz[i]= 1.0f; //(samples[i]->dist2/(1e-4f + dist2));
1541                 wn[i]= pow(dot_v3v3(samples[i]->n, n), 32.0f);
1542
1543                 w= wb[i]*wn[i]*wz[i];
1544
1545                 totw += w;
1546                 madd_v3_v3fl(ao, samples[i]->ao, w);
1547                 madd_v3_v3fl(env, samples[i]->env, w);
1548                 madd_v3_v3fl(indirect, samples[i]->indirect, w);
1549         }
1550
1551         if(totw >= 0.9f) {
1552                 totw= 1.0f/totw;
1553                 mul_v3_fl(ao, totw);
1554                 mul_v3_fl(env, totw);
1555                 mul_v3_fl(indirect, totw);
1556                 return 1;
1557         }
1558
1559         return 0;
1560 }
1561
1562 static void sample_occ_surface(ShadeInput *shi)
1563 {
1564         StrandRen *strand= shi->strand;
1565         StrandSurface *mesh= strand->buffer->surface;
1566         int *face, *index = RE_strandren_get_face(shi->obr, strand, 0);
1567         float w[4], *co1, *co2, *co3, *co4;
1568
1569         if(mesh && mesh->face && mesh->co && mesh->ao && index) {
1570                 face= mesh->face[*index];
1571
1572                 co1= mesh->co[face[0]];
1573                 co2= mesh->co[face[1]];
1574                 co3= mesh->co[face[2]];
1575                 co4= (face[3])? mesh->co[face[3]]: NULL;
1576
1577                 interp_weights_face_v3(w, co1, co2, co3, co4, strand->vert->co);
1578
1579                 zero_v3(shi->ao);
1580                 zero_v3(shi->env);
1581                 zero_v3(shi->indirect);
1582
1583                 madd_v3_v3fl(shi->ao, mesh->ao[face[0]], w[0]);
1584                 madd_v3_v3fl(shi->env, mesh->env[face[0]], w[0]);
1585                 madd_v3_v3fl(shi->indirect, mesh->indirect[face[0]], w[0]);
1586                 madd_v3_v3fl(shi->ao, mesh->ao[face[1]], w[1]);
1587                 madd_v3_v3fl(shi->env, mesh->env[face[1]], w[1]);
1588                 madd_v3_v3fl(shi->indirect, mesh->indirect[face[1]], w[1]);
1589                 madd_v3_v3fl(shi->ao, mesh->ao[face[2]], w[2]);
1590                 madd_v3_v3fl(shi->env, mesh->env[face[2]], w[2]);
1591                 madd_v3_v3fl(shi->indirect, mesh->indirect[face[2]], w[2]);
1592                 if(face[3]) {
1593                         madd_v3_v3fl(shi->ao, mesh->ao[face[3]], w[3]);
1594                         madd_v3_v3fl(shi->env, mesh->env[face[3]], w[3]);
1595                         madd_v3_v3fl(shi->indirect, mesh->indirect[face[3]], w[3]);
1596                 }
1597         }
1598         else {
1599                 shi->ao[0]= 1.0f;
1600                 shi->ao[1]= 1.0f;
1601                 shi->ao[2]= 1.0f;
1602                 zero_v3(shi->env);
1603                 zero_v3(shi->indirect);
1604         }
1605 }
1606
1607 /* ------------------------- External Functions --------------------------- */
1608
1609 static void *exec_strandsurface_sample(void *data)
1610 {
1611         OcclusionThread *othread= (OcclusionThread*)data;
1612         Render *re= othread->re;
1613         StrandSurface *mesh= othread->mesh;
1614         float ao[3], env[3], indirect[3], co[3], n[3], *co1, *co2, *co3, *co4;
1615         int a, *face;
1616
1617         for(a=othread->begin; a<othread->end; a++) {
1618                 face= mesh->face[a];
1619                 co1= mesh->co[face[0]];
1620                 co2= mesh->co[face[1]];
1621                 co3= mesh->co[face[2]];
1622
1623                 if(face[3]) {
1624                         co4= mesh->co[face[3]];
1625
1626                         mid_v3_v3v3(co, co1, co3);
1627                         normal_quad_v3( n,co1, co2, co3, co4);
1628                 }
1629                 else {
1630                         cent_tri_v3(co, co1, co2, co3);
1631                         normal_tri_v3( n,co1, co2, co3);
1632                 }
1633                 negate_v3(n);
1634
1635                 sample_occ_tree(re, re->occlusiontree, NULL, co, n, othread->thread, 0, ao, env, indirect);
1636                 copy_v3_v3(othread->faceao[a], ao);
1637                 copy_v3_v3(othread->faceenv[a], env);
1638                 copy_v3_v3(othread->faceindirect[a], indirect);
1639         }
1640
1641         return 0;
1642 }
1643
1644 void make_occ_tree(Render *re)
1645 {
1646         OcclusionThread othreads[BLENDER_MAX_THREADS];
1647         OcclusionTree *tree;
1648         StrandSurface *mesh;
1649         ListBase threads;
1650         float ao[3], env[3], indirect[3], (*faceao)[3], (*faceenv)[3], (*faceindirect)[3];
1651         int a, totface, totthread, *face, *count;
1652
1653         /* ugly, needed for occ_face */
1654         R= *re;
1655
1656         re->i.infostr= "Occlusion preprocessing";
1657         re->stats_draw(re->sdh, &re->i);
1658         
1659         re->occlusiontree= tree= occ_tree_build(re);
1660         
1661         if(tree) {
1662                 if(re->wrld.ao_approx_passes > 0)
1663                         occ_compute_passes(re, tree, re->wrld.ao_approx_passes);
1664                 if(tree->doindirect && (re->wrld.mode & WO_INDIRECT_LIGHT))
1665                         occ_compute_bounces(re, tree, re->wrld.ao_indirect_bounces);
1666
1667                 for(mesh=re->strandsurface.first; mesh; mesh=mesh->next) {
1668                         if(!mesh->face || !mesh->co || !mesh->ao)
1669                                 continue;
1670
1671                         count= MEM_callocN(sizeof(int)*mesh->totvert, "OcclusionCount");
1672                         faceao= MEM_callocN(sizeof(float)*3*mesh->totface, "StrandSurfFaceAO");
1673                         faceenv= MEM_callocN(sizeof(float)*3*mesh->totface, "StrandSurfFaceEnv");
1674                         faceindirect= MEM_callocN(sizeof(float)*3*mesh->totface, "StrandSurfFaceIndirect");
1675
1676                         totthread= (mesh->totface > 10000)? re->r.threads: 1;
1677                         totface= mesh->totface/totthread;
1678                         for(a=0; a<totthread; a++) {
1679                                 othreads[a].re= re;
1680                                 othreads[a].faceao= faceao;
1681                                 othreads[a].faceenv= faceenv;
1682                                 othreads[a].faceindirect= faceindirect;
1683                                 othreads[a].thread= a;
1684                                 othreads[a].mesh= mesh;
1685                                 othreads[a].begin= a*totface;
1686                                 othreads[a].end= (a == totthread-1)? mesh->totface: (a+1)*totface;
1687                         }
1688
1689                         if(totthread == 1) {
1690                                 exec_strandsurface_sample(&othreads[0]);
1691                         }
1692                         else {
1693                                 BLI_init_threads(&threads, exec_strandsurface_sample, totthread);
1694
1695                                 for(a=0; a<totthread; a++)
1696                                         BLI_insert_thread(&threads, &othreads[a]);
1697
1698                                 BLI_end_threads(&threads);
1699                         }
1700
1701                         for(a=0; a<mesh->totface; a++) {
1702                                 face= mesh->face[a];
1703
1704                                 copy_v3_v3(ao, faceao[a]);
1705                                 copy_v3_v3(env, faceenv[a]);
1706                                 copy_v3_v3(indirect, faceindirect[a]);
1707
1708                                 add_v3_v3(mesh->ao[face[0]], ao);
1709                                 add_v3_v3(mesh->env[face[0]], env);
1710                                 add_v3_v3(mesh->indirect[face[0]], indirect);
1711                                 count[face[0]]++;
1712                                 add_v3_v3(mesh->ao[face[1]], ao);
1713                                 add_v3_v3(mesh->env[face[1]], env);
1714                                 add_v3_v3(mesh->indirect[face[1]], indirect);
1715                                 count[face[1]]++;
1716                                 add_v3_v3(mesh->ao[face[2]], ao);
1717                                 add_v3_v3(mesh->env[face[2]], env);
1718                                 add_v3_v3(mesh->indirect[face[2]], indirect);
1719                                 count[face[2]]++;
1720
1721                                 if(face[3]) {
1722                                         add_v3_v3(mesh->ao[face[3]], ao);
1723                                         add_v3_v3(mesh->env[face[3]], env);
1724                                         add_v3_v3(mesh->indirect[face[3]], indirect);
1725                                         count[face[3]]++;
1726                                 }
1727                         }
1728
1729                         for(a=0; a<mesh->totvert; a++) {
1730                                 if(count[a]) {
1731                                         mul_v3_fl(mesh->ao[a], 1.0f/count[a]);
1732                                         mul_v3_fl(mesh->env[a], 1.0f/count[a]);
1733                                         mul_v3_fl(mesh->indirect[a], 1.0f/count[a]);
1734                                 }
1735                         }
1736
1737                         MEM_freeN(count);
1738                         MEM_freeN(faceao);
1739                         MEM_freeN(faceenv);
1740                         MEM_freeN(faceindirect);
1741                 }
1742         }
1743 }
1744
1745 void free_occ(Render *re)
1746 {
1747         if(re->occlusiontree) {
1748                 occ_free_tree(re->occlusiontree);
1749                 re->occlusiontree = NULL;
1750         }
1751 }
1752
1753 void sample_occ(Render *re, ShadeInput *shi)
1754 {
1755         OcclusionTree *tree= re->occlusiontree;
1756         OcclusionCache *cache;
1757         OcclusionCacheSample *sample;
1758         OccFace exclude;
1759         int onlyshadow;
1760
1761         if(tree) {
1762                 if(shi->strand) {
1763                         sample_occ_surface(shi);
1764                 }
1765                 /* try to get result from the cache if possible */
1766                 else if(shi->depth!=0 || !sample_occ_cache(tree, shi->co, shi->vno, shi->xs, shi->ys, shi->thread, shi->ao, shi->env, shi->indirect)) {
1767                         /* no luck, let's sample the occlusion */
1768                         exclude.obi= shi->obi - re->objectinstance;
1769                         exclude.facenr= shi->vlr->index;
1770                         onlyshadow= (shi->mat->mode & MA_ONLYSHADOW);
1771                         sample_occ_tree(re, tree, &exclude, shi->co, shi->vno, shi->thread, onlyshadow, shi->ao, shi->env, shi->indirect);
1772
1773                         /* fill result into sample, each time */
1774                         if(tree->cache) {
1775                                 cache= &tree->cache[shi->thread];
1776
1777                                 if(cache->sample && cache->step) {
1778                                         sample= &cache->sample[(shi->ys-cache->y)*cache->w + (shi->xs-cache->x)];
1779                                         copy_v3_v3(sample->co, shi->co);
1780                                         copy_v3_v3(sample->n, shi->vno);
1781                                         copy_v3_v3(sample->ao, shi->ao);
1782                                         copy_v3_v3(sample->env, shi->env);
1783                                         copy_v3_v3(sample->indirect, shi->indirect);
1784                                         sample->intensity= MAX3(sample->ao[0], sample->ao[1], sample->ao[2]);
1785                                         sample->intensity= MAX2(sample->intensity, MAX3(sample->env[0], sample->env[1], sample->env[2]));
1786                                         sample->intensity= MAX2(sample->intensity, MAX3(sample->indirect[0], sample->indirect[1], sample->indirect[2]));
1787                                         sample->dist2= dot_v3v3(shi->dxco, shi->dxco) + dot_v3v3(shi->dyco, shi->dyco);
1788                                         sample->filled= 1;
1789                                 }
1790                         }
1791                 }
1792         }
1793         else {
1794                 shi->ao[0]= 1.0f;
1795                 shi->ao[1]= 1.0f;
1796                 shi->ao[2]= 1.0f;
1797
1798                 shi->env[0]= 0.0f;
1799                 shi->env[1]= 0.0f;
1800                 shi->env[2]= 0.0f;
1801
1802                 shi->indirect[0]= 0.0f;
1803                 shi->indirect[1]= 0.0f;
1804                 shi->indirect[2]= 0.0f;
1805         }
1806 }
1807
1808 void cache_occ_samples(Render *re, RenderPart *pa, ShadeSample *ssamp)
1809 {
1810         OcclusionTree *tree= re->occlusiontree;
1811         PixStr ps;
1812         OcclusionCache *cache;
1813         OcclusionCacheSample *sample;
1814         OccFace exclude;
1815         ShadeInput *shi;
1816         intptr_t *rd=NULL;
1817         int *ro=NULL, *rp=NULL, *rz=NULL, onlyshadow;
1818         int x, y, step = CACHE_STEP;
1819
1820         if(!tree->cache)
1821                 return;
1822
1823         cache= &tree->cache[pa->thread];
1824         cache->w= pa->rectx;
1825         cache->h= pa->recty;
1826         cache->x= pa->disprect.xmin;
1827         cache->y= pa->disprect.ymin;
1828         cache->step= step;
1829         cache->sample= MEM_callocN(sizeof(OcclusionCacheSample)*cache->w*cache->h, "OcclusionCacheSample");
1830         sample= cache->sample;
1831
1832         if(re->osa) {
1833                 rd= pa->rectdaps;
1834         }
1835         else {
1836                 /* fake pixel struct for non-osa */
1837                 ps.next= NULL;
1838                 ps.mask= 0xFFFF;
1839
1840                 ro= pa->recto;
1841                 rp= pa->rectp;
1842                 rz= pa->rectz;
1843         }
1844
1845         /* compute a sample at every step pixels */
1846         for(y=pa->disprect.ymin; y<pa->disprect.ymax; y++) {
1847                 for(x=pa->disprect.xmin; x<pa->disprect.xmax; x++, sample++, rd++, ro++, rp++, rz++) {
1848                         if(!(((x - pa->disprect.xmin + step) % step) == 0 || x == pa->disprect.xmax-1))
1849                                 continue;
1850                         if(!(((y - pa->disprect.ymin + step) % step) == 0 || y == pa->disprect.ymax-1))
1851                                 continue;
1852
1853                         if(re->osa) {
1854                                 if(!*rd) continue;
1855
1856                                 shade_samples_fill_with_ps(ssamp, (PixStr *)(*rd), x, y);
1857                         }
1858                         else {
1859                                 if(!*rp) continue;
1860
1861                                 ps.obi= *ro;
1862                                 ps.facenr= *rp;
1863                                 ps.z= *rz;
1864                                 shade_samples_fill_with_ps(ssamp, &ps, x, y);
1865                         }
1866
1867                         shi= ssamp->shi;
1868                         if(shi->vlr) {
1869                                 onlyshadow= (shi->mat->mode & MA_ONLYSHADOW);
1870                                 exclude.obi= shi->obi - re->objectinstance;
1871                                 exclude.facenr= shi->vlr->index;
1872                                 sample_occ_tree(re, tree, &exclude, shi->co, shi->vno, shi->thread, onlyshadow, shi->ao, shi->env, shi->indirect);
1873
1874                                 copy_v3_v3(sample->co, shi->co);
1875                                 copy_v3_v3(sample->n, shi->vno);
1876                                 copy_v3_v3(sample->ao, shi->ao);
1877                                 copy_v3_v3(sample->env, shi->env);
1878                                 copy_v3_v3(sample->indirect, shi->indirect);
1879                                 sample->intensity= MAX3(sample->ao[0], sample->ao[1], sample->ao[2]);
1880                                 sample->intensity= MAX2(sample->intensity, MAX3(sample->env[0], sample->env[1], sample->env[2]));
1881                                 sample->intensity= MAX2(sample->intensity, MAX3(sample->indirect[0], sample->indirect[1], sample->indirect[2]));
1882                                 sample->dist2= dot_v3v3(shi->dxco, shi->dxco) + dot_v3v3(shi->dyco, shi->dyco);
1883                                 sample->x= shi->xs;
1884                                 sample->y= shi->ys;
1885                                 sample->filled= 1;
1886                         }
1887
1888                         if(re->test_break(re->tbh))
1889                                 break;
1890                 }
1891         }
1892 }
1893
1894 void free_occ_samples(Render *re, RenderPart *pa)
1895 {
1896         OcclusionTree *tree= re->occlusiontree;
1897         OcclusionCache *cache;
1898
1899         if(tree->cache) {
1900                 cache= &tree->cache[pa->thread];
1901
1902                 if(cache->sample)
1903                         MEM_freeN(cache->sample);
1904
1905                 cache->w= 0;
1906                 cache->h= 0;
1907                 cache->step= 0;
1908         }
1909 }
1910