ViewVC Help

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

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

Comparing ray/src/hd/sm.c (file contents):
Revision 3.5 by gwlarson, Fri Sep 11 11:52:25 1998 UTC vs.
Revision 3.8 by gwlarson, Tue Oct 6 18:16:54 1998 UTC

#	Line 8 | Line 8 | static char SCCSid[] = "$SunId$ SGI";
8		*  sm.c
9		*/
10		#include "standard.h"
11	+	#include "sm_flag.h"
12		#include "sm_list.h"
13		#include "sm_geom.h"
14	+	#include "sm_qtree.h"
15	+	#include "sm_stree.h"
16		#include "sm.h"
17
18
19		SM *smMesh = NULL;
20		double smDist_sum=0;
21		int smNew_tri_cnt=0;
22	+	double smMinSampDiff = 1e-4;
23
24	+	static FVECT smDefault_base[4] = { {SQRT3_INV, SQRT3_INV, SQRT3_INV},
25	+	{-SQRT3_INV, -SQRT3_INV, SQRT3_INV},
26	+	{-SQRT3_INV, SQRT3_INV, -SQRT3_INV},
27	+	{SQRT3_INV, -SQRT3_INV, -SQRT3_INV}};
28	+	static int smTri_verts[4][3] = { {2,1,0},{3,2,0},{1,3,0},{2,3,1}};
29	+
30		static int smBase_nbrs[4][3] =  { {3,2,1},{3,0,2},{3,1,0},{1,2,0}};
31
32		#ifdef TEST_DRIVER
#	Line 35 | Line 45 | smDir(sm,ps,id)
45		FVECT ps;
46		int id;
47		{
48	<	FVECT p;
49	<
40	<	VCOPY(p,SM_NTH_WV(sm,id));
41	<	point_on_sphere(ps,p,SM_VIEW_CENTER(sm));
48	>	VSUB(ps,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
49	>	normalize(ps);
50		}
51
52	<	smClear_mesh(sm)
53	<	SM *sm;
52	>	smDir_in_cone(sm,ps,id)
53	>	SM *sm;
54	>	FVECT ps;
55	>	int id;
56		{
57	<	/* Reset the triangle counters */
58	<	SM_TRI_CNT(sm) = 0;
59	<	SM_NUM_TRIS(sm) = 0;
50	<	SM_FREE_TRIS(sm) = -1;
57	>
58	>	VSUB(ps,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
59	>	normalize(ps);
60		}
61
62		smClear_flags(sm,which)
#	Line 58 | Line 67 | int which;
67
68		if(which== -1)
69		for(i=0; i < T_FLAGS;i++)
70	<	bzero(SM_NTH_FLAGS(sm,i),T_TOTAL_FLAG_BYTES(SM_MAX_TRIS(sm)));
70	>	bzero(SM_NTH_FLAGS(sm,i),FLAG_BYTES(SM_MAX_TRIS(sm)));
71		else
72	<	bzero(SM_NTH_FLAGS(sm,which),T_TOTAL_FLAG_BYTES(SM_MAX_TRIS(sm)));
72	>	bzero(SM_NTH_FLAGS(sm,which),FLAG_BYTES(SM_MAX_TRIS(sm)));
73		}
74
75	<	smClear_locator(sm)
76	<	SM *sm;
75	>	/* Given an allocated mesh- initialize */
76	>	smInit_mesh(sm)
77	>	SM *sm;
78		{
79	<	STREE  *st;
80	<
81	<	st = SM_LOCATOR(sm);
82	<
83	<	stClear(st);
79	>	/* Reset the triangle counters */
80	>	SM_NUM_TRI(sm) = 0;
81	>	SM_SAMPLE_TRIS(sm) = 0;
82	>	SM_FREE_TRIS(sm) = -1;
83	>	smClear_flags(sm,-1);
84		}
85
76	–	smInit_locator(sm,center,base)
77	–	SM *sm;
78	–	FVECT  center,base[4];
79	–	{
80	–	STREE  *st;
81	–
82	–	st = SM_LOCATOR(sm);
83	–
84	–	stInit(st,center,base);
86
87	<	}
88	<
87	>	/* Clear the SM for reuse: free any extra allocated memory:does initialization
88	>	as well
89	>	*/
90		smClear(sm)
91		SM *sm;
92		{
93		smClear_samples(sm);
92	–	smClear_mesh(sm);
94		smClear_locator(sm);
95	+	smInit_mesh(sm);
96		}
97
98	+	static int realloc_cnt=0;
99	+
100		int
101	<	smAlloc_tris(sm,max_verts,max_tris)
101	>	smRealloc_mesh(sm)
102		SM *sm;
103	+	{
104	+	int fbytes,i,max_tris,max_verts;
105	+
106	+	if(realloc_cnt <=0)
107	+	realloc_cnt = SM_MAX_TRIS(sm);
108	+
109	+	max_tris = SM_MAX_TRIS(sm) + realloc_cnt;
110	+	fbytes = FLAG_BYTES(max_tris);
111	+
112	+	if(!(SM_TRIS(sm) = (TRI *)realloc(SM_TRIS(sm),max_tris*sizeof(TRI))))
113	+	goto memerr;
114	+
115	+	for(i=0; i< T_FLAGS; i++)
116	+	if(!(SM_NTH_FLAGS(sm,i)=(int4 *)realloc((char *)SM_NTH_FLAGS(sm,i),fbytes)))
117	+	goto memerr;
118	+
119	+	SM_MAX_TRIS(sm) = max_tris;
120	+	return(max_tris);
121	+
122	+	memerr:
123	+	error(SYSTEM, "out of memory in smRealloc_mesh()");
124	+	}
125	+
126	+	/* Allocate and initialize a new mesh with max_verts and max_tris */
127	+	int
128	+	smAlloc_mesh(sm,max_verts,max_tris)
129	+	SM *sm;
130		int max_verts,max_tris;
131		{
132	<	int i,nbytes,vbytes,fbytes;
132	>	int fbytes,i;
133
134	<	vbytes = max_verts*sizeof(VERT);
104	<	fbytes = T_TOTAL_FLAG_BYTES(max_tris);
105	<	nbytes = vbytes + max_tris*sizeof(TRI) +T_FLAGS*fbytes + 8;
106	<	for(i = 1024; nbytes > i; i <<= 1)
107	<	;
108	<	/* check if casting works correctly */
109	<	max_tris = (i-vbytes-8)/(sizeof(TRI) + T_FLAG_BYTES);
110	<	fbytes = T_TOTAL_FLAG_BYTES(max_tris);
111	<
112	<	SM_BASE(sm)=(char *)malloc(vbytes+max_tris*sizeof(TRI)+T_FLAGS*fbytes);
134	>	fbytes = FLAG_BYTES(max_tris);
135
136	<	if (SM_BASE(sm) == NULL)
137	<	return(0);
136	>	if(!(SM_TRIS(sm) = (TRI *)realloc(NULL,max_tris*sizeof(TRI))))
137	>	goto memerr;
138
139	<	SM_TRIS(sm) = (TRI *)SM_BASE(sm);
140	<	SM_VERTS(sm) = (VERT *)(SM_TRIS(sm) + max_tris);
139	>	if(!(SM_VERTS(sm) = (VERT *)realloc(NULL,max_verts*sizeof(VERT))))
140	>	goto memerr;
141
142	<	SM_NTH_FLAGS(sm,0) = (int4 *)(SM_VERTS(sm) + max_verts);
143	<	for(i=1; i < T_FLAGS; i++)
144	<	SM_NTH_FLAGS(sm,i) = (int4 *)(SM_NTH_FLAGS(sm,i-1)+fbytes/sizeof(int4));
145	<
142	>	for(i=0; i< T_FLAGS; i++)
143	>	if(!(SM_NTH_FLAGS(sm,i)=(int4 *)realloc(NULL,fbytes)))
144	>	goto memerr;
145	>
146		SM_MAX_VERTS(sm) = max_verts;
147		SM_MAX_TRIS(sm) = max_tris;
148
149	<	smClear_mesh(sm);
149	>	realloc_cnt = max_verts >> 1;
150
151	+	smInit_mesh(sm);
152	+
153		return(max_tris);
154	+	memerr:
155	+	error(SYSTEM, "out of memory in smAlloc_mesh()");
156		}
157
158
133	–
159		int
160	<	smAlloc_locator(sm)
160	>	smAlloc_tri(sm)
161		SM *sm;
162		{
163	<	STREE  *st;
164	<
165	<	st = SM_LOCATOR(sm);
166	<
167	<	st = stAlloc(st);
168	<
169	<	if(st)
170	<	return(TRUE);
171	<	else
172	<	return(FALSE);
163	>	int id;
164	>
165	>	/* First check if there are any tris on the free list */
166	>	/* Otherwise, have we reached the end of the list yet?*/
167	>	if(SM_NUM_TRI(sm) < SM_MAX_TRIS(sm))
168	>	return(SM_NUM_TRI(sm)++);
169	>
170	>	if((id = SM_FREE_TRIS(sm)) != -1)
171	>	{
172	>	SM_FREE_TRIS(sm) =  T_NEXT_FREE(SM_NTH_TRI(sm,id));
173	>	return(id);
174	>	}
175	>
176	>	/*Else: realloc */
177	>	smRealloc_mesh(sm);
178	>	return(SM_NUM_TRI(sm)++);
179		}
180
181	+	smFree_mesh(sm)
182	+	SM *sm;
183	+	{
184	+	int i;
185	+
186	+	if(SM_TRIS(sm))
187	+	free(SM_TRIS(sm));
188	+	if(SM_VERTS(sm))
189	+	free(SM_VERTS(sm));
190	+	for(i=0; i< T_FLAGS; i++)
191	+	if(SM_NTH_FLAGS(sm,i))
192	+	free(SM_NTH_FLAGS(sm,i));
193	+	}
194	+
195	+
196		/* Initialize/clear global smL sample list for at least n samples */
197		smAlloc(max_samples)
198		register int max_samples;
#	Line 154 | Line 200 | smAlloc(max_samples)
200		unsigned nbytes;
201		register unsigned i;
202		int total_points;
203	<	int max_tris;
203	>	int max_tris,n;
204
205	+	n = max_samples;
206		/* If this is the first call, allocate sample,vertex and triangle lists */
207		if(!smMesh)
208		{
209		if(!(smMesh = (SM *)malloc(sizeof(SM))))
210	<	error(SYSTEM,"smAlloc():Unable to allocate memory");
210	>	error(SYSTEM,"smAlloc():Unable to allocate memory\n");
211		bzero(smMesh,sizeof(SM));
212		}
213		else
214		{   /* If existing structure: first deallocate */
215	<	if(SM_BASE(smMesh))
216	<	free(SM_BASE(smMesh));
217	<	if(SM_SAMP_BASE(smMesh))
218	<	free(SM_SAMP_BASE(smMesh));
172	<	}
215	>	smFree_mesh(smMesh);
216	>	smFree_samples(smMesh);
217	>	smFree_locator(smMesh);
218	>	}
219
220		/* First allocate at least n samples + extra points:at least enough
221		necessary to form the BASE MESH- Default = 4;
222		*/
223	<	max_samples = smAlloc_samples(smMesh, max_samples,SM_EXTRA_POINTS);
223	>	SM_SAMP(smMesh) = sAlloc(&n,SM_EXTRA_POINTS);
224
225	<	total_points = max_samples + SM_EXTRA_POINTS;
180	<	max_tris = total_points*2;
225	>	total_points = n + SM_EXTRA_POINTS;
226
227	+	max_tris = total_points*4;
228		/* Now allocate space for mesh vertices and triangles */
229	<	max_tris = smAlloc_tris(smMesh, total_points, max_tris);
229	>	max_tris = smAlloc_mesh(smMesh, total_points, max_tris);
230
231		/* Initialize the structure for point,triangle location.
232		*/
233		smAlloc_locator(smMesh);
188	–
234		}
235
236
237
238	<	smInit_mesh(sm,vp)
238	>	smInit_sm(sm,vp)
239		SM *sm;
240		FVECT vp;
241		{
242
198	–	/* NOTE: Should be elsewhere?*/
243		smDist_sum = 0;
244		smNew_tri_cnt = 0;
245
246	<	VCOPY(SM_VIEW_CENTER(smMesh),vp);
247	<	smClear_locator(sm);
248	<	smInit_locator(sm,vp,0);
249	<	smClear_aux_samples(sm);
206	<	smClear_mesh(sm);
246	>	VCOPY(SM_VIEW_CENTER(sm),vp);
247	>	smInit_locator(sm,vp);
248	>	smInit_samples(sm);
249	>	smInit_mesh(sm);
250		smCreate_base_mesh(sm,SM_DEFAULT);
251		}
252
#	Line 224 | Line 267 | smInit(n)
267		{
268		int max_vertices;
269
270	+
271		/* If n <=0, Just clear the existing structures */
272		if(n <= 0)
273		{
#	Line 237 | Line 281 | smInit(n)
281		max_vertices = n + SM_EXTRA_POINTS;
282
283		/* If the current mesh contains enough room, clear and return */
284	<	if(smMesh && max_vertices <= SM_MAX_VERTS(smMesh))
284	>	if(smMesh && (max_vertices <= SM_MAX_VERTS(smMesh)) && SM_MAX_SAMP(smMesh) <=
285	>	n && SM_MAX_POINTS(smMesh) <= max_vertices)
286		{
287		smClear(smMesh);
288		return(SM_MAX_SAMP(smMesh));
#	Line 251 | Line 296 | smInit(n)
296		}
297
298
299	<	int
300	<	smLocator_apply_func(sm,v0,v1,v2,func,arg)
301	<	SM *sm;
302	<	FVECT v0,v1,v2;
303	<	int (*func)();
304	<	int *arg;
299	>	smLocator_apply_func(sm,v0,v1,v2,edge_func,tri_func,argptr)
300	>	SM *sm;
301	>	FVECT v0,v1,v2;
302	>	int (*edge_func)();
303	>	int (*tri_func)();
304	>	int *argptr;
305		{
306		STREE *st;
262	–	int found;
307		FVECT p0,p1,p2;
308
309		st = SM_LOCATOR(sm);
#	Line 268 | Line 312 | int *arg;
312		VSUB(p1,v1,SM_VIEW_CENTER(sm));
313		VSUB(p2,v2,SM_VIEW_CENTER(sm));
314
315	<	found = stApply_to_tri_cells(st,p0,p1,p2,func,arg);
315	>	stApply_to_tri(st,p0,p1,p2,edge_func,tri_func,argptr);
316
273	–	return(found);
317		}
318
319	+	QUADTREE
320	+	delete_tri_set(qt,optr,del_set)
321	+	QUADTREE qt;
322	+	OBJECT *optr,*del_set;
323	+	{
324
325	<	int
326	<	add_tri_expand(qtptr,q0,q1,q2,t0,t1,t2,n,arg,t_id)
325	>	int set_size,i,t_id;
326	>	OBJECT *rptr,r_set[QT_MAXSET+1];
327	>	OBJECT *tptr,t_set[QT_MAXSET+1],*sptr;
328	>
329	>	/* First need to check if set size larger than QT_MAXSET: if so
330	>	need to allocate larger array
331	>	*/
332	>	if((set_size = MAX(QT_SET_CNT(optr),QT_SET_CNT(del_set))) >QT_MAXSET)
333	>	rptr = (OBJECT *)malloc((set_size+1)*sizeof(OBJECT));
334	>	else
335	>	rptr = r_set;
336	>	if(!rptr)
337	>	goto memerr;
338	>	setintersect(rptr,del_set,optr);
339	>
340	>	if(QT_SET_CNT(rptr) > 0)
341	>	{
342	>	/* First need to check if set size larger than QT_MAXSET: if so
343	>	need to allocate larger array
344	>	*/
345	>	sptr = QT_SET_PTR(rptr);
346	>	for(i = QT_SET_CNT(rptr); i > 0; i--)
347	>	{
348	>	t_id = QT_SET_NEXT_ELEM(sptr);
349	>	qt = qtdelelem(qt,t_id);
350	>	}
351	>	}
352	>	/* If we allocated memory: free it */
353	>	if(rptr != r_set)
354	>	free(rptr);
355	>
356	>	return(qt);
357	>	memerr:
358	>	error(SYSTEM,"delete_tri_set():Unable to allocate memory");
359	>	}
360	>
361	>	QUADTREE
362	>	expand_node(qt,q0,q1,q2,optr,n)
363	>	QUADTREE qt;
364	>	FVECT q0,q1,q2;
365	>	OBJECT *optr;
366	>	int n;
367	>	{
368	>	OBJECT *tptr,t_set[QT_MAXSET+1];
369	>	int i,t_id,found;
370	>	TRI *t;
371	>	FVECT v0,v1,v2;
372	>
373	>	if(QT_SET_CNT(optr) > QT_MAXSET)
374	>	tptr = (OBJECT *)malloc((QT_SET_CNT(optr)+1)*sizeof(OBJECT));
375	>	else
376	>	tptr = t_set;
377	>	if(!tptr)
378	>	goto memerr;
379	>
380	>	qtgetset(tptr,qt);
381	>	/* If set size exceeds threshold: subdivide cell and reinsert tris*/
382	>	qtfreeleaf(qt);
383	>	qtSubdivide(qt);
384	>
385	>	for(optr = QT_SET_PTR(tptr),i=QT_SET_CNT(tptr); i > 0; i--)
386	>	{
387	>	t_id = QT_SET_NEXT_ELEM(optr);
388	>	t = SM_NTH_TRI(smMesh,t_id);
389	>	if(!T_IS_VALID(t))
390	>	continue;
391	>	VSUB(v0,SM_T_NTH_WV(smMesh,t,0),SM_VIEW_CENTER(smMesh));
392	>	VSUB(v1,SM_T_NTH_WV(smMesh,t,1),SM_VIEW_CENTER(smMesh));
393	>	VSUB(v2,SM_T_NTH_WV(smMesh,t,2),SM_VIEW_CENTER(smMesh));
394	>	qt = qtAdd_tri(qt,q0,q1,q2,v0,v1,v2,t_id,n);
395	>	}
396	>	/* If we allocated memory: free it */
397	>	if( tptr != t_set)
398	>	free(tptr);
399	>
400	>	return(qt);
401	>	memerr:
402	>	error(SYSTEM,"expand_node():Unable to allocate memory");
403	>	}
404	>
405	>	add_tri_expand(qtptr,f,argptr,q0,q1,q2,t0,t1,t2,n)
406		QUADTREE *qtptr;
407	+	int *f;
408	+	ADD_ARGS *argptr;
409		FVECT q0,q1,q2;
410		FVECT t0,t1,t2;
411		int n;
283	–	int *arg;
284	–	int t_id;
412		{
413	<	OBJECT tset[QT_MAXSET+1],*optr;
414	<	int i,id,found;
288	<	FVECT v0,v1,v2;
413	>	int t_id;
414	>	OBJECT *optr,*del_set;
415
416	<	#ifdef DEBUG_TEST_DRIVER
417	<	Pick_tri = t_id;
418	<	Picking = TRUE;
419	<	#endif
420	<
421	<	if(QT_IS_EMPTY(*qtptr))
422	<	{
423	<	*qtptr = qtaddelem(*qtptr,t_id);
424	<	return(TRUE);
299	<	}
300	<
416	>	t_id = argptr->t_id;
417	>
418	>	if(QT_IS_EMPTY(*qtptr))
419	>	{
420	>	*qtptr = qtaddelem(*qtptr,t_id);
421	>	return;
422	>	}
423	>	if(!QT_LEAF_IS_FLAG(*qtptr))
424	>	{
425		optr = qtqueryset(*qtptr);
302	–	if(!inset(optr,t_id))
303	–	{
304	–	if(QT_SET_CNT(optr) < QT_MAXSET)
305	–	*qtptr = qtaddelem(*qtptr,t_id);
306	–	else
307	–	{
308	–	#ifdef DEBUG
309	–	eputs("add_tri_expand():no room in set\n");
310	–	#endif
311	–	return(FALSE);
312	–	}
313	–	}
314	–	optr = qtqueryset(*qtptr);
315	–	if(QT_SET_CNT(optr) >= QT_SET_THRESHOLD)
316	–	if (n < QT_MAX_LEVELS)
317	–	{
318	–	qtgetset(tset,*qtptr);
319	–	/* If set size exceeds threshold: subdivide cell and reinsert tris*/
320	–	qtfreeleaf(*qtptr);
321	–	qtSubdivide(qtptr);
426
427	<	for(optr = QT_SET_PTR(tset),i=QT_SET_CNT(tset); i > 0; i--)
428	<	{
429	<	id = QT_SET_NEXT_ELEM(optr);
430	<	qtTri_from_id(id,NULL,NULL,NULL,v0,v1,v2,NULL,NULL,NULL);
431	<	found=qtAdd_tri(qtptr,q0,q1,q2,v0,v1,v2,id,n);
432	<	#ifdef DEBUG
433	<	if(!found)
434	<	eputs("add_tri_expand():Reinsert\n");
435	<	#endif
436	<	}
333	<	return(QT_MODIFIED);
334	<	}
335	<	else
336	<	if(QT_SET_CNT(optr) < QT_MAXSET)
337	<	{
338	<	#ifdef DEBUG_TEST_DRIVER
339	<	eputs("add_tri_expand():too many levels:can't expand\n");
340	<	#endif
341	<	return(TRUE);
342	<	}
343	<	else
344	<	{
345	<	#ifdef DEBUG
346	<	eputs("add_tri_expand():too many tris inset:can't add\n");
347	<	#endif
348	<	return(FALSE);
349	<	}
427	>	if(del_set=argptr->del_set)
428	>	*qtptr = delete_tri_set(*qtptr,optr,del_set);
429	>	*qtptr = qtaddelem(*qtptr,t_id);
430	>	}
431	>	if (n >= QT_MAX_LEVELS)
432	>	return;
433	>	optr = qtqueryset(*qtptr);
434	>	if(QT_SET_CNT(optr) < QT_SET_THRESHOLD)
435	>	return;
436	>	*qtptr = expand_node(*qtptr,q0,q1,q2,optr,n);
437		}
438
439
440	<	int
441	<	add_tri(qtptr,fptr,t_id)
440	>
441	>	add_tri(qtptr,fptr,argptr)
442		QUADTREE *qtptr;
443		int *fptr;
444	<	int t_id;
444	>	ADD_ARGS *argptr;
445		{
446
447	<	OBJECT *optr;
447	>	OBJECT *optr,*del_set;
448	>	int t_id;
449
450	<	#ifdef DEBUG_TEST_DRIVER
451	<	Pick_tri = t_id;
452	<	Picking = TRUE;
453	<	#endif
454	<	if(QT_IS_EMPTY(*qtptr))
450	>	t_id = argptr->t_id;
451	>
452	>
453	>	if(QT_IS_EMPTY(*qtptr))
454	>	{
455	>	*qtptr = qtaddelem(*qtptr,t_id);
456	>	if(!QT_FLAG_FILL_TRI(*fptr))
457	>	(*fptr)++;
458	>	return;
459	>	}
460	>	if(QT_LEAF_IS_FLAG(*qtptr))
461	>	return;
462	>
463	>	optr = qtqueryset(*qtptr);
464	>
465	>	if(del_set = argptr->del_set)
466	>	*qtptr = delete_tri_set(*qtptr,optr,del_set);
467	>
468	>	if(!QT_IS_EMPTY(*qtptr))
469		{
470	<	*qtptr = qtaddelem(*qtptr,t_id);
471	<	if(!QT_FLAG_FILL_TRI(*fptr))
472	<	(*fptr)++;
470	>	optr = qtqueryset(*qtptr);
471	>	if(QT_SET_CNT(optr) >= QT_SET_THRESHOLD)
472	>	(*fptr) |= QT_EXPAND;
473		}
474	<	else
475	<	{
476	<	optr = qtqueryset(*qtptr);
477	<	if(!inset(optr,t_id))
376	<	{
377	<	if(QT_SET_CNT(optr) < QT_MAXSET)
378	<	{
379	<	if(QT_SET_CNT(optr) >= QT_SET_THRESHOLD)
380	<	(*fptr) |= QT_EXPAND;
381	<	if(!QT_FLAG_FILL_TRI(*fptr))
382	<	(*fptr)++;
383	<	*qtptr = qtaddelem(*qtptr,t_id);
384	<	}
385	<	else
386	<	{
387	<	#ifdef DEBUG_TESTDRIVER
388	<	eputs("add_tri():exceeded set size\n");
389	<	#endif
390	<	return(FALSE);
391	<	}
392	<	}
393	<	}
394	<	return(TRUE);
474	>	if(!QT_FLAG_FILL_TRI(*fptr))
475	>	(*fptr)++;
476	>	*qtptr = qtaddelem(*qtptr,t_id);
477	>
478		}
479
480
481	<	int
399	<	stInsert_tri(st,t_id,t0,t1,t2)
400	<	STREE *st;
401	<	int t_id;
402	<	FVECT t0,t1,t2;
403	<	{
404	<	int f;
405	<	FVECT dir;
406	<
407	<	/* First add all of the leaf cells lying on the triangle perimeter:
408	<	mark all cells seen on the way
409	<	*/
410	<	ST_CLEAR_FLAGS(st);
411	<	f = 0;
412	<	VSUB(dir,t1,t0);
413	<	stTrace_edge(st,t0,dir,1.0,add_tri,&f,t_id);
414	<	VSUB(dir,t2,t1);
415	<	stTrace_edge(st,t1,dir,1.0,add_tri,&f,t_id);
416	<	VSUB(dir,t0,t2);
417	<	stTrace_edge(st,t2,dir,1.0,add_tri,&f,t_id);
418	<	/* Now visit interior */
419	<	if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f))
420	<	stVisit_tri_interior(st,t0,t1,t2,add_tri_expand,&f,t_id);
421	<	}
422	<
423	<	smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id)
481	>	smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id,del_set)
482		SM *sm;
483		int t_id;
484	<	int v0_id,v1_id,v2_id;
484	>	int v0_id,v1_id,v2_id;
485	>	OBJECT *del_set;
486		{
487		STREE *st;
488		FVECT v0,v1,v2;
489	<
489	>	ADD_ARGS args;
490	>
491		st = SM_LOCATOR(sm);
492
493	+
494		VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm));
495		VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm));
496		VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm));
497
498	<	stUpdate_tri(st,t_id,v0,v1,v2,add_tri,add_tri_expand);
498	>	qtClearAllFlags();
499	>	args.t_id = t_id;
500	>	args.del_set = del_set;
501
502	+	stApply_to_tri(st,v0,v1,v2,add_tri,add_tri_expand,&args);
503	+
504		}
505
506		/* Add a triangle to the base array with vertices v1-v2-v3 */
507		int
508	<	smAdd_tri(sm, v0_id,v1_id,v2_id,tptr)
508	>	smAdd_tri(sm, v0_id,v1_id,v2_id)
509		SM *sm;
510		int v0_id,v1_id,v2_id;
446	–	TRI **tptr;
511		{
512		int t_id;
513		TRI *t;
514
515	+	t_id = smAlloc_tri(sm);
516
452	–	if(SM_TRI_CNT(sm)+1 > SM_MAX_TRIS(sm))
453	–	error(SYSTEM,"smAdd_tri():Too many triangles");
454	–
455	–	/* Get the id for the next available triangle */
456	–	SM_FREE_TRI_ID(sm,t_id);
517		if(t_id == -1)
518		return(t_id);
519
520		t = SM_NTH_TRI(sm,t_id);
521	+
522		T_CLEAR_NBRS(t);
523	+	/* set the triangle vertex ids */
524	+	T_NTH_V(t,0) = v0_id;
525	+	T_NTH_V(t,1) = v1_id;
526	+	T_NTH_V(t,2) = v2_id;
527
528	+	SM_NTH_VERT(sm,v0_id) = t_id;
529	+	SM_NTH_VERT(sm,v1_id) = t_id;
530	+	SM_NTH_VERT(sm,v2_id) = t_id;
531	+
532		if(SM_BASE_ID(sm,v0_id) || SM_BASE_ID(sm,v1_id) || SM_BASE_ID(sm,v2_id))
533		{
534		smClear_tri_flags(sm,t_id);
#	Line 467 | Line 536 | TRI **tptr;
536		}
537		else
538		{
539	<	SM_CLEAR_NTH_T_BASE(sm,t_id);
539	>	SM_CLR_NTH_T_BASE(sm,t_id);
540		SM_SET_NTH_T_ACTIVE(sm,t_id);
472	–	SM_SET_NTH_T_LRU(sm,t_id);
541		SM_SET_NTH_T_NEW(sm,t_id);
542	<	SM_NUM_TRIS(sm)++;
542	>	S_SET_FLAG(T_NTH_V(t,0));
543	>	S_SET_FLAG(T_NTH_V(t,1));
544	>	S_SET_FLAG(T_NTH_V(t,2));
545	>	SM_SAMPLE_TRIS(sm)++;
546		smNew_tri_cnt++;
547		}
477	–	/* set the triangle vertex ids */
478	–	T_NTH_V(t,0) = v0_id;
479	–	T_NTH_V(t,1) = v1_id;
480	–	T_NTH_V(t,2) = v2_id;
548
482	–	SM_NTH_VERT(sm,v0_id) = t_id;
483	–	SM_NTH_VERT(sm,v1_id) = t_id;
484	–	SM_NTH_VERT(sm,v2_id) = t_id;
485	–
486	–	if(t)
487	–	*tptr = t;
549		/* return initialized triangle */
550		return(t_id);
551		}
552
492	–	int
493	–	smClosest_vertex_in_tri(sm,v0_id,v1_id,v2_id,p,eps)
494	–	SM *sm;
495	–	int v0_id,v1_id,v2_id;
496	–	FVECT p;
497	–	double eps;
498	–	{
499	–	FVECT v;
500	–	double d,d0,d1,d2;
501	–	int closest = -1;
553
503	–	if(v0_id != -1)
504	–	{
505	–	smDir(sm,v,v0_id);
506	–	d0 = DIST(p,v);
507	–	if(eps < 0 || d0 < eps)
508	–	{
509	–	closest = v0_id;
510	–	d = d0;
511	–	}
512	–	}
513	–	if(v1_id != -1)
514	–	{
515	–	smDir(sm,v,v1_id);
516	–	d1 = DIST(p,v);
517	–	if(closest== -1)
518	–	{
519	–	if(eps < 0 || d1 < eps)
520	–	{
521	–	closest = v1_id;
522	–	d = d1;
523	–	}
524	–	}
525	–	else
526	–	if(d1 < d0)
527	–	{
528	–	if((eps < 0) ||  d1 < eps)
529	–	{
530	–	closest = v1_id;
531	–	d = d1;
532	–	}
533	–	}
534	–	}
535	–	if(v2_id != -1)
536	–	{
537	–	smDir(sm,v,v2_id);
538	–	d2 = DIST(p,v);
539	–	if((eps < 0) ||  d2 < eps)
540	–	if(closest == -1 ||(d2 < d))
541	–	return(v2_id);
542	–	}
543	–	return(closest);
544	–	}
545	–
546	–
547	–	int
548	–	smClosest_vertex_in_w_tri(sm,v0_id,v1_id,v2_id,p)
549	–	SM *sm;
550	–	int v0_id,v1_id,v2_id;
551	–	FVECT p;
552	–	{
553	–	FVECT v;
554	–	double d,d0,d1,d2;
555	–	int closest;
556	–
557	–	VCOPY(v,SM_NTH_WV(sm,v0_id));
558	–	d = d0 = DIST(p,v);
559	–	closest = v0_id;
560	–
561	–	VCOPY(v,SM_NTH_WV(sm,v1_id));
562	–	d1 = DIST(p,v);
563	–	if(d1 < d0)
564	–	{
565	–	closest = v1_id;
566	–	d = d1;
567	–	}
568	–	VCOPY(v,SM_NTH_WV(sm,v2_id));
569	–	d2 = DIST(p,v);
570	–	if(d2 < d)
571	–	return(v2_id);
572	–	else
573	–	return(closest);
574	–	}
575	–
554		void
555	<	smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add,del)
555	>	smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add_ptr,delptr)
556		SM *sm;
557		int t_id,t1_id;
558		int e,e1;
559		int *tn_id,*tn1_id;
560	<	LIST **add,**del;
560	>	LIST **add_ptr;
561	>	QUADTREE *delptr;
562
563		{
585	–	TRI *t,*t1;
586	–	TRI *ta,*tb;
564		int verts[3],enext,eprev,e1next,e1prev;
565		TRI *n;
566		FVECT p1,p2,p3;
#	Line 592 | Line 569 | smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add,d
569		defined by quadrilateral
570		formed by t,t1- swap for the opposite diagonal
571		*/
595	–	t = SM_NTH_TRI(sm,t_id);
596	–	t1 = SM_NTH_TRI(sm,t1_id);
572		enext = (e+1)%3;
573		eprev = (e+2)%3;
574		e1next = (e1+1)%3;
575		e1prev = (e1+2)%3;
576	<	verts[e] = T_NTH_V(t,e);
577	<	verts[enext] = T_NTH_V(t1,e1prev);
578	<	verts[eprev] = T_NTH_V(t,eprev);
579	<	ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&ta);
580	<	*add = push_data(*add,ta_id);
581	<	verts[e1] = T_NTH_V(t1,e1);
582	<	verts[e1next] = T_NTH_V(t,eprev);
583	<	verts[e1prev] = T_NTH_V(t1,e1prev);
584	<	tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&tb);
585	<	*add = push_data(*add,tb_id);
576	>	verts[e] = T_NTH_V(SM_NTH_TRI(sm,t_id),e);
577	>	verts[enext] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1prev);
578	>	verts[eprev] = T_NTH_V(SM_NTH_TRI(sm,t_id),eprev);
579	>	ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2]);
580	>	*add_ptr = push_data(*add_ptr,ta_id);
581	>	verts[e1] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1);
582	>	verts[e1next] = T_NTH_V(SM_NTH_TRI(sm,t_id),eprev);
583	>	verts[e1prev] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1prev);
584	>	tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2]);
585	>	*add_ptr = push_data(*add_ptr,tb_id);
586
587		/* set the neighbors */
588	<	T_NTH_NBR(ta,e) = T_NTH_NBR(t1,e1next);
589	<	T_NTH_NBR(tb,e1) = T_NTH_NBR(t,enext);
590	<	T_NTH_NBR(ta,enext) = tb_id;
591	<	T_NTH_NBR(tb,e1next) = ta_id;
592	<	T_NTH_NBR(ta,eprev) = T_NTH_NBR(t,eprev);
593	<	T_NTH_NBR(tb,e1prev) = T_NTH_NBR(t1,e1prev);
588	>	T_NTH_NBR(SM_NTH_TRI(sm,ta_id),e) = T_NTH_NBR(SM_NTH_TRI(sm,t1_id),e1next);
589	>	T_NTH_NBR(SM_NTH_TRI(sm,tb_id),e1) = T_NTH_NBR(SM_NTH_TRI(sm,t_id),enext);
590	>	T_NTH_NBR(SM_NTH_TRI(sm,ta_id),enext) =tb_id;
591	>	T_NTH_NBR(SM_NTH_TRI(sm,tb_id),e1next) = ta_id;
592	>	T_NTH_NBR(SM_NTH_TRI(sm,ta_id),eprev)=T_NTH_NBR(SM_NTH_TRI(sm,t_id),eprev);
593	>	T_NTH_NBR(SM_NTH_TRI(sm,tb_id),e1prev)=
594	>	T_NTH_NBR(SM_NTH_TRI(sm,t1_id),e1prev);
595
596		/* Reset neighbor pointers of original neighbors */
597	<	n = SM_NTH_TRI(sm,T_NTH_NBR(t,enext));
597	>	n = SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t_id),enext));
598		T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = tb_id;
599	<	n = SM_NTH_TRI(sm,T_NTH_NBR(t,eprev));
599	>	n = SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t_id),eprev));
600		T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = ta_id;
601
602	<	n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1next));
602	>	n = SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t1_id),e1next));
603		T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = ta_id;
604	<	n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1prev));
604	>	n = SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t1_id),e1prev));
605		T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = tb_id;
606
607		/* Delete two parent triangles */
608	+	if(remove_from_list(t_id,add_ptr))
609	+	smDelete_tri(sm,t_id);
610	+	else
611	+	*delptr = qtaddelem(*delptr,t_id);
612
613	<	*del = push_data(*del,t_id);
614	<	if(SM_IS_NTH_T_NEW(sm,t_id))
635	<	SM_CLEAR_NTH_T_NEW(sm,t_id);
613	>	if(remove_from_list(t1_id,add_ptr))
614	>	smDelete_tri(sm,t1_id);
615		else
616	<	SM_CLEAR_NTH_T_BASE(sm,t_id);
617	<	*del = push_data(*del,t1_id);
639	<	if(SM_IS_NTH_T_NEW(sm,t1_id))
640	<	SM_CLEAR_NTH_T_NEW(sm,t1_id);
641	<	else
642	<	SM_CLEAR_NTH_T_BASE(sm,t1_id);
616	>	*delptr = qtaddelem(*delptr,t1_id);
617	>
618		*tn_id = ta_id;
619		*tn1_id = tb_id;
620		}
621
622	<	smUpdate_locator(sm,add_list,del_list)
622	>	smUpdate_locator(sm,add_list,del_set)
623		SM *sm;
624	<	LIST *add_list,*del_list;
624	>	LIST *add_list;
625	>	OBJECT *del_set;
626		{
627	<	int t_id;
627	>	int t_id,i;
628		TRI *t;
629	+	OBJECT *optr;
630	+
631		while(add_list)
632		{
633		t_id = pop_list(&add_list);
656	–	if(!SM_IS_NTH_T_NEW(sm,t_id) && !SM_IS_NTH_T_BASE(sm,t_id))
657	–	{
658	–	SM_SET_NTH_T_NEW(sm,t_id);
659	–	smNew_tri_cnt--;
660	–	continue;
661	–	}
634		t = SM_NTH_TRI(sm,t_id);
635	<	smLocator_add_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2));
635	>	smLocator_add_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2),del_set);
636		}
637	<
638	<	while(del_list)
637	>
638	>	optr = QT_SET_PTR(del_set);
639	>	for(i = QT_SET_CNT(del_set); i > 0; i--)
640		{
641	<	t_id = pop_list(&del_list);
642	<	if(SM_IS_NTH_T_NEW(sm,t_id))
643	<	{
641	>	t_id = QT_SET_NEXT_ELEM(optr);
642	>	#if 0
643	>	t = SM_NTH_TRI(sm,t_id);
644	>	smLocator_remove_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2));
645	>	#endif
646		smDelete_tri(sm,t_id);
672	–	continue;
673	–	}
674	–	smLocator_remove_tri(sm,t_id);
675	–	smDelete_tri(sm,t_id);
647		}
648		}
649		/* MUST add check for constrained edges */
650		int
651	<	smFix_tris(sm,id,tlist)
651	>	smFix_tris(sm,id,tlist,add_list,delptr)
652		SM *sm;
653		int id;
654	<	LIST *tlist;
654	>	LIST *tlist,*add_list;
655	>	QUADTREE *delptr;
656		{
657		TRI *t,*t_opp;
658		FVECT p,p1,p2,p3;
659		int e,e1,swapped = 0;
660		int t_id,t_opp_id;
689	–	LIST *add_list,*del_list;
661
691	–
692	–	add_list = del_list = NULL;
662		VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
663		while(tlist)
664		{
#	Line 698 | Line 667 | LIST *tlist;
667		e = (T_WHICH_V(t,id)+1)%3;
668		t_opp_id = T_NTH_NBR(t,e);
669		t_opp = SM_NTH_TRI(sm,t_opp_id);
670	<
671	<	smDir(sm,p1,T_NTH_V(t_opp,0));
672	<	smDir(sm,p2,T_NTH_V(t_opp,1));
673	<	smDir(sm,p3,T_NTH_V(t_opp,2));
670	>
671	>	smDir_in_cone(sm,p1,T_NTH_V(t_opp,0));
672	>	smDir_in_cone(sm,p2,T_NTH_V(t_opp,1));
673	>	smDir_in_cone(sm,p3,T_NTH_V(t_opp,2));
674		if(point_in_cone(p,p1,p2,p3))
675		{
676		swapped = 1;
#	Line 709 | Line 678 | LIST *tlist;
678		/* check list for t_opp and Remove if there */
679		remove_from_list(t_opp_id,&tlist);
680		smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id,
681	<	&add_list,&del_list);
681	>	&add_list,delptr);
682		tlist = push_data(tlist,t_id);
683		tlist = push_data(tlist,t_opp_id);
684		}
685		}
686	<	smUpdate_locator(sm,add_list,del_list);
686	>	smUpdate_locator(sm,add_list,qtqueryset(*delptr));
687		return(swapped);
688		}
689
#	Line 728 | Line 697 | TRI *t;
697		int id;
698		{
699		int t_id;
700	<	int tri;
700	>	int nbr_id;
701
702		/* Want the edge for which "id" is the destination */
703		t_id = (T_WHICH_V(t,id)+ 2)% 3;
704	<	tri = T_NTH_NBR(t,t_id);
705	<	return(tri);
704	>	nbr_id = T_NTH_NBR(t,t_id);
705	>	return(nbr_id);
706		}
707
739	–	void
740	–	smReplace_point(sm,tri,id,nid)
741	–	SM *sm;
742	–	TRI *tri;
743	–	int id,nid;
744	–	{
745	–	TRI *t;
746	–	int t_id;
747	–
748	–	T_NTH_V(tri,T_WHICH_V(tri,id)) = nid;
749	–
750	–	t_id = smTri_next_ccw_nbr(sm,tri,nid);
751	–	while((t = SM_NTH_TRI(sm,t_id)) != tri)
752	–	{
753	–	T_NTH_V(t,T_WHICH_V(t,id)) = nid;
754	–	t_id = smTri_next_ccw_nbr(sm,t,nid);
755	–	}
756	–	}
757	–
758	–
708		smClear_tri_flags(sm,id)
709		SM *sm;
710		int id;
#	Line 763 | Line 712 | int id;
712		int i;
713
714		for(i=0; i < T_FLAGS; i++)
715	<	SM_CLEAR_NTH_T_FLAG(sm,id,i);
715	>	SM_CLR_NTH_T_FLAG(sm,id,i);
716
717		}
718
719		/* Locate the point-id in the point location structure: */
720		int
721	<	smReplace_vertex(sm,c,dir,p,tri_id,snew_id,type,which)
721	>	smInsert_samp(sm,s_id,tri_id)
722		SM *sm;
774	–	COLR c;
775	–	FVECT dir,p;
776	–	int tri_id,snew_id;
777	–	int type,which;
778	–	{
779	–	int n_id,s_id;
780	–	TRI *tri;
781	–
782	–	tri = SM_NTH_TRI(sm,tri_id);
783	–	/* Get the sample that corresponds to the "which" vertex of "tri" */
784	–	/* NEED: have re-init that sets clock flag */
785	–	/* If this is a base-sample: create a new sample and replace
786	–	all references to the base sample with references to the
787	–	new sample
788	–	*/
789	–	s_id = T_NTH_V(tri,which);
790	–	if(SM_BASE_ID(sm,s_id))
791	–	{
792	–	if(snew_id != -1)
793	–	n_id = smAdd_sample_point(sm,c,dir,p);
794	–	else
795	–	n_id = snew_id;
796	–	smReplace_point(sm,tri,s_id,n_id);
797	–	s_id = n_id;
798	–	}
799	–	else /* If the sample exists, reset the values */
800	–	/* NOTE: This test was based on the SPHERICAL coordinates
801	–	of the point: If we are doing a multiple-sample-per
802	–	SPHERICAL pixel: we will want to test for equality-
803	–	and do other processing: for now: SINGLE SAMPLE PER
804	–	PIXEL
805	–	*/
806	–	/* NOTE: snew_id needs to be marked as invalid?*/
807	–	if(snew_id == -1)
808	–	smInit_sample(sm,s_id,c,dir,p);
809	–	else
810	–	smReset_sample(sm,s_id,snew_id);
811	–	return(s_id);
812	–	}
813	–
814	–
815	–	/* Locate the point-id in the point location structure: */
816	–	int
817	–	smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id)
818	–	SM *sm;
819	–	COLR c;
820	–	FVECT dir,p;
723		int s_id,tri_id;
724		{
725	<	TRI *tri,*t0,*t1,*t2,*nbr;
726	<	int v0_id,v1_id,v2_id,n_id;
727	<	int t0_id,t1_id,t2_id;
728	<	LIST *tlist;
725	>	int v0_id,v1_id,v2_id;
726	>	int t0_id,t1_id,t2_id,replaced;
727	>	LIST *tlist,*add_list;
728	>	OBJECT del_set[2];
729	>	QUADTREE delnode;
730		FVECT npt;
731	+	TRI *tri,*nbr;
732
733	<	if(s_id == SM_INVALID)
830	<	s_id = smAdd_sample_point(sm,c,dir,p);
831	<
832	<	tri = SM_NTH_TRI(sm,tri_id);
833	<	v0_id = T_NTH_V(tri,0);
834	<	v1_id = T_NTH_V(tri,1);
835	<	v2_id = T_NTH_V(tri,2);
733	>	add_list = NULL;
734
735	<	n_id = -1;
736	<	if(SM_BASE_ID(sm,v0_id)||SM_BASE_ID(sm,v1_id)||SM_BASE_ID(sm,v2_id))
737	<	{
738	<	smDir(sm,npt,s_id);
739	<	/* Change to an add and delete */
842	<	t0_id = (SM_BASE_ID(sm,v0_id))?v0_id:-1;
843	<	t1_id = (SM_BASE_ID(sm,v1_id))?v1_id:-1;
844	<	t2_id = (SM_BASE_ID(sm,v2_id))?v2_id:-1;
845	<	n_id = smClosest_vertex_in_tri(sm,t0_id,t1_id,t2_id,npt,P_REPLACE_EPS);
846	<	}
847	<	t0_id = smAdd_tri(sm,s_id,v0_id,v1_id,&t0);
735	>	v0_id = T_NTH_V(SM_NTH_TRI(sm,tri_id),0);
736	>	v1_id = T_NTH_V(SM_NTH_TRI(sm,tri_id),1);
737	>	v2_id = T_NTH_V(SM_NTH_TRI(sm,tri_id),2);
738	>
739	>	t0_id = smAdd_tri(sm,s_id,v0_id,v1_id);
740		/* Add triangle to the locator */
741	<	smLocator_add_tri(sm,t0_id,s_id,v0_id,v1_id);
741	>
742	>	add_list = push_data(add_list,t0_id);
743
744	<	t1_id = smAdd_tri(sm,s_id,v1_id,v2_id,&t1);
745	<	smLocator_add_tri(sm,t1_id,s_id,v1_id,v2_id);
853	<	t2_id = smAdd_tri(sm,s_id,v2_id,v0_id,&t2);
854	<	smLocator_add_tri(sm,t2_id,s_id,v2_id,v0_id);
744	>	t1_id = smAdd_tri(sm,s_id,v1_id,v2_id);
745	>	add_list = push_data(add_list,t1_id);
746
747	+	t2_id = smAdd_tri(sm,s_id,v2_id,v0_id);
748	+	add_list = push_data(add_list,t2_id);
749	+
750	+	/* CAUTION: tri must be assigned after Add_tri: pointers may change*/
751	+	tri = SM_NTH_TRI(sm,tri_id);
752	+
753		/* Set the neighbor pointers for the new tris */
754	<	T_NTH_NBR(t0,0) = t2_id;
755	<	T_NTH_NBR(t0,1) = T_NTH_NBR(tri,0);
756	<	T_NTH_NBR(t0,2) = t1_id;
757	<	T_NTH_NBR(t1,0) = t0_id;
758	<	T_NTH_NBR(t1,1) = T_NTH_NBR(tri,1);
759	<	T_NTH_NBR(t1,2) = t2_id;
760	<	T_NTH_NBR(t2,0) = t1_id;
761	<	T_NTH_NBR(t2,1) = T_NTH_NBR(tri,2);
762	<	T_NTH_NBR(t2,2) = t0_id;
754	>	T_NTH_NBR(SM_NTH_TRI(sm,t0_id),0) = t2_id;
755	>	T_NTH_NBR(SM_NTH_TRI(sm,t0_id),1) = T_NTH_NBR(tri,0);
756	>	T_NTH_NBR(SM_NTH_TRI(sm,t0_id),2) = t1_id;
757	>	T_NTH_NBR(SM_NTH_TRI(sm,t1_id),0) = t0_id;
758	>	T_NTH_NBR(SM_NTH_TRI(sm,t1_id),1) = T_NTH_NBR(tri,1);
759	>	T_NTH_NBR(SM_NTH_TRI(sm,t1_id),2) = t2_id;
760	>	T_NTH_NBR(SM_NTH_TRI(sm,t2_id),0) = t1_id;
761	>	T_NTH_NBR(SM_NTH_TRI(sm,t2_id),1) = T_NTH_NBR(tri,2);
762	>	T_NTH_NBR(SM_NTH_TRI(sm,t2_id),2) = t0_id;
763
764		/* Reset the neigbor pointers for the neighbors of the original */
765		nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,0));
#	Line 872 | Line 769 | smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id)
769		nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,2));
770		T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t2_id;
771
772	<	smLocator_remove_tri(sm,tri_id);
773	<	smDelete_tri(sm,tri_id);
774	<
772	>	del_set[0] = 1; del_set[1] = tri_id;
773	>	delnode = qtnewleaf(del_set);
774	>
775		/* Fix up the new triangles*/
776		tlist = push_data(NULL,t0_id);
777		tlist = push_data(tlist,t1_id);
778		tlist = push_data(tlist,t2_id);
779
780	<	smFix_tris(sm,s_id,tlist);
780	>	smFix_tris(sm,s_id,tlist,add_list,&delnode);
781
782	<	if(n_id != -1)
886	<	smDelete_point(sm,n_id);
782	>	qtfreeleaf(delnode);
783
784	<	return(s_id);
784	>	return(TRUE);
785		}
786
787
788		int
789	<	smPointLocate(sm,pt,norm)
789	>	smTri_in_set(sm,p,optr)
790		SM *sm;
791	<	FVECT pt;
792	<	int norm;
791	>	FVECT p;
792	>	OBJECT *optr;
793		{
794	<	STREE *st;
795	<	int tri;
796	<	FVECT npt;
794	>	int i,t_id;
795	>	FVECT n,v0,v1,v2;
796	>	TRI *t;
797
798	<	st = SM_LOCATOR(sm);
903	<	if(norm)
798	>	for (i = QT_SET_CNT(optr),optr = QT_SET_PTR(optr);i > 0; i--)
799		{
800	<	VSUB(npt,pt,SM_VIEW_CENTER(sm));
801	<	tri = stPoint_locate(st,npt);
800	>	/* Find the first triangle that pt falls */
801	>	t_id = QT_SET_NEXT_ELEM(optr);
802	>	t = SM_NTH_TRI(sm,t_id);
803	>	if(!T_IS_VALID(t))
804	>	continue;
805	>	VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm));
806	>	VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm));
807	>	VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm));
808	>
809	>	if(EQUAL_VEC3(v0,p) || EQUAL_VEC3(v1,p) || EQUAL_VEC3(v2,p))
810	>	return(t_id);
811	>
812	>	VCROSS(n,v1,v0);
813	>	if(DOT(n,p) >0.0)
814	>	continue;
815	>	VCROSS(n,v2,v1);
816	>	if(DOT(n,p) > 0.0)
817	>	continue;
818	>
819	>	VCROSS(n,v0,v2);
820	>	if(DOT(n,p) > 0.0)
821	>	continue;
822	>
823	>	return(t_id);
824		}
825	<	else
909	<	tri = stPoint_locate(st,pt);
910	<	return(tri);
825	>	return(INVALID);
826		}
827
828	<	QUADTREE
829	<	smPointLocateCell(sm,pt,norm,v0,v1,v2)
828	>	int
829	>	smPointLocateTri(sm,id)
830		SM *sm;
831	<	FVECT pt;
917	<	int norm;
918	<	FVECT v0,v1,v2;
831	>	int id;
832		{
833	<	STREE *st;
834	<	QUADTREE *qtptr;
835	<	FVECT npt;
833	>	FVECT tpt;
834	>	QUADTREE qt,*optr;
835	>
836	>	VSUB(tpt,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
837	>	qt = smPointLocateCell(sm,tpt);
838	>	if(QT_IS_EMPTY(qt))
839	>	return(INVALID);
840	>
841	>	optr = qtqueryset(qt);
842	>	return(smTri_in_set(sm,tpt,optr));
843	>	}
844
845	<	st = SM_LOCATOR(sm);
846	<	if(norm)
845	>
846	>	/*
847	>	Determine whether this sample should:
848	>	a) be added to the mesh by subdividing the triangle
849	>	b) ignored
850	>	c) replace values of an existing mesh vertex
851	>
852	>	In case a, the routine will return TRUE, for b,c will return FALSE
853	>	In case a, also determine if this sample should cause the deletion of
854	>	an existing vertex. If so *rptr will contain the id of the sample to delete
855	>	after the new sample has been added.
856	>
857	>	ASSUMPTION: this will not be called with a new sample that is
858	>	a BASE point.
859	>
860	>	The following tests are performed (in order) to determine the fate
861	>	of the sample:
862	>
863	>	1) If the world space point of the sample coincides with one of the
864	>	triangle vertex samples: The values of the triangle sample are
865	>	replaced with the new values and FALSE is returned
866	>	2) If the new sample is close in ws, and close in the spherical projection
867	>	to one of the triangle vertex samples:
868	>	pick the point with dir closest to that of the canonical view
869	>	If it is the new point: mark existing point for deletion,and return
870	>	TRUE,else return FALSE
871	>	3) If the spherical projection of new is < REPLACE_EPS from a base point:
872	>	add new and mark the base for deletion: return TRUE
873	>	4) If the addition of the new sample point would introduce a "puncture"
874	>	or cause new triangles with large depth differences:return FALSE
875	>	This attempts to throw out points that should be occluded
876	>	*/
877	>	int
878	>	smTest_sample(sm,tri_id,s_id,dir,rptr)
879	>	SM *sm;
880	>	int tri_id,s_id;
881	>	FVECT dir;
882	>	int *rptr;
883	>	{
884	>	TRI *tri;
885	>	double d,d2,dnear,dspt,d01,d12,d20,s0,s1,s2,ds,dv;
886	>	int vid[3],i,nearid,norm,dcnt,bcnt;
887	>	FVECT diff[3],spt,npt;
888	>	FVECT p;
889	>
890	>	VCOPY(p,SM_NTH_WV(sm,s_id));
891	>	*rptr = INVALID;
892	>	bcnt = dcnt = 0;
893	>	tri = SM_NTH_TRI(sm,tri_id);
894	>	vid[0] = T_NTH_V(tri,0);
895	>	vid[1] = T_NTH_V(tri,1);
896	>	vid[2] = T_NTH_V(tri,2);
897	>
898	>	/* TEST 1: Test if the new point has the same world space point as
899	>	one of the existing triangle vertices
900	>	*/
901	>	for(i=0; i<3; i++)
902	>	{
903	>	if(SM_BASE_ID(sm,vid[i]))
904	>	{
905	>	bcnt++;
906	>	continue;
907	>	}
908	>	if(SM_DIR_ID(sm,vid[i]))
909	>	dcnt++;
910	>	VSUB(diff[i],SM_NTH_WV(sm,vid[i]),p);
911	>	/* If same world point: replace */
912	>	if(ZERO_VEC3(diff[i]))
913	>	{
914	>	sReset_samp(SM_SAMP(sm),vid[i],s_id);
915	>	SM_TONE_MAP(sm) = 0;
916	>	return(FALSE);
917	>	}
918	>	}
919	>	if(SM_DIR_ID(sm,s_id))
920	>	return(TRUE);
921	>	/* TEST 2: If the new sample is close in ws, and close in the spherical
922	>	projection to one of the triangle vertex samples
923	>	*/
924	>	norm = FALSE;
925	>	if(bcnt + dcnt != 3)
926	>	{
927	>	VSUB(spt,p,SM_VIEW_CENTER(sm));
928	>	ds = DOT(spt,spt);
929	>	dnear = FHUGE;
930	>	for(i=0; i<3; i++)
931	>	{
932	>	if(SM_BASE_ID(sm,vid[i]) || SM_DIR_ID(sm,vid[i]))
933	>	continue;
934	>	d = DOT(diff[i],diff[i])/ds;
935	>	if(d < dnear)
936	>	{
937	>	dnear = d;
938	>	nearid=vid[i];
939	>	}
940	>	}
941	>
942	>	if(dnear <=  smMinSampDiff*smMinSampDiff)
943	>	{
944	>	/* Pick the point with dir closest to that of the canonical view
945	>	if it is the new sample: mark existing point for deletion
946	>	*/
947	>	normalize(spt);
948	>	norm = TRUE;
949	>	VSUB(npt,SM_NTH_WV(sm,nearid),SM_VIEW_CENTER(sm));
950	>	normalize(npt);
951	>	d = fdir2diff(SM_NTH_W_DIR(sm,nearid), npt);
952	>	if(dir)
953	>	d2 = 2. - 2.*DOT(dir,spt);
954	>	else
955	>	d2 = fdir2diff(SM_NTH_W_DIR(sm,s_id), spt);
956	>	/* The existing sample is a better sample:punt */
957	>	if(d2 > d)
958	>	return(FALSE);
959	>	else
960	>	{
961	>	/* The new sample is better: mark the existing one
962	>	for deletion after the new one is added*/
963	>	*rptr = nearid;
964	>	return(TRUE);
965	>	}
966	>	}
967	>	}
968	>	/* TEST 3: If the spherical projection of new is < S_REPLACE_EPS
969	>	from a base point
970	>	*/
971	>	if(bcnt)
972	>	{
973	>	dnear = FHUGE;
974	>	if(bcnt + dcnt ==3)
975	>	VSUB(spt,p,SM_VIEW_CENTER(sm));
976	>	if(!norm)
977	>	normalize(spt);
978	>
979	>	for(i=0; i<3; i++)
980	>	{
981	>	if(!SM_BASE_ID(sm,vid[i]))
982	>	continue;
983	>	VSUB(npt,SM_NTH_WV(sm,vid[i]),SM_VIEW_CENTER(sm));
984	>	d = DIST_SQ(npt,spt);
985	>	if(d < S_REPLACE_EPS && d < dnear)
986	>	{
987	>	dnear = d;
988	>	nearid = vid[i];
989	>	}
990	>	}
991	>	if(dnear != FHUGE)
992	>	{
993	>	/* add new and mark the base for deletion */
994	>	*rptr = nearid;
995	>	return(TRUE);
996	>	}
997	>	}
998	>
999	>	/* TEST 4:
1000	>	If the addition of the new sample point would introduce a "puncture"
1001	>	or cause new triangles with large depth differences:dont add:
1002	>	*/
1003	>	if(bcnt || dcnt)
1004	>	return(TRUE);
1005	>	/* If the new point is in front of the existing points- add */
1006	>	dv = DIST_SQ(SM_NTH_WV(sm,vid[0]),SM_VIEW_CENTER(sm));
1007	>	if(ds < dv)
1008	>	return(TRUE);
1009	>
1010	>	d01 = DIST_SQ(SM_NTH_WV(sm,vid[1]),SM_NTH_WV(sm,vid[0]));
1011	>	s0 = DOT(diff[0],diff[0]);
1012	>	if(s0 < S_REPLACE_SCALE*d01)
1013	>	return(TRUE);
1014	>	d12 = DIST_SQ(SM_NTH_WV(sm,vid[2]),SM_NTH_WV(sm,vid[1]));
1015	>	if(s0 < S_REPLACE_SCALE*d12)
1016	>	return(TRUE);
1017	>	d20 = DIST_SQ(SM_NTH_WV(sm,vid[0]),SM_NTH_WV(sm,vid[2]));
1018	>	if(s0 < S_REPLACE_SCALE*d20)
1019	>	return(TRUE);
1020	>	d = MIN3(d01,d12,d20);
1021	>	s1 = DOT(diff[1],diff[1]);
1022	>	if(s1 < S_REPLACE_SCALE*d)
1023	>	return(TRUE);
1024	>	s2 = DOT(diff[2],diff[2]);
1025	>	if(s2 < S_REPLACE_SCALE*d)
1026	>	return(TRUE);
1027	>
1028	>
1029	>	return(FALSE);
1030	>	}
1031	>
1032	>
1033	>	int
1034	>	smAlloc_samp(sm,c,dir,pt)
1035	>	SM *sm;
1036	>	COLR c;
1037	>	FVECT dir,pt;
1038	>	{
1039	>	int s_id,replaced,cnt;
1040	>	SAMP *s;
1041	>	FVECT p;
1042	>
1043	>	s = SM_SAMP(sm);
1044	>	s_id = sAlloc_samp(s,&replaced);
1045	>
1046	>	cnt=0;
1047	>	while(replaced)
1048		{
1049	<	VSUB(npt,pt,SM_VIEW_CENTER(sm));
1050	<
1051	<	qtptr = stPoint_locate_cell(st,npt,v0,v1,v2);
1049	>	if(smMesh_remove_vertex(sm,s_id))
1050	>	break;
1051	>	s_id = sAlloc_samp(s,&replaced);
1052	>	cnt++;
1053	>	if(cnt > S_MAX_SAMP(s))
1054	>	error(CONSISTENCY,"smAlloc_samp():unable to find free samp\n");
1055		}
1056	+
1057	+	if(pt)
1058	+	sInit_samp(s,s_id,c,dir,pt);
1059		else
1060	<	qtptr = stPoint_locate_cell(st,pt,v0,v1,v2);
1061	<
1062	<	if(qtptr)
1063	<	return(*qtptr);
1064	<	else
937	<	return(EMPTY);
1060	>	{
1061	>	VADD(p,dir,SM_VIEW_CENTER(sm));
1062	>	sInit_samp(s,s_id,c,NULL,p);
1063	>	}
1064	>	return(s_id);
1065		}
1066
1067		int
1068	<	smAdd_sample_to_mesh(sm,c,dir,pt,s_id)
1068	>	smAdd_samp(sm,s_id,p,dir)
1069		SM *sm;
943	–	COLR c;
944	–	FVECT dir,pt;
1070		int s_id;
1071	+	FVECT p,dir;
1072		{
1073	<	int t_id;
1073	>	int t_id,r_id,test;
1074		double d;
1075	<	FVECT p;
1076	<
1077	<	/* If new, foreground pt */
1078	<	if(pt)
1075	>
1076	>	r_id = INVALID;
1077	>	t_id = smPointLocateTri(sm,s_id);
1078	>	if(t_id == INVALID)
1079		{
954	–	/* NOTE: This should be elsewhere! */
955	–	d = DIST(pt,SM_VIEW_CENTER(smMesh));
956	–	smDist_sum += 1.0/d;
957	–	/************************************/
958	–	t_id = smPointLocate(smMesh,pt,TRUE);
959	–	if(t_id >= 0)
960	–	s_id = smInsert_point_in_tri(smMesh,c,dir,pt,s_id,t_id);
1080		#ifdef DEBUG
1081	<	else
963	<	{
964	<	c[0] = 255;c[1]=0;c[2]=0;
965	<	s_id = smAdd_sample_point(sm,c,dir,pt);
966	<	eputs("smAdd_sample_to_mesh(): not found fg\n");
967	<	}
1081	>	eputs("smAdd_samp(): tri not found \n");
1082		#endif
1083	+	return(FALSE);
1084		}
1085	<	else if(s_id != -1)
1085	>	if(!SM_BASE_ID(sm,s_id))
1086		{
1087	<	VCOPY(p,SM_NTH_WV(sm,s_id));
1088	<	if(SM_NTH_W_DIR(sm,s_id) != -1)
1089	<	{
1090	<	/* NOTE: This should be elsewhere! */
1091	<	d = DIST(p,SM_VIEW_CENTER(smMesh));
1092	<	smDist_sum += 1.0/d;
1093	<	/************************************/
1094	<	}
980	<	t_id = smPointLocate(smMesh,p,TRUE);
981	<	if(t_id != -1)
982	<	s_id = smInsert_point_in_tri(smMesh,c,dir,p,s_id,t_id);
983	<	#ifdef DEBUG
984	<	else
985	<	eputs("smAdd_sample_to_mesh():not found reinsert\n");
986	<	#endif
1087	>	if(!smTest_sample(sm,t_id,s_id,dir,&r_id))
1088	>	return(FALSE);
1089	>	/* If not a sky point, add distance from the viewcenter to average*/
1090	>	if( !SM_DIR_ID(sm,s_id))
1091	>	{
1092	>	d = DIST(p,SM_VIEW_CENTER(smMesh));
1093	>	smDist_sum += 1.0/d;
1094	>	}
1095		}
1096	<	/* Is a BG(sky point) */
989	<	else
990	<	{
991	<	t_id = smPointLocate(smMesh,dir,FALSE);
992	<	if(t_id != -1)
993	<	s_id = smInsert_point_in_tri(smMesh,c,dir,NULL,s_id,t_id);
1096	>	test = smInsert_samp(smMesh,s_id,t_id);
1097
1098	<	#ifdef DEBUG
1099	<	else
1100	<	eputs("smAdd_sample_to_mesh(): not found bg\n");
1101	<	#endif
999	<	}
1000	<	return(s_id);
1098	>	if(test && r_id != INVALID)
1099	>	smMesh_remove_vertex(sm,r_id);
1100	>
1101	>	return(test);
1102		}
1103
1104		/*
#	Line 1019 | Line 1120 | FVECT p;
1120
1121		{
1122		int s_id;
1123	<	int debug=0;
1124	<
1123	>	int debug=0;
1124	>	static FILE *fp;
1125	>	static int cnt=0,n=3010;
1126		/* First check if this the first sample: if so initialize mesh */
1127		if(SM_NUM_SAMP(smMesh) == 0)
1128	<	smInit_mesh(smMesh,odev.v.vp);
1129	<	if(!debug)
1130	<	s_id = smAdd_sample_to_mesh(smMesh,c,dir,p,-1);
1128	>	{
1129	>	smInit_sm(smMesh,odev.v.vp);
1130	>	#if 0
1131	>	fp = fopen("Debug_data.view","w");
1132	>	fprintf(fp,"%d %d %f %f %f ",1280,1024,odev.v.vp[0],odev.v.vp[1],
1133	>	odev.v.vp[2]);
1134	>	fprintf(fp,"%f %f %f ",odev.v.vdir[0],odev.v.vdir[1],
1135	>	odev.v.vdir[2]);
1136	>	fprintf(fp,"%f %f %f ",odev.v.vup[0],odev.v.vup[1],odev.v.vup[2]);
1137	>	fprintf(fp,"%f %f ",odev.v.horiz,odev.v.vert);
1138	>	fclose(fp);
1139	>	fp = fopen("Debug_data","w");
1140	>	#endif
1141	>	}
1142	>	#if 0
1143	>	fprintf(fp,"%f %f %f %f %f %f ",p[0],p[1],p[2],(float)c[0]/255.0,(float)c[1]/255.0,
1144	>	(float)c[2]/255.0);
1145	>	#endif
1146	>
1147	>	/* Allocate space for a sample */
1148	>	s_id = smAlloc_samp(smMesh,c,dir,p);
1149	>	#if 0
1150	>	if(cnt==n)
1151	>	return(-1);
1152	>	cnt++;
1153	>	#endif
1154	>	/* Add the sample to the mesh */
1155	>	if(!smAdd_samp(smMesh,s_id,p,dir))
1156	>	{
1157	>	/* If the sample space was not used: return */
1158	>	smUnalloc_samp(smMesh,s_id);
1159	>	s_id = INVALID;
1160	>	}
1161		return(s_id);
1162
1163		}
1032	–	/*
1033	–	* int
1034	–	* smFindsamp(orig, dir): intersect ray with 3D rep. and find closest sample
1035	–	* FVECT        orig, dir;
1036	–	*
1037	–	* Find the closest sample to the given ray.  Return -1 on failure.
1038	–	*/
1039	–
1040	–	/*
1041	–	* smClean()            : display has been wiped clean
1042	–	*
1043	–	* Called after display has been effectively cleared, meaning that all
1044	–	* geometry must be resent down the pipeline in the next call to smUpdate().
1045	–	*/
1046	–
1047	–
1048	–	/*
1049	–	* smUpdate(vp, qua)    : update OpenGL output geometry for view vp
1050	–	* VIEW *vp;            : desired view
1051	–	* int  qua;            : quality level (percentage on linear time scale)
1052	–	*
1053	–	* Draw new geometric representation using OpenGL calls.  Assume that the
1054	–	* view has already been set up and the correct frame buffer has been
1055	–	* selected for drawing.  The quality level is on a linear scale, where 100%
1056	–	* is full (final) quality.  It is not necessary to redraw geometry that has
1057	–	* been output since the last call to smClean().
1058	–	*/
1059	–
1060	–
1164		int
1165	<	smClear_vert(sm,id)
1063	<	SM *sm;
1064	<	int id;
1065	<	{
1066	<	if(SM_INVALID_POINT_ID(sm,id))
1067	<	return(FALSE);
1068	<
1069	<	SM_NTH_VERT(sm,id) = SM_INVALID;
1070	<
1071	<	return(TRUE);
1072	<	}
1073	<
1074	<	int
1075	<	smAdd_base_vertex(sm,v,d)
1165	>	smAdd_base_vertex(sm,v)
1166		SM *sm;
1167	<	FVECT v,d;
1167	>	FVECT v;
1168		{
1169		int id;
1170
1171		/* First add coordinate to the sample array */
1172	<	id = smAdd_aux_point(sm,v,d);
1173	<	if(id == -1)
1174	<	return(SM_INVALID);
1172	>	id = sAdd_base_point(SM_SAMP(sm),v);
1173	>	if(id == INVALID)
1174	>	return(INVALID);
1175		/* Initialize triangle pointer to -1 */
1176		smClear_vert(sm,id);
1177		return(id);
#	Line 1099 | Line 1189 | smCreate_base_mesh(sm,type)
1189		SM *sm;
1190		int type;
1191		{
1192	<	int i,id,tri_id,nbr_id;
1192	>	int i,s_id,tri_id,nbr_id;
1193		int p[4],ids[4];
1194		int v0_id,v1_id,v2_id;
1195	<	TRI *tris[4];
1106	<	FVECT d,pt,cntr;
1195	>	FVECT d,pt,cntr,v0,v1,v2;
1196
1197		/* First insert the base vertices into the sample point array */
1198
1199		for(i=0; i < 4; i++)
1200		{
1201	<	VCOPY(cntr,stDefault_base[i]);
1201	>	VCOPY(cntr,smDefault_base[i]);
1202		cntr[0] += .01;
1203		cntr[1] += .02;
1204		cntr[2] += .03;
1205	<	VADD(cntr,cntr,SM_VIEW_CENTER(sm));
1206	<	point_on_sphere(d,cntr,SM_VIEW_CENTER(sm));
1118	<	id = smAdd_base_vertex(sm,cntr,d);
1119	<	/* test to make sure vertex allocated */
1120	<	if(id != -1)
1121	<	p[i] = id;
1122	<	else
1123	<	return(0);
1205	>	VADD(cntr,cntr,SM_VIEW_CENTER(sm));
1206	>	p[i]  = smAdd_base_vertex(sm,cntr);
1207		}
1208		/* Create the base triangles */
1209		for(i=0;i < 4; i++)
1210		{
1211	<	v0_id = p[stTri_verts[i][0]];
1212	<	v1_id = p[stTri_verts[i][1]];
1213	<	v2_id = p[stTri_verts[i][2]];
1214	<	if((ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id,&(tris[i])))== -1)
1215	<	return(0);
1133	<	smLocator_add_tri(sm,ids[i],v0_id,v1_id,v2_id);
1211	>	v0_id = p[smTri_verts[i][0]];
1212	>	v1_id = p[smTri_verts[i][1]];
1213	>	v2_id = p[smTri_verts[i][2]];
1214	>	ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id);
1215	>	smLocator_add_tri(sm,ids[i],v0_id,v1_id,v2_id,NULL);
1216		}
1217	+
1218		/* Set neighbors */
1219
1220		for(tri_id=0;tri_id < 4; tri_id++)
1221	<	for(nbr_id=0; nbr_id < 3; nbr_id++)
1222	<	T_NTH_NBR(tris[tri_id],nbr_id) = smBase_nbrs[tri_id][nbr_id];
1221	>	for(nbr_id=0; nbr_id < 3; nbr_id++)
1222	>	T_NTH_NBR(SM_NTH_TRI(sm,ids[tri_id]),nbr_id) = smBase_nbrs[tri_id][nbr_id];
1223
1224	<	return(1);
1224	>
1225	>	/* Now add the centroids of the faces */
1226	>	for(tri_id=0;tri_id < 4; tri_id++)
1227	>	{
1228	>	VCOPY(v0,SM_T_NTH_WV(sm,SM_NTH_TRI(sm,ids[tri_id]),0));
1229	>	VCOPY(v1,SM_T_NTH_WV(sm,SM_NTH_TRI(sm,ids[tri_id]),1));
1230	>	VCOPY(v2,SM_T_NTH_WV(sm,SM_NTH_TRI(sm,ids[tri_id]),2));
1231	>	tri_centroid(v0,v1,v2,cntr);
1232	>	VSUB(cntr,cntr,SM_VIEW_CENTER(sm));
1233	>	normalize(cntr);
1234	>	VADD(cntr,cntr,SM_VIEW_CENTER(sm));
1235	>	s_id = smAdd_base_vertex(sm,cntr);
1236	>	smAdd_samp(sm,s_id,NULL,NULL);
1237	>	}
1238	>	return(1);
1239
1240		}
1241
#	Line 1150 | Line 1247 | smNext_tri_flag_set(sm,i,which,b)
1247		int b;
1248		{
1249
1250	<	for(; i < SM_TRI_CNT(sm);i++)
1250	>	for(; i < SM_NUM_TRI(sm);i++)
1251		{
1252
1253	<	if(!SM_IS_NTH_T_FLAG(sm,i,which))
1253	>	if(!T_IS_VALID(SM_NTH_TRI(sm,i)))
1254		continue;
1255	+	if(!SM_IS_NTH_T_FLAG(sm,i,which))
1256	+	continue;
1257		if(!b)
1258		break;
1259		if((b==1) && !SM_BG_TRI(sm,i))
#	Line 1173 | Line 1272 | smNext_valid_tri(sm,i)
1272		int i;
1273		{
1274
1275	<	while( i < SM_TRI_CNT(sm) && !T_IS_VALID(SM_NTH_TRI(sm,i)))
1275	>	while( i < SM_NUM_TRI(sm) && !T_IS_VALID(SM_NTH_TRI(sm,i)))
1276		i++;
1277
1278		return(i);
#	Line 1181 | Line 1280 | smNext_valid_tri(sm,i)
1280
1281
1282
1283	<	qtTri_from_id(t_id,v0,v1,v2,n0,n1,n2,v0_idp,v1_idp,v2_idp)
1283	>	qtTri_from_id(t_id,v0,v1,v2)
1284		int t_id;
1285		FVECT v0,v1,v2;
1187	–	FVECT n0,n1,n2;
1188	–	int *v0_idp,*v1_idp,*v2_idp;
1286		{
1287		TRI *t;
1191	–	int v0_id,v1_id,v2_id;
1288
1289		t = SM_NTH_TRI(smMesh,t_id);
1290	<	v0_id = T_NTH_V(t,0);
1291	<	v1_id = T_NTH_V(t,1);
1292	<	v2_id = T_NTH_V(t,2);
1293	<
1294	<	if(v0)
1295	<	{
1200	<	VCOPY(v0,SM_NTH_WV(smMesh,v0_id));
1201	<	VCOPY(v1,SM_NTH_WV(smMesh,v1_id));
1202	<	VCOPY(v2,SM_NTH_WV(smMesh,v2_id));
1203	<	}
1204	<	if(n0)
1205	<	{
1206	<	smDir(smMesh,n0,v0_id);
1207	<	smDir(smMesh,n1,v1_id);
1208	<	smDir(smMesh,n2,v2_id);
1209	<
1210	<	}
1211	<	if(v0_idp)
1212	<	{
1213	<	*v0_idp = v0_id;
1214	<	*v1_idp = v1_id;
1215	<	*v2_idp = v2_id;
1216	<	}
1290	>	if(!T_IS_VALID(t))
1291	>	return(0);
1292	>	VSUB(v0,SM_T_NTH_WV(smMesh,t,0),SM_VIEW_CENTER(smMesh));
1293	>	VSUB(v1,SM_T_NTH_WV(smMesh,t,1),SM_VIEW_CENTER(smMesh));
1294	>	VSUB(v2,SM_T_NTH_WV(smMesh,t,2),SM_VIEW_CENTER(smMesh));
1295	>	return(1);
1296		}
1297
1298
1299	<	/*
1300	<	* int
1301	<	* smFindSamp(FVECT orig, FVECT dir)
1223	<	*
1224	<	* Find the closest sample to the given ray.  Returns sample id, -1 on failure.
1225	<	* "dir" is assumed to be normalized
1226	<	*/
1227	<	int
1228	<	smFindSamp(orig,dir)
1229	<	FVECT orig,dir;
1299	>	smRebuild_mesh(sm,v)
1300	>	SM *sm;
1301	>	VIEW *v;
1302		{
1303	<	FVECT r,v0,v1,v2,a,b,p;
1304	<	OBJECT os[QT_MAXCSET+1],t_set[QT_MAXSET+1],*ts;
1305	<	QUADTREE qt;
1234	<	int s_id;
1235	<	double d;
1303	>	int i,j,cnt;
1304	>	FVECT p,ov,dir;
1305	>	double d;
1306
1237	–	/*  r is the normalized vector from the view center to the current
1238	–	*  ray point ( starting with "orig"). Find the cell that r falls in,
1239	–	*  and test the ray against all triangles stored in the cell. If
1240	–	*  the test fails, trace the projection of the ray across to the
1241	–	*  next cell it intersects: iterate until either an intersection
1242	–	*  is found, or the projection ray is // to the direction. The sample
1243	–	*  corresponding to the triangle vertex closest to the intersection
1244	–	*  point is returned.
1245	–	*/
1246	–
1247	–	/* First test if "orig" coincides with the View_center or if "dir" is
1248	–	parallel to r formed by projecting "orig" on the sphere. In
1249	–	either case, do a single test against the cell containing the
1250	–	intersection of "dir" and the sphere
1251	–	*/
1252	–	point_on_sphere(b,orig,SM_VIEW_CENTER(smMesh));
1253	–	d = -DOT(b,dir);
1254	–	if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh)) || EQUAL(fabs(d),1.0))
1255	–	{
1256	–	qt = smPointLocateCell(smMesh,dir,FALSE,NULL,NULL,NULL);
1257	–	/* Test triangles in the set for intersection with Ray:returns
1258	–	first found
1259	–	*/
1260	–	ts = qtqueryset(qt);
1261	–	s_id = intersect_tri_set(ts,orig,dir,p);
1262	–	#ifdef DEBUG_TEST_DRIVER
1263	–	VCOPY(Pick_point[0],p);
1264	–	#endif
1265	–	return(s_id);
1266	–	}
1267	–	else
1268	–	{
1269	–	/* Starting with orig, Walk along projection of ray onto sphere */
1270	–	point_on_sphere(r,orig,SM_VIEW_CENTER(smMesh));
1271	–	qt = smPointLocateCell(smMesh,r,FALSE,v0,v1,v2);
1272	–	/* os will contain all triangles seen thus far */
1273	–	qtgetset(t_set,qt);
1274	–	setcopy(os,t_set);
1275	–
1276	–	/* Calculate ray perpendicular to dir: when projection ray is // to dir,
1277	–	the dot product will become negative.
1278	–	*/
1279	–	VSUM(a,b,dir,d);
1280	–	d = DOT(a,b);
1281	–	while(d > 0)
1282	–	{
1283	–	s_id = intersect_tri_set(t_set,orig,dir,p);
1284	–	#ifdef DEBUG_TEST_DRIVER
1285	–	VCOPY(Pick_point[0],p);
1286	–	#endif
1287	–	if(s_id != EMPTY)
1288	–	return(s_id);
1289	–	/* Find next cell that projection of ray intersects */
1290	–	traceRay(r,dir,v0,v1,v2,r);
1291	–	qt = smPointLocateCell(smMesh,r,FALSE,v0,v1,v2);
1292	–	qtgetset(t_set,qt);
1293	–	/* Check triangles in set against those seen so far(os):only
1294	–	check new triangles for intersection (t_set')
1295	–	*/
1296	–	check_set(t_set,os);
1297	–	d = DOT(a,r);
1298	–	}
1299	–	}
1307		#ifdef DEBUG
1308	<	eputs("smFindSamp():Pick Ray did not intersect mesh");
1308	>	eputs("smRebuild_mesh(): rebuilding....");
1309		#endif
1303	–	return(EMPTY);
1304	–	}
1305	–
1306	–
1307	–	smRebuild_mesh(sm,vp)
1308	–	SM *sm;
1309	–	FVECT vp;
1310	–	{
1311	–	int i;
1312	–	FVECT dir;
1313	–	COLR c;
1314	–	FVECT p,ov;
1315	–
1310		/* Clear the mesh- and rebuild using the current sample array */
1311	+	/* Remember the current number of samples */
1312	+	cnt = SM_NUM_SAMP(sm);
1313	+	/* Calculate the difference between the current and new viewpoint*/
1314	+	/* Will need to subtract this off of sky points */
1315	+	VSUB(ov,v->vp,SM_VIEW_CENTER(sm));
1316	+	/* Initialize the mesh to 0 samples and the base triangles */
1317
1318	<	VSUB(ov,vp,SM_VIEW_CENTER(sm));
1319	<	smInit_mesh(sm,vp);
1320	<
1321	<	SM_FOR_ALL_SAMPLES(sm,i)
1318	>	/* Go through all samples and add in if in the new view frustum, and
1319	>	the dir is <= 30 degrees from new view
1320	>	*/
1321	>	j=0;
1322	>	for(i=0; i < cnt; i++)
1323		{
1324	<	if(SM_NTH_W_DIR(sm,i)==-1)
1325	<	VADD(SM_NTH_WV(sm,i),SM_NTH_WV(sm,i),ov);
1326	<	smAdd_sample_to_mesh(sm,NULL,NULL,NULL,i);
1324	>	/* First check if sample visible(conservative approx: if one of tris
1325	>	attached to sample is in frustum)       */
1326	>	if(!S_IS_FLAG(i))
1327	>	continue;
1328	>
1329	>	/* Next test if direction > 30 from current direction */
1330	>	if(SM_NTH_W_DIR(sm,i)!=-1)
1331	>	{
1332	>	VSUB(p,SM_NTH_WV(sm,i),v->vp);
1333	>	normalize(p);
1334	>	d = fdir2diff(SM_NTH_W_DIR(sm,i), p);
1335	>	if (d > MAXDIFF2)
1336	>	continue;
1337	>	}
1338	>	sReset_samp(SM_SAMP(sm),j,i);
1339	>	j++;
1340		}
1341	+	smInit_sm(sm,v->vp);
1342	+	for(i=0; i< j; i++)
1343	+	{
1344	+	S_SET_FLAG(i);
1345	+	VCOPY(p,SM_NTH_WV(sm,i));
1346	+	smAdd_samp(sm,i,p,NULL);
1347	+	}
1348	+	SM_NUM_SAMP(sm) = j;
1349	+	smNew_tri_cnt = SM_SAMPLE_TRIS(sm);
1350	+	#ifdef DEBUG
1351	+	eputs("smRebuild_mesh():done\n");
1352	+	#endif
1353		}
1354
1355		int
#	Line 1343 | Line 1369 | intersect_tri_set(t_set,orig,dir,pt)
1369		t_id = QT_SET_NEXT_ELEM(optr);
1370
1371		t = SM_NTH_TRI(smMesh,t_id);
1372	+	if(!T_IS_VALID(t))
1373	+	continue;
1374	+
1375		pid0 = T_NTH_V(t,0);
1376		pid1 = T_NTH_V(t,1);
1377		pid2 = T_NTH_V(t,2);
#	Line 1366 | Line 1395 | intersect_tri_set(t_set,orig,dir,pt)
1395		return(-1);
1396		}
1397
1398	<	int
1399	<	ray_trace_check_set(qtptr,orig,dir,tptr,os)
1398	>	/* OS is constrained to be <= QT_MAXCSET : if the set exceeds this, the
1399	>	results of check_set are conservative
1400	>	*/
1401	>
1402	>	ray_trace_check_set(qtptr,fptr,argptr)
1403		QUADTREE *qtptr;
1404	<	FVECT orig,dir;
1405	<	int *tptr;
1374	<	OBJECT *os;
1404	>	int *fptr;
1405	>	RT_ARGS *argptr;
1406		{
1407	<	OBJECT tset[QT_MAXSET+1];
1407	>	OBJECT tset[QT_MAXSET+1],*tptr;
1408		double dt,t;
1409		int found;
1379	–	FVECT o;
1410
1411	<
1411	>	if(QT_LEAF_IS_FLAG(*qtptr))
1412	>	{
1413	>	QT_FLAG_SET_DONE(*fptr);
1414	>	#if DEBUG
1415	>	eputs("ray_trace_check_set():Already visited this node:aborting\n");
1416	>	#endif
1417	>	return;
1418	>	}
1419		if(!QT_IS_EMPTY(*qtptr))
1420	<	{
1421	<	VADD(o,orig,SM_VIEW_CENTER(smMesh));
1422	<	qtgetset(tset,*qtptr);
1420	>	{
1421	>	tptr = qtqueryset(*qtptr);
1422	>	if(QT_SET_CNT(tptr) > QT_MAXSET)
1423	>	tptr = (OBJECT *)malloc((QT_SET_CNT(tptr)+1)*sizeof(OBJECT));
1424	>	else
1425	>	tptr = tset;
1426	>	if(!tptr)
1427	>	goto memerr;
1428	>
1429	>	qtgetset(tptr,*qtptr);
1430		/* Check triangles in set against those seen so far(os):only
1431		check new triangles for intersection (t_set')
1432		*/
1433	<	check_set(tset,os);
1434	<	if((found = intersect_tri_set(tset,o,dir,NULL))!= -1)
1435	<	{
1436	<	*tptr = found;
1437	<	return(QT_DONE);
1438	<	}
1433	>	check_set_large(tptr,argptr->os);
1434	>	if((found = intersect_tri_set(tptr,argptr->orig,argptr->dir,NULL))!= -1)
1435	>	{
1436	>	argptr->t_id = found;
1437	>	if(tptr != tset)
1438	>	free(tptr);
1439	>	QT_FLAG_SET_DONE(*fptr);
1440	>	return;
1441		}
1442	<	return(FALSE);
1442	>	if(tptr != tset)
1443	>	free(tptr);
1444	>	}
1445	>	return;
1446	>	memerr:
1447	>	error(SYSTEM,"ray_trace_check_set():Unable to allocate memory");
1448		}
1449
1450	+
1451	+	/*
1452	+	* int
1453	+	* smFindSamp(FVECT orig, FVECT dir)
1454	+	*
1455	+	* Find the closest sample to the given ray.  Returns sample id, -1 on failure.
1456	+	* "dir" is assumed to be normalized
1457	+	*/
1458	+
1459		int
1460	<	smFindSamp_opt(orig,dir)
1460	>	smFindSamp(orig,dir)
1461		FVECT orig,dir;
1462		{
1463		FVECT b,p,o;
#	Line 1428 | Line 1488 | FVECT orig,dir;
1488		d = -DOT(b,dir);
1489		if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh)) || EQUAL(fabs(d),1.0))
1490		{
1491	<	qt = smPointLocateCell(smMesh,dir,FALSE,NULL,NULL,NULL);
1491	>	qt = smPointLocateCell(smMesh,dir);
1492		/* Test triangles in the set for intersection with Ray:returns
1493		first found
1494		*/
1495	+	#ifdef DEBUG
1496	+	if(QT_IS_EMPTY(qt))
1497	+	{
1498	+	eputs("smFindSamp(): point not found");
1499	+	return;
1500	+	}
1501	+	#endif
1502		ts = qtqueryset(qt);
1503		s_id = intersect_tri_set(ts,orig,dir,p);
1504		#ifdef DEBUG_TEST_DRIVER
#	Line 1440 | Line 1507 | FVECT orig,dir;
1507		}
1508		else
1509		{
1510	<	OBJECT t_set[QT_MAXCSET+1];
1510	>	OBJECT t_set[QT_MAXCSET + 1];
1511	>	RT_ARGS rt;
1512	>
1513		/* Test each of the root triangles against point id */
1514		QT_CLEAR_SET(t_set);
1515		VSUB(o,orig,SM_VIEW_CENTER(smMesh));
1516		ST_CLEAR_FLAGS(SM_LOCATOR(smMesh));
1517	<	s_id=stTrace_ray(SM_LOCATOR(smMesh),o,dir,ray_trace_check_set,&s_id,t_set);
1517	>	rt.t_id = -1;
1518	>	rt.os = t_set;
1519	>	VCOPY(rt.orig,orig);
1520	>	VCOPY(rt.dir,dir);
1521	>	stTrace_ray(SM_LOCATOR(smMesh),o,dir,ray_trace_check_set,&rt);
1522	>	s_id = rt.t_id;
1523		}
1524		return(s_id);
1525		}
1452	–
1526
1527
1528

Diff Legend

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