No puedo evitarlo. Me encanta este algoritmo pese a la gran cantidad de recursos que dispone. Además puede implementarse tanto por software (como en Blade, que al tirar de CPU corría perfectamente en portátiles con tarjetas cutres) como por hardware (no totalmente, pero las partes más importantes de cara al rendimiento).
Muchos sabréis a qué técnica me refiero si digo que todas las sombras del Doom 3 y sucesores (Quake 4 y Prey, por ejemplo) están hechas utilizando esta técnica. Principalmente, mi interés por este algoritmo es porque es totalmente genérico, y fue por esto por lo que John Carmack decidió utilizarlo. Como desventajas, que depende mucho de la geometría de los objetos y que las sombras generadas son “duras”, es decir, que hay demasiado contraste entre la zona sombreada y la que no.
El algoritmo se divide en una serie de pasos. El primero consiste en generar la silueta del objeto que va a arrojar la sombra. Evidentemente, esto nos dice dos cosas: que el algoritmo va a tardar más cuantos más polígonos tenga el objeto y que hay que tratar cada objeto de forma independiente, por lo que cuantos más objetos tengamos en pantalla, peor. También hay que tener en cuenta que la silueta se utilizará para arrojar la sombra a partir de ella, luego no se permiten objetos con agujeros, como pudiera ser un donut, pues la silueta sería una circunferencia SIN agujero. Se podría solventar dividiento el donut en dos partes.
Para agilizar los cálculos, muchos juegos utilizan modelos con menos polígonos para el cálculo de sombras. Esto puede verse claramente en el Crazy Taxi o, más recientemente, el Toca Pro Race Driver 3. Para calcular la silueta, se eligen las aristas cuyos puntos tienen la normal con mayor ángulo respecto a la posición de la luz. Evidentemente, si un polígono está “de espaldas” a la luz, no se tiene en cuenta.
Una vez que se ha hecho esto, se tiene una lista de aristas que representa la silueta del objeto. El siguiente paso consiste en crear un volúmen (denominado shadow volume) extruyendo dicha silueta. Para ello se suele sumar un vector a cada punto, que es el vector iluminación multiplicado por una constante. Es muy importante calcular bien esta constante o la sombra podría atravesar varias paredes, si el volumen las atraviesa. En esta operación de extrusión es dónde se suele implementar, si se desea, código en un vertex shader en la GPU.
Una vez tenemos el volumen, se le colocan las dos tapas pues, hasta ahora, solo era un “cilindro” deformado, por decirlo así. Ahora hay que utilizar el stencil buffer, que es algo así como una máscara del photoshop. Al poner el cilindro en ése búfer, tenemos una máscara con la forma de ese cilindro vista desde la cámara. Se procede a pintar con iluminación ambiental (que suele ser bastante oscura) y luego se hace otra pasada puntando la iluminación estándar solo FUERA de la máscara definida en el stencil búfer. Es decir, este método lo que hace no es añadir sombras a la escena, sino NO iluminar esas zonas.
Este algoritmo tiene varias pegas. Lo que os he explicado aquí es la versión más sencilla del algoritmo, pero tiene un problema fundamental. Los polígonos solo tienen una cara visible. Si se les da la vuelta no se ven, es decir, no aparecen en el render. Por ello, si nos encontramos DENTRO del volumen de sombra, estamos viendo de espaldas todos los polígonos. En cuanto nos metamos dentro del volumen, no habrá ninguna sombra, pues el stencil buffer estará vacío, porque todos los polígonos están “de espaldas”.
Para solventar este proceso existe una variante del algoritmo. Podéis buscar información sobre ambos métodos por sus nombres técnicos: z-pass y z-fail. Evidentemente, dicha variante es mucho más compleja y necesita más recursos, por lo que se suele emplear el método sencillo siempre si la cámara no se encuentra dentro de ningún volumen.
Evidentemente, me faltan muchas cosas que explicar, como la manera de conseguir distintos niveles de sombra si existen varias fuentes de luz. He dejado en el tintero varias técnicas y variaciones (como la afamada, Carmack’s reverse) pero al menos espero que hayáis entendido la idea general. Y ojalá consiga implementarla algún día 
Enlaces:
KnudoW dice:
Eres un freak de las sombras! XD
No entiendo eso de que el donut no saque el agujero pero luego por ejemplo.. que un humano en un momento dado su brazo con respecto al cuerpo hagan que en su sombra salga un hueco sin sombra y eso sí se vea… es que con la técnica se traza el contorno exterior del modelo sin tener en cuenta las luces ni la posición que va a tener la sombra, y después de hacer eso se le aplica a la sombra la deformación requerida?
Miguel Herrero dice:
Lo del donut depende del algoritmo que se utilice para obtener la silueta.
En la silueta se tiene en cuenta todo lo que has mencionado, por eso la silueta (y el volumen de sombra) se recalculan cada frame.
[...] shading, y otros tantos pseudos. El único efecto ‘estándar’ por decirlo así son las stencil shadows de los personajes. Por ejemplo, el HDR se calcula de forma algo manual: cada sector del mundo tiene [...]
[...] para una PS2, hay efectos por doquier: gotas de lluvia en la cámara, reflejos en el agua, stencil shadows… y sin ninguna ralentización a pesar de mover decenas de enemigos en [...]