Space Partitioning

Course: CS350

Instructor: Dr. Pushpak Karnick

Type: Solo project

Language: C++


The objective of this subject was to learn and understand multiple space partitioning techniques, used for both collision detection and graphics optimization. As part of the subject I programmed some of the techniques explained in class, here is the work I did:

Bounding Volume Hierarchy

This part consisted on computing the AABB and bounding Sphere for any mesh, the sphere computation was made using different approaches: centroid, Ritter’s boundign sphere and applying iterative refinement over the Ritters sphere to get a tighter result.

Constructed a Bounding Volume Hierarchy using different approaches, this could BVH can be used for the broad phase of a collision detection system. The construction modes I implemented are:

  • Bottom-Up: Merge the two BV that generate the smaller BV until we only have one BV left (the first BVs we take are the objects).

  • Top-Down: Compute the BV that contains all objects and then split it in two from the axis where the BV scale is bigger, I implemented three methods to determine where to split: object median, object mean and spatial meadian

Octree & BSPtree

Learning Outcomes

After the completion of this course, I understand the theory behind the different spatial data structures, culling methods, and spatial algorithms. I written various intersection functions and spatial partitioning algorithms in a provided framework.

© 2020 By Wonjae Jung