Version 1.3 will be a bugfix release (was: Should we have a 1.3 bug fix release milestone?)

[LegalizeAdulthood]

Since I've put the 2.0 milestone 6 months out in September, I'm wondering if we want a 1.3 milestone in 3 months time to get any bug fixes or such things deployed from master into a release before the switch to wxWidgets happening on the wx branch.

I know @PaulTheLionHeart is working on perturbation enhancements and I don't expect it to take 6 months for that :) based on progress so far.

I would also like to keep doing any bug fixes slated for 2.0 on the master branch and keep the GUI work separate on the wx branch. Thus a 1.3 milestone in 3 months that just consists of bug fixes seems reasonable.

@PaulTheLionHeart what do you think?

[PaulTheLionHeart]

I see two issues with full implementation of perturbation.

1. The high level program structure as discussed in pull down request Switch perturbation from a passes algorithm to work with the standard engine #256 last week. I'm waiting for comment on proposed structure.
2. Approximation. This is more difficult than I thought. Kevin Martin's document describes the theory, but I'm not making a lot of progress. Maybe it's my programming or mathematics skills that are holding me back :)

[LegalizeAdulthood]

I haven't commented on that yet in the pull request because I was busy with other things :) but I haven't forgotten about it.

Still, the question here remains: should we have a 1.3 milestone and try to get things sorted out with perturbation in the next 3 months? :)

[PaulTheLionHeart]

I guess the best thing is to set up a milestone 1.3 and if we don't meet it, we can squeeze it into 2.0. How does that sound?

[LegalizeAdulthood]

Sounds like a plan :)

Milestones are free, so why not?

[LegalizeAdulthood]

OK, I've created the milestone with a delivery date for the end of June and I've assigned the perturbation related issues and some other issues to the milestone.

[PaulTheLionHeart]

Great. Let's do it.

[LegalizeAdulthood]

OK, so I've been working on flushing out the 6-bit per channel color stuff from the code and replacing it with 8-bits/channel. Things are going fine, but I'm wondering if I should put in a backwards compatibility path for supporting the old 6-bit/channel stuff. This would be the first "breaking change" in Id compared to earlier versions. The funny thing is that the GIF file format always supported 0-255 range of values for color channels, but FRACTINT always kept color channels in the 0-63 range internally and then left shifted them by two bits when writing to a GIF file (and right shifting by two bits on file read). Since VGA displays have had 24-bit colors in colormaps for ages, I always wondered why it was doing this 6-bit manipulation everywhere.

Anyway, the question remains: should we have backwards compatibility logic throughout or just ensure 8-bits/channel from files on read?

[PaulTheLionHeart]

The pros for moving fully to a new strategy are simplicity of code, Id is a new product and it is closer to the standard used by most image processing software. The main issue for us will be the accuracy of FOTD's and detecting which mode was used to save the file.
May I suggest we go straight to PNG format and have full 24 bit support from the start? Then if we read a GIF file, we we know it's 6 bit colour and PNG is 24 bit. This is why I chose PNG for ManpWIN.

[LegalizeAdulthood]

Switching to PNG is a larger change; the issue here isn't truecolor (PNG) vs. colormapped (GIF) pixels, it's how many bits per channel are kept internally for colors in the colormap. Everything externally (GIF files, .map files) uses 0-255, but internally the code is mapping everything to 0-63 because VGA colormaps were 6-bits per pixel before 1991 (!).

You might ask: well, if it's internal, why does it matter?

The one place where it does matter so far is in the image-based tests where the 'gold' images come from FRACTINT. The iteration counts match (pixel value that indexes the colormap), but the colors in the colormap don't match. So far I've worked around it by ignoring the colormap between the rendered test image and the gold image, but then I lose the ability to identify bugs introduced that write out the wrong colormap. I could regenerate the 'gold' images in Id and the colormap would match. Hmm... maybe that is the real solution, I'm not sure.

The reason the colors don't match is that on colormap read, the old code did:

red = red >> 2;

and then we counter-compensate for this in the Win32 display code by doing:

red = red * 4;

So the display appeared to have the proper intensity (e.g. not dark), but in the end when we write out the GIF file, the lower 2 bits of the color channels in the colormap are always zero!

Maybe I'll try another hack in the image compare tool to zero out the bottom bits and see if that makes the FRACTINT images compare equal in the colormap.

The question still remains: do we provide a backwards compatibility path for this?

[LegalizeAdulthood]

Additional: I just pushed an image-dump tool to master that will dump out the contents of a GIF file. The GIF file does have in it the concept of a "color resolution" which FRACTINT was setting to 6, so I guess I should look at that header field value when reading GIF files.

[PaulTheLionHeart]

What are the consequences for the user? From the point of view of the user, is the main consequence a slight change in the color? If that's all the user sees, it's not a problem. Am I on track here? We have already removed integer arithmetic. We need to bring Id into current technology.

[LegalizeAdulthood]

What are the consequences for the user?

Good point, what is the observable effect? I think it comes down to more colors displayed and saved in the GIF file colormap because you have the full 0-255 range instead of (0-63)*4.

We need to bring Id into current technology.

Yes, but backwards compatibility has always been a strength of FRACTINT and when I make a change that could affect the image, I think about whether or not I need to retain the old behavior. In this case, it doesn't change how the fractal is computed, but it does affect how colors are displayed for iteration counts.

In this case, I'm on the fence about it, hence this discussion :).

[PaulTheLionHeart]

It doesn't seem like a critical problem if there is only a slight shift in the colors displayed.

[LegalizeAdulthood]

OK, I just wanted to 'take the pulse' and see if it was worth the extra effort.

I can always back-fill compatibility, based on git history, if someone asks for it :).

I'll deal with the image tests with a suitable flag to my image compare program so that I am checking legacy colors for match instead of trying to generate backwards compatible renderings in Id.

[PaulTheLionHeart]

Seems like a good decision.

[LegalizeAdulthood]

@PaulTheLionHeart I was thinking about the perturbation changes that you have in flight and I keep coming back to this one question in my thinking:

Why are we forcing perturbation to compute to max iterations during initialization?

In order to do the minimal amount of work (which is the whole point of any speed-up algorithm like perturbation), we should only be computing a new point on the reference orbit when necessary. Similarly, we should only be selecting new reference points when necessary. This leads me to the following algorithm when perturbation is enabled:

1. If perturbation is enabled, perform_work_list wraps the per_image, per_pixel and orbit_calc functions with perturbation enabled functions, similar to the way the functions are switched for alternate math:

   iterated-dynamics/libid/engine/calcfrac.cpp

   Line 884 in 6df3dea

   if (alt > -1)

2. The standard engine performs per-image initialization for the fractal type:

   iterated-dynamics/libid/engine/calcfrac.cpp

   Line 1038 in 6df3dea

   g_cur_fractal_specific->per_image();

3. If perturbation is enabled, the wrapped per_image function:
   1. Selects an initial reference point for the image, e.g. the center of the image
   2. Calls the original per_image function
4. The standard engine goes through the logic of selecting the appropriate pass routine based on g_std_calc_mode

   iterated-dynamics/libid/engine/calcfrac.cpp

   Line 1135 in 6df3dea

   switch (g_std_calc_mode)

5. The passes routines eventually invoke g_calc_type, which for the standard engine fractal types is usually standard_fractal

   iterated-dynamics/libid/engine/calcfrac.cpp

   Line 1315 in 6df3dea

   int standard_fractal() // per pixel 1/2/b/g, called with row & col set

6. standard_fractal invokes per_pixel for the fractal

   iterated-dynamics/libid/engine/calcfrac.cpp

   Line 1434 in 6df3dea

   g_cur_fractal_specific->per_pixel(); // initialize the calculations

   1. If perturbation is enabled, the wrapped per_pixel function selects the initial reference point to be used for this pixel. The first pixel to be computed starts with the initial reference point chosen for the image at the center of the image.
7. standard_fractal begins iterating the orbit:

   iterated-dynamics/libid/engine/calcfrac.cpp

   Line 1465 in 6df3dea

   while (++g_color_iter < g_max_iterations)

8. standard_fractal calls orbit_calc

   iterated-dynamics/libid/engine/calcfrac.cpp

   Line 1534 in 6df3dea

   else if ((g_cur_fractal_specific->orbit_calc() && g_inside_color != STAR_TRAIL) || g_overflow)

   1. If perturbation is enabled, the wrapped orbit_calc
      1. checks the reference orbit to see if it has enough iterations to compute this iteration of the pixel.
      2. If not, then an additional iterations are added to the reference orbit until it has enough iterations
      3. The perturbation functions for this fractal are used to compute the orbit for the pixel from the reference orbit (which now has sufficient iterations for the pixel)
      4. If the pixel's orbit has errored out, e.g. too much error has accumulated with respect to the reference orbit, then:
         1. A new reference point is selected for this pixel and made the current reference point.
         2. Restart the wrapped orbit_calc
      5. If the pixel has not errored out, then return normally

This algorithm only does work on reference orbits when necessary and only selects new reference points when necessary. It does the minimal amount of work. The additional overhead compared to brute-force deep zooming should be small compared to the amount of bignum math that is avoided due to the perturbation algorithm.

Unlike our previous discussions where the reference points were computed to max iterations, it doesn't run the reference orbit out any farther than necessary to compute the orbit of a particular pixel.

By wrapping the fractal type functions, perturbation support drops into all the existing passes code without modifying any of the passes algorithms. Perturbation is orthogonal to how the pixels are scanned.

[LegalizeAdulthood]

I've left unspecified how new reference points are selected. I think here there are various heuristics that can be applied. Even choosing the center of the screen for the initial reference point location is a heuristic that isn't guided by any mathematical analysis of the image. I think a good first heuristic would be to simply recursively subdivide the screen in quarters and choose the center of the subdivided region as the next reference point.

For example, suppose the image is 800x600. The initial reference point is arbitrarily chosen as the center of the screen at (400,300).

Suppose pixel (150,50) errors out. You subdivide the upper left quadrant and choose a new reference point at (200,150). This moves the reference point closer to the errored out pixel and now you have two reference points at (400,300) and (200,150). The current reference point is (200,150) and is used until another pixel errors out.

Suppose the next pixel to error out is at (500,50) while using reference point (200,150). The current pixel is now farther away from (200,150) than it is from (400,300). So we search the available reference points for one that is closer than the current reference point and we've selected (400,300) as a candidate reference point. The candidate reference point may not have its reference orbit calculated out far enough for the current iteration of the current pixel, so its orbit may need to be extended on demand to catch up to the current iteration. Having done that, we'll know if this new candidate is good enough for the pixel at (500,50), e.g. the current pixel doesn't error out. If so, then this closest reference point becomes the new current reference point.

Otherwise, we need a new reference point and we subdivide the upper right quadrant and choose a new reference point of (600,150) and repeat the above process to evaluate the new reference point.

In this way, I think we do the minimum amount of work to choose a new reference point when needed. The heuristic for the new reference point location is simplistic (repeated subdivision), but it is orthogonal to the work of deciding if the new reference point is acceptable for the current pixel. Subdivision could be replaced with some sort of gradient descent based on pixels computed so far, for instance. Subdivision is easy to implement and has the advantages of always choosing a new reference point that is logarithmically closer to the pixel that is erroring out.

An initial first pass for choosing reference points could simply use the location of the current pixel as a new reference point. When pixels error out, they still attempt to choose the nearest reference point, if different from the current reference point, before deciding to add a new reference point. This is probably a good way to do the "simplest thing that could possibly work" before tackling subdivision.

[LegalizeAdulthood]

I've also left out the details of what the code looks like when it does things like "wrap the per_pixel function". As much as possible the necessary state should be isolated inside the existing perturbation engine class and be updated by new global functions called from the standard engine. We shouldn't need any new global variables, just global functions. In fact, the standard engine can unconditionally invoke those perturbation functions and if perturbation isn't enabled (local state to the perturbation engine), then they simply return and do nothing.

This keeps all the data about perturbation local to the perturbation engine and the only connection to other code is through functions.

[LegalizeAdulthood]

I did some work on implementing this algorithm in a branch off of master. I made some progress, but I'm not sure if it's going to get into master before the end of June, which is the current cutoff date for the 1.3 release. If it's ready, it's ready, otherwise we'll keep working on it and it'll be in some later release. I see the improvements to perturbation as something we should keep pushing on, but I don't see it as a release blocker if it's not ready yet. As soon as 1.3 is released, I'm going to switch to working on 2.0 and wxWidgets.

[PaulTheLionHeart]

This sounds like a plan. While you work on wxWidgets, I can learn rebasing sufficiently to add my changes to master... incrementally.

[LegalizeAdulthood]

Over the long weekend I worked on finishing up the changes to move to full 8-bit color channels from 6-bit colors channels. It's kind of amazing that the code has persisted this long in truncating color channels to 6-bits and nobody ever complained before? I guess they just didn't notice it. I have a little more polishing to do to validate things end to end. My thinking is to have a test parameter file that uses a colormap with 256 distinct values in the color channel, e.g. grey.map, and saves out an image. Then I examine the saved color table and compare it against the values in the map file and they should match exactly.

[PaulTheLionHeart]

I have already made all these changes and we don't seem to get them into the master build. Why do it incrementally when I have already done the work?

[LegalizeAdulthood]

That pull request still has failing tests; did you get it properly rebased to remove unwanted changes and update it based on the review I left?

[PaulTheLionHeart]

Yes, I made a start at rebasing it but got a bit lost. I fixed the faulty labels, but didn't know what to do with the other changes. If I take them out, Id doesn't work the way I intend. SO I don't understand the conflict. Sorry to be so dense, but I just get lost. I am not confident in my understanding of current Id code. I hope I adequately described the changes I am trying to make.

[LegalizeAdulthood]

The git book has a chapter on rebasing: https://git-scm.com/book/en/v2/Git-Branching-Rebasing

Visual Studio also has the ability to do a "three-way merge" directly on a git repository to resolve conflicts. The git support in Visual Studio is here in their docs: https://learn.microsoft.com/en-us/visualstudio/version-control/git-with-visual-studio?view=vs-2022

I think this video does a good job of showing you how to resolve conflicts directly in Visual Studio:
https://www.youtube.com/watch?v=ziQlAo8H5w8

Resolving conflicts and doing so-called "three way merges" is probably one of the most difficult things to do in git. Not because git makes it difficult per se, it's just confusing to work with the three different views of the code and it's easy to make mistakes. Also, because resolving conflicts correctly is an acquired skill and it's not something we do every day, it can take a while to get the hang of things.

[PaulTheLionHeart]

While you are finishing Id 1.3, I'll study the rebase documents and wait until we have a stable master to work with. Then I might try incremental pull requests and rebase them...slowly.

Meanwhile I am trying to get double-double working in the parser in ManpWIN to check out some of the FOTDs to see if a little more precision will help to resolve them. If DD works, then I'll add QD. I'm not sure I walso want to add mpfr at this stage.

[LegalizeAdulthood]

We've made good progress on fixing issues for 1.3. Personally I want to try and get these fixed before the end of June:

• Bug in Solid Guessing for Normal Fractals (non-perturbation) #257
• Delay isn't displayed in type=ant when arrow keys are pressed #287

I think the solid guessing bug has been around forever, so that will be a nice improvement and not just cleaning up some mess I created while migrating the code as is the case for the displaying the ant delay value.

Personally I was surprised to learn that the code has been stripping color values down to 6 bits all these years. 8-bit colors were supported in DOS in 1997! So that's just something that never got improved in the code and is now fixed. This is a necessary prerequisite to moving on towards supporting 24-bit (and floating-point) colors. Fixing #61 required a sprinkling of changes throughout, but is a good upgrade.

[LegalizeAdulthood]

Yeah, OK, that's just normal discrete gradient processing, nothing special.

[PaulTheLionHeart]

If you say so :)

[LegalizeAdulthood]

It's been around for a long time in graphics APIs because the change per pixel in (u, v) texture coordinates is used to select the appropriate mipmap level in a mipmapped texture. The raster engine computes the discrete gradient of the texture coordinates to select the mipmap level. Sometimes you need to do it yourself.

[PaulTheLionHeart]

The first I knew about it was in the slope presentatiopn in Kalles. It sure looks good compared to a flat image.

[LegalizeAdulthood]

I'm pretty sure there's got to be an equivalent setting in UltraFractal, not sure where it is though. I looked through the coloring section of the help files today and nothing stood out.

[LegalizeAdulthood]

OK, I've fixed these:

• Sort the fractal type descriptions alphabetically #305
• Clarify formula semantics and syntax #304
• Documentation retains discussion of integer math #303
• Delay isn't displayed in type=ant when arrow keys are pressed #287
• Update Perturbation Documentation #254

I am going to try and fix the solid guessing bug (#257) and the VC++ runtime packaging bug (#132) by Sunday.

Even if I can't get those fixed by Sunday, the master branch is in good shape for a 1.3 bugfix release.

[PaulTheLionHeart]

Well done Richard.

Looks like you are on track for an end of June release of Id 1.3.