SAH-Kd-Tree back

(L) [2006/06/05] [Michael77] [SAH-Kd-Tree] Wayback!

Hi,


first of all: Great forum! Exactly what I was always looking for [SMILEY Smile]


I just started writing my first kd-Tree compiler and it works pretty decent right now, although it produces quite large trees in some situations. The trouble I am currently experiencing: When I change the size of my scene, the kd-tree changes quite a bit. While the average numbers stay roughly the same, in some situations, it produces many subdivisions until a cell is merely about 1e-5³ . It´s not so clear to me, why this happens. I actually used Walds idea in this paper:


[LINK http://www.sci.utah.edu/~wald/Publications/webgen/2006/KDTreeTR/download/kdtree.pdf]


However, I already made some additional adjustments since it otherwise always tried to cut of an empty cell with 0 width in one dimension, so my cost function is currently:

(L) [2006/06/06] [goodbyte] [SAH-Kd-Tree] Wayback!

Hi

My first post here aswell, have been lurking around and reading up for quite some time now. I too have managed to get some trees from my kd-compiler but I'm facing a similar problem (my compiler likes to create deep trees, some of my trees for more advanced models can be ~2000 levels deep, i.e. still some debugging to do).


To your problem, have you tried increasing your SEPSILON by a factor of 100? I'm not saying this is a solution to your problem, but it might be related. I've seen some hints in the forum that introducing clipping might solve the problem but that remains untested. Also how do you handle axis-planar triangles? with or without epsilon?

(L) [2006/06/06] [Michael77] [SAH-Kd-Tree] Wayback!

Axis planar triangles are handled with an epsilon, which is currently set to 1.0e-5f. Also, I am doing a sutherland hodgeman clipping already (and based on where splits are placed, the code seems to be correct).


There are some special cases that are not handled very well, a simple fan for example (like in the pole of a sphere). Without limiting the maximum depth it would recurse forever for the center since it can never get below the 2 triangle threshold I have set since this is simply not possible with a kd-tree. So there should be a condition that stops the kdtree from doing more subdivisions when a cell gets too small. But I can´t find a good one that takes into account the scene dimensions as well.


Michael

(L) [2006/06/06] [Phantom] [SAH-Kd-Tree] Wayback!

If your tree depth changes when you scale your scene, it's quite obviously an epsilon problem.


That being said: Did you take a look at my kd-tree compiler source code? I used a slightly different approach for empty space cutoff: A small slice of empty space scores worse than a large slice. Besides that, flat slices are OK as long as there are triangles in it. SAH should take care of that, even without special provisions for empty space cut-off. If you don't allow flat cells at all, you're going to have tree depth problems.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/06/06] [Michael77] [SAH-Kd-Tree] Wayback!

Hi,


I am allowing flat cells and the compiler creates them (tested it on a simple cube resulting in 2 Triangles in every leaf).


I must admit, I have some problems reading your code (totally different coding style than mine [SMILEY Smile] ) but if I understand it correctly, you only allow empty space cutoff if the empty box has at least 33% percent of the width of the original box, right? However, I don´t think that empty space is my problem. It looks more like non-empty space is the problem in some situations so the subdivision continues until the maximum depth is reached because it can´t find a good split. But maybe I am totally wrong anyway.


Here is the complete code I am currently using (its not optimized and is currently (n log² n)):

(L) [2006/06/06] [Phantom] [SAH-Kd-Tree] Wayback!

Well I'm not going to wade through all that code, but one thing that's strange is that you initialize bestcost to a very high value. It should be initialized to the cost of not splitting.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/07/29] [Germ] [SAH-Kd-Tree] Wayback!

Hey guys, kinda new here.  Been reading for a while, but first time posting.


Phantom, you mentioned your KD-tree compiler code.  Where can I find that?


Great forum guys!  Keep up the good work!