Du bist nicht angemeldet.

Werbeanzeige

1

29.10.2012, 11:16

Quadtree und Fragen dazu

Hi,
habe da so eine Idee, dafür brauche ich eine schnelle! Kollisionserkennung für runde Partikel.

Ich habe jetzt einen Quadtree implementiert. Als Alternative gäbe es die Möglichkeit ein Gitter zu benutzen. Aber Quadtrees sind ja effizienter?


Nunja es klappt auch alles ganz gut. So sieht die Quadtree Klasse aus.
(Sorry der Quelltext zerschießt sich bzgl. Formatierung irgendwie immer.)

C#-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using System;using System.Collections.Generic;using System.Linq;using System.Text;
namespace QuadTree{    public class Node    {        public Node LT_Node;        public Node RT_Node;        public Node LB_Node;        public Node RB_Node;
        public IntVector2 MidPos;        public int Level;
        public Int16 Count;        public bool Full;        int[] Index = new int [Config.NodeParticleMaximum];
        public int Size;

        public void SetUp(int NewLevel, int NewMidX, int NewMidY)        {            Level = NewLevel;//welches Level hat der Node            MidPos.X = NewMidX;            MidPos.Y = NewMidY;
            Size = Config.QuadTreeSize / (int)Math.Pow(2, Level-1);            Full = false;//Ist er voll            Count = -1;//wieviele Partikel sind drinne, falls es nicht voll ist.        }

        public void AddParticle(int ParticleIndex, ParticleProvider ParticleProvider)        {            if (Full)//wenn schon voll in sub node                AddToSubNode(ParticleIndex, ParticleProvider);            else//Wenn nicht voll hier adden            {                Count++;                if (Count < Config.NodeParticleMaximum)                {                    Index[Count] = ParticleIndex;                }                else//Wenn es voll werden sollte:                {                    Full = true;//Voll Markieren                    CreateSubnodes();//neue unterknoten anlegen
                    for (int i = 0; i < Config.NodeParticleMaximum; i++)//Alte partzikel in die Subnodes                        AddToSubNode(Index[i], ParticleProvider);                    AddToSubNode(ParticleIndex, ParticleProvider);//und den neuen auch                }            }        }
        private void CreateSubnodes()        {
            LT_Node = new Node();            RT_Node = new Node();            LB_Node = new Node();            RB_Node = new Node();
            int QuaterSize = Size / 4;
            LT_Node.SetUp(Level + 1, MidPos.X - QuaterSize, MidPos.Y - QuaterSize);//Mittelposition fehlt noch!!!            RT_Node.SetUp(Level + 1, MidPos.X + QuaterSize, MidPos.Y - QuaterSize);            LB_Node.SetUp(Level + 1, MidPos.X - QuaterSize, MidPos.Y + QuaterSize);            RB_Node.SetUp(Level + 1, MidPos.X + QuaterSize, MidPos.Y + QuaterSize);        }
        private void AddToSubNode(int ParticleIndex, ParticleProvider ParticleProvider)        {            if (ParticleProvider.Particle[ParticleIndex].Position.X < MidPos.X)                if (ParticleProvider.Particle[ParticleIndex].Position.Y < MidPos.Y)                    LT_Node.AddParticle(ParticleIndex, ParticleProvider);                else                    LB_Node.AddParticle(ParticleIndex, ParticleProvider);            else                if (ParticleProvider.Particle[ParticleIndex].Position.Y < MidPos.Y)                    RT_Node.AddParticle(ParticleIndex, ParticleProvider);                else                    RB_Node.AddParticle(ParticleIndex, ParticleProvider);        }
    }}



Es gibt eine Sache die ist ein totales Rätsel!

WIE FINDET MAN DIE QUADS DIE NEBEN DEM GERADE FOKUSSIERTEN QUAD BEFINDEN?
Ich will alle Quads durchgehen und Kollisionen im eigenen Quad und den neben liegenden prüfen.


Eine weitere Frage die sich Stellt ist, wie, mit der Positionsveränderung von Partikeln unzugehen ist. Muss ich für jeden Frame den Quadtree komplett neu aufbauen?
Oder prüfe ich "nur" ob Quads verlassen wurden und restrukturiere die Datenstruktur dann erneut?

Danke im schonmal!

EDIT:
Ich mach euch ein Bild, obwohl ihr ja alle wisst worum es geht


LG
Bilder zu meinem Projekt: ParSim

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Horus« (29.10.2012, 12:32)


Schorsch

Supermoderator

Beiträge: 5 206

Wohnort: Wickede

Beruf: Student

  • Private Nachricht senden

2

29.10.2012, 14:13

Benachbarte Quads könntest du mit abspeichern. Andererseits könntest du natürlich auch die Ebenen nach oben und dann wieder nach unten durchlaufen. Im Prinzip stellt sich aber die Frage ob ein Quadtree die richtige Datenstruktur ist. Je nachdem was für Funktionalitäten du benötigst. An sich ist ein Quadtree eine Datenstruktur, welche deinen Code schneller machen kann, aber nicht muss. Du hast halt den Vorteil, dass große Blöcke zusammen gefasst werden und du kleine Strukturen über einen Baum darstellst. Je nach Anforderung tut es oft aber auch ein einfaches Raster.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

3

29.10.2012, 15:33

WIE FINDET MAN DIE QUADS DIE NEBEN DEM GERADE FOKUSSIERTEN QUAD BEFINDEN?
Ich will alle Quads durchgehen und Kollisionen im eigenen Quad und den neben liegenden prüfen.


Die benachbarten Nodes, auf der gleichen Ebene, sind immer die 0-3 übrigen Kinder des Parentnodes.


Eine weitere Frage die sich Stellt ist, wie, mit der Positionsveränderung von Partikeln unzugehen ist. Muss ich für jeden Frame den Quadtree komplett neu aufbauen?
Oder prüfe ich "nur" ob Quads verlassen wurden und restrukturiere die Datenstruktur dann erneut?


Du kannst beides machen und beides ist nicht unbedingt die beste Lösung. Ein Quadtree ist super geeignet für statische Daten, so dass der Baum nicht aktualisiert werden muss. Bei total dynamischen Fuzzydingern, wie Partikelsystemen, kannst du den Performanzgewinn mit einem neuen Aufbauen des Baums ggf wieder verlieren.
@D13_Dreinig

4

29.10.2012, 18:38

Danke für die Antworten!

Zitat

Die benachbarten Nodes, auf der gleichen Ebene, sind immer die 0-3 übrigen Kinder des Parentnodes.
Ja das ist nicht so schwer. :D Aber die Anderen!?! und wie ist es bei weiterer Unterteilung der Partnernodes?


Ich glaube ich muss die Nodes komplett von Oben nach unten durchlaufen, dabei werden natürlich alle Nodes aussortiert, die nicht an den Ausgewählten Nodes grenzen. So bleiben dann die angrenzenden übrig. Diese Methode ist mega aufwändig. Da werden ja haufenweise Koordinaten verglichen


Ob es sinnvoll ist die Pfade zu den angrenzenden Nodes zu speichern? Sähe dann so aus Beispiel: 32413241 oder?
(Ich habe bei z.B. 32.000 Partikeln mindestens 7 Ebnen)
Wenn ich die Struktur nicht jedes mal neu aufbaue klingt das gut.


Welche Methode ist denn für eine Partikelsystem mit runden Partikeln am besten? Also konkret. Partikel müssen auch zugefügt oder entfernt werden.

Noch eine Frage.
Momentan habe ich eine Partikelliste, also einen Array, für alle Partikel. In dem Quadtree sind nur die Indizes der Partikel in der Liste abgespeichert.
Sollte ich es weiterhin so machen oder die Partikel direkt in den Nodes unterbringen, und keine weitere Liste verwenden?

LG
Bilder zu meinem Projekt: ParSim

dot

Supermoderator

Beiträge: 9 833

Wohnort: Graz

  • Private Nachricht senden

5

29.10.2012, 21:12

Als Alternative gäbe es die Möglichkeit ein Gitter zu benutzen. Aber Quadtrees sind ja effizienter?

Ist das so? Das ist mir neu...


WIE FINDET MAN DIE QUADS DIE NEBEN DEM GERADE FOKUSSIERTEN QUAD BEFINDEN?
Ich will alle Quads durchgehen und Kollisionen im eigenen Quad und den neben liegenden prüfen.

Das ist in der Tat ein Problem. Wofür genau brauchst du die benachbarten Quads? Du könntest natürlich z.B. in jedem Node Pointer auf seine Nachbarn speichern...


Eine weitere Frage die sich Stellt ist, wie, mit der Positionsveränderung von Partikeln unzugehen ist. Muss ich für jeden Frame den Quadtree komplett neu aufbauen?
Oder prüfe ich "nur" ob Quads verlassen wurden und restrukturiere die Datenstruktur dann erneut?

Ja, das ist eines der ganz fundamentalen Probleme bei solchen Datenstrukturen. Wenn sich was ändert, wirst den Baum neu bauen oder zumindest irgendwie updaten müssen, was natürlich nicht unbedingt trivial ist...


Ich würde jetzt mal postulieren, dass ein Grid in deinem Fall wesentlich besser geeignet wäre. Oder kann es passieren, dass sich tausende Partikel am selben Fleck aufhalten? Da es ja um Kollision geht wohl eher nicht. Ein Grid mit einer Zellengröße von ein paar Partikeln wäre dem Quadtree in Sachen Effizienz hier vermutlich bei weitem überlegen...

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »dot« (29.10.2012, 21:17)


6

29.10.2012, 22:09

Also Lohnt ein Quadtree erst wenn die Partikel sehr ungleich verteilt sind. Das leuchtet ein :D

Bis die ganzen Funktionen geschrieben sind, oh nein!

Zitat

Das ist in der Tat ein Problem. Wofür genau brauchst du die benachbarten Quads? Du könntest natürlich z.B. in jedem Node Pointer auf seine Nachbarn speichern...
Ja aber wenn sich die Partikel bewegen, dann ändern sich die Quads man müsste über die Pointer auf die umliegenden Quads zugreifen und dort die Pointer updqaten. :D das wird mir zu bunt...


Ich habe eine neue Idee.

Eine Art Hybrid aus Gitter und Quadtree. Gibt es das schon? ist das neu? Ist das Unsinn?


Ich lege Vier(Oder so) Gitter übereinander. Jedes Gitter hat die doppelte Sektorengröße wie das vorherige Gitter. Sie Ähneln somit einem Qadtree. Jedoch ist das Großte Gitter nicht zwangsläufig so groß wie die gesamte "Welt"


Die Partikel werden dann in alle 4 Gitter eingefügt.
Ich gehe jetzt das Gitter durch, wenn die großen Sektoren zu voll sind die Nächstkleineren usw.
Umliegende Sektoren kann ich über die Indices erreichen, Die Sektoren bestehen aus einem 2D Array.

Oder doch lieber nur ein "Einfaches" Gitter..?

LG
Bilder zu meinem Projekt: ParSim

dot

Supermoderator

Beiträge: 9 833

Wohnort: Graz

  • Private Nachricht senden

7

29.10.2012, 23:01

Ich habe eine neue Idee.

Eine Art Hybrid aus Gitter und Quadtree. Gibt es das schon? ist das neu? Ist das Unsinn?

Ja, das klingt unter Umständen sinnvoll. Ich würde mal davon ausgehen, dass es das schon gibt. Wobei ich mir überlegen würde, inwiefern das im konkreten Fall wirklich nötig ist...

Evrey

Treue Seele

Beiträge: 246

Beruf: Weltherrscher

  • Private Nachricht senden

8

29.10.2012, 23:07

Nun, genau das ist eigentlich die Idee der Quad- und Octrees. Eine ähnliche Technik findet man auch bei Navigationsgraphen, wo man quasi wichtige Punkte des feinen Netzes mit einem wesentlich gröberem "Schnellwahl-Netz" verbindet, um laaaaaaaaaaaange Pfade schneller errechnen zu können. Deine Lösung klingt wie 'ne Kreuzung aus beidem, sollte ergo in die richtige Richtung gehen. Wird bloß viel Verwaltungskrams, die eigene Position in mehreren Gittern festzulegen.

C-/C++-Quelltext

1
2
3
4
int main(int _argc, char** _argv) noexcept {
  asm volatile("lock cmpxchg8b %eax");
  return 0;
} // ::main
(Dieses kleine Biest vermochte einst x86-Prozessoren lahm zu legen.)

=> Und er blogt unter Hackish.Codes D:

9

29.10.2012, 23:55

Also ich habe getestet:

32K Partikel in einen Quadtree zu bringen dauert ~15ms

32K Partikel in ein Grid zu bringen dauert ~7ms bei vergleichbarer Rasterung




Bei der Iteration sind beide etwa gleichauf!

Hätte nie gedacht dass die Ganzen bool Entscheidungen in einem 7 Ebnen besitzenden Quadtree genau so schnell duchlaufen werden wie ein Grid, also ein Array mit vergleichbar vielen Sektoren. 8|

Ob sich ein Test mit mehreren Gittern überhaupt lohnt?


Die Tests lassen den Quadtree schneller aussehen als erwartet.
Gibt es nicht irgend einen "Trick" oder so die angrenzenden Sektoren direkt anzusprechen?



LG
Bilder zu meinem Projekt: ParSim

BlueCobold

Community-Fossil

Beiträge: 10 859

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

10

30.10.2012, 06:42

Klar gibt es so einen Trick: Nimm von Anfang an ein regelmäßiges Grid aus kleinen Sektoren und kein verschachteltes. Ich bin mir nämlich noch immer nicht sicher, dass eine verschachtelte Struktur überhaupt Deinem Zweck dienlich ist. Vielleicht solltest Du uns nochmal genau beschreiben WARUM Du sie überhaupt in so eine Struktur einordnen willst. Um was für eine Kollision geht es hier? Alle Partikel kollidieren mit den jeweils anderen? Wenn ja, dann brauchst Du hier ganz eindeutig keine verschachtelte Struktur, ein kleines Grid reicht da völlig. ("klein" heißt, dass nur wenige Partikel in das selbe Feld passen)
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Werbeanzeige