Add occlusion culling via rooms and portals

[lawnjelly]

Describe the project you are working on

First person shooters.

Describe the problem or limitation you are having in your project

Lack of occlusion culling giving poor performance.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Portals covering doors / windows restrict rendering into adjacent rooms to objects that intersect with the portal. This can greatly reduce the number of objects rendered, and hence increase performance.

Background

Note that this proposal concerns both 3.2 and 4.0. We are already planning official rooms and portals for 4.0, which probably reduz will do, but there is the possibility of a simple system being integrated in 3.2, depending on feedback. Much of the discussion is also relevant to 4.0, as the method of operation and user friendliness concerns are relevant to both, even if implementation details may differ.

I first wrote a room portal system 'LPortal' for 3.2 a year and a half ago, but recently have been doing a far simpler cut down rewrite, which has the potential to be available in 3.2 as an interrim measure until 4.0. This is partly driven by the availability of the new lightmapper in core, which means using simple occlusion in 3.2 is now viable for most users.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Typical room and portal systems are not fully automatic. They require the developer to manually assign their static meshes into rooms.

Mockups (in progress module)

(green lines are editor plugin showing the convex hull of the rooms, I will try changing this to transparent polys)

Rooms

The bounds of rooms are, to a large extent, defined by the objects they contain - such as tables, chairs, walls, floors and ceilings. They are usually defined as convex hulls. This both allows the visibility algorithm to work, and allows for quickly identifying whether a point is within a room. This is important in order to identify which room the camera, or dynamic objects, are within.

The convex hull can be specified manually with a mesh, or the default, which is to build a convex hull automatically from the objects within, using qhull.

Rooms need to be easily found by the room management system, currently called the room manager. It could be possible to define the rooms as spatials that are children of this manager, or to go with a system of a separate manager and define a node (roomlist) which the rooms are children of. I have gone for the latter initially because it may make importing scenes easier - see later.

(room manager node, can activate the system inside the editor)

Portals

Once rooms are defined, the user must specify portals which allow the visibility system to see between one room and the next. The visibility system is recursive - i.e. if it can see room B from room A, if it can see a portal into room C, it will also traverse into that room.

Portals are defined as convex single sided polygons, with points all sharing the same plane. The user can specify the portal location as a mesh, and it would typically cover a door or window. In many cases the portal could simply be a rectangular plane mesh.

There is no need to create a portal coming from each side of adjacent rooms, you would only need to create it in one room. The system will automatically use it in the mirror direction at runtime.

Camera

The current camera should be outside the rooms branch, and assigned in the room manager. You can either set it in the editor, or change at runtime.

Now we have everything setup to render our static scene.

Dynamic objects

There is one thing missing - we would like to have some of the objects, such as players, or rigid bodies, move, perhaps even between the rooms.

It turns out doing this in a user friendly manner that is also performant, is quite tricky. For now I've settled with a scheme where you specify a scene tree node in the manager for dynamic objects. Any meshes in this branch will automatically have their visibility altered as they move.

Note that these dynamic objects in the scene tree should not be placed in the rooms, as they are special and could be in any particular room at any time.

Importing

All this is very well, but it sounds like a lot of setup within the Godot IDE. What happens if I want to make my game level in blender, or other external editor?

The good news is this is very possible. The rooms and portals that the system use begin life as ordinary meshes. They must undergo a conversion step to convert them from meshes to rooms and portals. This can either be triggered from the Godot IDE by pressing 'Convert' button when the room manager is selected, or by script command (e.g. at runtime).

How does the system know which meshes are rooms, and which are portals? The best way I could come up with for doing this was a tagging system for the naming of the meshes. Rooms should always begin with 'room_', e.g. 'room_kitchen'. Portals should begin with 'portal_'. E.g. 'portal_lounge'. The name after the portal_ is the name of the room that the portal should link to. The link room could alternatively be automatically calculated.

Lighting

What about lighting? Well from my experience writing the original LPortal module, I found that lighting provided 90% of the difficulty, both in terms of implementation and in terms of difficulty for users. So in this rewrite I've ignored it, and assumed you will be using baked lighting. Baked lighting is an excellent match to such systems, and was used in many early games.

The reason that dynamic lighting is so problematic is that while classical occlusion only considers what is in view from the camera, objects in the camera view can be shadowed by objects that are outside of the view frustum. If these lights, and objects in between, are culled because they are out of view of the camera, the result will be a lack of shadows, followed by shadows popping into view when the objects enter the camera frustum.

You could get around this by simply rendering all the objects and all the lights for the shadowmaps, but then you would lose out on most of the performance advantages of occlusion.

While this proposal does not include support for dynamic lights, anyone interested can investigate my original lportal module, which is considerably more powerful and does offer full support for dynamic lights. The trade off is, it requires more time investment and is considerably less user friendly.

Performance considerations

In the original LPortal I offered the option of culling objects either by changing Godot visibility (show / hide), or by removing meshes temporarily from the scene tree. The latter resulted in far better performance, partly because the current hiding system does not remove objects from the octree.

With the new BVH available, I will shortly be fixing this, such that hiding objects internally removes them from the BVH, while preserving other data, which will make this process more efficient.

The other snag with removing objects from the scenetree is that users often hang physics collision shapes from their meshes. If a floor collision shape was removed when the floor was culled, you would get objects falling through the floor.

So simply changing visibility will be preferable, especially for beginners.

https://www.youtube.com/watch?v=uVwLltiouBs
(this video is from original LPortal, but new module should work pretty similar)

If this enhancement will not be used often, can it be worked around with a few lines of script?

No, requires c++ for speed.

Is there a reason why this should be core and not an add-on in the asset library?

It will already be available as a module (soon), could potentially be done in gdnative, but given the popular interest it may be worth considering having in core.

[lawnjelly]

Module

Module is now available at:
https://github.com/lawnjelly/godot-cyclops

Core & Lighting

I'll soon be having a look at how this could fit in with core. It strikes me that the major advantage of doing a core version (aside from distribution) is that using it from the visual server would far more easily allow it to be used for occlusion culling of dynamic lights as well as just the camera.

In the original LPortal module I had to use elaborate workarounds with masks to try and get dynamic lights working in any kind of efficient way. But with the portals working via visual server, this problem goes away, and the occlusion culling simply becomes a natural part of the call to cull_convex to the BVH, which returns a list of items seen from a camera or light.

This would require separation of the UI aspects in the editor from the actual functionality, which would be in / hooked from visual server, and communicate via a few extra visual server API commands. This I believe is more similar to how it was dealt with in Godot 2.0 (although I haven't looked at the source of that for a while).

I don't think this would be a massive job getting this working converting from the version in the module, so will investigate this.

Hypothetical Core functionality

If this was available via visual server, this should accelerate most use cases. The only exceptions to how much performance could be gained might be with GI probes, I don't know whether these will benefit from occlusions culling. This may turn out to be a problem in Godot 4.0 as well with GI probes and SDFGI - I don't know enough about how these work.

Plugin?

Another option which may be even better (if it can be done) is instead of inserting the portal culler directly in visual server, to insert hooks for pluggable occlusion culling, which is something we have talked about for Godot 4.0. This may or may not be feasible / a good idea but I'll have a look.

[lawnjelly]

Just to keep this updated, this is now implemented:
godotengine/godot#46130

I'm just waiting for 3.2.5 so we can start testing.

[akien-mga]

Implemented by godotengine/godot#46130.