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