Does in-order traversal guarantee the first intersection we find is the closest intersection? It looks like it does, but I don't know how to formally prove it.
moridin22
@jgforsberg I think you may just be overthinking it - since we traverse the spaces in the order that the ray passes through them, the first intersection has to be the closest one, since that's just what "in-order" means.
sirejdua
I agree that "in order" is confusing here.
I looked at the book (PBRT), and found this explanation of the traversal algorithm, which made a ton of sense.
"Intersecting the ray with the tree’s overall bounds gives initial tMin and tMax values, marked with points in the figure. As with the BVHAccel in this chapter, if the ray misses the overall primitive bounds, this method can immediately return false. Otherwise, it starts to descend into the tree, starting at the root. At each interior node, it determines which of the two children the ray enters first and processes both children in order. Traversal ends either when the ray exits the tree or when the closest intersection is found. "
surelywang
I found this visualization to be an interesting resource in seeing how a KD-Tree is built:
Does in-order traversal guarantee the first intersection we find is the closest intersection? It looks like it does, but I don't know how to formally prove it.
@jgforsberg I think you may just be overthinking it - since we traverse the spaces in the order that the ray passes through them, the first intersection has to be the closest one, since that's just what "in-order" means.
I agree that "in order" is confusing here.
I looked at the book (PBRT), and found this explanation of the traversal algorithm, which made a ton of sense.
"Intersecting the ray with the tree’s overall bounds gives initial tMin and tMax values, marked with points in the figure. As with the BVHAccel in this chapter, if the ray misses the overall primitive bounds, this method can immediately return false. Otherwise, it starts to descend into the tree, starting at the root. At each interior node, it determines which of the two children the ray enters first and processes both children in order. Traversal ends either when the ray exits the tree or when the closest intersection is found. "
I found this visualization to be an interesting resource in seeing how a KD-Tree is built:
http://bl.ocks.org/kevinlin1/d9e4b8d629f7f4163307d68272bf86a0