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.13 by gwlarson, Thu Jun 10 15:22:23 1999 UTC

# Line 30 | Line 30 | extern FVECT Pick_point[500];
30   extern int Pick_q[500];
31  
32   #endif
33 – int Incnt=0;
33  
34 + qtremovelast(qt,id)
35 + QUADTREE qt;
36 + int id;
37 + {
38 +  if(qtqueryset(qt)[(*(qtqueryset(qt)))] != id)
39 +    error(CONSISTENCY,"not removed\n");
40 +  ((*(qtqueryset(qt)))--);
41 + }
42   QUADTREE
43   qtAlloc()                       /* allocate a quadtree */
44   {
# Line 281 | Line 288 | int n;
288  
289    /* First check if can trivial accept: if vertex in cell */
290    if(s0 & s1 & s2)
291 +  {
292      goto Lfunc_call;
293 <
293 >  }
294    /* Assumption: Could not trivial reject*/
295    /* IF any coords lie on edge- must be in if couldnt reject */
296    a = q1[0];b= q0[1]; c= q0[2];
297    if(t0[0]== a || t0[1] == b || t0[2] == c)
298 +  {
299      goto Lfunc_call;
300 +  }
301    if(t1[0]== a || t1[1] == b || t1[2] == c)
302 +  {
303      goto Lfunc_call;
304 +  }
305    if(t2[0]== a || t2[1] == b || t2[2] == c)
306 +  {
307      goto Lfunc_call;
308 <  
308 >  }
309    /* Test for edge crossings */
310    /* Test t0t1,t1t2,t2t0 against a */
311    /* Calculate edge crossings */
# Line 411 | Line 424 | int n;
424    char testl,testh,test_t0t1,test_t1t2,test_t2t0;
425    unsigned int ls0,ls1,ls2;
426    
427 +  
428    /* May have gotten passed trivial reject if one/two vertices are ON */
429    a = q1[0];b= q0[1]; c= q0[2];
430    SIDES_LESS(t0,t1,t2,ls0,ls1,ls2,a,b,c);
431    
432    /* First check if can trivial accept: if vertex in cell */
433    if(ls0 & ls1 & ls2)
434 +  {
435      goto Lfunc_call;
436 <
436 >  }
437    if(ls0==0 || ls1 == 0 || ls2 ==0)
438      return(qt);
439    /* Assumption: Could not trivial reject*/
440    /* IF any coords lie on edge- must be in if couldnt reject */
441  
442    if(t0[0]== a || t0[1] == b || t0[2] == c)
443 +  {
444      goto Lfunc_call;
445 +  }
446    if(t1[0]== a || t1[1] == b || t1[2] == c)
447 +  {
448      goto Lfunc_call;
449 +  }
450    if(t2[0]== a || t2[1] == b || t2[2] == c)
451 +  {
452      goto Lfunc_call;
453 <
453 >  }
454    /* Test for edge crossings */
455    /* Test t0t1 against a,b,c */
456    /* First test if t0t1 can be trivially rejected */
# Line 454 | Line 474 | int n;
474        db = t1[1] + dt21[1]*((double)(a - t1[0]))/dt21[0];
475        TEST_INT(testl,testh,db,q1[1],b,bl,bh)
476    }
477 <  test_t2t0 = !(((ls0 & 5)==0) || ((ls1 & 5)==0)|| ((ls2 & 5)==0) ||
477 > test_t2t0 = !(((ls0 & 5)==0) || ((ls1 & 5)==0)|| ((ls2 & 5)==0) ||
478         ((sq0 & 5)==0) ||((sq1 & 5)==0)|| ((sq2 & 5)==0));
479    if(test_t2t0 && (e0 & 4))
480    {
# Line 519 | Line 539 | int n;
539  
540    return(qt);
541   Lfunc_call:
522 –
542    qt = f.func(f.argptr,root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
543                s0,s1,s2,sq0,sq1,sq2,1,f,n);
544    return(qt);
# Line 650 | Line 669 | BCOORD dt10[3],dt21[3],dt02[3];
669   BCOORD scale;
670   unsigned int s0,s1,s2,sq0,sq1,sq2;
671   FUNC f;
672 + int n;
673   {
674    BCOORD a,b,c;
675    BCOORD va[3],vb[3],vc[3];
# Line 740 | Line 760 | FUNC f;
760   /*************************************************************************/
761   /* Visit code for applying functions: NOTE THIS IS THE SAME AS INSERT CODE:
762    except sets flags: wanted insert to be as efficient as possible: so
763 <  broke into two sets of routines
763 >  broke into two sets of routines. Also traverses only to n levels.
764   */
765  
766   qtVisit_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
# Line 1205 | Line 1225 | Lfunc_call:
1225    if(!QT_IS_EMPTY(qt))
1226      QT_LEAF_SET_FLAG(qt);
1227   }
1228 +
1229 +
1230 + QUADTREE
1231 + qtInsert_point(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr)
1232 + int root;
1233 + QUADTREE qt,parent;
1234 + BCOORD q0[3],q1[3],q2[3],bc[3],scale;
1235 + FUNC f;
1236 + int n,*doneptr;
1237 + {
1238 +  BCOORD a,b,c;
1239 +  BCOORD va[3],vb[3],vc[3];
1240 +
1241 +  if(QT_IS_TREE(qt))
1242 +  {  
1243 +    a = q1[0] + scale;
1244 +    b = q0[1] + scale;
1245 +    c = q0[2] + scale;
1246 +    if(bc[0] > a)
1247 +    {
1248 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1249 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1250 +      QT_NTH_CHILD(qt,0) = qtInsert_point(root,QT_NTH_CHILD(qt,0),
1251 +                                  qt,q0,vc,vb,bc,scale>>1,f,n+1,doneptr);
1252 +      if(!*doneptr)
1253 +      {
1254 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1255 +        if(!*doneptr)
1256 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1257 +        if(!*doneptr)
1258 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1259 +      }      
1260 +      return(qt);
1261 +    }
1262 +    if(bc[1] > b)
1263 +    {
1264 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1265 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1266 +      QT_NTH_CHILD(qt,1) =qtInsert_point(root,QT_NTH_CHILD(qt,1),
1267 +                                 qt,vc,q1,va,bc,scale >>1,f,n+1,doneptr);
1268 +      if(!*doneptr)
1269 +      {
1270 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1271 +        if(!*doneptr)
1272 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1273 +        if(!*doneptr)
1274 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1275 +      }      
1276 +      return(qt);
1277 +    }
1278 +    if(bc[2] > c)
1279 +    {
1280 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1281 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1282 +      QT_NTH_CHILD(qt,2) = qtInsert_point(root,QT_NTH_CHILD(qt,2),
1283 +                                  qt,vb,va,q2,bc,scale>>1,f,n+1,doneptr);
1284 +      if(!*doneptr)
1285 +      {
1286 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1287 +        if(!*doneptr)
1288 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1289 +        if(!*doneptr)
1290 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1291 +      }
1292 +      return(qt);
1293 +    }
1294 +    else
1295 +    {
1296 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1297 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1298 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1299 +      QT_NTH_CHILD(qt,3) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,3),
1300 +                                      qt,va,vb,vc,bc,scale>>1,f,n+1,doneptr);
1301 +      if(!*doneptr)
1302 +      {
1303 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1304 +        if(!*doneptr)
1305 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1306 +        if(!*doneptr)
1307 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1308 +      }
1309 +      return(qt);
1310 +    }
1311 +  }
1312 +  else
1313 +  {
1314 +    qt = f.func(f.argptr,root,qt,parent,q0,q1,q2,bc,scale,0,f,n,doneptr);
1315 +    return(qt);
1316 +  }
1317 + }
1318 +
1319 +
1320 + QUADTREE
1321 + qtInsert_point_rev(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr)
1322 + int root;
1323 + QUADTREE qt,parent;
1324 + BCOORD q0[3],q1[3],q2[3],bc[3];
1325 + BCOORD scale;
1326 + FUNC f;
1327 + int n,*doneptr;
1328 + {
1329 +  BCOORD a,b,c;
1330 +  BCOORD va[3],vb[3],vc[3];
1331 +
1332 +  if(QT_IS_TREE(qt))
1333 +  {  
1334 +    a = q1[0] - scale;
1335 +    b = q0[1] - scale;
1336 +    c = q0[2] - scale;
1337 +    if(bc[0] < a)
1338 +    {
1339 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1340 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1341 +      QT_NTH_CHILD(qt,0) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,0),
1342 +                                  qt,q0,vc,vb,bc,scale>>1,f,n+1,doneptr);
1343 +      if(!*doneptr)
1344 +      {
1345 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1346 +        if(!*doneptr)
1347 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1348 +        if(!*doneptr)
1349 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1350 +      }
1351 +      return(qt);
1352 +    }
1353 +    if(bc[1] < b)
1354 +    {
1355 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1356 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1357 +      QT_NTH_CHILD(qt,1) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,1),
1358 +                                   qt,vc,q1,va,bc,scale>>1,f,n+1,doneptr);
1359 +      if(!*doneptr)
1360 +      {
1361 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1362 +        if(!*doneptr)
1363 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1364 +        if(!*doneptr)
1365 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1366 +      }
1367 +      return(qt);
1368 +    }
1369 +    if(bc[2] < c)
1370 +    {
1371 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1372 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1373 +      QT_NTH_CHILD(qt,2) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,2),
1374 +                                qt,vb,va,q2,bc,scale>>1,f,n+1,doneptr);
1375 +      if(!*doneptr)
1376 +      {
1377 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1378 +        if(!*doneptr)
1379 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1380 +        if(!*doneptr)
1381 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
1382 +      }
1383 +      return(qt);
1384 +    }
1385 +    else
1386 +    {
1387 +      va[0] = q1[0]; va[1] = b; va[2] = c;
1388 +      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
1389 +      vc[0] = a; vc[1] = b; vc[2] = q0[2];
1390 +      QT_NTH_CHILD(qt,3) = qtInsert_point(root,QT_NTH_CHILD(qt,3),
1391 +                                   qt,va,vb,vc,bc,scale>>1,f,n+1,doneptr);
1392 +      if(!*doneptr)
1393 +      {
1394 +        f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
1395 +        if(!*doneptr)
1396 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
1397 +        if(!*doneptr)
1398 +          f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
1399 +      }
1400 +      return(qt);
1401 +    }
1402 +  }
1403 +  else
1404 +  {
1405 +    qt = f.func(f.argptr,root,qt,parent,q0,q1,q2,bc,scale,1,f,n,doneptr);
1406 +    return(qt);
1407 +  }
1408 + }
1409 +
1410 +
1411 +
1412 +
1413 +
1414 +
1415 +
1416  
1417  
1418  

Diff Legend

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