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\
#	Content
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	* 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	*/
15	#include "standard.h"
16	#include "sm_flag.h"
17	#include "sm_geom.h"
18	#include "sm_qtree.h"
19	#include "sm_stree.h"
20
21	#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	/* 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
37
38	/* Initializes an stree structure with origin 'center':
39	Frees existing quadtrees hanging off of the roots
40	*/
41	stInit(st)
42	STREE *st;
43	{
44	ST_TOP_ROOT(st) = qtAlloc();
45	ST_BOTTOM_ROOT(st) = qtAlloc();
46	ST_INIT_ROOT(st);
47	}
48
49	/* Frees the children of the 2 quadtrees rooted at st,
50	Does not free root nodes: just clears
51	*/
52	stClear(st)
53	STREE *st;
54	{
55	qtDone();
56	stInit(st);
57	}
58
59	/* Allocates a stree structure and creates octahedron base */
60	STREE
61	*stAlloc(st)
62	STREE *st;
63	{
64	int i,m;
65	FVECT v0,v1,v2;
66	FVECT n;
67
68	if(!st)
69	if(!(st = (STREE *)malloc(sizeof(STREE))))
70	error(SYSTEM,"stAlloc(): Unable to allocate memory\n");
71
72	/* 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
78	/* 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	return(st);
94	}
95
96
97	/* Return quadtree leaf node containing point 'p'*/
98	QUADTREE
99	stPoint_locate(st,p)
100	STREE *st;
101	FVECT p;
102	{
103	int i;
104	QUADTREE root,qt;
105
106	/* Find root quadtree that contains p */
107	i = stPoint_in_root(p);
108	root = ST_NTH_ROOT(st,i);
109
110	/* 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	}
115
116	/* Add triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
117	FALSE on error, TRUE otherwise
118	*/
119
120	stAdd_tri(st,id,t0,t1,t2)
121	STREE *st;
122	int id;
123	FVECT t0,t1,t2;
124	{
125	int i;
126	QUADTREE root;
127
128	for(i=0; i < ST_NUM_ROOT_NODES; i++)
129	{
130	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	}
134	}
135
136	/* Remove triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
137	FALSE on error, TRUE otherwise
138	*/
139
140	stRemove_tri(st,id,t0,t1,t2)
141	STREE *st;
142	int id;
143	FVECT t0,t1,t2;
144	{
145	int i;
146	QUADTREE root;
147
148	for(i=0; i < ST_NUM_ROOT_NODES; i++)
149	{
150	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	}
154	}
155
156	/* 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	STREE *st;
162	FVECT t0,t1,t2;
163	int (func)(),fptr;
164	int *argptr;
165	{
166	int id,i,w,next;
167	QUADTREE root;
168	FVECT v[3],i_pt;
169
170	VCOPY(v[0],t0); VCOPY(v[1],t1); VCOPY(v[2],t2);
171	w = -1;
172
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
185	/* 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	}
201
202	/* Trace ray 'orig-dir' through stree and apply 'func(qtptr,f,argptr)' at each
203	node that it intersects
204	*/
205	int
206	stTrace_ray(st,orig,dir,func,argptr)
207	STREE *st;
208	FVECT orig,dir;
209	int (*func)();
210	int *argptr;
211	{
212	int next,last,i,f=0;
213	QUADTREE root;
214	FVECT o,n;
215	double pd,t;
216
217	VCOPY(o,orig);
218
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
230	/* 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	/* Ray does not cross into next cell: done and tri not found*/
242	return(FALSE);
243
244	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	}
255
256
257	/* 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	STREE *st;
263	FVECT t0,t1,t2;
264	int (func)(),f;
265	int *argptr;
266	{
267	int i;
268	QUADTREE root;
269	FVECT n0,n1,n2;
270
271	/* 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	{
278	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	}
283	}
284
285	/* 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	int
290	stApply_to_tri(st,t0,t1,t2,edge_func,tri_func,argptr)
291	STREE *st;
292	FVECT t0,t1,t2;
293	int (edge_func)(),(tri_func)();
294	int *argptr;
295	{
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	*/
302	f = 0;
303	/* Visit cells along edges of the tri */
304	stVisit_tri_edges(st,t0,t1,t2,edge_func,&f,argptr);
305
306	/* Now visit All cells interior */
307	if(QT_FLAG_FILL_TRI(f) \|\| QT_FLAG_UPDATE(f))
308	stVisit_tri(st,t0,t1,t2,tri_func,&f,argptr);
309	}
310
311
312
313
314
315
316
317
318