Это для флеш игры с изометрической проекцией. Мне нужно знать, как сортировать объекты, чтобы не требовалась проверка z-буфера при рисовании. Это может показаться простым, но есть другое ограничение: сцена может иметь более 10000 объектов, поэтому алгоритм должен быть запущен менее чем за 0 (n ^ 2). Все объекты представляют собой прямоугольные коробки, и в сцене движется 3-4 объекта. Какой лучший способ сделать это?
ОБНОВИТЬ
в каждой плитке есть только объект (я имею в виду объекты не могут складываться друг на друга). и мы получаем доступ как к карте объектов, так и объекты имеют свою позицию.
UPDATE2
увидеть эти цифры:
сначала должен быть нарисован первый синий объект, затем зеленый, а затем красный. в то время как во втором вы должны нарисовать их в обратном порядке. Вы должны нарисовать красный сначала, а затем зеленый и наконец синий объект. Как вы можете видеть, нет никакой разницы в положении синих и красных объектов, они оба имеют разное расстояние от камеры и так далее. но из-за их относительного положения относительно зеленого поля вам нужно изменить порядок их отрисовки между двумя изображениями. вот что делает эту проблему беспорядком.
примечание: поскольку все объекты представляют собой прямоугольную призму, математически доказано, что существует хотя бы один порядок отрисовки для удовлетворения проблемных задач.
источник
Ответы:
Это на самом деле очень просто, если ваши объекты совпадают с вашими изометрическими плитками. Посмотрите на это изображение:
Сначала вы должны нарисовать объект в красной позиции, затем синий, зеленый, желтый, пурпурный и т. Д. Должно быть достаточно очевидно, как это реализовать, если на вашей доске есть объекты вместо объектов. имея положение в качестве атрибута. Если это не ваш случай, вы должны сохранить отдельную структуру данных, обновляя ее всякий раз, когда объект перемещается (что тоже должно быть довольно просто).
Это создает новую проблему: вы можете легко увидеть, как теперь ее сложность составляет O (N), где N - размер вашей платы (
N=W*H). Чтобы преодолеть эту проблему, просто создайте новую линейную структуру данных, где каждый индекс в вашей структуре соответствует определенной глубине, обновляя ее всякий раз, когда объект меняет глубину.Случай, когда объект не соответствует одной плитке, немного сложнее, поэтому я опубликую его, если он вам понадобится, как только вы обновите свой вопрос.
источник
У меня нет специальных знаний по этому вопросу, но вот мысль.
Начните с маркировки каждой ячейки как "не нарисованной". (Или, что эквивалентно, используйте массив для представления местоположения ближайшей «нарисованной» вещи на каждой «ближней линии» ячеек или набора и т. Д.) Затем для каждой ячейки (я бы, вероятно, прошел через них в порядок, описанный kaoD): проверьте, была ли нарисована эта ячейка; если он не был нарисован и содержит объект, проверьте, была ли нарисована каждая ячейка, которая была бы скрыта этим объектом, и, если нет, нарисовать ее рекурсивно; рисовать объект, содержащийся в этой ячейке, если это необходимо; и пометьте эту ячейку и любые ячейки, занятые ее объектом, как «нарисованные».
Я предполагаю, что вы можете быстро сопоставить ячейку с объектом внутри нее, если есть. Я полагаю, что это время O (n), хотя это может привести к созданию большого стека (который вы можете превратить в связанный список, если вы беспокоитесь о нехватке места в стеке).
Если вам действительно нужен список, вы можете добавить его в список вместо рисования. Я подозреваю, что начинать с отсортированного в основном списка не помогает.
источник
Я бы использовал алгоритм живописца с расстоянием такси от самой дальней ячейки до камеры, сначала рисуя те, которые были ближе к камере, а затем двигаясь наружу.
Изменить: это не работает, если вы не можете нарисовать содержимое каждой ячейки в отдельности.
источник
Что заставляет вас верить, что «математически доказано, что существует хотя бы один порядок извлечения для удовлетворения проблемных потребностей»? Вот простой контрпример, в котором нельзя полагаться на объекты z-сортировки:
источник