ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/Development/ray/src/cv/bsdfmesh.c

Comparing ray/src/cv/bsdfmesh.c (file contents):
Revision 2.2 by greg, Sat Oct 20 07:02:00 2012 UTC vs.
Revision 2.5 by greg, Thu Nov 8 23:32:30 2012 UTC

#	Line 23 | Line 23 | int                    nprocs = 1;
23		/* number of children (-1 in child) */
24		static int              nchild = 0;
25
26	+	typedef struct {
27	+	int             nrows, ncols;   /* array size (matches migration) */
28	+	float           *price;         /* migration prices */
29	+	short           *sord;          /* sort for each row, low to high */
30	+	} PRICEMAT;                     /* sorted pricing matrix */
31	+
32	+	#define pricerow(p,i)   ((p)->price + (i)*(p)->ncols)
33	+	#define psortrow(p,i)   ((p)->sord + (i)*(p)->ncols)
34	+
35		/* Create a new migration holder (sharing memory for multiprocessing) */
36		static MIGRATION *
37		new_migration(RBFNODE *from_rbf, RBFNODE *to_rbf)
#	Line 124 | Line 133 | run_subprocess(void)
133
134		#endif  /* ! _WIN32 */
135
136	+	/* Comparison routine needed for sorting price row */
137	+	static int
138	+	msrt_cmp(void *b, const void *p1, const void *p2)
139	+	{
140	+	PRICEMAT        *pm = (PRICEMAT *)b;
141	+	int             ri = ((const short *)p1 - pm->sord) / pm->ncols;
142	+	float           c1 = pricerow(pm,ri)[*(const short *)p1];
143	+	float           c2 = pricerow(pm,ri)[*(const short *)p2];
144	+
145	+	if (c1 > c2) return(1);
146	+	if (c1 < c2) return(-1);
147	+	return(0);
148	+	}
149	+
150		/* Compute (and allocate) migration price matrix for optimization */
151	<	static float *
152	<	price_routes(const RBFNODE *from_rbf, const RBFNODE *to_rbf)
151	>	static void
152	>	price_routes(PRICEMAT *pm, const RBFNODE *from_rbf, const RBFNODE *to_rbf)
153		{
131	–	float   *pmtx = (float *)malloc(sizeof(float) *
132	–	from_rbf->nrbf * to_rbf->nrbf);
154		FVECT   *vto = (FVECT *)malloc(sizeof(FVECT) * to_rbf->nrbf);
155		int     i, j;
156
157	<	if ((pmtx == NULL) | (vto == NULL)) {
157	>	pm->nrows = from_rbf->nrbf;
158	>	pm->ncols = to_rbf->nrbf;
159	>	pm->price = (float *)malloc(sizeof(float) * pm->nrows*pm->ncols);
160	>	pm->sord = (short *)malloc(sizeof(short) * pm->nrows*pm->ncols);
161	>
162	>	if ((pm->price == NULL) | (pm->sord == NULL) | (vto == NULL)) {
163		fprintf(stderr, "%s: Out of memory in migration_costs()\n",
164		progname);
165		exit(1);
#	Line 145 | Line 171 | price_routes(const RBFNODE *from_rbf, const RBFNODE *t
171		const double        from_ang = R2ANG(from_rbf->rbfa[i].crad);
172		FVECT               vfrom;
173		ovec_from_pos(vfrom, from_rbf->rbfa[i].gx, from_rbf->rbfa[i].gy);
174	<	for (j = to_rbf->nrbf; j--; )
175	<	pmtx[i*to_rbf->nrbf + j] = acos(DOT(vfrom, vto[j])) +
174	>	for (j = to_rbf->nrbf; j--; ) {
175	>	pricerow(pm,i)[j] = acos(DOT(vfrom, vto[j])) +
176		fabs(R2ANG(to_rbf->rbfa[j].crad) - from_ang);
177	+	psortrow(pm,i)[j] = j;
178	+	}
179	+	qsort_r(psortrow(pm,i), pm->ncols, sizeof(short), pm, &msrt_cmp);
180		}
181		free(vto);
153	–	return(pmtx);
182		}
183
184	<	/* Comparison routine needed for sorting price row */
185	<	static const float      *price_arr;
186	<	static int
159	<	msrt_cmp(const void *p1, const void *p2)
184	>	/* Free price matrix */
185	>	static void
186	>	free_routes(PRICEMAT *pm)
187		{
188	<	float   c1 = price_arr[*(const int *)p1];
189	<	float   c2 = price_arr[*(const int *)p2];
163	<
164	<	if (c1 > c2) return(1);
165	<	if (c1 < c2) return(-1);
166	<	return(0);
188	>	free(pm->price); pm->price = NULL;
189	>	free(pm->sord); pm->sord = NULL;
190		}
191
192		/* Compute minimum (optimistic) cost for moving the given source material */
193		static double
194	<	min_cost(double amt2move, const double *avail, const float *price, int n)
194	>	min_cost(double amt2move, const double *avail, const PRICEMAT *pm, int s)
195		{
173	–	static int      *price_sort = NULL;
174	–	static int      n_alloc = 0;
196		double          total_cost = 0;
197	<	int             i;
197	>	int             j;
198
199		if (amt2move <= FTINY)                  /* pre-emptive check */
200	<	return(0.);
180	<	if (n > n_alloc) {                      /* (re)allocate sort array */
181	<	if (n_alloc) free(price_sort);
182	<	price_sort = (int *)malloc(sizeof(int)*n);
183	<	if (price_sort == NULL) {
184	<	fprintf(stderr, "%s: Out of memory in min_cost()\n",
185	<	progname);
186	<	exit(1);
187	<	}
188	<	n_alloc = n;
189	<	}
190	<	for (i = n; i--; )
191	<	price_sort[i] = i;
192	<	price_arr = price;
193	<	qsort(price_sort, n, sizeof(int), &msrt_cmp);
200	>	return(.0);
201		/* move cheapest first */
202	<	for (i = 0; i < n && amt2move > FTINY; i++) {
203	<	int     d = price_sort[i];
202	>	for (j = 0; j < pm->ncols && amt2move > FTINY; j++) {
203	>	int     d = psortrow(pm,s)[j];
204		double  amt = (amt2move < avail[d]) ? amt2move : avail[d];
205
206	<	total_cost += amt * price[d];
206	>	total_cost += amt * pricerow(pm,s)[d];
207		amt2move -= amt;
208		}
209		return(total_cost);
#	Line 204 | Line 211 | min_cost(double amt2move, const double *avail, const f
211
212		/* Take a step in migration by choosing optimal bucket to transfer */
213		static double
214	<	migration_step(MIGRATION *mig, double *src_rem, double *dst_rem, const float *pmtx)
214	>	migration_step(MIGRATION *mig, double *src_rem, double *dst_rem, const PRICEMAT *pm)
215		{
216	<	const double    maxamt = .1;
216	>	const double    maxamt = 1./(double)pm->ncols;
217		const double    minamt = maxamt*5e-6;
218	<	static double   *src_cost = NULL;
212	<	static int      n_alloc = 0;
218	>	double          *src_cost;
219		struct {
220		int     s, d;   /* source and destination */
221		double  price;  /* price estimate per amount moved */
222		double  amt;    /* amount we can move */
223		} cur, best;
224		int             i;
225	<
226	<	if (mtx_nrows(mig) > n_alloc) {         /* allocate cost array */
227	<	if (n_alloc)
228	<	free(src_cost);
229	<	src_cost = (double *)malloc(sizeof(double)*mtx_nrows(mig));
230	<	if (src_cost == NULL) {
225	<	fprintf(stderr, "%s: Out of memory in migration_step()\n",
226	<	progname);
227	<	exit(1);
228	<	}
229	<	n_alloc = mtx_nrows(mig);
225	>	/* allocate cost array */
226	>	src_cost = (double *)malloc(sizeof(double)*pm->nrows);
227	>	if (src_cost == NULL) {
228	>	fprintf(stderr, "%s: Out of memory in migration_step()\n",
229	>	progname);
230	>	exit(1);
231		}
232	<	for (i = mtx_nrows(mig); i--; )         /* starting costs for diff. */
233	<	src_cost[i] = min_cost(src_rem[i], dst_rem,
233	<	pmtx+i*mtx_ncols(mig), mtx_ncols(mig));
232	>	for (i = pm->nrows; i--; )              /* starting costs for diff. */
233	>	src_cost[i] = min_cost(src_rem[i], dst_rem, pm, i);
234
235		/* find best source & dest. */
236		best.s = best.d = -1; best.price = FHUGE; best.amt = 0;
237	<	for (cur.s = mtx_nrows(mig); cur.s--; ) {
238	<	const float *price = pmtx + cur.s*mtx_ncols(mig);
237	>	for (cur.s = pm->nrows; cur.s--; ) {
238		double      cost_others = 0;
239	+
240		if (src_rem[cur.s] <= minamt)
241		continue;
242	<	cur.d = -1;                         /* examine cheapest dest. */
243	<	for (i = mtx_ncols(mig); i--; )
244	<	if (dst_rem[i] > minamt &&
245	<	(cur.d < 0 || price[i] < price[cur.d]))
246	<	cur.d = i;
247	<	if (cur.d < 0)
248	<	return(.0);
249	<	if ((cur.price = price[cur.d]) >= best.price)
250	<	continue;                   /* no point checking further */
242	>	/* examine cheapest dest. */
243	>	for (i = 0; i < pm->ncols; i++)
244	>	if (dst_rem[ cur.d = psortrow(pm,cur.s)[i] ] > minamt)
245	>	break;
246	>	if (i >= pm->ncols)
247	>	break;
248	>	if ((cur.price = pricerow(pm,cur.s)[cur.d]) >= best.price)
249	>	continue;                       /* no point checking further */
250		cur.amt = (src_rem[cur.s] < dst_rem[cur.d]) ?
251		src_rem[cur.s] : dst_rem[cur.d];
252		if (cur.amt > maxamt) cur.amt = maxamt;
253		dst_rem[cur.d] -= cur.amt;          /* add up differential costs */
254	<	for (i = mtx_nrows(mig); i--; )
254	>	for (i = pm->nrows; i--; )
255		if (i != cur.s)
256	<	cost_others += min_cost(src_rem[i], dst_rem,
258	<	price, mtx_ncols(mig))
256	>	cost_others += min_cost(src_rem[i], dst_rem, pm, i)
257		- src_cost[i];
258		dst_rem[cur.d] += cur.amt;          /* undo trial move */
259		cur.price += cost_others/cur.amt;   /* adjust effective price */
260		if (cur.price < best.price)         /* are we better than best? */
261		best = cur;
262		}
263	<	if ((best.s < 0) | (best.d < 0))
263	>	free(src_cost);                         /* finish up */
264	>
265	>	if ((best.s < 0) | (best.d < 0))        /* nothing left to move? */
266		return(.0);
267	<	/* make the actual move */
267	>	/* else make the actual move */
268		mtx_coef(mig,best.s,best.d) += best.amt;
269		src_rem[best.s] -= best.amt;
270		dst_rem[best.d] -= best.amt;
#	Line 291 | Line 291 | static MIGRATION *
291		create_migration(RBFNODE *from_rbf, RBFNODE *to_rbf)
292		{
293		const double    end_thresh = 5e-6;
294	<	float           *pmtx;
294	>	PRICEMAT        pmtx;
295		MIGRATION       *newmig;
296		double          *src_rem, *dst_rem;
297		double          total_rem = 1., move_amt;
#	Line 305 | Line 305 | create_migration(RBFNODE *from_rbf, RBFNODE *to_rbf)
305		newmig = new_migration(from_rbf, to_rbf);
306		if (run_subprocess())
307		return(newmig);                 /* child continues */
308	<	pmtx = price_routes(from_rbf, to_rbf);
308	>	price_routes(&pmtx, from_rbf, to_rbf);
309		src_rem = (double *)malloc(sizeof(double)*from_rbf->nrbf);
310		dst_rem = (double *)malloc(sizeof(double)*to_rbf->nrbf);
311		if ((src_rem == NULL) | (dst_rem == NULL)) {
#	Line 327 | Line 327 | create_migration(RBFNODE *from_rbf, RBFNODE *to_rbf)
327		for (i = to_rbf->nrbf; i--; )
328		dst_rem[i] = rbf_volume(&to_rbf->rbfa[i]) / to_rbf->vtotal;
329		do {                                    /* move a bit at a time */
330	<	move_amt = migration_step(newmig, src_rem, dst_rem, pmtx);
330	>	move_amt = migration_step(newmig, src_rem, dst_rem, &pmtx);
331		total_rem -= move_amt;
332		#ifdef DEBUG
333		if (!nchild)
#	Line 347 | Line 347 | create_migration(RBFNODE *from_rbf, RBFNODE *to_rbf)
347		mtx_coef(newmig,i,j) *= nf;
348		}
349		end_subprocess();                       /* exit here if subprocess */
350	<	free(pmtx);                             /* free working arrays */
350	>	free_routes(&pmtx);                     /* free working arrays */
351		free(src_rem);
352		free(dst_rem);
353		return(newmig);

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines (old)
>	Changed lines (new)