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