src/rt/srcsamp.c

#ifndef lint
static const char       RCSid[] = "$Id: srcsamp.c,v 2.16 2009/06/06 02:11:44 greg Exp $";
#endif
/*
 * Source sampling routines
 *
 *  External symbols declared in source.h
 */

#include "copyright.h"

#include  "ray.h"

#include  "source.h"

#include  "random.h"


static int  cyl_partit(), flt_partit();


double
nextssamp(r, si)                /* compute sample for source, rtn. distance */
register RAY  *r;               /* origin is read, direction is set */
register SRCINDEX  *si;         /* source index (modified to current) */
{
        int  cent[3], size[3], parr[2];
        SRCREC  *srcp;
        FVECT  vpos;
        double  d;
        register int  i;
nextsample:
        while (++si->sp >= si->np) {    /* get next sample */
                if (++si->sn >= nsources)
                        return(0.0);    /* no more */
                if (source[si->sn].sflags & SSKIP)
                        si->np = 0;
                else if (srcsizerat <= FTINY)
                        nopart(si, r);
                else {
                        for (i = si->sn; source[i].sflags & SVIRTUAL;
                                        i = source[i].sa.sv.sn)
                                ;               /* partition source */
                        (*sfun[source[i].so->otype].of->partit)(si, r);
                }
                si->sp = -1;
        }
                                        /* get partition */
        cent[0] = cent[1] = cent[2] = 0;
        size[0] = size[1] = size[2] = MAXSPART;
        parr[0] = 0; parr[1] = si->sp;
        if (!skipparts(cent, size, parr, si->spt))
                error(CONSISTENCY, "bad source partition in nextssamp");
                                        /* compute sample */
        srcp = source + si->sn;
        if (dstrsrc > FTINY) {                  /* jitter sample */
                dimlist[ndims] = si->sn + 8831;
                dimlist[ndims+1] = si->sp + 3109;
                d = urand(ilhash(dimlist,ndims+2)+samplendx);
                if (srcp->sflags & SFLAT) {
                        multisamp(vpos, 2, d);
                        vpos[SW] = 0.5;
                } else
                        multisamp(vpos, 3, d);
                for (i = 0; i < 3; i++)
                        vpos[i] = dstrsrc * (1. - 2.*vpos[i]) *
                                        (double)size[i]*(1.0/MAXSPART);
        } else
                vpos[0] = vpos[1] = vpos[2] = 0.0;

        VSUM(vpos, vpos, cent, 1.0/MAXSPART);
                                        /* avoid circular aiming failures */
        if ((srcp->sflags & SCIR) && (si->np > 1 || dstrsrc > 0.7)) {
                FVECT   trim;
                if (srcp->sflags & (SFLAT|SDISTANT)) {
                        d = 1.12837917;         /* correct setflatss() */
                        trim[SU] = d*sqrt(1.0 - 0.5*vpos[SV]*vpos[SV]);
                        trim[SV] = d*sqrt(1.0 - 0.5*vpos[SU]*vpos[SU]);
                        trim[SW] = 0.0;
                } else {
                        trim[SW] = trim[SU] = vpos[SU]*vpos[SU];
                        d = vpos[SV]*vpos[SV];
                        if (d > trim[SW]) trim[SW] = d;
                        trim[SU] += d;
                        d = vpos[SW]*vpos[SW];
                        if (d > trim[SW]) trim[SW] = d;
                        trim[SU] += d;
                        if (trim[SU] > FTINY*FTINY) {
                                d = 1.0/0.7236; /* correct sphsetsrc() */
                                trim[SW] = trim[SV] = trim[SU] =
                                                d*sqrt(trim[SW]/trim[SU]);
                        } else
                                trim[SW] = trim[SV] = trim[SU] = 0.0;
                }
                for (i = 0; i < 3; i++)
                        vpos[i] *= trim[i];
        }
                                        /* compute direction */
        for (i = 0; i < 3; i++)
                r->rdir[i] = srcp->sloc[i] +
                                vpos[SU]*srcp->ss[SU][i] +
                                vpos[SV]*srcp->ss[SV][i] +
                                vpos[SW]*srcp->ss[SW][i];

        if (!(srcp->sflags & SDISTANT))
                VSUB(r->rdir, r->rdir, r->rorg);
                                        /* compute distance */
        if ((d = normalize(r->rdir)) == 0.0)
                goto nextsample;                /* at source! */

                                        /* compute sample size */
        if (srcp->sflags & SFLAT) {
                si->dom = sflatform(si->sn, r->rdir);
                si->dom *= size[SU]*size[SV]*(1.0/MAXSPART/MAXSPART);
        } else if (srcp->sflags & SCYL) {
                si->dom = scylform(si->sn, r->rdir);
                si->dom *= size[SU]*(1.0/MAXSPART);
        } else {
                si->dom = size[SU]*size[SV]*(double)size[SW] *
                                (1.0/MAXSPART/MAXSPART/MAXSPART) ;
        }
        if (srcp->sflags & SDISTANT) {
                si->dom *= srcp->ss2;
                return(FHUGE);
        }
        if (si->dom <= 1e-4)
                goto nextsample;                /* behind source? */
        si->dom *= srcp->ss2/(d*d);
        return(d);              /* sample OK, return distance */
}


int
skipparts(ct, sz, pp, pt)               /* skip to requested partition */
int  ct[3], sz[3];              /* center and size of partition (returned) */
register int  pp[2];            /* current index, number to skip (modified) */
unsigned char  *pt;             /* partition array */
{
        register int  p;
                                        /* check this partition */
        p = spart(pt, pp[0]);
        pp[0]++;
        if (p == S0) {                  /* leaf partition */
                if (pp[1]) {
                        pp[1]--;
                        return(0);      /* not there yet */
                } else
                        return(1);      /* we've arrived */
        }
                                /* else check lower */
        sz[p] >>= 1;
        ct[p] -= sz[p];
        if (skipparts(ct, sz, pp, pt))
                return(1);      /* return hit */
                                /* else check upper */
        ct[p] += sz[p] << 1;
        if (skipparts(ct, sz, pp, pt))
                return(1);      /* return hit */
                                /* else return to starting position */
        ct[p] -= sz[p];
        sz[p] <<= 1;
        return(0);              /* return miss */
}


void
nopart(si, r)                   /* single source partition */
register SRCINDEX  *si;
RAY  *r;
{
        clrpart(si->spt);
        setpart(si->spt, 0, S0);
        si->np = 1;
}


void
cylpart(si, r)                  /* partition a cylinder */
SRCINDEX  *si;
register RAY  *r;
{
        double  dist2, safedist2, dist2cent, rad2;
        FVECT  v;
        register SRCREC  *sp;
        int  pi;
                                        /* first check point location */
        clrpart(si->spt);
        sp = source + si->sn;
        rad2 = 1.365 * DOT(sp->ss[SV],sp->ss[SV]);
        v[0] = r->rorg[0] - sp->sloc[0];
        v[1] = r->rorg[1] - sp->sloc[1];
        v[2] = r->rorg[2] - sp->sloc[2];
        dist2 = DOT(v,sp->ss[SU]);
        safedist2 = DOT(sp->ss[SU],sp->ss[SU]);
        dist2 *= dist2 / safedist2;
        dist2cent = DOT(v,v);
        dist2 = dist2cent - dist2;
        if (dist2 <= rad2) {            /* point inside extended cylinder */
                si->np = 0;
                return;
        }
        safedist2 *= 4.*r->rweight*r->rweight/(srcsizerat*srcsizerat);
        if (dist2 <= 4.*rad2 ||         /* point too close to subdivide */
                        dist2cent >= safedist2) {       /* or too far */
                setpart(si->spt, 0, S0);
                si->np = 1;
                return;
        }
        pi = 0;
        si->np = cyl_partit(r->rorg, si->spt, &pi, MAXSPART,
                        sp->sloc, sp->ss[SU], safedist2);
}


static int
cyl_partit(ro, pt, pi, mp, cent, axis, d2)      /* slice a cylinder */
FVECT  ro;
unsigned char  *pt;
register int  *pi;
int  mp;
FVECT  cent, axis;
double  d2;
{
        FVECT  newct, newax;
        int  npl, npu;

        if (mp < 2 || dist2(ro, cent) >= d2) {  /* hit limit? */
                setpart(pt, *pi, S0);
                (*pi)++;
                return(1);
        }
                                        /* subdivide */
        setpart(pt, *pi, SU);
        (*pi)++;
        newax[0] = .5*axis[0];
        newax[1] = .5*axis[1];
        newax[2] = .5*axis[2];
        d2 *= 0.25;
                                        /* lower half */
        newct[0] = cent[0] - newax[0];
        newct[1] = cent[1] - newax[1];
        newct[2] = cent[2] - newax[2];
        npl = cyl_partit(ro, pt, pi, mp/2, newct, newax, d2);
                                        /* upper half */
        newct[0] = cent[0] + newax[0];
        newct[1] = cent[1] + newax[1];
        newct[2] = cent[2] + newax[2];
        npu = cyl_partit(ro, pt, pi, mp/2, newct, newax, d2);
                                        /* return total */
        return(npl + npu);
}


void
flatpart(si, r)                         /* partition a flat source */
register SRCINDEX  *si;
register RAY  *r;
{
        register RREAL  *vp;
        FVECT  v;
        double  du2, dv2;
        int  pi;

        clrpart(si->spt);
        vp = source[si->sn].sloc;
        v[0] = r->rorg[0] - vp[0];
        v[1] = r->rorg[1] - vp[1];
        v[2] = r->rorg[2] - vp[2];
        vp = source[si->sn].snorm;
        if (DOT(v,vp) <= 0.) {          /* behind source */
                si->np = 0;
                return;
        }
        dv2 = 2.*r->rweight/srcsizerat;
        dv2 *= dv2;
        vp = source[si->sn].ss[SU];
        du2 = dv2 * DOT(vp,vp);
        vp = source[si->sn].ss[SV];
        dv2 *= DOT(vp,vp);
        pi = 0;
        si->np = flt_partit(r->rorg, si->spt, &pi, MAXSPART,
                source[si->sn].sloc,
                source[si->sn].ss[SU], source[si->sn].ss[SV], du2, dv2);
}


static int
flt_partit(ro, pt, pi, mp, cent, u, v, du2, dv2)        /* partition flatty */
FVECT  ro;
unsigned char  *pt;
register int  *pi;
int  mp;
FVECT  cent, u, v;
double  du2, dv2;
{
        double  d2;
        FVECT  newct, newax;
        int  npl, npu;

        if (mp < 2 || ((d2 = dist2(ro, cent)) >= du2
                        && d2 >= dv2)) {        /* hit limit? */
                setpart(pt, *pi, S0);
                (*pi)++;
                return(1);
        }
        if (du2 > dv2) {                        /* subdivide in U */
                setpart(pt, *pi, SU);
                (*pi)++;
                newax[0] = .5*u[0];
                newax[1] = .5*u[1];
                newax[2] = .5*u[2];
                u = newax;
                du2 *= 0.25;
        } else {                                /* subdivide in V */
                setpart(pt, *pi, SV);
                (*pi)++;
                newax[0] = .5*v[0];
                newax[1] = .5*v[1];
                newax[2] = .5*v[2];
                v = newax;
                dv2 *= 0.25;
        }
                                        /* lower half */
        newct[0] = cent[0] - newax[0];
        newct[1] = cent[1] - newax[1];
        newct[2] = cent[2] - newax[2];
        npl = flt_partit(ro, pt, pi, mp/2, newct, u, v, du2, dv2);
                                        /* upper half */
        newct[0] = cent[0] + newax[0];
        newct[1] = cent[1] + newax[1];
        newct[2] = cent[2] + newax[2];
        npu = flt_partit(ro, pt, pi, mp/2, newct, u, v, du2, dv2);
                                /* return total */
        return(npl + npu);
}


double
scylform(sn, dir)               /* compute cosine for cylinder's projection */
int  sn;
register FVECT  dir;            /* assume normalized */
{
        register RREAL  *dv;
        double  d;

        dv = source[sn].ss[SU];
        d = DOT(dir, dv);
        d *= d / DOT(dv,dv);
        return(sqrt(1. - d));
}
Revision:	2.17
Committed:	Sat Oct 23 18:13:54 2010 UTC (13 years, 6 months ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad4R1
Changes since 2.16:	+8 -10 lines
Log Message:	Made a few obvious optimizations
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.17	static const char RCSid[] = "$Id: srcsamp.c,v 2.16 2009/06/06 02:11:44 greg Exp $";
3	greg	1.1	#endif
4			/*
5			* Source sampling routines
6	greg	2.7	*
7			* External symbols declared in source.h
8			*/
9
10	greg	2.8	#include "copyright.h"
11	greg	1.1
12	greg	1.4	#include "ray.h"
13	greg	1.1
14			#include "source.h"
15
16			#include "random.h"
17
18
19	greg	2.5	static int cyl_partit(), flt_partit();
20
21
22	greg	1.1	double
23	greg	1.4	nextssamp(r, si) /* compute sample for source, rtn. distance */
24			register RAY r; / origin is read, direction is set */
25	greg	1.1	register SRCINDEX si; / source index (modified to current) */
26			{
27			int cent[3], size[3], parr[2];
28	greg	2.16	SRCREC *srcp;
29	greg	1.1	FVECT vpos;
30			double d;
31			register int i;
32	greg	2.2	nextsample:
33	greg	1.1	while (++si->sp >= si->np) { /* get next sample */
34			if (++si->sn >= nsources)
35			return(0.0); /* no more */
36	greg	1.7	if (source[si->sn].sflags & SSKIP)
37			si->np = 0;
38			else if (srcsizerat <= FTINY)
39	greg	1.4	nopart(si, r);
40	greg	1.1	else {
41			for (i = si->sn; source[i].sflags & SVIRTUAL;
42			i = source[i].sa.sv.sn)
43			; /* partition source */
44	greg	1.4	(*sfun[source[i].so->otype].of->partit)(si, r);
45	greg	1.1	}
46			si->sp = -1;
47			}
48			/* get partition */
49			cent[0] = cent[1] = cent[2] = 0;
50			size[0] = size[1] = size[2] = MAXSPART;
51			parr[0] = 0; parr[1] = si->sp;
52			if (!skipparts(cent, size, parr, si->spt))
53			error(CONSISTENCY, "bad source partition in nextssamp");
54			/* compute sample */
55	greg	2.16	srcp = source + si->sn;
56	greg	1.1	if (dstrsrc > FTINY) { /* jitter sample */
57			dimlist[ndims] = si->sn + 8831;
58			dimlist[ndims+1] = si->sp + 3109;
59			d = urand(ilhash(dimlist,ndims+2)+samplendx);
60	greg	2.16	if (srcp->sflags & SFLAT) {
61	greg	1.1	multisamp(vpos, 2, d);
62	greg	2.12	vpos[SW] = 0.5;
63	greg	1.1	} else
64			multisamp(vpos, 3, d);
65			for (i = 0; i < 3; i++)
66			vpos[i] = dstrsrc * (1. - 2.vpos[i])
67	greg	2.17	(double)size[i]*(1.0/MAXSPART);
68	greg	1.1	} else
69			vpos[0] = vpos[1] = vpos[2] = 0.0;
70
71	greg	2.17	VSUM(vpos, vpos, cent, 1.0/MAXSPART);
72	greg	2.12	/* avoid circular aiming failures */
73	greg	2.16	if ((srcp->sflags & SCIR) && (si->np > 1 \|\| dstrsrc > 0.7)) {
74	greg	2.12	FVECT trim;
75	greg	2.16	if (srcp->sflags & (SFLAT\|SDISTANT)) {
76	greg	2.12	d = 1.12837917; /* correct setflatss() */
77			trim[SU] = dsqrt(1.0 - 0.5vpos[SV]*vpos[SV]);
78			trim[SV] = dsqrt(1.0 - 0.5vpos[SU]*vpos[SU]);
79			trim[SW] = 0.0;
80			} else {
81			trim[SW] = trim[SU] = vpos[SU]*vpos[SU];
82			d = vpos[SV]*vpos[SV];
83			if (d > trim[SW]) trim[SW] = d;
84			trim[SU] += d;
85			d = vpos[SW]*vpos[SW];
86			if (d > trim[SW]) trim[SW] = d;
87			trim[SU] += d;
88	greg	2.15	if (trim[SU] > FTINY*FTINY) {
89			d = 1.0/0.7236; /* correct sphsetsrc() */
90			trim[SW] = trim[SV] = trim[SU] =
91			d*sqrt(trim[SW]/trim[SU]);
92			} else
93			trim[SW] = trim[SV] = trim[SU] = 0.0;
94	greg	2.12	}
95			for (i = 0; i < 3; i++)
96			vpos[i] *= trim[i];
97			}
98	greg	1.1	/* compute direction */
99			for (i = 0; i < 3; i++)
100	greg	2.16	r->rdir[i] = srcp->sloc[i] +
101			vpos[SU]*srcp->ss[SU][i] +
102			vpos[SV]*srcp->ss[SV][i] +
103			vpos[SW]*srcp->ss[SW][i];
104	greg	1.1
105	greg	2.16	if (!(srcp->sflags & SDISTANT))
106	greg	2.17	VSUB(r->rdir, r->rdir, r->rorg);
107	greg	1.1	/* compute distance */
108	greg	1.4	if ((d = normalize(r->rdir)) == 0.0)
109	greg	2.2	goto nextsample; /* at source! */
110	greg	1.1
111			/* compute sample size */
112	greg	2.16	if (srcp->sflags & SFLAT) {
113	greg	2.6	si->dom = sflatform(si->sn, r->rdir);
114	greg	2.17	si->dom = size[SU]size[SV]*(1.0/MAXSPART/MAXSPART);
115	greg	2.16	} else if (srcp->sflags & SCYL) {
116	greg	2.6	si->dom = scylform(si->sn, r->rdir);
117	greg	2.17	si->dom = size[SU](1.0/MAXSPART);
118	greg	1.1	} else {
119	greg	2.17	si->dom = size[SU]size[SV](double)size[SW] *
120			(1.0/MAXSPART/MAXSPART/MAXSPART) ;
121	greg	1.1	}
122	greg	2.16	if (srcp->sflags & SDISTANT) {
123			si->dom *= srcp->ss2;
124	greg	1.1	return(FHUGE);
125	greg	2.6	}
126	greg	2.3	if (si->dom <= 1e-4)
127	greg	2.2	goto nextsample; /* behind source? */
128	greg	2.16	si->dom = srcp->ss2/(dd);
129	greg	1.1	return(d); /* sample OK, return distance */
130			}
131
132
133	greg	2.7	int
134	greg	1.1	skipparts(ct, sz, pp, pt) /* skip to requested partition */
135			int ct[3], sz[3]; /* center and size of partition (returned) */
136			register int pp[2]; /* current index, number to skip (modified) */
137			unsigned char pt; / partition array */
138			{
139			register int p;
140			/* check this partition */
141			p = spart(pt, pp[0]);
142			pp[0]++;
143	schorsch	2.10	if (p == S0) { /* leaf partition */
144	greg	1.1	if (pp[1]) {
145			pp[1]--;
146			return(0); /* not there yet */
147			} else
148			return(1); /* we've arrived */
149	schorsch	2.10	}
150	greg	1.1	/* else check lower */
151			sz[p] >>= 1;
152			ct[p] -= sz[p];
153			if (skipparts(ct, sz, pp, pt))
154			return(1); /* return hit */
155			/* else check upper */
156			ct[p] += sz[p] << 1;
157			if (skipparts(ct, sz, pp, pt))
158			return(1); /* return hit */
159			/* else return to starting position */
160			ct[p] -= sz[p];
161			sz[p] <<= 1;
162			return(0); /* return miss */
163			}
164
165
166	greg	2.7	void
167	greg	1.4	nopart(si, r) /* single source partition */
168	greg	1.1	register SRCINDEX *si;
169	greg	1.4	RAY *r;
170	greg	1.1	{
171			clrpart(si->spt);
172			setpart(si->spt, 0, S0);
173			si->np = 1;
174			}
175
176
177	greg	2.7	void
178	greg	1.4	cylpart(si, r) /* partition a cylinder */
179	greg	1.1	SRCINDEX *si;
180	greg	1.4	register RAY *r;
181	greg	1.1	{
182			double dist2, safedist2, dist2cent, rad2;
183			FVECT v;
184			register SRCREC *sp;
185			int pi;
186			/* first check point location */
187			clrpart(si->spt);
188	greg	1.4	sp = source + si->sn;
189	greg	1.3	rad2 = 1.365 * DOT(sp->ss[SV],sp->ss[SV]);
190	greg	1.4	v[0] = r->rorg[0] - sp->sloc[0];
191			v[1] = r->rorg[1] - sp->sloc[1];
192			v[2] = r->rorg[2] - sp->sloc[2];
193	greg	1.1	dist2 = DOT(v,sp->ss[SU]);
194			safedist2 = DOT(sp->ss[SU],sp->ss[SU]);
195			dist2 *= dist2 / safedist2;
196			dist2cent = DOT(v,v);
197			dist2 = dist2cent - dist2;
198			if (dist2 <= rad2) { /* point inside extended cylinder */
199			si->np = 0;
200			return;
201			}
202	greg	1.4	safedist2 = 4.r->rweightr->rweight/(srcsizeratsrcsizerat);
203	greg	1.5	if (dist2 <= 4.rad2 \|\| / point too close to subdivide */
204			dist2cent >= safedist2) { /* or too far */
205	greg	1.1	setpart(si->spt, 0, S0);
206			si->np = 1;
207			return;
208			}
209			pi = 0;
210	greg	1.4	si->np = cyl_partit(r->rorg, si->spt, &pi, MAXSPART,
211	greg	1.1	sp->sloc, sp->ss[SU], safedist2);
212			}
213
214
215			static int
216			cyl_partit(ro, pt, pi, mp, cent, axis, d2) /* slice a cylinder */
217			FVECT ro;
218			unsigned char *pt;
219			register int *pi;
220			int mp;
221			FVECT cent, axis;
222			double d2;
223			{
224			FVECT newct, newax;
225			int npl, npu;
226
227			if (mp < 2 \|\| dist2(ro, cent) >= d2) { /* hit limit? */
228			setpart(pt, *pi, S0);
229			(*pi)++;
230			return(1);
231			}
232			/* subdivide */
233			setpart(pt, *pi, SU);
234			(*pi)++;
235			newax[0] = .5*axis[0];
236			newax[1] = .5*axis[1];
237			newax[2] = .5*axis[2];
238			d2 *= 0.25;
239			/* lower half */
240			newct[0] = cent[0] - newax[0];
241			newct[1] = cent[1] - newax[1];
242			newct[2] = cent[2] - newax[2];
243	greg	1.2	npl = cyl_partit(ro, pt, pi, mp/2, newct, newax, d2);
244	greg	1.1	/* upper half */
245			newct[0] = cent[0] + newax[0];
246			newct[1] = cent[1] + newax[1];
247			newct[2] = cent[2] + newax[2];
248	greg	1.2	npu = cyl_partit(ro, pt, pi, mp/2, newct, newax, d2);
249	greg	1.1	/* return total */
250			return(npl + npu);
251			}
252
253
254	greg	2.7	void
255	greg	1.4	flatpart(si, r) /* partition a flat source */
256	greg	1.1	register SRCINDEX *si;
257	greg	1.5	register RAY *r;
258	greg	1.1	{
259	schorsch	2.9	register RREAL *vp;
260	greg	1.5	FVECT v;
261	greg	1.1	double du2, dv2;
262			int pi;
263
264	greg	1.5	clrpart(si->spt);
265			vp = source[si->sn].sloc;
266			v[0] = r->rorg[0] - vp[0];
267			v[1] = r->rorg[1] - vp[1];
268			v[2] = r->rorg[2] - vp[2];
269			vp = source[si->sn].snorm;
270	greg	2.11	if (DOT(v,vp) <= 0.) { /* behind source */
271	greg	1.5	si->np = 0;
272			return;
273			}
274	greg	1.4	dv2 = 2.*r->rweight/srcsizerat;
275			dv2 *= dv2;
276	greg	1.1	vp = source[si->sn].ss[SU];
277	greg	1.4	du2 = dv2 * DOT(vp,vp);
278	greg	1.1	vp = source[si->sn].ss[SV];
279	greg	1.4	dv2 *= DOT(vp,vp);
280	greg	1.1	pi = 0;
281	greg	1.4	si->np = flt_partit(r->rorg, si->spt, &pi, MAXSPART,
282			source[si->sn].sloc,
283	greg	1.1	source[si->sn].ss[SU], source[si->sn].ss[SV], du2, dv2);
284			}
285
286
287			static int
288			flt_partit(ro, pt, pi, mp, cent, u, v, du2, dv2) /* partition flatty */
289			FVECT ro;
290			unsigned char *pt;
291			register int *pi;
292			int mp;
293			FVECT cent, u, v;
294			double du2, dv2;
295			{
296			double d2;
297			FVECT newct, newax;
298			int npl, npu;
299
300			if (mp < 2 \|\| ((d2 = dist2(ro, cent)) >= du2
301			&& d2 >= dv2)) { /* hit limit? */
302			setpart(pt, *pi, S0);
303			(*pi)++;
304			return(1);
305			}
306			if (du2 > dv2) { /* subdivide in U */
307			setpart(pt, *pi, SU);
308			(*pi)++;
309			newax[0] = .5*u[0];
310			newax[1] = .5*u[1];
311			newax[2] = .5*u[2];
312			u = newax;
313			du2 *= 0.25;
314			} else { /* subdivide in V */
315			setpart(pt, *pi, SV);
316			(*pi)++;
317			newax[0] = .5*v[0];
318			newax[1] = .5*v[1];
319			newax[2] = .5*v[2];
320			v = newax;
321			dv2 *= 0.25;
322			}
323			/* lower half */
324			newct[0] = cent[0] - newax[0];
325			newct[1] = cent[1] - newax[1];
326			newct[2] = cent[2] - newax[2];
327	greg	1.2	npl = flt_partit(ro, pt, pi, mp/2, newct, u, v, du2, dv2);
328	greg	1.1	/* upper half */
329			newct[0] = cent[0] + newax[0];
330			newct[1] = cent[1] + newax[1];
331			newct[2] = cent[2] + newax[2];
332	greg	1.2	npu = flt_partit(ro, pt, pi, mp/2, newct, u, v, du2, dv2);
333	greg	1.1	/* return total */
334			return(npl + npu);
335			}
336
337
338			double
339			scylform(sn, dir) /* compute cosine for cylinder's projection */
340			int sn;
341			register FVECT dir; /* assume normalized */
342			{
343	schorsch	2.9	register RREAL *dv;
344	greg	1.1	double d;
345
346			dv = source[sn].ss[SU];
347			d = DOT(dir, dv);
348			d *= d / DOT(dv,dv);
349			return(sqrt(1. - d));
350			}