From: John Tsiombikas Date: Sun, 5 Sep 2021 14:24:18 +0000 (+0300) Subject: mesh, meshgroup, scenefile X-Git-Url: http://git.mutantstargoat.com/user/nuclear/?p=vrlugburz;a=commitdiff_plain;h=f3d32774e0c196175d8143c21313097bcc8ff3a2 mesh, meshgroup, scenefile --- diff --git a/src/geom.h b/src/geom.h new file mode 100644 index 0000000..afce931 --- /dev/null +++ b/src/geom.h @@ -0,0 +1,15 @@ +#ifndef GEOM_H_ +#define GEOM_H_ + +#include "cgmath/cgmath.h" + +struct sphere { + cgm_vec3 pos; + float rad; +}; + +struct aabox { + cgm_vec3 vmin, vmax; +}; + +#endif /* GEOM_H_ */ diff --git a/src/mesh.c b/src/mesh.c new file mode 100644 index 0000000..149fbe7 --- /dev/null +++ b/src/mesh.c @@ -0,0 +1,337 @@ +#include +#include +#include +#include +#include +#define GL_GLEXT_PROTOTYPES 1 +#include +#include +#include "mesh.h" + +static int update_mesh_vbo(struct mesh *m); +static int update_meshgroup_vbo(struct meshgroup *mg); + +void init_mesh(struct mesh *m) +{ + memset(m, 0, sizeof *m); +} + +void destroy_mesh(struct mesh *m) +{ + free(m->varr); + free(m->iarr); + + if(m->vbo) { + glDeleteBuffers(1, &m->vbo); + } + if(m->ibo) { + glDeleteBuffers(1, &m->ibo); + } +} + +void clear_mesh(struct mesh *m) +{ + free(m->varr); + free(m->iarr); + + m->varr = 0; + m->iarr = 0; + m->num_verts = m->max_verts = m->num_idx = m->max_idx = 0; + m->mtl = 0; + m->bbvalid = m->vbovalid = 0; +} + +void init_meshgroup(struct meshgroup *mg) +{ + memset(mg, 0, sizeof *mg); +} + +void destroy_meshgroup(struct meshgroup *mg) +{ + free(mg->meshes); + + if(mg->vbo) { + glDeleteBuffers(1, &mg->vbo); + } + if(mg->ibo) { + glDeleteBuffers(1, &mg->ibo); + } +} + +void clear_meshgroup(struct meshgroup *mg) +{ + free(mg->meshes); + + mg->meshes = 0; + mg->num_meshes = 0; + mg->num_verts = mg->num_idx = 0; + + mg->bbvalid = mg->vbovalid = 0; +} + +void calc_mesh_bounds(struct mesh *m) +{ + int i; + struct vertex *vptr = m->varr; + + m->bb.vmin.x = m->bb.vmin.y = m->bb.vmin.z = FLT_MAX; + m->bb.vmax.x = m->bb.vmax.y = m->bb.vmax.z = -FLT_MAX; + + for(i=0; inum_verts; i++) { + if(vptr->pos.x < m->bb.vmin.x) m->bb.vmin.x = vptr->pos.x; + if(vptr->pos.y < m->bb.vmin.y) m->bb.vmin.y = vptr->pos.y; + if(vptr->pos.z < m->bb.vmin.z) m->bb.vmin.z = vptr->pos.z; + if(vptr->pos.x > m->bb.vmax.x) m->bb.vmax.x = vptr->pos.x; + if(vptr->pos.y > m->bb.vmax.y) m->bb.vmax.y = vptr->pos.y; + if(vptr->pos.z > m->bb.vmax.z) m->bb.vmax.z = vptr->pos.z; + vptr++; + } + + m->bbvalid = 1; +} + +void calc_meshgroup_bounds(struct meshgroup *mg) +{ + int i; + struct mesh *m; + + mg->bb.vmin.x = mg->bb.vmin.y = mg->bb.vmin.z = FLT_MAX; + mg->bb.vmax.x = mg->bb.vmax.y = mg->bb.vmax.z = -FLT_MAX; + + for(i=0; inum_meshes; i++) { + m = mg->meshes[i]; + if(!m->bbvalid) { + calc_mesh_bounds(m); + } + + if(m->bb.vmin.x < mg->bb.vmin.x) mg->bb.vmin.x = m->bb.vmin.x; + if(m->bb.vmin.y < mg->bb.vmin.y) mg->bb.vmin.y = m->bb.vmin.y; + if(m->bb.vmin.z < mg->bb.vmin.z) mg->bb.vmin.z = m->bb.vmin.z; + if(m->bb.vmax.x > mg->bb.vmax.x) mg->bb.vmax.x = m->bb.vmax.x; + if(m->bb.vmax.y > mg->bb.vmax.y) mg->bb.vmax.y = m->bb.vmax.y; + if(m->bb.vmax.z > mg->bb.vmax.z) mg->bb.vmax.z = m->bb.vmax.z; + } + + mg->bbvalid = 1; +} + +int add_mesh_vertex(struct mesh *m, struct vertex *v) +{ + void *tmp; + int newmax; + + if(m->num_verts >= m->max_verts) { + newmax = m->max_verts ? m->max_verts * 2 : 16; + if(!(tmp = realloc(m->varr, newmax * sizeof *m->varr))) { + return -1; + } + m->varr = tmp; + m->max_verts = newmax; + } + + m->varr[m->num_verts++] = *v; + return 0; +} + +int add_mesh_index(struct mesh *m, int idx) +{ + void *tmp; + int newmax; + + if(m->num_idx >= m->max_idx) { + newmax = m->max_idx ? m->max_idx * 2 : 16; + if(!(tmp = realloc(m->iarr, newmax * sizeof *m->iarr))) { + return -1; + } + m->iarr = tmp; + m->max_idx = newmax; + } + + m->iarr[m->num_idx++] = idx; + return 0; +} + +int add_mesh_face(struct mesh *m, int va, int vb, int vc) +{ + if(add_mesh_index(m, va) == -1) return -1; + if(add_mesh_index(m, vb) == -1) { + m->num_idx--; + return -1; + } + if(add_mesh_index(m, vc) == -1) { + m->num_idx -= 2; + return -1; + } + return 0; +} + +int add_meshgroup_mesh(struct meshgroup *mg, struct mesh *m) +{ + void *tmp; + int newmax; + + if(mg->num_meshes >= mg->max_meshes) { + newmax = mg->max_meshes ? mg->max_meshes * 2 : 16; + if(!(tmp = realloc(mg->meshes, newmax * sizeof *mg->meshes))) { + return -1; + } + mg->meshes = tmp; + mg->max_meshes = newmax; + } + + mg->meshes[mg->num_meshes++] = m; + return 0; +} + +void draw_mesh(struct mesh *m) +{ + if(!m->vbovalid) { + if(update_mesh_vbo(m) == -1) { + return; + } + } + + glEnableVertexAttribArray(MESH_ATTR_VERTEX); + glEnableVertexAttribArray(MESH_ATTR_NORMAL); + glEnableVertexAttribArray(MESH_ATTR_TANGENT); + glEnableVertexAttribArray(MESH_ATTR_TEXCOORD); + + glBindBuffer(GL_ARRAY_BUFFER, m->vbo); + glVertexAttribPointer(MESH_ATTR_VERTEX, 3, GL_FLOAT, 0, sizeof *m->varr, 0); + glVertexAttribPointer(MESH_ATTR_NORMAL, 3, GL_FLOAT, 0, sizeof *m->varr, (void*)offsetof(struct vertex, norm)); + glVertexAttribPointer(MESH_ATTR_TANGENT, 3, GL_FLOAT, 0, sizeof *m->varr, (void*)offsetof(struct vertex, tang)); + glVertexAttribPointer(MESH_ATTR_TEXCOORD, 2, GL_FLOAT, 0, sizeof *m->varr, (void*)offsetof(struct vertex, tex)); + glBindBuffer(GL_ARRAY_BUFFER, 0); + + if(m->ibo) { + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, m->ibo); + glDrawElements(GL_TRIANGLES, m->num_idx, GL_UNSIGNED_INT, 0); + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0); + } else { + glDrawArrays(GL_TRIANGLES, 0, m->num_verts); + } + + glDisableVertexAttribArray(MESH_ATTR_VERTEX); + glDisableVertexAttribArray(MESH_ATTR_NORMAL); + glDisableVertexAttribArray(MESH_ATTR_TANGENT); + glDisableVertexAttribArray(MESH_ATTR_TEXCOORD); +} + +void draw_meshgroup(struct meshgroup *mg) +{ + if(!mg->vbovalid) { + if(update_meshgroup_vbo(mg) == -1) { + return; + } + } + + glEnableVertexAttribArray(MESH_ATTR_VERTEX); + glEnableVertexAttribArray(MESH_ATTR_NORMAL); + glEnableVertexAttribArray(MESH_ATTR_TANGENT); + glEnableVertexAttribArray(MESH_ATTR_TEXCOORD); + + glBindBuffer(GL_ARRAY_BUFFER, mg->vbo); + glVertexAttribPointer(MESH_ATTR_VERTEX, 3, GL_FLOAT, 0, sizeof(struct vertex), 0); + glVertexAttribPointer(MESH_ATTR_NORMAL, 3, GL_FLOAT, 0, sizeof(struct vertex), (void*)offsetof(struct vertex, norm)); + glVertexAttribPointer(MESH_ATTR_TANGENT, 3, GL_FLOAT, 0, sizeof(struct vertex), (void*)offsetof(struct vertex, tang)); + glVertexAttribPointer(MESH_ATTR_TEXCOORD, 2, GL_FLOAT, 0, sizeof(struct vertex), (void*)offsetof(struct vertex, tex)); + glBindBuffer(GL_ARRAY_BUFFER, 0); + + if(mg->ibo) { + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, mg->ibo); + glDrawElements(GL_TRIANGLES, mg->num_idx, GL_UNSIGNED_INT, 0); + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0); + } else { + glDrawArrays(GL_TRIANGLES, 0, mg->num_verts); + } + + glDisableVertexAttribArray(MESH_ATTR_VERTEX); + glDisableVertexAttribArray(MESH_ATTR_NORMAL); + glDisableVertexAttribArray(MESH_ATTR_TANGENT); + glDisableVertexAttribArray(MESH_ATTR_TEXCOORD); +} + +static int update_mesh_vbo(struct mesh *m) +{ + if(m->num_verts <= 0) return -1; + + if(!m->vbo) { + glGenBuffers(1, &m->vbo); + } + glBindBuffer(GL_ARRAY_BUFFER, m->vbo); + glBufferData(GL_ARRAY_BUFFER, m->num_verts * sizeof *m->varr, m->varr, GL_STATIC_DRAW); + glBindBuffer(GL_ARRAY_BUFFER, 0); + + if(m->num_idx > 0) { + if(!m->ibo) { + glGenBuffers(1, &m->ibo); + } + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, m->ibo); + glBufferData(GL_ELEMENT_ARRAY_BUFFER, m->num_idx * sizeof *m->iarr, + m->iarr, GL_STATIC_DRAW); + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0); + } + return 0; +} + +static int update_meshgroup_vbo(struct meshgroup *mg) +{ + int i; + struct vertex *varr, *vptr; + unsigned int *iarr = 0, *iptr; + struct mesh *m; + + mg->num_verts = mg->num_idx = 0; + + for(i=0; inum_meshes; i++) { + mg->num_verts += mg->meshes[i]->num_verts; + mg->num_idx += mg->meshes[i]->num_idx; + } + + if(mg->num_verts <= 0) return -1; + + if(!(varr = malloc(mg->num_verts * sizeof *varr))) { + fprintf(stderr, "update_meshgroup_vbo: failed to allocate vertex array with %d vertices\n", mg->num_verts); + return -1; + } + if(mg->num_idx > 0) { + if(!(iarr = malloc(mg->num_idx * sizeof *iarr))) { + fprintf(stderr, "update_meshgroup_vbo: failed to allocate index array with %d indices\n", mg->num_idx); + free(varr); + return -1; + } + } + + vptr = varr; + iptr = iarr; + + for(i=0; inum_meshes; i++) { + m = mg->meshes[i]; + memcpy(vptr, m->varr, m->num_verts * sizeof *vptr); + vptr += m->num_verts; + + if(iarr) { + memcpy(iptr, m->iarr, m->num_idx * sizeof *iptr); + iptr += m->num_idx; + } + } + + if(!mg->vbo) { + glGenBuffers(1, &mg->vbo); + } + glBindBuffer(GL_ARRAY_BUFFER, mg->vbo); + glBufferData(GL_ARRAY_BUFFER, mg->num_verts * sizeof *varr, varr, GL_STATIC_DRAW); + glBindBuffer(GL_ARRAY_BUFFER, 0); + if(iarr) { + if(!mg->ibo) { + glGenBuffers(1, &mg->ibo); + } + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, mg->ibo); + glBufferData(GL_ELEMENT_ARRAY_BUFFER, mg->num_idx * sizeof *iarr, iarr, GL_STATIC_DRAW); + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0); + } + + free(varr); + free(iarr); + return 0; +} diff --git a/src/mesh.h b/src/mesh.h new file mode 100644 index 0000000..b0a0a4b --- /dev/null +++ b/src/mesh.h @@ -0,0 +1,89 @@ +#ifndef MESH_H_ +#define MESH_H_ + +#include "cgmath/cgmath.h" +#include "geom.h" + +enum { + MESH_ATTR_VERTEX, + MESH_ATTR_NORMAL, + MESH_ATTR_TANGENT, + MESH_ATTR_TEXCOORD +}; + +struct vertex { + cgm_vec3 pos; + cgm_vec3 norm; + cgm_vec3 tang; + cgm_vec2 tex; +}; + +enum { + TEX_DIFFUSE, + TEX_SPECULAR, + TEX_NORMAL, + + NUM_TEX_SLOTS +}; + +struct material { + char *name; + + cgm_vec3 color; + cgm_vec3 spec; + float shininess; + + unsigned int tex[NUM_TEX_SLOTS]; + + struct material *next; +}; + +struct mesh { + struct vertex *varr; + unsigned int *iarr; + int num_verts, num_idx; + int max_verts, max_idx; + + struct material *mtl; + + struct aabox bb; + int bbvalid; + + unsigned int vbo, ibo; + int vbovalid; + + struct mesh *next; +}; + +struct meshgroup { + struct mesh **meshes; + int num_meshes, max_meshes; + + struct aabox bb; + int bbvalid; + + int num_verts, num_idx; + unsigned int vbo, ibo; + int vbovalid; +}; + +void init_mesh(struct mesh *m); +void destroy_mesh(struct mesh *m); +void clear_mesh(struct mesh *m); + +void init_meshgroup(struct meshgroup *mg); +void destroy_meshgroup(struct meshgroup *mg); +void clear_meshgroup(struct meshgroup *mg); + +void calc_mesh_bounds(struct mesh *m); + +int add_mesh_vertex(struct mesh *m, struct vertex *v); +int add_mesh_index(struct mesh *m, int idx); +int add_mesh_face(struct mesh *m, int va, int vb, int vc); + +int add_meshgroup_mesh(struct meshgroup *mg, struct mesh *m); + +void draw_mesh(struct mesh *m); +void draw_meshgroup(struct meshgroup *mg); + +#endif /* MESH_H_ */ diff --git a/src/rbtree.c b/src/rbtree.c new file mode 100644 index 0000000..f7ab537 --- /dev/null +++ b/src/rbtree.c @@ -0,0 +1,508 @@ +/* +rbtree - simple balanced binary search tree (red-black tree) library. +Copyright (C) 2011-2014 John Tsiombikas + +rbtree is free software, feel free to use, modify, and redistribute it, under +the terms of the 3-clause BSD license. See COPYING for details. +*/ +#include +#include +#include +#include +#include "rbtree.h" + +#define INT2PTR(x) ((void*)(intptr_t)(x)) +#define PTR2INT(x) ((int)(intptr_t)(x)) + +struct rbtree { + struct rbnode *root; + + rb_alloc_func_t alloc; + rb_free_func_t free; + + rb_cmp_func_t cmp; + rb_del_func_t del; + void *del_cls; + + struct rbnode *rstack, *iter; +}; + +static int cmpaddr(const void *ap, const void *bp); +static int cmpint(const void *ap, const void *bp); + +static int count_nodes(struct rbnode *node); +static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls); +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data); +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key); +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);*/ +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls); + +struct rbtree *rb_create(rb_cmp_func_t cmp_func) +{ + struct rbtree *rb; + + if(!(rb = malloc(sizeof *rb))) { + return 0; + } + if(rb_init(rb, cmp_func) == -1) { + free(rb); + return 0; + } + return rb; +} + +void rb_free(struct rbtree *rb) +{ + rb_destroy(rb); + free(rb); +} + + +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func) +{ + memset(rb, 0, sizeof *rb); + + if(!cmp_func) { + rb->cmp = cmpaddr; + } else if(cmp_func == RB_KEY_INT) { + rb->cmp = cmpint; + } else if(cmp_func == RB_KEY_STRING) { + rb->cmp = (rb_cmp_func_t)strcmp; + } else { + rb->cmp = cmp_func; + } + + rb->alloc = malloc; + rb->free = free; + return 0; +} + +void rb_destroy(struct rbtree *rb) +{ + del_tree(rb->root, rb->del, rb->del_cls); +} + +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free) +{ + rb->alloc = alloc; + rb->free = free; +} + + +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func) +{ + rb->cmp = func; +} + +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls) +{ + rb->del = func; + rb->del_cls = cls; +} + + +void rb_clear(struct rbtree *rb) +{ + del_tree(rb->root, rb->del, rb->del_cls); + rb->root = 0; +} + +int rb_copy(struct rbtree *dest, struct rbtree *src) +{ + struct rbnode *node; + + rb_clear(dest); + rb_begin(src); + while((node = rb_next(src))) { + if(rb_insert(dest, node->key, node->data) == -1) { + return -1; + } + } + return 0; +} + +int rb_size(struct rbtree *rb) +{ + return count_nodes(rb->root); +} + +int rb_insert(struct rbtree *rb, void *key, void *data) +{ + rb->root = insert(rb, rb->root, key, data); + rb->root->red = 0; + return 0; +} + +int rb_inserti(struct rbtree *rb, int key, void *data) +{ + rb->root = insert(rb, rb->root, INT2PTR(key), data); + rb->root->red = 0; + return 0; +} + + +int rb_delete(struct rbtree *rb, void *key) +{ + if((rb->root = delete(rb, rb->root, key))) { + rb->root->red = 0; + } + return 0; +} + +int rb_deletei(struct rbtree *rb, int key) +{ + if((rb->root = delete(rb, rb->root, INT2PTR(key)))) { + rb->root->red = 0; + } + return 0; +} + + +struct rbnode *rb_find(struct rbtree *rb, void *key) +{ + struct rbnode *node = rb->root; + + while(node) { + int cmp = rb->cmp(key, node->key); + if(cmp == 0) { + return node; + } + node = cmp < 0 ? node->left : node->right; + } + return 0; +} + +struct rbnode *rb_findi(struct rbtree *rb, int key) +{ + return rb_find(rb, INT2PTR(key)); +} + + +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls) +{ + traverse(rb->root, func, cls); +} + + +struct rbnode *rb_root(struct rbtree *rb) +{ + return rb->root; +} + +void rb_begin(struct rbtree *rb) +{ + rb->rstack = 0; + rb->iter = rb->root; +} + +#define push(sp, x) ((x)->next = (sp), (sp) = (x)) +#define pop(sp) ((sp) = (sp)->next) +#define top(sp) (sp) + +struct rbnode *rb_next(struct rbtree *rb) +{ + struct rbnode *res = 0; + + while(rb->rstack || rb->iter) { + if(rb->iter) { + push(rb->rstack, rb->iter); + rb->iter = rb->iter->left; + } else { + rb->iter = top(rb->rstack); + pop(rb->rstack); + res = rb->iter; + rb->iter = rb->iter->right; + break; + } + } + return res; +} + +void *rb_node_key(struct rbnode *node) +{ + return node ? node->key : 0; +} + +int rb_node_keyi(struct rbnode *node) +{ + return node ? PTR2INT(node->key) : 0; +} + +void *rb_node_data(struct rbnode *node) +{ + return node ? node->data : 0; +} + +void rb_node_setdata(struct rbnode *node, void *data) +{ + node->data = data; +} + +static int cmpaddr(const void *ap, const void *bp) +{ + return ap < bp ? -1 : (ap > bp ? 1 : 0); +} + +static int cmpint(const void *ap, const void *bp) +{ + return PTR2INT(ap) - PTR2INT(bp); +} + + +/* ---- left-leaning 2-3 red-black implementation ---- */ + +/* helper prototypes */ +static int is_red(struct rbnode *tree); +static void color_flip(struct rbnode *tree); +static struct rbnode *rot_left(struct rbnode *a); +static struct rbnode *rot_right(struct rbnode *a); +static struct rbnode *find_min(struct rbnode *tree); +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree); +/*static struct rbnode *move_red_right(struct rbnode *tree);*/ +static struct rbnode *move_red_left(struct rbnode *tree); +static struct rbnode *fix_up(struct rbnode *tree); + +static int count_nodes(struct rbnode *node) +{ + if(!node) + return 0; + + return 1 + count_nodes(node->left) + count_nodes(node->right); +} + +static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls) +{ + if(!node) + return; + + del_tree(node->left, delfunc, cls); + del_tree(node->right, delfunc, cls); + + if(delfunc) { + delfunc(node, cls); + } + free(node); +} + +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data) +{ + int cmp; + + if(!tree) { + struct rbnode *node = rb->alloc(sizeof *node); + node->red = 1; + node->key = key; + node->data = data; + node->left = node->right = 0; + return node; + } + + cmp = rb->cmp(key, tree->key); + + if(cmp < 0) { + tree->left = insert(rb, tree->left, key, data); + } else if(cmp > 0) { + tree->right = insert(rb, tree->right, key, data); + } else { + tree->data = data; + } + + /* fix right-leaning reds */ + if(is_red(tree->right)) { + tree = rot_left(tree); + } + /* fix two reds in a row */ + if(is_red(tree->left) && is_red(tree->left->left)) { + tree = rot_right(tree); + } + + /* if 4-node, split it by color inversion */ + if(is_red(tree->left) && is_red(tree->right)) { + color_flip(tree); + } + + return tree; +} + +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key) +{ + int cmp; + + if(!tree) { + return 0; + } + + cmp = rb->cmp(key, tree->key); + + if(cmp < 0) { + if(!is_red(tree->left) && !is_red(tree->left->left)) { + tree = move_red_left(tree); + } + tree->left = delete(rb, tree->left, key); + } else { + /* need reds on the right */ + if(is_red(tree->left)) { + tree = rot_right(tree); + } + + /* found it at the bottom (XXX what certifies left is null?) */ + if(cmp == 0 && !tree->right) { + if(rb->del) { + rb->del(tree, rb->del_cls); + } + rb->free(tree); + return 0; + } + + if(!is_red(tree->right) && !is_red(tree->right->left)) { + tree = move_red_left(tree); + } + + if(key == tree->key) { + struct rbnode *rmin = find_min(tree->right); + tree->key = rmin->key; + tree->data = rmin->data; + tree->right = del_min(rb, tree->right); + } else { + tree->right = delete(rb, tree->right, key); + } + } + + return fix_up(tree); +} + +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key) +{ + int cmp; + + if(!node) + return 0; + + if((cmp = rb->cmp(key, node->key)) == 0) { + return node; + } + return find(rb, cmp < 0 ? node->left : node->right, key); +}*/ + +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls) +{ + if(!node) + return; + + traverse(node->left, func, cls); + func(node, cls); + traverse(node->right, func, cls); +} + +/* helpers */ + +static int is_red(struct rbnode *tree) +{ + return tree && tree->red; +} + +static void color_flip(struct rbnode *tree) +{ + tree->red = !tree->red; + tree->left->red = !tree->left->red; + tree->right->red = !tree->right->red; +} + +static struct rbnode *rot_left(struct rbnode *a) +{ + struct rbnode *b = a->right; + a->right = b->left; + b->left = a; + b->red = a->red; + a->red = 1; + return b; +} + +static struct rbnode *rot_right(struct rbnode *a) +{ + struct rbnode *b = a->left; + a->left = b->right; + b->right = a; + b->red = a->red; + a->red = 1; + return b; +} + +static struct rbnode *find_min(struct rbnode *tree) +{ + if(!tree) + return 0; + + while(tree->left) { + tree = tree->left; + } + return tree; +} + +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree) +{ + if(!tree->left) { + if(rb->del) { + rb->del(tree->left, rb->del_cls); + } + rb->free(tree->left); + return 0; + } + + /* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */ + if(!is_red(tree->left) && !is_red(tree->left->left)) { + tree = move_red_left(tree); + } + tree->left = del_min(rb, tree->left); + + /* fix right-reds, red-reds, and split 4-nodes on the way up */ + return fix_up(tree); +} + +#if 0 +/* push a red link on this node to the right */ +static struct rbnode *move_red_right(struct rbnode *tree) +{ + /* flipping it makes both children go red, so we have a red to the right */ + color_flip(tree); + + /* if after the flip we've got a red-red situation to the left, fix it */ + if(is_red(tree->left->left)) { + tree = rot_right(tree); + color_flip(tree); + } + return tree; +} +#endif + +/* push a red link on this node to the left */ +static struct rbnode *move_red_left(struct rbnode *tree) +{ + /* flipping it makes both children go red, so we have a red to the left */ + color_flip(tree); + + /* if after the flip we've got a red-red on the right-left, fix it */ + if(is_red(tree->right->left)) { + tree->right = rot_right(tree->right); + tree = rot_left(tree); + color_flip(tree); + } + return tree; +} + +static struct rbnode *fix_up(struct rbnode *tree) +{ + /* fix right-leaning */ + if(is_red(tree->right)) { + tree = rot_left(tree); + } + /* change invalid red-red pairs into a proper 4-node */ + if(is_red(tree->left) && is_red(tree->left->left)) { + tree = rot_right(tree); + } + /* split 4-nodes */ + if(is_red(tree->left) && is_red(tree->right)) { + color_flip(tree); + } + return tree; +} diff --git a/src/rbtree.h b/src/rbtree.h new file mode 100644 index 0000000..dada0dc --- /dev/null +++ b/src/rbtree.h @@ -0,0 +1,79 @@ +/* +rbtree - simple balanced binary search tree (red-black tree) library. +Copyright (C) 2011-2014 John Tsiombikas + +rbtree is free software, feel free to use, modify, and redistribute it, under +the terms of the 3-clause BSD license. See COPYING for details. +*/ +#ifndef RBTREE_H_ +#define RBTREE_H_ + +struct rbtree; + + +struct rbnode { + void *key, *data; + int red; + struct rbnode *left, *right; + struct rbnode *next; /* for iterator stack */ +}; + + +typedef void *(*rb_alloc_func_t)(size_t); +typedef void (*rb_free_func_t)(void*); + +typedef int (*rb_cmp_func_t)(const void*, const void*); +typedef void (*rb_del_func_t)(struct rbnode*, void*); + +#define RB_KEY_ADDR (rb_cmp_func_t)(0) +#define RB_KEY_INT (rb_cmp_func_t)(1) +#define RB_KEY_STRING (rb_cmp_func_t)(3) + + +#ifdef __cplusplus +extern "C" { +#endif + +struct rbtree *rb_create(rb_cmp_func_t cmp_func); +void rb_free(struct rbtree *rb); + +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func); +void rb_destroy(struct rbtree *rb); + +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free); +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func); +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls); +/* TODO add user deep copy function */ + +void rb_clear(struct rbtree *rb); +int rb_copy(struct rbtree *dest, struct rbtree *src); + +int rb_size(struct rbtree *rb); + +int rb_insert(struct rbtree *rb, void *key, void *data); +int rb_inserti(struct rbtree *rb, int key, void *data); + +int rb_delete(struct rbtree *rb, void *key); +int rb_deletei(struct rbtree *rb, int key); + +struct rbnode *rb_find(struct rbtree *rb, void *key); +struct rbnode *rb_findi(struct rbtree *rb, int key); + +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls); + +struct rbnode *rb_root(struct rbtree *rb); + +void rb_begin(struct rbtree *rb); +struct rbnode *rb_next(struct rbtree *rb); + +void *rb_node_key(struct rbnode *node); +int rb_node_keyi(struct rbnode *node); +void *rb_node_data(struct rbnode *node); +void rb_node_setdata(struct rbnode *node, void *data); + +#ifdef __cplusplus +} +#endif + + +#endif /* RBTREE_H_ */ diff --git a/src/scenefile.c b/src/scenefile.c new file mode 100644 index 0000000..39d9b92 --- /dev/null +++ b/src/scenefile.c @@ -0,0 +1,441 @@ +#include +#include +#include +#include +#include "cgmath/cgmath.h" +#include "scenefile.h" +#include "rbtree.h" + +struct facevertex { + int vidx, tidx, nidx; +}; + +struct objmtl { + char *name; + cgm_vec3 ka, kd, ks, ke; + float shin; + float alpha; + float ior; + char *map_kd, *map_ke, *map_alpha; + struct objmtl *next; +}; + +static int proc_facevert(struct mesh *mesh, struct facevertex *fv, + cgm_vec3 *varr, cgm_vec3 *narr, cgm_vec2 *tarr, struct rbtree *rbtree); + +static char *cleanline(char *s); +static char *parse_idx(char *ptr, int *idx, int arrsz); +static char *parse_face_vert(char *ptr, struct facevertex *fv, int numv, int numt, int numn); + +static int load_mtllib(struct scenefile *scn, const char *path_prefix, const char *mtlfname); +static void free_mtllist(struct material *mtl); +static void conv_mtl(struct material *mm, struct objmtl *om, const char *path_prefix); + +static int cmp_facevert(const void *ap, const void *bp); +static void free_rbnode_key(struct rbnode *n, void *cls); + +#define GROW_ARRAY(arr, sz) \ + do { \ + int newsz = (sz) ? (sz) * 2 : 16; \ + void *tmp = realloc(arr, newsz * sizeof *(arr)); \ + if(!tmp) { \ + fprintf(stderr, "failed to grow array to %d\n", newsz); \ + goto fail; \ + } \ + arr = tmp; \ + sz = newsz; \ + } while(0) + + +int load_scenefile(struct scenefile *scn, const char *fname) +{ + int i, nlines, res = -1; + FILE *fp; + char buf[256], *line, *ptr, *path_prefix; + int varr_size, varr_max, narr_size, narr_max, tarr_size, tarr_max; + cgm_vec3 v, *varr = 0, *narr = 0; + cgm_vec2 *tarr = 0; + struct facevertex fv[4]; + struct mesh *mesh; + struct material *mtl = 0; + char *sep; + struct rbtree *rbtree = 0; + + + varr_size = varr_max = narr_size = narr_max = tarr_size = tarr_max = 0; + varr = narr = 0; + tarr = 0; + + if(!(fp = fopen(fname, "rb"))) { + fprintf(stderr, "load_scenefile: failed to open %s\n", fname); + return -1; + } + + if(!(rbtree = rb_create(cmp_facevert))) { + fprintf(stderr, "load_scenefile: failed to create facevertex search tree\n"); + fclose(fp); + return -1; + } + rb_set_delete_func(rbtree, free_rbnode_key, 0); + + strcpy(buf, fname); + if((sep = strrchr(buf, '/'))) { + sep[1] = 0; + } else { + buf[0] = 0; + } + path_prefix = alloca(strlen(buf) + 1); + strcpy(path_prefix, buf); + + if(!(mesh = malloc(sizeof *mesh))) { + fprintf(stderr, "failed to allocate mesh\n"); + fclose(fp); + return -1; + } + init_mesh(mesh); + + scn->meshlist = 0; + scn->num_meshes = 0; + + nlines = 0; + while(fgets(buf, sizeof buf, fp)) { + nlines++; + if(!(line = cleanline(buf))) { + continue; + } + + switch(line[0]) { + case 'v': + v.x = v.y = v.z = 0.0f; + if(sscanf(line + 2, "%f %f %f", &v.x, &v.y, &v.z) < 2) { + break; + } + if(isspace(line[1])) { + if(varr_size >= varr_max) { + GROW_ARRAY(varr, varr_max); + } + varr[varr_size++] = v; + } else if(line[1] == 't' && isspace(line[2])) { + if(tarr_size >= tarr_max) { + GROW_ARRAY(tarr, tarr_max); + } + tarr[tarr_size++] = *(cgm_vec2*)&v; + } else if(line[1] == 'n' && isspace(line[2])) { + if(narr_size >= narr_max) { + GROW_ARRAY(narr, narr_max); + } + narr[narr_size++] = v; + } + break; + + case 'f': + if(!isspace(line[1])) break; + + ptr = line + 2; + + for(i=0; i<3; i++) { + if(!(ptr = parse_face_vert(ptr, fv + i, varr_size, tarr_size, narr_size))) { + break; + } + if(proc_facevert(mesh, fv + i, varr, narr, tarr, rbtree) == -1) { + break; + } + } + + if(parse_face_vert(ptr, fv + 3, varr_size, tarr_size, narr_size)) { + proc_facevert(mesh, fv, varr, narr, tarr, rbtree); + proc_facevert(mesh, fv + 2, varr, narr, tarr, rbtree); + proc_facevert(mesh, fv + 3, varr, narr, tarr, rbtree); + } + break; + + case 'o': + case 'g': + if(mesh->num_verts) { + mesh->mtl = mtl; + mesh->next = scn->meshlist; + scn->meshlist = mesh; + scn->num_meshes++; + + if(!(mesh = malloc(sizeof *mesh))) { + fprintf(stderr, "failed to allocate mesh\n"); + goto fail; + } + init_mesh(mesh); + } + break; + + case 'm': + if(memcmp(line, "mtllib", 6) == 0 && (line = cleanline(line + 6))) { + free_mtllist(scn->mtllist); + load_mtllib(scn, path_prefix, line); + } + break; + + case 'u': + if(memcmp(line, "usemtl", 6) == 0 && (line = cleanline(line + 6))) { + mtl = scn->mtllist; + while(mtl) { + if(strcmp(mtl->name, line) == 0) { + break; + } + mtl = mtl->next; + } + } + break; + + default: + break; + } + } + + if(mesh->num_verts) { + mesh->mtl = mtl; + mesh->next = scn->meshlist; + scn->meshlist = mesh; + scn->num_meshes++; + } else { + free(mesh); + } + mesh = 0; + + printf("load_scenefile: loaded %d meshes, %d vertices\n", scn->num_meshes, + varr_size); + + res = 0; + +fail: + fclose(fp); + free(mesh); + free(varr); + free(narr); + free(tarr); + rb_free(rbtree); + return res; +} + +static int proc_facevert(struct mesh *mesh, struct facevertex *fv, + cgm_vec3 *varr, cgm_vec3 *narr, cgm_vec2 *tarr, struct rbtree *rbtree) +{ + struct rbnode *node; + unsigned int idx, newidx; + struct facevertex *newfv; + struct vertex v; + + if((node = rb_find(rbtree, &fv))) { + idx = (unsigned int)node->data; + assert(idx < mesh->num_verts); + } else { + newidx = mesh->num_verts; + + v.pos = varr[fv->vidx]; + if(fv->nidx >= 0) { + v.norm = narr[fv->nidx]; + } + if(fv->tidx >= 0) { + v.tex = tarr[fv->tidx]; + } + add_mesh_vertex(mesh, &v); + add_mesh_index(mesh, newidx); + } + + if((newfv = malloc(sizeof *newfv))) { + *newfv = *fv; + } + if(!newfv || rb_insert(rbtree, newfv, (void*)newidx) == -1) { + fprintf(stderr, "load_scenefile: failed to insert facevertex to rbtree\n"); + free(newfv); + return -1; + } + return 0; +} + +void destroy_scenefile(struct scenefile *scn) +{ + struct mesh *m; + while(scn->meshlist) { + m = scn->meshlist; + scn->meshlist = scn->meshlist->next; + free(m); + } +} + +static char *cleanline(char *s) +{ + char *ptr; + + if((ptr = strchr(s, '#'))) *ptr = 0; + + while(*s && isspace(*s)) s++; + ptr = s + strlen(s) - 1; + while(ptr >= s && isspace(*ptr)) *ptr-- = 0; + + return *s ? s : 0; +} + +static char *parse_idx(char *ptr, int *idx, int arrsz) +{ + char *endp; + int val = strtol(ptr, &endp, 10); + if(endp == ptr) return 0; + + if(val < 0) { /* convert negative indices */ + *idx = arrsz + val; + } else { + *idx = val - 1; /* indices in obj are 1-based */ + } + return endp; +} + +/* possible face-vertex definitions: + * 1. vertex + * 2. vertex/texcoord + * 3. vertex//normal + * 4. vertex/texcoord/normal + */ +static char *parse_face_vert(char *ptr, struct facevertex *fv, int numv, int numt, int numn) +{ + fv->tidx = fv->nidx = -1; + + if(!(ptr = parse_idx(ptr, &fv->vidx, numv))) + return 0; + if(*ptr != '/') return (!*ptr || isspace(*ptr)) ? ptr : 0; + + if(*++ptr == '/') { /* no texcoord */ + ++ptr; + } else { + if(!(ptr = parse_idx(ptr, &fv->tidx, numt))) + return 0; + if(*ptr != '/') return (!*ptr || isspace(*ptr)) ? ptr : 0; + ++ptr; + } + + if(!(ptr = parse_idx(ptr, &fv->nidx, numn))) + return 0; + return (!*ptr || isspace(*ptr)) ? ptr : 0; +} + +static int load_mtllib(struct scenefile *scn, const char *path_prefix, const char *mtlfname) +{ + FILE *fp; + char buf[256], *line; + struct objmtl om; + struct material *mtl; + + if(path_prefix && *path_prefix) { + sprintf(buf, "%s/%s", path_prefix, mtlfname); + } else { + strcpy(buf, mtlfname); + } + + if(!(fp = fopen(buf, "rb"))) { + return -1; + } + + while(fgets(buf, sizeof buf, fp)) { + if(!(line = cleanline(buf))) { + continue; + } + + if(memcmp(line, "newmtl", 6) == 0) { + if(mtl) { + mtl->next = scn->mtllist; + scn->mtllist = mtl; + } + if((mtl = calloc(1, sizeof *mtl))) { + if((line = cleanline(line + 6))) { + mtl->name = strdup(line); + } + } + } else if(memcmp(line, "Kd", 2) == 0) { + sscanf(line + 3, "%f %f %f", &om.kd.x, &om.kd.y, &om.kd.z); + } else if(memcmp(line, "Ks", 2) == 0) { + sscanf(line + 3, "%f %f %f", &om.ks.x, &om.ks.y, &om.ks.z); + } else if(memcmp(line, "Ke", 2) == 0) { + sscanf(line + 3, "%f %f %f", &om.ke.x, &om.ke.y, &om.ke.z); + } else if(memcmp(line, "Ni", 2) == 0) { + om.ior = atof(line + 3); + } else if(line[0] == 'd' && isspace(line[1])) { + om.alpha = atof(line + 2); + } else if(memcmp(line, "map_Kd", 6) == 0) { + if((line = cleanline(line + 6))) { + om.map_kd = strdup(line); + } + } else if(memcmp(line, "map_Ke", 6) == 0) { + if((line = cleanline(line + 6))) { + om.map_ke = strdup(line); + } + } else if(memcmp(line, "map_d", 5) == 0) { + if((line = cleanline(line + 5))) { + om.map_alpha = strdup(line); + } + } + conv_mtl(mtl, &om, path_prefix); + } + + if(mtl) { + mtl->next = scn->mtllist; + scn->mtllist = mtl; + } + + fclose(fp); + return 0; +} + +static void free_mtllist(struct material *mtl) +{ + while(mtl) { + void *tmp = mtl; + mtl = mtl->next; + free(tmp); + } +} + +static void conv_mtl(struct material *mm, struct objmtl *om, const char *path_prefix) +{ + char *fname = 0, *suffix = 0; + int len, prefix_len, maxlen = 0; + + memset(mm, 0, sizeof *mm); + mm->name = strdup(om->name); + mm->color = om->kd; + mm->spec = om->ks; + mm->shininess = om->shin; + + if(om->map_kd && (len = strlen(om->map_kd)) > maxlen) maxlen = len; + if(om->map_ke && (len = strlen(om->map_ke)) > maxlen) maxlen = len; + if(om->map_alpha && (len = strlen(om->map_alpha)) > maxlen) maxlen = len; + + if(maxlen) { + prefix_len = strlen(path_prefix); + fname = alloca(maxlen + prefix_len + 2); + suffix = fname + prefix_len; + strcpy(fname, path_prefix); + } + + /* + if(om->map_kd) { + strcpy(suffix, om->map_kd); + mm->tex[TEX_DIFFUSE] = get_image(fname); + } + */ +} + +static int cmp_facevert(const void *ap, const void *bp) +{ + const struct facevertex *a = ap; + const struct facevertex *b = bp; + + if(a->vidx == b->vidx) { + if(a->tidx == b->tidx) { + return a->nidx - b->nidx; + } + return a->tidx - b->tidx; + } + return a->vidx - b->vidx; +} + +static void free_rbnode_key(struct rbnode *n, void *cls) +{ + free(n->key); +} diff --git a/src/scenefile.h b/src/scenefile.h new file mode 100644 index 0000000..29e9268 --- /dev/null +++ b/src/scenefile.h @@ -0,0 +1,17 @@ +#ifndef SCENEFILE_H_ +#define SCENEFILE_H_ + +#include "mesh.h" + +struct scenefile { + struct mesh *meshlist; + int num_meshes; + + struct material *mtllist; + int num_mtl; +}; + +int load_scenefile(struct scenefile *scn, const char *fname); +void destroy_scenefile(struct scenefile *scn); + +#endif /* SCENEFILE_H_ */