# Screen or World Coordinates to tile Coordinates

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.

• You might want to read up about "frustum culling" on Google. You basically need to do an intersect test between the view frustum and the tiles to determine which are visible. – Nathan Reed May 20 '13 at 0:25
• I just read about that and this will definetly come in handy later, but for now, this seems not to be what i need. Frustum culling just calculates if an object is visible or not right? Since the "World" is of an infinite size, i can't test every tile if it's visible or not. – Chris May 20 '13 at 7:59
• You can generate a sphere around your frustum whose radius is calculated by dividing the far plane distance with the cosine of the FOV. You can easily figure out (or generate indices for) which tiles lie within the sphere, and then check those against the frustum. – Mokosha May 22 '13 at 7:25

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).

• Be careful to include in your matrix M, all the transforms used to convert your tiles from "tile-space" into screen-space. – axon May 22 '13 at 23:28
• Is the Matrix M the Projection matrix in OpenGL i should use for this? – Chris May 23 '13 at 7:08
• I'm sorry... i'm just not getting it. There is actually gluUnproject method which seems to do what i need. But somehow i can just get the coordinates of a point ON the near plane or ON the far plane but not on the plane where all my tiles are rendered. – Chris May 23 '13 at 16:31
• And what might dx and dy be? – Chris May 23 '13 at 17:05
• @Chris: (dx,dy) is the offset. The formula is a generic transformation between the world 2D coordinates, and the screen 2D coordinates. In OpenGL you have 3D world and "3D screen" - the gluProject function returns you winZ - the "depth" of an object. Most likely you simply discard that parameter. However when you're trying to gluUnProject, you need to supply the correct winZ nonetheless. If you supply 0, you'll get world coordinates with z!=0, probably not what you want. It seems to me it'll be easier to do the 2D transforms on your own (as opposed to solving for correct winZ). – Pasha May 23 '13 at 17:28

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.

• The Problem here is that i don't know the every in "For every tile". The information "Tile x=0, y=0 is in the view frustum" would do only half of the job since i need to determine how many tiles in x and y direction will fit on the screen. If you see the second image, how would you tell with frustum culling with which tile i need to start to render (the blue one is 0,0) and i would need to start at lets say... -28, -28 to fill the screen. How do i find this out? Maybe the answer is obvious for you but i just can't see at the moment. – Chris May 22 '13 at 11:29
• See my edited answer. – knight666 May 22 '13 at 12:49
• I don't know how to tell but thats exactly the problem. My array is actually infinity x infinity since the world is of infinite size. If the part of the world i want to render does not exist it is created on the fly. So i need to find out which part of this ridiculously large array i need to retrieve and load from the world and render it. So lets assume that there are NO TILES AT ALL at the beginning. How to find out what is the first tile i need to retrieve, load and render and HOW MANY do i need to retieve load and render. – Chris May 22 '13 at 13:10
• Specify a 0,0 and split the world in chunks from that point. Then calculate in which chunk where the camera is placed, and assume it "sees" x chunks around it. Then do the culling on each tile in these chunks. (So, don't have single array of tiles, but multiple arrays stored in chunks.) – Appleshell May 22 '13 at 18:09