3
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ You haven't mentioned: Is your game 2D or 3D? \$\endgroup\$ – Anko Oct 17 '14 at 13:51
  • \$\begingroup\$ closely related (almost duplicate) gamedev.stackexchange.com/questions/16306/… \$\endgroup\$ – jhocking Mar 16 '15 at 16:36
  • \$\begingroup\$ Many games will still run logic for entities if they are off camera, but will only do so for a limited amount of time (a few seconds). This is useful for the case when your camera moves back and forth within a relatively short amount of time - it will seem like things are still happening off screen even though they aren't. Unreal engine does this with skeletal animated models for instance! \$\endgroup\$ – Alan Wolfe Jun 14 '15 at 21:11
1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ But Calling this every frame checking if its inside the camera range it is not as expensive at drawing the image every Frame, I ask because i have no idea about computational costs. \$\endgroup\$ – Zaphyk Apr 20 '14 at 1:58
  • \$\begingroup\$ The computational costs depends greatly on the amount of items. Usually, it is cheaper to calculate what belongs to screen than just draw everything. And what belongs to screen can be computed for thousands of objects easily if you use quadtree or some other grid structure to store the entities in your world. \$\endgroup\$ – Lasse Apr 20 '14 at 2:19
  • \$\begingroup\$ quadtree? I divide the Blocks by 16x16 zones, Like Minecraft chunks \$\endgroup\$ – Zaphyk Apr 20 '14 at 3:58
  • \$\begingroup\$ Minecraft uses quadtree (most likely along with octree for the chunk blocks), yes, but the same structure fits well with 2d games too. You could also use bsp tree or simple grid to store entities. Whatever works for you. Note that this does not work well for the map, only for the entities if there are lots of them. The map works fastest with simple 2d array. \$\endgroup\$ – Lasse Apr 20 '14 at 11:17
  • 1
    \$\begingroup\$ Don't query if each tile position is inside the viewport. Query the viewport to find its tile extents, then just iterate over those specific tiles. You don't have to do expensive AABB tests for partial tiles, either; just take the floor or ceiling of the minimum and maximum extents. \$\endgroup\$ – Sean Middleditch Oct 12 '15 at 22:45
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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/

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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