Every operation on a mesh will simply loop through all of the triangles that make up the mesh and perform the requested operation on every triangle. With medium to large size meshes this becomes very expensive, very fast. Because of the expensive nature of these tests, we are going to add an optional acceleration structure to our Mesh object.
The optimization structure we are adding is a Bounding Volume Hierarchy (BVH), an Octree to be specific. First we will need to find an AABB that contains the entire mesh. Next, we will divide the box into eight sub-boxes. We assign each triangle of the mesh to one (or more) of the nine boxes it belongs to. We will recursively repeat this process:
Now that every triangle is inside an AABB, we can use this hierarchy to accelerate intersection testing. At the top level, we check if the intersection touches the AABB containing the box. Next, we check if the intersection touches any of the AABB's eight children. We recursively repeat this...
