View frustum culling (AABB vs Frustum)

View frustum cullong

En este post voy a mostrar una manera fácil y eficiente de llevar a cabo la conocida técnica de view frustum culling con cajas alineadas a los ejes (axis aligned bounding boxes o AABB a partir de ahora).

Sistema de coordenadas local del objeto

Si consideramos que en nuestra escena podremos tener objetos/nodos con una transformación arbitraria (translación, rotación, escalado), necesitaremos trabajar en el sistema de coordenadas local del objeto para poder utilizar su AABB.

Este objeto tiene una matriz modelview-projection específica; recordemos que se pueden extraer los planos del frustum en el sistema de coordenadas local de este objeto tal como se explica en Cómo extraer los planos del frustum de visión de una matrix modelview-projection.

La manera sencilla

La típica forma de hacer view frustum culling es comprobando si la AABB está situada completamente por detrás de alguno de los planos del frustum. La manera más intuitiva de hacer esta comprobación AABB-plano, consistiría en ver si todos los (ocho) vértices de la caja están situados por detrás de dicho plano. Para recordar como hacer la clasificación punto-plano, visitar el enlace Clasificación punto-plano.

Aunque el test AABB-plano se puede llevar a cabo de forma mucho más eficiente, comprobando un único vértice de la caja…

Una alternativa más eficiente

Dados un plano y una AABB, se llama p-vertex (o vértice positivo con respecto a dicho plano) a aquel vértice de la AABB que está más adelantado en la dirección de la normal del plano. Podemos clasificar completamente la AABB con respecto al plano con sólo fijarnos en la posición del p-vertex (fuera si el vèrtice está en el semi-espacio negativo y dentro en el caso contrario). La siguiente imagen muestra dos casos diferentes:

P-Vertex selection

En la imagen de la izquierda, el p-vertex queda por detrás del plano (en el semi-espacio negativo); en este caso, podemos confirmar que la AABB entera está por detrás del plano, y por lo tanto, fuera del frustum de visión. En la imagen de la derecha, el p-vertex está por delante del plano (en el semi-espacio positivo), así que no podemos descartar la AABB, y por lo tanto tenemos que seguir haciendo comprobaciones con el resto de planos del frustum.

Selección del p-vertex

Podemos averiguar rápidamente cuáles son las coordenades p-vertex si disponemos de los vértices mínimo y máximo de la AABB.

AABB min and max vertices

El plano está descrito por la ecuación (ax + by + cz + d = 0), de la cual conocemos los valores (a,b,c,d). (a,b,c) es la normal del plano y (d) es la distancia al origen (estos valores posiblemente no estén normalizados). Podemos averiguar las coordenadas del p-vertex con el siguiente algoritmo:

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

O aún mejor, si guardamos min-vertex y max-vertex en un array de tamaño 2 y utilizamos un poco de aritmética booleana y conversión a enteros, podemos saber las coordenadas del p-vertex sin necesidad de utilizar estructuras condicionales (como se ve en la implementación a continuación).

Implementación

Aquí adjunto un trozo de código que implementa el 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 optimizaciones

Otras optimizaciones de esta técnica podrían ser las siguientes:

  • Recordar el último plano que descarta la AABB (coherencia temporal)
  • Usar máscaras de planos para estructuras jerárquicas de AABB
  • Octant test

Para más detalles, visitar la siguiente 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>