Screen or World Coordinates to tile Coordinates

Question

I have Plane made of tiles in opengl. I start drawing them at (0, 0, -20) after that i do my translations so that the view is rotated somewhat similar to an isometric (kind of) perspective.

I'd now like to know, how many tiles are visible in each direction. So what i need to know basicly is, which coordinates (int the "before translation" - space) are now visible in the translated view.

The "tiles" before the translations" (for example in x direction there are 14 tiles visible):

And after the translations ( now there are 28 tiles visible in "old" x direction):

I tried to get the visible area via gluUnproject with no success.

EDIT: I already asked this question when i was trying to build the exact same thing in 2D and i got a good answer:

Calculating the number of tiles shown on an isometric map

maybe this helps to describe my problem further.

Answer 1

The problem is actually much simpler than you make it sound. Suppose wx, wy are your "world" coordinates -- that is, the native coordinates of your tiles. In order to transform that into the screen coordinates sx, sy, you apply some matrix transform. This can be written as: (sx, sy) = (dx, dy) + M * (wx, wy). You already have that equation somewhere in your program.

Now all you need to do is to invert it:

(wx, wy) = Inverse[M] * (sx-dx, sy-dy)

where the inverse for a square 2x2 matrix can be found for example on Wikipedia.

That's it. Now you can find which tile corresponds to a particular point within your window. For example in the top-left corner you have (sx, sy) = (0, 0). Plug those values into the formula above and you'll have the tile which sits in the top-left corner. Repeat for all other corners. Note that the complexity of this method is O(1), whereas the frustum culling will be at least O(n^2).

Answer 2

Although it doesn't seem like it, frustum culling is the answer here.

What you want to do is get a frustum from your view. This is determined by the screen width and height, the field of view angle and the near and far plane. Convert your view frustum to world space or your tiles to view space, depending on which is faster.

For every tile, determine if they are inside or outside the frustum. This is really simple, because a frustum is nothing more than 6 planes, so you can check a point against each of these planes. However, because your tiles are larger than a point, you'll probably have to do a check against an axis-aligned bounding box (AABB).

The frustum with AABB checks are explained here: http://zach.in.tu-clausthal.de/teaching/cg_literatur/lighthouse3d_view_frustum_culling/index.html

EDIT

Let's say you have a large array of tiles: 50 x 50.

Here's what you would do in pseudo-code:

std::vector<Tile*> tile_render;

Frustum& frustum_camera = m_Camera.GetFrustum();

for (int tile_y = 0; tile_y < 50; ++tile_y)
{
    for (int tile_x = 0; tile_x < 50; ++tile_x)
    {
        if (m_TileMap[(tile_y * 50) + tile_x].IsInside(frustum_camera))
        {
            tile_render.push_back(&m_TileMap[(tile_y * 50) + tile_x]);
        }
    }
}

Now you have a list of tiles that you can render.

The advantage of this technique is that when you have a very very large array of tiles you can chunk it up. For example, if you're dealing with 5000 x 5000 tiles, you can make 25 chunks of 1000 x 1000 tiles. First you check if the chunk is inside the frustum, and if it is, you add its valid tiles to the render list.