Quad-tree is not balanced tree. This is the main reason for its lower intersection performance than KD tree, right?
mchoquet
There's no particular reason why a kd tree should have to be balanced; the lower performance of a quad/octree comes from the way we're dividing the space. With a kd tree we can intelligently choose splitting planes to match the structure of our scene as well as possible, but with a quad/octree we must always divide the space down the middle. This means that if the triangle density in our scene is highly nonuniform, the quadtree might have several levels of empty or mostly empty nodes we have to traverse through before reaching the part we care about.
Quad-tree is not balanced tree. This is the main reason for its lower intersection performance than KD tree, right?
There's no particular reason why a kd tree should have to be balanced; the lower performance of a quad/octree comes from the way we're dividing the space. With a kd tree we can intelligently choose splitting planes to match the structure of our scene as well as possible, but with a quad/octree we must always divide the space down the middle. This means that if the triangle density in our scene is highly nonuniform, the quadtree might have several levels of empty or mostly empty nodes we have to traverse through before reaching the part we care about.