Jonas Notes

Spatial Data Structures and Speed-up Techniques

3 min read

1. Bounding Volume Hierarchies (BVHs)

  • Purpose: Organize geometry into hierarchies to speed up processing for:

    • Real-time rendering.
    • Intersection testing.
    • Collision detection.
    • Ray tracing and global illumination.

  • Bounding Volumes:

    • Axis-Aligned Bounding Boxes (AABBs): Simplest and widely used.
    • Oriented Bounding Boxes (OBBs): Handle rotated objects.
    • Spheres: Efficient for testing, though not as tight as boxes.

  • Tree Structure:

    • Internal nodes hold bounding volumes that encompass child nodes.
    • Leaves contain the actual geometry.

  • Construction Methods:

    • Top-down:
      • Split along the longest axis of a bounding box.
      • Recursively subdivide until minimal bounding boxes are achieved.
    • Bottom-up:
      • Group objects hierarchically into bounding volumes.

2. Binary Space Partitioning (BSP) Trees

  • Types:

    • Axis-aligned BSP:
      • Splitting planes are aligned with x, y, or z axes.
    • Polygon-aligned BSP:
      • Splitting planes align with object geometry for exact sorting.

  • Structure:

    • Internal nodes store splitting planes.
    • Leaves contain geometry for rendering.

  • Advantages:

    • Enables sorting geometry for back-to-front or front-to-back rendering efficiently.
      • To sort front to back, we recurse on the “hither” side first wrt to the camera before the farther side
    • Polygon-aligned BSP trees provide exact sorting.
  • Difference between BSP and BVH:
    • Objects can be part of multiple leaf nodes in BSP but in BVH an object can only be part of one leaf node

3. Octrees and Quadtrees

  • Octrees:

    • Divide 3D space into eight equally sized regions at each level.
    • Useful for:
      • Ray tracing.
      • Picking objects.
      • View frustum culling.

  • Quadtrees:

    • 2D counterpart of octrees, dividing space into four regions.

  • Sparse Voxel Octrees (SVOs):

    • Represent 3D spaces efficiently using voxel grids.
    • Store data hierarchically to reduce memory usage.

4. Culling Techniques

  • View Frustum Culling (VFC):

    • Use a bounding volume (e.g., sphere or box) to test if an object is outside the camera’s view frustum.
    • If the bounding volume is outside, skip rendering its contents.

  • Portal Culling:

    • Divide the scene into cells connected by portals (e.g., doors).
    • Recursively cull objects through visible portals to refine the view frustum.

  • Occlusion Culling:

    • Skip rendering objects completely blocked by others.
    • Often implemented with occlusion queries in OpenGL.

  • Backface Culling:

    • Skip rendering faces not visible to the camera.
    • Define front and back faces using counterclockwise vertex winding.

5. Level-of-Detail (LOD) Rendering

  • Purpose:

    • Reduce rendering complexity by using simpler models for objects farther away.
    • Close objects use detailed models, while far objects use simplified ones or are culled entirely.

  • Implementation:

    • Determine LOD based on the projected area of the object’s bounding volume.

6. Key Structures and Sorting

  • BVH Sorting:

    • AABB trees (e.g., NVIDIA RTX chips use these).
    • Efficient traversal for ray tracing and rendering.

  • BSP Tree Sorting:

    • Exact sorting for polygon-aligned trees.
    • Front-to-back sorting minimizes overdraw, improving performance.

What You Need to Know

  1. How BVHs are constructed and used.
  2. Top-down construction of BVHs and BSP trees.
  3. Sorting and construction differences between axis-aligned BSP and polygon-aligned BSP.
  4. Octree/quadtree structures and their applications.
  5. Different culling techniques:
    • View Frustum Culling.
    • Portal Culling.
    • Detail Culling (LOD).
    • Backface Culling.
    • Occlusion Culling.
  6. What Level-of-Detail (LOD) rendering is and how it is applied.