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