src/hd/sm_qtree.h

/* Copyright (c) 1998 Silicon Graphics, Inc. */

/* SCCSid "$SunId$ SGI" */

/*
 *  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
 */
#include "object.h"
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  BIGMEM
#define  QT_MAX_BLK     16383           /* maximum quadtree block */
#else
#define  QT_MAX_BLK     2047            /* 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.12
Committed:	Thu Jun 10 15:22:24 1999 UTC (24 years, 10 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.11:	+13 -3 lines
Log Message:	Implemented sample quadtree in place of triangle quadtree Made geometric predicates more robust Added #define LORES which utilizes a single precision floating point sample array, the default is a double sample array Added topology DEBUG commands (for DEBUG > 1) Made code optimizations
#	User	Rev	Content
1	gwlarson	3.1	/* Copyright (c) 1998 Silicon Graphics, Inc. */
2
3			/* SCCSid "$SunId$ SGI" */
4
5			/*
6			* sm_qtree.h - header file for routines using spherical quadtrees.
7			*
8			* adapted from octree.h
9			*/
10
11			/*
12			* An quadtree is expressed as an integer which is either
13			* an index to 4 other nodes, the empty tree, or an index
14			* to a set of objects. If the quadtree has a value:
15			*
16			* > -1: it is an index to four other nodes.
17			*
18			* -1: it is empty
19			*
20			* < -1: it is an index to a set of objects
21			*/
22	gwlarson	3.4	#include "object.h"
23	gwlarson	3.9	typedef struct _FUNC {
24			int (*func)();
25	gwlarson	3.12	int (*func_after)();
26	gwlarson	3.9	int *argptr;
27			}FUNC;
28	gwlarson	3.1
29	gwlarson	3.9	#define F_FUNC(f) (f.func)
30	gwlarson	3.12	#define F_FUNC2(f) (f.func_after)
31	gwlarson	3.9	#define F_ARGS(f) (f.argptr)
32	gwlarson	3.1	#define QUADTREE int
33
34			#define EMPTY (-1)
35
36			#define QT_IS_EMPTY(qt) ((qt) == EMPTY)
37	gwlarson	3.3	#define QT_IS_LEAF(qt) ((qt) < EMPTY)
38			#define QT_IS_TREE(qt) ((qt) > EMPTY)
39	gwlarson	3.1
40	gwlarson	3.3	#define QT_INDEX(qt) (-(qt)-2) /* quadtree node from set */
41			#define QT_SET_INDEX(i) (-((i)+2)) /* object set from node */
42			#define QT_BLOCK_SIZE 1024 /* quadtrees in block */
43			#define QT_BLOCK(qt) ((qt)>>10) /* quadtree block index */
44			#define QT_BLOCK_INDEX(qt) (((qt)&0x3ff)<<2) /* quadtree index in block */
45	gwlarson	3.1
46	gwlarson	3.4
47	gwlarson	3.1	#ifndef QT_MAX_BLK
48			#ifdef BIGMEM
49	gwlarson	3.3	#define QT_MAX_BLK 16383 /* maximum quadtree block */
50	gwlarson	3.1	#else
51	gwlarson	3.3	#define QT_MAX_BLK 2047 /* maximum quadtree block */
52	gwlarson	3.1	#endif
53			#endif
54
55
56			#define QT_NTH_CHILD(qt,br) (quad_block[QT_BLOCK(qt)][QT_BLOCK_INDEX(qt)+br])
57	gwlarson	3.3	#define QT_NTH_CHILD_PTR(qt,br) (&QT_NTH_CHILD(qt,br))
58			#define QT_CLEAR_CHILDREN(qt) (QT_NTH_CHILD(qt,0)=QT_NTH_CHILD(qt,1)= \
59			QT_NTH_CHILD(qt,2)=QT_NTH_CHILD(qt,3)=EMPTY)
60	gwlarson	3.1
61
62	gwlarson	3.3	/* QUADTREE NODE FLAGS */
63	gwlarson	3.7	#define QT_IS_FLAG(qt) IS_FLAG(quad_flag,qt)
64			#define QT_SET_FLAG(qt) SET_FLAG(quad_flag,qt)
65			#define QT_CLR_FLAG(qt) CLR_FLAG(quad_flag,qt)
66			#define QT_LEAF_IS_FLAG(qt) IS_FLAG(qtsetflag,QT_INDEX(qt))
67			#define QT_LEAF_SET_FLAG(qt) SET_FLAG(qtsetflag,QT_INDEX(qt))
68			#define QT_LEAF_CLR_FLAG(qt) CLR_FLAG(qtsetflag,QT_INDEX(qt))
69	gwlarson	3.1
70			/* OBJECT SET CODE */
71			#define QT_SET_CNT(s) ((s)[0])
72			#define QT_SET_NTH_ELEM(s,n) ((s)[(n)])
73
74			#define QT_CLEAR_SET(s) ((s)[0] = 0)
75	gwlarson	3.12	#define QT_SET_NEXT_ELEM(p) (*(++p))
76	gwlarson	3.1	#define QT_SET_PTR(s) (&((s)[1]))
77
78
79	gwlarson	3.6	#define QT_MAXSET 511
80	gwlarson	3.4	#define MAXCSET 2*QT_MAXSET
81			#define QT_MAXCSET MAXCSET
82	gwlarson	3.1	#ifndef QT_SET_THRESHOLD
83	gwlarson	3.12	#define QT_SET_THRESHOLD 32
84	gwlarson	3.1	#endif
85
86			#ifndef QT_MAX_LEVELS
87	gwlarson	3.9	#define QT_MAX_LEVELS 10
88	gwlarson	3.1	#endif
89
90	gwlarson	3.8	#define QT_FILL_THRESHOLD 2
91	gwlarson	3.4	#define QT_EXPAND 8
92			#define QT_COMPRESS 16
93	gwlarson	3.7	#define QT_DONE 32
94			#define QT_MODIFIED 64
95	gwlarson	3.4
96			#define QT_FLAG_FILL_TRI(f) (((f)&0x7) == QT_FILL_THRESHOLD)
97			#define QT_FLAG_UPDATE(f) ((f)& (QT_EXPAND \| QT_COMPRESS))
98	gwlarson	3.7	#define QT_FLAG_IS_DONE(f) ((f)& QT_DONE)
99			#define QT_FLAG_SET_DONE(f) ((f) \|= QT_DONE)
100			#define QT_FLAG_IS_MODIFIED(f) ((f)& QT_MODIFIED)
101			#define QT_FLAG_SET_MODIFIED(f) ((f) \|= QT_MODIFIED)
102	gwlarson	3.4
103	gwlarson	3.7	#define qtSubdivide(qt) (qt = qtAlloc(),QT_CLEAR_CHILDREN(qt))
104	gwlarson	3.10	#define qtSubdivide_tri(v0,v1,v2,a,b,c) (EDGE_MIDPOINT(a,v1,v2), \
105			EDGE_MIDPOINT(b,v2,v0), \
106			EDGE_MIDPOINT(c,v0,v1))
107	gwlarson	3.7
108	gwlarson	3.1	extern QUADTREE qtnewleaf(), qtaddelem(), qtdelelem();
109
110			extern QUADTREE quad_block[QT_MAX_BLK]; / quadtree blocks */
111	gwlarson	3.3	extern int4 quad_flag; / zeroeth quadtree flag */
112	gwlarson	3.4
113			extern OBJECT *qtsettab; / quadtree leaf node table */
114			extern QUADTREE qtnumsets; /* number of used set indices */
115	gwlarson	3.7	extern int4 *qtsetflag;
116	gwlarson	3.4	#ifdef DEBUG
117			extern OBJECT *qtqueryset();
118			#else
119			#define qtqueryset(qt) (qtsettab[QT_SET_INDEX(qt)])
120			#endif
121	gwlarson	3.12	#if 0
122			#define qtremovelast(qt) ((*(qtqueryset(qt)))--)
123			#endif
124	gwlarson	3.4	#define qtinset(qt,id) inset(qtqueryset(qt),id)
125			#define qtgetset(os,qt) setcopy(os,qtqueryset(qt))
126	gwlarson	3.9
127
128			#define SIDES_GTR(b0,b1,b2,s0,s1,s2,a,b,c) \
129			(s0 = ((b0[0] > a?4:0) \| (b1[0] > a?2:0) \| (b2[0] > a?1:0)), \
130			s1 = ((b0[1] > b?4:0) \| (b1[1] > b?2:0) \| (b2[1] > b?1:0)), \
131			s2 = ((b0[2] > c?4:0) \| (b1[2] > c?2:0) \| (b2[2] > c?1:0)))
132
133			#define SIDES_LESS(b0,b1,b2,s0,s1,s2,a,b,c) \
134			(s0 = ((b0[0] < a?4:0) \| (b1[0] < a?2:0) \| (b2[0] < a?1:0)), \
135			s1 = ((b0[1] < b?4:0) \| (b1[1] < b?2:0) \| (b2[1] < b?1:0)), \
136			s2 = ((b0[2] < c?4:0) \| (b1[2] < c?2:0) \| (b2[2] < c?1:0)))
137	gwlarson	3.4
138	gwlarson	3.7	/*
139			QUADTREE qtRoot_point_locate(qt,q0,q1,q2,peq,pt,r0,r1,r2)
140			QUADTREE qt;
141			FVECT q0,q1,q2;
142			FPEQ peq;
143			FVECT pt;
144			FVECT r0,r1,r2;
145
146			Return the quadtree node containing pt. It is assumed that pt is in
147			the root node qt with ws vertices q0,q1,q2 and plane equation peq.
148			If r0 != NULL will return coordinates of node in (r0,r1,r2).
149			*/
150
151			extern QUADTREE qtRoot_point_locate();
152			extern QUADTREE qtRoot_add_tri();
153			extern QUADTREE qtRoot_remove_tri();
154			extern QUADTREE qtAdd_tri();
155			extern QUADTREE qtRoot_visit_tri_edges();
156			extern QUADTREE qtRoot_trace_ray();
157	gwlarson	3.12
158
159
160
161
162