The idea is to move two or more 3D object towards each other until they collide. For the collision detection, sphere-octree will be used. The octree for each object will be created when the program begins and will be used for the collision detection. As soon as two objects collide, they will stop moving and the colliding sphere will be displayed.
When creating a sphere-octree node, it receives a bounding box and then creates a bounding sphere which includes all faces that are part of the bounding box. In this program, a face can be part of more bounding boxes when the different points are located in different bounding boxes. The sphere is defined by an origin point and a radius. The origin is with respect to the objects origin, so the translation can be added to the matrix-stack of the object. Also, each octree-node has up to eight child nodes. The sphere of the node contains all child nodes, so the child nodes are more precise.
For finding a bounding sphere, there are different approaches. This program uses Ritters algorithm. There are other algorithms which give better results yet have a longer runtime. When creating the child nodes, the nodes bounding box gets split into eight similar bounding boxes. Each of them is used to create one child node. For runtimes, see below.
After each movement of one or more objects, the collision detection is executed. Therefore, the parent-nodes of each objects are checked for a collision by using the spheres. If two spheres collide, all their child-nodes are checked for collision. Only when two or more leaf-nodes collide, it is assumed that the objects collide. Since the octrees are created at the start and the collision detection itself only has to check if the distance between two points is smaller than the sum of their radians, the collision detection only needs 1-3 milliseconds.
For the objects, a blinn-phong shader is used where the light is at the camera position. For displaying the colliding spheres, a grid-texture is used and only the grid itself is displayed. Beside the grid-texture, a silhouette-shader is used. If all spheres on a level are displayed, this sphere use a alpha-blending shader for transparency.
The deepness of the octrees can be modified as well as the number of objects in the world. The objects are stored in a vector and are all checked for collision with each other. The only limitation is the computer processing power.
As mentioned before, there are different algorithms for finding a bounding sphere for a given set of faces. I chose Ritters algorithm, because it is fast compared to the other algorithms. The disadvantage is that the bounding spheres are often not optimal. The collision detection with three or more objects is substantially better than with bounding boxes.
