# "AABB-terrain" occlusion culling

This topic is 2732 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Been working on a little project for a few days where I render perlin noise generated terrain as cubes (very basic at this point), split into chunks (currently 16x16x8). With a render distance of 512 it's rendering some 300.000 to 900.000 triangles per frame (no LOD at this time).

As a first optimization, I implemented an idea of my own in which I prevent back-facing triangles from being drawn while still only using one index buffer, vertex buffer and render call per chunk. Works very well, it removes some 35-70% of triangles with virtually no memory overhead.

However, I want to implement some kind of (coarse) occlusion culling as large parts of the terrain will often be occluded by the terrain itself as well as areas that might be inaccessible. Since I use "near-infinite" maps generated at run-time which are fully destructible... PVS and such is not a possibility. An obvious possibility is using GPU occlusion queries, the idea is sound, but it feels like one will be messing up the GPU rendering timings and just wasting a lot performance doing simple computations.

So, an idea I'm toying with is using the CPU to rasterize into a depth buffer for occlusion culling. Simplifying the geometry by perhaps simply only rendering chunks that are solid as a single box, or perhaps detecting which sides are solid and rendering those as quads.

From what it seems, there exists no exact methods for solving this efficiently (everything is/can be split into chunks in a fixed grid, and classifying each as either solid or empty is acceptable)... aka, I'm assuming there is no way to efficiently traverse chunks to determine all visible non-occluded chunks... or am I mistaken?

I'm sure there are a number of articles on this, I've even found one or two so far... like this one http://msinilo.pl/blog/?p=194 ... but are there perhaps other algorithms/solutions for my "simpler" scenario? I'm curious if anyone else has better ideas or some useful insight to guide me.

Here's two screenshots of the current state, graphics is quite obviously lacking right now ;) ... (the low frame rate is because of it still being busy generating terrain chunks)

[Edited by - Syranide on August 29, 2010 1:08:59 PM]

##### Share on other sites
First of all, I'd like to say that it looks very slick so far. It's a fantastic idea, rendering 3D Perlin noise with destructible boxes! May I inquire into what profiling tools (or engine) you're using? Did you make that yourself? Looks very sleek.

As for your problem, my only immediate solution, since the terrain appears fairly complex and too unpredictable to apply obvious solutions like occlusion mapping the whole grid, is to remove hidden boxes.

I would have a 3D boolean array representing each grid point in space and whether or not it should have a box (you may already have this). Then, traverse every box and check whether it is surrounded on six sides by other boxes. If so, remove it (it's obviously not visible if it's surrounded on all six sides). Note that the boolean array needs to stay intact (i.e. don't set to false just because you removed the box) for later.

This will leave you with only a "shell" of the terrain, which looks like it could speed up performance a good bit. Now, to make it destructible as well, you set it up such that when blocks are destroyed, they check their six sides and, if they find a space for which the corresponding boolean array is true but the box has been deleted (i.e. it has been culled by the aforementioned process even though the space should be filled), then that box "jumps" to the position of the culled box. In this way, destroyed boxes can fill in gaps that were created in the terrain by the culling algorithm without the user ever noticing. Obviously, if a box can find no suitable neighboring spot to jump to, it can be deleted.

This should reduce your triangle count significantly, if I understand your process correctly.

##### Share on other sites
Quote:
 Original post by XeonXTFirst of all, I'd like to say that it looks very slick so far. It's a fantastic idea, rendering 3D Perlin noise with destructible boxes! May I inquire into what profiling tools (or engine) you're using? Did you make that yourself? Looks very sleek.As for your problem, my only immediate solution, since the terrain appears fairly complex and too unpredictable to apply obvious solutions like occlusion mapping the whole grid, is to remove hidden boxes.I would have a 3D boolean array representing each grid point in space and whether or not it should have a box (you may already have this). Then, traverse every box and check whether it is surrounded on six sides by other boxes. If so, remove it (it's obviously not visible if it's surrounded on all six sides). Note that the boolean array needs to stay intact (i.e. don't set to false just because you removed the box) for later.This will leave you with only a "shell" of the terrain, which looks like it could speed up performance a good bit. Now, to make it destructible as well, you set it up such that when blocks are destroyed, they check their six sides and, if they find a space for which the corresponding boolean array is true but the box has been deleted (i.e. it has been culled by the aforementioned process even though the space should be filled), then that box "jumps" to the position of the culled box. In this way, destroyed boxes can fill in gaps that were created in the terrain by the culling algorithm without the user ever noticing. Obviously, if a box can find no suitable neighboring spot to jump to, it can be deleted.This should reduce your triangle count significantly, if I understand your process correctly.

Engine is custom-made... and not really an engine at the moment, more like a bunch of functionality cobbled together at the moment, and that profiler is actually a rather simple piece of code but serves it's purpose rather well.

Ah yes, I actually already do those things (sorry if I was being unclear). Removing unnecessary "blocks" was basically trivial, even more so than in your example, because in practice one just check the size of the vertex buffer for each block (if it's filled and surrounded, then there's no vertices), if it's empty, then there's nothing to draw. ;)

Removing and placing blocks actually already works as well, using an optimization of your method basically. So sorry if I was being unclear, but my intention was to inquire about "higher-level" occlusion culling.

Anyway, I decided to try GPU-occlusion in the end anyway (because I found this http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter06.html, currently using a variation of that) and it seemed simple enough. It's currently working beautifully, culling away some 30-90%. (I also use the aforemented solution of using index buffers with all sides being duplicated in different order, so that I can immediately discard sides/triangles that would otherwise just be backface culled, aka wasted)

My only wish right now would be some coarse block-culling to limit the amount of blocks that are sent for occlusion-testing. I'm toying with the idea of generating quads/AABBs that are as large as possible (but still within the terrain) and using them individually as coarse occluders. Although it will certainly miss a lot of occluded blocks, it could perhaps remove a lot of obviously occluded blocks for cheap before sending them to the more expensive pipeline.

Got no pictures of it at the moment as I'm at work.

(PS. LODs would obviously also be beneficial, and I intend on adding that as well)

[Edited by - Syranide on August 31, 2010 5:45:54 AM]

##### Share on other sites
Well, since I can't be of service to you, perhaps you could be of service to me :P

May I ask how you are rendering the text? My profiling display looks shameful compared to that. For example, I love the way yours has a crisp black outline so it shows regardless of screen brightness/darkness. Can you point me in the right direction as far as recreating that effect goes?

##### Share on other sites
Here's how I get the crisp black borders around my text in DX9. I just draw the text six times in black with different offsets and then one final time in yellow.

float g_FPS = 0.0f;ID3DXFont    *gameFont;void displayFPS(){    char buf[64];    sprintf(buf, "FPS = %.2f\n", g_FPS );	    long x = 5, y = 5;    RECT rect = { x, y, 0, 0 };    gameFont->DrawText(0, buf, -1, &rect, DT_CALCRECT, 0);    rect.left--; rect.right--;    gameFont->DrawText(0, buf, -1, &rect, DT_NOCLIP, 0xFF000000);    rect.top--; rect.bottom--;    gameFont->DrawText(0, buf, -1, &rect, DT_NOCLIP, 0xFF000000);    rect.top+=2; rect.bottom+=2;    gameFont->DrawText(0, buf, -1, &rect, DT_NOCLIP, 0xFF000000);    rect.top--; rect.bottom--;    rect.left+=2; rect.right += 2;    gameFont->DrawText(0, buf, -1, &rect, DT_NOCLIP, 0xFF000000);    rect.top-=2; rect.bottom-=2;    gameFont->DrawText(0, buf, -1, &rect, DT_NOCLIP, 0xFF000000);    rect.top+=2; rect.bottom+=2;    gameFont->DrawText(0, buf, -1, &rect, DT_NOCLIP, 0xFF000000);    rect.top-=1; rect.bottom-=1;    rect.left--; rect.right--;    gameFont->DrawText(0, buf, -1, &rect, DT_NOCLIP, 0xFFFFFF00);}

##### Share on other sites
Quote:
 Original post by Steve_SegretoHere's how I get the crisp black borders around my text in DX9. I just draw the text six times in black with different offsets and then one final time in yellow.*** Source Snippet Removed ***

Wow...and that doesn't kill performance??

Thanks, I'll try it.

##### Share on other sites
Quote:
 Original post by XeonXTWell, since I can't be of service to you, perhaps you could be of service to me :PMay I ask how you are rendering the text? My profiling display looks shameful compared to that. For example, I love the way yours has a crisp black outline so it shows regardless of screen brightness/darkness. Can you point me in the right direction as far as recreating that effect goes?

Funny that you ask since I got a PM asking exactly the same thing yesterday. ;)

I basically did it like Steve_Segreto does, rendering the font 8 times (although 4 is also possible for a rounder look) ... although I could easily bake the outlines into the texture instead (font is Courier I believe) since I use a bitmapped font.

If you're using high resolution fonts 6 or 8 might give the really good result, but note that you should offset the text a fixed length (normalize/sine) and not a fixed unit in multiple directions or you'll end up with uneven outlines.

##### Share on other sites
Thanks a bunch, Syranide and Steve. I'm very please with the effect and it was so much simpler than I thought!

[ sorry for hijacking your thread, Syranide, I promise I'm done here :) ]