ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhd_qtree.c
(Generate patch)

Comparing ray/src/hd/rhd_qtree.c (file contents):
Revision 3.7 by gregl, Tue Nov 25 11:15:20 1997 UTC vs.
Revision 3.23 by schorsch, Mon Jun 30 14:59:11 2003 UTC

# Line 1 | Line 1
1 /* Copyright (c) 1997 Silicon Graphics, Inc. */
2
1   #ifndef lint
2 < static char SCCSid[] = "$SunId$ SGI";
2 > static const char       RCSid[] = "$Id$";
3   #endif
6
4   /*
5   * Quadtree driver support routines.
6   */
7  
8 + #include <string.h>
9 +
10   #include "standard.h"
11   #include "rhd_qtree.h"
12                                  /* quantity of leaves to free at a time */
13   #ifndef LFREEPCT
14   #define LFREEPCT        25
15   #endif
16 +                                /* maximum allowed angle difference (deg.) */
17 + #ifndef MAXANG
18 + #define MAXANG          20
19 + #endif
20 + #if MAXANG>0
21 + #define MAXDIFF2        ( MAXANG*MAXANG * (PI*PI/180./180.))
22 + #endif
23  
24 + #define abs(i)          ((i) < 0 ? -(i) : (i))
25 +
26   RTREE   qtrunk;                 /* our quadtree trunk */
27 < double  qtDepthEps = .02;       /* epsilon to compare depths (z fraction) */
27 > double  qtDepthEps = .05;       /* epsilon to compare depths (z fraction) */
28   int     qtMinNodesiz = 2;       /* minimum node dimension (pixels) */
29   struct rleaves  qtL;            /* our pile of leaves */
30  
31 + int     rayqleft = 0;           /* rays left to queue before flush */
32 +
33 + static int32    falleaves;      /* our list of fallen leaves */
34 +
35 + #define composted(li)   (qtL.bl <= qtL.tl ? \
36 +                                        ((li) < qtL.bl || (li) >= qtL.tl) : \
37 +                                        ((li) < qtL.bl && (li) >= qtL.tl))
38 +
39   #define TBUNDLESIZ      409     /* number of twigs in a bundle */
40  
41   static RTREE    **twigbundle;   /* free twig blocks (NULL term.) */
42   static int      nexttwig;       /* next free twig */
43  
28 #define is_stump(t)     (!((t)->flgs & (BR_ANY|LF_ANY)))
44  
30
45   static RTREE *
46   newtwig()                       /* allocate a twig */
47   {
# Line 41 | Line 55 | newtwig()                      /* allocate a twig */
55          }
56          bi = nexttwig / TBUNDLESIZ;
57          if (twigbundle[bi] == NULL) {   /* new block */
58 <                twigbundle = (RTREE **)realloc((char *)twigbundle,
58 >                twigbundle = (RTREE **)realloc((void *)twigbundle,
59                                          (bi+2)*sizeof(RTREE *));
60                  if (twigbundle == NULL)
61                          goto memerr;
# Line 69 | Line 83 | int    really;
83          nexttwig = 0;
84          if (!really) {          /* just clear allocated blocks */
85                  while (i--)
86 <                        bzero((char *)twigbundle[i], TBUNDLESIZ*sizeof(RTREE));
86 >                        memset((char *)twigbundle[i], '\0', TBUNDLESIZ*sizeof(RTREE));
87                  return;
88          }
89                                  /* else "really" means free up memory */
90          for (i = 0; twigbundle[i] != NULL; i++)
91 <                free((char *)twigbundle[i]);
92 <        free((char *)twigbundle);
91 >                free((void *)twigbundle[i]);
92 >        free((void *)twigbundle);
93          twigbundle = NULL;
94   }
95  
96  
97 < static int
98 < newleaf()                       /* allocate a leaf from our pile */
85 < {
86 <        int     li;
87 <        
88 <        li = qtL.tl++;
89 <        if (qtL.tl >= qtL.nl)   /* get next leaf in ring */
90 <                qtL.tl = 0;
91 <        if (qtL.tl == qtL.bl)   /* need to shake some free */
92 <                qtCompost(LFREEPCT);
93 <        return(li);
94 < }
97 > #define LEAFSIZ         (3*sizeof(float)+sizeof(int32)+\
98 >                        sizeof(TMbright)+6*sizeof(BYTE))
99  
96
97 #define LEAFSIZ         (3*sizeof(float)+sizeof(TMbright)+6*sizeof(BYTE))
98
100   int
101   qtAllocLeaves(n)                /* allocate space for n leaves */
102   register int    n;
# Line 120 | Line 121 | register int   n;
121                  return(0);
122                                  /* assign larger alignment types earlier */
123          qtL.wp = (float (*)[3])qtL.base;
124 <        qtL.brt = (TMbright *)(qtL.wp + n);
124 >        qtL.wd = (int32 *)(qtL.wp + n);
125 >        qtL.brt = (TMbright *)(qtL.wd + n);
126          qtL.chr = (BYTE (*)[3])(qtL.brt + n);
127          qtL.rgb = (BYTE (*)[3])(qtL.chr + n);
128          qtL.nl = n;
129          qtL.tml = qtL.bl = qtL.tl = 0;
130 +        falleaves = -1;
131          return(n);
132   }
133  
# Line 155 | Line 158 | register RTREE *tp;
158                                  tp->flgs &= ~BRF(i);
159                  } else if (tp->flgs & LFF(i)) {
160                          li = tp->k[i].li;
161 <                        if (qtL.bl < qtL.tl ?
159 <                                (li < qtL.bl || li >= qtL.tl) :
160 <                                (li < qtL.bl && li >= qtL.tl))
161 >                        if (composted(li))
162                                  tp->flgs &= ~LFF(i);
163                  }
164   }
# Line 167 | Line 168 | int
168   qtCompost(pct)                  /* free up some leaves */
169   int     pct;
170   {
171 +        register int32  *fl;
172          int     nused, nclear, nmapped;
171
173                                  /* figure out how many leaves to clear */
174          nclear = qtL.nl * pct / 100;
175          nused = qtL.tl - qtL.bl;
# Line 179 | Line 180 | int    pct;
180          if (nclear >= nused) {  /* clear them all */
181                  qtFreeTree(0);
182                  qtL.tml = qtL.bl = qtL.tl = 0;
183 +                falleaves = -1;
184                  return(nused);
185          }
186                                  /* else clear leaves from bottom */
# Line 187 | Line 189 | int    pct;
189          qtL.bl += nclear;
190          if (qtL.bl >= qtL.nl) qtL.bl -= qtL.nl;
191          if (nmapped <= nclear) qtL.tml = qtL.bl;
192 <        shaketree(&qtrunk);
192 >        shaketree(&qtrunk);     /* dereference composted leaves */
193 >        for (fl = &falleaves; *fl >= 0; fl = qtL.wd + *fl)
194 >                while (composted(*fl))
195 >                        if ((*fl = qtL.wd[*fl]) < 0)
196 >                                return(nclear);
197          return(nclear);
198   }
199  
# Line 230 | Line 236 | int    x, y;
236  
237  
238   static
239 < addleaf(li)                     /* add a leaf to our tree */
240 < int     li;
239 > putleaf(li, drop)               /* put a leaf in our tree */
240 > register int    li;
241 > int     drop;
242   {
243          register RTREE  *tp = &qtrunk;
244          int     x0=0, y0=0, x1=odev.hres, y1=odev.vres;
245 <        int     lo = -1;
245 >        register int    lo = -1;
246 >        double  d2;
247          int     x, y, mx, my;
248          double  z;
249 <        FVECT   ip, wp;
249 >        FVECT   ip, wp, vd;
250          register int    q;
251 <                                        /* compute leaf location */
251 >                                        /* check for dead leaf */
252 >        if (!qtL.chr[li][1] && !(qtL.chr[li][0] | qtL.chr[li][2]))
253 >                return(0);
254 >                                        /* compute leaf location in view */
255          VCOPY(wp, qtL.wp[li]);
256          viewloc(ip, &odev.v, wp);
257          if (ip[2] <= 0. || ip[0] < 0. || ip[0] >= 1.
258                          || ip[1] < 0. || ip[1] >= 1.)
259 <                return;
259 >                goto dropit;                    /* behind or outside view */
260 > #ifdef DEBUG
261 >        if (odev.v.type == VT_PAR | odev.v.vfore > FTINY)
262 >                error(INTERNAL, "bad view assumption in putleaf");
263 > #endif
264 >        for (q = 0; q < 3; q++)
265 >                vd[q] = (wp[q] - odev.v.vp[q])/ip[2];
266 >        d2 = fdir2diff(qtL.wd[li], vd);
267 > #ifdef MAXDIFF2
268 >        if (d2 > MAXDIFF2)
269 >                goto dropit;                    /* leaf dir. too far off */
270 > #endif
271          x = ip[0] * odev.hres;
272          y = ip[1] * odev.vres;
273          z = ip[2];
# Line 266 | Line 288 | int    li;
288                  if (!(tp->flgs & LFF(q))) {     /* found stem for leaf */
289                          tp->k[q].li = li;
290                          tp->flgs |= CHLFF(q);
291 <                        break;
291 >                        return(1);
292                  }      
293 <                                                /* check existing leaf */
272 <                if (lo != tp->k[q].li) {
293 >                if (lo != tp->k[q].li) {        /* check old leaf */
294                          lo = tp->k[q].li;
295                          VCOPY(wp, qtL.wp[lo]);
296                          viewloc(ip, &odev.v, wp);
297                  }
298                                                  /* is node minimum size? */
299 <                if (x1-x0 <= qtMinNodesiz || y1-y0 <= qtMinNodesiz) {
300 <                        if (z > (1.-qtDepthEps)*ip[2])  /* who is closer? */
301 <                                return;                 /* old one is */
302 <                        tp->k[q].li = li;               /* new one is */
299 >                if (y1-y0 <= qtMinNodesiz || x1-x0 <= qtMinNodesiz) {
300 >                        if (z > (1.+qtDepthEps)*ip[2])
301 >                                break;                  /* old one closer */
302 >                        if (z >= (1.-qtDepthEps)*ip[2] &&
303 >                                        fdir2diff(qtL.wd[lo], vd) < d2)
304 >                                break;                  /* old one better */
305 >                        tp->k[q].li = li;               /* attach new */
306                          tp->flgs |= CHF(q);
307 +                        li = lo;                        /* drop old... */
308                          break;
309                  }
310                  tp->flgs &= ~LFF(q);            /* else grow tree */
# Line 290 | Line 315 | int    li;
315                  my = ip[1] * odev.vres;
316                  if (mx >= (x0 + x1) >> 1) q |= 01;
317                  if (my >= (y0 + y1) >> 1) q |= 02;
318 +                tp->flgs = CH_ANY|LFF(q);       /* all new */
319                  tp->k[q].li = lo;
294                tp->flgs |= LFF(q)|CH_ANY;      /* all new */
320          }
321 + dropit:
322 +        if (drop)
323 +                if (li+1 == (qtL.tl ? qtL.tl : qtL.nl))
324 +                        qtL.tl = li;            /* special case */
325 +                else {
326 +                        qtL.chr[li][0] = qtL.chr[li][1] = qtL.chr[li][2] = 0;
327 +                        qtL.wd[li] = falleaves;
328 +                        falleaves = li;
329 +                }
330 +        return(li == lo);
331   }
332  
333  
334 < dev_value(c, p)                 /* add a pixel value to our output queue */
334 > dev_value(c, d, p)              /* add a pixel value to our quadtree */
335   COLR    c;
336 < FVECT   p;
336 > FVECT   d, p;
337   {
338          register int    li;
339 <
340 <        li = newleaf();
341 <        VCOPY(qtL.wp[li], p);
342 <        tmCvColrs(&qtL.brt[li], qtL.chr[li], c, 1);
343 <        addleaf(li);
339 >        int     mapit;
340 >                                /* grab a leaf */
341 >        if (!imm_mode && falleaves >= 0) {      /* check for fallen leaves */
342 >                li = falleaves;
343 >                falleaves = qtL.wd[li];
344 >                mapit = qtL.tml <= qtL.tl ?
345 >                                (li < qtL.tml || li >= qtL.tl) :
346 >                                (li < qtL.tml && li >= qtL.tl) ;
347 >        } else {                                /* else allocate new one */
348 >                li = qtL.tl++;
349 >                if (qtL.tl >= qtL.nl)           /* next leaf in ring */
350 >                        qtL.tl = 0;
351 >                if (qtL.tl == qtL.bl)           /* need to shake some free */
352 >                        qtCompost(LFREEPCT);
353 >                mapit = 0;                      /* we'll map it later */
354 >        }
355 >        if (p == NULL)
356 >                VSUM(qtL.wp[li], odev.v.vp, d, FHUGE);
357 >        else
358 >                VCOPY(qtL.wp[li], p);
359 >        qtL.wd[li] = encodedir(d);
360 >        tmCvColrs(&qtL.brt[li], qtL.chr[li], (COLR *)c, 1);
361 >        if (putleaf(li, 1)) {
362 >                if (mapit)
363 >                        tmMapPixels((BYTE *)(qtL.rgb+li), qtL.brt+li,
364 >                                        (BYTE *)(qtL.chr+li), 1);
365 >                if (--rayqleft == 0)
366 >                        dev_flush();            /* flush output */
367 >        }
368   }
369  
370  
# Line 318 | Line 377 | qtReplant()                    /* replant our tree using new view */
377          qtFreeTree(0);                  /* blow the old tree away */
378                                          /* regrow it in new place */
379          for (i = qtL.bl; i != qtL.tl; ) {
380 <                addleaf(i);
380 >                putleaf(i, 0);
381                  if (++i >= qtL.nl) i = 0;
382          }
383   }
# Line 353 | Line 412 | int    redo;
412                  if (tmComputeMapping(0., 0., 0.) != TM_E_OK)
413                          return(0);
414          }
415 <        if (tmMapPixels(qtL.rgb+aorg, qtL.brt+aorg,
416 <                        qtL.chr+aorg, alen) != TM_E_OK)
415 >        if (tmMapPixels((BYTE *)(qtL.rgb+aorg), qtL.brt+aorg,
416 >                        (BYTE *)(qtL.chr+aorg), alen) != TM_E_OK)
417                  return(0);
418          if (blen > 0)
419 <                tmMapPixels(qtL.rgb+borg, qtL.brt+borg,
420 <                                qtL.chr+borg, blen);
419 >                tmMapPixels((BYTE *)(qtL.rgb+borg), qtL.brt+borg,
420 >                                (BYTE *)(qtL.chr+borg), blen);
421          qtL.tml = qtL.tl;
422          return(1);
364 }
365
366
367 static
368 redraw(tp, x0, y0, x1, y1, l)   /* mark portion of a tree for redraw */
369 register RTREE  *tp;
370 int     x0, y0, x1, y1;
371 int     l[2][2];
372 {
373        int     quads = CH_ANY;
374        int     mx, my;
375        register int    i;
376                                        /* compute midpoint */
377        mx = (x0 + x1) >> 1;
378        my = (y0 + y1) >> 1;
379                                        /* see what to do */
380        if (l[0][0] >= mx)
381                quads &= ~(CHF(2)|CHF(0));
382        else if (l[0][1] < mx)
383                quads &= ~(CHF(3)|CHF(1));
384        if (l[1][0] >= my)
385                quads &= ~(CHF(1)|CHF(0));
386        else if (l[1][1] < my)
387                quads &= ~(CHF(3)|CHF(2));
388        tp->flgs |= quads;              /* mark quadrants for update */
389                                        /* climb the branches */
390        for (i = 0; i < 4; i++)
391                if (tp->flgs & BRF(i) && quads & CHF(i))
392                        redraw(tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
393                                        i&01 ? x1 : mx, i&02 ? y1 : my, l);
394 }
395
396
397 static
398 update(ca, tp, x0, y0, x1, y1)  /* update tree display as needed */
399 BYTE    ca[3];          /* returned average color */
400 register RTREE  *tp;
401 int     x0, y0, x1, y1;
402 {
403        int     csm[3], nc;
404        register BYTE   *cp;
405        BYTE    rgb[3];
406        int     gaps = 0;
407        int     mx, my;
408        register int    i;
409                                        /* compute midpoint */
410        mx = (x0 + x1) >> 1;
411        my = (y0 + y1) >> 1;
412        csm[0] = csm[1] = csm[2] = nc = 0;
413                                        /* do leaves first */
414        for (i = 0; i < 4; i++) {
415                if (!(tp->flgs & CHF(i)))
416                        continue;
417                if (tp->flgs & LFF(i)) {
418                        dev_paintr(cp=qtL.rgb[tp->k[i].li],
419                                        i&01 ? mx : x0, i&02 ? my : y0,
420                                        i&01 ? x1 : mx, i&02 ? y1 : my);
421                        csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
422                        nc++;
423                } else if (!(tp->flgs & BRF(i)))
424                        gaps |= 1<<i;   /* empty stem */
425        }
426                                        /* now do branches */
427        for (i = 0; i < 4; i++)
428                if ((tp->flgs & CHBRF(i)) == CHBRF(i)) {
429                        update(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
430                                        i&01 ? x1 : mx, i&02 ? y1 : my);
431                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
432                        nc++;
433                }
434        if (nc > 1) {
435                ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
436        } else {
437                ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
438        }
439                                        /* fill in gaps with average */
440        for (i = 0; gaps && i < 4; gaps >>= 1, i++)
441                if (gaps & 01)
442                        dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
443                                        i&01 ? x1 : mx, i&02 ? y1 : my);
444        tp->flgs &= ~CH_ANY;            /* all done */
445 }
446
447
448 qtRedraw(x0, y0, x1, y1)        /* redraw part or all of our screen */
449 int     x0, y0, x1, y1;
450 {
451        int     lim[2][2];
452
453        if (is_stump(&qtrunk))
454                return;
455        if (!qtMapLeaves((lim[0][0]=x0) <= 0 & (lim[1][0]=y0) <= 0 &
456                (lim[0][1]=x1) >= odev.hres-1 & (lim[1][1]=y1) >= odev.vres-1))
457                return;
458        redraw(&qtrunk, 0, 0, odev.hres, odev.vres, lim);
459 }
460
461
462 qtUpdate()                      /* update our tree display */
463 {
464        BYTE    ca[3];
465
466        if (is_stump(&qtrunk))
467                return;
468        if (!qtMapLeaves(0))
469                return;
470        update(ca, &qtrunk, 0, 0, odev.hres, odev.vres);
423   }

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines