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.6 by gwlarson, Tue Oct 6 18:18:54 1998 UTC vs.
Revision 3.13 by greg, Sat Feb 22 02:07:25 2003 UTC

# Line 1 | Line 1
1 – /* Copyright (c) 1998 Silicon Graphics, Inc. */
2 –
1   #ifndef lint
2 < static char SCCSid[] = "$SunId$ SGI";
2 > static const char       RCSid[] = "$Id$";
3   #endif
6 –
4   /*
5   * sm_stree.c
6   *  An stree (spherical quadtree) is defined by an octahedron in
# Line 13 | Line 10 | static char SCCSid[] = "$SunId$ SGI";
10   *  sphere center.
11   */
12   #include "standard.h"
13 + #include "sm_list.h"
14   #include "sm_flag.h"
15   #include "sm_geom.h"
16 + #include "object.h"
17   #include "sm_qtree.h"
18   #include "sm_stree.h"
19  
20 +
21   #ifdef TEST_DRIVER
22   extern FVECT Pick_point[500],Pick_v0[500],Pick_v1[500],Pick_v2[500];
23   extern int Pick_cnt;
# Line 26 | Line 26 | extern int Pick_cnt;
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}};
29 > int stBase_verts[8][3] = { {0,1,2},{3,1,2},{0,4,2},{3,4,2},
30 >                           {0,1,5},{3,1,5},{0,4,5},{3,4,5}};
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};
32 > int stBase_nbrs[8][3] =  { {1,2,4},{0,3,5},{3,0,6},{2,1,7},
33 >                           {5,6,0},{4,7,1},{7,4,2},{6,5,3}};
34 > int stRoot_indices[8][3] = {{1,1,1},{-1,1,1},{1,-1,1},{-1,-1,1},
35 >                            {1,1,-1},{-1,1,-1},{1,-1,-1},{-1,-1,-1}};
36 > /*
37 > +z   y                -z   y
38 >      |                     |
39 > 1    |   0             5   |   4
40 > ______|______ x      _______|______ x
41 > 3    |   2             7   |   6  
42 >      |                     |
43  
44 <
45 < /* Initializes an stree structure with origin 'center':
46 <   Frees existing quadtrees hanging off of the roots
44 > Nbrs
45 >  +z   y                -z   y
46 >     /0|1\                 /1|0\
47 > 5  /  |  \ 4             /  |  \
48 >   /(1)|(0)\           1 /(5)|(4)\ 0
49 >  /    |    \           /    |    \
50 > /2   1|0   2\         /2   0|1   2\
51 > /------|------\x      /------|------\x
52 > \0    1|2    0/       \0    2|2    1/
53 > \     |     /         \     |     /
54 > 7\ (3)|(2) / 6       3 \ (7)|(6) / 2
55 >   \   |   /             \   |   /
56 >    \ 2|1 /               \ 1|0 /
57   */
58 +
59 +
60   stInit(st)
61   STREE *st;
62   {
63 <    ST_TOP_ROOT(st) = qtAlloc();
64 <    ST_BOTTOM_ROOT(st) = qtAlloc();
65 <    ST_INIT_ROOT(st);
63 >  int i,j;
64 >
65 >  qtDone();
66 >
67 >  ST_TOP_QT(st) = qtAlloc();
68 >  ST_BOTTOM_QT(st) = qtAlloc();
69 >  /* Clear the children */
70 >
71 >   QT_CLEAR_CHILDREN(ST_TOP_QT(st));
72 >   QT_CLEAR_CHILDREN(ST_BOTTOM_QT(st));
73   }
74  
75 < /* Frees the children of the 2 quadtrees rooted at st,
76 <   Does not free root nodes: just clears
51 < */
52 < stClear(st)
53 <   STREE *st;
75 > stFree(st)
76 > STREE *st;
77   {
78 <    qtDone();
79 <    stInit(st);
78 >  qtDone();
79 >  free(st);
80   }
81  
82   /* Allocates a stree structure  and creates octahedron base */
# Line 72 | Line 95 | STREE *st;
95    /* Allocate the top and bottom quadtree root nodes */
96    stInit(st);
97    
98 <  /* Set the octahedron base */
99 <  ST_SET_BASE(st,stDefault_base);
98 >  return(st);
99 > }
100  
101 <  /* Calculate octahedron face and edge normals */
102 <  for(i=0; i < ST_NUM_ROOT_NODES; i++)
101 > #define BARY_INT(v,b)  if((v)>2.0) (b) = MAXBCOORD;else \
102 >  if((v)<-2.0) (b)=-MAXBCOORD;else (b)=(BCOORD)((v)*MAXBCOORD2);
103 >
104 > vert_to_qt_frame(root,v,b)
105 > int root;
106 > FVECT v;
107 > BCOORD b[3];
108 > {
109 >  int i;
110 >  double scale;
111 >  double d0,d1,d2;
112 >
113 >  if(STR_NTH_INDEX(root,0)==-1)
114 >    d0 = -v[0];
115 >  else
116 >    d0 = v[0];
117 >  if(STR_NTH_INDEX(root,1)==-1)
118 >    d1 = -v[1];
119 >  else
120 >    d1 = v[1];
121 >  if(STR_NTH_INDEX(root,2)==-1)
122 >    d2 = -v[2];
123 >  else
124 >    d2 = v[2];
125 >
126 >  /* Plane is now x+y+z = 1 - intersection of pt ray is qtv/den */
127 >  scale = 1.0/ (d0 + d1 + d2);
128 >  d0 *= scale;
129 >  d1 *= scale;
130 >  d2 *= scale;
131 >
132 >  BARY_INT(d0,b[0])
133 >  BARY_INT(d1,b[1])
134 >  BARY_INT(d2,b[2])
135 > }
136 >
137 >
138 >
139 >
140 > ray_to_qt_frame(root,v,dir,b,db)
141 > int root;
142 > FVECT v,dir;
143 > BCOORD b[3],db[3];
144 > {
145 >  int i;
146 >  double scale;
147 >  double d0,d1,d2;
148 >  double dir0,dir1,dir2;
149 >
150 >  if(STR_NTH_INDEX(root,0)==-1)
151    {
152 <      VCOPY(v0,ST_NTH_V(st,i,0));
153 <      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);
152 >    d0 = -v[0];
153 >    dir0 = -dir[0];
154    }
155 <  return(st);
155 >  else
156 >  {
157 >    d0 = v[0];
158 >    dir0 = dir[0];
159 >  }
160 >  if(STR_NTH_INDEX(root,1)==-1)
161 >  {
162 >    d1 = -v[1];
163 >    dir1 = -dir[1];
164 >  }
165 >  else
166 >  {
167 >    d1 = v[1];
168 >    dir1 = dir[1];
169 >  }
170 >  if(STR_NTH_INDEX(root,2)==-1)
171 >  {
172 >    d2 = -v[2];
173 >    dir2 = -dir[2];
174 >  }
175 >  else
176 >  {
177 >    d2 = v[2];
178 >    dir2 = dir[2];
179 >  }
180 >  /* Plane is now x+y+z = 1 - intersection of pt ray is qtv/den */
181 >  scale = 1.0/ (d0 + d1 + d2);
182 >  d0 *= scale;
183 >  d1 *= scale;
184 >  d2 *= scale;
185 >
186 >  /* Calculate intersection point of orig+dir: This calculation is done
187 >     after the origin is projected into the plane in order to constrain
188 >     the projection( i.e. the size of the projection of the unit direction
189 >     vector translated to the origin depends on how close
190 >     the origin is to the view center
191 >     */
192 >  /* Must divide by at least root2 to insure that projection will fit
193 >     int [-2,2] bounds: assumed length is 1: therefore greatest projection
194 >     from endpoint of triangle is at 45 degrees or projected length of root2
195 >  */
196 >  dir0 = d0 + dir0*0.5;
197 >  dir1 = d1 + dir1*0.5;
198 >  dir2 = d2 + dir2*0.5;
199 >
200 >  scale = 1.0/ (dir0 + dir1 + dir2);
201 >  dir0 *= scale;
202 >  dir1 *= scale;
203 >  dir2 *= scale;
204 >
205 >  BARY_INT(d0,b[0])
206 >  BARY_INT(d1,b[1])
207 >  BARY_INT(d2,b[2])
208 >  BARY_INT(dir0,db[0])
209 >  BARY_INT(dir1,db[1])
210 >  BARY_INT(dir2,db[2])
211 >
212 >  db[0]  -= b[0];
213 >  db[1]  -= b[1];
214 >  db[2]  -= b[2];
215   }
216  
217 + qt_frame_to_vert(root,b,v)
218 + int root;
219 + BCOORD b[3];
220 + FVECT v;
221 + {
222 +  int i;
223 +  double d0,d1,d2;
224  
225 +  d0 = b[0]/(double)MAXBCOORD2;
226 +  d1 = b[1]/(double)MAXBCOORD2;
227 +  d2 = b[2]/(double)MAXBCOORD2;
228 +  
229 +  if(STR_NTH_INDEX(root,0)==-1)
230 +    v[0] = -d0;
231 +  else
232 +    v[0] = d0;
233 +  if(STR_NTH_INDEX(root,1)==-1)
234 +    v[1] = -d1;
235 +  else
236 +    v[1] = d1;
237 +  if(STR_NTH_INDEX(root,2)==-1)
238 +    v[2] = -d2;
239 +  else
240 +    v[2] = d2;
241 + }
242 +
243 +
244   /* Return quadtree leaf node containing point 'p'*/
245   QUADTREE
246   stPoint_locate(st,p)
247      STREE *st;
248      FVECT p;
249   {
250 +    QUADTREE qt;
251 +    BCOORD bcoordi[3];
252      int i;
104 –    QUADTREE root,qt;
253  
254      /* Find root quadtree that contains p */
255 <    i = stPoint_in_root(p);
256 <    root = ST_NTH_ROOT(st,i);
255 >    i = stLocate_root(p);
256 >    qt = ST_ROOT_QT(st,i);
257      
258 <    /* Traverse quadtree to leaf level */
259 <    qt = qtRoot_point_locate(root,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
260 <                        ST_NTH_V(st,i,2),ST_NTH_PLANE(st,i),p);
261 <    return(qt);
258 >     /* Will return lowest level triangle containing point: It the
259 >       point is on an edge or vertex: will return first associated
260 >       triangle encountered in the child traversal- the others can
261 >       be derived using triangle adjacency information
262 >    */
263 >    if(QT_IS_TREE(qt))
264 >    {  
265 >      vert_to_qt_frame(i,p,bcoordi);
266 >      i = bary_child(bcoordi);
267 >      return(qtLocate(QT_NTH_CHILD(qt,i),bcoordi));
268 >    }
269 >    else
270 >      return(qt);
271   }
272  
273 < /* Add triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
274 <   FALSE on error, TRUE otherwise
275 < */
276 <
277 < stAdd_tri(st,id,t0,t1,t2)
278 < STREE *st;
122 < int id;
123 < FVECT t0,t1,t2;
273 > static unsigned int nbr_b[8][3] ={{2,4,16},{1,8,32},{8,1,64},{4,2,128},
274 >                           {32,64,1},{16,128,2},{128,16,4},{64,32,8}};
275 > unsigned int
276 > stTri_cells(st,v)
277 >     STREE *st;
278 >     FVECT v[3];
279   {
280 <  int i;
281 <  QUADTREE root;
280 >  unsigned int cells,cross;
281 >  unsigned int vcell[3];
282 >  double t0,t1;
283 >  int i,inext;
284  
285 <  for(i=0; i < ST_NUM_ROOT_NODES; i++)
286 <  {
287 <    root = ST_NTH_ROOT(st,i);
288 <    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 <  }
134 < }
285 >  /* First find base cells that tri vertices are in (0-7)*/
286 >  vcell[0] = stLocate_root(v[0]);
287 >  vcell[1] = stLocate_root(v[1]);
288 >  vcell[2] = stLocate_root(v[2]);
289  
290 < /* Remove triangle 'id' with coordinates 't0,t1,t2' to the stree: returns
291 <   FALSE on error, TRUE otherwise
292 < */
290 >  /* If all in same cell- return that bit only */
291 >  if(vcell[0] == vcell[1] && vcell[1] == vcell[2])
292 >    return( 1 << vcell[0]);
293  
294 < stRemove_tri(st,id,t0,t1,t2)
295 < STREE *st;
142 < int id;
143 < FVECT t0,t1,t2;
144 < {
145 <  int i;
146 <  QUADTREE root;
147 <
148 <  for(i=0; i < ST_NUM_ROOT_NODES; i++)
294 >  cells = 0;
295 >  for(i=0;i<3; i++)
296    {
297 <    root = ST_NTH_ROOT(st,i);
298 <    ST_NTH_ROOT(st,i)=qtRoot_remove_tri(root,id,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),
299 <                          ST_NTH_V(st,i,2),t0,t1,t2);
297 >    if(i==2)
298 >      inext = 0;
299 >    else
300 >      inext = i+1;
301 >    /* Mark cell containing initial vertex */
302 >    cells |= 1 << vcell[i];
303 >
304 >    /* Take the exclusive or: will have bits set where edge crosses axis=0*/
305 >    cross = vcell[i] ^ vcell[inext];
306 >    /* If crosses 2 planes: then have 2 options for edge crossing-pick closest
307 >     otherwise just hits two*/
308 >    /* Neighbors are zyx */
309 >    switch(cross){
310 >    case 3: /* crosses x=0 and y=0 */
311 >      t0 = -v[i][0]/(v[inext][0]-v[i][0]);
312 >      t1 = -v[i][1]/(v[inext][1]-v[i][1]);
313 >      if(t0==t1)
314 >        break;
315 >      else if(t0 < t1)
316 >        cells |= nbr_b[vcell[i]][0];
317 >          else
318 >            cells |= nbr_b[vcell[i]][1];
319 >      break;
320 >    case 5: /* crosses x=0 and z=0 */
321 >      t0 = -v[i][0]/(v[inext][0]-v[i][0]);
322 >      t1 = -v[i][2]/(v[inext][2]-v[i][2]);
323 >      if(t0==t1)
324 >        break;
325 >      else if(t0 < t1)
326 >        cells |= nbr_b[vcell[i]][0];
327 >          else
328 >            cells |=nbr_b[vcell[i]][2];
329 >
330 >      break;
331 >    case 6:/* crosses  z=0 and y=0 */
332 >      t0 = -v[i][2]/(v[inext][2]-v[i][2]);
333 >      t1 = -v[i][1]/(v[inext][1]-v[i][1]);
334 >      if(t0==t1)
335 >        break;
336 >      else if(t0 < t1)
337 >      {
338 >        cells |= nbr_b[vcell[i]][2];
339 >      }
340 >      else
341 >      {
342 >        cells |=nbr_b[vcell[i]][1];
343 >      }
344 >      break;
345 >    case 7:
346 >      error(CONSISTENCY," Insert:Edge shouldnt be able to span 3 cells");
347 >      break;
348 >    }
349    }
350 +  return(cells);
351   }
352  
156 – /* Visit all nodes that are intersected by the edges of triangle 't0,t1,t2'
157 –   and apply 'func'
158 – */
353  
354 < stVisit_tri_edges(st,t0,t1,t2,func,fptr,argptr)
355 <   STREE *st;
356 <   FVECT t0,t1,t2;
357 <   int (*func)(),*fptr;
358 <   int *argptr;
354 > stRoot_trace_ray(qt,root,orig,dir,nextptr,func,f)
355 >   QUADTREE qt;
356 >   int root;
357 >   FVECT orig,dir;
358 >   int *nextptr;
359 >   FUNC func;
360 >   int *f;
361   {
362 <    int id,i,w,next;
363 <    QUADTREE root;
364 <    FVECT v[3],i_pt;
362 >  double br[3];
363 >  BCOORD bi[3],dbi[3];
364 >  
365 >  /* Project the origin onto the root node plane */
366 >  /* Find the intersection point of the origin */
367 >  ray_to_qt_frame(root,orig,dir,bi,dbi);
368  
369 <    VCOPY(v[0],t0); VCOPY(v[1],t1); VCOPY(v[2],t2);
370 <    w = -1;
369 >  /* trace the ray starting with this node */
370 >  qtTrace_ray(qt,bi,dbi[0],dbi[1],dbi[2],nextptr,0,0,func,f);
371 >  if(!QT_FLAG_IS_DONE(*f))
372 >    qt_frame_to_vert(root,bi,orig);
373  
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 –        /* 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 –    }
374   }
375  
376   /* Trace ray 'orig-dir' through stree and apply 'func(qtptr,f,argptr)' at each
377     node that it intersects
378   */
379   int
380 < stTrace_ray(st,orig,dir,func,argptr)
380 > stTrace_ray(st,orig,dir,func)
381     STREE *st;
382     FVECT orig,dir;
383 <   int (*func)();
210 <   int *argptr;
383 >   FUNC func;
384   {
385      int next,last,i,f=0;
386 <    QUADTREE root;
387 <    FVECT o,n;
388 <    double pd,t;
386 >    QUADTREE qt;
387 >    FVECT o,n,v;
388 >    double pd,t,d;
389  
390      VCOPY(o,orig);
391 <
392 <    /* Find the root node that o falls in */
393 <    i = stPoint_in_root(o);
394 <    root = ST_NTH_ROOT(st,i);
391 > #ifdef TEST_DRIVER
392 >       Pick_cnt=0;
393 > #endif;
394 >    /* Find the qt node that o falls in */
395 >    i = stLocate_root(o);
396 >    qt = ST_ROOT_QT(st,i);
397      
398 <    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);
398 >    stRoot_trace_ray(qt,i,o,dir,&next,func,&f);
399  
400      if(QT_FLAG_IS_DONE(f))
401        return(TRUE);
402 <        
402 >    /*
403 >    d = DOT(orig,dir)/sqrt(DOT(orig,orig));
404 >    VSUM(v,orig,dir,-d);
405 >    */
406      /* Crossed over to next cell: id = nbr */
407      while(1)
408        {
# Line 236 | Line 412 | stTrace_ray(st,orig,dir,func,argptr)
412             */
413          if(next == INVALID)
414            return(FALSE);
415 <        if(!intersect_ray_oplane(orig,dir,
416 <                                 ST_EDGE_NORM(st,i,(next+1)%3),NULL,o))
417 <           /* Ray does not cross into next cell: done and tri not found*/
418 <           return(FALSE);
243 <
244 <        VSUM(o,o,dir,10*FTINY);
415 >        /*
416 >        if(DOT(o,v) < 0.0)
417 >          return(FALSE);
418 >          */
419          i = stBase_nbrs[i][next];
420 <        root = ST_NTH_ROOT(st,i);
421 <        
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);
420 >        qt = ST_ROOT_QT(st,i);
421 >        stRoot_trace_ray(qt,i,o,dir,&next,func,&f);
422          if(QT_FLAG_IS_DONE(f))
423            return(TRUE);
424        }
425   }
426  
427  
428 < /* Visit nodes intersected by tri 't0,t1,t2' and apply 'func(arg1,arg2,arg3):
429 <   assumes that stVisit_tri_edges has already been called such that all nodes
430 <   intersected by tri edges are already marked as visited
431 < */
432 < stVisit_tri(st,t0,t1,t2,func,f,argptr)
433 <   STREE *st;
434 <   FVECT t0,t1,t2;
264 <   int (*func)(),*f;
265 <   int *argptr;
428 > stVisit_poly(st,verts,l,root,func,n)
429 > STREE *st;
430 > FVECT *verts;
431 > LIST *l;
432 > unsigned int root;
433 > FUNC func;
434 > int n;
435   {
436 <  int i;
437 <  QUADTREE root;
269 <  FVECT n0,n1,n2;
436 >  int id0,id1,id2;
437 >  FVECT tri[3];
438  
439 <  /* Calcuate the edge normals for tri */
440 <  VCROSS(n0,t1,t0);
441 <  VCROSS(n1,t2,t1);
442 <  VCROSS(n2,t0,t2);
439 >  id0 = pop_list(&l);
440 >  id1 = pop_list(&l);
441 >  while(l)
442 >  {
443 >    id2 = pop_list(&l);
444 >    VCOPY(tri[0],verts[id0]);
445 >    VCOPY(tri[1],verts[id1]);
446 >    VCOPY(tri[2],verts[id2]);
447 >    stRoot_visit_tri(st,root,tri,func,n);
448 >    id1 = id2;
449 >  }
450 > }
451 > /* Assumption: know crosses plane:dont need to check for 'on' case */
452 > intersect_edge_coord_plane(v0,v1,w,r)
453 > FVECT v0,v1;
454 > int w;
455 > FVECT r;
456 > {
457 >  FVECT dv;
458 >  int wnext;
459 >  double t;
460  
461 <  for(i=0; i < ST_NUM_ROOT_NODES; i++)
461 >  VSUB(dv,v1,v0);
462 >  t = -v0[w]/dv[w];
463 >  r[w] = 0.0;
464 >  wnext = (w+1)%3;
465 >  r[wnext] = v0[wnext] + dv[wnext]*t;
466 >  wnext = (w+2)%3;
467 >  r[wnext] = v0[wnext] + dv[wnext]*t;
468 > }
469 >
470 >
471 > stVisit_clip(st,i,verts,vcnt,l,cell,func,n)
472 >     STREE *st;
473 >     int i;
474 >     FVECT *verts;
475 >     int *vcnt;
476 >     LIST *l;
477 >     unsigned int cell;
478 >     FUNC func;
479 >     int n;
480 > {
481 >
482 >  LIST *labove,*lbelow,*endb,*enda;
483 >  int last = -1;
484 >  int id,last_id;
485 >  int first,first_id;
486 >  unsigned int cellb;
487 >
488 >  labove = lbelow = NULL;
489 >  enda = endb = NULL;
490 >  while(l)
491    {
492 <    root = ST_NTH_ROOT(st,i);
493 <    ST_NTH_ROOT(st,i) = qtVisit_tri_interior(root,ST_NTH_V(st,i,0),
494 <        ST_NTH_V(st,i,1),ST_NTH_V(st,i,2),t0,t1,t2,n0,n1,n2,0,func,f,argptr);
492 >    id = pop_list(&l);
493 >    if(ZERO(verts[id][i]))
494 >    {
495 >      if(last==-1)
496 >      {/* add below and above */
497 >        first = 2;
498 >        first_id= id;
499 >      }
500 >      lbelow=add_data(lbelow,id,&endb);
501 >      labove=add_data(labove,id,&enda);
502 >      last_id = id;
503 >      last = 2;
504 >      continue;
505 >    }
506 >    if(verts[id][i] < 0)
507 >    {
508 >      if(last != 1)
509 >      {
510 >        lbelow=add_data(lbelow,id,&endb);
511 >        if(last==-1)
512 >        {
513 >          first = 0;
514 >          first_id = id;
515 >        }
516 >        last_id = id;
517 >        last = 0;
518 >        continue;
519 >      }
520 >      /* intersect_edges */
521 >      intersect_edge_coord_plane(verts[last_id],verts[id],i,verts[*vcnt]);
522 >      /*newpoint goes to above and below*/
523 >      lbelow=add_data(lbelow,*vcnt,&endb);
524 >      lbelow=add_data(lbelow,id,&endb);
525 >      labove=add_data(labove,*vcnt,&enda);
526 >      last = 0;
527 >      last_id = id;
528 >      (*vcnt)++;
529 >    }
530 >    else
531 >    {
532 >      if(last != 0)
533 >      {
534 >        labove=add_data(labove,id,&enda);
535 >        if(last==-1)
536 >        {
537 >          first = 1;
538 >          first_id = id;
539 >        }
540 >        last_id = id;
541 >        last = 1;
542 >        continue;
543 >      }
544 >      /* intersect_edges */
545 >      /*newpoint goes to above and below*/
546 >      intersect_edge_coord_plane(verts[last_id],verts[id],i,verts[*vcnt]);
547 >      lbelow=add_data(lbelow,*vcnt,&endb);
548 >      labove=add_data(labove,*vcnt,&enda);
549 >      labove=add_data(labove,id,&enda);
550 >      last_id = id;
551 >      (*vcnt)++;
552 >      last = 1;
553 >    }
554 >  }
555 >  if(first != 2 && first != last)
556 >  {
557 >    intersect_edge_coord_plane(verts[id],verts[first_id],i,verts[*vcnt]);
558 >    /*newpoint goes to above and below*/
559 >    lbelow=add_data(lbelow,*vcnt,&endb);
560 >    labove=add_data(labove,*vcnt,&enda);
561 >    (*vcnt)++;
562  
563    }
564 +  if(i==2)
565 +  {
566 +    if(lbelow)
567 +    {
568 +      if(LIST_NEXT(lbelow) && LIST_NEXT(LIST_NEXT(lbelow)))
569 +      {
570 +        cellb = cell | (1 << i);
571 +        stVisit_poly(st,verts,lbelow,cellb,func,n);
572 +      }
573 +      else
574 +        free_list(lbelow);
575 +    }
576 +    if(labove)
577 +     {
578 +      if(LIST_NEXT(labove) && LIST_NEXT(LIST_NEXT(labove)))
579 +        stVisit_poly(st,verts,labove,cell,func,n);
580 +      else
581 +        free_list(labove);
582 +     }
583 +  }
584 +  else
585 +  {
586 +    if(lbelow)
587 +    {
588 +      if(LIST_NEXT(lbelow) && LIST_NEXT(LIST_NEXT(lbelow)))
589 +        {
590 +          cellb = cell | (1 << i);
591 +          stVisit_clip(st,i+1,verts,vcnt,lbelow,cellb,func,n);
592 +        }
593 +      else
594 +        free_list(lbelow);
595 +    }
596 +    if(labove)
597 +     {
598 +       if(LIST_NEXT(labove) && LIST_NEXT(LIST_NEXT(labove)))
599 +         stVisit_clip(st,i+1,verts,vcnt,labove,cell,func,n);
600 +       else
601 +         free_list(labove);
602 +     }
603 +  }
604 +
605   }
606  
607 < /* 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,edge_func,tri_func,argptr)
607 > stVisit(st,tri,func,n)
608     STREE *st;
609 <   FVECT t0,t1,t2;
610 <   int (*edge_func)(),(*tri_func)();
611 <   int *argptr;
609 >   FVECT tri[3];
610 >   FUNC func;
611 >   int n;
612   {
613 <    int f;
614 <    FVECT dir;
613 >    int r0,r1,r2;
614 >    LIST *l;
615 >
616 >    r0 = stLocate_root(tri[0]);
617 >    r1 = stLocate_root(tri[1]);
618 >    r2 = stLocate_root(tri[2]);
619 >    if(r0 == r1 && r1==r2)
620 >      stRoot_visit_tri(st,r0,tri,func,n);
621 >    else
622 >      {
623 >        FVECT verts[ST_CLIP_VERTS];
624 >        int cnt;
625 >
626 >        VCOPY(verts[0],tri[0]);
627 >        VCOPY(verts[1],tri[1]);
628 >        VCOPY(verts[2],tri[2]);
629 >        
630 >        l = add_data(NULL,0,NULL);
631 >        l = add_data(l,1,NULL);
632 >        l = add_data(l,2,NULL);
633 >        cnt = 3;
634 >        stVisit_clip(st,0,verts,&cnt,l,0,func,n);
635 >      }
636 > }
637 >
638 >
639 > BCOORD qtRoot[3][3] = { {MAXBCOORD2,0,0},{0,MAXBCOORD2,0},{0,0,MAXBCOORD2}};
640 >
641 >
642 > convert_tri_to_frame(root,tri,b0,b1,b2,db10,db21,db02)
643 > int root;
644 > FVECT tri[3];
645 > BCOORD b0[3],b1[3],b2[3];
646 > BCOORD db10[3],db21[3],db02[3];
647 > {
648 >  /* Project the vertex into the qtree plane */
649 >  vert_to_qt_frame(root,tri[0],b0);
650 >  vert_to_qt_frame(root,tri[1],b1);
651 >  vert_to_qt_frame(root,tri[2],b2);
652 >
653 >  /* calculate triangle edge differences in new frame */
654 >  db10[0] = b1[0] - b0[0]; db10[1] = b1[1] - b0[1]; db10[2] = b1[2] - b0[2];
655 >  db21[0] = b2[0] - b1[0]; db21[1] = b2[1] - b1[1]; db21[2] = b2[2] - b1[2];
656 >  db02[0] = b0[0] - b2[0]; db02[1] = b0[1] - b2[1]; db02[2] = b0[2] - b2[2];
657 > }
658 >
659 >
660 > QUADTREE
661 > stRoot_insert_tri(st,root,tri,f)
662 >   STREE *st;
663 >   int root;
664 >   FVECT tri[3];
665 >   FUNC f;
666 > {
667 >  BCOORD b0[3],b1[3],b2[3];
668 >  BCOORD db10[3],db21[3],db02[3];
669 >  unsigned int s0,s1,s2,sq0,sq1,sq2;
670 >  QUADTREE qt;
671 >
672 >  /* Map the triangle vertices into the canonical barycentric frame */
673 >  convert_tri_to_frame(root,tri,b0,b1,b2,db10,db21,db02);
674 >
675 >  /* Calculate initial sidedness info */
676 >  SIDES_GTR(b0,b1,b2,s0,s1,s2,qtRoot[1][0],qtRoot[0][1],qtRoot[0][2]);
677 >  SIDES_GTR(b0,b1,b2,sq0,sq1,sq2,qtRoot[0][0],qtRoot[1][1],qtRoot[2][2]);
678 >
679 >  qt = ST_ROOT_QT(st,root);
680 >  /* Visit cells that triangle intersects */
681 >  qt = qtInsert_tri(root,qt,qtRoot[0],qtRoot[1],qtRoot[2],
682 >       b0,b1,b2,db10,db21,db02,MAXBCOORD2 >> 1,s0,s1,s2, sq0,sq1,sq2,f,0);
683 >
684 >  return(qt);
685 > }
686 >
687 > stRoot_visit_tri(st,root,tri,f,n)
688 >   STREE *st;
689 >   int root;
690 >   FVECT tri[3];
691 >   FUNC f;
692 >   int n;
693 > {
694 >  BCOORD b0[3],b1[3],b2[3];
695 >  BCOORD db10[3],db21[3],db02[3];
696 >  unsigned int s0,s1,s2,sq0,sq1,sq2;
697 >  QUADTREE qt;
698 >
699 >  /* Map the triangle vertices into the canonical barycentric frame */
700 >  convert_tri_to_frame(root,tri,b0,b1,b2,db10,db21,db02);
701 >
702 >  /* Calculate initial sidedness info */
703 >  SIDES_GTR(b0,b1,b2,s0,s1,s2,qtRoot[1][0],qtRoot[0][1],qtRoot[0][2]);
704 >  SIDES_GTR(b0,b1,b2,sq0,sq1,sq2,qtRoot[0][0],qtRoot[1][1],qtRoot[2][2]);
705 >
706 >  qt = ST_ROOT_QT(st,root);
707 >  QT_SET_FLAG(ST_QT(st,root));
708 >  /* Visit cells that triangle intersects */
709 >  qtVisit_tri(root,qt,qtRoot[0],qtRoot[1],qtRoot[2],
710 >       b0,b1,b2,db10,db21,db02,MAXBCOORD2 >> 1,s0,s1,s2, sq0,sq1,sq2,f,n);
711 >
712 > }
713 >
714 > stInsert_tri(st,tri,f)
715 >   STREE *st;
716 >   FVECT tri[3];
717 >   FUNC f;
718 > {
719 >  unsigned int cells,which;
720 >  int root;
721 >  
722 >
723 >  /* calculate entry/exit points of edges through the cells */
724 >  cells = stTri_cells(st,tri);
725 >
726 >  /* For each cell that quadtree intersects: Map the triangle vertices into
727 >     the canonical barycentric frame of (1,0,0), (0,1,0),(0,0,1). Insert
728 >     by first doing a trivial reject on the interior nodes, and then a
729 >     tri/tri intersection at the leaf nodes.
730 >  */
731 >  for(root=0,which=1; root < ST_NUM_ROOT_NODES; root++,which <<= 1)
732 >  {
733 >    /* For each of the quadtree roots: check if marked as intersecting tri*/
734 >    if(cells & which)
735 >      /* Visit tri cells */
736 >      ST_ROOT_QT(st,root) = stRoot_insert_tri(st,root,tri,f);
737 >  }
738 > }
739 >
740 > stInsert_samp(st,p,f)
741 >   STREE *st;
742 >   FVECT p;
743 >   FUNC f;
744 > {
745 >
746 >    QUADTREE qt;
747 >    BCOORD bcoordi[3];
748 >    int i,done;
749 >
750 >    /* Find root quadtree that contains p */
751 >    i = stLocate_root(p);
752 >    qt = ST_ROOT_QT(st,i);
753      
754 <  /* First add all of the leaf cells lying on the triangle perimeter:
755 <     mark all cells seen on the way
756 <   */
302 <    f = 0;
303 <    /* Visit cells along edges of the tri */
304 <    stVisit_tri_edges(st,t0,t1,t2,edge_func,&f,argptr);
754 >    vert_to_qt_frame(i,p,bcoordi);
755 >    ST_ROOT_QT(st,i) =  qtInsert_point(i,qt,EMPTY,qtRoot[0],qtRoot[1],
756 >                          qtRoot[2],bcoordi,MAXBCOORD2>>1,f,0,&done);
757  
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);
758   }
759 +
760  
761  
762  

Diff Legend

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