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

Comparing ray/src/hd/sm_qtree.h (file contents):
Revision 3.2 by gwlarson, Thu Aug 20 16:47:22 1998 UTC vs.
Revision 3.8 by gwlarson, Wed Nov 11 12:05:40 1998 UTC

# Line 19 | Line 19
19   *
20   *              < -1:   it is an index to a set of objects
21   */
22 + #include "object.h"
23  
24   #define  QUADTREE               int
25  
26   #define  EMPTY          (-1)
27  
28   #define  QT_IS_EMPTY(qt)        ((qt) == EMPTY)
29 < #define  QT_IS_LEAF(qt) ((qt) < EMPTY)
30 < #define  QT_IS_TREE(qt) ((qt) > EMPTY)
29 > #define  QT_IS_LEAF(qt)         ((qt) < EMPTY)
30 > #define  QT_IS_TREE(qt)         ((qt) > EMPTY)
31  
32 < #define  QT_INDEX(qt)          (-(qt)-2)        /* quadtree node from set */
33 < #define  QT_SET_INDEX(i)       (-((i)+2))       /* object set from node */
34 < #define  QT_BLOCK(qt)         ((qt)>>8)         /* quadtree block index */
35 < #define  QT_BLOCK_INDEX(qt)   (((qt)&0377)<<2)  /* quadtree index in block */
32 > #define  QT_INDEX(qt)           (-(qt)-2)       /* quadtree node from set */
33 > #define  QT_SET_INDEX(i)        (-((i)+2))      /* object set from node */
34 > #define  QT_BLOCK_SIZE          1024            /* quadtrees in block */
35 > #define  QT_BLOCK(qt)           ((qt)>>10)      /* quadtree block index */
36 > #define  QT_BLOCK_INDEX(qt)   (((qt)&0x3ff)<<2) /* quadtree index in block */
37  
38 +
39   #ifndef  QT_MAX_BLK
40   #ifdef  BIGMEM
41 < #define  QT_MAX_BLK     65535           /* maximum quadtree block */
41 > #define  QT_MAX_BLK     16383           /* maximum quadtree block */
42   #else
43 < #define  QT_MAX_BLK     8191            /* maximum quadtree block */
43 > #define  QT_MAX_BLK     2047            /* maximum quadtree block */
44   #endif
45   #endif
46  
47  
45 –
48   #define  QT_NTH_CHILD(qt,br) (quad_block[QT_BLOCK(qt)][QT_BLOCK_INDEX(qt)+br])
49 < #define  QT_NTH_CHILD_PTR(qt,br) \
50 <                    (&(quad_block[QT_BLOCK(qt)][QT_BLOCK_INDEX(qt)+br]))
51 < #define  QT_CLEAR_CHILDREN(qt) (QT_NTH_CHILD(qt,0)=EMPTY, \
50 < QT_NTH_CHILD(qt,1)=EMPTY,QT_NTH_CHILD(qt,2)=EMPTY,QT_NTH_CHILD(qt,3)=EMPTY)
49 > #define  QT_NTH_CHILD_PTR(qt,br) (&QT_NTH_CHILD(qt,br))
50 > #define  QT_CLEAR_CHILDREN(qt) (QT_NTH_CHILD(qt,0)=QT_NTH_CHILD(qt,1)= \
51 >                        QT_NTH_CHILD(qt,2)=QT_NTH_CHILD(qt,3)=EMPTY)
52  
53  
54 < #if 0
55 < #define  QT_EMPTY       0
56 < #define  QT_FULL        1
57 < #define  QT_TREE        2
58 < #endif
54 > /* QUADTREE NODE FLAGS */
55 > #define QT_IS_FLAG(qt)          IS_FLAG(quad_flag,qt)
56 > #define QT_SET_FLAG(qt)         SET_FLAG(quad_flag,qt)
57 > #define QT_CLR_FLAG(qt)         CLR_FLAG(quad_flag,qt)
58 > #define QT_LEAF_IS_FLAG(qt)     IS_FLAG(qtsetflag,QT_INDEX(qt))
59 > #define QT_LEAF_SET_FLAG(qt)    SET_FLAG(qtsetflag,QT_INDEX(qt))
60 > #define QT_LEAF_CLR_FLAG(qt)    CLR_FLAG(qtsetflag,QT_INDEX(qt))
61  
59 –
60 –
62   /* OBJECT SET CODE */
63   #define QT_SET_CNT(s)          ((s)[0])
64   #define QT_SET_NTH_ELEM(s,n)   ((s)[(n)])  
# Line 67 | Line 68 | QT_NTH_CHILD(qt,1)=EMPTY,QT_NTH_CHILD(qt,2)=EMPTY,QT_N
68   #define QT_SET_PTR(s)          (&((s)[1]))
69  
70  
71 < #define QT_MAX_SET        MAXSET
72 < #define MAXCSET           MAXSET*2
71 > #define QT_MAXSET        511
72 > #define MAXCSET          2*QT_MAXSET
73 > #define QT_MAXCSET       MAXCSET
74   #ifndef QT_SET_THRESHOLD
75 < #define QT_SET_THRESHOLD  30  
75 > #define QT_SET_THRESHOLD 30  
76   #endif
77  
78   #ifndef QT_MAX_LEVELS
79 < #define QT_MAX_LEVELS     17
79 > #define QT_MAX_LEVELS     12
80   #endif
81  
82 < #define QT_BLOCK_SIZE 256
82 > #define QT_FILL_THRESHOLD 2
83 > #define QT_EXPAND   8
84 > #define QT_COMPRESS 16
85 > #define QT_DONE 32
86 > #define QT_MODIFIED 64
87  
88 + #define QT_FLAG_FILL_TRI(f)  (((f)&0x7) == QT_FILL_THRESHOLD)
89 + #define QT_FLAG_UPDATE(f)    ((f)& (QT_EXPAND | QT_COMPRESS))
90 + #define QT_FLAG_IS_DONE(f)   ((f)& QT_DONE)
91 + #define QT_FLAG_SET_DONE(f)   ((f) |= QT_DONE)
92 + #define QT_FLAG_IS_MODIFIED(f)   ((f)& QT_MODIFIED)
93 + #define QT_FLAG_SET_MODIFIED(f)   ((f) |= QT_MODIFIED)
94 +
95 + #define qtSubdivide(qt) (qt = qtAlloc(),QT_CLEAR_CHILDREN(qt))
96 + #define qtSubdivide_tri(v0,v1,v2,a,b,c) (EDGE_MIDPOINT_VEC3(a,v0,v1), \
97 +                                         EDGE_MIDPOINT_VEC3(b,v1,v2), \
98 +                                         EDGE_MIDPOINT_VEC3(c,v2,v0))
99 +
100   extern QUADTREE  qtnewleaf(), qtaddelem(), qtdelelem();
101  
102   extern QUADTREE  *quad_block[QT_MAX_BLK];       /* quadtree blocks */
103 + extern int4  *quad_flag;                        /* zeroeth quadtree flag */
104 +
105 + extern OBJECT   **qtsettab;             /* quadtree leaf node table */
106 + extern QUADTREE  qtnumsets;             /* number of used set indices */
107 + extern int4   *qtsetflag;
108 + #ifdef DEBUG
109 + extern OBJECT   *qtqueryset();
110 + #else
111 + #define qtqueryset(qt)  (qtsettab[QT_SET_INDEX(qt)])
112 + #endif
113 +
114 + #define qtinset(qt,id)  inset(qtqueryset(qt),id)
115 + #define qtgetset(os,qt) setcopy(os,qtqueryset(qt))
116 +
117 + /*
118 + QUADTREE qtRoot_point_locate(qt,q0,q1,q2,peq,pt,r0,r1,r2)
119 +   QUADTREE qt;
120 +   FVECT q0,q1,q2;
121 +   FPEQ peq;
122 +   FVECT pt;
123 +   FVECT r0,r1,r2;
124 +
125 +   Return the quadtree node containing pt. It is assumed that pt is in
126 +   the root node qt with ws vertices q0,q1,q2 and plane equation peq.
127 +   If r0 != NULL will return coordinates of node in (r0,r1,r2).
128 + */
129 +
130 + extern QUADTREE qtRoot_point_locate();
131 + extern QUADTREE qtRoot_add_tri();
132 + extern QUADTREE qtRoot_remove_tri();
133 + extern QUADTREE qtAdd_tri();
134 + extern QUADTREE qtRoot_visit_tri_edges();
135 + extern QUADTREE qtRoot_trace_ray();

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines