# Space Partitioning

* Everything I did for this course was done from scratch

## Bounding Volumes

The goal of this assignment was to compute the BV that fits any 3D model the user will import.

In this video you can see:

• AABB (axis-aligned bounding box) and BS (bounding sphere) bounding volumes.
• BS computed using centroid, ritter or iterative computation method.
• How this works for different shapes.

## Bounding Volume Hierarchy

In this assignment we had to use the previously implemented BVs to construct a hierarchical tree that will contain the objects in the scene.

In this video you can see:

• The whole tree at once.
• The levels of the trees one by one.
• How the tree updates on runtime when objects move.
• Difference when constructing the tree with different methods (top-bottom, bottom-up and insertion).

## Octree / K-d Tree

Once we understood the most basic hierarchical tree, we moved to more complex space partitioning trees. We started with the octrees, where each internal node has exactly eight children, this is, each level gets subdivided eight times.

In the video you can see:

• The levels of the tree one by one.
• The whole tree at once.

We also had the chance to implement a K-d tree, where the level is divided along the axis with the widest spread through the middle of the points contained in it.

In the video you can see:

• The levels of the tree one by one.

## Collisions

Doesn’t make much sense having the knowledge and ability to divide the space if you are not giving a usage to it. For solving this problem, our last assignment was about implementing an optimized collision detection system by using the space-partition tree of our choice, which in my case is a octree.

In the video you can see:

• How the octree gets updated on runtime when position of objects changes.
• The phases when two BVs collide (orange) and when two shapes collide (red).