Approximate AO: Diffuse Bounce Hack
[blender.git] / source / blender / render / intern / source / strand.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
21  * All rights reserved.
22  *
23  * The Original Code is: none of this file.
24  *
25  * Contributors: Brecht Van Lommel.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 #include <math.h>
31 #include <string.h>
32 #include <stdlib.h>
33
34 #include "MEM_guardedalloc.h"
35
36 #include "DNA_key_types.h"
37 #include "DNA_material_types.h"
38 #include "DNA_meshdata_types.h"
39
40 #include "BLI_math.h"
41 #include "BLI_blenlib.h"
42 #include "BLI_ghash.h"
43 #include "BLI_memarena.h"
44
45 #include "BKE_DerivedMesh.h"
46 #include "BKE_key.h"
47 #include "BKE_utildefines.h"
48
49 #include "render_types.h"
50 #include "initrender.h"
51 #include "rendercore.h"
52 #include "renderdatabase.h"
53 #include "renderpipeline.h"
54 #include "pixelblending.h"
55 #include "shading.h"
56 #include "strand.h"
57 #include "zbuf.h"
58
59 /* to be removed */
60 void hoco_to_zco(ZSpan *zspan, float *zco, float *hoco);
61 void zspan_scanconvert_strand(ZSpan *zspan, void *handle, float *v1, float *v2, float *v3, void (*func)(void *, int, int, float, float, float) );
62 void zbufsinglewire(ZSpan *zspan, int obi, int zvlnr, float *ho1, float *ho2);
63
64 /* *************** */
65
66 static float strand_eval_width(Material *ma, float strandco)
67 {
68         float fac;
69
70         strandco= 0.5f*(strandco + 1.0f);
71
72         if(ma->strand_ease!=0.0f) {
73                 if(ma->strand_ease<0.0f)
74                         fac= pow(strandco, 1.0+ma->strand_ease);
75                 else
76                         fac= pow(strandco, 1.0/(1.0f-ma->strand_ease));
77         }
78         else fac= strandco;
79         
80         return ((1.0f-fac)*ma->strand_sta + (fac)*ma->strand_end);
81 }
82
83 void strand_eval_point(StrandSegment *sseg, StrandPoint *spoint)
84 {
85         Material *ma;
86         StrandBuffer *strandbuf;
87         float *simplify;
88         float p[4][3], data[4], cross[3], crosslen, w, dx, dy, t;
89         int type;
90
91         strandbuf= sseg->buffer;
92         ma= sseg->buffer->ma;
93         t= spoint->t;
94         type= (strandbuf->flag & R_STRAND_BSPLINE)? KEY_BSPLINE: KEY_CARDINAL;
95
96         VECCOPY(p[0], sseg->v[0]->co);
97         VECCOPY(p[1], sseg->v[1]->co);
98         VECCOPY(p[2], sseg->v[2]->co);
99         VECCOPY(p[3], sseg->v[3]->co);
100
101         if(sseg->obi->flag & R_TRANSFORMED) {
102                 mul_m4_v3(sseg->obi->mat, p[0]);
103                 mul_m4_v3(sseg->obi->mat, p[1]);
104                 mul_m4_v3(sseg->obi->mat, p[2]);
105                 mul_m4_v3(sseg->obi->mat, p[3]);
106         }
107
108         if(t == 0.0f) {
109                 VECCOPY(spoint->co, p[1]);
110                 spoint->strandco= sseg->v[1]->strandco;
111
112                 spoint->dtstrandco= (sseg->v[2]->strandco - sseg->v[0]->strandco);
113                 if(sseg->v[0] != sseg->v[1])
114                         spoint->dtstrandco *= 0.5f;
115         }
116         else if(t == 1.0f) {
117                 VECCOPY(spoint->co, p[2]);
118                 spoint->strandco= sseg->v[2]->strandco;
119
120                 spoint->dtstrandco= (sseg->v[3]->strandco - sseg->v[1]->strandco);
121                 if(sseg->v[3] != sseg->v[2])
122                         spoint->dtstrandco *= 0.5f;
123         }
124         else {
125                 key_curve_position_weights(t, data, type);
126                 spoint->co[0]= data[0]*p[0][0] + data[1]*p[1][0] + data[2]*p[2][0] + data[3]*p[3][0];
127                 spoint->co[1]= data[0]*p[0][1] + data[1]*p[1][1] + data[2]*p[2][1] + data[3]*p[3][1];
128                 spoint->co[2]= data[0]*p[0][2] + data[1]*p[1][2] + data[2]*p[2][2] + data[3]*p[3][2];
129                 spoint->strandco= (1.0f-t)*sseg->v[1]->strandco + t*sseg->v[2]->strandco;
130         }
131
132         key_curve_tangent_weights(t, data, type);
133         spoint->dtco[0]= data[0]*p[0][0] + data[1]*p[1][0] + data[2]*p[2][0] + data[3]*p[3][0];
134         spoint->dtco[1]= data[0]*p[0][1] + data[1]*p[1][1] + data[2]*p[2][1] + data[3]*p[3][1];
135         spoint->dtco[2]= data[0]*p[0][2] + data[1]*p[1][2] + data[2]*p[2][2] + data[3]*p[3][2];
136
137         VECCOPY(spoint->tan, spoint->dtco);
138         normalize_v3(spoint->tan);
139
140         VECCOPY(spoint->nor, spoint->co);
141         VECMUL(spoint->nor, -1.0f);
142         normalize_v3(spoint->nor);
143
144         spoint->width= strand_eval_width(ma, spoint->strandco);
145         
146         /* simplification */
147         simplify= RE_strandren_get_simplify(strandbuf->obr, sseg->strand, 0);
148         spoint->alpha= (simplify)? simplify[1]: 1.0f;
149
150         /* outer points */
151         cross_v3_v3v3(cross, spoint->co, spoint->tan);
152
153         w= spoint->co[2]*strandbuf->winmat[2][3] + strandbuf->winmat[3][3];
154         dx= strandbuf->winx*cross[0]*strandbuf->winmat[0][0]/w;
155         dy= strandbuf->winy*cross[1]*strandbuf->winmat[1][1]/w;
156         w= sqrt(dx*dx + dy*dy);
157
158         if(w > 0.0f) {
159                 if(strandbuf->flag & R_STRAND_B_UNITS) {
160                         crosslen= len_v3(cross);
161                         w= 2.0f*crosslen*strandbuf->minwidth/w;
162
163                         if(spoint->width < w) {
164                                 spoint->alpha= spoint->width/w;
165                                 spoint->width= w;
166                         }
167
168                         if(simplify)
169                                 /* squared because we only change width, not length */
170                                 spoint->width *= simplify[0]*simplify[0];
171
172                         mul_v3_fl(cross, spoint->width*0.5f/crosslen);
173                 }
174                 else
175                         mul_v3_fl(cross, spoint->width/w);
176         }
177
178         sub_v3_v3v3(spoint->co1, spoint->co, cross);
179         add_v3_v3v3(spoint->co2, spoint->co, cross);
180
181         VECCOPY(spoint->dsco, cross);
182 }
183
184 /* *************** */
185
186 static void interpolate_vec1(float *v1, float *v2, float t, float negt, float *v)
187 {
188         v[0]= negt*v1[0] + t*v2[0];
189 }
190
191 static void interpolate_vec3(float *v1, float *v2, float t, float negt, float *v)
192 {
193         v[0]= negt*v1[0] + t*v2[0];
194         v[1]= negt*v1[1] + t*v2[1];
195         v[2]= negt*v1[2] + t*v2[2];
196 }
197
198 static void interpolate_vec4(float *v1, float *v2, float t, float negt, float *v)
199 {
200         v[0]= negt*v1[0] + t*v2[0];
201         v[1]= negt*v1[1] + t*v2[1];
202         v[2]= negt*v1[2] + t*v2[2];
203         v[3]= negt*v1[3] + t*v2[3];
204 }
205
206 void interpolate_shade_result(ShadeResult *shr1, ShadeResult *shr2, float t, ShadeResult *shr, int addpassflag)
207 {
208         float negt= 1.0f - t;
209
210         interpolate_vec4(shr1->combined, shr2->combined, t, negt, shr->combined);
211
212         if(addpassflag & SCE_PASS_VECTOR) {
213                 interpolate_vec4(shr1->winspeed, shr2->winspeed, t, negt, shr->winspeed);
214         }
215         /* optim... */
216         if(addpassflag & ~(SCE_PASS_VECTOR)) {
217                 if(addpassflag & SCE_PASS_Z)
218                         interpolate_vec1(&shr1->z, &shr2->z, t, negt, &shr->z);
219                 if(addpassflag & SCE_PASS_RGBA)
220                         interpolate_vec4(shr1->col, shr2->col, t, negt, shr->col);
221                 if(addpassflag & SCE_PASS_NORMAL) {
222                         interpolate_vec3(shr1->nor, shr2->nor, t, negt, shr->nor);
223                         normalize_v3(shr->nor);
224                 }
225                 if(addpassflag & SCE_PASS_DIFFUSE)
226                         interpolate_vec3(shr1->diff, shr2->diff, t, negt, shr->diff);
227                 if(addpassflag & SCE_PASS_SPEC)
228                         interpolate_vec3(shr1->spec, shr2->spec, t, negt, shr->spec);
229                 if(addpassflag & SCE_PASS_SHADOW)
230                         interpolate_vec3(shr1->shad, shr2->shad, t, negt, shr->shad);
231                 if(addpassflag & SCE_PASS_AO)
232                         interpolate_vec3(shr1->ao, shr2->ao, t, negt, shr->ao);
233                 if(addpassflag & SCE_PASS_REFLECT)
234                         interpolate_vec3(shr1->refl, shr2->refl, t, negt, shr->refl);
235                 if(addpassflag & SCE_PASS_REFRACT)
236                         interpolate_vec3(shr1->refr, shr2->refr, t, negt, shr->refr);
237                 /* removed if(addpassflag & SCE_PASS_RADIO)
238                         interpolate_vec3(shr1->rad, shr2->rad, t, negt, shr->rad);*/
239                 if(addpassflag & SCE_PASS_MIST)
240                         interpolate_vec1(&shr1->mist, &shr2->mist, t, negt, &shr->mist);
241         }
242 }
243
244 void strand_apply_shaderesult_alpha(ShadeResult *shr, float alpha)
245 {
246         if(alpha < 1.0f) {
247                 shr->combined[0] *= alpha;
248                 shr->combined[1] *= alpha;
249                 shr->combined[2] *= alpha;
250                 shr->combined[3] *= alpha;
251
252                 shr->col[0] *= alpha;
253                 shr->col[1] *= alpha;
254                 shr->col[2] *= alpha;
255                 shr->col[3] *= alpha;
256
257                 shr->alpha *= alpha;
258         }
259 }
260
261 void strand_shade_point(Render *re, ShadeSample *ssamp, StrandSegment *sseg, StrandPoint *spoint)
262 {
263         ShadeInput *shi= ssamp->shi;
264         ShadeResult *shr= ssamp->shr;
265         VlakRen vlr;
266
267         memset(&vlr, 0, sizeof(vlr));
268         vlr.flag= R_SMOOTH;
269         if(sseg->buffer->ma->mode & MA_TANGENT_STR)
270                 vlr.flag |= R_TANGENT;
271
272         shi->vlr= &vlr;
273         shi->strand= sseg->strand;
274         shi->obi= sseg->obi;
275         shi->obr= sseg->obi->obr;
276
277         /* cache for shadow */
278         shi->samplenr= re->shadowsamplenr[shi->thread]++;
279
280         shade_input_set_strand(shi, sseg->strand, spoint);
281         shade_input_set_strand_texco(shi, sseg->strand, sseg->v[1], spoint);
282         
283         /* init material vars */
284         shade_input_init_material(shi);
285         
286         /* shade */
287         shade_samples_do_AO(ssamp);
288         shade_input_do_shade(shi, shr);
289
290         /* apply simplification */
291         strand_apply_shaderesult_alpha(shr, spoint->alpha);
292
293         /* include lamphalos for strand, since halo layer was added already */
294         if(re->flag & R_LAMPHALO)
295                 if(shi->layflag & SCE_LAY_HALO)
296                         renderspothalo(shi, shr->combined, shr->combined[3]);
297         
298         shi->strand= NULL;
299 }
300
301 /* *************** */
302
303 struct StrandShadeCache {
304         GHash *resulthash;
305         GHash *refcounthash;
306         MemArena *memarena;
307 };
308
309 StrandShadeCache *strand_shade_cache_create()
310 {
311         StrandShadeCache *cache;
312
313         cache= MEM_callocN(sizeof(StrandShadeCache), "StrandShadeCache");
314         cache->resulthash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
315         cache->refcounthash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
316         cache->memarena= BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE);
317         
318         return cache;
319 }
320
321 void strand_shade_cache_free(StrandShadeCache *cache)
322 {
323         BLI_ghash_free(cache->refcounthash, NULL, NULL);
324         BLI_ghash_free(cache->resulthash, NULL, (GHashValFreeFP)MEM_freeN);
325         BLI_memarena_free(cache->memarena);
326         MEM_freeN(cache);
327 }
328
329 static void strand_shade_get(Render *re, StrandShadeCache *cache, ShadeSample *ssamp, StrandSegment *sseg, StrandVert *svert)
330 {
331         ShadeResult *hashshr;
332         StrandPoint p;
333         int *refcount;
334
335         hashshr= BLI_ghash_lookup(cache->resulthash, svert);
336         refcount= BLI_ghash_lookup(cache->refcounthash, svert);
337
338         if(!hashshr) {
339                 /* not shaded yet, shade and insert into hash */
340                 p.t= (sseg->v[1] == svert)? 0.0f: 1.0f;
341                 strand_eval_point(sseg, &p);
342                 strand_shade_point(re, ssamp, sseg, &p);
343
344                 hashshr= MEM_callocN(sizeof(ShadeResult), "HashShadeResult");
345                 *hashshr= ssamp->shr[0];
346                 BLI_ghash_insert(cache->resulthash, svert, hashshr);
347         }
348         else
349                 /* already shaded, just copy previous result from hash */
350                 ssamp->shr[0]= *hashshr;
351         
352         /* lower reference count and remove if not needed anymore by any samples */
353         (*refcount)--;
354         if(*refcount == 0) {
355                 BLI_ghash_remove(cache->resulthash, svert, NULL, (GHashValFreeFP)MEM_freeN);
356                 BLI_ghash_remove(cache->refcounthash, svert, NULL, NULL);
357         }
358 }
359
360 void strand_shade_segment(Render *re, StrandShadeCache *cache, StrandSegment *sseg, ShadeSample *ssamp, float t, float s, int addpassflag)
361 {
362         ShadeResult shr1, shr2;
363
364         /* get shading for two endpoints and interpolate */
365         strand_shade_get(re, cache, ssamp, sseg, sseg->v[1]);
366         shr1= ssamp->shr[0];
367         strand_shade_get(re, cache, ssamp, sseg, sseg->v[2]);
368         shr2= ssamp->shr[0];
369
370         interpolate_shade_result(&shr1, &shr2, t, ssamp->shr, addpassflag);
371
372         /* apply alpha along width */
373         if(sseg->buffer->widthfade != 0.0f) {
374                 s = 1.0f - pow(fabs(s), sseg->buffer->widthfade);
375
376                 strand_apply_shaderesult_alpha(ssamp->shr, s);
377         }
378 }
379
380 void strand_shade_unref(StrandShadeCache *cache, StrandVert *svert)
381 {
382         int *refcount;
383
384         /* lower reference count and remove if not needed anymore by any samples */
385         refcount= BLI_ghash_lookup(cache->refcounthash, svert);
386
387         (*refcount)--;
388         if(*refcount == 0) {
389                 BLI_ghash_remove(cache->resulthash, svert, NULL, (GHashValFreeFP)MEM_freeN);
390                 BLI_ghash_remove(cache->refcounthash, svert, NULL, NULL);
391         }
392 }
393
394 static void strand_shade_refcount(StrandShadeCache *cache, StrandVert *svert)
395 {
396         int *refcount= BLI_ghash_lookup(cache->refcounthash, svert);
397
398         if(!refcount) {
399                 refcount= BLI_memarena_alloc(cache->memarena, sizeof(int));
400                 *refcount= 1;
401                 BLI_ghash_insert(cache->refcounthash, svert, refcount);
402         }
403         else
404                 (*refcount)++;
405 }
406
407 /* *************** */
408
409 typedef struct StrandPart {
410         Render *re;
411         ZSpan *zspan;
412
413         APixstrand *apixbuf;
414         int *totapixbuf;
415         int *rectz;
416         int *rectmask;
417         intptr_t *rectdaps;
418         int rectx, recty;
419         int sample;
420         int shadow;
421         float (*jit)[2];
422
423         StrandSegment *segment;
424         float t[3], s[3];
425
426         StrandShadeCache *cache;
427 } StrandPart;
428
429 typedef struct StrandSortSegment {
430         struct StrandSortSegment *next;
431         int obi, strand, segment;
432         float z;
433 } StrandSortSegment;
434
435 static int compare_strand_segment(const void *poin1, const void *poin2)
436 {
437         const StrandSortSegment *seg1= (const StrandSortSegment*)poin1;
438         const StrandSortSegment *seg2= (const StrandSortSegment*)poin2;
439
440         if(seg1->z < seg2->z)
441                 return -1;
442         else if(seg1->z == seg2->z)
443                 return 0;
444         else
445                 return 1;
446 }
447
448 static void do_strand_point_project(float winmat[][4], ZSpan *zspan, float *co, float *hoco, float *zco)
449 {
450         projectvert(co, winmat, hoco);
451         hoco_to_zco(zspan, zco, hoco);
452 }
453
454 static void strand_project_point(float winmat[][4], float winx, float winy, StrandPoint *spoint)
455 {
456         float div;
457
458         projectvert(spoint->co, winmat, spoint->hoco);
459
460         div= 1.0f/spoint->hoco[3];
461         spoint->x= spoint->hoco[0]*div*winx*0.5f;
462         spoint->y= spoint->hoco[1]*div*winy*0.5f;
463 }
464
465 static APixstrand *addpsmainAstrand(ListBase *lb)
466 {
467         APixstrMain *psm;
468
469         psm= MEM_mallocN(sizeof(APixstrMain), "addpsmainA");
470         BLI_addtail(lb, psm);
471         psm->ps= MEM_callocN(4096*sizeof(APixstrand),"pixstr");
472
473         return psm->ps;
474 }
475
476 static APixstrand *addpsAstrand(ZSpan *zspan)
477 {
478         /* make new PS */
479         if(zspan->apstrandmcounter==0) {
480                 zspan->curpstrand= addpsmainAstrand(zspan->apsmbase);
481                 zspan->apstrandmcounter= 4095;
482         }
483         else {
484                 zspan->curpstrand++;
485                 zspan->apstrandmcounter--;
486         }
487         return zspan->curpstrand;
488 }
489
490 #define MAX_ZROW        2000
491
492 static void do_strand_fillac(void *handle, int x, int y, float u, float v, float z)
493 {
494         StrandPart *spart= (StrandPart*)handle;
495         StrandShadeCache *cache= spart->cache;
496         StrandSegment *sseg= spart->segment;
497         APixstrand *apn, *apnew;
498         float t, s;
499         int offset, mask, obi, strnr, seg, zverg, bufferz, maskz=0;
500
501         offset = y*spart->rectx + x;
502         obi= sseg->obi - spart->re->objectinstance;
503         strnr= sseg->strand->index + 1;
504         seg= sseg->v[1] - sseg->strand->vert;
505         mask= (1<<spart->sample);
506
507         /* check against solid z-buffer */
508         zverg= (int)z;
509
510         if(spart->rectdaps) {
511                 /* find the z of the sample */
512                 PixStr *ps;
513                 intptr_t *rd= spart->rectdaps + offset;
514                 
515                 bufferz= 0x7FFFFFFF;
516                 if(spart->rectmask) maskz= 0x7FFFFFFF;
517                 
518                 if(*rd) {       
519                         for(ps= (PixStr *)(*rd); ps; ps= ps->next) {
520                                 if(mask & ps->mask) {
521                                         bufferz= ps->z;
522                                         if(spart->rectmask)
523                                                 maskz= ps->maskz;
524                                         break;
525                                 }
526                         }
527                 }
528         }
529         else {
530                 bufferz= (spart->rectz)? spart->rectz[offset]: 0x7FFFFFFF;
531                 if(spart->rectmask)
532                         maskz= spart->rectmask[offset];
533         }
534
535 #define CHECK_ADD(n) \
536         if(apn->p[n]==strnr && apn->obi[n]==obi && apn->seg[n]==seg) \
537         { if(!(apn->mask[n] & mask)) { apn->mask[n] |= mask; apn->v[n] += t; apn->u[n] += s; } break; }
538 #define CHECK_ASSIGN(n) \
539         if(apn->p[n]==0) \
540         {apn->obi[n]= obi; apn->p[n]= strnr; apn->z[n]= zverg; apn->mask[n]= mask; apn->v[n]= t; apn->u[n]= s; apn->seg[n]= seg; break; }
541
542         /* add to pixel list */
543         if(zverg < bufferz && (spart->totapixbuf[offset] < MAX_ZROW)) {
544                 if(!spart->rectmask || zverg > maskz) {
545                         t = u*spart->t[0] + v*spart->t[1] + (1.0f-u-v)*spart->t[2];
546                         s = fabs(u*spart->s[0] + v*spart->s[1] + (1.0f-u-v)*spart->s[2]);
547
548                         apn= spart->apixbuf + offset;
549                         while(apn) {
550                                 CHECK_ADD(0);
551                                 CHECK_ADD(1);
552                                 CHECK_ADD(2);
553                                 CHECK_ADD(3);
554                                 CHECK_ASSIGN(0);
555                                 CHECK_ASSIGN(1);
556                                 CHECK_ASSIGN(2);
557                                 CHECK_ASSIGN(3);
558
559                                 apnew= addpsAstrand(spart->zspan);
560                                 SWAP(APixstrand, *apnew, *apn);
561                                 apn->next= apnew;
562                                 CHECK_ASSIGN(0);
563                         }
564
565                         if(cache) {
566                                 strand_shade_refcount(cache, sseg->v[1]);
567                                 strand_shade_refcount(cache, sseg->v[2]);
568                         }
569                         spart->totapixbuf[offset]++;
570                 }
571         }
572 }
573
574 static int strand_test_clip(float winmat[][4], ZSpan *zspan, float *bounds, float *co, float *zcomp)
575 {
576         float hoco[4];
577         int clipflag= 0;
578
579         projectvert(co, winmat, hoco);
580
581         /* we compare z without perspective division for segment sorting */
582         *zcomp= hoco[2];
583
584         if(hoco[0] > bounds[1]*hoco[3]) clipflag |= 1;
585         else if(hoco[0]< bounds[0]*hoco[3]) clipflag |= 2;
586         else if(hoco[1] > bounds[3]*hoco[3]) clipflag |= 4;
587         else if(hoco[1]< bounds[2]*hoco[3]) clipflag |= 8;
588
589         clipflag |= testclip(hoco);
590
591         return clipflag;
592 }
593
594 static void do_scanconvert_strand(Render *re, StrandPart *spart, ZSpan *zspan, float t, float dt, float *co1, float *co2, float *co3, float *co4, int sample)
595 {
596         float jco1[3], jco2[3], jco3[3], jco4[3], jx, jy;
597
598         VECCOPY(jco1, co1);
599         VECCOPY(jco2, co2);
600         VECCOPY(jco3, co3);
601         VECCOPY(jco4, co4);
602
603         if(spart->jit) {
604                 jx= -spart->jit[sample][0];
605                 jy= -spart->jit[sample][1];
606
607                 jco1[0] += jx; jco1[1] += jy;
608                 jco2[0] += jx; jco2[1] += jy;
609                 jco3[0] += jx; jco3[1] += jy;
610                 jco4[0] += jx; jco4[1] += jy;
611
612                 /* XXX mblur? */
613         }
614
615         spart->sample= sample;
616
617         spart->t[0]= t-dt;
618         spart->s[0]= -1.0f;
619         spart->t[1]= t-dt;
620         spart->s[1]= 1.0f;
621         spart->t[2]= t;
622         spart->s[2]= 1.0f;
623         zspan_scanconvert_strand(zspan, spart, jco1, jco2, jco3, do_strand_fillac);
624         spart->t[0]= t-dt;
625         spart->s[0]= -1.0f;
626         spart->t[1]= t;
627         spart->s[1]= 1.0f;
628         spart->t[2]= t;
629         spart->s[2]= -1.0f;
630         zspan_scanconvert_strand(zspan, spart, jco1, jco3, jco4, do_strand_fillac);
631 }
632
633 static void strand_render(Render *re, StrandSegment *sseg, float winmat[][4], StrandPart *spart, ZSpan *zspan, int totzspan, StrandPoint *p1, StrandPoint *p2)
634 {
635         if(spart) {
636                 float t= p2->t;
637                 float dt= p2->t - p1->t;
638                 int a;
639
640                 if(re->osa) {
641                         for(a=0; a<re->osa; a++)
642                                 do_scanconvert_strand(re, spart, zspan, t, dt, p1->zco2, p1->zco1, p2->zco1, p2->zco2, a);
643                 }
644                 else
645                         do_scanconvert_strand(re, spart, zspan, t, dt, p1->zco2, p1->zco1, p2->zco1, p2->zco2, 0);
646         }
647         else {
648                 float hoco1[4], hoco2[4];
649                 int a, obi, index;
650   
651                 obi= sseg->obi - re->objectinstance;
652                 index= sseg->strand->index;
653
654                 projectvert(p1->co, winmat, hoco1);
655                 projectvert(p2->co, winmat, hoco2);
656   
657                 for(a=0; a<totzspan; a++) {
658 #if 0
659                         /* render both strand and single pixel wire to counter aliasing */
660                         zbufclip4(re, &zspan[a], obi, index, p1->hoco2, p1->hoco1, p2->hoco1, p2->hoco2, p1->clip2, p1->clip1, p2->clip1, p2->clip2);
661 #endif
662                         /* only render a line for now, which makes the shadow map more
663                            similiar across frames, and so reduces flicker */
664                         zbufsinglewire(&zspan[a], obi, index, hoco1, hoco2);
665                 }
666         }
667 }
668   
669 static int strand_segment_recursive(Render *re, float winmat[][4], StrandPart *spart, ZSpan *zspan, int totzspan, StrandSegment *sseg, StrandPoint *p1, StrandPoint *p2, int depth)
670 {
671         StrandPoint p;
672         StrandBuffer *buffer= sseg->buffer;
673         float dot, d1[2], d2[2], len1, len2;
674
675         if(depth == buffer->maxdepth)
676                 return 0;
677
678         p.t= (p1->t + p2->t)*0.5f;
679         strand_eval_point(sseg, &p);
680         strand_project_point(buffer->winmat, buffer->winx, buffer->winy, &p);
681
682         d1[0]= (p.x - p1->x);
683         d1[1]= (p.y - p1->y);
684         len1= d1[0]*d1[0] + d1[1]*d1[1];
685
686         d2[0]= (p2->x - p.x);
687         d2[1]= (p2->y - p.y);
688         len2= d2[0]*d2[0] + d2[1]*d2[1];
689
690         if(len1 == 0.0f || len2 == 0.0f)
691                 return 0;
692         
693         dot= d1[0]*d2[0] + d1[1]*d2[1];
694         if(dot*dot > sseg->sqadaptcos*len1*len2)
695                 return 0;
696
697         if(spart) {
698                 do_strand_point_project(winmat, zspan, p.co1, p.hoco1, p.zco1);
699                 do_strand_point_project(winmat, zspan, p.co2, p.hoco2, p.zco2);
700         }
701         else {
702 #if 0
703                 projectvert(p.co1, winmat, p.hoco1);
704                 projectvert(p.co2, winmat, p.hoco2);
705                 p.clip1= testclip(p.hoco1);
706                 p.clip2= testclip(p.hoco2);
707 #endif
708         }
709
710         if(!strand_segment_recursive(re, winmat, spart, zspan, totzspan, sseg, p1, &p, depth+1))
711                 strand_render(re, sseg, winmat, spart, zspan, totzspan, p1, &p);
712         if(!strand_segment_recursive(re, winmat, spart, zspan, totzspan, sseg, &p, p2, depth+1))
713                 strand_render(re, sseg, winmat, spart, zspan, totzspan, &p, p2);
714         
715         return 1;
716 }
717
718 void render_strand_segment(Render *re, float winmat[][4], StrandPart *spart, ZSpan *zspan, int totzspan, StrandSegment *sseg)
719 {
720         StrandBuffer *buffer= sseg->buffer;
721         StrandPoint *p1= &sseg->point1;
722         StrandPoint *p2= &sseg->point2;
723
724         p1->t= 0.0f;
725         p2->t= 1.0f;
726
727         strand_eval_point(sseg, p1);
728         strand_project_point(buffer->winmat, buffer->winx, buffer->winy, p1);
729         strand_eval_point(sseg, p2);
730         strand_project_point(buffer->winmat, buffer->winx, buffer->winy, p2);
731
732         if(spart) {
733                 do_strand_point_project(winmat, zspan, p1->co1, p1->hoco1, p1->zco1);
734                 do_strand_point_project(winmat, zspan, p1->co2, p1->hoco2, p1->zco2);
735                 do_strand_point_project(winmat, zspan, p2->co1, p2->hoco1, p2->zco1);
736                 do_strand_point_project(winmat, zspan, p2->co2, p2->hoco2, p2->zco2);
737         }
738         else {
739 #if 0
740                 projectvert(p1->co1, winmat, p1->hoco1);
741                 projectvert(p1->co2, winmat, p1->hoco2);
742                 projectvert(p2->co1, winmat, p2->hoco1);
743                 projectvert(p2->co2, winmat, p2->hoco2);
744                 p1->clip1= testclip(p1->hoco1);
745                 p1->clip2= testclip(p1->hoco2);
746                 p2->clip1= testclip(p2->hoco1);
747                 p2->clip2= testclip(p2->hoco2);
748 #endif
749         }
750
751         if(!strand_segment_recursive(re, winmat, spart, zspan, totzspan, sseg, p1, p2, 0))
752                 strand_render(re, sseg, winmat, spart, zspan, totzspan, p1, p2);
753 }
754
755 /* render call to fill in strands */
756 int zbuffer_strands_abuf(Render *re, RenderPart *pa, APixstrand *apixbuf, ListBase *apsmbase, unsigned int lay, int negzmask, float winmat[][4], int winx, int winy, int sample, float (*jit)[2], float clipcrop, int shadow, StrandShadeCache *cache)
757 {
758         ObjectRen *obr;
759         ObjectInstanceRen *obi;
760         ZSpan zspan;
761         StrandRen *strand=0;
762         StrandVert *svert;
763         StrandBound *sbound;
764         StrandPart spart;
765         StrandSegment sseg;
766         StrandSortSegment *sortsegments = NULL, *sortseg, *firstseg;
767         MemArena *memarena;
768         float z[4], bounds[4], obwinmat[4][4];
769         int a, b, c, i, totsegment, clip[4];
770
771         if(re->test_break(re->tbh))
772                 return 0;
773         if(re->totstrand == 0)
774                 return 0;
775
776         /* setup StrandPart */
777         memset(&spart, 0, sizeof(spart));
778
779         spart.re= re;
780         spart.rectx= pa->rectx;
781         spart.recty= pa->recty;
782         spart.apixbuf= apixbuf;
783         spart.zspan= &zspan;
784         spart.rectdaps= pa->rectdaps;
785         spart.rectz= pa->rectz;
786         spart.rectmask= pa->rectmask;
787         spart.cache= cache;
788         spart.shadow= shadow;
789         spart.jit= jit;
790
791         zbuf_alloc_span(&zspan, pa->rectx, pa->recty, clipcrop);
792
793         /* needed for transform from hoco to zbuffer co */
794         zspan.zmulx= ((float)winx)/2.0;
795         zspan.zmuly= ((float)winy)/2.0;
796         
797         zspan.zofsx= -pa->disprect.xmin;
798         zspan.zofsy= -pa->disprect.ymin;
799
800         /* to center the sample position */
801         if(!shadow) {
802                 zspan.zofsx -= 0.5f;
803                 zspan.zofsy -= 0.5f;
804         }
805
806         zspan.apsmbase= apsmbase;
807
808         /* clipping setup */
809         bounds[0]= (2*pa->disprect.xmin - winx-1)/(float)winx;
810         bounds[1]= (2*pa->disprect.xmax - winx+1)/(float)winx;
811         bounds[2]= (2*pa->disprect.ymin - winy-1)/(float)winy;
812         bounds[3]= (2*pa->disprect.ymax - winy+1)/(float)winy;
813
814         memarena= BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE);
815         firstseg= NULL;
816         sortseg= sortsegments;
817         totsegment= 0;
818
819         /* for all object instances */
820         for(obi=re->instancetable.first, i=0; obi; obi=obi->next, i++) {
821                 obr= obi->obr;
822
823                 if(!obr->strandbuf || !(obr->strandbuf->lay & lay))
824                         continue;
825
826                 /* compute matrix and try clipping whole object */
827                 if(obi->flag & R_TRANSFORMED)
828                         mul_m4_m4m4(obwinmat, obi->mat, winmat);
829                 else
830                         copy_m4_m4(obwinmat, winmat);
831
832                 if(clip_render_object(obi->obr->boundbox, bounds, winmat))
833                         continue;
834
835                 /* for each bounding box containing a number of strands */
836                 sbound= obr->strandbuf->bound;
837                 for(c=0; c<obr->strandbuf->totbound; c++, sbound++) {
838                         if(clip_render_object(sbound->boundbox, bounds, winmat))
839                                 continue;
840
841                         /* for each strand in this bounding box */
842                         for(a=sbound->start; a<sbound->end; a++) {
843                                 strand= RE_findOrAddStrand(obr, a);
844                                 svert= strand->vert;
845
846                                 /* keep clipping and z depth for 4 control points */
847                                 clip[1]= strand_test_clip(obwinmat, &zspan, bounds, svert->co, &z[1]);
848                                 clip[2]= strand_test_clip(obwinmat, &zspan, bounds, (svert+1)->co, &z[2]);
849                                 clip[0]= clip[1]; z[0]= z[1];
850
851                                 for(b=0; b<strand->totvert-1; b++, svert++) {
852                                         /* compute 4th point clipping and z depth */
853                                         if(b < strand->totvert-2) {
854                                                 clip[3]= strand_test_clip(obwinmat, &zspan, bounds, (svert+2)->co, &z[3]);
855                                         }
856                                         else {
857                                                 clip[3]= clip[2]; z[3]= z[2];
858                                         }
859
860                                         /* check clipping and add to sortsegments buffer */
861                                         if(!(clip[0] & clip[1] & clip[2] & clip[3])) {
862                                                 sortseg= BLI_memarena_alloc(memarena, sizeof(StrandSortSegment));
863                                                 sortseg->obi= i;
864                                                 sortseg->strand= strand->index;
865                                                 sortseg->segment= b;
866
867                                                 sortseg->z= 0.5f*(z[1] + z[2]);
868
869                                                 sortseg->next= firstseg;
870                                                 firstseg= sortseg;
871                                                 totsegment++;
872                                         }
873
874                                         /* shift clipping and z depth */
875                                         clip[0]= clip[1]; z[0]= z[1];
876                                         clip[1]= clip[2]; z[1]= z[2];
877                                         clip[2]= clip[3]; z[2]= z[3];
878                                 }
879                         }
880                 }
881         }
882
883         if(!re->test_break(re->tbh)) {
884                 /* convert list to array and sort */
885                 sortsegments= MEM_mallocN(sizeof(StrandSortSegment)*totsegment, "StrandSortSegment");
886                 for(a=0, sortseg=firstseg; a<totsegment; a++, sortseg=sortseg->next)
887                         sortsegments[a]= *sortseg;
888                 qsort(sortsegments, totsegment, sizeof(StrandSortSegment), compare_strand_segment);
889         }
890
891         BLI_memarena_free(memarena);
892
893         spart.totapixbuf= MEM_callocN(sizeof(int)*pa->rectx*pa->recty, "totapixbuf");
894
895         if(!re->test_break(re->tbh)) {
896                 /* render segments in sorted order */
897                 sortseg= sortsegments;
898                 for(a=0; a<totsegment; a++, sortseg++) {
899                         if(re->test_break(re->tbh))
900                                 break;
901
902                         obi= &re->objectinstance[sortseg->obi];
903                         obr= obi->obr;
904
905                         if(obi->flag & R_TRANSFORMED)
906                                 mul_m4_m4m4(obwinmat, obi->mat, winmat);
907                         else
908                                 copy_m4_m4(obwinmat, winmat);
909
910                         sseg.obi= obi;
911                         sseg.strand= RE_findOrAddStrand(obr, sortseg->strand);
912                         sseg.buffer= sseg.strand->buffer;
913                         sseg.sqadaptcos= sseg.buffer->adaptcos;
914                         sseg.sqadaptcos *= sseg.sqadaptcos;
915
916                         svert= sseg.strand->vert + sortseg->segment;
917                         sseg.v[0]= (sortseg->segment > 0)? (svert-1): svert;
918                         sseg.v[1]= svert;
919                         sseg.v[2]= svert+1;
920                         sseg.v[3]= (sortseg->segment < sseg.strand->totvert-2)? svert+2: svert+1;
921                         sseg.shaded= 0;
922
923                         spart.segment= &sseg;
924
925                         render_strand_segment(re, obwinmat, &spart, &zspan, 1, &sseg);
926                 }
927         }
928
929         if(sortsegments)
930                 MEM_freeN(sortsegments);
931         MEM_freeN(spart.totapixbuf);
932         
933         zbuf_free_span(&zspan);
934
935         return totsegment;
936 }
937
938 /* *************** */
939
940 StrandSurface *cache_strand_surface(Render *re, ObjectRen *obr, DerivedMesh *dm, float mat[][4], int timeoffset)
941 {
942         StrandSurface *mesh;
943         MFace *mface;
944         MVert *mvert;
945         float (*co)[3];
946         int a, totvert, totface;
947
948         totvert= dm->getNumVerts(dm);
949         totface= dm->getNumFaces(dm);
950
951         for(mesh=re->strandsurface.first; mesh; mesh=mesh->next)
952                 if(mesh->obr.ob == obr->ob && mesh->obr.par == obr->par
953                         && mesh->obr.index == obr->index && mesh->totvert==totvert && mesh->totface==totface)
954                         break;
955
956         if(!mesh) {
957                 mesh= MEM_callocN(sizeof(StrandSurface), "StrandSurface");
958                 mesh->obr= *obr;
959                 mesh->totvert= totvert;
960                 mesh->totface= totface;
961                 mesh->face= MEM_callocN(sizeof(int)*4*mesh->totface, "StrandSurfFaces");
962                 mesh->ao= MEM_callocN(sizeof(float)*3*mesh->totvert, "StrandSurfAO");
963                 mesh->indirect= MEM_callocN(sizeof(float)*3*mesh->totvert, "StrandSurfIndirect");
964                 BLI_addtail(&re->strandsurface, mesh);
965         }
966
967         if(timeoffset == -1 && !mesh->prevco)
968                 mesh->prevco= co= MEM_callocN(sizeof(float)*3*mesh->totvert, "StrandSurfCo");
969         else if(timeoffset == 0 && !mesh->co)
970                 mesh->co= co= MEM_callocN(sizeof(float)*3*mesh->totvert, "StrandSurfCo");
971         else if(timeoffset == 1 && !mesh->nextco)
972                 mesh->nextco= co= MEM_callocN(sizeof(float)*3*mesh->totvert, "StrandSurfCo");
973         else
974                 return mesh;
975
976         mvert= dm->getVertArray(dm);
977         for(a=0; a<mesh->totvert; a++, mvert++) {
978                 VECCOPY(co[a], mvert->co);
979                 mul_m4_v3(mat, co[a]);
980         }
981
982         mface= dm->getFaceArray(dm);
983         for(a=0; a<mesh->totface; a++, mface++) {
984                 mesh->face[a][0]= mface->v1;
985                 mesh->face[a][1]= mface->v2;
986                 mesh->face[a][2]= mface->v3;
987                 mesh->face[a][3]= mface->v4;
988         }
989
990         return mesh;
991 }
992
993 void free_strand_surface(Render *re)
994 {
995         StrandSurface *mesh;
996
997         for(mesh=re->strandsurface.first; mesh; mesh=mesh->next) {
998                 if(mesh->co) MEM_freeN(mesh->co);
999                 if(mesh->prevco) MEM_freeN(mesh->prevco);
1000                 if(mesh->nextco) MEM_freeN(mesh->nextco);
1001                 if(mesh->ao) MEM_freeN(mesh->ao);
1002                 if(mesh->indirect) MEM_freeN(mesh->indirect);
1003                 if(mesh->face) MEM_freeN(mesh->face);
1004         }
1005
1006         BLI_freelistN(&re->strandsurface);
1007 }
1008
1009 void strand_minmax(StrandRen *strand, float *min, float *max)
1010 {
1011         StrandVert *svert;
1012         int a;
1013
1014         for(a=0, svert=strand->vert; a<strand->totvert; a++, svert++)
1015                 DO_MINMAX(svert->co, min, max)
1016 }
1017