(L) [2006/04/16] [Phantom] [extreme trees] Wayback!I started anew with my kd-tree compiler, got a working 'N^2' compiler now, plus a working 'Nlog2N' (though it's very slow, it's using bubblesort atm [SMILEY Wink] ). Thanks to the silly N^2 compiler I can now properly validate results of the faster compilers.
Anyway, I was thinking about the 'perfect tree' (that would be a nice name for a tracer btw):
- If build times are not an issue, it might be interesting to see how much netter a tree would get if:
a) The cost of a split would be based upon 'n' extra iterations, i.e., each split would evaluate the consequences for the next iteration, and add up the estimated cost of the left and right branch. Intuition tells me this should matter a slight bit (at a considerable expense, obviously). Interesting thing is: How much better could it get? For 'n=1' I expect a small gain (5%?), for n=2 an aditional 1 or 2%, from there on it should barely matter. It would help to conquer local minima in the cost function, so that could be (very) good in some cases. Exactly what the 'perfect tree' is is a question that is interesting anyway by the way.
- It might also be interesting to take areas of triangles into account. A ray has 25% chance of hitting just the left subnode, 25% for the right one, and 50% of hitting them both. However, the chance that a ray hits the right node after the left one is influenced by triangles that are in the split plane: A 'planar' polygon that covers 50% of the split plane would reduce the chance that a ray passes from left to right by 50%. This can be made more general (I'm probably going to screw up here, but anyway): A triangle that is halfway the left node, and covers 50% of the 2D area when projected on the axii of the split plane, has a chance of 0.5 * 0.5 of blocking a ray (on average). Taking this into account when calculating the estimated chance of hitting a subnode might matter quite a bit. There are way too many assumptions in the original SAH approach, and this is definitely one of them.
- Wald is suggesting in his latest paper to put the planars either left or right. This made my compiler a bit better, but why would you always put ALL planars either to the left or right? I would like to try what happens when all options are considered: Suppose you have 5 planars, the best cost could be for the case where 2 of the 5 are put to the left subnode.
Just some thoughts. All these ideas will degrade tree building performance, obviously. I'm very interested in 'the perfect tree' though. Fast building is really interesting, but I would like to have objective figures of the cost of fast building compared to a near perfect solution.
I also find it very worrying that SAH is sometimes just plain wrong. I believe it was Toxie that mentioned a case where a median split (~octree) is actually better than a SAH assisted kd-tree build. I would like to know why.
_________________
--------------------------------------------------------------
Whatever
(L) [2006/04/17] [tbp] [extreme trees] Wayback!I'm not sure it's that wise to scatter planars around because it's interesting to, at a later stage, split them in the plane they belong; it's not impossible in your scheme, just less probable.
Also, and you don't mention that, triangle extrema aren't the only possible splitting points. As a matter of fact, my old compiler also looks into splits standing around but not exactly at those extrema, and it brings better trees.