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