Space Partitioning
The following is a collection of solo projects that I worked on during my time as a student at Digipen. These projects consisted on learning about different Space Partitioning techniques and how to implement them in game development to significantly increase performance on videogames.
These include:
Bounding Volumes
Bounding Volume Hierarchies
Gilbert-Johnson Keerthi (GJK) algorithm for convex collision
KD-Trees
These projects were created on a simple C++ engine created by me using OpenGL as a base to render and using ImGUI for menu functionalities.
Bounding Volumes
The idea behind this project was to learn how bounding volumes work, how to implement the different types of them on a C++ engine and understand their importance on improving performance.
The Blue cubes represent the tightest possible OBB for the model, which is used to calculate the Bounding Volumes represented in Red, as the distance between the center and its furthest point can be used as a radius for the area that the object will be covering on any rotation. This OBB is precomputed by considering the points on the object that are furthest from the center, which can be precomputed to increase performance.
On this project I implemented both AABB and Sphere shaped Bounding Volumes, implementing the following techniques:
AABB:
Isotropic AABBs
Rotation Dependant AABBs
Sphere:
Naive
Centroid
Ritter’s method
Iterative Ritter’s Method
Isotropic AABBs: they are not updated when the object is rotated but are a bit more inaccurate when it comes to collision checks
Rotation Dependant AABBs: They are much more accurate but a bit more computationally heavy since they have to be updated on rotation
Sphere Naive: Less computationally heavy
More accurate Spheres: Created using Centroid, Ritter and Iterative methods
Bounding Volume Hierarchies
With this project, alongside the previous one, I learned that Bounding Volumes are a very helpful optimization tool because they avoid convex vs convex collision computations by creating a layer of AABB vs AABB collisions (which are a lot less computationally heavy), making it so convex collisions are computed only when necessary. This is specially helpful on games which contain a big amount of objects on a big world where they will rarely collide.
Using Hierarchical Trees for Bounding Volumes also improve performance by avoiding unnecessary AABB vs AABB collisions, since objects are separated enough from one another could be avoided.
On this project, a Bounding Volume Hierarchy is being used in rendering, another good usage for it. Objects that are outside of the view frustum are not drawn and, thanks to the Hierarchy, many Frustum vs AABB calls are avoided, increasing FPS count.
These Hierarchies can be created using the following methods:
On Start:
Top Down
Bottom Up
Runtime Insertion of objects on tree
Gilbert-Johnson Keerthi algorithm on Convex vs Convex
On this proejct, I implemented the GJK algorithm using an optimized version of the Minkowski Difference to calculate a simplex that checks if the origin is inside it to perform the separating axis theorem for Convex vs Convex collision detection.
Kd-Trees
Kd-Trees are another optimization technique based on partitioning the space by dividing it in K dimensions. On each level of the tree, the space is partitioned on a different dimension. This technique can be used for collision detection such as Ray vs AABB, which can be used on gameplay for bullet collision and is also used often on raytracing.
On this project, I implemented a 3 dimensional tree that divides a model into different branches of the tree, avoiding Ray vs Triangle computations and partitioning on the 3 cartesian axis (X, Y, Z) depending of the level of the tree.