--- ray/src/util/rttree_reduce.c	2011/05/26 15:32:02	2.1
+++ ray/src/util/rttree_reduce.c	2014/03/17 01:59:48	2.9
@@ -1,5 +1,5 @@
 #ifndef lint
-static const char RCSid[] = "$Id: rttree_reduce.c,v 2.1 2011/05/26 15:32:02 greg Exp $";
+static const char RCSid[] = "$Id: rttree_reduce.c,v 2.9 2014/03/17 01:59:48 greg Exp $";
 #endif
 /*
  *  A utility called by genBSDF.pl to reduce tensor tree samples and output
@@ -11,18 +11,17 @@ static const char RCSid[] = "$Id: rttree_reduce.c,v 2.
 #include "rterror.h"
 #include "platform.h"
 #include <stdlib.h>
+#include <math.h>
 
 float	*datarr;		/* our loaded BSDF data array */
 int	ttrank = 4;		/* tensor tree rank */
 int	log2g = 4;		/* log2 of grid resolution */
 int	infmt = 'a';		/* input format ('a','f','d') */
-double	tthresh = .05;		/* relative acceptance threshold */
+double	pctcull = 95.;		/* target culling percentile */
 
 #define dval3(ix,ox,oy)		datarr[((((ix)<<log2g)+(ox))<<log2g)+(oy)]
 #define dval4(ix,iy,ox,oy)	datarr[((((((ix)<<log2g)+(iy))<<log2g)+(ox))<<log2g)+(oy)]
 
-#define above_threshold(tp)	((tp)->vmax - (tp)->vmin > 2.*tthresh*(tp)->vavg)
-
 /* Tensor tree node */
 typedef struct ttree_s {
 	float		vmin, vmax;	/* value extrema */
@@ -30,6 +29,17 @@ typedef struct ttree_s {
 	struct ttree_s	*kid;		/* 2^ttrank children */
 } TNODE;
 
+#define HISTLEN		300	/* histogram resolution */
+#define HISTMAX		10.	/* maximum recorded measure in histogram */
+
+int	histo[HISTLEN];		/* histogram freq. of variance measure */
+
+double	tthresh;		/* acceptance threshold (TBD) */
+
+#define var_measure(tp)		( ((tp)->vmax - (tp)->vmin) / \
+					(sqrt((tp)->vavg) + .03) )
+#define above_threshold(tp)	(var_measure(tp) > tthresh)
+
 /* Allocate a new set of children for the given node (no checks) */
 static void
 new_kids(TNODE *pn)
@@ -77,6 +87,10 @@ build_tree(TNODE *tp, const int bmin[], int l2s)
 			tp->vavg += val;
 		}
 		tp->vavg /= (float)(1<<ttrank);
+					/* record stats */
+		i = (HISTLEN/HISTMAX) * var_measure(tp);
+		if (i >= HISTLEN) i = HISTLEN-1;
+		++histo[i];
 		return;
 	}
 	--l2s;				/* else still branching */
@@ -92,11 +106,38 @@ build_tree(TNODE *tp, const int bmin[], int l2s)
 		tp->vavg += tp->kid[i].vavg;
 	}
 	tp->vavg /= (float)(1<<ttrank);
-					/* is variation above threshold? */
-	if (!above_threshold(tp))
-		free_kids(tp);		/* if not, trim branches */
 }
 
+/* Set our trimming threshold */
+static void
+set_threshold()
+{
+	int	hsum = 0;
+	int	i;
+
+	for (i = HISTLEN; i--; )
+		hsum += histo[i];
+	hsum = pctcull*.01 * (double)hsum;
+	for (i = 0; hsum > 0; i++)
+		hsum -= histo[i];
+	tthresh = (HISTMAX/HISTLEN) * i;
+}
+
+/* Trim our tree according to the current threshold */
+static void
+trim_tree(TNODE *tp)
+{
+	if (tp->kid == NULL)
+		return;
+	if (above_threshold(tp)) {	/* keeping branches? */
+		int	i = 1<<ttrank;
+		while (i--)
+			trim_tree(tp->kid+i);
+		return;
+	}
+	free_kids(tp);			/* else trim at this point */
+}
+
 /* Print a tensor tree from the given hypercube */
 static void
 print_tree(const TNODE *tp, const int bmin[], int l2s)
@@ -111,7 +152,7 @@ print_tree(const TNODE *tp, const int bmin[], int l2s)
 		for (i = 0; i < 1<<ttrank; i++) {
 			float	val;
 			for (j = ttrank; j--; )
-				bkmin[j] = bmin[j] + (i>>j & 1);
+				bkmin[j] = bmin[j] + (i>>(ttrank-1-j) & 1);
 			val = (ttrank == 3) ? dval3(bkmin[0],bkmin[1],bkmin[2])
 				: dval4(bkmin[0],bkmin[1],bkmin[2],bkmin[3]);
 			printf(" %.4e", val);
@@ -219,17 +260,17 @@ load_data()
 		error(SYSTEM, "out of memory in load_data");
 	if (ttrank == 3) {
 		int	ix, ox;
-		for (ix = 0; ix < 1<<log2g; ix++)
+		for (ix = 0; ix < 1<<(log2g-1); ix++)
 			for (ox = 0; ox < 1<<log2g; ox++)
-				(*readf)(datarr+((((ix)<<log2g)+(ox))<<log2g),
-						1<<(log2g-1));
+				(*readf)(datarr+(((ix<<log2g)+ox)<<log2g),
+						1<<log2g);
 	} else /* ttrank == 4 */ {
 		int	ix, iy, ox;
 		for (ix = 0; ix < 1<<log2g; ix++)
 		    for (iy = 0; iy < 1<<log2g; iy++)
 			for (ox = 0; ox < 1<<log2g; ox++)
 				(*readf)(datarr +
-				((((((ix)<<log2g)+(iy))<<log2g)+(ox))<<log2g),
+				(((((ix<<log2g)+iy)<<log2g)+ox)<<log2g),
 						1<<log2g);
 	}
 	(*readf)(NULL, 0);	/* releases any buffers */
@@ -250,17 +291,50 @@ load_data()
 		error(WARNING, "binary data past end of expected input");
 }
 
+/* Enforce reciprocity by averaging data values */
+static void
+do_reciprocity()
+{
+	const int	siz = 1<<log2g;
+	float		*v1p, *v2p;
+
+	if (ttrank == 3) {
+		int	ix, ox, oy;
+		for (ix = 0; ix < siz>>1; ix++)
+		    for (ox = 0; ox < siz; ox++)
+		        for (oy = 0; oy < siz>>1; oy++) {
+				v1p = &dval3(ix,ox,oy);
+				v2p = &dval3(ix,ox,siz-1-oy);
+				*v1p = *v2p = .5f*( *v1p + *v2p );
+			}
+	} else /* ttrank == 4 */ {
+		int	ix, iy, ox, oy;
+		for (ix = 1; ix < siz; ix++)
+		    for (iy = 1; iy < siz; iy++)
+			for (ox = 0; ox < ix; ox++)
+			    for (oy = 0; oy < iy; oy++) {
+				v1p = &dval4(siz-1-ix,siz-1-iy,ox,oy);
+				v2p = &dval4(siz-1-ox,siz-1-oy,ix,iy);
+				*v1p = *v2p = .5f*( *v1p + *v2p );
+			    }
+	}
+}
+
 /* Load BSDF array, coalesce uniform regions and format as tensor tree */
 int
 main(int argc, char *argv[])
 {
 	int	doheader = 1;
+	int	recipavg = 0;
 	int	bmin[4];
 	TNODE	gtree;
 	int	i;
 					/* get options and parameters */
 	for (i = 1; i < argc && argv[i][0] == '-'; i++)
 		switch (argv[i][1]) {
+		case 'a':
+			recipavg = !recipavg;
+			break;
 		case 'h':
 			doheader = !doheader;
 			break;
@@ -275,8 +349,8 @@ main(int argc, char *argv[])
 				goto userr;
 			break;
 		case 't':
-			tthresh = atof(argv[++i]);
-			if (tthresh <= 0)
+			pctcull = atof(argv[++i]);
+			if ((pctcull < 0) | (pctcull >= 100.))
 				goto userr;
 			break;
 		case 'f':
@@ -290,13 +364,18 @@ main(int argc, char *argv[])
 	if (i < argc-1)
 		goto userr;
 					/* load input data */
-	if (i == argc-1 && freopen(argv[i], "rb", stdin) == NULL) {
+	if (i == argc-1 && freopen(argv[i], "r", stdin) == NULL) {
 		sprintf(errmsg, "cannot open input file '%s'", argv[i]);
 		error(SYSTEM, errmsg);
 	}
 	if (infmt != 'a')
 		SET_FILE_BINARY(stdin);
+#ifdef getc_unlocked			/* avoid lock/unlock overhead */
+	flockfile(stdin);
+#endif
 	load_data();
+	if (recipavg)
+		do_reciprocity();
 	if (doheader) {
 		for (i = 0; i < argc; i++) {
 			fputs(argv[i], stdout);
@@ -307,6 +386,9 @@ main(int argc, char *argv[])
 	gtree.kid = NULL;		/* create our tree */
 	bmin[0] = bmin[1] = bmin[2] = bmin[3] = 0;
 	build_tree(&gtree, bmin, log2g);
+					/* compute threshold & trim tree */
+	set_threshold();
+	trim_tree(&gtree);
 					/* format to stdout */
 	print_tree(&gtree, bmin, log2g);
 	/* Clean up isn't necessary for main()...
@@ -315,7 +397,7 @@ main(int argc, char *argv[])
 	*/
 	return(0);
 userr:
-	fprintf(stderr, "Usage: %s [-h][-f{a|f|d}][-r {3|4}][-g log2grid][-t thresh] [input]\n",
+	fprintf(stderr, "Usage: %s [-h][-a][-f{a|f|d}][-r {3|4}][-g log2grid][-t trim%%] [input]\n",
 			argv[0]);
 	return(1);
 }