image

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

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

Если у вас возникнут вопросы по терминам обезательно загляните сюда
Тезаурус:
— Рендеринг — процесс построения кадра на экране. Рендер, соответственно алгоритм который это делает.
— Растр — массив точек экрана или графического файла текстуры. Растеризация — процесс построения этого массива точек, из неких входных данных.
— Upscale — Так именуют процесс и осуществляющие его алгоритмы, предназначенные масшатбировать графику конкретно в сторону увеличения размеров. Основной фокус в них уделяется борьбе с появлением негативных эффектов искажения картинки, такие как излишняя зернистость, размытие, и др.
— Пиксельарт — растровая графика, либо в силу своего давнего года выпуска, либо специально имитирующая ретро компьютеры, не борющаяся за большое разрешение растра.
— Постпроцессинг — В общем случае, алгоритм который работает после некоторого другого предваряющего его работу алгоритма (тот может в таком случае называться препроцессинг).
— Шейдр — В общем случае алгоритм постпроцессинга реализованный для аппаратного исполнения на видеокарте.

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

— Marshing Squares – алгоритм генерации изолиний на двумерном скалярном поле. см. ru.wikipedia.org/wiki/Marching_squares
— Изолиния — Условная линия служащая для приближенного отражения положения точной.
— Апроксимация — Приближенное значение чего либо точного.


Забегая вперед, скажу сразу: это не улучшенный Marshing Squares,
хотя технология...
разбивки на 16 вариантов тайлов похожа, но это лишь внешнее сходство, алгоритм разработан с нуля. Если всмотреться глубже, используются 16 четвертинок, и только для переходов. Для цельно залитых или полностью пустых тайлов используется отдельный полноразмерный тайл.

В то время как изоповерхность в Marshing Squares стремится максимально апроксимировать положение линии и визуально меньше менять объемы исходных клеток, данный алгоритм стремится поднять минимальную кривизну линий, откуда в названии Rounded Squares.
При равном с Marshing Squares количестве проверок, он требует меньший объем входного тайлсета (а следовательно меньше работы художникам), хотя в худшем случае может работать до 4х раз медленнее из-за вывода четвертинками (на практике зависит от сложности топологии клеток и от реализации функции рисования тайлов, может почти не быть разницы).

Топологически алгоритм использует те же линии, повернутые друг от друга на 45 градусов, но начинает их откладывать не от 0 как Marsing Squares, а от 22.5 градуса (и это делает их симметричными друг другу при отражениях, как горизонтальных, так и диагональных, что позволяет получить все 16 четвертинок переходов всего из 2х, опять же меньше работы художнику, если у вас top-down или просто не ориентированные спрайты.) В случае, если вам не требуются даже плавные переходы (диффузия текстур), а достаточно лишь скругления клеток, работа художника может быть уменьшена до задачи «нарисовать одну четвертинку тайла — кусок параболы» (который автокомпиляция пересоберет автоматически).
В представленном примере кружок тайлов переходной текстуры выворачивается наизнанку лишь их перестановкой благодаря полной симетрии на 8 сторон.


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

То есть все текстуры переходят одна в другую через текстуру пустой клетки. Это максимально ускоряет работу художнику!
Хочу заметить, для тайловых движков это норма!
Не спешите судить, если вам не нравится такое ограничение на одинаковую для всех общую текстуру. Дело в том, что желая поддержки прямых переходов «всех во все», вы закладываете квадратичную зависимость, и ваш тайлсет будет расти как таблица умножения (каждое следующее дополнение потребует все больше работы по совмещению взаимосвязей — «каждый тайл во все остальные»). Если даже с человеческими ресурсами вы задачу решили, то, как минимум, на программном уровне это в любом случае загрузит занимаемую память (размер тайлсета) и размер передачи данных (если браузерка), или загрузит быстродействие (если динамически считать диффузию);
— другим способом внести разнообразие будет адаптация данного алгоритма на случай множества общих текстур. В общем случае каждый тип поверхности может состоять с любым другим типом в группе (через общую текстуру) только один раз (т. е. пара типов должна однозначно определять общую текстуру). Частный случай — цикл текстур. А переходит в общую АБ, в которую также переходит Б, которая переходит в общую БС, в которую также переходит С… и т. д. (при необходимости последняя зацикливается на первую);
— Так же хорошим вариантом может быть внесение разнообразия в общую для всех переходную текстуру только при переходе на новые уровни. Так она кешируется при загрузке один раз. (На мой взгляд, это наиболее эффективное направление применения настоящего алгоритма для создания простых 2д игр).


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

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

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

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

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

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

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


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

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

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

2.Две Проверки — Четыре клетки
Наивный подход заключался бы в обходе всех саб-клеток с проверкой на равенство с текущей клеткой её 2х соседей. При этом результат проверки это сдвиг координат вибираемого кусочка текстуры к центру (смотрите рис.). Изначально все четвертинки принимаются как угловые кусочки текстуры и образуют при соединении синий кружок (со всех сторон соседи синие). НЕравенство с соседом по вертикали сдвигает выбираемый кусок текстуры к центру по вертикали (на две позиции, так он выбирается следом за противоположным по вертикали углом) По горизонтали используется аналогичная проверка и сдвиг. Случай когда после проверок ничего не сдвинулось (остался целый синий круг) желательно обрабатывать как исключение и выводить целую клетку разом а не по четвертям.
Здесь наивный метод заканчивается.
(далее в коде начальная позиция тайлов и будет иметь константу 0xfc30. А сдвиги по горизонталям/вертикалям будут работать с соответствующими HEX разрядами нужных ячеек массива)
Важно заметить, что любая проверка равенства 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 – 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
т. о. на каждую клетку приходится один шестнадцатиричный разряд (он содержит индекс нужного тайла размытия).

4.Расширения / Дополнения
— Т.к. в общем случае xfcRS не говорит ничего о рендеринге, а лишь отдает индексированную таблицу границ, есть возможность внести дополнительные данные в эту таблицу — это может быть полезно для прокладки «тропинок» внутри больших однородных областей. Эти тропинки, получаемые из внешнего источника данных, не будут перекрыты при изменении окружающих клеток. Интересно также, что будучи «проложенными» изначально по пустому пространству, тропинки будут не видны. И чтобы их найти, необходимо будет специально их посыпать мукой (пеплом, выбрать по вкусу геймдизайнера).
— xfcRS можно доработать для обработки локальной области (в этом случае опять же вы должны себе представлять, как соотносятся обрезанные и сглаженные саб-клетки с искомыми).
Это позволит высокоэффективно перерисовывать локальные изменения карты.
В рамках статьи я этого не делал, т. к. боролся за простоту. К тому же алгоритм так легок, что вполне шустро работает, перерисовывая весь экран.
— Расширение алгоритма до фрактального без модификаций не приносит роста результата. Расширение возможно, если обрабатывать диагональную клетку при условии совпадения одновременно 2х равенств соседей (устанавливать ее на ? размытой). Хоть текстуры и не рассчитаны на такую схему, пусть они работают по старой (просто приближая значения при проверке клеток), но необходимо расширить хранимые значения пустых/непустых клеток до некоторых диапазонов. Последний проход всегда может использовать оригинальный алгоритм, т. к. на последнем проходе в любом случае необходимо привести дробные коэффициенты к целой форме, понимаемой рендером.

— Будучи используемый как масштабирующий пиксельный фильтр, алгоритм увеличивает оригинальную карту пикселей *8х8, исходный размер тайлсета делающий ЭТО всего 16х24px (текстуры ориентированы! Без ориентации / диффузии и того меньше)

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


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

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

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

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

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

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

Комментарии (9)


  1. OldFisher
    07.06.2016 09:41
    +8

    Содержание статьи, видимо, интересно и может быть даже довольно практически полезно для меня лично. Но, к сожалению, статья вовсе не рассчитана на то, чтобы я её понял. Она будет понятна только очень узкому кругу читателей, которые уже запанибрата с marching cubes (мне, например, понадобится провести некоторое время в википедии и других источниках, чтобы вспомнить, что этот алгоритм вообще делает) и другими тонкостями темы. Чтобы статья читалась лучше, она должна быть лучше структурирована. Нужно введение, в котором объясняется, что и как вообще делает предложенный алгоритм, начиная с основной идеи, изложенной в том числе с помощью предельно понятных схематичных иллюстраций. Не стоит исходить из предположения, что читатель в деталях знаком с тем же алгоритмом marching cubes: следует вкратце изложить, для чего он нужен, на каком принципе основан и привести ссылку на более подробное описание для интересующихся. Далеко не каждый заинтересовавшийся будет использовать именно JavaScript, многие с этим языком попросту незнакомы, поэтому желательно изложить суть и особенности реализации алгоритма так, чтобы свести к минимуму иллюстративную роль фрагментов кода.


    1. impfromliga
      07.06.2016 14:34

      Статья рассчитана чтобы ее поняло большинство, а не конкретно вы. (Здесь не частные уроки, а общий материал, с котором как и везде при самообучении придется разбираться) Стоит это того или нет должно быть ясно из краткого вступления, перечисляющего возможности алгоритма, скриншотов результата и живой демки.

      https://ru.wikipedia.org/wiki/Marching_squares — как написано в статье, к делу не относиться! Он упомянут, что бы его НЕ читать!

      Фрагменты кода в статьях я привожу на JS т.к. этот язык очень популярен и многие знают именно его (не на всех же языках код приводить). Весь код в статью был добавлен последним делом, именно в целях дополнительной понятности (и отмены необходимости скакать на гитхаб в другой вкладке).
      В то же время вся суть алгоритма, на сколько мне видится, последовательно объясняется (спойлеры читают те, кто хотят углубить понимание).

      Пожалуйста, лучше структурируйте ваш комментарий. Иначе, не указывая конкретно, что вам не понятно, я не смогу вам помочь.

      Каких иллюстраций кроме имеющихся основных, по вашему мнению не хватает?
      Что кроме имеющегося перечисления возможностей нужно внести во введение? Уже сейчас, в статье сразу после перечисления возможных применений, (без спойлеров) идет объяснение, «что и как вообще делает предложенный алгоритм», и между прочем именно с основной идеи и начиная:
      — Используется очень простая схема сглаживания тайлов. Это достигается за счет переходной текстуры, которая вставляется между любыми двумя другими, тайлы переходов в которую должны быть нарисованы для всех остальных текстур.
      — Алгоритм разбивает клетки на четвертинки 2х2, каждую из них заполняет более маленьким ориентированным тайлом из заготовленного набора.

      Очень просто написать «я не понял, — материал слаб». Но в критике желательна конкретика.
      Иначе я лишь внесу правки которые вызовут больше вопросов у других…
      Кстати говоря, я ожидаю что совместно здесь, многие прояснят ситуацию и помогут действительно улучшить материал.


      1. myxo
        07.06.2016 19:32
        +1

        Ну хорошо, вот вам немного конструктивной критики.

        Для начала, если вы действительно пишете для большинства, нужно пояснять термины. Что такое тайл я худо-бедно вспомнил, а вот что такое сглаживание тайлов — непонятно. Так же непонятно что такое сабтайлы, переходные тайлы, сабклетки, логическая изолиния и т.п. Ну то есть к середине статьи (а не там, где эти термины даны) у меня появились догадки, но что если они не совпадают с тем, что вы имели в виду?

        «Ясно, что «сглаживая» регулярные клетки визуально, одни будут наползать на другие.» — совсем не ясно что имеется в виду.

        Есть много предложений, которые вообще написаны не по-русски.
        «Это достигается за счет переходной текстуры, которая вставляется между любыми двумя другими, тайлы переходов в которую должны быть нарисованы для всех остальных текстур.» — я перечитал раз 5, но так и не понял что имеется в виду (ещё больше дезориентировало следующее предложение, в котором утверждается, что это какое-то ограничение).

        Иллюстрации. Например в начале была бы уместна иллюстрация, показывающая зачем это вообще все нужно (ну то есть что этот алгоритм вообще делает).

        И да, лично я ваш код так и не смог в голове распарсить.

        ps. Ох, не люблю писать критику, все как-то в резких выражениях всегда получается =)

        upd. И ещё, зря вы картинку обновили, и так на ней было слишком много чего и непонятно куда там нужно смотреть, а вы добавили ещё больше информации. Не нужно все валить в одну кучу.


        1. impfromliga
          07.06.2016 20:11

          ps. Ох, не люблю писать критику, все как-то в резких выражениях всегда получается =)

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


        1. impfromliga
          07.06.2016 23:41

          Добавил тезаурус под спойлер вначале статьи.
          Предложение не по-русски вообще заменил на «Используется очень простая схема сглаживания тайлов. Это достигается за счет “Диффузного круга”, части которого накладываются в места стыков разных клеток, или на стык полной клетки прилегающей к пустой.» (изображение круга лежит рядом) Это по идее, должно сразу прояснить что:
          "«Ясно, что «сглаживая» регулярные клетки визуально, одни будут наползать на другие.»"

          Больше иллюстраций! Отдельных по месту, в том числе и в начале.

          Код вообще убрал под спойлеры, т.к. он дополнительный. Поняв часть со складыванием тайлов можно написать свою реализацию, но данный конкретный алгоритм рассматривает еще и оптовую обработку, а этого без битовой магии не получить. Описывать битовые операции это тема отдельной статьи.

          Могу дать комментарий тут, — все константы работают по принципу один HEX разряд на саб-клетку. Соответственно выбираются индексы нужных клеток (с учетом того что результирующая сетка сдвинута) + верные позиции HEX разрядов содержащих данные о конкретных саб-клетках. При чтении все проще, т.к. алгоритм совершает все эти перестановки подготавливая данные к удобной работе опираясь на результирующую сетку (Об этом написано в одном из спойлеров)

          цифры 2 или 8 в константах это смещения разных координат выбираемого саб-тайла от углов диффузного круга в центр
          для х позиции, которая изначально может быть 0 или 3 это ^2 = 2 или 1,
          для y, которая изначально 0 или 12 это ^8 = 8 или 4

          И еще раз спасибо вам за конструктив, вы мне очень помогли!


    1. impfromliga
      07.06.2016 14:53

      Попробуйте вдумчиво поиграть с лайв демо: http://codepen.io/impfromliga/debug/qNOazj
      Это может дать интуитивное понимание того что я не учел, и того на что я не могу ответить из вашего вопроса.


      1. impfromliga
        07.06.2016 15:01

        Пожалуй стоит расписать подробнее наивный алгоритм, это может прояснить понимание.


  1. impfromliga
    07.06.2016 15:51

    Каюсь, было что дополнить сразу не учел, в текст внесено дополнение (цитирую):

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


  1. impfromliga
    07.06.2016 19:03

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

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