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