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.5 by gwlarson, Wed Sep 16 18:16:29 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,p0,p1,p2,NULL,NULL,NULL,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,arg3)
232 +   STREE *st;
233 +   FVECT t0,t1,t2;
234 +   int (*func)();
235 +   int *arg1,arg2,*arg3;
236 + {
237 +    int id,i,w;
238 +    QUADTREE *rootptr;
239 +    FVECT q0,q1,q2,v[3],i_pt;
240  
241 +    VCOPY(v[0],t0); VCOPY(v[1],t1); VCOPY(v[2],t2);
242 +    w = -1;
243 +    QT_SET_FLAG(ST_ROOT(st));
244 +    for(i=0; i < 4; i++)
245 +     {
246 + #ifdef TEST_DRIVER
247 + Pick_cnt = 0;
248 + #endif
249 +         rootptr = ST_NTH_ROOT_PTR(st,i);
250 +         stNth_base_verts(st,i,q0,q1,q2);
251 +         /* Return quadtree tri that p falls in */
252 +         if(!point_in_stri(q0,q1,q2,v[0]))  
253 +           continue;
254 + #ifdef TEST_DRIVER
255 +         id = qtRoot_visit_tri_edges(rootptr,q0,q1,q2,v,i_pt,&w,
256 +                                      func,arg1,arg2,arg3);
257 + #else
258 +         id = qtRoot_visit_tri_edgesi(rootptr,q0,q1,q2,v,i_pt,&w,
259 +                                      func,arg1,arg2,arg3);
260 + #endif
261 +         if(id == INVALID)
262 +         {
263 + #ifdef DEBUG
264 +           eputs("stVisit_tri_edges(): Unable to trace edges\n");
265 + #endif
266 +           return(INVALID);
267 +         }
268 +         if(id == QT_DONE)
269 +            return(*arg1);
270 +        
271 +         /* Crossed over to next cell: id = nbr */
272 +         while(1)
273 +         {
274 +             /* test if ray crosses plane between this quadtree triangle and
275 +                its neighbor- if it does then find intersection point with
276 +                ray and plane- this is the new origin
277 +                */
278 +           i = stTri_nbrs[i][id];
279 +           rootptr = ST_NTH_ROOT_PTR(st,i);
280 +           stNth_base_verts(st,i,q0,q1,q2);
281 + #ifdef TEST_DRIVER
282 +           id=qtRoot_visit_tri_edges(rootptr,q0,q1,q2,v,i_pt,&w,
283 +                                      func,arg1,arg2,arg3);
284 + #else
285 +           id=qtRoot_visit_tri_edgesi(rootptr,q0,q1,q2,v,i_pt,&w,
286 +                                      func,arg1,arg2,arg3);
287 + #endif
288 +           if(id == QT_DONE)
289 +             return(*arg1);
290 +           if(id == INVALID)
291 +             {
292 + #ifdef DEBUG
293 +             eputs("stVisit_tri_edges(): point not found\n");
294 + #endif  
295 +             return(INVALID);
296 +             }
297 +          
298 +         }
299 +     }    /* Point not found */
300 +    return(INVALID);
301 + }
302  
303 + int
304 + stTrace_ray(st,orig,dir,func,arg1,arg2)
305 +   STREE *st;
306 +   FVECT orig,dir;
307 +   int (*func)();
308 +   int *arg1,arg2;
309 + {
310 +    int id,i;
311 +    QUADTREE *rootptr;
312 +    FVECT q0,q1,q2,o,n;
313 +    double pd,t;
314  
315 +    VCOPY(o,orig);
316 +    for(i=0; i < 4; i++)
317 +     {
318 + #ifdef TEST_DRIVER
319 + Pick_cnt = 0;
320 + #endif
321 +         rootptr = ST_NTH_ROOT_PTR(st,i);
322 +         stNth_base_verts(st,i,q0,q1,q2);
323 +         /* Return quadtree tri that p falls in */
324 +         id= qtRoot_trace_ray(rootptr,q0,q1,q2,o,dir,func,arg1,arg2);
325 +         if(id == INVALID)
326 +           continue;
327 +         if(id == QT_DONE)
328 +            return(*arg1);
329 +        
330 +         /* Crossed over to next cell: id = nbr */
331 +         while(1)
332 +         {
333 +             /* test if ray crosses plane between this quadtree triangle and
334 +                its neighbor- if it does then find intersection point with
335 +                ray and plane- this is the new origin
336 +                */
337 +           if(id==0)
338 +             VCROSS(n,q1,q2);
339 +           else
340 +             if(id==1)
341 +               VCROSS(n,q2,q0);
342 +           else
343 +             VCROSS(n,q0,q1);
344  
345 < #if 0
346 < int
347 < stAdd_tri_opt(st,id,v0,v1,v2)
348 < STREE *st;
349 < int id;
350 < FVECT v0,v1,v2;
345 >           /* Ray does not cross into next cell: done and tri not found*/
346 >           if(!intersect_ray_plane(orig,dir,n,0.0,NULL,o))
347 >             return(INVALID);
348 >
349 >           VSUM(o,o,dir,10*FTINY);
350 >           i = stTri_nbrs[i][id];
351 >           rootptr = ST_NTH_ROOT_PTR(st,i);
352 >           stNth_base_verts(st,i,q0,q1,q2);
353 >           id = qtRoot_trace_ray(rootptr,q0,q1,q2,o,dir,func,arg1,arg2);
354 >           if(id == QT_DONE)
355 >             return(*arg1);
356 >           if(id == INVALID)
357 >             return(INVALID);
358 >          
359 >         }
360 >     }    /* Point not found */
361 >    return(INVALID);
362 > }
363 >
364 >
365 >
366 > stVisit_tri_interior(st,t0,t1,t2,func,arg1,arg2,arg3)
367 >   STREE *st;
368 >   FVECT t0,t1,t2;
369 >   int (*func)();
370 >   int *arg1,arg2,*arg3;
371   {
372 <  
373 <  int i,found;
374 <  QUADTREE *qtptr;
281 <  FVECT pt,t0,t1,t2;
372 >  int i;
373 >  QUADTREE *rootptr;
374 >  FVECT q0,q1,q2;
375  
376 +  for(i=0; i < 4; i++)
377 +  {
378 +    rootptr = ST_NTH_ROOT_PTR(st,i);
379 +    stNth_base_verts(st,i,q0,q1,q2);
380 +    qtVisit_tri_interior(rootptr,q0,q1,q2,t0,t1,t2,0,func,arg1,arg2,arg3);
381 +  }
382 + }
383 +
384 +
385 + int
386 + stApply_to_tri(st,t0,t1,t2,edge_func,interior_func,arg1,arg2)
387 +   STREE *st;
388 +   FVECT t0,t1,t2;
389 +   int (*edge_func)(),(*interior_func)();
390 +   int arg1,*arg2;
391 + {
392 +    int f;
393 +    FVECT dir;
394 +    
395    /* First add all of the leaf cells lying on the triangle perimeter:
396       mark all cells seen on the way
397     */
398 <  /* clear all of the flags */
399 <  qtClearAllFlags();            /* clear all quadtree branch flags */
398 >    f = 0;
399 >    /* Visit cells along edges of the tri */
400  
401 <  /* Now trace each triangle edge-marking cells visited, and adding tri to
290 <     the leafs
291 <   */
292 <  stAdd_tri_from_pt(st,v0,id,t0,t1,t2);
293 <  /* Find next cell that projection of ray intersects */
294 <  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 <  }
401 >    stVisit_tri_edges(st,t0,t1,t2,edge_func,&f,arg1,arg2);
402  
403 <  /* NOTE: Optimization: if <= 2 cells added: dont need to fill */
404 <  /* Traverse: follow nodes with flag set or one vertex in triangle */
405 <  
403 >    /* Now visit interior */
404 >    if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f))
405 >       stVisit_tri_interior(st,t0,t1,t2,interior_func,&f,arg1,arg2);
406   }
407  
408 < #endif
408 >
409 >
410 >
411 >

Diff Legend

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