Me ha parecido muy interesante el post de Shawn Hargreaves preguntándose si el SpriteBatch es una máquina de Turing, implementado para demostrarlo el juego de la vida y lo ha hecho en http://blogs.msdn.com/b/shawnhar/archive/2011/12/29/is-spritebatch-turing-complete.aspx.
Aquí tenéis la traducción:
Inspirado por una serie de twitts:
Scionwest- @shawnhargreaves @nickgravely Cómo va el post procesado en WP7? He visto a gente hacer efectos de Bloom y eso no es parte de WP7?
nickgravelyn – @Scionwest Los shaders no están disponibles, pero he visto ejemplos de post procesado muy inteligente con custom shaders. Teóricamente puedes hacerlo basándote en la CPU, pero también puedes usar blend states para conseguir efectos increíbles.
(Es un tema muy interesante y algún día volveré a él).
Me encontré a mi mismo pensando “bueno, seguro que puedes implementar bloom,ya que el subconjunto de gráficos Reach de Windows Phone son Turing complete, así que podríamos hacer lo que queramos con el suficiente ingenio. Puede que no se fácil, eficiente o con sentido, pero todo es posible…”
Así que pensé ¿es realmente posible?
Podemos sumar y restar a traves de blend states, y realizar comparaciones con AlphaTestEffect, lo que parece ser suficiente para permitir crear algoritmos arbitrarios (al menos si ignoramos cosas mundanas como el tiempo y el espacio 🙂 ¿Pero puedo “probar” que XNA en Windows Phone es suficiente para permitir una computación en la GPU Turing complete?
El juego de la vida de Conway ha probado ser una forma universal de máquina de Turing, así que me puesto a ver si puedo implementarlo en la GPU sin usar custom shaders.
A partir de la plantilla de Game por defecto, he declarado dos rendertargets para que mantengan el estado de la simulación:
const int width = 256; const int height = 128; RenderTarget2D currentState; RenderTarget2D nextState;
Además otros dos objetos de ayuda:
AlphaTestEffect alphaTestEffect;
Texture2D singleWhitePixel;
Estos objetos los inicializo en el LoadContent:
currentState = new RenderTarget2D(GraphicsDevice, width, height, false, SurfaceFormat.Color, DepthFormat.Depth24Stencil8); nextState = new RenderTarget2D(GraphicsDevice, width, height, false, SurfaceFormat.Color, DepthFormat.Depth24Stencil8); alphaTestEffect = new AlphaTestEffect(GraphicsDevice); singleWhitePixel = new Texture2D(GraphicsDevice, 1, 1); singleWhitePixel.SetData(new Color[] { Color.White });
Para hacerlo más interesante, el juego de la vida debe ser inicializado a algo más que simples ceros. Este código (al final del LoadContent) hace una inicialización de los datos iniciales:
Color[] initialData = new Color[width * height];
initialData[3 + 1 * width] = Color.White;
initialData[3 + 2 * width] = Color.White;
initialData[3 + 3 * width] = Color.White;
initialData[2 + 3 * width] = Color.White;
initialData[1 + 2 * width] = Color.White;
currentState.SetData(initialData);
Para un estado inicial más interesante, añadimos esto (ántes de la llamada currenState.SetData) para aleatorizar las células:
Random random = new Random(); for (int i = 0; i < 10000; i++) { initialData[random.Next(width * height)] = Color.White; }
El código del Draw es simple. Usa SamplerState.PointClamp para escalar el estado de la simulación ha pantalla completa, sin ningún filtro:
SimulateLife();
GraphicsDevice.Clear(Color.CornflowerBlue);
spriteBatch.Begin(SpriteSortMode.Deferred, null, SamplerState.PointClamp, null, null);
spriteBatch.Draw(currentState, GraphicsDevice.Viewport.Bounds, Color.White);
spriteBatch.End();
Vale, esa era la parte repetitiva. Ahora ¿cómo vamos a implementar el método SimluateLife()? La wikipedia define las reglas como:
- Cualquier célula viva con menos de dos vecinos muere, está despoblada.
- Cualquier célula viva con dos o más vecnios vive hasta la próxima generación.
- Cualquier célula viva con más de tres vecinos muere, como si fuese por superpoblación.
- Cualquier célula muerta con exáctamente tres vecinos se convierte en célula viva, se reproduce.
Pero he creido conveniente reagruparlas de manera diferente pero equivalente:
- Regla 1: Si hay dos vecinos vivos, se mantendrá el estado actual de la célula.
- Regla 2: Si hay tres vecinos vivos, la célcula revive.
- Regla 3: En otro caso la célula se muere.
Ok, vamos a hacerlo, SimluateLife comienza dibujándose en le renderTarget nextState, y seteando el AlphaTestEffect para que sólo acepte píxeles con un alpha mayor de 128, por ejemplo: las células que están vivas:
GraphicsDevice.SetRenderTarget(nextState);
GraphicsDevice.Clear(Color.Transparent);
Viewport viewport = GraphicsDevice.Viewport;
Matrix projection = Matrix.CreateOrthographicOffCenter(0, viewport.Width, viewport.Height, 0, 0, 1);
Matrix halfPixelOffset = Matrix.CreateTranslation(-0.5f, -0.5f, 0);
alphaTestEffect.Projection = halfPixelOffset * projection;
alphaTestEffect.AlphaFunction = CompareFunction.Greater;
alphaTestEffect.ReferenceAlpha = 128;
Vamos a contar cuantos vecinos vivos tiene cada célula, acumulando este valor en un buffer (que se había limpiado con zeros). Hacemos esto dibujando la textura de simulación 8 veces, desplazando un pixel arriba a la izquierda, arriba, arriba y derecha, izquierda, etc. Usamos un blend state que prevenga de dibujar nada al buffer de color, ya que sólo estamos interesados en la generación de símbolos. Este código combina el AlphaTestEffect (que elimina los pixeles de los vecinos muertos) y el buffer de símbolos (que cuenta cuantos vecinos han pasado el test del alpha):
spriteBatch.Begin(SpriteSortMode.Deferred, blendNone, null, stencilAdd, null, alphaTestEffect); spriteBatch.Draw(currentState, new Vector2(-1, -1), Color.White); spriteBatch.Draw(currentState, new Vector2( 0, -1), Color.White); spriteBatch.Draw(currentState, new Vector2( 1, -1), Color.White); spriteBatch.Draw(currentState, new Vector2(-1, 0), Color.White); spriteBatch.Draw(currentState, new Vector2( 1, 0), Color.White); spriteBatch.Draw(currentState, new Vector2(-1, 1), Color.White); spriteBatch.Draw(currentState, new Vector2( 0, 1), Color.White); spriteBatch.Draw(currentState, new Vector2( 1, 1), Color.White); spriteBatch.End();
Este código usa dos objetos de estado:
static readonly BlendState blendNone = new BlendState { ColorSourceBlend = Blend.Zero, ColorDestinationBlend = Blend.One, AlphaSourceBlend = Blend.Zero, AlphaDestinationBlend = Blend.One, ColorWriteChannels = ColorWriteChannels.None, }; static readonly DepthStencilState stencilAdd = new DepthStencilState { DepthBufferEnable = false, StencilEnable = true, StencilFunction = CompareFunction.Always, StencilPass = StencilOperation.Increment, };
Ahora tenemos nuestro rendertarget limpiado a cero (lo que significa que están todos muertos, así hemos implementado la tercera regla), mientras que stencil contiene un contador de las celdas vecinas vivas. Ahora vamos a dibujar una copia del estado de la simulación, usando la galería de símbolos para aceptar sólo aquellas células que tengan a dos vecinas vivas, implementando así la regla 1:
spriteBatch.Begin(SpriteSortMode.Deferred, BlendState.Opaque, null, stencilDrawIf2, null); spriteBatch.Draw(currentState, Vector2.Zero, Color.White); spriteBatch.End();
El último pintado implementa la regla 2 renderizando en blanco (lo que significa que está vivo) aquellas células que tienen 3 vecinos:
spriteBatch.Begin(SpriteSortMode.Deferred, BlendState.Opaque, null, stencilDrawIf3, null); spriteBatch.Draw(singleWhitePixel, viewport.Bounds, Color.White); spriteBatch.End();
Son necesarios dos objetos de estado:
static readonly DepthStencilState stencilDrawIf2 = new DepthStencilState { DepthBufferEnable = false, StencilEnable = true, StencilFunction = CompareFunction.Equal, ReferenceStencil = 2, }; static readonly DepthStencilState stencilDrawIf3 = new DepthStencilState { DepthBufferEnable = false, StencilEnable = true, StencilFunction = CompareFunction.Equal, ReferenceStencil = 3, };
Finalmente, la función SimulateLife quita el rendertarget, intercambia los dos rendertargets, reemplazando el estado actual con el nuevo que hemos calculado:
GraphicsDevice.SetRenderTarget(null); Swap(ref currentState, ref nextState);
La función Swap es tan simple como:
static void Swap<T>(ref T a, ref T b) { T temp = a; a = b; b = temp; }
¿Ha funcionado?
Chachán!
Traducido por: Juan María Laó Ramos
juanlao 