Hi,
I was reading Jacco's excellent series on writing his ray tracer a while ago and I ended up writing a tracer that also uses a KDTree as an accelerator.
I'm trying to implement general transforms at the same time and most of it seems fairly straight forward, inverse transformation of the ray, inverse transpose transformation of normals etc. but I was wondering if anybody had any insight on the following:

A primitive has a method that tests for intersection of a bounding box. This is used by the KDTree to test for inclusion in a node. The example Jacco has is of a sphere-box intersection method.

If I have a primitive with a transform I want to add to my kdtree I don't see how I can test for intersection without just transforming it's bounding box and using that. Obviously that means a loss of a lot of accuracy. Am I missing something simpler?

On a related note, does anybody know of any forums dedicated to rendering theory?
Flipcode seems to be more game development oriented but I can't seem to find any others.

There are some of us here who are interested in high quality rendering as opposed to straight game grfx, I can assure you :)

I don't think you are stating your problem clearly, or maybe it's just me who couldn't understand you well. At any rate, the following might hopefully answer your question:
* Kd trees are designed for static scenes, so if you're looking at primitives with transforms that change over time, things become a bit more complicated. If not, then consider transforming your primitives (along with their bounding volumes) before building the kd tree.

Hi,
I think the only option was to transform the bounding boxes to check for intersection. I implemented this and it seems to work fine.

I do have another issue though.
The time taken to create a kdtree using the SAH scheme for a large triangle mesh seems to be prohibivitely long.
Practically all of the open sourced ray tracers that I've seen on the web use octrees or HBVs. Is this due to the cost of creating an efficient kdtree or is my implementation just slow. I can't imagine that there are too many places I can optimize though and the SAH scheme in itself seems to be quite expensive.
Any ideas on this?
Perhaps I would be better off using a different heuristic, or even a different type of accelerator.

Well, that definitely sounds like my implementation needs an overhaul.
I'm still prototyping at the moment and so haven't made any optimizations, but it sounds like I need to pay a little more attention to this. I'll persevere with the kdtree.

Thanks for your help :)

Hi,
I rewrote my kdtree building algorithm a while ago, but I've run into a new problem.

I'm fairly sure I've now got an n log n algorithm for creating the kdtree (again, not optimized yet) but I'm unsure as to what kind of heuristic I should be using for maximum tree depth and objects/node threshold.

At the moment, I am using a maximum tree depth of 20 and an object threshold of 20 and when I build a kdtree on the stanford dragon model (about 870,000 triangles) I get massive memory consumption.
I assume I'm allowing too deep a tree, but it could be my algorithm.

Should I aim for a smaller tree or do you think I should be able to create a tree of that size?
What kind of memory consumption do your routines have with these kinds of values?
Is it perhaps my algorithm?

Any ideas?

In theory you should not have to limit the number of object or the tree depth but let the SAH heuristic decide (i.e. stop if the cost for splitting is greater then the cost of not splitting).

Mostly I do not limit the number of objects per node and use a tree depth of 30-50. Once models get a large (more then 500k tri), my application runs out of memory (400MB+) but thats mostly due to using Java wich results in a lot of bytes per node (+- 32 bytes for an empty node). In C++ you should easely be able to load way bigger models.

So SAH result in lots of nodes (an thus lots of memory) and I dont think there's alot you can do about that (without degrading performance).

You could post some statistics like:
-number of tri
-number of nodes
-number of leaves
-tri per non-emtpy node
-memory usage

Hi, I think I'm going to rewrite the kdtree code from scratch (again) and pay attention to memory optimization.
I have solved speed. Now I just need to solve allocation :)

At the moment my nodes are larger than necessary. Jacco got his nodes down to 8 bytes and I imagine I'll implement something similar.
It also looks like this means using a dedicated memory pool would be a good idea.

On a related note, what kind of algorithms are you guys using to get fast kdtree building? I couldn't find any literature on the web, so I just made one up. Is there more than one way to skin a cat or are we likely using the same method?

A while back I explained a fast way to construct a kd-tree using SAH on this forum. I'm not sure if it's easy to find that topic though.

If you want to take a look at my implementation, just drop me a line, I'll gladly send you some source code.

Basically, what I do is this:

The slowest part of the SAH kd-tree construction is finding the best split position, as each split position (in each of the orientations, x/y/z) has a approximated cost, based (a.o.) on the number of primitives to the left and to the right of the split plane candidate. Counting these primitives makes the algorithm very slow, especially during the initial splits. To solve this, I store all split plane candidates in a linked list (sorted). Once this is done, I walk this list from left to right, counting primitives and storing the count in each split plane candidate. For the 'right count' I do something similar. This runs in O(n). It is possible to build a kd-tree for 200k polygons, using SAH, in about 30 seconds if you implement the compiler well (mine is not that fast, but still reasonably fast, 1 or 2 minutes for 200k triangle scenes).