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