Extrusion+Octree

Hallo zusammen!
Ich hoffe, ihr habt die Feiertage gut überstanden!

Gleich mal wieder ein schönes Problemchen:

Ich nutze in meiner 3DApplikation einen Octree zur Performancesteigerung. Prinzipiell ist es mir möglich alle verwendeten 3DModelle in 3DObjekte und diese wiederum in 3DFaces zu unterteilen. Somit kann ich alle sichtbaren
Komponenten bis auf die Faceebene genau in den Knoten des Octree unterbringen und auf Sichtbarkeit testen.
Wirklich alle sichtbaren Komponenten?
==> Leider auf den ersten Blick nicht!
Manche recht umfangreiche Komponenten werden in meiner Anwendung durch Extrusion erzeugt und gerendert. Solche Komponenten als 3DModelle im Speicher zu halten wäre natürlich viel zu aufwendig. Das bring allerdings das Problem mit sich, dass ich solche Komponenten (z.B. eine Rohrleitung) nicht in 3DObjekte und 3DFaces aufsplitten kann und demzufolge auch nicht bis auf die Faceebene genau im Octree unterbringen kann. Was zur Folge hat, dass diese 'Rohrleitungen' viel leichter als fälschlich sichtbar erkannt werden als erwünscht.

Kann mir vielleicht jemand einen kleinen Tipp geben, wie man solche
Komponenten vielleicht doch gewinnbringend in einen Octree einbauen
könnte?

Vielen Dank für eure Hilfe!

Grüße,
TS++

rapso

es lohnt heutzutage nicht objekte zu zerstückeln und in den octree zu stecken, das macht man nur objektweise, weil man ja sonst das object aus dem octree polygon für polygon wiederherstellen müßte, das dauert länger als das objekt im grafikkartenspeicher zu lassen und einfach von der grafikkarte die potentiel sichtbaren bereiche zeichnen zu lassen (die nicht sichtbaren "erkennt" sie ja selber).

somit solltest du in deinem octree alles anhand von bounding volumes eintragen, damit wären deine dynamisch objecte auch recht simpel einzufügen.
falls du sie jedes frame (aus welchen gründen auch immer) neu generierst, kannst du sie ja immer noch vom frustrum cullen lassen.

rapso->greets();

Was das Zerstückeln anbelangt:
Ich wäre grundsätzlich so vorgegangen, dass ich beim Aufbau des Octrees mittels BoundingSpheres feststelle, welches 3DModell bzw. welche 3DObjekte bzw. welche
3DFaces in welchem Voxel liegen. Dann hätte ich in diesen Voxels, also auf der
tiefsten OctreeEbene Verweise auf die zugehörigen Modelle,Objekte,Faces hinterlegt. Abschließend hätte ich, das hab ich so noch gar nicht ausprobiert,
für alle Voxels Displaylisten erstellt. Wenn ich nun während des Renderns feststelle, dass ganz bestimmte Voxels sichtbar sind, gebe ich diesen lediglich den Befehl sich zu rendern, worauf diese die ihnen zugeordnete Displayliste laden.

==> das war die prinzipielle Idee! Ich war auf den ersten Blick erst mal davon überzeugt, dass man damit die Framerate erhöhen könnte!?

Und nochmal ganz kurz zu den 'Rohren':
Stell dir mal vor, ich hätte in meiner 3DWelt ein System weitverzweigter Rohrleitungen. Diese Rohrleitungen lassen sich in einzelne Abschnitte aufteilen.
Die Daten zur soliden Berechnung dieser Rohrabschnitte stehen mir zur Verfügung.
Allerdings möchte ich natürlich nicht das Rohr selbst komplett auf dem Heap behalten, also nicht alle Faces und Normals sondern nur die Rechenvorschrift, wie Stützpunkte usw. Ich werde also den Extrusionsalgorithmus erst beim eigentlichen Rendern anwenden. Vorteil: ich spare Speicher Nachteil: ich halte, wie oben erwähnt, die renderfähigen Rohrabschnitte (3DModelle,3DObjekte,3DFaces) nicht objektorientiert im Speicher, sondern nur Konstruktionsdaten. Ich kann demzufolge die Rohrabschnitte nicht wie andere sichtbare Komponenten in kleinere Bausteine aufsplitten und auf der Voxelebene des Octrees ablegen. Ich werde die Rohrabschnitte augrund ihrer Größe auf höheren Ebenen des Octrees ablegen müssen -> da es mir ja die BoundingSpheres so eines Rohrabschnitts nicht möglich machen, im Octree noch weiter nach unten zu rutschen. D.h. sobald festgestellt wird, dass der Würfel, in dem sich ein 'großes' Rohrelement befindet, sichtbar ist, wird das komplette Rohrelement gerendert.
Ob das dann wirklich so viel ausmacht weiss ich nicht!
Nur stört es mich, dass ich alle anderen Elemente sauber auf der untersten Ebene des Octrees ablegen kann, wogegen ich Rohrelemente auf höheren Ebenen liegenlassen muss!

Glaubst du wirklich, dass das nicht so viel ausmacht?

Danke,
TS++

rapso

du zerstückelst also das objekt nur damit du perfekt rausbekommst ob ein poly zu sehen ist?
das ist leicht unoptimal. du kannst das objekt einfach in die box reinstecken in die es noch reinpasst aber in deren childboxes nicht.
das mit den displaylists ist dann schon recht gut!

wenn du bessere ergäbnisse beim cullen haben möchtest, dann kannst du mehrere volumes um deine objekte packen z.B. zylinder,kugeln,AABBs und OBBs, wenn du dann z.B. die sphere im frustrum hast, dann kannst du noch die OBB testen und so bekommst du zwar nicht das gleiche ergäbniss, als wenn du jedes poly einzeln testest, aber manchmal kann es schneller sein ein objekt stupf auf der karte durchrechnen zu lassen, anstatt jedes poly zu testen.

vielleicht, wenn dich die stupfmethode abschreckt, könntest du ein objekt in 100poly blöcke aufspalten und die dann immer in den octree einfügen. dann hättest du einen kompromiss zwischen culling präzision und performance... also nur als vorschlag.

rapso->greets();

Danke für den Vorschlag!

Falls es sich so angehört hat, als ob ich alle 3DModelle extra für das ViewFrustrumCulling in Objekte und Faces aufsplitte, so korriegiere ich das besser jetzt. Alle 3DResourcen, die ich verwende, können über die Hierarchie Modell->Objekt->Face angesprochen werden. Ebenso kann ich für das komplette Modell, oder auch nur für ein konkretes Objekt, einen BoundingTree erzeugen lassen. Ich nutze also nur die bereits vorgegebenen Strukturen.

Du meinst also, dass ich 3DKomponenten, die ich nicht in meiner Hierarchie darstellen kann oder will(Speicher), einfach in den Octree mit einfügen soll(also in die Box, in der noch genug Platz ist)?!
Und dass ich dann, wieder bei dem Rohrbeispiel, das betroffene Rohrelement in enger zugeschnittene BoundingVolumes innerhalb der Box einfügen soll!?(wieauchimmer man das hinkriegen soll)
Könnte ich dann, wenn ich feststelle, das die Box, in der sich das Rohrelement befindet, sichtbar ist, zum Testen nicht gleich die BoundingBoxes des Rohrabschnitts verwenden? Denn ich kann so ein Rohr zwar, nicht ohne jede Menge Speicher zu verschenken, als Modell im Speicher halten, aber ich kann für das Rohr doch einen BoundingTree ermitteln. Also: 1 Sphere für den Rohrabschnitt, für jeden Zylinder 1 Sphere und für jeden Triangle jedes Zylinders 1 Sphere.
Das frisst zwar auch wieder Speicher, aber ich könnte wenigstens damit einen BoundingVolume um das Rohrelement beschreiben, der sehr eng ist!

Grüße,
TS++

rapso

ja so in etwa meinte ich das, wenn du etwas aufsplitten müßtest bzw. 2 oder mehrmals in die childboxen aufteilen/einfügen müßtest, dann lieber in der aktuellen box lassen, denn wenn du das objekt in die unteren boxen einfügst, dann bekommst du nicht unbedingt eine culling verbesserung, du wirst dann nur öfter feststellen, dass das objekt zu sehen ist

ja es kann dann auch passieren, dass keine childbox in der sich das objekt befindet, zu sehen ist.
aber für den fall hast du ja um das objekt selber noch ein bounding volume. das sollte man sowieso grundsätzlich haben.
du solltest nicht gleich die objekte testen, sondern das octree benutzen, damit du den vorteil eines octree nutzt, nämlich durch einen test vielleicht 50% der ganzen geometrieobjekte verwerfen zu können, außerdem hast du beim octree nicht nur "sichtbar=true" und "sichtbar=false" sondern:
-unsichtbar
-vollkommen sichtbar
-teilweise sichtbar

-bei unsichtbar von einer box verwirfst du alles was drinne ist
-wenn die ganze box sichtbar ist, brauchst du ja nicht weiter zu testen, denn alles darin wird sichtbar sein
-bei teilweise sichtbar mußte weiter testen.

wenn du jedes objekt einzeln testest, dann verlierst du diese optimierung, die ein octree bietet und mußt tausende von 100%ig sichtbaren oder unsichtbaren boxen testen (oder wie auch immer die bounding volumes von dir aussehen werden)

der nachteil eines octrees ist wiederum dass du objekte die z.B. megalang aber dünn sind, nur schlecht einordnen kannst, die steckt man dann so weit in den baum, solang man es nicht zerstückeln oder mehrfach reinstecken muss, und dann prüft man notfalls nochmal das bounding volume des objektes selber (nur wenn die box in dem sich das mesh befindet nicht 100% sichtbar oder unsichtbar ist)

rapso->greets();

ps. wie lange ich um immer das selbe reden kann ... *kopfkratz*

TS++

Danke, dass du bei meinen etwas längeren Ausführungen mithältst!
==> *Handschüttel*

Aber ich denke, wenn man etwas allgemeingültig erklären will, so dass die Beiträge auch evtl. einem anderen FAQ-Sucher weiterhelfen, kommt man um ein paar Zeilen mehr nicht drum herum!

Aber das Thema ist wirklich nicht zu unterschätzen! Die Grundprinzipien der Raumaufteilung, und damit natürlich auch von Quad-,Oc- und BSP-Trees(taucht ja als Thema immer wieder auf), hat jeder schnell begriffen. Nur einen effizienten möglichst allgemeingültigen Ansatz, den es wahrscheinlich garnicht gibt, zu finden, kann unter Umständen, siehe Extrusion oder Animationen, recht schwierig oder zumindest sehr aufwendig sein!
Na ja, mal sehn wann mir die nächste Frage einfällt!

Grüße,
TS++