Gute Beschleunigungsstruktur für Kugelstrahlversuche mit Kugeln, die sich bewegen

Question

Ich bin auf der Suche nach der richtigen Beschleunigungsstruktur für Strahl-Kugel-Schnitttests (in einem Spiel). gelten die folgenden Bedingungen:

-sind arround 100 Kugeln und 100 Strahlen gegeneinander pro Rahmen zu testen

-die Kugeln in jedem Rahmen bewegen, so tun die Strahlen

-e Strahlen sein können/Kugeln hinzugefügt/in jedem Rahmen entfernt (aber die meisten von ihnen die gleiche zwischen zwei Rahmen, nur leicht bewegt werden)

-ganz Sache ist in 3D

ein KD-Baum ist sehr gut für Ray Kreuzung Tests, aber seit den Kugeln bewegen, würde ich den KD-Baum in jedem Rahmen neu aufbauen müssen, was teuer ist

ein Oct-Baum ist einfacher zu pflegen, aber sehr unwirksam für Ray-Kreuzung Tests.

100 Strahlen gegen 100 Sphären scheinen nicht viel zu sein, aber ich bin Codierung sehr geringe Ressourcen auf, so dass ich mich für einige Beschleunigung für den

Wer auf der Suche kann mir auf, dass ein paar Hinweise geben?

Answer 1

100x100 = 10k, eine optimierte Brute-Force scheint nicht inkohärent zu sein, vor allem, dass der Ray/Sphere-Schnitt nur Add/Multiply beinhaltet. Sie können alle normalisierten Strahlvektoren vor der Hauptschleife immer vorberechnen.

Wenn Sie die Annahme machen, dass Sie in einem begrenzten Universum leben und die räumliche Dichte von Sphären und Strahlen relativ gleichmäßig ist, könnten Sie ein festes räumliches Gitter (fixed oct-tree) verwenden - etwas wie ein 16x16x16 Zellengitter, oder more-- und:

• Precompute für jede Kugel schneidende Zellen (leicht zu berechnen, betreffen nur wenige Additionen und Vergleiche), Speichern in jeder Zelle, die Liste der einander schneidenden Kugeln,
• für jeden Strahl, in eine Schleife:
  • berechnen Sie die Liste der Zellen die ra y Kreuze (eine Methode basierend auf einem Bresenham-Algorithmus könnte den Trick tun)
  • machen Sie den Schnitttest für alle Kugeln in dieser Zellliste.

diese Weise können Sie in jedem Baum jeden Strahl nicht speichern müssen, nur Sphären. Die Effizienz dieser Methode hängt vom Verhältnis Zellgröße/Kugelgröße ab. Wenn Sie nicht zu viel Dispersion auf die Kugelgröße haben, kann dies ein guter Hinweis sein.

Wenn Sphären einander nicht und Kugelgröße überqueren ein Minimum haben, können Sie auch die Kugel-Liste in der Zellenliste gebunden (entsprechende Nummer wird dem Leser als exercice links ...)

HTH