Visibility Culling, disegnare solo ciò che si vede

Le moderne schede video offrano prestazioni sempre più strabilianti, ma le loro capacità non sono illimitate (soprattutto se sviluppiamo per dispositivi mobili) e non è poi così difficile superare tali limiti se non si presta la dovuta attenzione a quanto si disegna fotogramma dopo fotogramma.

Quando la scheda video non riesce più a stare dietro alla scena che viene disegnata, il gioco diventa "scattoso", poiché il tempo impiegato per rasterizzare un singolo fotogramma è troppo lungo e il numero di fotogrammi per secondo scende troppo per "ingannare" l'occhio dell'utente e dare l'impressione di fluidità.

Stress test

Per verificare quanto appena detto, proviamo a costruire una scena con 203 modelli, posizionati in una griglia regolare. Per cominciare, prepariamo la griglia. Dichiariamo una lista di tipo Vector3 e inizializziamola come segue:

List<Vector3> positions = new List<Vector3>();

Nel metodo Initialize "riempiamo" la lista di 20 x 20 x 20 vettori in varie posizioni e a diversa distanza dall'osservatore:

for (int i = 0; i < 20; i++)
{
  for (int j = 0; j < 20; j++)
  {
    for (int k = 0; k < 20; k++)
    {
      positions.Add(new Vector3(i, j, k) * 8000.0f - Vector3.One * 4000.0f);
    }
  }
}

Ricordiamoci, come al solito, di impostare le nostre matrici View e Projection (mentre imposteremo la World fra un attimo, perché essa dovrà tenere conto delle diverse posizioni delle varie istanze del modello):

Matrix view = Matrix.CreateLookAt(Vector3.Backward * 5000.0f + Vector3.Up * 5000.0f, Vector3.Zero, Vector3.Up);
Matrix projection = Matrix.CreatePerspectiveFieldOfView(1.5f, 1.3f, 10.0f, 100000.0f);

Proviamo adesso a disegnare 8000 istanze (una per ciascun punto della griglia) di un modello con un discreto numero di poligoni, in modo da mettere sotto stress la nostra scheda video:

foreach (var p in positions)
{
  var world = Matrix.CreateTranslation(p);
  saucer.Draw(world, view, projection);
}

Premendo F5, vediamo che il gioco scorre lentissimo, anche su PC molto potenti, come immaginavamo.

Disegnare solo ciò che serve, le bounding sphere

Per ovviare a questo problema, una delle soluzioni più semplici ed efficaci consiste nel disegnare soltanto quei modelli il cui volume si intersechi con il volume dell'area visualizzata.

Se un modello si trova al di fuori di quest'area non sarà visibile dall'utente; potremo quindi non processare i suoi vertici (la tecnica opera a livello di geometria, non di pixel), con un evidente risparmio in termini di performance. Questa tecnica è detta visibility culling (da non confondere con la tecnica di occlusion culling, che invece esclude dal disegno gli oggetti che risultano coperti da altri, più vicini alla telecamera).

Dal momento che, così facendo, spostiamo il carico di lavoro sulla CPU, non andremo a verificare vertice per vertice quali siano visibilo e quali no, perché altrimenti il costo di tale operazione sarebbe ancora più costoso, in termini di performance, rispetto all'operazione di disegno dei vertici stessi. Per il nostro test useremo pertanto un algoritmo più "grezzo", ma pur sempre efficace.

Per prima cosa, costruiamo un oggetto che approssimi il volume occupato dal nostro modello. Per far questo sfrutteremo una proprietà della classe ModelMesh, che associa a ciascuna mesh del modello un oggetto di tipo bounding sphere, ovvero una sfera che contiene il volume di tale mesh:

public sealed class ModelMesh
{
	public BoundingSphere BoundingSphere { get; }
	    ...
}

Dall'unione delle bounding spheres di ciascuna mesh del modello potremo ricavare un'unica sfera in grado di contenere il volume del modello. In questo modo, il volume del modello sarà determinato per eccesso, dandoci ampi margini di sicurezza nell'escludere il modello dalla scena.

Per costruire la nostra bounding sphere, ricorreremo alla sintassi LINQ (che, come molti di voi sapranno, ci permette di effettuare una query su qualunque oggetto implementi IEnumerable<T> o IQueryable<T>, restituendoci a sua volta un IEnumerable<T>) come segue:

var spheres = from m in saucer.Meshes select m.BoundingSphere;

L'oggetto spheres restituito dalla query è un IEnumerable di BoundingSphere, sul quale possiamo adesso invocare il metodo Aggregate, che a sua volta consente di aggregare ricorsivamente le nostre sfere, una dopo l'altra, finché non resterà che una unica, grande sfera. Per unire le singole sfere associate alle mesh usiamo il metodo statico CreateMerged esposto dalla classe BoundingSphere, il quale - date due sfere - restituisce una sfera in grado di contenere entrambe le sfere in input:

var sphere = spheres.Aggregate(BoundingSphere.CreateMerged);

Per chi non avesse grande familiarità con la sintassi LINQ, possiamo ottenere lo stesso risultato nel modo seguente

:

var sphere1 = saucer.Meshes[0].BoundingSphere;
for (int i = 1; i < saucer.Meshes.Count; i++)
{
  sphere1 = BoundingSphere.CreateMerged(sphere1, saucer.Meshes[i].BoundingSphere);
}

Nel codice che vediamo sopra, per prima cosa estrapoliamo la bounding sphere associata alla prima mesh del nostro modello, dopodiché iteriamo tra le mesh successive e "uniamo" ad ogni passo la sfera corrente con quella successiva. Al primo passo per esempio uniamo la prima sfera con la seconda, poi uniamo questo risultato con la terza, poi il risultato con la quarta e così via, fino alla sfera dell'ultima mesh.

Fatto questo, creiamo adesso un BoundingFrustum, ossia una classe che rappresenta il volume di spazio visibile attraverso lo schermo, a forma di tronco di piramide (di qui il nome di frustum). Per determinare il volume, dobbiamo moltiplicare tra loro le matrici View e Projection (è infatti il loro prodotto a determinare il volume visibile):

var frustum = new BoundingFrustum(view * projection);

Infine, modifichiamo il ciclo che disegna tutti i nostri modelli in modo che la bounding sphere di ciascun modello sia collocata nella giusta posizione. La sfera, una volta traslata per coincidere con la posizione del modello (local_sphere.Center += p), viene quindi confrontata con il BoundingFrustum per vedere se i due volumi si intersecano oppure no (utilizzando l'apposito metodo Intersect esposto dalla classe BoundingFrustum). In caso affermativo, procederemo a disegnare il modello, mentre nel caso contrario il modello sarà senz'altro invisibile, dato che il volume della relativa bounding sphere è stato calcolato per eccesso, per cui possiamo non disegnarlo a schermo:

foreach (var p in positions)
{
  var local_sphere = sphere;
  local_sphere.Center += p;
  if (frustum.Intersects(local_sphere))
  {
    var world = Matrix.CreateTranslation(p);
    saucer.Draw(world, view, projection);
  }
}

Confontando le figure, la differenza di fps ottenuti nei due casi (rispettivamente, senza e con visibility culling), è a dir poco notevole.