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.2 by gwlarson, Thu Aug 20 16:47:22 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,qt;
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 119 | Line 116 | stPoint_locate(st,npt,type,which)
116           rootptr = ST_NTH_ROOT_PTR(st,i);
117           stNth_base_verts(st,i,v1,v2,v3);
118           /* Return tri that p falls in */
119 <         qt = qtRoot_point_locate(rootptr,v1,v2,v3,npt,type,which);
120 <         if(QT_IS_EMPTY(qt))
119 >         qtptr = qtRoot_point_locate(rootptr,v1,v2,v3,npt,NULL,NULL,NULL);
120 >         if(!qtptr || QT_IS_EMPTY(*qtptr))
121              continue;
122           /* Get the set */
123 <         qtgetset(os,qt);
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  
137 < int
138 < stPoint_locate_cell(st,p,type,which)
137 > QUADTREE
138 > *stPoint_locate_cell(st,p,t0,t1,t2)
139      STREE *st;
140      FVECT p;
141 <    char *type,*which;
141 >    FVECT t0,t1,t2;
142   {
143      int i,d;
144 <    QUADTREE *rootptr,qt;
144 >    QUADTREE *rootptr,*qtptr;
145      FVECT v0,v1,v2;
146  
147      
# Line 163 | Line 150 | stPoint_locate_cell(st,p,type,which)
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 */
154 <         qt = qtRoot_point_locate(rootptr,v0,v1,v2,p,type,which);
155 <         /* NOTE: For now return only one triangle */
156 <         if(!QT_IS_EMPTY(qt))
170 <            return(qt);
153 >         /* Return quadtree tri that p falls in */
154 >         qtptr = qtRoot_point_locate(rootptr,v0,v1,v2,p,t0,t1,t2);
155 >         if(qtptr)
156 >            return(qtptr);
157       }    /* Point not found */
158 <    if(which)
173 <      *which = 0;
174 <    if(type)
175 <      *type = 0;
176 <    return(EMPTY);
158 >    return(NULL);
159   }
160  
161 +
162   int
163   stAdd_tri(st,id,v0,v1,v2)
164   STREE *st;
# Line 192 | 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 |= qtAdd_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 202 | 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 240 | Line 225 | FVECT v0,v1,v2;
225     found |= qtRemove_tri(rootptr,id,v0,v1,v2,t0,t1,t2);
226    }
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 +           /* 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 +  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 +    f = 0;
399 +    /* Visit cells along edges of the tri */
400 +
401 +    stVisit_tri_edges(st,t0,t1,t2,edge_func,&f,arg1,arg2);
402 +
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  

Diff Legend

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