Lecture 9: Ray Tracing & Acceleration Structures (52)
TiaJain
To my understanding, a KD-Tree is like a decision tree for sorting spatial information. An analogy that helped me understand it better was thinking of it like a game of "20 Questions" where each question (an internal node) halves the possibilities until you reach a conclusive answer (a leaf node) that tells you exactly where an object is located in space.
litony396
Is there ever any reason to not build the tree as a binary tree?
oliver-ni
This is super cool! Sort of like a binary search tree. kd trees also have many other use cases as well. For example, in 61B for the BYOW project, I tried using a kd tree in order to generate a random world with different rooms and hallways. It didn't work as well as I wanted it to, but it was decent :)
To my understanding, a KD-Tree is like a decision tree for sorting spatial information. An analogy that helped me understand it better was thinking of it like a game of "20 Questions" where each question (an internal node) halves the possibilities until you reach a conclusive answer (a leaf node) that tells you exactly where an object is located in space.
Is there ever any reason to not build the tree as a binary tree?
This is super cool! Sort of like a binary search tree. kd trees also have many other use cases as well. For example, in 61B for the BYOW project, I tried using a kd tree in order to generate a random world with different rooms and hallways. It didn't work as well as I wanted it to, but it was decent :)