--- ray/src/hd/rhd_qtree.c 1997/12/05 15:40:54 3.11 +++ ray/src/hd/rhd_qtree.c 1997/12/30 17:08:37 3.15 @@ -16,11 +16,12 @@ static char SCCSid[] = "$SunId$ SGI"; #endif /* maximum allowed angle difference (deg.) */ #ifndef MAXANG -#define MAXANG 20. +#define MAXANG 20 #endif +#if MAXANG>0 +#define MAXDIFF2 ( MAXANG*MAXANG * (PI*PI/180./180.)) +#endif -#define MAXDIFF2 (PI*PI/180./180.* MAXANG*MAXANG ) - #define abs(i) ((i) < 0 ? -(i) : (i)) RTREE qtrunk; /* our quadtree trunk */ @@ -28,14 +29,18 @@ double qtDepthEps = .05; /* epsilon to compare depths int qtMinNodesiz = 2; /* minimum node dimension (pixels) */ struct rleaves qtL; /* our pile of leaves */ +static int4 falleaves; /* our list of fallen leaves */ + +#define composted(li) (qtL.bl <= qtL.tl ? \ + ((li) < qtL.bl || (li) >= qtL.tl) : \ + ((li) < qtL.bl && (li) >= qtL.tl)) + #define TBUNDLESIZ 409 /* number of twigs in a bundle */ static RTREE **twigbundle; /* free twig blocks (NULL term.) */ static int nexttwig; /* next free twig */ -#define ungetleaf(li) (qtL.tl=(li)) /* dangerous if used improperly */ - static RTREE * newtwig() /* allocate a twig */ { @@ -88,20 +93,6 @@ 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)) @@ -135,6 +126,7 @@ register int n; qtL.rgb = (BYTE (*)[3])(qtL.chr + n); qtL.nl = n; qtL.tml = qtL.bl = qtL.tl = 0; + falleaves = -1; return(n); } @@ -165,9 +157,7 @@ register RTREE *tp; tp->flgs &= ~BRF(i); } else if (tp->flgs & LFF(i)) { li = tp->k[i].li; - if (qtL.bl < qtL.tl ? - (li < qtL.bl || li >= qtL.tl) : - (li < qtL.bl && li >= qtL.tl)) + if (composted(li)) tp->flgs &= ~LFF(i); } } @@ -177,8 +167,8 @@ int qtCompost(pct) /* free up some leaves */ int pct; { + register int4 *fl; int nused, nclear, nmapped; - /* figure out how many leaves to clear */ nclear = qtL.nl * pct / 100; nused = qtL.tl - qtL.bl; @@ -189,6 +179,7 @@ int pct; if (nclear >= nused) { /* clear them all */ qtFreeTree(0); qtL.tml = qtL.bl = qtL.tl = 0; + falleaves = -1; return(nused); } /* else clear leaves from bottom */ @@ -197,101 +188,15 @@ int pct; qtL.bl += nclear; if (qtL.bl >= qtL.nl) qtL.bl -= qtL.nl; if (nmapped <= nclear) qtL.tml = qtL.bl; - shaketree(&qtrunk); + shaketree(&qtrunk); /* dereference composted leaves */ + for (fl = &falleaves; *fl >= 0; fl = qtL.wd + *fl) + while (composted(*fl)) + if ((*fl = qtL.wd[*fl]) < 0) + return(nclear); return(nclear); } -#define DCSCALE 11585.2 /* (1<<13)*sqrt(2) */ -#define FXNEG 01 -#define FYNEG 02 -#define FZNEG 04 -#define FXACT 010 -#define FZACT 020 -#define F1SFT 5 -#define F2SFT 18 -#define FMASK 0x1fff - -static int4 -encodedir(dv) /* encode a normalized direction vector */ -FVECT dv; -{ - register int4 dc = 0; - int cd[3], cm; - register int i; - - for (i = 0; i < 3; i++) - if (dv[i] < 0.) { - cd[i] = dv[i] * -DCSCALE; - dc |= 1<>F1SFT & FMASK)+.5)/DCSCALE; - d2 = ((dc>>F2SFT & FMASK)+.5)/DCSCALE; - der = sqrt(1. - d1*d1 - d2*d2); - if (dc & FXACT) { - dv[0] = d1; - if (dc & FZACT) { dv[1] = der; dv[2] = d2; } - else { dv[1] = d2; dv[2] = der; } - } else { - dv[1] = d1; - if (dc & FZACT) { dv[0] = der; dv[2] = d2; } - else { dv[0] = d2; dv[2] = der; } - } - if (dc & FXNEG) dv[0] = -dv[0]; - if (dc & FYNEG) dv[1] = -dv[1]; - if (dc & FZNEG) dv[2] = -dv[2]; -} - - -static double -dir2diff(dc1, dc2) /* relative radians^2 between directions */ -int4 dc1, dc2; -{ - FVECT v1, v2; - - decodedir(v1, dc1); - decodedir(v2, dc2); - - return(2. - 2.*DOT(v1,v2)); -} - - -static double -fdir2diff(dc1, v2) /* relative radians^2 between directions */ -int4 dc1; -register FVECT v2; -{ - FVECT v1; - - decodedir(v1, dc1); - - return(2. - 2.*DOT(v1,v2)); -} - - int qtFindLeaf(x, y) /* find closest leaf to (x,y) */ int x, y; @@ -330,32 +235,38 @@ int x, y; static -addleaf(li) /* add a leaf to our tree */ -int li; +putleaf(li, drop) /* put a leaf in our tree */ +register int li; +int drop; { register RTREE *tp = &qtrunk; int x0=0, y0=0, x1=odev.hres, y1=odev.vres; - int lo = -1; + register int lo = -1; double d2; int x, y, mx, my; double z; FVECT ip, wp, vd; register int q; + /* check for dead leaf */ + if (!qtL.chr[li][1] && !(qtL.chr[li][0] | qtL.chr[li][2])) + return(0); /* 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(0); /* behind or outside view */ + goto dropit; /* behind or outside view */ #ifdef DEBUG if (odev.v.type == VT_PAR | odev.v.vfore > FTINY) - error(INTERNAL, "bad view assumption in addleaf"); + error(INTERNAL, "bad view assumption in putleaf"); #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 */ + goto dropit; /* leaf dir. too far off */ +#endif x = ip[0] * odev.hres; y = ip[1] * odev.vres; z = ip[2]; @@ -376,7 +287,7 @@ int li; if (!(tp->flgs & LFF(q))) { /* found stem for leaf */ tp->k[q].li = li; tp->flgs |= CHLFF(q); - break; + return(1); } if (lo != tp->k[q].li) { /* check old leaf */ lo = tp->k[q].li; @@ -386,12 +297,13 @@ int li; /* is node minimum size? */ if (y1-y0 <= qtMinNodesiz || x1-x0 <= qtMinNodesiz) { if (z > (1.+qtDepthEps)*ip[2]) - return(0); /* old one closer */ + break; /* 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 */ + break; /* old one better */ + tp->k[q].li = li; /* attach new */ tp->flgs |= CHF(q); + li = lo; /* drop old... */ break; } tp->flgs &= ~LFF(q); /* else grow tree */ @@ -405,7 +317,13 @@ int li; tp->flgs = CH_ANY|LFF(q); /* all new */ tp->k[q].li = lo; } - return(1); /* done */ +dropit: + if (drop) { + qtL.chr[li][0] = qtL.chr[li][1] = qtL.chr[li][2] = 0; + qtL.wd[li] = falleaves; + falleaves = li; + } + return(li == lo); } @@ -414,13 +332,27 @@ COLR c; FVECT p, v; { register int li; - - li = newleaf(); + int mapit; + /* grab a leaf */ + if (falleaves >= 0) { /* check for fallen leaves */ + li = falleaves; + falleaves = qtL.wd[li]; + mapit = qtL.tml <= qtL.tl ? + (li < qtL.tml || li >= qtL.tl) : + (li < qtL.tml && li >= qtL.tl) ; + } else { /* else allocate new one */ + 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); + mapit = 0; /* we'll map it later */ + } VCOPY(qtL.wp[li], p); qtL.wd[li] = encodedir(v); tmCvColrs(&qtL.brt[li], qtL.chr[li], c, 1); - if (!addleaf(li)) - ungetleaf(li); + if (putleaf(li, 1) && mapit) + tmMapPixels(qtL.rgb+li, qtL.brt+li, qtL.chr+li, 1); } @@ -433,7 +365,7 @@ qtReplant() /* replant our tree using new view */ qtFreeTree(0); /* blow the old tree away */ /* regrow it in new place */ for (i = qtL.bl; i != qtL.tl; ) { - addleaf(i); + putleaf(i, 0); if (++i >= qtL.nl) i = 0; } }