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.4 by gwlarson, Tue Aug 25 11:03:27 1998 UTC vs.
Revision 3.9 by gwlarson, Wed Nov 11 12:05:37 1998 UTC

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

Diff Legend

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