src/hd/sm_stree.h

/* RCSid: $Id: sm_stree.h,v 3.6 2003/02/22 02:07:25 greg Exp $ */
/*
 *  sm_stree.h - header file for spherical quadtree code:
 *             
 */
#ifndef _RAD_SM_STREE_H_
#define _RAD_SM_STREE_H_

#ifdef __cplusplus
extern "C" {
#endif


#define STR_INDEX(s)  (stRoot_indices[(s)])
#define STR_NTH_INDEX(s,n)  (stRoot_indices[(s)][(n)])

#define ST_NUM_ROOT_NODES 8


/* The base is an octahedron: Each face contains a planar quadtree. At
 the root level, the "top" (positive y) four faces, and bottom four faces
 are stored together:forming two root quadtree nodes
 */

typedef struct _STREE {
  QUADTREE   qt[2];  /* root[0]= top four faces, root[1]=bottom 4 faces*/

}STREE;


#define ST_BASEI(n)            ((n)>>2)     /* root index: top or bottom */
#define ST_INDEX(n)            ((n) & 0x3) /* which child in root */
#define ST_QT(s,i)           ((s)->qt[ST_BASEI(i)]) /* top or bottom root*/
#define ST_QT_PTR(s,i)       (&ST_QT(s,i)) /* ptr to top(0)/bottom(1)root*/
#define ST_TOP_QT(s)         ((s)->qt[0])  /* top root (y>0)*/
#define ST_BOTTOM_QT(s)      ((s)->qt[1])  /* bottom qt (y <= 0)*/
#define ST_TOP_QT_PTR(s)     (&ST_TOP_QT(s)) /* ptr to top qt */
#define ST_BOTTOM_QT_PTR(s)  (&ST_BOTTOM_QT(s)) /* ptr to bottom qt*/

#define ST_NTH_V(s,n,w)        (stDefault_base[stBase_verts[n][w]])
#define ST_ROOT_QT(s,n)        QT_NTH_CHILD(ST_QT(s,n),ST_INDEX(n))

#define ST_CLEAR_QT(st)      (ST_TOP_QT(st)=EMPTY,ST_BOTTOM_QT(st)=EMPTY)
#define ST_INIT_QT(st)      (QT_CLEAR_CHILDREN(ST_TOP_QT(st)), \
                                QT_CLEAR_CHILDREN(ST_BOTTOM_QT(st)))

#define ST_CLEAR_FLAGS(s)       qtClearAllFlags()

/* Point location based on coordinate signs */ 
#define stLocate_root(p) (((p)[2]>0.0?0:4)|((p)[1]>0.0?0:2)|((p)[0]>0.0?0:1))
#define stClear(st)    stInit(st)

#define ST_CLIP_VERTS 16
/* STREE functions
void stInit(STREE *st,FVECT  center)
          Initializes an stree structure with origin 'center': 
          Frees existing quadtrees hanging off of the roots

STREE *stAlloc(STREE *st)
         Allocates a stree structure  and creates octahedron base 

         
QUADTREE stPoint_locate(STREE *st,FVECT p)
         Returns quadtree leaf node containing point 'p'. 

int stAdd_tri(STREE *st,int id,FVECT t0,t1,t2)
         Add triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
         FALSE on error, TRUE otherwise
         
int stRemove_tri(STREE *st,int id,FVECT t0,t1,t2)
         Removes triangle 'id' with coordinates 't0,t1,t2' from stree: returns
         FALSE on error, TRUE otherwise
         
int stTrace_ray(STREE *st,FVECT orig,dir,int (*func)(),int *arg1,*arg2)
        Trace ray 'orig-dir' through stree and apply 'func(arg1,arg2)' at each
        node that it intersects

int stApply_to_tri(STREE *st,FVECT t0,t1,t2,int (*edge_func)(),
        (*tri_func)(),int arg1,*arg2)   
   Visit nodes intersected by tri 't0,t1,t2'.Apply 'edge_func(arg1,arg2,arg3)',
   to those nodes intersected by edges, and interior_func to ALL nodes:
   ie some Nodes  will be visited more than once
*/

extern int stBase_verts[8][3];
extern FVECT stDefault_base[6];
extern STREE *stAlloc();
extern QUADTREE stPoint_locate();

#ifdef __cplusplus
}
#endif
#endif /* _RAD_SM_STREE_H_ */


Revision:	3.7
Committed:	Mon Jul 14 22:24:00 2003 UTC (20 years, 9 months ago) by schorsch
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad3R6P1, rad3R6
Changes since 3.6:	+12 -3 lines
Log Message:	Instrumented headers against multiple inclusion and for use from C++. Moved includes in headers out of "C" scope.
#	User	Rev	Content
1	schorsch	3.7	/* RCSid: $Id: sm_stree.h,v 3.6 2003/02/22 02:07:25 greg Exp $ */
2	gwlarson	3.1	/*
3			* sm_stree.h - header file for spherical quadtree code:
4			*
5			*/
6	schorsch	3.7	#ifndef _RAD_SM_STREE_H_
7			#define _RAD_SM_STREE_H_
8
9			#ifdef __cplusplus
10			extern "C" {
11			#endif
12
13	gwlarson	3.1
14	gwlarson	3.4	#define STR_INDEX(s) (stRoot_indices[(s)])
15			#define STR_NTH_INDEX(s,n) (stRoot_indices[(s)][(n)])
16	gwlarson	3.1
17	gwlarson	3.3	#define ST_NUM_ROOT_NODES 8
18	gwlarson	3.1
19	gwlarson	3.4
20
21	gwlarson	3.3	/* The base is an octahedron: Each face contains a planar quadtree. At
22			the root level, the "top" (positive y) four faces, and bottom four faces
23			are stored together:forming two root quadtree nodes
24			*/
25	gwlarson	3.1
26			typedef struct _STREE {
27	gwlarson	3.4	QUADTREE qt[2]; /* root[0]= top four faces, root[1]=bottom 4 faces*/
28
29	gwlarson	3.1	}STREE;
30
31
32	gwlarson	3.3	#define ST_BASEI(n) ((n)>>2) /* root index: top or bottom */
33			#define ST_INDEX(n) ((n) & 0x3) /* which child in root */
34	gwlarson	3.4	#define ST_QT(s,i) ((s)->qt[ST_BASEI(i)]) /* top or bottom root*/
35			#define ST_QT_PTR(s,i) (&ST_QT(s,i)) /* ptr to top(0)/bottom(1)root*/
36			#define ST_TOP_QT(s) ((s)->qt[0]) /* top root (y>0)*/
37			#define ST_BOTTOM_QT(s) ((s)->qt[1]) /* bottom qt (y <= 0)*/
38			#define ST_TOP_QT_PTR(s) (&ST_TOP_QT(s)) /* ptr to top qt */
39			#define ST_BOTTOM_QT_PTR(s) (&ST_BOTTOM_QT(s)) /* ptr to bottom qt*/
40
41	gwlarson	3.5	#define ST_NTH_V(s,n,w) (stDefault_base[stBase_verts[n][w]])
42	gwlarson	3.4	#define ST_ROOT_QT(s,n) QT_NTH_CHILD(ST_QT(s,n),ST_INDEX(n))
43
44			#define ST_CLEAR_QT(st) (ST_TOP_QT(st)=EMPTY,ST_BOTTOM_QT(st)=EMPTY)
45			#define ST_INIT_QT(st) (QT_CLEAR_CHILDREN(ST_TOP_QT(st)), \
46			QT_CLEAR_CHILDREN(ST_BOTTOM_QT(st)))
47
48	gwlarson	3.2	#define ST_CLEAR_FLAGS(s) qtClearAllFlags()
49	gwlarson	3.3
50			/* Point location based on coordinate signs */
51	gwlarson	3.4	#define stLocate_root(p) (((p)[2]>0.0?0:4)\|((p)[1]>0.0?0:2)\|((p)[0]>0.0?0:1))
52	gwlarson	3.5	#define stClear(st) stInit(st)
53	gwlarson	3.3
54	gwlarson	3.4	#define ST_CLIP_VERTS 16
55	gwlarson	3.1	/* STREE functions
56	gwlarson	3.3	void stInit(STREE *st,FVECT center)
57			Initializes an stree structure with origin 'center':
58			Frees existing quadtrees hanging off of the roots
59	gwlarson	3.1
60	gwlarson	3.3	STREE stAlloc(STREE st)
61			Allocates a stree structure and creates octahedron base
62	gwlarson	3.1
63	gwlarson	3.3
64			QUADTREE stPoint_locate(STREE *st,FVECT p)
65			Returns quadtree leaf node containing point 'p'.
66	gwlarson	3.1
67	gwlarson	3.3	int stAdd_tri(STREE *st,int id,FVECT t0,t1,t2)
68			Add triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
69			FALSE on error, TRUE otherwise
70
71			int stRemove_tri(STREE *st,int id,FVECT t0,t1,t2)
72			Removes triangle 'id' with coordinates 't0,t1,t2' from stree: returns
73			FALSE on error, TRUE otherwise
74
75			int stTrace_ray(STREE st,FVECT orig,dir,int (func)(),int arg1,arg2)
76			Trace ray 'orig-dir' through stree and apply 'func(arg1,arg2)' at each
77			node that it intersects
78	gwlarson	3.1
79	gwlarson	3.3	int stApply_to_tri(STREE st,FVECT t0,t1,t2,int (edge_func)(),
80			(tri_func)(),int arg1,arg2)
81			Visit nodes intersected by tri 't0,t1,t2'.Apply 'edge_func(arg1,arg2,arg3)',
82			to those nodes intersected by edges, and interior_func to ALL nodes:
83			ie some Nodes will be visited more than once
84	gwlarson	3.1	*/
85
86	gwlarson	3.3	extern int stBase_verts[8][3];
87	gwlarson	3.5	extern FVECT stDefault_base[6];
88	gwlarson	3.2	extern STREE *stAlloc();
89	gwlarson	3.3	extern QUADTREE stPoint_locate();
90	gwlarson	3.1
91	schorsch	3.7	#ifdef __cplusplus
92			}
93			#endif
94			#endif /* _RAD_SM_STREE_H_ */
95	gwlarson	3.1
96