Pre-calculate `is_visible_in_tree()`

[lawnjelly]

trafficstars

Greatly increases the efficiency and performance is the is_visible_in_tree() system. Forward port of #107324

Benchmarks

~6x faster in DEBUG and RELEASE with depth 10 scene tree (repeated for the same node, so in cache, so likely the change would be faster real world) Has to be benchmarked from c++ as gdscript is too slow to benchmark multiple calls to is_visible_in_tree().

Background

The 3D code for is_visible_in_tree() was added 14 years ago in https://github.com/godotengine/godot/commit/2ee4ac183babedd679e901b0158f5268556deceb however I long suspected it was not a good approach, as the runtime check is very expensive - it involves recursing up the chain to look for any invisible nodes. This kind of operation is very bad on modern CPUs, as it has a tendency to cause cache misses (like a linked list is bad).

As with many systems in scene graphs, there is a choice between:

• cheap updating
• cheap getting

In many situations Godot goes for "lazy updating", which is the cheap update, and then the expense is deferred to getting. In most cases the expensive getter is cached. Not so for is_visible_in_tree(). Everytime it is called, every frame, tick, it is expensive.

Solutions

There are two obvious solutions here:

1. Add some machinery to cache the expensive result, and continue to defer the calculation to the getter.
2. The other solution I have added here is to go for the more conventional approach, and actually do the expensive calculation as a one off when adding the node to the tree, or showing or hiding.

I think on balance this second approach makes sense. Adding / removing nodes from the tree is a relatively rare operation, as is showing / hiding, and in most cases the update will be cheap anyway as the _propagate_visible_in_tree() call terminates early when no change is detected.

_is_vi_visible()

This problem has come up before, and I'd already added a partial solution, which was the optimized _is_vi_visible() system. The only snag is that this only works for VisualInstance derived nodes, and not all Spatials, therefore we end up needing rather cumbersome checks for VisualInstance cast_to before using it. It would be much better if we could replace this with a generic system for all Spatials.

This is what this PR does.

Rollout

As this has some potential for the odd bug, and might require rebasing a couple of (my) PRs, I figure rollout could be done in three stages:

1. Adding the new is_visible_in_tree() machinery for 3D (and optional regression testing code) - this PR
2. Remove _is_vi_visible() and change callers to use is_visible_in_tree()
3. Add 2D version

Notes

• The code involved here is actually relatively simple.
• There is no change to behaviour, including the separation of visibility propagation in 2D and 3D.
• I have no idea why no one (including myself) didn't do this earlier, as the current system was probably (as far as I can see) not the best choice (in retrospect). :facepalm:
• This should in general speed up the engine, but particularly physics interpolation which does lots of scene tree traversal.
• DRAFT - As we need to figure out how to fast access the children list in 4.x, as this needs quick access like SceneTreeFTI, this is not a problem in 3.x as get_child() etc is fast there.