Fract'ol - How to zoom to the limit
Assignment
The assignment is to draw a fractal, but that is just the subject matter, as stated in the PDF, the purpose of this assignment is to learn about optimization and event handling.
What this document will explain
This article considers how to implement the following two requirements of the assignment
- The mouse wheel zooms in and out, almost infinitely (within the limits of the computer)*.
- The management of your window must remain smooth
"The limits of the computer" is interpreted in this document as "the limit of the number of doubles that can be represented by the computer".
What this document does NOT explain
There are various materials on how to write fractals, so I will not explain them here.
Goal
Even when zoomed in to the limit, the screen will be able to render smoothly moving fractals without freezing.
Mandelbrot Set
Julia Set
Sierpinski Gasket
Conflicting requirements
- Need to compute infinitely many times to draw a fractal
- The screen needs to operate smoothly without freezing
Now how to solve these two conflicting requirements is the point of this assignment.
Units of measure that are important
FPS: Number of images (frames) displayed per second
FLOPS: Number of floating point operations per second
What is a smooth running app!
Video is made to look like a moving picture by drawing images one after another like a flip book.
Most videos are 30 FPS (or 60 FPS). In other words, 30 pictures are displayed per second.
In other words, if we stop the calculation at one frame (1/30 = 0.033 seconds), display an image, and return an event (mouse operation, etc.) to the user, we can make it look as if it is runing smoothly.
When making a game or creating a UI for an application, it is very important for the user experience whether or not the computation is completed within one frame. I think this assignment is not only about drawing fractals, but also about learning to do so.
How to interrupte the calculation within 1/30 second
The number of times a computer can perform a calculation per second is expressed in FLOPS, but since threads cannot be used this assignment, it is sufficient to know that the number is roughly proportional to the number of CPU clocks.
Recent CPU clock speeds are around 2~3GHz. The detailed number is not so important, as long as the approximate order (number of digits) is correct, there is no problem.
For now, assuming that the CUP is 2GHz, the number of operations that can be performed within 1/30 second can be roughly estimated as follows.
In other words, counting the number of calculations and once 66 million times calculations have been made, the process can be stopped, the image in the middle of the calculation can be displayed, and events (such as mouse operations) can be returned to the user for smooth operation without the screen getting stuck.
Estimating the number of calculations
The heaviest processing part of the Mandelbrot and Julia set calculations is the loop to determine whether the asymptotic expressions diverge or not.
The asymptotic formula would roughly look like this code.
tmp = z[0] * z[0] - z[1] * z[1] + c[0];
z[1] = 2.0 * z[0] * z[1] + c[1];
z[0] = tmp;
How many floating-point operations are there in this code if we do the calculations in a straightforward manner?
Let's count them.
Real part
Imaginary part
The real part is calculated
The number of times that the asymptotic formula can be calculated within one frame (1/30 second) is
Well, we estimate it to be about
(I wrote roughly
Using loop hook of minilibx
Use the loop hook (mlx_loop_hook) to continue the calculation while returning events to the user.
The number of times each pixel has been calculated is added up, the number of pixels processed is stored, and the process is aborted after 10 million incremental calculations. Return an event to the user.
Then, the next minilibx loop hook computes the continuation.
Calculate details while increasing the number of judgments
At first, set the number of times to judge the divergence of an incremental expression to about 50 times, and when you have finished calculating to the last pixel, increase that number of times and recalculate the pixels that did not diverge (black pixels), you can operate smoothly and zoom to the limit of floating point.
(Appendix) How to use minilibx
Tutorial
Tutorial on how to use minilibx
Sample project
This is a sample that drawings and hooks. When executed, it looks like this.
Discussion