ZFX
ZFX Neu
Home
Community
Neueste Posts
Chat
FAQ
IOTW
Tutorials
Bücher
zfxCON
ZFXCE
Mathlib
ASSIMP
NES
Wir über uns
Impressum
Regeln
Suchen
Mitgliederliste
Membername:
Passwort:
Besucher:
4440656
Jetzt (Chat):
18 (0)
Mitglieder:
5239
Themen:
24223
Nachrichten:
234554
Neuestes Mitglied:
-insane-
"ViewFrustumCulling" von (xcvb)


Hab mich mal überwunden ein IOTW zu schicken.

Wie man leicht sieht handelt es sich um Screenshots einer kleinen Demoanwendung zum ViewFrustumCulling. Rote Boxes sind vollst. außerhalb des ViewFrutum (deshalb sieht man im rechten Teil auch keine solchen), gelbe Schneiden den VF, die grünen sind komplett innerhalb. In der Oberen Version kommt der einfache Algorithmus zur Anwendung, der in der unteren Version um Planemasking ergänzt wurde.

Informationen zum einfachen ViewFrustumCulling:
- Quadtree aus AxisAlignedBoundingBoxes (hier nur 4 Ebenen tief)
- die AABBs werden gegen die 6 Ebenen des ViewFrustum getestet
- ist eine AABB vollständig innerhalb/außerhalb wird in dem Zweig abgebrochen (auch alle Children sind innerhalb/außerhalb)

Ergänzung von Planemasking
- die innerhalb/außerhalb Eigenschaft einer AABB vererbt sich nicht nur für den ganzen VF auf die Children sondern für die einzelnen 'half spaces' die von den 6 Ebenen des VF.

Im blauen Teil des Bildes sind jeweils 53 der 85 AABB-Knoten des Baums (1 + 4 + 16 + 64 für die 4 Ebenen des Baums) getestet worden. Im einfachen Test muss jede AABB solange gegen die Ebenen des VF getestet werden, bis sie außerhalb einer der Ebenen liegt oder bis alle Ebenen getestet wurden. Die AABBs die komplett im VF liegen oder diesen schneiden müssen also 6 mal getestet werden. Für die 53 zu testenden Nodes wären das maximal 318 Tests. Der einfach Test benötigt 303 Tests, da nur für die vollständig außerhalb des VF liegenden AABBs vorzeitig abgebrochen werden kann. Durch Planemasking werden die bereits erfolgreich getesteten Ebenen für die Childnodes nicht erneut getestet. Denn befindet sich eine AABB vollständig auf einer Seite einer Ebene, so gilt das auch für alle AABBs die vollst. in dieser AABB liegen. Dadurch verringert sich die Anzahl der Tests erheblich auf 97 von maximal 318 nötigen.

Im unteren Screenshot sieht man mal einen komplexeren Baum mit 9 Ebenen (87381 Knoten). Dazu hab ich auch mal den Profiler angeworfen. Ein Auszug über den Test von 395 Frames zeigt folgendes (Compileroptimierte Release Version):

Funkt. Anzahl Funktion
Zeit % Aufrufe
106,225 3,3 520911 AABBvsFrustum
62,669 2,0 520911 AABBvsFrustumMask
141,712 4,4 520911 AABBvsFrustumCoherency

Erkenntnisse:
- Dank Hierarchie wurden nur knapp mehr als 1300 Knoten (weniger als 1,5% aller Knoten) im Schnitt pro Frame getestet.
- Die Planemasking Optimierung zeigt deutlich einen Performancegewinn. In komplizierten Fällen - z.B. sehr vielen intersects von Knoten mit z.B. der unteren ViewFrustum Ebene - ist der Vorsprung noch viel deutlicher. Im worst case des Cullings ist sie ca. 5 bis 6 mal schneller als der einfache Test. Im Durchschnittsfall ist sie bis zu doppelt so schnell.
- Die ersten Versuche meiner PlaneCoherency Optimierung gingen ziemlich daneben. Mit Debug Einstellungen ist die Coherency Optimierung wesentlich effektiver, lässt sich allerdings vermutlich weniger gut vom Compiler optimieren. Im aktuellen Stadium ist sie nur bei Bäumen mit bis zu ca. 5 bis 6 Ebenen schneller als der einfache Test und niemals schneller als die Masking Optimierung. Eine Kombination von beiden Optimierungen brachte auch keine Besserung. Dem werde ich wohl noch mal auf den Grund gehen müssen.
- Die niedrigen %-Werte gehen darauf zurück, dass ich ziemlich uneffektiv mit DrawIndexedPrimitiveUP rendere. Bei stärker opimiertem Rendering steigt der Anteil des Culling an der Framezeit und die Optimierung sollte sich auch effektiv in mehr FPS wiederspiegeln.

Nachdem ich das mit der Coherency Optimierung geklärt habe, wird der gleiche Test (nur umgekehrt) auch für Occlusion Culling mit OcclusionFrustums verwendet. Außerdem kann man durch einen Test mit dem Bounding Volume eines Objekts auch die Knoten bestimmen, die auf Kollision getestet werden müssen. Der Einfluss der Optimierungen wird sich also weiter vertstärken. Dann werde ich die Vorteile der Optimierungen in einer sehr einfach Terrainengine testen. Außerdem sollen die klobigen AABBs noch durch was besseres (k-DOPs sind mein Favorit) ersetzt werden.

Wer Interesse an dem aktuellen Code der kleinen Demo hat, und kein Problem damit hat, dass dieser weder gut kommentiert, noch schön anzusehen oder gar gut designt ist, kann einfach eine Mail an mich schicken.

MfG Johannes Löwe (xcvb)






Von Richard Schubert am 13.01.2004, 07:26:11 Uhr
dolle sache.

Von TCS am 13.01.2004, 12:54:00 Uhr
Hallo, sieht nett aus!
Ich hätte gerne den Quelltext und hab kein Problem damit, dass dieser weder gut kommentiert, noch schön anzusehen oder gar gut designt ist :) RatTac@web.de

Thx

Von Tanubi am 13.01.2004, 13:43:43 Uhr
Das mit dem Planemasking blick ich net ganz. Was für Eigenschaften werden da vererbt? Und was bringt das? Könntest das eventuell nochmal genauer erklären?

blutigerAnfaenger

Von Eisflamme am 13.01.2004, 15:28:17 Uhr
Super! :)

Von matrian am 13.01.2004, 17:51:12 Uhr
ganz witzig ""
weiter so!

Von xcvb am 13.01.2004, 18:27:21 Uhr
Zum Plane-Masking:
Bild aus: "Efficient View Frustum Culling" von Sýkora und Jelínek (leicht ergänzt zum beschreiben)
http://www.loewe-soft.de/masking.png

Angenommen p sei die Wurzel des AABB-Baums. Die Maske der zu testenden Ebenen ist 1111 (alle 4 Ebenen müssen noch getestet werden). p liegt vollständig innerhalb der von den Ebenen 1 und 2 erzeugten Halbräume und werden deshalb aus der Maske entfernt, die nun 1100 ist. Da p aber die anderen beiden Ebenen 3 und 4 (in der Zeichnung nicht benannt) schneidet, schneidet p den Viewfrustum und alle Kinder, c1, c2 ... müssen weiter getestet werden. Sie bekommen zum Test jedoch die Maske 1100 mit und wissen so, dass die Ebenen 1 und 2 nicht mehr getestet werden müssen (Bit 1 und 2 - von rechts gesehen - beide 0 in der Maske), da diese Tests ohnehin das ergebnis 'inside' liefern würden. Die Kinder werden also nur noch gegen die Ebenen 3 und 4 getestet. Für c4 würde z.B. die rechte Ebene (sagen wir 3) auch noch rausmaskiert, und evtl. vorhandene Kinder von c4 würden mit der Maske 1000 getestet. Also nur noch gegen eine anstelle von 4 Ebenen.

Für die Blatt-Knoten, die den Viewfrustum schneiden, wird in der Regel nur noch ein Test benötigt, wohingegen der allgemeine Test alle Ebenen testen würde. Die Meisten AABBvsFrustum Tests benötigen also nur noch einen AABBvsPlane Test. Die grünen AABBs benötigen aber immer noch in jedem Fall alle 6 AABBvsPlane Tests. Mal sehen, ob ich dazu auch noch ein paar Statistiken zusammenbasteln kann.

Am Rande: Bisher ist das Feedback ja nicht grad üppig. Klar gibt das Bild (wie mein letztes auch) an sich nicht so viel her, aber die Technik finde ich schon interessant. Ist das jetzt für die meisten ein alter Hut und viele verwenden es eh schon, oder haltet ihr sowas für unnötig.

Um mich mal selbst etwas unter Druck zu setzen: Ich spiele mittelfristig mit dem Gedanken, ein paar kurze Texte zu den Themen:
- Quadtree linear im Speicher
- Traversierungsarten eines linearen Quadtrees (pre-order, post-order, fixed-depth, leaf-only)
[- STL-Container quadtree mit Iteratoren für die Traversierungsarten ]
- ViewFrustumCulling mit dem Quadtree
- Wiederverwendung des VFC für Occlusionculling und Collisiondetection
- Optimierungen (wie z.B. die hier Vorgestellten)

In dieser Reihenfolge, aber vermutlich ohne den STL-Container. Und hey, ich hab auch nicht mein erstets IOTW vergessen und die LOD-Technik wird dann auch noch mit reingenommen (die Konzepte sind im Vergleich zum letzten IOTW schon um dynamisches lodding und effektive Trianglestrip-Erstellung erweitert, aber psst, alles noch geheim ;)). Nur frag ich mich, welcher Teil wieviel Aufmerksamkeit verlangt. Viele werden schon mit dem Quadtree zufrieden sein, während andere den ja schon haben und vielleicht erst von den folgenden Themen was haben. Mal sehen, wenn die Klausuren gut laufen, und in den Semesterferien mich nicht zuviel ablenkt, ist vielleicht was im entstehen.

MfG

Von Praios am 13.01.2004, 20:15:45 Uhr
Jo, super Technik. Scheint keine Nachteile zu haben, da man die Tests sowieso durchführen muss und ist daher wirklich sehr nützlich. Werde ich später bestimmt gebrauchen können, derzeit verwende ich aber noch keine quadtrees.
Inwieweit bist du eigenständig auf diese Technik gekommen. Oder hast du die Idee woanders her? Wie hast du das ausgearbeitet?

Von Mayhem am 13.01.2004, 22:11:49 Uhr
Bisher habe ich mich auch noch nicht so stark mit Octrees befasst. Werde aber, wenn ich mal wieder Zeit dafür finde, "Deine" Technik in meinen Raytracer (bisher rein BSP) einbauen. Sieht sehr interessant aus.

Von Tanubi am 13.01.2004, 22:17:17 Uhr
Wow, ausführlicher hätts ja fast nicht mehr sein können. Danke!
Scheint ja echt eine enorme Aufwandseinsparung mit minimalem zusätzlichen Speicheraufwand zu sein.

Nur eine Frage hab ich noch: Warum arbeitest du mit Ebenen und Quadern, wo du doch einen zweidimensionalen Quadtree hast?

blutigerAnfaenger

Von xcvb am 14.01.2004, 10:18:55 Uhr
Wie man jeweils inm rechten Teil des Screenshots sieht, haben die Quader auch eine Höhe. Und sie werden auch entsprechend an allen 6 Ebenen des Frustum gecullt. Im unteren Screenshot habe ich im linken Teil dann eine orthogonale Projektion gewählt, da das Ergebnis dann besser sichtbar ist. Man sieht ja in den oberen beiden schon, dass eine perspektivische Projektion nicht sehr übersichtlich ist.

Die Technik hab ich natürlich nicht selbst entwickelt. Das meiste stammt aus http://www.cg.tuwien.ac.at/studentwork/CESCG/CESCG-2002/DSykoraJJelinek/. Der Quadtree ist mehr schlecht als recht linear im Speicher angelegt (findet man bestimmt auch Material zu. Interessanter weise decken sich meine Performanceergebnisse nicht mit denen aus dem Paper. Die Coherency-Optimierung bringt bei mir, wenn ich sie wie im Paper implementiere, nichts. Deshalb habe ich sie etwas weiter entwickelt, und verwende sowas wie eine Prioritätsliste für die Ebenen. Wird eine AABB gegen eine Ebene 'out' getestet, wird diese in der Liste nach vorne gesetzt, da es wahrscheinlich ist, dass sie beim nächsten Test wieder 'out' ist. 'in' Ebenen entsprechend nach hinten. Wenn eine Box momentan vollständig sichtbar ist, wird sie im nächsten Frame wohl kaum komplett aus dem VF rausgewandert sein. Im Paper wird für jede Box nur ein Index gespeichert, der dann vor der Schleife extra getestet wird. Nur komm ich mit keiner Version auf das Ergebnis, dass sie am Ende vorstellen.

Von joeydee am 14.01.2004, 10:37:13 Uhr
Zitat:
Am Rande: Bisher ist das Feedback ja nicht grad üppig. Klar gibt das Bild (wie mein letztes auch) an sich nicht so viel her, aber die Technik finde ich schon interessant. Ist das jetzt für die meisten ein alter Hut und viele verwenden es eh schon, oder haltet ihr sowas für unnötig.


Unnötig auf keinen Fall, vor allem die Optimierungstechnik per PlaneMasking ist hochinteressant! Meinen Respekt hast du auf alle Fälle.

Geringes Feedback: Culling-Optimierung ist ein Thema, bei dem man sich erstmal reindenken muss. Wer nicht einfach nur einen Kommentar wie "sieht nett aus" schreiben will, muss sich die Zeit nehmen, das Ganze zu durchdenken. Und wer den Kopf voll hat mit eigenen Projekten ist nicht immer dazu geneigt :D
Aber hier lohnt es sich echt!

Von Cray am 14.01.2004, 17:16:43 Uhr
hi,
sieht wirklich beeindruckend aus,
mich würde der Sourcecode brennend interessieren.
dread@gmx.net

danke!
bye
goodi

Von Zweistein2 am 15.01.2004, 14:07:43 Uhr
*habenwill* *habenwill* :D

Hi, sehr schön! Sieht vielversprechend aus. Ich wollte auch schon immer sowas bauen, war aber immer zu faul.

Durch deinen Denkanstoss werd ich vielleicht mal zeit finden :)

Also schickst du mir das bitte auch?:Matthiasth@gmx.de

MFG

Von Cpt761 am 04.08.2004, 00:19:20 Uhr
Ok, ich weiss, dass das jetzt schon ein Weilchen zurückliegt, aber ich bin grad beim googeln nach Planemasking und Performance drauf gestoßen.

Hast du mal getestet, ob es einen Unterschied in der Performance macht, wenn man für die noch zu testenden Halbräume ein Array von 8 BOOLs/INTs übergibt oder das alles in ein BYTE codiert ( pbyte |= ja_nein_plane<
Es geht mir dabei jetzt nicht um die Anwendung im Frustrum-Culling (wie du dir vieleicht gedacht hast ;-) ), sondern um eine Simulation von Gasen......
Egal, man hat auf jeden Fall auch Halbraüme, auf die man bei Child-knoten nicht mehr testen muss.
Nur sind das dabei ein par mehr - also viel, viel mehr....