Best solution for 2D occlusion culling

Question

In my 2D game, I have static and dynamic objects. There can be multiple cameras. My problem: Determine objects that intersect with the current camera's view rectangle.

Currently, I simply iterate over all existing objects (not caring wheter dynamic or static) and do an AABB check with the cameras view rect on them. This seems acceptable for very dynamic objects, but not for static objects, where there can be tens of thousands of them (static level geometry scattered over the whole scene).

I have looked into multiple data structures which could solve my problem:

• Quadtree

This was the first thing I considered, however the problem is that it would force my scenes to be of fixed size. (Acceptable for static, but not for dynamic objects)

• Dynamic AABB tree

Seems good, but the overhead for rebalancing it seems just too great for many dynamic objects.

• Spatial hash

The main problem here for me was that if you zoom out with the camera a lot, a huge number of mostly non-existing spatial hash buckets had to be queried, causing low performance.

In general, my criterias for a good solution of this problem are:

• Dynamic size: The solution must not cause the scene size to be limited, or require heavy recomputation for resizing

• Good query performance (for the camera)

• Good support of very dynamic objects: The computations needed to handle objects with constantly changing position should be good:

The maximum sane number of dynamic objects in my game at one time probably is at 5000. Consider they all change their position every frame. Is there even a data structure which can be faster, considering the frequent insertions and deletions, than comparing the AABBs of the objects with the camera every frame?

Kendyl

What do you mean by "fixed size"? – Laskowski

@Cicada: When you create a quadtree, you need to set a size for the root node. Changing the root node size is costly as it involves rebuilding the whole tree, and you probably don't want to do that just if some small object leaves the root node area. I think that's what he meant with "fixed size". – Shuler

Why wouldn't a spatial hash not be good enough for you? I know of at least 2 space-filling-curves and 6 variations of it that an be useful. My favourite would be a hilbert curve. Can you explain a bit your problems? I've corrected my answer because 1 curve I know is very difficult to make (moore curve). – Debbydebee

@Cicada: Maybe he means the tree height? But this is not fixed. – Debbydebee

Jitamaro: He means the size of the root node, I'm sure – Shuler

Answer 1

Don't try to find the silver bullet. Just split your scene into dynamic and static parts and use different algorithms for them.

• Quad trees are obviously suitable for static geometry with fixed bounds.

• Spatial hashes are ideal for sets of objects with similar sizes
  (particle systems, for example).

• AFAIK dynamic AABB trees are rarely used for occlusion culling, their main purpose is the broad phase of collision detection.

• And as you noticed, bruteforce culling is normal for dynamic objects if the number of them is not really big.

static level geometry scattered over the whole scene

If your scene is highly-sparse, you can divide it into islands, i.e. create a list of scene parts with "good density".

Doublequick