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

Comparing ray/src/hd/sm_stree.c (file contents):
Revision 3.3 by gwlarson, Tue Aug 25 11:03:27 1998 UTC vs.
Revision 3.4 by gwlarson, Fri Sep 11 11:52:27 1998 UTC

# Line 8 | Line 8 | static char SCCSid[] = "$SunId$ SGI";
8   * sm_stree.c
9   */
10   #include "standard.h"
11 – #include "object.h"
12 –
11   #include "sm_geom.h"
12   #include "sm_stree.h"
13  
16 –
14   /* Define 4 vertices on the sphere to create a tetrahedralization on
15     the sphere: triangles are as follows:
16 <        (0,1,2),(0,2,3), (0,3,1), (1,3,2)
16 >        (2,1,0),(3,2,0), (1,3,0), (2,3,1)
17   */
18  
19 + #ifdef TEST_DRIVER
20 + extern FVECT Pick_point[500],Pick_v0[500],Pick_v1[500],Pick_v2[500];
21 + extern int Pick_cnt;
22 + #endif
23   FVECT stDefault_base[4] = { {SQRT3_INV, SQRT3_INV, SQRT3_INV},
24                            {-SQRT3_INV, -SQRT3_INV, SQRT3_INV},
25                            {-SQRT3_INV, SQRT3_INV, -SQRT3_INV},
26                            {SQRT3_INV, -SQRT3_INV, -SQRT3_INV}};
27 < int stTri_verts[4][3] = { {2,1,0},
28 <                          {3,2,0},
28 <                          {1,3,0},
29 <                          {2,3,1}};
27 > int stTri_verts[4][3] = { {2,1,0},{3,2,0},{1,3,0},{2,3,1}};
28 > int stTri_nbrs[4][3] =  { {2,1,3},{0,2,3},{1,0,3},{2,0,1}};
29  
30   stNth_base_verts(st,i,v1,v2,v3)
31   STREE *st;
# Line 101 | Line 100 | STREE *st;
100     "which" specifies which vertex (0,1,2) or edge (0=v0v1, 1 = v1v2, 2 = v21)
101   */
102   int
103 < stPoint_locate(st,npt,type,which)
103 > stPoint_locate(st,npt)
104      STREE *st;
105      FVECT npt;
107 –    char *type,*which;
106   {
107      int i,d,j,id;
108      QUADTREE *rootptr,*qtptr;
109      FVECT v1,v2,v3;
110 <    OBJECT os[MAXSET+1],*optr;
113 <    char w;
110 >    OBJECT os[QT_MAXSET+1],*optr;
111      FVECT p0,p1,p2;
112  
113      /* Test each of the root triangles against point id */
# Line 120 | Line 117 | stPoint_locate(st,npt,type,which)
117           stNth_base_verts(st,i,v1,v2,v3);
118           /* Return tri that p falls in */
119           qtptr = qtRoot_point_locate(rootptr,v1,v2,v3,npt,NULL,NULL,NULL);
120 <         if(!qtptr)
120 >         if(!qtptr || QT_IS_EMPTY(*qtptr))
121              continue;
122           /* Get the set */
123 <         qtgetset(os,*qtptr);
124 <         for (j = QT_SET_CNT(os),optr = QT_SET_PTR(os); j > 0; j--)
123 >         optr = qtqueryset(*qtptr);
124 >         for (j = QT_SET_CNT(optr),optr = QT_SET_PTR(optr);j > 0; j--)
125           {
126               /* Find the first triangle that pt falls */
127               id = QT_SET_NEXT_ELEM(optr);
128 <             qtTri_verts_from_id(id,p0,p1,p2);
129 <             d = test_single_point_against_spherical_tri(p0,p1,p2,npt,&w);  
128 >             qtTri_from_id(id,NULL,NULL,NULL,p0,p1,p2,NULL,NULL,NULL);
129 >             d = point_in_stri(p0,p1,p2,npt);  
130               if(d)
131 <                {
135 <                    if(type)
136 <                       *type = d;
137 <                    if(which)
138 <                       *which = w;
139 <                    return(id);
140 <                }
131 >               return(id);
132           }
133       }
143 –    if(which)
144 –      *which = 0;
145 –    if(type)
146 –      *type = 0;
134      return(EMPTY);
135   }
136  
# Line 163 | Line 150 | QUADTREE
150       {
151           rootptr = ST_NTH_ROOT_PTR(st,i);
152           stNth_base_verts(st,i,v0,v1,v2);
153 <         /* Return tri that p falls in */
153 >         /* Return quadtree tri that p falls in */
154           qtptr = qtRoot_point_locate(rootptr,v0,v1,v2,p,t0,t1,t2);
168 –         /* NOTE: For now return only one triangle */
155           if(qtptr)
156              return(qtptr);
157       }    /* Point not found */
# Line 173 | Line 159 | QUADTREE
159   }
160  
161  
176 – QUADTREE
177 – *stAdd_tri_from_pt(st,p,t_id)
178 –    STREE *st;
179 –    FVECT p;
180 –    int t_id;
181 – {
182 –    int i,d;
183 –    QUADTREE *rootptr,*qtptr;
184 –    FVECT v0,v1,v2;
185 –
186 –    
187 –    /* Test each of the root triangles against point id */
188 –    for(i=0; i < 4; i++)
189 –     {
190 –         rootptr = ST_NTH_ROOT_PTR(st,i);
191 –         stNth_base_verts(st,i,v0,v1,v2);
192 –         /* Return tri that p falls in */
193 –         qtptr = qtRoot_add_tri_from_point(rootptr,v0,v1,v2,p,t_id);
194 –         /* NOTE: For now return only one triangle */
195 –         if(qtptr)
196 –            return(qtptr);
197 –     }    /* Point not found */
198 –    return(NULL);
199 – }
200 –
162   int
163   stAdd_tri(st,id,v0,v1,v2)
164   STREE *st;
# Line 214 | Line 175 | FVECT v0,v1,v2;
175    {
176      rootptr = ST_NTH_ROOT_PTR(st,i);
177      stNth_base_verts(st,i,t0,t1,t2);
178 <    found |= qtRoot_add_tri(rootptr,id,v0,v1,v2,t0,t1,t2,0);
178 >    found |= qtRoot_add_tri(rootptr,t0,t1,t2,v0,v1,v2,id,0);
179    }
180    return(found);
181   }
# Line 224 | Line 185 | stApply_to_tri_cells(st,v0,v1,v2,func,arg)
185   STREE *st;
186   FVECT v0,v1,v2;
187   int (*func)();
188 < char *arg;
188 > int *arg;
189   {
190    int i,found;
191    QUADTREE *rootptr;
192    FVECT t0,t1,t2;
193  
194    found = 0;
195 +  func(ST_ROOT_PTR(st),arg);
196 +  QT_SET_FLAG(ST_ROOT(st));
197    for(i=0; i < 4; i++)
198    {
199      rootptr = ST_NTH_ROOT_PTR(st,i);
# Line 264 | Line 227 | FVECT v0,v1,v2;
227    return(found);
228   }
229  
230 + int
231 + stVisit_tri_edges(st,t0,t1,t2,func,arg1,arg2)
232 +   STREE *st;
233 +   FVECT t0,t1,t2;
234 +   int (*func)();
235 +   int *arg1,arg2;
236 + {
237 +    int id,i,w;
238 +    QUADTREE *rootptr;
239 +    FVECT q0,q1,q2,n,v[3],sdir[3],dir[3],tv,d;
240 +    double pd,t;
241  
242 +    VCOPY(v[0],t0); VCOPY(v[1],t1); VCOPY(v[2],t2);
243 +    VSUB(dir[0],t1,t0); VSUB(dir[1],t2,t1);VSUB(dir[2],t0,t2);
244 +    VCOPY(sdir[0],dir[0]);VCOPY(sdir[1],dir[1]);VCOPY(sdir[2],dir[2]);
245 +    w = 0;
246 +    for(i=0; i < 4; i++)
247 +     {
248 + #ifdef TEST_DRIVER
249 + Pick_cnt = 0;
250 + #endif
251 +         rootptr = ST_NTH_ROOT_PTR(st,i);
252 +         stNth_base_verts(st,i,q0,q1,q2);
253 +         /* Return quadtree tri that p falls in */
254 +         if(!point_in_stri(q0,q1,q2,v[w]))  
255 +           continue;
256 +         id = qtRoot_visit_tri_edges(rootptr,q0,q1,q2,v,dir,&w,func,arg1,arg2);
257 +         if(id == INVALID)
258 +         {
259 + #ifdef DEBUG
260 +           eputs("stVisit_tri_edges(): Unable to trace edges\n");
261 + #endif
262 +           return(INVALID);
263 +         }
264 +         if(id == QT_DONE)
265 +            return(*arg1);
266 +        
267 +         /* Crossed over to next cell: id = nbr */
268 +         while(1)
269 +         {
270 +             /* test if ray crosses plane between this quadtree triangle and
271 +                its neighbor- if it does then find intersection point with
272 +                ray and plane- this is the new origin
273 +                */
274 +           if(id==0)
275 +             VCROSS(n,q1,q2);
276 +           else
277 +             if(id==1)
278 +               VCROSS(n,q2,q0);
279 +           else
280 +             VCROSS(n,q0,q1);
281  
282 +           if(w==0)
283 +             VCOPY(tv,t0);
284 +           else
285 +             if(w==1)
286 +               VCOPY(tv,t1);
287 +           else
288 +             VCOPY(tv,t2);
289 +           if(!intersect_ray_plane(tv,sdir[w],n,0.0,&t,v[w]))
290 +             return(INVALID);
291  
292 +           VSUM(v[w],v[w],sdir[w],10.0*FTINY);
293  
294 +           t = (1.0-t-10.0*FTINY);
295 +           if(t <= 0.0)
296 +           {
297 +             t = FTINY;
298   #if 0
299 +             eputs("stVisit_tri_edges(): edge end on plane\n");
300 + #endif
301 +           }
302 +           dir[w][0] = sdir[w][0] * t;
303 +           dir[w][1] = sdir[w][1] * t;
304 +           dir[w][2] = sdir[w][2] * t;
305 +           i = stTri_nbrs[i][id];
306 +           rootptr = ST_NTH_ROOT_PTR(st,i);
307 +           stNth_base_verts(st,i,q0,q1,q2);
308 +           id=qtRoot_visit_tri_edges(rootptr,q0,q1,q2,v,dir,&w,func,arg1,arg2);
309 +           if(id == QT_DONE)
310 +             return(*arg1);
311 +           if(id == INVALID)
312 +             {
313 + #if 0
314 +             eputs("stVisit_tri_edges(): point not found\n");
315 + #endif  
316 +             return(INVALID);
317 +             }
318 +          
319 +         }
320 +     }    /* Point not found */
321 +    return(INVALID);
322 + }
323 +
324 +
325   int
326 < stAdd_tri_opt(st,id,v0,v1,v2)
327 < STREE *st;
328 < int id;
329 < FVECT v0,v1,v2;
326 > stVisit_tri_edges2(st,t0,t1,t2,func,arg1,arg2)
327 >   STREE *st;
328 >   FVECT t0,t1,t2;
329 >   int (*func)();
330 >   int *arg1,arg2;
331   {
332 <  
333 <  int i,found;
334 <  QUADTREE *qtptr;
281 <  FVECT pt,t0,t1,t2;
332 >    int id,i,w;
333 >    QUADTREE *rootptr;
334 >    FVECT q0,q1,q2,v[3],i_pt;
335  
336 +    VCOPY(v[0],t0); VCOPY(v[1],t1); VCOPY(v[2],t2);
337 +    w = -1;
338 +    for(i=0; i < 4; i++)
339 +     {
340 + #ifdef TEST_DRIVER
341 + Pick_cnt = 0;
342 + #endif
343 +         rootptr = ST_NTH_ROOT_PTR(st,i);
344 +         stNth_base_verts(st,i,q0,q1,q2);
345 +         /* Return quadtree tri that p falls in */
346 +         if(!point_in_stri(q0,q1,q2,v[0]))  
347 +           continue;
348 +         id = qtRoot_visit_tri_edges2(rootptr,q0,q1,q2,v,i_pt,&w,
349 +                                      func,arg1,arg2);
350 +         if(id == INVALID)
351 +         {
352 + #ifdef DEBUG
353 +           eputs("stVisit_tri_edges(): Unable to trace edges\n");
354 + #endif
355 +           return(INVALID);
356 +         }
357 +         if(id == QT_DONE)
358 +            return(*arg1);
359 +        
360 +         /* Crossed over to next cell: id = nbr */
361 +         while(1)
362 +         {
363 +             /* test if ray crosses plane between this quadtree triangle and
364 +                its neighbor- if it does then find intersection point with
365 +                ray and plane- this is the new origin
366 +                */
367 +           i = stTri_nbrs[i][id];
368 +           rootptr = ST_NTH_ROOT_PTR(st,i);
369 +           stNth_base_verts(st,i,q0,q1,q2);
370 +           id=qtRoot_visit_tri_edges2(rootptr,q0,q1,q2,v,i_pt,&w,
371 +                                      func,arg1,arg2);
372 +           if(id == QT_DONE)
373 +             return(*arg1);
374 +           if(id == INVALID)
375 +             {
376 + #ifdef DEBUG
377 +             eputs("stVisit_tri_edges(): point not found\n");
378 + #endif  
379 +             return(INVALID);
380 +             }
381 +          
382 +         }
383 +     }    /* Point not found */
384 +    return(INVALID);
385 + }
386 +
387 + int
388 + stTrace_edge(st,orig,dir,max_t,func,arg1,arg2)
389 +   STREE *st;
390 +   FVECT orig,dir;
391 +   double max_t;
392 +   int (*func)();
393 +   int *arg1,arg2;
394 + {
395 +    int id,i;
396 +    QUADTREE *rootptr;
397 +    FVECT q0,q1,q2,o,n,d;
398 +    double pd,t;
399 +
400 + #if DEBUG
401 +    if(max_t > 1.0 || max_t < 0.0)
402 +    {
403 +      eputs("stTrace_edge(): max_t must be in [0,1]:adjusting\n");
404 +      max_t = 1.0;
405 +    }
406 + #endif
407 +
408 +    VCOPY(o,orig);
409 +    for(i=0; i < 4; i++)
410 +     {
411 + #ifdef TEST_DRIVER
412 + Pick_cnt = 0;
413 + #endif
414 +         rootptr = ST_NTH_ROOT_PTR(st,i);
415 +         stNth_base_verts(st,i,q0,q1,q2);
416 +         /* Return quadtree tri that p falls in */
417 +         id= qtRoot_trace_edge(rootptr,q0,q1,q2,o,dir,max_t,func,arg1,arg2);
418 +         if(id == INVALID)
419 +           continue;
420 +         if(id == QT_DONE)
421 +            return(*arg1);
422 +        
423 +         /* Crossed over to next cell: id = nbr */
424 +         while(1)
425 +         {
426 +             /* test if ray crosses plane between this quadtree triangle and
427 +                its neighbor- if it does then find intersection point with
428 +                ray and plane- this is the new origin
429 +                */
430 +           if(id==0)
431 +             VCROSS(n,q1,q2);
432 +           else
433 +             if(id==1)
434 +               VCROSS(n,q2,q0);
435 +           else
436 +             VCROSS(n,q0,q1);
437 +
438 +           /* Ray does not cross into next cell: done and tri not found*/
439 +           if(!intersect_ray_plane(orig,dir,n,0.0,&t,o))
440 +             return(INVALID);
441 +
442 +           VSUM(o,o,dir,10*FTINY);
443 +
444 +           d[0] = dir[0]*(1-t-10*FTINY);
445 +           d[1] = dir[1]*(1-t-10*FTINY);
446 +           d[2] = dir[2]*(1-t-10*FTINY);
447 +           i = stTri_nbrs[i][id];
448 +           rootptr = ST_NTH_ROOT_PTR(st,i);
449 +           stNth_base_verts(st,i,q0,q1,q2);
450 +           id = qtRoot_trace_edge(rootptr,q0,q1,q2,o,d,max_t,func,arg1,arg2);
451 +           if(id == QT_DONE)
452 +             return(*arg1);
453 +           if(id == INVALID)
454 +             {
455 + #if 0
456 +             eputs("stTrace_edges(): point not found\n");
457 + #endif  
458 +             return(INVALID);
459 +             }
460 +          
461 +         }
462 +     }    /* Point not found */
463 +    return(INVALID);
464 + }
465 +
466 +
467 +
468 + int
469 + stTrace_ray(st,orig,dir,func,arg1,arg2)
470 +   STREE *st;
471 +   FVECT orig,dir;
472 +   int (*func)();
473 +   int *arg1,arg2;
474 + {
475 +    int id,i;
476 +    QUADTREE *rootptr;
477 +    FVECT q0,q1,q2,o,n;
478 +    double pd,t;
479 +
480 +    VCOPY(o,orig);
481 +    for(i=0; i < 4; i++)
482 +     {
483 + #ifdef TEST_DRIVER
484 + Pick_cnt = 0;
485 + #endif
486 +         rootptr = ST_NTH_ROOT_PTR(st,i);
487 +         stNth_base_verts(st,i,q0,q1,q2);
488 +         /* Return quadtree tri that p falls in */
489 +         id= qtRoot_trace_ray(rootptr,q0,q1,q2,o,dir,func,arg1,arg2);
490 +         if(id == INVALID)
491 +           continue;
492 +         if(id == QT_DONE)
493 +            return(*arg1);
494 +        
495 +         /* Crossed over to next cell: id = nbr */
496 +         while(1)
497 +         {
498 +             /* test if ray crosses plane between this quadtree triangle and
499 +                its neighbor- if it does then find intersection point with
500 +                ray and plane- this is the new origin
501 +                */
502 +           if(id==0)
503 +             VCROSS(n,q1,q2);
504 +           else
505 +             if(id==1)
506 +               VCROSS(n,q2,q0);
507 +           else
508 +             VCROSS(n,q0,q1);
509 +
510 +           /* Ray does not cross into next cell: done and tri not found*/
511 +           if(!intersect_ray_plane(orig,dir,n,0.0,NULL,o))
512 +             return(INVALID);
513 +
514 +           VSUM(o,o,dir,10*FTINY);
515 +           i = stTri_nbrs[i][id];
516 +           rootptr = ST_NTH_ROOT_PTR(st,i);
517 +           stNth_base_verts(st,i,q0,q1,q2);
518 +           id = qtRoot_trace_ray(rootptr,q0,q1,q2,o,dir,func,arg1,arg2);
519 +           if(id == QT_DONE)
520 +             return(*arg1);
521 +           if(id == INVALID)
522 +             return(INVALID);
523 +          
524 +         }
525 +     }    /* Point not found */
526 +    return(INVALID);
527 + }
528 +
529 +
530 +
531 + stVisit_tri_interior(st,t0,t1,t2,func,arg1,arg2)
532 +   STREE *st;
533 +   FVECT t0,t1,t2;
534 +   int (*func)();
535 +   int *arg1,arg2;
536 + {
537 +  int i;
538 +  QUADTREE *rootptr;
539 +  FVECT q0,q1,q2;
540 +
541 +  for(i=0; i < 4; i++)
542 +  {
543 +    rootptr = ST_NTH_ROOT_PTR(st,i);
544 +    stNth_base_verts(st,i,q0,q1,q2);
545 +    qtVisit_tri_interior(rootptr,q0,q1,q2,t0,t1,t2,0,func,arg1,arg2);
546 +  }
547 + }
548 +
549 +
550 + int
551 + stApply_to_tri(st,t0,t1,t2,func,arg1,arg2)
552 +   STREE *st;
553 +   FVECT t0,t1,t2;
554 +   int (*func)();
555 +   int *arg1,arg2;
556 + {
557 +    int f;
558 +    FVECT dir;
559 +    
560    /* First add all of the leaf cells lying on the triangle perimeter:
561       mark all cells seen on the way
562     */
563 <  /* clear all of the flags */
564 <  qtClearAllFlags();            /* clear all quadtree branch flags */
563 >    qtClearAllFlags();          /* clear all quadtree branch flags */
564 >    f = 0;
565 >    VSUB(dir,t1,t0);
566 >    stTrace_edge(st,t0,dir,1.0,func,arg1,arg2);
567 >    VSUB(dir,t2,t1);
568 >    stTrace_edge(st,t1,dir,1.0,func,arg1,arg2);
569 >    VSUB(dir,t0,t2);
570 >    stTrace_edge(st,t2,dir,1.0,func,arg1,arg2);
571 >    /* Now visit interior */
572 >    stVisit_tri_interior(st,t0,t1,t2,func,arg1,arg2);
573 > }
574  
575 <  /* Now trace each triangle edge-marking cells visited, and adding tri to
576 <     the leafs
575 >
576 >
577 >
578 >
579 > int
580 > stUpdate_tri(st,t_id,t0,t1,t2,edge_func,interior_func)
581 >   STREE *st;
582 >   int t_id;
583 >   FVECT t0,t1,t2;
584 >   int (*edge_func)(),(*interior_func)();
585 > {
586 >    int f;
587 >    FVECT dir;
588 >    
589 >  /* First add all of the leaf cells lying on the triangle perimeter:
590 >     mark all cells seen on the way
591     */
592 <  stAdd_tri_from_pt(st,v0,id,t0,t1,t2);
593 <  /* Find next cell that projection of ray intersects */
594 <  VCOPY(pt,v0);
295 <  /* NOTE: Check if in same cell */
296 <  while(traceEdge(pt,v1,t0,t1,t2,pt))
297 <  {
298 <      stAdd_tri_from_pt(st,pt,id,t0,t1,t2);
299 <      traceEdge(pt,v1,t0,t1,t2,pt);
300 <  }
301 <  while(traceEdge(pt,v2,t0,t1,t2,pt))
302 <  {
303 <      stAdd_tri_from_pt(st,pt,id,t0,t1,t2);
304 <      traceEdge(pt,v2,t0,t1,t2,pt);
305 <  }
306 <  while(traceEdge(pt,v0,t0,t1,t2,pt))
307 <  {
308 <      stAdd_tri_from_pt(st,pt,id,t0,t1,t2);
309 <      traceEdge(pt,v2,t0,t1,t2,pt);
310 <  }
592 >    ST_CLEAR_FLAGS(st);
593 >    f = 0;
594 >    /* Visit cells along edges of the tri */
595  
596 <  /* NOTE: Optimization: if <= 2 cells added: dont need to fill */
597 <  /* Traverse: follow nodes with flag set or one vertex in triangle */
598 <  
596 >    stVisit_tri_edges2(st,t0,t1,t2,edge_func,&f,t_id);
597 >
598 >    /* Now visit interior */
599 >    if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f))
600 >       stVisit_tri_interior(st,t0,t1,t2,interior_func,&f,t_id);
601   }
602  
603 < #endif
603 >
604 >
605 >

Diff Legend

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