DGL • Thema anzeigen - Octree Subbäume

Octree Subbäume

Moderator: DGL-Team

Seite 1 von 1

[ 9 Beiträge ]

Vorheriges Thema | Nächstes Thema

Autor

Nachricht

Seth

Betreff des Beitrags: Octree Subbäume

Verfasst: So Dez 12, 2010 20:04

DGL Member

Registriert: Di Mai 24, 2005 16:43
Beiträge: 710

Hallo,

nach langer Zeit beschäftige ich mich nun endlich mal wieder mit 3D Grafik/Programmierung und stoße sofort auf mein erstes Problem: Octrees :mrgreen:

Meine Implementierung läuft so ab, dass ich Zunächst alle Objekte (Daten) in die Wurzel speichere. Überschreiten diese eine gewisse Anzahl, so wird die Wurzel in 8 Teilbäume geteilt. Nun wird anhand von Bounding Boxes (Knoten VS Objekt) ermittelt, welches Objekt in welchen Teilbaum wandert. Ist hier wieder das Maximum überschritten, passiert das rekursiv so lange, bis alle Objekte ihren Platz gefunden haben. Ich glaube allerdigns nicht, dass das eine sonderlich schnelle Methode ist, einen Octree aufzubauen... :lol:

Das Problem ist nun, dass die Anzahl der Kollisionen, die ich mit meinem Octree finde, nicht mit der tatsächlichen Anzahl an Kollisionen übereinstimmt. Zuerst waren es weniger, jetzt sind es mehr.

Die BoundingBoxes der Subbäume berechne ich wie folgt (sry leider Java):

Zunächst habe ich ein Array, in das ich alle 8 Richtungen speichere:

Code:

   final static private Vector3d[] directions = {
         new Vector3d(-1, 1, -1),
         new Vector3d(-1, -1, -1),
         new Vector3d(1, -1, -1),
         new Vector3d(1, 1, -1),
         new Vector3d(-1, 1, 1),
         new Vector3d(-1, -1, 1),
         new Vector3d(1, -1, 1),
         new Vector3d(1, 1, 1)};
   static private Vector3d size;

Die Variable size speichert die Größe des Octrees und wird so berechnet:

Code:

      boundings = new BoundingBox(minimum, maximum);
      size = Vector3d.subtract(boundings.getMaximum(), boundings.getMinimum());

Und so bestimme ich die BoundingBoxes der Subbäume (ich denke hier liegt der Fehler):

Code:

   private BoundingBox subTreeBounding(int index) {
      if ((index < 0) || (index >= 8)) {
         return null;
      }
      Vector3d a = Vector3d.add(boundings.getCenter(), Vector3d.multiply(directions[index], size.scale(0.5).abs()));
      Vector3d min;
      Vector3d max;
      if (Vector3d.lessThan(a, boundings.getCenter())) {
         min = a;
         max = boundings.getCenter();
      } else {
         min = boundings.getCenter();
         max = a;
      }
      return new BoundingBox(min, max);
   }

.abs() liefert den Vektor zurück, bei dem alle Komponenten positiv sind, also {|x|, |y|, |z|} und bei multiply handelt es sich um eine Komponentenweise Multiplikation. lessThan ist true, wenn alle Komponenten des ersten Vektors kleiner sind, als die des zweiten.

Oder ist mein Ansatz grundlegend falsch?

Nach oben

Coolcat

Betreff des Beitrags: Re: Octree Subbäume

Verfasst: So Dez 12, 2010 20:41

DGL Member

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java

Hast du bedacht das ggf. einige Objekte innerhalb mehrerer BoundingBoxen sein könnten?

_________________
Yeah! :mrgreen:

Nach oben

Seth

Betreff des Beitrags: Re: Octree Subbäume

Verfasst: So Dez 12, 2010 21:59

DGL Member

Registriert: Di Mai 24, 2005 16:43
Beiträge: 710

Ja, das passiert an dieser Stelle:

Konstruktor für die Subbäume:

Code:

   public Octree(Octree parent, BoundingBox b) {
      this.parent = parent;
      this.boundings = b;
      isLeaf = true;
      size = Vector3d.subtract(boundings.getMaximum(), boundings.getMinimum());
      objects = new ArrayList<WorldObject>();
      for (WorldObject wo : parent.objects) {
         if (boundings.intersect(wo.getBoundingBox())) {
            objects.add(wo);
         }
      }

      divide();
   }

Methode zum Zerlegen des Octrees:

Code:

   private void divide() {
      if (objects.size() > limit) {
         isLeaf = false;
         for (int i = 0; i < 8; i++) {
            subTrees[i] = new Octree(this, subTreeBounding(i));
         }

         // TEST (ob alle Objekte ihren Platz gefunden haben)
         ArrayList<WorldObject> objs = new ArrayList<WorldObject>();
         for (int i = 0; i < 8; i++) {
            for (WorldObject wo : subTrees[i].objects) {
               if (!objs.contains(wo)) {
                  objs.add(wo);
               }
            }
         }
         if (objs.size() == objects.size()) {
            System.out.println("Korrekt");              // Das hier wird leider nie aufgerufen... :(
         } else {
            System.out.println(objs.size() + " sollte eigentlich " + objects.size() + " sein...");
         }
         // TEST ENDE 
         
         objects.clear(); // erst löschen, wenn alle Subbäume durch sind
      }
   }

Nach oben

Coolcat

Betreff des Beitrags: Re: Octree Subbäume

Verfasst: Mo Dez 13, 2010 10:06

DGL Member

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java

Also du hast mehr Objekte in objs als in objects, richtig? Wenn das der Fall ist liegt der Fehler nicht bei den BoundingBoxen, sondern wo anders. Dann selbst wenn die intersect-Methode immer true oder immer false zurück gibt bekommst du nicht mehr Objekte als vorher!

Bist du sicher das objs.contains(wo) wie erwartet funktioniert? Vielleicht ein Fehler beim überschreiben der equals-Methode?

_________________
Yeah! :mrgreen:

Nach oben

Seth

Betreff des Beitrags: Re: Octree Subbäume

Verfasst: Mo Dez 13, 2010 12:39

DGL Member

Registriert: Di Mai 24, 2005 16:43
Beiträge: 710

Ich bekomme weniger:

Zitat:

39 sollte eigentlich 62 sein...
42 sollte eigentlich 100 sein...

Die equals()-Methode ist nicht überschrieben, weil ich in diesem Fall wirklich nur true bekommen möchte, wenn es sich um das selbe Objekt handelt.

Nach oben

Coolcat

Betreff des Beitrags: Re: Octree Subbäume

Verfasst: Mo Dez 13, 2010 12:54

DGL Member

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java

Zitat:

Ich bekomme weniger:

Warum schreibst du dann oben das du mehr bekommst?

In dem Fall glaube ich das hier der Hase begraben liegt:

Code:

if (Vector3d.lessThan(a, boundings.getCenter())) {
         min = a;
         max = boundings.getCenter();
      } else {
         min = boundings.getCenter();
         max = a;
      }

Du musst das komponentenweise machen, sonst bekommst du keine valide BoundingBox heraus. ALso irgendwie so:

Code:

min.x = min(a.x, center.x)
max.x = max(a.x, center.x)
min.y = min(a.y, center.y)
max.y = max(a.y, center.y)
min.z = min(a.z, center.z)
max.z = max(a.z, center.z)

Edit: Es ist ggf. sinnvoller statt diesen "directions" vielleicht lieben das Minimum der jeweiligen BoundingBox im Array zu haben. Das Maximum bekommst du dann indem du size drauf addierst. Das spart dir die ganzen min/max Operationen.

_________________
Yeah! :mrgreen:

Nach oben

Seth

Betreff des Beitrags: Re: Octree Subbäume

Verfasst: Mo Dez 13, 2010 13:15

DGL Member

Registriert: Di Mai 24, 2005 16:43
Beiträge: 710

Coolcat hat geschrieben:

Zitat:

Ich bekomme weniger:

Warum schreibst du dann oben das du mehr bekommst?

Oben bezog ich mich auf die Anzahl der Kollisionen, die nachher auf den Octree angewendet werden (war vielleicht nicht ganz eindeutig ^^).

Zitat:

In dem Fall glaube ich das hier der Hase begraben liegt:

Code:

if (Vector3d.lessThan(a, boundings.getCenter())) {
         min = a;
         max = boundings.getCenter();
      } else {
         min = boundings.getCenter();
         max = a;
      }

Du musst das komponentenweise machen, sonst bekommst du keine valide BoundingBox heraus. ALso irgendwie so:

Code:

min.x = min(a.x, center.x)
max.x = max(a.x, center.x)
min.y = min(a.y, center.y)
max.y = max(a.y, center.y)
min.z = min(a.z, center.z)
max.z = max(a.z, center.z)

Meine Überlegung war ja, dass einer der beiden Eckpunkte der BoundingBox des Subbaums auf jeden Fall der Mittelpunkt der Boundingbox des Vaters sein muss. Aber das sollte bei deiner Überlegung eigentlich auch gewährleistet sein, ich werde das mal testen.

Zitat:

Das habe ich leider nicht ganz verstanden, sry :lol:

Diese Directions sollen mir eigentlich die (äußeren) Eckpunkte der neuen BoundingBoxes liefern. Die inneren Eckpunkte sind ja alle center.

Nach oben

Coolcat

Betreff des Beitrags: Re: Octree Subbäume

Verfasst: Mo Dez 13, 2010 13:38

DGL Member

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java

Zitat:

Meine Überlegung war ja, dass einer der beiden Eckpunkte der BoundingBox des Subbaums auf jeden Fall der Mittelpunkt der Boundingbox des Vaters sein muss

Ne, eben nicht...C ist Center und X und Y sind die Ecken einer der BoundingBoxen. Es muss immer gelten Vector3d.lessThan(X,Y)! Die Achsen werden nach rechts bzw. oben größer.

Code:

+---Y---+
|   |   |
X---C---+
|   |   |
+---+---+

_________________
Yeah! :mrgreen:

Nach oben

Seth

Betreff des Beitrags: Re: Octree Subbäume

Verfasst: Mo Dez 13, 2010 16:16

DGL Member

Registriert: Di Mai 24, 2005 16:43
Beiträge: 710

Stimmt, da wird mein Denkfehler liegen. Noch stimmts aber nicht. Vermutlich ist die Berechnung der Eckpunkte noch falsch:

Code:

   private BoundingBox subTreeBounding(int index) {
      if ((index < 0) || (index >= 8)) {
         return null;
      }
      Vector3d a = Vector3d.add(boundings.getCenter(), Vector3d.multiply(directions[index], size.scale(0.5).abs()));  // sicher blödsinn ;)
      Vector3d min = Vector3d.min(a, boundings.getCenter());   // elementweises minimum
      Vector3d max = Vector3d.max(a, boundings.getCenter());; // elementweises maximum
      return new BoundingBox(min, max);
   }

Nach oben

Seite 1 von 1

[ 9 Beiträge ]

Foren-Übersicht » Programmierung » Mathematik-Forum

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 4 Gäste

Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.