Continuous Zoom support

[edyoung]

Programs like Xaos provide the ability to hold down a mouse button and zoom continuously into the fractal, as opposed to the click-by-click operation Gnofract 4D currently supports.

[mindhells]

We've started to work in this feature. @josebailo has created a branch in which Gnofract4D allows the user to hold down left/right mouse button to continuously zoom in/out the fractal.
Under the hood, Gnofract4d still does just the same calculations as usual, and the result is not the smooth effect we're looking for.
In order to get the desired result we need to change the way every "frame" is calculated. Here Thomas Marsh and Jan Hubicka (original authors of the XaoS project) explain how they got there.
In the mentioned article, there's a subtle explanation of the many algorithms they use. We don't know yet if it's possible to bring them to Gnofract4d, due to the special features we have here. Nevertheless, in order to find out we're going to need some reverse engineering to understand their specifics.

I think the easiest way to get somewhere near the desired result is to follow an iterative process, starting from the most basic approach (maybe some kind of interpolation). To do that, we need to change the way Gnofract4d calculates the pixels and also add new data structures to reuse calculations from the previous frame (which is the foundation of the Xaos algorithms).

At this moment I'm working in the idea of creating a new IFractWorker implementation (not sure yet if I will need a new fractFunc as well) to be the place to implement the new algorithms. Hopefully I'll manage to keep the interface to ease switching between normal and XaoS zooming.

[mindhells]

1st approach created by @josebailo is based on a Timer that zooms and calculates the frame every 300ms while the user holds the button. Problem with this is you don't know exactly how much time you need to calculate the previous frame, but you need the previous frame to be calculated. We need then to sync the animation frequency with the previous frame calculation ending.

On the other hand, while this is just a proof of concept for now, we need to define some requirements of what the final result should look like. As some of the current features could clash with it (the selection rect for example), I see this new feature as a different "working mode", like the user has to toggle some sort of switch to enable it (and disable other features)... or maybe the user needs to hold a key. What would be the better, or more consistent, approach?

[mindhells]

We've been doing some progress these days:

• On the one hand we've introduced a new settings option to activate the continuous zooming mode.
• On the other hand we've created the XaosFractWorker class, which is a lightweight version STFractWorker. This class would be the responsible to perform the calculations when the continuous zoom mode is activated. By the time of writing this comment, the class has the ability to produce a new image based on a previous one with a wider value range (zooming in). To do so, it reuses the pixels from the old image that are within its value range. Of course this is yet incorrect, as it's only valid to go from the original image to the 1st zoom in level. Subsequent zoom levels shouldn't reuse all the pixels already reused by their previous image as they are already approximations. In summary, there's still a long way ahead and many pitfalls to discover (I have a feeling the 4D rotations will complicate things), but this 1st has been very insightful about how to bring Xaos algorithms into Gnofract.

A last note about XaosFractWorker: the reason to create a lightweight version of STFractWorker is to avoid dealing with more complexity (stats, qbox drawing strategy, etc.). We are also not using MTFractWorker yet, which enables having multiple workers and multiple threads. In the future we might even dispose XaosFractWorker and add their abilities to STFractWorker.

[mindhells]

I think I've managed to make the new worker handle both zooming in and out. There's probably an easier approach for the maths in there and also I have to confirm everything (reused pixels) is put in the right place.

Next steps:

• avoid reusing pixels from older frames, we need to avoid reuse pixels from the previous frame that were already reused. To do that we need to keep track of what row/column approximations we did in the last frame to evaluate if they are worth being reused again or disposed.
• synchronize the frame rate: don't start calculating the next frame until previous has finished (we need all the pixels calculated from the previous frame).

I think if we manage to complete these 2 steps we are good to merge and have a new "experimental feature". In the meantime, if you are curious, just checkout that branch, compile and launch, but try with 320x240 resolution, unless you have a very powerful CPU you'll get an error (not enough time to calculate previous frame).

On the other hand, we've been having some trouble with the tests. They got stuck at "test_director". We have to figure out how the new setting "enable/disable continuous zooming" is affecting them.

[mindhells]

We made gtkfractal to syncrhonize the frame rate to avoid unfinished frames. We had to create a custom Thread class to have a setinterval-like behavior.

We also had to deal with a problem regarding button press/release: when the user double clicks on the image, the onButtonPress event is called twice while the onButtonRelease is called only once, that made the continuous zoom effect to stay hanged.

On the other hand we also managed to avoid reusing pixels from ancient frames, preventing carrying errors on subsequent frames.

The problem with the tests is already solved as well.

Next steps:

• add all the improvements back from STFractWorker and MTFractWorker to XaosFractWorker: multithread, rectangle guessing...
• solve the following problems:
  • some kind of strange effect (flickering?) with the Gtk drawing area. Sometimes you see strange frames in between.
  • when holding the mouse button (continuous zooming activated), if the user moves the pointer outside the drawing area then the image is recentered to that position. We should keep the new center within the original complex plane dimensions.
• create test for this new feature.

[mindhells]

This is what we've done since the las update:

• restored "box guessing algorithm" into the continuous zoom worker.
• added multithread calculation into the continuous zoom worker: with a simple thread pool.
• keep the zooming center within the visible space.

All in all it seems the weird "flickering" effect is gone and performance has improved quite a bit: I'm able to run it for a 640x480 drawing area with a bearable framerate (I'm using my laptop, equipped with i5-8259U CPU @ 2.30GHz).

Next steps:

• dynamic resolution: https://github.com/xaos-project/XaoS/wiki/Developer's-Guide#dynamic-resolution
• avoid python-C++ interchange for every frame: at this moment we use the same approach as for a normal calculation, we call a calcxaos function on the fract4dc extension module. This represents an unnecessary overload, not only because of the boilerplate of the communication itself but because we need to create and destroy the same objects (fractfunc, worker) every time.
• add tests

Actually, the second point would go 1st, as it would allow us to control the framerate and thus decide if we calculate all the pixels for the current frame, as the dynamic resolution algorithm states.

[mindhells]

Updates since the last comment:

• Glib to handle frame interval from gtkfracal. Now we use GLib.timeout_add instead of python threads.
• new fract4dc interface to change communication model python-C++: now, instead of calling the usual fract4dc.calc interface for every frame (that involved creating several objects), we have an infinite loop in C++ waiting for updates.
  • fract4dc.calcxaos: this calculates the 1st frame and starts the infinite loop
  • fract4dc.updatexaos: this sends an update (new location params after recentering the image) to the C++ infinite loop
  • fract4dc.interruptxaos: this stops the infinite C++ loop
• dynamic resolution algorithm: the idea behind this is to improve the framerate while keeping enough detail in the image so it doesn't look weird. This basically is accomplished with 2 steps:
  • spiral box-guessing loop to prioritize image center pixels: instead of calculating the image in top-bottom left-right order, we do a spiral-loop from the center of the image. This way, boxes at the center of the image are calculated first (more priority).
  • interpolate rest of the pixels based on statistics and limitations: we try to run a 20fps animation, that is 50ms per frame. When calculating a frame takes more than 50ms then we try to speed up the process by interpolating the remaining pixels instead of calculating them. To do that we stablish a minimum amount amount of pixels to be calculated (or reused from the previous frame).
• added some tests

[mindhells]

Current status and plans:

• Reviewed and improved the pixel reutilization algorithm as well as added some other minor improvements.
• Found out there's a limitation in the pixel reutilization algorithm: plane XY rotation is not supported, since the algorithm is based on the principle that imaginary values keep constant while moving across X axis and real values keep constant while moving across Y axis on the complex plane.
• Investigating: segmentation fault errors appear from time to time in a MacOS environment. I think it's related to the image buffer management.
• Working on: adding some markdown documentation to explain how everything works, kind of a "developer manual" so others can follow up improving it.

[edyoung]

I tried it out - very cool effect!

One UX suggestion - perhaps we could make this feature a bit more discoverable? I actually had to read the source to find there was a checkbox in the preferences to enable it. Maybe something that can be toggled in the toolbar (like Explorer Mode) to enable it?

By using a high resolution (2560x1600) I was able to trigger a seg fault in malloc - haven't looked more deeply yet but it presumably indicates a memory management issue somewhere.

[mindhells]

Definitely we need to tell the user this feature is there, therefore user manual update should be included in the PR.

We thought about different approaches to enable the feature, including a mouse command (like holding "alt" + pointer button). However, since this is an experimental feature so far maybe it'd be a good idea to keep it a little bit "hidden" for now.

I've been investigating this seg fault error for a while. I've the hunch either it's related with Gtk or the image buffer python interface, but unfortunately my knowledge in both is very limited:

• https://github.com/HyveInnovate/gnofract4d/blob/1a4708896b967e323f31c6d30ef34b8ccef584f3/fract4dgui/gtkfractal.py#L1126
• https://github.com/HyveInnovate/gnofract4d/blob/1a4708896b967e323f31c6d30ef34b8ccef584f3/fract4d/c/fract4dc/images.cpp#L342

[mindhells]

I've added a draft markdown document to try to explain everything we are doing in the CZ implementation:

https://github.com/HyveInnovate/gnofract4d/blob/continuous-zoom/doc/continuous_zooming.md

Source code comments should also help to understand fine grain detail.

[mindhells]

Being trying several things to solve the segfault errors but no luck so far.

I've tried to use a copy of the image buffer so in case the problem was related to simultaneous read/write (Gtk reading from one end and C++ extension updating the buffer from the other end). Didn't solve the problem.

I had also another suspect: "box guessing algorithm" works with sharing edges in between boxes, so I thought different threads could be trying to update the same pixel at once.

I'm out of ideas at this moment.

This is a sample trace log in MacOS 10.15.7 . To reproduce the problem just, madly, click left and right mouse button to zoom in/out the image:

Thread 0 Crashed:: Dispatch queue: com.apple.main-thread
0   libsystem_kernel.dylib        	0x00007fff71df133a __pthread_kill + 10
1   libsystem_pthread.dylib       	0x00007fff71eade60 pthread_kill + 430
2   libsystem_c.dylib             	0x00007fff71d78808 abort + 120
3   libsystem_c.dylib             	0x00007fff71d77ac6 __assert_rtn + 314
4   com.apple.CoreGraphics        	0x00007fff3847ff84 CGBitmapFreeData.cold.1 + 35
5   com.apple.CoreGraphics        	0x00007fff380730c4 CGBitmapFreeData + 34
6   com.apple.CoreGraphics        	0x00007fff3805ee14 CGBitmapContextInfoRelease + 76
7   com.apple.CoreGraphics        	0x00007fff3809b1e4 CGBitmapContextSetData + 184
8   com.apple.QuartzCore          	0x00007fff4373584c CAGetCachedCGBitmapContext_(void*, unsigned int, unsigned int, unsigned int, unsigned long, CGColorSpace*) + 513
9   com.apple.QuartzCore          	0x00007fff43735263 CABackingStoreBeginUpdate_(CABackingStore*, unsigned int, unsigned int, unsigned int, unsigned int, unsigned int, unsigned long long, unsigned int, UpdateState*) + 653
10  com.apple.QuartzCore          	0x00007fff43733821 CABackingStoreUpdate_ + 519
11  com.apple.QuartzCore          	0x00007fff437934ad invocation function for block in CA::Layer::display_() + 53
12  com.apple.QuartzCore          	0x00007fff43732d86 -[CALayer _display] + 2103
13  com.apple.AppKit              	0x00007fff3503a69a -[_NSBackingLayer display] + 537
14  com.apple.AppKit              	0x00007fff34f9c187 -[_NSViewBackingLayer display] + 800
15  com.apple.QuartzCore          	0x00007fff43731e09 CA::Layer::display_if_needed(CA::Transaction*) + 757
16  com.apple.QuartzCore          	0x00007fff43710106 CA::Context::commit_transaction(CA::Transaction*, double) + 334
17  com.apple.QuartzCore          	0x00007fff4370ecf0 CA::Transaction::commit() + 644
18  com.apple.AppKit              	0x00007fff35050da1 __62+[CATransaction(NSCATransaction) NS_setFlushesWithDisplayLink]_block_invoke + 266
19  com.apple.AppKit              	0x00007fff35770080 ___NSRunLoopObserverCreateWithHandler_block_invoke + 41
20  com.apple.CoreFoundation      	0x00007fff37c40335 __CFRUNLOOP_IS_CALLING_OUT_TO_AN_OBSERVER_CALLBACK_FUNCTION__ + 23
21  com.apple.CoreFoundation      	0x00007fff37c40267 __CFRunLoopDoObservers + 457
22  com.apple.CoreFoundation      	0x00007fff37c3f805 __CFRunLoopRun + 874
23  com.apple.CoreFoundation      	0x00007fff37c3ee3e CFRunLoopRunSpecific + 462
24  com.apple.HIToolbox           	0x00007fff3686babd RunCurrentEventLoopInMode + 292
25  com.apple.HIToolbox           	0x00007fff3686b7d5 ReceiveNextEventCommon + 584
26  com.apple.HIToolbox           	0x00007fff3686b579 _BlockUntilNextEventMatchingListInModeWithFilter + 64
27  com.apple.AppKit              	0x00007fff34eb1039 _DPSNextEvent + 883
28  com.apple.AppKit              	0x00007fff34eaf880 -[NSApplication(NSEvent) _nextEventMatchingEventMask:untilDate:inMode:dequeue:] + 1352
29  libgdk-3.0.dylib              	0x000000010c2f13ac poll_func + 172
30  libglib-2.0.0.dylib           	0x000000010b733ff1 g_main_context_iterate + 433
31  libglib-2.0.0.dylib           	0x000000010b73437f g_main_loop_run + 239
32  libgtk-3.0.dylib              	0x00000001103037aa gtk_main + 74
33  libffi.7.dylib                	0x000000010b8bef2d ffi_call_unix64 + 85
34  libffi.7.dylib                	0x000000010b8be7fe ffi_call_int + 721
35  _gi.cpython-39-darwin.so      	0x000000010b6be9d2 pygi_invoke_c_callable + 2338
36  _gi.cpython-39-darwin.so      	0x000000010b6bf9e7 pygi_function_cache_invoke + 55
37  org.python.python             	0x000000010a922fc9 _PyObject_Call + 138
38  org.python.python             	0x000000010a9c8064 _PyEval_EvalFrameDefault + 28268
39  org.python.python             	0x000000010a9cb6eb _PyEval_EvalCode + 1998
40  org.python.python             	0x000000010a92317c _PyFunction_Vectorcall + 248
41  org.python.python             	0x000000010a9caba3 call_function + 403
42  org.python.python             	0x000000010a9c7d34 _PyEval_EvalFrameDefault + 27452
43  org.python.python             	0x000000010a9231ec function_code_fastcall + 97
44  org.python.python             	0x000000010a9caba3 call_function + 403
45  org.python.python             	0x000000010a9c7de0 _PyEval_EvalFrameDefault + 27624
46  org.python.python             	0x000000010a9231ec function_code_fastcall + 97
47  org.python.python             	0x000000010a9caba3 call_function + 403
48  org.python.python             	0x000000010a9c7de0 _PyEval_EvalFrameDefault + 27624
49  org.python.python             	0x000000010a9cb6eb _PyEval_EvalCode + 1998
50  org.python.python             	0x000000010a9c111d PyEval_EvalCode + 79
51  org.python.python             	0x000000010a9fc185 run_eval_code_obj + 110
52  org.python.python             	0x000000010a9fb57d run_mod + 103
53  org.python.python             	0x000000010a9fa441 PyRun_FileExFlags + 241
54  org.python.python             	0x000000010a9f9a31 PyRun_SimpleFileExFlags + 271
55  org.python.python             	0x000000010aa1194d Py_RunMain + 1839
56  org.python.python             	0x000000010aa11c86 pymain_main + 306
57  org.python.python             	0x000000010aa11cd4 Py_BytesMain + 42
58  libdyld.dylib                 	0x00007fff71ca9cc9 start + 1

Thread 1:
0   libsystem_pthread.dylib       	0x00007fff71ea9b68 start_wqthread + 0

Thread 2:
0   libsystem_kernel.dylib        	0x00007fff71df13d6 poll + 10
1   libgdk-3.0.dylib              	0x000000010c2f1e54 select_thread_func + 212
2   libsystem_pthread.dylib       	0x00007fff71eae109 _pthread_start + 148
3   libsystem_pthread.dylib       	0x00007fff71ea9b8b thread_start + 15

Thread 3:
0   libsystem_pthread.dylib       	0x00007fff71ea9b68 start_wqthread + 0

Thread 4:
0   libsystem_pthread.dylib       	0x00007fff71ea9b68 start_wqthread + 0

Thread 5:
0   fract4dc.cpython-39-darwin.so 	0x000000010b58e7f0 image::get(int, int) const + 0 (image.cpp:120)
1   fract4dc.cpython-39-darwin.so 	0x000000010b58765d XaosFractWorker::reuse_pixels() + 2861 (XaosFractWorker.cpp:133)
2   fract4dc.cpython-39-darwin.so 	0x000000010b58d462 fractFunc::draw_all_xaos() + 1042 (fractfunc.cpp:208)
3   fract4dc.cpython-39-darwin.so 	0x000000010b58a3ea calc_xaos + 266 (calcfunc.cpp:70)
4   fract4dc.cpython-39-darwin.so 	0x000000010b57cfc8 calculation_thread_xaos(calc_args*) + 104 (calcs.cpp:168)
5   fract4dc.cpython-39-darwin.so 	0x000000010b57d2cc void* std::__1::__thread_proxy<std::__1::tuple<std::__1::unique_ptr<std::__1::__thread_struct, std::__1::default_delete<std::__1::__thread_struct> >, void* (*)(calc_args*), calc_args*> >(void*) + 44 (thread:289)
6   libsystem_pthread.dylib       	0x00007fff71eae109 _pthread_start + 148
7   libsystem_pthread.dylib       	0x00007fff71ea9b8b thread_start + 15

Thread 0 crashed with X86 Thread State (64-bit):
  rax: 0x0000000000000000  rbx: 0x000000011574cdc0  rcx: 0x00007ffee53183a8  rdx: 0x0000000000000000
  rdi: 0x0000000000000307  rsi: 0x0000000000000006  rbp: 0x00007ffee53183d0  rsp: 0x00007ffee53183a8
   r8: 0x00000000000000e8   r9: 0xcccccccccccccccd  r10: 0x000000011574cdc0  r11: 0x0000000000000246
  r12: 0x0000000000000307  r13: 0x000000011265c000  r14: 0x0000000000000006  r15: 0x0000000000000016
  rip: 0x00007fff71df133a  rfl: 0x0000000000000246  cr2: 0x000000011265c000