Каково происхождение этого однострочника GLSL rand ()?

94

Я видел этот генератор псевдослучайных чисел для использования в шейдерах, упоминаемых здесь и там в сети :

float rand(vec2 co){
  return fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * 43758.5453);
}

Его по-разному называют «каноническим» или «однострочным, который я где-то нашел в Интернете».

Каково происхождение этой функции? Являются ли постоянные значения столь же произвольными, как кажутся, или их выбор является искусством? Есть ли обсуждение достоинств этой функции?

РЕДАКТИРОВАТЬ: самая старая ссылка на эту функцию, с которой я столкнулся, - это архив от февраля 2008 года , исходная страница теперь удалена из Интернета. Но там это обсуждается не больше, чем где-либо еще.

Грумдриг
источник
Это функция шума, используемая для создания процедурно созданного ландшафта. похоже на что-то вроде этого en.wikipedia.org/wiki/Perlin_noise
foreyez

Ответы:

42

Очень интересный вопрос!

Я пытаюсь понять это, набирая ответ :) Сначала простой способ поиграть с ним: http://www.wolframalpha.com/input/?i=plot%28+mod%28+sin%28x*12.9898 +% 2B + y * 78.233% 29 + * + 43758.5453% 2C1% 29x% 3D0..2% 2C + y% 3D0..2% 29

Затем давайте подумаем, что мы здесь пытаемся сделать: для двух входных координат x, y мы возвращаем «случайное число». Но это не случайное число. То же самое каждый раз, когда мы вводим одни и те же x, y. Это хеш-функция!

Первое, что делает функция, - это переход от 2d к 1d. Само по себе это неинтересно, но числа выбраны так, чтобы они обычно не повторялись. Также у нас есть добавление с плавающей запятой. Будет еще несколько бит от y или x, но числа могут быть просто выбраны правильно, чтобы получилось смешивание.

Затем мы выбираем функцию черного ящика sin (). Это будет во многом зависеть от реализации!

Наконец, он усиливает ошибку в реализации sin () путем умножения и взятия дроби.

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

Опять же, настоящая проблема с этой хеш-функцией заключается в том, что sin () - это черный ящик.

Starmole
источник
1
Это не отвечает на вопрос о происхождении, но я не думаю, что это действительно ответ. Я согласен с этим ответом из-за иллюстративного графика.
Grumdrig
19

Источником, вероятно, является статья: «О генерации случайных чисел с помощью y = [(a + x) sin (bx)] mod 1», WJJ Rey, 22-е Европейское совещание статистиков и 7-я Вильнюсская конференция по теории вероятностей и Математическая статистика, август 1998 г.

РЕДАКТИРОВАТЬ: Поскольку я не могу найти копию этой статьи, а ссылка на «TestU01» может быть непонятной, вот схема, описанная в TestU01 на псевдо-C:

#define A1 ???
#define A2 ???
#define B1 pi*(sqrt(5.0)-1)/2
#define B2 ???

uint32_t n;   // position in the stream

double next() {
  double t = fract(A1     * sin(B1*n));
  double u = fract((A2+t) * sin(B2*t));
  n++;
  return u;
} 

где единственное рекомендуемое постоянное значение - B1.

Обратите внимание, что это для потока. Преобразование в одномерный хэш 'n' становится целочисленной сеткой. Итак, я предполагаю, что кто-то видел это и преобразовал 't' в простую функцию f (x, y). Используя исходные константы, указанные выше, мы получим:

float hash(vec2 co){
  float t = 12.9898*co.x + 78.233*co.y; 
  return fract((A2+t) * sin(t));  // any B2 is folded into 't' computation
}
МБ Рейнольдс
источник
3
Действительно очень интересно! Я нашел статью, которая ссылается на него, а также на сам журнал в Google Книгах, но похоже, что доклад или сама статья не были включены в журнал.
Grumdrig
1
Кроме того, из заголовка следует, что функция, о которой я спрашиваю, должна возвращаться, fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * (co.xy + vec2(43758.5453, SOMENUMBER))чтобы соответствовать функции, о которой идет речь.
Grumdrig
И еще один момент: если это действительно источник использования функции, вопрос о происхождении магических чисел (выбор aи b), используемых снова и снова, остается, но, возможно, они использовались в статье, которую вы цитируете.
Grumdrig
Я тоже не могу найти бумагу. (править: та же статья, что и ссылка выше)
М.Б. Рейнольдс,
Обновите ответ, добавив больше информации.
MB Reynolds
8

постоянные значения произвольны, особенно если они очень большие и отличаются от простых чисел на пару десятичных знаков.

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

поскольку функция двумерная, скалярное произведение имеет эффект поворота периодической функции под наклоном относительно осей X и Y. Примерно в соотношении 13/79. Это неэффективно, вы действительно можете добиться того же, выполнив синус (13x + 79y), это также даст то же самое, я думаю, с меньшим количеством математики ..

Если вы найдете период функции как по X, так и по Y, вы можете сделать выборку, чтобы она снова выглядела как простая синусоида.

Вот картина его увеличенная в графике

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

инопланетный
источник
Но на графических процессорах X и Y находятся в диапазоне от 0 до 1, и это выглядит гораздо более случайным, если вы измените свой график. Я знаю, что это звучит как утверждение, но на самом деле это вопрос, потому что мое математическое образование закончилось в 18 лет.
Strings
я знаю, я просто увеличил масштаб, чтобы вы могли видеть, что случайная функция имеет такую ​​форму, за исключением того, что гребни очень быстро меняются, за исключением того, что вам нужно уменьшить масштаб, чтобы увидеть изменения вообще ... вы можете представить, что получение точек на гребнях даст довольно случайные числа от 0 до 1 по высоте для значений x и y от 1 до 1.
Aliential
О, я понимаю, и это кажется очень логичным для любой генерации случайных чисел, которая в своей основе использует функцию sin
Strings
2
По сути, это линейный зигзаг, и этот грех должен добавить крошечную вариацию, это то же самое, как если бы кто-то очень быстро перебрасывал колоду карт от 1 до 10 по кругу перед вами, и вы должны попробовать В конце выберите набор чисел с карточек, они будут случайными числами, потому что они будут перемещаться очень быстро, и он сможет получить узор только путем выбора карточек в точной синхронизации относительно того, как быстро карточки вращаются.
aliential
Просто примечание, это было бы не быстрее, (13x + 79y)потому что он dot(XY, AB)будет делать именно то, что вы описываете, как скалярное произведение, котороеx,y dot 13, 79 = (13x + 79y)
2018,
1

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

РЕДАКТИРОВАТЬ: В основном функция фракт (sin (x) * 43758.5453) представляет собой простую хеш-подобную функцию, sin (x) обеспечивает плавную интерполяцию sin от -1 до 1, поэтому sin (x) * 43758.5453 будет интерполяцией из - 43758.5453 к 43758.5453. Это довольно большой диапазон, поэтому даже небольшой шаг по x обеспечит большой шаг в результате и действительно большое изменение дробной части. «Фракт» нужен для получения значений в диапазоне от -0,99 ... до 0,999 .... Теперь, когда у нас есть что-то вроде хеш-функции, мы должны создать функцию для производственного хеша из вектора. Самый простой способ - это вызвать "хеш" отдельно для x любой компоненты y входного вектора. Но тогда у нас будут некоторые симметричные значения. Итак, мы должны получить некоторое значение из вектора, подход состоит в том, чтобы найти некоторый случайный вектор и найти "точечный" продукт на этот вектор, вот и мы: фракт (sin (точка (co.xy, vec2 (12.9898,78.233))) * 43758.5453); Также, в соответствии с выбранным вектором, его длина должна быть длинной, чтобы было несколько периодов функции «sin» после вычисления «скалярного» произведения.

Римский
источник
но тогда 4e5 тоже должно работать, я не понимаю, почему магическое число 43758.5453. (также, я бы компенсировал x некоторым дробным числом, чтобы избежать rand (0) = 0.
Фабрис НЕЙРЕТ
1
Я думаю, что с 4e5 вы не получите столько вариаций дробных битов, это всегда будет давать вам одно и то же значение. Итак, должны быть выполнены два условия: достаточно большие и достаточно хорошие вариации дробных частей.
Роман
что вы имеете в виду, "всегда будет давать вам одинаковую ценность"? (если вы имеете в виду, что он всегда будет принимать одни и те же цифры, во-первых, они все еще хаотичны, во-вторых, float хранятся как m * 2 ^ p, а не 10 ^ p, поэтому * 4e5 все еще шифрует биты).
Фабрис НЕЙРЕТ
Я думал, вы написали экспоненциальное представление числа, 4 * 10 ^ 5, поэтому sin (x) * 4e5 даст вам не такое хаотичное число. Я согласен, что дробные биты из sin wave также дадут вам хороший chatoic.
Роман
Но тогда это зависит от диапазона x, я имею в виду, должна ли функция быть устойчивой для малых (-0,001, 0,001) и больших значений (-1, 1). Вы можете попробовать увидеть разницу с помощью фракта (sin (x /1000.0) * 43758.5453); и фракт (sin (x /1000.0) * 4e5) ;, где x находится в диапазоне [-1., 1.]. Во втором варианте изображение будет более монотонным (по крайней мере, я вижу разницу в шейдере). Но в целом я согласен с тем, что можно использовать 4e5 и получить достаточно хороший результат.
Роман