--- ray/src/hd/rhd_qtree.c	1997/11/21 13:35:57	3.5
+++ ray/src/hd/rhd_qtree.c	1997/11/25 16:52:04	3.9
@@ -10,6 +10,10 @@ static char SCCSid[] = "$SunId$ SGI";
 
 #include "standard.h"
 #include "rhd_qtree.h"
+				/* quantity of leaves to free at a time */
+#ifndef LFREEPCT
+#define	LFREEPCT	25
+#endif
 
 RTREE	qtrunk;			/* our quadtree trunk */
 double	qtDepthEps = .02;	/* epsilon to compare depths (z fraction) */
@@ -21,9 +25,7 @@ struct rleaves	qtL;		/* our pile of leaves */
 static RTREE	**twigbundle;	/* free twig blocks (NULL term.) */
 static int	nexttwig;	/* next free twig */
 
-#define	is_stump(t)	(!((t)->flgs & (BR_ANY|LF_ANY)))
 
-
 static RTREE *
 newtwig()			/* allocate a twig */
 {
@@ -58,12 +60,13 @@ int	really;
 {
 	register int	i;
 
-	qtrunk.flgs = 0;
-	nexttwig = 0;
+	qtrunk.flgs = CH_ANY;	/* chop down tree */
 	if (twigbundle == NULL)
 		return;
+	i = (TBUNDLESIZ-1+nexttwig)/TBUNDLESIZ;
+	nexttwig = 0;
 	if (!really) {		/* just clear allocated blocks */
-		for (i = 0; twigbundle[i] != NULL; i++)
+		while (i--)
 			bzero((char *)twigbundle[i], TBUNDLESIZ*sizeof(RTREE));
 		return;
 	}
@@ -291,7 +294,7 @@ int	li;
 }
 
 
-dev_value(c, p)			/* add a pixel value to our output queue */
+dev_value(c, p)			/* add a pixel value to our quadtree */
 COLR	c;
 FVECT	p;
 {
@@ -323,11 +326,12 @@ qtMapLeaves(redo)		/* map our leaves to RGB */
 int	redo;
 {
 	int	aorg, alen, borg, blen;
+					/* recompute mapping? */
+	if (redo)
+		qtL.tml = qtL.bl;
 					/* already done? */
 	if (qtL.tml == qtL.tl)
 		return(1);
-	if (redo)
-		qtL.tml = qtL.bl;
 					/* compute segments */
 	aorg = qtL.tml;
 	if (qtL.tl >= aorg) {
@@ -355,142 +359,4 @@ int	redo;
 				qtL.chr+borg, blen);
 	qtL.tml = qtL.tl;
 	return(1);
-}
-
-
-static
-redraw(ca, tp, x0, y0, x1, y1, l)	/* redraw portion of a tree */
-BYTE	ca[3];		/* returned average color */
-register RTREE	*tp;
-int	x0, y0, x1, y1;
-int	l[2][2];
-{
-	int	csm[3], nc;
-	register BYTE	*cp;
-	BYTE	rgb[3];
-	int	quads = CH_ANY;
-	int	mx, my;
-	register int	i;
-					/* compute midpoint */
-	mx = (x0 + x1) >> 1;
-	my = (y0 + y1) >> 1;
-					/* see what to do */
-	if (l[0][0] >= mx)
-		quads &= ~(CHF(2)|CHF(0));
-	else if (l[0][1] <= mx)
-		quads &= ~(CHF(3)|CHF(1));
-	if (l[1][0] >= my)
-		quads &= ~(CHF(1)|CHF(0));
-	else if (l[1][1] <= my)
-		quads &= ~(CHF(3)|CHF(2));
-	tp->flgs &= ~quads;		/* mark them done */
-	csm[0] = csm[1] = csm[2] = nc = 0;
-					/* do leaves first */
-	for (i = 0; i < 4; i++)
-		if (quads & CHF(i) && tp->flgs & LFF(i)) {
-			dev_paintr(cp=qtL.rgb[tp->k[i].li],
-					i&01 ? mx : x0, i&02 ? my : y0,
-					i&01 ? x1 : mx, i&02 ? y1 : my);
-			csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
-			nc++;
-			quads &= ~CHF(i);
-		}
-					/* now do branches */
-	for (i = 0; i < 4; i++)
-		if (quads & CHF(i) && tp->flgs & BRF(i)) {
-			redraw(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
-					i&01 ? x1 : mx, i&02 ? y1 : my, l);
-			csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
-			nc++;
-			quads &= ~CHF(i);
-		}
-	if (nc > 1) {
-		ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
-	} else {
-		ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
-	}
-	if (!quads) return;
-					/* fill in gaps with average */
-	for (i = 0; i < 4; i++)
-		if (quads & CHF(i))
-			dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
-					i&01 ? x1 : mx, i&02 ? y1 : my);
-}
-
-
-static
-update(ca, tp, x0, y0, x1, y1)	/* update tree display as needed */
-BYTE	ca[3];		/* returned average color */
-register RTREE	*tp;
-int	x0, y0, x1, y1;
-{
-	int	csm[3], nc;
-	register BYTE	*cp;
-	BYTE	rgb[3];
-	int	gaps = 0;
-	int	mx, my;
-	register int	i;
-					/* compute midpoint */
-	mx = (x0 + x1) >> 1;
-	my = (y0 + y1) >> 1;
-	csm[0] = csm[1] = csm[2] = nc = 0;
-					/* do leaves first */
-	for (i = 0; i < 4; i++) {
-		if (!(tp->flgs & CHF(i)))
-			continue;
-		if (tp->flgs & LFF(i)) {
-			dev_paintr(cp=qtL.rgb[tp->k[i].li],
-					i&01 ? mx : x0, i&02 ? my : y0,
-					i&01 ? x1 : mx, i&02 ? y1 : my);
-			csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
-			nc++;
-		} else if (!(tp->flgs & BRF(i)))
-			gaps |= 1<<i;	/* empty stem */
-	}
-					/* now do branches */
-	for (i = 0; i < 4; i++)
-		if ((tp->flgs & CHBRF(i)) == CHBRF(i)) {
-			update(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
-					i&01 ? x1 : mx, i&02 ? y1 : my);
-			csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
-			nc++;
-		}
-	if (nc > 1) {
-		ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
-	} else {
-		ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
-	}
-					/* fill in gaps with average */
-	for (i = 0; gaps && i < 4; gaps >>= 1, i++)
-		if (gaps & 01)
-			dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
-					i&01 ? x1 : mx, i&02 ? y1 : my);
-	tp->flgs &= ~CH_ANY;		/* all done */
-}
-
-
-qtRedraw(x0, y0, x1, y1)	/* redraw part or all of our screen */
-int	x0, y0, x1, y1;
-{
-	int	lim[2][2];
-	BYTE	ca[3];
-
-	if (is_stump(&qtrunk))
-		return;
-	if (!qtMapLeaves((lim[0][0]=x0) <= 0 & (lim[1][0]=y0) <= 0 &
-		(lim[0][1]=x1) >= odev.hres-1 & (lim[1][1]=y1) >= odev.vres-1))
-		return;
-	redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim);
-}
-
-
-qtUpdate()			/* update our tree display */
-{
-	BYTE	ca[3];
-
-	if (is_stump(&qtrunk))
-		return;
-	if (!qtMapLeaves(0))
-		return;
-	update(ca, &qtrunk, 0, 0, odev.hres, odev.vres);
 }