source/blender/render/intern/source/zbuf.c

   1 /**
   2  * $Id$
   3  *
   4  * ***** BEGIN GPL LICENSE BLOCK *****
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License
   8  * as published by the Free Software Foundation; either version 2
   9  * of the License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software Foundation,
  18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  19  *
  20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  21  * All rights reserved.
  22  *
  23  * Contributors: Hos, RPW
  24  *               2004-2006 Blender Foundation, full recode
  25  *
  26  * ***** END GPL LICENSE BLOCK *****
  27  */
  28
  29
  30 /*---------------------------------------------------------------------------*/
  31 /* Common includes                                                           */
  32 /*---------------------------------------------------------------------------*/
  33
  34 #include <math.h>
  35 #include <float.h>
  36 #include <stdlib.h>
  37 #include <limits.h>
  38 #include <string.h>
  39
  40 #include "BLI_blenlib.h"
  41 #include "MTC_matrixops.h"
  42 #include "MEM_guardedalloc.h"
  43
  44 #include "DNA_lamp_types.h"
  45 #include "DNA_mesh_types.h"
  46 #include "DNA_meshdata_types.h"
  47
  48 #include "BKE_global.h"
  49 #include "BKE_utildefines.h"
  50
  51 #include "radio_types.h"
  52 #include "radio.h"  /* needs RG, some root data for radiosity */
  53
  54 #include "SDL_thread.h"
  55
  56 #include "RE_render_ext.h"
  57
  58 /* local includes */
  59 #include "render_types.h"
  60 #include "renderpipeline.h"
  61 #include "renderdatabase.h"
  62 #include "rendercore.h"
  63 #include "pixelblending.h"
  64
  65 /* own includes */
  66 #include "zbuf.h"
  67
  68 /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
  69 /* defined in pipeline.c, is hardcopy of active dynamic allocated Render */
  70 /* only to be used here in this file, it's for speed */
  71 extern struct Render R;
  72 /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
  73
  74
  75 /* ****************** Spans ******************************* */
  76
  77 /* each zbuffer has coordinates transformed to local rect coordinates, so we can simply clip */
  78 void zbuf_alloc_span(ZSpan *zspan, int rectx, int recty)
  79 {
  80         memset(zspan, 0, sizeof(ZSpan));
  81
  82         zspan->rectx= rectx;
  83         zspan->recty= recty;
  84
  85         zspan->span1= RE_mallocN(recty*sizeof(float), "zspan");
  86         zspan->span2= RE_mallocN(recty*sizeof(float), "zspan");
  87 }
  88
  89 static void zbuf_free_span(ZSpan *zspan)
  90 {
  91         if(zspan) {
  92                 if(zspan->span1) RE_freeN(zspan->span1);
  93                 if(zspan->span2) RE_freeN(zspan->span2);
  94                 zspan->span1= zspan->span2= NULL;
  95         }
  96 }
  97
  98 /* reset range for clipping */
  99 static void zbuf_init_span(ZSpan *zspan)
 100 {
 101         zspan->miny1= zspan->miny2= zspan->recty+1;
 102         zspan->maxy1= zspan->maxy2= -1;
 103         zspan->minp1= zspan->maxp1= zspan->minp2= zspan->maxp2= NULL;
 104 }
 105
 106 static void zbuf_add_to_span(ZSpan *zspan, float *v1, float *v2)
 107 {
 108         float *minv, *maxv, *span;
 109         float xx1, dx0, xs0;
 110         int y, my0, my2;
 111
 112         if(v1[1]<v2[1]) {
 113                 minv= v1; maxv= v2;
 114         }
 115         else {
 116                 minv= v2; maxv= v1;
 117         }
 118
 119         my0= ceil(minv[1]);
 120         my2= floor(maxv[1]);
 121
 122         if(my2<0 || my0>= zspan->recty) return;
 123
 124         /* clip top */
 125         if(my2>=zspan->recty) my2= zspan->recty-1;
 126         /* clip bottom */
 127         if(my0<0) my0= 0;
 128
 129         if(my0>my2) return;
 130         /* if(my0>my2) should still fill in, that way we get spans that skip nicely */
 131
 132         xx1= maxv[1]-minv[1];
 133         if(xx1>FLT_EPSILON) {
 134                 dx0= (minv[0]-maxv[0])/xx1;
 135                 xs0= dx0*(minv[1]-my2) + minv[0];
 136         }
 137         else {
 138                 dx0= 0.0f;
 139                 xs0= MIN2(minv[0],maxv[0]);
 140         }
 141
 142         /* empty span */
 143         if(zspan->maxp1 == NULL) {
 144                 span= zspan->span1;
 145         }
 146         else {  /* does it complete left span? */
 147                 if( maxv == zspan->minp1 || minv==zspan->maxp1) {
 148                         span= zspan->span1;
 149                 }
 150                 else {
 151                         span= zspan->span2;
 152                 }
 153         }
 154
 155         if(span==zspan->span1) {
 156 //              printf("left span my0 %d my2 %d\n", my0, my2);
 157                 if(zspan->minp1==NULL || zspan->minp1[1] > minv[1] ) {
 158                         zspan->minp1= minv;
 159                 }
 160                 if(zspan->maxp1==NULL || zspan->maxp1[1] < maxv[1] ) {
 161                         zspan->maxp1= maxv;
 162                 }
 163                 if(my0<zspan->miny1) zspan->miny1= my0;
 164                 if(my2>zspan->maxy1) zspan->maxy1= my2;
 165         }
 166         else {
 167 //              printf("right span my0 %d my2 %d\n", my0, my2);
 168                 if(zspan->minp2==NULL || zspan->minp2[1] > minv[1] ) {
 169                         zspan->minp2= minv;
 170                 }
 171                 if(zspan->maxp2==NULL || zspan->maxp2[1] < maxv[1] ) {
 172                         zspan->maxp2= maxv;
 173                 }
 174                 if(my0<zspan->miny2) zspan->miny2= my0;
 175                 if(my2>zspan->maxy2) zspan->maxy2= my2;
 176         }
 177
 178         for(y=my2; y>=my0; y--, xs0+= dx0) {
 179                 /* xs0 is the xcoord! */
 180                 span[y]= xs0;
 181         }
 182 }
 183
 184 /*-----------------------------------------------------------*/
 185 /* Functions                                                 */
 186 /*-----------------------------------------------------------*/
 187
 188
 189 void fillrect(int *rect, int x, int y, int val)
 190 {
 191         int len, *drect;
 192
 193         len= x*y;
 194         drect= rect;
 195         while(len>0) {
 196                 len--;
 197                 *drect= val;
 198                 drect++;
 199         }
 200 }
 201
 202 /* based on Liang&Barsky, for clipping of pyramidical volume */
 203 static short cliptestf(float p, float q, float *u1, float *u2)
 204 {
 205         float r;
 206
 207         if(p<0.0) {
 208                 if(q<p) return 0;
 209                 else if(q<0.0) {
 210                         r= q/p;
 211                         if(r>*u2) return 0;
 212                         else if(r>*u1) *u1=r;
 213                 }
 214         }
 215         else {
 216                 if(p>0.0) {
 217                         if(q<0.0) return 0;
 218                         else if(q<p) {
 219                                 r= q/p;
 220                                 if(r<*u1) return 0;
 221                                 else if(r<*u2) *u2=r;
 222                         }
 223                 }
 224                 else if(q<0.0) return 0;
 225         }
 226         return 1;
 227 }
 228
 229 int testclip(float *v)
 230 {
 231         float abs4;     /* WATCH IT: this function should do the same as cliptestf, otherwise troubles in zbufclip()*/
 232         short c=0;
 233
 234         /* if we set clip flags, the clipping should be at least larger than epsilon.
 235            prevents issues with vertices lying exact on borders */
 236         abs4= fabs(v[3]) + FLT_EPSILON;
 237
 238         if(v[2]< -abs4) c=16;                   /* this used to be " if(v[2]<0) ", see clippz() */
 239         else if(v[2]> abs4) c+= 32;
 240
 241         if( v[0]>abs4) c+=2;
 242         else if( v[0]< -abs4) c+=1;
 243
 244         if( v[1]>abs4) c+=4;
 245         else if( v[1]< -abs4) c+=8;
 246
 247         return c;
 248 }
 249
 250
 251
 252 /* *************  ACCUMULATION ZBUF ************ */
 253
 254
 255 static APixstr *addpsmainA(ListBase *lb)
 256 {
 257         APixstrMain *psm;
 258
 259         psm= RE_mallocN(sizeof(APixstrMain), "addpsmainA");
 260         BLI_addtail(lb, psm);
 261         psm->ps= RE_mallocN(4096*sizeof(APixstr),"pixstr");
 262
 263         return psm->ps;
 264 }
 265
 266 static void freepsA(ListBase *lb)
 267 {
 268         APixstrMain *psm, *psmnext;
 269
 270         for(psm= lb->first; psm; psm= psmnext) {
 271                 psmnext= psm->next;
 272                 if(psm->ps)
 273                         RE_freeN(psm->ps);
 274                 RE_freeN(psm);
 275         }
 276 }
 277
 278 static APixstr *addpsA(ZSpan *zspan)
 279 {
 280         /* make new PS */
 281         if(zspan->apsmcounter==0) {
 282                 zspan->curpstr= addpsmainA(zspan->apsmbase);
 283                 zspan->apsmcounter= 4095;
 284         }
 285         else {
 286                 zspan->curpstr++;
 287                 zspan->apsmcounter--;
 288         }
 289         return zspan->curpstr;
 290 }
 291
 292 static void zbufinvulAc4(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4)
 293 {
 294         APixstr *ap, *apofs, *apn;
 295         double zxd, zyd, zy0, zverg;
 296         float x0,y0,z0;
 297         float x1,y1,z1,x2,y2,z2,xx1;
 298         float *span1, *span2;
 299         int *rz, x, y;
 300         int sn1, sn2, rectx, *rectzofs, my0, my2, mask;
 301
 302         /* init */
 303         zbuf_init_span(zspan);
 304
 305         /* set spans */
 306         zbuf_add_to_span(zspan, v1, v2);
 307         zbuf_add_to_span(zspan, v2, v3);
 308         if(v4) {
 309                 zbuf_add_to_span(zspan, v3, v4);
 310                 zbuf_add_to_span(zspan, v4, v1);
 311         }
 312         else
 313                 zbuf_add_to_span(zspan, v3, v1);
 314
 315         /* clipped */
 316         if(zspan->minp2==NULL || zspan->maxp2==NULL) return;
 317
 318         if(zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
 319         if(zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
 320
 321         if(my2<my0) return;
 322
 323         /* ZBUF DX DY, in floats still */
 324         x1= v1[0]- v2[0];
 325         x2= v2[0]- v3[0];
 326         y1= v1[1]- v2[1];
 327         y2= v2[1]- v3[1];
 328         z1= v1[2]- v2[2];
 329         z2= v2[2]- v3[2];
 330         x0= y1*z2-z1*y2;
 331         y0= z1*x2-x1*z2;
 332         z0= x1*y2-y1*x2;
 333
 334         if(z0==0.0) return;
 335
 336         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
 337
 338         zxd= -(double)x0/(double)z0;
 339         zyd= -(double)y0/(double)z0;
 340         zy0= ((double)my2)*zyd + (double)xx1;
 341
 342         /* start-offset in rect */
 343         rectx= zspan->rectx;
 344         rectzofs= (int *)(zspan->arectz+rectx*(my2));
 345         apofs= (zspan->apixbuf+ rectx*(my2));
 346         mask= zspan->mask;
 347
 348         /* correct span */
 349         sn1= (my0 + my2)/2;
 350         if(zspan->span1[sn1] < zspan->span2[sn1]) {
 351                 span1= zspan->span1+my2;
 352                 span2= zspan->span2+my2;
 353         }
 354         else {
 355                 span1= zspan->span2+my2;
 356                 span2= zspan->span1+my2;
 357         }
 358
 359         for(y=my2; y>=my0; y--, span1--, span2--) {
 360
 361                 sn1= floor(*span1);
 362                 sn2= floor(*span2);
 363                 sn1++;
 364
 365                 if(sn2>=rectx) sn2= rectx-1;
 366                 if(sn1<0) sn1= 0;
 367
 368                 if(sn2>=sn1) {
 369                         zverg= (double)sn1*zxd + zy0;
 370                         rz= rectzofs+sn1;
 371                         ap= apofs+sn1;
 372                         x= sn2-sn1;
 373
 374                         zverg-= zspan->polygon_offset;
 375
 376                         while(x>=0) {
 377                                 if( (int)zverg < *rz) {
 378 //                                      int i= zvlnr & 3;
 379
 380                                         apn= ap;
 381                                         while(apn) {
 382                                                 if(apn->p[0]==0) {apn->p[0]= zvlnr; apn->z[0]= zverg; apn->mask[0]= mask; break; }
 383                                                 if(apn->p[0]==zvlnr) {apn->mask[0]|= mask; break; }
 384                                                 if(apn->p[1]==0) {apn->p[1]= zvlnr; apn->z[1]= zverg; apn->mask[1]= mask; break; }
 385                                                 if(apn->p[1]==zvlnr) {apn->mask[1]|= mask; break; }
 386                                                 if(apn->p[2]==0) {apn->p[2]= zvlnr; apn->z[2]= zverg; apn->mask[2]= mask; break; }
 387                                                 if(apn->p[2]==zvlnr) {apn->mask[2]|= mask; break; }
 388                                                 if(apn->p[3]==0) {apn->p[3]= zvlnr; apn->z[3]= zverg; apn->mask[3]= mask; break; }
 389                                                 if(apn->p[3]==zvlnr) {apn->mask[3]|= mask; break; }
 390 //                                              if(apn->p[i]==0) {apn->p[i]= zvlnr; apn->z[i]= zverg; apn->mask[i]= mask; break; }
 391 //                                              if(apn->p[i]==zvlnr) {apn->mask[i]|= mask; break; }
 392                                                 if(apn->next==NULL) apn->next= addpsA(zspan);
 393                                                 apn= apn->next;
 394                                         }
 395                                 }
 396                                 zverg+= zxd;
 397                                 rz++;
 398                                 ap++;
 399                                 x--;
 400                         }
 401                 }
 402
 403                 zy0-=zyd;
 404                 rectzofs-= rectx;
 405                 apofs-= rectx;
 406         }
 407 }
 408
 409
 410
 411 static void zbuflineAc(ZSpan *zspan, int zvlnr, float *vec1, float *vec2)
 412 {
 413         APixstr *ap, *apn;
 414         int *rectz;
 415         int start, end, x, y, oldx, oldy, ofs;
 416         int dz, vergz, mask, maxtest=0;
 417         float dx, dy;
 418         float v1[3], v2[3];
 419
 420         dx= vec2[0]-vec1[0];
 421         dy= vec2[1]-vec1[1];
 422
 423         mask= zspan->mask;
 424
 425         if(fabs(dx) > fabs(dy)) {
 426
 427                 /* all lines from left to right */
 428                 if(vec1[0]<vec2[0]) {
 429                         VECCOPY(v1, vec1);
 430                         VECCOPY(v2, vec2);
 431                 }
 432                 else {
 433                         VECCOPY(v2, vec1);
 434                         VECCOPY(v1, vec2);
 435                         dx= -dx; dy= -dy;
 436                 }
 437
 438                 start= floor(v1[0]);
 439                 end= start+floor(dx);
 440                 if(end>=zspan->rectx) end= zspan->rectx-1;
 441
 442                 oldy= floor(v1[1]);
 443                 dy/= dx;
 444
 445                 vergz= v1[2];
 446                 vergz-= zspan->polygon_offset;
 447                 dz= (v2[2]-v1[2])/dx;
 448                 if(vergz>0x50000000 && dz>0) maxtest= 1;                // prevent overflow
 449
 450                 rectz= (int *)(zspan->arectz+zspan->rectx*(oldy) +start);
 451                 ap= (zspan->apixbuf+ zspan->rectx*(oldy) +start);
 452
 453                 if(dy<0) ofs= -zspan->rectx;
 454                 else ofs= zspan->rectx;
 455
 456                 for(x= start; x<=end; x++, rectz++, ap++) {
 457
 458                         y= floor(v1[1]);
 459                         if(y!=oldy) {
 460                                 oldy= y;
 461                                 rectz+= ofs;
 462                                 ap+= ofs;
 463                         }
 464
 465                         if(x>=0 && y>=0 && y<zspan->recty) {
 466                                 if(vergz<*rectz) {
 467
 468                                         apn= ap;
 469                                         while(apn) {    /* loop unrolled */
 470                                                 if(apn->p[0]==0) {apn->p[0]= zvlnr; apn->z[0]= vergz; apn->mask[0]= mask; break; }
 471                                                 if(apn->p[0]==zvlnr) {apn->mask[0]|= mask; break; }
 472                                                 if(apn->p[1]==0) {apn->p[1]= zvlnr; apn->z[1]= vergz; apn->mask[1]= mask; break; }
 473                                                 if(apn->p[1]==zvlnr) {apn->mask[1]|= mask; break; }
 474                                                 if(apn->p[2]==0) {apn->p[2]= zvlnr; apn->z[2]= vergz; apn->mask[2]= mask; break; }
 475                                                 if(apn->p[2]==zvlnr) {apn->mask[2]|= mask; break; }
 476                                                 if(apn->p[3]==0) {apn->p[3]= zvlnr; apn->z[3]= vergz; apn->mask[3]= mask; break; }
 477                                                 if(apn->p[3]==zvlnr) {apn->mask[3]|= mask; break; }
 478                                                 if(apn->next==0) apn->next= addpsA(zspan);
 479                                                 apn= apn->next;
 480                                         }
 481
 482                                 }
 483                         }
 484
 485                         v1[1]+= dy;
 486                         if(maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 487                         else vergz+= dz;
 488                 }
 489         }
 490         else {
 491
 492                 /* all lines from top to bottom */
 493                 if(vec1[1]<vec2[1]) {
 494                         VECCOPY(v1, vec1);
 495                         VECCOPY(v2, vec2);
 496                 }
 497                 else {
 498                         VECCOPY(v2, vec1);
 499                         VECCOPY(v1, vec2);
 500                         dx= -dx; dy= -dy;
 501                 }
 502
 503                 start= floor(v1[1]);
 504                 end= start+floor(dy);
 505
 506                 if(start>=zspan->recty || end<0) return;
 507
 508                 if(end>=zspan->recty) end= zspan->recty-1;
 509
 510                 oldx= floor(v1[0]);
 511                 dx/= dy;
 512
 513                 vergz= v1[2];
 514                 vergz-= zspan->polygon_offset;
 515                 dz= (v2[2]-v1[2])/dy;
 516                 if(vergz>0x50000000 && dz>0) maxtest= 1;                // prevent overflow
 517
 518                 rectz= (int *)( zspan->arectz+ (start)*zspan->rectx+ oldx );
 519                 ap= (zspan->apixbuf+ zspan->rectx*(start) +oldx);
 520
 521                 if(dx<0) ofs= -1;
 522                 else ofs= 1;
 523
 524                 for(y= start; y<=end; y++, rectz+=zspan->rectx, ap+=zspan->rectx) {
 525
 526                         x= floor(v1[0]);
 527                         if(x!=oldx) {
 528                                 oldx= x;
 529                                 rectz+= ofs;
 530                                 ap+= ofs;
 531                         }
 532
 533                         if(x>=0 && y>=0 && x<zspan->rectx) {
 534                                 if(vergz<*rectz) {
 535
 536                                         apn= ap;
 537                                         while(apn) {    /* loop unrolled */
 538                                                 if(apn->p[0]==0) {apn->p[0]= zvlnr; apn->z[0]= vergz; apn->mask[0]= mask; break; }
 539                                                 if(apn->p[0]==zvlnr) {apn->mask[0]|= mask; break; }
 540                                                 if(apn->p[1]==0) {apn->p[1]= zvlnr; apn->z[1]= vergz; apn->mask[1]= mask; break; }
 541                                                 if(apn->p[1]==zvlnr) {apn->mask[1]|= mask; break; }
 542                                                 if(apn->p[2]==0) {apn->p[2]= zvlnr; apn->z[2]= vergz; apn->mask[2]= mask; break; }
 543                                                 if(apn->p[2]==zvlnr) {apn->mask[2]|= mask; break; }
 544                                                 if(apn->p[3]==0) {apn->p[3]= zvlnr; apn->z[3]= vergz; apn->mask[3]= mask; break; }
 545                                                 if(apn->p[3]==zvlnr) {apn->mask[3]|= mask; break; }
 546                                                 if(apn->next==0) apn->next= addpsA(zspan);
 547                                                 apn= apn->next;
 548                                         }
 549
 550                                 }
 551                         }
 552
 553                         v1[0]+= dx;
 554                         if(maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 555                         else vergz+= dz;
 556                 }
 557         }
 558 }
 559
 560 /* *************  NORMAL ZBUFFER ************ */
 561
 562 static void zbufline(ZSpan *zspan, int zvlnr, float *vec1, float *vec2)
 563 {
 564         int *rectz, *rectp;
 565         int start, end, x, y, oldx, oldy, ofs;
 566         int dz, vergz, maxtest= 0;
 567         float dx, dy;
 568         float v1[3], v2[3];
 569
 570         dx= vec2[0]-vec1[0];
 571         dy= vec2[1]-vec1[1];
 572
 573         if(fabs(dx) > fabs(dy)) {
 574
 575                 /* all lines from left to right */
 576                 if(vec1[0]<vec2[0]) {
 577                         VECCOPY(v1, vec1);
 578                         VECCOPY(v2, vec2);
 579                 }
 580                 else {
 581                         VECCOPY(v2, vec1);
 582                         VECCOPY(v1, vec2);
 583                         dx= -dx; dy= -dy;
 584                 }
 585
 586                 start= floor(v1[0]);
 587                 end= start+floor(dx);
 588                 if(end>=zspan->rectx) end= zspan->rectx-1;
 589
 590                 oldy= floor(v1[1]);
 591                 dy/= dx;
 592
 593                 vergz= floor(v1[2]);
 594                 dz= floor((v2[2]-v1[2])/dx);
 595                 if(vergz>0x50000000 && dz>0) maxtest= 1;                // prevent overflow
 596
 597                 rectz= zspan->rectz + oldy*zspan->rectx+ start;
 598                 rectp= zspan->rectp + oldy*zspan->rectx+ start;
 599
 600                 if(dy<0) ofs= -zspan->rectx;
 601                 else ofs= zspan->rectx;
 602
 603                 for(x= start; x<=end; x++, rectz++, rectp++) {
 604
 605                         y= floor(v1[1]);
 606                         if(y!=oldy) {
 607                                 oldy= y;
 608                                 rectz+= ofs;
 609                                 rectp+= ofs;
 610                         }
 611
 612                         if(x>=0 && y>=0 && y<zspan->recty) {
 613                                 if(vergz<*rectz) {
 614                                         *rectz= vergz;
 615                                         *rectp= zvlnr;
 616                                 }
 617                         }
 618
 619                         v1[1]+= dy;
 620
 621                         if(maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 622                         else vergz+= dz;
 623                 }
 624         }
 625         else {
 626                 /* all lines from top to bottom */
 627                 if(vec1[1]<vec2[1]) {
 628                         VECCOPY(v1, vec1);
 629                         VECCOPY(v2, vec2);
 630                 }
 631                 else {
 632                         VECCOPY(v2, vec1);
 633                         VECCOPY(v1, vec2);
 634                         dx= -dx; dy= -dy;
 635                 }
 636
 637                 start= floor(v1[1]);
 638                 end= start+floor(dy);
 639
 640                 if(end>=zspan->recty) end= zspan->recty-1;
 641
 642                 oldx= floor(v1[0]);
 643                 dx/= dy;
 644
 645                 vergz= floor(v1[2]);
 646                 dz= floor((v2[2]-v1[2])/dy);
 647                 if(vergz>0x50000000 && dz>0) maxtest= 1;                // prevent overflow
 648
 649                 rectz= zspan->rectz + start*zspan->rectx+ oldx;
 650                 rectp= zspan->rectp + start*zspan->rectx+ oldx;
 651
 652                 if(dx<0) ofs= -1;
 653                 else ofs= 1;
 654
 655                 for(y= start; y<=end; y++, rectz+=zspan->rectx, rectp+=zspan->rectx) {
 656
 657                         x= floor(v1[0]);
 658                         if(x!=oldx) {
 659                                 oldx= x;
 660                                 rectz+= ofs;
 661                                 rectp+= ofs;
 662                         }
 663
 664                         if(x>=0 && y>=0 && x<zspan->rectx) {
 665                                 if(vergz<*rectz) {
 666                                         *rectz= vergz;
 667                                         *rectp= zvlnr;
 668                                 }
 669                         }
 670
 671                         v1[0]+= dx;
 672                         if(maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 673                         else vergz+= dz;
 674                 }
 675         }
 676 }
 677
 678 static void zbufline_onlyZ(ZSpan *zspan, int zvlnr, float *vec1, float *vec2)
 679 {
 680         int *rectz;
 681         int start, end, x, y, oldx, oldy, ofs;
 682         int dz, vergz, maxtest= 0;
 683         float dx, dy;
 684         float v1[3], v2[3];
 685
 686         dx= vec2[0]-vec1[0];
 687         dy= vec2[1]-vec1[1];
 688
 689         if(fabs(dx) > fabs(dy)) {
 690
 691                 /* all lines from left to right */
 692                 if(vec1[0]<vec2[0]) {
 693                         VECCOPY(v1, vec1);
 694                         VECCOPY(v2, vec2);
 695                 }
 696                 else {
 697                         VECCOPY(v2, vec1);
 698                         VECCOPY(v1, vec2);
 699                         dx= -dx; dy= -dy;
 700                 }
 701
 702                 start= floor(v1[0]);
 703                 end= start+floor(dx);
 704                 if(end>=zspan->rectx) end= zspan->rectx-1;
 705
 706                 oldy= floor(v1[1]);
 707                 dy/= dx;
 708
 709                 vergz= floor(v1[2]);
 710                 dz= floor((v2[2]-v1[2])/dx);
 711                 if(vergz>0x50000000 && dz>0) maxtest= 1;                // prevent overflow
 712
 713                 rectz= zspan->rectz + oldy*zspan->rectx+ start;
 714
 715                 if(dy<0) ofs= -zspan->rectx;
 716                 else ofs= zspan->rectx;
 717
 718                 for(x= start; x<=end; x++, rectz++) {
 719
 720                         y= floor(v1[1]);
 721                         if(y!=oldy) {
 722                                 oldy= y;
 723                                 rectz+= ofs;
 724                         }
 725
 726                         if(x>=0 && y>=0 && y<zspan->recty) {
 727                                 if(vergz<*rectz) {
 728                                         *rectz= vergz;
 729                                 }
 730                         }
 731
 732                         v1[1]+= dy;
 733
 734                         if(maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 735                         else vergz+= dz;
 736                 }
 737         }
 738         else {
 739                 /* all lines from top to bottom */
 740                 if(vec1[1]<vec2[1]) {
 741                         VECCOPY(v1, vec1);
 742                         VECCOPY(v2, vec2);
 743                 }
 744                 else {
 745                         VECCOPY(v2, vec1);
 746                         VECCOPY(v1, vec2);
 747                         dx= -dx; dy= -dy;
 748                 }
 749
 750                 start= floor(v1[1]);
 751                 end= start+floor(dy);
 752
 753                 if(end>=zspan->recty) end= zspan->recty-1;
 754
 755                 oldx= floor(v1[0]);
 756                 dx/= dy;
 757
 758                 vergz= floor(v1[2]);
 759                 dz= floor((v2[2]-v1[2])/dy);
 760                 if(vergz>0x50000000 && dz>0) maxtest= 1;                // prevent overflow
 761
 762                 rectz= zspan->rectz + start*zspan->rectx+ oldx;
 763
 764                 if(dx<0) ofs= -1;
 765                 else ofs= 1;
 766
 767                 for(y= start; y<=end; y++, rectz+=zspan->rectx) {
 768
 769                         x= floor(v1[0]);
 770                         if(x!=oldx) {
 771                                 oldx= x;
 772                                 rectz+= ofs;
 773                         }
 774
 775                         if(x>=0 && y>=0 && x<zspan->rectx) {
 776                                 if(vergz<*rectz) {
 777                                         *rectz= vergz;
 778                                 }
 779                         }
 780
 781                         v1[0]+= dx;
 782                         if(maxtest && (vergz > 0x7FFFFFF0 - dz)) vergz= 0x7FFFFFF0;
 783                         else vergz+= dz;
 784                 }
 785         }
 786 }
 787
 788
 789 static int clipline(float *v1, float *v2)       /* return 0: do not draw */
 790 {
 791         float dz,dw, u1=0.0, u2=1.0;
 792         float dx, dy, v13;
 793
 794         dz= v2[2]-v1[2];
 795         dw= v2[3]-v1[3];
 796
 797         /* this 1.01 is for clipping x and y just a tinsy larger. that way it is
 798                 filled in with zbufwire correctly when rendering in parts. otherwise
 799                 you see line endings at edges... */
 800
 801         if(cliptestf(-dz-dw, v1[3]+v1[2], &u1,&u2)) {
 802                 if(cliptestf(dz-dw, v1[3]-v1[2], &u1,&u2)) {
 803
 804                         dx= v2[0]-v1[0];
 805                         dz= 1.01*(v2[3]-v1[3]);
 806                         v13= 1.01*v1[3];
 807
 808                         if(cliptestf(-dx-dz, v1[0]+v13, &u1,&u2)) {
 809                                 if(cliptestf(dx-dz, v13-v1[0], &u1,&u2)) {
 810
 811                                         dy= v2[1]-v1[1];
 812
 813                                         if(cliptestf(-dy-dz, v1[1]+v13, &u1,&u2)) {
 814                                                 if(cliptestf(dy-dz, v13-v1[1], &u1,&u2)) {
 815
 816                                                         if(u2<1.0) {
 817                                                                 v2[0]= v1[0]+u2*dx;
 818                                                                 v2[1]= v1[1]+u2*dy;
 819                                                                 v2[2]= v1[2]+u2*dz;
 820                                                                 v2[3]= v1[3]+u2*dw;
 821                                                         }
 822                                                         if(u1>0.0) {
 823                                                                 v1[0]= v1[0]+u1*dx;
 824                                                                 v1[1]= v1[1]+u1*dy;
 825                                                                 v1[2]= v1[2]+u1*dz;
 826                                                                 v1[3]= v1[3]+u1*dw;
 827                                                         }
 828                                                         return 1;
 829                                                 }
 830                                         }
 831                                 }
 832                         }
 833                 }
 834         }
 835
 836         return 0;
 837 }
 838
 839 static void hoco_to_zco(ZSpan *zspan, float *zco, float *hoco)
 840 {
 841         float div;
 842
 843         div= 1.0f/hoco[3];
 844         zco[0]= zspan->zmulx*(1.0+hoco[0]*div) + zspan->zofsx;
 845         zco[1]= zspan->zmuly*(1.0+hoco[1]*div) + zspan->zofsy;
 846         zco[2]= 0x7FFFFFFF *(hoco[2]*div);
 847 }
 848
 849 void zbufclipwire(ZSpan *zspan, int zvlnr, VlakRen *vlr)
 850 {
 851         float vez[20], *f1, *f2, *f3, *f4= 0;
 852         int c1, c2, c3, c4, ec, and, or;
 853
 854         /* edgecode: 1= draw */
 855         ec = vlr->ec;
 856         if(ec==0) return;
 857
 858         c1= vlr->v1->clip;
 859         c2= vlr->v2->clip;
 860         c3= vlr->v3->clip;
 861         f1= vlr->v1->ho;
 862         f2= vlr->v2->ho;
 863         f3= vlr->v3->ho;
 864
 865         if(vlr->v4) {
 866                 f4= vlr->v4->ho;
 867                 c4= vlr->v4->clip;
 868
 869                 and= (c1 & c2 & c3 & c4);
 870                 or= (c1 | c2 | c3 | c4);
 871         }
 872         else {
 873                 and= (c1 & c2 & c3);
 874                 or= (c1 | c2 | c3);
 875         }
 876
 877         if(or) {        /* not in the middle */
 878                 if(and) {       /* out completely */
 879                         return;
 880                 }
 881                 else {  /* clipping */
 882
 883                         if(ec & ME_V1V2) {
 884                                 QUATCOPY(vez, f1);
 885                                 QUATCOPY(vez+4, f2);
 886                                 if( clipline(vez, vez+4)) {
 887                                         hoco_to_zco(zspan, vez, vez);
 888                                         hoco_to_zco(zspan, vez+4, vez+4);
 889                                         zspan->zbuflinefunc(zspan, zvlnr, vez, vez+4);
 890                                 }
 891                         }
 892                         if(ec & ME_V2V3) {
 893                                 QUATCOPY(vez, f2);
 894                                 QUATCOPY(vez+4, f3);
 895                                 if( clipline(vez, vez+4)) {
 896                                         hoco_to_zco(zspan, vez, vez);
 897                                         hoco_to_zco(zspan, vez+4, vez+4);
 898                                         zspan->zbuflinefunc(zspan, zvlnr, vez, vez+4);
 899                                 }
 900                         }
 901                         if(vlr->v4) {
 902                                 if(ec & ME_V3V4) {
 903                                         QUATCOPY(vez, f3);
 904                                         QUATCOPY(vez+4, f4);
 905                                         if( clipline(vez, vez+4)) {
 906                                                 hoco_to_zco(zspan, vez, vez);
 907                                                 hoco_to_zco(zspan, vez+4, vez+4);
 908                                                 zspan->zbuflinefunc(zspan, zvlnr, vez, vez+4);
 909                                         }
 910                                 }
 911                                 if(ec & ME_V4V1) {
 912                                         QUATCOPY(vez, f4);
 913                                         QUATCOPY(vez+4, f1);
 914                                         if( clipline(vez, vez+4)) {
 915                                                 hoco_to_zco(zspan, vez, vez);
 916                                                 hoco_to_zco(zspan, vez+4, vez+4);
 917                                                 zspan->zbuflinefunc(zspan, zvlnr, vez, vez+4);
 918                                         }
 919                                 }
 920                         }
 921                         else {
 922                                 if(ec & ME_V3V1) {
 923                                         QUATCOPY(vez, f3);
 924                                         QUATCOPY(vez+4, f1);
 925                                         if( clipline(vez, vez+4)) {
 926                                                 hoco_to_zco(zspan, vez, vez);
 927                                                 hoco_to_zco(zspan, vez+4, vez+4);
 928                                                 zspan->zbuflinefunc(zspan, zvlnr, vez, vez+4);
 929                                         }
 930                                 }
 931                         }
 932
 933                         return;
 934                 }
 935         }
 936
 937         hoco_to_zco(zspan, vez, f1);
 938         hoco_to_zco(zspan, vez+4, f2);
 939         hoco_to_zco(zspan, vez+8, f3);
 940         if(vlr->v4) {
 941                 hoco_to_zco(zspan, vez+12, f4);
 942
 943                 if(ec & ME_V3V4)  zspan->zbuflinefunc(zspan, zvlnr, vez+8, vez+12);
 944                 if(ec & ME_V4V1)  zspan->zbuflinefunc(zspan, zvlnr, vez+12, vez);
 945         }
 946         else {
 947                 if(ec & ME_V3V1)  zspan->zbuflinefunc(zspan, zvlnr, vez+8, vez);
 948         }
 949
 950         if(ec & ME_V1V2)  zspan->zbuflinefunc(zspan, zvlnr, vez, vez+4);
 951         if(ec & ME_V2V3)  zspan->zbuflinefunc(zspan, zvlnr, vez+4, vez+8);
 952
 953 }
 954
 955 /**
 956  * Fill the z buffer, but invert z order, and add the face index to
 957  * the corresponing face buffer.
 958  *
 959  * This is one of the z buffer fill functions called in zbufclip() and
 960  * zbufwireclip().
 961  *
 962  * @param v1 [4 floats, world coordinates] first vertex
 963  * @param v2 [4 floats, world coordinates] second vertex
 964  * @param v3 [4 floats, world coordinates] third vertex
 965  */
 966 static void zbufinvulGLinv4(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4)
 967 {
 968         double zxd, zyd, zy0, zverg;
 969         float x0,y0,z0;
 970         float x1,y1,z1,x2,y2,z2,xx1;
 971         float *span1, *span2;
 972         int *rectpofs, *rp;
 973         int *rz, x, y;
 974         int sn1, sn2, rectx, *rectzofs, my0, my2;
 975
 976         /* init */
 977         zbuf_init_span(zspan);
 978
 979         /* set spans */
 980         zbuf_add_to_span(zspan, v1, v2);
 981         zbuf_add_to_span(zspan, v2, v3);
 982         if(v4) {
 983                 zbuf_add_to_span(zspan, v3, v4);
 984                 zbuf_add_to_span(zspan, v4, v1);
 985         }
 986         else
 987                 zbuf_add_to_span(zspan, v3, v1);
 988
 989         /* clipped */
 990         if(zspan->minp2==NULL || zspan->maxp2==NULL) return;
 991
 992         if(zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
 993         if(zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
 994
 995         //      printf("my %d %d\n", my0, my2);
 996         if(my2<my0) return;
 997
 998
 999         /* ZBUF DX DY, in floats still */
1000         x1= v1[0]- v2[0];
1001         x2= v2[0]- v3[0];
1002         y1= v1[1]- v2[1];
1003         y2= v2[1]- v3[1];
1004         z1= v1[2]- v2[2];
1005         z2= v2[2]- v3[2];
1006         x0= y1*z2-z1*y2;
1007         y0= z1*x2-x1*z2;
1008         z0= x1*y2-y1*x2;
1009
1010         if(z0==0.0) return;
1011
1012         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
1013
1014         zxd= -(double)x0/(double)z0;
1015         zyd= -(double)y0/(double)z0;
1016         zy0= ((double)my2)*zyd + (double)xx1;
1017
1018         /* start-offset in rect */
1019         rectx= zspan->rectx;
1020         rectzofs= (zspan->rectz+rectx*my2);
1021         rectpofs= (zspan->rectp+rectx*my2);
1022
1023         /* correct span */
1024         sn1= (my0 + my2)/2;
1025         if(zspan->span1[sn1] < zspan->span2[sn1]) {
1026                 span1= zspan->span1+my2;
1027                 span2= zspan->span2+my2;
1028         }
1029         else {
1030                 span1= zspan->span2+my2;
1031                 span2= zspan->span1+my2;
1032         }
1033
1034         for(y=my2; y>=my0; y--, span1--, span2--) {
1035
1036                 sn1= floor(*span1);
1037                 sn2= floor(*span2);
1038                 sn1++;
1039
1040                 if(sn2>=rectx) sn2= rectx-1;
1041                 if(sn1<0) sn1= 0;
1042
1043                 if(sn2>=sn1) {
1044                         zverg= (double)sn1*zxd + zy0;
1045                         rz= rectzofs+sn1;
1046                         rp= rectpofs+sn1;
1047                         x= sn2-sn1;
1048
1049                         while(x>=0) {
1050                                 if( (int)zverg > *rz || *rz==0x7FFFFFFF) {
1051                                         *rz= (int)zverg;
1052                                         *rp= zvlnr;
1053                                 }
1054                                 zverg+= zxd;
1055                                 rz++;
1056                                 rp++;
1057                                 x--;
1058                         }
1059                 }
1060
1061                 zy0-=zyd;
1062                 rectzofs-= rectx;
1063                 rectpofs-= rectx;
1064         }
1065 }
1066
1067 /* uses spanbuffers */
1068
1069 static void zbufinvulGL4(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4)
1070 {
1071         double zxd, zyd, zy0, zverg;
1072         float x0,y0,z0;
1073         float x1,y1,z1,x2,y2,z2,xx1;
1074         float *span1, *span2;
1075         int *rectpofs, *rp;
1076         int *rz, x, y;
1077         int sn1, sn2, rectx, *rectzofs, my0, my2;
1078
1079         /* init */
1080         zbuf_init_span(zspan);
1081
1082         /* set spans */
1083         zbuf_add_to_span(zspan, v1, v2);
1084         zbuf_add_to_span(zspan, v2, v3);
1085         if(v4) {
1086                 zbuf_add_to_span(zspan, v3, v4);
1087                 zbuf_add_to_span(zspan, v4, v1);
1088         }
1089         else
1090                 zbuf_add_to_span(zspan, v3, v1);
1091
1092         /* clipped */
1093         if(zspan->minp2==NULL || zspan->maxp2==NULL) return;
1094
1095         if(zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
1096         if(zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
1097
1098 //      printf("my %d %d\n", my0, my2);
1099         if(my2<my0) return;
1100
1101
1102         /* ZBUF DX DY, in floats still */
1103         x1= v1[0]- v2[0];
1104         x2= v2[0]- v3[0];
1105         y1= v1[1]- v2[1];
1106         y2= v2[1]- v3[1];
1107         z1= v1[2]- v2[2];
1108         z2= v2[2]- v3[2];
1109         x0= y1*z2-z1*y2;
1110         y0= z1*x2-x1*z2;
1111         z0= x1*y2-y1*x2;
1112
1113         if(z0==0.0) return;
1114
1115         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
1116
1117         zxd= -(double)x0/(double)z0;
1118         zyd= -(double)y0/(double)z0;
1119         zy0= ((double)my2)*zyd + (double)xx1;
1120
1121         /* start-offset in rect */
1122         rectx= zspan->rectx;
1123         rectzofs= (zspan->rectz+rectx*my2);
1124         rectpofs= (zspan->rectp+rectx*my2);
1125
1126         /* correct span */
1127         sn1= (my0 + my2)/2;
1128         if(zspan->span1[sn1] < zspan->span2[sn1]) {
1129                 span1= zspan->span1+my2;
1130                 span2= zspan->span2+my2;
1131         }
1132         else {
1133                 span1= zspan->span2+my2;
1134                 span2= zspan->span1+my2;
1135         }
1136
1137         for(y=my2; y>=my0; y--, span1--, span2--) {
1138
1139                 sn1= floor(*span1);
1140                 sn2= floor(*span2);
1141                 sn1++;
1142
1143                 if(sn2>=rectx) sn2= rectx-1;
1144                 if(sn1<0) sn1= 0;
1145
1146                 if(sn2>=sn1) {
1147                         zverg= (double)sn1*zxd + zy0;
1148                         rz= rectzofs+sn1;
1149                         rp= rectpofs+sn1;
1150                         x= sn2-sn1;
1151
1152                         while(x>=0) {
1153                                 if( (int)zverg < *rz) {
1154                                         *rz= (int)zverg;
1155                                         *rp= zvlnr;
1156                                 }
1157                                 zverg+= zxd;
1158                                 rz++;
1159                                 rp++;
1160                                 x--;
1161                         }
1162                 }
1163
1164                 zy0-=zyd;
1165                 rectzofs-= rectx;
1166                 rectpofs-= rectx;
1167         }
1168 }
1169
1170 /**
1171  * Fill the z buffer. The face buffer is not operated on!
1172  *
1173  * This is one of the z buffer fill functions called in zbufclip() and
1174  * zbufwireclip().
1175  *
1176  * @param v1 [4 floats, world coordinates] first vertex
1177  * @param v2 [4 floats, world coordinates] second vertex
1178  * @param v3 [4 floats, world coordinates] third vertex
1179  */
1180
1181 static void zbufinvulGL_onlyZ(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4)
1182 {
1183         double zxd, zyd, zy0, zverg;
1184         float x0,y0,z0;
1185         float x1,y1,z1,x2,y2,z2,xx1;
1186         float *span1, *span2;
1187         int *rz, x, y;
1188         int sn1, sn2, rectx, *rectzofs, my0, my2;
1189
1190         /* init */
1191         zbuf_init_span(zspan);
1192
1193         /* set spans */
1194         zbuf_add_to_span(zspan, v1, v2);
1195         zbuf_add_to_span(zspan, v2, v3);
1196         if(v4) {
1197                 zbuf_add_to_span(zspan, v3, v4);
1198                 zbuf_add_to_span(zspan, v4, v1);
1199         }
1200         else
1201                 zbuf_add_to_span(zspan, v3, v1);
1202
1203         /* clipped */
1204         if(zspan->minp2==NULL || zspan->maxp2==NULL) return;
1205
1206         if(zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
1207         if(zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
1208
1209         //      printf("my %d %d\n", my0, my2);
1210         if(my2<my0) return;
1211
1212
1213         /* ZBUF DX DY, in floats still */
1214         x1= v1[0]- v2[0];
1215         x2= v2[0]- v3[0];
1216         y1= v1[1]- v2[1];
1217         y2= v2[1]- v3[1];
1218         z1= v1[2]- v2[2];
1219         z2= v2[2]- v3[2];
1220         x0= y1*z2-z1*y2;
1221         y0= z1*x2-x1*z2;
1222         z0= x1*y2-y1*x2;
1223
1224         if(z0==0.0) return;
1225
1226         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
1227
1228         zxd= -(double)x0/(double)z0;
1229         zyd= -(double)y0/(double)z0;
1230         zy0= ((double)my2)*zyd + (double)xx1;
1231
1232         /* start-offset in rect */
1233         rectx= zspan->rectx;
1234         rectzofs= (zspan->rectz+rectx*my2);
1235
1236         /* correct span */
1237         sn1= (my0 + my2)/2;
1238         if(zspan->span1[sn1] < zspan->span2[sn1]) {
1239                 span1= zspan->span1+my2;
1240                 span2= zspan->span2+my2;
1241         }
1242         else {
1243                 span1= zspan->span2+my2;
1244                 span2= zspan->span1+my2;
1245         }
1246
1247         for(y=my2; y>=my0; y--, span1--, span2--) {
1248
1249                 sn1= floor(*span1);
1250                 sn2= floor(*span2);
1251                 sn1++;
1252
1253                 if(sn2>=rectx) sn2= rectx-1;
1254                 if(sn1<0) sn1= 0;
1255
1256                 if(sn2>=sn1) {
1257                         zverg= (double)sn1*zxd + zy0;
1258                         rz= rectzofs+sn1;
1259                         x= sn2-sn1;
1260
1261                         while(x>=0) {
1262                                 if( (int)zverg < *rz) {
1263                                         *rz= (int)zverg;
1264                                 }
1265                                 zverg+= zxd;
1266                                 rz++;
1267                                 x--;
1268                         }
1269                 }
1270
1271                 zy0-=zyd;
1272                 rectzofs-= rectx;
1273         }
1274 }
1275
1276
1277 /**
1278  * (clip pyramid)
1279  * Sets labda: flag, and parametrize the clipping of vertices in
1280  * viewspace coordinates. labda = -1 means no clipping, labda in [0,
1281          * 1] means a clipping.
1282  * Note: uses globals.
1283  * @param v1 start coordinate s
1284  * @param v2 target coordinate t
1285  * @param b1
1286  * @param b2
1287  * @param b3
1288  * @param a index for coordinate (x, y, or z)
1289  */
1290
1291 static void clippyra(float *labda, float *v1, float *v2, int *b2, int *b3, int a)
1292 {
1293         float da,db,u1=0.0,u2=1.0;
1294
1295         labda[0]= -1.0;
1296         labda[1]= -1.0;
1297
1298         da= v2[a]-v1[a];
1299         db= v2[3]-v1[3];
1300
1301         /* according the original article by Liang&Barsky, for clipping of
1302          * homogenous coordinates with viewplane, the value of "0" is used instead of "-w" .
1303          * This differs from the other clipping cases (like left or top) and I considered
1304          * it to be not so 'homogenic'. But later it has proven to be an error,
1305          * who would have thought that of L&B!
1306          */
1307
1308         if(cliptestf(-da-db, v1[3]+v1[a], &u1,&u2)) {
1309                 if(cliptestf(da-db, v1[3]-v1[a], &u1,&u2)) {
1310                         *b3=1;
1311                         if(u2<1.0) {
1312                                 labda[1]= u2;
1313                                 *b2=1;
1314                         }
1315                         else labda[1]=1.0;  /* u2 */
1316                         if(u1>0.0) {
1317                                 labda[0]= u1;
1318                                 *b2=1;
1319                         } else labda[0]=0.0;
1320                 }
1321         }
1322 }
1323
1324 /**
1325  * (make vertex pyramide clip)
1326  * Checks labda and uses this to make decision about clipping the line
1327  * segment from v1 to v2. labda is the factor by which the vector is
1328  * cut. ( calculate s + l * ( t - s )). The result is appended to the
1329  * vertex list of this face.
1330  *
1331  *
1332  * @param v1 start coordinate s
1333  * @param v2 target coordinate t
1334  * @param b1
1335  * @param b2
1336  * @param clve vertex vector.
1337  */
1338
1339 static void makevertpyra(float *vez, float *labda, float **trias, float *v1, float *v2, int *b1, int *clve)
1340 {
1341         float l1, l2, *adr;
1342
1343         l1= labda[0];
1344         l2= labda[1];
1345
1346         if(l1!= -1.0) {
1347                 if(l1!= 0.0) {
1348                         adr= vez+4*(*clve);
1349                         trias[*b1]=adr;
1350                         (*clve)++;
1351                         adr[0]= v1[0]+l1*(v2[0]-v1[0]);
1352                         adr[1]= v1[1]+l1*(v2[1]-v1[1]);
1353                         adr[2]= v1[2]+l1*(v2[2]-v1[2]);
1354                         adr[3]= v1[3]+l1*(v2[3]-v1[3]);
1355                 }
1356                 else trias[*b1]= v1;
1357
1358                 (*b1)++;
1359         }
1360         if(l2!= -1.0) {
1361                 if(l2!= 1.0) {
1362                         adr= vez+4*(*clve);
1363                         trias[*b1]=adr;
1364                         (*clve)++;
1365                         adr[0]= v1[0]+l2*(v2[0]-v1[0]);
1366                         adr[1]= v1[1]+l2*(v2[1]-v1[1]);
1367                         adr[2]= v1[2]+l2*(v2[2]-v1[2]);
1368                         adr[3]= v1[3]+l2*(v2[3]-v1[3]);
1369                         (*b1)++;
1370                 }
1371         }
1372 }
1373
1374 /* ------------------------------------------------------------------------- */
1375
1376 void projectverto(float *v1, float winmat[][4], float *adr)
1377 {
1378         /* calcs homogenic coord of vertex v1 */
1379         float x,y,z;
1380
1381         x= v1[0];
1382         y= v1[1];
1383         z= v1[2];
1384         adr[0]= x*winmat[0][0]                          +       z*winmat[2][0] + winmat[3][0];
1385         adr[1]=                       y*winmat[1][1]    +       z*winmat[2][1] + winmat[3][1];
1386         adr[2]=                                                                         z*winmat[2][2] + winmat[3][2];
1387         adr[3]=                                                                         z*winmat[2][3] + winmat[3][3];
1388
1389         //printf("hoco %f %f %f %f\n", adr[0], adr[1], adr[2], adr[3]);
1390 }
1391
1392 /* ------------------------------------------------------------------------- */
1393
1394 void projectvert(float *v1, float winmat[][4], float *adr)
1395 {
1396         /* calcs homogenic coord of vertex v1 */
1397         float x,y,z;
1398
1399         x= v1[0];
1400         y= v1[1];
1401         z= v1[2];
1402         adr[0]= x*winmat[0][0]+ y*winmat[1][0]+ z*winmat[2][0]+ winmat[3][0];
1403         adr[1]= x*winmat[0][1]+ y*winmat[1][1]+ z*winmat[2][1]+ winmat[3][1];
1404         adr[2]= x*winmat[0][2]+ y*winmat[1][2]+ z*winmat[2][2]+ winmat[3][2];
1405         adr[3]= x*winmat[0][3]+ y*winmat[1][3]+ z*winmat[2][3]+ winmat[3][3];
1406 }
1407
1408 /* do zbuffering and clip, f1 f2 f3 are hocos, c1 c2 c3 are clipping flags */
1409
1410 void zbufclip(ZSpan *zspan, int zvlnr, float *f1, float *f2, float *f3, int c1, int c2, int c3)
1411 {
1412         float *vlzp[32][3], labda[3][2];
1413         float vez[400], *trias[40];
1414
1415         if(c1 | c2 | c3) {      /* not in middle */
1416                 if(c1 & c2 & c3) {      /* completely out */
1417                         return;
1418                 } else {        /* clipping */
1419                         int arg, v, b, clipflag[3], b1, b2, b3, c4, clve=3, clvlo, clvl=1;
1420
1421                         vez[0]= f1[0]; vez[1]= f1[1]; vez[2]= f1[2]; vez[3]= f1[3];
1422                         vez[4]= f2[0]; vez[5]= f2[1]; vez[6]= f2[2]; vez[7]= f2[3];
1423                         vez[8]= f3[0]; vez[9]= f3[1]; vez[10]= f3[2];vez[11]= f3[3];
1424
1425                         vlzp[0][0]= vez;
1426                         vlzp[0][1]= vez+4;
1427                         vlzp[0][2]= vez+8;
1428
1429                         clipflag[0]= ( (c1 & 48) | (c2 & 48) | (c3 & 48) );
1430                         if(clipflag[0]==0) {    /* othwerwise it needs to be calculated again, after the first (z) clip */
1431                                 clipflag[1]= ( (c1 & 3) | (c2 & 3) | (c3 & 3) );
1432                                 clipflag[2]= ( (c1 & 12) | (c2 & 12) | (c3 & 12) );
1433                         }
1434
1435                         for(b=0;b<3;b++) {
1436
1437                                 if(clipflag[b]) {
1438
1439                                         clvlo= clvl;
1440
1441                                         for(v=0; v<clvlo; v++) {
1442
1443                                                 if(vlzp[v][0]!=0) {     /* face is still there */
1444                                                         b2= b3 =0;      /* clip flags */
1445
1446                                                         if(b==0) arg= 2;
1447                                                         else if (b==1) arg= 0;
1448                                                         else arg= 1;
1449
1450                                                         clippyra(labda[0], vlzp[v][0],vlzp[v][1], &b2,&b3, arg);
1451                                                         clippyra(labda[1], vlzp[v][1],vlzp[v][2], &b2,&b3, arg);
1452                                                         clippyra(labda[2], vlzp[v][2],vlzp[v][0], &b2,&b3, arg);
1453
1454                                                         if(b2==0 && b3==1) {
1455                                                                 /* completely 'in' */;
1456                                                         } else if(b3==0) {
1457                                                                 vlzp[v][0]=0;
1458                                                                 /* completely 'out' */;
1459                                                         } else {
1460                                                                 b1=0;
1461                                                                 makevertpyra(vez, labda[0], trias, vlzp[v][0],vlzp[v][1], &b1,&clve);
1462                                                                 makevertpyra(vez, labda[1], trias, vlzp[v][1],vlzp[v][2], &b1,&clve);
1463                                                                 makevertpyra(vez, labda[2], trias, vlzp[v][2],vlzp[v][0], &b1,&clve);
1464
1465                                                                 /* after front clip done: now set clip flags */
1466                                                                 if(b==0) {
1467                                                                         clipflag[1]= clipflag[2]= 0;
1468                                                                         f1= vez;
1469                                                                         for(b3=0; b3<clve; b3++) {
1470                                                                                 c4= testclip(f1);
1471                                                                                 clipflag[1] |= (c4 & 3);
1472                                                                                 clipflag[2] |= (c4 & 12);
1473                                                                                 f1+= 4;
1474                                                                         }
1475                                                                 }
1476
1477                                                                 vlzp[v][0]=0;
1478                                                                 if(b1>2) {
1479                                                                         for(b3=3; b3<=b1; b3++) {
1480                                                                                 vlzp[clvl][0]= trias[0];
1481                                                                                 vlzp[clvl][1]= trias[b3-2];
1482                                                                                 vlzp[clvl][2]= trias[b3-1];
1483                                                                                 clvl++;
1484                                                                         }
1485                                                                 }
1486                                                         }
1487                                                 }
1488                                         }
1489                                 }
1490                         }
1491
1492             /* warning, this should never happen! */
1493                         if(clve>38 || clvl>31) printf("clip overflow: clve clvl %d %d\n",clve,clvl);
1494
1495             /* perspective division */
1496                         f1=vez;
1497                         for(c1=0;c1<clve;c1++) {
1498                                 hoco_to_zco(zspan, f1, f1);
1499                                 f1+=4;
1500                         }
1501                         for(b=1;b<clvl;b++) {
1502                                 if(vlzp[b][0]) {
1503                                         zspan->zbuffunc(zspan, zvlnr, vlzp[b][0],vlzp[b][1],vlzp[b][2], NULL);
1504                                 }
1505                         }
1506                         return;
1507                 }
1508         }
1509
1510         /* perspective division: HCS to ZCS */
1511         hoco_to_zco(zspan, vez, f1);
1512         hoco_to_zco(zspan, vez+4, f2);
1513         hoco_to_zco(zspan, vez+8, f3);
1514
1515         zspan->zbuffunc(zspan, zvlnr, vez,vez+4,vez+8, NULL);
1516 }
1517
1518 static void zbufclip4(ZSpan *zspan, int zvlnr, float *f1, float *f2, float *f3, float *f4, int c1, int c2, int c3, int c4)
1519 {
1520         float vez[16];
1521
1522         if(c1 | c2 | c3 | c4) { /* not in middle */
1523                 if(c1 & c2 & c3 & c4) { /* completely out */
1524                         return;
1525                 } else {        /* clipping */
1526                         zbufclip(zspan, zvlnr, f1, f2, f3, c1, c2, c3);
1527                         zbufclip(zspan, zvlnr, f1, f3, f4, c1, c3, c4);
1528                 }
1529                 return;
1530         }
1531
1532         /* perspective division: HCS to ZCS */
1533         hoco_to_zco(zspan, vez, f1);
1534         hoco_to_zco(zspan, vez+4, f2);
1535         hoco_to_zco(zspan, vez+8, f3);
1536         hoco_to_zco(zspan, vez+12, f4);
1537
1538         zspan->zbuffunc(zspan, zvlnr, vez, vez+4, vez+8, vez+12);
1539 }
1540
1541
1542 /* ***************** ZBUFFER MAIN ROUTINES **************** */
1543
1544 void set_part_zbuf_clipflag(RenderPart *pa)
1545 {
1546         VertRen *ver=NULL;
1547         float minx, miny, maxx, maxy, wco;
1548         unsigned short clipclear;
1549         int v;
1550
1551         minx= (2*pa->disprect.xmin - R.winx-1)/(float)R.winx;
1552         maxx= (2*pa->disprect.xmax - R.winx+1)/(float)R.winx;
1553         miny= (2*pa->disprect.ymin - R.winy-1)/(float)R.winy;
1554         maxy= (2*pa->disprect.ymax - R.winy+1)/(float)R.winy;
1555
1556         /* supports up to 4 threads this way */
1557         clipclear= ~(15 << 4*(pa->thread & 3));
1558
1559         for(v=0; v<R.totvert; v++) {
1560                 if((v & 255)==0) ver= RE_findOrAddVert(&R, v);
1561                 else ver++;
1562
1563                 wco= ver->ho[3];
1564                 ver->flag &= clipclear;
1565
1566                 switch(pa->thread & 3) {
1567                         case 0:
1568                                 if( ver->ho[0] > maxx*wco) ver->flag |= 1;
1569                                 else if( ver->ho[0]< minx*wco) ver->flag |= 2;
1570                                 if( ver->ho[1] > maxy*wco) ver->flag |= 4;
1571                                 else if( ver->ho[1]< miny*wco) ver->flag |= 8;
1572                                 break;
1573                         case 1:
1574                                 if( ver->ho[0] > maxx*wco) ver->flag |= 16;
1575                                 else if( ver->ho[0]< minx*wco) ver->flag |= 32;
1576                                 if( ver->ho[1] > maxy*wco) ver->flag |= 64;
1577                                 else if( ver->ho[1]< miny*wco) ver->flag |= 128;
1578                                 break;
1579                         case 2:
1580                                 if( ver->ho[0] > maxx*wco) ver->flag |= 256;
1581                                 else if( ver->ho[0]< minx*wco) ver->flag |= 512;
1582                                 if( ver->ho[1] > maxy*wco) ver->flag |= 1024;
1583                                 else if( ver->ho[1]< miny*wco) ver->flag |= 2048;
1584                                 break;
1585                         case 3:
1586                                 if( ver->ho[0] > maxx*wco) ver->flag |= 4096;
1587                                 else if( ver->ho[0]< minx*wco) ver->flag |= 8192;
1588                                 if( ver->ho[1] > maxy*wco) ver->flag |= 16384;
1589                                 else if( ver->ho[1]< miny*wco) ver->flag |= 32768;
1590                                 break;
1591                 }
1592         }
1593 }
1594
1595 void zbuffer_solid(RenderPart *pa)
1596 {
1597         ZSpan zspan;
1598         VlakRen *vlr= NULL;
1599         Material *ma=0;
1600         int v, zvlnr;
1601         unsigned short clipmask;
1602         short transp=0, env=0, wire=0;
1603
1604         zbuf_alloc_span(&zspan, pa->rectx, pa->recty);
1605
1606         /* needed for transform from hoco to zbuffer co */
1607         zspan.zmulx=  ((float)R.winx)/2.0;
1608         zspan.zmuly=  ((float)R.winy)/2.0;
1609         if(R.osa) {
1610                 zspan.zofsx= -pa->disprect.xmin - R.jit[pa->sample][0];
1611                 zspan.zofsy= -pa->disprect.ymin - R.jit[pa->sample][1];
1612         }
1613         else {
1614                 zspan.zofsx= -pa->disprect.xmin -0.5f;
1615                 zspan.zofsy= -pa->disprect.ymin -0.5f;
1616         }
1617
1618         /* the buffers */
1619         zspan.rectz= pa->rectz;
1620         zspan.rectp= pa->rectp;
1621         fillrect(pa->rectp, pa->rectx, pa->recty, 0);
1622         fillrect(pa->rectz, pa->rectx, pa->recty, 0x7FFFFFFF);
1623
1624         /* filling methods */
1625         zspan.zbuffunc= zbufinvulGL4;
1626         zspan.zbuflinefunc= zbufline;
1627
1628         /* part clipflag, threaded */
1629         clipmask= (15 << 4*(pa->thread & 3));
1630
1631         for(v=0; v<R.totvlak; v++) {
1632
1633                 if((v & 255)==0) vlr= R.blovl[v>>8];
1634                 else vlr++;
1635
1636                 if(vlr->flag & R_VISIBLE) {
1637                         if(vlr->mat!=ma) {
1638                                 ma= vlr->mat;
1639                                 transp= ma->mode & MA_ZTRA;
1640                                 env= (ma->mode & MA_ENV);
1641                                 wire= (ma->mode & MA_WIRE);
1642
1643                                 if(ma->mode & MA_ZINV) zspan.zbuffunc= zbufinvulGLinv4;
1644                                 else zspan.zbuffunc= zbufinvulGL4;
1645                         }
1646
1647                         if(transp==0) {
1648                                 unsigned short partclip;
1649
1650                                 /* partclipping doesn't need viewplane clipping */
1651                                 if(vlr->v4) partclip= vlr->v1->flag & vlr->v2->flag & vlr->v3->flag & vlr->v4->flag;
1652                                 else partclip= vlr->v1->flag & vlr->v2->flag & vlr->v3->flag;
1653
1654                                 if((partclip & clipmask)==0) {
1655
1656                                         if(env) zvlnr= 0;
1657                                         else zvlnr= v+1;
1658
1659                                         if(wire) zbufclipwire(&zspan, zvlnr, vlr);
1660                                         else {
1661                                                 /* strands allow to be filled in as quad */
1662                                                 if(vlr->v4 && (vlr->flag & R_STRAND)) {
1663                                                         zbufclip4(&zspan, zvlnr, vlr->v1->ho, vlr->v2->ho, vlr->v3->ho, vlr->v4->ho, vlr->v1->clip, vlr->v2->clip, vlr->v3->clip, vlr->v4->clip);
1664                                                 }
1665                                                 else {
1666                                                         zbufclip(&zspan, zvlnr, vlr->v1->ho, vlr->v2->ho, vlr->v3->ho, vlr->v1->clip, vlr->v2->clip, vlr->v3->clip);
1667                                                         if(vlr->v4) {
1668                                                                 if(zvlnr) zvlnr+= 0x800000;
1669                                                                 zbufclip(&zspan, zvlnr, vlr->v1->ho, vlr->v3->ho, vlr->v4->ho, vlr->v1->clip, vlr->v3->clip, vlr->v4->clip);
1670                                                         }
1671                                                 }
1672                                         }
1673                                 }
1674                         }
1675                 }
1676         }
1677
1678         zbuf_free_span(&zspan);
1679 }
1680
1681 typedef struct {
1682         float *vert;
1683         float hoco[4];
1684         int clip;
1685 } VertBucket;
1686
1687 /* warning, not threaded! */
1688 static int hashlist_projectvert(float *v1, float winmat[][4], float *hoco)
1689 {
1690         static VertBucket bucket[256], *buck;
1691
1692         /* init static bucket */
1693         if(v1==NULL) {
1694                 memset(bucket, 0, 256*sizeof(VertBucket));
1695                 return 0;
1696         }
1697
1698         buck= &bucket[ (((long)v1)/16) & 255 ];
1699         if(buck->vert==v1) {
1700                 QUATCOPY(hoco, buck->hoco);
1701                 return buck->clip;
1702         }
1703
1704         projectvert(v1, winmat, hoco);
1705         buck->clip = testclip(hoco);
1706         buck->vert= v1;
1707         QUATCOPY(buck->hoco, hoco);
1708         return buck->clip;
1709 }
1710
1711 /* used for booth radio 'tool' as during render */
1712 void RE_zbufferall_radio(struct RadView *vw, RNode **rg_elem, int rg_totelem, Render *re)
1713 {
1714         ZSpan zspan;
1715         float hoco[4][4], winmat[4][4];
1716         int a, zvlnr;
1717         int c1, c2, c3, c4= 0;
1718
1719         if(rg_totelem==0) return;
1720
1721         hashlist_projectvert(NULL, winmat, NULL);
1722
1723         /* needed for projectvert */
1724         MTC_Mat4MulMat4(winmat, vw->viewmat, vw->winmat);
1725
1726         zbuf_alloc_span(&zspan, vw->rectx, vw->recty);
1727         zspan.zmulx=  ((float)vw->rectx)/2.0;
1728         zspan.zmuly=  ((float)vw->recty)/2.0;
1729         zspan.zofsx= 0;
1730         zspan.zofsy= 0;
1731
1732         /* the buffers */
1733         zspan.rectz= vw->rectz;
1734         zspan.rectp= vw->rect;
1735         fillrect(zspan.rectz, vw->rectx, vw->recty, 0x7FFFFFFF);
1736         fillrect(zspan.rectp, vw->rectx, vw->recty, 0xFFFFFF);
1737
1738         /* filling methods */
1739         zspan.zbuffunc= zbufinvulGL4;
1740
1741         if(rg_elem) {   /* radio tool */
1742                 RNode **re, *rn;
1743
1744                 re= rg_elem;
1745                 re+= (rg_totelem-1);
1746                 for(a= rg_totelem-1; a>=0; a--, re--) {
1747                         rn= *re;
1748                         if( (rn->f & RAD_SHOOT)==0 ) {    /* no shootelement */
1749
1750                                 if( rn->f & RAD_TWOSIDED) zvlnr= a;
1751                                 else if( rn->f & RAD_BACKFACE) zvlnr= 0xFFFFFF;
1752                                 else zvlnr= a;
1753
1754                                 c1= hashlist_projectvert(rn->v1, winmat, hoco[0]);
1755                                 c2= hashlist_projectvert(rn->v2, winmat, hoco[1]);
1756                                 c3= hashlist_projectvert(rn->v3, winmat, hoco[2]);
1757
1758                                 if(rn->v4) {
1759                                         c4= hashlist_projectvert(rn->v4, winmat, hoco[3]);
1760                                 }
1761
1762                                 if(rn->v4)
1763                                         zbufclip4(&zspan, zvlnr, hoco[0], hoco[1], hoco[2], hoco[3], c1, c2, c3, c4);
1764                                 else
1765                                         zbufclip(&zspan, zvlnr, hoco[0], hoco[1], hoco[2], c1, c2, c3);
1766                         }
1767                 }
1768         }
1769         else {  /* radio render */
1770                 VlakRen *vlr=NULL;
1771                 RadFace *rf;
1772                 int totface=0;
1773
1774                 for(a=0; a<re->totvlak; a++) {
1775                         if((a & 255)==0) vlr= re->blovl[a>>8]; else vlr++;
1776
1777                         if(vlr->radface) {
1778                                 rf= vlr->radface;
1779                                 if( (rf->flag & RAD_SHOOT)==0 ) {    /* no shootelement */
1780
1781                                         if( rf->flag & RAD_TWOSIDED) zvlnr= totface;
1782                                         else if( rf->flag & RAD_BACKFACE) zvlnr= 0xFFFFFF;      /* receives no energy, but is zbuffered */
1783                                         else zvlnr= totface;
1784
1785                                         c1= hashlist_projectvert(vlr->v1->co, winmat, hoco[0]);
1786                                         c2= hashlist_projectvert(vlr->v2->co, winmat, hoco[1]);
1787                                         c3= hashlist_projectvert(vlr->v3->co, winmat, hoco[2]);
1788
1789                                         if(vlr->v4) {
1790                                                 c4= hashlist_projectvert(vlr->v4->co, winmat, hoco[3]);
1791                                         }
1792
1793                                         if(vlr->v4)
1794                                                 zbufclip4(&zspan, zvlnr, hoco[0], hoco[1], hoco[2], hoco[3], c1, c2, c3, c4);
1795                                         else
1796                                                 zbufclip(&zspan, zvlnr, hoco[0], hoco[1], hoco[2], c1, c2, c3);
1797                                 }
1798                                 totface++;
1799                         }
1800                 }
1801         }
1802
1803         zbuf_free_span(&zspan);
1804 }
1805
1806 void zbuffer_shadow(Render *re, LampRen *lar, int *rectz, int size)
1807 {
1808         ZSpan zspan;
1809         VlakRen *vlr= NULL;
1810         Material *ma=0;
1811         int a, ok=1, lay= -1;
1812
1813         if(lar->mode & LA_LAYER) lay= lar->lay;
1814
1815         zbuf_alloc_span(&zspan, size, size);
1816         zspan.zmulx=  ((float)size)/2.0;
1817         zspan.zmuly=  ((float)size)/2.0;
1818         zspan.zofsx= -0.5f;
1819         zspan.zofsy= -0.5f;
1820
1821         /* the buffers */
1822         zspan.rectz= rectz;
1823         fillrect(rectz, size, size, 0x7FFFFFFE);
1824
1825         /* filling methods */
1826         zspan.zbuflinefunc= zbufline_onlyZ;
1827         zspan.zbuffunc= zbufinvulGL_onlyZ;
1828
1829         for(a=0; a<re->totvlak; a++) {
1830
1831                 if((a & 255)==0) vlr= re->blovl[a>>8];
1832                 else vlr++;
1833
1834                 if(vlr->mat!= ma) {
1835                         ma= vlr->mat;
1836                         ok= 1;
1837                         if((ma->mode & MA_SHADBUF)==0) ok= 0;
1838                 }
1839
1840                 if(ok && (vlr->flag & R_VISIBLE) && (vlr->lay & lay)) {
1841                         if(ma->mode & MA_WIRE) zbufclipwire(&zspan, a+1, vlr);
1842                         else if(vlr->flag & R_STRAND) zbufclipwire(&zspan, a+1, vlr);
1843                         else {
1844                                 if(vlr->v4)
1845                                         zbufclip4(&zspan, 0, vlr->v1->ho, vlr->v2->ho, vlr->v3->ho, vlr->v4->ho, vlr->v1->clip, vlr->v2->clip, vlr->v3->clip, vlr->v4->clip);
1846                                 else
1847                                         zbufclip(&zspan, 0, vlr->v1->ho, vlr->v2->ho, vlr->v3->ho, vlr->v1->clip, vlr->v2->clip, vlr->v3->clip);
1848                         }
1849                 }
1850         }
1851         zbuf_free_span(&zspan);
1852 }
1853
1854
1855
1856 /* ******************** ABUF ************************* */
1857
1858 /**
1859  * Copy results from the solid face z buffering to the transparent
1860  * buffer.
1861  */
1862 static void copyto_abufz(RenderPart *pa, int *arectz, int sample)
1863 {
1864         PixStr *ps;
1865         int x, y, *rza;
1866         long *rd;
1867
1868         /* now, in OSA the pixstructs contain all faces filled in */
1869         if(R.r.mode & R_OSA) fillrect(arectz, pa->rectx, pa->recty, 0x7FFFFFFF);
1870         else {
1871                 memcpy(arectz, pa->rectz, 4*pa->rectx*pa->recty);
1872                 return;
1873         }
1874         if( (R.r.mode & R_OSA)==0 || sample==0) return;
1875
1876         rza= arectz;
1877         rd= pa->rectdaps;
1878
1879         sample= (1<<sample);
1880
1881         for(y=0; y<pa->recty; y++) {
1882                 for(x=0; x<pa->rectx; x++) {
1883
1884                         if(*rd) {
1885                                 ps= (PixStr *)(*rd);
1886
1887                                 while(ps) {
1888                                         if(sample & ps->mask) {
1889                                                 //printf("filled xy %d %d mask %d\n", x, y, sample);
1890                                                 *rza= ps->z;
1891                                                 break;
1892                                         }
1893                                         ps= ps->next;
1894                                 }
1895                         }
1896
1897                         rd++; rza++;
1898                 }
1899         }
1900 }
1901
1902
1903 /* ------------------------------------------------------------------------ */
1904
1905 /**
1906  * Do accumulation z buffering.
1907  */
1908
1909 static void zbuffer_abuf(RenderPart *pa, APixstr *APixbuf, ListBase *apsmbase)
1910 {
1911         ZSpan zspan;
1912         Material *ma=0;
1913         VlakRen *vlr=NULL;
1914         float vec[3], hoco[4], mul, zval, fval;
1915         int v, zvlnr, zsample;
1916         unsigned short clipmask;
1917
1918         zbuf_alloc_span(&zspan, pa->rectx, pa->recty);
1919
1920         /* needed for transform from hoco to zbuffer co */
1921         zspan.zmulx=  ((float)R.winx)/2.0;
1922         zspan.zmuly=  ((float)R.winy)/2.0;
1923         zspan.zofsx= -pa->disprect.xmin -0.5f;
1924         zspan.zofsy= -pa->disprect.ymin -0.5f;
1925
1926         /* the buffers */
1927         zspan.arectz= RE_mallocN(sizeof(int)*pa->rectx*pa->recty, "Arectz");
1928         zspan.apixbuf= APixbuf;
1929         zspan.apsmbase= apsmbase;
1930
1931         /* filling methods */
1932         zspan.zbuffunc= zbufinvulAc4;
1933         zspan.zbuflinefunc= zbuflineAc;
1934
1935         /* part clipflag, 4 threads */
1936         clipmask= (15 << 4*(pa->thread & 3));
1937
1938         for(zsample=0; zsample<R.osa || R.osa==0; zsample++) {
1939
1940                 copyto_abufz(pa, zspan.arectz, zsample);        /* init zbuffer */
1941                 zspan.mask= 1<<zsample;
1942
1943                 if(R.r.mode & R_OSA) {
1944                         zspan.zofsx= -pa->disprect.xmin-R.jit[zsample][0]-0.5;
1945                         zspan.zofsy= -pa->disprect.ymin-R.jit[zsample][1]-0.5;
1946                 }
1947
1948                 for(v=0; v<R.totvlak; v++) {
1949                         if((v & 255)==0)
1950                                 vlr= R.blovl[v>>8];
1951                         else vlr++;
1952
1953                         ma= vlr->mat;
1954                         if(ma->mode & (MA_ZTRA)) {
1955                                 if(vlr->flag & R_VISIBLE) {
1956                                         unsigned short partclip;
1957
1958                                         /* partclipping doesn't need viewplane clipping */
1959                                         if(vlr->v4) partclip= vlr->v1->flag & vlr->v2->flag & vlr->v3->flag & vlr->v4->flag;
1960                                         else partclip= vlr->v1->flag & vlr->v2->flag & vlr->v3->flag;
1961
1962                                         if((partclip & clipmask)==0) {
1963                                                 /* a little advantage for transp rendering (a z offset) */
1964                                                 if( ma->zoffs != 0.0) {
1965                                                         mul= 0x7FFFFFFF;
1966                                                         zval= mul*(1.0+vlr->v1->ho[2]/vlr->v1->ho[3]);
1967
1968                                                         VECCOPY(vec, vlr->v1->co);
1969                                                         /* z is negative, otherwise its being clipped */
1970                                                         vec[2]-= ma->zoffs;
1971                                                         projectverto(vec, R.winmat, hoco);
1972                                                         fval= mul*(1.0+hoco[2]/hoco[3]);
1973
1974                                                         zspan.polygon_offset= (int) fabs(zval - fval );
1975                                                 }
1976                                                 else zspan.polygon_offset= 0;
1977
1978                                                 zvlnr= v+1;
1979
1980                                                 if(ma->mode & (MA_WIRE)) zbufclipwire(&zspan, zvlnr, vlr);
1981                                                 else {
1982                                                         if(vlr->v4 && (vlr->flag & R_STRAND)) {
1983                                                                 zbufclip4(&zspan, zvlnr, vlr->v1->ho, vlr->v2->ho, vlr->v3->ho, vlr->v4->ho, vlr->v1->clip, vlr->v2->clip, vlr->v3->clip, vlr->v4->clip);
1984                                                         }
1985                                                         else {
1986                                                                 zbufclip(&zspan, zvlnr, vlr->v1->ho, vlr->v2->ho, vlr->v3->ho, vlr->v1->clip, vlr->v2->clip, vlr->v3->clip);
1987                                                                 if(vlr->v4) {
1988                                                                         zvlnr+= 0x800000;
1989                                                                         zbufclip(&zspan, zvlnr, vlr->v1->ho, vlr->v3->ho, vlr->v4->ho, vlr->v1->clip, vlr->v3->clip, vlr->v4->clip);
1990                                                                 }
1991                                                         }
1992                                                 }
1993                                         }
1994                                 }
1995                                 if( (v & 255)==255)
1996                                         if(R.test_break())
1997                                                 break;
1998                         }
1999                 }
2000
2001                 if((R.r.mode & R_OSA)==0) break;
2002                 if(R.test_break()) break;
2003         }
2004
2005         RE_freeN(zspan.arectz);
2006         zbuf_free_span(&zspan);
2007
2008 }
2009
2010 static int vergzvlak(const void *a1, const void *a2)
2011 {
2012         const int *x1=a1, *x2=a2;
2013
2014         if( x1[0] < x2[0] ) return 1;
2015         else if( x1[0] > x2[0]) return -1;
2016         return 0;
2017 }
2018
2019 /**
2020 * Shade this face at this location in SCS.
2021  */
2022 static void shadetrapixel(RenderPart *pa, float x, float y, int z, int facenr, int mask, float *fcol)
2023 {
2024         float rco[3];
2025
2026         if( (facenr & 0x7FFFFF) > R.totvlak) {
2027                 printf("error in shadetrapixel nr: %d\n", (facenr & 0x7FFFFF));
2028                 return;
2029         }
2030         if(R.r.mode & R_OSA) {
2031                 VlakRen *vlr= RE_findOrAddVlak(&R, (facenr-1) & 0x7FFFFF);
2032                 float accumcol[4]={0,0,0,0}, tot=0.0;
2033                 int a;
2034
2035                 if(vlr->flag & R_FULL_OSA) {
2036                         for(a=0; a<R.osa; a++) {
2037                                 if(mask & (1<<a)) {
2038                                         shadepixel(pa, x+R.jit[a][0], y+R.jit[a][1], z, facenr, 1<<a, fcol, rco);
2039                                         accumcol[0]+= fcol[0];
2040                                         accumcol[1]+= fcol[1];
2041                                         accumcol[2]+= fcol[2];
2042                                         accumcol[3]+= fcol[3];
2043                                         tot+= 1.0;
2044                                 }
2045                         }
2046                         tot= 1.0/tot;
2047                         fcol[0]= accumcol[0]*tot;
2048                         fcol[1]= accumcol[1]*tot;
2049                         fcol[2]= accumcol[2]*tot;
2050                         fcol[3]= accumcol[3]*tot;
2051                 }
2052                 else {
2053                         int b= R.samples->centmask[mask];
2054                         x= x+R.samples->centLut[b & 15];
2055                         y= y+R.samples->centLut[b>>4];
2056                         shadepixel(pa, x, y, z, facenr, mask, fcol, rco);
2057
2058                 }
2059         }
2060         else shadepixel(pa, x, y, z, facenr, mask, fcol, rco);
2061 }
2062
2063 static int addtosampcol(float *sampcol, float *fcol, int mask)
2064 {
2065         int a, retval = R.osa;
2066
2067         for(a=0; a < R.osa; a++) {
2068                 if(mask & (1<<a)) addAlphaUnderFloat(sampcol, fcol);
2069                 if(sampcol[3]>0.999) retval--;
2070                 sampcol+= 4;
2071         }
2072         return retval;
2073 }
2074
2075 #define MAX_ZROW        1000
2076 /* main render call to fill in pass the full transparent layer */
2077
2078 void zbuffer_transp_shade(RenderPart *pa, float *pass)
2079 {
2080         APixstr *APixbuf;      /* Zbuffer: linked list of face samples */
2081         APixstr *ap, *apn;
2082         ListBase apsmbase={NULL, NULL};
2083         float col[4], fcol[4], tempcol[4], sampcol[16*4], *scol, accumcol[4];
2084         float fac, alpha[32];
2085         int x, y, a, zrow[MAX_ZROW][3], totface, nr;
2086         int sval;
2087
2088         /* looks nicer for calling code */
2089         if(R.test_break())
2090                 return;
2091
2092         APixbuf= RE_callocN(pa->rectx*pa->recty*sizeof(APixstr), "APixbuf");
2093
2094         if(R.osa>16) {
2095                 printf("abufsetrow: osa too large\n");
2096                 G.afbreek= 1;
2097                 return;
2098         }
2099
2100         /* alpha LUT */
2101         if(R.r.mode & R_OSA ) {
2102                 fac= (1.0/(float)R.osa);
2103                 for(a=0; a<=R.osa; a++) {
2104                         alpha[a]= (float)a*fac;
2105                 }
2106         }
2107
2108         /* fill the Apixbuf */
2109         zbuffer_abuf(pa, APixbuf, &apsmbase);
2110
2111         /* render tile */
2112         ap= APixbuf;
2113
2114         for(y=pa->disprect.ymin; y<pa->disprect.ymax; y++) {
2115                 for(x=pa->disprect.xmin; x<pa->disprect.xmax; x++, ap++, pass+=4) {
2116
2117                         if(ap->p[0]) {
2118                                 /* sort in z */
2119                                 totface= 0;
2120                                 apn= ap;
2121                                 while(apn) {
2122                                         for(a=0; a<4; a++) {
2123                                                 if(apn->p[a]) {
2124                                                         zrow[totface][0]= apn->z[a];
2125                                                         zrow[totface][1]= apn->p[a];
2126                                                         zrow[totface][2]= apn->mask[a];
2127                                                         totface++;
2128                                                         if(totface>=MAX_ZROW) totface= MAX_ZROW-1;
2129                                                 }
2130                                                 else break;
2131                                         }
2132                                         apn= apn->next;
2133                                 }
2134
2135                                 if(totface==1) {
2136
2137                                         shadetrapixel(pa, (float)x, (float)y, zrow[0][0], zrow[0][1], zrow[0][2], fcol);
2138
2139                                         nr= count_mask(zrow[0][2]);
2140                                         if( (R.r.mode & R_OSA) && nr<R.osa) {
2141                                                 fac= alpha[ nr ];
2142                                                 col[0]= (fcol[0]*fac);
2143                                                 col[1]= (fcol[1]*fac);
2144                                                 col[2]= (fcol[2]*fac);
2145                                                 col[3]= (fcol[3]*fac);
2146                                         }
2147                                         else {
2148                                                 col[0]= fcol[0];
2149                                                 col[1]= fcol[1];
2150                                                 col[2]= fcol[2];
2151                                                 col[3]= fcol[3];
2152                                         }
2153                                 }
2154                                 else {
2155                                         col[0]= col[1]= col[2]= col[3]= 0.0f;
2156
2157                                         if(totface==2) {
2158                                                 if(zrow[0][0] < zrow[1][0]) {
2159                                                         a= zrow[0][0]; zrow[0][0]= zrow[1][0]; zrow[1][0]= a;
2160                                                         a= zrow[0][1]; zrow[0][1]= zrow[1][1]; zrow[1][1]= a;
2161                                                         a= zrow[0][2]; zrow[0][2]= zrow[1][2]; zrow[1][2]= a;
2162                                                 }
2163
2164                                         }
2165                                         else {  /* totface>2 */
2166                                                 qsort(zrow, totface, sizeof(int)*3, vergzvlak);
2167                                         }
2168
2169                                         /* join when pixels are adjacent */
2170
2171                                         while(totface>0) {
2172                                                 totface--;
2173
2174                                                 shadetrapixel(pa, (float)x, (float)y, zrow[totface][0], zrow[totface][1], zrow[totface][2], fcol);
2175
2176                                                 a= count_mask(zrow[totface][2]);
2177                                                 if( (R.r.mode & R_OSA ) && a<R.osa) {
2178                                                         if(totface>0) {
2179                                                                 memset(sampcol, 0, 4*sizeof(float)*R.osa);
2180                                                                 sval= addtosampcol(sampcol, fcol, zrow[totface][2]);
2181
2182                                                                 /* sval==0: alpha completely full */
2183                                                                 while( (sval != 0) && (totface>0) ) {
2184                                                                         a= count_mask(zrow[totface-1][2]);
2185                                                                         if(a==R.osa) break;
2186                                                                         totface--;
2187
2188                                                                         shadetrapixel(pa, (float)x, (float)y, zrow[totface][0], zrow[totface][1], zrow[totface][2], fcol);
2189                                                                         sval= addtosampcol(sampcol, fcol, zrow[totface][2]);
2190                                                                 }
2191
2192                                                                 scol= sampcol;
2193                                                                 accumcol[0]= scol[0]; accumcol[1]= scol[1];
2194                                                                 accumcol[2]= scol[2]; accumcol[3]= scol[3];
2195                                                                 scol+= 4;
2196                                                                 for(a=1; a<R.osa; a++, scol+=4) {
2197                                                                         accumcol[0]+= scol[0]; accumcol[1]+= scol[1];
2198                                                                         accumcol[2]+= scol[2]; accumcol[3]+= scol[3];
2199                                                                 }
2200                                                                 tempcol[0]= accumcol[0]/R.osa;
2201                                                                 tempcol[1]= accumcol[1]/R.osa;
2202                                                                 tempcol[2]= accumcol[2]/R.osa;
2203                                                                 tempcol[3]= accumcol[3]/R.osa;
2204
2205                                                                 addAlphaUnderFloat(col, tempcol);
2206
2207                                                         }
2208                                                         else {
2209                                                                 fac= alpha[a];
2210                                                                 fcol[0]= (fcol[0]*fac);
2211                                                                 fcol[1]= (fcol[1]*fac);
2212                                                                 fcol[2]= (fcol[2]*fac);
2213                                                                 fcol[3]= (fcol[3]*fac);
2214                                                                 addAlphaUnderFloat(col, fcol);
2215                                                         }
2216                                                 }
2217                                                 else addAlphaUnderFloat(col, fcol);     /* no osa or full pixel with same face? */
2218
2219                                                 if(col[3]>=0.999) break;
2220                                         }
2221                                 }
2222                                 if(col[3]!=0.0) addAlphaOverFloat(pass, col);
2223                         }
2224                 }
2225         }
2226
2227         RE_freeN(APixbuf);
2228         freepsA(&apsmbase);
2229
2230 }
2231
2232
2233 /* end of zbuf.c */
2234
2235
2236
2237