Home › For broad-phase collision, SWEEP-AND-PRUNE (a.k.…
For broad-phase collision, SWEEP-AND-PRUNE (a.k.a. sort-and-sweep) achieves average performance close to which order on N objects?
AO(N log² N) regardless of scene
BO(N + k) for k overlapping pairs
CO(N²) tests every frame always
DO(N!) for the worst case always
Answer & Solution
Correct answer: B. O(N + k) for k overlapping pairs
Ericson Ch. 7: sort projection intervals each axis; sweep; coherent across frames (objects don't move much). Output sensitive in number of overlapping pairs k.
Related questions
Per Ericson + Catto, COULOMB FRICTION at a contact is typically modelled with friction forPer Erin Catto (Box2D), CONSTRAINT-BASED simulation solves contacts and joints using whichPer Ericson Ch. 6 + Erin Catto, CONTINUOUS COLLISION DETECTION (CCD) addresses which problPer Glenn Fiedler 'Fix Your Timestep!', the recommended technique for stable physics indepPer Glenn Fiedler 'Integration Basics', the integration scheme used in Jakobsen's CLOTH SIPer Glenn Fiedler 'Integration Basics' (gafferongames.com), SEMI-IMPLICIT EULER (a.k.a. syPer Ericson Ch. 9.5, after GJK detects intersection, EPA (Expanding Polytope Algorithm) isPer Ericson Ch. 9, the GJK algorithm finds collision between two CONVEX shapes by which it