I was wondering why each node in the oct tree only had up to 4 children. Then, I realized these were the 2d versions of the data structures, so in 3d, a node of an oct tree would have up to 8 children, since you can split the space into 8 octants (https://en.wikipedia.org/wiki/Octant_(solid_geometry)).
knguyen0811
In what situations would one tree structure be more preferable compared to the others? I read in a forum that BSP-trees take longer to build and is restricted to static geometry.
andrewdcampbell
Its interesting to note that these trees can be constructed either top-down, bottom-up, or incrementally. In top-down, we bound everything, choose a split plane, divide objects into sets, and recurse. In bottom-up construction, we bound individual objects, group them into sets, create a parent, and recuse. According to wikipedia, bottom-up methods are more difficult to implement, but likely to produce better trees in general. In incremental construction, we insert one bound at at a time and grow the tree as required. It is good for online environments where objects are created dynamically.
Hsifnus
Given that spatial partitioning inherently creates a tree data structure, it would seem that such schemes are able to accommodate cases in which enough new objects are created in the space of one node such that a partition may be needed. However, if a group of objects was to suddenly change position, would a spatial partitioning scheme need to recompute its entire tree, or are there potentially more efficient ways of going about this?
GitMerlin
@Hsifnus, I'm no expert in this, but in my opinion, if a single object is to move, then we can simply do a insert node operation (and potentially a delete node). However, if a great many objects are going to move, I don't expect to see any structure be able to handle this situation without reconstructing an entire tree.
eliot1019
knguyen, this is speculation but perhaps it depends on how expensive the ray calculations themselves are vs the cost of creating the bounding boxes. Maybe there could be a scene where ray calcs are minimal for each object but there are many objects which could benefit from better bounds.
Gilbert-Han
Since these trees are trying to minimize the expected cost of a ray intersection, are they related to Huffman Trees?
orkun1675
The Oct-Tree, especially the version depicted here, reminds me of the mipmap storage strategy we discussed in the previous part of the course.
I was wondering why each node in the oct tree only had up to 4 children. Then, I realized these were the 2d versions of the data structures, so in 3d, a node of an oct tree would have up to 8 children, since you can split the space into 8 octants (https://en.wikipedia.org/wiki/Octant_(solid_geometry)).
In what situations would one tree structure be more preferable compared to the others? I read in a forum that BSP-trees take longer to build and is restricted to static geometry.
Its interesting to note that these trees can be constructed either top-down, bottom-up, or incrementally. In top-down, we bound everything, choose a split plane, divide objects into sets, and recurse. In bottom-up construction, we bound individual objects, group them into sets, create a parent, and recuse. According to wikipedia, bottom-up methods are more difficult to implement, but likely to produce better trees in general. In incremental construction, we insert one bound at at a time and grow the tree as required. It is good for online environments where objects are created dynamically.
Given that spatial partitioning inherently creates a tree data structure, it would seem that such schemes are able to accommodate cases in which enough new objects are created in the space of one node such that a partition may be needed. However, if a group of objects was to suddenly change position, would a spatial partitioning scheme need to recompute its entire tree, or are there potentially more efficient ways of going about this?
@Hsifnus, I'm no expert in this, but in my opinion, if a single object is to move, then we can simply do a insert node operation (and potentially a delete node). However, if a great many objects are going to move, I don't expect to see any structure be able to handle this situation without reconstructing an entire tree.
knguyen, this is speculation but perhaps it depends on how expensive the ray calculations themselves are vs the cost of creating the bounding boxes. Maybe there could be a scene where ray calcs are minimal for each object but there are many objects which could benefit from better bounds.
Since these trees are trying to minimize the expected cost of a ray intersection, are they related to Huffman Trees?
The Oct-Tree, especially the version depicted here, reminds me of the mipmap storage strategy we discussed in the previous part of the course.