I am making a hobby OS, and I thought about adding a command for interactively rendering the Mandelbrot set. The "interactive" part is not really important, but I wanted to check if the Mandelbrot algorithm is as good as it can be.
The most performance-sensitive part is the code inside the inner for
loop, the one that iterates max_iter
.
I tried making it as optimized as possible, but I might have left something (also note that my OS doesn't support multicore yet).
/* Smaller -> More zoom (1.0 is defaul) */
#define DEFAULT_ZOOM 1.0
/* Offsets for moving in the set. */
#define DEFAULT_X_OFF 0.0 /* -2.0..+2.0 (Left..Right) */
#define DEFAULT_Y_OFF 0.0 /* -1.0..+1.0 (Up..Down) */
/* Default steps when moving around */
#define ZOOM_STEP 0.5
#define DEFAULT_MOVE_STEP 0.1
int mandelbrot(int argc, char** argv) {
const uint32_t w = screen_width();
const uint32_t h = screen_height();
const int max_iter = atoi(argv[1]);
/* Check arguments are valid... */
/* Framebuffer. Each 32 bit entry is a color */
volatile uint32_t* fb = fb_get_ptr();
/* Calculate some values here for performance */
const double scaled_h = h / 2.0;
const double scaled_w = w / 3.0;
/* Will become smaller when zooming */
double zoom = DEFAULT_ZOOM;
double x_offset = DEFAULT_X_OFF;
double y_offset = DEFAULT_X_OFF;
/* Will be scaled when zooming, so we don't move too much */
double move_step = DEFAULT_MOVE_STEP;
bool main_loop = true;
while (main_loop) {
do_mandelbrot();
handle_input();
}
}
My do_mandelbrot()
function:
static void do_mandelbrot(void) {
for (uint32_t y_px = 0; y_px < h; y_px++) {
double real_y = (y_px / scaled_h) - 1.0;
real_y *= zoom;
real_y += y_offset;
for (uint32_t x_px = 0; x_px < w; x_px++) {
double real_x = (x_px / scaled_w) - 2.0;
real_x *= zoom;
real_x += x_offset;
double x = real_x;
double y = real_y;
bool inside_set = true;
int iter;
for (iter = 0; iter < max_iter; iter++) {
/* Calulate squares once */
double sqr_x = x * x;
double sqr_y = y * y;
/* Absolute value of a complex number is the distance from
* origin: sqrt(x^2 + y^2) > 2 */
if ((sqr_x + sqr_y) > 2 * 2) {
inside_set = false;
break;
}
y = (2.0 * x * y) + real_y;
x = (sqr_x - sqr_y) + real_x;
}
/* If it's inside the set, draw black */
if (inside_set) {
fb[y_px * w + x_px] = 0x000000;
continue;
}
/* Get 0..360 hue for color based on iter..max_iter */
int scaled_hue = iter * MAX_H / max_iter;
fb[y_px * w + x_px] = hue2rgb(scaled_hue);
}
}
}
My hue2rgb
function:
static uint32_t hue2rgb(float h) {
float prime = fmod(h / 60.f, 6);
float x = 1 - fabs(fmod(prime, 2) - 1);
uint32_t ret = 0x000000;
if (prime >= 0 && prime < 1) {
ret |= 0xFF0000; /* r = 255 */
ret |= (uint8_t)(x * 0xFF) << 8; /* g = x */
} else if (prime < 2) {
ret |= 0x00FF00; /* g = 255 */
ret |= (uint8_t)(x * 0xFF) << 16; /* r = x */
} else if (prime < 3) {
ret |= 0x00FF00; /* g = 255 */
ret |= (uint8_t)(x * 0xFF) << 0; /* b = x */
} else if (prime < 4) {
ret |= 0x0000FF; /* b = 255 */
ret |= (uint8_t)(x * 0xFF) << 8; /* g = x */
} else if (prime < 5) {
ret |= 0x0000FF; /* b = 255 */
ret |= (uint8_t)(x * 0xFF) << 16; /* r = x */
} else if (prime < 6) {
ret |= 0xFF0000; /* r = 255 */
ret |= (uint8_t)(x * 0xFF) << 0; /* b = x */
}
return ret;
}
My handle_input
function should not be important, but here it is:
static void handle_input() {
/* User input, not really important for performance */
switch (getchar()) {
case KEY_ZOOM_IN:
zoom *= ZOOM_STEP;
move_step *= ZOOM_STEP;
break;
case KEY_ZOOM_OUT:
zoom /= ZOOM_STEP;
move_step /= ZOOM_STEP;
break;
case KEY_UP:
if (y_offset > -1.1)
y_offset -= move_step;
break;
case KEY_DOWN:
if (y_offset < 1.1)
y_offset += move_step;
break;
case KEY_LEFT:
if (x_offset > -2.1)
x_offset -= move_step;
break;
case KEY_RIGHT:
if (x_offset < 2.1)
x_offset += move_step;
break;
case KEY_RESET:
zoom = DEFAULT_ZOOM;
move_step = DEFAULT_MOVE_STEP;
x_offset = DEFAULT_X_OFF;
y_offset = DEFAULT_X_OFF;
break;
default:
break;
}
}
Edit: I changed the hue2rgb
return value.
Edit: Separated code into multiple blocks. Didn't bother with variables or returns, contents of do_mandelbrot
and handle_input
should be replaced where the functions are called.
getchar()
keystroke should clearly be broken out as a helper. We strive to make each function do one thing well. It should be possible to read and absorb the meaning of a function in a single screenful of code, with no scrolling around. No one has posted an Answer, so there's still time to revise the Question. Also, you might comment on the decision to not spawn N threads when running on an N-core machine. \$\endgroup\$getchar()
keystroke should clearly be broken out as a helper". I will separate the loops and the other function into separate code blocks. \$\endgroup\$switch (getchar()) {
chunk of code in the middle of the main loop. Currently it is broken out as ahandle_input()
helper. Thank you, that is exactly the refactor I was encouraging you to take on. \$\endgroup\$scaled_h
declared as used indouble real_y = (y_px / scaled_h) - 1.0;
? Have you tried compiling what is posted here? \$\endgroup\$