Octree schreiben?

Hi,

gibt es irgendwo ein tut wie man einen Octree schreibt? Ich habe folgendes Problem: Ich hab mein Model geladen und ne Achsen Bounding Box drauf gelegt, nun für kollisionsabfragen ist das natürlich net besonderns drum will ich nen Octree verwenden. Aber kennt jemand dazu ein tut? weil mir fehlt echt die materie dazu

de_Bert

hi

versuch es doch mal mit der Suchfunktion oder in der FAQ.

DocJunioR

was fehlt denn da?
Ein Octree ist nichts weiter als ein dynamischer Baum. Ein Binärbaum funktioniert auch nicht anders, mal abgesehen davon, dass jedes Element nur 2 Kinder hat und nicht 8.

Du brauchst also eigentlich nur eine dynamische Speicherverwaltung für eine Strunktur, ähnlich dieser:

struct S_OcTreeData
{
  int           ObjectCount;
  S_ObjectData *Data;

  S_OcTreeData *LinksObenVorne
             , *RechtsObenVorne
             , *LinksUntenVorne
             , *RechtsUntenVorne
             , *LinksObenVorne
             , *RechtsObenVorne
             , *LinksUntenVorne
             , *RechtsUntenVorne

             , *VaterKnoten;

  S_MyVektor    BorderLinksObenVorne
             ,  BorderRechtsObenVorne
             ..

};

Wahlweise auch einfach

struct S_OcTreeData
{
  S_ObjectData *Data;
  S_OcTreeData *Kinder[8]
             , *Vater;
  S_MyVektor    Border[8]
};

Okay, die Strukturenansammlung ist nicht schön, aber dafür simpel gestrickt.

Wenn ein Objekt in der Position verändert wird, musst Du nur schauen, ob es noch innerhalb des aktuellen Knotens ist und es ansonsten an den Vaterknoten weiter reichen. Von diesem aus wird es entweder an den entsprechenden Kindknoten weiter gegeben oder noch eine Ebene nach oben verlagert.
Dies ist IMHO übrigens ein schönes Anwendungsgebiet für die Rekursion

cYa
DjR