A ray tracer in Brainfuck: a 23MB program that renders one pixel a minute

The author of the blog epestr.com took a line in the CMake tutorial as a challenge: ray-tracers, it says, have even been written in the CMake Language, though that is not recommended practice. He had already written a ray tracer and rewritten it for the GPU, so he picked Brainfuck, the simplest language he knows, and set out to reproduce the image from the Metal section of Ray Tracing in One Weekend. The code is on GitHub as mTvare6/rayfuck.

Eight commands and one tape

Brainfuck has eight operations and one data structure: an infinite tape of cells, each holding an unsigned byte. No register is wider than one cell, no instruction touches two cells at once, and addition and multiplication are not instructions at all. Real numbers therefore had to be encoded by hand: each value takes four cells in a signed Q16.16 fixed-point format, 16 bits of integer and 16 of fraction, for a resolution of 1/2^16 and a range of roughly [-2^15, 2^15). A cheaper Q8.8 was rejected as too narrow, because the sphere acting as the ground needs a radius of 1000 to look flat.

Rebuilding the arithmetic

The 23 megabytes of Brainfuck were generated, not typed: the program is turned into an SSA-like form and then parsed into a small intermediate DSL of about thirty operations such as copy, mul, sqrt, if and while. Two primitives carry most of the work: move ([->+<]) drains a cell into its neighbour and copy ([->+>+<<]) leaves the value in two. Multiplication is repeated addition over the four fixed-point cells, and division follows school long division in base 256, subtracting the divisor at most 255 times per cell.

The maths library was rebuilt from the same blocks. Random numbers come from a tiny generator, A = (5*A + 1) % 256, whose full 256-value period suits the supersampling anti-aliasing in the scene. Heron's method lost the square root to its division and a Taylor series fitted poorly below 0.305, so the author used long division.

One pixel a minute

The finished program is 23MB, larger than the 0.9MB image it renders, which the author notes makes Brainfuck a poor compression technique. Speed is about 100 ray calculations per minute, or one pixel per minute, so a 400×225 image would take an estimated 62.5 days on his laptop. By the time of writing 1229 of about 90,000 pixels had been produced, and only 10 differ from the C reference, mostly by a value of one.

After a comment on his Reddit thread suggested fork/join primitives, the author improved his JIT interpreter instead and reported a massive speed-up; the real render, he says, now looks a bit like a Van Gogh painting, probably because of precision errors.