Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / Using KDTrees with general transforms Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
thehustler

May 19, 2005, 12:25 AM

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?

 
thehustler

May 20, 2005, 02:15 PM

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.

 
Ono-Sendai

May 21, 2005, 09:41 AM

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

 
adel

May 22, 2005, 09:11 AM

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.

 
thehustler

May 22, 2005, 11:10 PM

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.

 
dummy

May 23, 2005, 12:12 AM

thehustler wrote: 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?


Side note, SAH is also the best scheme to build BVHs or better put to build the most efficient BVHs, but it's easier to make it non quadratic than for kdtrees.
And, as for BVH, you don't _have_ to use SAH to compile a kdtree: you could use the greatest cell axis, split it in the middle or any other cheap heuristic.

SAH is quite tricky to get right, and a naive implementation will behave quadratically.
But if you pay attention to algorithms/acceleration structures/code & other gory details, you get something working in n.log(n) (in fact much better, but it's data dependant).
On top of that, SAH isn't a panacea... there's ways to enhance the original heuristic quite a bit at the expense of even more potential split inspections (like 2x more).

Compilation times are mesh dependant (you can think of a SAH kdtree compiler as a form of compression), but atm i can compile a 250k triangle soup under 30s.
That's with other kdtree transformations included and an even more expensive heuristic for "small" nodes (

 
thehustler

May 23, 2005, 02:09 PM

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 :)

 
thehustler

May 30, 2005, 05:20 AM

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?

 
Lotuspec

May 30, 2005, 06:39 AM

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

 
thehustler

May 30, 2005, 10:46 PM

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?

 
Jacco Bikker

May 31, 2005, 03:46 AM

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).

 
This thread contains 11 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.