Frustum und Box

Vertex

Weil ich beide BoundingVolumes anbieten will. Gerade für Octrees unerlässlich.

Das wäre der Fall, wo sich das Frustum in der Box selber befinden würde z. B.

Das ist doch nicht wirklich ein interessanter Fall oder? Du willst doch i.d.R. herausfinden, ob sich eine BoundingBox im Sichtfeld befindet, und nicht umgekehrt. Und andere Fälle fallen mir nicht ein.

Vertex

http://www.blitz-pasting.net/uploads/useruploads/arLTL22655403776061_frustum.gif

Die Box müsste dennoch gerendert werden, obwohl die Eckpunkte auserhalb des Frustums wären.

mfg olli

TGGC

Vertex schrieb:

Hi!
http://www.delphigl.de/tutorials/frustumcull_de.html
Das Tutorial erklährt, wie man herausfindet, ob sich eine angegebene Box im Frustum befindet.

Die Box hat ja 4 Eckpunkte, das Frustum 6 Planes. Jetzt berechnet er die Distanz in einer Schleife der 4 Eckpunkte zu den 6 Planes. Ist der Abstand eines Eckpunktes zu einer Plane positiv, so befindet sich die Box im Frustum.

Die Beschreibung auf der Seite ist ungenau. Der Code testet für alle 6 Flächen, ob einer der 8 (BTW es sind 8 Ecken!) vor der Fläche liegt. Ist dies nicht der Fall, hat man eine separierende Achse gefunden, und die Box liegt ausserhalb. Findet man vor jeder Fläche eine Punkt (wie auch in deinem Beipielbild), wird die Box als im Frustum akzeptiert. Es gibt aber Boxen, die ausserhalb liegen, und trotzdem gezeichtnet werden.

+-------------+
|             |
|             |
|             |
|             |
|             |  ____________
|             |  \          /
|             |   \        /
|             |    \      / 
+-------------+     \    /
                     \__/

Bye, TGGC

rapso

Vertex schrieb:

Weil ich beide BoundingVolumes anbieten will. Gerade für Octrees unerlässlich.

bei nem octree testet man nicht ob 8boxen ein einem frustum sind, sondern auf welcher seite der 3planes das frustum ist. das ist dann auch sehr viel schneller (du hast doch gefragt wegen schnellerem test ).

rapso->greets();

SideWinder

rapso kannst du das mal näher erläutern, meinst du mit 8Boxen, Boxen mit 8 Eckpunkten, also nen Quader?

MfG SideWinder

TGGC

rapso schrieb:

bei nem octree testet man nicht ob 8boxen ein einem frustum sind, sondern auf welcher seite der 3planes das frustum ist. das ist dann auch sehr viel schneller

Man kann auch noch 'ne Kugel um die Box legen und erstmal diese testen.

Bye, TGGC

Cpp_Junky

Hm, also eigentlich müssen doch nur folgende Bedingungen getestet werden:

Rendern wenn:

- Min. ein Punkt innerhalb Frustum

- Min. ein Punkt links von / oder innerhalb Frustum _und_ 
  Min. ein Punkt rechts von / oder innerhalb Frustum
  (Nur links/rechts zieht hier natürlich nicht ganz - Man muss das in allen 
  Dimensionen testen

Diese ganze Frustum-Orgie lässt sich übrigens enorm vereinfachen wenn man das Frustum in Form von auf der Z-Achse immer grösseren Boxen darstellt. Das ist dann zwar nicht "ganz ein Frustum" weil es keine schöne Pyramide mehr ist aber es ist einfacher zu berechnen. Hab mir das Tutorial nicht durchgelesen, vielleicht machen die das ja sogar so

0x00000001

TGGC schrieb:

Es gibt aber Boxen, die ausserhalb liegen, und trotzdem gezeichtnet werden.

+-------------+
|             |
|             |
|             |
|             |
|             |  ____________
|             |  \          /
|             |   \        /
|             |    \      / 
+-------------+     \    /
                     \__/

Und hast Du vielleicht auch eine schöne Lösung für dieses Problem?
Man könnte schauen, ob mnindestens eine der 8 Frustumecken auch wirklich in der Box liegt. Besonders elegant ist das aber nicht. editier: und falsch wäre es sowieso fällt mir grad auf.

TGGC

0x00000001 schrieb:

Und hast Du vielleicht auch eine schöne Lösung für dieses Problem?

Man könnte eine genauere Abfrage machen. Bei konvexen Körper bzw. Polyedern gilt, (wenn ich es richtig zusammenbekomme) es existiert eine separierenden Achse senkrecht zu einer der Flächen oder zum Kreuzprodukt zweier Kanten, oder die Körper schneiden sich.

Oder du zeigst die Boxen halt trotzdem an. Das sind ja ehh nur BVs, d.h. selbst bei genauer Berechnung zeigst du ein paar unsichtbare Dinge an. Wenn die Boxen im Verglecih zum Frustum klein sind, gibts auch nur wenige die irrtümlich sichtbar sind.

Bye, TGGC

0x00000001

Danke.
Da muss ich jetzt wirklich erstmal analysieren wieviele unnötige Blätter tatsächlich gezeichnet werden. Denn um eine separierende Ebene zu finden sind viele Vergleiche nötig, und dazu kommt noch dass mein Frustum keine Near und Farplane hat und somit eine unendlich große Pyramide ist.

Vertex:
Vergleiche mit allen 8 Boxpunkten sind unnötig. Wenn nur interessiert ob Kollision oder nicht, nimmt man einfach den der Ebene am nächsten gelegenen Punkt.

Der Code kommt ursprünglich von www.zfx.info

BOOL CFrustum::BoxInFrustum(const CBoundBox *pbox )
{	
	VEC3 NearPoint;	

	for( UINT i=0 ; i<6 ; ++i )
	{
		if( (m_dwPlaneFlags & (1<<i)) == 0 )
			continue;

		CEbene* pEbene = &m_Ebenen[ i ];
		// Initialisiere nahen Punkt unter der Annahme
		// dass alle Normalen Komponenten <= 0.0f sind
		NearPoint = pbox->m_vMax;

		// Überprüfe die Annahme...
		if( pEbene->vNormal.x > 0.0f )
		{
			NearPoint.x = pbox->m_vMin.x;
		}

		if (pEbene->vNormal.y > 0.0f)
		{
			NearPoint.y = pbox->m_vMin.y;
		}

		if (pEbene->vNormal.z > 0.0f)
		{
			NearPoint.z = pbox->m_vMin.z;
		}

		// Checke ob der nahe Punkt ausserhalb liegt,
		// dann ist auch die ganze Box ausserhalb
		if ( D3DXVec3Dot( &pEbene->vNormal, &NearPoint) - 
			pEbene->fDist > 0.0f )
			return FALSE;

	} // for

	return TRUE;
}

Vertex

Da ich mich noch nicht so richtig beschäftigt habe mit Ebenen/Planes:
Ich kenne die Darstellungsformen c = N * X. Wobei N ein Einheitsvektor ist, X jeder Punkt auf der Ebene und c ein Konstanterwert sowie die Koeffizienten aus OpenGL: (P1 P2 P3 P4).

Jetzt frage ich mich ersteinmal:
P1 = (P2 P3 P4) * X ?

Laut GlSpecs2.0 werden die Koeffizienten P1 bis P4 als 4D Vektor aufgefasst, und mit der inversen ModelViewMatrix multipliziert zu (P1' P2' P3' P4') was die Eyekoordinaten dann sind. Ein Punkt (X Y Z W) der ebenfalls mit der inversen MVM multipliziert wurde (Xe Ye Ze We) liegt dann im Halfspace wenn das Punktprodukt aus (P1' P2' P3' P4') und (Xe Ye Ze We) => 0 ist. Stimmt das?

Kann mir jemand einen Anhaltspunkt geben, wie die aus der Projektionsmatrix die 6 Planes für das Frustum immer berechnen?

0x00000001: weißt du ob der Code funktioniert, scheint nämlich schnell zu sein.

Habe auch noch VBArchiv einen (bösen = 666) Code gefunden:
http://www.vbarchiv.net/archiv/tipp_666.html

mfg olli

0x00000001

Den 4D Vektor (a,b,c,d) einer Ebene kann man auch so auffassen:
(a,b,c) = N ist die Normale der Ebene, und d ist der Abstand zum Ursprung in Richtung von N. Also N * d = x, ein Punkt in der Ebene. Ich nehm mal an unter OGL wird das auch so sein, aber ohne Gewähr.

In Deinem Link steht ja drin wie Du das Frustum aus der Matrix bekommst. Und natürlich funktioniert mein Code, zumindestens hatte ich die letzten zwei Jahre den Eindruck Es gibt da nur den Sonderfall den TGGC angesprochen hat, aber das Problem hat Dein ursprünglicher Code auch.