ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/cv/bsdfmesh.c
(Generate patch)

Comparing ray/src/cv/bsdfmesh.c (file contents):
Revision 2.24 by greg, Sat Mar 15 18:11:37 2014 UTC vs.
Revision 2.32 by greg, Thu Aug 21 19:31:23 2014 UTC

# Line 27 | Line 27 | int                    nprocs = 1;
27                                  /* number of children (-1 in child) */
28   static int              nchild = 0;
29  
30 < typedef struct {
31 <        int             nrows, ncols;   /* array size (matches migration) */
32 <        float           *price;         /* migration prices */
33 <        short           *sord;          /* sort for each row, low to high */
34 <        float           *prow;          /* current price row */
35 < } PRICEMAT;                     /* sorted pricing matrix */
30 > /* Compute average DSF value at the given radius from central vector */
31 > static double
32 > eval_DSFsurround(const RBFNODE *rbf, const FVECT outvec, const double rad)
33 > {
34 >        const int       ninc = 12;
35 >        const double    phinc = 2.*M_PI/ninc;
36 >        double          sum = 0;
37 >        int             n = 0;
38 >        FVECT           tvec;
39 >        int             i;
40 >                                                /* compute initial vector */
41 >        if (output_orient*outvec[2] >= 1.-FTINY) {
42 >                tvec[0] = tvec[2] = 0;
43 >                tvec[1] = 1;
44 >        } else {
45 >                tvec[0] = tvec[1] = 0;
46 >                tvec[2] = 1;
47 >        }
48 >        geodesic(tvec, outvec, tvec, rad, GEOD_RAD);
49 >                                                /* average surrounding DSF */
50 >        for (i = 0; i < ninc; i++) {
51 >                if (i) spinvector(tvec, tvec, outvec, phinc);
52 >                if (tvec[2] > 0 ^ output_orient > 0)
53 >                        continue;
54 >                sum += eval_rbfrep(rbf, tvec) * output_orient*tvec[2];
55 >                ++n;
56 >        }
57 >        if (n < 2)                              /* should never happen! */
58 >                return(sum);
59 >        return(sum/(double)n);
60 > }
61  
62 < #define pricerow(p,i)   ((p)->price + (i)*(p)->ncols)
63 < #define psortrow(p,i)   ((p)->sord + (i)*(p)->ncols)
62 > /* Estimate single-lobe radius for DSF at the given outgoing angle */
63 > static double
64 > est_DSFrad(const RBFNODE *rbf, const FVECT outvec)
65 > {
66 >        const double    rad_epsilon = 0.03;
67 >        const double    DSFtarget = 0.60653066 * eval_rbfrep(rbf,outvec)
68 >                                                * output_orient*outvec[2];
69 >        double          inside_rad = rad_epsilon;
70 >        double          outside_rad = 0.5;
71 >        double          DSFinside = eval_DSFsurround(rbf, outvec, inside_rad);
72 >        double          DSFoutside = eval_DSFsurround(rbf, outvec, outside_rad);
73 > #define interp_rad      inside_rad + (outside_rad-inside_rad) * \
74 >                                (DSFtarget-DSFinside) / (DSFoutside-DSFinside)
75 >                                                /* Newton's method (sort of) */
76 >        do {
77 >                double  test_rad = interp_rad;
78 >                double  DSFtest;
79 >                if (test_rad >= outside_rad)
80 >                        return(test_rad);
81 >                if (test_rad <= inside_rad)
82 >                        return(test_rad*(test_rad>0));
83 >                DSFtest = eval_DSFsurround(rbf, outvec, test_rad);
84 >                if (DSFtest > DSFtarget) {
85 >                        inside_rad = test_rad;
86 >                        DSFinside = DSFtest;
87 >                } else {
88 >                        outside_rad = test_rad;
89 >                        DSFoutside = DSFtest;
90 >                }
91 >                if (DSFoutside >= DSFinside)
92 >                        return(test_rad);
93 >        } while (outside_rad-inside_rad > rad_epsilon);
94 >        return(interp_rad);
95 > #undef interp_rad
96 > }
97  
98 + /* Compute average BSDF peak from current DSF's */
99 + static void
100 + comp_bsdf_spec(void)
101 + {
102 +        double          peak_sum = 0;
103 +        double          rad_sum = 0;
104 +        int             n = 0;
105 +        RBFNODE         *rbf;
106 +        FVECT           sdv;
107 +
108 +        if (dsf_list == NULL) {
109 +                bsdf_spec_peak = 0;
110 +                bsdf_spec_rad = 0;
111 +                return;
112 +        }
113 +        for (rbf = dsf_list; rbf != NULL; rbf = rbf->next) {
114 +                sdv[0] = -rbf->invec[0];
115 +                sdv[1] = -rbf->invec[1];
116 +                sdv[2] = rbf->invec[2]*(2*(input_orient==output_orient) - 1);
117 +                peak_sum += eval_rbfrep(rbf, sdv);
118 +                rad_sum += est_DSFrad(rbf, sdv);
119 +                ++n;
120 +        }
121 +        bsdf_spec_peak = peak_sum/(double)n;
122 +        bsdf_spec_rad = rad_sum/(double)n;
123 + }
124 +
125   /* Create a new migration holder (sharing memory for multiprocessing) */
126   static MIGRATION *
127   new_migration(RBFNODE *from_rbf, RBFNODE *to_rbf)
# Line 180 | Line 265 | neighborhood_dist2(int x0, int y0, int x1, int y1)
265          return(sum2 / (4*rad*(rad+1) + 1));
266   }
267  
268 < /* Comparison routine needed for sorting price row */
269 < static int
270 < msrt_cmp(void *b, const void *p1, const void *p2)
268 > /* Compute distance between two RBF lobes */
269 > double
270 > lobe_distance(RBFVAL *rbf1, RBFVAL *rbf2)
271   {
272 <        PRICEMAT        *pm = (PRICEMAT *)b;
273 <        float           c1 = pm->prow[*(const short *)p1];
274 <        float           c2 = pm->prow[*(const short *)p2];
275 <
276 <        if (c1 > c2) return(1);
277 <        if (c1 < c2) return(-1);
278 <        return(0);
272 >        FVECT   vfrom, vto;
273 >        double  d, res;
274 >                                        /* quadratic cost function */
275 >        ovec_from_pos(vfrom, rbf1->gx, rbf1->gy);
276 >        ovec_from_pos(vto, rbf2->gx, rbf2->gy);
277 >        d = Acos(DOT(vfrom, vto));
278 >        res = d*d;
279 >        d = R2ANG(rbf2->crad) - R2ANG(rbf1->crad);
280 >        res += d*d;
281 >                                        /* neighborhood difference */
282 >        res += NEIGH_FACT2 * neighborhood_dist2( rbf1->gx, rbf1->gy,
283 >                                                rbf2->gx, rbf2->gy );
284 >        return(res);
285   }
286  
196 /* Compute (and allocate) migration price matrix for optimization */
197 static void
198 price_routes(PRICEMAT *pm, const RBFNODE *from_rbf, const RBFNODE *to_rbf)
199 {
200        FVECT   *vto = (FVECT *)malloc(sizeof(FVECT) * to_rbf->nrbf);
201        int     i, j;
287  
203        compute_nDSFs(from_rbf, to_rbf);
204        pm->nrows = from_rbf->nrbf;
205        pm->ncols = to_rbf->nrbf;
206        pm->price = (float *)malloc(sizeof(float) * pm->nrows*pm->ncols);
207        pm->sord = (short *)malloc(sizeof(short) * pm->nrows*pm->ncols);
208        
209        if ((pm->price == NULL) | (pm->sord == NULL) | (vto == NULL)) {
210                fprintf(stderr, "%s: Out of memory in migration_costs()\n",
211                                progname);
212                exit(1);
213        }
214        for (j = to_rbf->nrbf; j--; )           /* save repetitive ops. */
215                ovec_from_pos(vto[j], to_rbf->rbfa[j].gx, to_rbf->rbfa[j].gy);
216
217        for (i = from_rbf->nrbf; i--; ) {
218            const double        from_ang = R2ANG(from_rbf->rbfa[i].crad);
219            FVECT               vfrom;
220            short               *srow;
221            ovec_from_pos(vfrom, from_rbf->rbfa[i].gx, from_rbf->rbfa[i].gy);
222            pm->prow = pricerow(pm,i);
223            srow = psortrow(pm,i);
224            for (j = to_rbf->nrbf; j--; ) {
225                double  d;                      /* quadratic cost function */
226                d = Acos(DOT(vfrom, vto[j]));
227                pm->prow[j] = d*d;
228                d = R2ANG(to_rbf->rbfa[j].crad) - from_ang;
229                pm->prow[j] += d*d;
230                                                /* neighborhood difference */
231                pm->prow[j] += NEIGH_FACT2 * neighborhood_dist2(
232                                from_rbf->rbfa[i].gx, from_rbf->rbfa[i].gy,
233                                to_rbf->rbfa[j].gx, to_rbf->rbfa[j].gy );
234                srow[j] = j;
235            }
236            qsort_r(srow, pm->ncols, sizeof(short), pm, &msrt_cmp);
237        }
238        free(vto);
239 }
240
241 /* Free price matrix */
242 static void
243 free_routes(PRICEMAT *pm)
244 {
245        free(pm->price); pm->price = NULL;
246        free(pm->sord); pm->sord = NULL;
247 }
248
249 /* Compute minimum (optimistic) cost for moving the given source material */
250 static double
251 min_cost(double amt2move, const double *avail, const PRICEMAT *pm, int s)
252 {
253        const short     *srow = psortrow(pm,s);
254        const float     *prow = pricerow(pm,s);
255        double          total_cost = 0;
256        int             j;
257                                                /* move cheapest first */
258        for (j = 0; (j < pm->ncols) & (amt2move > FTINY); j++) {
259                int     d = srow[j];
260                double  amt = (amt2move < avail[d]) ? amt2move : avail[d];
261
262                total_cost += amt * prow[d];
263                amt2move -= amt;
264        }
265        return(total_cost);
266 }
267
268 typedef struct {
269        short   s, d;           /* source and destination */
270        float   dc;             /* discount to push inventory */
271 } ROWSENT;              /* row sort entry */
272
273 /* Compare entries by discounted moving price */
274 static int
275 rmovcmp(void *b, const void *p1, const void *p2)
276 {
277        PRICEMAT        *pm = (PRICEMAT *)b;
278        const ROWSENT   *re1 = (const ROWSENT *)p1;
279        const ROWSENT   *re2 = (const ROWSENT *)p2;
280        double          price_diff;
281
282        if (re1->d < 0) return(re2->d >= 0);
283        if (re2->d < 0) return(-1);
284        price_diff = re1->dc*pricerow(pm,re1->s)[re1->d] -
285                        re2->dc*pricerow(pm,re2->s)[re2->d];
286        if (price_diff > 0) return(1);
287        if (price_diff < 0) return(-1);
288        return(0);
289 }
290
291 /* Take a step in migration by choosing reasonable bucket to transfer */
292 static double
293 migration_step(MIGRATION *mig, double *src_rem, double *dst_rem, PRICEMAT *pm)
294 {
295        const int       max2check = 100;
296        const double    maxamt = 1./(double)pm->ncols;
297        const double    minamt = maxamt*1e-4;
298        double          *src_cost;
299        ROWSENT         *rord;
300        struct {
301                int     s, d;   /* source and destination */
302                double  price;  /* cost per amount moved */
303                double  amt;    /* amount we can move */
304        } cur, best;
305        int             r2check, i, ri;
306        /*
307         * Check cheapest available routes only -- a higher adjusted
308         * destination price implies that another source is closer, so
309         * we can hold off considering more expensive options until
310         * some other (hopefully better) moves have been made.
311         * A discount based on source remaining is supposed to prioritize
312         * movement from large lobes, but it doesn't seem to do much,
313         * so we have it set to 1.0 at the moment.
314         */
315 #define discount(qr)    1.0
316                                                /* most promising row order */
317        rord = (ROWSENT *)malloc(sizeof(ROWSENT)*pm->nrows);
318        if (rord == NULL)
319                goto memerr;
320        for (ri = pm->nrows; ri--; ) {
321            rord[ri].s = ri;
322            rord[ri].d = -1;
323            rord[ri].dc = 1.f;
324            if (src_rem[ri] <= minamt)          /* enough source material? */
325                    continue;
326            for (i = 0; i < pm->ncols; i++)
327                if (dst_rem[ rord[ri].d = psortrow(pm,ri)[i] ] > minamt)
328                        break;
329            if (i >= pm->ncols) {               /* moved all we can? */
330                free(rord);
331                return(.0);
332            }
333            rord[ri].dc = discount(src_rem[ri]);
334        }
335        if (pm->nrows > max2check)              /* sort if too many sources */
336                qsort_r(rord, pm->nrows, sizeof(ROWSENT), pm, &rmovcmp);
337                                                /* allocate cost array */
338        src_cost = (double *)malloc(sizeof(double)*pm->nrows);
339        if (src_cost == NULL)
340                goto memerr;
341        for (i = pm->nrows; i--; )              /* starting costs for diff. */
342                src_cost[i] = min_cost(src_rem[i], dst_rem, pm, i);
343                                                /* find best source & dest. */
344        best.s = best.d = -1; best.price = FHUGE; best.amt = 0;
345        if ((r2check = pm->nrows) > max2check)
346                r2check = max2check;            /* put a limit on search */
347        for (ri = 0; ri < r2check; ri++) {      /* check each source row */
348            double      cost_others = 0;
349            cur.s = rord[ri].s;
350            if ((cur.d = rord[ri].d) < 0 ||
351                        rord[ri].dc*pricerow(pm,cur.s)[cur.d] >= best.price) {
352                if (pm->nrows > max2check) break;       /* sorted end */
353                continue;                       /* else skip this one */
354            }
355            cur.amt = (src_rem[cur.s] < dst_rem[cur.d]) ?
356                                src_rem[cur.s] : dst_rem[cur.d];
357                                                /* don't just leave smidgen */
358            if (cur.amt > maxamt*1.02) cur.amt = maxamt;
359            dst_rem[cur.d] -= cur.amt;          /* add up opportunity costs */
360            for (i = pm->nrows; i--; )
361                if (i != cur.s)
362                    cost_others += min_cost(src_rem[i], dst_rem, pm, i)
363                                        - src_cost[i];
364            dst_rem[cur.d] += cur.amt;          /* undo trial move */
365                                                /* discount effective price */
366            cur.price = ( pricerow(pm,cur.s)[cur.d] + cost_others/cur.amt ) *
367                                        rord[ri].dc;
368            if (cur.price < best.price)         /* are we better than best? */
369                best = cur;
370        }
371        free(src_cost);                         /* clean up */
372        free(rord);
373        if ((best.s < 0) | (best.d < 0))        /* nothing left to move? */
374                return(.0);
375                                                /* else make the actual move */
376        mtx_coef(mig,best.s,best.d) += best.amt;
377        src_rem[best.s] -= best.amt;
378        dst_rem[best.d] -= best.amt;
379        return(best.amt);
380 memerr:
381        fprintf(stderr, "%s: Out of memory in migration_step()\n", progname);
382        exit(1);
383 #undef discount
384 }
385
288   /* Compute and insert migration along directed edge (may fork child) */
289   static MIGRATION *
290   create_migration(RBFNODE *from_rbf, RBFNODE *to_rbf)
291   {
390        const double    end_thresh = 5e-6;
391        PRICEMAT        pmtx;
292          MIGRATION       *newmig;
393        double          *src_rem, *dst_rem;
394        double          total_rem = 1., move_amt;
293          int             i, j;
294                                                  /* check if exists already */
295          for (newmig = from_rbf->ejl; newmig != NULL;
# Line 411 | Line 309 | create_migration(RBFNODE *from_rbf, RBFNODE *to_rbf)
309          newmig = new_migration(from_rbf, to_rbf);
310          if (run_subprocess())
311                  return(newmig);                 /* child continues */
414        price_routes(&pmtx, from_rbf, to_rbf);
415        src_rem = (double *)malloc(sizeof(double)*from_rbf->nrbf);
416        dst_rem = (double *)malloc(sizeof(double)*to_rbf->nrbf);
417        if ((src_rem == NULL) | (dst_rem == NULL)) {
418                fprintf(stderr, "%s: Out of memory in create_migration()\n",
419                                progname);
420                exit(1);
421        }
422                                                /* starting quantities */
423        memset(newmig->mtx, 0, sizeof(float)*from_rbf->nrbf*to_rbf->nrbf);
424        for (i = from_rbf->nrbf; i--; )
425                src_rem[i] = rbf_volume(&from_rbf->rbfa[i]) / from_rbf->vtotal;
426        for (j = to_rbf->nrbf; j--; )
427                dst_rem[j] = rbf_volume(&to_rbf->rbfa[j]) / to_rbf->vtotal;
312  
313 <        do {                                    /* move a bit at a time */
314 <                move_amt = migration_step(newmig, src_rem, dst_rem, &pmtx);
315 <                total_rem -= move_amt;
432 <        } while ((total_rem > end_thresh) & (move_amt > 0));
313 >                                                /* compute transport plan */
314 >        compute_nDSFs(from_rbf, to_rbf);
315 >        plan_transport(newmig);
316  
317          for (i = from_rbf->nrbf; i--; ) {       /* normalize final matrix */
318              double      nf = rbf_volume(&from_rbf->rbfa[i]);
# Line 439 | Line 322 | create_migration(RBFNODE *from_rbf, RBFNODE *to_rbf)
322                  mtx_coef(newmig,i,j) *= nf;     /* row now sums to 1.0 */
323          }
324          end_subprocess();                       /* exit here if subprocess */
442        free_routes(&pmtx);                     /* free working arrays */
443        free(src_rem);
444        free(dst_rem);
325          return(newmig);
326   }
327  
# Line 531 | Line 411 | mesh_from_edge(MIGRATION *edge)
411                                  ej1 = create_migration(tvert[0], edge->rbfv[1]);
412                          mesh_from_edge(ej0);
413                          mesh_from_edge(ej1);
414 +                        return;
415                  }
416 <        } else if (tvert[1] == NULL) {          /* grow mesh on left */
416 >        }
417 >        if (tvert[1] == NULL) {                 /* grow mesh on left */
418                  tvert[1] = find_chull_vert(edge->rbfv[1], edge->rbfv[0]);
419                  if (tvert[1] != NULL) {
420                          if (tvert[1]->ord > edge->rbfv[0]->ord)
# Line 553 | Line 435 | mesh_from_edge(MIGRATION *edge)
435   static void
436   check_normal_incidence(void)
437   {
438 <        static const FVECT      norm_vec = {.0, .0, 1.};
438 >        static FVECT            norm_vec = {.0, .0, 1.};
439          const int               saved_nprocs = nprocs;
440          RBFNODE                 *near_rbf, *mir_rbf, *rbf;
441          double                  bestd;
442          int                     n;
443  
562
444          if (dsf_list == NULL)
445                  return;                         /* XXX should be error? */
446          near_rbf = dsf_list;
# Line 609 | Line 490 | check_normal_incidence(void)
490          nprocs = 1;                             /* compute migration matrix */
491          if (create_migration(mir_rbf, near_rbf) == NULL)
492                  exit(1);                        /* XXX should never happen! */
493 <                                                /* interpolate normal dist. */
494 <        rbf = e_advect_rbf(mig_list, norm_vec, 2*near_rbf->nrbf);
493 >        norm_vec[2] = input_orient;             /* interpolate normal dist. */
494 >        rbf = e_advect_rbf(mig_list, norm_vec, 0);
495          nprocs = saved_nprocs;                  /* final clean-up */
496          free(mir_rbf);
497          free(mig_list);
# Line 630 | Line 511 | build_mesh(void)
511          double          best2 = M_PI*M_PI;
512          RBFNODE         *shrt_edj[2];
513          RBFNODE         *rbf0, *rbf1;
514 +                                                /* average specular peak */
515 +        comp_bsdf_spec();
516                                                  /* add normal if needed */
517          check_normal_incidence();
518                                                  /* check if isotropic */

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines