Sign in to follow this  
Gumgo

Dynamic and static spatial partitioning

Recommended Posts

Hi everyone,
I'm attempting to come up with a spatial partitioning system but the requirements for this make it tricky. Here is the situation:

The world is a "continuous" map divided into square regions that load as the player approaches (I'm calling them map squares). Each map square has a terrain square and probably mostly static objects. There are some dynamic objects as well.

Basically, the trouble I'm having is figuring out how to deal with the fact that the loaded area "scrolls" as the player moves because this essentially means I can't really put bounds on the world. My current solution is to have a sort of quadtree-coarse/fine grid hybrid for each map square where insertion/removal automatically adjusts the height bounds of each cell. Objects are inserted into all map squares they intersect. However, I'm not separating static and dynamic objects, and my implementation is very slow, especially for "boundaries" where an object is in multiple map squares, and also for very large objects which affect many cells. I think this is just the complete wrong approach for something like this.

There's one more thing to complicate matters. Since really high floating point numbers are not so great to use, each object has a pair of 2 integers <x, y> representing its map square index, and its transformation is relative to that. To compare objects' positions in different map squares, first the difference between their map square indices is taken and that resulting difference is multiplied by the map square size, and that is added to the difference between their transformations. So, comparisons are not performed like this:

A = <10000.0f, 10000.0f>
B = <10120.0f, 10120.0f>
Difference = A-B;

but instead like this:

MapSquareSize = 100.0f
A = <0.0f, 0.0f>
AIndex = <100, 100>
B = <20.0f, 20.0f>
BIndex = <101, 101>
IndexDifference = (AIndex - BIndex) * MapSquareSize
Difference = A - B + IndexDifference

Anyway, the point is, there aren't really any truly "absolute" coordinates, but it's still possible to compare translations.

So here are some approaches I have though of, along with their problems:

1) Build a static octree for each map square. Insert dynamic objects into it but do not let them affect its structure.
Advantages: Only one spatial partitioning structure would be needed for everything. This means anything like occlusion culling (if that's even possible with octrees) for static geometry could also be applied to dynamic geometry.
Disadvantages: well, where to begin... There would be issues with inserting dynamic objects into multiple octrees at boundaries, which would not really be ideal. Since each octree would be "separate" from the rest, anything like occlusion culling (again, if that's possible with octrees) could only be on a per-octree basis, and would not be "scene-wide". Also, the height of the dynamic objects would be limited by the height of the octree. If a character is standing at the top of a tall hill, that might not be so good.

2) Build a static octree for each map square for static geometry only, and have a separate "boundless" structure (an R-tree? are these used much, and if so, how good are they? I know basically nothing about them) for all dynamic objects.
Advantages: The static octree could be made very efficient because it would never need to be modified. Since only one dynamic structure would exist, there would not be boundary issues inserting into multiple map squares. Updating dynamic objects would probably be fairly lightweight since there would be much fewer dynamic objects than static ones.
Disadvantages: Dynamic objects could not take advantage of the partitioning structure of the octree. It may be harder for dynamic and static objects to interact (though as long as each structure could fairly quickly perform queries on AABBs, it shouldn't be too bad). Also, the octrees still have the same problem as with the first approach: since they are separate, no real "scene-wide" operations could be performed easily. Also, I'm not familiar with any "boundless" data structures that have quick insertion/deletion and work for operations such as AABB querying and frustum culling (solution: enlighten me!).

I'm heavily leaning toward the second approach, since the first approach only seems like a slight modification to my current bad implementation. Does anyone have any ideas on this or solutions to any of the problems I mentioned? Thanks.

EDIT: Regarding approach 2, anyone seen or implemented this before?

[Edited by - Gumgo on October 2, 2010 2:42:26 AM]

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