ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm_qtree.c
(Generate patch)

Comparing ray/src/hd/sm_qtree.c (file contents):
Revision 3.13 by gwlarson, Thu Jun 10 15:22:23 1999 UTC vs.
Revision 3.17 by schorsch, Mon Jun 30 14:59:12 2003 UTC

# Line 1 | Line 1
1 – /* Copyright (c) 1998 Silicon Graphics, Inc. */
2 –
1   #ifndef lint
2 < static char SCCSid[] = "$SunId$ SGI";
2 > static const char       RCSid[] = "$Id$";
3   #endif
6 –
4   /*
5   *  sm_qtree.c: adapted from octree.c from radiance code
6   */
# Line 13 | Line 10 | static char SCCSid[] = "$SunId$ SGI";
10   *     7/28/85
11   */
12  
13 + #include <string.h>
14 +
15   #include "standard.h"
16   #include "sm_flag.h"
17   #include "sm_geom.h"
18 + #include "object.h"
19   #include "sm_qtree.h"
20  
21 < QUADTREE  *quad_block[QT_MAX_BLK];              /* our quadtree */
21 > QUADTREE  *quad_block[QT_MAX_BLK];        /* our quadtree */
22   static QUADTREE  quad_free_list = EMPTY;  /* freed octree nodes */
23 < static QUADTREE  treetop = 0;           /* next free node */
24 < int4 *quad_flag= NULL;
23 > static QUADTREE  treetop = 0;             /* next free node */
24 > int32 *quad_flag= NULL;                    /* quadtree flags */
25  
26 – #ifdef TEST_DRIVER
27 – extern FVECT Pick_v0[500],Pick_v1[500],Pick_v2[500];
28 – extern int Pick_cnt,Pick_tri,Pick_samp;
29 – extern FVECT Pick_point[500];
30 – extern int Pick_q[500];
26  
32 – #endif
33 –
27   qtremovelast(qt,id)
28   QUADTREE qt;
29 < int id;
29 > OBJECT id;
30   {
31 + #ifdef DEBUG
32    if(qtqueryset(qt)[(*(qtqueryset(qt)))] != id)
33      error(CONSISTENCY,"not removed\n");
34 + #endif
35    ((*(qtqueryset(qt)))--);
36   }
37   QUADTREE
# Line 59 | Line 54 | qtAlloc()                      /* allocate a quadtree */
54             error(SYSTEM,"qtAlloc(): Unable to allocate memory\n");
55  
56          /* Realloc the per/node flags */
57 <        quad_flag = (int4 *)realloc((char *)quad_flag,
57 >        quad_flag = (int32 *)realloc((void *)quad_flag,
58                          (QT_BLOCK(freet)+1)*((QT_BLOCK_SIZE+7)>>3));
59          if (quad_flag == NULL)
60             error(SYSTEM,"qtAlloc(): Unable to allocate memory\n");
# Line 75 | Line 70 | qtClearAllFlags()              /* clear all quadtree branch flags
70      return;
71    
72    /* Clear the node flags*/
73 <  bzero((char *)quad_flag, (QT_BLOCK(treetop-4)+1)*((QT_BLOCK_SIZE+7)>>3));
73 >  memset((char *)quad_flag, '\0',
74 >                  (QT_BLOCK(treetop-4)+1)*((QT_BLOCK_SIZE+7)>>3));
75    /* Clear set flags */
76    qtclearsetflags();
77   }
# Line 106 | Line 102 | qtDone()                       /* free EVERYTHING */
102          {
103              if (quad_block[i] == NULL)
104                  break;
105 <            free((char *)quad_block[i]);
105 >            free((void *)quad_block[i]);
106              quad_block[i] = NULL;
107          }
108          /* Free the flags */
109 <        if (i) free((char *)quad_flag);
109 >        if (i) free((void *)quad_flag);
110          quad_flag = NULL;
111          quad_free_list = EMPTY;
112          treetop = 0;
113   }
114  
115 + /*
116 + * bary_parent(coord,i)  : Set coord to be value of pt at one level up in
117 + *                         quadtree, given it was the ith child
118 + * BCOORD coord[3];      :barycentric coordinates of point, also will hold
119 + *                        result as side effect
120 + * int i;                :designates which child coord was
121 + */
122 + bary_parent(coord,i)
123 + BCOORD coord[3];
124 + int i;
125 + {
126 +  switch(i) {
127 +  case 0:
128 +    /* update bary for child */
129 +    coord[0] = (coord[0] >> 1) + MAXBCOORD4;
130 +    coord[1] >>= 1;
131 +    coord[2] >>= 1;
132 +    break;
133 +  case 1:
134 +    coord[0] >>= 1;
135 +    coord[1]  = (coord[1] >> 1) + MAXBCOORD4;
136 +    coord[2] >>= 1;
137 +    break;
138 +    
139 +  case 2:
140 +    coord[0] >>= 1;
141 +    coord[1] >>= 1;
142 +    coord[2] = (coord[2] >> 1) + MAXBCOORD4;
143 +    break;
144 +    
145 +  case 3:
146 +    coord[0] = MAXBCOORD4 - (coord[0] >> 1);
147 +    coord[1] = MAXBCOORD4 - (coord[1] >> 1);
148 +    coord[2] = MAXBCOORD4 - (coord[2] >> 1);
149 +    break;
150 + #ifdef DEBUG
151 +  default:
152 +    eputs("bary_parent():Invalid child\n");
153 +    break;
154 + #endif
155 +  }
156 + }
157 +
158 + /*
159 + * bary_from_child(coord,child,next): Given that coord was the (child) child
160 + *                      of the quadtree node, calculate what the (next) child
161 + *                      is at the same level.
162 + * BCOORD coord[3];   :At current level (child)th child of node,will also hold
163 + *                     result as side effect
164 + * int child,next;    :Which child coord was (child), and which one
165 + *                     is now desired(next)
166 + */
167 + bary_from_child(coord,child,next)
168 + BCOORD coord[3];
169 + int child,next;
170 + {
171 + #ifdef DEBUG
172 +  if(child <0 || child > 3)
173 +  {
174 +    eputs("bary_from_child():Invalid child\n");
175 +    return;
176 +  }
177 +  if(next <0 || next > 3)
178 +  {
179 +    eputs("bary_from_child():Invalid next\n");
180 +    return;
181 +  }
182 + #endif
183 +  if(next == child)
184 +    return;
185 +
186 +  switch(child){
187 +  case 0:
188 +      coord[0] = 0;
189 +      coord[1] = MAXBCOORD2 - coord[1];
190 +      coord[2] = MAXBCOORD2 - coord[2];
191 +      break;
192 +  case 1:
193 +      coord[0] = MAXBCOORD2 - coord[0];
194 +      coord[1] = 0;
195 +      coord[2] = MAXBCOORD2 - coord[2];
196 +      break;
197 +  case 2:
198 +      coord[0] = MAXBCOORD2 - coord[0];
199 +      coord[1] = MAXBCOORD2 - coord[1];
200 +      coord[2] = 0;
201 +    break;
202 +  case 3:
203 +    switch(next){
204 +    case 0:
205 +      coord[0] = 0;
206 +      coord[1] = MAXBCOORD2 - coord[1];
207 +      coord[2] = MAXBCOORD2 - coord[2];
208 +      break;
209 +    case 1:
210 +      coord[0] = MAXBCOORD2 - coord[0];
211 +      coord[1] = 0;
212 +      coord[2] = MAXBCOORD2 - coord[2];
213 +      break;
214 +    case 2:
215 +      coord[0] = MAXBCOORD2 - coord[0];
216 +      coord[1] = MAXBCOORD2 - coord[1];
217 +      coord[2] = 0;
218 +      break;
219 +    }
220 +    break;
221 +  }
222 + }
223 +
224 + /*
225 + * int
226 + * bary_child(coord):  Return which child coord is of node at current level
227 + *                     As side effect recalculate coord at next level
228 + * BCOORD coord[3];   :At current level coordinates of point, will also set
229 + *                     to coords at next level as side effect
230 + */
231 + int
232 + bary_child(coord)
233 + BCOORD coord[3];
234 + {
235 +  int i;
236 +
237 +  if(coord[0] > MAXBCOORD4)
238 +  {
239 +      /* update bary for child */
240 +      coord[0] = (coord[0]<< 1) - MAXBCOORD2;
241 +      coord[1] <<= 1;
242 +      coord[2] <<= 1;
243 +      return(0);
244 +  }
245 +  else
246 +    if(coord[1] > MAXBCOORD4)
247 +    {
248 +      coord[0] <<= 1;
249 +      coord[1] = (coord[1] << 1) - MAXBCOORD2;
250 +      coord[2] <<= 1;
251 +      return(1);
252 +    }
253 +    else
254 +      if(coord[2] > MAXBCOORD4)
255 +      {
256 +        coord[0] <<= 1;
257 +        coord[1] <<= 1;
258 +        coord[2] = (coord[2] << 1) - MAXBCOORD2;
259 +        return(2);
260 +      }
261 +      else
262 +         {
263 +           coord[0] = MAXBCOORD2 - (coord[0] << 1);
264 +           coord[1] = MAXBCOORD2 - (coord[1] << 1);
265 +           coord[2] = MAXBCOORD2 - (coord[2] << 1);
266 +           return(3);
267 +         }
268 + }
269 +
270 +
271 +
272   QUADTREE
273   qtLocate(qt,bcoord)
274   QUADTREE qt;
# Line 254 | Line 407 | qtTrace_ray(qt,b,db0,db1,db2,nextptr,sign,sfactor,func
407     }
408   }    
409  
257 –
258 –
259 –
260 –
261 –
262 –
263 –
410   #define TEST_INT(tl,th,d,q0,q1,h,l) \
411                    tl=d>q0;th=d<q1; if(tl&&th) goto Lfunc_call; \
412                   if(tl) if(l) goto Lfunc_call; else h=TRUE; \
# Line 1406 | Line 1552 | int n,*doneptr;
1552      return(qt);
1553    }
1554   }
1555 +
1556  
1557  
1558  

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines