Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Isometric rectangle rendering order

Isometric rectangle rendering order

Поделиться

Страницы: 1 2 Следующая

SuslikМодераторwww8 июня 201712:49#0
Есть тайловая карта. Вид на карту — классическая изометрия. Тайловые объекты представляют из себя прямоугольные блоки произвольных габаритов, ориентированные по координатным осям. Да вот хотя бы возьмём для примера лего:
+ Показать

Гарантируется, что блоки не пересекаются в пространстве. Для каждого блока известно, какие тайлы он занимает в горизонтальной проекции, но по спрайту каждого блока неизвестно, какой именно он высоты(потому что он может состоять в основном из прозрачности). Требуется отрендерить все блоки в корректном порядке без использования z-buffer'а.

Для определённости положим, что ось x направлена право-вверх, а ось y — влево-вверх. Я уже пробовал сортировать объекты по величине (x + y), если брать самую нижнюю или самую верхнюю точки блока(в 2д), но оба способа дают артефакты в случаях с длинными блоками.
Если сортировать по самой нижней точке, то артефакт даёт такой случай:
2 | Isometric rectangle rendering order

Если сортировать по самой верхней, то такой:
1 | Isometric rectangle rendering order

Пара вопросов:
1) всегда ли это возможно при моих ограничениях?
2) если нет, то какими эвристиками можно пользоваться, чтобы минимизировать количество артефактов?

Правка: 8 июня 2017 13:00

iKestПостоялецwww8 июня 201713:18#1
Вот очень хорошая статья по Вашей проблеме - https://habrahabr.ru/post/269653/

Правка: 8 июня 2017 13:29

SuslikМодераторwww8 июня 201713:49#2
в статье куча слов, большинство из них — про трудности жизни сишарп-программиста, которые меня не интересуют совершенно. основная идея алгоритма, который использует автор — для каждой пары объектов завести функцию сравнения, а-ля кто кого перекрывает (A перекрывает B, B перекрывает A или никто не перекрывает никого). далее топологической сортировкой строится строго неубывающая последовательность.

да, такое можно замутить, но придётся писать аккуратную реализацию за линейную сложность, что на самом деле вовсе не тривиально, потому что самая эффективная реализация, если верить вики — это через обход в глубину за O(m), где m — количество рёбер. в данном случае вершины — это тайлы, которых уже w * h, а рёбра — это потенциальные предикаты загораживания, то есть в первом приближении (w * h) ^ 2. радует, что теоретически это возможно, но практически придётся искать нормальный алгоритм топологической сортировки именно для тайловой карты.

Правка: 8 июня 2017 13:55

MAMOHT-92Постоялецwww8 июня 201714:07#3
Suslik
> да, такое можно замутить, но придётся писать аккуратную реализацию за линейную
> сложность
что у автора не получилось сделать, использовать умные хранилища данных тоже, вроде сетку какую-то заюзал он. Основная идея оптимизации всего этого добра в том, что бы обновлялись только те объекты, которые двигались.
VestaПостоялецwww8 июня 201714:29#4
Как-то так?
auto less = [](const Block& b1, const Block& b2)
{
  if(b1.minX <= b2.minX && b1.minY <= b2.minY)
  {
    return true;
  }
  if(b1.maxX <= b2.minX || b1.maxY <= b2.minY)
  {
    return true;
  }
  return false;
};

Upd:
На самом деле, видимо, достаточно

return (b1.maxX <= b2.minX || b1.maxY <= b2.minY);

Правка: 8 июня 2017 14:31

iKestПостоялецwww8 июня 201714:40#5
Suslik
Вы статьи читать не умеете. Там приведены ссылки на ресурсы с уже реализованными топографическими алгоритмами. Ну если только Вы не фанат велосипедов...
SuslikМодераторwww8 июня 201716:10#6
MAMOHT-92
> Основная идея оптимизации всего этого добра в том, что бы обновлялись только те
> объекты, которые двигались.
у меня вообще движущихся объектов нет, но сетка может быть достаточно большой (тысячи тайлов по каждому направлению), а времени на поиск нужного порядка — миллисекунды.

iKest
> Ну если только Вы не фанат велосипедов...
тащить какую-то там либу ради полэкрана кода? я быстрее сам напишу. вообще у нас в GGG практически весь код состоит из велосипедов. никаких сторонних зависимостей, меня это очень радует.

Правка: 8 июня 2017 16:11

susagePПостоялецwww8 июня 201716:32#7
Suslik
> Suslik

1) Высота объекта не влияет на порядок отрисовки. По этому высоту не рассматриваем, Будем считать плоскими.
2) Объект можно рисовать только в том случаи если объекты прилегающие к его 2 видимым граням нарисованы.


Простой алгоритм заливки справится.
Для простоты 1 клетка это 1 тайл.
1) Все пустоты заполняются единичными клетками  пустышками.
2) Все объекты состоят как минимум из 1 клетки.
3) Все тайловое поле представляется как 2D массив клеток.
4) В каждой клетки есть информация об объекте(ссылка).

На первом шаге все объекты связываются с клетками. И вычисляется количество видимых ребер клеток в объекте X.
На втором(если нужно) проходим по всему массиву и пустые клетки заполняем объектами пустышками с X=2.
На третьем учитываем размеры караты. На  краях карты граней клеток ничего не перекрывает поэтому пробегаем по этим клеткам заходим в ихнии объекты и уменьшаем X на 1. Если X==0 то мы уже отрисовали все клетки прилегающие к его граням и объект можно рисовать, объект помещаем в очередь на отрисову.
На четвертом бегаем по циклу.  Берем объект из очереди на отрисову. Для каждой его не видимой клеточной грани. Берем соседскую клетку и у ее объекта уменьшаем X на 1 с проверкой на 0(как на 3 шаге).

***************************************************
Если сетка статик и нету вращения(проекции) меняющее видимые грани. То можно 1 раз рассчитать для всей карты, пронумеровать. и потом брать любую выборку и сортировать ее.

iKestПостоялецwww8 июня 201716:43#8
Suslik
Вы не только статьи, но и посты читать не умеете.... Я ни слова не говорил о либах. Только об алгоритмах, причем неоднократно обкатанных в "боевых" условиях. Впрочем, если хочется "велосипедить" самому, то нубуя тогда было спрашивать?
SuslikМодераторwww8 июня 201717:26#9
короче я написал топологическую сортировку.

что имеем на входе(без сортировки):
Изображение

что имеем на выходе(после сортировки):
Изображение

сделал таки за линейное время, исходя из предположения, что высота каждого спрайта ограничена некоторой константой(то есть он может загораживать другие тайлы только в на конечном расстоянии). всем спасибо за идеи — сам бы я до идеи топологической сортировки не додумался, можем расходиться.

susageP
твой алгоритм не учитывает высокие объекты, которые могут перекрывать далеко стоящие за ними низкие объекты

Правка: 8 июня 2017 17:32

MrShoorУчастникwww8 июня 201717:51#10
Suslik
У себя делал так. Рисовал кубики, на которые проецировал кусочки спрайтов. А единичные кубики сортировать - нефиг делать. В моем случае я их сразу генерил в вершинных и геометрических шейдерах в нужном порядке.
susagePПостоялецwww8 июня 201718:27#11
Suslik
> твой алгоритм не учитывает высокие объекты, которые могут перекрывать далеко
> стоящие за ними низкие объекты
Найди на своей картине объект высота которого изменит порядок отрисовки.
Мой алгоритм не визуально упорядочивает, а на 2D карте и ему пофиг на высоту можно сказать клетки бесконечной высоты..


Посмотри на свою картинку и увидишь.
susageP
> Объект можно рисовать только в том случаи если объекты прилегающие к его 2
> видимым граням нарисованы.
( пустоты заполнены пустышками(объектами) )
И высота не влияет на это условие.

meekoboldПостоялецwww9 июня 20179:02#12
MrShoor
+1
Простой и изящный подход, который основан на аппаратной фиче, которая есть сегодня на любой рисовалке, которому пофиг на выпуклость объектов и который элементарно дописывается до 3х-мёрной сетки
Статья забавная: "я не хочу связываться с текстурными координатами, поэтому давайте сортировать слои каждый кадр!"
MATovУчастникwww22 июня 201712:00#13
Suslik
У автора той статьи собственно тоже топологическая сортировка, просто со всякими оптимизациями на движущиеся объекты, дабы квадрата по сложности небыло.
В последних оптимизациях вообще сделал QuadTree в скринспейсе для того, что бы быстрее искать с чем точно пересекаешься (вот эта интересная оптимизация). И это всё всё равно поверх топологической ессно.
1 frag / 2 deathsУчастникwww22 июня 201714:16#14
Разбить блоки на блоки единичного размера, для которых сортировка тривиальна?

Страницы: 1 2 Следующая

/ Форум / Программирование игр / 2D графика и изометрия

2001—2017 © GameDev.ru — Разработка игр