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