Comment puis-je générer un effet d'éclair?

26

Existe-t-il un algorithme pour générer un éclair?

Je voudrais un algorithme qui génère une liste d'objets segment ou point spécifiant où le boulon va atterrir. La méthode aurait besoin d'un paramètre de point de départ, ainsi que d'un point de terminaison. Le boulon doit avoir des branches aléatoires qui s'en détachent et zigzaguer à intervalles aléatoires. Le résultat sera un effet de foudre aléatoire qui ressemblerait un peu à ceci


(source: wikimedia.org )

Si quelqu'un connaît un algorithme pour lequel cela peut fonctionner, l'aide serait grandement appréciée!

Geoffroi
la source
2
Ce document de Nvidia devrait être exactement ce dont vous avez besoin, même s'il peut être un peu trop volumineux. Consultez les diapositives 7 à 11, elles ont de belles images qui devraient vous donner une idée de ce à quoi viser. Si vous suivez le deuxième lien, vous trouverez le code source (C ++, Direct3D). developer.download.nvidia.com/SDK/10/direct3d/Source/Lightning/… developer.download.nvidia.com/SDK/10/direct3d/samples.html
Erreur

Réponses:

32

Il existe un algorithme assez simple que vous pouvez utiliser pour générer des boulons d'éclairage.

Commencez par un segment de ligne entre l'origine du boulon ( O) et le point final ( E)

Choisissez un point sur cette ligne (approximativement ou exactement au milieu), appelé Set divisez le segment en deux segments de ligne ( O->Set S->E). Déplacer Sloin du segment de ligne initial ( le long de la normale du segment) par une petite quantité aléatoire. Cela vous donne un seul "virage" de la foudre.

Après avoir calculé le pli, en fonction d'une petite chance aléatoire, vous souhaiterez ajouter un troisième segment de ligne (généralement une extension du O->Ssegment). C'est ainsi que vous produisez les "fourches" dans la foudre. Vous voudrez généralement suivre les informations sur l'intensité du boulon pendant ce processus de génération, car vous voudrez que les fourches soient plus faibles ou aient un flou plus subtil:

entrez la description de l'image ici

Ensuite, répétez le processus ci-dessus pour tous les nouveaux segments de ligne que vous avez; vous devrez choisir une quantité de répétition qui produit des formes que vous aimez:

entrez la description de l'image ici

Il y a une explication assez claire de cette technique sur le blog de mon ami ici (c'est d'où j'ai volé sans vergogne les photos); cela va plus loin dans l'ajout de l'effet de lueur également.

Enfin, il y a aussi cet article NVIDIA qui décrit le même algorithme de base (également avec plus de détails).

Josh
la source
13

Je recommanderais une approche alternative: l'arbre aléatoire à exploration rapide (RRT) . Une chose intéressante à ce sujet est que vous pouvez le faire tourner dans les coins ou exploser dans toutes les directions.

L'algorithme est vraiment basique:

// 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;
}

En modifiant les fonctions RandomSampleet ExtendToward, vous pouvez obtenir des arbres très différents. Si RandomSamplejuste des échantillons uniformément partout, l'arbre se développera uniformément dans toutes les directions. S'il est biaisé vers l'objectif, l'arbre aura tendance à croître vers l'objectif. S'il échantillonne toujours le but, l'arbre sera une ligne droite du début au but.

ExtendTowardpeut également vous permettre de faire des choses intéressantes sur l'arbre. D'une part, si vous avez des obstacles (tels que des murs), vous pouvez faire pousser l'arbre autour d' eux simplement en rejetant les extensions qui entrent en collision avec les murs.

Voici à quoi cela ressemble lorsque vous ne biaisez pas l'échantillonnage vers l'objectif:

img
(source: uiuc.edu )

Et voici à quoi ça ressemble avec des murs

Quelques propriétés intéressantes du RRT une fois terminé:

  • Le RRT ne se franchira jamais
  • Le RRT couvrira finalement tout l'espace avec des branches de plus en plus petites
  • Le chemin du début au but peut être complètement aléatoire et étrange.
mklingen
la source
Je viens d'utiliser cet algorithme pour générer une animation éclair. Je dois dire que cela a très bien fonctionné! Il y a une faute de frappe majeure dans le code, comme iter qui n'est pas incrémenté à chaque boucle. À part cela, il est presque prêt à être utilisé tel que publié
applejacks01