Lecture 9: Ray Tracing & Acceleration Structures (73)
omijimo
would it be possible to terminate the algorithm early if there is an already closer intersection than the current node being checked? in other words, we first check the intersection with the border of the nodes, and if in the closer node there is a triangle that is closer than the closest border of the other child node, then we just skip that child entirely?
buggy213
yes, ideally you want to do a front-to-back traversal so you can exit early. however, its not always feasible to do this without actually computing the intersection with both children
Yeek2
I'm not quite certain why we're not allowed to end the algorithm early. I thought by selecting sets of objects we'd be able to tell which one was "closer" to the ray unless we had poor partitioning of the objects (which is what we were trying to avoid in the first place?)
GH-JamesD
Can these recursive traversals be parallelized such that they can be run efficiently on multithreaded devices?
kalebdawit
Along the lines of the previous comments, would we be able to store extra spatial metadata for each node? Specifically, the min and max point of any object in the node's object set for each dimension (i.e. x, y, and z), building a spatial bounding box for each node. Then, like the first comment said, we can check if our hit1 is closer than the leftmost x value in child2. In this case, this would allow us to skip child2 entirely.
andrewn3672
I find this algorithm to be very elegant in how it performs its search as it is very easy to understand. I originally had a bug in the project where I tried terminating early when searching for a hit since I returned hit1 || hit2 as my return statement. This is incorrect because this return statement would only return hit 1 if it returned true, but hit2 could possibly have a closer hit. This means we have to check both the left and right sides in order to find the correct minimum.
would it be possible to terminate the algorithm early if there is an already closer intersection than the current node being checked? in other words, we first check the intersection with the border of the nodes, and if in the closer node there is a triangle that is closer than the closest border of the other child node, then we just skip that child entirely?
yes, ideally you want to do a front-to-back traversal so you can exit early. however, its not always feasible to do this without actually computing the intersection with both children
I'm not quite certain why we're not allowed to end the algorithm early. I thought by selecting sets of objects we'd be able to tell which one was "closer" to the ray unless we had poor partitioning of the objects (which is what we were trying to avoid in the first place?)
Can these recursive traversals be parallelized such that they can be run efficiently on multithreaded devices?
Along the lines of the previous comments, would we be able to store extra spatial metadata for each node? Specifically, the min and max point of any object in the node's object set for each dimension (i.e. x, y, and z), building a spatial bounding box for each node. Then, like the first comment said, we can check if our hit1 is closer than the leftmost x value in child2. In this case, this would allow us to skip child2 entirely.
I find this algorithm to be very elegant in how it performs its search as it is very easy to understand. I originally had a bug in the project where I tried terminating early when searching for a hit since I returned hit1 || hit2 as my return statement. This is incorrect because this return statement would only return hit 1 if it returned true, but hit2 could possibly have a closer hit. This means we have to check both the left and right sides in order to find the correct minimum.