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.5 by gwlarson, Wed Sep 16 18:16:29 1998 UTC

#	Line 8 | Line 8 | static char SCCSid[] = "$SunId$ SGI";
8		* sm_stree.c
9		*/
10		#include "standard.h"
11	–	#include "object.h"
12	–
11		#include "sm_geom.h"
12		#include "sm_stree.h"
13
16	–
14		/* Define 4 vertices on the sphere to create a tetrahedralization on
15		the sphere: triangles are as follows:
16	<	(0,1,2),(0,2,3), (0,3,1), (1,3,2)
16	>	(2,1,0),(3,2,0), (1,3,0), (2,3,1)
17		*/
18
19	+	#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		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	<	int stTri_verts[4][3] = { {2,1,0},
28	<	{3,2,0},
28	<	{1,3,0},
29	<	{2,3,1}};
27	>	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
30		stNth_base_verts(st,i,v1,v2,v3)
31		STREE *st;
#	Line 101 | Line 100 | STREE *st;
100		"which" specifies which vertex (0,1,2) or edge (0=v0v1, 1 = v1v2, 2 = v21)
101		*/
102		int
103	<	stPoint_locate(st,npt,type,which)
103	>	stPoint_locate(st,npt)
104		STREE *st;
105		FVECT npt;
107	–	char *type,*which;
106		{
107		int i,d,j,id;
108	<	QUADTREE *rootptr,qt;
108	>	QUADTREE *rootptr,*qtptr;
109		FVECT v1,v2,v3;
110	<	OBJECT os[MAXSET+1],*optr;
113	<	char w;
110	>	OBJECT os[QT_MAXSET+1],*optr;
111		FVECT p0,p1,p2;
112
113		/* Test each of the root triangles against point id */
#	Line 119 | Line 116 | stPoint_locate(st,npt,type,which)
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	<	qt = qtRoot_point_locate(rootptr,v1,v2,v3,npt,type,which);
120	<	if(QT_IS_EMPTY(qt))
119	>	qtptr = qtRoot_point_locate(rootptr,v1,v2,v3,npt,NULL,NULL,NULL);
120	>	if(!qtptr || QT_IS_EMPTY(*qtptr))
121		continue;
122		/* Get the set */
123	<	qtgetset(os,qt);
124	<	for (j = QT_SET_CNT(os),optr = QT_SET_PTR(os); j > 0; j--)
123	>	optr = qtqueryset(*qtptr);
124	>	for (j = QT_SET_CNT(optr),optr = QT_SET_PTR(optr);j > 0; j--)
125		{
126		/* Find the first triangle that pt falls */
127		id = QT_SET_NEXT_ELEM(optr);
128	<	qtTri_verts_from_id(id,p0,p1,p2);
129	<	d = test_single_point_against_spherical_tri(p0,p1,p2,npt,&w);
128	>	qtTri_from_id(id,p0,p1,p2,NULL,NULL,NULL,NULL,NULL,NULL);
129	>	d = point_in_stri(p0,p1,p2,npt);
130		if(d)
131	<	{
135	<	if(type)
136	<	*type = d;
137	<	if(which)
138	<	*which = w;
139	<	return(id);
140	<	}
131	>	return(id);
132		}
133		}
143	–	if(which)
144	–	*which = 0;
145	–	if(type)
146	–	*type = 0;
134		return(EMPTY);
135		}
136
137	<	int
138	<	stPoint_locate_cell(st,p,type,which)
137	>	QUADTREE
138	>	*stPoint_locate_cell(st,p,t0,t1,t2)
139		STREE *st;
140		FVECT p;
141	<	char *type,*which;
141	>	FVECT t0,t1,t2;
142		{
143		int i,d;
144	<	QUADTREE *rootptr,qt;
144	>	QUADTREE *rootptr,*qtptr;
145		FVECT v0,v1,v2;
146
147
#	Line 163 | Line 150 | stPoint_locate_cell(st,p,type,which)
150		{
151		rootptr = ST_NTH_ROOT_PTR(st,i);
152		stNth_base_verts(st,i,v0,v1,v2);
153	<	/* Return tri that p falls in */
154	<	qt = qtRoot_point_locate(rootptr,v0,v1,v2,p,type,which);
155	<	/* NOTE: For now return only one triangle */
156	<	if(!QT_IS_EMPTY(qt))
170	<	return(qt);
153	>	/* Return quadtree tri that p falls in */
154	>	qtptr = qtRoot_point_locate(rootptr,v0,v1,v2,p,t0,t1,t2);
155	>	if(qtptr)
156	>	return(qtptr);
157		}    /* Point not found */
158	<	if(which)
173	<	*which = 0;
174	<	if(type)
175	<	*type = 0;
176	<	return(EMPTY);
158	>	return(NULL);
159		}
160
161	+
162		int
163		stAdd_tri(st,id,v0,v1,v2)
164		STREE *st;
#	Line 192 | Line 175 | FVECT v0,v1,v2;
175		{
176		rootptr = ST_NTH_ROOT_PTR(st,i);
177		stNth_base_verts(st,i,t0,t1,t2);
178	<	found |= qtAdd_tri(rootptr,id,v0,v1,v2,t0,t1,t2,0);
178	>	found |= qtRoot_add_tri(rootptr,t0,t1,t2,v0,v1,v2,id,0);
179		}
180		return(found);
181		}
#	Line 202 | Line 185 | stApply_to_tri_cells(st,v0,v1,v2,func,arg)
185		STREE *st;
186		FVECT v0,v1,v2;
187		int (*func)();
188	<	char *arg;
188	>	int *arg;
189		{
190		int i,found;
191		QUADTREE *rootptr;
192		FVECT t0,t1,t2;
193
194		found = 0;
195	+	func(ST_ROOT_PTR(st),arg);
196	+	QT_SET_FLAG(ST_ROOT(st));
197		for(i=0; i < 4; i++)
198		{
199		rootptr = ST_NTH_ROOT_PTR(st,i);
#	Line 240 | Line 225 | FVECT v0,v1,v2;
225		found |= qtRemove_tri(rootptr,id,v0,v1,v2,t0,t1,t2);
226		}
227		return(found);
228	+	}
229	+
230	+	int
231	+	stVisit_tri_edges(st,t0,t1,t2,func,arg1,arg2,arg3)
232	+	STREE *st;
233	+	FVECT t0,t1,t2;
234	+	int (*func)();
235	+	int *arg1,arg2,*arg3;
236	+	{
237	+	int id,i,w;
238	+	QUADTREE *rootptr;
239	+	FVECT q0,q1,q2,v[3],i_pt;
240	+
241	+	VCOPY(v[0],t0); VCOPY(v[1],t1); VCOPY(v[2],t2);
242	+	w = -1;
243	+	QT_SET_FLAG(ST_ROOT(st));
244	+	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	+	#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	+	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	+	#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	+	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	+	stVisit_tri_interior(st,t0,t1,t2,func,arg1,arg2,arg3)
367	+	STREE *st;
368	+	FVECT t0,t1,t2;
369	+	int (*func)();
370	+	int *arg1,arg2,*arg3;
371	+	{
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	+	qtVisit_tri_interior(rootptr,q0,q1,q2,t0,t1,t2,0,func,arg1,arg2,arg3);
381	+	}
382	+	}
383	+
384	+
385	+	int
386	+	stApply_to_tri(st,t0,t1,t2,edge_func,interior_func,arg1,arg2)
387	+	STREE *st;
388	+	FVECT t0,t1,t2;
389	+	int (*edge_func)(),(*interior_func)();
390	+	int arg1,*arg2;
391	+	{
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	+	*/
398	+	f = 0;
399	+	/* Visit cells along edges of the tri */
400	+
401	+	stVisit_tri_edges(st,t0,t1,t2,edge_func,&f,arg1,arg2);
402	+
403	+	/* Now visit interior */
404	+	if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f))
405	+	stVisit_tri_interior(st,t0,t1,t2,interior_func,&f,arg1,arg2);
406		}
407
408

Diff Legend

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