xfcRS — многофункциональный быстрый алгоритм, для тайлового рендера с гладкими переходами / для построения изоповерхности / для выделения края в растре / для постпроцессинга как пиксельный шейдер — для пиксельарт масштабирования 8х8 (для быстрой растеризации шрифтов, иной материал для upscale'инга без доработок не рекомендуется). Расшифровка акронима — «eXpansion Fast Cell — Rounded Squares»

В данной статье мы будем рассматривать его преимущественно в контексте рендера сглаженных тайлов:

Если у вас возникнут вопросы по терминам обезательно загляните сюда

Забегая вперед, скажу сразу: это не улучшенный Marshing Squares,

Используется очень простая схема сглаживания тайлов. Это достигается за счет “Диффузного круга”, части которого накладываются в места стыков не одинаковых клеток, или на стык любой клетки с пустой. “Диффузный круг» должен быть нарисован для всех типов клеток и отражать в текстуре их плавный переход в пустую клетку.

То есть все текстуры переходят одна в другую через текстуру пустой клетки. Это максимально ускоряет работу художнику!

Алгоритм разбивает клетки на четвертинки 2х2, каждую из них заполняет более маленьким ориентированным тайлом из заготовленного набора. Но это в итоге. На самом деле xfcRS является алгоритмом постпроцессинга. И вьювер является внешним дополнением. Сам xfcRS лишь сворачивает карту клеток в таблицу индексов, которую можно использовать очень разнообразно. Что же это за таблица, как она строится и как потом используется?

Здесь в статье будет приведен пример простого пост-рендера. Под «пост» рендером я подразумеваю то, что он является некоторым очередным проходом во вьюве и не выводит сам всю карту с нуля, а рисует только дополнительные саб-тайлы там, где они нужны.

Не будем торопиться, начну объяснение в порядке, в котором это было придумано:

1.Текстура перехода
Смотрим на «Топологию», видим 16 кусочков тайлов, из которых может составляться клетка в зависимости от соседей.
Простейшая ситуация: все соседи равны (клетка составляется из краевых кусочков) можно запомнить по аналогии, — что кусочки как бы прилипают к соседям
(Пусть это начальное состояние, от которого мы меняемся).
Если какой-то сосед не равен, он отталкивает от себя кусочек на две позиции.

Когда все соседи проверены и все кусочки тайла соответственно оттолкнуты, можно выводить клетку этими четырьмя кусочками.
(Для эффективности можно проверить на оптовые условия, например, если клетка полностью целая или полностью пустая).

Первое, о чем стоит подумать — как выбрать постановку задачи о сглаживании тайлов так, чтобы она реализовывалась проще, но без существенных качественных различий.
Ясно, что «сглаживая» регулярные клетки визуально, одни будут наползать на другие. Но не все «наползания» равнозначно минималистичны по трудозатратам рендера.
Можно заметить, что скруглить клетку можно двумя путями — наползанием на нее общей текстуры, или наоборот — вытягиванием клетки за свои изначальные границы. Два варианта мало что визуально нам дают. Выбираем один — только сужение клеток при встрече с чужими или с нулевой текстурой. Также это означает, что мы исключаем взаимодействие с диагональными клетками, что так же полезно для дальнейшей оптимизации.

Контур переходов в этом случае лучше всего взять близким к идеальному кругу (хотя это не ограничение, но чем ближе к нему, тем более гладким будет казаться скругление). Идеальный круг точно описан вокруг клетки — проходит через ее углы (это уже ограничение для гладких переходов). Также важна симметрия, она должна быть би-радиальной. Это позволяет сглаживать изгибы на тонких участках. Если ваша текстура перехода не однородна — рисуйте тор (см. рис на оригинальной текстуре, можете брать ее за шаблон. Это заявление можно считать за creative commons лицензию).


На рисунке:
Черной сеткой показаны исходные клетки. Краевая область, где сглаживание невозможно рассчитать из-за отсутствия соседей — затенена. Т.е. ширина и высота результирующей сетки уменьшается на клетку. Оставшаяся белая сетка позиционируется с отступом в пол-клетки — в нее будут записаны результирующие индексы саб-клеток.

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

Если вам захочется поэкспериментировать с кривой, посмотрите на рисунок слева «топология зон диффузии текстур». Белая линия показывает логическую изолинию. Черные линии по обе стороны от нее — допустимые диапазоны смещения (при этом точки перехода соединений тайлов попарно левый — правый, верхний — нижний, должны быть равноудалены от центра). Например, можно нарисовать эллипс, и получить эффект изометрии (наклон вида камеры).

2.Две Проверки — Четыре клетки
Наивный подход заключался бы в обходе всех саб-клеток с проверкой на равенство с текущей клеткой её 2х соседей. При этом результат проверки это сдвиг координат вибираемого кусочка текстуры к центру (смотрите рис.). Изначально все четвертинки принимаются как угловые кусочки текстуры и образуют при соединении синий кружок (со всех сторон соседи синие). НЕравенство с соседом по вертикали сдвигает выбираемый кусок текстуры к центру по вертикали (на две позиции, так он выбирается следом за противоположным по вертикали углом) По горизонтали используется аналогичная проверка и сдвиг. Случай когда после проверок ничего не сдвинулось (остался целый синий круг) желательно обрабатывать как исключение и выводить целую клетку разом а не по четвертям.
Здесь наивный метод заканчивается.
(далее в коде начальная позиция тайлов и будет иметь константу 0xfc30. А сдвиги по горизонталям/вертикалям будут работать с соответствующими HEX разрядами нужных ячеек массива)
Важно заметить, что любая проверка равенства 2х клеток на самом деле влияет всегда на 4 саб-клетки, а 2 уже на 8 соответственно! Так давайте получим это восьмикратное ускорение (от метода в лоб) и обработаем их оптом. см. Рис.



Так мы будем обходить искомые клетки вместо каждой саб-клетки, просто в результирующий массив будем складывать изменения по месту. Так же заметим, что комбинация наличия/отсутствия соседей может восприниматься как 2 независимых фактора (наличие соседа сверху сдвигает текстуру по х, соседа слева — по у). А раз факторы независимы, незачем упираться в синхронность, можно обрабатывать их ассинхронно. Кстати говоря, xfcRS вообще прекрасно распараллеливается!
При нахождении факторов, мы просто проставляем соответствующие иксы/игрики в результирующий массив (все это хитро, но, если разобраться, очень удобно хранится в битах индекса).

— ! ВАЖНО! По этим же причинам зона, для которой xfcRS отдает результирующий массив, СДВИНУТА на половину клетки (на одну саб-клетку). И то, что невозможно рассчитать краевые клетки — не главное. Главное, что сдвинув (и соответственно перегруппировав) индексы, мы получаем блоки, удобные для проверки и быстрого определения полностью залитых 2х2 саб-клеток. — пример: если на входящей карте наличествует блок 2х2 из искомых клеток, в результате он будет сглажен по контуру на половину клетки, а в середине (сдвинутой на пол клетки) будет одна целая клетка, вот ее-то и хочется легко определять из индекса. Определение пустых клеток не требуется, т. к. (по определению проходного алгоритма) они должны быть уже нарисованы стандартным тайловым алгоритмом. Код рендера из примера их просто пропускает.

3.Комментарии о реализации
Полный исходный код см. github.com/impfromliga/xfcRS
При реализации важно учитывать, что возвращаемая дата идет для сабклеток (которые сгруппированы 2х2 между имеющимися), т. к. рассчитать значение краевых нет возможности (недостаточно соседей) — размер возвращаемого поля будет меньше на клетку (на полклетки с каждого края).
Как вы его обрабатываете, xfcRS не касается. Край можно вывести без сабклеток самостоятельно, но если карта предполагает прокрутку, на краю экрана визуально местность будет «дрожать» (при появлении влияющих соседей). В этом случае рекомендуется обрезать вывод на полклетки от исходных данных или заранее давать xfcRS на клетку больше входных данных.

Группа сабклеток 2х2 упаковывается в одно значение в порядке big-endian, т. е. Значения клеток
A B
C D
— находятся в битах числа начиная от младших к старшим. И значение индекса = ((D * 16 + C)*16 + B)*16 + A
т. о. на каждую клетку приходится один шестнадцатиричный разряд (он содержит индекс нужного тайла размытия).



5.Комбинации:
— При реализации скроллинга xfcRS легко кладется на 2д буфер, разобранный мной в предыдущей статье. => habrahabr.ru/post/280830
— В дополнение, как вы уже видели из картинки к посту — замечательно рисует оригинальные шрифты (которые можно стилизовать растрово).

6.Для истории
Рожденный (не без труда, но оттого лишь приятнее) алгоритм так мне понравился, что я решил его громко наречь.
Стал искать аббревиатуру, хотелось что-то похожее на алгоритмы то ли FXAA -антиалиасинг, то ли xBR или EPX — масштабирование пиксельарт графики (кстати, после недавнего осмотра последнего, было выяснено, что он имеет с моим некое вполне ощутимое сходство).
Так пришел к двум вариантам «eXpansion Fast Cell Rounder» или просто «Rounded Squares», в итоге стал больше склоняться к последнему.
Но знаете, что еще меня поразило? В итоге в коде, уже после названия, я пришел к константе 0xfc30.
(уверен, меня поймет и поддержит всякий как и я IT-нерд, пусть единое название, без дефисов хорошо для всяких SEO, но в данном случае двух не миновать !)

Еще одним подарком судьбы стала более ранняя находка интересной закономерности на переходной текстуре:
— На ней отображен красивый шарик текстуры (прям как в 3д редакторах материалы)
— Дело в том, что попиксельно этот шарик можно вывернуть наизнанку, используя лишь перестановку 4х4 тайлов. Т.е. не важно, какая текстура основа, их можно перевернуть.

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

Кстати говоря, есть еще одна эстетическая задача на компоновку, хотя не задача, скорее вопрос, который не дает мне покоя. Ввиду такой необычно замечательной возможности выворачивать круг наизнанку, есть ли какой- то более лаконичный способ хранения текстур… есть идеи?

Ну и на сладкое:
Скриншоты:







и лайв-демо codepen.io/impfromliga/pen/qNOazj

Вот и все. Хотел писать статьи чаще, но во-первых совесть не позволяет выкладывать что то не проработанное до конца, а во-вторых времени на внятное описание оказывается уходит больше, чем на саму реализацию, но не всегда оно есть в достатке…

Комментарии, критика, предложения, заранее благодарю за любой конструктив!

И кстати, время склонно находиться тем быстрее чем больше людей пинает тебя в ж проявляет интерес к твоим находкам.

Если вы дочитали до сюда, Огромное спасибо за внимание!
И до встречи.