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