La Realidad Virtual es la más sofisticada de las interfícies existentes. Utilizando periféricos de RV, podemos manejar gran cantidad de datos complejos de forma intuitiva y ágil.

Entrevista a Oscar García

Técnicas de “Flocking” para entornos de Realidad Virtual

por Oscar García

Este artículo pretende retomar uno de los temas que en su día introduje en la revista. Ahora la aproximación a la problemática será mucho más práctica, intentando plantear soluciones concretas.

Introducción

¿Cómo podemos animar muchos seres virtuales (de ahora en adelante “avatars”) sin tener que modelarlos uno a uno?. Esta es la cuestión que quisiera plantearos. En grandes factorías de producción Multimedia como Disney, producen películas con escenas en las que inundan la pantalla de avatars que se comportan independientemente uno de otro. Por ejemplo la escena de la plaza en EL JOROBADO DE NOTRE DAME o bien la estampida de animales en EL REY LEON además de los típicos escuadrones de aviones “clónicos” que aparecen en muchas películas bélicas.

Al contrario de lo que pudiera parecer, los diseñadores no modelan y colorean a cada avatar por separado. Existen técnicas que automatizan este proceso. La idea es que el ordenador calcule automáticamente los efectos de “flocking” (bandadas, rebaños, estampidas, etc...) de forma que la responsabilidad del diseñador sólo implique la óptima elección del modelo 3D (mallado) o 2D (textura) para cada avatar.

Veamos un ejemplo con el que he trabajado recientemente:

Varias especies de animales marinos conviven en un Acuario Virtual.

en rojo se observan las partículas de comida que engullen los animales.

Para crear avatars “inteligentes” les tendremos que dotar de:

Visión. La posibilidad de ver todo aquello que les rodea. Técnicamente se trata de definir una región de “sensibilidad” para cada uno, dentro de la cual tienen acceso a la base de datos de geometría.

Movimiento. Es obvio que un pájaro vuela y un pez nada. Eso lo podemos solventar con un “solver numérico” de más o menos orden, según la precisión buscada. Ejemplos típicos son los algoritmos de Euler, Punto Medio o Runge-Kutta.

Colisión. El avatar tendrá conciencia del resto de elementos de la escena y chocará con ellos, ya sean objetos estáticos u otros avatars. Este punto es inseparable del primero, los sensores de visión artificial.

Intencionalidad. Un avatar tiene asociado un generador de intenciones que básicamente se encarga de las decisiones en cada momento: ¿voy a chocar?, ¿me estoy alejando de mi destino?, ¿estoy cerca del resto del grupo?, etc...

Existen aún más posibilidades al respecto pero de momento trabajaremos con lo dicho. Para centrar el tema hablaré de un ejemplo concreto: la simulación de bandadas de pájaros.

Pensad que son muchos los juegos que se sustentan en técnicas de este estilo. Algunos ejemplos son Unreal o Half-life

Diagrama General

Bueno que mejor que un diagrama para tener una visión global del sistema. Vamos a echarle una ojeada:

Nuestros avatars-pajaros “piensan por sí mismos” y por tanto tienen que ser capaces de priorizar entre diversas acciones. En este caso observamos que sus “heurísticas” de pensamiento son:

Tengo que volar hacia un destino predefinido, como por ejemplo un nido, un árbol o un montón de comida.

Tengo que permanecer cerca de la bandada. Los pájaros tienden a volar juntos en grupo y nunca se alejan demasiado a no ser que la necesidad sea imperiosa!.

Tengo que evitar colisiones. Esta claro que un pájaro no desea chocar contra un árbol, contra otro pájaro o bien contra un posible predador.

Tengo que seguir a mi líder. En el caso de existir puede optarse porque nuestros pájaros sigan más o menos fielmente a uno que ejerce de “jefe de grupo”.

El hecho de decidir qué hacer y qué no hacer o incluso priorizar entre varias opciones existentes se relega al llamado “Generador de Intenciones”. Este módulo es el que realmente modela el cerebro de cada pájaro. Un águila no actúa igual que una paloma o que un gorrión, a eso me refiero.

En la simulación intervienen diversos módulos que paso a describir uno por uno a continuación:

Solver Numérico

Parece contradictorio que empiece por el último módulo pero lo necesito para justificar el proceso que viene antes

Un solver numérico se encarga de calcular la evolución dinámica del sistema, es decir, la posición y velocidad de cada avatar a cada instante de simulación. La idea fundamental radica en definir lo que se llama un “problema de valor inicial”. Se parte de unas condiciones iniciales conocidas, típicamente las posiciones y velocidades iniciales de todos los avatars. A partir de éstas y conocido el Dt (incremento de tiempo) que supondremos que se produce a cada iteración, pasamos a “mover” toda la geometría. O sea que:

para t = t₀, conocemos la posición(t₀) = (x₀,y₀,z₀) y la velocidad(t₀) = (vx₀,vy₀,vz₀) de cada avatar

No es nada raro. De hecho básicamente a todos os tendría que sonar la famosa segunda ley de Newton:

Fuerza = Masa * Aceleración

Definidas cuáles son las fuerzas que actúan sobre un determinado avatar y conocida su masa, deducimos su aceleración. A partir de la aceleración y del tiempo deducimos su incremento de velocidad instantánea y de ésta su incremento de posición...osease:

1) Aceleración = Fuerza / Masa

2) Nueva velocidad = Velocidad anterior + Aceleración * Dt

3) Nueva posición = Posición anterior + Velocidad anterior * Dt

y ya lo tenemos! si hacemos esto repetidamente iteración tras iteración renderizando al final de cada una, tenemos un sistema de simulación dinámica. A este procedimiento tan simple se le conoce como “método explícito de Euler”. Es muy inestable para Dt’s demasiado grandes pero si se controla este parámetro no hay problema. Existen métodos más completos para integrar pero suelen emplearse en simulación física, cuando la precisión es un factor decisivo. En nuestro caso podemos sacrificarla un poco en favor de la velocidad, idealmente “tiempo real”.

Por tanto siempre tendremos una función dedicada a la resolución del método de Euler en nuestro sistema. Conclusión: necesitamos fuerzas como parámetro de entrada!

Para más información leed mis artículos sobre Simulación física. Métodos numéricos y Paso adaptativo.

Fuerzas

Podemos “inventar” tantas fuerzas como consideremos conveniente. De hecho existen procedimientos matemáticos complejos para deducir fuerzas a partir de condiciones aunque no entraré en ese punto. Se trata de introducir gravedad, fricción con el aire, tornados, eléctricas, magnéticas, muelles ... De momento pueden sernos de interés las dos primeras:

Gravedad Þ Fuerza (Newton’s) = masa (Kg’s) * G (típicamente constante de gravitación universal de valor -9.81 m/s²)

Fricción Þ Fuerza (Newton’s) = -Kv * velocidad (Kv es una constante de restitución a escoger por parte del programador. Se observa que esta fuerza siempre va en contra de la dirección del movimiento y dota al sistema global de más estabilidad).

Obviamente para la primera se nos hace imperiosa la necesidad de definir una masa para cada avatar.

Módulo de cálculo de aceleraciones

Bueno acabamos de ver que necesitamos trabajar con fuerzas para poder calcular aceleraciones. De hecho también es totalmente lícito añadir aceleraciones precalculadas a las obtenidas a partir de las fuerzas. Esto es lo que haremos con el generador de intenciones.

La idea básica es que en función de las decisiones del avatar se calcule un vector de aceleración que sumado a las aceleraciones provenientes de las fuerzas, se utilizará para desplazarlo en la próxima iteración. Una posible aproximación al cálculo es el promediado de varios vectores ponderados que es lo que se muestra en el diagrama. El avatar-pájaro calcula los siguientes vectores (siempre en coordenadas de mundo 3D):

1.       Vector desde su posición hasta el destino final prefijado. Este vector lo pondera la constante KD.

2.       Vector desde su posición hasta el centroide de la bandada (se entiende por centroide el promedio de las posiciones de todo el resto de pájaros). Este vector lo pondera la constante KB.

3.       En el caso de detección inminente de colisión, vector de respuesta a ésta. Me refiero al vector que evita la colisión. Este vector lo pondera la constante KC.

4.       Vector desde su posición hasta la del líder de la bandada (en caso de haberlo). Este vector lo pondera la constante KL.

Calculados estos vectores con un procedimiento puramente geométrico (hablo de ésto en mi curso de Gráficos publicado en esta misma revista) los ponderamos (multiplicamos) con las constantes para después promediarlos. Lo fundamental es escoger adecuadamente los valores de las constantes de forma que demos más peso a las decisiones de más prioridad y menos a las menos importantes (para el avatar-pájaro que estemos modelando está claro puesto que cada uno tiene sus propias constantes). Esto quedaría así:

Aceleración intenciones = [ KD(xd,yd,zd) + KB(xb,yb,zb) + KC(xc,yc,zc) + KL(xl,yl,zl) ] / 4.0

Aceleración fuerzas = S (Fuerzas) / masa

Aceleración Total = Aceleración intenciones + Aceleración fuerzas

De esta forma tenemos en cuenta tanto lo que decide el pájaro como lo que no puede controlar, es decir la influencia del resto del entorno sobre él. A partir de esta Aceleración Total y empleando el solver numérico deduciremos las nuevas posiciones / velocidades.

Correspondencia de velocidades

En el caso de que sea importante seguir el ritmo del resto de la bandada será de importancia este criterio. Si bien ya lo hemos tenido algo en cuenta en el apartado anterior con el vector avatar-centroide bandada, no está de más añadir un segundo punto de ajuste fino.

Simplemente se trata de escalar el módulo de la velocidad recién calculada (nada de tocar su dirección y sentido !!!) con la constante KV en el caso de detectar que somos demasiado lentos para el resto de la bandada aunque nos estemos dirigiendo hacia ella. La corrección pues:

Nueva velocidad final = Nueva velocidad * KV

De esta forma podremos acelerar a nuestros avatars si se quedan cortos! Quede claro que la metodología que estoy comentando conduce a un efecto realista a nivel de visualización y no de precisión. Si deseáramos lo segundo probablemente tendríamos que recurrir a algoritmos mucho más complejos. Esto nos irá muy bien para una bandada de pájaros o para el acuario virtual que os presentaba antes pero no para un sistema de cirugía virtual en tiempo real, por ejemplo.

Colisiones

Para documentaros sobre este tema podéis dirigiros a los artículos que escribí en su día sobre Detección de Colisiones entre objetos  deformables y Respuesta a las colisiones.

Además de lo mencionado en esos artículos quisiera comentar otra técnica que os puede ser muy útil para evitar obstáculos de forma automática en sistemas como éste, basados en cálculos dinámicos. Se trata de la utilización de voxels inicializados con campos vectoriales. Vamos a ello.

Un voxel es básicamente un “cubito” 3D en el espacio . Cada voxel almacena un valor de propiedad. Por claridad vamos a imaginarnos lo que se vería desde arriba, algo así como una proyección ortográfica superior de un trocito de nuestro mundo 3D:

En este caso supongamos el caso en que uno de nuestros pájaros tiene que bordear una columna. Podríamos optar por un procedimiento puramente geométrico a partir de vectores proyectándola sobre el plano de visión del pájaro y tratando de encontrar cual es la dirección que éste debe tomar para no chocar. Esto es complicado y tedioso puesto que empiezan a aparecer casos y más casos de esos que hay que contemplar aparte (singularidades...buuufff).

Ya que tenemos un sistema basado en fuerzas vamos a utilizarlas para evitar la columna con lo cual no tendremos que añadir procesos “extraños” al sistema. Sólo aprovecharemos lo que ya hay hecho!

Bueno se trata de añadir una nueva fuerza: un campo vectorial gradiente que apunte en dirección normal y opuesta al centro de la columna. Es un campo radial, normal a la superficie de ésta. Vamos mirad la figura y decidme que entendéis lo que digo!!!

Cada cajita es un voxel, una discretización 3D del espacio. Tiene unas dimensiones fijas conocidas y por lo tanto es muy fácil saber si nuestro pájaro esta dentro de uno. Montamos una “grid” como la de la figura (la resolución de ésta la decidimos a priori según nos parezca), asociamos un vector orientado de forma radial y hacia afuera en cada voxel y a simular.

El vector de cada voxel puede calcularse fácilmente a partir del centro de éste y el centro de la sección circular de la columna.

Si detectamos que nuestro pájaro se ha metido dentro de un voxel, o sea que se está acercando peligrosamente a la columna, le aplicaremos ,además de todo lo anterior, la fuerza que contiene. Podemos incluso escalarla para darle más o menos peso en relación al resto. Dejamos al solver numérico que haga su trabajo y tachán!!! (mirad la línea naranja de la figura) ... el pajarito no choca!!!

Consideraciones finales

Para acabar deciros que típicamente se normalizan todos los vectores (ya sabéis, se les divide por su módulo para hacerlos unitarios) de forma que inicialmente todos los módulos sean iguales. En esta situación digamos que todos “pesan” igual y es entonces cuando se escalan por sus constantes respectivas. Con estas constantes estamos dando más peso a unos y menos a otros, en definitiva, estamos modelando el “cerebro” del avatar.

Quede claro que “No es oro todo lo que brilla” y que la implementación de sistemas de este tipo siempre pasa por la resolución de distintos problemas. Para empezar no es fácil escoger el valor de cada constante que nos da el comportamiento exacto que buscamos. Tampoco lo es encontrar el valor adecuado del Dt (queremos velocidad pero si lo subimos mucho tendremos inestabilidad...). Hay que probar y probar pero bueno, ¿algo de “salsa” tiene que haber no? ¿si no dónde está la aventura?