Space Partitioning

kdtree_dragon

Course: CS350

Instructor: Jorge Usabiaga

Type: Solo project

Language: C++

Reference book:  Real-Time Collision Detection by Christer Ericson

Overview

The objective of this subject was to learn and understand multiple space partitioning techniques, used for both collision detection and graphics optimization. As part of the subject I programmed some of the techniques explained in class, here is the work I did:

Bounding Volumes

This part consisted on computing the AABB and bounding Sphere for any mesh, the sphere computation was made using different approaches: centroid, Ritter’s boundign sphere and applying iterative refinement over the Ritters sphere to get a tighter result.

Bounding Volume Hierarchy

Constructed a Bounding Volume Hierarchy using different approaches, this could BVH can be used for the broad phase of a collision detection system. The construction modes I implemented are:

  • Bottom-Up: Merge the two BV that generate the smaller BV until we only have one BV left (the first BVs we take are the objects).
  • Top-Down: Compute the BV that contains all objects and then split it in two from the axis where the BV scale is bigger, I implemented three methods to determine where to split: object median, object mean and spatial meadian.
  • Insertion: Insert all the objects one after an other. When an object moves, is taken out from the hierarchy and inserted again.

Octree

Built an octree by inserting the triangles of a 3D model.

KDTree using Surface Area Heuristic

Built a KDTree out of a 3D mesh, used Surface Area Heuristics to determine the best split plane position. I used this KDTree to optimize my Advanced Ray Tracer I did the semester after the one I took this subject.

Collision System

Programmed a three phase collision detection system and the Separating Axis Theorem to determine if two convex objects where colliding. These are the phases of the collision system:

  • Broad Phase: Used an octree to drastically reduce collision checks.
  • Medium Phase: AABB and Sphere bounding volume collision detection to determine f the objects could be colliding.
  • Narrow Phase: Programmed the Separating Axis Theorem (SAT) to determine if two convex objects are colliding.

Video Legend:

  • White: Objects discarded by the Broad Phase, by the octree.
  • Green: Objects that arrived to the Middle Phase and where discarded in it, Sphere vs Sphere returned false.
  • Orange: Objects that arrived to the Narrow Phase and where discarded in it, SAT returned false. The plane is the separation plane obtained by the SAT.
  • Red: Objects that are colliding.

 

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Create a website or blog at WordPress.com

Up ↑