OcTree For Randomly Generated Terrain Frustum Culling

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.

Thanks for the replies.

I think I might end up letting the different chunks have their own position matrix because its more natural in my engine ATM but if that causes flickering on the redrawn triangles from fp error I suppose I'll make some special case.

Also the problem I'm trying to solve with frustum culling is generating a potentially visible set given your current view frustum to reduce both batch count and vertex shader overhead. Obviously it's pretty rough but it removes enough terrain and objects that we know can't possibly be seen for my purposes.

What other data structures are there that I could use besides octrees?
I thought about using like bsp but as far as my understanding of them goes they would not be any better and seem slower as they store things at a triangle level and I would then have to fill vertex and index buffers before sending them off to the graphics card which is slow compared to the octree solution of ready to go chunks.

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.

Also octrees are simple.

I would also use the 'radar' method to test if a node/box is visible as it is the fastest. The 'radar' method is detailed in one of the various game gems books by I'm sure googling it would work.

Thanks for all your replies everyone!

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.

All you have to do is walk down the OcTree and find what chunks are visible then put those in a list and sort if you want then draw them.

If you're talking about removing chunks that are hidden by some object/other-chunk but technically within the frustum that's a pretty hard problem to solve in general and often requires a pre-process step. Are you talking about rendering bounding boxes and reading back the back-buffer?

Either way culling non-viewables is beyond my experience level as I have not had a project that would benefit from that granular a level of culling.

EDIT: I also want to mention there is nearly no overhead in the pixel pipeline to z-reject pixels, you still have to pay for their transformations in the vertex stage however but that's probably light.

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

You will also have to allocate the OcTree nodes either using an allocator or something like that to prevent cache trashing.