Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


OcTree For Randomly Generated Terrain Frustum Culling


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 James Leighe   Members   -  Reputation: 222

Like
0Likes
Like

Posted 03 November 2012 - 06:36 PM

C++, DirectX11, MSVC


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.

I figure using an OcTree sounds reasonable for this, as it could both split my terrain into chunks of no more than N polygons (then whatever triangles were inside a 'bottom level' node would be placed in a single 'chunk' and grouped into a vertex and index buffer) and allow for fast frustum culling agensed the nodes themselves.


The issue I'm having is that some triangles will straddle borders between the 'bottom level' nodes and hence be placed into more than one 'chunk'. Then, that triangle can potentialy be rendered more than once.

Would this cause 'flickering' due to z-fighting with itself or something similar? I figure it might not since it's fighting with a triangle that is exactly the same and so it dosent matter where each pixel gets picked from...


I figured I would ask because even if thats not a problem maybe there is a smarter way of doing all this!

Thanks guys.

Sponsor:

#2 slayemin   Members   -  Reputation: 2806

Like
1Likes
Like

Posted 05 November 2012 - 11:00 AM

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?

Eric Nevala

Indie Developer | Dev blog


#3 C0lumbo   Crossbones+   -  Reputation: 2399

Like
1Likes
Like

Posted 05 November 2012 - 12:19 PM

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.

#4 James Leighe   Members   -  Reputation: 222

Like
0Likes
Like

Posted 06 November 2012 - 12:02 PM

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.

#5 C0lumbo   Crossbones+   -  Reputation: 2399

Like
1Likes
Like

Posted 06 November 2012 - 12:57 PM

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.

#6 larspensjo   Members   -  Reputation: 1557

Like
1Likes
Like

Posted 07 November 2012 - 08:02 AM

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.
Current project: Ephenation.
Sharing OpenGL experiences: http://ephenationopengl.blogspot.com/

#7 James Leighe   Members   -  Reputation: 222

Like
1Likes
Like

Posted 07 November 2012 - 01:26 PM

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!

#8 larspensjo   Members   -  Reputation: 1557

Like
0Likes
Like

Posted 07 November 2012 - 03:40 PM

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.

Edited by larspensjo, 07 November 2012 - 04:02 PM.

Current project: Ephenation.
Sharing OpenGL experiences: http://ephenationopengl.blogspot.com/

#9 James Leighe   Members   -  Reputation: 222

Like
0Likes
Like

Posted 07 November 2012 - 03:54 PM

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.

Edited by James Leighe, 07 November 2012 - 03:56 PM.


#10 larspensjo   Members   -  Reputation: 1557

Like
0Likes
Like

Posted 07 November 2012 - 04:05 PM

Doing performance test, my algorithm to identify chunks outside the frustum takes 4.7% of the total render time. This is a little expensive.
Current project: Ephenation.
Sharing OpenGL experiences: http://ephenationopengl.blogspot.com/

#11 James Leighe   Members   -  Reputation: 222

Like
0Likes
Like

Posted 07 November 2012 - 10:47 PM

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




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS