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