Lecture 9: Intro to Ray-Tracing & Accelerating Ray-Scene Intersection (53)
austinapatel
Are we going to learn more about BSP-Tree creation in this class? I'd be interested to further investigate the tradeoffs between the more complex partitioning, and actual benefits when doing ray tracing.
ClaireLiu123
I did some interesting research and I found out that besides KD-tree, there is another one called PR quadtree. The KD tree is an extension of the BSP tree to multiple dimensions. It uses object space decomposition. While PR quadtree uses key space decomposition. They are both binary trees, but just one splitting decisions alternate among the key dimensions, the other one splitting space into four equal-sized quadrants at each branch.
StaffDanCubed
I wonder why both Oct-Tree and KD-Tree use rectangles, while BSP-Tree uses whatever shapes it see fit. What difference does it make? what are the benefits and tradeoffs of rectangles vs non-rectangles? I wonder if it is something similar to what was covered on slide 35?
LuxuFate
@DanCubed BSP-Tree is just a generalization of a KD-Tree, where a KD-tree has the restriction that all lines of division must be parallel to the axes. Here is a post I found on when to use each one/their tradeoffs https://stackoverflow.com/questions/99796/when-to-use-binary-space-partitioning-quadtree-octree
Are we going to learn more about BSP-Tree creation in this class? I'd be interested to further investigate the tradeoffs between the more complex partitioning, and actual benefits when doing ray tracing.
I did some interesting research and I found out that besides KD-tree, there is another one called PR quadtree. The KD tree is an extension of the BSP tree to multiple dimensions. It uses object space decomposition. While PR quadtree uses key space decomposition. They are both binary trees, but just one splitting decisions alternate among the key dimensions, the other one splitting space into four equal-sized quadrants at each branch.
I wonder why both Oct-Tree and KD-Tree use rectangles, while BSP-Tree uses whatever shapes it see fit. What difference does it make? what are the benefits and tradeoffs of rectangles vs non-rectangles? I wonder if it is something similar to what was covered on slide 35?
@DanCubed BSP-Tree is just a generalization of a KD-Tree, where a KD-tree has the restriction that all lines of division must be parallel to the axes. Here is a post I found on when to use each one/their tradeoffs https://stackoverflow.com/questions/99796/when-to-use-binary-space-partitioning-quadtree-octree