Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 3 down vote favorite
2

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

share|improve this question
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. – Josh Petrie Jul 11 '11 at 14:52
I'm asking how to do it. – Milo Jul 11 '11 at 14:53
1  
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). – PatrickB Jul 12 '11 at 0:51

2 Answers

up vote 8 down vote accepted

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.

share|improve this answer
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. – PatrickB Jul 12 '11 at 0:50
up vote 2 down vote

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.

share|improve this answer
This seems good for the static case, what about the dynamic case? – Milo Jul 11 '11 at 15:08
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. – TravisG Jul 11 '11 at 16:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.