top of page
SPACE PARTITIONING
Class
CS350
Instructor
Eder Beldad
Languages
C++ and OpenGL
About
In this class, we learned how acceleration structures and optimizations for graphics work, so we created a framework to implement these structures and to implement the collision detection algorithm GJK. The implemented structures were Bounding Volume Hierarchy, Octrees, and KD Trees.
Bounding Volume Hierarchy
For this structure, we developed three approaches that vary according to how the bounding volumes of the objects of the scenes are analyzed, the approaches are top-down, bottom-up and insertion.
​
Octrees
For making the Octrees implementation as fast as possible, we used bitfields to analyze which were the children of each node that were activated. Also, we combined the Octree with the usage of frustum culling to make it even faster.
KD Trees
Being KD Trees one of the most used structures for Raytracing, we had to implement one to be able to perform ray-casting against the triangles of the objects in a scene in a very fast way.
GJK
In physics simulation, one of the hardest challenges is to be able to compute complex polygons collisions cheaply. Gilbert-Johnson-Kerti collision detection algorithm takes advantage of the Voronoi Region to compute them without expensive computational cost.
bottom of page