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.4 by gwlarson, Fri Sep 11 11:52:27 1998 UTC vs.
Revision 3.6 by gwlarson, Tue Oct 6 18:18:54 1998 UTC

# Line 6 | Line 6 | static char SCCSid[] = "$SunId$ SGI";
6  
7   /*
8   * sm_stree.c
9 + *  An stree (spherical quadtree) is defined by an octahedron in
10 + *  canonical form,and a world center point. Each face of the
11 + *  octahedron is adaptively subdivided as a planar triangular quadtree.
12 + *  World space geometry is projected onto the quadtree faces from the
13 + *  sphere center.
14   */
15   #include "standard.h"
16 + #include "sm_flag.h"
17   #include "sm_geom.h"
18 + #include "sm_qtree.h"
19   #include "sm_stree.h"
20  
14 – /* Define 4 vertices on the sphere to create a tetrahedralization on
15 –   the sphere: triangles are as follows:
16 –        (2,1,0),(3,2,0), (1,3,0), (2,3,1)
17 – */
18 –
21   #ifdef TEST_DRIVER
22   extern FVECT Pick_point[500],Pick_v0[500],Pick_v1[500],Pick_v2[500];
23   extern int Pick_cnt;
24   #endif
25 < FVECT stDefault_base[4] = { {SQRT3_INV, SQRT3_INV, SQRT3_INV},
26 <                          {-SQRT3_INV, -SQRT3_INV, SQRT3_INV},
27 <                          {-SQRT3_INV, SQRT3_INV, -SQRT3_INV},
28 <                          {SQRT3_INV, -SQRT3_INV, -SQRT3_INV}};
29 < int stTri_verts[4][3] = { {2,1,0},{3,2,0},{1,3,0},{2,3,1}};
30 < int stTri_nbrs[4][3] =  { {2,1,3},{0,2,3},{1,0,3},{2,0,1}};
25 > /* octahedron coordinates */
26 > FVECT stDefault_base[6] = {  {1.,0.,0.},{0.,1.,0.}, {0.,0.,1.},
27 >                            {-1.,0.,0.},{0.,-1.,0.},{0.,0.,-1.}};
28 > /* octahedron triangle vertices */
29 > int stBase_verts[8][3] = { {0,1,2},{0,5,1},{3,1,5},{3,2,1},
30 >                          {0,2,4},{5,0,4},{5,4,3},{2,3,4}};
31 > /* octahedron triangle nbrs ; nbr i is the face opposite vertex i*/
32 > int stBase_nbrs[8][3] =  { {3,4,1},{2,0,5},{1,6,3},{0,2,7},
33 >                          {7,5,0},{4,6,1},{7,2,5},{6,4,3}};
34 > /* look up table for octahedron point location */
35 > int stlocatetbl[8] = {6,7,2,3,5,4,1,0};
36  
37 < stNth_base_verts(st,i,v1,v2,v3)
37 >
38 > /* Initializes an stree structure with origin 'center':
39 >   Frees existing quadtrees hanging off of the roots
40 > */
41 > stInit(st)
42   STREE *st;
32 – int i;
33 – FVECT v1,v2,v3;
43   {
44 <  VCOPY(v1,ST_NTH_BASE(st,stTri_verts[i][0]));
45 <  VCOPY(v2,ST_NTH_BASE(st,stTri_verts[i][1]));
46 <  VCOPY(v3,ST_NTH_BASE(st,stTri_verts[i][2]));
44 >    ST_TOP_ROOT(st) = qtAlloc();
45 >    ST_BOTTOM_ROOT(st) = qtAlloc();
46 >    ST_INIT_ROOT(st);
47   }
48  
49 < /* Frees the 4 quadtrees rooted at st */
49 > /* Frees the children of the 2 quadtrees rooted at st,
50 >   Does not free root nodes: just clears
51 > */
52   stClear(st)
53 < STREE *st;
53 >   STREE *st;
54   {
55 <  int i;
56 <
46 <  /* stree always has 4 children corresponding to the base tris
47 <  */
48 <  for (i = 0; i < 4; i++)
49 <    qtFree(ST_NTH_ROOT(st, i));
50 <
51 <  QT_CLEAR_CHILDREN(ST_ROOT(st));
52 <
55 >    qtDone();
56 >    stInit(st);
57   }
58  
59 <
59 > /* Allocates a stree structure  and creates octahedron base */
60   STREE
57 – *stInit(st,center,base)
58 – STREE *st;
59 – FVECT  center,base[4];
60 – {
61 –
62 –  if(base)
63 –    ST_SET_BASE(st,base);
64 –  else
65 –    ST_SET_BASE(st,stDefault_base);
66 –
67 –  ST_SET_CENTER(st,center);
68 –  stClear(st);
69 –
70 –  return(st);
71 – }
72 –
73 –
74 – /* "base" defines 4 vertices on the sphere to create a tetrahedralization on
75 –     the sphere: triangles are as follows:(0,1,2),(0,2,3), (0,3,1), (1,3,2)
76 –     if base is null: does default.
77 –
78 – */
79 – STREE
61   *stAlloc(st)
62   STREE *st;
63   {
64 <  int i;
65 <
64 >  int i,m;
65 >  FVECT v0,v1,v2;
66 >  FVECT n;
67 >  
68    if(!st)
69 <    st = (STREE *)malloc(sizeof(STREE));
69 >    if(!(st = (STREE *)malloc(sizeof(STREE))))
70 >       error(SYSTEM,"stAlloc(): Unable to allocate memory\n");
71  
72 <  ST_ROOT(st) = qtAlloc();
73 <    
74 <  QT_CLEAR_CHILDREN(ST_ROOT(st));
72 >  /* Allocate the top and bottom quadtree root nodes */
73 >  stInit(st);
74 >  
75 >  /* Set the octahedron base */
76 >  ST_SET_BASE(st,stDefault_base);
77  
78 +  /* Calculate octahedron face and edge normals */
79 +  for(i=0; i < ST_NUM_ROOT_NODES; i++)
80 +  {
81 +      VCOPY(v0,ST_NTH_V(st,i,0));
82 +      VCOPY(v1,ST_NTH_V(st,i,1));
83 +      VCOPY(v2,ST_NTH_V(st,i,2));
84 +      tri_plane_equation(v0,v1,v2, &ST_NTH_PLANE(st,i),FALSE);
85 +      m = max_index(FP_N(ST_NTH_PLANE(st,i)),NULL);
86 +      FP_X(ST_NTH_PLANE(st,i)) = (m+1)%3;
87 +      FP_Y(ST_NTH_PLANE(st,i)) = (m+2)%3;
88 +      FP_Z(ST_NTH_PLANE(st,i)) = m;
89 +      VCROSS(ST_EDGE_NORM(st,i,0),v1,v0);
90 +      VCROSS(ST_EDGE_NORM(st,i,1),v2,v1);
91 +      VCROSS(ST_EDGE_NORM(st,i,2),v0,v2);
92 +  }
93    return(st);
94   }
95  
96  
97 < /* Find location of sample point in the DAG and return lowest level
97 <   containing triangle. "type" indicates whether the point was found
98 <   to be in interior to the triangle: GT_FACE, on one of its
99 <   edges GT_EDGE or coinciding with one of its vertices GT_VERTEX.
100 <   "which" specifies which vertex (0,1,2) or edge (0=v0v1, 1 = v1v2, 2 = v21)
101 < */
102 < int
103 < stPoint_locate(st,npt)
104 <    STREE *st;
105 <    FVECT npt;
106 < {
107 <    int i,d,j,id;
108 <    QUADTREE *rootptr,*qtptr;
109 <    FVECT v1,v2,v3;
110 <    OBJECT os[QT_MAXSET+1],*optr;
111 <    FVECT p0,p1,p2;
112 <
113 <    /* Test each of the root triangles against point id */
114 <    for(i=0; i < 4; i++)
115 <     {
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 <         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 <         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_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 <               return(id);
132 <         }
133 <     }
134 <    return(EMPTY);
135 < }
136 <
97 > /* Return quadtree leaf node containing point 'p'*/
98   QUADTREE
99 < *stPoint_locate_cell(st,p,t0,t1,t2)
99 > stPoint_locate(st,p)
100      STREE *st;
101      FVECT p;
141 –    FVECT t0,t1,t2;
102   {
103 <    int i,d;
104 <    QUADTREE *rootptr,*qtptr;
145 <    FVECT v0,v1,v2;
103 >    int i;
104 >    QUADTREE root,qt;
105  
106 +    /* Find root quadtree that contains p */
107 +    i = stPoint_in_root(p);
108 +    root = ST_NTH_ROOT(st,i);
109      
110 <    /* Test each of the root triangles against point id */
111 <    for(i=0; i < 4; i++)
112 <     {
113 <         rootptr = ST_NTH_ROOT_PTR(st,i);
152 <         stNth_base_verts(st,i,v0,v1,v2);
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 <    return(NULL);
110 >    /* Traverse quadtree to leaf level */
111 >    qt = qtRoot_point_locate(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
112 >                        ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),p);
113 >    return(qt);
114   }
115  
116 + /* Add triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
117 +   FALSE on error, TRUE otherwise
118 + */
119  
120 < int
163 < stAdd_tri(st,id,v0,v1,v2)
120 > stAdd_tri(st,id,t0,t1,t2)
121   STREE *st;
122   int id;
123 < FVECT v0,v1,v2;
123 > FVECT t0,t1,t2;
124   {
125 <  
126 <  int i,found;
170 <  QUADTREE *rootptr;
171 <  FVECT t0,t1,t2;
125 >  int i;
126 >  QUADTREE root;
127  
128 <  found = 0;
174 <  for(i=0; i < 4; i++)
128 >  for(i=0; i < ST_NUM_ROOT_NODES; i++)
129    {
130 <    rootptr = ST_NTH_ROOT_PTR(st,i);
131 <    stNth_base_verts(st,i,t0,t1,t2);
132 <    found |= qtRoot_add_tri(rootptr,t0,t1,t2,v0,v1,v2,id,0);
130 >    root = ST_NTH_ROOT(st,i);
131 >    ST_NTH_ROOT(st,i) = qtRoot_add_tri(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
132 >                            ST_NTH_V(st,i,2),t0,t1,t2,id,0);
133    }
180 –  return(found);
134   }
135  
136 < int
137 < stApply_to_tri_cells(st,v0,v1,v2,func,arg)
138 < STREE *st;
186 < FVECT v0,v1,v2;
187 < int (*func)();
188 < int *arg;
189 < {
190 <  int i,found;
191 <  QUADTREE *rootptr;
192 <  FVECT t0,t1,t2;
136 > /* Remove triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
137 >   FALSE on error, TRUE otherwise
138 > */
139  
140 <  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);
200 <    stNth_base_verts(st,i,t0,t1,t2);
201 <    found |= qtApply_to_tri_cells(rootptr,v0,v1,v2,t0,t1,t2,func,arg);
202 <  }
203 <  return(found);
204 < }
205 <
206 <
207 <
208 <
209 < int
210 < stRemove_tri(st,id,v0,v1,v2)
140 > stRemove_tri(st,id,t0,t1,t2)
141   STREE *st;
142   int id;
143 < FVECT v0,v1,v2;
143 > FVECT t0,t1,t2;
144   {
145 <  
146 <  int i,found;
217 <  QUADTREE *rootptr;
218 <  FVECT t0,t1,t2;
145 >  int i;
146 >  QUADTREE root;
147  
148 <  found = 0;
221 <  for(i=0; i < 4; i++)
148 >  for(i=0; i < ST_NUM_ROOT_NODES; i++)
149    {
150 <    rootptr = ST_NTH_ROOT_PTR(st,i);
151 <    stNth_base_verts(st,i,t0,t1,t2);
152 <   found |= qtRemove_tri(rootptr,id,v0,v1,v2,t0,t1,t2);
150 >    root = ST_NTH_ROOT(st,i);
151 >    ST_NTH_ROOT(st,i)=qtRoot_remove_tri(root,id,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
152 >                          ST_NTH_V(st,i,2),t0,t1,t2);
153    }
227 –  return(found);
154   }
155  
156 < int
157 < stVisit_tri_edges(st,t0,t1,t2,func,arg1,arg2)
158 <   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;
156 > /* Visit all nodes that are intersected by the edges of triangle 't0,t1,t2'
157 >   and apply 'func'
158 > */
159  
160 <    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 < stVisit_tri_edges2(st,t0,t1,t2,func,arg1,arg2)
160 > stVisit_tri_edges(st,t0,t1,t2,func,fptr,argptr)
161     STREE *st;
162     FVECT t0,t1,t2;
163 <   int (*func)();
164 <   int *arg1,arg2;
163 >   int (*func)(),*fptr;
164 >   int *argptr;
165   {
166 <    int id,i,w;
167 <    QUADTREE *rootptr;
168 <    FVECT q0,q1,q2,v[3],i_pt;
166 >    int id,i,w,next;
167 >    QUADTREE root;
168 >    FVECT v[3],i_pt;
169  
170      VCOPY(v[0],t0); VCOPY(v[1],t1); VCOPY(v[2],t2);
171      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 – }
172  
173 < int
174 < stTrace_edge(st,orig,dir,max_t,func,arg1,arg2)
175 <   STREE *st;
176 <   FVECT orig,dir;
177 <   double max_t;
178 <   int (*func)();
179 <   int *arg1,arg2;
180 < {
181 <    int id,i;
182 <    QUADTREE *rootptr;
183 <    FVECT q0,q1,q2,o,n,d;
184 <    double pd,t;
185 <
186 < #if DEBUG
401 <    if(max_t > 1.0 || max_t < 0.0)
173 >    /* Locate the root containing triangle vertex v0 */
174 >    i = stPoint_in_root(v[0]);
175 >    /* Mark the root node as visited */
176 >    QT_SET_FLAG(ST_ROOT(st,i));
177 >    root = ST_NTH_ROOT(st,i);
178 >    
179 >    ST_NTH_ROOT(st,i) = qtRoot_visit_tri_edges(root,ST_NTH_V(st,i,0),
180 >       ST_NTH_V(st,i,1),ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),v,i_pt,&w,
181 >                                               &next,func,fptr,argptr);
182 >    if(QT_FLAG_IS_DONE(*fptr))
183 >      return;
184 >        
185 >    /* Crossed over to next node: id = nbr */
186 >    while(1)
187      {
188 <      eputs("stTrace_edge(): max_t must be in [0,1]:adjusting\n");
189 <      max_t = 1.0;
188 >        /* test if ray crosses plane between this quadtree triangle and
189 >           its neighbor- if it does then find intersection point with
190 >           ray and plane- this is the new start point
191 >           */
192 >        i = stBase_nbrs[i][next];
193 >        root = ST_NTH_ROOT(st,i);
194 >        ST_NTH_ROOT(st,i) =
195 >          qtRoot_visit_tri_edges(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
196 >         ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),v,i_pt,&w,&next,func,fptr,argptr);
197 >        if(QT_FLAG_IS_DONE(*fptr))
198 >          return;
199      }
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);
200   }
201  
202 <
203 <
202 > /* Trace ray 'orig-dir' through stree and apply 'func(qtptr,f,argptr)' at each
203 >   node that it intersects
204 > */
205   int
206 < stTrace_ray(st,orig,dir,func,arg1,arg2)
206 > stTrace_ray(st,orig,dir,func,argptr)
207     STREE *st;
208     FVECT orig,dir;
209     int (*func)();
210 <   int *arg1,arg2;
210 >   int *argptr;
211   {
212 <    int id,i;
213 <    QUADTREE *rootptr;
214 <    FVECT q0,q1,q2,o,n;
212 >    int next,last,i,f=0;
213 >    QUADTREE root;
214 >    FVECT o,n;
215      double pd,t;
216  
217      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);
218  
219 +    /* Find the root node that o falls in */
220 +    i = stPoint_in_root(o);
221 +    root = ST_NTH_ROOT(st,i);
222 +    
223 +    ST_NTH_ROOT(st,i) =
224 +      qtRoot_trace_ray(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
225 +          ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),o,dir,&next,func,&f,argptr);
226 +
227 +    if(QT_FLAG_IS_DONE(f))
228 +      return(TRUE);
229 +        
230 +    /* Crossed over to next cell: id = nbr */
231 +    while(1)
232 +      {
233 +        /* test if ray crosses plane between this quadtree triangle and
234 +           its neighbor- if it does then find intersection point with
235 +           ray and plane- this is the new origin
236 +           */
237 +        if(next == INVALID)
238 +          return(FALSE);
239 +        if(!intersect_ray_oplane(orig,dir,
240 +                                 ST_EDGE_NORM(st,i,(next+1)%3),NULL,o))
241             /* Ray does not cross into next cell: done and tri not found*/
242 <           if(!intersect_ray_plane(orig,dir,n,0.0,NULL,o))
512 <             return(INVALID);
242 >           return(FALSE);
243  
244 <           VSUM(o,o,dir,10*FTINY);
245 <           i = stTri_nbrs[i][id];
246 <           rootptr = ST_NTH_ROOT_PTR(st,i);
247 <           stNth_base_verts(st,i,q0,q1,q2);
248 <           id = qtRoot_trace_ray(rootptr,q0,q1,q2,o,dir,func,arg1,arg2);
249 <           if(id == QT_DONE)
250 <             return(*arg1);
251 <           if(id == INVALID)
252 <             return(INVALID);
253 <          
524 <         }
525 <     }    /* Point not found */
526 <    return(INVALID);
244 >        VSUM(o,o,dir,10*FTINY);
245 >        i = stBase_nbrs[i][next];
246 >        root = ST_NTH_ROOT(st,i);
247 >        
248 >        ST_NTH_ROOT(st,i) =
249 >          qtRoot_trace_ray(root, ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
250 >               ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),o,dir,&next,func,&f,argptr);
251 >        if(QT_FLAG_IS_DONE(f))
252 >          return(TRUE);
253 >      }
254   }
255  
256  
257 <
258 < stVisit_tri_interior(st,t0,t1,t2,func,arg1,arg2)
257 > /* Visit nodes intersected by tri 't0,t1,t2' and apply 'func(arg1,arg2,arg3):
258 >   assumes that stVisit_tri_edges has already been called such that all nodes
259 >   intersected by tri edges are already marked as visited
260 > */
261 > stVisit_tri(st,t0,t1,t2,func,f,argptr)
262     STREE *st;
263     FVECT t0,t1,t2;
264 <   int (*func)();
265 <   int *arg1,arg2;
264 >   int (*func)(),*f;
265 >   int *argptr;
266   {
267    int i;
268 <  QUADTREE *rootptr;
269 <  FVECT q0,q1,q2;
268 >  QUADTREE root;
269 >  FVECT n0,n1,n2;
270  
271 <  for(i=0; i < 4; i++)
271 >  /* Calcuate the edge normals for tri */
272 >  VCROSS(n0,t1,t0);
273 >  VCROSS(n1,t2,t1);
274 >  VCROSS(n2,t0,t2);
275 >
276 >  for(i=0; i < ST_NUM_ROOT_NODES; i++)
277    {
278 <    rootptr = ST_NTH_ROOT_PTR(st,i);
279 <    stNth_base_verts(st,i,q0,q1,q2);
280 <    qtVisit_tri_interior(rootptr,q0,q1,q2,t0,t1,t2,0,func,arg1,arg2);
278 >    root = ST_NTH_ROOT(st,i);
279 >    ST_NTH_ROOT(st,i) = qtVisit_tri_interior(root,ST_NTH_V(st,i,0),
280 >        ST_NTH_V(st,i,1),ST_NTH_V(st,i,2),t0,t1,t2,n0,n1,n2,0,func,f,argptr);
281 >
282    }
283   }
284  
285 <
285 > /* Visit nodes intersected by tri 't0,t1,t2'.Apply 'edge_func(arg1,arg2,arg3)',
286 >   to those nodes intersected by edges, and interior_func to ALL nodes:
287 >   ie some Nodes  will be visited more than once
288 > */
289   int
290 < stApply_to_tri(st,t0,t1,t2,func,arg1,arg2)
290 > stApply_to_tri(st,t0,t1,t2,edge_func,tri_func,argptr)
291     STREE *st;
292     FVECT t0,t1,t2;
293 <   int (*func)();
294 <   int *arg1,arg2;
293 >   int (*edge_func)(),(*tri_func)();
294 >   int *argptr;
295   {
296      int f;
297      FVECT dir;
# Line 560 | Line 299 | stApply_to_tri(st,t0,t1,t2,func,arg1,arg2)
299    /* First add all of the leaf cells lying on the triangle perimeter:
300       mark all cells seen on the way
301     */
563 –    qtClearAllFlags();          /* clear all quadtree branch flags */
302      f = 0;
303 <    VSUB(dir,t1,t0);
304 <    stTrace_edge(st,t0,dir,1.0,func,arg1,arg2);
305 <    VSUB(dir,t2,t1);
306 <    stTrace_edge(st,t1,dir,1.0,func,arg1,arg2);
307 <    VSUB(dir,t0,t2);
308 <    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);
303 >    /* Visit cells along edges of the tri */
304 >    stVisit_tri_edges(st,t0,t1,t2,edge_func,&f,argptr);
305 >
306 >    /* Now visit All cells interior */
307 >    if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f))
308 >       stVisit_tri(st,t0,t1,t2,tri_func,&f,argptr);
309   }
310  
311  
312  
313  
314  
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 –    ST_CLEAR_FLAGS(st);
593 –    f = 0;
594 –    /* Visit cells along edges of the tri */
595 –
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 – }
315  
316  
317  

Diff Legend

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