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.2 by gwlarson, Thu Aug 20 16:47:21 1998 UTC

# Line 102 | Line 102 | register QUADTREE  qt;
102   }
103  
104   QUADTREE
105 < qtPoint_locate(qtptr,v1,v2,v3,pt,type,which,p0,p1,p2)
105 > qtLocate_leaf(qtptr,bcoord,type,which)
106   QUADTREE *qtptr;
107 < FVECT v1,v2,v3;
107 > double bcoord[3];
108 > char *type,*which;
109 > {
110 >  int i;
111 >  QUADTREE *child;
112 >
113 >    if(QT_IS_TREE(*qtptr))
114 >    {  
115 >      i = bary2d_child(bcoord);
116 >      child = QT_NTH_CHILD_PTR(*qtptr,i);
117 >      return(qtLocate_leaf(child,bcoord,type,which));
118 >    }
119 >    else
120 >      return(*qtptr);
121 > }
122 >
123 >
124 >
125 >
126 > QUADTREE
127 > qtRoot_point_locate(qtptr,v0,v1,v2,pt,type,which)
128 > QUADTREE *qtptr;
129 > FVECT v0,v1,v2;
130   FVECT pt;
131   char *type,*which;
110 – FVECT p0,p1,p2;
132   {
133      char d,w;
134 <    int i;
134 >    int i,x,y;
135      QUADTREE *child;
136      QUADTREE qt;
137 <    FVECT a,b,c;
138 <    FVECT t1,t2,t3;
137 >    FVECT n,i_pt;
138 >    double pd,bcoord[3];
139  
140      /* Determine if point lies within pyramid (and therefore
141         inside a spherical quadtree cell):GT_INTERIOR, on one of the
# Line 123 | Line 144 | FVECT p0,p1,p2;
144         For each triangle edge: compare the
145         point against the plane formed by the edge and the view center
146      */
147 <    d = test_single_point_against_spherical_tri(v1,v2,v3,pt,&w);  
147 >    d = test_single_point_against_spherical_tri(v0,v1,v2,pt,&w);  
148  
149      /* Not in this triangle */
150      if(!d)
# Line 138 | Line 159 | FVECT p0,p1,p2;
159         triangle encountered in the child traversal- the others can
160         be derived using triangle adjacency information
161      */
141 –    
162      if(QT_IS_TREE(*qtptr))
163      {  
164 <      qtSubdivide_tri(v1,v2,v3,a,b,c);
165 <      child = QT_NTH_CHILD_PTR(*qtptr,0);
166 <      if(!QT_IS_EMPTY(*child))
167 <      {
168 <        qt = qtPoint_locate(child,v1,a,c,pt,type,which,p0,p1,p2);
169 <        if(!QT_IS_EMPTY(qt))
170 <          return(qt);
171 <      }
172 <      child = QT_NTH_CHILD_PTR(*qtptr,1);
173 <      if(!QT_IS_EMPTY(*child))
174 <      {
175 <        qt = qtPoint_locate(child,a,b,c,pt,type,which,p0,p1,p2);
176 <        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 <      }
164 >      /* Find the intersection point */
165 >      tri_plane_equation(v0,v1,v2,n,&pd,FALSE);
166 >      intersect_vector_plane(pt,n,pd,NULL,i_pt);
167 >
168 >      i = max_index(n);
169 >      x = (i+1)%3;
170 >      y = (i+2)%3;
171 >      /* Calculate barycentric coordinates of i_pt */
172 >      bary2d(v0[x],v0[y],v1[x],v1[y],v2[x],v2[y],i_pt[x],i_pt[y],bcoord);
173 >
174 >      i = bary2d_child(bcoord);
175 >      child = QT_NTH_CHILD_PTR(*qtptr,i);
176 >      return(qtLocate_leaf(child,bcoord,type,which));
177      }
178      else
179         if(!QT_IS_EMPTY(*qtptr))
# Line 181 | Line 185 | FVECT p0,p1,p2;
185             *type = d;
186           if(which)
187             *which = w;
184 –         VCOPY(p0,v1);
185 –         VCOPY(p1,v2);
186 –         VCOPY(p2,v3);
188           return(*qtptr);
189         }
190      return(EMPTY);
# Line 201 | Line 202 | char *type,*which;
202      char d,w;
203      int i,id;
204      FVECT p0,p1,p2;
205 <  
206 <    qt = qtPoint_locate(qtptr,v0,v1,v2,pt,type,which,p0,p1,p2);
205 >
206 >    qt = qtRoot_point_locate(qtptr,v0,v1,v2,pt,type,which);
207 >
208      if(QT_IS_EMPTY(qt))
209         return(EMPTY);
210      
# Line 250 | Line 252 | int n;
252    return(node);
253   }
254  
255 < /* for triangle v1-v2-v3- returns a,b,c: children are:
255 > /* for triangle v0-v1-v2- returns a,b,c: children are:
256  
257 <        v3                     0: v1,a,c
258 <        /\                     1: a,b,c
259 <       /3 \                    2: a,v2,b
260 <     c/____\b                  3: c,b,v3
257 >        v2                     0: v0,a,c
258 >        /\                     1: a,v1,b                  
259 >       /2 \                    2: c,b,v2
260 >     c/____\b                  3: b,c,a
261       /\    /\  
262 <    /0 \1 /2 \
263 < v1/____\/____\v2
262 >    /0 \3 /1 \
263 >  v0____\/____\v1
264          a
265   */
266  
267 < qtSubdivide_tri(v1,v2,v3,a,b,c)
268 < FVECT v1,v2,v3;
267 > qtSubdivide_tri(v0,v1,v2,a,b,c)
268 > FVECT v0,v1,v2;
269   FVECT a,b,c;
270   {
271 <    EDGE_MIDPOINT_VEC3(a,v1,v2);
272 <    normalize(a);
273 <    EDGE_MIDPOINT_VEC3(b,v2,v3);
272 <    normalize(b);
273 <    EDGE_MIDPOINT_VEC3(c,v3,v1);
274 <    normalize(c);
271 >    EDGE_MIDPOINT_VEC3(a,v0,v1);
272 >    EDGE_MIDPOINT_VEC3(b,v1,v2);
273 >    EDGE_MIDPOINT_VEC3(c,v2,v0);
274   }
275  
276 < qtNth_child_tri(v1,v2,v3,a,b,c,i,r1,r2,r3)
277 < FVECT v1,v2,v3;
276 > qtNth_child_tri(v0,v1,v2,a,b,c,i,r0,r1,r2)
277 > FVECT v0,v1,v2;
278   FVECT a,b,c;
279   int i;
280 < FVECT r1,r2,r3;
280 > FVECT r0,r1,r2;
281   {
283 –  VCOPY(r1,a); VCOPY(r2,b);    VCOPY(r3,c);
282    switch(i){
283    case 0:  
284 <    VCOPY(r2,r1);
287 <    VCOPY(r1,v1);
284 >  VCOPY(r0,v0); VCOPY(r1,a);    VCOPY(r2,c);
285      break;
286    case 1:  
287 +  VCOPY(r0,a); VCOPY(r1,v1);    VCOPY(r2,b);
288      break;
289    case 2:  
290 <    VCOPY(r3,r2);
293 <    VCOPY(r2,v2);
290 >  VCOPY(r0,c); VCOPY(r1,b);    VCOPY(r2,v2);
291      break;
292    case 3:  
293 <    VCOPY(r1,r3);
297 <    VCOPY(r3,v3);
293 >  VCOPY(r0,b); VCOPY(r1,c);    VCOPY(r2,a);
294      break;
295    }
296   }
# Line 308 | Line 304 | into the new child cells: it is assumed that "v1,v2,v3
304   */
305  
306   int
307 < qtAdd_tri(qtptr,id,t1,t2,t3,v1,v2,v3,n)
307 > qtAdd_tri(qtptr,id,t0,t1,t2,v0,v1,v2,n)
308   QUADTREE *qtptr;
309   int id;
310 < FVECT t1,t2,t3;
311 < FVECT v1,v2,v3;
310 > FVECT t0,t1,t2;
311 > FVECT v0,v1,v2;
312   int n;
313   {
314    
# Line 322 | Line 318 | int n;
318    OBJECT os[MAXSET+1],*optr;
319    QUADTREE qt;
320    int found;
321 <  FVECT r1,r2,r3;
321 >  FVECT r0,r1,r2;
322  
323 <  /* test if triangle (t1,t2,t3) overlaps cell triangle (v1,v2,v3) */
324 <  test = spherical_tri_intersect(t1,t2,t3,v1,v2,v3);
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)
# Line 336 | Line 332 | int n;
332    if(QT_IS_TREE(*qtptr))
333    {
334      n++;
335 <    qtSubdivide_tri(v1,v2,v3,a,b,c);
336 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t1,t2,t3,v1,a,c,n);
337 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t1,t2,t3,a,b,c,n);
338 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t1,t2,t3,a,v2,b,n);
339 <    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t1,t2,t3,c,b,v3,n);
335 >    qtSubdivide_tri(v0,v1,v2,a,b,c);
336 >    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t0,t1,t2,v0,a,c,n);
337 >    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t0,t1,t2,a,v1,b,n);
338 >    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t0,t1,t2,c,b,v2,n);
339 >    found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t0,t1,t2,b,c,a,n);
340  
341   #if 0
342      if(!found)
# Line 408 | Line 404 | int n;
404                   n++;
405                   qtfreeleaf(*qtptr);
406                   qtSubdivide(qtptr);
407 <                 found = qtAdd_tri(qtptr,id,t1,t2,t3,v1,v2,v3,n);
407 >                 found = qtAdd_tri(qtptr,id,t0,t1,t2,v0,v1,v2,n);
408   #if 0
409                   if(!found)
410                   {
# Line 422 | Line 418 | int n;
418                   for(optr = &(os[1]),i = QT_SET_CNT(os); i > 0; i--)
419                   {
420                     id = QT_SET_NEXT_ELEM(optr);
421 <                   qtTri_verts_from_id(id,r1,r2,r3);
422 <                   found=qtAdd_tri(qtptr,id,r1,r2,r3,v1,v2,v3,n);
421 >                   qtTri_verts_from_id(id,r0,r1,r2);
422 >                   found=qtAdd_tri(qtptr,id,r0,r1,r2,v0,v1,v2,n);
423   #ifdef DEBUG
424                   if(!found)
425                      eputs("qtAdd_tri():Reinsert-in parent but not children\n");
# Line 464 | Line 460 | int n;
460  
461  
462   int
463 < qtApply_to_tri_cells(qtptr,t1,t2,t3,v1,v2,v3,func,arg)
463 > qtApply_to_tri_cells(qtptr,t0,t1,t2,v0,v1,v2,func,arg)
464   QUADTREE *qtptr;
465 < FVECT t1,t2,t3;
466 < FVECT v1,v2,v3;
465 > FVECT t0,t1,t2;
466 > FVECT v0,v1,v2;
467   int (*func)();
468   char *arg;
469   {
470    char test;
471    FVECT a,b,c;
472  
473 <  /* test if triangle (t1,t2,t3) overlaps cell triangle (v1,v2,v3) */
474 <  test = spherical_tri_intersect(t1,t2,t3,v1,v2,v3);
473 >  /* test if triangle (t0,t1,t2) overlaps cell triangle (v0,v1,v2) */
474 >  test = spherical_tri_intersect(t0,t1,t2,v0,v1,v2);
475  
476    /* If triangles do not overlap: done */
477    if(!test)
# Line 484 | Line 480 | char *arg;
480    /* if this is tree: recurse */
481    if(QT_IS_TREE(*qtptr))
482    {
483 <    qtSubdivide_tri(v1,v2,v3,a,b,c);
484 <    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,0),t1,t2,t3,v1,a,c,func,arg);
485 <    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,1),t1,t2,t3,a,b,c,func,arg);
486 <    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,2),t1,t2,t3,a,v2,b,func,arg);
487 <    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,3),t1,t2,t3,c,b,v3,func,arg);
483 >    qtSubdivide_tri(v0,v1,v2,a,b,c);
484 >    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,0),t0,t1,t2,v0,a,c,func,arg);
485 >    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,1),t0,t1,t2,a,v1,b,func,arg);
486 >    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,2),t0,t1,t2,c,b,v2,func,arg);
487 >    qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,3),t0,t1,t2,b,c,a,func,arg);
488    }
489    else
490      return(func(qtptr,arg));
# Line 496 | Line 492 | char *arg;
492  
493  
494   int
495 < qtRemove_tri(qtptr,id,t1,t2,t3,v1,v2,v3)
495 > qtRemove_tri(qtptr,id,t0,t1,t2,v0,v1,v2)
496   QUADTREE *qtptr;
497   int id;
498 < FVECT t1,t2,t3;
499 < FVECT v1,v2,v3;
498 > FVECT t0,t1,t2;
499 > FVECT v0,v1,v2;
500   {
501    
502    char test;
# Line 508 | Line 504 | FVECT v1,v2,v3;
504    FVECT a,b,c;
505    OBJECT os[MAXSET+1];
506    
507 <  /* test if triangle (t1,t2,t3) overlaps cell triangle (v1,v2,v3) */
508 <  test = spherical_tri_intersect(t1,t2,t3,v1,v2,v3);
507 >  /* test if triangle (t0,t1,t2) overlaps cell triangle (v0,v1,v2) */
508 >  test = spherical_tri_intersect(t0,t1,t2,v0,v1,v2);
509  
510    /* If triangles do not overlap: done */
511    if(!test)
# Line 518 | Line 514 | FVECT v1,v2,v3;
514    /* if this is tree: recurse */
515    if(QT_IS_TREE(*qtptr))
516    {
517 <    qtSubdivide_tri(v1,v2,v3,a,b,c);
518 <    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t1,t2,t3,v1,a,c);
519 <    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t1,t2,t3,a,b,c);
520 <    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t1,t2,t3,a,v2,b);
521 <    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t1,t2,t3,c,b,v3);
517 >    qtSubdivide_tri(v0,v1,v2,a,b,c);
518 >    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t0,t1,t2,v0,a,c);
519 >    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t0,t1,t2,a,v1,b);
520 >    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t0,t1,t2,c,b,v2);
521 >    qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t0,t1,t2,b,c,a);
522    }
523    else
524    {
# Line 563 | Line 559 | FVECT v1,v2,v3;
559    }
560    return(TRUE);
561   }
562 +
563 +
564 +
565 +
566 +
567 +
568 +
569 +
570 +
571 +
572 +

Diff Legend

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