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