• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
jamesleighe

OcTree For Randomly Generated Terrain Frustum Culling

10 posts in this topic

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.
0

Share this post


Link to post
Share on other sites
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?
1

Share this post


Link to post
Share on other sites
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.
1

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
1

Share this post


Link to post
Share on other sites
[quote name='James Leighe' timestamp='1351989415' post='4997031']
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.
[/quote]

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 [i]on the same side[/i]. 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 [url="https://github.com/larspensjo/ephenation-client/blob/9f01e80144331958b57df1f494dd6a9901da10f4/Source/render.cpp#L200"]https://github.com/larspensjo/ephenation-client/blob/9f01e80144331958b57df1f494dd6a9901da10f4/Source/render.cpp#L200[/url].
1

Share this post


Link to post
Share on other sites
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!
1

Share this post


Link to post
Share on other sites
[quote name='James Leighe' timestamp='1352316415' post='4998535']
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.
[/quote]

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 [url="https://github.com/larspensjo/ephenation-client/blob/9f01e80144331958b57df1f494dd6a9901da10f4/Source/render.cpp#L227"]algorihm[/url] 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
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
Doing performance test, my algorithm to identify chunks outside the frustum takes 4.7% of the total render time. This is a little expensive.
0

Share this post


Link to post
Share on other sites
You will also have to allocate the OcTree nodes either using an allocator or something like that to prevent cache trashing.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0