To do collision detection efficiently, primitives which are certainly not colliding must be identified as soon as possible and discarded from consideration to avoid wasting time. To do this, some form of spatial subdivision scheme is essential, to avoid a brute force test of O [ n 2 ] primitive collisions. Approaches used include: