Сортировка братьев и сестер в иерархии объектов
Я реализовал дерево сцен для использования в 2D-игре. Узлы дерева содержат преобразования и нарисованные объекты.
Вот как выглядит дерево сцены:
Root
|
--------------------------
| |
Layer1 Layer2
| |
----------------- ---------
| | | | |
A B C F G
|
---------
| |
D E
Чтобы нарисовать сцену, дерево сначала перемещается в порядке глубины. Во время прохождения чертежи собираются в очереди рендеринга. Очередь рендеринга затем передается на рендерер для обработки.
Поскольку элементы рисования собраны в порядке первой глубины, это также порядок, в котором они нарисованы средством визуализации. Чтобы изменить порядок рисования, мне нужно переставить узлы дерева. Если, например, я хочу, чтобы узел G отображался перед узлом F, я должен поменять их местами. Я хотел бы изменить это так, чтобы узлы больше не нужно было переставлять. Вместо этого средство визуализации должно иметь возможность сортировать очередь визуализации самостоятельно.
Эта проблема:
Каждая группа узлов (например, [A, B, C] или [F, G] или [D, E]) должна быть отсортирована по отдельности, чтобы иерархия не изменялась. Если узлы дерева отсортированы напрямую, это не проблема. Однако, если дерево сплющено в очередь рендеринга, все усложняется.
Мои вопросы:
Как я могу отсортировать очередь рендеринга, не нарушая иерархию узлов?
Существуют ли альтернативные решения для такого рода проблем?
Дополнительная информация:
Лучший ресурс, который я смог найти, это статья в блоге. Он объясняет, как сортировать очередь рендеринга, используя 64-битный ключ, который собран из нескольких порций информации. Это не решает проблему, которая у меня есть.
Вы можете спросить, почему я не довольствуюсь сортировкой узлов дерева напрямую. Есть две причины: во-первых, я хотел бы разделить проблемы. Перестановка узлов в дереве сцены таким образом, чтобы средство визуализации отображало их в правильном порядке, не способствовало бы достижению этой цели. Во-вторых, было бы невозможно исключить невидимые узлы / элементы рисования из сортировки (тогда как очередь рендеринга содержит только видимые элементы рисования).