Hi,

ich bin grad bei meiner engine dabei einen Octree einzubauen, allerdings habe ich hier ein problem.. kein technisches, sondern mehr ein generelles zum thema beschleunigung durch Octrees etc.

Mein test-level ist ein recht low-leveliges Indoor Scenario wo jede wand nur aus 2 Triangles besteht.. die triangles sind halt relativ groß wodurch ein aufteilen in Octree nur bedingt gut machbar ist..

Entweder ich gebe eine feste größe für die kleinste unterteilung des trees vor, dann kann es aber passieren das aufeinmal in einer der unterteilungen sehr viel geometry steckt weil es durchaus auch high-poly objekte in der scene gibt.. sage ich "Minimal 100 Triangles pro branch", klappt es zwar mit den unterteilungen.. aber da die Triangles ziemlich groß sind würde ich dadurch u.U. nur wenig performance gewinnen..

Ist etwas schwer zu erklären..

Worauf ich hinaus will, es gibt ja noch alternativen zu Octrees.. welche? Und wo sind die jeweiligen vor- und nachteile?

Ich kenne sonst nur noch BSP-Trees, hab aber bei denen noch nie richtig verstanden wie die funktionieren..

Aya~

Portal-Rendering könnte was für dich sein, dazu musst du deiner Engine nur begreiflich machen, was Räume sind, und wo Türen/Fenster/Durchgänge sind.
Der Raum in dem du bist wird dann immer gerendert (wobei du die high-Poly-Modelle vlt. noch einzeln in einen Occtree oder ähnliches packen könntest,
damit von denen nur sichtbare Stellen gerendert werden). Die anderen Räume werden nur dann, wenn ein durchgang in diesen Raum sichtbar ist.
(Falls es schließbare Türen gibt könntest du hier noch testen ob die Tür nicht vlt. zu ist)

Das hat aber den Nachteil, dass du a) Durchgänge makieren oder b) Durchgänge irgendwie detektieren können musst.

Außerdem schlägt das ganze bei Räumen mit vielen Polygonen fehl (daher der Vorschlag diese nochmal mit einem Octree zu unterteilen, dann sind die "Riesen-triangles" auch nicht mehr mit drin)

Weniger arbeit hättest du aber wahrscheinlich wirklich mit BSP, vor allem wenn die Sichtbarkeitsmap vorberechnet ist - dazu habe ich aber leider gerade keinen Link ö.ä. da.

_________________
Bevor du definierst, was etwas ist, versichere dich seiner Existenz.

Wenn es bei Indoor bleibt, solltest du auf BSP setzen und wenn du auch aussenlandschaft hast, dann Octree.
BSP zerlegt ein Raum in unterräume, indem es Portale sucht und an diesen die Räume trennt.
Deswegen benötigt man auch ein geschlossenden Raum für BSP.
Bei Spielen wie HL wird um das ganze Level noch eine Box gezogen(Skybox) und damit kann dort BSP auf aussengelände durchlaufen aber das ist höchstgradig ineffizient, wenn die Aussenlandschaft größer wird, da dann ein Node des BSP die ganze Aussenlanschaft ist und somit ziemlich rechenlastig.
Octree ist wesentlich Vorteilhafter, da es immer funktioniert und vorallem Konstante Leistung bringt.
Es zerlegt zwar Innenräume oft Inefizient aber das ist nicht weiter wild.
Ladezeiten sind beim Octree gleichmässig, wärend beim BSP diese starke Schwankungen haben, je nach Raumkomplexität.
Sinnvoll wäre es bei Octree schon die Leveldaten entsprechend zu optimieren(zerlegung des Meshes in Nodes).
Dann muss das nicht mehr zur Ladezeit noch Flächen zerschnitten werden und du kannst jedes Node als VBO verwenden.
Wenn Meshes mit blending drin sind bekommen die ein extra VBO.
Die Nodes kann man nach Geschmack aufbauen aber sinnvoll wäre wohl abhängig der Polygonanzahl zu zerlegen(wegen ausnutzung von VBO und Vertex-Cache).
Allerdings hat auch das Unterteilen in feste Blockgrößen Vorteile(weniger Nodes im Baum, das handhaben von dynamischen Objekten wird einfacher, da diese einfach in ein entsprechend großes Node mit rein gehangen werden können, ohne es zu zerlegen und man kann kommende Hardware noch unterstützen, da die Polygonzahl nicht fixiert ist).
Die Unterteilung von Mesh bringt nicht wirklich viel(man reduziert die Anzahl der zu Prüfenden Objekte nur geringfügig).
Was die Gewschwindigkeit bringt ist der Sichtbarkeitsbaum, also die Listen mit Sichtbaren Nodes für jedes Node.
Für größere bzw. theoretisch unendliche Welten, sollte das Octree entsprechend designed werden und streaming nutzen, sowie sich dynamisch selber aufbauen. Wenn du dich bewegst, dann sollten die Nachbarnodes entsprehend geladen werden und länger nicht mehr gebrauchte Nodes entfernt werden.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004