xfcRS — оригинальный лаконичный шустрый рендер сглаженных тайлов, «expansion fast cell — Rounded Squares»

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

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

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

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

Не спешите судить, если вам не нравится такое ограничение. Оно работает на то, что от него и требуется — предельно сокращает расходы необходимых графических ресурсов. Хочу заметить, для тайловых движков это норма!

Алгоритм разбивает клетки на четвертинки 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 вообще прекрасно распараллеливается!
При нахождении факторов, мы просто проставляем соответствующие иксы/игрики в результирующий массив (все это хитро, но, если разобраться, очень удобно хранится в битах индекса).
<spoiler title=«Комментарий „почему понадобилось упаковывать значения вообще“»>
— когда «память нынче не так уж и важна» сразу отвечу, что в данном случае сжатие памяти приводит к ускорению. Инструкции, работающие с клетками, обрабатывают и опрашивают по несколько клеток за раз. Так же при рендеринге, для быстрого определения необходимости обрабатывать клетку по четвертям, достаточно сравнить значение индексов на 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 – 8x8 полная (синей текстурой) клетка; 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
т. о. на каждую клетку приходится один шестнадцатиричный разряд (он содержит индекс нужного тайла размытия).

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

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

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

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

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

Автор: impfromliga

Источник