kd tree traversal

(L) [2006/08/05] [monkeyman] [kd tree traversal] Wayback!

Hi

This is my first post ever here. I like the forum and its exactly what I was looking for. [SMILEY Very Happy]

I hope I posted in the correct forum.

Now I guess I understood how to build a kd trees from reading phantoms #7 Article. But I still dont understand how to traverse it later on. What about secondary rays... How do those work?

Btw I wrote my raytracer in python so it is extremly slow but I am a planning on finishing kd trees and then writing one in C++ or so.

I just hope that kd trees speed up the renders for large scenes because for a simple cube with 12 faces it takes about 10 minutes to render.
_________________
This is the funniest video I have ever seen!:

[LINK http://video.google.com/videoplay?docid=5430343841227974645&q=internet+is+for+pron]

(L) [2006/08/09] [monkeyman] [kd tree traversal] Wayback!

well I decieded to just finnish of pyray and then go on my C++ tracer... do you know any sites that might help me understand the building and traversal of it?
_________________
This is the funniest video I have ever seen!:

[LINK http://video.google.com/videoplay?docid=5430343841227974645&q=internet+is+for+pron]

(L) [2006/08/09] [Michael77] [kd tree traversal] Wayback!

Actually, I would recommend a book:

Peter Shirley: Realistic Raytracing

It guides you through the creation of your own raytracer, including source code (although not optimized for speed). It covers all topics, from basic math to ray triangle intersections, acceleration structures ( Edition 1 used a regular grid, Edition 2 uses a bounding volume hierarchy) up to more advanced topics like path tracing for global illumination.

Michael

(L) [2006/08/09] [Lynx] [kd tree traversal] Wayback!

For a cube made of 12 tris you for sure won't get much speedup, if at all.

Actually, a typical SAH algorithm won't have much luck finding smart split planes when the box is axis aligned.

I'd suggest reading e.g. this one, at least the parts on traversal:

[LINK http://www.cgg.cvut.cz/~havran/phdthesis.html]

Has some very useably pseudo-code, at least if you're satisfied with non-SIMD traversal (like me) [SMILEY Smile]

But we have a nice paper section here, check the sticky thread of must-read material...

(L) [2006/08/09] [monkeyman] [kd tree traversal] Wayback!

Micheal I have taht book and BVH trees is not what I am searching for...

That cube example was just an example meaning Ill never do that again without any bounding volume or so...

but okay thanks lnyx
_________________
This is the funniest video I have ever seen!:

[LINK http://video.google.com/videoplay?docid=5430343841227974645&q=internet+is+for+pron]

(L) [2006/08/09] [funky] [kd tree traversal] Wayback!

Hello,

also very usefull:

[LINK http://www.sci.utah.edu/~wald/Publications/webgen/2004/WaldPhD/download//phd.pdf]

I used the pseudo-code given there to implement my kd-tree traversal.

p.s. @toxie: you (the "real world toxie") tould me about this forum ... thanks for that!

p.p.s ... wow, this is the first time I use my english writing skills ... I hope it dose not sound too strange [SMILEY Smile]

(L) [2006/08/09] [toxie] [kd tree traversal] Wayback!

@funky: when was that?

(and plz don't mention that i have a real world life. this could harm my reputation as being known as a hardcore coder living in a basement and only come out once and then to earn some money or buy food ;)))
_________________
what do you expect to do if you don't know what to do when you've got nothing to do?

(L) [2006/08/10] [monkeyman] [kd tree traversal] Wayback!

Dont worry I know about secondary rays and thats no true that I can jsut stop if I want to do any type of GI I need to know the distance...

I seem to be very popular [SMILEY Very Happy] haha over 10 posts in 1 day [SMILEY Very Happy]

Thanks for the papers I shall commence reading when I have beaten the errors and bugs out of my vector.cpp file!

btw since we are talking about kd trees

is there some psuedo code for building one in the first place around somewhere with detailed things because just having a text on cost of intersection does not really help?
_________________
This is the funniest video I have ever seen!:

[LINK http://video.google.com/videoplay?docid=5430343841227974645&q=internet+is+for+pron]

(L) [2006/08/10] [tbp] [kd tree traversal] Wayback!

Building a kd-tree isn't rocket science: make a box, pick an axis, stuff a splitting plane in between boundaries, categorize geometry wrt to that split, pick an axis... rince & repeat.

Where it gets harder is when you try to produce a 'good' (whatever's the metric you fancy, which is a tricky topic by itself) tree in a reasonable time (read tending to n.log(n)).

So really it can get as complex as you want.
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2006/08/10] [monkeyman] [kd tree traversal] Wayback!

I am first going to focus on writing a working tracer [SMILEY Very Happy] then the kd tree but still see I dont get the best cost median thing... and I guess that is the most effienct
_________________
This is the funniest video I have ever seen!:

[LINK http://video.google.com/videoplay?docid=5430343841227974645&q=internet+is+for+pron]

(L) [2006/08/10] [lycium] [kd tree traversal] Wayback!

to add some justification: there are lots of resources on the net on the basics, and in my perhaps-not-so-humble opinion it's pretty sufficient to get going. however, once the basics are in place (say, 8 byte per node k-d tree construction and traversal), there's suddenly very little info on the net about how to make it really excellent, and even less "visible" collaboration / exchanging of ideas relating to this. that's where the true value of these forums lies.

i'm not saying there can't be a section for beginners, that could perhaps be arranged (see eg. the underused non-realtime section), depending on what kind of focus tbp has in mind for these forums- ray tracing or advanced ray tracing. what i am saying is that if you see there's a forum, where specialists are discussing the latest developments and you "don't expect to know what you're doing", perhaps it may not be the best place to post "lol plz explain k-d tree and best cost median thing"...

quick thing: seek and ye shall find! (eg "where do i find phantom's k-d building code?" -> "see that little box in the topright corner?" / "there's always google").

(L) [2006/08/10] [tbp] [kd tree traversal] Wayback!

Like lycium noticed, there's a metric ton of entry level articles about SSE, acceleration structures and raytracing in general on the net. After that point it's mostly terra incognita. I think discussions we're having on this board prove the point.

Now if there's nobody willing to answer beginner's questions then a brand new section ain't going to do any good. I'm not going to add insult to injury by moderating, the lack of reply is enough of a clue... that is unless there's a deluge of topics google should have filled or too much whining about said lack of replies [SMILEY Wink]
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2006/08/12] [beason] [kd tree traversal] Wayback!

2nd edition of Shirley's Realistic Ray Tracing (RRT) has code for BVH.

To answer original poster:

(Efficient) Kd-tree's are explained in Wald's thesis (link provided in earlier reply). You can add realistic shading easily as long as you don't mind that it's slow. The pseudo-code for this algorithm (called path tracing) is 4 lines long and given in Shirley's RRT book. A bigger and more comprehensive book is PBRT as someone else mentioned earlier. Essentially all of this information is available online if you are willing to really dig. Sounds like you already have RRT, so that's a good start. There are also several open source renderer's if you want to see how other people have done things. For example, sunflow (fpsunflower's renderer) has a Kd-tree (and BVH or grid) and complete source code. However, it's optimized using the latest techniques discussed in this forum. Since this is your first acceleration structure you may want to go with something more simple at first, such as choosing the longest axis and using midpoint subdivison. Even this will provide a huge speedup over testing every tri for every ray, as you move from an algorithm that is O(n) to O(log n). (Someone correct me if I'm wrong.) Most of the other optimizations are for special cases like teapot-in-a-stadium or for improving the order of algorithm for building the tree, which in my experience is usually the least expensive part of the process.

(L) [2006/08/12] [tbp] [kd tree traversal] Wayback!

[shameless plug]

Another kd-tree compiler, if a bit hairy, can be found here, [LINK https://gna.org/projects/radius/]

I've been working on it a bit lately, and tuned the code for a 25% speedup - in the construction itself - when not memory bound; there's also a few fixes, a radix sort that directly build lists etc... but i'm going to tackle proper multithreading before commiting.
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2006/08/12] [Phantom] [kd tree traversal] Wayback!

Perhaps you shouldn't try kd-trees at all; Toxie's BIH is far simpler to implement, and though it's slower for static scenes, it makes it possible to render dynamic scenes. I think that's a quite fundamental requirement if you ever want to use the raytracer for anything practical, so you may want to go for this simpler solution.

Perhaps this is a bit of an fundamental question by the way: Is kd/sah dead, now dynamic scenes are possible using an approach that is at the same time simpler to implement? Seems to me the answer is 'yes'. Also, considering the amount of thought that has gone into kd/sah, bih and derivatives might very well take over even in the performance department once they are polished a bit more.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/08/12] [monkeyman] [kd tree traversal] Wayback!

ya I actually though of implementing more then one algorithm... So that I could choose depending on the scene.

Thanks for the posts [SMILEY Very Happy]

btw maybe you should make a beginners forum... it might help alittle.

First my raytracer actually has to work without any algorithm before I do anything but thanks alot... I ll have a look into BIH aswell.
_________________
This is the funniest video I have ever seen!:

[LINK http://video.google.com/videoplay?docid=5430343841227974645&q=internet+is+for+pron]

(L) [2006/08/12] [tbp] [kd tree traversal] Wayback!

If anything is dead, then that would be BVH. The strength of a kd-tree is that it has few pathological weaknesses, or put another way that when facing those cases the outcome isn't that pathological. Thusly using peak performance figures to compare it to other hierarchies doesn't make much sense.

I think Michael77's point is much more important, as a fast sah/kd-tree compiler and out of core or tight memory conditions are tricky to tackle to say the least.
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2006/08/13] [monkeyman] [kd tree traversal] Wayback!

I read the paper on BIH yesterday evening(night) and I am going to have a shot at it, it seems promising that is performs the same or faster than kdtrees...

And then Ill implement multiple algorithm sometime else when I am in school again [SMILEY Razz]

btw what computer specs do you all have that you can run at such high speeds?
_________________
This is the funniest video I have ever seen!:

[LINK http://video.google.com/videoplay?docid=5430343841227974645&q=internet+is+for+pron]

(L) [2006/08/13] [tbp] [kd tree traversal] Wayback!

At the time i bought them, opterons with proper revision (SSE3 support etc) were insanely overpriced in dual core version. So i still have wet dreams of a quad core box but i only really have two 2.6ghz k8 (opteron 252).
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2006/08/13] [monkeyman] [kd tree traversal] Wayback!

hm oaky I dont have dual cores [SMILEY Sad] but I am planning on building a monster (dual core dual processor, 4 gigs ram) a monster for at home [SMILEY Very Happy]

but my laptop has a 2.0 ghz pentium m procesor and 2 gigs of ram [SMILEY Very Happy]
_________________
This is the funniest video I have ever seen!:

[LINK http://video.google.com/videoplay?docid=5430343841227974645&q=internet+is+for+pron]

(L) [2006/08/16] [Phantom] [kd tree traversal] Wayback!

@lycium: Let me define 'anything practical': Unless you're doing a fly-through of a static scene (architectural visualization perhaps?) you will be doing animations. That's why I called kd-trees impractical.

I'm not so sure anymore though (I wrote that in January), as the difference between a really fast kd-tree compiler and a bih 'compiler' is about one order of magnitude. If there's enough rays to trace, the faster rendering times of kd-trees will make up for the longer build times. Clearly, if you want area lights, recursive reflections or even global illumination, a fast kd-tree compiler might be a better choice. So indeed, let's postpone that kd-tree funeral until bih and it's variations match kd-tree rendering times. Or, let's build really great bih/sah trees and investigate dynamic trees.

I would still advice a newbie to go for BIH at this point btw. It's far simpler. But that's currently the main reason.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/08/16] [madmethods] [kd tree traversal] Wayback!

Interesting discussions.  We should definitely separate the question of acceleration structure (kd-tree vs. various BVHs (BBHs or SKD/BKD/BIH/H trees)) from the question of building with SAH optimization.  The two questions are largely orthogonal.

Regarding kd-trees, I think they're superior in the limit of high complexity, irregularity, and visual quality.  I haven't seen any evidence that contradicts that.  Two coherent rays per pixel cast against a laser-scanned model floating in space doesn't convince me [SMILEY Smile].  I do like the SKD style trees, though.

Regarding SAH, approximate it as much as you like, but don't throw it out.  I haven't seen any evidence that a non-SAH build can compete with an SAH build on scenes with significant irregularity.  Laser-scanned models are less than useless for evaluating this.  I also don't see any fundamental reason to believe that a builder that doesn't use SAH at all is necessarily significantly faster than a builder that uses a rough approximation to SAH.

-G

(L) [2006/08/16] [tbp] [kd tree traversal] Wayback!

Indeed. Tho, practically speaking there's a quite a difference whether we're trying to s(A)hoehorn a BVH or kd-tree.
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2006/08/17] [Michael77] [kd tree traversal] Wayback!

Especially in the non-realtime raytracing part, the speed of tracing a ray is not as important as other aspects. Scenes with 20 Million triangles or more are very common, so the memory requirements are a big issue. This is, where the BIH is the clear winner. Also, on HQ Renders, most of the time is spend in the shading algorithms. If finding a intersection with a kdtree takes about 100 instrcutions and with a BIH takes about 120 instructions, no one really cares, since shading probably takes about 1000 instructions.

So if the BIH delivers about 80% of the performance of a kdtree, is faster to build and requires less memory, this is the clear winner to me for HQ Renders. I am not shure, but I think, most HQ renderers like mental ray don´t even use a SAH when building their BSP/KD Tree. So for these renderers, the BIH will probably be the way to go.

(L) [2006/08/17] [Phantom] [kd tree traversal] Wayback!

One thing I would like to add is the greater numerical stability of BIH compared to kd. It's quite hard to build a perfect kd-tree, although Havran doesn't seem to have too much problems with that.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/08/17] [tbp] [kd tree traversal] Wayback!

You are describing OS limitations, and that's orthogonal; note that win32 has had PAE support for some time now, [LINK http://en.wikipedia.org/wiki/Physical_Address_Extension]

So either tell your HQ renderer vendor to support PAE or out-of-core processing, again it's pretty straight. Or use a real OS [SMILEY Smile]

But you haven't addressed the keypoint, that a kd-tree is way more reliable.
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2006/08/17] [toxie] [kd tree traversal] Wayback!

/enable sarcastic mode

the point of being able to render more triangles (because less memory used) is of little use in production rendering actually, as artists will ALWAYS max out the memory, no matter how much memory you'll save with the acceleration structure. They will just include another highres-texture if there's still place for it.

;)
_________________
what do you expect to do if you don't know what to do when you've got nothing to do?

(L) [2006/08/17] [tbp] [kd tree traversal] Wayback!

A triangulated Wavefront/.obj export should be possible from Maya, right?

ATM there's no semi-large public geometry to play with beside scanned models or procedural stuff. It would be very kind of you to share a scene.
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

kd tree traversal back