summaryrefslogtreecommitdiffstats
path: root/main.c
diff options
context:
space:
mode:
Diffstat (limited to 'main.c')
-rw-r--r--main.c281
1 files changed, 281 insertions, 0 deletions
diff --git a/main.c b/main.c
new file mode 100644
index 0000000..d286ebb
--- /dev/null
+++ b/main.c
@@ -0,0 +1,281 @@
+/*********************************************************************
+ * kd-forest *
+ * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * This program is free software. It comes without any warranty, to *
+ * the extent permitted by applicable law. You can redistribute it *
+ * and/or modify it under the terms of the Do What The Fuck You Want *
+ * To Public License, Version 2, as published by Sam Hocevar. See *
+ * the COPYING file or http://www.wtfpl.net/ for more details. *
+ *********************************************************************/
+
+// Number of trailing zero bits on each color chanel, set to zero for all
+// 24-bit images
+#define ZERO_BITS 0
+// Whether to sort by hue
+#define HUE_SORT 1
+
+#if HUE_SORT
+# define PASSES 16
+# define RANDOMIZE 0
+#else
+# define PASSES 1
+# define RANDOMIZE 1
+#endif
+
+#include "kd-forest.h"
+#include "util.h"
+#include <errno.h>
+#include <math.h>
+#include <png.h>
+#include <setjmp.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#if __unix__
+#include <unistd.h>
+#endif
+
+unsigned int
+rand_in(unsigned int range)
+{
+ // Compensate for bias if (RAND_MAX + 1) isn't a multiple of range
+ unsigned int limit = RAND_MAX + 1U - ((RAND_MAX + 1U)%range);
+ unsigned int res;
+ do {
+ res = rand();
+ } while (res >= limit);
+ return res%range;
+}
+
+kd_node_t *
+try_neighbor(kd_node_t *node, unsigned int width, unsigned int height,
+ int which)
+{
+ int dx = which%3 - 1;
+ int dy = which/3 - 1;
+
+ if (dx < 0 && node->x < -dx) {
+ return NULL;
+ } else if (dx > 0 && node->x + dx >= width) {
+ return NULL;
+ } else if (dy < 0 && node->y < -dy) {
+ return NULL;
+ } else if (dy > 0 && node->y + dy >= height) {
+ return NULL;
+ }
+
+ return node + (int)width*dy + dx;
+}
+
+kd_node_t *
+next_neighbor(kd_node_t *node, unsigned int width, unsigned int height)
+{
+ unsigned int first = rand_in(9);
+
+ for (unsigned int i = first; i < first + 9; ++i) {
+ int which = i%9;
+ if (which == 4) {
+ // Skip self
+ continue;
+ }
+
+ kd_node_t *neighbor = try_neighbor(node, width, height, which);
+ if (neighbor && !neighbor->added) {
+ return neighbor;
+ }
+ }
+
+ return NULL;
+}
+
+void
+remove_if_surrounded(kd_forest_t *kdf, kd_node_t *node, unsigned int width,
+ unsigned int height)
+{
+ if (node->added && !node->removed
+ && next_neighbor(node, width, height) == NULL) {
+ kdf_remove(kdf, node);
+ }
+}
+
+void
+remove_non_boundary(kd_forest_t *kdf, kd_node_t *node, unsigned int width,
+ unsigned int height)
+{
+ for (int i = 0; i < 9; ++i) {
+ kd_node_t *neighbor = try_neighbor(node, width, height, i);
+ if (neighbor) {
+ remove_if_surrounded(kdf, neighbor, width, height);
+ }
+ }
+}
+
+#if HUE_SORT
+#define PI 3.1415926535897932
+
+static double
+hue(uint32_t color)
+{
+ int R = (color >> 16) & 0xFF;
+ int G = (color >> 8) & 0xFF;
+ int B = color & 0xFF;
+
+ double hue = atan2(sqrt(3.0)*(G - B), 2*R - G - B);
+ if (hue < 0.0) {
+ hue += 2.0*PI;
+ }
+ return hue;
+}
+
+static int
+hue_comparator(const void *a, const void *b)
+{
+ double ahue = hue(*(uint32_t *)a);
+ double bhue = hue(*(uint32_t *)b);
+ return (ahue > bhue) - (ahue < bhue);
+}
+
+#endif
+
+int
+main(void)
+{
+ const unsigned int jump = 1U << ZERO_BITS;
+ const unsigned int width = 1U << ((24 - 3*ZERO_BITS + 1)/2); // Round up
+ const unsigned int height = 1U << ((24 - 3*ZERO_BITS)/2); // Round down
+ const unsigned int size = width*height;
+
+ printf("Generating a %ux%u image (%u pixels)\n", width, height, size);
+
+ // Generate all the colors
+ uint32_t *colors = xmalloc(size*sizeof(uint32_t));
+ for (unsigned int b = 0, i = 0; b < 0x100; b += jump) {
+ for (unsigned int g = 0; g < 0x100; g += jump) {
+ for (unsigned int r = 0; r < 0x100; r += jump, ++i) {
+ colors[i] = (r << 16) | (g << 8) | b;
+ }
+ }
+ }
+ srand(0);
+#if RANDOMIZE
+ // Fisher-Yates shuffle
+ for (unsigned int i = size; i-- > 0;) {
+ unsigned int j = rand_in(i + 1);
+ uint32_t temp = colors[i];
+ colors[i] = colors[j];
+ colors[j] = temp;
+ }
+#endif
+#if HUE_SORT
+ qsort(colors, size, sizeof(uint32_t), hue_comparator);
+#endif
+
+ // Make a pool of potential k-d nodes
+ kd_node_t *nodes = xmalloc(size*sizeof(kd_node_t));
+ for (unsigned int y = 0, i = 0; y < height; ++y) {
+ for (unsigned int x = 0; x < width; ++x, ++i) {
+ kd_node_init(nodes + y*width + x, x, y);
+ }
+ }
+
+ // Make the forest
+ kd_forest_t kdf;
+ kdf_init(&kdf);
+
+#if __unix__
+ bool tty = isatty(1);
+ const char *clear_line = tty ? "\033[2K\r" : "";
+ const char *new_line = tty ? "" : "\n";
+#else
+ const char *clear_line = "";
+ const char *new_line = "\n";
+#endif
+
+ size_t max_size = 0;
+
+ // Do multiple passes to get rid of artifacts in HUE_SORT mode
+ for (unsigned int i = 0, progress = 0; i < PASSES; ++i) {
+ for (unsigned int j = i; j < size; j += PASSES, ++progress) {
+ if (progress%width == 0) {
+ printf("%s%.2f%%\t| boundary size: %zu\t| max boundary size: %zu%s",
+ clear_line, 100.0*progress/size, kdf.size, max_size, new_line);
+ fflush(stdout);
+ }
+
+ uint32_t color = colors[j];
+
+ kd_node_t target;
+ kd_node_set_color(&target, color);
+
+ kd_node_t *new_node;
+ if (j == 0) {
+ // First node goes in the center
+ new_node = nodes + size/2 + width/2;
+ } else {
+ kd_node_t *nearest = kdf_find_nearest(&kdf, &target);
+ new_node = next_neighbor(nearest, width, height);
+ }
+
+ kd_node_set_color(new_node, color);
+ kdf_insert(&kdf, new_node);
+ remove_non_boundary(&kdf, new_node, width, height);
+
+ if (kdf.size > max_size) {
+ max_size = kdf.size;
+ }
+ }
+ }
+ printf("%s%.2f%%\t| boundary size: 0\t| max boundary size: %zu\n",
+ clear_line, 100.0, max_size);
+
+ FILE *file = fopen("kd-forest.png", "wb");
+ if (!file) {
+ abort();
+ }
+
+ png_structp png_ptr =
+ png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL);
+ if (!png_ptr) {
+ abort();
+ }
+
+ png_infop info_ptr = png_create_info_struct(png_ptr);
+ if (!info_ptr) {
+ abort();
+ }
+
+ // libpng will longjmp here if it encounters an error from now on
+ if (setjmp(png_jmpbuf(png_ptr))) {
+ abort();
+ }
+
+ png_init_io(png_ptr, file);
+ png_set_IHDR(png_ptr, info_ptr, width, height, 8,
+ PNG_COLOR_TYPE_RGB, PNG_INTERLACE_NONE,
+ PNG_COMPRESSION_TYPE_DEFAULT, PNG_FILTER_TYPE_DEFAULT);
+ png_set_sRGB_gAMA_and_cHRM(png_ptr, info_ptr, PNG_sRGB_INTENT_ABSOLUTE);
+
+ png_write_info(png_ptr, info_ptr);
+
+ uint8_t *row = xmalloc(3*width*sizeof(uint8_t));
+ for (unsigned int y = 0; y < height; ++y) {
+ for (unsigned int x = 0; x < width; ++x) {
+ kd_node_t *node = nodes + y*width + x;
+ row[3*x] = node->coords[0];
+ row[3*x + 1] = node->coords[1];
+ row[3*x + 2] = node->coords[2];
+ }
+ png_write_row(png_ptr, (png_bytep)row);
+ }
+
+ png_write_end(png_ptr, info_ptr);
+
+ free(row);
+ png_destroy_write_struct(&png_ptr, &info_ptr);
+ fclose(file);
+ kdf_destroy(&kdf);
+ free(nodes);
+ free(colors);
+ return 0;
+}