ViewVC Help

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

root/radiance/ray/src/hd/sm_qtree.c

Comparing ray/src/hd/sm_qtree.c (file contents):
Revision 3.6 by gwlarson, Wed Sep 16 18:16:29 1998 UTC vs.
Revision 3.7 by gwlarson, Tue Oct 6 18:18:54 1998 UTC

#	Line 14 | Line 14 | static char SCCSid[] = "$SunId$ SGI";
14		*/
15
16		#include "standard.h"
17	<
17	>	#include "sm_flag.h"
18		#include "sm_geom.h"
19		#include "sm_qtree.h"
20
#	Line 27 | Line 27 | int4 *quad_flag= NULL;
27		extern FVECT Pick_v0[500],Pick_v1[500],Pick_v2[500];
28		extern int Pick_cnt,Pick_tri,Pick_samp;
29		extern FVECT Pick_point[500];
30	+
31	+
32		#endif
33	+	int Incnt=0;
34
35		QUADTREE
36		qtAlloc()                       /* allocate a quadtree */
#	Line 46 | Line 49 | qtAlloc()                      /* allocate a quadtree */
49		return(EMPTY);
50		if ((quad_block[QT_BLOCK(freet)] = (QUADTREE *)malloc(
51		QT_BLOCK_SIZE*4*sizeof(QUADTREE))) == NULL)
52	<	return(EMPTY);
52	>	error(SYSTEM,"qtAlloc(): Unable to allocate memory\n");
53
54	+	/* Realloc the per/node flags */
55		quad_flag = (int4 *)realloc((char *)quad_flag,
56	<	(QT_BLOCK(freet)+1)*(QT_BLOCK_SIZE/8));
56	>	(QT_BLOCK(freet)+1)*((QT_BLOCK_SIZE+7)>>3));
57		if (quad_flag == NULL)
58	<	return(EMPTY);
58	>	error(SYSTEM,"qtAlloc(): Unable to allocate memory\n");
59		}
60		treetop += 4;
61		return(freet);
#	Line 60 | Line 64 | qtAlloc()                      /* allocate a quadtree */
64
65		qtClearAllFlags()               /* clear all quadtree branch flags */
66		{
67	<	if (!treetop) return;
68	<	bzero((char *)quad_flag, (QT_BLOCK(treetop-4)+1)*(QT_BLOCK_SIZE/8));
67	>	if (!treetop)
68	>	return;
69	>
70	>	/* Clear the node flags*/
71	>	bzero((char *)quad_flag, (QT_BLOCK(treetop-4)+1)*((QT_BLOCK_SIZE+7)>>3));
72	>	/* Clear set flags */
73	>	qtclearsetflags();
74		}
75
67	–
76		qtFree(qt)                      /* free a quadtree */
77		register QUADTREE  qt;
78		{
#	Line 85 | Line 93 | qtFree(qt)                     /* free a quadtree */
93		qtDone()                        /* free EVERYTHING */
94		{
95		register int    i;
96	<
96	>
97		qtfreeleaves();
98		for (i = 0; i < QT_MAX_BLK; i++)
99		{
#	Line 94 | Line 102 | qtDone()                       /* free EVERYTHING */
102		free((char *)quad_block[i]);
103		quad_block[i] = NULL;
104		}
105	+	/* Free the flags */
106		if (i) free((char *)quad_flag);
107		quad_flag = NULL;
108		quad_free_list = EMPTY;
#	Line 101 | Line 110 | qtDone()                       /* free EVERYTHING */
110		}
111
112		QUADTREE
113	<	*qtLocate_leaf(qtptr,bcoord,t0,t1,t2)
114	<	QUADTREE *qtptr;
115	<	double bcoord[3];
107	<	FVECT t0,t1,t2;
113	>	qtLocate_leaf(qt,bcoord)
114	>	QUADTREE qt;
115	>	BCOORD bcoord[3];
116		{
117		int i;
110	–	QUADTREE *child;
111	–	FVECT a,b,c;
118
119	<	if(QT_IS_TREE(*qtptr))
120	<	{
121	<	i = bary_child(bcoord);
116	<	#ifdef DEBUG_TEST_DRIVER
117	<	qtSubdivide_tri(Pick_v0[Pick_cnt-1],Pick_v1[Pick_cnt-1],
118	<	Pick_v2[Pick_cnt-1],a,b,c);
119	<	qtNth_child_tri(Pick_v0[Pick_cnt-1],Pick_v1[Pick_cnt-1],
120	<	Pick_v2[Pick_cnt-1],a,b,c,i,
121	<	Pick_v0[Pick_cnt],Pick_v1[Pick_cnt],
122	<	Pick_v2[Pick_cnt]);
123	<	Pick_cnt++;
124	<	#endif
119	>	if(QT_IS_TREE(qt))
120	>	{
121	>	i = baryi_child(bcoord);
122
123	<	child = QT_NTH_CHILD_PTR(*qtptr,i);
124	<	if(t0)
125	<	{
126	<	qtSubdivide_tri(t0,t1,t2,a,b,c);
130	<	qtNth_child_tri(t0,t1,t2,a,b,c,i,t0,t1,t2);
131	<	}
132	<	return(qtLocate_leaf(child,bcoord,t0,t1,t2));
133	<	}
134	<	else
135	<	return(qtptr);
123	>	return(qtLocate_leaf(QT_NTH_CHILD(qt,i),bcoord));
124	>	}
125	>	else
126	>	return(qt);
127		}
128
129	<
129	>	/*
130	>	Return the quadtree node containing pt. It is assumed that pt is in
131	>	the root node qt with ws vertices q0,q1,q2 and plane equation peq.
132	>	*/
133		QUADTREE
134	<	*qtRoot_point_locate(qtptr,v0,v1,v2,pt,t0,t1,t2)
135	<	QUADTREE *qtptr;
136	<	FVECT v0,v1,v2;
134	>	qtRoot_point_locate(qt,q0,q1,q2,peq,pt)
135	>	QUADTREE qt;
136	>	FVECT q0,q1,q2;
137	>	FPEQ peq;
138		FVECT pt;
144	–	FVECT t0,t1,t2;
139		{
146	–	int d;
140		int i,x,y;
141	<	QUADTREE *child;
142	<	FVECT n,i_pt,a,b,c;
143	<	double pd,bcoord[3];
141	>	FVECT i_pt;
142	>	double bcoord[3];
143	>	BCOORD bcoordi[3];
144
145	<	/* Determine if point lies within pyramid (and therefore
153	<	inside a spherical quadtree cell):GT_INTERIOR, on one of the
154	<	pyramid sides (and on cell edge):GT_EDGE(1,2 or 3),
155	<	or on pyramid vertex (and on cell vertex):GT_VERTEX(1,2, or 3).
156	<	For each triangle edge: compare the
157	<	point against the plane formed by the edge and the view center
158	<	*/
159	<	d = point_in_stri(v0,v1,v2,pt);
160	<
161	<
162	<	/* Not in this triangle */
163	<	if(!d)
164	<	return(NULL);
165	<
166	<	/* Will return lowest level triangle containing point: It the
145	>	/* Will return lowest level triangle containing point: It the
146		point is on an edge or vertex: will return first associated
147		triangle encountered in the child traversal- the others can
148		be derived using triangle adjacency information
149		*/
150	<	if(QT_IS_TREE(*qtptr))
150	>	if(QT_IS_TREE(qt))
151		{
152		/* Find the intersection point */
153	<	tri_plane_equation(v0,v1,v2,n,&pd,FALSE);
175	<	intersect_vector_plane(pt,n,pd,NULL,i_pt);
153	>	intersect_vector_plane(pt,peq,NULL,i_pt);
154
155	<	i = max_index(n,NULL);
156	<	x = (i+1)%3;
179	<	y = (i+2)%3;
155	>	x = FP_X(peq);
156	>	y = FP_Y(peq);
157		/* Calculate barycentric coordinates of i_pt */
158	<	bary2d(v0[x],v0[y],v1[x],v1[y],v2[x],v2[y],i_pt[x],i_pt[y],bcoord);
158	>	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],i_pt[x],i_pt[y],bcoord);
159	>
160	>	/* convert to integer coordinate */
161	>	convert_dtol(bcoord,bcoordi);
162
163	<	i = bary_child(bcoord);
164	<	child = QT_NTH_CHILD_PTR(*qtptr,i);
165	<	#ifdef DEBUG_TEST_DRIVER
186	<	Pick_cnt = 0;
187	<	VCOPY(Pick_v0[0],v0);
188	<	VCOPY(Pick_v1[0],v1);
189	<	VCOPY(Pick_v2[0],v2);
190	<	Pick_cnt++;
191	<	qtSubdivide_tri(Pick_v0[Pick_cnt-1],Pick_v1[Pick_cnt-1],
192	<	Pick_v2[Pick_cnt-1],a,b,c);
193	<	qtNth_child_tri(Pick_v0[Pick_cnt-1],Pick_v1[Pick_cnt-1],
194	<	Pick_v2[Pick_cnt-1],a,b,c,i,
195	<	Pick_v0[Pick_cnt],Pick_v1[Pick_cnt],
196	<	Pick_v2[Pick_cnt]);
197	<	Pick_cnt++;
198	<	#endif
199	<	if(t0)
200	<	{
201	<	qtSubdivide_tri(v0,v1,v2,a,b,c);
202	<	qtNth_child_tri(v0,v1,v2,a,b,c,i,t0,t1,t2);
203	<	}
204	<	return(qtLocate_leaf(child,bcoord,t0,t1,t2));
163	>	i = baryi_child(bcoordi);
164	>
165	>	return(qtLocate_leaf(QT_NTH_CHILD(qt,i),bcoordi));
166		}
167		else
168	<	{
208	<	if(t0)
209	<	{
210	<	VCOPY(t0,v0);
211	<	VCOPY(t1,v1);
212	<	VCOPY(t2,v2);
213	<	}
214	<	return(qtptr);
215	<	}
168	>	return(qt);
169		}
170
171
219	–	QUADTREE
220	–	qtSubdivide(qtptr)
221	–	QUADTREE *qtptr;
222	–	{
223	–	QUADTREE node;
224	–	node = qtAlloc();
225	–	QT_CLEAR_CHILDREN(node);
226	–	*qtptr = node;
227	–	return(node);
228	–	}
172
173
231	–	QUADTREE
232	–	qtSubdivide_nth_child(qt,n)
233	–	QUADTREE qt;
234	–	int n;
235	–	{
236	–	QUADTREE node;
237	–
238	–	node = qtSubdivide(&(QT_NTH_CHILD(qt,n)));
239	–
240	–	return(node);
241	–	}
242	–
174		/* for triangle v0-v1-v2- returns a,b,c: children are:
175
176		v2                     0: v0,a,c
#	Line 252 | Line 183 | int n;
183		a
184		*/
185
255	–	qtSubdivide_tri(v0,v1,v2,a,b,c)
256	–	FVECT v0,v1,v2;
257	–	FVECT a,b,c;
258	–	{
259	–	EDGE_MIDPOINT_VEC3(a,v0,v1);
260	–	EDGE_MIDPOINT_VEC3(b,v1,v2);
261	–	EDGE_MIDPOINT_VEC3(c,v2,v0);
262	–	}
186
187		qtNth_child_tri(v0,v1,v2,a,b,c,i,r0,r1,r2)
188		FVECT v0,v1,v2;
#	Line 268 | Line 191 | int i;
191		FVECT r0,r1,r2;
192		{
193
194	<	switch(i){
195	<	case 0:
196	<	VCOPY(r0,v0); VCOPY(r1,a);    VCOPY(r2,c);
197	<	break;
198	<	case 1:
199	<	VCOPY(r0,a); VCOPY(r1,v1);    VCOPY(r2,b);
200	<	break;
201	<	case 2:
202	<	VCOPY(r0,c); VCOPY(r1,b);    VCOPY(r2,v2);
203	<	break;
204	<	case 3:
205	<	VCOPY(r0,b); VCOPY(r1,c);    VCOPY(r2,a);
206	<	break;
194	>	if(!a)
195	>	{
196	>	/* Caution: r's must not be equal to v's:will be incorrect */
197	>	switch(i){
198	>	case 0:
199	>	VCOPY(r0,v0);
200	>	EDGE_MIDPOINT_VEC3(r1,v0,v1);
201	>	EDGE_MIDPOINT_VEC3(r2,v2,v0);
202	>	break;
203	>	case 1:
204	>	EDGE_MIDPOINT_VEC3(r0,v0,v1);
205	>	VCOPY(r1,v1);
206	>	EDGE_MIDPOINT_VEC3(r2,v1,v2);
207	>	break;
208	>	case 2:
209	>	EDGE_MIDPOINT_VEC3(r0,v2,v0);
210	>	EDGE_MIDPOINT_VEC3(r1,v1,v2);
211	>	VCOPY(r2,v2);
212	>	break;
213	>	case 3:
214	>	EDGE_MIDPOINT_VEC3(r0,v1,v2);
215	>	EDGE_MIDPOINT_VEC3(r1,v2,v0);
216	>	EDGE_MIDPOINT_VEC3(r2,v0,v1);
217	>	break;
218	>	}
219		}
220	+	else
221	+	{
222	+	switch(i){
223	+	case 0:
224	+	VCOPY(r0,v0); VCOPY(r1,a);    VCOPY(r2,c);
225	+	break;
226	+	case 1:
227	+	VCOPY(r0,a); VCOPY(r1,v1);    VCOPY(r2,b);
228	+	break;
229	+	case 2:
230	+	VCOPY(r0,c); VCOPY(r1,b);    VCOPY(r2,v2);
231	+	break;
232	+	case 3:
233	+	VCOPY(r0,b); VCOPY(r1,c);    VCOPY(r2,a);
234	+	break;
235	+	}
236	+	}
237		}
238
239		/* Add triangle "id" to all leaf level cells that are children of
#	Line 292 | Line 244 | threshold- the cell is split- and the triangle must be
244		into the new child cells: it is assumed that "v1,v2,v3" are normalized
245		*/
246
247	<	int
248	<	qtRoot_add_tri(qtptr,q0,q1,q2,t0,t1,t2,id,n)
249	<	QUADTREE *qtptr;
247	>	QUADTREE
248	>	qtRoot_add_tri(qt,q0,q1,q2,t0,t1,t2,id,n)
249	>	QUADTREE qt;
250		FVECT q0,q1,q2;
251		FVECT t0,t1,t2;
252	<	int id;
301	<	int n;
252	>	int id,n;
253		{
254	<	int test;
255	<	int found;
254	>	if(stri_intersect(q0,q1,q2,t0,t1,t2))
255	>	qt = qtAdd_tri(qt,q0,q1,q2,t0,t1,t2,id,n);
256
257	<	test = stri_intersect(q0,q1,q2,t0,t1,t2);
307	<	if(!test)
308	<	return(FALSE);
309	<
310	<	found = qtAdd_tri(qtptr,q0,q1,q2,t0,t1,t2,id,n);
311	<
312	<	return(found);
257	>	return(qt);
258		}
259
260	<	int
261	<	qtAdd_tri(qtptr,q0,q1,q2,t0,t1,t2,id,n)
262	<	QUADTREE *qtptr;
260	>	QUADTREE
261	>	qtRoot_remove_tri(qt,q0,q1,q2,t0,t1,t2,id,n)
262	>	QUADTREE qt;
263		FVECT q0,q1,q2;
264		FVECT t0,t1,t2;
265	+	int id,n;
266	+	{
267	+
268	+	if(stri_intersect(q0,q1,q2,t0,t1,t2))
269	+	qt = qtRemove_tri(qt,q0,q1,q2,t0,t1,t2,id,n);
270	+	return(qt);
271	+	}
272	+
273	+
274	+	QUADTREE
275	+	qtAdd_tri(qt,q0,q1,q2,t0,t1,t2,id,n)
276	+	QUADTREE qt;
277	+	FVECT q0,q1,q2;
278	+	FVECT t0,t1,t2;
279		int id;
280		int n;
281		{
323	–	int i,index,test,found;
282		FVECT a,b,c;
283	<	OBJECT os[QT_MAXSET+1],*optr;
326	<	QUADTREE qt;
283	>	OBJECT tset[QT_MAXSET+1],*optr,*tptr;
284		FVECT r0,r1,r2;
285	+	int i;
286
329	–	found = 0;
287		/* if this is tree: recurse */
288	<	if(QT_IS_TREE(*qtptr))
288	>	if(QT_IS_TREE(qt))
289		{
290	+	QT_SET_FLAG(qt);
291		n++;
292		qtSubdivide_tri(q0,q1,q2,a,b,c);
293	<	test = stri_intersect(t0,t1,t2,q0,a,c);
294	<	if(test)
295	<	found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,0),q0,a,c,t0,t1,t2,id,n);
296	<	test = stri_intersect(t0,t1,t2,a,q1,b);
297	<	if(test)
298	<	found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,1),a,q1,b,t0,t1,t2,id,n);
299	<	test = stri_intersect(t0,t1,t2,c,b,q2);
300	<	if(test)
301	<	found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,2),c,b,q2,t0,t1,t2,id,n);
302	<	test = stri_intersect(t0,t1,t2,b,c,a);
345	<	if(test)
346	<	found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,3),b,c,a,t0,t1,t2,id,n);
293	>
294	>	if(stri_intersect(t0,t1,t2,q0,a,c))
295	>	QT_NTH_CHILD(qt,0) = qtAdd_tri(QT_NTH_CHILD(qt,0),q0,a,c,t0,t1,t2,id,n);
296	>	if(stri_intersect(t0,t1,t2,a,q1,b))
297	>	QT_NTH_CHILD(qt,1) = qtAdd_tri(QT_NTH_CHILD(qt,1),a,q1,b,t0,t1,t2,id,n);
298	>	if(stri_intersect(t0,t1,t2,c,b,q2))
299	>	QT_NTH_CHILD(qt,2) = qtAdd_tri(QT_NTH_CHILD(qt,2),c,b,q2,t0,t1,t2,id,n);
300	>	if(stri_intersect(t0,t1,t2,b,c,a))
301	>	QT_NTH_CHILD(qt,3) = qtAdd_tri(QT_NTH_CHILD(qt,3),b,c,a,t0,t1,t2,id,n);
302	>	return(qt);
303		}
304		else
305		{
306		/* If this leave node emptry- create a new set */
307	<	if(QT_IS_EMPTY(*qtptr))
308	<	*qtptr = qtaddelem(*qtptr,id);
307	>	if(QT_IS_EMPTY(qt))
308	>	qt = qtaddelem(qt,id);
309		else
310		{
311		/* If the set is too large: subdivide */
312	<	optr = qtqueryset(*qtptr);
312	>	optr = qtqueryset(qt);
313
314		if(QT_SET_CNT(optr) < QT_SET_THRESHOLD)
315	<	*qtptr = qtaddelem(*qtptr,id);
316	<	else
317	<	{
318	<	if (n < QT_MAX_LEVELS)
319	<	{
320	<	/* If set size exceeds threshold: subdivide cell and
321	<	reinsert set tris into cell
322	<	*/
323	<	qtgetset(os,*qtptr);
315	>	qt = qtaddelem(qt,id);
316	>	else
317	>	{
318	>	if (n < QT_MAX_LEVELS)
319	>	{
320	>	/* If set size exceeds threshold: subdivide cell and
321	>	reinsert set tris into cell
322	>	*/
323	>	/* CAUTION:If QT_SET_THRESHOLD << QT_MAXSET, and dont add
324	>	more than a few triangles before expanding: then are safe here
325	>	otherwise must check to make sure set size is < MAXSET,
326	>	or  qtgetset could overflow os.
327	>	*/
328	>	tptr = qtqueryset(qt);
329	>	if(QT_SET_CNT(tptr) > QT_MAXSET)
330	>	tptr = (OBJECT *)malloc((QT_SET_CNT(tptr)+1)*sizeof(OBJECT));
331	>	else
332	>	tptr = tset;
333	>	if(!tptr)
334	>	goto memerr;
335
336	<	n++;
337	<	qtfreeleaf(*qtptr);
338	<	qtSubdivide(qtptr);
339	<	found = qtAdd_tri(qtptr,q0,q1,q2,t0,t1,t2,id,n);
336	>	qtgetset(tptr,qt);
337	>	n++;
338	>	qtfreeleaf(qt);
339	>	qtSubdivide(qt);
340	>	qt = qtAdd_tri(qt,q0,q1,q2,t0,t1,t2,id,n);
341
342	<	for(optr = QT_SET_PTR(os),i = QT_SET_CNT(os); i > 0; i--)
343	<	{
344	<	id = QT_SET_NEXT_ELEM(optr);
345	<	qtTri_from_id(id,r0,r1,r2,NULL,NULL,NULL,NULL,NULL,NULL);
346	<	found=qtAdd_tri(qtptr,q0,q1,q2,r0,r1,r2,id,n);
347	<	#ifdef DEBUG
348	<	if(!found)
349	<	eputs("qtAdd_tri():Reinsert-in parent but not children\n");
350	<	#endif
383	<	}
342	>	for(optr = QT_SET_PTR(tptr),i = QT_SET_CNT(tptr); i > 0; i--)
343	>	{
344	>	id = QT_SET_NEXT_ELEM(optr);
345	>	if(!qtTri_from_id(id,r0,r1,r2))
346	>	continue;
347	>	qt  = qtAdd_tri(qt,q0,q1,q2,r0,r1,r2,id,n);
348	>	}
349	>	if(tptr != tset)
350	>	free(tptr);
351		}
352		else
353	<	if(QT_SET_CNT(optr) < QT_MAXSET)
354	<	*qtptr = qtaddelem(*qtptr,id);
388	<	else
389	<	{
390	<	#ifdef DEBUG
391	<	eputs("qtAdd_tri():two many levels\n");
392	<	#endif
393	<	return(FALSE);
394	<	}
395	<	}
353	>	qt = qtaddelem(qt,id);
354	>	}
355		}
356		}
357	<	return(TRUE);
357	>	return(qt);
358	>	memerr:
359	>	error(SYSTEM,"qtAdd_tri():Unable to allocate memory");
360		}
361
362
363	<	int
364	<	qtApply_to_tri_cells(qtptr,t0,t1,t2,v0,v1,v2,func,arg)
365	<	QUADTREE *qtptr;
405	<	FVECT t0,t1,t2;
406	<	FVECT v0,v1,v2;
407	<	int (*func)();
408	<	int *arg;
409	<	{
410	<	int test;
411	<	FVECT a,b,c;
412	<
413	<	/* test if triangle (t0,t1,t2) overlaps cell triangle (v0,v1,v2) */
414	<	test = stri_intersect(t0,t1,t2,v0,v1,v2);
415	<
416	<	/* If triangles do not overlap: done */
417	<	if(!test)
418	<	return(FALSE);
419	<
420	<	/* if this is tree: recurse */
421	<	func(qtptr,arg);
422	<
423	<	if(QT_IS_TREE(*qtptr))
424	<	{
425	<	QT_SET_FLAG(*qtptr);
426	<	qtSubdivide_tri(v0,v1,v2,a,b,c);
427	<	qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,0),t0,t1,t2,v0,a,c,func,arg);
428	<	qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,1),t0,t1,t2,a,v1,b,func,arg);
429	<	qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,2),t0,t1,t2,c,b,v2,func,arg);
430	<	qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,3),t0,t1,t2,b,c,a,func,arg);
431	<	}
432	<	}
433	<
434	<	int
435	<	qtRemove_tri(qtptr,id,t0,t1,t2,v0,v1,v2)
436	<	QUADTREE *qtptr;
363	>	QUADTREE
364	>	qtRemove_tri(qt,id,q0,q1,q2,t0,t1,t2)
365	>	QUADTREE qt;
366		int id;
367	+	FVECT q0,q1,q2;
368		FVECT t0,t1,t2;
439	–	FVECT v0,v1,v2;
369		{
441	–
442	–	int test;
443	–	int i;
370		FVECT a,b,c;
445	–	OBJECT os[QT_MAXSET+1];
371
372		/* test if triangle (t0,t1,t2) overlaps cell triangle (v0,v1,v2) */
373	<	test = stri_intersect(t0,t1,t2,v0,v1,v2);
373	>	if(!stri_intersect(t0,t1,t2,q0,q1,q2))
374	>	return(qt);
375
450	–	/* If triangles do not overlap: done */
451	–	if(!test)
452	–	return(FALSE);
453	–
376		/* if this is tree: recurse */
377	<	if(QT_IS_TREE(*qtptr))
377	>	if(QT_IS_TREE(qt))
378		{
379	<	qtSubdivide_tri(v0,v1,v2,a,b,c);
380	<	qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t0,t1,t2,v0,a,c);
381	<	qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t0,t1,t2,a,v1,b);
382	<	qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t0,t1,t2,c,b,v2);
383	<	qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t0,t1,t2,b,c,a);
379	>	qtSubdivide_tri(q0,q1,q2,a,b,c);
380	>	QT_NTH_CHILD(qt,0) = qtRemove_tri(QT_NTH_CHILD(qt,0),id,t0,t1,t2,q0,a,c);
381	>	QT_NTH_CHILD(qt,1) = qtRemove_tri(QT_NTH_CHILD(qt,1),id,t0,t1,t2,a,q1,b);
382	>	QT_NTH_CHILD(qt,2) = qtRemove_tri(QT_NTH_CHILD(qt,2),id,t0,t1,t2,c,b,q2);
383	>	QT_NTH_CHILD(qt,3) = qtRemove_tri(QT_NTH_CHILD(qt,3),id,t0,t1,t2,b,c,a);
384	>	return(qt);
385		}
386		else
387		{
388	<	if(QT_IS_EMPTY(*qtptr))
388	>	if(QT_IS_EMPTY(qt))
389		{
390		#ifdef DEBUG
391		eputs("qtRemove_tri(): triangle not found\n");
#	Line 471 | Line 394 | FVECT v0,v1,v2;
394		/* remove id from set */
395		else
396		{
397	<	if(!qtinset(*qtptr,id))
397	>	if(!qtinset(qt,id))
398		{
399		#ifdef DEBUG
400		eputs("qtRemove_tri(): tri not in set\n");
401		#endif
402		}
403		else
404	<	{
482	<	*qtptr = qtdelelem(*qtptr,id);
483	<	}
404	>	qt = qtdelelem(qt,id);
405		}
406		}
407	<	return(TRUE);
407	>	return(qt);
408		}
409
410
411	<	int
412	<	move_to_nbr(b,db0,db1,db2,tptr)
413	<	double b[3],db0,db1,db2;
493	<	double *tptr;
494	<	{
495	<	double t,dt;
496	<	int nbr;
497	<
498	<	nbr = -1;
499	<	/* Advance to next node */
500	<	if(!ZERO(db0) && db0 < 0.0)
501	<	{
502	<	t = -b[0]/db0;
503	<	nbr = 0;
504	<	}
505	<	else
506	<	t = FHUGE;
507	<	if(!ZERO(db1) && db1 < 0.0 )
508	<	{
509	<	dt = -b[1]/db1;
510	<	if( dt < t)
511	<	{
512	<	t = dt;
513	<	nbr = 1;
514	<	}
515	<	}
516	<	if(!ZERO(db2) && db2 < 0.0 )
517	<	{
518	<	dt = -b[2]/db2;
519	<	if( dt < t)
520	<	{
521	<	t = dt;
522	<	nbr = 2;
523	<	}
524	<	}
525	<	*tptr = t;
526	<	return(nbr);
527	<	}
528	<
529	<	int
530	<	qtTrace_ray(qtptr,b,db0,db1,db2,orig,dir,func,arg1,arg2)
531	<	QUADTREE *qtptr;
532	<	double b[3],db0,db1,db2;
533	<	FVECT orig,dir;
534	<	int (*func)();
535	<	int *arg1,arg2;
536	<	{
537	<
538	<	int i,found;
539	<	QUADTREE *child;
540	<	int nbr,next;
541	<	double t;
542	<	#ifdef DEBUG_TEST_DRIVER
543	<
544	<	FVECT a1,b1,c1;
545	<	int Pick_parent = Pick_cnt-1;
546	<	qtSubdivide_tri(Pick_v0[Pick_parent],Pick_v1[Pick_parent],
547	<	Pick_v2[Pick_parent],a1,b1,c1);
548	<
549	<	#endif
550	<	if(QT_IS_TREE(*qtptr))
551	<	{
552	<	/* Find the appropriate child and reset the coord */
553	<	i = bary_child(b);
554	<
555	<	QT_SET_FLAG(*qtptr);
556	<
557	<	for(;;)
558	<	{
559	<	child = QT_NTH_CHILD_PTR(*qtptr,i);
560	<
561	<	if(i != 3)
562	<	nbr = qtTrace_ray(child,b,db0,db1,db2,orig,dir,func,arg1,arg2);
563	<	else
564	<	/* If the center cell- must flip direction signs */
565	<	nbr =qtTrace_ray(child,b,-db0,-db1,-db2,orig,dir,func,arg1,arg2);
566	<	if(nbr == QT_DONE)
567	<	return(nbr);
568	<
569	<	/* If in same block: traverse */
570	<	if(i==3)
571	<	next = nbr;
572	<	else
573	<	if(nbr == i)
574	<	next = 3;
575	<	else
576	<	{
577	<	/* reset the barycentric coordinates in the parents*/
578	<	bary_parent(b,i);
579	<	/* Else pop up to parent and traverse from there */
580	<	return(nbr);
581	<	}
582	<	bary_from_child(b,i,next);
583	<	i = next;
584	<	}
585	<	}
586	<	else
587	<	{
588	<	#ifdef DEBUG_TEST_DRIVER
589	<	qtNth_child_tri(Pick_v0[Pick_parent],Pick_v1[Pick_parent],
590	<	Pick_v2[Pick_parent],a1,b1,c1,i,
591	<	Pick_v0[Pick_cnt],Pick_v1[Pick_cnt],
592	<	Pick_v2[Pick_cnt]);
593	<	Pick_cnt++;
594	<	#endif
595	<
596	<	if(func(qtptr,orig,dir,arg1,arg2) == QT_DONE)
597	<	return(QT_DONE);
598	<
599	<	/* Advance to next node */
600	<	/* NOTE: Optimize: should only have to check 1/2 */
601	<	nbr = move_to_nbr(b,db0,db1,db2,&t);
602	<
603	<	if(nbr != -1)
604	<	{
605	<	b[0] += t * db0;
606	<	b[1] += t * db1;
607	<	b[2] += t * db2;
608	<	}
609	<	return(nbr);
610	<	}
611	<
612	<	}
613	<
614	<	int
615	<	qtRoot_trace_ray(qtptr,q0,q1,q2,orig,dir,func,arg1,arg2)
616	<	QUADTREE *qtptr;
411	>	QUADTREE
412	>	qtVisit_tri_interior(qt,q0,q1,q2,t0,t1,t2,n0,n1,n2,n,func,f,argptr)
413	>	QUADTREE qt;
414		FVECT q0,q1,q2;
618	–	FVECT orig,dir;
619	–	int (*func)();
620	–	int *arg1,arg2;
621	–	{
622	–	int i,x,y,nbr;
623	–	QUADTREE *child;
624	–	FVECT n,c,i_pt,d;
625	–	double pd,b[3],db[3],t;
626	–	/* Determine if point lies within pyramid (and therefore
627	–	inside a spherical quadtree cell):GT_INTERIOR, on one of the
628	–	pyramid sides (and on cell edge):GT_EDGE(1,2 or 3),
629	–	or on pyramid vertex (and on cell vertex):GT_VERTEX(1,2, or 3).
630	–	For each triangle edge: compare the
631	–	point against the plane formed by the edge and the view center
632	–	*/
633	–	i = point_in_stri(q0,q1,q2,orig);
634	–
635	–	/* Not in this triangle */
636	–	if(!i)
637	–	return(INVALID);
638	–	/* Project the origin onto the root node plane */
639	–
640	–	/* Find the intersection point of the origin */
641	–	tri_plane_equation(q0,q1,q2,n,&pd,FALSE);
642	–	intersect_vector_plane(orig,n,pd,NULL,i_pt);
643	–	/* project the dir as well */
644	–	VADD(c,orig,dir);
645	–	intersect_vector_plane(c,n,pd,&t,c);
646	–
647	–	/* map to 2d by dropping maximum magnitude component of normal */
648	–	i = max_index(n,NULL);
649	–	x = (i+1)%3;
650	–	y = (i+2)%3;
651	–	/* Calculate barycentric coordinates of orig */
652	–	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],i_pt[x],i_pt[y],b);
653	–	/* Calculate barycentric coordinates of dir */
654	–	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],c[x],c[y],db);
655	–	if(t < 0.0)
656	–	VSUB(db,b,db);
657	–	else
658	–	VSUB(db,db,b);
659	–
660	–
661	–	#ifdef DEBUG_TEST_DRIVER
662	–	VCOPY(Pick_v0[Pick_cnt],q0);
663	–	VCOPY(Pick_v1[Pick_cnt],q1);
664	–	VCOPY(Pick_v2[Pick_cnt],q2);
665	–	Pick_cnt++;
666	–	#endif
667	–
668	–	/* trace the ray starting with this node */
669	–	nbr = qtTrace_ray(qtptr,b,db[0],db[1],db[2],orig,dir,func,arg1,arg2);
670	–	return(nbr);
671	–
672	–	}
673	–
674	–	qtVisit_tri_interior(qtptr,q0,q1,q2,t0,t1,t2,n,func,arg1,arg2,arg3)
675	–	QUADTREE *qtptr;
676	–	FVECT q0,q1,q2;
415		FVECT t0,t1,t2;
416	+	FVECT n0,n1,n2;
417		int n;
418	<	int (*func)();
419	<	int *arg1,arg2,*arg3;
418	>	int (*func)(),*f;
419	>	int *argptr;
420		{
421	<	int i,found,test;
683	<	QUADTREE *child;
684	<	FVECT c0,c1,c2,a,b,c;
685	<	OBJECT os[QT_MAXSET+1],*optr;
686	<	int w;
421	>	FVECT a,b,c;
422
423		/* If qt Flag set, or qt vertices interior to t0t1t2-descend */
424		tree_modified:
425
426	<	if(QT_IS_TREE(*qtptr))
426	>	if(QT_IS_TREE(qt))
427		{
428	<	if(QT_IS_FLAG(*qtptr) ||  point_in_stri(t0,t1,t2,q0))
428	>	if(QT_IS_FLAG(qt) ||  point_in_stri_n(n0,n1,n2,q0))
429		{
430	<	QT_SET_FLAG(*qtptr);
430	>	QT_SET_FLAG(qt);
431		qtSubdivide_tri(q0,q1,q2,a,b,c);
432		/* descend to children */
433	<	for(i=0;i < 4; i++)
434	<	{
435	<	child = QT_NTH_CHILD_PTR(*qtptr,i);
436	<	qtNth_child_tri(q0,q1,q2,a,b,c,i,c0,c1,c2);
437	<	qtVisit_tri_interior(child,c0,c1,c2,t0,t1,t2,n+1,
438	<	func,arg1,arg2,arg3);
439	<	}
433	>	QT_NTH_CHILD(qt,0) = qtVisit_tri_interior(QT_NTH_CHILD(qt,0),
434	>	q0,a,c,t0,t1,t2,n0,n1,n2,n+1,func,f,argptr);
435	>	QT_NTH_CHILD(qt,1) = qtVisit_tri_interior(QT_NTH_CHILD(qt,1),
436	>	a,q1,b,t0,t1,t2,n0,n1,n2,n+1,func,f,argptr);
437	>	QT_NTH_CHILD(qt,2) = qtVisit_tri_interior(QT_NTH_CHILD(qt,2),
438	>	c,b,q2,t0,t1,t2,n0,n1,n2,n+1,func,f,argptr);
439	>	QT_NTH_CHILD(qt,3) = qtVisit_tri_interior(QT_NTH_CHILD(qt,3),
440	>	b,c,a,t0,t1,t2,n0,n1,n2,n+1,func,f,argptr);
441		}
442		}
443		else
444	<	{
445	<	/* NOTE THIS IN TRI TEST Could be replaced by a flag */
710	<	if(!QT_IS_EMPTY(*qtptr))
444	>	if((!QT_IS_EMPTY(qt) && QT_LEAF_IS_FLAG(qt)) ||
445	>	point_in_stri_n(n0,n1,n2,q0))
446		{
447	<	if(qtinset(*qtptr,arg2))
448	<	if(func(qtptr,q0,q1,q2,t0,t1,t2,n,arg1,arg2,arg3)==QT_MODIFIED)
714	<	goto tree_modified;
715	<	else
716	<	return;
717	<	}
718	<	if(point_in_stri(t0,t1,t2,q0) )
719	<	if(func(qtptr,q0,q1,q2,t0,t1,t2,n,arg1,arg2,arg3)==QT_MODIFIED)
720	<	goto tree_modified;
721	<	}
722	<	}
723	<
724	<
725	<
726	<
727	<
728	<
729	<	/* NOTE: SINCE DIR could be unit: then we could use integer math */
730	<	int
731	<	qtVisit_tri_edges(qtptr,b,db0,db1,db2,
732	<	db,wptr,t,sign,sfactor,func,arg1,arg2,arg3)
733	<	QUADTREE *qtptr;
734	<	double b[3],db0,db1,db2,db[3][3];
735	<	int *wptr;
736	<	double t[3];
737	<	int sign;
738	<	double sfactor;
739	<	int (*func)();
740	<	int *arg1,arg2,*arg3;
741	<	{
742	<	int i,found;
743	<	QUADTREE *child;
744	<	int nbr,next,w;
745	<	double t_l,t_g;
746	<	#ifdef DEBUG_TEST_DRIVER
747	<	FVECT a1,b1,c1;
748	<	int Pick_parent = Pick_cnt-1;
749	<	qtSubdivide_tri(Pick_v0[Pick_parent],Pick_v1[Pick_parent],
750	<	Pick_v2[Pick_parent],a1,b1,c1);
751	<	#endif
752	<	if(QT_IS_TREE(*qtptr))
753	<	{
754	<	/* Find the appropriate child and reset the coord */
755	<	i = bary_child(b);
756	<
757	<	QT_SET_FLAG(*qtptr);
758	<
759	<	for(;;)
760	<	{
761	<	w = *wptr;
762	<	child = QT_NTH_CHILD_PTR(*qtptr,i);
763	<
764	<	if(i != 3)
765	<	nbr = qtVisit_tri_edges(child,b,db0,db1,db2,
766	<	db,wptr,t,sign,
767	<	sfactor*2.0,func,arg1,arg2,arg3);
768	<	else
769	<	/* If the center cell- must flip direction signs */
770	<	nbr = qtVisit_tri_edges(child,b,-db0,-db1,-db2,
771	<	db,wptr,t,1-sign,
772	<	sfactor*2.0,func,arg1,arg2,arg3);
773	<
774	<	if(nbr == QT_DONE)
775	<	return(nbr);
776	<	if(*wptr != w)
777	<	{
778	<	w = *wptr;
779	<	db0 = db[w][0];db1 = db[w][1];db2 = db[w][2];
780	<	if(sign)
781	<	{  db0 *= -1.0;db1 *= -1.0; db2 *= -1.0;}
782	<	}
783	<	/* If in same block: traverse */
784	<	if(i==3)
785	<	next = nbr;
786	<	else
787	<	if(nbr == i)
788	<	next = 3;
789	<	else
790	<	{
791	<	/* reset the barycentric coordinates in the parents*/
792	<	bary_parent(b,i);
793	<	/* Else pop up to parent and traverse from there */
794	<	return(nbr);
795	<	}
796	<	bary_from_child(b,i,next);
797	<	i = next;
798	<	}
799	<	}
800	<	else
801	<	{
802	<	#ifdef DEBUG_TEST_DRIVER
803	<	qtNth_child_tri(Pick_v0[Pick_parent],Pick_v1[Pick_parent],
804	<	Pick_v2[Pick_parent],a1,b1,c1,i,Pick_v0[Pick_cnt],
805	<	Pick_v1[Pick_cnt],Pick_v2[Pick_cnt]);
806	<	Pick_cnt++;
807	<	#endif
808	<
809	<	if(func(qtptr,arg1,arg2,arg3) == QT_DONE)
810	<	return(QT_DONE);
811	<
812	<	/* Advance to next node */
813	<	w = *wptr;
814	<	while(1)
447	>	func(&qt,f,argptr,q0,q1,q2,t0,t1,t2,n);
448	>	if(QT_FLAG_IS_MODIFIED(*f))
449		{
450	<	nbr = move_to_nbr(b,db0,db1,db2,&t_l);
451	<
818	<	t_g = t_l/sfactor;
819	<	#ifdef DEBUG
820	<	if(t[w] <= 0.0)
821	<	eputs("qtVisit_tri_edges():negative t\n");
822	<	#endif
823	<	if(t_g >= t[w])
824	<	{
825	<	if(w == 2)
826	<	return(QT_DONE);
827	<
828	<	b[0] += (t[w])*sfactor*db0;
829	<	b[1] += (t[w])*sfactor*db1;
830	<	b[2] += (t[w])*sfactor*db2;
831	<	w++;
832	<	db0 = db[w][0];
833	<	db1 = db[w][1];
834	<	db2 = db[w][2];
835	<	if(sign)
836	<	{  db0 *= -1.0;db1 *= -1.0; db2 *= -1.0;}
837	<	}
838	<	else
839	<	if(nbr != INVALID)
840	<	{
841	<	b[0] += t_l * db0;
842	<	b[1] += t_l * db1;
843	<	b[2] += t_l * db2;
844	<
845	<	t[w] -= t_g;
846	<	*wptr = w;
847	<	return(nbr);
848	<	}
849	<	else
850	<	return(INVALID);
450	>	QT_SET_FLAG(qt);
451	>	goto tree_modified;
452		}
453	<	}
454	<
453	>	if(QT_IS_LEAF(qt))
454	>	QT_LEAF_SET_FLAG(qt);
455	>	else
456	>	if(QT_IS_TREE(qt))
457	>	QT_SET_FLAG(qt);
458	>	}
459	>	return(qt);
460		}
461
462
857	–	int
858	–	qtRoot_visit_tri_edges(qtptr,q0,q1,q2,tri,i_pt,wptr,func,arg1,arg2,arg3)
859	–	QUADTREE *qtptr;
860	–	FVECT q0,q1,q2;
861	–	FVECT tri[3],i_pt;
862	–	int *wptr;
863	–	int (*func)();
864	–	int *arg1,arg2,*arg3;
865	–	{
866	–	int x,y,z,nbr,w,i,j;
867	–	QUADTREE *child;
868	–	FVECT n,c,d,v[3];
869	–	double pd,b[4][3],db[3][3],et[3],t[3],exit_pt;
870	–
871	–	w = *wptr;
463
873	–	/* Project the origin onto the root node plane */
874	–
875	–	/* Find the intersection point of the origin */
876	–	tri_plane_equation(q0,q1,q2,n,&pd,FALSE);
877	–	/* map to 2d by dropping maximum magnitude component of normal */
878	–	z = max_index(n,NULL);
879	–	x = (z+1)%3;
880	–	y = (z+2)%3;
881	–	/* Calculate barycentric coordinates for current vertex */
882	–	if(w != -1)
883	–	{
884	–	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],i_pt[x],i_pt[y],b[3]);
885	–	intersect_vector_plane(tri[w],n,pd,&(et[w]),v[w]);
886	–	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],v[w][x],v[w][y],b[w]);
887	–	}
888	–	else
889	–	/* Just starting: b[0] is the origin point: guaranteed to be valid b*/
890	–	{
891	–	w = 0;
892	–	intersect_vector_plane(tri[0],n,pd,&(et[0]),v[0]);
893	–	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],v[0][x],v[0][y],b[0]);
894	–	VCOPY(b[3],b[0]);
895	–	}
896	–
897	–
898	–	j = (w+1)%3;
899	–	intersect_vector_plane(tri[j],n,pd,&(et[j]),v[j]);
900	–	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],v[j][x],v[j][y],b[j]);
901	–	if(et[j] < 0.0)
902	–	{
903	–	VSUB(db[w],b[3],b[j]);
904	–	t[w] = FHUGE;
905	–	}
906	–	else
907	–	{
908	–	/* NOTE: for stability: do not increment with ipt- use full dir and
909	–	calculate t: but for wrap around case: could get same problem?
910	–	*/
911	–	VSUB(db[w],b[j],b[3]);
912	–	t[w] = 1.0;
913	–	move_to_nbr(b[3],db[w][0],db[w][1],db[w][2],&exit_pt);
914	–	if(exit_pt >= 1.0)
915	–	{
916	–	for(;j < 3;j++)
917	–	{
918	–	i = (j+1)%3;
919	–	if(i!= w)
920	–	{
921	–	intersect_vector_plane(tri[i],n,pd,&(et[i]),v[i]);
922	–	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],v[i][x],
923	–	v[i][y],b[i]);
924	–	}
925	–	if(et[i] < 0.0)
926	–	{
927	–	VSUB(db[j],b[j],b[i]);
928	–	t[j] = FHUGE;
929	–	break;
930	–	}
931	–	else
932	–	{
933	–	VSUB(db[j],b[i],b[j]);
934	–	t[j] = 1.0;
935	–	}
936	–	move_to_nbr(b[j],db[j][0],db[j][1],db[j][2],&exit_pt);
937	–	if(exit_pt < 1.0)
938	–	break;
939	–	}
940	–	}
941	–	}
942	–	*wptr = w;
943	–	/* trace the ray starting with this node */
944	–	nbr = qtVisit_tri_edges(qtptr,b[3],db[w][0],db[w][1],db[w][2],
945	–	db,wptr,t,0,1.0,func,arg1,arg2,arg3);
946	–	if(nbr != INVALID && nbr != QT_DONE)
947	–	{
948	–	i_pt[x] = b[3][0]*q0[x] + b[3][1]*q1[x] + b[3][2]*q2[x];
949	–	i_pt[y] = b[3][0]*q0[y] + b[3][1]*q1[y] + b[3][2]*q2[y];
950	–	i_pt[z] = (-n[x]*i_pt[x] - n[y]*i_pt[y] -pd)/n[z];
951	–	}
952	–	return(nbr);
953	–
954	–	}
955	–
464		int
465		move_to_nbri(b,db0,db1,db2,tptr)
466		BCOORD b[3];
#	Line 964 | Line 472 | TINT *tptr;
472		int nbr;
473
474		nbr = -1;
475	+	*tptr = 0;
476		/* Advance to next node */
477	+	if(b[0]==0 && db0 < 0)
478	+	return(0);
479	+	if(b[1]==0 && db1 < 0)
480	+	return(1);
481	+	if(b[2]==0 && db2 < 0)
482	+	return(2);
483	+
484		if(db0 < 0)
485		{
486	<	bc = MAXBCOORD*b[0];
486	>	bc = b[0]<<SHIFT_MAXBCOORD;
487		t = bc/-db0;
488		nbr = 0;
489		}
#	Line 975 | Line 491 | TINT *tptr;
491		t = HUGET;
492		if(db1 < 0)
493		{
494	<	bc = MAXBCOORD*b[1];
494	>	bc = b[1] <<SHIFT_MAXBCOORD;
495		dt = bc/-db1;
496		if( dt < t)
497		{
#	Line 985 | Line 501 | TINT *tptr;
501		}
502		if(db2 < 0)
503		{
504	<	bc = MAXBCOORD*b[2];
504	>	bc = b[2] << SHIFT_MAXBCOORD;
505		dt = bc/-db2;
506		if( dt < t)
507		{
#	Line 996 | Line 512 | TINT *tptr;
512		*tptr = t;
513		return(nbr);
514		}
515	<	/* NOTE: SINCE DIR could be unit: then we could use integer math */
516	<	int
517	<	qtVisit_tri_edgesi(qtptr,b,db0,db1,db2,
518	<	db,wptr,t,sign,sfactor,func,arg1,arg2,arg3)
1003	<	QUADTREE *qtptr;
515	>
516	>	QUADTREE
517	>	qtVisit_tri_edges(qt,b,db0,db1,db2,db,wptr,nextptr,t,sign,sfactor,func,f,argptr)
518	>	QUADTREE qt;
519		BCOORD b[3];
520		BDIR db0,db1,db2,db[3][3];
521	<	int *wptr;
521	>	int *wptr,*nextptr;
522		TINT t[3];
523	<	int sign;
1009	<	int sfactor;
523	>	int sign,sfactor;
524		int (*func)();
525	<	int *arg1,arg2,*arg3;
525	>	int *f,*argptr;
526		{
527		int i,found;
528	<	QUADTREE *child;
528	>	QUADTREE child;
529		int nbr,next,w;
530	<	TINT t_g,t_l,t_i;
531	<	#ifdef DEBUG_TEST_DRIVER
532	<	FVECT a1,b1,c1;
1019	<	int Pick_parent = Pick_cnt-1;
1020	<	qtSubdivide_tri(Pick_v0[Pick_parent],Pick_v1[Pick_parent],
1021	<	Pick_v2[Pick_parent],a1,b1,c1);
1022	<	#endif
1023	<	if(QT_IS_TREE(*qtptr))
530	>	TINT t_g,t_l,t_i,l;
531	>
532	>	if(QT_IS_TREE(qt))
533		{
534	<	/* Find the appropriate child and reset the coord */
535	<	i = baryi_child(b);
534	>	/* Find the appropriate child and reset the coord */
535	>	i = baryi_child(b);
536
537	<	QT_SET_FLAG(*qtptr);
537	>	QT_SET_FLAG(qt);
538
539	<	for(;;)
540	<	{
541	<	w = *wptr;
542	<	child = QT_NTH_CHILD_PTR(*qtptr,i);
539	>	for(;;)
540	>	{
541	>	w = *wptr;
542	>	child = QT_NTH_CHILD(qt,i);
543	>	if(i != 3)
544	>	QT_NTH_CHILD(qt,i) =
545	>	qtVisit_tri_edges(child,b,db0,db1,db2,db,wptr,nextptr,t,sign,
546	>	sfactor+1,func,f,argptr);
547	>	else
548	>	/* If the center cell- must flip direction signs */
549	>	QT_NTH_CHILD(qt,i) =
550	>	qtVisit_tri_edges(child,b,-db0,-db1,-db2,db,wptr,nextptr,t,1-sign,
551	>	sfactor+1,func,f,argptr);
552
553	<	if(i != 3)
554	<	nbr = qtVisit_tri_edgesi(child,b,db0,db1,db2,
555	<	db,wptr,t,sign,
556	<	sfactor+1,func,arg1,arg2,arg3);
557	<	else
558	<	/* If the center cell- must flip direction signs */
559	<	nbr = qtVisit_tri_edgesi(child,b,-db0,-db1,-db2,
560	<	db,wptr,t,1-sign,
1043	<	sfactor+1,func,arg1,arg2,arg3);
1044	<
1045	<	if(nbr == QT_DONE)
1046	<	return(nbr);
1047	<	if(*wptr != w)
1048	<	{
1049	<	w = *wptr;
1050	<	db0 = db[w][0];db1 = db[w][1];db2 = db[w][2];
1051	<	if(sign)
1052	<	{  db0 *= -1;db1 *= -1; db2 *= -1;}
1053	<	}
1054	<	/* If in same block: traverse */
1055	<	if(i==3)
1056	<	next = nbr;
1057	<	else
1058	<	if(nbr == i)
1059	<	next = 3;
1060	<	else
1061	<	{
1062	<	/* reset the barycentric coordinates in the parents*/
1063	<	baryi_parent(b,i);
1064	<	/* Else pop up to parent and traverse from there */
1065	<	return(nbr);
1066	<	}
1067	<	baryi_from_child(b,i,next);
1068	<	i = next;
553	>	if(QT_FLAG_IS_DONE(*f))
554	>	return(qt);
555	>	if(*wptr != w)
556	>	{
557	>	w = *wptr;
558	>	db0 = db[w][0];db1 = db[w][1];db2 = db[w][2];
559	>	if(sign)
560	>	{  db0 *= -1;db1 *= -1; db2 *= -1;}
561		}
562	+	/* If in same block: traverse */
563	+	if(i==3)
564	+	next = *nextptr;
565	+	else
566	+	if(*nextptr == i)
567	+	next = 3;
568	+	else
569	+	{
570	+	/* reset the barycentric coordinates in the parents*/
571	+	baryi_parent(b,i);
572	+	/* Else pop up to parent and traverse from there */
573	+	return(qt);
574	+	}
575	+	baryi_from_child(b,i,next);
576	+	i = next;
577	+	}
578		}
579		else
580		{
581	<	#ifdef DEBUG_TEST_DRIVER
582	<	qtNth_child_tri(Pick_v0[Pick_parent],Pick_v1[Pick_parent],
583	<	Pick_v2[Pick_parent],a1,b1,c1,i,Pick_v0[Pick_cnt],
584	<	Pick_v1[Pick_cnt],Pick_v2[Pick_cnt]);
585	<	Pick_cnt++;
586	<	#endif
587	<
588	<	if(func(qtptr,arg1,arg2,arg3) == QT_DONE)
589	<	return(QT_DONE);
590	<
591	<	/* Advance to next node */
592	<	w = *wptr;
593	<	while(1)
581	>	func(&qt,f,argptr);
582	>	if(QT_FLAG_IS_DONE(*f))
583	>	{
584	>	if(!QT_IS_EMPTY(qt))
585	>	QT_LEAF_SET_FLAG(qt);
586	>	return(qt);
587	>	}
588	>
589	>	if(!QT_IS_EMPTY(qt))
590	>	QT_LEAF_SET_FLAG(qt);
591	>	/* Advance to next node */
592	>	w = *wptr;
593	>	while(1)
594		{
595	<	nbr = move_to_nbri(b,db0,db1,db2,&t_i);
596	<
595	>	nbr = move_to_nbri(b,db0,db1,db2,&t_i);
596	>
597		t_g = t_i >> sfactor;
598
599		if(t_g >= t[w])
600		{
601		if(w == 2)
602	<	return(QT_DONE);
603	<
604	<	/* The edge fits in the cell- therefore the result of shifting db by
605	<	sfactor is guaranteed to be less than MAXBCOORD
606	<	*/
602	>	{
603	>	QT_FLAG_SET_DONE(*f);
604	>	return(qt);
605	>	}
606	>	/* The edge fits in the cell- therefore the result of shifting
607	>	db by sfactor is guaranteed to be less than MAXBCOORD
608	>	*/
609		/* Caution: (t[w]*db) must occur before divide by MAXBCOORD
610		since t[w] will always be < MAXBCOORD
611	<	*/
612	<	b[0] = b[0] + (t[w]*db0*(1 << sfactor))/MAXBCOORD;
613	<	b[1] = b[1] + (t[w]*db1*(1 << sfactor))/MAXBCOORD;
614	<	b[2] = b[2] + (t[w]*db2*(1 << sfactor))/MAXBCOORD;
611	>	*/
612	>	l = t[w] << sfactor;
613	>	/* NOTE: Change divides to Shift and multiply by sign*/
614	>	b[0] += (l*db0)/MAXBCOORD;
615	>	b[1] += (l*db1)/MAXBCOORD;
616	>	b[2] += (l*db2)/MAXBCOORD;
617		w++;
618		db0 = db[w][0]; db1 = db[w][1]; db2 = db[w][2];
619		if(sign)
620	<	{  db0 *= -1;db1 *= -1; db2 *= -1;}
620	>	{  db0 *= -1;db1 *= -1; db2 *= -1;}
621		}
622	<	else
623	<	if(nbr != INVALID)
1112	<	{
622	>	else
623	>	{
624		/* Caution: (t_i*db) must occur before divide by MAXBCOORD
625	<	since t_i will always be < MAXBCOORD
626	<	*/
627	<	b[0] = b[0] + (t_i *db0) / MAXBCOORD;
628	<	b[1] = b[1] + (t_i *db1) / MAXBCOORD;
629	<	b[2] = b[2] + (t_i *db2) / MAXBCOORD;
630	<
625	>	since t_i will always be < MAXBCOORD*/
626	>	/* NOTE: Change divides to Shift and  by sign*/
627	>	b[0] += (t_i *db0) / MAXBCOORD;
628	>	b[1] += (t_i *db1) / MAXBCOORD;
629	>	b[2] += (t_i *db2) / MAXBCOORD;
630	>
631		t[w] -= t_g;
632		*wptr = w;
633	<	return(nbr);
633	>	*nextptr = nbr;
634	>	return(qt);
635		}
1124	–	else
1125	–	return(INVALID);
636		}
637		}
638		}
639
640
641	<	int
642	<	qtRoot_visit_tri_edgesi(qtptr,q0,q1,q2,tri,i_pt,wptr,func,arg1,arg2,arg3)
643	<	QUADTREE *qtptr;
641	>	QUADTREE
642	>	qtRoot_visit_tri_edges(qt,q0,q1,q2,peq,tri,i_pt,wptr,nextptr,func,f,argptr)
643	>	QUADTREE qt;
644		FVECT q0,q1,q2;
645	+	FPEQ  peq;
646		FVECT tri[3],i_pt;
647	<	int *wptr;
647	>	int *wptr,*nextptr;
648		int (*func)();
649	<	int *arg1,arg2,*arg3;
649	>	int *f,*argptr;
650		{
651	<	int x,y,z,nbr,w,i,j;
652	<	QUADTREE *child;
653	<	FVECT n,c,d,v[3];
654	<	double pd,b[4][3],db[3][3],et[3],exit_pt;
651	>	int x,y,z,w,i,j,first;
652	>	QUADTREE child;
653	>	FVECT c,d,v[3];
654	>	double b[4][3],db[3][3],et[3],exit_pt;
655		BCOORD bi[3];
656		TINT t[3];
657		BDIR dbi[3][3];
658	+
659	+	first =0;
660		w = *wptr;
661	<
661	>	if(w==-1)
662	>	{
663	>	first = 1;
664	>	*wptr = w = 0;
665	>	}
666		/* Project the origin onto the root node plane */
667
668		t[0] = t[1] = t[2] = 0;
669		/* Find the intersection point of the origin */
1153	–	tri_plane_equation(q0,q1,q2,n,&pd,FALSE);
670		/* map to 2d by dropping maximum magnitude component of normal */
671	<	z = max_index(n,NULL);
672	<	x = (z+1)%3;
673	<	y = (z+2)%3;
671	>
672	>	x = FP_X(peq);
673	>	y = FP_Y(peq);
674	>	z = FP_Z(peq);
675		/* Calculate barycentric coordinates for current vertex */
676	<	if(w != -1)
1160	<	{
676	>	if(!first)
677		bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],i_pt[x],i_pt[y],b[3]);
1162	–	intersect_vector_plane(tri[w],n,pd,&(et[w]),v[w]);
1163	–	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],v[w][x],v[w][y],b[w]);
1164	–	}
678		else
679		/* Just starting: b[0] is the origin point: guaranteed to be valid b*/
680		{
681	<	w = 0;
1169	<	intersect_vector_plane(tri[0],n,pd,&(et[0]),v[0]);
681	>	intersect_vector_plane(tri[0],peq,&(et[0]),v[0]);
682		bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],v[0][x],v[0][y],b[0]);
683		VCOPY(b[3],b[0]);
684		}
685
1174	–
686		j = (w+1)%3;
687	<	intersect_vector_plane(tri[j],n,pd,&(et[j]),v[j]);
687	>	intersect_vector_plane(tri[j],peq,&(et[j]),v[j]);
688		bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],v[j][x],v[j][y],b[j]);
689		if(et[j] < 0.0)
690		{
#	Line 1188 | Line 699 | qtRoot_visit_tri_edgesi(qtptr,q0,q1,q2,tri,i_pt,wptr,f
699		VSUB(db[w],b[j],b[3]);
700		/* Check if the point is out side of the triangle: if so t[w] =HUGET */
701		if((fabs(b[j][0])>(FTINY+1.0)) ||(fabs(b[j][1])>(FTINY+1.0)) ||
702	<	(fabs(b[j][2])>(FTINY+1.0)))
703	<	t[w] = HUGET;
702	>	(fabs(b[j][2])>(FTINY+1.0))||(b[j][0] <-FTINY) ||
703	>	(b[j][1]<-FTINY) ||(b[j][2]<-FTINY))
704	>	t[w] = HUGET;
705		else
706		{
707		/* The next point is in the triangle- so db values will be in valid
#	Line 1197 | Line 709 | qtRoot_visit_tri_edgesi(qtptr,q0,q1,q2,tri,i_pt,wptr,f
709		*/
710		t[w] = MAXT;
711		if(j != 0)
712	<	for(;j < 3;j++)
713	<	{
714	<	i = (j+1)%3;
715	<	if(i!= w)
716	<	{
717	<	intersect_vector_plane(tri[i],n,pd,&(et[i]),v[i]);
718	<	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],v[i][x],
719	<	v[i][y],b[i]);
720	<	}
721	<	if(et[i] < 0.0)
722	<	{
723	<	VSUB(db[j],b[j],b[i]);
724	<	t[j] = HUGET;
725	<	break;
726	<	}
727	<	else
728	<	{
729	<	VSUB(db[j],b[i],b[j]);
730	<	if((fabs(b[j][0])>(FTINY+1.0)) ||
731	<	(fabs(b[j][1])>(FTINY+1.0)) ||
732	<	(fabs(b[j][2])>(FTINY+1.0)))
733	<	{
734	<	t[j] = HUGET;
735	<	break;
736	<	}
737	<	else
738	<	t[j] = MAXT;
739	<	}
740	<	}
712	>	for(;j < 3;j++)
713	>	{
714	>	i = (j+1)%3;
715	>	if(!first || i != 0)
716	>	{
717	>	intersect_vector_plane(tri[i],peq,&(et[i]),v[i]);
718	>	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],v[i][x],
719	>	v[i][y],b[i]);
720	>	}
721	>	if(et[i] < 0.0)
722	>	{
723	>	VSUB(db[j],b[j],b[i]);
724	>	t[j] = HUGET;
725	>	break;
726	>	}
727	>	else
728	>	{
729	>	VSUB(db[j],b[i],b[j]);
730	>	if((fabs(b[j][0])>(FTINY+1.0))||(fabs(b[j][1])>(FTINY+1.0)) ||
731	>	(fabs(b[j][2])>(FTINY+1.0))||(b[i][0] <-FTINY) ||
732	>	(b[i][1]<-FTINY) ||(b[i][2]<-FTINY))
733	>	{
734	>	t[j] = HUGET;
735	>	break;
736	>	}
737	>	else
738	>	t[j] = MAXT;
739	>	}
740	>	}
741		}
742	<	}
743	<	*wptr = w;
744	<	bary_dtol(b[3],db,bi,dbi,t);
1233	<
742	>	}
743	>	bary_dtol(b[3],db,bi,dbi,t,w);
744	>
745		/* trace the ray starting with this node */
746	<	nbr = qtVisit_tri_edgesi(qtptr,bi,dbi[w][0],dbi[w][1],dbi[w][2],
747	<	dbi,wptr,t,0,0,func,arg1,arg2,arg3);
748	<	if(nbr != INVALID && nbr != QT_DONE)
749	<	{
750	<	b[3][0] = (double)bi[0]/(double)MAXBCOORD;
751	<	b[3][1] = (double)bi[1]/(double)MAXBCOORD;
752	<	b[3][2] = (double)bi[2]/(double)MAXBCOORD;
753	<	i_pt[x] = b[3][0]*q0[x] + b[3][1]*q1[x] + b[3][2]*q2[x];
754	<	i_pt[y] = b[3][0]*q0[y] + b[3][1]*q1[y] + b[3][2]*q2[y];
755	<	i_pt[z] = (-n[x]*i_pt[x] - n[y]*i_pt[y] -pd)/n[z];
756	<	}
757	<	return(nbr);
746	>	qt = qtVisit_tri_edges(qt,bi,dbi[w][0],dbi[w][1],dbi[w][2],
747	>	dbi,wptr,nextptr,t,0,0,func,f,argptr);
748	>	if(!QT_FLAG_IS_DONE(*f))
749	>	{
750	>	b[3][0] = (double)bi[0]/(double)MAXBCOORD;
751	>	b[3][1] = (double)bi[1]/(double)MAXBCOORD;
752	>	b[3][2] = (double)bi[2]/(double)MAXBCOORD;
753	>	i_pt[x] = b[3][0]*q0[x] + b[3][1]*q1[x] + b[3][2]*q2[x];
754	>	i_pt[y] = b[3][0]*q0[y] + b[3][1]*q1[y] + b[3][2]*q2[y];
755	>	i_pt[z] = (-FP_N(peq)[x]*i_pt[x] - FP_N(peq)[y]*i_pt[y]-FP_D(peq))/FP_N(peq)[z];
756	>	}
757	>	return(qt);
758
759		}
760
761
762	+	QUADTREE
763	+	qtRoot_trace_ray(qt,q0,q1,q2,peq,orig,dir,nextptr,func,f,argptr)
764	+	QUADTREE qt;
765	+	FVECT q0,q1,q2;
766	+	FPEQ  peq;
767	+	FVECT orig,dir;
768	+	int *nextptr;
769	+	int (*func)();
770	+	int *f,*argptr;
771	+	{
772	+	int x,y,z,nbr,w,i;
773	+	QUADTREE child;
774	+	FVECT v,i_pt;
775	+	double b[2][3],db[3],et[2],d,br[3];
776	+	BCOORD bi[3];
777	+	TINT t[3];
778	+	BDIR dbi[3][3];
779	+
780	+	/* Project the origin onto the root node plane */
781	+	t[0] = t[1] = t[2] = 0;
782
783	+	VADD(v,orig,dir);
784	+	/* Find the intersection point of the origin */
785	+	/* map to 2d by dropping maximum magnitude component of normal */
786	+	x = FP_X(peq);
787	+	y = FP_Y(peq);
788	+	z = FP_Z(peq);
789	+
790	+	/* Calculate barycentric coordinates for current vertex */
791	+	intersect_vector_plane(orig,peq,&(et[0]),i_pt);
792	+	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],i_pt[x],i_pt[y],b[0]);
793	+
794	+	intersect_vector_plane(v,peq,&(et[1]),i_pt);
795	+	bary2d(q0[x],q0[y],q1[x],q1[y],q2[x],q2[y],i_pt[x],i_pt[y],b[1]);
796	+	if(et[1] < 0.0)
797	+	VSUB(db,b[0],b[1]);
798	+	else
799	+	VSUB(db,b[1],b[0]);
800	+	t[0] = HUGET;
801	+	convert_dtol(b[0],bi);
802	+	if(et[1]<0.0 || (fabs(b[1][0])>(FTINY+1.0)) ||(fabs(b[1][1])>(FTINY+1.0)) ||
803	+	(fabs(b[1][2])>(FTINY+1.0))||(b[1][0] <-FTINY) ||
804	+	(b[1][1]<-FTINY) ||(b[1][2]<-FTINY))
805	+	{
806	+	max_index(db,&d);
807	+	for(i=0; i< 3; i++)
808	+	dbi[0][i] = (BDIR)(db[i]/d*MAXBDIR);
809	+	}
810	+	else
811	+	for(i=0; i< 3; i++)
812	+	dbi[0][i] = (BDIR)(db[i]*MAXBDIR);
813	+	w=0;
814	+	/* trace the ray starting with this node */
815	+	qt = qtVisit_tri_edges(qt,bi,dbi[0][0],dbi[0][1],dbi[0][2], dbi,&w,
816	+	nextptr,t,0,0,func,f,argptr);
817	+	if(!QT_FLAG_IS_DONE(*f))
818	+	{
819	+	br[0] = (double)bi[0]/(double)MAXBCOORD;
820	+	br[1] = (double)bi[1]/(double)MAXBCOORD;
821	+	br[2] = (double)bi[2]/(double)MAXBCOORD;
822	+	orig[x] = br[0]*q0[x] + br[1]*q1[x] + br[2]*q2[x];
823	+	orig[y] = br[0]*q0[y] + br[1]*q1[y] + br[2]*q2[y];
824	+	orig[z]=(-FP_N(peq)[x]*orig[x] -
825	+	FP_N(peq)[y]*orig[y]-FP_D(peq))/FP_N(peq)[z];
826	+	}
827	+	return(qt);
828	+
829	+	}
830
831
832

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines