3d spatial libraries

I’m writing a server side engine and looking at ways to track game objects in 3d space and do things like tracking ‘objects near me’. What are some good libraries for doing more advanced things like proximity searches, seeing if a point is within a region in 3d space, etc…?

Specifically, I’ve been thinking about an approach where I divide the world up into fairly small pieces, say cubes. Instead of trying to calculate all the players near an object, I track which cube each object is in as it moves through the world. Then getting objects near me becomes just reading the list of objects in adjacent cubes. Then I send the client a list of these objects with their vector, heading, and speed.

Another idea I had was that I might be able to use a mix if 2d and 3d. Say we are tracking players in the world. I record their locations in a 2d matrix, but they also have a 3d point. To get players near me I get adjacent entries from the matrix, then also do a distance calculation on every player whose z axis is outside of a certain range. The assumption being that many times, the landscape will be fairly flat.

If I’m crazy or way off base let me know. And if anyone knows some good libraries that would help me out here, that would be great!

Chris