I am having some performance problems with my terrain. I think I am hitting the vertex per second limit on my GPU. I am also making a lot of draw calls, but looking at the vertex per second numbers on the card's specs I pretty sure I am going over that when the framerate goes to crap.

I need to do much better culling (frustrum) which should cut the number to about 1/4 of what it was, but I am just gonna up the distance I draw on the terrain and run into the same problem again.

So basically I really need a good method for dynamically removing unnecessary vertices. I will need to implement it myself. I don't think any of the built in library stuff for meshes will apply because of my weird geometry (I am using vertex/index buffers directly).

My googling isn't turning up very much that is applicable (I mostly don't know what to search for). The majority of vertices are in flat planes so the main problem is taking a bunch tiny squares and finding bigger rectangles made up of them. I am sure there is a specific term for that but I don't know it. Also it needs to be fast, I am loading all of the terrain dynamically so speed is essential. Any tips?

When you say terrain, is this outdoors? City? Inside a building? Any culling technique you use needs to take advantage of whatever setting your 3D world is in. If it's interior there's portal culling. If it's exterior then depending on the layout, you could possibly use a bounding volume heirarchy to help work out occlusion. Maybe use level-of-detail model swapping for distant objects.

Level-of-detail would be the hardest one to implement, and give the biggest gains. It's possible to create or find some way of doing this dynamically.

Do you already have some kind of bounding volume heirarchy set up for your frustrum culling? You could run occlusion checks through that to hopefully cut out large chunks of geometry.

_________________
Whatever the mind can conceive and believe, it can achieve

Maybe my question wasn't clear. It is "outdoors" and I can do frustrum culling myself. It will help a lot, I just haven't implemented it yet. But I really need to remove these extra vertices.

I can't really use any sort of level of detail. Removing any vertices will either mess up the model noticeably (even at a distance) or not change the structure at all (those are the vertices I want to remove).

Like I said it is really weird "terrain".

I found this picture.
http://www.flickr.com/photos/apocas/3854406242/sizes/m/in/set-72157622010379421/

Its not at all to do with what I am doing but it shows the opposite of what I want. They are taking large quads and splitting them up. I want to take small quads and combine them into larger ones. That way every one I combine is "free" (at least to GPU anyway).

If two vertices are nearby, then merge them : Move A to the midpoint between A and B. Take all references to B and make them references to A. Delete vertex B. Delete degenerate polygons.

_________________
I ain't pushing no moon buttons.

So if I understand you correctly there are chunks of areas that are flat that you can combine without any loss of detail. If you have that then why don't you just remove them from the geometry entirely?

You could write a tool that would go over each quad and compute it's normal. Then you can look at chunks of 4x4 quads and see if their normals match, if they do then you can remove them and add in a new quad to cover that area.

I'm curious what your terrain looks like that you can't do some sort of ROAM, SOAR, etc LOD algorithm. Of course it's going to look worse in the distance but if it makes your game playable then it's a necessary evil.

_________________
My Development Blog | My Website | My Current 3d Engine

Thats what I want to do but it I need an algorithm to do it in realtime as I load the terrain dynamically. The terrain is also destructible so there is that too...

If each number represents a separate quad and "-" is empty, I need to turn this...

into this...

Only on a much much much larger scale. I guess the main issue is figuring out how to do it without looping through every quad.

I think that's called a cover in mathematics.

I did something similar in my RTS game (that I never completed). For me it was reducing the number of vertices in the pathing map. My algorithm was very simple, but effective.



Reading vertices from left to right (then top to bottom)
{
take the first unmarked location, and if we can extend this quad to the right, do so until we hit a boundary. Now extend it down until we hit a boundary. Merge quads and mark the locations.
}

_________________
I ain't pushing no moon buttons.

The problem with that method is that I would have to do it many times (lots of layers,textures, etc.) for every piece of terrain. I was hoping for a more elegant solution. My "terrain" is mostly empty but at the same time there are lots of adjacent reducible quads (like a sparse array of adjacent pixels of the same color in an image). I imagine the algorithm would need to be similar to real-time video encoding/compression.

Maybe you can create a heuristic that works well for your particular terrain. Divide the terrain up into a grid, with the sizes of the cells chosen as the largest size that will tend to "catch" all the flat areas. It should be quick to eliminate cells that have uneven terrain by checking adjacent vertices. You can improve the elimination by sampling a cell instead of checking its entire area, sampling can be effective if you know the usual distribution of uneven areas. Once you know which cells are flat and which are uneven, you can merge all the vertices of the flat cells together. You can get further gains by merging adjacent flat cells together into a single quad.

Do you have a screenshot of your terrain? I'm finding it hard to visualise what you're describing. At the moment, I'm imagining a largely flat area interspersed with mountainous regions. Along the lines of this ↓ but with big flat areas between the mountains.

_________________
Whatever the mind can conceive and believe, it can achieve

I think I figured it out. I can just merge quads along the x-axis as I add them and then merge along the y in a separate step while just keeping the previous strip of quads in memory, as soon as a quad is no longer touching the last strip I can output its vertices.


It is slightly less efficient with different geometry and does not find the optimal solution

Optimally it would be

But I care more about the compute time than getting the absolute minimum number of quads.

I'm still not sure how to visualise this terrain you're generating.

My original suggestion was given with the belief that there was going to be extrusion of this map out of the plane of the screen. (3D)

The algorithms we're talking about now are for covering a 2D plane with bigger quads.

If we use the latter algorithms AND have 3D extrusion, surely there are going to be gaps where the quads don't line up along their edges.

The only thing I can imagine that would work how you're proceeding would be a minecraft-like terrain, where everything lines up because everything is rectilinear.

_________________
I ain't pushing no moon buttons.

It is "minecraft-like" voxel terrain but pretty much everything related to rendering minecraft terrain doesn't apply. It is a totally different rendering technique.