--- ray/src/hd/rhd_qtree.c	1997/11/25 16:52:04	3.9
+++ ray/src/hd/rhd_qtree.c	1997/12/29 17:31:45	3.14
@@ -14,9 +14,18 @@ static char SCCSid[] = "$SunId$ SGI";
 #ifndef LFREEPCT
 #define	LFREEPCT	25
 #endif
+				/* maximum allowed angle difference (deg.) */
+#ifndef MAXANG
+#define MAXANG		20
+#endif
+#if MAXANG>0
+#define MAXDIFF2	( MAXANG*MAXANG * (PI*PI/180./180.))
+#endif
 
+#define abs(i)		((i) < 0 ? -(i) : (i))
+
 RTREE	qtrunk;			/* our quadtree trunk */
-double	qtDepthEps = .02;	/* epsilon to compare depths (z fraction) */
+double	qtDepthEps = .05;	/* epsilon to compare depths (z fraction) */
 int	qtMinNodesiz = 2;	/* minimum node dimension (pixels) */
 struct rleaves	qtL;		/* our pile of leaves */
 
@@ -78,22 +87,9 @@ int	really;
 }
 
 
-static int
-newleaf()			/* allocate a leaf from our pile */
-{
-	int	li;
-	
-	li = qtL.tl++;
-	if (qtL.tl >= qtL.nl)	/* get next leaf in ring */
-		qtL.tl = 0;
-	if (qtL.tl == qtL.bl)	/* need to shake some free */
-		qtCompost(LFREEPCT);
-	return(li);
-}
+#define	LEAFSIZ		(3*sizeof(float)+sizeof(int4)+\
+			sizeof(TMbright)+6*sizeof(BYTE))
 
-
-#define	LEAFSIZ		(3*sizeof(float)+sizeof(TMbright)+6*sizeof(BYTE))
-
 int
 qtAllocLeaves(n)		/* allocate space for n leaves */
 register int	n;
@@ -118,7 +114,8 @@ register int	n;
 		return(0);
 				/* assign larger alignment types earlier */
 	qtL.wp = (float (*)[3])qtL.base;
-	qtL.brt = (TMbright *)(qtL.wp + n);
+	qtL.wd = (int4 *)(qtL.wp + n);
+	qtL.brt = (TMbright *)(qtL.wd + n);
 	qtL.chr = (BYTE (*)[3])(qtL.brt + n);
 	qtL.rgb = (BYTE (*)[3])(qtL.chr + n);
 	qtL.nl = n;
@@ -234,16 +231,28 @@ int	li;
 	register RTREE	*tp = &qtrunk;
 	int	x0=0, y0=0, x1=odev.hres, y1=odev.vres;
 	int	lo = -1;
+	double	d2;
 	int	x, y, mx, my;
 	double	z;
-	FVECT	ip, wp;
+	FVECT	ip, wp, vd;
 	register int	q;
-					/* compute leaf location */
+					/* compute leaf location in view */
 	VCOPY(wp, qtL.wp[li]);
 	viewloc(ip, &odev.v, wp);
 	if (ip[2] <= 0. || ip[0] < 0. || ip[0] >= 1.
 			|| ip[1] < 0. || ip[1] >= 1.)
-		return;
+		return(-1);			/* behind or outside view */
+#ifdef DEBUG
+	if (odev.v.type == VT_PAR | odev.v.vfore > FTINY)
+		error(INTERNAL, "bad view assumption in addleaf");
+#endif
+	for (q = 0; q < 3; q++)
+		vd[q] = (wp[q] - odev.v.vp[q])/ip[2];
+	d2 = fdir2diff(qtL.wd[li], vd);
+#ifdef MAXDIFF2
+	if (d2 > MAXDIFF2)
+		return(0);			/* leaf dir. too far off */
+#endif
 	x = ip[0] * odev.hres;
 	y = ip[1] * odev.vres;
 	z = ip[2];
@@ -266,17 +275,19 @@ int	li;
 			tp->flgs |= CHLFF(q);
 			break;
 		}	
-						/* check existing leaf */
-		if (lo != tp->k[q].li) {
+		if (lo != tp->k[q].li) {	/* check old leaf */
 			lo = tp->k[q].li;
 			VCOPY(wp, qtL.wp[lo]);
 			viewloc(ip, &odev.v, wp);
 		}
 						/* is node minimum size? */
-		if (x1-x0 <= qtMinNodesiz || y1-y0 <= qtMinNodesiz) {
-			if (z > (1.-qtDepthEps)*ip[2])	/* who is closer? */
-				return;			/* old one is */
-			tp->k[q].li = li;		/* new one is */
+		if (y1-y0 <= qtMinNodesiz || x1-x0 <= qtMinNodesiz) {
+			if (z > (1.+qtDepthEps)*ip[2])
+				return(0);		/* old one closer */
+			if (z >= (1.-qtDepthEps)*ip[2] &&
+					fdir2diff(qtL.wd[lo], vd) < d2)
+				return(0);		/* old one better */
+			tp->k[q].li = li;		/* else new one is */
 			tp->flgs |= CHF(q);
 			break;
 		}
@@ -288,22 +299,29 @@ int	li;
 		my = ip[1] * odev.vres;
 		if (mx >= (x0 + x1) >> 1) q |= 01;
 		if (my >= (y0 + y1) >> 1) q |= 02;
+		tp->flgs = CH_ANY|LFF(q);	/* all new */
 		tp->k[q].li = lo;
-		tp->flgs |= LFF(q)|CH_ANY;	/* all new */
 	}
+	return(1);		/* done */
 }
 
 
-dev_value(c, p)			/* add a pixel value to our quadtree */
+dev_value(c, p, v)		/* add a pixel value to our quadtree */
 COLR	c;
-FVECT	p;
+FVECT	p, v;
 {
 	register int	li;
 
-	li = newleaf();
+	li = qtL.tl++;
+	if (qtL.tl >= qtL.nl)	/* advance to next leaf in ring */
+		qtL.tl = 0;
+	if (qtL.tl == qtL.bl)	/* need to shake some free */
+		qtCompost(LFREEPCT);
 	VCOPY(qtL.wp[li], p);
+	qtL.wd[li] = encodedir(v);
 	tmCvColrs(&qtL.brt[li], qtL.chr[li], c, 1);
-	addleaf(li);
+	if (!addleaf(li))
+		qtL.tl = li;	/* unget this leaf */
 }