How do I efficiently determine what objects are visible to a camera?

Question

I want to call the rendering methods of only the game objects that are visible. How can I efficiently determine which objects or tiles are within the camera's rendered region?

Answer 1

You are talking about tiles, therefore i'm assuming you are talking about a 2d game.

You need to have the camera position in the world like so:

int cameraX = 0;
int cameraY = 0;

You also need to have the camera size, which is usually the same as your viewport size:

int cameraWidth = viewportWidth;
int cameraHeight = viewPortHeight;

Then you can find out if a quad is inside the camera by using simple AABB collision check:

public boolean isInsideCamera(int x, int y, int width, int height) {
    if(x < cameraX + cameraWidth && x > cameraX) {
        if(y < cameraY + cameraHeight && y > cameraY) {
            return true;
        }
    }
    return false;
}

NOTE: The above example only works if the quad is completly inside camera. For proper AABB intersection, try here: What is the fastest way to work out 2D bounding box intersection?

Answer 2

If the tiles are stored in a linear way( sorted so that the top left tile is first and the bottom right is last, or some other reasonable order ), you can access the array / list by an index that describes tiles that only lay within the screen bounds. This will be a bit faster than doing a bounds check every tile.

Tile[,] tiles = new Tile[x,y];

We can now access the tiles in this way:

for( int x = camera.x / tileWidth; x < ( camera.x + camera.width ) / tileWidth; x++ )
{
    for( int y = cameray / tileHight; y < ( camera.y + camera.height ) / tileHeight; y++ )
    {
        // Access the tiles that are in the screen here.
    }
}

I believe this may be the fastest way we could do it. If the tiles aren't in an array, however, you can use the bounds checking method described by Lasse. If that's not fast enough, you could use a quadtree. This data structure allows use to quickly check where things are in the world.

Read about it here: http://en.wikipedia.org/wiki/Quadtree

It's a pretty simple structure to create and helps in far more than just object culling.

Answer 3

Your question doesn't specify 2d or 3d but if it's 2d the best way would probably be to use a spatial hash map. Essentially a spatial hashmap stores objects in buckets like a usual hashmap, but instead of storing based on a hash it stores based on it's position in space. Objects that span multiple buckets are placed in every bucket they overlap. so because things that are near each other are stored in the same bucket you can just pass in a position and get the objects near it. Check out this article on spatial hash maps for more info: https://www.gamedev.net/articles/programming/general-and-gameplay-programming/spatial-hashing-r2697/

Answer 4

You could always start with frustrum culling as it's quite simple to implement and fairly straight forward via extracting the information you already need to compute (your model view projection matrix). It doesn't account for objects which may be blocking your view, but it would provide the correct geometric approach. If a vertex passes your frustrum culling, it is guaranteed in your field of view.

Also, the SIMPLEST test would be to get the signed distance from the object in question to the plane formed by your camera's position and view direction. Obviously, if the dot product is negative with all vertices, then it's in the opposite direction and can't be seen.

Otherwise, I recommend using a balanced bounding-volume hierarchy.