Hallo allerseits,
Ich habe mir das Tutorial für das Frustum Culling (http://wiki.delphigl.com/index.php/Tuto ... um_Culling) durchgelesen und kam auf die Idee, dass es eventuell ein effizenteres Verfahren geben müsste um das auszurechnen. Mit einem Freund kam ich auf folgenden Idee (wenns dass schon längst gibt, bitte sagen):

Ich führe das Ganze mal nur theoretisch durch, da mir noch ein paar Kenntnisse zum Thema OpenGL dazu fehlen.

Also wir berechnen aus der OpenGL Matrix, welche unsere Sicht speichert, den Vektor mit dem man schaut. Danach berechnen wir eine Ebene die X Einheiten von dem Betrachter entfernt ist und orthogonal zu dem Sichtvektor verläuft.
X entspricht dabei dem Farclipping vom Sichtfeld.

Um zu überprüfen ob ein Objekt im Sichtfeld liegt, berechnen wir den Schnittpunkt von einer Geraden durch diesen Punkt und unserer Sichtfeldebene. Die Gerade sollte in folgender Form vorliegen.

vektor zum Betrachter + r * (Vektor vom Betrachter zum Objekt welches wir überprüfen wollen);
Wenn r für den Schnittpunkt kleiner 0 ist, wissen wir, dass das Objekt hinter dem Spieler liegt, also nicht gezeichnet werden muss.

Hier mal ein 2D Bild zur verdeutlichung:

Das X in der Mitte markiert den Betrachter und die hellblaue Linie unsere Ebene (hier eine Linie weil 2D).

Objekt 1 liegt in unserem Sichtfeld dafür wäre r ein Wert größer als 1, da man den Richtungsvektor mehr als einmal braucht um die Ebene zu erreichen.
Objekt 2 liegt hinter unserem Sichtfeld dafür wäre r ein Wert kleiner 1, da die Ebene vor dem Objekt liegt.
Objekt 3 erhält fpr r einen negativen Wert und liegt deshalb hinter unserem Betrachter.

Somit könnte man mit einer Überprüfung

einen Großteil der Objekte bereits ausschliessen. Hiermit habe ich nämlich die Überprüfung ob es hinter dem Nutzer oder hinter der Clipping Plane bereits beides miteinbezogen.

Wenn r dem gewünschten Wert entspricht, dann muss man nur noch rausfinden, wo der Schnittpunkt mit der Ebene liegt. Nehmen wir als Beispiel das der Winkel zwischen dem Sichtvektor und dem in der 2D Darstellung oberen Sichtbegrenzungsvektor 45° (obere blaue Linie) beträgt, dann müsste man nur noch rausfinden ob die Distanz zwischen dem Schnittpunkt Objektgerade mit Ebene (in der 2D Dartstellung das grüne X) und Schnittpunkt Sichtvektor Ebene kleiner ist als die Länge des Sichtvektors.

Bei einem anderen FOV müsste man dies entsprechend mit sin/cos korrigieren, aber diese Rechnung würde nur einmal am Anfang anfallen.

Um rauszufinden ob eine Kugel im Sichtfeld liegt, muss man lediglich das gefundene r * Kugelgröße als Erweiterung des Sichtfelds nehmen. Im Code sähe das so aus:

Weil je näher das Objekt am Betrachter liegt, desto größer muss ich die Toleranz-Grenze wählen an der es abgeschnitten wird.

Eine Schwierigkeit würde momentan noch darstellen, was passiert wenn man das Sichtfeld an der eigene Achse dreht, weil sich dadurch die Rechnung für X- und Y-Distanz verändern müsste.

----------

Ich fände es toll, wenn ihr mir sagt was ihr davon haltet.

Hey,

man kann das sicher so machen wie du das vorschlägst. Also ausgehend vom Betrachter die Vektoren bzw. Strahlen berechnen und prüfen ob sie im Frustum liegen. Bei RayTracing-Systemen würde sich das vlt sogar eher anbieten als bei "normalen" OpenGL Anwendungen. Aber ich denke nicht, das es schneller ist als die Methode im Tutorial, da muss ich für einen Punkt nur 6 Skalrprodukte berechnen, das geht sehr fix. Bei deiner Methode müsste man ggf. ein Gleichungssystem lösen und das ist definitiv aufwendiger.
Du hast allerdings einen sehr Großen Denkfehler in deiner Rechnung. Wenn du den Vektor vom Betrachter zum Objekt bestimmtst, dann ist r immer 1!

MfG Bergmann.

_________________
Aktuelle Projekte: BumpMapGenerator, Massive Universe Online
Auf meiner Homepage gibt auch noch paar Projekte und Infos von mir.

Richtig, das im Tutorial beschriebene Verfahren hat etwa den Vorteil das du nicht nur gegen Punkte bei gleichem Aufwand auch gegen eine Kugel testen kannst. D.h. du umschließt dein Objekt mit einer BoundingSphere und kannst so extrem flott testen das Objekt sichtbar ist oder nicht. Auch ein Quader (AxisAlignedBoundingBox) lässt sich ziemlich schnell testen (der Code aus dem Tutorial sieht mir unnötig komplex aus, geht viel einfacher, siehe Code unten), das geht mit deinem Verfahren nicht so schön.

Aber es ist natürlich löblich das du die Gedanken dazu machst und nicht alles als gegeben hinnimmst was man dir vorwirft

_________________
Yeah!

Danke schonmal für die Antworten.
Das das Verfahren wahrscheinlich nicht so effizent ist wie das im Tutorial hielt ich irgendwie auch schon für wahrscheinlicher als die Möglichkeit, dass ich als Erster auf eine neue Technik komme.
Ich kam nur auf die Idee, weil ja soweit ich weis Überprüfung im Vergleich zu Berechnungen lange dauern. Und bei meiner Methode spart man an Überprüfungen muss aber deutlich mehr (zu viel) ausrechnen.

Einen Versuchs wars wert. xD


Danke.

Üblicherweise macht man gar nicht sooo viele einzelne Tests ob Objekte im Frustum liegen oder nicht. Ich weiß nicht ob das im Tutorial steht oder nicht, aber zumindest die statischen (=unbeweglichen) Objekte in deiner Szene kannst du in eine Baum-Struktur aus BoundingBoxen einsortieren. Stichworte: BSP-Tree, Quad-Tree, Oct-Tree

Die Grundidee ist einfach das du mehrere Objekte in einer BoundingBox zusammenfasst. Also einfach Minimum und Maximum aller Vertexpositionen in allen drei Dimensionen berechnen. Die BoundingBoxen kannst du weiter zusammenfassen und erhälst größere BoundingBoxen die du noch weiter zusammenfasst.
Ist nun eine BoundingBox nicht im Frustum, kannst du mit einem schlag sämtliche enthaltenen Objekte mit einem Schlag ausschließen. Das sind verdammt viele, denn üblciherweise ist ja nur ein kleiner Teil der Szene sichtbar. Ist die Box dagegen ganz oder teilweise innerhalb des Frustums steigst du in diese Box hinein und testest alle enthaltenen BoundingBoxen. Ist davon wieder eine sichtbar steigst du dort hinein usw....

_________________
Yeah!

Hey,

warum nur die statischen? Das geht mit dynamischen genau so gut. Ist nur die Frage, wie schnell das ganze ist. Gansu das ist das Thema meiner Bachelorarbeit, die ich demnächst beginnen werde. N kleiner Performancetest wird auch dabei sein. Ich werd die (wenn sie dann einmal fertig ist) auch hier im Forum publizieren (denke ich). Also wenn euch das Thema wirklich interessiert, dann bekommt ihr da auch noch was zu lesen ^^

MfG Bergmann

_________________
Aktuelle Projekte: BumpMapGenerator, Massive Universe Online
Auf meiner Homepage gibt auch noch paar Projekte und Infos von mir.

Vorweg: Mit dynamischen Objekten meine ich hier Objekte die sich wirklich größere Strecken bewegen so es ernsthafte Auswirkungen auf das Frustum-Culling hat.

Wenn sich ein Objekt bewegt musst du es sowieso anfassen. In der Zeit wo du es neu in den Baum einsortierst kannst du es auch einfach gegen den Frustum testen.

Natürlich kannst man sich Baumstrukturen ausdenken in denen man ein Objekt verschieben kann (statt löschen und neu einfügen). Objekte bewegen sich ja üblicherweise nicht in einem Frame über die komplette Karte, also ggf. aktualisiert man auch die Position im Baum nur einmal pro Sekunde, etc. Aber wenn es nur um einen simplen Frustum-Test geht ist der Nutzen gegenüber Fehleranfälligkeit/Implementierungsaufwand gering. Manchmal die einfachere Lösung die bessere, gerade für Hobby-Entwickler.

Wenn du den Baum für mehr brauchst als einen einzelnen Frustum-Test sieht die Sache natürlich anders aus. Wenn etwa die Szene aus etlichen Perspektiven gerendert wird, du Ray-Tracing oder Objekt-Objekt-Interaktion machst. Sinnvoll wird es auch wenn sich Objekte etwa nur in Nähe des Spielers dynamisch verhalten.

_________________
Yeah!