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.6 by gwlarson, Wed Sep 16 18:16:29 1998 UTC vs.
Revision 3.17 by schorsch, Sat Aug 30 08:17:32 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   *
5   *    adapted from octree.h
6   */
7 + #ifndef _RAD_SM_QTREE_H_
8 + #define _RAD_SM_QTREE_H_
9  
10 + #ifdef __cplusplus
11 + extern "C" {
12 + #endif
13 +
14   /*
15   *      An quadtree is expressed as an integer which is either
16   *      an index to 4 other nodes, the empty tree, or an index
# Line 19 | Line 22
22   *
23   *              < -1:   it is an index to a set of objects
24   */
22 – #include "object.h"
25  
26 + typedef struct _FUNC {
27 +    int (*func)();
28 +    int (*func_after)();
29 +    int *argptr;
30 + }FUNC;
31 +
32 + #define F_FUNC(f) (f.func)
33 + #define F_FUNC2(f) (f.func_after)
34 + #define F_ARGS(f) (f.argptr)
35   #define  QUADTREE               int
36  
37   #define  EMPTY          (-1)
# Line 37 | Line 48
48  
49  
50   #ifndef  QT_MAX_BLK
51 < #ifdef  BIGMEM
41 < #define  QT_MAX_BLK     16383           /* maximum quadtree block */
42 < #else
51 > #ifdef  SMLMEM
52   #define  QT_MAX_BLK     2047            /* maximum quadtree block */
53 + #else
54 + #define  QT_MAX_BLK     16383           /* maximum quadtree block */
55   #endif
56   #endif
57  
# Line 52 | Line 63
63  
64  
65   /* QUADTREE NODE FLAGS */
66 < #define QT_OFFSET(qt)           ((qt)>>5)
67 < #define QT_F_BIT(qt)            ((qt)&0x1f)
68 < #define QT_F_OP(f,qt,op)        ((f)[QT_OFFSET(qt)] op (0x1<<QT_F_BIT(qt)))
69 < #define QT_IS_FLAG(qt)          QT_F_OP(quad_flag,qt,&)
70 < #define QT_SET_FLAG(qt)         QT_F_OP(quad_flag,qt,|=)
71 < #define QT_CLR_FLAG(qt)         QT_F_OP(quad_flag,qt,|=~)
66 > #define QT_IS_FLAG(qt)          IS_FLAG(quad_flag,qt)
67 > #define QT_SET_FLAG(qt)         SET_FLAG(quad_flag,qt)
68 > #define QT_CLR_FLAG(qt)         CLR_FLAG(quad_flag,qt)
69 > #define QT_LEAF_IS_FLAG(qt)     IS_FLAG(qtsetflag,QT_INDEX(qt))
70 > #define QT_LEAF_SET_FLAG(qt)    SET_FLAG(qtsetflag,QT_INDEX(qt))
71 > #define QT_LEAF_CLR_FLAG(qt)    CLR_FLAG(qtsetflag,QT_INDEX(qt))
72  
62 –
73   /* OBJECT SET CODE */
74   #define QT_SET_CNT(s)          ((s)[0])
75   #define QT_SET_NTH_ELEM(s,n)   ((s)[(n)])  
76  
77   #define QT_CLEAR_SET(s)        ((s)[0] = 0)
78 < #define QT_SET_NEXT_ELEM(p)    (*(p)++)
78 > #define QT_SET_NEXT_ELEM(p)    (*(++p))
79   #define QT_SET_PTR(s)          (&((s)[1]))
80  
81  
# Line 73 | Line 83
83   #define MAXCSET          2*QT_MAXSET
84   #define QT_MAXCSET       MAXCSET
85   #ifndef QT_SET_THRESHOLD
86 < #define QT_SET_THRESHOLD  100  
86 > #define QT_SET_THRESHOLD 32  
87   #endif
88  
89   #ifndef QT_MAX_LEVELS
90 < #define QT_MAX_LEVELS     12
90 > #define QT_MAX_LEVELS     10
91   #endif
92  
93 < #define QT_HIT  -2
84 < #define QT_DONE -4
85 < #define QT_MODIFIED -8
86 <
87 < #define QT_FILL_THRESHOLD 3
93 > #define QT_FILL_THRESHOLD 2
94   #define QT_EXPAND   8
95   #define QT_COMPRESS 16
96 + #define QT_DONE 32
97 + #define QT_MODIFIED 64
98  
99   #define QT_FLAG_FILL_TRI(f)  (((f)&0x7) == QT_FILL_THRESHOLD)
100   #define QT_FLAG_UPDATE(f)    ((f)& (QT_EXPAND | QT_COMPRESS))
101 + #define QT_FLAG_IS_DONE(f)   ((f)& QT_DONE)
102 + #define QT_FLAG_SET_DONE(f)   ((f) |= QT_DONE)
103 + #define QT_FLAG_IS_MODIFIED(f)   ((f)& QT_MODIFIED)
104 + #define QT_FLAG_SET_MODIFIED(f)   ((f) |= QT_MODIFIED)
105  
106 + #define qtSubdivide(qt) (qt = qtAlloc(),QT_CLEAR_CHILDREN(qt))
107 + #define qtSubdivide_tri(v0,v1,v2,a,b,c) (EDGE_MIDPOINT(a,v1,v2), \
108 +                                         EDGE_MIDPOINT(b,v2,v0), \
109 +                                         EDGE_MIDPOINT(c,v0,v1))
110 +
111   extern QUADTREE  qtnewleaf(), qtaddelem(), qtdelelem();
112  
113   extern QUADTREE  *quad_block[QT_MAX_BLK];       /* quadtree blocks */
114 < extern int4  *quad_flag;                        /* zeroeth quadtree flag */
114 > extern int32  *quad_flag;                       /* zeroeth quadtree flag */
115  
116   extern OBJECT   **qtsettab;             /* quadtree leaf node table */
117   extern QUADTREE  qtnumsets;             /* number of used set indices */
118 <
118 > extern int32   *qtsetflag;
119   #ifdef DEBUG
120   extern OBJECT   *qtqueryset();
121   #else
122   #define qtqueryset(qt)  (qtsettab[QT_SET_INDEX(qt)])
123   #endif
124 <
124 > #if 0
125 > #define qtremovelast(qt) ((*(qtqueryset(qt)))--)
126 > #endif
127   #define qtinset(qt,id)  inset(qtqueryset(qt),id)
128   #define qtgetset(os,qt) setcopy(os,qtqueryset(qt))
129  
130 < extern QUADTREE *qtRoot_point_locate();
130 >
131 > #define SIDES_GTR(b0,b1,b2,s0,s1,s2,a,b,c) \
132 >    (s0 = ((b0[0] > a?4:0) | (b1[0] > a?2:0) | (b2[0] > a?1:0)), \
133 >     s1 = ((b0[1] > b?4:0) | (b1[1] > b?2:0) | (b2[1] > b?1:0)), \
134 >     s2 = ((b0[2] > c?4:0) | (b1[2] > c?2:0) | (b2[2] > c?1:0)))
135 >
136 > #define SIDES_LESS(b0,b1,b2,s0,s1,s2,a,b,c) \
137 >    (s0 = ((b0[0] < a?4:0) | (b1[0] < a?2:0) | (b2[0] < a?1:0)), \
138 >     s1 = ((b0[1] < b?4:0) | (b1[1] < b?2:0) | (b2[1] < b?1:0)), \
139 >     s2 = ((b0[2] < c?4:0) | (b1[2] < c?2:0) | (b2[2] < c?1:0)))
140 >
141 > /*
142 > QUADTREE qtRoot_point_locate(qt,q0,q1,q2,peq,pt,r0,r1,r2)
143 >   QUADTREE qt;
144 >   FVECT q0,q1,q2;
145 >   FPEQ peq;
146 >   FVECT pt;
147 >   FVECT r0,r1,r2;
148 >
149 >   Return the quadtree node containing pt. It is assumed that pt is in
150 >   the root node qt with ws vertices q0,q1,q2 and plane equation peq.
151 >   If r0 != NULL will return coordinates of node in (r0,r1,r2).
152 > */
153 >
154 > extern QUADTREE qtRoot_point_locate();
155 > extern QUADTREE qtRoot_add_tri();
156 > extern QUADTREE qtRoot_remove_tri();
157 > extern QUADTREE qtAdd_tri();
158 > extern QUADTREE qtRoot_visit_tri_edges();
159 > extern QUADTREE qtRoot_trace_ray();
160 >
161 >
162 > #ifdef __cplusplus
163 > }
164 > #endif
165 > #endif /* _RAD_SM_QTREE_H_ */
166 >

Diff Legend

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