Obtener los vértices del frustum

[ALBSIM]

                                Tengo una función, que a partir de las matrices de modelado y proyección de OpenGL, extraigo los planos del frustum en coord. de mundo.
Mi pregunta es: ¿Qué método sería el mas óptimo para obtener los vértices del frustum? Es decir, a parte de la posición de la cámara en coord. de mundo, quiero conocer los 4 vértices en coord. de mundo que delimitan el plano de corte lejano.
¿Es mejor obtenerlos a partir de sus coord. de recorte y las matrices de proy. y modelado? (no estoy seguro, pero creo que en este caso la concatención de matrices sería distinta a la usada para la extracción de los planos del frustum, ya que para los planos y normales (covariantes)  se utiliza la matriz traspuesta de la inversa de la transformación de ptos.),
O por el contrario es mas eficiente encontrar los puntos de corte de los planos extraídos en coord. de mundo.
Conoceis codigo fuente que resuelva este problema.

Gracias                                

[BeRSeRKeR]

                                Este es el code que utilicé para dibujar el frustum de las luces en unas pruebas que hice una vez. Utiliza Direct3D pero no creo que sea problema pasarlo a OpenGL...

(al principio de la aplicación)

// Tipo de vértice para las líneas que definirián el frustum
struct LINEVTX
{
   float x, y, z;      // posición de un vértice
   DWORD color;      // color del vértice
};

// Definimos los vértices para las líneas que definirián el frustum (clip space)
LINEVTX   g_FrustumVerts[] =
{
   { -1, -1, -1, 0xffffffff },   // L1
   { -1,  1, -1, 0xffffffff },

   { -1,  1, -1, 0xffffffff },   // L2
   {  1,  1, -1, 0xffffffff },

   {  1,  1, -1, 0xffffffff },   // L3
   {  1, -1, -1, 0xffffffff },

   {  1, -1, -1, 0xffffffff },   // L4
   { -1, -1, -1, 0xffffffff },

   { -1, -1,  1, 0xffffffff },   // L5
   { -1,  1,  1, 0xffffffff },

   { -1,  1,  1, 0xffffffff },   // L6
   {  1,  1,  1, 0xffffffff },

   {  1,  1,  1, 0xffffffff },   // L7
   {  1, -1,  1, 0xffffffff },

   {  1, -1,  1, 0xffffffff },   // L8
   { -1, -1,  1, 0xffffffff },

   { -1, -1, -1, 0xffffffff },   // L9
   { -1, -1,  1, 0xffffffff },

   { -1,  1, -1, 0xffffffff },   // L10
   { -1,  1,  1, 0xffffffff },

   {  1,  1, -1, 0xffffffff },   // L11
   {  1,  1,  1, 0xffffffff },

   {  1, -1, -1, 0xffffffff },   // L12
   {  1, -1,  1, 0xffffffff },
};

(en un método de inicialización)

   // Creamos una matriz de proyección para la luz...
   D3DXMatrixPerspectiveFovLH(&g_MtxLightFrustum, g_fLightFov, 1.0f, 10.0f, g_fLightFarPlane);

   // Calculamos la inversa de la matriz de proyección de la luz...
   D3DXMatrixInverse(&g_MtxInvLightFrustum, NULL, &g_MtxLightFrustum);

(método de render del frustum de la luz)

void RenderLightFrustum(void)
{
   D3DXMATRIX mtxWorld;

   mtxWorld = g_MtxInvLightFrustum * g_MtxInvLightView;

   g_pD3DDev->SetTransform(D3DTS_WORLD, &mtxWorld);

   g_pD3DDev->SetTexture(0, NULL);
   g_pD3DDev->SetMaterial(&g_YellowMtl);

   g_pD3DDev->SetVertexShader(D3DFVF_LINEVTX);
   g_pD3DDev->DrawPrimitiveUP(D3DPT_LINELIST, 12, g_FrustumVerts, sizeof(LINEVTX));
}

Saludos                                

[ALBSIM]

                                gracias por tu respuesta                                

[Repoker]

                                Ya que hablais de frustrum, tengo una preguntilla:

En un proyecto de demo que tengo entre manos hice un heightmap con valores generados usando un algoritmo de "colinas". El resultado es una malla de tamaño variable (10 - millones de poigonos) que gestiono en forma de triangle strips (para mayor velocidad). El problema viene cuando he de aplicar un algoritmo que me sirva para discriminar los triangulos que se dibujan o no; es decir, he estraido los planos del frustrum y tengo una funcion que me dice si un punto/triangulo está dentro del frustrum, pero en mapas grandes (300000-500000 triangulos) hacer la comprobacion de cada triangulo con esta funcion resulta inviable (muestra: renderizar toda una malla de 500mil tri. con Display Lists me da unos 50 fps en Geforce 4 4200 sin preocuparme por el frustrum, mientras que si aplico el algoritmo de frustrum culling me da unos 10).

Entonces mi pregunta es: conoceis algun algoritmo que permita una seleccion más rapida de los triangulos que hemos de chequear contra la funcion de frustrum culling?

Espero haberme expresado bien (me parece que no ...).

Gracias !                                

[Haddd]

                                Deberías utilizar un Octree, o quizás en tu caso con un Quadtree sea suficiente. Se basa en dividir el espacio en cubos. De esta forma basta comprobar el cubo con el frustum y si no está dentro, se descartan muchísimos polígonos.                                

[Loover]

                                ¿cuál es la diferencia entre un octree y un quadtree?                                

[Haddd]

                                Un Octree previdide el espacio en 8 cubos pequeños, en cambio un Quadtree sólo en 4. El Octree tiene una dimensión más.

Si coges tu mundo y le pones encima una cuadricula en los ejes X y Z, eso es un Quadtree:dividirlo en cuadrados más pequeños. Pero si además le añades altura, tendrás un cubo lleno de cuadrados pequeños:eso es un Octree