/** 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))) #define PRESORT_UNSOLVED (1 << 0) #define PRESORT_VISITED (1 << VISITED) //#define PRESORT_INTERIOR (1 << INTERIOR) //in set, NOT an edge //#define PRESORT_BACKTRACKED (1 << BACKTRACED) //#define PRESORT_EXTERIOR (1 << //we'll be storing info in the green channel to utalize all available memory. //the following is bitmasks to do so #define GCHAN_RENDERED (1 << 0) #define GCHAN_VISITED (1 << 1) #define GCHAN_BLOCKED (1 << 2) //interior element or backtrack #define GCHAN_EXTERNAL (1 << 3) #define GCHAN_DEBUG (1 << 4) //extra, not nessesary /** void switch_pixel(coord &this_coord, const coord step, size_t this_index, int dir) { } **/ 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)); static Camera2D debug_cam = {0}; debug_cam.zoom = (float)GetRenderWidth()/RES_X; /** //for keeping track of border only. will organize later uint8_t set[(160*80)/8] = {0}; uint8_t unset[(160*80)/8] = {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} }; static int debug_color = 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]; //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; 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 & GCHAN_RENDERED) { gchan_info &= ~(GCHAN_RENDERED); if(gchan_info & GCHAN_EXTERNAL) { interior = false; gchan_info = GCHAN_BLOCKED; } if(gchan_info & GCHAN_BLOCKED) gchan_info = GCHAN_BLOCKED; nei_presort[nei_dir] = gchan_info; } else { int i = iterate(get_neighbor_coord(this_coord, nei_dir, scale)); pixels[nei_i] = get_color(i); pixels[nei_i].g = GCHAN_RENDERED; if(i == ITERS) nei_presort[nei_dir] = 0; else { //exterior interior = false; nei_presort[nei_dir] = GCHAN_BLOCKED; pixels[nei_i].g |= GCHAN_EXTERNAL; } } } if(interior) { printf("interior\n"); asm volatile("interior_check:"); pixels[this_index].g = GCHAN_RENDERED | 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_VISITED; //so we don't think we need to backtrack } else { int blocked_cnt = 0; for(int nei_dir = 0; nei_dir < 8; nei_dir++) { int offset_cw = (last_direction - nei_dir) % 8; int offset_ccw = (nei_dir - last_direction) % 8; int forward_offset; switch(nei_presort[nei_dir]) { case GCHAN_VISITED: nei_priority[nei_dir] = 15; break; case GCHAN_BLOCKED: case GCHAN_EXTERNAL: nei_priority[nei_dir] = -1; blocked_cnt++; break; default: //unvisited element if((nei_presort[(nei_dir - 1) % 8] == 0) || (nei_presort[(nei_dir + 1) % 8] == 0)) { nei_priority[nei_dir] = 3; break; } if((nei_presort[(nei_dir - 1) % 8] == GCHAN_VISITED) || (nei_presort[(nei_dir + 1) % 8] == GCHAN_VISITED)) { nei_priority[nei_dir] = 7; break; } nei_priority[nei_dir] = 11; break; } if(nei_priority[nei_dir] < 0) continue; forward_offset = abs((offset_cw < offset_ccw) ? offset_cw : offset_ccw); if(forward_offset < 3) nei_priority[nei_dir] -= (3-forward_offset); } if(blocked_cnt == 8) { for(int nd = 0; nd < 8; nd++) printf("%i, ", nei_priority[nd]); printf("we blocked ourselves in!\n"); for(;;) sleep(10); exit(1); } } for(int priority = 0; priority < 17; priority++) { for(int nei_dir = 0; nei_dir < 8; nei_dir++) { if(nei_priority[nei_dir] != priority) continue; if(nei_dir % 2) 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("] -> "); // if(pixels[this_index].g & GCHAN_VISITED) { if(priority >= 12) { pixels[this_index].g |= GCHAN_BLOCKED; printf("backtracking!!!\n"); } else pixels[this_index].g |= GCHAN_VISITED; memcpy(last_nei_priority, nei_priority, sizeof(nei_priority)); last_direction = nei_dir; 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; /** BeginDrawing(); DrawPixel(debug_x, debug_y, debug_colors[debug_color % (sizeof(debug_colors) / sizeof(*debug_colors))]); EndDrawing(); */ //FOR VISUAL DEBUGGING- read warning on line 0! { static bool hit_debug_pix = false; const float dbg_cam_step = 100; const float dbg_cam_zoom = .25; if((debug_x == 1046) && (debug_y == 126)) hit_debug_pix = true; if(hit_debug_pix) { for(;;) { switch(GetKeyPressed()) { case KEY_UP: debug_cam.offset.y += dbg_cam_step; break; case KEY_DOWN: debug_cam.offset.y -= dbg_cam_step; break; case KEY_RIGHT: debug_cam.offset.x += dbg_cam_step; break; case KEY_LEFT: debug_cam.offset.x -= dbg_cam_step; break; case KEY_W: debug_cam.zoom += dbg_cam_zoom; break; case KEY_S: debug_cam.zoom -= dbg_cam_zoom; break; case KEY_ENTER: goto switch_pixel; default: // BeginDrawing(); BeginDrawing(); const int dbg_clrs = 32; uint8_t this_dbg_clr = ((debug_color++) % dbg_clrs) * (255 / dbg_clrs); debug_pix[this_index] = (Color) {this_dbg_clr, this_dbg_clr, this_dbg_clr, 255}; BeginDrawing(); UpdateTexture(debug_tex, debug_pix); DrawTextureEx(debug_tex, (Vector2) {0 - debug_cam.offset.x, debug_cam.offset.y}, 0, debug_cam.zoom, WHITE); EndDrawing(); // EndDrawing(); } } } } goto switch_pixel; } } switch_pixel: } debug_color++; } 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; }