Jump to content
  • Advertisement
Sign in to follow this  
Tesctassa

Which space partition?

This topic is 3826 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

Hi all! As you can see this is my first post, so I'm not sure if this is the right section to post this question, but it looks like :P The problem is quite simple and (probably) common: I need to choose the most suitable space partition system. The main point is that I have custom shaped sectors (not curved) in my scene. For example I can have not only parallelepiped, but also shapes obtained by composition of more parallelepipeds, or other solid geometric shapes, also non-convex. I thought about using a kd-tree, but I wanted your opinions about it, or any suggestion, even about what kind of considerations to do in kind of situation. Thanks a lot!! Regards, Adriano

Share this post


Link to post
Share on other sites
Advertisement
The optimal spatial partitioning algorithm does depend on what you want to use it for really.

A Kd-tree may be a good option, if you use the forum search feature for terms like 'adaptive-binary-tree', 'abt' and 'abtree' then you should come across several (oftentimes lengthy) posts about this structure.
The basic premise is that you construct a kd-tree (actually a binary tree) using some heuristic, then convert it to a AABBTree while applying volume resizing (tightening and growth) to end up with a highly optimised spatial partitioning structure that is good for both indoor and outdoor scenes.
You can also combine this with a re-building heurisitic to get efficient dynamic culling for moving objects too.

Share this post


Link to post
Share on other sites
A space composed of overlapping, arbitrarily shaped volumes might be a good place for a Bounding Volume Heirarchy. Pete Shirley, the author of my graphic class text book likes them hehe:

http://psgraphics.blogspot.com/2007/03/bounding-volume-hierarchy.html

He advocates them due to simplicity, which I agree is the overriding factor in all non-commercial software.

Share this post


Link to post
Share on other sites
Just to emphasise a minor point that may go un-noticed otherwise - an AABBTree is a bounding volume hierarchy. [smile]

Share this post


Link to post
Share on other sites
Thanks for you're replies! Very helpful!

Quote:
Original post by FippyDarkpaw
A space composed of overlapping, arbitrarily shaped volumes might be a good place for a Bounding Volume Heirarchy. Pete Shirley, the author of my graphic class text book likes them hehe:

http://psgraphics.blogspot.com/2007/03/bounding-volume-hierarchy.html

He advocates them due to simplicity, which I agree is the overriding factor in all non-commercial software.


I forgot! Volumes are not overlapping. They're customly shaped to avoid that, and my aim is real-time graphics.

Thanks again!
Regards,
Adriano

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!