src/hd/sm_qtree.h

/* RCSid: $Id: sm_qtree.h,v 3.15 2003/06/20 00:25:49 greg Exp $ */
/*
 *  sm_qtree.h - header file for routines using spherical quadtrees.
 *
 *    adapted from octree.h 
 */
#ifndef _RAD_CONE_H_
#define _RAD_CONE_H_

#ifdef __cplusplus
extern "C" {
#endif

/*
 *      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 int32  *quad_flag;                       /* zeroeth quadtree flag */

extern OBJECT   **qtsettab;             /* quadtree leaf node table */
extern QUADTREE  qtnumsets;             /* number of used set indices */
extern int32   *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();


#ifdef __cplusplus
}
#endif
#endif /* _RAD_CONE_H_ */

Revision:	3.16
Committed:	Mon Jul 14 22:24:00 2003 UTC (20 years, 9 months ago) by schorsch
Content type:	text/plain
Branch:	MAIN
Changes since 3.15:	+11 -4 lines
Log Message:	Instrumented headers against multiple inclusion and for use from C++. Moved includes in headers out of "C" scope.
#	User	Rev	Content
1	schorsch	3.16	/* RCSid: $Id: sm_qtree.h,v 3.15 2003/06/20 00:25:49 greg Exp $ */
2	gwlarson	3.1	/*
3			* sm_qtree.h - header file for routines using spherical quadtrees.
4			*
5			* adapted from octree.h
6			*/
7	schorsch	3.16	#ifndef _RAD_CONE_H_
8			#define _RAD_CONE_H_
9
10			#ifdef __cplusplus
11			extern "C" {
12			#endif
13	gwlarson	3.1
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
17			* to a set of objects. If the quadtree has a value:
18			*
19			* > -1: it is an index to four other nodes.
20			*
21			* -1: it is empty
22			*
23			* < -1: it is an index to a set of objects
24			*/
25	greg	3.13
26	gwlarson	3.9	typedef struct _FUNC {
27			int (*func)();
28	gwlarson	3.12	int (*func_after)();
29	gwlarson	3.9	int *argptr;
30			}FUNC;
31	gwlarson	3.1
32	gwlarson	3.9	#define F_FUNC(f) (f.func)
33	gwlarson	3.12	#define F_FUNC2(f) (f.func_after)
34	gwlarson	3.9	#define F_ARGS(f) (f.argptr)
35	gwlarson	3.1	#define QUADTREE int
36
37			#define EMPTY (-1)
38
39			#define QT_IS_EMPTY(qt) ((qt) == EMPTY)
40	gwlarson	3.3	#define QT_IS_LEAF(qt) ((qt) < EMPTY)
41			#define QT_IS_TREE(qt) ((qt) > EMPTY)
42	gwlarson	3.1
43	gwlarson	3.3	#define QT_INDEX(qt) (-(qt)-2) /* quadtree node from set */
44			#define QT_SET_INDEX(i) (-((i)+2)) /* object set from node */
45			#define QT_BLOCK_SIZE 1024 /* quadtrees in block */
46			#define QT_BLOCK(qt) ((qt)>>10) /* quadtree block index */
47			#define QT_BLOCK_INDEX(qt) (((qt)&0x3ff)<<2) /* quadtree index in block */
48	gwlarson	3.1
49	gwlarson	3.4
50	gwlarson	3.1	#ifndef QT_MAX_BLK
51	greg	3.14	#ifdef SMLMEM
52			#define QT_MAX_BLK 2047 /* maximum quadtree block */
53			#else
54	gwlarson	3.3	#define QT_MAX_BLK 16383 /* maximum quadtree block */
55	gwlarson	3.1	#endif
56			#endif
57
58
59			#define QT_NTH_CHILD(qt,br) (quad_block[QT_BLOCK(qt)][QT_BLOCK_INDEX(qt)+br])
60	gwlarson	3.3	#define QT_NTH_CHILD_PTR(qt,br) (&QT_NTH_CHILD(qt,br))
61			#define QT_CLEAR_CHILDREN(qt) (QT_NTH_CHILD(qt,0)=QT_NTH_CHILD(qt,1)= \
62			QT_NTH_CHILD(qt,2)=QT_NTH_CHILD(qt,3)=EMPTY)
63	gwlarson	3.1
64
65	gwlarson	3.3	/* QUADTREE NODE FLAGS */
66	gwlarson	3.7	#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	gwlarson	3.1
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	gwlarson	3.12	#define QT_SET_NEXT_ELEM(p) (*(++p))
79	gwlarson	3.1	#define QT_SET_PTR(s) (&((s)[1]))
80
81
82	gwlarson	3.6	#define QT_MAXSET 511
83	gwlarson	3.4	#define MAXCSET 2*QT_MAXSET
84			#define QT_MAXCSET MAXCSET
85	gwlarson	3.1	#ifndef QT_SET_THRESHOLD
86	gwlarson	3.12	#define QT_SET_THRESHOLD 32
87	gwlarson	3.1	#endif
88
89			#ifndef QT_MAX_LEVELS
90	gwlarson	3.9	#define QT_MAX_LEVELS 10
91	gwlarson	3.1	#endif
92
93	gwlarson	3.8	#define QT_FILL_THRESHOLD 2
94	gwlarson	3.4	#define QT_EXPAND 8
95			#define QT_COMPRESS 16
96	gwlarson	3.7	#define QT_DONE 32
97			#define QT_MODIFIED 64
98	gwlarson	3.4
99			#define QT_FLAG_FILL_TRI(f) (((f)&0x7) == QT_FILL_THRESHOLD)
100			#define QT_FLAG_UPDATE(f) ((f)& (QT_EXPAND \| QT_COMPRESS))
101	gwlarson	3.7	#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	gwlarson	3.4
106	gwlarson	3.7	#define qtSubdivide(qt) (qt = qtAlloc(),QT_CLEAR_CHILDREN(qt))
107	gwlarson	3.10	#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	gwlarson	3.7
111	gwlarson	3.1	extern QUADTREE qtnewleaf(), qtaddelem(), qtdelelem();
112
113			extern QUADTREE quad_block[QT_MAX_BLK]; / quadtree blocks */
114	greg	3.15	extern int32 quad_flag; / zeroeth quadtree flag */
115	gwlarson	3.4
116			extern OBJECT *qtsettab; / quadtree leaf node table */
117			extern QUADTREE qtnumsets; /* number of used set indices */
118	greg	3.15	extern int32 *qtsetflag;
119	gwlarson	3.4	#ifdef DEBUG
120			extern OBJECT *qtqueryset();
121			#else
122			#define qtqueryset(qt) (qtsettab[QT_SET_INDEX(qt)])
123			#endif
124	gwlarson	3.12	#if 0
125			#define qtremovelast(qt) ((*(qtqueryset(qt)))--)
126			#endif
127	gwlarson	3.4	#define qtinset(qt,id) inset(qtqueryset(qt),id)
128			#define qtgetset(os,qt) setcopy(os,qtqueryset(qt))
129	gwlarson	3.9
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	gwlarson	3.4
141	gwlarson	3.7	/*
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	gwlarson	3.12
161
162	schorsch	3.16	#ifdef __cplusplus
163			}
164			#endif
165			#endif /* _RAD_CONE_H_ */
166	gwlarson	3.12