BSP`s, Quadtrees und Octrees

[Einfachkrank]

Hi,

ja wie schon erwähnt, wie genau setzt man die ein und wie sind sie aufgebaut(insbesonders Quadtree und Octree)? Und macht es Sinn die im privaten Bereich einzusetzen, oder bringt das zu viel Aufwand mit sich?

MFG Einfachkrank

[zeckensack]

Man benutzt diese Trees um schnell zu überprüfen, was auf dem Bildschirm sichtbar ist (muß gerendert werde) und was nicht (kann man sich dann sparen). Man kann noch mehr damit anfangen, aber das ist erstmal das wichtigste.

Ein solcher Baum teilt rekursiv einen Haufen Daten in Teile auf (binary tree/BSP -> jeweils zwei; Quadtree -> vier; Octree -> acht).

Rekursiv, weil die Unterteile wieder aufgeteilt sind, bis eine bestimmte Tiefe erreicht ist. Das Volumen einer Unterteilung (Node) enthält alle Volumen die in der Baumstruktur darunterliegen (Childnodes, Leaves). Der gesamte Baum (ie der komplette Datensatz) ergibt sich so aus der Summe aller darin (idR an den Blättern, 'Leaves') gespeicherten Daten.

Wenn ich dann zB einen kompletten Level in einem Binärbaum gespeichert habe und anhand meiner Kameraposition festgestellt habe, daß von der Wurzel aus der 'rechte' Ast nicht sichtbar ist, dann brauche ich auch die weiteren Unterteilungen des rechten Asts nicht zu überprüfen.
Nur Elemente des linken Asts können überhaupt sichtbar sein. Damit habe ich auf einen Schlag den halben Level von der weiteren Untersuchung ausgeschlossen, das können zigtausende Dreiecke sein, oder gar noch mehr. Sehr effizient.

Dann schaue ich im linken Hauptast weiter, arbeite mich den Baum hinab bis ich eine Liste aller (zumindest teilweise) sichtbaren Bildteile habe. Uswusf.

Am Ende brauche ich dann nur das zu rendern, was auch tatsächlich zu sichtbaren Pixeln führt.

(Googeln nach 'binary space partition tutorial')

Das gleiche funktioniert sinngemäß auch mit Quadtrees und Octrees. Ein Binärbaum teilt einen Raum mittels einer Ebene in zwei Teile.
Ein Quadtree teilt mittels zweier Ebenen, die sich in einer Gerade schneiden.
Ein Octree teilt mittels dreier Ebenen die sich in einem Punkt schneiden.


Das Thema ist leider viel zu kompliziert um hier vollständig erklärt zu werden. Ich würde vorschlagen daß du erstmal ein wenig googelst und die einschlägigen Tutorial-Seiten (siehe Stickie hier im Forum) abklapperst. :)

[Che]

Holla, das interessiert mich auch.
Ich bin im Moment auf der Suche nach einer methode mit der ich mein Gelände schneller rendern kann, da würde sich doch ein Quad/Octree anbieten (Binary schonmal nicht weil man im Gelände keine vernünftigen Teilerpolygone findet, und der Baum soll ja am schluss auch "ausgewogen" sein, d.h. auf beiden seiten ungefähr gleich viel polys)

Ich bin aber am nachdenken, ob sich quad/octrees in zeiten von Hardware T&L überhaupt noch lohnen - vielleicht wär ein LOD-System besser? (Ich sprechen hier von Gelände, also nix Indoor)
Was meinen die Gurus?
(btw, verträgt sich LOD mit Quad/Octrees?)

Wie die Bäume funktionieren hab ich ungefähr kapiert, aber leider kA wie man ein LOD-system angeht - auch keinen Tuts gefunden. Ich wäre an dieser Stelle für einen Link sehr dankbar. :)

[Nasenbaer]

Also wenn ich das richtig verstanden habe, schließt sich beides nicht von einander aus.

Die Polygone, die sichtbar sind und gerendert werden müssen kannst du ja dann noch mittels LOD in verschiedene Detailgrade unterteilen.

Mfg NAsenbaer

[Demirug]

ja man kan durchaus Quad/Octree mit einem LOD kombinieren. Über den Octree (bzw Quad) werden die im Sichtbereich liegenden Objekte bestimmt und über die Entfernung des Objects zum Betrachter wird das LOD bestimmt. Das ganze ist jetzt natürlich etwas vereinfacht ausgedrückt in der Praxsis muss man da noch auf gewisse Unschönheiten wie zum Beispiel Polygonenpopping aufpassen.

Wenn es um Gelände LOD geht ist diese Seite in der Regel ein guter Ausgangspunkt: http://www.vterrain.org/LOD/Implementations/

[uh-lee]

Originally posted by Che
(Binary schonmal nicht weil man im Gelände keine vernünftigen Teilerpolygone findet, und der Baum soll ja am schluss auch "ausgewogen" sein, d.h. auf beiden seiten ungefähr gleich viel polys)Naja, Binary macht schon Sinn, wenn man die Cuts von Hand setzt. Wenn du dein Terrain per Code generierst ist Quad-/Octree aber die für den Programmierer angenehmere Variante.
Naja, letztendlich eine Frage der Zeit bzw. Manpower die du zur Verfügung hast. Mir sind die Binärtrees eigentlich sympathischer, aber sie erfordern eben mehr Handarbeit.

[zeckensack]

Letztendlich läßt sich ein beliebiger Quadtree/Octree/n^2-tree auch auf einen Binärbaum reduzieren :)

Der Unterschied ist ja nur, daß man pro Node mehr Verzweigungen hat und die Teilungsregeln nicht ganz so flexibel sind (weil zB beim Octree pro Node immer acht Teilungen erstellt werden, auch wenn nur eine davon Nutzdaten enthält). Ersteres kann ein Vorteil sein, letzteres ist generell ein Nachteil, wenn auch nicht unbedingt ein großer.

[Che]

Originally posted by uh-lee
Naja, Binary macht schon Sinn, wenn man die Cuts von Hand setzt. Wenn du dein Terrain per Code generierst ist Quad-/Octree aber die für den Programmierer angenehmere Variante.
Naja, letztendlich eine Frage der Zeit bzw. Manpower die du zur Verfügung hast. Mir sind die Binärtrees eigentlich sympathischer, aber sie erfordern eben mehr Handarbeit.

Also wenn ich alles richtig verstanden habe müsste man ja dann JEDE EINZELNE Teilerebene von Hand setzen -> das ist aber viel Arbeit :D
Außerdem weiß man ja (üblicherweise) vorher nicht wie das Terrain aussieht, wie soll man dann vernünftige Cuts setzen?

Mir fällt gerade ein, ich krieg mein Gelände von einer heightmap, also weiß ich schon vorher wies aussieht, aber wie soll ich von der Heightmap (Bilddatei) darauf schließen wo ich am besten meine Cuts setze?

(Überlegung: einfach entlang einer hellen Linie (->hohes terrain) cutten wird wohl nicht hinhauen...)

[uh-lee]

Yep, ihr habt natürlich recht.

Che, das mein ich mit "wenn du dein Terrain automatisch generierst".
Was ich meine ist, dass du wenn du die Zeit und so hast, du wahrscheinlich nicht ewig nur mit heightmaps hantieren wirst, sondern irgendwann einen level editor proggen/benutzen wirst.

Wenn ich recht verstehen compilierst du im Moment den Tree direkt von der Heightmap, was die Möglichkeit des nachträglichen editirens des Terrains natürlich einschränkt.

Ansonsten sag ich ja, nimm ruhig codemäßig generierte Octrees, die sind auf jeden Fall einfacher für den Coder :-).