Revert: Sprite sorting optimisation sorted incorrectly. #6970
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This reverts commit 25ab9c1.
frosch123
referenced
this pull request
Nov 15, 2018
When zooming out with a high res display, there can be about 150k sprites to be sorted before displaying. With the O(n^2) complexity of the sprite sorter, this can take several seconds. This patch works around this by sorting the sprites by the xmin coordinate first using QSort, which later allows an early bailout out of the inner loop. This is enough to cut down the full unzoom time on a 4k display to a fraction of second.
nielsmh
approved these changes
Nov 17, 2018
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This reverts commit 25ab9c1.
The optimisation consists of pre-sorting the bounding boxes in X direction.
During the actual sorting it then short-circuits loops with the assumption
However, the pre-sorting only applies as long as no sprites are moved.
"psd" is a vector iterator, thus the
also affects elements including and after "psd".
This seems to be the core of this patch, so I do not see any other option, but revert.