"Try of a new sprite sorter"-Patch
Posted: 31 Jul 2007 14:55
Hello
Inspired by http://bugs.openttd.org/task/119 I wrote a new sprite-sorter.
During my insufficient testing I did not encounter any of the standard sorting-problems. Well I wrote "insufficient", so you may now guess, what I want you to do...
Please test the attached patch with your savegames and search for glitches with bad sorted sprites. If you have found one, compare it to current trunk, and report if it's a new or a old one. I hope a screenshot with the glitch will be enough for now.
About the attachments:
1) For those who do not know the basic dilemma of sprite sorting, I have attached a small exercise for you.
2) The patch introduces a debuging feature: By pressing "Ctrl-B" you can toggle drawing of bounding boxes. Please do not report about residues of the bouding boxes of moving objects.
3) Well the patch file. If someone with a running BuildOTTD is around, I will be happy if you would post a Win32 executable, so more people can search for glitches.
Technical details:
1. Airports are a bit tricky. The bounding boxes of aircrafts on the floor are pretty wrong. But it is not obvious how to correct them. For now I got away with only modifying the bounding-boxes of the jetways.
2. The current code is only a experiment, if it may work. Please do not talk about efficiency, or code niceness.
3. The sprites are sorted in multiple steps:
I) First dependencies between sprites are created (in the source called "after"-list). These are always correct, but they can lead to cyclic dependencies (attachment 1).
II) Cycles are detected and broken at the weakest edge determined by a heuristic based on the barycenter of the bounding boxes.
III) All sprites that currently do not depend on other sprites, get additional dependencies based only of the Z-coordinates of their bounding-boxes. (This aims at glitches with foundations.)
IV) The remaining sprites are sorted by the barycenter-heuristic.
V) Every time a sprite is drawn, dependencies of other sprites to it are removed. If a sprite has no longer any dependencies, proceed with it like in III.
Somewhat unrelated changes in source:
First drawing lines could segfault. Second selection sprites on foundations can be drawn it a much more correct way, which removes the drawing of selections above vehicles etc.
I will post this changes on Flyspray later, when I get time.
Inspired by http://bugs.openttd.org/task/119 I wrote a new sprite-sorter.
During my insufficient testing I did not encounter any of the standard sorting-problems. Well I wrote "insufficient", so you may now guess, what I want you to do...
Please test the attached patch with your savegames and search for glitches with bad sorted sprites. If you have found one, compare it to current trunk, and report if it's a new or a old one. I hope a screenshot with the glitch will be enough for now.
About the attachments:
1) For those who do not know the basic dilemma of sprite sorting, I have attached a small exercise for you.
2) The patch introduces a debuging feature: By pressing "Ctrl-B" you can toggle drawing of bounding boxes. Please do not report about residues of the bouding boxes of moving objects.
3) Well the patch file. If someone with a running BuildOTTD is around, I will be happy if you would post a Win32 executable, so more people can search for glitches.
Technical details:
1. Airports are a bit tricky. The bounding boxes of aircrafts on the floor are pretty wrong. But it is not obvious how to correct them. For now I got away with only modifying the bounding-boxes of the jetways.
2. The current code is only a experiment, if it may work. Please do not talk about efficiency, or code niceness.
3. The sprites are sorted in multiple steps:
I) First dependencies between sprites are created (in the source called "after"-list). These are always correct, but they can lead to cyclic dependencies (attachment 1).
II) Cycles are detected and broken at the weakest edge determined by a heuristic based on the barycenter of the bounding boxes.
III) All sprites that currently do not depend on other sprites, get additional dependencies based only of the Z-coordinates of their bounding-boxes. (This aims at glitches with foundations.)
IV) The remaining sprites are sorted by the barycenter-heuristic.
V) Every time a sprite is drawn, dependencies of other sprites to it are removed. If a sprite has no longer any dependencies, proceed with it like in III.
Somewhat unrelated changes in source:
First drawing lines could segfault. Second selection sprites on foundations can be drawn it a much more correct way, which removes the drawing of selections above vehicles etc.
I will post this changes on Flyspray later, when I get time.