Wie kann ich einen Blitz-Effekt erzeugen?

26

Gibt es einen Algorithmus zum Erzeugen eines Blitzes?

Ich hätte gerne einen Algorithmus, der eine Liste von Segment- oder Punktobjekten generiert, die angeben, wo der Bolzen landen wird. Die Methode würde einen Startpunktparameter zusammen mit einem Endpunkt benötigen. Der Bolzen sollte zufällige Abzweigungen haben und in zufälligen Abständen im Zickzack. Das Ergebnis ist ein zufälliger Blitzeffekt, der ungefähr so ​​aussehen würde


(Quelle: wikimedia.org )

Wenn jemand einen Algorithmus kennt, für den dies möglicherweise funktioniert, wäre er dankbar!

Geoffroi
quelle
2
Dieses Papier von Nvidia sollte genau das sein, was Sie brauchen, obwohl es möglicherweise etwas zu umfangreich ist. Schauen Sie sich die Folien 7 bis 11 an, sie haben einige nette Beispiele, die Ihnen eine Vorstellung davon geben sollen, worauf Sie abzielen sollen. Wenn Sie dem zweiten Link folgen, finden Sie den Quellcode (C ++, Direct3D). developer.download.nvidia.com/SDK/10/direct3d/Source/Lightning/… developer.download.nvidia.com/SDK/10/direct3d/samples.html
Fehler

Antworten:

32

Es gibt einen ziemlich einfachen Algorithmus, mit dem Sie Beleuchtungsbolzen generieren können.

Beginnen Sie mit einem Liniensegment zwischen dem Ursprung der Schraube ( O) und dem Endpunkt (E )

Wählen Sie einen Punkt auf dieser Linie (ungefähr oder genau in der Mitte), Sund teilen Sie das Segment in zwei Liniensegmente ( O->Sund S->E) auf. VerdrängenS Abstand zum ursprünglichen Liniensegment (entlang der Segmentnormalen) um einen kleinen zufälligen Betrag. Dies gibt Ihnen eine einzige "Biegung" des Blitzes.

Nachdem Sie die Biegung berechnet haben, möchten Sie, basierend auf einer kleinen zufälligen Chance, ein drittes Liniensegment hinzufügen (normalerweise eine Erweiterung des O->SSegments). So stellen Sie die "Gabeln" im Blitz her. Normalerweise möchten Sie während dieses Generierungsprozesses Informationen über die Intensität des Bolzens verfolgen, da die Gabeln dunkler sein oder eine subtilere Unschärfe aufweisen sollen:

Bildbeschreibung hier eingeben

Wiederholen Sie dann den obigen Vorgang für alle neuen Liniensegmente. Sie müssen einen Wiederholungsbetrag auswählen, der Formen erzeugt, die Ihnen gefallen:

Bildbeschreibung hier eingeben

Eine ziemlich klare Erklärung für diese Technik findet sich hier im Blog meines Freundes (hier habe ich die Bilder schamlos gestohlen). Es geht auch darum, den Glow-Effekt noch weiter zu vertiefen.

Schließlich gibt es auch dieses NVIDIA-Dokument, das denselben grundlegenden Algorithmus beschreibt (auch mit mehr Details).

Josh
quelle
13

Ich würde einen alternativen Ansatz empfehlen: den Rapid Exploring Random Tree (RRT) . Eine coole Sache dabei ist, dass Sie es dazu bringen können, um Ecken zu fahren oder in alle Richtungen zu explodieren.

Der Algorithmus ist wirklich grundlegend:

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

Durch Ändern der RandomSampleundExtendToward Funktionen können Sie sehr unterschiedliche Bäume erhalten. ObRandomSample überall nur gleichmäßige Proben entnommen werden, wächst der Baum gleichmäßig in alle Richtungen. Wenn der Baum auf das Ziel ausgerichtet ist, wächst er tendenziell auf das Ziel zu. Wenn das Ziel immer abgetastet wird, ist der Baum vom Start bis zum Ziel eine gerade Linie.

ExtendTowardSie können dem Baum auch interessante Dinge antun. Zum einen können Sie bei Hindernissen (wie Mauern) den Baum zum Wachsen bringen um sie einfach durch Erweiterungen , dass kollidieren mit Wänden Ablehnung.

So sieht es aus, wenn Sie die Stichprobe nicht auf das Ziel ausrichten:

img
(Quelle: uiuc.edu )

Und so sieht es mit Wänden aus

Einige coole Eigenschaften des RRT, sobald es fertig ist:

  • Das RRT wird sich niemals bekreuzen
  • Die RRT wird schließlich den gesamten Raum mit immer kleineren Zweigen abdecken
  • Der Weg vom Start zum Ziel kann völlig zufällig und seltsam sein.
mklingen
quelle
Ich habe gerade diesen Algorithmus verwendet, um eine Blitzanimation zu erzeugen. Ich muss sagen, es hat wirklich gut funktioniert! Der Code enthält einen großen Tippfehler, zum Beispiel, dass er nicht bei jeder Schleife inkrementiert wird.
Davon abgesehen