| 10 | 
  | 
 | 
| 11 | 
  | 
#include "standard.h" | 
| 12 | 
  | 
#include "rhd_qtree.h" | 
| 13 | 
+ | 
                                /* quantity of leaves to free at a time */ | 
| 14 | 
+ | 
#ifndef LFREEPCT | 
| 15 | 
+ | 
#define LFREEPCT        25 | 
| 16 | 
+ | 
#endif | 
| 17 | 
+ | 
                                /* maximum allowed angle difference (deg.) */ | 
| 18 | 
+ | 
#ifndef MAXANG | 
| 19 | 
+ | 
#define MAXANG          20 | 
| 20 | 
+ | 
#endif | 
| 21 | 
+ | 
#if MAXANG>0 | 
| 22 | 
+ | 
#define MAXDIFF2        ( MAXANG*MAXANG * (PI*PI/180./180.)) | 
| 23 | 
+ | 
#endif | 
| 24 | 
  | 
 | 
| 25 | 
+ | 
#define abs(i)          ((i) < 0 ? -(i) : (i)) | 
| 26 | 
+ | 
 | 
| 27 | 
  | 
RTREE   qtrunk;                 /* our quadtree trunk */ | 
| 28 | 
< | 
double  qtDepthEps = .02;       /* epsilon to compare depths (z fraction) */ | 
| 28 | 
> | 
double  qtDepthEps = .05;       /* epsilon to compare depths (z fraction) */ | 
| 29 | 
  | 
int     qtMinNodesiz = 2;       /* minimum node dimension (pixels) */ | 
| 30 | 
+ | 
struct rleaves  qtL;            /* our pile of leaves */ | 
| 31 | 
  | 
 | 
| 18 | 
– | 
static RLEAF    *leafpile;      /* our collection of leaf values */ | 
| 19 | 
– | 
static int      nleaves;        /* count of leaves in our pile */ | 
| 20 | 
– | 
static int      bleaf, tleaf;   /* bottom and top (next) leaf index (ring) */ | 
| 21 | 
– | 
 | 
| 32 | 
  | 
#define TBUNDLESIZ      409     /* number of twigs in a bundle */ | 
| 33 | 
  | 
 | 
| 34 | 
  | 
static RTREE    **twigbundle;   /* free twig blocks (NULL term.) */ | 
| 35 | 
  | 
static int      nexttwig;       /* next free twig */ | 
| 36 | 
  | 
 | 
| 37 | 
< | 
static RTREE    emptytree;      /* empty tree for test below */ | 
| 37 | 
> | 
#define ungetleaf(li)   (qtL.tl=(li))   /* dangerous if used improperly */ | 
| 38 | 
  | 
 | 
| 29 | 
– | 
#define is_stump(t)     (!bcmp((char *)(t), (char *)&emptytree, sizeof(RTREE))) | 
| 39 | 
  | 
 | 
| 31 | 
– | 
 | 
| 40 | 
  | 
static RTREE * | 
| 41 | 
  | 
newtwig()                       /* allocate a twig */ | 
| 42 | 
  | 
{ | 
| 66 | 
  | 
} | 
| 67 | 
  | 
 | 
| 68 | 
  | 
 | 
| 69 | 
< | 
static | 
| 62 | 
< | 
freetree(really)                /* free allocated twigs */ | 
| 69 | 
> | 
qtFreeTree(really)              /* free allocated twigs */ | 
| 70 | 
  | 
int     really; | 
| 71 | 
  | 
{ | 
| 72 | 
  | 
        register int    i; | 
| 73 | 
  | 
 | 
| 74 | 
< | 
        if (tmTop != NULL) | 
| 68 | 
< | 
                tmClearHisto(); | 
| 69 | 
< | 
        bzero((char *)&qtrunk, sizeof(RTREE)); | 
| 70 | 
< | 
        nexttwig = 0; | 
| 74 | 
> | 
        qtrunk.flgs = CH_ANY;   /* chop down tree */ | 
| 75 | 
  | 
        if (twigbundle == NULL) | 
| 76 | 
  | 
                return; | 
| 77 | 
+ | 
        i = (TBUNDLESIZ-1+nexttwig)/TBUNDLESIZ; | 
| 78 | 
+ | 
        nexttwig = 0; | 
| 79 | 
  | 
        if (!really) {          /* just clear allocated blocks */ | 
| 80 | 
< | 
                for (i = 0; twigbundle[i] != NULL; i++) | 
| 80 | 
> | 
                while (i--) | 
| 81 | 
  | 
                        bzero((char *)twigbundle[i], TBUNDLESIZ*sizeof(RTREE)); | 
| 82 | 
  | 
                return; | 
| 83 | 
  | 
        } | 
| 89 | 
  | 
} | 
| 90 | 
  | 
 | 
| 91 | 
  | 
 | 
| 92 | 
< | 
static RLEAF * | 
| 92 | 
> | 
static int | 
| 93 | 
  | 
newleaf()                       /* allocate a leaf from our pile */ | 
| 94 | 
  | 
{ | 
| 95 | 
< | 
        if (tleaf++ >= nleaves)         /* get next leaf in ring */ | 
| 96 | 
< | 
                tleaf = 0; | 
| 97 | 
< | 
        if (tleaf == bleaf)             /* need to shake some free */ | 
| 95 | 
> | 
        int     li; | 
| 96 | 
> | 
         | 
| 97 | 
> | 
        li = qtL.tl++; | 
| 98 | 
> | 
        if (qtL.tl >= qtL.nl)   /* get next leaf in ring */ | 
| 99 | 
> | 
                qtL.tl = 0; | 
| 100 | 
> | 
        if (qtL.tl == qtL.bl)   /* need to shake some free */ | 
| 101 | 
  | 
                qtCompost(LFREEPCT); | 
| 102 | 
< | 
        return(leafpile + tleaf); | 
| 102 | 
> | 
        return(li); | 
| 103 | 
  | 
} | 
| 104 | 
  | 
 | 
| 105 | 
  | 
 | 
| 106 | 
+ | 
#define LEAFSIZ         (3*sizeof(float)+sizeof(int4)+\ | 
| 107 | 
+ | 
                        sizeof(TMbright)+6*sizeof(BYTE)) | 
| 108 | 
+ | 
 | 
| 109 | 
  | 
int | 
| 110 | 
  | 
qtAllocLeaves(n)                /* allocate space for n leaves */ | 
| 111 | 
< | 
int     n; | 
| 111 | 
> | 
register int    n; | 
| 112 | 
  | 
{ | 
| 113 | 
  | 
        unsigned        nbytes; | 
| 114 | 
  | 
        register unsigned       i; | 
| 115 | 
  | 
 | 
| 116 | 
< | 
        freetree(0);            /* make sure tree is empty */ | 
| 116 | 
> | 
        qtFreeTree(0);          /* make sure tree is empty */ | 
| 117 | 
  | 
        if (n <= 0) | 
| 118 | 
  | 
                return(0); | 
| 119 | 
< | 
        if (nleaves >= n) | 
| 120 | 
< | 
                return(nleaves); | 
| 121 | 
< | 
        else if (nleaves > 0) | 
| 122 | 
< | 
                free((char *)leafpile); | 
| 119 | 
> | 
        if (qtL.nl >= n) | 
| 120 | 
> | 
                return(qtL.nl); | 
| 121 | 
> | 
        else if (qtL.nl > 0) | 
| 122 | 
> | 
                free(qtL.base); | 
| 123 | 
  | 
                                /* round space up to nearest power of 2 */ | 
| 124 | 
< | 
        nbytes = n*sizeof(RLEAF) + 8; | 
| 124 | 
> | 
        nbytes = n*LEAFSIZ + 8; | 
| 125 | 
  | 
        for (i = 1024; nbytes > i; i <<= 1) | 
| 126 | 
  | 
                ; | 
| 127 | 
< | 
        n = (i - 8) / sizeof(RLEAF); | 
| 128 | 
< | 
        leafpile = (RLEAF *)malloc(n*sizeof(RLEAF)); | 
| 129 | 
< | 
        if (leafpile == NULL) | 
| 130 | 
< | 
                return(-1); | 
| 131 | 
< | 
        nleaves = n; | 
| 132 | 
< | 
        bleaf = tleaf = 0; | 
| 133 | 
< | 
        return(nleaves); | 
| 127 | 
> | 
        n = (i - 8) / LEAFSIZ;  /* should we make sure n is even? */ | 
| 128 | 
> | 
        qtL.base = (char *)malloc(n*LEAFSIZ); | 
| 129 | 
> | 
        if (qtL.base == NULL) | 
| 130 | 
> | 
                return(0); | 
| 131 | 
> | 
                                /* assign larger alignment types earlier */ | 
| 132 | 
> | 
        qtL.wp = (float (*)[3])qtL.base; | 
| 133 | 
> | 
        qtL.wd = (int4 *)(qtL.wp + n); | 
| 134 | 
> | 
        qtL.brt = (TMbright *)(qtL.wd + n); | 
| 135 | 
> | 
        qtL.chr = (BYTE (*)[3])(qtL.brt + n); | 
| 136 | 
> | 
        qtL.rgb = (BYTE (*)[3])(qtL.chr + n); | 
| 137 | 
> | 
        qtL.nl = n; | 
| 138 | 
> | 
        qtL.tml = qtL.bl = qtL.tl = 0; | 
| 139 | 
> | 
        return(n); | 
| 140 | 
  | 
} | 
| 141 | 
  | 
 | 
| 142 | 
+ | 
#undef  LEAFSIZ | 
| 143 | 
  | 
 | 
| 144 | 
+ | 
 | 
| 145 | 
  | 
qtFreeLeaves()                  /* free our allocated leaves and twigs */ | 
| 146 | 
  | 
{ | 
| 147 | 
< | 
        freetree(1);            /* free tree also */ | 
| 148 | 
< | 
        if (nleaves <= 0) | 
| 147 | 
> | 
        qtFreeTree(1);          /* free tree also */ | 
| 148 | 
> | 
        if (qtL.nl <= 0) | 
| 149 | 
  | 
                return; | 
| 150 | 
< | 
        free((char *)leafpile); | 
| 151 | 
< | 
        leafpile = NULL; | 
| 152 | 
< | 
        nleaves = 0; | 
| 150 | 
> | 
        free(qtL.base); | 
| 151 | 
> | 
        qtL.base = NULL; | 
| 152 | 
> | 
        qtL.nl = 0; | 
| 153 | 
  | 
} | 
| 154 | 
  | 
 | 
| 155 | 
  | 
 | 
| 160 | 
  | 
        register int    i, li; | 
| 161 | 
  | 
 | 
| 162 | 
  | 
        for (i = 0; i < 4; i++) | 
| 163 | 
< | 
                if (tp->flgs & BRF(i)) | 
| 163 | 
> | 
                if (tp->flgs & BRF(i)) { | 
| 164 | 
  | 
                        shaketree(tp->k[i].b); | 
| 165 | 
< | 
                else if (tp->k[i].l != NULL) { | 
| 166 | 
< | 
                        li = tp->k[i].l - leafpile; | 
| 167 | 
< | 
                        if (bleaf < tleaf ? (li < bleaf || li >= tleaf) : | 
| 168 | 
< | 
                                        (li < bleaf && li >= tleaf)) { | 
| 169 | 
< | 
                                tmAddHisto(&tp->k[i].l->brt, 1, -1); | 
| 170 | 
< | 
                                tp->k[i].l = NULL; | 
| 171 | 
< | 
                        } | 
| 165 | 
> | 
                        if (is_stump(tp->k[i].b)) | 
| 166 | 
> | 
                                tp->flgs &= ~BRF(i); | 
| 167 | 
> | 
                } else if (tp->flgs & LFF(i)) { | 
| 168 | 
> | 
                        li = tp->k[i].li; | 
| 169 | 
> | 
                        if (qtL.bl < qtL.tl ? | 
| 170 | 
> | 
                                (li < qtL.bl || li >= qtL.tl) : | 
| 171 | 
> | 
                                (li < qtL.bl && li >= qtL.tl)) | 
| 172 | 
> | 
                                tp->flgs &= ~LFF(i); | 
| 173 | 
  | 
                } | 
| 174 | 
  | 
} | 
| 175 | 
  | 
 | 
| 178 | 
  | 
qtCompost(pct)                  /* free up some leaves */ | 
| 179 | 
  | 
int     pct; | 
| 180 | 
  | 
{ | 
| 181 | 
< | 
        int     nused, nclear; | 
| 181 | 
> | 
        int     nused, nclear, nmapped; | 
| 182 | 
> | 
 | 
| 183 | 
  | 
                                /* figure out how many leaves to clear */ | 
| 184 | 
< | 
        nclear = nleaves * pct / 100; | 
| 184 | 
> | 
        nclear = qtL.nl * pct / 100; | 
| 185 | 
> | 
        nused = qtL.tl - qtL.bl; | 
| 186 | 
> | 
        if (nused <= 0) nused += qtL.nl; | 
| 187 | 
> | 
        nclear -= qtL.nl - nused; | 
| 188 | 
  | 
        if (nclear <= 0) | 
| 189 | 
  | 
                return(0); | 
| 165 | 
– | 
        nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf; | 
| 190 | 
  | 
        if (nclear >= nused) {  /* clear them all */ | 
| 191 | 
< | 
                freetree(0); | 
| 192 | 
< | 
                bleaf = tleaf = 0; | 
| 191 | 
> | 
                qtFreeTree(0); | 
| 192 | 
> | 
                qtL.tml = qtL.bl = qtL.tl = 0; | 
| 193 | 
  | 
                return(nused); | 
| 194 | 
  | 
        } | 
| 195 | 
  | 
                                /* else clear leaves from bottom */ | 
| 196 | 
< | 
        bleaf = (bleaf + nclear) % nleaves; | 
| 196 | 
> | 
        nmapped = qtL.tml - qtL.bl; | 
| 197 | 
> | 
        if (nmapped < 0) nmapped += qtL.nl; | 
| 198 | 
> | 
        qtL.bl += nclear; | 
| 199 | 
> | 
        if (qtL.bl >= qtL.nl) qtL.bl -= qtL.nl; | 
| 200 | 
> | 
        if (nmapped <= nclear) qtL.tml = qtL.bl; | 
| 201 | 
  | 
        shaketree(&qtrunk); | 
| 202 | 
  | 
        return(nclear); | 
| 203 | 
  | 
} | 
| 204 | 
  | 
 | 
| 205 | 
  | 
 | 
| 206 | 
+ | 
int | 
| 207 | 
+ | 
qtFindLeaf(x, y)                /* find closest leaf to (x,y) */ | 
| 208 | 
+ | 
int     x, y; | 
| 209 | 
+ | 
{ | 
| 210 | 
+ | 
        register RTREE  *tp = &qtrunk; | 
| 211 | 
+ | 
        int     li = -1; | 
| 212 | 
+ | 
        int     x0=0, y0=0, x1=odev.hres, y1=odev.vres; | 
| 213 | 
+ | 
        int     mx, my; | 
| 214 | 
+ | 
        register int    q; | 
| 215 | 
+ | 
                                        /* check limits */ | 
| 216 | 
+ | 
        if (x < 0 || x >= odev.hres || y < 0 || y >= odev.vres) | 
| 217 | 
+ | 
                return(-1); | 
| 218 | 
+ | 
                                        /* find nearby leaf in our tree */ | 
| 219 | 
+ | 
        for ( ; ; ) { | 
| 220 | 
+ | 
                for (q = 0; q < 4; q++)         /* find any leaf this level */ | 
| 221 | 
+ | 
                        if (tp->flgs & LFF(q)) { | 
| 222 | 
+ | 
                                li = tp->k[q].li; | 
| 223 | 
+ | 
                                break; | 
| 224 | 
+ | 
                        } | 
| 225 | 
+ | 
                q = 0;                          /* which quadrant are we? */ | 
| 226 | 
+ | 
                mx = (x0 + x1) >> 1; | 
| 227 | 
+ | 
                my = (y0 + y1) >> 1; | 
| 228 | 
+ | 
                if (x < mx) x1 = mx; | 
| 229 | 
+ | 
                else {x0 = mx; q |= 01;} | 
| 230 | 
+ | 
                if (y < my) y1 = my; | 
| 231 | 
+ | 
                else {y0 = my; q |= 02;} | 
| 232 | 
+ | 
                if (tp->flgs & BRF(q)) {        /* branch down if not a leaf */ | 
| 233 | 
+ | 
                        tp = tp->k[q].b; | 
| 234 | 
+ | 
                        continue; | 
| 235 | 
+ | 
                } | 
| 236 | 
+ | 
                if (tp->flgs & LFF(q))          /* good shot! */ | 
| 237 | 
+ | 
                        return(tp->k[q].li); | 
| 238 | 
+ | 
                return(li);                     /* else return what we have */ | 
| 239 | 
+ | 
        } | 
| 240 | 
+ | 
} | 
| 241 | 
+ | 
 | 
| 242 | 
+ | 
 | 
| 243 | 
  | 
static | 
| 244 | 
< | 
addleaf(lp)                     /* add a leaf to our tree */ | 
| 245 | 
< | 
RLEAF   *lp; | 
| 244 | 
> | 
addleaf(li)                     /* add a leaf to our tree */ | 
| 245 | 
> | 
int     li; | 
| 246 | 
  | 
{ | 
| 247 | 
  | 
        register RTREE  *tp = &qtrunk; | 
| 248 | 
  | 
        int     x0=0, y0=0, x1=odev.hres, y1=odev.vres; | 
| 249 | 
< | 
        RLEAF   *lo = NULL; | 
| 249 | 
> | 
        int     lo = -1; | 
| 250 | 
> | 
        double  d2; | 
| 251 | 
  | 
        int     x, y, mx, my; | 
| 252 | 
  | 
        double  z; | 
| 253 | 
< | 
        FVECT   ip, wp; | 
| 253 | 
> | 
        FVECT   ip, wp, vd; | 
| 254 | 
  | 
        register int    q; | 
| 255 | 
< | 
                                        /* compute leaf location */ | 
| 256 | 
< | 
        VCOPY(wp, lp->wp); | 
| 255 | 
> | 
                                        /* compute leaf location in view */ | 
| 256 | 
> | 
        VCOPY(wp, qtL.wp[li]); | 
| 257 | 
  | 
        viewloc(ip, &odev.v, wp); | 
| 258 | 
  | 
        if (ip[2] <= 0. || ip[0] < 0. || ip[0] >= 1. | 
| 259 | 
  | 
                        || ip[1] < 0. || ip[1] >= 1.) | 
| 260 | 
< | 
                return; | 
| 260 | 
> | 
                return(-1);                     /* behind or outside view */ | 
| 261 | 
> | 
#ifdef DEBUG | 
| 262 | 
> | 
        if (odev.v.type == VT_PAR | odev.v.vfore > FTINY) | 
| 263 | 
> | 
                error(INTERNAL, "bad view assumption in addleaf"); | 
| 264 | 
> | 
#endif | 
| 265 | 
> | 
        for (q = 0; q < 3; q++) | 
| 266 | 
> | 
                vd[q] = (wp[q] - odev.v.vp[q])/ip[2]; | 
| 267 | 
> | 
        d2 = fdir2diff(qtL.wd[li], vd); | 
| 268 | 
> | 
#ifdef MAXDIFF2 | 
| 269 | 
> | 
        if (d2 > MAXDIFF2) | 
| 270 | 
> | 
                return(0);                      /* leaf dir. too far off */ | 
| 271 | 
> | 
#endif | 
| 272 | 
  | 
        x = ip[0] * odev.hres; | 
| 273 | 
  | 
        y = ip[1] * odev.vres; | 
| 274 | 
  | 
        z = ip[2]; | 
| 286 | 
  | 
                        tp = tp->k[q].b; | 
| 287 | 
  | 
                        continue; | 
| 288 | 
  | 
                } | 
| 289 | 
< | 
                if (tp->k[q].l == NULL) {       /* found stem for leaf */ | 
| 290 | 
< | 
                        tp->k[q].l = lp; | 
| 291 | 
< | 
                        tp->flgs |= CHF(q); | 
| 289 | 
> | 
                if (!(tp->flgs & LFF(q))) {     /* found stem for leaf */ | 
| 290 | 
> | 
                        tp->k[q].li = li; | 
| 291 | 
> | 
                        tp->flgs |= CHLFF(q); | 
| 292 | 
  | 
                        break; | 
| 293 | 
  | 
                }        | 
| 294 | 
< | 
                                                /* check existing leaf */ | 
| 295 | 
< | 
                if (lo != tp->k[q].l) { | 
| 296 | 
< | 
                        lo = tp->k[q].l; | 
| 220 | 
< | 
                        VCOPY(wp, lo->wp); | 
| 294 | 
> | 
                if (lo != tp->k[q].li) {        /* check old leaf */ | 
| 295 | 
> | 
                        lo = tp->k[q].li; | 
| 296 | 
> | 
                        VCOPY(wp, qtL.wp[lo]); | 
| 297 | 
  | 
                        viewloc(ip, &odev.v, wp); | 
| 298 | 
  | 
                } | 
| 299 | 
  | 
                                                /* is node minimum size? */ | 
| 300 | 
< | 
                if (x1-x0 <= qtMinNodesiz || y1-y0 <= qtMinNodesiz) { | 
| 301 | 
< | 
                        if (z > (1.-qtDepthEps)*ip[2])  /* who is closer? */ | 
| 302 | 
< | 
                                return;                 /* old one is */ | 
| 303 | 
< | 
                        tp->k[q].l = lp;                /* new one is */ | 
| 300 | 
> | 
                if (y1-y0 <= qtMinNodesiz || x1-x0 <= qtMinNodesiz) { | 
| 301 | 
> | 
                        if (z > (1.+qtDepthEps)*ip[2]) | 
| 302 | 
> | 
                                return(0);              /* old one closer */ | 
| 303 | 
> | 
                        if (z >= (1.-qtDepthEps)*ip[2] && | 
| 304 | 
> | 
                                        fdir2diff(qtL.wd[lo], vd) < d2) | 
| 305 | 
> | 
                                return(0);              /* old one better */ | 
| 306 | 
> | 
                        tp->k[q].li = li;               /* else new one is */ | 
| 307 | 
  | 
                        tp->flgs |= CHF(q); | 
| 229 | 
– | 
                        tmAddHisto(&lo->brt, 1, -1);    /* drop old one */ | 
| 308 | 
  | 
                        break; | 
| 309 | 
  | 
                } | 
| 310 | 
< | 
                tp->flgs |= CHBRF(q);           /* else grow tree */ | 
| 310 | 
> | 
                tp->flgs &= ~LFF(q);            /* else grow tree */ | 
| 311 | 
> | 
                tp->flgs |= CHBRF(q); | 
| 312 | 
  | 
                tp = tp->k[q].b = newtwig(); | 
| 234 | 
– | 
                tp->flgs |= CH_ANY;             /* all new */ | 
| 313 | 
  | 
                q = 0;                          /* old leaf -> new branch */ | 
| 314 | 
  | 
                mx = ip[0] * odev.hres; | 
| 315 | 
  | 
                my = ip[1] * odev.vres; | 
| 316 | 
  | 
                if (mx >= (x0 + x1) >> 1) q |= 01; | 
| 317 | 
  | 
                if (my >= (y0 + y1) >> 1) q |= 02; | 
| 318 | 
< | 
                tp->k[q].l = lo; | 
| 318 | 
> | 
                tp->flgs = CH_ANY|LFF(q);       /* all new */ | 
| 319 | 
> | 
                tp->k[q].li = lo; | 
| 320 | 
  | 
        } | 
| 321 | 
< | 
        tmAddHisto(&lp->brt, 1, 1);     /* add leaf to histogram */ | 
| 321 | 
> | 
        return(1);              /* done */ | 
| 322 | 
  | 
} | 
| 323 | 
  | 
 | 
| 324 | 
  | 
 | 
| 325 | 
< | 
dev_value(c, p)                 /* add a pixel value to our output queue */ | 
| 325 | 
> | 
dev_value(c, p, v)              /* add a pixel value to our quadtree */ | 
| 326 | 
  | 
COLR    c; | 
| 327 | 
< | 
FVECT   p; | 
| 327 | 
> | 
FVECT   p, v; | 
| 328 | 
  | 
{ | 
| 329 | 
< | 
        register RLEAF  *lp; | 
| 329 | 
> | 
        register int    li; | 
| 330 | 
  | 
 | 
| 331 | 
< | 
        lp = newleaf(); | 
| 332 | 
< | 
        VCOPY(lp->wp, p); | 
| 333 | 
< | 
        tmCvColrs(&lp->brt, lp->chr, c, 1); | 
| 334 | 
< | 
        addleaf(lp); | 
| 331 | 
> | 
        li = newleaf(); | 
| 332 | 
> | 
        VCOPY(qtL.wp[li], p); | 
| 333 | 
> | 
        qtL.wd[li] = encodedir(v); | 
| 334 | 
> | 
        tmCvColrs(&qtL.brt[li], qtL.chr[li], c, 1); | 
| 335 | 
> | 
        if (!addleaf(li)) | 
| 336 | 
> | 
                ungetleaf(li); | 
| 337 | 
  | 
} | 
| 338 | 
  | 
 | 
| 339 | 
  | 
 | 
| 340 | 
  | 
qtReplant()                     /* replant our tree using new view */ | 
| 341 | 
  | 
{ | 
| 342 | 
  | 
        register int    i; | 
| 343 | 
< | 
 | 
| 344 | 
< | 
        if (bleaf == tleaf)             /* anything to replant? */ | 
| 343 | 
> | 
                                        /* anything to replant? */ | 
| 344 | 
> | 
        if (qtL.bl == qtL.tl) | 
| 345 | 
  | 
                return; | 
| 346 | 
< | 
        freetree(0);                    /* blow the tree away */ | 
| 347 | 
< | 
                                        /* now rebuild it */ | 
| 348 | 
< | 
        for (i = bleaf; i != tleaf; ) { | 
| 349 | 
< | 
                addleaf(leafpile+i); | 
| 350 | 
< | 
                if (++i >= nleaves) i = 0; | 
| 346 | 
> | 
        qtFreeTree(0);                  /* blow the old tree away */ | 
| 347 | 
> | 
                                        /* regrow it in new place */ | 
| 348 | 
> | 
        for (i = qtL.bl; i != qtL.tl; ) { | 
| 349 | 
> | 
                addleaf(i); | 
| 350 | 
> | 
                if (++i >= qtL.nl) i = 0; | 
| 351 | 
  | 
        } | 
| 271 | 
– | 
        tmComputeMapping(0., 0., 0.);   /* update the display */ | 
| 272 | 
– | 
        qtUpdate(); | 
| 352 | 
  | 
} | 
| 353 | 
  | 
 | 
| 354 | 
  | 
 | 
| 355 | 
< | 
static | 
| 356 | 
< | 
redraw(ca, tp, x0, y0, x1, y1, l)       /* redraw portion of a tree */ | 
| 278 | 
< | 
BYTE    ca[3];          /* returned average color */ | 
| 279 | 
< | 
register RTREE  *tp; | 
| 280 | 
< | 
int     x0, y0, x1, y1; | 
| 281 | 
< | 
int     l[2][2]; | 
| 355 | 
> | 
qtMapLeaves(redo)               /* map our leaves to RGB */ | 
| 356 | 
> | 
int     redo; | 
| 357 | 
  | 
{ | 
| 358 | 
< | 
        int     csm[3], nc; | 
| 359 | 
< | 
        BYTE    rgb[3]; | 
| 360 | 
< | 
        int     quads = CH_ANY; | 
| 361 | 
< | 
        int     mx, my; | 
| 362 | 
< | 
        register int    i; | 
| 363 | 
< | 
                                        /* compute midpoint */ | 
| 364 | 
< | 
        mx = (x0 + x1) >> 1; | 
| 365 | 
< | 
        my = (y0 + y1) >> 1; | 
| 366 | 
< | 
                                        /* see what to do */ | 
| 367 | 
< | 
        if (l[0][0] >= mx) | 
| 368 | 
< | 
                quads &= ~(CHF(2)|CHF(0)); | 
| 369 | 
< | 
        else if (l[0][1] <= mx) | 
| 295 | 
< | 
                quads &= ~(CHF(3)|CHF(1)); | 
| 296 | 
< | 
        if (l[1][0] >= my) | 
| 297 | 
< | 
                quads &= ~(CHF(1)|CHF(0)); | 
| 298 | 
< | 
        else if (l[1][1] <= my) | 
| 299 | 
< | 
                quads &= ~(CHF(3)|CHF(2)); | 
| 300 | 
< | 
        tp->flgs &= ~quads;             /* mark them done */ | 
| 301 | 
< | 
        csm[0] = csm[1] = csm[2] = nc = 0; | 
| 302 | 
< | 
                                        /* do leaves first */ | 
| 303 | 
< | 
        for (i = 0; i < 4; i++) | 
| 304 | 
< | 
                if (quads & CHF(i) && !(tp->flgs & BRF(i)) && | 
| 305 | 
< | 
                                tp->k[i].l != NULL) { | 
| 306 | 
< | 
                        tmMapPixels(rgb, &tp->k[i].l->brt, tp->k[i].l->chr, 1); | 
| 307 | 
< | 
                        dev_paintr(rgb, i&01 ? mx : x0, i&02 ? my : y0, | 
| 308 | 
< | 
                                        i&01 ? x1 : mx, i&02 ? y1 : my); | 
| 309 | 
< | 
                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2]; | 
| 310 | 
< | 
                        nc++; | 
| 311 | 
< | 
                        quads &= ~CHF(i); | 
| 312 | 
< | 
                } | 
| 313 | 
< | 
                                        /* now do branches */ | 
| 314 | 
< | 
        for (i = 0; i < 4; i++) | 
| 315 | 
< | 
                if (quads & CHF(i) && tp->flgs & BRF(i)) { | 
| 316 | 
< | 
                        redraw(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0, | 
| 317 | 
< | 
                                        i&01 ? x1 : mx, i&02 ? y1 : my, l); | 
| 318 | 
< | 
                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2]; | 
| 319 | 
< | 
                        nc++; | 
| 320 | 
< | 
                        quads &= ~CHF(i); | 
| 321 | 
< | 
                } | 
| 322 | 
< | 
        if (nc > 1) { | 
| 323 | 
< | 
                ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc; | 
| 358 | 
> | 
        int     aorg, alen, borg, blen; | 
| 359 | 
> | 
                                        /* recompute mapping? */ | 
| 360 | 
> | 
        if (redo) | 
| 361 | 
> | 
                qtL.tml = qtL.bl; | 
| 362 | 
> | 
                                        /* already done? */ | 
| 363 | 
> | 
        if (qtL.tml == qtL.tl) | 
| 364 | 
> | 
                return(1); | 
| 365 | 
> | 
                                        /* compute segments */ | 
| 366 | 
> | 
        aorg = qtL.tml; | 
| 367 | 
> | 
        if (qtL.tl >= aorg) { | 
| 368 | 
> | 
                alen = qtL.tl - aorg; | 
| 369 | 
> | 
                blen = 0; | 
| 370 | 
  | 
        } else { | 
| 371 | 
< | 
                ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2]; | 
| 371 | 
> | 
                alen = qtL.nl - aorg; | 
| 372 | 
> | 
                borg = 0; | 
| 373 | 
> | 
                blen = qtL.tl; | 
| 374 | 
  | 
        } | 
| 375 | 
< | 
        if (!quads) return; | 
| 376 | 
< | 
                                        /* fill in gaps with average */ | 
| 377 | 
< | 
        for (i = 0; i < 4; i++) | 
| 378 | 
< | 
                if (quads & CHF(i)) | 
| 379 | 
< | 
                        dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0, | 
| 380 | 
< | 
                                        i&01 ? x1 : mx, i&02 ? y1 : my); | 
| 381 | 
< | 
} | 
| 382 | 
< | 
 | 
| 335 | 
< | 
 | 
| 336 | 
< | 
static | 
| 337 | 
< | 
update(ca, tp, x0, y0, x1, y1)  /* update tree display as needed */ | 
| 338 | 
< | 
BYTE    ca[3];          /* returned average color */ | 
| 339 | 
< | 
register RTREE  *tp; | 
| 340 | 
< | 
int     x0, y0, x1, y1; | 
| 341 | 
< | 
{ | 
| 342 | 
< | 
        int     csm[3], nc; | 
| 343 | 
< | 
        BYTE    rgb[3]; | 
| 344 | 
< | 
        int     gaps = 0; | 
| 345 | 
< | 
        int     mx, my; | 
| 346 | 
< | 
        register int    i; | 
| 347 | 
< | 
                                        /* compute midpoint */ | 
| 348 | 
< | 
        mx = (x0 + x1) >> 1; | 
| 349 | 
< | 
        my = (y0 + y1) >> 1; | 
| 350 | 
< | 
        csm[0] = csm[1] = csm[2] = nc = 0; | 
| 351 | 
< | 
                                        /* do leaves first */ | 
| 352 | 
< | 
        for (i = 0; i < 4; i++) | 
| 353 | 
< | 
                if ((tp->flgs & CHBRF(i)) == CHF(i)) { | 
| 354 | 
< | 
                        if (tp->k[i].l == NULL) { | 
| 355 | 
< | 
                                gaps |= 1<<i;   /* empty stem */ | 
| 356 | 
< | 
                                continue; | 
| 357 | 
< | 
                        } | 
| 358 | 
< | 
                        tmMapPixels(rgb, &tp->k[i].l->brt, tp->k[i].l->chr, 1); | 
| 359 | 
< | 
                        dev_paintr(rgb, i&01 ? mx : x0, i&02 ? my : y0, | 
| 360 | 
< | 
                                        i&01 ? x1 : mx, i&02 ? y1 : my); | 
| 361 | 
< | 
                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2]; | 
| 362 | 
< | 
                        nc++; | 
| 363 | 
< | 
                } | 
| 364 | 
< | 
                                        /* now do branches */ | 
| 365 | 
< | 
        for (i = 0; i < 4; i++) | 
| 366 | 
< | 
                if ((tp->flgs & CHBRF(i)) == CHBRF(i)) { | 
| 367 | 
< | 
                        update(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0, | 
| 368 | 
< | 
                                        i&01 ? x1 : mx, i&02 ? y1 : my); | 
| 369 | 
< | 
                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2]; | 
| 370 | 
< | 
                        nc++; | 
| 371 | 
< | 
                } | 
| 372 | 
< | 
        if (nc > 1) { | 
| 373 | 
< | 
                ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc; | 
| 374 | 
< | 
        } else { | 
| 375 | 
< | 
                ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2]; | 
| 375 | 
> | 
                                        /* (re)compute tone mapping? */ | 
| 376 | 
> | 
        if (qtL.tml == qtL.bl) { | 
| 377 | 
> | 
                tmClearHisto(); | 
| 378 | 
> | 
                tmAddHisto(qtL.brt+aorg, alen, 1); | 
| 379 | 
> | 
                if (blen > 0) | 
| 380 | 
> | 
                        tmAddHisto(qtL.brt+borg, blen, 1); | 
| 381 | 
> | 
                if (tmComputeMapping(0., 0., 0.) != TM_E_OK) | 
| 382 | 
> | 
                        return(0); | 
| 383 | 
  | 
        } | 
| 384 | 
< | 
                                        /* fill in gaps with average */ | 
| 385 | 
< | 
        for (i = 0; gaps && i < 4; gaps >>= 1, i++) | 
| 386 | 
< | 
                if (gaps & 01) | 
| 387 | 
< | 
                        dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0, | 
| 388 | 
< | 
                                        i&01 ? x1 : mx, i&02 ? y1 : my); | 
| 389 | 
< | 
        tp->flgs &= ~CH_ANY;            /* all done */ | 
| 390 | 
< | 
} | 
| 391 | 
< | 
 | 
| 385 | 
< | 
 | 
| 386 | 
< | 
qtRedraw(x0, y0, x1, y1)        /* redraw part of our screen */ | 
| 387 | 
< | 
int     x0, y0, x1, y1; | 
| 388 | 
< | 
{ | 
| 389 | 
< | 
        int     lim[2][2]; | 
| 390 | 
< | 
        BYTE    ca[3]; | 
| 391 | 
< | 
 | 
| 392 | 
< | 
        if (is_stump(&qtrunk)) | 
| 393 | 
< | 
                return; | 
| 394 | 
< | 
        if ((lim[0][0]=x0) == 0 & (lim[1][0]=y0) == 0 & | 
| 395 | 
< | 
                (lim[0][1]=x1) == odev.hres & (lim[1][1]=y1) == odev.vres || | 
| 396 | 
< | 
                        tmTop->lumap == NULL) | 
| 397 | 
< | 
                tmComputeMapping(0., 0., 0.); | 
| 398 | 
< | 
        redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim); | 
| 399 | 
< | 
} | 
| 400 | 
< | 
 | 
| 401 | 
< | 
 | 
| 402 | 
< | 
qtUpdate()                      /* update our tree display */ | 
| 403 | 
< | 
{ | 
| 404 | 
< | 
        BYTE    ca[3]; | 
| 405 | 
< | 
 | 
| 406 | 
< | 
        if (is_stump(&qtrunk)) | 
| 407 | 
< | 
                return; | 
| 408 | 
< | 
        if (tmTop->lumap == NULL) | 
| 409 | 
< | 
                tmComputeMapping(0., 0., 0.); | 
| 410 | 
< | 
        update(ca, &qtrunk, 0, 0, odev.hres, odev.vres); | 
| 384 | 
> | 
        if (tmMapPixels(qtL.rgb+aorg, qtL.brt+aorg, | 
| 385 | 
> | 
                        qtL.chr+aorg, alen) != TM_E_OK) | 
| 386 | 
> | 
                return(0); | 
| 387 | 
> | 
        if (blen > 0) | 
| 388 | 
> | 
                tmMapPixels(qtL.rgb+borg, qtL.brt+borg, | 
| 389 | 
> | 
                                qtL.chr+borg, blen); | 
| 390 | 
> | 
        qtL.tml = qtL.tl; | 
| 391 | 
> | 
        return(1); | 
| 392 | 
  | 
} |