3d Occlusion Culling

Question

I'm writing a Minecraft like static 3d block world in C++ / openGL. I'm working at improving framerates, and so far I've implemented frustum culling using an octree. This helps, but I'm still seeing moderate to bad frame rates. The next step would be to cull cubes that are hidden from the viewpoint by closer cubes. However I haven't been able to find many resources on how to accomplish this.

Strategist

You've read about z-buffers? de.wikipedia.org/wiki/Z-Buffer – Infernal

@Thomas: you might mean en.wikipedia.org/wiki/Z-Buffer :) – Embed

I have read briefly about them, but not enough to know how to use them. I'll have to read more. – Strategist

Sorry and thanks @Matt :D just copied and didn't worry about the language. – Infernal

Z-buffering isn't going to help you reduce the amount of geometry you're pumping to the graphics card. In fact, unless you're sorting back-to-front, you're using Z-buffering already. – Pretentious

Answer 1

Create a render target with a Z-buffer (or "depth buffer") enabled. Then make sure to sort all your opaque objects so they are rendered front to back, i.e. the ones closest to the camera first. Anything using alpha blending still needs to be rendered back to front, AFTER you rendered all your opaque objects.

Another technique is occlusion culling: You can cheaply "dry-render" your geometry and then find out how many pixels failed the depth test. There is occlusion query support in DirectX and OpenGL, although not every GPU can do it.

The downside is that you need a delay between the rendering and fetching the result - depending on the setup (like when using predicated tiling), it may be a full frame. That means that you need to be creative there, like rendering a bounding box that is bigger than the object itself, and dismissing the results after a camera cut.

And one more thing: A more traditional solution (that you can use concurrently with occlusion culling) is a room/portal system, where you define regions as "rooms", connected via "portals". If a portal is not visible from your current room, you can't see the room connected to it. And even it is, you can click your viewport to what's visible through the portal.

Autolysis

Note that z-buffering is a good way to avoid doing unnecessary fragment (pixel) operations (computing the color of a fragment, doing a texture lookup, lighting, etc.) but if possible it's better to simply skip geometry that isn't visible (and avoid doing transformations on vertices that won't contribute to the final image), like you're doing with view frustum culling. – Toussaint

For that, there is occlusion culling. I should edit my answer to touch that topic. – Autolysis

Answer 2

The approach I took in this minecraft level renderer is essentially a frustum-limited flood fill. The 16x16x128 chunks are split into 16x16x16 chunklets, each with a VBO with the relevant geometry. I start a floodfill in the chunklet grid at the player's location to find chunklets to render. The fill is limited by:

1. The view frustum
2. Solid chunklets - if the entire side of a chunklet is opaque blocks, then the floodfill will not enter the chunklet in that direction
3. Direction - the flood will not reverse direction, e.g.: if the current chunklet is to the north of the starting chunklet, do not flood into the chunklet to the south

It seems to work OK. I'm on android, so while a more complex analysis (antiportals as noted by Mike Daniels) would cull more geometry, I'm already CPU-limited so there's not much point.

I've just seen your answer to Alan: culling is not your problem - it's what and how you're sending to OpenGL that is slow.

What to draw: don't render a cube for each block, render the faces of transparent blocks that border an opaque block. Consider a 3x3x3 cube of, say, stone blocks: There is no point drawing the center block because there is no way that the player can see it. Likewise, the player will never see the faces between two adjacent stone blocks, so don't draw them.

How to draw: As noted by Alan, use VBOs to batch geometry. You will not believe how much faster they make things.

An easier approach, with minimal changes to your existing code, would be to use display lists. This is what minecraft uses.

Neona

Answer 3

How many blocks are you rendering and on what hardware? Modern hardware is very fast and is very difficult to overwhelm with geometry (unless we're talking about a handheld platform). On any moderately recent desktop hardware you should be able to render hundreds of thousands of cubes per frame at 60 frames per second without any fancy culling tricks.

If you're drawing each block with a separate draw call (glDrawElements/Arrays, glBegin/glEnd, etc) (bonus points: don't use glBegin/glEnd) then that will be your bottleneck. This is a common pitfall for beginners. If you're doing this, then you need to batch together all triangles that share texture and shading parameters into a single call for each setup. If the geometry is static and doesn't change frame to frame, you want to use one Vertex Buffer Object for each batch of triangles.

This can still be combined with frustum culling with an octree if you typically only have a small portion of your total game world in the view frustum at one time. The vertex buffers are still loaded statically and not changed. Frustum cull the octree to generate only the index buffers for the triangles in the frustum and upload those dynamically each frame.

Dogmatize

I'm drawing ~ 250,000 1x1x1 cubes before frustum culling, on a modern system (Gefore 8800 GT, dual core, 2GB ram). With frustum culling, I'm getting a frame rate of 17.83fps, versus ~2fps without frustum culling. The actual drawing of cubes is done through an interface provided, but from what I can tell, they are being drawn using glPush/PopMatrix and glutSolidCube. – Strategist

glutSolidCube is your problem. You are bounded by all the state changes to draw 250,000 cubes, one at a time. Under 1000 objects would be a typical limit to run at reasonable speed. – Dogmatize

Answer 4

If you have surfaces close to the camera, you can create a frustum which represents an area that is not visible, and cull objects that are entirely contained in that frustum. In the diagram below, C is the camera, | is a flat surface near the camera, and the frustum-shaped region composed of . represents the occluded area. The surface is called an antiportal.

        .
       ..
      ...
     ....
    |....
    |....
    |....
    |....
C   |....
    |....
    |....
    |....
     ....
      ...
       ..
        .

(You should of course also turn on depth testing and depth writing as mentioned in other answer and comments -- it's very simple to do in OpenGL.)

Toussaint

This can be a great technique, but I think it's important to add that it should only be done for obscuring objects that you know ahead of time are likely to obscure a large amount of the world from the frustum. Going overboard on antiportals can just make things slower. – Dogmatize

Answer 5

The use of a Z-Buffer ensures that polygons overlap correctly.

Enabling the depth test makes every drawing operation check the Z-buffer before placing pixels onto the screen.

If you have convex objects you must (for performance) enable backface culling!

Example code:

glEnable(GL_CULL_FACE); glEnable(GL_DEPTH_TEST); glDepthMask(GL_TRUE);

You can change the behaviour of glCullFace() passing GL_FRONT or GL_BACK...

glCullFace(...);

// Draw the "game world"...

Plaintiff