Lecture 9: Ray Tracing & Acceleration Structures (49)
brandonlouie
Is the main difference between oct-tree and KD-tree that the former splits up spaces into equal partitions, and the later can split up spaces into variables size partitions?
lycorisradiatu
It seems like oct-tree divide the space based on the distribution of points. I wonder if it's true that the partitions of oct-tree are always equal in size.
MichaelYu15
how does the BSP-Tree extend to higher dimensions?
GarciaEricS
I'm wondering about how often BSP-Trees are used in practice. It seems to be that checking about what internal bounding box a ray lands in would be a pretty hefty calculation for the benefit we get compared to a KD-Tree, where it seems we can still basically segment the grid how we want.
omijimo
it seems like the BSP tree is used to minimize excess volume in each box while still partitioning based on the number of objects, or perhaps it just splits the plane with the shortest possible line during each recursive call.
AnikethPrasad
Which tree is most commonly used in the industry? Is the computation required for BSP-Trees worth it for rendering dynamic scenes?
KD-trees are guaranteed to have log depth but their aspect ratio is unbounded compared to oct trees, meaning that the number of divisions at each level can vary a lot meaning you might have to examine an unbounded amount of cells.
Zackoon
Why would we use a BSP tree over the other two options? Is there a disadvantage in axis aligned splits? Additionally, does it matter whether we segment up a shape (like a circle in the oct tree) vs. not (like how the BSP tree doesn't break up any shapes)?
onionzn
Is it possible to apply different spatial partitioning methods to different parts of a scene based on the characteristics of the objects within the part? For example, apply uniform spatial partitioning to areas where objects are evenly distributed, while applying non-uniform partitioning to regions with more irregularities. I got the inspiration from the method of level sampling using mipmaps, where textels from different mipmap levels are mapped to screen pixels depending on a screen pixel's footprint in the texture. However, I feel that in the case of spatial partitioning, applying multiple partitioning methods to a single scene might make it difficult to store information efficiently though. For example, we may have to switch back and forth between the grids and spatial hierarchy data structures.
sparky-ed
Responding to Zackoon's response, I think the reason why a BSP tree would be used over the other two options is its flexibility in partitioning. Not like the other two options, it provides flexible splitting by using arbitrary planes which result in a partition closely tailored to the specific geometry in this case circles. Also, if we consider this in 3D space, it may be really efficient in terms of the area of the spatial partition. Therefore, it reduces the number of polygons that need to be rendered.
anavmehta12
Based on my understanding a oct-tree in 3d would split into octants or box looking shapes and bsp-tree would use planes in 3D to partition the objects.
brandogn
How would we implement a BSP-Tree? It seems like the partitions are separated by some line (or maybe a hyper plane in more dimensions), and they don't seem to be aligned with an axis. Would it be defined by a line equation, and would that make it more inefficient since we now have to do a little bit of extra work to calculate intersections?
Is the main difference between oct-tree and KD-tree that the former splits up spaces into equal partitions, and the later can split up spaces into variables size partitions?
It seems like oct-tree divide the space based on the distribution of points. I wonder if it's true that the partitions of oct-tree are always equal in size.
how does the BSP-Tree extend to higher dimensions?
I'm wondering about how often BSP-Trees are used in practice. It seems to be that checking about what internal bounding box a ray lands in would be a pretty hefty calculation for the benefit we get compared to a KD-Tree, where it seems we can still basically segment the grid how we want.
it seems like the BSP tree is used to minimize excess volume in each box while still partitioning based on the number of objects, or perhaps it just splits the plane with the shortest possible line during each recursive call.
Which tree is most commonly used in the industry? Is the computation required for BSP-Trees worth it for rendering dynamic scenes?
https://cstheory.stackexchange.com/questions/8470/why-would-one-ever-use-an-octree-over-a-kd-tree
KD-trees are guaranteed to have log depth but their aspect ratio is unbounded compared to oct trees, meaning that the number of divisions at each level can vary a lot meaning you might have to examine an unbounded amount of cells.
Why would we use a BSP tree over the other two options? Is there a disadvantage in axis aligned splits? Additionally, does it matter whether we segment up a shape (like a circle in the oct tree) vs. not (like how the BSP tree doesn't break up any shapes)?
Is it possible to apply different spatial partitioning methods to different parts of a scene based on the characteristics of the objects within the part? For example, apply uniform spatial partitioning to areas where objects are evenly distributed, while applying non-uniform partitioning to regions with more irregularities. I got the inspiration from the method of level sampling using mipmaps, where textels from different mipmap levels are mapped to screen pixels depending on a screen pixel's footprint in the texture. However, I feel that in the case of spatial partitioning, applying multiple partitioning methods to a single scene might make it difficult to store information efficiently though. For example, we may have to switch back and forth between the grids and spatial hierarchy data structures.
Responding to Zackoon's response, I think the reason why a BSP tree would be used over the other two options is its flexibility in partitioning. Not like the other two options, it provides flexible splitting by using arbitrary planes which result in a partition closely tailored to the specific geometry in this case circles. Also, if we consider this in 3D space, it may be really efficient in terms of the area of the spatial partition. Therefore, it reduces the number of polygons that need to be rendered.
Based on my understanding a oct-tree in 3d would split into octants or box looking shapes and bsp-tree would use planes in 3D to partition the objects.
How would we implement a BSP-Tree? It seems like the partitions are separated by some line (or maybe a hyper plane in more dimensions), and they don't seem to be aligned with an axis. Would it be defined by a line equation, and would that make it more inefficient since we now have to do a little bit of extra work to calculate intersections?