Bounding Volume Hierarchy


The only collision occurs in a4 and b5.
Suppose there is no false positive, the minimum number of tests will be 9.

  1. check a0 against b0 - found that a0 and b0 overlaps
  2. check a1 a2 against b1 b2, which is 2x2 = 4 tests- found that only a1 and b2 overlaps
  3. check a3, a4 against b5 b6, which is 2x2 = 4 tests - found that only a4 and b5 overlaps
    in total is 1 + 4 + 4 = 9

Suppose false positive in all bounding volumes, the minimum number of tests will be 29.

  1. check a0 against b0 - found that a0 and b0 overlaps
  2. check a1 a2 against b1 b2, which is 2x2 = 4 tests- found that they all overlap with each other
  3. check a3, a4 a5 a6 against b3 b4 b5 b6, which is 4x4 = 16 tests - found that only a4 and b5 overlaps in node level, and a3 a4 a5 a6 overlaps with b4
  4. check a3 a4 a5 a6 against b7 b8, which is 4 x 2 = 8 tests - found no overlaps
    in total is 1 + 4 + 16 + 8 = 29