|
Autor: Oscar García i Panyella - “KOKOPUS” Fecha: 13-04-01 Técnicas de “Flocking” para entornos de Realidad Virtual 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:
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:
·
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 = t0, conocemos la posición(t0)
= (x0,y0,z0) y la velocidad(t0) =
(vx0,vy0,vz0) 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/s2) 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:
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? Si os interesa
más el tema podéis leer mis artículos sobre Aprendizaje Artificial
aplicado a Modelos deformables, también aquí en
Macedonia. |
