dipityPix app

Thursday, March 15, 2007

Bounding Volume Hierarchy

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.

17 comments:

Thomas said...

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

Peter Shirley said...

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

Thomas said...

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.

Peter Shirley said...

I think that you are right that some pruned exhaustive search would be a good idea. Probably a good MS thesis.

Thomas said...

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!

Sebastian said...

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

Sebastian said...

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.

Peter Shirley said...

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.

Thomas said...

looking forward to seeing you in the discussions!

btw seb, "mr" shirley is in fact a professor ;)

Sebastian said...

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

Sebastian said...

uh oh, second "Asche auf mein Haupt":

I spelled "meta-algorithms" above, what I meant was "meta-acceleration-structure"

Thomas said...

a GEM of a thread has recently spawned interesting results: http://ompf.org/forum/viewtopic.php?p=3107

Bryan McNett said...

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

sexy said...

情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,A片,視訊聊天室,聊天室,視訊,視訊聊天室,080苗栗人聊天室,上班族聊天室,成人聊天室,中部人聊天室,一夜情聊天室,情色聊天室,視訊交友網a片,a片


免費A片,AV女優,美女視訊,情色交友,免費AV,色情網站,辣妹視訊,美女交友,色情影片,成人影片,成人網站,A片,H漫,18成人,成人圖片,成人漫畫,情色網,日本A片,免費A片下載,性愛

A片,色情,成人,做愛,情色文學,A片下載,色情遊戲,色情影片,色情聊天室,情色電影,免費視訊,免費視訊聊天,免費視訊聊天室,一葉情貼圖片區,情色,情色視訊,免費成人影片,視訊交友,視訊聊天,視訊聊天室,言情小說,愛情小說,AIO,AV片,A漫,avdvd,聊天室,自拍,情色論壇,視訊美女,AV成人網,色情A片,SEX,成人論壇

情趣用品,A片,免費A片,AV女優,美女視訊,情色交友,色情網站,免費AV,辣妹視訊,美女交友,色情影片,成人網站,H漫,18成人,成人圖片,成人漫畫,成人影片,情色網


情趣用品,A片,免費A片,日本A片,A片下載,線上A片,成人電影,嘟嘟成人網,成人,成人貼圖,成人交友,成人圖片,18成人,成人小說,成人圖片區,微風成人區,成人文章,成人影城,情色,情色貼圖,色情聊天室,情色視訊,情色文學,色情小說,情色小說,臺灣情色網,色情,情色電影,色情遊戲,嘟嘟情人色網,麗的色遊戲,情色論壇,色情網站,一葉情貼圖片區,做愛,性愛,美女視訊,辣妹視訊,視訊聊天室,視訊交友網,免費視訊聊天,美女交友,做愛影片

av,情趣用品,a片,成人電影,微風成人,嘟嘟成人網,成人,成人貼圖,成人交友,成人圖片,18成人,成人小說,成人圖片區,成人文章,成人影城,愛情公寓,情色,情色貼圖,色情聊天室,情色視訊,情色文學,色情小說,情色小說,色情,寄情築園小遊戲,情色電影,aio,av女優,AV,免費A片,日本a片,美女視訊,辣妹視訊,聊天室,美女交友,成人光碟

情趣用品.A片,情色,情色貼圖,色情聊天室,情色視訊,情色文學,色情小說,情色小說,色情,寄情築園小遊戲,情色電影,色情遊戲,色情網站,聊天室,ut聊天室,豆豆聊天室,美女視訊,辣妹視訊,視訊聊天室,視訊交友網,免費視訊聊天,免費A片,日本a片,a片下載,線上a片,av女優,av,成人電影,成人,成人貼圖,成人交友,成人圖片,18成人,成人小說,成人圖片區,成人文章,成人影城,成人網站,自拍,尋夢園聊天室

smallawei said...

G點,按摩棒,
轉珠按摩棒,變頻跳蛋,
跳蛋,無線跳蛋,
飛機杯,男用強精長軟質套,
男用強精短軟質套,充氣娃娃,
男性性感內褲,性感內褲,
自慰套,自慰套,
情趣娃娃,自慰器,
電動自慰器,充氣娃娃器,
角色扮演,角色扮演服,

性感睡衣,情趣睡衣,
性感內衣褲,性感內衣,
內衣,性感內褲,
C字褲,內褲,
性感貓裝,性感睡衣,
貓裝,吊帶襪,
情趣內褲,丁字褲,
SM道具,SM,

震動環,潤滑液,
情趣禮物,情趣玩具,
威而柔,精油,
逼真按摩棒,數位按摩棒,
加盟,免費加盟,
網路賺錢,情趣加盟,
情趣,情趣用品,巴黎,

javieth said...

I like to see a good illustration in the websides, even if the text isn´t good, i think the graphics have too much importance.I must to say this blog contain a great graphics and that´s what i´ve been looking for.Actually
costa rica investment opportunities
introduce wonderful graphics about different things.

Entertainment said...

home city trung kính

http://homecitytrungkinh.com.vn/

home city

http://homecitytrungkinh.com.vn/tong-quan-du-an-home-city/

chung cư trung kính

http://homecitytrungkinh.com.vn/mat-bang-can-ho-chung-cu-trung-kinh/

trung kính complex

http://homecitytrungkinh.com.vn/tien-ich-trung-kinh-complex/

5S Online - mùa 3 - Tập 66: Tình cậu duyên anh - Phần 1

5S Online - mùa 3 - Tập 65: Con nuôi sếp tổng - Phần 2

5S Online - mùa 3 - Tập 64: Con nuôi sếp tổng - Phần 1

5S Online - mùa 3 - Tập 63: Cắt đuôi sao cho xuôi - Phần 3

5S Online - mùa 3 - Tập 62: Cắt đuôi sao cho xuôi - Phần 2

5S Online - mùa 3 - Tập 61: Cắt đuôi sao cho xuôi - Phần 1

5S Online - Tập 54: Làm giàu quá khó cần có vận may - Phần 3

5S Online - Tập 53: Làm giàu quá khó cần có vận may - Phần 2

5S Online - Tập 52: Làm giàu quá khó cần có vận may - Phần 1

chung cư t&t riverside

chung cư 440 vĩnh hưng

chung cư t&t riverside 440 vĩnh hưng

bat dong san

bat dong san cho thue

bat dong san ban