src/hd/sm_stree.c

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

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

/*
 * sm_stree.c
 */
#include "standard.h"
#include "sm_geom.h"
#include "sm_stree.h"

/* Define 4 vertices on the sphere to create a tetrahedralization on 
   the sphere: triangles are as follows:
        (2,1,0),(3,2,0), (1,3,0), (2,3,1)
*/

#ifdef TEST_DRIVER
extern FVECT Pick_point[500],Pick_v0[500],Pick_v1[500],Pick_v2[500];
extern int Pick_cnt;
#endif
FVECT stDefault_base[4] = { {SQRT3_INV, SQRT3_INV, SQRT3_INV},
                          {-SQRT3_INV, -SQRT3_INV, SQRT3_INV},
                          {-SQRT3_INV, SQRT3_INV, -SQRT3_INV},
                          {SQRT3_INV, -SQRT3_INV, -SQRT3_INV}};
int stTri_verts[4][3] = { {2,1,0},{3,2,0},{1,3,0},{2,3,1}};
int stTri_nbrs[4][3] =  { {2,1,3},{0,2,3},{1,0,3},{2,0,1}};

stNth_base_verts(st,i,v1,v2,v3)
STREE *st;
int i;
FVECT v1,v2,v3;
{
  VCOPY(v1,ST_NTH_BASE(st,stTri_verts[i][0]));
  VCOPY(v2,ST_NTH_BASE(st,stTri_verts[i][1]));
  VCOPY(v3,ST_NTH_BASE(st,stTri_verts[i][2]));
}

/* Frees the 4 quadtrees rooted at st */
stClear(st)
STREE *st;
{
  int i;

  /* stree always has 4 children corresponding to the base tris
  */
  for (i = 0; i < 4; i++)
    qtFree(ST_NTH_ROOT(st, i));

  QT_CLEAR_CHILDREN(ST_ROOT(st));

}


STREE
*stInit(st,center,base)
STREE *st;
FVECT  center,base[4];
{

  if(base)
    ST_SET_BASE(st,base);
  else
    ST_SET_BASE(st,stDefault_base);

  ST_SET_CENTER(st,center);
  stClear(st);

  return(st);
}


/* "base" defines 4 vertices on the sphere to create a tetrahedralization on 
     the sphere: triangles are as follows:(0,1,2),(0,2,3), (0,3,1), (1,3,2)
     if base is null: does default.

 */
STREE
*stAlloc(st)
STREE *st;
{
  int i;

  if(!st)
    st = (STREE *)malloc(sizeof(STREE));

  ST_ROOT(st) = qtAlloc();
    
  QT_CLEAR_CHILDREN(ST_ROOT(st));

  return(st);
}


/* Find location of sample point in the DAG and return lowest level
   containing triangle. "type" indicates whether the point was found
   to be in interior to the triangle: GT_FACE, on one of its
   edges GT_EDGE or coinciding with one of its vertices GT_VERTEX.
   "which" specifies which vertex (0,1,2) or edge (0=v0v1, 1 = v1v2, 2 = v21) 
*/
int
stPoint_locate(st,npt)
    STREE *st;
    FVECT npt;
{
    int i,d,j,id;
    QUADTREE *rootptr,*qtptr;
    FVECT v1,v2,v3;
    OBJECT os[QT_MAXSET+1],*optr;
    FVECT p0,p1,p2;

    /* Test each of the root triangles against point id */
    for(i=0; i < 4; i++)
     {
         rootptr = ST_NTH_ROOT_PTR(st,i);
         stNth_base_verts(st,i,v1,v2,v3);
         /* Return tri that p falls in */
         qtptr = qtRoot_point_locate(rootptr,v1,v2,v3,npt,NULL,NULL,NULL);
         if(!qtptr || QT_IS_EMPTY(*qtptr))
            continue;
         /* Get the set */
         optr = qtqueryset(*qtptr);
         for (j = QT_SET_CNT(optr),optr = QT_SET_PTR(optr);j > 0; j--)
         {
             /* Find the first triangle that pt falls */
             id = QT_SET_NEXT_ELEM(optr);
             qtTri_from_id(id,p0,p1,p2,NULL,NULL,NULL,NULL,NULL,NULL);
             d = point_in_stri(p0,p1,p2,npt);  
             if(d)
               return(id);
         }
     }
    return(EMPTY);
}

QUADTREE
*stPoint_locate_cell(st,p,t0,t1,t2)
    STREE *st;
    FVECT p;
    FVECT t0,t1,t2;
{
    int i,d;
    QUADTREE *rootptr,*qtptr;
    FVECT v0,v1,v2;

    
    /* Test each of the root triangles against point id */
    for(i=0; i < 4; i++)
     {
         rootptr = ST_NTH_ROOT_PTR(st,i);
         stNth_base_verts(st,i,v0,v1,v2);
         /* Return quadtree tri that p falls in */
         qtptr = qtRoot_point_locate(rootptr,v0,v1,v2,p,t0,t1,t2);
         if(qtptr)
            return(qtptr);
     }    /* Point not found */
    return(NULL);
}


int
stAdd_tri(st,id,v0,v1,v2)
STREE *st;
int id;
FVECT v0,v1,v2;
{
  
  int i,found;
  QUADTREE *rootptr;
  FVECT t0,t1,t2;

  found = 0;
  for(i=0; i < 4; i++)
  {
    rootptr = ST_NTH_ROOT_PTR(st,i);
    stNth_base_verts(st,i,t0,t1,t2);
    found |= qtRoot_add_tri(rootptr,t0,t1,t2,v0,v1,v2,id,0);
  }
  return(found);
}

int
stApply_to_tri_cells(st,v0,v1,v2,func,arg)
STREE *st;
FVECT v0,v1,v2;
int (*func)();
int *arg;
{
  int i,found;
  QUADTREE *rootptr;
  FVECT t0,t1,t2;

  found = 0;
  func(ST_ROOT_PTR(st),arg);
  QT_SET_FLAG(ST_ROOT(st));
  for(i=0; i < 4; i++)
  {
    rootptr = ST_NTH_ROOT_PTR(st,i);
    stNth_base_verts(st,i,t0,t1,t2); 
    found |= qtApply_to_tri_cells(rootptr,v0,v1,v2,t0,t1,t2,func,arg);
  }
  return(found);
}


int
stRemove_tri(st,id,v0,v1,v2)
STREE *st;
int id;
FVECT v0,v1,v2;
{
  
  int i,found;
  QUADTREE *rootptr;
  FVECT t0,t1,t2;

  found = 0;
  for(i=0; i < 4; i++)
  {
    rootptr = ST_NTH_ROOT_PTR(st,i);
    stNth_base_verts(st,i,t0,t1,t2); 
   found |= qtRemove_tri(rootptr,id,v0,v1,v2,t0,t1,t2);
  }
  return(found);
}

int
stVisit_tri_edges(st,t0,t1,t2,func,arg1,arg2,arg3)
   STREE *st;
   FVECT t0,t1,t2;
   int (*func)();
   int *arg1,arg2,*arg3;
{
    int id,i,w;
    QUADTREE *rootptr;
    FVECT q0,q1,q2,v[3],i_pt;

    VCOPY(v[0],t0); VCOPY(v[1],t1); VCOPY(v[2],t2);
    w = -1;
    QT_SET_FLAG(ST_ROOT(st));
    for(i=0; i < 4; i++)
     {
#ifdef TEST_DRIVER 
Pick_cnt = 0;
#endif
         rootptr = ST_NTH_ROOT_PTR(st,i);
         stNth_base_verts(st,i,q0,q1,q2);
         /* Return quadtree tri that p falls in */
         if(!point_in_stri(q0,q1,q2,v[0]))  
           continue;
#ifdef TEST_DRIVER
         id = qtRoot_visit_tri_edges(rootptr,q0,q1,q2,v,i_pt,&w,
                                      func,arg1,arg2,arg3);
#else
         id = qtRoot_visit_tri_edgesi(rootptr,q0,q1,q2,v,i_pt,&w,
                                      func,arg1,arg2,arg3);
#endif
         if(id == INVALID)
         {
#ifdef DEBUG
           eputs("stVisit_tri_edges(): Unable to trace edges\n");
#endif
           return(INVALID);
         }
         if(id == QT_DONE)
            return(*arg1);
        
         /* 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
                */
           i = stTri_nbrs[i][id];
           rootptr = ST_NTH_ROOT_PTR(st,i);
           stNth_base_verts(st,i,q0,q1,q2);
#ifdef TEST_DRIVER
           id=qtRoot_visit_tri_edges(rootptr,q0,q1,q2,v,i_pt,&w,
                                      func,arg1,arg2,arg3);
#else
           id=qtRoot_visit_tri_edgesi(rootptr,q0,q1,q2,v,i_pt,&w,
                                      func,arg1,arg2,arg3);
#endif
           if(id == QT_DONE)
             return(*arg1);
           if(id == INVALID)
             {
#ifdef DEBUG
             eputs("stVisit_tri_edges(): point not found\n");
#endif  
             return(INVALID);
             }
           
         }
     }    /* Point not found */
    return(INVALID); 
}

int
stTrace_ray(st,orig,dir,func,arg1,arg2)
   STREE *st;
   FVECT orig,dir;
   int (*func)();
   int *arg1,arg2;
{
    int id,i;
    QUADTREE *rootptr;
    FVECT q0,q1,q2,o,n;
    double pd,t;

    VCOPY(o,orig);
    for(i=0; i < 4; i++)
     {
#ifdef TEST_DRIVER 
Pick_cnt = 0;
#endif
         rootptr = ST_NTH_ROOT_PTR(st,i);
         stNth_base_verts(st,i,q0,q1,q2);
         /* Return quadtree tri that p falls in */
         id= qtRoot_trace_ray(rootptr,q0,q1,q2,o,dir,func,arg1,arg2);
         if(id == INVALID)
           continue;
         if(id == QT_DONE)
            return(*arg1);
        
         /* 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(id==0)
             VCROSS(n,q1,q2);
           else
             if(id==1)
               VCROSS(n,q2,q0);
           else
             VCROSS(n,q0,q1);

           /* Ray does not cross into next cell: done and tri not found*/
           if(!intersect_ray_plane(orig,dir,n,0.0,NULL,o))
             return(INVALID);

           VSUM(o,o,dir,10*FTINY);
           i = stTri_nbrs[i][id];
           rootptr = ST_NTH_ROOT_PTR(st,i);
           stNth_base_verts(st,i,q0,q1,q2);
           id = qtRoot_trace_ray(rootptr,q0,q1,q2,o,dir,func,arg1,arg2);
           if(id == QT_DONE)
             return(*arg1);
           if(id == INVALID)
             return(INVALID);
           
         }
     }    /* Point not found */
    return(INVALID);
}


stVisit_tri_interior(st,t0,t1,t2,func,arg1,arg2,arg3)
   STREE *st;
   FVECT t0,t1,t2;
   int (*func)();
   int *arg1,arg2,*arg3;
{
  int i;
  QUADTREE *rootptr;
  FVECT q0,q1,q2;

  for(i=0; i < 4; i++)
  {
    rootptr = ST_NTH_ROOT_PTR(st,i);
    stNth_base_verts(st,i,q0,q1,q2); 
    qtVisit_tri_interior(rootptr,q0,q1,q2,t0,t1,t2,0,func,arg1,arg2,arg3);
  }
}


int
stApply_to_tri(st,t0,t1,t2,edge_func,interior_func,arg1,arg2)
   STREE *st;
   FVECT t0,t1,t2;
   int (*edge_func)(),(*interior_func)();
   int arg1,*arg2;
{
    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,arg1,arg2);

    /* Now visit interior */
    if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f))
       stVisit_tri_interior(st,t0,t1,t2,interior_func,&f,arg1,arg2);
}


Revision:	3.5
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.4:	+26 -220 lines
Log Message:	implemented integer triangle tracing
#	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			*/
10			#include "standard.h"
11			#include "sm_geom.h"
12			#include "sm_stree.h"
13
14			/* Define 4 vertices on the sphere to create a tetrahedralization on
15			the sphere: triangles are as follows:
16	gwlarson	3.4	(2,1,0),(3,2,0), (1,3,0), (2,3,1)
17	gwlarson	3.1	*/
18
19	gwlarson	3.4	#ifdef TEST_DRIVER
20			extern FVECT Pick_point[500],Pick_v0[500],Pick_v1[500],Pick_v2[500];
21			extern int Pick_cnt;
22			#endif
23	gwlarson	3.1	FVECT stDefault_base[4] = { {SQRT3_INV, SQRT3_INV, SQRT3_INV},
24			{-SQRT3_INV, -SQRT3_INV, SQRT3_INV},
25			{-SQRT3_INV, SQRT3_INV, -SQRT3_INV},
26			{SQRT3_INV, -SQRT3_INV, -SQRT3_INV}};
27	gwlarson	3.4	int stTri_verts[4][3] = { {2,1,0},{3,2,0},{1,3,0},{2,3,1}};
28			int stTri_nbrs[4][3] = { {2,1,3},{0,2,3},{1,0,3},{2,0,1}};
29	gwlarson	3.1
30			stNth_base_verts(st,i,v1,v2,v3)
31			STREE *st;
32			int i;
33			FVECT v1,v2,v3;
34			{
35			VCOPY(v1,ST_NTH_BASE(st,stTri_verts[i][0]));
36			VCOPY(v2,ST_NTH_BASE(st,stTri_verts[i][1]));
37			VCOPY(v3,ST_NTH_BASE(st,stTri_verts[i][2]));
38			}
39
40			/* Frees the 4 quadtrees rooted at st */
41			stClear(st)
42			STREE *st;
43			{
44			int i;
45
46			/* stree always has 4 children corresponding to the base tris
47			*/
48			for (i = 0; i < 4; i++)
49			qtFree(ST_NTH_ROOT(st, i));
50
51			QT_CLEAR_CHILDREN(ST_ROOT(st));
52
53			}
54
55
56			STREE
57			*stInit(st,center,base)
58			STREE *st;
59			FVECT center,base[4];
60			{
61
62			if(base)
63			ST_SET_BASE(st,base);
64			else
65			ST_SET_BASE(st,stDefault_base);
66
67			ST_SET_CENTER(st,center);
68			stClear(st);
69
70			return(st);
71			}
72
73
74			/* "base" defines 4 vertices on the sphere to create a tetrahedralization on
75			the sphere: triangles are as follows:(0,1,2),(0,2,3), (0,3,1), (1,3,2)
76			if base is null: does default.
77
78			*/
79			STREE
80			*stAlloc(st)
81			STREE *st;
82			{
83			int i;
84
85			if(!st)
86			st = (STREE *)malloc(sizeof(STREE));
87
88			ST_ROOT(st) = qtAlloc();
89
90			QT_CLEAR_CHILDREN(ST_ROOT(st));
91
92			return(st);
93			}
94
95
96			/* Find location of sample point in the DAG and return lowest level
97			containing triangle. "type" indicates whether the point was found
98			to be in interior to the triangle: GT_FACE, on one of its
99			edges GT_EDGE or coinciding with one of its vertices GT_VERTEX.
100			"which" specifies which vertex (0,1,2) or edge (0=v0v1, 1 = v1v2, 2 = v21)
101			*/
102			int
103	gwlarson	3.4	stPoint_locate(st,npt)
104	gwlarson	3.1	STREE *st;
105			FVECT npt;
106			{
107			int i,d,j,id;
108	gwlarson	3.3	QUADTREE rootptr,qtptr;
109	gwlarson	3.1	FVECT v1,v2,v3;
110	gwlarson	3.4	OBJECT os[QT_MAXSET+1],*optr;
111	gwlarson	3.1	FVECT p0,p1,p2;
112	gwlarson	3.2
113	gwlarson	3.1	/* Test each of the root triangles against point id */
114			for(i=0; i < 4; i++)
115			{
116			rootptr = ST_NTH_ROOT_PTR(st,i);
117			stNth_base_verts(st,i,v1,v2,v3);
118			/* Return tri that p falls in */
119	gwlarson	3.3	qtptr = qtRoot_point_locate(rootptr,v1,v2,v3,npt,NULL,NULL,NULL);
120	gwlarson	3.4	if(!qtptr \|\| QT_IS_EMPTY(*qtptr))
121	gwlarson	3.1	continue;
122			/* Get the set */
123	gwlarson	3.4	optr = qtqueryset(*qtptr);
124			for (j = QT_SET_CNT(optr),optr = QT_SET_PTR(optr);j > 0; j--)
125	gwlarson	3.1	{
126			/* Find the first triangle that pt falls */
127			id = QT_SET_NEXT_ELEM(optr);
128	gwlarson	3.5	qtTri_from_id(id,p0,p1,p2,NULL,NULL,NULL,NULL,NULL,NULL);
129	gwlarson	3.4	d = point_in_stri(p0,p1,p2,npt);
130	gwlarson	3.1	if(d)
131	gwlarson	3.4	return(id);
132	gwlarson	3.1	}
133			}
134			return(EMPTY);
135			}
136
137	gwlarson	3.3	QUADTREE
138			*stPoint_locate_cell(st,p,t0,t1,t2)
139	gwlarson	3.1	STREE *st;
140	gwlarson	3.2	FVECT p;
141	gwlarson	3.3	FVECT t0,t1,t2;
142	gwlarson	3.1	{
143			int i,d;
144	gwlarson	3.3	QUADTREE rootptr,qtptr;
145	gwlarson	3.1	FVECT v0,v1,v2;
146
147
148			/* Test each of the root triangles against point id */
149			for(i=0; i < 4; i++)
150			{
151			rootptr = ST_NTH_ROOT_PTR(st,i);
152			stNth_base_verts(st,i,v0,v1,v2);
153	gwlarson	3.4	/* Return quadtree tri that p falls in */
154	gwlarson	3.3	qtptr = qtRoot_point_locate(rootptr,v0,v1,v2,p,t0,t1,t2);
155			if(qtptr)
156			return(qtptr);
157	gwlarson	3.1	} /* Point not found */
158	gwlarson	3.3	return(NULL);
159	gwlarson	3.1	}
160
161	gwlarson	3.3
162	gwlarson	3.1	int
163	gwlarson	3.2	stAdd_tri(st,id,v0,v1,v2)
164	gwlarson	3.1	STREE *st;
165			int id;
166	gwlarson	3.2	FVECT v0,v1,v2;
167	gwlarson	3.1	{
168
169			int i,found;
170			QUADTREE *rootptr;
171	gwlarson	3.2	FVECT t0,t1,t2;
172
173	gwlarson	3.1	found = 0;
174			for(i=0; i < 4; i++)
175			{
176			rootptr = ST_NTH_ROOT_PTR(st,i);
177	gwlarson	3.2	stNth_base_verts(st,i,t0,t1,t2);
178	gwlarson	3.4	found \|= qtRoot_add_tri(rootptr,t0,t1,t2,v0,v1,v2,id,0);
179	gwlarson	3.1	}
180			return(found);
181			}
182
183			int
184			stApply_to_tri_cells(st,v0,v1,v2,func,arg)
185			STREE *st;
186			FVECT v0,v1,v2;
187			int (*func)();
188	gwlarson	3.4	int *arg;
189	gwlarson	3.1	{
190			int i,found;
191			QUADTREE *rootptr;
192			FVECT t0,t1,t2;
193
194			found = 0;
195	gwlarson	3.4	func(ST_ROOT_PTR(st),arg);
196			QT_SET_FLAG(ST_ROOT(st));
197	gwlarson	3.1	for(i=0; i < 4; i++)
198			{
199			rootptr = ST_NTH_ROOT_PTR(st,i);
200			stNth_base_verts(st,i,t0,t1,t2);
201			found \|= qtApply_to_tri_cells(rootptr,v0,v1,v2,t0,t1,t2,func,arg);
202			}
203			return(found);
204			}
205
206
207
208
209			int
210			stRemove_tri(st,id,v0,v1,v2)
211			STREE *st;
212			int id;
213			FVECT v0,v1,v2;
214			{
215
216			int i,found;
217			QUADTREE *rootptr;
218			FVECT t0,t1,t2;
219
220			found = 0;
221			for(i=0; i < 4; i++)
222			{
223			rootptr = ST_NTH_ROOT_PTR(st,i);
224			stNth_base_verts(st,i,t0,t1,t2);
225			found \|= qtRemove_tri(rootptr,id,v0,v1,v2,t0,t1,t2);
226			}
227			return(found);
228			}
229
230	gwlarson	3.4	int
231	gwlarson	3.5	stVisit_tri_edges(st,t0,t1,t2,func,arg1,arg2,arg3)
232	gwlarson	3.4	STREE *st;
233			FVECT t0,t1,t2;
234			int (*func)();
235	gwlarson	3.5	int arg1,arg2,arg3;
236	gwlarson	3.4	{
237			int id,i,w;
238			QUADTREE *rootptr;
239			FVECT q0,q1,q2,v[3],i_pt;
240	gwlarson	3.3
241	gwlarson	3.4	VCOPY(v[0],t0); VCOPY(v[1],t1); VCOPY(v[2],t2);
242			w = -1;
243	gwlarson	3.5	QT_SET_FLAG(ST_ROOT(st));
244	gwlarson	3.4	for(i=0; i < 4; i++)
245			{
246			#ifdef TEST_DRIVER
247			Pick_cnt = 0;
248			#endif
249			rootptr = ST_NTH_ROOT_PTR(st,i);
250			stNth_base_verts(st,i,q0,q1,q2);
251			/* Return quadtree tri that p falls in */
252			if(!point_in_stri(q0,q1,q2,v[0]))
253			continue;
254	gwlarson	3.5	#ifdef TEST_DRIVER
255			id = qtRoot_visit_tri_edges(rootptr,q0,q1,q2,v,i_pt,&w,
256			func,arg1,arg2,arg3);
257			#else
258			id = qtRoot_visit_tri_edgesi(rootptr,q0,q1,q2,v,i_pt,&w,
259			func,arg1,arg2,arg3);
260			#endif
261	gwlarson	3.4	if(id == INVALID)
262			{
263			#ifdef DEBUG
264			eputs("stVisit_tri_edges(): Unable to trace edges\n");
265			#endif
266			return(INVALID);
267			}
268			if(id == QT_DONE)
269			return(*arg1);
270
271			/* Crossed over to next cell: id = nbr */
272			while(1)
273			{
274			/* test if ray crosses plane between this quadtree triangle and
275			its neighbor- if it does then find intersection point with
276			ray and plane- this is the new origin
277			*/
278			i = stTri_nbrs[i][id];
279			rootptr = ST_NTH_ROOT_PTR(st,i);
280			stNth_base_verts(st,i,q0,q1,q2);
281	gwlarson	3.5	#ifdef TEST_DRIVER
282			id=qtRoot_visit_tri_edges(rootptr,q0,q1,q2,v,i_pt,&w,
283			func,arg1,arg2,arg3);
284			#else
285			id=qtRoot_visit_tri_edgesi(rootptr,q0,q1,q2,v,i_pt,&w,
286			func,arg1,arg2,arg3);
287			#endif
288	gwlarson	3.4	if(id == QT_DONE)
289			return(*arg1);
290			if(id == INVALID)
291			{
292			#ifdef DEBUG
293			eputs("stVisit_tri_edges(): point not found\n");
294			#endif
295			return(INVALID);
296			}
297
298			}
299			} /* Point not found */
300			return(INVALID);
301			}
302
303			int
304			stTrace_ray(st,orig,dir,func,arg1,arg2)
305			STREE *st;
306			FVECT orig,dir;
307			int (*func)();
308			int *arg1,arg2;
309			{
310			int id,i;
311			QUADTREE *rootptr;
312			FVECT q0,q1,q2,o,n;
313			double pd,t;
314
315			VCOPY(o,orig);
316			for(i=0; i < 4; i++)
317			{
318			#ifdef TEST_DRIVER
319			Pick_cnt = 0;
320			#endif
321			rootptr = ST_NTH_ROOT_PTR(st,i);
322			stNth_base_verts(st,i,q0,q1,q2);
323			/* Return quadtree tri that p falls in */
324			id= qtRoot_trace_ray(rootptr,q0,q1,q2,o,dir,func,arg1,arg2);
325			if(id == INVALID)
326			continue;
327			if(id == QT_DONE)
328			return(*arg1);
329
330			/* Crossed over to next cell: id = nbr */
331			while(1)
332			{
333			/* test if ray crosses plane between this quadtree triangle and
334			its neighbor- if it does then find intersection point with
335			ray and plane- this is the new origin
336			*/
337			if(id==0)
338			VCROSS(n,q1,q2);
339			else
340			if(id==1)
341			VCROSS(n,q2,q0);
342			else
343			VCROSS(n,q0,q1);
344
345			/* Ray does not cross into next cell: done and tri not found*/
346			if(!intersect_ray_plane(orig,dir,n,0.0,NULL,o))
347			return(INVALID);
348
349			VSUM(o,o,dir,10*FTINY);
350			i = stTri_nbrs[i][id];
351			rootptr = ST_NTH_ROOT_PTR(st,i);
352			stNth_base_verts(st,i,q0,q1,q2);
353			id = qtRoot_trace_ray(rootptr,q0,q1,q2,o,dir,func,arg1,arg2);
354			if(id == QT_DONE)
355			return(*arg1);
356			if(id == INVALID)
357			return(INVALID);
358
359			}
360			} /* Point not found */
361			return(INVALID);
362			}
363
364
365
366	gwlarson	3.5	stVisit_tri_interior(st,t0,t1,t2,func,arg1,arg2,arg3)
367	gwlarson	3.4	STREE *st;
368			FVECT t0,t1,t2;
369			int (*func)();
370	gwlarson	3.5	int arg1,arg2,arg3;
371	gwlarson	3.4	{
372			int i;
373			QUADTREE *rootptr;
374			FVECT q0,q1,q2;
375
376			for(i=0; i < 4; i++)
377			{
378			rootptr = ST_NTH_ROOT_PTR(st,i);
379			stNth_base_verts(st,i,q0,q1,q2);
380	gwlarson	3.5	qtVisit_tri_interior(rootptr,q0,q1,q2,t0,t1,t2,0,func,arg1,arg2,arg3);
381	gwlarson	3.4	}
382			}
383
384
385			int
386	gwlarson	3.5	stApply_to_tri(st,t0,t1,t2,edge_func,interior_func,arg1,arg2)
387	gwlarson	3.4	STREE *st;
388			FVECT t0,t1,t2;
389			int (edge_func)(),(interior_func)();
390	gwlarson	3.5	int arg1,*arg2;
391	gwlarson	3.4	{
392			int f;
393			FVECT dir;
394
395			/* First add all of the leaf cells lying on the triangle perimeter:
396			mark all cells seen on the way
397	gwlarson	3.3	*/
398	gwlarson	3.4	f = 0;
399			/* Visit cells along edges of the tri */
400	gwlarson	3.3
401	gwlarson	3.5	stVisit_tri_edges(st,t0,t1,t2,edge_func,&f,arg1,arg2);
402	gwlarson	3.4
403			/* Now visit interior */
404			if(QT_FLAG_FILL_TRI(f) \|\| QT_FLAG_UPDATE(f))
405	gwlarson	3.5	stVisit_tri_interior(st,t0,t1,t2,interior_func,&f,arg1,arg2);
406	gwlarson	3.3	}
407	gwlarson	3.5
408	gwlarson	3.3
409	gwlarson	3.4
410
411