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

Comparing ray/src/hd/sm_qtree.c (file contents):
Revision 3.9 by gwlarson, Mon Dec 28 18:07:36 1998 UTC vs.
Revision 3.17 by schorsch, Mon Jun 30 14:59:12 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_qtree.c: adapted from octree.c from radiance code
6   */
# Line 13 | Line 10 | static char SCCSid[] = "$SunId$ SGI";
10   *     7/28/85
11   */
12  
13 + #include <string.h>
14 +
15   #include "standard.h"
16   #include "sm_flag.h"
17   #include "sm_geom.h"
18 + #include "object.h"
19   #include "sm_qtree.h"
20  
21 < QUADTREE  *quad_block[QT_MAX_BLK];              /* our quadtree */
21 > QUADTREE  *quad_block[QT_MAX_BLK];        /* our quadtree */
22   static QUADTREE  quad_free_list = EMPTY;  /* freed octree nodes */
23 < static QUADTREE  treetop = 0;           /* next free node */
24 < int4 *quad_flag= NULL;
23 > static QUADTREE  treetop = 0;             /* next free node */
24 > int32 *quad_flag= NULL;                    /* quadtree flags */
25  
26 – #ifdef TEST_DRIVER
27 – extern FVECT Pick_v0[500],Pick_v1[500],Pick_v2[500];
28 – extern int Pick_cnt,Pick_tri,Pick_samp;
29 – extern FVECT Pick_point[500];
30 – extern int Pick_q[500];
26  
27 + qtremovelast(qt,id)
28 + QUADTREE qt;
29 + OBJECT id;
30 + {
31 + #ifdef DEBUG
32 +  if(qtqueryset(qt)[(*(qtqueryset(qt)))] != id)
33 +    error(CONSISTENCY,"not removed\n");
34   #endif
35 < int Incnt=0;
36 <
35 >  ((*(qtqueryset(qt)))--);
36 > }
37   QUADTREE
38   qtAlloc()                       /* allocate a quadtree */
39   {
# Line 52 | Line 54 | qtAlloc()                      /* allocate a quadtree */
54             error(SYSTEM,"qtAlloc(): Unable to allocate memory\n");
55  
56          /* Realloc the per/node flags */
57 <        quad_flag = (int4 *)realloc((char *)quad_flag,
57 >        quad_flag = (int32 *)realloc((void *)quad_flag,
58                          (QT_BLOCK(freet)+1)*((QT_BLOCK_SIZE+7)>>3));
59          if (quad_flag == NULL)
60             error(SYSTEM,"qtAlloc(): Unable to allocate memory\n");
# Line 68 | Line 70 | qtClearAllFlags()              /* clear all quadtree branch flags
70      return;
71    
72    /* Clear the node flags*/
73 <  bzero((char *)quad_flag, (QT_BLOCK(treetop-4)+1)*((QT_BLOCK_SIZE+7)>>3));
73 >  memset((char *)quad_flag, '\0',
74 >                  (QT_BLOCK(treetop-4)+1)*((QT_BLOCK_SIZE+7)>>3));
75    /* Clear set flags */
76    qtclearsetflags();
77   }
# Line 99 | Line 102 | qtDone()                       /* free EVERYTHING */
102          {
103              if (quad_block[i] == NULL)
104                  break;
105 <            free((char *)quad_block[i]);
105 >            free((void *)quad_block[i]);
106              quad_block[i] = NULL;
107          }
108          /* Free the flags */
109 <        if (i) free((char *)quad_flag);
109 >        if (i) free((void *)quad_flag);
110          quad_flag = NULL;
111          quad_free_list = EMPTY;
112          treetop = 0;
113   }
114  
115 + /*
116 + * bary_parent(coord,i)  : Set coord to be value of pt at one level up in
117 + *                         quadtree, given it was the ith child
118 + * BCOORD coord[3];      :barycentric coordinates of point, also will hold
119 + *                        result as side effect
120 + * int i;                :designates which child coord was
121 + */
122 + bary_parent(coord,i)
123 + BCOORD coord[3];
124 + int i;
125 + {
126 +  switch(i) {
127 +  case 0:
128 +    /* update bary for child */
129 +    coord[0] = (coord[0] >> 1) + MAXBCOORD4;
130 +    coord[1] >>= 1;
131 +    coord[2] >>= 1;
132 +    break;
133 +  case 1:
134 +    coord[0] >>= 1;
135 +    coord[1]  = (coord[1] >> 1) + MAXBCOORD4;
136 +    coord[2] >>= 1;
137 +    break;
138 +    
139 +  case 2:
140 +    coord[0] >>= 1;
141 +    coord[1] >>= 1;
142 +    coord[2] = (coord[2] >> 1) + MAXBCOORD4;
143 +    break;
144 +    
145 +  case 3:
146 +    coord[0] = MAXBCOORD4 - (coord[0] >> 1);
147 +    coord[1] = MAXBCOORD4 - (coord[1] >> 1);
148 +    coord[2] = MAXBCOORD4 - (coord[2] >> 1);
149 +    break;
150 + #ifdef DEBUG
151 +  default:
152 +    eputs("bary_parent():Invalid child\n");
153 +    break;
154 + #endif
155 +  }
156 + }
157 +
158 + /*
159 + * bary_from_child(coord,child,next): Given that coord was the (child) child
160 + *                      of the quadtree node, calculate what the (next) child
161 + *                      is at the same level.
162 + * BCOORD coord[3];   :At current level (child)th child of node,will also hold
163 + *                     result as side effect
164 + * int child,next;    :Which child coord was (child), and which one
165 + *                     is now desired(next)
166 + */
167 + bary_from_child(coord,child,next)
168 + BCOORD coord[3];
169 + int child,next;
170 + {
171 + #ifdef DEBUG
172 +  if(child <0 || child > 3)
173 +  {
174 +    eputs("bary_from_child():Invalid child\n");
175 +    return;
176 +  }
177 +  if(next <0 || next > 3)
178 +  {
179 +    eputs("bary_from_child():Invalid next\n");
180 +    return;
181 +  }
182 + #endif
183 +  if(next == child)
184 +    return;
185 +
186 +  switch(child){
187 +  case 0:
188 +      coord[0] = 0;
189 +      coord[1] = MAXBCOORD2 - coord[1];
190 +      coord[2] = MAXBCOORD2 - coord[2];
191 +      break;
192 +  case 1:
193 +      coord[0] = MAXBCOORD2 - coord[0];
194 +      coord[1] = 0;
195 +      coord[2] = MAXBCOORD2 - coord[2];
196 +      break;
197 +  case 2:
198 +      coord[0] = MAXBCOORD2 - coord[0];
199 +      coord[1] = MAXBCOORD2 - coord[1];
200 +      coord[2] = 0;
201 +    break;
202 +  case 3:
203 +    switch(next){
204 +    case 0:
205 +      coord[0] = 0;
206 +      coord[1] = MAXBCOORD2 - coord[1];
207 +      coord[2] = MAXBCOORD2 - coord[2];
208 +      break;
209 +    case 1:
210 +      coord[0] = MAXBCOORD2 - coord[0];
211 +      coord[1] = 0;
212 +      coord[2] = MAXBCOORD2 - coord[2];
213 +      break;
214 +    case 2:
215 +      coord[0] = MAXBCOORD2 - coord[0];
216 +      coord[1] = MAXBCOORD2 - coord[1];
217 +      coord[2] = 0;
218 +      break;
219 +    }
220 +    break;
221 +  }
222 + }
223 +
224 + /*
225 + * int
226 + * bary_child(coord):  Return which child coord is of node at current level
227 + *                     As side effect recalculate coord at next level
228 + * BCOORD coord[3];   :At current level coordinates of point, will also set
229 + *                     to coords at next level as side effect
230 + */
231 + int
232 + bary_child(coord)
233 + BCOORD coord[3];
234 + {
235 +  int i;
236 +
237 +  if(coord[0] > MAXBCOORD4)
238 +  {
239 +      /* update bary for child */
240 +      coord[0] = (coord[0]<< 1) - MAXBCOORD2;
241 +      coord[1] <<= 1;
242 +      coord[2] <<= 1;
243 +      return(0);
244 +  }
245 +  else
246 +    if(coord[1] > MAXBCOORD4)
247 +    {
248 +      coord[0] <<= 1;
249 +      coord[1] = (coord[1] << 1) - MAXBCOORD2;
250 +      coord[2] <<= 1;
251 +      return(1);
252 +    }
253 +    else
254 +      if(coord[2] > MAXBCOORD4)
255 +      {
256 +        coord[0] <<= 1;
257 +        coord[1] <<= 1;
258 +        coord[2] = (coord[2] << 1) - MAXBCOORD2;
259 +        return(2);
260 +      }
261 +      else
262 +         {
263 +           coord[0] = MAXBCOORD2 - (coord[0] << 1);
264 +           coord[1] = MAXBCOORD2 - (coord[1] << 1);
265 +           coord[2] = MAXBCOORD2 - (coord[2] << 1);
266 +           return(3);
267 +         }
268 + }
269 +
270 +
271 +
272   QUADTREE
273   qtLocate(qt,bcoord)
274   QUADTREE qt;
# Line 247 | Line 407 | qtTrace_ray(qt,b,db0,db1,db2,nextptr,sign,sfactor,func
407     }
408   }    
409  
250 –
251 –
252 –
253 –
254 –
255 –
256 –
410   #define TEST_INT(tl,th,d,q0,q1,h,l) \
411                    tl=d>q0;th=d<q1; if(tl&&th) goto Lfunc_call; \
412                   if(tl) if(l) goto Lfunc_call; else h=TRUE; \
# Line 281 | Line 434 | int n;
434  
435    /* First check if can trivial accept: if vertex in cell */
436    if(s0 & s1 & s2)
437 +  {
438      goto Lfunc_call;
439 <
439 >  }
440    /* Assumption: Could not trivial reject*/
441    /* IF any coords lie on edge- must be in if couldnt reject */
442    a = q1[0];b= q0[1]; c= q0[2];
443    if(t0[0]== a || t0[1] == b || t0[2] == c)
444 +  {
445      goto Lfunc_call;
446 +  }
447    if(t1[0]== a || t1[1] == b || t1[2] == c)
448 +  {
449      goto Lfunc_call;
450 +  }
451    if(t2[0]== a || t2[1] == b || t2[2] == c)
452 +  {
453      goto Lfunc_call;
454 <  
454 >  }
455    /* Test for edge crossings */
456    /* Test t0t1,t1t2,t2t0 against a */
457    /* Calculate edge crossings */
# Line 411 | Line 570 | int n;
570    char testl,testh,test_t0t1,test_t1t2,test_t2t0;
571    unsigned int ls0,ls1,ls2;
572    
573 +  
574    /* May have gotten passed trivial reject if one/two vertices are ON */
575    a = q1[0];b= q0[1]; c= q0[2];
576    SIDES_LESS(t0,t1,t2,ls0,ls1,ls2,a,b,c);
577    
578    /* First check if can trivial accept: if vertex in cell */
579    if(ls0 & ls1 & ls2)
580 +  {
581      goto Lfunc_call;
582 <
582 >  }
583    if(ls0==0 || ls1 == 0 || ls2 ==0)
584      return(qt);
585    /* Assumption: Could not trivial reject*/
586    /* IF any coords lie on edge- must be in if couldnt reject */
587  
588    if(t0[0]== a || t0[1] == b || t0[2] == c)
589 +  {
590      goto Lfunc_call;
591 +  }
592    if(t1[0]== a || t1[1] == b || t1[2] == c)
593 +  {
594      goto Lfunc_call;
595 +  }
596    if(t2[0]== a || t2[1] == b || t2[2] == c)
597 +  {
598      goto Lfunc_call;
599 <
599 >  }
600    /* Test for edge crossings */
601    /* Test t0t1 against a,b,c */
602    /* First test if t0t1 can be trivially rejected */
# Line 454 | Line 620 | int n;
620        db = t1[1] + dt21[1]*((double)(a - t1[0]))/dt21[0];
621        TEST_INT(testl,testh,db,q1[1],b,bl,bh)
622    }
623 <  test_t2t0 = !(((ls0 & 5)==0) || ((ls1 & 5)==0)|| ((ls2 & 5)==0) ||
623 > test_t2t0 = !(((ls0 & 5)==0) || ((ls1 & 5)==0)|| ((ls2 & 5)==0) ||
624         ((sq0 & 5)==0) ||((sq1 & 5)==0)|| ((sq2 & 5)==0));
625    if(test_t2t0 && (e0 & 4))
626    {
# Line 519 | Line 685 | int n;
685  
686    return(qt);
687   Lfunc_call:
522 –
688    qt = f.func(f.argptr,root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
689                s0,s1,s2,sq0,sq1,sq2,1,f,n);
690    return(qt);
# Line 650 | Line 815 | BCOORD dt10[3],dt21[3],dt02[3];
815   BCOORD scale;
816   unsigned int s0,s1,s2,sq0,sq1,sq2;
817   FUNC f;
818 + int n;
819   {
820    BCOORD a,b,c;
821    BCOORD va[3],vb[3],vc[3];
# Line 740 | Line 906 | FUNC f;
906   /*************************************************************************/
907   /* Visit code for applying functions: NOTE THIS IS THE SAME AS INSERT CODE:
908    except sets flags: wanted insert to be as efficient as possible: so
909 <  broke into two sets of routines
909 >  broke into two sets of routines. Also traverses only to n levels.
910   */
911  
912   qtVisit_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
913 <            s0,s1,s2,sq0,sq1,sq2,f)
913 >            s0,s1,s2,sq0,sq1,sq2,f,n)
914   int root;
915   QUADTREE qt;
916   BCOORD q0[3],q1[3],q2[3];
# Line 753 | Line 919 | BCOORD dt10[3],dt21[3],dt02[3];
919   BCOORD scale;
920   unsigned int s0,s1,s2,sq0,sq1,sq2;
921   FUNC f;
922 + int n;
923   {
924    BCOORD a,b,c;
925    BCOORD va[3],vb[3],vc[3];
926    unsigned int sa,sb,sc;
927  
928 +  if(n == 0)
929 +    return;
930    /* If a tree: trivial reject and recurse on potential children */
931    if(QT_IS_TREE(qt))
932    {
# Line 780 | Line 949 | FUNC f;
949        vb[2] = c;
950        vb[0] = vc[0] = a;
951        qtVisit_tri(root,QT_NTH_CHILD(qt,0),q0,vc,
952 <          vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f);
952 >          vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
953        return;
954      }
955     if(sb==7)
# Line 791 | Line 960 | FUNC f;
960       va[2] = c;
961       vc[0] = a;
962       qtVisit_tri(root,QT_NTH_CHILD(qt,1),vc,q1,va,
963 <             t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
963 >             t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
964       return;
965     }
966     if(sc==7)
# Line 802 | Line 971 | FUNC f;
971       va[2] = vb[2] = c;
972       vb[0] = a;
973       qtVisit_tri(root,QT_NTH_CHILD(qt,2),vb,va,
974 <       q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
974 >       q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
975       return;
976     }
977  
# Line 816 | Line 985 | FUNC f;
985     if(sa==0 && sb==0 && sc==0)
986     {
987       qtVisit_tri_rev(root,QT_NTH_CHILD(qt,3),va,vb,
988 <       vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f);
988 >       vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
989        return;
990     }
991  
992     if(sa)
993       qtVisit_tri(root,QT_NTH_CHILD(qt,0),q0,vc,vb,t0,
994 <          t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f);
994 >          t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
995     if(sb)
996       qtVisit_tri(root,QT_NTH_CHILD(qt,1),vc,q1,va,t0,
997 <              t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
997 >              t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
998     if(sc)
999       qtVisit_tri(root,QT_NTH_CHILD(qt,2),vb,va,q2,t0,
1000 <              t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
1000 >              t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
1001     qtVisit_tri_rev(root,QT_NTH_CHILD(qt,3),va,vb,vc,t0,
1002 <             t1,t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f);
1002 >             t1,t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
1003    }
1004    /* Leaf node: Do definitive test */
1005    else
1006      qtLeaf_visit_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
1007 <                         scale,s0,s1,s2,sq0,sq1,sq2,f);
1007 >                         scale,s0,s1,s2,sq0,sq1,sq2,f,n);
1008  
1009   }
1010  
1011  
1012   qtVisit_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
1013 <            s0,s1,s2,sq0,sq1,sq2,f)
1013 >            s0,s1,s2,sq0,sq1,sq2,f,n)
1014   int root;
1015   QUADTREE qt;
1016   BCOORD q0[3],q1[3],q2[3];
# Line 850 | Line 1019 | BCOORD dt10[3],dt21[3],dt02[3];
1019   BCOORD scale;
1020   unsigned int s0,s1,s2,sq0,sq1,sq2;
1021   FUNC f;
1022 + int n;
1023   {
1024    BCOORD a,b,c;
1025    BCOORD va[3],vb[3],vc[3];
1026    unsigned int sa,sb,sc;
1027  
1028 +  if(n==0)
1029 +    return;
1030    /* If a tree: trivial reject and recurse on potential children */
1031    if(QT_IS_TREE(qt))
1032    {
# Line 876 | Line 1048 | FUNC f;
1048        vb[2] = c;
1049        vb[0] = vc[0] = a;
1050        qtVisit_tri_rev(root,QT_NTH_CHILD(qt,0),q0,vc,
1051 <          vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f);
1051 >          vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
1052        return;
1053      }
1054      if(sb==0)
# Line 887 | Line 1059 | FUNC f;
1059        va[2] = c;
1060        vc[0] = a;
1061        qtVisit_tri_rev(root,QT_NTH_CHILD(qt,1),vc,q1,va,
1062 <         t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
1062 >         t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
1063        return;
1064      }
1065      if(sc==0)
# Line 898 | Line 1070 | FUNC f;
1070        va[2] = vb[2] = c;
1071        vb[0] = a;
1072        qtVisit_tri_rev(root,QT_NTH_CHILD(qt,2),vb,va,
1073 <         q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
1073 >         q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
1074        return;
1075      }
1076      va[0] = q1[0];
# Line 911 | Line 1083 | FUNC f;
1083      if(sa==7 && sb==7 && sc==7)
1084      {
1085       qtVisit_tri(root,QT_NTH_CHILD(qt,3),va,vb,
1086 <           vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f);
1086 >           vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
1087        return;
1088      }
1089      if(sa!=7)
1090        qtVisit_tri_rev(root,QT_NTH_CHILD(qt,0),q0,vc,vb,
1091 <           t0,t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f);
1091 >           t0,t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
1092      if(sb!=7)
1093        qtVisit_tri_rev(root,QT_NTH_CHILD(qt,1),vc,q1,va,
1094 <           t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
1094 >           t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
1095      if(sc!=7)
1096        qtVisit_tri_rev(root,QT_NTH_CHILD(qt,2),vb,va,q2,
1097 <           t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
1097 >           t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
1098  
1099      qtVisit_tri(root,QT_NTH_CHILD(qt,3),va,vb,vc,t0,t1,
1100 <              t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f);
1100 >              t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
1101      return;
1102    }
1103    /* Leaf node: Do definitive test */
1104    else
1105      qtLeaf_visit_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
1106 <                         scale,s0,s1,s2,sq0,sq1,sq2,f);
1106 >                         scale,s0,s1,s2,sq0,sq1,sq2,f,n);
1107   }
1108  
1109  
1110  
1111   qtLeaf_visit_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
1112 <                 scale, s0,s1,s2,sq0,sq1,sq2,f)
1112 >                 scale, s0,s1,s2,sq0,sq1,sq2,f,n)
1113   int root;
1114   QUADTREE qt;
1115   BCOORD q0[3],q1[3],q2[3];
# Line 945 | Line 1117 | BCOORD t0[3],t1[3],t2[3];
1117   BCOORD dt10[3],dt21[3],dt02[3];
1118   unsigned int scale,s0,s1,s2,sq0,sq1,sq2;
1119   FUNC f;
1120 + int n;
1121   {
1122    double db;
1123    unsigned int e0,e1,e2;
1124    char al,ah,bl,bh,cl,ch,testl,testh;
1125    char test_t0t1,test_t1t2,test_t2t0;
1126    BCOORD a,b,c;
1127 <
1127 >  
1128    /* First check if can trivial accept: if vertex in cell */
1129    if(s0 & s1 & s2)
1130      goto Lfunc_call;
# Line 1055 | Line 1228 | FUNC f;
1228    return;
1229  
1230   Lfunc_call:
1231 <  f.func(f.argptr,root,qt);
1231 >
1232 >  f.func(f.argptr,root,qt,n);
1233    if(!QT_IS_EMPTY(qt))
1234      QT_LEAF_SET_FLAG(qt);
1235 +
1236   }
1237  
1238  
# Line 1065 | Line 1240 | Lfunc_call:
1240   /* Leaf node: Do definitive test */
1241   QUADTREE
1242   qtLeaf_visit_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
1243 <                 scale, s0,s1,s2,sq0,sq1,sq2,f)
1243 >                 scale, s0,s1,s2,sq0,sq1,sq2,f,n)
1244   int root;
1245   QUADTREE qt;
1246   BCOORD q0[3],q1[3],q2[3];
# Line 1073 | Line 1248 | BCOORD t0[3],t1[3],t2[3];
1248   BCOORD dt10[3],dt21[3],dt02[3];
1249   unsigned int scale,s0,s1,s2,sq0,sq1,sq2;
1250   FUNC f;
1251 + int n;
1252   {
1253    double db;
1254    unsigned int e0,e1,e2;
# Line 1191 | Line 1367 | FUNC f;
1367    return;
1368  
1369   Lfunc_call:
1370 <  f.func(f.argptr,root,qt);
1370 >  f.func(f.argptr,root,qt,n);
1371    if(!QT_IS_EMPTY(qt))
1372      QT_LEAF_SET_FLAG(qt);
1373   }
1374 +
1375 +
1376 + QUADTREE
1377 + qtInsert_point(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr)
1378 + int root;
1379 + QUADTREE qt,parent;
1380 + BCOORD q0[3],q1[3],q2[3],bc[3],scale;
1381 + FUNC f;
1382 + int n,*doneptr;
1383 + {
1384 +  BCOORD a,b,c;
1385 +  BCOORD va[3],vb[3],vc[3];
1386 +
1387 +  if(QT_IS_TREE(qt))
1388 +  {  
1389 +    a = q1[0] + scale;
1390 +    b = q0[1] + scale;
1391 +    c = q0[2] + scale;
1392 +    if(bc[0] > a)
1393 +    {
1394 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1395 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1396 +      QT_NTH_CHILD(qt,0) = qtInsert_point(root,QT_NTH_CHILD(qt,0),
1397 +                                  qt,q0,vc,vb,bc,scale>>1,f,n+1,doneptr);
1398 +      if(!*doneptr)
1399 +      {
1400 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1401 +        if(!*doneptr)
1402 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1403 +        if(!*doneptr)
1404 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1405 +      }      
1406 +      return(qt);
1407 +    }
1408 +    if(bc[1] > b)
1409 +    {
1410 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1411 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1412 +      QT_NTH_CHILD(qt,1) =qtInsert_point(root,QT_NTH_CHILD(qt,1),
1413 +                                 qt,vc,q1,va,bc,scale >>1,f,n+1,doneptr);
1414 +      if(!*doneptr)
1415 +      {
1416 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1417 +        if(!*doneptr)
1418 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1419 +        if(!*doneptr)
1420 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1421 +      }      
1422 +      return(qt);
1423 +    }
1424 +    if(bc[2] > c)
1425 +    {
1426 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1427 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1428 +      QT_NTH_CHILD(qt,2) = qtInsert_point(root,QT_NTH_CHILD(qt,2),
1429 +                                  qt,vb,va,q2,bc,scale>>1,f,n+1,doneptr);
1430 +      if(!*doneptr)
1431 +      {
1432 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1433 +        if(!*doneptr)
1434 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1435 +        if(!*doneptr)
1436 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1437 +      }
1438 +      return(qt);
1439 +    }
1440 +    else
1441 +    {
1442 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1443 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1444 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1445 +      QT_NTH_CHILD(qt,3) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,3),
1446 +                                      qt,va,vb,vc,bc,scale>>1,f,n+1,doneptr);
1447 +      if(!*doneptr)
1448 +      {
1449 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1450 +        if(!*doneptr)
1451 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1452 +        if(!*doneptr)
1453 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1454 +      }
1455 +      return(qt);
1456 +    }
1457 +  }
1458 +  else
1459 +  {
1460 +    qt = f.func(f.argptr,root,qt,parent,q0,q1,q2,bc,scale,0,f,n,doneptr);
1461 +    return(qt);
1462 +  }
1463 + }
1464 +
1465 +
1466 + QUADTREE
1467 + qtInsert_point_rev(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr)
1468 + int root;
1469 + QUADTREE qt,parent;
1470 + BCOORD q0[3],q1[3],q2[3],bc[3];
1471 + BCOORD scale;
1472 + FUNC f;
1473 + int n,*doneptr;
1474 + {
1475 +  BCOORD a,b,c;
1476 +  BCOORD va[3],vb[3],vc[3];
1477 +
1478 +  if(QT_IS_TREE(qt))
1479 +  {  
1480 +    a = q1[0] - scale;
1481 +    b = q0[1] - scale;
1482 +    c = q0[2] - scale;
1483 +    if(bc[0] < a)
1484 +    {
1485 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1486 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1487 +      QT_NTH_CHILD(qt,0) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,0),
1488 +                                  qt,q0,vc,vb,bc,scale>>1,f,n+1,doneptr);
1489 +      if(!*doneptr)
1490 +      {
1491 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1492 +        if(!*doneptr)
1493 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1494 +        if(!*doneptr)
1495 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1496 +      }
1497 +      return(qt);
1498 +    }
1499 +    if(bc[1] < b)
1500 +    {
1501 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1502 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1503 +      QT_NTH_CHILD(qt,1) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,1),
1504 +                                   qt,vc,q1,va,bc,scale>>1,f,n+1,doneptr);
1505 +      if(!*doneptr)
1506 +      {
1507 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1508 +        if(!*doneptr)
1509 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1510 +        if(!*doneptr)
1511 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1512 +      }
1513 +      return(qt);
1514 +    }
1515 +    if(bc[2] < c)
1516 +    {
1517 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1518 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1519 +      QT_NTH_CHILD(qt,2) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,2),
1520 +                                qt,vb,va,q2,bc,scale>>1,f,n+1,doneptr);
1521 +      if(!*doneptr)
1522 +      {
1523 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1524 +        if(!*doneptr)
1525 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1526 +        if(!*doneptr)
1527 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1528 +      }
1529 +      return(qt);
1530 +    }
1531 +    else
1532 +    {
1533 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1534 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1535 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1536 +      QT_NTH_CHILD(qt,3) = qtInsert_point(root,QT_NTH_CHILD(qt,3),
1537 +                                   qt,va,vb,vc,bc,scale>>1,f,n+1,doneptr);
1538 +      if(!*doneptr)
1539 +      {
1540 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1541 +        if(!*doneptr)
1542 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1543 +        if(!*doneptr)
1544 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1545 +      }
1546 +      return(qt);
1547 +    }
1548 +  }
1549 +  else
1550 +  {
1551 +    qt = f.func(f.argptr,root,qt,parent,q0,q1,q2,bc,scale,1,f,n,doneptr);
1552 +    return(qt);
1553 +  }
1554 + }
1555 +
1556 +
1557 +
1558 +
1559 +
1560 +
1561 +
1562 +
1563  
1564  
1565  

Diff Legend

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