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

[jcostello]

Godot version

v4.2.dev.custom_build [9c51d22d6]

System information

Ubuntu with Nvidia 2060

Issue description

scene/3d/lightmap_gi.cpp:559 - Inconsistency found in triangulation while building BSP, probe interpolation quality may degrade a bit.

This causes some of the probes to not be linked correctly (or at all) with other probes, which causes unnatural light transition between probes (or of the probe is not connected with any other, it will transition instantly to that probe is a dynamic object pass through it, causing a unnatural result)

Steps to reproduce

Bake MRP

Minimal reproduction project

Lightmap.zip

[Calinou]

This comment explains what is happening behind the scenes:

godot/scene/3d/lightmap_gi.cpp

Lines 547 to 559 in 0ca8542

	if (best_plane_score < 0.0 || indices_over.size() == p_simplex_indices.size() || indices_under.size() == p_simplex_indices.size()) {
	ERR_FAIL_COND_V(p_simplex_indices.size() <= 1, 0); //should not happen, this is a bug
	// Failed to separate the tetrahedrons using planes
	// this means Delaunay broke at some point.
	// Luckily, because we are using tetrahedrons, we can resort to
	// less precise but still working ways to generate the separating plane
	// this will most likely look bad when interpolating, but at least it will not crash.
	// and the artifact will most likely also be very small, so too difficult to notice.
	//find the longest axis
	WARN_PRINT("Inconsistency found in triangulation while building BSP, probe interpolation quality may degrade a bit.");

[jcostello]

the artifact will most likely also be very small, so too difficult to notice.

The artifacts are very noticeable in some cases as I mention above

[jcostello]

Maybe the problem is that even when probes are disabled, there are 4 probes in the extends of the scene and Lightmap Probes are tried to be link to them (Im guessing)

[Calinou]

Maybe the problem is that even when probes are disabled, there are 4 probes in the extends of the scene and Lightmap

This is done by design as explained by the code comments in the same file. This allows probes to interpolate across the entire extents of the lightmap, so that dynamic objects always have at least one probe they can use for lighting as long as they're within the lightmap's extents.

[SpockBauru]

I may have found something new.

In the first time I baked this scene, I had just a couple of errors. Then I added some spotlights in the tunnel with LightmapProbes, got thousands of errors and the character lighting was totally inconsistent while traversing the tunnel.

The tricky part is: When I took out all the lights and probes and returned to the previews state, I still got the errors.

Now things get even worse: If I delete the LightmapGI node, the lightmap files, the folder .godot, restart the PC and add LightmapGI again the number of errors start to vary. I can get anything from 800 to 10,000 errors!

Here the scene, seems like "organic" scenes like terrains have more errors: demo.zip

My setup: Godot v4.2.rc1 - Windows 10.0.22631 - Vulkan (Forward+) - dedicated NVIDIA GeForce RTX 3080 (NVIDIA; 31.0.15.2849) - 12th Gen Intel(R) Core(TM) i7-12700KF (20 Threads)

[Calinou]

Can you test this with #82915 applied?

[jcostello]

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

[SpockBauru]

Can you test this with #82915 applied?

Sorry, I tried but the artifacts are expired:

Download artifacts
The following artifacts have expired and are no longer able to be downloaded.

Also tried the nightly link, but returned Did not detect a link to a GitHub workflow file, actions run, or artifact.

The last option, compile by myself is too overwhelming for me yet... I have to study more about SCons on Windows, MinGW-w64 and Python, never used any of those before. Sorry for that.

[akien-mga]

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

[SpockBauru]

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:

Light_Probe_Bug_edit.mp4

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

probes_bug.zip

[jcostello]

@SpockBauru thank for the MRP

Yeah I notice the error. It has to be with the triangulation or with the calculation of the closest probe as @reduz once mention. I don't have the enough knowledge to fix it

[reduz]

I am checking this, but despite the error, this does not look like a problem with the probes. It looks more like an error with the lightmapper itself.

[reduz]

Just so you understand better, if you have an issue where the probes look weird (light where there should not be any, or no light where there should be), then this is a lightmapper bug or problem.

The BSP error sometimes can appear, but I think its likely mostly harmless. This is what is used for probe interpolation in dynamic objects, so it has nothing to do with the probes looking weird.

[SpockBauru]

Sorry for the delay in response, was far from personal internet.

@reduz

The BSP error sometimes can appear, but I think its likely mostly harmless. This is what is used for probe interpolation in dynamic objects, so it has nothing to do with the probes looking weird.

The bug is not on the probes themselves, as I mentioned in the video above they are correctly lit. The bug is on dynamic objects not being correctly lit, like in the second part of the video where the capsule does not receive the probes lighting on 2/3 of the tunnel lights, which is VERY noticeable (specially on player characters).

This seems to happen because the probes are not connected correctly. In Godot 4.2 this is easy to see (Huge thanks for whoever improved the gizmos!!!) as there are no connections on the inner probes of the tunnel (just the outer probes are connected):

LighmapProbes_Bug_edit.mp4

If you need a test project I can make the repository of the video public right now, I was planning to publish once finished the documentation on next week but this is really a project stopping bug due on how characters are inconsistently lit by the probes while moving around (there was one guy on twitter where his characters appeared to flicker while running, that's how bad it is).

[BernhardMt]

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?

[permelin]

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.

[SpockBauru]

Hello @permelin, huge thanks for looking at the issue :D

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.

[jcostello]

Hey @permelin any way to solve that?

[permelin]

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.

godot/scene/3d/lightmap_gi.cpp

Lines 484 to 485 in da945ce

	//adjusting priority over least splits, probably not a great idea
	//score *= Math::sqrt(float(over_count + under_count) / p_simplex_indices.size()); //also multiply score

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%.

[SpockBauru]

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:

ProbesFixed_edit.mp4

[permelin]

Are you sure that you got #89281 too? It's wrong at the end of the tunnel that should be fixed by that PR. But it could actually be because you also want #90701 to fix everything.

[jcostello]

Maybe there is no probes at the end of the tunnel. Both part looks almost identical at the end

[SpockBauru]

Are you sure that you got #89281 too? It's wrong at the end of the tunnel that should be fixed by that PR. But it could actually be because you also want #90701 to fix everything.

You are right, for some reason #89281 is not working on my end, the probes at the center of the tunnel seems to be not connected. Also tried to compile Godot master branch but had no luck, the probes are still not (visually) connected.

Maybe I'm making something wrong, unfortunately I'm not well versed on either C++ or GitHub, I just copied/pasted the lines on the files and compiled using Visual Studio. Sorry for that.

I will double check and then test #90701 later. Here is the testing project, it's the DemoScene from my probe placement tool (LightmapProbeGrid)
LightmapProbeGrid_test.zip

[SpockBauru]

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

ProbesFixed-89281_90702_90701.mp4

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...