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.14 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_qtree.c: adapted from octree.c from radiance code
6   */
# Line 16 | Line 13 | static char SCCSid[] = "$SunId$ SGI";
13   #include "standard.h"
14   #include "sm_flag.h"
15   #include "sm_geom.h"
16 + #include "object.h"
17   #include "sm_qtree.h"
18  
19 < QUADTREE  *quad_block[QT_MAX_BLK];              /* our quadtree */
19 > QUADTREE  *quad_block[QT_MAX_BLK];        /* our quadtree */
20   static QUADTREE  quad_free_list = EMPTY;  /* freed octree nodes */
21 < static QUADTREE  treetop = 0;           /* next free node */
22 < int4 *quad_flag= NULL;
21 > static QUADTREE  treetop = 0;             /* next free node */
22 > int4 *quad_flag= NULL;                    /* quadtree flags */
23  
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];
24  
25 + qtremovelast(qt,id)
26 + QUADTREE qt;
27 + OBJECT id;
28 + {
29 + #ifdef DEBUG
30 +  if(qtqueryset(qt)[(*(qtqueryset(qt)))] != id)
31 +    error(CONSISTENCY,"not removed\n");
32   #endif
33 < int Incnt=0;
34 <
33 >  ((*(qtqueryset(qt)))--);
34 > }
35   QUADTREE
36   qtAlloc()                       /* allocate a quadtree */
37   {
# Line 99 | Line 99 | qtDone()                       /* free EVERYTHING */
99          {
100              if (quad_block[i] == NULL)
101                  break;
102 <            free((char *)quad_block[i]);
102 >            free((void *)quad_block[i]);
103              quad_block[i] = NULL;
104          }
105          /* Free the flags */
106 <        if (i) free((char *)quad_flag);
106 >        if (i) free((void *)quad_flag);
107          quad_flag = NULL;
108          quad_free_list = EMPTY;
109          treetop = 0;
110   }
111  
112 + /*
113 + * bary_parent(coord,i)  : Set coord to be value of pt at one level up in
114 + *                         quadtree, given it was the ith child
115 + * BCOORD coord[3];      :barycentric coordinates of point, also will hold
116 + *                        result as side effect
117 + * int i;                :designates which child coord was
118 + */
119 + bary_parent(coord,i)
120 + BCOORD coord[3];
121 + int i;
122 + {
123 +  switch(i) {
124 +  case 0:
125 +    /* update bary for child */
126 +    coord[0] = (coord[0] >> 1) + MAXBCOORD4;
127 +    coord[1] >>= 1;
128 +    coord[2] >>= 1;
129 +    break;
130 +  case 1:
131 +    coord[0] >>= 1;
132 +    coord[1]  = (coord[1] >> 1) + MAXBCOORD4;
133 +    coord[2] >>= 1;
134 +    break;
135 +    
136 +  case 2:
137 +    coord[0] >>= 1;
138 +    coord[1] >>= 1;
139 +    coord[2] = (coord[2] >> 1) + MAXBCOORD4;
140 +    break;
141 +    
142 +  case 3:
143 +    coord[0] = MAXBCOORD4 - (coord[0] >> 1);
144 +    coord[1] = MAXBCOORD4 - (coord[1] >> 1);
145 +    coord[2] = MAXBCOORD4 - (coord[2] >> 1);
146 +    break;
147 + #ifdef DEBUG
148 +  default:
149 +    eputs("bary_parent():Invalid child\n");
150 +    break;
151 + #endif
152 +  }
153 + }
154 +
155 + /*
156 + * bary_from_child(coord,child,next): Given that coord was the (child) child
157 + *                      of the quadtree node, calculate what the (next) child
158 + *                      is at the same level.
159 + * BCOORD coord[3];   :At current level (child)th child of node,will also hold
160 + *                     result as side effect
161 + * int child,next;    :Which child coord was (child), and which one
162 + *                     is now desired(next)
163 + */
164 + bary_from_child(coord,child,next)
165 + BCOORD coord[3];
166 + int child,next;
167 + {
168 + #ifdef DEBUG
169 +  if(child <0 || child > 3)
170 +  {
171 +    eputs("bary_from_child():Invalid child\n");
172 +    return;
173 +  }
174 +  if(next <0 || next > 3)
175 +  {
176 +    eputs("bary_from_child():Invalid next\n");
177 +    return;
178 +  }
179 + #endif
180 +  if(next == child)
181 +    return;
182 +
183 +  switch(child){
184 +  case 0:
185 +      coord[0] = 0;
186 +      coord[1] = MAXBCOORD2 - coord[1];
187 +      coord[2] = MAXBCOORD2 - coord[2];
188 +      break;
189 +  case 1:
190 +      coord[0] = MAXBCOORD2 - coord[0];
191 +      coord[1] = 0;
192 +      coord[2] = MAXBCOORD2 - coord[2];
193 +      break;
194 +  case 2:
195 +      coord[0] = MAXBCOORD2 - coord[0];
196 +      coord[1] = MAXBCOORD2 - coord[1];
197 +      coord[2] = 0;
198 +    break;
199 +  case 3:
200 +    switch(next){
201 +    case 0:
202 +      coord[0] = 0;
203 +      coord[1] = MAXBCOORD2 - coord[1];
204 +      coord[2] = MAXBCOORD2 - coord[2];
205 +      break;
206 +    case 1:
207 +      coord[0] = MAXBCOORD2 - coord[0];
208 +      coord[1] = 0;
209 +      coord[2] = MAXBCOORD2 - coord[2];
210 +      break;
211 +    case 2:
212 +      coord[0] = MAXBCOORD2 - coord[0];
213 +      coord[1] = MAXBCOORD2 - coord[1];
214 +      coord[2] = 0;
215 +      break;
216 +    }
217 +    break;
218 +  }
219 + }
220 +
221 + /*
222 + * int
223 + * bary_child(coord):  Return which child coord is of node at current level
224 + *                     As side effect recalculate coord at next level
225 + * BCOORD coord[3];   :At current level coordinates of point, will also set
226 + *                     to coords at next level as side effect
227 + */
228 + int
229 + bary_child(coord)
230 + BCOORD coord[3];
231 + {
232 +  int i;
233 +
234 +  if(coord[0] > MAXBCOORD4)
235 +  {
236 +      /* update bary for child */
237 +      coord[0] = (coord[0]<< 1) - MAXBCOORD2;
238 +      coord[1] <<= 1;
239 +      coord[2] <<= 1;
240 +      return(0);
241 +  }
242 +  else
243 +    if(coord[1] > MAXBCOORD4)
244 +    {
245 +      coord[0] <<= 1;
246 +      coord[1] = (coord[1] << 1) - MAXBCOORD2;
247 +      coord[2] <<= 1;
248 +      return(1);
249 +    }
250 +    else
251 +      if(coord[2] > MAXBCOORD4)
252 +      {
253 +        coord[0] <<= 1;
254 +        coord[1] <<= 1;
255 +        coord[2] = (coord[2] << 1) - MAXBCOORD2;
256 +        return(2);
257 +      }
258 +      else
259 +         {
260 +           coord[0] = MAXBCOORD2 - (coord[0] << 1);
261 +           coord[1] = MAXBCOORD2 - (coord[1] << 1);
262 +           coord[2] = MAXBCOORD2 - (coord[2] << 1);
263 +           return(3);
264 +         }
265 + }
266 +
267 +
268 +
269   QUADTREE
270   qtLocate(qt,bcoord)
271   QUADTREE qt;
# Line 247 | Line 404 | qtTrace_ray(qt,b,db0,db1,db2,nextptr,sign,sfactor,func
404     }
405   }    
406  
250 –
251 –
252 –
253 –
254 –
255 –
256 –
407   #define TEST_INT(tl,th,d,q0,q1,h,l) \
408                    tl=d>q0;th=d<q1; if(tl&&th) goto Lfunc_call; \
409                   if(tl) if(l) goto Lfunc_call; else h=TRUE; \
# Line 281 | Line 431 | int n;
431  
432    /* First check if can trivial accept: if vertex in cell */
433    if(s0 & s1 & s2)
434 +  {
435      goto Lfunc_call;
436 <
436 >  }
437    /* Assumption: Could not trivial reject*/
438    /* IF any coords lie on edge- must be in if couldnt reject */
439    a = q1[0];b= q0[1]; c= q0[2];
440    if(t0[0]== a || t0[1] == b || t0[2] == c)
441 +  {
442      goto Lfunc_call;
443 +  }
444    if(t1[0]== a || t1[1] == b || t1[2] == c)
445 +  {
446      goto Lfunc_call;
447 +  }
448    if(t2[0]== a || t2[1] == b || t2[2] == c)
449 +  {
450      goto Lfunc_call;
451 <  
451 >  }
452    /* Test for edge crossings */
453    /* Test t0t1,t1t2,t2t0 against a */
454    /* Calculate edge crossings */
# Line 411 | Line 567 | int n;
567    char testl,testh,test_t0t1,test_t1t2,test_t2t0;
568    unsigned int ls0,ls1,ls2;
569    
570 +  
571    /* May have gotten passed trivial reject if one/two vertices are ON */
572    a = q1[0];b= q0[1]; c= q0[2];
573    SIDES_LESS(t0,t1,t2,ls0,ls1,ls2,a,b,c);
574    
575    /* First check if can trivial accept: if vertex in cell */
576    if(ls0 & ls1 & ls2)
577 +  {
578      goto Lfunc_call;
579 <
579 >  }
580    if(ls0==0 || ls1 == 0 || ls2 ==0)
581      return(qt);
582    /* Assumption: Could not trivial reject*/
583    /* IF any coords lie on edge- must be in if couldnt reject */
584  
585    if(t0[0]== a || t0[1] == b || t0[2] == c)
586 +  {
587      goto Lfunc_call;
588 +  }
589    if(t1[0]== a || t1[1] == b || t1[2] == c)
590 +  {
591      goto Lfunc_call;
592 +  }
593    if(t2[0]== a || t2[1] == b || t2[2] == c)
594 +  {
595      goto Lfunc_call;
596 <
596 >  }
597    /* Test for edge crossings */
598    /* Test t0t1 against a,b,c */
599    /* First test if t0t1 can be trivially rejected */
# Line 454 | Line 617 | int n;
617        db = t1[1] + dt21[1]*((double)(a - t1[0]))/dt21[0];
618        TEST_INT(testl,testh,db,q1[1],b,bl,bh)
619    }
620 <  test_t2t0 = !(((ls0 & 5)==0) || ((ls1 & 5)==0)|| ((ls2 & 5)==0) ||
620 > test_t2t0 = !(((ls0 & 5)==0) || ((ls1 & 5)==0)|| ((ls2 & 5)==0) ||
621         ((sq0 & 5)==0) ||((sq1 & 5)==0)|| ((sq2 & 5)==0));
622    if(test_t2t0 && (e0 & 4))
623    {
# Line 519 | Line 682 | int n;
682  
683    return(qt);
684   Lfunc_call:
522 –
685    qt = f.func(f.argptr,root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
686                s0,s1,s2,sq0,sq1,sq2,1,f,n);
687    return(qt);
# Line 650 | Line 812 | BCOORD dt10[3],dt21[3],dt02[3];
812   BCOORD scale;
813   unsigned int s0,s1,s2,sq0,sq1,sq2;
814   FUNC f;
815 + int n;
816   {
817    BCOORD a,b,c;
818    BCOORD va[3],vb[3],vc[3];
# Line 740 | Line 903 | FUNC f;
903   /*************************************************************************/
904   /* Visit code for applying functions: NOTE THIS IS THE SAME AS INSERT CODE:
905    except sets flags: wanted insert to be as efficient as possible: so
906 <  broke into two sets of routines
906 >  broke into two sets of routines. Also traverses only to n levels.
907   */
908  
909   qtVisit_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
# Line 1205 | Line 1368 | Lfunc_call:
1368    if(!QT_IS_EMPTY(qt))
1369      QT_LEAF_SET_FLAG(qt);
1370   }
1371 +
1372 +
1373 + QUADTREE
1374 + qtInsert_point(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr)
1375 + int root;
1376 + QUADTREE qt,parent;
1377 + BCOORD q0[3],q1[3],q2[3],bc[3],scale;
1378 + FUNC f;
1379 + int n,*doneptr;
1380 + {
1381 +  BCOORD a,b,c;
1382 +  BCOORD va[3],vb[3],vc[3];
1383 +
1384 +  if(QT_IS_TREE(qt))
1385 +  {  
1386 +    a = q1[0] + scale;
1387 +    b = q0[1] + scale;
1388 +    c = q0[2] + scale;
1389 +    if(bc[0] > a)
1390 +    {
1391 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1392 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1393 +      QT_NTH_CHILD(qt,0) = qtInsert_point(root,QT_NTH_CHILD(qt,0),
1394 +                                  qt,q0,vc,vb,bc,scale>>1,f,n+1,doneptr);
1395 +      if(!*doneptr)
1396 +      {
1397 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1398 +        if(!*doneptr)
1399 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1400 +        if(!*doneptr)
1401 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1402 +      }      
1403 +      return(qt);
1404 +    }
1405 +    if(bc[1] > b)
1406 +    {
1407 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1408 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1409 +      QT_NTH_CHILD(qt,1) =qtInsert_point(root,QT_NTH_CHILD(qt,1),
1410 +                                 qt,vc,q1,va,bc,scale >>1,f,n+1,doneptr);
1411 +      if(!*doneptr)
1412 +      {
1413 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1414 +        if(!*doneptr)
1415 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1416 +        if(!*doneptr)
1417 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1418 +      }      
1419 +      return(qt);
1420 +    }
1421 +    if(bc[2] > c)
1422 +    {
1423 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1424 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1425 +      QT_NTH_CHILD(qt,2) = qtInsert_point(root,QT_NTH_CHILD(qt,2),
1426 +                                  qt,vb,va,q2,bc,scale>>1,f,n+1,doneptr);
1427 +      if(!*doneptr)
1428 +      {
1429 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1430 +        if(!*doneptr)
1431 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1432 +        if(!*doneptr)
1433 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1434 +      }
1435 +      return(qt);
1436 +    }
1437 +    else
1438 +    {
1439 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1440 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1441 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1442 +      QT_NTH_CHILD(qt,3) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,3),
1443 +                                      qt,va,vb,vc,bc,scale>>1,f,n+1,doneptr);
1444 +      if(!*doneptr)
1445 +      {
1446 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1447 +        if(!*doneptr)
1448 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1449 +        if(!*doneptr)
1450 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1451 +      }
1452 +      return(qt);
1453 +    }
1454 +  }
1455 +  else
1456 +  {
1457 +    qt = f.func(f.argptr,root,qt,parent,q0,q1,q2,bc,scale,0,f,n,doneptr);
1458 +    return(qt);
1459 +  }
1460 + }
1461 +
1462 +
1463 + QUADTREE
1464 + qtInsert_point_rev(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr)
1465 + int root;
1466 + QUADTREE qt,parent;
1467 + BCOORD q0[3],q1[3],q2[3],bc[3];
1468 + BCOORD scale;
1469 + FUNC f;
1470 + int n,*doneptr;
1471 + {
1472 +  BCOORD a,b,c;
1473 +  BCOORD va[3],vb[3],vc[3];
1474 +
1475 +  if(QT_IS_TREE(qt))
1476 +  {  
1477 +    a = q1[0] - scale;
1478 +    b = q0[1] - scale;
1479 +    c = q0[2] - scale;
1480 +    if(bc[0] < a)
1481 +    {
1482 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1483 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1484 +      QT_NTH_CHILD(qt,0) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,0),
1485 +                                  qt,q0,vc,vb,bc,scale>>1,f,n+1,doneptr);
1486 +      if(!*doneptr)
1487 +      {
1488 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1489 +        if(!*doneptr)
1490 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1491 +        if(!*doneptr)
1492 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1493 +      }
1494 +      return(qt);
1495 +    }
1496 +    if(bc[1] < b)
1497 +    {
1498 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1499 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1500 +      QT_NTH_CHILD(qt,1) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,1),
1501 +                                   qt,vc,q1,va,bc,scale>>1,f,n+1,doneptr);
1502 +      if(!*doneptr)
1503 +      {
1504 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1505 +        if(!*doneptr)
1506 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1507 +        if(!*doneptr)
1508 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1509 +      }
1510 +      return(qt);
1511 +    }
1512 +    if(bc[2] < c)
1513 +    {
1514 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1515 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1516 +      QT_NTH_CHILD(qt,2) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,2),
1517 +                                qt,vb,va,q2,bc,scale>>1,f,n+1,doneptr);
1518 +      if(!*doneptr)
1519 +      {
1520 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1521 +        if(!*doneptr)
1522 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1523 +        if(!*doneptr)
1524 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1525 +      }
1526 +      return(qt);
1527 +    }
1528 +    else
1529 +    {
1530 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1531 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1532 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1533 +      QT_NTH_CHILD(qt,3) = qtInsert_point(root,QT_NTH_CHILD(qt,3),
1534 +                                   qt,va,vb,vc,bc,scale>>1,f,n+1,doneptr);
1535 +      if(!*doneptr)
1536 +      {
1537 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1538 +        if(!*doneptr)
1539 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1540 +        if(!*doneptr)
1541 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1542 +      }
1543 +      return(qt);
1544 +    }
1545 +  }
1546 +  else
1547 +  {
1548 +    qt = f.func(f.argptr,root,qt,parent,q0,q1,q2,bc,scale,1,f,n,doneptr);
1549 +    return(qt);
1550 +  }
1551 + }
1552 +
1553 +
1554 +
1555 +
1556 +
1557 +
1558 +
1559 +
1560  
1561  
1562  

Diff Legend

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