--- ray/src/hd/rhd_qtree.c 1997/12/24 10:50:49 3.13 +++ ray/src/hd/rhd_qtree.c 2005/01/07 20:33:02 3.26 @@ -1,13 +1,12 @@ -/* Copyright (c) 1997 Silicon Graphics, Inc. */ - #ifndef lint -static char SCCSid[] = "$SunId$ SGI"; +static const char RCSid[] = "$Id: rhd_qtree.c,v 3.26 2005/01/07 20:33:02 greg Exp $"; #endif - /* * Quadtree driver support routines. */ +#include + #include "standard.h" #include "rhd_qtree.h" /* quantity of leaves to free at a time */ @@ -29,16 +28,27 @@ double qtDepthEps = .05; /* epsilon to compare depths int qtMinNodesiz = 2; /* minimum node dimension (pixels) */ struct rleaves qtL; /* our pile of leaves */ +int rayqleft = 0; /* rays left to queue before flush */ + +static int32 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(void); +static void qtFreeTree(int really); +static void shaketree(RTREE *tp); +static int putleaf(int li, int drop); static RTREE * -newtwig() /* allocate a twig */ +newtwig(void) /* allocate a twig */ { register int bi; @@ -50,7 +60,7 @@ newtwig() /* allocate a twig */ } bi = nexttwig / TBUNDLESIZ; if (twigbundle[bi] == NULL) { /* new block */ - twigbundle = (RTREE **)realloc((char *)twigbundle, + twigbundle = (RTREE **)realloc((void *)twigbundle, (bi+2)*sizeof(RTREE *)); if (twigbundle == NULL) goto memerr; @@ -63,11 +73,14 @@ newtwig() /* allocate a twig */ return(twigbundle[bi] + (nexttwig++ - bi*TBUNDLESIZ)); memerr: error(SYSTEM, "out of memory in newtwig"); + return NULL; /* pro forma return */ } -qtFreeTree(really) /* free allocated twigs */ -int really; +static void +qtFreeTree( /* free allocated twigs */ + int really +) { register int i; @@ -78,37 +91,24 @@ int really; nexttwig = 0; if (!really) { /* just clear allocated blocks */ while (i--) - bzero((char *)twigbundle[i], TBUNDLESIZ*sizeof(RTREE)); + memset((char *)twigbundle[i], '\0', TBUNDLESIZ*sizeof(RTREE)); return; } /* else "really" means free up memory */ for (i = 0; twigbundle[i] != NULL; i++) - free((char *)twigbundle[i]); - free((char *)twigbundle); + free((void *)twigbundle[i]); + free((void *)twigbundle); twigbundle = NULL; } -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)+\ +#define LEAFSIZ (3*sizeof(float)+sizeof(int32)+\ sizeof(TMbright)+6*sizeof(BYTE)) -int -qtAllocLeaves(n) /* allocate space for n leaves */ -register int n; +extern int +qtAllocLeaves( /* allocate space for n leaves */ + register int n +) { unsigned nbytes; register unsigned i; @@ -130,19 +130,21 @@ register int n; return(0); /* assign larger alignment types earlier */ qtL.wp = (float (*)[3])qtL.base; - qtL.wd = (int4 *)(qtL.wp + n); + qtL.wd = (int32 *)(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; qtL.tml = qtL.bl = qtL.tl = 0; + falleaves = -1; return(n); } #undef LEAFSIZ -qtFreeLeaves() /* free our allocated leaves and twigs */ +extern void +qtFreeLeaves(void) /* free our allocated leaves and twigs */ { qtFreeTree(1); /* free tree also */ if (qtL.nl <= 0) @@ -153,9 +155,10 @@ qtFreeLeaves() /* free our allocated leaves and twig } -static -shaketree(tp) /* shake dead leaves from tree */ -register RTREE *tp; +static void +shaketree( /* shake dead leaves from tree */ + register RTREE *tp +) { register int i, li; @@ -166,20 +169,19 @@ 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); } } -int -qtCompost(pct) /* free up some leaves */ -int pct; +extern int +qtCompost( /* free up some leaves */ + int pct +) { + register int32 *fl; int nused, nclear, nmapped; - /* figure out how many leaves to clear */ nclear = qtL.nl * pct / 100; nused = qtL.tl - qtL.bl; @@ -190,6 +192,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 */ @@ -198,14 +201,20 @@ 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); } -int -qtFindLeaf(x, y) /* find closest leaf to (x,y) */ -int x, y; +extern int +qtFindLeaf( /* find closest leaf to (x,y) */ + int x, + int y +) { register RTREE *tp = &qtrunk; int li = -1; @@ -240,34 +249,39 @@ int x, y; } -static -addleaf(li) /* add a leaf to our tree */ -int li; +static int +putleaf( /* 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(-1); /* 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; @@ -289,7 +303,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; @@ -299,12 +313,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 */ @@ -318,26 +333,62 @@ int li; tp->flgs = CH_ANY|LFF(q); /* all new */ tp->k[q].li = lo; } - return(1); /* done */ +dropit: + if (drop) { + if (li+1 == (qtL.tl ? qtL.tl : qtL.nl)) + qtL.tl = li; /* special case */ + else { + qtL.chr[li][0] = qtL.chr[li][1] = qtL.chr[li][2] = 0; + qtL.wd[li] = falleaves; + falleaves = li; + } + } + return(li == lo); } -dev_value(c, p, v) /* add a pixel value to our quadtree */ -COLR c; -FVECT p, v; +extern void +dev_value( /* add a pixel value to our quadtree */ + COLR c, + FVECT d, + FVECT p +) { register int li; - - li = newleaf(); - VCOPY(qtL.wp[li], p); - qtL.wd[li] = encodedir(v); - tmCvColrs(&qtL.brt[li], qtL.chr[li], c, 1); - if (!addleaf(li)) - ungetleaf(li); + int mapit; + /* grab a leaf */ + if (!imm_mode && 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) /* 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 */ + } + if (p == NULL) + VSUM(qtL.wp[li], odev.v.vp, d, FHUGE); + else + VCOPY(qtL.wp[li], p); + qtL.wd[li] = encodedir(d); + tmCvColrs(tmGlobal, &qtL.brt[li], qtL.chr[li], (COLR *)c, 1); + if (putleaf(li, 1)) { + if (mapit) + tmMapPixels(tmGlobal, (BYTE *)(qtL.rgb+li), qtL.brt+li, + (BYTE *)(qtL.chr+li), 1); + if (--rayqleft == 0) + dev_flush(); /* flush output */ + } } -qtReplant() /* replant our tree using new view */ +extern void +qtReplant(void) /* replant our tree using new view */ { register int i; /* anything to replant? */ @@ -346,14 +397,16 @@ 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; } } -qtMapLeaves(redo) /* map our leaves to RGB */ -int redo; +extern int +qtMapLeaves( /* map our leaves to RGB */ + int redo +) { int aorg, alen, borg, blen; /* recompute mapping? */ @@ -374,19 +427,19 @@ int redo; } /* (re)compute tone mapping? */ if (qtL.tml == qtL.bl) { - tmClearHisto(); - tmAddHisto(qtL.brt+aorg, alen, 1); + tmClearHisto(tmGlobal); + tmAddHisto(tmGlobal, qtL.brt+aorg, alen, 1); if (blen > 0) - tmAddHisto(qtL.brt+borg, blen, 1); - if (tmComputeMapping(0., 0., 0.) != TM_E_OK) + tmAddHisto(tmGlobal, qtL.brt+borg, blen, 1); + if (tmComputeMapping(tmGlobal, 0., 0., 0.) != TM_E_OK) return(0); } - if (tmMapPixels(qtL.rgb+aorg, qtL.brt+aorg, - qtL.chr+aorg, alen) != TM_E_OK) + if (tmMapPixels(tmGlobal, (BYTE *)(qtL.rgb+aorg), qtL.brt+aorg, + (BYTE *)(qtL.chr+aorg), alen) != TM_E_OK) return(0); if (blen > 0) - tmMapPixels(qtL.rgb+borg, qtL.brt+borg, - qtL.chr+borg, blen); + tmMapPixels(tmGlobal, (BYTE *)(qtL.rgb+borg), qtL.brt+borg, + (BYTE *)(qtL.chr+borg), blen); qtL.tml = qtL.tl; return(1); }