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
 */

#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_OFFSET(qt)           ((qt)>>5)
#define QT_F_BIT(qt)            ((qt)&0x1f)
#define QT_F_OP(f,qt,op)        ((f)[QT_OFFSET(qt)] op (0x1<<QT_F_BIT(qt)))
#define QT_IS_FLAG(qt)          QT_F_OP(quad_flag,qt,&)
#define QT_SET_FLAG(qt)         QT_F_OP(quad_flag,qt,|=)
#define QT_CLR_FLAG(qt)         QT_F_OP(quad_flag,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_MAX_SET        255
#define MAXCSET           QT_MAX_SET*2
#ifndef QT_SET_THRESHOLD
#define QT_SET_THRESHOLD  30  
#endif

#ifndef QT_MAX_LEVELS
#define QT_MAX_LEVELS     17
#endif

extern QUADTREE  qtnewleaf(), qtaddelem(), qtdelelem();

extern QUADTREE  *quad_block[QT_MAX_BLK];       /* quadtree blocks */
extern int4  *quad_flag;                        /* zeroeth quadtree flag */
Revision:	3.3
Committed:	Tue Aug 25 11:03:27 1998 UTC (27 years, 2 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.2:	+22 -23 lines
Log Message:	fixed problem with picking (ray tracking) of tetrahedron
#	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
23			#define QUADTREE int
24
25			#define EMPTY (-1)
26
27			#define QT_IS_EMPTY(qt) ((qt) == EMPTY)
28	gwlarson	3.3	#define QT_IS_LEAF(qt) ((qt) < EMPTY)
29			#define QT_IS_TREE(qt) ((qt) > EMPTY)
30	gwlarson	3.1
31	gwlarson	3.3	#define QT_INDEX(qt) (-(qt)-2) /* quadtree node from set */
32			#define QT_SET_INDEX(i) (-((i)+2)) /* object set from node */
33			#define QT_BLOCK_SIZE 1024 /* quadtrees in block */
34			#define QT_BLOCK(qt) ((qt)>>10) /* quadtree block index */
35			#define QT_BLOCK_INDEX(qt) (((qt)&0x3ff)<<2) /* quadtree index in block */
36	gwlarson	3.1
37			#ifndef QT_MAX_BLK
38			#ifdef BIGMEM
39	gwlarson	3.3	#define QT_MAX_BLK 16383 /* maximum quadtree block */
40	gwlarson	3.1	#else
41	gwlarson	3.3	#define QT_MAX_BLK 2047 /* maximum quadtree block */
42	gwlarson	3.1	#endif
43			#endif
44
45
46			#define QT_NTH_CHILD(qt,br) (quad_block[QT_BLOCK(qt)][QT_BLOCK_INDEX(qt)+br])
47	gwlarson	3.3	#define QT_NTH_CHILD_PTR(qt,br) (&QT_NTH_CHILD(qt,br))
48			#define QT_CLEAR_CHILDREN(qt) (QT_NTH_CHILD(qt,0)=QT_NTH_CHILD(qt,1)= \
49			QT_NTH_CHILD(qt,2)=QT_NTH_CHILD(qt,3)=EMPTY)
50	gwlarson	3.1
51
52	gwlarson	3.3	/* QUADTREE NODE FLAGS */
53			#define QT_OFFSET(qt) ((qt)>>5)
54			#define QT_F_BIT(qt) ((qt)&0x1f)
55			#define QT_F_OP(f,qt,op) ((f)[QT_OFFSET(qt)] op (0x1<<QT_F_BIT(qt)))
56			#define QT_IS_FLAG(qt) QT_F_OP(quad_flag,qt,&)
57			#define QT_SET_FLAG(qt) QT_F_OP(quad_flag,qt,\|=)
58			#define QT_CLR_FLAG(qt) QT_F_OP(quad_flag,qt,\|=~)
59	gwlarson	3.1
60
61			/* OBJECT SET CODE */
62			#define QT_SET_CNT(s) ((s)[0])
63			#define QT_SET_NTH_ELEM(s,n) ((s)[(n)])
64
65			#define QT_CLEAR_SET(s) ((s)[0] = 0)
66			#define QT_SET_NEXT_ELEM(p) (*(p)++)
67			#define QT_SET_PTR(s) (&((s)[1]))
68
69
70	gwlarson	3.3	#define QT_MAX_SET 255
71			#define MAXCSET QT_MAX_SET*2
72	gwlarson	3.1	#ifndef QT_SET_THRESHOLD
73	gwlarson	3.2	#define QT_SET_THRESHOLD 30
74	gwlarson	3.1	#endif
75
76			#ifndef QT_MAX_LEVELS
77	gwlarson	3.2	#define QT_MAX_LEVELS 17
78	gwlarson	3.1	#endif
79
80			extern QUADTREE qtnewleaf(), qtaddelem(), qtdelelem();
81
82			extern QUADTREE quad_block[QT_MAX_BLK]; / quadtree blocks */
83	gwlarson	3.3	extern int4 quad_flag; / zeroeth quadtree flag */