/*

opengametools voxel meshifier - v0.9 - MIT license - Justin Paver, April 2020

This is a single-header-file library that provides easy-to-use

support for converting paletted voxel grid data into an indexed triangle mesh.

Please see the MIT license information at the end of this file.

Also, please consider sharing any improvements you make.

For more information and more tools, visit:

https://github.com/jpaver/opengametools

USAGE

1. load your voxel grid data and palette data (see ogt_vox_model inside ogt_vox_loader.h for example)

and obtain the x, y and z dimensions of the grid.

2. convert into a mesh

ogt_mesh* mesh = ogt_mesh_from_paletted_voxels_simple( voxel_data, size_x, size_y, size_z, voxel_palette );

3. use the indexed triangle list in the mesh to construct renderable geometry, collision geometry.

// This is old sceen OpenGL immediate mode rendering for demonstration purposes only.

// Ideally you'd use more modern practices for rendering, including converting ogt_mesh data to

// your own engine's layout.

glBegin(GL_TRIANGLES);

for (uint32_t i = 0; i < mesh->index_count; i+=3)

{

uint32_t i0 = mesh->indices[i + 0];

uint32_t i1 = mesh->indices[i + 1];

uint32_t i2 = mesh->indices[i + 2];

const ogt_mesh_vertex* v0 = &mesh->vertices[i0];

const ogt_mesh_vertex* v1 = &mesh->vertices[i1];

const ogt_mesh_vertex* v2 = &mesh->vertices[i2];

glColor4ubv(&v0->color);

glNormal3fv(&v0->normal);

glVertex3fv(&v0->pos);

glColor4ubv(&v1->color);

glNormal3fv(&v1->normal);

glVertex3fv(&v1->pos);

glColor4ubv(&v2->color);

glNormal3fv(&v2->normal);

glVertex3fv(&v2->pos);

}

glEnd();

EXPLANATION

We currently only support paletted voxel data as input to the meshing algorithms here.

Paletted voxel mesh data assumes each voxel within the grid is a single byte

that represents a color index into a 256 color palette.

If the color index is 0, the voxel is assumed to be empty, otherwise it is solid.

For this reason, palette[0] will never be used.

Voxel data is laid out in x, then y, then z order. In other words, given

a coordinate (x,y,z) within your grid, you can compute where it is in your voxel

array using the following logic:

voxel_index = x + (y * size_x) + (z * size_x * size_y);

We support the following algorithms for meshing the voxel data for now:

* ogt_mesh_from_paletted_voxels_simple: creates 2 triangles for every visible voxel face.

* ogt_mesh_from_paletted_voxels_greedy: creates 2 triangles for every rectangular region of voxel faces with the same color

* ogt_mesh_from_paletted_voxels_polygon: determines the polygon contour of every connected voxel face with the same color and then triangulates that.

*/

#ifndef OGT_VOXEL_MESHIFY_H__

#define OGT_VOXEL_MESHIFY_H__

#if _MSC_VER == 1400

// VS2005 doesn't have inttypes or stdint so we just define what we need here.

typedef unsigned char uint8_t;

typedef signed int int32_t;

typedef unsigned int uint32_t;

typedef unsigned short uint16_t;

#ifndef UINT32_MAX

#define UINT32_MAX 0xFFFFFFFF

#endif

#elif defined(_MSC_VER)

// general VS*

#include <inttypes.h>

#elif __APPLE__

// general Apple compiler

#elif defined(__GNUC__)

// any GCC*

#include <inttypes.h>

#include <stdlib.h> // for size_t

#else

#error some fixup needed for this platform?

#endif

// a 3 dimensional quantity

struct ogt_mesh_vec3

{

float x, y, z;

};

// a color

struct ogt_mesh_rgba

{

uint8_t r,g,b,a;

};

// represents a vertex

struct ogt_mesh_vertex

};

// a mesh that contains an indexed triangle list of vertices

struct ogt_mesh

};

// allocate memory function interface. pass in size, and get a pointer to memory with at least that size available.

typedef void* (*ogt_voxel_meshify_alloc_func)(size_t size, void* user_data);

// free memory function interface. pass in a pointer previously allocated and it will be released back to the system managing memory.

typedef void (*ogt_voxel_meshify_free_func)(void* ptr, void* user_data);

// stream function can receive a batch of triangles for each voxel processed by ogt_stream_from_paletted_voxels_simple. (i,j,k)

typedef void (*ogt_voxel_simple_stream_func)(uint32_t x, uint32_t y, uint32_t z, const ogt_mesh_vertex* vertices, uint32_t vertex_count, const uint32_t* indices, uint32_t index_count, void* user_data);

// a context that allows you to override various internal operations of the below api functions.

struct ogt_voxel_meshify_context

};

// returns the number of quad faces that would be generated by tessellating the specified voxel field using the simple algorithm. Useful for preallocating memory.

// number of vertices needed would 4x this value, and number of indices needed would be 6x this value.

uint32_t ogt_face_count_from_paletted_voxels_simple(const uint8_t* voxels, uint32_t size_x, uint32_t size_y, uint32_t size_z);

// The simple meshifier returns the most naieve mesh possible, which will be tessellated at voxel granularity.

ogt_mesh* ogt_mesh_from_paletted_voxels_simple(const ogt_voxel_meshify_context* ctx, const uint8_t* voxels, uint32_t size_x, uint32_t size_y, uint32_t size_z, const ogt_mesh_rgba* palette);

// The greedy meshifier will use a greedy box-expansion pass to replace the polygons of adjacent voxels of the same color with a larger polygon that covers the box.

// It will generally produce t-junctions which can make rasterization not water-tight based on your camera/project/distances.

ogt_mesh* ogt_mesh_from_paletted_voxels_greedy(const ogt_voxel_meshify_context* ctx, const uint8_t* voxels, uint32_t size_x, uint32_t size_y, uint32_t size_z, const ogt_mesh_rgba* palette);

// The polygon meshifier will polygonize and triangulate connected voxels that are of the same color. The boundary of the polygon

// will be tessellated only to the degree that is necessary to there are tessellations at color discontinuities.

// This will mostly be water-tight, except for a very small number of cases.

ogt_mesh* ogt_mesh_from_paletted_voxels_polygon(const ogt_voxel_meshify_context* ctx, const uint8_t* voxels, uint32_t size_x, uint32_t size_y, uint32_t size_z, const ogt_mesh_rgba* palette);

// ogt_mesh_remove_duplicate_vertices will in-place remove identical vertices and remap indices to produce an identical mesh.

// Use this after a call to ogt_mesh_from_paletted_voxels_* functions to remove duplicate vertices with the same attributes.

void ogt_mesh_remove_duplicate_vertices(const ogt_voxel_meshify_context* ctx, ogt_mesh* mesh);

// Removes faceted normals on the mesh and averages vertex normals based on the faces that are adjacent.

// It is recommended only to call this on ogt_mesh_from_paletted_voxels_simple.

void ogt_mesh_smooth_normals(const ogt_voxel_meshify_context* ctx, ogt_mesh* mesh);

// destroys the mesh returned by ogt_mesh_from_paletted_voxels* functions.

void ogt_mesh_destroy(const ogt_voxel_meshify_context* ctx, ogt_mesh* mesh );

// The simple stream function will stream geometry for the specified voxel field, to the specified stream function, which will be invoked on each voxel that requires geometry.

void ogt_stream_from_paletted_voxels_simple(const uint8_t* voxels, uint32_t size_x, uint32_t size_y, uint32_t size_z, const ogt_mesh_rgba* palette, ogt_voxel_simple_stream_func stream_func, void* stream_func_data);

#endif // OGT_VOXEL_MESHIFY_H__

//-----------------------------------------------------------------------------------------------------------------

//

// If you're only interested in using this library, everything you need is above this point.

// If you're interested in how this library works, everything you need is below this point.

//

//-----------------------------------------------------------------------------------------------------------------

#ifdef OGT_VOXEL_MESHIFY_IMPLEMENTATION

#include <assert.h>

#include <stdlib.h>

#include <memory.h>

#include <math.h>

// a set of up to 65536 bits

struct ogt_mesh_bitset_64k {

}

uint8_t is_set(uint32_t index) { return bits[index/8] & (1<<(index%8)); }

void set(uint32_t index) { bits[index/8] |= (1<<(index%8)); }

void unset(uint32_t index) { bits[index/8] &= ~(1<<(index%8)); }

};

static void* _voxel_meshify_malloc(const ogt_voxel_meshify_context* ctx, size_t size) {

return size ? (ctx->alloc_func ? ctx->alloc_func(size, ctx->alloc_free_user_data) : malloc(size)) : NULL;

}

static void _voxel_meshify_free(const ogt_voxel_meshify_context* ctx, void* old_ptr) {

if (old_ptr) {

if (ctx->free_func)

ctx->free_func(old_ptr, ctx->alloc_free_user_data);

else

free(old_ptr);

}

}

// column-major 4x4 matrix

struct ogt_mesh_transform {

};

// replaces transforms the point computes: transform * (vec.x, vec.y, vec.z, 1.0)

inline ogt_mesh_vec3 _transform_point(const ogt_mesh_transform& transform, const ogt_mesh_vec3& vec) {

ogt_mesh_vec3 ret;

ret.x = transform.m30 + (transform.m00 * vec.x) + (transform.m10 * vec.y) + (transform.m20 * vec.z);

ret.y = transform.m31 + (transform.m01 * vec.x) + (transform.m11 * vec.y) + (transform.m21 * vec.z);

ret.z = transform.m32 + (transform.m02 * vec.x) + (transform.m12 * vec.y) + (transform.m22 * vec.z);

return ret;

}

// replaces transforms the point computes: transform * (vec.x, vec.y, vec.z, 0.0)

inline ogt_mesh_vec3 _transform_vector(const ogt_mesh_transform& transform, const ogt_mesh_vec3& vec) {

ogt_mesh_vec3 ret;

ret.x = (transform.m00 * vec.x) + (transform.m10 * vec.y) + (transform.m20 * vec.z);

ret.y = (transform.m01 * vec.x) + (transform.m11 * vec.y) + (transform.m21 * vec.z);

ret.z = (transform.m02 * vec.x) + (transform.m12 * vec.y) + (transform.m22 * vec.z);

return ret;

}

inline ogt_mesh_transform _make_transform(

float m30, float m31, float m32, float m33)

{

ogt_mesh_transform ret;

ret.m00 = m00; ret.m01 = m01; ret.m02 = m02; ret.m03 = m03;

ret.m10 = m10; ret.m11 = m11; ret.m12 = m12; ret.m13 = m13;

ret.m20 = m20; ret.m21 = m21; ret.m22 = m22; ret.m23 = m23;

ret.m30 = m30; ret.m31 = m31; ret.m32 = m32; ret.m33 = m33;

return ret;

}

inline ogt_mesh_vec3 _make_vec3(float x, float y, float z ) {

ogt_mesh_vec3 ret;

ret.x = x; ret.y = y; ret.z = z;

return ret;

}

static inline const ogt_mesh_vec3* _make_vec3_ptr(const float* xyz_elements) {

return (ogt_mesh_vec3*)xyz_elements;

}

static inline float _dot3(const ogt_mesh_vec3& a, const ogt_mesh_vec3& b) {

return (a.x * b.x) + (a.y * b.y) + (a.z * b.z);

}

static inline ogt_mesh_vec3 _cross3(const ogt_mesh_vec3& a, const ogt_mesh_vec3& b) {

ogt_mesh_vec3 ret;

ret.x = (a.y * b.z) - (a.z * b.y);

ret.y = (a.z * b.x) - (a.x * b.z);

ret.z = (a.x * b.y) - (a.y * b.x);

return ret;

}

static inline ogt_mesh_vec3 _sub3(const ogt_mesh_vec3 & a, const ogt_mesh_vec3 & b) {

ogt_mesh_vec3 ret;

ret.x = a.x - b.x;

ret.y = a.y - b.y;

ret.z = a.z - b.z;

return ret;

}

static inline ogt_mesh_vec3 _add3(const ogt_mesh_vec3 & a, const ogt_mesh_vec3 & b) {

ogt_mesh_vec3 ret;

ret.x = a.x + b.x;

ret.y = a.y + b.y;

ret.z = a.z + b.z;

return ret;

}

static inline ogt_mesh_vec3 _normalize3(const ogt_mesh_vec3 & a) {

float len = sqrtf(a.x * a.x + a.y * a.y + a.z * a.z);

assert(len > 0.0f);

float len_inv = 1.0f / len;

ogt_mesh_vec3 ret;

ret.x = a.x * len_inv;

ret.y = a.y * len_inv;

ret.z = a.z * len_inv;

return ret;

}

static inline ogt_mesh_vertex _mesh_make_vertex(const ogt_mesh_vec3& pos, const ogt_mesh_vec3& normal, const ogt_mesh_rgba color, uint32_t palette_index) {

ogt_mesh_vertex ret;

ret.pos = pos;

ret.normal = normal;

ret.color = color;

ret.palette_index = palette_index;

return ret;

}

static inline ogt_mesh_vertex _mesh_make_vertex(float pos_x, float pos_y, float pos_z, float normal_x, float normal_y, float normal_z, ogt_mesh_rgba color, uint32_t palette_index) {

return _mesh_make_vertex(_make_vec3(pos_x, pos_y, pos_z), _make_vec3(normal_x, normal_y, normal_z), color, palette_index);

}

// counts the number of voxel sized faces that are needed for this voxel grid.

static uint32_t _count_voxel_sized_faces( const uint8_t* voxels, uint32_t size_x, uint32_t size_y, uint32_t size_z ) {

const int32_t k_stride_x = 1;

const int32_t k_stride_y = size_x;

const int32_t k_stride_z = size_x * size_y;

const int32_t k_max_x = size_x - 1;

const int32_t k_max_y = size_y - 1;

const int32_t k_max_z = size_z - 1;

uint32_t face_count = 0;

const uint8_t* current_voxel = voxels;

for (int32_t k = 0; k < (int32_t)size_z; k++)

{

for (int32_t j = 0; j < (int32_t)size_y; j++)

{

for (int32_t i = 0; i < (int32_t)size_x; i++, current_voxel++)

{

if (current_voxel[0] != 0) // voxel is not empty.

{

// check each of the -X,+X,-Y,+Y,-Z,+Z directions to see if a face is needed in that direction.

face_count += ((i == 0) || (current_voxel[-k_stride_x] == 0 )) ? 1 : 0; // if on min x boundary of voxel grid, or neighbor to -1 on x is empty

face_count += ((i == k_max_x) || (current_voxel[ k_stride_x] == 0 )) ? 1 : 0; // if on max x boundary of voxel grid, or neighbor to +1 on x is empty

face_count += ((j == 0) || (current_voxel[-k_stride_y] == 0 )) ? 1 : 0; // if on min y boundary of voxel grid, or neighbor to -1 on y is empty

face_count += ((j == k_max_y) || (current_voxel[ k_stride_y] == 0 )) ? 1 : 0; // if on max y boundary of voxel grid, or neighbor to +1 on y is empty

face_count += ((k == 0) || (current_voxel[-k_stride_z] == 0 )) ? 1 : 0; // if on min z boundary of voxel grid, or neighbor to -1 on z is empty

face_count += ((k == k_max_z) || (current_voxel[ k_stride_z] == 0 )) ? 1 : 0; // if on max z boundary of voxel grid, or neighbor to +1 on z is empty

}

}

}

}

return face_count;

}

// murmur_hash2 - this variant deals with only 4 bytes at a time

static uint32_t murmur_hash2_size4(uint32_t h, const uint32_t* data, uint32_t data_len) {

assert(data_len % 4 == 0);

const uint32_t m = 0x5bd1e995;

while (data_len >= 4) {

uint32_t k = data[0];

k *= m;

k ^= k >> (signed)24;

k *= m;

h *= m;

h ^= k;

data++;

data_len -= 4;

}

return h;

}

// quadratic probing in the hash table.

static uint32_t* hash_table_find_vertex(uint32_t* table, uint32_t table_index_mask, const uint8_t* vertex_data, uint32_t vertex_size, uint32_t vertex_index) {

uint32_t* this_vertex = (uint32_t*)&vertex_data[vertex_index*vertex_size];

uint32_t bucket_index = murmur_hash2_size4(0, this_vertex, vertex_size) & table_index_mask;

for (uint32_t probe_count = 0; probe_count <= table_index_mask; probe_count++) {

uint32_t* existing_index = &table[bucket_index];

// if there is an uninitialized value at this bucket, the vertex is definitely not already in the hash table.

if (*existing_index == UINT32_MAX)

return existing_index;

// this item is potentially in the table, we compare to see if the existing vertex matches the one we're trying to find.

uint32_t* existing_vertex = (uint32_t*)&vertex_data[*existing_index*vertex_size];

if (memcmp(this_vertex, existing_vertex, vertex_size) == 0) {

assert(*existing_index < vertex_index);

return existing_index;

}

// use quadratic probing to find the next bucket in the case of a collision.

bucket_index = (bucket_index + probe_count + 1) & table_index_mask;

}

// hash table is full. We should technically never get here because we always allocate more buckets in the table than vertices we search for.

assert(false);

return NULL;

}

// quadratic probing in the hash table

static uint32_t* hash_table_find_vertex_position(uint32_t* table, uint32_t table_index_mask, const ogt_mesh_vertex* vertex_data, uint32_t vertex_index) {

const ogt_mesh_vertex* this_vertex = &vertex_data[vertex_index];

uint32_t bucket_index = murmur_hash2_size4(0, (uint32_t*)& this_vertex->pos, sizeof(this_vertex->pos)) & table_index_mask;

for (uint32_t probe_count = 0; probe_count <= table_index_mask; probe_count++) {

uint32_t* existing_index = &table[bucket_index];

// if there is an uninitialized value at this bucket, the vertex is definitely not already in the hash table.

if (*existing_index == UINT32_MAX)

return existing_index;

// this item is potentially in the table, we compare to see if the existing vertex matches the one we're trying to find.

const ogt_mesh_vertex * existing_vertex = &vertex_data[*existing_index];

if (memcmp(&this_vertex->pos, &existing_vertex->pos, sizeof(this_vertex->pos)) == 0) {

assert(*existing_index < vertex_index);

return existing_index;

}

// use quadratic probing to find the next bucket in the case of a collision.

bucket_index = (bucket_index + probe_count + 1) & table_index_mask;

}

// hash table is full. We should technically never get here because we always allocate more buckets in the table than vertices we search for.

assert(false);

return NULL;

}

// removes duplicate vertices in-place from the specified mesh.

void ogt_mesh_remove_duplicate_vertices(const ogt_voxel_meshify_context* ctx, ogt_mesh* mesh) {

uint32_t* indices = mesh->indices;

uint32_t index_count = mesh->index_count;

uint8_t* vertices = (uint8_t*)mesh->vertices;

uint32_t vertex_count = mesh->vertex_count;

uint32_t vertex_size = sizeof(ogt_mesh_vertex);

assert(indices && index_count && vertices && vertex_count && vertex_size);

// allocate a hash table that is sized at the next power of 2 above the vertex count

uint32_t hash_table_size = 1;

while (hash_table_size < vertex_count)

hash_table_size *= 2;

uint32_t hash_table_mask = hash_table_size - 1;

uint32_t* hash_table = (uint32_t*)_voxel_meshify_malloc(ctx, sizeof(uint32_t) * hash_table_size);

memset(hash_table, -1, hash_table_size * sizeof(uint32_t));

// generate an remap table for vertex indices

uint32_t* remap_indices = (uint32_t*)_voxel_meshify_malloc(ctx, sizeof(uint32_t) * vertex_count);

memset(remap_indices, -1, vertex_count * sizeof(uint32_t));

uint32_t num_unique_vertices = 0;

for (uint32_t vertex_index = 0; vertex_index < vertex_count; vertex_index++) {

uint32_t* hash_table_entry = hash_table_find_vertex(hash_table, hash_table_mask, vertices, vertex_size, vertex_index);

if (*hash_table_entry == UINT32_MAX) {

// vertex is not already in the hash table. allocate a unique index for it.

*hash_table_entry = vertex_index;;

remap_indices[vertex_index] = num_unique_vertices++;

}

else {

// vertex is already in the hash table. Point this to the index that is already existing!

assert(remap_indices[*hash_table_entry] != UINT32_MAX);

remap_indices[vertex_index] = remap_indices[*hash_table_entry];

}

}

// compact all vertices using the remap_indices map.

for (uint32_t i = 0; i < vertex_count; i++) {

uint32_t dst_index = remap_indices[i];

uint32_t src_index = i;

assert(dst_index <= src_index);

memcpy(&vertices[dst_index*vertex_size], &vertices[src_index*vertex_size], vertex_size);

}

// remap all indices now

for (uint32_t i = 0; i < index_count; i++) {

indices[i] = remap_indices[indices[i]];

}

_voxel_meshify_free(ctx, hash_table);

_voxel_meshify_free(ctx, remap_indices);

assert(num_unique_vertices <= mesh->vertex_count);

mesh->vertex_count = num_unique_vertices;

}

// resets normals for the mesh so they are based on triangle connectivity, while preserving triangle colors.

void ogt_mesh_smooth_normals(const ogt_voxel_meshify_context* ctx, ogt_mesh* mesh) {

// generate an remap table for vertex indices based on the vertex positions.

uint32_t* remap_indices = (uint32_t*)_voxel_meshify_malloc(ctx, sizeof(uint32_t) * mesh->vertex_count);

memset(remap_indices, -1, mesh->vertex_count * sizeof(uint32_t));

{

// allocate a hash table that is sized at the next power of 2 above the vertex count

uint32_t hash_table_size = 1;

while (hash_table_size < mesh->vertex_count)

hash_table_size *= 2;

uint32_t hash_table_mask = hash_table_size - 1;

uint32_t* hash_table = (uint32_t*)_voxel_meshify_malloc(ctx, sizeof(uint32_t) * hash_table_size);

memset(hash_table, -1, hash_table_size * sizeof(uint32_t));

// create a unique mapping for each vertex based purely on its position

uint32_t num_unique_vertices = 0;

for (uint32_t vertex_index = 0; vertex_index < mesh->vertex_count; vertex_index++) {

uint32_t* hash_table_entry = hash_table_find_vertex_position(hash_table, hash_table_mask, mesh->vertices, vertex_index);

if (*hash_table_entry == UINT32_MAX) {

// vertex is not already in the hash table. allocate a unique index for it.

*hash_table_entry = vertex_index;

remap_indices[vertex_index] = num_unique_vertices++;

}

else {

// vertex is already in the hash table. Point this to the index that is already existing!

assert(remap_indices[*hash_table_entry] != UINT32_MAX);

remap_indices[vertex_index] = remap_indices[*hash_table_entry];

}

}

// now that we have remap_indices, we no longer need the hash table.

_voxel_meshify_free(ctx, hash_table);

}

// for each triangle face, add the normal of the face to the unique normal for the vertex

ogt_mesh_vec3* remap_normals = (ogt_mesh_vec3*)_voxel_meshify_malloc(ctx, sizeof(ogt_mesh_vec3) * mesh->vertex_count);

memset(remap_normals, 0, sizeof(ogt_mesh_vec3) * mesh->vertex_count);

for (uint32_t i = 0; i < mesh->index_count; i += 3) {

uint32_t i0 = mesh->indices[i + 0];

uint32_t i1 = mesh->indices[i + 1];

uint32_t i2 = mesh->indices[i + 2];

ogt_mesh_vertex v0 = mesh->vertices[i0];

ogt_mesh_vertex v1 = mesh->vertices[i1];

ogt_mesh_vertex v2 = mesh->vertices[i2];

ogt_mesh_vec3 normal = _cross3(_sub3(v1.pos, v0.pos), _sub3(v2.pos, v0.pos));

uint32_t ri0 = remap_indices[i0];

uint32_t ri1 = remap_indices[i1];

uint32_t ri2 = remap_indices[i2];

remap_normals[ri0] = _add3(remap_normals[ri0], normal);

remap_normals[ri1] = _add3(remap_normals[ri1], normal);

remap_normals[ri2] = _add3(remap_normals[ri2], normal);

}

// for each vertex, copy over remap normal if it's non-zero.

for (uint32_t vertex_index = 0; vertex_index < mesh->vertex_count; vertex_index++) {

ogt_mesh_vec3 accumulated_normal = remap_normals[remap_indices[vertex_index]];

if (_dot3(accumulated_normal, accumulated_normal) > 0.001f)

mesh->vertices[vertex_index].normal = _normalize3(accumulated_normal);

}

_voxel_meshify_free(ctx, remap_normals);

_voxel_meshify_free(ctx, remap_indices);

}

static void _streaming_add_to_mesh(uint32_t x, uint32_t y, uint32_t z, const ogt_mesh_vertex* vertices, uint32_t vertex_count, const uint32_t* indices, uint32_t index_count, void* stream_func_data) {

// these params are unused for now.

(void)x; (void)y; (void)z;

// copy the specified vertices and indices into the mesh

ogt_mesh* mesh = (ogt_mesh*)stream_func_data;

memcpy(&mesh->vertices[mesh->vertex_count], vertices, vertex_count * sizeof(ogt_mesh_vertex));

memcpy(&mesh->indices[mesh->index_count], indices, index_count * sizeof(uint32_t));

mesh->vertex_count += vertex_count;

mesh->index_count += index_count;

}

// returns the number of quad faces that would be generated by tessellating the specified voxel field using the simple algorithm.

uint32_t ogt_face_count_from_paletted_voxels_simple(const uint8_t* voxels, uint32_t size_x, uint32_t size_y, uint32_t size_z)

{

return _count_voxel_sized_faces( voxels, size_x, size_y, size_z );

}

// constructs and returns a mesh from the specified voxel grid with no optimization to the geometry.

ogt_mesh* ogt_mesh_from_paletted_voxels_simple(

const ogt_voxel_meshify_context* ctx,

const uint8_t* voxels, uint32_t size_x, uint32_t size_y, uint32_t size_z, const ogt_mesh_rgba* palette)

{

uint32_t max_face_count = _count_voxel_sized_faces( voxels, size_x, size_y, size_z );

uint32_t max_vertex_count = max_face_count * 4;

uint32_t max_index_count = max_face_count * 6;

uint32_t mesh_size = sizeof(ogt_mesh) + (max_vertex_count * sizeof(ogt_mesh_vertex)) + (max_index_count * sizeof(uint32_t));

ogt_mesh* mesh = (ogt_mesh*)_voxel_meshify_malloc(ctx, mesh_size);

if (!mesh)

return NULL;

mesh->vertices = (ogt_mesh_vertex*)&mesh[1];

mesh->indices = (uint32_t*)&mesh->vertices[max_vertex_count];

mesh->vertex_count = 0;

mesh->index_count = 0;

ogt_stream_from_paletted_voxels_simple(voxels, size_x, size_y, size_z, palette, _streaming_add_to_mesh, mesh);

assert( mesh->vertex_count == max_vertex_count);

assert( mesh->index_count == max_index_count);

return mesh;

}

// streams geometry for each voxel at a time to a specified user function.

void ogt_stream_from_paletted_voxels_simple(

const uint8_t* voxels, uint32_t size_x, uint32_t size_y, uint32_t size_z, const ogt_mesh_rgba* palette,

ogt_voxel_simple_stream_func stream_func, void* stream_func_data)

{

assert(stream_func);

const int32_t k_stride_x = 1;

const int32_t k_stride_y = size_x;

const int32_t k_stride_z = size_x * size_y;

const int32_t k_max_x = size_x - 1;

const int32_t k_max_y = size_y - 1;

const int32_t k_max_z = size_z - 1;

const uint8_t* current_voxel = voxels;

uint32_t total_vertex_count = 0;

uint32_t total_index_count = 0;

for (int32_t k = 0; k < (int32_t)size_z; k++)

{

const float min_z = (float)k;

const float max_z = min_z + 1.0f;

for (int32_t j = 0; j < (int32_t)size_y; j++)

{

const float min_y = (float)j;

const float max_y = min_y + 1.0f;

for (int32_t i = 0; i < (int32_t)size_x; i++, current_voxel++)

{

// current voxel slot is empty? skip it.

if (current_voxel[0] == 0)

continue;

ogt_mesh_rgba color = palette[ current_voxel[0]];

// determine the min/max coords of the voxel for each dimension.

const float min_x = (float)i;

const float max_x = min_x + 1.0f;

// determine which faces we need to generate

uint32_t neg_x = ((i == 0) || (current_voxel[-k_stride_x] == 0));

uint32_t pos_x = ((i == k_max_x) || (current_voxel[ k_stride_x] == 0));

uint32_t neg_y = ((j == 0) || (current_voxel[-k_stride_y] == 0));

uint32_t pos_y = ((j == k_max_y) || (current_voxel[ k_stride_y] == 0));

uint32_t neg_z = ((k == 0) || (current_voxel[-k_stride_z] == 0));

uint32_t pos_z = ((k == k_max_z) || (current_voxel[ k_stride_z] == 0));

// count the number of faces. skip if zero.

const uint32_t face_count_needed = (neg_x + pos_x + neg_y + pos_y + neg_z + pos_z);

if (!face_count_needed)

continue;

// generate geometry for this voxel to a local buffer first.

ogt_mesh_vertex local_vertex[24];

uint32_t local_index[36];

ogt_mesh_vertex* current_vertex = local_vertex;

uint32_t* current_index = local_index;

// -X direction face

if (neg_x)

{

current_vertex[0] = _mesh_make_vertex( min_x, min_y, min_z, -1.0f, 0.0f, 0.0f, color, current_voxel[0] );

current_vertex[1] = _mesh_make_vertex( min_x, max_y, min_z, -1.0f, 0.0f, 0.0f, color, current_voxel[0] );

current_vertex[2] = _mesh_make_vertex( min_x, max_y, max_z, -1.0f, 0.0f, 0.0f, color, current_voxel[0] );

current_vertex[3] = _mesh_make_vertex( min_x, min_y, max_z, -1.0f, 0.0f, 0.0f, color, current_voxel[0] );

current_index[0] = total_vertex_count + 2;

current_index[1] = total_vertex_count + 1;

current_index[2] = total_vertex_count + 0;

current_index[3] = total_vertex_count + 0;

current_index[4] = total_vertex_count + 3;

current_index[5] = total_vertex_count + 2;

total_vertex_count += 4;

total_index_count += 6;

current_vertex += 4;

current_index += 6;

}

// +X direction face

if (pos_x)

{

current_vertex[0] = _mesh_make_vertex( max_x, min_y, min_z, 1.0f, 0.0f, 0.0f, color, current_voxel[0] );

current_vertex[1] = _mesh_make_vertex( max_x, max_y, min_z, 1.0f, 0.0f, 0.0f, color, current_voxel[0] );

current_vertex[2] = _mesh_make_vertex( max_x, max_y, max_z, 1.0f, 0.0f, 0.0f, color, current_voxel[0] );

current_vertex[3] = _mesh_make_vertex( max_x, min_y, max_z, 1.0f, 0.0f, 0.0f, color, current_voxel[0] );

current_index[0] = total_vertex_count + 0;

current_index[1] = total_vertex_count + 1;

current_index[2] = total_vertex_count + 2;

current_index[3] = total_vertex_count + 2;

current_index[4] = total_vertex_count + 3;

current_index[5] = total_vertex_count + 0;

total_vertex_count += 4;

total_index_count += 6;

current_vertex += 4;

current_index += 6;

}

// -Y direction face

if (neg_y)

{

current_vertex[0] = _mesh_make_vertex( min_x, min_y, min_z, 0.0f,-1.0f, 0.0f, color, current_voxel[0] );

current_vertex[1] = _mesh_make_vertex( max_x, min_y, min_z, 0.0f,-1.0f, 0.0f, color, current_voxel[0] );

current_vertex[2] = _mesh_make_vertex( max_x, min_y, max_z, 0.0f,-1.0f, 0.0f, color, current_voxel[0] );

current_vertex[3] = _mesh_make_vertex( min_x, min_y, max_z, 0.0f,-1.0f, 0.0f, color, current_voxel[0] );

current_index[0] = total_vertex_count + 0;

current_index[1] = total_vertex_count + 1;

current_index[2] = total_vertex_count + 2;

current_index[3] = total_vertex_count + 2;

current_index[4] = total_vertex_count + 3;

current_index[5] = total_vertex_count + 0;

total_vertex_count += 4;

total_index_count += 6;

current_vertex += 4;

current_index += 6;

}

// +Y direction face

if (pos_y)

{

current_vertex[0] = _mesh_make_vertex( min_x, max_y, min_z, 0.0f, 1.0f, 0.0f, color, current_voxel[0] );

current_vertex[1] = _mesh_make_vertex( max_x, max_y, min_z, 0.0f, 1.0f, 0.0f, color, current_voxel[0] );

current_vertex[2] = _mesh_make_vertex( max_x, max_y, max_z, 0.0f, 1.0f, 0.0f, color, current_voxel[0] );

current_vertex[3] = _mesh_make_vertex( min_x, max_y, max_z, 0.0f, 1.0f, 0.0f, color, current_voxel[0] );

current_index[0] = total_vertex_count + 2;

current_index[1] = total_vertex_count + 1;

current_index[2] = total_vertex_count + 0;

current_index[3] = total_vertex_count + 0;

current_index[4] = total_vertex_count + 3;

current_index[5] = total_vertex_count + 2;

total_vertex_count += 4;

total_index_count += 6;

current_vertex += 4;

current_index += 6;

}

// -Z direction face

if (neg_z)

{

current_vertex[0] = _mesh_make_vertex( min_x, min_y, min_z, 0.0f, 0.0f,-1.0f, color, current_voxel[0] );

current_vertex[1] = _mesh_make_vertex( max_x, min_y, min_z, 0.0f, 0.0f,-1.0f, color, current_voxel[0] );

current_vertex[2] = _mesh_make_vertex( max_x, max_y, min_z, 0.0f, 0.0f,-1.0f, color, current_voxel[0] );

current_vertex[3] = _mesh_make_vertex( min_x, max_y, min_z, 0.0f, 0.0f,-1.0f, color, current_voxel[0] );

current_index[0] = total_vertex_count + 2;

current_index[1] = total_vertex_count + 1;

current_index[2] = total_vertex_count + 0;

current_index[3] = total_vertex_count + 0;

current_index[4] = total_vertex_count + 3;

current_index[5] = total_vertex_count + 2;

total_vertex_count += 4;

total_index_count += 6;

current_vertex += 4;

current_index += 6;

}

// +Z direction face

if (pos_z)

{

current_vertex[0] = _mesh_make_vertex( min_x, min_y, max_z, 0.0f, 0.0f, 1.0f, color, current_voxel[0] );

current_vertex[1] = _mesh_make_vertex( max_x, min_y, max_z, 0.0f, 0.0f, 1.0f, color, current_voxel[0] );

current_vertex[2] = _mesh_make_vertex( max_x, max_y, max_z, 0.0f, 0.0f, 1.0f, color, current_voxel[0] );

current_vertex[3] = _mesh_make_vertex( min_x, max_y, max_z, 0.0f, 0.0f, 1.0f, color, current_voxel[0] );

current_index[0] = total_vertex_count + 0;

current_index[1] = total_vertex_count + 1;

current_index[2] = total_vertex_count + 2;

current_index[3] = total_vertex_count + 2;

current_index[4] = total_vertex_count + 3;

current_index[5] = total_vertex_count + 0;

total_vertex_count += 4;

total_index_count += 6;

current_vertex += 4;

current_index += 6;

}

// geometry for this voxel is provided to a caller-specified stream function/callback

stream_func(i, j, k, local_vertex, face_count_needed*4, local_index, face_count_needed*6, stream_func_data);

}

}

}

}

// The base algorithm that is used here, is as follows:

// On a per slice basis, we find a voxel that has not yet been polygonized. We then try to

// grow a rectangle from that voxel within the slice that can be represented by a polygon.

// We create the quad polygon to represent the voxel, mark the voxels in the slice that are

// covered by the rectangle as having been polygonized, and continue on the search through

// the rest of the slice.

void _greedy_meshify_voxels_in_face_direction(

ogt_mesh* out_mesh)

{

// enable aggressive voxel optimization for now.

uint32_t max_voxels_per_slice = size_x * size_y;

// allocate a structure that is used for tracking which voxels in a slice have already been included in output mesh.

assert(max_voxels_per_slice <= 65536); //

ogt_mesh_bitset_64k voxel_polygonized;

ogt_mesh_vec3 normal = _transform_vector(transform, _make_vec3(0.0f, 0.0f, 1.0f));

#define VOXELDATA_INDEX(_x,_y,_z) ((_x) * k_stride_x) + ((_y) * k_stride_y) + ((_z) * k_stride_z)

#define LOCALDATA_INDEX(_x,_y) ((_x) + ((_y) * size_x))

uint32_t* index_data = &out_mesh->indices[out_mesh->index_count];

ogt_mesh_vertex* vertex_data = &out_mesh->vertices[out_mesh->vertex_count];

// determine if the transform parity has flipped in a way that winding would have been switched.

const ogt_mesh_vec3* side = _make_vec3_ptr(&transform.m00);

const ogt_mesh_vec3* up = _make_vec3_ptr(&transform.m10);

const ogt_mesh_vec3* fwd = _make_vec3_ptr(&transform.m20);

bool is_parity_flipped = _dot3(*fwd, _cross3(*side, *up)) < 0.0f;

for (int32_t k0 = 0; k0 < size_z; k0++) {

// k0 = current slice, k1 = next slice

int32_t k1 = k0 + 1;

// reset the per-voxel X/Y status for this slice.

voxel_polygonized.clear(max_voxels_per_slice);

// is this the last slice? If yes, we don't check

bool is_last_k_slice = (k1 == size_z);

// here, we search for the first unprocessed voxel

for (int32_t j0 = 0; j0 < size_y; j0++) {

for (int32_t i0 = 0; i0 < size_x; i0++) {

// determine the polygon color index

uint8_t color_index = voxels[VOXELDATA_INDEX(i0, j0, k0)];

// this voxel doesn't need to be polygonized if...

if ((color_index == 0) || // (1) voxel is empty

voxel_polygonized.is_set(LOCALDATA_INDEX(i0, j0)) || // (2) voxel is already part of a polygon for the zslice.

(!is_last_k_slice && voxels[VOXELDATA_INDEX(i0, j0, k1)] != 0)) // (3) voxel in the next slice (+z direction) is solid

{

continue;

}

// compute i1. This is the coord bounding the longest span of identical voxels in the +i direction.

int32_t i1 = i0 + 1;

for (i1 = i0 + 1; i1 < size_x; i1++) {

// stop extending i1 if...

if ((voxels[VOXELDATA_INDEX(i1, j0, k0)] != color_index) || // (1) this voxel doesn't match the match color

(voxel_polygonized.is_set(LOCALDATA_INDEX(i1, j0))) || // (2) voxel is already part of a polygon for the zslice

(!is_last_k_slice && voxels[VOXELDATA_INDEX(i1, j0, k1)] != 0)) // (3) voxel in the next slice (+z direction) is solid

{

break;

}

}

// compute j1. The is the coord bounding the longest span of identical voxels [i0..i1] in the +j direction

int32_t j1 = j0 + 1;

for (j1 = j0 + 1; j1 < size_y; j1++) {

bool got_j1 = false;

for (int32_t a = i0; a < i1; a++) {

// stop extending i1 if...

if ((voxels[VOXELDATA_INDEX(a, j1, k0)] != color_index) || // (1) this voxel doesn't match the match color

(voxel_polygonized.is_set(LOCALDATA_INDEX(a,j1))) || // (2) voxel is already part of a polygon for the zslice

(!is_last_k_slice && voxels[VOXELDATA_INDEX(a,j1,k1)] != 0)) // (3) voxel in the next slice (+z direction) is solid

{

got_j1 = true;

break;

}

}

if (got_j1)

break;

}

// now j1 and i1 are the upper bound (exclusive) of the rectangle starting from i0,j0.

// mark all of this slice voxels in that rectangle as processed.

for (int32_t b = j0; b < j1; b++)

for (int32_t a = i0; a < i1; a++)

voxel_polygonized.set(LOCALDATA_INDEX(a,b));

// determine the min/max coords of the polygon for each dimension.

float min_x = (float)i0;

float max_x = (float)i1;

float min_y = (float)j0;

float max_y = (float)j1;

float max_z = (float)k1;

// cache the color

ogt_mesh_rgba color = palette[color_index];

// write the verts for this face

vertex_data[0] = _mesh_make_vertex(_transform_point(transform, _make_vec3(min_x, min_y, max_z)), normal, color, color_index);

vertex_data[1] = _mesh_make_vertex(_transform_point(transform, _make_vec3(max_x, min_y, max_z)), normal, color, color_index);

vertex_data[2] = _mesh_make_vertex(_transform_point(transform, _make_vec3(max_x, max_y, max_z)), normal, color, color_index);

vertex_data[3] = _mesh_make_vertex(_transform_point(transform, _make_vec3(min_x, max_y, max_z)), normal, color, color_index);

// reserve the index order to ensure parity/winding is still correct.

if (is_parity_flipped) {

index_data[0] = out_mesh->vertex_count + 0;

index_data[1] = out_mesh->vertex_count + 3;

index_data[2] = out_mesh->vertex_count + 2;

index_data[3] = out_mesh->vertex_count + 2;

index_data[4] = out_mesh->vertex_count + 1;

index_data[5] = out_mesh->vertex_count + 0;

}

else {

index_data[0] = out_mesh->vertex_count + 0;

index_data[1] = out_mesh->vertex_count + 1;

index_data[2] = out_mesh->vertex_count + 2;

index_data[3] = out_mesh->vertex_count + 2;

index_data[4] = out_mesh->vertex_count + 3;

index_data[5] = out_mesh->vertex_count + 0;

}

vertex_data += 4;

index_data += 6;

out_mesh->vertex_count += 4;

out_mesh->index_count += 6;

}

}

}

#undef VOXELDATA_INDEX

#undef LOCALDATA_INDEX

}

ogt_mesh* ogt_mesh_from_paletted_voxels_greedy(

const ogt_voxel_meshify_context* ctx,

const uint8_t* voxels, uint32_t size_x, uint32_t size_y, uint32_t size_z, const ogt_mesh_rgba* palette)

{

uint32_t max_face_count = _count_voxel_sized_faces( voxels, size_x, size_y, size_z );

uint32_t max_vertex_count = max_face_count * 4;

uint32_t max_index_count = max_face_count * 6;

uint32_t mesh_size = sizeof(ogt_mesh) + (max_vertex_count * sizeof(ogt_mesh_vertex)) + (max_index_count * sizeof(uint32_t));

ogt_mesh* mesh = (ogt_mesh*)_voxel_meshify_malloc(ctx, mesh_size);

if (!mesh)

return NULL;

mesh->vertices = (ogt_mesh_vertex*)&mesh[1];

mesh->indices = (uint32_t*)&mesh->vertices[max_vertex_count];

mesh->vertex_count = 0;

mesh->index_count = 0;

const int32_t k_stride_x = 1;

const int32_t k_stride_y = size_x;

const int32_t k_stride_z = size_x * size_y;

// do the +y PASS

{

ogt_mesh_transform transform_pos_y = _make_transform(

0.0f, 0.0f, 1.0f, 0.0f,

1.0f, 0.0f, 0.0f, 0.0f,

0.0f, 1.0f, 0.0f, 0.0f,

0.0f, 0.0f, 0.0f, 0.0f);

_greedy_meshify_voxels_in_face_direction(

voxels, palette,

size_z, size_x, size_y,

k_stride_z, k_stride_x, k_stride_y,

transform_pos_y,

mesh);

}

// do the -y PASS

{

ogt_mesh_transform transform_neg_y = _make_transform(

0.0f, 0.0f, 1.0f, 0.0f,

1.0f, 0.0f, 0.0f, 0.0f,

0.0f,-1.0f, 0.0f, 0.0f,

0.0f, (float)(size_y), 0.0f, 0.0f);

_greedy_meshify_voxels_in_face_direction(

voxels + (size_y - 1) * k_stride_y,

palette,

size_z, size_x, size_y,

k_stride_z, k_stride_x,-k_stride_y,

transform_neg_y,

mesh);

}

// do the +X pass

{

ogt_mesh_transform transform_pos_x = _make_transform(

0.0f, 1.0f, 0.0f, 0.0f,

0.0f, 0.0f, 1.0f, 0.0f,

1.0f, 0.0f, 0.0f, 0.0f,

0.0f, 0.0f, 0.0f, 0.0f);

_greedy_meshify_voxels_in_face_direction(

voxels, palette,

size_y, size_z, size_x,

k_stride_y, k_stride_z, k_stride_x,

transform_pos_x,

mesh);

}

// do the -X pass

{

ogt_mesh_transform transform_neg_x = _make_transform(

0.0f, 1.0f, 0.0f, 0.0f,

0.0f, 0.0f, 1.0f, 0.0f,

-1.0f, 0.0f, 0.0f, 0.0f,

(float)size_x, 0.0f, 0.0f, 0.0f);

_greedy_meshify_voxels_in_face_direction(

voxels + (size_x - 1) * k_stride_x,

palette,

size_y, size_z, size_x,

k_stride_y, k_stride_z, -k_stride_x,

transform_neg_x,

mesh);

}

// do the +Z pass

{

ogt_mesh_transform transform_pos_z = _make_transform(

1.0f, 0.0f, 0.0f, 0.0f,

0.0f, 1.0f, 0.0f, 0.0f,

0.0f, 0.0f, 1.0f, 0.0f,

0.0f, 0.0f, 0.0f, 0.0f);

_greedy_meshify_voxels_in_face_direction(

voxels, palette,

size_x, size_y, size_z,

k_stride_x, k_stride_y, k_stride_z,

transform_pos_z,