ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/rt/ambient.c
Revision: 2.51
Committed: Thu Jun 26 00:58:10 2003 UTC (20 years, 10 months ago) by schorsch
Content type: text/plain
Branch: MAIN
Changes since 2.50: +3 -1 lines
Log Message:
Abstracted process and path handling for Windows.
Renamed FLOAT to RREAL because of conflict on Windows.
Added conditional compiles for some signal handlers.

File Contents

# User Rev Content
1 greg 1.1 #ifndef lint
2 schorsch 2.51 static const char RCSid[] = "$Id: ambient.c,v 2.50 2003/06/05 19:29:34 schorsch Exp $";
3 greg 1.1 #endif
4     /*
5     * ambient.c - routines dealing with ambient (inter-reflected) component.
6 greg 2.47 *
7     * Declarations of external symbols in ambient.h
8     */
9    
10 greg 2.48 #include "copyright.h"
11 greg 1.1
12 schorsch 2.50 #include "platform.h"
13 greg 1.1 #include "ray.h"
14 greg 1.8 #include "otypes.h"
15 greg 1.14 #include "ambient.h"
16 greg 1.1 #include "random.h"
17    
18 greg 2.32 #ifndef OCTSCALE
19 greg 2.29 #define OCTSCALE 1.0 /* ceil((valid rad.)/(cube size)) */
20 greg 2.32 #endif
21 greg 1.1
22 greg 2.27 extern char *shm_boundary; /* memory sharing boundary */
23 greg 2.26
24 greg 2.12 #define MAXASET 511 /* maximum number of elements in ambient set */
25     OBJECT ambset[MAXASET+1]={0}; /* ambient include/exclude set */
26 greg 1.1
27 greg 2.12 double maxarad; /* maximum ambient radius */
28     double minarad; /* minimum ambient radius */
29 greg 1.1
30 greg 2.12 static AMBTREE atrunk; /* our ambient trunk node */
31 greg 1.1
32     static FILE *ambfp = NULL; /* ambient file pointer */
33 greg 2.16 static int nunflshed = 0; /* number of unflushed ambient values */
34 greg 1.1
35 greg 2.26 #ifndef SORT_THRESH
36 greg 2.49 #ifdef SMLMEM
37     #define SORT_THRESH ((3L<<20)/sizeof(AMBVAL))
38     #else
39 greg 2.27 #define SORT_THRESH ((9L<<20)/sizeof(AMBVAL))
40 greg 2.26 #endif
41     #endif
42     #ifndef SORT_INTVL
43 greg 2.41 #define SORT_INTVL (SORT_THRESH<<1)
44 greg 2.26 #endif
45 greg 2.28 #ifndef MAX_SORT_INTVL
46 greg 2.41 #define MAX_SORT_INTVL (SORT_INTVL<<6)
47 greg 2.28 #endif
48 greg 2.26
49 gregl 2.43 static double avsum = 0.; /* computed ambient value sum (log) */
50     static unsigned int navsum = 0; /* number of values in avsum */
51 greg 2.35 static unsigned int nambvals = 0; /* total number of indirect values */
52     static unsigned int nambshare = 0; /* number of values from file */
53 greg 2.27 static unsigned long ambclock = 0; /* ambient access clock */
54     static unsigned long lastsort = 0; /* time of last value sort */
55 greg 2.26 static long sortintvl = SORT_INTVL; /* time until next sort */
56 greg 2.47 static FILE *ambinp = NULL; /* auxiliary file for input */
57     static long lastpos = -1; /* last flush position */
58 greg 2.26
59     #define MAXACLOCK (1L<<30) /* clock turnover value */
60 greg 2.27 /*
61     * Track access times unless we are sharing ambient values
62     * through memory on a multiprocessor, when we want to avoid
63 greg 2.35 * claiming our own memory (copy on write). Go ahead anyway
64     * if more than two thirds of our values are unshared.
65 gregl 2.43 * Compile with -Dtracktime=0 to turn this code off.
66 greg 2.27 */
67 gregl 2.43 #ifndef tracktime
68 greg 2.35 #define tracktime (shm_boundary == NULL || nambvals > 3*nambshare)
69 gregl 2.43 #endif
70 greg 2.26
71 greg 2.12 #define AMBFLUSH (BUFSIZ/AMBVALSIZ)
72 greg 2.6
73 greg 2.47 #define newambval() (AMBVAL *)malloc(sizeof(AMBVAL))
74     #define freeav(av) free((void *)av);
75 greg 1.1
76 greg 2.47 static void initambfile(), avsave(), avinsert(), sortambvals(), unloadatree();
77     static int avlmemi();
78 greg 2.20 static AMBVAL *avstore();
79 greg 2.19 #ifdef F_SETLKW
80 greg 2.47 static void aflock();
81 greg 2.19 #endif
82 greg 1.1
83 greg 2.7
84 greg 2.47 void
85 greg 2.3 setambres(ar) /* set ambient resolution */
86     int ar;
87     {
88 greg 2.21 ambres = ar < 0 ? 0 : ar; /* may be done already */
89 greg 2.3 /* set min & max radii */
90     if (ar <= 0) {
91 greg 2.25 minarad = 0;
92 greg 2.3 maxarad = thescene.cusize / 2.0;
93     } else {
94     minarad = thescene.cusize / ar;
95 greg 2.30 maxarad = 64 * minarad; /* heuristic */
96 greg 2.3 if (maxarad > thescene.cusize / 2.0)
97     maxarad = thescene.cusize / 2.0;
98     }
99 greg 2.25 if (minarad <= FTINY)
100     minarad = 10*FTINY;
101     if (maxarad <= minarad)
102     maxarad = 64 * minarad;
103 greg 2.3 }
104    
105    
106 greg 2.47 void
107 greg 2.21 setambacc(newa) /* set ambient accuracy */
108 greg 2.20 double newa;
109     {
110 greg 2.33 double ambdiff;
111 greg 2.20
112 greg 2.33 if (newa < 0.0)
113     newa = 0.0;
114     ambdiff = fabs(newa - ambacc);
115     if (ambdiff >= .01 && (ambacc = newa) > FTINY && nambvals > 0)
116     sortambvals(1); /* rebuild tree */
117 greg 2.20 }
118    
119    
120 greg 2.47 void
121     setambient() /* initialize calculation */
122 greg 1.1 {
123 gwlarson 2.46 int readonly = 0;
124 greg 2.37 long pos, flen;
125 greg 2.12 AMBVAL amb;
126 greg 2.47 /* make sure we're fresh */
127     ambdone();
128 greg 2.3 /* init ambient limits */
129     setambres(ambres);
130 greg 2.21 setambacc(ambacc);
131 greg 2.47 if (ambfile == NULL || !ambfile[0])
132 greg 2.19 return;
133 greg 2.20 if (ambacc <= FTINY) {
134 greg 2.21 sprintf(errmsg, "zero ambient accuracy so \"%s\" not opened",
135 greg 2.47 ambfile);
136 greg 2.20 error(WARNING, errmsg);
137     return;
138     }
139 greg 2.3 /* open ambient file */
140 greg 2.47 if ((ambfp = fopen(ambfile, "r+")) == NULL)
141     readonly = (ambfp = fopen(ambfile, "r")) != NULL;
142 gwlarson 2.46 if (ambfp != NULL) {
143     initambfile(0); /* file exists */
144 greg 2.37 pos = ftell(ambfp);
145 greg 2.19 while (readambval(&amb, ambfp))
146 greg 2.21 avinsert(avstore(&amb));
147 gwlarson 2.46 nambshare = nambvals; /* share loaded values */
148     if (readonly) {
149     sprintf(errmsg,
150     "loaded %u values from read-only ambient file",
151     nambvals);
152     error(WARNING, errmsg);
153     fclose(ambfp); /* close file so no writes */
154     ambfp = NULL;
155     return; /* avoid ambsync() */
156     }
157     /* align file pointer */
158 greg 2.37 pos += (long)nambvals*AMBVALSIZ;
159 greg 2.47 flen = lseek(fileno(ambfp), (off_t)0L, 2);
160 greg 2.37 if (flen != pos) {
161 greg 2.42 sprintf(errmsg,
162 greg 2.37 "ignoring last %ld values in ambient file (corrupted)",
163     (flen - pos)/AMBVALSIZ);
164 greg 2.42 error(WARNING, errmsg);
165 greg 2.37 fseek(ambfp, pos, 0);
166 schorsch 2.51 #ifndef _WIN32 /* XXX we need a replacement for that one */
167 greg 2.47 ftruncate(fileno(ambfp), (off_t)pos);
168 schorsch 2.51 #endif
169 greg 2.37 }
170 greg 2.47 } else if ((ambfp = fopen(ambfile, "w+")) != NULL) {
171 gwlarson 2.46 initambfile(1); /* else create new file */
172     } else {
173 greg 2.47 sprintf(errmsg, "cannot open ambient file \"%s\"", ambfile);
174 greg 2.19 error(SYSTEM, errmsg);
175 greg 2.16 }
176 greg 2.19 nunflshed++; /* lie */
177     ambsync();
178 greg 1.8 }
179    
180    
181 greg 2.47 void
182     ambdone() /* close ambient file and free memory */
183     {
184     if (ambfp != NULL) { /* close ambient file */
185     ambsync();
186     fclose(ambfp);
187     ambfp = NULL;
188     if (ambinp != NULL) {
189     fclose(ambinp);
190     ambinp = NULL;
191     }
192     lastpos = -1;
193     }
194     /* free ambient tree */
195     unloadatree(&atrunk, free);
196     /* reset state variables */
197     avsum = 0.;
198     navsum = 0;
199     nambvals = 0;
200     nambshare = 0;
201     ambclock = 0;
202     lastsort = 0;
203     sortintvl = SORT_INTVL;
204     }
205    
206    
207     void
208 greg 1.8 ambnotify(obj) /* record new modifier */
209 greg 2.12 OBJECT obj;
210 greg 1.8 {
211 greg 1.11 static int hitlimit = 0;
212 greg 2.47 register OBJREC *o;
213 greg 1.8 register char **amblp;
214    
215 greg 2.47 if (obj == OVOID) { /* starting over */
216     ambset[0] = 0;
217     hitlimit = 0;
218     return;
219     }
220     o = objptr(obj);
221 greg 1.11 if (hitlimit || !ismodifier(o->otype))
222 greg 1.8 return;
223     for (amblp = amblist; *amblp != NULL; amblp++)
224     if (!strcmp(o->oname, *amblp)) {
225 greg 1.11 if (ambset[0] >= MAXASET) {
226     error(WARNING, "too many modifiers in ambient list");
227     hitlimit++;
228     return; /* should this be fatal? */
229     }
230 greg 1.8 insertelem(ambset, obj);
231     return;
232 greg 1.1 }
233     }
234    
235    
236 greg 2.47 void
237 greg 2.34 ambient(acol, r, nrm) /* compute ambient component for ray */
238 greg 1.1 COLOR acol;
239     register RAY *r;
240 greg 2.34 FVECT nrm;
241 greg 1.1 {
242     static int rdepth = 0; /* ambient recursion */
243 gregl 2.43 double d, l;
244 greg 1.1
245     if (ambdiv <= 0) /* no ambient calculation */
246     goto dumbamb;
247     /* check number of bounces */
248 greg 1.16 if (rdepth >= ambounce)
249 greg 1.1 goto dumbamb;
250     /* check ambient list */
251     if (ambincl != -1 && r->ro != NULL &&
252     ambincl != inset(ambset, r->ro->omod))
253     goto dumbamb;
254    
255     if (ambacc <= FTINY) { /* no ambient storage */
256 greg 1.16 rdepth++;
257     d = doambient(acol, r, r->rweight, NULL, NULL);
258     rdepth--;
259 greg 2.32 if (d <= FTINY)
260 greg 1.1 goto dumbamb;
261 greg 1.16 return;
262 greg 1.1 }
263 greg 2.40
264     if (tracktime) /* sort to minimize thrashing */
265     sortambvals(0);
266 greg 1.1 /* get ambient value */
267     setcolor(acol, 0.0, 0.0, 0.0);
268 greg 2.34 d = sumambient(acol, r, nrm, rdepth,
269 greg 1.16 &atrunk, thescene.cuorg, thescene.cusize);
270 greg 2.32 if (d > FTINY) {
271 greg 1.16 scalecolor(acol, 1.0/d);
272 greg 2.32 return;
273 greg 1.16 }
274 greg 2.33 rdepth++; /* need to cache new value */
275 greg 2.34 d = makeambient(acol, r, nrm, rdepth-1);
276 greg 2.32 rdepth--;
277 greg 1.16 if (d > FTINY)
278     return;
279 greg 1.1 dumbamb: /* return global value */
280     copycolor(acol, ambval);
281 gregl 2.43 if (ambvwt <= 0 | navsum == 0)
282 greg 2.32 return;
283 gregl 2.43 l = bright(ambval); /* average in computations */
284     if (l > FTINY) {
285     d = (log(l)*(double)ambvwt + avsum) /
286     (double)(ambvwt + navsum);
287     d = exp(d) / l;
288     scalecolor(acol, d); /* apply color of ambval */
289     } else {
290     d = exp( avsum / (double)navsum );
291     setcolor(acol, d, d, d); /* neutral color */
292     }
293 greg 1.1 }
294    
295    
296     double
297 greg 2.34 sumambient(acol, r, rn, al, at, c0, s) /* get interpolated ambient value */
298 greg 1.1 COLOR acol;
299     register RAY *r;
300 greg 2.34 FVECT rn;
301 greg 1.16 int al;
302 greg 2.12 AMBTREE *at;
303 greg 1.1 FVECT c0;
304 greg 2.12 double s;
305 greg 1.1 {
306 greg 2.12 double d, e1, e2, wt, wsum;
307 greg 1.1 COLOR ct;
308     FVECT ck0;
309     int i;
310     register int j;
311 greg 2.12 register AMBVAL *av;
312 greg 2.29
313     wsum = 0.0;
314 greg 1.7 /* do this node */
315 greg 1.1 for (av = at->alist; av != NULL; av = av->next) {
316 greg 2.47 double rn_dot = -2.0;
317 greg 2.26 if (tracktime)
318 greg 2.40 av->latick = ambclock;
319 greg 1.1 /*
320 greg 1.16 * Ambient level test.
321 greg 1.1 */
322 greg 2.23 if (av->lvl > al) /* list sorted, so this works */
323     break;
324     if (av->weight < r->rweight-FTINY)
325 greg 1.1 continue;
326     /*
327     * Ambient radius test.
328     */
329 greg 2.29 d = av->pos[0] - r->rop[0];
330     e1 = d * d;
331     d = av->pos[1] - r->rop[1];
332     e1 += d * d;
333     d = av->pos[2] - r->rop[2];
334     e1 += d * d;
335 greg 1.1 e1 /= av->rad * av->rad;
336     if (e1 > ambacc*ambacc*1.21)
337     continue;
338     /*
339 greg 2.47 * Direction test using closest normal.
340 greg 1.1 */
341 greg 2.47 d = DOT(av->dir, r->ron);
342     if (rn != r->ron) {
343     rn_dot = DOT(av->dir, rn);
344     if (rn_dot > 1.0-FTINY)
345     rn_dot = 1.0-FTINY;
346     if (rn_dot >= d-FTINY) {
347     d = rn_dot;
348     rn_dot = -2.0;
349     }
350     }
351     e2 = (1.0 - d) * r->rweight;
352 greg 1.1 if (e2 < 0.0) e2 = 0.0;
353     if (e1 + e2 > ambacc*ambacc*1.21)
354     continue;
355     /*
356     * Ray behind test.
357     */
358     d = 0.0;
359     for (j = 0; j < 3; j++)
360     d += (r->rop[j] - av->pos[j]) *
361     (av->dir[j] + r->ron[j]);
362 greg 1.18 if (d*0.5 < -minarad*ambacc-.001)
363 greg 1.1 continue;
364     /*
365     * Jittering final test reduces image artifacts.
366     */
367 greg 2.47 e1 = sqrt(e1);
368     e2 = sqrt(e2);
369     wt = e1 + e2;
370 greg 2.31 if (wt > ambacc*(.9+.2*urand(9015+samplendx)))
371 greg 1.1 continue;
372 greg 2.47 /*
373     * Recompute directional error using perturbed normal
374     */
375     if (rn_dot > 0.0) {
376     e2 = sqrt((1.0 - rn_dot)*r->rweight);
377     wt = e1 + e2;
378     }
379 greg 1.1 if (wt <= 1e-3)
380     wt = 1e3;
381     else
382     wt = 1.0 / wt;
383     wsum += wt;
384 greg 2.34 extambient(ct, av, r->rop, rn);
385 greg 1.1 scalecolor(ct, wt);
386     addcolor(acol, ct);
387 greg 1.7 }
388     if (at->kid == NULL)
389     return(wsum);
390     /* do children */
391     s *= 0.5;
392     for (i = 0; i < 8; i++) {
393     for (j = 0; j < 3; j++) {
394     ck0[j] = c0[j];
395     if (1<<j & i)
396     ck0[j] += s;
397     if (r->rop[j] < ck0[j] - OCTSCALE*s)
398     break;
399     if (r->rop[j] > ck0[j] + (1.0+OCTSCALE)*s)
400     break;
401     }
402     if (j == 3)
403 greg 2.34 wsum += sumambient(acol, r, rn, al, at->kid+i, ck0, s);
404 greg 1.1 }
405     return(wsum);
406     }
407    
408    
409     double
410 greg 2.34 makeambient(acol, r, rn, al) /* make a new ambient value */
411 greg 1.1 COLOR acol;
412     register RAY *r;
413 greg 2.34 FVECT rn;
414 greg 1.16 int al;
415 greg 1.1 {
416 greg 2.12 AMBVAL amb;
417 greg 1.14 FVECT gp, gd;
418 greg 1.16 /* compute weight */
419     amb.weight = pow(AVGREFL, (double)al);
420 greg 2.33 if (r->rweight < 0.1*amb.weight) /* heuristic */
421 greg 1.16 amb.weight = r->rweight;
422     /* compute ambient */
423     amb.rad = doambient(acol, r, amb.weight, gp, gd);
424 greg 2.33 if (amb.rad <= FTINY)
425 greg 1.1 return(0.0);
426     /* store it */
427     VCOPY(amb.pos, r->rop);
428     VCOPY(amb.dir, r->ron);
429 greg 1.16 amb.lvl = al;
430 greg 1.1 copycolor(amb.val, acol);
431 greg 1.14 VCOPY(amb.gpos, gp);
432     VCOPY(amb.gdir, gd);
433 greg 1.1 /* insert into tree */
434 greg 2.7 avsave(&amb); /* and save to file */
435 greg 2.34 if (rn != r->ron)
436     extambient(acol, &amb, r->rop, rn); /* texture */
437 greg 1.1 return(amb.rad);
438 greg 1.15 }
439    
440    
441 greg 2.47 void
442 greg 1.15 extambient(cr, ap, pv, nv) /* extrapolate value at pv, nv */
443     COLOR cr;
444 greg 2.12 register AMBVAL *ap;
445 greg 1.15 FVECT pv, nv;
446     {
447 gwlarson 2.45 FVECT v1;
448 greg 1.15 register int i;
449 greg 2.12 double d;
450 greg 1.15
451     d = 1.0; /* zeroeth order */
452     /* gradient due to translation */
453     for (i = 0; i < 3; i++)
454     d += ap->gpos[i]*(pv[i]-ap->pos[i]);
455     /* gradient due to rotation */
456 gwlarson 2.45 VCROSS(v1, ap->dir, nv);
457     d += DOT(ap->gdir, v1);
458 greg 1.15 if (d <= 0.0) {
459     setcolor(cr, 0.0, 0.0, 0.0);
460     return;
461     }
462     copycolor(cr, ap->val);
463     scalecolor(cr, d);
464 greg 1.1 }
465    
466    
467 greg 2.47 static void
468 greg 2.9 initambfile(creat) /* initialize ambient file */
469     int creat;
470     {
471 greg 2.47 extern char *progname, *octname;
472     static char *mybuf = NULL;
473 greg 2.9
474 greg 2.19 #ifdef F_SETLKW
475     aflock(creat ? F_WRLCK : F_RDLCK);
476     #endif
477 schorsch 2.50 SET_FILE_BINARY(ambfp);
478 greg 2.47 if (mybuf == NULL)
479     mybuf = (char *)bmalloc(BUFSIZ+8);
480     setbuf(ambfp, mybuf);
481 greg 2.9 if (creat) { /* new file */
482 greg 2.24 newheader("RADIANCE", ambfp);
483 greg 2.41 fprintf(ambfp, "%s -av %g %g %g -aw %d -ab %d -aa %g ",
484 greg 2.9 progname, colval(ambval,RED),
485     colval(ambval,GRN), colval(ambval,BLU),
486 greg 2.41 ambvwt, ambounce, ambacc);
487 greg 2.47 fprintf(ambfp, "-ad %d -as %d -ar %d ",
488     ambdiv, ambssamp, ambres);
489     if (octname != NULL)
490     printargs(1, &octname, ambfp);
491     else
492     fputc('\n', ambfp);
493 greg 2.9 fprintf(ambfp, "SOFTWARE= %s\n", VersionID);
494 greg 2.47 fputnow(ambfp);
495 greg 2.9 fputformat(AMBFMT, ambfp);
496     putc('\n', ambfp);
497     putambmagic(ambfp);
498 greg 2.17 } else if (checkheader(ambfp, AMBFMT, NULL) < 0 || !hasambmagic(ambfp))
499     error(USER, "bad ambient file");
500 greg 2.9 }
501    
502    
503 greg 2.47 static void
504 greg 2.7 avsave(av) /* insert and save an ambient value */
505 greg 2.12 AMBVAL *av;
506 greg 1.1 {
507 greg 2.21 avinsert(avstore(av));
508 greg 1.1 if (ambfp == NULL)
509     return;
510 greg 2.5 if (writambval(av, ambfp) < 0)
511 greg 1.1 goto writerr;
512 greg 2.16 if (++nunflshed >= AMBFLUSH)
513 greg 2.7 if (ambsync() == EOF)
514 greg 1.1 goto writerr;
515     return;
516     writerr:
517 greg 2.47 error(SYSTEM, "error writing to ambient file");
518 greg 1.1 }
519    
520    
521 greg 2.20 static AMBVAL *
522     avstore(aval) /* allocate memory and store aval */
523     register AMBVAL *aval;
524     {
525     register AMBVAL *av;
526 gregl 2.43 double d;
527 greg 2.20
528     if ((av = newambval()) == NULL)
529     error(SYSTEM, "out of memory in avstore");
530     copystruct(av, aval);
531 greg 2.26 av->latick = ambclock;
532     av->next = NULL;
533     nambvals++;
534 gregl 2.43 d = bright(av->val);
535     if (d > FTINY) { /* add to log sum for averaging */
536     avsum += log(d);
537     navsum++;
538     }
539 greg 2.20 return(av);
540     }
541    
542    
543 greg 2.26 #define ATALLOCSZ 512 /* #/8 trees to allocate at once */
544    
545     static AMBTREE *atfreelist = NULL; /* free ambient tree structures */
546    
547    
548 greg 2.47 static AMBTREE *
549 greg 2.26 newambtree() /* allocate 8 ambient tree structs */
550     {
551     register AMBTREE *atp, *upperlim;
552    
553     if (atfreelist == NULL) { /* get more nodes */
554 greg 2.47 atfreelist = (AMBTREE *)malloc(ATALLOCSZ*8*sizeof(AMBTREE));
555 greg 2.26 if (atfreelist == NULL)
556     return(NULL);
557     /* link new free list */
558     upperlim = atfreelist + 8*(ATALLOCSZ-1);
559     for (atp = atfreelist; atp < upperlim; atp += 8)
560     atp->kid = atp + 8;
561     atp->kid = NULL;
562     }
563     atp = atfreelist;
564     atfreelist = atp->kid;
565     bzero((char *)atp, 8*sizeof(AMBTREE));
566     return(atp);
567     }
568    
569    
570 greg 2.47 static void
571 greg 2.26 freeambtree(atp) /* free 8 ambient tree structs */
572     AMBTREE *atp;
573     {
574     atp->kid = atfreelist;
575     atfreelist = atp;
576     }
577    
578    
579 greg 2.47 static void
580 greg 2.21 avinsert(av) /* insert ambient value in our tree */
581 greg 2.20 register AMBVAL *av;
582 greg 1.1 {
583 greg 2.21 register AMBTREE *at;
584 greg 2.23 register AMBVAL *ap;
585     AMBVAL avh;
586 greg 1.1 FVECT ck0;
587 greg 2.21 double s;
588 greg 1.1 int branch;
589     register int i;
590    
591 greg 2.20 if (av->rad <= FTINY)
592     error(CONSISTENCY, "zero ambient radius in avinsert");
593 greg 2.21 at = &atrunk;
594     VCOPY(ck0, thescene.cuorg);
595     s = thescene.cusize;
596 greg 1.1 while (s*(OCTSCALE/2) > av->rad*ambacc) {
597     if (at->kid == NULL)
598     if ((at->kid = newambtree()) == NULL)
599 greg 2.20 error(SYSTEM, "out of memory in avinsert");
600 greg 1.1 s *= 0.5;
601     branch = 0;
602     for (i = 0; i < 3; i++)
603     if (av->pos[i] > ck0[i] + s) {
604     ck0[i] += s;
605     branch |= 1 << i;
606     }
607     at = at->kid + branch;
608     }
609 greg 2.23 avh.next = at->alist; /* order by increasing level */
610     for (ap = &avh; ap->next != NULL; ap = ap->next)
611     if (ap->next->lvl >= av->lvl)
612     break;
613     av->next = ap->next;
614     ap->next = av;
615     at->alist = avh.next;
616 greg 2.7 }
617    
618    
619 greg 2.47 static void
620 greg 2.26 unloadatree(at, f) /* unload an ambient value tree */
621 greg 2.20 register AMBTREE *at;
622 greg 2.47 void (*f)();
623 greg 2.20 {
624     register AMBVAL *av;
625     register int i;
626     /* transfer values at this node */
627     for (av = at->alist; av != NULL; av = at->alist) {
628     at->alist = av->next;
629 greg 2.26 (*f)(av);
630 greg 2.20 }
631 greg 2.21 if (at->kid == NULL)
632     return;
633 greg 2.20 for (i = 0; i < 8; i++) /* transfer and free children */
634 greg 2.26 unloadatree(at->kid+i, f);
635 greg 2.20 freeambtree(at->kid);
636 greg 2.26 at->kid = NULL;
637     }
638    
639    
640 greg 2.39 static struct avl {
641     AMBVAL *p;
642     unsigned long t;
643     } *avlist1; /* ambient value list with ticks */
644     static AMBVAL **avlist2; /* memory positions for sorting */
645 greg 2.26 static int i_avlist; /* index for lists */
646    
647    
648 greg 2.47 static int
649 greg 2.26 av2list(av)
650 greg 2.39 register AMBVAL *av;
651 greg 2.26 {
652 greg 2.27 #ifdef DEBUG
653 greg 2.26 if (i_avlist >= nambvals)
654     error(CONSISTENCY, "too many ambient values in av2list1");
655 greg 2.27 #endif
656 greg 2.39 avlist1[i_avlist].p = avlist2[i_avlist] = av;
657     avlist1[i_avlist++].t = av->latick;
658 greg 2.26 }
659    
660    
661     static int
662 greg 2.39 alatcmp(av1, av2) /* compare ambient values for MRA */
663     struct avl *av1, *av2;
664 greg 2.26 {
665 greg 2.39 register long lc = av2->t - av1->t;
666 greg 2.38 return(lc<0 ? -1 : lc>0 ? 1 : 0);
667 greg 2.26 }
668    
669    
670 greg 2.47 /* GW NOTE 2002/10/3:
671     * I used to compare AMBVAL pointers, but found that this was the
672     * cause of a serious consistency error with gcc, since the optimizer
673     * uses some dangerous trick in pointer subtraction that
674     * assumes pointers differ by exact struct size increments.
675     */
676 greg 2.26 static int
677     aposcmp(avp1, avp2) /* compare ambient value positions */
678 greg 2.47 const void *avp1, *avp2;
679 greg 2.26 {
680 greg 2.47 register long diff = *(char * const *)avp1 - *(char * const *)avp2;
681     if (diff < 0)
682     return(-1);
683     return(diff > 0);
684 greg 2.26 }
685    
686 greg 2.39 #if 1
687 greg 2.27 static int
688     avlmemi(avaddr) /* find list position from address */
689     AMBVAL *avaddr;
690     {
691     register AMBVAL **avlpp;
692    
693     avlpp = (AMBVAL **)bsearch((char *)&avaddr, (char *)avlist2,
694     nambvals, sizeof(AMBVAL *), aposcmp);
695     if (avlpp == NULL)
696     error(CONSISTENCY, "address not found in avlmemi");
697     return(avlpp - avlist2);
698     }
699     #else
700     #define avlmemi(avaddr) ((AMBVAL **)bsearch((char *)&avaddr,(char *)avlist2, \
701     nambvals,sizeof(AMBVAL *),aposcmp) - avlist2)
702     #endif
703    
704    
705 greg 2.47 static void
706 greg 2.26 sortambvals(always) /* resort ambient values */
707     int always;
708     {
709     AMBTREE oldatrunk;
710     AMBVAL tav, *tap, *pnext;
711     register int i, j;
712 greg 2.28 /* see if it's time yet */
713 greg 2.40 if (!always && (ambclock++ < lastsort+sortintvl ||
714 greg 2.28 nambvals < SORT_THRESH))
715     return;
716 greg 2.26 /*
717     * The idea here is to minimize memory thrashing
718     * in VM systems by improving reference locality.
719     * We do this by periodically sorting our stored ambient
720     * values in memory in order of most recently to least
721     * recently accessed. This ordering was chosen so that new
722     * ambient values (which tend to be less important) go into
723     * higher memory with the infrequently accessed values.
724     * Since we expect our values to need sorting less
725     * frequently as the process continues, we double our
726     * waiting interval after each call.
727     * This routine is also called by setambacc() with
728     * the "always" parameter set to 1 so that the ambient
729     * tree will be rebuilt with the new accuracy parameter.
730     */
731 greg 2.27 if (tracktime) { /* allocate pointer arrays to sort */
732 greg 2.26 avlist2 = (AMBVAL **)malloc(nambvals*sizeof(AMBVAL *));
733 greg 2.39 avlist1 = (struct avl *)malloc(nambvals*sizeof(struct avl));
734     } else {
735     avlist2 = NULL;
736     avlist1 = NULL;
737     }
738     if (avlist1 == NULL) { /* no time tracking -- rebuild tree? */
739     if (avlist2 != NULL)
740 greg 2.47 free((void *)avlist2);
741 greg 2.27 if (always) { /* rebuild without sorting */
742     copystruct(&oldatrunk, &atrunk);
743     atrunk.alist = NULL;
744     atrunk.kid = NULL;
745     unloadatree(&oldatrunk, avinsert);
746     }
747 greg 2.26 } else { /* sort memory by last access time */
748     /*
749     * Sorting memory is tricky because it isn't contiguous.
750     * We have to sort an array of pointers by MRA and also
751     * by memory position. We then copy values in "loops"
752     * to minimize memory hits. Nevertheless, we will visit
753 greg 2.27 * everyone at least twice, and this is an expensive process
754 greg 2.26 * when we're thrashing, which is when we need to do it.
755     */
756 greg 2.27 #ifdef DEBUG
757 greg 2.29 sprintf(errmsg, "sorting %u ambient values at ambclock=%lu...",
758     nambvals, ambclock);
759 greg 2.27 eputs(errmsg);
760     #endif
761     i_avlist = 0;
762     unloadatree(&atrunk, av2list); /* empty current tree */
763     #ifdef DEBUG
764     if (i_avlist < nambvals)
765     error(CONSISTENCY, "missing ambient values in sortambvals");
766     #endif
767 greg 2.39 qsort((char *)avlist1, nambvals, sizeof(struct avl), alatcmp);
768 greg 2.26 qsort((char *)avlist2, nambvals, sizeof(AMBVAL *), aposcmp);
769     for (i = 0; i < nambvals; i++) {
770 greg 2.39 if (avlist1[i].p == NULL)
771 greg 2.26 continue;
772     tap = avlist2[i];
773     copystruct(&tav, tap);
774 greg 2.39 for (j = i; (pnext = avlist1[j].p) != tap;
775 greg 2.27 j = avlmemi(pnext)) {
776 greg 2.26 copystruct(avlist2[j], pnext);
777     avinsert(avlist2[j]);
778 greg 2.39 avlist1[j].p = NULL;
779 greg 2.26 }
780     copystruct(avlist2[j], &tav);
781     avinsert(avlist2[j]);
782 greg 2.39 avlist1[j].p = NULL;
783 greg 2.26 }
784 greg 2.47 free((void *)avlist1);
785     free((void *)avlist2);
786 greg 2.28 /* compute new sort interval */
787     sortintvl = ambclock - lastsort;
788 greg 2.32 if (sortintvl >= MAX_SORT_INTVL/2)
789 greg 2.28 sortintvl = MAX_SORT_INTVL;
790     else
791 greg 2.26 sortintvl <<= 1; /* wait twice as long next */
792 greg 2.27 #ifdef DEBUG
793     eputs("done\n");
794     #endif
795 greg 2.26 }
796     if (ambclock >= MAXACLOCK)
797     ambclock = MAXACLOCK/2;
798     lastsort = ambclock;
799 greg 2.20 }
800    
801    
802 greg 2.18 #ifdef F_SETLKW
803 greg 2.10
804 greg 2.47 static void
805 greg 2.19 aflock(typ) /* lock/unlock ambient file */
806     int typ;
807     {
808     static struct flock fls; /* static so initialized to zeroes */
809    
810     fls.l_type = typ;
811     if (fcntl(fileno(ambfp), F_SETLKW, &fls) < 0)
812     error(SYSTEM, "cannot (un)lock ambient file");
813     }
814    
815    
816 greg 2.16 int
817 greg 2.7 ambsync() /* synchronize ambient file */
818     {
819 greg 2.15 long flen;
820 greg 2.12 AMBVAL avs;
821 greg 2.7 register int n;
822 greg 2.16
823     if (nunflshed == 0)
824     return(0);
825 greg 2.19 if (lastpos < 0) /* initializing (locked in initambfile) */
826     goto syncend;
827 greg 2.7 /* gain exclusive access */
828 greg 2.19 aflock(F_WRLCK);
829 greg 2.7 /* see if file has grown */
830 greg 2.47 if ((flen = lseek(fileno(ambfp), (off_t)0L, 2)) < 0)
831 greg 2.21 goto seekerr;
832 greg 2.15 if (n = flen - lastpos) { /* file has grown */
833 greg 2.17 if (ambinp == NULL) { /* use duplicate filedes */
834     ambinp = fdopen(dup(fileno(ambfp)), "r");
835 greg 2.14 if (ambinp == NULL)
836 greg 2.17 error(SYSTEM, "fdopen failed in ambsync");
837 greg 2.14 }
838 greg 2.15 if (fseek(ambinp, lastpos, 0) < 0)
839 greg 2.21 goto seekerr;
840 greg 2.15 while (n >= AMBVALSIZ) { /* load contributed values */
841 greg 2.37 if (!readambval(&avs, ambinp)) {
842     sprintf(errmsg,
843 greg 2.47 "ambient file \"%s\" corrupted near character %ld",
844     ambfile, flen - n);
845 greg 2.37 error(WARNING, errmsg);
846     break;
847     }
848 greg 2.21 avinsert(avstore(&avs));
849 greg 2.15 n -= AMBVALSIZ;
850     }
851 greg 2.22 /*** seek always as safety measure
852     if (n) ***/ /* alignment */
853 greg 2.47 if (lseek(fileno(ambfp), (off_t)(flen-n), 0) < 0)
854 greg 2.21 goto seekerr;
855 greg 2.7 }
856 greg 2.21 #ifdef DEBUG
857     if (ambfp->_ptr - ambfp->_base != nunflshed*AMBVALSIZ) {
858     sprintf(errmsg, "ambient file buffer at %d rather than %d",
859     ambfp->_ptr - ambfp->_base,
860     nunflshed*AMBVALSIZ);
861     error(CONSISTENCY, errmsg);
862     }
863     #endif
864 greg 2.15 syncend:
865 greg 2.7 n = fflush(ambfp); /* calls write() at last */
866 greg 2.47 if ((lastpos = lseek(fileno(ambfp), (off_t)0L, 1)) < 0)
867 greg 2.21 goto seekerr;
868 greg 2.19 aflock(F_UNLCK); /* release file */
869 greg 2.16 nunflshed = 0;
870 greg 2.7 return(n);
871 greg 2.21 seekerr:
872     error(SYSTEM, "seek failed in ambsync");
873 greg 2.18 }
874    
875     #else
876    
877     int
878     ambsync() /* flush ambient file */
879     {
880     if (nunflshed == 0)
881     return(0);
882     nunflshed = 0;
883     return(fflush(ambfp));
884 greg 1.1 }
885 greg 2.10
886     #endif