OcTree - Stack Overflow

[daemon777]

Hallo Leute,
ich hab mal wieder ein Problem auch wenn es dieses Mal ausnahmsweise mal etwas interessanter ist ^^

Eigentlich geht es bei der Frage eher um das Prinzip als um eine genaue Programmiersprache weshalb ich für den Thread kein Präfix gewählt habe. Programmieren tue ich aber mit C++.

Und jetzt zum Problem: ich teste im Moment ein bisschen mit 3D-Graphik und da ist es hilfreich sich die Polygone in einer Baumstruktur zu speichern. Jetzt habe ich aber das Problem, dass ein Baum nunmal eine rekursive Datenstruktur ist und wenn diese zu groß wird so sprengt sie den Stack.

Mein Beispiel sollte zum Beispiel mit 30.000 Polygonen rechnen (was ja in einem Graphikprogramm nicht wirklich viel ist) und scheitert daran hoffnungslos. Das Problem liegt wohl wirklich daran, dass ich beim erstellen eines Knotens direkt die Children miterstelle und somit über 1 Millionen Knoten gleichzeitig auf dem Stack landen.

Wie könnte ich das Ganze denn jetzt beheben? Das Heraufsetzen der Stackgröße wäre natürlich eine Idee wobei die Größe gigantisch sein müsste. Das Heruntersetzen der Rekursionstiefe wäre eine Andere. Aber hier müsste ich eben die Tiefe sehr stark begrenzen.

Habt ihr vielleicht noch andere Ideen? Sollte ich vielleicht sogar hingehen und den Baum irgendwie ganz anders aufbauen? Im Moment bin ich ehrlich gesagt etwas ratlos.

 

[BsOne]

Moin,

du musst beim erstellen eines Knotens im Baum doch nicht die Childs mit erstellen, da reicht ein Pointer auf "null" und das wars und beim einsetzen setzt du dann den pointer auf das neue element

http://cslibrary.stanford.edu/110/BinaryTrees.html

 

[daemon777]

Ah jetzt bin ich dank deines Posts auf die Ursache meines Problems gestoßen und bin zum Schluss gekommen, dass meine Probleme eher vorrübergehender Natur sind und daran liegen, dass ich die Daten noch in keiner vernünftigen Form vorliegen habe. So wie ich es im Moment mache wäre es etwas schwer die Children erst hinterher zu berechnen. Das liegt aber nicht am Baum selbst sondern an der restlichen Struktur.

Danke für deine Antwort. Damit hast du mich vom Schlauch geschupst auf dem ich grade stand

EDIT: Lustigerweise kommen mir jetzt auch die Ideen und Notizen, die ich mir vorher dazu gemacht habe, auch wieder sinnvoll vor. Wenn man so ein Projekt zu lange aufschiebt vergisst man eben leider doch ein paar Details xD

 

[BsOne]

Jo kommt mal vor na dann noch viel spaß beim coden

 

[daemon777]

Also irgendwie schein ich was mit meinem Hirn angestellt zu haben was ihm nicht gut tat ^^

Auch wenn der Baum an sich noch große Fehler zu haben scheint (seltsam weil ich spontan mal ein kleines Testprogramm mit Binär und QuadTree schreiben konnte wo beide Bäume funktioniert haben ^^) habe ich das Gefühl, dass das eigentliche Problem ganz wo anders liegt.

Im Moment erstelle ich einfach mal nur die Wurzel und das Problem tritt dennoch genauso auf. Bleibt die Wurzel jedoch ein Null-Pointer habe ich das Problem nicht.

Da das Problem genau an der Stelle abstürzt wo ich versuche meine Datenstruktur einem Vektor hinzuzufügen habe ich so langsam das Gefühl, dass ich einem Vektor nicht so ohne Weiteres eine Datenstruktur mit variabler Größe übergeben kann. Interessant ist auch, dass die erste Zuweisung zum Vektor funktioniert, bei der Zweiten stürzt aber dann das Programm ab.

Meine Struktur sieht folgendermaßen aus:
- Es gibt einen Chunk-Datentyp welcher eine gewisse Anzahl an Geometrie verwaltet
- Diese Chunk-Datei hat einen OcTree um effizient die Geometrie verwalten zu können
- Es gibt eine Überstruktur welche in einem Vektor (std::vector<Chunk>) die einzelnen Chunks speichern soll

Wie gesagt kann ich dem vector<Chunk> chunks per chunks.push_back(chunk0) noch das erste Element zufügen aber bei chunks.push_back(chunk1) wirds dann problematisch und das Programm stürzt ab. Das trifft aber eben nur auf wenn der Pointer zur Wurzel des OcTrees von NULL verschieden ist.

Puh ich hoffe ich habe das jetzt einigermaßen vernünftig formuliert ^^

Ich hoffe ihr könnt mir da mal wieder weiterhelfen. Muss ich jetzt die Verwaltung der Daten nochmal komplett überdenken weil das mit einem vektor nicht so geht wie ich das vorhatte? Oder woran könnte es sonst liegen?