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.1 by gwlarson, Wed Aug 19 17:45:24 1998 UTC vs.
Revision 3.15 by greg, Fri Jun 20 00:25:49 2003 UTC

# Line 1 | Line 1
1 < /* Copyright (c) 1998 Silicon Graphics, Inc. */
2 <
3 < /* SCCSid "$SunId$ SGI" */
4 <
1 > /* RCSid: $Id$ */
2   /*
3   *  sm_qtree.h - header file for routines using spherical quadtrees.
4   *
# Line 20 | Line 17
17   *              < -1:   it is an index to a set of objects
18   */
19  
20 + typedef struct _FUNC {
21 +    int (*func)();
22 +    int (*func_after)();
23 +    int *argptr;
24 + }FUNC;
25 +
26 + #define F_FUNC(f) (f.func)
27 + #define F_FUNC2(f) (f.func_after)
28 + #define F_ARGS(f) (f.argptr)
29   #define  QUADTREE               int
30  
31   #define  EMPTY          (-1)
32  
33   #define  QT_IS_EMPTY(qt)        ((qt) == EMPTY)
34 < #define  QT_IS_LEAF(qt) ((qt) < EMPTY)
35 < #define  QT_IS_TREE(qt) ((qt) > EMPTY)
34 > #define  QT_IS_LEAF(qt)         ((qt) < EMPTY)
35 > #define  QT_IS_TREE(qt)         ((qt) > EMPTY)
36  
37 < #define  QT_INDEX(qt)          (-(qt)-2)        /* quadtree node from set */
38 < #define  QT_SET_INDEX(i)       (-((i)+2))       /* object set from node */
39 < #define  QT_BLOCK(qt)         ((qt)>>8)         /* quadtree block index */
40 < #define  QT_BLOCK_INDEX(qt)   (((qt)&0377)<<2)  /* quadtree index in block */
37 > #define  QT_INDEX(qt)           (-(qt)-2)       /* quadtree node from set */
38 > #define  QT_SET_INDEX(i)        (-((i)+2))      /* object set from node */
39 > #define  QT_BLOCK_SIZE          1024            /* quadtrees in block */
40 > #define  QT_BLOCK(qt)           ((qt)>>10)      /* quadtree block index */
41 > #define  QT_BLOCK_INDEX(qt)   (((qt)&0x3ff)<<2) /* quadtree index in block */
42  
43 +
44   #ifndef  QT_MAX_BLK
45 < #ifdef  BIGMEM
46 < #define  QT_MAX_BLK     65535           /* maximum quadtree block */
45 > #ifdef  SMLMEM
46 > #define  QT_MAX_BLK     2047            /* maximum quadtree block */
47   #else
48 < #define  QT_MAX_BLK     8191            /* maximum quadtree block */
48 > #define  QT_MAX_BLK     16383           /* maximum quadtree block */
49   #endif
50   #endif
51  
52  
45 –
53   #define  QT_NTH_CHILD(qt,br) (quad_block[QT_BLOCK(qt)][QT_BLOCK_INDEX(qt)+br])
54 < #define  QT_NTH_CHILD_PTR(qt,br) \
55 <                    (&(quad_block[QT_BLOCK(qt)][QT_BLOCK_INDEX(qt)+br]))
56 < #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)
54 > #define  QT_NTH_CHILD_PTR(qt,br) (&QT_NTH_CHILD(qt,br))
55 > #define  QT_CLEAR_CHILDREN(qt) (QT_NTH_CHILD(qt,0)=QT_NTH_CHILD(qt,1)= \
56 >                        QT_NTH_CHILD(qt,2)=QT_NTH_CHILD(qt,3)=EMPTY)
57  
58  
59 < #if 0
60 < #define  QT_EMPTY       0
61 < #define  QT_FULL        1
62 < #define  QT_TREE        2
63 < #endif
59 > /* QUADTREE NODE FLAGS */
60 > #define QT_IS_FLAG(qt)          IS_FLAG(quad_flag,qt)
61 > #define QT_SET_FLAG(qt)         SET_FLAG(quad_flag,qt)
62 > #define QT_CLR_FLAG(qt)         CLR_FLAG(quad_flag,qt)
63 > #define QT_LEAF_IS_FLAG(qt)     IS_FLAG(qtsetflag,QT_INDEX(qt))
64 > #define QT_LEAF_SET_FLAG(qt)    SET_FLAG(qtsetflag,QT_INDEX(qt))
65 > #define QT_LEAF_CLR_FLAG(qt)    CLR_FLAG(qtsetflag,QT_INDEX(qt))
66  
59 –
60 –
67   /* OBJECT SET CODE */
68   #define QT_SET_CNT(s)          ((s)[0])
69   #define QT_SET_NTH_ELEM(s,n)   ((s)[(n)])  
70  
71   #define QT_CLEAR_SET(s)        ((s)[0] = 0)
72 < #define QT_SET_NEXT_ELEM(p)    (*(p)++)
72 > #define QT_SET_NEXT_ELEM(p)    (*(++p))
73   #define QT_SET_PTR(s)          (&((s)[1]))
74  
75  
76 < #define QT_MAX_SET        MAXSET
77 < #define MAXCSET           MAXSET*2
76 > #define QT_MAXSET        511
77 > #define MAXCSET          2*QT_MAXSET
78 > #define QT_MAXCSET       MAXCSET
79   #ifndef QT_SET_THRESHOLD
80 < #define QT_SET_THRESHOLD  40  
80 > #define QT_SET_THRESHOLD 32  
81   #endif
82  
83   #ifndef QT_MAX_LEVELS
84 < #define QT_MAX_LEVELS     16
84 > #define QT_MAX_LEVELS     10
85   #endif
86  
87 < #define QT_BLOCK_SIZE 256
87 > #define QT_FILL_THRESHOLD 2
88 > #define QT_EXPAND   8
89 > #define QT_COMPRESS 16
90 > #define QT_DONE 32
91 > #define QT_MODIFIED 64
92  
93 + #define QT_FLAG_FILL_TRI(f)  (((f)&0x7) == QT_FILL_THRESHOLD)
94 + #define QT_FLAG_UPDATE(f)    ((f)& (QT_EXPAND | QT_COMPRESS))
95 + #define QT_FLAG_IS_DONE(f)   ((f)& QT_DONE)
96 + #define QT_FLAG_SET_DONE(f)   ((f) |= QT_DONE)
97 + #define QT_FLAG_IS_MODIFIED(f)   ((f)& QT_MODIFIED)
98 + #define QT_FLAG_SET_MODIFIED(f)   ((f) |= QT_MODIFIED)
99 +
100 + #define qtSubdivide(qt) (qt = qtAlloc(),QT_CLEAR_CHILDREN(qt))
101 + #define qtSubdivide_tri(v0,v1,v2,a,b,c) (EDGE_MIDPOINT(a,v1,v2), \
102 +                                         EDGE_MIDPOINT(b,v2,v0), \
103 +                                         EDGE_MIDPOINT(c,v0,v1))
104 +
105   extern QUADTREE  qtnewleaf(), qtaddelem(), qtdelelem();
106  
107   extern QUADTREE  *quad_block[QT_MAX_BLK];       /* quadtree blocks */
108 + extern int32  *quad_flag;                       /* zeroeth quadtree flag */
109 +
110 + extern OBJECT   **qtsettab;             /* quadtree leaf node table */
111 + extern QUADTREE  qtnumsets;             /* number of used set indices */
112 + extern int32   *qtsetflag;
113 + #ifdef DEBUG
114 + extern OBJECT   *qtqueryset();
115 + #else
116 + #define qtqueryset(qt)  (qtsettab[QT_SET_INDEX(qt)])
117 + #endif
118 + #if 0
119 + #define qtremovelast(qt) ((*(qtqueryset(qt)))--)
120 + #endif
121 + #define qtinset(qt,id)  inset(qtqueryset(qt),id)
122 + #define qtgetset(os,qt) setcopy(os,qtqueryset(qt))
123 +
124 +
125 + #define SIDES_GTR(b0,b1,b2,s0,s1,s2,a,b,c) \
126 +    (s0 = ((b0[0] > a?4:0) | (b1[0] > a?2:0) | (b2[0] > a?1:0)), \
127 +     s1 = ((b0[1] > b?4:0) | (b1[1] > b?2:0) | (b2[1] > b?1:0)), \
128 +     s2 = ((b0[2] > c?4:0) | (b1[2] > c?2:0) | (b2[2] > c?1:0)))
129 +
130 + #define SIDES_LESS(b0,b1,b2,s0,s1,s2,a,b,c) \
131 +    (s0 = ((b0[0] < a?4:0) | (b1[0] < a?2:0) | (b2[0] < a?1:0)), \
132 +     s1 = ((b0[1] < b?4:0) | (b1[1] < b?2:0) | (b2[1] < b?1:0)), \
133 +     s2 = ((b0[2] < c?4:0) | (b1[2] < c?2:0) | (b2[2] < c?1:0)))
134 +
135 + /*
136 + QUADTREE qtRoot_point_locate(qt,q0,q1,q2,peq,pt,r0,r1,r2)
137 +   QUADTREE qt;
138 +   FVECT q0,q1,q2;
139 +   FPEQ peq;
140 +   FVECT pt;
141 +   FVECT r0,r1,r2;
142 +
143 +   Return the quadtree node containing pt. It is assumed that pt is in
144 +   the root node qt with ws vertices q0,q1,q2 and plane equation peq.
145 +   If r0 != NULL will return coordinates of node in (r0,r1,r2).
146 + */
147 +
148 + extern QUADTREE qtRoot_point_locate();
149 + extern QUADTREE qtRoot_add_tri();
150 + extern QUADTREE qtRoot_remove_tri();
151 + extern QUADTREE qtAdd_tri();
152 + extern QUADTREE qtRoot_visit_tri_edges();
153 + extern QUADTREE qtRoot_trace_ray();
154 +
155 +
156 +
157 +
158 +
159 +

Diff Legend

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