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 StrandShadeCache *strand_shade_cache_create(void)
 327 {
 328         StrandShadeCache *cache;
 329
 330         cache= MEM_callocN(sizeof(StrandShadeCache), "StrandShadeCache");
 331         cache->resulthash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "strand_shade_cache_create1 gh");
 332         cache->refcounthash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "strand_shade_cache_create2 gh");
 333         cache->memarena= BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "strand shade cache arena");
 334
 335         return cache;
 336 }
 337
 338 void strand_shade_cache_free(StrandShadeCache *cache)
 339 {
 340         BLI_ghash_free(cache->refcounthash, NULL, NULL);
 341         BLI_ghash_free(cache->resulthash, NULL, (GHashValFreeFP)MEM_freeN);
 342         BLI_memarena_free(cache->memarena);
 343         MEM_freeN(cache);
 344 }
 345
 346 static void strand_shade_get(Render *re, StrandShadeCache *cache, ShadeSample *ssamp, StrandSegment *sseg, StrandVert *svert)
 347 {
 348         ShadeResult *hashshr;
 349         StrandPoint p;
 350         int *refcount;
 351
 352         hashshr= BLI_ghash_lookup(cache->resulthash, svert);
 353         refcount= BLI_ghash_lookup(cache->refcounthash, svert);
 354
 355         if (!hashshr) {
 356                 /* not shaded yet, shade and insert into hash */
 357                 p.t= (sseg->v[1] == svert)? 0.0f: 1.0f;
 358                 strand_eval_point(sseg, &p);
 359                 strand_shade_point(re, ssamp, sseg, svert, &p);
 360
 361                 hashshr= MEM_callocN(sizeof(ShadeResult), "HashShadeResult");
 362                 *hashshr= ssamp->shr[0];
 363                 BLI_ghash_insert(cache->resulthash, svert, hashshr);
 364         }
 365         else
 366                 /* already shaded, just copy previous result from hash */
 367                 ssamp->shr[0]= *hashshr;
 368
 369         /* lower reference count and remove if not needed anymore by any samples */
 370         (*refcount)--;
 371         if (*refcount == 0) {
 372                 BLI_ghash_remove(cache->resulthash, svert, NULL, (GHashValFreeFP)MEM_freeN);
 373                 BLI_ghash_remove(cache->refcounthash, svert, NULL, NULL);
 374         }
 375 }
 376
 377 void strand_shade_segment(Render *re, StrandShadeCache *cache, StrandSegment *sseg, ShadeSample *ssamp, float t, float s, int addpassflag)
 378 {
 379         ShadeResult shr1, shr2;
 380
 381         /* get shading for two endpoints and interpolate */
 382         strand_shade_get(re, cache, ssamp, sseg, sseg->v[1]);
 383         shr1= ssamp->shr[0];
 384         strand_shade_get(re, cache, ssamp, sseg, sseg->v[2]);
 385         shr2= ssamp->shr[0];
 386
 387         interpolate_shade_result(&shr1, &shr2, t, ssamp->shr, addpassflag);
 388
 389         /* apply alpha along width */
 390         if (sseg->buffer->widthfade != 0.0f) {
 391                 s = 1.0f - pow(fabs(s), sseg->buffer->widthfade);
 392
 393                 strand_apply_shaderesult_alpha(ssamp->shr, s);
 394         }
 395 }
 396
 397 void strand_shade_unref(StrandShadeCache *cache, StrandVert *svert)
 398 {
 399         int *refcount;
 400
 401         /* lower reference count and remove if not needed anymore by any samples */
 402         refcount= BLI_ghash_lookup(cache->refcounthash, svert);
 403
 404         (*refcount)--;
 405         if (*refcount == 0) {
 406                 BLI_ghash_remove(cache->resulthash, svert, NULL, (GHashValFreeFP)MEM_freeN);
 407                 BLI_ghash_remove(cache->refcounthash, svert, NULL, NULL);
 408         }
 409 }
 410
 411 static void strand_shade_refcount(StrandShadeCache *cache, StrandVert *svert)
 412 {
 413         int *refcount= BLI_ghash_lookup(cache->refcounthash, svert);
 414
 415         if (!refcount) {
 416                 refcount= BLI_memarena_alloc(cache->memarena, sizeof(int));
 417                 *refcount= 1;
 418                 BLI_ghash_insert(cache->refcounthash, svert, refcount);
 419         }
 420         else
 421                 (*refcount)++;
 422 }
 423
 424 /* *************** */
 425
 426 typedef struct StrandPart {
 427         Render *re;
 428         ZSpan *zspan;
 429
 430         APixstrand *apixbuf;
 431         int *totapixbuf;
 432         int *rectz;
 433         int *rectmask;
 434         intptr_t *rectdaps;
 435         int rectx, recty;
 436         int sample;
 437         int shadow;
 438         float (*jit)[2];
 439
 440         StrandSegment *segment;
 441         float t[3], s[3];
 442
 443         StrandShadeCache *cache;
 444 } StrandPart;
 445
 446 typedef struct StrandSortSegment {
 447         struct StrandSortSegment *next;
 448         int obi, strand, segment;
 449         float z;
 450 } StrandSortSegment;
 451
 452 static int compare_strand_segment(const void *poin1, const void *poin2)
 453 {
 454         const StrandSortSegment *seg1= (const StrandSortSegment*)poin1;
 455         const StrandSortSegment *seg2= (const StrandSortSegment*)poin2;
 456
 457         if (seg1->z < seg2->z)
 458                 return -1;
 459         else if (seg1->z == seg2->z)
 460                 return 0;
 461         else
 462                 return 1;
 463 }
 464
 465 static void do_strand_point_project(float winmat[][4], ZSpan *zspan, float *co, float *hoco, float *zco)
 466 {
 467         projectvert(co, winmat, hoco);
 468         hoco_to_zco(zspan, zco, hoco);
 469 }
 470
 471 static void strand_project_point(float winmat[][4], float winx, float winy, StrandPoint *spoint)
 472 {
 473         float div;
 474
 475         projectvert(spoint->co, winmat, spoint->hoco);
 476
 477         div= 1.0f/spoint->hoco[3];
 478         spoint->x= spoint->hoco[0]*div*winx*0.5f;
 479         spoint->y= spoint->hoco[1]*div*winy*0.5f;
 480 }
 481
 482 static APixstrand *addpsmainAstrand(ListBase *lb)
 483 {
 484         APixstrMain *psm;
 485
 486         psm= MEM_mallocN(sizeof(APixstrMain), "addpsmainA");
 487         BLI_addtail(lb, psm);
 488         psm->ps= MEM_callocN(4096*sizeof(APixstrand),"pixstr");
 489
 490         return psm->ps;
 491 }
 492
 493 static APixstrand *addpsAstrand(ZSpan *zspan)
 494 {
 495         /* make new PS */
 496         if (zspan->apstrandmcounter==0) {
 497                 zspan->curpstrand= addpsmainAstrand(zspan->apsmbase);
 498                 zspan->apstrandmcounter= 4095;
 499         }
 500         else {
 501                 zspan->curpstrand++;
 502                 zspan->apstrandmcounter--;
 503         }
 504         return zspan->curpstrand;
 505 }
 506
 507 #define MAX_ZROW        2000
 508
 509 static void do_strand_fillac(void *handle, int x, int y, float u, float v, float z)
 510 {
 511         StrandPart *spart= (StrandPart*)handle;
 512         StrandShadeCache *cache= spart->cache;
 513         StrandSegment *sseg= spart->segment;
 514         APixstrand *apn, *apnew;
 515         float t, s;
 516         int offset, mask, obi, strnr, seg, zverg, bufferz, maskz=0;
 517
 518         offset = y*spart->rectx + x;
 519         obi= sseg->obi - spart->re->objectinstance;
 520         strnr= sseg->strand->index + 1;
 521         seg= sseg->v[1] - sseg->strand->vert;
 522         mask= (1<<spart->sample);
 523
 524         /* check against solid z-buffer */
 525         zverg= (int)z;
 526
 527         if (spart->rectdaps) {
 528                 /* find the z of the sample */
 529                 PixStr *ps;
 530                 intptr_t *rd= spart->rectdaps + offset;
 531
 532                 bufferz= 0x7FFFFFFF;
 533                 if (spart->rectmask) maskz= 0x7FFFFFFF;
 534
 535                 if (*rd) {
 536                         for (ps= (PixStr *)(*rd); ps; ps= ps->next) {
 537                                 if (mask & ps->mask) {
 538                                         bufferz= ps->z;
 539                                         if (spart->rectmask)
 540                                                 maskz= ps->maskz;
 541                                         break;
 542                                 }
 543                         }
 544                 }
 545         }
 546         else {
 547                 bufferz= (spart->rectz)? spart->rectz[offset]: 0x7FFFFFFF;
 548                 if (spart->rectmask)
 549                         maskz= spart->rectmask[offset];
 550         }
 551
 552 #define CHECK_ADD(n) \
 553         if (apn->p[n]==strnr && apn->obi[n]==obi && apn->seg[n]==seg) \
 554         { if (!(apn->mask[n] & mask)) { apn->mask[n] |= mask; apn->v[n] += t; apn->u[n] += s; } break; }
 555 #define CHECK_ASSIGN(n) \
 556         if (apn->p[n]==0) \
 557         {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; }
 558
 559         /* add to pixel list */
 560         if (zverg < bufferz && (spart->totapixbuf[offset] < MAX_ZROW)) {
 561                 if (!spart->rectmask || zverg > maskz) {
 562                         t = u*spart->t[0] + v*spart->t[1] + (1.0f-u-v)*spart->t[2];
 563                         s = fabs(u*spart->s[0] + v*spart->s[1] + (1.0f-u-v)*spart->s[2]);
 564
 565                         apn= spart->apixbuf + offset;
 566                         while (apn) {
 567                                 CHECK_ADD(0);
 568                                 CHECK_ADD(1);
 569                                 CHECK_ADD(2);
 570                                 CHECK_ADD(3);
 571                                 CHECK_ASSIGN(0);
 572                                 CHECK_ASSIGN(1);
 573                                 CHECK_ASSIGN(2);
 574                                 CHECK_ASSIGN(3);
 575
 576                                 apnew= addpsAstrand(spart->zspan);
 577                                 SWAP(APixstrand, *apnew, *apn);
 578                                 apn->next= apnew;
 579                                 CHECK_ASSIGN(0);
 580                         }
 581
 582                         if (cache) {
 583                                 strand_shade_refcount(cache, sseg->v[1]);
 584                                 strand_shade_refcount(cache, sseg->v[2]);
 585                         }
 586                         spart->totapixbuf[offset]++;
 587                 }
 588         }
 589 }
 590
 591 /* width is calculated in hoco space, to ensure strands are visible */
 592 static int strand_test_clip(float winmat[][4], ZSpan *UNUSED(zspan), float *bounds, float *co, float *zcomp, float widthx, float widthy)
 593 {
 594         float hoco[4];
 595         int clipflag= 0;
 596
 597         projectvert(co, winmat, hoco);
 598
 599         /* we compare z without perspective division for segment sorting */
 600         *zcomp= hoco[2];
 601
 602         if (hoco[0]+widthx < bounds[0]*hoco[3]) clipflag |= 1;
 603         else if (hoco[0]-widthx > bounds[1]*hoco[3]) clipflag |= 2;
 604
 605         if (hoco[1]-widthy > bounds[3]*hoco[3]) clipflag |= 4;
 606         else if (hoco[1]+widthy < bounds[2]*hoco[3]) clipflag |= 8;
 607
 608         clipflag |= testclip(hoco);
 609
 610         return clipflag;
 611 }
 612
 613 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)
 614 {
 615         float jco1[3], jco2[3], jco3[3], jco4[3], jx, jy;
 616
 617         copy_v3_v3(jco1, co1);
 618         copy_v3_v3(jco2, co2);
 619         copy_v3_v3(jco3, co3);
 620         copy_v3_v3(jco4, co4);
 621
 622         if (spart->jit) {
 623                 jx= -spart->jit[sample][0];
 624                 jy= -spart->jit[sample][1];
 625
 626                 jco1[0] += jx; jco1[1] += jy;
 627                 jco2[0] += jx; jco2[1] += jy;
 628                 jco3[0] += jx; jco3[1] += jy;
 629                 jco4[0] += jx; jco4[1] += jy;
 630
 631                 /* XXX mblur? */
 632         }
 633
 634         spart->sample= sample;
 635
 636         spart->t[0]= t-dt;
 637         spart->s[0]= -1.0f;
 638         spart->t[1]= t-dt;
 639         spart->s[1]= 1.0f;
 640         spart->t[2]= t;
 641         spart->s[2]= 1.0f;
 642         zspan_scanconvert_strand(zspan, spart, jco1, jco2, jco3, do_strand_fillac);
 643         spart->t[0]= t-dt;
 644         spart->s[0]= -1.0f;
 645         spart->t[1]= t;
 646         spart->s[1]= 1.0f;
 647         spart->t[2]= t;
 648         spart->s[2]= -1.0f;
 649         zspan_scanconvert_strand(zspan, spart, jco1, jco3, jco4, do_strand_fillac);
 650 }
 651
 652 static void strand_render(Render *re, StrandSegment *sseg, float winmat[][4], StrandPart *spart, ZSpan *zspan, int totzspan, StrandPoint *p1, StrandPoint *p2)
 653 {
 654         if (spart) {
 655                 float t= p2->t;
 656                 float dt= p2->t - p1->t;
 657                 int a;
 658
 659                 if (re->osa) {
 660                         for (a=0; a<re->osa; a++)
 661                                 do_scanconvert_strand(re, spart, zspan, t, dt, p1->zco2, p1->zco1, p2->zco1, p2->zco2, a);
 662                 }
 663                 else
 664                         do_scanconvert_strand(re, spart, zspan, t, dt, p1->zco2, p1->zco1, p2->zco1, p2->zco2, 0);
 665         }
 666         else {
 667                 float hoco1[4], hoco2[4];
 668                 int a, obi, index;
 669
 670                 obi= sseg->obi - re->objectinstance;
 671                 index= sseg->strand->index;
 672
 673                 projectvert(p1->co, winmat, hoco1);
 674                 projectvert(p2->co, winmat, hoco2);
 675
 676
 677                 for (a=0; a<totzspan; a++) {
 678 #if 0
 679                         /* render both strand and single pixel wire to counter aliasing */
 680                         zbufclip4(re, &zspan[a], obi, index, p1->hoco2, p1->hoco1, p2->hoco1, p2->hoco2, p1->clip2, p1->clip1, p2->clip1, p2->clip2);
 681 #endif
 682                         /* only render a line for now, which makes the shadow map more
 683                          * similar across frames, and so reduces flicker */
 684                         zbufsinglewire(&zspan[a], obi, index, hoco1, hoco2);
 685                 }
 686         }
 687 }
 688
 689 static int strand_segment_recursive(Render *re, float winmat[][4], StrandPart *spart, ZSpan *zspan, int totzspan, StrandSegment *sseg, StrandPoint *p1, StrandPoint *p2, int depth)
 690 {
 691         StrandPoint p;
 692         StrandBuffer *buffer= sseg->buffer;
 693         float dot, d1[2], d2[2], len1, len2;
 694
 695         if (depth == buffer->maxdepth)
 696                 return 0;
 697
 698         p.t= (p1->t + p2->t)*0.5f;
 699         strand_eval_point(sseg, &p);
 700         strand_project_point(buffer->winmat, buffer->winx, buffer->winy, &p);
 701
 702         d1[0]= (p.x - p1->x);
 703         d1[1]= (p.y - p1->y);
 704         len1= d1[0]*d1[0] + d1[1]*d1[1];
 705
 706         d2[0]= (p2->x - p.x);
 707         d2[1]= (p2->y - p.y);
 708         len2= d2[0]*d2[0] + d2[1]*d2[1];
 709
 710         if (len1 == 0.0f || len2 == 0.0f)
 711                 return 0;
 712
 713         dot= d1[0]*d2[0] + d1[1]*d2[1];
 714         if (dot*dot > sseg->sqadaptcos*len1*len2)
 715                 return 0;
 716
 717         if (spart) {
 718                 do_strand_point_project(winmat, zspan, p.co1, p.hoco1, p.zco1);
 719                 do_strand_point_project(winmat, zspan, p.co2, p.hoco2, p.zco2);
 720         }
 721         else {
 722 #if 0
 723                 projectvert(p.co1, winmat, p.hoco1);
 724                 projectvert(p.co2, winmat, p.hoco2);
 725                 p.clip1= testclip(p.hoco1);
 726                 p.clip2= testclip(p.hoco2);
 727 #endif
 728         }
 729
 730         if (!strand_segment_recursive(re, winmat, spart, zspan, totzspan, sseg, p1, &p, depth+1))
 731                 strand_render(re, sseg, winmat, spart, zspan, totzspan, p1, &p);
 732         if (!strand_segment_recursive(re, winmat, spart, zspan, totzspan, sseg, &p, p2, depth+1))
 733                 strand_render(re, sseg, winmat, spart, zspan, totzspan, &p, p2);
 734
 735         return 1;
 736 }
 737
 738 void render_strand_segment(Render *re, float winmat[][4], StrandPart *spart, ZSpan *zspan, int totzspan, StrandSegment *sseg)
 739 {
 740         StrandBuffer *buffer= sseg->buffer;
 741         StrandPoint *p1= &sseg->point1;
 742         StrandPoint *p2= &sseg->point2;
 743
 744         p1->t= 0.0f;
 745         p2->t= 1.0f;
 746
 747         strand_eval_point(sseg, p1);
 748         strand_project_point(buffer->winmat, buffer->winx, buffer->winy, p1);
 749         strand_eval_point(sseg, p2);
 750         strand_project_point(buffer->winmat, buffer->winx, buffer->winy, p2);
 751
 752         if (spart) {
 753                 do_strand_point_project(winmat, zspan, p1->co1, p1->hoco1, p1->zco1);
 754                 do_strand_point_project(winmat, zspan, p1->co2, p1->hoco2, p1->zco2);
 755                 do_strand_point_project(winmat, zspan, p2->co1, p2->hoco1, p2->zco1);
 756                 do_strand_point_project(winmat, zspan, p2->co2, p2->hoco2, p2->zco2);
 757         }
 758         else {
 759 #if 0
 760                 projectvert(p1->co1, winmat, p1->hoco1);
 761                 projectvert(p1->co2, winmat, p1->hoco2);
 762                 projectvert(p2->co1, winmat, p2->hoco1);
 763                 projectvert(p2->co2, winmat, p2->hoco2);
 764                 p1->clip1= testclip(p1->hoco1);
 765                 p1->clip2= testclip(p1->hoco2);
 766                 p2->clip1= testclip(p2->hoco1);
 767                 p2->clip2= testclip(p2->hoco2);
 768 #endif
 769         }
 770
 771         if (!strand_segment_recursive(re, winmat, spart, zspan, totzspan, sseg, p1, p2, 0))
 772                 strand_render(re, sseg, winmat, spart, zspan, totzspan, p1, p2);
 773 }
 774
 775 /* render call to fill in strands */
 776 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)
 777 {
 778         ObjectRen *obr;
 779         ObjectInstanceRen *obi;
 780         ZSpan zspan;
 781         StrandRen *strand=0;
 782         StrandVert *svert;
 783         StrandBound *sbound;
 784         StrandPart spart;
 785         StrandSegment sseg;
 786         StrandSortSegment *sortsegments = NULL, *sortseg, *firstseg;
 787         MemArena *memarena;
 788         float z[4], bounds[4], obwinmat[4][4];
 789         int a, b, c, i, totsegment, clip[4];
 790
 791         if (re->test_break(re->tbh))
 792                 return 0;
 793         if (re->totstrand == 0)
 794                 return 0;
 795
 796         /* setup StrandPart */
 797         memset(&spart, 0, sizeof(spart));
 798
 799         spart.re= re;
 800         spart.rectx= pa->rectx;
 801         spart.recty= pa->recty;
 802         spart.apixbuf= apixbuf;
 803         spart.zspan= &zspan;
 804         spart.rectdaps= pa->rectdaps;
 805         spart.rectz= pa->rectz;
 806         spart.rectmask= pa->rectmask;
 807         spart.cache= cache;
 808         spart.shadow= shadow;
 809         spart.jit= jit;
 810
 811         zbuf_alloc_span(&zspan, pa->rectx, pa->recty, clipcrop);
 812
 813         /* needed for transform from hoco to zbuffer co */
 814         zspan.zmulx= ((float)winx)/2.0f;
 815         zspan.zmuly= ((float)winy)/2.0f;
 816
 817         zspan.zofsx= -pa->disprect.xmin;
 818         zspan.zofsy= -pa->disprect.ymin;
 819
 820         /* to center the sample position */
 821         if (!shadow) {
 822                 zspan.zofsx -= 0.5f;
 823                 zspan.zofsy -= 0.5f;
 824         }
 825
 826         zspan.apsmbase= apsmbase;
 827
 828         /* clipping setup */
 829         bounds[0]= (2*pa->disprect.xmin - winx-1)/(float)winx;
 830         bounds[1]= (2*pa->disprect.xmax - winx+1)/(float)winx;
 831         bounds[2]= (2*pa->disprect.ymin - winy-1)/(float)winy;
 832         bounds[3]= (2*pa->disprect.ymax - winy+1)/(float)winy;
 833
 834         memarena= BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "strand sort arena");
 835         firstseg= NULL;
 836         totsegment= 0;
 837
 838         /* for all object instances */
 839         for (obi=re->instancetable.first, i=0; obi; obi=obi->next, i++) {
 840                 Material *ma;
 841                 float widthx, widthy;
 842
 843                 obr= obi->obr;
 844
 845                 if (!obr->strandbuf || !(obr->strandbuf->lay & lay))
 846                         continue;
 847
 848                 /* compute matrix and try clipping whole object */
 849                 if (obi->flag & R_TRANSFORMED)
 850                         mult_m4_m4m4(obwinmat, winmat, obi->mat);
 851                 else
 852                         copy_m4_m4(obwinmat, winmat);
 853
 854                 /* test if we should skip it */
 855                 ma = obr->strandbuf->ma;
 856
 857                 if (shadow && !(ma->mode & MA_SHADBUF))
 858                         continue;
 859                 else if (!shadow && (ma->mode & MA_ONLYCAST))
 860                         continue;
 861
 862                 if (clip_render_object(obi->obr->boundbox, bounds, obwinmat))
 863                         continue;
 864
 865                 widthx= obr->strandbuf->maxwidth*obwinmat[0][0];
 866                 widthy= obr->strandbuf->maxwidth*obwinmat[1][1];
 867
 868                 /* for each bounding box containing a number of strands */
 869                 sbound= obr->strandbuf->bound;
 870                 for (c=0; c<obr->strandbuf->totbound; c++, sbound++) {
 871                         if (clip_render_object(sbound->boundbox, bounds, obwinmat))
 872                                 continue;
 873
 874                         /* for each strand in this bounding box */
 875                         for (a=sbound->start; a<sbound->end; a++) {
 876                                 strand= RE_findOrAddStrand(obr, a);
 877                                 svert= strand->vert;
 878
 879                                 /* keep clipping and z depth for 4 control points */
 880                                 clip[1]= strand_test_clip(obwinmat, &zspan, bounds, svert->co, &z[1], widthx, widthy);
 881                                 clip[2]= strand_test_clip(obwinmat, &zspan, bounds, (svert+1)->co, &z[2], widthx, widthy);
 882                                 clip[0]= clip[1]; z[0]= z[1];
 883
 884                                 for (b=0; b<strand->totvert-1; b++, svert++) {
 885                                         /* compute 4th point clipping and z depth */
 886                                         if (b < strand->totvert-2) {
 887                                                 clip[3]= strand_test_clip(obwinmat, &zspan, bounds, (svert+2)->co, &z[3], widthx, widthy);
 888                                         }
 889                                         else {
 890                                                 clip[3]= clip[2]; z[3]= z[2];
 891                                         }
 892
 893                                         /* check clipping and add to sortsegments buffer */
 894                                         if (!(clip[0] & clip[1] & clip[2] & clip[3])) {
 895                                                 sortseg= BLI_memarena_alloc(memarena, sizeof(StrandSortSegment));
 896                                                 sortseg->obi= i;
 897                                                 sortseg->strand= strand->index;
 898                                                 sortseg->segment= b;
 899
 900                                                 sortseg->z= 0.5f*(z[1] + z[2]);
 901
 902                                                 sortseg->next= firstseg;
 903                                                 firstseg= sortseg;
 904                                                 totsegment++;
 905                                         }
 906
 907                                         /* shift clipping and z depth */
 908                                         clip[0]= clip[1]; z[0]= z[1];
 909                                         clip[1]= clip[2]; z[1]= z[2];
 910                                         clip[2]= clip[3]; z[2]= z[3];
 911                                 }
 912                         }
 913                 }
 914         }
 915
 916         if (!re->test_break(re->tbh)) {
 917                 /* convert list to array and sort */
 918                 sortsegments= MEM_mallocN(sizeof(StrandSortSegment)*totsegment, "StrandSortSegment");
 919                 for (a=0, sortseg=firstseg; a<totsegment; a++, sortseg=sortseg->next)
 920                         sortsegments[a]= *sortseg;
 921                 qsort(sortsegments, totsegment, sizeof(StrandSortSegment), compare_strand_segment);
 922         }
 923
 924         BLI_memarena_free(memarena);
 925
 926         spart.totapixbuf= MEM_callocN(sizeof(int)*pa->rectx*pa->recty, "totapixbuf");
 927
 928         if (!re->test_break(re->tbh)) {
 929                 /* render segments in sorted order */
 930                 sortseg= sortsegments;
 931                 for (a=0; a<totsegment; a++, sortseg++) {
 932                         if (re->test_break(re->tbh))
 933                                 break;
 934
 935                         obi= &re->objectinstance[sortseg->obi];
 936                         obr= obi->obr;
 937
 938                         sseg.obi= obi;
 939                         sseg.strand= RE_findOrAddStrand(obr, sortseg->strand);
 940                         sseg.buffer= sseg.strand->buffer;
 941                         sseg.sqadaptcos= sseg.buffer->adaptcos;
 942                         sseg.sqadaptcos *= sseg.sqadaptcos;
 943
 944                         svert= sseg.strand->vert + sortseg->segment;
 945                         sseg.v[0]= (sortseg->segment > 0)? (svert-1): svert;
 946                         sseg.v[1]= svert;
 947                         sseg.v[2]= svert+1;
 948                         sseg.v[3]= (sortseg->segment < sseg.strand->totvert-2)? svert+2: svert+1;
 949                         sseg.shaded= 0;
 950
 951                         spart.segment= &sseg;
 952
 953                         render_strand_segment(re, winmat, &spart, &zspan, 1, &sseg);
 954                 }
 955         }
 956
 957         if (sortsegments)
 958                 MEM_freeN(sortsegments);
 959         MEM_freeN(spart.totapixbuf);
 960
 961         zbuf_free_span(&zspan);
 962
 963         return totsegment;
 964 }
 965
 966 /* *************** */
 967
 968 StrandSurface *cache_strand_surface(Render *re, ObjectRen *obr, DerivedMesh *dm, float mat[][4], int timeoffset)
 969 {
 970         StrandSurface *mesh;
 971         MFace *mface;
 972         MVert *mvert;
 973         float (*co)[3];
 974         int a, totvert, totface;
 975
 976         totvert= dm->getNumVerts(dm);
 977         totface= dm->getNumTessFaces(dm);
 978
 979         for (mesh = re->strandsurface.first; mesh; mesh = mesh->next) {
 980                 if ((mesh->obr.ob    == obr->ob) &&
 981                     (mesh->obr.par   == obr->par) &&
 982                     (mesh->obr.index == obr->index) &&
 983                     (mesh->totvert   == totvert) &&
 984                     (mesh->totface   == totface))
 985                 {
 986                         break;
 987                 }
 988         }
 989
 990         if (!mesh) {
 991                 mesh= MEM_callocN(sizeof(StrandSurface), "StrandSurface");
 992                 mesh->obr= *obr;
 993                 mesh->totvert= totvert;
 994                 mesh->totface= totface;
 995                 mesh->face= MEM_callocN(sizeof(int)*4*mesh->totface, "StrandSurfFaces");
 996                 mesh->ao= MEM_callocN(sizeof(float)*3*mesh->totvert, "StrandSurfAO");
 997                 mesh->env= MEM_callocN(sizeof(float)*3*mesh->totvert, "StrandSurfEnv");
 998                 mesh->indirect= MEM_callocN(sizeof(float)*3*mesh->totvert, "StrandSurfIndirect");
 999                 BLI_addtail(&re->strandsurface, mesh);
1000         }
1001
1002         if (timeoffset == -1 && !mesh->prevco)
1003                 mesh->prevco= co= MEM_callocN(sizeof(float)*3*mesh->totvert, "StrandSurfCo");
1004         else if (timeoffset == 0 && !mesh->co)
1005                 mesh->co= co= MEM_callocN(sizeof(float)*3*mesh->totvert, "StrandSurfCo");
1006         else if (timeoffset == 1 && !mesh->nextco)
1007                 mesh->nextco= co= MEM_callocN(sizeof(float)*3*mesh->totvert, "StrandSurfCo");
1008         else
1009                 return mesh;
1010
1011         mvert= dm->getVertArray(dm);
1012         for (a=0; a<mesh->totvert; a++, mvert++) {
1013                 copy_v3_v3(co[a], mvert->co);
1014                 mul_m4_v3(mat, co[a]);
1015         }
1016
1017         mface= dm->getTessFaceArray(dm);
1018         for (a=0; a<mesh->totface; a++, mface++) {
1019                 mesh->face[a][0]= mface->v1;
1020                 mesh->face[a][1]= mface->v2;
1021                 mesh->face[a][2]= mface->v3;
1022                 mesh->face[a][3]= mface->v4;
1023         }
1024
1025         return mesh;
1026 }
1027
1028 void free_strand_surface(Render *re)
1029 {
1030         StrandSurface *mesh;
1031
1032         for (mesh=re->strandsurface.first; mesh; mesh=mesh->next) {
1033                 if (mesh->co) MEM_freeN(mesh->co);
1034                 if (mesh->prevco) MEM_freeN(mesh->prevco);
1035                 if (mesh->nextco) MEM_freeN(mesh->nextco);
1036                 if (mesh->ao) MEM_freeN(mesh->ao);
1037                 if (mesh->env) MEM_freeN(mesh->env);
1038                 if (mesh->indirect) MEM_freeN(mesh->indirect);
1039                 if (mesh->face) MEM_freeN(mesh->face);
1040         }
1041
1042         BLI_freelistN(&re->strandsurface);
1043 }
1044
1045 void strand_minmax(StrandRen *strand, float *min, float *max, float width)
1046 {
1047         StrandVert *svert;
1048         float vec[3], width2= 2.0f*width;
1049         int a;
1050
1051         for (a=0, svert=strand->vert; a<strand->totvert; a++, svert++) {
1052                 copy_v3_v3(vec, svert->co);
1053                 DO_MINMAX(vec, min, max);
1054
1055                 if (width!=0.0f) {
1056                         vec[0]+= width; vec[1]+= width; vec[2]+= width;
1057                         DO_MINMAX(vec, min, max);
1058                         vec[0]-= width2; vec[1]-= width2; vec[2]-= width2;
1059                         DO_MINMAX(vec, min, max);
1060                 }
1061         }
1062 }
1063