View frustum culling (AABB vs Frustum)

View frustum cullong

En aquesta publicació vull explicar una manera fàcil i eficient de fer el conegut view frustum culling per caixes contenidores alineades als eixos (axis aligned bounding boxes o AABB a partir d’ara).

Sistema de coordenades local dels objectes

Si considerem que a la nostra escena podem tenir objectes/nodes amb una transformació arbitraria (translació, rotació, escalat), necessitarem treballar en el sistema de coordenades local de cada objecte per tal de poder utilitzar la seva AABB.

Cada objecte té una matriu modelview-projection específica; recordem que podem extreure els plans del frustum de visió en l’espai de coordenades local de l’objecte com s’explica a l’enllaç Com extreure els plans del frustum d’una matriu modelview-projection.

Una forma senzilla de fer frustum culling

La manera típica de fer el view frustum culling, donada una certa AABB, és basicament comprovant si aquesta està situada completament al darrere d’algun dels plans del frustum. Una manera senzilla de fer això seria comprovant que tots els seus (vuit) vèrtexs estan al darrere d’aquest pla. En aquest enllaç podem recordar com es classifica un punt respecte d’un pla.

Però aquesta operació es pot fer molt més eficientment comparant només un vèrtex de la caixa…

Una alternativa més eficient

Donats un pla i una AABB, anomenem p-vertex (o vèrtex positiu) aquell vertex de la AABB que està situat més lluny en la direcció de la normal del pla. Podem fer la classificació de la AABB respecte aquest pla només fixant-nos en la posició del p-vertex (la AABB quedarà fora si el vèrtex està en el semi-espai negatiu del pla, o dins en el cas contrari). En la següent image podem veure dos casos diferents:

P-Vertex selection

A la imatge de l’esquerra, el p-vertex queda per darrere del pla; en aquest cas podem confirmar que la caixa sencera resta al darrere del pla, i així doncs, fora del frustum de visió. A la imatge de la dreta, el p-vertex està en el semi-espai positiu del pla, així que la AABB no pot ser descartada encara, i per tant hem de continuar fent tests amb els següents plans del frustum.

Sel·lecció del p-vertex

La sel·lecció del p-vertex es pot fer de forma molt ràpida si tenim els vèrtexs minim i màxim de la AABB.

AABB min and max vertices

El nostre pla està descrit per l’ecuació (ax + by + cz + d = 0), on nosaltres coneixem (a,b,c,d). (a,b,c) és la normal del pla i (d) és la distància des de l’origen (possiblement, tots aquest valors no estaran normalitzats). Poden saber quines són les coordenades del p-vertex amb el següent algoritme:

  • Si sign(a) > 0, agafem xmax; si no, agafem xmin.
  • Si sign(b) > 0, agafem ymax; si no, agafem ymin.
  • Si sign(c) > 0, agafem zmax; si no, agafem zmin.

Però encara millor,
Però encara millor, si posem min-vertex i max-vertex en un array de mida 2 i utilitzem una mica d’aritmètica booleana i conversions a enters, podem agafar els valors de les coordenades del p-vertex sense necessitat d’utilitzar sentències condicionals (com es fà en la implementació a continuació).

Implementació

A continuació poso un tros de codi que implementa aquest test:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Tells whether or not b is intersecting f.
 * @param f Viewing frustum.
 * @param b An axis aligned bounding box.
 * @return True if b intersects f, false otherwise.
 */

bool intersectFrustumAABB(
        const Frustum &f,
        const box3 &b)
{
  // Indexed for the 'index trick' later
  vec3 box[] = {b.min, b.max};

  // We have 6 planes defining the frustum
  static const int NUM_PLANES = 6;
  const plane3 *planes[NUM_PLANES] =
     { &f.n, &f.l, &f.r, &f.b, &f.t, &f.f };

  // We only need to do 6 point-plane tests
  for (int i = 0; i < NUM_PLANES; ++i)
  {
    // This is the current plane
    const plane3 &p = *planes[i];

    // p-vertex selection (with the index trick)
    // According to the plane normal we can know the
    // indices of the positive vertex
    const int px = static_cast<int>(p.a > 0.0f);
    const int py = static_cast<int>(p.b > 0.0f);
    const int pz = static_cast<int>(p.c > 0.0f);

    // Dot product
    // project p-vertex on plane normal
    // (How far is p-vertex from the origin)
    const float dp =
        (p.a*box[px].x) +
        (p.b*box[py].y) +
        (p.c*box[pz].z);

    // Doesn't intersect if it is behind the plane
    if (dp < -p.d) { return false; }
  }
  return true;
}

Més optimitzacions

Altres optimitzacions per aquesta tècnica podrien ser:

  • Recordar l’últim plà que va descartar cada caixa (coherència temporal)
  • Utilitzar màscares de plans en AABBs jeràrquiques
  • Octant test

Podem trobar més detalls sobre tot això en aquesta pàgina: Efficient View Frustum Culling.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>