Iterating

Iterating is described in the paper, however it’s worth clarifying because it’s the most important part of the algorithm. Further, most academic descriptions of it oversimplify where the algorithm stands today after years of work by various projects.

Xform Application

The classic Iterated Function System works like the following pseudo code:

  • x and y = random numbers between -1 and 1.
  • Pick a random xform from the Ember, with biases specified by their weights.
  • Calculate tx and ty by applying the selected xform’s pre affine transform to x and y:
tx = Ax * By + C
ty = Dx * Ey + F

Pass the transformed point to each of the variations and sum the results. Note that this does not change the transformed points at all, they are only used as inputs.

vx,vy += var1(tx, ty)
vx,vy += var2(tx, ty)
vx,vy += var3(tx, ty)
...
vx,vy += varN(tx, ty)

ox, oy = vx, vy

If a post affine transform is present, apply it to the result calculated from summing the outputs of the variations above.

ox = pAvx * pBvy + pC
oy = pDvx * pEvy + pF

Now that the new point has been calculated, compute the new color coordinate. As the paper states, the coordinate is the one specified in the currently chosen xform, blended with the one from the previously chosen xform. It incorrectly states that blending is achieved by adding the current and previous coordinates and dividing by 2. Not only is it calculated differently, but the hard coded value of 2 is actually the user specified color speed parameter of each xform. The real calculation is:

newindex = colorspeed * thisindex + (1.0 - colorspeed) * oldindex

Positive values for colorspeed have the effect of pulling the index toward the current xform’s index, and negative values will repel the index.

It’s important to note that the colors themselves are not being blended, only their indices in the palette are.

At this point, we have the final output point ox,oy to be plotted to the histogram. However, we can’t use it just yet. There is a slight possibility that the calculated value was not valid. This is detected by checking for it being very close to infinity, or very close to zero. If either are the case, 5 attempts at the following correction method are tried:

  • Pick a new input point with x and y each being a different random number between -1 and 1.
  • Pick a new random xform and apply it.
  • Keep color index from the first xform that was applied, which originally gave us the bad values.

If after 5 attempts, a valid point is not produced, the output point is assigned random numbers between -1 and 1. The number of bad values are saved for statistical use later.

After computing this point, apply a final xform if one is present. Plot its output next, however do not feed it back into the iteration loop. Rather, only feed the output of the randomly selected xform above to the next iteration of the loop.

Plotting

Once we have the┬ánew point, it’s time to plot it. First, let’s review the information the point contains:

  • An x,y coordinate in Cartesian space.
  • A color index from 0-255.

The first step in plotting is applying any non-zero rotation. It is specified in terms of the camera, so it will actually rotate the image in the opposite direction.

After applying rotation to the coordinate, bounds checking is done. If the point is outside of the Cartesian space the histogram covers, then it’s discarded, otherwise it’s plotted if the opacity is non-zero.

The point can’t be plotted directly because it’s in a different coordinate system than the one used for indexing the histogram memory. The points are decimal numbers in Cartesian space with 0,0 at the center. The histogram is stored in raster coordinates with 0,0 at the top left and each bucket specified by an integer x,y index. So before plotting, the coordinates must be converted to determine the histogram bucket to write to.

After computing the raster coordinate, a color must be added to the bucket. This is gotten from the Ember’s color palette, at the index specified in the point. A similar coordinate problem occurs in that the computed color index is a decimal number, but the indices in the palette are integers. The algorithm offers two methods for retrieving the color. The first is called “Step” and just rounds the index down to the nearest integer. The other is called “Linear” and does a blending of the values at the integer index and the one next to it.

Once a color is retrieved, all three RBG values are multiplied by the opacity and the result is added to the RGB values in the histogram bucket at the specified location. The alpha channel is unused for transparency and is instead used as a hit counter to record how many times a given bucket was hit during iteration. Each hit adds one to the alpha channel.

The Cartesian coordinate calculated from applying the xform in the previous step is fed back into the iteration loop and is used as the starting point for repeating the process all over again. The number of times this is done is referred to as the quality and is equal to:

quality * finalwidth * finalheight

Note that while supersampling increases the size of the histogram, it does not increase the number of iterations performed.

Trajectory

Iterating and plotting don’t occur exactly in the order described above or in the paper. The point is not plotted immediately after each xform application. Rather, the points are all stored in a temporary buffer whose size defaults to 10,000, known as a sub batch. Once 10,000 iterations have completed, all of the points are plotted to the histogram. Before the next sub batch begins, the point trajectory is reset by re-enabling the fuse state and assigning the first input coordinate random numbers between -1 and 1.

This method of using sub batches reveals an interesting characteristic of the algorithm not covered in the paper. That is, the point trajectory need not remain continuous to produce a final image. Even when resetting every 10,000 iterations, the trajectory still converges on the attractor. Thanks to this property, multi-threading does not degrade the image quality by breaking up the trajectory, since each thread will run many sub batches.