JS1k-Julia-Fractal Browser Explained

Posted by Doug Haber on 2015-08-05
Back in 2013, I made a tiny Julia fractal browser with stripe average coloring support for the JS1k Spring Competition. In this post I will release the code along with some explanations of how it works, and how it was made small enough to fit in 1024 bytes.



Here is the description of the program, from the JS1k entry:
A Julia Fractal Browser with Stripe Average Coloring.

Controls:
  * Use the mouse wheel to zoom in and out.
  * Press the "Next" button to cycle through available fractals.
  * Press the "Rand" button to randomize the fractal settings.
  * Resize your window to grow the viewport. Full screen is great,
    though it may effect performance.

Every time the page is loaded initial settings are randomized.

Technically this might not be stripe average coloring. Shortcuts were
taken to make it fit in 1k. It is somewhat close though.

JSCrush was used to get down to the 1k limit.

Click here to launch
JS1k Julia Fractal Browser on JS1k.com

Overview

The JS1k competition challenges developers to create an interesting program in JavaScript that is 1k or less in size. I had previously written the full-featured fractal browser, Leshy Fractal Explorer, and thought it would be fun to try to get something much smaller to produce some amazing fractal images.

To help reduce the space wasted on referencing some commonly needed objects, the JS1k competition provided a shim that automatically sets variables named a, b, and c to the 2d context, the body, and the canvas element.
  var b = document.body;
  var c = document.getElementsByTagName('canvas')[0];
  var a = c.getContext('2d');
I really like stripe average coloring, which provides an alternate way of rendering a fractal that often looks amazing. Julia fractals seemed like a good choice. They work well with that type of coloring, and their formula uses two constants which can greatly alter the appearance of the fractal. By using Julia fractals, I was able to provide several of these pairs of constants to allow for cycling through different modes (or sets.) The "Next" button in the program cycles through the pre-defined constants.

I thought it would be nice if there was a large variety of different rendering styles to explore. There wasn't room to provide a proper UI, so instead, I added a "Rand" button to choose random settings. This randomizes the color scheme, as well as the number of stripes and an orbit multiplier.

I wanted the program to be able to render high-quality fractal images and to be very responsive. To make this work, I ended up going with a multi-pass renderer. This draws the fractal at different quality levels. First, it makes a very low quality draw of the entire fractal, then it goes row by row, increasing the quality level each time a render completes. In the interest of space, later passes don't take advantage of calculations from earlier passes.

There were two features that didn't make the final cut, since I was having trouble getting them to fit in 1024 bytes. The first was anti-aliasing, which would use multiple samples per pixel to smooth out the image. (You can still get some "poor man's anti-aliasing" by zooming out with your browser's zoom settings. This will impact performance. You can right click and select "Save Image as" to save high-resolution images of the fractal.)

The second feature that didn't fit was panning, which allowed exploring the fractal by holding down a mouse button and dragging. Without the ability to pan, you are limited to using the mouse-wheel and cursor to zoom towards the areas you want to see.


Design Philosophy

Heavily golfed code can be difficult to work with, so I chose to first write things in a clear and normal way, and not concern myself too much with size optimization. Knowing that I would be minifying the source, I didn't hesitate to use variables with long and clear names. I even used strict mode while developing, just to help catch mistakes.

Once the program was working, a loop began where I repeatedly would make some changes to reduce the size, and then recompile it down to see the results. When it was finally under the size limit, it came in at 1023 bytes. I'm certain that it can be further optimized, but once I had it working in the allowed size I didn't see any reason to go further. The whole project took roughly six hours of non-continuous work.

To compile it down, I used Google's Closure Compiler with ADVANCED_OPTIMIZATIONS enabled. The code was then sent it through a Perl filter which further removed things like 'var' statements that were just wasting space. Any trailing semi-colon was removed at this point, since it just wastes a byte. The script also changed numbers like 0.1 to just .1, and replaced a few things, which are described below. Finally, the result were passed to JSCrush which used its dictionary technique to further optimize the size.

The Code

If you just want to see the code, the best place to view it is on GitHub. An explanation of some of the details and flow of the code follows below.

Please keep in mind that this was written for a code golfing competition. That means the objective is to make the code as small as possible while still functioning, with no regard for writing it cleanly. Many of the techniques and styles found here should not be used when writing code that needs to be maintained.

The start - Global Variables and Strict Mode

  "use strict";
To begin, the first line is "use strict." This is just for development, and is removed in the final version. By using strict mode we are able to catch certain types of mistakes early on, which helps cut down on development time.
  // State
  var w, h, imageData; // Width, Height, and ImageData
  var xPosition, yPosition, zoom; // Fractal viewport location
  var stripes, orbitMultiplier;
  var currentRow // When drawing one row at a time, the row we are on
  var scale; // When drawing, the scale rate we are using
  var c2, a2; // Temporary canvas (c2) and context (a2)
  var timeoutId; // Stored timeoutId to cancel draw requests with
  var colorR, colorG, colorB; // Color values to use when drawing
  var buf8, buf32; // 32 bit and 8 bit buffers for accessing the imagedata
Here are all the global variables. After compiling, each and every one of these definitions is pruned out, since 'var' statements don't add anything necessary. While global variables are often frowned upon, this is for a code-golfing competition, and so anything goes, as long as it saves space.
  // The mode determines the Julia constants to use.
  // They are stored as pairs in the modes array, so mode 1 is the elements with
  // the index 0 and 1, and mode 2 has the indices 2 and 3, etc.
  var currentMode;
  var modes = [ -0.7, 0.3, 0.285, -0.01, -0.8, 0.16, 0.4, 0.4 ];
These "modes" are the various pre-defined Julia sets that are available to cycle through with the "Next" button. The adjacent pairs of numbers provide the Julia constants to be used.
  // Temp variables
  var x, y, tmp, tmp2;
These 4 temporary variables are used for different things in different places. They effectively are used as registers, so that less variables need to be defined.
  // Abbreviations
  var MATH = Math;
  var SIN = MATH.sin;
  var RANDOM = MATH.random;
  var ATAN = MATH.atan;
  var SET_TIMEOUT = setTimeout;
  var FF = 0xff;
In the compiled version, each of the symbols becomes a single character. These references are used to reduce the number of characters needed for common expressions. For example, ATAN may become z, and so every time we need to use Math.atan(), we just need z(), and so we save a few bytes.

Calculating the Fractal and Rendering

  function draw() {
     var zx, zy, orbit, totalOrbits;

     clearTimeout(timeoutId); // Cancel any other scheduled draws
The draw function begins with some variable definitions. These local variables are just for keeping the development clean. In the compiled code, they are removed.

The variable timeoutId is used to store the id of any pending draw. When a draw call occurs, we always cancel any other pending draw, ensuring that the latest draw call is in control. If timeoutId is invalid when calling clearTimeout(), that has no negative effect, so to save space we don't bother checking its validity.
    // Draw one row of the fractal
    for (x = 0; x < w / scale;) {
	// y is the iteration count
	totalOrbits = orbit = y = 0;

	zx = xPosition + ((w / h) / w * x * scale) / zoom;
	zy = yPosition + (1 / h * currentRow) / zoom;
In this loop we draw a single row of the fractal. The temporary variable 'y' in this context is used as an iteration counter. The use of chained equals statements is done to save a few bytes while setting multiple variables to the same value.

The xPosition and yPosition variables refer to our current coordinates within the fractal. The zx and zy variables refer to the real and imaginary parts of the complex number z. In the Julia set z starts as z = x + yi.
  	while (zx * zx + zy * zy <= 200) { // While we are less than the bailout of 200
	    tmp = zx;

	    zx = (zx * zx - zy * zy) + modes[tmp2 = (currentMode % 4) * 2];
	    zy = (tmp * zy + tmp * zy) + modes[tmp2 + 1];

	    if (++y > 9) {
		totalOrbits += orbit = SIN(stripes * ATAN(zy, zx));
	    }
	}
Here we calculate the value for a given point within the fractal. The modes[] array stores the Julia constants for our current Julia set in two adjacent locations in the array.

The currentMode variable is always incremented when the mode changes. It never resets to 0, since that would require an extra statement. Instead, we use modular division to take whatever the mode value is set to, and convert it back to a value from 0 to 3.

With the 'if (++y > 9) {' the iteration counter 'y' is incremented, and we skip counting the first 9 iterations against total orbits. When using the stripe average method for coloring, skipping some early iterations can have a nice effect on the final image, so 9 was chosen to provide that.

You might notice that while the loop is escaped on a large bailout, there is no escape on a maximum number of iterations. This was done to save a few bytes on the extra conditional.
	// Do a 32 bit write of the color
	buf32[x++] =
	    ((FF << 24) + // Alpha is always 0x255
 	     ((FF * (0.5 + SIN((tmp2 = ((orbitMultiplier * totalOrbits - orbit) / y * 0.8)) + colorR) / 2)) << 16) +
	     ((FF * (0.5 + SIN(tmp2 + colorG) / 2)) << 8) +
	     ((FF * (0.5 + SIN(tmp2 + colorB) / 2))));
    }
For the rest of the code we finish calculating the color for a given pixel using an abbreviated stripe average method. The value is placed into buf32 so that we can perform a 32 bit write. The 32 bit write provides a big performance boost over doing 8 bits at a time. This is used as an imageData buffer, and so the image is stored linearly within the buffer and we only need to increment x to find the next pixel, wherever that may be.

To save space, I assumed everyone running this will be using little endian. In big endian, the colors will be all wrong. The JS1k rules didn't mention anything about endian, but I thought this would probably be a safe assumption.
    imageData.data.set(buf8);

    // Write to the temporary canvas buffer, and then draw the scaled results onto the real canvas
    a2.putImageData(imageData, 0, 0);
    a.drawImage(c2, 0, 0, x, 1, 0, currentRow, w, scale);
A second canvas 'c2' along with its 2d context 'a2' is used as a draw buffer. The image data gathered for each pixel is first written to the off screen canvas, and then that section of the off screen canvas is scaled and written it back to the displayed canvas.

There is another optimization that can be done where only one canvas is used, and draw the data written to that gets overwritten by drawing that section scaled onto the canvas. I've used that with some success elsewhere, but the JS1k rules required it to work well with the Opera web browser, which wasn't handling it well.

For some reason this technique works perfectly in Chrome, but ends up drawing unnecessary lines between elements in Firefox. I have a few guesses as to why and how to fix it, but it didn't seem important enough for the competition.
    currentRow += scale;

    if (currentRow < h && scale > 21) { // At the highest scale, keep drawing until we've filled the screen
	draw();
    }
    else if (currentRow < h) { // At other scales, schedule new draws
	timeoutId = SET_TIMEOUT(draw, 0);
    }
    else if (scale > 1) {
	if (scale > 9) {
	    scale = 8;
	}
	else {
	    scale /= 2;
	}

	timeoutId = SET_TIMEOUT(draw, currentRow = 0);
    }
}
At this point a single row has been drawn, and so we need to decide what happens next. When in the lowest quality scale, we want a full-screen to be drawn at once, so that the screen always contains something full to look at. To do this draw() is just called recursively. Each row will call draw() to render the next row. If there were a whole lot of rows, this could blow the stack, but since we are in the low quality scale (drawing 1/22nd of the rows,) it is fairly safe.

In any scale but the lowest quality one, a drawing of the next row is scheduled. This pause isn't great for performance, but it helps keep the program very responsive.

In the event where all rows of the image area drawn but the scale is still over 1:1, the scale is cut in half, and drawing from the top at the new scale is scheduled. An adjustment was made so that from the initial quality of 22 we adjust down to 8 to bring us to even numbers. With even numbers, we can always divide by 2 to get the next scale.

Helper Functions

function onScroll(e) {
    // When the mouse wheel scrolls, zoom in or out towards or away from the mouse position
    var x = e.clientX;
    var y = e.clientY - 35;
    var wx = xPosition + ((w / h) / zoom) / (w / x);
    var wy = yPosition + (1 / zoom) / (h / y);

    if ((e.wheelDelta || -e['deltaY']) > 0) {
	zoom *= 1.3;
    }
    else {
	zoom /= 1.3;
    }

    xPosition = wx - ((w / h) / (w / x)) / zoom;

    newDraw(yPosition = wy - (1 / (h / y)) / zoom);
}
This function handles mouse-wheel events. When the wheel is turned the viewport should either scroll towards or away from the cursor, depending on the direction the wheel turned. Unfortunately, browsers historically weren't consistent on how wheel events worked, so we need to check e.wheelDelta and e.deltaY to get it working everywhere. Technically, we are throwing away information about how much the wheel turned, and treating any amount the same, but for JS1k that seemed acceptable.

Since wheel events change the viewport, the current draw cycle is invalidated, and a new one begins. This is taken care of by the newDraw() function.

You may notice in several places we call functions that take no parameters with parameters, such as in the above newDraw() call. This is done to save 1 byte. Normally statements need a 1 byte semi-colon delimiter. Placing a statement in parenthesis allows us to avoid that cost for a single statement.
function newDraw() {
    // Begin a new scaled lowest quality drawing cycle
    currentRow = 0;

    draw(scale = 22);
}
This little helper function begins a new drawing cycle. Whenever any settings invalidate the viewport, this gets called. It resets the currentRow and scale and then calls the draw() function. The draw() function immediately does a low quality render of the whole fractal at the lowest scale, and then schedules in the higher quality drawing passes.

Once again, we use the trick of placing a statement inside a function call, despite the function taking no parameters. This saves us 1 byte, since an extra delimiter is not needed.
function resize(event, newMode) {
    // Resize the canvas to fill the window and start a new drawing cycle
    if (newMode) {
	yPosition = xPosition = -1.4;
	zoom = 0.4;
	currentMode++;
    }

    c2 = c.cloneNode();
    a2 = c2.getContext('2d');

    w = c2.width = c.width = innerWidth;
    h = c.height = innerHeight - 35;

    buf8 = new Uint8Array(tmp = new ArrayBuffer(w * 4));
    buf32 = new Uint32Array(tmp);

    newDraw(imageData = a.createImageData(w, 1));
}
The resize() function is called whenever the window resizes, as well as on initialization. The function makes the canvas resize to fill the window. It also creates a temporary draw buffer c2 and it's 2d context a2.

The function takes in the event and newMode. The original code bound resize to an event, making the event variable necessary. I think things were changed enough where this could be safely removed, and allow for saving a couple more bytes on the callers.

The newMode flag, when set, tells the function to cycle to next Julia set mode. The offset -1.4 is hard-coded as a "good enough" value for centering the fractal. Depending on the size of the window, this may not be perfect.

To create the new canvas, we use cloneNode() instead of document.createElement('canvas'). Doing it this way saves us 18 bytes.

The 35 byte offset on the height was a bit arbitrary. There needs to be room to fit buttons up top, and a vertical scroll bar never should be shown. The number 35 seemed safe across browsers for fitting everything, though it does leave a little white stripe at the bottom of the window. Hard-coding 35 took a lot less code than calculating the space dynamically.

The resize function is also responsible for creating a buffer for storing our pixels. It creates buf8 and buf32, so that we can do 32 bit writes, and use the imageData.set() function with the buffer via buf8.

function randomize(noDraw) {
    // Choose random colors, number of stripes, and orbitMultiplier, and then start a new draw
    colorR = RANDOM();
    colorG = RANDOM();
    colorB = RANDOM();

    stripes = RANDOM() * 25 + 0.5;
    orbitMultiplier = RANDOM() * 35 + 6;

    ! noDraw && newDraw();
}
This function randomizes the various settings for the fractal. It is called when the program starts and when the "Rand" button is pressed. For stripes and orbitMultiplier, a range of values likely to produce decent results was chosen.

Normally, when randomizing the settings this is followed by a new drawing cycle. The noDraw flag allows this to be avoided, which is necessary when starting up, since resize() hasn't yet been called to initialize the necessary variables for the first drawing cycle.

Flags in this program are only concerned with the truth or false evaluation of the variable, so boolean typed values are not used. For example, instead of true, we generally use 1, or anything else that evaluates to true.

Initialization

// Create the buttons as strings
tmp = "<button onclick='";
b.innerHTML = tmp + "resize(0,1)'>Next</button>" + tmp + "randomize()'>Rand</button>";
b.appendChild(c).onwheel = c.onmousewheel = onScroll

randomize(1); // Set the initial values randomly
// Initialize variables to 0, and call resize(0, 1), which begins the first draw
resize(timeoutId = b.style.margin = currentMode = 0, 1);

// Junk to help with replacing strings after minification
window['function_randomize'] = randomize;
window['function_next'] = resize;
This code is run once when the program starts up. First, it adds the buttons. The smallest way of doing that is to place it into the page using innerHTML. The tmp variable is used to store the repeated string, and then the HTML for the buttons is forced into the body through the shim's pre-defined b variable.

Since the body was overwritten through innerHTML, the canvas no longer exists on the page. To fix this, it is added it back, and the same statement binds wheel events that should work for each browser.

Next, the fractal settings are randomized with 1 passed in to prevent drawing from occurring. Then, resize() is called. In calling resize(), we set a few things to 0, and enable the newMode flag to cause the viewport to be reset and the initial draw to occur.

The final two lines are used for capturing the symbols that the randomize() and resize() function are minified to. After minifying, those values are used to replace the values in the above string that innerHTML is set to. Those function names then take up a single byte. Other than as a convenient way of reading back the symbols, those lines aren't needed, so they are removed before passing the final code to JSCrush.

Conclusions

The source code is available on GitHub under a BSD license.

This was my first time entering JS1k, and it was a lot of fun writing something for it, and learning to make it fit in under 1k. I hope at some point in the future to find time to enter another one.




comments powered by Disqus

Featured Apps


  • Leshy SpriteSheet Tool
  • Sprite Sheet Packer, Mapper, and Editor
  • Leshy SFMaker
    Sound FX Generator
  • Leshy Tuner
    HTML5 Chromatic Instrument Tuner
  • Leshy Fractal Explorer
    Web Based Fractal Browser
  • Leshy SpriteSheet Animator
    SpriteSheet Animation Manager