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