/*
 * trimesh.c -- in-memory indexed mesh for ez3d.
 *
 * The hash-index discipline is the same as verify.c's vspace: vertices
 * live in an append-only array (ids never change), and the bucket array
 * is re-linkable because chains only reference those stable ids. The
 * decimator depends on both properties.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "trimesh.h"

#define TM_NONE UINT32_MAX
#define TM_BASIS 1469598103934665603ull

static uint64_t tm_hash(const vertex_t *v)
{
    float key[3] = { v->x, v->y, v->z };
    const unsigned char *b = (const void *)key;
    uint64_t h = TM_BASIS;

    for (size_t i = 0; i < 12; i++) {
        h ^= b[i];
        h *= 1099511628211ull;
    }
    return h;
}

static void *tm_xrealloc(void *p, size_t n)
{
    p = realloc(p, n);
    if (!p) {
        fprintf(stderr, "ez3d: out of memory building mesh\n");
        exit(2);
    }
    return p;
}

void tm_init(trimesh_t *m)
{
    m->capv = m->captri = 1 << 12;
    m->nv = m->ntri = 0;
    m->v = tm_xrealloc(NULL, m->capv * sizeof *m->v);
    m->tri = tm_xrealloc(NULL, m->captri * 3 * sizeof *m->tri);
    m->nbuckets = 1 << 12;
    m->buckets = tm_xrealloc(NULL, m->nbuckets * sizeof *m->buckets);
    for (size_t i = 0; i < m->nbuckets; i++)
        m->buckets[i] = TM_NONE;
    m->next = tm_xrealloc(NULL, m->capv * sizeof *m->next);
}

void tm_free(trimesh_t *m)
{
    free(m->v);
    free(m->tri);
    free(m->buckets);
    free(m->next);
    memset(m, 0, sizeof *m);
}

static void tm_buckets_grow(trimesh_t *m)
{
    free(m->buckets);
    m->nbuckets *= 2;
    m->buckets = tm_xrealloc(NULL, m->nbuckets * sizeof *m->buckets);
    for (size_t i = 0; i < m->nbuckets; i++)
        m->buckets[i] = TM_NONE;
    for (size_t i = 0; i < m->nv; i++) {
        size_t j = tm_hash(&m->v[i]) & (m->nbuckets - 1);
        m->next[i] = m->buckets[j];
        m->buckets[j] = (uint32_t)i;
    }
}

uint32_t tm_vertex(trimesh_t *m, const vertex_t *v)
{
    uint64_t h = tm_hash(v);
    size_t j = h & (m->nbuckets - 1);

    for (uint32_t i = m->buckets[j]; i != TM_NONE; i = m->next[i]) {
        vertex_t *w = &m->v[i];
        if (v->x == w->x && v->y == w->y && v->z == w->z)
            return i;
    }

    if (m->nv == m->capv) {
        m->capv *= 2;
        m->v = tm_xrealloc(m->v, m->capv * sizeof *m->v);
        m->next = tm_xrealloc(m->next, m->capv * sizeof *m->next);
    }
    if ((m->nv + 1) * 10 >= m->nbuckets * 7)
        tm_buckets_grow(m);

    uint32_t id = (uint32_t)m->nv;
    m->v[id] = *v;
    j = h & (m->nbuckets - 1); /* may have changed after growth */
    m->next[id] = m->buckets[j];
    m->buckets[j] = id;
    m->nv++;
    return id;
}

uint32_t tm_append(trimesh_t *m, const vertex_t *v)
{
    if (m->nv == m->capv) {
        m->capv *= 2;
        m->v = tm_xrealloc(m->v, m->capv * sizeof *m->v);
        m->next = tm_xrealloc(m->next, m->capv * sizeof *m->next);
    }

    uint32_t id = (uint32_t)m->nv;
    m->v[id] = *v;
    m->next[id] = TM_NONE; /* not in any dedup bucket */
    m->nv++;
    return id;
}

void tm_tri(trimesh_t *m, const triangle_t *t)
{
    if (m->ntri == m->captri) {
        m->captri *= 2;
        m->tri = tm_xrealloc(m->tri, m->captri * sizeof *m->tri);
    }
    m->tri[m->ntri] = *t;
    m->ntri++;
}