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.

 

Octree:

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.

 

Kdtree:

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.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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