src/hd/sm_qtree.h

/* RCSid: $Id$ */
/*
 *  sm_qtree.h - header file for routines using spherical quadtrees.
 *
 *    adapted from octree.h 
 */

/*
 *      An quadtree is expressed as an integer which is either
 *      an index to 4 other nodes, the empty tree, or an index
 *      to a set of objects.  If the quadtree has a value:
 *
 *              > -1:   it is an index to four other nodes.
 *
 *              -1:     it is empty
 *
 *              < -1:   it is an index to a set of objects
 */

typedef struct _FUNC {
    int (*func)();
    int (*func_after)();
    int *argptr;
}FUNC;

#define F_FUNC(f) (f.func)
#define F_FUNC2(f) (f.func_after)
#define F_ARGS(f) (f.argptr)
#define  QUADTREE               int

#define  EMPTY          (-1)

#define  QT_IS_EMPTY(qt)        ((qt) == EMPTY)
#define  QT_IS_LEAF(qt)         ((qt) < EMPTY)
#define  QT_IS_TREE(qt)         ((qt) > EMPTY)

#define  QT_INDEX(qt)           (-(qt)-2)       /* quadtree node from set */
#define  QT_SET_INDEX(i)        (-((i)+2))      /* object set from node */
#define  QT_BLOCK_SIZE          1024            /* quadtrees in block */
#define  QT_BLOCK(qt)           ((qt)>>10)      /* quadtree block index */
#define  QT_BLOCK_INDEX(qt)   (((qt)&0x3ff)<<2) /* quadtree index in block */


#ifndef  QT_MAX_BLK
#ifdef  SMLMEM
#define  QT_MAX_BLK     2047            /* maximum quadtree block */
#else
#define  QT_MAX_BLK     16383           /* maximum quadtree block */
#endif
#endif


#define  QT_NTH_CHILD(qt,br) (quad_block[QT_BLOCK(qt)][QT_BLOCK_INDEX(qt)+br])
#define  QT_NTH_CHILD_PTR(qt,br) (&QT_NTH_CHILD(qt,br))
#define  QT_CLEAR_CHILDREN(qt) (QT_NTH_CHILD(qt,0)=QT_NTH_CHILD(qt,1)= \
                        QT_NTH_CHILD(qt,2)=QT_NTH_CHILD(qt,3)=EMPTY)


/* QUADTREE NODE FLAGS */
#define QT_IS_FLAG(qt)          IS_FLAG(quad_flag,qt)
#define QT_SET_FLAG(qt)         SET_FLAG(quad_flag,qt)
#define QT_CLR_FLAG(qt)         CLR_FLAG(quad_flag,qt)
#define QT_LEAF_IS_FLAG(qt)     IS_FLAG(qtsetflag,QT_INDEX(qt))
#define QT_LEAF_SET_FLAG(qt)    SET_FLAG(qtsetflag,QT_INDEX(qt))
#define QT_LEAF_CLR_FLAG(qt)    CLR_FLAG(qtsetflag,QT_INDEX(qt))

/* OBJECT SET CODE */
#define QT_SET_CNT(s)          ((s)[0])
#define QT_SET_NTH_ELEM(s,n)   ((s)[(n)])   

#define QT_CLEAR_SET(s)        ((s)[0] = 0)
#define QT_SET_NEXT_ELEM(p)    (*(++p))
#define QT_SET_PTR(s)          (&((s)[1]))


#define QT_MAXSET        511
#define MAXCSET          2*QT_MAXSET
#define QT_MAXCSET       MAXCSET
#ifndef QT_SET_THRESHOLD
#define QT_SET_THRESHOLD 32  
#endif

#ifndef QT_MAX_LEVELS
#define QT_MAX_LEVELS     10
#endif

#define QT_FILL_THRESHOLD 2
#define QT_EXPAND   8
#define QT_COMPRESS 16
#define QT_DONE 32
#define QT_MODIFIED 64

#define QT_FLAG_FILL_TRI(f)  (((f)&0x7) == QT_FILL_THRESHOLD)
#define QT_FLAG_UPDATE(f)    ((f)& (QT_EXPAND | QT_COMPRESS))
#define QT_FLAG_IS_DONE(f)   ((f)& QT_DONE)
#define QT_FLAG_SET_DONE(f)   ((f) |= QT_DONE)
#define QT_FLAG_IS_MODIFIED(f)   ((f)& QT_MODIFIED)
#define QT_FLAG_SET_MODIFIED(f)   ((f) |= QT_MODIFIED)

#define qtSubdivide(qt) (qt = qtAlloc(),QT_CLEAR_CHILDREN(qt))
#define qtSubdivide_tri(v0,v1,v2,a,b,c) (EDGE_MIDPOINT(a,v1,v2), \
                                         EDGE_MIDPOINT(b,v2,v0), \
                                         EDGE_MIDPOINT(c,v0,v1))
 
extern QUADTREE  qtnewleaf(), qtaddelem(), qtdelelem();

extern QUADTREE  *quad_block[QT_MAX_BLK];       /* quadtree blocks */
extern int4  *quad_flag;                        /* zeroeth quadtree flag */

extern OBJECT   **qtsettab;             /* quadtree leaf node table */
extern QUADTREE  qtnumsets;             /* number of used set indices */
extern int4   *qtsetflag;
#ifdef DEBUG
extern OBJECT   *qtqueryset();
#else
#define qtqueryset(qt)  (qtsettab[QT_SET_INDEX(qt)])
#endif
#if 0
#define qtremovelast(qt) ((*(qtqueryset(qt)))--)
#endif
#define qtinset(qt,id)  inset(qtqueryset(qt),id)
#define qtgetset(os,qt) setcopy(os,qtqueryset(qt))


#define SIDES_GTR(b0,b1,b2,s0,s1,s2,a,b,c) \
    (s0 = ((b0[0] > a?4:0) | (b1[0] > a?2:0) | (b2[0] > a?1:0)), \
     s1 = ((b0[1] > b?4:0) | (b1[1] > b?2:0) | (b2[1] > b?1:0)), \
     s2 = ((b0[2] > c?4:0) | (b1[2] > c?2:0) | (b2[2] > c?1:0)))

#define SIDES_LESS(b0,b1,b2,s0,s1,s2,a,b,c) \
    (s0 = ((b0[0] < a?4:0) | (b1[0] < a?2:0) | (b2[0] < a?1:0)), \
     s1 = ((b0[1] < b?4:0) | (b1[1] < b?2:0) | (b2[1] < b?1:0)), \
     s2 = ((b0[2] < c?4:0) | (b1[2] < c?2:0) | (b2[2] < c?1:0)))

/* 
QUADTREE qtRoot_point_locate(qt,q0,q1,q2,peq,pt,r0,r1,r2)
   QUADTREE qt;
   FVECT q0,q1,q2;
   FPEQ peq;
   FVECT pt;
   FVECT r0,r1,r2;

   Return the quadtree node containing pt. It is assumed that pt is in
   the root node qt with ws vertices q0,q1,q2 and plane equation peq.
   If r0 != NULL will return coordinates of node in (r0,r1,r2). 
*/

extern QUADTREE qtRoot_point_locate();
extern QUADTREE qtRoot_add_tri();
extern QUADTREE qtRoot_remove_tri();
extern QUADTREE qtAdd_tri();
extern QUADTREE qtRoot_visit_tri_edges();
extern QUADTREE qtRoot_trace_ray();


Revision:	3.14
Committed:	Thu May 15 05:13:35 2003 UTC (20 years, 11 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 3.13:	+3 -3 lines
Log Message:	Eliminated -DBIGMEM define, since we always used it in makeall
#	User	Rev	Content
1	greg	3.13	/* RCSid: $Id$ */
2	gwlarson	3.1	/*
3			* sm_qtree.h - header file for routines using spherical quadtrees.
4			*
5			* adapted from octree.h
6			*/
7
8			/*
9			* An quadtree is expressed as an integer which is either
10			* an index to 4 other nodes, the empty tree, or an index
11			* to a set of objects. If the quadtree has a value:
12			*
13			* > -1: it is an index to four other nodes.
14			*
15			* -1: it is empty
16			*
17			* < -1: it is an index to a set of objects
18			*/
19	greg	3.13
20	gwlarson	3.9	typedef struct _FUNC {
21			int (*func)();
22	gwlarson	3.12	int (*func_after)();
23	gwlarson	3.9	int *argptr;
24			}FUNC;
25	gwlarson	3.1
26	gwlarson	3.9	#define F_FUNC(f) (f.func)
27	gwlarson	3.12	#define F_FUNC2(f) (f.func_after)
28	gwlarson	3.9	#define F_ARGS(f) (f.argptr)
29	gwlarson	3.1	#define QUADTREE int
30
31			#define EMPTY (-1)
32
33			#define QT_IS_EMPTY(qt) ((qt) == EMPTY)
34	gwlarson	3.3	#define QT_IS_LEAF(qt) ((qt) < EMPTY)
35			#define QT_IS_TREE(qt) ((qt) > EMPTY)
36	gwlarson	3.1
37	gwlarson	3.3	#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	gwlarson	3.1
43	gwlarson	3.4
44	gwlarson	3.1	#ifndef QT_MAX_BLK
45	greg	3.14	#ifdef SMLMEM
46			#define QT_MAX_BLK 2047 /* maximum quadtree block */
47			#else
48	gwlarson	3.3	#define QT_MAX_BLK 16383 /* maximum quadtree block */
49	gwlarson	3.1	#endif
50			#endif
51
52
53			#define QT_NTH_CHILD(qt,br) (quad_block[QT_BLOCK(qt)][QT_BLOCK_INDEX(qt)+br])
54	gwlarson	3.3	#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	gwlarson	3.1
58
59	gwlarson	3.3	/* QUADTREE NODE FLAGS */
60	gwlarson	3.7	#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	gwlarson	3.1
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	gwlarson	3.12	#define QT_SET_NEXT_ELEM(p) (*(++p))
73	gwlarson	3.1	#define QT_SET_PTR(s) (&((s)[1]))
74
75
76	gwlarson	3.6	#define QT_MAXSET 511
77	gwlarson	3.4	#define MAXCSET 2*QT_MAXSET
78			#define QT_MAXCSET MAXCSET
79	gwlarson	3.1	#ifndef QT_SET_THRESHOLD
80	gwlarson	3.12	#define QT_SET_THRESHOLD 32
81	gwlarson	3.1	#endif
82
83			#ifndef QT_MAX_LEVELS
84	gwlarson	3.9	#define QT_MAX_LEVELS 10
85	gwlarson	3.1	#endif
86
87	gwlarson	3.8	#define QT_FILL_THRESHOLD 2
88	gwlarson	3.4	#define QT_EXPAND 8
89			#define QT_COMPRESS 16
90	gwlarson	3.7	#define QT_DONE 32
91			#define QT_MODIFIED 64
92	gwlarson	3.4
93			#define QT_FLAG_FILL_TRI(f) (((f)&0x7) == QT_FILL_THRESHOLD)
94			#define QT_FLAG_UPDATE(f) ((f)& (QT_EXPAND \| QT_COMPRESS))
95	gwlarson	3.7	#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	gwlarson	3.4
100	gwlarson	3.7	#define qtSubdivide(qt) (qt = qtAlloc(),QT_CLEAR_CHILDREN(qt))
101	gwlarson	3.10	#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	gwlarson	3.7
105	gwlarson	3.1	extern QUADTREE qtnewleaf(), qtaddelem(), qtdelelem();
106
107			extern QUADTREE quad_block[QT_MAX_BLK]; / quadtree blocks */
108	gwlarson	3.3	extern int4 quad_flag; / zeroeth quadtree flag */
109	gwlarson	3.4
110			extern OBJECT *qtsettab; / quadtree leaf node table */
111			extern QUADTREE qtnumsets; /* number of used set indices */
112	gwlarson	3.7	extern int4 *qtsetflag;
113	gwlarson	3.4	#ifdef DEBUG
114			extern OBJECT *qtqueryset();
115			#else
116			#define qtqueryset(qt) (qtsettab[QT_SET_INDEX(qt)])
117			#endif
118	gwlarson	3.12	#if 0
119			#define qtremovelast(qt) ((*(qtqueryset(qt)))--)
120			#endif
121	gwlarson	3.4	#define qtinset(qt,id) inset(qtqueryset(qt),id)
122			#define qtgetset(os,qt) setcopy(os,qtqueryset(qt))
123	gwlarson	3.9
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	gwlarson	3.4
135	gwlarson	3.7	/*
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	gwlarson	3.12
155
156
157
158
159