Space Partitioning

CS350: Spatial Data Structures and Algorithms

Instructor: Jorge Usabiaga

Framework: C++ custom engine

The course covered the efficient representation and processing of complex 3D scenes in order to improve CPU &GPU throughput. Topics included spatial data structures (static: K-Dimensional (KD) Tree, Binary Space Partition-ing Tree, Dynamic: Hierarchical Bounding Volume (AABB) Tree), object-culling methods (occlusion and portal)and spatial intersection algorithms (Gilbert-Johnson-Keerthi (GJK) and Minkowski Portal Refinement (MPR)).

Bounding Volumes:

Compute the bounding volumes of moving, rotating and scaling objects.


Bounding Volumes Hierarchy:

Tree structure drawing the bounding volumes from the different depths.



Showing all the octree level, and testing collision against a dynamic object. I draw the nodes of the octree that are colliding with the dinamic objects, also the aabb of the objects if they are also colliding.



Showing all the depths subdivision.


Collision Detection System and Separation Axis Theorem:

Collision detection system with a broad, middle and narrow phase components. Being the narrow test the separation axis theorem.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s