• Advertisement
Sign in to follow this  

Bounding interval hierarchy vs KDTree

This topic is 3409 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was just wondering if anyone know or used a Bounding interval hierarchy (BIH) for scene management. How does it compare to a KDTree or other such spacial partitioning systems? If so, can someone point me to some reading on this, preferably a posted implementation if there is one? Thanks in advance. (And Yes I did google this)

Share this post


Link to post
Share on other sites
Advertisement
Have a look at the forum of ompf.org . There are discussions about these topics, and I have seen posted implementation of a BIH there, you might also find a kDtree.

It's not easy to find them though, but it can be done, try searching in the forums.

Share this post


Link to post
Share on other sites
This may be too obvious, but wikipedia actually has some pretty good stuff on these with a psuedo-implementation. See the kd-tree article.

I know you've probably already looked at it, but I figured I would post it just in case.

Share this post


Link to post
Share on other sites
I've used both object-aligned and axis-aligned bounding volume hierarchies with good results in the past; they're fairly decent and certainly easier to implement than a kd-tree. The main reason I find them useful is to directly mirror a scenegraph in the bounding volume structure; this helps when doing debugging etc. because you can see directly which nodes get pruned.

Performance-wise it really depends on what your scene's layout is like. A good BVH can rival a kd-tree in the average case, but each one shines in special extreme cases. BVHs are usually useless with lots of tiny geometry, for example, whereas a kd-tree isn't all that great for working with highly sparse geometry.

Of course, that also depends on what you're doing with that geometry; for some cases (like scanline conversion in a typical 3D engine) it makes very little difference. For others (ray tracing) it can make a world of difference. So YMMV.

Share this post


Link to post
Share on other sites
Well, I am not making a ray-tracer and all I'm looking into is a scene Management structure that is very fast in outdoor environments. I was going to use one for Geometry (BIH or ABT or KDTree) and one for terrain (OcTree). I looked into the BIH and KDTree entries on wikipedia but it lacked comparison details.

Thanks for the info thus far.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement