Difference between BVH and Octree/K-d trees

Question

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?

Answer 1

Well I researched quite a lot after that and this paper helped a lot.

"Space Subdivision algorithms" by Macdonald 1988.

So just summing what I understood. Some of them are obvious reasons but after reading the paper make much more sense and I'll try to do the same here.

1) In BVH we are subdividing objects into smaller pieces. So for example a model of dragon consisting of thousands of triangles, We first start with a Bounding Volume covering the whole dragon. Then we subdivide again and again until our conditions are met. In BVHs, the leafnodes usually have 1 object in contrast to octrees which can have many. However this isn't clear whether it's referring to an object (sphere) or a single triangle since spheres can contain hundreds of triangles if triangulated. Here is a picture explaining BVH.

In contrast, Octrees/K-d trees and other space subdivision, divide the space recursively. A simple picture of an octree given in the paper.

2) The above pictures show another difference. That is, in Space subdivisions we have disjoint sets of space regions or voxels or cells whatever you wanna call them. In contrast, BVHs have disjoint sets of objects.

This means in octrees one object may be assigned to more than 1 voxel. And thus we may have to check for that object again and again though this can be avoided using techniques like mailboxing etc. In BVHs, however, this isn't the case as an object may be inside only 1 bounding volume at a time, thus it may be checked for intersection only once which is when the ray intersects the bounding volume it's currently in.

3) The other difference the paper mentions is that in Space subdivision traversal algorithms usually calculate the exit point of the ray from the current intersected child node and calculate a new point just past this exit point and from this information the next child node is found. The benefit of this is that traversal may stop as soon as it hits an object.

On the other hand, BVHs can't do this since in BVHs we may have object overlapping in nodes. In this case we will have to maintain a list of the intersected objects and find which is the closest one. A good example of this is given in "Raytracing Complex Scenes by Kajiya"

As we can see although the ray first intersects the upper BV, the closest object hit is actually inside the lower BV which the upper one has no information of unlike space subdivision structures.

And now on to the part of how I implemented the structure, it seems what Kajiya suggested was to use the octree scheme to define a traversing algorithm for the BVH. In the end when I recalculated the bounding volumes of each cells, this relaxed many voxels boundaries causing several to overlap. After this operation the structure didn't resemble "Disjoint sets of spaces" rather it resembled "disjoint sets of objects" hence it's essentially a BVH.

Do note that this operation may sound like somewhat an efficient optimization to the space subdivision structure, that is relaxing the bounds of voxels to avoid having all the voxels keep track of the object that overlaps them. This way we assign 1 object to 1 voxel and relax it bounds.

But doing so we lose the traversing efficiency of space subdivision structure where we could have stopped after intersecting only 1 object. Other pros may also have been lost. That's what I have understood so far.

If anybody would like to add some more feel free to do so.