Verständnisfrage Frustum Culling

[schneidi74]

Hallo zusammen,

ich habe mal eine kleine Verständnisfrage zum Frustum Culling.

Ich möchte testen ob eine AAB innerhalb des Frustums liegt. Nun habe ich meine Frustum Planes erstellt mit der View*Projektions-Matrix.

Nun beinhaltet meine AAB ja lediglich die minimale und maximale Ausdehnung der Box, und keine Informationen über die Position. Muss ich hier zuerst jede zu testende Box mit der World-Matrix des Mesh transformieren? Ich hab schon diverse Internet-Quellen durch bezüglich dieses Themas, aber so wirklich wurde mir diese Frage nicht beantwortet.

VIelleicht habe ich hier ja mehr Glück ;) ;) ;)

Danke schonmal im voraus!!!

Gruß
Marco

[kimmi]

Da mir gerade die Zeit fehlt, dir genauer zu antworten: Hier ein recht guter Artikel, wo deine Frage hoffentlich beantwortet werden sollte:
http://www.flipcode.com/archives/Frustum_Culling.shtml

Gruß Kimmi

[schneidi74]

Erstmal Danke für die superschnelle Antwort.

Den Bericht kannte ich leider schon. Von der Theorie her hab ich das auch alles verstanden.

Was mir derzeit nur nicht klar ist, was ich mit meinen AAB-Eckpunkten zu machen habe (Transformation oder nicht). Ich habe nämlich niergends einen Source gesehen, wo soetwas gemacht wird, und irgendwie fehlt mir das Verständnis, wie der Test dann funktionieren kann...... :oops:

[Zudomon]

Hallo!

Die Frage ist eigentlich immer, in welchem Space befindest du dich... es gibt ja Textur-, Objekt-, World-, View-, Projectionspace... und bestimmt noch andere, von denen ich nichts ahne ;)

Also deine Daten transformiert sind, also schon im Worldspace vorliegen und dann nur View und Projection draufkommt, dann brauchst du nichts mehr beachten. Falls du aber Instanzen benutzt bzw. die Objekte erstmal über eine Matrix in den Worldspace bringen musst, dann muss davon anschließend die Boundingbox gebildet werden. Die AABB befindet sich also selbst im Worldspace. Vielleicht könntest du auch die Boundingbox deines Objektes berechnen und dann das Kamerafrustum mit der Inversen Objektmatrix transformieren. So würde sich dieses auch im jeweiligen Objektspace befinden und dann könnte auch so das Frustum-Culling klappen.
Du könntest auch noch den Weg gehen, dass die Objekte durch Boundingspheres repräsentiert werden. Das würde ersparen, falls du komplett im Worldspace arbeitest, dass die BoundingBox neu berechnet werden muss, sobald sich das Objekt dreht. Ich hoffe, dass bringt dich schonmal in die richtige Richtung :)

Gruß
Zudo

[schneidi74]

Hallo Zudo,

das hilft mir wirklich schonmal weiter.
Da ich die Vertices nicht transformiert vorliegen habe, also zur Laufzeit transformiere, reicht es da nicht, wenn ich auch die einzelnen Ecken der AAB mit der gleichen Matrix transformiere? Oder kommt da nur Blech bei raus???

Ich denke das Frustum jeweils an mit der inversen Objektmatrix zu transformieren würde die Performance ordentlich in die Knie zwingen, wenn ich das bei jedem Modell mache?!

Die Idee mit der Sphere ist gut, da brauch ich ja lediglich die Position des Modells und den Radius, das werd ich mal testen.

Gruß
Marco

[Zudomon]

Jo, das wäre Blech... weil dann ja nur 2 Vertices transformiert würden. Wenn du das machen wolltest, müsstest du alle 8 Punkte der AABB in den Worldspace bringen und davon wiederrum die Boundingbox/Sphere bilden. Stell dir das mal 2D vor, wenn du zwei Punkte hast. Dann dreh mal nur beide, und dann alle 4 von dem Rechteck.... wenn man davon wieder die AABB bildet, dann ist die mit 2 Punkten wesentlich kleiner geworden.

Also was im Endeffekt schneller ist, kann ich nicht sagen, entweder die Inverse bilden... die kann ja mit gespeichert werden, und dann das Frustum damit multiplizieren, wobei da vorsicht geboten ist. Habe vor ein paar Tagen erfahren müssen, dass so ein Plane transformieren garnicht so einfach ist, da die DirectX Funktion dafür die transponierte inverse Normale haben wollte oder sowas. Bei Interesse schau ich aber gerne nochmal, wie das genauer ging.

Aber ansonsten einfach immer die Boundingbox neu berechnen. So hab ich das bei mir und bisher keine Probleme gehabt. Die kann man ja dann auch speichern, solange das Objekt sich nicht ändert.

[schneidi74]

Aber ansonsten einfach immer die Boundingbox neu berechnen. So hab ich das bei mir und bisher keine Probleme gehabt. Die kann man ja dann auch speichern, solange das Objekt sich nicht ändert.

Hm, ich denke jetzt daran wenn man sehr große Modelle hat, rechnet sich das dann, wenn bei jeder Transformation die AAB neu berechnet wird?

Ansonsten hast du mir heut wirklich sehr weitergeholfen. Ich glaub ich hab jetzt genug Info's um das umsetzen zu können. Vielen Dank dafür schonmal!

[Zudomon]

Also ich hatte bisher da keine Probleme mit. Aber wenn es zu langsam sein sollte, kannst du den besagten Trick benutzen, die Boundingbox des Objektes vorberechnen. Daraus dann jeweils die 8 Vertexe berechnen, alle transformieren und von den 8 die Boundingbox ermitteln. Es ist dann nicht mehr ganz exakt. Aber das fällt eh nicht auf. Man benutzt ja eh eine hierarische Szenenunterteilung. Und da geht es beim Frusting Culling schnell viele Objekte auszuschließen.

Hab gerade mal das Fledermausmodell (54k Vertices) getestet. Die werden transformiert und davon die BoundingBox gebildet. Das ganze benötigt 1,25ms. Ich verwende dazu die Direct3D Funktionen.

[schneidi74]

Das ist schnell, das sollte nicht ins Gewicht fallen...

Vielleicht kannst du mir noch just einen Tipp geben wie du deine Bounding-Sphere erstellst?!? Ich versuche gerade diesen Tipp von Dir umzusetzen. Normal würd ich sagen von den transformierten Vertices das Maximum und Minimum ermitteln um die Mitte und den Radius zu bekommen. Aber mit der Theorie wird mein Modell (eine simple Cube) viel zu früh als nicht sichtbar markiert...

[Zudomon]

Also eigentlich benutze ich in meiner Anwendung derzeit keine Boundingsphere.
Aber ein releativ einfaches Verfahren wäre, wenn du von deinen Vertices die Boundingbox bildest. Davon das Zentrum, also der Mittelwert der beiden AABB-Vertices, bildet das Zentrum der Sphere. Dann durchläufste jeden Punkt und bildest die Länge zwischen Zentrum und Punkt. Die maximalste Länge ist der Radius.

Da kannste noch ein wenig tricksen, indem du statt die Länge, die quadratische Länge berechnest. Wenn alle Punkte durch sind, also du die maximalste quadrierte Länge hast, brauchste dann nur noch die Wurzel ziehen :D

Nun wünsch ich dir viel Spass beim Implementieren :D

[Despotist]

Das mit der Bounding Sphere ist der einfachste und schnellste Test überhaupt und bevor du mit Boxen anfängst solltest du den Sphere Test immer zuerst machen.
Hast du denn nicht den "Mittelpunkt" deines Modells sowieso gespeichert? Ich verstehe nicht warum du den berechnen must. Irgendwie muss doch die Position wo sich das Objekt im Worldspace befindet angegeben werden.

Du erstellst die Bounding Sphere (BS) um das View Frustum (gab dazu mal einen Thread im alten Forum). Und die von deinen Modellen solltest du haben (mittelpunkt + Radius). Speichere die Radien immer im Quadrat da du so das radizieren vermeidest. Dann testest du einfach ob der Abstand der Objekte von der BS des View Frustums kleiner als die Summe der quadratischen Radien ist. Wenn ja kannst du genauere Tests mit den Grenzflächen machen oder sogar Polygonweise wenn du magst. Das ganze eignet sich auch für Kollisionen zwischen Objekten generell.

Despotist