src/hd/sm_stree.c

/* Copyright (c) 1998 Silicon Graphics, Inc. */

#ifndef lint
static char SCCSid[] = "$SunId$ SGI";
#endif

/*
 * sm_stree.c
 *  An stree (spherical quadtree) is defined by an octahedron in 
 *  canonical form,and a world center point. Each face of the 
 *  octahedron is adaptively subdivided as a planar triangular quadtree.
 *  World space geometry is projected onto the quadtree faces from the
 *  sphere center.
 */
#include "standard.h"
#include "sm_flag.h"
#include "sm_geom.h"
#include "sm_qtree.h"
#include "sm_stree.h"

#ifdef TEST_DRIVER
extern FVECT Pick_point[500],Pick_v0[500],Pick_v1[500],Pick_v2[500];
extern int Pick_cnt;
#endif
/* octahedron coordinates */
FVECT stDefault_base[6] = {  {1.,0.,0.},{0.,1.,0.}, {0.,0.,1.},
                            {-1.,0.,0.},{0.,-1.,0.},{0.,0.,-1.}};
/* octahedron triangle vertices */
int stBase_verts[8][3] = { {2,1,0},{1,5,0},{5,1,3},{1,2,3},
                          {4,2,0},{4,0,5},{3,4,5},{4,3,2}};
/* octahedron triangle nbrs ; nbr i is the face opposite vertex i*/
int stBase_nbrs[8][3] =  { {1,4,3},{5,0,2},{3,6,1},{7,2,0},
                          {0,5,7},{1,6,4},{5,2,7},{3,4,6}};
/* look up table for octahedron point location */
int stlocatetbl[8] = {6,7,2,3,5,4,1,0};


/* Initializes an stree structure with origin 'center': 
   Frees existing quadtrees hanging off of the roots
*/
stInit(st)
STREE *st;
{
    ST_TOP_ROOT(st) = qtAlloc();
    ST_BOTTOM_ROOT(st) = qtAlloc();
    ST_INIT_ROOT(st);
}

/* Frees the children of the 2 quadtrees rooted at st,
   Does not free root nodes: just clears
*/
stClear(st)
   STREE *st;
{
    qtDone();
    stInit(st);
}

/* Allocates a stree structure  and creates octahedron base */
STREE
*stAlloc(st)
STREE *st;
{
  int i,m;
  FVECT v0,v1,v2;
  FVECT n;
  
  if(!st)
    if(!(st = (STREE *)malloc(sizeof(STREE))))
       error(SYSTEM,"stAlloc(): Unable to allocate memory\n");

  /* Allocate the top and bottom quadtree root nodes */
  stInit(st);
  
  /* Set the octahedron base */
  ST_SET_BASE(st,stDefault_base);

  /* Calculate octahedron face and edge normals */
  for(i=0; i < ST_NUM_ROOT_NODES; i++)
  {
      VCOPY(v0,ST_NTH_V(st,i,0));
      VCOPY(v1,ST_NTH_V(st,i,1));
      VCOPY(v2,ST_NTH_V(st,i,2));
      tri_plane_equation(v0,v1,v2, &ST_NTH_PLANE(st,i),FALSE);
      m = max_index(FP_N(ST_NTH_PLANE(st,i)),NULL);
      FP_X(ST_NTH_PLANE(st,i)) = (m+1)%3; 
      FP_Y(ST_NTH_PLANE(st,i)) = (m+2)%3;
      FP_Z(ST_NTH_PLANE(st,i)) = m;
      VCROSS(ST_EDGE_NORM(st,i,0),v0,v1);
      VCROSS(ST_EDGE_NORM(st,i,1),v1,v2);
      VCROSS(ST_EDGE_NORM(st,i,2),v2,v0);
  }
  return(st);
}


/* Return quadtree leaf node containing point 'p'*/
QUADTREE
stPoint_locate(st,p)
    STREE *st;
    FVECT p;
{
    int i;
    QUADTREE root,qt;

    /* Find root quadtree that contains p */
    i = stPoint_in_root(p);
    root = ST_NTH_ROOT(st,i);
    
    /* Traverse quadtree to leaf level */
    qt = qtRoot_point_locate(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
                        ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),p);
    return(qt);
}

/* Add triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
   FALSE on error, TRUE otherwise
*/

stAdd_tri(st,id,t0,t1,t2)
STREE *st;
int id;
FVECT t0,t1,t2;
{
  int i;
  QUADTREE root;

  for(i=0; i < ST_NUM_ROOT_NODES; i++)
  {
    root = ST_NTH_ROOT(st,i);
    ST_NTH_ROOT(st,i) = qtRoot_add_tri(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
                            ST_NTH_V(st,i,2),t0,t1,t2,id,0);
  }
}

/* Remove triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
   FALSE on error, TRUE otherwise
*/

stRemove_tri(st,id,t0,t1,t2)
STREE *st;
int id;
FVECT t0,t1,t2;
{
  int i;
  QUADTREE root;

  for(i=0; i < ST_NUM_ROOT_NODES; i++)
  {
    root = ST_NTH_ROOT(st,i);
    ST_NTH_ROOT(st,i)=qtRoot_remove_tri(root,id,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
                          ST_NTH_V(st,i,2),t0,t1,t2);
  }
}

/* Visit all nodes that are intersected by the edges of triangle 't0,t1,t2'
   and apply 'func'
*/

stVisit_tri_edges(st,t0,t1,t2,func,fptr,argptr)
   STREE *st;
   FVECT t0,t1,t2;
   int (*func)(),*fptr;
   int *argptr;
{
    int id,i,w,next;
    QUADTREE root;
    FVECT v[3],i_pt;

    VCOPY(v[0],t0); VCOPY(v[1],t1); VCOPY(v[2],t2);
    w = -1;

    /* Locate the root containing triangle vertex v0 */
    i = stPoint_in_root(v[0]);
    /* Mark the root node as visited */
    QT_SET_FLAG(ST_ROOT(st,i));
    root = ST_NTH_ROOT(st,i);
    
    ST_NTH_ROOT(st,i) = qtRoot_visit_tri_edges(root,ST_NTH_V(st,i,0),
       ST_NTH_V(st,i,1),ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),v,i_pt,&w,
                                               &next,func,fptr,argptr);
    if(QT_FLAG_IS_DONE(*fptr))
      return;
        
    /* Crossed over to next node: id = nbr */
    while(1) 
    {
        /* test if ray crosses plane between this quadtree triangle and
           its neighbor- if it does then find intersection point with 
           ray and plane- this is the new start point
           */
        i = stBase_nbrs[i][next];
        root = ST_NTH_ROOT(st,i);
        ST_NTH_ROOT(st,i) = 
          qtRoot_visit_tri_edges(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
         ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),v,i_pt,&w,&next,func,fptr,argptr);
        if(QT_FLAG_IS_DONE(*fptr))
          return;
    }
}

/* Trace ray 'orig-dir' through stree and apply 'func(qtptr,f,argptr)' at each
   node that it intersects
*/
int
stTrace_ray(st,orig,dir,func,argptr)
   STREE *st;
   FVECT orig,dir;
   int (*func)();
   int *argptr;
{
    int next,last,i,f=0;
    QUADTREE root;
    FVECT o,n,v;
    double pd,t,d;

    VCOPY(o,orig);
#ifdef TEST_DRIVER
       Pick_cnt=0;
#endif;
    /* Find the root node that o falls in */
    i = stPoint_in_root(o);
    root = ST_NTH_ROOT(st,i);
    
    ST_NTH_ROOT(st,i) = 
      qtRoot_trace_ray(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
          ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),o,dir,&next,func,&f,argptr);

    if(QT_FLAG_IS_DONE(f))
      return(TRUE);
    
    d = DOT(orig,dir)/sqrt(DOT(orig,orig));
    VSUM(v,orig,dir,-d);
    /* Crossed over to next cell: id = nbr */
    while(1) 
      {
        /* test if ray crosses plane between this quadtree triangle and
           its neighbor- if it does then find intersection point with 
           ray and plane- this is the new origin
           */
        if(next == INVALID)
          return(FALSE);
#if 0
        if(!intersect_ray_oplane(o,dir,ST_EDGE_NORM(st,i,(next+1)%3),NULL,o))
#endif
           if(DOT(o,v) < 0.0)
           /* Ray does not cross into next cell: done and tri not found*/
           return(FALSE);

        VSUM(o,o,dir,10*FTINY);
        i = stBase_nbrs[i][next];
        root = ST_NTH_ROOT(st,i);
        
        ST_NTH_ROOT(st,i) = 
          qtRoot_trace_ray(root, ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
               ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),o,dir,&next,func,&f,argptr);
        if(QT_FLAG_IS_DONE(f))
          return(TRUE);
      }
}


/* Visit nodes intersected by tri 't0,t1,t2' and apply 'func(arg1,arg2,arg3):
   assumes that stVisit_tri_edges has already been called such that all nodes
   intersected by tri edges are already marked as visited
*/
stVisit_tri(st,t0,t1,t2,func,f,argptr)
   STREE *st;
   FVECT t0,t1,t2;
   int (*func)(),*f;
   int *argptr;
{
  int i;
  QUADTREE root;
  FVECT n0,n1,n2;

  /* Calcuate the edge normals for tri */
  VCROSS(n0,t0,t1);
  VCROSS(n1,t1,t2);
  VCROSS(n2,t2,t0);

  for(i=0; i < ST_NUM_ROOT_NODES; i++)
  {
    root = ST_NTH_ROOT(st,i);
    ST_NTH_ROOT(st,i) = qtVisit_tri_interior(root,ST_NTH_V(st,i,0),
        ST_NTH_V(st,i,1),ST_NTH_V(st,i,2),t0,t1,t2,n0,n1,n2,0,func,f,argptr);

  }
}

/* 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
 */
int
stApply_to_tri(st,t0,t1,t2,edge_func,tri_func,argptr)
   STREE *st;
   FVECT t0,t1,t2;
   int (*edge_func)(),(*tri_func)();
   int *argptr;
{
    int f;
    FVECT dir;

#ifdef TEST_DRIVER
    Pick_cnt=0;
#endif;
  /* First add all of the leaf cells lying on the triangle perimeter:
     mark all cells seen on the way
   */
    f = 0;
    /* Visit cells along edges of the tri */
    stVisit_tri_edges(st,t0,t1,t2,edge_func,&f,argptr);

    /* Now visit All cells interior */
    if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f))
       stVisit_tri(st,t0,t1,t2,tri_func,&f,argptr);
}


Revision:	3.7
Committed:	Wed Nov 11 12:05:41 1998 UTC (27 years, 1 month ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.6:	+30 -17 lines
Log Message:	new triangulation code changed triangle vertex order to CCW changed numbering of triangle neighbors to match quadtree fixed tone-mapping bug removed errant printf() statements redid logic for adding and testing samples with new epsilon
#	User	Rev	Content
1	gwlarson	3.1	/* Copyright (c) 1998 Silicon Graphics, Inc. */
2
3			#ifndef lint
4			static char SCCSid[] = "$SunId$ SGI";
5			#endif
6
7			/*
8			* sm_stree.c
9	gwlarson	3.6	* An stree (spherical quadtree) is defined by an octahedron in
10			* canonical form,and a world center point. Each face of the
11			* octahedron is adaptively subdivided as a planar triangular quadtree.
12			* World space geometry is projected onto the quadtree faces from the
13			* sphere center.
14	gwlarson	3.1	*/
15			#include "standard.h"
16	gwlarson	3.6	#include "sm_flag.h"
17	gwlarson	3.1	#include "sm_geom.h"
18	gwlarson	3.6	#include "sm_qtree.h"
19	gwlarson	3.1	#include "sm_stree.h"
20
21	gwlarson	3.4	#ifdef TEST_DRIVER
22			extern FVECT Pick_point[500],Pick_v0[500],Pick_v1[500],Pick_v2[500];
23			extern int Pick_cnt;
24			#endif
25	gwlarson	3.6	/* octahedron coordinates */
26			FVECT stDefault_base[6] = { {1.,0.,0.},{0.,1.,0.}, {0.,0.,1.},
27			{-1.,0.,0.},{0.,-1.,0.},{0.,0.,-1.}};
28			/* octahedron triangle vertices */
29	gwlarson	3.7	int stBase_verts[8][3] = { {2,1,0},{1,5,0},{5,1,3},{1,2,3},
30			{4,2,0},{4,0,5},{3,4,5},{4,3,2}};
31	gwlarson	3.6	/* octahedron triangle nbrs ; nbr i is the face opposite vertex i*/
32	gwlarson	3.7	int stBase_nbrs[8][3] = { {1,4,3},{5,0,2},{3,6,1},{7,2,0},
33			{0,5,7},{1,6,4},{5,2,7},{3,4,6}};
34	gwlarson	3.6	/* look up table for octahedron point location */
35			int stlocatetbl[8] = {6,7,2,3,5,4,1,0};
36	gwlarson	3.1
37	gwlarson	3.6
38			/* Initializes an stree structure with origin 'center':
39			Frees existing quadtrees hanging off of the roots
40			*/
41			stInit(st)
42	gwlarson	3.1	STREE *st;
43			{
44	gwlarson	3.6	ST_TOP_ROOT(st) = qtAlloc();
45			ST_BOTTOM_ROOT(st) = qtAlloc();
46			ST_INIT_ROOT(st);
47	gwlarson	3.1	}
48
49	gwlarson	3.6	/* Frees the children of the 2 quadtrees rooted at st,
50			Does not free root nodes: just clears
51			*/
52	gwlarson	3.1	stClear(st)
53	gwlarson	3.6	STREE *st;
54	gwlarson	3.1	{
55	gwlarson	3.6	qtDone();
56			stInit(st);
57	gwlarson	3.1	}
58
59	gwlarson	3.6	/* Allocates a stree structure and creates octahedron base */
60	gwlarson	3.1	STREE
61			*stAlloc(st)
62			STREE *st;
63			{
64	gwlarson	3.6	int i,m;
65			FVECT v0,v1,v2;
66			FVECT n;
67
68	gwlarson	3.1	if(!st)
69	gwlarson	3.6	if(!(st = (STREE *)malloc(sizeof(STREE))))
70			error(SYSTEM,"stAlloc(): Unable to allocate memory\n");
71	gwlarson	3.1
72	gwlarson	3.6	/* Allocate the top and bottom quadtree root nodes */
73			stInit(st);
74
75			/* Set the octahedron base */
76			ST_SET_BASE(st,stDefault_base);
77	gwlarson	3.1
78	gwlarson	3.6	/* Calculate octahedron face and edge normals */
79			for(i=0; i < ST_NUM_ROOT_NODES; i++)
80			{
81			VCOPY(v0,ST_NTH_V(st,i,0));
82			VCOPY(v1,ST_NTH_V(st,i,1));
83			VCOPY(v2,ST_NTH_V(st,i,2));
84			tri_plane_equation(v0,v1,v2, &ST_NTH_PLANE(st,i),FALSE);
85			m = max_index(FP_N(ST_NTH_PLANE(st,i)),NULL);
86			FP_X(ST_NTH_PLANE(st,i)) = (m+1)%3;
87			FP_Y(ST_NTH_PLANE(st,i)) = (m+2)%3;
88			FP_Z(ST_NTH_PLANE(st,i)) = m;
89	gwlarson	3.7	VCROSS(ST_EDGE_NORM(st,i,0),v0,v1);
90			VCROSS(ST_EDGE_NORM(st,i,1),v1,v2);
91			VCROSS(ST_EDGE_NORM(st,i,2),v2,v0);
92	gwlarson	3.6	}
93	gwlarson	3.1	return(st);
94			}
95
96
97	gwlarson	3.6	/* Return quadtree leaf node containing point 'p'*/
98	gwlarson	3.3	QUADTREE
99	gwlarson	3.6	stPoint_locate(st,p)
100	gwlarson	3.1	STREE *st;
101	gwlarson	3.2	FVECT p;
102	gwlarson	3.1	{
103	gwlarson	3.6	int i;
104			QUADTREE root,qt;
105	gwlarson	3.1
106	gwlarson	3.6	/* Find root quadtree that contains p */
107			i = stPoint_in_root(p);
108			root = ST_NTH_ROOT(st,i);
109	gwlarson	3.1
110	gwlarson	3.6	/* Traverse quadtree to leaf level */
111			qt = qtRoot_point_locate(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
112			ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),p);
113			return(qt);
114	gwlarson	3.1	}
115
116	gwlarson	3.6	/* Add triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
117			FALSE on error, TRUE otherwise
118			*/
119	gwlarson	3.3
120	gwlarson	3.6	stAdd_tri(st,id,t0,t1,t2)
121	gwlarson	3.1	STREE *st;
122			int id;
123	gwlarson	3.6	FVECT t0,t1,t2;
124	gwlarson	3.1	{
125	gwlarson	3.6	int i;
126			QUADTREE root;
127	gwlarson	3.2
128	gwlarson	3.6	for(i=0; i < ST_NUM_ROOT_NODES; i++)
129	gwlarson	3.1	{
130	gwlarson	3.6	root = ST_NTH_ROOT(st,i);
131			ST_NTH_ROOT(st,i) = qtRoot_add_tri(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
132			ST_NTH_V(st,i,2),t0,t1,t2,id,0);
133	gwlarson	3.1	}
134			}
135
136	gwlarson	3.6	/* Remove triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
137			FALSE on error, TRUE otherwise
138			*/
139	gwlarson	3.1
140	gwlarson	3.6	stRemove_tri(st,id,t0,t1,t2)
141	gwlarson	3.1	STREE *st;
142			int id;
143	gwlarson	3.6	FVECT t0,t1,t2;
144	gwlarson	3.1	{
145	gwlarson	3.6	int i;
146			QUADTREE root;
147	gwlarson	3.1
148	gwlarson	3.6	for(i=0; i < ST_NUM_ROOT_NODES; i++)
149	gwlarson	3.1	{
150	gwlarson	3.6	root = ST_NTH_ROOT(st,i);
151			ST_NTH_ROOT(st,i)=qtRoot_remove_tri(root,id,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
152			ST_NTH_V(st,i,2),t0,t1,t2);
153	gwlarson	3.1	}
154			}
155
156	gwlarson	3.6	/* Visit all nodes that are intersected by the edges of triangle 't0,t1,t2'
157			and apply 'func'
158			*/
159
160			stVisit_tri_edges(st,t0,t1,t2,func,fptr,argptr)
161	gwlarson	3.4	STREE *st;
162			FVECT t0,t1,t2;
163	gwlarson	3.6	int (func)(),fptr;
164			int *argptr;
165	gwlarson	3.4	{
166	gwlarson	3.6	int id,i,w,next;
167			QUADTREE root;
168			FVECT v[3],i_pt;
169	gwlarson	3.3
170	gwlarson	3.4	VCOPY(v[0],t0); VCOPY(v[1],t1); VCOPY(v[2],t2);
171			w = -1;
172	gwlarson	3.6
173			/* Locate the root containing triangle vertex v0 */
174			i = stPoint_in_root(v[0]);
175			/* Mark the root node as visited */
176			QT_SET_FLAG(ST_ROOT(st,i));
177			root = ST_NTH_ROOT(st,i);
178
179			ST_NTH_ROOT(st,i) = qtRoot_visit_tri_edges(root,ST_NTH_V(st,i,0),
180			ST_NTH_V(st,i,1),ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),v,i_pt,&w,
181			&next,func,fptr,argptr);
182			if(QT_FLAG_IS_DONE(*fptr))
183			return;
184	gwlarson	3.4
185	gwlarson	3.6	/* Crossed over to next node: id = nbr */
186			while(1)
187			{
188			/* test if ray crosses plane between this quadtree triangle and
189			its neighbor- if it does then find intersection point with
190			ray and plane- this is the new start point
191			*/
192			i = stBase_nbrs[i][next];
193			root = ST_NTH_ROOT(st,i);
194			ST_NTH_ROOT(st,i) =
195			qtRoot_visit_tri_edges(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
196			ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),v,i_pt,&w,&next,func,fptr,argptr);
197			if(QT_FLAG_IS_DONE(*fptr))
198			return;
199			}
200	gwlarson	3.4	}
201
202	gwlarson	3.6	/* Trace ray 'orig-dir' through stree and apply 'func(qtptr,f,argptr)' at each
203			node that it intersects
204			*/
205	gwlarson	3.4	int
206	gwlarson	3.6	stTrace_ray(st,orig,dir,func,argptr)
207	gwlarson	3.4	STREE *st;
208			FVECT orig,dir;
209			int (*func)();
210	gwlarson	3.6	int *argptr;
211	gwlarson	3.4	{
212	gwlarson	3.6	int next,last,i,f=0;
213			QUADTREE root;
214	gwlarson	3.7	FVECT o,n,v;
215			double pd,t,d;
216	gwlarson	3.4
217			VCOPY(o,orig);
218	gwlarson	3.7	#ifdef TEST_DRIVER
219			Pick_cnt=0;
220			#endif;
221	gwlarson	3.6	/* Find the root node that o falls in */
222			i = stPoint_in_root(o);
223			root = ST_NTH_ROOT(st,i);
224
225			ST_NTH_ROOT(st,i) =
226			qtRoot_trace_ray(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
227			ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),o,dir,&next,func,&f,argptr);
228
229			if(QT_FLAG_IS_DONE(f))
230			return(TRUE);
231	gwlarson	3.7
232			d = DOT(orig,dir)/sqrt(DOT(orig,orig));
233			VSUM(v,orig,dir,-d);
234	gwlarson	3.6	/* Crossed over to next cell: id = nbr */
235			while(1)
236			{
237			/* test if ray crosses plane between this quadtree triangle and
238			its neighbor- if it does then find intersection point with
239			ray and plane- this is the new origin
240			*/
241			if(next == INVALID)
242			return(FALSE);
243	gwlarson	3.7	#if 0
244			if(!intersect_ray_oplane(o,dir,ST_EDGE_NORM(st,i,(next+1)%3),NULL,o))
245			#endif
246			if(DOT(o,v) < 0.0)
247	gwlarson	3.4	/* Ray does not cross into next cell: done and tri not found*/
248	gwlarson	3.6	return(FALSE);
249	gwlarson	3.4
250	gwlarson	3.6	VSUM(o,o,dir,10*FTINY);
251			i = stBase_nbrs[i][next];
252			root = ST_NTH_ROOT(st,i);
253
254			ST_NTH_ROOT(st,i) =
255			qtRoot_trace_ray(root, ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
256			ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),o,dir,&next,func,&f,argptr);
257			if(QT_FLAG_IS_DONE(f))
258			return(TRUE);
259			}
260	gwlarson	3.4	}
261
262
263	gwlarson	3.6	/* Visit nodes intersected by tri 't0,t1,t2' and apply 'func(arg1,arg2,arg3):
264			assumes that stVisit_tri_edges has already been called such that all nodes
265			intersected by tri edges are already marked as visited
266			*/
267			stVisit_tri(st,t0,t1,t2,func,f,argptr)
268	gwlarson	3.4	STREE *st;
269			FVECT t0,t1,t2;
270	gwlarson	3.6	int (func)(),f;
271			int *argptr;
272	gwlarson	3.4	{
273			int i;
274	gwlarson	3.6	QUADTREE root;
275			FVECT n0,n1,n2;
276	gwlarson	3.4
277	gwlarson	3.6	/* Calcuate the edge normals for tri */
278	gwlarson	3.7	VCROSS(n0,t0,t1);
279			VCROSS(n1,t1,t2);
280			VCROSS(n2,t2,t0);
281	gwlarson	3.6
282			for(i=0; i < ST_NUM_ROOT_NODES; i++)
283	gwlarson	3.4	{
284	gwlarson	3.6	root = ST_NTH_ROOT(st,i);
285			ST_NTH_ROOT(st,i) = qtVisit_tri_interior(root,ST_NTH_V(st,i,0),
286			ST_NTH_V(st,i,1),ST_NTH_V(st,i,2),t0,t1,t2,n0,n1,n2,0,func,f,argptr);
287
288	gwlarson	3.4	}
289			}
290
291	gwlarson	3.6	/* Visit nodes intersected by tri 't0,t1,t2'.Apply 'edge_func(arg1,arg2,arg3)',
292			to those nodes intersected by edges, and interior_func to ALL nodes:
293			ie some Nodes will be visited more than once
294			*/
295	gwlarson	3.4	int
296	gwlarson	3.6	stApply_to_tri(st,t0,t1,t2,edge_func,tri_func,argptr)
297	gwlarson	3.4	STREE *st;
298			FVECT t0,t1,t2;
299	gwlarson	3.6	int (edge_func)(),(tri_func)();
300			int *argptr;
301	gwlarson	3.4	{
302			int f;
303			FVECT dir;
304	gwlarson	3.7
305			#ifdef TEST_DRIVER
306			Pick_cnt=0;
307			#endif;
308	gwlarson	3.4	/* First add all of the leaf cells lying on the triangle perimeter:
309			mark all cells seen on the way
310	gwlarson	3.3	*/
311	gwlarson	3.4	f = 0;
312			/* Visit cells along edges of the tri */
313	gwlarson	3.6	stVisit_tri_edges(st,t0,t1,t2,edge_func,&f,argptr);
314	gwlarson	3.3
315	gwlarson	3.6	/* Now visit All cells interior */
316	gwlarson	3.4	if(QT_FLAG_FILL_TRI(f) \|\| QT_FLAG_UPDATE(f))
317	gwlarson	3.6	stVisit_tri(st,t0,t1,t2,tri_func,&f,argptr);
318	gwlarson	3.3	}
319	gwlarson	3.7
320
321
322
323	gwlarson	3.6
324
325
326
327	gwlarson	3.5
328	gwlarson	3.3
329	gwlarson	3.4
330
331