ViewVC Help

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

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

Comparing ray/src/hd/rhd_qtree.c (file contents):
Revision 3.10 by gregl, Fri Dec 5 09:40:05 1997 UTC vs.
Revision 3.16 by gregl, Wed Dec 31 09:06:54 1997 UTC

#	Line 16 | Line 16 | static char SCCSid[] = "$SunId$ SGI";
16		#endif
17		/* maximum allowed angle difference (deg.) */
18		#ifndef MAXANG
19	<	#define MAXANG          20.
19	>	#define MAXANG          20
20		#endif
21	+	#if MAXANG>0
22	+	#define MAXDIFF2        ( MAXANG*MAXANG * (PI*PI/180./180.))
23	+	#endif
24
22	–	#define MAXDIFF2        (long)( MAXANG*MAXANG /90./90.*(1L<<15)*(1L<<15))
23	–
25		#define abs(i)          ((i) < 0 ? -(i) : (i))
26
27		RTREE   qtrunk;                 /* our quadtree trunk */
#	Line 28 | Line 29 | double qtDepthEps = .05;       /* epsilon to compare depths
29		int     qtMinNodesiz = 2;       /* minimum node dimension (pixels) */
30		struct rleaves  qtL;            /* our pile of leaves */
31
32	+	static int4     falleaves;      /* our list of fallen leaves */
33	+
34	+	#define composted(li)   (qtL.bl <= qtL.tl ? \
35	+	((li) < qtL.bl || (li) >= qtL.tl) : \
36	+	((li) < qtL.bl && (li) >= qtL.tl))
37	+
38		#define TBUNDLESIZ      409     /* number of twigs in a bundle */
39
40		static RTREE    **twigbundle;   /* free twig blocks (NULL term.) */
41		static int      nexttwig;       /* next free twig */
42
36	–	#define ungetleaf(li)   (qtL.tl=(li))   /* dangerous if used improperly */
43
38	–
44		static RTREE *
45		newtwig()                       /* allocate a twig */
46		{
#	Line 88 | Line 93 | int    really;
93		}
94
95
96	<	static int
92	<	newleaf()                       /* allocate a leaf from our pile */
93	<	{
94	<	int     li;
95	<
96	<	li = qtL.tl++;
97	<	if (qtL.tl >= qtL.nl)   /* get next leaf in ring */
98	<	qtL.tl = 0;
99	<	if (qtL.tl == qtL.bl)   /* need to shake some free */
100	<	qtCompost(LFREEPCT);
101	<	return(li);
102	<	}
103	<
104	<
105	<	#define LEAFSIZ         (3*sizeof(float)+2*sizeof(short)+\
96	>	#define LEAFSIZ         (3*sizeof(float)+sizeof(int4)+\
97		sizeof(TMbright)+6*sizeof(BYTE))
98
99		int
#	Line 129 | Line 120 | register int   n;
120		return(0);
121		/* assign larger alignment types earlier */
122		qtL.wp = (float (*)[3])qtL.base;
123	<	qtL.wd = (short (*)[2])(qtL.wp + n);
123	>	qtL.wd = (int4 *)(qtL.wp + n);
124		qtL.brt = (TMbright *)(qtL.wd + n);
125		qtL.chr = (BYTE (*)[3])(qtL.brt + n);
126		qtL.rgb = (BYTE (*)[3])(qtL.chr + n);
127		qtL.nl = n;
128		qtL.tml = qtL.bl = qtL.tl = 0;
129	+	falleaves = -1;
130		return(n);
131		}
132
#	Line 165 | Line 157 | register RTREE *tp;
157		tp->flgs &= ~BRF(i);
158		} else if (tp->flgs & LFF(i)) {
159		li = tp->k[i].li;
160	<	if (qtL.bl < qtL.tl ?
169	<	(li < qtL.bl || li >= qtL.tl) :
170	<	(li < qtL.bl && li >= qtL.tl))
160	>	if (composted(li))
161		tp->flgs &= ~LFF(i);
162		}
163		}
#	Line 177 | Line 167 | int
167		qtCompost(pct)                  /* free up some leaves */
168		int     pct;
169		{
170	+	register int4   *fl;
171		int     nused, nclear, nmapped;
181	–
172		/* figure out how many leaves to clear */
173		nclear = qtL.nl * pct / 100;
174		nused = qtL.tl - qtL.bl;
#	Line 189 | Line 179 | int    pct;
179		if (nclear >= nused) {  /* clear them all */
180		qtFreeTree(0);
181		qtL.tml = qtL.bl = qtL.tl = 0;
182	+	falleaves = -1;
183		return(nused);
184		}
185		/* else clear leaves from bottom */
#	Line 197 | Line 188 | int    pct;
188		qtL.bl += nclear;
189		if (qtL.bl >= qtL.nl) qtL.bl -= qtL.nl;
190		if (nmapped <= nclear) qtL.tml = qtL.bl;
191	<	shaketree(&qtrunk);
191	>	shaketree(&qtrunk);     /* dereference composted leaves */
192	>	for (fl = &falleaves; *fl >= 0; fl = qtL.wd + *fl)
193	>	while (composted(*fl))
194	>	if ((*fl = qtL.wd[*fl]) < 0)
195	>	return(nclear);
196		return(nclear);
197		}
198
199
205	–	static
206	–	encodedir(pa, dv)               /* encode a normalized direction vector */
207	–	short   pa[2];
208	–	FVECT   dv;
209	–	{
210	–	pa[1] = 0;
211	–	if (dv[2] >= 1.)
212	–	pa[0] = (1L<<15)-1;
213	–	else if (dv[2] <= -1.)
214	–	pa[0] = -((1L<<15)-1);
215	–	else {
216	–	pa[0] = ((1L<<15)-1)/(PI/2.) * asin(dv[2]);
217	–	pa[1] = ((1L<<15)-1)/PI * atan2(dv[1], dv[0]);
218	–	}
219	–	}
220	–
221	–
222	–	#define ALTSHFT         5
223	–	#define NALT            (1<<ALTSHFT)
224	–	#define azisft(alt)     azisftab[abs(alt)>>(15-ALTSHFT)]
225	–
226	–	static unsigned short   azisftab[NALT];
227	–
228	–	static
229	–	azisftinit(alt)         /* initialize azimuth scale factor table */
230	–	int     alt;
231	–	{
232	–	register int    i;
233	–
234	–	for (i = NALT; i--; )
235	–	azisftab[i] = 2.*(1L<<15) * cos(PI/2.*(i+.5)/NALT);
236	–	return(azisft(alt));
237	–	}
238	–
239	–	#define azisf(alt)      (azisftab[0] ? azisft(alt) : azisftinit(alt)) >> 15
240	–
241	–	static long
242	–	dir2diff(pa1, pa2)              /* relative distance^2 between directions */
243	–	short   pa1[2], pa2[2];
244	–	{
245	–	long    altd2, azid2;
246	–	int     alt;
247	–
248	–	altd2 = pa1[0] - pa2[0];        /* get altitude difference^2 */
249	–	altd2 *= altd2;
250	–	if (altd2 > MAXDIFF2)
251	–	return(altd2);          /* too large already */
252	–	azid2 = pa1[1] - pa2[1];        /* get adjusted azimuth difference^2 */
253	–	if (azid2 < 0) azid2 = -azid2;
254	–	if (azid2 >= 1L<<15) {          /* wrap sphere */
255	–	azid2 -= 1L<<16;
256	–	if (azid2 < 0) azid2 = -azid2;
257	–	}
258	–	alt = (pa1[0]+pa2[0])/2;
259	–	azid2 = azid2*azisf(alt);       /* evaluation order is important */
260	–	azid2 *= azid2;
261	–	return(altd2 + azid2);
262	–	}
263	–
264	–
200		int
201		qtFindLeaf(x, y)                /* find closest leaf to (x,y) */
202		int     x, y;
#	Line 300 | Line 235 | int    x, y;
235
236
237		static
238	<	addleaf(li)                     /* add a leaf to our tree */
239	<	int     li;
238	>	putleaf(li, drop)               /* put a leaf in our tree */
239	>	register int    li;
240	>	int     drop;
241		{
242		register RTREE  *tp = &qtrunk;
243		int     x0=0, y0=0, x1=odev.hres, y1=odev.vres;
244	<	int     lo = -1;
245	<	long    d2;
310	<	short   dc[2];
244	>	register int    lo = -1;
245	>	double  d2;
246		int     x, y, mx, my;
247		double  z;
248	<	FVECT   ip, wp;
248	>	FVECT   ip, wp, vd;
249		register int    q;
250	+	/* check for dead leaf */
251	+	if (!qtL.chr[li][1] && !(qtL.chr[li][0] | qtL.chr[li][2]))
252	+	return(0);
253		/* compute leaf location in view */
254		VCOPY(wp, qtL.wp[li]);
255		viewloc(ip, &odev.v, wp);
256		if (ip[2] <= 0. || ip[0] < 0. || ip[0] >= 1.
257		|| ip[1] < 0. || ip[1] >= 1.)
258	<	return(0);                      /* behind or outside view */
258	>	goto dropit;                    /* behind or outside view */
259		#ifdef DEBUG
260		if (odev.v.type == VT_PAR | odev.v.vfore > FTINY)
261	<	error(INTERNAL, "bad view assumption in addleaf");
261	>	error(INTERNAL, "bad view assumption in putleaf");
262		#endif
263		for (q = 0; q < 3; q++)
264	<	wp[q] = (wp[q] - odev.v.vp[q])/ip[2];
265	<	encodedir(dc, wp);              /* compute pixel direction */
266	<	d2 = dir2diff(dc, qtL.wd[li]);
264	>	vd[q] = (wp[q] - odev.v.vp[q])/ip[2];
265	>	d2 = fdir2diff(qtL.wd[li], vd);
266	>	#ifdef MAXDIFF2
267		if (d2 > MAXDIFF2)
268	<	return(0);                      /* leaf dir. too far off */
268	>	goto dropit;                    /* leaf dir. too far off */
269	>	#endif
270		x = ip[0] * odev.hres;
271		y = ip[1] * odev.vres;
272		z = ip[2];
#	Line 348 | Line 287 | int    li;
287		if (!(tp->flgs & LFF(q))) {     /* found stem for leaf */
288		tp->k[q].li = li;
289		tp->flgs |= CHLFF(q);
290	<	break;
290	>	return(1);
291		}
292		if (lo != tp->k[q].li) {        /* check old leaf */
293		lo = tp->k[q].li;
#	Line 358 | Line 297 | int    li;
297		/* is node minimum size? */
298		if (y1-y0 <= qtMinNodesiz || x1-x0 <= qtMinNodesiz) {
299		if (z > (1.+qtDepthEps)*ip[2])
300	<	return(0);              /* old one closer */
300	>	break;                  /* old one closer */
301		if (z >= (1.-qtDepthEps)*ip[2] &&
302	<	dir2diff(dc, qtL.wd[lo]) < d2)
303	<	return(0);              /* old one better */
304	<	tp->k[q].li = li;               /* else new one is */
302	>	fdir2diff(qtL.wd[lo], vd) < d2)
303	>	break;                  /* old one better */
304	>	tp->k[q].li = li;               /* attach new */
305		tp->flgs |= CHF(q);
306	+	li = lo;                        /* drop old... */
307		break;
308		}
309		tp->flgs &= ~LFF(q);            /* else grow tree */
#	Line 374 | Line 314 | int    li;
314		my = ip[1] * odev.vres;
315		if (mx >= (x0 + x1) >> 1) q |= 01;
316		if (my >= (y0 + y1) >> 1) q |= 02;
317	+	tp->flgs = CH_ANY|LFF(q);       /* all new */
318		tp->k[q].li = lo;
378	–	tp->flgs |= LFF(q)|CH_ANY;      /* all new */
319		}
320	<	return(1);              /* done */
320	>	dropit:
321	>	if (drop)
322	>	if (li+1 == (qtL.tl ? qtL.tl : qtL.nl))
323	>	qtL.tl = li;            /* special case */
324	>	else {
325	>	qtL.chr[li][0] = qtL.chr[li][1] = qtL.chr[li][2] = 0;
326	>	qtL.wd[li] = falleaves;
327	>	falleaves = li;
328	>	}
329	>	return(li == lo);
330		}
331
332
#	Line 386 | Line 335 | COLR   c;
335		FVECT   p, v;
336		{
337		register int    li;
338	<
339	<	li = newleaf();
338	>	int     mapit;
339	>	/* grab a leaf */
340	>	if (!imm_mode && falleaves >= 0) {      /* check for fallen leaves */
341	>	li = falleaves;
342	>	falleaves = qtL.wd[li];
343	>	mapit = qtL.tml <= qtL.tl ?
344	>	(li < qtL.tml || li >= qtL.tl) :
345	>	(li < qtL.tml && li >= qtL.tl) ;
346	>	} else {                                /* else allocate new one */
347	>	li = qtL.tl++;
348	>	if (qtL.tl >= qtL.nl)           /* next leaf in ring */
349	>	qtL.tl = 0;
350	>	if (qtL.tl == qtL.bl)           /* need to shake some free */
351	>	qtCompost(LFREEPCT);
352	>	mapit = 0;                      /* we'll map it later */
353	>	}
354		VCOPY(qtL.wp[li], p);
355	<	encodedir(qtL.wd[li], v);
355	>	qtL.wd[li] = encodedir(v);
356		tmCvColrs(&qtL.brt[li], qtL.chr[li], c, 1);
357	<	if (!addleaf(li))
358	<	ungetleaf(li);
357	>	if (putleaf(li, 1) && mapit)
358	>	tmMapPixels(qtL.rgb+li, qtL.brt+li, qtL.chr+li, 1);
359		}
360
361
#	Line 405 | Line 368 | qtReplant()                    /* replant our tree using new view */
368		qtFreeTree(0);                  /* blow the old tree away */
369		/* regrow it in new place */
370		for (i = qtL.bl; i != qtL.tl; ) {
371	<	addleaf(i);
371	>	putleaf(i, 0);
372		if (++i >= qtL.nl) i = 0;
373		}
374		}

Diff Legend

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