--- ray/src/hd/rhd_qtree.c	1997/11/19 18:01:03	3.1
+++ ray/src/hd/rhd_qtree.c	1997/11/20 18:03:43	3.3
@@ -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,8 +58,7 @@ memerr:
 }
 
 
-static
-freetwigs(really)		/* free allocated twigs */
+qtFreeTree(really)		/* free allocated twigs */
 int	really;
 {
 	register int	i;
@@ -101,7 +100,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 +123,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 +139,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);
 }
 
 
@@ -167,7 +163,7 @@ int	pct;
 		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);
 	}
@@ -178,6 +174,43 @@ int	pct;
 }
 
 
+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 +298,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);