Onion skinning breaks at Viewports number > 16 (INTROSORT_THRESHOLD)

[butkeim]

Godot version

3.4.stable

System information

Windows 10

Issue description

Onion skinning will break as soon as there are more than 16 viewports in the engine.

This occur on the following engine call stack:

• Onion skinning, file _"animation_player_editorplugin.cpp", makes calls to VS::draw()
• In VS::draw, file _"visual_serverraster.cpp", line 107: VSViewport::draw_viewports()
• In VSViewport::draw_viewports, file _"visual_serverviewport.cpp", line 285: active_viewports.sort_custom<ViewportSort>()

This issue's root comes from the fact that .sort_custom uses introsort alg. (file _"sortarray.h") whom have a different behavior when vector's size goes over introsort's threshold (INTROSORT_THRESHOLD = 16).

The following screenshot represent two block, each one is a draw call, with number of viewports at the top and active_viewports's content. As you can see, a mirroring sorting happens when you're above introsort's threshold (actually at 16), and sorting criteria are met.

This issue can easily be fixed by changing the sorting algorithm. Now before I go on fixing this issue, I need to now how I should "properly" fixe this (modifying such code without approval is generally a bad idea/waste of time). Looking forward for Godot's gods to show me the way.

@RandomShaper

Steps to reproduce

This issue can easily be reproduce:

• Create a 2D/3D scene
• Add a visual Node (Sprite/MeshInstance)
• Add an AnimationPlayer
• Create a new Animation so that your visual Node move in space
• Activate onion skinning
• Add/Duplicate a Viewport in the scene (7 Viewports should be the number)
• See onion skinning break

Minimal reproduction project

No response

[butkeim]

I'm upping this issue, as I said I'm totally up to fixe this by myself (as it's absolutely trivial to correct), I just need someone who knows enough about godot to tell me: - ok go ahead implement anything local to this issue (or) - you should use this other sorting algorithm already present in godot's env.

I'm actually working on a viewports heavy plugin (3D Drawing tool), that NEEDS onion skinning. (I can fixe this issue on a fork for myself, but in the end I want everyone to be able to use my tool).

[Calinou]

• ok go ahead implement anything local to this issue (or) - you should use this other sorting algorithm already present in godot's env.

If it's easier and/or cleaner to go with a "local" solution, feel free to use that :slightly_smiling_face:

See Prefer local solutions in the best practices for engine contributors.

[RandomShaper]

I've been checking this issue. Sorting with introsort is unstable and that seems to be the cause of the issue.

It that is the case, I was considering a non-local solution: modifying SortArray to add a bool StableRequired = false (introsort wouldn't be used if true) template argument to it and adding a stable version of Vector::sort_custom() that uses it.

That said, given that this is so far the only case of such requirement, I can agree that a local solution may be a better bit. On the other hand, a custom, stable sorting algorithm at visual_server_viewport.cpp doesn't sound great either.

Another possibility would be to add to VisualServerViewport::Viewport a member that tracks somehow the tree order (similarly to what happens in its CanvasData member, where tree order is known by the sublayer member). That would allow ViewportSort to inform its result based on that.

DISCLAIMER: I haven't had much time to investigate this. Please take all this with a grain of salt.