Jump to content

View more

Image of the Day

#ld38 #screenshotsaturday Mimosa Fizz action gif #2 https://t.co/TUzdppvfUL
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.


Sign up now

Bounding interval hierarchy vs KDTree

4: Adsense

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   

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)

#2 Almonsin   Members   

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   

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   

22567
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   

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.