Kamerafrustumplanes berechnen

[Andre]

Hi, ich habe auch mal wieder eine Frage.

Seit ein paar Stunden sitze ich jetzt schon am Frustum Culling für mein Spiel. Eigentlich kein Problem, hatte ich gedacht, da ich einfach alten Code wiederverwenden konnte.
Zwar musste ich von D3DX auf DirectXMath umstellen, und außerdem will die neue Engine die Matrizen transponiert haben, aber das sollte ja alles kein Problem sein, oder?

Nun, anscheinend schon. Ich weiß nicht genau was falsch läuft, ich habe aber die Frustum Planes unter Verdacht. Ich bin mir nämlich immer noch ziemlich unsicher wann ich welche Matrix transponieren muss und in welcher reihen folge diese dann zusammen multipliziert werden müssen um zum richtigen Ergebnis zu kommen.

Hier ist mein alter, funktionierender, Code:

Code: Alles auswählen

void WCamera::BuildFrustumPlanes()
{
	D3DXMATRIX viewProjection;
    D3DXMatrixMultiply( &viewProjection, ViewMatrix, ProjMatrix );

    // Left plane
    FrustumPlanes[0].a = viewProjection._14 + viewProjection._11;
    FrustumPlanes[0].b = viewProjection._24 + viewProjection._21;
    FrustumPlanes[0].c = viewProjection._34 + viewProjection._31;
    FrustumPlanes[0].d = viewProjection._44 + viewProjection._41;

    // Right plane
    FrustumPlanes[1].a = viewProjection._14 - viewProjection._11;
    FrustumPlanes[1].b = viewProjection._24 - viewProjection._21;
    FrustumPlanes[1].c = viewProjection._34 - viewProjection._31;
    FrustumPlanes[1].d = viewProjection._44 - viewProjection._41;

    // Top plane
    FrustumPlanes[2].a = viewProjection._14 - viewProjection._12;
    FrustumPlanes[2].b = viewProjection._24 - viewProjection._22;
    FrustumPlanes[2].c = viewProjection._34 - viewProjection._32;
    FrustumPlanes[2].d = viewProjection._44 - viewProjection._42;

    // Bottom plane
    FrustumPlanes[3].a = viewProjection._14 + viewProjection._12;
    FrustumPlanes[3].b = viewProjection._24 + viewProjection._22;
    FrustumPlanes[3].c = viewProjection._34 + viewProjection._32;
    FrustumPlanes[3].d = viewProjection._44 + viewProjection._42;

    // Near plane
    FrustumPlanes[4].a = viewProjection._13;
    FrustumPlanes[4].b = viewProjection._23;
    FrustumPlanes[4].c = viewProjection._33;
    FrustumPlanes[4].d = viewProjection._43;

    // Far plane
    FrustumPlanes[5].a = viewProjection._14 - viewProjection._13;
    FrustumPlanes[5].b = viewProjection._24 - viewProjection._23;
    FrustumPlanes[5].c = viewProjection._34 - viewProjection._33;
    FrustumPlanes[5].d = viewProjection._44 - viewProjection._43;

    // Normalize planes
    for ( int i = 0; i < 6; i++ )
    {
        D3DXPlaneNormalize( &FrustumPlanes[i], &FrustumPlanes[i] );
    }
}

Und hier die neue Version:

Code: Alles auswählen

void BaseCamera::BuildFrustumPlanes(const XMFLOAT4X4& proj)
{
	XMMATRIX mViewMatrix = XMLoadFloat4x4( &ViewMatrix );
	XMMATRIX mProjMatrix = XMLoadFloat4x4( &proj );

	XMMATRIX mViewProjection = XMMatrixTranspose( XMMatrixMultiply(mProjMatrix, mViewMatrix) );

    XMFLOAT4X4 viewProjection; XMStoreFloat4x4(&viewProjection, mViewProjection);

    // Left plane
    FrustumPlanes[0].x = viewProjection._14 + viewProjection._11;
    FrustumPlanes[0].y = viewProjection._24 + viewProjection._21;
    FrustumPlanes[0].z = viewProjection._34 + viewProjection._31;
    FrustumPlanes[0].w = viewProjection._44 + viewProjection._41;

    // Right plane
    FrustumPlanes[1].x = viewProjection._14 - viewProjection._11;
    FrustumPlanes[1].y = viewProjection._24 - viewProjection._21;
    FrustumPlanes[1].z = viewProjection._34 - viewProjection._31;
    FrustumPlanes[1].w = viewProjection._44 - viewProjection._41;

    // Top plane
    FrustumPlanes[2].x = viewProjection._14 - viewProjection._12;
    FrustumPlanes[2].y = viewProjection._24 - viewProjection._22;
    FrustumPlanes[2].z = viewProjection._34 - viewProjection._32;
    FrustumPlanes[2].w = viewProjection._44 - viewProjection._42;

    // Bottom plane
    FrustumPlanes[3].x = viewProjection._14 + viewProjection._12;
    FrustumPlanes[3].y = viewProjection._24 + viewProjection._22;
    FrustumPlanes[3].z = viewProjection._34 + viewProjection._32;
    FrustumPlanes[3].w = viewProjection._44 + viewProjection._42;

    // Near plane
    FrustumPlanes[4].x = viewProjection._13;
    FrustumPlanes[4].y = viewProjection._23;
    FrustumPlanes[4].z = viewProjection._33;
    FrustumPlanes[4].w = viewProjection._43;

    // Far plane
    FrustumPlanes[5].x = viewProjection._14 - viewProjection._13;
    FrustumPlanes[5].y = viewProjection._24 - viewProjection._23;
    FrustumPlanes[5].z = viewProjection._34 - viewProjection._33;
    FrustumPlanes[5].w = viewProjection._44 - viewProjection._43;

    // Normalize planes
    for ( int i = 0; i < 6; i++ )
    {
		XMStoreFloat4( &FrustumPlanes[i], XMPlaneNormalize( XMLoadFloat4(&FrustumPlanes[i]) ));	
    }
}

Ich hab leider auch keine gute Idee wie ich jetzt schnell mal überprüfen könnte ob die Planes stimmen.

Hier ist noch die Funktion, welche überprüft ob ein Objekt im Frustum liegt:

Code: Alles auswählen

/** Checks if the component is visible from our POV */
bool WorldObject::CheckVisibility(const XMFLOAT4* frustumPlanes)
{
	float rad = GetObjectRadius();

	if(rad > 0.0001f) // Only cull things with a radius
	{

		XMFLOAT3 mid = GetTrueObjectMid();

		// Frustum Culling with Caching
		if(FrustumCullPlaneCache != -1 )
		{
			if ( XMVectorGetX( XMPlaneDotCoord( XMLoadFloat4( &frustumPlanes[FrustumCullPlaneCache]), XMLoadFloat3(&mid) ) ) + rad < 0 )
			{
				// Outside the frustum, reject it. No need to alter the cache!
				return false;
			}
		}

		for(int i=0; i < 6; i++)
		{
			if ( XMVectorGetX( XMPlaneDotCoord( XMLoadFloat4( &frustumPlanes[i]), XMLoadFloat3(&mid) ) ) + rad < 0 )
			{
				// Outside the frustum, reject it and set cache!
				FrustumCullPlaneCache = i;
				return false;
			}
		}

		// Wasn't frustumculled, reset cache
		FrustumCullPlaneCache = -1;
	}

	return true;

}

[RazorX]

Wenn du doch eh schon bei DirectXMath bist, dann nutz doch einfach DirectXCollision. Da gibt es die Klasse BoundingFrustum die eine Methode zur Extraktion bereitstellt (leider nur für LH Matrizen, RH Konstruktion muss per Hand vorgenommen werden). Außerdem könnteste die Klassen aus dem Framework direkt mit SSE Optimierungen nutzen.

http://msdn.microsoft.com/de-de/library ... s.85).aspx

[Andre]

Meine Matrizen sind leider RH. Aber gut, dass du mich daran erinnerst, hatte das total vergessen. Deswegen funktioniert es wohl auch nicht. Du meinst also ich müsse das ganze von Hand ausrechnen? Was verändert sich denn dann?

[Niki]

Schwierig den Fehler so zu finden. Kannst du so ungefähr formulieren was nicht zu klappen scheint? Macht die Near Plane Probleme?

Und wie sieht der Code aus, der die Projektionsmatrix erstellt?

Was bedeutet "die neue Engine"? Heißt das, dass die Engine nicht von dir selbst ist? Du sagst sie will transponierte Matrizen haben. Sind die Input-Matrizen proj und ViewMatrix bereits transponierte RH-Matrizen?

[Andre]

Naja, das culling scheint völlig willkürlich zu sein.

Hier ist der Code der Proj-Matrix:

Code: Alles auswählen

XMStoreFloat4x4(&Projection, XMMatrixTranspose(XMMatrixPerspectiveFovRH(65 * XM_PI / 180.0f, Global::ScreenResolution.x/Global::ScreenResolution.y, 0.50f, 10000.0f)));

Und "neue Engine" bedeutet nur, dass ich für unser neues Projekt von vorne angefangen habe, da es ein Windows 8 App wird und ich sowieso DirectXMath lernen wollte.

Jetzt wo du mich auch noch fragst ob die schon transponiert sind... ja, sind sie. Eigentlich sollten die nur vor dem einspeisen in die Shader transponiert werden, oder? Dem C++ Teil sollte das wohl recht egal sein dürfen, nicht wahr?

[Niki]

Also... angenommen das Du XMMatrixPerspective*RH nimmst, und angenommen das proj und ViewMatrix von vornherein transponiert sind, dann scheint mir der Extrahierungs-Code korrekt zu sein.

Dabei gehe ich jetzt einfach mal davon aus, dass sowohl die "neue Engine" als auch XMMatrixPerspective*RH die alten Direct3D Ungleichungen für den homogenen Clipping-Raum benutzen.

Diese Antwort ist allerdings mit etwas Vorsicht zu genießen. Ich mag zwar einer der beiden Autoren des Extraction Papers sein, aber nach 12 Jahren fängt da auch bei mir das Hirn an zu braten.

[Niki]

Jetzt wo du mich auch noch fragst ob die schon transponiert sind... ja, sind sie. Eigentlich sollten die nur vor dem einspeisen in die Shader transponiert werden, oder? Dem C++ Teil sollte das wohl recht egal sein dürfen, nicht wahr?

Ja, ich persönlich finde es schöner erst beim Einspeisen in den Shader zu transponieren. Das macht die Rechnerei weniger konfus.

Kannst du bei dir bitte mal die Near-und Far-Planes beim Culling deaktivieren? Mich würde interessieren ob der Rest dann passt. Ich bin jetzt schon völlig verwirrt, und die DirectXMath-Hilfe ist unter aller....

[RazorX]

Meine Matrizen sind leider RH. Aber gut, dass du mich daran erinnerst, hatte das total vergessen. Deswegen funktioniert es wohl auch nicht. Du meinst also ich müsse das ganze von Hand ausrechnen? Was verändert sich denn dann?

Ich verweise hierfür einfach mal auf einen MSDN Thread:
http://social.msdn.microsoft.com/Forums ... c450646833

[Andre]

Hab beide beim culling ausgelassen, aber klappen tut es immer noch nicht. Es ist vielmehr so, dass, fast alles ausgeblendet wird wenn ich mich über einen bestimmten Punkt drehe. Und erst nach einer fast 180° Wende wird alles wieder eingeblendet.

Ich verweise hierfür einfach mal auf einen MSDN Thread:
http://social.msdn.microsoft.com/Forums ... c450646833

Da steht nur, dass die Funktionen nicht mit RH-Matrizen funktionieren, oder? Und das aus dem ersten Posting hat ebenfalls bei mir nicht funktioniert.

[Niki]

Also, ich komme so auch nicht dahinter. Ich habe zwar die Vermutung, dass die Z-Komponenten falsch sind, aber das ist nur eine Vermutung. Ich müsste schon eine Demo-App schreiben um das hinzukriegen, denn sonst bin auch ich nur am Raten.

Aber ich kann dir zumindest sagen wie ich das oft visuell überprüft habe. Ich mache mir eine Culling-Routine die 3 States zurückgibt. Diese sind (1) komplett im Frustum, (2) schneidet den Frustum, und (3) komplett außerhalb des Frustums. Je nach State färbe ich dann die Objekte ein. Am besten funzt das mit einer einfachen Ebene aus Quads, und dann AABB Culling benutzen.

[Andre]

So, im Moment sieht es eher so aus als würden sich die Planes um den Ursprung der Scene bauen und sich mit der Kamera mitdrehen. Ist man dann mit der Kameraposition aus dem Frustum raus so wird wieder fast gar nichts angezeigt.

[Niki]

Also, ich mache dir 'nen Vorschlag. Wenn du's morgen Abend immer noch nicht am Rennen hast, dann mache ich hier eine D3D11 Demo, für RH und LH. Ich muss das ganz einfach selbst sehen und machen können. Erwarte dann aber bitte keinen sauberen Code. Ich würde das halt hinhacken (mit Ausnahme der Plane Extraction). Samstag morgen sollte das wohl fertig sein.

Nur tu mir bitte einen Gefallen. Falls du das nicht haben willst, oder falls du dich für was anderes entscheiden solltest, dann sag mir das bitte hier im Forum vor morgen Abend, denn ich will das ungern für nichts und wieder nichts tun.

[Andre]

Hmm, das wäre sehr nett. Das mag ich fast gar nicht annehmen... :D Aber ich schaue trotzdem natürlich lieber erstmal ob ich das nicht doch selbst hinbekomme. Dann musst du dir keine Arbeit machen.

[Niki]

Das mag ich fast gar nicht annehmen... :D

Die Panik kann ich dir nehmen, und zwar aus folgendem Grund. Damals habe ich eine AABB Culling Demo in D3D7 geschrieben, die auch verteilt wurde. Da war mir aber ein Fehler mit der Near-Plane unterlaufen, weshalb ziemlich viele Leute einen falschen Extraction Code hatten. Diesen Fehler finde ich heute immer noch, z.B. hier, in Zerbie's Tutorials: http://old.zfx.info/Tutorials.php?ID=10

Seit dem empfinde ich bei dem ganzen Thema eine gewisse Verpflichting :D Das Resultat ist, dass ich mich mit Gil Gribb zusammengetan habe, die Formeln hergeleitet habe, und dieses Paper geschrieben habe. Manchmal verfluche ich diesen Fehler heute noch. Der kann einen echt für Jahre beschäftigen, denn dieser Algorithmus hat verflixt viel Einsatz gefunden.

Sag mir also bis morgen Abend Bescheid, wenn's nicht geht :)

[Alexander Kornrumpf]

Aus dem Tutorial:

Referenz: Der folgenden Code stammt aus einem Tutorial von Gary Simmons, der jedoch darauf hinwies dass Klaus Hartmann ihm diesen Code erläutert hat und dass jemand namens Gil Gribb letztenendes dafür die Lorbeeren verdient :-)

Bist du eine der genannten Personen?

[Niki]

Bist du eine der genannten Personen?

Klaus Hartmann. Niki ist mein Spitzname.

[Alexander Kornrumpf]

Wie cool. Irgendwann in der Steinzeit vor dem Studium und bevor ich wusste was eine Ebenengleichung ist, hab ich auch mal versucht das Paper zu implementieren. Oh the memories :)

[Niki]

@Schrompf, da du ja eh immer alles mitliest... hast du die Möglichkeit das Tutorial zu korrigieren? Zerbie habe ich erst einmal gesehen seit ich wieder hier bin.

Code: Alles auswählen

   // Nahe Clipping Plane
    VFrustrum[VF_N].vNormal.x = -matViewProj._13;
    VFrustrum[VF_N].vNormal.y = -matViewProj._23;
    VFrustrum[VF_N].vNormal.z = -matViewProj._33;
    VFrustrum[VF_N].fDistanz  = -matViewProj._43;

[Alexander Kornrumpf]

Im Zweifel mal den Seraph anschreiben.

[Andre]

Ich habs jetzt soweit hinbekommen, dass das Frustum richtig aussieht (Habs doch gezeichnet bekommen, dank dem BoundingFrustum-Interface aus DirectXCollision), aber die Farplane viel zu nah dran ist. Und obwohl der Check aus ist wird immernoch das meißte nicht gezeichnet.

Edit: Ah, es ist im moment so, dass die Nearplane viel zu nah an der Kamera ist und die Farplane genau auf der Nearplane liegt.

[Niki]

Glückwunsch! Hast du jetzt also die Extraction weggeworfen, oder habe ich das falsch verstanden? Ich benutze die momentan auch nicht, da ich gerne die 8 Eckpunkte des Frustums zur Verfügung habe. Geht natürlich auch mit Ebenen schneiden, aber muss ja nicht. Auf Extraction gehe ich erst zurück falls ich Culling im Object Space haben will.

[Andre]

Ich habe den Code von hier mal getestet: http://social.msdn.microsoft.com/Forums ... c450646833
Und der gibt mir auch ein gutes Frustum aus, bis auf das was ich eben noch in meinem Post über dir reineditiert habe... aber das sollte ja eigentlich egal sein, da ich die checks mit Planes mache. Naja, bestimmt reichts aus die Normalen zu invertieren wenn ich so drüber nachdenke.

[Andre]

So, Normalen invertieren, UND WorldPos der Objekte auch berücksichtigen habens jetzt gebracht. :roll:

Funktioniert, bis auf, dass die Near- und Farplanes nicht richtig sind, aber das ist in meinem Fall egal. :)

[dot]

Bringen wir mal ein wenig Ordnung in die Sache. Wofür genau das Transponieren? Betrachtest du Vektoren als Zeilen oder als Spalten? Wegen der Plane Extraction schau mal hier: http://www.cs.otago.ac.nz/postgrads/ale ... action.pdf, Handedness sollte da imo keine Rolle spielen.
Wenn du nur die Eckpunkte des Frustum brauchst, kannst du auch einfach die Ecken des Frustum in Normalized Device Coords (also die Punkte (-1, -1, -1) etc.) durch die inverse ViewProjection schicken.

[Niki]

Wenn das erwünscht ist, dann kann ich das PDF heute Abend auch mal ganz offiziell in der Rubrik "Artikel, Tutorials und Materialen" als Dateianhang hochladen. Ich weiß aber nicht, ob diese Dateianhänge eine begrenzte Lebensdauer haben.

[Artificial Mind]

Bringen wir mal ein wenig Ordnung in die Sache. Wofür genau das Transponieren? Betrachtest du Vektoren als Zeilen oder als Spalten? Wegen der Plane Extraction schau mal hier: http://www.cs.otago.ac.nz/postgrads/ale ... action.pdf, Handedness sollte da imo keine Rolle spielen.
Wenn du nur die Eckpunkte des Frustum brauchst, kannst du auch einfach die Ecken des Frustum in Normalized Device Coords (also die Punkte (-1, -1, -1) etc.) durch die inverse ViewProjection schicken.

Nur mal so als kleiner Tipp am Rande fürs Implementieren: Niemals die inverse ViewProjection nutzen.
Die wird schon bei Koordinaten im dreistelligen Bereich instabil.
Lieber folgenden Pseudocode nutzen:

Code: Alles auswählen

vec4 screenPos = ...;
vec4 eyePos = inverseProjection * screenPos;
eyePos /= eyePos.w;
vec4 worldPos = inverseView * eyePos;

Das ist wesentlich stabiler (am eigenen Leib erlebt) ;)

[Andre]

Bringen wir mal ein wenig Ordnung in die Sache. Wofür genau das Transponieren?

Das kommt noch von den Anfangszeiten dieses Projektes, wo ich noch nicht genau verstanden hatte was das Transponieren überhaupt macht. Das Transponieren soll die Matrizen anscheinend GPU-Freundlicher machen, auf jeden Fall ging es ohne nicht und ich wusste zu der Zeit auch nicht genau wieso, da ich auf ein wenig Samplecode aufgebaut habe.
Also hab ich einfach jede Matrix direkt nach dem erstellen Transponiert, also World-, View-, und Projection, da ich auf der CPU Seite noch nicht groß damit rechnen musste.

Jetzt bin ich aber um einiges Schlauer und weiß, dass es sehr viel günstiger und übersichtlicher ist dies nur beim eingeben in die Shader zu machen.

Und danke für den Tipp mit der invViewProj, ich werds mir merken!

[dot]

Das Transponieren ist nur notwendig, da die D3DX Matritzen nicht mit dem standardmäßig von HLSL angenommenen Speicherlayout übereinstimmen. Sofern du dich an die von D3DX vorgegebenen Konventionen hältst (Vektoren sind Zeilen, mathematisch gesehen zwar Schwachsinn, aber so ist es nunmal in D3DX), gibt es keinen mathematischen Grund dafür und der einzige richtige Zeitpunkt dafür ist, vor der Übergabe an den Shader. Mit den transponierten Matritzen auch nur irgendwas zu rechnen wäre schlichtweg falsch.

(Zumindest im Allgemeinen, natürlich kann man unter Umständen Dinge so umformulieren, dass man direkt mit transponierten Werten rechnen kann und das transponierte Ergebnis erhält, sodass man sich evtl. ein paar Mal unnötiges Transponieren spart, aber dann könnte man auch gleich eine anständige Mathelibrary verwenden und sich derartige Kunststücke von vorn herein ganz sparen...)

[Andre]

Ich benutze allerdings DirectXMath. Bei D3DX mit Direct3D11 war Transpornieren auch nicht notwendig.

[dot]

Transponieren ist nur notwendig, wenn das Speicherlayout der Matritzen auf CPU Seite nicht mit dem von den Shadern erwarteten Layout übereinstimmt. Das Layout lässt sich z.B. beim HLSL Compiler global über Flags und auch im Code über Keywords steuern, Stichwort column_major vs row_major...