ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/Development/ray/src/hd/sm_stree.c

Comparing ray/src/hd/sm_stree.c (file contents):
Revision 3.2 by gwlarson, Thu Aug 20 16:47:22 1998 UTC vs.
Revision 3.6 by gwlarson, Tue Oct 6 18:18:54 1998 UTC

#	Line 6 | Line 6 | static char SCCSid[] = "$SunId$ SGI";
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 "object.h"
12	<
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
17	–	/* Define 4 vertices on the sphere to create a tetrahedralization on
18	–	the sphere: triangles are as follows:
19	–	(0,1,2),(0,2,3), (0,3,1), (1,3,2)
20	–	*/
37
38	<	FVECT stDefault_base[4] = { {SQRT3_INV, SQRT3_INV, SQRT3_INV},
39	<	{-SQRT3_INV, -SQRT3_INV, SQRT3_INV},
40	<	{-SQRT3_INV, SQRT3_INV, -SQRT3_INV},
41	<	{SQRT3_INV, -SQRT3_INV, -SQRT3_INV}};
26	<	int stTri_verts[4][3] = { {2,1,0},
27	<	{3,2,0},
28	<	{1,3,0},
29	<	{2,3,1}};
30	<
31	<	stNth_base_verts(st,i,v1,v2,v3)
38	>	/* Initializes an stree structure with origin 'center':
39	>	Frees existing quadtrees hanging off of the roots
40	>	*/
41	>	stInit(st)
42		STREE *st;
33	–	int i;
34	–	FVECT v1,v2,v3;
43		{
44	<	VCOPY(v1,ST_NTH_BASE(st,stTri_verts[i][0]));
45	<	VCOPY(v2,ST_NTH_BASE(st,stTri_verts[i][1]));
46	<	VCOPY(v3,ST_NTH_BASE(st,stTri_verts[i][2]));
44	>	ST_TOP_ROOT(st) = qtAlloc();
45	>	ST_BOTTOM_ROOT(st) = qtAlloc();
46	>	ST_INIT_ROOT(st);
47		}
48
49	<	/* Frees the 4 quadtrees rooted at st */
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;
53	>	STREE *st;
54		{
55	<	int i;
56	<
47	<	/* stree always has 4 children corresponding to the base tris
48	<	*/
49	<	for (i = 0; i < 4; i++)
50	<	qtFree(ST_NTH_ROOT(st, i));
51	<
52	<	QT_CLEAR_CHILDREN(ST_ROOT(st));
53	<
55	>	qtDone();
56	>	stInit(st);
57		}
58
59	<
59	>	/* Allocates a stree structure  and creates octahedron base */
60		STREE
61	<	*stInit(st,center,base)
61	>	*stAlloc(st)
62		STREE *st;
60	–	FVECT  center,base[4];
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	<	if(base)
73	<	ST_SET_BASE(st,base);
74	<	else
75	<	ST_SET_BASE(st,stDefault_base);
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	<	ST_SET_CENTER(st,center);
79	<	stClear(st);
80	<
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	<	/* "base" defines 4 vertices on the sphere to create a tetrahedralization on
98	<	the sphere: triangles are as follows:(0,1,2),(0,2,3), (0,3,1), (1,3,2)
99	<	if base is null: does default.
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	<	*/
107	<	STREE
108	<	*stAlloc(st)
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	<	if(!st)
129	<	st = (STREE *)malloc(sizeof(STREE));
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	<	ST_ROOT(st) = qtAlloc();
137	<
138	<	QT_CLEAR_CHILDREN(ST_ROOT(st));
136	>	/* Remove triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
137	>	FALSE on error, TRUE otherwise
138	>	*/
139
140	<	return(st);
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	<
157	<	/* Find location of sample point in the DAG and return lowest level
98	<	containing triangle. "type" indicates whether the point was found
99	<	to be in interior to the triangle: GT_FACE, on one of its
100	<	edges GT_EDGE or coinciding with one of its vertices GT_VERTEX.
101	<	"which" specifies which vertex (0,1,2) or edge (0=v0v1, 1 = v1v2, 2 = v21)
156	>	/* Visit all nodes that are intersected by the edges of triangle 't0,t1,t2'
157	>	and apply 'func'
158		*/
159	<	int
160	<	stPoint_locate(st,npt,type,which)
161	<	STREE *st;
162	<	FVECT npt;
163	<	char *type,*which;
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 i,d,j,id;
167	<	QUADTREE *rootptr,qt;
168	<	FVECT v1,v2,v3;
112	<	OBJECT os[MAXSET+1],*optr;
113	<	char w;
114	<	FVECT p0,p1,p2;
166	>	int id,i,w,next;
167	>	QUADTREE root;
168	>	FVECT v[3],i_pt;
169
170	<	/* Test each of the root triangles against point id */
171	<	for(i=0; i < 4; i++)
172	<	{
173	<	rootptr = ST_NTH_ROOT_PTR(st,i);
174	<	stNth_base_verts(st,i,v1,v2,v3);
175	<	/* Return tri that p falls in */
176	<	qt = qtRoot_point_locate(rootptr,v1,v2,v3,npt,type,which);
177	<	if(QT_IS_EMPTY(qt))
178	<	continue;
179	<	/* Get the set */
180	<	qtgetset(os,qt);
181	<	for (j = QT_SET_CNT(os),optr = QT_SET_PTR(os); j > 0; j--)
182	<	{
183	<	/* Find the first triangle that pt falls */
184	<	id = QT_SET_NEXT_ELEM(optr);
185	<	qtTri_verts_from_id(id,p0,p1,p2);
186	<	d = test_single_point_against_spherical_tri(p0,p1,p2,npt,&w);
187	<	if(d)
188	<	{
189	<	if(type)
190	<	*type = d;
191	<	if(which)
192	<	*which = w;
193	<	return(id);
194	<	}
195	<	}
196	<	}
197	<	if(which)
198	<	*which = 0;
199	<	if(type)
146	<	*type = 0;
147	<	return(EMPTY);
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	<	stPoint_locate_cell(st,p,type,which)
207	<	STREE *st;
208	<	FVECT p;
209	<	char *type,*which;
206	>	stTrace_ray(st,orig,dir,func,argptr)
207	>	STREE *st;
208	>	FVECT orig,dir;
209	>	int (*func)();
210	>	int *argptr;
211		{
212	<	int i,d;
213	<	QUADTREE *rootptr,qt;
214	<	FVECT v0,v1,v2;
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	<	/* Test each of the root triangles against point id */
224	<	for(i=0; i < 4; i++)
225	<	{
226	<	rootptr = ST_NTH_ROOT_PTR(st,i);
227	<	stNth_base_verts(st,i,v0,v1,v2);
228	<	/* Return tri that p falls in */
229	<	qt = qtRoot_point_locate(rootptr,v0,v1,v2,p,type,which);
230	<	/* NOTE: For now return only one triangle */
231	<	if(!QT_IS_EMPTY(qt))
232	<	return(qt);
233	<	}    /* Point not found */
234	<	if(which)
235	<	*which = 0;
236	<	if(type)
237	<	*type = 0;
238	<	return(EMPTY);
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	<	int
257	<	stAdd_tri(st,id,v0,v1,v2)
258	<	STREE *st;
259	<	int id;
260	<	FVECT v0,v1,v2;
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	<
268	<	int i,found;
269	<	QUADTREE *rootptr;
188	<	FVECT t0,t1,t2;
267	>	int i;
268	>	QUADTREE root;
269	>	FVECT n0,n1,n2;
270
271	<	found = 0;
272	<	for(i=0; i < 4; i++)
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	<	rootptr = ST_NTH_ROOT_PTR(st,i);
279	<	stNth_base_verts(st,i,t0,t1,t2);
280	<	found |= qtAdd_tri(rootptr,id,v0,v1,v2,t0,t1,t2,0);
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		}
197	–	return(found);
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_cells(st,v0,v1,v2,func,arg)
291	<	STREE *st;
292	<	FVECT v0,v1,v2;
293	<	int (*func)();
294	<	char *arg;
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 i,found;
297	<	QUADTREE *rootptr;
298	<	FVECT t0,t1,t2;
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	<	found = 0;
307	<	for(i=0; i < 4; i++)
308	<	{
214	<	rootptr = ST_NTH_ROOT_PTR(st,i);
215	<	stNth_base_verts(st,i,t0,t1,t2);
216	<	found |= qtApply_to_tri_cells(rootptr,v0,v1,v2,t0,t1,t2,func,arg);
217	<	}
218	<	return(found);
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
224	–	int
225	–	stRemove_tri(st,id,v0,v1,v2)
226	–	STREE *st;
227	–	int id;
228	–	FVECT v0,v1,v2;
229	–	{
230	–
231	–	int i,found;
232	–	QUADTREE *rootptr;
233	–	FVECT t0,t1,t2;
234	–
235	–	found = 0;
236	–	for(i=0; i < 4; i++)
237	–	{
238	–	rootptr = ST_NTH_ROOT_PTR(st,i);
239	–	stNth_base_verts(st,i,t0,t1,t2);
240	–	found |= qtRemove_tri(rootptr,id,v0,v1,v2,t0,t1,t2);
241	–	}
242	–	return(found);
243	–	}
314
315
316

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines (old)
>	Changed lines (new)