I have a small optimization problem in my game. If I have 10,000 objects in-game, but only 10 objects on screen (or no objects on screen), the game will lag, because what I do is I check every single frame, for every object, if the object is inside the screen or not.

So obviously as more objects are added, the slower things get. I thought about using some form of spatial indexing, so that if my camera is at (100,100), then instead of looping through 10k objects to know which are in-screen, I will simply ask my grid if there are any objects at 100,100, and do the same for neighbouring cells to get all objects inside the screen without ever having to loop, no matter if I have a thousand, or a million objects.

The problem, however, was that this doesn't account for moving objects, because if an object moves, I would have to check every frame if it has entered another grid cell or exited its cell.

So how do you detect which objects are inside the screen?

You need some form of frustum culling. I do this with an octree which seems to work pretty well. Google quadtree, octree, etc, there are tonnes of resources about it.

Essentially, you hierarchically and spatially split your game world down by symmetrical (or not in some cases) cubes (your game world splits to 8 cubes, each of those 8 cubes splits internally to 8 cubes, and so on). When you have split your world down to some manageable degree, your objects 'live in' or are somehow associated with the end nodes (aka leaf nodes, the smallest cubes).

You then do some frustum culling by starting at the root node (the encompassing box) and recursively checking down through the children of each box. If you can't see a box in your frustum then you will not be able to see any of its children (and hence any objects within it) so it can be discarded. This way you can cull thousands of objects in one simple test.

A quad tree is a simpler, 'flattened' version meaning you dissect your world into 4 cubes instead of 8, probably more useful for things like terrain geomipmapping and the like (or if your objects all reside in more or less the same y coordinate area. If its a universe-wide type game with planets you're looking to occlude, id go with an octree.

Hope that helps.

The moving object problem isn't that bad. If you think for a while, you'll realize that you'll need to update only objects which move outside of the octree node. So, as long as the object stays inside a node, you don't need to change your spatial structure.

However, depending on the octree implementation, you may need to update the loose bound of nodes (and their parents) which contain moving objects.

Otherwise, if you have objects sparsely, a simple grid might work too. The problem may be that you cannot scale up (ie. increase the visible distance) a grid space spatial structure, since the amount of grid cells increase pretty quickly.

Cheers!

In my 2d engine, this is how I chose to solve the problem:

First the interface for a generic spatial container ..

template <typename T>
class SpatialContainer {
   public:
      virtual bool insert(T item, const Range& boundingBox) = 0;
      virtual bool remove(T item, const Range& boundingBox) = 0;
      virtual void removeAll() = 0;
      virtual int getNumEntries() const = 0;
      virtual void getEntries(const Range& region, std::vector<T>& entries) const = 0;
      virtual const Range& getBoundary() const = 0;

      virtual ~SpatialContainer() {}
};

, where the Range class is just a rectangle, basically.

I made a Quadtree implementation, but you may prefer to use a simple grid instead.

template <typename T>
class Quadtree : public SpatialContainer<T> {
   // (implements the interface defined by SpatialContainer)
};

Then there's the WorldSpace class, which listens for 'entity moved' events and updates its spatial container accordingly. It only manages entities that have first been registered via a call to trackEntity().

class WorldSpace {
   public:
      inline void init(std::unique_ptr<SpatialContainer<pEntity_t> > container);

      inline void trackEntity(pEntity_t entity);
      inline void untrackEntity(pEntity_t entity);
      inline void untrackAll();
      inline void insertEntity(pEntity_t entity);
      inline void insertAndTrackEntity(pEntity_t entity);
      inline void removeEntity(pEntity_t entity);
      inline void removeAndUntrackEntity(pEntity_t entity);
      inline void removeAll();
      inline void removeAndUntrackAll();
      inline void getEntities(const Range& region, std::vector<pEntity_t>& entities) const;

      // ...

   private:
      static std::unique_ptr<SpatialContainer<pEntity_t> > m_container;
      static std::set<pEntity_t> m_tracking;

      // ...
};

Drawing all on-screen entities is then very simple:

vector<pEntity_t> visibleEnts;
m_worldSpace.getEntities(m_viewArea, visibleEnts);

for (uint_t i = 0; i < visibleEnts.size(); ++i)
   visibleEnts[i]->draw();

, where m_viewArea is the rectangle defining the view area.

If you're curious how I implemented the event system, I've written about it here.

Hope this helps

I would try first to check if your program is cpu-bound already to not make it worse by complicated sorting on cpu. Then I would use a much simpler approach and just get a rough estimate whats inside the frustum, as the graphics card can do the exact calculations and it will do them anyway.

- Just have a bounding sphere for all objects.

- Calculate the distance of all center points to the frustum one time.

- Sort all objects into 3 buckets

1. inside->test only rarely (few seconds later or whatever)

2. could get inside soon->calc time for next test from (distance-radius)/max possible velocity->save it in the object

3. maybe there are far away things where you have some extra information (get some rough estimate for lower bound of time when they could enter the frustum)

- put some pointers in a priority queue sorted by next test time

- now you just have to retest a few things per frame from the queue when the current time is near the recalculation time you have in the object

Maybe refine this later to use current velocity to get larger retest intervals or velocity vectors to check if objects are moving away from the frustum and not towards it.

That should be easier than immediately going to a complicated datastructure like an octree which you maybe dont even need and could give you problems if you need to split objects at its artificial borders.

http://blog.bwhiting.co.uk/?p=362

If you click the link on the page above to go to the demo then press the "+" key to start adding objects, you should see that you can smash though the 10,000 (not on screen but in the world) barrier no sweat barely a millisecond of time on my machine (which isn't amazing or anything)

Not to mention this is actionscript 3, EASILY 10 time slower than most normal languages.

All I am doing is fast frustum culling with caching.

see this post:

http://blog.bwhiting.co.uk/?p=355

b

On my crappy computer I get a frame rate of 8 with 10,000 objects. Also, the objects appear 'flat' and unlit; I see no evidence of normal mapping. I think my computer sucks =) .. but this actually makes me happy, because it means that the game I'm developing (in which I'm getting frame rates of around 80) must be performing very well. I think the bottleneck is the fill rate, because when I shrink the window it speeds up considerably.