Quadtree

Manuel

Hi,
ich möchte im mein Terrain ein Quad-tree-culling implementieren. Der Tree hat folgende Struktur :

typedef struct TERRAIN_TREE_TYPE
{
    UINT id;
    AOBB bounding_box;

    UINT terrain_page_id;

    DWORD creation_value;

    struct TERRAIN_TREE_TYPE    *parent;    //Übergeordneter Zweig
    struct TERRAIN_TREE_TYPE    *child[4];  //Untergeordnete Zweige
} TERRAIN_TREE;

Wie fülle ich die Struktur nun aber mit den Daten?

Ich hab eine feste Terraingröße aus X*X Terrain-Pages. Jeder unterste Ast im Quadtree soll eine Page beinhalten. Wie durchlaufe ich den Baum nun aber am schnellsten?
->Ich hab bis jetzt in der 'creation_value' eine Zahl eingeschrieben, die die Unter-Ast-Zahl und den aktuellen Ast (1-4) speichert (MAKELONG rulez ). Der Baum sollte nun so durchlaufen werden, dass die 'aktueller Ast' Zahl immer um 1 erhöht wird und sobald sie 4 ist, er zurück in den 'Parent-Ast' springt.
Ist diese Methode gut?

Danke für die Hilfe (hoffentlich )

M.T.

Headhunter

Was ist eine Page für dich ? Ich habe diesen Begriff noch nicht im Zusammenhang mit Bäumen gelesen.

Und was hast du mit der Variable creation_value genau vor , ich bin durch deine Beschreibung nämlich nicht ganz durchgestiegen..

Die schnellste Durchlaufmöglichkeit ist wahrscheinlich Rekrusion.

Manuel

@Headhunter: Bei der Page handelt es sich um einen kleinen Teil des Terrains (5x5 Einheiten), das ist die kleinste clipp-bare Einheit in meinem Terrain, weil ich denke, dass Per-Poly-Culling auf heutigen Grafikkarten langsamer ist.
Die creation_value ist eine per MAKELONG erstellte Zahl aus dem Aktuellen Ast (NW | NO | SW | SO), der so durchlaufen wird, dass wenn er an den Ast kommt, der Weg gegangen wird, der in der Zahl steht und der Wert erhöht wird, sodass beim nächsten Durchgang der nächste Zweig durchlaufen wird. Der zweite Teil von creation_value ist die Tiefe der Zweiges (root=0 / erster Unterast=1 / u.s.w).
Ich wollte eben wissen, ob diese Methode gut ist und was ihr benutzt

@Florianx: Werds mal per Rekursion versuchen, danke

M.T.

rapso

rekursive wäre wohl wirklich die beste methode, dabei kannst du für jedes quad testen ob
es nicht zu sehen ist, ganz zu sehen ist oder teilweise zu sehen ist
abhängig davon kannst du dann die rekursion weiter führen.

rapso->greets();

TGGC

Wie man am schnellsten durchläuft hängt davon ab, welches Nodes du "besuchst". Am schwerwiegensten ist nämlich, das die Nodes normalerweise im Speicher wirr verteilt sind (weil jeder einzeln allokiert wird) und so bei einem rekursiven Durchlauf ständig im Speicher hin und hergesprungen wird.

Manuel

Ich hab aber jeden Node einzeln allokalisiert , weil ich vorher nicht weiß, wie groß das Terrain wird - hab jetzt aber ne Methode gefunden, mit der ich die Sache schnell erledigen kann.

M.T.

normalerweise macht man bei sowas einen memorypool, pools von 4kb sind optimal, und anstatt immer new aufzurufen, hollst du dir ein freies stück vom pool und machst dort ein inplacement new, dadurch bekommst du kompackte blöcke die schneller sind, als wild im speicher rumliegende stücke, ich stimme TGGGC zu, dass das wohl am meißten performance frisst.

rapso->greets();

TGGC

Original erstellt von <rapso>:
**normalerweise macht man bei sowas einen memorypool, pools von 4kb sind optimal, und anstatt immer new aufzurufen, hollst du dir ein freies stück vom pool und machst dort ein inplacement new, dadurch bekommst du kompackte blöcke die schneller sind, als wild im speicher rumliegende stücke, ich stimme TGGGC zu, dass das wohl am meißten performance frisst.

rapso->greets();**

Noch "optimaler" ist's wenn man es wirklich auf die Nodes seines Quadtree ausrichtet. Normalerweise steht dessen Grösse ja durch eine maximale Tiefe fest.

rapso

@TGGGC
wie genau meinst du das mit "genau ausrichten",
ein memorypool von je 4kb müßte doch schon optimal sein,weil es sowohl das memorymanagement von windows nutzt als auch den cpu cache mit 32byte pagegrenzen.

also ich wüßte gerne was dabei noch optimaler ist, wenn man von vorne herein ausreichend platz reserviert.... *keineneinfallhat,vielleichtschlechtentag;)*

rapso->greets();