Faster Alternative to TIA coloring?

[dbyrne]

I've been messing around with branching average colorings like the triangle inequality average and curvature estimation algorithms and have come to the conclusion that they are needlessly slow.

To illustrate my point, compare these two images:
TIA: http://picasaweb.google.com/lh/photo/5My1RMT1lDd-jVJKRD70kg?feat=directlink
My method: http://picasaweb.google.com/lh/photo/olaMlO_Hzb3ILaWF7vu2yQ?feat=directlink

Both of these images use the same color scheme, iteration count, bailout, interpolation technique, etc.
The only difference is the addend function I used.  The TIA image took almost 75% longer to generate!  I guess my question is, given that the end result is so similar, whats the advantage to using TIA?

For those interested here is the code for the two different addend functions:

double TIA() {     
  double z_mag = sqrt(tia_prev_x*tia_prev_x + tia_prev_y*tia_prev_y);
  double c_mag =  c_mag = sqrt(P*P + Q*Q);
  double mn = z_mag - c_mag;
  mn = sqrt(mn*mn);
  double Mn = z_mag + c_mag;
  double num = sqrt(x*x + y*y) - mn;
  double den = Mn - mn;
  return num/den;
}

double myMethod() {
  return minVal(abs(y/x),2);
}

[makc]

I like "my method" version better.

[dbyrne]

I like "my method" version better.

I do as well.  I actually think I could have tweaked "myMethod" to be even more visually similar to TIA, but left it as is because I liked it more.

Also, in my original post I said TIA took 75% longer, when in fact I meant that my method took 75% shorter, which is a much larger difference!

[dbyrne]

Also, I am not trying to say that my method will always produce a similar image to TIA.  Here is another example where the results vary much more:

TIA: http://picasaweb.google.com/lh/photo/YxDQNXaApv09SSOd7rq-Tw?feat=directlink
My method: http://picasaweb.google.com/lh/photo/iZl7kMmCua28lJQ9jFm-5A?feat=directlink

These are different enough I think both algorithms merit examination.  My real point is that any application where performance is a major concern should consider an alternative to TIA.

[juharkonen]

  I remember making up the naming "branching average colorings" so it looks like you've been reading my master's thesis on coloring techniques (for anyone interested, it can be found in
http://www.violetindustries.com/gallery.php?cat=techniques).

As for TIA, I agree it's excessively complex to calculate and similar results can be achieved with much less calculation. In my thesis, I proposed the Stripes addend function as an alternative to TIA which is somewhat easier to calculate:
f(angle) = 0.5 + 0.5*sin(s*angle), where angle = arg {(x,y)} = atan(y/x) and s = integer constant

If I understood correctly, MyMethod corresponds to the addend function
t(angle) = min{tan(angle), 2} = min{tan(atan(y/x), 2} = min{y/x, 2}
Similar to TIA and Stripes, this method gives wave-like result as a function of angle which will lead to the branching appearance characteristic to TIA.

As for performance, MyMethod clearly has advantage because it avoids calculation of the argument with atan and doesn't involve any other trigonometric functions either. This can be significant especially on CPU because trigonometric functions are expensive. On the GPU, however, trigonometric functions are hardware accelerated and MyMethod ought to have slighter advantage.

[dbyrne]

Yes I have read your paper.  It is a great resource. I am writing fractal software for smartphones, so often a math coprocessor isn't available. I like your stripes algorithm a lot and have implemented it actually.

[dbyrne]

Actually I've been meaning to add a link to your paper in the documentation for my code.  Thanks for reminding me to do that. 

[Duncan C]

I've been messing around with branching average colorings like the triangle inequality average and curvature estimation algorithms and have come to the conclusion that they are needlessly slow.

To illustrate my point, compare these two images:
TIA: http://picasaweb.google.com/lh/photo/5My1RMT1lDd-jVJKRD70kg?feat=directlink
My method: http://picasaweb.google.com/lh/photo/olaMlO_Hzb3ILaWF7vu2yQ?feat=directlink

Both of these images use the same color scheme, iteration count, bailout, interpolation technique, etc.
The only difference is the addend function I used.  The TIA image took almost 75% longer to generate!  I guess my question is, given that the end result is so similar, whats the advantage to using TIA?

For those interested here is the code for the two different addend functions:

double TIA() {     
  double z_mag = sqrt(tia_prev_x*tia_prev_x + tia_prev_y*tia_prev_y);
  double c_mag =  c_mag = sqrt(P*P + Q*Q);
  double mn = z_mag - c_mag;
  mn = sqrt(mn*mn);
  double Mn = z_mag + c_mag;
  double num = sqrt(x*x + y*y) - mn;
  double den = Mn - mn;
  return num/den;
}

double myMethod() {
  return minVal(abs(y/x),2);
}

Thanks for posting this. I've been trying to find info on how to implement TIA coloring. Can you explain a little more, though?


Do you calculate the TIA (or "my method") value at the iteration when a point steps outside the bailout circle? That yields a floating-point value. What do you do with that value?

Are the x and y values the real/imaginary coordinates of the Zn value?