Wednesday, October 1, 2014

Program your shaders in Webfunge

I released Webfunge at the Evoke a couple of weeks ago. I made it because on the previous Revision, someone made a shader interpreter in Scheme, and wow! If it's possible in Scheme then it's possible in Befunge. This is the perfect opportunity to finally make a project in Befunge.

I have always loved Befunge for three reasons. The most important one is that code in Befunge lives in a n-dimension space, whereas all other languages, as far as I know, are only one-dimensional. It's a modular storytelling programming language! Code has a topology, and unique patterns emerge that couldn't exist with any other language.

The second reason is that it's based on a stack. It means that everything happens with a stack of values, and computations are eventually stack manipulations. For instance, the add instruction pops two values off the stack, and pushes back the sum. Most code written today falls in the C-family, that doesn't compute that way, so it's really refreshing. Lua uses a similar, although simpler stack, and it has been an inspiration source for Webfunge.

The last reason I love Befunge is that people don't understand someone could love it. Eventually I fell in love when I read this code:
12481> #+?\# _.@
which is a 1..16 random number generator. If ever you try to make sense of this, beware! It's a trap!

Webfunge isn't compliant with the specs of Befunge. For one, some instructions are missing from Befunge, for instance replace in stack (which pops an index off the stack, then pops a value, then sets the stack at index to this value) doesn't exist in Befunge, whereas it exists in Lua. Moreover, shader code heavily relies on number and vector operations, so I added some convenient instructions to deal with them. Obviously I hadn't planned these changes right from the start, I started the project by doing a simple interpreter. And at the end, it can do all kind of shader stuff, like raytracing.

Once the Proof Of Concept was validated, it had been optimized a lot. The main tips are:
  • don't use an Array because they are type agnostic and it's slow, use all sort of UInt8Array and Float32Array with an index pointing to the last element of the array
  • avoid allocations (i.e. garbage collections)
  • use Web Workers to distribute the load
It's a lot faster than at the beginning, however it will never perform as fast as WebGL shaders...

I even started a static compiler, but it would take me too much time to finish it. For now it can convert
0y2y/ 1y3y/ 4y @
function getColor(x, y, offset) {
  output[offset    ] = (x/width);
  output[offset + 1] = (y/height);
  output[offset + 2] = time;
  output[offset + 3] = 256;
which uses the original interpreter's variables.

The basic idea is to build an AST and generate JS code when the IP path is known, and to bail out to the original interpreter otherwise. Some ideas:
  1. A path is defined after the IP's delta is set, in particular using >, v, >, and ^. Jumps to subroutines also define paths. There is also a path at (0, 0) toward east, as it's the beginning of the program.
  2. Each path is executed inside a case of a switch block. If the path ends with a change to the IP's delta, then loop on the switch again, otherwise bail out to the interpreter.
  3. Stack values have type constant or expression. Constants are useful for reducing code complexity. In the code above, the y instruction popped the constant value 0, thus acceded stack[0] which contains the expression value x, so the result of 0y is x.
  4. If it's impossible to bail out, remove the interpreter part. It would even be able to compile into GLSL, but then, none of the unique features of Webfunge would have been used, so there's no point doing it.
If you want to continue this, feel free! Take a look at the repo on Github

No comments:

Post a Comment