Space Partitioning

About the projects

The following projects were solo projects made for the course CS350 at DigiPen using C++ with an engine made from scratch.

 

Bounding Volumes

The objective for this project was to compute the AABB and Bounding Sphere for any mesh. For computing the Bounding Sphere, three different methods where used: Centroid method, Ritter’s Bounding Sphere and Ritter Iterative Refinement Sphere (which gives a tighter result than Ritter)

 

Bounding Volume Hierarchy

The objective for this project was to construct a Bounding Volume Hierarchy using different approaches:

  • Top-Down: First we compute the BV that contains all objects. Then, recursively split it in half from the axis where the BV scale is bigger.
  • Bottom-Up: Starting from the BV of the objects, we merge the two BV that generate the smaller BV until we only have one BV left.
  • Insertion: Insert all the objects one after the other in the leaf with less insertion cost (less volume change)

When an object moves, is taken out from the hierarchy and inserted again.

 

Octree

The objective for this project was to build an octree by inserting the triangles of a 3D model and perform frustum culling.

 

KDTree using Surface Area Heuristic

The objective for this project was to build a KDTree out of a 3D mesh by using Surface Area Heuristics to determine the best split plane position.

 

Collision System

The objective for this project was to create a three-phase collision detection system to determine if two convex objects where colliding:

  1. Broad Phase: Check with the octree to discard most of the objects pairs.
  2. Medium Phase: Perform AABB vs AABB collision detection test to determine if the pair of objects could be colliding.
  3. Narrow Phase: Perform Separating Axis Theorem (SAT) test to determine if the pair of convex objects is colliding.

Whenever a phase cannot determine if a pair of objects are colliding or not, the pair is moved to the next phase.

Video Legend:

  • White/Grey: Objects discarded in the Broad Phase.
  • Green: Objects discarded in the Middle Phase.
  • Orange: Objects discarded in the Narrow Phase. The plane drawn is the separation plane obtained by the SAT.
  • Red: Objects that are colliding.