ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/rt/ambient.c
Revision: 2.54
Committed: Sun Jul 27 22:12:03 2003 UTC (20 years, 9 months ago) by schorsch
Content type: text/plain
Branch: MAIN
Changes since 2.53: +3 -3 lines
Log Message:
Added grouping parens to reduce ambiguity warnings.

File Contents

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