/* marching_cubes.h - v0.6 - public domain - Pavol Klacansky Marching cubes algorithm implementation using lookup table with no holes. At least one .c file needs to define MARCHING_CUBES_IMPLEMENTATION before including this header. References: - Marching cubes: A high resolution 3D surface construction algorithm, William E. Lorensen and Harvey E. Cline - A modified look-up table for implicit disambiguation of Marching Cubes, Claudio Montani, Riccardo Scateni, and Roberto Scopigno Example C code that generates isosurface for a single cell and saves the mesh into mesh.obj file: ``` #include #include #include #include #define MARCHING_CUBES_DATA_TYPE uint8_t #define MARCHING_CUBES_IMPLEMENTATION #include "marching_cubes.h" int main(void) { uint8_t volume[] = {10, 5, 0, 3, 1, 8, 2, 4}; int64_t size_x = 2; int64_t size_y = 2; int64_t size_z = 2; double spacing_x = 1.0; double spacing_y = 2.0; double spacing_z = 4.0; double threshold = 4.0; // allocate index_map int32_t *index_map = malloc(3*size_x*size_y*size_z*sizeof *index_map); assert(index_map != NULL); // query number of positions and indices int64_t vertex_count = 0; int64_t index_count = 0; marching_cubes_compute(size_x, size_y, size_z, volume, spacing_x, spacing_y, spacing_z, index_map, threshold, &vertex_count, NULL, &index_count, NULL); // allocate memory for vertices and indices (can be pinned memory buffer for Vulkan rendering) float *vertices = malloc(3*vertex_count*sizeof *vertices); // 3 times because of x, y, z assert(vertices != NULL); int32_t *indices = malloc(index_count*sizeof *indices); assert(indices != NULL); marching_cubes_compute(size_x, size_y, size_z, volume, spacing_x, spacing_y, spacing_z, index_map, threshold, &vertex_count, vertices, &index_count, indices); free(index_map); // write as .obj file FILE *fp = fopen("mesh.obj", "wb"); assert(fp != NULL); for (int64_t i = 0; i < vertex_count; i += 1) fprintf(fp, "v %f %f %f\n", vertices[3*i], vertices[3*i + 1], vertices[3*i + 2]); for (int64_t i = 0; i < index_count; i += 3) fprintf(fp, "f %"PRIi32" %"PRIi32" %"PRIi32"\n", indices[i] + 1, indices[i + 1] + 1, indices[i + 2] + 1); // .obj indexes from 1 instead of 0 fclose(fp); free(vertices); free(indices); return EXIT_SUCCESS; } ``` Versions: - 0.6 - remove slab processing, require macro specifing data type, new spacing argument - 0.5 - MARCHING_CUBES_IMPLEMENTATION (like stb header library) - 0.4 - rename the file, require MARCHING_CUBES_HEADER when using as a header file (non-unity build), rename functions - 0.3 - remove the memory allocation from inside the extraction routine - 0.2 - support MSVC (move from C11 to C99); expand example with mesh saving to .obj - 0.1 - initial release with triangle mesh extraction */ #if !defined(MARCHING_CUBES_H) #define MARCHING_CUBES_H #include void marching_cubes_compute(int64_t size_x, int64_t size_y, int64_t size_z, MARCHING_CUBES_DATA_TYPE const *volume, double spacing_x, double spacing_y, double spacing_z, int32_t *index_map, double threshold, int64_t *out_vertex_count, float *out_vertices, int64_t *out_index_count, int32_t *out_indices); #if defined(MARCHING_CUBES_IMPLEMENTATION) #include #include static int8_t const marching_cubes_edges[256][16] = { { -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 0, 8, 3, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 1, 9, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 8, 1, 9, 8, 3, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 2, 10, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 0, 8, 3, 1, 2, 10, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 9, 2, 10, 9, 0, 2, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 3, 2, 10, 3, 10, 8, 8, 10, 9, -1, 0, 0, 0, 0, 0, 0,}, { 2, 3, 11, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 11, 0, 8, 11, 2, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 1, 9, 0, 2, 3, 11, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 2, 1, 9, 2, 9, 11, 11, 9, 8, -1, 0, 0, 0, 0, 0, 0,}, { 3, 10, 1, 3, 11, 10, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 1, 0, 8, 1, 8, 10, 10, 8, 11, -1, 0, 0, 0, 0, 0, 0,}, { 0, 3, 11, 0, 11, 9, 9, 11, 10, -1, 0, 0, 0, 0, 0, 0,}, { 11, 10, 9, 11, 9, 8, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 4, 7, 8, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 4, 3, 0, 4, 7, 3, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 4, 7, 8, 9, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 9, 4, 7, 9, 7, 1, 1, 7, 3, -1, 0, 0, 0, 0, 0, 0,}, { 4, 7, 8, 1, 2, 10, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 4, 3, 0, 4, 7, 3, 2, 10, 1, -1, 0, 0, 0, 0, 0, 0,}, { 2, 9, 0, 2, 10, 9, 4, 7, 8, -1, 0, 0, 0, 0, 0, 0,}, { 3, 2, 7, 7, 9, 4, 7, 2, 9, 9, 2, 10, -1, 0, 0, 0,}, { 8, 4, 7, 3, 11, 2, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 7, 11, 2, 7, 2, 4, 4, 2, 0, -1, 0, 0, 0, 0, 0, 0,}, { 2, 3, 11, 1, 9, 0, 8, 4, 7, -1, 0, 0, 0, 0, 0, 0,}, { 2, 1, 9, 2, 9, 4, 2, 4, 11, 11, 4, 7, -1, 0, 0, 0,}, { 10, 3, 11, 10, 1, 3, 8, 4, 7, -1, 0, 0, 0, 0, 0, 0,}, { 4, 7, 0, 0, 10, 1, 7, 10, 0, 7, 11, 10, -1, 0, 0, 0,}, { 8, 4, 7, 0, 3, 11, 0, 11, 9, 9, 11, 10, -1, 0, 0, 0,}, { 7, 9, 4, 7, 11, 9, 9, 11, 10, -1, 0, 0, 0, 0, 0, 0,}, { 4, 9, 5, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 8, 3, 0, 4, 9, 5, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 0, 5, 4, 0, 1, 5, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 4, 8, 3, 4, 3, 5, 5, 3, 1, -1, 0, 0, 0, 0, 0, 0,}, { 1, 2, 10, 9, 5, 4, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 4, 9, 5, 8, 3, 0, 1, 2, 10, -1, 0, 0, 0, 0, 0, 0,}, { 10, 5, 4, 10, 4, 2, 2, 4, 0, -1, 0, 0, 0, 0, 0, 0,}, { 4, 8, 3, 4, 3, 2, 4, 2, 5, 5, 2, 10, -1, 0, 0, 0,}, { 2, 3, 11, 5, 4, 9, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 11, 0, 8, 11, 2, 0, 9, 5, 4, -1, 0, 0, 0, 0, 0, 0,}, { 5, 0, 1, 5, 4, 0, 3, 11, 2, -1, 0, 0, 0, 0, 0, 0,}, { 11, 2, 8, 8, 5, 4, 2, 5, 8, 2, 1, 5, -1, 0, 0, 0,}, { 3, 10, 1, 3, 11, 10, 5, 4, 9, -1, 0, 0, 0, 0, 0, 0,}, { 9, 5, 4, 1, 0, 8, 1, 8, 10, 10, 8, 11, -1, 0, 0, 0,}, { 10, 5, 11, 11, 0, 3, 11, 5, 0, 0, 5, 4, -1, 0, 0, 0,}, { 4, 10, 5, 4, 8, 10, 10, 8, 11, -1, 0, 0, 0, 0, 0, 0,}, { 7, 9, 5, 7, 8, 9, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 0, 9, 5, 0, 5, 3, 3, 5, 7, -1, 0, 0, 0, 0, 0, 0,}, { 8, 0, 1, 8, 1, 7, 7, 1, 5, -1, 0, 0, 0, 0, 0, 0,}, { 3, 1, 5, 3, 5, 7, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 7, 9, 5, 7, 8, 9, 1, 2, 10, -1, 0, 0, 0, 0, 0, 0,}, { 1, 2, 10, 0, 9, 5, 0, 5, 3, 3, 5, 7, -1, 0, 0, 0,}, { 7, 8, 5, 5, 2, 10, 8, 2, 5, 8, 0, 2, -1, 0, 0, 0,}, { 10, 3, 2, 10, 5, 3, 3, 5, 7, -1, 0, 0, 0, 0, 0, 0,}, { 9, 7, 8, 9, 5, 7, 11, 2, 3, -1, 0, 0, 0, 0, 0, 0,}, { 0, 9, 2, 2, 7, 11, 2, 9, 7, 7, 9, 5, -1, 0, 0, 0,}, { 3, 11, 2, 8, 0, 1, 8, 1, 7, 7, 1, 5, -1, 0, 0, 0,}, { 2, 7, 11, 2, 1, 7, 7, 1, 5, -1, 0, 0, 0, 0, 0, 0,}, { 11, 1, 3, 11, 10, 1, 7, 8, 9, 7, 9, 5, -1, 0, 0, 0,}, { 11, 10, 1, 11, 1, 7, 7, 1, 0, 7, 0, 9, 7, 9, 5, -1,}, { 5, 7, 8, 5, 8, 10, 10, 8, 0, 10, 0, 3, 10, 3, 11, -1,}, { 11, 10, 5, 11, 5, 7, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 10, 6, 5, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 0, 8, 3, 10, 6, 5, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 9, 0, 1, 5, 10, 6, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 8, 1, 9, 8, 3, 1, 10, 6, 5, -1, 0, 0, 0, 0, 0, 0,}, { 6, 1, 2, 6, 5, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 6, 1, 2, 6, 5, 1, 0, 8, 3, -1, 0, 0, 0, 0, 0, 0,}, { 5, 9, 0, 5, 0, 6, 6, 0, 2, -1, 0, 0, 0, 0, 0, 0,}, { 6, 5, 2, 2, 8, 3, 5, 8, 2, 5, 9, 8, -1, 0, 0, 0,}, { 2, 3, 11, 10, 6, 5, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 0, 11, 2, 0, 8, 11, 6, 5, 10, -1, 0, 0, 0, 0, 0, 0,}, { 0, 1, 9, 3, 11, 2, 10, 6, 5, -1, 0, 0, 0, 0, 0, 0,}, { 10, 6, 5, 2, 1, 9, 2, 9, 11, 11, 9, 8, -1, 0, 0, 0,}, { 11, 6, 5, 11, 5, 3, 3, 5, 1, -1, 0, 0, 0, 0, 0, 0,}, { 11, 6, 8, 8, 1, 0, 8, 6, 1, 1, 6, 5, -1, 0, 0, 0,}, { 0, 3, 11, 0, 11, 6, 0, 6, 9, 9, 6, 5, -1, 0, 0, 0,}, { 5, 11, 6, 5, 9, 11, 11, 9, 8, -1, 0, 0, 0, 0, 0, 0,}, { 7, 8, 4, 6, 5, 10, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 3, 4, 7, 3, 0, 4, 5, 10, 6, -1, 0, 0, 0, 0, 0, 0,}, { 6, 5, 10, 7, 8, 4, 9, 0, 1, -1, 0, 0, 0, 0, 0, 0,}, { 5, 10, 6, 9, 4, 7, 9, 7, 1, 1, 7, 3, -1, 0, 0, 0,}, { 1, 6, 5, 1, 2, 6, 7, 8, 4, -1, 0, 0, 0, 0, 0, 0,}, { 7, 0, 4, 7, 3, 0, 6, 5, 1, 6, 1, 2, -1, 0, 0, 0,}, { 4, 7, 8, 5, 9, 0, 5, 0, 6, 6, 0, 2, -1, 0, 0, 0,}, { 2, 6, 5, 2, 5, 3, 3, 5, 9, 3, 9, 4, 3, 4, 7, -1,}, { 4, 7, 8, 5, 10, 6, 11, 2, 3, -1, 0, 0, 0, 0, 0, 0,}, { 6, 5, 10, 7, 11, 2, 7, 2, 4, 4, 2, 0, -1, 0, 0, 0,}, { 4, 7, 8, 9, 0, 1, 6, 5, 10, 3, 11, 2, -1, 0, 0, 0,}, { 6, 5, 10, 11, 4, 7, 11, 2, 4, 4, 2, 9, 9, 2, 1, -1,}, { 7, 8, 4, 11, 6, 5, 11, 5, 3, 3, 5, 1, -1, 0, 0, 0,}, { 0, 4, 7, 0, 7, 1, 1, 7, 11, 1, 11, 6, 1, 6, 5, -1,}, { 4, 7, 8, 9, 6, 5, 9, 0, 6, 6, 0, 11, 11, 0, 3, -1,}, { 7, 11, 4, 11, 9, 4, 11, 5, 9, 11, 6, 5, -1, 0, 0, 0,}, { 10, 4, 9, 10, 6, 4, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 10, 4, 9, 10, 6, 4, 8, 3, 0, -1, 0, 0, 0, 0, 0, 0,}, { 1, 10, 6, 1, 6, 0, 0, 6, 4, -1, 0, 0, 0, 0, 0, 0,}, { 4, 8, 6, 6, 1, 10, 6, 8, 1, 1, 8, 3, -1, 0, 0, 0,}, { 9, 1, 2, 9, 2, 4, 4, 2, 6, -1, 0, 0, 0, 0, 0, 0,}, { 0, 8, 3, 9, 1, 2, 9, 2, 4, 4, 2, 6, -1, 0, 0, 0,}, { 0, 2, 6, 0, 6, 4, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 3, 4, 8, 3, 2, 4, 4, 2, 6, -1, 0, 0, 0, 0, 0, 0,}, { 4, 10, 6, 4, 9, 10, 2, 3, 11, -1, 0, 0, 0, 0, 0, 0,}, { 8, 2, 0, 8, 11, 2, 4, 9, 10, 4, 10, 6, -1, 0, 0, 0,}, { 2, 3, 11, 1, 10, 6, 1, 6, 0, 0, 6, 4, -1, 0, 0, 0,}, { 8, 11, 2, 8, 2, 4, 4, 2, 1, 4, 1, 10, 4, 10, 6, -1,}, { 3, 11, 1, 1, 4, 9, 11, 4, 1, 11, 6, 4, -1, 0, 0, 0,}, { 6, 4, 9, 6, 9, 11, 11, 9, 1, 11, 1, 0, 11, 0, 8, -1,}, { 11, 0, 3, 11, 6, 0, 0, 6, 4, -1, 0, 0, 0, 0, 0, 0,}, { 8, 11, 6, 8, 6, 4, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 6, 7, 8, 6, 8, 10, 10, 8, 9, -1, 0, 0, 0, 0, 0, 0,}, { 3, 0, 7, 7, 10, 6, 0, 10, 7, 0, 9, 10, -1, 0, 0, 0,}, { 1, 10, 6, 1, 6, 7, 1, 7, 0, 0, 7, 8, -1, 0, 0, 0,}, { 6, 1, 10, 6, 7, 1, 1, 7, 3, -1, 0, 0, 0, 0, 0, 0,}, { 9, 1, 8, 8, 6, 7, 8, 1, 6, 6, 1, 2, -1, 0, 0, 0,}, { 7, 3, 0, 7, 0, 6, 6, 0, 9, 6, 9, 1, 6, 1, 2, -1,}, { 8, 6, 7, 8, 0, 6, 6, 0, 2, -1, 0, 0, 0, 0, 0, 0,}, { 2, 6, 7, 2, 7, 3, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 11, 2, 3, 6, 7, 8, 6, 8, 10, 10, 8, 9, -1, 0, 0, 0,}, { 9, 10, 6, 9, 6, 0, 0, 6, 7, 0, 7, 11, 0, 11, 2, -1,}, { 3, 11, 2, 0, 7, 8, 0, 1, 7, 7, 1, 6, 6, 1, 10, -1,}, { 6, 7, 10, 7, 1, 10, 7, 2, 1, 7, 11, 2, -1, 0, 0, 0,}, { 1, 3, 11, 1, 11, 9, 9, 11, 6, 9, 6, 7, 9, 7, 8, -1,}, { 6, 7, 11, 9, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 8, 0, 7, 0, 6, 7, 0, 11, 6, 0, 3, 11, -1, 0, 0, 0,}, { 6, 7, 11, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 6, 11, 7, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 3, 0, 8, 11, 7, 6, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 6, 11, 7, 9, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 1, 8, 3, 1, 9, 8, 7, 6, 11, -1, 0, 0, 0, 0, 0, 0,}, { 11, 7, 6, 2, 10, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 1, 2, 10, 0, 8, 3, 11, 7, 6, -1, 0, 0, 0, 0, 0, 0,}, { 9, 2, 10, 9, 0, 2, 11, 7, 6, -1, 0, 0, 0, 0, 0, 0,}, { 11, 7, 6, 3, 2, 10, 3, 10, 8, 8, 10, 9, -1, 0, 0, 0,}, { 2, 7, 6, 2, 3, 7, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 8, 7, 6, 8, 6, 0, 0, 6, 2, -1, 0, 0, 0, 0, 0, 0,}, { 7, 2, 3, 7, 6, 2, 1, 9, 0, -1, 0, 0, 0, 0, 0, 0,}, { 8, 7, 9, 9, 2, 1, 9, 7, 2, 2, 7, 6, -1, 0, 0, 0,}, { 6, 10, 1, 6, 1, 7, 7, 1, 3, -1, 0, 0, 0, 0, 0, 0,}, { 6, 10, 1, 6, 1, 0, 6, 0, 7, 7, 0, 8, -1, 0, 0, 0,}, { 7, 6, 3, 3, 9, 0, 6, 9, 3, 6, 10, 9, -1, 0, 0, 0,}, { 6, 8, 7, 6, 10, 8, 8, 10, 9, -1, 0, 0, 0, 0, 0, 0,}, { 8, 6, 11, 8, 4, 6, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 11, 3, 0, 11, 0, 6, 6, 0, 4, -1, 0, 0, 0, 0, 0, 0,}, { 6, 8, 4, 6, 11, 8, 0, 1, 9, -1, 0, 0, 0, 0, 0, 0,}, { 1, 9, 3, 3, 6, 11, 9, 6, 3, 9, 4, 6, -1, 0, 0, 0,}, { 8, 6, 11, 8, 4, 6, 10, 1, 2, -1, 0, 0, 0, 0, 0, 0,}, { 2, 10, 1, 11, 3, 0, 11, 0, 6, 6, 0, 4, -1, 0, 0, 0,}, { 11, 4, 6, 11, 8, 4, 2, 10, 9, 2, 9, 0, -1, 0, 0, 0,}, { 4, 6, 11, 4, 11, 9, 9, 11, 3, 9, 3, 2, 9, 2, 10, -1,}, { 3, 8, 4, 3, 4, 2, 2, 4, 6, -1, 0, 0, 0, 0, 0, 0,}, { 2, 0, 4, 2, 4, 6, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 0, 1, 9, 3, 8, 4, 3, 4, 2, 2, 4, 6, -1, 0, 0, 0,}, { 9, 2, 1, 9, 4, 2, 2, 4, 6, -1, 0, 0, 0, 0, 0, 0,}, { 6, 10, 4, 4, 3, 8, 4, 10, 3, 3, 10, 1, -1, 0, 0, 0,}, { 1, 6, 10, 1, 0, 6, 6, 0, 4, -1, 0, 0, 0, 0, 0, 0,}, { 10, 9, 0, 10, 0, 6, 6, 0, 3, 6, 3, 8, 6, 8, 4, -1,}, { 10, 9, 4, 10, 4, 6, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 6, 11, 7, 5, 4, 9, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 0, 8, 3, 9, 5, 4, 7, 6, 11, -1, 0, 0, 0, 0, 0, 0,}, { 0, 5, 4, 0, 1, 5, 6, 11, 7, -1, 0, 0, 0, 0, 0, 0,}, { 7, 6, 11, 4, 8, 3, 4, 3, 5, 5, 3, 1, -1, 0, 0, 0,}, { 2, 10, 1, 11, 7, 6, 5, 4, 9, -1, 0, 0, 0, 0, 0, 0,}, { 0, 8, 3, 1, 2, 10, 4, 9, 5, 11, 7, 6, -1, 0, 0, 0,}, { 6, 11, 7, 10, 5, 4, 10, 4, 2, 2, 4, 0, -1, 0, 0, 0,}, { 6, 11, 7, 5, 2, 10, 5, 4, 2, 2, 4, 3, 3, 4, 8, -1,}, { 2, 7, 6, 2, 3, 7, 4, 9, 5, -1, 0, 0, 0, 0, 0, 0,}, { 4, 9, 5, 8, 7, 6, 8, 6, 0, 0, 6, 2, -1, 0, 0, 0,}, { 3, 6, 2, 3, 7, 6, 0, 1, 5, 0, 5, 4, -1, 0, 0, 0,}, { 1, 5, 4, 1, 4, 2, 2, 4, 8, 2, 8, 7, 2, 7, 6, -1,}, { 5, 4, 9, 6, 10, 1, 6, 1, 7, 7, 1, 3, -1, 0, 0, 0,}, { 4, 9, 5, 7, 0, 8, 7, 6, 0, 0, 6, 1, 1, 6, 10, -1,}, { 3, 7, 6, 3, 6, 0, 0, 6, 10, 0, 10, 5, 0, 5, 4, -1,}, { 4, 8, 5, 8, 10, 5, 8, 6, 10, 8, 7, 6, -1, 0, 0, 0,}, { 5, 6, 11, 5, 11, 9, 9, 11, 8, -1, 0, 0, 0, 0, 0, 0,}, { 0, 9, 5, 0, 5, 6, 0, 6, 3, 3, 6, 11, -1, 0, 0, 0,}, { 8, 0, 11, 11, 5, 6, 11, 0, 5, 5, 0, 1, -1, 0, 0, 0,}, { 11, 5, 6, 11, 3, 5, 5, 3, 1, -1, 0, 0, 0, 0, 0, 0,}, { 10, 1, 2, 5, 6, 11, 5, 11, 9, 9, 11, 8, -1, 0, 0, 0,}, { 2, 10, 1, 3, 6, 11, 3, 0, 6, 6, 0, 5, 5, 0, 9, -1,}, { 0, 2, 10, 0, 10, 8, 8, 10, 5, 8, 5, 6, 8, 6, 11, -1,}, { 11, 3, 6, 3, 5, 6, 3, 10, 5, 3, 2, 10, -1, 0, 0, 0,}, { 2, 3, 6, 6, 9, 5, 3, 9, 6, 3, 8, 9, -1, 0, 0, 0,}, { 5, 0, 9, 5, 6, 0, 0, 6, 2, -1, 0, 0, 0, 0, 0, 0,}, { 6, 2, 3, 6, 3, 5, 5, 3, 8, 5, 8, 0, 5, 0, 1, -1,}, { 6, 2, 1, 6, 1, 5, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 8, 9, 5, 8, 5, 3, 3, 5, 6, 3, 6, 10, 3, 10, 1, -1,}, { 1, 0, 10, 0, 6, 10, 0, 5, 6, 0, 9, 5, -1, 0, 0, 0,}, { 0, 3, 8, 10, 5, 6, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 10, 5, 6, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 11, 5, 10, 11, 7, 5, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 5, 11, 7, 5, 10, 11, 3, 0, 8, -1, 0, 0, 0, 0, 0, 0,}, { 11, 5, 10, 11, 7, 5, 9, 0, 1, -1, 0, 0, 0, 0, 0, 0,}, { 9, 3, 1, 9, 8, 3, 5, 10, 11, 5, 11, 7, -1, 0, 0, 0,}, { 2, 11, 7, 2, 7, 1, 1, 7, 5, -1, 0, 0, 0, 0, 0, 0,}, { 3, 0, 8, 2, 11, 7, 2, 7, 1, 1, 7, 5, -1, 0, 0, 0,}, { 2, 11, 0, 0, 5, 9, 0, 11, 5, 5, 11, 7, -1, 0, 0, 0,}, { 9, 8, 3, 9, 3, 5, 5, 3, 2, 5, 2, 11, 5, 11, 7, -1,}, { 10, 2, 3, 10, 3, 5, 5, 3, 7, -1, 0, 0, 0, 0, 0, 0,}, { 5, 10, 7, 7, 0, 8, 10, 0, 7, 10, 2, 0, -1, 0, 0, 0,}, { 1, 9, 0, 10, 2, 3, 10, 3, 5, 5, 3, 7, -1, 0, 0, 0,}, { 7, 5, 10, 7, 10, 8, 8, 10, 2, 8, 2, 1, 8, 1, 9, -1,}, { 7, 5, 1, 7, 1, 3, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 8, 1, 0, 8, 7, 1, 1, 7, 5, -1, 0, 0, 0, 0, 0, 0,}, { 0, 5, 9, 0, 3, 5, 5, 3, 7, -1, 0, 0, 0, 0, 0, 0,}, { 7, 5, 9, 7, 9, 8, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 4, 5, 10, 4, 10, 8, 8, 10, 11, -1, 0, 0, 0, 0, 0, 0,}, { 11, 3, 10, 10, 4, 5, 10, 3, 4, 4, 3, 0, -1, 0, 0, 0,}, { 9, 0, 1, 4, 5, 10, 4, 10, 8, 8, 10, 11, -1, 0, 0, 0,}, { 3, 1, 9, 3, 9, 11, 11, 9, 4, 11, 4, 5, 11, 5, 10, -1,}, { 8, 4, 11, 11, 1, 2, 4, 1, 11, 4, 5, 1, -1, 0, 0, 0,}, { 5, 1, 2, 5, 2, 4, 4, 2, 11, 4, 11, 3, 4, 3, 0, -1,}, { 11, 8, 4, 11, 4, 2, 2, 4, 5, 2, 5, 9, 2, 9, 0, -1,}, { 2, 11, 3, 5, 9, 4, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 4, 5, 10, 4, 10, 2, 4, 2, 8, 8, 2, 3, -1, 0, 0, 0,}, { 10, 4, 5, 10, 2, 4, 4, 2, 0, -1, 0, 0, 0, 0, 0, 0,}, { 0, 1, 9, 8, 2, 3, 8, 4, 2, 2, 4, 10, 10, 4, 5, -1,}, { 10, 2, 5, 2, 4, 5, 2, 9, 4, 2, 1, 9, -1, 0, 0, 0,}, { 4, 3, 8, 4, 5, 3, 3, 5, 1, -1, 0, 0, 0, 0, 0, 0,}, { 0, 4, 5, 0, 5, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 0, 3, 9, 3, 5, 9, 3, 4, 5, 3, 8, 4, -1, 0, 0, 0,}, { 4, 5, 9, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 7, 4, 9, 7, 9, 11, 11, 9, 10, -1, 0, 0, 0, 0, 0, 0,}, { 8, 3, 0, 7, 4, 9, 7, 9, 11, 11, 9, 10, -1, 0, 0, 0,}, { 0, 1, 4, 4, 11, 7, 1, 11, 4, 1, 10, 11, -1, 0, 0, 0,}, { 10, 11, 7, 10, 7, 1, 1, 7, 4, 1, 4, 8, 1, 8, 3, -1,}, { 2, 11, 7, 2, 7, 4, 2, 4, 1, 1, 4, 9, -1, 0, 0, 0,}, { 0, 8, 3, 1, 4, 9, 1, 2, 4, 4, 2, 7, 7, 2, 11, -1,}, { 7, 2, 11, 7, 4, 2, 2, 4, 0, -1, 0, 0, 0, 0, 0, 0,}, { 7, 4, 11, 4, 2, 11, 4, 3, 2, 4, 8, 3, -1, 0, 0, 0,}, { 7, 4, 3, 3, 10, 2, 3, 4, 10, 10, 4, 9, -1, 0, 0, 0,}, { 2, 0, 8, 2, 8, 10, 10, 8, 7, 10, 7, 4, 10, 4, 9, -1,}, { 4, 0, 1, 4, 1, 7, 7, 1, 10, 7, 10, 2, 7, 2, 3, -1,}, { 4, 8, 7, 1, 10, 2, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 9, 7, 4, 9, 1, 7, 7, 1, 3, -1, 0, 0, 0, 0, 0, 0,}, { 8, 7, 0, 7, 1, 0, 7, 9, 1, 7, 4, 9, -1, 0, 0, 0,}, { 4, 0, 3, 4, 3, 7, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 4, 8, 7, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 8, 9, 10, 8, 10, 11, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 0, 11, 3, 0, 9, 11, 11, 9, 10, -1, 0, 0, 0, 0, 0, 0,}, { 1, 8, 0, 1, 10, 8, 8, 10, 11, -1, 0, 0, 0, 0, 0, 0,}, { 3, 1, 10, 3, 10, 11, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 2, 9, 1, 2, 11, 9, 9, 11, 8, -1, 0, 0, 0, 0, 0, 0,}, { 0, 9, 3, 9, 11, 3, 9, 2, 11, 9, 1, 2, -1, 0, 0, 0,}, { 11, 8, 0, 11, 0, 2, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 2, 11, 3, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 3, 10, 2, 3, 8, 10, 10, 8, 9, -1, 0, 0, 0, 0, 0, 0,}, { 9, 10, 2, 9, 2, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 3, 8, 2, 8, 10, 2, 8, 1, 10, 8, 0, 1, -1, 0, 0, 0,}, { 2, 1, 10, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 8, 9, 1, 8, 1, 3, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 1, 0, 9, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { 0, 3, 8, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, { -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, }; static int8_t const marching_cubes_edge2indices[12][2] = { { 0, 1,}, { 2, 1,}, { 3, 2,}, { 3, 0,}, { 4, 5,}, { 6, 5,}, { 7, 6,}, { 7, 4,}, { 4, 0,}, { 5, 1,}, { 6, 2,}, { 7, 3,}, }; static int8_t const marching_cubes_index2vertex[8][3] = { { 0, 1, 1,}, { 1, 1, 1,}, { 1, 1, 0,}, { 0, 1, 0,}, { 0, 0, 1,}, { 1, 0, 1,}, { 1, 0, 0,}, { 0, 0, 0,}, }; void marching_cubes_compute(int64_t size_x, int64_t size_y, int64_t size_z, MARCHING_CUBES_DATA_TYPE const *volume, double spacing_x, double spacing_y, double spacing_z, int32_t *index_map, double threshold, int64_t *out_vertex_count, float *out_vertices, int64_t *out_index_count, int32_t *out_indices) { // indexed starting from 1 thus 0 means no vertex memset(index_map, 0, 3*size_x*size_y*size_z*sizeof *index_map); int64_t v_count = 0; int64_t i_count = 0; // precompute vertex offsets to keep the code cleaner int64_t offsets[8]; for (int64_t i = 0; i < 8; i += 1) { offsets[i] = marching_cubes_index2vertex[i][0] + size_x*(marching_cubes_index2vertex[i][1] + size_y*marching_cubes_index2vertex[i][2]); } for (int64_t k = 0; k + 1 < size_z; k += 1) { for (int64_t j = 0; j + 1 < size_y; j += 1) { for (int64_t i = 0; i + 1 < size_x; i += 1) { int64_t offset = i + size_x*(j + size_y*k); // compute the case uint8_t c = 0; for (int vertex_i = 0; vertex_i < 8; vertex_i += 1) { c |= (volume[offset + offsets[vertex_i]] >= threshold) << vertex_i; } // extract trangles (every 3 edges is one triangle) for (int edge_i = 0; marching_cubes_edges[c][edge_i] != -1; edge_i += 1) { int8_t vertex0_i = marching_cubes_edge2indices[marching_cubes_edges[c][edge_i]][0]; int8_t vertex1_i = marching_cubes_edge2indices[marching_cubes_edges[c][edge_i]][1]; int8_t const *vertex0 = marching_cubes_index2vertex[vertex0_i]; int8_t const *vertex1 = marching_cubes_index2vertex[vertex1_i]; int64_t hash = 3*(offset + offsets[vertex0_i]) + (vertex0[1] != vertex1[1]) + 2*(vertex0[2] != vertex1[2]); if (index_map[hash] == 0) { // calculate vertex along the edge if (out_vertices != NULL && out_indices != NULL) { double scalar0 = volume[offset + offsets[vertex0_i]]; double scalar1 = volume[offset + offsets[vertex1_i]]; double a = (threshold - scalar0)/(scalar1 - scalar0); out_vertices[3*v_count + 0] = (float)(spacing_x*((1.0 - a)*(i + vertex0[0]) + a*(i + vertex1[0]))); out_vertices[3*v_count + 1] = (float)(spacing_y*((1.0 - a)*(j + vertex0[1]) + a*(j + vertex1[1]))); out_vertices[3*v_count + 2] = (float)(spacing_z*((1.0 - a)*(k + vertex0[2]) + a*(k + vertex1[2]))); } v_count += 1; index_map[hash] = (int32_t)v_count; } if (out_vertices != NULL && out_indices != NULL) { out_indices[i_count] = index_map[hash] - 1; } i_count += 1; } } } } *out_vertex_count = v_count; *out_index_count = i_count; } #endif #endif