How to find visible tiles using a perspective projection?

This topic is 1749 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I am working on a project that uses 3D tiles, all 1 unit in size, with a top-down perspective projection (think of a typical screen aligned 2D tile map, but with a perspective projection and tiles not constrained to 2D planes). I need to be able to find the minimum and maximum row and column extents to ensure that I am drawing only visible tiles. I've considered using bounding volumes, but that would require iterating over what could be a massive data set, in which only a tiny fraction would be visible. I could use a quad tree, but even that is overkill. With a 2D tile map using a orthographic projection, finding the row and column extents is easy. Take a rectangle in pixels corresponding to the location of the viewport in the tile map and divide the extents by the width and height of the tiles. This doesn't work so well with a perspective projection.

How do I do this?

Edited by MarkS

Share on other sites

that would require iterating over what could be a massive data set

How many millions of tile instances do you have?

If memory serves last time I checked culling performance was on my Athlon XP 1800+. It could frustum-cull around 300k vertices and still have enough perf to do >60 fps. I think it would be able to cull even more but for obvious reasons, I stopped there.

I think I understand your concern however. If you don't want to use "bounding volumes" (which I suppose to be hulls), just go for aligned boxes.

Share on other sites

The levels vary in size and start out quite small, around 4x4 cells and then increase with each successive level. For testing purposes, I am testing out absurdly large levels, around 1000x1000 cells; an unobtainable level through normal game play. Right now, while testing, each tile (or cell) is just a simple textured quad. The actual cell geometry I am going to use runs around 2000+ vertices per cell, and that does not include any characters, items, etc.

I was able to get what I want by taking two vertices, each exactly 1 unit apart, projecting each with glm::project and then calculating the resulting distance between the projected vertices. This value, when divided by the view port width and height give the maximum number of columns and rows visible with that projection matrix and view port. This works, but calculating this by projecting vertices seems, in some way, hack-ish. I figure that there must be some sort of analytical way of telling how large an object will be after projection, but cannot figure out how to do so.

Share on other sites
Soo... based on your height above the field, and your fov's - calculate how many rows and colums are visible. That would be... I believe one possible answer to be (height/tan(fovx/2))*2 based on soacahtoa. Is that a less hackish answer?

Share on other sites

Soo... based on your height above the field, and your fov's - calculate how many rows and colums are visible. That would be... I believe one possible answer to be (height/tan(fovx/2))*2 based on soacahtoa. Is that a less hackish answer?

The result of that is almost exactly 1/10 of the correct value.

Share on other sites
I am sorry that it didn't work, I have to go to work right now, however if no one has posted the correct equation (I'm thinking I isolated x wrong... havnt used that math in a while) I will try again when I get home. It should be tan(fov/2) = height/x.

Share on other sites
I can't edit from the mobile site, but make sure your fov is in radians and your height uses the same unit size as your grid. So if each square is 10 units across, you should divide the height by 10 to get row number.

Share on other sites

I will outline a method I used in a similar situation, though in my case:
- The camera/projection was not constrained: it could rotate in all 3 axes.
- The tiles corresponded to a height map terrain.

1. Obtain a world-space representation of view frustum either by computing it directly with view&projection data or extracting it from a view&projection matrix.

2. Clip the segments that join the near plane to the far plane against a plane representing the minimum height of the tiles.

3. Discard the height component of the end points of the clipped segments (i.e. project the end points onto a 2d plane.)

4. With the above 2D points you can do the following interesting things:
- Compute the 2D AABB which contains the visible tiles.
- Compute a 2D convex hull containing the visible tiles.
- From the convex hull compute a minimum 2D OBB of the visible tiles.

In your case you will only want the 2D AABB and you will want to "round up" to integer extents so that you include all the edge tiles.

If the camera is constrained as you have described then the 2D AABB, 2D convex hull and 2D OBB should all be identical.

Edited by scniton

Share on other sites

First you need your perspective matrix - if you havn't created one here is some code as an example

NSMatrix4Df NSMatrix4Df::getProjectionMatrix(float fovAngle, int screenWidth, int screenHeight, float zNear, float zFar)
{
float aspectRatio = float(screenWidth) / float(screenHeight);
float zRange = zNear - zFar;
float usefulNum = tanf(DegreesToRadians(fovAngle) / 2.0f);
NSMatrix4Df projMat;

projMat.value(0,0) = ( 1.0f / (aspectRatio * usefulNum) );
projMat.value(1,1) = ( 1.0f / usefulNum );
projMat.value(2,2) = (-zNear - zFar) / zRange;
projMat.value(2,3) = (2.0f * zFar * zNear) / zRange;
projMat.value(3,2) = 1.0f;
projMat.value(3,3) = 0.0f;

return projMat;
}


NSMatrix4Df is just a class representation of a 2x2 array ( [4][4] ) and value(x,y) is the same thing as matrix[x][y].

If you already have your perspective matrix then you need to have a world space transform for each one of your tiles you want drawn on the screen based on their position, scale, and orientation in world space. Here is some showing how to create these tranforms..

NSMatrix4Df NSMatrix4Df::getRotationMatrix(float xAxisAng, float yAxisAng, float zAxisAng)
{

NSMatrix4Df xRotMat;
NSMatrix4Df yRotMat;
NSMatrix4Df zRotMat;

return zRotMat * yRotMat * xRotMat;
}

NSMatrix4Df NSMatrix4Df::getTranslationMatrix(float xMove, float yMove, float zMove)
{
NSMatrix4Df identity;
// set the fourth column of the matrix to the translation amount
// the rest of the matrix is the identity matrix
identity.setColumn(NSVec4Df(xMove,yMove,zMove,1),3);
return identity;
}

NSMatrix4Df NSMatrix4Df::getScalingMatrix(float scaleX, float scaleY, float scaleZ)
{
NSMatrix4Df identity;
// replace 1s in identity with scaling factors here
identity.value(0,0) = scaleX;
identity.value(1,1) = scaleY;
identity.value(2,2) = scaleZ;
return identity;
}


I should also mention that the NSMatrix4Df class initializes the matrix with the identity matrix - as shown below

NSMatrix4Df::NSMatrix4Df():rows(MATDIM4D),
columns(MATDIM4D)
{
data[0][0] = 1.0f; data[0][1] = 0.0f; data[0][2] = 0.0f; data[0][3] = 0.0f;
data[1][0] = 0.0f; data[1][1] = 1.0f; data[1][2] = 0.0f; data[1][3] = 0.0f;
data[2][0] = 0.0f; data[2][1] = 0.0f; data[2][2] = 1.0f; data[2][3] = 0.0f;
data[3][0] = 0.0f; data[3][1] = 0.0f; data[3][2] = 0.0f; data[3][3] = 1.0f;
}


So now for each tile you want to draw to screen space you need to
multiply projMat * TranslationMat * RotationMat * ScaleMat * (your tiles position in 3d space)

If you had all that then that's great - you can use these tranforms to find clipping space for the screen.

This, by the way, is assuming you dont have a camera in place yet. If you do you need to make sure and insert the camera transform between the projMat and the TranslationMat.

If you have these matrixes you can take the position of your tile in x,y,z,w (for example 2,6,10,1) and multiply it by all of your matrixes. The result will be a four dimensional vector (x,y,z,w). You then need to divide that vector by its w because the opengl pipeline won't be doing it for you.

And now you can check the resulting 4 dimensional vector - if ( x < -1 || x > 1 || y < -1 || y > 1) then don't draw the tile.

Just as an aside - I hope you are using shaders for the draw operations, and then I hope you are using buffers to store your verts and indices. If you are going to have a bunch of the same tiles I would suggest learning about..

glDrawElementsInstanced(GL_TRIANGLES, indices.size(), GL_UNSIGNED_INT, 0, translationMatrixes.size());


- drawing your tiles instanced could very well be the way to go here. A lot of advantages. Something to think about.

Edited by EarthBanana

Share on other sites
EarthBanana, what you seem to be suggesting is that I project the tiles and then cycle through them to find which are visible. This is terribly inefficient. What I am doing now is to project two vertices that are exactly 1 unit apart and measuring the distance between them. That gives me the exact size in pixels of an object after projection with the mvp matrix. After this, I divide the width and height of the view port by this value to get the exact number of rows and columns that are visible in the viewport. I then get the row and column of the tile in the center of projection. With this information, I can tell which columns are visible at the right and left sides of the view port and which rows are visible at the top and bottom of the view port. This result is exact. The tiles drawn are guaranteed to be visible with no false positives. The projected size of the tile, along with the row and columns extents only need to by calculated when the field of view or view port changes and can be stored. I only need to do about 4 divides and a few comparisons per frame.

What I *want* to do is two fold:

1.) I want to take the mvp matrix and determine the projected size without having to do the projection.
2.) I want to be able to calculate the field of view required to display a tile at a set size, say 256 pixels.

As MichaelNIII stated, this should be possible with soacahtoa. However, nothing I have done has worked. I can get the distance between the view point and the object from the mvp matrix (mvp[2][3]). Let's say that I want the tiles to be 256x256 pixels. According to soacahtoa, the field of view should be: 128/5(the distance in my case)*2. This doesn't work. The correct value is approximately 43.5113 degrees, found through testing, not the 51.2 degrees arrived from 128/5*2.

Equally, I should be able to tell the width in pixels by: ((5 / tan(60 / 2)) * 2) * 10(still not sure why 10 is necessary...). Once again, it doesn't work. The correct value, found by projection, is exactly 176.959 pixels, not 173.20 pixels.

My best guess is that the problem lies in that the distance is in units, not pixels. I would need to convert the distance to pixels or the pixel size to units. I'm not sure how to do this, or even if it is possible.

Unless someone can explain what I'm doing wrong, I am just going to stick with what I have. Edited by MarkS

Share on other sites
I am using degrees, but am converting to radians.

tan(0.5235) = 0.57735
5 / 0.57735 = 8.66025
8.66025 * 2 = 17.32050 Edited by MarkS

Share on other sites
I'm sorry. I feel like a tard. Anyways. X = (tan(fov/2)*height)*2

Share on other sites
I was looking at my projection matrix and noticed that the location[0][0] was exactly 1/100 the correct projected tile width. Looking at glm::perspective, I came up with this:

range = tan(fov / 2) * z_near;
right = range * aspect;
left = -range * aspect;
width = ((2 * z_near) / (right - left)) * (z_far * z_near);

I would still like to know how to get the fov from the projected size.