Okay, let's back up a bit... what problem are you trying to solve, and why did you choose frustum culling as the solution to this problem?

Yes, I think you needn't worry about z-fighting between two triangles that are exactly the same (in fact they won't z-fight at all), or two triangles that are nearly the same (e.g. if your system allowed different chunks to use different transforms, then you'd be introducing some fp-error), as long as your triangles are opaque.

As Slayemin is perhaps hinting at though, there are different approaches to bounding volume hierarchies that wouldn't allow duplicate triangles at all, and there's different options other than oct-trees that might result in fewer empty/nearly empty nodes.

Just to make it clear, I think the z-fighting you'd get on redrawn triangles with fp error wouldn't be a problem as long as the triangles are opaque.

For a good menu of options with Bounding Volume Hierarchies, take a look at Chapter 6 of Real-Time Collision Detection.

Personally, I'd probably do the following - mainly because it's pretty simple to implement. Start with an AABB enclosing all the triangles in your terrain. Use some heuristic to determine a split point along one of the axes. Decide which side of the split each triangle goes on (probably according to their centroid) and construct two new child bounding boxes (they will overlap a little). Recurse down until you reach some sort of stopping point heuristic.

But there's loads of ways to skin this cat, and as long as you don't make a terrible choice (and an oct tree doesn't sound like a terrible choice to me), it's unlikely to make a huge difference in the grand scheme of things.

The basic idea is that I need to perform frustum culling on some random terrain. The best way I can figure is to cut the terrain up into 'chunks' with their own position in the vertex and index buffers and then only render out 'chunks' that are at least partially visible.

The way I am doing this is to first organize the terrain into chunks, like you do. As the next step, I calculate a bounding box for each chunk. The bounding box has 8 corners. I then test if all of these corners are outside the frustum on the same side. If so, the chunk can be ignored in the drawing. This will guarantee to never cull a chunk that can possibly be seen.

The drawback is that some chunks are not culled, that could have been culled. But the advantage is that it is a simple and quick algorithm. See my implementation at https://github.com/larspensjo/ephenation-client/blob/9f01e80144331958b57df1f494dd6a9901da10f4/Source/render.cpp#L200.

You could improve your implementation by using octrees because if you find a node is outside then all it's children are outside so you never have to test each chunk.

Thanks for the suggestion, I'll have a look into using octree for this purpose!

Edit: Doing some performance measurements, I find that my test for chunks being outside the frustum takes 4.7% of the drawing time, which is expensive.

I am using a quadtree on the server side, to find out what players and monsters are near each other, and I am fairly happy of the functionality of octree/quadtree.

The main problem I have, is that I can quite quickly identify all chunks in the frustum. But then, it is problematic to cull those that are not visible. I am using the obvious way of sorting, to draw the near chunks first. But that gives a culling rather late in the pipeline.

A trick i am using is to draw invisible bounding boxes for each chunk, and using queries to find out if they are visible. This is tricky, as you can get the result of the query immediately, or you would stall the pipeline. To help with that, I delay the result "a little". The algorihm is:

1. Draw chunk 1-20
2. Draw bounding box for chunk 41-60, with queries enabled for each.
3. Draw chunk 21-40
4. Go to 2, but all chunks are now conditionally drawn depending on the earlier bounding box query.

It is far from a perfect algorithm, and I am not very happy about it. But it improves the drawing.

It would be possible to use bounding boxes with queries for all chunks, and delay the result until the next frame. However, I don't think that will handle the case of a quickly turning camera well. It will work perfectly for a stable camera, but that case don't need good FPS anyway.

Doing performance test, my algorithm to identify chunks outside the frustum takes 4.7% of the total render time. This is a little expensive.