Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Bounding interval hierarchy vs KDTree


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 RealMarkP   Members   -  Reputation: 216

Like
0Likes
Like

Posted 22 September 2008 - 08:24 AM

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)

Sponsor:

#2 Almonsin   Members   -  Reputation: 180

Like
0Likes
Like

Posted 22 September 2008 - 08:39 AM

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.

#3 smitty1276   Members   -  Reputation: 560

Like
0Likes
Like

Posted 22 September 2008 - 08:43 AM

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.

#4 ApochPiQ   Moderators   -  Reputation: 17144

Like
0Likes
Like

Posted 22 September 2008 - 08:56 AM

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.

#5 RealMarkP   Members   -  Reputation: 216

Like
0Likes
Like

Posted 22 September 2008 - 11:09 AM

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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS