godot: Vulkan: Baking LightmapGI results in dozens of "Inconsistency found in triangulation while building BSP" messages

Below are two changes that together removes pretty much all warnings. I would really appreciate feedback from a maintainer or someone else with experience of these things.

One very easy adjustment is to increase the tolerance used with Plane::has_point() in LightmapGI::_bsp_get_simplex_side() 7x from 0.00001 to 0.00007. This increase offsets the lack of precision in Vector3 in scenes up to 1000m that I’ve found. It’s still a very small distance and I don’t think it’ll cause false positives, and even if it did in some rare cases, I’m not sure it matters?

I picked 0.00007 because the error is seemingly always a multiple of 2^-16, with the largest error in my test scenes being 2^-14, which is 0.0000610352. Not the most rigorous way to pick a tolerance, but I assume that there wasn’t a lot of theorycrafting behind the current value either.

This change decreases the number of warnings in SpockBauru’s scene from 3715 to 4. It does however nothing to improve the 180 warnings in jcostello’s scene, since that one is quite small.

As for the remaining warnings, there’s actually a solution already in the code! But it’s commented out, with a warning about probably not being a great idea. I hate to bother @reduz but since he wrote it, it would be great to get his input. https://github.com/godotengine/godot/blob/da945ce6266ce27ba63b6b08dc0eb2414594f7cb/scene/3d/lightmap_gi.cpp#L484-L485

Background: The BSP tree sorting recursively goes though the planes of the tetrahedra to find a plane that divides the remaining tetrahedra into two groups as evenly as possible. It gives each plane a score, and the more equal the number of tetrahedra that fall on each side, the higher the score. Tetrahedra that intersect with the plane are not counted at all in the score.

One “problem” (?) with this system is that a plane can for example have one tetrahedron on each side while intersecting 20, and still get a perfect score because 1/1 is a perfect balance. The remaining 20 are then put into both the over and under branches of the tree. This often creates a rather large tree. For example, jcostello’s scene has 2184 tetrahedra but the BSP tree has 116590 nodes.

The line that is commented out in the code changes the scoring of planes to penalizes them based on how many tetrahedra they intersect (and hence fail to separate). I guess that the risk is that this creates a less balanced tree, but on the half dozen scenes I’ve tested with, this doesn’t seem to happen. jcostello’s scene for example had min depth 13, max depth 25 before, and after this change min depth 12, max depth 18.

Besides creating smaller trees, a bonus to this change seems to be that it stops the sorter from making decisions that it can’t resolve later further down the tree.

Uncommenting this line reduces the 180 warnings in jcostello’s scene to 6 and shrinks the tree by 87%. It also removes all remaining warnings in SpockBauru’s scene except one.

Just because the warnings are gone doesn’t automatically mean that it’s an improvement in how it performs. I don’t know how to objectively test this. The fallback we get when there is a warning is likely an okay compromise in many situations, but I believe that it can also be very wrong for certain cases. Avoiding it seems like a win to me.

I also tried a much more aggressive version that squares the penalty instead of using its root. With that I don’t get any warnings at all in any scene I’ve tested, and it shrank the tree by another 50%.

I’ve looked into this a bit and I think I’ve found three different relevant issues. Two are about the BSP warnings and the third one likely explains why some probes are not connected.

Two issues are specific to scenes that cover a large area.

Once you go beyond a few hundred meters, I find a lot of tetrahedra where Plane::has_point() starts giving false negatives and Plane::is_point_over() can return a mix of true and false for points that were used to construct the plane in the first place. The result is tetrahedra that (falsely) appear to be concave, and as a consequence BSP sorting breaks down and you get these warnings.

(A tetrahedron is a group of four connected probes.)

In a scene with nothing but a single 500x500x5 meter mesh and a lightmap, I get 46 warnings due to this.

I don’t know what size it’s reasonable for a single lightmap to support? The project uploaded by @SpockBauru for example is roughly 1000x1000 meters.

At that size, another issue is that the Delaunay3D pruning of coplanar tetrahedra seems to be more aggressive. It will remove ones that I’m fairly certain would have survived in a smaller scene.

In SpockBauru’s project, 1788 tetrahedra were pruned, which is probably why there are 190 probes that are not connected at all. I suspect that this is what is causing most of the actual problems with incorrect lighting in that scene. (Together with an completely different bug where dynamic GI didn’t update at all in half the tunnel. I’ve already fixed that in #89281)

Even small, room sized lightmaps get many BSP warnings, but the issue here looks quite different. I’ve exported a bunch of cases into Mathematica and looked at them there. It always comes down to separating two tetrahedra that look something like this:

The long diagonal black line is the plane that I guess in theory should separate the two tetrahedra, but that fails by a small margin. Of the 20+ failing cases I’ve randomly picked from different scenes, every single one have had a flat-ish tetrahedron, and always with a tiny overlap. I don’t know if Delaunay is supposed to guarantee that this does not happen, but it does have the look of either a precision issue or maybe a margin applied in the wrong direction.

Seems reproducible in 4.1.3-stable too (just to clarify this isn’t a 4.2 regression, thus not a release blocker).

Purged my local fork and manually added line by line of #89281, #90702 and #90701 on 4.2.3 code. Results are flawless!

https://github.com/godotengine/godot/assets/67930504/6632854f-92dd-4eee-974d-ddcc40bb929d

Here are some findings:

#89281 don’t make any changes on my test scene, but seems safe to cherry pick to 4.2.3. #90702 the file scene/3d/lightmap_gi.cpp on master is kinda different from 4.2. I don’t know how GitHub will handle this but manually adding just the PR code fixes many issues. #90701 the file core/math/delaunay_3d.h on master is already better than 4.2, and adding the PR improves to near perfection. Once the PR is merged, backporting the whole file to 4.2.3 seems to be safe.

Here are the files from all 3 PRs that I used, the base code is yesterday’s 4.2.3.rc just with the PRs added: permelin_ProbesFixes_4.2_backport.zip

Feel free to make a PR to 4.2 with those files since I have no idea how to do that…

Is that possible to cherry pick #89281 and #90702 to 4.2.3?

I’ve manually applied both to my 4.2.3 fork (updated today) and results are really impressive! A HUGE thanks to @permelin \o/

The following video compares the “vanilla” 4.2.2 (from Godot site) with Github’s 4.2.3 having only both PR applied. Note how much consistent the illumination on the character is now:

https://github.com/godotengine/godot/assets/67930504/f3e5c5dd-52c4-43a4-8168-f2fe36f2ede9

I’m also experiencing this problem on a project I’m currently working on in Godot 4.2 stable. I think it only effects custom placed lightmap probes, the auto generated look fine so far. Like described above the probes themself look correct but once I bake with custom probes there are several thousand inconsistency warnings and a lot of missing connections between the probes. I guess the missing connections are then causing the flickering of the character when moving through the level because it is interpolating between the wrong probes?

Hello, after two weeks I finally managed to understand how to compile Godot. Luckily it compiles in less than 10 minutes on my machine but unfortunately the issue remains on #82915.

I’ve also tested all way back to Godot 4.0 stable (the first with probes, I guess?) and the problem is also there.

Because of this bug the light probes are completely broken on terrain-like scenarios.

On the following tunnel test (using 4.2 stable) the spotlights are enabled before baking and disabled after baking, this way the player will only receive the illumination from the probes.

In the first part of the video, you can see that the probes themselves are receiving the light information correctly but in the second part the player is dark on the first two lights and only receive probe information from the last one:

https://github.com/godotengine/godot/assets/67930504/36ff60cf-5a12-4461-91f4-593daececca2

Here the reproduction file. be aware that due the unpredictability of the bug your results may be different:

probes_bug.zip

@Calinou I test it before in the TPS Demo. Tringulation errors have nothing to do with probes cache

Hello @permelin, huge thanks for looking at the issue 😄

About the terrain size, 1000x1000 meters is the standard size for terrain generators. For other engines and also Godot plugins such as Terrain3D this is the default size for each chunk of terrain called tile.

The usual approach is to load and unload terrain tiles according each game’s LOD system, which can be open worlds or racing linear tracks (not circuits) usually up to 16km total (16 tiles on an straight road) in the worst case.