Tekx — что под капотом?

Компьютерная генерация

Некоторых людей заинтересовал принцип работы моего процедурного генератора графики, результаты которого были показаны мной в начале этого года, вместе со ссылкой на сам Tekx 0.8.

Что ж, пришлось мне вооружиться ILSpy'ем, декомпилировать (нет, это всего лишь C#, поэтому всё делается автоматически) исполняемый файл, и написать пост о том, как же оно всё работает, и каким это таким образом безликие цифры обретают всякоразные необычные формы.

В этом посте будет много математики и немного алгоритмов.

Вкладки Lining, Trailing и PostFX я затрагивать не буду. Первые две не доделаны и рисуют неинтересно, а последнее это уже пост-эффекты, и упопянуть оттуда стоит разве что технику wrapping'а — заворота текстуры так, чтобы она стала бесшовной, с дублированием её взаимно противоположных частей через край.

Вещи типа Angular drive и Retrace to points работали когда-то ранее, но были сломаны в процессе улучшения, и как они работали, я уже сам не помню. Так что они вернутся, может быть, в реинкарнации Tekx'а, которую я уже запланировал под названием «XitteX».

Тем более я не буду затрагивать разные режимы отображения и пакетной генерации текстур в левом окне — это всё тривиально и просто интерфейс, не имеет отношения к самой генерации.

Итак:

        private object[] Op(object[] i)
        {
            return i;
        }

… Ээээ, что за хрень? Так… А здесь я тестировал синусы и косинусы, с непонятным результатом, всё это тоже надо пропустить. Так, тут какие-то функции подготовки аргументов генерации для… делегатов… или чего… Хм, оказывается я впилил в этот проект ещё и осцилляторы из моего другого проекта по генерации звука, который называется Oscilla. И ещё lookup tables для функции корня квадратного и функции «вычесть-и-возвести-в-квадрат», ну окей. Хм, параллельные вычисления в разных потоках… А… Где вообще начинается код генерации?..

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

Благо, начинается всё понятно как — с шума Ворли:

  1. Определяем размер текстуры, то есть ширину и высоту;
  2. Создаём одномерный массив двухмерных точек. Раскидываем случайным образом в этой области N точек (Amount). R-Limit в Tekx ограничивает расстояние раскидываемых точек от центра текстуры;
  3. Если включён Pre-wrapping, то раскиданные точки дублируются в разные стороны. То есть копии исходных точек, раскиданных между нулевыми координатами (левый верхний угол текстуры) и требуемым размером текстуры, переносятся влево-вправо-вверх-вниз (а также по диагоналям, если Pre-wrapping 8), и добавляются к массиву точек. Вот так втупую, да:

            int num8 = array.Length;
            if (prewrap_mode == PreWrapMode.Side8)
            {
                Array.Resize<Point>(ref array, array.Length * 9);
                for (int l = 0; l < num8; l++)
                {
                    array[num8 + l] = new Point(array[l].X — size.Width, array[l].Y);
                    array[2 * num8 + l] = new Point(array[l].X, array[l].Y — size.Height);
                    array[3 * num8 + l] = new Point(array[l].X — size.Width, array[l].Y — size.Height);
                    array[4 * num8 + l] = new Point(array[l].X + size.Width, array[l].Y);
                    array[5 * num8 + l] = new Point(array[l].X, array[l].Y + size.Height);
                    array[6 * num8 + l] = new Point(array[l].X + size.Width, array[l].Y + size.Height);
                    array[7 * num8 + l] = new Point(array[l].X + size.Width, array[l].Y — size.Height);
                    array[8 * num8 + l] = new Point(array[l].X — size.Width, array[l].Y + size.Height);
                }
            }
  4. Создаём двухмерный массив вещественных значений. Длина и ширина массива — такая же, как и генерируемой текстуры. В цикле для каждого элемента такового массива проходимся по массиву точек, которые мы раскидали выше, вычисляя расстояние от текущих координат до каждой точки из них. Если нам требуется наименьшее расстояние из вычисленных, берём его, иначе берём второе наименьшее, или наибольшее, или какое ещё. В Tekx это регулируется в рамке Order. Получаем в итоге двухмерный массив расстояний до ближайшей/2-й ближайшей/… точки из массива точек.
  5. Полученный массив нормализуется. Так как в моём алгоритме вычисляется расстояние, а оно не может быть отрицательным, то формула там попроще — нет min и newMin. Так как глубина в моём алгоритме ограничена 8 битами на 1 канал цвета на пиксел, то массив нормализуется к интервалу [0, 255].
  6. Нормализованный массив раскрашивается в цвета между первым и вторым выбранным. Там есть ещё алгоритм для наркоманской спектральной раскраски через цветовую модель HSV, но это вряд ли требует особо объяснения.

В общем-то это и всё. Нюансы:

  • Расстояние может быть не только «обычным». Оно может быть Манхэттеновским, или расстоянием Чебышёва, или вовсе с кастомной степенью. 1 — Манхэттен, 2 — обычное. С отрицательными и дробными получается иногда интересно.
  • Области в которых две точки находятся примерно на одном расстоянии от вычисляемой точки, можно отнести к фасетным, и придать им другой цвет. На ширину этой пограничной области влияет настройка Facet.
  • Noise отвечает за примешивание рандомных величин. Наверное, самый очевидный параметр.
  • Flat cells превращает текстуру в диаграмму Вороного для исходного массива точек. Просто в массив расстояний записывается не расстояние, а индекс ближайшей/N-й ближайшей точки.
  • Настройка Sined модулирует функцию расстояния синусоидой с делителем, указанным тут же в поле Divisor.
  • Настройка Striped находит остаток от деления вычисленного расстояния на заданное число Leap.
  • Power это степень в которую возводится всё это дело после всего.
  • Op устанавливает оператор между двумя блоками вычисления расстояний. Можно выбрать одно из них, а можно сумму, разницу, произведение, частное, синус одного с амплитудой другого, логарифмическая функция и экспонента (как это точно работает — надо тщательно смотреть исходники).
  • Ранее сгенерированные текстуры можно смешивать с новыми сгенерированными. За это отвечает блок Apply to previous.

Похожие статьи

12 комментариев
StaticZ

Очень интересная тема, но к сожалению очень скомканно описана. Много ссылок на шум Ворли, но по ним лишь пара слов о том, что мол да такое существует, в чем состоит алгоритм-то? Вообще это больше походит не на описание что под капотом, а на справку по интерфейсу программы с краткими техническими пояснениями, тем не менее постарался вникнуть...

 

Так как глубина в моём алгоритме ограничена 8 битами на 1 канал цвета на пиксел, то массив нормализуется к интервалу [0, 255].

Не очень понятно, в этом ведь случае получиться монохромное изображение, если данная операция проделывалась для каждой компоненты цвета RGB или HSV то былобы понятно, а если она служит лишь как растояние между двумя задаваемыми цветами, то зачем тогда имеено этот интервал?  с тем же успехом можно было взять и 1024 и 7779. Кстати не возникало идеи проделать данную операцию для каждой компоненты цвета отдельно? насколько  я понимаю результат мог бы выйти интересным, особенно с HSV.

 

Op устанавливает оператор между двумя блоками вычисления расстояний. Можно выбрать одно из них, а можно сумму, разницу, произведение, частное, синус одного с амплитудой другого, логарифмическая функция и экспонента

Два   блока? Откуда второе расстояние взялось? Допустим посчитали два расстояния, простейшая арифметика понятна (складываем, вычитаем, делим одно на другое), но как считается тогда к примеру синус?

 

Ранее сгенерированные текстуры можно смешивать с новыми сгенерированными. За это отвечает блок Apply to previous.

Каким образом идет перемешивание? наложением двух изображений или это както влияет на генерацию? Если да то как?

 

PS Почему не считать обычно декартовское расстояние? Вроде не сложно, и поидее должны быть плавнее переходы или же при этом алгоритм распадается?

 

PPS Для генератора наверное былобы полезна возможность задавать вручную сид, для генерации точек.

 

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

Xitilon

в чем состоит алгоритм-то?

Ну вот официальная статья самого Ворли. Моя трактовка его алгоритма реализуется так, как написано в пункте 2 в посте: «В цикле для каждого элемента такового массива проходимся по массиву точек, которые мы раскидали выше, вычисляя расстояние от текущих координат до каждой точки из них.».

Не очень понятно, в этом ведь случае получиться монохромное изображение

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

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

К сожалению, не понял, что тут имеется в виду, можно более подробно или пример использования?

Два   блока? Откуда второе расстояние взялось?

Второе расстояние, как и первое, берётся из настроек, галочек этих всех. Синус считается как синус одного расстояния умноженный на второе. Я ведь это писал там: «синус одного с амплитудой другого».

PS Почему не считать обычно декартовское расстояние? Вроде не сложно, и поидее должны быть плавнее переходы или же при этом алгоритм распадается?

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

PPS Для генератора наверное былобы полезна возможность задавать вручную сид, для генерации точек.

Будет в новой версии.

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

Опять же планирую что-то подобное. А вот зачем расстояние Хэмминга тут? Или как его приспособить?

StaticZ

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

Но тогда следовало бы его нормализовывать не в интервале [0..255], а в интервале [color1...color2]

 

К сожалению, не понял, что тут имеется в виду, можно более подробно или пример использования?

Все просто — проделать сей алгоритм не 1 раз а 3 раза, отдельно для составляющих RGB или HSV и потом собрать все воедино. Что получиться не знаю, но мне кажеться результат бы мог выйти интересным.

 

Опять же планирую что-то подобное. А вот зачем расстояние Хэмминга тут? Или как его приспособить?

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

Xitilon

Но тогда следовало бы его нормализовывать не в интервале [0..255], а в интервале [color1...color2]

Но ведь цвет — трёхмерная величина? Это тогда нужен массив структур, ну по крайней мере логически это так, и это тогда конвертация, а не нормализация. Честно говоря не помню зачем там именно так, и сейчас это смотрится странно. Но я всё равно решил переписать всё с нуля, оглядываясь на прошлый опыт, копаться в старом коде уже не вариант.

Все просто — проделать сей алгоритм не 1 раз а 3 раза, отдельно для составляющих RGB или HSV и потом собрать все воедино. Что получиться не знаю, но мне кажеться результат бы мог выйти интересным.

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

хэмминг как вариант оценки  монотонности

Вот я всё опять же понял, а куда потом эту оценку хэмминга применить — не понял. Можно как-то на пальцах? Типа, вот в некоем мутном изображении такая монотонность, а в чётком другая, и оценка тогда там 1 а там 100 и что из этого следует. Никогда не считал ничего по Хэммингу.

StaticZ

Но ведь цвет — трёхмерная величина? Это тогда нужен массив структур, ну по крайней мере логически это так, и это тогда конвертация, а не нормализация. Честно говоря не помню зачем там именно так, и сейчас это смотрится странно

Может это я чего-то не понимаю, но смысл в интервале от 0 до 255 всеравно не понимаю. По большому счету мы должны получить интервал от 0 до 1 и далее Rmin += val * (Rmax — Rmin); и аналогично для каждой компоненты цвета. Если нормализуем от 0 до 255, то тогда будет Rmin += val * (Rmax — Rmin) / 255; Т.е. с тем же успехом можно было взять любой другой интервал.

 

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

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

 

Вот я всё опять же понял, а куда потом эту оценку хэмминга применить — не понял. Можно как-то на пальцах? Типа, вот в некоем мутном изображении такая монотонность, а в чётком другая, и оценка тогда там 1 а там 100 и что из этого следует. Никогда не считал ничего по Хэммингу.

Там ничего сложного — посути бьем грейскейл с ресайзом изображения или его части до 8х8, ну а затем считаем его:

private static readonly byte[] _BitCountTable = new byte[] {
                0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
                1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
                1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
                2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
                1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
                2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
                2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
                3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
        };

        internal ulong GetAvrHash008()
        {
            var minimg = GrayscaleResize(8, 8);

            uint avgcolor = 0;
            for (var c = 0; c < 64; ++c)
                avgcolor += minimg[c];
            avgcolor /= 64;

            ulong hashsum = 0;
            for (var c = 0; c < 64; ++c) 
                if (minimg[c] > avgcolor)
                    hashsum |= ((ulong)0x01 << c);

            return hashsum;
        }

        ushort IImageSurface.GetHammingDistanceForAvrHash008(IImageSurface surface)
        {
            if (surface == null) {
                return 0xFFFF;
            }

            ushort result;
            ulong avrhash = 0;
            if (surface is BitmapSurface)
                avrhash = (surface as BitmapSurface).GetAvrHash008();
            else
                throw new NotImplementedException();

            avrhash ^= GetAvrHash008();

            result  = _BitCountTable[avrhash & 0xFF];
            result += _BitCountTable[(avrhash >>  8) & 0xFF];
            result += _BitCountTable[(avrhash >> 16) & 0xFF];
            result += _BitCountTable[(avrhash >> 24) & 0xFF];
            result += _BitCountTable[(avrhash >> 32) & 0xFF];
            result += _BitCountTable[(avrhash >> 40) & 0xFF];
            result += _BitCountTable[(avrhash >> 48) & 0xFF];
            result += _BitCountTable[(avrhash >> 56) & 0xFF];
            return result;
        }

 

 

 В принципе аналогично можно считать и для больших хешей, к примеру для 128 байтного хеша надо лишь заменить ресайз на 32х32 ну и лишние итерации добавляем для таблицы. Само расстояние хэмминга служит обычно не для определения четкости изображения а для простого и быстрого поиска похожих изображений, где само расстояние характеризует степень разлиия. Для этого они и конвертируются в черно белый цвет, чтобы избавиться от влияния тональности. В данном случае речь идет скорее об получение отличий частей изображения друг с другом. 

 

 

 

Xitilon
Rmin += val * (Rmax — Rmin);

Ну, во-первых такой формулы там у меня нет, у меня Rmin всегда 0 а Rmax всегда 255. Во-вторых, val всегда от 0.0 до 1.0, соответственно второй множитель от 0 до 255 и итог от 0.0 до 255.0 приведенный к целому типу.

по факту сейчас генерируется монохромная картинка или картинка в некой тональности, а так получиться причудливое переплетение цветов

Да что вы говорите? Вы пробовали саму программу в режиме HSV? Вот эти картинки, которые я показывал в первом посте, вовсе не в одной тональности, и уж тем более не монохромные (и не искусственно раскрашенные после генерации):

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

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

buntarsky
Мне кажется, что вы друг друга не слышите. )
Так как глубина в моём алгоритме ограничена 8 битами на 1 канал цвета на пиксел, то массив нормализуется к интервалу [0, 255].

Не очень понятно, в этом ведь случае получиться монохромное изображение, если данная операция проделывалась для каждой компоненты цвета RGB или HSV то былобы понятно, а если она служит лишь как растояние между двумя задаваемыми цветами, то зачем тогда имеено этот интервал?...

Именно, что операция «проделывается для каждой компоненты цвета». В этом истинный смысл слова «нормализация».

Xitilon

http://www.gamedev.ru/code/terms/Normalization

Нормализация (normalization) — приведение к единичному размеру.

Не обязательно цвета. Можно и звука.

buntarsky
Ну да. Я про конкретно этот пример.
Xitilon
Я ничего не понял.
buntarsky
Вообще это было адресовано StaticZ. По-хорошему, надо было под первое его сообщение это запостить, откуда я и взял цитаты. Но по непостижимому стечению обстоятельств запостил в «конец» вашей дискуссии, где вы так и не пришли к консенсусу и еще больше все запутали.
Xitilon
Теперь понял. Но это не совсем правильное уточнение было. У меня нормализация делается для массива скалярных величин, не цветов. Это потом оно раскрашивается либо по RGB, либо по HSV. О чём и шла речь. Короче, надо мне писать более понятные посты, да.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.