Space Partitioning

Subject: CS350

Instructor: Eder Beldad

Language: C++

Course Decription

This course deals with the efficient representation and processing of complex 3D scenes in order to avoid bottlenecks in the use of the CPU and the GPU. Specific topics include a variety of spatial data structures (binary space-partitioning trees, octrees, kd-trees, and grid data structures), several object-culling methods (occlusion, viewport, and portal), and finally the construction and uses of bounding volumes and their hierarchies for collision detection and related geometric operations.

Bounding Volume Hierarchies

For this project I implemented the Top-Down and Bottom-Up approach. Although BVH’s are not really considered spatial partitioning, these can be used for frustum culling, ray intersection or collision detection to increase performance and early discard entities.

Octree

I implemented a very efficient octree using bitwise operations and locational codes which can be used to speed up rendering by efficiently locating objects inside the camera frustum, for collision testing, ray tracing and voxels.

Kd Trees

I created a Kd Tree, which is a generalization for quadtrees and octrees.

Kd Trees are extremely useful for ray tracing and in this demo I perform a ray intersection against a high detailed mesh. This allowed me to see which triangle was hit by the ray extremely fast.

Gilbert-Johnson-Keerthi (GKJ)

Not a spatial partitioning algorithm, but one used to check if two convex polyhedra are intersecting with possibilities to reduce its time compexity to O(1) using time coherence.

In the demo it is possible to see two meshes intersecting, the minkowski difference and the simplex that is generated each step.