Best use of 1 Infinite Loop

Qiming Hou
hqm03ster@gmail.com
http://www.houqiming.net

Judges' comments:

To build:

make hou

To run:

./hou [scene-file-name] [options]

Follow the instructions in stdout, preferably with an auto-refreshing PPM image viewer ready.
Refresh the image every time the output refreshes, all effects should be more or less recognizable when you see 16.

Try:

./hou BIG
./hou old_default.scene BIG
./hou otherroom.scene
./hou otherroom.scene NAIVE

Selected Judges Remarks:

You could consider that this program violates the source code size limit. This is because the first compliation of this program is really just a decompressor to generate the real source code of the program.

This program will loop infinitely while progressivly refining a raytraced image.

Author’s comments:

Using hou

This program is a programmable rendering engine with a built-in default scene. The standard command line is:

./hou [scene-file-name] [options]

As hou runs, it writes a progressively refining image to a ppm file specified in the scene. The initialization may take a while, but once it’s done, a rough preview should be available in seconds. Leave hou running for the night, and you get a high quality result like the attached *.jpg files. Kill hou manually after you’re satisfied with the image quality.

To save time and energy for the judges, rendered images for all provided scenes are provided as attached files.

Features

Abuse of the rules

Self-imposed restrictions

Comments and why obfuscated

Spoiler

 3225  3225  3225  9  9    3225  3225
 1     1  1  1  1  1  1    1     1  1  
 4225  1226  1  1  1  1    1222  1226  
    1  1     1  1  1  1    1     1 1   
 4226  1     4226  8  4222 4226  1  1

The program consists of a recursive-descend interpreter, a 3DDDA (3D Discrete Differential Analysis) ray tracer, a PSSMLT (Primary Sample Space Metropolis Light Transport) light path sampler, all squeezed into the size limit using a PPM compressor (Prediction by Partial Matching, and yes, the output format is chosen for the pun).

PSSMLT uses the Metropolis-Hasting algorithm to sample a 32D unit hypercube. Each point in the hypercube is interpreted as a sequence of random numbers, and is sent to a path tracer to generate a light path. The point’s Metropolis-Hasting energy is then defined as the corresponding path’s contribution value to the final image. Since each path is sampled with a probability proportional to its energy, the sample distribution directly corresponds to the final image, which can then be produced as a simple per-pixel histogram of all generated paths. The robustness comes from a state mutation strategy that actively tries to explore the neighborhood of high energy peaks (e.g. paths that happen to hit the light source in otherroom.scene). In addition, a rudimentary form of lens path stratification is added to balance the attention each pixel receives. The Metropolis-Hasting process completely avoids the tell-tale pixel sampling loop required in most other image generation methods.

The 3DDDA tracer is chosen for scalability: its performance doesn’t get much worse as scene complexity increases. Another benefit is that with the DDA code in place one can naturally use hierarchical grids as an acceleration structure. The downside, of course, is that the setup involves quite a few divisions, which naturally turns into division-by-zeros. Fortunately, the IEEE754 standard has a nice set of rules just for this purpose and the arithmetics are organized in a specific way to take advantage of this. The shader interpreter component is relatively straightforward, just an expression evaluator stripped to the bare minimum – it doesn’t even support numerical constants natively. A final little bit is a just-good-enough PRNG (Pseudo Random Number Generator) to replace the low precision Windows rand() and the non-C99 Unix drand48(). An overnight session would run through its short period many times, but that doesn’t necessarily map to the same set of paths in PSSMLT. After all, Metropolis et al. used an even worse PRNG in their 1953 paper.

The PPM compressor uses statically weighted fixed order contexts with an arithmetic encoder tweaked for iocccsize. The encoder emits octet-space pairs where each octet encodes ~6.5 bits of information and each space encodes 2 bits (thanks to the generous definition of “space” in iocccsize.c). The compressor actively shuffles the variable names around until the compressed string happens to contain enough “{}; ” to pass the final iocccsize test. There are a few other tweaks:


Creative Commons License

© Copyright 1984-2015, Leo Broukhis, Simon Cooper, Landon Curt Noll - All rights reserved
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.