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