Sign in to follow this  
Guy Meh

Spacial partitioning that handles moving entities

Recommended Posts

I'm prototyping a space game and have been thinking about a spacial partitioning system for frustum culling. The spacial partition structure has to be able to handle moving entities such as space ships and particle effects since there's not much else (save stars in the background and heightfield terrain for planetary levels). I've read about octrees and bsps, but I get the impression that they're mostly for static level geometry. What kinds of structures can you recommend?

Share this post


Link to post
Share on other sites
kD trees work well for that. They're basically axis-aligned BSPs. You can easily rebalance a node in a kD tree by keeping in each node a total object count for each side of the current divide. When you insert an object to one side, update the count of objects for that side. Once you pass a threshold difference (#objects on + side is N greater or lesser than the #objects on - side), rebalance the divide point.

A given node encompasses a k-dimensional axis-aligned rectangular area (with +inf and -inf as valid coordinates for the further-from-0 faces of the area). Basically, it's a binary tree implementation of an octree (like how a red-black tree is a binary tree implementation of an AB tree).

You're right in that BSPs are generally for static geometry, but octrees are as good for static as dynamic scenes, so long as you have a good tree-search algorithm in place.

Share this post


Link to post
Share on other sites
As far as I know kd-trees are not good for dynamic geometry, because it can be really slow to build and memory requirement cannot be easily predicted.
Many people tend to use two different structures (i.e. kd-tree for static and BVH for dynamic).

You could give a look to BIH (Bounding Interval Hierarchy): it is a spatial subdivision tree wich has a very good construction time (close to BVH) and very good traversal time (60-70% of a kd-tree).

You can find many threads on BIH on OMPF

Hope this helps

Share this post


Link to post
Share on other sites
Hi Guy,

I'm not familiar with BIHs but I definitely agree with BVHs. They support incremental insertion and deletion, which I assume you will need as objects are added and deleted from your scene. Also, there are recent papers written on handling moving objects very efficiently.

I recommend you look at the 2007 paper "Automatic Creation of Object Hierarchies for Ray Tracing of Dynamic Scenes". To build your initial BVH, check out this.

Good luck,
Patrick
3D Blog

Share this post


Link to post
Share on other sites
This might not be particularly interesting, but do you even NEED a complex spatial partitioning system?

It sounds very low tech and very "boring", but a simple array of AABB's, and a few minutes on vectorized code, will do the job. You'd be surprised how low tech a lot of the major studios code is.

Share this post


Link to post
Share on other sites
Try googling for "TPR tree"

R-Trees consist of freely placeable rectangles, so they're ideal for a space game where quad- or octrees would either need to have a very large root node or be open to extensions in both directions (meaning the root node can become the child of an even higher root node if too many objects wander outside of the region covered by the octree).

TPR trees are a variant of the R-Tree that tracks moving objects, so you can even make a query for when in the future objects are likely going to collide.

There's also a quad-/octree variant with arbitrary axes of separation: when a node becomes too populated, it's split so that 50% of its contents are on the left side and 50% of its contents are on the right side. Do the same again for top and bottom and, if going 3D, front and back. This doesn't need a confined root node, since it only tracks axes of separation, not quadrants/octants.

For a prototyping scenario, though, why not simply use a plain list and only fix it when it becomes too slow?

Share this post


Link to post
Share on other sites
I agree with Opwiz. I've used a loose octree for a fully dynamic scene and it works like a charm. Also, if you use if for frustum culling only, you can implement the lazy version:

If an object doesn't fit in a cell anymore, move it up in the hierarchy until either it fits or it reaches a visible cell. If it reaches a visible cell, decent it back down the hierarchy until you reach an appropriately small cell OR an invisible cell. Using this method, all invisible cells are lazy and invisible objects will rise slowly to bigger invisible cells without descending back into the tree. The advantage is that invisible objects will migrate less often between cells because they stay in bigger cells. The descending is postponed until the big invisible cells become visible, so it only works if the view does only change slowly (which is normal in most games).

I implemented this lazy loose octree and it gave a very good performance with respect to the non-lazy or non-loose octree.

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