xfcRS — оригинальный лаконичный шустрый рендер сглаженных тайлов, «expansion fast cell — Rounded Squares»
xfcRS — многофункциональный быстрый алгоритм, для тайлового рендера с гладкими переходами / для построения изоповерхности / для выделения края в растре / для постпроцессинга как пиксельный шейдер — для пиксельарт масштабирования 8×8 (для быстрой растеризации шрифтов, иной материал для upscale’инга без доработок не рекомендуется). Расшифровка акронима — «eXpansion Fast Cell — Rounded Squares»
В данной статье мы будем рассматривать его преимущественно в контексте рендера сглаженных тайлов:
Забегая вперед, скажу сразу: это не улучшенный Marshing Squares,
В то время как изоповерхность в Marshing Squares стремится максимально апроксимировать положение линии и визуально меньше менять объемы исходных клеток, данный алгоритм стремится поднять минимальную кривизну линий, откуда в названии Rounded Squares.
При равном с Marshing Squares количестве проверок, он требует меньший объем входного тайлсета (а следовательно меньше работы художникам), хотя в худшем случае может работать до 4х раз медленнее из-за вывода четвертинками (на практике зависит от сложности топологии клеток и от реализации функции рисования тайлов, может почти не быть разницы).
Топологически алгоритм использует те же линии, повернутые друг от друга на 45 градусов, но начинает их откладывать не от 0 как Marsing Squares, а от 22.5 градуса (и это делает их симметричными друг другу при отражениях, как горизонтальных, так и диагональных, что позволяет получить все 16 четвертинок переходов всего из 2х, опять же меньше работы художнику, если у вас top-down или просто не ориентированные спрайты.) В случае, если вам не требуются даже плавные переходы (диффузия текстур), а достаточно лишь скругления клеток, работа художника может быть уменьшена до задачи «нарисовать одну четвертинку тайла — кусок параболы» (который автокомпиляция пересоберет автоматически).
В представленном примере кружок тайлов переходной текстуры выворачивается наизнанку лишь их перестановкой благодаря полной симетрии на 8 сторон.
Используется очень простая схема сглаживания тайлов. Это достигается за счет переходной текстуры, которая вставляется между любыми двумя другими, тайлы переходов в которую должны быть нарисованы для всех остальных текстур.
Не спешите судить, если вам не нравится такое ограничение. Оно работает на то, что от него и требуется — предельно сокращает расходы необходимых графических ресурсов. Хочу заметить, для тайловых движков это норма!
— желая поддержки прямых переходов «всех во все», вы закладываете квадратичную зависимость, и ваш тайлсет будет расти как таблица умножения (каждое следующее дополнение потребует все больше работы по совмещению взаимосвязей). Если даже с человеческими ресурсами вы задачу решили, то, как минимум, на программном уровне это в любом случае загрузит занимаемую память (размер тайлсета) и размер передачи данных (если браузерка), или загрузит быстродействие (если динамически считать диффузию);
— другим способом внести разнообразие будет адаптация данного алгоритма на случай множества общих текстур. В общем случае каждый тип поверхности может состоять с любым другим типом в группе (через общую текстуру) только один раз (т. е. пара типов должна однозначно определять общую текстуру). Частный случай — цикл текстур. А переходит в общую АБ, в которую также переходит Б, которая переходит в общую БС, в которую также переходит С… и т. д. (при необходимости последняя зацикливается на первую);
— Так же хорошим вариантом может быть внесение разнообразия в общую для всех переходную текстуру только при переходе на новые уровни. Так она кешируется при загрузке один раз. (На мой взгляд, это наиболее эффективное направление применения настоящего алгоритма для создания простых 2д игр).
Алгоритм разбивает клетки на четвертинки 2×2, каждую из них заполняет более маленьким ориентированным тайлом из заготовленного набора. Но это в итоге. На самом деле xfcRS является алгоритмом постпроцессинга. И вьювер является внешним дополнением. Сам xfcRS лишь сворачивает карту клеток в таблицу индексов, которую можно использовать очень разнообразно. Что же это за таблица, как она строится и как потом используется?
Здесь в статье будет приведен пример простого пост-рендера. Под «пост» рендером я подразумеваю то, что он является некоторым очередным проходом во вьюве и не выводит сам всю карту с нуля, а рисует только дополнительные саб-тайлы там, где они нужны.
Не будем торопиться, начну объяснение в порядке, в котором это было придумано:
1.Текстура перехода
Первое, о чем стоит подумать — как выбрать постановку задачи о сглаживании тайлов так, чтобы она реализовывалась проще, но без существенных качественных различий.
Ясно, что «сглаживая» регулярные клетки визуально, одни будут наползать на другие. Но не все «наползания» равнозначно минималистичны по трудозатратам рендера.
Можно заметить, что скруглить клетку можно двумя путями — наползанием на нее общей текстуры, или наоборот — вытягиванием клетки за свои изначальные границы. Два варианта мало что визуально нам дают. Выбираем один — только сужение клеток при встрече с чужими или с нулевой текстурой. Также это означает, что мы исключаем взаимодействие с диагональными клетками, что так же полезно для дальнейшей оптимизации.
Контур переходов в этом случае лучше всего взять близким к идеальному кругу (хотя это не ограничение, но чем ближе к нему, тем более гладким будет казаться скругление). Идеальный круг точно описан вокруг клетки — проходит через ее углы (это уже ограничение для гладких переходов). Также важна симметрия, она должна быть би-радиальной. Это позволяет сглаживать изгибы на тонких участках. Если ваша текстура перехода не однородна — рисуйте тор (см. рис на оригинальной текстуре, можете брать ее за шаблон. Это заявление можно считать за creative commons лицензию).
На рисунке:
Черной сеткой показаны исходные клетки. Краевая область, где сглаживание невозможно рассчитать из-за отсутствия соседей — затенена. Т.е. ширина и высота результирующей сетки уменьшается на клетку. Оставшаяся белая сетка позиционируется с отступом в пол-клетки — в нее будут записаны результирующие индексы саб-клеток.
В левом верхнем углу показаны условные поименования клеток для одного шага проверки, а также направления сравнений (знаками равенства) и образующееся влияние на конкретные саб-клетки (показаны плюсами).
В левом нижнем углу добавлена оригинальная текстура переходов, из которой собраны все изгибы на представленном рисунке.
Если вам захочется поэкспериментировать с кривой, посмотрите на рисунок слева «топология зон диффузии текстур». Белая линия показывает логическую изолинию. Черные линии по обе стороны от нее — допустимые диапазоны смещения (при этом точки перехода соединений тайлов попарно левый — правый, верхний — нижний, должны быть равноудалены от центра). Например, можно нарисовать эллипс, и получить эффект изометрии (наклон вида камеры).
2.Две Проверки — Четыре клетки
Наивный подход заключался бы в обходе всех саб-клеток с проверкой их 2х соседей. Но любая проверка равенства 2х клеток на самом деле влияет всегда на 4 саб-клетки, а 2 уже на 8 соответственно! Так давайте получим это восьмикратное ускорение (от метода в лоб) и обработаем их оптом. см. рис. Вот ядро алгоритма (на JS):
function XFCR(map, w, h){ // "eXpansion Fast Cell - Rounded Squares"
for(var xfc = [], n = 0, C = map[n - 1], D; n < w * h; xfc[n++ - w - 1] ^= 0xfc30, C = D){
if(C ^ (D = map[n]))
xfc[n - w - 1] |= 0x8800,
xfc[n - 1] |= 0x0088;
if(D ^ map[n — w])
xfc[n - w] |= 0x202,
xfc[n - w - 1] |= 0x2020;
}
return xfc;
}
Так мы будем обходить искомые клетки вместо каждой саб-клетки, просто в результирующий массив будем складывать изменения по месту. Так же заметим, что комбинация наличия/отсутствия соседей может восприниматься как 2 независимых фактора (наличие соседа сверху сдвигает текстуру по х, соседа слева — по у). А раз факторы независимы, незачем упираться в синхронность, можно обрабатывать их ассинхронно. Кстати говоря, xfcRS вообще прекрасно распараллеливается!
При нахождении факторов, мы просто проставляем соответствующие иксы/игрики в результирующий массив (все это хитро, но, если разобраться, очень удобно хранится в битах индекса).
— когда «память нынче не так уж и важна» сразу отвечу, что в данном случае сжатие памяти приводит к ускорению. Инструкции, работающие с клетками, обрабатывают и опрашивают по несколько клеток за раз. Так же при рендеринге, для быстрого определения необходимости обрабатывать клетку по четвертям, достаточно сравнить значение индексов на 0xfc30 — эта константа говорит о том, что окружение данной клетки однородно и ее можно вывести оптом, без разбивки (без упаковки пришлось бы проверять отдельно все 4 сабклетки);
— на самом деле взятый бинарный формат результата содержит двукратный избыток информации (зато каждый HEX разряд хранит готовый индекс смещения для тайла. При этом все равно получается хранить координаты сдвигов 4х клеток в 2х байтах). Если вам вдруг понадобится запускать его на очень больших объемах, можно хранить всего по 2 бита для сабклетки. Придется вынести «волшебную» константу 0xfc30 в логику рендера и учитывать позиционирование саб-клетки, но все 4 будут занимать всего байт. А если пойти на чрезвычайные ухищрения, можно сохранять только значения условий и тратить на каждую саб-клетку ровно половину бита =) хотя при этом суть алгоритма xfcRS будет уже размотана до нуля, потому как его суть быстро сравнить соседей, отдав удобную карту индекса. (Кстати говоря, на Си, например, можно было бы паковать массив байт (для каждой сабклетки) аппаратно разрешая его в Int32. Что будет сильнее проигрывать по памяти, но выигрывать по скорости и удобству).
— ! ВАЖНО! По этим же причинам зона, для которой xfcRS отдает результирующий массив, СДВИНУТА на половину клетки (на одну саб-клетку). И то, что невозможно рассчитать краевые клетки — не главное. Главное, что сдвинув (и соответственно перегруппировав) индексы, мы получаем блоки, удобные для проверки и быстрого определения полностью залитых 2×2 саб-клеток. — пример: если на входящей карте наличествует блок 2×2 из искомых клеток, в результате он будет сглажен по контуру на половину клетки, а в середине (сдвинутой на пол клетки) будет одна целая клетка, вот ее-то и хочется легко определять из индекса. Определение пустых клеток не требуется, т. к. (по определению проходного алгоритма) они должны быть уже нарисованы стандартным тайловым алгоритмом. Код рендера из примера их просто пропускает. Пример пост рендера:
function draw(map, w, h){// View: //(multipass - empty cell background pattern needed)
var sub = XFCR(map, w, h); // Compute sub-tiles by XFCR algorithm
for (var n = 0, y = 4, j = h; --j; y += 8, n++){
for (var x = 4, S, i = w; --i; x += 8, n++){
if((S = sub[n]) ^ 0xfc30){ //go sub-tiles 4x4 x4:
if(map[n]) ctx.drawImage(fuse, S << 2 & 12, S & 12, 4, 4, x, y, 4, 4);
if(map[n+1]) ctx.drawImage(fuse, S >> 2 & 12, S >> 4 & 12, 4, 4, x + 4, y, 4, 4);
if(map[n+w]) ctx.drawImage(fuse, S >> 6 & 12, S >> 8 & 12, 4, 4, x, y + 4, 4, 4);
if(map[n+w+1]) ctx.drawImage(fuse, S >> 10 & 12, S >> 12 & 12, 4, 4, x + 4, y + 4, 4, 4);
}else if(map[n]) ctx.drawImage(full, x, y); //full sub-tile block 4x4
};
};
}
Применительно к JS достаточно установить на фон паттерн пустой клетки, а вывод на канву сдвинуть на саб-клетку. Дополнительно рекомендую предрассчитать адаптивное css масштабирование. Я это делаю для канвы 320×192 растягивая ее через CSS на 100% в данном примере:
var ctx = cnv.getContext('2d');
ctx.drawImage(habr, 0, 0); //draw text
var w = cnv.width >> 3, h = cnv.height >> 3, z = cnv.width / window.innerWidth, //calc dynamic scale - ratio
map = ctx.getImageData(0, 0, w, h).data.filter( (x, i) => !(i & 3) ).map(x => x >> 7); //convert pixel data to map
cnv.style.width = '100%'; cnv.style.backgroundSize = (8/z)+'px '+(8/z)+'px'; //dynamic scale - background pattern
Не буду приводить здесь HTML, скажу, что fuse — это IMG 16×16 с диффузным тайлсетом; full — 8×8 полная (синей текстурой) клетка; habr — пиксельарт надпись, которая попиксельно преобразуется в карту map; body margin сброшен в 0, background канвы — пустая (бежевая) клетка с замощением.
3.Комментарии о реализации
Полный исходный код см. github.com/impfromliga/xfcRS
При реализации важно учитывать, что возвращаемая дата идет для сабклеток (которые сгруппированы 2×2 между имеющимися), т. к. рассчитать значение краевых нет возможности (недостаточно соседей) — размер возвращаемого поля будет меньше на клетку (на полклетки с каждого края).
Как вы его обрабатываете, xfcRS не касается. Край можно вывести без сабклеток самостоятельно, но если карта предполагает прокрутку, на краю экрана визуально местность будет «дрожать» (при появлении влияющих соседей). В этом случае рекомендуется обрезать вывод на полклетки от исходных данных или заранее давать xfcRS на клетку больше входных данных.
Группа сабклеток 2×2 упаковывается в одно значение в порядке big-endian, т. е. Значения клеток
A B
C D
— находятся в битах числа начиная от младших к старшим. И значение индекса = ((D * 16 + C)*16 + B)*16 + A
т. о. на каждую клетку приходится один шестнадцатиричный разряд (он содержит индекс нужного тайла размытия).
— xfcRS можно доработать для обработки локальной области (в этом случае опять же вы должны себе представлять, как соотносятся обрезанные и сглаженные саб-клетки с искомыми).
Это позволит высокоэффективно перерисовывать локальные изменения карты.
В рамках статьи я этого не делал, т. к. боролся за простоту. К тому же алгоритм так легок, что вполне шустро работает, перерисовывая весь экран.
— Расширение алгоритма до фрактального без модификаций не приносит роста результата. Расширение возможно, если обрабатывать диагональную клетку при условии совпадения одновременно 2х равенств соседей (устанавливать ее на ¾ размытой). Хоть текстуры и не рассчитаны на такую схему, пусть они работают по старой (просто приближая значения при проверке клеток), но необходимо расширить хранимые значения пустых/непустых клеток до некоторых диапазонов. Последний проход всегда может использовать оригинальный алгоритм, т. к. на последнем проходе в любом случае необходимо привести дробные коэффициенты к целой форме, понимаемой рендером.
— Будучи используемый как масштабирующий пиксельный фильтр, алгоритм увеличивает оригинальную карту пикселей *8×8, исходный размер тайлсета делающий ЭТО всего 16×24 px (текстуры ориентированы! Без ориентации / диффузии и того меньше)
— Алгоритм может использоваться для выявления краев растровых объектов (дописав функцию сравнения пикселей для диапазона)
— (применительно к JS) вычисленный край поможет группировать операции рисования множества паттернов на канву.
5.Комбинации:
— При реализации скроллинга xfcRS легко кладется на 2д буфер, разобранный мной в предыдущей статье.
— В дополнение, как вы уже видели из картинки к посту — замечательно рисует оригинальные шрифты (которые можно стилизовать растрово).
6.Для истории
Рожденный (не без труда, но оттого лишь приятнее) алгоритм так мне понравился, что я решил его громко наречь.
Стал искать аббревиатуру, хотелось что-то похожее на алгоритмы то ли FXAA -антиалиасинг, то ли xBR или EPX — масштабирование пиксельарт графики (кстати, после недавнего осмотра последнего, было выяснено, что он имеет с моим некое вполне ощутимое сходство).
Так пришел к двум вариантам «eXpansion Fast Cell Rounder» или просто «Rounded Squares», в итоге стал больше склоняться к последнему.
Но знаете, что еще меня поразило? В итоге в коде, уже после названия, я пришел к константе 0xfc30.
(уверен, меня поймет и поддержит всякий как и я IT-нерд, пусть единое название, без дефисов хорошо для всяких SEO, но в данном случае двух не миновать !)
Еще одним подарком судьбы стала более ранняя находка интересной закономерности на переходной текстуре:
— На ней отображен красивый шарик текстуры (прям как в 3д редакторах материалы)
— Дело в том, что попиксельно этот шарик можно вывернуть наизнанку, используя лишь перестановку 4×4 тайлов. Т.е. не важно, какая текстура основа, их можно перевернуть.
На самом деле, xfcRS получился таким стройным не сразу — в старых тестах, например, я не углядел замечательное расположение тайлсета, в котором просто визуально проверяется гладкость сложения.
Кстати говоря, есть еще одна эстетическая задача на компоновку, хотя не задача, скорее вопрос, который не дает мне покоя. Ввиду такой необычно замечательной возможности выворачивать круг наизнанку, есть ли какой- то более лаконичный способ хранения текстур… есть идеи?
Ну и на сладкое простейший код для динамического редактирования (с поддержкой мобильного хрома):
onload = window.ontouchstart = onmousedown = function(e){ //Controll:
e = e || window.event;
e.preventDefault ? e.preventDefault() : e.returnValue = false;
var E = e.touches ? e.touches[0] : e,
n = E.pageX * z / 8 + w * (E.pageY * z / 8 | 0) | 0;
map[n] = !map[n];
ctx.clearRect(0, 0, cnv.width, cnv.height);
draw(map, w, h);
}
Скриншоты! Полученные с помощью пропускания белого шума или ручным редактированием в процессе разработки: 
и лайв-демо codepen.io/impfromliga/pen/qNOazj
Вот и все. Хотел писать статьи чаще, но во-первых совесть не позволяет выкладывать что то не проработанное до конца, а во-вторых времени на внятное описание оказывается уходит больше, чем на саму реализацию, но не всегда оно есть в достатке…
Комментарии, критика, предложения, заранее благодарю за любой конструктив!
И кстати, время склонно находиться тем быстрее чем больше людей пинает тебя в ж проявляет интерес к твоим находкам.
Если вы дочитали до сюда, Огромное спасибо за внимание!
И до встречи.
