   Which space partition?
  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 :PThe 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   
  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.   ;  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.htmlHe advocates them due to simplicity, which I agree is the overriding factor in all non-commercial software.;  Just to emphasise a minor point that may go un-noticed otherwise - an AABBTree is a bounding volume hierarchy. [smile]   ;  Thanks for you're replies! Very helpful!Quote:Original post by FippyDarkpawA 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.htmlHe 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   