--- ray/src/hd/rhd_qtree.c	1997/11/19 18:01:03	3.1
+++ ray/src/hd/rhd_qtree.c	1997/11/21 09:52:06	3.4
@@ -11,14 +11,14 @@ static char SCCSid[] = "$SunId$ SGI";
 #include "standard.h"
 #include "rhd_qtree.h"
 
-static RLEAF	*leafpile;	/* our collection of leaf values */
-static int	nleaves;	/* count of leaves in our pile */
-static int	bleaf, tleaf;	/* bottom and top (next) leaf index (ring) */
-
 RTREE	qtrunk;			/* our quadtree trunk */
 double	qtDepthEps = .02;	/* epsilon to compare depths (z fraction) */
 int	qtMinNodesiz = 2;	/* minimum node dimension (pixels) */
 
+static RLEAF	*leafpile;	/* our collection of leaf values */
+static int	nleaves;	/* count of leaves in our pile */
+static int	bleaf, tleaf;	/* bottom and top (next) leaf index (ring) */
+
 #define	TBUNDLESIZ	409	/* number of twigs in a bundle */
 
 static RTREE	**twigbundle;	/* free twig blocks (NULL term.) */
@@ -58,14 +58,12 @@ memerr:
 }
 
 
-static
-freetwigs(really)		/* free allocated twigs */
+qtFreeTree(really)		/* free allocated twigs */
 int	really;
 {
 	register int	i;
 
-	if (tmTop != NULL)
-		tmClearHisto();
+	tmClearHisto();
 	bzero((char *)&qtrunk, sizeof(RTREE));
 	nexttwig = 0;
 	if (twigbundle == NULL)
@@ -86,11 +84,14 @@ int	really;
 static RLEAF *
 newleaf()			/* allocate a leaf from our pile */
 {
-	if (tleaf++ >= nleaves)		/* get next leaf in ring */
+	RLEAF	*lp;
+	
+	lp = leafpile + tleaf++;
+	if (tleaf >= nleaves)		/* get next leaf in ring */
 		tleaf = 0;
 	if (tleaf == bleaf)		/* need to shake some free */
 		qtCompost(LFREEPCT);
-	return(leafpile + tleaf);
+	return(lp);
 }
 
 
@@ -101,7 +102,7 @@ int	n;
 	unsigned	nbytes;
 	register unsigned	i;
 
-	freetwigs(0);		/* make sure tree is empty */
+	qtFreeTree(0);		/* make sure tree is empty */
 	if (n <= 0)
 		return(0);
 	if (nleaves >= n)
@@ -124,7 +125,7 @@ int	n;
 
 qtFreeLeaves()			/* free our allocated leaves and twigs */
 {
-	freetwigs(1);		/* free tree also */
+	qtFreeTree(1);		/* free tree also */
 	if (nleaves <= 0)
 		return;
 	free((char *)leafpile);
@@ -140,19 +141,16 @@ register RTREE	*tp;
 	register int	i, li;
 
 	for (i = 0; i < 4; i++)
-		if (tp->flgs & BRF(i)) {
-			if (shaketree(tp->k[i].b))
-				tp->flgs |= CHF(i);
-		} else if (tp->k[i].l != NULL) {
+		if (tp->flgs & BRF(i))
+			shaketree(tp->k[i].b);
+		else if (tp->k[i].l != NULL) {
 			li = tp->k[i].l - leafpile;
 			if (bleaf < tleaf ? (li < bleaf || li >= tleaf) :
 					(li < bleaf && li >= tleaf)) {
 				tmAddHisto(&tp->k[i].l->brt, 1, -1);
 				tp->k[i].l = NULL;
-				tp->flgs |= CHF(i);
 			}
 		}
-	return(tp->flgs & CH_ANY);
 }
 
 
@@ -161,23 +159,65 @@ qtCompost(pct)			/* free up some leaves */
 int	pct;
 {
 	int	nused, nclear;
+
+	if (is_stump(&qtrunk))
+		return(0);
 				/* figure out how many leaves to clear */
 	nclear = nleaves * pct / 100;
+	nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf;
+	nclear -= nleaves - nused;	/* less what's already free */
 	if (nclear <= 0)
 		return(0);
-	nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf;
 	if (nclear >= nused) {	/* clear them all */
-		freetwigs(0);
+		qtFreeTree(0);
 		bleaf = tleaf = 0;
 		return(nused);
 	}
 				/* else clear leaves from bottom */
-	bleaf = (bleaf + nclear) % nleaves;
+	bleaf += nclear;
+	if (bleaf >= nleaves) bleaf -= nleaves;
 	shaketree(&qtrunk);
 	return(nclear);
 }
 
 
+RLEAF *
+qtFindLeaf(x, y)		/* find closest leaf to (x,y) */
+int	x, y;
+{
+	register RTREE	*tp = &qtrunk;
+	RLEAF	*lp = NULL;
+	int	x0=0, y0=0, x1=odev.hres, y1=odev.vres;
+	int	mx, my;
+	register int	q;
+					/* check limits */
+	if (x < 0 || x >= odev.hres || y < 0 || y >= odev.vres)
+		return(NULL);
+					/* find nearby leaf in our tree */
+	for ( ; ; ) {
+		for (q = 0; q < 4; q++)		/* find any leaf this level */
+			if (!(tp->flgs & BRF(q)) && tp->k[q].l != NULL) {
+				lp = tp->k[q].l;
+				break;
+			}
+		q = 0;				/* which quadrant are we? */
+		mx = (x0 + x1) >> 1;
+		my = (y0 + y1) >> 1;
+		if (x < mx) x1 = mx;
+		else {x0 = mx; q |= 01;}
+		if (y < my) y1 = my;
+		else {y0 = my; q |= 02;}
+		if (tp->flgs & BRF(q)) {	/* branch down if not a leaf */
+			tp = tp->k[q].b;
+			continue;
+		}
+		if (tp->k[q].l != NULL)		/* good shot! */
+			return(tp->k[q].l);
+		return(lp);			/* else return what we have */
+	}
+}
+
+
 static
 addleaf(lp)			/* add a leaf to our tree */
 RLEAF	*lp;
@@ -265,7 +305,7 @@ qtReplant()			/* replant our tree using new view */
 
 	if (bleaf == tleaf)		/* anything to replant? */
 		return;
-	freetwigs(0);			/* blow the tree away */
+	qtFreeTree(0);			/* blow the tree away */
 					/* now rebuild it */
 	for (i = bleaf; i != tleaf; ) {
 		addleaf(leafpile+i);
@@ -394,10 +434,11 @@ int	x0, y0, x1, y1;
 
 	if (is_stump(&qtrunk))
 		return;
-	if ((lim[0][0]=x0) == 0 & (lim[1][0]=y0) == 0 &
-		(lim[0][1]=x1) == odev.hres & (lim[1][1]=y1) == odev.vres ||
-			tmTop->lumap == NULL)
-		tmComputeMapping(0., 0., 0.);
+	if ((lim[0][0]=x0) <= 0 & (lim[1][0]=y0) <= 0 &
+		(lim[0][1]=x1) >= odev.hres-1 & (lim[1][1]=y1) >= odev.vres-1
+			|| tmTop->lumap == NULL)
+		if (tmComputeMapping(0., 0., 0.) != TM_E_OK)
+			return;
 	redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim);
 }