Drawing only what you can see (terrain)

Well, ive been cracking out my game (RTS genre, OpenGL) and I have a fully functional terrain engine that randomly generates terrain maps and transition textures. I can fly (player is a helocopter) around the world with the player object. The problem I have is drawing the terrain.

I have tried to setup a rectangle area that is drawn, and that area floats with the player. I have been less than successful in getting acceptable results.

My terrain has no LOD system, It is based off a procedural heightmap and is basically just an 2d array of display lists. What sort of system do you think I can implement for drawing terrain? I have considered maybe some kind of frustrum culling, but I am concerned about the cpu expense of the math involved.

While writing this I have the idea of using my current rectangle area, oversizing it and adding a check so that it only draws below a specific height. To tired to mess with it tonight, will update tomorrow.

Code:

---

void cTerrain::DrawTerrain(sDrawArea* drawArea) {
        int a,b;
       
        if(drawArea->type == DRAW_RECTANGLE) {
                RenderEngine->Translate(drawArea->x*TER_SCALE,drawArea->y*TER_SCALE,0);
                for(a = drawArea->x; a < drawArea->w+drawArea->x; a++) {
                        for(b = drawArea->y; b < drawArea->h+drawArea->y; b++) {
                                RenderEngine->DrawModel(displayMap->GetData(a,b));
                                propMap->GetData(a,b)->Draw();
                                RenderEngine->ShiftUp(TER_SCALE);
                        }
                        RenderEngine->ShiftLeft(TER_SCALE);
                        RenderEngine->ShiftUp(-(drawArea->h)*TER_SCALE);
                }
        }
        else if(drawArea->type == DRAW_ALL) {

                for(a = 0; a < displayMap->size; a++) {
                        for(b = 0; b < displayMap->size; b++) {
                                RenderEngine->DrawModel(displayMap->GetData(a,b));
                                RenderEngine->ShiftUp(TER_SCALE);
                        }
                        RenderEngine->ShiftLeft(TER_SCALE);
                        RenderEngine->ShiftUp(-displayMap->size*TER_SCALE);
                }
        }
}

---

I did a lot of playing with this kind of stuff, and my starting place was www.gamedev.net. I can't seem to get the page to display right now so I can't direct link you. There is however, a wonderful article for frustum culling that is very adequete for a begginner. You are right, the cpu expense is pretty intense (a rhyme). However, the larger your terrain, the better the pay off. If you only have a few hundered vertexs you dont really need culling any way but any larger then that and frustum culling is very useful. Check gamedev.net when you can - theres lots of super useful articles.

if it's just the terrain you plan on culling, I don't think you would have to use frustum culling(although it isn't a bad idea). You're rectangle idea will work as long as you remember to strecth it as the camera pitch changes.

The problem with the rectangle is that the terrain is so diverse that, even if I set it to draw a huge area there are still sections where I can see the edge of what is drawn.

You have to consider the height of the player, the zoom level (distance from eye to player) and then the terrain is so diverse. I just have not found a happy medium yet.

alright, its been a while since ive really taken the time to help someone, i feel its time i stepped up again ;)

heres a high level algo for a simple "rectangle" approach. Ive used this in an overhead camera terrain engine. it is simple and will render more terrain then is visible, but will cull more than enough for decent performance.

your terrain is essentailly a 2D grid of height values.

1. project your camera position on to the grid.
=> Proj( x, y, z ) = (x, z) (assuming y is up)
2. *calculate the width and height of the rectangle.
=> see below for width and heigh calcs.
3. draw the terrain
=> start at grid value [proj.x - (width/2), proj.y - (height/2)]
=> end at [proj.x + (width/2), proj.y + (height/2)]

*how to calculate width and height.
here's were your algorithm can be as simple or as complicated as you like. Since this is 3D (im assuming) your camera will be at some angle looking down on the terrain over the player. The most simple approach would be to calculate the longest visible length from the camera (ie. use the direction the camera is facing) and use that value as one half the widht and height. This would form a large square sure to cover all visible area.
To do this you essentailly just need basic trig using the distance of the camera above the terrain along with the angle it is at relative to the grid and the aspect ratio | FOV (depending on camera orientation).

ok, i made an image (with a laptop track pad :p ) to try and help explain. this assumes your camera uses only pitch and yaw ( x and y rotation ) with no roll ( z rotation ). i figured this was a safe assumption since its an RTS.

The green circle is the camera
The red arrow is the direction of the camera (this should split the black lines equally, bad diagram)
The black lines are the Field of View for the camera, intersecting the terrain at the visible boundries.
The blue line is the orthogonal projection of the camera to the terrain grid.
The helicopter is the helicopter.
a = angle camera is titlted from terrain
b = 1/2 FOV angle | aspect ratio (depending on camera orientation)
x = the distance we want to find.

let h = the height of the camera (camera.y)
since, tan( theta ) = opposite / adjacent

tan( a + b ) = x / h
x = h * tan( a + b )

define width and height as 2 * x and you have a square covering all visible area with enough culling to get decent rendering.

*note: if the height of your camera is defined by its distance above a particular point in the terrain, you could have problems with the intersection of the camera's view and the terrain at a lower point (resulting in the edge of the terrain being visible). You could either adjust the camera height by some constant (results in more terrain being rendered) or find the lowest height value (min terrain height of intersection of black lines with terrain) and use the camera's height above that height value as the 'height' variable.

Problems with this algo:
=>This simple algo assumes you dont have some crazy fish eye view (ie. the sides of the camera's view extend farther to the terrain than the actual direction of the camera).
=>it is definately not the most efficient piece of work. It is however, simple and effective.

[edit] fixed some confusing notation.

That's pretty much what I was thinking, but I didn't start thinking too hard about the math. Kudos to you sir!

Best way to do this Eber in my experience is to use a quadtree system. Each node of the tree has four neighbors. If a node has no neighbors then it is a leaf.

Here is a better explanation in code w/o the underlying quad tree structure. But this will give you the principle.

Code:

---

void QuadTree(int depth,int left,int top, int right, int bottom)
{
if ((right-left)>=depth) return;
 
int midx=(right+left)>>1;
int midy=(top+bottom)>>1;
 
//Insert code to store vertex data for this cell
//.....
 
//Recurse to get neighbors
//Top left
QuadTree(depth,left,top,midx,midy);
 
//Top right
QuadTree(depth,midx,top,right,midy);
 
//Bottom left
QuadTree(depth,left,midy,midx,bottom);
 
//Bottom right
QuadTree(depth,midx,midy,right,bottom);
 
}

---

Now on rendering find the location of the player and view frustrum in the tree by using his x,z or x,y coords depending on your setup. Here is the process:

CELL can be top left, top right, bottom left, bottom right

If the frustrum is totally outside of the CELL totally discard the CELL - else recurse deeper into the CELL.

As you will notice you can find what needs to be rendered in about 3 recursions. Let's say you have a total of 40000 vertices in your terrain grid. On the first recursion you will be able to discard 30000 vertices. Then you have 10000 left. On the second recursion you will be able to discard 10000/3 vertices and so on.

The O notation for this algo is O(log n).

This is extremely fast and also allows you to recreate the terrain mesh on each frame with little performance loss, but it does have some added complexity as opposed to brute force.

Here is a basic quadtree structure:

Code:

---

struct QNode
{
  QNode *TL;
  QNode *TR;
  QNode *BL;
  QNode *BR;
  RECT        Boundaries;
  Vertex *NodeVertex;
};

---

Note that this structure assumes that you will recurse into your tree until 1 world unit separates the vertices. If you do not wish to do that...you will need each node of the tree to hold a list of vertices - all vertices that fall within it's boundaries.

As you can see if implemented correctly...this will be extremely fast.

I think I could write a recrusive algo that would use the quadtree principals without having to change the way my data is stored, but were back to the same problem. How do you tell if a vertex is visable?

I could probably do a decent rectangle method for an overhead camera, but not for my isometric view. Thanks for the help guys.

With the quadtree algo you already 'know' what is visible. Essentially you choose a view depth, height and width which represents your frustrum. Since you know that any vertexes that lie outside of this frustrum will not be visible then you know exactly what vertexes will be visible.

To make this easier simply disregard one of the dimensions and make this a 2D problem on a terrain grid. The frustrum on the grid is simply going to be a box with extents:

Code:

---

...
RECT frustrum;
 
float viewdist2=player.viewdist/2.0f;
float viewangle2=player.viewangle-player.HFOV;
 
float viewangle_left=player.viewangle-viewangle2;
float viewangle_right=viewangle_left+player.viewangle;
 
 
if (viewangle_left<0.0f) viewangle_left+=360.0f;
if (viewangle_right>360.0f) viewangle_right-=360.0f;
 
frustrum.left=player.worldx-(cos(viewangle_left)*viewdist2);
frustrum.top=player.worldz-(sin(viewangle_left)*viewdist2);
 
frustrum.right=player.worldx+(cos(viewangle_right)*viewdist2);
frustrum.bottom=player.worldz+(sin(viewangle_right)*viewdist2);
 
//Recursively check which vertexes are in frustrum
QuadTreeCheck(MapRect,frustrum);
...

---

This creates a 2D box around the player based on the current viewangle. The extents will change accordingly with the view angle. You will probably want to pre-compute this for one orientation and simple change these values on the fly. Also this creates a view frustrum or box with the player at the center. Since all vertexes that are behind the player will not be visible...you may want to set the bottom of the view frustrum 'box' to player.worldz.

The only catch to this algo is that you must account for quads in the terrain that lie half inside of and half outside of the view frustrum. But I've found that in my code it is both simpler and faster to simply throw all the vertex data in the frustrum and let the card auto-clip the quads that fit this criteria.

This is not a major performance problem since you will only be sending at max:

((frustrum.right-frustrum.left)/cellsize)+(((frustrum.bottom-frustrum.top)*2.0f)/cellsize);

quads to the hardware to be clipped. The rest of the quads are guaranteed to be inside of the view frustrum. I'll illustrate with text graphics.

The * represent quads that might be clipped and the + are quads that will not be clipped, and the X represents the player location.

Code:

---

width
*********** h
*+++++++++* e
*+++++++++* i
*+++++++++* g
*+++++++++* h
*++++X++++* t

---

You can see from the diagram why I multiplied the bottom-top/cellsize value by 2 -> to account for the left and right sides of the frustrum that might have quads that need to be clipped. The width will only have 1 line of quads that might need to be clipped if you compute the frustrum as starting at player.worldz

Hope this helps, Eber. Tried to make it clear but not easy w/o creating some kind of diagram to show what I'm talking about.

If this is for a top down view or isometric simply change the x,y,z extents of the frustrum. For top down you would need x,y and for iso you would need a combo of x,y and z to create an iso frustrum.

You are essentially creating a bounding volume for your frustrum. I'm not a big fan of testing quads or tri's against bounding sphere's for frustrum culling. You can eliminate many many more vertexes in one pass with the quadtree method.

Hmmm... let me think about this for an iso view as that poses several new problems.