шумовые ф-ции
- From
- Boris Rudakov (2:5054/9.4)
- To
- Alex Maltsev
- Date
- 2000-03-03T13:15:29Z
- Area
- RU.ALGORITHMS
Hello Alex!
01 Mar 00 18:18, Alex Maltsev wrote to All:
AM> Hello, All!
AM> Что такое сабж? Объясните плс в общих чертах. Инета нет....
Очень на пальцах:
Шумовая функция размерности N, это такая функция, которая для каждой точки N-мерного пространстява выдает некоторое псевдослучайное число. Как правило, такие функции по алгоритмам, близким к общепринятому random, могут вычислить значения функции в точках, с координатами кратными некоторой величине, и интерполируют результат на промежуточные координаты. Хочу подчеркнуть, что шумовая функция является функцией от координат, и однозначно определена для каждой точки пространства (т.е. двумерная шумовая функция _однозначно_ определена для каждой пары x,y и в этой точке _всегда_ возвращает одно и то же значение). Это важно потому, что простенький алгоритм на базе стандартного random волен при каждом следующем вызове возвращать в той же точке что-то новенькое, в то время как шумовая функция - это функция, и возвращает однозначно определенное значение.
В последнее десятилетие шумовые функции применяются очень широко для моделирования самых разнообразных естественных эффектов. Однако, основное их применение - графика (ради которой они, собственно, и были изобретены). Не даром Кен Перлин (Ken Perlin) среди нескольких десятков наград, полученных за свою знаменитую Perlin Noise, получил еще и Оскара.
Практически 99% всех применяемых в настоящий момент шумовых функций являются либо вариациями, либо надстройками над Perlin Noise. Perlin Noise получает на вход координаты точки (1D, 2D, 3D - в зависимости от модификации функции) и на выход подает псевдослучайное число в диапазоне -1..1. С этим результатом ты можешь делать все что хош. Например, сделать так: Pixel[X][Y] = (noise2(X,Y) + 1.0) * 128; Однако, на практеке над результатом Perlin Noise строят здоровенную надстройку из разных sin, fmod, pow и прочего, добиваясь самых разнообразных и удивительных результатов: всякие текстуры под гранит, агат, газ - бесконечное количество вариаций.
Далее, на базе шумовых функций строятся так называемые ФРАКТАЛЬНЫЕ шумовые функции. Кроме координат точки, такая функция получает некий коэффициент, отвечающий за количество итераций (как правило зависит от разрешения в котором применяется функция) и проводит несколько итераций по вычислению шума: на каждой итерации кооржинаты получают некоторый инкремент (у Перлина в его Turbulent Noise это умножение координат на 2 при каждой итерации), а результат с некоторым все убывающим коэффициентом прибавляется к результату (у Перлина коэффициент делится пополам при каждой итерации). Таким образом, каждая итерация добавляет все более мелкое дребезжание у результату, а число итераций зависит только от жалаемой детализации. Практически, фрактальная шумовая функция имеет бесконечную разрешающую способность, ограниченную только точностью FPU и здравым смыслом.
Среди реализаций шумовых функций нужно особо выделить оригинальную реализацию Перлина (авторские реализации для 1D, 2D и 3D), его же Turbulent Noise для тех же размерностей. Очень неплохая вариация алгоритма реализована в рэйтрейсере POV-Ray - там применена забавная Hash-таблица, а результат функции более контрастный, нежели у Кена. Более высокоуровневых же функций на их базе просто невозможно пересчитать - они повсюду. Особенно мне нравятся функции моделирования газовых субстанций Дэвида Эберта (David S. Ebert), ландшафтные функции F.Kenton Musgrave, очень неплохой набор текстур в POV-Ray (текстура Granite просто вне конкуренции, надо будет ее в 3DSMAX портировать), наборы текстур в 3DSMAX, забавный, хотя и медленный алгоритм генерации облаков от Hugo Elias.
Ну и в заключение (раз уж у тебя ИНета нет) позволю себе процитировать 3 килобайта оригинального алгоритма Кена Перлина (с моей минимальной правкой, касаемо моделей вызова функций):
От меня:
#ifdef __WIN32__
# define INTERNPROC __fastcall
# define LOCALPROC static __fastcal
#else
# define INTERNPROC __fastcall
# define LOCALPROC static __near __fastcall
#endif
=== Cut ===
/* coherent noise function over 1, 2 or 3 dimensions */
/* (copyright Ken Perlin) */
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define B 0x100
#define BM 0xff
#define N 0x1000
#define NP 12 /* 2^N */
#define NM 0xfff
static p[B + B + 2];
static float g3[B + B + 2][3];
static float g2[B + B + 2][2];
static float g1[B + B + 2];
static start = 1;
void LOCALPROC init(void);
#define random() rand()
#define s_curve(t) ( t * t * (3. - 2. * t) )
#define lerp(t, a, b) ( a + t * (b - a) )
#define setup(i,b0,b1,r0,r1)\
t = vec[i] + N;\
b0 = ((int)t) & BM;\
b1 = (b0+1) & BM;\
r0 = t - (int)t;\
r1 = r0 - 1.;
double INTERNPROC noise1(double arg)
{
int bx0, bx1;
float rx0, rx1, sx, t, u, v, vec[1];
vec[0] = arg;
if (start) {
start = 0;
init();
}
setup(0, bx0,bx1, rx0,rx1);
sx = s_curve(rx0);
u = rx0 * g1[ p[ bx0 ] ];
v = rx1 * g1[ p[ bx1 ] ];
return lerp(sx, u, v);
}
float INTERNPROC noise2(float vec[2])
{
int bx0, bx1, by0, by1, b00, b10, b01, b11;
float rx0, rx1, ry0, ry1, *q, sx, sy, a, b, t, u, v;
register i, j;
if (start) {
start = 0;
init();
}
setup(0, bx0,bx1, rx0,rx1);
setup(1, by0,by1, ry0,ry1);
i = p[ bx0 ];
j = p[ bx1 ];
b00 = p[ i + by0 ];
b10 = p[ j + by0 ];
b01 = p[ i + by1 ];
b11 = p[ j + by1 ];
sx = s_curve(rx0);
sy = s_curve(ry0);
#define at2(rx,ry) ( rx * q[0] + ry * q[1] )
q = g2[ b00 ] ; u = at2(rx0,ry0);
q = g2[ b10 ] ; v = at2(rx1,ry0);
a = lerp(sx, u, v);
q = g2[ b01 ] ; u = at2(rx0,ry1);
q = g2[ b11 ] ; v = at2(rx1,ry1);
b = lerp(sx, u, v);
return lerp(sy, a, b);
}
float INTERNPROC noise3(float vec[3])
{
int bx0, bx1, by0, by1, bz0, bz1, b00, b10, b01, b11;
float rx0, rx1, ry0, ry1, rz0, rz1, *q, sy, sz, a, b, c, d, t, u, v;
register i, j;
if (start) {
start = 0;
init();
}
setup(0, bx0,bx1, rx0,rx1);
setup(1, by0,by1, ry0,ry1);
setup(2, bz0,bz1, rz0,rz1);
i = p[ bx0 ];
j = p[ bx1 ];
b00 = p[ i + by0 ];
b10 = p[ j + by0 ];
b01 = p[ i + by1 ];
b11 = p[ j + by1 ];
t = s_curve(rx0);
sy = s_curve(ry0);
sz = s_curve(rz0);
#define at3(rx,ry,rz) ( rx * q[0] + ry * q[1] + rz * q[2] )
q = g3[ b00 + bz0 ] ; u = at3(rx0,ry0,rz0);
q = g3[ b10 + bz0 ] ; v = at3(rx1,ry0,rz0);
a = lerp(t, u, v);
q = g3[ b01 + bz0 ] ; u = at3(rx0,ry1,rz0);
q = g3[ b11 + bz0 ] ; v = at3(rx1,ry1,rz0);
b = lerp(t, u, v);
c = lerp(sy, a, b);
q = g3[ b00 + bz1 ] ; u = at3(rx0,ry0,rz1);
q = g3[ b10 + bz1 ] ; v = at3(rx1,ry0,rz1);
a = lerp(t, u, v);
q = g3[ b01 + bz1 ] ; u = at3(rx0,ry1,rz1);
q = g3[ b11 + bz1 ] ; v = at3(rx1,ry1,rz1);
b = lerp(t, u, v);
d = lerp(sy, a, b);
return lerp(sz, c, d);
}
void LOCALPROC normalize2(float v[2])
{
float s;
s = sqrt(v[0] * v[0] + v[1] * v[1]);
v[0] = v[0] / s;
v[1] = v[1] / s;
}
void LOCALPROC normalize3(float v[3])
{
float s;
s = sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
v[0] = v[0] / s;
v[1] = v[1] / s;
v[2] = v[2] / s;
}
void LOCALPROC init(void)
{
int i, j, k;
for (i = 0 ; i < B ; i++) {
p[i] = i;
g1[i] = (float)((random() % (B + B)) - B) / B;
for (j = 0 ; j < 2 ; j++)
g2[i][j] = (float)((random() % (B + B)) - B) / B;
normalize2(g2[i]);
for (j = 0 ; j < 3 ; j++)
g3[i][j] = (float)((random() % (B + B)) - B) / B;
normalize3(g3[i]);
}
while (--i) {
k = p[i];
p[i] = p[j = random() % B];
p[j] = k;
}
for (i = 0 ; i < B + 2 ; i++) {
p[B + i] = p[i];
g1[B + i] = g1[i];
for (j = 0 ; j < 2 ; j++)
g2[B + i][j] = g2[i][j];
for (j = 0 ; j < 3 ; j++)
g3[B + i][j] = g3[i][j];
}
}
=== Cut ===
А вот его же оригинальная реализация фрактального шума:
=== Cut ===
float turbulence(point, lofreq, hifreq)
float point[3], freq, resolution;
{
float noise3(), freq, t, p[3];
p[0] = point[0] + 123.456;
p[1] = point[1];
p[2] = point[2];
t = 0;
for (freq = lofreq ; freq < hifreq ; freq *= 2.) {
t += fabs(noise3(p)) / freq;
p[0] *= 2.;
p[1] *= 2.;
p[2] *= 2.;
}
return t - 0.3; /* readjust to make mean value = 0.0 */
}
=== Cut ===
А вот текстура Granite, взятая мной из POV-Ray (примечание: тут используется не оригинальная Perlin Noise, а ее вариация из POV-Ray - Noise(Point3& P), которая дает более контрастный результат):
=== Cut ===
float INTERNPROC Granite(Point3& P)
{
Point3 V1 = P * 4;
float Freq = 1, ANoise = 0;
for (UINT I = 0; I < 6; Freq *= 2, I++)
ANoise += fabs(0.5 - Noise(V1 * Freq)) / Freq;
return ANoise;
}
=== Cut ===
Вот также спертая из POV-Ray их вариация фрактального шума:
=== Cut ===
float INTERNPROC Turbulence(Point3& P, float Lambda, float Omega, int Octaves)
{
float L = Lambda, O = Omega, Value = Noise(EPoint);
for (int I = 2; I <= Octaves; I++) {
Value += O * Noise(P * L);
if (I < Octaves) {
L *= Lambda;
O *= Omega;
}
}
return Value;
}
=== Cut ===
ЗЫ: Функции рассчитаны на входные координаты в диапазоне -1..1, при других диапазонах просто делается масштабирование; как обычно, корорче.
AM> ЗЫЖ учусь в 11 классе
:)
Boris Rudakov, И конечно тут же я понравился бы всем,
BBR Стали б все меня любить еще больше чем теперь.
--- Be happy: BBR is looking at you !
* Origin: АлкАголь малыми дозами безвреден в любых количествах (2:5054/9.4)