PDF de programación - sesión 6 - Gráficos y Física - APIs, Algoritmos y Técnicas

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

Índice de Contenidos :.

APIs para Gráficos 3D :: 1
OpenGL :: 1.1
Direct X / Direct 3D :: 1.2
Nvidia Cg :: 1.3
Algunas Técnicas Habituales :: 2
Algoritmos de Interiores :: 2.1
Algoritmos de Exteriores :: 2.2
Sistemas de Partículas :: 2.3
Shading :: 2.4
Simulaciones Físicas :: 3
Open Dynamics Engine (ODE) :: 3.1
Ejemplo en Blender Game Engine :: 3.2

«Todo debe hacerse tan simple como sea posible, pero
no más». Albert Einstein

Sesión 6 :: Transp. 2 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

¿Qué es una API para Gráficos 3D? :.

● API: Application Programming Interface.
● Es una capa software situada entre el programador y la
tarjeta aceleradora, presentando una abstracción consistente
al programador.
● Algunas APIs famosas:

● Glide: Diseñada específicamente para tarjetas 3DFx. Su
primera versión salió en 1994. Muy similar a OpenGL,
pero específica para esta familia de tarjetas. Actualmente
está siendo poco utilizada.
● OpenGL.
● Direct3D (parte de DirectX).

Sesión 6 :: Transp. 3 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

OpenGL :.

● Creado en 1990 por Silicon Graphics, y
actualmente mantenido por un comité de
compañías (Nvidia, Microsoft, SGI...).

● API Multiplataforma, simple y elegante.
● API de Modo Inmediato: Las llamadas
afectan directamente al frame buffer.
Esto simplifica el desarrollo; permite
independencia de estructuras de datos.
● Independiente de la gestión de
ventanas, bloques de memoria...
● Ampliamente utilizado en el desarrollo
de videojuegos.
● Gran comunidad de usuarios.

glClearColor(0.0, 0.0,
0.0, 0.0);
glClear(GL_COLOR_BUFFER_BIT
);
glLookAt(0, 0, -10,
0, 0, 0, 0, 1, 0);
glBegin(GL_TRIANGLES);
glColor3f(1,0,0);
glVertex3f(-1,0,0);
glColor3f(1,1,0);
glVertex3f(1,0,0);
glColor3f(0,0,1);
glVertex3f(0,1,0);
glEnd();

Sesión 6 :: Transp. 4 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

Direct3D :.

● Primera versión creada para W95.
● No llegó a ser funcional hasta la
versión 5.
● Gran esfuerzo para convencer a los
desarrolladores.
● DirectX no es sólo de
representación; módulos para
manejo de sonido, teclado...
● Actualmente DirectX es el API
dominante en juegos para PC y en
Xbox.
● Direct3D funcionalmente
equivalente a OpenGL.

Inicialización de un
dispositivo Direct3D

LPDIRECT3D8 g_pD3D = NULL;
LPDIRECT3DDEVICE8 g_pd3dDevice = NULL;
HWND hWnd;
D3DDISPLAYMODE d3ddm;
if(FAILED(g_pD3D
->GetAdapterDisplayMode
(D3DADAPTER_DEFAULT, &d3ddm)))
return false;
D3DPRESENT_PARAMETERS d3dpp;
ZeroMemory( &d3dpp, sizeof(d3dpp));
d3dpp.Windowed = TRUE;
d3dpp.SwapEffect =
D3DSWAPEFFECT_DISCARD;
d3dpp.BackBufferFormat = d3ddm.Format;
if(FAILED(g_pD3D->CreateDevice(
D3DADAPTER_DEFAULT, D3DDEVTYPE_HAL,
hWnd, D3DCREATE_SOFTWARE_
VERTEXPROCESSING,
&d3dpp, &g_pd3dDevice)))
return false;

Sesión 6 :: Transp. 5 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

NVidia CG :.

● CG significa "C para Gráficos" y es un lenguaje
de alto nivel, multiplataforma.
● El compilador de Cg genera código ASM para
ser introducido en los proyectos. El lenguaje del
programador es similar a C.

● MultiAPI: OpenGL y DirectX.
Requiere soporte mínimo DirectX8
y OpenGL 1.4
● Multiplataforma: Win. y Linux.
● Multihardware: NVidia, ATI,
Matrox...
● Asegura la optimización
manteniendo la compatibilidad.

Sesión 6 :: Transp. 6 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

NVidia CG :.

vpconn main(appdata IN, uniform float4x4 WorldViewProj,
uniform float3x3 WorldIT,
uniform float3x4 World,uniform float3 LightVec,
uniform float3 EyePos)
{
vpconn OUT;
float3 worldNormal = normalize (mul(WorldIT, IN.Normal));
float4 tempPos;
tempPos.xyz = IN.Position.xyz;
tempPos.w = 1.0;
float3 worldSpacePos = mul(World, tempPos);
float3 vertToEye = normalize(EyePos - worldSpacePos);
float3 halfAngle = normalize(vertToEye + LightVec);
OUT.TexCoord0.x = max(dot(LightVec, worldNormal), 0.0);
OUT.HPosition = mul(WorldViewProj, tempPos);
return OUT;
}

Fragmento (casi completo) de Anisotropic L.

Sesión 6 :: Transp. 7 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

Algoritmos de Interiores :.

● Combinando clipping + culling, sólo nos quedamos con 1/8 de la
geometría original. Sin embargo, sigue siendo demasiado.
● En Interior de Edificios, uso de Técnicas de Oclusión.

Algoritmos
Interiores
Exteriores

Clipping

Culling

Oclusión

Sí

LOD

Opcional

Sí
Sí

Sí
Sí

Opcional

Sí
● Para conseguir una tasa de fps determinada, suelen utilizarse
BSPs como estructuras de datos (Usado en Quake, Doom...)
● BSP: Binary Space Partitioning es un árbol binario que nos
permite clasificar la geometría espacialmente.
● Independiente del punto de vista, podemos consultarlo en
cualquier momento.

Sesión 6 :: Transp. 8 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

BSP: Construcción del Árbol :.

Algoritmo de generación del árbol recursivo.

1. Inicialmente, partir del conjunto de triángulos total.
2. Elegir el triángulo que mejor divide al conjunto por la mitad.
3. Calcular el plano que contiene al triángulo.
4. Almacenar el triángulo y el plano en el nodo actual.
5. Dividir los triángulos restantes según el lado del plano donde estén.
6. Si alguna sublista de triángulos del paso 5 no es vacía, crear un nuevo
nodo y ejecutar de nuevo el punto 2.
3

2

1

Sesión 6 :: Transp. 9 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

BSP: Construcción del Árbol :.

4

5

Finalmente, cada nodo
del BSP almacena
exactamente un
triángulo, que se utiliza
para dividir el conjunto
de datos en ese punto.

6

Sesión 6 :: Transp. 10 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

BSP: Construcción del Árbol :.

7

Sesión 6 :: Transp. 11 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

BSP: ¿Y todo esto para qué? :.

Ordenación Dependiente

de la Vista.

1. Comenzar con el punto de
vista y el nodo raíz del árbol.
2. Mirar si está en frente o
dentrás del plano.
3. Si estás en frente

3.1. Mirar el nodo "back".
3.2. Dibujar el triángulo.
3.3. Mirar el nodo "front".

4. Sino

4.1. Mirar el nodo "front".
4.2. Dibujar el triángulo.
4.3. Mirar el nodo "back".

Según el árbol de la Trp. anterior, los
triángulos se pintarían (de atrás-
adelante): 6, 5.1.1, 1.1, 5.1.2, 9, 8, 1.2,
2, 3, 4, 5.2

Sesión 6 :: Transp. 12 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

Leafy-BSP: Detección de Oclusiones :.

● Modificación de BSP para detectar oclusiones: Leafy-BSP.
● Constituyen el núcleo del pipeline de Quake.
● La geometría se propaga a las hojas. En las hojas guardamos
la lista de triángulos de cada nodo. Esto nos constituyen
"celdas".
● Si "lanzamos rayos" desde cada celda a el resto y vemos
cuales alcanzamos directamente (visibles), podemos saber
cuales están ocultas desde esa celda.
● Matriz PVS (Potentially Visible Set); es una matriz de
booleanos (bits) que indica si la celda de la fila X es visible por
la celda de la columna Y. Evidentemente es simétrica.

Sesión 6 :: Transp. 13 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

Leafy-BSP: Detección de Oclusiones :.

Sesión 6 :: Transp. 14 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

Algoritmos de Exteriores :.

● Uno de los principales problemas (a parte del LOD progresivo) es
almacenar las mallas de los escenarios. Alternativas:

● Mapas de Altura: Imágenes en escalas de grises que codifican la altura

del terreno.

● Quadtrees: Árboles cuaternarios que subdividen cada nodo en 4. Refinan

cada nodo calculando su punto medio y los vértices adyacentes con
valores (xmin, zmin), (xmin, zmax), (xmax, zmin) y (xmax, zmax).

Nivel N

z

Nodo
Original

Nivel N+1

Xmin
Zmax

Xmin
Zmin

Xmax
Zmax

Xmax
Zmin

División

x

Sesión 6 :: Transp. 15 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

Sistemas de Partículas :.

● Existen elementos que no pueden representarse de forma cómoda
como un conjunto de triángulos (un fuego, ondas, un árbol, ...).
● Sistemas de partículas: descripciones matemáticas de sistemas
dinámicos y complejos.
● Características:

● Dinámicos y dependientes del tiempo.
● Altamente paralelos con componentes individuales.
● Complejos.

● Sistemas Locales: No hay interacción con otras partículas.
● Sistemas Globales: El comportamiento de una partícula se ve
influenciada por ciertas propiedades de otras.
● Estructuras de datos en Partículas. Depende de lo que queramos
representar:

● Posición, velocidad, tamaño, color, transparencia, forma, tiempo

de vida...

Sesión 6 :: Transp. 16 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

Shading :.

● Implementación del modo de interactuar la luz con los materiales de
los objetos (iluminación y sombreado).
● Un modelo muy sencillo: La luz se calcula como suma de los
componentes ambiental, difusa y especular.

● Ambiente: Iluminación base de la escena. Proviene de todas

direcciones.

● Difusa: Luz reflejada por las superficies en todas direcciones.
● Especular: Luz reflejada en la "dirección del espejo". Evidentemente, la

intensidad es dependiente del punto de vista.

● Modelos más avanzados:

● Trazado de Rayos.
● Radiosidad. Muy utilizado por sus resultados y su eficiencia.
● BDRF (Bidirectional Reflactance Distribution Function).

Sesión 6 :: Transp. 17 

[Contenido] 1. APIs 3D :: 2. Algunas Técnicas Usuales :: 3. Físicas

Simulaciones Físicas :.

Modelo

(Mediante Ecuaciones)

1

Proceso Físico
(El sistema a Simular)

2

3

Algoritmo de
Simulación

(Método de resolución de

las ecuaciones)

4

Programa

(Implementación