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.1 by gwlarson, Wed Aug 19 17:45:24 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 < qtPoint_locate(qtptr,v1,v2,v3,pt,type,which,p0,p1,p2)
121 > *qtLocate_leaf(qtptr,bcoord,t0,t1,t2)
122   QUADTREE *qtptr;
123 < FVECT v1,v2,v3;
123 > double bcoord[3];
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 >      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);
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 < char *type,*which;
110 < FVECT p0,p1,p2;
236 > int id;
237   {
238      char d,w;
239 <    int i;
239 >    int i,x,y;
240      QUADTREE *child;
241      QUADTREE qt;
242 <    FVECT a,b,c;
243 <    FVECT t1,t2,t3;
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,t0,t1,t2)
333 + QUADTREE *qtptr;
334 + FVECT v0,v1,v2;
335 + FVECT pt;
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,a,b,c;
343 +    double pd,bcoord[3];
344 +
345      /* Determine if point lies within pyramid (and therefore
346         inside a spherical quadtree cell):GT_INTERIOR, on one of the
347         pyramid sides (and on cell edge):GT_EDGE(1,2 or 3),
# Line 123 | Line 349 | FVECT p0,p1,p2;
349         For each triangle edge: compare the
350         point against the plane formed by the edge and the view center
351      */
352 <    d = test_single_point_against_spherical_tri(v1,v2,v3,pt,&w);  
352 >    d = test_single_point_against_spherical_tri(v0,v1,v2,pt,&w);  
353  
354      /* Not in this triangle */
355      if(!d)
356      {
357 <      if(which)
132 <        *which = 0;
133 <      return(EMPTY);
357 >      return(NULL);
358      }
359  
360      /* Will return lowest level triangle containing point: It the
# Line 138 | Line 362 | FVECT p0,p1,p2;
362         triangle encountered in the child traversal- the others can
363         be derived using triangle adjacency information
364      */
141 –    
365      if(QT_IS_TREE(*qtptr))
366      {  
367 <      qtSubdivide_tri(v1,v2,v3,a,b,c);
368 <      child = QT_NTH_CHILD_PTR(*qtptr,0);
369 <      if(!QT_IS_EMPTY(*child))
367 >      /* Find the intersection point */
368 >      tri_plane_equation(v0,v1,v2,n,&pd,FALSE);
369 >      intersect_vector_plane(pt,n,pd,NULL,i_pt);
370 >
371 >      i = max_index(n);
372 >      x = (i+1)%3;
373 >      y = (i+2)%3;
374 >      /* Calculate barycentric coordinates of i_pt */
375 >      bary2d(v0[x],v0[y],v1[x],v1[y],v2[x],v2[y],i_pt[x],i_pt[y],bcoord);
376 >
377 >      i = bary2d_child(bcoord);
378 >      child = QT_NTH_CHILD_PTR(*qtptr,i);
379 >      if(t0)
380        {
381 <        qt = qtPoint_locate(child,v1,a,c,pt,type,which,p0,p1,p2);
382 <        if(!QT_IS_EMPTY(qt))
150 <          return(qt);
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 <      child = QT_NTH_CHILD_PTR(*qtptr,1);
153 <      if(!QT_IS_EMPTY(*child))
154 <      {
155 <        qt = qtPoint_locate(child,a,b,c,pt,type,which,p0,p1,p2);
156 <        if(!QT_IS_EMPTY(qt))
157 <          return(qt);
158 <      }
159 <      child = QT_NTH_CHILD_PTR(*qtptr,2);
160 <      if(!QT_IS_EMPTY(*child))
161 <      {
162 <        qt = qtPoint_locate(child,a,v2,b,pt,type,which,p0,p1,p2);
163 <        if(!QT_IS_EMPTY(qt))
164 <          return(qt);
165 <      }
166 <      child = QT_NTH_CHILD_PTR(*qtptr,3);
167 <      if(!QT_IS_EMPTY(*child))
168 <      {
169 <        qt = qtPoint_locate(child,c,b,v3,pt,type,which,p0,p1,p2);
170 <        if(!QT_IS_EMPTY(qt))
171 <          return(qt);
172 <      }
384 >      return(qtLocate_leaf(child,bcoord,t0,t1,t2));
385      }
386      else
387 <       if(!QT_IS_EMPTY(*qtptr))
176 <       {  
177 <           /* map GT_VERTEX,GT_EDGE,GT_FACE GT_INTERIOR of pyramid to
178 <              spherical triangle primitives
179 <              */
180 <         if(type)
181 <           *type = d;
182 <         if(which)
183 <           *which = w;
184 <         VCOPY(p0,v1);
185 <         VCOPY(p1,v2);
186 <         VCOPY(p2,v3);
187 <         return(*qtptr);
188 <       }
189 <    return(EMPTY);
387 >      return(qtptr);
388   }
389  
390   int
# Line 196 | Line 394 | FVECT v0,v1,v2;
394   FVECT pt;
395   char *type,*which;
396   {
199 –    QUADTREE qt;
397      OBJECT os[MAXSET+1],*optr;
398      char d,w;
399      int i,id;
400      FVECT p0,p1,p2;
401 <  
402 <    qt = qtPoint_locate(qtptr,v0,v1,v2,pt,type,which,p0,p1,p2);
403 <    if(QT_IS_EMPTY(qt))
401 >
402 >    qtptr = qtRoot_point_locate(qtptr,v0,v1,v2,pt,NULL,NULL,NULL);
403 >
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 250 | Line 448 | int n;
448    return(node);
449   }
450  
451 < /* for triangle v1-v2-v3- returns a,b,c: children are:
451 > /* for triangle v0-v1-v2- returns a,b,c: children are:
452  
453 <        v3                     0: v1,a,c
454 <        /\                     1: a,b,c
455 <       /3 \                    2: a,v2,b
456 <     c/____\b                  3: c,b,v3
453 >        v2                     0: v0,a,c
454 >        /\                     1: a,v1,b                  
455 >       /2 \                    2: c,b,v2
456 >     c/____\b                  3: b,c,a
457       /\    /\  
458 <    /0 \1 /2 \
459 < v1/____\/____\v2
458 >    /0 \3 /1 \
459 >  v0____\/____\v1
460          a
461   */
462  
463 < qtSubdivide_tri(v1,v2,v3,a,b,c)
464 < FVECT v1,v2,v3;
463 > qtSubdivide_tri(v0,v1,v2,a,b,c)
464 > FVECT v0,v1,v2;
465   FVECT a,b,c;
466   {
467 <    EDGE_MIDPOINT_VEC3(a,v1,v2);
468 <    normalize(a);
469 <    EDGE_MIDPOINT_VEC3(b,v2,v3);
272 <    normalize(b);
273 <    EDGE_MIDPOINT_VEC3(c,v3,v1);
274 <    normalize(c);
467 >    EDGE_MIDPOINT_VEC3(a,v0,v1);
468 >    EDGE_MIDPOINT_VEC3(b,v1,v2);
469 >    EDGE_MIDPOINT_VEC3(c,v2,v0);
470   }
471  
472 < qtNth_child_tri(v1,v2,v3,a,b,c,i,r1,r2,r3)
473 < FVECT v1,v2,v3;
472 > qtNth_child_tri(v0,v1,v2,a,b,c,i,r0,r1,r2)
473 > FVECT v0,v1,v2;
474   FVECT a,b,c;
475   int i;
476 < FVECT r1,r2,r3;
476 > FVECT r0,r1,r2;
477   {
283 –  VCOPY(r1,a); VCOPY(r2,b);    VCOPY(r3,c);
478    switch(i){
479    case 0:  
480 <    VCOPY(r2,r1);
287 <    VCOPY(r1,v1);
480 >  VCOPY(r0,v0); VCOPY(r1,a);    VCOPY(r2,c);
481      break;
482    case 1:  
483 +  VCOPY(r0,a); VCOPY(r1,v1);    VCOPY(r2,b);
484      break;
485    case 2:  
486 <    VCOPY(r3,r2);
293 <    VCOPY(r2,v2);
486 >  VCOPY(r0,c); VCOPY(r1,b);    VCOPY(r2,v2);
487      break;
488    case 3:  
489 <    VCOPY(r1,r3);
297 <    VCOPY(r3,v3);
489 >  VCOPY(r0,b); VCOPY(r1,c);    VCOPY(r2,a);
490      break;
491    }
492   }
# Line 308 | Line 500 | into the new child cells: it is assumed that "v1,v2,v3
500   */
501  
502   int
503 < qtAdd_tri(qtptr,id,t1,t2,t3,v1,v2,v3,n)
503 > qtRoot_add_tri(qtptr,id,t0,t1,t2,v0,v1,v2,n)
504   QUADTREE *qtptr;
505   int id;
506 < FVECT t1,t2,t3;
507 < FVECT v1,v2,v3;
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;
544 + FVECT t0,t1,t2;
545 + FVECT v0,v1,v2;
546 + int n;
547 + {
548 +  
549 +  char test;
550    int i,index;
551    FVECT a,b,c;
552    OBJECT os[MAXSET+1],*optr;
553    QUADTREE qt;
554    int found;
555 <  FVECT r1,r2,r3;
555 >  FVECT r0,r1,r2;
556  
327 –  /* test if triangle (t1,t2,t3) overlaps cell triangle (v1,v2,v3) */
328 –  test = spherical_tri_intersect(t1,t2,t3,v1,v2,v3);
329 –
330 –  /* If triangles do not overlap: done */
331 –  if(!test)
332 –    return(FALSE);
557    found = 0;
334 –
558    /* if this is tree: recurse */
559    if(QT_IS_TREE(*qtptr))
560    {
561      n++;
562 <    qtSubdivide_tri(v1,v2,v3,a,b,c);
563 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t1,t2,t3,v1,a,c,n);
564 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t1,t2,t3,a,b,c,n);
565 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t1,t2,t3,a,v2,b,n);
566 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t1,t2,t3,c,b,v3,n);
562 >    qtSubdivide_tri(v0,v1,v2,a,b,c);
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 357 | Line 588 | int n;
588    {
589        /* If this leave node emptry- create a new set */
590        if(QT_IS_EMPTY(*qtptr))
591 <      {
361 <          *qtptr = qtaddelem(*qtptr,id);
362 < #if 0
363 <          {
364 <              int k;
365 <              qtgetset(os,*qtptr);
366 <              printf("\n%d:\n",os[0]);
367 <              for(k=1; k <= os[0];k++)
368 <                 printf("%d ",os[k]);
369 <              printf("\n");
370 <          }
371 < #endif
372 <          /*
373 <          os[0] = 0;
374 <          insertelem(os,id);
375 <          qt = fullnode(os);
376 <          *qtptr = qt;
377 <          */
378 <      }
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)
384 –          {
597              *qtptr = qtaddelem(*qtptr,id);
386 – #if 0
387 –            {
388 –              int k;
389 –              qtgetset(os,*qtptr);
390 –              printf("\n%d:\n",os[0]);
391 –              for(k=1; k <= os[0];k++)
392 –                 printf("%d ",os[k]);
393 –              printf("\n");
394 –          }
395 – #endif      
396 –            /*
397 –             insertelem(os,id);
398 –             *qtptr = fullnode(os);
399 –             */
400 –          }
598            else
599            {
600              if (n < QT_MAX_LEVELS)
# Line 408 | Line 605 | int n;
605                   n++;
606                   qtfreeleaf(*qtptr);
607                   qtSubdivide(qtptr);
608 <                 found = qtAdd_tri(qtptr,id,t1,t2,t3,v1,v2,v3,n);
608 >                 found = qtAdd_tri(qtptr,id,t0,t1,t2,v0,v1,v2,n);
609   #if 0
610                   if(!found)
611                   {
# Line 422 | Line 619 | int n;
619                   for(optr = &(os[1]),i = QT_SET_CNT(os); i > 0; i--)
620                   {
621                     id = QT_SET_NEXT_ELEM(optr);
622 <                   qtTri_verts_from_id(id,r1,r2,r3);
623 <                   found=qtAdd_tri(qtptr,id,r1,r2,r3,v1,v2,v3,n);
622 >                   qtTri_verts_from_id(id,r0,r1,r2);
623 >                   found=qtAdd_tri(qtptr,id,r0,r1,r2,v0,v1,v2,n);
624   #ifdef DEBUG
625                   if(!found)
626                      eputs("qtAdd_tri():Reinsert-in parent but not children\n");
# Line 464 | Line 661 | int n;
661  
662  
663   int
664 < qtApply_to_tri_cells(qtptr,t1,t2,t3,v1,v2,v3,func,arg)
664 > qtApply_to_tri_cells(qtptr,t0,t1,t2,v0,v1,v2,func,arg)
665   QUADTREE *qtptr;
666 < FVECT t1,t2,t3;
667 < FVECT v1,v2,v3;
666 > FVECT t0,t1,t2;
667 > FVECT v0,v1,v2;
668   int (*func)();
669   char *arg;
670   {
671    char test;
672    FVECT a,b,c;
673  
674 <  /* test if triangle (t1,t2,t3) overlaps cell triangle (v1,v2,v3) */
675 <  test = spherical_tri_intersect(t1,t2,t3,v1,v2,v3);
674 >  /* test if triangle (t0,t1,t2) overlaps cell triangle (v0,v1,v2) */
675 >  test = spherical_tri_intersect(t0,t1,t2,v0,v1,v2);
676  
677    /* If triangles do not overlap: done */
678    if(!test)
# Line 484 | Line 681 | char *arg;
681    /* if this is tree: recurse */
682    if(QT_IS_TREE(*qtptr))
683    {
684 <    qtSubdivide_tri(v1,v2,v3,a,b,c);
685 <    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,0),t1,t2,t3,v1,a,c,func,arg);
686 <    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,1),t1,t2,t3,a,b,c,func,arg);
687 <    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,2),t1,t2,t3,a,v2,b,func,arg);
688 <    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,3),t1,t2,t3,c,b,v3,func,arg);
684 >    qtSubdivide_tri(v0,v1,v2,a,b,c);
685 >    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,0),t0,t1,t2,v0,a,c,func,arg);
686 >    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,1),t0,t1,t2,a,v1,b,func,arg);
687 >    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,2),t0,t1,t2,c,b,v2,func,arg);
688 >    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,3),t0,t1,t2,b,c,a,func,arg);
689    }
690    else
691      return(func(qtptr,arg));
# Line 496 | Line 693 | char *arg;
693  
694  
695   int
696 < qtRemove_tri(qtptr,id,t1,t2,t3,v1,v2,v3)
696 > qtRemove_tri(qtptr,id,t0,t1,t2,v0,v1,v2)
697   QUADTREE *qtptr;
698   int id;
699 < FVECT t1,t2,t3;
700 < FVECT v1,v2,v3;
699 > FVECT t0,t1,t2;
700 > FVECT v0,v1,v2;
701   {
702    
703    char test;
# Line 508 | Line 705 | FVECT v1,v2,v3;
705    FVECT a,b,c;
706    OBJECT os[MAXSET+1];
707    
708 <  /* test if triangle (t1,t2,t3) overlaps cell triangle (v1,v2,v3) */
709 <  test = spherical_tri_intersect(t1,t2,t3,v1,v2,v3);
708 >  /* test if triangle (t0,t1,t2) overlaps cell triangle (v0,v1,v2) */
709 >  test = spherical_tri_intersect(t0,t1,t2,v0,v1,v2);
710  
711    /* If triangles do not overlap: done */
712    if(!test)
# Line 518 | Line 715 | FVECT v1,v2,v3;
715    /* if this is tree: recurse */
716    if(QT_IS_TREE(*qtptr))
717    {
718 <    qtSubdivide_tri(v1,v2,v3,a,b,c);
719 <    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t1,t2,t3,v1,a,c);
720 <    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t1,t2,t3,a,b,c);
721 <    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t1,t2,t3,a,v2,b);
722 <    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t1,t2,t3,c,b,v3);
718 >    qtSubdivide_tri(v0,v1,v2,a,b,c);
719 >    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t0,t1,t2,v0,a,c);
720 >    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t0,t1,t2,a,v1,b);
721 >    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t0,t1,t2,c,b,v2);
722 >    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t0,t1,t2,b,c,a);
723    }
724    else
725    {
# Line 545 | Line 742 | FVECT v1,v2,v3;
742            else
743            {
744              *qtptr = qtdelelem(*qtptr,id);
548 – #if 0
549 –            {
550 –              int k;
551 –              if(!QT_IS_EMPTY(*qtptr))
552 –              {qtgetset(os,*qtptr);
553 –              printf("\n%d:\n",os[0]);
554 –              for(k=1; k <= os[0];k++)
555 –                 printf("%d ",os[k]);
556 –              printf("\n");
557 –           }
558 –
559 –          }
560 – #endif
745          }
746        }
747    }
748    return(TRUE);
749   }
750 +
751 +
752 +
753 +
754 +
755 +
756 +
757 +
758 +
759 +
760 +
761 +

Diff Legend

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