Use OpenGL's Occlusion Queries to unload chunks and avoid loading chunks

[emanuele3d]

Currently all chunks within the volume defined by the ViewDistance and centered on the player are scheduled for loading and are eventually loaded. Within the volume however a number of chunks might be completely irrelevant to the player, i.e. because they are not in the immediate vicinity AND are completely occluded by other chunks.

OpenGL's occlusion queries could help by leveraging the GPU to find out chunks that are within the ViewDistance volume but are beyond some set distance AND are invisible to the player, so that they do not get scheduled for loading.

[Cervator]

Linking to #1309 which seems mildly related :-)

[emanuele3d]

Some further info/note to self:

Occlusion queries work by rendering off-screen a simplified, fast version of the scene (i.e. no shading) to verify if a given mesh is completely occluded. Crucially, the mesh used for the occlusion query and the mesh used for the actual rendering need not be the same. This means that an axis-aligned bounding box (or AABB, 12 triangles) of a chunk could be used for the occlusion query. If the AABB is visible, even by just one pixel, only then the chunk is loaded and is actually rendered.

In this context, a number of chunks near the player should be loaded immediately anyway, i.e. a 3x3x3 or a 5x5x5 volume. Then, the rest of the ViewDistance volume would initially get filled with chunk-sized AABB, visible (or not!) only during occlusion queries. If an AABB is not completely occluded, its corresponding chunk is loaded and its mesh is used for both the actual rendering and further occlusion queries, as it might unocclude further AABBs behind it.

In a typical scenario, with this method chunks deep underground or in the distance, behind large features (i.e. mountains) would not get loaded until the player moves closer to them or peeks around the obstacle. If the player is underground already, chunks in all directions might not get loaded.

Obviously occlusion queries require GPU time and this would need to be assessed to see if the CPU time and the memory saved are worth the effort.

One final note: this method only intends to provide an additional, stricter criteria for a chunk's loading. Unloading should still be purely ViewDistance-based, as unloading chunks just because a player is looking elsewhere is likely to generate to many loading/unloading operations.

[DPirate]

How about casting rays from the player and then entering the tagged blocks to render stack ? Also could you point me to where in code-base can i look into for this issue and global illumination.

It will be great if you could brief me about how global illumination is implemented in terasology. @emanuele3d

[emanuele3d]

@DPirate: thank you for your interest in this issue.

Regarding casting rays from the player: can you elaborate? Consider that at the stage we are talking about, the chunks (1 chunk = 32x64x32 blocks, 1 block = 1 cubic meter) are not in memory yet, apart probably from those immediately around the player. So, what would you cast the ray against?

In any case, a good starting point on this is the RenderableWorldImpl class. It holds the queues of chunks/meshes that are eventually rendered in WorldRendererImpl. Relevant nodes are instantiated in WorldRendererImpl.initRenderGraph(), i.e. OpaqueBlocksNode. Other important classes are the WorldProvider and the ChunkProvider, although I'm not familiar with those.

Regarding global illumination: we don't actually do Global Illumination. We use cellular-automata-like algorithms that propagate the sun/moonlight around corners and into shadowed areas. In-game lights, such as torches, are handled more "traditionally", through deferred rendering stages.

The Light Propagation aspect is something I haven't looked into. A good starting point is probably the PropagationRules interface and its implementations.

In game lights are handled into the DeferredPointLightsNode, DeferredMainLightsNode and ApplyDeferredLightingNode.

In this context you might be interested in issue #2601, which aims to integrate in-game lights withing the light propagation framework.

[DPirate]

@emanuele3d Thanks for the reply , I was thinking of loading a basic skeleton of the whole chunk in the memory(is that possible? How does world generation works? ),no need to render yet i guess, so that we know what kind of block the ray encounters while traversing. As for the number of rays, that needs to be experimented. For the traversal, its a block(uniform) world so perhaps each block's bounding box could be defined according to their coordinates.

PS : I have not done something like this before and am relatively new to OpenGL(but quite comfortable) and gamedev

[emanuele3d]

@DPirate: implied in the idea of using Occlusion Queries is the idea of using low-res chunks to see if they are visible. Given that a chunk is box-shaped the simplest low-res representation of a chunk is its bounding box I'd do tests against that.

World generation from a world designer perspective is detailed here. However, we don't have a document regarding the "bowels" of world generation, before rasterization occurs.

That's the conceptual level you need to dig in: there is a time where the engine comes up with the list of chunks to load, each chunk being defined simply by its xyz coordinates - the content of a chunk is irrelevant at this stage. This chunk list emerges from a box-shaped volume of space defined by the player position and extending according to the ViewDistance setting.

To proceed with this idea you'd need to:

1. restrict the mandatory loading of chunks to a smaller volume, say 7x3x7 chunks around the player - everything so close would always need to be loaded.
2. override the current mechanism so that chunks beyond that volume and within the ViewDistance are tagged for loading only if they are visible.

The classes to start looking into are the RenderableWorldImpl, ChunkProvider and probably the WorldProvider, but you'll likely have to expand from there. Remember to use the CTRL button in intelliJ to see where classes are used.

The visibility check is what you'd do with raycasting while I'd do it with Occlusion Queries. The engine has raycasting functionality CPU-side which would make it easy to implement but would limit the number of rays you can cast per frame as it would be relatively slow. You could find a way to do it GPU- side but you'd have to work on an efficient representation of the visible geometry and the chunks to be tested for visibility. If you go down this road it would be interesting to develop in parallel raytraced shadows as there would be considerable code-overlaps. This would be a good GSOC-sized project I'd expect.

Finally, it's ok if you don't have much experience: that's what the GSOC is for. Willingness to learn, initiative and teamplaying are far more important from our perspective.

[DPirate]

Since its(the raycasting) just to check visibility, I think all we need for block representation : position(coords) and Opacity(opaque(dirt) , non-opaque ( fences , glasses , flowers etc)), need to find where to get that data from. The ray source can be at the camera position.

If you could recommend any study material for GPU-side computing it will be great and if I can take this up as a GSOC project that would be awesome 😄

[emanuele3d]

Let me reiterate/clarify because I might have miscommunicated something:

• Currently chunks are first listed for loading depending on the position of the player and the ViewDistance setting: we don't want to load the whole universe, right?
• Then they are either loaded from disk or rasterized - either ways only then you get per-block information.

What we are discussing here is how to prevent chunks from being listed for loading well before the block data is loaded from disk or rasterized, depending if they (the chunks) are visible or not.

This implies that we have to start from the player and work outward, checking concentric "shells" made of chunks.

For simplicity let's assume the only chunk that -must- be loaded is the one the player is in. The next step is to verify the visibility of the 26 (3x3x3-1) chunks around it. For example if the player is standing on flat ground spanning the whole chunk, the chunk below it won't be visible and in this simple scenario it doesn't need to be loaded/rasterized.

The question is: given the position of the player and the blocks contained in the loaded chunks (the one the player is in), how do you determine if the chunk below is visible and is therefore worth loading/rasterizing? Notice that at this stage we don't really care what's in the chunk below. We just want to know if its bounding box is visible.

Regarding GPU-side computing:

https://www.khronos.org/opengl/wiki/Query_Object#Occlusion_queries https://www.khronos.org/opengl/wiki/Compute_Shader

Notice that the latter would be appropriate for GPU-side raytracing but you'd be limited by Terasology's code written against OpenGL 2.1. You'd either have to see if you can use an extension on capable graphic cards or fake compute shaders by using standard shaders and buffers.

Finally: I strongly recommend you find some smaller issue to work with and show your skills to the community well before the proposals for the GSOC need to be turned in. A proposal might be amazing, but if we are not reasonably confident a student can pull it off it won't get the green light.

In this context please have a look at the existing list of issues and in particular the bite-sized ones.

[DPirate]

Yes my bad, I did get a hint about it while having a look at the source code(i got pretty lost) , but i still cannot figure out how chunks are selected for loading purposes (I know viewDistance and playerposition affects it). Is it like ViewDistance creates a big box which then gets divided into chunks? If yes,

1. possible ViewDistance configs, is it relevant ?
2. division starts from where and how?

If I am going to introduce a playerChunk (7x3x7) how is it gonna affect it OR am I to restrict the chunk size constant to 7x3x7 so that all the other chunks are of that size(which i think would be better if i am to filter out chunks) .

Thoughts:-

--> Earlier on I was imagining a single big cube with lattice point (coords), representing blocks, containing only opacity properties ( only to realize later that i need to load chunks first to getBlock) , which would have made tagging easier . Is it possible to fetch position and opacity of all the blocks needed , that too efficiently? OR maybe create a compressedChunk class(having nothing more than simple block info) , possible?

--> With chunks (possibility of spacial sub-division of viewDistance box), we can check the border blocks of loaded chunks (if reached) for opacity (structure needed to identify border blocks) . Even this might need something like compressedChunk class. If done without rays, it will result in some non-visible chunks getting loaded. Seems like an exponential algo ,should not matter though since we have limited space, right? although it will pose problem in parallel implementation.

Excuse me if I am getting it wrong ,overthinking(without analyzing properly) things. I am working on my code reading capabilities.

I will surely look into the list of issues, hoping for the best :D.

[OvermindDL1]

For note, in another block engine I've used, Occlusion queries ended up being more costly that other methods, the other methods being if a renderableChunk was 'solid' on all its edges (16x16x16 blocks though it is) then doing a simple comparison from there. Later on other methods for having a cache of rays through a chunk of open areas to determine if the far face was occluded or not and updated on block change was tested, and it had a performance boost as well unless many blocks were changing often (in which case it become quite a bit slower).

For Terasology's 32x32x32 sized chunks being larger then Occlusion Queries might be more worth it, however do a lot of testing, you'd be surprised at how often it does not. If you could find out some way to determine if a chunk is solid along one of its axis then you could do an occlusion query with a single rectangle aligned to that, and that would be fast, but definitely test and benchmark in lots of conditions. :-)

[emanuele3d]

@OvermindDL1: yes, occlusion queries must be implemented carefully and their performance must be verified to avoid doing more damage than good. That been said, let's remember that often occlusion queries are used to avoid rendering more complex objects, which indeed requires a delicate cost/benefit analyses. In our case they would be used not only to avoid rendering chunks but also to avoid loading/rasterizing them. This should allow for faster world generation and longer ViewDistances. Especially after the world is first loaded/rasterized, further visibility checks as the player moves would involve considerably fewer chunks, reducing the job of the occlusion queries.

I guess the ultimate question is: will the cost of evaluating an occlusion query for a chunk's bounding box be worth the benefit of a) not loading/rasterizing the chunk AND b) not passing it to the GPU for rendering? I could be proven wrong but I suspect the answer is yes.

P.S. Terasology's chunks are 32x64x32 = 2^16 = 65536 blocks, no doubt to fit in current 32 and 64 bit memory architectures.

@DPirate:

Regarding the selection of chunks for loading purposes: yes, you are overthinking it. =)

The player position and the ViewDistance define a box centered around the player. Let's say the player is in chunk 0,0,0 and the ViewDistance is set to 3x3x3 for simplicity - think of a Rubik cube. So, one of the chunks to be loaded will be 1,1,1, while a the opposite corner of the box there is chunk -1,-1,-1. At this stage chunks are just defined by their signed integer coordinates in "chunk space". Those coordinates are then passed to the world generator that either loads the chunk from disk or rasterize it, evaluating the functions that decide, for every block in the chunk, what each block should be - grass, stone, wood. The ViewDistance doesn't quite "create" a big box that gets subdivided, it just defines mathematically a volume in chunk space from which you can deduce the list of chunks to be loaded, i.e. (1,1,1), (1,1,0), (1,0,0), ... , (-1,-1,-1).

Touching chunk size (the number of blocks in a chunk) would not be wise. So, I'm not sure what you mean with a playerChunk of size 7x3x7. What I was talking about earlier was: 1) have a box of chunks (not blocks), 7x3x7 in size and centered around the player, that gets loaded no matter what. This would allow the game to load entities such as mobs in the vicinity of the player even though he can't see them, for example because they are underground. 2) expand outward from that box to the boundaries defined by the ViewDistance (which could be 17x7x17 for example) and test the visibility of those chunks before including them in the list of chunks to load/rasterize.

Regarding obtaining opacity information efficiently: you'd have to change the way WorldGenerators work to provide a block's opacity before the chunk is fully rasterized. But right now pretty much everything gets decided at rasterization and I'd be curious to see if it is a) possible, b) efficient. So, to answer your question: it is certainly possible to obtain the opacity of all blocks in a chunk but only after rasterization, by which point the chunk is loaded.

I don't understand your paragraph starting with "If done without rays". Occlusion queries are designed to check if something is visible or not and avoid the loading/rasterization/rendering of something more expensive in its place - a chunk's blocks (in CPU memory) and its renderable mesh (in GPU memory and eventually on screen).

[DPirate]

If we can tweak WorldGenerators and get just position opacity of blocks- Then we simply proceed by loading the default chunk with player in it (playerChunk) then traversing the rest and see which all chunks have been reached by rays( each chunk will have only one face towards player) If not - Say we have loaded the basic playerChunk(chunk with player inside it ) now I have all the info of blocks inside it, after which I check the faceBlocks for opacity(if reached). If, any block on a face is non-opaque, then, load the adjacent chunk and modify faceBlockMap. This approach may result in additional memory reads thats why I wanted opacity beforehand .

[emanuele3d]

It wouldn't be a tweak, it would be a significant change. You need to study more what's under the hood of world generation before you can make an assessment of this kind.

Chunks, like blocks, are always axis-aligned. Depending on the relative position of the player a chunk's bounding box will have at least 1 and at most 3 faces toward the player - take a box, rotate it in front of your eyes and you'll see that if a corner is pointing toward you 3 faces will be visible.

In any case, I think we have hijacked this issue for too long. This issue is about using occlusion queries, not raycasting. Feel free to create a new issue and eventually a GSOC proposal if you wish to pursue that idea.

[Weilin1992]

If I'm not mistaken,the basic idea of Occlusion is never render the objects that is hidden by other objects. For example, the car behind a building should not be rendered since the player can't see the car. if one chunk is blocked by other chunks and the player can't see that chunk, we don't load it?

[Weilin1992]

@emanuele3d @OvermindDL1 what does it mean the edge of a chunk is solid & a chunk is solid?

[emanuele3d]

@Weilin1992: in response to your first question: yes. Regarding your second question, I'll let Overmind respond.

In general I think this issue has generated far too much discussion and overcomplication.

All this issue is about is to do quick renders of boxes corresponding to the bounding boxes of chunks that are geometrically relevant to the player - chunks within a volume defined by the ViewDistance setting.

Occlusion queries allow you to verify if a box has actually been rendered during a fast&cheap pass: this is a rendering that doesn't even have to store its outcome in an FBO. If a box has been rendered, we tag the corresponding chunk for loading. If a box hasn't been rendered, it means it is invisible from the point of view of the player and the corresponding chunk doesn't need to be loaded, never mind rendered.

We then continue to unload the chunks the way they are unloaded already, when the player move far from them and they are no longer within the volume defined by the ViewDistance.

Please let's refocus this discussion by keeping this context in mind. Alternatives, for example not taking advantage of Occlusion Queries, can be proposed in other issues.

[OvermindDL1]

@OvermindDL1 what does it mean the edge of a chunk is solid & a chunk is solid?

@Weilin1992 When building up a chunk renderable keep a flag of if a side of that renderable is entirely 'solid'/opaque, and store that with the renderable. Then for an occlusion call you can render a single large polygon to represent the entire side for quick occlusion testing. However if there is, say, a cave running through it then no test will be done there, however if the cave ends in the chunk and the other 5 sides are solid then it likely would not render anything behind it anyway, things like that. You can also do a quick test at renderable-generation to do axis aligned center occlusion as well.

[emanuele3d]

@OvermindDL1: how can you check for the things you are describing if the chunk is not loaded yet?

[OvermindDL1]

@OvermindDL1: how can you check for the things you are describing if the chunk is not loaded yet?

The chunk would have to be loaded.

As an example, in Minecraft if a chunk is not loaded yet then it treats it as 'solid', so it will not render things behind it (as it would cause broken terrain parts like it used to), could do the same.

[emanuele3d]

Ok, @OvermindDL1, I'm not sure where I wasn't clear enough, but this discussion is about using Occlusion Queries to avoid loading a chunk that is invisible from the player perspective.

[OvermindDL1]

Ok, @OvermindDL1, I'm not sure where I wasn't clear enough, but this discussion is about using Occlusion Queries to avoid loading a chunk that is invisible from the player perspective.

@emanuele3d Yes, exactly that. The chunk that performs the occluding (the occluder) needs to be loaded, but using it you can prevent loading behind it. And technically if you pre-calc those edge and axis flags then you can do a trivial load of that tiny bit of data and can use that to occlude without needing to load that chunk, but I'm not sure how useful that would be unless it itself was occluded. ^.^

[Weilin1992]

@emanuele3d @OvermindDL1 after several days reading the code and learning opengl, I implement occlusion culling. But it seems doesn't work well....there a some problems, so I can't pull a request.. Since tomorrow is the due to submit a proposal, I want to show what I've already done.

https://github.com/Weilin1992/Terasology/tree/Occlusion let me describe my implementation briefly 0.only do Occlusion query for opaque chunks.

1. add Occlusion query related attribute to Chunkmesh class : queryid, occlusionquerystate,occluded

   /* Occlusion Query */
    public int queryid = -1;   
    public boolean occluded = false;   
    public OcclusionState occlusionState = OcclusionState.Hidden;  

2. do fake rendering for occlusion query in WorldRendererImpl.preRenderUpdate(), render all chunks in chunksInProximityOfCamera,

   private void preRenderUpdate(WorldRenderingStage renderingStage) {
   
      // previous code
   
       renderableWorld.updateOcclusion();
   
       // this line needs to be here as deep down it relies on the camera's frustrum, updated just above.
       renderableWorld.queueVisibleChunks(isFirstRenderingStageForCurrentFrame);
   }

3. do occlusion query in queueVisibleChunks(), add visible chunks to renderQueue

               if (isChunkVisible(chunk)) {
                   if (triangleCount(mesh, ChunkMesh.RenderPhase.OPAQUE) > 0) {
                       if (!mesh.isOccluded()) {
                           renderQueues.chunksOpaque.add(chunk);
                       }else {
                           statOccludedChunks++;
                       }
                   } else {
                       statIgnoredPhases++;
                   }
             }

now the problem is after the query result is wrong, all chunk's passed samples counter is larger than 0, which means none of the chunks is occluded. There must be something wrong with my code.

This is my proposal:https://docs.google.com/document/d/1vZUu5_ohOWyDJUvKFL1IJFSOfcB2Lb9PVJxabvNtmI4/edit?usp=sharing