570 Final Project
Christopher Patton
Edgar's Octree
Prerequisites
All objects in the game with a physical representation are called Entities. A specific implementation of Entity is the CollidableEntity, which contains a BoundingRegion.
See: collidable_entity.h,Bounding Regions
A BoundingRegion is an abstract base class for different types of (you guessed it) bounding regions. Currently, we have SphericalBoundingRegion's and AxisAlignedBoundingRegion's
See: bounding_region.h, spherical_bounding_region.h, axis_aligned_bounding_region.hCollision Detection
To asses the collision of different BoundingRegion's, we have a collision library that handles different permutations of BoundingRegion derived classes. Utilizing dynamic casting, we determine which type of BoundingRegion's we are dealing with, and call the appropriate collision function.
Assessing the intersection of spheres is trivial, and includes comparing the distance between their centers to the sum of the radii.
Spheres with axis aligned boxes is also trivial: check that the center of the sphere is between the minimum and maximum points of the axis aligned box, or within the radius of them.
Colliding axis aligned boxes is slightly more complicated, and involves performing the same sphere and axis-aligned check, but with the eight points that compose the second box instead of the center of the sphere.
See: collision.h, collision.ccOctree
To reduce the number of collisions that need to be assessed per update, we utilize a spatial hierarchy (specifically, an octree). This separates the game world recursively into eighths such that the number of entities compared for collision are logarithmically reduced (assuming a relatively uniform distribution of entities).
We enforce a maximum number of entities per section in the octree prior to a subdivision operation to prevent the leaf nodes of the tree from becoming overpopulated. We also enforce a maximum depth to prevent degenerate trees (better to have overpopulated leaves than excessive recursion).
Each node in the octree represents a section of space, and can be represented by an AxisAlignedBoundingRegion. To find if a CollidableEntity is contained by a node of the octree, we collide its BoundingRegion with the AxisAlignedBoundingRegion of the node.
The inner nodes contain eight child nodes that represent an eighth of the uniformly subdivided space of their parent. The leaf nodes of the octree contain a set of CollidableEntity's that reside in the space defined by the node.
Performing a collision check of any CollidableEntity with the contents of the octree happens as follows:
If this node is a leaf:
collide our subject with all entities in the node
return a set of the successful collisions
If this node is an inner node:
collide our subject with the bounding regions of the child nodes
for each of the child nodes that our subject collides with:
union the sets of returned collisions
return the union
Octrees do a great job of reducing the computation time of collision detection, especially over spaces with uniformly distributed entities. The difference can be seen in situations where the number of entities close to the player is significantly less than the number of entities in the game.
For example, beginning the game in realtive calm:
collidable entities
total: 34; local: 8
collidable entities
total: 34; local: 8
collidable entities
total: 34; local: 8
collidable entities
total: 34; local: 8
collidable entities
total: 34; local: 8
Versus navigating a shower of asteroids (which, for the life of me I could not catch on one frame):
collidable entities
total: 38; local: 12
collidable entities
total: 42; local: 16
collidable entities
total: 38; local: 12
collidable entities
total: 36; local: 10
collidable entities
total: 34; local: 8