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.10 by greg, Thu Sep 26 14:57:18 2013 UTC vs.
Revision 2.11 by greg, Thu Oct 24 16:11:37 2013 UTC

# Line 198 | Line 198 | free_routes(PRICEMAT *pm)
198   static double
199   min_cost(double amt2move, const double *avail, const PRICEMAT *pm, int s)
200   {
201 +        const short     *srow = psortrow(pm,s);
202 +        const float     *prow = pricerow(pm,s);
203          double          total_cost = 0;
204          int             j;
203
204        if (amt2move <= FTINY)                  /* pre-emptive check */
205                return(.0);
205                                                  /* move cheapest first */
206 <        for (j = 0; j < pm->ncols && amt2move > FTINY; j++) {
207 <                int     d = psortrow(pm,s)[j];
206 >        for (j = 0; (j < pm->ncols) & (amt2move > FTINY); j++) {
207 >                int     d = srow[j];
208                  double  amt = (amt2move < avail[d]) ? amt2move : avail[d];
209  
210 <                total_cost += amt * pricerow(pm,s)[d];
210 >                total_cost += amt * prow[d];
211                  amt2move -= amt;
212          }
213          return(total_cost);
214   }
215  
216 < /* Take a step in migration by choosing optimal bucket to transfer */
216 > /* Compare entries by moving price */
217 > static int
218 > rmovcmp(void *b, const void *p1, const void *p2)
219 > {
220 >        PRICEMAT        *pm = (PRICEMAT *)b;
221 >        const short     *ij1 = (const short *)p1;
222 >        const short     *ij2 = (const short *)p2;
223 >        float           price_diff;
224 >
225 >        if (ij1[1] < 0) return(ij2[1] >= 0);
226 >        if (ij2[1] < 0) return(-1);
227 >        price_diff = pricerow(pm,ij1[0])[ij1[1]] - pricerow(pm,ij2[0])[ij2[1]];
228 >        if (price_diff > 0) return(1);
229 >        if (price_diff < 0) return(-1);
230 >        return(0);
231 > }
232 >
233 > /* Take a step in migration by choosing reasonable bucket to transfer */
234   static double
235 < migration_step(MIGRATION *mig, double *src_rem, double *dst_rem, const PRICEMAT *pm)
235 > migration_step(MIGRATION *mig, double *src_rem, double *dst_rem, PRICEMAT *pm)
236   {
237 +        const int       max2check = 100;
238          const double    maxamt = 1./(double)pm->ncols;
239          const double    minamt = maxamt*5e-6;
240          double          *src_cost;
241 +        short           (*rord)[2];
242          struct {
243                  int     s, d;   /* source and destination */
244                  double  price;  /* price estimate per amount moved */
245                  double  amt;    /* amount we can move */
246          } cur, best;
247 <        int             i;
247 >        int             r2check, i, ri;
248 >        /*
249 >         * Check cheapest available routes only -- a higher adjusted
250 >         * destination price implies that another source is closer, so
251 >         * we can hold off considering more expensive options until
252 >         * some other (hopefully better) moves have been made.
253 >         */
254 >                                                /* most promising row order */
255 >        rord = (short (*)[2])malloc(sizeof(short)*2*pm->nrows);
256 >        if (rord == NULL)
257 >                goto memerr;
258 >        for (ri = pm->nrows; ri--; ) {
259 >            rord[ri][0] = ri;
260 >            rord[ri][1] = -1;
261 >            if (src_rem[ri] <= minamt)          /* enough source material? */
262 >                    continue;
263 >            for (i = 0; i < pm->ncols; i++)
264 >                if (dst_rem[ rord[ri][1] = psortrow(pm,ri)[i] ] > minamt)
265 >                        break;
266 >            if (i >= pm->ncols) {               /* moved all we can? */
267 >                free(rord);
268 >                return(.0);
269 >            }
270 >        }
271 >        if (pm->nrows > max2check)              /* sort if too many sources */
272 >                qsort_r(rord, pm->nrows, sizeof(short)*2, pm, &rmovcmp);
273                                                  /* allocate cost array */
274          src_cost = (double *)malloc(sizeof(double)*pm->nrows);
275 <        if (src_cost == NULL) {
276 <                fprintf(stderr, "%s: Out of memory in migration_step()\n",
234 <                                progname);
235 <                exit(1);
236 <        }
275 >        if (src_cost == NULL)
276 >                goto memerr;
277          for (i = pm->nrows; i--; )              /* starting costs for diff. */
278                  src_cost[i] = min_cost(src_rem[i], dst_rem, pm, i);
239
279                                                  /* find best source & dest. */
280          best.s = best.d = -1; best.price = FHUGE; best.amt = 0;
281 <        for (cur.s = pm->nrows; cur.s--; ) {
281 >        if ((r2check = pm->nrows) > max2check)
282 >                r2check = max2check;            /* put a limit on search */
283 >        for (ri = 0; ri < r2check; ri++) {      /* check each source row */
284              double      cost_others = 0;
285 <
286 <            if (src_rem[cur.s] <= minamt)
287 <                    continue;
288 <                                                /* examine cheapest dest. */
289 <            for (i = 0; i < pm->ncols; i++)
290 <                if (dst_rem[ cur.d = psortrow(pm,cur.s)[i] ] > minamt)
250 <                        break;
251 <            if (i >= pm->ncols)
252 <                break;
253 <            if ((cur.price = pricerow(pm,cur.s)[cur.d]) >= best.price)
254 <                continue;                       /* no point checking further */
285 >            cur.s = rord[ri][0];
286 >            if ((cur.d = rord[ri][1]) < 0 ||
287 >                        (cur.price = pricerow(pm,cur.s)[cur.d]) >= best.price) {
288 >                if (pm->nrows > max2check) break;       /* sorted end */
289 >                continue;                       /* else skip this one */
290 >            }
291              cur.amt = (src_rem[cur.s] < dst_rem[cur.d]) ?
292                                  src_rem[cur.s] : dst_rem[cur.d];
293 <            if (cur.amt > maxamt) cur.amt = maxamt;
294 <            dst_rem[cur.d] -= cur.amt;          /* add up differential costs */
293 >                                                /* don't just leave smidgen */
294 >            if (cur.amt > maxamt*1.02) cur.amt = maxamt;
295 >            dst_rem[cur.d] -= cur.amt;          /* add up opportunity costs */
296              for (i = pm->nrows; i--; )
297                  if (i != cur.s)
298 <                        cost_others += min_cost(src_rem[i], dst_rem, pm, i)
298 >                    cost_others += min_cost(src_rem[i], dst_rem, pm, i)
299                                          - src_cost[i];
300              dst_rem[cur.d] += cur.amt;          /* undo trial move */
301              cur.price += cost_others/cur.amt;   /* adjust effective price */
302              if (cur.price < best.price)         /* are we better than best? */
303 <                    best = cur;
303 >                best = cur;
304          }
305 <        free(src_cost);                         /* finish up */
306 <
305 >        free(src_cost);                         /* clean up */
306 >        free(rord);
307          if ((best.s < 0) | (best.d < 0))        /* nothing left to move? */
308                  return(.0);
309                                                  /* else make the actual move */
# Line 274 | Line 311 | migration_step(MIGRATION *mig, double *src_rem, double
311          src_rem[best.s] -= best.amt;
312          dst_rem[best.d] -= best.amt;
313          return(best.amt);
314 + memerr:
315 +        fprintf(stderr, "%s: Out of memory in migration_step()\n", progname);
316 +        exit(1);
317   }
318  
319   /* Compute and insert migration along directed edge (may fork child) */

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines