Lecture 9: Ray Tracing & Acceleration Structures (65)
euhan123
I didn't realize that we could also partition objects even if their bounding boxes are overlapping. I imagined that bounding boxes were it and we had to carefully choose our boundaries in order to split different objects into different partitions.
lycorisradiatu
I wonder when I would prefer spatial partitions over object partitions and what about the other way around.
srikartalluri
I think these sorts of partitioning can have multiple applications. Especially object partitioning looks very similar to the way autonomous driving vehicles bound and classify groups of any objects that they parse. This is in contrast to spatial partitioning which a video game might use to render/ ray trace objects only in our pov, which is a box.
omijimo
would it be possible to pre-process or partition the objects in some sort of way to determine the best partitioning method? for example, where the objects are sparse, use spatial partitioning, but where the objects are dense, use object partitioning
emily-xiao
Which method is typically used in industry / what situations would usually prefer the use of one over the other? The end of the slides covers calculating hierarchy speed but not the tradeoffs of these two strategies.
muuncakez
The key differences between spatial and object partition were hard to distinguish for me when first reviewing the lecture but I found this article to be really helpful as it provides examples while also breaking down how to think about the traversal method for both partitions
https://computergraphics.stackexchange.com/questions/7828/difference-between-bvh-and-octree-k-d-trees
AnikethPrasad
@euhan123 I think having overlapping bounding boxes could be more beneficial. For example, spatial queries and collision detection could be more accurate if objects could be in multiple partitions.
maldenz
I think KD-tree is preferred when dealing with a large number of static objects or scenes where objects are evenly distributed in space; BVH is preferred in scenes with moving or dynamic objects because BVHs are easier to update as objects move.
aishikbhattacharyya
I feel like a geographical application like Google Maps would find spatial partitioning useful because they would need to distinctify spaces even when objects can fall in multiple spaces. Object partitioning might be more useful for seperating stores in an outlet area. I'm a bit less sure about the second thought.
carolyn-wang
Looking into this further, it seems like some applications for spatial partitioning beyond optimizing rendering include (1) collision detection to quickly identify potential collisions by only checking nearby partitions' object, (2) physics simulations with localized computations that segment space into manageable chunks, and (3) pathfinding where this can facilitate spatial queries to optimize navigation
DestinyLuong
This topic confused me at first but after coming back to this slide I found that spatial partitioning is basically dividing off the general area into parts and creating a tree that can share items between these sub-areas. Object partitioning is more about splitting the objects into layers, with the trees not being able to share these elements.
ayra-jafri
I'd like to add a few more advantages/disadvantages between using KD-trees and BVH. BVHs are typically more efficient to build compared to KD-trees, and are also less prone to numerical errors (see PBRT 7.3 for more information). As per this paper [1], BVH performs better for smaller and medium sized scenes, while KD-trees perform better on large scenes. This means BVH is better when dealing with less computationally powerful machines, such as phones. This paper from NVidia [2] presents a sort of combo between KD-trees and BVH, the Split-BVH (aka SBVH), which utilizes spatial splits when building BVH builds, and performs better than BVHs at the cost of simplicity.
It makes sense that one key to distinguishing KD-tree and BVH is to know if these triangles are intersecting. Take KD-tree, it essentially uses the idea of binary search. It should be ordered properly before the binary search, so overlapping essentially violates this condition.
s3kim2018
I notice that BVH has a bigger bounding box and KD tress will have duplicate triangle entries. I think a good heuristic in choosing when to use which is checking for intersecting/overlapping triangles. Larger bounding boxes mean we would have to sample more but if there are a lots of triangles (high density scene), duplicate triangles that we have to check for intersections could turn out to be more costly.
Zzz212zzZ
When the bounding boxes are overlapping, we just use a larger box that can contain these two boxes as a parent node. The BVH is partitioning based on the existing objects (i.e., triangles), all we need to do is find a bounding box that could relatively contain the object accurately.
I didn't realize that we could also partition objects even if their bounding boxes are overlapping. I imagined that bounding boxes were it and we had to carefully choose our boundaries in order to split different objects into different partitions.
I wonder when I would prefer spatial partitions over object partitions and what about the other way around.
I think these sorts of partitioning can have multiple applications. Especially object partitioning looks very similar to the way autonomous driving vehicles bound and classify groups of any objects that they parse. This is in contrast to spatial partitioning which a video game might use to render/ ray trace objects only in our pov, which is a box.
would it be possible to pre-process or partition the objects in some sort of way to determine the best partitioning method? for example, where the objects are sparse, use spatial partitioning, but where the objects are dense, use object partitioning
Which method is typically used in industry / what situations would usually prefer the use of one over the other? The end of the slides covers calculating hierarchy speed but not the tradeoffs of these two strategies.
The key differences between spatial and object partition were hard to distinguish for me when first reviewing the lecture but I found this article to be really helpful as it provides examples while also breaking down how to think about the traversal method for both partitions https://computergraphics.stackexchange.com/questions/7828/difference-between-bvh-and-octree-k-d-trees
@euhan123 I think having overlapping bounding boxes could be more beneficial. For example, spatial queries and collision detection could be more accurate if objects could be in multiple partitions.
I think KD-tree is preferred when dealing with a large number of static objects or scenes where objects are evenly distributed in space; BVH is preferred in scenes with moving or dynamic objects because BVHs are easier to update as objects move.
I feel like a geographical application like Google Maps would find spatial partitioning useful because they would need to distinctify spaces even when objects can fall in multiple spaces. Object partitioning might be more useful for seperating stores in an outlet area. I'm a bit less sure about the second thought.
Looking into this further, it seems like some applications for spatial partitioning beyond optimizing rendering include (1) collision detection to quickly identify potential collisions by only checking nearby partitions' object, (2) physics simulations with localized computations that segment space into manageable chunks, and (3) pathfinding where this can facilitate spatial queries to optimize navigation
This topic confused me at first but after coming back to this slide I found that spatial partitioning is basically dividing off the general area into parts and creating a tree that can share items between these sub-areas. Object partitioning is more about splitting the objects into layers, with the trees not being able to share these elements.
I'd like to add a few more advantages/disadvantages between using KD-trees and BVH. BVHs are typically more efficient to build compared to KD-trees, and are also less prone to numerical errors (see PBRT 7.3 for more information). As per this paper [1], BVH performs better for smaller and medium sized scenes, while KD-trees perform better on large scenes. This means BVH is better when dealing with less computationally powerful machines, such as phones. This paper from NVidia [2] presents a sort of combo between KD-trees and BVH, the Split-BVH (aka SBVH), which utilizes spatial splits when building BVH builds, and performs better than BVHs at the cost of simplicity.
[1] https://dcgi.fel.cvut.cz/home/havran/ARTICLES/sccg2014.pdf
[2] https://www.nvidia.in/docs/IO/77714/sbvh.pdf
It makes sense that one key to distinguishing KD-tree and BVH is to know if these triangles are intersecting. Take KD-tree, it essentially uses the idea of binary search. It should be ordered properly before the binary search, so overlapping essentially violates this condition.
I notice that BVH has a bigger bounding box and KD tress will have duplicate triangle entries. I think a good heuristic in choosing when to use which is checking for intersecting/overlapping triangles. Larger bounding boxes mean we would have to sample more but if there are a lots of triangles (high density scene), duplicate triangles that we have to check for intersections could turn out to be more costly.
When the bounding boxes are overlapping, we just use a larger box that can contain these two boxes as a parent node. The BVH is partitioning based on the existing objects (i.e., triangles), all we need to do is find a bounding box that could relatively contain the object accurately.