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.10 by gwlarson, Mon Dec 28 19:30:27 1998 UTC vs.
Revision 3.19 by schorsch, Mon Jun 30 14:59:12 2003 UTC

#	Line 1 | Line 1
1	–	/* Copyright (c) 1998 Silicon Graphics, Inc. */
2	–
1		#ifndef lint
2	<	static char SCCSid[] = "$SunId$ SGI";
2	>	static const char       RCSid[] = "$Id$";
3		#endif
6	–
4		/*
5		*  sm.c
6		*/
7	+
8	+	#include <string.h>
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"
14		#include "sm.h"
15
18	–
16		SM *smMesh = NULL;
17		double smDist_sum=0;
21	–	int smNew_tri_cnt=0;
22	–	double smMinSampDiff = 4.25e-4; /* min edge length in radians */
18
19	<	/* Each edge extends .5536 radians - 31.72 degrees */
19	>	#ifdef DEBUG
20	>	int Tcnt=0,Wcnt=0;
21	>	#endif
22	>	/* Each edge extends .372 radians  */
23		static FVECT icosa_verts[162] =
24		{{-0.018096,0.495400,0.868477},{0.018614,-0.554780,0.831789},
25		{0.850436,0.011329,0.525956},{0.850116,0.048016,-0.524402},
#	Line 128 | Line 126 | static int icosa_tris[320][3] =
126		{34,112,114},{112,33,113},{114,113,1},{112,113,114},{32,111,107},{111,33,112},
127		{107,112,34},{111,112,107},{9,109,116},{109,32,115},{116,115,36},{109,115,116},
128		{32,106,118},{106,8,117},{118,117,35},{106,117,118},{36,119,121},{119,35,120},
129	<	{121,120,11},{119,120,121},{32,118,115},{118,35,119},{115,119,36},{118,119,115},
130	<	{10,122,124},{122,37,123},{124,123,39},{122,123,124},{37,125,127},{125,11,126},
131	<	{127,126,38},{125,126,127},{39,128,130},{128,38,129},{130,129,3},{128,129,130},
129	>	{121,120,11},{119,120,121},{32,118,115},{118,35,119},{115,119,36},
130	>	{118,119,115},{10,122,124},{122,37,123},{124,123,39},{122,123,124},
131	>	{37,125,127},{125,11,126},{127,126,38},{125,126,127},{39,128,130},
132	>	{128,38,129},{130,129,3},{128,129,130},
133		{37,127,123},{127,38,128},{123,128,39},{127,128,123},{11,125,132},{125,37,131},
134	<	{132,131,41},{125,131,132},{37,122,134},{122,10,133},{134,133,40},{122,133,134},
135	<	{41,135,137},{135,40,136},{137,136,5},{135,136,137},{37,134,131},{134,40,135},
134	>	{132,131,41},{125,131,132},{37,122,134},{122,10,133},{134,133,40},
135	>	{122,133,134},{41,135,137},{135,40,136},{137,136,5},{135,136,137},
136	>	{37,134,131},{134,40,135},
137		{131,135,41},{134,135,131},{6,65,94},{65,18,138},{94,138,28},{65,138,94},
138	<	{18,62,139},{62,2,49},{139,49,13},{62,49,139},{28,140,97},{140,13,46},{97,46,0},
139	<	{140,46,97},{18,139,138},{139,13,140},{138,140,28},{139,140,138},{1,44,114},
138	>	{18,62,139},{62,2,49},{139,49,13},{62,49,139},{28,140,97},{140,13,46},
139	>	{97,46,0},{140,46,97},{18,139,138},{139,13,140},{138,140,28},{139,140,138},
140	>	{1,44,114},
141		{44,14,141},{114,141,34},{44,141,114},{14,50,142},{50,2,68},{142,68,21},
142		{50,68,142},{34,143,108},{143,21,73},{108,73,8},{143,73,108},{14,142,141},
143		{142,21,143},{141,143,34},{142,143,141},{0,52,98},{52,16,144},{98,144,29},
#	Line 152 | Line 153 | static int icosa_tris[320][3] =
153		{155,38,126},{120,126,11},{155,126,120},{20,154,153},{154,38,155},{153,155,35},
154		{154,155,153},{7,81,101},{81,23,156},{101,156,30},{81,156,101},{23,78,157},
155		{78,5,136},{157,136,40},{78,136,157},{30,158,104},{158,40,133},{104,133,10},
156	<	{158,133,104},{23,157,156},{157,40,158},{156,158,30},{157,158,156},{11,132,121},
156	>	{158,133,104},{23,157,156},{157,40,158},{156,158,30},{157,158,156},{
157	>	11,132,121},
158		{132,41,159},{121,159,36},{132,159,121},{41,137,160},{137,5,84},{160,84,26},
159		{137,84,160},{36,161,116},{161,26,89},{116,89,9},{161,89,116},{41,160,159},
160		{160,26,161},{159,161,36},{160,161,159}};
#	Line 192 | Line 194 | static int icosa_nbrs[320][3] =
194		{182,180,181},{187,308,190},{294,187,189},{293,309,187},{186,184,185},
195		{191,177,180},{185,191,182},{184,178,191},{190,188,189},{195,101,42},
196		{204,195,41},{206,102,195},{194,192,193},{199,204,38},{10,199,37},{9,205,199},
197	<	{198,196,197},{203,105,206},{6,203,205},{5,106,203},{202,200,201},{207,193,196},
198	<	{201,207,198},{200,194,207},{206,204,205},{211,138,0},{220,211,2},{222,136,211},
199	<	{210,208,209},{215,220,8},{48,215,10},{50,221,215},{214,212,213},{219,130,222},
197	>	{198,196,197},{203,105,206},{6,203,205},{5,106,203},{202,200,201},
198	>	{207,193,196},{201,207,198},{200,194,207},{206,204,205},{211,138,0},
199	>	{220,211,2}, {222,136,211},{210,208,209},{215,220,8},{48,215,10},{50,221,215},
200	>	{214,212,213},{219,130,222},
201		{56,219,221},{58,128,219},{218,216,217},{223,209,212},{217,223,214},
202		{216,210,223},{222,220,221},{227,106,16},{236,227,18},{238,104,227},
203	<	{226,224,225},{231,236,24},{64,231,26},{66,237,231},{230,228,229},{235,98,238},
203	>	{226,224,225},{231,236,24},{64,231,26},{66,237,231},{230,228,229},
204	>	{235,98,238},
205		{72,235,237},{74,96,235},{234,232,233},{239,225,228},{233,239,230},
206		{232,226,239},{238,236,237},{243,133,90},{252,243,89},{254,134,243},
207	<	{242,240,241},{247,252,86},{26,247,85},{25,253,247},{246,244,245},{251,137,254},
207	>	{242,240,241},{247,252,86},{26,247,85},{25,253,247},{246,244,245},
208	>	{251,137,254},
209		{22,251,253},{21,138,251},{250,248,249},{255,241,244},{249,255,246},
210		{248,242,255},{254,252,253},{259,122,160},{268,259,162},{270,120,259},
211		{258,256,257},{263,268,168},{32,263,170},{34,269,263},{262,260,261},
#	Line 230 | Line 235 | FVECT FrustumNear[4],FrustumFar[4];
235		double dev_zmin=.01,dev_zmax=1000;
236		#endif
237
238	<	smDir(sm,ps,id)
239	<	SM *sm;
240	<	FVECT ps;
241	<	int id;
238	>
239	>	char *
240	>	tempbuf(len,resize)                     /* get a temporary buffer */
241	>	unsigned  len;
242	>	int resize;
243		{
244	<	VSUB(ps,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
245	<	normalize(ps);
244	>	static char  *tempbuf = NULL;
245	>	static unsigned  tempbuflen = 0;
246	>
247	>	#ifdef DEBUG
248	>	static int in_use=FALSE;
249	>
250	>	if(len == -1)
251	>	{
252	>	in_use = FALSE;
253	>	return(NULL);
254	>	}
255	>	if(!resize && in_use)
256	>	{
257	>	eputs("Buffer in use:cannot allocate:tempbuf()\n");
258	>	return(NULL);
259	>	}
260	>	#endif
261	>	if (len > tempbuflen) {
262	>	if (tempbuflen > 0)
263	>	tempbuf = realloc((void *)tempbuf, len);
264	>	else
265	>	tempbuf = malloc(len);
266	>	tempbuflen = tempbuf==NULL ? 0 : len;
267	>	}
268	>	#ifdef DEBUG
269	>	in_use = TRUE;
270	>	#endif
271	>	return(tempbuf);
272		}
273
274	<	smDir_in_cone(sm,ps,id)
274	>	smDir(sm,ps,id)
275		SM *sm;
276		FVECT ps;
277	<	int id;
277	>	S_ID id;
278		{
247	–
279		VSUB(ps,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
280		normalize(ps);
281		}
#	Line 257 | Line 288 | int which;
288
289		if(which== -1)
290		for(i=0; i < T_FLAGS;i++)
291	<	bzero(SM_NTH_FLAGS(sm,i),FLAG_BYTES(SM_MAX_TRIS(sm)));
291	>	memset(SM_NTH_FLAGS(sm,i), '\0', FLAG_BYTES(SM_MAX_TRIS(sm)));
292		else
293	<	bzero(SM_NTH_FLAGS(sm,which),FLAG_BYTES(SM_MAX_TRIS(sm)));
293	>	memset(SM_NTH_FLAGS(sm,which), '\0', FLAG_BYTES(SM_MAX_TRIS(sm)));
294		}
295
296		/* Given an allocated mesh- initialize */
#	Line 268 | Line 299 | smInit_mesh(sm)
299		{
300		/* Reset the triangle counters */
301		SM_NUM_TRI(sm) = 0;
271	–	SM_SAMPLE_TRIS(sm) = 0;
302		SM_FREE_TRIS(sm) = -1;
273	–	SM_AVAILABLE_TRIS(sm) = -1;
303		smClear_flags(sm,-1);
304		}
305
#	Line 281 | Line 310 | smInit_mesh(sm)
310		smClear(sm)
311		SM *sm;
312		{
313	<	smClear_samples(sm);
314	<	smClear_locator(sm);
313	>	smDist_sum = 0;
314	>	smInit_samples(sm);
315	>	smInit_locator(sm);
316		smInit_mesh(sm);
317		}
318
289	–	static int realloc_cnt=0;
290	–
291	–	int
292	–	smRealloc_mesh(sm)
293	–	SM *sm;
294	–	{
295	–	int fbytes,i,max_tris,max_verts;
296	–
297	–	if(realloc_cnt <=0)
298	–	realloc_cnt = SM_MAX_TRIS(sm);
299	–
300	–	max_tris = SM_MAX_TRIS(sm) + realloc_cnt;
301	–	fbytes = FLAG_BYTES(max_tris);
302	–
303	–	if(!(SM_TRIS(sm) = (TRI *)realloc(SM_TRIS(sm),max_tris*sizeof(TRI))))
304	–	goto memerr;
305	–
306	–	for(i=0; i< T_FLAGS; i++)
307	–	if(!(SM_NTH_FLAGS(sm,i)=(int4 *)realloc((char *)SM_NTH_FLAGS(sm,i),fbytes)))
308	–	goto memerr;
309	–
310	–	SM_MAX_TRIS(sm) = max_tris;
311	–	return(max_tris);
312	–
313	–	memerr:
314	–	error(SYSTEM, "out of memory in smRealloc_mesh()");
315	–	}
316	–
319		/* Allocate and initialize a new mesh with max_verts and max_tris */
320		int
321		smAlloc_mesh(sm,max_verts,max_tris)
#	Line 324 | Line 326 | int max_verts,max_tris;
326
327		fbytes = FLAG_BYTES(max_tris);
328
329	<	if(!(SM_TRIS(sm) = (TRI *)realloc(NULL,max_tris*sizeof(TRI))))
329	>	if(!(SM_TRIS(sm) = (TRI *)malloc(max_tris*sizeof(TRI))))
330		goto memerr;
331
330	–	if(!(SM_VERTS(sm) = (VERT *)realloc(NULL,max_verts*sizeof(VERT))))
331	–	goto memerr;
332	–
332		for(i=0; i< T_FLAGS; i++)
333	<	if(!(SM_NTH_FLAGS(sm,i)=(int4 *)realloc(NULL,fbytes)))
333	>	if(!(SM_NTH_FLAGS(sm,i)=(int32 *)malloc(fbytes)))
334		goto memerr;
335
336		SM_MAX_VERTS(sm) = max_verts;
337		SM_MAX_TRIS(sm) = max_tris;
338
340	–	realloc_cnt = max_verts >> 1;
341	–
339		smInit_mesh(sm);
340
341		return(max_tris);
#	Line 347 | Line 344 | memerr:
344		}
345
346
347	<	int
348	<	compress_set(os)
349	<	OBJECT *os;
350	<	{
351	<	int i,j;
352	<
356	<	for (i = 1, j = os[0]; i <= j; i++)
357	<	{
358	<	if(SM_T_ID_VALID(smMesh,os[i]))
359	<	continue;
360	<	if(i==j)
361	<	break;
362	<	while(!SM_T_ID_VALID(smMesh,os[j]) && (i < j))
363	<	j--;
364	<	if(i==j)
365	<	break;
366	<	os[i] = os[j--];
367	<	}
368	<	i--;
369	<
370	<	os[0] = i;
371	<	return(i);
372	<
373	<	}
374	<
347	>	/*
348	>	* smAlloc_tri(sm) : Allocate a new mesh triangle
349	>	* SM *sm;                    : mesh
350	>	*
351	>	*  Returns ptr to next available tri
352	>	*/
353		int
354		smAlloc_tri(sm)
355		SM *sm;
#	Line 382 | Line 360 | SM *sm;
360		/* Otherwise, have we reached the end of the list yet?*/
361		if(SM_NUM_TRI(sm) < SM_MAX_TRIS(sm))
362		return(SM_NUM_TRI(sm)++);
385	–	if((id = SM_AVAILABLE_TRIS(sm)) != -1)
386	–	{
387	–	SM_AVAILABLE_TRIS(sm) =  T_NEXT_AVAILABLE(SM_NTH_TRI(sm,id));
388	–	return(id);
389	–	}
363		if((id = SM_FREE_TRIS(sm)) != -1)
364		{
365	<	dosets(compress_set);
393	<	SM_AVAILABLE_TRIS(sm) = T_NEXT_FREE(SM_NTH_TRI(sm,id));
394	<	SM_FREE_TRIS(sm) = -1;
365	>	SM_FREE_TRIS(sm) =  T_NEXT_FREE(SM_NTH_TRI(sm,id));
366		return(id);
367		}
368	<	/*Else: realloc */
369	<	smRealloc_mesh(sm);
370	<	return(SM_NUM_TRI(sm)++);
368	>
369	>	error(CONSISTENCY,"smAlloc_tri: no more available triangles\n");
370	>	return(INVALID);
371		}
372
373	+
374		smFree_mesh(sm)
375		SM *sm;
376		{
#	Line 406 | Line 378 | SM *sm;
378
379		if(SM_TRIS(sm))
380		free(SM_TRIS(sm));
409	–	if(SM_VERTS(sm))
410	–	free(SM_VERTS(sm));
381		for(i=0; i< T_FLAGS; i++)
382		if(SM_NTH_FLAGS(sm,i))
383		free(SM_NTH_FLAGS(sm,i));
384		}
385
386	<
387	<	/* Initialize/clear global smL sample list for at least n samples */
386	>
387	>	/*
388	>	* smAlloc(max_samples) : Initialize/clear global sample list for at least
389	>	*                       max_samples
390	>	* int max_samples;
391	>	*
392	>	*/
393		smAlloc(max_samples)
394		register int max_samples;
395		{
#	Line 429 | Line 404 | smAlloc(max_samples)
404		{
405		if(!(smMesh = (SM *)malloc(sizeof(SM))))
406		error(SYSTEM,"smAlloc():Unable to allocate memory\n");
407	<	bzero(smMesh,sizeof(SM));
407	>	memset(smMesh, '\0', sizeof(SM));
408		}
409		else
410		{   /* If existing structure: first deallocate */
#	Line 441 | Line 416 | smAlloc(max_samples)
416		/* First allocate at least n samples + extra points:at least enough
417		necessary to form the BASE MESH- Default = 4;
418		*/
419	<	SM_SAMP(smMesh) = sAlloc(&n,SM_EXTRA_POINTS);
419	>	SM_SAMP(smMesh) = sAlloc(&n,SM_BASE_POINTS);
420
421	<	total_points = n + SM_EXTRA_POINTS;
421	>	total_points = n + SM_BASE_POINTS;
422
423	<	max_tris = total_points*4;
423	>	/* Need enough tris for base mesh, + 2 for each sample, plus extra
424	>	since triangles are not deleted until added and edge flips (max 4)
425	>	*/
426	>	max_tris = n*2 + SM_BASE_TRIS + 10;
427		/* Now allocate space for mesh vertices and triangles */
428		max_tris = smAlloc_mesh(smMesh, total_points, max_tris);
429
#	Line 460 | Line 438 | smInit_sm(sm,vp)
438		SM *sm;
439		FVECT vp;
440		{
463	–
464	–	smDist_sum = 0;
465	–	smNew_tri_cnt = 0;
466	–
441		VCOPY(SM_VIEW_CENTER(sm),vp);
442	<	smInit_locator(sm,vp);
469	<	smInit_samples(sm);
470	<	smInit_mesh(sm);
442	>	smClear(sm);
443		smCreate_base_mesh(sm,SM_DEFAULT);
444		}
445
#	Line 481 | Line 453 | FVECT vp;
453		* If n is <= 0, then clear data structures.  Returns number samples
454		* actually allocated.
455		*/
484	–
456		int
457		smInit(n)
458		register int n;
459		{
460		int max_vertices;
461	<
491	<
461	>	sleep(5);
462		/* If n <=0, Just clear the existing structures */
463		if(n <= 0)
464		{
465	+	#ifdef DEBUG
466	+	fprintf(stderr,"Tcnt=%d Wcnt = %d, avg = %f\n",Tcnt,Wcnt,(float)Wcnt/Tcnt);
467	+	#endif
468		smClear(smMesh);
469		return(0);
470		}
#	Line 499 | Line 472 | smInit(n)
472		/* Total mesh vertices includes the sample points and the extra vertices
473		to form the base mesh
474		*/
475	<	max_vertices = n + SM_EXTRA_POINTS;
475	>	max_vertices = n + SM_BASE_POINTS;
476
477		/* If the current mesh contains enough room, clear and return */
478		if(smMesh && (max_vertices <= SM_MAX_VERTS(smMesh)) && SM_MAX_SAMP(smMesh) <=
#	Line 513 | Line 486 | smInit(n)
486		*/
487		smAlloc(n);
488
489	+	#ifdef DEBUG
490	+	fprintf(stderr,"smInit: allocating room for %d samples\n",
491	+	SM_MAX_SAMP(smMesh));
492	+	#endif
493		return(SM_MAX_SAMP(smMesh));
494		}
495
496
497	<	smLocator_apply(sm,v0,v1,v2,func)
497	>	smLocator_apply(sm,v0,v1,v2,func,n)
498		SM *sm;
499		FVECT v0,v1,v2;
500		FUNC func;
501	+	int n;
502		{
503		STREE *st;
504		FVECT tri[3];
#	Line 530 | Line 508 | smLocator_apply(sm,v0,v1,v2,func)
508		VSUB(tri[0],v0,SM_VIEW_CENTER(sm));
509		VSUB(tri[1],v1,SM_VIEW_CENTER(sm));
510		VSUB(tri[2],v2,SM_VIEW_CENTER(sm));
511	<	stVisit(st,tri,func);
511	>	stVisit(st,tri,func,n);
512
513		}
514
515	<
516	<	/* NEW INSERTION!!! ******************************************************/
515	>	/*
516	>	* QUADTREE
517	>	* insert_samp(argptr,root,qt,parent,q0,q1,q2,bc,scale,rev,f,n,doneptr)
518	>	*     Callback function called from quadtree traversal when leaf is reached
519	>	*   int *argptr;                 :ptr to sample id number
520	>	*   int root;                    :quadtree root from which traversal started
521	>	*   QUADTREE qt,parent;          :current quadtree node and its parent
522	>	*   BCOORD q0[3],q1[3],q2[3],bc[3]; :barycentric coordinates of the current
523	>	*                                 quadtree node (q0,q1,q2) and sample (bc)
524	>	*   unsigned int scale,rev;      :scale factor relative to which level at in
525	>	*                                 tree, rev indicates if traversed of child 3
526	>	*   FUNC f;                      :function structure so can recurse
527	>	*   int n,*doneptr;              :n indicates which level at in quadtree, and
528	>	*                                 doneptr can be set to indicate whether nbr
529	>	*                                 sample has been found
530	>	*/
531		QUADTREE
532	<	insert_tri(argptr,root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
541	<	s0,s1,s2,sq0,sq1,sq2,rev,f,n)
532	>	insert_samp(argptr,root,qt,parent,q0,q1,q2,bc,scale,rev,f,n,doneptr)
533		int *argptr;
534		int root;
535	<	QUADTREE qt;
536	<	BCOORD q0[3],q1[3],q2[3];
537	<	BCOORD t0[3],t1[3],t2[3];
547	<	BCOORD dt10[3],dt21[3],dt02[3];
548	<	unsigned int scale,s0,s1,s2,sq0,sq1,sq2,rev;
535	>	QUADTREE qt,parent;
536	>	BCOORD q0[3],q1[3],q2[3],bc[3];
537	>	unsigned int scale,rev;
538		FUNC f;
539	<	int n;
539	>	int n,*doneptr;
540		{
541	<	OBJECT *optr,*tptr,t_set[QT_MAXSET+1];
542	<	int i,t_id;
554	<	TRI *t;
555	<	FVECT tri[3];
556	<	BCOORD b0[3],b1[3],b2[3];
557	<	BCOORD tb0[3],tb1[3],tb2[3];
558	<	BCOORD db10[3],db21[3],db02[3];
559	<	BCOORD a,b,c,qa,qb,qc;
560	<	FUNC tfunc;
541	>	S_ID s_id;
542	>	S_ID *optr;
543
544	<	t_id = *argptr;
563	<
544	>	s_id = ((S_ARGS *)argptr)->s_id;
545		/* If the set is empty - just add */
546		if(QT_IS_EMPTY(qt))
547	<	return(qtadduelem(qt,t_id));
548	<
547	>	{
548	>	qt = qtadduelem(qt,s_id);
549	>	SM_S_NTH_QT(smMesh,s_id) = qt;
550	>	if(((S_ARGS *)argptr)->n_id)
551	>	*doneptr = FALSE;
552	>	else
553	>	*doneptr = TRUE;
554	>	return(qt);
555	>	}
556		/* If the set size is below expansion threshold,or at maximum
557		number of quadtree levels : just add */
558		optr = qtqueryset(qt);
559	<	if(QT_SET_CNT(optr) < QT_SET_THRESHOLD || (n >= QT_MAX_LEVELS))
560	<	return(qtadduelem(qt,t_id));
561	<	/* otherwise: expand node- and insert tri, and reinsert existing tris
559	>	if(QT_SET_CNT(optr) < QT_SET_THRESHOLD || (n > (QT_MAX_LEVELS-2)))
560	>	{
561	>	qt = qtadduelem(qt,s_id);
562	>
563	>	SM_S_NTH_QT(smMesh,s_id) = qt;
564	>	if(((S_ARGS *)argptr)->n_id)
565	>	if(QT_SET_CNT(qtqueryset(qt)) > 1)
566	>	{
567	>	((S_ARGS *)argptr)->n_id = qtqueryset(qt)[1];
568	>	*doneptr = TRUE;
569	>	}
570	>	else
571	>	*doneptr = FALSE;
572	>	else
573	>	*doneptr = TRUE;
574	>	return(qt);
575	>	}
576	>	/* otherwise: expand node- and insert sample, and reinsert existing samples
577		in set to children of new node
578		*/
579	<	/* First tri compressing set */
580	<	#ifdef NEWSETS0
581	<	if(qtcompressuelem(qt,compress_set) < QT_SET_THRESHOLD)
582	<	/* Get set: If greater than standard size: allocate memory to hold */
583	<	return(qtadduelem(qt,t_id));
584	<	#endif
585	<	if(QT_SET_CNT(optr) > QT_MAXSET)
586	<	{
587	<	if(!(tptr = (OBJECT *)malloc((QT_SET_CNT(optr)+1)*sizeof(OBJECT))))
588	<	goto memerr;
589	<	}
590	<	else
591	<	tptr = t_set;
592	<	qtgetset(tptr,qt);
579	>	{
580	>	OBJECT *sptr,s_set[QT_MAXSET+1];
581	>	FUNC sfunc;
582	>	S_ARGS args;
583	>	FVECT p;
584	>	BCOORD bp[3];
585	>	int i;
586	>
587	>	if(QT_SET_CNT(optr) > QT_MAXSET)
588	>	{
589	>	if(!(sptr = (OBJECT *)malloc((QT_SET_CNT(optr)+1)*sizeof(OBJECT))))
590	>	goto memerr;
591	>	}
592	>	else
593	>	sptr = s_set;
594
595	<	/* subdivide node */
596	<	qtfreeleaf(qt);
597	<	qtSubdivide(qt);
595	>	qtgetset(sptr,qt);
596	>
597	>	/* subdivide node */
598	>	qtfreeleaf(qt);
599	>	qtSubdivide(qt);
600	>
601	>	/* Now add in all of the rest; */
602	>	F_FUNC(sfunc) = F_FUNC(f);
603	>	F_ARGS(sfunc) = (int *) (&args);
604	>	args.n_id = 0;
605	>	for(optr = sptr,i=QT_SET_CNT(sptr); i > 0; i--)
606	>	{
607	>	s_id = QT_SET_NEXT_ELEM(optr);
608	>	args.s_id = s_id;
609	>	VSUB(p,SM_NTH_WV(smMesh,s_id),SM_VIEW_CENTER(smMesh));
610	>	normalize(p);
611	>	vert_to_qt_frame(i,p,bp);
612	>	if(rev)
613	>	qt= qtInsert_point_rev(root,qt,parent,q0,q1,q2,bp,
614	>	scale,sfunc,n,doneptr);
615	>	else
616	>	qt= qtInsert_point(root,qt,parent,q0,q1,q2,bp,
617	>	scale,sfunc,n,doneptr);
618	>	}
619	>	/* Add current sample: have all of the information */
620	>	if(rev)
621	>	qt =qtInsert_point_rev(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr);
622	>	else
623	>	qt = qtInsert_point(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr);
624	>
625	>	/* If we allocated memory: free it */
626
627	<	a = q1[0];  b = q0[1]; c = q0[2];
628	<	qa = q0[0]; qb = q1[1];  qc = q2[2];
597	<	/* First add current tri: have all of the information */
598	<	if(rev)
599	<	qt = qtInsert_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
600	<	s0,s1,s2,sq0,sq1,sq2,f,n);
601	<	else
602	<	qt = qtInsert_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
603	<	s0,s1,s2,sq0,sq1,sq2,f,n);
627	>	if( sptr != s_set)
628	>	free(sptr);
629
630	<	/* Now add in all of the rest; */
606	<	F_FUNC(tfunc) = F_FUNC(f);
607	<	for(optr = QT_SET_PTR(tptr),i=QT_SET_CNT(tptr); i > 0; i--)
608	<	{
609	<	t_id = QT_SET_NEXT_ELEM(optr);
610	<	t = SM_NTH_TRI(smMesh,t_id);
611	<	if(!T_IS_VALID(t))
612	<	continue;
613	<	F_ARGS(tfunc) = &t_id;
614	<	VSUB(tri[0],SM_T_NTH_WV(smMesh,t,0),SM_VIEW_CENTER(smMesh));
615	<	VSUB(tri[1],SM_T_NTH_WV(smMesh,t,1),SM_VIEW_CENTER(smMesh));
616	<	VSUB(tri[2],SM_T_NTH_WV(smMesh,t,2),SM_VIEW_CENTER(smMesh));
617	<	convert_tri_to_frame(root,tri,b0,b1,b2,db10,db21,db02);
618	<
619	<	/* Calculate appropriate sidedness values */
620	<	SIDES_GTR(b0,b1,b2,s0,s1,s2,a,b,c);
621	<	SIDES_GTR(b0,b1,b2,sq0,sq1,sq2,qa,qb,qc);
622	<	if(rev)
623	<	qt = qtInsert_tri_rev(root,qt,q0,q1,q2,b0,b1,b2,db10,db21,db02,scale,
624	<	s0,s1,s2,sq0,sq1,sq2,tfunc,n);
625	<	else
626	<	qt = qtInsert_tri(root,qt,q0,q1,q2,b0,b1,b2,db10,db21,db02,scale,
627	<	s0,s1,s2,sq0,sq1,sq2,tfunc,n);
630	>	return(qt);
631		}
629	–	/* If we allocated memory: free it */
630	–	if( tptr != t_set)
631	–	free(tptr);
632	–
633	–	return(qt);
632		memerr:
633		error(SYSTEM,"expand_node():Unable to allocate memory");
634
635		}
636
637
638	<
639	<	smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id)
640	<	SM *sm;
641	<	int t_id;
642	<	int v0_id,v1_id,v2_id;
643	<	{
644	<	FVECT tri[3];
645	<	FUNC f;
646	<
647	<	#ifdef DEBUG
648	<	if(T_NTH_NBR(SM_NTH_TRI(sm,t_id),0)== -1 ||
651	<	T_NTH_NBR(SM_NTH_TRI(sm,t_id),1)== -1 ||
652	<	T_NTH_NBR(SM_NTH_TRI(sm,t_id),2)== -1)
653	<	error("Invalid tri: smLocator_add_tri()\n");
654	<
655	<	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t_id),0))) ||
656	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t_id),1))) ||
657	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t_id),2))))
658	<	error("Invalid tri: smLocator_add_tri()\n");
659	<	#endif
660	<
661	<	VSUB(tri[0],SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm));
662	<	VSUB(tri[1],SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm));
663	<	VSUB(tri[2],SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm));
664	<
665	<	F_FUNC(f) = insert_tri;
666	<	F_ARGS(f) = &t_id;
667	<	stInsert_tri(SM_LOCATOR(sm),tri,f);
668	<	}
669	<
670	<	/* Add a triangle to the base array with vertices v1-v2-v3 */
638	>	/*
639	>	* int
640	>	* smAdd_tri(sm,v0_id,v1_id,v2_id,tptr)
641	>	*             : Add a triangle to the base array with vertices v0-v1-v2,
642	>	*               returns ptr to triangle in tptr
643	>	* SM *sm;                   : mesh
644	>	* S_ID v0_id,v1_id,v2_id;    : sample ids of triangle vertices
645	>	* TRI **tptr;               : ptr to set to triangle
646	>	*
647	>	*  Allocates and initializes mesh triangle with vertices specified.
648	>	*/
649		int
650	<	smAdd_tri(sm, v0_id,v1_id,v2_id)
650	>	smAdd_tri(sm, v0_id,v1_id,v2_id,tptr)
651		SM *sm;
652	<	int v0_id,v1_id,v2_id;
652	>	S_ID v0_id,v1_id,v2_id;
653	>	TRI **tptr;
654		{
655		int t_id;
656		TRI *t;
657	+
658		#ifdef DEBUG
659		if(v0_id==v1_id || v0_id==v2_id || v1_id==v2_id)
660		error(CONSISTENCY,"smAdd_tri: invalid vertex ids\n");
681	–	#endif
682	–	t_id = smAlloc_tri(sm);
661
662	<	if(t_id == -1)
663	<	return(t_id);
662	>	#endif
663	>	t_id = smAlloc_tri(sm);
664	>	#ifdef DEBUG
665	>	#if DEBUG > 1
666	>	{
667	>	double v0[3],v1[3],v2[3],n[3];
668	>	double area,dp;
669	>	double ab[3],ac[3];
670	>	VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm));
671	>	VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm));
672	>	VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm));
673	>	normalize(v0);
674	>	normalize(v1);
675	>	normalize(v2);
676
677	<	t = SM_NTH_TRI(sm,t_id);
677	>	VSUB(ab,v1,v2);
678	>	normalize(ab);
679	>	VSUB(ac,v0,v2);
680	>	normalize(ac);
681	>	VCROSS(n,ab,ac);
682	>	area = normalize(n);
683	>	if((dp=DOT(v0,n)) < 0.0)
684	>	{
685	>	eputs("backwards tri\n");
686	>	}
687	>	}
688	>	#endif
689	>	#endif
690
691	+	t = SM_NTH_TRI(sm,t_id);
692	+	#ifdef DEBUG
693		T_CLEAR_NBRS(t);
694	+	#endif
695		/* set the triangle vertex ids */
696		T_NTH_V(t,0) = v0_id;
697		T_NTH_V(t,1) = v1_id;
#	Line 697 | Line 702 | int v0_id,v1_id,v2_id;
702		SM_NTH_VERT(sm,v2_id) = t_id;
703
704		if(SM_BASE_ID(sm,v0_id) || SM_BASE_ID(sm,v1_id) || SM_BASE_ID(sm,v2_id))
700	–	{
701	–	smClear_tri_flags(sm,t_id);
705		SM_SET_NTH_T_BASE(sm,t_id);
703	–	}
706		else
705	–	{
707		SM_CLR_NTH_T_BASE(sm,t_id);
708	<	SM_SET_NTH_T_ACTIVE(sm,t_id);
709	<	SM_SET_NTH_T_NEW(sm,t_id);
710	<	S_SET_FLAG(T_NTH_V(t,0));
711	<	S_SET_FLAG(T_NTH_V(t,1));
712	<	S_SET_FLAG(T_NTH_V(t,2));
713	<	SM_SAMPLE_TRIS(sm)++;
714	<	smNew_tri_cnt++;
714	<	}
708	>	if(SM_DIR_ID(sm,v0_id) || SM_DIR_ID(sm,v1_id) || SM_DIR_ID(sm,v2_id))
709	>	SM_SET_NTH_T_BG(sm,t_id);
710	>	else
711	>	SM_CLR_NTH_T_BG(sm,t_id);
712	>	S_SET_FLAG(T_NTH_V(t,0));
713	>	S_SET_FLAG(T_NTH_V(t,1));
714	>	S_SET_FLAG(T_NTH_V(t,2));
715
716	+	SM_SET_NTH_T_ACTIVE(sm,t_id);
717	+	SM_SET_NTH_T_NEW(sm,t_id);
718	+
719	+	*tptr = t;
720		/* return initialized triangle */
721		return(t_id);
722		}
723
724
725	<	void
726	<	smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add_ptr)
727	<	SM *sm;
728	<	int t_id,t1_id;
729	<	int e,e1;
730	<	int *tn_id,*tn1_id;
727	<	LIST **add_ptr;
725	>
726	>	smRestore_Delaunay(sm,a,b,c,t,t_id,a_id,b_id,c_id)
727	>	SM *sm;
728	>	FVECT a,b,c;
729	>	TRI *t;
730	>	int t_id,a_id,b_id,c_id;
731		{
732	<	int verts[3],enext,eprev,e1next,e1prev;
733	<	TRI *n,*ta,*tb,*t,*t1;
734	<	FVECT p1,p2,p3;
735	<	int ta_id,tb_id;
733	<	/* form new diagonal (e relative to t, and e1 relative to t1)
734	<	defined by quadrilateral formed by t,t1- swap for the opposite diagonal
735	<	*/
736	<	enext = (e+1)%3;
737	<	eprev = (e+2)%3;
738	<	e1next = (e1+1)%3;
739	<	e1prev = (e1+2)%3;
740	<	verts[e] = T_NTH_V(SM_NTH_TRI(sm,t_id),e);
741	<	verts[enext] = T_NTH_V(SM_NTH_TRI(sm,t_id),enext);
742	<	verts[eprev] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1);
743	<	ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2]);
744	<	*add_ptr = push_data(*add_ptr,ta_id);
745	<	verts[e1] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1);
746	<	verts[e1next] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1next);
747	<	verts[e1prev] = T_NTH_V(SM_NTH_TRI(sm,t_id),e);
748	<	tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2]);
732	>	int e1,topp_id;
733	>	S_ID p_id;
734	>	TRI *topp;
735	>	FVECT p;
736
737	<	*add_ptr = push_data(*add_ptr,tb_id);
751	<	ta = SM_NTH_TRI(sm,ta_id);
752	<	tb = SM_NTH_TRI(sm,tb_id);
753	<	t = SM_NTH_TRI(sm,t_id);
754	<	t1 = SM_NTH_TRI(sm,t1_id);
755	<	/* set the neighbors */
756	<	T_NTH_NBR(ta,e) = T_NTH_NBR(t1,e1next);
757	<	T_NTH_NBR(tb,e1) = T_NTH_NBR(t,enext);
758	<	T_NTH_NBR(ta,enext)= tb_id;
759	<	T_NTH_NBR(tb,e1next)= ta_id;
760	<	T_NTH_NBR(ta,eprev)=T_NTH_NBR(t,eprev);
761	<	T_NTH_NBR(tb,e1prev)=T_NTH_NBR(t1,e1prev);
762	<
763	<
737	>	topp_id = T_NTH_NBR(t,0);
738		#ifdef DEBUG
739	<	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,0))) ||
740	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,1))) ||
741	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,2))) ||
742	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,0))) ||
743	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,1))) ||
770	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,2))))
771	<	goto Ltri_error;
772	<	if(SM_NTH_TRI(sm,T_NTH_NBR(ta,0))==SM_NTH_TRI(sm,T_NTH_NBR(ta,1)) ||
773	<	SM_NTH_TRI(sm,T_NTH_NBR(ta,0))==SM_NTH_TRI(sm,T_NTH_NBR(ta,2)) ||
774	<	SM_NTH_TRI(sm,T_NTH_NBR(ta,1))==SM_NTH_TRI(sm,T_NTH_NBR(ta,2)) ||
775	<	SM_NTH_TRI(sm,T_NTH_NBR(tb,0))==SM_NTH_TRI(sm,T_NTH_NBR(tb,1)) ||
776	<	SM_NTH_TRI(sm,T_NTH_NBR(tb,0))==SM_NTH_TRI(sm,T_NTH_NBR(tb,2)) ||
777	<	SM_NTH_TRI(sm,T_NTH_NBR(tb,1))==SM_NTH_TRI(sm,T_NTH_NBR(tb,2)) )
778	<	goto Ltri_error;
739	>	if(topp_id==INVALID)
740	>	{
741	>	eputs("Invalid tri id smRestore_delaunay()\n");
742	>	return;
743	>	}
744		#endif
745	<	/* Reset neighbor pointers of original neighbors */
781	<	n = SM_NTH_TRI(sm,T_NTH_NBR(t,enext));
745	>	topp = SM_NTH_TRI(sm,topp_id);
746		#ifdef DEBUG
747	<	if(!T_IS_VALID(n))
748	<	goto Ltri_error;
747	>	if(!T_IS_VALID(topp))
748	>	{
749	>	eputs("Invalid tri smRestore_delaunay()\n");
750	>	return;
751	>	}
752		#endif
753	+	e1 = T_NTH_NBR_PTR(t_id,topp);
754	+	p_id = T_NTH_V(topp,e1);
755	+
756	+	VSUB(p,SM_NTH_WV(sm,p_id),SM_VIEW_CENTER(sm));
757	+	normalize(p);
758	+	if(pt_in_cone(p,c,b,a))
759	+	{
760	+	int e1next,e1prev;
761	+	int ta_id,tb_id;
762	+	TRI *ta,*tb,*n;
763	+	e1next = (e1 + 1)%3;
764	+	e1prev = (e1 + 2)%3;
765	+	ta_id = smAdd_tri(sm,a_id,b_id,p_id,&ta);
766	+	tb_id = smAdd_tri(sm,a_id,p_id,c_id,&tb);
767	+
768	+	T_NTH_NBR(ta,0) = T_NTH_NBR(topp,e1next);
769	+	T_NTH_NBR(ta,1) = tb_id;
770	+	T_NTH_NBR(ta,2) = T_NTH_NBR(t,2);
771	+
772	+	T_NTH_NBR(tb,0) = T_NTH_NBR(topp,e1prev);
773	+	T_NTH_NBR(tb,1) = T_NTH_NBR(t,1);
774	+	T_NTH_NBR(tb,2) = ta_id;
775	+
776	+	n = SM_NTH_TRI(sm,T_NTH_NBR(t,1));
777		T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = tb_id;
778	<	n = SM_NTH_TRI(sm,T_NTH_NBR(t,eprev));
788	<	#ifdef DEBUG
789	<	if(!T_IS_VALID(n))
790	<	goto Ltri_error;
791	<	#endif
778	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t,2));
779		T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = ta_id;
780	+	n = SM_NTH_TRI(sm,T_NTH_NBR(topp,e1next));
781	+	T_NTH_NBR(n,T_NTH_NBR_PTR(topp_id,n)) = ta_id;
782	+	n = SM_NTH_TRI(sm,T_NTH_NBR(topp,e1prev));
783	+	T_NTH_NBR(n,T_NTH_NBR_PTR(topp_id,n)) = tb_id;
784	+
785	+	smDelete_tri(sm,t_id,t);
786	+	smDelete_tri(sm,topp_id,topp);
787
794	–	n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1next));
788		#ifdef DEBUG
789	<	if(!T_IS_VALID(n))
790	<	goto Ltri_error;
791	<	#endif
792	<	T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = ta_id;
793	<	n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1prev));
794	<	#ifdef DEBUG
795	<	if(!T_IS_VALID(n))
796	<	goto Ltri_error;
797	<	#endif
798	<	T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = tb_id;
789	>	#if DEBUG > 1
790	>	if(T_NTH_NBR(ta,0) == T_NTH_NBR(ta,1)  ||
791	>	T_NTH_NBR(ta,1) == T_NTH_NBR(ta,2)  ||
792	>	T_NTH_NBR(ta,0) == T_NTH_NBR(ta,2))
793	>	error(CONSISTENCY,"Invalid topology\n");
794	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,0))) ||
795	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,1))) ||
796	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,2))))
797	>	error(CONSISTENCY,"Invalid topology\n");
798	>	n = SM_NTH_TRI(sm,T_NTH_NBR(ta,0));
799	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
800	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
801	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
802	>	error(CONSISTENCY,"Invalid topology\n");
803	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
804	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
805	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
806	>	error(CONSISTENCY,"Invalid topology\n");
807	>	n = SM_NTH_TRI(sm,T_NTH_NBR(ta,1));
808	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
809	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
810	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
811	>	error(CONSISTENCY,"Invalid topology\n");
812	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
813	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
814	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
815	>	error(CONSISTENCY,"Invalid topology\n");
816	>	n = SM_NTH_TRI(sm,T_NTH_NBR(ta,2));
817	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
818	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
819	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
820	>	error(CONSISTENCY,"Invalid topology\n");
821	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
822	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
823	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
824	>	error(CONSISTENCY,"Invalid topology\n");
825	>	n = SM_NTH_TRI(sm,T_NTH_NBR(tb,0));
826	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
827	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
828	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
829	>	error(CONSISTENCY,"Invalid topology\n");
830	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
831	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
832	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
833	>	error(CONSISTENCY,"Invalid topology\n");
834	>	n = SM_NTH_TRI(sm,T_NTH_NBR(tb,1));
835	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
836	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
837	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
838	>	error(CONSISTENCY,"Invalid topology\n");
839	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
840	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
841	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
842	>	error(CONSISTENCY,"Invalid topology\n");
843	>	n = SM_NTH_TRI(sm,T_NTH_NBR(tb,2));
844	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
845	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
846	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
847	>	error(CONSISTENCY,"Invalid topology\n");
848	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
849	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
850	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
851	>	error(CONSISTENCY,"Invalid topology\n");
852
853	<	#ifdef DEBUG
854	<	T_VALID_FLAG(SM_NTH_TRI(sm,t_id))=-1;
855	<	T_VALID_FLAG(SM_NTH_TRI(sm,t1_id))=-1;
856	<	#endif
853	>	if(T_NTH_NBR(tb,0) == T_NTH_NBR(tb,1)  ||
854	>	T_NTH_NBR(tb,1) == T_NTH_NBR(tb,2)  ||
855	>	T_NTH_NBR(tb,0) == T_NTH_NBR(tb,2))
856	>	error(CONSISTENCY,"Invalid topology\n");
857	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,0))) ||
858	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,1))) ||
859	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,2))))
860	>	error(CONSISTENCY,"Invalid topology\n");
861
862	<	remove_from_list(t_id,add_ptr);
863	<	remove_from_list(t1_id,add_ptr);
864	<	#if 1
865	<	smDelete_tri(sm,t_id);
816	<	smDelete_tri(sm,t1_id);
817	<	#else
818	<	*del_ptr = push_data(*del_ptr,t_id);
819	<	*del_ptr = push_data(*del_ptr,t1_id);
820	<	#endif
821	<
822	<
823	<
824	<	*tn_id = ta_id;
825	<	*tn1_id = tb_id;
826	<
827	<	#ifdef DEBUG
828	<	if(T_NTH_NBR(SM_NTH_TRI(sm,ta_id),0)== -1 ||
829	<	T_NTH_NBR(SM_NTH_TRI(sm,ta_id),1)== -1 ||
830	<	T_NTH_NBR(SM_NTH_TRI(sm,ta_id),2)== -1 ||
831	<	T_NTH_NBR(SM_NTH_TRI(sm,tb_id),0)== -1 ||
832	<	T_NTH_NBR(SM_NTH_TRI(sm,tb_id),1)== -1 ||
833	<	T_NTH_NBR(SM_NTH_TRI(sm,tb_id),2)== -1)
834	<	goto Ltri_error;
835	<	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,ta_id),0))) ||
836	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,ta_id),1))) ||
837	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,ta_id),2))))
838	<	goto Ltri_error;
839	<	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tb_id),0))) ||
840	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tb_id),1))) ||
841	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tb_id),2))))
842	<	goto Ltri_error;
843	<	#endif
844	<	return;
845	<	Ltri_error:
846	<	error(CONSISTENCY,"Invalid tri: smTris_swap_edge()\n");
847	<	}
848	<
849	<	smUpdate_locator(sm,add_list)
850	<	SM *sm;
851	<	LIST *add_list;
852	<	{
853	<	int t_id,i;
854	<	TRI *t;
855	<	OBJECT *optr;
856	<
857	<	while(add_list)
858	<	{
859	<	t_id = pop_list(&add_list);
860	<	t = SM_NTH_TRI(sm,t_id);
861	<	smLocator_add_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2));
862	>	#endif
863	>	#endif
864	>	smRestore_Delaunay(sm,a,b,p,ta,ta_id,a_id,b_id,p_id);
865	>	smRestore_Delaunay(sm,a,p,c,tb,tb_id,a_id,p_id,c_id);
866		}
867		}
868
865	–	int
866	–	smFix_tris(sm,id,tlist,add_list)
867	–	SM *sm;
868	–	int id;
869	–	LIST *tlist,*add_list;
870	–	{
871	–	TRI *t,*t_opp;
872	–	FVECT p,p0,p1,p2;
873	–	int e,e1,swapped = 0;
874	–	int t_id,t_opp_id;
875	–	LIST *del_list=NULL;
869
877	–	VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
878	–	while(tlist)
879	–	{
880	–	t_id = pop_list(&tlist);
881	–	#ifdef DEBUG
882	–	if(t_id==INVALID || t_id > smMesh->num_tri)
883	–	error(CONSISTENCY,"Invalid tri id smFix_tris()\n");
884	–	#endif
885	–	t = SM_NTH_TRI(sm,t_id);
886	–	e = T_WHICH_V(t,id);
887	–	t_opp_id = T_NTH_NBR(t,e);
888	–	#ifdef DEBUG
889	–	if(t_opp_id==INVALID || t_opp_id > smMesh->num_tri)
890	–	error(CONSISTENCY,"Invalid tri id smFix_tris()\n");
891	–	#endif
892	–	t_opp = SM_NTH_TRI(sm,t_opp_id);
893	–	#ifdef DEBUG
894	–	if(!T_IS_VALID(t_opp))
895	–	error(CONSISTENCY,"Invalid trismFix_tris()\n");
896	–	#endif
897	–	smDir_in_cone(sm,p0,T_NTH_V(t_opp,0));
898	–	smDir_in_cone(sm,p1,T_NTH_V(t_opp,1));
899	–	smDir_in_cone(sm,p2,T_NTH_V(t_opp,2));
900	–	if(point_in_cone(p,p0,p1,p2))
901	–	{
902	–	swapped = 1;
903	–	e1 = T_NTH_NBR_PTR(t_id,t_opp);
904	–	/* check list for t_opp and Remove if there */
905	–	remove_from_list(t_opp_id,&tlist);
906	–	smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id,
907	–	&add_list);
908	–	tlist = push_data(tlist,t_id);
909	–	tlist = push_data(tlist,t_opp_id);
910	–	}
911	–	}
912	–	#if 0
913	–	while(del_list)
914	–	{
915	–	t_id = pop_list(&del_list);
916	–	smDelete_tri(sm,t_id);
917	–	}
918	–	#endif
919	–	smUpdate_locator(sm,add_list);
920	–
921	–	return(swapped);
922	–	}
923	–
870		/* Give the vertex "id" and a triangle "t" that it belongs to- return the
871		next nbr in a counter clockwise order about vertex "id"
872		*/
#	Line 928 | Line 874 | int
874		smTri_next_ccw_nbr(sm,t,id)
875		SM *sm;
876		TRI *t;
877	<	int id;
877	>	S_ID id;
878		{
879		int which;
880		int nbr_id;
#	Line 955 | Line 901 | int id;
901
902		/* Locate the point-id in the point location structure: */
903		int
904	<	smInsert_samp(sm,s_id,tri_id,on,which)
904	>	smInsert_samp_mesh(sm,s_id,tri_id,a,b,c,d,on,which)
905		SM *sm;
906	<	int s_id,tri_id;
906	>	S_ID s_id;
907	>	int tri_id;
908	>	FVECT a,b,c,d;
909		int on,which;
910		{
911	<	int v_id[3],topp_id,i;
912	<	int t0_id,t1_id,t2_id,t3_id,replaced;
913	<	int e0,e1,e2,opp0,opp1,opp2,opp_id;
914	<	LIST *tlist,*add_list;
915	<	FVECT npt;
916	<	TRI *tri,*nbr,*topp;
911	>	S_ID v_id[3],opp_id;
912	>	int topp_id,i;
913	>	int t0_id,t1_id,t2_id,t3_id;
914	>	int e0,e1,e2,opp0,opp1,opp2;
915	>	TRI *tri,*nbr,*topp,*t0,*t1,*t2,*t3;
916	>	FVECT e;
917
970	–
971	–	add_list = NULL;
918		for(i=0; i<3;i++)
919		v_id[i] = T_NTH_V(SM_NTH_TRI(sm,tri_id),i);
920
921		/* If falls on existing edge */
922		if(on == ON_E)
923		{
924	+	FVECT n,vopp;
925	+	double dp;
926	+
927		tri = SM_NTH_TRI(sm,tri_id);
928		topp_id = T_NTH_NBR(tri,which);
929		e0 = which;
#	Line 982 | Line 931 | smInsert_samp(sm,s_id,tri_id,on,which)
931		e2 = (which+2)%3;
932		topp = SM_NTH_TRI(sm,topp_id);
933		opp0 = T_NTH_NBR_PTR(tri_id,topp);
985	–	opp_id = T_NTH_V(topp,opp0);
934		opp1 = (opp0+1)%3;
935		opp2 = (opp0+2)%3;
936	+
937	+	opp_id = T_NTH_V(topp,opp0);
938
939		/* Create 4 triangles */
940		/*      /|\             /|\
#	Line 994 | Line 944 | smInsert_samp(sm,s_id,tri_id,on,which)
944		\ | /           \ | /
945		\|/             \|/
946		*/
947	<	t0_id = smAdd_tri(sm,s_id,v_id[e0],v_id[e1]);
948	<	add_list = push_data(add_list,t0_id);
949	<	t1_id = smAdd_tri(sm,s_id,v_id[e2],v_id[e0]);
950	<	add_list = push_data(add_list,t1_id);
1001	<	t2_id = smAdd_tri(sm,s_id,v_id[e1],opp_id);
1002	<	add_list = push_data(add_list,t2_id);
1003	<	t3_id = smAdd_tri(sm,s_id,opp_id,v_id[e2]);
1004	<	add_list = push_data(add_list,t3_id);
1005	<	/* CAUTION: tri must be assigned after Add_tri: pointers may change*/
1006	<	tri = SM_NTH_TRI(sm,tri_id);
1007	<	topp =SM_NTH_TRI(sm,topp_id);
947	>	t0_id = smAdd_tri(sm,s_id,v_id[e0],v_id[e1],&t0);
948	>	t1_id = smAdd_tri(sm,s_id,v_id[e2],v_id[e0],&t1);
949	>	t2_id = smAdd_tri(sm,s_id,v_id[e1],opp_id,&t2);
950	>	t3_id = smAdd_tri(sm,s_id,opp_id,v_id[e2],&t3);
951
952	<	/* Set the neighbor pointers for the new tris */
953	<	T_NTH_NBR(SM_NTH_TRI(sm,t0_id),0) = T_NTH_NBR(tri,e2);
954	<	T_NTH_NBR(SM_NTH_TRI(sm,t0_id),1) = t2_id;
955	<	T_NTH_NBR(SM_NTH_TRI(sm,t0_id),2) = t1_id;
956	<	T_NTH_NBR(SM_NTH_TRI(sm,t1_id),0) = T_NTH_NBR(tri,e1);
957	<	T_NTH_NBR(SM_NTH_TRI(sm,t1_id),1) = t0_id;
958	<	T_NTH_NBR(SM_NTH_TRI(sm,t1_id),2) = t3_id;
959	<	T_NTH_NBR(SM_NTH_TRI(sm,t2_id),0) = T_NTH_NBR(topp,opp1);
960	<	T_NTH_NBR(SM_NTH_TRI(sm,t2_id),1) = t3_id;
961	<	T_NTH_NBR(SM_NTH_TRI(sm,t2_id),2) = t0_id;
962	<	T_NTH_NBR(SM_NTH_TRI(sm,t3_id),0) = T_NTH_NBR(topp,opp2);
963	<	T_NTH_NBR(SM_NTH_TRI(sm,t3_id),1) = t1_id;
964	<	T_NTH_NBR(SM_NTH_TRI(sm,t3_id),2) = t2_id;
952	>	/* Set the neighbor pointers for the new tris */
953	>	T_NTH_NBR(t0,0) = T_NTH_NBR(tri,e2);
954	>	T_NTH_NBR(t0,1) = t2_id;
955	>	T_NTH_NBR(t0,2) = t1_id;
956	>	T_NTH_NBR(t1,0) = T_NTH_NBR(tri,e1);
957	>	T_NTH_NBR(t1,1) = t0_id;
958	>	T_NTH_NBR(t1,2) = t3_id;
959	>	T_NTH_NBR(t2,0) = T_NTH_NBR(topp,opp1);
960	>	T_NTH_NBR(t2,1) = t3_id;
961	>	T_NTH_NBR(t2,2) = t0_id;
962	>	T_NTH_NBR(t3,0) = T_NTH_NBR(topp,opp2);
963	>	T_NTH_NBR(t3,1) = t1_id;
964	>	T_NTH_NBR(t3,2) = t2_id;
965
966		/* Reset the neigbor pointers for the neighbors of the original */
967		nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,e1));
#	Line 1029 | Line 972 | smInsert_samp(sm,s_id,tri_id,on,which)
972		T_NTH_NBR(nbr,T_NTH_NBR_PTR(topp_id,nbr)) = t2_id;
973		nbr = SM_NTH_TRI(sm,T_NTH_NBR(topp,opp2));
974		T_NTH_NBR(nbr,T_NTH_NBR_PTR(topp_id,nbr)) = t3_id;
975	+
976		#ifdef DEBUG
977	<	T_VALID_FLAG(SM_NTH_TRI(sm,tri_id))=-1;
978	<	T_VALID_FLAG(SM_NTH_TRI(sm,topp_id))=-1;
979	<	#endif
980	<	tlist = push_data(NULL,t0_id);
981	<	tlist = push_data(tlist,t1_id);
982	<	tlist = push_data(tlist,t2_id);
983	<	tlist = push_data(tlist,t3_id);
977	>	#if DEBUG > 1
978	>	{
979	>	TRI *n;
980	>
981	>	if(T_NTH_NBR(t0,0) == T_NTH_NBR(t0,1)  ||
982	>	T_NTH_NBR(t0,1) == T_NTH_NBR(t0,2)  ||
983	>	T_NTH_NBR(t0,0) == T_NTH_NBR(t0,2))
984	>	error(CONSISTENCY,"Invalid topology\n");
985	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,0))) ||
986	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,1))) ||
987	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,2))))
988	>	error(CONSISTENCY,"Invalid topology\n");
989	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t0,0));
990	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
991	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
992	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
993	>	error(CONSISTENCY,"Invalid topology\n");
994	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
995	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
996	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
997	>	error(CONSISTENCY,"Invalid topology\n");
998	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t0,1));
999	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1000	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1001	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1002	>	error(CONSISTENCY,"Invalid topology\n");
1003	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1004	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1005	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1006	>	error(CONSISTENCY,"Invalid topology\n");
1007	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t0,2));
1008	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1009	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1010	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1011	>	error(CONSISTENCY,"Invalid topology\n");
1012	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1013	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1014	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1015	>	error(CONSISTENCY,"Invalid topology\n");
1016	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t1,0));
1017	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1018	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1019	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1020	>	error(CONSISTENCY,"Invalid topology\n");
1021	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1022	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1023	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1024	>	error(CONSISTENCY,"Invalid topology\n");
1025	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t1,1));
1026	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1027	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1028	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1029	>	error(CONSISTENCY,"Invalid topology\n");
1030	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1031	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1032	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1033	>	error(CONSISTENCY,"Invalid topology\n");
1034	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t1,2));
1035	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1036	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1037	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1038	>	error(CONSISTENCY,"Invalid topology\n");
1039	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1040	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1041	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1042	>	error(CONSISTENCY,"Invalid topology\n");
1043	>
1044	>	if(T_NTH_NBR(t1,0) == T_NTH_NBR(t1,1)  ||
1045	>	T_NTH_NBR(t1,1) == T_NTH_NBR(t1,2)  ||
1046	>	T_NTH_NBR(t1,0) == T_NTH_NBR(t1,2))
1047	>	error(CONSISTENCY,"Invalid topology\n");
1048	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,0))) ||
1049	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,1))) ||
1050	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,2))))
1051	>	error(CONSISTENCY,"Invalid topology\n");
1052	>
1053	>	if(T_NTH_NBR(t2,0) == T_NTH_NBR(t2,1)  ||
1054	>	T_NTH_NBR(t2,1) == T_NTH_NBR(t2,2)  ||
1055	>	T_NTH_NBR(t2,0) == T_NTH_NBR(t2,2))
1056	>	error(CONSISTENCY,"Invalid topology\n");
1057	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t2,0))) ||
1058	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t2,1))) ||
1059	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t2,2))))
1060	>	error(CONSISTENCY,"Invalid topology\n");
1061	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t2,0));
1062	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1063	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1064	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1065	>	error(CONSISTENCY,"Invalid topology\n");
1066	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1067	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1068	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1069	>	error(CONSISTENCY,"Invalid topology\n");
1070	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t2,1));
1071	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1072	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1073	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1074	>	error(CONSISTENCY,"Invalid topology\n");
1075	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1076	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1077	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1078	>	error(CONSISTENCY,"Invalid topology\n");
1079	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t2,2));
1080	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1081	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1082	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1083	>	error(CONSISTENCY,"Invalid topology\n");
1084	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1085	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1086	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1087	>	error(CONSISTENCY,"Invalid topology\n");
1088	>
1089	>	if(T_NTH_NBR(t3,0) == T_NTH_NBR(t3,1)  ||
1090	>	T_NTH_NBR(t3,1) == T_NTH_NBR(t3,2)  ||
1091	>	T_NTH_NBR(t3,0) == T_NTH_NBR(t3,2))
1092	>	error(CONSISTENCY,"Invalid topology\n");
1093	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t3,0))) ||
1094	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t3,1))) ||
1095	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t3,2))))
1096	>	error(CONSISTENCY,"Invalid topology\n");
1097	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t3,0));
1098	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1099	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1100	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1101	>	error(CONSISTENCY,"Invalid topology\n");
1102	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1103	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1104	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1105	>	error(CONSISTENCY,"Invalid topology\n");
1106	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t3,1));
1107	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1108	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1109	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1110	>	error(CONSISTENCY,"Invalid topology\n");
1111	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1112	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1113	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1114	>	error(CONSISTENCY,"Invalid topology\n");
1115	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t3,2));
1116	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1117	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1118	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1119	>	error(CONSISTENCY,"Invalid topology\n");
1120	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1121	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1122	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1123	>	error(CONSISTENCY,"Invalid topology\n");
1124	>	}
1125	>	#endif
1126	>	#endif
1127	>	smDir(sm,e,opp_id);
1128	>	if(which == 0)
1129	>	{
1130	>	smRestore_Delaunay(sm,a,b,c,t0,t0_id,s_id,v_id[e0],v_id[e1]);
1131	>	smRestore_Delaunay(sm,a,d,b,t1,t1_id,s_id,v_id[e2],v_id[e0]);
1132	>	smRestore_Delaunay(sm,a,c,e,t2,t2_id,s_id,v_id[e1],opp_id);
1133	>	smRestore_Delaunay(sm,a,e,d,t3,t3_id,s_id,opp_id,v_id[e2]);
1134	>	}
1135	>	else
1136	>	if( which==1 )
1137	>	{
1138	>	smRestore_Delaunay(sm,a,c,d,t0,t0_id,s_id,v_id[e0],v_id[e1]);
1139	>	smRestore_Delaunay(sm,a,b,c,t1,t1_id,s_id,v_id[e2],v_id[e0]);
1140	>	smRestore_Delaunay(sm,a,d,e,t2,t2_id,s_id,v_id[e1],opp_id);
1141	>	smRestore_Delaunay(sm,a,e,b,t3,t3_id,s_id,opp_id,v_id[e2]);
1142	>	}
1143	>	else
1144	>	{
1145	>	smRestore_Delaunay(sm,a,d,b,t0,t0_id,s_id,v_id[e0],v_id[e1]);
1146	>	smRestore_Delaunay(sm,a,c,d,t1,t1_id,s_id,v_id[e2],v_id[e0]);
1147	>	smRestore_Delaunay(sm,a,b,e,t2,t2_id,s_id,v_id[e1],opp_id);
1148	>	smRestore_Delaunay(sm,a,e,c,t3,t3_id,s_id,opp_id,v_id[e2]);
1149	>	}
1150	>	smDelete_tri(sm,tri_id,tri);
1151	>	smDelete_tri(sm,topp_id,topp);
1152	>	return(TRUE);
1153		}
1154	<	else
1155	<	{
1156	<	/* Create 3 triangles */
1157	<	/*      / \             /|\
1158	<	/   \           / | \
1159	<	/  *  \  ---->  /  |  \
1160	<	/       \       /  / \  \
1161	<	/         \     / /     \ \
1162	<	/___________\   //_________\\
1163	<	*/
1154	>	Linsert_in_tri:
1155	>	/* Create 3 triangles */
1156	>	/*      / \             /|\
1157	>	/   \           / | \
1158	>	/  *  \  ---->  /  |  \
1159	>	/       \       /  / \  \
1160	>	/         \       / /     \ \
1161	>	___________\   //_________\\
1162	>	*/
1163	>	tri = SM_NTH_TRI(sm,tri_id);
1164
1165	<	t0_id = smAdd_tri(sm,s_id,v_id[0],v_id[1]);
1166	<	add_list = push_data(add_list,t0_id);
1167	<	t1_id = smAdd_tri(sm,s_id,v_id[1],v_id[2]);
1055	<	add_list = push_data(add_list,t1_id);
1056	<	t2_id = smAdd_tri(sm,s_id,v_id[2],v_id[0]);
1057	<	add_list = push_data(add_list,t2_id);
1165	>	t0_id = smAdd_tri(sm,s_id,v_id[0],v_id[1],&t0);
1166	>	t1_id = smAdd_tri(sm,s_id,v_id[1],v_id[2],&t1);
1167	>	t2_id = smAdd_tri(sm,s_id,v_id[2],v_id[0],&t2);
1168
1169	<	/* CAUTION: tri must be assigned after Add_tri: pointers may change*/
1170	<	tri = SM_NTH_TRI(sm,tri_id);
1171	<	/* Set the neighbor pointers for the new tris */
1172	<	T_NTH_NBR(SM_NTH_TRI(sm,t0_id),0) = T_NTH_NBR(tri,2);
1173	<	T_NTH_NBR(SM_NTH_TRI(sm,t0_id),1) = t1_id;
1174	<	T_NTH_NBR(SM_NTH_TRI(sm,t0_id),2) = t2_id;
1175	<	T_NTH_NBR(SM_NTH_TRI(sm,t1_id),0) = T_NTH_NBR(tri,0);
1176	<	T_NTH_NBR(SM_NTH_TRI(sm,t1_id),1) = t2_id;
1177	<	T_NTH_NBR(SM_NTH_TRI(sm,t1_id),2) = t0_id;
1178	<	T_NTH_NBR(SM_NTH_TRI(sm,t2_id),0) = T_NTH_NBR(tri,1);
1069	<	T_NTH_NBR(SM_NTH_TRI(sm,t2_id),1) = t0_id;
1070	<	T_NTH_NBR(SM_NTH_TRI(sm,t2_id),2) = t1_id;
1169	>	/* Set the neighbor pointers for the new tris */
1170	>	T_NTH_NBR(t0,0) = T_NTH_NBR(tri,2);
1171	>	T_NTH_NBR(t0,1) = t1_id;
1172	>	T_NTH_NBR(t0,2) = t2_id;
1173	>	T_NTH_NBR(t1,0) = T_NTH_NBR(tri,0);
1174	>	T_NTH_NBR(t1,1) = t2_id;
1175	>	T_NTH_NBR(t1,2) = t0_id;
1176	>	T_NTH_NBR(t2,0) = T_NTH_NBR(tri,1);
1177	>	T_NTH_NBR(t2,1) = t0_id;
1178	>	T_NTH_NBR(t2,2) = t1_id;
1179
1180	<	/* Reset the neigbor pointers for the neighbors of the original */
1181	<	nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,0));
1182	<	T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t1_id;
1183	<	nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,1));
1184	<	T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t2_id;
1185	<	nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,2));
1186	<	T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t0_id;
1180	>	/* Reset the neigbor pointers for the neighbors of the original */
1181	>	nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,0));
1182	>	T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t1_id;
1183	>	nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,1));
1184	>	T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t2_id;
1185	>	nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,2));
1186	>	T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t0_id;
1187	>	#ifdef DEBUG
1188	>	#if DEBUG > 1
1189	>	{
1190	>	TRI *n;
1191	>	if(T_NTH_NBR(t0,0) == T_NTH_NBR(t0,1)  ||
1192	>	T_NTH_NBR(t0,1) == T_NTH_NBR(t0,2)  ||
1193	>	T_NTH_NBR(t0,0) == T_NTH_NBR(t0,2))
1194	>	error(CONSISTENCY,"Invalid topology\n");
1195	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,0))) ||
1196	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,1))) ||
1197	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,2))))
1198	>	error(CONSISTENCY,"Invalid topology\n");
1199	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t0,0));
1200	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1201	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1202	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1203	>	error(CONSISTENCY,"Invalid topology\n");
1204	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1205	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1206	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1207	>	error(CONSISTENCY,"Invalid topology\n");
1208	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t0,1));
1209	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1210	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1211	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1212	>	error(CONSISTENCY,"Invalid topology\n");
1213	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1214	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1215	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1216	>	error(CONSISTENCY,"Invalid topology\n");
1217	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t0,2));
1218	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1219	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1220	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1221	>	error(CONSISTENCY,"Invalid topology\n");
1222	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1223	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1224	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1225	>	error(CONSISTENCY,"Invalid topology\n");
1226	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t1,0));
1227	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1228	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1229	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1230	>	error(CONSISTENCY,"Invalid topology\n");
1231	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1232	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1233	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1234	>	error(CONSISTENCY,"Invalid topology\n");
1235	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t1,1));
1236	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1237	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1238	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1239	>	error(CONSISTENCY,"Invalid topology\n");
1240	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1241	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1242	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1243	>	error(CONSISTENCY,"Invalid topology\n");
1244	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t1,2));
1245	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1246	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1247	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1248	>	error(CONSISTENCY,"Invalid topology\n");
1249	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1250	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1251	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1252	>	error(CONSISTENCY,"Invalid topology\n");
1253
1254	<	tlist = push_data(NULL,t0_id);
1255	<	tlist = push_data(tlist,t1_id);
1256	<	tlist = push_data(tlist,t2_id);
1257	<	}
1258	<	/* Fix up the new triangles*/
1259	<	smFix_tris(sm,s_id,tlist,add_list);
1254	>	if(T_NTH_NBR(t1,0) == T_NTH_NBR(t1,1)  ||
1255	>	T_NTH_NBR(t1,1) == T_NTH_NBR(t1,2)  ||
1256	>	T_NTH_NBR(t1,0) == T_NTH_NBR(t1,2))
1257	>	error(CONSISTENCY,"Invalid topology\n");
1258	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,0))) ||
1259	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,1))) ||
1260	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,2))))
1261	>	error(CONSISTENCY,"Invalid topology\n");
1262
1263	<	smDelete_tri(sm,tri_id);
1264	<	if(on==ON_E)
1265	<	smDelete_tri(sm,topp_id);
1263	>	if(T_NTH_NBR(t2,0) == T_NTH_NBR(t2,1)  ||
1264	>	T_NTH_NBR(t2,1) == T_NTH_NBR(t2,2)  ||
1265	>	T_NTH_NBR(t2,0) == T_NTH_NBR(t2,2))
1266	>	error(CONSISTENCY,"Invalid topology\n");
1267	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t2,0))) ||
1268	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t2,1))) ||
1269	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t2,2))))
1270	>	error(CONSISTENCY,"Invalid topology\n");
1271	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t2,0));
1272	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1273	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1274	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1275	>	error(CONSISTENCY,"Invalid topology\n");
1276	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1277	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1278	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1279	>	error(CONSISTENCY,"Invalid topology\n");
1280	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t2,1));
1281	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1282	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1283	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1284	>	error(CONSISTENCY,"Invalid topology\n");
1285	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1286	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1287	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1288	>	error(CONSISTENCY,"Invalid topology\n");
1289	>	n = SM_NTH_TRI(sm,T_NTH_NBR(t2,2));
1290	>	if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
1291	>	T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
1292	>	T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
1293	>	error(CONSISTENCY,"Invalid topology\n");
1294	>	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
1295	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
1296	>	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
1297	>	error(CONSISTENCY,"Invalid topology\n");
1298	>	}
1299	>	#endif
1300	>	#endif
1301	>	smRestore_Delaunay(sm,a,b,c,t0,t0_id,s_id,v_id[0],v_id[1]);
1302	>	smRestore_Delaunay(sm,a,c,d,t1,t1_id,s_id,v_id[1],v_id[2]);
1303	>	smRestore_Delaunay(sm,a,d,b,t2,t2_id,s_id,v_id[2],v_id[0]);
1304	>	smDelete_tri(sm,tri_id,tri);
1305	>	return(TRUE);
1306
1091	–	return(TRUE);
1092	–
1307		#ifdef DEBUG
1308		Ladderror:
1309	<	error(CONSISTENCY,"Invalid tri: smInsert_samp()\n");
1309	>	error(CONSISTENCY,"Invalid tri: smInsert_samp_mesh()\n");
1310		#endif
1311		}
1312
1313	+
1314		int
1315	<	smTri_in_set(sm,p,optr,onptr,whichptr)
1315	>	smWalk(sm,p,t_id,t,onptr,wptr,from,on_edge,a,b)
1316		SM *sm;
1317		FVECT p;
1318	<	OBJECT *optr;
1319	<	int *onptr,*whichptr;
1318	>	int t_id;
1319	>	TRI *t;
1320	>	int *onptr,*wptr;
1321	>	int from;
1322	>	double on_edge;
1323	>	FVECT a,b;
1324		{
1106	–	int i,t_id,on0,on1,on2;
1325		FVECT n,v0,v1,v2;
1326	<	TRI *t;
1327	<	double side;
1326	>	TRI *tn;
1327	>	double on0,on1,on2;
1328	>	int tn_id;
1329
1330	<	for (i = QT_SET_CNT(optr),optr = QT_SET_PTR(optr);i > 0; i--)
1331	<	{
1332	<	/* Find the first triangle that pt falls */
1333	<	t_id = QT_SET_NEXT_ELEM(optr);
1334	<	t = SM_NTH_TRI(sm,t_id);
1335	<	if(!T_IS_VALID(t))
1336	<	continue;
1330	>	#ifdef DEBUG
1331	>	Wcnt++;
1332	>	on0 = on1 = on2 = 10;
1333	>	#endif
1334	>	switch(from){
1335	>	case 0:
1336	>	on0 = on_edge;
1337	>	/* Havnt calculate v0 yet: check for equality first */
1338		VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm));
1339	<	VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm));
1340	<	VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm));
1339	>	normalize(v0);
1340	>	if(EQUAL_VEC3(v0,p)){ *onptr = ON_V; *wptr = 0; return(t_id); }
1341	>	/* determine what side of edge v0v1 (v0a) point is on*/
1342	>	VCROSS(n,v0,a);
1343	>	normalize(n);
1344	>	on2 = DOT(n,p);
1345	>	if(on2 > 0.0)
1346	>	{
1347	>	tn_id = T_NTH_NBR(t,2);
1348	>	tn = SM_NTH_TRI(sm,tn_id);
1349	>	return(smWalk(sm,p,tn_id,tn,onptr,wptr,T_NTH_NBR_PTR(t_id,tn),
1350	>	-on2,a,v0));
1351	>	}
1352	>	else
1353	>	if(on2 >= -EDGE_EPS)
1354	>	{
1355	>	if(on0 >= -EDGE_EPS)
1356	>	{
1357	>	/* Could either be epsilon of vertex 1*/
1358	>	/* dot(p,a) == cos angle between them. Want length of chord x to
1359	>	be <= EDGE_EPS for test. if the perpendicular bisector of pa
1360	>	is d, cos@/2 = d/1, with right triangle d^2 + (x/2)^2 = 1
1361	>	or x^2 = 4(1-cos^2@/2) = 4(1- (1 + cos@)/2) =  2 -2cos@,
1362	>	so test is if  x^2 <= VERT_EPS*VERT_EPS,
1363	>	2 - 2cos@ <= VERT_EPS*VERT_EPS, or... */
1364	>	if(DOT(p,a) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1365	>	{*onptr = ON_P; *wptr = 1;}
1366	>	else
1367	>	if(on2 > on0)
1368	>	{*onptr = ON_E; *wptr = 2;}
1369	>	else
1370	>	{*onptr = ON_E; *wptr = 0;}
1371	>	return(t_id);
1372	>	}
1373	>	}
1374
1375	<	if(EQUAL_VEC3(v0,p))
1375	>	VCROSS(n,b,v0);
1376	>	normalize(n);
1377	>	on1 = DOT(n,p);
1378	>	if(on1 > 0.0)
1379		{
1380	<	*onptr = ON_V;
1381	<	*whichptr = 0;
1382	<	return(t_id);
1380	>	tn_id = T_NTH_NBR(t,1);
1381	>	tn = SM_NTH_TRI(sm,tn_id);
1382	>	return(smWalk(sm,p,tn_id,tn,onptr,wptr,T_NTH_NBR_PTR(t_id,tn),
1383	>	-on1,v0,b));
1384		}
1385	<	if(EQUAL_VEC3(v1,p))
1385	>	else
1386	>	if(on1 >= -EDGE_EPS)
1387	>	{ /* Either on v0 or on edge 1 */
1388	>	if(on0 >= -EDGE_EPS)
1389	>	{
1390	>	if(DOT(p,b) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1391	>	{*onptr = ON_P; *wptr = 2;}
1392	>	else
1393	>	if(on1 > on0)
1394	>	{*onptr = ON_E; *wptr = 1;}
1395	>	else
1396	>	{*onptr = ON_E; *wptr = 0;}
1397	>	return(t_id);
1398	>	}
1399	>	if(on2 >= -EDGE_EPS)
1400	>	{
1401	>	if(DOT(p,v0) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1402	>	{*onptr = ON_P; *wptr = 0;}
1403	>	else
1404	>	if( on1 > on2)
1405	>	{*onptr = ON_E; *wptr = 1;}
1406	>	else
1407	>	{*onptr = ON_E; *wptr = 2;}
1408	>	return(t_id);
1409	>	}
1410	>	*onptr = ON_E; *wptr = 1;
1411	>	return(t_id);
1412	>	}
1413	>	else
1414	>	if(on2 >= -EDGE_EPS)
1415	>	{
1416	>	*onptr = ON_E; *wptr = 2;
1417	>	return(t_id);
1418	>	}
1419	>	if(on0 >= -EDGE_EPS)
1420	>	{
1421	>	*onptr = ON_E; *wptr = 0;
1422	>	return(t_id);
1423	>	}
1424	>	*onptr = IN_T;
1425	>	return(t_id);
1426	>	case 1:
1427	>	on1 = on_edge;
1428	>	/* Havnt calculate v1 yet: check for equality first */
1429	>	VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm));
1430	>	normalize(v1);
1431	>	if(EQUAL_VEC3(v1,p)){ *onptr = ON_V; *wptr = 1; return(t_id); }
1432	>	/* determine what side of edge v0v1 (v0a) point is on*/
1433	>	VCROSS(n,b,v1);
1434	>	normalize(n);
1435	>	on2 = DOT(n,p);
1436	>	if(on2 > 0.0)
1437		{
1438	<	*onptr = ON_V;
1439	<	*whichptr = 1;
1440	<	return(t_id);
1438	>	tn_id = T_NTH_NBR(t,2);
1439	>	tn = SM_NTH_TRI(sm,tn_id);
1440	>	return(smWalk(sm,p,tn_id,tn,onptr,wptr,T_NTH_NBR_PTR(t_id,tn),
1441	>	-on2,v1,b));
1442		}
1443	<	if(EQUAL_VEC3(v2,p))
1443	>	if(on2 >= -EDGE_EPS)
1444		{
1445	<	*onptr = ON_V;
1446	<	*whichptr = 2;
1447	<	return(t_id);
1445	>	if(on1 >= -EDGE_EPS)
1446	>	{
1447	>	if(DOT(p,b) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1448	>	{ *onptr = ON_P; *wptr = 0;}
1449	>	else
1450	>	if(on2 > on1)
1451	>	{ *onptr = ON_E; *wptr = 2;}
1452	>	else
1453	>	{ *onptr = ON_E; *wptr = 1;}
1454	>	return(t_id);
1455	>	}
1456		}
1140	–
1141	–	on0 = on1 =on2 = 0;
1142	–	VCROSS(n,v0,v1);
1143	–	side = DOT(n,p);
1144	–	if(ZERO(side))
1145	–	on2 = TRUE;
1146	–	else
1147	–	if(side >0.0)
1148	–	continue;
1457
1458	<	VCROSS(n,v1,v2);
1459	<	side = DOT(n,p);
1460	<	if(ZERO(side))
1461	<	on0 = TRUE;
1458	>	VCROSS(n,v1,a);
1459	>	normalize(n);
1460	>	on0 = DOT(n,p);
1461	>	if(on0 >0.0)
1462	>	{
1463	>	tn_id = T_NTH_NBR(t,0);
1464	>	tn = SM_NTH_TRI(sm,tn_id);
1465	>	return(smWalk(sm,p,tn_id,tn,onptr,wptr,T_NTH_NBR_PTR(t_id,tn),
1466	>	-on0,a,v1));
1467	>	}
1468	>	else
1469	>	if(on0 >= -EDGE_EPS)
1470	>	{ /* Either on v0 or on edge 1 */
1471	>	if(on1 >= -EDGE_EPS)
1472	>	{
1473	>	if(DOT(p,a) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1474	>	{*onptr = ON_P; *wptr = 2;}
1475	>	else
1476	>	if(on0 > on1)
1477	>	{ *onptr = ON_E; *wptr = 0;}
1478	>	else
1479	>	{ *onptr = ON_E; *wptr = 1;}
1480	>	return(t_id);
1481	>	}
1482	>	if(on2 >= -EDGE_EPS)
1483	>	{
1484	>	if(DOT(p,v1) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1485	>	{*onptr = ON_P; *wptr = 1;}
1486	>	else
1487	>	if(on0 > on2)
1488	>	{ *onptr = ON_E; *wptr = 0;}
1489	>	else
1490	>	{ *onptr = ON_E; *wptr = 2;}
1491	>	return(t_id);
1492	>	}
1493	>	*onptr = ON_E; *wptr = 0;
1494	>	return(t_id);
1495	>	}
1496		else
1497	<	if(side >0.0)
1498	<	continue;
1497	>	if(on2 >= -EDGE_EPS)
1498	>	{
1499	>	*onptr = ON_E; *wptr = 2;
1500	>	return(t_id);
1501	>	}
1502	>	if(on1 >= -EDGE_EPS)
1503	>	{
1504	>	*onptr = ON_E; *wptr = 1;
1505	>	return(t_id);
1506	>	}
1507	>	*onptr = IN_T;
1508	>	return(t_id);
1509	>	case 2:
1510	>	on2 = on_edge;
1511	>	VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm));
1512	>	normalize(v2);
1513	>	if(EQUAL_VEC3(v2,p)){ *onptr = ON_V; *wptr = 2; return(t_id); }
1514
1515	<	VCROSS(n,v2,v0);
1516	<	side = DOT(n,p);
1517	<	if(ZERO(side))
1518	<	on1 = TRUE;
1519	<	else
1163	<	if(side >0.0)
1164	<	continue;
1165	<	if(on0)
1515	>	/* determine what side of edge v0v1 (v0a) point is on*/
1516	>	VCROSS(n,b,v2);
1517	>	normalize(n);
1518	>	on0 = DOT(n,p);
1519	>	if(on0 > 0.0)
1520		{
1521	<	if(on1)
1521	>	tn_id = T_NTH_NBR(t,0);
1522	>	tn = SM_NTH_TRI(sm,tn_id);
1523	>	return(smWalk(sm,p,tn_id,tn,onptr,wptr,T_NTH_NBR_PTR(t_id,tn),
1524	>	-on0,v2,b));
1525	>	}
1526	>	else
1527	>	if(on0 >= -EDGE_EPS)
1528		{
1529	<	*onptr = ON_P;
1530	<	*whichptr = 2;
1529	>	if(on2 >= - EDGE_EPS)
1530	>	{
1531	>	if(DOT(p,b) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1532	>	{*onptr = ON_P; *wptr = 1;}
1533	>	else
1534	>	if(on0 > on2)
1535	>	{*onptr = ON_E; *wptr = 0;}
1536	>	else
1537	>	{*onptr = ON_E; *wptr = 2;}
1538	>	return(t_id);
1539	>	}
1540		}
1541	<	else
1542	<	if(on2)
1541	>	VCROSS(n,v2,a);
1542	>	normalize(n);
1543	>	on1 = DOT(n,p);
1544	>	if(on1 >0.0)
1545	>	{
1546	>	tn_id = T_NTH_NBR(t,1);
1547	>	tn = SM_NTH_TRI(sm,tn_id);
1548	>	return(smWalk(sm,p,tn_id,tn,onptr,wptr,T_NTH_NBR_PTR(t_id,tn),
1549	>	-on1,a,v2));
1550	>	}
1551	>	else
1552	>	if(on1 >= -EDGE_EPS)
1553	>	{ /* Either on v0 or on edge 1 */
1554	>	if(on0 >= - EDGE_EPS)
1555		{
1556	<	*onptr = ON_P;
1557	<	*whichptr = 1;
1556	>	if(DOT(p,v2) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1557	>	{*onptr = ON_P;*wptr = 2;}
1558	>	else
1559	>	if(on1 > on0)
1560	>	{*onptr = ON_E;*wptr = 1;}
1561	>	else
1562	>	{*onptr = ON_E;*wptr = 0;}
1563	>	return(t_id);
1564		}
1565	+	if(on2 >= -EDGE_EPS)
1566	+	{
1567	+	if(DOT(p,a) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1568	+	{*onptr = ON_P;*wptr = 0;}
1569		else
1570	<	{
1571	<	*onptr = ON_E;
1572	<	*whichptr = 0;
1573	<	}
1570	>	if(on1 > on2)
1571	>	{*onptr = ON_E;*wptr = 1;}
1572	>	else
1573	>	{*onptr = ON_E;*wptr = 2;}
1574	>	return(t_id);
1575	>	}
1576	>	*onptr = ON_E;*wptr = 1;
1577	>	return(t_id);
1578	>	}
1579	>	else
1580	>	if(on0 >= -EDGE_EPS)
1581	>	{
1582	>	*onptr = ON_E;*wptr = 0;
1583	>	return(t_id);
1584	>	}
1585	>	if(on2 >= -EDGE_EPS)
1586	>	{
1587	>	*onptr = ON_E;*wptr = 2;
1588	>	return(t_id);
1589	>	}
1590	>	*onptr = IN_T;
1591	>	return(t_id);
1592	>	default:
1593	>	/* First time called: havnt tested anything */
1594	>	/* Check against vertices */
1595	>	VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm));
1596	>	normalize(v0);
1597	>	if(EQUAL_VEC3(v0,p)){ *onptr = ON_V; *wptr = 0; return(t_id); }
1598	>	VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm));
1599	>	normalize(v1);
1600	>	if(EQUAL_VEC3(v1,p)){ *onptr = ON_V; *wptr = 1; return(t_id); }
1601	>	VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm));
1602	>	normalize(v2);
1603	>	if(EQUAL_VEC3(v2,p)){ *onptr = ON_V; *wptr = 2; return(t_id); }
1604	>
1605	>	VCROSS(n,v0,v1);  /* Check against v0v1, or edge 2 */
1606	>	normalize(n);
1607	>	on2 = DOT(n,p);
1608	>	if(on2 > 0.0)
1609	>	{              /* Outside edge: traverse to nbr 2 */
1610	>	tn_id = T_NTH_NBR(t,2);
1611	>	tn = SM_NTH_TRI(sm,tn_id);
1612	>	return(smWalk(sm,p,tn_id,tn,onptr,wptr,T_NTH_NBR_PTR(t_id,tn),
1613	>	-on2,v1,v0));
1614	>	}
1615	>	else
1616	>	VCROSS(n,v1,v2);  /* Check against v1v2 or edge 0 */
1617	>	normalize(n);
1618	>	on0 = DOT(n,p);
1619	>	if(on0 > 0.0)
1620	>	{                      /* Outside edge: traverse to nbr 0 */
1621	>	tn_id = T_NTH_NBR(t,0);
1622	>	tn = SM_NTH_TRI(sm,tn_id);
1623	>	return(smWalk(sm,p,tn_id,tn,onptr,wptr,T_NTH_NBR_PTR(t_id,tn),
1624	>	-on0,v2,v1));
1625	>	}
1626	>	else
1627	>	if(on0 >= -EDGE_EPS)
1628	>	{                /* On the line defining edge 0 */
1629	>	if(on2 >= -EDGE_EPS)
1630	>	{
1631	>	if(DOT(p,v1) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1632	>	{*onptr = ON_P;*wptr = 1;}
1633	>	else
1634	>	if(on0 > on2)
1635	>	{*onptr = ON_E;*wptr = 0;}
1636	>	else
1637	>	{*onptr = ON_E;*wptr = 2;}
1638	>	return(t_id);
1639	>	}
1640	>	}
1641	>	VCROSS(n,v2,v0);  /* Check against v2v0 or edge 1 */
1642	>	normalize(n);
1643	>	on1 = DOT(n,p);
1644	>	if(on1 >0.0)
1645	>	{                            /* Outside edge: traverse to nbr 1 */
1646	>	tn_id = T_NTH_NBR(t,1);
1647	>	tn = SM_NTH_TRI(sm,tn_id);
1648	>	return(smWalk(sm,p,tn_id,tn,onptr,wptr,T_NTH_NBR_PTR(t_id,tn),
1649	>	-on1,v0,v2));
1650	>	}
1651	>	else
1652	>	if(on1  >= -EDGE_EPS)
1653	>	{               /* On the line defining edge 1 */
1654	>	if(on2 >= -EDGE_EPS)
1655	>	{
1656	>	if(DOT(p,v0) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1657	>	{*onptr = ON_P;*wptr = 0;}
1658	>	else
1659	>	if(on1 > on2)
1660	>	{*onptr = ON_E;*wptr = 1;}
1661	>	else
1662	>	{*onptr = ON_E;*wptr = 2;}
1663	>	return(t_id);
1664	>	}
1665	>	if(on0 >= -EDGE_EPS)
1666	>	{
1667	>	if(DOT(p,v2) >= 1.0-VERT_EPS*VERT_EPS/2.0)
1668	>	{*onptr = ON_P;*wptr = 2;}
1669	>	else
1670	>	if(on1 > on0)
1671	>	{*onptr = ON_E;*wptr = 1;}
1672	>	else
1673	>	{*onptr = ON_E;*wptr = 0;}
1674	>	return(t_id);
1675	>	}
1676	>	*onptr = ON_E; /* Only on edge 1 */
1677	>	*wptr = 1;
1678	>	return(t_id);
1679	>	}
1680	>	else
1681	>	if(on2 >= -EDGE_EPS)           /* Is on edge 2 ? */
1682	>	{
1683	>	*onptr = ON_E; *wptr = 2;
1684	>	return(t_id);
1685	>	}
1686	>	if(on0 >= -EDGE_EPS)            /* Is on edge 0 ? */
1687	>	{
1688	>	*onptr = ON_E; *wptr = 0;
1689		return(t_id);
1690		}
1691	<	if(on1)
1691	>	*onptr = IN_T;   /* Must be interior to t */
1692	>	return(t_id);
1693	>	}
1694	>	}
1695	>
1696	>	#define check_edges(on0,on1,on2,o,w,t_id) \
1697	>	if(on0){if(on1){*o = ON_P;*w = 2;} else if(on2){*o = ON_P;*w = 1;} \
1698	>	else {*o = ON_E; *w = 0; } return(t_id); } \
1699	>	if(on1){if(on2){*o = ON_P;*w = 0;} else {*o = ON_E;*w = 1;}return(t_id);}\
1700	>	if(on2){*o = ON_E;*w = 2;return(t_id);}
1701	>
1702	>	#define  check_verts(p,v0,v1,v2,o,w,t_id) \
1703	>	if(EQUAL_VEC3(v0,p)){ *o = ON_V; *w = 0; return(t_id); } \
1704	>	if(EQUAL_VEC3(v1,p)){ *o = ON_V; *w = 1; return(t_id); } \
1705	>	if(EQUAL_VEC3(v2,p)){ *o = ON_V; *w = 2; return(t_id);}
1706	>
1707	>
1708	>
1709	>	find_neighbor(argptr,qt,f,doneptr)
1710	>	int *argptr;
1711	>	QUADTREE qt;
1712	>	FUNC f;
1713	>	int *doneptr;
1714	>	{
1715	>	S_ID s_id;
1716	>	int i;
1717	>	S_ID *optr;
1718	>
1719	>	if(QT_IS_EMPTY(qt))
1720	>	return;
1721	>	else
1722	>	if(QT_IS_TREE(qt))
1723		{
1724	<	if(on2)
1724	>	for(i=0;i < 4; i++)
1725		{
1726	<	*onptr = ON_P;
1727	<	*whichptr = 0;
1726	>	find_neighbor(argptr,QT_NTH_CHILD(qt,i),f,doneptr);
1727	>	if(*doneptr)
1728	>	return;
1729		}
1730	<	else
1730	>	}
1731	>	else
1732	>	{
1733	>	optr = qtqueryset(qt);
1734	>	for(i = QT_SET_CNT(optr); i > 0; i--)
1735		{
1736	<	*onptr = ON_E;
1737	<	*whichptr = 1;
1736	>	s_id = QT_SET_NEXT_ELEM(optr);
1737	>	if(s_id != ((S_ARGS *)argptr)->s_id)
1738	>	{
1739	>	*doneptr = TRUE;
1740	>	((S_ARGS *)argptr)->n_id = s_id;
1741	>	return;
1742	>	}
1743		}
1197	–	return(t_id);
1744		}
1745	<	if(on2)
1746	<	{
1747	<	*onptr = ON_E;
1748	<	*whichptr = 2;
1749	<	return(t_id);
1750	<	}
1751	<	*onptr = IN_T;
1752	<	return(t_id);
1745	>	}
1746	>
1747	>	smInsert_samp(sm,s_id,p,nptr)
1748	>	SM *sm;
1749	>	S_ID s_id;
1750	>	FVECT p;
1751	>	S_ID *nptr;
1752	>	{
1753	>	FVECT tpt;
1754	>	FUNC f;
1755	>	S_ARGS args;
1756	>
1757	>	F_FUNC(f) = insert_samp;
1758	>	args.s_id = s_id;
1759	>	if(nptr)
1760	>	{
1761	>	args.n_id = 1;
1762	>	F_FUNC2(f) = find_neighbor;
1763		}
1764	<	return(INVALID);
1764	>	else
1765	>	args.n_id = 0;
1766	>	F_ARGS(f) = (int *)(&args);
1767	>	stInsert_samp(SM_LOCATOR(sm),p,f);
1768	>
1769	>	if(nptr)
1770	>	*nptr = args.n_id;
1771		}
1772
1773	+	/* Assumed p is normalized to view sphere */
1774		int
1775	<	smPointLocateTri(sm,p,onptr,whichptr)
1775	>	smSample_locate_tri(sm,p,s_id,onptr,whichptr,nptr)
1776		SM *sm;
1777		FVECT p;
1778	+	S_ID s_id;
1779		int *onptr,*whichptr;
1780	+	S_ID *nptr;
1781		{
1217	–	QUADTREE qt,*optr;
1218	–	FVECT tpt;
1782		int tri_id;
1783	+	FVECT tpt;
1784	+	TRI *tri;
1785
1786	<	VSUB(tpt,p,SM_VIEW_CENTER(sm));
1787	<	qt = smPointLocateCell(sm,tpt);
1788	<	if(QT_IS_EMPTY(qt))
1789	<	return(INVALID);
1790	<
1791	<	optr = qtqueryset(qt);
1792	<	tri_id = smTri_in_set(sm,tpt,optr,onptr,whichptr);
1786	>	if(SM_S_NTH_QT(sm,s_id) == EMPTY)
1787	>	smInsert_samp(sm,s_id,p,nptr);
1788	>	#ifdef DEBUG
1789	>	if(*nptr == INVALID)
1790	>	error(CONSISTENCY,"smSample_locate_tri: unable to find sample\n");
1791	>	#endif
1792	>
1793	>	/* Get the triangle adjacent to a sample in qt, or if there are no other
1794	>	samples in qt than the one just inserted, look at siblings-from parent
1795	>	node
1796	>	*/
1797
1798	+	tri_id = SM_NTH_VERT(sm,*nptr);
1799		#ifdef DEBUG
1800	<	if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tri_id),0))) ||
1801	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tri_id),1))) ||
1232	<	!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tri_id),2))))
1233	<	eputs("Invalid tri nbrs smPointLocateTri()\n");
1800	>	if(tri_id == INVALID)
1801	>	error(CONSISTENCY,"smSample_locate_tri: Invalid tri_id\n");
1802		#endif
1803	<	return(tri_id);
1803	>
1804	>	tri = SM_NTH_TRI(sm,tri_id);
1805	>	#ifdef DEBUG
1806	>	Tcnt++;
1807	>	if(!T_IS_VALID(tri))
1808	>	error(CONSISTENCY,"smSample_locate_tri: Invalid tri\n");
1809	>	#endif
1810	>	tri_id = smWalk(sm,p,tri_id,tri,onptr,whichptr,-1,0.0,NULL,NULL);
1811	>	#ifdef DEBUG
1812	>	if(tri_id == INVALID)
1813	>	error(CONSISTENCY,"smSample_locate_tri: unable to find tri on walk\n");
1814	>	#endif
1815	>	return(tri_id);
1816		}
1817
1238	–
1818		/*
1819		Determine whether this sample should:
1820		a) be added to the mesh by subdividing the triangle
#	Line 1265 | Line 1844 | int *onptr,*whichptr;
1844		This attempts to throw out points that should be occluded
1845		*/
1846		int
1847	<	smTest_sample(sm,tri_id,dir,p,rptr)
1847	>	smTest_samp(sm,tri_id,dir,p,rptr,ns,n0,n1,n2,ds,d0,on,which)
1848		SM *sm;
1849		int tri_id;
1850		FVECT dir,p;
1851	<	int *rptr;
1851	>	S_ID *rptr;
1852	>	FVECT ns,n0,n1,n2;
1853	>	double ds,d0;
1854	>	int on,which;
1855		{
1856		TRI *tri;
1857	<	double d,d2,dnear,dspt,d01,d12,d20,s0,s1,s2,ds,dv;
1858	<	int vid[3],i,nearid,norm,dcnt,bcnt;
1859	<	FVECT diff[3],spt,npt;
1857	>	double d,d2,dnear,dspt,d01,d12,d20,s0,s1,s2;
1858	>	double dp,dp1;
1859	>	S_ID vid[3];
1860	>	int i,norm,dcnt,bcnt;
1861	>	FVECT diff[3],spt,npt,n;
1862	>	FVECT nearpt;
1863
1864		*rptr = INVALID;
1865		bcnt = dcnt = 0;
#	Line 1285 | Line 1870 | smTest_sample(sm,tri_id,dir,p,rptr)
1870
1871		for(i=0; i<3; i++)
1872		{
1873	<	if(SM_BASE_ID(sm,vid[i]))
1874	<	{
1875	<	bcnt++;
1291	<	continue;
1292	<	}
1873	>	if(SM_BASE_ID(sm,vid[i]))
1874	>	bcnt++;
1875	>	else
1876		if(SM_DIR_ID(sm,vid[i]))
1877	<	dcnt++;
1295	<	VSUB(diff[i],SM_NTH_WV(sm,vid[i]),p);
1296	<	/* If same world point: replace */
1877	>	dcnt++;
1878		}
1879	<	/* TEST 1: If the new sample is close in ws, and close in the spherical
1299	<	projection to one of the triangle vertex samples
1300	<	*/
1301	<	norm = FALSE;
1302	<	if(bcnt + dcnt != 3)
1879	>	if(on == ON_P)
1880		{
1881	<	VSUB(spt,p,SM_VIEW_CENTER(sm));
1882	<	ds = DOT(spt,spt);
1883	<	dnear = FHUGE;
1884	<	for(i=0; i<3; i++)
1885	<	{
1886	<	if(SM_BASE_ID(sm,vid[i]) || SM_DIR_ID(sm,vid[i]))
1887	<	continue;
1888	<	d = DOT(diff[i],diff[i])/ds;
1889	<	if(d < dnear)
1890	<	{
1891	<	dnear = d;
1892	<	nearid=vid[i];
1893	<	}
1894	<	}
1881	>	FVECT edir;
1882	>	/* Pick the point with dir closest to that of the canonical view
1883	>	if it is the new sample: mark existing point for deletion
1884	>	*/
1885	>	if(!dir)
1886	>	return(FALSE);
1887	>	if(SM_BASE_ID(sm,vid[which]))
1888	>	return(FALSE);
1889	>	if(SM_DIR_ID(sm,vid[which]))
1890	>	{
1891	>	*rptr = vid[which];
1892	>	return(TRUE);
1893	>	}
1894	>	decodedir(edir,SM_NTH_W_DIR(sm,vid[which]));
1895	>	if(which == 0)
1896	>	d = DOT(edir,n0);
1897	>	else
1898	>	if(which == 1)
1899	>	d = DOT(edir,n1);
1900	>	else
1901	>	d = DOT(edir,n2);
1902	>	d2 = DOT(dir,ns);
1903	>	/* The existing sample is a better sample:punt */
1904	>	if(d2 >= d)
1905	>	return(FALSE);
1906	>	else
1907	>	{
1908	>	/* The new sample is better: mark existing one for deletion*/
1909	>	*rptr = vid[which];
1910	>	return(TRUE);
1911	>	}
1912	>	}
1913
1914	<	if(dnear <=  smMinSampDiff*smMinSampDiff)
1914	>	/* Now test if sample epsilon is within circumcircle of enclosing tri
1915	>	if not punt:
1916	>	*/
1917	>	{
1918	>	double ab[3],ac[3],r[3];
1919	>
1920	>	VSUB(ab,n2,n1);
1921	>	VSUB(ac,n0,n2);
1922	>	VCROSS(r,ab,ac);
1923	>	dp = DOT(r,n1);
1924	>	dp1 = DOT(r,ns);
1925	>	if(dp1*dp1 + COS_VERT_EPS*DOT(r,r) < dp*dp)
1926		{
1927	<	/* Pick the point with dir closest to that of the canonical view
1928	<	if it is the new sample: mark existing point for deletion
1929	<	*/
1930	<	normalize(spt);
1325	<	norm = TRUE;
1326	<	VSUB(npt,SM_NTH_WV(sm,nearid),SM_VIEW_CENTER(sm));
1327	<	normalize(npt);
1328	<	d = fdir2diff(SM_NTH_W_DIR(sm,nearid), npt);
1329	<	d2 = 2. - 2.*DOT(dir,spt);
1330	<	/* The existing sample is a better sample:punt */
1331	<	if(d2 > d)
1332	<	return(FALSE);
1333	<	else
1334	<	{
1335	<	/* The new sample is better: mark the existing one
1336	<	for deletion after the new one is added*/
1337	<	*rptr = nearid;
1338	<	return(TRUE);
1339	<	}
1927	>	#ifdef DEBUG
1928	>	eputs("smTest_samp:rejecting samp,cant guarantee not within eps\n");
1929	>	#endif
1930	>	return(FALSE);
1931		}
1932		}
1933	<	/* TEST 3: If the spherical projection of new is < S_REPLACE_EPS
1934	<	from a base point: Edge length is constrained to subtend <45 degrees:
1935	<	original base mesh edges are approx 32 degrees- so have about 13 degrees
1936	<	to work in: S_REPLACE_EPS is the square of the radian value
1937	<	*/
1938	<	if(bcnt)
1939	<	{
1349	<	dnear = FHUGE;
1350	<	if(bcnt + dcnt ==3)
1351	<	VSUB(spt,p,SM_VIEW_CENTER(sm));
1352	<	if(!norm)
1353	<	normalize(spt);
1933	>	#ifdef DEBUG
1934	>	#if DEBUG > 1
1935	>	if(on == ON_E)
1936	>	{
1937	>	TRI *topp;
1938	>	int opp_id;
1939	>	FVECT vopp;
1940
1941	<	for(i=0; i<3; i++)
1942	<	{
1943	<	if(!SM_BASE_ID(sm,vid[i]))
1944	<	continue;
1945	<	VSUB(npt,SM_NTH_WV(sm,vid[i]),SM_VIEW_CENTER(sm));
1946	<	d = DIST_SQ(npt,spt);
1947	<	if(d < S_REPLACE_EPS && d < dnear)
1948	<	{
1949	<	dnear = d;
1950	<	nearid = vid[i];
1951	<	}
1952	<	}
1953	<	if(dnear != FHUGE)
1954	<	{
1955	<	/* add new and mark the base for deletion */
1956	<	*rptr = nearid;
1957	<	return(TRUE);
1958	<	}
1941	>	topp = SM_NTH_TRI(sm,T_NTH_NBR(tri,which));
1942	>	opp_id = T_NTH_V(topp, T_NTH_NBR_PTR(tri_id,topp));
1943	>	/* first check if valid tri created*/
1944	>	VSUB(vopp,SM_NTH_WV(sm,opp_id),SM_VIEW_CENTER(sm));
1945	>	normalize(vopp);
1946	>	VCROSS(n,ns,vopp);
1947	>	normalize(n);
1948	>	if(which==2)
1949	>	dp = DOT(n,n0) * DOT(n,n1);
1950	>	else
1951	>	if(which==0)
1952	>	dp = DOT(n,n1) * DOT(n,n2);
1953	>	else
1954	>	dp = DOT(n,n2) * DOT(n,n0);
1955	>	if(dp > 0.0)
1956	>	{
1957	>	eputs("smInsert_samp_mesh: couldn't split edge: rejecting\n");
1958	>	/* test epsilon for edge */
1959	>	return(FALSE);
1960	>	}
1961		}
1962	<
1962	>	#endif
1963	>	#endif
1964		/* TEST 4:
1965		If the addition of the new sample point would introduce a "puncture"
1966		or cause new triangles with large depth differences:dont add:
1967		*/
1968		if(bcnt || dcnt)
1969		return(TRUE);
1970	<	/* If the new point is in front of the existing points- add */
1971	<	dv = DIST_SQ(SM_NTH_WV(sm,vid[0]),SM_VIEW_CENTER(sm));
1383	<	if(ds < dv)
1970	>
1971	>	if(ds < d0)
1972		return(TRUE);
1973
1974		d01 = DIST_SQ(SM_NTH_WV(sm,vid[1]),SM_NTH_WV(sm,vid[0]));
1975	+	VSUB(diff[0],SM_NTH_WV(sm,vid[0]),p);
1976		s0 = DOT(diff[0],diff[0]);
1977		if(s0 < S_REPLACE_SCALE*d01)
1978		return(TRUE);
1979	+
1980		d12 = DIST_SQ(SM_NTH_WV(sm,vid[2]),SM_NTH_WV(sm,vid[1]));
1981		if(s0 < S_REPLACE_SCALE*d12)
1982		return(TRUE);
#	Line 1394 | Line 1984 | smTest_sample(sm,tri_id,dir,p,rptr)
1984		if(s0 < S_REPLACE_SCALE*d20)
1985		return(TRUE);
1986		d = MIN3(d01,d12,d20);
1987	<	s1 = DOT(diff[1],diff[1]);
1987	>	VSUB(diff[1],SM_NTH_WV(sm,vid[1]),p);
1988	>	s1 = DOT(diff[1],diff[1]);
1989		if(s1 < S_REPLACE_SCALE*d)
1990		return(TRUE);
1991	+	VSUB(diff[2],SM_NTH_WV(sm,vid[2]),p);
1992		s2 = DOT(diff[2],diff[2]);
1993		if(s2 < S_REPLACE_SCALE*d)
1994		return(TRUE);
#	Line 1404 | Line 1996 | smTest_sample(sm,tri_id,dir,p,rptr)
1996		/* TEST 5:
1997		Check to see if triangle is relatively large and should therefore
1998		be subdivided anyway.
1999	<	*/
2000	<	dv *= DIST_SQ(SM_NTH_WV(sm,vid[1]),SM_VIEW_CENTER(sm));
2001	<	dv *= DIST_SQ(SM_NTH_WV(sm,vid[2]),SM_VIEW_CENTER(sm));
2002	<	if (d01*d12*d20/dv > S_REPLACE_TRI)
1999	>	*/
2000	>	d0 = d0*d0*DIST_SQ(SM_NTH_WV(sm,vid[1]),SM_VIEW_CENTER(sm));
2001	>	d0 *= DIST_SQ(SM_NTH_WV(sm,vid[2]),SM_VIEW_CENTER(sm));
2002	>	if (d01*d12*d20/d0 > S_REPLACE_TRI)
2003		return(TRUE);
2004
2005		return(FALSE);
2006		}
2007	<
2008	<
1417	<	int
1418	<	smAlloc_samp(sm)
1419	<	SM *sm;
1420	<	{
1421	<	int s_id,replaced,cnt;
1422	<	SAMP *s;
1423	<	FVECT p;
1424	<
1425	<	s = SM_SAMP(sm);
1426	<	s_id = sAlloc_samp(s,&replaced);
1427	<
1428	<	cnt=0;
1429	<	while(replaced)
1430	<	{
1431	<	if(smRemoveVertex(sm,s_id))
1432	<	break;
1433	<	s_id = sAlloc_samp(s,&replaced);
1434	<	cnt++;
1435	<	if(cnt > S_MAX_SAMP(s))
1436	<	error(CONSISTENCY,"smAlloc_samp():unable to find free samp\n");
1437	<	}
1438	<	return(s_id);
1439	<	}
1440	<
1441	<	int
1442	<	smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which)
2007	>	S_ID
2008	>	smReplace_samp(sm,c,dir,p,np,s_id,t_id,o_id,on,which)
2009		SM *sm;
2010		COLR c;
2011	<	FVECT dir,p;
2012	<	int s_id,t_id,o_id,on,which;
2011	>	FVECT dir,p,np;
2012	>	S_ID s_id;
2013	>	int t_id;
2014	>	S_ID o_id;
2015	>	int on,which;
2016		{
2017	<	int tonemap,v_id;
2017	>	S_ID v_id;
2018	>	int tri_id;
2019		TRI *t,*tri;
2020
2021		tri = SM_NTH_TRI(sm,t_id);
#	Line 1453 | Line 2023 | smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which)
2023
2024		/* If it is a base id, need new sample */
2025		if(SM_BASE_ID(sm,v_id))
2026	<	{
2027	<	tonemap = (SM_TONE_MAP(sm) > s_id);
2028	<	sInit_samp(SM_SAMP(sm),s_id,c,dir,p,o_id,tonemap);
2029	<	SM_NTH_VERT(sm,s_id) = t_id;
2030	<	T_NTH_V(tri,which) = s_id;
2031	<	if(!(SM_BASE_ID(sm,T_NTH_V(tri,(which+1)%3)) ||
2032	<	SM_BASE_ID(sm,T_NTH_V(tri,(which+2)%3))))
2033	<	SM_CLR_NTH_T_BASE(sm,t_id);
2034	<	t_id = smTri_next_ccw_nbr(sm,tri,v_id);
2035	<	while(t_id != INVALID)
2026	>	return(v_id);
2027	>
2028	>	if(EQUAL_VEC3(p,SM_NTH_WV(sm,v_id)))
2029	>	return(INVALID);
2030	>
2031	>	if(dir)
2032	>	{    /* If world point */
2033	>	FVECT odir,no;
2034	>	double d,d1;
2035	>	int dir_id;
2036	>	/* if existing point is a not a dir, compare directions */
2037	>	if(!(dir_id = SM_DIR_ID(sm,v_id)))
2038		{
2039	<	t = SM_NTH_TRI(sm,t_id);
2040	<	which = T_WHICH_V(t,v_id);
2041	<	T_NTH_V(t,which) = s_id;
2042	<	/* Check if still a base triangle */
2043	<	if(!(SM_BASE_ID(sm,T_NTH_V(t,(which+1)%3)) ||
1472	<	SM_BASE_ID(sm,T_NTH_V(t,(which+2)%3))))
1473	<	SM_CLR_NTH_T_BASE(sm,t_id);
1474	<	t_id = smTri_next_ccw_nbr(sm,t,v_id);
2039	>	decodedir(odir, SM_NTH_W_DIR(sm,v_id));
2040	>	VSUB(no,SM_NTH_WV(sm,v_id),SM_VIEW_CENTER(sm));
2041	>	d = DOT(dir,np);
2042	>	d1 = DOT(odir,np);
2043	>	/* The existing sample is a better sample:punt */
2044		}
2045	<	return(s_id);
1477	<	}
1478	<	else
1479	<	if(on == ON_V || !p)
2045	>	if(dir_id || (d*d*DOT(no,no) > d1*d1))
2046		{
2047	<	tonemap = (SM_TONE_MAP(sm) > v_id);
2048	<	sInit_samp(SM_SAMP(sm),v_id,c,dir,p,o_id,tonemap);
2049	<	return(v_id);
2050	<	}
2051	<	else /* on == ON_P */
2052	<	{
1487	<	FVECT spt,npt;
1488	<	double d,d2;
1489	<
1490	<	/* Need to check which sample is preferable */
1491	<	VSUB(spt,p,SM_VIEW_CENTER(sm));
1492	<	normalize(spt);
1493	<
1494	<	VSUB(npt,SM_NTH_WV(sm,v_id),SM_VIEW_CENTER(sm));
1495	<	normalize(npt);
1496	<	d = fdir2diff(SM_NTH_W_DIR(sm,v_id), npt);
1497	<	d2 = 2. - 2.*DOT(dir,spt);
1498	<	/* The existing sample is a better sample:punt */
1499	<	if(d2 < d)
2047	>	/* The new sample has better information- replace values */
2048	>	sInit_samp(SM_SAMP(sm),v_id,c,dir,p,o_id);
2049	>	if(!SM_IS_NTH_T_NEW(sm,t_id))
2050	>	SM_SET_NTH_T_NEW(sm,t_id);
2051	>	tri_id = smTri_next_ccw_nbr(sm,tri,v_id);
2052	>	while(tri_id != t_id)
2053		{
2054	<	/* The new sample has better information- replace values */
2055	<	tonemap = (SM_TONE_MAP(sm) > v_id);
2056	<	sInit_samp(SM_SAMP(sm),v_id,c,dir,p,o_id,tonemap);
2054	>	t = SM_NTH_TRI(sm,tri_id);
2055	>	if(!SM_IS_NTH_T_NEW(sm,tri_id))
2056	>	SM_SET_NTH_T_NEW(sm,tri_id);
2057	>	tri_id = smTri_next_ccw_nbr(sm,t,v_id);
2058		}
1505	–	return(v_id);
2059		}
2060	+	return(v_id);
2061	+	}
2062	+	else  /* New point is a dir */
2063	+	return(INVALID);
2064	+
2065		}
2066
2067	+	S_ID
2068	+	smAlloc_samp(sm)
2069	+	SM *sm;
2070	+	{
2071	+	S_ID s_id;
2072	+	int replaced,cnt;
2073	+	SAMP *s;
2074	+	FVECT p;
2075	+
2076	+	s = SM_SAMP(sm);
2077	+	s_id = sAlloc_samp(s,&replaced);
2078	+	while(replaced)
2079	+	{
2080	+	smRemoveVertex(sm,s_id);
2081	+	s_id = sAlloc_samp(s,&replaced);
2082	+	}
2083	+	return(s_id);
2084	+	}
2085	+
2086	+
2087		/* Add sample to the mesh:
2088
2089		the sample can be a world space or directional point. If o_id !=INVALID,
#	Line 1519 | Line 2097 | smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which)
2097		b) coincide with existing edge
2098		c) Fall in existing triangle
2099		*/
2100	<	int
2100	>	S_ID
2101		smAdd_samp(sm,c,dir,p,o_id)
2102		SM *sm;
2103		COLR c;
2104		FVECT dir,p;
2105	<	int o_id;
2105	>	S_ID o_id;
2106		{
2107	<	int t_id,s_id,r_id,on,which,n_id;
2108	<	double d;
2109	<	FVECT wpt;
2107	>	int t_id,on,which,n_id;
2108	>	S_ID s_id,r_id,nbr_id;
2109	>	double ds,d0;
2110	>	FVECT wpt,ns,n0,n1,n2;
2111	>	QUADTREE qt,parent;
2112	>	TRI *t;
2113
2114		r_id = INVALID;
2115	<
2115	>	nbr_id = INVALID;
2116		/* Must do this first-as may change mesh */
2117		s_id = smAlloc_samp(sm);
2118	+	SM_S_NTH_QT(sm,s_id)= EMPTY;
2119		/* If sample is a world space point */
2120		if(p)
2121		{
2122	<	t_id = smPointLocateTri(sm,p,&on,&which);
2123	<	if(t_id == INVALID)
2122	>	VSUB(ns,p,SM_VIEW_CENTER(sm));
2123	>	ds = normalize(ns);
2124	>	while(1)
2125	>	{
2126	>	t_id = smSample_locate_tri(sm,ns,s_id,&on,&which,&nbr_id);
2127	>	qt = SM_S_NTH_QT(sm,s_id);
2128	>	if(t_id == INVALID)
2129		{
2130		#ifdef DEBUG
2131	<	eputs("smAddSamp(): unable to locate tri containing sample \n");
2131	>	eputs("smAddSamp(): unable to locate tri containing sample \n");
2132		#endif
2133	+	smUnalloc_samp(sm,s_id);
2134	+	qtremovelast(qt,s_id);
2135	+	return(INVALID);
2136	+	}
2137	+	/* If spherical projection coincides with existing sample: replace */
2138	+	if(on == ON_V)
2139	+	{
2140	+	n_id = smReplace_samp(sm,c,dir,p,ns,s_id,t_id,o_id,on,which);
2141	+	if(n_id != s_id)
2142	+	{
2143	+	smUnalloc_samp(sm,s_id);
2144	+	#if 0
2145	+	fprintf(stderr,"Unallocating sample %d\n",s_id);
2146	+	#endif
2147	+	qtremovelast(qt,s_id);
2148	+	}
2149	+	return(n_id);
2150	+	}
2151	+	t = SM_NTH_TRI(sm,t_id);
2152	+	VSUB(n0,SM_NTH_WV(sm,T_NTH_V(t,0)),SM_VIEW_CENTER(sm));
2153	+	d0 = normalize(n0);
2154	+	VSUB(n1,SM_NTH_WV(sm,T_NTH_V(t,1)),SM_VIEW_CENTER(sm));
2155	+	normalize(n1);
2156	+	VSUB(n2,SM_NTH_WV(sm,T_NTH_V(t,2)),SM_VIEW_CENTER(sm));
2157	+	normalize(n2);
2158	+	if((!(smTest_samp(sm,t_id,dir,p,&r_id,ns,n0,n1,n2,ds,d0,on,which))))
2159	+	{
2160		smUnalloc_samp(sm,s_id);
2161	+	#if 0
2162	+	fprintf(stderr,"Unallocating sample %d\n",s_id);
2163	+	#endif
2164	+	qtremovelast(qt,s_id);
2165		return(INVALID);
2166		}
2167	<	/* If spherical projection coincides with existing sample: replace */
2168	<	if((on == ON_V || on == ON_P))
2169	<	{
2170	<	if((n_id = smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which))!= s_id)
2171	<	smUnalloc_samp(sm,s_id);
2172	<	return(n_id);
2167	>	if(r_id != INVALID)
2168	>	{
2169	>	smRemoveVertex(sm,r_id);
2170	>	if(nbr_id == r_id)
2171	>	{
2172	>	qtremovelast(qt,s_id);
2173	>	SM_S_NTH_QT(sm,s_id) = EMPTY;
2174	>	}
2175	>	}
2176	>	else
2177	>	break;
2178		}
1556	–	if((!(smTest_sample(sm,t_id,dir,p,&r_id))))
1557	–	{
1558	–	smUnalloc_samp(sm,s_id);
1559	–	return(INVALID);
1560	–	}
2179		/* If sample is being added in the middle of the sample array: tone
2180		map individually
2181		*/
2182	+	/* If not base or sky point, add distance from center to average*/
2183	+	smDist_sum += 1.0/ds;
2184		/* Initialize sample */
2185	<	sInit_samp(SM_SAMP(sm),s_id,c,dir,p,o_id,(SM_TONE_MAP(sm)>s_id));
2186	<
2185	>	sInit_samp(SM_SAMP(sm),s_id,c,dir,p,o_id);
2186	>	smInsert_samp_mesh(sm,s_id,t_id,ns,n0,n1,n2,on,which);
2187		}
2188		/* If sample is a direction vector */
2189		else
2190		{
2191		VADD(wpt,dir,SM_VIEW_CENTER(sm));
2192	<	t_id = smPointLocateTri(sm,wpt,&on,&which);
2193	<	if(t_id == INVALID)
2194	<	{
2192	>	/* Allocate space for a sample and initialize */
2193	>	while(1)
2194	>	{
2195	>	t_id = smSample_locate_tri(sm,dir,s_id,&on,&which,&nbr_id);
2196	>	qt = SM_S_NTH_QT(sm,s_id);
2197		#ifdef DEBUG
2198	<	eputs("smAddSamp(): unable to locate tri containing sample \n");
2198	>	if(t_id == INVALID)
2199	>	{
2200	>	eputs("smAddSamp():can't locate tri containing samp\n");
2201	>	smUnalloc_samp(sm,s_id);
2202	>	qtremovelast(qt,s_id);
2203	>	return(INVALID);
2204	>	}
2205		#endif
2206	+	if(on == ON_V)
2207	+	{
2208		smUnalloc_samp(sm,s_id);
2209	+	qtremovelast(qt,s_id);
2210		return(INVALID);
2211		}
2212	<	if(on == ON_V || on == ON_P)
2213	<	{
2214	<	if((n_id = smReplace_samp(sm,c,wpt,NULL,s_id,t_id,o_id,on,which))!= s_id)
2215	<	smUnalloc_samp(sm,s_id);
2216	<	return(n_id);
2212	>	t = SM_NTH_TRI(sm,t_id);
2213	>	VSUB(n0,SM_NTH_WV(sm,T_NTH_V(t,0)),SM_VIEW_CENTER(sm));
2214	>	d0 = normalize(n0);
2215	>	VSUB(n1,SM_NTH_WV(sm,T_NTH_V(t,1)),SM_VIEW_CENTER(sm));
2216	>	normalize(n1);
2217	>	VSUB(n2,SM_NTH_WV(sm,T_NTH_V(t,2)),SM_VIEW_CENTER(sm));
2218	>	normalize(n2);
2219	>	if(!smTest_samp(sm,t_id,NULL,wpt,&r_id,dir,n0,n1,n2,1.0,d0,on,which))
2220	>	{
2221	>	smUnalloc_samp(sm,s_id);
2222	>	qtremovelast(qt,s_id);
2223	>	return(INVALID);
2224	>	}
2225	>	if(r_id != INVALID)
2226	>	{
2227	>	smRemoveVertex(sm,r_id);
2228	>	if(nbr_id == r_id)
2229	>	{
2230	>	qtremovelast(qt,s_id);
2231	>	SM_S_NTH_QT(sm,s_id) = EMPTY;
2232	>	}
2233	>	}
2234	>	else
2235	>	break;
2236	>	}
2237	>	sInit_samp(SM_SAMP(sm),s_id,c,NULL,wpt,o_id);
2238	>	smInsert_samp_mesh(sm,s_id,t_id,dir,n0,n1,n2,on,which);
2239		}
1587	–	/* Allocate space for a sample and initialize */
1588	–	sInit_samp(SM_SAMP(sm),s_id,c,wpt,NULL,o_id,(SM_TONE_MAP(sm)>s_id));
1589	–	}
1590	–	if(!SM_DIR_ID(sm,s_id))
1591	–	{
1592	–	/* If not a base or sky point, add distance from the
1593	–	viewcenter to average*/
1594	–	d = DIST(SM_NTH_WV(sm,s_id),SM_VIEW_CENTER(sm));
1595	–	smDist_sum += 1.0/d;
1596	–	}
1597	–	smInsert_samp(sm,s_id,t_id,on,which);
1598	–
1599	–	/* If new sample replaces existing one- remove that vertex now */
1600	–	if(r_id != INVALID)
1601	–	{
1602	–	smRemoveVertex(sm,r_id);
1603	–	sDelete_samp(SM_SAMP(sm),r_id);
1604	–	}
2240		return(s_id);
2241		}
2242
#	Line 1616 | Line 2251 | smAdd_samp(sm,c,dir,p,o_id)
2251		* New sample representation will be output in next call to smUpdate().
2252		* If the point is a sky point: then v=NULL
2253		*/
2254	+	#define FVECT_TO_SFLOAT(p) \
2255	+	(p[0]=(SFLOAT)p[0],p[1]=(SFLOAT)p[1],p[2]=(SFLOAT)p[2])
2256		int
2257		smNewSamp(c,dir,p)
2258		COLR c;
2259		FVECT dir;
2260		FVECT p;
2261		{
2262	<	int s_id;
2262	>	S_ID s_id;
2263
1627	–
2264		/* First check if this the first sample: if so initialize mesh */
1629	–
2265		if(SM_NUM_SAMP(smMesh) == 0)
2266		{
2267		smInit_sm(smMesh,odev.v.vp);
2268		sClear_all_flags(SM_SAMP(smMesh));
2269		}
2270	+	FVECT_TO_SFLOAT(p);
2271	+	FVECT_TO_SFLOAT(dir);
2272		/* Add the sample to the mesh */
2273		s_id = smAdd_samp(smMesh,c,dir,p,INVALID);
2274
2275	<	return(s_id);
2275	>	return((int)s_id);
2276
2277		}
2278	<	int
2278	>	S_ID
2279		smAdd_base_vertex(sm,v)
2280		SM *sm;
2281		FVECT v;
2282		{
2283	<	int id;
2283	>	S_ID id;
2284
2285		/* First add coordinate to the sample array */
2286		id = sAdd_base_point(SM_SAMP(sm),v);
#	Line 1667 | Line 2304 | SM *sm;
2304		int type;
2305		{
2306		int i,s_id,tri_id,nbr_id;
2307	<	int p[SM_EXTRA_POINTS],ids[SM_BASE_TRIS];
2308	<	int v0_id,v1_id,v2_id;
2307	>	S_ID p[SM_BASE_POINTS];
2308	>	int ids[SM_BASE_TRIS];
2309	>	S_ID v0_id,v1_id,v2_id;
2310		FVECT d,pt,cntr,v0,v1,v2;
2311		TRI *t;
2312
2313		/* First insert the base vertices into the sample point array */
2314	<
1677	<	for(i=0; i < SM_EXTRA_POINTS; i++)
2314	>	for(i=0; i < SM_BASE_POINTS; i++)
2315		{
2316		VADD(cntr,icosa_verts[i],SM_VIEW_CENTER(sm));
2317		p[i]  = smAdd_base_vertex(sm,cntr);
2318	+	smInsert_samp(sm,p[i],icosa_verts[i],NULL);
2319		}
2320		/* Create the base triangles */
2321		for(i=0;i < SM_BASE_TRIS; i++)
#	Line 1685 | Line 2323 | int type;
2323		v0_id = p[icosa_tris[i][0]];
2324		v1_id = p[icosa_tris[i][1]];
2325		v2_id = p[icosa_tris[i][2]];
2326	<	ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id);
2326	>	ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id,&t);
2327		/* Set neighbors */
2328		for(nbr_id=0; nbr_id < 3; nbr_id++)
2329		T_NTH_NBR(SM_NTH_TRI(sm,ids[i]),nbr_id) = icosa_nbrs[i][nbr_id];
2330
2331		}
1694	–	for(i=0;i < SM_BASE_TRIS; i++)
1695	–	{
1696	–	t = SM_NTH_TRI(sm,ids[i]);
1697	–	smLocator_add_tri(sm,ids[i],T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2));
1698	–	}
2332		return(1);
2333
2334		}
2335
2336	<
1704	<	int
1705	<	smNext_tri_flag_set(sm,i,which,b)
1706	<	SM *sm;
1707	<	int i,which;
1708	<	int b;
1709	<	{
1710	<
1711	<	for(; i < SM_NUM_TRI(sm);i++)
1712	<	{
1713	<
1714	<	if(!T_IS_VALID(SM_NTH_TRI(sm,i)))
1715	<	continue;
1716	<	if(!SM_IS_NTH_T_FLAG(sm,i,which))
1717	<	continue;
1718	<	if(!b)
1719	<	break;
1720	<	if((b==1) && !SM_BG_TRI(sm,i))
1721	<	break;
1722	<	if((b==2) && SM_BG_TRI(sm,i))
1723	<	break;
1724	<	}
1725	<
1726	<	return(i);
1727	<	}
1728	<
1729	<
1730	<	int
1731	<	smNext_valid_tri(sm,i)
1732	<	SM *sm;
1733	<	int i;
1734	<	{
1735	<
1736	<	while( i < SM_NUM_TRI(sm) && !T_IS_VALID(SM_NTH_TRI(sm,i)))
1737	<	i++;
1738	<
1739	<	return(i);
1740	<	}
1741	<
1742	<
1743	<
1744	<	qtTri_from_id(t_id,v0,v1,v2)
1745	<	int t_id;
1746	<	FVECT v0,v1,v2;
1747	<	{
1748	<	TRI *t;
1749	<
1750	<	t = SM_NTH_TRI(smMesh,t_id);
1751	<	if(!T_IS_VALID(t))
1752	<	return(0);
1753	<	VSUB(v0,SM_T_NTH_WV(smMesh,t,0),SM_VIEW_CENTER(smMesh));
1754	<	VSUB(v1,SM_T_NTH_WV(smMesh,t,1),SM_VIEW_CENTER(smMesh));
1755	<	VSUB(v2,SM_T_NTH_WV(smMesh,t,2),SM_VIEW_CENTER(smMesh));
1756	<	return(1);
1757	<	}
1758	<
1759	<
1760	<	smRebuild_mesh(sm,v)
2336	>	smRebuild(sm,v)
2337		SM *sm;
2338		VIEW *v;
2339		{
2340	<	int i,j,cnt;
2340	>	S_ID s_id;
2341	>	int j,cnt;
2342		FVECT p,ov,dir;
2343		double d;
2344
2345		#ifdef DEBUG
2346	<	fprintf(stderr,"smRebuild_mesh(): rebuilding....");
2346	>	fprintf(stderr,"smRebuild(): rebuilding....");
2347		#endif
2348	+	smCull(sm,v,SM_ALL_LEVELS);
2349		/* Clear the mesh- and rebuild using the current sample array */
2350		/* Remember the current number of samples */
2351		cnt = SM_NUM_SAMP(sm);
2352		/* Calculate the difference between the current and new viewpoint*/
2353		/* Will need to subtract this off of sky points */
2354		VCOPY(ov,SM_VIEW_CENTER(sm));
1777	–	/* Initialize the mesh to 0 samples and the base triangles */
2355
2356	+	/* Initialize the mesh to 0 samples and the base triangles */
2357	+	smInit_sm(sm,v->vp);
2358		/* Go through all samples and add in if in the new view frustum, and
2359		the dir is <= 30 degrees from new view
2360		*/
2361	<	smInit_sm(sm,v->vp);
1783	<	for(i=0; i < cnt; i++)
2361	>	for(s_id=0; s_id < cnt; s_id++)
2362		{
2363		/* First check if sample visible(conservative approx: if one of tris
2364		attached to sample is in frustum)       */
2365	<	if(!S_IS_FLAG(i))
2365	>	if(!S_IS_FLAG(s_id))
2366		continue;
2367	<
2368	<	/* Next test if direction > 30 from current direction */
2369	<	if(SM_NTH_W_DIR(sm,i)!=-1)
2367	>
2368	>	/* Next test if direction > 30 degrees from current direction */
2369	>	if(SM_NTH_W_DIR(sm,s_id)!=-1)
2370		{
2371	<	VSUB(p,SM_NTH_WV(sm,i),v->vp);
2372	<	normalize(p);
2373	<	decodedir(dir,SM_NTH_W_DIR(sm,i));
2374	<	d = 2. - 2.*DOT(dir,p);
1797	<	if (d > MAXDIFF2)
2371	>	VSUB(p,SM_NTH_WV(sm,s_id),v->vp);
2372	>	decodedir(dir,SM_NTH_W_DIR(sm,s_id));
2373	>	d = DOT(dir,p);
2374	>	if (d*d < MAXDIFF2*DOT(p,p))
2375		continue;
2376	<	VCOPY(p,SM_NTH_WV(sm,i));
2377	<	smAdd_samp(sm,NULL,dir,p,i);
2376	>	VCOPY(p,SM_NTH_WV(sm,s_id));
2377	>	smAdd_samp(sm,NULL,dir,p,s_id);
2378		}
2379		else
2380		{
2381	<	VSUB(dir,SM_NTH_WV(sm,i),ov);
2382	<	VADD(SM_NTH_WV(sm,i),dir,SM_VIEW_CENTER(sm));
2383	<	smAdd_samp(sm,NULL,dir,NULL,i);
2381	>	/* If the direction is > 45 degrees from current view direction:
2382	>	throw out
2383	>	*/
2384	>	VSUB(dir,SM_NTH_WV(sm,s_id),ov);
2385	>	if(DOT(dir,v->vdir) < MAXDIR)
2386	>	continue;
2387	>
2388	>	VADD(SM_NTH_WV(sm,s_id),dir,SM_VIEW_CENTER(sm));
2389	>	smAdd_samp(sm,NULL,dir,NULL,s_id);
2390		}
2391
2392		}
1810	–
1811	–	smNew_tri_cnt = SM_SAMPLE_TRIS(sm);
2393		#ifdef DEBUG
2394	<	fprintf(stderr,"smRebuild_mesh():done\n");
2394	>	fprintf(stderr,"smRebuild():done\n");
2395		#endif
2396		}
2397
1817	–	int
1818	–	intersect_tri_set(t_set,orig,dir,pt)
1819	–	OBJECT *t_set;
1820	–	FVECT orig,dir,pt;
1821	–	{
1822	–	OBJECT *optr;
1823	–	int i,t_id,id,base;
1824	–	int pid0,pid1,pid2;
1825	–	FVECT p0,p1,p2,p;
1826	–	TRI *t;
1827	–	double d,d1;
1828	–
1829	–	optr = QT_SET_PTR(t_set);
1830	–	for(i = QT_SET_CNT(t_set); i > 0; i--)
1831	–	{
1832	–	t_id = QT_SET_NEXT_ELEM(optr);
1833	–	t = SM_NTH_TRI(smMesh,t_id);
1834	–	if(!T_IS_VALID(t))
1835	–	continue;
1836	–	pid0 = T_NTH_V(t,0);
1837	–	pid1 = T_NTH_V(t,1);
1838	–	pid2 = T_NTH_V(t,2);
1839	–	if(base = SM_IS_NTH_T_BASE(smMesh,t_id))
1840	–	if(SM_BASE_ID(smMesh,pid0) && SM_BASE_ID(smMesh,pid1) &&
1841	–	SM_BASE_ID(smMesh,pid2))
1842	–	continue;
1843	–	VCOPY(p0,SM_NTH_WV(smMesh,pid0));
1844	–	VCOPY(p1,SM_NTH_WV(smMesh,pid1));
1845	–	VCOPY(p2,SM_NTH_WV(smMesh,pid2));
1846	–	if(ray_intersect_tri(orig,dir,p0,p1,p2,p))
1847	–	{
1848	–	if(!base)
1849	–	{
1850	–	d =  DIST_SQ(p,p0);
1851	–	d1 = DIST_SQ(p,p1);
1852	–	if(d < d1)
1853	–	{
1854	–	d1 = DIST_SQ(p,p2);
1855	–	id = (d1 < d)?pid2:pid0;
1856	–	}
1857	–	else
1858	–	{
1859	–	d = DIST_SQ(p,p2);
1860	–	id = (d < d1)? pid2:pid1;
1861	–	}
1862	–	}
1863	–	else
1864	–	{
1865	–	if(SM_BASE_ID(smMesh,pid0))
1866	–	{
1867	–	if(SM_BASE_ID(smMesh,pid1))
1868	–	id = pid2;
1869	–	else
1870	–	if(SM_BASE_ID(smMesh,pid2))
1871	–	id = pid1;
1872	–	else
1873	–	{
1874	–	d =  DIST_SQ(p,p1);
1875	–	d1 = DIST_SQ(p,p2);
1876	–	if(d < d1)
1877	–	id = pid1;
1878	–	else
1879	–	id = pid2;
1880	–	}
1881	–	}
1882	–	else
1883	–	{
1884	–	if(SM_BASE_ID(smMesh,pid1))
1885	–	{
1886	–	if(SM_BASE_ID(smMesh,pid2))
1887	–	id = pid0;
1888	–	else
1889	–	{
1890	–	d =  DIST_SQ(p,p0);
1891	–	d1 = DIST_SQ(p,p2);
1892	–	if(d < d1)
1893	–	id = pid0;
1894	–	else
1895	–	id = pid2;
1896	–	}
1897	–	}
1898	–	else
1899	–	{
1900	–	d =  DIST_SQ(p,p0);
1901	–	d1 = DIST_SQ(p,p1);
1902	–	if(d < d1)
1903	–	id = pid0;
1904	–	else
1905	–	id = pid1;
1906	–	}
1907	–	}
1908	–	}
1909	–	if(pt)
1910	–	VCOPY(pt,p);
1911	–	#ifdef TEST_DRIVER
1912	–	Pick_tri = t_id;
1913	–	Pick_samp = id;
1914	–	VCOPY(Pick_point[0],p);
1915	–	#endif
1916	–	return(id);
1917	–	}
1918	–	}
1919	–	return(-1);
1920	–	}
1921	–
2398		/* OS is constrained to be <= QT_MAXCSET : if the set exceeds this, the
2399		results of check_set are conservative
2400		*/
2401		int
2402		compare_ids(id1,id2)
2403	<	OBJECT *id1,*id2;
2403	>	S_ID *id1,*id2;
2404		{
2405		int d;
2406
#	Line 1938 | Line 2414 | OBJECT *id1,*id2;
2414		return(0);
2415		}
2416
1941	–	ray_trace_check_set(qt,argptr,fptr)
1942	–	QUADTREE qt;
1943	–	RT_ARGS *argptr;
1944	–	int *fptr;
1945	–	{
1946	–	OBJECT tset[QT_MAXSET+1],*tptr;
1947	–	double dt,t;
1948	–	int found;
1949	–	if(QT_IS_EMPTY(qt))
1950	–	return;
1951	–	if(QT_LEAF_IS_FLAG(qt))
1952	–	{
1953	–	QT_FLAG_SET_DONE(*fptr);
1954	–	#if DEBUG
1955	–	eputs("ray_trace_check_set():Already visited this node:aborting\n");
1956	–	#endif
1957	–	return;
1958	–	}
1959	–	else
1960	–	QT_LEAF_SET_FLAG(qt);
2417
2418	<	tptr = qtqueryset(qt);
2419	<	if(QT_SET_CNT(tptr) > QT_MAXSET)
2420	<	tptr = (OBJECT *)malloc((QT_SET_CNT(tptr)+1)*sizeof(OBJECT));
2421	<	else
2422	<	tptr = tset;
1967	<	if(!tptr)
1968	<	goto memerr;
1969	<
1970	<	qtgetset(tptr,qt);
1971	<	/* Must sort */
1972	<	qsort((void *)(&(tptr[1])),tptr[0],sizeof(OBJECT),compare_ids);
1973	<	/* Check triangles in set against those seen so far(os):only
1974	<	check new triangles for intersection (t_set')
1975	<	*/
1976	<	check_set_large(tptr,argptr->os);
1977	<
1978	<	if(!QT_SET_CNT(tptr))
1979	<	return;
1980	<	found = intersect_tri_set(tptr,argptr->orig,argptr->dir,NULL);
1981	<	if(tptr != tset)
1982	<	free(tptr);
1983	<	if(found != INVALID)
1984	<	{
1985	<	argptr->t_id = found;
1986	<	QT_FLAG_SET_DONE(*fptr);
1987	<	}
1988	<	return;
1989	<	memerr:
1990	<	error(SYSTEM,"ray_trace_check_set():Unable to allocate memory");
1991	<	}
1992	<
1993	<
1994	<	/*
1995	<	* int
1996	<	* smFindSamp(FVECT orig, FVECT dir)
1997	<	*
1998	<	* Find the closest sample to the given ray.  Returns sample id, -1 on failure.
1999	<	* "dir" is assumed to be normalized
2000	<	*/
2001	<
2002	<	int
2003	<	smFindSamp(orig,dir)
2004	<	FVECT orig,dir;
2418	>	null_func(argptr,root,qt,n)
2419	>	int *argptr;
2420	>	int root;
2421	>	QUADTREE qt;
2422	>	int n;
2423		{
2424	<	FVECT b,p,o;
2007	<	OBJECT *ts;
2008	<	QUADTREE qt;
2009	<	int s_id,test;
2010	<	double d;
2011	<
2012	<	/*  r is the normalized vector from the view center to the current
2013	<	*  ray point ( starting with "orig"). Find the cell that r falls in,
2014	<	*  and test the ray against all triangles stored in the cell. If
2015	<	*  the test fails, trace the projection of the ray across to the
2016	<	*  next cell it intersects: iterate until either an intersection
2017	<	*  is found, or the projection ray is // to the direction. The sample
2018	<	*  corresponding to the triangle vertex closest to the intersection
2019	<	*  point is returned.
2020	<	*/
2021	<
2022	<	/* First test if "orig" coincides with the View_center or if "dir" is
2023	<	parallel to r formed by projecting "orig" on the sphere. In
2024	<	either case, do a single test against the cell containing the
2025	<	intersection of "dir" and the sphere
2026	<	*/
2027	<	/* orig will be updated-so preserve original value */
2028	<	if(!smMesh)
2029	<	return;
2030	<	#ifdef TEST_DRIVER
2031	<	Picking= TRUE;
2032	<	#endif
2033	<
2034	<	if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh)))
2035	<	{
2036	<	qt = smPointLocateCell(smMesh,dir);
2037	<	if(QT_IS_EMPTY(qt))
2038	<	goto Lerror;
2039	<	ts = qtqueryset(qt);
2040	<	s_id = intersect_tri_set(ts,orig,dir,p);
2041	<	#ifdef DEBUG_TEST_DRIVER
2042	<	VCOPY(Pick_point[0],p);
2043	<	#endif
2044	<	#ifdef DEBUG
2045	<	fprintf(stderr,"Simple pick returning %d\n",s_id);
2046	<	#endif
2047	<
2048	<	return(s_id);
2049	<	}
2050	<	d = point_on_sphere(b,orig,SM_VIEW_CENTER(smMesh));
2051	<	if(EQUAL_VEC3(b,dir))
2052	<	{
2053	<	qt = smPointLocateCell(smMesh,dir);
2054	<	if(QT_IS_EMPTY(qt))
2055	<	goto Lerror;
2056	<	ts = qtqueryset(qt);
2057	<	s_id = intersect_tri_set(ts,orig,dir,p);
2058	<	#ifdef DEBUG_TEST_DRIVER
2059	<	VCOPY(Pick_point[0],p);
2060	<	#endif
2061	<	#ifdef DEBUG
2062	<	fprintf(stderr,"Simple pick2 returning %d\n",s_id);
2063	<	#endif
2064	<	return(s_id);
2065	<	}
2066	<	if(OPP_EQUAL_VEC3(b,dir))
2067	<	{
2068	<	qt = smPointLocateCell(smMesh,orig);
2069	<	if(QT_IS_EMPTY(qt))
2070	<	goto Lerror;
2071	<	ts = qtqueryset(qt);
2072	<	s_id = intersect_tri_set(ts,orig,dir,p);
2073	<	#ifdef DEBUG_TEST_DRIVER
2074	<	VCOPY(Pick_point[0],p);
2075	<	#endif
2076	<	if(s_id != INVALID)
2077	<	{
2078	<	#ifdef DEBUG
2079	<	fprintf(stderr,"Front pick returning %d\n",s_id);
2080	<	#endif
2081	<	return(s_id);
2082	<	}
2083	<	qt = smPointLocateCell(smMesh,dir);
2084	<	if(QT_IS_EMPTY(qt))
2085	<	goto Lerror;
2086	<	ts = qtqueryset(qt);
2087	<	s_id = intersect_tri_set(ts,orig,dir,p);
2088	<	#ifdef DEBUG_TEST_DRIVER
2089	<	VCOPY(Pick_point[0],p);
2090	<	#endif
2091	<	#ifdef DEBUG
2092	<	fprintf(stderr,"Back pick returning %d\n",s_id);
2093	<	#endif
2094	<	return(s_id);
2095	<	}
2096	<	{
2097	<	OBJECT t_set[QT_MAXCSET + 1];
2098	<	RT_ARGS rt;
2099	<	FUNC func;
2100	<
2101	<	/* Test each of the root triangles against point id */
2102	<	QT_CLEAR_SET(t_set);
2103	<	VSUB(o,orig,SM_VIEW_CENTER(smMesh));
2104	<	ST_CLEAR_FLAGS(SM_LOCATOR(smMesh));
2105	<	rt.t_id = -1;
2106	<	rt.os = t_set;
2107	<	VCOPY(rt.orig,orig);
2108	<	VCOPY(rt.dir,dir);
2109	<	F_FUNC(func) = ray_trace_check_set;
2110	<	F_ARGS(func) = (int *)(&rt);
2111	<	stTrace_ray(SM_LOCATOR(smMesh),o,dir,func);
2112	<	s_id = rt.t_id;
2113	<	}
2114	<	#ifdef DEBUG
2115	<	fprintf(stderr,"Trace pick returning %d\n",s_id);
2116	<	#endif
2117	<	return(s_id);
2118	<
2119	<	Lerror:
2120	<	#ifdef DEBUG
2121	<	eputs("smFindSamp(): point not found");
2122	<	#endif
2123	<	return(INVALID);
2124	<
2424	>	/* do nothing */
2425		}
2426
2427	<
2128	<	mark_active_tris(argptr,root,qt)
2427	>	mark_active_samples(argptr,root,qt,n)
2428		int *argptr;
2429		int root;
2430		QUADTREE qt;
2431	+	int n;
2432		{
2433	<	OBJECT *os,*optr;
2434	<	register int i,t_id;
2433	>	S_ID *os,s_id;
2434	>	register int i,t_id,tri_id;
2435		TRI *tri;
2436
2437		if(QT_IS_EMPTY(qt) || QT_LEAF_IS_FLAG(qt))
#	Line 2140 | Line 2440 | mark_active_tris(argptr,root,qt)
2440		/* For each triangle in the set, set the which flag*/
2441		os = qtqueryset(qt);
2442
2443	<	for (i = QT_SET_CNT(os), optr = QT_SET_PTR(os); i > 0; i--)
2443	>	for (i = QT_SET_CNT(os); i > 0; i--)
2444		{
2445	<	t_id = QT_SET_NEXT_ELEM(optr);
2446	<	/* Set the render flag */
2147	<	tri = SM_NTH_TRI(smMesh,t_id);
2148	<	if(!T_IS_VALID(tri) ||  SM_IS_NTH_T_BASE(smMesh,t_id))
2149	<	continue;
2150	<	SM_SET_NTH_T_ACTIVE(smMesh,t_id);
2151	<	/* Set the Active bits of the Vertices */
2152	<	S_SET_FLAG(T_NTH_V(tri,0));
2153	<	S_SET_FLAG(T_NTH_V(tri,1));
2154	<	S_SET_FLAG(T_NTH_V(tri,2));
2155	<	}
2156	<	}
2445	>	s_id = QT_SET_NEXT_ELEM(os);
2446	>	S_SET_FLAG(s_id);
2447
2448	+	tri_id = SM_NTH_VERT(smMesh,s_id);
2449	+	/* Set the active flag for all adjacent triangles */
2450	+	tri = SM_NTH_TRI(smMesh,tri_id);
2451	+	SM_SET_NTH_T_ACTIVE(smMesh,tri_id);
2452	+	while((t_id = smTri_next_ccw_nbr(smMesh,tri,s_id)) != tri_id)
2453	+	{
2454	+	tri = SM_NTH_TRI(smMesh,t_id);
2455	+	SM_SET_NTH_T_ACTIVE(smMesh,t_id);
2456	+	}
2457	+	}
2458	+	}
2459
2460	<	mark_tris_in_frustum(view)
2460	>	smCull(sm,view,n)
2461	>	SM *sm;
2462		VIEW *view;
2463	+	int n;
2464		{
2465		FVECT nr[4],far[4];
2466		FPEQ peq;
2467		int debug=0;
2468		FUNC f;
2469
2470	<	F_FUNC(f) = mark_active_tris;
2471	<	F_ARGS(f) = NULL;
2470	>	/* First clear all the quadtree node flags */
2471	>	qtClearAllFlags();
2472
2473	+	F_ARGS(f) = NULL;
2474	+	/* If marking samples down to leaves */
2475	+	if(n == SM_ALL_LEVELS)
2476	+	{
2477		/* Mark triangles in approx. view frustum as being active:set
2478		LRU counter: for use in discarding samples when out
2479		of space
2480	+	*/
2481	+	F_FUNC(f) = mark_active_samples;
2482	+	smClear_flags(sm,T_ACTIVE_FLAG);
2483	+	/* Clear all of the active sample flags*/
2484	+	sClear_all_flags(SM_SAMP(sm));
2485	+	}
2486	+	else
2487	+	/* Just mark qtree flags */
2488	+	F_FUNC(f) = null_func;
2489	+
2490	+	/* calculate the world space coordinates of the view frustum:
2491		Radiance often has no far clipping plane: but driver will set
2492		dev_zmin,dev_zmax to satisfy OGL
2493	<	*/
2176	<
2177	<	/* First clear all the quadtree node and triangle active flags */
2178	<	qtClearAllFlags();
2179	<	smClear_flags(smMesh,T_ACTIVE_FLAG);
2180	<	/* Clear all of the active sample flags*/
2181	<	sClear_all_flags(SM_SAMP(smMesh));
2182	<
2183	<
2184	<	/* calculate the world space coordinates of the view frustum */
2493	>	*/
2494		calculate_view_frustum(view->vp,view->hvec,view->vvec,view->horiz,
2495		view->vert, dev_zmin,dev_zmax,nr,far);
2496
#	Line 2202 | Line 2511 | mark_tris_in_frustum(view)
2511		Also set the triangles LRU clock counter
2512		*/
2513
2514	<	if(EQUAL_VEC3(view->vp,SM_VIEW_CENTER(smMesh)))
2514	>	if(EQUAL_VEC3(view->vp,SM_VIEW_CENTER(sm)))
2515		{/* Near face triangles */
2516
2517	<	smLocator_apply(smMesh,nr[0],nr[2],nr[3],f);
2518	<	smLocator_apply(smMesh,nr[2],nr[0],nr[1],f);
2517	>	smLocator_apply(sm,nr[0],nr[2],nr[3],f,n);
2518	>	smLocator_apply(sm,nr[2],nr[0],nr[1],f,n);
2519		return;
2520		}
2521		/* Test the view against the planes: and swap orientation if inside:*/
2522		tri_plane_equation(nr[0],nr[2],nr[3], &peq,FALSE);
2523	<	if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0)
2523	>	if(PT_ON_PLANE(SM_VIEW_CENTER(sm),peq) < 0.0)
2524		{/* Near face triangles */
2525	<	smLocator_apply(smMesh,nr[3],nr[2],nr[0],f);
2526	<	smLocator_apply(smMesh,nr[1],nr[0],nr[2],f);
2525	>	smLocator_apply(sm,nr[3],nr[2],nr[0],f,n);
2526	>	smLocator_apply(sm,nr[1],nr[0],nr[2],f,n);
2527		}
2528		else
2529		{/* Near face triangles */
2530	<	smLocator_apply(smMesh,nr[0],nr[2],nr[3],f);
2531	<	smLocator_apply(smMesh,nr[2],nr[0],nr[1],f);
2530	>	smLocator_apply(sm,nr[0],nr[2],nr[3],f,n);
2531	>	smLocator_apply(sm,nr[2],nr[0],nr[1],f,n);
2532		}
2533		tri_plane_equation(nr[0],far[3],far[0], &peq,FALSE);
2534	<	if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0)
2534	>	if(PT_ON_PLANE(SM_VIEW_CENTER(sm),peq) < 0.0)
2535		{ /* Right face triangles */
2536	<	smLocator_apply(smMesh,far[0],far[3],nr[0],f);
2537	<	smLocator_apply(smMesh,nr[3],nr[0],far[3],f);
2536	>	smLocator_apply(sm,far[0],far[3],nr[0],f,n);
2537	>	smLocator_apply(sm,nr[3],nr[0],far[3],f,n);
2538		}
2539		else
2540		{/* Right face triangles */
2541	<	smLocator_apply(smMesh,nr[0],far[3],far[0],f);
2542	<	smLocator_apply(smMesh,far[3],nr[0],nr[3],f);
2541	>	smLocator_apply(sm,nr[0],far[3],far[0],f,n);
2542	>	smLocator_apply(sm,far[3],nr[0],nr[3],f,n);
2543		}
2544
2545		tri_plane_equation(nr[1],far[2],nr[2], &peq,FALSE);
2546		if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0)
2547		{ /* Left face triangles */
2548	<	smLocator_apply(smMesh,nr[2],far[2],nr[1],f);
2549	<	smLocator_apply(smMesh,far[1],nr[1],far[2],f);
2548	>	smLocator_apply(sm,nr[2],far[2],nr[1],f,n);
2549	>	smLocator_apply(sm,far[1],nr[1],far[2],f,n);
2550		}
2551		else
2552		{ /* Left face triangles */
2553	<	smLocator_apply(smMesh,nr[1],far[2],nr[2],f);
2554	<	smLocator_apply(smMesh,far[2],nr[1],far[1],f);
2553	>	smLocator_apply(sm,nr[1],far[2],nr[2],f,n);
2554	>	smLocator_apply(sm,far[2],nr[1],far[1],f,n);
2555		}
2556		tri_plane_equation(nr[0],far[0],nr[1], &peq,FALSE);
2557	<	if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0)
2557	>	if(PT_ON_PLANE(SM_VIEW_CENTER(sm),peq) < 0.0)
2558		{/* Top face triangles */
2559	<	smLocator_apply(smMesh,nr[1],far[0],nr[0],f);
2560	<	smLocator_apply(smMesh,far[1],far[0],nr[1],f);
2559	>	smLocator_apply(sm,nr[1],far[0],nr[0],f,n);
2560	>	smLocator_apply(sm,far[1],far[0],nr[1],f,n);
2561		}
2562		else
2563		{/* Top face triangles */
2564	<	smLocator_apply(smMesh,nr[0],far[0],nr[1],f);
2565	<	smLocator_apply(smMesh,nr[1],far[0],far[1],f);
2564	>	smLocator_apply(sm,nr[0],far[0],nr[1],f,n);
2565	>	smLocator_apply(sm,nr[1],far[0],far[1],f,n);
2566		}
2567		tri_plane_equation(nr[3],nr[2],far[3], &peq,FALSE);
2568	<	if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0)
2568	>	if(PT_ON_PLANE(SM_VIEW_CENTER(sm),peq) < 0.0)
2569		{/* Bottom face triangles */
2570	<	smLocator_apply(smMesh,far[3],nr[2],nr[3],f);
2571	<	smLocator_apply(smMesh,far[3],far[2],nr[2],f);
2570	>	smLocator_apply(sm,far[3],nr[2],nr[3],f,n);
2571	>	smLocator_apply(sm,far[3],far[2],nr[2],f,n);
2572		}
2573		else
2574		{ /* Bottom face triangles */
2575	<	smLocator_apply(smMesh,nr[3],nr[2],far[3],f);
2576	<	smLocator_apply(smMesh,nr[2],far[2],far[3],f);
2575	>	smLocator_apply(sm,nr[3],nr[2],far[3],f,n);
2576	>	smLocator_apply(sm,nr[2],far[2],far[3],f,n);
2577		}
2578		tri_plane_equation(far[2],far[0],far[1], &peq,FALSE);
2579	<	if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0)
2579	>	if(PT_ON_PLANE(SM_VIEW_CENTER(sm),peq) < 0.0)
2580		{/* Far face triangles */
2581	<	smLocator_apply(smMesh,far[0],far[2],far[1],f);
2582	<	smLocator_apply(smMesh,far[2],far[0],far[3],f);
2581	>	smLocator_apply(sm,far[0],far[2],far[1],f,n);
2582	>	smLocator_apply(sm,far[2],far[0],far[3],f,n);
2583		}
2584		else
2585		{/* Far face triangles */
2586	<	smLocator_apply(smMesh,far[1],far[2],far[0],f);
2587	<	smLocator_apply(smMesh,far[3],far[0],far[2],f);
2586	>	smLocator_apply(sm,far[1],far[2],far[0],f,n);
2587	>	smLocator_apply(sm,far[3],far[0],far[2],f,n);
2588		}
2589
2590		}
2591	+
2592	+
2593	+
2594	+
2595	+
2596	+
2597	+
2598	+
2599	+
2600	+
2601
2602
2603

Diff Legend

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