Schnellster Frustum-Culling-Code?

[Asmodeus]

Ich suche nach dem schnellsten Code für das Frustum Culling von Bounding Boxes. Bisher vewende ich die Methode über den Ebenentest.


bool ComputeSurfaceObjectVisibility(float Position[3], float Size[3], const PlaneInfo frustum[6])
{
for(int i = 0; i < 6; i++)
{
if((frustum[i].normal.x * (Position[0] - Size[0]) +
frustum[i].normal.y * (Position[1] - Size[1]) +
frustum[i].normal.z * (Position[2] - Size[2]) +
frustum[i].d) > 0)
continue;

if((frustum[i].normal.x * (Position[0] + Size[0]) +
frustum[i].normal.y * (Position[1] - Size[1]) +
frustum[i].normal.z * (Position[2] - Size[2]) +
frustum[i].d) > 0)
continue;

if((frustum[i].normal.x * (Position[0] - Size[0]) +
frustum[i].normal.y * (Position[1] + Size[1]) +
frustum[i].normal.z * (Position[2] - Size[2]) +
frustum[i].d) > 0)
continue;

if((frustum[i].normal.x * (Position[0] + Size[0]) +
frustum[i].normal.y * (Position[1] + Size[1]) +
frustum[i].normal.z * (Position[2] - Size[2]) +
frustum[i].d) > 0)
continue;

if((frustum[i].normal.x * (Position[0] - Size[0]) +
frustum[i].normal.y * (Position[1] - Size[1]) +
frustum[i].normal.z * (Position[2] + Size[2]) +
frustum[i].d) > 0)
continue;

if((frustum[i].normal.x * (Position[0] + Size[0]) +
frustum[i].normal.y * (Position[1] - Size[1]) +
frustum[i].normal.z * (Position[2] + Size[2]) +
frustum[i].d) > 0)
continue;

if((frustum[i].normal.x * (Position[0] - Size[0]) +
frustum[i].normal.y * (Position[1] + Size[1]) +
frustum[i].normal.z * (Position[2] + Size[2]) +
frustum[i].d) > 0)
continue;

if((frustum[i].normal.x * (Position[0] + Size[0]) +
frustum[i].normal.y * (Position[1] + Size[1]) +
frustum[i].normal.z * (Position[2] + Size[2]) +
frustum[i].d) > 0)
continue;

return false;
}

return true;
}


Meine Frage ist nun, gibt es noch eine schnellere Methode?

Gruss, Carsten.

[Chris Lux]

schau mal hier unter punkt 2.4:
http://www.cg.tuwien.ac.at/studentwork/CESCG/CESCG-2002/DSykoraJJelinek/

sowas mit der LUT für AA bounding boxen habe ich mal implementiert und das funktioniert wirklich sehr fix, da man auch nur 2 vertices testen muss. jedoch funktioniert das nur für AABBs, was man ja einrichten kann ;)

HTH

edit: hier noch als pdf http://www.ce.chalmers.se/old/staff/uffe/Vfc_Bbox.pdf

[Corrail]

Ich habe mich mit Frustum Culling noch nicht beschäftigt, aber wäre es nicht einfacher sich eine Matrix zu dem Frustum zu basteln, die Objekte mit dieser Matrix zu multiplizieren und dann das ganze gegen den Unit-Cube zu testen?

[Chris Lux]

Ich habe mich mit Frustum Culling noch nicht beschäftigt, aber wäre es nicht einfacher sich eine Matrix zu dem Frustum zu basteln, die Objekte mit dieser Matrix zu multiplizieren und dann das ganze gegen den Unit-Cube zu testen?

glaub nicht, da man so die ganzen transformationen per cpu erledigen muss. es ist viel einfacher die, möglicherweise hierachisch angeordneten, AABBs zu transformieren oder zu bestimmen und dann eben nur gegen die 6 ebenen des frustums zu testen. diese ebenen lassen sich ganz einfach aus der viewproj matrix bestimmen. mit oben genanntem algorithmus muss man so auch nur maximal zwei vertices testen, was den rechenaufwand somit auch minimiert.

ich für meinen teil war und bin noch sehr überzeugt von diesem algorithmus.

1. AABB holen/bestimmen
2. per LUT mit dem vorzeichen der ebenennormalen die beiden zu testenden vertices der AABB bestimmen (nahester und am weitesten entvertester).
3. beide gegen ebene testen.
4. fertig ;)

[Einfachkrank]

Ich weiß zwar nicht obs schneller ist, aber funktioniert auch :)

http://www.gametutorials.com/Tutorials/opengl/OpenGL_Pg5.htm

Da blätter mal nach unten, da ist dann en Quellcode Download für Frustum Culling...

[BinVadim]

... ich hätte an deiner Stelle Zeiger als Parameter an diese Funktion übergeben.

Also nicht:

bool ComputeSurfaceObjectVisibility(float Position[3], float Size[3], const PlaneInfo frustum[6])

sondern:

bool ComputeSurfaceObjectVisibility(float Position[], float Size[], const PlaneInfo frustum[])

und Aufruf z.B.:

float Position[3];
float Size[3];
PlaneInfo frustum[6];
ComputeSurfaceObjectVisibility(Position, Size, frustum);

geht viel schneller ... glaub mir.

... in deinem Fall muss deine Funktion kopien von diesen Arrays machen was zusätzliche Rechnerleistung braucht.

[micki]

das schnellste ist immer das was man nicht durchführen muss :)

also bevor es zum frustumtest kommt, erstmal ein bounding volume um das frustum (z.b. eine AABB oder BoundingSphere) und aus der ganzen hierarchy dagegen testen. das bissl was dann übrig bleibt dann erst gegen das frustum testen, bei grossen scenen ist das wohl das fixeste.

MfG
micki

[Xmas]

... ich hätte an deiner Stelle Zeiger als Parameter an diese Funktion übergeben.

Also nicht:

bool ComputeSurfaceObjectVisibility(float Position[3], float Size[3], const PlaneInfo frustum[6])

sondern:

bool ComputeSurfaceObjectVisibility(float Position[], float Size[], const PlaneInfo frustum[])
Falls das C++ sein soll, liegst du falsch. Es ist unerheblich ob da Größen für die Arrays angibst, Arrays werden in C++ immer als Pointer übergeben.

[BinVadim]

Falls das C++ sein soll, liegst du falsch. Es ist unerheblich ob da Größen für die Arrays angibst, Arrays werden in C++ immer als Pointer übergeben.

ich gehe davon aus dass es C ist, da die Funktion oben wurde nicht als Methode geschrieben.

[Asmodeus]

Erstmal Danke an alle für die Ratschläge. Ich werd sehen, was ich davon wie verwenden werde, um ein optimales Ergebnis zu erreichen.

@BinVadim:

Es ist tatsächlich C++, habe CLASS:: nur weggelassen, damit die Codezeile nicht noch länger wird.

@all:

Allgemein finde ich beim Frustum Culling problematisch, Aussagen darüber machen zu können, bis zu welchem Grad es überhaupt sinnvoll ist Frustum Culling anzuwenden. Bisher läuft es bei mir so, ich führe den Test für meine Quadtreestruktur des Terrains aus. Für die sichtbaren Quads wird dann der Test hierarchisch für alle Pflanzenmodelle ausgeführt, die auf dem jeweiligen Quad stehen. Und nun stellt sich mir die Frage, ob man eine Aussage darüber treffen kann (vielleicht gibt es ne Heuristik darüber), ab welcher geringen Anzahl von Dreiecken pro Objekt (z.B. Grashalme) ein Verwerfen der Geometrie durch die Grafikkarte schneller ist, also ein Frustum Culling durch die CPU.

Gruss, Carsten.

[Xmas]

ich gehe davon aus dass es C ist, da die Funktion oben wurde nicht als Methode geschrieben.
Es gibt kein "bool" in C ;)
Und dass Arrays immer als Pointer übergeben werden, ist AFAIK auch in C so.