commit 5b67115268acf849b3e5c7ebb08895a4e38e05d1
parent 0bd78557e526be25ade169f09af521a9da1bf9fc
Author: Christian Ermann <christianermann@gmail.com>
Date: Thu, 5 Aug 2021 19:49:36 -0500
Load surrounding chunks
Diffstat:
10 files changed, 678 insertions(+), 169 deletions(-)
diff --git a/include/chunk.h b/include/chunk.h
@@ -1,16 +1,27 @@
#ifndef CHUNK_H
#define CHUNK_H
-extern const int CHUNK_WIDTH;
+#include "sdf.h"
+
+#include <glad/glad.h>
+
+#define CHUNK_WIDTH 16
+#define CHUNK_VOLUME CHUNK_WIDTH * CHUNK_WIDTH * CHUNK_WIDTH
typedef struct {
- int id[3];
- float origin[3];
+ IVec3 id;
+ unsigned int vertex_count;
+ Vec3 vertices[CHUNK_VOLUME * 15];
+ GLuint vbo;
+ GLuint vao;
} Chunk;
-Chunk Chunk_create(int x, int y, int z);
+void Chunk_init(Chunk *chunk, IVec3 id);
+
+void Chunk_origin(const Chunk *chunk, Vec3 origin);
+
+void Chunk_meshify(Chunk *chunk, SDF f, float isolevel);
-void Chunk_outline(const Chunk* chunk, float corners[24], unsigned int offset,
- unsigned int indices[24]);
+void Chunk_draw(const Chunk *chunk);
#endif
diff --git a/include/chunk_manager.h b/include/chunk_manager.h
@@ -4,15 +4,22 @@
#include "chunk.h"
typedef struct {
+ IVec3 origin;
int radius;
- int chunk_count;
- int origin[3];
- int* offsets;
- Chunk* chunks;
+
+ SDF f;
+ float isolevel;
+
+ unsigned int chunk_count;
+ IVec3 *offsets;
+ Chunk *chunks;
} ChunkManager;
-ChunkManager ChunkManager_create(int radius, float player[3]);
+ChunkManager ChunkManager_create(const Vec3 target, int radius, SDF f,
+ float isolevel);
+
+void ChunkManager_recenter(ChunkManager *cm, const Vec3 target);
-void ChunkManager_update(ChunkManager* chunk_manager, float player[3]);
+void ChunkManager_drawChunks(const ChunkManager *cm);
#endif
diff --git a/include/marching_cubes.h b/include/marching_cubes.h
@@ -0,0 +1,10 @@
+#ifndef MC_H
+#define MC_H
+
+#include "vec.h"
+#include "sdf.h"
+
+int MC_polygonize(const Vec3 corners[8], SDF f, float isolevel,
+ Vec3 triangles[15]);
+
+#endif
diff --git a/include/sdf.h b/include/sdf.h
@@ -0,0 +1,8 @@
+#ifndef SDF_H
+#define SDF_H
+
+#include "vec.h"
+
+typedef float (*SDF)(const Vec3 p);
+
+#endif
diff --git a/include/vec.h b/include/vec.h
@@ -0,0 +1,12 @@
+#ifndef VEC_H
+#define VEC_H
+
+#include <stdbool.h>
+
+typedef int IVec3[3];
+
+bool IVec3_equal(const IVec3 a, const IVec3 b);
+
+typedef float Vec3[3];
+
+#endif
diff --git a/src/chunk.c b/src/chunk.c
@@ -1,93 +1,99 @@
#include "chunk.h"
+#include "marching_cubes.h"
-const int CHUNK_WIDTH = 16;
-
-Chunk Chunk_create(int x, int y, int z)
+void Chunk_init(Chunk *chunk, IVec3 id)
{
- Chunk chunk;
+ chunk->id[0] = id[0];
+ chunk->id[1] = id[1];
+ chunk->id[2] = id[2];
+
+ chunk->vertex_count = 0;
- chunk.id[0] = x;
- chunk.id[1] = y;
- chunk.id[2] = z;
+ glGenVertexArrays(1, &chunk->vao);
+ glBindVertexArray(chunk->vao);
- chunk.origin[0] = x * CHUNK_WIDTH;
- chunk.origin[1] = y * CHUNK_WIDTH;
- chunk.origin[2] = z * CHUNK_WIDTH;
+ glGenBuffers(1, &chunk->vbo);
+ glBindBuffer(GL_ARRAY_BUFFER, chunk->vbo);
- return chunk;
+ glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, sizeof(Vec3), (GLvoid*)0);
+ glEnableVertexAttribArray(0);
+}
+
+void Chunk_origin(const Chunk *chunk, Vec3 origin)
+{
+ origin[0] = chunk->id[0] * CHUNK_WIDTH;
+ origin[1] = chunk->id[1] * CHUNK_WIDTH;
+ origin[2] = chunk->id[2] * CHUNK_WIDTH;
}
-void Cube_corners(const float origin[3], float width, float corners[24])
+static void Cube_corners(const Vec3 origin, float width, Vec3 corners[8])
{
- corners[0] = origin[0];
- corners[1] = origin[1];
- corners[2] = origin[2];
+ corners[0][0] = origin[0];
+ corners[0][1] = origin[1];
+ corners[0][2] = origin[2];
- corners[3] = origin[0] + width;
- corners[4] = origin[1];
- corners[5] = origin[2];
+ corners[1][0] = origin[0] + width;
+ corners[1][1] = origin[1];
+ corners[1][2] = origin[2];
- corners[6] = origin[0] + width;
- corners[7] = origin[1];
- corners[8] = origin[2] + width;
+ corners[2][0] = origin[0] + width;
+ corners[2][1] = origin[1];
+ corners[2][2] = origin[2] + width;
- corners[9] = origin[0];
- corners[10] = origin[1];
- corners[11] = origin[2] + width;
+ corners[3][0] = origin[0];
+ corners[3][1] = origin[1];
+ corners[3][2] = origin[2] + width;
- corners[12] = origin[0];
- corners[13] = origin[1] + width;
- corners[14] = origin[2];
+ corners[4][0] = origin[0];
+ corners[4][1] = origin[1] + width;
+ corners[4][2] = origin[2];
- corners[15] = origin[0] + width;
- corners[16] = origin[1] + width;
- corners[17] = origin[2];
+ corners[5][0] = origin[0] + width;
+ corners[5][1] = origin[1] + width;
+ corners[5][2] = origin[2];
- corners[18] = origin[0] + width;
- corners[19] = origin[1] + width;
- corners[20] = origin[2] + width;
+ corners[6][0] = origin[0] + width;
+ corners[6][1] = origin[1] + width;
+ corners[6][2] = origin[2] + width;
- corners[21] = origin[0];
- corners[22] = origin[1] + width;
- corners[23] = origin[2] + width;
+ corners[7][0] = origin[0];
+ corners[7][1] = origin[1] + width;
+ corners[7][2] = origin[2] + width;
}
-void Cube_outlineIndices(unsigned int offset, unsigned int indices[24])
+void Chunk_meshify(Chunk *chunk, SDF f, float isolevel)
{
- // Bottom edges
- indices[0] = 0 + offset;
- indices[1] = 1 + offset;
- indices[2] = 1 + offset;
- indices[3] = 2 + offset;
- indices[4] = 2 + offset;
- indices[5] = 3 + offset;
- indices[6] = 3 + offset;
- indices[7] = 0 + offset;
-
- // Top edges
- indices[8] = 4 + offset;
- indices[9] = 5 + offset;
- indices[10] = 5 + offset;
- indices[11] = 6 + offset;
- indices[12] = 6 + offset;
- indices[13] = 7 + offset;
- indices[14] = 7 + offset;
- indices[15] = 4 + offset;
-
- // Middle edges
- indices[16] = 0 + offset;
- indices[17] = 4 + offset;
- indices[18] = 1 + offset;
- indices[19] = 5 + offset;
- indices[20] = 2 + offset;
- indices[21] = 6 + offset;
- indices[22] = 3 + offset;
- indices[23] = 7 + offset;
+ chunk->vertex_count = 0;
+ for (int i = 0; i < CHUNK_WIDTH; i++)
+ {
+ for (int j = 0; j < CHUNK_WIDTH; j++)
+ {
+ for (int k = 0; k < CHUNK_WIDTH; k++)
+ {
+ Vec3 chunk_origin;
+ Chunk_origin(chunk, chunk_origin);
+
+ Vec3 cell_origin = {
+ chunk_origin[0] + i,
+ chunk_origin[1] + j,
+ chunk_origin[2] + k
+ };
+
+ Vec3 cell_corners[8];
+ Cube_corners(cell_origin, 1, cell_corners);
+
+ chunk->vertex_count += MC_polygonize(cell_corners, f, isolevel,
+ &chunk->vertices[chunk->vertex_count]);
+ }
+ }
+ }
+ glBindBuffer(GL_ARRAY_BUFFER, chunk->vbo);
+ glBufferData(GL_ARRAY_BUFFER, sizeof(Vec3) * chunk->vertex_count,
+ chunk->vertices, GL_STATIC_DRAW);
}
-void Chunk_outline(const Chunk* chunk, float corners[24],
- unsigned int offset, unsigned int indices[24])
+void Chunk_draw(const Chunk *chunk)
{
- Cube_corners(chunk->origin, CHUNK_WIDTH, corners);
- Cube_outlineIndices(offset, indices);
+ glBindVertexArray(chunk->vao);
+ glDrawArrays(GL_TRIANGLES, 0, chunk->vertex_count);
}
diff --git a/src/chunk_manager.c b/src/chunk_manager.c
@@ -1,84 +1,144 @@
-
#include "chunk_manager.h"
-#include <stdlib.h>
#include <math.h>
+#include <stdlib.h>
-int ChunkManager_offsets(int radius, int* offsets)
+static void ChunkManager_setChunkCount(ChunkManager *cm)
{
- int count = 0;
- for (int x = -radius; x <= radius; x++)
+ cm->chunk_count = 0;
+ for (int x = -cm->radius; x <= cm->radius; x++)
{
- for (int y = -radius; y <= radius; y++)
+ for (int y = -cm->radius; y <= cm->radius; y++)
{
- for (int z = -radius; z <= radius; z++)
+ for (int z = -cm->radius; z <= cm->radius; z++)
{
- if (x * x + y * y + z * z <= radius * radius)
- {
- if (offsets != NULL)
- {
- offsets[count] = x;
- offsets[count + 1] = y;
- offsets[count + 2] = z;
- }
- count += 3;
- }
+ cm->chunk_count += 1;
}
}
}
- return count;
}
-void ChunkManager_worldToChunk(const float src[3], int dst[3])
+static void ChunkManager_createOffsets(ChunkManager *cm)
{
- dst[0] = (int)floor(src[0] / CHUNK_WIDTH);
- dst[1] = (int)floor(src[1] / CHUNK_WIDTH);
- dst[2] = (int)floor(src[2] / CHUNK_WIDTH);
+ cm->offsets = malloc(sizeof *cm->offsets * cm->chunk_count);
+ for (int i = 0, x = -cm->radius; x <= cm->radius; x++)
+ {
+ for (int y = -cm->radius; y <= cm->radius; y++)
+ {
+ for (int z = -cm->radius; z <= cm->radius; z++, i++)
+ {
+ cm->offsets[i][0] = x;
+ cm->offsets[i][1] = y;
+ cm->offsets[i][2] = z;
+ }
+ }
+ }
}
-void ChunkManager_recenter(ChunkManager* chunk_manager, const int origin[3])
+static void ChunkManager_createChunks(ChunkManager *cm)
{
- chunk_manager->origin[0] = origin[0];
- chunk_manager->origin[1] = origin[1];
- chunk_manager->origin[2] = origin[2];
- for (int i = 0; i < chunk_manager->chunk_count; i++)
+ cm->chunks = malloc(sizeof *cm->chunks * cm->chunk_count);
+ for (int i = 0; i < cm->chunk_count; i++)
{
- chunk_manager->chunks[i] = Chunk_create(
- origin[0] + chunk_manager->offsets[i * 3],
- origin[1] + chunk_manager->offsets[i * 3 + 1],
- origin[2] + chunk_manager->offsets[i * 3 + 2]
- );
+ Chunk_init(&cm->chunks[i], cm->offsets[i]);
+ Chunk_meshify(&cm->chunks[i], cm->f, cm->isolevel);
}
}
-ChunkManager ChunkManager_create(int radius, float player[3])
+static void ChunkManager_updateChunks(ChunkManager *cm)
{
- ChunkManager chunk_manager;
+ // is_new indicates whether an offset is new
+ bool *is_new = malloc(sizeof *is_new * cm->chunk_count);
+ // is_old indicates whether a chunk is old
+ bool *is_old = malloc(sizeof *is_old * cm->chunk_count);
+ for (int i = 0; i < cm->chunk_count; i++)
+ {
+ is_new[i] = true;
+ is_old[i] = true;
+ }
- chunk_manager.radius = radius;
-
- int offset_count = ChunkManager_offsets(radius, NULL);
- chunk_manager.offsets = (int*)malloc(offset_count * sizeof(int));
- ChunkManager_offsets(radius, chunk_manager.offsets);
-
- chunk_manager.chunk_count = offset_count / 3;
- chunk_manager.chunks = (Chunk*)malloc(chunk_manager.chunk_count
- * sizeof(Chunk));
+ // Determine which offsets are new and which chunks are old
+ IVec3 *new_ids = malloc(sizeof *new_ids * cm->chunk_count);
+ for (int i = 0; i < cm->chunk_count; i++)
+ {
+ new_ids[i][0] = cm->origin[0] + cm->offsets[i][0];
+ new_ids[i][1] = cm->origin[1] + cm->offsets[i][1];
+ new_ids[i][2] = cm->origin[2] + cm->offsets[i][2];
+ for (int j = 0; j < cm->chunk_count; j++)
+ {
+ if (IVec3_equal(new_ids[i], cm->chunks[j].id) != 0)
+ {
+ is_new[i] = false;
+ is_old[j] = false;
+ break;
+ }
+ }
+ }
+
+ // Set old chunks to have new ids
+ for (int i = 0; i < cm->chunk_count; i++)
+ {
+ if (is_new[i])
+ {
+ for (int j = 0; j < cm->chunk_count; j++)
+ {
+ if (is_old[j])
+ {
+ cm->chunks[j].id[0] = new_ids[i][0];
+ cm->chunks[j].id[1] = new_ids[i][1];
+ cm->chunks[j].id[2] = new_ids[i][2];
+ Chunk_meshify(&cm->chunks[j], cm->f, cm->isolevel);
+ is_new[i] = false;
+ is_old[j] = false;
+ break;
+ }
+ }
+ }
+ }
+}
+
+static void ChunkManager_worldToChunk(const Vec3 src, IVec3 dst)
+{
+ dst[0] = (int)floorf(src[0] / CHUNK_WIDTH);
+ dst[1] = (int)floorf(src[1] / CHUNK_WIDTH);
+ dst[2] = (int)floorf(src[2] / CHUNK_WIDTH);
+}
+
+ChunkManager ChunkManager_create(const Vec3 target, int radius, SDF f,
+ float isolevel)
+{
+ ChunkManager cm;
+
+ ChunkManager_worldToChunk(target, cm.origin);
+ cm.radius = radius;
+
+ cm.f = f;
+ cm.isolevel = isolevel;
- ChunkManager_worldToChunk(player, chunk_manager.origin);
- ChunkManager_recenter(&chunk_manager, chunk_manager.origin);
+ ChunkManager_setChunkCount(&cm);
+ ChunkManager_createOffsets(&cm);
+ ChunkManager_createChunks(&cm);
- return chunk_manager;
+ return cm;
+}
+
+void ChunkManager_recenter(ChunkManager *cm, const Vec3 target)
+{
+ IVec3 new_origin;
+ ChunkManager_worldToChunk(target, new_origin);
+ if (!IVec3_equal(new_origin, cm->origin))
+ {
+ cm->origin[0] = new_origin[0];
+ cm->origin[1] = new_origin[1];
+ cm->origin[2] = new_origin[2];
+ ChunkManager_updateChunks(cm);
+ }
}
-void ChunkManager_update(ChunkManager* chunk_manager, float player[3])
+void ChunkManager_drawChunks(const ChunkManager *cm)
{
- int new_origin[3];
- ChunkManager_worldToChunk(player, new_origin);
- if (new_origin[0] != chunk_manager->origin[0]
- || new_origin[1] != chunk_manager->origin[1]
- || new_origin[2] != chunk_manager->origin[2])
+ for (int i = 0; i < cm->chunk_count; i++)
{
- ChunkManager_recenter(chunk_manager, new_origin);
+ Chunk_draw(&cm->chunks[i]);
}
}
diff --git a/src/main.c b/src/main.c
@@ -1,16 +1,12 @@
#include "camera.h"
-#include "chunk.h"
#include "chunk_manager.h"
-#include "glh/buffer.h"
#include "glh/shader.h"
#include "glad/glad.h"
#include <cglm/cglm.h>
-
#include <SDL2/SDL.h>
#include <SDL2/SDL_opengl.h>
-#include <stdbool.h>
#include <stdio.h>
const int WIDTH = 512, HEIGHT = 512;
@@ -31,6 +27,11 @@ void Camera_update(Camera* camera)
Camera_updateMatrix(camera);
}
+float sphereSDF(const float p[3])
+{
+ return sqrtf(p[0] * p[0] + p[1] * p[1] + p[2] * p[2]) - 25.0f;
+}
+
int main(int argc, char** argv)
{
if (SDL_Init(SDL_INIT_VIDEO) < 0)
@@ -47,6 +48,7 @@ int main(int argc, char** argv)
exit(EXIT_FAILURE);
}
+
SDL_GL_SetAttribute(SDL_GL_CONTEXT_PROFILE_MASK,
SDL_GL_CONTEXT_PROFILE_CORE);
SDL_GL_SetAttribute(SDL_GL_CONTEXT_MAJOR_VERSION, 3);
@@ -62,7 +64,7 @@ int main(int argc, char** argv)
SDL_ShowCursor(SDL_DISABLE);
SDL_SetRelativeMouseMode(SDL_TRUE);
- Camera camera = Camera_create(0, 0, 3, -90, 0);
+ Camera camera = Camera_create(0, 0, -3, 0, 0);
gladLoadGLLoader(SDL_GL_GetProcAddress);
@@ -72,23 +74,11 @@ int main(int argc, char** argv)
glClearColor(0.4f, 0.4f, 0.6f, 1.0f);
- ChunkManager chunk_manager = ChunkManager_create(2, camera.position);
+ glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
- float vertices[24 * chunk_manager.chunk_count];
- unsigned int indices[24 * chunk_manager.chunk_count];
- for (int i = 0; i < chunk_manager.chunk_count; i++)
- {
- Chunk_outline(&chunk_manager.chunks[i], &vertices[i * 24], i * 8,
- &indices[i * 24]);
- }
- GLuint vertex_buffer = createVertexBuffer(24 * chunk_manager.chunk_count
- * sizeof(float), vertices, GL_DYNAMIC_DRAW);
- GLuint index_buffer = createIndexBuffer(24 * chunk_manager.chunk_count
- * sizeof(unsigned int), indices, GL_STATIC_DRAW);
-
- int vertex[] = { 3 };
- GLuint vertex_array = createVertexArray(vertex_buffer, index_buffer, 1,
- vertex);
+ sphereSDF(camera.position);
+ ChunkManager chunk_manager = ChunkManager_create(camera.position, 1,
+ sphereSDF, 0.0f);
Shader shader = Shader_create("shaders/basic.vs", "shaders/basic.fs");
glUseProgram(shader.program);
@@ -123,19 +113,8 @@ int main(int argc, char** argv)
Camera_update(&camera);
glUniformMatrix4fv(cam_loc, 1, GL_FALSE, camera.matrix[0]);
- ChunkManager_update(&chunk_manager, camera.position);
- for (int i = 0; i < chunk_manager.chunk_count; i++)
- {
- Chunk_outline(&chunk_manager.chunks[i], &vertices[i * 24], i * 8,
- &indices[i * 24]);
- }
- glBindBuffer(GL_ARRAY_BUFFER, vertex_buffer);
- glBufferSubData(GL_ARRAY_BUFFER, 0, 24 * chunk_manager.chunk_count
- * sizeof(float), vertices);
-
- glBindVertexArray(vertex_array);
- glDrawElements(GL_LINES, 24 * chunk_manager.chunk_count,
- GL_UNSIGNED_INT, 0);
+ ChunkManager_recenter(&chunk_manager, camera.position);
+ ChunkManager_drawChunks(&chunk_manager);
SDL_GL_SwapWindow(window);
}
diff --git a/src/marching_cubes.c b/src/marching_cubes.c
@@ -0,0 +1,410 @@
+#include "marching_cubes.h"
+
+#include <math.h>
+
+const int EDGE_TABLE[256] = {
+ 0x0 , 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c, 0x80c, 0x905,
+ 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00, 0x190, 0x99 , 0x393, 0x29a,
+ 0x596, 0x49f, 0x795, 0x69c, 0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93,
+ 0xf99, 0xe90, 0x230, 0x339, 0x33 , 0x13a, 0x636, 0x73f, 0x435, 0x53c,
+ 0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30, 0x3a0, 0x2a9,
+ 0x1a3, 0xaa , 0x7a6, 0x6af, 0x5a5, 0x4ac, 0xbac, 0xaa5, 0x9af, 0x8a6,
+ 0xfaa, 0xea3, 0xda9, 0xca0, 0x460, 0x569, 0x663, 0x76a, 0x66 , 0x16f,
+ 0x265, 0x36c, 0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
+ 0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff , 0x3f5, 0x2fc, 0xdfc, 0xcf5,
+ 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0, 0x650, 0x759, 0x453, 0x55a,
+ 0x256, 0x35f, 0x55 , 0x15c, 0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53,
+ 0x859, 0x950, 0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc ,
+ 0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0, 0x8c0, 0x9c9,
+ 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc, 0xcc , 0x1c5, 0x2cf, 0x3c6,
+ 0x4ca, 0x5c3, 0x6c9, 0x7c0, 0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f,
+ 0xf55, 0xe5c, 0x15c, 0x55 , 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
+ 0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc, 0x2fc, 0x3f5,
+ 0xff , 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0, 0xb60, 0xa69, 0x963, 0x86a,
+ 0xf66, 0xe6f, 0xd65, 0xc6c, 0x36c, 0x265, 0x16f, 0x66 , 0x76a, 0x663,
+ 0x569, 0x460, 0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,
+ 0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa , 0x1a3, 0x2a9, 0x3a0, 0xd30, 0xc39,
+ 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c, 0x53c, 0x435, 0x73f, 0x636,
+ 0x13a, 0x33 , 0x339, 0x230, 0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f,
+ 0x895, 0x99c, 0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99 , 0x190,
+ 0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c, 0x70c, 0x605,
+ 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0
+};
+
+const int TRI_TABLE[256][16] = {
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
+ { 2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1},
+ { 8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ {11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1},
+ { 3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1},
+ { 4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1},
+ { 4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
+ { 5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1},
+ { 2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1},
+ { 9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
+ { 2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1},
+ {10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1},
+ { 5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1},
+ { 5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1},
+ {10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1},
+ { 8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1},
+ { 2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1},
+ { 7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1},
+ { 2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1},
+ {11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1},
+ { 5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1},
+ {11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1},
+ {11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ {10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1},
+ { 5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1},
+ { 2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ {11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
+ { 5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1},
+ { 6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1},
+ { 3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1},
+ { 6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1},
+ { 5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
+ {10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1},
+ { 6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1},
+ { 8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1},
+ { 7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1},
+ { 3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
+ { 5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1},
+ { 0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1},
+ { 9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1},
+ { 8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1},
+ { 5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1},
+ { 0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1},
+ { 6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1},
+ {10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1},
+ {10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1},
+ { 8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1},
+ { 1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1},
+ { 0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1},
+ {10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1},
+ { 3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1},
+ { 6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1},
+ { 9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1},
+ { 8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1},
+ { 3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1},
+ { 6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1},
+ {10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1},
+ {10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1},
+ { 2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1},
+ { 7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1},
+ { 7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1},
+ { 2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1},
+ { 1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1},
+ {11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1},
+ { 8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1},
+ { 0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1},
+ { 7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
+ {10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
+ { 2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
+ { 6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1},
+ { 7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1},
+ { 2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1},
+ {10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1},
+ {10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1},
+ { 0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1},
+ { 7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1},
+ { 6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1},
+ { 8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1},
+ { 6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1},
+ { 4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1},
+ {10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1},
+ { 8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1},
+ { 1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1},
+ { 8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1},
+ {10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1},
+ {10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
+ { 5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
+ {11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1},
+ { 9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
+ { 6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1},
+ { 7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1},
+ { 3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1},
+ { 7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1},
+ { 3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1},
+ { 6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1},
+ { 9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1},
+ { 1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1},
+ { 4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1},
+ { 7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1},
+ { 6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1},
+ { 0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1},
+ { 6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1},
+ { 0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1},
+ {11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1},
+ { 6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1},
+ { 5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1},
+ { 9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1},
+ { 1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1},
+ {10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1},
+ { 0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ {10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ {11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ {11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1},
+ { 5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1},
+ {10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1},
+ {11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1},
+ { 9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1},
+ { 7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1},
+ { 2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1},
+ { 8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1},
+ { 9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1},
+ { 9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1},
+ { 1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1},
+ { 5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1},
+ { 0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1},
+ {10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1},
+ { 2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1},
+ { 0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1},
+ { 0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1},
+ { 9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1},
+ { 5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1},
+ { 5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1},
+ { 8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1},
+ { 9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1},
+ { 1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1},
+ { 3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1},
+ { 4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1},
+ { 9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1},
+ {11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1},
+ {11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1},
+ { 2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1},
+ { 9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1},
+ { 3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1},
+ { 1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1},
+ { 4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1},
+ { 0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1},
+ { 9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1},
+ { 1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ { 0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
+};
+
+int MC_index(const Vec3 corners[8], SDF f, float isolevel)
+{
+ int mc_index = 0;
+ if (f(corners[0]) < isolevel) mc_index |= 1;
+ if (f(corners[1]) < isolevel) mc_index |= 2;
+ if (f(corners[2]) < isolevel) mc_index |= 4;
+ if (f(corners[3]) < isolevel) mc_index |= 8;
+ if (f(corners[4]) < isolevel) mc_index |= 16;
+ if (f(corners[5]) < isolevel) mc_index |= 32;
+ if (f(corners[6]) < isolevel) mc_index |= 64;
+ if (f(corners[7]) < isolevel) mc_index |= 128;
+ return mc_index;
+}
+
+void MC_interpVertex(const Vec3 a, const Vec3 b, SDF f, float isolevel,
+ Vec3 dst)
+{
+ float fa = f(a);
+ float fb = f(b);
+ if (fabsf(isolevel - fa) < 0.0001f || fabsf(fa - fb) < 0.0001f)
+ {
+ dst[0] = a[0];
+ dst[1] = a[1];
+ dst[2] = a[2];
+ return;
+ }
+ if (fabsf(isolevel - fb) < 0.0001f)
+ {
+ dst[0] = b[0];
+ dst[1] = b[1];
+ dst[2] = b[2];
+ return;
+ }
+ float t = (isolevel - fa) / (fb - fa);
+ dst[0] = a[0] + t * (b[0] - a[0]);
+ dst[1] = a[1] + t * (b[1] - a[1]);
+ dst[2] = a[2] + t * (b[2] - a[2]);
+ return;
+}
+
+void MC_vertices(const Vec3 corners[8], SDF f, float isolevel, int mc_index,
+ Vec3 vertices[12])
+{
+ if (EDGE_TABLE[mc_index] & 1)
+ {
+ MC_interpVertex(corners[0], corners[1], f, isolevel, vertices[0]);
+ }
+ if (EDGE_TABLE[mc_index] & 2)
+ {
+ MC_interpVertex(corners[1], corners[2], f, isolevel, vertices[1]);
+ }
+ if (EDGE_TABLE[mc_index] & 4)
+ {
+ MC_interpVertex(corners[2], corners[3], f, isolevel, vertices[2]);
+ }
+ if (EDGE_TABLE[mc_index] & 8)
+ {
+ MC_interpVertex(corners[3], corners[0], f, isolevel, vertices[3]);
+ }
+ if (EDGE_TABLE[mc_index] & 16)
+ {
+ MC_interpVertex(corners[4], corners[5], f, isolevel, vertices[4]);
+ }
+ if (EDGE_TABLE[mc_index] & 32)
+ {
+ MC_interpVertex(corners[5], corners[6], f, isolevel, vertices[5]);
+ }
+ if (EDGE_TABLE[mc_index] & 64)
+ {
+ MC_interpVertex(corners[6], corners[7], f, isolevel, vertices[6]);
+ }
+ if (EDGE_TABLE[mc_index] & 128)
+ {
+ MC_interpVertex(corners[7], corners[4], f, isolevel, vertices[7]);
+ }
+ if (EDGE_TABLE[mc_index] & 256)
+ {
+ MC_interpVertex(corners[0], corners[4], f, isolevel, vertices[8]);
+ }
+ if (EDGE_TABLE[mc_index] & 512)
+ {
+ MC_interpVertex(corners[1], corners[5], f, isolevel, vertices[9]);
+ }
+ if (EDGE_TABLE[mc_index] & 1024)
+ {
+ MC_interpVertex(corners[2], corners[6], f, isolevel, vertices[10]);
+ }
+ if (EDGE_TABLE[mc_index] & 2048)
+ {
+ MC_interpVertex(corners[3], corners[7], f, isolevel, vertices[11]);
+ }
+}
+
+int MC_triangles(const Vec3 vertices[12], SDF f, float isolevel, int mc_index,
+ Vec3* triangles)
+{
+ int vertex_count = 0;
+ for (int i = 0; TRI_TABLE[mc_index][i] != -1; i++)
+ {
+ triangles[i][0] = vertices[TRI_TABLE[mc_index][i]][0];
+ triangles[i][1] = vertices[TRI_TABLE[mc_index][i]][1];
+ triangles[i][2] = vertices[TRI_TABLE[mc_index][i]][2];
+ vertex_count++;
+ }
+ return vertex_count;
+}
+
+int MC_polygonize(const Vec3 corners[8], SDF f, float isolevel,
+ Vec3 triangles[15])
+{
+ int mc_index = MC_index(corners, f, isolevel);
+
+ Vec3 vertices[12];
+ MC_vertices(corners, f, isolevel, mc_index, vertices);
+
+ return MC_triangles(vertices, f, isolevel, mc_index,
+ triangles);
+}
diff --git a/src/vec.c b/src/vec.c
@@ -0,0 +1,6 @@
+#include "vec.h"
+
+bool IVec3_equal(const IVec3 a, const IVec3 b)
+{
+ return (a[0] == b[0]) & (a[1] == b[1]) & (a[2] == b[2]);
+}
