domingo, 31 de octubre de 2010

Shadow-Texture Map

Este post esta relacionado con el de Shadows Map anterior. La idea surgió haciendo modificaciones al shadow map para que en lugar de proyectar una sombra, proyecte una luz o una textura. (ojo que no es un light map), por ejemplo una persiana que proyecta la luz (y la sombra) sobre el piso.
Esto mismo se podría hacer generando la geometría de la persiana y ubicando una luz atras de la misma, y usando el shadow map standard, pero eso es muy costoso, en el sentido que la geometría suele ser bastante complicada. (En verdad ni lo probé).
Lo que si probé, es modificar la textura del shadow map a mano, simulando que existe una geometría, y eso si funciona relativamente rápido. Por ejemplo, si escribo un texto en el shadow map (una vez que lo tengo en memoria ya calculado, usando el shadow map en 2d), el efecto es que se proyecta el texto como sombra en la escena. Sin embargo después de analizarlo más a fondo, encontré que ni hace falta generar el shadow map, y la cosa es mucho más sencilla.
Vamos de cero:
En el SM standard, el problema central radica en obtener las coordenadas del shadowmap a partir de las coordenadas del pixel actual. En otras palabras, lo que quiero saber es que coordenadas tendría el pixel actual desde el punto de vista de luz, y no de la camara.

Si partimos de la posición iPos de un vértice en object space y en lugar de aplicar la transformación de la camara, aplicamos la de la luz:

vPosLight = mul( iPos, g_mLightWorldViewProj );

g_mLightWorldViewProj es lo mismo que el g_mWorldViewProj pero haciendo de cuenta que la camara esta posicionada en la luz, y mirando hacia la direccion arbitraria a la que apunta el spot de la luz pp dicha.


Ahora, en el shadowmap standard, habria que usar las coordenadas vPosLight, para buscar en el shadowmap (previamente calculado) y verificar si el punto esta iluminado o no. Sin embargo lo que vamos a hacer es mucho mas simple:
1- No hay ningun shadow map si no una textura previamente cargada, que es la que queremos proyectar
2- En el VertexShader generamos vPosLigth como siempre: vPosLight = mul( iPos, g_mLightWorldViewProj );
3- En el PixelShader, usamos vPosLight para calcular la pos. en la textura a proyectar, y si esta dentro de los limites de la misma (x,y entre 0 y 1), tomamos el color de la textura.

Ejemplo:

float4 PixScene2( float2 Tex : TEXCOORD0,
float4 vPos : TEXCOORD1,
float3 vNormal : TEXCOORD2,
float4 vPosLight : TEXCOORD3 ) : COLOR
{
float4 color1 = 0;
float4 color2 = tex2D( g_samScene, Tex );
if(vPosLight.w>=0)
{
float2 pos = 0.5 * vPosLight.xy / vPosLight.w + float2( 0.5, 0.5 );
pos.y = 1.0f - pos.y;
if(pos.x>=0 && pos.x<=1 && pos.y>=0 && pos.y<=1)
color1 = tex2D( g_samProjTex, pos);
}

return lerp(color1,color2,0.5);
}










Esta linea sirve para limitar la proyeccion a la parte que esta delante del nearplane
if(pos.x>=0 && pos.x<=1 && pos.y>=0 && pos.y<=1)
De lo contrario saldria asi:





Por otra parte, la matematica involucrada en la proyeccion genera 2 imagenes, una inversa de la otra, cuando las coordenadas homogeneas son ambas negativas, es decir
tanto z, como w son negativas, luego Zp = z/w >0, pero estamos del otro lado de la "camara", ejemplo:




Para eliminar ese artificio, simplemente se puede poner:
if(vPosLight.w>=0)

Por ultimo, habría que combinarlo con el ShadowMap estandard, para evitar proyectar la textura en los lugares donde no podria verse, porque esta oculta por otro objeto.

lunes, 6 de septiembre de 2010

El Plano Proyectivo

Consideremos un punto P=(1,0) en el plano, la recta real en y=0, y un círculo que pasa por el origen y por P.

Graficamente:



Para cada punto de la recta real , se puede trazar una recta hasta el punto P, que intersecta al círculo en un único punto. Esta es la demostración standard, que el intervalo abierto (-1,1) tiene la misma cantidad de puntos que la recta real. Primero se demuesta que el intervalo (-1,1) se deforma hasta formar una circunferencia a la que le falta un punto (por eso el intervalo es abierto y no cerrado). Luego, la recta que une los puntos de la circunferencia con la recta real, define una función biyectiva que es lo que se necesita para probar que ámbos conjuntos tienen la misma cantidad de elementos.

La función se puede escribir como
(1) x1 = x1p / h
para todo x1p que pertenece a la circunferencia, salvo el punto p = (1,0), que es donde h=0 y el cociente no existe.

El hecho que la circunferencia tenga un punto menos que la recta real, a los efectos de la cardinalidad no tiene importancia, y se demuestra facilmente que un número finito o infinito numerable de elementos no modifica la cardinalidad de un conjunto infinito.
Sin embargo si genera una diferencia importante en el aspecto topológico, la recta real es equivalente a la circunferencia a la que le falta un punto, no la circunferencia completa.

Interpretación.
Si queremos representar en la recta real todos los ángulos posibles, o sea todas las rectas que pasan por P, nos estaría faltando una recta, que es la paralela a la recta real. Si se agrega el punto que falta en la circunferencia y se lo relaciona con dicha recta, (intuitivamente seríaa agregar el punto del infinito), podemos establecer que el conjunto de la recta real unión el punto del infinito es topologicamente una circunferencia completa.
A este conjunto se lo llama la recta proyectiva, porque esta compuesto de todas las rectas que pasan por un punto, o dicho de otra manera, por la recta real más el punto del infinito.
Los 2 puntos en el infinito se toman como el mismo punto en realidad, ya que corresponden a una sola recta, la dimensión de los puntos del infinito es cero, mientras que la dimensión de la recta es 1.


Plano proyectivo.
Pasando a 2 dimensiones, y con el mismo esquema de demostración, se tiene que el plano es equivalente a una esfera (superficie, usualmente se llama S2) a la que le falta un punto, o tambien, a una semiesfera abierta (que no incluye el borde). La frontera (el ecuador) esta relacionada con los puntos en el infinito. Se puede definir al plano proyectivo como el conjunto de todas los puntos del plano más los puntos en el infinito. En este caso los puntos del infinito son equivalentes a toda una circunferencia, y su dimensión es 1 , mientras que el plano tiene dimensión 2. De esta forma se puede definir recursivamente para un hiperplano:
El espacio proyectivo, se define de la misma manera, y los puntos del infinito son un plano y asi sucesivamente.


Coordenadas Homogeneas.
Para describir un punto en la recta proyectiva si bien se podría usar un sólo elemento ya que su dimensión es 1, (el agregarle un punto no cambia la dimensión del espacio), usualmente se usan 2 elementos, relacionados por la formula (1), que la escribimos de nuevo:

(1) x1 = x1p / h

Q = (x1p,h) cada elemento del plano proyectivo se representa por 2 coordenadas, pero que no son independientes si no que estan relacionadas por la fórmula (1).

Esto llevado al plano proyectivo, y usando la noticion habitual, se tiene
Q = (xp,yp,w)
donde x = xp/w y y=yp/w y (w!=0)

Esta forma de notación se llama coordeandas homogeneas o w-homogeneas. Se interpreta que el punto esta siendo proyectado en el plano w=w0, usualmente para puntos en el plano se utiliza w=1, con lo cual se tiene:
Q = (xp,yp,1)

Y tiene la ventaja que es posible escribir los puntos en el infinito, que estan asociados a w=0,
Q = (xp,yp,0)

Siempre se hace énfasis en que xp/0 no existe, y que no se tiene que tomar como una división que da infinito. Uno intuitivamente interpreta que xp/0 es un símbolo que representa un punto en el infinito y no una operación de división.

Algunas consecuencias de esta notación son
- cada punto tiene infinitas representaciones,
- que se puede escribir los puntos del infinito.
- 2 rectas siempre se cortan en un punto.

Estas coordeandas fueron introducidas por Möebius hace como 200 años pero se usan hoy en dia en la mayor parte de las librerias gráficas.

Que esta estudiando Möebius y que tiene que ver con el plano proyectivo?

Imaginen que queremos representar todas las rectas que pasan por un punto P en el espacio, (ese conjunto es el plano proyectivo claro). La forma mas facil es ubicar el punto P en el centro de una esfera (superficie), y las rectas que pasan por el centro, intersectadas con la esfera generan 2 puntos: p1,p2
Sin embaro, no hace falta usar 2 puntos, si no que con uno solo ya alcanza, porque la recta siempre pasa por el origen, con lo cual con una semiesfera es suficiente:
Todas las rectas están representandas por un punto en el interior de la semiesfera S, salvo (las del infinito) que van a estar representadas por 2 puntos en la frontera de S, o sea en el ecuador. Si arbitrariamente tomamos uno de los 2 puntos, (no hacen falta los 2), y si tomamos una recta que se va moviendo, siempre representada por un punto en S, cuando llega al ecuador (la frontera de S), súbitamente desaparece y re-aparece por el otro lado en la antípoda. (Eso en el momento que se hace invisible el primer extremo de la recta, a la vez que se hace visible el segundo, por el otro lado)



Como podemos “reorganizar” la superficie para que el movimiento de este punto virtual sea continuo?

Que pasa si intentamos “cocer “ la semiesfera S por el borde, uniendo cada par de antipodas? Bueno, eso no se puede hacer, intenten con una tela, o se puede demostrar con topología, (si se pudiese la esfera sin un punto seria equivalente a la que esta completa y eso no es cierto).

Möebius (o vaya a saber quien, la verdad que no lo se, pero me imagino que habra sido él), propuso lo siguiente:

Tomamos un punto p1 en el ecuador, y recortamos un entorno sobre el, y sobre su opuesto p2. Esas 2 superfices las unimos invertidas por el borde que antes era el ecuador , y con eso obtenemos un disco, el pto p1 = p2 = centro del disco, y con esa operación conectamos los puntos p1 y p2, y todo el entorno de ellos en el ecuador.
Lo quedo es esto:



Tomemos otro punto q1 en lo que quedo del ecuador, su opuesto q2, esta del otro lado, pero “opuesto”. Quiero conectar esos 2 puntos, (ya que son el mismo elemento), para ello tengo que doblar de un extremo y unir invirtiendo, lo que queda es una banda de Möebius, (que casualidad no? )




Ahora, la banda es una superficie no orientable: tiene una sola cara y un solo borde cerrado. Si el borde es una curva cerreda, es equivalente a una circunferencia. Si intentamos doblar y plegar la banda para que nos quede ese círculo no vamos a poder en 3 dimensiones, se necesitan 4 dimensiones para que la banda no se intersecte a si misma, pero eso no quiere decir que no se pueda imaginar. Sigan el borde de una banda de Möebius y van a verificar que es una curva cerrada, despues olvidense de la superficie, imaginense solo una curva cerrada y vean que se puede deformar hasta convertirse en una circunferencia.

Bueno, una vez que se tiene el círculo, ese borde corresponde a la frontera de los 2 entornos que habiamos retirado originalmente, y que unimos para formar un disco. Si pegamos ese disco en el borde, quedan conectados todos los puntos.
Con un poco de esfuerzo se puede demostrar que esta construcción respeta la "estructura" original (es un morfismo especial), si por ejemplo estudiamos el movimiento de una recta en la esfera original, representandola como el movimiento del punto en el plano proyectivo, el movimiento es continuo en ambos casos.

La banda de Möebius unida por el borde con un disco, se llama en topologia el plano proyectivo.

domingo, 5 de septiembre de 2010

Refrito de Matemáticas - Parte A

Esto esta reflotado de un TP de cuando estaba cursando análisis funcional y álgebra lineal en la UBA. Son todas cuestiones de matemáticas que tienen que ver con los gráficos por computadora.

El producto interno.
Motivación Geométrica.

Consideremos 2 vectores en el espacio euclídeo A y B, y el producto interno definido
A . B = A B cos O
Donde O = ángulo que forman, graficamente:

A cos O representa la proyeccion escalar de A sobre el vector B

Se puede demostrar que en R3 es equivalente al producto matricial:

Bx
A.B = [Ax Ay Az] By = AxBx + AyBy + AzBz
Bz


A veces se suele notar el producto interno entre 2 vectores v y w, como , especialmente cuando se trata de otros espacios que no sean Rn

Si consideramos dos vectores v y w en R3, w =1 (unitario) y el subespacio W (de dimensión en 1) generado por w, es decir W = {k*w}
Se puede demostrar que el vector
p = <v,w>*w
que es la proyección de v sobre w, es la mejor representación de v en W. Es decir no existe otro elemento en W que aproxime mejor a v.

Al estudiar el producto interno en el espacio euclídeo (recta, plano y espacio), los matemáticos indentificaron cuales eran las mínimas propiedades necesarias para demostrar todos los teoremas y asi generalizaron el concepto del producto interno a espacios mas abstractos, como los espacios de funciones. Finalmente se abstraen de la fórmula del producto interno, y formalmente, se define como una aplicación de VxV en K: (V es el espacio Vectorial y K es el cuerpo sobre el que esta definido. )


<.,.> VxV -> K

Ahora <.,.> tiene que cumplir:

<ax + by,z> = a<x,z> + b<y,z> (linearidad)

<x,y> = conj <y,x> (hermeticidad)

<x,y>=0 y <x,y>=0 <=> x=0 (definida positiva)





Es decir cualquier aplicación que cumpla esas condiciones es un producto interno, y son válidas todas las afirmaciones que se demostraron para Rn
Es facil demostrar que A.B = AxBx + AyBy + AzBz es un producto interno en R3, lo mismo que A.B = A1B1 + A2B2 + ....+AnBn tambien es un producto interno en Rn
(es el primer ejercicio que se ve en álgebra luego de definir el producto interno)

Usualmente esta definición abstracta de producto interno es el punto de partida del cual se deducen todas las demas propiedades. Por ejemplo, el angulo entre 2 vectores, se define a partir del producto interno como

cos O = <v,w>/(v w )

Esto permite definir un ángulo para vectores en especios vectoriales no tan convencionales como Rn. La verdad que la gracia de tanta abstracción se aprecia cuando se trabajan con otro tipo de espacios, como los espacios de funciones, donde un vector es una función, y gracias a estas abstracciones se puede definir el “ángulo” entre 2 funciones.

Bases.
De algebra lineal sabemos que todo vector se puede expresar como una combinación lineal de elementos de la base. Esa combinación es única, y sus coeficientes se llaman coordenadas.
Ahora, si la base es ortonormal, o sea si los vectores son ortogonales entre si, y unitarios, se cumple que :


B = { b1,b2...bn} Base ortonormal

v = <v,b1>b1 + <v,b2>b2 +...+ <v,bn>bn



Demostración. (resumida, para ver la idea)


por ser B base

v = a1b1 + a2b2 + ...+ anbn

lo que queremos probar es que

vk = <v,bk>para todo k

<v,bk>= <sum>x las prop de linealidad de <> para la suma y para el producto:

= sum ai <bi,bk>= ak porque <bi,bk>= 0 si i==k, o =1 si i=k

como queriamos probar,



Quería demostrar este teorema para hacer hincapie en que sólo se usa la definición del producto interno y la ortonormalidad de la base, y no la fórmula concreta para calcularlo.
Esta ecuación a la conoce tambien como expansión de Fourier, por algo que despues vemos.
Ahora, si consideramos la matriz T = [b1,b2,...bn], es decir cada columna de la matriz es un vector de la base, se puede demostrar que T es otorgonal, y la transformación lineal definida por T se llama ortogonal tambien.


Si escribimos

                    |b11  b21  bn1|        |<v,b1>|

v*T = (v1,v2...vn)* |b12  b22  bn2|     =  |<v,b2>|

                    ......................  

                    |b1n  b2n  bnn|        |<v,vn>|




o sea al mutiplicar un vector por la matriz T, que resulta de poner en cada columna un vector de la base ortonormal, se obtienen las coordenadas de v en la base B (Eso se suele notar como (v)B = v*T )

Nota: La coordenada i-esima es la proyección del vector sobre el vector i-esimo de la base.

Upgrade 2010:

En los graficos por computadora, es usual tener que transformar un punto del espacio real 3d (usualmente llamado world space) , al espacio del observador (usualmente llamado view space)
La función D3DXMatrixLookAtLH del DirectX calcula una matriz de vista, que luego se aplica a los puntos para transformarlos de world space al view space, en un proceso que se llama View Transform, en la jerga del DirectX

Esa matriz llamada View, esta compuesta por los vectores de una base ortonormal definidos por la direccion a la cual el observador esta mirando. El View Transform del pipeline del DirectX no es otra cosa que aplicar la expansion de Fourier en esa base a cada punto o vértice.
Usualmente se trabaja en en R4, para poder aplicar las traslaciones como multiplicación de matrices en la misma transformación. (Pero eso es tema del proximo post)


D3DXMATRIXA16 matView;
// posicion del punto de vista
D3DXVECTOR3 vEyePt(100,50,200);
// posicion a la que estoy mirando
D3DXVECTOR3 vLookatPt(0,0,0);
// direccion arbitraria hacia arriba
D3DXVECTOR3 vUpVec(0,0,1);
// el DX usa esta funcion para generar la matriz T
D3DXMatrixLookAtLH( &matView, &vEyePt, &vLookatPt, &vUpVec );


// segun lo que vimos, necesitamos una base ortonormal, que vamos a
// construi asi :
D3DXVECTOR3 vX,vY,vZ;
// la direccion Z es la direccion a la que estamos mirando
vZ = vLookatPt - vEyePt;
// la direccion X tiene que ser perpendicular a la direccion Z
// (el cross producto A = BxC devuelve un vector perpendicular a B y C,
// para eso necesitamos el vector UP, para poder generar un vector perpendicular
D3DXVec3Cross(&vX,&vUpVec,&vZ);
// pero la direccion UP, era aproximada, la real la generamos otra vez con
// el cross producto, Y es un vector perpendicular tanto a X, como Z
D3DXVec3Cross(&vY,&vZ,&vX);
// Hasta aca tenemos vX,vY,vZ todos perpendiculares entre si.
// nota: 3 vectores ortogonales son una base de R3
// Normalizamos
D3DXVec3Normalize(&vX,&vX);
D3DXVec3Normalize(&vY,&vY);
D3DXVec3Normalize(&vZ,&vZ);
// Ahora
// B = {vX,vY,vZ} = Base ortonormal de R3
// La matriz T = [vX vY vZ] es un aplicacion ortogonal

// Verificacion las columnas de T son los vectores de la Base
D3DXMATRIX T;
// vX vY vZ vW
T._11 = vX.x , T._12 = vY.x, T._13 = vZ.x, T._14=0;
T._21 = vX.y , T._22 = vY.y, T._23 = vZ.y, T._24=0;
T._31 = vX.z , T._32 = vY.z, T._33 = vZ.z, T._34=0;
T._41 = 0 , T._42 = 0, T._43 = 0, T._44=1;

// Hasta aca tenemos la parte de la matriz 3x3. Lo que falta para completar
// la matriz del DirectX que es de 4x4 es la translacion
T._41 = -D3DXVec3Dot(&vEyePt,&vX);
T._42 = -D3DXVec3Dot(&vEyePt,&vY);
T._43 = -D3DXVec3Dot(&vEyePt,&vZ);

// esto tambien se prodria haber hecho asi:
// | 1 0 0 0 |
// | 0 1 0 0 | x T
// | 0 0 1 0 |
// | -tx -ty -tz 1 |

// Trans = matriz de traslacion para origen al punto de vista.
// Entonces primero aplico la traslacion y luego el cambio de coordenadas
// pp dicho

//D3DXMATRIX Tras;
//D3DXMatrixIdentity(&Tras);
//Tras._41 = -vEyePt.x , Tras._42 = -vEyePt.y, Tras._43 = -vEyePt.z;
//D3DXMatrixMultiply(&T,&Tras,&T);

// La matriz T y la matView son iguales


Como decía anteriormente, la gracia de partir de una definición tan abastracta del producto interno radica en aplicarla a espacios no convencionales. Un buen ejemplo es el espacios de las funciones. Se puede demostrar facilmente que las funciones con las operaciones de suma y producto triviales (sumar funciones y multplicar una función por un numero), son un espacio vectorial.
Si pensamos una funcion como un vector de infinitas componentes, donde cada componente es el valor de la funcion en un punto, resulta intuitivo, que la sumatoria que define el producto interno habitual entre 2 vectores de dimensiones finitas, se transforma en una integral, lo que motiva a definir el producto interno entre 2 funciones como la integral del producto sobre el intervalo.
b
= integral f(x)g(x) dx
a

se puede demostrar que el conjunto de las funciones continuas acotadas en el intervalo [a,b], es un esp. vectorial y asi definido es un producto interno.

Con algunas condiciones más, las series de senos y cosenos típica de la forma de Fourier se basan en expresar una vector como una combinación lineal de elementos de la base, y en las propiedades de ortogonalidad

Nota: más tecnicamente se requiere un espacio de Hilbert, es un poco mas que un espacio vectorial.
El producto interno es una integral pero con algunas constantes para que cumpla las condiciones del producto interno, por ejemplo definida entre –pi y pi, la funcion tiene que ser cuadrado integrable etc etc) todas cosas que no vienen al caso en este contexto.

Como la base es infinita, si uno toma solo un cantidad finita de funciones (o elementos de la base), la serie se transforma en una suma, y la función resultante es una “proyección” de la función original en el sub-espacio generado por la base finita, y como habiamos dicho es la mejor aproximación que se puede obtener de esa función en dicha base. Es decir podemos ver a la suma de Fourier como una proyección en un espacio de dimension n, de la funcion real que vive en un espacio de dimension infinita.

Existen otras bases de espacios de funciones, como los polinomios ortogonales y que tienen propiedades similares a las de Fourier, usualmente se ven en la materia optativa de ecuaciones diferenciales de 3ero.

martes, 3 de agosto de 2010

Z-BUFFER Vectorial

El z-buffer es un invento magnífico, especialmente para todos aquellos que alguna vez tuvimos que resolver "a mano" el problema de las caras ocultas, para figuras arbitrarias. Cuando se trata de una superficie cerrada, se pueden ocultar facilmente las caras invisibles si se sabe de antemano en que orden están los vertices(horario o antihorario,pero todos iguales) . Si la proyección mantiene el orden la cara es visible (y si no esta oculta). (ver. Back-Face Culling). Pero para un conjunto arbitrario de caras, que es el caso más común en un escenario, el tema no es nada facil. Una de las formas de hacerlo es dibujando las objetos en orden z: primero los que estan mas alejados del pto de vista. Este algoritmo se llama del pintor. Para poder implementarlo es necesario una estructura especial con los caras, usualmente se utiliza en BSP (busquen binary space partition en el google, que hay cientos de ejemplos). En sintesis: es un despelote.

Todo esto se resuelve sencillamente con el directX activando el zbuffer, y con una resolucion de 24bits para la profundidad, es mas que suficiente para cualquier escenario tipico.

Ahora..si alguna vez intentaron trabajar con z-buffer y transparencias al mismo tiempo, la cosa se vuelve a complicar. Si bien en el directx permite configurar el alpha blending muy facilmente, el z-buffer asi como esta planteado no es compatible con el concepto de transparencia.
Una manera sencilla (y físicamente incorrecta) de resolverlo es dibujar primero todos los objetos opacos con el zbuffer activado, y luego desactivar el z-buffer y dibujar los objetos transparentes. Sin embargo, (y se puede demostrar facilmente) las ecuaciones que definen la transparencia NO SON CONMUTATIVAS, (salvo en el caso improbable que todos los objetos tengan el mismo color). En el caso general, la luz tiene que pasar por todos los objetos transparentes en el orden correcto (desde el más lejano hasta el más cercano) antes de alcanzar el punto de vista. Esto requiere que tengamos que dibujar los objetos transparentes en el orden z, por ejemplo usando una estructura de BSP, justamente lo que habíamos logramos evitar con el zbuffer!! . (El zbuffer surgió para evitar calcular estructuras como el BSP).

La solución que presento a continuacion es una prueba de concepto para extender el zbuffer. El zbuffer "normal" (y el color buffer) se puede pensar como "escalar" en el sentido que cada elemento del mismo contiene un valor único, que representa la profundidad, usualmente el valor de z que corresponde al punto más cercano al near plane.
Lo que necesitamos para implementar un alpha blending correcto, es que el zbuffer tenga todos los puntos al mismo tiempo, para poder ordenarlos por profundidad y asi generar la transparencia. Es decir un z-buffer "vectorial" y de ahi el titulo del post. La idea es simular este comportamiento "vectorial" de la siguiente manera:

1- Usar una textura auxiliares (con formato F32R) que va a representar el zbuffer, la vamos a llamar DepthMap.
2- Otra textura auxiliar (con formato RGB) va a representar el color buffer.
3- En el primer paso se dibuja toda la escena con el zbuffer activado, con un shader especial, para que grabe la profundidad en el depth map y el color en el colorbuffer. Este paso puede requerir 2 pasadas y 4 texturas, dependiendo de la implementación, pero esto no viene al caso. (Por ejemplo si no se usan multiples render targets). Luego de este paso, cada punto del depthMap y del ColorBufer contiene la profundidad y color respectivamente, del punto MAS cercano al near plane.
4- En el segundo paso, se vuelve a dibujar la escena, tambien con el z-buffer activado, pero con un pixel shader especial que hace uso del depthmap previamente generado y de la posibilidad que se introduce en el shader 3.0 de la semantica DEPTH. Esta permite que el pixel shader genere una profundidad como salida. (Siempre me pregunte para que podria llegar a servir eso...). El ps pregunta si la profundidad del pixel actual, es menor o igual a la que esta previamente grabada en el DepthMap. Si es asi, eso indica que ese punto ya fue "procesado", su color esta en el ColorBuffer y su profundidad en el DepthMap, Aprovechando que el ps puede cambiar la profundidad y que este punto no lo queremos volver a procesar, el ps asigna la profundidad en -1, haciendo al pto invisible. Y permitiendo que el directx ubique otro punto en dicho lugar. Si la profundidad por el contrario es mayor, se trata de un pto diferente, asi que devuelve la misma profundidad, para que el ztest sea el standard, y el color, combina el color actual con el que esta grabado en el colorbuffer, es decir hace un alpha blending a manopla.
Luego de este punto, en el dephmap esta grabado el SEGUNDO punto mas cercano al near plane, y en color buffer, la combinacion de ambos.
Este paso hay que volver a repetirlo una cierta cantidad de veces, hasta que finalmente no hay mas cambios en el depthmap y en el color buffer. En cada paso avanzamos "un lugar" hacia el farplane.

Para poder verlo graficamente, modifique el algoritmo para que borre (Clear) el colorbuffer en cada paso, asi se puede ver que puntos son visibles en cada paso, como el plano va avanzando desde el pto mas cercano hasta los mas lejamos.



Uniendo todos los colorBuffers:




Este es el PS que dibuja la escena en el ColorBuffer

void RenderScenePS( VS_OUTPUT In,float2 vpos:VPOS,out float4 Color:COLOR0,out float Depth:DEPTH)

{

   float prof = In.depth.x / In.depth.y; // prof del punto actual

   // pos = pos en el colorbuffer (0,1)

   float2 pos = float2(vpos.x/DX,vpos.y/DY);

   float prof_ant = tex2D(g_samDepthMap, pos).r;

   Color = 0;

   Depth = -1;

      if(prof>prof_ant+EPSILON )

      {

         // punto visible

         float4 scr_color = tex2D(g_samColorBuffer, pos);

         float4 dest_color = tex2D(MeshTextureSampler, In.TextureUV) * In.Diffuse;

         Color = scr_color + dest_color*kt;

      }

}




El ps que genera el depth map es muy similar, solo que en lugar del color devuelve la profundidad. Si se usaran MRT no haria falta 2 ps separados.



El algoritmo tiene 3 problemas importantes:
- El orden en que se obtienen los distintos mapas es inverso, primero el que esta mas cerca y por ultimo el que esta mas lejos. Eso es asi aproposito, primero probe de hacerlo al reves y me encontre con otro problema peor que no pude resolver. El problema que esten inversos se resuelve con un poco de algebra, al aplicar la ecuacion de alpha blending en cada paso, pero basicamente, el primer paso tiene mas peso que el segundo, y asi sucesivamente. Los ultimos pasos son los que menos contribuyen a la imagen final.
- No se sabe bien cuantos pasos hay que hacer, si bien "teoricamente" el algortimo se detiene cuando no hay cambios entre un paso y el siguiente, es muy costoso verificar eso en una textura de 1000 x 700. Por ese motivo decidi que el orden sea desde el near plane hacia el far plane, asi la cantidad de pasos la puedo dejar fija, y listo, total como los ultimos pasos son los que menos contribuyen, no seria tan grave perderlos. Si lo hiciera al reves, ahi si estaria en problemas...
- Hay serios problemas de redondeo, de momento hay que preguntar siempre con algun EPSILON puesto muy a manopla, con lo cual estoy trabajando para resolver estos problemas de inestabilidad del algoritmo.

domingo, 27 de junio de 2010

Simular un Object Shader

Con el Direct10, se introduce el concepto de object shader, que permite generar nuevas primitivas en el pipeline. Esto puede ser útil para el tesselado "on the fly", para efectos especiales de ropas, pelo, etc, donde se necesita un numero variable de polígonos que se puedan controlar durante la ejecución del pipeline.

Estoy trabajando con la idea de simular de alguna manera ese comportamiento en el DX9: es decir generar polígonos en tiempo real, sin usar el object shader. La motivación es que el VertexBuffer reside en la memoria física de la GPU, donde se ejecuta el Shader, entonces porque no acceder a él directamente?

Bueno, aca presento una manera de hacerlo, usando la posibilidad de acceder a texturas desde el VertexShader, (vertex texture), que se introdujo con la version 3.0 del modelo de shaders. (Anteriormente el VS no podia acceder a las texturas).

La instrucción que permite hacerlo es :

tex2Dlod(s, t)

(El algoritmo de Radiosity que presente en el post anterior hace uso intensivo de esto, ya que trabaja en el VS. )

Estrategia:

Se crea un VertexBuffer genérico que no tiene informacion de los vertices (ni posición, ni color, ni textura, nada). El vértice sólo tiene un ID o nro de vértice, que se implementa como una coordenada de texturas.
Este ID apunta a una texel dentro de una textura de "vértices" que se crea con tamaño suficiente para alojar a todos los vértices que se necesiten. Cada vértice tiene asociado un texel en dicha textura, que contiene las coordenadas x,y,z reales del vértice. Un valor de z =-1 indica que el vértice no esta siendo usado, ya que estamos hablando de un número dinámico de vertices o primitivas.
Para generar los vértices un shader especial renderiza directamente sobre la textura. Y el Vertex Shader que dibuja la escena, en lugar de tomar la posición como es habitual, del stream del VertexBuffer, solo usa el id, para ir a buscar la posición real a la textura.
Al estar el Vertex Buffer apuntando a una textura, y el VS dibujando sobre dicha textura, se esta simulando una especie de "dibujar sobre el Vertex Buffer", que es lo mismo que generar polígonos directamente desde la GPU.


Implementación:

Así definimos los vértices:



struct VERTEX_VIRTUAL

{

   D3DXVECTOR2 texcoord_id;

};

#define D3DFVF_VERTEX_VIRTUAL (D3DFVF_TEX1)





Lo único que tienen los vértices es un id. (Raro no?)

Para crear el VertexBuffer:



int cant_vertices = MAP_SIZE*MAP_SIZE;

g_pd3dDevice->CreateVertexBuffer( cant_vertices*sizeof(VERTEX_VIRTUAL),0,

D3DFVF_VERTEX_VIRTUAL,D3DPOOL_DEFAULT, &g_pVB, NULL);

VERTEX_VIRTUAL* pVertices;

g_pVB->Lock( 0, cant_vertices*sizeof(VERTEX_VIRTUAL), (void**)&pVertices, 0 );





Despues hay que generar los ids en forma correlativa:



int id_i = 0;

int id_j = 0;

for(int i =0;i<cant_vertices;++i)

{

  pVertices[i].texcoord_id.x = id_i++;

  pVertices[i].texcoord_id.y = id_j;

  if(id_i>=MAP_SIZE)

  {

    id_i = 0;

    ++id_j;

  }

}





Y hay que crear una textura para albergar los datos de los vertices pp dichos:



g_pd3dDevice->CreateTexture( MAP_SIZE, MAP_SIZE,1, D3DUSAGE_RENDERTARGET, D3DFMT_A32B32G32R32F,D3DPOOL_DEFAULT,&g_pTexVB,NULL);



Ojo: la textura tiene que ser del formato D3DFMT_A32B32G32R32F, porque el VS solo puede leer este tipo de textura, ademas necesitamos cierta precision para almacenar coordenadas.

Para generar los polígonos necesitamos que se llame un PS para cada texel de la textura. Para eso lo mismo de simpre, dibujamos 2 triángulos que ocupan toda la pantalla.
Ejemplo: Este PS simula un ObjectShader, y genera un único triangulo:



void PSGenerarTriangulos( float2 Tex : TEXCOORD0 , out float4 Color : COLOR0 )

{

  Color.xy = 0;

  Color.w = 1;

  Color.z = -1; // x defecto el vert. no es visible

  int id_i = Tex.x*MAP_SIZE;

  int id_j = Tex.y*MAP_SIZE;

  int t = id_j*MAP_SIZE + id_i;

  int nro_triangulo = t/3;

  if(nro_triangulo==0)

  {

    int nro_vertice = round(fmod(t,3));

    if(nro_vertice==0)

    {

      Color.x = -1;

      Color.y =  1;

    }

    else

    if(nro_vertice==1)

    {

      Color.x = 0;

      Color.y = 0;

    }

    else

    {

      Color.x = 1;

      Color.y = 1;

    }

    Color.z = 1;

  }

}






Desde la CPU, en cada frame hacemos asi:
1- Hay que generar los triangulso, como habiamos dicho, dibujamos los 2 triangulos:



g_pEffect->SetTechnique( "GenerarTriangulos");

LPDIRECT3DSURFACE9 pOldRT = NULL;

g_pd3dDevice->GetRenderTarget( 0, &pOldRT );

LPDIRECT3DSURFACE9 pSurf;

g_pTexVB->GetSurfaceLevel( 0, &pSurf );

g_pd3dDevice->SetRenderTarget( 0, pSurf );

g_pd3dDevice->Clear( 0, NULL, D3DCLEAR_TARGET, 0, 1.0f, 0 );

UINT cPass;

g_pEffect->Begin( &cPass, 0);

g_pEffect->BeginPass( 0 );

g_pd3dDevice->DrawPrimitive( D3DPT_TRIANGLESTRIP, 0, 2 );

g_pEffect->EndPass();

g_pEffect->End();

// Restauro el render Target

g_pd3dDevice->SetRenderTarget( 0, pOldRT );






2- Ahora que tengo los triangulos cargados en la textura, dibujo la escena pp dicha:




g_pd3dDevice->Clear( 0, NULL, D3DCLEAR_TARGET, D3DCOLOR_XRGB(0,0,0), 1.0f, 0 );

g_pEffect->SetTechnique( "Draw");

g_pd3dDevice->SetStreamSource( 0, g_pVB, 0, sizeof(VERTEX_VIRTUAL) );

g_pd3dDevice->SetFVF( D3DFVF_VERTEX_VIRTUAL );

g_pEffect->Begin( &cPass, 0);

g_pEffect->BeginPass( 0 );

// dibujo la cantidad maxima de polígonos, la mayoria no se va madar mucho mas adelante del VS, en el pipeline

// ya que el z=-1 hara que no sea visible.

g_pd3dDevice->DrawPrimitive(D3DPT_TRIANGLELIST, 0, MAP_SIZE*MAP_SIZE/3);

g_pEffect->EndPass();

g_pEffect->End();




Ahora, desde el VS de dibujar la escena, hay que tomar la pos. del vertice, accediendo a la textura:
Notar que el VS NO recibe ninguna posicion, pero si la devuelve, aca esta la posta:



void VS_Draw(float2 iId: TEXCOORD0,out float4 oPos : POSITION)

{

  // voy a buscar la pos. del vertice a la textura de datos

  oPos = tex2Dlod( g_samVertexBuffer, float4(iId/MAP_SIZE,0,0));

}




Y asi sale el triangulito por pantalla :





Escribir el PS que genere los triangulos NO es nada trivial, y ahi esta toda la complicacion del implementar esta idea para algun caso concreto. Ya que no se puede poner un if(nro_triangulo==n) para todo n...
Y la logica queda inversa: usualmente uno parte del triangulo, genera sus 3 vertices, y luego guarda en memoria esos 3 vertices, correlativos, y un triangulo al lado de otro, en el stream del VertexBuffer.
El problema que aca estamos "al reves", en el PS tengo la posicion del byte o del vertice en el stream del VertexBuffer, y tengo que hacer el camino inverso para determinar que triangulo seria el que genero el vertice que va a ser guardado ahi. O sea un kilombo. Sin embargo se puede resolver. Aca muestro un ejemplo, de algo mas concreto, es un shader que toma una textura previamente grabada de un bmp, y genera un triangulo para cada pixel en la textura, cuya pos x,y corresponde al ubicacion dentro del bmp, y la profundidad corresponde al color. Esto es la base para implementar un heigh-map dinámico, pero eso lo voy a presentar en el próximo post: la idea es que la precision del height map se adapte a la distancia al punto de vista.



void PSHeightMap( float2 Tex : TEXCOORD0 , out float4 Color : COLOR0 )

{

  Color.xy = 0;

  Color.w = 1;

  Color.z = -1; // x defecto el vert. no es visible

  int id_i = Tex.x*MAP_SIZE;

  int id_j = Tex.y*MAP_SIZE;

  int t = id_j*MAP_SIZE + id_i; // pos en el VertexBuffer

  int offset = round(fmod(t,12));

  int nro_triangulo = offset/3;

  int nro_vertice = round(fmod(t,3));

  // pos. en el heightmap

  int pos = t/12;

  int i = pos/HMAP_SIZE;

  int j = round(fmod(pos,HMAP_SIZE));

  if(i<HMAP_SIZE && j<HMAP_SIZE)

  {

    float h = tex2Dlod( g_samDatos, float4((float)i/HMAP_SIZE,(float)j/HMAP_SIZE,0,0)).r;

    if(nro_triangulo==0)

    {

      if(nro_vertice==0)

      {

        Color.x = (float)i/HMAP_SIZE;

        Color.y = (float)j/HMAP_SIZE;

      }

      else

      if(nro_vertice==1)

      {

        Color.x = (float)(i+1)/HMAP_SIZE;

        Color.y = (float)(j+1)/HMAP_SIZE;

      }

      else

      {

        Color.x = (float)(i+1)/HMAP_SIZE;

        Color.y = (float)(j-1)/HMAP_SIZE;

      }

      Color.z = h;

    }

  }

  Color.x = 2*Color.x - 1;

  Color.y = 1 - 2*Color.y;

}




Y asi sale por pantalla (para los que quieren ver algun dibujito...mucho código para poca cosa parece no?) Lo bueno esta abajo de la superficie (en z<0? )


hacking depth-buffer

Me preguntaron como se podía acceder al depth-buffer directamente desde un shader. La verdad que siempre que necesite el valor de z, por ejemplo para un shadow map, lo tenia guardado en una textura, previamente generada.
Sin embargo, porque no poder acceder directamente al depth-buffer? aunque sea solo para lectura, si de alguna manera esta disponible.

Buscando, encontre este truco en el manual de programación de la placa. Desafortunadamente es especifico de la placa, en este caso de la nvidia serie 7, y no es algo del directx. El truco es asi, para poder hacerlo, el driver de la placa expone una textura especial que contiene los datos del depth-buffer, engañando asi al directX. Para poder hacerlo, el formato de la textura se crea con una macro FOURCC y el siguiente codigo "no documentado" :


pd3dDevice->CreateTexture(ancho, alto, 1,D3DUSAGE_DEPTHSTENCIL,
(D3DFORMAT)MAKEFOURCC('R','A','W','Z'),
D3DPOOL_DEFAULT, &m_DepthBufTexture, NULL);

El codigo RAWZ funciona para la GeForce serie 6 y 7. Una vez creada esta textura se comporta como cualquier otra textura. Por ejemplo desde un shader se puede acceder al valor del z asi:

(1)
float z = dot(tex2D(DepthBufSampler, Tex).arg,
float3(0.99609375,0.0038909912109375,0.000015199184417724609375));

De donde sale semejante formula?
El tema es asi, el rawz significa que el driver expone la memoria tal como esta, sin convertila a ningun valor, el depth buffer tiene que tener el formato de 24bits para el z-buffer y 8 para el stencil. El z-buffer se almacen en los primeros 3 bytes en el A,R y G, y el stencil se almacena en el B.
A,R y G van de 0 a 1, el A es el de mayor peso, lo que nos lleva a esta formula:
z = A*255/256 + R*255/256/256 + G*255/256/256/256
que es justamente la formula (1). (Ya se imaginan los problemas de redondeo que debe tener esta fórmula no?)

Y esto anda? Bueno me anduvo barbaro hasta que quise probar otra forma de hacerlo, que con el código mas nuevo: INTZ, que dice que expone directamente el valor de Z, en cualquier de los 3 canales, con lo cual no habría que hacer ninguna conversión, y chau problemas de redondeo. Tambien dice que requiere el nuevo driver de nvidia, asi que me lo baje.
A partir de eso no me anda ni el RAWT que si andaba y se me cuelga el panel de control de la nvidia (entre otras cosas....) (tendria que haber guardado el driver original no? )
Mas alla de eso, es interesante como usan una textura con un código mágico para exponer al directx una característica no standard. Buscando un poco por la red encontré que esto es comun en casi todas las placas y hay otras características que se pueden acceder de esta manera.

domingo, 20 de junio de 2010

Real Time Radiosity - Problemas y Soluciones

Algunos Problemas y como se fueron resolviendo.

Anti-Aliasing del Shadow Map.
Si acercamos la vista a la sombra de una de las piedras, vemos que la se puede notar un efecto "serrucho". Sin embargo este error no es introducido por el shadow map (cosa que se puede comprobar agrandando o achicando el tamaño del mapa sin ningun efecto en el mismo), si no que esta producido por el tesselado.




Para resolverlo seguimos 2 caminos.

- Primero cuanto mas tesselado este la escena menos visible sera el error. Pero como estamos muy limitados con la cantidad de poligonos y pacthes a evaluar, no es una buena solucion. La disposición del tesselado tambien repercute senciblemente en el error:




El tesselado de la izquierda es muy superior a la de la derecha, es preferible tener menos cantidad de polígonos totales pero distribuidos centralmente como en la izquierda, que un tessellado mas fino, pero con una distribución como el de la derecha. Con esa distribución si la linea de sombras fuera dialogonal en menos 45 grados, el efecto del error sería muy visible.

De contar con un el un object shader (directx10) se podria resolver el problema directamente en el shader generando un tesselado en el momento, de acuerdo a si hay diferencias de iluminacion marcadas entre los 3 vertices.

- Aplicar un algoritmo de anti-aliasing modificado:

// anti-aliasing del shadowmap
// I = intensidad de luz
float I2 = 0;
float r = 1;
float FP = 2;
for(int i=-r;i<=r;++i)
for(int j=-r;j<=r;++j)
I2 += (tex2Dlod( g_samShadow,
float4(auxCoord + float2((float)(i*FP)/SHADOWMAP_SIZE, (float)(j*FP)/SHADOWMAP_SIZE),0,0) )
+ EPSILON < vPosLight.z / vPosLight.w)? 0.0f: 1.0f;

I2 /= (2*r+1)*(2*r+1);
I = I*0.2 + I2*0.8;

El algoritmo toma un cierto radio r alreder del punto i,j del shadow map para promediar los distintos valores (que pueden ser cero o 1 si esta o no en la sombra). Sin embargo, como estamos trabajando con polígonos y no con pixels, hay que introducir un factor, (lo llamamos factor de penumbra = FP), que permite alejarse mas del punto inicial del shadow map. De no introducir este factor, habria que tomar un radio enorme para obtener algun efecto. El un gran factor FP produce un efecto de penumbra. De todas formas en algoritmo de radiosity usualmente no nos preocupamos por este error del shadow map, porque la sombra se va a suavizar por si sola, en la medida que sigamos evaluando mas rayos, y como consecuencia todas las sombras tienden a ser suaves en cualquier solución de radiosity. Sin embargo, como en nuestro algoritmo estamos tomando muy pocos rayos, se logra un buen efecto haciendo un anti-aliasing SOLO del primer rayo:




En estos ejemplos solo se toma el primer rayo para ver bien el efecto del anti-aliasing. En la práctica con todos los rebotes se llega a un buen balance con r = 1, y FP=2.
Ejemplo con r = 1, y evaluando todos los rayos, el error original ademas se ve suavizado con tonalidades rojizas que provienen de la pared.




- Intensidad de la luz en cada Rebote.

Si el algoritmo fuese físicamente correcto no habría ningun problema con la intensidad de luz. Pero al simplificar las ecuaciones, y evaluar solo cierto rayos etc etc, el algoritmo esta precisa ciertos valores que se introducen artificialmente y que si no estan corrrectos pueden producir errores extraños.
La fuente de luz inicial parte con una intensidad i0, los rebotes primarios i1, y los secundarios i2. Tiene que haber un balance entre la cantidad de rayos totales y las intensidades relativas.




Afortundamente estos valores se pueden aproximar ya que son directamente proporcionales a la cantidad de rayos. Y luego se pueden ajustar por cuestiones estéticas o subjetivas.

Velocidad y Discontinuidad en el tiempo.

El algoritmo estandard funciona aproximadamente a 2fps usando 40 rebotes promedio, y menos de 1fps usando 60 rebotes promedio. Para mejorar la performance se usa la siguiente técnica: en lugar de usar un solo mapa de radiosity, se usan 3 mapas, uno para cada paso del algoritmo y se divide el algoritmo en 4 pasos de carga similar. En cada frame solo se calcula uno de los pasos:
paso 1: se procesa la 1er luz con el antialiasing del shadow map.
paso 2: se calculan las luces secundarias.
paso 3: se procesan las luces secundarias.
paso 4: se generan las luces terciarias y se procesan.
En cada paso se procesa el input y se dibuja la escena sumando los valores de los 3 mapas:

Diffuse = tex2Dlod( g_samRMap, float4(iId/MAP_SIZE,0,0))
+ tex2Dlod( g_samRMap2, float4(iId/MAP_SIZE,0,0))
+ tex2Dlod( g_samRMap3, float4(iId/MAP_SIZE,0,0));

Los primeros frames el algoritmo dibuja resultados parciales, pero una vez que llenaron todos los mapas, en cada paso dibuja una solución que es una mezcla de la solución actual + 2 soluciones anteriores.
Esto ademas resolvió otro problema que tiene que ver con una discontinuidad en el tiempo al mover las fuentes luminosas o los objetos de la escena. Una mínima diferencia en la fuente luminosa puede producir un bruzco cambio de toda la solución, al caer por ejemplo en otro patch diferente. De esta manera al promediar siempre 3 soluciones se minimiza ese efecto a la vez que se llega a velocidades de entre 6 y 10 fps.



Rebotes con color.

Uno de los efectos del radiosity es que la luz al rebotar contra un objeto, sale de un color preciso, con lo cual los objetos son bañados por diferentes colores provenientes del la escena y no solo por la luz blanca original.
En la implementacion el color de cada objeto esta previamente almacenado (no esta tomando el color exacto donde rebota, pero no seria un impedimento generarlo offline).
Para visualizarlo más graficamente se modificó el algoritmo para la primera luz sea roja pura, las luces secundarias sean verdes, y las terciarias azules:




Se ve claramente como la pared donde pega la primer luz se ve en un tono rojo intenso, luego rebota la luz de color verde, que llena la pared izquierda y el piso de un tono verde. El efecto de las luces terciarias es mucho mas leve, pero se puede notar en la base de las columnas y en el techo.

Ejemplo con 30 rayos entre 13 y 14 fps y el mismo ejemplo con 60 rayos aprox 6 fps: