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] = { {0,1,2},{0,5,1},{3,1,5},{3,2,1},
                          {0,2,4},{5,0,4},{5,4,3},{2,3,4}};
/* octahedron triangle nbrs ; nbr i is the face opposite vertex i*/
int stBase_nbrs[8][3] =  { {3,4,1},{2,0,5},{1,6,3},{0,2,7},
                          {7,5,0},{4,6,1},{7,2,5},{6,4,3}};
/* 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),v1,v0);
      VCROSS(ST_EDGE_NORM(st,i,1),v2,v1);
      VCROSS(ST_EDGE_NORM(st,i,2),v0,v2);
  }
  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;
    double pd,t;

    VCOPY(o,orig);

    /* 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);
        
    /* 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(!intersect_ray_oplane(orig,dir,
                                 ST_EDGE_NORM(st,i,(next+1)%3),NULL,o))
           /* 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,t1,t0);
  VCROSS(n1,t2,t1);
  VCROSS(n2,t0,t2);

  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;
    
  /* 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.6
Committed:	Tue Oct 6 18:18:54 1998 UTC (25 years, 6 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.5:	+203 -296 lines
Log Message:	new triangulate routine added smTestSample to check for occlusion added frustum culling before rebuild changed base quadtree to use octahedron and created new point locate added "sample active" flags and implemented LRU replacement started handling case of too many triangles set sizes are now unbounded\
#	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			int stBase_verts[8][3] = { {0,1,2},{0,5,1},{3,1,5},{3,2,1},
30			{0,2,4},{5,0,4},{5,4,3},{2,3,4}};
31			/* octahedron triangle nbrs ; nbr i is the face opposite vertex i*/
32			int stBase_nbrs[8][3] = { {3,4,1},{2,0,5},{1,6,3},{0,2,7},
33			{7,5,0},{4,6,1},{7,2,5},{6,4,3}};
34			/* 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			VCROSS(ST_EDGE_NORM(st,i,0),v1,v0);
90			VCROSS(ST_EDGE_NORM(st,i,1),v2,v1);
91			VCROSS(ST_EDGE_NORM(st,i,2),v0,v2);
92			}
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			FVECT o,n;
215	gwlarson	3.4	double pd,t;
216
217			VCOPY(o,orig);
218	gwlarson	3.6
219			/* Find the root node that o falls in */
220			i = stPoint_in_root(o);
221			root = ST_NTH_ROOT(st,i);
222
223			ST_NTH_ROOT(st,i) =
224			qtRoot_trace_ray(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
225			ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),o,dir,&next,func,&f,argptr);
226
227			if(QT_FLAG_IS_DONE(f))
228			return(TRUE);
229	gwlarson	3.4
230	gwlarson	3.6	/* Crossed over to next cell: id = nbr */
231			while(1)
232			{
233			/* test if ray crosses plane between this quadtree triangle and
234			its neighbor- if it does then find intersection point with
235			ray and plane- this is the new origin
236			*/
237			if(next == INVALID)
238			return(FALSE);
239			if(!intersect_ray_oplane(orig,dir,
240			ST_EDGE_NORM(st,i,(next+1)%3),NULL,o))
241	gwlarson	3.4	/* Ray does not cross into next cell: done and tri not found*/
242	gwlarson	3.6	return(FALSE);
243	gwlarson	3.4
244	gwlarson	3.6	VSUM(o,o,dir,10*FTINY);
245			i = stBase_nbrs[i][next];
246			root = ST_NTH_ROOT(st,i);
247
248			ST_NTH_ROOT(st,i) =
249			qtRoot_trace_ray(root, ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
250			ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),o,dir,&next,func,&f,argptr);
251			if(QT_FLAG_IS_DONE(f))
252			return(TRUE);
253			}
254	gwlarson	3.4	}
255
256
257	gwlarson	3.6	/* Visit nodes intersected by tri 't0,t1,t2' and apply 'func(arg1,arg2,arg3):
258			assumes that stVisit_tri_edges has already been called such that all nodes
259			intersected by tri edges are already marked as visited
260			*/
261			stVisit_tri(st,t0,t1,t2,func,f,argptr)
262	gwlarson	3.4	STREE *st;
263			FVECT t0,t1,t2;
264	gwlarson	3.6	int (func)(),f;
265			int *argptr;
266	gwlarson	3.4	{
267			int i;
268	gwlarson	3.6	QUADTREE root;
269			FVECT n0,n1,n2;
270	gwlarson	3.4
271	gwlarson	3.6	/* Calcuate the edge normals for tri */
272			VCROSS(n0,t1,t0);
273			VCROSS(n1,t2,t1);
274			VCROSS(n2,t0,t2);
275
276			for(i=0; i < ST_NUM_ROOT_NODES; i++)
277	gwlarson	3.4	{
278	gwlarson	3.6	root = ST_NTH_ROOT(st,i);
279			ST_NTH_ROOT(st,i) = qtVisit_tri_interior(root,ST_NTH_V(st,i,0),
280			ST_NTH_V(st,i,1),ST_NTH_V(st,i,2),t0,t1,t2,n0,n1,n2,0,func,f,argptr);
281
282	gwlarson	3.4	}
283			}
284
285	gwlarson	3.6	/* Visit nodes intersected by tri 't0,t1,t2'.Apply 'edge_func(arg1,arg2,arg3)',
286			to those nodes intersected by edges, and interior_func to ALL nodes:
287			ie some Nodes will be visited more than once
288			*/
289	gwlarson	3.4	int
290	gwlarson	3.6	stApply_to_tri(st,t0,t1,t2,edge_func,tri_func,argptr)
291	gwlarson	3.4	STREE *st;
292			FVECT t0,t1,t2;
293	gwlarson	3.6	int (edge_func)(),(tri_func)();
294			int *argptr;
295	gwlarson	3.4	{
296			int f;
297			FVECT dir;
298
299			/* First add all of the leaf cells lying on the triangle perimeter:
300			mark all cells seen on the way
301	gwlarson	3.3	*/
302	gwlarson	3.4	f = 0;
303			/* Visit cells along edges of the tri */
304	gwlarson	3.6	stVisit_tri_edges(st,t0,t1,t2,edge_func,&f,argptr);
305	gwlarson	3.3
306	gwlarson	3.6	/* Now visit All cells interior */
307	gwlarson	3.4	if(QT_FLAG_FILL_TRI(f) \|\| QT_FLAG_UPDATE(f))
308	gwlarson	3.6	stVisit_tri(st,t0,t1,t2,tri_func,&f,argptr);
309	gwlarson	3.3	}
310	gwlarson	3.6
311
312
313
314	gwlarson	3.5
315	gwlarson	3.3
316	gwlarson	3.4
317
318