Lecture 9: Ray Tracing & Acceleration Structures (54)
emily-xiao
Since our runtime is related to the number of objects, I believe it would always be better to split at the median; splitting at the midpoint could cause unbalanced trees. Is there any case where this is untrue?
sebzhao
Might be a toy example but apparently there's good enough performance splitting on the midpoint with some alterations (called sliding-midpoint). https://en.wikipedia.org/wiki/K-d_tree
jefforee
In the case we split at the midpoint, how would we distinguish where to place the circle that is on the line? What if the line perfectly cut the circle in half? Would it be considered the top, the bottom, or both?
Since our runtime is related to the number of objects, I believe it would always be better to split at the median; splitting at the midpoint could cause unbalanced trees. Is there any case where this is untrue?
Might be a toy example but apparently there's good enough performance splitting on the midpoint with some alterations (called sliding-midpoint). https://en.wikipedia.org/wiki/K-d_tree
In the case we split at the midpoint, how would we distinguish where to place the circle that is on the line? What if the line perfectly cut the circle in half? Would it be considered the top, the bottom, or both?