BKD-Trees

(L) [2006/06/21] [fpsunflower] [BKD-Trees] Wayback!

[LINK http://graphics.cs.uni-sb.de/Publications/2006/bkd_gh06_final.pdf]

BVH+KDTrees, for those who can't decide [SMILEY Wink]

(L) [2006/06/21] [Phantom] [BKD-Trees] Wayback!

5300 lines of code to build that FPGA... Is that affordable hardware? Sounds like cool stuff to play around with. [SMILEY Smile]

EDIT: You can get this gear for PCIe @ $349:

[LINK http://www.analogzone.com/iop_0424.htm]

(that is, if your family-safe internet filter doesn't prevent you from surfing to that url, it's... odd)
_________________
--------------------------------------------------------------

Whatever

(L) [2006/06/21] [Ho Ho] [BKD-Trees] Wayback!

So, does this mean that tracing dynamic scenes is "solved"?

Certainly looks like that. Rendering a bunch of random triangles has never been effective, not even on regular rasterizers and I doubt many use those random tris in real world anyway.

Am I correct that one thing that might not be very effective to render with that algorithm is an explosion when some object blows into several smaller chunks? E.g a car consisting of 100k polys gets ripped into 1000 pieces, 100 polys each. That kind of movement is not completely random but I think it doesn't map very well to BVH's either.

(L) [2006/06/21] [Phantom] [BKD-Trees] Wayback!

Well the HW I linked to is quite a bit newer (it supports PCIe), but I'm not sure if it could support their architecture (I suppose the number of gates is the primary limiting factor here?). I could imagine that stuff that cost 10k 5 years ago is now in the sub-1000 range. That's what happens to other HW anyway. [SMILEY Smile]

By the way, this algorithm clearly needs some tweaking. I'm sure 4x22bit floats is fine for FPGA, but it's a disaster for CPU's. And since I am not so optimistic about RPU's arriving anytime soon, I simply see a huge data structure per node, plus expensive traversal (4x the number of ray/plane intersections). But yeah, it appears to solve the animation problem.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/06/21] [toxie] [BKD-Trees] Wayback!

Damn! It's almost exactly like what we did with the Bounding Interval Hierarchy! :(
_________________
what do you expect to do if you don't know what to do when you've got nothing to do?

(L) [2006/06/21] [Shadow007] [BKD-Trees] Wayback!

I never traversed a KdTree (let alone coded one) so I don't get soime of their reasoning

<naive mode>I've parsed quickly the paper, and have one question : why use 4 planes and not only 2 ? would'nt the end position of the left slab and the start position of the right slab be enough ? with one more bit you get to know if the left one is really left or if for some reason it's the reverse ...

</naive mode>

It may be because it eases the rebuilds ?

Or because it speeds up some traversals ?

BKD-Trees back