So I'm currently reading up on acceleration data structures and so far I've heard there are 2 main schemes. Object Subdivision and Spatial Subdivision.
The Bounding Volume Hierarchy belongs to the Object Subdivision approach and K-d/Octree belong to the latter. However I'm having trouble distinguishing the two of them as both of them seem almost the same.
I had implemented a data structure before for my GPU raytracer which I thought was an Octree but I am not sure anymore. This was according to the paper "Ray tracing Complex Scenes" by Kajiya. I'm gonna quote him directly.
We could spend additional computer time to construct a better hierarchy. A median-cut scheme will help group near objects together even if they aren't modeled coherently.
The previous algorithm attempts to group objects based on their nearness to each other, but it does so along one dimension at a time. It might do better to group objects in along three dimensions at once by employing an octree. This preprocessing step would be very similar to the one described in [Glassner 84] or [Kaplan 85]. The difference is that, if an object straddles two or more octree cells, it is arbitrarily placed in exactly one of them. Furthermore, after the preprocessing is completed, the octree is used solely to define the hierarchy; each object must still be assigned a distinct bounding volume.
So I constructed this structure the same way. First I made an Octree, I inserted spheres into the cells if their center was in that cell. Every time I checked if the leaf nodes consisted of more than 2 spheres. If it did, I had to subdivide the cells again. After the octree was completed, I looped over all the compartments and resized them w.r.t the minimum
x,y,z and the maximum
x,y,z of the objects it had. This was done to avoid the case where some portion of a sphere would be outside the cell it's currently in (due to it's center lying in that cell).
Now according to the paper the above structure is a BVH? But I'm thinking its an octree? What's the difference?
2) Secondly, so far I have only inserted spheres. What's the case with triangles? What should be the maximum threshold for leaf nodes after which I should subdivide i.e. The number of traingles?