generator layer notes online, comments welcome

[Matthew Woehlke]

Boudewijn Rempt wrote:
> On Saturday 20 September 2008, Matthew Woehlke wrote:
>> I still need to write about color mapping for flames some time. In a
>> nutshell... it's hard. I would *really* like to be able to change the
>> palette without having to re-render the flame, but I'm not sure if
>> that's possible.
> 
> Well, if you keep the original data and the color paint device with the right
> color, sort of.

Keeping the data is the problem. (Are you familiar with how IFS's are 
colored? I had assumed this would be "easy" until I tried to figure out 
how the coloring is actually done. The information below took me rather 
some time to figure out, and I'm not sure it's right. If you actually 
know more than me, I'd appreciate knowing what's incorrect!)

As I understand it, the current algorithm works in the following manner:

- Define a color map. From what I can tell, this is essentially a 
gradient, but they tend to have quite a few stops.
- Assign each function a position on the map.
- Start with a random color from the map. Remember its position.
- Plot a new point. The new color is chosen from the position halfway 
between the old position and that of the picked function.
- For each plotted point, add the current color to the RGB accumulators, 
and increment the density (alpha) accumulator.

Therefore, the result of each pixel is the average of all color 
positions when that pixel was plotted, where the color position is 
continuous (theoretically infinite possible values, practically limited 
by the FPU's precision and/or quantization in the RGB accumulators).

Now, if gamma/etc are applied /after/ turning data+accumulators into the 
averaged color (which I think is the case in traditional 
implementations, though I'm not certain), Krita can bypass that entirely 
by simply having the generator output in a high-precision color space; 
you can then apply brightness/contrast curves to the output with minimal 
loss of detail (probably none if you reduce to 8 bpp for final output).

But you can't just change the palette, because that radically changes 
what goes into the RGB accumulators. The only obvious solution I've 
thought of so far is to keep the color map position for each pixel, but 
simply averaging the values isn't the same effect, which means keeping a 
/list/ of all positions for each pixel. You could quantize the position 
into a number of buckets (I think with a power-of-two that is at least 
64, this would work), but it's still a huge^1 amount of data.

(de Jong transient has the same problem, except that the color function 
is fixed to the number of transient iterations being performed. On the 
plus side, there is usually a much higher number of buckets that will 
contain zero, making a sparse matrix implementation desirable. On the 
down side, it is not unusual for the number of transient iterations to 
be as high as 300-500. That said, the mapping for de Jong transient can 
also be thought of as a subset of the mapping for strange, which is 
three dimensional, in which what is really desired is the ability to map 
depth (Z axis) to color^2. Similarly, using a lower resolution 
quantization is probably desired, especially since antialiasing might 
make sense in this instance. Such antialiasing might also make sense for 
the IFS case. If it is reasonable to similarly quantize the color map^4, 
the same technique could likely be applied to transient de Jong to 
reduce the number of needed buckets.)

^1 64 buckets, with 32-bit precision per bucket, at WQXGA^3 resolution, 
is well over 1 GiB. We can assume reasonable compression on that, but at 
this point we're essentially be talking about a generator that cannot be 
used on a 32-bit machine.

^2 ...alternatively, it would take quite a bit longer to map, but Z 
could also be mapped to blur, for depth-of-field effects. Can you 
imagine that? :-)

^3 WQXGA = 2560x1600, a.k.a. the largest current "mainstream" resolution 
(so far as I know).

^4 I believe the GIMP IFS implementation already uses a quantized color 
map, so no loss there.

(Methinks this is going to become the wiki section :-).)

...although this is making me want to impose a strict "2d only" 
restriction on Krita fractal generators, due to the potential for quite 
a bit of scope bloat. I think an IFS generator is almost required (as 
GIMP has it since a long time), and I really want to see at least 
non-transient de Jong, and /maybe/ a strange formula or two. Being able 
to dynamically change colors is a major plus, but something I'd be 
willing to cut in the interest of sanity if it would be "hard". Fiddling 
with 3D projections is probably better suited to a stand-alone program, 
or at least to starting out that way. Similarly, I'm not sure what will 
happen with transient de Jong, since that's another can of worms (maybe 
just do like fyre, and don't support iteration as a mapping parameter).

-- 
Matthew
I sure hope they never make a hearse out of a Scion. I wouldn't want to 
be caught dead in one.