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_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_MAXSET        511
#define MAXCSET          2*QT_MAXSET
#define QT_MAXCSET       MAXCSET
#ifndef QT_SET_THRESHOLD
#define QT_SET_THRESHOLD  100  
#endif

#ifndef QT_MAX_LEVELS
#define QT_MAX_LEVELS     12
#endif

#define QT_HIT  -2
#define QT_DONE -4
#define QT_MODIFIED -8

#define QT_FILL_THRESHOLD 3
#define QT_EXPAND   8
#define QT_COMPRESS 16

#define QT_FLAG_FILL_TRI(f)  (((f)&0x7) == QT_FILL_THRESHOLD)
#define QT_FLAG_UPDATE(f)    ((f)& (QT_EXPAND | QT_COMPRESS))

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

#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))

extern QUADTREE *qtRoot_point_locate();
Revision:	3.6
Committed:	Wed Sep 16 18:16:29 1998 UTC (25 years, 7 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.5:	+3 -3 lines
Log Message:	implemented integer triangle tracing
#	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			#define QT_OFFSET(qt) ((qt)>>5)
56			#define QT_F_BIT(qt) ((qt)&0x1f)
57			#define QT_F_OP(f,qt,op) ((f)[QT_OFFSET(qt)] op (0x1<<QT_F_BIT(qt)))
58			#define QT_IS_FLAG(qt) QT_F_OP(quad_flag,qt,&)
59			#define QT_SET_FLAG(qt) QT_F_OP(quad_flag,qt,\|=)
60			#define QT_CLR_FLAG(qt) QT_F_OP(quad_flag,qt,\|=~)
61	gwlarson	3.1
62
63			/* OBJECT SET CODE */
64			#define QT_SET_CNT(s) ((s)[0])
65			#define QT_SET_NTH_ELEM(s,n) ((s)[(n)])
66
67			#define QT_CLEAR_SET(s) ((s)[0] = 0)
68			#define QT_SET_NEXT_ELEM(p) (*(p)++)
69			#define QT_SET_PTR(s) (&((s)[1]))
70
71
72	gwlarson	3.6	#define QT_MAXSET 511
73	gwlarson	3.4	#define MAXCSET 2*QT_MAXSET
74			#define QT_MAXCSET MAXCSET
75	gwlarson	3.1	#ifndef QT_SET_THRESHOLD
76	gwlarson	3.6	#define QT_SET_THRESHOLD 100
77	gwlarson	3.1	#endif
78
79			#ifndef QT_MAX_LEVELS
80	gwlarson	3.6	#define QT_MAX_LEVELS 12
81	gwlarson	3.1	#endif
82
83	gwlarson	3.4	#define QT_HIT -2
84			#define QT_DONE -4
85			#define QT_MODIFIED -8
86
87			#define QT_FILL_THRESHOLD 3
88			#define QT_EXPAND 8
89			#define QT_COMPRESS 16
90
91			#define QT_FLAG_FILL_TRI(f) (((f)&0x7) == QT_FILL_THRESHOLD)
92			#define QT_FLAG_UPDATE(f) ((f)& (QT_EXPAND \| QT_COMPRESS))
93
94	gwlarson	3.1	extern QUADTREE qtnewleaf(), qtaddelem(), qtdelelem();
95
96			extern QUADTREE quad_block[QT_MAX_BLK]; / quadtree blocks */
97	gwlarson	3.3	extern int4 quad_flag; / zeroeth quadtree flag */
98	gwlarson	3.4
99			extern OBJECT *qtsettab; / quadtree leaf node table */
100			extern QUADTREE qtnumsets; /* number of used set indices */
101
102			#ifdef DEBUG
103			extern OBJECT *qtqueryset();
104			#else
105			#define qtqueryset(qt) (qtsettab[QT_SET_INDEX(qt)])
106			#endif
107
108			#define qtinset(qt,id) inset(qtqueryset(qt),id)
109			#define qtgetset(os,qt) setcopy(os,qtqueryset(qt))
110
111			extern QUADTREE *qtRoot_point_locate();