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.