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.2 by gwlarson, Thu Aug 20 16:47:21 1998 UTC vs.
Revision 3.3 by gwlarson, Tue Aug 25 11:03:27 1998 UTC

# Line 22 | Line 22 | static char SCCSid[] = "$SunId$ SGI";
22   QUADTREE  *quad_block[QT_MAX_BLK];              /* our quadtree */
23   static QUADTREE  quad_free_list = EMPTY;  /* freed octree nodes */
24   static QUADTREE  treetop = 0;           /* next free node */
25 + int4 *quad_flag;
26  
26 –
27 –
27   QUADTREE
28   qtAlloc()                       /* allocate a quadtree */
29   {
# Line 41 | Line 40 | qtAlloc()                      /* allocate a quadtree */
40          if (QT_BLOCK(freet) >= QT_MAX_BLK)
41             return(EMPTY);
42          if ((quad_block[QT_BLOCK(freet)] = (QUADTREE *)malloc(
43 <                   (unsigned)QT_BLOCK_SIZE*4*sizeof(QUADTREE))) == NULL)
43 >                        QT_BLOCK_SIZE*4*sizeof(QUADTREE))) == NULL)
44             return(EMPTY);
45 +        quad_flag = (int4 *)realloc((char *)quad_flag,
46 +                        (QT_BLOCK(freet)+1)*QT_BLOCK_SIZE/(8*sizeof(int4)));
47 +        if (quad_flag == NULL)
48 +                return(EMPTY);
49      }
50      treetop += 4;
51      return(freet);
52   }
53  
54  
55 + qtClearAllFlags()               /* clear all quadtree branch flags */
56 + {
57 +        if (!treetop) return;
58 +        bzero((char *)quad_flag,
59 +                (QT_BLOCK(treetop-1)+1)*QT_BLOCK_SIZE/(8*sizeof(int4)));
60 + }
61 +
62 +
63   qtFree(qt)                      /* free a quadtree */
64     register QUADTREE  qt;
65   {
# Line 72 | Line 83 | qtDone()                       /* free EVERYTHING */
83  
84          for (i = 0; i < QT_MAX_BLK; i++)
85          {
86 <            free((char *)quad_block[i],
87 <                  (unsigned)QT_BLOCK_SIZE*4*sizeof(QUADTREE));
86 >            if (quad_block[i] == NULL)
87 >                break;
88 >            free((char *)quad_block[i]);
89              quad_block[i] = NULL;
90          }
91 +        if (i) free((char *)quad_flag);
92 +        quad_flag = NULL;
93          quad_free_list = EMPTY;
94          treetop = 0;
95   }
96  
97 +
98   QUADTREE
99   qtCompress(qt)                  /* recursively combine nodes */
100   register QUADTREE  qt;
# Line 101 | Line 116 | register QUADTREE  qt;
116      return(qres);
117   }
118  
119 +
120   QUADTREE
121 < qtLocate_leaf(qtptr,bcoord,type,which)
121 > *qtLocate_leaf(qtptr,bcoord,t0,t1,t2)
122   QUADTREE *qtptr;
123   double bcoord[3];
124 < char *type,*which;
124 > FVECT t0,t1,t2;
125   {
126    int i;
127    QUADTREE *child;
128 +  FVECT a,b,c;
129  
130      if(QT_IS_TREE(*qtptr))
131      {  
132        i = bary2d_child(bcoord);
133        child = QT_NTH_CHILD_PTR(*qtptr,i);
134 <      return(qtLocate_leaf(child,bcoord,type,which));
134 >      if(t0)
135 >      {
136 >        qtSubdivide_tri(t0,t1,t2,a,b,c);
137 >        qtNth_child_tri(t0,t1,t2,a,b,c,i,t0,t1,t2);
138 >      }
139 >      return(qtLocate_leaf(child,bcoord,t0,t1,t2));
140      }
141      else
142 <      return(*qtptr);
142 >      return(qtptr);
143   }
144  
145  
146  
147 + int
148 + qtLeaf_add_tri_from_pt(qtptr,bcoord,id,v0,v1,v2,n)
149 + QUADTREE *qtptr;
150 + double bcoord[3];
151 + int id;
152 + FVECT v0,v1,v2;
153 + int n;
154 + {
155 +  int i;
156 +  QUADTREE *child;
157 +  OBJECT os[MAXSET+1],*optr;
158 +  int found;
159 +  FVECT r0,r1,r2;
160 +  
161 +  if(QT_IS_TREE(*qtptr))
162 +  {  
163 +    QT_SET_FLAG(*qtptr);
164 +    i = bary2d_child(bcoord);
165 +    child = QT_NTH_CHILD_PTR(*qtptr,i);
166 +    return(qtLeaf_add_tri_from_pt(child,bcoord,id,v0,v1,v2,++n));
167 +  }
168 +  else
169 +    {
170 +      /* If this leave node emptry- create a new set */
171 +      if(QT_IS_EMPTY(*qtptr))
172 +        *qtptr = qtaddelem(*qtptr,id);
173 +      else
174 +      {
175 +          qtgetset(os,*qtptr);
176 +          /* If the set is too large: subdivide */
177 +          if(QT_SET_CNT(os) < QT_SET_THRESHOLD)
178 +            *qtptr = qtaddelem(*qtptr,id);
179 +          else
180 +          {
181 +            if (n < QT_MAX_LEVELS)
182 +            {
183 +                 /* If set size exceeds threshold: subdivide cell and
184 +                    reinsert set tris into cell
185 +                    */
186 +                 n++;
187 +                 qtfreeleaf(*qtptr);
188 +                 qtSubdivide(qtptr);
189 +                 QT_SET_FLAG(*qtptr);
190 +                 found = qtLeaf_add_tri_from_pt(qtptr,bcoord,id,v0,v1,v2,n);
191 + #if 0
192 +                 if(!found)
193 +                 {
194 + #ifdef TEST_DRIVER    
195 +      HANDLE_ERROR("qtAdd_tri():Found in parent but not children\n");
196 + #else
197 +                   eputs("qtAdd_tri():Found in parent but not children\n");
198 + #endif
199 +                 }
200 + #endif
201 +                 for(optr = &(os[1]),i = QT_SET_CNT(os); i > 0; i--)
202 +                 {
203 +                   id = QT_SET_NEXT_ELEM(optr);
204 +                   qtTri_verts_from_id(id,r0,r1,r2);
205 +                   found= qtLeaf_add_tri_from_pt(qtptr,bcoord,id,v0,v1,v2,++n);
206 + #ifdef DEBUG
207 +                 if(!found)
208 +                    eputs("qtAdd_tri():Reinsert-in parent but not children\n");
209 + #endif
210 +               }
211 +             }
212 +            else
213 +              if(QT_SET_CNT(os) < QT_MAX_SET)
214 +                {
215 +                  *qtptr = qtaddelem(*qtptr,id);
216 +                }
217 +              else
218 +                {
219 + #ifdef DEBUG
220 +                    eputs("qtAdd_tri():two many levels\n");
221 + #endif
222 +                    return(FALSE);
223 +                }
224 +          }
225 +      }
226 +  }
227 +  return(TRUE);
228 + }
229  
230 +
231 + int
232 + qtAdd_tri_from_point(qtptr,v0,v1,v2,pt,id)
233 + QUADTREE *qtptr;
234 + FVECT v0,v1,v2;
235 + FVECT pt;
236 + int id;
237 + {
238 +    char d,w;
239 +    int i,x,y;
240 +    QUADTREE *child;
241 +    QUADTREE qt;
242 +    FVECT i_pt,n,a,b,c,r0,r1,r2;
243 +    double pd,bcoord[3];
244 +    OBJECT os[MAXSET+1],*optr;
245 +    int found;
246 +        
247 +    /* Determine if point lies within pyramid (and therefore
248 +       inside a spherical quadtree cell):GT_INTERIOR, on one of the
249 +       pyramid sides (and on cell edge):GT_EDGE(1,2 or 3),
250 +       or on pyramid vertex (and on cell vertex):GT_VERTEX(1,2, or 3).
251 +       For each triangle edge: compare the
252 +       point against the plane formed by the edge and the view center
253 +    */
254 +    d = test_single_point_against_spherical_tri(v0,v1,v2,pt,&w);  
255 +
256 +    /* Not in this triangle */
257 +    if(!d)
258 +      return(FALSE);
259 +
260 +    /* Will return lowest level triangle containing point: It the
261 +       point is on an edge or vertex: will return first associated
262 +       triangle encountered in the child traversal- the others can
263 +       be derived using triangle adjacency information
264 +    */
265 +    if(QT_IS_TREE(*qtptr))
266 +    {  
267 +      QT_SET_FLAG(*qtptr);
268 +      /* Find the intersection point */
269 +      tri_plane_equation(v0,v1,v2,n,&pd,FALSE);
270 +      intersect_vector_plane(pt,n,pd,NULL,i_pt);
271 +
272 +      i = max_index(n);
273 +      x = (i+1)%3;
274 +      y = (i+2)%3;
275 +      /* Calculate barycentric coordinates of i_pt */
276 +      bary2d(v0[x],v0[y],v1[x],v1[y],v2[x],v2[y],i_pt[x],i_pt[y],bcoord);
277 +
278 +      i = bary2d_child(bcoord);
279 +      child = QT_NTH_CHILD_PTR(*qtptr,i);
280 +      /* NOTE: Optimize: only subdivide for specified child */
281 +      qtSubdivide_tri(v0,v1,v2,a,b,c);
282 +      qtNth_child_tri(v0,v1,v2,a,b,c,i,v0,v1,v2);
283 +      return(qtLeaf_add_tri_from_pt(child,bcoord,id,v0,v1,v2,1));
284 +    }
285 +    else
286 +   {
287 +      /* If this leave node emptry- create a new set */
288 +      if(QT_IS_EMPTY(*qtptr))
289 +        *qtptr = qtaddelem(*qtptr,id);
290 +      else
291 +      {
292 +          qtgetset(os,*qtptr);
293 +          /* If the set is too large: subdivide */
294 +          if(QT_SET_CNT(os) < QT_SET_THRESHOLD)
295 +            *qtptr = qtaddelem(*qtptr,id);
296 +          else
297 +          {
298 +                 /* If set size exceeds threshold: subdivide cell and
299 +                    reinsert set tris into cell
300 +                    */
301 +                 qtfreeleaf(*qtptr);
302 +                 qtSubdivide(qtptr);
303 +                 found = qtLeaf_add_tri_from_pt(qtptr,bcoord,id,v0,v1,v2,1);
304 + #if 0
305 +                 if(!found)
306 +                 {
307 + #ifdef TEST_DRIVER    
308 +      HANDLE_ERROR("qtAdd_tri():Found in parent but not children\n");
309 + #else
310 +                   eputs("qtAdd_tri():Found in parent but not children\n");
311 + #endif
312 +                 }
313 + #endif
314 +                 for(optr = &(os[1]),i = QT_SET_CNT(os); i > 0; i--)
315 +                 {
316 +                   id = QT_SET_NEXT_ELEM(optr);
317 +                   qtTri_verts_from_id(id,r0,r1,r2);
318 +                   found=qtAdd_tri(qtptr,id,r0,r1,r2,v0,v1,v2,1);
319 + #ifdef DEBUG
320 +                 if(!found)
321 +                    eputs("qtAdd_tri():Reinsert-in parent but not children\n");
322 + #endif
323 +               }
324 +             }
325 +      }
326 +  }
327 +  return(TRUE);
328 + }
329 +
330 +
331   QUADTREE
332 < qtRoot_point_locate(qtptr,v0,v1,v2,pt,type,which)
332 > *qtRoot_point_locate(qtptr,v0,v1,v2,pt,t0,t1,t2)
333   QUADTREE *qtptr;
334   FVECT v0,v1,v2;
335   FVECT pt;
336 < char *type,*which;
336 > FVECT t0,t1,t2;
337   {
338      char d,w;
339      int i,x,y;
340      QUADTREE *child;
341      QUADTREE qt;
342 <    FVECT n,i_pt;
342 >    FVECT n,i_pt,a,b,c;
343      double pd,bcoord[3];
344  
345      /* Determine if point lies within pyramid (and therefore
# Line 149 | Line 354 | char *type,*which;
354      /* Not in this triangle */
355      if(!d)
356      {
357 <      if(which)
153 <        *which = 0;
154 <      return(EMPTY);
357 >      return(NULL);
358      }
359  
360      /* Will return lowest level triangle containing point: It the
# Line 173 | Line 376 | char *type,*which;
376  
377        i = bary2d_child(bcoord);
378        child = QT_NTH_CHILD_PTR(*qtptr,i);
379 <      return(qtLocate_leaf(child,bcoord,type,which));
379 >      if(t0)
380 >      {
381 >        qtSubdivide_tri(v0,v1,v2,a,b,c);
382 >        qtNth_child_tri(v0,v1,v2,a,b,c,i,t0,t1,t2);
383 >      }
384 >      return(qtLocate_leaf(child,bcoord,t0,t1,t2));
385      }
386      else
387 <       if(!QT_IS_EMPTY(*qtptr))
180 <       {  
181 <           /* map GT_VERTEX,GT_EDGE,GT_FACE GT_INTERIOR of pyramid to
182 <              spherical triangle primitives
183 <              */
184 <         if(type)
185 <           *type = d;
186 <         if(which)
187 <           *which = w;
188 <         return(*qtptr);
189 <       }
190 <    return(EMPTY);
387 >      return(qtptr);
388   }
389  
390   int
# Line 197 | Line 394 | FVECT v0,v1,v2;
394   FVECT pt;
395   char *type,*which;
396   {
200 –    QUADTREE qt;
397      OBJECT os[MAXSET+1],*optr;
398      char d,w;
399      int i,id;
400      FVECT p0,p1,p2;
401  
402 <    qt = qtRoot_point_locate(qtptr,v0,v1,v2,pt,type,which);
402 >    qtptr = qtRoot_point_locate(qtptr,v0,v1,v2,pt,NULL,NULL,NULL);
403  
404 <    if(QT_IS_EMPTY(qt))
404 >    if(!qtptr || QT_IS_EMPTY(*qtptr))
405         return(EMPTY);
406      
407      /* Get the set */
408 <    qtgetset(os,qt);
408 >    qtgetset(os,*qtptr);
409      for (i = QT_SET_CNT(os),optr = QT_SET_PTR(os); i > 0; i--)
410      {
411          /* Find the triangle that pt falls in (NOTE:FOR now return first 1) */
# Line 304 | Line 500 | into the new child cells: it is assumed that "v1,v2,v3
500   */
501  
502   int
503 + qtRoot_add_tri(qtptr,id,t0,t1,t2,v0,v1,v2,n)
504 + QUADTREE *qtptr;
505 + int id;
506 + FVECT t0,t1,t2;
507 + FVECT v0,v1,v2;
508 + int n;
509 + {
510 +  char test;
511 +  int found;
512 +
513 +  test = spherical_tri_intersect(t0,t1,t2,v0,v1,v2);
514 +  if(!test)
515 +    return(FALSE);
516 +  
517 +  found = qtAdd_tri(qtptr,id,t0,t1,t2,v0,v1,v2,n);
518 +  return(found);
519 + }
520 +
521 + int
522 + qtRoot_add_tri_from_point(qtptr,id,t0,t1,t2,v0,v1,v2,n)
523 + QUADTREE *qtptr;
524 + int id;
525 + FVECT t0,t1,t2;
526 + FVECT v0,v1,v2;
527 + int n;
528 + {
529 +  char test;
530 +  int found;
531 +
532 +  test = spherical_tri_intersect(t0,t1,t2,v0,v1,v2);
533 +  if(!test)
534 +    return(FALSE);
535 +  
536 +  found = qtAdd_tri_from_point(qtptr,id,t0,t1,t2,v0,v1,v2,n);
537 +  return(found);
538 + }
539 +
540 + int
541   qtAdd_tri(qtptr,id,t0,t1,t2,v0,v1,v2,n)
542   QUADTREE *qtptr;
543   int id;
# Line 320 | Line 554 | int n;
554    int found;
555    FVECT r0,r1,r2;
556  
323 –  /* test if triangle (t0,t1,t2) overlaps cell triangle (v0,v1,v2) */
324 –  test = spherical_tri_intersect(t0,t1,t2,v0,v1,v2);
325 –
326 –  /* If triangles do not overlap: done */
327 –  if(!test)
328 –    return(FALSE);
557    found = 0;
330 –
558    /* if this is tree: recurse */
559    if(QT_IS_TREE(*qtptr))
560    {
561      n++;
562      qtSubdivide_tri(v0,v1,v2,a,b,c);
563 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t0,t1,t2,v0,a,c,n);
564 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t0,t1,t2,a,v1,b,n);
565 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t0,t1,t2,c,b,v2,n);
566 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t0,t1,t2,b,c,a,n);
563 >    test = spherical_tri_intersect(t0,t1,t2,v0,a,c);
564 >    if(test)
565 >      found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t0,t1,t2,v0,a,c,n);
566 >    test = spherical_tri_intersect(t0,t1,t2,a,v1,b);
567 >    if(test)
568 >      found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t0,t1,t2,a,v1,b,n);
569 >    test = spherical_tri_intersect(t0,t1,t2,c,b,v2);
570 >    if(test)
571 >      found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t0,t1,t2,c,b,v2,n);
572 >    test = spherical_tri_intersect(t0,t1,t2,b,c,a);
573 >    if(test)
574 >      found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t0,t1,t2,b,c,a,n);
575  
576   #if 0
577      if(!found)
# Line 353 | Line 588 | int n;
588    {
589        /* If this leave node emptry- create a new set */
590        if(QT_IS_EMPTY(*qtptr))
591 <      {
357 <          *qtptr = qtaddelem(*qtptr,id);
358 < #if 0
359 <          {
360 <              int k;
361 <              qtgetset(os,*qtptr);
362 <              printf("\n%d:\n",os[0]);
363 <              for(k=1; k <= os[0];k++)
364 <                 printf("%d ",os[k]);
365 <              printf("\n");
366 <          }
367 < #endif
368 <          /*
369 <          os[0] = 0;
370 <          insertelem(os,id);
371 <          qt = fullnode(os);
372 <          *qtptr = qt;
373 <          */
374 <      }
591 >        *qtptr = qtaddelem(*qtptr,id);
592        else
593        {
594            qtgetset(os,*qtptr);
595            /* If the set is too large: subdivide */
596            if(QT_SET_CNT(os) < QT_SET_THRESHOLD)
380 –          {
597              *qtptr = qtaddelem(*qtptr,id);
382 – #if 0
383 –            {
384 –              int k;
385 –              qtgetset(os,*qtptr);
386 –              printf("\n%d:\n",os[0]);
387 –              for(k=1; k <= os[0];k++)
388 –                 printf("%d ",os[k]);
389 –              printf("\n");
390 –          }
391 – #endif      
392 –            /*
393 –             insertelem(os,id);
394 –             *qtptr = fullnode(os);
395 –             */
396 –          }
598            else
599            {
600              if (n < QT_MAX_LEVELS)
# Line 541 | Line 742 | FVECT v0,v1,v2;
742            else
743            {
744              *qtptr = qtdelelem(*qtptr,id);
544 – #if 0
545 –            {
546 –              int k;
547 –              if(!QT_IS_EMPTY(*qtptr))
548 –              {qtgetset(os,*qtptr);
549 –              printf("\n%d:\n",os[0]);
550 –              for(k=1; k <= os[0];k++)
551 –                 printf("%d ",os[k]);
552 –              printf("\n");
553 –           }
554 –
555 –          }
556 – #endif
745          }
746        }
747    }
748    return(TRUE);
749   }
750 +
751  
752  
753  

Diff Legend

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