--- ray/src/common/bsdf_t.c 2011/04/19 21:31:22 3.5 +++ ray/src/common/bsdf_t.c 2011/04/24 19:39:21 3.6 @@ -1,5 +1,5 @@ #ifndef lint -static const char RCSid[] = "$Id: bsdf_t.c,v 3.5 2011/04/19 21:31:22 greg Exp $"; +static const char RCSid[] = "$Id: bsdf_t.c,v 3.6 2011/04/24 19:39:21 greg Exp $"; #endif /* * bsdf_t.c @@ -17,7 +17,29 @@ static const char RCSid[] = "$Id: bsdf_t.c,v 3.5 2011/ #include "ezxml.h" #include "bsdf.h" #include "bsdf_t.h" +#include "hilbert.h" +/* Callback function type for SDtraverseTre() */ +typedef int SDtreCallback(float val, const double *cmin, + double csiz, void *cptr); + + /* reference width maximum (1.0) */ +static const unsigned iwmax = (1<<(sizeof(unsigned)*4))-1; + +/* Struct used for our distribution-building callback */ +typedef struct { + int wmin; /* minimum square size so far */ + int wmax; /* maximum square size */ + int nic; /* number of input coordinates */ + int alen; /* current array length */ + int nall; /* number of allocated entries */ + struct outdir_s { + unsigned hent; /* entering Hilbert index */ + int wid; /* this square size */ + float bsdf; /* BSDF for this square */ + } *darr; /* output direction array */ +} SDdistScaffold; + /* Allocate a new scattering distribution node */ static SDNode * SDnewNode(int nd, int lg) @@ -45,7 +67,7 @@ SDnewNode(int nd, int lg) if (st == NULL) { if (lg < 0) sprintf(SDerrorDetail, - "Cannot allocate %d branch BSDF tree", nd); + "Cannot allocate %d branch BSDF tree", 1<st); + free(sdt); +} + /* Add up N-dimensional hypercube array values over the given box */ static double SDiterSum(const float *va, int nd, int siz, const int *imin, const int *imax) @@ -94,7 +125,7 @@ SDiterSum(const float *va, int nd, int siz, const int /* Average BSDF leaves over an orthotope defined by the unit hypercube */ static double -SDavgBox(const SDNode *st, const double *bmin, const double *bmax) +SDavgTreBox(const SDNode *st, const double *bmin, const double *bmax) { int imin[SD_MAXDIM], imax[SD_MAXDIM]; unsigned n; @@ -129,7 +160,7 @@ SDavgBox(const SDNode *st, const double *bmin, const d w *= sbmax[i] - sbmin[i]; } if (w > 1e-10) { - sum += w * SDavgBox(st->u.t[n], sbmin, sbmax); + sum += w * SDavgTreBox(st->u.t[n], sbmin, sbmax); wsum += w; } } @@ -150,58 +181,433 @@ SDavgBox(const SDNode *st, const double *bmin, const d (double)n; } -#endif /* 0 */ +/* Recursive call for SDtraverseTre() */ +static int +SDdotravTre(const SDNode *st, const double *pos, int cmask, + SDtreCallback *cf, void *cptr, + const double *cmin, double csiz) +{ + int rv, rval = 0; + double bmin[SD_MAXDIM]; + int i, n; + /* in branches? */ + if (st->log2GR < 0) { + unsigned skipmask = 0; + csiz *= .5; + for (i = st->ndim; i--; ) + if (1<ndim; n--; ) + if (n & 1<ndim; n--; ) + if (!(n & 1<ndim; n--; ) { + if (1<ndim; i--; ) + if (1<u.t[n], pos, cmask, + cf, cptr, bmin, csiz); + if (rv < 0) + return rv; + } + } else { /* else traverse leaves */ + int clim[SD_MAXDIM][2]; + int cpos[SD_MAXDIM]; + + if (st->log2GR == 0) /* short cut */ + return (*cf)(st->u.v[0], cmin, csiz, cptr); + + csiz /= (double)(1 << st->log2GR); + /* assign coord. ranges */ + for (i = st->ndim; i--; ) + if (1<> st->log2GR; + clim[i][1] = clim[i][0] + 1; + } else { + clim[i][0] = 0; + clim[i][1] = 1 << st->log2GR; + } + /* fill in unused dimensions */ + for (i = SD_MAXDIM; i-- > st->ndim; ) { + clim[i][0] = 0; clim[i][1] = 1; + } +#if (SD_MAXDIM == 4) + bmin[0] = cmin[0] + csiz*clim[0][0]; + for (cpos[0] = clim[0][0]; cpos[0] < clim[0][1]; cpos[0]++) { + bmin[1] = cmin[1] + csiz*clim[1][0]; + for (cpos[1] = clim[1][0]; cpos[1] < clim[1][1]; cpos[1]++) { + bmin[2] = cmin[2] + csiz*clim[2][0]; + for (cpos[2] = clim[2][0]; cpos[2] < clim[2][1]; cpos[2]++) { + bmin[3] = cmin[3] + csiz*(cpos[3] = clim[3][0]); + n = cpos[0]; + for (i = 1; i < st->ndim; i++) + n = (n << st->log2GR) + cpos[i]; + for ( ; cpos[3] < clim[3][1]; cpos[3]++) { + rval += rv = (*cf)(st->u.v[n++], bmin, csiz, cptr); + if (rv < 0) + return rv; + bmin[3] += csiz; + } + bmin[2] += csiz; + } + bmin[1] += csiz; + } + bmin[0] += csiz; + } +#else + _!_ "broken code segment!" +#endif + } + return rval; +} + +/* Traverse a tree, visiting nodes in a slice that fits partial position */ +static int +SDtraverseTre(const SDNode *st, const double *pos, int cmask, + SDtreCallback *cf, void *cptr) +{ + static double czero[SD_MAXDIM]; + int i; + /* check arguments */ + if ((st == NULL) | (cf == NULL)) + return -1; + for (i = st->ndim; i--; ) + if (1<= 1.)) + return -1; + + return SDdotravTre(st, pos, cmask, cf, cptr, czero, 1.); +} + /* Look up tree value at the given grid position */ static float -SDlookupTre(const SDNode *st, const double *pos) +SDlookupTre(const SDNode *st, const double *pos, double *hcube) { double spos[SD_MAXDIM]; int i, n, t; + /* initialize voxel return */ + if (hcube) { + hcube[i = st->ndim] = 1.; + while (i--) + hcube[i] = .0; + } /* climb the tree */ while (st->log2GR < 0) { n = 0; /* move to appropriate branch */ + if (hcube) hcube[st->ndim] *= .5; for (i = st->ndim; i--; ) { spos[i] = 2.*pos[i]; t = (spos[i] >= 1.); n |= t<ndim]; } st = st->u.t[n]; /* avoids tail recursion */ pos = spos; } + if (st->log2GR == 0) /* short cut */ + return st->u.v[0]; n = t = 0; /* find grid array index */ for (i = st->ndim; i--; ) { n += (int)((1<log2GR)*pos[i]) << t; t += st->log2GR; } - return st->u.v[n]; /* XXX no interpolation */ + if (hcube) { /* compute final hypercube */ + hcube[st->ndim] /= (double)(1<log2GR); + for (i = st->ndim; i--; ) + hcube[i] += floor((1<log2GR)*pos[i])*hcube[st->ndim]; + } + return st->u.v[n]; /* no interpolation */ } -/* Compute non-diffuse component for variable-resolution BSDF */ -static int -SDgetTreBSDF(float coef[SDmaxCh], const FVECT outVec, - const FVECT inVec, const void *dist) +/* Query BSDF value and sample hypercube for the given vectors */ +static float +SDqueryTre(const SDTre *sdt, const FVECT outVec, const FVECT inVec, double *hc) { - const SDNode *st = (const SDNode *)dist; - double gridPos[4]; + static const FVECT zvec = {.0, .0, 1.}; + FVECT rOutVec; + double gridPos[4]; + /* check transmission */ + if (!sdt->isxmit ^ outVec[2] > 0 ^ inVec[2] > 0) + return -1.; /* convert vector coordinates */ - if (st->ndim == 3) { /* reduce for isotropic BSDF? */ - static const FVECT zvec = {.0, .0, 1.}; - FVECT rOutVec; + if (sdt->st->ndim == 3) { spinvector(rOutVec, outVec, zvec, -atan2(inVec[1],inVec[0])); - SDdisk2square(gridPos, rOutVec[0], rOutVec[1]); - gridPos[2] = .5 - .5*sqrt(inVec[0]*inVec[0] + inVec[1]*inVec[1]); - } else if (st->ndim == 4) { /* XXX no component identity checks */ - SDdisk2square(gridPos, outVec[0], outVec[1]); - SDdisk2square(gridPos+2, -inVec[0], -inVec[1]); + gridPos[0] = .5 - .5*sqrt(inVec[0]*inVec[0] + inVec[1]*inVec[1]); + SDdisk2square(gridPos+1, rOutVec[0], rOutVec[1]); + } else if (sdt->st->ndim == 4) { + SDdisk2square(gridPos, -inVec[0], -inVec[1]); + SDdisk2square(gridPos+2, outVec[0], outVec[1]); } else - return 0; /* should be internal error */ + return -1.; /* should be internal error */ + + return SDlookupTre(sdt->st, gridPos, hc); +} + +/* Compute non-diffuse component for variable-resolution BSDF */ +static int +SDgetTreBSDF(float coef[SDmaxCh], const FVECT outVec, + const FVECT inVec, SDComponent *sdc) +{ + /* check arguments */ + if ((coef == NULL) | (outVec == NULL) | (inVec == NULL) | (sdc == NULL) + || sdc->dist == NULL) + return 0; /* get nearest BSDF value */ - coef[0] = SDlookupTre(st, gridPos); - return 1; /* monochromatic for now */ + coef[0] = SDqueryTre((SDTre *)sdc->dist, outVec, inVec, NULL); + return (coef[0] >= 0); /* monochromatic for now */ } +/* Callback to build cumulative distribution using SDtraverseTre() */ +static int +build_scaffold(float val, const double *cmin, double csiz, void *cptr) +{ + SDdistScaffold *sp = (SDdistScaffold *)cptr; + int wid = csiz*(double)iwmax + .5; + bitmask_t bmin[2], bmax[2]; + + cmin += sp->nic; /* skip to output coords */ + if (wid < sp->wmin) /* new minimum width? */ + sp->wmin = wid; + if (wid > sp->wmax) /* new maximum? */ + sp->wmax = wid; + if (sp->alen >= sp->nall) { /* need more space? */ + struct outdir_s *ndarr; + sp->nall += 8192; + ndarr = (struct outdir_s *)realloc(sp->darr, + sizeof(struct outdir_s)*sp->nall); + if (ndarr == NULL) + return -1; /* abort build */ + sp->darr = ndarr; + } + /* find Hilbert entry index */ + bmin[0] = cmin[0]*(double)iwmax + .5; + bmin[1] = cmin[1]*(double)iwmax + .5; + bmax[0] = bmin[0] + wid; + bmax[1] = bmin[1] + wid; + hilbert_box_vtx(2, sizeof(bitmask_t), sizeof(unsigned)*4, + 1, bmin, bmax); + sp->darr[sp->alen].hent = hilbert_c2i(2, sizeof(unsigned)*4, bmin); + sp->darr[sp->alen].wid = wid; + sp->darr[sp->alen].bsdf = val; + sp->alen++; /* on to the next entry */ + return 0; +} + +/* Scaffold comparison function for qsort -- ascending Hilbert index */ +static int +sscmp(const void *p1, const void *p2) +{ + return (int)((*(const struct outdir_s *)p1).hent - + (*(const struct outdir_s *)p2).hent); +} + +/* Create a new cumulative distribution for the given input direction */ +static SDTreCDst * +make_cdist(const SDTre *sdt, const double *pos) +{ + const unsigned cumlmax = ~0; + SDdistScaffold myScaffold; + SDTreCDst *cd; + struct outdir_s *sp; + double scale, cursum; + int i; + /* initialize scaffold */ + myScaffold.wmin = iwmax; + myScaffold.wmax = 0; + myScaffold.nic = sdt->st->ndim - 2; + myScaffold.alen = 0; + myScaffold.nall = 8192; + myScaffold.darr = (struct outdir_s *)malloc(sizeof(struct outdir_s) * + myScaffold.nall); + if (myScaffold.darr == NULL) + return NULL; + /* grow the distribution */ + if (SDtraverseTre(sdt->st, pos, (1<carr[0])*myScaffold.alen); + if (cd == NULL) { + free(myScaffold.darr); + return NULL; + } + /* sort the distribution */ + qsort(myScaffold.darr, cd->calen = myScaffold.alen, + sizeof(struct outdir_s), &sscmp); + + /* record input range */ + scale = (double)myScaffold.wmin / iwmax; + for (i = myScaffold.nic; i--; ) { + cd->clim[i][0] = floor(pos[i]/scale + .5) * scale; + cd->clim[i][1] = cd->clim[i][0] + scale; + } + cd->max_psa = myScaffold.wmax / (double)iwmax; + cd->max_psa *= cd->max_psa * M_PI; + cd->isxmit = sdt->isxmit; + cd->cTotal = 1e-20; /* compute directional total */ + sp = myScaffold.darr; + for (i = myScaffold.alen; i--; sp++) + cd->cTotal += sp->bsdf * (double)sp->wid * sp->wid; + cursum = .0; /* go back and get cumulative values */ + scale = (double)cumlmax / cd->cTotal; + sp = myScaffold.darr; + for (i = 0; i < cd->calen; i++, sp++) { + cd->carr[i].cuml = scale*cursum + .5; + cursum += sp->bsdf * (double)sp->wid * sp->wid; + } + cd->carr[i].hndx = ~0; /* make final entry */ + cd->carr[i].cuml = cumlmax; + cd->cTotal *= M_PI/(double)iwmax/iwmax; + /* all done, clean up and return */ + free(myScaffold.darr); + return cd; +} + +/* Find or allocate a cumulative distribution for the given incoming vector */ +const SDCDst * +SDgetTreCDist(const FVECT inVec, SDComponent *sdc) +{ + const SDTre *sdt; + double inCoord[2]; + int vflags; + int i; + SDTreCDst *cd, *cdlast; + /* check arguments */ + if ((inVec == NULL) | (sdc == NULL) || + (sdt = (SDTre *)sdc->dist) == NULL) + return NULL; + if (sdt->st->ndim == 3) /* isotropic BSDF? */ + inCoord[0] = .5 - .5*sqrt(inVec[0]*inVec[0] + inVec[1]*inVec[1]); + else if (sdt->st->ndim == 4) + SDdisk2square(inCoord, -inVec[0], -inVec[1]); + else + return NULL; /* should be internal error */ + cdlast = NULL; /* check for direction in cache list */ + for (cd = (SDTreCDst *)sdc->cdList; cd != NULL; + cdlast = cd, cd = (SDTreCDst *)cd->next) { + for (i = sdt->st->ndim - 2; i--; ) + if ((cd->clim[i][0] > inCoord[i]) | + (inCoord[i] >= cd->clim[i][1])) + break; + if (i < 0) + break; /* means we have a match */ + } + if (cd == NULL) /* need to create new entry? */ + cdlast = cd = make_cdist(sdt, inCoord); + if (cdlast != NULL) { /* move entry to head of cache list */ + cdlast->next = cd->next; + cd->next = sdc->cdList; + sdc->cdList = (SDCDst *)cd; + } + return (SDCDst *)cd; /* ready to go */ +} + +/* Query solid angle for vector(s) */ +static SDError +SDqueryTreProjSA(double *psa, const FVECT v1, const RREAL *v2, + int qflags, SDComponent *sdc) +{ + double myPSA[2]; + /* check arguments */ + if ((psa == NULL) | (v1 == NULL) | (sdc == NULL) || + sdc->dist == NULL) + return SDEargument; + /* get projected solid angle(s) */ + if (v2 != NULL) { + const SDTre *sdt = (SDTre *)sdc->dist; + double hcube[SD_MAXDIM]; + if (SDqueryTre(sdt, v1, v2, hcube) < 0) { + if (qflags == SDqueryVal) + *psa = M_PI; + return SDEnone; + } + myPSA[0] = hcube[sdt->st->ndim]; + myPSA[1] = myPSA[0] *= myPSA[0] * M_PI; + } else { + const SDTreCDst *cd = (const SDTreCDst *)SDgetTreCDist(v1, sdc); + if (cd == NULL) + return SDEmemory; + myPSA[0] = M_PI * (cd->clim[0][1] - cd->clim[0][0]) * + (cd->clim[1][1] - cd->clim[1][0]); + myPSA[1] = cd->max_psa; + } + switch (qflags) { /* record based on flag settings */ + case SDqueryVal: + *psa = myPSA[0]; + break; + case SDqueryMax: + if (myPSA[1] > *psa) + *psa = myPSA[1]; + break; + case SDqueryMin+SDqueryMax: + if (myPSA[1] > psa[1]) + psa[1] = myPSA[1]; + /* fall through */ + case SDqueryMin: + if (myPSA[0] < psa[0]) + psa[0] = myPSA[0]; + break; + } + return SDEnone; +} + +/* Sample cumulative distribution */ +static SDError +SDsampTreCDist(FVECT ioVec, double randX, const SDCDst *cdp) +{ + const unsigned nBitsC = 4*sizeof(bitmask_t); + const unsigned nExtraBits = 8*(sizeof(bitmask_t)-sizeof(unsigned)); + const unsigned maxval = ~0; + const SDTreCDst *cd = (const SDTreCDst *)cdp; + const unsigned target = randX*maxval; + bitmask_t hndx, hcoord[2]; + double gpos[3]; + int i, iupper, ilower; + /* check arguments */ + if ((ioVec == NULL) | (cd == NULL)) + return SDEargument; + /* binary search to find position */ + ilower = 0; iupper = cd->calen; + while ((i = (iupper + ilower) >> 1) != ilower) + if ((long)target >= (long)cd->carr[i].cuml) + ilower = i; + else + iupper = i; + /* localize random position */ + randX = (randX*maxval - cd->carr[ilower].cuml) / + (double)(cd->carr[iupper].cuml - cd->carr[ilower].cuml); + /* index in longer Hilbert curve */ + hndx = (randX*cd->carr[iupper].hndx + (1.-randX)*cd->carr[ilower].hndx) + * (double)((bitmask_t)1 << nExtraBits); + /* convert Hilbert index to vector */ + hilbert_i2c(2, nBitsC, hndx, hcoord); + for (i = 2; i--; ) + gpos[i] = ((double)hcoord[i] + rand()*(1./(RAND_MAX+.5))) / + (double)((bitmask_t)1 << nBitsC); + SDsquare2disk(gpos, gpos[0], gpos[1]); + gpos[2] = 1. - gpos[0]*gpos[0] - gpos[1]*gpos[1]; + if (gpos[2] > 0) /* paranoia, I hope */ + gpos[2] = sqrt(gpos[2]); + if (ioVec[2] > 0 ^ !cd->isxmit) + gpos[2] = -gpos[2]; + VCOPY(ioVec, gpos); + return SDEnone; +} + /* Load a variable-resolution BSDF tree from an open XML file */ SDError SDloadTre(SDData *sd, ezxml_t wtl) @@ -212,8 +618,8 @@ SDloadTre(SDData *sd, ezxml_t wtl) /* Variable resolution BSDF methods */ SDFunc SDhandleTre = { &SDgetTreBSDF, - NULL, - NULL, - NULL, - &SDfreeTre, + &SDqueryTreProjSA, + &SDgetTreCDist, + &SDsampTreCDist, + &SDFreeBTre, };