New shadow feature: Irregular Shadow Buffers

Full log:
http://www.blender3d.org/cms/Irregular_Shadow_Buffe.785.0.html

In short: this is a shadow buffer approach that always results in crispy
shadows, independent of lamp buffer size or zoom level. This shadow buffer
system also supports transparent shadow.

This is part of work on refreshing Shadow Buffers in Blender. You now can
choose of two types (Classical, Irregular). More types will follow. Also
quality issues for Classical shadow buffers are going to be reviewed,
especially to solve the lousy Biasing.

For the CVS log record; it is based on articles:
Gregory Johnson et al, University of Texas, Austin. (Regular grid method).
Timo Aila and Samuli Laine, Helsinki University of Technology. (BSP method).

9 files changed, 1330 insertions, 59 deletions

diff --git a/source/blender/render/extern/include/RE_shader_ext.h b/source/blender/render/extern/include/RE_shader_ext.h
index 9fdaf8f4e62..25110e4edfb 100644
--- a/source/blender/render/extern/include/RE_shader_ext.h
+++ b/source/blender/render/extern/include/RE_shader_ext.h
@@ -106,6 +106,7 @@ typedef struct ShadeInput
 	short osatex, puno;
 	int mask;
 	int depth;			/* 1 or larger on raytrace shading */
+	int facenr;
 	unsigned int lay;
 } ShadeInput;
 
diff --git a/source/blender/render/intern/include/render_types.h b/source/blender/render/intern/include/render_types.h
index 5ff00e7a72c..a429e3027cd 100644
--- a/source/blender/render/intern/include/render_types.h
+++ b/source/blender/render/intern/include/render_types.h
@@ -49,7 +49,7 @@ struct GHash;
 #define TABLEINITSIZE 1024
 #define LAMPINITSIZE 256
 		/* hardcoded maximum now, for optimize tables */
-#define MAX_THREADS		2
+#define RE_MAXTHREAD	2
 
 typedef struct SampleTables
 {
@@ -188,6 +188,8 @@ struct Render
 
 /* ------------------------------------------------------------------------- */
 
+struct ISBData;
+
 typedef struct ShadSampleBuf {
 	struct ShadSampleBuf *next, *prev;
 	long *zbuf;
@@ -195,6 +197,7 @@ typedef struct ShadSampleBuf {
 } ShadSampleBuf;
 
 typedef struct ShadBuf {
+	/* regular shadowbuffer */
 	short samp, shadhalostep, totbuf;
 	float persmat[4][4];
 	float viewmat[4][4];
@@ -204,6 +207,9 @@ typedef struct ShadBuf {
 	int co[3];
 	int size, bias;
 	ListBase buffers;
+	
+	/* irregular shadowbufer, result stored per thread */
+	struct ISBData *isb_result[RE_MAXTHREAD];
 } ShadBuf;
 
 /* ------------------------------------------------------------------------- */
@@ -304,8 +310,10 @@ typedef struct LampRen
 	short samp;
 	/** Softness factor for shadow */
 	float soft;
-	/** amount of subsample buffers */
+	/** amount of subsample buffers and type of filter for sampling */
 	short buffers, filtertype;
+	/** shadow buffer type (regular, irregular) */
+	short buftype;
 	/** autoclip */
 	short bufflag;
 	/** shadow plus halo: detail level */
@@ -339,7 +347,7 @@ typedef struct LampRen
 	short YF_glowtype;
 	
 	/* ray optim */
-	VlakRen *vlr_last[MAX_THREADS];
+	VlakRen *vlr_last[RE_MAXTHREAD];
 	
 	struct MTex *mtex[MAX_MTEX];
 } LampRen;
diff --git a/source/blender/render/intern/include/shadbuf.h b/source/blender/render/intern/include/shadbuf.h
index 8258dea466f..8b786c6e098 100644
--- a/source/blender/render/intern/include/shadbuf.h
+++ b/source/blender/render/intern/include/shadbuf.h
@@ -61,6 +61,50 @@ float testshadowbuf(struct ShadBuf *shb, float *rco, float *dxco, float *dyco, f
  */
 float shadow_halo(LampRen *lar, float *p1, float *p2);
 
+/**
+ * Irregular shadowbuffer
+ */
+
+struct MemArena;
+struct APixstr;
+
+void ISB_create(RenderPart *pa, struct APixstr *apixbuf);
+void ISB_free(RenderPart *pa);
+float ISB_getshadow(ShadeInput *shi, ShadBuf *shb);
+
+/* data structures have to be accessible both in camview(x, y) as in lampview(x, y) */
+/* since they're created per tile rendered, speed goes over memory requirements */
+
+
+/* buffer samples, allocated in camera buffer and pointed to in lampbuffer nodes */
+typedef struct ISBSample {
+	float zco[3];			/* coordinate in lampview projection */
+	short *shadfac;			/* initialized zero = full lighted */
+	int facenr;				/* index in faces list */	
+} ISBSample;
+
+/* transparent version of buffer sample */
+typedef struct ISBSampleA {
+	float zco[3];				/* coordinate in lampview projection */
+	short *shadfac;				/* NULL = full lighted */
+	int facenr;					/* index in faces list */	
+	struct ISBSampleA *next;	/* in end, we want the first items to align with ISBSample */
+} ISBSampleA;
+
+/* used for transparent storage only */
+typedef struct ISBShadfacA {
+	struct ISBShadfacA *next;
+	int facenr;
+	float shadfac;
+} ISBShadfacA;
+
+/* What needs to be stored to evaluate shadow, for each thread in ShadBuf */
+typedef struct ISBData {
+	short *shadfacs;				/* simple storage for solid only */
+	ISBShadfacA **shadfaca;
+	struct MemArena *memarena;
+	int minx, miny, rectx, recty;	/* copy from part disprect */
+} ISBData;
 
 #endif /* SHADBUF_EXT_H */
 
diff --git a/source/blender/render/intern/include/zbuf.h b/source/blender/render/intern/include/zbuf.h
index 1ec682c2162..ebad8f241f7 100644
--- a/source/blender/render/intern/include/zbuf.h
+++ b/source/blender/render/intern/include/zbuf.h
@@ -54,8 +54,9 @@ void convert_zbuf_to_distbuf(struct RenderPart *pa, struct RenderLayer *rl);
 
 typedef struct APixstr {
     unsigned short mask[4]; /* jitter mask */
-    int z[4];       /* distance    */
-    int p[4];       /* index       */
+    int z[4];			/* distance    */
+    int p[4];			/* index       */
+	short shadfac[4];	/* optimize storage for irregular shadow */
     struct APixstr *next;
 } APixstr;
 
@@ -81,6 +82,7 @@ typedef struct ZSpan {
 	struct ListBase *apsmbase;
 	
 	int polygon_offset;						/* offset in Z */
+	float shad_alpha;						/* copy from material, used by irregular shadbuf */
 	int mask, apsmcounter;					/* in use by apixbuf */
 	
 	void (*zbuffunc)(struct ZSpan *, int, float *, float *, float *, float *);
@@ -88,10 +90,14 @@ typedef struct ZSpan {
 	
 } ZSpan;
 
-/* exported for evil edge render... */
+/* exported to shadbuf.c */
+void zbufclip4(struct ZSpan *zspan, int zvlnr, float *f1, float *f2, float *f3, float *f4, int c1, int c2, int c3, int c4);
+void zbuf_free_span(struct ZSpan *zspan);
+
+/* exported to edge render... */
 void zbufclip(struct ZSpan *zspan, int zvlnr, float *f1, float *f2, float *f3, int c1, int c2, int c3);
-void zbuf_alloc_span(ZSpan *zspan, int rectx, int recty);
-void zbufclipwire(ZSpan *zspan, int zvlnr, struct VlakRen *vlr); 
+void zbuf_alloc_span(struct ZSpan *zspan, int rectx, int recty);
+void zbufclipwire(struct ZSpan *zspan, int zvlnr, struct VlakRen *vlr); 
 
 #endif
 
diff --git a/source/blender/render/intern/source/convertblender.c b/source/blender/render/intern/source/convertblender.c
index 54ff0b90541..c1cc2627e4f 100644
--- a/source/blender/render/intern/source/convertblender.c
+++ b/source/blender/render/intern/source/convertblender.c
@@ -1242,7 +1242,7 @@ static void static_particle_strand(Render *re, Object *ob, Material *ma, float *
 		flag= R_SMOOTH;
 	
 	/* only 1 pixel wide strands filled in as quads now, otherwise zbuf errors */
-	if(width==1.0f)
+	if(ma->strand_sta==1.0f)
 		flag |= R_STRAND;
 	
 	/* first two vertices */
@@ -2221,6 +2221,7 @@ static LampRen *add_render_lamp(Render *re, Object *ob)
 	lar->samp = la->samp;
 	lar->buffers= la->buffers;
 	if(lar->buffers==0) lar->buffers= 1;
+	lar->buftype= la->buftype;
 	lar->filtertype= la->filtertype;
 	lar->soft = la->soft;
 	lar->shadhalostep = la->shadhalostep;
@@ -2327,7 +2328,7 @@ static LampRen *add_render_lamp(Render *re, Object *ob)
 		lar->spottexfac= 1.0/(xn);
 
 		if(lar->mode & LA_ONLYSHADOW) {
-			if((lar->mode & (LA_SHAD|LA_SHAD_RAY))==0) lar->mode -= LA_ONLYSHADOW;
+			if((lar->mode & (LA_SHAD_BUF|LA_SHAD_RAY))==0) lar->mode -= LA_ONLYSHADOW;
 		}
 
 	}
@@ -2369,7 +2370,7 @@ static LampRen *add_render_lamp(Render *re, Object *ob)
 	/* yafray: shadowbuffers and jitter only needed for internal render */
 	if (re->r.renderer==R_INTERN) {
 		if(re->r.mode & R_SHADOW) {
-			if (la->type==LA_SPOT && (lar->mode & LA_SHAD) ) {
+			if (la->type==LA_SPOT && (lar->mode & LA_SHAD_BUF) ) {
 				/* Per lamp, one shadow buffer is made. */
 				lar->bufflag= la->bufflag;
 				Mat4CpyMat4(mat, ob->obmat);
@@ -3383,6 +3384,7 @@ void RE_Database_FromScene(Render *re, Scene *scene, int use_camera_view)
 			
 			if(re->test_break()) break;
 			if(lar->shb) {
+				/* if type is irregular, this only sets the perspective matrix and autoclips */
 				makeshadowbuf(re, lar);
 			}
 		}
diff --git a/source/blender/render/intern/source/pipeline.c b/source/blender/render/intern/source/pipeline.c
index f6c51753204..5bbc3174a3c 100644
--- a/source/blender/render/intern/source/pipeline.c
+++ b/source/blender/render/intern/source/pipeline.c
@@ -1120,7 +1120,8 @@ static void threaded_tile_processor(Render *re)
 		IMB_exrtile_begin_write(rr->exrhandle, str, rr->rectx, rr->recty, rr->rectx/re->xparts, rr->recty/re->yparts);
 	}
 	
-	if(re->r.mode & R_THREADS) maxthreads= 2;
+	if(re->r.mode & R_THREADS) 
+		maxthreads= RE_MAXTHREAD;	/* should become button value too */
 	else maxthreads= 1;
 	
 	BLI_init_threads(&threads, do_part_thread, maxthreads);
diff --git a/source/blender/render/intern/source/rendercore.c b/source/blender/render/intern/source/rendercore.c
index 1cbba7aa144..7e7a790ebad 100644
--- a/source/blender/render/intern/source/rendercore.c
+++ b/source/blender/render/intern/source/rendercore.c
@@ -412,7 +412,7 @@ static void renderspothalo(ShadeInput *shi, float *col, float alpha)
 
 
 
-/* also used in zbuf.c */
+/* also used in zbuf.c and shadbuf.c */
 int count_mask(unsigned short mask)
 {
 	if(R.samples)
@@ -1453,7 +1453,10 @@ static void shade_one_light(LampRen *lar, ShadeInput *shi, ShadeResult *shr, int
 				if(lar->type==LA_HEMI);	// no shadow
 				else {
 					if(lar->shb) {
-						shadfac[3] = testshadowbuf(lar->shb, shi->co, shi->dxco, shi->dyco, inp);
+						if(lar->buftype==LA_SHADBUF_IRREGULAR)
+							shadfac[3]= ISB_getshadow(shi, lar->shb);
+						else
+							shadfac[3] = testshadowbuf(lar->shb, shi->co, shi->dxco, shi->dyco, inp);
 					}
 					else if(lar->mode & LA_SHAD_RAY) {
 						ray_shadow(shi, lar, shadfac);
@@ -2410,9 +2413,9 @@ void *shadepixel(ShadePixelInfo *shpi, float x, float y, int z, volatile int fac
 	ShadeInput shi;
 	VlakRen *vlr=NULL;
 	
-	/* currently in use for dithering (soft shadow) node preview */
-	shi.xs= (int)(x+0.5f);
-	shi.ys= (int)(y+0.5f);
+	/* currently in use for dithering (soft shadow), node preview, irregular shad */
+	shi.xs= (int)(x);
+	shi.ys= (int)(y);
 
 	shi.thread= shpi->thread;
 	shi.do_preview= R.r.scemode & R_NODE_PREVIEW;
@@ -2430,7 +2433,8 @@ void *shadepixel(ShadePixelInfo *shpi, float x, float y, int z, volatile int fac
 		VertRen *v1;
 		float alpha, fac, zcor;
 		
-		vlr= RE_findOrAddVlak(&R, (facenr-1) & RE_QUAD_MASK);
+		shi.facenr= (facenr-1) & RE_QUAD_MASK;
+		vlr= RE_findOrAddVlak(&R, shi.facenr);
 		
 		shi.vlr= vlr;
 		shi.mat= vlr->mat;
@@ -2959,6 +2963,10 @@ static void shadeDA_tile(RenderPart *pa, RenderLayer *rl)
 	
 	if(R.test_break()) return; 
 	
+	/* irregular shadowb buffer creation */
+	if(R.r.mode & R_SHADOW)
+		ISB_create(pa, NULL);
+	
 	/* we set per pixel a fixed seed, for random AO and shadow samples */
 	seed= pa->rectx*pa->disprect.ymin;
 
@@ -3081,6 +3089,9 @@ static void shadeDA_tile(RenderPart *pa, RenderLayer *rl)
 			rectf[2] = invGammaCorrect(rectf[2]);
 		}
 	}
+	
+	if(R.r.mode & R_SHADOW)
+		ISB_free(pa);
 }
 
 /* ************* pixel struct ******** */
@@ -3319,7 +3330,8 @@ void zbufshade_tile(RenderPart *pa)
 		
 		zbuffer_solid(pa, rl->lay, rl->layflag);
 		
-		if(!R.test_break()) {
+		if(!R.test_break()) {	/* NOTE: this if() is not consistant */
+			
 			/* edges only for solid part, ztransp doesn't support it yet anti-aliased */
 			if(rl->layflag & SCE_LAY_EDGE) 
 				if(R.r.mode & R_EDGE)
@@ -3333,6 +3345,10 @@ void zbufshade_tile(RenderPart *pa)
 				float *fcol= rl->rectf;
 				int x, y, *rp= pa->rectp, *rz= pa->rectz, offs=0;
 				
+				/* irregular shadowb buffer creation */
+				if(R.r.mode & R_SHADOW)
+					ISB_create(pa, NULL);
+				
 				for(y=pa->disprect.ymin; y<pa->disprect.ymax; y++, rr->renrect.ymax++) {
 					for(x=pa->disprect.xmin; x<pa->disprect.xmax; x++, rz++, rp++, fcol+=4, offs++) {
 						shadepixel_sky(&shpi, (float)x, (float)y, *rz, *rp, 0);
@@ -3345,6 +3361,9 @@ void zbufshade_tile(RenderPart *pa)
 					if(y&1)
 						if(R.test_break()) break; 
 				}
+				
+				if(R.r.mode & R_SHADOW)
+					ISB_free(pa);
 			}
 			else if(rl->layflag & SCE_LAY_SKY) {
 				sky_tile(pa, rl->rectf);
diff --git a/source/blender/render/intern/source/shadbuf.c b/source/blender/render/intern/source/shadbuf.c
index b9e2562a6c0..fc6e34d0cbb 100644
--- a/source/blender/render/intern/source/shadbuf.c
+++ b/source/blender/render/intern/source/shadbuf.c
@@ -29,6 +29,7 @@
 #include "MTC_matrixops.h"
 #include "MEM_guardedalloc.h"
 
+#include "DNA_group_types.h"
 #include "DNA_lamp_types.h"
 #include "DNA_material_types.h"
 
@@ -38,10 +39,13 @@
 #include "BLI_arithb.h"
 #include "BLI_blenlib.h"
 #include "BLI_jitter.h"
+#include "BLI_memarena.h"
+#include "BLI_rand.h"
 
 #include "renderpipeline.h"
 #include "render_types.h"
 #include "renderdatabase.h"
+#include "rendercore.h"
 
 #include "shadbuf.h"
 #include "zbuf.h"
@@ -60,6 +64,12 @@
 #define ACOMP	3
 #endif
 
+/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
+/* defined in pipeline.c, is hardcopy of active dynamic allocated Render */
+/* only to be used here in this file, it's for speed */
+extern struct Render R;
+/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
+
 /* ------------------------------------------------------------------------- */
 
 /* initshadowbuf() in convertBlenderScene.c */
@@ -359,18 +369,13 @@ void makeshadowbuf(Render *re, LampRen *lar)
 	float wsize, *jitbuf, twozero[2]= {0.0f, 0.0f}, angle, temp;
 	int *rectz, samples;
 	
-	/* jitter, weights */
-	shb->jit= give_jitter_tab(shb->samp);
-	make_jitter_weight_tab(shb, lar->filtertype);
-	
-	shb->totbuf= lar->buffers;
-	if(shb->totbuf==4) jitbuf= give_jitter_tab(2);
-	else if(shb->totbuf==9) jitbuf= give_jitter_tab(3);
-	else jitbuf= twozero;
-	
 	if(lar->bufflag & (LA_SHADBUF_AUTO_START|LA_SHADBUF_AUTO_END))
 		shadowbuf_autoclip(re, lar);
 	
+	/* just to enforce identical behaviour of all irregular buffers */
+	if(lar->buftype==LA_SHADBUF_IRREGULAR)
+		shb->size= 1024;
+	
 	/* matrices and window: in winmat the transformation is being put,
 		transforming from observer view to lamp view, including lamp window matrix */
 	
@@ -381,26 +386,38 @@ void makeshadowbuf(Render *re, LampRen *lar)
 	
 	i_window(-wsize, wsize, -wsize, wsize, shb->d, shb->clipend, shb->winmat);
 	MTC_Mat4MulMat4(shb->persmat, shb->viewmat, shb->winmat);
-	/* temp, will be restored */
-	MTC_Mat4SwapMat4(shb->persmat, re->winmat);
+	
+	if(lar->buftype==LA_SHADBUF_REGULAR) {
+		/* jitter, weights */
+		shb->jit= give_jitter_tab(shb->samp);
+		make_jitter_weight_tab(shb, lar->filtertype);
+		
+		shb->totbuf= lar->buffers;
+		if(shb->totbuf==4) jitbuf= give_jitter_tab(2);
+		else if(shb->totbuf==9) jitbuf= give_jitter_tab(3);
+		else jitbuf= twozero;
+		
+		/* temp, will be restored */
+		MTC_Mat4SwapMat4(shb->persmat, re->winmat);
 
-	/* zbuffering */
- 	rectz= MEM_mapallocN(sizeof(int)*shb->size*shb->size, "makeshadbuf");
+		project_renderdata(re, projectvert, 0, 0);
+		
+		/* zbuffering */
+		rectz= MEM_mapallocN(sizeof(int)*shb->size*shb->size, "makeshadbuf");
+		
+		for(samples=0; samples<shb->totbuf; samples++) {
+			zbuffer_shadow(re, lar, rectz, shb->size, jitbuf[2*samples], jitbuf[2*samples+1]);
+			/* create Z tiles (for compression): this system is 24 bits!!! */
+			compress_shadowbuf(shb, rectz, lar->mode & LA_SQUARE);
+		}
+		
+		MEM_freeN(rectz);
+		
+		/* old matrix back */
+		MTC_Mat4SwapMat4(shb->persmat, re->winmat);
 
-	project_renderdata(re, projectvert, 0, 0);
-	
-	for(samples=0; samples<shb->totbuf; samples++) {
-		zbuffer_shadow(re, lar, rectz, shb->size, jitbuf[2*samples], jitbuf[2*samples+1]);
-		/* create Z tiles (for compression): this system is 24 bits!!! */
-		compress_shadowbuf(shb, rectz, lar->mode & LA_SQUARE);
+		/* printf("lampbuf %d\n", sizeoflampbuf(shb)); */
 	}
-	
-	MEM_freeN(rectz);
-	
-	/* old matrix back */
-	MTC_Mat4SwapMat4(shb->persmat, re->winmat);
-
-	/* printf("lampbuf %d\n", sizeoflampbuf(shb)); */
 }
 
 void freeshadowbuf(LampRen *lar)
@@ -826,8 +843,1172 @@ float shadow_halo(LampRen *lar, float *p1, float *p2)
 }
 
 
+/* ********************* Irregular Shadow Buffer (ISB) ************* */
+/* ********** storage of all view samples in a raster of lists ***** */
+
+/* based on several articles describing this method, like:
+The Irregular Z-Buffer and its Application to Shadow Mapping
+Gregory S. Johnson - William R. Mark - Christopher A. Burns 
+and
+Alias-Free Shadow Maps
+Timo Aila and Samuli Laine
+*/
+
+/* bsp structure (actually kd tree) */
+
+#define BSPMAX_SAMPLE	128
+#define BSPMAX_DEPTH	32
+
+/* aligned with struct rctf */
+typedef struct Boxf {
+	float xmin, xmax;
+	float ymin, ymax;
+	float zmin, zmax;
+} Boxf;
+
+typedef struct ISBBranch {
+	struct ISBBranch *left, *right;
+	float divider[2];
+	Boxf box;
+	short totsamp, index, full, unused;
+	ISBSample **samples;
+} ISBBranch;
+
+typedef struct BSPFace {
+	Boxf box;
+	float *v1, *v2, *v3, *v4;
+	int facenr;		/* index to retrieve VlakRen */
+	int type;		/* only for strand now */
+	short shad_alpha, is_full;
+	
+	/* strand caching data, optimize for point_behind_strand() */
+	float radline, radline_end, len;
+	float vec1[3], vec2[3], rc[3];
+} BSPFace;
+
+/* boxes are in lamp projection */
+static void init_box(Boxf *box)
+{
+	box->xmin= 1000000.0f;
+	box->xmax= 0;
+	box->ymin= 1000000.0f;
+	box->ymax= 0;
+	box->zmin= 0x7FFFFFFF;
+	box->zmax= - 0x7FFFFFFF;
+}
+
+/* use v1 to calculate boundbox */
+static void bound_boxf(Boxf *box, float *v1)
+{
+	if(v1[0] < box->xmin) box->xmin= v1[0];
+	if(v1[0] > box->xmax) box->xmax= v1[0];
+	if(v1[1] < box->ymin) box->ymin= v1[1];
+	if(v1[1] > box->ymax) box->ymax= v1[1];
+	if(v1[2] < box->zmin) box->zmin= v1[2];
+	if(v1[2] > box->zmax) box->zmax= v1[2];
+}
+
+/* use v1 to calculate boundbox */
+static void bound_rectf(rctf *box, float *v1)
+{
+	if(v1[0] < box->xmin) box->xmin= v1[0];
+	if(v1[0] > box->xmax) box->xmax= v1[0];
+	if(v1[1] < box->ymin) box->ymin= v1[1];
+	if(v1[1] > box->ymax) box->ymax= v1[1];
+}
+
+
+/* halfway splitting, for initializing a more regular tree */
+static void isb_bsp_split_init(ISBBranch *root, MemArena *mem, int level)
+{
+	
+	/* if level > 0 we create new branches and go deeper*/
+	if(level > 0) {
+		ISBBranch *left, *right;
+		int i;
+		
+		/* splitpoint */
+		root->divider[0]= 0.5f*(root->box.xmin+root->box.xmax);
+		root->divider[1]= 0.5f*(root->box.ymin+root->box.ymax);
+		
+		/* find best splitpoint */
+		if(root->box.xmax-root->box.xmin > root->box.ymax-root->box.ymin)
+			i= root->index= 0;
+		else
+			i= root->index= 1;
+		
+		left= root->left= BLI_memarena_alloc(mem, sizeof(ISBBranch));
+		right= root->right= BLI_memarena_alloc(mem, sizeof(ISBBranch));
+		
+		/* box info */
+		left->box= root->box;
+		right->box= root->box;
+		if(i==0) {
+			left->box.xmax= root->divider[0];
+			right->box.xmin= root->divider[0];
+		}
+		else {
+			left->box.ymax= root->divider[1];
+			right->box.ymin= root->divider[1];
+		}
+		isb_bsp_split_init(left, mem, level-1);
+		isb_bsp_split_init(right, mem, level-1);
+	}
+	else {
+		/* we add sample array */
+		root->samples= BLI_memarena_alloc(mem, BSPMAX_SAMPLE*sizeof(void *));
+	}
+}
+
+/* note; if all samples on same location we just spread them over 2 new branches */
+static void isb_bsp_split(ISBBranch *root, MemArena *mem)
+{
+	ISBBranch *left, *right;
+	ISBSample *samples[BSPMAX_SAMPLE];
+	int a, i;
+
+	/* splitpoint */
+	root->divider[0]= root->divider[1]= 0.0f;
+	for(a=BSPMAX_SAMPLE-1; a>=0; a--) {
+		root->divider[0]+= root->samples[a]->zco[0];
+		root->divider[1]+= root->samples[a]->zco[1];
+	}
+	root->divider[0]/= BSPMAX_SAMPLE;
+	root->divider[1]/= BSPMAX_SAMPLE;
+	
+	/* find best splitpoint */
+	if(root->box.xmax-root->box.xmin > root->box.ymax-root->box.ymin)
+		i= root->index= 0;
+	else
+		i= root->index= 1;
+	
+	/* new branches */
+	left= root->left= BLI_memarena_alloc(mem, sizeof(ISBBranch));
+	right= root->right= BLI_memarena_alloc(mem, sizeof(ISBBranch));
+
+	/* new sample array */
+	left->samples= BLI_memarena_alloc(mem, BSPMAX_SAMPLE*sizeof(void *));
+	right->samples= samples; // tmp
+	
+	/* split samples */
+	for(a=BSPMAX_SAMPLE-1; a>=0; a--) {
+		int comp= 0;
+		/* this prevents adding samples all to 1 branch when divider is equal to samples */
+		if(root->samples[a]->zco[i] == root->divider[i])
+			comp= a & 1;
+		else if(root->samples[a]->zco[i] < root->divider[i])
+			comp= 1;
+		
+		if(comp==1) {
+			left->samples[left->totsamp]= root->samples[a];
+			left->totsamp++;
+		}
+		else {
+			right->samples[right->totsamp]= root->samples[a];
+			right->totsamp++;
+		}
+	}
+	
+	/* copy samples from tmp */
+	memcpy(root->samples, samples, right->totsamp*(sizeof(void *)));
+	right->samples= root->samples;
+	root->samples= NULL;
+	
+	/* box info */
+	left->box= root->box;
+	right->box= root->box;
+	if(i==0) {
+		left->box.xmax= root->divider[0];
+		right->box.xmin= root->divider[0];
+	}
+	else {
+		left->box.ymax= root->divider[1];
+		right->box.ymin= root->divider[1];
+	}
+}
+
+/* inserts sample in main tree, also splits on threshold */
+/* returns 1 if error */
+static int isb_bsp_insert(ISBBranch *root, MemArena *memarena, ISBSample *sample)
+{
+	ISBBranch *bspn= root;
+	float *zco= sample->zco;
+	int i= 0;
+	
+	/* debug counter, also used to check if something was filled in ever */
+	root->totsamp++;
+	
+	/* going over branches until last one found */
+	while(bspn->left) {
+		if(zco[bspn->index] <= bspn->divider[bspn->index])
+			bspn= bspn->left;
+		else
+			bspn= bspn->right;
+		i++;
+	}
+	/* bspn now is the last branch */
+	
+	if(bspn->totsamp==BSPMAX_SAMPLE) {
+		printf("error in bsp branch\n");	/* only for debug, cannot happen */
+		return 1;
+	}
+	
+	/* insert */
+	bspn->samples[bspn->totsamp]= sample;
+	bspn->totsamp++;
+	
+	/* split if allowed and needed */
+	if(bspn->totsamp==BSPMAX_SAMPLE) {
+		if(i==BSPMAX_DEPTH) {
+			bspn->totsamp--;	/* stop filling in... will give errors */
+			return 1;
+		}
+		isb_bsp_split(bspn, memarena);
+	}
+	return 0;
+}
+
+static float VecLen2f( float *v1, float *v2)
+{
+	float x= v1[0]-v2[0];
+	float y= v1[1]-v2[1];
+	return (float)sqrt(x*x+y*y);
+}
+
+/* initialize vars in face, for optimal point-in-face test */
+static void bspface_init_strand(BSPFace *face) 
+{
+	
+	face->radline= 0.5f*VecLen2f(face->v1, face->v2);
+	
+	VecMidf(face->vec1, face->v1, face->v2);
+	if(face->v4)
+		VecMidf(face->vec2, face->v3, face->v4);
+	else
+		VECCOPY(face->vec2, face->v3);
+	
+	face->rc[0]= face->vec2[0]-face->vec1[0];
+	face->rc[1]= face->vec2[1]-face->vec1[1];
+	face->rc[2]= face->vec2[2]-face->vec1[2];
+	
+	face->len= face->rc[0]*face->rc[0]+ face->rc[1]*face->rc[1];
+	
+	if(face->len!=0.0f) {
+		face->radline_end= face->radline/sqrt(face->len);
+		face->len= 1.0f/face->len;
+	}
+}
+
+/* brought back to a simple 2d case */
+static int point_behind_strand(float *p, BSPFace *face)
+{
+	/* v1 - v2 is radius, v1 - v3 length */
+	float dist, rc[2], pt[2];
+	
+	/* using code from PdistVL2Dfl(), distance vec to line-piece */
+
+	if(face->len==0.0f) {
+		rc[0]= p[0]-face->vec1[0];
+		rc[1]= p[1]-face->vec1[1];
+		dist= (float)(sqrt(rc[0]*rc[0]+ rc[1]*rc[1]));
+		
+		if(dist < face->radline)
+			return 1;
+	}
+	else {
+		float labda= ( face->rc[0]*(p[0]-face->vec1[0]) + face->rc[1]*(p[1]-face->vec1[1]) )*face->len;
+		
+		if(labda > -face->radline_end && labda < 1.0f+face->radline_end) { 
+			/* hesse for dist: */
+			//dist= (float)(fabs( (p[0]-vec2[0])*rc[1] + (p[1]-vec2[1])*rc[0])/len);
+			
+			pt[0]= labda*face->rc[0]+face->vec1[0];
+			pt[1]= labda*face->rc[1]+face->vec1[1];
+			
+			rc[0]= pt[0]-p[0];
+			rc[1]= pt[1]-p[1];
+			dist= (float)sqrt(rc[0]*rc[0]+ rc[1]*rc[1]);
+			
+			if(dist < face->radline) {
+				float zval= face->vec1[2] + labda*face->rc[2];
+				if(p[2] > zval)
+					return 1;
+			}
+		}
+	}
+	return 0;
+}
+
+
+/* return 1 if inside. code derived from src/parametrizer.c */
+static int point_behind_tria2d(float *p, float *v1, float *v2, float *v3)
+{
+	float a[2], c[2], h[2], div;
+	float u, v;
+	
+	a[0] = v2[0] - v1[0];
+	a[1] = v2[1] - v1[1];
+	c[0] = v3[0] - v1[0];
+	c[1] = v3[1] - v1[1];
+	
+	div = a[0]*c[1] - a[1]*c[0];
+	if(div==0.0f)
+		return 0;
+	
+	h[0] = p[0] - v1[0];
+	h[1] = p[1] - v1[1];
+	
+	div = 1.0f/div;
+	
+	u = (h[0]*c[1] - h[1]*c[0])*div;
+	if(u >= 0.0f) {
+		v = (a[0]*h[1] - a[1]*h[0])*div;
+		if(v >= 0.0f) {
+			if( u + v <= 1.0f) {
+				/* inside, now check if point p is behind */
+				float z=  (1.0f-u-v)*v1[2] + u*v2[2] + v*v3[2];
+				if(z <= p[2])
+					return 1;
+			}
+		}
+	}
+	
+	return 0;
+}
+
+#if 0
+/* tested these calls, but it gives inaccuracy, 'side' cannot be found reliably using v3 */
+
+/* check if line v1-v2 has all rect points on other side of point v3 */
+static int rect_outside_line(rctf *rect, float *v1, float *v2, float *v3)
+{
+	float a, b, c;
+	int side;
+	
+	/* line formula for v1-v2 */
+	a= v2[1]-v1[1];
+	b= v1[0]-v2[0];
+	c= -a*v1[0] - b*v1[1];
+	side= a*v3[0] + b*v3[1] + c < 0.0f;
+	
+	/* the four quad points */
+	if( side==(rect->xmin*a + rect->ymin*b + c >= 0.0f) )
+		if( side==(rect->xmax*a + rect->ymin*b + c >= 0.0f) )
+			if( side==(rect->xmax*a + rect->ymax*b + c >= 0.0f) )
+				if( side==(rect->xmin*a + rect->ymax*b + c >= 0.0f) )
+					return 1;
+	return 0;
+}
+
+/* check if one of the triangle edges separates all rect points on 1 side */
+static int rect_isect_tria(rctf *rect, float *v1, float *v2, float *v3)
+{
+	if(rect_outside_line(rect, v1, v2, v3))
+		return 0;
+	if(rect_outside_line(rect, v2, v3, v1))
+		return 0;
+	if(rect_outside_line(rect, v3, v1, v2))
+		return 0;
+	return 1;
+}
+#endif
+
+/* if face overlaps a branch, it executes func. recursive */
+static void isb_bsp_face_inside(ISBBranch *bspn, BSPFace *face)
+{
+	
+	/* are we descending? */
+	if(bspn->left) {
+		/* hrmf, the box struct cannot be addressed with index */
+		if(bspn->index==0) {
+			if(face->box.xmin <= bspn->divider[0])
+				isb_bsp_face_inside(bspn->left, face);
+			if(face->box.xmax > bspn->divider[0])
+				isb_bsp_face_inside(bspn->right, face);
+		}
+		else {
+			if(face->box.ymin <= bspn->divider[1])
+				isb_bsp_face_inside(bspn->left, face);
+			if(face->box.ymax > bspn->divider[1])
+				isb_bsp_face_inside(bspn->right, face);
+		}
+	}
+	else {
+		/* else: end branch reached */
+		int a;
+		
+		if(bspn->totsamp==0) return;
+		
+		/* check for nodes entirely in shadow, can be skipped */
+		if(bspn->totsamp==bspn->full)
+			return;
+		
+		/* if bsp node is entirely in front of face, give up */
+		if(bspn->box.zmax < face->box.zmin)
+			return;
+		
+		/* if face boundbox is outside of branch rect, give up */
+		if(0==BLI_isect_rctf((rctf *)&face->box, (rctf *)&bspn->box, NULL))
+			return;
+		
+		/* test all points inside branch */
+		for(a=bspn->totsamp-1; a>=0; a--) {
+			ISBSample *samp= bspn->samples[a];
+			
+			if(samp->facenr!=face->facenr && samp->shadfac) {
+				if(face->box.zmax < samp->zco[2]) {
+					if(BLI_in_rctf((rctf *)&face->box, samp->zco[0], samp->zco[1])) {
+						int inshadow= 0;
+						
+						if(face->type) {
+							if(point_behind_strand(samp->zco, face)) 
+								inshadow= 1;
+						}
+						else if( point_behind_tria2d(samp->zco, face->v1, face->v2, face->v3))
+							inshadow= 1;
+						else if(face->v4 && point_behind_tria2d(samp->zco, face->v1, face->v3, face->v4))
+							inshadow= 1;
+
+						if(inshadow) {
+							*(samp->shadfac) += face->shad_alpha;
+							/* optimize; is_full means shad_alpha==4096 */
+							if(*(samp->shadfac) >= 4096 || face->is_full) {
+								bspn->full++;
+								samp->shadfac= NULL;
+							}
+						}
+					}
+				}
+			}
+		}
+	}
+}
+
+/* based on available samples, recalculate the bounding box for bsp nodes, recursive */
+static void isb_bsp_recalc_box(ISBBranch *root)
+{
+	if(root->left) {
+		isb_bsp_recalc_box(root->left);
+		isb_bsp_recalc_box(root->right);
+	}
+	else if(root->totsamp) {
+		int a;
+		
+		init_box(&root->box);
+		for(a=root->totsamp-1; a>=0; a--)
+			bound_boxf(&root->box, root->samples[a]->zco);
+	}	
+}
+
+/* callback function for zbuf clip */
+static void isb_bsp_test_strand(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4)
+{
+	BSPFace face;
+	
+	face.v1= v1;
+	face.v2= v2;
+	face.v3= v3;
+	face.v4= v4;
+	face.facenr= zvlnr & ~RE_QUAD_OFFS;
+	face.type= R_STRAND;
+	if(R.osa)
+		face.shad_alpha= (short)ceil(4096.0f*zspan->shad_alpha/(float)R.osa);
+	else
+		face.shad_alpha= (short)ceil(4096.0f*zspan->shad_alpha);
+	
+	face.is_full= (zspan->shad_alpha==1.0f);
+	
+	/* setup boundbox */
+	init_box(&face.box);
+	bound_boxf(&face.box, v1);
+	bound_boxf(&face.box, v2);
+	bound_boxf(&face.box, v3);
+	if(v4)
+		bound_boxf(&face.box, v4);
+	
+	/* optimize values */
+	bspface_init_strand(&face);
+	
+	isb_bsp_face_inside((ISBBranch *)zspan->rectz, &face);
+	
+}
 
+/* callback function for zbuf clip */
+static void isb_bsp_test_face(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4) 
+{
+	BSPFace face;
+	
+	face.v1= v1;
+	face.v2= v2;
+	face.v3= v3;
+	face.v4= v4;
+	face.facenr= zvlnr & ~RE_QUAD_OFFS;
+	face.type= 0;
+	if(R.osa)
+		face.shad_alpha= (short)ceil(4096.0f*zspan->shad_alpha/(float)R.osa);
+	else
+		face.shad_alpha= (short)ceil(4096.0f*zspan->shad_alpha);
+	
+	face.is_full= (zspan->shad_alpha==1.0f);
+	
+	/* setup boundbox */
+	init_box(&face.box);
+	bound_boxf(&face.box, v1);
+	bound_boxf(&face.box, v2);
+	bound_boxf(&face.box, v3);
+	if(v4)
+		bound_boxf(&face.box, v4);
+
+	isb_bsp_face_inside((ISBBranch *)zspan->rectz, &face);
+}
 
+static int testclip_minmax(float *ho, float *minmax)
+{
+	float wco= ho[3];
+	int flag= 0;
+	
+	if( ho[0] > minmax[1]*wco) flag = 1;
+	else if( ho[0]< minmax[0]*wco) flag = 2;
+	
+	if( ho[1] > minmax[3]*wco) flag |= 4;
+	else if( ho[1]< minmax[2]*wco) flag |= 8;
+	
+	return flag;
+}
+
+/* main loop going over all faces and check in bsp overlaps, fill in shadfac values */
+static void isb_bsp_fillfaces(Render *re, LampRen *lar, ISBBranch *root)
+{
+	ShadBuf *shb= lar->shb;
+	ZSpan zspan, zspanstrand;
+	VlakRen *vlr= NULL;
+	Material *ma= NULL;
+	float minmaxf[4];
+	int size= shb->size;
+	int a, ok=1, lay= -1;
+	
+	/* further optimize, also sets minz maxz */
+	isb_bsp_recalc_box(root);
+	
+	/* extra clipping for minmax */
+	minmaxf[0]= (2.0f*root->box.xmin - size-2.0f)/size;
+	minmaxf[1]= (2.0f*root->box.xmax - size+2.0f)/size;
+	minmaxf[2]= (2.0f*root->box.ymin - size-2.0f)/size;
+	minmaxf[3]= (2.0f*root->box.ymax - size+2.0f)/size;
+	
+	if(lar->mode & LA_LAYER) lay= lar->lay;
+	
+	/* (ab)use zspan, since we use zbuffer clipping code */
+	zbuf_alloc_span(&zspan, size, size);
+	
+	zspan.zmulx=  ((float)size)/2.0f;
+	zspan.zmuly=  ((float)size)/2.0f;
+	zspan.zofsx= -0.5f;
+	zspan.zofsy= -0.5f;
+	
+	/* pass on bsp root to zspan */
+	zspan.rectz= (int *)root;
+	
+	/* filling methods */
+	zspanstrand= zspan;
+	//	zspan.zbuflinefunc= zbufline_onlyZ;
+	zspan.zbuffunc= isb_bsp_test_face;
+	zspanstrand.zbuffunc= isb_bsp_test_strand;
+	
+	for(a=0; a<re->totvlak; a++) {
+		
+		if((a & 255)==0) vlr= re->blovl[a>>8];
+		else vlr++;
+		
+		/* note, these conditions are copied in shadowbuf_autoclip() */
+		if(vlr->mat!= ma) {
+			ma= vlr->mat;
+			ok= 1;
+			if((ma->mode & MA_SHADBUF)==0) ok= 0;
+			zspanstrand.shad_alpha= zspan.shad_alpha= ma->shad_alpha;
+		}
+		
+		if(ok && (vlr->lay & lay)) {
+			float hoco[4][4];
+			int c1, c2, c3, c4=0;
+			int d1, d2, d3, d4=0;
+			int partclip;
+			
+			/* create hocos per face, it is while render */
+			projectvert(vlr->v1->co, shb->persmat, hoco[0]); d1= testclip_minmax(hoco[0], minmaxf);
+			projectvert(vlr->v2->co, shb->persmat, hoco[1]); d2= testclip_minmax(hoco[1], minmaxf);
+			projectvert(vlr->v3->co, shb->persmat, hoco[2]); d3= testclip_minmax(hoco[2], minmaxf);
+			if(vlr->v4) {
+				projectvert(vlr->v4->co, shb->persmat, hoco[3]); d4= testclip_minmax(hoco[3], minmaxf);
+			}
+			
+			/* minmax clipping */
+			if(vlr->v4) partclip= d1 & d2 & d3 & d4;
+			else partclip= d1 & d2 & d3;
+			
+			if(partclip==0) {
+				
+				/* window clipping */
+				c1= testclip(hoco[0]); 
+				c2= testclip(hoco[1]); 
+				c3= testclip(hoco[2]); 
+				if(vlr->v4)
+					c4= testclip(hoco[3]); 
+				
+				/* ***** NO WIRE YET */			
+				if(ma->mode & MA_WIRE) 
+					zbufclipwire(&zspan, a+1, vlr);
+				else if(vlr->v4) {
+					if(vlr->flag & R_STRAND)
+						zbufclip4(&zspanstrand, a+1, hoco[0], hoco[1], hoco[2], hoco[3], c1, c2, c3, c4);
+					else
+						zbufclip4(&zspan, a+1, hoco[0], hoco[1], hoco[2], hoco[3], c1, c2, c3, c4);
+				}
+				else
+					zbufclip(&zspan, a+1, hoco[0], hoco[1], hoco[2], c1, c2, c3);
+				
+			}
+		}
+	}
+	
+	zbuf_free_span(&zspan);
+	
+}
+
+
+/* returns 1 when the viewpixel is visible in lampbuffer */
+static int viewpixel_to_lampbuf(ShadBuf *shb, VlakRen *vlr, float x, float y, float *co)
+{
+	float hoco[4], *v1= vlr->v1->co, *nor= vlr->n;
+	float dface, fac, siz;
+	
+	/* from shadepixel() */
+	dface= v1[0]*nor[0] + v1[1]*nor[1] + v1[2]*nor[2];
+	hoco[3]= 1.0f;
+	
+	/* ortho viewplane cannot intersect using view vector originating in (0,0,0) */
+	if(R.r.mode & R_ORTHO) {
+		/* x and y 3d coordinate can be derived from pixel coord and winmat */
+		float fx= 2.0/(R.winx*R.winmat[0][0]);
+		float fy= 2.0/(R.winy*R.winmat[1][1]);
+		
+		hoco[0]= (x - 0.5*R.winx)*fx - R.winmat[3][0]/R.winmat[0][0];
+		hoco[1]= (y - 0.5*R.winy)*fy - R.winmat[3][1]/R.winmat[1][1];
+		
+		/* using a*x + b*y + c*z = d equation, (a b c) is normal */
+		if(nor[2]!=0.0f)
+			hoco[2]= (dface - nor[0]*hoco[0] - nor[1]*hoco[1])/nor[2];
+		else
+			hoco[2]= 0.0f;
+	}
+	else {
+		float div, view[3];
+		
+		calc_view_vector(view, x, y);
+		
+		div= nor[0]*view[0] + nor[1]*view[1] + nor[2]*view[2];
+		if (div==0.0f) 
+			return 0;
+		
+		fac= dface/div;
+		
+		hoco[0]= fac*view[0];
+		hoco[1]= fac*view[1];
+		hoco[2]= fac*view[2];
+	}
+	
+	/* move 3d vector to lampbuf */
+	MTC_Mat4MulVec4fl(shb->persmat, hoco);	/* rational hom co */
+	
+	/* clip We can test for -1.0/1.0 because of the properties of the
+	 * coordinate transformations. */
+	if(hoco[0]<-hoco[3] || hoco[0]>hoco[3])
+		return 0;
+	if(hoco[1]<-hoco[3] || hoco[1]>hoco[3])
+		return 0;
+	
+	siz= 0.5f*(float)shb->size;
+	co[0]= siz*(1.0f+hoco[0]/hoco[3]) -0.5f;
+	co[1]= siz*(1.0f+hoco[1]/hoco[3]) -0.5f;
+	
+	/* Clip for z: clipsta and clipend clip values of the shadow buffer */
+	fac= (hoco[2]/hoco[3]);
+	
+	if(fac >= 1.0f || fac <= -1.0f)
+		return 0;
+	else
+		co[2]= ((float)0x7FFFFFFF)*fac;
+	
+	/* XXXX bias, much less than normal shadbuf, or do we need a constant? */
+	co[2] -= 0.05f*shb->bias;
+	
+	return 1;
+}
+
+
+/* adding samples, solid case */
+static int isb_add_samples(RenderPart *pa, ISBBranch *root, MemArena *memarena, ISBSample **samplebuf)
+{
+	int xi, yi, *xcos, *ycos;
+	int sample, bsp_err= 0;
+	
+	/* bsp split doesn't like to handle regular sequenes */
+	xcos= MEM_mallocN( pa->rectx*sizeof(int), "xcos");
+	ycos= MEM_mallocN( pa->recty*sizeof(int), "ycos");
+	for(xi=0; xi<pa->rectx; xi++)
+		xcos[xi]= xi;
+	for(yi=0; yi<pa->recty; yi++)
+		ycos[yi]= yi;
+	BLI_array_randomize(xcos, sizeof(int), pa->rectx, 12345);
+	BLI_array_randomize(ycos, sizeof(int), pa->recty, 54321);
+	
+	for(sample=0; sample<(R.osa?R.osa:1); sample++) {
+		ISBSample *samp= samplebuf[sample], *samp1;
+		
+		for(yi=0; yi<pa->recty; yi++) {
+			int y= ycos[yi];
+			for(xi=0; xi<pa->rectx; xi++) {
+				int x= xcos[xi];
+				samp1= samp + y*pa->rectx + x;
+				if(samp1->facenr)
+					bsp_err |= isb_bsp_insert(root, memarena, samp1);
+			}
+			if(bsp_err) break;
+		}
+	}	
+	
+	MEM_freeN(xcos);
+	MEM_freeN(ycos);
+
+	return bsp_err;
+}
+
+/* solid version */
+/* lar->shb, pa->rectz and pa->rectp should exist */
+static void isb_make_buffer(RenderPart *pa, LampRen *lar)
+{
+	ShadBuf *shb= lar->shb;
+	ISBData *isbdata;
+	ISBSample *samp, *samplebuf[16];	/* should be RE_MAX_OSA */
+	ISBBranch root;
+	MemArena *memarena;
+	long *rd;
+	int *rectp, x, y, sindex, sample, bsp_err=0;
+	
+	/* storage for shadow, per thread */
+	isbdata= shb->isb_result[pa->thread];
+	
+	/* to map the shi->xs and ys coordinate */
+	isbdata->minx= pa->disprect.xmin;
+	isbdata->miny= pa->disprect.ymin;
+	isbdata->rectx= pa->rectx;
+	isbdata->recty= pa->recty;
+	
+	/* branches are added using memarena (32k branches) */
+	memarena = BLI_memarena_new(0x8000 * sizeof(ISBBranch));
+	
+	/* samplebuf is in camera view space (pixels) */
+	for(sample=0; sample<(R.osa?R.osa:1); sample++)
+		samplebuf[sample]= MEM_callocN(sizeof(ISBSample)*pa->rectx*pa->recty, "isb samplebuf");
+	
+	/* end result, ISBSamples point to this */
+	isbdata->shadfacs= MEM_callocN(pa->rectx*pa->recty*sizeof(short), "isb shadfacs");
+	
+	/* setup bsp root */
+	memset(&root, 0, sizeof(ISBBranch));
+	root.box.xmin= (float)shb->size;
+	root.box.ymin= (float)shb->size;
+	
+	/* create the sample buffers */
+	for(sindex=0, y=0; y<pa->recty; y++) {
+		for(x=0; x<pa->rectx; x++, sindex++) {
+			
+			/* this makes it a long function, but splitting it out would mean 10+ arguments */
+			/* first check OSA case */
+			if(R.osa) {
+				rd= pa->rectdaps + sindex;
+				if(*rd) {
+					float xs= (float)(x + pa->disprect.xmin);
+					float ys= (float)(y + pa->disprect.ymin);
+					
+					for(sample=0; sample<R.osa; sample++) {
+						PixStr *ps= (PixStr *)(*rd);
+						int mask= (1<<sample);
+						
+						while(ps) {
+							if(ps->mask & mask)
+								break;
+							ps= ps->next;
+						}
+						if(ps && ps->facenr>0) {
+							VlakRen *vlr= RE_findOrAddVlak(&R, (ps->facenr-1) & RE_QUAD_MASK);
+							
+							samp= samplebuf[sample] + sindex;
+							/* convert image plane pixel location to lamp buffer space */
+							if(viewpixel_to_lampbuf(shb, vlr, xs + R.jit[sample][0], ys + R.jit[sample][1], samp->zco)) {
+								samp->facenr= ps->facenr & ~RE_QUAD_OFFS;
+								samp->shadfac= isbdata->shadfacs + sindex;
+								bound_rectf((rctf *)&root.box, samp->zco);
+							}
+						}
+					}
+				}
+			}
+			else {
+				rectp= pa->rectp + sindex;
+				if(*rectp>0) {
+					VlakRen *vlr= RE_findOrAddVlak(&R, (*rectp-1) & RE_QUAD_MASK);
+					float xs= (float)(x + pa->disprect.xmin);
+					float ys= (float)(y + pa->disprect.ymin);
+					
+					samp= samplebuf[0] + sindex;
+					/* convert image plane pixel location to lamp buffer space */
+					if(viewpixel_to_lampbuf(shb, vlr, xs, ys, samp->zco)) {
+						samp->facenr= *rectp & ~RE_QUAD_OFFS;
+						samp->shadfac= isbdata->shadfacs + sindex;
+						bound_rectf((rctf *)&root.box, samp->zco);
+					}
+				}
+			}
+		}
+	}
+	
+	/* simple method to see if we have samples */
+	if(root.box.xmin != (float)shb->size) {
+		/* now create a regular split, root.box has the initial bounding box of all pixels */
+		/* split bsp 8 levels deep, in regular grid (16 x 16) */
+		isb_bsp_split_init(&root, memarena, 8);
+		
+		/* insert all samples in BSP now */
+		bsp_err= isb_add_samples(pa, &root, memarena, samplebuf);
+			
+		if(bsp_err==0) {
+			/* go over all faces and fill in shadow values */
+			
+			isb_bsp_fillfaces(&R, lar, &root);	/* shb->persmat should have been calculated */
+		}
+	}
+	else {
+		MEM_freeN(isbdata->shadfacs);
+		isbdata->shadfacs= NULL;
+	}
+
+	/* free BSP */
+	BLI_memarena_free(memarena);
+	
+	/* free samples */
+	for(x=0; x<(R.osa?R.osa:1); x++)
+		MEM_freeN(samplebuf[x]);
+	
+	if(bsp_err) printf("error in filling bsp\n");
+}
+
+/* add sample to buffer, isbsa is the root sample in a buffer */
+static ISBSampleA *isb_alloc_sample_transp(ISBSampleA **isbsa, MemArena *mem)
+{
+	ISBSampleA *new;
+	
+	new= BLI_memarena_alloc(mem, sizeof(ISBSampleA));
+	if(*isbsa)
+		new->next= (*isbsa);
+	
+	*isbsa= new;
+	return new;
+}
+
+/* adding samples in BSP, transparent case */
+static int isb_add_samples_transp(RenderPart *pa, ISBBranch *root, MemArena *memarena, ISBSampleA ***samplebuf)
+{
+	int xi, yi, *xcos, *ycos;
+	int sample, bsp_err= 0;
+	
+	/* bsp split doesn't like to handle regular sequenes */
+	xcos= MEM_mallocN( pa->rectx*sizeof(int), "xcos");
+	ycos= MEM_mallocN( pa->recty*sizeof(int), "ycos");
+	for(xi=0; xi<pa->rectx; xi++)
+		xcos[xi]= xi;
+	for(yi=0; yi<pa->recty; yi++)
+		ycos[yi]= yi;
+	BLI_array_randomize(xcos, sizeof(int), pa->rectx, 12345);
+	BLI_array_randomize(ycos, sizeof(int), pa->recty, 54321);
+	
+	for(sample=0; sample<(R.osa?R.osa:1); sample++) {
+		ISBSampleA **samp= samplebuf[sample], *samp1;
+		
+		for(yi=0; yi<pa->recty; yi++) {
+			int y= ycos[yi];
+			for(xi=0; xi<pa->rectx; xi++) {
+				int x= xcos[xi];
+				
+				samp1= *(samp + y*pa->rectx + x);
+				while(samp1) {
+					bsp_err |= isb_bsp_insert(root, memarena, (ISBSample *)samp1);
+					samp1= samp1->next;
+				}
+			}
+			if(bsp_err) break;
+		}
+	}	
+	
+	MEM_freeN(xcos);
+	MEM_freeN(ycos);
+	
+	return bsp_err;
+}
+
+/* storage of shadow results, transparent case */
+static void isb_add_shadfac_transp(ISBShadfacA **isbsapp, MemArena *mem, int facenr, short shadfac, short samples)
+{
+	ISBShadfacA *new;
+	float shadfacf;
+	
+	/* in osa case, the samples were filled in with factor 1.0/R.osa. if fewer samples we have to correct */
+	if(R.osa)
+		shadfacf= ((float)shadfac*R.osa)/(4096.0*samples);
+	else
+		shadfacf= ((float)shadfac)/(4096.0);
+		
+	new= BLI_memarena_alloc(mem, sizeof(ISBShadfacA));
+	new->facenr= facenr & ~RE_QUAD_OFFS;
+	new->shadfac= shadfacf;
+	if(*isbsapp)
+		new->next= (*isbsapp);
+	
+	*isbsapp= new;
+}
+
+/* Ztransp version */
+/* lar->shb, pa->rectz and pa->rectp should exist */
+static void isb_make_buffer_transp(RenderPart *pa, APixstr *apixbuf, LampRen *lar)
+{
+	ShadBuf *shb= lar->shb;
+	ISBData *isbdata;
+	ISBSampleA *samp, **samplebuf[16];	/* MAX_OSA */
+	ISBBranch root;
+	MemArena *memarena;
+	APixstr *ap;
+	int x, y, sindex, sample, bsp_err=0;
+	
+	/* storage for shadow, per thread */
+	isbdata= shb->isb_result[pa->thread];
+	
+	/* to map the shi->xs and ys coordinate */
+	isbdata->minx= pa->disprect.xmin;
+	isbdata->miny= pa->disprect.ymin;
+	isbdata->rectx= pa->rectx;
+	isbdata->recty= pa->recty;
+	
+	/* branches are added using memarena (32k branches) */
+	memarena = BLI_memarena_new(0x8000 * sizeof(ISBBranch));
+	
+	/* samplebuf is in camera view space (pixels) */
+	for(sample=0; sample<(R.osa?R.osa:1); sample++)
+		samplebuf[sample]= MEM_callocN(sizeof(void *)*pa->rectx*pa->recty, "isb alpha samplebuf");
+	
+	/* setup bsp root */
+	memset(&root, 0, sizeof(ISBBranch));
+	root.box.xmin= (float)shb->size;
+	root.box.ymin= (float)shb->size;
+
+	/* create the sample buffers */
+	for(ap= apixbuf, sindex=0, y=0; y<pa->recty; y++) {
+		for(x=0; x<pa->rectx; x++, sindex++, ap++) {
+			
+			if(ap->p[0]) {
+				APixstr *apn;
+				float xs= (float)(x + pa->disprect.xmin);
+				float ys= (float)(y + pa->disprect.ymin);
+				
+				for(apn=ap; apn; apn= apn->next) {
+					int a;
+					for(a=0; a<4; a++) {
+						if(apn->p[a]) {
+							VlakRen *vlr= RE_findOrAddVlak(&R, (apn->p[a]-1) & RE_QUAD_MASK);
+							float zco[3];
+							
+							/* here we store shadfac, easier to create the end storage buffer. needs zero'ed, multiple shadowbufs use it */
+							apn->shadfac[a]= 0;
+							
+							if(R.osa) {
+								for(sample=0; sample<R.osa; sample++) {
+									int mask= (1<<sample);
+									
+									if(apn->mask[a] & mask) {
+										
+										/* convert image plane pixel location to lamp buffer space */
+										if(viewpixel_to_lampbuf(shb, vlr, xs + R.jit[sample][0], ys + R.jit[sample][1], zco)) {
+											samp= isb_alloc_sample_transp(samplebuf[sample] + sindex, memarena);
+											samp->facenr= apn->p[a] & ~RE_QUAD_OFFS;
+											samp->shadfac= &apn->shadfac[a];
+											
+											VECCOPY(samp->zco, zco);
+											bound_rectf((rctf *)&root.box, samp->zco);
+										}
+									}
+								}
+							}
+							else {
+								
+								/* convert image plane pixel location to lamp buffer space */
+								if(viewpixel_to_lampbuf(shb, vlr, xs, ys, zco)) {
+									
+									samp= isb_alloc_sample_transp(samplebuf[0] + sindex, memarena);
+									samp->facenr= apn->p[a] & ~RE_QUAD_OFFS;
+									samp->shadfac= &apn->shadfac[a];
+									
+									VECCOPY(samp->zco, zco);
+									bound_rectf((rctf *)&root.box, samp->zco);
+								}
+							}
+						}
+					}
+				}
+			}
+		}
+	}
+	
+	/* simple method to see if we have samples */
+	if(root.box.xmin != (float)shb->size) {
+		/* now create a regular split, root.box has the initial bounding box of all pixels */
+		/* split bsp 8 levels deep, in regular grid (16 x 16) */
+		isb_bsp_split_init(&root, memarena, 8);
+		
+		/* insert all samples in BSP now */
+		bsp_err= isb_add_samples_transp(pa, &root, memarena, samplebuf);
+		
+		if(bsp_err==0) {
+			ISBShadfacA **isbsa;
+			
+			/* go over all faces and fill in shadow values */
+			isb_bsp_fillfaces(&R, lar, &root);	/* shb->persmat should have been calculated */
+			
+			/* copy shadow samples to persistant buffer, reduce memory overhead */
+			isbsa= isbdata->shadfaca= MEM_callocN(pa->rectx*pa->recty*sizeof(void *), "isb shadfacs");
+			
+			isbdata->memarena = BLI_memarena_new(0x8000 * sizeof(ISBSampleA));
+			
+			for(ap= apixbuf, x=pa->rectx*pa->recty; x>0; x--, ap++, isbsa++) {
+					
+				if(ap->p[0]) {
+					APixstr *apn;
+					for(apn=ap; apn; apn= apn->next) {
+						int a;
+						for(a=0; a<4; a++) {
+							if(apn->p[a] && apn->shadfac[a]) {
+								if(R.osa)
+									isb_add_shadfac_transp(isbsa, isbdata->memarena, apn->p[a], apn->shadfac[a], count_mask(apn->mask[a]));
+								else
+									isb_add_shadfac_transp(isbsa, isbdata->memarena, apn->p[a], apn->shadfac[a], 0);
+							}
+						}
+					}
+				}
+			}
+		}
+	}
+
+	/* free BSP */
+	BLI_memarena_free(memarena);
+
+	/* free samples */
+	for(x=0; x<(R.osa?R.osa:1); x++)
+		MEM_freeN(samplebuf[x]);
+
+	if(bsp_err) printf("error in filling bsp\n");
+}
+
+
+
+/* exported */
+
+/* returns amount of light (1.0 = no shadow) */
+/* note, shadepixel() rounds the coordinate, not the real sample info */
+float ISB_getshadow(ShadeInput *shi, ShadBuf *shb)
+{
+	/* if raytracing, we can't accept irregular shadow */
+	if(shi->depth==0) {
+		ISBData *isbdata= shb->isb_result[shi->thread];
+		
+		if(isbdata) {
+			if(isbdata->shadfacs || isbdata->shadfaca) {
+				int x= shi->xs - isbdata->minx;
+				
+				if(x >= 0 && x < isbdata->rectx) {
+					int y= shi->ys - isbdata->miny;
+			
+					if(y >= 0 && y < isbdata->recty) {
+						if(isbdata->shadfacs) {
+							short *sp= isbdata->shadfacs + y*isbdata->rectx + x;
+							return *sp>=4096?0.0f:1.0f - ((float)*sp)/4096.0f;
+						}
+						else {
+							int sindex= y*isbdata->rectx + x;
+							ISBShadfacA *isbsa= *(isbdata->shadfaca + sindex);
+							
+							while(isbsa) {
+								if(isbsa->facenr==shi->facenr+1)
+									return isbsa->shadfac>=1.0f?0.0f:1.0f - isbsa->shadfac;
+								isbsa= isbsa->next;
+							}
+						}
+					}
+				}
+			}
+		}
+	}
+	return 1.0f;
+}
+
+/* part is supposed to be solid zbuffered (apixbuf==NULL) or transparent zbuffered */
+void ISB_create(RenderPart *pa, APixstr *apixbuf)
+{
+	GroupObject *go;
+	
+	/* go over all lamps, and make the irregular buffers */
+	for(go=R.lights.first; go; go= go->next) {
+		LampRen *lar= go->lampren;
+		
+		if(lar->type==LA_SPOT && lar->shb && lar->buftype==LA_SHADBUF_IRREGULAR) {
+			
+			/* create storage for shadow, per thread */
+			lar->shb->isb_result[pa->thread]= MEM_callocN(sizeof(ISBData), "isb data");
+			
+			if(apixbuf)
+				isb_make_buffer_transp(pa, apixbuf, lar);
+			else
+				isb_make_buffer(pa, lar);
+		}
+	}
+}
+
+
+/* end of part rendering, free stored shadow data for this thread from all lamps */
+void ISB_free(RenderPart *pa)
+{
+	GroupObject *go;
+	
+	/* go over all lamps, and free the irregular buffers */
+	for(go=R.lights.first; go; go= go->next) {
+		LampRen *lar= go->lampren;
+		
+		if(lar->type==LA_SPOT && lar->shb && lar->buftype==LA_SHADBUF_IRREGULAR) {
+			ISBData *isbdata= lar->shb->isb_result[pa->thread];
+
+			if(isbdata) {
+				if(isbdata->shadfacs)
+					MEM_freeN(isbdata->shadfacs);
+				if(isbdata->shadfaca)
+					MEM_freeN(isbdata->shadfaca);
+				
+				if(isbdata->memarena)
+					BLI_memarena_free(isbdata->memarena);
+				
+				MEM_freeN(isbdata);
+				lar->shb->isb_result[pa->thread]= NULL;
+			}
+		}
+	}
+}
 
 
 
diff --git a/source/blender/render/intern/source/zbuf.c b/source/blender/render/intern/source/zbuf.c
index c46be0eec28..deb5031ebf3 100644
--- a/source/blender/render/intern/source/zbuf.c
+++ b/source/blender/render/intern/source/zbuf.c
@@ -37,6 +37,7 @@
 #include <limits.h>
 #include <string.h>
 
+#include "BLI_arithb.h"
 #include "BLI_blenlib.h"
 #include "BLI_threads.h"
 #include "BLI_jitter.h"
@@ -59,11 +60,12 @@
 
 /* local includes */
 #include "gammaCorrectionTables.h"
+#include "pixelblending.h"
 #include "render_types.h"
 #include "renderpipeline.h"
 #include "renderdatabase.h"
 #include "rendercore.h"
-#include "pixelblending.h"
+#include "shadbuf.h"
 
 /* own includes */
 #include "zbuf.h"
@@ -89,7 +91,7 @@ void zbuf_alloc_span(ZSpan *zspan, int rectx, int recty)
 	zspan->span2= MEM_mallocN(recty*sizeof(float), "zspan");
 }
 
-static void zbuf_free_span(ZSpan *zspan)
+void zbuf_free_span(ZSpan *zspan)
 {
 	if(zspan) {
 		if(zspan->span1) MEM_freeN(zspan->span1);
@@ -292,7 +294,7 @@ static APixstr *addpsA(ZSpan *zspan)
 	return zspan->curpstr;
 }
 
-static void zbufinvulAc4(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4)
+static void zbuffillAc4(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4)
 {
 	APixstr *ap, *apofs, *apn;
 	double zxd, zyd, zy0, zverg;
@@ -966,7 +968,7 @@ void zbufclipwire(ZSpan *zspan, int zvlnr, VlakRen *vlr)
  * @param v2 [4 floats, world coordinates] second vertex
  * @param v3 [4 floats, world coordinates] third vertex
  */
-static void zbufinvulGLinv4(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4) 
+static void zbuffillGLinv4(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4) 
 {
 	double zxd, zyd, zy0, zverg;
 	float x0,y0,z0;
@@ -1069,7 +1071,7 @@ static void zbufinvulGLinv4(ZSpan *zspan, int zvlnr, float *v1, float *v2, float
 
 /* uses spanbuffers */
 
-static void zbufinvulGL4(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4)
+static void zbuffillGL4(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4)
 {
 	double zxd, zyd, zy0, zverg;
 	float x0,y0,z0;
@@ -1181,7 +1183,7 @@ static void zbufinvulGL4(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v
  * @param v3 [4 floats, world coordinates] third vertex
  */
 
-static void zbufinvulGL_onlyZ(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4) 
+static void zbuffillGL_onlyZ(ZSpan *zspan, int zvlnr, float *v1, float *v2, float *v3, float *v4) 
 {
 	double zxd, zyd, zy0, zverg;
 	float x0,y0,z0;
@@ -1530,7 +1532,7 @@ void zbufclip(ZSpan *zspan, int zvlnr, float *f1, float *f2, float *f3, int c1,
 	zspan->zbuffunc(zspan, zvlnr, vez,vez+4,vez+8, NULL);
 }
 
-static void zbufclip4(ZSpan *zspan, int zvlnr, float *f1, float *f2, float *f3, float *f4, int c1, int c2, int c3, int c4)
+void zbufclip4(ZSpan *zspan, int zvlnr, float *f1, float *f2, float *f3, float *f4, int c1, int c2, int c3, int c4)
 {
 	float vez[16];
 	
@@ -1651,7 +1653,7 @@ void zbuffer_solid(RenderPart *pa, unsigned int lay, short layflag)
 	fillrect(pa->rectz, pa->rectx, pa->recty, 0x7FFFFFFF);
 	
 	/* filling methods */
-	zspan.zbuffunc= zbufinvulGL4;
+	zspan.zbuffunc= zbuffillGL4;
 	zspan.zbuflinefunc= zbufline;
 
 	/* part clipflag, threaded */
@@ -1671,8 +1673,8 @@ void zbuffer_solid(RenderPart *pa, unsigned int lay, short layflag)
 					env= (ma->mode & MA_ENV);
 					wire= (ma->mode & MA_WIRE);
 					
-					if(ma->mode & MA_ZINV) zspan.zbuffunc= zbufinvulGLinv4;
-					else zspan.zbuffunc= zbufinvulGL4;
+					if(ma->mode & MA_ZINV) zspan.zbuffunc= zbuffillGLinv4;
+					else zspan.zbuffunc= zbuffillGL4;
 				}
 			}
 			else if(all_z) {
@@ -1774,7 +1776,7 @@ void RE_zbufferall_radio(struct RadView *vw, RNode **rg_elem, int rg_totelem, Re
 	fillrect(zspan.rectp, vw->rectx, vw->recty, 0xFFFFFF);
 	
 	/* filling methods */
-	zspan.zbuffunc= zbufinvulGL4;
+	zspan.zbuffunc= zbuffillGL4;
 	
 	if(rg_elem) {	/* radio tool */
 		RNode **re, *rn;
@@ -1862,7 +1864,7 @@ void zbuffer_shadow(Render *re, LampRen *lar, int *rectz, int size, float jitx,
 	
 	/* filling methods */
 	zspan.zbuflinefunc= zbufline_onlyZ;
-	zspan.zbuffunc= zbufinvulGL_onlyZ;
+	zspan.zbuffunc= zbuffillGL_onlyZ;
 				
 	for(a=0; a<re->totvlak; a++) {
 
@@ -2429,7 +2431,7 @@ static void zbuffer_abuf(RenderPart *pa, APixstr *APixbuf, ListBase *apsmbase, u
 	zspan.apsmbase= apsmbase;
 	
 	/* filling methods */
-	zspan.zbuffunc= zbufinvulAc4;
+	zspan.zbuffunc= zbuffillAc4;
 	zspan.zbuflinefunc= zbuflineAc;
 	
 	/* part clipflag, 4 threads */
@@ -2732,6 +2734,10 @@ void zbuffer_transp_shade(RenderPart *pa, RenderLayer *rl, float *pass)
 	aprect= APixbuf;
 	rdrect= pa->rectdaps;
 	
+	/* irregular shadowb buffer creation */
+	if(R.r.mode & R_SHADOW)
+		ISB_create(pa, APixbuf);
+	
 	/* filtered render, for now we assume only 1 filter size */
 	if(pa->crop) {
 		crop= 1;
@@ -2756,7 +2762,7 @@ void zbuffer_transp_shade(RenderPart *pa, RenderLayer *rl, float *pass)
 		
 		for(x=pa->disprect.xmin+crop; x<pa->disprect.xmax-crop; x++, ap++, pass+=4, od++) {
 			
-			if(ap->p[0]==NULL) {
+			if(ap->p[0]==0) {
 				if(addpassflag & SCE_PASS_VECTOR) 
 					add_transp_speed(rl, od, NULL, 0.0f, rdrect);
 			}
@@ -2873,6 +2879,9 @@ void zbuffer_transp_shade(RenderPart *pa, RenderLayer *rl, float *pass)
 	MEM_freeN(APixbuf);
 	freepsA(&apsmbase);	
 
+	if(R.r.mode & R_SHADOW)
+		ISB_free(pa);
+
 }
 
 /* *************** */