2D Collision Broad-Phase: Spatial Partitioning Fundamentals Quiz

Test your understanding of 2D collision broad-phase detection using spatial partitioning methods like uniform grids, quadtrees, and spatial hashing. This quiz covers hash-bucket lookups, time and memory trade-offs, and key concepts behind efficient collision detection for interactive applications.

1. Purpose of Broad-Phase Collision Detection

   What is the main purpose of broad-phase collision detection in a 2D environment?

   1. To render all moving objects on the screen simultaneously
   2. To quickly reduce the number of object pairs that need to be checked for collisions
   3. To guarantee collision responses between all pairs
   4. To store the exact positions of all objects in memory

   Explanation: Broad-phase collision detection works to filter out object pairs that are definitely not colliding, greatly reducing the computational load before more expensive narrow-phase checks. Rendering objects is unrelated to the collision detection process. Storing all positions does not facilitate efficient collision checking. It does not guarantee all collisions are handled, but narrows candidates for more precise detection.

2. Spatial Partitioning Techniques

   Which of the following is a commonly used spatial partitioning technique for 2D broad-phase collision detection?

   1. Bucket filling
   2. Merge sorting
   3. Hash chains
   4. Quadtrees

   Explanation: Quadtrees are a popular spatial partitioning structure that recursively divides space into four quadrants, fitting well with 2D environments. Hash chains are used in some hashing algorithms but not exclusively for spatial partitioning. Merge sorting is a general sorting method. Bucket filling is not a spatial partitioning technique; while buckets are related, the term is incorrect in this context.

3. Uniform Grid Approach

   How does a uniform grid help speed up broad-phase collision checks among many objects?

   1. By sorting objects based on their velocities
   2. By grouping nearby objects into cells and only checking objects within the same or adjacent cells
   3. By grouping objects by their color attributes
   4. By checking collisions for every possible pair in the scene

   Explanation: Uniform grids partition space into cells, so only objects in relevant cells need to be checked for potential collisions, optimizing time complexity. Sorting by velocity does not group spatially nearby objects. Checking every pair is computationally expensive and defeats the purpose. Color attributes are irrelevant to spatial collision checks.

4. Spatial Hashing Basics

   In spatial hashing for 2D collision detection, how are objects typically assigned to hash buckets?

   1. By sorting objects alphabetically by name
   2. By assigning each object a random bucket
   3. By calculating the object's mass and density
   4. By using their spatial coordinates to compute a hash function determining the bucket

   Explanation: Spatial hashes use an object's position to assign it to a hash bucket, which organizes objects based on their spatial locations. Mass and density do not help in spatial assignment. Random assignment would defeat the spatial grouping purpose. Sorting alphabetically is unrelated to spatial partitioning techniques.

5. Quadtree Subdivision Trigger

   What typically triggers a quadtree to subdivide a node in 2D collision detection?

   1. When the application is paused
   2. When the node contains more objects than a predefined threshold
   3. When there are no objects in the node
   4. When objects become larger in size

   Explanation: A quadtree subdivides a node when it becomes crowded, exceeding a set object count, to maintain efficient collision checks. Larger object sizes alone do not require subdivision. Addressing empty nodes is unnecessary. Application state, like pausing, doesn't affect quadtree structure directly.

6. Memory Usage Comparison

   Which spatial partitioning technique can potentially use more memory in sparsely populated 2D spaces: uniform grid or quadtree?

   1. Quadtree
   2. Both always use the same memory
   3. None, both use zero memory
   4. Uniform grid

   Explanation: Uniform grids allocate memory for all cells regardless of object presence, which can waste memory in sparse environments. Quadtrees dynamically allocate memory where objects exist, saving space in empty regions. It's inaccurate to say both always use the same or zero memory, as their allocation depends on the method and data.

7. Trade-Off Between Time and Memory

   Why is there a trade-off between time and memory in 2D spatial partitioning for collision detection?

   1. Reducing collision checks with finer partitions uses more memory to store extra cells or nodes
   2. Increasing cell resolution never affects computational time
   3. You can have unlimited memory without any impact
   4. Using less memory always leads to faster computations

   Explanation: Finer partitions create more cells or nodes, reducing redundant checks but increasing memory usage. Less memory does not always equal faster performance; it may lead to more time spent in collision checks. Higher cell resolution can indeed affect computational time. Unlimited memory is not realistic in practice.

8. Spatial Hash Bucket Limitations

   What is a potential limitation of using hash buckets in spatial hashing for 2D collision detection?

   1. All objects are always stored in a single bucket
   2. Spatial hashes work only with circular objects
   3. Objects near hash bucket boundaries may get separated into different buckets and miss collision checks
   4. Hash buckets always eliminate all false positives

   Explanation: Spatial hashing can cause boundary objects to be split across buckets, possibly missing collisions unless overlap or neighbor checks are considered. Hash buckets do not eliminate all false positives; candidates may still require verification. Objects are rarely all in one bucket unless data is highly clustered. Shape restrictions do not limit spatial hashing.

9. Choosing Cell Size for Uniform Grid

   Why is it important to choose an appropriate cell size when using a uniform grid in 2D collision detection?

   1. Cell size affects the object's color representation
   2. Cell size has no effect on performance or accuracy
   3. Cell size is only important for narrow-phase collision detection
   4. Too large cells can increase unnecessary collision checks, while too small cells increase memory usage and overhead

   Explanation: Cell size directly impacts performance: large cells lead to more collisions checked per cell (false positives), while small cells increase memory and management overhead. Cell size does not influence color. It is relevant for broad-phase, not just narrow-phase. Saying cell size has no effect is incorrect.

10. Broad-Phase Complexity Reduction

    How does effective spatial partitioning affect the computational complexity of broad-phase collision detection compared to checking all object pairs?

    1. It guarantees collision detection in constant O(1) time
    2. It makes the process slower overall
    3. It reduces the average complexity from O(n^2) to approximately O(n)
    4. It increases complexity to O(n^3)

    Explanation: Spatial partitioning methods like grids and quadtrees help avoid checking every pair, lowering average-case complexity from quadratic to near-linear time. Complexity is not increased to cubic, and partitioning generally makes the process faster. Guaranteed constant time per collision check is an unrealistic expectation for spatial partitioning.