If I were trapped on a desert island with only one data structure allowed I would bring my trusty BVH. I have been liking the BVH for some time in spite of all the k-d tree advocates (see the SIGGRAPH 05 notes for a discussion before ray packets were integrated) despite them being "slow". One reason is simplicity-- dividing on objects leads to cleaner implementations than dividing space, and leads to O(N) bounded memory use. My basic software rule is KISS rules! . Another reason is they handle many dynamic models well as has been shown by the collision detection community. It turns out they can also be fast.
Solomon Boulos and Ingo Wald have done a bunch of nice work to packetize a BVH (a ray packet is a set of rays that are traced together). The first optimization (and a huge one) is to descend the BVH as soon as any of the rays hit a box. Maintaining a "first not dead ray" index makes this more efficient. Another optimization is to use interval arithmetic to test a whole packet against a box for a conservative trivial reject. See Solomon's tech report for details (it is really simple even though it sounds fancy, and has a nice mapping to C++ code). Note that both of these optimizations are algorithmic and are mostly orthogonal to SSE optimizations (the descend if one hits optimization makes SSE less helpful).
Finally, the BVH traversal has a low penalty for false positives on boxes, so conservative boxes like you get for moving objects, and well as the lower intrinsic coherency of secondary packets, are not so bad for the BVH.
An important disclaimer: I have previously (in the early 90s) been an advocate of k-d, and later the grid. So maybe this is just the end of the first cycle in my opinion!
It does help if you use the surface-area heuristic to build (that was what it was first invented for in fact-- the BVH). Nobody has ever justified to my satisfaction why the SAH greedy algorithm works so well.
13 comments:
Nobody has ever justified to my satisfaction why the SAH greedy algorithm works so well.
nobody knows what the optimum is, making all comparisons relative. in fact, i'm surprised that no one's taken something like the stanford bunny model and computed, exhaustively, the best possible tree; of course this depends on your definiton of "best", and i think the sah cost model gives a good description: if applied recursively (at each split "event", you recursively consider the minimum total cost of all splits after that) that ought to lead to the best possible tree for any given set of rays (since it's probabilistic).
Hi Thomas. I think it is just too many possible trees! How many ways are there to make the first split for N objects? I think it is N choose 1 + N choose 2 + N choose 3 +... + N choose N/2. And then you need to recurse! So you need some good pruning to make such a computation managable...
indeed it's no walk in the park, and an absolute optimum may be impossible to find for any models worth intersecing.
the real question is whether several "really bad" splits early on can later produce the sah-optimal tree; such a theoretical nuggest would be priceless!
still, there are a lot of cpu cycles in the world right now, and i would have expected _someone_ to have taken their idling supercomputer/cluster and, over a weekend or a month or whatever, find the absolute sah-optimal tree: the stanford bunny could well fit in a modern processor's l2 cache, and all the tree evaluations are in dependent.
a quasi-deterministic approach might also be feasible: you "only" look 2 or 3 splits ahead, and all decisions after that are randomised. if you take enough samples it may be possible to get a good estimate of the jacobian of the total-sah cost wrt the first split co-ordinates...
i really wish i had the time to investigate these ideas; for ye olde median-split k-d trees i wrote a global optimiser to find the best choice of splitting axes, and while that's obviously a much easier problem some of the methods of multidimensional exhaustive search carry over.
I think that you are right that some pruned exhaustive search would be a good idea. Probably a good MS thesis.
that's actually really relieving to hear, i'm still undergrad at 23 *sniff* and very worried that i'm staying weak because of it :/
i would love, love, love to do interesting postgrad research one day (finally publish a real paper and give back to the community that has given me so much), but at the rate i'm going i'll probably retire first!
Very interesting,
I have only implemented the BIH-, the Kd-, the Quad- and the Octree (and a hybrid I've worked out) in the last years, so I dedicate my post to the kd-tree, which everyone seems to see as "The One Mighty AS".
-------------------
Disregarding all the hundreds of lines of code, there might be good AS's for the one thing, good ones for the other things, bad ones, for sure, et cetera. And there might be meta-algorithms (or maybe not? I don't know) which determine the optimal acceleration structure out of a pool of available ones.
In my opinion, there is no absolutely best AS (maybe statistically, but that's only for specific statistics again), e.g. the kd-tree might perform best on "all-day models" as Havran pointed out early this millenium, but what's it worth looking at massive model?
Since my next works are dedicated to massively complex and mostly explicit models I've quit the kd-tree and am now using a bih-tree in general (Wächter/Keller). I have also a q/kd-tree (==quad/kd) in handy (must get that paper ready...) which enables the tracing of >0.1 GTriangles for heightmap based models at some frames per second (also good for visualizing water) on <512 MB RAM.
So I think, at least in areas with home-computerish systems with <4GB RAM (I have only 512MB) AND massive models with 2M+ Triangles/Objects, the kd-tree is the loser.
And doing exhaustive test would be worth a thesis :D
Before I forget, Mister Shirley, as I know Thomas here he already invited you, but for the case he did not, I do now invite you to http://ompf.org/forum, a small, not always serious to the bones, forum dedicated to ray tracing. We have some aperiodically active discussions on Acceleration Structures there and more.
I agree there is likely to be no best universal structure. For static models I think the way things will evolve is to build bunches of them, test empirically for that model, and store the structure with the model.
BTW, I have joined the forum-- just waiting for approval from the moderator.
looking forward to seeing you in the discussions!
btw seb, "mr" shirley is in fact a professor ;)
oops, pardon me about that, for sure I know that and he got my full respect for this and all the work he has done and he was involved in! Mea Culpa :(
uh oh, second "Asche auf mein Haupt":
I spelled "meta-algorithms" above, what I meant was "meta-acceleration-structure"
a GEM of a thread has recently spawned interesting results: http://ompf.org/forum/viewtopic.php?p=3107
Heya,
I have developed an algorithm which bounds intervals like BIH, but which requires no memory for pointers or object indices. Here it is. You might like to check it out.
http://www.mcnett.org/
Bryan McNett
Post a Comment