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