7fac9f599447453cf144bbf511f4ea735fc5c2c7
[blender-staging.git] / 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_callocN(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,dw,u1=0.0,u2=1.0;
1294         float v13;
1295         
1296         labda[0]= -1.0;
1297         labda[1]= -1.0;
1298
1299         da= v2[a]-v1[a];
1300         /* prob; we clip slightly larger, osa renders add 2 pixels on edges, should become variable? */
1301         /* or better; increase r.winx/y size, but thats quite a complex one. do it later */
1302         if(a==2) {
1303                 dw= (v2[3]-v1[3]);
1304                 v13= v1[3];
1305         }
1306         else {
1307                 dw= 1.005f*(v2[3]-v1[3]);
1308                 v13= 1.005f*v1[3];
1309         }       
1310         /* according the original article by Liang&Barsky, for clipping of
1311          * homogenous coordinates with viewplane, the value of "0" is used instead of "-w" .
1312          * This differs from the other clipping cases (like left or top) and I considered
1313          * it to be not so 'homogenic'. But later it has proven to be an error,
1314          * who would have thought that of L&B!
1315          */
1316
1317         if(cliptestf(-da-dw, v13+v1[a], &u1,&u2)) {
1318                 if(cliptestf(da-dw, v13-v1[a], &u1,&u2)) {
1319                         *b3=1;
1320                         if(u2<1.0) {
1321                                 labda[1]= u2;
1322                                 *b2=1;
1323                         }
1324                         else labda[1]=1.0;  /* u2 */
1325                         if(u1>0.0) {
1326                                 labda[0]= u1;
1327                                 *b2=1;
1328                         } else labda[0]=0.0;
1329                 }
1330         }
1331 }
1332
1333 /**
1334  * (make vertex pyramide clip)
1335  * Checks labda and uses this to make decision about clipping the line
1336  * segment from v1 to v2. labda is the factor by which the vector is
1337  * cut. ( calculate s + l * ( t - s )). The result is appended to the
1338  * vertex list of this face.
1339  * 
1340  * 
1341  * @param v1 start coordinate s
1342  * @param v2 target coordinate t
1343  * @param b1 
1344  * @param b2 
1345  * @param clve vertex vector.
1346  */
1347
1348 static void makevertpyra(float *vez, float *labda, float **trias, float *v1, float *v2, int *b1, int *clve)
1349 {
1350         float l1, l2, *adr;
1351
1352         l1= labda[0];
1353         l2= labda[1];
1354
1355         if(l1!= -1.0) {
1356                 if(l1!= 0.0) {
1357                         adr= vez+4*(*clve);
1358                         trias[*b1]=adr;
1359                         (*clve)++;
1360                         adr[0]= v1[0]+l1*(v2[0]-v1[0]);
1361                         adr[1]= v1[1]+l1*(v2[1]-v1[1]);
1362                         adr[2]= v1[2]+l1*(v2[2]-v1[2]);
1363                         adr[3]= v1[3]+l1*(v2[3]-v1[3]);
1364                 } 
1365                 else trias[*b1]= v1;
1366                 
1367                 (*b1)++;
1368         }
1369         if(l2!= -1.0) {
1370                 if(l2!= 1.0) {
1371                         adr= vez+4*(*clve);
1372                         trias[*b1]=adr;
1373                         (*clve)++;
1374                         adr[0]= v1[0]+l2*(v2[0]-v1[0]);
1375                         adr[1]= v1[1]+l2*(v2[1]-v1[1]);
1376                         adr[2]= v1[2]+l2*(v2[2]-v1[2]);
1377                         adr[3]= v1[3]+l2*(v2[3]-v1[3]);
1378                         (*b1)++;
1379                 }
1380         }
1381 }
1382
1383 /* ------------------------------------------------------------------------- */
1384
1385 void projectverto(float *v1, float winmat[][4], float *adr)
1386 {
1387         /* calcs homogenic coord of vertex v1 */
1388         float x,y,z;
1389
1390         x= v1[0]; 
1391         y= v1[1]; 
1392         z= v1[2];
1393         adr[0]= x*winmat[0][0]                          +       z*winmat[2][0] + winmat[3][0];
1394         adr[1]=                       y*winmat[1][1]    +       z*winmat[2][1] + winmat[3][1];
1395         adr[2]=                                                                         z*winmat[2][2] + winmat[3][2];
1396         adr[3]=                                                                         z*winmat[2][3] + winmat[3][3];
1397
1398         //printf("hoco %f %f %f %f\n", adr[0], adr[1], adr[2], adr[3]);
1399 }
1400
1401 /* ------------------------------------------------------------------------- */
1402
1403 void projectvert(float *v1, float winmat[][4], float *adr)
1404 {
1405         /* calcs homogenic coord of vertex v1 */
1406         float x,y,z;
1407
1408         x= v1[0]; 
1409         y= v1[1]; 
1410         z= v1[2];
1411         adr[0]= x*winmat[0][0]+ y*winmat[1][0]+ z*winmat[2][0]+ winmat[3][0];
1412         adr[1]= x*winmat[0][1]+ y*winmat[1][1]+ z*winmat[2][1]+ winmat[3][1];
1413         adr[2]= x*winmat[0][2]+ y*winmat[1][2]+ z*winmat[2][2]+ winmat[3][2];
1414         adr[3]= x*winmat[0][3]+ y*winmat[1][3]+ z*winmat[2][3]+ winmat[3][3];
1415 }
1416
1417 /* do zbuffering and clip, f1 f2 f3 are hocos, c1 c2 c3 are clipping flags */
1418
1419 void zbufclip(ZSpan *zspan, int zvlnr, float *f1, float *f2, float *f3, int c1, int c2, int c3)
1420 {
1421         float *vlzp[32][3], labda[3][2];
1422         float vez[400], *trias[40];
1423
1424         if(c1 | c2 | c3) {      /* not in middle */
1425                 if(c1 & c2 & c3) {      /* completely out */
1426                         return;
1427                 } else {        /* clipping */
1428                         int arg, v, b, clipflag[3], b1, b2, b3, c4, clve=3, clvlo, clvl=1;
1429
1430                         vez[0]= f1[0]; vez[1]= f1[1]; vez[2]= f1[2]; vez[3]= f1[3];
1431                         vez[4]= f2[0]; vez[5]= f2[1]; vez[6]= f2[2]; vez[7]= f2[3];
1432                         vez[8]= f3[0]; vez[9]= f3[1]; vez[10]= f3[2];vez[11]= f3[3];
1433
1434                         vlzp[0][0]= vez;
1435                         vlzp[0][1]= vez+4;
1436                         vlzp[0][2]= vez+8;
1437
1438                         clipflag[0]= ( (c1 & 48) | (c2 & 48) | (c3 & 48) );
1439                         if(clipflag[0]==0) {    /* othwerwise it needs to be calculated again, after the first (z) clip */
1440                                 clipflag[1]= ( (c1 & 3) | (c2 & 3) | (c3 & 3) );
1441                                 clipflag[2]= ( (c1 & 12) | (c2 & 12) | (c3 & 12) );
1442                         }
1443                         
1444                         for(b=0;b<3;b++) {
1445                                 
1446                                 if(clipflag[b]) {
1447                                 
1448                                         clvlo= clvl;
1449                                         
1450                                         for(v=0; v<clvlo; v++) {
1451                                         
1452                                                 if(vlzp[v][0]!=0) {     /* face is still there */
1453                                                         b2= b3 =0;      /* clip flags */
1454
1455                                                         if(b==0) arg= 2;
1456                                                         else if (b==1) arg= 0;
1457                                                         else arg= 1;
1458                                                         
1459                                                         clippyra(labda[0], vlzp[v][0],vlzp[v][1], &b2,&b3, arg);
1460                                                         clippyra(labda[1], vlzp[v][1],vlzp[v][2], &b2,&b3, arg);
1461                                                         clippyra(labda[2], vlzp[v][2],vlzp[v][0], &b2,&b3, arg);
1462
1463                                                         if(b2==0 && b3==1) {
1464                                                                 /* completely 'in' */;
1465                                                                 vlzp[clvl][0]= vlzp[v][0];
1466                                                                 vlzp[clvl][1]= vlzp[v][1];
1467                                                                 vlzp[clvl][2]= vlzp[v][2];
1468                                                                 clvl++;
1469                                                         } else if(b3==0) {
1470                                                                 vlzp[v][0]=0;
1471                                                                 /* completely 'out' */;
1472                                                         } else {
1473                                                                 b1=0;
1474                                                                 makevertpyra(vez, labda[0], trias, vlzp[v][0],vlzp[v][1], &b1,&clve);
1475                                                                 makevertpyra(vez, labda[1], trias, vlzp[v][1],vlzp[v][2], &b1,&clve);
1476                                                                 makevertpyra(vez, labda[2], trias, vlzp[v][2],vlzp[v][0], &b1,&clve);
1477
1478                                                                 /* after front clip done: now set clip flags */
1479                                                                 if(b==0) {
1480                                                                         clipflag[1]= clipflag[2]= 0;
1481                                                                         f1= vez;
1482                                                                         for(b3=0; b3<clve; b3++) {
1483                                                                                 c4= testclip(f1);
1484                                                                                 clipflag[1] |= (c4 & 3);
1485                                                                                 clipflag[2] |= (c4 & 12);
1486                                                                                 f1+= 4;
1487                                                                         }
1488                                                                 }
1489                                                                 
1490                                                                 vlzp[v][0]=0;
1491                                                                 if(b1>2) {
1492                                                                         for(b3=3; b3<=b1; b3++) {
1493                                                                                 vlzp[clvl][0]= trias[0];
1494                                                                                 vlzp[clvl][1]= trias[b3-2];
1495                                                                                 vlzp[clvl][2]= trias[b3-1];
1496                                                                                 clvl++;
1497                                                                         }
1498                                                                 }
1499                                                         }
1500                                                 }
1501                                         }
1502                                 }
1503                         }
1504
1505             /* warning, this should never happen! */
1506                         if(clve>38 || clvl>31) printf("clip overflow: clve clvl %d %d\n",clve,clvl);
1507
1508             /* perspective division */
1509                         f1=vez;
1510                         for(c1=0;c1<clve;c1++) {
1511                                 hoco_to_zco(zspan, f1, f1);
1512                                 f1+=4;
1513                         }
1514                         for(b=1;b<clvl;b++) {
1515                                 if(vlzp[b][0]) {
1516                                         zspan->zbuffunc(zspan, zvlnr, vlzp[b][0],vlzp[b][1],vlzp[b][2], NULL);
1517                                 }
1518                         }
1519                         return;
1520                 }
1521         }
1522
1523         /* perspective division: HCS to ZCS */
1524         hoco_to_zco(zspan, vez, f1);
1525         hoco_to_zco(zspan, vez+4, f2);
1526         hoco_to_zco(zspan, vez+8, f3);
1527
1528         zspan->zbuffunc(zspan, zvlnr, vez,vez+4,vez+8, NULL);
1529 }
1530
1531 static void zbufclip4(ZSpan *zspan, int zvlnr, float *f1, float *f2, float *f3, float *f4, int c1, int c2, int c3, int c4)
1532 {
1533         float vez[16];
1534         
1535         if(c1 | c2 | c3 | c4) { /* not in middle */
1536                 if(c1 & c2 & c3 & c4) { /* completely out */
1537                         return;
1538                 } else {        /* clipping */
1539                         zbufclip(zspan, zvlnr, f1, f2, f3, c1, c2, c3);
1540                         zbufclip(zspan, zvlnr, f1, f3, f4, c1, c3, c4);
1541                 }
1542                 return;
1543         }
1544
1545         /* perspective division: HCS to ZCS */
1546         hoco_to_zco(zspan, vez, f1);
1547         hoco_to_zco(zspan, vez+4, f2);
1548         hoco_to_zco(zspan, vez+8, f3);
1549         hoco_to_zco(zspan, vez+12, f4);
1550
1551         zspan->zbuffunc(zspan, zvlnr, vez, vez+4, vez+8, vez+12);
1552 }
1553
1554
1555 /* ***************** ZBUFFER MAIN ROUTINES **************** */
1556
1557 void set_part_zbuf_clipflag(RenderPart *pa)
1558 {
1559         VertRen *ver=NULL;
1560         float minx, miny, maxx, maxy, wco;
1561         unsigned short clipclear;
1562         int v;
1563
1564         minx= (2*pa->disprect.xmin - R.winx-1)/(float)R.winx;
1565         maxx= (2*pa->disprect.xmax - R.winx+1)/(float)R.winx;
1566         miny= (2*pa->disprect.ymin - R.winy-1)/(float)R.winy;
1567         maxy= (2*pa->disprect.ymax - R.winy+1)/(float)R.winy;
1568         
1569         /* supports up to 4 threads this way */
1570         clipclear= ~(15 << 4*(pa->thread & 3));
1571         
1572         for(v=0; v<R.totvert; v++) {
1573                 if((v & 255)==0) ver= RE_findOrAddVert(&R, v);
1574                 else ver++;
1575                 
1576                 wco= ver->ho[3];
1577                 ver->flag &= clipclear;
1578                 
1579                 switch(pa->thread & 3) {
1580                         case 0:
1581                                 if( ver->ho[0] > maxx*wco) ver->flag |= 1;
1582                                 else if( ver->ho[0]< minx*wco) ver->flag |= 2;
1583                                 if( ver->ho[1] > maxy*wco) ver->flag |= 4;
1584                                 else if( ver->ho[1]< miny*wco) ver->flag |= 8;
1585                                 break;
1586                         case 1:
1587                                 if( ver->ho[0] > maxx*wco) ver->flag |= 16;
1588                                 else if( ver->ho[0]< minx*wco) ver->flag |= 32;
1589                                 if( ver->ho[1] > maxy*wco) ver->flag |= 64;
1590                                 else if( ver->ho[1]< miny*wco) ver->flag |= 128;
1591                                 break;
1592                         case 2:
1593                                 if( ver->ho[0] > maxx*wco) ver->flag |= 256;
1594                                 else if( ver->ho[0]< minx*wco) ver->flag |= 512;
1595                                 if( ver->ho[1] > maxy*wco) ver->flag |= 1024;
1596                                 else if( ver->ho[1]< miny*wco) ver->flag |= 2048;
1597                                 break;
1598                         case 3:
1599                                 if( ver->ho[0] > maxx*wco) ver->flag |= 4096;
1600                                 else if( ver->ho[0]< minx*wco) ver->flag |= 8192;
1601                                 if( ver->ho[1] > maxy*wco) ver->flag |= 16384;
1602                                 else if( ver->ho[1]< miny*wco) ver->flag |= 32768;
1603                                 break;
1604                 }
1605         }
1606 }
1607
1608 void zbuffer_solid(RenderPart *pa, unsigned int lay, short layflag)
1609 {
1610         ZSpan zspan;
1611         VlakRen *vlr= NULL;
1612         Material *ma=0;
1613         int v, zvlnr;
1614         unsigned short clipmask;
1615         short transp=0, env=0, wire=0;
1616
1617         zbuf_alloc_span(&zspan, pa->rectx, pa->recty);
1618         
1619         /* needed for transform from hoco to zbuffer co */
1620         zspan.zmulx=  ((float)R.winx)/2.0;
1621         zspan.zmuly=  ((float)R.winy)/2.0;
1622         if(R.osa) {
1623                 zspan.zofsx= -pa->disprect.xmin - R.jit[pa->sample][0];
1624                 zspan.zofsy= -pa->disprect.ymin - R.jit[pa->sample][1];
1625         }
1626         else {
1627                 zspan.zofsx= -pa->disprect.xmin;
1628                 zspan.zofsy= -pa->disprect.ymin;
1629         }
1630         
1631         /* the buffers */
1632         zspan.rectz= pa->rectz;
1633         zspan.rectp= pa->rectp;
1634         fillrect(pa->rectp, pa->rectx, pa->recty, 0);
1635         fillrect(pa->rectz, pa->rectx, pa->recty, 0x7FFFFFFF);
1636         
1637         /* filling methods */
1638         zspan.zbuffunc= zbufinvulGL4;
1639         zspan.zbuflinefunc= zbufline;
1640
1641         /* part clipflag, threaded */
1642         clipmask= (15 << 4*(pa->thread & 3));
1643
1644         for(v=0; v<R.totvlak; v++) {
1645
1646                 if((v & 255)==0) vlr= R.blovl[v>>8];
1647                 else vlr++;
1648                 
1649                 if((vlr->flag & R_VISIBLE) && (vlr->lay & lay)) {
1650                         if(vlr->mat!=ma) {
1651                                 ma= vlr->mat;
1652                                 transp= ma->mode & MA_ZTRA;
1653                                 env= (ma->mode & MA_ENV);
1654                                 wire= (ma->mode & MA_WIRE);
1655                                 
1656                                 if(ma->mode & MA_ZINV) zspan.zbuffunc= zbufinvulGLinv4;
1657                                 else zspan.zbuffunc= zbufinvulGL4;
1658                         }
1659                         
1660                         if(transp==0) {
1661                                 unsigned short partclip;
1662                                 
1663                                 /* partclipping doesn't need viewplane clipping */
1664                                 if(vlr->v4) partclip= vlr->v1->flag & vlr->v2->flag & vlr->v3->flag & vlr->v4->flag;
1665                                 else partclip= vlr->v1->flag & vlr->v2->flag & vlr->v3->flag;
1666                                 
1667                                 if((partclip & clipmask)==0) {
1668                                         
1669                                         if(env) zvlnr= 0;
1670                                         else zvlnr= v+1;
1671                                         
1672                                         if(wire) zbufclipwire(&zspan, zvlnr, vlr);
1673                                         else {
1674                                                 /* strands allow to be filled in as quad */
1675                                                 if(vlr->v4 && (vlr->flag & R_STRAND)) {
1676                                                         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);
1677                                                 }
1678                                                 else {
1679                                                         zbufclip(&zspan, zvlnr, vlr->v1->ho, vlr->v2->ho, vlr->v3->ho, vlr->v1->clip, vlr->v2->clip, vlr->v3->clip);
1680                                                         if(vlr->v4) {
1681                                                                 if(zvlnr) zvlnr+= 0x800000;
1682                                                                 zbufclip(&zspan, zvlnr, vlr->v1->ho, vlr->v3->ho, vlr->v4->ho, vlr->v1->clip, vlr->v3->clip, vlr->v4->clip);
1683                                                         }
1684                                                 }
1685                                         }
1686                                 }
1687                         }
1688                 }
1689         }
1690         
1691         zbuf_free_span(&zspan);
1692 }
1693
1694 typedef struct {
1695         float *vert;
1696         float hoco[4];
1697         int clip;
1698 } VertBucket;
1699
1700 /* warning, not threaded! */
1701 static int hashlist_projectvert(float *v1, float winmat[][4], float *hoco)
1702 {
1703         static VertBucket bucket[256], *buck;
1704         
1705         /* init static bucket */
1706         if(v1==NULL) {
1707                 memset(bucket, 0, 256*sizeof(VertBucket));
1708                 return 0;
1709         }
1710         
1711         buck= &bucket[ (((long)v1)/16) & 255 ];
1712         if(buck->vert==v1) {
1713                 QUATCOPY(hoco, buck->hoco);
1714                 return buck->clip;
1715         }
1716         
1717         projectvert(v1, winmat, hoco);
1718         buck->clip = testclip(hoco);
1719         buck->vert= v1;
1720         QUATCOPY(buck->hoco, hoco);
1721         return buck->clip;
1722 }
1723
1724 /* used for booth radio 'tool' as during render */
1725 void RE_zbufferall_radio(struct RadView *vw, RNode **rg_elem, int rg_totelem, Render *re)
1726 {
1727         ZSpan zspan;
1728         float hoco[4][4], winmat[4][4];
1729         int a, zvlnr;
1730         int c1, c2, c3, c4= 0;
1731
1732         if(rg_totelem==0) return;
1733
1734         hashlist_projectvert(NULL, winmat, NULL);
1735         
1736         /* needed for projectvert */
1737         MTC_Mat4MulMat4(winmat, vw->viewmat, vw->winmat);
1738
1739         zbuf_alloc_span(&zspan, vw->rectx, vw->recty);
1740         zspan.zmulx=  ((float)vw->rectx)/2.0;
1741         zspan.zmuly=  ((float)vw->recty)/2.0;
1742         zspan.zofsx= 0;
1743         zspan.zofsy= 0;
1744         
1745         /* the buffers */
1746         zspan.rectz= vw->rectz;
1747         zspan.rectp= vw->rect;
1748         fillrect(zspan.rectz, vw->rectx, vw->recty, 0x7FFFFFFF);
1749         fillrect(zspan.rectp, vw->rectx, vw->recty, 0xFFFFFF);
1750         
1751         /* filling methods */
1752         zspan.zbuffunc= zbufinvulGL4;
1753         
1754         if(rg_elem) {   /* radio tool */
1755                 RNode **re, *rn;
1756
1757                 re= rg_elem;
1758                 re+= (rg_totelem-1);
1759                 for(a= rg_totelem-1; a>=0; a--, re--) {
1760                         rn= *re;
1761                         if( (rn->f & RAD_SHOOT)==0 ) {    /* no shootelement */
1762                                 
1763                                 if( rn->f & RAD_TWOSIDED) zvlnr= a;
1764                                 else if( rn->f & RAD_BACKFACE) zvlnr= 0xFFFFFF; 
1765                                 else zvlnr= a;
1766                                 
1767                                 c1= hashlist_projectvert(rn->v1, winmat, hoco[0]);
1768                                 c2= hashlist_projectvert(rn->v2, winmat, hoco[1]);
1769                                 c3= hashlist_projectvert(rn->v3, winmat, hoco[2]);
1770                                 
1771                                 if(rn->v4) {
1772                                         c4= hashlist_projectvert(rn->v4, winmat, hoco[3]);
1773                                 }
1774         
1775                                 if(rn->v4)
1776                                         zbufclip4(&zspan, zvlnr, hoco[0], hoco[1], hoco[2], hoco[3], c1, c2, c3, c4);
1777                                 else
1778                                         zbufclip(&zspan, zvlnr, hoco[0], hoco[1], hoco[2], c1, c2, c3);
1779                         }
1780                 }
1781         }
1782         else {  /* radio render */
1783                 VlakRen *vlr=NULL;
1784                 RadFace *rf;
1785                 int totface=0;
1786                 
1787                 for(a=0; a<re->totvlak; a++) {
1788                         if((a & 255)==0) vlr= re->blovl[a>>8]; else vlr++;
1789                 
1790                         if(vlr->radface) {
1791                                 rf= vlr->radface;
1792                                 if( (rf->flag & RAD_SHOOT)==0 ) {    /* no shootelement */
1793                                         
1794                                         if( rf->flag & RAD_TWOSIDED) zvlnr= totface;
1795                                         else if( rf->flag & RAD_BACKFACE) zvlnr= 0xFFFFFF;      /* receives no energy, but is zbuffered */
1796                                         else zvlnr= totface;
1797                                         
1798                                         c1= hashlist_projectvert(vlr->v1->co, winmat, hoco[0]);
1799                                         c2= hashlist_projectvert(vlr->v2->co, winmat, hoco[1]);
1800                                         c3= hashlist_projectvert(vlr->v3->co, winmat, hoco[2]);
1801                                         
1802                                         if(vlr->v4) {
1803                                                 c4= hashlist_projectvert(vlr->v4->co, winmat, hoco[3]);
1804                                         }
1805                 
1806                                         if(vlr->v4)
1807                                                 zbufclip4(&zspan, zvlnr, hoco[0], hoco[1], hoco[2], hoco[3], c1, c2, c3, c4);
1808                                         else
1809                                                 zbufclip(&zspan, zvlnr, hoco[0], hoco[1], hoco[2], c1, c2, c3);
1810                                 }
1811                                 totface++;
1812                         }
1813                 }
1814         }
1815
1816         zbuf_free_span(&zspan);
1817 }
1818
1819 void zbuffer_shadow(Render *re, LampRen *lar, int *rectz, int size)
1820 {
1821         ZSpan zspan;
1822         VlakRen *vlr= NULL;
1823         Material *ma=0;
1824         int a, ok=1, lay= -1;
1825
1826         if(lar->mode & LA_LAYER) lay= lar->lay;
1827
1828         zbuf_alloc_span(&zspan, size, size);
1829         zspan.zmulx=  ((float)size)/2.0;
1830         zspan.zmuly=  ((float)size)/2.0;
1831         zspan.zofsx= 0.0f;
1832         zspan.zofsy= 0.0f;
1833         
1834         /* the buffers */
1835         zspan.rectz= rectz;
1836         fillrect(rectz, size, size, 0x7FFFFFFE);
1837         
1838         /* filling methods */
1839         zspan.zbuflinefunc= zbufline_onlyZ;
1840         zspan.zbuffunc= zbufinvulGL_onlyZ;
1841                                 
1842         for(a=0; a<re->totvlak; a++) {
1843
1844                 if((a & 255)==0) vlr= re->blovl[a>>8];
1845                 else vlr++;
1846
1847                 if(vlr->mat!= ma) {
1848                         ma= vlr->mat;
1849                         ok= 1;
1850                         if((ma->mode & MA_SHADBUF)==0) ok= 0;
1851                 }
1852                 
1853                 if(ok && (vlr->flag & R_VISIBLE) && (vlr->lay & lay)) {
1854                         if(ma->mode & MA_WIRE) zbufclipwire(&zspan, a+1, vlr);
1855                         else if(vlr->flag & R_STRAND) zbufclipwire(&zspan, a+1, vlr);
1856                         else {
1857                                 if(vlr->v4) 
1858                                         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);
1859                                 else
1860                                         zbufclip(&zspan, 0, vlr->v1->ho, vlr->v2->ho, vlr->v3->ho, vlr->v1->clip, vlr->v2->clip, vlr->v3->clip);
1861                         }
1862                 }
1863         }
1864         zbuf_free_span(&zspan);
1865 }
1866
1867
1868
1869 /* ******************** ABUF ************************* */
1870
1871 /**
1872  * Copy results from the solid face z buffering to the transparent
1873  * buffer.
1874  */
1875 static void copyto_abufz(RenderPart *pa, int *arectz, int sample)
1876 {
1877         PixStr *ps;
1878         int x, y, *rza;
1879         long *rd;
1880         
1881         /* now, in OSA the pixstructs contain all faces filled in */
1882         if(R.r.mode & R_OSA) fillrect(arectz, pa->rectx, pa->recty, 0x7FFFFFFF);
1883         else {
1884                 memcpy(arectz, pa->rectz, 4*pa->rectx*pa->recty);
1885                 return;
1886         }
1887                 
1888         rza= arectz;
1889         rd= pa->rectdaps;
1890
1891         sample= (1<<sample);
1892         
1893         for(y=0; y<pa->recty; y++) {
1894                 for(x=0; x<pa->rectx; x++) {
1895                         
1896                         if(*rd) {       
1897                                 ps= (PixStr *)(*rd);
1898
1899                                 while(ps) {
1900                                         if(sample & ps->mask) {
1901                                                 //printf("filled xy %d %d mask %d\n", x, y, sample);
1902                                                 *rza= ps->z;
1903                                                 break;
1904                                         }
1905                                         ps= ps->next;
1906                                 }
1907                         }
1908                         
1909                         rd++; rza++;
1910                 }
1911         }
1912 }
1913
1914
1915 /* ------------------------------------------------------------------------ */
1916
1917 /**
1918  * Do accumulation z buffering.
1919  */
1920
1921 static void zbuffer_abuf(RenderPart *pa, APixstr *APixbuf, ListBase *apsmbase, unsigned int lay, short layflag)
1922 {
1923         ZSpan zspan;
1924         Material *ma=0;
1925         VlakRen *vlr=NULL;
1926         float vec[3], hoco[4], mul, zval, fval;
1927         int v, zvlnr, zsample;
1928         unsigned short clipmask;
1929         
1930         zbuf_alloc_span(&zspan, pa->rectx, pa->recty);
1931         
1932         /* needed for transform from hoco to zbuffer co */
1933         zspan.zmulx=  ((float)R.winx)/2.0;
1934         zspan.zmuly=  ((float)R.winy)/2.0;
1935         zspan.zofsx= -pa->disprect.xmin;
1936         zspan.zofsy= -pa->disprect.ymin;
1937         
1938         /* the buffers */
1939         zspan.arectz= RE_mallocN(sizeof(int)*pa->rectx*pa->recty, "Arectz");
1940         zspan.apixbuf= APixbuf;
1941         zspan.apsmbase= apsmbase;
1942         
1943         /* filling methods */
1944         zspan.zbuffunc= zbufinvulAc4;
1945         zspan.zbuflinefunc= zbuflineAc;
1946         
1947         /* part clipflag, 4 threads */
1948         clipmask= (15 << 4*(pa->thread & 3));
1949         
1950         for(zsample=0; zsample<R.osa || R.osa==0; zsample++) {
1951                 
1952                 copyto_abufz(pa, zspan.arectz, zsample);        /* init zbuffer */
1953                 zspan.mask= 1<<zsample;
1954                 
1955                 if(R.r.mode & R_OSA) {
1956                         zspan.zofsx= -pa->disprect.xmin-R.jit[zsample][0];
1957                         zspan.zofsy= -pa->disprect.ymin-R.jit[zsample][1];
1958                 }
1959                 
1960                 for(v=0; v<R.totvlak; v++) {
1961                         if((v & 255)==0)
1962                                 vlr= R.blovl[v>>8];
1963                         else vlr++;
1964                         
1965                         ma= vlr->mat;
1966                         if(ma->mode & (MA_ZTRA)) {
1967                                 if((vlr->flag & R_VISIBLE) && (vlr->lay & lay)) {
1968                                         unsigned short partclip;
1969                                         
1970                                         /* partclipping doesn't need viewplane clipping */
1971                                         if(vlr->v4) partclip= vlr->v1->flag & vlr->v2->flag & vlr->v3->flag & vlr->v4->flag;
1972                                         else partclip= vlr->v1->flag & vlr->v2->flag & vlr->v3->flag;
1973                                         
1974                                         if((partclip & clipmask)==0) {
1975                                                 /* a little advantage for transp rendering (a z offset) */
1976                                                 if( ma->zoffs != 0.0) {
1977                                                         mul= 0x7FFFFFFF;
1978                                                         zval= mul*(1.0+vlr->v1->ho[2]/vlr->v1->ho[3]);
1979
1980                                                         VECCOPY(vec, vlr->v1->co);
1981                                                         /* z is negative, otherwise its being clipped */ 
1982                                                         vec[2]-= ma->zoffs;
1983                                                         projectverto(vec, R.winmat, hoco);
1984                                                         fval= mul*(1.0+hoco[2]/hoco[3]);
1985
1986                                                         zspan.polygon_offset= (int) fabs(zval - fval );
1987                                                 }
1988                                                 else zspan.polygon_offset= 0;
1989                                                 
1990                                                 zvlnr= v+1;
1991                         
1992                                                 if(ma->mode & (MA_WIRE)) zbufclipwire(&zspan, zvlnr, vlr);
1993                                                 else {
1994                                                         if(vlr->v4 && (vlr->flag & R_STRAND)) {
1995                                                                 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);
1996                                                         }
1997                                                         else {
1998                                                                 zbufclip(&zspan, zvlnr, vlr->v1->ho, vlr->v2->ho, vlr->v3->ho, vlr->v1->clip, vlr->v2->clip, vlr->v3->clip);
1999                                                                 if(vlr->v4) {
2000                                                                         zvlnr+= 0x800000;
2001                                                                         zbufclip(&zspan, zvlnr, vlr->v1->ho, vlr->v3->ho, vlr->v4->ho, vlr->v1->clip, vlr->v3->clip, vlr->v4->clip);
2002                                                                 }
2003                                                         }
2004                                                 }
2005                                         }
2006                                 }
2007                                 if( (v & 255)==255) 
2008                                         if(R.test_break()) 
2009                                                 break; 
2010                         }
2011                 }
2012                 
2013                 if((R.r.mode & R_OSA)==0) break;
2014                 if(R.test_break()) break;
2015         }
2016         
2017         RE_freeN(zspan.arectz);
2018         zbuf_free_span(&zspan);
2019
2020 }
2021
2022 static int vergzvlak(const void *a1, const void *a2)
2023 {
2024         const int *x1=a1, *x2=a2;
2025
2026         if( x1[0] < x2[0] ) return 1;
2027         else if( x1[0] > x2[0]) return -1;
2028         return 0;
2029 }
2030
2031 /**
2032 * Shade this face at this location in SCS.
2033  */
2034 static void shadetrapixel(RenderPart *pa, float x, float y, int z, int facenr, int mask, float *fcol)
2035 {
2036         float rco[3];
2037         
2038         if( (facenr & 0x7FFFFF) > R.totvlak) {
2039                 printf("error in shadetrapixel nr: %d\n", (facenr & 0x7FFFFF));
2040                 return;
2041         }
2042         if(R.r.mode & R_OSA) {
2043                 VlakRen *vlr= RE_findOrAddVlak(&R, (facenr-1) & 0x7FFFFF);
2044                 float accumcol[4]={0,0,0,0}, tot=0.0;
2045                 int a;
2046                 
2047                 if(vlr->flag & R_FULL_OSA) {
2048                         for(a=0; a<R.osa; a++) {
2049                                 if(mask & (1<<a)) {
2050                                         shadepixel(pa, x+R.jit[a][0], y+R.jit[a][1], z, facenr, 1<<a, fcol, rco);
2051                                         accumcol[0]+= fcol[0];
2052                                         accumcol[1]+= fcol[1];
2053                                         accumcol[2]+= fcol[2];
2054                                         accumcol[3]+= fcol[3];
2055                                         tot+= 1.0;
2056                                 }
2057                         }
2058                         tot= 1.0/tot;
2059                         fcol[0]= accumcol[0]*tot;
2060                         fcol[1]= accumcol[1]*tot;
2061                         fcol[2]= accumcol[2]*tot;
2062                         fcol[3]= accumcol[3]*tot;
2063                 }
2064                 else {
2065                         int b= R.samples->centmask[mask];
2066                         x= x+R.samples->centLut[b & 15];
2067                         y= y+R.samples->centLut[b>>4];
2068                         shadepixel(pa, x, y, z, facenr, mask, fcol, rco);
2069         
2070                 }
2071         }
2072         else shadepixel(pa, x, y, z, facenr, mask, fcol, rco);
2073 }
2074
2075 static int addtosampcol(float *sampcol, float *fcol, int mask)
2076 {
2077         int a, retval = R.osa;
2078         
2079         for(a=0; a < R.osa; a++) {
2080                 if(mask & (1<<a)) addAlphaUnderFloat(sampcol, fcol);
2081                 if(sampcol[3]>0.999) retval--;
2082                 sampcol+= 4;
2083         }
2084         return retval;
2085 }
2086
2087 #define MAX_ZROW        1000
2088 /* main render call to fill in pass the full transparent layer */
2089
2090 void zbuffer_transp_shade(RenderPart *pa, float *pass, unsigned int lay, short layflag)
2091 {
2092         APixstr *APixbuf;      /* Zbuffer: linked list of face samples */
2093         APixstr *ap, *apn;
2094         ListBase apsmbase={NULL, NULL};
2095         float col[4], fcol[4], tempcol[4], sampcol[16*4], *scol, accumcol[4];
2096         float fac, alpha[32];
2097         int x, y, a, zrow[MAX_ZROW][3], totface, nr;
2098         int sval;
2099         
2100         /* looks nicer for calling code */
2101         if(R.test_break())
2102                 return;
2103         
2104         APixbuf= RE_callocN(pa->rectx*pa->recty*sizeof(APixstr), "APixbuf");
2105         
2106         if(R.osa>16) {
2107                 printf("abufsetrow: osa too large\n");
2108                 G.afbreek= 1;
2109                 return;
2110         }
2111         
2112         /* alpha LUT */
2113         if(R.r.mode & R_OSA ) {
2114                 fac= (1.0/(float)R.osa);
2115                 for(a=0; a<=R.osa; a++) {
2116                         alpha[a]= (float)a*fac;
2117                 }
2118         }
2119         
2120         /* fill the Apixbuf */
2121         zbuffer_abuf(pa, APixbuf, &apsmbase, lay, layflag);
2122         
2123         /* render tile */
2124         ap= APixbuf;
2125         
2126         for(y=pa->disprect.ymin; y<pa->disprect.ymax; y++) {
2127                 for(x=pa->disprect.xmin; x<pa->disprect.xmax; x++, ap++, pass+=4) {
2128
2129                         if(ap->p[0]) {
2130                                 /* sort in z */
2131                                 totface= 0;
2132                                 apn= ap;
2133                                 while(apn) {
2134                                         for(a=0; a<4; a++) {
2135                                                 if(apn->p[a]) {
2136                                                         zrow[totface][0]= apn->z[a];
2137                                                         zrow[totface][1]= apn->p[a];
2138                                                         zrow[totface][2]= apn->mask[a];
2139                                                         totface++;
2140                                                         if(totface>=MAX_ZROW) totface= MAX_ZROW-1;
2141                                                 }
2142                                                 else break;
2143                                         }
2144                                         apn= apn->next;
2145                                 }
2146                                 
2147                                 if(totface==1) {
2148                                         
2149                                         shadetrapixel(pa, (float)x, (float)y, zrow[0][0], zrow[0][1], zrow[0][2], fcol);
2150                                         
2151                                         nr= count_mask(zrow[0][2]);
2152                                         if( (R.r.mode & R_OSA) && nr<R.osa) {
2153                                                 fac= alpha[ nr ];
2154                                                 col[0]= (fcol[0]*fac);
2155                                                 col[1]= (fcol[1]*fac);
2156                                                 col[2]= (fcol[2]*fac);
2157                                                 col[3]= (fcol[3]*fac);
2158                                         }
2159                                         else {
2160                                                 col[0]= fcol[0];
2161                                                 col[1]= fcol[1];
2162                                                 col[2]= fcol[2];
2163                                                 col[3]= fcol[3];
2164                                         }
2165                                 }
2166                                 else {
2167                                         col[0]= col[1]= col[2]= col[3]= 0.0f;
2168                                         
2169                                         if(totface==2) {
2170                                                 if(zrow[0][0] < zrow[1][0]) {
2171                                                         a= zrow[0][0]; zrow[0][0]= zrow[1][0]; zrow[1][0]= a;
2172                                                         a= zrow[0][1]; zrow[0][1]= zrow[1][1]; zrow[1][1]= a;
2173                                                         a= zrow[0][2]; zrow[0][2]= zrow[1][2]; zrow[1][2]= a;
2174                                                 }
2175                                                 
2176                                         }
2177                                         else {  /* totface>2 */
2178                                                 qsort(zrow, totface, sizeof(int)*3, vergzvlak);
2179                                         }
2180                                         
2181                                         /* join when pixels are adjacent */
2182                                         
2183                                         while(totface>0) {
2184                                                 totface--;
2185                                                 
2186                                                 shadetrapixel(pa, (float)x, (float)y, zrow[totface][0], zrow[totface][1], zrow[totface][2], fcol);
2187                                                 
2188                                                 a= count_mask(zrow[totface][2]);
2189                                                 if( (R.r.mode & R_OSA ) && a<R.osa) {
2190                                                         if(totface>0) {
2191                                                                 memset(sampcol, 0, 4*sizeof(float)*R.osa);
2192                                                                 sval= addtosampcol(sampcol, fcol, zrow[totface][2]);
2193                                                                 
2194                                                                 /* sval==0: alpha completely full */
2195                                                                 while( (sval != 0) && (totface>0) ) {
2196                                                                         a= count_mask(zrow[totface-1][2]);
2197                                                                         if(a==R.osa) break;
2198                                                                         totface--;
2199                                                                         
2200                                                                         shadetrapixel(pa, (float)x, (float)y, zrow[totface][0], zrow[totface][1], zrow[totface][2], fcol);
2201                                                                         sval= addtosampcol(sampcol, fcol, zrow[totface][2]);
2202                                                                 }
2203                                                                 
2204                                                                 scol= sampcol;
2205                                                                 accumcol[0]= scol[0]; accumcol[1]= scol[1];
2206                                                                 accumcol[2]= scol[2]; accumcol[3]= scol[3];
2207                                                                 scol+= 4;
2208                                                                 for(a=1; a<R.osa; a++, scol+=4) {
2209                                                                         accumcol[0]+= scol[0]; accumcol[1]+= scol[1];
2210                                                                         accumcol[2]+= scol[2]; accumcol[3]+= scol[3];
2211                                                                 }
2212                                                                 tempcol[0]= accumcol[0]/R.osa;
2213                                                                 tempcol[1]= accumcol[1]/R.osa;
2214                                                                 tempcol[2]= accumcol[2]/R.osa;
2215                                                                 tempcol[3]= accumcol[3]/R.osa;
2216                                                                 
2217                                                                 addAlphaUnderFloat(col, tempcol);
2218                                                                 
2219                                                         }
2220                                                         else {
2221                                                                 fac= alpha[a];
2222                                                                 fcol[0]= (fcol[0]*fac);
2223                                                                 fcol[1]= (fcol[1]*fac);
2224                                                                 fcol[2]= (fcol[2]*fac);
2225                                                                 fcol[3]= (fcol[3]*fac);
2226                                                                 addAlphaUnderFloat(col, fcol);
2227                                                         }
2228                                                 }       
2229                                                 else addAlphaUnderFloat(col, fcol);     /* no osa or full pixel with same face? */
2230                                                 
2231                                                 if(col[3]>=0.999) break;
2232                                         }
2233                                 }
2234                                 if(col[3]!=0.0) addAlphaOverFloat(pass, col);
2235                         }
2236                 }
2237         }
2238
2239         RE_freeN(APixbuf);
2240         freepsA(&apsmbase);     
2241
2242 }
2243
2244 /* *************** */
2245
2246 /* uses part zbuffer values to convert into distances from camera in renderlayer */
2247 void convert_zbuf_to_distbuf(RenderPart *pa, RenderLayer *rl)
2248 {
2249         float *rectzf, zco;
2250         int a, *rectz, ortho= R.r.mode & R_ORTHO;
2251         
2252         if(pa->rectz==NULL) return;
2253         if(rl->rectz==NULL) {
2254                 printf("called convert zbuf wrong...\n");
2255                 return;
2256         }
2257         rectzf= rl->rectz;
2258         rectz= pa->rectz;
2259         
2260         for(a=pa->rectx*pa->recty; a>0; a--, rectz++, rectzf++) {
2261                 if(*rectz==0x7FFFFFFF)
2262                         *rectzf= 10e10;
2263                 else {
2264                         /* inverse of zbuf calc: zbuf = MAXZ*hoco_z/hoco_w */
2265                         /* or: (R.winmat[3][2] - zco*R.winmat[3][3])/(R.winmat[2][2] - R.winmat[2][3]*zco); */
2266                         /* if ortho [2][3] is zero, else [3][3] is zero */
2267                         
2268                         zco= ((float)*rectz)/2147483647.0f;
2269                         if(ortho)
2270                                 *rectzf= (R.winmat[3][2] - zco*R.winmat[3][3])/(R.winmat[2][2]);
2271                         else
2272                                 *rectzf= (R.winmat[3][2])/(R.winmat[2][2] - R.winmat[2][3]*zco);
2273                 }
2274         }
2275 }
2276
2277
2278 /* end of zbuf.c */
2279
2280
2281
2282