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