c++ - Culling for a 2D, platformer game?

By culling, I mean, only rendering what is currently seen by the camera. In my game, nothing is tile based. Each object has a center point and that is where it is on the screen. The camera is simulated by doing glTranslatef before drawing anything on that layer.

Here are the constraints:

I have 6 layers. Each of these is an array of IRenderableEntity. Each layer has a scalar that it multiplies the camera position by to simulate Parallax Scrolling. Within these arrays, the object itself could be static or dynamic.

I'm not concerned with collision detection since Box2D takes care of this.

How can I only render what I see on the screen in a logerithmic manner (not n^2)

Thanks

Answer

There are plenty of resources for culling techniques of this nature -- ideal search terms include phrases like "2D culling quadtree" and "2D spatial partitioning."

A basic approach will use frustum culling (the link describes a 3D approach, but in 2D this boils down to basically a rectangle-in-rectangle test) and a quadtree to partion space hierarchically -- the hierarchical approach allows you to trivially reject large batches of objects, testing only those that are near the viewable area. As long as you update the spatial partitioning structure as objects update, this is suitable for dynamic scenarios as well as static ones.

You may also be interested in this article on an alternative approach (although its old), or this article on using the slightly-more-advanced kd-tree for partioning space. See here for a handful of other scene management structures.