Screen culling für Surround Gaming

[Demirug]

In einen anderen Thread haben zeckensack und ich einen Diskussion über Screen Culling angefangen. Da es dort Offtopic war geht es hier weiter:

Bisher:

Zeckensack:

Ein Spatz auf meinem Dach hat mir erzählt, daß die gängige 'moderne' Methode für's culling auf einem Kreiskegel beruht. Da kriegt man nicht mehr viel weg, wenn man den Sichtbereich beinahe auf 180° hochdreht

Demirug:

Das mit den Kreiskegeln hab ich mir ganz schnell abgewöhnt. Das bleit auch beim "normalen" Sichtbereich zuviel unnötiges übrig.

Im Moment benutze ich 6 Ebenen im Raum die den Sichtbereich bschränken. Nun wird einfach noch das Umgebungsvolumen der Objekte(Kugeln gehen am schnellsten) gegen jede Ebene gebrüft. Schneidet das Volumen eine Ebene oder liegt das Volumen immer hinter der ebene muss es gerendert werden. Ist ziemlich gut und schnell und man bekommt auch noch gleich einen LOD Wert.

Zeckensack:

Das ist sicherlich eine gute Methode und vor allem hat sie keine Probleme mit assymetrischen Blickfeldern.

Trotzdem behaupte ich, wenn das Blickfeld weitgehend symmetrisch ist (4:3 ist ok) und sehr viel Software-Culling betrieben wird (ein paar zigtausend Tests pro Frame), dann ist der Kreiskegel besser. Auf Spiele trifft das natürlich idR nicht zu, nur so als Gedanke.

[zeckensack]

http://www.forum-3dcenter.org/vbulletin/showthread.php?postid=301915#post301915
Originally posted by zeckensack
Ein Spatz auf meinem Dach hat mir erzählt, daß die gängige 'moderne' Methode für's culling auf einem Kreiskegel beruht. Da kriegt man nicht mehr viel weg, wenn man den Sichtbereich beinahe auf 180° hochdreht ... Originally posted by Demirug
Das mit den Kreiskegeln hab ich mir ganz schnell abgewöhnt. Das bleit auch beim "normalen" Sichtbereich zuviel unnötiges übrig.

Im Moment benutze ich 6 Ebenen im Raum die den Sichtbereich bschränken. Nun wird einfach noch das Umgebungsvolumen der Objekte(Kugeln gehen am schnellsten) gegen jede Ebene gebrüft. Schneidet das Volumen eine Ebene oder liegt das Volumen immer hinter der ebene muss es gerendert werden. Ist ziemlich gut und schnell und man bekommt auch noch gleich einen LOD Wert. Originally posted by zeckensack
Das ist sicherlich eine gute Methode und vor allem hat sie keine Probleme mit assymetrischen Blickfeldern.

Trotzdem behaupte ich, wenn das Blickfeld weitgehend symmetrisch ist (4:3 ist ok) und sehr viel Software-Culling betrieben wird (ein paar zigtausend Tests pro Frame), dann ist der Kreiskegel besser. Auf Spiele trifft das natürlich idR nicht zu, nur so als Gedanke.

Wird langsam etwas OT, aber wir haben ja jetzt ein Progger-Forum =)



@Demirug: Ich glaube, das kann man vereinfachen.
Symmetrisches Blickfeld vorausgesetzt, erstmal die drei Grundachsen des Koordinatensystems nehmen, sagen wir mal die drei Vektoren +Z, +X, +Y

Dann noch den Mittelpunkt P und den Radius R des zu testenden Objekts. Die Position des Auges (resp Kamera) sei E (eye point ...)

Dann:

1)Tiefe=LOD-Wert=+Z * (P-E) (<- * soll ein Skalarprodukt sein)

2)Wenn (Tiefe-R)< (Entfernung der Near Clip Plane), dann weg damit

Jetzt wirds etwas komplizierter (jedenfalls in der Erklärung). Wir müssen die +X und +Y Vektoren jetzt so skalieren, daß die Projektion wieder ausgeglichen wird, sprich, je tiefer das Objekt im Bildschirm liegt, desto kleiner sollen sie werden . Das hängt vom FOV ab. Es läuft am Ende zum Glück auf einfache Multiplikation hinaus:

3)
Xneu=+X*cx/Tiefe (<-cx ist eine Konstante zur Skalierung)
Yneu=+Y*cy/Tiefe (<-dito)

4)Jetzt berechnen wir Skalarprodukte, vergleichen diese mit einem Schwellenwert und verwerfen bei Überschreitung das Objekt. Das schöne daran ist, daß wir uns die Ebenengleichung erspart haben. Weil wir von symmetrischem Blickfeld ausgegangen sind, brauchen wir den Test außerdem pro Achse nur einmal, wir können für den Vergleich das Vorzeichen wegwerfen. Dadurch, daß wir oben Xneu und Yneu 'in der Tiefe verkleinert' haben, ist das Culling auch perspektivisch richtig.

Wenn abs(Xneu*(P-E))>Schwellwert, dann weg damit
Wenn abs(Yneu*(P-E))>Schwellwert, dann weg damit

Erklärund: Das erste Skalarprodukt ist das Quadrat des perspektivisch entzerrten 'senkrechten Abstands' zwischen Objektmittelpunkt und einer Ebene, die die Z-Achse enthält, und die - auf den Bildschirm bezogen - waagrecht liegt.

Die Sache hat einen Haken: Sie funktioniert so nur mit Punkten korrekt. Der Radius muß auch vorskaliert werden.

Setzen wir also
4a)
Rx=R*cx/Tiefe
Ry=R*cy/Tiefe
4b)
Wenn abs(Xneu*(P-E))> (Schwellwert-Rx), dann weg damit
Wenn abs(Yneu*(P-E))> (Schwellwert-Ry), dann weg damit


Kleine Optimierung: Die Faktoren cx/Tiefe und cy/Tiefe sollten sinnigerweise nur einmal berechnet werden.

Und?

[zeckensack]

Zwei dumme, ein Gedanke (http://www.forum-3dcenter.org/vbulletin/showthread.php?threadid=24445) :D

[Demirug]

Pro Ebene braucht man maximal 4 Multiplikationen und 4 Additionen (SIMD freundlich) einmal den absolute Betrag und zwei vergleiche. Maximal müssen 6 Ebenen geprüft werden. Ein grosser Teil wird in der Regel aber schon nach der zweite Ebene verworfen.

0% Fehler beim Cullen.

Bei Kreiskegel bekommen wir einen nicht unbedeutenden Fehlerquote.

Desweiteren enthält die Rechnung einige Wurzeln, acos und atan. Nicht sehr SIMD freundlich.

Was die anzahl der Objekte angeht. Mehrer Objekte zu Gruppen zusammenfassen und zuerst das volumen der Gruppe prüfen. Für dynamische Welten gibt es da bewerte Verfahren (z.B. Octrees).

[zeckensack]

Originally posted by Demirug
Bei Kreiskegel bekommen wir einen nicht unbedeutenden Fehlerquote.Wenn der Kegel das Sichtfeld komplett umschließt und der Abstandscheck korrekt implementiert ist, dann gibt's doch keine Fehler ??? :|
Desweiteren enthält die Rechnung einige Wurzeln, acos und atan. Nicht sehr SIMD freundlich.acos und atan? Willst du Winkel ausrechnen? Du mußt doch 'nur' das Objekt (inklusive Perspektivenkorrektur) auf die 'Kameraebene' projiziern und den Abstand vom Kamera-'Punkt' ausrechnen. Dafür braucht es keine transzendentalen Funktionen, lediglich eine Division (<- was etwas unfein ist, dafür muß man auch nur drei Checks machen: hinten, vorne, Radius. Das steht gegen sechs Checks beim Ansatz mit den Ebenen).Originally posted by Demirug
Was die anzahl der Objekte angeht. Mehrer Objekte zu Gruppen zusammenfassen und zuerst das volumen der Gruppe prüfen. Für dynamische Welten gibt es da bewerte Verfahren (z.B. Octrees). Das ist eine sehr feine Idee ... :| ... :)

[Xmas]

Originally posted by zeckensack
Wenn der Kegel das Sichtfeld komplett umschließt und der Abstandscheck korrekt implementiert ist, dann gibt's doch keine Fehler ??? :|
Fehler nicht, aber es wird nicht so "perfekt" gecullt wie bei der Ebenenlösung, die ja genau dem sichtbaren Bildbereich entspricht (auch wenn es natürlich sein kann, dass die Bounding-Box/Sphere im sichtbaren Bereich liegt, das Objekt jedoch nicht).

[Demirug]

Mit Cullingfehler meine ich das Objekte die eignetlich nicht gerendert werden sollen trozdem zur Karte gehen und dann dort auf Dreicksebene gecullt werden müssen. (Kostet AGP und Shader leistung)

"acos und atan? Willst du Winkel ausrechnen? Du mußt doch 'nur' das Objekt (inklusive Perspektivenkorrektur) auf die 'Kameraebene' projiziern und den Abstand vom Kamera-'Punkt' ausrechnen. Dafür braucht es keine transzendentalen Funktionen, lediglich eine Division (<- was etwas unfein ist, dafür muß man auch nur drei Checks machen: hinten, vorne, Radius. Das steht gegen sechs Checks beim Ansatz mit den Ebenen)."

Das erfordert erst mal eine 4*4 Matrix operation und bei einer Kugle läst sich die Perspektivenkorrektur nicht so gut durchführen. Veileicht kennst du ja ein besseres verfahren? Ich habe damals 4 Punkte der Kugel transformiert und gebprüft.

Deswegen bin ich ja dazu übergegangen zuerst die entfernung zur Frontplane zu bestimmen (DOT produkt und eine Addition). Damit habe ich dann auch die Entfernung zur Backplane (ist ja parralel).

Mit zwei ifs ist dann schon ein großer Teil weg. Mit den restlichen 4 Ebenen dann eben das gleiche.

andere Thread:

So ganz verstehe ich das noch nicht. Du skaliert zwar X und Y aber ich kann nicht erkennen wo die Position berechnet wird. Wenn ich nun den Radius hinzufüge brauche ich ja wie gesagt 4 Punkte womit wir wieder beim gleichen wären.

[zeckensack]

Zu dem anderen Thread (ich glaub' ich kopier den gleich hier rein ...):
+---------+
| | O
| + |
| |
+---------+
O ist das Objekt, das + in der Mitte der Bildschirmmittelpunkt und gleichzeitig die Z-Achse.

Lassen wir das Tiefen-Skalieren mal weg, sonst kann ich's unmöglicher mit der Skizze vereinbaren ...

Das Skalarprodukt einer Normalen (Länge:=1) und eines Vektors liefert immer nur den Abstand in Richtung der Normalen.

Stellen wir uns vor, daß durch unsere Z-Achse zwei Ebenen verlaufen, eine senkrecht, die andere waagerecht (in Bezug auf den Bildschirm). Die Normalen dieser Ebenen kann man mehr oder weniger direkt aus einer Transformationsmatrix (Modelview bei GL, bzw World bei DX) entnehmen.

Dann ist (O-Beliebiger Punkt auf der Z-Achse)*(Oberflächennormale einer der Ebenen) = der Abstand zu dieser gedachten Ebene, egal über welcher Stelle auf dieser Ebene das Objekt 'schwebt'. Als "Punkt auf Z-Achse" wähle ich den eye point E.

Ist der Wert (beim Test in X-Richtung) negativ, dann liegt der Objektmittelpunkt links vom Bildschirmmittelpunkt, ohne Aussage über die Höhe.

Nun fehlt noch der Radius.
Für den korrekten Test nach rechts prüfe ich dann
(O-E)*Normale < (Xmax + R)

Für den Test nach links und rechts gleichzeitig prüfe ich sinngemäß
abs((O-E)*Normale) < (Xmax + R)

Sinngemäß gilt dann das gleiche für die Y-Richtung. Beides zusammen ergibt einen sauberen Culling-Test gegen einen Bildschirm-'Schlauch'. Die restlichen Operationen dienen nur dazu, die Perspektivkorrektur mit einzubeziehen. Dies funktioniert übrigens für Kugeln identisch, wie bei zur Near Plane parallelen Kreisscheiben, denn du mißt immer 'an der dicksten Stelle'.

[Demirug]

Jetzt glaube jetzt habe ich es verstandenden.

Wir definieren drei zueinander senkrechte ebnen im Raum. Diese werden durch die Position und Blickrichtung der Kamera bestimmt.

Würde man diese Ebenen von Welt in Screenkoordinaten projeziert bekämme man:

1. Den Bildschirm
2. Eine Senkrechte auf der Mitte des Bildschirms
3. Eine Wagerechte auf der Mitte des Bildschirms

Nun bestimmen wir die Entfernung aller Spharenpunkte zu diesen 3 Ebenen und führen folgende Prüfungen durch. Damit das Object welches die Spahre umschliesst gerendert wird müssen alle bedigungen erfüllt sein.

1. Ebene:

Entfernung1 >= -Radius
Entfernung1 <= Sichtweite+Radius

2. Ebene:

abs(Entfernung2) < (Xmin + R*Entferung1*XScale)

3. Ebene:

abs(Entfernung3) < (Ymin + R*Entferung1*YScale)

Ist das so richtig???

[zeckensack]

Hmm, wenn ich's mir recht überlege, sind Kreisscheiben und Kugeln doch nicht wirklich vergleichbar ...
Eine Kugel könnte immer noch in das Sicht-Frustum hineinragen... glücklicherweise ist dieser Fehler eine Konstante (abhängig vom FoV und dem Radius). Bei (hypothetischem) 180°-Rundumblick wäre der Fehler == Radius. Aus der Hüfte geschossen würde ich sagen, daß er bei cos(0,5*FoV)*r liegt. (wobei ich hier mit 180° FoV einen kompletten Halbraum meine)
Meine Rechnung liegt immer genau um diesen Betrag daneben. Man sollte also pro Frame 1+cos(0,5*FoV) vorberechnen (kann in x- und y-Richtung unterschiedlich sein!), und das dann später mit den Objektradien multiplizieren. Nennen wir das mal rXrcale und rYscale.

Punkt 2:
Sehr elegant wäre es, wenn man für die Tiefenskalierung den W-Wert nähme, der hinten aus der Geometriepipeline rauskommt. Denn damit macht auch der Grafikchip selbst die Perspektivkorrektur. Man müßte dazu den Mittelpunkt des Objekts als Vektor nehmen und mit der W-Zeile der kombinierten Transformationsmatrizen ein Skalarprodukt machen (meint: vierte Zeile von Model*World*Camera, resp Modelview*Projection bei OpenGL. Dieser 'Zeilenvektor' kann einmal pro Frame vorberechnet werden)

Originally posted by Demirug
1. Ebene:

Entfernung1 >= -Radius
Entfernung1 <= Sichtweite+Radius

2. Ebene:

abs(Entfernung2) < (Xmin + R*Entferung1*XScale)

3. Ebene:

abs(Entfernung3) < (Ymin + R*Entferung1*YScale)

Ist das so richtig??? Beinahe so, wie ich es gedacht hatte. Ich möchte es aber mittlerweise sowieso umändern, die alte Idee war nicht ganz korrekt:

Pro FoV-Änderung
0.1)rXscale=1+cos(0,5*FoV_x) ; (bzw 1+cos(FoV_x), je nach Sicht der Dinge)
0.2)rYscale=1+cos(0,5*FoV_y)
Anmerkung: Ich glaube, der FoV-Winkel, den man an diese nette Hilfsfunktionen übergibt, bezieht sich immer auf die Längere Bildkante, ist also im Normalfall == FoV_x. FoV_y = FoV_x/aspect_ratio, wenn ich mich nicht irre ...

Pro Frame:
0.3)Vektor W_helper berechnen (s.o.)

Pro Objekt:
Test 1: Bleibt
Entfernung1 >= -Radius
Entfernung1 <= Sichtweite+Radius

edit: kleine Optimierung
erst jetzt W ausrechnen: W = O * W_helper (Skalarprodukt)
/edit

Test 2: abs(Entfernung2) < W * (Xmin + R*rXscale)
Test 3: abs(Entfernung3) < W * (Ymin + R*rYscale)

__________
Ich werd's bei Gelegenheit mal penibel testen. Btw könnte man wahrscheinlich auf Far/Near-Culling auf einen einzigen Test reduzieren, wenn man einen Ebene hernimmt, die sich über die aktuelle Z-Achse und den Punkt in der Mitte der sichtbaren Z-Achse definiert ... :|

[Demirug]

Also das mit dem Far/Near Test geht. Die Idee kam mir in dem Moment auch.

[zeckensack]

Ich habe meine kleine Anmerkung zum FoV_x und FoV_y nochmal weiterverfolgt.
In den GLU-Docs steht, daß gluPerspective(...) den übergebenen FoV-Winkel immer für die y-Richtung anwendet. Ok.

Hab ein bisserl Skizze gemacht und gerechnet und dabei ist das rausgekommen:
fov_x=asin(aspect_ratio*sin(fov_y))

[zeckensack]

Ich hab's jetzt am Laufen. Das Verfahren an sich funktioniert, ist sogar noch ein bisserl einfacher geworden.

Ich bastle jetzt noch an einer Demo-Applikation. Sobald ich einen Direktvergleich (performancetechnisch) mit der Kegelmethode und der Sechs-Ebenen-Methode habe und einen brauchbaren visuellen 'Beweis', daß es tatsächlich sauber funktioniert, gibt's eine kleine Demo-App mit Quellcode :)

Auch ein direkter Vergleich der reinen Culling-Performance ohne Animation/Darstellung steht zu erwarten ;)

Falls das eine Rolle spielt, 1024 Partikel ohne Culling 80 fps, mit Culling 255fps, nur Animation (Physik :naughty: ) und Buffer-Clears 700+ fps. Hängt natürlich davon ab, wieviele im Schnitt den Test überleben ...
Hier fehlt mir leider der direkte Vergleich mit den anderen (noch nicht implementierten) Verfahren.

Partikel jeweils 100 Vertices, inkl 1 Hardware-Licht.

Das wird ein Spaß =)

[Demirug]

Ich wollte am Wochende auch ein bischen was coden aber mir ist mein Entwicklungrechner abgeraucht und mit der Maschine die ich jetzt noch zur verfügung habe kann man nicht viel machen.

[zeckensack]

Originally posted by Demirug
Ich wollte am Wochende auch ein bischen was coden aber mir ist mein Entwicklungrechner abgeraucht und mit der Maschine die ich jetzt noch zur verfügung habe kann man nicht viel machen. Schrecklich ... :bawling:
Ich teile deinen Schmerz ;(