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