ViewVC Help

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

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

Comparing ray/src/hd/sm_qtree.c (file contents):
Revision 3.10 by gwlarson, Tue Jan 5 16:52:39 1999 UTC vs.
Revision 3.14 by greg, Sat Feb 22 02:07:25 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_qtree.c: adapted from octree.c from radiance code
6		*/
#	Line 16 | Line 13 | static char SCCSid[] = "$SunId$ SGI";
13		#include "standard.h"
14		#include "sm_flag.h"
15		#include "sm_geom.h"
16	+	#include "object.h"
17		#include "sm_qtree.h"
18
19	<	QUADTREE  *quad_block[QT_MAX_BLK];              /* our quadtree */
19	>	QUADTREE  *quad_block[QT_MAX_BLK];        /* our quadtree */
20		static QUADTREE  quad_free_list = EMPTY;  /* freed octree nodes */
21	<	static QUADTREE  treetop = 0;           /* next free node */
22	<	int4 *quad_flag= NULL;
21	>	static QUADTREE  treetop = 0;             /* next free node */
22	>	int4 *quad_flag= NULL;                    /* quadtree flags */
23
26	–	#ifdef TEST_DRIVER
27	–	extern FVECT Pick_v0[500],Pick_v1[500],Pick_v2[500];
28	–	extern int Pick_cnt,Pick_tri,Pick_samp;
29	–	extern FVECT Pick_point[500];
30	–	extern int Pick_q[500];
24
25	+	qtremovelast(qt,id)
26	+	QUADTREE qt;
27	+	OBJECT id;
28	+	{
29	+	#ifdef DEBUG
30	+	if(qtqueryset(qt)[(*(qtqueryset(qt)))] != id)
31	+	error(CONSISTENCY,"not removed\n");
32		#endif
33	<	int Incnt=0;
34	<
33	>	((*(qtqueryset(qt)))--);
34	>	}
35		QUADTREE
36		qtAlloc()                       /* allocate a quadtree */
37		{
#	Line 99 | Line 99 | qtDone()                       /* free EVERYTHING */
99		{
100		if (quad_block[i] == NULL)
101		break;
102	<	free((char *)quad_block[i]);
102	>	free((void *)quad_block[i]);
103		quad_block[i] = NULL;
104		}
105		/* Free the flags */
106	<	if (i) free((char *)quad_flag);
106	>	if (i) free((void *)quad_flag);
107		quad_flag = NULL;
108		quad_free_list = EMPTY;
109		treetop = 0;
110		}
111
112	+	/*
113	+	* bary_parent(coord,i)  : Set coord to be value of pt at one level up in
114	+	*                         quadtree, given it was the ith child
115	+	* BCOORD coord[3];      :barycentric coordinates of point, also will hold
116	+	*                        result as side effect
117	+	* int i;                :designates which child coord was
118	+	*/
119	+	bary_parent(coord,i)
120	+	BCOORD coord[3];
121	+	int i;
122	+	{
123	+	switch(i) {
124	+	case 0:
125	+	/* update bary for child */
126	+	coord[0] = (coord[0] >> 1) + MAXBCOORD4;
127	+	coord[1] >>= 1;
128	+	coord[2] >>= 1;
129	+	break;
130	+	case 1:
131	+	coord[0] >>= 1;
132	+	coord[1]  = (coord[1] >> 1) + MAXBCOORD4;
133	+	coord[2] >>= 1;
134	+	break;
135	+
136	+	case 2:
137	+	coord[0] >>= 1;
138	+	coord[1] >>= 1;
139	+	coord[2] = (coord[2] >> 1) + MAXBCOORD4;
140	+	break;
141	+
142	+	case 3:
143	+	coord[0] = MAXBCOORD4 - (coord[0] >> 1);
144	+	coord[1] = MAXBCOORD4 - (coord[1] >> 1);
145	+	coord[2] = MAXBCOORD4 - (coord[2] >> 1);
146	+	break;
147	+	#ifdef DEBUG
148	+	default:
149	+	eputs("bary_parent():Invalid child\n");
150	+	break;
151	+	#endif
152	+	}
153	+	}
154	+
155	+	/*
156	+	* bary_from_child(coord,child,next): Given that coord was the (child) child
157	+	*                      of the quadtree node, calculate what the (next) child
158	+	*                      is at the same level.
159	+	* BCOORD coord[3];   :At current level (child)th child of node,will also hold
160	+	*                     result as side effect
161	+	* int child,next;    :Which child coord was (child), and which one
162	+	*                     is now desired(next)
163	+	*/
164	+	bary_from_child(coord,child,next)
165	+	BCOORD coord[3];
166	+	int child,next;
167	+	{
168	+	#ifdef DEBUG
169	+	if(child <0 || child > 3)
170	+	{
171	+	eputs("bary_from_child():Invalid child\n");
172	+	return;
173	+	}
174	+	if(next <0 || next > 3)
175	+	{
176	+	eputs("bary_from_child():Invalid next\n");
177	+	return;
178	+	}
179	+	#endif
180	+	if(next == child)
181	+	return;
182	+
183	+	switch(child){
184	+	case 0:
185	+	coord[0] = 0;
186	+	coord[1] = MAXBCOORD2 - coord[1];
187	+	coord[2] = MAXBCOORD2 - coord[2];
188	+	break;
189	+	case 1:
190	+	coord[0] = MAXBCOORD2 - coord[0];
191	+	coord[1] = 0;
192	+	coord[2] = MAXBCOORD2 - coord[2];
193	+	break;
194	+	case 2:
195	+	coord[0] = MAXBCOORD2 - coord[0];
196	+	coord[1] = MAXBCOORD2 - coord[1];
197	+	coord[2] = 0;
198	+	break;
199	+	case 3:
200	+	switch(next){
201	+	case 0:
202	+	coord[0] = 0;
203	+	coord[1] = MAXBCOORD2 - coord[1];
204	+	coord[2] = MAXBCOORD2 - coord[2];
205	+	break;
206	+	case 1:
207	+	coord[0] = MAXBCOORD2 - coord[0];
208	+	coord[1] = 0;
209	+	coord[2] = MAXBCOORD2 - coord[2];
210	+	break;
211	+	case 2:
212	+	coord[0] = MAXBCOORD2 - coord[0];
213	+	coord[1] = MAXBCOORD2 - coord[1];
214	+	coord[2] = 0;
215	+	break;
216	+	}
217	+	break;
218	+	}
219	+	}
220	+
221	+	/*
222	+	* int
223	+	* bary_child(coord):  Return which child coord is of node at current level
224	+	*                     As side effect recalculate coord at next level
225	+	* BCOORD coord[3];   :At current level coordinates of point, will also set
226	+	*                     to coords at next level as side effect
227	+	*/
228	+	int
229	+	bary_child(coord)
230	+	BCOORD coord[3];
231	+	{
232	+	int i;
233	+
234	+	if(coord[0] > MAXBCOORD4)
235	+	{
236	+	/* update bary for child */
237	+	coord[0] = (coord[0]<< 1) - MAXBCOORD2;
238	+	coord[1] <<= 1;
239	+	coord[2] <<= 1;
240	+	return(0);
241	+	}
242	+	else
243	+	if(coord[1] > MAXBCOORD4)
244	+	{
245	+	coord[0] <<= 1;
246	+	coord[1] = (coord[1] << 1) - MAXBCOORD2;
247	+	coord[2] <<= 1;
248	+	return(1);
249	+	}
250	+	else
251	+	if(coord[2] > MAXBCOORD4)
252	+	{
253	+	coord[0] <<= 1;
254	+	coord[1] <<= 1;
255	+	coord[2] = (coord[2] << 1) - MAXBCOORD2;
256	+	return(2);
257	+	}
258	+	else
259	+	{
260	+	coord[0] = MAXBCOORD2 - (coord[0] << 1);
261	+	coord[1] = MAXBCOORD2 - (coord[1] << 1);
262	+	coord[2] = MAXBCOORD2 - (coord[2] << 1);
263	+	return(3);
264	+	}
265	+	}
266	+
267	+
268	+
269		QUADTREE
270		qtLocate(qt,bcoord)
271		QUADTREE qt;
#	Line 247 | Line 404 | qtTrace_ray(qt,b,db0,db1,db2,nextptr,sign,sfactor,func
404		}
405		}
406
250	–
251	–
252	–
253	–
254	–
255	–
256	–
407		#define TEST_INT(tl,th,d,q0,q1,h,l) \
408		tl=d>q0;th=d<q1; if(tl&&th) goto Lfunc_call; \
409		if(tl) if(l) goto Lfunc_call; else h=TRUE; \
#	Line 281 | Line 431 | int n;
431
432		/* First check if can trivial accept: if vertex in cell */
433		if(s0 & s1 & s2)
434	+	{
435		goto Lfunc_call;
436	<
436	>	}
437		/* Assumption: Could not trivial reject*/
438		/* IF any coords lie on edge- must be in if couldnt reject */
439		a = q1[0];b= q0[1]; c= q0[2];
440		if(t0[0]== a || t0[1] == b || t0[2] == c)
441	+	{
442		goto Lfunc_call;
443	+	}
444		if(t1[0]== a || t1[1] == b || t1[2] == c)
445	+	{
446		goto Lfunc_call;
447	+	}
448		if(t2[0]== a || t2[1] == b || t2[2] == c)
449	+	{
450		goto Lfunc_call;
451	<
451	>	}
452		/* Test for edge crossings */
453		/* Test t0t1,t1t2,t2t0 against a */
454		/* Calculate edge crossings */
#	Line 411 | Line 567 | int n;
567		char testl,testh,test_t0t1,test_t1t2,test_t2t0;
568		unsigned int ls0,ls1,ls2;
569
570	+
571		/* May have gotten passed trivial reject if one/two vertices are ON */
572		a = q1[0];b= q0[1]; c= q0[2];
573		SIDES_LESS(t0,t1,t2,ls0,ls1,ls2,a,b,c);
574
575		/* First check if can trivial accept: if vertex in cell */
576		if(ls0 & ls1 & ls2)
577	+	{
578		goto Lfunc_call;
579	<
579	>	}
580		if(ls0==0 || ls1 == 0 || ls2 ==0)
581		return(qt);
582		/* Assumption: Could not trivial reject*/
583		/* IF any coords lie on edge- must be in if couldnt reject */
584
585		if(t0[0]== a || t0[1] == b || t0[2] == c)
586	+	{
587		goto Lfunc_call;
588	+	}
589		if(t1[0]== a || t1[1] == b || t1[2] == c)
590	+	{
591		goto Lfunc_call;
592	+	}
593		if(t2[0]== a || t2[1] == b || t2[2] == c)
594	+	{
595		goto Lfunc_call;
596	<
596	>	}
597		/* Test for edge crossings */
598		/* Test t0t1 against a,b,c */
599		/* First test if t0t1 can be trivially rejected */
#	Line 454 | Line 617 | int n;
617		db = t1[1] + dt21[1]*((double)(a - t1[0]))/dt21[0];
618		TEST_INT(testl,testh,db,q1[1],b,bl,bh)
619		}
620	<	test_t2t0 = !(((ls0 & 5)==0) || ((ls1 & 5)==0)|| ((ls2 & 5)==0) ||
620	>	test_t2t0 = !(((ls0 & 5)==0) || ((ls1 & 5)==0)|| ((ls2 & 5)==0) ||
621		((sq0 & 5)==0) ||((sq1 & 5)==0)|| ((sq2 & 5)==0));
622		if(test_t2t0 && (e0 & 4))
623		{
#	Line 519 | Line 682 | int n;
682
683		return(qt);
684		Lfunc_call:
522	–
685		qt = f.func(f.argptr,root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
686		s0,s1,s2,sq0,sq1,sq2,1,f,n);
687		return(qt);
#	Line 650 | Line 812 | BCOORD dt10[3],dt21[3],dt02[3];
812		BCOORD scale;
813		unsigned int s0,s1,s2,sq0,sq1,sq2;
814		FUNC f;
815	+	int n;
816		{
817		BCOORD a,b,c;
818		BCOORD va[3],vb[3],vc[3];
#	Line 740 | Line 903 | FUNC f;
903		/*************************************************************************/
904		/* Visit code for applying functions: NOTE THIS IS THE SAME AS INSERT CODE:
905		except sets flags: wanted insert to be as efficient as possible: so
906	<	broke into two sets of routines
906	>	broke into two sets of routines. Also traverses only to n levels.
907		*/
908
909		qtVisit_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
910	<	s0,s1,s2,sq0,sq1,sq2,f)
910	>	s0,s1,s2,sq0,sq1,sq2,f,n)
911		int root;
912		QUADTREE qt;
913		BCOORD q0[3],q1[3],q2[3];
#	Line 753 | Line 916 | BCOORD dt10[3],dt21[3],dt02[3];
916		BCOORD scale;
917		unsigned int s0,s1,s2,sq0,sq1,sq2;
918		FUNC f;
919	+	int n;
920		{
921		BCOORD a,b,c;
922		BCOORD va[3],vb[3],vc[3];
923		unsigned int sa,sb,sc;
924
925	+	if(n == 0)
926	+	return;
927		/* If a tree: trivial reject and recurse on potential children */
928		if(QT_IS_TREE(qt))
929		{
#	Line 780 | Line 946 | FUNC f;
946		vb[2] = c;
947		vb[0] = vc[0] = a;
948		qtVisit_tri(root,QT_NTH_CHILD(qt,0),q0,vc,
949	<	vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f);
949	>	vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
950		return;
951		}
952		if(sb==7)
#	Line 791 | Line 957 | FUNC f;
957		va[2] = c;
958		vc[0] = a;
959		qtVisit_tri(root,QT_NTH_CHILD(qt,1),vc,q1,va,
960	<	t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
960	>	t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
961		return;
962		}
963		if(sc==7)
#	Line 802 | Line 968 | FUNC f;
968		va[2] = vb[2] = c;
969		vb[0] = a;
970		qtVisit_tri(root,QT_NTH_CHILD(qt,2),vb,va,
971	<	q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
971	>	q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
972		return;
973		}
974
#	Line 816 | Line 982 | FUNC f;
982		if(sa==0 && sb==0 && sc==0)
983		{
984		qtVisit_tri_rev(root,QT_NTH_CHILD(qt,3),va,vb,
985	<	vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f);
985	>	vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
986		return;
987		}
988
989		if(sa)
990		qtVisit_tri(root,QT_NTH_CHILD(qt,0),q0,vc,vb,t0,
991	<	t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f);
991	>	t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
992		if(sb)
993		qtVisit_tri(root,QT_NTH_CHILD(qt,1),vc,q1,va,t0,
994	<	t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
994	>	t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
995		if(sc)
996		qtVisit_tri(root,QT_NTH_CHILD(qt,2),vb,va,q2,t0,
997	<	t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
997	>	t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
998		qtVisit_tri_rev(root,QT_NTH_CHILD(qt,3),va,vb,vc,t0,
999	<	t1,t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f);
999	>	t1,t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
1000		}
1001		/* Leaf node: Do definitive test */
1002		else
1003		qtLeaf_visit_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
1004	<	scale,s0,s1,s2,sq0,sq1,sq2,f);
1004	>	scale,s0,s1,s2,sq0,sq1,sq2,f,n);
1005
1006		}
1007
1008
1009		qtVisit_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
1010	<	s0,s1,s2,sq0,sq1,sq2,f)
1010	>	s0,s1,s2,sq0,sq1,sq2,f,n)
1011		int root;
1012		QUADTREE qt;
1013		BCOORD q0[3],q1[3],q2[3];
#	Line 850 | Line 1016 | BCOORD dt10[3],dt21[3],dt02[3];
1016		BCOORD scale;
1017		unsigned int s0,s1,s2,sq0,sq1,sq2;
1018		FUNC f;
1019	+	int n;
1020		{
1021		BCOORD a,b,c;
1022		BCOORD va[3],vb[3],vc[3];
1023		unsigned int sa,sb,sc;
1024
1025	+	if(n==0)
1026	+	return;
1027		/* If a tree: trivial reject and recurse on potential children */
1028		if(QT_IS_TREE(qt))
1029		{
#	Line 876 | Line 1045 | FUNC f;
1045		vb[2] = c;
1046		vb[0] = vc[0] = a;
1047		qtVisit_tri_rev(root,QT_NTH_CHILD(qt,0),q0,vc,
1048	<	vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f);
1048	>	vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
1049		return;
1050		}
1051		if(sb==0)
#	Line 887 | Line 1056 | FUNC f;
1056		va[2] = c;
1057		vc[0] = a;
1058		qtVisit_tri_rev(root,QT_NTH_CHILD(qt,1),vc,q1,va,
1059	<	t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
1059	>	t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
1060		return;
1061		}
1062		if(sc==0)
#	Line 898 | Line 1067 | FUNC f;
1067		va[2] = vb[2] = c;
1068		vb[0] = a;
1069		qtVisit_tri_rev(root,QT_NTH_CHILD(qt,2),vb,va,
1070	<	q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
1070	>	q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
1071		return;
1072		}
1073		va[0] = q1[0];
#	Line 911 | Line 1080 | FUNC f;
1080		if(sa==7 && sb==7 && sc==7)
1081		{
1082		qtVisit_tri(root,QT_NTH_CHILD(qt,3),va,vb,
1083	<	vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f);
1083	>	vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
1084		return;
1085		}
1086		if(sa!=7)
1087		qtVisit_tri_rev(root,QT_NTH_CHILD(qt,0),q0,vc,vb,
1088	<	t0,t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f);
1088	>	t0,t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
1089		if(sb!=7)
1090		qtVisit_tri_rev(root,QT_NTH_CHILD(qt,1),vc,q1,va,
1091	<	t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
1091	>	t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
1092		if(sc!=7)
1093		qtVisit_tri_rev(root,QT_NTH_CHILD(qt,2),vb,va,q2,
1094	<	t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
1094	>	t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
1095
1096		qtVisit_tri(root,QT_NTH_CHILD(qt,3),va,vb,vc,t0,t1,
1097	<	t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f);
1097	>	t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
1098		return;
1099		}
1100		/* Leaf node: Do definitive test */
1101		else
1102		qtLeaf_visit_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
1103	<	scale,s0,s1,s2,sq0,sq1,sq2,f);
1103	>	scale,s0,s1,s2,sq0,sq1,sq2,f,n);
1104		}
1105
1106
1107
1108		qtLeaf_visit_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
1109	<	scale, s0,s1,s2,sq0,sq1,sq2,f)
1109	>	scale, s0,s1,s2,sq0,sq1,sq2,f,n)
1110		int root;
1111		QUADTREE qt;
1112		BCOORD q0[3],q1[3],q2[3];
#	Line 945 | Line 1114 | BCOORD t0[3],t1[3],t2[3];
1114		BCOORD dt10[3],dt21[3],dt02[3];
1115		unsigned int scale,s0,s1,s2,sq0,sq1,sq2;
1116		FUNC f;
1117	+	int n;
1118		{
1119		double db;
1120		unsigned int e0,e1,e2;
1121		char al,ah,bl,bh,cl,ch,testl,testh;
1122		char test_t0t1,test_t1t2,test_t2t0;
1123		BCOORD a,b,c;
1124	<
1124	>
1125		/* First check if can trivial accept: if vertex in cell */
1126		if(s0 & s1 & s2)
1127		goto Lfunc_call;
#	Line 1055 | Line 1225 | FUNC f;
1225		return;
1226
1227		Lfunc_call:
1228	<	f.func(f.argptr,root,qt);
1228	>
1229	>	f.func(f.argptr,root,qt,n);
1230		if(!QT_IS_EMPTY(qt))
1231		QT_LEAF_SET_FLAG(qt);
1232	+
1233		}
1234
1235
#	Line 1065 | Line 1237 | Lfunc_call:
1237		/* Leaf node: Do definitive test */
1238		QUADTREE
1239		qtLeaf_visit_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
1240	<	scale, s0,s1,s2,sq0,sq1,sq2,f)
1240	>	scale, s0,s1,s2,sq0,sq1,sq2,f,n)
1241		int root;
1242		QUADTREE qt;
1243		BCOORD q0[3],q1[3],q2[3];
#	Line 1073 | Line 1245 | BCOORD t0[3],t1[3],t2[3];
1245		BCOORD dt10[3],dt21[3],dt02[3];
1246		unsigned int scale,s0,s1,s2,sq0,sq1,sq2;
1247		FUNC f;
1248	+	int n;
1249		{
1250		double db;
1251		unsigned int e0,e1,e2;
#	Line 1191 | Line 1364 | FUNC f;
1364		return;
1365
1366		Lfunc_call:
1367	<	f.func(f.argptr,root,qt);
1367	>	f.func(f.argptr,root,qt,n);
1368		if(!QT_IS_EMPTY(qt))
1369		QT_LEAF_SET_FLAG(qt);
1370		}
1371	+
1372	+
1373	+	QUADTREE
1374	+	qtInsert_point(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr)
1375	+	int root;
1376	+	QUADTREE qt,parent;
1377	+	BCOORD q0[3],q1[3],q2[3],bc[3],scale;
1378	+	FUNC f;
1379	+	int n,*doneptr;
1380	+	{
1381	+	BCOORD a,b,c;
1382	+	BCOORD va[3],vb[3],vc[3];
1383	+
1384	+	if(QT_IS_TREE(qt))
1385	+	{
1386	+	a = q1[0] + scale;
1387	+	b = q0[1] + scale;
1388	+	c = q0[2] + scale;
1389	+	if(bc[0] > a)
1390	+	{
1391	+	vc[0] = a; vc[1] = b; vc[2] = q0[2];
1392	+	vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1393	+	QT_NTH_CHILD(qt,0) = qtInsert_point(root,QT_NTH_CHILD(qt,0),
1394	+	qt,q0,vc,vb,bc,scale>>1,f,n+1,doneptr);
1395	+	if(!*doneptr)
1396	+	{
1397	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1398	+	if(!*doneptr)
1399	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1400	+	if(!*doneptr)
1401	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1402	+	}
1403	+	return(qt);
1404	+	}
1405	+	if(bc[1] > b)
1406	+	{
1407	+	vc[0] = a; vc[1] = b; vc[2] = q0[2];
1408	+	va[0] = q1[0]; va[1] = b; va[2] = c;
1409	+	QT_NTH_CHILD(qt,1) =qtInsert_point(root,QT_NTH_CHILD(qt,1),
1410	+	qt,vc,q1,va,bc,scale >>1,f,n+1,doneptr);
1411	+	if(!*doneptr)
1412	+	{
1413	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1414	+	if(!*doneptr)
1415	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1416	+	if(!*doneptr)
1417	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1418	+	}
1419	+	return(qt);
1420	+	}
1421	+	if(bc[2] > c)
1422	+	{
1423	+	va[0] = q1[0]; va[1] = b; va[2] = c;
1424	+	vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1425	+	QT_NTH_CHILD(qt,2) = qtInsert_point(root,QT_NTH_CHILD(qt,2),
1426	+	qt,vb,va,q2,bc,scale>>1,f,n+1,doneptr);
1427	+	if(!*doneptr)
1428	+	{
1429	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1430	+	if(!*doneptr)
1431	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1432	+	if(!*doneptr)
1433	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1434	+	}
1435	+	return(qt);
1436	+	}
1437	+	else
1438	+	{
1439	+	va[0] = q1[0]; va[1] = b; va[2] = c;
1440	+	vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1441	+	vc[0] = a; vc[1] = b; vc[2] = q0[2];
1442	+	QT_NTH_CHILD(qt,3) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,3),
1443	+	qt,va,vb,vc,bc,scale>>1,f,n+1,doneptr);
1444	+	if(!*doneptr)
1445	+	{
1446	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1447	+	if(!*doneptr)
1448	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1449	+	if(!*doneptr)
1450	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1451	+	}
1452	+	return(qt);
1453	+	}
1454	+	}
1455	+	else
1456	+	{
1457	+	qt = f.func(f.argptr,root,qt,parent,q0,q1,q2,bc,scale,0,f,n,doneptr);
1458	+	return(qt);
1459	+	}
1460	+	}
1461	+
1462	+
1463	+	QUADTREE
1464	+	qtInsert_point_rev(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr)
1465	+	int root;
1466	+	QUADTREE qt,parent;
1467	+	BCOORD q0[3],q1[3],q2[3],bc[3];
1468	+	BCOORD scale;
1469	+	FUNC f;
1470	+	int n,*doneptr;
1471	+	{
1472	+	BCOORD a,b,c;
1473	+	BCOORD va[3],vb[3],vc[3];
1474	+
1475	+	if(QT_IS_TREE(qt))
1476	+	{
1477	+	a = q1[0] - scale;
1478	+	b = q0[1] - scale;
1479	+	c = q0[2] - scale;
1480	+	if(bc[0] < a)
1481	+	{
1482	+	vc[0] = a; vc[1] = b; vc[2] = q0[2];
1483	+	vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1484	+	QT_NTH_CHILD(qt,0) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,0),
1485	+	qt,q0,vc,vb,bc,scale>>1,f,n+1,doneptr);
1486	+	if(!*doneptr)
1487	+	{
1488	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1489	+	if(!*doneptr)
1490	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1491	+	if(!*doneptr)
1492	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1493	+	}
1494	+	return(qt);
1495	+	}
1496	+	if(bc[1] < b)
1497	+	{
1498	+	vc[0] = a; vc[1] = b; vc[2] = q0[2];
1499	+	va[0] = q1[0]; va[1] = b; va[2] = c;
1500	+	QT_NTH_CHILD(qt,1) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,1),
1501	+	qt,vc,q1,va,bc,scale>>1,f,n+1,doneptr);
1502	+	if(!*doneptr)
1503	+	{
1504	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1505	+	if(!*doneptr)
1506	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1507	+	if(!*doneptr)
1508	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1509	+	}
1510	+	return(qt);
1511	+	}
1512	+	if(bc[2] < c)
1513	+	{
1514	+	va[0] = q1[0]; va[1] = b; va[2] = c;
1515	+	vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1516	+	QT_NTH_CHILD(qt,2) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,2),
1517	+	qt,vb,va,q2,bc,scale>>1,f,n+1,doneptr);
1518	+	if(!*doneptr)
1519	+	{
1520	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1521	+	if(!*doneptr)
1522	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1523	+	if(!*doneptr)
1524	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1525	+	}
1526	+	return(qt);
1527	+	}
1528	+	else
1529	+	{
1530	+	va[0] = q1[0]; va[1] = b; va[2] = c;
1531	+	vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1532	+	vc[0] = a; vc[1] = b; vc[2] = q0[2];
1533	+	QT_NTH_CHILD(qt,3) = qtInsert_point(root,QT_NTH_CHILD(qt,3),
1534	+	qt,va,vb,vc,bc,scale>>1,f,n+1,doneptr);
1535	+	if(!*doneptr)
1536	+	{
1537	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1538	+	if(!*doneptr)
1539	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1540	+	if(!*doneptr)
1541	+	f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1542	+	}
1543	+	return(qt);
1544	+	}
1545	+	}
1546	+	else
1547	+	{
1548	+	qt = f.func(f.argptr,root,qt,parent,q0,q1,q2,bc,scale,1,f,n,doneptr);
1549	+	return(qt);
1550	+	}
1551	+	}
1552	+
1553	+
1554	+
1555	+
1556	+
1557	+
1558	+
1559	+
1560
1561
1562

Diff Legend

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