cfbdf04d75a1a0638dc575da9e84ab0be55ce176
[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, 1] means a clipping.
1595  * Note: uses globals.
1596  * \param v1 start coordinate s
1597  * \param v2 target coordinate t
1598  * \param b1 
1599  * \param b2 
1600  * \param b3
1601  * \param a index for coordinate (x, y, or z)
1602  */
1603
1604 static void clippyra(float *labda, float *v1, float *v2, int *b2, int *b3, int a, float clipcrop)
1605 {
1606         float da, dw, u1=0.0, u2=1.0;
1607         float v13;
1608         
1609         labda[0]= -1.0;
1610         labda[1]= -1.0;
1611
1612         da= v2[a]-v1[a];
1613         /* prob; we clip slightly larger, osa renders add 2 pixels on edges, should become variable? */
1614         /* or better; increase r.winx/y size, but thats quite a complex one. do it later */
1615         if (a==2) {
1616                 dw= (v2[3]-v1[3]);
1617                 v13= v1[3];
1618         }
1619         else {
1620                 dw= clipcrop*(v2[3]-v1[3]);
1621                 v13= clipcrop*v1[3];
1622         }       
1623         /* according the original article by Liang&Barsky, for clipping of
1624          * homogenous coordinates with viewplane, the value of "0" is used instead of "-w" .
1625          * This differs from the other clipping cases (like left or top) and I considered
1626          * it to be not so 'homogenic'. But later it has proven to be an error,
1627          * who would have thought that of L&B!
1628          */
1629
1630         if (cliptestf(-da, -dw, v13, v1[a], &u1, &u2)) {
1631                 if (cliptestf(da, -dw, v13, -v1[a], &u1, &u2)) {
1632                         *b3=1;
1633                         if (u2<1.0f) {
1634                                 labda[1]= u2;
1635                                 *b2=1;
1636                         }
1637                         else labda[1]=1.0;  /* u2 */
1638                         if (u1>0.0f) {
1639                                 labda[0] = u1;
1640                                 *b2 = 1;
1641                         }
1642                         else {
1643                                 labda[0] = 0.0;
1644                         }
1645                 }
1646         }
1647 }
1648
1649 /**
1650  * (make vertex pyramide clip)
1651  * Checks labda and uses this to make decision about clipping the line
1652  * segment from v1 to v2. labda is the factor by which the vector is
1653  * cut. ( calculate s + l * ( t - s )). The result is appended to the
1654  * vertex list of this face.
1655  * 
1656  * 
1657  * \param v1 start coordinate s
1658  * \param v2 target coordinate t
1659  * \param b1 
1660  * \param b2 
1661  * \param clve vertex vector.
1662  */
1663
1664 static void makevertpyra(float *vez, float *labda, float **trias, float *v1, float *v2, int *b1, int *clve)
1665 {
1666         float l1, l2, *adr;
1667
1668         l1= labda[0];
1669         l2= labda[1];
1670
1671         if (l1!= -1.0f) {
1672                 if (l1!= 0.0f) {
1673                         adr= vez+4*(*clve);
1674                         trias[*b1]=adr;
1675                         (*clve)++;
1676                         adr[0]= v1[0]+l1*(v2[0]-v1[0]);
1677                         adr[1]= v1[1]+l1*(v2[1]-v1[1]);
1678                         adr[2]= v1[2]+l1*(v2[2]-v1[2]);
1679                         adr[3]= v1[3]+l1*(v2[3]-v1[3]);
1680                 } 
1681                 else trias[*b1]= v1;
1682                 
1683                 (*b1)++;
1684         }
1685         if (l2!= -1.0f) {
1686                 if (l2!= 1.0f) {
1687                         adr= vez+4*(*clve);
1688                         trias[*b1]=adr;
1689                         (*clve)++;
1690                         adr[0]= v1[0]+l2*(v2[0]-v1[0]);
1691                         adr[1]= v1[1]+l2*(v2[1]-v1[1]);
1692                         adr[2]= v1[2]+l2*(v2[2]-v1[2]);
1693                         adr[3]= v1[3]+l2*(v2[3]-v1[3]);
1694                         (*b1)++;
1695                 }
1696         }
1697 }
1698
1699 /* ------------------------------------------------------------------------- */
1700
1701 void projectverto(const float v1[3], float winmat[][4], float adr[4])
1702 {
1703         /* calcs homogenic coord of vertex v1 */
1704         float x, y, z;
1705
1706         x = v1[0];
1707         y = v1[1];
1708         z = v1[2];
1709         adr[0] = x * winmat[0][0] + z * winmat[2][0] + winmat[3][0];
1710         adr[1] = y * winmat[1][1] + z * winmat[2][1] + winmat[3][1];
1711         adr[2] =                    z * winmat[2][2] + winmat[3][2];
1712         adr[3] =                    z * winmat[2][3] + winmat[3][3];
1713
1714         //printf("hoco %f %f %f %f\n", adr[0], adr[1], adr[2], adr[3]);
1715 }
1716
1717 /* ------------------------------------------------------------------------- */
1718
1719 void projectvert(const float v1[3], float winmat[][4], float adr[4])
1720 {
1721         /* calcs homogenic coord of vertex v1 */
1722         float x, y, z;
1723
1724         x = v1[0];
1725         y = v1[1];
1726         z = v1[2];
1727         adr[0] = x * winmat[0][0] + y * winmat[1][0] + z * winmat[2][0] + winmat[3][0];
1728         adr[1] = x * winmat[0][1] + y * winmat[1][1] + z * winmat[2][1] + winmat[3][1];
1729         adr[2] = x * winmat[0][2] + y * winmat[1][2] + z * winmat[2][2] + winmat[3][2];
1730         adr[3] = x * winmat[0][3] + y * winmat[1][3] + z * winmat[2][3] + winmat[3][3];
1731 }
1732
1733 /* ------------------------------------------------------------------------- */
1734
1735 #define ZBUF_PROJECT_CACHE_SIZE 256
1736
1737 typedef struct ZbufProjectCache {
1738         int index, clip;
1739         float ho[4];
1740 } ZbufProjectCache;
1741
1742 static void zbuf_project_cache_clear(ZbufProjectCache *cache, int size)
1743 {
1744         int i;
1745
1746         if (size > ZBUF_PROJECT_CACHE_SIZE)
1747                 size= ZBUF_PROJECT_CACHE_SIZE;
1748
1749         memset(cache, 0, sizeof(ZbufProjectCache)*size);
1750         for (i=0; i<size; i++)
1751                 cache[i].index= -1;
1752 }
1753
1754 static int zbuf_shadow_project(ZbufProjectCache *cache, int index, float winmat[][4], float *co, float *ho)
1755 {
1756         int cindex= index & 255;
1757
1758         if (cache[cindex].index == index) {
1759                 copy_v4_v4(ho, cache[cindex].ho);
1760                 return cache[cindex].clip;
1761         }
1762         else {
1763                 int clipflag;
1764                 projectvert(co, winmat, ho);
1765                 clipflag= testclip(ho);
1766
1767                 copy_v4_v4(cache[cindex].ho, ho);
1768                 cache[cindex].clip= clipflag;
1769                 cache[cindex].index= index;
1770
1771                 return clipflag;
1772         }
1773 }
1774
1775 static void zbuffer_part_bounds(int winx, int winy, RenderPart *pa, float *bounds)
1776 {
1777         bounds[0]= (2*pa->disprect.xmin - winx-1)/(float)winx;
1778         bounds[1]= (2*pa->disprect.xmax - winx+1)/(float)winx;
1779         bounds[2]= (2*pa->disprect.ymin - winy-1)/(float)winy;
1780         bounds[3]= (2*pa->disprect.ymax - winy+1)/(float)winy;
1781 }
1782
1783 static int zbuf_part_project(ZbufProjectCache *cache, int index, float winmat[][4], float *bounds, float *co, float *ho)
1784 {
1785         float vec[3];
1786         int cindex= index & 255;
1787
1788         if (cache[cindex].index == index) {
1789                 copy_v4_v4(ho, cache[cindex].ho);
1790                 return cache[cindex].clip;
1791         }
1792         else {
1793                 float wco;
1794                 int clipflag= 0;
1795                 copy_v3_v3(vec, co);
1796                 projectvert(co, winmat, ho);
1797
1798                 wco= ho[3];
1799                 if (ho[0] < bounds[0]*wco) clipflag |= 1;
1800                 else if (ho[0] > bounds[1]*wco) clipflag |= 2;
1801                 if (ho[1] > bounds[3]*wco) clipflag |= 4;
1802                 else if (ho[1] < bounds[2]*wco) clipflag |= 8;
1803
1804                 copy_v4_v4(cache[cindex].ho, ho);
1805                 cache[cindex].clip= clipflag;
1806                 cache[cindex].index= index;
1807
1808                 return clipflag;
1809         }
1810 }
1811
1812 void zbuf_render_project(float winmat[][4], const float co[3], float ho[4])
1813 {
1814         float vec[3];
1815
1816         copy_v3_v3(vec, co);
1817         projectvert(vec, winmat, ho);
1818 }
1819
1820 void zbuf_make_winmat(Render *re, float winmat[][4])
1821 {
1822         if (re->r.mode & R_PANORAMA) {
1823                 float panomat[4][4]= MAT4_UNITY;
1824
1825                 panomat[0][0]= re->panoco;
1826                 panomat[0][2]= re->panosi;
1827                 panomat[2][0]= -re->panosi;
1828                 panomat[2][2]= re->panoco;
1829
1830                 mult_m4_m4m4(winmat, re->winmat, panomat);
1831         }
1832         else
1833                 copy_m4_m4(winmat, re->winmat);
1834 }
1835
1836 /* do zbuffering and clip, f1 f2 f3 are hocos, c1 c2 c3 are clipping flags */
1837
1838 void zbufclip(ZSpan *zspan, int obi, int zvlnr, float *f1, float *f2, float *f3, int c1, int c2, int c3)
1839 {
1840         float *vlzp[32][3], labda[3][2];
1841         float vez[400], *trias[40];
1842         
1843         if (c1 | c2 | c3) {     /* not in middle */
1844                 if (c1 & c2 & c3) {     /* completely out */
1845                         return;
1846                 }
1847                 else {  /* clipping */
1848                         int arg, v, b, clipflag[3], b1, b2, b3, c4, clve=3, clvlo, clvl=1;
1849
1850                         vez[0]= f1[0]; vez[1]= f1[1]; vez[2]= f1[2]; vez[3]= f1[3];
1851                         vez[4]= f2[0]; vez[5]= f2[1]; vez[6]= f2[2]; vez[7]= f2[3];
1852                         vez[8]= f3[0]; vez[9]= f3[1]; vez[10]= f3[2];vez[11]= f3[3];
1853
1854                         vlzp[0][0]= vez;
1855                         vlzp[0][1]= vez+4;
1856                         vlzp[0][2]= vez+8;
1857
1858                         clipflag[0]= ( (c1 & 48) | (c2 & 48) | (c3 & 48) );
1859                         if (clipflag[0]==0) {   /* othwerwise it needs to be calculated again, after the first (z) clip */
1860                                 clipflag[1]= ( (c1 & 3) | (c2 & 3) | (c3 & 3) );
1861                                 clipflag[2]= ( (c1 & 12) | (c2 & 12) | (c3 & 12) );
1862                         }
1863                         else clipflag[1]=clipflag[2]= 0;
1864                         
1865                         for (b=0;b<3;b++) {
1866                                 
1867                                 if (clipflag[b]) {
1868                                 
1869                                         clvlo= clvl;
1870                                         
1871                                         for (v=0; v<clvlo; v++) {
1872                                         
1873                                                 if (vlzp[v][0]!=NULL) { /* face is still there */
1874                                                         b2= b3 =0;      /* clip flags */
1875
1876                                                         if (b==0) arg= 2;
1877                                                         else if (b==1) arg= 0;
1878                                                         else arg= 1;
1879                                                         
1880                                                         clippyra(labda[0], vlzp[v][0], vlzp[v][1], &b2, &b3, arg, zspan->clipcrop);
1881                                                         clippyra(labda[1], vlzp[v][1], vlzp[v][2], &b2, &b3, arg, zspan->clipcrop);
1882                                                         clippyra(labda[2], vlzp[v][2], vlzp[v][0], &b2, &b3, arg, zspan->clipcrop);
1883
1884                                                         if (b2==0 && b3==1) {
1885                                                                 /* completely 'in', but we copy because of last for () loop in this section */;
1886                                                                 vlzp[clvl][0]= vlzp[v][0];
1887                                                                 vlzp[clvl][1]= vlzp[v][1];
1888                                                                 vlzp[clvl][2]= vlzp[v][2];
1889                                                                 vlzp[v][0]= NULL;
1890                                                                 clvl++;
1891                                                         }
1892                                                         else if (b3==0) {
1893                                                                 vlzp[v][0]= NULL;
1894                                                                 /* completely 'out' */;
1895                                                         }
1896                                                         else {
1897                                                                 b1=0;
1898                                                                 makevertpyra(vez, labda[0], trias, vlzp[v][0], vlzp[v][1], &b1, &clve);
1899                                                                 makevertpyra(vez, labda[1], trias, vlzp[v][1], vlzp[v][2], &b1, &clve);
1900                                                                 makevertpyra(vez, labda[2], trias, vlzp[v][2], vlzp[v][0], &b1, &clve);
1901
1902                                                                 /* after front clip done: now set clip flags */
1903                                                                 if (b==0) {
1904                                                                         clipflag[1]= clipflag[2]= 0;
1905                                                                         f1= vez;
1906                                                                         for (b3=0; b3<clve; b3++) {
1907                                                                                 c4= testclip(f1);
1908                                                                                 clipflag[1] |= (c4 & 3);
1909                                                                                 clipflag[2] |= (c4 & 12);
1910                                                                                 f1+= 4;
1911                                                                         }
1912                                                                 }
1913                                                                 
1914                                                                 vlzp[v][0]= NULL;
1915                                                                 if (b1>2) {
1916                                                                         for (b3=3; b3<=b1; b3++) {
1917                                                                                 vlzp[clvl][0]= trias[0];
1918                                                                                 vlzp[clvl][1]= trias[b3-2];
1919                                                                                 vlzp[clvl][2]= trias[b3-1];
1920                                                                                 clvl++;
1921                                                                         }
1922                                                                 }
1923                                                         }
1924                                                 }
1925                                         }
1926                                 }
1927                         }
1928
1929                         /* warning, this should never happen! */
1930                         if (clve>38 || clvl>31) printf("clip overflow: clve clvl %d %d\n", clve, clvl);
1931
1932                         /* perspective division */
1933                         f1=vez;
1934                         for (c1=0;c1<clve;c1++) {
1935                                 hoco_to_zco(zspan, f1, f1);
1936                                 f1+=4;
1937                         }
1938                         for (b=1;b<clvl;b++) {
1939                                 if (vlzp[b][0]) {
1940                                         zspan->zbuffunc(zspan, obi, zvlnr, vlzp[b][0], vlzp[b][1], vlzp[b][2], NULL);
1941                                 }
1942                         }
1943                         return;
1944                 }
1945         }
1946
1947         /* perspective division: HCS to ZCS */
1948         hoco_to_zco(zspan, vez, f1);
1949         hoco_to_zco(zspan, vez+4, f2);
1950         hoco_to_zco(zspan, vez+8, f3);
1951         zspan->zbuffunc(zspan, obi, zvlnr, vez, vez+4, vez+8, NULL);
1952 }
1953
1954 void zbufclip4(ZSpan *zspan, int obi, int zvlnr, float *f1, float *f2, float *f3, float *f4, int c1, int c2, int c3, int c4)
1955 {
1956         float vez[16];
1957         
1958         if (c1 | c2 | c3 | c4) {        /* not in middle */
1959                 if (c1 & c2 & c3 & c4) {        /* completely out */
1960                         return;
1961                 }
1962                 else {  /* clipping */
1963                         zbufclip(zspan, obi, zvlnr, f1, f2, f3, c1, c2, c3);
1964                         zbufclip(zspan, obi, zvlnr, f1, f3, f4, c1, c3, c4);
1965                 }
1966                 return;
1967         }
1968
1969         /* perspective division: HCS to ZCS */
1970         hoco_to_zco(zspan, vez, f1);
1971         hoco_to_zco(zspan, vez+4, f2);
1972         hoco_to_zco(zspan, vez+8, f3);
1973         hoco_to_zco(zspan, vez+12, f4);
1974
1975         zspan->zbuffunc(zspan, obi, zvlnr, vez, vez+4, vez+8, vez+12);
1976 }
1977
1978 /* ************** ZMASK ******************************** */
1979
1980 #define EXTEND_PIXEL(a) if (temprectp[a]) {z+= rectz[a]; tot++;}
1981
1982 /* changes the zbuffer to be ready for z-masking: applies an extend-filter, and then clears */
1983 static void zmask_rect(int *rectz, int *rectp, int xs, int ys, int neg)
1984 {
1985         int len=0, x, y;
1986         int *temprectp;
1987         int row1, row2, row3, *curp, *curz;
1988         
1989         temprectp= MEM_dupallocN(rectp);
1990         
1991         /* extend: if pixel is not filled in, we check surrounding pixels and average z value  */
1992         
1993         for (y=1; y<=ys; y++) {
1994                 /* setup row indices */
1995                 row1= (y-2)*xs;
1996                 row2= row1 + xs;
1997                 row3= row2 + xs;
1998                 if (y==1)
1999                         row1= row2;
2000                 else if (y==ys)
2001                         row3= row2;
2002                 
2003                 curp= rectp + (y-1)*xs;
2004                 curz= rectz + (y-1)*xs;
2005                 
2006                 for (x=0; x<xs; x++, curp++, curz++) {
2007                         if (curp[0]==0) {
2008                                 int tot= 0;
2009                                 float z= 0.0f;
2010                                 
2011                                 EXTEND_PIXEL(row1);
2012                                 EXTEND_PIXEL(row2);
2013                                 EXTEND_PIXEL(row3);
2014                                 EXTEND_PIXEL(row1 + 1);
2015                                 EXTEND_PIXEL(row3 + 1);
2016                                 if (x!=xs-1) {
2017                                         EXTEND_PIXEL(row1 + 2);
2018                                         EXTEND_PIXEL(row2 + 2);
2019                                         EXTEND_PIXEL(row3 + 2);
2020                                 }                                       
2021                                 if (tot) {
2022                                         len++;
2023                                         curz[0]= (int)(z/(float)tot);
2024                                         curp[0]= -1;    /* env */
2025                                 }
2026                         }
2027                         
2028                         if (x!=0) {
2029                                 row1++; row2++; row3++;
2030                         }
2031                 }
2032         }
2033
2034         MEM_freeN(temprectp);
2035         
2036         if (neg); /* z values for negative are already correct */
2037         else {
2038                 /* clear not filled z values */
2039                 for (len= xs*ys -1; len>=0; len--) {
2040                         if (rectp[len]==0) {
2041                                 rectz[len] = -0x7FFFFFFF;
2042                                 rectp[len]= -1; /* env code */
2043                         }       
2044                 }
2045         }
2046 }
2047
2048
2049
2050
2051 /* ***************** ZBUFFER MAIN ROUTINES **************** */
2052
2053 void zbuffer_solid(RenderPart *pa, RenderLayer *rl, void(*fillfunc)(RenderPart*, ZSpan*, int, void*), void *data)
2054 {
2055         ZbufProjectCache cache[ZBUF_PROJECT_CACHE_SIZE];
2056         ZSpan zspans[16], *zspan; /* 16 = RE_MAX_OSA */
2057         VlakRen *vlr= NULL;
2058         VertRen *v1, *v2, *v3, *v4;
2059         Material *ma=0;
2060         ObjectInstanceRen *obi;
2061         ObjectRen *obr;
2062         float obwinmat[4][4], winmat[4][4], bounds[4];
2063         float ho1[4], ho2[4], ho3[4], ho4[4]={0};
2064         unsigned int lay= rl->lay, lay_zmask= rl->lay_zmask;
2065         int i, v, zvlnr, zsample, samples, c1, c2, c3, c4=0;
2066         short nofill=0, env=0, wire=0, zmaskpass=0;
2067         short all_z= (rl->layflag & SCE_LAY_ALL_Z) && !(rl->layflag & SCE_LAY_ZMASK);
2068         short neg_zmask= (rl->layflag & SCE_LAY_ZMASK) && (rl->layflag & SCE_LAY_NEG_ZMASK);
2069
2070         zbuf_make_winmat(&R, winmat);
2071         
2072         samples= (R.osa? R.osa: 1);
2073         samples= MIN2(4, samples-pa->sample);
2074
2075         for (zsample=0; zsample<samples; zsample++) {
2076                 zspan= &zspans[zsample];
2077
2078                 zbuffer_part_bounds(R.winx, R.winy, pa, bounds);
2079                 zbuf_alloc_span(zspan, pa->rectx, pa->recty, R.clipcrop);
2080                 
2081                 /* needed for transform from hoco to zbuffer co */
2082                 zspan->zmulx= ((float)R.winx)/2.0f;
2083                 zspan->zmuly= ((float)R.winy)/2.0f;
2084                 
2085                 if (R.osa) {
2086                         zspan->zofsx= -pa->disprect.xmin - R.jit[pa->sample+zsample][0];
2087                         zspan->zofsy= -pa->disprect.ymin - R.jit[pa->sample+zsample][1];
2088                 }
2089                 else if (R.i.curblur) {
2090                         zspan->zofsx= -pa->disprect.xmin - R.mblur_jit[R.i.curblur-1][0];
2091                         zspan->zofsy= -pa->disprect.ymin - R.mblur_jit[R.i.curblur-1][1];
2092                 }
2093                 else {
2094                         zspan->zofsx= -pa->disprect.xmin;
2095                         zspan->zofsy= -pa->disprect.ymin;
2096                 }
2097                 /* to center the sample position */
2098                 zspan->zofsx -= 0.5f;
2099                 zspan->zofsy -= 0.5f;
2100                 
2101                 /* the buffers */
2102                 if (zsample == samples-1) {
2103                         zspan->rectp= pa->rectp;
2104                         zspan->recto= pa->recto;
2105
2106                         if (neg_zmask)
2107                                 zspan->rectz= pa->rectmask;
2108                         else
2109                                 zspan->rectz= pa->rectz;
2110                 }
2111                 else {
2112                         zspan->recto= MEM_mallocN(sizeof(int)*pa->rectx*pa->recty, "recto");
2113                         zspan->rectp= MEM_mallocN(sizeof(int)*pa->rectx*pa->recty, "rectp");
2114                         zspan->rectz= MEM_mallocN(sizeof(int)*pa->rectx*pa->recty, "rectz");
2115                 }
2116
2117                 fillrect(zspan->rectz, pa->rectx, pa->recty, 0x7FFFFFFF);
2118                 fillrect(zspan->rectp, pa->rectx, pa->recty, 0);
2119                 fillrect(zspan->recto, pa->rectx, pa->recty, 0);
2120         }
2121
2122         /* in case zmask we fill Z for objects in lay_zmask first, then clear Z, and then do normal zbuffering */
2123         if (rl->layflag & SCE_LAY_ZMASK)
2124                 zmaskpass= 1;
2125         
2126         for (; zmaskpass >=0; zmaskpass--) {
2127                 ma= NULL;
2128
2129                 /* filling methods */
2130                 for (zsample=0; zsample<samples; zsample++) {
2131                         zspan= &zspans[zsample];
2132
2133                         if (zmaskpass && neg_zmask)
2134                                 zspan->zbuffunc= zbuffillGLinv4;
2135                         else
2136                                 zspan->zbuffunc= zbuffillGL4;
2137                         zspan->zbuflinefunc= zbufline;
2138                 }
2139
2140                 /* regular zbuffering loop, does all sample buffers */
2141                 for (i=0, obi=R.instancetable.first; obi; i++, obi=obi->next) {
2142                         obr= obi->obr;
2143
2144                         /* continue happens in 2 different ways... zmaskpass only does lay_zmask stuff */
2145                         if (zmaskpass) {
2146                                 if ((obi->lay & lay_zmask)==0)
2147                                         continue;
2148                         }
2149                         else if (!all_z && !(obi->lay & (lay|lay_zmask)))
2150                                 continue;
2151                         
2152                         if (obi->flag & R_TRANSFORMED)
2153                                 mult_m4_m4m4(obwinmat, winmat, obi->mat);
2154                         else
2155                                 copy_m4_m4(obwinmat, winmat);
2156
2157                         if (clip_render_object(obi->obr->boundbox, bounds, obwinmat))
2158                                 continue;
2159
2160                         zbuf_project_cache_clear(cache, obr->totvert);
2161
2162                         for (v=0; v<obr->totvlak; v++) {
2163                                 if ((v & 255)==0) vlr= obr->vlaknodes[v>>8].vlak;
2164                                 else vlr++;
2165
2166                                 /* the cases: visible for render, only z values, zmask, nothing */
2167                                 if (obi->lay & lay) {
2168                                         if (vlr->mat!=ma) {
2169                                                 ma= vlr->mat;
2170                                                 nofill= (ma->mode & MA_ONLYCAST) || ((ma->mode & MA_TRANSP) && (ma->mode & MA_ZTRANSP));
2171                                                 env= (ma->mode & MA_ENV);
2172                                                 wire= (ma->material_type == MA_TYPE_WIRE);
2173                                                 
2174                                                 for (zsample=0; zsample<samples; zsample++) {
2175                                                         if (ma->mode & MA_ZINV || (zmaskpass && neg_zmask))
2176                                                                 zspans[zsample].zbuffunc= zbuffillGLinv4;
2177                                                         else
2178                                                                 zspans[zsample].zbuffunc= zbuffillGL4;
2179                                                 }
2180                                         }
2181                                 }
2182                                 else if (all_z || (obi->lay & lay_zmask)) {
2183                                         env= 1;
2184                                         nofill= 0;
2185                                         ma= NULL; 
2186                                 }
2187                                 else {
2188                                         nofill= 1;
2189                                         ma= NULL;       /* otherwise nofill can hang */
2190                                 }
2191
2192                                 if (!(vlr->flag & R_HIDDEN) && nofill==0) {
2193                                         unsigned short partclip;
2194                                         
2195                                         v1= vlr->v1;
2196                                         v2= vlr->v2;
2197                                         v3= vlr->v3;
2198                                         v4= vlr->v4;
2199
2200                                         c1= zbuf_part_project(cache, v1->index, obwinmat, bounds, v1->co, ho1);
2201                                         c2= zbuf_part_project(cache, v2->index, obwinmat, bounds, v2->co, ho2);
2202                                         c3= zbuf_part_project(cache, v3->index, obwinmat, bounds, v3->co, ho3);
2203
2204                                         /* partclipping doesn't need viewplane clipping */
2205                                         partclip= c1 & c2 & c3;
2206                                         if (v4) {
2207                                                 c4= zbuf_part_project(cache, v4->index, obwinmat, bounds, v4->co, ho4);
2208                                                 partclip &= c4;
2209                                         }
2210
2211                                         if (partclip==0) {
2212                                                 
2213                                                 if (env) zvlnr= -1;
2214                                                 else zvlnr= v+1;
2215
2216                                                 c1= testclip(ho1);
2217                                                 c2= testclip(ho2);
2218                                                 c3= testclip(ho3);
2219                                                 if (v4)
2220                                                         c4= testclip(ho4);
2221
2222                                                 for (zsample=0; zsample<samples; zsample++) {
2223                                                         zspan= &zspans[zsample];
2224
2225                                                         if (wire) {
2226                                                                 if (v4)
2227                                                                         zbufclipwire(zspan, i, zvlnr, vlr->ec, ho1, ho2, ho3, ho4, c1, c2, c3, c4);
2228                                                                 else
2229                                                                         zbufclipwire(zspan, i, zvlnr, vlr->ec, ho1, ho2, ho3, 0, c1, c2, c3, 0);
2230                                                         }
2231                                                         else {
2232                                                                 /* strands allow to be filled in as quad */
2233                                                                 if (v4 && (vlr->flag & R_STRAND)) {
2234                                                                         zbufclip4(zspan, i, zvlnr, ho1, ho2, ho3, ho4, c1, c2, c3, c4);
2235                                                                 }
2236                                                                 else {
2237                                                                         zbufclip(zspan, i, zvlnr, ho1, ho2, ho3, c1, c2, c3);
2238                                                                         if (v4)
2239                                                                                 zbufclip(zspan, i, (env)? zvlnr: zvlnr+RE_QUAD_OFFS, ho1, ho3, ho4, c1, c3, c4);
2240                                                                 }
2241                                                         }
2242                                                 }
2243                                         }
2244                                 }
2245                         }
2246                 }
2247                 
2248                 /* clear all z to close value, so it works as mask for next passes (ztra+strand) */
2249                 if (zmaskpass) {
2250                         for (zsample=0; zsample<samples; zsample++) {
2251                                 zspan= &zspans[zsample];
2252
2253                                 if (neg_zmask) {
2254                                         zspan->rectmask= zspan->rectz;
2255                                         if (zsample == samples-1)
2256                                                 zspan->rectz= pa->rectz;
2257                                         else
2258                                                 zspan->rectz= MEM_mallocN(sizeof(int)*pa->rectx*pa->recty, "rectz");
2259                                         fillrect(zspan->rectz, pa->rectx, pa->recty, 0x7FFFFFFF);
2260
2261                                         zmask_rect(zspan->rectmask, zspan->rectp, pa->rectx, pa->recty, 1);
2262                                 }
2263                                 else
2264                                         zmask_rect(zspan->rectz, zspan->rectp, pa->rectx, pa->recty, 0);
2265                         }
2266                 }
2267         }
2268
2269         for (zsample=0; zsample<samples; zsample++) {
2270                 zspan= &zspans[zsample];
2271
2272                 if (fillfunc)
2273                         fillfunc(pa, zspan, pa->sample+zsample, data);
2274
2275                 if (zsample != samples-1) {
2276                         MEM_freeN(zspan->rectz);
2277                         MEM_freeN(zspan->rectp);
2278                         MEM_freeN(zspan->recto);
2279                         if (zspan->rectmask)
2280                                 MEM_freeN(zspan->rectmask);
2281                 }
2282
2283                 zbuf_free_span(zspan);
2284         }
2285 }
2286
2287 void zbuffer_shadow(Render *re, float winmat[][4], LampRen *lar, int *rectz, int size, float jitx, float jity)
2288 {
2289         ZbufProjectCache cache[ZBUF_PROJECT_CACHE_SIZE];
2290         ZSpan zspan;
2291         ObjectInstanceRen *obi;
2292         ObjectRen *obr;
2293         VlakRen *vlr= NULL;
2294         Material *ma= NULL;
2295         StrandSegment sseg;
2296         StrandRen *strand= NULL;
2297         StrandVert *svert;
2298         StrandBound *sbound;
2299         float obwinmat[4][4], ho1[4], ho2[4], ho3[4], ho4[4];
2300         int a, b, c, i, c1, c2, c3, c4, ok=1, lay= -1;
2301
2302         if (lar->mode & (LA_LAYER|LA_LAYER_SHADOW)) lay= lar->lay;
2303
2304         /* 1.0f for clipping in clippyra()... bad stuff actually */
2305         zbuf_alloc_span(&zspan, size, size, 1.0f);
2306         zspan.zmulx=  ((float)size)/2.0f;
2307         zspan.zmuly=  ((float)size)/2.0f;
2308         /* -0.5f to center the sample position */
2309         zspan.zofsx= jitx - 0.5f;
2310         zspan.zofsy= jity - 0.5f;
2311         
2312         /* the buffers */
2313         zspan.rectz= rectz;
2314         fillrect(rectz, size, size, 0x7FFFFFFE);
2315         if (lar->buftype==LA_SHADBUF_HALFWAY) {
2316                 zspan.rectz1= MEM_mallocN(size*size*sizeof(int), "seconday z buffer");
2317                 fillrect(zspan.rectz1, size, size, 0x7FFFFFFE);
2318         }
2319         
2320         /* filling methods */
2321         zspan.zbuflinefunc= zbufline_onlyZ;
2322         zspan.zbuffunc= zbuffillGL_onlyZ;
2323
2324         for (i=0, obi=re->instancetable.first; obi; i++, obi=obi->next) {
2325                 obr= obi->obr;
2326
2327                 if (obr->ob==re->excludeob)
2328                         continue;
2329                 else if (!(obi->lay & lay))
2330                         continue;
2331
2332                 if (obi->flag & R_TRANSFORMED)
2333                         mult_m4_m4m4(obwinmat, winmat, obi->mat);
2334                 else
2335                         copy_m4_m4(obwinmat, winmat);
2336
2337                 if (clip_render_object(obi->obr->boundbox, NULL, obwinmat))
2338                         continue;
2339
2340                 zbuf_project_cache_clear(cache, obr->totvert);
2341
2342                 /* faces */
2343                 for (a=0; a<obr->totvlak; a++) {
2344
2345                         if ((a & 255)==0) vlr= obr->vlaknodes[a>>8].vlak;
2346                         else vlr++;
2347
2348                         /* note, these conditions are copied in shadowbuf_autoclip() */
2349                         if (vlr->mat!= ma) {
2350                                 ma= vlr->mat;
2351                                 ok= 1;
2352                                 if ((ma->mode & MA_SHADBUF)==0) ok= 0;
2353                         }
2354
2355                         if (ok && (obi->lay & lay) && !(vlr->flag & R_HIDDEN)) {
2356                                 c1= zbuf_shadow_project(cache, vlr->v1->index, obwinmat, vlr->v1->co, ho1);
2357                                 c2= zbuf_shadow_project(cache, vlr->v2->index, obwinmat, vlr->v2->co, ho2);
2358                                 c3= zbuf_shadow_project(cache, vlr->v3->index, obwinmat, vlr->v3->co, ho3);
2359
2360                                 if ((ma->material_type == MA_TYPE_WIRE) || (vlr->flag & R_STRAND)) {
2361                                         if (vlr->v4) {
2362                                                 c4= zbuf_shadow_project(cache, vlr->v4->index, obwinmat, vlr->v4->co, ho4);
2363                                                 zbufclipwire(&zspan, 0, a+1, vlr->ec, ho1, ho2, ho3, ho4, c1, c2, c3, c4);
2364                                         }
2365                                         else
2366                                                 zbufclipwire(&zspan, 0, a+1, vlr->ec, ho1, ho2, ho3, 0, c1, c2, c3, 0);
2367                                 }
2368                                 else {
2369                                         if (vlr->v4) {
2370                                                 c4= zbuf_shadow_project(cache, vlr->v4->index, obwinmat, vlr->v4->co, ho4);
2371                                                 zbufclip4(&zspan, 0, 0, ho1, ho2, ho3, ho4, c1, c2, c3, c4);
2372                                         }
2373                                         else
2374                                                 zbufclip(&zspan, 0, 0, ho1, ho2, ho3, c1, c2, c3);
2375                                 }
2376                         }
2377
2378                         if ((a & 255)==255 && re->test_break(re->tbh)) 
2379                                 break;
2380                 }
2381
2382                 /* strands */
2383                 if (obr->strandbuf) {
2384                         /* for each bounding box containing a number of strands */
2385                         sbound= obr->strandbuf->bound;
2386                         for (c=0; c<obr->strandbuf->totbound; c++, sbound++) {
2387                                 if (clip_render_object(sbound->boundbox, NULL, obwinmat))
2388                                         continue;
2389
2390                                 /* for each strand in this bounding box */
2391                                 for (a=sbound->start; a<sbound->end; a++) {
2392                                         strand= RE_findOrAddStrand(obr, a);
2393
2394                                         sseg.obi= obi;
2395                                         sseg.buffer= strand->buffer;
2396                                         sseg.sqadaptcos= sseg.buffer->adaptcos;
2397                                         sseg.sqadaptcos *= sseg.sqadaptcos;
2398                                         sseg.strand= strand;
2399                                         svert= strand->vert;
2400
2401                                         /* note, these conditions are copied in shadowbuf_autoclip() */
2402                                         if (sseg.buffer->ma!= ma) {
2403                                                 ma= sseg.buffer->ma;
2404                                                 ok= 1;
2405                                                 if ((ma->mode & MA_SHADBUF)==0) ok= 0;
2406                                         }
2407
2408                                         if (ok && (sseg.buffer->lay & lay)) {
2409                                                 zbuf_project_cache_clear(cache, strand->totvert);
2410
2411                                                 for (b=0; b<strand->totvert-1; b++, svert++) {
2412                                                         sseg.v[0]= (b > 0)? (svert-1): svert;
2413                                                         sseg.v[1]= svert;
2414                                                         sseg.v[2]= svert+1;
2415                                                         sseg.v[3]= (b < strand->totvert-2)? svert+2: svert+1;
2416
2417                                                         c1= zbuf_shadow_project(cache, sseg.v[0]-strand->vert, obwinmat, sseg.v[0]->co, ho1);
2418                                                         c2= zbuf_shadow_project(cache, sseg.v[1]-strand->vert, obwinmat, sseg.v[1]->co, ho2);
2419                                                         c3= zbuf_shadow_project(cache, sseg.v[2]-strand->vert, obwinmat, sseg.v[2]->co, ho3);
2420                                                         c4= zbuf_shadow_project(cache, sseg.v[3]-strand->vert, obwinmat, sseg.v[3]->co, ho4);
2421
2422                                                         if (!(c1 & c2 & c3 & c4))
2423                                                                 render_strand_segment(re, winmat, NULL, &zspan, 1, &sseg);
2424                                                 }
2425                                         }
2426
2427                                         if ((a & 255)==255 && re->test_break(re->tbh)) 
2428                                                 break;
2429                                 }
2430                         }
2431                 }
2432
2433                 if (re->test_break(re->tbh)) 
2434                         break;
2435         }
2436         
2437         /* merge buffers */
2438         if (lar->buftype==LA_SHADBUF_HALFWAY) {
2439                 for (a=size*size -1; a>=0; a--)
2440                         rectz[a]= (rectz[a]>>1) + (zspan.rectz1[a]>>1);
2441                 
2442                 MEM_freeN(zspan.rectz1);
2443         }
2444         
2445         zbuf_free_span(&zspan);
2446 }
2447
2448 static void zbuffill_sss(ZSpan *zspan, int obi, int zvlnr, float *v1, float *v2, float *v3, float *v4)
2449 {
2450         double zxd, zyd, zy0, z;
2451         float x0, y0, x1, y1, x2, y2, z0, z1, z2, xx1, *span1, *span2;
2452         int x, y, sn1, sn2, rectx= zspan->rectx, my0, my2;
2453         /* init */
2454         zbuf_init_span(zspan);
2455         
2456         /* set spans */
2457         zbuf_add_to_span(zspan, v1, v2);
2458         zbuf_add_to_span(zspan, v2, v3);
2459         if (v4) {
2460                 zbuf_add_to_span(zspan, v3, v4);
2461                 zbuf_add_to_span(zspan, v4, v1);
2462         }
2463         else 
2464                 zbuf_add_to_span(zspan, v3, v1);
2465         
2466         /* clipped */
2467         if (zspan->minp2==NULL || zspan->maxp2==NULL) return;
2468         
2469         if (zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
2470         if (zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
2471         
2472         if (my2<my0) return;
2473         
2474         /* ZBUF DX DY, in floats still */
2475         x1= v1[0]- v2[0];
2476         x2= v2[0]- v3[0];
2477         y1= v1[1]- v2[1];
2478         y2= v2[1]- v3[1];
2479         z1= v1[2]- v2[2];
2480         z2= v2[2]- v3[2];
2481         
2482         x0= y1*z2-z1*y2;
2483         y0= z1*x2-x1*z2;
2484         z0= x1*y2-y1*x2;
2485         
2486         if (z0==0.0f) return;
2487         
2488         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
2489         zxd= -(double)x0/(double)z0;
2490         zyd= -(double)y0/(double)z0;
2491         zy0= ((double)my2)*zyd + (double)xx1;
2492         
2493         /* correct span */
2494         sn1= (my0 + my2)/2;
2495         if (zspan->span1[sn1] < zspan->span2[sn1]) {
2496                 span1= zspan->span1+my2;
2497                 span2= zspan->span2+my2;
2498         }
2499         else {
2500                 span1= zspan->span2+my2;
2501                 span2= zspan->span1+my2;
2502         }
2503         
2504         for (y=my2; y>=my0; y--, span1--, span2--) {
2505                 sn1= floor(*span1);
2506                 sn2= floor(*span2);
2507                 sn1++; 
2508                 
2509                 if (sn2>=rectx) sn2= rectx-1;
2510                 if (sn1<0) sn1= 0;
2511                 
2512                 z= (double)sn1*zxd + zy0;
2513                 
2514                 for (x= sn1; x<=sn2; x++, z+=zxd)
2515                         zspan->sss_func(zspan->sss_handle, obi, zvlnr, x, y, z);
2516                 
2517                 zy0 -= zyd;
2518         }
2519 }
2520
2521 void zbuffer_sss(RenderPart *pa, unsigned int lay, void *handle, void (*func)(void*, int, int, int, int, int))
2522 {
2523         ZbufProjectCache cache[ZBUF_PROJECT_CACHE_SIZE];
2524         ZSpan zspan;
2525         ObjectInstanceRen *obi;
2526         ObjectRen *obr;
2527         VlakRen *vlr= NULL;
2528         VertRen *v1, *v2, *v3, *v4;
2529         Material *ma=0, *sss_ma= R.sss_mat;
2530         float obwinmat[4][4], winmat[4][4], bounds[4];
2531         float ho1[4], ho2[4], ho3[4], ho4[4]={0};
2532         int i, v, zvlnr, c1, c2, c3, c4=0;
2533         short nofill=0, env=0, wire=0;
2534         
2535         zbuf_make_winmat(&R, winmat);
2536         zbuffer_part_bounds(R.winx, R.winy, pa, bounds);
2537         zbuf_alloc_span(&zspan, pa->rectx, pa->recty, R.clipcrop);
2538
2539         zspan.sss_handle= handle;
2540         zspan.sss_func= func;
2541         
2542         /* needed for transform from hoco to zbuffer co */
2543         zspan.zmulx=  ((float)R.winx)/2.0f;
2544         zspan.zmuly=  ((float)R.winy)/2.0f;
2545         
2546         /* -0.5f to center the sample position */
2547         zspan.zofsx= -pa->disprect.xmin - 0.5f;
2548         zspan.zofsy= -pa->disprect.ymin - 0.5f;
2549         
2550         /* filling methods */
2551         zspan.zbuffunc= zbuffill_sss;
2552
2553         /* fill front and back zbuffer */
2554         if (pa->rectz) {
2555                 fillrect(pa->recto, pa->rectx, pa->recty, 0); 
2556                 fillrect(pa->rectp, pa->rectx, pa->recty, 0); 
2557                 fillrect(pa->rectz, pa->rectx, pa->recty, 0x7FFFFFFF);
2558         }
2559         if (pa->rectbackz) {
2560                 fillrect(pa->rectbacko, pa->rectx, pa->recty, 0); 
2561                 fillrect(pa->rectbackp, pa->rectx, pa->recty, 0); 
2562                 fillrect(pa->rectbackz, pa->rectx, pa->recty, -0x7FFFFFFF);
2563         }
2564
2565         for (i=0, obi=R.instancetable.first; obi; i++, obi=obi->next) {
2566                 obr= obi->obr;
2567
2568                 if (!(obi->lay & lay))
2569                         continue;
2570
2571                 if (obi->flag & R_TRANSFORMED)
2572                         mult_m4_m4m4(obwinmat, winmat, obi->mat);
2573                 else
2574                         copy_m4_m4(obwinmat, winmat);
2575
2576                 if (clip_render_object(obi->obr->boundbox, bounds, obwinmat))
2577                         continue;
2578
2579                 zbuf_project_cache_clear(cache, obr->totvert);
2580
2581                 for (v=0; v<obr->totvlak; v++) {
2582                         if ((v & 255)==0) vlr= obr->vlaknodes[v>>8].vlak;
2583                         else vlr++;
2584                         
2585                         if (material_in_material(vlr->mat, sss_ma)) {
2586                                 /* three cases, visible for render, only z values and nothing */
2587                                 if (obi->lay & lay) {
2588                                         if (vlr->mat!=ma) {
2589                                                 ma= vlr->mat;
2590                                                 nofill= ma->mode & MA_ONLYCAST;
2591                                                 env= (ma->mode & MA_ENV);
2592                                                 wire= (ma->material_type == MA_TYPE_WIRE);
2593                                         }
2594                                 }
2595                                 else {
2596                                         nofill= 1;
2597                                         ma= NULL;       /* otherwise nofill can hang */
2598                                 }
2599                                 
2600                                 if (nofill==0 && wire==0 && env==0) {
2601                                         unsigned short partclip;
2602                                         
2603                                         v1= vlr->v1;
2604                                         v2= vlr->v2;
2605                                         v3= vlr->v3;
2606                                         v4= vlr->v4;
2607
2608                                         c1= zbuf_part_project(cache, v1->index, obwinmat, bounds, v1->co, ho1);
2609                                         c2= zbuf_part_project(cache, v2->index, obwinmat, bounds, v2->co, ho2);
2610                                         c3= zbuf_part_project(cache, v3->index, obwinmat, bounds, v3->co, ho3);
2611
2612                                         /* partclipping doesn't need viewplane clipping */
2613                                         partclip= c1 & c2 & c3;
2614                                         if (v4) {
2615                                                 c4= zbuf_part_project(cache, v4->index, obwinmat, bounds, v4->co, ho4);
2616                                                 partclip &= c4;
2617                                         }
2618
2619                                         if (partclip==0) {
2620                                                 c1= testclip(ho1);
2621                                                 c2= testclip(ho2);
2622                                                 c3= testclip(ho3);
2623
2624                                                 zvlnr= v+1;
2625                                                 zbufclip(&zspan, i, zvlnr, ho1, ho2, ho3, c1, c2, c3);
2626                                                 if (v4) {
2627                                                         c4= testclip(ho4);
2628                                                         zbufclip(&zspan, i, zvlnr+RE_QUAD_OFFS, ho1, ho3, ho4, c1, c3, c4);
2629                                                 }
2630                                         }
2631                                 }
2632                         }
2633                 }
2634         }
2635                 
2636         zbuf_free_span(&zspan);
2637 }
2638
2639 /* ******************** VECBLUR ACCUM BUF ************************* */
2640
2641 typedef struct DrawBufPixel {
2642         float *colpoin;
2643         float alpha;
2644 } DrawBufPixel;
2645
2646
2647 static void zbuf_fill_in_rgba(ZSpan *zspan, DrawBufPixel *col, float *v1, float *v2, float *v3, float *v4)
2648 {
2649         DrawBufPixel *rectpofs, *rp;
2650         double zxd, zyd, zy0, zverg;
2651         float x0, y0, z0;
2652         float x1, y1, z1, x2, y2, z2, xx1;
2653         float *span1, *span2;
2654         float *rectzofs, *rz;
2655         int x, y;
2656         int sn1, sn2, rectx, my0, my2;
2657         
2658         /* init */
2659         zbuf_init_span(zspan);
2660         
2661         /* set spans */
2662         zbuf_add_to_span(zspan, v1, v2);
2663         zbuf_add_to_span(zspan, v2, v3);
2664         zbuf_add_to_span(zspan, v3, v4);
2665         zbuf_add_to_span(zspan, v4, v1);
2666         
2667         /* clipped */
2668         if (zspan->minp2==NULL || zspan->maxp2==NULL) return;
2669         
2670         if (zspan->miny1 < zspan->miny2) my0= zspan->miny2; else my0= zspan->miny1;
2671         if (zspan->maxy1 > zspan->maxy2) my2= zspan->maxy2; else my2= zspan->maxy1;
2672         
2673         //      printf("my %d %d\n", my0, my2);
2674         if (my2<my0) return;
2675         
2676         /* ZBUF DX DY, in floats still */
2677         x1= v1[0]- v2[0];
2678         x2= v2[0]- v3[0];
2679         y1= v1[1]- v2[1];
2680         y2= v2[1]- v3[1];
2681         z1= v1[2]- v2[2];
2682         z2= v2[2]- v3[2];
2683         x0= y1*z2-z1*y2;
2684         y0= z1*x2-x1*z2;
2685         z0= x1*y2-y1*x2;
2686         
2687         if (z0==0.0f) return;
2688         
2689         xx1= (x0*v1[0] + y0*v1[1])/z0 + v1[2];
2690         
2691         zxd= -(double)x0/(double)z0;
2692         zyd= -(double)y0/(double)z0;
2693         zy0= ((double)my2)*zyd + (double)xx1;
2694         
2695         /* start-offset in rect */
2696         rectx= zspan->rectx;
2697         rectzofs= (float *)(zspan->rectz + rectx*my2);
2698         rectpofs= ((DrawBufPixel *)zspan->rectp) + rectx*my2;
2699         
2700         /* correct span */
2701         sn1= (my0 + my2)/2;
2702         if (zspan->span1[sn1] < zspan->span2[sn1]) {
2703                 span1= zspan->span1+my2;
2704                 span2= zspan->span2+my2;
2705         }
2706         else {
2707                 span1= zspan->span2+my2;
2708                 span2= zspan->span1+my2;
2709         }
2710         
2711         for (y=my2; y>=my0; y--, span1--, span2--) {
2712                 
2713                 sn1= floor(*span1);
2714                 sn2= floor(*span2);
2715                 sn1++; 
2716                 
2717                 if (sn2>=rectx) sn2= rectx-1;
2718                 if (sn1<0) sn1= 0;
2719                 
2720                 if (sn2>=sn1) {
2721                         zverg= (double)sn1*zxd + zy0;
2722                         rz= rectzofs+sn1;
2723                         rp= rectpofs+sn1;
2724                         x= sn2-sn1;
2725                         
2726                         while (x>=0) {
2727                                 if ( zverg < *rz) {
2728                                         *rz= zverg;
2729                                         *rp= *col;
2730                                 }
2731                                 zverg+= zxd;
2732                                 rz++; 
2733                                 rp++; 
2734                                 x--;
2735                         }
2736                 }
2737                 
2738                 zy0-=zyd;
2739                 rectzofs-= rectx;
2740                 rectpofs-= rectx;
2741         }
2742 }
2743
2744 /* char value==255 is filled in, rest should be zero */
2745 /* returns alpha values, but sets alpha to 1 for zero alpha pixels that have an alpha value as neighbor */
2746 void antialias_tagbuf(int xsize, int ysize, char *rectmove)
2747 {
2748         char *row1, *row2, *row3;
2749         char prev, next;
2750         int a, x, y, step;
2751         
2752         /* 1: tag pixels to be candidate for AA */
2753         for (y=2; y<ysize; y++) {
2754                 /* setup rows */
2755                 row1= rectmove + (y-2)*xsize;
2756                 row2= row1 + xsize;
2757                 row3= row2 + xsize;
2758                 for (x=2; x<xsize; x++, row1++, row2++, row3++) {
2759                         if (row2[1]) {
2760                                 if (row2[0]==0 || row2[2]==0 || row1[1]==0 || row3[1]==0)
2761                                         row2[1]= 128;
2762                         }
2763                 }
2764         }
2765         
2766         /* 2: evaluate horizontal scanlines and calculate alphas */
2767         row1= rectmove;
2768         for (y=0; y<ysize; y++) {
2769                 row1++;
2770                 for (x=1; x<xsize; x++, row1++) {
2771                         if (row1[0]==128 && row1[1]==128) {
2772                                 /* find previous color and next color and amount of steps to blend */
2773                                 prev= row1[-1];
2774                                 step= 1;
2775                                 while (x+step<xsize && row1[step]==128)
2776                                         step++;
2777                                 
2778                                 if (x+step!=xsize) {
2779                                         /* now we can blend values */
2780                                         next= row1[step];
2781
2782                                         /* note, prev value can be next value, but we do this loop to clear 128 then */
2783                                         for (a=0; a<step; a++) {
2784                                                 int fac, mfac;
2785                                                 
2786                                                 fac= ((a+1)<<8)/(step+1);
2787                                                 mfac= 255-fac;
2788                                                 
2789                                                 row1[a]= (prev*mfac + next*fac)>>8; 
2790                                         }
2791                                 }
2792                         }
2793                 }
2794         }
2795         
2796         /* 3: evaluate vertical scanlines and calculate alphas */
2797         /*    use for reading a copy of the original tagged buffer */
2798         for (x=0; x<xsize; x++) {
2799                 row1= rectmove + x+xsize;
2800                 
2801                 for (y=1; y<ysize; y++, row1+=xsize) {
2802                         if (row1[0]==128 && row1[xsize]==128) {
2803                                 /* find previous color and next color and amount of steps to blend */
2804                                 prev= row1[-xsize];
2805                                 step= 1;
2806                                 while (y+step<ysize && row1[step*xsize]==128)
2807                                         step++;
2808                                 
2809                                 if (y+step!=ysize) {
2810                                         /* now we can blend values */
2811                                         next= row1[step*xsize];
2812                                         /* note, prev value can be next value, but we do this loop to clear 128 then */
2813                                         for (a=0; a<step; a++) {
2814                                                 int fac, mfac;
2815                                                 
2816                                                 fac= ((a+1)<<8)/(step+1);
2817                                                 mfac= 255-fac;
2818                                                 
2819                                                 row1[a*xsize]= (prev*mfac + next*fac)>>8; 
2820                                         }
2821                                 }
2822                         }
2823                 }
2824         }
2825         
2826         /* last: pixels with 0 we fill in zbuffer, with 1 we skip for mask */
2827         for (y=2; y<ysize; y++) {
2828                 /* setup rows */
2829                 row1= rectmove + (y-2)*xsize;
2830                 row2= row1 + xsize;
2831                 row3= row2 + xsize;
2832                 for (x=2; x<xsize; x++, row1++, row2++, row3++) {
2833                         if (row2[1]==0) {
2834                                 if (row2[0]>1 || row2[2]>1 || row1[1]>1 || row3[1]>1)
2835                                         row2[1]= 1;
2836                         }
2837                 }
2838         }
2839 }
2840
2841 /* in: two vectors, first vector points from origin back in time, 2nd vector points to future */
2842 /* we make this into 3 points, center point is (0, 0) */
2843 /* and offset the center point just enough to make curve go through midpoint */
2844
2845 static void quad_bezier_2d(float *result, float *v1, float *v2, float *ipodata)
2846 {
2847         float p1[2], p2[2], p3[2];
2848         
2849         p3[0]= -v2[0];
2850         p3[1]= -v2[1];
2851         
2852         p1[0]= v1[0];
2853         p1[1]= v1[1];
2854         
2855         /* official formula 2*p2 - .5*p1 - .5*p3 */
2856         p2[0]= -0.5f*p1[0] - 0.5f*p3[0];
2857         p2[1]= -0.5f*p1[1] - 0.5f*p3[1];
2858         
2859         result[0]= ipodata[0]*p1[0] + ipodata[1]*p2[0] + ipodata[2]*p3[0];
2860         result[1]= ipodata[0]*p1[1] + ipodata[1]*p2[1] + ipodata[2]*p3[1];
2861 }
2862
2863 static void set_quad_bezier_ipo(float fac, float *data)
2864 {
2865         float mfac= (1.0f-fac);
2866         
2867         data[0]= mfac*mfac;
2868         data[1]= 2.0f*mfac*fac;
2869         data[2]= fac*fac;
2870 }
2871
2872 void RE_zbuf_accumulate_vecblur(NodeBlurData *nbd, int xsize, int ysize, float *newrect, float *imgrect, float *vecbufrect, float *zbufrect)
2873 {
2874         ZSpan zspan;
2875         DrawBufPixel *rectdraw, *dr;
2876         static float jit[256][2];
2877         float v1[3], v2[3], v3[3], v4[3], fx, fy;
2878         float *rectvz, *dvz, *dimg, *dvec1, *dvec2, *dz, *dz1, *dz2, *rectz;
2879         float *minvecbufrect= NULL, *rectweight, *rw, *rectmax, *rm, *ro;
2880         float maxspeedsq= (float)nbd->maxspeed*nbd->maxspeed;
2881         int y, x, step, maxspeed=nbd->maxspeed, samples= nbd->samples;
2882         int tsktsk= 0;
2883         static int firsttime= 1;
2884         char *rectmove, *dm;
2885         
2886         zbuf_alloc_span(&zspan, xsize, ysize, 1.0f);
2887         zspan.zmulx=  ((float)xsize)/2.0f;
2888         zspan.zmuly=  ((float)ysize)/2.0f;
2889         zspan.zofsx= 0.0f;
2890         zspan.zofsy= 0.0f;
2891         
2892         /* the buffers */
2893         rectz= MEM_mapallocN(sizeof(float)*xsize*ysize, "zbuf accum");
2894         zspan.rectz= (int *)rectz;
2895         
2896         rectmove= MEM_mapallocN(xsize*ysize, "rectmove");
2897         rectdraw= MEM_mapallocN(sizeof(DrawBufPixel)*xsize*ysize, "rect draw");
2898         zspan.rectp= (int *)rectdraw;
2899
2900         rectweight= MEM_mapallocN(sizeof(float)*xsize*ysize, "rect weight");
2901         rectmax= MEM_mapallocN(sizeof(float)*xsize*ysize, "rect max");
2902         
2903         /* debug... check if PASS_VECTOR_MAX still is in buffers */
2904         dvec1= vecbufrect;
2905         for (x= 4*xsize*ysize; x>0; x--, dvec1++) {
2906                 if (dvec1[0]==PASS_VECTOR_MAX) {
2907                         dvec1[0]= 0.0f;
2908                         tsktsk= 1;
2909                 }
2910         }
2911         if (tsktsk) printf("Found uninitialized speed in vector buffer... fixed.\n");
2912         
2913         /* min speed? then copy speedbuffer to recalculate speed vectors */
2914         if (nbd->minspeed) {
2915                 float minspeed= (float)nbd->minspeed;
2916                 float minspeedsq= minspeed*minspeed;
2917                 
2918                 minvecbufrect= MEM_mapallocN(4*sizeof(float)*xsize*ysize, "minspeed buf");
2919                 
2920                 dvec1= vecbufrect;
2921                 dvec2= minvecbufrect;
2922                 for (x= 2*xsize*ysize; x>0; x--, dvec1+=2, dvec2+=2) {
2923                         if (dvec1[0]==0.0f && dvec1[1]==0.0f) {
2924                                 dvec2[0]= dvec1[0];
2925                                 dvec2[1]= dvec1[1];
2926                         }
2927                         else {
2928                                 float speedsq= dvec1[0]*dvec1[0] + dvec1[1]*dvec1[1];
2929                                 if (speedsq <= minspeedsq) {
2930                                         dvec2[0]= 0.0f;
2931                                         dvec2[1]= 0.0f;
2932                                 }
2933                                 else {
2934                                         speedsq= 1.0f - minspeed/sqrt(speedsq);
2935                                         dvec2[0]= speedsq*dvec1[0];
2936                                         dvec2[1]= speedsq*dvec1[1];
2937                                 }
2938                         }
2939                 }
2940                 SWAP(float *, minvecbufrect, vecbufrect);
2941         }
2942         
2943         /* make vertex buffer with averaged speed and zvalues */
2944         rectvz= MEM_mapallocN(4*sizeof(float)*(xsize+1)*(ysize+1), "vertices");
2945         dvz= rectvz;
2946         for (y=0; y<=ysize; y++) {
2947