Space Partitioning

Course: CS350

Instructor: Jorge Usabiaga

Type: Solo project

Language: C++

Reference book:  Real-Time Collision Detection by Christer Ericson

Overview

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 Volumes

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.

 

Bounding Volume Hierarchy

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.
• Insertion: Insert all the objects one after an other. When an object moves, is taken out from the hierarchy and inserted again.

 

Octree

Built an octree by inserting the triangles of a 3D model.

 

KDTree using Surface Area Heuristic

Built a KDTree out of a 3D mesh, used Surface Area Heuristics to determine the best split plane position. I used this KDTree to optimize my Advanced Ray Tracer I did the semester after the one I took this subject.

 

Collision System

Programmed a three phase collision detection system and the Separating Axis Theorem to determine if two convex objects where colliding. These are the phases of the collision system:

• Broad Phase: Used an octree to drastically reduce collision checks.
• Medium Phase: AABB and Sphere bounding volume collision detection to determine f the objects could be colliding.
• Narrow Phase: Programmed the Separating Axis Theorem (SAT) to determine if two convex objects are colliding.

Legend:

• White: Objects discarded by the Broad Phase – by the octree.
• Green: Objects that arrived to the Middle Phase and where discarded in it – Spheres not colliding.
• Orange: Objects that arrived to the Narrow Phase and where discarded in it – SAT determined the shapes are not colliding (the plane is the separation plane obtained by the SAT)
• Red: Objects that are colliding.