ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/clumpbeams.c
Revision: 3.3
Committed: Sat Feb 22 02:07:24 2003 UTC (21 years, 1 month ago) by greg
Content type: text/plain
Branch: MAIN
CVS Tags: rad3R5
Changes since 3.2: +3 -6 lines
Log Message:
Changes and check-in for 3.5 release
Includes new source files and modifications not recorded for many years
See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release

File Contents

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id$";
3 #endif
4 /*
5 * Bundle holodeck beams together into clumps.
6 */
7
8 #include "holo.h"
9
10 #define flgop(p,i,op) ((p)[(i)>>5] op (1L<<((i)&0x1f)))
11 #define isset(p,i) flgop(p,i,&)
12 #define setfl(p,i) flgop(p,i,|=)
13 #define clrfl(p,i) flgop(p,i,&=~)
14
15 static int bneighlist[9*9-1];
16 static int bneighrem;
17
18 #define nextneigh() (bneighrem<=0 ? 0 : bneighlist[--bneighrem])
19
20
21 gcshifti(gc, ia, di, hp) /* shift cell row or column */
22 register GCOORD *gc;
23 int ia, di;
24 register HOLO *hp;
25 {
26 int nw;
27
28 if (di > 0) {
29 if (++gc->i[ia] >= hp->grid[((gc->w>>1)+1+ia)%3]) {
30 nw = ((gc->w&~1) + (ia<<1) + 3) % 6;
31 gc->i[ia] = gc->i[1-ia];
32 gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
33 gc->w = nw;
34 }
35 } else if (di < 0) {
36 if (--gc->i[ia] < 0) {
37 nw = ((gc->w&~1) + (ia<<1) + 2) % 6;
38 gc->i[ia] = gc->i[1-ia];
39 gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
40 gc->w = nw;
41 }
42 }
43 }
44
45
46 mkneighgrid(ng, hp, gc) /* compute neighborhood for grid cell */
47 GCOORD ng[3*3];
48 HOLO *hp;
49 GCOORD *gc;
50 {
51 GCOORD gci0;
52 register int i, j;
53
54 for (i = 3; i--; ) {
55 copystruct(&gci0, gc);
56 gcshifti(&gci0, 0, i-1, hp);
57 for (j = 3; j--; ) {
58 copystruct(ng+(3*i+j), &gci0);
59 gcshifti(ng+(3*i+j), gci0.w==gc->w, j-1, hp);
60 }
61 }
62 }
63
64
65 static int
66 firstneigh(hp, b) /* initialize neighbor list and return first */
67 HOLO *hp;
68 int b;
69 {
70 GCOORD wg0[9], wg1[9], bgc[2];
71 int i, j;
72
73 hdbcoord(bgc, hp, b);
74 mkneighgrid(wg0, hp, bgc);
75 mkneighgrid(wg1, hp, bgc+1);
76 bneighrem = 0;
77 for (i = 9; i--; )
78 for (j = 9; j--; ) {
79 if (i == 4 & j == 4) /* don't copy starting beam */
80 continue;
81 if (wg0[i].w == wg1[j].w)
82 continue;
83 copystruct(bgc, wg0+i);
84 copystruct(bgc+1, wg1+j);
85 bneighlist[bneighrem++] = hdbindex(hp, bgc);
86 #ifdef DEBUG
87 if (bneighlist[bneighrem-1] <= 0)
88 error(CONSISTENCY, "bad beam in firstneigh");
89 #endif
90 }
91 return(nextneigh());
92 }
93
94
95 clumpbeams(hp, maxcnt, maxsiz, cf) /* clump beams from hinp */
96 register HOLO *hp;
97 int maxcnt, maxsiz;
98 int (*cf)();
99 {
100 static short primes[] = {9431,6803,4177,2659,1609,887,587,251,47,1};
101 unsigned int4 *bflags;
102 int *bqueue;
103 int bqlen;
104 int4 bqtotal;
105 int bc, bci, bqc, myprime;
106 register int i;
107 /* get clump size */
108 if (maxcnt <= 1)
109 maxcnt = nbeams(hp);
110 maxsiz /= sizeof(RAYVAL);
111 /* allocate beam queue */
112 bqueue = (int *)malloc(maxcnt*sizeof(int));
113 bflags = (unsigned int4 *)calloc((nbeams(hp)>>5)+1,
114 sizeof(unsigned int4));
115 if (bqueue == NULL | bflags == NULL)
116 error(SYSTEM, "out of memory in clumpbeams");
117 /* mark empty beams as done */
118 for (i = nbeams(hp); i > 0; i--)
119 if (!bnrays(hp, i))
120 setfl(bflags, i);
121 /* pick a good prime step size */
122 for (i = 0; primes[i]<<5 >= nbeams(hp); i++)
123 ;
124 while ((myprime = primes[i++]) > 1)
125 if (nbeams(hp) % myprime)
126 break;
127 /* add each input beam and neighbors */
128 for (bc = bci = nbeams(hp); bc > 0; bc--,
129 bci += bci>myprime ? -myprime : nbeams(hp)-myprime) {
130 if (isset(bflags, bci))
131 continue;
132 bqueue[0] = bci; /* initialize queue */
133 bqlen = 1;
134 bqtotal = bnrays(hp, i);
135 setfl(bflags, bci);
136 /* run through growing queue */
137 for (bqc = 0; bqc < bqlen; bqc++) {
138 /* add neighbors until full */
139 for (i = firstneigh(hp,bqueue[bqc]); i > 0;
140 i = nextneigh()) {
141 if (isset(bflags, i)) /* done already? */
142 continue;
143 bqueue[bqlen++] = i; /* add it */
144 bqtotal += bnrays(hp, i);
145 setfl(bflags, i);
146 if (bqlen >= maxcnt ||
147 (maxsiz && bqtotal >= maxsiz))
148 break; /* queue full */
149 }
150 if (i > 0)
151 break;
152 }
153 (*cf)(hp, bqueue, bqlen); /* transfer clump */
154 }
155 /* all done; clean up */
156 free((void *)bqueue);
157 free((void *)bflags);
158 }