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 *argptr;
}FUNC;

#define F_FUNC(f) (f.func)
#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 64  
#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,v0,v1), \
                                         EDGE_MIDPOINT(b,v1,v2), \
                                         EDGE_MIDPOINT(c,v2,v0))
 
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

#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.9
Committed:	Mon Dec 28 18:07:36 1998 UTC (26 years, 10 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.8:	+22 -5 lines
Log Message:	New insertion routine New Culling routine based on insertion algorithm Adapted old insertion code: now used by picking Point location code returns on-vertex,on-edge, or in-triangle Added on_edge case for subdivision Implemented unordered sets Removed deletion from quadtree- added set compression to replace functionality
#	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			int *argptr;
26			}FUNC;
27	gwlarson	3.1
28	gwlarson	3.9	#define F_FUNC(f) (f.func)
29			#define F_ARGS(f) (f.argptr)
30	gwlarson	3.1	#define QUADTREE int
31
32			#define EMPTY (-1)
33
34			#define QT_IS_EMPTY(qt) ((qt) == EMPTY)
35	gwlarson	3.3	#define QT_IS_LEAF(qt) ((qt) < EMPTY)
36			#define QT_IS_TREE(qt) ((qt) > EMPTY)
37	gwlarson	3.1
38	gwlarson	3.3	#define QT_INDEX(qt) (-(qt)-2) /* quadtree node from set */
39			#define QT_SET_INDEX(i) (-((i)+2)) /* object set from node */
40			#define QT_BLOCK_SIZE 1024 /* quadtrees in block */
41			#define QT_BLOCK(qt) ((qt)>>10) /* quadtree block index */
42			#define QT_BLOCK_INDEX(qt) (((qt)&0x3ff)<<2) /* quadtree index in block */
43	gwlarson	3.1
44	gwlarson	3.4
45	gwlarson	3.1	#ifndef QT_MAX_BLK
46			#ifdef BIGMEM
47	gwlarson	3.3	#define QT_MAX_BLK 16383 /* maximum quadtree block */
48	gwlarson	3.1	#else
49	gwlarson	3.3	#define QT_MAX_BLK 2047 /* maximum quadtree block */
50	gwlarson	3.1	#endif
51			#endif
52
53
54			#define QT_NTH_CHILD(qt,br) (quad_block[QT_BLOCK(qt)][QT_BLOCK_INDEX(qt)+br])
55	gwlarson	3.3	#define QT_NTH_CHILD_PTR(qt,br) (&QT_NTH_CHILD(qt,br))
56			#define QT_CLEAR_CHILDREN(qt) (QT_NTH_CHILD(qt,0)=QT_NTH_CHILD(qt,1)= \
57			QT_NTH_CHILD(qt,2)=QT_NTH_CHILD(qt,3)=EMPTY)
58	gwlarson	3.1
59
60	gwlarson	3.3	/* QUADTREE NODE FLAGS */
61	gwlarson	3.7	#define QT_IS_FLAG(qt) IS_FLAG(quad_flag,qt)
62			#define QT_SET_FLAG(qt) SET_FLAG(quad_flag,qt)
63			#define QT_CLR_FLAG(qt) CLR_FLAG(quad_flag,qt)
64			#define QT_LEAF_IS_FLAG(qt) IS_FLAG(qtsetflag,QT_INDEX(qt))
65			#define QT_LEAF_SET_FLAG(qt) SET_FLAG(qtsetflag,QT_INDEX(qt))
66			#define QT_LEAF_CLR_FLAG(qt) CLR_FLAG(qtsetflag,QT_INDEX(qt))
67	gwlarson	3.1
68			/* OBJECT SET CODE */
69			#define QT_SET_CNT(s) ((s)[0])
70			#define QT_SET_NTH_ELEM(s,n) ((s)[(n)])
71
72			#define QT_CLEAR_SET(s) ((s)[0] = 0)
73			#define QT_SET_NEXT_ELEM(p) (*(p)++)
74			#define QT_SET_PTR(s) (&((s)[1]))
75
76
77	gwlarson	3.6	#define QT_MAXSET 511
78	gwlarson	3.4	#define MAXCSET 2*QT_MAXSET
79			#define QT_MAXCSET MAXCSET
80	gwlarson	3.1	#ifndef QT_SET_THRESHOLD
81	gwlarson	3.9	#define QT_SET_THRESHOLD 64
82	gwlarson	3.1	#endif
83
84			#ifndef QT_MAX_LEVELS
85	gwlarson	3.9	#define QT_MAX_LEVELS 10
86	gwlarson	3.1	#endif
87
88	gwlarson	3.8	#define QT_FILL_THRESHOLD 2
89	gwlarson	3.4	#define QT_EXPAND 8
90			#define QT_COMPRESS 16
91	gwlarson	3.7	#define QT_DONE 32
92			#define QT_MODIFIED 64
93	gwlarson	3.4
94			#define QT_FLAG_FILL_TRI(f) (((f)&0x7) == QT_FILL_THRESHOLD)
95			#define QT_FLAG_UPDATE(f) ((f)& (QT_EXPAND \| QT_COMPRESS))
96	gwlarson	3.7	#define QT_FLAG_IS_DONE(f) ((f)& QT_DONE)
97			#define QT_FLAG_SET_DONE(f) ((f) \|= QT_DONE)
98			#define QT_FLAG_IS_MODIFIED(f) ((f)& QT_MODIFIED)
99			#define QT_FLAG_SET_MODIFIED(f) ((f) \|= QT_MODIFIED)
100	gwlarson	3.4
101	gwlarson	3.7	#define qtSubdivide(qt) (qt = qtAlloc(),QT_CLEAR_CHILDREN(qt))
102	gwlarson	3.9	#define qtSubdivide_tri(v0,v1,v2,a,b,c) (EDGE_MIDPOINT(a,v0,v1), \
103			EDGE_MIDPOINT(b,v1,v2), \
104			EDGE_MIDPOINT(c,v2,v0))
105	gwlarson	3.7
106	gwlarson	3.1	extern QUADTREE qtnewleaf(), qtaddelem(), qtdelelem();
107
108			extern QUADTREE quad_block[QT_MAX_BLK]; / quadtree blocks */
109	gwlarson	3.3	extern int4 quad_flag; / zeroeth quadtree flag */
110	gwlarson	3.4
111			extern OBJECT *qtsettab; / quadtree leaf node table */
112			extern QUADTREE qtnumsets; /* number of used set indices */
113	gwlarson	3.7	extern int4 *qtsetflag;
114	gwlarson	3.4	#ifdef DEBUG
115			extern OBJECT *qtqueryset();
116			#else
117			#define qtqueryset(qt) (qtsettab[QT_SET_INDEX(qt)])
118			#endif
119
120			#define qtinset(qt,id) inset(qtqueryset(qt),id)
121			#define qtgetset(os,qt) setcopy(os,qtqueryset(qt))
122	gwlarson	3.9
123
124			#define SIDES_GTR(b0,b1,b2,s0,s1,s2,a,b,c) \
125			(s0 = ((b0[0] > a?4:0) \| (b1[0] > a?2:0) \| (b2[0] > a?1:0)), \
126			s1 = ((b0[1] > b?4:0) \| (b1[1] > b?2:0) \| (b2[1] > b?1:0)), \
127			s2 = ((b0[2] > c?4:0) \| (b1[2] > c?2:0) \| (b2[2] > c?1:0)))
128
129			#define SIDES_LESS(b0,b1,b2,s0,s1,s2,a,b,c) \
130			(s0 = ((b0[0] < a?4:0) \| (b1[0] < a?2:0) \| (b2[0] < a?1:0)), \
131			s1 = ((b0[1] < b?4:0) \| (b1[1] < b?2:0) \| (b2[1] < b?1:0)), \
132			s2 = ((b0[2] < c?4:0) \| (b1[2] < c?2:0) \| (b2[2] < c?1:0)))
133	gwlarson	3.4
134	gwlarson	3.7	/*
135			QUADTREE qtRoot_point_locate(qt,q0,q1,q2,peq,pt,r0,r1,r2)
136			QUADTREE qt;
137			FVECT q0,q1,q2;
138			FPEQ peq;
139			FVECT pt;
140			FVECT r0,r1,r2;
141
142			Return the quadtree node containing pt. It is assumed that pt is in
143			the root node qt with ws vertices q0,q1,q2 and plane equation peq.
144			If r0 != NULL will return coordinates of node in (r0,r1,r2).
145			*/
146
147			extern QUADTREE qtRoot_point_locate();
148			extern QUADTREE qtRoot_add_tri();
149			extern QUADTREE qtRoot_remove_tri();
150			extern QUADTREE qtAdd_tri();
151			extern QUADTREE qtRoot_visit_tri_edges();
152			extern QUADTREE qtRoot_trace_ray();