Collision Detection

Ray Tracing:
- Advantages:
  - Fast and simple to implement.
- Disadvantages:
  - Not accurate (approximations only).
- When to Use:
  - Useful for approximate collision detection in large-scale scenarios.
Bounding Volume Hierarchies (BVH):
- Advantages:
  - More accurate as it allows precise collision detection.
  - Can handle complex geometries by testing intersections at finer levels (e.g., triangle-triangle).
- Disadvantages:
  - Slower than ray tracing.
- Use Case:
  - For scenarios requiring high precision.
Efficient Collision Detection for Many Objects:
- Techniques to handle hundreds of objects efficiently, avoiding ( O(n^2) ) complexity.

How It Works:
- BVH organizes geometry hierarchically using bounding volumes like:
  - AABBs (Axis-Aligned Bounding Boxes).
  - OBBs (Oriented Bounding Boxes).
  - Spheres.
  - k-DOPs (Discrete Oriented Polytopes).
- Each node in the hierarchy contains a bounding volume:
  - Leaves: Contain geometry (e.g., triangles).
  - Internal Nodes: Contain bounding volumes that enclose all child nodes.
Building BVHs:
- Split Planes:
  - Use centroid positions or geometry properties to divide space recursively.
- Top-Down Construction:
  - Divide geometry into subsets and create bounding volumes for each subset.
Collision Detection Using BVH:
- For two BVHs:
  - Test if their bounding volumes overlap.
  - If they do, check child nodes recursively.
  - For leaf nodes, perform a precise test (e.g., triangle-triangle intersection).

Grid-Based Approach:
- Divide space into a grid.
- Store objects in cells they intersect.
- Test only objects in cells with multiple entries using BVH or other exact methods.
Sweep-and-Prune Algorithm:
- Purpose:
  - Efficiently identify potentially colliding pairs by reducing dimensionality.
- Steps:
  1. Treat each axis (x, y, z) separately.
  2. Represent each object’s bounding volume as an interval on the axis.
  3. Sort the intervals.
  4. Traverse the sorted list, maintaining an active interval list:
    - Add intervals when they start (b).
    - Remove intervals when they end (e).
    - Overlapping intervals in the active list indicate potential collisions.
- Optimization:
  - Exploit frame-to-frame coherence (objects do not move much between frames):
    - Use simpler sorting algorithms (e.g., bubble sort) for small changes.

Bounding Volume Selection:
- Tighter Bounds (e.g., OBBs, k-DOPs):
  - Fewer false positives but slower intersection tests.
- Looser Bounds (e.g., AABBs, spheres):
  - Faster intersection tests but may result in more false positives.
Complexity:
- Testing ( n ) moving objects against ( m ) static objects requires ( O(n \times m) ) tests.
- Smart techniques like grids or sweep-and-prune reduce this complexity.

BVH/BVH Test Pseudocode:
- Handles four cases:
  1. Leaf vs. Leaf.
  2. Internal Node vs. Internal Node.
  3. Internal Node vs. Leaf.
  4. Leaf vs. Internal Node.
- Stops when the first collision is found.
- Can be modified to find all colliding pairs by collecting results in a list.
Efficient Pair Updates:
- Maintain a list of colliding pairs using flags:
  - Flip a flag when the overlap status changes (e.g., during sorting).

Choosing a Method:
- For fast but approximate detection: Use ray tracing.
- For precise detection: Use BVH or grid-based methods.
- For handling many objects efficiently: Use grids or sweep-and-prune.

Three Algorithms:
- Ray tracing: Fast, approximate.
- BVH: Precise, slower.
- Efficient methods for many objects: Grid-based, sweep-and-prune.
Bounding Volumes:
- Understand AABBs, OBBs, spheres, and k-DOPs.
Efficient Pruning:
- Use grids to group objects spatially and test groups with finer methods.

Jonas Notes