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.12 by gwlarson, Fri Mar 5 16:32:49 1999 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,
# Line 1205 | Line 1371 | Lfunc_call:
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