#include <math.h>
#include <stdio.h>

#include "uthash.h"
#include "utlist.h"

// minus one for extra vertex
#define VOXEL_SIDE 31
#define BITS_PER_SIDE 5
#define VERTEX_MASK 0x1F

#define EXTRACT_BITS(value, offset, count) ((value >> offset) & (0xFFFFFFFF >> (32 - count)))

static char voxel[VOXEL_SIDE][VOXEL_SIDE][VOXEL_SIDE] = { 0 };

struct vertex_hash {
	int id;			/* key */
	int n;			/* value */
	UT_hash_handle hh;	/* hash */
};
struct vertex_hash *vertices = NULL;

struct face_list {
	int ns[3];		/* value */
	struct face_list *next;
};
struct face_list *faces = NULL;

static inline int voxel_valid(int x, int y, int z)
{
	return x >= 0 && x < VOXEL_SIDE
		&& y >= 0 && y < VOXEL_SIDE
		&& z >= 0 && z < VOXEL_SIDE;
}

static inline int vertex_compress(int x, int y, int z)
{
	return (x & VERTEX_MASK) | ((y & VERTEX_MASK) << BITS_PER_SIDE) | ((z & VERTEX_MASK) << (BITS_PER_SIDE * 2));
}

static int get_vertex_index(int x, int y, int z)
{
	static int vertex_iota = 0;

	int id = vertex_compress(x, y, z);
#ifdef DEBUG
	printf("Compressed: %i\n", id);
#endif
	struct vertex_hash *h;
	HASH_FIND_INT(vertices, &id, h);

	if (h == NULL)
	{
#ifdef DEBUG
		printf("Failed to find a vertex (%i %i %i), making a new one then!\n", x, y, z);
#endif
		h = (struct vertex_hash*) malloc(sizeof *h);
		h->id = id;
		h->n = vertex_iota++;
		HASH_ADD_INT(vertices, id, h);

		return h->n;
	}

	return h->n;
}

static inline void make_face(int id1, int id2, int id3, int id4)
{
	struct face_list *face1 = (struct face_list*) malloc(sizeof *face1);
	//face1->ns = (int[3]) { id1, id2, id3 }; // LIFE COULD BE DREAM...
	face1->ns[0] = id1;
	face1->ns[1] = id2;
	face1->ns[2] = id3;
	LL_APPEND(faces, face1);

	struct face_list *face2 = (struct face_list*) malloc(sizeof *face1);
	//face2->ns = (int[3]) { id3, id4, id1 }; // LIFE COULD BE DREEEEAAAAAM.....
	face2->ns[0] = id3;
	face2->ns[1] = id4;
	face2->ns[2] = id1;
	LL_APPEND(faces, face2);
}

static inline void make_cube(int x, int y, int z)
{
#ifdef DEBUG
	printf("Block color: %i\n", (int) voxel[x][y][z]);
#endif
	if (voxel[x][y][z] == 0)
		return;

	/* Replace Y with - 1 if it points down */
	int vertex_offsets[8][3] = {
		{ 0, 0, 0 },
		{ 0, 1, 0 },
		{ 0, 0, 1 },
		{ 0, 1, 1 },
		{ 1, 0, 0 },
		{ 1, 1, 0 },
		{ 1, 0, 1 },
		{ 1, 1, 1 }
	};

	int vertices_cache[8] = { -1, -1, -1, -1, -1, -1, -1, -1 };
	int _get_v(int i)
	{
		if (vertices_cache[i] == -1)
			vertices_cache[i] = get_vertex_index(x + vertex_offsets[i][0], y + vertex_offsets[i][1], z + vertex_offsets[i][2]);
		return vertices_cache[i];
	}

	/* Front and back */
	if (!voxel_valid(x - 1, y, z) || voxel[x - 1][y][z] == 0)
		make_face(_get_v(0), _get_v(1), _get_v(3), _get_v(2));
	if (!voxel_valid(x + 1, y, z) || voxel[x + 1][y][z] == 0)
		make_face(_get_v(6), _get_v(7), _get_v(5), _get_v(4));

	/* Left and right */
	if (!voxel_valid(x, y, z - 1) || voxel[x][y][z - 1] == 0)
		make_face(_get_v(0), _get_v(4), _get_v(5), _get_v(1));
	if (!voxel_valid(x, y, z + 1) || voxel[x][y][z + 1] == 0)
		make_face(_get_v(2), _get_v(3), _get_v(7), _get_v(6));

	/* Top and bottom */
	if (!voxel_valid(x, y - 1, z) || voxel[x][y - 1][z] == 0)
		make_face(_get_v(4), _get_v(0), _get_v(2), _get_v(6));
	if (!voxel_valid(x, y + 1, z) || voxel[x][y + 1][z] == 0)
		make_face(_get_v(1), _get_v(5), _get_v(7), _get_v(3));
}

int main(int, char**)
{
	/* Generating voxel world */
	for (int x = 0; x < VOXEL_SIDE; x++)
	for (int y = 0; y < VOXEL_SIDE; y++)
	for (int z = 0; z < VOXEL_SIDE; z++)
	{
		float lx = x - 16.f, ly = y - 16.f, lz = z - 16.f;
		if (sqrt(lx * lx + ly * ly + lz * lz) < (float) (VOXEL_SIDE / 2))
//		if (x == 0 || x == VOXEL_SIDE - 1 || y == 0 || y == VOXEL_SIDE - 1 || z == 0 || z == VOXEL_SIDE - 1)
//		if (y == 0)
			voxel[x][y][z] = 1;
	}

	/* Making a mesh */
	for (int x = 0; x < VOXEL_SIDE; x++)
	for (int y = 0; y < VOXEL_SIDE; y++)
	for (int z = 0; z < VOXEL_SIDE; z++)
		make_cube(x, y, z);

	/* Writing the mesh to output.obj */
	FILE *f = fopen("output.obj", "w");

	/* Writing verticies */
	{
		struct vertex_hash *current = NULL;
		struct vertex_hash *temp = NULL;
		HASH_ITER(hh, vertices, current, temp)
		{
			fprintf(
				f,
				"v %i %i %i\n",
				EXTRACT_BITS(current->id, 0, BITS_PER_SIDE), // x
				EXTRACT_BITS(current->id, BITS_PER_SIDE, BITS_PER_SIDE), // y
				EXTRACT_BITS(current->id, BITS_PER_SIDE * 2, BITS_PER_SIDE) // z
			);
		}
	}

	/* Writing faces */
	{
		struct face_list *current = NULL;
		LL_FOREACH(faces, current)
		{
			fprintf(
				f,
				"f %i %i %i\n",
				current->ns[0] + 1,
				current->ns[1] + 1,
				current->ns[2] + 1
			);
		}
	}

	fclose(f);

	return 0;
}