11 |
|
#include "standard.h" |
12 |
|
#include "rhd_qtree.h" |
13 |
|
|
14 |
– |
static RLEAF *leafpile; /* our collection of leaf values */ |
15 |
– |
static int nleaves; /* count of leaves in our pile */ |
16 |
– |
static int bleaf, tleaf; /* bottom and top (next) leaf index (ring) */ |
17 |
– |
|
14 |
|
RTREE qtrunk; /* our quadtree trunk */ |
15 |
|
double qtDepthEps = .02; /* epsilon to compare depths (z fraction) */ |
16 |
|
int qtMinNodesiz = 2; /* minimum node dimension (pixels) */ |
17 |
|
|
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 |
+ |
|
22 |
|
#define TBUNDLESIZ 409 /* number of twigs in a bundle */ |
23 |
|
|
24 |
|
static RTREE **twigbundle; /* free twig blocks (NULL term.) */ |
58 |
|
} |
59 |
|
|
60 |
|
|
61 |
< |
static |
62 |
< |
freetwigs(really) /* free allocated twigs */ |
61 |
> |
qtFreeTree(really) /* free allocated twigs */ |
62 |
|
int really; |
63 |
|
{ |
64 |
|
register int i; |
65 |
|
|
66 |
< |
if (tmTop != NULL) |
68 |
< |
tmClearHisto(); |
66 |
> |
tmClearHisto(); |
67 |
|
bzero((char *)&qtrunk, sizeof(RTREE)); |
68 |
|
nexttwig = 0; |
69 |
|
if (twigbundle == NULL) |
84 |
|
static RLEAF * |
85 |
|
newleaf() /* allocate a leaf from our pile */ |
86 |
|
{ |
87 |
< |
if (tleaf++ >= nleaves) /* get next leaf in ring */ |
87 |
> |
RLEAF *lp; |
88 |
> |
|
89 |
> |
lp = leafpile + tleaf++; |
90 |
> |
if (tleaf >= nleaves) /* get next leaf in ring */ |
91 |
|
tleaf = 0; |
92 |
|
if (tleaf == bleaf) /* need to shake some free */ |
93 |
|
qtCompost(LFREEPCT); |
94 |
< |
return(leafpile + tleaf); |
94 |
> |
return(lp); |
95 |
|
} |
96 |
|
|
97 |
|
|
102 |
|
unsigned nbytes; |
103 |
|
register unsigned i; |
104 |
|
|
105 |
< |
freetwigs(0); /* make sure tree is empty */ |
105 |
> |
qtFreeTree(0); /* make sure tree is empty */ |
106 |
|
if (n <= 0) |
107 |
|
return(0); |
108 |
|
if (nleaves >= n) |
125 |
|
|
126 |
|
qtFreeLeaves() /* free our allocated leaves and twigs */ |
127 |
|
{ |
128 |
< |
freetwigs(1); /* free tree also */ |
128 |
> |
qtFreeTree(1); /* free tree also */ |
129 |
|
if (nleaves <= 0) |
130 |
|
return; |
131 |
|
free((char *)leafpile); |
141 |
|
register int i, li; |
142 |
|
|
143 |
|
for (i = 0; i < 4; i++) |
144 |
< |
if (tp->flgs & BRF(i)) { |
145 |
< |
if (shaketree(tp->k[i].b)) |
146 |
< |
tp->flgs |= CHF(i); |
146 |
< |
} else if (tp->k[i].l != NULL) { |
144 |
> |
if (tp->flgs & BRF(i)) |
145 |
> |
shaketree(tp->k[i].b); |
146 |
> |
else if (tp->k[i].l != NULL) { |
147 |
|
li = tp->k[i].l - leafpile; |
148 |
|
if (bleaf < tleaf ? (li < bleaf || li >= tleaf) : |
149 |
|
(li < bleaf && li >= tleaf)) { |
150 |
|
tmAddHisto(&tp->k[i].l->brt, 1, -1); |
151 |
|
tp->k[i].l = NULL; |
152 |
– |
tp->flgs |= CHF(i); |
152 |
|
} |
153 |
|
} |
155 |
– |
return(tp->flgs & CH_ANY); |
154 |
|
} |
155 |
|
|
156 |
|
|
159 |
|
int pct; |
160 |
|
{ |
161 |
|
int nused, nclear; |
162 |
+ |
|
163 |
+ |
if (is_stump(&qtrunk)) |
164 |
+ |
return(0); |
165 |
|
/* figure out how many leaves to clear */ |
166 |
|
nclear = nleaves * pct / 100; |
167 |
+ |
nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf; |
168 |
+ |
nclear -= nleaves - nused; /* less what's already free */ |
169 |
|
if (nclear <= 0) |
170 |
|
return(0); |
168 |
– |
nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf; |
171 |
|
if (nclear >= nused) { /* clear them all */ |
172 |
< |
freetwigs(0); |
172 |
> |
qtFreeTree(0); |
173 |
|
bleaf = tleaf = 0; |
174 |
|
return(nused); |
175 |
|
} |
176 |
|
/* else clear leaves from bottom */ |
177 |
< |
bleaf = (bleaf + nclear) % nleaves; |
177 |
> |
bleaf += nclear; |
178 |
> |
if (bleaf >= nleaves) bleaf -= nleaves; |
179 |
|
shaketree(&qtrunk); |
180 |
|
return(nclear); |
181 |
|
} |
182 |
|
|
183 |
|
|
184 |
+ |
RLEAF * |
185 |
+ |
qtFindLeaf(x, y) /* find closest leaf to (x,y) */ |
186 |
+ |
int x, y; |
187 |
+ |
{ |
188 |
+ |
register RTREE *tp = &qtrunk; |
189 |
+ |
RLEAF *lp = NULL; |
190 |
+ |
int x0=0, y0=0, x1=odev.hres, y1=odev.vres; |
191 |
+ |
int mx, my; |
192 |
+ |
register int q; |
193 |
+ |
/* check limits */ |
194 |
+ |
if (x < 0 || x >= odev.hres || y < 0 || y >= odev.vres) |
195 |
+ |
return(NULL); |
196 |
+ |
/* find nearby leaf in our tree */ |
197 |
+ |
for ( ; ; ) { |
198 |
+ |
for (q = 0; q < 4; q++) /* find any leaf this level */ |
199 |
+ |
if (!(tp->flgs & BRF(q)) && tp->k[q].l != NULL) { |
200 |
+ |
lp = tp->k[q].l; |
201 |
+ |
break; |
202 |
+ |
} |
203 |
+ |
q = 0; /* which quadrant are we? */ |
204 |
+ |
mx = (x0 + x1) >> 1; |
205 |
+ |
my = (y0 + y1) >> 1; |
206 |
+ |
if (x < mx) x1 = mx; |
207 |
+ |
else {x0 = mx; q |= 01;} |
208 |
+ |
if (y < my) y1 = my; |
209 |
+ |
else {y0 = my; q |= 02;} |
210 |
+ |
if (tp->flgs & BRF(q)) { /* branch down if not a leaf */ |
211 |
+ |
tp = tp->k[q].b; |
212 |
+ |
continue; |
213 |
+ |
} |
214 |
+ |
if (tp->k[q].l != NULL) /* good shot! */ |
215 |
+ |
return(tp->k[q].l); |
216 |
+ |
return(lp); /* else return what we have */ |
217 |
+ |
} |
218 |
+ |
} |
219 |
+ |
|
220 |
+ |
|
221 |
|
static |
222 |
|
addleaf(lp) /* add a leaf to our tree */ |
223 |
|
RLEAF *lp; |
305 |
|
|
306 |
|
if (bleaf == tleaf) /* anything to replant? */ |
307 |
|
return; |
308 |
< |
freetwigs(0); /* blow the tree away */ |
308 |
> |
qtFreeTree(0); /* blow the tree away */ |
309 |
|
/* now rebuild it */ |
310 |
|
for (i = bleaf; i != tleaf; ) { |
311 |
|
addleaf(leafpile+i); |
434 |
|
|
435 |
|
if (is_stump(&qtrunk)) |
436 |
|
return; |
437 |
< |
if ((lim[0][0]=x0) == 0 & (lim[1][0]=y0) == 0 & |
438 |
< |
(lim[0][1]=x1) == odev.hres & (lim[1][1]=y1) == odev.vres || |
439 |
< |
tmTop->lumap == NULL) |
440 |
< |
tmComputeMapping(0., 0., 0.); |
437 |
> |
if ((lim[0][0]=x0) <= 0 & (lim[1][0]=y0) <= 0 & |
438 |
> |
(lim[0][1]=x1) >= odev.hres-1 & (lim[1][1]=y1) >= odev.vres-1 |
439 |
> |
|| tmTop->lumap == NULL) |
440 |
> |
if (tmComputeMapping(0., 0., 0.) != TM_E_OK) |
441 |
> |
return; |
442 |
|
redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim); |
443 |
|
} |
444 |
|
|