Sign in to follow this  
Tesctassa

Which space partition?

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
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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this