Frustum Culling - notJustCode.it - Il sito sulla programmazione

Iniziamo con l’introdurre il concetto di Viewing Frustum.

Il frustum è un tronco di piramide costruito in questo modo: il vertice coincide con la posizione della telecamera (il nostro punto d’osservazione), la piramide è tagliata da due piani paralleli tra loro e perpendicolari all’asse del frustum, questi due piani prendono rispettivamente il nome di near e far plane, infine ci sono i 4 piani che definiscono i lati della piramide che prendono il nome di left, right, bottom e top; l’ampiezza del campo visivo della scena (l’apertura del frustum) e data dagli angoli Horizontal Field of View e Vertical Field of View i quali dipendono dalla risoluzione del viewport.

L’idea che sta alla base del frustum culling è di renderizzare solo gli oggetti contenuti, anche solo parzialmente, nel volume di spazio racchiuso dal viewing frustum così da ridurre il numero di oggetti che saranno elaborati dalla GPU. Lo svantaggio di questa tecnica sta nel fatto che il test, che stabilire se un oggetto è contenuto o meno nel frustum, è dispendioso dal punto di vista computazionale in quanto va applicato a tutti gli oggetti che compongono la nostra scena e deve essere ripetuto prima di disegnare ogni fotogramma, pertanto per ovviare a questo “problema” la tecnica del frustum culling si abbina con delle tecniche che permettono di partizionare lo spazio (anche dette space partitioning) in ordine gerarchico così da effettuare il test di visibilità sul minor numero possibile di oggetti che costituiscono la scena, la trattazione delle tecniche di space partitioning va oltre questo articolo ma per chi volesse saperne di più tra le principali tecniche esistenti vi sono il QuadTree, Octree, BSP, Portal Rendering. L’impiego del frustum culling è quindi limitato a scene con pochi oggetti.

Costruzione del Frustum

In questa parte dell’articolo vedremo come si costruisce il frustum.

Per calcolare i sei piani che formano il frustum abbiamo bisogno delle matrici View e Projection, in più dobbiamo dichiarare un array che contenga i 6 piani:

Questa è il metodo che calcola il frustum:

void BuildFrustumPlane()

{

D3DXMATRIX viewProjection;

D3DXMatrixMultiply(&viewProjection, &m_mView, &m_mProj);

// Left plane

m_frustum[0].a = viewProjection._14 + viewProjection._11;

m_frustum[0].b = viewProjection._24 + viewProjection._21;

m_frustum[0].c = viewProjection._34 + viewProjection._31;

m_frustum[0].d = viewProjection._44 + viewProjection._41;

// Right plane

m_frustum[1].a = viewProjection._14 - viewProjection._11;

m_frustum[1].b = viewProjection._24 - viewProjection._21;

m_frustum[1].c = viewProjection._34 - viewProjection._31;

m_frustum[1].d = viewProjection._44 - viewProjection._41;

// Top plane

m_frustum[2].a = viewProjection._14 - viewProjection._12;

m_frustum[2].b = viewProjection._24 - viewProjection._22;

m_frustum[2].c = viewProjection._34 - viewProjection._32;

m_frustum[2].d = viewProjection._44 - viewProjection._42;

// Bottom plane

m_frustum[3].a = viewProjection._14 + viewProjection._12;

m_frustum[3].b = viewProjection._24 + viewProjection._22;

m_frustum[3].c = viewProjection._34 + viewProjection._32;

m_frustum[3].d = viewProjection._44 + viewProjection._42;

// Near plane

m_frustum[4].a = viewProjection._13;

m_frustum[4].b = viewProjection._23;

m_frustum[4].c = viewProjection._33;

m_frustum[4].d = viewProjection._43;

// Far plane

m_frustum[5].a = viewProjection._14 - viewProjection._13;

m_frustum[5].b = viewProjection._24 - viewProjection._23;

m_frustum[5].c = viewProjection._34 - viewProjection._33;

m_frustum[5].d = viewProjection._44 - viewProjection._43;

// Normalize planes

D3DXPlaneNormalize(&m_frustum[0], &m_frustum[0]);

D3DXPlaneNormalize(&m_frustum[1], &m_frustum[1]);

D3DXPlaneNormalize(&m_frustum[2], &m_frustum[2]);

D3DXPlaneNormalize(&m_frustum[3], &m_frustum[3]);

D3DXPlaneNormalize(&m_frustum[4], &m_frustum[4]);

D3DXPlaneNormalize(&m_frustum[5], &m_frustum[5]);

}

Con questo passaggio abbiamo il nostro frustum, adesso possiamo passare alla scrittura dei metodi che ci consentiranno di controllare se un oggetto sarà inquadrato oppure no.

Test di visibilità

Fondamentalmente il test si limita a calcolare se ci siano vertici, appartenenti dell’oggetto, interni al frustum, dovremo quindi calcolare la distanza tra il vertice in esame e i piani e vedere se tale distanza sia maggiore di zero, se ciò fosse vero il punto e dentro il frustum altrimenti sarà fuori di esso.

I principali test di visibilità sono eseguiti su forme geometriche semplice (anche perché eseguire il test su forme geometriche complesse è controproducente e farebbe venir meno i vantaggi di questa tecnica) come Punti, Sfere e Cubi (fondamentale se si fa uso dei QuadTree), quindi non dovremo eseguire il test direttamente su tutti i vertici della nostra mesh bensì su un oggetto che lo “avvolga”.

Per fare ciò possiamo usare le comode funzioni D3DXComputeBoundingBox e D3DXComputeBoundingSphere che danno rispettivamente un box e una sfera che circonda la mesh.

Test su un punto

Calcoliamo la distanza tra il punto e il piano sfruttando la funzione che le DirectX ci mette a disposizione D3DXPlaneDotCoord, se la distanza è maggiore di zero proseguiamo il controllo con i restanti piani, se il punto è interno a tutti e sei i piani allora l’oggetto deve essere renderizzato:

bool isPointInFustum(const D3DXVECTOR3* Point)

{

// Se il prodotto scalare è maggiore di zero allora il punto è interno al piano

if(D3DXPlaneDotCoord(&m_frustum[4], Point) > 0.0f)

if(D3DXPlaneDotCoord(&m_frustum[3], Point) > 0.0f)

if(D3DXPlaneDotCoord(&m_frustum[2], Point) > 0.0f)

if(D3DXPlaneDotCoord(&m_frustum[1], Point) > 0.0f)

if(D3DXPlaneDotCoord(&m_frustum[0], Point) > 0.0f)

if(D3DXPlaneDotCoord(&m_frustum[5], Point) > 0.0f)

return true;

return false;

}

Test di una sfera

Il controllo su una sfera ha lo stesso ragionamento di base del punto ma in questo caso prendiamo in considerazione il centro della sfera a cui aggiungiamo il valore del raggio:

bool isSphereInFustum(const D3DXVECTOR3* Point, const float Radius)

{

// Se il prodotto scalare è maggiore di -Radius allora la sfera è interna al piano

if(D3DXPlaneDotCoord(&m_frustum[4], Point) > -Radius)

if(D3DXPlaneDotCoord(&m_frustum[3], Point) > -Radius)

if(D3DXPlaneDotCoord(&m_frustum[2], Point) > -Radius)

if(D3DXPlaneDotCoord(&m_frustum[1], Point) > -Radius)

if(D3DXPlaneDotCoord(&m_frustum[0], Point) > -Radius)

if(D3DXPlaneDotCoord(&m_frustum[5], Point) > -Radius)

return true;

return false;

}

Test su un cubo

Il test su un cubo si riduce semplicemente al test del punto, infatti, un cubo e costituito da otto vertici, basterà perciò controllare se almeno un vertice è interno al frustum, per fare questo sfruttiamo la funziona gia scritta isPointInFustum:

Bool isCubeInFustum(const D3DXVECTOR3* minPoint, const D3DXVECTOR3* maxPoint)

{

// Metà del lato del cubo

float size = maxPoint->x - minPoint->x;

if(isOPointInFustum(&D3DXVECTOR3(maxPoint->x, maxPoint->y, maxPoint->z)))

return true;

else if(isOPointInFustum(&D3DXVECTOR3(maxPoint->x, maxPoint->y, maxPoint->z - size)))

return true;

else if(isOPointInFustum(&D3DXVECTOR3(maxPoint->x, maxPoint->y - size, maxPoint->z)))

return true;

else if(isOPointInFustum(&D3DXVECTOR3(maxPoint->x - size, maxPoint->y, maxPoint->z)))

return true;

else if(isOPointInFustum(&D3DXVECTOR3(minPoint->x, minPoint->y, minPoint->z)))

return true;

else if(isOPointInFustum(&D3DXVECTOR3(minPoint->x, minPoint->y, minPoint->z + size)))

return true;

else if(isOPointInFustum(&D3DXVECTOR3(minPoint->x, minPoint->y + size, minPoint->z)))

return true;

else if(isOPointInFustum(&D3DXVECTOR3(minPoint->x + size, minPoint->y, minPoint->z)))

return true;

return false;

}

Faccio notare che per descrivere un cubo (che deve avere i lati allineati con gli assi “Axis Aligned Bounding Box”) basta avere il vertice minore e maggiore del cubo per poter trovare i restanti vertici.

Per approfondimenti consultate questo paper

http://www2.ravensoft.com/users/ggribb/plane%20extraction.pdf

Qui il Demo