
404 Chapter 8 Collision Detection
Table 8.1 A comparison of times between projecting all vertices to compute a projection
interval and using a BSP tree for the query.
n BSP Time t
b
Project-All Time t
p
t
b
/ log nt
p
/n
4 2.141 0.812 1.0705 0.2030
8 3.922 1.547 1.3073 0.1933
16 5.422 2.563 1.3555 0.1601
32 5.937 4.328 1.1874 0.1352
64 6.922 7.765 1.1536 0.1213
128 7.922 14.391 1.1317 0.1124
256 9.281 27.359 1.1601 0.1068
512 10.250 53.859 1.1388 0.1051
1024 11.532 104.125 1.1532 0.1016
2048 12.797 210.765 1.1633 0.1029
A sample application to illustrate the queries is in the SampleMiscellaneous
folder, project ExtremalQuery. A convex polyhedron is displayed using ...