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)


  • \$\begingroup\$ There's no actual question here. Are you asking if culling will be neccessary? Are you asking how to do it? Please edit your question to make it a little clearer; that way you'll be more likely to get the responses you want. \$\endgroup\$
    – user1430
    Commented Jul 11, 2011 at 14:52
  • \$\begingroup\$ I'm asking how to do it. \$\endgroup\$
    – jmasterx
    Commented Jul 11, 2011 at 14:53
  • 4
    \$\begingroup\$ You shouldn't even have O(N^2) algorithm -- you can simply test each object once against the camera's frustum and get O(N). \$\endgroup\$
    – PatrickB
    Commented Jul 12, 2011 at 0:51

2 Answers 2


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.

  • \$\begingroup\$ Keep in mind that which algorithm you use is really dependent on how many objects you have, how spread out they are, and if you even need to at all given your target platform. If rendering every object works and is more than fast enough, then problem solved. \$\endgroup\$
    – PatrickB
    Commented Jul 12, 2011 at 0:50
  • \$\begingroup\$ Nearly all the links in the answer are dead. If anyone can provide an edit with working links or archives that are functionally the same, please update. \$\endgroup\$
    – 4127157
    Commented Apr 30, 2023 at 14:15

Basically, you use collision detection to detect a collision between whatever your objects are, and a rectangle which is the current view of the camera. If the two collide, the object needs to be rendered.

In order to not have to check this for every single entity on the screen, you should use spatial partitioning structures such as quad trees to reduce the number of collision tests that you have to do.

  • \$\begingroup\$ This seems good for the static case, what about the dynamic case? \$\endgroup\$
    – jmasterx
    Commented Jul 11, 2011 at 15:08
  • \$\begingroup\$ I still think you have to use quad or kd trees (although kd trees can get unbalanced by insertion - and rebalancing can be costly afaik. (Although I never use kd-trees so I can't give detailed data). If you really have a large amount of moving objects which can collide with each other, I'd just insert and move them around in the quad tree. Otherwise, I'd just do brute force tests for rendering. It depends on the problem really, since inserting and moving around in the quad tree has a lot of overhead, but that overhead can quickly save you a lot of time in nxn-type collision tests. \$\endgroup\$
    – TravisG
    Commented Jul 11, 2011 at 16:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .