/** READ BEFORE JUDING! * Yes, I know this code is a mess. Debug code is added * happhazardly, two cameras are used, etc. * That's because it's a temporary program * to create optimizations and debug rendering issues without hardware. * None of this is going to be included in the project, and the code is thus * not extensible or organized; it really doesn't save any effort to do so. * * This code is meant for my eyes only. You've been warned! * */ #include #include #include #include #include #include #include #include #include #define WINDOW_SIZE_X 1600 #define WINDOW_SIZE_Y 800 #define RES_X 1600 #define RES_Y 800 #define DEFAULT_CENTER_X 0 #define DEFAULT_CENTER_Y 0 #define MOUSE_BUTTON 0 #define STEP_SIZE .1 #define ZOOM_SIZE .1 #define DECIMAL_LOC 28 #define DOUBLE_SCALER (1 << DECIMAL_LOC) #define DOUBLE_TO_FIXED(val) (int32_t)((val) * DOUBLE_SCALER) #define FIXED_MULTIPLY(x,y) ((((uint64_t)(x))*(y)) >> DECIMAL_LOC) #define FIXED_TO_DOUBLE(val) ((val) / (double)DOUBLE_SCALER) #define INFTY 2 #define INFTY_SQR INFTY * INFTY #define ITERS 255 #define INFTY_SQR_FIXED DOUBLE_TO_FIXED(INFTY_SQR) //#define SHIP //#undef SHIP int debug_x, debug_y; #ifdef SHIP Color get_color(int i) { if(i == ITERS) return (Color){0, 0, 0, 255}; if(i == 0) return (Color){0, 0, 0, 255}; return (Color) { 2*(i - 128)+255, 0, 0, 255 }; } #else Color get_color(int i) { // if((i == ITERS) || (i == 0)) return (Color){0, 0, 0, 255}; if(i == ITERS) return (Color){0,0,0,255}; if(i == 0) return (Color){0,0,1,255}; if(i < 128) { return (Color) { (8*(i - 128)+255) & 0xff, 0, (16*(i - 64)+255) & 0xff, 255 }; } return (Color) { 0, 0, ((unsigned int)-2*(i - 128)+255) & 0xff, 255 }; } #endif //TODO remove struct debug_info { int32_t r, i; int x, y; }; __attribute__((used)) struct debug_info debug_get_coord(size_t i) { struct debug_info ret; ret.x = i % RES_X; ret.y = i / RES_Y; return ret; } struct camera { double min_r, min_i, max_r, max_i; }; typedef struct { int32_t r; int32_t i; } FixedCord; static inline int iterate(FixedCord c) { int32_t z_i = 0; int32_t z_r = 0; int32_t z_r_2, z_i_2, zn_r, zn_i; for(int it = 0; it < ITERS; it++) { z_r_2 = FIXED_MULTIPLY(z_r, z_r); z_i_2 = FIXED_MULTIPLY(z_i, z_i); zn_r = z_r_2 - z_i_2 + c.r; #ifdef SHIP zn_i = abs(FIXED_MULTIPLY((DOUBLE_TO_FIXED(2)), (FIXED_MULTIPLY(z_r, z_i)))) + c.i; #else zn_i = (FIXED_MULTIPLY((DOUBLE_TO_FIXED(2)), (FIXED_MULTIPLY(z_r, z_i)))) + c.i; #endif z_i = zn_i; z_r = zn_r; if(z_i_2 + z_r_2 > INFTY_SQR_FIXED) return it; } return ITERS; } //blllluuuuurg, matracies and vectors in raylib are floats and we need doubles void shift_cam(struct camera *cam, double step_r, double step_i) { double i_offset = (cam->max_i - cam->min_i) * step_i; double r_offset = (cam->max_r - cam->min_r) * step_r; cam->min_i += i_offset; cam->max_i += i_offset; cam->min_r += r_offset; cam->max_r += r_offset; } void zoom_cam(struct camera *cam, double zoom) { double i_scale = (cam->max_i - cam->min_i) * zoom; double r_scale = (cam->max_r - cam->min_r) * zoom; cam->min_i += i_scale; cam->max_i -= i_scale; cam->min_r += r_scale; cam->max_r -= r_scale; } enum DIRECTIONS { N, NE, E, SE, S, SW, W, NW }; //we can inline these if needed inline bool bitarray_check(uint8_t *array, size_t i) { return array[i/8] & (1 << (i%8)); } inline void bitarray_set(uint8_t *array, size_t i) { array[i/8] |= (1 << (i%8)); } inline FixedCord get_neighbor_coord(FixedCord from_coord, int direction, FixedCord step) { if((direction == NW) || (direction < E)) from_coord.i += step.i; if((direction > N) && (direction < S)) from_coord.r += step.r; if((direction > E) && (direction < W)) from_coord.i -= step.i; if(direction > S) from_coord.r -= step.r; return from_coord; } FixedCord get_neighbor_coord(FixedCord from_coord, int direction, FixedCord step); size_t get_neighbor_index(size_t from_pixel, int direction) { const int neighbor_index_accl[8] = {-RES_X, -RES_X + 1, 1, RES_X + 1, RES_X, RES_X - 1, -1, -RES_X - 1}; from_pixel += neighbor_index_accl[direction]; //canidate for optimization; lots of branches. maybe inline return from_pixel; } bool bitarray_check(uint8_t *array, size_t i); void bitarray_set(uint8_t *array, size_t i); #define BITARRAY_SET(array, i) ((array)[(i)/8] |= (1 << ((i) % 8))) #define BITARRAY_CLEAR(array, i) ((array)[(i)/8] &= ~(1 << ((i) % 8))) #define BITARRAY_CHECK(array, i) ((array)[(i)/8] & (1 << ((i) % 8))) //we'll be storing info in the green channel to utalize available memory //per pixel. #define GCHAN_BLOCKED (1 << 0) //interior element or visiteed #define GCHAN_INTERNAL (1 << 1) //part of set #define GCHAN_EXTERNAL (1 << 2) //not part of set #define GCHAN_DEBUG (1 << 3) //extra, not nessesary #define BACKSTACK_SIZE 32 /** void switch_pixel(coord &this_coord, const coord step, size_t this_index, int dir) { } **/ void debug_step(Color *pix, Texture *tex, size_t index) { static Camera2D cam = {0}; if(!cam.zoom) cam.zoom = (float)GetRenderWidth()/RES_X; static int debug_color = 0; const Color debug_colors[] = { (Color) {0xff, 0x00, 0x00, 0xff}, (Color) {0xff, 0x00, 0xff, 0xff}, (Color) {0x00, 0xff, 0x00, 0xff}, (Color) {0x00, 0x00, 0xff, 0xff}, (Color) {0x6a, 0x00, 0xff, 0xff} }; const float dbg_cam_step = 100; const float dbg_cam_zoom = .25; for(;;) { switch(GetKeyPressed()) { case KEY_UP: cam.offset.y += dbg_cam_step; break; case KEY_DOWN: cam.offset.y -= dbg_cam_step; break; case KEY_RIGHT: cam.offset.x += dbg_cam_step; break; case KEY_LEFT: cam.offset.x -= dbg_cam_step; break; case KEY_W: cam.zoom += dbg_cam_zoom; break; case KEY_S: cam.zoom -= dbg_cam_zoom; break; case KEY_ENTER: return; default: BeginDrawing(); const int dbg_clrs = 32; uint8_t this_dbg_clr = ((debug_color++) % dbg_clrs) * (255 / dbg_clrs); pix[index] = (Color) {this_dbg_clr, this_dbg_clr, this_dbg_clr, 255}; BeginDrawing(); UpdateTexture(*tex, pix); DrawTextureEx(*tex, (Vector2) {0 - cam.offset.x, cam.offset.y}, 0, cam.zoom, WHITE); EndDrawing(); } } } unsigned int mandelbrot_bordertrace(struct camera *cam, Color *pixels) { //these lookup tables r cheap cuz on the stm32f1, 1 memory read is 1 instruction FixedCord scale = { .r = DOUBLE_TO_FIXED((cam->max_r - cam->min_r) / (double)RES_X), .i = DOUBLE_TO_FIXED((cam->max_i - cam->min_i) / (double)RES_Y)}; FixedCord c = {.r = 0, .i = DOUBLE_TO_FIXED(cam->max_i)}; unsigned int total_iters = 0; size_t on_pixel = 0; //for camera border calculations int32_t cam_bord_fixed_n = DOUBLE_TO_FIXED(cam->min_i); int32_t cam_bord_fixed_s = DOUBLE_TO_FIXED(cam->max_i); int32_t cam_bord_fixed_e = DOUBLE_TO_FIXED(cam->max_r); int32_t cam_bord_fixed_w = DOUBLE_TO_FIXED(cam->min_r); //I know this is gross, just for debugigng! //will clean up once I get things ironed out Image img = GenImageColor(RES_X, RES_Y, BLUE); Texture debug_tex = LoadTextureFromImage(img); UnloadImage(img); Color *debug_pix = malloc(RES_X * RES_Y * sizeof(Color)); memcpy(debug_pix, pixels, RES_X * RES_Y * sizeof(Color)); /** //for keeping track of border only. will organize later uint8_t set[(160*80)/8] = {0}; uint8_t unset[(160*80)/8] = {0}; **/ for(int y = 0; y < RES_Y; y++) { c.r = DOUBLE_TO_FIXED(cam->min_r); for(int x = 0; x < RES_X; x++) { int i = iterate(c); total_iters += i; pixels[on_pixel] = get_color(i); if(i == ITERS) { FixedCord this_coord = c; size_t this_index = on_pixel; int nei_priority[8]; int last_nei_priority[8]; int last_direction = E; int nei_presort[8]; size_t backstack[BACKSTACK_SIZE]; size_t backstack_i = 0; //only really need to zero green channel bzero(pixels, RES_X * RES_Y * sizeof(*pixels)); //this is so fucking knarly printf("NEW BORDER\n"); while(true) { //step 1: check pixels around us, fill in neighbors. bzero(nei_presort, sizeof(nei_presort)); //find if we're pushed against screen border. //feels gross but I don't think there's a better way if((this_coord.i - scale.i) < cam_bord_fixed_n) { for(int nei_dir = SE; nei_dir <= SW; nei_dir++) nei_presort[nei_dir] = GCHAN_EXTERNAL; } else if((this_coord.i + scale.i) > cam_bord_fixed_s) { nei_presort[NE] = GCHAN_EXTERNAL; nei_presort[N] = GCHAN_EXTERNAL; nei_presort[NW] = GCHAN_EXTERNAL; } if((this_coord.r - scale.r) < cam_bord_fixed_w) { for(int nei_dir = SW; nei_dir < NW; nei_dir++) nei_presort[nei_dir] = GCHAN_EXTERNAL; } else if((this_coord.r + scale.r) > cam_bord_fixed_e) { for(int nei_dir = NE; nei_dir < SE; nei_dir++) nei_presort[nei_dir] = GCHAN_EXTERNAL; } /** now fill in neighbor info based on green channel, * iterate if no info available. * if this is to slow we could flatten this; it's predictable * where there will be info **/ // TODO replace modulos with something faster bool interior = true; for(int nei_dir = 0; nei_dir < 8; nei_dir++) { size_t nei_i; uint8_t gchan_info; //happens if we're pushed against the screen if(nei_presort[nei_dir] == GCHAN_EXTERNAL) { interior = false; nei_presort[nei_dir] = GCHAN_EXTERNAL; continue; } nei_i = get_neighbor_index(this_index, nei_dir); gchan_info = pixels[nei_i].g; //note that when we move this over, there will be no alpha channel. //gchan_info will be extracted differently!!! if(gchan_info) { if(gchan_info & GCHAN_EXTERNAL) interior = false; nei_presort[nei_dir] = gchan_info; } else { int i = iterate(get_neighbor_coord(this_coord, nei_dir, scale)); pixels[nei_i] = get_color(i); if(i == ITERS) nei_presort[nei_dir] = GCHAN_INTERNAL; else { //exterior interior = false; nei_presort[nei_dir] = GCHAN_EXTERNAL; } pixels[nei_i].g = nei_presort[nei_dir]; } } //go back if we're in the interior and not an edge if(interior) { printf("interior\n"); asm volatile("interior_check:"); pixels[this_index].g = GCHAN_BLOCKED; //printf("bruh\n"); memcpy(nei_priority, last_nei_priority, sizeof(nei_priority)); nei_priority[last_direction] = -1; this_index = get_neighbor_index(this_index, (last_direction + 4) % 8); this_coord = get_neighbor_coord( this_coord, (last_direction + 4) % 8, scale); pixels[this_index].g = GCHAN_BLOCKED; //so we don't think we need to backtrack } else { int edge_cnt = 0; //sort into prioraties for(int nei_dir = 0; nei_dir < 8; nei_dir += 2) { int nei_1 = nei_presort[(nei_dir + 1) % 8]; int nei_2 = nei_presort[(nei_dir - 1) % 8]; if((nei_presort[nei_dir] != GCHAN_INTERNAL) || ((nei_1 & nei_2) & (GCHAN_EXTERNAL | GCHAN_BLOCKED))) { nei_priority[nei_dir] = -1; } else if(((nei_1 ^ nei_2) & (GCHAN_INTERNAL | GCHAN_EXTERNAL)) == (GCHAN_INTERNAL | GCHAN_EXTERNAL)) { edge_cnt++; nei_priority[nei_dir] = 0; } else if(nei_1 & nei_2 & GCHAN_INTERNAL) { nei_priority[nei_dir] = 1; } else if(((nei_1 ^ nei_2) & (GCHAN_BLOCKED | GCHAN_EXTERNAL)) == (GCHAN_BLOCKED | GCHAN_EXTERNAL)) { nei_priority[nei_dir] = 2; } } if(edge_cnt >= 2) { backstack[backstack_i] = this_index; if(backstack_i++ > BACKSTACK_SIZE) { printf("max backstack\n"); for(;;); } printf("backstack increased\n"); } } //now go to canidate with lowest prioraty for(int priority = 0; priority <= 1; priority++) { for(int nei_dir = 0; nei_dir < 8; nei_dir += 2) { if(nei_priority[nei_dir] != priority) continue; printf("(%zu, %zu): dir %i. [", this_index % RES_X, this_index / RES_X, nei_dir); for(int nd = 0; nd < 8; nd++) printf("%i, ", nei_priority[nd]); printf("] -> "); pixels[this_index].g = GCHAN_BLOCKED; memcpy(last_nei_priority, nei_priority, sizeof(nei_priority)); this_index = get_neighbor_index(this_index, nei_dir); this_coord = get_neighbor_coord(this_coord, nei_dir, scale); printf("(%zu, %zu)\n", this_index % RES_X, this_index / RES_X); debug_x = this_index % RES_X; debug_y = this_index / RES_X; //FOR VISUAL DEBUGGING- read warning on line 0! { static bool hit_debug_pix = true; if((debug_x == 1046) && (debug_y == 126)) hit_debug_pix = true; if(hit_debug_pix) debug_step(debug_pix, &debug_tex, this_index); } goto next_pixel; } } printf("checking backtrack stack\nThis pri:"); for(int nd = 0; nd < 8; nd++) printf("%i, ", nei_priority[nd]); printf("\n"); if(--backstack_i > BACKSTACK_SIZE) { printf("backstack depleated, no recovery\n"); for(;;); } printf("%lu\n", backstack_i); this_index = backstack[backstack_i]; this_coord.r = (((this_index % RES_X) / (float)RES_X) * (cam->max_r - cam->min_r)) + cam->min_r; this_coord.i = (((this_index / RES_X) / (float)RES_Y) * (cam->max_i - cam->min_i)) + cam->min_i; debug_step(debug_pix, &debug_tex, this_index); next_pixel: } } on_pixel++; c.r += scale.r; } c.i -= scale.i; } return total_iters; } unsigned int mandelbrot_unoptimized(struct camera *cam, Color *pixels) { FixedCord scale = { .r = DOUBLE_TO_FIXED((cam->max_r - cam->min_r) / (double)RES_X), .i = DOUBLE_TO_FIXED((cam->max_i - cam->min_i) / (double)RES_Y) }; FixedCord c = { .r = 0, .i = DOUBLE_TO_FIXED(cam->max_i) }; unsigned int total_iters = 0; for(int y = 0; y < RES_Y; y++) { c.r = DOUBLE_TO_FIXED(cam->min_r); for(int x = 0; x < RES_X; x++) { int i = iterate(c); total_iters += i; pixels[((y * RES_X) + x)] = get_color(i); c.r += scale.r; } c.i -= scale.i; } return total_iters; } void test() { uint8_t bitarray[(160*80)/8] = {0}; int test_i = 9; BITARRAY_SET(bitarray, test_i); printf("%s\n", BITARRAY_CHECK(bitarray, 9) ? "true" : "false"); } int main() { //test(); //return 0; Color *pixels = malloc(RES_X * RES_Y * sizeof(Color)); struct camera cam = { .min_r = -1, .max_r = 1, // .min_i = -1, // .max_i = 1 }; cam.min_i = ((double)RES_Y / RES_X) * cam.min_r; cam.max_i = ((double)RES_Y / RES_X) * cam.max_r; InitWindow(WINDOW_SIZE_X, WINDOW_SIZE_Y, "mandelbrot fixed point test"); Image img = GenImageColor(RES_X, RES_Y, BLUE); Texture tex = LoadTextureFromImage(img); Texture backdrop = LoadTextureFromImage(img); UnloadImage(img); SetTargetFPS(60); while(!WindowShouldClose()) { switch(GetKeyPressed()) { case KEY_UP: shift_cam(&cam, 0, STEP_SIZE); break; case KEY_DOWN: shift_cam(&cam, 0, -STEP_SIZE); break; case KEY_RIGHT: shift_cam(&cam, STEP_SIZE, 0); break; case KEY_LEFT: shift_cam(&cam, -STEP_SIZE, 0); break; case KEY_W: zoom_cam(&cam, ZOOM_SIZE); break; case KEY_S: zoom_cam(&cam, -ZOOM_SIZE); break; default: BeginDrawing(); EndDrawing(); continue; break; } printf("(%.21f, %.21f) - (%.21f, %.21f)\n", cam.min_r, cam.min_i, cam.max_r, cam.max_i); printf("Unoptimized: %u iterations\n", mandelbrot_unoptimized(&cam, pixels)); BeginDrawing(); UpdateTexture(backdrop, pixels); DrawTextureEx(backdrop, (Vector2){0,0}, 0, (float)GetRenderWidth()/RES_X, WHITE); EndDrawing(); printf("Border tracing: %u iterations\n", mandelbrot_bordertrace(&cam, pixels)); BeginDrawing(); UpdateTexture(tex, pixels); DrawTextureEx(tex, (Vector2){0,0}, 0, (float)GetRenderWidth()/RES_X, WHITE); EndDrawing(); } return 0; }