Ruido blanco

Uno de los elementos fundamentales para la generación de contenido procedural es el ruido. Empezaremos por la forma de ruido más simple, el ruido blanco.

white_noise

Una imagen bidimensional compuesta por ruido blanco

como oirse (bajar el volumen antes de escuchar el sonido!).

Se denomina de esta forma a una señal que posee las distintas componentes espectrales “en igual proporción”. Dese el punto de vista de las señales continuas es solo una idealización ya que, si tuviera una potencia no nula en una banda espectral dada, tendría que tener una potencia total infinita. Pero en las señales discretas, al estar su frecuencia acotada superiormente, es posible tener un “espectro plano”. (También es posible definir ruido blanco en una banda de frecuencias dadas para señales continuas, pero eso no es el tema que trataremos en este post.)

Una forma común de generar ruido blanco es mediante el uso de muestras aleatorias independientes repartidas uniformemente en un intervalo. Por ejemplo, la imagen y el archivo WAV anteriormente mostrados fueron generadas mediante los siguientes scripts:

# requires PIL 1.1.6
# http://www.pythonware.com/products/pil/
import Image, random

def make_white_noise(fname, size):
    im = Image.new('L', size)
    pix = im.load()
    for i in range(size[0]):
        for j in range(size[1]):
            pix[i, j] = random.randint(0, 255)
    im.save(fname)

if __name__ == '__main__':
    make_white_noise('white_noise.png', (256, 256))

import random, struct, wave

def make_white_noise(fname, time):
wfp = wave.open(fname, ‘w’)
wfp.setparams((1, 2, 44100, 0, ‘NONE’, None))
for i in xrange(44100*time):
wfp.writeframesraw(
struct.pack(‘h’,
random.randint(-1<<15, 1<<15-1))) wfp.close() if __name__ == '__main__': make_white_noise('white_noise.wav', 1) [/code] En lo que resta de este post analizaremos porqué esto funciona…

Varianza y correlación

La varianza de una variable aleatoria es una medida de la dispersión de sus valores y se define, para el caso de una variable aleatoria real X, como:

\sigma^2(X) = E[X^2] - E[X]^2

donde E[.] representa al valor esperado. Utilizando la propiedad de linealidad del valor esperado podemos llegar a la siguiente identidad:

\sigma^2(X + Y) = E[(X+Y)^2] - E[X+Y]^2

\sigma^2(X + Y) = E[(X+Y)^2] - (E[X]+E[Y])^2

\sigma^2(X + Y) = E[X^2+2XY+Y^2] - (E[X]^2+2E[X]E[Y]+E[Y]^2)

\sigma^2(X + Y) = (E[X^2]-E[X]^2)+2(E[XY]-E[X]E[Y])+(E[Y^2]-E[Y]^2)

\sigma^2(X + Y) = \sigma^2(X)+\sigma^2(Y)+2(E[XY]-E[X]E[Y]).

El término que aparece sumado a las varianzas se denomina (bueno, en realidad la mitad de ese término se denomina…) covarianza y se anula si las variables aleatorias son independientes ya que:

E[XY] = \int_{\mathbb{R}^2} xy h(x, y) dx dy

E[XY] = \int_{\mathbb{R}^2} xy f(x) g(y) dx dy

E[XY] = \int_{\mathbb{R}} x f(x) dx \int_{\mathbb{R}} y g(y) dy

E[XY] = \int_{\mathbb{R}} x f(x) dx \int_{\mathbb{R}} y g(y) dy

E[XY] = E[X]E[Y],

donde llamamos f(x) a la densidad de probabilidad de X, g(y) a la densidad de probabilidad de Y y h(x, y) a la densidad de probabilidad conjunta, además de suponer que X e Y son independientes.

Por lo tanto, en caso de ser X e Y variables aleatorias independientes tendremos:

\sigma^2(X + Y) = \sigma^2(X)+\sigma^2(Y).

Espectro de una señal compuesta por muestras independientes y distribuidas uniformemente

Llamemos x_n a la señal compuesta por N muestras independientes distribuidas uniformemente en [-1, 1] y X_k a su DFT. Entonces tendremos

X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} k n}.

Como E[x_n] es nulo, cada término de la suma tendrá un valor esperado nulo y, por lo tanto, E[X_k] es nulo. Pero estamos interesados en la distribución de potencia por intervalo espectral, por lo que debemos observar a E[|X_k|^2] en lugar de a E[X_k].

Aplicando directamente la definición y operando algebraicamente tenemos:

E[|X_k|^2] = E\left[\left|\sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} k n}\right|^2\right]

E[|X_k|^2] = E\left[\left|\sum_{n=0}^{N-1} x_n \left(\cos\left(-\frac{2 \pi}{N} k n\right) + i \sin\left(-\frac{2 \pi}{N} k n\right) \right) \right|^2\right]

E[|X_k|^2] = E\left[\left|\sum_{n=0}^{N-1} x_n \cos\left(-\frac{2 \pi}{N} k n\right) + i \sum_{n=0}^{N-1} x_n \sin\left(-\frac{2 \pi}{N} k n\right) \right|^2\right]

E[|X_k|^2] = E\left[\left(\sum_{n=0}^{N-1} x_n \cos\left(-\frac{2 \pi}{N} k n\right)\right)^2 + \left(\sum_{n=0}^{N-1} x_n \sin\left(-\frac{2 \pi}{N} k n\right)\right)^2 \right].

Ahora, como los valores de x_n son independientes, tenemos que la covarianza entre dos elementos distintos cualesquiera para cada una estas sumas será nula. Eso nos permite, junto con el hecho de que E[x_n] = 0, transformar la expresión anterior a la siguiente:

E[|X_k|^2] = E\left[\sum_{n=0}^{N-1} x_n^2 \cos^2\left(-\frac{2 \pi}{N} k n\right) + \sum_{n=0}^{N-1} x_n^2 \sin^2\left(-\frac{2 \pi}{N} k n\right) \right].

Aplicando una identidad bien conocida 🙂 y distribuyendo a E[.] aprovechando su linealidad, llegamos a:

E[|X_k|^2] = \sum_{n=0}^{N-1} E[x_n^2].

Aunque podríamos encontrar el valor exacto, no es de mucha importancia ya que podemos observar algo mucho más importante: no depende de k. Eso nos indica que el espectro “es plano”, el resultado que buscábamos. (En realidad lo que es plano no es “el” espectro sino su valor esperado; pero eso es lo que suele interesar en el caso de una señal aleatoria.)

Terrenos multifractales

Un campo de creciente interés, teniendo en cuenta las enormes cantidades de contenido requeridas en los juegos modernos, es la generación de contenido procedural. Esta técnica consiste en reemplazar datos almacenados por datos generados mediante la ejecución de un procedimiento, de ahí el nombre “procedural”. La aplicación de estas técnicas permite ver la enorme cantidad de información que puede almacenarse en solo 96K.

Aprovechando este “fin de semana largo”, estuve explorando la geometría procedural y, en particular, la generación de terrenos mediante la utilización de fractales. Se denomina fractal a una entidad geométrica que presenta la característica de ser “autosimilar” a distintas escalas, o sea que si observamos una pequeña porción del mismo se “parecerá” en un cierto sentido a la entidad en su conjunto.

Un fractal muy utilizado para la creación de terrenos aleatorios es el denomiado como “fractional Brownian motion” (fBm), consistente en la suma de distintas señales de ruido con bandas limitadas y con un factor de escala adecuado (para evitar que las altas frecuencias tengan amplitudes comparables a las bajas frecuencias). En la siguiente imagen puede observarse un terreno generado mediante esta técnica:

Imagen de un terreno fractal (algoritmo fBM).

Imagen de un terreno fractal (algoritmo fBm).

Sin embargo esta clase de terrenos no resulta visualmente muy atractiva, ya que es simétrico (en cuanto a forma general, no en cuanto a los detalles ya que es aleatorio) respecto al plano “h = 0”, problema que no puede resolverse utilizando fractales del tipo fBM. Una solución, descrita por Ken Musgrave en su tesis doctoral junto a muchas otras, consiste en el uso de multifractales. En mi caso particular, me decidí por el algoritmo descrito por el mismo Ken en la sección 2.3.2.5.1 de su tesis.

El resultado obtenido puede observarse en la siguiente figura:

Imagen de un terreno multifractal.

Imagen de un terreno multifractal.

El código utilizado para crear y navegar en tiempo real sobre este terreno puede obtenerse en mi repositorio en Google Code (se sale con ESC, las flechas giran en torno al punto central, PgUp/PgDn controlan la distancia).

Pueden verse otros terrenos mucho más espectaculares (aunque no generados para renderizarlos realtime) en MojoWorld.

[Nota: Agregué en la home del proyecto los binarios para descargar. Requieren tener instalados “los componentes runtime” del Visual C++ 9, que puede descargarse desde aquí.]