Bagaimana saya bisa menghasilkan efek petir?

26

Apakah ada algoritma untuk menghasilkan petir?

Saya ingin algoritma yang menghasilkan daftar objek segmen atau titik yang menentukan di mana baut akan mendarat. Metode ini membutuhkan parameter titik awal, bersama dengan titik akhir. Baut harus memiliki cabang acak yang keluar darinya, dan zig-zag pada interval acak. Hasilnya akan menjadi efek kilat acak yang akan terlihat seperti ini


(sumber: wikimedia.org )

Jika ada yang tahu tentang algoritma yang dapat bekerja untuk ini, bantuan akan sangat dihargai!

Geoffroi
sumber
2
Makalah ini oleh Nvidia seharusnya hanya apa yang Anda butuhkan, meskipun mungkin agak terlalu luas. Periksa slide 7 hingga 11, mereka memiliki beberapa imadges bagus yang harus memberi Anda ide tentang apa yang harus dituju. Jika Anda mengikuti tautan kedua, Anda akan menemukan kode sumber (C ++, Direct3D). developer.download.nvidia.com/SDK/10/direct3d/Source/Lightning/… developer.download.nvidia.com/SDK/10/direct3d/samples.html
Fault

Jawaban:

32

Ada algoritma yang cukup sederhana yang dapat Anda gunakan untuk menghasilkan baut pencahayaan.

Mulai dengan segmen garis antara asal baut ( O) dan titik akhir ( E)

Pilih satu titik pada garis itu (kira-kira atau tepatnya di tengah), panggil Sdan bagi segmen menjadi dua segmen garis ( O->Sdan S->E). Mengusir Sdari segmen garis asli (sepanjang normal segmen) dengan sedikit jumlah acak. Ini memberi Anda satu "tikungan" petir.

Setelah menghitung tikungan, berdasarkan peluang acak kecil, Anda ingin menambahkan segmen garis ketiga (biasanya ekstensi O->Ssegmen). Ini adalah bagaimana Anda menghasilkan "garpu" di petir. Anda biasanya ingin melacak informasi tentang intensitas baut selama proses pembuatan ini, karena Anda ingin garpu menjadi lebih redup atau memiliki kekaburan yang lebih halus:

masukkan deskripsi gambar di sini

Lalu, ulangi proses di atas untuk semua segmen baris baru yang Anda miliki; Anda harus memilih jumlah pengulangan yang menghasilkan bentuk yang Anda sukai:

masukkan deskripsi gambar di sini

Ada penjelasan yang cukup jelas tentang teknik ini di blog teman saya di sini (di situlah saya tanpa malu mencuri gambar dari); itu masuk ke kedalaman tambahan tentang menambahkan efek cahaya juga.

Akhirnya, ada juga makalah NVIDIA ini yang menggambarkan algoritma dasar yang sama (juga dengan lebih detail).

Josh
sumber
13

Saya akan merekomendasikan pendekatan alternatif: pohon acak mengeksplorasi cepat (RRT) . Satu hal yang keren tentang itu adalah Anda bisa membuatnya berputar-putar, atau meledak ke segala arah.

Algoritma ini sangat mendasar:

// Returns a random tree containing the start and the goal.
// Grows the tree for a maximum number of iterations.
Tree RRT(Node start, Node goal, int maxIters)
{
    // Initialize a tree with a root as the start node.
    Tree t = new Tree();
    t.Root = start;


    bool reachedGoal = false;
    int iter = 0;

    // Keep growing the tree until it contains the goal and we've
    // grown for the required number of iterations.
    while (!reachedGoal || iter < maxIters)
    {
         // Get a random node somewhere near the goal
         Node random = RandomSample(goal);
         // Get the closest node in the tree to the sample.
         Node closest = t.GetClosestNode(random);
         // Create a new node between the closest node and the sample.
         Node extension = ExtendToward(closest, random);
         // If we managed to create a new node, add it to the tree.
         if (extension)
         {
             closest.AddChild(extension);

             // If we haven't yet reached the goal, and the new node
             // is very near the goal, add the goal to the tree.
             if(!reachedGoal && extension.IsNear(goal))
             {
                extension.AddChild(goal);
                reachedGoal = true;
             }
         }
         iter++;
    }
    return t;
}

Dengan memodifikasi RandomSampledan ExtendTowardfungsinya, Anda bisa mendapatkan pohon yang sangat berbeda. Jika RandomSamplehanya sampel seragam di mana-mana, pohon akan tumbuh seragam di semua arah. Jika bias terhadap tujuan, pohon akan cenderung tumbuh ke arah tujuan. Jika selalu sampel tujuan, pohon akan menjadi garis lurus dari awal hingga tujuan.

ExtendTowarddapat memungkinkan Anda untuk melakukan hal-hal menarik ke pohon juga. Untuk satu hal, jika Anda memiliki hambatan (seperti dinding), Anda bisa membuat pohon tumbuh di sekitar mereka hanya dengan menolak ekstensi yang bertabrakan dengan dinding.

Ini terlihat seperti ketika Anda tidak bias mengambil sampel ke arah tujuan:

img
(sumber: uiuc.edu )

Dan inilah yang terlihat seperti dengan dinding

Beberapa properti keren RRT setelah selesai:

  • RRT tidak akan pernah menyeberang dengan sendirinya
  • RRT pada akhirnya akan mencakup seluruh ruang dengan cabang yang lebih kecil dan lebih kecil
  • Jalur dari awal hingga tujuan bisa sepenuhnya acak dan aneh.
mklingen
sumber
Saya hanya menggunakan algoritma ini untuk menghasilkan animasi baut petir. Saya harus mengatakan itu bekerja dengan sangat baik! Ada kesalahan ketik utama dalam kode, seperti iter tidak bertambah setiap loop. Selain itu, ini hampir siap untuk digunakan sebagai diposting
applejacks01