source/blender/render/intern/source/zbuf.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  * Contributors: Hos, RPW
  22  *               2004-2006 Blender Foundation, full recode
  23  *
  24  * ***** END GPL LICENSE BLOCK *****
  25  */
  26
  27 /** \file blender/render/intern/source/zbuf.c
  28  *  \ingroup render
  29  */
  30
  31
  32
  33 /*---------------------------------------------------------------------------*/
  34 /* Common includes                                                           */
  35 /*---------------------------------------------------------------------------*/
  36
  37 #include <math.h>
  38 #include <float.h>
  39 #include <stdlib.h>
  40 #include <limits.h>
  41 #include <string.h>
  42
  43 #include "BLI_math.h"
  44 #include "BLI_blenlib.h"
  45 #include "BLI_jitter.h"
  46 #include "BLI_threads.h"
  47 #include "BLI_utildefines.h"
  48
  49 #include "MEM_guardedalloc.h"
  50
  51 #include "DNA_lamp_types.h"
  52 #include "DNA_mesh_types.h"
  53 #include "DNA_node_types.h"
  54 #include "DNA_meshdata_types.h"
  55 #include "DNA_material_types.h"
  56
  57 #include "BKE_global.h"
  58 #include "BKE_material.h"
  59
  60
  61 #include "RE_render_ext.h"
  62
  63 /* local includes */
  64 #include "pixelblending.h"
  65 #include "render_result.h"
  66 #include "render_types.h"
  67 #include "renderpipeline.h"
  68 #include "renderdatabase.h"
  69 #include "rendercore.h"
  70 #include "shadbuf.h"
  71 #include "shading.h"
  72 #include "sss.h"
  73 #include "strand.h"
  74
  75 /* own includes */
  76 #include "zbuf.h"
  77
  78 /* could enable at some point but for now there are far too many conversions */
  79 #ifdef __GNUC__
  80 #  pragma GCC diagnostic ignored "-Wdouble-promotion"
  81 #endif
  82
  83 /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
  84 /* defined in pipeline.c, is hardcopy of active dynamic allocated Render */
  85 /* only to be used here in this file, it's for speed */
  86 extern struct Render R;
  87 /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
  88
  89
  90 /* ****************** Spans ******************************* */
  91
  92 /* each zbuffer has coordinates transformed to local rect coordinates, so we can simply clip */
  93 void zbuf_alloc_span(ZSpan *zspan, int rectx, int recty, float clipcrop)
  94 {
  95         memset(zspan, 0, sizeof(ZSpan));
  96
  97         zspan->rectx= rectx;
  98         zspan->recty= recty;
  99
 100         zspan->span1= MEM_mallocN(recty*sizeof(float), "zspan");
 101         zspan->span2= MEM_mallocN(recty*sizeof(float), "zspan");
 102
 103         zspan->clipcrop= clipcrop;
 104 }
 105
 106 void zbuf_free_span(ZSpan *zspan)
 107 {
 108         if (zspan) {
 109                 if (zspan->span1) MEM_freeN(zspan->span1);
 110                 if (zspan->span2) MEM_freeN(zspan->span2);
 111                 zspan->span1= zspan->span2= NULL;
 112         }
 113 }
 114
 115 /* reset range for clipping */
 116 static void zbuf_init_span(ZSpan *zspan)
 117 {
 118         zspan->miny1= zspan->miny2= zspan->recty+1;
 119         zspan->maxy1= zspan->maxy2= -1;
 120         zspan->minp1= zspan->maxp1= zspan->minp2= zspan->maxp2= NULL;
 121 }
 122
 123 static void zbuf_add_to_span(ZSpan *zspan, const float v1[2], const float v2[2])
 124 {
 125         const float *minv, *maxv;
 126         float *span;
 127         float xx1, dx0, xs0;
 128         int y, my0, my2;
 129
 130         if (v1[1]<v2[1]) {
 131                 minv= v1; maxv= v2;
 132         }
 133         else {
 134                 minv= v2; maxv= v1;
 135         }
 136
 137         my0= ceil(minv[1]);
 138         my2= floor(maxv[1]);
 139
 140         if (my2<0 || my0>= zspan->recty) return;
 141
 142         /* clip top */
 143         if (my2>=zspan->recty) my2= zspan->recty-1;
 144         /* clip bottom */
 145         if (my0<0) my0= 0;
 146
 147         if (my0>my2) return;
 148         /* if (my0>my2) should still fill in, that way we get spans that skip nicely */
 149
 150         xx1= maxv[1]-minv[1];
 151         if (xx1>FLT_EPSILON) {
 152                 dx0= (minv[0]-maxv[0])/xx1;
 153                 xs0= dx0*(minv[1]-my2) + minv[0];
 154         }
 155         else {
 156                 dx0 = 0.0f;
 157                 xs0 = min_ff(minv[0], maxv[0]);
 158         }
 159
 160         /* empty span */
 161         if (zspan->maxp1 == NULL) {
 162                 span= zspan->span1;
 163         }
 164         else {  /* does it complete left span? */
 165                 if ( maxv == zspan->minp1 || minv==zspan->maxp1) {
 166                         span= zspan->span1;
 167                 }
 168                 else {
 169                         span= zspan->span2;
 170                 }
 171         }
 172
 173         if (span==zspan->span1) {
 174 //              printf("left span my0 %d my2 %d\n", my0, my2);
 175                 if (zspan->minp1==NULL || zspan->minp1[1] > minv[1] ) {
 176                         zspan->minp1= minv;
 177                 }
 178                 if (zspan->maxp1==NULL || zspan->maxp1[1] < maxv[1] ) {
 179                         zspan->maxp1= maxv;
 180                 }
 181                 if (my0<zspan->miny1) zspan->miny1= my0;
 182                 if (my2>zspan->maxy1) zspan->maxy1= my2;
 183         }
 184         else {
 185 //              printf("right span my0 %d my2 %d\n", my0, my2);
 186                 if (zspan->minp2==NULL || zspan->minp2[1] > minv[1] ) {
 187                         zspan->minp2= minv;
 188                 }
 189                 if (zspan->maxp2==NULL || zspan->maxp2[1] < maxv[1] ) {
 190                         zspan->maxp2= maxv;
 191                 }
 192                 if (my0<zspan->miny2) zspan->miny2= my0;
 193                 if (my2>zspan->maxy2) zspan->maxy2= my2;
 194         }
 195
 196         for (y=my2; y>=my0; y--, xs0+= dx0) {
 197                 /* xs0 is the xcoord! */
 198                 span[y]= xs0;
 199         }
 200 }
 201
 202 /*-----------------------------------------------------------*/
 203 /* Functions                                                 */
 204 /*-----------------------------------------------------------*/
 205
 206 void fillrect(int *rect, int x, int y, int val)
 207 {
 208         int len, *drect;
 209
 210         len= x*y;
 211         drect= rect;
 212         while (len>0) {
 213                 len--;
 214                 *drect= val;
 215                 drect++;
 216         }
 217 }
 218
 219 /* based on Liang&Barsky, for clipping of pyramidical volume */
 220 static short cliptestf(float a, float b, float c, float d, float *u1, float *u2)
 221 {
 222         float p= a + b, q= c + d, r;
 223
 224         if (p<0.0f) {
 225                 if (q<p) return 0;
 226                 else if (q<0.0f) {
 227                         r= q/p;
 228                         if (r>*u2) return 0;
 229                         else if (r>*u1) *u1=r;
 230                 }
 231         }
 232         else {
 233                 if (p>0.0f) {
 234                         if (q<0.0f) return 0;
 235                         else if (q<p) {
 236                                 r= q/p;
 237                                 if (r<*u1) return 0;
 238                                 else if (r<*u2) *u2=r;
 239                         }
 240                 }
 241                 else if (q<0.0f) return 0;
 242         }
 243         return 1;
 244 }
 245
 246 int testclip(const float v[4])
 247 {
 248         float abs4;     /* WATCH IT: this function should do the same as cliptestf, otherwise troubles in zbufclip()*/
 249         short c=0;
 250
 251         /* if we set clip flags, the clipping should be at least larger than epsilon.
 252          * prevents issues with vertices lying exact on borders */
 253         abs4= fabsf(v[3]) + FLT_EPSILON;
 254
 255         if ( v[0] < -abs4) c+=1;
 256         else if ( v[0] > abs4) c+=2;
 257
 258         if ( v[1] > abs4) c+=4;
 259         else if ( v[1] < -abs4) c+=8;
 260
 261         if (v[2] < -abs4) c+=16;                        /* this used to be " if (v[2]<0) ", see clippz() */
 262         else if (v[2]> abs4) c+= 32;
 263
 264         return c;
 265 }
 266
 267
 268
 269 /* *************  ACCUMULATION ZBUF ************ */
 270
 271
 272 static APixstr *addpsmainA(ListBase *lb)
 273 {
 274         APixstrMain *psm;
 275
 276         psm= MEM_mallocN(sizeof(APixstrMain), "addpsmainA");
 277         BLI_addtail(lb, psm);
 278         psm->ps= MEM_callocN(4096*sizeof(APixstr), "pixstr");
 279
 280         return psm->ps;
 281 }
 282
 283 void freepsA(ListBase *lb)
 284 {
 285         APixstrMain *psm, *psmnext;
 286
 287         for (psm= lb->first; psm; psm= psmnext) {
 288                 psmnext= psm->next;
 289                 if (psm->ps)
 290                         MEM_freeN(psm->ps);
 291                 MEM_freeN(psm);
 292         }
 293 }
 294
 295 static APixstr *addpsA(ZSpan *zspan)
 296 {
 297         /* make new PS */
 298         if (zspan->apsmcounter==0) {
 299                 zspan->curpstr= addpsmainA(zspan->apsmbase);
 300                 zspan->apsmcounter= 4095;
 301         }
 302         else {
 303                 zspan->curpstr++;
 304                 zspan->apsmcounter--;
 305         }
 306         return zspan->curpstr;
 307 }
 308
 309 static void zbuffillAc4(ZSpan *zspan, int obi, int zvlnr,
 310                         const float *v1, const float *v2, const float *v3, const float *v4)
 311 {
 312         APixstr *ap, *apofs, *apn;
 313         double zxd, zyd, zy0, zverg;
 314         float x0, y0, z0;
 315         float x1, y1, z1, x2, y2, z2, xx1;
 316         float *span1, *span2;
 317         int *rz, *rm, x, y;
 318         int sn1, sn2, rectx, *rectzofs, *rectmaskofs, my0, my2, mask;
 319
 320         /* init */
 321         zbuf_init_span(zspan);
 322
 323         /* set spans */
 324         zbuf_add_to_span(zspan, v1, v2);
 325         zbuf_add_to_span(zspan, v2, v3);
 326         if (v4) {
 327                 zbuf_add_to_span(zspan, v3, v4);
 328                 zbuf_add_to_span(zspan, v4, v1);
 329         }
 330         else
 331                 zbuf_add_to_span(zspan, v3, v1);
 332
 333         /* clipped */
 334         if (zspan->minp2==NULL || zspan->maxp2==NULL) return;
 335
 336         if (zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
 337         if (zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
 338
 339         if (my2<my0) return;
 340
 341         /* ZBUF DX DY, in floats still */
 342         x1= v1[0]- v2[0];
 343         x2= v2[0]- v3[0];
 344         y1= v1[1]- v2[1];
 345         y2= v2[1]- v3[1];
 346         z1= v1[2]- v2[2];
 347         z2= v2[2]- v3[2];
 348         x0= y1*z2-z1*y2;
 349         y0= z1*x2-x1*z2;
 350         z0= x1*y2-y1*x2;
 351
 352         if (z0==0.0f) return;
 353
 354         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
 355
 356         zxd= -(double)x0/(double)z0;
 357         zyd= -(double)y0/(double)z0;
 358         zy0= ((double)my2)*zyd + (double)xx1;
 359
 360         /* start-offset in rect */
 361         rectx= zspan->rectx;
 362         rectzofs= (int *)(zspan->arectz+rectx*(my2));
 363         rectmaskofs= (int *)(zspan->rectmask+rectx*(my2));
 364         apofs= (zspan->apixbuf+ rectx*(my2));
 365         mask= zspan->mask;
 366
 367         /* correct span */
 368         sn1= (my0 + my2)/2;
 369         if (zspan->span1[sn1] < zspan->span2[sn1]) {
 370                 span1= zspan->span1+my2;
 371                 span2= zspan->span2+my2;
 372         }
 373         else {
 374                 span1= zspan->span2+my2;
 375                 span2= zspan->span1+my2;
 376         }
 377
 378         for (y=my2; y>=my0; y--, span1--, span2--) {
 379
 380                 sn1= floor(*span1);
 381                 sn2= floor(*span2);
 382                 sn1++;
 383
 384                 if (sn2>=rectx) sn2= rectx-1;
 385                 if (sn1<0) sn1= 0;
 386
 387                 if (sn2>=sn1) {
 388                         int intzverg;
 389
 390                         zverg= (double)sn1*zxd + zy0;
 391                         rz= rectzofs+sn1;
 392                         rm= rectmaskofs+sn1;
 393                         ap= apofs+sn1;
 394                         x= sn2-sn1;
 395
 396                         zverg-= zspan->polygon_offset;
 397
 398                         while (x>=0) {
 399                                 intzverg= (int)CLAMPIS(zverg, INT_MIN, INT_MAX);
 400
 401                                 if ( intzverg < *rz) {
 402                                         if (!zspan->rectmask || intzverg > *rm) {
 403
 404                                                 apn= ap;
 405                                                 while (apn) {
 406                                                         if (apn->p[0]==0) {apn->obi[0]= obi; apn->p[0]= zvlnr; apn->z[0]= intzverg; apn->mask[0]= mask; break; }
 407                                                         if (apn->p[0]==zvlnr && apn->obi[0]==obi) {apn->mask[0]|= mask; break; }
 408                                                         if (apn->p[1]==0) {apn->obi[1]= obi; apn->p[1]= zvlnr; apn->z[1]= intzverg; apn->mask[1]= mask; break; }
 409                                                         if (apn->p[1]==zvlnr && apn->obi[1]==obi) {apn->mask[1]|= mask; break; }
 410                                                         if (apn->p[2]==0) {apn->obi[2]= obi; apn->p[2]= zvlnr; apn->z[2]= intzverg; apn->mask[2]= mask; break; }
 411                                                         if (apn->p[2]==zvlnr && apn->obi[2]==obi) {apn->mask[2]|= mask; break; }
 412                                                         if (apn->p[3]==0) {apn->obi[3]= obi; apn->p[3]= zvlnr; apn->z[3]= intzverg; apn->mask[3]= mask; break; }
 413                                                         if (apn->p[3]==zvlnr && apn->obi[3]==obi) {apn->mask[3]|= mask; break; }
 414                                                         if (apn->next==NULL) apn->next= addpsA(zspan);
 415                                                         apn= apn->next;
 416                                                 }
 417                                         }
 418                                 }
 419                                 zverg+= zxd;
 420                                 rz++;
 421                                 rm++;
 422                                 ap++;
 423                                 x--;
 424                         }
 425                 }
 426
 427                 zy0-=zyd;
 428                 rectzofs-= rectx;
 429                 rectmaskofs-= rectx;
 430                 apofs-= rectx;
 431         }
 432 }
 433
 434
 435
 436 static void zbuflineAc(ZSpan *zspan, int obi, int zvlnr, const float vec1[3], const float vec2[3])
 437 {
 438         APixstr *ap, *apn;
 439         int *rectz, *rectmask;
 440         int start, end, x, y, oldx, oldy, ofs;
 441         int dz, vergz, mask, maxtest=0;
 442         float dx, dy;
 443         float v1[3], v2[3];
 444
 445         dx= vec2[0]-vec1[0];
 446         dy= vec2[1]-vec1[1];
 447
 448         mask= zspan->mask;
 449
 450         if (fabsf(dx) > fabsf(dy)) {
 451
 452                 /* all lines from left to right */
 453                 if (vec1[0]<vec2[0]) {
 454                         copy_v3_v3(v1, vec1);
 455                         copy_v3_v3(v2, vec2);
 456                 }
 457                 else {
 458                         copy_v3_v3(v2, vec1);
 459                         copy_v3_v3(v1, vec2);
 460                         dx= -dx; dy= -dy;
 461                 }
 462
 463                 start= floor(v1[0]);
 464                 end= start+floor(dx);
 465                 if (end>=zspan->rectx) end= zspan->rectx-1;
 466
 467                 oldy= floor(v1[1]);
 468                 dy/= dx;
 469
 470                 vergz= v1[2];
 471                 vergz-= zspan->polygon_offset;
 472                 dz= (v2[2]-v1[2])/dx;
 473                 if (vergz>0x50000000 && dz>0) maxtest= 1;  /* prevent overflow */
 474
 475                 rectz= (int *)(zspan->arectz+zspan->rectx*(oldy) +start);
 476                 rectmask= (int *)(zspan->rectmask+zspan->rectx*(oldy) +start);
 477                 ap= (zspan->apixbuf+ zspan->rectx*(oldy) +start);
 478
 479                 if (dy<0) ofs= -zspan->rectx;
 480                 else ofs= zspan->rectx;
 481
 482                 for (x= start; x<=end; x++, rectz++, rectmask++, ap++) {
 483
 484                         y= floor(v1[1]);
 485                         if (y!=oldy) {
 486                                 oldy= y;
 487                                 rectz+= ofs;
 488                                 rectmask+= ofs;
 489                                 ap+= ofs;
 490                         }
 491
 492                         if (x>=0 && y>=0 && y<zspan->recty) {
 493                                 if (vergz<*rectz) {
 494                                         if (!zspan->rectmask || vergz>*rectmask) {
 495
 496                                                 apn= ap;
 497                                                 while (apn) {   /* loop unrolled */
 498                                                         if (apn->p[0]==0) {apn->obi[0]= obi; apn->p[0]= zvlnr; apn->z[0]= vergz; apn->mask[0]= mask; break; }
 499                                                         if (apn->p[0]==zvlnr && apn->obi[0]==obi) {apn->mask[0]|= mask; break; }
 500                                                         if (apn->p[1]==0) {apn->obi[1]= obi; apn->p[1]= zvlnr; apn->z[1]= vergz; apn->mask[1]= mask; break; }
 501                                                         if (apn->p[1]==zvlnr && apn->obi[1]==obi) {apn->mask[1]|= mask; break; }
 502                                                         if (apn->p[2]==0) {apn->obi[2]= obi; apn->p[2]= zvlnr; apn->z[2]= vergz; apn->mask[2]= mask; break; }
 503                                                         if (apn->p[2]==zvlnr && apn->obi[2]==obi) {apn->mask[2]|= mask; break; }
 504                                                         if (apn->p[3]==0) {apn->obi[3]= obi; apn->p[3]= zvlnr; apn->z[3]= vergz; apn->mask[3]= mask; break; }
 505                                                         if (apn->p[3]==zvlnr && apn->obi[3]==obi) {apn->mask[3]|= mask; break; }
 506                                                         if (apn->next == NULL) apn->next = addpsA(zspan);
 507                                                         apn= apn->next;
 508                                                 }
 509                                         }
 510                                 }
 511                         }
 512
 513                         v1[1]+= dy;
 514                         if (maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 515                         else vergz+= dz;
 516                 }
 517         }
 518         else {
 519
 520                 /* all lines from top to bottom */
 521                 if (vec1[1]<vec2[1]) {
 522                         copy_v3_v3(v1, vec1);
 523                         copy_v3_v3(v2, vec2);
 524                 }
 525                 else {
 526                         copy_v3_v3(v2, vec1);
 527                         copy_v3_v3(v1, vec2);
 528                         dx= -dx; dy= -dy;
 529                 }
 530
 531                 start= floor(v1[1]);
 532                 end= start+floor(dy);
 533
 534                 if (start>=zspan->recty || end<0) return;
 535
 536                 if (end>=zspan->recty) end= zspan->recty-1;
 537
 538                 oldx= floor(v1[0]);
 539                 dx/= dy;
 540
 541                 vergz= v1[2];
 542                 vergz-= zspan->polygon_offset;
 543                 dz= (v2[2]-v1[2])/dy;
 544                 if (vergz>0x50000000 && dz>0) maxtest= 1;  /* prevent overflow */
 545
 546                 rectz= (int *)( zspan->arectz+ (start)*zspan->rectx+ oldx );
 547                 rectmask= (int *)( zspan->rectmask+ (start)*zspan->rectx+ oldx );
 548                 ap= (zspan->apixbuf+ zspan->rectx*(start) +oldx);
 549
 550                 if (dx<0) ofs= -1;
 551                 else ofs= 1;
 552
 553                 for (y= start; y<=end; y++, rectz+=zspan->rectx, rectmask+=zspan->rectx, ap+=zspan->rectx) {
 554
 555                         x= floor(v1[0]);
 556                         if (x!=oldx) {
 557                                 oldx= x;
 558                                 rectz+= ofs;
 559                                 rectmask+= ofs;
 560                                 ap+= ofs;
 561                         }
 562
 563                         if (x>=0 && y>=0 && x<zspan->rectx) {
 564                                 if (vergz<*rectz) {
 565                                         if (!zspan->rectmask || vergz>*rectmask) {
 566
 567                                                 apn= ap;
 568                                                 while (apn) {   /* loop unrolled */
 569                                                         if (apn->p[0]==0) {apn->obi[0]= obi; apn->p[0]= zvlnr; apn->z[0]= vergz; apn->mask[0]= mask; break; }
 570                                                         if (apn->p[0]==zvlnr) {apn->mask[0]|= mask; break; }
 571                                                         if (apn->p[1]==0) {apn->obi[1]= obi; apn->p[1]= zvlnr; apn->z[1]= vergz; apn->mask[1]= mask; break; }
 572                                                         if (apn->p[1]==zvlnr) {apn->mask[1]|= mask; break; }
 573                                                         if (apn->p[2]==0) {apn->obi[2]= obi; apn->p[2]= zvlnr; apn->z[2]= vergz; apn->mask[2]= mask; break; }
 574                                                         if (apn->p[2]==zvlnr) {apn->mask[2]|= mask; break; }
 575                                                         if (apn->p[3]==0) {apn->obi[3]= obi; apn->p[3]= zvlnr; apn->z[3]= vergz; apn->mask[3]= mask; break; }
 576                                                         if (apn->p[3]==zvlnr) {apn->mask[3]|= mask; break; }
 577                                                         if (apn->next == NULL) apn->next = addpsA(zspan);
 578                                                         apn= apn->next;
 579                                                 }
 580                                         }
 581                                 }
 582                         }
 583
 584                         v1[0]+= dx;
 585                         if (maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 586                         else vergz+= dz;
 587                 }
 588         }
 589 }
 590
 591 /* *************  NORMAL ZBUFFER ************ */
 592
 593 static void zbufline(ZSpan *zspan, int obi, int zvlnr, const float vec1[3], const float vec2[3])
 594 {
 595         int *rectz, *rectp, *recto, *rectmask;
 596         int start, end, x, y, oldx, oldy, ofs;
 597         int dz, vergz, maxtest= 0;
 598         float dx, dy;
 599         float v1[3], v2[3];
 600
 601         dx= vec2[0]-vec1[0];
 602         dy= vec2[1]-vec1[1];
 603
 604         if (fabsf(dx) > fabsf(dy)) {
 605
 606                 /* all lines from left to right */
 607                 if (vec1[0]<vec2[0]) {
 608                         copy_v3_v3(v1, vec1);
 609                         copy_v3_v3(v2, vec2);
 610                 }
 611                 else {
 612                         copy_v3_v3(v2, vec1);
 613                         copy_v3_v3(v1, vec2);
 614                         dx= -dx; dy= -dy;
 615                 }
 616
 617                 start= floor(v1[0]);
 618                 end= start+floor(dx);
 619                 if (end>=zspan->rectx) end= zspan->rectx-1;
 620
 621                 oldy= floor(v1[1]);
 622                 dy/= dx;
 623
 624                 vergz= floor(v1[2]);
 625                 dz= floor((v2[2]-v1[2])/dx);
 626                 if (vergz>0x50000000 && dz>0) maxtest= 1;  /* prevent overflow */
 627
 628                 rectz= zspan->rectz + oldy*zspan->rectx+ start;
 629                 rectp= zspan->rectp + oldy*zspan->rectx+ start;
 630                 recto= zspan->recto + oldy*zspan->rectx+ start;
 631                 rectmask= zspan->rectmask + oldy*zspan->rectx+ start;
 632
 633                 if (dy<0) ofs= -zspan->rectx;
 634                 else ofs= zspan->rectx;
 635
 636                 for (x= start; x<=end; x++, rectz++, rectp++, recto++, rectmask++) {
 637
 638                         y= floor(v1[1]);
 639                         if (y!=oldy) {
 640                                 oldy= y;
 641                                 rectz+= ofs;
 642                                 rectp+= ofs;
 643                                 recto+= ofs;
 644                                 rectmask+= ofs;
 645                         }
 646
 647                         if (x>=0 && y>=0 && y<zspan->recty) {
 648                                 if (vergz<*rectz) {
 649                                         if (!zspan->rectmask || vergz>*rectmask) {
 650                                                 *recto= obi;
 651                                                 *rectz= vergz;
 652                                                 *rectp= zvlnr;
 653                                         }
 654                                 }
 655                         }
 656
 657                         v1[1]+= dy;
 658
 659                         if (maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 660                         else vergz+= dz;
 661                 }
 662         }
 663         else {
 664                 /* all lines from top to bottom */
 665                 if (vec1[1]<vec2[1]) {
 666                         copy_v3_v3(v1, vec1);
 667                         copy_v3_v3(v2, vec2);
 668                 }
 669                 else {
 670                         copy_v3_v3(v2, vec1);
 671                         copy_v3_v3(v1, vec2);
 672                         dx= -dx; dy= -dy;
 673                 }
 674
 675                 start= floor(v1[1]);
 676                 end= start+floor(dy);
 677
 678                 if (end>=zspan->recty) end= zspan->recty-1;
 679
 680                 oldx= floor(v1[0]);
 681                 dx/= dy;
 682
 683                 vergz= floor(v1[2]);
 684                 dz= floor((v2[2]-v1[2])/dy);
 685                 if (vergz>0x50000000 && dz>0) maxtest= 1;  /* prevent overflow */
 686
 687                 rectz= zspan->rectz + start*zspan->rectx+ oldx;
 688                 rectp= zspan->rectp + start*zspan->rectx+ oldx;
 689                 recto= zspan->recto + start*zspan->rectx+ oldx;
 690                 rectmask= zspan->rectmask + start*zspan->rectx+ oldx;
 691
 692                 if (dx<0) ofs= -1;
 693                 else ofs= 1;
 694
 695                 for (y= start; y<=end; y++, rectz+=zspan->rectx, rectp+=zspan->rectx, recto+=zspan->rectx, rectmask+=zspan->rectx) {
 696
 697                         x= floor(v1[0]);
 698                         if (x!=oldx) {
 699                                 oldx= x;
 700                                 rectz+= ofs;
 701                                 rectp+= ofs;
 702                                 recto+= ofs;
 703                                 rectmask+= ofs;
 704                         }
 705
 706                         if (x>=0 && y>=0 && x<zspan->rectx) {
 707                                 if (vergz<*rectz) {
 708                                         if (!zspan->rectmask || vergz>*rectmask) {
 709                                                 *rectz= vergz;
 710                                                 *rectp= zvlnr;
 711                                                 *recto= obi;
 712                                         }
 713                                 }
 714                         }
 715
 716                         v1[0]+= dx;
 717                         if (maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 718                         else vergz+= dz;
 719                 }
 720         }
 721 }
 722
 723 static void zbufline_onlyZ(ZSpan *zspan, int UNUSED(obi), int UNUSED(zvlnr), const float vec1[3], const float vec2[3])
 724 {
 725         int *rectz, *rectz1= NULL;
 726         int start, end, x, y, oldx, oldy, ofs;
 727         int dz, vergz, maxtest= 0;
 728         float dx, dy;
 729         float v1[3], v2[3];
 730
 731         dx= vec2[0]-vec1[0];
 732         dy= vec2[1]-vec1[1];
 733
 734         if (fabsf(dx) > fabsf(dy)) {
 735
 736                 /* all lines from left to right */
 737                 if (vec1[0]<vec2[0]) {
 738                         copy_v3_v3(v1, vec1);
 739                         copy_v3_v3(v2, vec2);
 740                 }
 741                 else {
 742                         copy_v3_v3(v2, vec1);
 743                         copy_v3_v3(v1, vec2);
 744                         dx= -dx; dy= -dy;
 745                 }
 746
 747                 start= floor(v1[0]);
 748                 end= start+floor(dx);
 749                 if (end>=zspan->rectx) end= zspan->rectx-1;
 750
 751                 oldy= floor(v1[1]);
 752                 dy/= dx;
 753
 754                 vergz= floor(v1[2]);
 755                 dz= floor((v2[2]-v1[2])/dx);
 756                 if (vergz>0x50000000 && dz>0) maxtest= 1;  /* prevent overflow */
 757
 758                 rectz= zspan->rectz + oldy*zspan->rectx+ start;
 759                 if (zspan->rectz1)
 760                         rectz1= zspan->rectz1 + oldy*zspan->rectx+ start;
 761
 762                 if (dy<0) ofs= -zspan->rectx;
 763                 else ofs= zspan->rectx;
 764
 765                 for (x= start; x<=end; x++, rectz++) {
 766
 767                         y= floor(v1[1]);
 768                         if (y!=oldy) {
 769                                 oldy= y;
 770                                 rectz+= ofs;
 771                                 if (rectz1) rectz1+= ofs;
 772                         }
 773
 774                         if (x>=0 && y>=0 && y<zspan->recty) {
 775                                 if (vergz < *rectz) {
 776                                         if (rectz1) *rectz1= *rectz;
 777                                         *rectz= vergz;
 778                                 }
 779                                 else if (rectz1 && vergz < *rectz1)
 780                                         *rectz1= vergz;
 781                         }
 782
 783                         v1[1]+= dy;
 784
 785                         if (maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 786                         else vergz+= dz;
 787
 788                         if (rectz1) rectz1++;
 789                 }
 790         }
 791         else {
 792                 /* all lines from top to bottom */
 793                 if (vec1[1]<vec2[1]) {
 794                         copy_v3_v3(v1, vec1);
 795                         copy_v3_v3(v2, vec2);
 796                 }
 797                 else {
 798                         copy_v3_v3(v2, vec1);
 799                         copy_v3_v3(v1, vec2);
 800                         dx= -dx; dy= -dy;
 801                 }
 802
 803                 start= floor(v1[1]);
 804                 end= start+floor(dy);
 805
 806                 if (end>=zspan->recty) end= zspan->recty-1;
 807
 808                 oldx= floor(v1[0]);
 809                 dx/= dy;
 810
 811                 vergz= floor(v1[2]);
 812                 dz= floor((v2[2]-v1[2])/dy);
 813                 if (vergz>0x50000000 && dz>0) maxtest= 1;  /* prevent overflow */
 814
 815                 rectz= zspan->rectz + start*zspan->rectx+ oldx;
 816                 if (zspan->rectz1)
 817                         rectz1= zspan->rectz1 + start*zspan->rectx+ oldx;
 818
 819                 if (dx<0) ofs= -1;
 820                 else ofs= 1;
 821
 822                 for (y= start; y<=end; y++, rectz+=zspan->rectx) {
 823
 824                         x= floor(v1[0]);
 825                         if (x!=oldx) {
 826                                 oldx= x;
 827                                 rectz+= ofs;
 828                                 if (rectz1) rectz1+= ofs;
 829                         }
 830
 831                         if (x>=0 && y>=0 && x<zspan->rectx) {
 832                                 if (vergz < *rectz) {
 833                                         if (rectz1) *rectz1= *rectz;
 834                                         *rectz= vergz;
 835                                 }
 836                                 else if (rectz1 && vergz < *rectz1)
 837                                         *rectz1= vergz;
 838                         }
 839
 840                         v1[0]+= dx;
 841                         if (maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 842                         else vergz+= dz;
 843
 844                         if (rectz1)
 845                                 rectz1+=zspan->rectx;
 846                 }
 847         }
 848 }
 849
 850
 851 static int clipline(float v1[4], float v2[4])   /* return 0: do not draw */
 852 {
 853         float dz, dw, u1=0.0, u2=1.0;
 854         float dx, dy, v13;
 855
 856         dz= v2[2]-v1[2];
 857         dw= v2[3]-v1[3];
 858
 859         /* this 1.01 is for clipping x and y just a tinsy larger. that way it is
 860          * filled in with zbufwire correctly when rendering in parts. otherwise
 861          * you see line endings at edges... */
 862
 863         if (cliptestf(-dz, -dw, v1[3], v1[2], &u1, &u2)) {
 864                 if (cliptestf(dz, -dw, v1[3], -v1[2], &u1, &u2)) {
 865
 866                         dx= v2[0]-v1[0];
 867                         dz= 1.01f*(v2[3]-v1[3]);
 868                         v13= 1.01f*v1[3];
 869
 870                         if (cliptestf(-dx, -dz, v1[0], v13, &u1, &u2)) {
 871                                 if (cliptestf(dx, -dz, v13, -v1[0], &u1, &u2)) {
 872
 873                                         dy= v2[1]-v1[1];
 874
 875                                         if (cliptestf(-dy, -dz, v1[1], v13, &u1, &u2)) {
 876                                                 if (cliptestf(dy, -dz, v13, -v1[1], &u1, &u2)) {
 877
 878                                                         if (u2<1.0f) {
 879                                                                 v2[0]= v1[0]+u2*dx;
 880                                                                 v2[1]= v1[1]+u2*dy;
 881                                                                 v2[2]= v1[2]+u2*dz;
 882                                                                 v2[3]= v1[3]+u2*dw;
 883                                                         }
 884                                                         if (u1>0.0f) {
 885                                                                 v1[0]= v1[0]+u1*dx;
 886                                                                 v1[1]= v1[1]+u1*dy;
 887                                                                 v1[2]= v1[2]+u1*dz;
 888                                                                 v1[3]= v1[3]+u1*dw;
 889                                                         }
 890                                                         return 1;
 891                                                 }
 892                                         }
 893                                 }
 894                         }
 895                 }
 896         }
 897
 898         return 0;
 899 }
 900
 901 void hoco_to_zco(ZSpan *zspan, float zco[3], const float hoco[4])
 902 {
 903         float div;
 904
 905         div= 1.0f/hoco[3];
 906         zco[0]= zspan->zmulx*(1.0f+hoco[0]*div) + zspan->zofsx;
 907         zco[1]= zspan->zmuly*(1.0f+hoco[1]*div) + zspan->zofsy;
 908         zco[2]= 0x7FFFFFFF *(hoco[2]*div);
 909 }
 910
 911 void zbufclipwire(ZSpan *zspan, int obi, int zvlnr, int ec,
 912                   const float ho1[4], const float ho2[4], const float ho3[4], const float ho4[4],
 913                   const int c1, const int c2, const int c3, const int c4)
 914 {
 915         float vez[20];
 916         int and, or;
 917
 918         /* edgecode: 1= draw */
 919         if (ec==0) return;
 920
 921         if (ho4) {
 922                 and= (c1 & c2 & c3 & c4);
 923                 or= (c1 | c2 | c3 | c4);
 924         }
 925         else {
 926                 and= (c1 & c2 & c3);
 927                 or= (c1 | c2 | c3);
 928         }
 929
 930         if (or) {       /* not in the middle */
 931                 if (and) {      /* out completely */
 932                         return;
 933                 }
 934                 else {  /* clipping */
 935
 936                         if (ec & ME_V1V2) {
 937                                 copy_v4_v4(vez, ho1);
 938                                 copy_v4_v4(vez+4, ho2);
 939                                 if ( clipline(vez, vez+4)) {
 940                                         hoco_to_zco(zspan, vez, vez);
 941                                         hoco_to_zco(zspan, vez+4, vez+4);
 942                                         zspan->zbuflinefunc(zspan, obi, zvlnr, vez, vez+4);
 943                                 }
 944                         }
 945                         if (ec & ME_V2V3) {
 946                                 copy_v4_v4(vez, ho2);
 947                                 copy_v4_v4(vez+4, ho3);
 948                                 if ( clipline(vez, vez+4)) {
 949                                         hoco_to_zco(zspan, vez, vez);
 950                                         hoco_to_zco(zspan, vez+4, vez+4);
 951                                         zspan->zbuflinefunc(zspan, obi, zvlnr, vez, vez+4);
 952                                 }
 953                         }
 954                         if (ho4) {
 955                                 if (ec & ME_V3V4) {
 956                                         copy_v4_v4(vez, ho3);
 957                                         copy_v4_v4(vez+4, ho4);
 958                                         if ( clipline(vez, vez+4)) {
 959                                                 hoco_to_zco(zspan, vez, vez);
 960                                                 hoco_to_zco(zspan, vez+4, vez+4);
 961                                                 zspan->zbuflinefunc(zspan, obi, zvlnr, vez, vez+4);
 962                                         }
 963                                 }
 964                                 if (ec & ME_V4V1) {
 965                                         copy_v4_v4(vez, ho4);
 966                                         copy_v4_v4(vez+4, ho1);
 967                                         if ( clipline(vez, vez+4)) {
 968                                                 hoco_to_zco(zspan, vez, vez);
 969                                                 hoco_to_zco(zspan, vez+4, vez+4);
 970                                                 zspan->zbuflinefunc(zspan, obi, zvlnr, vez, vez+4);
 971                                         }
 972                                 }
 973                         }
 974                         else {
 975                                 if (ec & ME_V3V1) {
 976                                         copy_v4_v4(vez, ho3);
 977                                         copy_v4_v4(vez+4, ho1);
 978                                         if ( clipline(vez, vez+4)) {
 979                                                 hoco_to_zco(zspan, vez, vez);
 980                                                 hoco_to_zco(zspan, vez+4, vez+4);
 981                                                 zspan->zbuflinefunc(zspan, obi, zvlnr, vez, vez+4);
 982                                         }
 983                                 }
 984                         }
 985
 986                         return;
 987                 }
 988         }
 989
 990         hoco_to_zco(zspan, vez, ho1);
 991         hoco_to_zco(zspan, vez+4, ho2);
 992         hoco_to_zco(zspan, vez+8, ho3);
 993         if (ho4) {
 994                 hoco_to_zco(zspan, vez+12, ho4);
 995
 996                 if (ec & ME_V3V4)  zspan->zbuflinefunc(zspan, obi, zvlnr, vez+8, vez+12);
 997                 if (ec & ME_V4V1)  zspan->zbuflinefunc(zspan, obi, zvlnr, vez+12, vez);
 998         }
 999         else {
1000                 if (ec & ME_V3V1)  zspan->zbuflinefunc(zspan, obi, zvlnr, vez+8, vez);
1001         }
1002
1003         if (ec & ME_V1V2)  zspan->zbuflinefunc(zspan, obi, zvlnr, vez, vez+4);
1004         if (ec & ME_V2V3)  zspan->zbuflinefunc(zspan, obi, zvlnr, vez+4, vez+8);
1005
1006 }
1007
1008 void zbufsinglewire(ZSpan *zspan, int obi, int zvlnr, const float ho1[4], const float ho2[4])
1009 {
1010         float f1[4], f2[4];
1011         int c1, c2;
1012
1013         c1= testclip(ho1);
1014         c2= testclip(ho2);
1015
1016         if (c1 | c2) {  /* not in the middle */
1017                 if (!(c1 & c2)) {       /* not out completely */
1018                         copy_v4_v4(f1, ho1);
1019                         copy_v4_v4(f2, ho2);
1020
1021                         if (clipline(f1, f2)) {
1022                                 hoco_to_zco(zspan, f1, f1);
1023                                 hoco_to_zco(zspan, f2, f2);
1024                                 zspan->zbuflinefunc(zspan, obi, zvlnr, f1, f2);
1025                         }
1026                 }
1027         }
1028         else {
1029                 hoco_to_zco(zspan, f1, ho1);
1030                 hoco_to_zco(zspan, f2, ho2);
1031
1032                 zspan->zbuflinefunc(zspan, obi, zvlnr, f1, f2);
1033         }
1034 }
1035
1036 /**
1037  * Fill the z buffer, but invert z order, and add the face index to
1038  * the corresponding face buffer.
1039  *
1040  * This is one of the z buffer fill functions called in zbufclip() and
1041  * zbufwireclip().
1042  *
1043  * \param v1 [4 floats, world coordinates] first vertex
1044  * \param v2 [4 floats, world coordinates] second vertex
1045  * \param v3 [4 floats, world coordinates] third vertex
1046  */
1047
1048 /* WATCH IT: zbuffillGLinv4 and zbuffillGL4 are identical except for a 2 lines,
1049  * commented below */
1050 static void zbuffillGLinv4(ZSpan *zspan, int obi, int zvlnr,
1051                            const float *v1, const float *v2, const float *v3, const float *v4)
1052 {
1053         double zxd, zyd, zy0, zverg;
1054         float x0, y0, z0;
1055         float x1, y1, z1, x2, y2, z2, xx1;
1056         float *span1, *span2;
1057         int *rectoofs, *ro;
1058         int *rectpofs, *rp;
1059         int *rectmaskofs, *rm;
1060         int *rz, x, y;
1061         int sn1, sn2, rectx, *rectzofs, my0, my2;
1062
1063         /* init */
1064         zbuf_init_span(zspan);
1065
1066         /* set spans */
1067         zbuf_add_to_span(zspan, v1, v2);
1068         zbuf_add_to_span(zspan, v2, v3);
1069         if (v4) {
1070                 zbuf_add_to_span(zspan, v3, v4);
1071                 zbuf_add_to_span(zspan, v4, v1);
1072         }
1073         else
1074                 zbuf_add_to_span(zspan, v3, v1);
1075
1076         /* clipped */
1077         if (zspan->minp2==NULL || zspan->maxp2==NULL) return;
1078
1079         if (zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
1080         if (zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
1081
1082         //      printf("my %d %d\n", my0, my2);
1083         if (my2<my0) return;
1084
1085
1086         /* ZBUF DX DY, in floats still */
1087         x1= v1[0]- v2[0];
1088         x2= v2[0]- v3[0];
1089         y1= v1[1]- v2[1];
1090         y2= v2[1]- v3[1];
1091         z1= v1[2]- v2[2];
1092         z2= v2[2]- v3[2];
1093         x0= y1*z2-z1*y2;
1094         y0= z1*x2-x1*z2;
1095         z0= x1*y2-y1*x2;
1096
1097         if (z0==0.0f) return;
1098
1099         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
1100
1101         zxd= -(double)x0/(double)z0;
1102         zyd= -(double)y0/(double)z0;
1103         zy0= ((double)my2)*zyd + (double)xx1;
1104
1105         /* start-offset in rect */
1106         rectx= zspan->rectx;
1107         rectzofs= (zspan->rectz+rectx*my2);
1108         rectpofs= (zspan->rectp+rectx*my2);
1109         rectoofs= (zspan->recto+rectx*my2);
1110         rectmaskofs= (zspan->rectmask+rectx*my2);
1111
1112         /* correct span */
1113         sn1= (my0 + my2)/2;
1114         if (zspan->span1[sn1] < zspan->span2[sn1]) {
1115                 span1= zspan->span1+my2;
1116                 span2= zspan->span2+my2;
1117         }
1118         else {
1119                 span1= zspan->span2+my2;
1120                 span2= zspan->span1+my2;
1121         }
1122
1123         for (y=my2; y>=my0; y--, span1--, span2--) {
1124
1125                 sn1= floor(*span1);
1126                 sn2= floor(*span2);
1127                 sn1++;
1128
1129                 if (sn2>=rectx) sn2= rectx-1;
1130                 if (sn1<0) sn1= 0;
1131
1132                 if (sn2>=sn1) {
1133                         int intzverg;
1134
1135                         zverg= (double)sn1*zxd + zy0;
1136                         rz= rectzofs+sn1;
1137                         rp= rectpofs+sn1;
1138                         ro= rectoofs+sn1;
1139                         rm= rectmaskofs+sn1;
1140                         x= sn2-sn1;
1141
1142                         while (x>=0) {
1143                                 intzverg= (int)CLAMPIS(zverg, INT_MIN, INT_MAX);
1144
1145                                 if ( intzverg > *rz || *rz==0x7FFFFFFF) { /* UNIQUE LINE: see comment above */
1146                                         if (!zspan->rectmask || intzverg > *rm) {
1147                                                 *ro= obi; /* UNIQUE LINE: see comment above (order differs) */
1148                                                 *rz= intzverg;
1149                                                 *rp= zvlnr;
1150                                         }
1151                                 }
1152                                 zverg+= zxd;
1153                                 rz++;
1154                                 rp++;
1155                                 ro++;
1156                                 rm++;
1157                                 x--;
1158                         }
1159                 }
1160
1161                 zy0-=zyd;
1162                 rectzofs-= rectx;
1163                 rectpofs-= rectx;
1164                 rectoofs-= rectx;
1165                 rectmaskofs-= rectx;
1166         }
1167 }
1168
1169 /* uses spanbuffers */
1170
1171 /* WATCH IT: zbuffillGLinv4 and zbuffillGL4 are identical except for a 2 lines,
1172  * commented below */
1173 static void zbuffillGL4(ZSpan *zspan, int obi, int zvlnr,
1174                         const float *v1, const float *v2, const float *v3, const float *v4)
1175 {
1176         double zxd, zyd, zy0, zverg;
1177         float x0, y0, z0;
1178         float x1, y1, z1, x2, y2, z2, xx1;
1179         float *span1, *span2;
1180         int *rectoofs, *ro;
1181         int *rectpofs, *rp;
1182         int *rectmaskofs, *rm;
1183         int *rz, x, y;
1184         int sn1, sn2, rectx, *rectzofs, my0, my2;
1185
1186         /* init */
1187         zbuf_init_span(zspan);
1188
1189         /* set spans */
1190         zbuf_add_to_span(zspan, v1, v2);
1191         zbuf_add_to_span(zspan, v2, v3);
1192         if (v4) {
1193                 zbuf_add_to_span(zspan, v3, v4);
1194                 zbuf_add_to_span(zspan, v4, v1);
1195         }
1196         else
1197                 zbuf_add_to_span(zspan, v3, v1);
1198
1199         /* clipped */
1200         if (zspan->minp2==NULL || zspan->maxp2==NULL) return;
1201
1202         if (zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
1203         if (zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
1204
1205         //      printf("my %d %d\n", my0, my2);
1206         if (my2<my0) return;
1207
1208
1209         /* ZBUF DX DY, in floats still */
1210         x1= v1[0]- v2[0];
1211         x2= v2[0]- v3[0];
1212         y1= v1[1]- v2[1];
1213         y2= v2[1]- v3[1];
1214         z1= v1[2]- v2[2];
1215         z2= v2[2]- v3[2];
1216         x0= y1*z2-z1*y2;
1217         y0= z1*x2-x1*z2;
1218         z0= x1*y2-y1*x2;
1219
1220         if (z0==0.0f) return;
1221
1222         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
1223
1224         zxd= -(double)x0/(double)z0;
1225         zyd= -(double)y0/(double)z0;
1226         zy0= ((double)my2)*zyd + (double)xx1;
1227
1228         /* start-offset in rect */
1229         rectx= zspan->rectx;
1230         rectzofs= (zspan->rectz+rectx*my2);
1231         rectpofs= (zspan->rectp+rectx*my2);
1232         rectoofs= (zspan->recto+rectx*my2);
1233         rectmaskofs= (zspan->rectmask+rectx*my2);
1234
1235         /* correct span */
1236         sn1= (my0 + my2)/2;
1237         if (zspan->span1[sn1] < zspan->span2[sn1]) {
1238                 span1= zspan->span1+my2;
1239                 span2= zspan->span2+my2;
1240         }
1241         else {
1242                 span1= zspan->span2+my2;
1243                 span2= zspan->span1+my2;
1244         }
1245
1246         for (y=my2; y>=my0; y--, span1--, span2--) {
1247
1248                 sn1= floor(*span1);
1249                 sn2= floor(*span2);
1250                 sn1++;
1251
1252                 if (sn2>=rectx) sn2= rectx-1;
1253                 if (sn1<0) sn1= 0;
1254
1255                 if (sn2>=sn1) {
1256                         int intzverg;
1257
1258                         zverg= (double)sn1*zxd + zy0;
1259                         rz= rectzofs+sn1;
1260                         rp= rectpofs+sn1;
1261                         ro= rectoofs+sn1;
1262                         rm= rectmaskofs+sn1;
1263                         x= sn2-sn1;
1264
1265                         while (x>=0) {
1266                                 intzverg= (int)CLAMPIS(zverg, INT_MIN, INT_MAX);
1267
1268                                 if (intzverg < *rz) { /* ONLY UNIQUE LINE: see comment above */
1269                                         if (!zspan->rectmask || intzverg > *rm) {
1270                                                 *rz= intzverg;
1271                                                 *rp= zvlnr;
1272                                                 *ro= obi; /* UNIQUE LINE: see comment above (order differs) */
1273                                         }
1274                                 }
1275                                 zverg+= zxd;
1276                                 rz++;
1277                                 rp++;
1278                                 ro++;
1279                                 rm++;
1280                                 x--;
1281                         }
1282                 }
1283
1284                 zy0-=zyd;
1285                 rectzofs-= rectx;
1286                 rectpofs-= rectx;
1287                 rectoofs-= rectx;
1288                 rectmaskofs-= rectx;
1289         }
1290 }
1291
1292 /**
1293  * Fill the z buffer. The face buffer is not operated on!
1294  *
1295  * This is one of the z buffer fill functions called in zbufclip() and
1296  * zbufwireclip().
1297  *
1298  * \param v1 [4 floats, world coordinates] first vertex
1299  * \param v2 [4 floats, world coordinates] second vertex
1300  * \param v3 [4 floats, world coordinates] third vertex
1301  */
1302
1303 /* now: filling two Z values, the closest and 2nd closest */
1304 static void zbuffillGL_onlyZ(ZSpan *zspan, int UNUSED(obi), int UNUSED(zvlnr),
1305                              const float *v1, const float *v2, const float *v3, const float *v4)
1306 {
1307         double zxd, zyd, zy0, zverg;
1308         float x0, y0, z0;
1309         float x1, y1, z1, x2, y2, z2, xx1;
1310         float *span1, *span2;
1311         int *rz, *rz1, x, y;
1312         int sn1, sn2, rectx, *rectzofs, *rectzofs1= NULL, my0, my2;
1313
1314         /* init */
1315         zbuf_init_span(zspan);
1316
1317         /* set spans */
1318         zbuf_add_to_span(zspan, v1, v2);
1319         zbuf_add_to_span(zspan, v2, v3);
1320         if (v4) {
1321                 zbuf_add_to_span(zspan, v3, v4);
1322                 zbuf_add_to_span(zspan, v4, v1);
1323         }
1324         else
1325                 zbuf_add_to_span(zspan, v3, v1);
1326
1327         /* clipped */
1328         if (zspan->minp2==NULL || zspan->maxp2==NULL) return;
1329
1330         if (zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
1331         if (zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
1332
1333         //      printf("my %d %d\n", my0, my2);
1334         if (my2<my0) return;
1335
1336
1337         /* ZBUF DX DY, in floats still */
1338         x1= v1[0]- v2[0];
1339         x2= v2[0]- v3[0];
1340         y1= v1[1]- v2[1];
1341         y2= v2[1]- v3[1];
1342         z1= v1[2]- v2[2];
1343         z2= v2[2]- v3[2];
1344         x0= y1*z2-z1*y2;
1345         y0= z1*x2-x1*z2;
1346         z0= x1*y2-y1*x2;
1347
1348         if (z0==0.0f) return;
1349
1350         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
1351
1352         zxd= -(double)x0/(double)z0;
1353         zyd= -(double)y0/(double)z0;
1354         zy0= ((double)my2)*zyd + (double)xx1;
1355
1356         /* start-offset in rect */
1357         rectx= zspan->rectx;
1358         rectzofs= (zspan->rectz+rectx*my2);
1359         if (zspan->rectz1)
1360                 rectzofs1= (zspan->rectz1+rectx*my2);
1361
1362         /* correct span */
1363         sn1= (my0 + my2)/2;
1364         if (zspan->span1[sn1] < zspan->span2[sn1]) {
1365                 span1= zspan->span1+my2;
1366                 span2= zspan->span2+my2;
1367         }
1368         else {
1369                 span1= zspan->span2+my2;
1370                 span2= zspan->span1+my2;
1371         }
1372
1373         for (y=my2; y>=my0; y--, span1--, span2--) {
1374
1375                 sn1= floor(*span1);
1376                 sn2= floor(*span2);
1377                 sn1++;
1378
1379                 if (sn2>=rectx) sn2= rectx-1;
1380                 if (sn1<0) sn1= 0;
1381
1382                 if (sn2>=sn1) {
1383                         zverg= (double)sn1*zxd + zy0;
1384                         rz= rectzofs+sn1;
1385                         rz1= rectzofs1+sn1;
1386                         x= sn2-sn1;
1387
1388                         while (x>=0) {
1389                                 int zvergi= (int)CLAMPIS(zverg, INT_MIN, INT_MAX);
1390
1391                                 /* option: maintain two depth values, closest and 2nd closest */
1392                                 if (zvergi < *rz) {
1393                                         if (rectzofs1) *rz1= *rz;
1394                                         *rz= zvergi;
1395                                 }
1396                                 else if (rectzofs1 && zvergi < *rz1)
1397                                         *rz1= zvergi;
1398
1399                                 zverg+= zxd;
1400
1401                                 rz++;
1402                                 rz1++;
1403                                 x--;
1404                         }
1405                 }
1406
1407                 zy0-=zyd;
1408                 rectzofs-= rectx;
1409                 if (rectzofs1) rectzofs1-= rectx;
1410         }
1411 }
1412
1413 /* 2d scanconvert for tria, calls func for each x, y coordinate and gives UV barycentrics */
1414 void zspan_scanconvert_strand(ZSpan *zspan, void *handle, float *v1, float *v2, float *v3, void (*func)(void *, int, int, float, float, float) )
1415 {
1416         float x0, y0, x1, y1, x2, y2, z0, z1, z2, z;
1417         float u, v, uxd, uyd, vxd, vyd, uy0, vy0, zxd, zyd, zy0, xx1;
1418         float *span1, *span2;
1419         int x, y, sn1, sn2, rectx= zspan->rectx, my0, my2;
1420
1421         /* init */
1422         zbuf_init_span(zspan);
1423
1424         /* set spans */
1425         zbuf_add_to_span(zspan, v1, v2);
1426         zbuf_add_to_span(zspan, v2, v3);
1427         zbuf_add_to_span(zspan, v3, v1);
1428
1429         /* clipped */
1430         if (zspan->minp2==NULL || zspan->maxp2==NULL) return;
1431
1432         if (zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
1433         if (zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
1434
1435         //      printf("my %d %d\n", my0, my2);
1436         if (my2<my0) return;
1437
1438         /* ZBUF DX DY, in floats still */
1439         x1= v1[0]- v2[0];
1440         x2= v2[0]- v3[0];
1441         y1= v1[1]- v2[1];
1442         y2= v2[1]- v3[1];
1443         z1= v1[2]- v2[2];
1444         z2= v2[2]- v3[2];
1445
1446         x0= y1*z2-z1*y2;
1447         y0= z1*x2-x1*z2;
1448         z0= x1*y2-y1*x2;
1449
1450         if (z0==0.0f) return;
1451
1452         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
1453         zxd= -(double)x0/(double)z0;
1454         zyd= -(double)y0/(double)z0;
1455         zy0= ((double)my2)*zyd + (double)xx1;
1456
1457         z1= 1.0f; /* (u1 - u2) */
1458         z2= 0.0f; /* (u2 - u3) */
1459
1460         x0= y1*z2-z1*y2;
1461         y0= z1*x2-x1*z2;
1462
1463         xx1= (x0*v1[0] + y0*v1[1])/z0 + 1.0f;
1464         uxd= -(double)x0/(double)z0;
1465         uyd= -(double)y0/(double)z0;
1466         uy0= ((double)my2)*uyd + (double)xx1;
1467
1468         z1= -1.0f; /* (v1 - v2) */
1469         z2= 1.0f;  /* (v2 - v3) */
1470
1471         x0= y1*z2-z1*y2;
1472         y0= z1*x2-x1*z2;
1473
1474         xx1= (x0*v1[0] + y0*v1[1])/z0;
1475         vxd= -(double)x0/(double)z0;
1476         vyd= -(double)y0/(double)z0;
1477         vy0= ((double)my2)*vyd + (double)xx1;
1478
1479         /* correct span */
1480         sn1= (my0 + my2)/2;
1481         if (zspan->span1[sn1] < zspan->span2[sn1]) {
1482                 span1= zspan->span1+my2;
1483                 span2= zspan->span2+my2;
1484         }
1485         else {
1486                 span1= zspan->span2+my2;
1487                 span2= zspan->span1+my2;
1488         }
1489
1490         for (y=my2; y>=my0; y--, span1--, span2--) {
1491
1492                 sn1= floor(*span1);
1493                 sn2= floor(*span2);
1494                 sn1++;
1495
1496                 if (sn2>=rectx) sn2= rectx-1;
1497                 if (sn1<0) sn1= 0;
1498
1499                 u= (double)sn1*uxd + uy0;
1500                 v= (double)sn1*vxd + vy0;
1501                 z= (double)sn1*zxd + zy0;
1502
1503                 for (x= sn1; x<=sn2; x++, u+=uxd, v+=vxd, z+=zxd)
1504                         func(handle, x, y, u, v, z);
1505
1506                 uy0 -= uyd;
1507                 vy0 -= vyd;
1508                 zy0 -= zyd;
1509         }
1510 }
1511
1512 /* scanconvert for strand triangles, calls func for each x, y coordinate and gives UV barycentrics and z */
1513
1514 void zspan_scanconvert(ZSpan *zspan, void *handle, float *v1, float *v2, float *v3, void (*func)(void *, int, int, float, float) )
1515 {
1516         float x0, y0, x1, y1, x2, y2, z0, z1, z2;
1517         float u, v, uxd, uyd, vxd, vyd, uy0, vy0, xx1;
1518         float *span1, *span2;
1519         int x, y, sn1, sn2, rectx= zspan->rectx, my0, my2;
1520
1521         /* init */
1522         zbuf_init_span(zspan);
1523
1524         /* set spans */
1525         zbuf_add_to_span(zspan, v1, v2);
1526         zbuf_add_to_span(zspan, v2, v3);
1527         zbuf_add_to_span(zspan, v3, v1);
1528
1529         /* clipped */
1530         if (zspan->minp2==NULL || zspan->maxp2==NULL) return;
1531
1532         if (zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
1533         if (zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
1534
1535         //      printf("my %d %d\n", my0, my2);
1536         if (my2<my0) return;
1537
1538         /* ZBUF DX DY, in floats still */
1539         x1= v1[0]- v2[0];
1540         x2= v2[0]- v3[0];
1541         y1= v1[1]- v2[1];
1542         y2= v2[1]- v3[1];
1543
1544         z1= 1.0f; /* (u1 - u2) */
1545         z2= 0.0f; /* (u2 - u3) */
1546
1547         x0= y1*z2-z1*y2;
1548         y0= z1*x2-x1*z2;
1549         z0= x1*y2-y1*x2;
1550
1551         if (z0==0.0f) return;
1552
1553         xx1= (x0*v1[0] + y0*v1[1])/z0 + 1.0f;
1554         uxd= -(double)x0/(double)z0;
1555         uyd= -(double)y0/(double)z0;
1556         uy0= ((double)my2)*uyd + (double)xx1;
1557
1558         z1= -1.0f; /* (v1 - v2) */
1559         z2= 1.0f;  /* (v2 - v3) */
1560
1561         x0= y1*z2-z1*y2;
1562         y0= z1*x2-x1*z2;
1563
1564         xx1= (x0*v1[0] + y0*v1[1])/z0;
1565         vxd= -(double)x0/(double)z0;
1566         vyd= -(double)y0/(double)z0;
1567         vy0= ((double)my2)*vyd + (double)xx1;
1568
1569         /* correct span */
1570         sn1= (my0 + my2)/2;
1571         if (zspan->span1[sn1] < zspan->span2[sn1]) {
1572                 span1= zspan->span1+my2;
1573                 span2= zspan->span2+my2;
1574         }
1575         else {
1576                 span1= zspan->span2+my2;
1577                 span2= zspan->span1+my2;
1578         }
1579
1580         for (y=my2; y>=my0; y--, span1--, span2--) {
1581
1582                 sn1= floor(*span1);
1583                 sn2= floor(*span2);
1584                 sn1++;
1585
1586                 if (sn2>=rectx) sn2= rectx-1;
1587                 if (sn1<0) sn1= 0;
1588
1589                 u= (double)sn1*uxd + uy0;
1590                 v= (double)sn1*vxd + vy0;
1591
1592                 for (x= sn1; x<=sn2; x++, u+=uxd, v+=vxd)
1593                         func(handle, x, y, u, v);
1594
1595                 uy0 -= uyd;
1596                 vy0 -= vyd;
1597         }
1598 }
1599
1600
1601
1602 /**
1603  * (clip pyramid)
1604  * Sets lambda: flag, and parametrize the clipping of vertices in
1605  * viewspace coordinates. lambda = -1 means no clipping, lambda in [0, 1] means a clipping.
1606  * Note: uses globals.
1607  * \param v1 start coordinate s
1608  * \param v2 target coordinate t
1609  * \param b1
1610  * \param b2
1611  * \param b3
1612  * \param a index for coordinate (x, y, or z)
1613  */
1614
1615 static void clippyra(float *lambda, float *v1, float *v2, int *b2, int *b3, int a, float clipcrop)
1616 {
1617         float da, dw, u1=0.0, u2=1.0;
1618         float v13;
1619
1620         lambda[0]= -1.0;
1621         lambda[1]= -1.0;
1622
1623         da= v2[a]-v1[a];
1624         /* prob; we clip slightly larger, osa renders add 2 pixels on edges, should become variable? */
1625         /* or better; increase r.winx/y size, but thats quite a complex one. do it later */
1626         if (a==2) {
1627                 dw= (v2[3]-v1[3]);
1628                 v13= v1[3];
1629         }
1630         else {
1631                 dw= clipcrop*(v2[3]-v1[3]);
1632                 v13= clipcrop*v1[3];
1633         }
1634         /* according the original article by Liang&Barsky, for clipping of
1635          * homogeneous coordinates with viewplane, the value of "0" is used instead of "-w" .
1636          * This differs from the other clipping cases (like left or top) and I considered
1637          * it to be not so 'homogenic'. But later it has proven to be an error,
1638          * who would have thought that of L&B!
1639          */
1640
1641         if (cliptestf(-da, -dw, v13, v1[a], &u1, &u2)) {
1642                 if (cliptestf(da, -dw, v13, -v1[a], &u1, &u2)) {
1643                         *b3=1;
1644                         if (u2<1.0f) {
1645                                 lambda[1]= u2;
1646                                 *b2=1;
1647                         }
1648                         else lambda[1]=1.0;  /* u2 */
1649                         if (u1>0.0f) {
1650                                 lambda[0] = u1;
1651                                 *b2 = 1;
1652                         }
1653                         else {
1654                                 lambda[0] = 0.0;
1655                         }
1656                 }
1657         }
1658 }
1659
1660 /**
1661  * (make vertex pyramide clip)
1662  * Checks lambda and uses this to make decision about clipping the line
1663  * segment from v1 to v2. lambda is the factor by which the vector is
1664  * cut. ( calculate s + l * ( t - s )). The result is appended to the
1665  * vertex list of this face.
1666  *
1667  *
1668  * \param v1 start coordinate s
1669  * \param v2 target coordinate t
1670  * \param b1
1671  * \param b2
1672  * \param clve vertex vector.
1673  */
1674
1675 static void makevertpyra(float *vez, float *lambda, float **trias, float *v1, float *v2, int *b1, int *clve)
1676 {
1677         float l1, l2, *adr;
1678
1679         l1= lambda[0];
1680         l2= lambda[1];
1681
1682         if (l1!= -1.0f) {
1683                 if (l1!= 0.0f) {
1684                         adr= vez+4*(*clve);
1685                         trias[*b1]=adr;
1686                         (*clve)++;
1687                         adr[0]= v1[0]+l1*(v2[0]-v1[0]);
1688                         adr[1]= v1[1]+l1*(v2[1]-v1[1]);
1689                         adr[2]= v1[2]+l1*(v2[2]-v1[2]);
1690                         adr[3]= v1[3]+l1*(v2[3]-v1[3]);
1691                 }
1692                 else trias[*b1]= v1;
1693
1694                 (*b1)++;
1695         }
1696         if (l2!= -1.0f) {
1697                 if (l2!= 1.0f) {
1698                         adr= vez+4*(*clve);
1699                         trias[*b1]=adr;
1700                         (*clve)++;
1701                         adr[0]= v1[0]+l2*(v2[0]-v1[0]);
1702                         adr[1]= v1[1]+l2*(v2[1]-v1[1]);
1703                         adr[2]= v1[2]+l2*(v2[2]-v1[2]);
1704                         adr[3]= v1[3]+l2*(v2[3]-v1[3]);
1705                         (*b1)++;
1706                 }
1707         }
1708 }
1709
1710 /* ------------------------------------------------------------------------- */
1711
1712 void projectverto(const float v1[3], float winmat[4][4], float adr[4])
1713 {
1714         /* calcs homogenic coord of vertex v1 */
1715         float x, y, z;
1716
1717         x = v1[0];
1718         y = v1[1];
1719         z = v1[2];
1720         adr[0] = x * winmat[0][0] + z * winmat[2][0] + winmat[3][0];
1721         adr[1] = y * winmat[1][1] + z * winmat[2][1] + winmat[3][1];
1722         adr[2] =                    z * winmat[2][2] + winmat[3][2];
1723         adr[3] =                    z * winmat[2][3] + winmat[3][3];
1724
1725         //printf("hoco %f %f %f %f\n", adr[0], adr[1], adr[2], adr[3]);
1726 }
1727
1728 /* ------------------------------------------------------------------------- */
1729
1730 void projectvert(const float v1[3], float winmat[4][4], float adr[4])
1731 {
1732         /* calcs homogenic coord of vertex v1 */
1733         float x, y, z;
1734
1735         x = v1[0];
1736         y = v1[1];
1737         z = v1[2];
1738         adr[0] = x * winmat[0][0] + y * winmat[1][0] + z * winmat[2][0] + winmat[3][0];
1739         adr[1] = x * winmat[0][1] + y * winmat[1][1] + z * winmat[2][1] + winmat[3][1];
1740         adr[2] = x * winmat[0][2] + y * winmat[1][2] + z * winmat[2][2] + winmat[3][2];
1741         adr[3] = x * winmat[0][3] + y * winmat[1][3] + z * winmat[2][3] + winmat[3][3];
1742 }
1743
1744 /* ------------------------------------------------------------------------- */
1745
1746 #define ZBUF_PROJECT_CACHE_SIZE 256
1747
1748 typedef struct ZbufProjectCache {
1749         int index, clip;
1750         float ho[4];
1751 } ZbufProjectCache;
1752
1753 static void zbuf_project_cache_clear(ZbufProjectCache *cache, int size)
1754 {
1755         int i;
1756
1757         if (size > ZBUF_PROJECT_CACHE_SIZE)
1758                 size= ZBUF_PROJECT_CACHE_SIZE;
1759
1760         memset(cache, 0, sizeof(ZbufProjectCache)*size);
1761         for (i=0; i<size; i++)
1762                 cache[i].index= -1;
1763 }
1764
1765 static int zbuf_shadow_project(ZbufProjectCache *cache, int index, float winmat[4][4], float *co, float *ho)
1766 {
1767         int cindex= index & 255;
1768
1769         if (cache[cindex].index == index) {
1770                 copy_v4_v4(ho, cache[cindex].ho);
1771                 return cache[cindex].clip;
1772         }
1773         else {
1774                 int clipflag;
1775                 projectvert(co, winmat, ho);
1776                 clipflag= testclip(ho);
1777
1778                 copy_v4_v4(cache[cindex].ho, ho);
1779                 cache[cindex].clip= clipflag;
1780                 cache[cindex].index= index;
1781
1782                 return clipflag;
1783         }
1784 }
1785
1786 static void zbuffer_part_bounds(int winx, int winy, RenderPart *pa, float *bounds)
1787 {
1788         bounds[0]= (2*pa->disprect.xmin - winx-1)/(float)winx;
1789         bounds[1]= (2*pa->disprect.xmax - winx+1)/(float)winx;
1790         bounds[2]= (2*pa->disprect.ymin - winy-1)/(float)winy;
1791         bounds[3]= (2*pa->disprect.ymax - winy+1)/(float)winy;
1792 }
1793
1794 static int zbuf_part_project(ZbufProjectCache *cache, int index, float winmat[4][4], float *bounds, float *co, float *ho)
1795 {
1796         float vec[3];
1797         int cindex= index & 255;
1798
1799         if (cache[cindex].index == index) {
1800                 copy_v4_v4(ho, cache[cindex].ho);
1801                 return cache[cindex].clip;
1802         }
1803         else {
1804                 float wco;
1805                 int clipflag= 0;
1806                 copy_v3_v3(vec, co);
1807                 projectvert(co, winmat, ho);
1808
1809                 wco= ho[3];
1810                 if (ho[0] < bounds[0]*wco) clipflag |= 1;
1811                 else if (ho[0] > bounds[1]*wco) clipflag |= 2;
1812                 if (ho[1] > bounds[3]*wco) clipflag |= 4;
1813                 else if (ho[1] < bounds[2]*wco) clipflag |= 8;
1814
1815                 copy_v4_v4(cache[cindex].ho, ho);
1816                 cache[cindex].clip= clipflag;
1817                 cache[cindex].index= index;
1818
1819                 return clipflag;
1820         }
1821 }
1822
1823 void zbuf_render_project(float winmat[4][4], const float co[3], float ho[4])
1824 {
1825         float vec[3];
1826
1827         copy_v3_v3(vec, co);
1828         projectvert(vec, winmat, ho);
1829 }
1830
1831 void zbuf_make_winmat(Render *re, float winmat[4][4])
1832 {
1833         if (re->r.mode & R_PANORAMA) {
1834                 float panomat[4][4]= MAT4_UNITY;
1835
1836                 panomat[0][0]= re->panoco;
1837                 panomat[0][2]= re->panosi;
1838                 panomat[2][0]= -re->panosi;
1839                 panomat[2][2]= re->panoco;
1840
1841                 mul_m4_m4m4(winmat, re->winmat, panomat);
1842         }
1843         else
1844                 copy_m4_m4(winmat, re->winmat);
1845 }
1846
1847 /* do zbuffering and clip, f1 f2 f3 are hocos, c1 c2 c3 are clipping flags */
1848
1849 void zbufclip(ZSpan *zspan, int obi, int zvlnr,
1850               const float f1[4], const float f2[4], const float f3[4],
1851               const int c1, const int c2, const int c3)
1852 {
1853         float *vlzp[32][3], lambda[3][2];
1854         float vez[400], *trias[40];
1855
1856         if (c1 | c2 | c3) {     /* not in middle */
1857                 if (c1 & c2 & c3) {     /* completely out */
1858                         return;
1859                 }
1860                 else {  /* clipping */
1861                         int arg, v, b, clipflag[3], b1, b2, b3, c4, clve=3, clvlo, clvl=1;
1862                         float *fp;
1863
1864                         vez[0]= f1[0]; vez[1]= f1[1]; vez[2]= f1[2]; vez[3]= f1[3];
1865                         vez[4]= f2[0]; vez[5]= f2[1]; vez[6]= f2[2]; vez[7]= f2[3];
1866                         vez[8]= f3[0]; vez[9]= f3[1]; vez[10]= f3[2];vez[11]= f3[3];
1867
1868                         vlzp[0][0]= vez;
1869                         vlzp[0][1]= vez+4;
1870                         vlzp[0][2]= vez+8;
1871
1872                         clipflag[0]= ( (c1 & 48) | (c2 & 48) | (c3 & 48) );
1873                         if (clipflag[0]==0) {   /* othwerwise it needs to be calculated again, after the first (z) clip */
1874                                 clipflag[1]= ( (c1 & 3) | (c2 & 3) | (c3 & 3) );
1875                                 clipflag[2]= ( (c1 & 12) | (c2 & 12) | (c3 & 12) );
1876                         }
1877                         else clipflag[1]=clipflag[2]= 0;
1878
1879                         for (b=0;b<3;b++) {
1880
1881                                 if (clipflag[b]) {
1882
1883                                         clvlo= clvl;
1884
1885                                         for (v=0; v<clvlo; v++) {
1886
1887                                                 if (vlzp[v][0]!=NULL) { /* face is still there */
1888                                                         b2= b3 =0;      /* clip flags */
1889
1890                                                         if (b==0) arg= 2;
1891                                                         else if (b==1) arg= 0;
1892                                                         else arg= 1;
1893
1894                                                         clippyra(lambda[0], vlzp[v][0], vlzp[v][1], &b2, &b3, arg, zspan->clipcrop);
1895                                                         clippyra(lambda[1], vlzp[v][1], vlzp[v][2], &b2, &b3, arg, zspan->clipcrop);
1896                                                         clippyra(lambda[2], vlzp[v][2], vlzp[v][0], &b2, &b3, arg, zspan->clipcrop);
1897
1898                                                         if (b2==0 && b3==1) {
1899                                                                 /* completely 'in', but we copy because of last for () loop in this section */;
1900                                                                 vlzp[clvl][0]= vlzp[v][0];
1901                                                                 vlzp[clvl][1]= vlzp[v][1];
1902                                                                 vlzp[clvl][2]= vlzp[v][2];
1903                                                                 vlzp[v][0]= NULL;
1904                                                                 clvl++;
1905                                                         }
1906                                                         else if (b3==0) {
1907                                                                 vlzp[v][0]= NULL;
1908                                                                 /* completely 'out' */;
1909                                                         }
1910                                                         else {
1911                                                                 b1=0;
1912                                                                 makevertpyra(vez, lambda[0], trias, vlzp[v][0], vlzp[v][1], &b1, &clve);
1913                                                                 makevertpyra(vez, lambda[1], trias, vlzp[v][1], vlzp[v][2], &b1, &clve);
1914                                                                 makevertpyra(vez, lambda[2], trias, vlzp[v][2], vlzp[v][0], &b1, &clve);
1915
1916                                                                 /* after front clip done: now set clip flags */
1917                                                                 if (b==0) {
1918                                                                         clipflag[1]= clipflag[2]= 0;
1919                                                                         f1= vez;
1920                                                                         for (b3=0; b3<clve; b3++) {
1921                                                                                 c4= testclip(f1);
1922                                                                                 clipflag[1] |= (c4 & 3);
1923                                                                                 clipflag[2] |= (c4 & 12);
1924                                                                                 f1+= 4;
1925                                                                         }
1926                                                                 }
1927
1928                                                                 vlzp[v][0]= NULL;
1929                                                                 if (b1>2) {
1930                                                                         for (b3=3; b3<=b1; b3++) {
1931                                                                                 vlzp[clvl][0]= trias[0];
1932                                                                                 vlzp[clvl][1]= trias[b3-2];
1933                                                                                 vlzp[clvl][2]= trias[b3-1];
1934                                                                                 clvl++;
1935                                                                         }
1936                                                                 }
1937                                                         }
1938                                                 }
1939                                         }
1940                                 }
1941                         }
1942
1943                         /* warning, clip overflow, this should never happen! */
1944                         BLI_assert(!(clve > 38 || clvl > 31));
1945
1946                         /* perspective division */
1947                         fp = vez;
1948                         for (b = 0; b < clve; b++) {
1949                                 hoco_to_zco(zspan, fp, fp);
1950                                 fp += 4;
1951                         }
1952                         for (b = 1; b < clvl; b++) {
1953                                 if (vlzp[b][0]) {
1954                                         zspan->zbuffunc(zspan, obi, zvlnr, vlzp[b][0], vlzp[b][1], vlzp[b][2], NULL);
1955                                 }
1956                         }
1957                         return;
1958                 }
1959         }
1960
1961         /* perspective division: HCS to ZCS */
1962         hoco_to_zco(zspan, vez, f1);
1963         hoco_to_zco(zspan, vez+4, f2);
1964         hoco_to_zco(zspan, vez+8, f3);
1965         zspan->zbuffunc(zspan, obi, zvlnr, vez, vez+4, vez+8, NULL);
1966 }
1967
1968 void zbufclip4(ZSpan *zspan, int obi, int zvlnr,
1969                const float f1[4], const float f2[4], const float f3[4], const float f4[4],
1970                const int c1, const int c2, const int c3, const int c4)
1971 {
1972         float vez[16];
1973
1974         if (c1 | c2 | c3 | c4) {        /* not in middle */
1975                 if (c1 & c2 & c3 & c4) {        /* completely out */
1976                         return;
1977                 }
1978                 else {  /* clipping */
1979                         zbufclip(zspan, obi, zvlnr, f1, f2, f3, c1, c2, c3);
1980                         zbufclip(zspan, obi, zvlnr, f1, f3, f4, c1, c3, c4);
1981                 }
1982                 return;
1983         }
1984
1985         /* perspective division: HCS to ZCS */
1986         hoco_to_zco(zspan, vez, f1);
1987         hoco_to_zco(zspan, vez+4, f2);
1988         hoco_to_zco(zspan, vez+8, f3);
1989         hoco_to_zco(zspan, vez+12, f4);
1990
1991         zspan->zbuffunc(zspan, obi, zvlnr, vez, vez+4, vez+8, vez+12);
1992 }
1993
1994 /* ************** ZMASK ******************************** */
1995
1996 #define EXTEND_PIXEL(a) if (temprectp[a]) { z += rectz[a]; tot++; } (void)0
1997
1998 /* changes the zbuffer to be ready for z-masking: applies an extend-filter, and then clears */
1999 static void zmask_rect(int *rectz, int *rectp, int xs, int ys, int neg)
2000 {
2001         int len=0, x, y;
2002         int *temprectp;
2003         int row1, row2, row3, *curp, *curz;
2004
2005         temprectp= MEM_dupallocN(rectp);
2006
2007         /* extend: if pixel is not filled in, we check surrounding pixels and average z value  */
2008
2009         for (y=1; y<=ys; y++) {
2010                 /* setup row indices */
2011                 row1= (y-2)*xs;
2012                 row2= row1 + xs;
2013                 row3= row2 + xs;
2014                 if (y==1)
2015                         row1= row2;
2016                 else if (y==ys)
2017                         row3= row2;
2018
2019                 curp= rectp + (y-1)*xs;
2020                 curz= rectz + (y-1)*xs;
2021
2022                 for (x=0; x<xs; x++, curp++, curz++) {
2023                         if (curp[0]==0) {
2024                                 int tot= 0;
2025                                 float z= 0.0f;
2026
2027                                 EXTEND_PIXEL(row1);
2028                                 EXTEND_PIXEL(row2);
2029                                 EXTEND_PIXEL(row3);
2030                                 EXTEND_PIXEL(row1 + 1);
2031                                 EXTEND_PIXEL(row3 + 1);
2032                                 if (x!=xs-1) {
2033                                         EXTEND_PIXEL(row1 + 2);
2034                                         EXTEND_PIXEL(row2 + 2);
2035                                         EXTEND_PIXEL(row3 + 2);
2036                                 }
2037                                 if (tot) {
2038                                         len++;
2039                                         curz[0]= (int)(z/(float)tot);
2040                                         curp[0]= -1;    /* env */
2041                                 }
2042                         }
2043
2044                         if (x!=0) {
2045                                 row1++; row2++; row3++;
2046                         }
2047                 }
2048         }
2049
2050         MEM_freeN(temprectp);
2051
2052         if (neg) {
2053                 /* z values for negative are already correct */
2054         }
2055         else {
2056                 /* clear not filled z values */
2057                 for (len= xs*ys -1; len>=0; len--) {
2058                         if (rectp[len]==0) {
2059                                 rectz[len] = -0x7FFFFFFF;
2060                                 rectp[len]= -1; /* env code */
2061                         }
2062                 }
2063         }
2064 }
2065
2066
2067
2068
2069 /* ***************** ZBUFFER MAIN ROUTINES **************** */
2070
2071 void zbuffer_solid(RenderPart *pa, RenderLayer *rl, void(*fillfunc)(RenderPart *, ZSpan *, int, void *), void *data)
2072 {
2073         ZbufProjectCache cache[ZBUF_PROJECT_CACHE_SIZE];
2074         ZSpan zspans[16], *zspan; /* 16 = RE_MAX_OSA */
2075         VlakRen *vlr= NULL;
2076         VertRen *v1, *v2, *v3, *v4;
2077         Material *ma = NULL;
2078         ObjectInstanceRen *obi;
2079         ObjectRen *obr;
2080         float obwinmat[4][4], winmat[4][4], bounds[4];
2081         float ho1[4], ho2[4], ho3[4], ho4[4]={0};
2082         unsigned int lay= rl->lay, lay_zmask= rl->lay_zmask;
2083         int i, v, zvlnr, zsample, samples, c1, c2, c3, c4=0;
2084         short nofill=0, env=0, wire=0, zmaskpass=0;
2085         short all_z= (rl->layflag & SCE_LAY_ALL_Z) && !(rl->layflag & SCE_LAY_ZMASK);
2086         short neg_zmask= (rl->layflag & SCE_LAY_ZMASK) && (rl->layflag & SCE_LAY_NEG_ZMASK);
2087
2088         zbuf_make_winmat(&R, winmat);
2089
2090         samples= (R.osa? R.osa: 1);
2091         samples= MIN2(4, samples-pa->sample);
2092
2093         for (zsample=0; zsample<samples; zsample++) {
2094                 zspan= &zspans[zsample];
2095
2096                 zbuffer_part_bounds(R.winx, R.winy, pa, bounds);
2097                 zbuf_alloc_span(zspan, pa->rectx, pa->recty, R.clipcrop);
2098
2099                 /* needed for transform from hoco to zbuffer co */
2100                 zspan->zmulx= ((float)R.winx)/2.0f;
2101                 zspan->zmuly= ((float)R.winy)/2.0f;
2102
2103                 if (R.osa) {
2104                         zspan->zofsx= -pa->disprect.xmin - R.jit[pa->sample+zsample][0];
2105                         zspan->zofsy= -pa->disprect.ymin - R.jit[pa->sample+zsample][1];
2106                 }
2107                 else if (R.i.curblur) {
2108                         zspan->zofsx= -pa->disprect.xmin - R.mblur_jit[R.i.curblur-1][0];
2109                         zspan->zofsy= -pa->disprect.ymin - R.mblur_jit[R.i.curblur-1][1];
2110                 }
2111                 else {
2112                         zspan->zofsx= -pa->disprect.xmin;
2113                         zspan->zofsy= -pa->disprect.ymin;
2114                 }
2115                 /* to center the sample position */
2116                 zspan->zofsx -= 0.5f;
2117                 zspan->zofsy -= 0.5f;
2118
2119                 /* the buffers */
2120                 if (zsample == samples-1) {
2121                         zspan->rectp= pa->rectp;
2122                         zspan->recto= pa->recto;
2123
2124                         if (neg_zmask)
2125                                 zspan->rectz= pa->rectmask;
2126                         else
2127                                 zspan->rectz= pa->rectz;
2128                 }
2129                 else {
2130                         zspan->recto= MEM_mallocN(sizeof(int)*pa->rectx*pa->recty, "recto");
2131                         zspan->rectp= MEM_mallocN(sizeof(int)*pa->rectx*pa->recty, "rectp");
2132                         zspan->rectz= MEM_mallocN(sizeof(int)*pa->rectx*pa->recty, "rectz");
2133                 }
2134
2135                 fillrect(zspan->rectz, pa->rectx, pa->recty, 0x7FFFFFFF);
2136                 fillrect(zspan->rectp, pa->rectx, pa->recty, 0);
2137                 fillrect(zspan->recto, pa->rectx, pa->recty, 0);
2138         }
2139
2140         /* in case zmask we fill Z for objects in lay_zmask first, then clear Z, and then do normal zbuffering */
2141         if (rl->layflag & SCE_LAY_ZMASK)
2142                 zmaskpass= 1;
2143
2144         for (; zmaskpass >=0; zmaskpass--) {
2145                 ma= NULL;
2146
2147                 /* filling methods */
2148                 for (zsample=0; zsample<samples; zsample++) {
2149                         zspan= &zspans[zsample];
2150
2151                         if (zmaskpass && neg_zmask)
2152                                 zspan->zbuffunc= zbuffillGLinv4;
2153                         else
2154                                 zspan->zbuffunc= zbuffillGL4;
2155                         zspan->zbuflinefunc= zbufline;
2156                 }
2157
2158                 /* regular zbuffering loop, does all sample buffers */
2159                 for (i=0, obi=R.instancetable.first; obi; i++, obi=obi->next) {
2160                         obr= obi->obr;
2161
2162                         /* continue happens in 2 different ways... zmaskpass only does lay_zmask stuff */
2163                         if (zmaskpass) {
2164                                 if ((obi->lay & lay_zmask)==0)
2165                                         continue;
2166                         }
2167                         else if (!all_z && !(obi->lay & (lay|lay_zmask)))
2168                                 continue;
2169
2170                         if (obi->flag & R_TRANSFORMED)
2171                                 mul_m4_m4m4(obwinmat, winmat, obi->mat);
2172                         else
2173                                 copy_m4_m4(obwinmat, winmat);
2174
2175                         if (clip_render_object(obi->obr->boundbox, bounds, obwinmat))
2176                                 continue;
2177
2178                         zbuf_project_cache_clear(cache, obr->totvert);
2179
2180                         for (v=0; v<obr->totvlak; v++) {
2181                                 if ((v & 255)==0) vlr= obr->vlaknodes[v>>8].vlak;
2182                                 else vlr++;
2183
2184                                 /* the cases: visible for render, only z values, zmask, nothing */
2185                                 if (obi->lay & lay) {
2186                                         if (vlr->mat!=ma) {
2187                                                 ma= vlr->mat;
2188                                                 nofill= (ma->mode & MA_ONLYCAST) || ((ma->mode & MA_TRANSP) && (ma->mode & MA_ZTRANSP));
2189                                                 env= (ma->mode & MA_ENV);
2190                                                 wire= (ma->material_type == MA_TYPE_WIRE);
2191
2192                                                 for (zsample=0; zsample<samples; zsample++) {
2193                                                         if (ma->mode & MA_ZINV || (zmaskpass && neg_zmask))
2194                                                                 zspans[zsample].zbuffunc= zbuffillGLinv4;
2195                                                         else
2196                                                                 zspans[zsample].zbuffunc= zbuffillGL4;
2197                                                 }
2198                                         }
2199                                 }
2200                                 else if (all_z || (obi->lay & lay_zmask)) {
2201                                         env= 1;
2202                                         nofill= 0;
2203                                         ma= NULL;
2204                                 }
2205                                 else {
2206                                         nofill= 1;
2207                                         ma= NULL;       /* otherwise nofill can hang */
2208                                 }
2209
2210                                 if (!(vlr->flag & R_HIDDEN) && nofill==0) {
2211                                         unsigned short partclip;
2212
2213                                         v1= vlr->v1;
2214                                         v2= vlr->v2;
2215                                         v3= vlr->v3;
2216                                         v4= vlr->v4;
2217
2218                                         c1= zbuf_part_project(cache, v1->index, obwinmat, bounds, v1->co, ho1);
2219                                         c2= zbuf_part_project(cache, v2->index, obwinmat, bounds, v2->co, ho2);
2220                                         c3= zbuf_part_project(cache, v3->index, obwinmat, bounds, v3->co, ho3);
2221
2222                                         /* partclipping doesn't need viewplane clipping */
2223                                         partclip= c1 & c2 & c3;
2224                                         if (v4) {
2225                                                 c4= zbuf_part_project(cache, v4->index, obwinmat, bounds, v4->co, ho4);
2226                                                 partclip &= c4;
2227                                         }
2228
2229                                         if (partclip==0) {
2230
2231                                                 if (env) zvlnr= -1;
2232                                                 else zvlnr= v+1;
2233
2234                                                 c1= testclip(ho1);
2235                                                 c2= testclip(ho2);
2236                                                 c3= testclip(ho3);
2237                                                 if (v4)
2238                                                         c4= testclip(ho4);
2239
2240                                                 for (zsample=0; zsample<samples; zsample++) {
2241                                                         zspan= &zspans[zsample];
2242
2243                                                         if (wire) {
2244                                                                 if (v4)
2245                                                                         zbufclipwire(zspan, i, zvlnr, vlr->ec, ho1, ho2, ho3, ho4, c1, c2, c3, c4);
2246                                                                 else
2247                                                                         zbufclipwire(zspan, i, zvlnr, vlr->ec, ho1, ho2, ho3, NULL, c1, c2, c3, 0);
2248                                                         }
2249                                                         else {
2250                                                                 /* strands allow to be filled in as quad */
2251                                                                 if (v4 && (vlr->flag & R_STRAND)) {
2252                                                                         zbufclip4(zspan, i, zvlnr, ho1, ho2, ho3, ho4, c1, c2, c3, c4);
2253                                                                 }
2254                                                                 else {
2255                                                                         zbufclip(zspan, i, zvlnr, ho1, ho2, ho3, c1, c2, c3);
2256                                                                         if (v4)
2257                                                                                 zbufclip(zspan, i, (env)? zvlnr: zvlnr+RE_QUAD_OFFS, ho1, ho3, ho4, c1, c3, c4);
2258                                                                 }
2259                                                         }
2260                                                 }
2261                                         }
2262                                 }
2263                         }
2264                 }
2265
2266                 /* clear all z to close value, so it works as mask for next passes (ztra+strand) */
2267                 if (zmaskpass) {
2268                         for (zsample=0; zsample<samples; zsample++) {
2269                                 zspan= &zspans[zsample];
2270
2271                                 if (neg_zmask) {
2272                                         zspan->rectmask= zspan->rectz;
2273                                         if (zsample == samples-1)
2274                                                 zspan->rectz= pa->rectz;
2275                                         else
2276                                                 zspan->rectz= MEM_mallocN(sizeof(int)*pa->rectx*pa->recty, "rectz");
2277                                         fillrect(zspan->rectz, pa->rectx, pa->recty, 0x7FFFFFFF);
2278
2279                                         zmask_rect(zspan->rectmask, zspan->rectp, pa->rectx, pa->recty, 1);
2280                                 }
2281                                 else
2282                                         zmask_rect(zspan->rectz, zspan->rectp, pa->rectx, pa->recty, 0);
2283                         }
2284                 }
2285         }
2286
2287         for (zsample=0; zsample<samples; zsample++) {
2288                 zspan= &zspans[zsample];
2289
2290                 if (fillfunc)
2291                         fillfunc(pa, zspan, pa->sample+zsample, data);
2292
2293                 if (zsample != samples-1) {
2294                         MEM_freeN(zspan->rectz);
2295                         MEM_freeN(zspan->rectp);
2296                         MEM_freeN(zspan->recto);
2297                         if (zspan->rectmask)
2298                                 MEM_freeN(zspan->rectmask);
2299                 }
2300
2301                 zbuf_free_span(zspan);
2302         }
2303 }
2304
2305 void zbuffer_shadow(Render *re, float winmat[4][4], LampRen *lar, int *rectz, int size, float jitx, float jity)
2306 {
2307         ZbufProjectCache cache[ZBUF_PROJECT_CACHE_SIZE];
2308         ZSpan zspan;
2309         ObjectInstanceRen *obi;
2310         ObjectRen *obr;
2311         VlakRen *vlr= NULL;
2312         Material *ma= NULL;
2313         StrandSegment sseg;
2314         StrandRen *strand= NULL;
2315         StrandVert *svert;
2316         StrandBound *sbound;
2317         float obwinmat[4][4], ho1[4], ho2[4], ho3[4], ho4[4];
2318         int a, b, c, i, c1, c2, c3, c4, ok=1, lay= -1;
2319
2320         if (lar->mode & (LA_LAYER|LA_LAYER_SHADOW)) lay= lar->lay;
2321
2322         /* 1.0f for clipping in clippyra()... bad stuff actually */
2323         zbuf_alloc_span(&zspan, size, size, 1.0f);
2324         zspan.zmulx=  ((float)size)/2.0f;
2325         zspan.zmuly=  ((float)size)/2.0f;
2326         /* -0.5f to center the sample position */
2327         zspan.zofsx= jitx - 0.5f;
2328         zspan.zofsy= jity - 0.5f;
2329
2330         /* the buffers */
2331         zspan.rectz= rectz;
2332         fillrect(rectz, size, size, 0x7FFFFFFE);
2333         if (lar->buftype==LA_SHADBUF_HALFWAY) {
2334                 zspan.rectz1= MEM_mallocN(size*size*sizeof(int), "seconday z buffer");
2335                 fillrect(zspan.rectz1, size, size, 0x7FFFFFFE);
2336         }
2337
2338         /* filling methods */
2339         zspan.zbuflinefunc= zbufline_onlyZ;
2340         zspan.zbuffunc= zbuffillGL_onlyZ;
2341
2342         for (i=0, obi=re->instancetable.first; obi; i++, obi=obi->next) {
2343                 obr= obi->obr;
2344
2345                 if (obr->ob==re->excludeob)
2346                         continue;
2347                 else if (!(obi->lay & lay))
2348                         continue;
2349
2350                 if (obi->flag & R_TRANSFORMED)
2351                         mul_m4_m4m4(obwinmat, winmat, obi->mat);
2352                 else
2353                         copy_m4_m4(obwinmat, winmat);
2354
2355                 if (clip_render_object(obi->obr->boundbox, NULL, obwinmat))
2356                         continue;
2357
2358                 zbuf_project_cache_clear(cache, obr->totvert);
2359
2360                 /* faces */
2361                 for (a=0; a<obr->totvlak; a++) {
2362
2363                         if ((a & 255)==0) vlr= obr->vlaknodes[a>>8].vlak;
2364                         else vlr++;
2365
2366                         /* note, these conditions are copied in shadowbuf_autoclip() */
2367                         if (vlr->mat!= ma) {
2368                                 ma= vlr->mat;
2369                                 ok= 1;
2370                                 if ((ma->mode2 & MA_CASTSHADOW)==0 || (ma->mode & MA_SHADBUF)==0) ok= 0;
2371                         }
2372
2373                         if (ok && (obi->lay & lay) && !(vlr->flag & R_HIDDEN)) {
2374                                 c1= zbuf_shadow_project(cache, vlr->v1->index, obwinmat, vlr->v1->co, ho1);
2375                                 c2= zbuf_shadow_project(cache, vlr->v2->index, obwinmat, vlr->v2->co, ho2);
2376                                 c3= zbuf_shadow_project(cache, vlr->v3->index, obwinmat, vlr->v3->co, ho3);
2377
2378                                 if ((ma->material_type == MA_TYPE_WIRE) || (vlr->flag & R_STRAND)) {
2379                                         if (vlr->v4) {
2380                                                 c4= zbuf_shadow_project(cache, vlr->v4->index, obwinmat, vlr->v4->co, ho4);
2381                                                 zbufclipwire(&zspan, 0, a+1, vlr->ec, ho1, ho2, ho3, ho4, c1, c2, c3, c4);
2382                                         }
2383                                         else
2384                                                 zbufclipwire(&zspan, 0, a+1, vlr->ec, ho1, ho2, ho3, NULL, c1, c2, c3, 0);
2385                                 }
2386                                 else {
2387                                         if (vlr->v4) {
2388                                                 c4= zbuf_shadow_project(cache, vlr->v4->index, obwinmat, vlr->v4->co, ho4);
2389                                                 zbufclip4(&zspan, 0, 0, ho1, ho2, ho3, ho4, c1, c2, c3, c4);
2390                                         }
2391                                         else
2392                                                 zbufclip(&zspan, 0, 0, ho1, ho2, ho3, c1, c2, c3);
2393                                 }
2394                         }
2395
2396                         if ((a & 255)==255 && re->test_break(re->tbh))
2397                                 break;
2398                 }
2399
2400                 /* strands */
2401                 if (obr->strandbuf) {
2402                         /* for each bounding box containing a number of strands */
2403                         sbound= obr->strandbuf->bound;
2404                         for (c=0; c<obr->strandbuf->totbound; c++, sbound++) {
2405                                 if (clip_render_object(sbound->boundbox, NULL, obwinmat))
2406                                         continue;
2407
2408                                 /* for each strand in this bounding box */
2409                                 for (a=sbound->start; a<sbound->end; a++) {
2410                                         strand= RE_findOrAddStrand(obr, a);
2411
2412                                         sseg.obi= obi;
2413                                         sseg.buffer= strand->buffer;
2414                                         sseg.sqadaptcos= sseg.buffer->adaptcos;
2415                                         sseg.sqadaptcos *= sseg.sqadaptcos;
2416                                         sseg.strand= strand;
2417                                         svert= strand->vert;
2418
2419                                         /* note, these conditions are copied in shadowbuf_autoclip() */
2420                                         if (sseg.buffer->ma!= ma) {
2421                                                 ma= sseg.buffer->ma;
2422                                                 ok= 1;
2423                                                 if ((ma->mode2 & MA_CASTSHADOW)==0 || (ma->mode & MA_SHADBUF)==0) ok= 0;
2424                                         }
2425
2426                                         if (ok && (sseg.buffer->lay & lay)) {
2427                                                 zbuf_project_cache_clear(cache, strand->totvert);
2428
2429                                                 for (b=0; b<strand->totvert-1; b++, svert++) {
2430                                                         sseg.v[0]= (b > 0)? (svert-1): svert;
2431                                                         sseg.v[1]= svert;
2432                                                         sseg.v[2]= svert+1;
2433                                                         sseg.v[3]= (b < strand->totvert-2)? svert+2: svert+1;
2434
2435                                                         c1= zbuf_shadow_project(cache, sseg.v[0]-strand->vert, obwinmat, sseg.v[0]->co, ho1);
2436                                                         c2= zbuf_shadow_project(cache, sseg.v[1]-strand->vert, obwinmat, sseg.v[1]->co, ho2);
2437                                                         c3= zbuf_shadow_project(cache, sseg.v[2]-strand->vert, obwinmat, sseg.v[2]->co, ho3);
2438                                                         c4= zbuf_shadow_project(cache, sseg.v[3]-strand->vert, obwinmat, sseg.v[3]->co, ho4);
2439
2440                                                         if (!(c1 & c2 & c3 & c4))
2441                                                                 render_strand_segment(re, winmat, NULL, &zspan, 1, &sseg);
2442                                                 }
2443                                         }
2444
2445                                         if ((a & 255)==255 && re->test_break(re->tbh))
2446                                                 break;
2447                                 }
2448                         }
2449                 }
2450
2451                 if (re->test_break(re->tbh))
2452                         break;
2453         }
2454
2455         /* merge buffers */
2456         if (lar->buftype==LA_SHADBUF_HALFWAY) {
2457                 for (a=size*size -1; a>=0; a--)
2458                         rectz[a]= (rectz[a]>>1) + (zspan.rectz1[a]>>1);
2459
2460                 MEM_freeN(zspan.rectz1);
2461         }
2462
2463         zbuf_free_span(&zspan);
2464 }
2465
2466 static void zbuffill_sss(ZSpan *zspan, int obi, int zvlnr,
2467                          const float *v1, const float *v2, const float *v3, const float *v4)
2468 {
2469         double zxd, zyd, zy0, z;
2470         float x0, y0, x1, y1, x2, y2, z0, z1, z2, xx1, *span1, *span2;
2471         int x, y, sn1, sn2, rectx= zspan->rectx, my0, my2;
2472         /* init */
2473         zbuf_init_span(zspan);
2474
2475         /* set spans */
2476         zbuf_add_to_span(zspan, v1, v2);
2477         zbuf_add_to_span(zspan, v2, v3);
2478         if (v4) {
2479                 zbuf_add_to_span(zspan, v3, v4);
2480                 zbuf_add_to_span(zspan, v4, v1);
2481         }
2482         else
2483                 zbuf_add_to_span(zspan, v3, v1);
2484
2485         /* clipped */
2486         if (zspan->minp2==NULL || zspan->maxp2==NULL) return;
2487
2488         if (zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
2489         if (zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
2490
2491         if (my2<my0) return;
2492
2493         /* ZBUF DX DY, in floats still */
2494         x1= v1[0]- v2[0];
2495         x2= v2[0]- v3[0];
2496         y1= v1[1]- v2[1];
2497         y2= v2[1]- v3[1];
2498         z1= v1[2]- v2[2];
2499         z2= v2[2]- v3[2];
2500
2501         x0= y1*z2-z1*y2;
2502         y0= z1*x2-x1*z2;
2503         z0= x1*y2-y1*x2;
2504
2505         if (z0==0.0f) return;
2506
2507         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
2508         zxd= -(double)x0/(double)z0;
2509         zyd= -(double)y0/(double)z0;
2510         zy0= ((double)my2)*zyd + (double)xx1;
2511
2512         /* correct span */
2513         sn1= (my0 + my2)/2;
2514         if (zspan->span1[sn1] < zspan->span2[sn1]) {
2515                 span1= zspan->span1+my2;
2516                 span2= zspan->span2+my2;
2517         }
2518         else {
2519                 span1= zspan->span2+my2;
2520                 span2= zspan->span1+my2;
2521         }
2522
2523         for (y=my2; y>=my0; y--, span1--, span2--) {
2524                 sn1= floor(*span1);
2525                 sn2= floor(*span2);
2526                 sn1++;
2527
2528                 if (sn2>=rectx) sn2= rectx-1;
2529                 if (sn1<0) sn1= 0;
2530
2531                 z= (double)sn1*zxd + zy0;
2532
2533                 for (x= sn1; x<=sn2; x++, z+=zxd)
2534                         zspan->sss_func(zspan->sss_handle, obi, zvlnr, x, y, z);
2535
2536                 zy0 -= zyd;
2537         }
2538 }
2539
2540 void zbuffer_sss(RenderPart *pa, unsigned int lay, void *handle, void (*func)(void *, int, int, int, int, int))
2541 {
2542         ZbufProjectCache cache[ZBUF_PROJECT_CACHE_SIZE];
2543         ZSpan zspan;
2544         ObjectInstanceRen *obi;
2545         ObjectRen *obr;
2546         VlakRen *vlr= NULL;
2547         VertRen *v1, *v2, *v3, *v4;
2548         Material *ma = NULL, *sss_ma = R.sss_mat;
2549         float obwinmat[4][4], winmat[4][4], bounds[4];
2550         float ho1[4], ho2[4], ho3[4], ho4[4]={0};
2551         int i, v, zvlnr, c1, c2, c3, c4=0;
2552         short nofill=0, env=0, wire=0;
2553
2554         zbuf_make_winmat(&R, winmat);
2555         zbuffer_part_bounds(R.winx, R.winy, pa, bounds);
2556         zbuf_alloc_span(&zspan, pa->rectx, pa->recty, R.clipcrop);
2557
2558         zspan.sss_handle= handle;
2559         zspan.sss_func= func;
2560
2561         /* needed for transform from hoco to zbuffer co */
2562         zspan.zmulx=  ((float)R.winx)/2.0f;
2563         zspan.zmuly=  ((float)R.winy)/2.0f;
2564
2565         /* -0.5f to center the sample position */
2566         zspan.zofsx= -pa->disprect.xmin - 0.5f;
2567         zspan.zofsy= -pa->disprect.ymin - 0.5f;
2568
2569         /* filling methods */
2570         zspan.zbuffunc= zbuffill_sss;
2571
2572         /* fill front and back zbuffer */
2573         if (pa->rectz) {
2574                 fillrect(pa->recto, pa->rectx, pa->recty, 0);
2575                 fillrect(pa->rectp, pa->rectx, pa->recty, 0);
2576                 fillrect(pa->rectz, pa->rectx, pa->recty, 0x7FFFFFFF);
2577         }
2578         if (pa->rectbackz) {
2579                 fillrect(pa->rectbacko, pa->rectx, pa->recty, 0);
2580                 fillrect(pa->rectbackp, pa->rectx, pa->recty, 0);
2581                 fillrect(pa->rectbackz, pa->rectx, pa->recty, -0x7FFFFFFF);
2582         }
2583
2584         for (i=0, obi=R.instancetable.first; obi; i++, obi=obi->next) {
2585                 obr= obi->obr;
2586
2587                 if (!(obi->lay & lay))
2588                         continue;
2589
2590                 if (obi->flag & R_TRANSFORMED)
2591                         mul_m4_m4m4(obwinmat, winmat, obi->mat);
2592                 else
2593                         copy_m4_m4(obwinmat, winmat);
2594
2595                 if (clip_render_object(obi->obr->boundbox, bounds, obwinmat))
2596                         continue;
2597
2598                 zbuf_project_cache_clear(cache, obr->totvert);
2599
2600                 for (v=0; v<obr->totvlak; v++) {
2601                         if ((v & 255)==0) vlr= obr->vlaknodes[v>>8].vlak;
2602                         else vlr++;
2603
2604                         if (material_in_material(vlr->mat, sss_ma)) {
2605                                 /* three cases, visible for render, only z values and nothing */
2606                                 if (obi->lay & lay) {
2607                                         if (vlr->mat!=ma) {
2608                                                 ma= vlr->mat;
2609                                                 nofill= ma->mode & MA_ONLYCAST;
2610                                                 env= (ma->mode & MA_ENV);
2611                                                 wire= (ma->material_type == MA_TYPE_WIRE);
2612                                         }
2613                                 }
2614                                 else {
2615                                         nofill= 1;
2616                                         ma= NULL;       /* otherwise nofill can hang */
2617                                 }
2618
2619                                 if (nofill==0 && wire==0 && env==0) {
2620                                         unsigned short partclip;
2621
2622                                         v1= vlr->v1;
2623                                         v2= vlr->v2;
2624                                         v3= vlr->v3;
2625                                         v4= vlr->v4;
2626
2627                                         c1= zbuf_part_project(cache, v1->index, obwinmat, bounds, v1->co, ho1);
2628                                         c2= zbuf_part_project(cache, v2->index, obwinmat, bounds, v2->co, ho2);
2629                                         c3= zbuf_part_project(cache, v3->index, obwinmat, bounds, v3->co, ho3);
2630
2631                                         /* partclipping doesn't need viewplane clipping */
2632                                         partclip= c1 & c2 & c3;
2633                                         if (v4) {
2634                                                 c4= zbuf_part_project(cache, v4->index, obwinmat, bounds, v4->co, ho4);
2635                                                 partclip &= c4;
2636                                         }
2637
2638                                         if (partclip==0) {
2639                                                 c1= testclip(ho1);
2640                                                 c2= testclip(ho2);
2641                                                 c3= testclip(ho3);
2642
2643                                                 zvlnr= v+1;
2644                                                 zbufclip(&zspan, i, zvlnr, ho1, ho2, ho3, c1, c2, c3);
2645                                                 if (v4) {
2646                                                         c4= testclip(ho4);
2647                                                         zbufclip(&zspan, i, zvlnr+RE_QUAD_OFFS, ho1, ho3, ho4, c1, c3, c4);
2648                                                 }
2649                                         }
2650                                 }
2651                         }
2652                 }
2653         }
2654
2655         zbuf_free_span(&zspan);
2656 }
2657
2658 /* ******************** VECBLUR ACCUM BUF ************************* */
2659
2660 typedef struct DrawBufPixel {
2661         float *colpoin;
2662         float alpha;
2663 } DrawBufPixel;
2664
2665
2666 static void zbuf_fill_in_rgba(ZSpan *zspan, DrawBufPixel *col, float *v1, float *v2, float *v3, float *v4)
2667 {
2668         DrawBufPixel *rectpofs, *rp;
2669         double zxd, zyd, zy0, zverg;
2670         float x0, y0, z0;
2671         float x1, y1, z1, x2, y2, z2, xx1;
2672         float *span1, *span2;
2673         float *rectzofs, *rz;
2674         int x, y;
2675         int sn1, sn2, rectx, my0, my2;
2676
2677         /* init */
2678         zbuf_init_span(zspan);
2679
2680         /* set spans */
2681         zbuf_add_to_span(zspan, v1, v2);
2682         zbuf_add_to_span(zspan, v2, v3);
2683         zbuf_add_to_span(zspan, v3, v4);
2684         zbuf_add_to_span(zspan, v4, v1);
2685
2686         /* clipped */
2687         if (zspan->minp2==NULL || zspan->maxp2==NULL) return;
2688
2689         if (zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
2690         if (zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
2691
2692         //      printf("my %d %d\n", my0, my2);
2693         if (my2<my0) return;
2694
2695         /* ZBUF DX DY, in floats still */
2696         x1= v1[0]- v2[0];
2697         x2= v2[0]- v3[0];
2698         y1= v1[1]- v2[1];
2699         y2= v2[1]- v3[1];
2700         z1= v1[2]- v2[2];
2701         z2= v2[2]- v3[2];
2702         x0= y1*z2-z1*y2;
2703         y0= z1*x2-x1*z2;
2704         z0= x1*y2-y1*x2;
2705
2706         if (z0==0.0f) return;
2707
2708         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
2709
2710         zxd= -(double)x0/(double)z0;
2711         zyd= -(double)y0/(double)z0;
2712         zy0= ((double)my2)*zyd + (double)xx1;
2713
2714         /* start-offset in rect */
2715         rectx= zspan->rectx;
2716         rectzofs= (float *)(zspan->rectz + rectx*my2);
2717         rectpofs= ((DrawBufPixel *)zspan->rectp) + rectx*my2;
2718
2719         /* correct span */
2720         sn1= (my0 + my2)/2;
2721         if (zspan->span1[sn1] < zspan->span2[sn1]) {
2722                 span1= zspan->span1+my2;
2723                 span2= zspan->span2+my2;
2724         }
2725         else {
2726                 span1= zspan->span2+my2;
2727                 span2= zspan->span1+my2;
2728         }
2729
2730         for (y=my2; y>=my0; y--, span1--, span2--) {
2731
2732                 sn1= floor(*span1);
2733                 sn2= floor(*span2);
2734                 sn1++;
2735
2736                 if (sn2>=rectx) sn2= rectx-1;
2737                 if (sn1<0) sn1= 0;
2738
2739                 if (sn2>=sn1) {
2740                         zverg= (double)sn1*zxd + zy0;
2741                         rz= rectzofs+sn1;
2742                         rp= rectpofs+sn1;
2743                         x= sn2-sn1;
2744
2745                         while (x>=0) {
2746                                 if (zverg < (double)*rz) {
2747                                         *rz= zverg;
2748                                         *rp= *col;
2749                                 }
2750                                 zverg+= zxd;
2751                                 rz++;
2752                                 rp++;
2753                                 x--;
2754                         }
2755                 }
2756
2757                 zy0-=zyd;
2758                 rectzofs-= rectx;
2759                 rectpofs-= rectx;
2760         }
2761 }
2762
2763 /* char value==255 is filled in, rest should be zero */
2764 /* returns alpha values, but sets alpha to 1 for zero alpha pixels that have an alpha value as neighbor */
2765 void antialias_tagbuf(int xsize, int ysize, char *rectmove)
2766 {
2767         char *row1, *row2, *row3;
2768         char prev, next;
2769         int a, x, y, step;
2770
2771         /* 1: tag pixels to be candidate for AA */
2772         for (y=2; y<ysize; y++) {
2773                 /* setup rows */
2774                 row1= rectmove + (y-2)*xsize;
2775                 row2= row1 + xsize;
2776                 row3= row2 + xsize;
2777                 for (x=2; x<xsize; x++, row1++, row2++, row3++) {
2778                         if (row2[1]) {
2779                                 if (row2[0]==0 || row2[2]==0 || row1[1]==0 || row3[1]==0)
2780                                         row2[1]= 128;
2781                         }
2782                 }
2783         }
2784
2785         /* 2: evaluate horizontal scanlines and calculate alphas */
2786         row1= rectmove;
2787         for (y=0; y<ysize; y++) {
2788                 row1++;
2789                 for (x=1; x<xsize; x++, row1++) {
2790                         if (row1[0]==128 && row1[1]==128) {
2791                                 /* find previous color and next color and amount of steps to blend */
2792                                 prev= row1[-1];
2793                                 step= 1;
2794                                 while (x+step<xsize && row1[step]==128)
2795                                         step++;
2796
2797                                 if (x+step!=xsize) {
2798                                         /* now we can blend values */
2799                                         next= row1[step];
2800
2801                                         /* note, prev value can be next value, but we do this loop to clear 128 then */
2802                                         for (a=0; a<step; a++) {
2803                                                 int fac, mfac;
2804
2805                                                 fac= ((a+1)<<8)/(step+1);
2806                                                 mfac= 255-fac;
2807
2808                                                 row1[a]= (prev*mfac + next*fac)>>8;
2809                                         }
2810                                 }
2811                         }
2812                 }
2813         }
2814
2815         /* 3: evaluate vertical scanlines and calculate alphas */
2816         /*    use for reading a copy of the original tagged buffer */
2817         for (x=0; x<xsize; x++) {
2818                 row1= rectmove + x+xsize;
2819
2820                 for (y=1; y<ysize; y++, row1+=xsize) {
2821                         if (row1[0]==128 && row1[xsize]==128) {
2822                                 /* find previous color and next color and amount of steps to blend */
2823                                 prev= row1[-xsize];
2824                                 step= 1;
2825                                 while (y+step<ysize && row1[step*xsize]==128)
2826                                         step++;
2827
2828                                 if (y+step!=ysize) {
2829                                         /* now we can blend values */
2830                                         next= row1[step*xsize];
2831                                         /* note, prev value can be next value, but we do this loop to clear 128 then */
2832                                         for (a=0; a<step; a++) {
2833                                                 int fac, mfac;
2834
2835                                                 fac= ((a+1)<<8)/(step+1);
2836                                                 mfac= 255-fac;
2837
2838                                                 row1[a*xsize]= (prev*mfac + next*fac)>>8;
2839                                         }
2840                                 }
2841                         }
2842                 }
2843         }
2844
2845         /* last: pixels with 0 we fill in zbuffer, with 1 we skip for mask */
2846         for (y=2; y<ysize; y++) {
2847                 /* setup rows */
2848                 row1= rectmove + (y-2)*xsize;
2849                 row2= row1 + xsize;
2850                 row3= row2 + xsize;
2851                 for (x=2; x<xsize; x++, row1++, row2++, row3++) {
2852                         if (row2[1]==0) {
2853                                 if (row2[0]>1 || row2[2]>1 || row1[1]>1 || row3[1]>1)
2854                                         row2[1]= 1;
2855                         }
2856                 }
2857         }
2858 }
2859
2860 /* in: two vectors, first vector points from origin back in time, 2nd vector points to future */
2861 /* we make this into 3 points, center point is (0, 0) */
2862 /* and offset the center point just enough to make curve go through midpoint */
2863
2864 static void quad_bezier_2d(float *result, float *v1, float *v2, float *ipodata)
2865 {
2866         float p1[2], p2[2], p3[2];
2867
2868         p3[0]= -v2[0];
2869         p3[1]= -v2[1];
2870
2871         p1[0]= v1[0];
2872         p1[1]= v1[1];
2873
2874         /* official formula 2*p2 - 0.5*p1 - 0.5*p3 */
2875         p2[0]= -0.5f*p1[0] - 0.5f*p3[0];
2876         p2[1]= -0.5f*p1[1] - 0.5f*p3[1];
2877
2878         result[0]= ipodata[0]*p1[0] + ipodata[1]*p2[0] + ipodata[2]*p3[0];
2879         result[1]= ipodata[0]*p1[1] + ipodata[1]*p2[1] + ipodata[2]*p3[1];
2880 }
2881
2882 static void set_quad_bezier_ipo(float fac, float *data)
2883 {
2884         float mfac= (1.0f-fac);
2885
2886         data[0]= mfac*mfac;
2887         data[1]= 2.0f*mfac*fac;
2888         data[2]= fac*fac;
2889 }
2890
2891 void RE_zbuf_accumulate_vecblur(NodeBlurData *nbd, int xsize, int ysize, float *newrect, float *imgrect, float *vecbufrect, float *zbufrect)
2892 {
2893         ZSpan zspan;
2894         DrawBufPixel *rectdraw, *dr;
2895         static float jit[256][2];
2896         float v1[3], v2[3], v3[3], v4[3], fx, fy;
2897         float *rectvz, *dvz, *dimg, *dvec1, *dvec2, *dz, *dz1, *dz2, *rectz;
2898         float *minvecbufrect= NULL, *rectweight, *rw, *rectmax, *rm, *ro;
2899         float maxspeedsq= (float)nbd->maxspeed*nbd->maxspeed;
2900         int y, x, step, maxspeed=nbd->maxspeed, samples= nbd->samples;
2901         int tsktsk= 0;
2902         static int firsttime= 1;
2903         char *rectmove, *dm;
2904
2905         zbuf_alloc_span(&zspan, xsize, ysize, 1.0f);
2906         zspan.zmulx=  ((float)xsize)/2.0f;
2907         zspan.zmuly=  ((float)ysize)/2.0f;
2908         zspan.zofsx= 0.0f;
2909         zspan.zofsy= 0.0f;
2910
2911         /* the buffers */
2912         rectz= MEM_mapallocN(sizeof(float)*xsize*ysize, "zbuf accum");
2913         zspan.rectz= (int *)rectz;
2914
2915         rectmove= MEM_mapallocN(xsize*ysize, "rectmove");
2916         rectdraw= MEM_mapallocN(sizeof(DrawBufPixel)*xsize*ysize, "rect draw");
2917         zspan.rectp= (int *)rectdraw;
2918
2919         rectweight= MEM_mapallocN(sizeof(float)*xsize*ysize, "rect weight");
2920         rectmax= MEM_mapallocN(sizeof(float)*xsize*ysize, "rect max");
2921
2922         /* debug... check if PASS_VECTOR_MAX still is in buffers */
2923         dvec1= vecbufrect;
2924         for (x= 4*xsize*ysize; x>0; x--, dvec1++) {
2925                 if (dvec1[0]==PASS_VECTOR_MAX) {
2926                         dvec1[0]= 0.0f;
2927                         tsktsk= 1;
2928                 }
2929         }
2930         if (tsktsk) printf("Found uninitialized speed in vector buffer... fixed.\n");
2931
2932         /* min speed? then copy speedbuffer to recalculate speed vectors */
2933         if (nbd->minspeed) {
2934                 float minspeed= (float)nbd->minspeed;
2935                 float minspeedsq= minspeed*minspeed;
2936
2937                 minvecbufrect= MEM_mapallocN(4*sizeof(float)*xsize*ysize, "minspeed buf");
2938
2939                 dvec1= vecbufrect;
2940                 dvec2= minvecbufrect;
2941                 for (x= 2*xsize*ysize; x>0; x--, dvec1+=2, dvec2+=2) {
2942                         if (dvec1[0]==0.0f && dvec1[1]==0.0f) {
2943                                 dvec2[0]= dvec1[0];
2944                                 dvec2[1]= dvec1[1];
2945                         }
2946                         else {
2947                                 float speedsq= dvec1[0]*dvec1[0] + dvec1[1]*dvec1[1];
2948                                 if (speedsq <= minspeedsq) {
2949                                         dvec2[0]= 0.0f;
2950                                         dvec2[1]= 0.0f;
2951                                 }
2952                                 else {
2953                                         speedsq= 1.0f - minspeed/sqrt(speedsq);
2954                                         dvec2[0]= speedsq*dvec1[0];