src/rt/srcsamp.c

#ifndef lint
static const char       RCSid[] = "$Id: srcsamp.c,v 2.21 2024/11/09 15:21:32 greg Exp $";
#endif
/*
 * Source sampling routines
 *
 *  External symbols declared in source.h
 */

#include "copyright.h"

#include  "ray.h"

#include  "source.h"

#include  "random.h"

#ifdef SSKIPOPT
/* The following table is used for skipping sources */
static uby8     *srcskipflags = NULL;           /* source inclusion lookup */
static int      ssf_count = 0;                  /* number of flag entries */
static int      ssf_max = 0;                    /* current array size */
static uby8     *ssf_noskip = NULL;             /* set of zero flags */

uby8            *ssf_select = NULL;             /* sources we may skip */

/* Find/allocate source skip flag entry (free all if NULL) */
int
sskip_rsi(uby8 *flags)
{
        uby8    *flp;
        int     i;

        if (flags == NULL) {            /* means clear all */
                efree(srcskipflags); srcskipflags = NULL;
                ssf_count = ssf_max = 0;
                sskip_free(ssf_noskip);
                sskip_free(ssf_select);
                return(0);
        }
        if (ssf_noskip == NULL)         /* first call? */
                ssf_noskip = sskip_new();

        if (sskip_eq(flags, ssf_noskip))
                return(-1);             /* nothing to skip */
                                        /* search recent entries */
        flp = srcskipflags + ssf_count*SSKIPFLSIZ;
        for (i = ssf_count; i-- > 0; )
                if (sskip_eq(flp -= SSKIPFLSIZ, flags))
                        return(-2-i);   /* found it! */
                                        /* else tack on new entry */
        if (ssf_count >= ssf_max) {     /* need more space? */
fprintf(stderr, "DEBUG: skip flag array > %d entries (%.2f MBytes)\n",
ssf_count, SSKIPFLSIZ/1024./1024.*ssf_count);
                ssf_max = ssf_count + (ssf_count>>2) + 64;
                if (ssf_max <= ssf_count &&
                                (ssf_max = ssf_count+1024) <= ssf_count)
                        error(SYSTEM, "out of space in sskip_rsi()");

                srcskipflags = (uby8 *)erealloc(srcskipflags,
                                                ssf_max*SSKIPFLSIZ);
        }
        sskip_cpy(srcskipflags + ssf_count*SSKIPFLSIZ, flags);

        return(-2 - ssf_count++);       /* return index (< -1) */
}

/* Get skip flags associated with RAY rsrc index (or NULL) */
uby8 *
sskip_flags(int rsi)
{
        if (rsi >= -1)
                return(ssf_noskip);

        if ((rsi = -2 - rsi) >= ssf_count)
                error(CONSISTENCY, "bad index to sskip_flags()");

        return(srcskipflags + rsi*SSKIPFLSIZ);
}

/* OR in a second set of flags into a first */
void
sskip_addflags(uby8 *dfl, const uby8 *sfl)
{
        int     nb = SSKIPFLSIZ;

        while (nb--)
                *dfl++ |= *sfl++;
}
#endif

int
srcskip(                        /* pre-emptive test for source to skip */
        int  sn,
        RAY  *r
)
{
        SRCREC  *sp = source + sn;

        if (sp->sflags & SSKIP)
                return(1);
#ifdef SSKIPOPT
        if (r->rsrc < -1 &&     /* ray has custom skip flags? */
                        sskip_chk(sskip_flags(r->rsrc), sn))
                return(1);
#endif
        if ((sp->sflags & (SPROX|SDISTANT)) != SPROX)
                return(0);

        return(dist2(r->rorg, sp->sloc) >
                        (sp->sl.prox + sp->srad)*(sp->sl.prox + sp->srad));
}

double
nextssamp(                      /* compute sample for source, rtn. distance */
        RAY  *r,                /* origin is read, direction is set */
        SRCINDEX  *si           /* source index (modified to current) */
)
{
        int  cent[3], size[3], parr[2];
        SRCREC  *srcp;
        double  vpos[3];
        double  d;
        int  i;
nextsample:
        while (++si->sp >= si->np) {    /* get next sample */
                if (++si->sn >= nsources)
                        return(0.0);    /* no more */
                if (srcskip(si->sn, r))
                        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(                      /* skip to requested partition */
        int  ct[3],
        int  sz[3],             /* center and size of partition (returned) */
        int  pp[2],             /* current index, number to skip (modified) */
        unsigned char  *pt      /* partition array */
)
{
        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(                         /* single source partition */
        SRCINDEX  *si,
        RAY  *r
)
{
        clrpart(si->spt);
        setpart(si->spt, 0, S0);
        si->np = 1;
}


static int
cyl_partit(                             /* slice a cylinder */
        FVECT  ro,
        unsigned char  *pt,
        int  *pi,
        int  mp,
        FVECT  cent,
        FVECT  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
cylpart(                        /* partition a cylinder */
        SRCINDEX  *si,
        RAY  *r
)
{
        double  dist2, safedist2, dist2cent, rad2;
        FVECT  v;
        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
flt_partit(                             /* partition flatty */
        FVECT  ro,
        unsigned char  *pt,
        int  *pi,
        int  mp,
        FVECT  cent,
        FVECT  u,
        FVECT  v,
        double  du2,
        double  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);
}


void
flatpart(                               /* partition a flat source */
        SRCINDEX  *si,
        RAY  *r
)
{
        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);
}


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

        dv = source[sn].ss[SU];
        d = DOT(dir, dv);
        d *= d / DOT(dv,dv);
        return(sqrt(1. - d));
}
Revision:	2.22
Committed:	Fri Nov 15 20:47:42 2024 UTC (6 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.21:	+79 -2 lines
Log Message:	feat(rpict): Experimental source skipping option with -DSSKIPOPT compile flag
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.22	static const char RCSid[] = "$Id: srcsamp.c,v 2.21 2024/11/09 15:21:32 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	greg	2.22	#ifdef SSKIPOPT
19			/* The following table is used for skipping sources */
20			static uby8 srcskipflags = NULL; / source inclusion lookup */
21			static int ssf_count = 0; /* number of flag entries */
22			static int ssf_max = 0; /* current array size */
23			static uby8 ssf_noskip = NULL; / set of zero flags */
24
25			uby8 ssf_select = NULL; / sources we may skip */
26
27			/* Find/allocate source skip flag entry (free all if NULL) */
28			int
29			sskip_rsi(uby8 *flags)
30			{
31			uby8 *flp;
32			int i;
33
34			if (flags == NULL) { /* means clear all */
35			efree(srcskipflags); srcskipflags = NULL;
36			ssf_count = ssf_max = 0;
37			sskip_free(ssf_noskip);
38			sskip_free(ssf_select);
39			return(0);
40			}
41			if (ssf_noskip == NULL) /* first call? */
42			ssf_noskip = sskip_new();
43
44			if (sskip_eq(flags, ssf_noskip))
45			return(-1); /* nothing to skip */
46			/* search recent entries */
47			flp = srcskipflags + ssf_count*SSKIPFLSIZ;
48			for (i = ssf_count; i-- > 0; )
49			if (sskip_eq(flp -= SSKIPFLSIZ, flags))
50			return(-2-i); /* found it! */
51			/* else tack on new entry */
52			if (ssf_count >= ssf_max) { /* need more space? */
53			fprintf(stderr, "DEBUG: skip flag array > %d entries (%.2f MBytes)\n",
54			ssf_count, SSKIPFLSIZ/1024./1024.*ssf_count);
55			ssf_max = ssf_count + (ssf_count>>2) + 64;
56			if (ssf_max <= ssf_count &&
57			(ssf_max = ssf_count+1024) <= ssf_count)
58			error(SYSTEM, "out of space in sskip_rsi()");
59
60			srcskipflags = (uby8 *)erealloc(srcskipflags,
61			ssf_max*SSKIPFLSIZ);
62			}
63			sskip_cpy(srcskipflags + ssf_count*SSKIPFLSIZ, flags);
64
65			return(-2 - ssf_count++); /* return index (< -1) */
66			}
67
68			/* Get skip flags associated with RAY rsrc index (or NULL) */
69			uby8 *
70			sskip_flags(int rsi)
71			{
72			if (rsi >= -1)
73			return(ssf_noskip);
74
75			if ((rsi = -2 - rsi) >= ssf_count)
76			error(CONSISTENCY, "bad index to sskip_flags()");
77
78			return(srcskipflags + rsi*SSKIPFLSIZ);
79			}
80
81			/* OR in a second set of flags into a first */
82			void
83			sskip_addflags(uby8 dfl, const uby8 sfl)
84			{
85			int nb = SSKIPFLSIZ;
86
87			while (nb--)
88			dfl++ \|= sfl++;
89			}
90			#endif
91	greg	1.1
92	greg	2.21	int
93			srcskip( /* pre-emptive test for source to skip */
94			int sn,
95			RAY *r
96	greg	2.18	)
97			{
98	greg	2.21	SRCREC *sp = source + sn;
99
100	greg	2.18	if (sp->sflags & SSKIP)
101			return(1);
102	greg	2.22	#ifdef SSKIPOPT
103			if (r->rsrc < -1 && /* ray has custom skip flags? */
104			sskip_chk(sskip_flags(r->rsrc), sn))
105			return(1);
106			#endif
107	greg	2.18	if ((sp->sflags & (SPROX\|SDISTANT)) != SPROX)
108			return(0);
109
110	greg	2.21	return(dist2(r->rorg, sp->sloc) >
111	greg	2.18	(sp->sl.prox + sp->srad)*(sp->sl.prox + sp->srad));
112			}
113	greg	2.5
114	greg	1.1	double
115	greg	2.18	nextssamp( /* compute sample for source, rtn. distance */
116			RAY r, / origin is read, direction is set */
117	greg	2.21	SRCINDEX si / source index (modified to current) */
118	greg	2.18	)
119	greg	1.1	{
120			int cent[3], size[3], parr[2];
121	greg	2.16	SRCREC *srcp;
122	greg	2.19	double vpos[3];
123	greg	1.1	double d;
124	greg	2.18	int i;
125	greg	2.2	nextsample:
126	greg	1.1	while (++si->sp >= si->np) { /* get next sample */
127			if (++si->sn >= nsources)
128			return(0.0); /* no more */
129	greg	2.21	if (srcskip(si->sn, r))
130	greg	1.7	si->np = 0;
131			else if (srcsizerat <= FTINY)
132	greg	1.4	nopart(si, r);
133	greg	1.1	else {
134			for (i = si->sn; source[i].sflags & SVIRTUAL;
135			i = source[i].sa.sv.sn)
136			; /* partition source */
137	greg	1.4	(*sfun[source[i].so->otype].of->partit)(si, r);
138	greg	1.1	}
139			si->sp = -1;
140			}
141			/* get partition */
142			cent[0] = cent[1] = cent[2] = 0;
143			size[0] = size[1] = size[2] = MAXSPART;
144			parr[0] = 0; parr[1] = si->sp;
145			if (!skipparts(cent, size, parr, si->spt))
146			error(CONSISTENCY, "bad source partition in nextssamp");
147			/* compute sample */
148	greg	2.16	srcp = source + si->sn;
149	greg	1.1	if (dstrsrc > FTINY) { /* jitter sample */
150			dimlist[ndims] = si->sn + 8831;
151			dimlist[ndims+1] = si->sp + 3109;
152			d = urand(ilhash(dimlist,ndims+2)+samplendx);
153	greg	2.16	if (srcp->sflags & SFLAT) {
154	greg	1.1	multisamp(vpos, 2, d);
155	greg	2.12	vpos[SW] = 0.5;
156	greg	1.1	} else
157			multisamp(vpos, 3, d);
158			for (i = 0; i < 3; i++)
159			vpos[i] = dstrsrc * (1. - 2.vpos[i])
160	greg	2.17	(double)size[i]*(1.0/MAXSPART);
161	greg	1.1	} else
162			vpos[0] = vpos[1] = vpos[2] = 0.0;
163
164	greg	2.17	VSUM(vpos, vpos, cent, 1.0/MAXSPART);
165	greg	2.12	/* avoid circular aiming failures */
166	greg	2.20	if ((srcp->sflags & SCIR) && (si->np > 1) \| (dstrsrc > 0.7)) {
167	greg	2.12	FVECT trim;
168	greg	2.16	if (srcp->sflags & (SFLAT\|SDISTANT)) {
169	greg	2.12	d = 1.12837917; /* correct setflatss() */
170			trim[SU] = dsqrt(1.0 - 0.5vpos[SV]*vpos[SV]);
171			trim[SV] = dsqrt(1.0 - 0.5vpos[SU]*vpos[SU]);
172			trim[SW] = 0.0;
173			} else {
174			trim[SW] = trim[SU] = vpos[SU]*vpos[SU];
175			d = vpos[SV]*vpos[SV];
176			if (d > trim[SW]) trim[SW] = d;
177			trim[SU] += d;
178			d = vpos[SW]*vpos[SW];
179			if (d > trim[SW]) trim[SW] = d;
180			trim[SU] += d;
181	greg	2.15	if (trim[SU] > FTINY*FTINY) {
182			d = 1.0/0.7236; /* correct sphsetsrc() */
183			trim[SW] = trim[SV] = trim[SU] =
184			d*sqrt(trim[SW]/trim[SU]);
185			} else
186			trim[SW] = trim[SV] = trim[SU] = 0.0;
187	greg	2.12	}
188			for (i = 0; i < 3; i++)
189			vpos[i] *= trim[i];
190			}
191	greg	1.1	/* compute direction */
192			for (i = 0; i < 3; i++)
193	greg	2.16	r->rdir[i] = srcp->sloc[i] +
194			vpos[SU]*srcp->ss[SU][i] +
195			vpos[SV]*srcp->ss[SV][i] +
196			vpos[SW]*srcp->ss[SW][i];
197	greg	1.1
198	greg	2.16	if (!(srcp->sflags & SDISTANT))
199	greg	2.17	VSUB(r->rdir, r->rdir, r->rorg);
200	greg	1.1	/* compute distance */
201	greg	1.4	if ((d = normalize(r->rdir)) == 0.0)
202	greg	2.2	goto nextsample; /* at source! */
203	greg	1.1
204			/* compute sample size */
205	greg	2.16	if (srcp->sflags & SFLAT) {
206	greg	2.6	si->dom = sflatform(si->sn, r->rdir);
207	greg	2.17	si->dom = size[SU]size[SV]*(1.0/MAXSPART/MAXSPART);
208	greg	2.16	} else if (srcp->sflags & SCYL) {
209	greg	2.6	si->dom = scylform(si->sn, r->rdir);
210	greg	2.17	si->dom = size[SU](1.0/MAXSPART);
211	greg	1.1	} else {
212	greg	2.17	si->dom = size[SU]size[SV](double)size[SW] *
213			(1.0/MAXSPART/MAXSPART/MAXSPART) ;
214	greg	1.1	}
215	greg	2.16	if (srcp->sflags & SDISTANT) {
216			si->dom *= srcp->ss2;
217	greg	1.1	return(FHUGE);
218	greg	2.6	}
219	greg	2.3	if (si->dom <= 1e-4)
220	greg	2.2	goto nextsample; /* behind source? */
221	greg	2.16	si->dom = srcp->ss2/(dd);
222	greg	1.1	return(d); /* sample OK, return distance */
223			}
224
225
226	greg	2.7	int
227	greg	2.18	skipparts( /* skip to requested partition */
228			int ct[3],
229			int sz[3], /* center and size of partition (returned) */
230			int pp[2], /* current index, number to skip (modified) */
231			unsigned char pt / partition array */
232			)
233	greg	1.1	{
234	greg	2.18	int p;
235	greg	1.1	/* check this partition */
236			p = spart(pt, pp[0]);
237			pp[0]++;
238	schorsch	2.10	if (p == S0) { /* leaf partition */
239	greg	1.1	if (pp[1]) {
240			pp[1]--;
241			return(0); /* not there yet */
242			} else
243			return(1); /* we've arrived */
244	schorsch	2.10	}
245	greg	1.1	/* else check lower */
246			sz[p] >>= 1;
247			ct[p] -= sz[p];
248			if (skipparts(ct, sz, pp, pt))
249			return(1); /* return hit */
250			/* else check upper */
251			ct[p] += sz[p] << 1;
252			if (skipparts(ct, sz, pp, pt))
253			return(1); /* return hit */
254			/* else return to starting position */
255			ct[p] -= sz[p];
256			sz[p] <<= 1;
257			return(0); /* return miss */
258			}
259
260
261	greg	2.7	void
262	greg	2.18	nopart( /* single source partition */
263			SRCINDEX *si,
264			RAY *r
265			)
266	greg	1.1	{
267			clrpart(si->spt);
268			setpart(si->spt, 0, S0);
269			si->np = 1;
270			}
271
272
273			static int
274	greg	2.18	cyl_partit( /* slice a cylinder */
275			FVECT ro,
276			unsigned char *pt,
277			int *pi,
278			int mp,
279			FVECT cent,
280			FVECT axis,
281			double d2
282			)
283	greg	1.1	{
284			FVECT newct, newax;
285			int npl, npu;
286
287			if (mp < 2 \|\| dist2(ro, cent) >= d2) { /* hit limit? */
288			setpart(pt, *pi, S0);
289			(*pi)++;
290			return(1);
291			}
292			/* subdivide */
293			setpart(pt, *pi, SU);
294			(*pi)++;
295			newax[0] = .5*axis[0];
296			newax[1] = .5*axis[1];
297			newax[2] = .5*axis[2];
298			d2 *= 0.25;
299			/* lower half */
300			newct[0] = cent[0] - newax[0];
301			newct[1] = cent[1] - newax[1];
302			newct[2] = cent[2] - newax[2];
303	greg	1.2	npl = cyl_partit(ro, pt, pi, mp/2, newct, newax, d2);
304	greg	1.1	/* upper half */
305			newct[0] = cent[0] + newax[0];
306			newct[1] = cent[1] + newax[1];
307			newct[2] = cent[2] + newax[2];
308	greg	1.2	npu = cyl_partit(ro, pt, pi, mp/2, newct, newax, d2);
309	greg	1.1	/* return total */
310			return(npl + npu);
311			}
312
313
314	greg	2.7	void
315	greg	2.18	cylpart( /* partition a cylinder */
316			SRCINDEX *si,
317			RAY *r
318			)
319	greg	1.1	{
320	greg	2.18	double dist2, safedist2, dist2cent, rad2;
321	greg	1.5	FVECT v;
322	greg	2.18	SRCREC *sp;
323	greg	1.1	int pi;
324	greg	2.18	/* first check point location */
325	greg	1.5	clrpart(si->spt);
326	greg	2.18	sp = source + si->sn;
327			rad2 = 1.365 * DOT(sp->ss[SV],sp->ss[SV]);
328			v[0] = r->rorg[0] - sp->sloc[0];
329			v[1] = r->rorg[1] - sp->sloc[1];
330			v[2] = r->rorg[2] - sp->sloc[2];
331			dist2 = DOT(v,sp->ss[SU]);
332			safedist2 = DOT(sp->ss[SU],sp->ss[SU]);
333			dist2 *= dist2 / safedist2;
334			dist2cent = DOT(v,v);
335			dist2 = dist2cent - dist2;
336			if (dist2 <= rad2) { /* point inside extended cylinder */
337	greg	1.5	si->np = 0;
338			return;
339			}
340	greg	2.18	safedist2 = 4.r->rweightr->rweight/(srcsizeratsrcsizerat);
341			if (dist2 <= 4.rad2 \|\| / point too close to subdivide */
342			dist2cent >= safedist2) { /* or too far */
343			setpart(si->spt, 0, S0);
344			si->np = 1;
345			return;
346			}
347	greg	1.1	pi = 0;
348	greg	2.18	si->np = cyl_partit(r->rorg, si->spt, &pi, MAXSPART,
349			sp->sloc, sp->ss[SU], safedist2);
350	greg	1.1	}
351
352
353			static int
354	greg	2.18	flt_partit( /* partition flatty */
355			FVECT ro,
356			unsigned char *pt,
357			int *pi,
358			int mp,
359			FVECT cent,
360			FVECT u,
361			FVECT v,
362			double du2,
363			double dv2
364			)
365	greg	1.1	{
366			double d2;
367			FVECT newct, newax;
368			int npl, npu;
369
370			if (mp < 2 \|\| ((d2 = dist2(ro, cent)) >= du2
371			&& d2 >= dv2)) { /* hit limit? */
372			setpart(pt, *pi, S0);
373			(*pi)++;
374			return(1);
375			}
376			if (du2 > dv2) { /* subdivide in U */
377			setpart(pt, *pi, SU);
378			(*pi)++;
379			newax[0] = .5*u[0];
380			newax[1] = .5*u[1];
381			newax[2] = .5*u[2];
382			u = newax;
383			du2 *= 0.25;
384			} else { /* subdivide in V */
385			setpart(pt, *pi, SV);
386			(*pi)++;
387			newax[0] = .5*v[0];
388			newax[1] = .5*v[1];
389			newax[2] = .5*v[2];
390			v = newax;
391			dv2 *= 0.25;
392			}
393			/* lower half */
394			newct[0] = cent[0] - newax[0];
395			newct[1] = cent[1] - newax[1];
396			newct[2] = cent[2] - newax[2];
397	greg	1.2	npl = flt_partit(ro, pt, pi, mp/2, newct, u, v, du2, dv2);
398	greg	1.1	/* upper half */
399			newct[0] = cent[0] + newax[0];
400			newct[1] = cent[1] + newax[1];
401			newct[2] = cent[2] + newax[2];
402	greg	1.2	npu = flt_partit(ro, pt, pi, mp/2, newct, u, v, du2, dv2);
403	greg	1.1	/* return total */
404			return(npl + npu);
405			}
406
407
408	greg	2.18	void
409			flatpart( /* partition a flat source */
410			SRCINDEX *si,
411			RAY *r
412			)
413			{
414			RREAL *vp;
415			FVECT v;
416			double du2, dv2;
417			int pi;
418
419			clrpart(si->spt);
420			vp = source[si->sn].sloc;
421			v[0] = r->rorg[0] - vp[0];
422			v[1] = r->rorg[1] - vp[1];
423			v[2] = r->rorg[2] - vp[2];
424			vp = source[si->sn].snorm;
425			if (DOT(v,vp) <= 0.) { /* behind source */
426			si->np = 0;
427			return;
428			}
429			dv2 = 2.*r->rweight/srcsizerat;
430			dv2 *= dv2;
431			vp = source[si->sn].ss[SU];
432			du2 = dv2 * DOT(vp,vp);
433			vp = source[si->sn].ss[SV];
434			dv2 *= DOT(vp,vp);
435			pi = 0;
436			si->np = flt_partit(r->rorg, si->spt, &pi, MAXSPART,
437			source[si->sn].sloc,
438			source[si->sn].ss[SU], source[si->sn].ss[SV], du2, dv2);
439			}
440
441
442	greg	1.1	double
443	greg	2.18	scylform( /* compute cosine for cylinder's projection */
444			int sn,
445			FVECT dir /* assume normalized */
446			)
447	greg	1.1	{
448	greg	2.18	RREAL *dv;
449	greg	1.1	double d;
450
451			dv = source[sn].ss[SU];
452			d = DOT(dir, dv);
453			d *= d / DOT(dv,dv);
454			return(sqrt(1. - d));
455			}