562 lines
17 KiB
Plaintext

/** 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 <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <raylib.h>
#include <raymath.h>
#include <limits.h>
#include <complex.h>
#include <string.h>
#include <unistd.h>
#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;
}