Apakah ada (derau) fungsi noise monotonik yang tidak berkurang?

10

Saya ingin fungsi untuk menghidupkan objek yang bergerak dari titik A ke titik B dari waktu ke waktu, sehingga mencapai B pada waktu tertentu, tetapi posisinya kapan saja secara acak terganggu secara terus-menerus, tetapi tidak pernah mundur. Objek bergerak sepanjang garis lurus, jadi saya hanya perlu satu dimensi.

Secara matematis, itu berarti saya mencari beberapa kontinu f (x), x ∈ [0,1], sehingga:

  • f (0) = 0
  • f (1) = 1
  • x <y → f (x) ≤ f (y)
  • Pada "sebagian besar" titik f (x + d) - f (x) tidak memiliki hubungan yang jelas dengan d. (Fungsi tidak meningkat secara seragam atau dapat diprediksi; saya pikir itu juga setara dengan mengatakan tidak ada derajat turunan yang konstan.)

Idealnya, saya sebenarnya ingin beberapa cara untuk memiliki keluarga fungsi-fungsi ini, menyediakan beberapa kondisi awal. Saya membutuhkan setidaknya 4 bit benih (16 fungsi yang mungkin), untuk penggunaan saya saat ini, tetapi karena itu tidak banyak merasa bebas untuk memberikan lebih banyak lagi.

Untuk menghindari berbagai masalah dengan akumulasi kesalahan, saya lebih suka fungsi ini tidak memerlukan kondisi internal apa pun. Artinya, saya ingin itu menjadi fungsi nyata, bukan "fungsi" pemrograman.


sumber
3
Persyaratan ketiga dan keempat Anda dapat diperkirakan f'(x)>0, sehingga integrasi normal dari nilai absolut dari setiap fungsi noise akan memenuhi semua kebutuhan Anda. Sayangnya saya tidak tahu cara mudah untuk menghitung itu, tetapi mungkin orang lain melakukannya. :)
SkimFlux
Akankah mengganggu fungsi tegak lurus lereng Anda berfungsi?
kaoD
Ketika Anda mengatakan "Untuk menghindari berbagai masalah dengan akumulasi kesalahan" saya pikir Anda khawatir tentang presisi. Tampaknya, berdasarkan banyak komentar Anda, Anda prihatin dengan biaya kinerja dari banyak evaluasi. Anda harus menyatakan dengan pasti apa batasan kinerja dan memori yang harus kita tangani - persyaratannya tetap tidak membantu karena seseorang tampaknya dapat membangun fungsi dengan keadaan yang tidak memiliki kesalahan akumulasi (apa artinya, sih?). Juga, poin ke-4 Anda salah. Contoh sepele: Tidak ada turunan dari e ^ x adalah konstan, jadi itu tidak setara dengan mengatakan itu.
Biasa

Jawaban:

4

Untuk posting ini, y = f (t) di mana t adalah parameter yang Anda variasikan (waktu / kemajuan) dan y adalah jarak ke target. Jadi saya akan berbicara dalam hal titik pada plot 2D di mana sumbu horizontal adalah waktu / kemajuan dan vertikal adalah jarak.

Saya pikir Anda bisa membuat kurva Bezier kubik dengan titik pertama di (0, 1) dan keempat (terakhir) titik di (1, 0). Dua titik tengah dapat ditempatkan secara acak (x = rand, y = rand) dalam kotak 1-by-1 ini. Saya tidak dapat memverifikasi ini secara analitis, tetapi hanya dari bermain-main dengan applet (yeah, silakan saja dan tertawa) tampaknya kurva Bezier tidak akan pernah berkurang dengan kendala seperti itu.

Ini akan menjadi fungsi dasar Anda b (p1, p2) yang menyediakan jalur non-menurun dari titik p1 ke titik p2.

Sekarang Anda dapat menghasilkan ab (p (1) = (0, 1), p (n) = (1, 0)) dan memilih sejumlah p (i) sepanjang kurva ini sehingga 1

Pada dasarnya, Anda membuat satu jalur "umum", dan kemudian memecahnya menjadi segmen dan meregenerasi setiap segmen.

Karena Anda menginginkan fungsi matematika: Misalkan prosedur di atas dikemas ke dalam satu fungsi y = f (t, s) yang memberi Anda jarak pada t untuk fungsi seed s. Anda akan perlu:

  • 4 angka acak untuk menempatkan 2 titik tengah dari spline Bezier utama (dari (0, 1) hingga (1, 0))
  • nomor n-1 untuk batas setiap segmen jika Anda memiliki n segmen (segmen pertama selalu dimulai pada (0, 1) yaitu t = 0 dan ujung terakhir pada (1,0) yaitu t = 1)
  • 1 angka jika Anda ingin mengacak jumlah segmen
  • 4 angka lebih banyak untuk menempatkan titik tengah spline segmen tempat Anda akan t

Jadi setiap benih harus menyediakan salah satu dari yang berikut ini:

  • 7 + n bilangan real antara 0 dan 1 (jika Anda ingin mengontrol jumlah segmen)
  • 7 bilangan real dan satu bilangan bulat lebih besar dari 1 (untuk jumlah segmen acak)

Saya membayangkan Anda dapat mencapai salah satu dari ini dengan hanya menyediakan array angka sebagai benih. Atau, Anda bisa melakukan sesuatu seperti memasok satu angka s sebagai seed, dan kemudian memanggil generator angka acak bawaan dengan rand, rand (s + 1), rand (s + 2) dan sebagainya (atau menginisialisasi dengan s dan kemudian terus memanggil rand.NextNumber).

Perhatikan bahwa meskipun seluruh fungsi f (t, s) terdiri dari banyak segmen, Anda hanya mengevaluasi satu segmen untuk setiap t. Anda akan perlu berulang kali menghitung batas-batas segmen dengan metode ini, karena Anda akan harus menyortir mereka untuk memastikan tidak ada dua segmen tumpang tindih. Anda mungkin dapat mengoptimalkan dan menyingkirkan pekerjaan tambahan ini dan hanya menemukan titik akhir dari satu segmen untuk setiap panggilan, tetapi tidak jelas bagi saya saat ini.

Juga, kurva Bezier tidak diperlukan, spline berperilaku yang sesuai akan dilakukan.

Saya membuat contoh implementasi Matlab.

Fungsi Bezier (vektor):

function p = bezier(t, points)
% p = bezier(t, points) takes 4 2-dimensional points defined by 2-by-4 matrix
% points and gives the value of the Bezier curve between these points at t.
% 
% t can be a number or 1-by-n vector. p will be an n-by-2 matrix.
    coeffs = [
        (1-t').^3, ...
        3*(1-t').^2.*t', ...
        3*(1-t').*t'.^2, ...
        t'.^3
    ];

    p = coeffs * points;
end

Fungsi majemuk Bezier yang dijelaskan di atas (sengaja dibiarkan tidak terverifikasi untuk memperjelas berapa banyak evaluasi yang diperlukan untuk setiap panggilan):

function p = bezier_compound(t, ends, s)
% p = bezier(t, points) takes 2 2-dimensional endpoints defined by a 2-by-2
% matrix ends and gives the value of a "compound" Bezier curve between
% these points at t.
% 
% t can be a number or 1-by-n vector. s must be a 1-by-7+m vector of random
% numbers from 0 to 1. p will be an n-by-2 matrix. 
    %% Generate a list of segment boundaries
    seg_bounds = [0, sort(s(9:end)), 1];

    %% Find which segment t falls on
    seg = find(seg_bounds(1:end-1)<=t, 1, 'last');

    %% Find the points that segment boundaries evaluate to
    points(1, :) = ends(1, :);
    points(2, :) = [s(1), s(2)];
    points(3, :) = [s(3), s(4)];
    points(4, :) = ends(2, :);

    p1 = bezier(seg_bounds(seg), points);
    p4 = bezier(seg_bounds(seg+1), points);

    %% Random middle points
    p2 = [s(5), s(6)] .* (p4-p1) + p1;
    p3 = [s(7), s(8)] .* (p4-p1) + p1;

    %% Gather together these points
    p_seg = [p1; p2; p3; p4];

    %% Find what part of this segment t falls on
    t_seg = (t-seg_bounds(seg))/(seg_bounds(seg+1)-seg_bounds(seg));

    %% Evaluate
    p = bezier(t_seg, p_seg);    
end

Script yang memplot fungsi untuk seed acak (perhatikan bahwa ini adalah satu-satunya tempat di mana fungsi acak dipanggil, variabel acak ke semua kode lain disebarkan dari satu array acak ini):

clear
clc

% How many samples of the function to plot (higher = higher resolution)
points = 1000;

ends = [
    0, 0;
    1, 1;
    ];

% a row vector of 12 random points
r = rand(1, 12);

p = zeros(points, 2);

for i=0:points-1
    t = i/points;
    p(i+1, :) = bezier_compound(t, ends, r);
end

% We take a 1-p to invert along y-axis here because it was easier to
% implement a function for slowly moving away from a point towards another.
scatter(p(:, 1), 1-p(:, 2), '.');
xlabel('Time');
ylabel('Distance to target');

Berikut ini contoh keluaran:

masukkan deskripsi gambar di sini

Tampaknya memenuhi sebagian besar kriteria Anda. Namun:

  • Ada "sudut". Ini mungkin bisa diterima dengan menggunakan kurva Bezier lebih tepat.
  • Ini "jelas" terlihat seperti splines, meskipun Anda tidak bisa menebak apa yang akan dilakukan setelah periode waktu yang tidak sepele kecuali Anda tahu benihnya.
  • Sangat jarang menyimpang terlalu banyak ke sudut (dapat diperbaiki dengan bermain dengan distribusi generator benih).
  • Fungsi Bezier kubik tidak dapat mencapai area dekat sudut mengingat kendala ini.
Hebat
sumber
1

Saya kira bahwa alih-alih memadukan sekelompok cosinus yang ditransformasi (seperti yang diberikan produk titik dalam perlin noise), Anda dapat memadukan beberapa fungsi monoton yang dimulai dari f (0) = 0, seperti f (x) = x, atau 2x, atau x ^ 2, dll. Faktanya karena domain Anda terbatas pada 0 => 1, Anda juga dapat memadukan fungsi trigonometri yang sesuai dengan tagihan dalam domain tersebut seperti cos (90 * x + 270). Untuk menormalkan metode Anda hingga berakhir pada 1, Anda bisa membagi jumlah tertimbang dari metode monotonik ini mulai dari f (0) = 0 oleh f (1). Sesuatu seperti ini harusnya cukup mudah untuk dibalik juga (yang saya kumpulkan Anda inginkan dari sedikit tentang fungsi real stateless versus fungsi pemrograman).

Semoga ini membantu.

Gary Dahl
sumber
1

Orang dapat menganalisis gambar kasar ini. masukkan deskripsi gambar di sini Anda dapat berakhir dengan fungsi yang menjalankan animasi Anda dengan cepat, dengan memanfaatkan fungsi rand yang seragam. Saya tahu ini bukan rumus matematika yang tepat, tetapi sebenarnya tidak ada rumus matematika untuk fungsi acak, dan bahkan jika ada, Anda akan banyak mengkode untuk mencapai ini. Mengingat Anda tidak menentukan kondisi kelancaran, profil kecepatannya adalah $ C ^ 0 $ terus menerus (tetapi karena Anda tidak berurusan dengan robot, tidak perlu khawatir tentang profil percepatan yang terputus-putus).

teko teh
sumber
"Sebenarnya tidak ada rumus matematika untuk fungsi acak" Saya ingin fungsi noise, bukan fungsi acak. Fungsi kebisingan didokumentasikan dengan baik untuk ada. Definisi sedikit demi sedikit seperti ini juga cenderung menciptakan inefisiensi (mengevaluasi menjadi O (buah) yang menjadi masalah ketika Anda memiliki skala waktu yang lama), fungsi tidak murni (mengevaluasi dalam O (1) tetapi perlu mempertahankan posisi sebelumnya), atau membatasi fungsi yang mungkin (mis. semua titik belok berada pada interval tetap).
Hmm, maaf, saya pikir fungsi noise juga menggunakan prosedur penghasil angka acak dan yang juga bergantung pada seperangkat panduan / poin kunci yang terpisah untuk menghasilkan bentuk (saya melihat Perlin Noise disebutkan .. bahwa seseorang bekerja melalui pseudo-acak jumlah generator yang cukup sulit untuk diintegrasikan, karenanya tidak ada solusi analitik). Bisakah satu mengintegrasikan fungsi noise secara analitis? Saya bertanya-tanya apakah salah satu dari ini bisa menjadi tautan
teodron
Sebagai contoh, noise Perlin mengambil status seed dari angka 255 8 bit, tetapi dari situ menghasilkan noise acak dalam jarak tak terbatas dalam tiga dimensi; itu tidak benar-benar akurat untuk menggambarkan mereka sebagai "titik panduan", secara matematis mereka lebih seperti 256 parameter lain yang tidak ingin Anda berikan. Seperti yang Anda katakan itu pada dasarnya tidak dapat diintegrasikan, tetapi ini adalah fungsi murni. Halaman yang Anda tautkan adalah penjelasan buruk tentang Perlin noise (sebenarnya bukan Perlin noise yang dijelaskannya). Adapun apakah itu mungkin untuk beberapa jenis fungsi noise ... yah, itu pertanyaannya, bukan?
1

Cara yang biasa untuk menghasilkan urutan peningkatan angka acak N dari [0,1] adalah dengan menghasilkan angka acak N dalam rentang apa pun, kemudian membaginya semua dengan jumlah totalnya, kemudian menjumlahkannya satu per satu untuk mendapatkan urutan.

Hasilkan urutan 2, 2, 5, 8, 6.
Jumlah mereka adalah 23, jadi jumlah kami yang dijumlahkan adalah 2/23, 2/23, 5/23, 8/23, dan 6/23.
Urutan terakhir kami adalah 2/23, 4/23, 9/23, 17/23, 23/23

Ini dapat diperluas ke 2D dengan menghasilkan nilai-nilai ini untuk X dan Y. Anda dapat meningkatkan N untuk mendapatkan rincian yang Anda inginkan.


Dalam jawaban serupa @ teodron, Anda mengutip masalah efisiensi dengan skala waktu yang besar. Tanpa mengetahui masalah sebenarnya yang Anda hadapi, saya tidak bisa memastikan apakah kekhawatiran itu valid; tetapi opsi lain adalah menghasilkan untuk N kecil , dan hanya memperlancar hasilnya. Tergantung pada aplikasi, ini sebenarnya dapat memberikan hasil yang lebih baik .

masukkan deskripsi gambar di sini
N = 100, tidak ada smoothing

masukkan deskripsi gambar di sini
N = 15, dengan smoothing

BlueRaja - Danny Pflughoeft
sumber
Apa pun yang Anda lakukan untuk memuluskan, tampaknya hasilnya bahkan tidak berfungsi (sekitar x = 0,95); Saya tidak yakin apakah itu artifak dari program grafik Anda atau kesalahan. Monotonicity juga tampaknya dilanggar sekitar 0,7. Ngomong-ngomong, saya terbiasa dengan "jalan biasa" - Saya mengajukan pertanyaan ini karena saya curiga cara biasa jelek. Pre-Perlin-noise, setelah semua, tidak ada yang punya masalah dengan LUT raksasa nilai kebisingan, itu hanya "cara biasa". Saat ini, kami memiliki cara yang jauh lebih fleksibel dan efisien.
3
Saya setuju dengan BlueRaja: Ada beberapa cara penghalusan yang terkenal dan mudah diimplementasikan tanpa melanggar sifat monoton, apa pun contohnya. Misalnya, moving average atau gambar splines. Namun, kekhawatiran @JoeWreschnig tidak relevan. Aturan dan mekanisme gim mungkin bergantung pada objek yang tidak pernah mundur untuk berfungsi - jarang ada ide bagus untuk mengasumsikan bahwa benda yang penanya tidak benar-benar membutuhkan apa yang menurutnya dibutuhkan.
Biasa
1
@BlueRaja: Keluhan dasar saya tentang pendekatan piecewise seperti ini dijelaskan dalam tanggapan saya terhadap teodrone. Ini bukan tentang menemukan "hasil yang paling kaku dan tepat secara matematis" - ini tentang membuka kemungkinan baru dengan alat matematika yang sebelumnya tidak diketahui oleh kita. Sekali lagi, pertimbangkan analogi antara LUT nilai kebisingan raksasa dan kebisingan Perlin. Tidak setiap pertanyaan di situs ini membutuhkan jawaban "cukup baik" yang tidak masuk akal, setiap sarjana CS yang setengah cerdas dapat menggebrak di antara kuliah - kadang-kadang, mari kita bidik untuk melakukan sesuatu yang asli dan profesional, oke?
1
Atau kita bisa terus membiarkan situs ini berkubang dalam 90% kebingungan mendasar tentang matriks transformasi, 10% "bantu aku berhenti bermain game!" Itu akan membuat situs tanya jawab yang luar biasa yang disukai oleh setiap profesional.
2
@ Jo: Itu, erm, tidak pantas untuk. Anda meminta solusi agar sesuai dengan kriteria Anda, saya berikan satu. Hanya karena sederhana tidak membuatnya buruk.
BlueRaja - Danny Pflughoeft
1

Saya menyarankan implementasi ini terinspirasi oleh penjumlahan oktaf yang ditemukan dalam fraktal noise, dengan sedikit keledai murahan di sana-sini. Saya percaya ini cukup cepat dan dapat disetel dengan meminta oktaf lebih sedikit daripada disimpan dalam parameter dengan kehilangan presisi sekitar 1/2^octave.

Anda bisa melihatnya sebagai implementasi sedikit demi sedikit yang hanya membutuhkan waktu O (log (potongan)) . Array parameter digunakan baik untuk posisi pivot divide-and-conquer, dan untuk jarak yang ditempuh ketika mencapai pivot.

template<int N> struct Trajectory
{
    Trajectory(int seed = 0)
    {
        /* The behaviour can be tuned by changing 0.2 and 0.6 below. */
        if (seed)
            srand(seed);
        for (int i = 0; i < N; i++)
            m_params[i] = 0.2 + 0.6 * (double)(rand() % 4096) / 4096;
    }

    double Get(double t, int depth = N)
    {
        double min = 0.0, max = 1.0;
        for (int i = 0, dir = 0; i < N && i < depth; i++)
        {
            int j = (dir + 1 + i) % N;
            double mid = min + (max - min) * m_params[j];
            if (t < m_params[i])
            {
                dir += 1;
                t = t / m_params[i];
                max = mid;
            }
            else
            {
                dir ^= i;
                t = (t - m_params[i]) / (1.0 - m_params[i]);
                min = mid;
            }
        }
        t = (3.0 - 2.0 * t) * t * t; // Optional smoothing
        return min + (max - min) * t;
    }

    double m_params[N];
};

Itu bisa dibuat lebih cepat dengan pra-komputasi divisi floating point, dengan biaya menyimpan informasi tiga kali lipat.

Ini adalah contoh cepat:

lima lintasan yang berbeda

Contoh diperoleh dengan kode berikut:

for (int run = 0; run < 5; run++)
{
    /* Create a new shuffled trajectory */
    Trajectory<12> traj;

    /* Print dots */
    for (double t = 0; t <= 1.0; t += 0.0001)
        printf("%g %g\n", t, traj.Get(t));
}
sam hocevar
sumber
0

Berpikir keras, dan mengakui kalkulus bukanlah poin kuat saya ... apakah ini mungkin tidak mungkin? Untuk menghindari pola yang jelas, rata-rata fungsi noise atas setiap perubahan dalam x harus mendekati nol, dan untuk menjamin monotonitas, amplitudo noise dari perubahan dalam x harus lebih kecil daripada perubahan dalam x, karena amplitudo yang lebih besar dapat menghasilkan nilai yang lebih rendah pada x 'relatif terhadap x. Tapi itu berarti bahwa ketika Anda mengurangi dx ke 0, fungsi seperti itu juga harus mengurangi dA (di mana A adalah amplitudo) menuju nol, yang berarti Anda tidak mendapatkan kontribusi dari fungsi kebisingan yang sesuai.

Saya bisa membayangkan itu mungkin untuk merumuskan fungsi yang secara bertahap mengurangi kontribusi kebisingan sebagai x mendekati 1, tetapi itu akan memberi Anda fungsi melengkung yang melambat ketika x mendekati 1, yang bukan apa yang saya pikir Anda inginkan.

Kylotan
sumber
1
Saya dapat menggambar jutaan grafik dari fungsi-fungsi tersebut, dan seperti yang dikatakan SkimFlux, integrasi fungsi noise memberikan fungsi yang secara praktis setara jika Anda menormalkannya. Jadi fungsi ada , itu hanya masalah apakah mereka dapat dikodekan . Oleh karena itu bertanya di sini alih-alih math.se.
Misalnya, fungsi apa pun yang melambat saat x mendekati 1 memiliki fungsi "terbalik" yang setara g(x) = 1 - f(1 - x), yang sebaliknya berakselerasi saat x berangkat 0.
Tentu, fungsinya ada - Anda bisa menggambar yang seperti teodron lakukan - tetapi apakah fungsinya 'berisik'? Noise menyiratkan fungsi kontinu berdasarkan input pseudo-acak dengan amplitudo implisit relatif terhadap baseline. Dan jika amplitudo itu terlalu tinggi maka Anda tidak dapat menjamin perbedaan antara langkah-langkah cukup rendah untuk menjaga output monoton. Tetapi memang terpikir oleh saya bahwa kepadatan kebisingan dan langkah interpolasi dapat dibuat untuk memenuhi spesifikasi Anda, yang akan saya pikirkan sedikit lebih banyak tentang.
Kylotan
Noise hanya berarti "tidak dapat diprediksi", ia tidak mengatakan apa pun tentang metode pembuatannya (atau bahkan, secara teknis, kontinuitas, meskipun untuk animasi Anda hampir selalu menginginkan noise yang koheren). Memang benar bahwa titik akhir tetap membatasi amplitudo fungsi yang mungkin agak, tetapi tidak sepenuhnya. Fungsi noise lainnya memiliki sifat yang serupa, misalnya Perlin (x) = 0 untuk bilangan bulat apa pun x. Monotonisitas adalah jaminan yang lebih kuat dari itu, tetapi saya tidak berpikir itu jauh lebih kuat sehingga tidak mungkin.
@ JoWreschnig Saya yakin Anda sadar bahwa fungsi noise Perlin terang-terangan melanggar beberapa kriteria Anda. Pertama melewati 0 pada node grid sehingga f (x + d) -f (x) adalah kelipatan konstan dari d untuk beberapa x (spasi tertentu) tertentu. Selain itu, karena trik caching yang cerdik, itu akan diulang untuk grid besar. Untuk noise klasik, saya pikir implementasi referensi seharusnya memiliki kotak petak (x, y) identik dengan petak (x + 256, y + 256). Anda harus menyatakan apakah ini dapat diterima, dan sejauh mana.
Biasa