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