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"

#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 30  
#endif

#ifndef QT_MAX_LEVELS
#define QT_MAX_LEVELS     12
#endif

#define QT_FILL_THRESHOLD 3
#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_VEC3(a,v0,v1), \
                                         EDGE_MIDPOINT_VEC3(b,v1,v2), \
                                         EDGE_MIDPOINT_VEC3(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))

/* 
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.7
Committed:	Tue Oct 6 18:18:54 1998 UTC (25 years, 6 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.6:	+38 -14 lines
Log Message:	new triangulate routine added smTestSample to check for occlusion added frustum culling before rebuild changed base quadtree to use octahedron and created new point locate added "sample active" flags and implemented LRU replacement started handling case of too many triangles set sizes are now unbounded\
#	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.1
24			#define QUADTREE int
25
26			#define EMPTY (-1)
27
28			#define QT_IS_EMPTY(qt) ((qt) == EMPTY)
29	gwlarson	3.3	#define QT_IS_LEAF(qt) ((qt) < EMPTY)
30			#define QT_IS_TREE(qt) ((qt) > EMPTY)
31	gwlarson	3.1
32	gwlarson	3.3	#define QT_INDEX(qt) (-(qt)-2) /* quadtree node from set */
33			#define QT_SET_INDEX(i) (-((i)+2)) /* object set from node */
34			#define QT_BLOCK_SIZE 1024 /* quadtrees in block */
35			#define QT_BLOCK(qt) ((qt)>>10) /* quadtree block index */
36			#define QT_BLOCK_INDEX(qt) (((qt)&0x3ff)<<2) /* quadtree index in block */
37	gwlarson	3.1
38	gwlarson	3.4
39	gwlarson	3.1	#ifndef QT_MAX_BLK
40			#ifdef BIGMEM
41	gwlarson	3.3	#define QT_MAX_BLK 16383 /* maximum quadtree block */
42	gwlarson	3.1	#else
43	gwlarson	3.3	#define QT_MAX_BLK 2047 /* maximum quadtree block */
44	gwlarson	3.1	#endif
45			#endif
46
47
48			#define QT_NTH_CHILD(qt,br) (quad_block[QT_BLOCK(qt)][QT_BLOCK_INDEX(qt)+br])
49	gwlarson	3.3	#define QT_NTH_CHILD_PTR(qt,br) (&QT_NTH_CHILD(qt,br))
50			#define QT_CLEAR_CHILDREN(qt) (QT_NTH_CHILD(qt,0)=QT_NTH_CHILD(qt,1)= \
51			QT_NTH_CHILD(qt,2)=QT_NTH_CHILD(qt,3)=EMPTY)
52	gwlarson	3.1
53
54	gwlarson	3.3	/* QUADTREE NODE FLAGS */
55	gwlarson	3.7	#define QT_IS_FLAG(qt) IS_FLAG(quad_flag,qt)
56			#define QT_SET_FLAG(qt) SET_FLAG(quad_flag,qt)
57			#define QT_CLR_FLAG(qt) CLR_FLAG(quad_flag,qt)
58			#define QT_LEAF_IS_FLAG(qt) IS_FLAG(qtsetflag,QT_INDEX(qt))
59			#define QT_LEAF_SET_FLAG(qt) SET_FLAG(qtsetflag,QT_INDEX(qt))
60			#define QT_LEAF_CLR_FLAG(qt) CLR_FLAG(qtsetflag,QT_INDEX(qt))
61	gwlarson	3.1
62			/* OBJECT SET CODE */
63			#define QT_SET_CNT(s) ((s)[0])
64			#define QT_SET_NTH_ELEM(s,n) ((s)[(n)])
65
66			#define QT_CLEAR_SET(s) ((s)[0] = 0)
67			#define QT_SET_NEXT_ELEM(p) (*(p)++)
68			#define QT_SET_PTR(s) (&((s)[1]))
69
70
71	gwlarson	3.6	#define QT_MAXSET 511
72	gwlarson	3.4	#define MAXCSET 2*QT_MAXSET
73			#define QT_MAXCSET MAXCSET
74	gwlarson	3.1	#ifndef QT_SET_THRESHOLD
75	gwlarson	3.7	#define QT_SET_THRESHOLD 30
76	gwlarson	3.1	#endif
77
78			#ifndef QT_MAX_LEVELS
79	gwlarson	3.6	#define QT_MAX_LEVELS 12
80	gwlarson	3.1	#endif
81
82	gwlarson	3.4	#define QT_FILL_THRESHOLD 3
83			#define QT_EXPAND 8
84			#define QT_COMPRESS 16
85	gwlarson	3.7	#define QT_DONE 32
86			#define QT_MODIFIED 64
87	gwlarson	3.4
88			#define QT_FLAG_FILL_TRI(f) (((f)&0x7) == QT_FILL_THRESHOLD)
89			#define QT_FLAG_UPDATE(f) ((f)& (QT_EXPAND \| QT_COMPRESS))
90	gwlarson	3.7	#define QT_FLAG_IS_DONE(f) ((f)& QT_DONE)
91			#define QT_FLAG_SET_DONE(f) ((f) \|= QT_DONE)
92			#define QT_FLAG_IS_MODIFIED(f) ((f)& QT_MODIFIED)
93			#define QT_FLAG_SET_MODIFIED(f) ((f) \|= QT_MODIFIED)
94	gwlarson	3.4
95	gwlarson	3.7	#define qtSubdivide(qt) (qt = qtAlloc(),QT_CLEAR_CHILDREN(qt))
96			#define qtSubdivide_tri(v0,v1,v2,a,b,c) (EDGE_MIDPOINT_VEC3(a,v0,v1), \
97			EDGE_MIDPOINT_VEC3(b,v1,v2), \
98			EDGE_MIDPOINT_VEC3(c,v2,v0))
99
100	gwlarson	3.1	extern QUADTREE qtnewleaf(), qtaddelem(), qtdelelem();
101
102			extern QUADTREE quad_block[QT_MAX_BLK]; / quadtree blocks */
103	gwlarson	3.3	extern int4 quad_flag; / zeroeth quadtree flag */
104	gwlarson	3.4
105			extern OBJECT *qtsettab; / quadtree leaf node table */
106			extern QUADTREE qtnumsets; /* number of used set indices */
107	gwlarson	3.7	extern int4 *qtsetflag;
108	gwlarson	3.4	#ifdef DEBUG
109			extern OBJECT *qtqueryset();
110			#else
111			#define qtqueryset(qt) (qtsettab[QT_SET_INDEX(qt)])
112			#endif
113
114			#define qtinset(qt,id) inset(qtqueryset(qt),id)
115			#define qtgetset(os,qt) setcopy(os,qtqueryset(qt))
116
117	gwlarson	3.7	/*
118			QUADTREE qtRoot_point_locate(qt,q0,q1,q2,peq,pt,r0,r1,r2)
119			QUADTREE qt;
120			FVECT q0,q1,q2;
121			FPEQ peq;
122			FVECT pt;
123			FVECT r0,r1,r2;
124
125			Return the quadtree node containing pt. It is assumed that pt is in
126			the root node qt with ws vertices q0,q1,q2 and plane equation peq.
127			If r0 != NULL will return coordinates of node in (r0,r1,r2).
128			*/
129
130			extern QUADTREE qtRoot_point_locate();
131			extern QUADTREE qtRoot_add_tri();
132			extern QUADTREE qtRoot_remove_tri();
133			extern QUADTREE qtAdd_tri();
134			extern QUADTREE qtRoot_visit_tri_edges();
135			extern QUADTREE qtRoot_trace_ray();