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 |
|
{ |
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 */ |
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 */ |
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 |
|
{ |
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); |
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]; |
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, |
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 |
|
|