--- ray/src/hd/sm_stree.h	1998/08/19 17:45:24	3.1
+++ ray/src/hd/sm_stree.h	2003/02/22 02:07:25	3.6
@@ -1,67 +1,85 @@
-/* Copyright (c) 1998 Silicon Graphics, Inc. */
-
-/* SCCSid "$SunId$ SGI" */
-
+/* 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:
  *             
  */
 
-#include "sm_qtree.h"
+#define STR_INDEX(s)  (stRoot_indices[(s)])
+#define STR_NTH_INDEX(s,n)  (stRoot_indices[(s)][(n)])
 
-#define SQRT3_INV 0.5773502692
+#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   root;       /* quadtree triangulation of sphere */
-    FVECT    center;   /* sphere center */
-    FVECT    base[4];  /* 4 vertices on sphere that define base triangulation
-			of 4 triangles: assume cover sphere and triangles
-			are base verts (0,1,2),(0,2,3),(0,3,1), and (1,3,2)
-			*/
+  QUADTREE   qt[2];  /* root[0]= top four faces, root[1]=bottom 4 faces*/
+
 }STREE;
 
-#define ST_ROOT(s)             ((s)->root)
-#define ST_NTH_ROOT(s,n)       QT_NTH_CHILD(ST_ROOT(s),n)
-#define ST_NTH_ROOT_PTR(s,n)   QT_NTH_CHILD_PTR(ST_ROOT(s),n)
-#define ST_CLEAR_ROOT(s)       QT_CLEAR_CHILDREN(ST_ROOT(s))
 
-#define ST_CENTER(s)           ((s)->center)
-#define ST_SET_CENTER(s,b)     VCOPY(ST_CENTER(s),b)
-#define ST_BASE(s)             ((s)->base)
-#define ST_NTH_BASE(s,n)       ((s)->base[(n)])
-#define ST_SET_NTH_BASE(s,n,b) VCOPY(ST_NTH_BASE(s,n),b)
-#define ST_SET_BASE(s,b)       (VCOPY(ST_NTH_BASE(s,0),(b)[0]), \
-				VCOPY(ST_NTH_BASE(s,1),(b)[1]), \
-				VCOPY(ST_NTH_BASE(s,2),(b)[2]), \
-				VCOPY(ST_NTH_BASE(s,3),(b)[3]))
-#define ST_COORD(s,p,r)         VSUB(r,p,ST_CENTER(s))
+#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*/
 
-/* STREE functions
+#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)))
 
-   STREE *stInit(STREE *st)
-           Initialize STREE: if st = NULL, allocate a new one, else clear
-	   return pointer to initialized structure
+#define ST_CLEAR_FLAGS(s)       qtClearAllFlags()
 
-   QUADTREE *stPoint_locate(STREE *st,FVECT pt)
-           Find stree node that projection of pt on sphere falls in 
+/* 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)
 
-   stInsert_tri()
-          for every quadtree tri in the base- find node all leaf nodes that
-	  tri overlaps and add tri to set. If this causes any of the nodes
-	  to be over threshhold- split
-   stDelete_tri()
-          for every quadtree tri in the base- find node all leaf nodes that
-	  tri overlaps. If this causes any of the nodes to be under
-	  threshold- merge
-*/
-extern int   stTri_verts[4][3];
-extern FVECT stDefault_base[4];
+#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();