**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.

## Leave a Reply