Войти
ПрограммированиеФорумОбщее

Качественная целочисленная шумовая функция

Страницы: 1 2 3 Следующая »
#0
22:49, 1 июля 2016

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

Более фрмально: ищется функция [cht]\mathrm{uint32} \mapsto \mathrm{uint32}[/cht], для которой последовательность [cht]f(0),\, f(1), f(2), f(3), f(4), \dots[/cht] выглядит как белый шум.

Основные цели: генерация текстур и звука, ну и всякая мелочёвка.
Требования: сносные статистические характеристики, отсутствие затайленности, скорость, компактность, лёгкость обобщения на n-мерную ([cht]\mathrm{uint32}^n \mapsto \mathrm{uint32}[/cht]).

Кандидаты:
1. Переделать функцию из libnoise:

double IntegerNoise (int n)
{
  n = (n >> 13) ^ n;
  int nn = (n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff;
  return 1.0 - ((double)nn / 1073741824.0);
}
Даже отвлекаясь от int вместо uint32_t и знакового целочисленного переполнения, ведущего к undefined bevavior, всё равно не очень вдохновляюще. Вроде смутно вспоминается, что видел к ней какие-то претензии.

2. n-й член последовательности какого-либо генератора случайных чисел (LCG, PCG). O(log(n)) не радует, хочется константного времени.

3. Применить однократно шаг, например, LCG ко входу (return A*x+B;). Отстой, как легко видеть.

4. Применить несколькократный шаг, например, LCG ко входу. Тоже отстой.

5. Взять какой-нибудь CRC-подобный хеш. Вроде тоже не особо здраво.

6. PrecomputedArray[x%size]. Его надо ещё отдельно предпросчитывать; и тайлится.

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

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

Текущий лидер:

uint32_t noise_uint32(uint32_t n)
{
    uint64_t state=n;
    state=state*state;
    state=state*6364136223846793005ULL+1442695040888963407ULL;
    uint32_t xorshifted=uint32_t(((state>>18u)^state)>>27u);
    uint32_t rot=uint32_t(state>>59u);
    return (xorshifted>>rot)|(xorshifted<<((-rot)&31));
}

#1
23:53, 1 июля 2016

см. Кнут Искусство программирования том 2.

#2
0:57, 2 июля 2016

xorshift? Реализуется очень просто, существуют множество вореций реализации.
https://en.wikipedia.org/wiki/Xorshift
Это псевдослучайный генератор с состоянием в виде одного целого числа. Содержимое его скачет по всему диапазону, не 1, 2, 3....

Если надо рандом где на входе идут последовательные числа 1...N, погляди на всякие алгоритмы хеширования, начиная с MD5 и вперёд к звёздам. Вообще определение хэш-функции - это такая функция, в которой при минимальном изменении входных данных получается максимальный эффект на все биты результата. Ну то есть нечто шумоподобное.

#3
1:44, 2 июля 2016

http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine
https://ru.wikipedia.org/wiki/Вихрь_Мерсенна

Не благодари.

#4
3:33, 2 июля 2016

FordPerfect
> 5. Взять какой-нибудь CRC-подобный хеш. Вроде тоже не особо здраво.
Я пробовал, получилась фигня.

Попробуй к индексу применить одну итерацию PCG, у него функция перемешивания вывода неплохая.

#5
12:12, 2 июля 2016

Zab
А подробнее можно пальцем ткнуть?
При беглом осмотре - там сплошняком stateful rng.
Что с ними делать? Очевидных идей 2: n-й член последовательности (мой п. 2) - не радует O(log(n)) времени работы (~20 умножений на одно несчастное значение?!); и применение трансформации (мои пп. 3,4) к аргументу функции - не радует отстойным качеством для большинства rng.

kvakvs
См. комментарии выше о stateful rng. Сама по себе трансформация xorshift - не вдохновляет.
Комментарий о "какой-нибудь хеш-функции" весьма расплывчат. Интересно, какую именно. CRC похоже что отстой же (вон }:+()___ [Smile], вроде, пробовал), а MD5 - довольно тяжеловесная. А так - да, хеш.

ArchiDevil
К Mersenne Twister несколько дополнительных претензий, кроме озвученных выше.

}:+()___ [Smile]
>Попробуй к индексу применить одну итерацию PCG, у него функция перемешивания вывода неплохая.
Сама по себе итерация PCG - это чистый LCG, перемешивание используется только для вывода.
Ты подразумеваешь что-то вроде

uint32_t IntNoisePCG(uint32_t n)
{
    uint64_t state=n;
    state=state*6364136223846793005ULL+1442695040888963407ULL;
    uint32_t xorshifted=uint32_t(((state>>18u)^state)>>27u);
    uint32_t rot=uint32_t(state>>59u);
    return (xorshifted>>rot)|(xorshifted<<((-rot)&31));
}
?
Можно взглянуть.
#6
12:51, 2 июля 2016

Сделал тут такой незатейливый тест:

+ Показать

Тест заполняет текстуру 128x128 значениями NoiseUint32(128*y+x). Точнее, 4 текстуры - младшие 8 бит, биты 8..15, биты 16..24, старшие 8 бит.

Резултаты:

+ libnoise

+ libnoise, модификация с использованием uint32_t
+ Borland LCG
+ Borland LCG, x5
+ xorshift128
+ xorshift128, x5
+ PCG

Видим, что версия }:+()___ [Smile] (если я его правильно понял) на глаз выглядит лучше всего, но сдаётся мне, там всё-равно диагональные полосы видны.

#7
13:10, 2 июля 2016

xorshift это стейтфул генератор, ты ему подавал 1,2,3... на вход, это неверно :) Надо подавать результат предыдущего вызова и следующий будет случайнее чем сейчас. Ну потому что это не функция шума, а именно псевдослучайный генератор.

А по хэшам это по виду именно то, что тебе надо. Гуглируй список алгоритмов хэщей. Вон либнойс взял и пользуйся :)

#8
15:54, 2 июля 2016

FordPerfect
> А подробнее можно пальцем ткнуть?
Подробно там и есть. Половина тома посвящена генераторам, больше 200 страниц. Все не просто и наивные генераторы как правило очень плохие. Из того, что ты не знаешь какие будут значения, вовсе не значит что они случайные. А если они и признаны случайными для одного применения, будут не случайными для другого. У разных потребителей разные требования к качеству.

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

#9
16:11, 2 июля 2016

Накодил вот такое:

uint32_t f8(uint32_t n)
{
    uint64_t state=n;
    state=state*state;
    state=state*6364136223846793005ULL+1442695040888963407ULL;
    uint32_t xorshifted=uint32_t(((state>>18u)^state)>>27u);
    uint32_t rot=uint32_t(state>>59u);
    return (xorshifted>>rot)|(xorshifted<<((-rot)&31));
}
На глаз вроде выглядит нормально.
Его бы на каких-нибудь специальных тестах прогнать.
У кого-то есть под рукой рабочий TestU01?

#10
18:21, 2 июля 2016

FordPerfect
> + libnoise, модификация с использованием uint32_t
Рекомендую вместо одного генератора на 32 бита взять 4 таких, каждый со своим семенем, и собирать верхние 8 бит. У линейных, как правило, чем правее цифра, тем меньше период (что и видно на текстурах).
FordPerfect
> У кого-то есть под рукой рабочий TestU01?
Кстати, зачем тебе нужен этот шум? В зависимости от назначения там свои требования будут. Если это текстура, то там достаточно, чтобы выглядело ровно, а с тонкостями можно и не заморачиваться.

FordPerfect
> Основные цели: генерация текстур и звука
А, ну вот.
У текстуры главное, чтобы приятно глазу было. Для звука хорошим критерием будет автокоррелляция - чем равномернее распределение по частотам, тем шум ближе к белому.
Теоретически, можно пойти от обратного - заполнить комплексный вектор одинаковыми амплитудами и средней случайности фазами, а затем сделать обратное FFT, правда, скорость будет не очень, да и диапазон у результата не гарантируется.

И 32 бита для обоих случаев - это оверкилл. Для звука очень хорошего качества достаточно 24 бит, а для HDR-текстуры - 16 бит/канал. Разные каналы в любом случае придётся генерировать раздельно, разве что если какой-нибудь убер-хеш не задействован.

#11
19:25, 2 июля 2016

На всякий случай:

Классический stateful rng здесь не ищется.
Потому что задача "нужен stateful rng для gamedev"- что её решать, можно взять PCG и не париться.

Но stateful rng - последовательный, что не всегда удобно. Иногда хочется чистой функции "индекс - значение" (ну например заполняем мы текстуру самплингом value noise, причём, например, координаты замеров не эквидистантны: tex(u,v)=SampleNoise(sin(u),cos(v))).

И хочется найти шумовую функцию, которая решает эту задачу примерно так же хорошо, как PCG - задачу "нужен stateful rng для gamedev".
Чтобы
>дальше копипастить из этой темы, не заморачиваясь переизобретением по каждому поводу

Ну и хочется качественное решение - общее, быстрое.

Ограничения на ровном месте не вдохновляют.
Задачу по возможности хочется возложить не на пользователя, а на составителя функции UintNoise.
Условно говоря: если пользователю нужно помнить, что нужно говорить rnd()>>24, а не rnd()&255, то ваша rnd() - отстой. Особенно - если можно без потерь сделать обще.

Хочется этой теме найти достаточно хорошую функцию. И дальше пользоваться.

#12
19:59, 2 июля 2016

https://www.shadertoy.com/view/MsV3z3 оч дешёвый и вроде паттернов никаких не раглядел

#13
21:12, 2 июля 2016

FordPerfect
> Видим, что версия }:+()___ [Smile] (если я его правильно понял) на глаз выглядит лучше всего, но сдаётся мне, там всё-равно диагональные полосы видны.
Да, я именно это имел в виду. Попробуй заменить итерацию LCG в начале на полином по типу libnoise, должно стать лучше.

#14
2:36, 3 июля 2016

FordPerfect

Мне как то требовалось такое.
Нужно было генерить случайные числа(вектора, цвета, матрицы)  для 1D,2D,3D,4D карт причем от позиции, а не последовательно. Не хранить все карты в памяти а от позиции восстановить.
В итоги получилась хэш.
Причем подбирал так что:
1) на изменение 1бита вероятность изменение любого бита на выходе 0.5
2) корреляция между измененным битом на входе и битами на выходе ->0
3) корреляция между выходными битами при изменение 1бита на входе->0

Использует SSE на выходе 128 бит.  трактовать можно как 16 char, или 4 uint32, 4 int32 ...

Если есть желание пощупать могу выложить код.

Страницы: 1 2 3 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.